Giáo trình Lý thuyết mật mã - Chương 4: Hệ mật RSA và vấn đề phân tích thừa số

58 trang ngocly 170

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Lý thuyết mật mã - Chương 4: Hệ mật RSA và vấn đề phân tích thừa số", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

giao_trinh_ly_thuyet_mat_ma_chuong_4_he_mat_rsa_va_van_de_ph.pdf

Nội dung text: Giáo trình Lý thuyết mật mã - Chương 4: Hệ mật RSA và vấn đề phân tích thừa số

Ch−ơng 4 Hệ mật RSA và vấn đề phân tích thừa số 4.1. Giới thiệu về hệ mật khoá công khai Trong mô hình mật m cổ điển tr−ớc đây mà hiện nay đang đ−ợc nghiên cứu Alice (ng−ời gửi) và Bob (ng−ời nhận) chọn một cách bí mật khoá K. Sau đó dùng K để tạo luật m hoá ekvà luật giải m dk. Trong hệ mật này dk hoặc giống nh− ek hoặc dễ dàng nhận đ−ợc từ nó (ví dụ trong hệ DES quá trình giải m hoàn toàn t−ơng tự nh− quá trình m nh−ng thủ tục khoá ng−ợc lại). Các hệ mật thuộc loại này đ−ợc gọi là hệ mật khoá bí mật, nếu để lộ ek thì làm cho hệ thống mất an toàn. Nh−ợc điểm của hệ mật này là nó yêu cầu phải có thông tin tr−ớc về khoá K giữa Alice và Bob qua một kênh an toàn tr−ớc khi gửi một bản m bất kỳ. Trên thực tế điều này rất khó đảm bảo. Chẳng hạn khi Alice và Bob ở cách xa nhau và họ chỉ có thể liên lạc với nhau bằng th− tín điện tử (Email). Trong tình huống đó Alice và Bob không thể tạo một kênh bảo mật với giá phải chăng. ý t−ởng xây dựng một hệ mật khoá công khai (hay khoá dùng chung) là tìm một hệ mật không có khả năng tính toán để xác định dkkhi biết ek. Nếu thực hiện đ−ợc nh− vậy thì quy tắc m ek có thể đ−ợc công khai bằng cách công bố nó trong một danh bạ (bởi vậy nên có thuật ngữ hệ mật khoá công khai). Ưu điểm của hệ mật khoá công khai là ở chỗ Alice (hoặc bất kì một ai) có thể gửi một bản tin đ m cho Bob (mà không cần thông tin tr−ớc về khoá mật) bằng cách dùng luật m công khai ek. Ng−ời nhận A sẽ là ng−ời duy nhất có thể giải đ−ợc bản m này bằng cách sử dụng luật giải m bí mật dk của mình. Có thể hình dung hệ mật này t−ơng tự nh− sau. Alice đặt một vật vào một hộp kim loại và rồi khoá nó lại bằng một khoá số do Bob để lại. Chỉ có Bob là ng−ời duy nhất có thể mở đ−ợc hộp vì chỉ có anh ta mới biết tổ hợp m của khoá số của mình.
ý t−ởng về một hệ mật khoá công khai đ đựoc Diffie và Hellman đ−a ra vào năm 1976. Còn việc hiện thực hoá nó thì do Rivesrt, Shamir và Adleman đ−a ra đầu tiên vào năm 1977, họ đ tạo nên hệ mật nổi tiếng RSA (sẽ đ−ợc nghiên cứu trong ch−ơng này). Kể từ đó một số hệ đ−ợc công bố, độ mật của chúng dựa trên các bài toán tính toán khác nhau. Sau đây là các hệ mật khoá công khai quan trọng : + Hệ mật RSA: Độ bảo mật của hệ RSA dựa trên độ khó của việc phân tích ra thừa số nguyên tố các số nguyên lớn. Hệ này sẽ đ−ợc mô tả trong phần 4.3. + Hệ mật xếp ba lô Merkle - Hellman: Hệ này và các hệ liên quan dựa trên tính khó giải của bài toán tổng các tập con (bài toán này là bài toán NP đầy đủ – là một lớp khá lớn các bài toán không có thuật giải đ−ợc biết trong thời gian đa thức). Tuy nhiên tất cả các hệ mật xếp ba lô khác nhau đều đ bị chứng tỏ là không mật (ngoại trừ hệ mật Chor – Rivest sẽ đ−ợc nêu d−ới đây). Hệ mật này đ−ợc xét ở ch−ơng 5. + Hệ mật McEliece: Hệ này dựa trên lý thuyết m đại số và vẫn còn đ−ợc coi là an toàn. Hệ mật McEliece dựa trên bài toán giải m cho các m tuyến tính (cũng là một bài toán NP đầy đủ). Hệ mật McEliece đ−ợc trình bày ở ch−ơng 5. + Hệ mật Elgamal: Hệ mật Elgamal dựa trên tính khó giải của bài toán logarithm rời rạc trên các tr−ờng hữu hạn (xem trong ch−ơng 5). + Hệ mật Chor - Rivest: Hệ mật Chor - Rivest cũng đ−ợc xem nh− một loại hệ mật xếp ba lô. Tuy nhiên nó vẫn đ−ợc coi là an toàn. + Hệ mật trên các đ−ờng cong Elliptic Các hệ mật này là biến t−ớng cảu các hệ mật khác (chẳng hạn nh− hệ mật Elgamal) , chúng làm việc trên các đ−ờng cong Elliptic chứ không phải là trên các tr−ờng hữu hạn. Hệ mật này đảm bảo độ mật với khoá số nhỏ hơn các hệ mật khoá công khai khác (xem ch−ơng 5). Một chú ý quan trọng là một hệ mật khoá công khai không bao giờ có thể đảm bảo đ−ợc độ mật tuyệt đối (an toàn vô điều kiện). Sở dĩ nh− vậy vì đối ph−ơng khi nghiên cứu một bản m y có thể m lần l−ợt các bản rõ bằng luật m công khai ek cho tới khi anh ta tìm đ−ợc bản rõ duy nhất x đảm bảo y = ek
(x). Bản rõ này chính là kết quả giải m của y. Bởi vậy ta chỉ nghiên cứu độ mật về mặt tính toán của các hệ mật này. Một khái niệm có ích khi nghiên cứu hệ mật khoá công khai là khái niệm về hàm cửa sập một chiều. Ta định nghĩa khái niệm này một cách không hình thức. Hàm m khoá công khai ek của Bob phải là một hàm dễ tính toán. Song việc tìm hàm ng−ợc (hàm giải m ) phải rất khó khăn (đối với bất kỳ ai không phải là Bob). Đặc tính dễ tính toán nh−ng khó tính toán hàm ng−ợc th−ờng đ−ợc gọi là đặc tính một chiều. Bởi vậy điều kiện cân thiết là ek phải là hàm một chiều. Các hàm một chiều đóng vai trò quan trọng trong mật m học: chúng rất quan trong các hệ mật khoá công khai và trong nhiều lĩnh vực khác. Đáng tiếc là mặc dù có rts nhiều hàm đ−ợc coi là hàm một chiều nh−ng cho tới nay vẫn không tồn tại một hàm nào có thể chứng minh đ−ợc là hàm một chiều. Sau đây là một ví dụ về một hàm đ−ợc coi là hàm một chiều. Giả sử n là tích của hai số nguyên tố lớn p và q, giả sử b là một số nguyên d−ơng. Khi đó ta xác định ánh xạ f : Z n Z n là f(x) = x b mod n (với b và n đ đ−ợc chọn thích hợp thì đây chính là hàm m RSA, sau này sẽ còn nói nhiều về nó). Để xây dựng một hệ mật khoá công khai thì việc tìm đ−ợc một hàm một chiều vẫn ch−a đủ. Ta không muốn ek là hàm một chiều đối với Bob vì anh ta phải có khả năng giải m các bản tin nhận đ−ợc một cách hiệu quả. Điều cần thiết là Bob phải có một cửa sập chứa thông tin bí mật cho phép dễ dàng tìm hàm ng−ợc của ek. Nh− vậy Bob có thể giải m một cách hữu hiệu vì anh ta có một hiểu biết tuyệt mật nào đó về K. Bởi vậy một hàm đ−ợc gọi là cửa sập một chiều nếu nó là hàm một chiều và nó trở nên dễ tính ng−ợc nếu biết một cửa sập mhất định. Ta sẽ xét cách tìm một cửa sập đối với hàm f nêu ở trên trong phần 4.3. Các tìm này sẽ dẫn đến hệ mật RSA.
4.2. một số vấn đề sâu hơn về lý thuyết số Tr−ớc khi mô tả hệ mật RSA làm việc ra sao cần phải xem xét một số yếu tố liên quan đến lý thuyết số và số học modulo. Hai kết quả cần biết là thuật toán Euclide và định lý phần d− China. 4.2.1 Thuật toán Euclide Trong ch−ơng 1 đ xét Z n là một vành với số nguyên d−ơng bất kỳ n. Ta cũng đ chứng tỏ rằng phần tử b ∈ Z n có phần tử nghịch đảo (phần tử ng−ợc của phép nhân) khi và chỉ khi −CLN (b,n) = 1 và các số nguyên d−ơng nhỏ hơn n và nguyên tố cùng nhau với n bằng φ (n). Tập các thặng d− theo modulo n và nguyên tố cùng nhau với n đ−ợc ký * * hiệu là Z n .Không khó khăn có thể thấy rằng Z n sẽ tạo nên một nhóm Abel đối với phép nhân. Ta cũng biết rằng, phép nhân theo modulo n là giao hoán và * kết hợp và phần tử đơn vị là 1. Một phần tử bất kỳ trong Z n đều có nghịch đảo * * bội (cũng nằm trong Z n ). Cuối cùng Z n là đóng đối với phép nhân vì xy là nguyên tố cùng nhau với n khi x và y nguyên tố cùng nhau với n. (H y chứng minh điều này!) * Cho tới bây giờ ta chỉ biết rằng một phần tử b bất kì ∈ Z n đều có nghịch đảo b -1 song việc tính nó vẫn ch−a nói đến. Một thuật toán nh− vậy đ−ợc gọi là thuật toán Euclide mở rộng. Tr−ớc tiên ta sẽ mô tả thuật toán Euclide, thông th−ờng thuật toán này đ−ợc dùng để tính −ớc số chung lớn nhất ( −CLN ) của hai số nguyên d−ơng r 0 và r 1 với r 0 > r 1.Thuật toán Euclide bao gồm việc thực hiện các phép toán nh− sau: r0 = q 1 r 1 +r 2 0 < r 2 < r 1 r1 = q 2 r 2 +r 3 0 < r 3 < r 2 . . rm -2 = q m -1 r m -1 +r m 0 < r m -1 < r m rm -1 = q m r m Khi đó dễ dàng chứng tỏ đ−ợc rằng −CLN (r 0 , r 1 ) = −CLN (r 1 , r 2 ) = . . . −CLN (r m-1 , r m ) = r m
Bởi vậy −CLN (r 0 , r 1 ) = r m Vì thuật toán Euclide tính các −CLN nên có thể áp dụng nó để xác định xem liệu một số nguyên d−ơng b < n có nghịch đảo theo modulo n không bằng cách bắt đầu với r 0 = n và r 1 = b. Tuy nhiên thuật toán này không cho phép tính giá trị của phần tử nghịch đảo (nếu nó tồn tại). Bây giờ giả sử định nghĩa một d y số t 0 , t 1 , ,t m theo các công thức truy toán sau (trong đó các giá trị q j đ đ−ợc xác định ở trên) t0 = 0 t1 = 1 tj = t j-2- q j-1 t j-1 mod r 0 nếu j ≥ 2 Ta có kết quả quan trọng sau Định lý 4.1. Với 0 ≤ j ≤ m, ta có r j ≡ t jr1 (mod r 0), trong đó các giá trị q j và r j đ−ợc xác định theo thuật toán Euclide còn các giá trị t j đ−ợc xác định theo công thức truy toán ở trên. Chứng minh: Ta chứng minh bằng cách quy nạp theo j. Định lý hiển nhiên đúng với j = 0 và j = 1. Giả sử định lý cũng đúng với j = i-1 và j = i-2, trong đó i ≥ 2; sau đây ta sẽ chứng tỏ định lý đúng với j = i. Theo quy nạp ta có ri-2 ≡ t i-2 r 1 (mod r 0) và ri-1 ≡ t i-1 r 1 (mod r 0) Bây giờ ta tính ri = r i-2 - q i-1 r i-1 ≡ t i-2 r 1 - q i-1 t i-1 r 1 (mod r 0) ≡ (t i-2 - q i-1 t i-1)r 1 (mod r 0) ≡ t i r 1 (mod r 0) Bởi vậy theo quy nạp định lý là đúng. Hệ quả rút ra trực tiếp từ định lý trên. Hệ quả 4.2:
−CLN -1 Giả sử (r 0,r 1) = 1, khi đó t m = r 1 mod r 0. Hìn 2.1 Thuật toán Euclide mở rộng: 1. n0 = n 2. b0 = b 3. t0 = 0 4. t = 1 5. q = n0 /b 0 6. r = n 0 - q ìb0 7. While r > 0 do 8. temp = t 0 -qìt 9. if temp ≥ 0 then temp = temp mod n 10. if temp < 0 then temp = n - ((- temp) mod n) 11. t 0 = t 12. t = temp 13. n 0 = b0 14. b0 = r 15. q = n0 /b 0 16. r = n 0 - q ìb0 17. if b0 ≠ 1 then b không có nghịch đảo theo modulo n else b -1 = t mod n . Xét thấy d y các số t 0, t 1, . . . , t m có thể đ−ợc tính toán trong thuật toán Euclide đồng thời nh− các giá trị q j và r j. Hình 4.1 trình bày thuật toán Euclide mở rộng để tính nghịch đảo của b theo modulo n (nếu nó tồn tại). Trong thuật toán này không phải dùng mảng (array) để ghi các giá trị q j, r j và t j vì chỉ cần nhớ hai giá trị cuối cùng trong mỗi d y này ở một điểm bất kì trong thuật toán. Trong b−ớc 10 của thuật toán ta đ viết biểu thức cho biến temp theo cách để phép rút gọn theo modulo n đ−ợc thực hiện đối với số d−ơng. (Tr−ớc đây đ biết rằng việc rút gọn theo modulo của các số âm sẽ dẫn đến các kết quả âm ở nhiêù ngôn ngữ máy tính; còn ở đây ta muốn kết thúc với kết quả d−ơng). ở b−ớc 12 luôn có tb ≡ r (mod n) (kết quả này đ đ−ợc chứng minh ở định lý 4.1).
Sau đây là một ví dụ nhỏ để minh hoạ Ví dụ 4.1. Giả sử ta cần tính 28 -1 mod 75. Thuật toán Euclide mở rộng thực hiện nh− sau: 75 = 2 ì 28 +29 b−ớc 6 73 ì 28 mod 75 = 19 b−ớc 12 28 = 1 ì 19 + 9 b−ớc 16 3 ì 28 mod 75 = 9 b−ớc 12 19 = 2 ì 9 + 1 b−ớc 16 67 ì 28 mod 75 = 1 b−ớc 12 9 = 9 ì 1 b−ớc 16 Vì thế 28 -1 mod 75 = 67. 4.2.2. Định lý phần d− China Định lý này thực sự là một ph−ơng pháp giải các hệ ph−ơng trình đồng d−. Giả sử m 1, . . . , m r là các số nguyên tố cùng nhau từng đôi một (tức −CLN (m i,m j)=1 nếu j ≠i). Giả sử a 1,. . ., a r là các số nguyên xét hệ ph−ơng trình đồng d− sau: x ≡ a 1 (mod m 1) x ≡ a 2 (mod m 2) . . x ≡ a r (mod m r) Định lý phần d− China khẳng định rằng hệ này có nghiệm duy nhất theo modulo M = m 1ìììm2ììì. . . ìììmr. Ta sẽ chứng minh kết quả đó trong phần này và cũng mô tả một thuật toán hữu hiệu để giải hệ đồng d− thức dạng trên. Để thuận tiện, xét hàm π : Z M Z m1ì . . . ìZmr. Hàm này đ−ợc định nghĩa nh− sau: π(x) = (x mod m 1, . . . , x mod m r )
Ví dụ 4.2 Giả sử r = 2, m 1 = 5 và m 2 = 3, bởi vậy M = 15. Khi đó hàm π có giá trị sau π(0) = (0,0) π(1) = (1,1) π(2) = (2,2) π(3) = (3,0) π(4) = (4,1) π(5) = (0,2) π(6) = (1,0) π(7) = (2,1) π(8) = (3,2) π(9) = (4,0) π(10) =(0,1) π(11) =(1,2) π(12) =(2,0) π(13) =(3,1) π(14) =(4,2) Việc chứng minh định lý phần d− China t−ơng đ−ơng với việc chứng minh rằng hàm π là một song ánh. Điều này có thể dễ dàng thấy đ−ợc ở ví dụ 4.2. Trong thực tế có thể đ−a ra một công thức t−ờng minh tổng quát cho hàm ng−ợc π-1. Với 1 ≤ i ≤ r, định nghĩa: Mi = M/m i Khi đó, dễ dàng thấy rằng −CLN (M i,mi) = 1 với 1 ≤ i ≤ r. Tiếp theo, với 1 ≤ i ≤ r, định nghĩa -1 yi = M i mod m i (phần tử nghịch đảo này tồn tại do −CLN (M i,m i) = 1 và có thể tìm đ−ợc bằng thuật toán Euclide). Cần để ý rằng Miyi ≡ 1 (mod m i) với 1 ≤ i ≤ r. Bây giờ ta định nghĩa hàm ρ: Z m1 ì . . . ì Z mr Z M nh− sau r ρ (a , a r )= ∑ a M y mod M 1 i = 1 i i i Ta sẽ chứng tỏ rằng ρ = π-1 , tức là nó cho một công thức t−ờng minh để giải hệ đồng d− thức ban đầu. Kí hiệu X = ρ(a 1, . . . ,a r) và cho 1 ≤ j ≤ r. Xét số hạng a iMiyi trong tổng trên khi rút gọn theo modulo m j. Nếu i = j thì aiMiyi ≡ a i (mod m i)
vì Miyi ≡ 1 (mod m i) Mặt khác, nếu i ≠ j thì aiMiyi ≡ 0(mod m j) do m i Mi trong tr−ờng hợp này. Bởi vậy chúng ta có X ≡ ∑ a i M i y i (mod m j ) ≡ a i (mod m j ) Do điều này đúng đối với mọi j, 1 ≤ j ≤ r, nên X là nghiệm của hệ ph−ơng trình đồng d−. Tới lúc này cần phải chứng tỏ rằng nghiệm X là duy nhất theo modulo M và điều này có thể đ−ợc chứng tỏ bằng cách tính toán đơn giản. π là hàm từ một miền có lực l−ợng M sang một miền có lực l−ợng M. Ta vừa mới chứng tỏ rằng π là một toàn ánh. Bởi vậy π phải cũng là một đơn ánh (tức là phép t−ơng ứng 1 - 1) do miền xác định và miền giá trị có cùng lực l−ợng. Điều đó kéo theo π là một song ánh và π-1 = p. Cũng cần chú ý là π-1 là một hàm tuyến tính của các biến a 1,. . ., a r. Sau đây là một ví dụ lớn hơn để minh hoạ Ví dụ 4.3 Giả sử r = 3, m 1 = 7, m 2 = 11 và m 3 = 13. Khi đó M = 1001. Ta tính M 1 = 143, M 2 = 91 và M 3 = 77 và sau đó tính y 1 = 5, y 2 = 4 và y 3 = 12. Khi đó hàm -1 π : Z 7ìZ11 ìZ13 Z 1001 có dạng: -1 π (a 1,a 2,a 3) = 715a 1 +364a 2 + 924a 3 mod 1001 Ví dụ, nếu x ≡ 5 (mod 7), x ≡ 3 (mod 11) và x ≡ 10 (mod 13) thì công thức trên sẽ cho ta biết rằng x = 715 ì 5 + 364 ì 3 + 924 ì 10 mod 1001 = 13907 mod 1001 = 894 mod 1001 Điều này có thể kiểm tra đ−ợc bằng cách rút gọn 894 theo modulo 7, 11 và 13. Để tham khảo sau này, ta sẽ ghi các kết quả ở phần này d−ới dạng một định lý
Định lý 4.3 (Định lý phần d− China) Giả sử m 1, . . . ,m r là các số nguyên d−ơng nguyên tố cùng nhau từng đôi một và cho a 1, . . ., a r là các số nguyên. Khi đó, hệ r đồng d− thức x ≡ a i (mod mi) (1 ≤ i ≤ r ) sẽ có một nghiệm duy nhất theo modulo M = m 1ì . . . ì m r đ−ợc cho theo công thức r x = ∑ a i M i y i mod M i=1 -1 trong đó M i = M/m i và y i = M i mod m i, với 1 ≤ i ≤ r. 4.2.3. Các kiến thức cần thiết khác Sau đây sẽ nhắc tới một kết quả khác trong lý thuyết nhóm sơ cấp: định lý Lagrange. Định lý này có liên quan đến cách đề cập về hệ mật RSA. Với một nhóm nhân hữu hạn G, ta định nghĩa cấp của một phần tử g ∈ G là số nguyên d−ơng m bé nhất sao cho g m = 1. Ta có kết quả sau đây (không chứng minh ). Định lý 4.4 (Lagrange ) Giả sử G là một nhóm cấp n và g ∈ G. Khi đó cấp của g là −ớc của n. Với mục đích đ−a ra, hệ quả sau rất quan trọng. Hệ quả 4.5 * φ(n) Nếu b ∈ Z n thì b ≡ 1 (mod n) * Chứng minh: Z n là nhóm nhân cấp φ(n). Hệ quả 4.6 (Ferma) p Giả sử p là số nguyên tố và b ∈ Z p. Khi đó b ≡ b (mod p). Chứng minh: Nếu p là số nguyên tố thì φ(n) = p-1. Bởi vậy, với b ≡0(mod p), kết quả trên đ−ợc rút ra từ hệ quả 4.5. Với b ≡ 0 (mod p), kết quả trên p vẫn đúng do 0 ≡ 0 (mod 0). * Cho tới giờ ta đ biết rằng, nếu p là số nguyên tố thì Z p là một nhóm * cấp p-1 và một phần tử bất kì trong Z p sẽ có bậc là −ớc của p-1. Tuy nhiên, * * nếu p là số nguyên tố thì nhóm Z p là nhóm cyclic: tồn tại một phần tử α ∈ Z p
có cấp bằng p-1. Ta không chứng minh kết quả quan trọng này nh−ng sẽ ghi lại để tham khảo sau này. Định lý 4.7. * Nếu p là số nguyên tố thì Z p là nhóm cyclic. Một phần tử α có cấp p-1 đ−ợc gọi là phần tử nguyên thuỷ modulo p. Xét thấy α là phần tử nguyên thuỷ khi và chỉ khi: i * {α : 0 ≤ i ≤ p-2} = Z p Bây giờ giả sử p – nguyên tố và α - phần tử nguyên thuỷ modulo p. Một phần * i tử bất kì β ∈ Z p có thể đ−ợc viết nh− sau: β = α , trong đó 0 ≤ i ≤ p-2 (theo một cách duy nhất ). Không khó khăn có thể chứng tỏ rằng cấp của β = αi là: p - 1 UCLN(p - 1, i) Nh− vậy bản thân β là phần tử nguyên thuỷ khi và chỉ khi −CLN (p-1,i) = 1. Điều đó dẫn đến là số các phần tử nguyên thuỷ theo modulo p = φ(p-1). Ví dụ 4.4: Giả sử p=13. Bằng cách tính các luỹ thừa liên tiếp của 2 ta có thể thấy rằng 2 là phần tử nguyên thuỷ theo modulo 13: 20 mod 13 =1 21 mod 13 =2 22 mod 13 =4 23 mod 13 =8 24 mod 13 =3 25 mod 13 =6 26 mod 13 =12 27 mod 13 =11 28 mod 13 =9 29 mod 13 =5 210 mod 13 =10 211 mod 13 =7 Phần tử 2 i là nguyên thuỷ khi và chỉ khi −CLN (i,12) = 1; nghĩa là khi và chỉ khi i = 1, 5, 7 hoặc 11. Bởi vậy các phần tử nguyên thuỷ theo modulo 13 là 2, 6, 7 và 11. 4.3. hệ mật RSA Bây giờ chúng ta có thể mô tả hệ mật RSA. Hệ mật này sử dụng các tính toán trong Z n, trong đó n là tích của 2 số nguyên tố phân biệt p và q. Ta nhận thấy rằng φ(n) = (p-1)(q-1).
Mô tả hình thức của hệ mật đ−ợc cho trong hình 4.2 . Ta h y kiểm tra xem các phép m và giải m có phải là các phép toán nghịch đảo của nhau hay không. Vì ab ≡ 1 (mod φ(n)) nên ta có ab = t φ(n) + 1 * với một số nguyên t ≥ 1 nào đó. Giả sử x ∈ Z p ; khi đó ta có: (x b)a ≡ x tφ(n)+1 (mod n) ≡ (x φ(n) )t x (mod n) ≡ 1 t x (mod n) ≡ x (mod n) Hình 4.2: Hệ mật RSA Cho n = p.q trong đó p và q là các số nguyên tố. Đặt P = C = Zn và định nghĩa K = {(n,p,q,a,b): n = p.q, p,q là các số nguyên tố, ab ≡ 1(mod φ(n))} Với K = (n,p,q,a,b) ta xác định b eK (x) = x mod n a và dK (y) = y mod n (x,y) ∈ Z n. Các giá trị n và b đ−ợc công khai , các giá trị p,q,a đ−ợc giữ bí mật. đúng nh− mong muốn. Xem nh− một bài tập, bạn đọc h y chứng tỏ rằng (x b)a * ≡ x (mod n) nếu x ∈ Z n\ Z p . Sau đây là một ví dụ nhỏ (tất nhiên là không mật ) về hệ mật RSA. Ví dụ 4.5: Giả sử Bob chọn p = 101 và q = 113. Khi đó n = 11413 và φ(n) = 100 ì112 = 11200. Vì 11200 = 2 6527, nên có thể dùng một số nguyên b nh− một số mũ m hoá khi và chỉ khi b không chia hết cho 2, 5 hoặc 7. (Vì thế trong thực tế Bob sẽ không phân tích φ(n), anh ta sẽ kiểm tra điều kiện −CLN (φ(n),b) = 1 bằng thuật toán Euclide. Giả sử Bob chọn b = 3533, khi đó theo thuật toán Euclide mở rộng: b-1 = 6597 mod 11200
Bởi vậy số mũ mật để giải m của Bob là a = 6597. Bob sẽ công bố n = 11413 và b = 3533 trong một danh bạ. Bây giờ, giả sử Alice muốn gửi bản rõ 9726 tới Bob. Cô ta tính 9726 3533 mod 11413 = 5761 rồi gửi bản m 5761 trên kênh. Khi đó Bob nhận đ−ợc bản m 5761, anh ta sử dụng số mũ a mật để tính: 5761 6597 mod 11413 = 9762 (cho tới lúc này, các phép m và giải m cho hệ mật đ khá phức tạp, tuy nhiên ta sẽ thảo luận về các thuật toán hữu hiệu cho các phép toán này ở phần sau). b Độ mật của hệ RSA đ−ợc dựa trên giả thiết là hàm m ek(x)= x mod n là hàm một chiều. Bởi vậy thám m sẽ không có khả năng về mặt tính toán để giải m một bản m . Cửa sập cho phép Bob giải m đ−ợc chính là thông tin về phép phân tích thừa số n (n = pq). Vì Bob biết phân tích này, anh ta có thể tính φ(n) = (p-1)(q-1) và rồi tính số mũ giải m a bằng cách sử dụng thuật toán Euclide mở rộng. Sau này chúng ta sẽ còn tiếp tục nói thêm về vấn dề này. 4.4. Thực hiện hệ mật RSA Có nhiều khía cạnh cần thảo luận về hệ mật RSA bao gồm các chi tiết về việc thiết lập hệ mật, tính hiệu quả của phép m và giải m và độ mật của hệ. Để thiết lập hệ thống, Bob sẽ tuân theo các b−ớc đ−ợc nêu trong hình 4.3. Hình 4.3 Thiết lập hệ mật RSA 1. Bob tạo hai số nguyên tố lớn p và q 2. Bob tính n = p.q và φ(n) = (p-1)(q-1) 3. Bob chọn một số ngẫu nhiên b (0< b < φ(n)) sao cho −CLN (b, φ(n)) = 1 4. Bob tính a = b-1 mod φ(n) bằng cách dùng thuật toán Euclide 5. Bob công bố n và b trong một danh bạ và chúng làm khoá công khai .
Việc Bob tiến hành các b−ớc này nh− thế nào sẽ còn đ−ợc tiếp tục thảo luận trong ch−ơng này. Cách tấn công dễ thấy nhất hệ mật này là thám m cố gắng phân tích n ra các thừa số nguyên tố. Nếu thực hiện đ−ợc việc này thì có thể dễ dàng tính đ−ợc φ(n) = (p-1)(q-1) rồi tính số mũ a từ b nh− Bob làm (ng−ời ta phỏng đoán rằng, việc phá hệ mật RSA là t−ơng đ−ơng đa thức với việc phân tích n, tuy nhiên điều này vẫn còn ch−a đ−ợc chứng minh. Hai bài toán đ−ợc gọi là t−ơng đ−ơng đa thức nếu tồn tại một thuật toán thời gian đa thức cho bài toán này sẽ suy ra đ−ợc sự tồn tại một thuật toán thời gian đa thức cho bài toán kia). Vì thế hệ mật RSA đ−ợc coi là mật thì nhất thiết n = pq phải là một số đủ lớn để việc phân tích nó không có khả năng về mặt tính toán. Các thuật toán phân tích hiện thời có khả năng phân tích các số có 130 chữ số thập phân (chi tiết hơn về bài toán phân tích thừa số nguyên tố xem trong phần 4.8). Vì vậy để đảm bảo an toàn nên chọn các số p và q chừng 100 chữ số, khi đó n sẽ có tới 200 chữ số. Một vài áp dụng phần cứng của RSA sử dụng mô đun có độ dài 512 bit. Tuy nhiên một mô đun 512 bit t−ơng ứng với một số có 154 chữ số thập phân (vì số các bit trong biểu diễn nhị phân của một số nguyên băng log 210 lần của các chữ số thập phân) vì vậy không đủ đảm bảo an toàn lâu dài. Bây giờ tạm thời gác lại vấn đề tìm các số nguyên tố có 100 chữ số để xem xét việc thực hiện các phép toán số học trong m và giải m . Phép m (hoặc giải m ) sẽ xoay quanh phép lấy luỹ thừa theo modulo n. Vì n là một số rất lớn nên ta phải sử dụng số học lấy chính xác nhiều lần (multi – precision) để thực hiện các tính toán trong Z n và thời gian tính toán cần thiết sẽ phụ thuộc vào số các bít trong biểu diễn nhị phân của n. Giả sử n có k bit trong biểu diễn nhị phân, tức là k = log 2 n + 1. Sử dụng kĩ thuật số học ở bậc trung học, dễ dàng thấy rằng một phép cộng hai số nguyên k bit có thể thực hiện trong thời gian O(k) và một phép nhân có thể thực hiện trong thời gian O(k 2). Cũng vậy, phép rút gọn một số nguyên theo modulo n (số này có nhiều nhất là 2K bít )có thể thực hiện trong thời gian O(k 2) (để thực hiện phép chia và phép tìm phần d−). Bây giờ giả sử rằng x,y ∈Zn (ở đây xem rằng 0 ≤ x,y ≤ n-1). Khi đó có thể tính xy mod n tr−ớc tiên bằng việc tính tích xy (là một số nguyên 2k bít), rồi rút gọn cho modulo n. Hai b−ớc này có thể thực hiện trong thời gian O(k 2). Ta gọi phép tính này là nhân modulo. Bây giờ xét phép lấy luỹ thừa theo modulo (tức là tính hàm dạng x c mod n). Nh− nhận xét ở trên, cả hai phép m và giải m trong RSA đều là các phép
luỹ thừa theo modulo. Việc tính x c mod n có thể thực hiện bằng c-1 phép nhân modulo, tuy nhiên khi c lớn thì cách tính này rất cồng kềnh. Chú ý rằng c lớn cỡ nh− φ(n) -1 (là một số lớn cấp luỹ thừa so với k). Sử dụng biện pháp "bình ph−ơng và nhân" đ biết sẽ làm giảm số phép nhân modulo cần thiết, để tính x mod n nhiều nhất là 2l, trong đó l là số các bit trong biễu diễn nhị phân của c. Vì l ≤ k nên có thể coi x c mod n đ−ợc thực hiện trong thời gian O(k 3). Vì thế các phép m và giải m đ−ợc thực hiện theo thời gian đa thức (nh− một hàm của k là số các bít trong một bản rõ (hoặc bản m ). Trong thuật toán “ bình ph−ơng và nhân”, ta coi rằng số mũ b đ−ợc biểu thị ở dạng nhị phân nh− sau: l-1 i b = ∑bi 2 2 i=0 b Trong đó b i = 0 hoặc 1, 0 ≤ i ≤ l-1. Thuật toán để tính z = x mod n đ−ợc mô tả ở hình 4.4. Hình 2.5 Thuật toán bình ph−ơng và nhân để tính x b mod n 1. z = 1 2. for i = l-1 down to 0 do 3. z = z2 mod n 4. if bi = 1 then z = z.x mod n Dễ dàng tính đ−ợc số các phép nhân modulo thực hiện bởi thuật toán trên. Luôn luôn phải thực hiện l phép bình ph−ơng (ở b−ớc 3). Số phép nhân trong b−ớc 4 bằng số các bit "1" trong biểu diễn nhị phân của b (số này thuộc khoảng từ 0 tới l). Bởi vậy tổng số phép nhân modulo cần thực hiện nằm trong khoảng từ l tới 2 l. Ta sẽ minh hoạ cách sử dụng thuật toán trên bằng cách quay trở lại ví dụ 4.5. Ví dụ 4.5 (tiếp):
Ta có n = 11413 và số mũ m hoá công khai b = 3533. Alice sẽ m hoá bản rõ 9726 bằng cách tính 9726 3533 mod 11413 theo thuật toán “bình ph−ơng và nhân” nh− sau: i bi z 11 1 12ì 9726 = 9726 10 1 9726 2 ì 9726 = 2659 9 0 2659 2 = 5634 8 1 5634 2 ì 9726 = 9167 7 1 9167 2 ì 9726 = 4958 6 1 4958 2 ì 9726 = 7783 5 0 7783 2 = 6298 4 0 6298 2 = 4629 3 1 4629 2 ì 9726 = 10185 2 1 10185 2 ì 9726 = 105 1 0 105 2 = 11025 0 1 11025 2 ì 9726 = 5761 Nh− vậy bản m là 5761. Cần phải nhấn mạnh rằng, những ứng dụng phần cứng hiệu quả nhất hiện thời của RSA chỉ đạt đ−ợc tốc độ m hoá chừng 600Kb/s (sử dụng các mô đun 512 bít) so với DES có tốc độ 1 Gb/s. Nói cách khác RSA chậm hơn khoảng 1500 lần so với DES. Đến đây, ta chỉ mới xét đ−ợc các phép m hoá và giải m cho RSA. Để thiết lập hệ mật RSA, ta còn phải xét việc tạo các số nguyên tố p và q (b−ớc 1), b−ớc này sẽ đ−ợc nghiên cứu ở phần sau. B−ớc 2 khá đơn giản và đ−ợc thực hiện trong thời gian O((log n) 2). Các b−ớc 3 và 4 xoay quanh thuật toán Euclide, vì thế sẽ xét qua về độ phức tạp của thuật toán này. Giả sử ta phải tính −CLN của r 0 và r 1, trong đó r 0 > r 1 . Trong mỗi b−ớc lặp đều phải tính th−ơng và phần d−, điều này có thể thực hiện đ−ợc trong thời 2 gian O((log r 0) ). Nếu tìm đ−ợc giới hạn trên cho số phép lặp thì ta sẽ có đ−ợc giới hạn cho độ phức tạp của thuật toán. Kết quả này đ đ−ợc nêu trong định lý Lamé. Định lý khẳng định rằng nếu s là số các phép lặp thì f 3+2 ≤ r 0 , trong đó fi là số Fibonacci thứ i . Vì
  1 + 5  fi =    2  Nên điều đó kéo theo s là O(log r 0). Điều này chứng tỏ rằng thời gian chạy của thuật toán Euclide là O((log n) 3) (trên thực tế, bằng các phân tích chi tiết hơn, có thể chứng tỏ rằng thời gian chạy chỉ là O((log n) 2). 4.5. Kiểm tra tính nguyên tố xác suất Để thiết lập hệ mật RSA, ta phải tạo ra các số nguyên tố ngẫu nhiên lớn (chẳng hạn có 80 chữ số). Trong thực tế, ph−ơng cách thực hiện điều này là: tr−ớc hết phải tạo ra các số ngẩu nhiên lớn, sau đó kiểm tra tính nguyên thuỷ của chúng bằng cách dùng thuật toán xác suất Monte- Carlo thời gian đa thức (chẳng hạn nh− thuật toán Miller- Rabin hoặc là thuật toán Solovay- Strasen). Cả hai thuật toán trên đều đ−ợc trình bày trong phần này. Chúng là các thuật toán nhanh (tức là một số nguyên n đ−ợc kiểm tra trong thời đa thức theo log 2n, là số các bít trong biểu diện nhị phân của n). Tuy nhiên, vẫn có khả năng là thuật toán cho rằng n là số nguyên tố trong khi thực tế n là hợp số. Bởi vậy, bằng cách thay đổi thuật toán nhiều lần, có thể giảm xác suất sai số d−ới một mức ng−ỡng cho phép (sau này sẽ thảo luận kỹ hơn một chút về vấn đề này). Một vấn đề quan trọng khác: là cần phải kiểm tra bao nhiêu số nguyên ngẫu nhiên (với kích th−ớc xác định) cho tới khi tìm đ−ợc một số nguyên tố. Một kết quả nỗi tiếng trong lý thuyết số (đ−ợc gọi là định lý số nguyên tố) phát biểu rằng: số các số nguyên tố không lớn hơn N xấp xỉ bằng N/ln N. Bởi vậy, nếu p đ−ợc chọn ngẫu nhiên thì xác suất p là một số nguyên tố sẽ vào khoảng 1/ln p. Với một mođun 512 bít, ta có 1/ln p ≈ 1/77. Điều này có nghĩa là tính trung bình, cứ 177 số nguyên ngẫu nhiên p với kích th−ớc t−ơng ứng sẽ có một số là số nguyên tố. Dĩ nhiên, nếu chĩ hạn chế xét các số nguyên lẻ thì xác suất sẽ tăng gấp đôi tới khoảng 2/177). Bỡi vậy trên thực tế, hoàn toàn có khả năng tạo đ−ợc các nguyên tố đủ lớn và do đó về mặt thực thể ta có thể thiết lập đ−ợc một hệ mật RSA. Sau đây sẽ tiếp tục xem xét điều này đ−ợc thực hiện nh− thế nào. Một bài toán quyết định là một bài toán trong đó một câu hỏi cần đ−ợc trả lời “có” hoặc “không”. Một thuật toán xác suất là một thuật toán bất kỳ có sử dụng các số ngẫu nhiên (ng−ợc lại, thuật toán không sử dụng các số ngẫu
nhiên sẽ đ−ợc gọi là một thuật toán tất định). Các định nghĩa sau có liên quan tới các thuật toán xác suất cho các bài toán quyết định. Định nghĩa 4.1 Thuật toán Monte Carlo định h−ớng “có” là một thuật toán xác suất cho một bài toán quyết định, trong đó câu trả lời “có” luôn luôn là đúng còn câu trả lời “không” có thể là sai. Thuật toán Monte Carlo định h−ớng “không“ cũng đ−ợc định nghĩa theo cách t−ơng tự. Chúng ta nói rằng, một thuật toán Monte Carlo định h−ớng “có” có xác suất sai bằng ε nếu với bất kỳ mổt tr−ờng hợp nào mà câu trả lời là “có” thì thuật toán có câu trả lời sai “không” với xác suất không lớn hơn ε (xác suất này đ−ợc tính trên mọi phép chon ngẫu nhiên, có thể thực hiên bởi thuật toán với một câu vào đU cho). Bài toán quyết định ở đây là bài toán hợp lệ số mô tả ở hình 4.5. Cần chú ý rằng một thuật toán quyết định chỉ có câu trả lời “có” hoặc “không” đặc biệt trong bài toán hợp lệ số là ta không yêu cầu thuật toán tính tích thừa số khi n là hợp lệ số. Tr−ớc tiên ta sẽ mô tả thuật toán Soloway- Strasson. Đây là một thuật toán Monte- Carlo định h−ớng “có” cho bài toán hợp số có Tr−ớc tiên ta sẽ mô tả thuật toán Soloway- Strasson. Đây là một thuật toán Monte-Carlo định h−ớng “có” cho bài toán hợp số và xác xuất sai 1/2. Bởi vậy, nếu thuật toán trả lời “có” thì n là hợp số; ng−ợc lại nếu n là hợp số thì thuật toán trả lời “có” với xác xuất tối thiểu 1/2. Hình 4.5. Bài toán hợp số. Đặc tr−ng của bài toán: một số nguyên d−ơng n ≥ 2 Câu hỏi: n có phải là hợp số không ? Hình 4.6. Bài toán về các thặng d− bậc hai. Đặc tr−ng của bài toán: cho p là một số nguyên tố lẻ và một số nguyên x sao cho 0 ≤ x ≤ p-1 Câu hỏi: x có phải là thặng d− bậc hai phép modulo p ?
Mặc dù thuật toán Miller-Rabin (ta sẽ xét sau) nhanh hơn thuật toán Soloway-Strasson (S-S) nh−ng ta sẽ xét thuật toán S-S tr−ớc vì nó dễ hiểu hơn về khái niệm, đồng thời lại liên quan tới một số vấn đề của lý thuyết số (mà ta sẽ còn dùng trong các ch−ơng trình sau). Ta sẽ xây dựng một số nền tảng sâu sắc hơn trong lý thuyết số tr−ớc khi mô tả thuật toán. Định nghĩa 4.2. Giả sử p là một số nguyên tố lẻ và x là một số nguyên, 1 ≤ x ≤ p-1. x đ−ợc gọi là thặng d− bậc hai theo modulo p nếu ph−ơng trình đồng d− y 2 ≡ x (modulo p) có một nghiệm y ∈Zp x đ−ợc gọi là thặng d− không bậc hai theo modulo p nếu x ??? 0 (mod p) và x không phải là thặng d− bậc hai theo modulo p. Ví dụ 4.6. Các thặng d− bậc hai theo modulo 11 là 1,3,4,5 và 9. Cần để ý rằng, (±1) 2=1, ( ±5) 2=3, ( ±2) 2=4, ( ±4) 2=5, ( ±3) 2=9 (ở đây tất cả các phép số học đều thực hiện trong Z 11 ). Bài toán quyết định thặng d− bậc hai đ−ợc trình bày trên hình 4.6 sẽ đ−ợc thấy một cách t−ơnngf minh nh− sau: Tr−ớc hết, ta sẽ chứng minh một kết quả- tiêu chuẩn Euler –tạo nên thuật toán tất định theo thời gian đa thức cho bài toán về các thặng d− bậc hai. Định lý 4.8. (Tiêu chuẩn Euler) Giả sử p là một số nguyên tố, khi đó x là một thặng d− bậc hai theo modulo p khi và chỉ khi: x(p-1)/2 ≡1 (mod p) Chứng minh: Tr−ớc hết giả sử rằng, x ≡y2(mod p). Theo hệ quả 4.6, nếu p là số nguyên tố thì x p-1≡1 (mod p) với mọi x ≡ 0 (mod p). Bởi vậy ta có : x(p-1)/2 ≡ (y 2)(p-1)/2 (mod p) ≡yp-1(mod p) ≡1 (mod p) Ng−ợc lại, giả sử rằng x (p-1)/2 ≡1 (mod p). Cho p là một phần tử nguyên thuỷ theo modulo p. Khi đó x ≡bi (mod p) với giá trị i nào đó. Ta có
x (p-1)/2 ≡ (b i)(p-1)/2 (mod p) ≡bi(p-1)/2 (mod p) Vì b có bậc bằng p-1 nên p-1 phải là −ớc của i(p-1)/2. Bởi vậy i là số chẵn và nh− vậy căn bậc hai của x là ±bi/2 . Định lý 4.8 sẽ dẫn tới một thuật toán thời gian đa thức cho các thặng d− bậc hai nhờ sử dụng kỹ thuật “bình ph−ơng và nhân” cho phép lấy luỹ thừa theo modulo p. Độ phức tạp của thuật toán khoảng O((log p) 3). Sau đây tiếp tục đ−a ra một số định nghĩa từ lý thuyết số: Định nghĩa 4.3 Giả sử p là một số nguyên tố lẻ. Với một số nguyên bất kỳ a ≥ 0 ,  a  ta dịnh nghĩa ký hiệu Legendre   nh− sau :  p  0 nếu a ≡ 0 (mod p)  a    = 1 nếu a là thặng d− bậc hai theo modulo p  p  - 1 nếu a là thặng d− không bậc hai theo modulo p Ta đ biết là a (p-1)/2 ≡ 1 (mod p) khi và chỉ khi a là một thặng d− bậc hai theo modulo p. Nếu a là bội của p thì rõ ràng a (p-1)/2 ≡ 0(mod p). Cuối cùng, nếu a là một thặng d− không bậc hai theo modulo p thì a(p-1) ≡ -1 (mod p) vì a p- 1≡1(mod p). Bởi vậy, ta có kết quả cho phép xây dựng một thuật toán hữu hiệu để đánh giá các ký hiệu Legendre nh− sau Định Lý 4.9.  a    (p-1)/2 Giả sử p là một số nguyên tố. Khi đó  p  ≡ a (mod p). Sau đây là một định nghĩa tổng quát hoá cho ký hiệu Legendre. Định nghĩa 4.4. Giả sử n là một số nguyên d−ơng lẻ và phân tích theo các luỹ thừa e1 ek nguyên tố của n là p 1 p K . Giả sử a ≥ 0 là một số nguyên.  a     r 
Ký hiệu Jacobi đ−ợc định nghĩa nh− sau: ei    a  K  a    = ∏     n i=1 pi  Ví dụ 4.7.  6278  Xét ký hiệu Jacobi   . Phan tích luỹ thừa nguyê n tố của 9975  9975  là : 9975 = 3 ì 5 2 ì 7 ì 19. Bởi vậy ta có :  6278   6278  6278  2  6278  6278    =        9975   3  5   7  19   2  3  2  6  8  =       = (− 1 )(− 1 )2 (− 1 )(− 1 )  3  5   7  19   a  = - 1.    a   n  Giả sử n > 1 là một số lẻ. Nếu n là nguyê n tố thi   ≡ a (n -1)/2 (mod n)  n  với a bất kì. Mặt khác nếu n là một hợp số thì đồng d− thức trên có thể đúng hoặc không. Nếu ph−ơng trình đó vẫn đúng thì a đ−ợc gọi là số giả nguyên tố Euler theo cơ số n. Ví dụ: 10 là số giả nguyên tố Euler theo cơ số 91 vì :  10    = −1=10 45 mod 91  9  Tuy nhiên có thể chứng tỏ rằng, với một hợp số lẻ n bất kỳ, sẽ có nhiều nhất một nửa các số nguyên a (sao cho 1 ≤ a ≤ n-1) là các số giả nguyên tố Euler cơ số n (xem các bài tập). Điều đó chứng tỏ rằng, việc kiểm tra tính nguyên tố theo thuật toán Soloway-Strasson đ−ợc nêu ở hình 4.7 là thuật toán Monte-Carlo định h−ớng “có”với xác xuất sai tối đa là 1/2. Đến đây vẫn ch−a xác định rõ thuật toán ttrên có theo thời gian đa thức hay không. Ta đ biết cách đánh giá a (n-1)/2 (mod n) trong thời gian đa thức O((log n) 3), tuy nhiên cần phải làm thế nào để tính các ký hiệu Jacobi một cách có hiệu quả. Vì ký hiệu Jacobi đ−ợc xác định theo các thừa số trong phân
tích của n. Tuy nhiên nếu có thể phân tích đ−ợc n thì ta đ biết nó có phải là số nguyên tố hay không, bởi vậy cách làm này sẽ dẫn tới một vòng luẩn quẩn. Hình 4.7. Thuật toán kiểm tra tính nguyên tố Solova-Strassen với số nguyên lẻ n. 1. Chọn một số nguyên ngẫu nhiên a, 1 ≤ a ≤ n-1  a    (n-1)/2 2. Nếu  n  ≡ ≡ a (mod n) thì Trả lời “ n là số nguyên tố ” Nếu không Trả lời “ n là một hợp số ” Rất may là có thể đánh giá ký hiệu Jacobi mà không cần phải phân tích n nhờ sử dụng một số kết quả của lý thuyết số, trong đó kết quả quan trọng nhất là tính chất 4 (tổng quát hoá luật t−ơng hỗ bậc hai ). Ta sẽ liệt kê mà không chứng minh các tính chất này. 1. Nếu n là một số nguyên tố lẻ và m 1 ≡ m 2 (mod n) thì:  m   m   1 = =  2   n       n  2. Nếu n là một số nguyên lẻ thì 1 nếu n ≡ ± 1 (mod 8)  2     n  = -1 nếu n ≡ ± 3 (mod 8) 3. Nếu n là một số nguyên lẻ thì  m1m 2   m1  m 2    =     n   n  n  Đặc biệt nếu m=2 kt với t là một số lẻ thì:
 m   2  k  t    =      n   n   n  4. Giả sử m và n là các số nguyên lẻ, khi đó:   n  −   nếu m ≡ n ≡ 3 (mod 4)   m  =   2      n   n    trong các tr−ờng hợp còn lại   m   Ví dụ Để minh hoạ cho việc áp dụng các tính chất trên , ta sẽ đánh  7411 giá kíhiệu Jacobi   nh− trong bảng d−ới đây. Cần chú ý là  9283 trong ví dụ này, ta đ sử dụng liên tiếp các tính chất4, 1,3 ,và 2. Nói chung, bằng cách áp dụng 4 tính chất trên, có thể tính  m  toánkí hiệu Jacobi   trong thời gian đa thức. Các phép tính số  n  học dùng ở đây chỉ là rút gọn theo modulo và phân tích ra các luỹ thừa của thuật toán đ−ợc biểu diễn d−ới dạng nhị phân thì việc phân tích ra các luỹ thừa của hai số chính là việc xác định số các số 0 tiếp sau. Bởi vậy, độ phức tạp của thuật toán đ−ợc xác định bởi số các phép rút gọn theo modulo cần tiến hành. Không khó khăn lắm có thể chứng tỏ rằng, cần thực hiện nhiều nhất là.  7411  9283    = −  theo tính chất 4  9283  7411  1872  = −   theo tính chất 1  7411  2 4 117  . = −     theo tính chất 3  7411  7411   117  = −   theo tính chất 2  7411  7411 = −   theo tính chất 4  117   40  = −   theo tính chất 1 177   2 3 5  = −     theo tính chất 3 117  117 
O(log n) phép rút gọn theo modulo. Mỗi phép có thể thực hiện trong thời gian O((log n) 2). Điều đó chứng tỏ rằng, độ phức tạp là O((log n) 3) là đa thức theo log n. Thực ra bằng các phân tích chính xác hơn, có thể chứng tỏ răng, độ phức tạp chỉ cỡ O((log n) 2). Giả sử ta đ tạo đ−ợc một số ngẫu nhiên n và đ kiểm tra tính nguyên tố của nó theo thuật toán Soloway- Strasen. Nếu chạy thuật toán m lần thì câu trả lời “n là một số nguyên tố” sẽ có mức độ tin cậy nh− thế nào? Quả là liều lĩnh nếu coi răng, xác suất này là 1-2-m. Kết luận này th−ờng đ−ợc nêu trong các giáo trình và bài báo kĩ thuật, tuy nhiên ta không thể dẫn ra theo các số liệu cho tr−ớc. Cần phải thận trọng hơn khi sự dụng các tính toán xác suất. Ta sẽ định nghĩa các biến ngẫu nhiên sau: a- Chỉ sự kiện “số nguyên lẻ n có kích th−ớc đ định là một hợp số”. b- Chỉ sự kiện “thuật toán trả lời n là số nguyên tố m lần liên tiếp” . Điều chắc chắn là prob(b | a)2 -m. Tuy nhiên xác suất mà ta thực sự quan tâm là prob(a/b), xác suất này th−ờng không giống nh− prob(b/a).
Có thể tính prob(a/b) bằng định lý Bayes (định lý2.1). Tr−ớc hết cần phải biết prob(a). Giả sử N ≤ n ≤ 2N. áp dụng định lý về số nguyên tố: các số nguyên tố(lẻ) giửa N và 2N xấp xỉ bằng: 2N/ln 2N – N/ln N ≈ N/ ln N ` ≈ n/ln n Vì có N/2 ≈ n/2 số nguyên tố lẻ giửa N và 2N, ta sẽ dùng −ớc l−ợng Prob (a) ≈ 1 – 2/ln n Sau đó có thể tính toán nh− sau: prob(ba | a)prob(a) prob(a | b) = prob(b) prob(b | a)prob(a) = prob(b | a)prob(a) + prob(b | a)prob( )a 2 prob(b | a)(1 - ) ≈ ln n 2 2 prob(b | a)(1 - ) + ln n ln n prob(b | a)(ln n - 2) = prob(b | a)(ln n - 2) + 2 2-m (ln n − )2 ≤ 2−m (ln n − )2 + 2 ln n - 2 = ln n - 2 + 2m+1 Chú ý rằng trong tính toán trên chỉ sự kiện “số nguyên lẻ ngẫu nhiên n là một số nguyên tố”. Khá thú vị nếu so sánh hai hàm sau của m (ln n − )2 ln n − 2 + 2m+1 Giả sự n ≈ 2 256 ≈ e 177 (đây là kích th−ớc của các số nguyên tố sự dụng
175 trong hệ mặt RSA). Khi đó hàm đầu tiên xấp xỉ bằng m+1 . . Ta 175+2 sẽ lập bảng cho hai hàm ứng với một số giá trị của m (xem hình4.8).
Hình 4.8. Các xác suất sai đối với phép kiểm tra Solovay- Strasen M 2-m 1 0,500 0,978 2 0250, 0,956 5 0,312.10 -1 0,732 10 0,977.10 -3 0,787.10 - 20 0,954.10 -6 0,834.10 -4 30 0,930.10 -9 0,815.10 -7 50 0,888.10 -15 0,777.10 -13 100 0,789.10 -30 0,690.10 -28 175 Mặc dù m+1 tiến tới 0 khá nhanh theo hàm mũ nh−ng vẫn 175+2 không tiến nhanh bằng 2 -m. Tuy nhiên, nếu lấy m vào cỡ 50 hoặc 100 thì các xác suất sai đó cùng qui về một l−ợng rất nhỏ. Phần này sẽ kết thúc bằng một thuật toán Monte- Carlo khác cho bài toán hợp số, đó là thuật toán Miller- Rabin (M-R) (đ−ợc coi là một phép kiểm tra giả nguyên tố mạnh). Thuật toán đ−ợc mô tả trong hình 4.9. Đây lá một thuật toán với thời gian đa thức: độ phức tạp của nó cỡ O((log n) 3) t−ơng tự nh− thuật toán S-S Thực ra trong thức tế thuật toán M-R thực hiện tốt hơn thuật toán S-S. Bây giờ chúng ta sẽ chỉ ra rằng thuật toán này không thể lời “n là một hợp số” nếu n là số nguyên tố, tức nó là một thuật toán định h−ớng “có” . Định lý 4.10 Thuật toán Miller – Rabin về các hợp số là thuật toán monte-carlo định h−ớng “có “
Hình 4.9 Thuật toán kiểm tra tính nguyên tố Miller-rabin với số nguyên lẻ n 1. Viết n-1=2 km, trong đó m là một số lẻ 2. Chọn số nguyên ngẫu nhiên a, 1 ≤ a ≤ (n-1 ) 3. Tính b=a m mod n 4. iF b ≡1 (mod n) then Trả lời “ n là số nguyên tố “ và quit 5. For i=0 to k-1 do 6. iF b ≡-1 (mod n) then Trả lời “n là số nguyên tố “ và quit Else b=b 2 mod n 7.Trả lời “ n là hợp số “ Chứng minh: Ta sẽ chứng minh bằng cách giả sử thuật toán trả lời “n là hợp số” với số nguyên tố n nào đó và nhân đ−ợc mâu thuẫt. Vì thuật toán trả lời “n là hợp số “ nên chắc chắn là a m ≡ 1(mod n). Bây giờ xét d y các giá trị b đ−ợc kiểm tra trong b−ớc 2 của thuật toán .Vì b đ−ợc bình ph−ơng trong mỗi phép lặp của vòng For nên ta sẽ kiểm tra các giá trị a m , a 2m , ,a 2k-1m . Vì thuật toán trả lời “n là hợp số” nên suy ra: 2i m a ≡ −1(mod n) với 0 ≤ i ≤ k-1 Bây giờ sử dụng giả thiết n là số nguyên tố. Theo định lý Ferma (hệ quả 4.6) ta có a 2i m ≡1(mod n) 2k −1 m vì n-1 = 2 km. Khi đó a là căn bậc hai của một modulo n = ± 1 mod n. Điều này có thể thấy rõ nh− sau: x là căn bậc hai của 1 theo modulo n khi và chỉ khi n (x-1)(x+1) Vì n là một số nguyên tố nên hoặc n (x-1)(tức là x ≡1 modun) hoặc n (x+1) (tức là x ≡-1 modun)
Ta đ có a 2k −1 m ≡ −1(mod n) bởi vậy ta phải có: a 2k −1 m ≡1(mod n) Khi dó a 2 2-k m phả i là căn bậc hai của 1. Bằng lập luận t−ong tự : a 2 1-k m ≡1(mod n) Lặp lại lập luận trên, cuối cùng ta nhận đ−ợc: am ≡ 1(mod n) điều này là mâu thuẫn, bởi vậy trong tr−ờng hợp này thuật toán phải có câu trả lời “n là số nguyên tố”. Còn một vấn đề ch−a ch−a đ−ợc xem xét là xác xuất sai của thuật toán M- R. Mặc dù không chứng minh ở đây nh−ng có thể chứng tỏ đ−ợc rằng xác xuất này nhiều nhất là ẳ. 4.6 Các ph−ơng pháp tấn công hệ mật rsa Trong phần này ta sẽ l−u tâm đến vấn đề: Liệu có các ph−ơng pháp tấn công RSA khác với ph−ơng pháp phân tích n không ? tr−ớc tiên ta thấy rằng thám m chỉ cần tính đ−ợc Φ(n) là đủ. Nếu đ biết n và Φ(n) và n là tích của 2 số nguyên tố p và q thì có thể dễ dàng phân tích đ−ợc n bằng cách giải 2 ph−ơng trình sau để tìm hai số p và q ch−a biết: n=pq Φ(n)=(p-1)(q-1) Nếu thay q=n/p và ph−ơng trình thứ 2 thì ta sẽ thu đ−ợc ph−ơng trình bậc 2 của biến ch−a biết p :
p2-(n-Φ(n) + 1)p + n=0 Hai nghiệmncủa ph−ơng trình này là p và q là các nhân tữ của n. Bởi vậy thám m biết đ−ợc Φ(n) thì anh ta có thể phân tích đ−ợc n và phá đ−ợc hệ mật.Nói cách khác, việc tính Φ(n) không dễ hơn việc phân tích n.Sau đây là một ví dụ dụ minh hoạ : Ví dụ 4.9 Giả sử thám m đả biết rằng n=84773093 và Φ(n)= 4754668. Thông tin này sẽ dẫn tới ph−ơng trình: p2-18426p+84773093=0 Giải ph−ơng trình này thu đ−ợc hai nghiệm 9539 và 8887.Đây là hai thừa số của n. 4.6.1 Số mũ giải mb Bây giờ chúng ta sẽ chứng minh một kết quả rất thú vị là một thuật toán bất kỳ để tính số mũ giải m a đều có thể đ−ợc dùng nh− một ch−ơng trình con (hay một điều kiện )trong thuật toán xác suất phân tích n .Bởi vậy việc tính a sẽ không dễ hơn việc phân tích n.Tuy nhiên, có một điều không ngoài quy luật là ta vẫn có thể phá hệ mật mà không cần tính a. Kết quả này có ý nghĩa nhiều hơn về mặt lý thuyết .Nó cho thấy rằng nếu a bị lộ thì giá trị m cũng không còn khó phân tích nữa.Nếu điều này xẩy ra thì việc Bob chọn một số mũ mới cũng chẳng có ý nghĩa; Điều cần thiết là Bob phải chọn lại n. Thuật toán mà ta sẽ mô tả là một thuật toán xác suất kiểu las vegas.Sau đây là định nghĩa của kiểu thuật toán này. Định nghĩa 4.5 Giả sử 0 ≤ ε ≤1 là một số thực.Thuật toán las vegas là một thuật toán xác suất cao cho với một tr−ờng hợp bất kỳ của bài toán i, thuật toán có thể không cho kết quả với một xác suất ε nào đó (chẳng hạn thuật toán có thể kết thúc với thông báo “ không trả lời ”).Tuy nhiên, nếu thuật toán cho lời giải thì lời giải này là đúng .
Nhân xét: Thuật toán las vegas có thể không cho câu trả lời nh−ng một câu trả lời bất kỳ mà thuật toán cho là đều là câu tra lời đúng.Ng−ợc lại, thuật toán monte-carlo luôn luôn cho câu trả lời nh−ng câu trà lời này có thể là sai. Nếu ta có một thuật toán las vegas để giải một bài toán thì đơn giản ta chỉ chạy lặp đi lặp lại thuật toán này cho tới khi nó tìm ra một câu trả lời.Xác suất để thuật toán không trả lời sau m lần liên tiếp là εm.Số lần chạy trung bình để thu đ−ợc câu tra lời thực tế là 1/ ε (Xem các bài tập ). Giả sử A là một thuật toán giả định tính số mũ giải m a từ b. Ta sẽ mô tả một thuật toán las vegas dùng A nh− một ch−ơng trình giả định (oracle) con.Thuật toán sẻ phân tích n với xác suất tối thiểu là 1/2.Bởi vậy nếu thuật toán chạy m lần thì n sẽ đ−ợc phân tích với xác suất tối thiểu là 1-1/2 m. Thuật toán đ−ợc xây dựng trên cơ sở một số nguyên tố nhất định liên quan tới các căn bậc 2 của một theo modulo n, trong đó n=pq là tích của hai số nguyên tố lẻ phân biệt ta biết rằng ph−ơng trình đồng d− x 2 ≡1(mod p) có hai nghiệm theo modulo p là x= ±1 mod p .T−ơng tự, ph−ơng trình đồng d− x2≡1(mod q) cũng có hai nghiệm là x= ±1 mod q . Vì x 2 ≡1 (mod n) khi và chỉ khi x 2≡1 (mod p) và x 2≡1 (mod q) nên suy ra x 2≡ 1 (mod n) khi và chỉ khi x= ±1 mod p và x= ±1 mod q.Bởi vậy có 4 căn bậc 2 của 1 theo modulo n và các căn này có thể tìm đ−ợc thông qua định lý phần d− china.Hai trong các nghiệm này là x= ±1 mod n; chúng đ−ợc gọi là các căn bậc hai tầm th−ờng và là các giá trị đối của nhau theo modulo n. Sau đây là một ví dụ dụ nhỏ để minh hoạ : Ví dụ 4.10 Giả sử n=403=13 ì11.Bốn căn bậc hai của một theo modulo 403 là 1,92,311 và 402.Căn bậc hai 92 nhận đ−ợc bằng cách giải hệ x ≡1 (mod 13) , x≡-1 (mod 31) theo định lý phần d− China. Nếu tìm đ−ợc không tầm th−ờng này, nghiệm không tầm th−ờng kia phải là 403-92=311.Đó là nghiệm của hệ x≡-1(mod 13), x ≡1 (mod 31). Giả sử x là căn bậc hai không tầm th−ờng của 1 modulo n. Khi đó ta có n (x-1)(x+1) nh−ng n không là −ớc của một nhân tử nào ở vế phải .Điều đó kéo theo −CLN (x+1,n) = p hoặc q(và t−ơng tự −CLN (x-1,n)=p hoặc q).Tất nhiên có thể tính
−CLN bằng thuật toán Euclide mà không cần phải biết phân tích nhân tử của n.Bởi vậy, hiểu biết về căn bậc hai không tầm th−ờng của 1 mod n sẽ làm cho việc phân tích n chỉ cần thực hiện trong thời gian đa thức. Yếu tố quan trọng này là cơ sở của nhiều kết quả quan trong mật m . Trong ví dụ dụ 4.10 ở trên, −CLN (93,403) =31 và −CLN (312,403)=13 Trên hình 4.10 trình bày thuật toán (dùng thuật toán giả định A làm ch−ơng trình con) để phân tích n bằng cách tìm một căn bậc hai không tầm th−ờng của 1 modulo n (A thực hiện tính số mũ giải m a theo số mũ m b ).Tr−ớc tiên ta sẽ đ−a ra một ví dụ để minh hoạ cho việc áp dụng thuật toán này. Ví dụ 4.11 Giả sử n=89855713, b=34986517 và a=82330933 và giá trị ngẫu nhiên w=5.Ta có : ab-1=2 3.360059073378795 Trong b−ớc 6, v=85877701 còn ở b−ớc 10 , v=1.Trong b−ớc 12 ta tính −CLN (85877702,n)=9103. Đây là một thừa số của n; thừa số kia là n/9103=9871. Bây giờ sẽ tiến hành phân tích thuật toán.Tr−ớc tiên, nhân thấy rằng nếu ta may mắn chọn đ−ợc w là bội của p hoặc q thì có thể ngay lập tức phân tích đ−ợc n.Điều này đ−ợc biểu thị ở b−ớc 2. Nếu − nguyên tố cùng nhau với n thì chúng ta sẽ tính w r , w 2r , w 4r ,. . .,bằng cách bình ph−ơng liện tiếp cho tới khi w 2r ≡1 (mod n) với giá trị t nào đó.Vì ab-1=2 sr≡0 (mod Φ(n)) Hình 4.10 Thuật toán phân tích thừa số (cho tr−ớc số mũ giải mb a). 1. Chọn w ngẫu nhiên sao cho 1 ≤ w ≤ n-1 2. Tính x= −CLN (w,n) 3. iF 1 < x < n then quit (thành công :x=p hoặc x=q) 4. Tính a=A(b) 5. Viết ab-1=2 sr, r Lợ 6. Tính v=w r mod n 7. iF v=1 (mod n) then quit (không thàmh công)
8. While v ≡ 1 (mod n) do 9. V 0=v 10. v=v 2 mod n 11. if v 0 ≡-1 (mod n) then Quit (không thành cô g) Else Tính x= −CLN (v 0+1,n) (thành công :x=p hoặc x=q) 2s r nến ta có w ≡ 1 (mod n ) Bởi vậy, vòng lặp while sẽ kết thúc sau nhiều nhất là s b−ớc lặp .kết thúc vòng lặp, ta tìm đ−ợc một giá trị v 0 sao cho 2 v0 ≡1 (mod n) nh−ng v 0≡ 1 (mod n) .Nếu v 0≡-1 (mod ,n ) thì thuật toán không thành công ; ng−ợc lại , v 0 sẽ là một căn bậc hai không tầm th−ờng của 1 modulo n và ta phân tích đ−ợc n (b−ớc 12 ). Nhiệm vụ chính còn lại bây giờ là phải chứng minh rằng, thuật toán thành công với xác suất là ẵ .Có hai cách mà theo đó thuật toán có thể không thành công khi phân tích n : 1. w r ≡ 1 (b−ớc 7) i 2. w 2 r ≡ -1(mod n) với giá trị t nào dó , 0 ≤ t ≤ s − t(b−ớc 11) Chúng ta có n+1 ph−ơng trình đồng d− để xem xét.Nếu giá trị ngẫu nhiên w là một nghiệm của ít nhất một trong các đồng d− thức này thì phép lựa chọn w này là “tồi” và thuật toán sẽ không thành công .Bởi vậy, ta sẽ chuyển sang tính số các nghiệm của mỗi đông d− thức này. Tr−ớc tiên xét đồng d− thức w r≡1 (md n).Ph−ơng pháp phân tích một đồng d− thức giống nh− cách xem xét một cách riêng rẻ các nghiệm theo modulo q .Sau đó kết hợp chúng nhờ định lý phần d− China. Cần đề ý rằng x ≡1 (mod n) khi và chỉ khi x ≡1 (mod p) và x ≡1 (mod q). Nh− vậy, tr−ớc hết ta phải xét w r≡1 (mod n) .Vì p là một số nguyên tố nên * z p là một nhóm cyclic theo định lý 4.7.Giả sử g là một phần tử nguyên thuỷ
theo modulo p.Ta có thể viết w=g u với số nguyên duy nhất u nào đó, 0 ≤ u ≤ p- 2. Khi đó ta có : w r ≡1(mod p) g ur ≡1 (mod p) (p-1) ur i j Giả sử ta biểu diễn p-1=2 p1, trong đó p 1 là một số lẻ và q-1 =2 q1, q 1 là một số lẻ. Vì Φ(n)=(p-1)(q-1) (ab-1)=2 sr nên ta có i+j s 2 p1q12 r Bởi vậy: i+j ≤s và p 1q1 r i Bây giờ điều kiện p-1  ur sẻ trở thành 2 p1 ur. Vì p 1r và r lẻ nên điều i i kiện cần và đủ là 2 u.Vì thế, u=k. 2 , 0 ≤ k ≤ p 1-1 và số các nghiệm của d− r thức w ≡1 (mod p) sẻ là p 1. Bằng lập luận t−ơng t−, ta thấy đồng d− thức w r ≡1 (mod q) sẻ có đúng q1 nghiệm.Có thể kết hợp nghiệm bất kỳ theo modulo p với nghiệm bất kỳ theo modulo q để thu đ−ợc một nghiệm duy nhất theo modulo n nhờ định lý phần r d− China. Do vậy số các nghiệm của đồng d− thức w ≡1 (mod n ) sẻ là p 1q1. 2t r Tiếp theo, xét đồng d− thức w = 1 (mod nvới) giá trị t cố định (trong đó : 0 ≤ t ≤ s-1). Tr−ớc tiên lại xét đồng d− thức theo modulo p 2i r rồi sau đo xét theo modulo q. (Để ý rằng, w = − 1 (mod n ) khi và i 2 r t t chỉ khi w = − 1 và(mod w2 pr )≡ −1(mod q). Đầu tiên ta xét w2 r ≡ −1(mod p) . Nếu viết w = g u nh− ở phần trên ta nhận đ−ợc: t g u 2 r ≡ −1(mod p) Vì g (p-1)/2 ≡ -1(mod p) nên ta có u2 tr ≡(p-1)/2(mod p-1) (p-1) ৆ (u2 tr-(p-1)/2)
2(p-1) ৆ (u2 t+1 r-(p-1)) i Vì p-1=2 p1 nên ta nhận đ−ợc i+2 t+1 i 2 p1 ৆ (u 2 r-2 p1) Loai bỏ thừa số chung ta có t+1 i+1  u2 r i  2 |  − 2   p1  Xét thấy nếu t ≥ i thì có thể là không có nghiệm do 2 i+1 ৆ 2 t+1 nh−ng 2 i+1 ৆ 2 i . Mặt khác nếu t ≤ i -1 thì u sẽ là một nghiệm khi và chỉ khi u là bội lẻ của i-t-1 2 .(chú ý rằng r/p 1 là một số nguyên lẻ). Bởi vậy, số các nghiệm trong tr−ờnh hợp này là p −1 1 ì =2 tp 2i−t−1 2 1 i T−ơng tự, đồng d− thức w2 r ≡ −1 (mod q) sẽ : - Không có nghiệm nếu t ≥ j t - Có 2 q1 nghiệm nếu t ≤ j-1 i Từ định lý phần d− China ta sẽ thấy rằng số các nghiệm của w2 r ≡ −1(mod n) là - 0 nếu t ≥ min{ i, j} 2t - 2 p1q1 nếu t ≤ min{ i, j) −1 t có thể nằm trong dải từ 0 tới s-1. Không mất tính tổnh quát giả sử i ≤ j; khi đó số các nghiệm sẽ bằng 0 nếu t ≥ i . Tổng số các lựa chọn”tồi” của w nhiều nhất là 22i 1 p q +p q (1+2 2+2 4+ +2 2i-1) = p q (1+ − ) 1 1 1 1 1 1 3  2i   2 2  = p1q1  +   3 3  i j Để ý là p-1 = 2 p1 còn q-1=2 q1. Bây giờ giả sử j ≥ i ≥1 khi đó p 1q1<n/4. Ta cũng có :
2i i+j 2 p1q1 ≤ 2 p 1q1 =(p-1)(q-1) < n Bởi vậy: 2 22t n n n p q ( + )< − = 1 1 3 3 6 3 2 Vì có nhiều nhất là (n-1)/2 phép chọn “tồi” đối với w nên điều đó có nghĩa là có ít nhất (n-1)/2 phép chọn “tốt” và vì thế xác suất thành công của thuật toán tối thiểu là 1/2. 4.6.2 .Thông tin riêng có liên quan tới các bit cửa bản rõ Xét một kết quả khác có liên quan tới thông tin về bản rõ có thể bị rò rỉ bởi phép m hoá RSA. Sau đây là hai tr−ờng hợp xét về thông tin riêng 1.Cho y=e K(x), h y tính parity(y) trong đó parity (y) chỉ bít cấp thấp của x. 2.Cho y=e K(x), h y tính half(y) trong đó half(y) =0 nếu 0 ≤ x ≤ n/2 và half (y)=1 nếu n/2 < x ≤ n-1. Ta sẽ chứng minh rằng với y=e K(x) cho tr−ớc một thuật toán bất kỳ tính parity(y) hoặc half(y) đều có thể đ−ợc dùng nh− một ch−ơng trình con để xây dựng một thuật toán tính bản x. Điều đó có nghĩa là, với một bản m cho tr−ớc, việc tính bit bậc thấp của bản rõ sẽ t−ơng đ−ơng đa thức với việc xác định toàn bộ bản rõ ! Tr−ớc hết, ta sẽ chứng minh rằng, việc tính parity(y) là t−ơng đ−ơng đa thức với việc tính half (y). Điều này rút ra từ hai đồng nhất thức đơn giản sau (xét bài tập ): halt(y)=parity(y x e K(2) mod n) (4.1) -1 parity(y)=half(y x e K(2 )mod n) (4.2) và từ quy tắc nhận e K(x1) e K(x2)=e K(x1x2) Ta sẽ chỉ ra cách tính x=d K(y) theo một thuật toán giả định cho tr−ớc để tính half(y). Thuật toán đ−ợc trình bày trên hình 4.11 .Trong các b−ớc 2-4 ta tính : i i yi = half(y x (e K(2)) )=half(e K(x x2 ))
với 0 ≤ x ≤ log 2 n . Nhận thấy rằng:  n  half (e K(x))= 0 ⇔ x ∈  ,0   2   n  n 3n  half (e K(2x)=0 ⇔ x ∈  ,0  U  ,   4  2 4   n  n 3n  n 5n  3n 7n  half (e (4x))= 0 ⇔ x ∈ ,0  ,  ,  ,  K  8 U 4 8 U 2 8 U  4 8  Bởi vậy ta có thể tìm theo kỹ thuật tìm tìm kiếm nhị phân (đ−ợc làm trong các b−ớc 7-11). D−ới đây là một ví dụ nhỏ để minh hoạ Ví dụ 4.12 Giả sử n=1457, b=779 và ta có bản m y=772. e K(2) đ−ợc tính bằng 946. Giả giử rằng (sử dụng thuật toán giả định đối với half(y)) . ta nhận đ−ợc các giá trị y i sau theo b−ớc 3 thuật toán: Hình 4.11.Giả mb bản mb RSA với một thuật toán giả định tính half(y) cho tr−ớc 1. Ký hi ệu k= log 2n 2. For i=0 to k do 3. y i = half (y) 4. y=(y ìeK(2)) mod 2 5. l o=0 6. hi=n 7. for i=0 to k do 8. mid=(hi+lo)/2 9. if y i=1 then lo=mid else hi=mid 10. x= hi  Hình 4.12. Phép tìm kiếm nhị phân để giải mb RSA.
i lo mid hi 0 0.00 728.50 1457.00 1 728.50 1092.75 1457.00 2 728.50 910.62 1092.75 3 910.62 1001.69 1092.75 4 910.62 956.16 1001.69 5 956.16 978.92 1001.69 6 978.92 990.00 1001.69 7 990.30 996.00 1001.69 8 996.00 998.84 1001.69 9 998.84 1000,26 1001.26 10 998.84 999.55 1000.26 998.84 999.25 999.55 i ৆0 ৆ 1 ৆ 2 ৆ 3 ৆ 4 ৆ 5 ৆6 ৆ 7 ৆ 8 ৆ 9 ৆ 10 yi ৆1 ৆ 0 ৆ 1 ৆ 0 ৆ 1 ৆ 1 ৆ 1 ৆ 1 ৆ 1 ৆ 0 ৆ 0 Sau đó tiến hành tìm kiếm nhị phân theo hình 4.12. Bản rõ tìm thấy là x= ৆999.55 ৆=999. 4.7. Hệ MậT RABiN Trong phần này sẽ mô tả hệ ma trận Rabin. Đây là hệ mật có độ an toàn cao về mặt tính toán chống lại đ−ợc cách tấn công bản rõ lựa chọn và không có khả năng phân tích đ−ợc n=pq(hệ đ−ợc trình bày trong hình 4.13). Chúng ta sẽ chỉ ra rằng, hàm m hoá e k không phải là một đơn ánh, vì thế phép giải m không thể thực hiện đ−ợc một cách xác định. Thực tế có 4
bản rõ có thể ứng với một bản m bất kỳ cho tr−ớc. Chính xác hơn, giả sử w là một trong 4 căn bậc hai của một modulo n. Giả sử x Z n. Khi đó có thể kiểm tra các ph−ơng trình sau:   B  B    B  B   B  B       ek w x +  −  = w x +  −  w x +  +    2  2    2  2   2  2   B 2  B  2 = w2  x +  −    2   2  B 2 B 2 = x 2 + Bx + − 4 4 = x 2 + Bx = ek ()x (Cần chú ý là tất cả các phép tính số học đều thực hiện trong Z n, còn phép chia cho 2 và 4 giống nh− phép nhân 2 -1và 4 -1 theo modulo n ). Hình 4.13. Hệ mật Rabin Giả sử n là tích của hai số nguyên tố phân biệt p và q, p.q ≤ 3 (mod 4). Giả sử p = C= Zn và ta xác định K={(n , p , q , B): 0 ≤ B ≤n-1} Với K = (n , p , q , B) ta định nghĩa: ek(x) = x(x+B) mod n và B 2 B d ()y = + y − K 4 2 các giá trị n và B đ−ợc công khai trong khi p và q đ−ợc giữ kín. Bốn bản rõ m hoá thành e K(x) là x, -x –B, w(x+B/2) và -w(x+B/2), trong đó w là một căn bậc hai không tầm th−ờng của 1modulo n. Nói chung Bob không có cách nào để xác định bản nào trong bốn bản rõ có thể này là bản rõ đúng, trừ phi bản rõ có đủ độ d− để loại bỏ ba trong bốn bản rõ đó.
Bây giờ ta xem xet bài toán giải m theo quan điểm của Bob. Anh ta đ có bản m y và muốn xác định x sao cho: x2+ bx ≡ y(mod n) Đây là một ph−ơng trình bậc hai theo giá trị x ch−a biết. Ta có thể loại bỏ số hạng tuyến tính bằng phép thế x 1=x+B/2 (Hay x = x 1- B/2). Khi đó ph−ơng trình trên có dạng B 2 B 2 x 2 − Bx + + Bx − − y ≡ 0()mod n 1 1 4 1 2 hay B 2 x 2 ≡ + y()mod n 1 4 B 2 Nếu đặt C = + y thì có thể viết lai ph−ơng trình đồng d− nh− sau: 4 x1 ≡ C (mod n) Nh− vậy phép giải m sẽ chỉ còn là thực hiện phép khai căn bậc hai theo modulo n. điều này t−ơng đ−ơng với việc giải ph−ơng trình đồng d− sau: 2 x1 ≡ C (mod p) 2 x1 ≡ C (mod q) (Có hai căn bậc hai của C modolo p và hai căn bậc của C theo modolo q. Bằng cách dùng định lý phần d− China, các nghiệm này có thể đ−ợc kết hợp để tạo nên bốn nghiệm theo modulo n). Có thể dùng tiêu chuẩn Eucler để xác định xem C có phải là một thặng d− bậc hai theo modulo p (và modulo q) hay không . Trên thực tế, C là một thặng d− bậc hai theo modulo p và modulo q nếu phép m hoá đ−ợc thực hiện đúng. Tuy nhiên tiêu chuẩn Eucler không giúp chúng ta tìm đ−ợc các căn bậc hai của C. Nó chỉ ra một câu trả lời “Có” hoăc “Không”.
Khi p ≡ 3 (mod 4), ta có một công thức đơn giản để tính các căn bậc hai của các thặng d− bậc hai theo modulo p. Giả sử C là một thặng d− bậc hai và p ≡ 3 (mod 4) . Khi đó ta có: (± C (p+1)/4 )2 ≡ C (p+1)/2 (mod p) ≡ C (p-1)/2 C (mod p) ≡ C(mod p) ở đây ta lại một lần nữa sử dụng tiêu chuẩn Eucler, hai tiêu chuẩn này phát biểu rằng, nếu C là một thặng d− bậc hai theo modulo p thì C (p+1)/2 ≡ 1( mod p ). Vì thế , hai căn bậc hai của C modulo p là ±C (p+1)/4 mod p. T−ơng tự, hai căn bậc hai của C modulo q là ±C (p+1)/4 mod q. Sau đó ta có thể thu đ−ợc bốn căn bậc hai của x 1 của C modulo n bằng cách dùng định lý phần d− China. Nhận xét: Một điều lý thú là với p ≡1 (mod 4), ng−ời ta ch−a biết đ−ợc một thuật toán tất định theo thời gian đa thức nào để tính căn bậc hai của các thặng d− bậc hai theo modulo p . Tuy nhiên, vẫn có thuật toán Las Vegas với thời gian đa thức để tính nó . Một khi đ xác định bốn giá trị có thể của x 1, ta tính x từ ph−ơng trình x=x 1-B/2 để tìm đ−ợc bốn bản rõ có thể. Điều này dẫn đến công thức giải m sau: B 2 B d ()y = − y − K 4 2 Ví dụ 4.13 Ta xẽ minh hoạ các thủ tục m hoá và giải m đối với hệ mật Rabin một ví dụ nhỏ. Giả sử n=77=7 ì11 và B=9. Khi đó hàm m hoá là 2 eK(y)=x +9x mod 77 và hàm giải m là
d K (y) = 1+ y − 43 mod 77 Giả sử Bob muốn giải m bản m y=22. Điều cần thiết tr−ớc tiên là tìm các căn bậc hai của 23 theo modulo 7 và modulo 11. Vì cả 7 va11 đều đồng d− với 3 modulo 4 nên ta có 23 (7+1)/4 ≡ 22 ≡ 4 mod 7 và 23 (11+1)/4 ≡ 1 3 ≡ 1 mod 7 Sử dụng định lý phần d− China, ta sẽ tính đ−ợc bốn căn bậc hai của 23 theo modulo 77 là ±10, ± 32 mod 77 . Cuối cùng bốn bản giõi có thể là : 10- 43 mod 77=44 67- 43 mod 77=24 32- 43 mod 77=66 45- 43 mod 77= 2 Có thể kiểm tra lại rằng, mỗi một bản rõ này đều đ−ợc m hoá thành một bản m 22. Bây giờ chúng ta xẽ thảo luận về độ mật của hệ Rabin. Ta xẽ chứng minh rằng một thuật toán giải m giả định A có thể đ−ợc dùng nh− một ch−ơng trình con trong một thuật toán Las Vegas để phân tích modulo n với xác suất tối thiểu bằng 1/2. Thuật toán này đ−ợc mô tả ở hình 4.14. Có một số điểm cần đ−ợc giải thích ở đây. Tr−ớc hết ta thấy rằng  B  y = e r −  K  2  Hình 4.14. Phân tích modulus của rabin với một ch−ơng trình con giải m cho tr−ớc. 1. Chọn một số ngẫu nhiên r , 1 ≤ r ≤ n-1 2. Tính y = r 2 - B2/4 mod n 3. Gọi ch−ơng trình con A(y) để tìm bản giải m x 4. Tính x 1 = x+B/2 5. if x 1 ≡ ± r (mod n) then quit (không thành công) else −CLN (x 1+r,n)=p hoặc q (thành công)
2 bởi vậy giá trị x sẽ thu đ−ợc ở b−ớc 3. Tiếp theo xét b−ớc 4. Nhận thấy rằng x 1 2 ≡ r (mod n). Điều đó dẫn tới x 1 ≡ ±r (mod n) hoặc x 1 ≡ ±ωr (mod n), trong đó ω là một trong các căn bậc hai không tầm th−ờng của 1 modulo n. Trong tr−ờng hợp thứ hai ta có : n(x 1-r )(x 1+r) song n không phải là −ớc của một thừa số nào ở vế phải. Bởi vậy, việc tính −CLN (x 1 +r,n)(hoặc −CLN (x 1-r, n)) phải dẫn tới hoặc p hoặc q, và nh− vậy phép phân tích n đ−ợc hoàn thành. Ta sẽ tính xác suất thành công của thuật toán này trên tất cả (n-1) phép chọn ngẫu nhiên r. Với hai thặng d− khác không r 1 và r 2 , định nghĩa: 2 2 r1 ~ r 2 ⇔ r 1 ≡ r 2 (mod n) Dễ dàng thấy rằng r ~ r với mọi r, r 1 ~ r 2 cũng có nghĩa là r 2 ~ r 1; r 1 ~ r 2 và r2 ~ r 3 thì r 1 ~ r 3 . Điều đó cho ta thấy rằng quan hệ ~ là một quan hệ t−ơng đ−ơng. Các lớp t−ơng đ−ơng của Z n\{0} đều có bốn phần tử, lớp t−ơng đ−ơng chứa r là tập [r] = { ±r, ±wr (mod n)} trong đó ω là căn bậc hai không tầm th−ờng của 1 modulo n. Trong thuật toán đ−ợc trình bày ở hình 4.14, hai giá trị r bất kỳ trong cùng một lớp t−ơng đ−ơng sẽ dẫn tới cùng một giá trị y. Bây giờ xét giá trị x thu đ−ợc từ ch−ơng trình con A khi đ biết y. Ta có: [y]={ ±y, ±wy} Nếu r= ±y thì thuật toán không thành công; trong khi nếu r=±wy thì thuật toán sẽ thành công. Vì r đ−ợc chọn ngẫu nhiên, nên một giá trị bất kỳ trong bốn giá
trị có thể đều cùng khả năng. Ta kết luận rằng xác suất thành công của thuật toán là 1/2. Điều thú vị là hệ mật rabin là an toàn đối với ph−ơng pháp tấn công bản rõ chọn lọc, mh−mg hệ này lại hoàn toàn không an toànđối với ph−ơng pháp tấn công bảm m chọn lọc. Thuật toán ở hình 4.14, phần dùng để chứng minh sự an toàn đối với phép tấn công bản rõ chọn lọc cũng có thể đ−ợc dùng để phá hệ mật Rabin khi thực hiện tấn công bản m chọn lọc!. Trong ph−ơng pháp tấn công bản m chọn lọc, ch−ơng trình con A đ−ợc thay bằng thuật toán giải m của Bob. 4.8. Các thuật toán phân tích thừa số. Đ có một khối l−ợng khổng lồ các tìa liệu về các thuật toán phân tích thừa số và việc nghiên cứu kỹ l−ỡng sẽ đòi hỏi phải có một cuốn sách dày hơn quyển sách này. ở đây chỉ cố gắng đ−a ra một cái nhìn khái quát bao gồm việc thảo luận sơ l−ợc về các thuật toán phân tichs thừa số tốt nhất hiện thời và cách sử dụng chúng trong thực tế. Ba thuật toán hiệu quả nhất trên các số thật lớn là sàng bậc hai, thuật toán đ−ờng cong elliptic và sàng tr−ờng số. Các thuật toán nổi tiếng khác (những thuật toán toán có tr−ớc) bao gồm ph−ơng pháp ρ và thuật toán p-1 của Pollard, thuật toán p+1 của Williams, thuật toán liên phân số và dĩ nhiên cả những phép chia thử. Trong toàn bộ phần này, chúng ta cỏìng số nguyên n cần phân tích ra thừa số là một số lẻ. Phép chia thử bao gồm việc chia n cho từng số nguyên lẻ cho tới [ n ] . Nếu n < 10 12 thì đây là một ph−ơng pháp phân tích thừa số hợp lý một cách hoàn hảo, tuy nhiên với n lớn hơn nói chung ta phải dùng các kỹ thuật tinh tế hơn. 4.8.1. Ph−ơng pháp p-1 Thuật toán p-1 của Pollar (đ−a ra vào năm 1947) là một thí dụ về một thuật toán đơn giản đơn khi đ−ợc áp dụng với các số nguyên lớn. Thuật toán này (trình bày trên hình 4.15) có hai đầu vào: số nguyên lẻ n cần đ−ợc phân tích và một cận B. Có thể mô tả thuật toán nh− sau:
Hình 4.15. Thuật toán phân tích thừa số p-1. Đầu vào: n và B 1. a=2 2. For j=2 to B do a = a j mod n 3. d = −CLN (a-1,n) 4. if 1 < d < n then d là một thừa số của n (thành công) else không tìm đ−ợc thừa số của n (không thành công) Giả sử p là −ớc mhuyên tố của n và q ≤ B , với mỗi mũ nguyên tố p (p- 1). Khi đó (p-1) B! ở cuối vòng lặp for (b−ớc 2) a ≡ 2 B! (mod n) nên a ≡ 2 B! (mod p) vì p n. nên theo định ý Fermat ta có : 2p-1 ≡ 1 (mod p) Vì (p-1) B! nên a ≡ 1 (mod p) (trong b−ớc 3). Bởi vậy ở b−ớc 4 p (a-1) và p n, do đó pd = −CLN (a-1,n) Số nguyên d sẽ là −ớc không tầm th−ờng của n (trừ phi a= 1 ở b−ớc 3). Sau khi đ tìm đ−ợc d, ta sẽ tiếp tực phân tích d và n/d nếu chúng là hợp số. Ví dụ 4.14.
Giả sử n = 15770708441. Nếu áp dụng thuật toán p-1 với B = 180 thì sẽ thấy rằng a = 11620221425 ở b−ớc 3, còn d đ−ợc tính bằng 135979. Trên thực tế, phấn tích đầy đủ n thành các −ớc nguyên tố là: 15770708441 = 135979 ì 115979 Trong tr−ờng hợp này, phép phân tích sẽ thành công do 135978 chỉ gồm các thừa số nguyên tố nhỏ: Vì thế 135978 = 2 ì 3 ì131 ì 173 nếu lấy B ≥ 173 thì chắc chăn rằng 135978 B! nh− mong muốn. Trong thuật toán có (B-1) luỹ thừa theo modulo, mỗi luỹ cần nhiều nhất là 2log 2B phép nhân modulo dùng thuật toán bình ph−ơng và nhân. Việc tính −ớc chung lớn nhất có thể thực hiện trong thời gian O((log n) 3) bằng thuật toán Euclide. Bởi vậy, độ phức tạp của thuật toán là O(B logB (log n) 2 +(log n) 3). Nếu B là O((log n) i) với một số nguyên i xác định nào đó thì thuật toán thực sự là thuật toán thời gian đa thức, tuy nhiên với phép chọn B nh− vậy, xác suất thành công sẽ rất nhỏ. Mặt khác, nếu tăng kích th−ớc của B lên thật lớn (chẳng hạn tới n ) thì thuật toán sẽ thành công nh−ng nó sẽ không thực hiện nhanh hơn phép chia thử. Nh− vậy, điểm bất lợi của thuật toán này là nó yêu cầu n phải có −ớc nguyên tố p sao cho (p-1) chỉ các thừa số nguyên tố bé. Ta có thể dễ dàng xây dựng đ−ợc hệ mật RSA với modulus n= pq hạn chế đ−ợc việc phân tích theo ph−ơng pháp này. Tr−ớc tiên tìm một số nguyên tố lớn p 1 sao cho p= 2p 1+1 cũng là một số nguyên tố và một số nguyên tố lớn q 1 sao cho q= 2q 1+1 cũng là một số nguyên tố (nhờ dùng một trong các thuật toán kiểm tra tính nguyên tố Monte-Carlo nêu trong phần 4.5). Khi đó modulo của RSA n= pq sẽ chống đ−ợc cách phân tích theo ph−ơng pháp p-1. Thuật toán đ−ờng cong elliptic mạnh hơn (đ−ợc Lenstra xây dựng vào những năm 1980) trên thực tế là sự tổng quát hoá của ph−ơng pháp p-1. Ta sẽ không thảo luận về lý thuyết ở đây mà chỉ nhấn mạnh rằng, thành công của ph−ơng pháp đ−ờng cong elliptic tuỳ thuộc vào tình huống t−ơng tự : một số nguyên “gần với” p chỉ có các thừa số nguyên tố bé. Trong khi ph−ơng pháp p- 1 phụ thuộc vào quan hệ trong Z p thì ph−ơng pháp đ−ờng cong elliptic phụ thuộc vào các nhóm xác định trên các đ−ờng cong elliptic theo modulo n.
4.8.2. Thuật toán Dixon và sàng bậc hai Thuật toán Dixon đ−ợc xây dựng trên ý t−ởng đơn giản mà ta đ thấy trong hệ mật Rabin. ý t−ởng đó là: nếu tìm đ−ợc x ≡ ±y (mod n) sao cho x2≡y2 (mod n) thì −CLN (x-y,n) là −ớc không tầm th−ờng của n. Ph−ơng pháp này sử dụng cơ sở nhân tử là một tập B chứa các số nguyên tố bé. Tr−ớc tiên ta nhận đ−ợc một vài số nguyên x sao cho tất cả các thừa số nguyên tốcủa x 2 (mod n) nằm trong cơ sở B (cách thực hiện điều này sẽ đ−ợc thảo luận sau). ý t−ởng thực hiên ở đây là lấy tích của một vài giá trĩ sao cho mỗi số nguyên tố trong cơ sở đ−ợc sử dụng một số chẵn lần. Điều này dẫn đến một đồng d− thức dạng mong muốn x 2 ≡ y 2 (mod n) mà ta hy vọng sẽ đ−a đến việc phân tích n. Ta sẽ minh hoạ bằng một ví dụ đ đ−ợc dự tính kỹ l−ỡng. Ví dụ 4.15 Giả sử n=15770708441(giá trị n này đ dùng trong ví dụ 4.14). Giả sử b = {2,3,5,7,11,13}. Xét ba đồng thức sau: 8340934156 2 ≡ 3 ì 7 (mod n) 12044942944 2 ≡ 1 ì 7 ì 13 (mod n) 2773700011 2 =2 ì 3 ì 13 (mod n) Nếu lấy tích của ba đồng d− thức trên: (8340934156 ì 2044942944 ì2773700011) 2 ≡(2 ì 3 ì 7 ì 13) 2 (mod n) Rút gọn các biểu thức bên trong các dấu ngặc theo modulo n, ta có: 9503435785 2 ≡ 546 2 (mod n) Sau đó tính: −CLN (9503435785-546, 15770708441)=115759 Ta thấy 115759 là một thừa số của n. Giả sử B = {p 1, . . . .p B}là một cơ sở nhân tử. Giả sử c lớn hơn B một chút (chẳng hạn C=B+10) và giả sử ta đ có C đồng d− thức: 2 α1j α2j αBj xj ≡ p 1 ì p 2 ì . . . ì p B (mod n) với 1 ≤ j ≤ C. Với mỗi j xét véctor : B aj = ( α1j mod 2, α2j mod 2, . . ., αBj mod 2) ∈ (Z 2)
Nếu có thể tìm đ−ợc một tập con các a j sao cho tổng theo modulo 2 là vector (0,. . ., 0) thì tích của các x j t−ơng ứng sẽ sử dụng mỗi nhân tử trong B một số chẵn lần. Ta sẽ minh hoạ bằng cách trở lại ví dụ 4.15. 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ì bảo đảm để một đồng d− thức cho tr−ớc bất kỳ sẽ tạo đ−ợc phân tích n. Khoảng 50% thuật toán cho ra x ≡ ±y (mod n). Tuy nhiên nếu C > B+1 thì có thể nhận đ−ợc một vài đồng d− thức nh− vậy. (Nảy sinh từ các phụ thuộc tuyến tính khác của các a j). 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 lại là phải làm thế nào để nhận đ−ợc các số nguyên x j mà 2 các giá trị x j mod n có thể phân tích hoàn toàn trên cơ sở B. Một vài 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 x j=j + [ n ]
,j=1,2 Tên “sàng bậc hai” lấy từ thủ tục sàng (không mô tả ở đây) dùng để xác định các x j phân tích đ−ợc trên B. ở đây dĩ nhiên là một sự thoả hiệp: nếu B = | 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 x j trên B. Tuy nhiên khi B càng lớn thì ta càng phải gom nhiều đồng d− thức hơn tr−ớc khi có thể tìm đ−ợc một quan hệ phụ thuộc. Lựa chọn tối −u cho B xấp xỉ bằng e ln n ln ln n và điều này dẫn đến thời gian thực hiện cỡ O(e(1+O )1( ln n ln ln n ) ) Sàng tr−ờng số là thuật toán phân tích mới hơn (từ cuối những năm 80) Thuật toán này cũng phân tích n bằng cách xây dựng một đồng d− thức x 2 ≡ y 2 (mod n), song nó đ−ợc thực hiện bằng các tính toán trên vành các số đại số. 4.8.3.Các thuật toán phân tích trên thực tế. Thời gian chạy tiệm cận của các thuật toán sàng bậc hai, đ−ơng cong elliptic và sàng tr−ờng số nh− sau: (1+O )1( ln n ln ln n ) Sàng bậc hai O(e ) Đ−ờng cong elliptic O(e(1+O )1( 2 ln p ln ln p ) ) ()1,92+O )1( (ln n) /1 3 (ln ln n)2 / 3 Sàng tr−ờng số O(e ) trong đó O(1) là hàm của n, hàm này tiến tới 0 khi n ∞ và p là thừa số nguyên tố nhỏ nhất của n. Trong tr−ờng hợp xấu nhất p ≈ n , thời gian chạy tiệm
cận của các thuật toán đ−ờng cong elliptic và sàng bậc hai cơ bản nh− nhau. Tuy nhiên trong tr−ờng hợp này, ph−ơng pháp sàng bậc hai nói chung trội hơn ph−ơng pháp đ−ờng cong elliptic. Ph−ơng pháp đ−ơ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 ph−ơng pháp đ−ờng cong elliptic là tham số Fermat (2 2048 -1) (đ−ợc Brent thực hiện năm 1988) . Để phân tích các modulo RSA (trong đó n=pq, p và q là các số nguyên tố có cùng kích th−ớc), sàng bậc hai là một thuật toán thành công nhất hiện nay. Sau đây là một số kết quả quan trọng. Vào năm 1983, thuật toán sàng bậc hai đ phân tích thành công một 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). Quá trình này tiếp tục trong những năm 80 và đến năm 1989 đ có thể phân tích đ−ợc các số có tới 106 chữ số theo ph−ơng pháp 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− điện tử”). Gần đây hơn, 4/1994 Atkins, Graff, Lenstra và Leyland đ phân tích đ−ợc một số 129 chữ số (đ−ợc gọi là RSA-129) nhờ sử dụng sàng bậc hai (các số RSA-100, RSA-110, ,RSA-500 là một danh sách các modulo RSA đ−ợc công bố trên internet nh− là sự thách đố cho các thuật toán phân tích. Mỗi một số RSA-d là một số d chữ số, số này là tích của hai số nguyên tố có kích th−ớc xấp xỉ nhau). Việc phân tích số RSA-129 cần hàng trăm tính toán với máy tính 5000 MiPS (triệu lệnh/s) đ−ợc thực hiện bởi 600 nhà nghiên cứu trên toàn thế giới. Sàng tr−ờng số là một thuật toán mới nhất trong ba thuật toán toán. Nó có vẻ có tiềm năng lớn do thời gian chạy tiệm cận của nó nhanh hơpn cả hai thuật toán trên. Thuật toán này hiện vẫn còn trong thời kì nghiên cứu, tuy nhiên ng−ời ta đ dự đoán là sàng tr−ờng số phải chứng tỏ là nhanh hơn với các số có trên 125-130 chữ số. Năm 1990, Lenstra, Manase và Pollaid đ dùng sàng tr−ờng số để phân tích (2 512 - 1) thành ba số nguyên tố có 7, 49 và 99 chữ số. 4.9. chú giải và tài liệu dẫn ý t−ởng về mật m khoá công khai đ đ−ợc Diffie và Hellman nêu ra vào 1976. Mặc dù [HD 76A] là tài liệu đ−ợc trích dẫn nhiều nhất những bài báo
Hội nghị [DH 76] thực tế đ xuất hiện sớm hơn một chút. Hệ mật RSA đ−ợc Rivest, Shamis và Adleman [RSA 78] phát minh. Hệ mật Rabin đ−ợc mô tả trong [RA 79]: một hệ t−ơng tự với phép giải m không mập mờ đ đ−ợc Willians tìm ra trong [Wi 80]. Bạn đọc nếu tham khảo [Di 92] là một bài báo tổng quát và mặt m khoá công khai của Diffie. Phép thử Solovay- Stassen lần đầu tiên mô tả trong [SS 77]. Phép thử Miller- Rabin đ−ợc nêu trong[Mi 76] và [Ra 80]. Thảo luận của chúng ta về các xác suất sai dựa trên các nhập xét của Brassard và Bratly [BB 88A, ξ 8.6] (cũng có thể trong[BBCGP 88]. Các cận tối nhất hiện thời về xác suất sai của thuật toán Miller- Rabin có thể tìm thấy trong [DLP 93]. Nội dung của phần 4.6 dựa trên quan điểm của Salomaa [SA 90, các trang 143-154]. Phép phân tích n với số mũ giải m cho tr−ớc đ−ợc nêu trong [DE 84]: các kết quả về thông tin riêng bị lộ bởi RSA lấy từ [GMT 82]. Nh− đ nói trên, đ có rất nguồn tài liệu về các thuật toán phân tích. Pomerance [Po 90]là tổng quát về phếp phân tích. Lenstra và Lenstra [LL 90] là một báo cáo hay là về các thuật toán lý thuyết nói chung. Bressoud [Br 89] là một giáo trình sơ cấp về phép phân tích thừa số và phép kiểm tra tính nguyên tố. Các giáo trinh về mật m có chú trọng tới lý thuyết số là các sách của Koblitz [Ko 87] và của Kranakis [Kr 86]. Còn sách của Lenstra và Lenstra [LL 93] là một chuyên thảo tốt về sàng tr−ờng số. Các bài tập 4.7- 4.9 cho một số ví dụ về trục trặc trong giao thức (protocol). Về vấn đề này có thể xem một bài báo rất hay của Moore [Mo 92]. Bài tập 4.1. H y dùng thuật toán Euclide mỡ rộng để tính các phần tử nghịch đảo rau: a) 17 -1 mod 101 b) 357 -1 mod 1234 c) 3125 -1 mod 9987 4.2. Giải hệ ph−ơng trình đồng d− sau: x ≡ 12 (mod 25) x ≡ 9 (mod 26)
x ≡ 23 (mod 27) 4.3. Giải hệ ph−ơng trình đồng d− sau 13x ≡ 4 (mod 99) 15x ≡ 56 (mod 101) gợi ý: tr−ớc tiên h y dùng thuật toán Euclide mỡ rông rồi áp dụng định lý phần d− của China. 4.4. Ta nghiên cứu một số tính chất của các căn nguyên thuỷ a) 97 là một số nguyen tố. H y chứng minh rằng x ≠ 0 là một căn nguyên thuỷ theo modulo 97 khi và chỉ khi x32 ≡ 1 (mod 97) và x 48 ≡ 1 (mod 97) b) H y dùng ph−ơng pháp này để tìm căn nguyên thuỷ nhỏ nhất theo modulo 97. c) Giả sử p là một số nguyên tố và p-1 có phần tích ra các mũ nguyên tố sau : n ei p −1= ∏ pi i=1 ở đây p i là các số nguyên tố khác nhau. H y chứng minh tỏ rằng x ≠ 0 là một căn nguyên thuỷ theo modulo p khi và chỉ khi (p-1)/p x i ≡ 1 (mod p ) với 1 ≤ i ≤ n 4.5. Giả sử n =pq, p và aq là các số nguyên tố lẻ phân biệt vad ab ≡ 1 (mod (p- 1)(q-1)). Phép toán m hoá RSA là e(x) = x b mod n và phép toán giải m là d(y) = y a mod n. * Ta đ chứng tỏ rằng d(e(x)) = 1 nếu x ∈ Z n . H y chứng tỏ rằng khẳng định trên là đúng đối với bất kỳ x ∈ Z n. Chỉ dẫn: H y dùng kết quả : x 1 ≡ x 1 (mod pq) khi và chỉ khi x 1 ≡ x 1 (mod p) và x 1 ≡ x 1(mod q). Điều này rút ra từ định lý phần d− China. 4.6. Hai ví dụ về bản m RSA đ−ợc nêu ở các bảng 4.1 và bảng 4.2. Nhiệm vụ của bạn là phải giải m chúng. Các tham số công khai của hệ thống là n =18923 và b = 1261 (bảng 4.1) và n = 31313, b = 4913 (với bảng 4.2). Phép giải mả cáo thể thực hiện nh− sau. Tr−ớc hết hỹ phân tích n (điều này khá dể vì
n quá nhỏ). Sau đó tính số mũ a từ φ(n) và cuối cùng sẽ giải m bản m . H y dùng thuật toán bình ph−ơng và nhân để lấy luỹ thừa theo modulo n. Bảng 4.1 Bản mb RSA 12423 11524 7243 7459 14303 6127 10964 16399 9792 13692 14407 18817 18830 13556 3159 16647 5300 13951 91 8986 8007 13167 10022 17213 2264 9553 18194 3830 2664 13998 12501 18873 13236 5300 13951 8850 12129 6091 18110 3332 15061 12347 7817 7946 11675 13924 13892 18031 2620 6276 8500 201 8850 11178 16477 10161 3533 13842 7537 12259 18110 44 2364 15570 3460 9886 8687 4481 11231 7547 11383 17910 12867 13203 5102 4742 5053 15407 2976 9330 12192 56 2471 14334 841 13995 13297 8186 2430 9741 11675 242 6686 738 13874 8186 7913 6246 14301 1144 9056 15967 7328 13203 796 195 9872 16979 15404 14130 9105 2001 9792 14251 1498 11296 1105 4502 16979 1105 56 4118 11302 5988 3363 15827 6928 4191 4277 10617 874 13211 1182 3090 18110 44 2364 15570 3460 9886 9988 3798 1158 9872 16979 15404 6127 9872 3652 14838 7437 2540 1367 2512 14407 5053 1521 297 10935 17137 2186 9433 13293 7555 13618 13000 6490 5310 18676 4782 11375 446 4165 11634 3846 14611 2364 6789 11634 4493 4063 4576 17955 7965 11748 14616 11453 17666 925 56 4118 18031 9522 14838 7437 3880 11476 8305 5102 2999 18628 14326 9175 9061 650 18110 8720 15404 2951 722 15334 841 15610 2443 11056 2186 Để chuyển bản rõ trở về văn bản tiếng Anh thông th−ờng, bạn cần phải các ký tự đ đ−ợc “m hoá” thành các phần tử trong Z n nh− thế nào. Mỗi phần tử của Z n sẽ biểu thị ba ký tự nh− trong các ví dụ sau: DOG 3 ì 26 2 + 14 ì 26 +6 = 2398 CAT 2 ì 26 2 + 0 ì 26 + 19 = 1371 ZZ 25 ì 26 2 + 25 ì 26 + 25 = 17575 B−ớc cuối cùng trong ch−ơng trình của bạn là làm ng−ợc lại quá trình trên.
Bản rõ đầu lấy trong cuốn “The diary of Samuel Mảchbankls” của Robertson Davies, 1947. Bản rõ thứ hai lấy từ cuốn “Lake Wobegon Days” của Garrison Keillor, 1985. 4.7. Bài tập này mô tả cái đ−ợc gọi là sự trục trặc về thủ tục. Đây là một ví dụ về một bản mà có thể bị đối ph−ơng giải mà không cần phải xác định khoá nếu dùng thiêú thận trọng hệ mật (vì đối ph−ơng không phải xác định Bảng 4.2 Bản mb RSA 6340 8309 14010 8936 27358 25023 16481 25809 23316 7135 24996 30596 27570 26486 30388 9395 27584 14999 4517 12146 29421 26439 1606 17881 25774 7647 23901 7372 25774 18436 12056 13547 7908 8635 2149 1908 22076 7372 8686 1307 4082 11803 5314 107 7359 22470 7372 22827 15698 30317 4685 14696 30388 8671 29956 15705 1417 26905 25809 28347 26277 7879 20240 21519 12437 1108 27106 18743 24144 10685 25234 30155 23055 8267 9917 7994 9694 2149 10042 27705 15930 29748 8635 23645 11738 24591 20240 27212 27486 9741 2149 29329 2149 5501 14015 30155 18154 22319 27705 20321 23254 13624 3249 5443 2149 16975 16087 146000 27705 19386 7325 26277 19554 23614 7553 4734 8091 23973 14015 107 3183 17347 25234 4595 21498 6360 19837 8463 6000 31280 29413 2066 369 23204 8425 7792 25973 4477 30989 Khoá nên nếu gọi là thám m thì không đ−ợc chính xác lắm). Tinh thần ở đây là dùng hệ mật “ an toàn toàn” vẫn ch−a đủ để đảm bảo liên lạc an toàn toàn. Giả sử Bob có một hệ mật RSA có modulo n lớn để việc phân tích n không thể thực hiên trong một thời gian chấp nhận đ−ợc. Giả sử Alice gửi một thong báo cho Bob bằng cách biểu thị một ký tự bằng một số nguyên trong khoảng 0- 25 (chẳng hạn A ↔0, B ↔1, ) và rồi m hoá từng ký tự của bản rõ. a) H y mô tả cách Oscar có thể giải m dễ dàng các bản m đ−ợc m nh− cách trên. b) Minh hoạ cách tấn công qua việc giải m bản m sau (bản này đ đ−ợc m bằng hệ mật RSA với n = 18721 và b = 25) mà không cần phải phân tích n: 365,0,4845,14930,2608,2608,0
4.8. Bài tập này mô tả một ví dụ khác về sự trục trặc thủ tục (theo Simons)trong RSA đ−ợc gọi là trục trặc thủ tục modulo chung. Giả sử Bob có hệ mât RSA với modulo n, số mũ hoá b 1 còn Charlie có hệ mât RSA với cùng modulo n, số mũ hoá b 2. Giả sử −CLN (b 1,b 2) =1. Bây giờ ta h y xét tình hình xảy ra nếu Alice m hoá cùng một bản rõ x để gửi cho cả Bob và Charlie. Nh− b1 b2 vậy, Alice sẽ tính y 1 =x mod n và y 2 =x mod n và rồi gửi y 1 cho Bob và gửi y2 cho Charlie. Giả sử Oscar thu đ−ợc y 1 và y 2 và thực hiện các tính toán đ−ợc nếu ở hình 4.16 sau. Hình 4.16. trục trặc thủ tục modulo chung. Đầu vào : n, b 1, b 2, y 1, y 2 -1 1. Tính c 1 = b 1 mod b 2 2. Tính c 2 = (c 1b1- 1)/b 2 c1 c2 -1 3. Tính x 1 = y 1 (y 2 ) mod n a) H y chứng tỏ rằng giá trị x 1 tính đ−ợc ở b−ớc 3 của hình 4.16 thực tế là bản rõ x của Alice. Bởi vậy, Oscar có thể giải m đ−ợc thông báo mà Alice đ gửi, ngay cả khi bản rõ đ−ợc gửi qua hệ mật đ−ợc coi là an toàn. b) Minh hoạ cách tấn công qua việc tính x theo ph−ơng pháp này nếu n = 18721,b 1 = 945, b 2 = 7717, y 1 = 12677 và y 2 = 14702. 4.9 Đây lại là một ví dụ khác về sự trục trặc thủ tục xoay quanh hệ mật RSA. Giả sử có ba ng−ời dùng trong mạng là Bob, Bar và Bert, họ đều có số mũ m hoá b =3. Các modulo t−ơng ứng n 1, n 2, n 3. Giả sử Alice m hoá cùng một bản rõ x để gửi cho Bob, Bar và Bert. Khi đó Alice tính 3 yi = x mod n i , 1 ≤ i ≤ 3 H y mô tả cách tnhs x của Oscar khi anh ta đ biết y 1, y 2, y 3, mà không cần phải phân tích bất cứ n i nào. 4.10. Bản rõ x đ−ợc gọi là cố định nếu e k(x) = x. H y chứng tỏ rằng đối với hệ * mật RSA, số các bản rõ cố định x ∈ Z n bằng
−CLN (b-1, p-1) ì −CLN (b-1, p-1) Chỉ dẫn: xét hệ hai ph−ơng trình đồng d−: eK (x 1) ≡ x (mod p), e K(x 2) ≡ x (mod p). 4.11. Giả sử A là một thuật toán tất định có đầu vào là một RSA modulo n và bản m y. A sẽ hoặc giải m y hoặc không có lời giải. Giả sử rằng có ε ì n bản m mà có thể giải, hay chỉ rõ cách dùng A làm một ch−ơng con trong thuật toán giải m Las Vegas có xác suất không thành công là ε. Chỉ dẫn: sử dung tính chất nhân của RSA là eK (x 1) e K(x 2) = e K(x 1x2) trong đó tất cả các phép toán số học là theo modulo n. 4.12. Viết một ch−ơng trình để đánh giá các ký hiệu Jacobi bằng cách dùng bốn tính chất đ−ợc nêu ở phần 4.5. Ch−ơng trình không thực hiện việc phân tích thừa số trừ việc phân ra các luỹ thừa bậc hai. H y kiểm tra ch−ơng trình của bạn qua việc tính các ký hiệu Jacobi sau:  610   20964   1234567   ,  ,   4.13. H y viết một 987 ch−ơng  1987trình tính  111111.11số các số giả nguyên tố Euler theo các cơ sở 837, 851 và 1189. 4.14. Mục đích của bài tập này là phải chứng tỏ rằng: xác suất của kiểm tra * tính nguyên tố Solovay- Strassen nhiều nhất là 1/2 . Giả sử Z n là nhóm các phần tử khả nghịch theo modulo n. Ta định nghĩa: *  a  G(n) = {a : a ∈ Z ,  ≡ a ()1-n 2/ (mod n)} n  n  * a) H y chứng minh rằng, G(n) là một nhóm con của Z n . Do đó theo * định lý Lagrange nếu G(n) ≠ Z n thì * G(n)  ≤ Zn /2 ≤ (n-1)/2 b) Giả sử n = p kq, trong đó p và q là các số lẻ, p là số nguyên tố, k ≥ 2 và −CLN (p,q) =1. Giả sử a = 1+p k-1q. Chứng minh rằng:  a    ≡ a ()n−1 / 2 (mod n)  n 
Chỉ dẫn: Dùng định lý nhị thức để tính a (n-1)/2 . c) Giả sử n = p 1. . . p s trong đó các p i là các số nguyên tố lẻ phân biệt. Giả sử a ≡ u (mod n) và a ≡ 1 (mod p 2p3. . .p s), u là một thặng d− không bậc hai theo modulo p 1. (Chú ý rằng, a nh− vậy tồn tại theo định lý phần d− China). H y chứng minh rằng:  a    ≡ −1(mod n)  n  nh−ng (n-1)/2 a ≡ 1 (mod p 2p3 ps) nên a(n-1)/2 ≡ -1 9mod n) d) Nếu n là một số hợp số lẻ, chứng minh rằng : | G(n) | ≤ (n-1) /2 e) Tổng hợp các kết quả trên, h y chứng minh rằng xác suất sai của phép kiểm tra tính nguyên tố Solovay- Strassen nhiều nhất là 1/2. 4.15. Giả sử ta có thuật toán Las-Vegas với xác suất sai ε. a) H y chứng minh rằng, xác suất thành công lần đầu sau phép thử thứ n là : n-1 pn = ε (1-ε) b) Số phép thử trung bình để đạt thành công là : ∞ ∑ n=1 (n ì p n) H y chứng tỏ rằng giá trị này bằng 1/(1-ε) c) Giả sử δ là một số d−ơng thực nhỏ hơn 1. H y chứng tỏ rằng số các phép lặp cần thiết để giảm xác suất sai tối đa δ là: log δ  2   log ε  2  4.16. Giả sử thiếu trần trọng, Bob đ để lộ số mũ giải m của mình là a = 14039 trong hệ mật RSA với khoa công khai n = 36581 và b = 4679. áp dụng dụng thuật toán sác suất để phân tích n theo thông tin đ−ợc biết này. H y kiểm tra thuật toan của bạn với các phép chọn ngẫu nhiên w = 9983 và w = 13461. H y chỉ ra tất cả các tính toán .
4.17. H y chứng minh các ph−ơng trình 4.1 và 4.2 có liên quan đến các hàm half và parity . 4.18. giả sử p = 199, q = 211 và b = 1357 trong hệ mật Rabin. H y thực hiện tính toán sau: a) Xác định 4 căn bậc hai của modulo n, trong đó n =pq. b) Tính phép m y = e k(32767) c) Xác định 4 bản giả m có thể của bản m y đ cho. 4.19. H y phân tích ra thừa số các số 262063 và 9420457 bằng ph−ơng pháp p- 1. Trong mỗi tr−ờng hợp, để thành công phải chọn B lơn nh− thế nào?.