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

với các mục đích như: Mã hóa: giữ bí mật thông tin và chỉ có người có khóa bí mật mới giải mã được. Tạo chữ ký số: cho phép kiểm tra một văn bản có phải đã được tạo với một khóa bí mật nào đó hay không. Thỏa thuận khóa: cho phép thiết lập khóa dùng để trao đổi thông tin mật giữa 2 bên. Các kỹ thuật mã bất đối xứng đòi hỏi khối lượng tính toán nhiều hơn các kỹ thuật mã hóa khóa đối xứng nhưng những lợi điểm mà chúng mang lại khiến cho chúng được áp dụng trong nhiều ứng dụng. Các hệ mã bất đối xứng dựa trên tính chất của các bài toán cơ bản như: 2.2.1 Bài toán phân tích số nguyên thành thừa số nguyên tố Cho số nguyên dương n , tìm tất cả các ước số nguyên tố của nó, hay là tìm dạng phân tích chính tắc của n =, trong đó pi là các số nguyên tố từng cặp khác nhau và các ai ³ 1. Bài toán này có liên hệ mật thiết với các bài toán thử tính nguyên tố hay thử tính hợp số của một số nguyên, nhưng với những gì mà ta biết đến nay, nó dường như khó hơn nhiều so với hai bài toán thử tính nguyên tố và tính hợp số. 2.2.2 Bài toán RSA (Rivest-Shamir-Adleman) Cho số nguyên dương n là tích của hai số nguyên tố lẻ khác nhau, một số nguyên dương e sao cho gcd(e,f (n)) =1, và một số nguyên c ; tìm một số nguyên m sao cho . Điều kiện gcd(e,f (n)) =1 bảo đảm cho việc với mỗi số nguyên c Î {0,1,...,n -1} có đúng một số m Î {0,1,...,n -1} sao cho . Dễ thấy rằng nếu biết hai thừa số nguyên tố của n, tức là biết n =p.q thì sẽ biết f (n) = (p -1)(q -1), và từ đó, do gcd(e,f (n)) =1 sẽ tìm được d =e -1modf (n), và do đó sẽ tìm được m =c d modn. Như vậy, bài toán RSA có thể qui dẫn trong thời gian đa thức về bài toán phân tích số nguyên. 2.2.3 Bài toán thặng dư bậc hai Cho một số nguyên lẻ n là hợp số, và một số nguyên a ÎJn , tập tất cả các số a có ký hiệu Jacobi. Hãy quyết định xem a có là thặng dư bậc hai theo modn hay không? Trong lý thuyết mật mã, bài toán này cũng thường được xét với trường hợp n là số nguyên Blum, tức n là tích của hai số nguyên tố p và q , n =p.q. Ta chú ý rằng trong trường hợp này, nếu a ÎJn , thì a là thặng dư bậc hai theo modn, điều này có thể thử được dễ dàng vì nó tương đương với điều kiện a (p -1)/2º 1 (modp). Như vậy, trong trường hợp này, bài toán thặng dư bậc hai có thể qui dẫn trong thời gian đa thức về bài toán phân tích số nguyên. Mặt khác, nếu không biết cách phân tích n thành thừa số nguyên tố thì cho đến nay, không có cách nào giải được bài toán thặng dư bậc hai trong thời gian đa thức. Điều đó củng cố thêm niềm tin rằng bài toán thặng dư bậc hai và bài toán phân tích số nguyên là có độ khó tương đương nhau. 2.2.4 Bài toán tìm căn bậc hai mod n Cho một số nguyên lẻ n là hợp số Blum, và một số a ÎQn , tức a là một thặng dư bậc hai theo modn . Hãy tìm một căn bậc hai của a theo modn, tức tìm x sao cho x 2º a (modn). Nếu biết phân tích n thành thừa số nguyên tố, n =p.q , thì bằng cách giải các phương trình x 2º a theo các modp và modq, rồi sau đó kết hợp các nghiệm của chúng lại theo định lý số dư Trung quốc ta sẽ được nghiệm theo modn , tức là căn bậc hai của a theo modn cần tìm. Vì mỗi phương trình x 2º a theo modp và modq có hai nghiệm (tương ứng theo modp và modq ), nên kết hợp lại ta được bốn nghiệm, tức bốn căn bậc hai của a theo modn. Người ta đã tìm được một số thuật toán tương đối đơn giản (trong thời gian đa thức) giải phương trình x 2º a (modp) với p là số nguyên tố. Như vậy, bài toán tìm căn bậc hai modn có thể qui dẫn trong thời gian đa thức về bài toán phân tích số nguyên. Ngược lại, nếu có thuật toán A giải bài toán tìm căn bậc hai modn thì cũng có thể xây dựng một thuậ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 điệp M1, . . . , Mk Z*N và với đơn vị thời gian Ti nó yêu cầu card cung cấp các chữ ký khác nhau. - Nếu d1 = 1, smardcard sẽ tính C.z = M . M2 mod N. Nếu khác 1 thì không tính. Gọi ti là thời gian tính Mi.Mi2 mod N. Các giá trị ti’s sẽ khác nhau phụ thuộc vào giá trị của Mi (Cũng như thuật toán rút gọn, thời gian tính toán sẽ phụ thuộc vào giá trị mà ta cần tình toán). Đơn vị ti’s là số lần anh ta ngừng để yêu cầu với card (trước khi thực hiện tấn công) tương ứng với những lần anh ta thao tác vật lý trực tiếp card. - Khi d1 = 1, hai bộ {ti} và {Ti} có tương quan với nhau. Ví dụ: Nếu với i, ti lớn hơn so với sự mong đợi, thì Ti cũng lớn hơn so với sự mong đợi. Mặt khác: nếu d1 = 0, hai bộ {ti} và {Ti} độc lập như các biến ngẫu nhiên. Với độ đo độ tương quan, Marvin có thể xác định được d1 hoặc bằng 1 hoặc bằng 0. Tiếp tục với phương pháp này, anh ta có thể khôi phục được d2,d3… Lưu ý rằng, khi thành phần e của khóa công khai được sử dụng thấp, khóa riêng tìm được theo phương pháp ở phần trên giúp cho phương pháp của Kocher có thể khôi phục được toàn bộ d chỉ cần biết trước một phần tư số bít của d. Giải pháp chống đỡ: 1) Đơn giản nhất là tăng độ trễ nhất định để quá trình mũ hóa luôn mất một thời gian nhất định. 2) Rivest đưa ra dựa trên cơ chế bịt các kẽ hở (blinding). Kocher đã khám phá ra một cách tấn công khác dọc theo các hàng được gọi là phân tích mật mã theo lũi thừa (power cryptanalysis). Kocher đã chỉ ra rằng bằng cách đo chính xác lũy thừa của smartcard trong suốt quá trình sinh chữ ký, Marvin có thể dễ dàng ra khóa riêng. Thật vậy, trong suốt quá trình thực hiện một phép nhân, năng lương tiêu thụ của card cao hơn mức bình thường. Bằng phương pháp đo chiều dài của độ cao của sự tiêu thụ trong phần trước, Marvin có thể dễ dàng xác định được nếu card lặp đi lặp lại một vài phép nhân, bằng cách anh ta thu được chuỗi bít của d. 3.7.2 Tấn công dựa trên các lỗi ngẫu nhiên. Quá trình cài đặt giải mã và ký số RSA thường sử dụng định lý đồng dư trung hoa ( Chinese Remainder Theorem) nhằm cải thiện tốc độ tính toán Md mod N. Boneh, DeMillo, và Lipton [3] đã quan sát và thấy rằng có một lỗi nguy hiểm khi sử dụng phương pháp CRT. Vấn đề là khi sinh chữ ký mà máy tính của Bob hoạt động không đều là nguyên nhân gây nên lỗi tính toán. Hay nói cách khác trong khi copy giữa các thanh ghi, một bit của dòng bít bị thất lạc. (Sự hoạt động không đều nguyên nhân có thể do xung đột điện từ hoặc cũng có thể do sâu phần cứng, các lỗi này đã sớm được tìm thầy trong các phiên bản của chíp Pentium). Được cung cấp một chữ ký lỗi, kẻ tấn công như Marvin có thể dẽ dàng phân tích thành nhân tử modul N. Bình thường Bob tính: Cp = Mdp mod p và Cq = Mdq mod q Với dp = d mod (p - 1) và dp = d mod (q - 1). Anh ấy thu được chữ ký C bằng cách: C = T1Cp + T2Cq (mod N), Với và Nhưng khi một lỗi đơn xẩy ra lúc Bob đang sinh chứ ký. Kết quả là Cp hoặc Cq sẽ sai. Giả sử là Cp đúng, nhưng thì không đúng. Kết quả của chữ ký là . Marvin nhận được , anh ta biết rằng đây là chữ ký sai vì . Tuy nhiên ta thấy rằng: khi Và kết quả là gcd() rất có giá trị đối với việc phân tích N thành nhân tử. Lưu ý là để thực hiện tấn công, Marvin phải biết đầy đủ về M. Cụ thể là, chúng ta giả sử rằng Bob không sử dụng bất kỳ một thủ tục sinh khóa ngẫu nhiên nào để tránh các tấn công trước. Một cách đơn giản để an toàn là Bob thực hiện kiểm tra trong lúc ký trước khi gửi chúng đi. Công việc kiểm tra là hết sức quan trọng vì khi sử dụng phương pháp CRT để cải thiện tốc độ, những lỗi ngẫu nhiên gặp phải rất nguy như đã trình bày ở phần trước. Nhiều hệ thống, bao gồm cả những hệ không cài đặt CRT, có thể bị tấn công bằng cách sử dụng những lỗi ngẫu nhiên này [3]. Tuy nhiên, trong thực tế kết quả thu được chưa được như tính toán lý thuyết. 3.8 Một số tấn công bằng nhân tử hóa số N với số N lớn Khi các sơ hở của hệ mật RSA được “bịt kín” thì người ta thường sử dụng một số tính toán sau đây để nhân tử hóa số N. 3.8.1 Tìm nhân tử lớn nhất thứ nhất Định lý 7 Fermat: Giả sử n là một số nguyên dương lẻ có dạng n = p.q. trong đó pq và p, q là các số nguyên tố. Khi đó biểu thức n có thể được viết dưới dạng: n = t2 – s2 (t, s là các số nguyên dương). Các số nguyên t, s, p và q có mối quan hệ: t = và s = Phương pháp này được xây dựng dựa trên định lý Fermat, cụ thể: Đặt x = 2. + 1, y = 1, r = - n. If r go to (4) r = r – y, y = y+2 goto (2) If r =0 then thuật toán dừng Khi đó chúng ta sẽ có: n = {Đây chính là hai nhân tử của n(p,q)} và là phân số có giá trị lớn nhất r = r + x x = x+2 goto (3) Thuật toán này đơn giản nhưng sử dụng nhiều vòng lặp 3.8..2 Phân tích thứ hai. Như chúng ta đã phân tích, độ an toàn của hệ mật RSA phụ thuộc vào độ khó của phép phân tích n thành các thừa số nguyên tố p, q. Nếu trong hai số nguyên tố p, q; số này nhỏ hơn số kia rất nhiều thì khả năng phân tích được n là rất cao. Vì thế khi thiết kế, các chuyên gia khuyên cáo nên chọn giá trị p, q sao cho p < < q và độ dài cảu pxấp xỉ bằng một nửa độ dài của n. Khí đó xác suất p nẳm trong khoảng () là rất cao. Bài toán đặt ra là cho n là số nguyên dương lẻ, d . Tìm nhân tử lẻ nhỏ nhất f sao cho d < f. Thuật toán được thực hiện như sau: Đặt r = n mod d {trong đó d = } r’ = n mod (d - 2) q = 4 s = ; If d> s thuật toán kết thúc với kết quả không tìm được nhân tử; Đặt d = d +2, x = r r = 2r – r’, r’ = x If r < 0, set r = r + d q = q + 1, goto (6) If r < d, set r = r –d q = q - 1, goto (5) If r = 0 then d là một thừa số của n Thuật toán kết thúc, ta sẽ thu được f = d Else goto (2) Ta thấy rằng thuật toán sẽ quét tất cả các giá trị lẻ nằm trong khoảng () 3.8.3 Phân tích thứ ba Ta lấy r số nguyên: m1, m2, . ., mr thỏa mãn gcd(mi, mj) = 1 Trước tiên ta lập ma trận S[i,j] với 1 thỏa mãn: 1 nếu j2 – n có nghiệm y S[i,j] = 0 nếu trái lại Thuật toán tiến hành như sau: Set x = và ki = (-x) mod mi. For 1 i r If S[i,j] = 1 For 1 i r goto (4) Set x = x + 1, ki = (ki -1) mod mi For 1 i r goto (2) Set y = If y2 = x2 – b then (x - y) là một nhân tử cần tìm của n và thuật toán kết thúc Else goto (3). Trong đó: - là số nguyên bé nhất mà lơn hơn hoặc bằng x. - là số nguyên lớn nhất mà nhỏ hơn hoặc bằng x. 3.8.4 Thuật toán Pollard (p-1) Giả sử n là B – mịn (tất cả các ước nguyên tố của nó đều B), Q là bộc chung nhỏ nhất của tất cả các lũy thừa của số nguyên tố B mà bản thân chúng n. Nếu q n thì l ln g ln n1, tức l là số nguyên bé nhất lớn hơn x) Khi đó ta có: Q = Trong đó tích lấy theo tất cả các số nguyên tố khác nhau q B. Nếu p là một thừa số nguyên tố của n sao cho p – 1 là B – mịn, thì p-1|Q và do đó với mọi a bất kỳ thỏa mãn gcd(a,p) = 1, theo định lý Fermat ta có: aQ 1(mod p). Vì vậy: Nếu lấy d = gcd(aQ – 1, n) thì p|d Nếu d = n coi như thuật toán không cho ta kết quả như mong muốn. Tuy nhiên điều đó sẽ không xẩy ra nếu n có ít nhất hai thừa số nguyên tố khác nhau. Cụ thể thuật toán như sau: Chọn một lần cho độ min B Chọn ngẫu nhiên một số nguyên a, 2 a n – 1 Tính d = gcd(a,n) If (2d) then d là kết quả cần tìm Với mỗi số nguyên tố q B thực hiện: Tính l = Tính a = aq1 mod n Tính d = gcd (a-1,n) If 1< d < n then cho kết quả (d) Else không tìm thấy kết quả nào thỏa mãn. Thuật toán Pollars phân tích n thành thừa số nguyên tố có hiệu quả đối với những số nguyên n là B mịn, người ta tính được thời gian thực hiện thuật toán là O(Bln n/ln B). 3.9 Kết luận Như vậy cho đến nay người ta mới công bố được một số phương pháp tấn công vào hệ thống mật mã RSA. Trong đó, phương pháp phân tích nhân tử modul N của RSA được nhiều nhà toán học tập trung nghiên cứu hơn cả. Tuy nhiên thuật toán sàng sàng bình phương đã và đang được chú ý hơn, mặc dù thuật toán cũng mới chỉ giải quyết cho trường hợp modul N có độ dài không lớn lắm. Nếu độ dài modul N của RSA mà lớn hơn thì cho đến nay chưa có một thuật toán nào khả thi được công bố. Chương 4 - THƯ VIỆN TÍNH TOÁN SỐ LỚN Trước khi xây dựng giải pháp tấn công RSA, chúng ta nghiên cứu cách biểu diễn số nguyên lớn cũng như các thuật toán số học làm việc với các số lớn đó trong máy tính. 4.1 Biểu diễn số lớn. Có nhiều cách để biểu diễn và lưu trữ số lớn. Cách thông thường nhất là biểu diễn bằng xâu ký tự. Cho một số lớn có n+1chữ số thập phân được biểu diễn trong hệ cơ số b, có dạng a = (an-1an-2…a0)b ta sử dụng một xâu ký tự s có độ dài n là ký tự để biểu diễn a theo cách: Chữ số a0 được lưu vào phần tử s[0] Chữ số a1 được lưu vào phần tử s[1] ……………………………………. Chữ số an-1 được lưu vào phần tử s[n-1] Dấu của số lớn được đặt trong biến trạng thái “dau”: Nếu dau = 1 thì a là số dương Nếu dau = -1 thì a là số âm Ta quy ước khi nói đến số lớn a thì a là xâu ký tự, các phần tử của xâu chính là các phần tử của số lớn được biểu diễn ở hệ cơ số b một cách tương ứng. Giả sử ta đang biểu diễn số lớn ở hệ cơ số c nào đó và ta muốn chuyển số lớn sang biểu diễn ở hệ cơ số b thông qua thuật toán sau: Input: số nguyên dương a, số nguyên dương b (2 b 256) Output: biểu diễn ở hệ cơ số b của a = (an-1an-2…a0)b , 0 n; an 0 Thuật toán: i = 0; x = A; q = ; ai = x – q.b; while (q > 0) i = i + 1; x = q; q = ; ai = x – qp; return (ai…a 0) 4.2 Các phép toán trong số lớn Ta quy ước số lớn biểu diễn trong hệ cơ số b = 10 4.2.1 So sánh hai số Input: Số Hai số lớn x = (xn-1 . . . x0), y = (ym-1…y0) có độ dài n và m Output: - Nếu x > y thì retum l. - Nếu x < y thì retum 0 - Nếu x = y thì return 2. Algorithm: 1. If (x dương, y âm) return 1; 2. If (x âm, y dương) return 0; 3: If (n > m)&&(x âm) return 0; // x <y 4. if (n y 5. If (n > m) && (x dương) return 1; //x >y 6. If (n < m) && (y dương) return 0; //x < y 7. If ( n == m) 7. l If (x dương) For ( i = n - 1 ; i 0; i--) If (x[i] > y[i]) return 1;// x >y Else return 0; 7.2 Else lf (x âm) For ( i = n-1; i-0; i--) If (x[i] > y[i]) return 0;//x <y Else If (x[i] y 8. return 2; 4.2.2 Cộng hai số lớn dương. Cho x, y là hai số lớn có độ dài lần lượt là n và m. Nếu số nào nhỏ hơn sẽ được chèn thêm 0 vào sao cho độ dài của hai số là bằng nhau. Cộng từng phần từ một của hai xâu lưu trữ hai số. Input: Hai số lớn x = (xn-1..x0), y = (ym-1..y0) có độ dài là n và m Output: z = x + y Algorithm: 1. temp=0, nho=0; // nho: biến lưu giá trị nhớ của phép cộng 2. If (n > m) temp = n; Else temp = m; 3. For (i = 0; i < temp, i++) z[i] = x[i]+y[i]+nho; if (z[i] > 9) z[i] = z[i] - 10; nho = l; else nho = 0; 4. Retum a; 4.2.3 Trừ hai số lớn dương Cho x, y là hai số lớn có độ dài lần lượt là n và m. Nếu số nào nhỏ hơn sẽ được chèn thêm 0 vào sao cho độ dài của hai số bằng nhau khi ta tiến hành trừ. Ta tiến trừ từng phần tử một của hai xâu lưu trữ hai số lớn. Input: Hai số lớn x = (xn-1..x0), y = (ym-1..y0) có độ dài là n và m Output: z = x – y Algorithm: 1. nho = 0; // nho: biến lưu giá trị nhớ của phép trừ 2. for (i=0;i < n; i++) 3. if (i > m) y[i] = 0;//chèn 0 vào nếu x có độ dải nhỏ hơn y 4. if (x[i] < y[i] + nho) z[i] = x[i] + 10 - y[i] - nho; nho = 1; else z[i] = x[i] - y[i] - 10; 5. nho = 0; 6. Xét dấu cho z; 4.2.4 Phép nhân hai số lớn. 4.2.4.1 Nhân số lớn với một số nguyên Input: Số lớn x = (xn-1..x0) và số nguyên k Output: z = x*k, z có độ dải tối thiểu bằng n Algorithm: l. nho = 0 ; temp; 2. for (i = 0; i<n; i++) 3. temp = x[i]*k + nho; 4. z[i] = temp % 10; 5. nho = (temp - z[i])/10; 6. Độ dài của z 1à n; 7. if(nho != 0) 8. while (nho !=0) 9. n = n+l; //Tăng độ dài của z, 10. z[i] = nho % 10; 11. nho = (nho - z[i])/10; 12. i++; 13. retum z; 4.2.4.2 Nhân hai số lớn Cho hai số lớn x = (xn-1..x0), y = (ym-1..y0) có cần tính z = x.y có độ dài là (n+m). Để nhân hai số lớn ta tiến hành như sau: - Lấy phần tử của số hạng thứ hai nhân với tất cả các phần tử của số hạng thứ nhất hay nói cách khác lấy từng phần tử của y nhân với toàn bộ x cộng thêm một phần tử nhớ, được kết quà đem chia cho hệ cơ số, lấy số dư làm kết quả của hàng tương ứng, thương số là số nhớ của số mới. - Dịch trái một số bước phù hợp. - Cộng tất cả các kết quả nhân lại Cụ thể thuật toán nhân hai số lớn như sau: Input: Hai số lớn x = (xn-1..x0), y = (ym-1..y0) có độ dài là n và m Output: z = x * y Algorithm: 1. i, temp, nho; 2. BigNum b; 3. for (i=0; i < m; i++) 4. temp = y[i]; b = x * temp; // Nhân một số lớn với một số nguyên 5. Dichtrai (b,i); // dịch trái b, i vị trí; 6. z = z + b; 7. retum z; 4.2.5 Phép chia hai số lớn dương. Cho hai số lớn x = (xn-1..x0), y = (ym-1..y0) có độ dài là n và m, ta xét hai trường hợp sau: 4.2.5.1 Phép chia hai số lớn có thương nhỏ hơn hoặc bằng 9 Input: Hai số lớn x = (xn-1..x0), y = (ym-1..y0) có độ dài là n và m Output: z = x / y, z có độ dài là k = n – m; Algorithm: 1. For i = 0 to i = 10 do 2. BigNum c ; 3. c = b*i ; // Nhân một số lớn với một số nguyên 4. If (Sosanh(c,a)==1) return i-1 ;//c>a 5. Else IF(Sosanh(c,a)==2) retum i ;//c=a 4.2.5.2 Chia hai số lớn Thuật toán chia hai số lớn dựa trên ý tưởng của phép chia thông thường Input : Hai số lớn x, y có độ đài n, m Output : z – x/y Algorithm: 1. BigNum b, z, c1 ; 2. If ( y[0] == 0 && m = 1) cout << “ Loi Chia Cho 0”; return b; 3. If ( x < y ) 3.1. z = 0; 3.2 Độ dài của b là 1; 3.3 dau = l;// b dương 3.4 return z; 4. t, i = 0 5. for j = n – 1 down to j 0 // đảo ngược 5.1. Độ dài của số lớn b là ; 5.2 b[0] = x[j]; 5.3 if ( j == n - 1) then c1 = c1 + b; else Dich(c1,1);// Dịch c1 sang trái 1 vị trí c1 = c1 + b; Chuan(c1); // loại bỏ các số 0 : dạng 0001 thành 12 5.5 if( Sosanh(c1,y) != 0){ t = Chia(c1,y);// chia hai số lớn có thương 9 t b = y * t; z[i] = t; i++; c1 = c1- b; Chuan(c1); 5.6 If(i != 0) then z[i]=0 ; i++; 6. Độ dài của z là i; 7. Giá trị dấu của z = giá tri dấu của x * giá trị dấu của y 8. z = dao(z); // đảo ngược lại số z ; 9. retum z; 4.2.6 Lũy thừa Input: a, k Zn Output: ak mod n Algorithm: 1. Đưa k về dạng: k= ở đây dạng biểu diễn này chính là dạng biểu diễn trong hệ cơ số 2 của k. 2. Xét b =1 và nếu k = 0 thì b là kết quả 3. Xét A = a 4. Nếu k0 = 1 thì b = a 5. For (i = 1; i < t; i++) 5.1 A = A.A mod n 5.2 Nếu k1 = 1 thì b = A.b mod n 6. Return b; 4.2.7 Ước chung lớn nhất Sử dụng thuật toán Euclidean mở rộng tìm ước chung lớn nhất của 2 số. Input: Hai số lớn a, b với a> b Output: d = gcd(a,b) và 2 số nguyên x,y thỏa mãn a.x + b.y = d Algorithm: 1. if( b== 0) then {d = a; x = 1; y = 0; return (d, x, y);} 2. a1 = 1; a2 = 0; a3 = a; b1 = 0; b2 = 1 ; b3 = b; 3. q = a3 div b3; 4. While (b3!= 0) 4.1. c1 = a1; c2 = a2; c3 = a3; 4.2. a1 = b1; a2 = b2; a3 = b3; 4.3. b1 = c1 – q.b1; b2 = c2 – q.b2; b3 = c3 – q.b3; 5. If (a2 < 0) then a2 = a + a2 6. d = a2; x.= a1; y = a3; 7. return (d, x, y); 4.2.8 Phép nhân theo module p Để tính a.b mod p, ta biều diễn b dưới dạng nhị phân b = trong đó bj = 0 hoặc bằng 1. Áp dụng thuật toán Horner: a.b mod p = ~2;.b) Thuật toán tính a.b mod p như sau: Input: Ba số lớn a, b, p Output: z = a.b mod p Algorithm: b = ; 2. z = a; 3. For (i = k - 1; i 0; i--) z = z2 mod p; If (bj = 1) then z = z + a; 4. return z; 4.2.9 Tìm phần từ nghịch đảo theo module p Để tính nghịch đảo, chúng ta sẽ sử dụng thuật toán Euclidean mở rộng. Cụ thể: Algorithm: Input: a Zn với gcd(a, n) =1 Output: a-1 mod n Sử dụng giải thuật Euclidean mở rộng tìm x, y thỏa mãn điều kiện ax + by = d và d = gcd(a,n). Nếu d > 1 thì a-1 mod n không tồn tại, nếu ngược lại thì x là giá trị cần tìm. 4.2.10 Phép cộng có dấu Phép cộng hai số có dấu được thực hiện dựa trên phép so sánh, phép cộng và phép trừ hai số không âm đã trình bảy. Dấu của số lớn được lưu bít cao nhất của số lớn Thuật toán cộng hai số lớn có dấu được thực hiện như sau: Input: Hai số lớn x, y Output: z = x + y; Algorithm: 1. If (x, y cùng dấu) 1.1. z = x + y; 1.2.Đăt z cùng dấu với x; 1.3. Return z; 2. if (x dương) // y âm 2.1. If(s = Sơsanh(x,y)!=0) Retum z = x - y; 2.2. If(s==0) z = y - x; Đặt z cùng dấu với y; return z; 3. if (x âm) // y dương 3.1. if((s = Sosanh (x,y))==0) Retum z = y - x; 3.2 if(sl==0) z = x.y; Đặt z cùng dấu với x; Retum z 4.2.11 Phép trừ có dấu Phép trừ hai số có dấu được thực hiện dựa trên phép cộng hai số có. Cụ thể: Input: Hai số lớn x, y Output: z = x -y Algorithm: 1. Đổi dấu của y; 2. Cộng có dấu z = x + y; 3. retum z; 4.3.12 Phép nhân có dấu Phép nhân hai số có dấu được thực hiện dựa trên phép nhân hai số không âm đã được trình bày ở trên. Thuật toán nhân hai số có dấu như sau: Input: Hai số lớn x, y Output: z = x * y; Algorithm: 1. If (x, y cùng dấu) return z = x.y; 2. If(x, y khác dấu) z = x.y; Đổi dấu z; 3. Return z; Chương 5 - PHƯƠNG PHÁP TẤN CÔNG BẰNG NHÂN TỬ HOÁ SỐ N SỬ DỤNG ĐỊNH LÝ FERMAT 5.1 Bổ đề 1 Giả sử rằng n=p.q với p#q là hai số nguyên tố lẻ. Ngoài ra ta giả thiết rằng p < q. Khi đó: i/ p < < q ii/ Số p gần hơn số q. Tức là giả sử , > 0 sao cho: p + = = q - , khi đó < Chứng minh: i/ Hiển nhiên đúng ii/ Từ kết quả ở i/ ta suy ra có tồn tại hai số dương , sao cho: p = - và q = + Từ đó: n = p.q = ( - )( + ) = n - + - Hay: ( - ) - =0 (1) ( - ) = hay = - Do , > 0 và > 0 nên - > 0 => # vì nếu = thì từ (1) ta suy ra = 0. T Từ đó hoặc = 0 hoặc = 0. Nhưng nếu = 0 thì p = vô lý, tương tự nếu = 0 thì q = cũng vô lý. Mệnh đề được chứng minh Từ bổ đề 1 ta suy ra rằng giữa hai nhân tử nguyên tố của số n thì nhân tử bé hơn p gần hơn so với số q. 5.2 Định lý Fermat Định lý 7 Fermat: Giả sử n là một số nguyên dương lẻ có dạng n = p.q. trong đó pq và p, q là các số nguyên tố. Khi đó biểu thức n có thể được viết dưới dạng: n = t2 – s2 (t, s là các số nguyên dương). Các số nguyên t, s, p và q có mối quan hệ: t = và s = Phương pháp này được xây dựng dựa trên định lý Fermat, cụ thể: Đặt x = 2. + 1, y = 1, r = - n. If r go to (4) r = r – y, y = y+2 goto (2) If r =0 then thuật toán dừng Khi đó chúng ta sẽ có: n = {Đây chính là hai nhân tử của n(p,q)} và là phân số có giá trị lớn nhất r = r + x x = x+2 goto (3) Ví dụ: Cho n = 9401 x = 2. + 1 = 193 y = 1, r = - n = -185 Duyệt từ trên xuống dưới từ trái qua phải theo cột r, y, x R Y X R Y X R Y X -185 1 193 167 13 197 7 29 197 8 1 195 154 15 197 -22 31 197 7 3 195 139 17 197 175 31 199 4 5 195 122 19 197 144 33 199 -1 7 195 103 21 197 111 35 199 194 7 197 82 23 197 76 37 199 187 9 197 59 25 197 39 39 199 178 11 197 34 27 197 0 41 199 vậy n = 9401 = = = 79. 119 p = 79 q = 119 KẾT LUẬN Hơn hai thập niên nghiên cứu vào các bài toán tính toàn về RSA để tìm sự tấn công hiệu quả nhưng không có một tấn công hiệu quả nào được tìm ra. Những sự tấn công được khám phá cho đến nay chủ yếu minh hoạ các cạm bẫy phải tránh trong quá trình cài đặt RSA. Lúc này có vẻ như sự cài đặt đúng cách có thể đảm bảo được an ninh trong thế giới số. Chúng ta phân loại tấn công RSA ra thành 5 loại: Tấn cơ bản khai thác sự sai sót của hệ thống Tấn công khoá riêng có số mũ thấp không đủ, khoá riêng có số mũ thấp không bao giờ được sử dụng. Tấn công khoá công khai có số mũ thấp Tấn công trong cài đặt Tấn công bằng cách nhân tử hoá Hệ mật mã RSA đựơc cài đặt và triển khai đúng theo chuẩn mà các nhà phát triển RSA đã khuyến cáo có độ an toàn cao. Nhưng ngày nay với sự phát triển rất nhanh của các hệ tính toán số hứa hẹn trong tương lai sẽ có một cuộc chạy đua giữa các hệ tính toán số với các nhà phát triển RSA TÀI LIỆU THAM KHẢO Tài liệu tiếng việt: [1] Đặng Văn Cương - Vấn đề an toàn của hệ mật mã khoá công khai - Luận văn thạc sĩ, Khoa công nghệ thông tin - Đại học công nghệ 2003 [2] Nguyễn Thị Miền – Thanh toán từ xa – Luận văn đại học, Khoa công nghệ thông tin - Đại học công nghệ 2008 [3] Nguyễn Minh Hải - Đấu thầu từ xa - Luận văn đại học, Khoa công nghệ thông tin - Đại học công nghệ 2008 [4] Đặn Thị Lan Hương - Vấn đề an toàn thông tin trong thương mại điện tử - Luận văn đại học, Khoa công nghệ thông tin - Đại học công nghệ 2008 [5] Phan Đình Diệu – Lý thuyết mật mã và an toàn thông tin, Đại học quốc gia Hà Nội 2002 [6] Trịnh Nhật Tiến – Giáo trình an toàn dữ liệu – Khoa công nghệ thông tin, Đại học quốc gia Hà Nội Tài liệu tiếng anh: [7] D.Bleichenbacher. Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1 [8] D.Boneh, R.Demillo, and R.Lipton. On the importance of checking cryptographic protocols for faults. [9] D.Boneh and G.Durfee. New results on cryptanalysis of low private exponent RSA. Preprint, 1998 [10] Mark Stamp Richard M.Low: “Applied Cryptanalysis”, A John Wiley & Sons INC publication, San Jose state University, San Jose CA 2007 [11] M. Wiener. Cryptanalysis of short RSA secret exponents. IEEE Transactions on Information Theory, 1990 [12] Neal Koblitz: “ A course in Number theory and Cryptography” New York, Berlin Heidelberg, London, Paris, Tokyo, 1987 [13] J. Hastad. Solving simultaneous modular equation of low degree. SIAM J. of Computing, 1988 [14] [15] [16] S. Goldwasser. The search for provably secure cryptosystems. In Cryptology and computational number theory, volume 42 of Proceeding of the 42nd Symposium in Applied Mathematics. American Mathematical Society, 1990