Bài giảng 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 : Zn
Zn là f(x) = xb 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 Zn 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 ∈ Zn 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à Zn * .Không khó khăn có thể thấy rằng Zn * 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 Zn *đều có nghịch đảo bội (cũng nằm trong Zn *). Cuối cùng Zn * 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ì ∈ Zn * đề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 r0 và r1 với r0 > r1.Thuật toán Euclide bao gồm việc thực hiện các phép toán nh− sau: r0 = q1 r1 +r2 0 < r2 < r1 r1 = q2 r2 +r3 0 < r3 < r2 . . rm -2 = qm -1 rm -1 +rm 0 < rm -1 < rm rm -1 = qm rm Khi đó dễ dàng chứng tỏ đ−ợc rằng −CLN(r0 , r1 ) = −CLN(r1 , r2 ) = . . . −CLN(rm-1 , rm ) = rm Bởi vậy −CLN(r0 , r1 ) = rm 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 r0 = n và r1 = 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ố t0 , t1 ,.... ,tm theo các công thức truy toán sau (trong đó các giá trị qj đ đ−ợc xác định ở trên) t0 = 0 t1 = 1 tj = tj-2- qj-1 tj-1 mod r0 nếu j ≥ 2 Ta có kết quả quan trọng sau Định lý 4.1. Với 0 ≤ j ≤ m, ta có rj ≡ tjr1 (mod r0), trong đó các giá trị qj và rj đ−ợc xác định theo thuật toán Euclide còn các giá trị tj đ−ợ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 ≡ ti-2 r1 (mod r0) và ri-1 ≡ ti-1 r1 (mod r0) Bây giờ ta tính ri = ri-2 - qi-1 ri-1 ≡ ti-2 r1 - qi-1 ti-1 r1 (mod r0) ≡ (ti-2 - qi-1 ti-1)r1 (mod r0) ≡ ti r1 (mod r0) 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: Giả sử −CLN (r0,r1) = 1, khi đó tm = r1 -1 mod r0. Hìn 2.1 Thuật toán Euclide mở rộng: Xét thấy d y các số t0, t1, . . . , tm có thể đ−ợc tính toán trong thuật toán Euclide đồng thời nh− các giá trị qj và rj. 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ị qj, rj và tj 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). 1. n0 = n 2. b0 = b 3. t0 = 0 4. t = 1 5. q = n0 /b0 6. r = n0 - qìb0 7. While r > 0 do 8. temp = t0 -qìt 9. if temp ≥ 0 then temp = temp mod n 10. if temp < 0 then temp = n - ((- temp) mod n) 11. t0 = t 12. t = temp 13. n0 = b0 14. b0 = r 15. q = n0 /b0 16. r = n0 - qìb0 17. if b0 ≠ 1 then b không có nghịch đảo theo modulo n else b-1 = t mod n . 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ử m1, . . . , mr là các số nguyên tố cùng nhau từng đôi một (tức −CLN(mi,mj)=1 nếu j≠i). Giả sử a1,. . ., ar là các số nguyên xét hệ ph−ơng trình đồng d− sau: x ≡ a1 (mod m1) x ≡ a2 (mod m2) . . x ≡ ar (mod mr) Định lý phần d− China khẳng định rằng hệ này có nghiệm duy nhất theo modulo M = m1ì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 pi : ZM
Zm1ì . . .ìZmr. Hàm này đ−ợc định nghĩa nh− sau: pi(x) = (x mod m1, . . . , x mod mr ) Ví dụ 4.2 Giả sử r = 2, m1 = 5 và m2 = 3, bởi vậy M = 15. Khi đó hàm pi có giá trị sau pi(0) = (0,0) pi(1) = (1,1) pi(2) = (2,2) pi(3) = (3,0) pi(4) = (4,1) pi(5) = (0,2) pi(6) = (1,0) pi(7) = (2,1) pi(8) = (3,2) pi(9) = (4,0) pi(10) =(0,1) pi(11) =(1,2) pi(12) =(2,0) pi(13) =(3,1) pi(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 pi 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 pi-1. Với 1 ≤ i ≤ r, định nghĩa: Mi = M/mi Khi đó, dễ dàng thấy rằng −CLN(Mi,mi) = 1 với 1 ≤ i ≤ r. Tiếp theo, với 1 ≤ i ≤ r, định nghĩa yi = Mi -1 mod mi (phần tử nghịch đảo này tồn tại do −CLN(Mi,mi) = 1 và có thể tìm đ−ợc bằng thuật toán Euclide). Cần để ý rằng Miyi ≡ 1 (mod mi) với 1 ≤ i ≤ r. Bây giờ ta định nghĩa hàm ρ: Zm1 ì . . . ì Zmr
ZM nh− sau Ta sẽ chứng tỏ rằng ρ = pi-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 = ρ(a1, . . . ,ar) và cho 1 ≤ j ≤ r. Xét số hạng aiMiyi trong tổng trên khi rút gọn theo modulo mj. Nếu i = j thì aiMiyi ≡ ai (mod mi) ( ) M mod iyiMr 1i iar,...a1aρ ∑== vì Miyi ≡ 1 (mod mi) Mặt khác, nếu i ≠ j thì aiMiyi ≡ 0(mod mj) do mi Mi trong tr−ờng hợp này. Bởi vậy chúng ta có 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. pi 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 pi là một toàn ánh. Bởi vậy pi 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 pi là một song ánh và pi-1 = p. Cũng cần chú ý là pi-1 là một hàm tuyến tính của các biến a1,. . ., ar. Sau đây là một ví dụ lớn hơn để minh hoạ Ví dụ 4.3 Giả sử r = 3, m1 = 7, m2 = 11 và m3 = 13. Khi đó M = 1001. Ta tính M1 = 143, M2 = 91 và M3 = 77 và sau đó tính y1 = 5, y2 = 4 và y3 = 12. Khi đó hàm pi-1: Z7ìZ11ìZ13
Z1001 có dạng: pi-1(a1,a2,a3) = 715a1 +364a2 + 924a3 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ý )ji ii m (mod a )m (mod a X ≡ ∑≡ jiyM Định lý 4.3 (Định lý phần d− China) Giả sử m1, . . . ,mr là các số nguyên d−ơng nguyên tố cùng nhau từng đôi một và cho a1, . . ., ar là các số nguyên. Khi đó, hệ r đồng d− thức x ≡ ai (mod mi) (1 ≤ i ≤ r ) sẽ có một nghiệm duy nhất theo modulo M = m1ì . . . ì mr đ−ợc cho theo công thức trong đó Mi = M/mi và yi = Mi -1 mod mi, 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 gm = 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ếu b ∈ Zn * thì bφ(n) ≡ 1 (mod n) Chứng minh: Zn * là nhóm nhân cấp φ(n). Hệ quả 4.6 (Ferma) Giả sử p là số nguyên tố và b ∈ Zp. Khi đó b p ≡ b (mod p). Chứng minh: Cho tới giờ ta đ biết rằng, nếu p là số nguyên tố thì Zp * là một nhóm cấp p-1 và một phần tử bất kì trong Zp * sẽ có bậc là −ớc của p-1. Tuy nhiên, nếu p là số nguyên tố thì nhóm Zp * là nhóm cyclic: tồn tại một phần tử α ∈ Zp * M mod yMa x ii r 1i i∑= = 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 vẫn đúng do 0p ≡ 0 (mod 0). 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ì Zp * 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} = Zp* Bây giờ giả sử p – nguyên tố và α - phần tử nguyên thuỷ modulo p. Một phần tử bất kì β ∈ Zp* có thể đ−ợc viết nh− sau: β = αi, 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à: 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ử 2i 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 Zn, 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). i)1,-UCLN(p 1-p 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 ∈ Zp*; khi đó ta có: (xb)a ≡ xtφ(n)+1 (mod n) ≡ (xφ(n))t x (mod n) ≡ 1t x (mod n) ≡ x (mod n) Hình 4.2: Hệ mật RSA đúng nh− mong muốn. Xem nh− một bài tập, bạn đọc h y chứng tỏ rằng (xb)a ≡ x (mod n) nếu x ∈ Zn\ Zp *. 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 = 26527, 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 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 eK (x) = x b mod n và dK (y) = y a mod n (x,y) ∈ Zn. Các giá trị n và b đ−ợc công khai , các giá trị p,q,a đ−ợc giữ bí mật. 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 97263533 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: 57616597 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). Độ mật của hệ RSA đ−ợc dựa trên giả thiết là hàm m ek(x)= x b 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à