Xem xét mức an toàn đối với độ dài khóa RSA

Hệ thống mật mã RSA (thuật toán mã hóa khóa công khai, lược đồ chữ ký số) cũng như tất cả các nguyên thuỷ mật mã khác, mô hình hệ mật, cấu trúc thuật toán của các nguyên thủy mật mã trong hệ thống mật mã RSA là công khai. Tuy nhiên, việc lựa chọn và sử dụng các tham số cho hệ thống mật mã này sao cho an toàn và hiệu quả là một vấn đề đã và đang được nhiều tổ chức, các nhà khoa học quan tâm nghiên cứu. Trong bài viết này chúng tôi tổng hợp và giới thiệu về các kết quả và dự đoán về khả năng thám mã RSA dựa trên phân tích RSA mô đun lô, các độ dài RSA mô đun lô hiện tại được cho là an toàn, từ đó đưa ra khuyến cáo về độ dài mô đun lô RSA dùng cho các ứng dụng bảo mật và an toàn thông tin.

GIỚI THIỆU

Hệ thống mật mã RSA được đặt tên theo các chữ cái viết tắt tên ba tác giả phát minh ra hệ thống mật mã này là Ron Rivest, Adi Shamir và Leonard Adleman [1] và là hệ thống mật mã khóa công khai với hai nguyên thủy là hệ mật khóa công khai RSA và lược đồ chữ ký số RSA đã và đang được tích hợp trong hầu hết các sản phẩm bảo mật và an toàn thông tin hiện nay (cả sản phẩm phần cứng và phần mềm). Để triển khai sử dụng các nguyên thủy mật mã RSA, các bộ tham số RSA được sinh, phân phối dưới dạng các chứng thư số (khóa công khai) và khóa riêng thông qua các hệ thống cơ sở hạ tầng khóa công khai (PKI). Các nguyên thủy mật mã RSA cùng bộ tham số đi kèm có thể được sử dụng cho nhiều mục đích trong các hệ thống thông tin dùng trong cả lĩnh vực kinh tế xã hội cũng như an ninh quốc phòng, như: bảo mật, xác thực thư tín điện tử, bảo mật và xác thực Web, bảo mật và xác thực giao thức truyền tệp (FTP), đăng nhập mạng máy tính, bảo mật và xác thực dữ liệu được lưu trữ và xử lý trong các hệ quản trị cơ sở dữ liệu, bảo mật luồng IP,... Dưới đây là thuật toán sinh bộ tham số khóa cho các nguyên thủy mật mã RSA.

Mỗi thực thể trong hệ thống trước khi muốn sử dụng các nguyên thủy mật mã RSA sẽ tạo hoặc được tạo một bộ tham số RSA theo các bước dưới đây [1]:

1. Sinh ngẫu nhiên hai số nguyên tố lớn khác nhau p và q, chúng có cùng độ dài theo bít.
2. Tính  N = pq, φ(N) = (p-1)(q-1)
3. Chọn e thỏa mãn 1<e<φ(N) sao cho (e,φ(N)) = 1
4. Tính số nguyên dương d thỏa mãn: 1< e < φ(N)  và ed = 1 mod φ(N)
5. Đầu ra là bộ tham số: N, e, d

Trong đó: N là RSA mô đun lô, e là khóa công khai, d là khóa bí mật (thông thường khi người ta nói bộ tham số RSA 2048 bít là bộ tham số RSA với mô đun lô N có độ dài tính theo bít là 2048 bít).

Các bộ tham số RSA sau khi sinh sẽ được sử dụng cho thuật toán mã hóa khóa công khai như RSA-OAEP, RSAES-PKCS1-V1_5 và các lược đồ chữ ký số như RSASSA-PSS, RSASSA-PKCS1-V1_5 [2].

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 mô đun lô 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 mô đun lô 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 số nguyên tố lớn, độ lớn của chúng mang tính lịch sử, 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ố.

Tóm lại để sử dụng các nguyên thủy RSA sao cho an toàn và hiệu quả cần quan tâm đến nhiều yếu tố. Trong phạm vi bài viết này chúng tôi sẽ tổng hợp và giới thiệu các kết quả nghiên cứu đã được công bố trên thế giới về việc lựa chọn độ dài RSA mô đun lô nhằm đáp ứng hai mục tiêu nêu trên. Trên cơ sở đó đưa ra những khuyến cáo về độ dài RSA mô đun lô phù hợp cho thời điểm hiện tại và tương lai để đảm bảo các bộ tham số RSA được sinh, phân phối và quản lý bởi các hệ thống PKI đủ an toàn và hiệu quả khi sử dụng để bảo mật và xác thực thông tin thuộc lĩnh vực kinh tế xã hội.

