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ạch Nhật Hồng

99 HNUE JOURNAL OF SCIENCE DOI: 10.18173/2354-1059.2018-0010 Natural Sciences 2018, Volume 63, Issue 3, pp. 99-107 This paper is available online at 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ạch Nhật Hồng1 và Lê Quang Huy2 1Khoa Điện - Điện tử, Trường Đại học Sư phạm Kĩ thuật Hưng Yên 2Cục Chứng thực số và Bảo mật thông tin, Ban Cơ yếu Chính phủ Tó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ứng tuâ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ựa trê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ật toá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ở đầu Backdoor 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 an ninh 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ểm củ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ên cứ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 cho hệ 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ại chuẩ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ứng tuâ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ứu 2.1. Cơ sở về backdoor trong sinh khóa RSA 2.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ương 4 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 trong bà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êu chuẩ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.com Bạch Nhật Hồng và Lê Quang Huy 100 2.1.2. Phương pháp phân tích nhân tử của Coppersmith Mộ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ử khi biế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ủa phươ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ình modulo một biến. Năm 1996, Coppersmith [4] đã đưa ra phương pháp hiệu quả tìm nghiệm nguyê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án Giả 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 x d + ad-1 x d-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ột rà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ành bà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ủa phươ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ính của các đa thức trong tập hợp sao cho vector (hệ số) của đa thức mới có chuẩn Euclide thỏa mãn điều kiện biến đổi phương trình modulo thành phương trình không modulo. Ràng buộc X và các hệ số của đa thức mới được tìm thấy hiệu quả bằng cách áp dụng thuật toán rút gọn LLL. * Phân tích nhân tử số modulo N khi biết một nửa số bit p Phương pháp tìm nghiệm nguyên nhỏ của phương trình đa thức modulo một biến có nhiều ứng dụng rộng rãi. Một ứng dụng quan trọng là: phân tích nhân tử số modulo N = p.q trong thời gian đa thức, khi biết một nửa các bit của số nguyên tố p. Cụ thể, Coppersmith trong [4] đã chứng minh các kết quả sau: Định lí 2.1. Phân tích nhân tử khi biết các bit cao của kp Cho N = p.q, giả sử p > q, gọi k là một số nguyên không phải là bội số của q. Giả sử ta biết được xấp xỉ p’ của kp sao cho: 1 4' 2kp p N  Thì có thể phân tích nhân tử N trong thời gian đa thức theo log N. Định lí 2.2. Phân tích nhân tử khi biết các bit cao của p Cho N = p.q, trong đó p, q là các số nguyên tố. Nếu biết một nửa các bit cao (1/4 log2 N) của p, ta có thể phân tích nhân tử N trong thời gian đa thức theo kích thước bit của p. Định lí 2.3. Phân tích nhân tử khi biết các bit thấp của p 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 101 Cho N = p.q trong đó p, q có cùng kích thước bit và p > q. Giả sử biết p0 và M thỏa mãn p0 = p mod M và M ≥ N1/4 thì có thể phân tích nhân tử của N trong thời gian đa thức log2 N. 2.1.3. Thuật toán trung thực tuân thủ điều kiện “lỏng” theo chuẩn FIPS 186-4 Để tạo cơ sở cho việc phân tích và đánh giá thuật toán backdoor đề xuất, điều kiện về tham số và thuật toán trung thực tuân thủ chuẩn FIPS 186-4 được trình bày chi tiết. * Điều kiện “lỏng” về tham số khóa RSA theo FIPS 186-4 Điều kiện “lỏng” về tham số khóa của hệ mật RSA là điều kiện về tham số khóa được mô tả tại mục A2 và mục B tại phần B.3.1 appendix B, FIPS 186-4 [1]. “Lỏng” ở đây được hiểu là yêu cầu “không cao” về tính nguyên tố của tham số p và q (các số có thể nguyên tố), để có không gian khóa lớn. Kí hiệu khóa công khai (n, e), khóa riêng (n, d), n = p.q, với p, q là các số nguyên tố. Kí hiệu nlen là độ dài theo bit của n. Các tham số thỏa mãn điều kiện sau: 1. p và q là các số có thể nguyên tố (probable prime) ngẫu nhiên (nlen ≥ 2048). 2. e được chọn trước khi tạo p, q; e là một số lẻ thỏa mãn: 216 < e < 2256. 3. Các số nguyên tố p và q thỏa mãn các ràng buộc sau: a) (p - 1), (q - 1) nguyên tố cùng nhau với số mũ công khai e. b)    /2 1 /2 12. 2 , 2nlen nlenp q   (1) c) /2 1002nlenp q   (2) 4. Số mũ riêng d, được tạo sau khi tạo p và q, thỏa mãn: 2 nlen / 2 < d < LCM (p - 1, q - 1) và d = e -1 mod (LCM (p - 1, q - 1)). * Thuật toán sinh khóa RSA tuân thủ điều kiện “lỏng” (thuật toán G0) Thuật toán sinh khóa RSA trung thực tuân thủ điều kiện “lỏng” theo chuẩn FIPS 186-4 được tóm tắt theo thuật toán tại mục B.3.3. appendix B FIPS 186-4, được mô tả như sau: Input (nlen, e) Output (p, q, n, e, d) 1: if (e < 2 16 or e > 2 256 ) then return failure ; // generate p 2: p = RandomOddInteger() ; //log2 p =nlen/2 3: if  /2 12.2nlenp  then goto step 2 ; 4: if (gcd(p - 1, e) ≠ 1) then goto step 2 ; 5: if (not PrimalityTest (p)) then goto step 2; // generate q 6: q = RandomOddInteger() ; //log2 q =nlen/2 7: if  /2 12.2nlenq  then goto step 6 ; 8: if ( |p – q| ≤ 2 nlen/2 – 100 ) then go to step 6 ; 9: if (gcd(q - 1, e) ≠ 1) then goto step 6 ; 10: if (not PrimalityTest (q)) then goto step 6 ; // compute n, d 11: n = p.q ; 12: d = e –1 mod (LCM(p - 1, q - 1)) ; 13: if ( d < 2 nlen/ 2 ) then go to step 6 ; 14: return (p, q, n, d) ; 2.3.5. Lực lượng khóa của thuật toán sinh khóa RSA tuân thủ điều kiện “lỏng” Xét cách tạo p: Vì p là một số nguyên tố nằm trong khoảng  /2 1 /22.2 ,2 1nlen nlen  . Bạch Nhật Hồng và Lê Quang Huy 102 Nên #{ p } = Pr[số nlen/2 bit là số nguyên tố].  /2 /2 12 2.2nlen nlen  2 /2 /2 /2 log/2 12 2 2.0,6.2 1,2. 2 / 2 nlen nlen nlen nlennlen nlen nlen nlen     (3) Xét cách tạo q: Kí hiệu u là số nguyên tố trong khoảng (p - 2nlen/2 -100, p + 2nlen/2 -100) (4) Vậy #{u}= Pr[số nlen/2 bit là số nguyên tố] * (p + 2nlen/2 -100 – (p - 2nlen/2 -100) = /2 97 /2 992 2.2 / 2 nlen nlen nlen nlen    (5) Vì q được tạo giống như p và sau p thỏa mãn điều kiện (2), nằm ngoài khoảng ( (p + 2nlen/2 - 100 – (p - 2nlen/2 -100) = 2nlen/2 -99), nhỏ hơn rất nhiều so với khoảng tồn tại của p và q (điều kiện (1)) với giá trị là :   /2 1 /2 22 2 .2 2nlen nlen   . Nên #{q} = #{p} - #{u} = 2 /2 /2 97 /2 1 /2 1 log2 2 2 2 nlen nlen nlen nlen nlen nlen nlen nlen       (6) Vậy lực lượng khóa của thuật toán là, #{(p, q, d)} = {#{p}. #{q)} = /2 /2 1 1 2 2 2 2 . nlen nlen nlen nlen nlen nlen    (7) 2.2. Đề xuất thuật toán sinh khóa RSA chứa backdoor mới 2.2.1. Giới thiệu thuật toán Thuật toán sinh khóa RSA chứa backdoor đề xuất được xây dựng dựa trên việc cải tiến thuật toán backdoor ở mục 3.4. trong [2]. Điểm cải tiến trong thuật toán đề xuất là các tham số đầu vào và đầu ra (p, q, d) thỏa mãn điều kiện “lỏng” theo chuẩn FIPS 186-4. Việc cải tiến chỉ áp dụng cho phần sinh khóa, phần khôi phục khóa không thay đổi. Ý tưởng của thuật toán: tạo số nguyên tố p ngẫu nhiên, trích thông tin backdoor từ p và nhúng vào một giá trị n’ gần với số modulus n. Từ giá trị n’ sẽ tìm ra q, n và d. Thông tin backdoor I(kpriv) = ((p⌉k/2)⌋s - k/2), được trích với độ dài nhỏ hơn một nửa các bit của số nguyên tố p (bước 10). Kỹ thuật nhúng: thông tin backdoor sau khi đã mã mật được ghép vào phía bên phải (các bit thấp) với giá trị ngẫu nhiên (các bit cao) để tạo ra một giá trị có độ dài k = nlen/2 bit, giá trị được ghép này được ghép tiếp vào bên trái (phía các bit cao) với giá trị nlen/2 bit ngẫu nhiên (các bit thấp) tạo thành giá trị có chiều dài nlen bit. (bước 12). Giá trị nlen bit này được sử dụng để tìm ra số nguyên tố q. Các tham số thuật toán: + G1 = Thuật toán đề xuất; G1 = G0 = nlen ≥ 2048; E = AES, E ≥ 128; M = n; log2 p = log2 q = k=nlen/2. + Hàm F: là hàm mã mật hóa đối xứng AES, AES ≥ 128. + Hàm G: {0, 1} 2k x {0, 1} k/2 x {0, 1} k/2 → {0, 1}k, hàm này thực hiện phương pháp phân tích nhân tử của Coppersmith (mục 2.2), ví dụ: p = G(n, 2k/2, p div 2k/2). 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 103 Thuật toán đề xuất [sinh khóa RSA] 1: Input (e, s, nlen) ; 2: if (e < 2 16 or e > 2 256 ) then return failure ; // tạo số nguyên tố p 3: p = RandomOddInteger() ; //log2 p =nlen/2 4: if  /2 12.2nlenp  then goto step 3 ; 5: if (gcd(p - 1, e) ≠ 1) then goto step 3 ; 6: if (not (PrimalityTest (p))) then goto step 3 ; // tạo số nguyên tố q 7: q’ = RandomOddInteger() ; //log2 q =nlen/2 8: n1 = p.q’ ; //k = nlen/2 9: τ = n1⌉ k/2 ; 10: μ = F K((p⌉ k/2 )⌋s - k/2);//K, khóa người thiết kế 11: r = RandomOddInteger() ; //log2 r = 3k/2 - s 12: n2 = τ . 2 3k/2 + μ . 23k/2 –s + r ; //n2 = τ : μ : r 13: q = [n2 / p] ; 14: if  /2 12.2nlenq  then goto step 7 ; 15: if ( |p – q| ≤ 2 nlen/2 – 100 ) then go to step 7 ; 16: if (gcd(q - 1, e) ≠ 1) then goto step 7 ; 17: if (not (PrimalityTest (q))) then goto step 7 ; 18: n = p.q ; 19: d = e –1 mod (LCM(p - 1, q - 1)) ; 20: if ( d < 2 nlen/ 2 ) then go to step 7 ; 21: return (p, q, n, d) ; Thuật toán đề xuất [khôi phục khóa RSA] 1: Input (n, e, s) ; 2: μ = ( n⌋3k/2 )⌉s - k/2 ; 3: p1 =   /2s kn    e ; 4: p2 = F -1 K(μ) ; 5: p3 = p1 . 2 s-k/2 + p2 ; //p3 = p1 : p2 //p3 == p⌉ k/2 6: p = S(n, 2 k/2 , p3) ;//phương pháp Coppersmith 7: q = n / p ; 8: d ≡ e−1 mod φ(n) ; 9: return (p, q, d) ; 2.2.2. Đánh giá thuật toán đề xuất Tính bảo mật: Xét trường hợp kẻ tấn công có khóa công khai của người dùng, không có khóa bí mật của người thiết kế. Giả sử độ dài tham số an toàn của hệ mật người dùng G1 ≥ 2048, Start e, nlen, s Điều kiện tham số đầu vào Trả về mã lỗi Stop No Tạo số nguyên tố p Tính giá trị q Điều kiện tham số q Yes No Tính n, d Điều kiện số mũ riêng d Yes No p, q, n, d Yes Điều kiện tham số p No Yes 2 16 < e < 2 256 p là số có thể nguyên tố gcd(p - 1, e) = 1 (1,41.2 nlen/2-1 < p < 2 nlen/2 ) A.1, B.2.a, B.2.b mục 1.4.3 q là số có thể nguyên tố gcd (q - 1, e) = 1 (1,41 . 2 nlen/2-1 < q < 2 nlen/2 ) |p – q| 2nlen/2 – 100 A.1, B.2.a, B.2.b, B.2.c mục 1.4.3 d < 2 nlen/ 2 B.3,mục 1.4.3 Chuẩn bị thông tin backdoor Chèn backdoor vào số modulus n Chèn thông tin backdoor vào số modulus n Hình 1. Sơ đồ khối phần thuật toán sinh khóa của backdoor đề xuất Start n, e, s Stop p = Phân_tích_nhân_tử_Coppersmith(p3) Tính q, d p, q, d Tính thông tin backdoor từ khóa công khai, p3 Hình 2. Sơ đồ khối phần thuật toán khôi phục khóa của backdoor đề xuất Bạch Nhật Hồng và Lê Quang Huy 104 người thiết kế lựa chọn hệ mật đối xứng AES có độ dài tham số an toàn AES ≥ 128 tương đương với độ an toàn của người dùng. Vì kẻ tấn công không có khóa bí mật của người thiết kế và độ an toàn hệ mật của người thiết kế được lựa chọn tương đương với độ an toàn hệ mật người dùng nên kẻ tấn công không phá vỡ được hệ mật của người dùng thì cũng không phá vỡ được hệ mật của người thiết kế. Căn cứ vào bảng các tiêu chuẩn đánh giá backdoor mục 2.1, tính bảo mật được đánh giá ở mức “tốt”. Tính hoàn chỉnh: Xét thuật toán sinh khóa: Với mục tiêu nhúng thông tin backdoor vào khóa công khai, thông tin backdoor ít hơn một nửa các bit của p được trích và mã mật (bước 10) và nhúng vào giá trị n (bước 12). Xét thuật toán khôi phục khóa: với mục tiêu khôi phục khóa riêng, thông tin backdoor đã mã mật được tách ra khỏi các bit cao của n (bước 2). Sử dụng khóa bí mật của người thiết kế, giải mã mật thông tin backdoor ta thu được gần một nửa các bit cao của p (bước 4). Phần còn lại của nửa các bit cao của p, nhận được khi lấy các bit cao của căn bậc 2 số modulus n. Sử dụng phương pháp phân tích nhân tử của Coppersmith với đầu vào là một nửa các bit cao của p, ta nhận được toàn bộ giá trị p. Từ p dễ dàng tính được q và d. Theo các bước trong thuật toán sinh khóa và thuật toán khôi phục khóa, người thiết kế luôn tính được khóa riêng của người dùng từ khóa công khai tương ứng. Căn cứ vào bảng các tiêu chuẩn đánh giá backdoor mục 2.1, tính hoàn chỉnh được đánh giá ở mức “tốt”. Lực lượng khóa: Xét việc tạo p (từ bước 3 đến bước 6) Vì p được tạo ngẫu nhiên và giống như trong thuật toán trung thực mục 2.3.2. nên theo (2), ta có #{p} = 2 /2 /2 log2 2 nlen nlen nlen nlen  . Xét việc tạo q (từ bước 7 đến bước 17). Với mỗi p có thể chọn ngẫu nhiên τ và r , do đó tạo được 22k - s = 2nlen - s giá trị n2. Vì q được tính theo n2 và p (bước 12), nên #{ q }= #{n2 / p} . Pr[q là số nguyên tố]. #{ q } = 2 2 1 log ( /2) /2 2 /2 log 2 .2 2 2 nlen s nlen nlen s nlen nlen       Vậy số lượng n là: #{n} = #{p} . #{q} = 2 2 /2 log 2 log/2 22 .2 2 nlen nlen nlen s nlennlen s      Xét tỷ lệ giữa lực lượng của G1 và G0, vì p được sinh trong G1 giống trong G0 nên hạng tử #{p} có thể bỏ qua, ta có: 2 2 1 2 1 2 0 12 3 log . log, 3 log 2 2 2 1 log , 2 2 2 2 2 k nlennlen s nlen nlenG q s nlen G nlen nlen G q N R N                 Vì hằng số c < -1/2 trong 1G R và căn cứ vào bảng các tiêu chuẩn đánh giá backdoor mục 2.1, lực lượng của G1 được đánh giá ở mức “tốt”. Tính phân phối: Thông tin backdoor được mã mật hóa và nhúng vào vị trí cố định trong n. Tuy nhiên vì thông tin backdoor được mã mật hóa bằng mã khối đối xứng (có phân phối đầu ra gần với phân bố đều) nên phần nhúng thông tin backdoor cũng có phân phối gần với phân phối đều. Việc sinh p ngẫu nhiên và q được tạo thông qua việc chia n2 cho p với giá trị n2 phụ thuộc một phần vào p, tham số ngẫu nhiên r và tham số ngẫu nhiên q’. Do vậy phân phối của q, n có thể gần với phân bố đều và do vậy khoảng cách thống kê giữa thành phần q, n của G1 và G0 là xấp xỉ bằng 0, DG1 ≈ 0. Căn cứ vào bảng các tiêu chuẩn đánh giá backdoor mục 2.1, tính phân phối của G1 được đánh giá ở mức “tốt”. Tính tương quan: Theo cách tạo q (từ bước 7 đến bước 17), q phụ thuộc vào p, tham số ngẫu nhiên r và tham số ngẫu nhiên q’. Nếu người dùng cố định p và yêu cầu sinh lại q thì việc sinh lại 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 105 khóa tổng quát thực hiện được. Tuy nhiên, nếu người dùng yêu cầu ngược lại, tức là cố định q và sinh lại p là không khả thi. (Việc sinh lại khóa trong trường hợp này chỉ khả thi nếu thuật toán cho phép hoán đổi được vai trò của p và q). Căn cứ vào bảng các tiêu chuẩn đánh giá backdoor mục 2.1, tính tương quan của G1 được đánh giá đạt mức “trung bình”. Độ phức tạp tính toán: Vì p được tạo giống như trong G0 nên ta có tp(G0) = tp(G1). Trong vòng lặp tạo q (từ bước 7 đến bước 17) có thêm việc mã mật hóa thông tin backdoor bằng hệ mật đối xứng (AES). Tuy nhiên độ phức tạp của hệ mật đối xứng AES không đáng kể so độ phức tạp của việc tạo q nên độ phức tạp của việc tạo q trong G1 cũng gần giống như trong G0 nên ta có: tq (G1) = tq (G0). Vậy độ phức tạp tạo n là: tn(G1) = tp + tq = tn . Căn cứ vào bảng các tiêu chuẩn đánh giá backdoor mục 2.1, độ phức tạp của G1 được đánh giá ở mức “tốt” vì nó tuyến tính đối với độ phức tạp của G0 Bộ nhớ sử dụng: Thuật toán không sử dụng bộ nhớ NM và VM nên nó có thuộc tính bộ nhớ sử dụng được đánh giá ở mức “tốt”. 2.2.3. So sánh thuật toán backdoor đề xuất với thuật toán Hidden Prime Factor Thuật toán backdoor đề xuất có ưu điểm hơn so với thuật toán backdoor tại mục 3 trong [2] ở chỗ các tham số đầu vào và đầu ra tuân thủ chuẩn FIPS 186-4. Vì thuật toán backdoor tại mục 3 trong [2] được xây dựng dựa trên ý tưởng của thuật toán Hidden Prime Factor trong [6], nên việc phân tích so sánh giữa thuật toán backdoor đề xuất và thuật toán Hidden Prime Factor sẽ làm rõ hơn các cải tiến. * Các điểm giống nhau - Vị trí giấu thông tin backdoor: trong các bit cao của số modulus n. - Khôi phục khóa riêng: sử dụng phương pháp phân tích nhân tử của Coppersmith. - Bộ nhớ: Không sử dụng bộ nhớ tĩnh (NM). * Các điểm khác biệt Bảng 1. Điểm khác biệt giữa thuật toán backdoor đề xuất với thuật toán Hidden Prime Factor * Tóm tắt các điểm nổi bật của backdoor đề xuất - Các tham số (vào/ra) của backdoor thỏa mãn điều kiện “lỏng” theo chuẩn FIPS 186-4 - Thông tin backdoor: ít hơn một nửa các bit của số nguyên tố p, lực lượng khóa lớn hơn. - 06 thuộc tính được đánh giá tốt, 01 thuộc tính (tương quan) được đánh giá trung bình. 2.2.4. Thử nghiệm thuật toán backdoor đề xuất Để khẳng định kết quả về mặt lí thuyết, thuật toán backdoor đề xuất được cài đặt, thử nghiệm trên trên một thiết bị phần cứng có tên gọi là T-Token [7]. Stt Nội dung Thuật toán Hidden Prime Factor Thuật toán backdoor đề xuất 1 Thông tin backdoor p⌉k/2 Một nửa các bit cao của số nguyên tố p ((p⌉k/2)⌋s - k/2), ít hơn một nửa các bit cao của số nguyên tố p 2 Chuẩn FIPS 186-4 Không tuân thủ Thỏa mãn điều kiện “lỏng” 3 Lực lượng khóa Trung bình 7 7 . 8 8 22 2 k nlen    Tốt (hằng số c < -1/2) 2 1 . log 3 2 22 2 nlen nlen s     Bạch Nhật Hồng và Lê Quang Huy 106 * Cài đặt, thử nghiệm backdoor đề xuất Thiết bị thử nghiệm (T-Token) [7] là một thiết bị PKI-Token được nghiên cứu, thiết kế, chế tạo tại Việt Nam, sử dụng phần cứng hiện đại, firmware chứa các module mật mã được làm chủ hoàn toàn, có các đặc điểm kỹ thuật tương tự như phần lớn các thiết bị PKI-Token hiện được sử dụng rộng rãi, phù hợp để thử nghiệm với các đặc điểm chính: - Phần cứng: có kích thước nhỏ gọn, giao diện USB 2.0. - Firmware: Thực thi thuật toán mật mã RSA chuẩn PKCS#1 v1.5 và v2.1, độ dài khóa 2048 bit, tốc độ kí, giải mã < 2s; Bảo vệ khóa và các tham số mật bằng thuật toán AES. - API: tuân theo chuẩn PKCS#11 v2.2. Cài đặt thuật toán backdoor đề xuất: Do đối tượng sử dụng khác nhau, 02 phần của backdoor (sinh khóa và khôi phục khóa) được cài đặt độc lập với nhau (không trên cùng một module). Phần thuật toán sinh khóa được cài đặt bên trong firmware của thiết bị T-Token dành cho người dùng và được gọi từ bên ngoài thông qua hàm quản lí khóa, C_GenerateKeyPair, của giao diện lập trình. Phần thuật toán khôi phục khóa được cài đặt độc lập trên máy tính chỉ dành riêng cho người thiết kế. Các thuộc tính của backdoor đề xuất được thử nghiệm gồm: tính hoàn chỉnh, độ phức tạp tính toán. Đối với tính hoàn chỉnh kết quả thử nghiệm là thành công nếu từ khóa công khai được tạo ra bởi phần sinh khóa, phần khôi phục khóa của thuật toán khôi phục được khóa riêng tương ứng; ngược lại khi không khôi phục được khóa riêng tương ứng kết quả thử nghiệm là thất bại. Độ phức tạp tính toán của thuật toán backdoor đề xuất (phần sinh khóa và khôi phục khóa) được đo lường thông qua thời gian chạy (đơn vị giây). * Kết quả thử nghiệm Kết quả thử nghiệm cho thấy với các tham số đầu vào khác nhau thời gian thực hiện trung bình của phần sinh khóa thuật toán backdoor đề xuất chậm hơn một chút so với thời gian thực hiện trung bình của thuật toán sinh khóa trung thực. Phần khôi phục khóa của backdoor để xuất có kết quả tất định, người thiết kế luôn khôi phục được khóa riêng từ khóa công khai tương ứng. Tốc độ khôi phục khóa riêng tương đối nhanh so với tốc độ sinh khóa. 3. Kết luận Thuật toán sinh khóa chứa backdoor mới được đề xuất dựa trên việc cải tiến backdoor tại mục 3 trong [2] với ưu điểm các tham số đầu vào/ra thỏa mãn chuẩn FIPS 186-4. Thuật toán Bảng 2. Kết quả thử nghiệm tính hoàn chỉnh Số lần thử Kết quả (%) Thành công Thất bại 100 100 (100%) 0 (0%) Bảng 3. Kết quả thử nghiệm độ phức tạp phần sinh khóa Bảng 4. Kết quả thử nghiệm độ phức tạp phần khôi phục khóa Lần thử nlen Thời gian chạy trung bình Lần thử nlen Thời gian chạy trung bình (s) G0 G1 1 1024 1,32s 1,56s 1 1024 0,2s 2 2048 2,1s 2,39s 2 2048 0,3s 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 107 backdoor đề xuất đã được cài đặt, thử nghiệm trên thiết bị T-Token có kết quả phù hợp với các phân tích về mặt lí thuyết. Thuật toán backdoor đề xuất có thể ứng dụng tốt trong phần sinh khóa của module mật mã dạng hộp đen ứng dụng trong hạ tầng PKI. Ngoài ra thuật toán có thể được xem xét cải tiến theo hướng tăng lực lượng khóa hoặc rút bớt thông tin backdoor. TÀI LIỆU THAM KHẢO [1] FIPS, 2013, FIPS PUB 186-4, Digital Signature Standard, gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf [2] Bạch Nhật Hồng, Lê Quang Huy, 2017. Về một backdoor đối xứng trong sinh khóa RSA. Tạp chí Khoa học Công nghệ Thông tin và Truyền thông, Học viện Công nghệ Bưu chính viễn thông, số 01, 2017, tr. 03-07. [3] Danny Yadron, 2016. FBI confirms it won't tell Apple how it hacked San Bernardino shooter's iPhone. The Guardian, Available online at: https://www.theguardian.com/technology /2016/apr/27/fbi-apple-iphone-secret-hack-san-bernardino [4] D Coppersmith, 1995, Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities. Available online at: https://www.di.ens.fr/~fouque/ens-rennes/ coppersmith.pdf [5] G.Arboit, 2008. Two mathematical security aspects of the rsa cryptosystem. Available online at: [6] Claude Crepeau and Alain Slakmon, 2003. Simple Backdoors for RSA Key Generation, Available online: https://pdfs. semanticscholar.org/0428/db02e8c46cd4b1b8a43359503 bd9509034f6.pdf [7] Nguyễn Thành Trung, 2016. Báo cáo đề tài “Nghiên cứu thiết kế, chế tạo thiết bị PKI Token phục vụ triển khai hệ thống chứng thực điện tử chuyên dùng Chính phủ”. Ban Cơ yếu CP. ABSTRACT A symmetric backdoor in rsa key generation comply with “loose” conditions of fips 186-4 Bạch Nhật Hồng1 and Lê Quang Huy2 1 Faculty of Electronic and Electrical Engineering, Hung Yen University of Technology and Education 2 Department of Digital Certification and Information Securrity, Vietnam Government Information Security Commission This paper presents a propose of a symmetric backdoored RSA key generation algorithm, comply with “loose” conditions of key parameter in FIPS 186-4 [1]. The proposed algorithm improved the backdoor at secsion 3 in [2] with backdoor’s parameters comply with the conditions of FIPS 186-4. In order to assert theoretic analysis, the proposed backdoor are tested with a PKI- Token with suitable results. Keywords: Cryptography, key generation, RSA, backdoor.