Luận văn trình bày một số thuật toán số học và ứng dụng; thuật toán phân tích một số nguyên ra các thừa số nguyên tố bắt đầu từ sàng Eratosthennes, phương pháp RHO của Pollard, phân tích Fermat, phương pháp Squfof, thuật toán Dixon, thuật toán sàng bậc hai.
Luận văn được bảo vệ trước Hội đồng chấm luận văn tại:
Trường đại học Thăng Long
Vào hồi 09 giờ 00 ngày 28 tháng 12 năm 2018
Trang
Mở đầu 1
Chương 1 Thuật toán và tư duy thuật toán
2 2 2 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1 Thuật toán 1.2 Độ phức tạp của thuật toán . . . . . . . . . . . . . . . . . . . . . 1.3 Tư duy thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . .
Chương 2 Một số thuật toán số học thông dụng
4 4 4 5 5 6 6 7 7 7 7 9 2.1 Kiến thức cơ bản . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1 Tính chia hết . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.2 Số nguyên tố . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.3 Đồng dư . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.4 Hệ thặng dư và lớp thặng dư . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.5 Phân số liên tục 2.2 Một số thuật toán tìm ước chung lớn nhất . . . . . . . . . . . . . 2.2.1 Thuật toán Euclid . . . . . . . . . . . . . . . . . . . . . . 2.2.2 Thuật toán J.Stein . . . . . . . . . . . . . . . . . . . . . . 2.2.3 Thuật toán Euclid mở rộng . . . . . . . . . . . . . . . . . 2.2.4 Định lý Fermat nhỏ . . . . . . . . . . . . . . . . . . . . .
2.3 Một số thuật toán phân tích số nguyên thành tích các thừa số
iii
nguyên tố đặc biệt . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3.1 Phân tích số nguyên bằng sàng Erathostenes . . . . . . . 11 2.3.2 Pollard’s rho method . . . . . . . . . . . . . . . . . . . . . 11 2.3.3 Đường cong Eliptic . . . . . . . . . . . . . . . . . . . . . . 13 2.3.4 Phương pháp của Fermat . . . . . . . . . . . . . . . . . . 15 . . . . . . . . . . . . . . . . . . . . . 16 2.3.5 Phương pháp Squfof 2.3.6 Thuật toán Dixon . . . . . . . . . . . . . . . . . . . . . . 16 2.3.7 Thuật toán Sàng bậc hai-Quadratic Sieve . . . . . . . . . 17
Chương 3 Hệ mã khóa RSA, chữ ký số và hàm băm mật mã
19 3.1 Hệ mã hóa RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.2 Tạo khóa, mã hóa, giải mã của hệ RSA . . . . . . . . . . . . . . 19 3.3 Chữ ký điện tử-Chữ ký số . . . . . . . . . . . . . . . . . . . . . . 20 3.4 Hàm băm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.4.1 Phương thức mã hóa MD5 . . . . . . . . . . . . . . . . . 21 3.4.2 Phương thức mã hóa SHA1 . . . . . . . . . . . . . . . . . 25
Kết luận 31
iv
Tài liệu tham khảo 32
Số học là một môn khoa học lý thú, hấp dẫn những người học và làm toán, các giáo viên, học sinh trên khắp thế giới. Mặc dù khoa học kỹ thuật ngày nay rất phát triển nhưng có những bài toán từ thời cổ đại vẫn còn giá trị đến tận bây giờ và việc đi tìm một thuật toán phân tích số nguyên ra tích các thừa số nguyên tố là một trong những thuật toán như vậy. Chính nhờ độ khó của việc phân tích số nguyên thành tích các thừa số nguyên tố đã là cơ sở cho sự ra đời của mật mã học.
Luận văn này trình bày một số thuật toán số học và ứng dụng. Thuật toán phân tích một số nguyên ra các thừa số nguyên tố bắt đầu từ sàng Eratosthennes, phương pháp RHO của Pollard, phân tích Fermat, phương pháp Squfof, thuật toán Dixon, thuật toán sàng bậc hai. Luận văn được chia làm ba chương:
1. Chương 1: Thuật toán và tư duy thuật toán trình bày những khái niệm
cơ bản về thuật toán, độ phức tạp và tư duy thuật toán.
2. Chương 2: Một số thuật toán thông dụng trình bày một số kiến thức cơ
bản về một số thuật toán số học thông dụng.
1
3. Chương 3: Hệ mã khóa RSA và chữ ký số trình bày một số ứng dụng của thuật toán phân tích số nguyên thành tích các thừa số nguyên tố vào mật mã và tạo chữ ký số.
Chương này trình bày những khái niệm cơ bản về thuật toán, độ phức tạp và tư duy thuật toán. Nội dung của chương này được hình thành từ tài liệu [1].
Định nghĩa 1.1. Thuật toán là một quy tắc, thao tác để với những dữ liệu ban đầu đã cho, ta tìm được lời giải cho bài toán sau một khoảng thời gian hữu hạn.
Trong thuật toán cần có: Đầu vào: input. Đầu ra: output. Thuật toán phải bao gồm nhiều bước và phải thỏa mãn yêu cầu sau:
1. Tính hữu hạn
2. Tính xác định
3. Tính hiệu quả
4. Tính phổ dụng
Để ước lượng độ phức tạp của thuật toán, ta dùng khía niệm bậc O-lớn
= C.
Định nghĩa 1.2. Giả sử f(n) và g(n) là hai hàm xác định trên tập hợp các số nguyên dương. Ta nói f(n)có bậc O-lớn của g(n) và viết: f(n)= O(g(n)) hoặc f=O(g), nếu tồn tại số C ̸= 0, sao cho với n đủ lớn, các hàm f(n) và g(n) đều
n→+∞
f (n) g(n)
2
dương và lim
Nếu thuật toán có thời gian thực hiện f(n) = O(g(n)) ta nói thời gian thực
hiện là cấp g(n).
Chúng ta cần lưu ý thêm một điểm sau đây. Trong thực tế chúng ta còn nhắc đến thuật toán ”xác suất” tức là thuật toán phụ thuộc vào một hay nhiều tham số ngẫu nhiên. Những ” thuật toán”này, về nguyên tắc không được gọi là thuật toán, vì chúng có thể, với xác suất quá bé, không bao giờ kết thúc. Tuy nhiên, thực nghiệm chỉ ra rằng, các thuật toán xác suất thường hữu hiệu hơn các thuật toán tất định. Thậm chí, trong rất nhiều trường hợp, chỉ có các thuật toán như thế là sử dụng được. Ta định nghĩa thêm: Lx[u; v] = exp(v(lnx)u.(lnlnx)1−u). Trong suốt luận văn hàm Ln được dùng để tính thời gian chạy.
Ta có: Ln[0; v] = exp(v(lnlnn)) = (lnn)v và Ln[1; v] = exp(v(lnn)) = nv. Thời gian chạy Ln[u, v] với u < 0 và v là hằng số là thời gian mũ(subexponential time.)
Tư duy thuật toán là sự tổng hợp các năng lực tư duy để giải quyết vấn đề theo một quy trình xác định hướng đến một tác nhân tương thích (tác nhân ở đây muốn nói là con người, máy tính, hay bất cứ một thiết bị nào có chức năng tính toán tự động có thể hiểu và thực hiện được thuật toán).
Tư duy thuật toán luôn định hướng vào việc mở ra một con đường lớn, một giải pháp vạn năng cho việc giải quyết hàng loạt vấn đề. Tư duy thuật toán giúp làm thay đổi quan điểm nhìn nhận vấn đề và thay đổi thói quen làm toán cho học sinh thay vì làm theo mẹo mực biến đổi thì sẽ làm toán theo cơ bản và có tính ứng dụng rộng rãi, tổng quát cho nhiều trường hợp.
Thuật toán có các đặc điểm[1]: Đó là một dãy hữu hạn các bước sắp xếp theo một trình tự nhất định Mỗi bước là một thao tác sơ cấp, trường hợp đặc biệt cũng có thể là một thuật toán đã biết. Các bước rõ ràng, thao tác chính xác (trong cùng một điều kiện, hai bộ xử lí cùng thực hiện một thuật toán thì phải cho ra cùng một kết quả).
Có tính kết thúc Tư duy thuật toán là cách suy nghĩ để nhận thức, để giải
3
quyết vấn đề một cách có trình tự (sắp xếp lần lượt, thứ tự trước sau).[1]
Chương này trình bày những kiến thức cơ bản của số học và một số thuật toán số học thông dụng. Nội dung của chương này cơ bản được hình thành từ các tài liệu [2] và [3].
Mục này trình bày một số khái niệm cơ bản số học như tính chia hết, số
nguyên tố, đồng dư, thặng dư, ... cần thiết cho nội dung của luận văn.
Định nghĩa 2.1. Chúng ta ký hiêu: N: tập hợp của các số tự nhiên. Z+ = {0, 1, ...}: tập các số nguyên không âm. Z: tập các số nguyên. Q: tập các số hữu tỉ. R, R1: tập các số thực.
Định nghĩa 2.2. Với hai số nguyên a, b, a ̸= 0 ta nói a chia hết b đối với số nguyên c nào đó, nếu b = ac và ký hiệu a|b. Ta cũng nói b chia hết cho a, hay là bội của a và viết b ...a.
b = aq + r, r < a.
Định lý 2.1. Với mọi số nguyên dương a, b tồn tại duy nhất cặp số nguyên không âm (q, r) sao cho:
4
Định nghĩa 2.3. Trong định lý trên, khi a là số chia hết b thì số q được gọi là thương(quotient). Số r được gọi là số dư(remainder).
b = aq + r,
0 ≤ r < |a|.
Nhận xét 2.1. Thuật toán chia có thể mở rộng ra tập số nguyên Z như sau. Với mọi số nguyên a, b, a ̸= 0, tồn tại duy nhất cặp số nguyên (q, r) ∈ Z × Z, sao cho
Định nghĩa 2.4. Số nguyên tố là số nguyên lớn hơn 1, không chia hết cho số nguyên dương nào ngoài 1 và chính nó. Số nguyên lớn hơn 1 không phải số nguyên tố được gọi là hợp số.
Các tính chất của số nguyên tố:
√
n.
Định lý 2.2. (Euclid) i) 2 là số nguyên tố nhỏ nhất và là số chẵn duy nhất. ii) Số các số nguyên tố là vô hạn.
Định lý 2.3. Mọi hợp số n đều có ước nguyên tố không vượt quá
Với mỗi số thực dương x cho trước, ta kí hiệu π(x) là số các số nguyên tố
= 1
không vượt quá x. Khi đó, ta có:
π(x) x logx
√
√
n √
n là vào khoảng
Định lý 2.4. lim n→+∞
√ n logn .
n = 2
log
Như vậy, số các số nguyên tố không vượt quá
Định lý 2.5. Mọi số nguyên tố lớn hơn 1 đều phân tích được một cách duy nhất thành tích các thừa số nguyên tố, trong đó, các thừa số viết với thứ tự không giảm.
Trong phần này chúng ta hiểu các chữ ký hiệu thay số là các số nguyên.
Định nghĩa 2.5. Giả sử n là một số nguyên dương. Ta nói, hai số nguyên a, b là đồng dư với nhau theo modulo n nếu a − b chia hết cho n và ký hiệu a ≡ b(mod n).
Hệ thức trên gọi là đồng dư thức. Như vậy, a ≡ b(mod n) khi và chỉ khi tồn tại số nguyên k, sao cho: a = b + kn. Nếu a ̸≡ b(mod n) có nghĩa là a − b không chia hết cho n.
5
...n. Định nghĩa 2.6. Nếu a ≡ 0(mod n) thì ta nói a chia hết cho n và ký hiệu a Chúng ta cũng nói n là ước của a. Ước chung lớn nhất của hai số a, b được ký hiệu là gcd(a, b).
Định nghĩa 2.7. (Nguyên tố cùng nhau). Hai số nguyên a, b được gọi là nguyên tố cùng nhau nếu gcd(a, b) là 1.
Định nghĩa 2.8. (Phần tử nghịch đảo). Nếu hai số nguyên a và n nguyên tố cùng nhau, tồn tại số nguyên x sao cho: a.x ≡ 1(mod n) thì ta gọi x là phần tử nghịch đảo của a trong phép modulo cho n và ký hiệu là a−1.
Định nghĩa 2.9. Giả sử m và r là số tự nhiên và 0 ≤ r ≤ m − 1. Ký hiệu Ar là tập hợp tất cả các số nguyên đồng dư với r theo modulo m và được gọi là lớp thặng dư modulo m. Mỗi phần tử của Ar được gọi là một thặng dư modulo m.
0 ≤ c0 < b
0 ≤ c1 < c0
0 ≤ cn−1 < cn−2,
1
.
b có thể viết: = · · · = a0 +
a1+
b c0
1 ···+an−1+ 1 an
cn−3 = cn−2an−1 + cn−1, cn−2 = cn−1an. Như vậy, phân số a b = a0 + c0 b = a0 + 1 a Cách viết trên được gọi là biểu diễn số hữu tỷ a
b dưới dạng phân số liên tục.
Định nghĩa 2.10. Cho a, b là các số nguyên, b > 0. Thực hiện thuật toán Euclid ta được: a = ba0, b = c0a1 + c1, · · ·
Chúng ta quan tâm đến các định lý sau(phần chứng minh xem [1])
Định lý 2.6. Giả sử a0, a1, · · · , an, · · · là các số thực, trong đó a1, · · · , an > 0.
b1 = a1b0 + 1,
q0 = 1,
q1 = a1, và với mỗi k ≥ 2,
qk = akqk−1 + qk−2.
.
√
Đặt b0 = a0,
n. Ta đặt α0 =
√
n
,
αk =
Pk + Qk
ak = [αk],
Pk+1 = akQk − Pk, k+1)
.
Qk =
(n − P 2 Qk
6
là các phân số hội tụ n, và các số αk, Qk, Pk được định nghĩa như sau:
− nq2
k = (−1)k+1Qk+1.
√
Khi đó, ta có: b2 k
√
n.
là các phân k mod n lấy theo thặng dư tuyệt đối
Hệ quả 2.1. Giả sử n là số tự nhiên không chính phương. Gọi bk qk n. Thế thì, đồng dư b2 số hội tụ riêng của bé nhất, có giá trị tuyệt đối bé hơn 2
Định lý 2.8. Với mọi số nguyên a ≥ 0; b > 0 thì gcd(a, b) = gcd(b, a mod b).
Thuật toán Euclid:a hoặc b bằng 0 trả về gcd(a,b)= 0. function gcd(a,b) begin
while b ̸= 0 do
r := a mod b; a := b; b := r;
begin
end; Result:=a
end;
Năm 1967 J.Stein xây dựng một thuật toán khá thuận tiện để tìm UCLN trong trường hợp các số đã cho viết dưới dạng nhị phân. Thuật toán trên dựa trên những nhận xét đơn giản sau:
1. gcd(a, 0)=a trong trường hợp đặc biệt thì gcd(0, 0) = 0
;
2 , b a 2
) ( 2. Nếu a, b là các số chẵn thì (a, b) = 2
;
a 2 , b
( ) 3. Nếu a chẵn, b lẻ, thì (a, b) =
√
N .
4. Nếu a, b đều lẻ thì a − b chẵn và | a − b |< max (a, b) . (a, b) = (a − b, b)
Định lý 2.9. Nếu N có các ước không tầm thường s, t với N = s.t và s ≤ t, thì s ≤
7
Thuật toán Euclid mở rộng hơn thuật toán Euclid ở điểm trong trường hợp a và b nguyên tố cùng nhau gcd(a, b) = 1 với b ≥ a > 0 thì thuật toán cho biết thêm a−1 của a trong phép chia modulo b tức là: a.a−1 ≡ 1(mod b)
Định nghĩa 2.11. Nếu số nguyên dương a và số nguyên b nguyên tố cùng nhau thì tồn tại duy nhất một số x ∈ {0, 1, 2, · · · , b − 1} sao cho ax ≡ 1(mod b). Số x này được gọi là nghịch đảo của a theo modulo b (hoặc ngược lại, nói a là nghịch đảo của x (mod b).
a−1 ≡ x(mod b)
Ký hiệu
x−1 ≡ a(mod b).
hoặc
(ax − 1)
Tìm nghịch đảo của a theo modulo b. Ta có:
... b ⇔ ax − 1 = by ⇔ ax − by = 1.
Vậy, nghịch đảo của a theo modulo b tồn tại khi và chỉ khi gcd(a, b) = 1.
Việc xác định các số nguyên x và y với ax + by = gcd(a, b) được biết đến như
là thuật toán Euclid mở rộng. Ta có:
gcd(x, 0) = x.
gcd(x, z) = gcd(z, x mod z) nếu z ̸= 0.
Nếu x ≥ z và phần dư không âm nhỏ nhất được thay thế, cặp ’mới’ (z, x
mod z) là nhỏ hơn so với cặp cũ (x, z).
(u, v) = u3 = uu1 + uu2.
Cho hai số nguyên không âm u,v tìm (u1; u2; u3) sao cho:
Trong tính toán, ta thêm các ẩn phụ (v1; v2; v3), (t1; t2; t3) và luôn có trong
ut1 + vt2 = t3, uv1 + vv2 = v3; uu1 + vv2 = v3
mọi bước các đẳng thức sau:
u3 v3
[ ] , và sau đó ta đặt
8
Đặt (u1; u2; u3) ← (1, 0, u), (v1; v2; v3) ← (0, 1, v) Kiểm tra v3 = 0 thuật toán kết thúc. Đặt:q ← (t1; t2; t3) ← (u1; u2; u3) − q (v1; v2; v3) , (u1; u2; u3) ← (v1; v2; v3) , (v1; v2; v3) ← (t1; t2; t3) và quay về bước 2. Giả sử rằng, 0 ≤ x < z chúng ta có: r1 = 0, s1 = z, r2 = 1, và s2 = x.
x mod z)
Dòng thứ (i + 1) theo sau từ thứ (i − 1) và i bằng cách khấu trừ lần thứ i càng nhiều càng tốt từ lần thứ (i − 1), mà không làm cho phía tay phải của kết quả của dòng thứ (i + 1) là âm. Quá trình chấm dứt ngay khi một số si = 0; nếu sk = 0 sau đó sk−1 = gcd(x, z) và nếu sk−1 = 1, thì (rk−1 ≡ 1
Thuật toán Euclid mở rộng: Cho a, b không đồng thời bằng 0, trả về cặp (x,y): a.x + b.y = gcd(a, b). Về tư tưởng là quá trình tính cặp số (x, y) vào trong vòng lặp chính của thuật toán Euclid function Extended gcd(a, b);
(xa, ya) := (1, 0);
(xb, yb) := (0, 1);
while
b ̸= 0
do
Begin
q :=
]
r := a mod b; a := b; b := r
(xr, yr) := (xa, ya) − q.(xb, yb)
(xa, ya) := (xb, yb);
(xb, yb) := (xr, yr);
Begin [ a b
end result := (xa, ya) end
Định lý 2.10. Nếu p là một số nguyên tố, thì với số nguyên a bất kỳ, không chia hết cho p thì ap−1 − 1 sẽ chia hết cho p hay ap−1 ≡ 1 mod p.
2
Định nghĩa 2.12. Số Carmichael: Hợp số n là số Carmichael nếu nó là số giả nguyên tố Fermat với mọi cơ sở a: ƯCLN (a, n) = 1.
7 trong số chúng ≤ x, một khi x đủ lớn. Điều này làm mất hiệu lực của phép thử dựa trên định lý nhỏ Fermat: Cho một số Carmichael p thử nghệm ap−1 ≡ 1 mod p không bao giờ thất bại, nếu p và a nguyên tố cùng nhau, và do đó không bao giờ chứng minh được p là hợp số. Nhưng nhờ giải thuật kiểm tra Miler-Kabin-thuật toán xác suất để kiểm tra tính nguyên tố.
9
• Gần đây đã chứng minh được có vô số số Carmichael. Có ít nhất x
Kiểm tra Miler-Rabin:
x ≡ 1( mod p)
Bổ đề 2.1. Với p là số nguyên tố, x là số nguyên: x2 ≡ 1( mod p) khi và chỉ khi
x ≡ (p − 1)( mod p).
hoặc
x ≡ 1( mod p) hoặc x ≡ (p − 1)( mod p).
p là số nguyên tố viết lại p dưới dạng p = 2k.q + 1 trong đó q là số lẻ, a là
Bổ đề 2.2. Với p là số nguyên tố, x là số nguyên: x2 ≡ 1( mod p) khi và chỉ khi
số nguyên dương bé hơn p. Ta có:
• Hoặc aq ≡ 1( mod p).
(p − 1) mod p.
• Hoặc trong dãy số aq; a2q; a4q; · · · ; a2k−1q tồn tại một số mà đồng dư với
Thuật toán Miller-Rabin kiểm tra tính nguyên tố của số nguyên p.
Định nghĩa 2.13. Giả sử n là số nguyên dương lẻ n − 1 = 2s.t trong đó s là số nguyên không âm, t là số nguyên dương lẻ. Ta nói n được kiểm tra Miller cơ sở b, nếu hoặc bt ≡ 1 mod n hoặc b2j .t ≡ −1 mod n với j nào đó, 0 ≤ j ≤ s − 1.
2, t ← t + 1 (bây giờ ta có)
N − 1 = 2t.q, q lẻ. Sau đó, đặt c ← 20.
INPUT Số tự nhiên lẻ N. OUTPUT N là số nguyên tố: TRUE/FALSE. MR1.(Xuất phát): Phân tích Đặt q ← N − 1, t ← 0 và nếu q chẵn ta đặt q ← q
MR2.(Chọn a mới): Chọn ngẫu nhiên số tự nhiên a trong khoảng 1 < a < N.
Đặt e ← 0, b ← aq mod N. Nếu b = 1, chuyển sang MR4.
MR3.(Bình phương): Nếu b ̸≡ ±1( mod N ) và e < t − 2 ta đặt b := b2 mod N , e ← e + 1. Nếu b ̸= N − 1,in ra thông báo ”n là hợp số” và kết thúc thuật toán.
MR4. Đặt c ← c − 1. Nếu c > 0, chuyển sang MR2.Nếu c = 0 in ra thông
báo ”N là số nguyên tố”. Trả lời FALSE. Kết thúc.
10
Đối với số lẻ n có thể chứng minh rằng một số nguyên ngẫu nhiên được chọn một ∈ (2, 3, ..., n − 1) có cơ hội ít nhất 75% không thỏa mãn các điều kiện này và do đó là một chứng minh cho tính hợp nhất của n xem [38,49]); xem thêm [3]. Điều này chứng tỏ n là hợp số.
cơ sở
Định lý 2.11. Nếu p là một hợp số dương lẻ thì tồn tại không quá p−1 4 b, 1 ≤ b ≤ p − 1 sao cho p trải qua được kiểm tra Miler đối với các cơ sở đó.
(xem [1])
√
N.
Theo định lý 2.4 ở chương I để tìm một ước số nguyên tố của một hợp số
N ta phải chia N cho các số nguyên tố không vượt quá
• Ưu điểm: sàng của Erathostenes cho ta thuật toán xác định mọi số nguyên
tố không vượt quá một số cho trước.
Đối với hầu hết các con số, nó rất hiệu quả vì hầu hết các con số đều có các ước nguyên tố nhỏ: 88% số nguyên dương có một ước nguyên tố < 100, và gần 92% có ước nguyên tố < 1000.
x lnx
√
limx→∞( π(x)
√
n √
= 2 ln
n
√
n
tố): quá x. Như vậy, số các số nguyên tố không vượt quá
• Nhược điểm: độ phức tạp quá lớn. Bởi vì, theo định lý (số nguyên ) = 1. trong đó π(x) là các số nguyên tố không vượt n là vào khoảng √ n n . Chúng ta cần O(log2 n. log2 m) phép tính bit để chia n cho √ ln m. Như vậy, số các phép tính bit cần thiết để phân tích số n vào khoảng √ 2 ln n .C. log2 n = C n. Nếu n vào cỡ khoảng 100 chữ số thập phân, thì số các phép tính phải dùng cỡ 1050. Với những máy tính thực hiện cỡ một triệu phép tính một giây, thời gian cần thiết sẽ vào khoảng 3, 1.1036 năm.(xem [1]) Vì vậy, chúng ta ít dùng để xác định xem một số có phải số nguyên tố hay không?
11
Pollard sử dụng một hàm giả ngẫu nhiên để sinh dãy x1; x2; · · · ; xk. Hàm đơn giản nhất thỏa mãn chính là: f (x) = x2 + 1 mod N (1). Như vậy, chúng ta chỉ sinh ra một số x1 hoàn toàn ngẫu nhiên và các phần tử còn lại sẽ được sinh dựa trên hàm f (x). Dãy số ngẫu nhiên ta thu được cuối cùng là: x1; x2 = f (x1); x3 = f (x2); · · · ; xk = f (xk−1)(2). Do dãy x2; x3; · · · ; xk được sinh bởi hàm f(x), nếu tồn tại xi ≡ xj mod p thì ta dễ dàng suy ra: xi+1 ≡ xj+1 mod p, xi+2 ≡ xj+2 mod p, · · · (3).
Nói cách khác, ta sẽ có một vòng trong các dãy số bởi f (x) khi lấy mod p (giống như hình vẽ vòng liên kết ở trên). Những ý tưởng này có thể được kết hợp thành một thuật toán theo cách sau:
• Chọn f (x) = x2 + 1
ρ
Figure 2.1: rho
• Chọn một giá trị x0 nào đó và tính theo phép lặp bởi ánh xạ f dãy sau: x1 = f (x0), x2 = f (x1), · · · , x(j + 1) = f (xj), j = 0; 1; 2; · · · Sau đó, xét hiệu giữa các xj với hi vọng tìm thấy xj, xk nào đó sao cho: xj /∈ xk( mod n) nhưng xj ≡ xk( mod n), trong đó d là một ước không tầm thường nào đó của n. Khi đó, bằng cách tính (xj − xk, n) ta thu được một ước thực sự của n.
Thuật toán: INPUTS: n là số nguyên cần phân tích. f(x) là hàm tạo số giả ngẫu nhiên. OUTPUT: Ước thực sự(̸= 1; ̸= n) của n hoặc không thực hiện được 1)x ← 2; y ← 2; d ← 1 2)While d = 1
• x ← f (x)
• y ← f (f (x))
• d ← gcd(| x − y |, n)
12
3) Nếu d = n, return (không thực hiện). 4)Else, return d.
Thành công đáng chú ý nhất của phương pháp rho của Pollard cho tới nay là khám phá vào năm 1980 bởi Brent và Pollard về việc phân tích nhân tố số Fermat thứ tám (xem [2]): 228 + 1 = 1238926361552897.p62 trong đó p62 biểu thị số nguyên tố 62 chữ số.
Pollard’s p − 1 method Giả sử cần phân tích số nguyên n và p là một ước nguyên tố của n. Nếu p − 1 không có các ước nguyên tố lớn thì thuật toán p − 1 của Pollard là rất hiệu quả.
Thuật toán 1) Chọn một số k sao cho nó chia hết cho hầu hết các số nguyên nhỏ hơn một số B nào đó. Chẳng hạn k là B! hoặc k là bội chung nhỏ nhất của tất cả các số từ 1 đến B.
2) Chọn ngẫu nhiên một số nguyên a trong khoảng từ 2 đến n − 2. 3) Tính ak( mod n) (bằng thuật toán bình phương liên tiếp). 4) Tính (ak − 1, n) (Bằng thuật toán Euclid.) 5) Nếu d = (ak − 1, n) không phải là một ước thực sự của n, ta lặp lại quá
trình trên với một số a khác, hoặc k khác(hoặc cả a và k khác).
Nhược điểm của phương pháp (p − 1) của Pollard là nó làm việc có hiệu quả nếu thừa số của nó có yếu tố p : p − 1 là B-mịn nên phương pháp này chỉ hiệu quả khi có chút may mắn.
Thuật toán đường cong elliptic mạnh hơn được Lesntra xây dựng vào những
năm 1980 trên thực tế là sự tổng quát hóa của phương pháp p − 1 Pollard.
Phương pháp đường cong eliptic khắc phục hoàn toàn được nhược điểm trên. Trong bất kỳ thử nghiệm nào trong đó mỗi lần thử nghiệm bất kỳ không cần yếu tố may mắn. Một thử nghiệm thành công nếu một số ngẫu nhiên gần với một số nguyên tố của n là B− mịn.
1
2 .
Đường cong elliptic được Lenstra đề xuất, và độ phức tạp của phương pháp
này là e((2+o(1)) log p log log p)
Phép cộng: Để xác định điểm R(xR; yR) = P (xP ; yP ) + Q(xQ; yQ) ta tính xR và yR như
λ =
sau:
yQ − yP xQ − xP
xR = (λ2 − xP − xQ) mod n yR = (λ(xP − xQ) − yP ) mod n
13
mod n
-Điểm tại vô cùng O là điểm cộng với bất kỳ điểm nào cũng sẽ ra chính
điểm đó. Nghĩa là :∀P ∈ E, P + O = O + P = P
∈ ZP sao cho (y′
-Điểm đối xứng của P (xP ; yP ) ∈ E là −P (xP ; yP ) ∈ E thỏa mãn các điều
P + yP ) mod n;P + (−P ) = 0
kiện: y′ P
Phép nhân đôi: -Để xác định điểm R(xR; yR) = 2P (xP ; yP ) với yP ̸= 0, ta
3x2
λ =
tính xR và yR như sau:
P + a 2yP
xR = (λ2 − 2xP ) mod p. yR = (λ(xP − xR) − yP ) mod p.
mod p.
Mở rộng ra,phép nhân kP nhận được bằng cách thực hiện k lần phép cộng. Thuật toán nhân đôi và thêm cho ta cách làm như sau:
• Lấy P
• Tăng gấp đôi để được 2P
• Thêm P vào 2P để được 21P + 20P
• Nhân đôi 2P để được 22P
• Thêm vào để được 22P + 21P + 20P
• Gấp đôi 22P để được 23P
• Gấp đôi 23P để được 24P
• Thêm nó vào kết quả trước để được 24P + 23P + 22P + 21P + 20P
• …
• Cuối cùng chúng ta tính toán 151P thực hiện chỉ bảy lần nhân đôi và bốn
phép cộng bổ sung
Thuật toán nhân tử hóa với một đường cong elliptic Cho k là hợp số sao cho k = k1.k2 khi đó ta có thể tính kP = k1(k2P ).
n)
Đầu vào của thuật toán là số tự nhiên n và các tham số v; w ∈ N, phụ thuộc vào n. Cũng như a; x; y ∈ Zn, sao cho P (x; y; 1) ∈ Vn từ y2 = x3 + ax + b ⇔ b ≡ y2 − x3 − ax( mod n) thỏa mãn điều kiện (4a3 + 27b2 ∈ Z.
Thuật toán tìm kiếm ước số tự nhiên d của số n: 1 < d < n. Đối với từng
√
v + 1}, và sau đó:
e(r) = max {m |∈ Z≥0, rm ≤ v + 2
14
số r ∈ N,
re(r)(r là số nguyên tố; e(r) là một số nguyên dương)2 ≤ r ≤ w chúng
k = ta giả sử:
∏
Giả sử P (x : y : 1) ∈ Vn.Khi đó,P nằm trên đường cong Eliptic Ea;b ttrong vành Zn, được xác định bởi phương trình y2 = x3 + ax + b. Chúng ta tính điểm kP,nếu trong quá trình tính toán tìm được ước của số n,1 < d < n, thì chúng ta phân tích được n ra thừa số và thuật toán dừng.Nếu như tìm được kP và không tìm được d thì thuật toán dừng và thông báo và thuật toán phân tích thành nhân tử không thành công.Thuật toán kết thúc.
Định lý 2.12. Giả sử E là đường cong elliptic cho bởi phương trình y2 = x3 + ax + b, trong đó a, b ∈ Z và (4a3 + 27b2, n) = 1. Giả sử P1 và P2 là hai điểm trên E có mẫu số của các tọa độ nguyên tố cùng nhau với n, đồng thời P1 ̸= −P2. Khi đó điểm P1 + P2 có tọa độ với mẫu số nguyên tố cùng nhau với n nếu và chỉ nếu không tồn tại ước nguyên tố nào của n, p | n với tính chất sau đây. Các điểm P1 mod P và P2 mod P trên E mod p có tổng là điểm O mod p ∈ E mod p. (E mod p là đường cong trên trường Fp nhận được bằng cách lấy đồng dư rút gọn modulo p các hệ số của phương trình y2 = x3 + ax + b.)
Thuật toán nhân tử hóa với một đường cong elliptic. Cho k là hợp
số sao cho k = k1.k2 khi đó ta có thể tính kP = k1(k2P ).
n)
Đầu vào của thuật toán là số tự nhiên n và các tham số v; w ∈ N, phụ thuộc vào n. Cũng như a; x; y ∈ Zn, sao cho P (x; y; 1) ∈ Vn từ y2 = x3 + ax + b ⇔ b ≡ y2 − x3 − ax( mod n) thỏa mãn điều kiện (4a3 + 27b2 ∈ Z.
Thuật toán tìm kiếm ước số tự nhiên d của số n : 1 < d < n. Đối với từng
√
v + 1}, và sau đó:
số r ∈ N,
e(r) = max {m |∈ Z≥0, rm ≤ v + 2 re(r)(r là số nguyên tố; e(r) là một số nguyên dương)2 ≤ r ≤ w k = Giả sử P (x : y : 1) ∈ Vn. Khi đó, P nằm trên đường cong elliptic Ea;b trong vành Zn, được xác định bởi phương trình y2 = x3 + ax + b. Chúng ta tính điểm kP , nếu trong quá trình tính toán tìm được ước của số n, 1 < d < n, thì chúng ta phân tích được n ra thừa số và thuật toán dừng. Nếu như tìm được kP và không tìm được d thì thuật toán dừng và thông báo và thuật toán phân tích thành nhân tử không thành công.
∏
Thuật toán kết thúc.
15
Tính gcd(n; xy) tính ước số chung lớn nhất của n và xy. Nếu n là hợp số, không phải là số nguyên tố, và x, y là các số nguyên ngẫu nhiên thỏa mãn
x2 ≡ y2 thì có ít nhất 50% cơ hội cho gcd(x − y; n) và gcd(x + y; n) các thừa số không nhỏ của n.
√
Thuật toán Phân tích hợp số n 1) Chọn số nguyên x > n. 2) Kiểm tra xem x2 − n có là số chính phương không?
• Nếu x2 − n không là số chính phương, thì ta quay lại bước 1 và tăng giá
trị của x.
• Nếu x2 − n là số chính phương y2, thì ta chuyển sang bước sau.
3) n = x2 − y2 = (x − y)(x − y).
Squfof là từ viết tắt của”square form factorization” phân tích các dạng
chính phương.
Ta xuất phát từ nhận xét sau đây: Nếu ta tìm được các số x, y sao cho:x − y ̸= 1 và x2 − y2 = n thì ta tìm được ước số không tầm thường của n vì n = x2 − y2 = (x + y)(x − y). Bây giờ, ta có kết quả yếu hơn:
Giả sử có x, y : x2 ≡ y2( mod n) và 0 < x < y < n, x + y ̸= n khi đó n là một ước của tích (x + y)(x − y) và rõ ràng n không là ước của x + y cũng như x − y và do đó d1 = gcd(x − y, n) và d2 = gcd(x + y, n) là các ước số không tầm thường của n. Các ước số này được tìm nhanh chóng thông qua thuật toán Euclid. Từ định lý 2.9 cho ta phương pháp tìm x, y cần thiết.
≡ (−1)k+1Qk+1( mod n) như vậy, ta phải tìm được các Qk+1 với chỉ ...n. số chẵn và là số chính phương y2 thì x2 ≡ y2( mod n). Khi đó, (xk +y)(xk −y) Như vậy, các ước số chung lớn nhất d1 = (xk + y, n) và d2 = (xk − y, n) , có nhiều khả năng là các ước không tầm thường của n, vì các số xk + y, xk − y, không nhất thiết bé hơn n.
Ta có p2 k
Thuật toán: INPUTS: Số nguyên n cần kiểm tra. Bước 1: Chúng ta cần tìm các số m1, · · · , mk+1 bằng cách lựa chọn ngẫu
1
...pαi,k k
≡ Q(mi)( mod n).
1 < mi < n Q(mi) = pαi,1 m2 i
16
nhiên sao cho:
−→ v = (αi,1, · · · , αi,k) ∈ Zk. Bước 2: Giải hệ phương trình tuyến tính:
−→ 0 ( mod 2).
x1
−→ v1 + ... + xk+1
−−→ vk+1 ≡
Các giá trị của pi là chẵn lần, và với i = 1, ..., k + 1. Kí hiệu:
2 , chúng ta tìm được tập
x1, ..., xk+1 ∈ {0, 1},
Trong không gian vecto Zk
tập này không bao gồm các giá trị 0(bởi vì số lượng phương trình k nhỏ hơn số ẩn).
∑
∑
k+1 i=1 xiαi,1
k+1 i=1 xiαi,k
(mx1
( mod n).
1 ...mxk+1
1
k+1 )2 ≡ p
...p k
Bước 3: Để tìm được x1, ..., xk+1,ta có biểu thức sau:
∑
k∏
k+1 i=1 xiαi,j)/2
xk+1), Y =
p
X = (m1
x1...mk+1
( j
j=1
Ký hiệu
k+1∑
((
xiαi,j)/2)
i=1
số
là số nguyên xác định theo xi. Chúng ta nhận được biểu thức tương ứng X 2 ≡ Y 2( mod n). Tiếp tục ta kiểm tra điều kiện : 1 < gcd(X ± Y, n) < n. Nếu thành công ta đã phân tích n thành thừa số. Trong trường hợp không thành công thì chúng ta quay lại bước 1 và tính các giá trị khác của mi
Kết thúc thuật toán. Giả sử chúng ta có một tập B = p1, ..., pB ở nhân tử và tập V các mối quan
...pαBj
.pα2j 2
≡ pα1j 1
hệ trong bước thu thập dữ liệu.
Xử lý dữ liệu: Giả sử C lớn hơn B và giả sử C có đồng dư thức: B ( mod n) với 1 ≤ j ≤ C. Với mỗi j vecto: x2 j −→ aj = (α1j mod 2, α2j mod 2, ..., αBj mod 2) ∈ (Z2)B. Nếu có thể tìm được −→ aj sao cho tổng các modulo 2 là vecto (0, 0, ..., 0) thì tích của
một tập con các các xj tương ứng sẽ sử dụng mỗi nhân tử trong B một số chẵn lần.
1 Độ phức tạp của thuật toán là: Ln 2; 1 Chúng ta mô tả sơ đồ thuật toán ban đầu của sàng bậc hai. Đầu tiên, chúng ta xây dựng biểu thức X 2 ≡ Y 2( mod n) và kiểm tra bất đẳng thức:
17
[ ] lệnh số học.
√
√
n⌋)2 − n ≡ H(x)2( mod n). Ở đây, H(x) = x + ⌊
1 < gcd(X ± Y, n) < n để làm được điều này chúng ta xem xét đa thức: Q(x) = n⌋. Dễ nhận thấy các (x + ⌊ giá trị của Q(x) là các giá trị nguyên, rõ ràng chúng là số chính phương theo modulo n. Trong cơ sở nhân tử chúng ta có thể xem p0 = −1 và tất cả các số nguyên tố pi, p1 ≤ B sao cho: n = 1. Sau đó, với sự giúp đỡ của sàng, chúng pi p∈S pαip nghĩa là Q(xi) phân tích trong cơ ta tìm giá trị xi mà: Ai = Q(xi) = sở nhân tử của chúng ta. Ta kí hiệu: Bi = H(xi) ta nhận được đồng dư thức ≡ Ai(modn) ta tích lũy số lượng đủ lớn các biểu thức như thế chúng ta thực B2 i hiện loại bỏ các biến và xây dựng biểu thức X 2 ≡ Y 2( mod n)
∏
√
p = 1 với p là số nguyên tố của cơ sở nhân tử lấy từ đồng dư n⌋)2 ≡ n( mod p), mà đồng dư cần thỏa mãn đối với một số giá
Điều kiện n
1p)
thức (x + ⌊ trị của x ∈ Z.
và r(
Giá trị xi ∈ Z đối với Q(xi) được xác định như sau: 1) Đối với từng số nguyên tố p từ cơ sở nhân tử, chúng ta tìm nghiệm r( 2p) của phương trình Q(x) ≡ 0( mod p). 2) Sau đó, chúng ta thay đổi x trong khoảng đủ lớn [−M ; M ],M ∈ N, chúng
ta đưa đến một ma trận A, mà nó được đánh số thứ tự bằng giá trị của x.
x ≡ rp
1( mod p)
3) Trong mỗi phần tử của ma trận với số thứ tự của x ta đặt A log | Q(x) | . 4) Sau đó, đối với từng giá trị p từ cơ sở nhân tử S chúng ta thực hiện quá trình sàng như sau: Từ mỗi phân tử cuả ma trận (A [x]), số thứ tự của nó nằm trong cấp số cộng
x ≡ rp
2( mod p),
và
; 1
.
Ln
1 2
18
chúng ta tính toán giá trị của log p. Thời gian chạy của thuật toán là ] [
Nội dung chủ yếu của chương này được hình thành từ tài liệu [4].
Thuật toán RSA được lấy từ ba chữ cái đầu của tên ba tác giả thuật toán là: Ron Rivest, Adi Shamir và Len Adleman mô tả lần đầu tiên vào năm 1977 tại Học viện Công nghệ Massachusetts (MIT) và được MIT đăng ký bằng sáng chế tại Hoa Kỳ vào năm 1983(số đăng ký 4405829.)
Ý tưởng chính đảm bảo tính an toàn của thuật toán dựa trên độ khó của việc phân tích số nguyên lớn thành tích các thừa số nguyên tố.Thuật toán RSA có bốn bước chính là:tạo khóa, chia sẻ key, mã hóa và giải mã,có hai khóa:
• Khóa công khai( Public Key)
• Khóa bí mật ( Private Key)
Các bước tạo khóa:
1. Chọn 2 số nguyên tố lớn p và q ,với p ̸= q,lựa chọn ngẫu nhiên và độc lập.
2. Tính n = p.q.
3. Tính : Giá trị hàm số Ơle ϕ(n) = (p − 1)(q − 1).
4. Chọn một số tự nhiên e sao cho:1 < e < ϕ(n), và là nguyên tố cùng nhau
19
với ϕ(n).
d.e ≡ 1( mod ϕ(n)).
5. Tính : d sao cho
d =
x.ϕ(n) + 1 e
hay
Khóa công khai:(e,n). Khóa bí mật:(d,n). Các số nguyên tố được chọn theo phương pháp thử xác suất. Bước bốn ,năm được thực hiện bằng thuật giải Euclide mở rộng. Mã hóa và giải mã: Bản rõ (thông tin trước khi mã hóa )ký hiệu m Bản mã (thông tin sau khi mã hóa )ký hiệu là c Khóa bí mật d thường là một số rất lớn được giữ bí mật Bước 1: A nhận
khóa công khai của B
Bước 2: A chuyển bản rõ M thành số tự nhiên m sao cho m và n nguyên
tố cùng nhau và 0 < m < n.
c ≡ me mod n
Bước 3: Mã hóa m thành c
và c là bản mã chuyển cho người nhận.
Bước 4: Gửi c cho B Bước 5: Giải mã: Người nhận sẽ chuyển bản mã từ c được m ta làm như
sau:cd ≡ med ≡ m mod n m là thông tin nhận được.
Độ an toàn của thuật toán RSA phụ thuộc vào hai bài toán: bài toán phân tích một số ra tích các thừa số nguyên tố và bài toán RSA. Hiện nay, chưa tìm được một phương pháp nào trên máy tính giải quyết được bài toán này trong thời gian đa thức.
20
Một sơ đồ chữ ký số có hai phần: Thuật toán ký và thuật toán xác minh. Giao thức chữ ký số đơn giản. Bob tạo ra một cặp khóa một khóa công khai kpr và kpub Nhập thông điệp (sign message: s = sigkpr(x)) Gửi thông điệp và chữ ký số (x,s) cho Alice Alice xác minh chữ ký số verify signature: verkpr,B(x, s)=true/false
Chúng ta sẽ nghiên cứu tại sao hàm băm được yêu cầu trong các lược đồ
chữ ký số?
Định nghĩa 3.1. Hàm băm mật mã là hàm nhận vào chuỗi ký tự có độ dài bất kỳ(Message) kết xuất ra một chuỗi có độ dài xác định(digest) gọi là giá trị băm và kết quả tạo ra có dung lượng nhỏ hơn chuỗi đầu vào. Hàm băm có các thuộc tính:
- Dễ dàng tìm được digest của một chuỗi bất kỳ - Không thể tìm được thông điệp gốc của digest - Không thể điều chỉnh được thông điệp mà không làm thay đổi digest của
nó
- Không thể tìm được hai thông điệp khác nhau có cùng digest.
MD5 Là một phiên bản tăng cường của M D4, được đề xuất bởi giáo sư Rivest vào năm 1991. Cả hai hàm băm tính toán đầu ra 128 bit, tức là chúng có sức đề kháng va chạm khoảng 264. M D5 là một loạt các giải thuật đồng hóa thông tin với các thuật toán được thiết kế tùy chỉnh.
Ứng dụng: -Trong chữ ký điện tử. -Dùng trong các ứng dụng bảo mật. -Kiểm tra tính toàn vẹn của tập tin được truyền đi. -lưu trữ mật khẩu. Đặc điểm : -Từ một đoạn văn bản đầu vào sẽ tạo ra một chuỗi gọi là Message Digest hay còn gọi là MD5 hasd có độ dài cố định cho trước được mã hóa dưới dạng hexa.
-Từ một đoạn văn bản đầu vào sẽ tạo ra duy nhất một hash cho một văn
bản.
-Từ một hash đầu ta sẽ không bao giờ suy ngược được plantext (bản rõ)
ban đầu.
l = n.512 + 448 (với l, n nguyên).
21
Giải thuật: Gồm 5 bước: Input: chuỗi có độ dài bất kỳ. Output: Giá trị băm có độ dài 128 bits. Bước 1: Nhồi dữ liệu: -Nhồi thêm các bits sao cho dữ liệu có độ dài là l ≡ 448 mod 512 hay
Figure 3.1: Mô phỏng bước 1 MD5
-Các bits được nhồi gồm 1 bits 1 và các bits 0 theo sau. Bước 2:Thêm vào độ dài: -Độ dài của khối dữ liệu ban đầu được biểu diễn dưới dạng nhị phân 64 bits
và được thêm vào cuối chuỗi nhị phân kết quả của bước 1.
-Nếu độ dài của khối dữ liệu ban đầu > 264, chỉ 64 bits thấp được sử dụng,
nghĩa là giá trị được thêm vào bằng K mod 264
-Kết quả có được từ hai bước đầu là một khối dữ liệu có độ dài là bội số
Y0, Y1, · · · , YL−1.
của 512. Khối dữ liệu được biểu diễn: Bằng một dãy L khối 512 bits
M0, M1, · · · , MN −1.
Bằng một dãy N từ 32 bits
N = L.16(32.16 = 512).
Vậy,
A = 67
45
23
01
B = EF CD AB 89
C = 98 BA DC F E
D = 10
32
54
76
22
Bước 3: Khởi tạo bộ đệm MD (MD buffer) Một bộ đệm 128 bit được dùng để lưu trữ các giá trị băm trung gian và kết quả. Bộ đệm được biểu diễn bằng bốn thanh ghi 32 bit với các giá trị khởi tạo dạng litte-endian (byte có trọng số nhỏ nhất trong từ nằm ở địa chỉ thấp nhất) như sau:
A = 01
23
45
67
B = 89 AB CD EF
C = F E DC BA 98
D = 76
54
32
10
Các giá trị này tương đương với 32 bit sau:
F (X, Y, Z) = (X ∧ Y ) ∨ (¬X ∧ Z)
G(X, Y, Z) = (X ∧ Z) ∨ (Y ∧ ¬Z)
G(X, Y, Z) = (X ∧ Z) ∨ (Y ∧ ¬Z)
H(X, Y, Z) = X ⊕ Y ⊕ Z
H(X, Y, Z) = X ⊕ Y ⊕ Z
I(X, Y, Z) = Y ⊕ (X ∨ ¬Z)
Bước 4:Xử lý các khối dữ liệu 512 bit Trọng tâm của giải thuật là hàm nén(compression function) gồm 4 vòng xử lý. Các vòng này có cấu trúc giống nhau nhưng sử dụng các hàm luận lý khác nhau gồm F, G, H và I như sau:
Quy ước : ⊕, ∧, ∨, ¬⊕, ∧, ∨, ¬ lần lượt chỉ phép XOR, AND, OR và NOT. X <<< s các bits được dịch chuyển xoay vòng sang trái s vị trí(0 < eqs < 32). Mảng 64 phần tử được tính theo công thức: T [i] = 232.abs(sin(i)), i được tính bằng radian. Kết quả của 4 vòng được cộng (theo mod 232 với đầu vào CVq để tạo CVq+1 Bước 5: Xuất kết quả:
128 bits.
Sau khi xử lý hết khối 512 bits đầu ra của lần xử lý thứ L là giá trị băm
CV0 = IV
CVq+1 = SU M32 [CVq, RFI (Yq, RFH (Yq, RFG(Yq, RFF (Yq, CVq))))]
M D = CVL−1
-Giải thuật M D5 được tóm tắt như sau:
23
Với các tham số : IV: bộ đệm gồm 4 thanh ghi ABCD. Yq: Khối dữ liệu thứ q gồm 512 bits. L: số khối 512-bit sau khi nhồi dữ liệu. CVq: Đầu ra của khối thứ q sau khi áp dụng hàm nén. RFX: Hàm luận lý sử dụng trong các ”vòng”(F, G, H, I).
Figure 3.2: Mô phỏng bước 4 MD5
Figure 3.3: Các giá trị trong bảng T MD5
MD: message digest-Giá trị băm. SU M32 cộng mod 232. -Mỗi vòng thực hiện 16 bước, mỗi bước thực hiện các phép toán để cập nhật giá trị buffer ABCD, mỗi bước được mô tả như sau: A ← B +((A+F (B, C, D)+ X [k] + T [i]) <<< s). -A, B, C, D: Các từ của thanh ghi.
-F: một trong các hàm F, G, H, I. -<<< s: Dịch vòng trái s bits -Mi ∼ X [k] từ bit thứ k của khối dữ liệu 512
bits.k = 1 · · · 15.
24
-Ki ∼ T [i] giá trị thứ i trong bảng T.
Figure 3.4: Sơ đồ hàm băm MD5
M D5 input:”huyen”= dbbf 9a0b815665d82400930a87c43472
-X + Y : phép cộng trong mod 232 Ví dụ nhỏ mô tả kết quả sau khi băm:
Lịch sử: SHA (Secure Hash Algorithm hay thuật giải băm an toàn) là năm thuật giải được chấp nhận bởi FIPS dùng để chuyển một đoạn dữ liệu nhất định thành một đoạn dữ liệu có chiều dài không đổi với xác suất khác biệt cao. Những thuật giải này được gọi là ”an toàn”theo nguyên văn của chuẩn FIPS 180 − 2 phát hành ngày 1 tháng 8 năm 2002
1) Cho một giá trị băm nhất định được tạo nên bởi một trong những thuật
giải SHA, việc tìm lại được đoạn dữ liệu gốc là không khả thi.
2) Việc tìm được hai đoạn dữ liệu khác nhau có cùng kết quả băm tạo ra bởi một trong những thuật giải SHA là không khả thi. Bất cứ thay đổi nào trên đoạn dữ liệu gốc, dù nhỏ, cũng sẽ tạo nên một giá trị băm hoàn toàn khác với xác suất rất cao.
Năm thuật giải SHA là SHA − 1 (trả lại kết quả dài 160 bit), SHA − 224 (trả lại kết quả dài 224 bit), SHA − 256 (trả lại kết quả dài 256 bit), SHA − 384 (trả lại kết quả dài 384 bit), và SHA − 512 (trả lại kết quả dài 512 bit).
25
Xử lý dữ liệu đầu vào: Giải thuật: Gồm 5 bước: Input: Chuỗi có độ dài tối đa 264 bits Output: Giá trị băm có độ dài 160 bits Giải thuật gồm 5 bước thao tác trên các khối 512 bits. Bước 1: Passding: Giả sử rằng chúng ta có một thông điệp x với chiều dài của bit l(l ≡ 448 mod 512 hay l = n.512 + 448 (l, n là các số nguyên). Để thu được kých thước thông báo là bội số của 512 bit. Thông điệp luôn luôn được nhồi thêm dữ liệu. Số bits nhồi thêm nằm trong khoảng 1 đến 512. Chúng tôi nối thêm một bit 1 , sau đó là các bit zero 0. Bước 2: -Độ dài của khối dữ liệu ban đầu được biểu diễn dưới dạng nhị phân 64 bit và được
thêm vào cuối chuỗi nhị phân kết quả của bước 1.
A = 01
23
45
67
B = 89 AB CD EF
C = F E DC BA 98
D = 76
54
32
10
E = C3 D2 E1 F 0
-Độ dài được biểu diễn dưới dạng chuỗi nhị phân không dấu. -Kết quả có được từ 2 bước đầu là một khối dữ liệu có độ dài là bội số của 512. Khối dữ liệu được biểu diễn: Bằng một dãy L khối 512 bit Y0, Y1, · · · , YL−1. Bằng một dãy N từ 32 bits M0, M1, · · · , MN −1.Vậy, N = L.16(32.16 = 512). Bước 3: Khởi tạo bộ đệm MD (MD buffer) Một bộ đệm 160 bit được dùng để lưu trữ các giá trị băm trung gian và kết quả. Bộ đệm được biểu diễn bằng năm thanh ghi 32 bit với các giá trị khởi tạo dạng big-endian (byte có trọng số nhỏ nhất trong từ nằm ở địa chỉ thấp nhất) như sau:
A = 01
23
45
67
B = 89 AB CD EF
C = F E DC BA 98
D = 76
54
32
10
E = C3 D2 E1 F 0
Các giá trị này tương đương với 32 bit sau:
Bước 4: Xử lý các khối dữ liệu 512 bit.
Trọng tâm của giải thuật bao gồm 4 lặp thực hiện tất cả 80 bước. 4 vòng lặp có cấu trúc như nhau, chỉ khác nhau ở các hàm logic f1, f2, f3, f4 Mỗi vòng có đầu vào gồm khối 512 bit hiện thời và một bộ đệm 160-bit ABCDE.
79
99
(0 ≤ t ≤ 19)
Kt = 5A 82
(20 ≤ t ≤ 39) Kt = 6E D9 EB A1 Kt = 8F 1B BC DC (30 ≤ t ≤ 59) (60 ≤ t ≤ 79).
Kt = CA 62 C1 D6
Mỗi bước sử dụngmột hằng số Kt (0 ≤ t ≤ 79.)
26
Đầu ra của 4 vòng( bước 80 được cộng với đầu của bước CVq để tạo ra CVq+1.
Figure 3.5: Sơ đồ sử lý khối đơn 512 bit
Bước 5: Xuất kết quả:
Sau khi thao tác trên toàn bộ L block. Kết quả của khối thứ L là bảng
băm 128 bits.
27
-Giải thuật SHA1 được tóm tắt như sau: CV0 = IV CVq+1 = SU M32(CVq, ABCDEq) M D = CVL Với IV = giá trị khởi tạo của bộ đệm gồm ABCDE. ABCDEq = đầu ra của hàm nén trên khối thứ q. L = số khối 512-bit của thông điệp. SU M32 = phép cộng mod 232 trên từng từ (32 bits) của đầu vào. M D = giá trị băm
Figure 3.6: Giải thuật SHA-1 Hàm nén
A ← E + f (t, B, C, D) + S(A) + Wt + Kt B ← A C ← S30(B) D ← C
E ← D
Giải thuật thực hiện tất cả 80 bước:
Trong đó A, B, C, D, E là các từ trong bộ đệm
28
t là số thứ tự của bước. F(t, B, C, D) là hàm logic tại bước t. Sk dịch vòng trái k bits. Wt từ thứ t của khối dữ liệu. Kt là hằng số. là phép cộng mod 232. Các hàm f: Từ 16 đến 32 bits từ khối dữ liệu đầu vào, mở rộng thành 80 từ Wt Với 0 ≤ t ≤ 15, giá trị Wt được lấy trực tiếp từ khối dữ liệu. Với t ≻ 15, Wt = S1(Wt−16xorWt−14xorWt−8xorWt−3) So sánh 2 phương thức mã hóa MD5 và SHA1.
Figure 3.7: Các hàm f
Figure 3.8: Demo SHA2
Khác nhau: - Thuật toán
• M D5 sử dụng mỗi hằng số duy nhất cho mỗi bước biến đổi, SHA sử dụng mỗi hằng số cho mỗi vòng biến đổi, hằng số dịch này là một số nguyên tố đối với độ lớn của từ (giống với M D4).
• Trong hàm phi tuyến thứ 2 của M D5 có sự cải tiến so với M D4, SHA thì sử dụng lại hàm phi tuyến của M D4, tức (X và Y) hoặc (X và Z) hoặc (Y và Z).
• Trong M D5 với mỗi bước được cộng kết quả của bước trước đó. Sự khác biệt đối với SHA là cột thứ 5 được cộng (không phải b, c hay d như trong M D5), điều này làm cho phương pháp tấn công của Boer-Bosselaers đối với SHA bị thất bại (Den Boer vaf Bosselaers là hai người đã phá thành công 2 vòng cuối trong M D4).
• Đầu vào: M D5 là chuỗi có độ dài bất kì còn SHA1 là chuỗi có độ dài tối
đa 264 bits.
- Hao tốn tài nguyên.
- Tốc độ
• Cả hai dựa trên phép toán 32 bit, thực hiện tốt trên các kiến trúc 32 bit.
• SHA1 thực hiện nhiều hơn 16 bước và thao tác trên thanh ghi 160 bit
29
nên tốc độ thực hiện chậm hơn.
- Độ an toàn (khả năng chống tấn công)
• Để tạo ra thông điệp có giá trị băm cho trước, cần 2128 thao tác với M D5
và 2160 với SHA1.
280 với SHA1.
30
• Để tìm 2 thông điệp có cùng giá trị băm, cần 264 thao tác với M D5 và
Luận văn ”Một số thuật toán trong số học và ứng dụng” đã trình bày một
số vấn đề sau:
1-Thuật toán, độ phức tạp của thuật toán, tư duy thuật toán và cách tư
duy về thuật toán áp dụng cho việc giảng dạy môn toán ở THPT.
2-Trình bày về một số kiến thức cơ bản về số học, một số thuật toán tìm ước chung lớn nhất, một số thuật toán phân tích số nguyên thành tích các thừa số nguyên tố.
31
3-Trình bày về hệ mã hóa RSA và chữ ký số.
[1] Hà Huy Khoái và Phạm Huy Điển (2003),Số học và thuật toán- Cơ sở lý
thuyết và tính toán thực hành, NXB Đại học quốc gia Hà Nội.
[2] https://www.fdi.ucm.es/profesor/m alonso/Documentos/factorizacion/arjlensfac.pdf
[3] https://infoscience.epfl.ch/record/164502/file/nscan18.pdf
32
[4] Christof Paar-Jan Pelzl (2010), Understanding Cryptography.
