//www.ebook.edu.vn 89* Phương pháp sàng Dyxon và sàng bậc hai Trong phần này giơi thiệu thuật toán phân tích hai số nguyên được coi là mạnh nhất theo nghĩa thời gian tính tốt nhất hiện nay. ý tưởng của một loạt khá lớn các thuật toán phân tích số như phương pháp phân tích các dạng chính phương Danien Shaks, phương pháp đặc biệt của Ơle, phương pháp khai triển liên phân số của Morrison và Brillhart, phương pháp sàng bậc hai của Pomerance, Dixon… là cố tìm được x≠± y mod n sao cho x2≡y2 mod n, còn kỹ thuật tìm cụ thể như thế nào thì chính là nội dung riêng của từng thuật toán Thuật toán Dixon được thực hiện như sau: - Sử dụng một tập B chứa các số nguyên tố bé và gọi là cơ sở phân tích - Chọn một vài số nguyên x sao cho tất cả các thừa số nguyên tố của x2 mod n nằm trong cơ sở B, - Lấy tích của một vài giá trị x sao cho mỗi nguyên tố trong cơ sở được sử dụng một số chẵn lần. Chính điều này dẫn đến một đồng dư thức dạng mong muốn x2≡y2 mod n mà ta hy vọng sẽ đưa tới việc phân tích n và suy ra gcd[x-y,n] là một ước của n. Ví dụ: Giả sử chọn: n = 15770708441, B = {2, 3, 5, 7, 11, 13} Và chọn ba giá trị x là : 8340934156, 12044942944, 2773700011 Xét ba đồng dư thức: 83409341562 ≡ 3x7 [mod n] 120449429442 ≡ 2x7x13 [mod n] 27737000112 ≡ 2x3x13 [mod n] Lấy tích của ba đồng dư thức trên: [8340934156 x 12044942944 x 2773700011]2 ≡ [2 x 3 x 7 x 13]2 mod n Rút gọn biểu thức bên trong dấu ngoặc trong modulo đó ta có: 95034357852 ≡ 5462 [mod n] Suy ra 9503435785546xy=⎧⎨=⎩ //www.ebook.edu.vn 90Tính gcd[x-y,n] = gcd[9503435785 – 546, 15770708441] = 1157759 Ta nhận thấy 115759 là một thừa số của n Giả sử: - B = {p1,…, pB} là một cơ sở phân tích - C lớn hơn B một chút [chẳng hạn C = B + 10] - Có đồng dư thức: 12212 jjBjjBxpp pααα≡ [mod n] Với 1≤j≤ C, mỗi j, xét véc tơ: 12 2[ mod2, mod2, , mod2] [ ]Bjj j BjaZαα α=∈ Nếu có thể tìm được một tập con các aj sao cho tổng theo modulo 2 là vectơ [0, 0,…,0] thì tích của các xj tương ứng sẽ được sử dụng mỗi nhân tử trong B một số chẵn lần. Ví dụ: Xét lại ví dụ trên n = 15770708441, B = {2, 3. 5, 11, 13Ư Cho ba vectơ a1, a2, a3 : A1 = [0, 1, 0, 1, 0, 0] A2 = [1, 0, 0, 1, 0, 1] A3 = [1, 1, 0, 0, 0, 1] Suy ra a1 + a2 + a3 = [0, 0, 0, 0, 0, 0] mod 2 Trong trường hợp này nếu C B, sự phụ thuộc tuyến tính này nhất định phải tồn tại và ta có thể dễ dàng tìm được bằng phương pháp loại trừ Gaux. Lý do giải thích tại sao lấy C > B + 1 là do không có gì đảm bảo để một đồng dư thức cho trước bất kỳ sẽ tạo được phân tích n. Người ta chỉ ra rằng khoảng 50% thời gian thuật toán cho ra x≡± y [mod n]. Tuy nhiên nếu C > B + 1 thì //www.ebook.edu.vn 91có thể nhận được một vài đồng dư thức như vậy. Hy vọng là ít nhất một trong các đồng dư thức kết quả sẽ dẫn đến việc phân tích n. Vấn đề cần đặt ra là phải làm như thế nào để nhận được các số nguyên xj mà các giá trị xj2 mod n có thể phân tích hoàn toàn trên cơ sở B. Một số phương pháp có thể thực hiện được điều đó. Biện pháp sàng bậc hai do Pomerance đưa ra dùng các số nguyên dạng xj = j + n⎢⎥⎣⎦, j = 1, 2, … dùng để xác định các xj phân tích được trên B. Nếu B là một số lớn thì thích hợp hơn cả là nên phân tích số nguyên xj trên B. Khi B càng lớn thì càng phải gom nhiều đồng dư thức hơn trước khi có thể tìm ra một số quan hệ phụ thuộc và điều này dẫn đến thời gian thực hiện cỡ [1 0[1] ln lnln ]0[ ]nne+ Với 0[1] là một hàm tiến tới 0 khi n tiến tới ∞ Thuật toán sàng trường số là thuật toán cũng phân tích n bằng cách xây dựng một đồng dư thức x2≡y2 mod n, song nó lại được thực hiện bằng cách tính toán trên vành các số đại số. * Thời gian tính các thuật toán trên thực tế Thuật toán đường cong Elliptic hiệu quả hơn nếu các thừa số nguyên tố của n có kích thước khác nhau. Một số rất lớn đã được phân tích bằng thuật toán đường cong Elliptic là số Fermat 2[2 1]n− [ được Brent thực hiện năm 1988]. Thời gian tính của thuật toán này được tính là [1 0[1] 2ln lnln ]0[ ]ppe+ p là thừa số nguyên tố nhỏ nhất của n Trong trường hợp nếu hai ước của n chênh lệch nhau nhiều thì thuật toán đường cong Elliptic tỏ ra hơn hẳn thuật toán sàng bậc hai. Tuy nhiên nếu hai ước của n xấp xỉ nhau thì thuật toán sàng bậc hai nói chung trội hơn thuật toán đường cong Elliptic. //www.ebook.edu.vn 92Sàng bậc hai là một thuật toán thành công nhất khi phân tích các modulo RSA với n = p.q và p, q là các số nguyên tố có cùng kích thước. Năm 1983, thuật toán sàng bậc 2 đã phân tích thành công số có 69 chữ số, số này là một thừa số của 2251 – 1 [do Davis, Holdredye và Simmons thực hiện]. Đến năm 1989 đã có thể phân tích được các số có tới 106 chữ số theo thuật toán này [ do Lenstra và Manasse thực hiện], nhờ phân bố các phép tính cho hàng trăm trạm làm việc tách biệt [ người ta gọi phương pháp này là “Phân tích thừa số bằng thư tín điện tử”]. Các số RSA – d với d là chữ số thập phân của số RSA [d = 100 ÷500] được công bố trên Internet như là sự thách đố cho các thuật toán phân tích số. Vào 4/1994 Atkins, Lenstra và Leyland đã phân tích được một số 129 chữ số, nhờ sử dụng sàng bậc hai. Việc phân tích số RSA – 129 trong vòng một năm tính toán với máy tính có tốc độ 5 tỷ lệnh trên 1 giây, với công sức của hơn 600 nhà nghiên cứu trên thế giới. Thuật toán sàng trường số là một thuật toán mới nhất trong ba thuật toán. Thuật toán sàng trường số cũng phân tích số nguyên n bằng việc xây dựng đồng dư thức x2≡y2 mod n. Nhưng việc thực hiện bằng cách tính toán trên các vành đại số… Sàng trường số vẫn còn trong thời kỳ nghiên cứu. Tuy nhiên theo dự đoán thì phải chứng tỏ nhanh hơn với các số có trên 125 chữ số thập phân. Thời gian tính của thuật toán sàng trường số là 233[1.92 0[1]] ln [ln ln ]0[ ]nne− Việc trình bày các thuật toán phân tích trên để hiểu rõ một phần nào các biện pháp tấn công vào RSA để có thể xây dựng một hệ mật an toàn hơn. Từ các thuật toán trên yêu cầu đối với p và q nên thoả mãn: - Các số nguyên p và q phải xấp xỉ nhau về độ dài nhưng không được xấp xỉ nhau về độ lớn. - Các số p± 1 và q± 1 phải có ít nhất một thừa số nguyên tố lớn - Phải có khoảng luỹ thừa 2 đủ lớn - Giá trị F = gcd[p± 1, q±1] không được lớn hơn 3n //www.ebook.edu.vn 93- Các số p và q phải là các số có ít nhất 100 chữ số thập phân Nhận xét đầu để ngăn chặn khả năng tấn công bởi thuật toán sơ đẳng nhất, đó là thuật toán sàng, đồng thời như các phân tích trên thì đã đưa bài toán phân tích về trường hợp khó giải nhất, của ngay thuật toán được đánh giá là có triển vọng nhất đó là thuật toán dựa vào phương pháp trường số. Nhận xét thứ hai dựa vào khả năng của thuật toán Pollard và thuật toán Williams mà khả năng đó phụ thuộc chủ yếu vào việc các số p± 1 và q±1 phân tích được hoàn toàn qua các số nguyên tố trong tập B. Trong tập B có thể là tập các số nguyên tố nhỏ hơn 32 bits. Ngược lại cũng có thể sử dụng tập B lớn hơn. Do đó nhận xét này cũng hợp lý. Việc có một tham số công khai như số mũ lập mã e chắc chắn phải cung cấp thêm thông tin cho bài toán phân tích số. Do đó cần tìm hiểu mức độ ảnh hưởng của thông tin này để xây dựng nên một yêu cầu với số mũ e này và phần nào đó có tính đối ngẫu liên quan cả số mũ giải mã d. Để cho một số nguyên tố đáp ứng tiêu chuẩn về độ dài thì đối với hệ mật sử dụng bài toán logarit cần các số nguyên tố có độ dài khoảng gấp rưỡi so với các số nguyên tố dùng cho loại hệ mật dựa trên bài toán phân tích số. Nếu có được một thuật toán nhanh [thuật toán xác suất như Rabin – Miller] thì thời gian tính cũng phải cỡ 0[n3] [ với n là độ dài khoảng gấp rưỡi so với các số nguyên tố trong các số nhỏ hơn n theo Direcle là ln[]nnnΠ≈, do vậy khả năng tìm được số nguyên tố 521 bít so với một số nguyên tố 350 bit lâu hơn gấp nhiều lần. Thiết kế một hệ mật sử dụng bài toán logarit rời rạc chỉ cần đúng một số nguyên tố trong khi để có một tính năng tương đương, thì hệ mật dựa trên bài toán phân tích số nguyên ra thừa số nguyên tố cần đến 2k số nguyên tố cho hệ thống có k người sử dụng. Các số nguyên tố cần dùng cho hệ mật thứ hai đòi hỏi phải có các ước nguyên tố lớn, dẫn đến khả năng tìm kiếm số nguyên tố cũng sẽ khó khăn hơn nhiều so với hệ mật thứ nhất. 4.3. Một số hệ mật mã công khai khác //www.ebook.edu.vn 94Trong chương này ta sẽ xem xét một số hệ mật khoá công khai khác. Hệ mật Elgamal dựa trên bài toán logarithm rời rạc là bài toán được dùng nhiều trong nhiều thủ tục mật mã. Bởi vậy ta sẽ dành nhiều thời gian để thảo luận về bài toán quan trọng này. ở các phần sau sẽ xem xét sơ lược một số hệ mật khoá công khai quan trọng khác bao gồm các hệ thoóng loại Elgamal dựa trên các trường hữu hạn và các đường cong elliptic, hệ mật xếp ba lô Merkle-Helman và hệ mật McElice. 4.3.1.Hệ mật Elgamal và các logarithm rời rạc. Hệ mật Elgamal được xây dựng trên bài toán logảithm rời rạc . Chúng ta sẽ bắt đầu băng việc mô tả bài toán bài khi thiết lập môi trường hữu hạn Zp, p là số nguyên tố [Nhớ lại rằng nhóm nhân Zp* là nhóm cyclic và phần tử sinh của Zp* được gọi là phần tử nguyên thuỷ]. Bài toán logarithm rời rạc trong Zp là đối tượng trong nhiều công trình nghiên cứu và được xem là bài toán khó nếu p được chọn cẩn thận. Cụ thể không có một thuật toán thời gian đa thức nào cho bài toán logarithm rời rạc. Để gây khó khăn cho các phương pháp tấn công đã biết p phải có ít nhất 150 chữ số và [p-1] phải có ít nhất một thừa số nguyên tố lớn. Lợi thế của bài toán logarithm rời rạc trong xây dượng hệ mật là khó tìm được các logarithm rời rạc, song bài toán ngược lấy luỹ thừa lại có thể tính toán hiệu quả theo thuật toán “bình phương và nhân”. Nói cách khác, luỹ thừa theo modulo p là hàm một chiều với các số nguyên tố p thích hợp. Elgamal đã phát triển một hệ mật khoá công khai dựa trên bài toán logarithm rời rạc. Hệ thống này được trình bày sau. Hệ mật này là một hệ không tất định vì bản mã phụ thuộc vào cả bản rõ x lẫn giá trị ngẫu nhiên k do Alice chọn. Bởi vậy, sẽ có nhiều bản mã được mã từ cùng bản rõ. Bài toán logarithm rời rạc trong Zp //www.ebook.edu.vn 95 Hệ mật khoá công khai Elgamal trong Zp* Sau đây sẽ nmô tả sơ lược cách làm việc của hệ mật Elgamal .Bản rõ x được “che dấu” bằng cách nhân nó với βk để tạo y2 . Giá trị αk cũng được gửi đi như một phần của bản mã. Bob – người biết số mũ bí mật a có thể tính được βk từ αk . Sau đó anh ta sẽ “tháo mặt nạ” bằng cách chia y2 cho βk để thu được x. Ví dụ: Cho p = 2579, α = 2, a = 765. Khi đó β = 2765 mod 2579 = 949 Bây giờ ta giả sử Alice muốn gửi thông báo x = 1299 tới Bob. Giả sử số ngẫu nhiên k mà cô chọn là k = 853. Sau đó cô ta tính Cho p là số nguyên tố sao cho bài toán logarithm rời rạc trong Zp là khó giải. Cho α ∈ Zp* là phần tử nguyên thuỷ.Giả sử P = Zp* , C = Zp* × Zp* . Ta định nghĩa: K = {[p, α,a,β]: β ≡ αa [mod p]} Các giá trị p, α,β được công khai, còn a giữ kín Với K = [p, α,a,β] và một số ngẫu nhiên bí mật k ∈ Zp-1, ta xác định: ek [x,k] = [y1 ,y2 ] trong đó y1 = αk mod p y2 = xβk mod p với y1 ,y2 ∈ Zp* ta xác định: dk[y1 ,y2 ] = y2 [y1a ]-1 mod p Đặc trương của bài toán: I = [p,α,β] trong đó p là số nguyên tố, α ∈ Zp là phần tử nguyên thuỷ , β ∈ Zp* Mục tiêu:Hãy tìm một số nguyên duy nhất a, 0 ≤ a ≤ p-2 sao cho: αa ≡ β [mod p] Ta sẽ xác định số nguyên a bằng logα β //www.ebook.edu.vn 96 y1 = 2853 mod 2579 = 435 y2 = 1299 × 949853 mod 2579 = 2396 Khi đó Bob thu được bản mã y = [435,2396], anh ta tính x = 2396 × [435765]-1 mod 2579 = 1299 Đó chính là bản rõ mà Alice đã mã hoá. 4.3.2 Mật mã Balô. 4.3.2.1. Cơ sở của mật mã balô Mật mã balô xuất phát từ bài toán tổng tập con tổng quát [bài toán al ô]. Bài toán được phát biểu như sau: Cho dãy các số dương S={s1, s2,…., sn} và một số dương C. Hỏi có tồn tại một tập con nằm trong S sao cho tổng tập con đó bằng C. [Hỏi có tồn tại một véc tơ nhị phân x=[x1, x2,…, xn] sao cho C=∑xi.si [i=1 n]] Đây là bài toán khó có thời gian là hàm mũ O[2n]. Nếu S là dãy siêu tăng thì bài toán trên giải được với thời gian tuyến tính O[n]. Định nghĩa: Dãy S gọi là siêu tăng nếu mọi si>∑sj [j=1, i-1] [tức là phần tử đứng sau lớn hơn tổng các phần tử đứng trước nó] Khi đó bài toán tổng tập con được phát biểu như sau: Cho dãy siêu tăng S={s1, s2,…., sn} và một số dương C. Hỏi có tồn tại một tập con nằm trong S sao cho tổng tập con đó bằng C. [Hỏi có tồn tại một véc tơ nhị phân x=[x1, x2,…, xn] sao cho C=∑xi.si [i=1 n]] Khi đó bài toán được giải như sau: For i:=n downto 1 do Begin If C>=si then xi=1 //www.ebook.edu.vn 97Else xi:=0; C:=C-xi.si; End; If C=0 then “bài toán có đáp án là véc tơ x” Else “bài toán không có đáp án”; Áp dụng bài toán này ta sử dụng dãy S siêu tăng làm khóa bí mật. Sau đó tác động lên dãy S để biến đổi thành một dãy bất kỳ, và công khai dãy này là khóa công khai. Ta có hệ mật mã al ô như sau: 4.3.2.2. Thuật toán: * Tạo khóa: - Chọn dãy siêu tăng S={s1, s2, …, s3} - Chọn p sao cho p>∑si [i=1 n] - Chọn a sao cho 1