Khóa luận Các phương pháp tấn công RSA

uật toán giải bài toán phân tích số nguyên như sau: Chọn ngẫu nhiên một số x với gcd(x,n) =1, và tính a =x2modn. Dùng thuật toán A cho a để tìm một căn bậc hai modn của a. Gọi căn bậc hai tìm được đó là y. Nếu y º ±x (modn), thì phép thử coi như thất bại, và ta phải chọn tiếp một số x khác. còn nếu y !º ±x (modn), thì gcd(x-y, n) chắc chắn là một ước số không tầm thường của n, cụ thể là p hay là q. Vì n có 4 căn bậc hai modn nên xác suất của thành công ở mỗi lần thử là 1/2, và do đó số trung bình (kỳ vọng toán học) các phép thử để thu được một thừa số p hayq của n là 2, từ đó ta thu được một thuật toán giải bài toán phân tích số nguyên (Blum) với thời gian trung bình đa thức. Tóm lại, theo một nghĩa không chặt chẽ lắm, ta có thể xem hai bài toán phân tích số nguyên và tìm căn bậc hai modn là khó tương đương nhau. 2.2.5 Bài toán lôgarit rời rạc Cho số nguyên tố p, một phần tử nguyên thuỷ a theo modp (hay a là phần tử nguyên thuỷ của ), và một phần tử b Î.Tìm số nguyên x (0£ x £ p - 2) sao cho a x º b (modp). Ta đã biết rằng trong trường hợp chung, cho đến nay chưa có một thuật toán nào giải bài toán này trong thời gian đa thức. Bài toán này cũng được suy rộng cho các nhóm cyclic hữu hạn như sau: 2.2.6 Bài toán lôgarit rời rạc suy rộng Cho một nhóm cyclic hữu hạn G cấp n, một phần tử sinh (nguyên thuỷ) a của G, và một phần tử b ÎG. Tìm số nguyên x (0£ x £ n - 1) sao cho a x = b. Các nhóm được quan tâm nhiều nhất trong lý thuyết mật mã là: nhóm nhân của trường hữu hạn GF (p) - đẳng cấu với nhóm của trường Zp ,nhóm nhân của trường hữu hạn GF (2m), nhóm nhân: của trường Zn với n là hợp số, nhóm gồm các điểm trên một đường cong elliptic xác định trên một trường hữu hạn, v.v... 2.2.7 Bài toán Diffie-Hellman Cho số nguyên tố p, một phần tử nguyên thuỷ a theo modp (tức phần tử sinh của ), và các phần tử và . Hãy tìm giá trị . Có thể chứng minh được rằng bài toán Diffie-Hellman qui dẫn được về bài toán lôgarit rời rạc trong thời gian đa thức. Thực vậy, giả sử có thuật toán A giải bài toán lôgarit rời rạc. Khi đó, cho một bộ dữ liệu vào của bài toán Diffie-Hellman gồm p, a , và ; trước hết dùng thuật toán A cho (p, a ,) ta tìm được , và sau đó tính được : Người ta cũng chứng minh được hai bài toán lôgarit rời rạc và Diffie-Hellman là tương đương về mặt tính toán trong một số trường hợp, ví dụ p -1 là B-mịn với B = O ((lnp)c ),c là hằng số. Tương tự như với bài toán lôgarit rời rạc, ta cũng có thể định nghĩa các bài toán Diffie-Hellman suy rộng cho các nhóm cyclic hữu hạn khác. 2.2.8 Bài toán giải mã đối với mã tuyến tính Mã tuyến tính là một lớp mã truyền tin có tính chất tự sửa sai được sử dụng trong kỹ thuật truyền tin số hoá. Ta phát biểu bài toán giải mã đối với mã tuyến tính như sau: Cho một ma trận cấp n xm A=(aij) gồm các thành phần là 0 hoặc 1, một vectơ y =(y1,y2,...,ym) các giá trị 0 và 1, và một số nguyên dương K. Hỏi: có hay không một vectơ x =(x1,x2,...,xn) gồm các số 0 hoặc 1 và có không nhiều hơn K số 1 sao cho với mọi j (1£ j £ m): ? Chú ý rằng ở đây, x là vectơ thông tin, và y là vectơ mã, phép giải mã là tìm lại x khi nhận được y, bài toán này tiếc thay lại là một bài toán khó; Berlekamp, McEliece và Tilborg năm 1978 đã chứng minh nó thuộc lớp các bài toán Np đầy đủ ! Dựa trên các bài toán số học nêu trên, nhiều hệ mã bất đối xứng đã ra đời, trong khuôn khổ luận văn này chúng ta đi sâu nghiên cứu hệ mật RSA. Hệ mật RSA được phát minh bởi Ron Rivest, Adi Shamir, và Len Adleman [18], được đưa ra công khai lần đầu tiên vào tháng 8 năm 1977 trên tạp chí khoa học Mỹ. Hệ mật thường sử dụng cho việc cung cấp sự riêng tư và bảo đảm tính xác thực của dữ liệu số. Sơ đồ chung của hệ mã khoá công khai được cho bởi : S = (P , C , K , E , D ) trong đó P là tập ký tự bản rõ, C là tập ký tự bản mã, K là tập các khoá K , mỗi khoá K gồm có hai phần K =(K’,K''), K' là khoá công khai dành cho việc lập mật mã, còn K'' là khoá bí mật dành cho việc giải mã. Với mỗi ký tự bản rõ xÎP , thuật toán lập mã E cho ta ký tự mã tương ứng y =E (K', x) Î C , và với ký tự mã y thuật toán giải mã D sẽ cho ta lại ký tự bản rõ x : D (K'', y) = D (K'', E (K', x)) =x. Để xây dựng một hệ mã khoá công khai RSA, ta chọn trước một số nguyên n =p.q là tích của hai số nguyên tố lớn, chọn một số e sao cho gcd(e, f (n)) =1, và tính số d sao cho e.d º 1(modf (n)). Mỗi cặp K =(K’,K''), với K' =(n,e) và K'' = d sẽ là một cặp khoá của một hệ mật mã RSA cụ thể cho một người tham gia. Như vậy, sơ đồ chung của hệ mật mã RSA được định nghĩa bởi danh sách (1), trong đó: P = C = Zn , trong đó n là một số nguyên Blum, tức là tích của hai số nguyên tố; K = {K =(K’,K''): K' =(n,e) và K'' = d, gcd(e, f (n)) =1, e.d º 1(modf (n))}; E và D được xác định bởi: E (K', x) = xe modn, với mọi x ÎP , D (K'', y) = yd modn, với mọi y ÎC . Để chứng tỏ định nghĩa trên là hợp thức, ta phải chứng minh rằng với mọi cặp khoá K =(K' ,K'' ), và mọi x ÎP , ta đều có D (K'', E (K', x)) = x . Thực vậy, do e.d º 1(modf (n)) ta có thể viết e.d = t .f (n) +1. Nếu x nguyên tố với n , thì dùng định lý Euler (xem 2.1.3) ta có D (K'', E (K', x)) = Nếu x không nguyên tố với n , thì do n =p.q , hoặc x chia hết cho p và nguyên tố với q, hoặc x chia hết cho q và nguyên tố với p, và f (n) =(p -1).(q -1),trong cả hai trường hợp ta đều có từ đó suy ra tức D (K'', E (K', x)) =x. Tính bảo mật của RSA có độ khó tương đương với bài toán phân tích số nguyên (Blum) thành thừa số nguyên tố. Do đó, giữ tuyệt mật khoá bí mật d, hay giữ tuyệt mật các thừa số p,q , là có ý nghĩa rất quyết định đến việc bảo vệ tính an toàn của hệ mật mã RSA. 2.3 Vấn đề thám mã Mục tiêu của thám mã (phá mã) là tìm những điểm yếu hoặc không an toàn trong phương thức mật mã hóa. Thám mã có thể được thực hiện bởi những kẻ tấn công ác ý, nhằm làm hỏng hệ thống; hoặc bởi những người thiết kế ra hệ thống (hoặc những người khác) với ý định đánh giá độ an toàn của hệ thống. Có rất nhiều loại hình tấn công thám mã, và chúng có thể được phân loại theo nhiều cách khác nhau. Một trong những đặc điểm liên quan là những người tấn công có thể biết và làm những gì để hiểu được thông tin bí mật. Ví dụ, những người thám mã chỉ truy cập được bản mã hay không? hay anh ta có biết hay đoán được một phần nào đó của bản rõ? hoặc thậm chí: Anh ta có chọn lựa các bản rõ ngẫu nhiên để mật mã hóa? Các kịch bản này tương ứng với tấn công bản mã, tấn công biết bản rõ và tấn công chọn lựa bản rõ. Trong khi công việc thám mã thuần túy sử dụng các điểm yếu trong các thuật toán mật mã hóa, những cuộc tấn công khác lại dựa trên sự thi hành, được biết đến như là các tấn công side-channel. Nếu người thám mã biết lượng thời gian mà thuật toán cần để mã hóa một lượng bản rõ nào đó, anh ta có thể sử dụng phương thức tấn công thời gian để phá mật mã. Người tấn công cũng có thể nghiên cứu các mẫu và độ dài của thông điệp để rút ra các thông tin hữu ích cho việc phá mã; điều này được biết đến như là thám mã lưu thông Nếu như hệ thống mã sử dụng khóa xuất phát từ mật khẩu, chúng có nguy cơ bị tấn công kiểu duyệt toàn bộ (brute force), vì kích thước không đủ lớn cũng như thiếu tính ngẫu nhiên của các mật khẩu. Thám mã tuyến tính và Thám mã vi phân là các phương pháp chung cho mã hóa khóa đối xứng. Khi mã hóa dựa vào các vấn đề toán học như độ khó NP, giống như trong trường hợp của thuật toán khóa bất đối xứng, các thuật toán như phân tích ra thừa số nguyên tố trở thành công cụ tiềm năng cho thám mã. Ở luận văn này, ta tập trung nghiên cứu vấn đề thám mã với RSA. Từ khi được công bố lần đầu, hệ RSA đã được phân tích hệ số an toàn bởi nhiều nhà nghiên cứu. Mặc dầu với nhiều năm nghiên cứu và đã có một số cuộc tấn công ấn tượng nhưng không mang lai kết quả (phá hủy). Chúng ta chỉ ra những mối nguy hiểm của người sử dụng RSA cần cải thiện. Mục đích của chúng ta là nghiên cứu, cài đặt tấn công và mô tả các công cụ toán học mà chúng ta sử dụng. Quá trình nghiên cứu của chúng ta tuân theo chuẩn ngầm định và sử dụng Alice và Bob để biểu thị cho hai phía muốn truyền thông lẫn nhau. Chúng ta coi Marvin là kẻ gian muốn tấn công nghe lén hay lấy trộm trộm thông tin giữa Alice và Bob. Ta bắt đầu mô tả một phiên bản được đơn giản hóa của hệ mật RSA: Giả sử N=pq là tích của hai số nguyên tố lớn cùng kích thước (mỗi số n/2 bít). Số N với kích thức 1024 bit, nghĩa là 309 số thập phân. Mỗi một nhân tử là 512 bit. Giả sử e, d là hai số nguyên thỏa mãn ed = 1 mod (N) với điều kiện (N) = (p − 1)(q − 1) là cấp của nhóm nhân trên Z*N. Chúng ta gọi N là modul RSA, e là số mũ mã hóa và d là số mũ giải mã. Cặp (N,e) là khóa công khai. Cặp (N,d) được gọi là khóa bí mật hay còn gọi là khóa riêng và chỉ có người nhận mới được biết. Khóa bí mật dùng để giải mã bản mã. Một thông điệp (message) là một số nguyên M Z*N . Để mã hóa M, một phép tính C=Me mod N. Để giải mã bản mã, cần tính Cd mod N. Tức là: Cd = Med = M (mod N) Ở đây phương trình cuối cùng được chỉ ra bởi định lý Euler. Người ta xác định (hay định nghĩa) hàm RSA là một ánh xạ f: x xe mod N. Nếu d cho trước, hàm đó có thể dễ dàng nghịch đảo được bằng cách dùng phương trình trên. Chúng ta coi d như là một cửa sập (trapdoor) để nghịch đảo hàm f. Bản chất của việc tấn công là nghiên cứu độ khó của hàm ngược (nghịch đảo) RSA khi không cho trước của sập d. Nói chính xác hơn, cho trước bộ 3 (N,e,C), chúng ta muốn biết được độ khó của việc tìm căn bậc e của C theo mod N (N = p.q) như thế nào khi chưa biết nhân tử của N. Vì ZN* là một tập hợp hữu hạn nên người ta có thể liệt kê (đếm) được tất cả các phần tử của Z*N cho đến khi tìm được đúng số nguyên (bức thông điệp) M cần tìm. Rất tiếc là thời gian thực hiện của thuật toán để tìm được đúng số M có cấp N, nghĩa là kích cỡ đầu vào có cấp số mũ thì thời gian chạy có cấp log2N. Chúng ta quan tâm đến thuật toán có thời gian bé hơn, tính bậc của nc điều kiện n=log2N và c là một hằng số nhỏ (bé hơn 5), thực tế thuật toán tốt hay không phụ thuộc vào kích thước đầu vào. Trong luận văn này chúng ta quan tâm đến thuật toán được coi là có hiệu quả. Chúng ta tập trung chủ yếu vào nghiên cứu hàm ngược của RSA để tấn công vào RSA. Việc khó khăn của tính hàm ngược RSA chính là từ đầu vào ngẫu nhiên, được cho bởi (N,e,C), một kẻ tấn công không thể tìm ra bản rõ M. Nếu cho trước (N,e,C), rất khó để tìm ra thông tin về M. Điều này được biết trong lý thuyết an ninh an toàn. Chúng ta chỉ ra rằng RSA được mô tả ở trên là không an toàn: nếu cho (N,e,C), chúng ta có thể dẽ dàng suy diễn ra một vài thông tin của bản rõ M (ví dụ, ký tự Jacobi của M trên N được dễ dàng suy ra từ C). RSA có thể được an toàn ngữ nghĩa bằng việc thêm các bít ngẫu nhiên vào quá trình xử lý mã hóa. Hàm RSA x xe mod N là một ví dụ về hàm của sập một chiều (trapdoor one-way function). Nó có thể được tính toán dẽ dàng, nhưng như chúng ta đã biết không thể tính ngược hiệu quả nếu không có (cửa sập) d ngoại trừ một vài trường hợp đặc biệt. Chương 3 - TỔNG KẾT NHỮNG KẾT QUẢ TẤN CÔNG VÀO HỆ MẬT RSA TRONG NHỮNG NĂM QUA 3.1 Một số giả thiết ngầm định 1) N – RSA modulus 2) e – số mũ mã hóa (encryption exponent) 3) d – số mũ giải mã (decryption exponent) 4) M – Thông điệp số nguyên (message integer), M Z*N 5) Alice, Bob là đại diện hai bên truyền thông điệp cho nhau, Marvin là kẻ tấn công (attacker) 6) Hàm RSA là một ánh xạ f: x xe mod N. Nếu d cho trước, hàm đó có thể dễ dàng nghịch đảo được bằng cách dùng phương trình trên. Chúng ta coi d như là một cửa sập (trapdoor) để nghịch đảo hàm f. 7) Chúng ta nghiên cứu độ khó của hàm ngược (nghịch đảo) RSA khi không cho trước của sập d và nghiên cứu phương pháp tấn công RSA trong trường hợp này. 8) Chúng ta quan tấm đến thuật toán hữu hiệu có thời gian bé, tính bậc của nc điều kiện n=log2N và c là một hằng số nhỏ (bé hơn 5). 9) Về mặt lý thuyết, nếu cho trước (N,e,C), rất khó để tìm ra thông tin về M. 10) Tấn công vét cạn (brute-force attack) bằng cách phân tích các modulus, thời gian chạy với số nguyên n-bít là exp((c + o(1))n1/3log2/3n) trong đó c < 2 . 3.2 Phân tích các số nguyên lớn Vấn đề phân tích một số nguyên tố lớn thành tích các số nguyên tố khác nhau là bài toán rất hấp dẫn và đã được nhiều nhà toán học quan tâm nghiên cứu; chẳng hạn [1], [2], [3] tuy nhiên trong phạm vi của một luận văn cao học, em chỉ tập trung nghiên cứu trong trường hợp N là tích của hai số nguyên tố phân biệt. sau đây là một số mệnh đề quan trọng phục vụ việc tấn công cơ bản: Mệnh đề 1: Giả sử N là một số tự nhiên không chính phương (perfect square), tức N không phải là bình phương đúng của một số nguyên tố, thỏa mãn điều kiện: N – 1 > (N) > N – N2/3 Khi đó N là tích của 2 số nguyên tố phân biệt. Chứng minh: Thật vậy, rõ ràng N không phải là số nguyên tố vì nếu N là số nguyên tố thì (N) = N-1, trái với giả thiết. Do giả thiết N không phải là bình phương của một số nguyên tố. Như vậy nếu N không phải là tích của 2 số nguyên tố phân biệt thì nó phải là tích của nhiều hơn 2 số nguyên tố (không cần phân biệt). Giả sử p là số nguyên tố nhỏ nhất của tích; Khi đó p N 1/3 do đó chúng ta có (N) N(1- ) N(1 – N-1/3) = N – N2/3 Điều này mâu thuẫn với giả thiết. Vậy N = p.q trong đó p,q là 2 số nguyên tố lẻ, phân biệt. Chú ý: Mệnh đề đảo của mệnh đề 1 cũng đúng. Mệnh đề 2: Với (N,e) là khóa công khai của RSA. Cho trước khóa riêng d, người ta có thể phân tích thành nhân tử môdul N=pq một cách hiệu quả. Ngược lại cho các thừa số của N, người ta có thể khôi phục được d một cách có hiệu quả. Từ các mệnh đề ở trên người ta đã đưa ra một số tấn công vào RSA sau đây: 3.3 Các tấn công cơ bản 3.3.1 Modul chung Để tránh việc phân tích modul N = pq khác nhau cho các người dùng khác nhau, chúng ta lấy N chung cho tất cả. Cùng một N được sử dung cho tất cả người sử dụng. Trung tâm xác thực có thể cung cấp cho người sử dụng i với một cặp ei, di và người sử dụng i có một khóa công khai là (N,ei) và khóa riêng là (N,di). Ban đầu chúng ta có: một bản mã C = Mea mod N cung cấp cho Alice không được mã hóa bởi Bob, vì Bob không có da. Tuy nhiên điều này là nhầm lẫn và kết quả là hệ thống không an toàn. Bằng mệnh đề 1 (ở trên) Bob có thể sử dụng các thành phần eb và db của mình để nhân tử hóa N. N bị nhân tử hóa bởi Bob có thể lấy được khóa riêng da của Alice từ khóa công khai ea của cô ấy. Với cách tiếp cận này, theo Simmons chỉ ra rằng một modul RSA không nên sử dụng quá một thực thể. 3.3.2 Mù (Blinding) Marvin chọn ngẫu nhiên một số r Z*N và đặt M’ = re M mod N. Sau đó anh ta nhờ Bob ký lên M’. Bob có thể cung cấp chứ ký của mình là S’ lên M’. Nhưng từ cách tính S’= (M’)d mod N, Marvin có thể đơn giản tính S = S’/r mod N để có được chữ ký của Bob là S trên M. Se = (S’)e/re = (M’)ed/re = M’/re = M/(mod N) 3.4 Số mũ riêng bé (Low Private Exponnent) Trong thực tế, để giải mã nhanh đòi hỏi số d nhỏ và điều này để lộ lỗ hổng mà kẻ tấn công có thể thực hiện như sau. Trước hết ta nghiên cứu định lý Wiener Định lý 1 (M. Wiener): Cho N = pq với q < p< 2q. Giả sử d < 1/3N1/4. Cho trước (N,e) với ed = 1 mod (N), Marvin có thể tìm được d hiệu quả. Việc chứng minh định lý trên dựa trên xấp xỉ hóa phân số liên tục như sau: Khi ed = 1 mod (N), tồn tại một số k thỏa mãn ed - k(N) = 1 Vì thế: Do đó, là xấp xỉ của . Mặc dù Marvin không biết (N), anh ta có thể sử dụng N để xấp xỉ nó. Hơn nữa, từ (N) = N- p- q +1 và p + q-1< 3, chúng ta có | N - (N) | < 3. Sử dụng N thay vào (N), chúng ta có: = Bây giờ, k(N) = ed – 1 < ed. Từ e < (N), chúng ta thấy rằng k < d < N1/4. Vì thế ta có: Đây là hệ thức xấp xỉ cổ điển. Phân số với d < N là xấp xỉ của nên bị chặn tại log2N. Trong thực tế, tất cả các nhân tử thu được từ phân tích đều hội tụ tại kết triển khai mở rộng phân số [12, Th, 177]. Tất cả kết quả đó đều thu được từ việc tính toán logN hội tụ của việc tính toán phân số . Một trong những kết quả đó sẽ là . Khi đó ed - k(N) = 1, chúng ta có gcd(k,d) = 1, và vì thế là rút gọn phân số. Thuật toán tìm khóa riêng d là thuật toán có thời gian tuyến tính. 3.4.1 Độ lớn e Thay vì rút gọn e trong (N), ta sử dụng (N,e’) cho khóa công khai thỏa mãn e’ = e + t.(N) trong đó số t lớn. Rõ ràng có thể sử dụng e’ thay thế e để mã hóa thông điệp. Tuy nhiên, khi số e có giá trị lớn, theo chứng minh ở trên thì số k không thể nhỏ hơn. Một tính toán đơn giản chỉ ra rằng nếu e’ > N1.5 thì sẽ không có vấn đề gì xẩy ra mặc dù số d nhỏ và tấn công ở trên không thể thực hiện được. Nhưng điều bất tiện là số e lớn sẽ là tăng thời gian mã hóa. 3.4.2 Sử dụng CRT Một cách tiếp cận khác là sử dụng định lý đồng dư trung hoa (Chinese Remainder Theorem - CRT). Ta chọn một số d sao cho cả dp = d mod (p - 1) và dp =d mod (q - 1) đều nhỏ 128 bits. Để giải mã nhanh bản C ta có thể tiến hành: Trước hết ta tính Mp = Cdp mod p và Mq = Cdq mod q . Sau đó sử dụng CRT để tính giá trị M ZN thỏa mãn M = Mp mod p và M = Mq mod q. Kết quả M phải thỏa mãn M = Cd mod N là bắt buộc. Mặc dầu dp và dq là nhỏ song giá trị d mod (N) có thể lớn, tùy thuộc vào (N). Theo kết quả, sự tấn công của định lý 2 không được áp dụng. Chúng ta lưu ý rằng nếu (N,e) được biết thì kẻ địch có thể tấn công N trong thời gian O(min(, )), vì thể dp và dq không thể quá nhỏ. Mặt khác ta không thể biết được điều gì xẩy ra đối với vấn đề an ninh này. Chúng ta chỉ biết thông qua tấn công hữu hiệu của Wiener. Định lý 1 gần đây đã được cải thiện bởi Boneh và Durfee [4], họ chỉ ra rằng số với d < N0.292, kẻ tấn công có thể tính được d từ (N,e). Kết quả này chỉ ra ranh giới của Wiener là không rõ ràng. Nó có vẻ như là d< N0.5, đây là một bài toán mở. Bài toán mở : Cho N = pq và d < N 0.5. Nếu Marvin biết (N,e) với ed = 1 mod (N) và e < (N), anh ta có thể tìm được d không ? 3.5 Số mũ công khai bé (Low public Exponent) Định lý 2 (Coppersmith): Cho N là một số nguyên và f Z[x] là một đa thức mà có độ đo là d. Đặt X = N1/d-e cho e 0. Sau đó biết (N,f) Marvin có thể tìm tất cả số nguyên |x0| < X thỏa mãn f(x0) = 0 mod N. Thời gian chạy phụ thuộc vào thời gian chạy thuật toán LLL với trên một lưới có khoảng cách là O() với = min(1/e, log2 N). Định lý cung cấp một thuật toán có thể tìm kiếm hiệu quả tất cả gốc f của N ít hơn X = N1/d. Với X nhỏ hơn, thời gian chạy thuật toán cũng giảm. Sức mạnh của thuật toán là có thể tìm được gốc của N trong thời gian đa thức. Định lý Coppersmith làm việc rất hiệu quả với một số nguyên tố. 3.5.1 Hastad's Broadcast Attack. Để đơn giản ta coi ei là thành phần công khai bằng 3. Marvin tìm ra M rất đơn giản nếu k 3. Thực vậy, Marvin có được C1, C2, C3, thỏa mãn: C1 = M3 mod N1, C2 = M3 mod N2, C3 = M3 mod N3. Nên với e = 3, gửi các thông điệp giống nhau đến 3 người nhận là không an toàn. Giải pháp chống tấn công này chúng ta gắn các thông điệp trước khi mã hóa với đa thức ? Định lý 3 (Hastad). Cho N1, . . , Nk là những số nguyên tố và tập Nmin = mini(Ni) từng đôi một. Với gi ZNi[x], k là đa thức có giá trị nhỏ nhất là d. Tồn tại M d, có thể tìm M khi cho (Ni,gi)ki=1. Định lý chỉ ra rằng một hệ thống đồng biến với các đa thức nguyên tố hỗn hợp có thể giải quyết hiệu quả, giả thiết rằng các hàm được cung cấp đầy đủ. Bằng cách cài đặt gi = fiei – Ci mod Ni, chúng ta thấy rằng Marvin có thể tìm được M từ bản mã được cho với số thành viên ít nhất là d, khi đó d là giá trị lơn nhất của eideg(fi) với i = 1,…,k. Chúng ta lưu ý rằng để chống lại tấn công broadcast ở trên chúng ta sử dụng một cặp số ngẫu nhiên thay vì gắn cứng vào một giá trị. 3.5.2 Franklin-Reiter Related Message Attack. Hệ quả (FR): Giả sử rằng với e =3 và (N,e) là một khóa công khai của RSA. Cho M1 M2 Z*N thỏa mãn M1 = f(M2) mod N trong đó f = ax + b Z*N là đa thức tuyến tính với b 0. Khi đó cho trước (N, e, C1,C2, f), Marvin có thể tìm được M1, M2 với thời gian là đa thức bậc hai log N. - Để chứng minh hệ quả FR ta tính gcd của hai đa thức. - Với e = 3 thì giá trị gcd phải là giá trị tuyến tính. Thật vậy, đa thức x3 – C2 phân tích thành p và q là phép phân tích tuyên tính và không thể rút gọn về nhân tố bậc hai (ta nhớ rằng gcd(e, (N)) = 1 và vì thế x3 – C2 chỉ có giá trị gốc nằm trong ZN). Khi đó g2 không thể chia cho g1, gcd phải là một hàm tuyến tính. Với e = 3 hàm gcd luôn là tuyến tính. Tuy nhiên, đối với một vài M1, M2 và f, gcd có thể không phải là tuyến tính, trong trường hợp này việc tấn công là thất bại. - Thường nó chỉ áp dụng với khi số mũ công khai e được sử dụng với giá trị nhỏ. Với e lớn, công việc tính toán gcd là rất khó. Một câu hỏi thú vị (nếu không nói là khó) đặt ra là liệu việc tấn công với một số e bất kỳ sẽ như thế nào. Khí đó việc tính toán gcd của g1 và g2 theo cách trên có trong thời gian đa thức đối với log e ? 3.6 Thành phần công khai bé 3.6.1 Coppersmith's Short Pad Attack. - Ý tưởng chính của tấn công này là ta thêm ngẫu nhiên các bít vào cuối của thông điệp, thuật toán này có thể thu được bản rõ của M. Tấn công này rất đơn giản nhưng rất nguy hiểm. Định lý 4: Với (N,e) là một khóa công khai của RSA, N có độ dài n-bits. Đặt m = [n/e2]. Với M Z*N là một thông điệp có độ dài n-m bit. M1 = 2mM + r1 và M2 = 2mM + r2 với điều kiện r1 và r2 là hai số nguyên khác nhau thỏa mãn 0 r1 , r2< 2m. Nếu Marvin biết (N,e) và các bản mã hóa C1, C2 của M1, M2 (nhưng không biết r1 , r2 ), anh ấy có thể tìm ra M một cách có hiệu quả. Thực tế, khi e = 3 tấn công có thể đạt được với độ dài của các bít thêm vào là ít hơn 1/9th độ dài của bản thông điệp. Đây là một kết quả quan trọng. Lưu ý rằng việc đưa ra giá trị e = 65537 thì sự tấn công là vô ích đối với các modul kích kỡ chuẩn. 3.6.2 Tấn công bằng khóa riêng. Với (N,d) là một khóa riêng của RSA. Giả sử rằng Marvin có thể tìm được một nhân tử trong dãy bit của d, hay một phần của d. Từ đó Marvin có thể khôi phục được phần còn lại của d. Cụ thể ta có định lý sau: Định lý 5 (BDF): Cho (N,d) là một khóa riêng của RSA trong đó N có độ dài là n bit. Biết [n/4] bít ít ý nghĩa nhất của d, Marvin có khôi phục được số d với thời gian tuyến tính elog2e. Định lý 6 (Coppersmith): Giả sử số N = pq (là một modul RSA) có n bit. Cho trước n/4 bít ít ý nghĩa nhất (hoặc n/4 bít nhiều ý nghĩa nhất) của p (giả thiết p<q). Khi đó có tồn tại một phân tích số N một cách có hiệu quả. Định lý BDF được chứng minh thông qua định lý Coppersmith. Định lý 5 là kết quả của định lý 6. Trong thực tế, từ e và d, tồn tại một số nguyên k sao cho ed – k(N – p – q + 1) = 1 vì thế d < (N), mặt khác ta có 0 < k e. Rút gọn với 2n/4 và đặt q = N/p, chúng ta có: (ed)p – kp(N – p + 1) + kN = p (mod2n/4). Khi Marvin biết được ít nhất n/4 bít của chuỗi bít d, anh ta có được giá trị của ed mod 2n/4. Ví thế anh ta có được phương trình có k và p. Mặt khác từ giá trị của e và có thể là k, Marvin giải phương trình bậc hai chứa p và thu được một giá trị của p mod 2n/4. Với các giá trị thu được này, anh ta chạy thuật toán của định lý 6 để phân tích nhân N thành nhân tử. Do tổng các giá trị của p mod 2n/4 lớn nhất là e log2e. Vì thế tại giá trị lớn nhất e log2e, N sẽ bị phân tích. Định lý 5 được biết như là một phương pháp tấn công vào khóa riêng (partial key-exposure). Tương tự như các phương pháp tấn công đã tồn tại, với giá trị e lớn hơn và phải bé hơn , tuy nhiên với số bít tăng kỹ thuật sẽ phức tạp hơn. Có một điều thú vị là các hệ mật dựa trên log rời rạc như hệ mật khóa công khai ElGamal, thì dường như không dẽ bị phá vỡ bởi phương pháp này. Hơn nữa nếu gx mod p và một nhân tử là hằng số x được cho, không có thuật toán với thời gian đa thức để tính phần còn lại của x. Với cách tấn công này, chúng ta chỉ ra rằng khi mã hóa với thành phần e nhỏ, hệ mật RSA bị rò rỉ một nửa số bít quan trọng nhất (hoặc ít quan trọng nhất) tương ứng với rò khóa riêng d. Để hiểu rõ điều này, chúng ta xét phương trình ed –k(N – p – q + 1) = 1 trong đó k là một số nguyên thỏa mãn 0 < k e. Cho k, Marvin có thể dẽ dàng tính : Sau đó tính: Vì thế là một xấp xỉ tốt cho d. Với biên này cho thấy với d tốt nhất, một nửa số tín hiệu bít của sẽ dẫn tới d. Vì thế chỉ e mới có thể là giá trị của k, Marvin có thể xây dựng một tập con nhỏ của e như là một thành phần của tập bằng một nửa tín hiệu bít có ý nghĩa nhất của d. Trong trường hợp e = 3 là trường hợp đặc biệt, tại đây có thể chỉ ra rằng k luôn bằng 2 và vì thế hoàn toàn bị rò rỉ một nửa tín hiệu bít ý nghĩa nhất của d. 3.7 Cài đặt các tấn công. 3.7.1 Tấn công dựa trên thời gian. Tấn công thông minh của Kocher cho thấy rằng bằng phương pháp lựa chọn thời gian chính xác để giải mã (hoặc ký số) RSA của smartcard, Marvin có thể nhanh chóng tìm ra thành phần giải mã riêng d. Sử dụng thuật toán “repeated squaring algorithm” tính C = Md mod N. Với d = dndn-1 . . . d0 là biểu diễn nhị phân của d (hay d = với di {0,1}), sử dụng nhiều nhất 2n modul nhân. Nó dựa trên việc xem xét C = mod N. Thuật toán làm việc như sau: Đặt: z = M và C =1. For i = 0,…,n, thực hiện các bước: Nếu di = 1 đặt C = C – z mod N Đặt z = z2 mod N Tại trạng thái kết thúc, C có giá trị là Md mod N. Để thực hiện tấn công, Marvin sẽ yêu cầu smartcard cung cấp chữ ký điện tử trên trường số lớn ngẫu nhiên với một trong các thông đ