MỘT SỐ KHUYẾN CÁO TRONG CÁC BỘ CHUẨN TRÊN THẾ GIỚI

Để đảm bảo các nguyên thủy mật mã an toàn trước các tấn công đã biết, nhiều bộ chuẩn về mật mã và an toàn thông tin đã đưa ra các tiêu chuẩn về độ dài khóa cho các nguyên thủy mật mã nói chung, trong đó có độ dài khóa cho các nguyên thủy mật mã mà độ an toàn của nó dựa trên bài toán phân tích số nguyên ra các thừa số nguyên tố (trong đó các nguyên thủy RSA là ví dụ điển hình). Dưới đây, chúng tôi xin giới thiệu một số khuyến cáo về độ dài RSA mô đun lô đã được đưa ra bởi một số tổ chức ban hành tiêu chuẩn có uy tín trên thế giới.

Khuyến cáo của NIST

Viện Tiêu chuẩn và Công nghệ Mỹ (NIST) đưa ra khuyến cáo về việc sử dụng độ dài RSA mô đun lô theo thời gian trong chuẩn NIST 800-57 [3] với phiên bản được cập nhật mới nhất vào năm 2020. NIST 800-57 lấy một mốc thời gian chung từ năm 2019-2030 với các độ dài mô đun như Bảng 1.  

Bảng 1. Khuyến cáo độ dài RSA mô đun lô theo thời gian của NIST

TT	Thời gian sử dụng	Độ dài RSA mô đun lô theo bít
1	Thừa kế	1024
2	2019-2030 (mức 1)	2048
3	2019-2030 (mức 1)	3072
4	2019-2030 (mức 3)	7680
5	2019-2030 (mức 4)	15360

Chú ý: “Thừa kế” theo nghĩa là đối với RSA 1024 bít được dùng để tương thích với các ứng dụng cũ, tức chỉ được dùng để xử lý dữ liệu đã được bảo vệ trước đó, không sử dụng để bảo vệ dữ liệu sau năm 2019 (mã hóa dữ liệu và ký số).

Khuyến cáo của ANSSI

Năm 2014, Cơ quan An ninh Mạng và Thông tin Pháp (ANSSI) đã đưa ra khuyến cáo về độ dài RSA mô đun lô theo thời gian [4]. Độ dài RSA mô đun lô được khuyến cáo dùng trong ba giai đoạn chính với các khoảng thời gian cụ thể như Bảng 2 dưới đây.

Bảng 2. Khuyến cáo độ dài RSA mô đun lô theo thời gian của ANSSI

TT	Thời gian sử dụng	Độ dài RSA mô đun lô theo bít
1	2014-2020	2048
2	2020-2030	2048
3	>2030	3072

ECRYPT-CSA là cơ quan đưa ra các khuyến nghị về sử dụng an toàn mật mã của Liên minh Châu Âu. Năm 2018, ECRYPT-CSA đưa ra khuyến cáo về độ dài RSA mô đun lô sử dụng trong các khoảng thời gian như Bảng 3 [5].

Bảng 3. Khuyến cáo độ dài RSA mô đun lô theo thời gian của ECRYPT-CSA

TT	Thời gian sử dụng	Độ dài RSA mô đun lô theo bít
1	Thừa kế	1024
2	2022-2028 (dữ liệu sử dụng dưới 10 năm)	3072
3	2022-2068 (dữ liệu sử dụng từ 30 đến 50 năm)	15360

Khuyến cáo của BSI

BSI là cơ quan ban có trách nhiệm hành chuẩn mật mã của Đức. Theo khuyến cáo của BSI [6], độ dài RSA mô đun lô dùng theo thời gian được cho như Bảng 4.

Bảng 4. Khuyến cáo độ dài RSA mô đun lô theo thời gian của BSI

TT	Thời gian sử dụng	Độ dài RSA mô đun lô theo bít
1	2020-2022	2000
2	2023-2026	3000

Khuyến cáo của RFC 3766

RFC 3766 [7] đưa ra phương pháp xác định độ dài RSA mô đun lô theo từng năm, cụ thể áp dụng phương pháp này chúng ta có các khuyến cáo cho từng năm như Bảng 5.

Bảng 5. Khuyến cáo độ dài RSA mô đun lô theo thời gian của RFC 3766

TT	Thời gian sử dụng	Độ dài RSA mô đun lô theo bít
1	2023	2269
2	2025	2313
3	2026	2358
4	2028	2403
5	2029	2448

