intTypePromotion=1

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

Chia sẻ: ViEngland2711 ViEngland2711 | Ngày: | Loại File: PDF | Số trang:7

0
9
lượt xem
0
download

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

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài viết trình bày đề xuất về một thuật toán sinh khóa RSA chứa backdoor tuân thủ điều kiện “chặt” về tham số khóa theo chuẩn FIPS 186-4 [1]. 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] để tạo số nguyên tố mạnh và tấn công phân tích nhân tử của Coppersmith [3] để giảm lượng thông tin backdoor cần nhúng.

Chủ đề:
Lưu

Nội dung Text: 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 />
ADSENSE
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2