Về một backdoor đối xứng trong sinh khóa RSA tuân thủ điều kiện 'lỏng' theo chuẩn FIPS 186-4

Bài viết trình bày đề xuất về một thuật toán sinh khóa RSA chứa backdoor đối xứng tuân thủ điều kiện “lỏng” về tham số khóa theo chuẩn FIPS 186-4. Thuật toán đề xuất dựa trên sự cải tiến thuật toán backdoor trong sinh khóa RSA tại mục 3 trong với các tham số đầu vào và đầu ra thỏa mãn chuẩn FIPS 186-4.
Nội dung trích xuất từ tài liệu:
Về một backdoor đối xứng trong sinh khóa RSA tuân thủ điều kiện “lỏng” theo chuẩn FIPS 186-4HNUE JOURNAL OF SCIENCENatural Sciences 2018, Volume 63, Issue 3, pp. 99-107This paper is available online at http://stdb.hnue.edu.vnDOI: 10.18173/2354-1059.2018-0010VỀ MỘT BACKDOOR ĐỐI XỨNG TRONG SINH KHÓA RSATUÂN THỦ ĐIỀU KIỆN “LỎNG” THEO CHUẨN FIPS 186-4Bạch Nhật Hồng1 và Lê Quang Huy2Khoa Điện - Điện tử, Trường Đại học Sư phạm Kĩ thuật Hưng Yên2Cục Chứng thực số và Bảo mật thông tin, Ban Cơ yếu Chính phủ1Tóm tắt. Bài báo trình bày đề xuất về một thuật toán sinh khóa RSA chứa backdoor đối xứngtuân thủ điều kiện “lỏng” về tham số khóa theo chuẩn FIPS 186-4 [1]. Thuật toán đề xuất dựatrên sự cải tiến thuật toán backdoor trong sinh khóa RSA tại mục 3 trong [2] với các tham sốđầu vào và đầu ra thỏa mãn chuẩn FIPS 186-4. Để khẳng định các phân tích, đánh giá, thuậttoán backdoor đề xuất được thử nghiệm trên một thiết bị PKI-Token với các kết quả phù hợp.Từ khóa: Mật mã, sinh khóa, RSA, backdoor.1. Mở đầuBackdoor trong các hệ mật mã được nghiên cứu phục vụ nhu cầu (hợp pháp) đảm bảo anninh chống lại việc sử dụng mật mã thực hiện các hành động tội phạm [3]. Căn cứ vào đặc điểmcủa hệ mật việc nghiên cứu backdoor tập trung vào phần sinh khóa (key generation) đối với hệmật bất đối xứng và vào phần mã mật (encryption) đối với hệ mật đối xứng. Tuy nhiên các nghiêncứu đã công bố về backdoor đối với một hệ mật xác định chỉ đề xuất các giải pháp chung trên hệmật đó chứ chưa đề xuất giải pháp tuân thủ một chuẩn nhất định. Với hệ mật khóa công khai RSAđang được sử dụng phổ biến trong các sản phẩm mật mã (phần cứng, phần mềm), nhiều tổ chứcđịnh chuẩn đã công bố các chuẩn ứng dụng trong thực tế. Do vậy để các thuật toán backdoor chohệ mật RSA có thể ứng dụng được trong thực tế cũng cần thỏa mãn một chuẩn nhất định. Hiện tạichuẩn FIPS 186-4 về chữ kí số do viện tiêu chuẩn quốc gia Mỹ (NIST) công bố có bao gồm hệmật RSA, được nhiều nhà sản xuất các sản phẩm mật mã tuân thủ.Để có thể ứng dụng đảm bảo an ninh khi sử dụng mật mã, bài báo tập trung nghiên cứu vềbackdoor trong sinh khóa RSA và đề xuất một thuật toán sinh khóa RSA chứa backdoor đối xứngtuân thủ điều kiện “lỏng” về tham số khóa tại Appendix B.3.1. FIPS 186-4 [1].2. Nội dung nghiên cứu2.1. Cơ sở về backdoor trong sinh khóa RSA2.1.1. Công cụ hình thức phân tích và đánh giá backdoorĐể tạo cơ sở phân tích và đánh giá backdoor, công cụ hình thức của Arboit (mục 4.2 chương4 trong [5]) với định nghĩa hình thức cụ thể, các tiêu chuẩn đánh giá hiệu quả được sử dụng trongbài báo này và được trình bày tóm tắt tại mục A phần 2 trong [2]. Để đánh giá backdoor, các tiêuchuẩn đánh giá được phân tích, lượng hóa, phân ngưỡng, tổng hợp tại bảng I mục B phần 2 trong [2].Ngày nhận bài: 19/7/2017. Ngày sửa bài: 1/2/2018. Ngày nhận đăng: 9/2/2018.Tác giả liên hệ: Lê Quang Huy. Địa chỉ e-mail: lequanghuyabc@gmail.com99Bạch Nhật Hồng và Lê Quang Huy2.1.2. Phương pháp phân tích nhân tử của CoppersmithMột vấn đề khó trong lí thuyết số là tìm cách hiệu quả để phân tích nhân tử của một sốnguyên. Các thuật toán phân tích nhân tử tốt nhất hiện nay, phương pháp đường cong Ellip vàsàng trường số, vẫn có độ phức tạp lũy thừa. Một hướng nghiên cứu được hình thành gần đây làsự nới lỏng bài toán phân tích nhân tử để có thể giải quyết được trong thời gian đa thức. Một sựnới lỏng bài toán phân tích nhân tử có nhiều ứng dụng trong phân tích mã là phân tích nhân tử khibiết một nửa số các bit của số nguyên tố p, sử dụng phương pháp tìm nghiệm nguyên nhỏ củaphương trình đa thức modulo một biến của Coppersmith [4].* Tìm nghiệm nguyên nhỏ của phương trình đa thức modulo một biếnĐến nay, chưa có thuật toán tổng quát hiệu quả để tìm nghiệm nguyên của phương trìnhmodulo một biến. Năm 1996, Coppersmith [4] đã đưa ra phương pháp hiệu quả tìm nghiệmnguyên nhỏ của phương trình modulo một biến sử dụng thuật toán rút gọn cơ sở LLL. Phát biểu bài toánGiả thuyết cho:- N là một số nguyên lớn không biết nhân tử (thừa số)- Đa thức f ∈ Z[x], có bậc d, f (x) = ad xd + ad-1 xd-1 + … + a1x + a0- Phương trình modulo: f (x) ≡ 0 (mod N)Cần tìm nghiệm nguyên x0 ∈ Z, của phương trình f (x) ≡ 0 (mod N); với | x0 | ≤ X, X là mộtràng buộc xác định, x0 thỏa mãn f (x0) ≡ 0 (mod N). Ý tưởng và cách tìm nghiệmÝ tưởng: rút gọn (biến đổi) bài toán tìm nghiệm nguyên nhỏ của phương trình modulo thànhbài toán tìm nghiệm nguyên nhỏ của phương trình trên tập các số nguyên Z.Điều kiện: Giả sử |f (x)| < N với | x | ≤ X, (X là một ràng buộc xác định). Khi đó nghiệm x0 củaphương trình đa thức f (x) = 0, cũng là nghiệm của f (x) ≡ 0 (mod N).Ràng buộc X càng lớn thì càng chứa được nhiều nghiệm. Nghiệm x0 của f (x) = 0 trên Z cóthể được tìm thấy bằng cách sử dụng các thuật toán tìm nghiệm chuẩn (Sturm sequence).Cách thực hiện: lựa chọn tập đa thức thích hợp để xây dựng đa thức mới là tổ hợp tuyến tínhcủa các đa thức trong tập hợp sao cho ...