Mặc dù các bộ tiêu chuẩn nêu trên đã đưa ra các khuyến cáo về độ dài RSA mô đun lô cho từng mốc thời gian cụ thể, tuy nhiên đảm bảo toán học cho các tiêu chuẩn không được các tổ chức ban hành chuẩn công bố. Trong phần tiếp theo chúng tôi sẽ giới thiệu một số công trình nghiên cứu khoa học và thực tiễn liên quan đến việc xác định độ dài RSA mô đun lô nhằm đảm bảo cho các nguyên thủy mật mã RSA được sử dụng một cách an toàn và hiệu quả.

MỘT SỐ CÔNG TRÌNH NGHIÊN CỨU KHOA HỌC VÀ THỰC TIỄN KHÁC

Năm 2001, Arjen K. Lenstra và Eric R. Verheul đã đưa ra các công thức toán học cụ thể để tính mức an toàn và đưa ra các khuyến nghị về độ dài khóa cho hầu hết các hệ thống mật mã [8]. Đây là công trình đầu tiên có cách tiếp cận toán học dựa trên các tham số cụ thể. Đến năm 2004, Arjen K. Lenstra trong công trình công bố của mình [9] đã đưa ra phương pháp được xem là phiên bản cập nhật của phương pháp đã được đưa ra trong [8]. Trong phương pháp này số lượng các tham số được sử dụng để tính toán được cập nhật và giảm bớt tạo sự dễ hiểu khi xác định độ dài khóa cho các nguyên thủy mật mã.

Trong phạm bài viết này chúng tôi chỉ giới thiệu tóm lược phương pháp tính được đưa ra trong [9] đối với bài toán phân tích số nhằm đưa ra độ dài RSA mô đun lô theo các mốc thời gian. Phương pháp này dựa vào một số giả thuyết và căn cứ dưới đây:

- Một nguyên thủy mật mã được cho là an toàn cho đến một năm cho trước, nếu chi phí cho một tấn công thành công trong năm đó là xấp xỉ 40 triệu Đô la Mỹ một ngày (40M dollardays). Đây chính là chi phí được tính toán để có thể phá Chuẩn mã hoá dữ liệu (DES) vào năm 1982.

- Tại thời điểm năm 2004 (thời điểm [7] được công bố), chi phí của tấn công trên RSA 1024 bít sử dụng phần cứng chuyên dụng cùng thuật toán phân tích số nguyên “sàng trường số” (NFS – Number Field Sieve) được đánh giá với chi phí tối đa là 400M dollardays.

- Dưới tác động của luật Moore và các yếu tố khác như kinh phí đầu tư có tính đến phát triển của kinh tế, của khoa học mã thám, … tác giả [7] đưa ra giả thuyết đối với bài toán phân tích số là "Gấp đôi luật phân tích Moore" như sau: Chi phí phân tích một modulus cố định bất kỳ giảm đi 2 lần sau mỗi 9 tháng.

Trên cơ sở các giả thiết chính nêu trên, Arjen K. Lenstra đã đưa ra công thức tính độ dài RSA mô đun lô an toàn theo mốc thời gian (công thức, các khái niệm có liên quan có thể xem chi tiết trong [9]). Cụ thể theo [9] một số độ dài RSA mô đun lô được khuyến cáo sử dụng đến các mốc thời gian như sau:

Bảng 6. RSA mô đun lô và thời gian sử dụng theo cách tính trong [9]

TT	Thời gian sử dụng	Độ dài RSA mô đun lô theo bít
1	2023	1708
2	2024	1756
3	2025	1805
4	2026	1855
5	2027	1906
6	2030	2063

Bên cạnh các công trình nghiên cứu cơ sở lý thuyết nhằm xác định độ dài RSA mô đun lô sử dụng an toàn theo các mốc thời gian, thì nhiều công trình nghiên cứu mang tính thực tiễn khi triển khai phân tích các RSA mô đun lô cũng đã được công bố. Dưới đây là một số là kết quả của một số nhóm nghiên cứu:

- Ngay sau khi chương trình thử thách phân tích RSA (RSA Factoring Challenge) do phòng thí nghiệm RSA đưa ra vào ngày 18 tháng 3 năm 1991 thì đến ngày 1 tháng 4 cùng năm Arjen K. Lenstra đã công bố kết quả phân tích RSA-330 (100 chữ số thập phân).

- Ngày 22/8/1999 Herman và nhóm nghiên cứu đã công bố kết quả phân tích RSA-512 (155 chữ số thập phân).

- Ngày 12/12/2009 Thorsten Kleinjung và nhóm nghiên cứu đã công bố kết quả phân tích RSA-768 (232 chữ số thập phân).

- Ngày 28/02/2020 nhóm các tác giả F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé and P. Zimmermann đã công bố kết quả phân tích RSA-829 (250 chữ số thập phân).

