Về một backdoor trong sinh khóa RSA tuân thủ điều kiện “chặt” theo chuẩn FIPS 186-4

Nghiên cứu khoa học công nghệ<br /> <br /> VỀ MỘT BACKDOOR TRONG SINH KHÓA RSA TUÂN THỦ<br /> ĐIỀU KIỆN “CHẶT” THEO CHUẨN FIPS 186-4<br /> Lê Quang Huy*<br /> 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<br /> backdoor tuân thủ điều kiện “chặt” về tham số khóa theo chuẩn FIPS 186-4 [1].<br /> Thuật toán đề xuất dựa trên cơ sở thuật toán tìm số nguyên tố của John Gordon [2]<br /> để tạo số nguyên tố mạnh và tấn công phân tích nhân tử của Coppersmith [3] để<br /> giảm lượng thông tin backdoor cần nhúng.<br /> Từ khóa: Mật mã, Sinh khóa, RSA, Backdoor.<br /> <br /> 1. ĐẶT VẤN ĐỀ<br /> Hiện nay, Backdoor trong các hệ mật mã được nghiên cứu và công bố rộng rãi.<br /> Backdoor trong các hệ mật được nghiên cứu chủ yếu tập trung vào phần sinh khóa (key<br /> generation) và phần mã mật (encryption). Tuy nhiên, các nghiên cứu đã công bố về<br /> 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ứ<br /> chưa đề xuất giải pháp tuân thủ một chuẩn nhất định. Với hệ mật RSA, nhiều tổ chức định<br /> 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<br /> 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<br /> định. Hiện tại, chuẩn FIPS 186-4 về chữ ký số là chuẩn mới nhất có bao gồm hệ mật RSA,<br /> được nhiều nhà sản xuất các sản phẩm mật mã tuân thủ.<br /> Thuật toán sinh khóa chứa backdoor nhằm đảm bảo an ninh, an toàn cho cộng đồng. Đối<br /> tượng áp dụng là các module mật mã dạng hộp đen. Để có thể ứng dụng được vào các<br /> module mật mã dạng hộp đen hiện có, bài báo tập trung nghiên cứu các thuật toán sinh khóa<br /> RSA chứa backdoor và đề xuất một thuật toán sinh khóa RSA chứa backdoor mới tuân thủ<br /> điều kiện “chặt” về tham số khóa tại Appendix B.3.1. FIPS 186-4 [1]. Thực hiện mục tiêu<br /> trên, bài báo được tổ chức thành 4 phần: Mục 1 - Đặt vấn đề, nêu lên sự cần thiết nghiên<br /> cứu; Mục 2 - Các định nghĩa và cơ sở phục vụ cho việc phân tích backdoor; Mục 3 - Đề xuất<br /> backdoor mới; Mục 4 - Kết luận tóm tắt các kết quả nghiên cứu và hướng phát triển.<br /> 2. CÁC ĐỊNH NGHĨA VÀ CƠ SỞ<br /> 2.1. Thuật toán sinh khóa chứa backdoor<br /> Định nghĩa về thuật toán sinh khóa chứa backdoor và các thuộc tính có liên quan (tiêu<br /> chuẩn đánh giá) trình bày trong phần này sử dụng các kết quả trong [4].<br /> 2.1.1. Định nghĩa thuật toán sinh khóa chứa backdoor<br /> Ký hiệu G0, G1 lần lượt là thuật toán sinh khóa trung thực (chuẩn) và thuật toán sinh<br /> khóa chứa backdoor. Ký hiệu (kpriv , kpub) lần lượt là khóa riêng và khóa công khai được tạo<br /> bởi G0 hoặc G1. Ký hiệu kpub* là khóa công khai hoặc một phần của khóa công khai. Ký<br /> hiệu  là tham số an toàn của hệ mật. Ký hiệu B0 , B1 lần lượt là sản phẩm hộp đen được<br /> cài đặt thuật toán sinh khóa G0, G1. Ký hiệu R1 là thuật toán khôi phục cặp khóa được tạo<br /> bởi G1.<br /> Định nghĩa: Các cặp khóa được tạo ra bởi G1 là các cặp khóa chứa backdoor an toàn nếu<br /> G1 tạo ra cặp khóa (kpub, kpriv) với các thuộc tính sau được thỏa mãn:<br /> 1. Tính bảo mật:<br /> a) người thiết kế nhúng một phần khóa riêng vào trong khóa công khai tương ứng, kpub*<br /> = M ◦ E ◦ I (kpriv) (1)<br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 52, 12 - 2017 131<br />  Công nghệ thông tin & Cơ sở toán học cho tin học<br /> <br /> b) Người dùng, kẻ tấn công không thể tính toán được khóa riêng từ khóa công khai<br /> tương ứng, kpriv ≠ I -1 ◦ E -1 ◦ M-1 (kpub) (2)<br /> 2. Tính hoàn chỉnh: Tồn tại thuật toán R1 , để người thiết kế có thể khôi phục được khóa<br /> riêng từ khóa công khai tương ứng, kpriv = R1(kpub). Hay các hàm M, E, I khả nghịch để<br /> người thiết kế tính được kpriv = I -1 ◦ E -1 ◦ M-1 (kpub) (3)<br /> 3. Khả năng ẩn giấu (khả năng không thể phân biệt được):<br /> a) Đầu ra của B0 và B1 không thể phân biệt được về thống kê hoặc về tính toán.<br /> b) Các đo đạc bên ngoài B0 và B1 không thể phân biệt được một cách rõ ràng.<br /> 2.1.2. Một số tiêu chuẩn đánh giá thuật toán sinh khóa chứa backdoor<br /> Các tiêu chuẩn đánh giá G1 (mục 5 trong [4]) được tóm tắt trong bảng sau:<br /> Bảng 1. Các tiêu chuẩn đánh giá thuật toán sinh khóa chứa backdoor.<br /> Đánh giá<br /> Tốt Trung bình Kém (thất bại)<br /> Tiêu chuẩn<br /> Bảo mật lE >= lG1 lG1 >= lE >= lG1 /2 lE < lG1 /2<br /> ∀ kpub kẻ tấn công kpriv ≠ ∃ kpub kẻ tấn công kpriv<br /> Hoàn chỉnh -<br /> F-1 (kpub) = F-1 (kpub)<br /> Lực lượng khóa c >= - ½ -1/2 > c >= -3/2 c < -3/2<br /> Tính phân phối D G1 ≈ 0 D G1 ≈ 0 D G1 > 0<br /> ∃ thành phần khóa<br /> Tính tương quan Không tương quan -<br /> tương quan<br /> Tuyến tính (a =< 1 và c < bậc 2 (2 > a > 1 >= bậc 2 (a >= 2 hoặc<br /> Độ phức tạp<br /> =< 1) hoặc 2 > c > 1) c >= 2)<br /> Bộ nhớ Không dùng VM, NM Chỉ dùng VM Dùng NM<br /> 2.3. Một số kết quả về hệ mật RSA<br /> 2.3.1. Định lý về số các số nguyên tố<br /> Ký hiệu π(n) là số lượng các số nguyên tố nhỏ hơn hoặc bằng n.<br /> Thì khi n lớn, ta có ( )~ (4)<br /> Giả sử p là số nguyên tố k bít, số lượng các số nguyên tố k-bit<br /> ( )<br /> #{ } = 2 − 2 = ( )<br /> ≈ = ≈2 (5)<br /> Xác xuất một số nguyên k bít là số nguyên tố:<br /> ( )<br /> Pr[ ố à ố ê ố] = ≈ =2 = (6)<br /> 2.3.2. Định lý Coppersmith (Theorem 4, 5 trong [3] và được chứng minh trong [7])<br /> Trong thời gian đa thức, có thể tìm được phân tích nhân tử của n = p.q nếu biết ¼ log2<br /> n (khoảng ½ độ dài bit của p) các bít thấp (cao) của p.<br /> 2.3.3. Điều kiện “chặt” về tham số khóa RSA theo FIPS 186-4<br /> Phần này trình bày điều kiện “chặt” về tham số khóa của hệ mật RSA. “Chặt” ở đây<br /> được hiểu là yêu cầu cao nhất đối với tham số p và q được mô tả tại phần B1 mục B.3.1<br /> appendix B, FIPS 186-4.<br /> 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ố.<br /> 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:<br /> 1. p và q là những số nguyên tố được tạo ngẫu nhiên thỏa mãn điều kiện:<br /> <br /> <br /> <br /> 132 Lê Quang Huy, “Về một backdoor trong sinh khóa RSA… theo chuẩn FIPS 186-4.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> - p, q là các số nguyên tố chứng minh được.<br /> - p1, p2, q1, q2 lần lượt là nhân tử nguyên tố của các số (p - 1), (p + 1), (q - 1), (q + 1),<br /> (các số nguyên tố phụ của p, q) là các số nguyên tố có thể chứng minh được.<br /> - Ký hiệu n1, n2, n3, n4 lần lượt là chiều dài theo bit của p1, p2, q1, q2. Chiều dài của các<br /> số nguyên tố phụ tuân thủ các ràng buộc trong bảng 2.<br /> Bảng 2. Chiều dài tối thiểu và tối đa của p1, p2, q1 và q2.<br /> nlen Chiều dài tối thiểu của Chiều dài tối đa của<br /> p1, p2, q1, q2 len(p1) + len(p2) và len(q1) + len(q2)<br /> 1024 > 100 bits > nlen/16 = 64 < 239 bits = nlen/4 - 17<br /> 2048 > 140 bits > nlen/16 = 128 < 494 bits = nlen/4 - 18<br /> 3072 > 170 bits < nlen/16 = 192 < 750 bits = nlen/4 - 18<br /> 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.<br /> 3. Các số nguyên tố p và q thỏa mãn các ràng buộc sau:<br /> a) (p - 1), (q - 1) nguyên tố cùng nhau với số mũ công khai e.<br /> / /<br /> b) √2 . 2 ≤ , ≤ 2 −1 (7).<br /> | | /<br /> c) − > 2 (8).<br /> 4. Số mũ riêng d, được tạo sau khi tạo p và q, thỏa mãn:<br /> 2nlen / 2 < d < LCM (p - 1, q - 1) và d = e-1 mod (LCM (p - 1, q - 1)).<br /> 2.3.4. Thuật toán sinh khóa RSA tuân thủ điều kiện 2.3.3 (thuật toán G0)<br /> Các số nguyên tố p, q được tạo dựa trên cơ sở của thuật toán tìm số nguyên tố mạnh<br /> của John Gordon [2], các số nguyên tố phụ p1, p2, q1, q2 được tạo dựa trên thuật toán sinh<br /> số nguyên tố chứng minh được của Maurer ([6]). Giá trị Bp , Bq được tính dựa theo định lý<br /> phần dư Trung Hoa (CRT).<br /> Input: nlen, n1, n2, n3, n4 8. q1 = RandomProvablePrime(2 ,2 )<br /> Output: p, q, n, e, d 9. q2 = RandomProvablePrime(2 ,2 )<br /> // generate e 10. Aq = q1.q2.<br /> 1. e = RandomOddInteger(216, 2256) 1<br /> // generate p 11. = //using CRT<br /> −1<br /> 2. p1 = RandomProvablePrime(2 ,2 )<br /> 12. Sq ={ Aq.j + Bq } (i = 1, 2, 3, …)<br /> 3. p2 = RandomProvablePrime (2 ,2 )<br /> 13. =<br /> 4. Ap = p1.p2.<br /> / /<br /> 1 ∩ √2. 2 ,2 −1<br /> 5. = // using CRT such that gcd(q - 1, e) = 1<br /> −1 nlen/2 – 100<br /> 6. Sp = { Ap.i + Bp } (i = 1, 2, 3, …) 14. if ( |p – q| ≤ 2 ) then go to step 8.<br /> 7. = // compute n, d<br /> ∩ √2. 2 /<br /> ,2 /<br /> −1 15. n = p.q<br /> 16. d = e–1 mod (LCM(p - 1, q - 1))<br /> such that gcd(p - 1, e) = 1 nlen/ 2<br /> // generate q 17. if ( d < 2 ) then go to step 8.<br /> 18. return (p, q, n, e, d)<br /> 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 2.3.3<br /> Số lượng phần tử e, #{ e }= (2256 - 216)/2 = (2255 - 215) ≥ 2254 (e là số lẻ).<br /> Xét cách tạo p: Vì p1 , p2 là các số nguyên tố thỏa mãn điều kiện tại bảng 1 nên ước<br /> lượng chiều dài theo bit của p1 , p2 : (nlen/16) ≤ log2 p1 , log2 p2 ≤ (nlen/8 - 9).<br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 52, 12 - 2017 133<br />  Công nghệ thông tin & Cơ sở toán học cho tin học<br /> <br /> Tập Sp được tạo bởi p1 và p2 theo thuật toán sinh số nguyên tố chứng minh được của<br /> Maurer. Số lượng số nguyên tố được sinh bởi thuật toán của Maurer sau vài mức đệ quy<br /> đạt khoảng 10% trong tất cả các số nguyên tố (mục 3.4 trong [6]).<br /> Vậy số lượng các số nguyên tố p1 và p2 = {10% các số nguyên tố (2nlen/16, 2nlen/8-9)}≈<br /> 1/8 * các số nguyên tố (2nlen/16, 2nlen/8-9)<br /> / /<br /> #{ } = #{ } = 2 . 2 − 2 =2 . −<br /> ( / ). / .<br /> / . / ( ). / / /<br /> =2 . ( ).<br /> > = (9)<br /> / / . /<br /> Vì p là một số nguyên tố nằm trong tập Sp và nằm trong khoảng<br /> / /<br /> √2. 2 ,2 − 1 . Ký hiệu s ∈ Sp , ta có s = Ap.i + Bp, (bước 6), Ta có<br /> / /<br /> / / √ .<br /> √2. 2 < . + (13)<br /> Vậy lực lượng khóa của thuật toán là, #{(p, q, d, e)} = #{e}.#{(p}.#{q)}<br /> <br /> <br /> <br /> 134 Lê Quang Huy, “Về một backdoor trong sinh khóa RSA… theo chuẩn FIPS 186-4.”<br /> Nghiên cứu khoa học công nghệ<br /> / /<br /> = 2254 . . = 2254 . (14)<br /> 3. ĐỀ XUẤT THUẬT TOÁN SINH KHÓA RSA CHỨA BACKDOOR MỚI<br /> 3.1. Giới thiệu thuật toán đề xuất<br /> Thuật toán đề xuất sử dụng ý tưởng của thuật toán tìm số nguyên tố mạnh của John<br /> Gordon [2] thỏa mãn các điều kiện tại 2.3.3, để cài thông tin backdoor vào một nửa các bit<br /> thấp của p. Thông tin backdoor được mã mật hóa (hoặc băm) bởi hàm FK. Giá trị p được<br /> khôi phục thông qua thuật toán của Coppersmith [3].<br /> Các tham số thuật toán:<br /> + G1 = Thuật toán đề xuất; I(kpriv) = ((p⌋k/2)⌋); E = FK = AES,<br /> E = log2 n = nlen, k(E) = (K); M = n; log2 p = log2 q = nlen/2.<br /> + 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 kết quả của định<br /> lý Coppersmith (mục 2.3.2), ví dụ: p = G(n, 2k/2, p mod 2k/2); (nlen = 2k)<br /> + Giá trị Bp, Bq: có thể được tính thông qua định lý phần dư Trung Hoa (CRT).<br /> + Giá trị m là một ngưỡng để chọn giá trị ngẫu nhiên t không quá lớn để có thể dò tìm<br /> lại trong thuật toán khôi phục khóa.<br /> Thuật toán đề xuất: Sinh khóa RSA<br /> Input: nlen, n1, n2, n3, n4, m // generate q<br /> Output: p, q, n, e, d 11. q1 = RandomProvablePrime(2 ,2 )<br /> // generate e 12. q2 = RandomProvablePrime(2 ,2 )<br /> 1. e = RandomOddInteger(216, 2256) 13. Aq = q1.q2.<br /> 2. u = FK(e) //encryption or hash with 1<br /> key 14. = //using CRT<br /> −1<br /> 3. t = Random(m) // t < m<br /> 15. Sq ={ Aq.j + Bq } (i = 1, 2, 3, …)<br /> 4. C = ut mod 2nlen/4<br /> 16. =<br /> // generate p<br /> / /<br /> 5. p1 = RandomProvablePrime(2 ,2 ) ∩ √2. 2 ,2 −1<br /> 6. p2 = RandomProvablePrime (2 ,2 ) such that gcd(q - 1, e) = 1<br /> 7. Ap = p1.p2. 2nlen/4 17. if ( |p – q| ≤ 2<br /> nlen/2 – 100<br /> ) then go to step<br /> 1 11.<br /> 8. = −1 // using CRT // compute n, d<br /> / 18. n = p.q<br /> 2<br /> 9. Sp = { Ap.i + Bp } (i = 1, 2, 3, …) 19. d = e–1 mod (LCM(p - 1, q - 1))<br /> nlen/ 2<br /> 10. = 17. if ( d < 2 ) then go to step 11.<br /> / / 18. return (p, q, n, e, d).<br /> ∩ √2. 2 ,2 −1<br /> such that gcd(p - 1, e) = 1<br /> Thuật toán đề xuất: khôi phục khóa RSA<br /> Input: n, e, m 5. if C mod 2 = 1 then<br /> Output: p, q, d 6. p = G(n, 2nlen/4, C) //Coppersmith (2.3.2)<br /> 1. t = 1, C = 1 7. t=t+1<br /> 2. u = FK(e) 8. until (p mod 2nlen/4 = C) and (p is prime) and (t < m)<br /> 3. repeat 9. q =n / p;<br /> 4. C = C.u mod 2nlen/4 10. d = e–1 mod (LCM(p - 1, q - 1))<br /> t nlen/4<br /> //(C = u mod 2 ) 11. return (p, q, d)<br /> 3.2. Đánh giá thuật toán đề xuất<br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 52, 12 - 2017 135<br />  Công nghệ thông tin & Cơ sở toán học cho tin học<br /> <br /> Tính bảo mật: Tính bảo mật được đánh giá ở mức tốt vì người thiết kế sử dụng hệ mật đối<br /> xứng, hoặc hàm băm có khóa với độ dài tham số an toàn tương đương với độ dài tham số<br /> an toàn của người dùng.<br /> Tính hoàn chỉnh: Tính hoàn chỉnh được đánh giá ở mức tốt. Với thuật toán đề xuất người<br /> thiết kế luôn tính được khóa riêng từ khóa công khai tương ứng và kẻ tấn công không thể<br /> tính toán được khóa riêng, từ khóa công khai của người dùng.<br /> Lực lượng khóa:<br /> /<br /> Xét việc tạo p (bước 5 đến 10). Theo (9), ta có #{ } = #{ } ≈<br /> Ký hiệu s ∈ Sp , ta có s = Ap.i + Bp , (bước 9) và #{ s } = #{ i }<br /> / / / /<br /> √ . √ .<br /> ≤ ⇔ / ≤ ≤ /<br /> . . . .<br /> / / / /<br /> √ . √ .<br /> / / ≤ ≤ / / ⇔ / ≤ ≤ /<br /> . . .<br /> / / / /<br /> √ . ( √ ). ( √ ).<br /> ⇒#{ } = / = / = / = 2 . 0,6 ≈ 2<br /> Vậy số lượng các số nguyên của bởi tập Sp,<br /> / / /<br /> # Sp = #{p1}. #{p2}.#{i } = . .2 =<br /> Theo (6), ta có Pr[ ố à ê ố] = ,<br /> / . /<br /> Vậy số lượng p, #{p}= # Sp . Pr[số k bit là nguyên tố] = = (15)<br /> . /<br /> Xét cách tạo q, vì q được tạo giống như q trong thuật toán mục 2.3.4, độc lập với p và<br /> /<br /> thỏa mãn điều kiện (8). Theo (13), vậy #{ } ≈ (16)<br /> Cách tạo d, cũng giống như trong thuật toán mục 2.3.4.<br /> Xét tỷ lệ giữa lực lượng của G1 và G0, vì e, q, d được sinh trong G1 giống như trong G0<br /> nên hạng tử #{e}, #{q} có thể bỏ qua, nên tỷ lệ lực lượng giữa G1 và G0 là:<br /> / /<br /> , / .<br /> = ≈ / =2 =2 (17)<br /> , /<br /> <br /> Vì hằng số c = -1/2 trong tỷ lệ giữa hai lực lượng, , nên theo bảng 1, lực lượng của<br /> G1 được đánh giá ở mức tốt.<br /> Tính chất phân phối: Thông tin backdoor được tạo ngẫu nhiên và được nhúng vào các bit<br /> thấp của p 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.<br /> Việc sinh p, q ngẫu nhiên nên phân phối của n có thể gần với phân bố đều và do vậy,<br /> khoảng cách thống kê giữa thành phần n của G1 và G0 là xấp xỉ bằng 0, DG1 ≈ 0. Vậy tính<br /> chất phân phối của G1 được đánh giá là tốt.<br /> Tương quan giữa các thành phần khóa: Thông tin backdoor đựợc nhúng vào tham số p.<br /> Theo cách thực hiện của thuật toán tham số q được tạo độc lập. Nếu người dùng cố định p<br /> hoặc q và yêu cầu sinh lại q hoặc p thì có thể thực hiện được. Do vậy, tính tương quan<br /> giữa các thành phần khóa của G1 được đánh giá đạt mức tốt.<br /> Độ phức tạp tính toán:<br /> Vì p được tạo gần giống như trong G0 (chỉ khác A, B) nên ta có tp(G0) = tp(G1).<br /> Việc tạo e, q, d giống như trong G0 nên độ phức tạp tạo n là: tn(G1) = tp + tq = tn và độ<br /> phức tạp tạo e là: te (G1) = te (G0).<br /> <br /> <br /> 136 Lê Quang Huy, “Về một backdoor trong sinh khóa RSA… theo chuẩn FIPS 186-4.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> Vậy độ phức tạp của thuật toán là: T(G1) = tn + te . Nên độ phức tạp của G1 được đánh giá<br /> là “tốt” vì nó khác biệt không đáng kể đối với độ phức tạp của G0.<br /> 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ộ<br /> nhớ sử dụng được đánh giá là tốt.<br /> 4. KẾT LUẬN<br /> Dựa trên thuật toán sinh số nguyên tố chứng minh được của Maurer và thuật toán tìm<br /> số nguyên tố mạnh của John Gordon và tấn công phân tích nhân tử của Coppersmith, một<br /> thuật toán sinh khóa RSA chứa backdoor mới thỏa mãn các điều kiện chặt theo chuẩn<br /> FIPS 186-4 được đề xuất. Thuật toán đề xuất được đánh giá tốt trên 7 thuộc tính và có thể<br /> ứng dụng tốt trong phần sinh khóa của thiết bị PKI Token hoặc HSM (Hardware Security<br /> Module). 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<br /> khóa hoặc rút bớt thông tin backdoor.<br /> TÀI LIỆU THAM KHẢO<br /> [1]. FIPS, 2013, FIPS PUB 186-4; Digital Signature Standard,<br /> http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf<br /> [2]. John Gordon, 1985, Strong Primes are Easy to Find. In: Beth T., Cot N., Ingemarsson<br /> I. (eds) Advances in Cryptology<br /> [3]. D Coppersmith, 1995, Small Solutions to Polynomial Equations, and Low Exponent<br /> RSA Vulnerabilities, https://www.di.ens.fr/~fouque/ens-rennes/coppersmith.pdf<br /> [4]. G.Arboit, 2008, Two mathematical security aspects of the rsa cryptosystem,<br /> http://crypto.cs.mcgill.ca/~crepeau/PDF/these-Genevieve.pdf<br /> [5]. A. Menezes, P. van Oorschot, and S. Vanstone, 2001, Handbook of Applied<br /> Cryptography, CRC Press.<br /> [6]. U. Maurer, 1994, Fast Generation of Prime Numbers and Secure Public Key<br /> Cryptographic Parameters, https://pdfs.semanticscholar.org/e<br /> [7]. Alexander May, 2007, Using LLL-Reduction for Solving RSA and Factorization<br /> Problems, https://pdfs.<br /> ABSTRACT<br /> A BACKDOOR IN RSA KEY GENERATION STRICTLY COMPLY WITH FIPS 186-4<br /> In this paper, a proposal of backdoored RSA key generation algorithm strictly<br /> comply with conditions of key parameter in FIPS 186-4 [1] is presented. The<br /> proposed algorithm use John Gordon’s strong prime finding algorithm [2] and using<br /> Coppersmith’s factoring attack [3] to reduce backdoor information for embedding.<br /> Keywords: Cryptography, Key generation, RSA, Backdoor.<br /> <br /> Nhận bài ngày 24 tháng 7 năm 2017<br /> Hoàn thiện ngày 13 tháng 10 năm 2017<br /> Chấp nhận đăng ngày 20 tháng 12 năm 2017<br /> <br /> <br /> Địa chỉ: Cục Chứng thực số và Bảo mật thông tin - Ban Cơ yếu Chính phủ.<br /> *<br /> Email : lequanghuyabc@gmail.com.<br /> <br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 52, 12 - 2017 137<br />