Khuyến nghị độ dài các tham số sử dụng cho hệ thống mật mã RSA trong một số tiêu chuẩn mật mã
GIỚI THIỆU HỆ THỐNG MẬT MÃ RSA
Trong Tạp chí An toàn thông tin số 4 (074) 2023 [1] đã giới thiệu tổng quan về hệ thống mật mã RSA, bao gồm hai nguyên thủy là hệ mật khóa công khai và lược đồ chữ ký số RSA đang được áp dụng rất phổ biến trong hệ thống mạng công nghệ thông tin hiện nay như trong: các hạ tầng PKI, các giao thức bảo mật và trong các thiết bị phần cứng và phần mềm về an toàn thông tin.
Hệ thống mật mã khoá công khai RSA là một trong các hệ thống mật mã mà độ an toàn của nó dựa trên tính khó giải của bài toán phân tích số nguyên thành các nhân tử nguyên tố, ở đây là bài toán phân tích RSA modulo N thành các nhân tử nguyên tố p và q. Do đó khi sinh bộ tham số khóa RSA đòi hỏi các số nguyên tố p, q và cặp khóa bí mật, công khai d, e phải được chọn sao cho việc phân tích modulo N là không thể về mặt tính toán. Để đạt được yêu cầu trên, trước hết p, q phải là các tham số nguyên tố mạnh và đủ lớn, phụ thuộc vào tốc độ và kỹ thuật tính toán được sử dụng khi thực hiện bài toán phân tích số nguyên.
Hiện nay, các hệ mật khóa công khai và lược đồ ký số của hệ thống mật mã RSA đã được chuẩn hóa và đang được sử dụng rất rộng rãi như RSA-OAEP, RSAES-PKCS1 và RSASSAPSS, RSASSA-PKCS1 [3]. Trong 4 lược đồ trên thì nhóm tác giả trình bày hai chuẩn tiêu biểu là lược đồ mã hóa công khai RSA-OAEP và lược đồ ký số RSA-PSS.
Lược đồ mã hóa RSA-OAEP
Lược đồ mã hoá khoá phi đối xứng RSA[1]OAEP, gọi tắt là Lược đồ RSA-OAEP được Bellare và Rogaway xây dựng dựa trên cơ chế mã hoá đưa từ năm 1995 [2], sau đó được chuẩn hoá thành tài liệu PKCS #1 v2 năm 2002 bởi RSA Laboratories và được cập nhật mới nhất trong PKCS #1 v2.2 [3].
Lược đồ RSA-OAEP cung cấp cho người dùng một phương pháp sử dụng nguyên thuỷ RSA để mã hoá các thông điệp, đặc biệt là các thông điệp nhỏ. Trong [2] đã chỉ ra lược đồ này là an toàn chứng minh được trong mô hình bộ tiên tri ngẫu nhiên, tức là an toàn dưới việc giả thiết rằng các hàm băm được sử dụng trong lược đồ hoạt động như các bộ tiên tri ngẫu nhiên. Cho đến nay tính an toàn chứng minh được của lược đồ RSA-OAEP trong mô hình ROM vẫn được thừa nhận là đúng đắn.
Độ an toàn thực tế của lược đồ RSA-OAEP phụ thuộc vào tính khó giải của bài toán phân tích số cùng với tính an toàn của các nguyên thuỷ mật mã sử dụng trong lược đồ. Điều này có nghĩa là, việc sử dụng lược đồ RSA-OAEP an toàn cần gắn với các tiêu chuẩn về tham số RSA và các nguyên thuỷ mật mã có liên quan khác.
Cho đến thời điểm này, lược đồ mã hoá khoá phi đối xứng RSA-OAEP vẫn là một lược đồ được chấp nhận và chuẩn hoá trong các tiêu chuẩn mới nhất như PKCS #1 v2.2 [3], ISO/IEC 18033- 2 [4],… Các báo cáo, rà soát mới nhất về các thuật toán, giao thức mật mã của Cơ quan An ninh thông tin Cộng hòa Liên bang Đức (BSI) [5] hoặc báo cáo của Cơ quan mật mã Liên minh châu Âu (ECRYPT-CSA) [6] đều công nhận lược đồ RSA-OAEP là an toàn khi được sử dụng với các tham số và nguyên thuỷ mật mã phù hợp.
Lược đồ chữ ký số RSA-PSS
Lược đồ chữ ký số RSA-PSS thực chất là lược đồ chữ ký số RSASSA-PSS được chuẩn hoá lần đầu vào năm 2002 [2]. Cho đến nay, lược đồ chữ ký số RSA-PSS vẫn là một trong những thuật toán chữ ký số được chấp nhận rộng rãi và chuẩn hoá trong hầu hết các chuẩn trên thế giới. Có thể kể đến các chuẩn như PKCS #1 v2.2 [3], chuẩn chữ ký số của Mỹ FIPS PUB 186-4 [7] và dự thảo mới nhất của chuẩn này là FIPS PUB 186-5 [8], chuẩn ISO/IEC 14888-2:2008 [9].
Độ an toàn của lược đồ chữ ký số RSA-PSS trên thực tế phụ thuộc vào tính khó giải của bài toán phân tích số, do đó phụ thuộc vào các tham số được sử dụng trong lược đồ. Còn trong các mô hình lý thuyết, lược đồ RSA-PSS đã được chứng minh là không thể bị giả mạo dưới tấn công sử dụng thông điệp được lựa chọn, hay nói cách khác là đạt độ an toàn UF-CMA trong mô hình bộ tiên tri ngẫu nhiên [10]. Trong các báo cáo mới nhất của BSI [8] và ECRYPT-CSA [3], thuật toán chữ ký số RSA-PSS vẫn được đánh giá là một thuật toán chữ ký số an toàn và hiệu quả trong sử dụng với điều kiện các tham số và nguyên thuỷ mật mã sử dụng trong đó là an toàn.
KHUYẾN NGHỊ ĐỘ DÀI THAM SỐ HỆ THỐNG MẬT MÃ RSA TRONG MỘT SỐ TIÊU CHUẨN
Phần này bài báo trình bày chi tiết về khuyến nghị độ dài các tham số sử dụng cho hệ thống mật mã RSA như thừa số modulo, số mũ bí mật, số mũ công khai và các thừa số nguyên tố trong một số tiêu chuẩn mật mã của châu Âu, Đức và Mỹ.
Tham số modulo n
Trong thời gian qua, việc giải bài toán phân tích số đã đạt được các tiến bộ như sau: năm 2005 phá được hệ mật RSA có modulo 640 bit [11], năm 2009 phá được 47 hệ mật RSA với giá trị modulo 768 bit [12]. Những kỷ lục này đã được thiết lập với thuật toán Sàng trường số (NFS) [13] được sử dụng để phân tích số. Do đó theo báo cáo mới vào năm 2018 của ECRYPT-CSA [6], sẽ là không an toàn nếu sử dụng hệ mật RSA với giá trị modulo có độ lớn 1024 bit và trong thời gian tới chỉ nên sử dụng các hệ mật RSA với giá trị modulo có độ lớn 3072 bit trở lên. Các giá trị tương ứng giữa ngưỡng an toàn và độ lớn modulo được khuyến cáo bởi một số chuẩn mật mã trên thế giới được thể hiện trong Bảng 1 [18].
Bảng 1. Khuyến nghị độ dài số modulo n tương ứng với mức an toàn trong một số chuẩn trên thế giới
Theo chuẩn BSI mới nhất năm 2023 thì việc sử dụng số mudulo trong hệ thống mật mã RSA có độ dài 3200 bit tương ứng với mức an toàn 128 có thể sử dụng an toàn tới năm 2028 và có thể lâu hơn nữa. Dự đoán này được đưa ra dựa trên việc suy đoán về phát triển của máy tính lượng tử.
Các thừa số nguyên tố p và q
Trong các hệ mật RSA, giá trị modulo n luôn có dạng n = p⋅q, trong đó p, q là các số nguyên tố. Để bài toán phân tích là khó giải, ngoài yêu cầu chung về độ dài bit của n, ta cần phải đến các tiêu chí cụ thể cho hai thừa số nguyên tố p, q này.
Thứ nhất các số nguyên tố p, q phải có cùng độ lớn bit nhưng không được quá gần nhau. Yêu cầu này là bởi các lý do sau đây:
- Nếu p, q có độ lớn bit quá chênh lệch, chẳng hạn l(p) ≪ l(q), ở đây ký hiệu l(x) là độ dài bit của số nguyên x, khi đó ta có thể áp dụng phương pháp phân tích số sử dụng đường cong elliptic (phương pháp ECM) để phân tích n [14]. Do đó cần phải sinh p, q sao cho phương pháp ECM không thể áp dụng được. Theo [6] và từ phương pháp ECM, với các giá trị p, q thoả mãn 0.1<|l(p)-l(q)|<20 thì phương pháp ECM sẽ không thể áp dụng được.
- Nếu các giá trị p, q quá gần nhau, cụ thể nếu |p-q| < n1/4 thì có thể áp dụng phương pháp Coppersmith để phân tích n trong [15]. Do đó, cần sinh các số nguyên tố p, q thoả mãn |p-q|≥n1/4.
Từ hai lý do trên, ta thấy rằng với các số nguyên tố p, q có độ dài bit xấp xỉ l(n)/2 và thoả mãn điều kiện |p-q| ≥ n1/4 thì cả hai phương pháp phân tích ở trên đều không thực hiện được.
Tuy nhiên, theo FIPS 186-4 thì điều kiện đặt ra mạnh hơn, theo đó các số nguyên tố p, q phải thoả mãn |p-q| > 2(nlen/2)-100.
Số mũ công khai e và số mũ bí mật d
Do các thuật toán ký số RSA cần phải có quá trình xác minh chữ ký nhanh, hiệu quả, cho nên các chuẩn trên thế giới đều lấy e là số nguyên dương lẻ và có độ lớn tương đối nhỏ. Chẳng hạn, trong NIST SP 800-56B, số mũ công khai e được chọn là một số nguyên dương lẻ thoả mãn 65537<e< 2256. Còn trong chuẩn FIPS 186-4, thì số mũ công khai e được yêu cầu là số nguyên dương lẻ thoả mãn 216< e <2256.
Đối với số mũ bí mật d, các tiêu chuẩn được đề xuất nhằm kháng lại các tấn công sử dụng lý thuyết lưới để khám phá d. Tiêu biểu là các tấn công của Wiener [16], tấn công của Boneh và Durfee [17]. Nếu ta ký hiệu e = nα , d = nδ thì điều kiện để kháng lại các tấn công này là δ >7/6- 1/3(1+6α)1/2. Từ tiêu chuẩn về độ lớn cho số mũ công khai e, ta hoàn toàn có thể tính được tiêu chuẩn độ lớn cho số mũ bí mật d. Theo FIPS 186-4 đưa ra cho d là: 2nlen/2<d< lcm(p-1,q-1).
KẾT LUẬN
Bài báo đã đưa ra các khuyến nghị rất cụ thể về độ dài các tham số sử dụng trong hệ thống mật mã RSA trong một số chuẩn mật mã phổ biến trên thế giới và một số công trình liên quan. Với các khuyến nghị được đưa ra thì đây có thể xem là tài liệu rất tốt cho các nhà phát triển hệ thống, các sản phẩm phần mềm, phần cứng bảo mật có sử dụng hệ thống mật mã RSA.
|
TÀI LIỆU THAM KHẢO [1]. Phạm Quốc Hoàng, Đặng Tuấn Anh, Một số khuyến nghị về độ an toàn của hệ mật RSA (Phần 1), Tạp chí An toàn thông tin số (4) 2023. [2]. M. Bellare and P. Rogaway, “Optimal Asymmetric Encryption -- How to encrypt with RSA. Extended abstract in Advances in Cryptology - Eurocrypt '94 Proceedings,” Lecture Notes in Computer Science Vol. 950, Springer-Verlag, 1995. [3]. PKCS #1 v2.2, “RSA cryptography standard. RSA Laboratories”, 2016. [4]. ISO/IEC 18033-2. Information technology - Security techniques -Encryption algorithms - Part 2: Asymmetric Ciphers. International Organization for Standardization, 2017. [5]. Cryptographic Mechanisms: Recommendations and Key Lengths, TR02102-1 v2023-01, BSI, 03/2023. [6]. N. P. Smart, “Algorithms, Key Size and Protocols Report”, ECRYPT-CSA, H2020-ICT-2014-Project 645421, 02/2018. [7]. C. Kerry, and P. Gallagher, “FIPS PUB 186-4: Digital Signature Standard (DSS)”, Federal Information Processing Standards Publication. National Institute of Standards und Technology, 2013. [8]. FIPS 186-5 (Draft). Digital Signature Standard (DSS), 2019. [9]. ISO/IEC 14888-2:2008 Information technology - Security techniques - Digital signatures with appendix - Part 2: Integer factorization based mechanisms. [10]. Saqib A. Kakvi Eike Kiltz, “Optimal Security Proofs for Full-Domain Hash”, Cambridge, EUROCRYPT 2012. [11]. Jens Franke, “RSA576. Post to various internet discussion boards/email lists”, 2005. [12]. Thorsten Kleinjung, Kazumaro Aoki, and et al, “Factorization of a 768-bit RSA modulo”, 2009. [13]. Arjen K. Lenstra and Hendrik W. Lenstra, “The development of the number field sieve”, volume 1554 of Lecture Notes in Mathematics. Springer, 1993. [14]. Hendrik and Lenstra, “Factoring integers with elliptic curves. Annals of Mathematics”, 126(3):649-673, 1987. [15]. Don Coppersmith, “Small solutions to polynomial equations, and low exponent RSA vulnerabilities”, Jounal Cryptology, 10(4):233-260, 1997. [16]. Wiener, “Cryptanalysis of short RSA secret exponents.” IEEE Transactions on Information Theory, 36 (3), 553- 558, 1990. [17]. Boneh, D. and G. Durfee, “Cryptanalysis of RSA with private key d less than N 0.292.” IEEE Transactions on Information Theory, 46 (4), pp. 1339-1349, 2000 [18]. Damien Giry, “BlueKrypt v32.3 - Crytographic key length recommendation”, 2020. |
TS. Đỗ Quang Trung, TS. Nguyễn Văn Nghị (Học viện Kỹ thuật mật mã)
