Về một Backdoor bất đối xứng trong sinh khóa RSA tuân thủ điều kiện “lỏng” theo chuẩn Fips 186-4 - Lê Quang huy

Công nghệ thông tin Lê Quang Huy, “Về một backdoor bất đối xứng trong sinh khóa RSA FIPS 186-4.” 162 VỀ MỘT BACKDOOR BẤT ĐỐI XỨNG TRONG SINH KHÓA RSA TUÂN THỦ ĐIỀU KIỆN “LỎNG” THEO CHUẨN FIPS 186-4 Lê Quang Huy* 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 bất đố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 ý tưởng của thuật toán PAP trong [2] và sử dụng kết quả của Coppersmith [3] để giảm lượng thông tin backdoor cần nhúng. Từ khóa: Mật mã, Sinh khóa, RSA, Backdoor. 1. ĐẶT VẤN ĐỀ Mật mã (khóa công khai) được sử dụng rộng rãi để đảm bảo an toàn cho các giao dịch điện tử. Tuy nhiên, khi ứng dụng mật mã, thì xuất hiện nguy cơ sử dụng mật mã để thực hiện các hành vi tội phạm: tạo mã độc tấn công hệ thống thông tin của nhà máy điện hạt nhân, vệ tinh, vũ khí quân sự;giữ bí mật thông tin phục vụ hoạt động: khủng bố, buôn bán vũ khí, ma túy, tống tiền, giết người. Từ các nguy cơ nêu trên nảy sinh nhu cầu khôi phục, giải mã (lấy được bản rõ) các dữ liệu đã mã mật (phá vỡ tính bảo mật) để đảm bảo an ninh cho cộng đồng. Để phá vỡ tính bảo mật cách truyền thống là sử dụng thám mã (phá vỡ hệ mật bằng phương pháp toán học), tuy nhiên, với sự phát triển của các hệ mật mã hiện đại, việc thám mã trở nên ngày càng khó và không khả thi. Sử dụng backdoor để phá vỡ tính bảo mật là hướng được nghiên cứu mới trong thời gian gần đây. Backdoor có nhược điểm làm giảm không gian khóa nhưng có ưu điểm khôi phục lại bản mã nhanh, tất định, chi phí thấp, khó bị phát hiện khi cài đặt trong những sản phẩm mật mã dạng hộp đen. Hiện tại hệ mật RSA được dùng phổ biến trong các sản phẩm mật mã ở thế giới và Việt Nam. Do đó, nghiên cứu backdoor trong hệ mật RSA là việc làm cần thiết để đảm bảo an ninh cho cộng đồng khi sử dụng mật mã. Để có thể xây dựng được thuật toán backdoor trong sinh khóa RSA hiệu quả, bài báo tập trung nghiên cứu các thuật toán sinh khóa 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ủ điều kiện “lỏng” về tham số khóa tại Appendix B.3.1. FIPS 186-4 [1]. Thực hiện mục tiêu 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 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 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. 2. CÁC ĐỊNH NGHĨA VÀ CƠ SỞ 2.1. Thuật toán sinh khóa chứa backdoor Định nghĩa và các tiêu chuẩn đánh giáthuật toán sinh khóa chứa backdoortrình bày trong phần này sử dụng các kết quả trong [4]. 2.1.1. Định nghĩa thuật toán sinh khóa chứa backdoor Ký hiệu G0, G1 lần lượt là thuật toán sinh khóa trung thực và thuật toán sinh 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 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 Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 163 công khai. Ký 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 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 bởi G1. Thuật toán sinh khóa chứa backdoor được biểu diễn thông qua 3 hàm sau và các hàm nghịch đảo tương ứng: - Hàm trích thông tin, ký hiệu I, trích từ khóa riêng kpriv thông tin, I(kpriv), để giấu trong khóa công khai kpub sao cho thông tin được trích đủ để khôi phụckpriv. - Hàm giấu thông tin, ký hiệu E, mã mật hóa thông được trích, I(kpriv), tạo ra thông tin che giấu E(I(kpriv)). Hàm E sử dụng hệ mật đối xứng hoặc bất đối xứng sao cho phân phối đầu ra của E không thể phân biệt được với phân phối đều. - Hàm nhúng thông tin, ký hiệu M, nhúng thông tin backdoor đã mã mật hóa, E(I(kpriv)), vào trong khóa công khai, kpub* = M ◦ E ◦ I(kpriv). Định nghĩa thuật toán sinh khóa chứa backdoor an toàn: 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 G1 tạo ra cặp khóa (kpub,kpriv) thỏa mãn các thuộc tính sau: 1. Tính bảo mật: 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* = M◦E ◦ I(kpriv), 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 tương ứng, kpriv ≠ I -1◦E-1◦M-1(kpub). 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 riêng từ khóa công khai tương ứng,kpriv = R1(kpub). Hay các hàm M , E , Ikhả nghịch để người thiết kế tính được kpriv= I -1◦E-1◦M-1(kpub). 3. Khả năng ẩn (che) giấu (khả năng không thể phân biệt được): a) Kết quả đầu ra của B0 và B1 không thể phân biệt được về thống kê, tính toán. 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. 2.1.2. Một số tiêu chuẩn đánh giá thuật toán sinh khóa chứa backdoor Các tiêu chuẩn đánh giá thuật toán sinh khóa chứa backdoor (mục 5 trong [4]) được tóm tắt trong bảng sau: Bảng 1. Các tiêu chuẩn đánh giá thuật toán sinh khóa chứa backdoor. Đánh giá Tốt Trung bình Kém (thất bại) Tiêu chuẩn Bảo mật lE>= lG1 lG1>= lE>= lG1 /2 lE<lG1 /2 Hoàn chỉnh ∀ kpub kẻ tấn công kpriv ≠ F-1(kpub) - ∃ kpub kẻ tấn công kpriv = F -1(kpub) Lực lượng khóa c >= - ½ -1/2 > c >= -3/2 c < -3/2 Tính phân phối D G1≈ 0 D G1≈ 0 D G1> 0 Tính tương quan Không tương quan - ∃ thành phần khóa tương quan Độ phức tạp Tuyến tính (a =< 1 và c =< 1) a > 1 hoặc 2 > c > 1) >= bậc 2 (a >= 2 hoặc c >= 2) Bộ nhớ Không dùng VM, NM Chỉ dùng VM Dùng NM 2.2. Một số kết quả về hệ mật RSA 2.2.1. Định lý về số các số nguyên tố Công nghệ thông tin Lê Quang Huy, “Về một backdoor bất đối xứng trong sinh khóa RSA FIPS 186-4.” 164 Ký hiệu π(n) là số lượng các số nguyên tố nhỏ hơn hoặc bằng n. Thì khi n lớn, ta có () ~ ;Fact 2.95 trong [5] (1) Giả sử p là số nguyên tố k bít, số lượng các số nguyên tố k-bit #{} = (2) − (2) = () () ≈ = ≈ 2 (2) Xác suất một số nguyên k bít là số nguyên tố: Pr[ố à ố ê ố] = () ≈ = 2 = (3) 2.2.2. Định lý Coppersmith (Theorem 4, 5 trong [3]) 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 ¼ log2n (khoảng ½ độ dài bit của p) các bít thấp (cao) của p. 2.2.3. Đ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 được hiểu là sự so sánh tương đối về điều kiện về tham số p và q giữa các mục A2 với mục A1 và mục B tại phần B.3.1 appendix B, FIPS 186-4[1]. 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. 2/ ≤ , ≤ 2/ − 1 (4) c) | − | > 2/ (5) 4. Số mũ riêng d, được tạo sau khi tạo p và q, thỏa mãn: 2nlen / 2<d< LCM (p- 1, q- 1) và d = e-1mod (LCM (p- 1, q- 1)). 2.2.4. Thuật toán sinh khóa RSA tuân thủ điều kiện 2.2.3 (thuật toán G0) Phần này trình bày thuật toán sinh khóa RSA trung thực tuân thủ điều kiện tại mục 2.2.3 và được tóm tắt theo thuật toán mục B.3.3. appendix B FIPS 186-4. Tham số an toàn của thuật toán G0 (sinh khóa RSA): G0 =nlen ≥ 2048. Input (nlen, e) Output (p, q, n, e, d) 1:if (e 2256)then return failure // generate p 2:p = RandomOddInteger() //log2p =nlen/2 3:if ( < √2. 2/) 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() //log2q =nlen/2 7:if ( < √2. 2/) 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) Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 165 2.2.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.2.3 Số lượng phần tử e, #{e }= (2256- 216)/2= (2255- 215) >2254(e là số lẻ). Xét cách tạo p: Vì p là một số nguyên tố nằm trong khoảng √2. 2/, 2/ − 1 . Nên #{p } = Pr[số nlen/2 bit là số nguyên tố]. 2/ − √2. 2/ ≈ / . 0,6. 2/ = 1,2. / > / = 2/ (6) 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) (7) Vậy #{u}= Pr[số nlen/2 bit là số nguyên tố].(p + 2nlen/2 -100 – (p - 2nlen/2 -100) = / . 2/ = / (8) Vì q được tạo giống như p và sau p thỏa mãn điều kiện (5), 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 (4)) với giá trị là:(2 − √2). 2/ > 2/ . Nên #{q} = #{p} - #{u} = / − / > / = 2/(9) Vậy lực lượng khóa của thuật toán là: #{(p,q,d,e)} = #{e}.#{p}.#{q)} = 2254 . / . / = 2254 . (10) 3. ĐỀ XUẤT THUẬT TOÁN SINH KHÓA RSA CHỨA BACKDOOR MỚI 3.1. Bổ đề 1 Ký hiệu p là một số nguyên tố, r là một số nguyên lẻ với log2p = 2.log2r = k. Gọi u = 2kmodp; v0 = vmodp ; s0 = (v0 + u 2).u-1modp; s = 2k – s0 ; n = s.2k + v (nối s với v, ký hiệu s:v). Thì ta có p | n. Chứng minh: u = 2kmodp⇔ 2k = m.p + u với m∈ Z v0 = vmodp⇔v = l.p + v0 với l∈ Z Từ n = s.2k+v = 2k. (2k – s0) + l.p + v0 = (m.p + u).(m.p + u – s0) + l.p + v0 = m2p2 + (2mu – ms0).p +u 2 – us0 + l.p+ v0 = m2p2 + (2mu – ms0 + l).p + u 2 + v0 – u(v0 + u 2).u-1modp = (m2p + 2mu – ms0 + l).p mod p Vậy p | n. 3.2. Thuật toán đề xuất thoả mãn điều kiện 2.2.3 Thuật toán sinh khóa RSA chứa backdoor bất đối xứng đề xuất dựa trên ý tưởng của thuật toán PAP trong [2] thỏa mãn các điều kiện ở mục 2.2.3. Thông tin backdoor là một nửa các bit cao của p được mã mật hóa bởi lược đồ mã mật ECIES của hệ mật EC và được giấu trong các bit thấp của n. (Hiện có hai phương pháp nhúng thông tin backdoor là: nhúng vào n hoặc nhúng vào e. Phương pháp nhúng thông tin backdoor vào n có nhiều ưu điểm nên được nghiên cứu nhiều hơn.) Công nghệ thông tin Lê Quang Huy, “Về một backdoor bất đối xứng trong sinh khóa RSA FIPS 186-4.” 166 Các tham số thuật toán đề xuất: + G1 = Thuật toán đề xuất; I(kpriv) = (p⌉k/2); G1 =G0 =nlen ≥ 2048; E = ECIES;E≥ 128 ; M = n; log2p = log2q = k=nlen/2. + Các hàm của lược đồ mã mật ECIES: hàm mã mật hóa EncECIES() và hàm giải mã mật DecECIES(). + Hàm G: {0, 1}2k x {0, 1}k/2x {0, 1}k/2 → {0, 1}k, hàm này thực hiện kết quả của định lý Coppersmith (mục 2.2.2), ví dụ: p = G(n, 2k/2, p div 2k/2) Thuật toán đề xuất [sinh khóa RSA] Input (e, Kpub, B1) Output (p, q, d, e) 1:if (e 2256) then return failure // generate p 2:p = RandomPrime() //log2p =k 3:if ( < √2. 2/) 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:u = 2kmodp//log2q =nlen/2 7: v1 = Enc ECIES (p⌉k/2, Kpub) 8:for i = 0 toB1 9: r = RandomOddInteger() //log2r = k/2 10: v = v1.2 k/2 + r //v = v1 : r 11:v0 = vmodp 12: s0 = (v0 + u 2).u-1modp 13: if (s0≤ 2 k-1) then 14: s = 2k – s0 15: n = s.2k +v; // n = s : v 16: q = n / p//Bổ đề 1 17: if ( < √2. 2/) thennext i 18: if ( |p – q| ≤ 2 nlen/2 – 100 ) thennext i 19: if (gcd(q - 1, e) ≠ 1) thennext i 20:if (PrimalityTest (q)))then break 21: endfor 21: if (PrimalityTest (q)))then goto step 6 22:n = p.q 23:d = e–1 mod (LCM(p - 1, q - 1)) 24:if ( d < 2 nlen/ 2 ) then go to step 6. 25:return (p, q, d, e) Thuật toán đề xuất [khôi phục khóa RSA] Input (n, e, Kpriv) Output (d) 1:v = nmod 2k 2: v1 = v div 2 k/2 3:p1 = Dec ECIES(v1, Kpriv) 4: p =G (n, 2k/2, p1) //định lý Coppersmith 5: q = n / p 6: d ≡ e−1 mod φ(n). 7: return (d). 3.3. Đánh giá thuật toán đề xuất 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 lược độ mã mật ECIEScủa hệ mật EC có độ dài tham số an toàn E≥ 128 tương đương với độ dài tham số an toàn của người dùng G1 ≥ 2048(bảng 7.9 trong [6]). 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 thiết kế luôn tính được khóa riêng từ khóa công khai tương ứng (thuật toán khôi phục khóa). Kẻ tấn công chỉ tính được khóa riêng của người dùng khi phá vỡ được hệ mật của người thiết kế (lược đồ mã mật ECIES). Lực lượng khóa: Xét việc tạo p (từ bước 2 đến bước 5). Vì p được tạo ngẫu nhiên và giống như trong thuật toán mục 2.2.4 nên theo (6), ta có #{p} = / = 2/. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 167 Xét việc tạo q(từ bước 6 đến bước 21). Với mỗi p có thể chọn ngẫu nhiên 2k/2-1 giá trị r , do đó, tạo được 2k/2 - 1 giá trị n và tạo được 2k/2 - 1giá trị q. Vì q được tính theo n và p (bước 16), nên #{ q}= #{n / p } . Pr[ à ố ê ố] #{ q} = 2/. 2(/) = 2/(/) = 2/ Vậy số lượng n là: #{n} = #{p} . #{q} = 2/. 2/(/) = 2/ 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 = 2/ = 2/ Vì hằng số c= -1/2 trong nên lực lượng của G1 được đánh giá là tốt. Tính chất 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 lược đồ mã mật ECIES (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 n cho p với giá trị n phụ thuộc một phần vào p, tham số ngẫu nhiên r. Do vậy, phân phối của n có thể gần với phân bố đều và vì vậy 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 chất phân phối của G1 được đánh giá là tốt. Tương quan giữa các thành phần khóa: Theo cách tạo q (từ bước 6 đến bước 21), q phụ thuộc vào một phần của p, tham số ngẫu nhiên r. Nếu người dùng cố định p và yêu cầu sinh lại q thì việc sinh lại 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). Do vậy, tính tương quan giữa các thành phần khóa 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 6 đến bước 21) có thêm việc mã mật hóa thông tin backdoor bằng lược đồ mã mật ECIES và vòng lặp (for) với số lần cố định (B1). Do đó, độ phức tạp của việc tạo q trong G1 là: tq (G1) = tq (G0) + T(ECIES). Vậy độ phức tạp tạo n là: tn(G1) = tp + tq+ T(ECIES). Vì độ phức tạp của lược đồ mã mật ECIES không đáng kể so độ phức tạp của việc tạo p hoặc q, do đó, độ phức tạp của G1 được đánh giá là “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á là tốt. 3.4. Tóm tắt các ưu điểm của thuật toán đề xuất so với thuật toán PAP Thuật toán đề xuất ưu điểm hơn so với thuật toán PAP ở những điểm sau: - Các tham số khóa của thuật toán đề xuất thỏa mãn điều kiện 2.3.3 (tuân thủ FIPS 186-4), các tham số thuật toán PAP không đề cập tuân thủ chuẩn nào. Công nghệ thông tin Lê Quang Huy, “Về một backdoor bất đối xứng trong sinh khóa RSA FIPS 186-4.” 168 - Tính bảo mật: thuật toán đề xuất sử dụng lược đồ mã mật ECIES (có độ an toàn tương đương với độ an toàn hệ mật của người dùng) để mã mật thông tin backdoor nên tính bảo mật được đảm bảo. Thuật toán PAP có độ dài khóa của người thiết kế bằng một nửa độ dài khóa của người dùng nên tính bảo mật có điểm yếu. - Lực lượng: Tỷ lệ lực lượng của thuật toán đề xuất = 2 / được đánh giá là tốt, và lớn hơn (tốt hơn) so với tỷ lệ lực lượng thuật toán PAP = 2 , được đánh giá trung bình. - Độ phức tạp của thuật toán đề xuất, T(G1) = tp + tq+ T(ECIES) ít phức tạp hơn độ phức tạp của thuật toán PAP, T(G1) = tp + tq+ T(FK) + T(GK) + T(RSA-k). - Thuật toán khôi phục khóa của thuật toán đề xuất đơn giản hơn (không phải thử 2 trường hợp) so với thuật toán khôi phục khóa của thuật toán PAP. 4. KẾT LUẬN Dựa trên ý tưởng của thuật toán PAP, một thuật toán sinh khóa chứa backdoor bất đối xứng mới được đề xuất có các ưu điểm tốt hơn so với thuật toán PAP và thỏa mãn điều kiện về tham số khóa tạiphần A2 mục B.3.1 appendix B, FIPS 186- 4. Thuật toán đề xuất có thể ứng dụng tốt trong phần sinh khóa của các module mật mã dạng hộp đen như thiết bị PKI Token hoặc HSM (Hardware Security 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 khóa hoặc rút bớt thông tin backdoor để backdoor càng khó bị phát hiện hơn. TÀI LIỆU THAM KHẢO [1]. FIPS, 2013, FIPS PUB 186-4;Digital Signature Standard, [2]. Young A and Yung M, 1996, The Dark Side of “Black-Box” Cryptography or: Should We Trust Capstone?, ype=pdf [3]. D Coppersmith, 1995, Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities, https://www.di.ens.fr/~fouque/ens-rennes/coppersmith.pdf [4]. G.Arboit, 2008, Two mathematical security aspects of the rsa cryptosystem, [5]. A. Menezes, P. van Oorschot, and S. Vanstone, 2001,Handbook of Applied Cryptography, CRC Press. [6]. Bruce Schneier, 1996, Applied Cryptography: Second Edition, Wiley Computer Publishing, John Wiley & Sons, Inc. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 169 ABSTRACT A ASYMMETRIC BACKDOOR INRSA KEY GENERATIONEASILY COMPLY WITH FIPS 186-4 In this paper, a propose of a asymmetric backdoored RSA key generationalgorithmeasily comply with conditions of key parameter in FIPS 186-4 [1] is presented. The proposed algorithm use the idea of PAP’s algorithm [2] anduse Coppersmith’s factoring attack[3]to reduce backdoor information for embedding. Keywords: Cryptography, Key generation, RSA, Backdoor. Nhận bài ngày 15 tháng8năm 2017 Hoàn thiện ngày 16 tháng10 năm 2017 Chấp nhận đăng ngày 28 tháng 11 năm 2017 Địa chỉ: Cục Chứng thực số và Bảo mật thông tin - Ban Cơ yếu Chính phủ. *Email: [email protected].