Từ khi được công bố, hệ mật mã RSA đã được đánh giá là rất an toàn và “khó” có thể bị tấn công, tuy nhiên liệu hệ mật mã RSA có hoàn hảo đến thế? Liệu có phương pháp nào để tấn công và khôi phụ được khóa bí mật trong hệ mật mã RSA? Khi hoàn thành bài đọc này, bạn đọc có thể có được những hiểu biết cơ bản về liên phân số và có thể hiểu rõ được bản chất của phương pháp tấn công được trình bày trong bài.
Trong bài này chúng ta sẽ tìm hiểu về Định lý Wiener được nhà toán học Michael James Wiener trình bày trong công bố của ông mang tên Cryptanalysis of short RSA secret exponents vào năm 1989. Với việc sử dụng định lý này, chúng ta hoàn toàn có thể khôi phục được khóa bí mật nếu biết khóa công khai dựa vào điểm yếu mũ giải mã bé.
Để sử dụng hệ mật mã RSA ta cần sinh khóa công khai và khóa bí mật . Người dùng sinh khóa công khai và gửi cho người khác để mã hóa và giữ lại cho mình khóa bí mật để giải mã.
Người ta mã hóa bản rõ (plaintext) bằng cách tính:
và giải mã bản mã(ciphertext) bằng cách tính:
Quay lại với câu hỏi, liệu hệ mật mã RSA có thể bị tấn công? Câu trả lời dĩ nhiên là có, hệ mật mã RSA tuy hoàn hảo nhưng nó vẫn có điểm yếu và điểm yếu chí mạng của nó lại nằm ở cách người dùng sử dụng nó, có thể kể đến một số phương pháp khai thác lỗi như:
- Chọn số module quá bé (dưới 1024 bit, có thể bị phân tích thành nhân tử [3], hiện tại theo khuyến nghị [4], chúng ta nên sử dụng số module ít nhất là 2048 bit);
- Chọn mũ mã hóa bé (để tăng tốc độ mã hóa người ta sử dụng mũ mã hóa rất bé, việc sử dụng mũ mã hóa quá bé như vậy dẫn tới bản rõ có thể bị dễ dàng khôi phục);
- Sử dụng mũ mã hóa trùng nhau (Hastad Broadcast Attack);
- Chọn bản rõ quá bé (việc sử dụng bản rõ quá bé sẽ dẫn tới trường hợp sau khi tính; và phép tính theo module sẽ không còn tác dụng, kẻ tấn công có thể khôi phục bản mã nhanh hơn và dễ dàng hơn);
- Tấn công Fermat (sử dụng khi hiệu và bé, theo tài liệu nghiên cứu [5], nếu thì có thể khôi phục được khóa bí mật và );
- Mũ giải mã bé (Wiener đã phát hiện ra phương pháp tấn công lên hệ mật mã RSA khi [6]. Sau đó Boneh và Durfee đã phát hiện ra phương pháp tấn công mạnh mẽ hơn khi [7])
- …
Hôm nay chúng ta sẽ tìm hiểu về liên phân số và sử dụng liên phân số (continued fraction) như một phương pháp tấn công lên hệ mật mã RSA khi người dùng chọn mũ giải mã bé (tấn công Wiener). Với phương pháp này, chúng ta hoàn toàn có thể khôi phục khóa bí mật được sử dụng trong hệ mật mã RSA.
Liên phân số còn có tên gọi khác là phân số liên tục, trong bài này tác giả sẽ sử dụng thuật ngữ liên phân số.
Liên phân số được phát minh vào năm 1680 bởi nhà toán học và vật lý Christiaan Huygens với mục đích tìm ra giá trị gần đúng nhất của số thực. Liên phân số được ứng dụng trong nhiều lĩnh vực như lý thuyết xấp xỉ (Approximation theory), lý thuyết số đại số (Algebraic number theory), lý thuyết xác xuất. Trong những năm gần đây liên phân số còn được ứng dụng rất nhiều vào mật mã.
Liên phân số trên trường số nguyên là biểu thức có dạng:
với . Nếu số lượng hữu hạn, ta gọi đây là liên phân số hữu hạn và được gọi là phần tử của liên phân số.
Ta có thể sử dụng cách viết khác gọn hơn đó là
Tính chất của liên phân số
Định lý Legendre trong phân số liên tục: Nếu là một số thực và là số nguyên dương sao cho , thì là hội tụ của liên phân số .
Chứng minh của định lý các bạn có thể xem tại [9]
Là giải thuật để tính ước chung lớn nhất (ƯCLN) của hai số nguyên, là số lớn nhất có thể chia được bởi hai số nguyên đó với số dư bằng không. Giải thuật này được đặt tên theo nhà toán học người Hy Lạp cổ đại Euclid, người đã viết nó trong bộ Cơ sở của ông (khoảng năm 300 TCN).
Định lý 1: Cho , trong đó và là số nguyên tố thỏa mãn . Với mọi số nguyên thỏa mãn điều kiện
thì có liên phân số hội tụ tới phân số [6].
Chứng minh
Ta nhận thấy rằng, và là 2 số nguyên tố cùng nhau, nên nếu là hội tụ của liên phân số và thì và .
Định lý trên cho phép chúng ta phân thích module thành nhân tử. Giả sử chúng ta biết cặp khóa công khai của hệ mật mã RSA. Ta có thể dò phân số hội tụ của liên phân số và kiểm tra có phải là nghiệm của phương trình bậc 2 sau hay không:
cho (các bạn nhớ là ở trên và ở dưới nhé)
Giải thích
Ví dụ
Tác giả mô tả code bằng ngôn ngữ lập trình python 3 nhằm thực thi tấn công Wiener, sau đây là code của chương trình, đầu vào của chương trình là khóa công khai và , đầu ra của chương trình theo thứ tự sẽ là các khóa bí mật .
Đầu tiên ta xây dựng hàm
is_perfect_square để kiểm tra số đó có phải số chính phương hay khôngCode minh họa
Sau đó xây dựng hàm tấn công
Attack_Wiener :Code minh họa
- Tìm hiểu về hệ mật mã RSA và vai trò của nó trong cuộc sống (phần 1). https://www.math2it.com/bai-viet/tim-hieu-ve-he-mat-ma-rsa-va-vai-tro-cua-no-trong-cuoc-song-phan-1/
- Tìm hiểu về hệ mật mã RSA và vai trò của nó trong cuộc sống (phần 2). https://www.math2it.com/bai-viet/tim-hieu-ve-he-mat-ma-rsa-va-vai-tro-cua-no-trong-cuoc-song-phan-2/
- Burt Kaliski (2003), Twirl And RSA Key Size, RSA Laboratories.
- Barker, E. B., & Dang, Q. H. (2009). Recommendation for Key Management Part 3: Application-Specific Key Management Guidance. https://doi.org/10.6028/nist.sp.800-57pt3r1
- Weger, B.D. (2002). Cryptanalysis of RSA with Small Prime Difference. Applicable Algebra in Engineering, Communication and Computing, 13, 17-28.
- Wiener M. Cryptanalysis of short RSA secret exponents // IEEE Trans. Inform. Theory. 1990. Vol. 36. P. 553558.
- Boneh, D., Durfee, G. (1999). Cryptanalysis of RSA with Private Key d Less than N^0.292 . In: Stern, J. (eds) Advances in Cryptology — EUROCRYPT ’99. EUROCRYPT 1999. Lecture Notes in Computer Science, vol 1592. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48910-X_1
- A001203 , Simple continued fraction expansion of Pi. https://oeis.org/A001203
- Hardy, G. H.; Wright, E. M. (1938). An Introduction to the Theory of Numbers. London: Oxford University Press. pp. 140–141, 153.
- May A. New RSA Vulnerabilities Using Lattice Reduction Methods. PhD thesis. University of Paderborn. 2003.