Trên đây là kết quả công bố của một số nhóm nghiên cứu với tiềm lực về công nghệ và tài chính giới hạn. Hiện tại, theo dữ liệu về siêu máy tính được công bố trong [10] vào tháng 6/2022, siêu máy tính mạnh nhất thế giới hiện nay là siêu máy tính Frontier của công ty ORNL, Mỹ. Tốc độ tính toán của siêu máy tính Frontier là 1102Exaflop/s, trong đó mỗi Exaflop tương đương với 10¹⁸ phép tính. Như vậy mỗi năm siêu máy tính này có thể thực hiện được tương đương số lượng phép tính là:

(365 × 24 × 60 × 60) × 1102 × 10¹⁸ ≈ 2⁹³.

Với giả thiết dùng toàn bộ GDP của quốc gia có GDP cao nhất là Mỹ (cỡ 23.000 tỷ đô la theo [11]) đầu tư mua siêu máy tính Frontier (giá 0,6 tỷ Đô la) thì một năm hệ thống này có thể thực hiện tổng cộng cỡ 2¹⁰⁹ phép tính. Với 2⁹³ phép tính là tương đương với việc phân tích RSA-1939 và 2¹⁰⁹ phép tính tương đương với việc phân tích RSA-2919 (việc quy đổi này có thể tham khảo [12]).

KẾT LUẬN

Trong bài viết này tổng hợp các khuyến cáo từ các bộ chuẩn được ban hành bởi các tổ chức ban hành chuẩn về bảo mật và an toàn thông tin có uy tín trên thế giới về độ dài RSA mô đun lô sử dụng cho các khoảng thời gian cụ thể; các công trình nghiên cứu về cơ sở khoa học và thực tiễn của các nhà khoa học nhằm đánh giá độ an toàn của các nguyên thủy mật mã RSA với các độ dài mô đun lô cho trước; cập nhật sự phát triển của khoa học công nghệ có ảnh hưởng đến bài toán phân tích số cũng như là ảnh hưởng đến độ an toàn của các nguyên thủy mật mã RSA. Qua kết quả nghiên cứu phân tích, tổng  hợp trên, chúng ta thấy để các nguyên thủy mật mã RSA được dùng đủ an toàn thì RSA mô đun lô tối thiểu được dùng tại thời điểm hiện tại và tương lai gần phải có độ dài tối thiểu là 2048 bít.

Tuy nhiên, trình bày trên mới chỉ dừng lại ở việc xem xét độ an toàn dựa trên các kiểu tấn công tổng quát lên các nguyên thủy mật mã RSA đó là phân tích RSA mô đun lô sử dụng thuật toán sàng trường số (NFS) và công cụ tính toán là các máy tính không-lượng tử. Đối với độ an toàn của các nguyên thủy mật mã RSA, ngoài việc chịu ảnh hưởng của các phương pháp phân tích số mà trong đó độ phức tạp phụ thuộc vào độ lớn của RSA mô đun lô thì trên thế giới cũng đã có nhiều công trình nghiên cứu nhằm đưa ra các thuật toán phân tích RSA mô đun lô chỉ phụ thuộc vào tính chất của các tham số khác như các nhân tử nguyên tố p, q; các thành phần công khai, bí mật e, d. Trong các bài viết tiếp theo chúng tôi sẽ xem xét, phân tích, tổng hợp về các khía cạnh này nhằm đưa ra các khuyến cáo để có được các bộ tham số RSA thực sự an toàn dùng cho các ứng dụng bảo mật và an toàn thông tin.

TÀI LIỆU THAM KHẢO [1] Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone "Handbook of Applied Cryptograph", CRC Press, Inc, 1997. [2] RSA Laboratories, “PKCS #1 v2.1: RSA Cryptography Standard”, 1999. [3] Special Publication 800-57 Part 1, “Recommendation for Key Management”, Rev. 5, NIST, 05/2020. [4] ANSSI, “Mécanismes cryptographiques - Règles et recommandations”, Rev. 2.03, 02/2014. [5] ECRYPT-–CSA, “Algorithms, Key Size and Protocols Report”, H2020-ICT-2014—Project 645421, 02/2018. [6] TR-02102-1 v2020-01, BSI, “Cryptographic Mechanisms: Recommendations and Key Lengths”, 03/2020. [7] H. Orman and P. Hoffman, “Determining Strengths for Public Keys Used for Exchanging Symmetric Keys”, RFC 3766, 04/2004. [8] Arjen K. Lenstra, and Eric R. Verheul. “Selecting cryptographic key sizes”. Journal of cryptology 14.4 (2001): 255-293. [9]  Arjen K. Lenstra, “Key lengths”. The Handbook of Information Security, 06/2004. [10] https://top500.org/lists/top500/2022/06 [11] https: //tradingeconomics.com/united-states/gdp [12] https://www.keylength.com