Luận án Nghiên cứu, phát triển một số thuật toán sinh khóa RSA chứa backdoor

en và đề xuất môi trường ứng dụng. Kết quả nghiên cứu về thuật toán backdoor BD3 được công bố tại bài báo [2] trong mục “Các công trình khoa học đã công bố”. 3.1. Thuật toán sinh khóa trung thực tuân thủ điều kiện “P2” 3.1.1. Giới thiệu thuật toán Thuật toán sinh khóa RSA trung thực (thuật toán G0) tuân thủ điều kiện “P2” là thuật toán sinh khóa RSA trung thực tuân thủ điều kiện “P2” tại mục 1.4.3 và theo mô tả thuật toán tại mục B.3.4 appendix B FIPS 186-4 [27]. Nhìn chung thuật toán sinh khóa RSA trung thực tuân thủ điều kiện “P2” dựa trên thuật toán sinh khóa RSA tổng quát. Điểm khác biệt là trong thuật toán sinh khóa trung thực tuân thủ điều kiện “P2”, 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 của John Gordon [31]. Sau khi được tạo, các tham số đều được kiểm tra thỏa mãn điều kiện “P2” theo chuẩn FIPS 186-4. Trong phần tạo số nguyên tố p, q theo thuật toán tìm số nguyên tố mạnh của John Gordon, các số nguyên tố phụ p1, p2, q1, q2 được tạo dựa trên thuật toán sinh số nguyên tố chứng minh được của Maurer ([41]). Các giá trị Bp , Bq được tính dựa theo định lý phần dư Trung Hoa (CRT). Hàm RandomProvablePrime() tạo số nguyên tố chứng minh được theo phương pháp của Maurer [41]. Nội dung thuật toán sinh khóa RSA trung thực tuân thủ điều kiện “P2” được mô tả dưới dạng sơ đồ khối ở hình 3.1 và mã giả thuật toán ở mục thuật toán 3.1. 82 Sơ đồ khối thuật toán sinh khóa trung thực tuân thủ điều kiện “P2”: Mã giả thuật toán sinh khóa trung thực tuân thủ điều kiện “P2”: Input: e, nlen, n1, n2, n3, n4 Output: p, q, n, d Start e, nlen, n1, n2, n3, n4 2 16 < e < 2 256 nlen 1024 Trả về mã lỗi Stop No Tạo số nguyên tố p Tạo các số nguyên tố phụ q1, q2 GCD (q - 1, e) = 1 (1,41 . 2 nlen/2-1 q < 2nlen/2) |p – q| > 2nlen/2 – 100 Yes Yes No Tính n, d 2 nlen/ 2 < d< LCM (p-1, q-1) Yes No p, q, n, d Hình 3.1. Sơ đồ khối thuật toán sinh khóa trung thực tuân thủ điều kiện P2" GCD (p - 1, e) = 1 (1,41.2 nlen/2-1 p < 2 nlen/2 ) Yes No Tạo số nguyên tố qTạo số nguyên tố q Chiều dài tối thiểu và tối đa của các số nguyên tố phụ q1, q2 No Yes Tạo các số nguyên tố phụ p1, p2 Chiều dài tối thiểu và tối đa của các số nguyên tố phụ p1, p2 No Yes Tạo số nguyên tố p 83 1: Input: e, nlen, n1, n2, n3, n4 ; 2: if (e 2256 or nlen < 1024) then return failure; // generate p 3: p1 = RandomProvablePrime(2𝑛1−1, 2𝑛1) ; 4: p2 = RandomProvablePrime (2𝑛2−1, 2𝑛2) ; 5: Ap = p1.p2 ; 6: 𝐵𝑝 = { 1 𝑚𝑜𝑑 𝑝1 −1 𝑚𝑜𝑑 𝑝2 ; // using CRT 7: Sp = { Ap.i + Bp }; (i = 1, 2, 3, ) 8: 𝑝 = 𝑃𝑟𝑖𝑚𝑒 (𝑆𝑝 ∩ (√2. 2 𝑛𝑙𝑒𝑛/2−1, 2𝑛𝑙𝑒𝑛/2 − 1));such that gcd(p - 1, e) = 1 // generate q 9: q1 = RandomProvablePrime(2𝑛3−1, 2𝑛3) ; 10: q2 = RandomProvablePrime(2𝑛4−1, 2𝑛4) ; 11: Aq = q1.q2 ; 12: 𝐵𝑞 = { 1 𝑚𝑜𝑑 𝑞1 −1 𝑚𝑜𝑑 𝑞2 ; //using CRT 13: Sq ={ Aq.j + Bq } ; (i = 1, 2, 3, ) 14: 𝑞 = 𝑃𝑟𝑖𝑚𝑒 (𝑆𝑞 ∩ (√2. 2 𝑛𝑙𝑒𝑛/2−1, 2𝑛𝑙𝑒𝑛/2 − 1));such that gcd(q - 1, e) = 1 15: if ( |p – q| ≤ 2 nlen/2 – 100 ) then go to step 9 ; // compute n, d 16: n = p.q ; 17: d = e–1 mod (LCM(p - 1, q - 1)) ; 18: if ( d < 2 nlen/ 2 ) then go to step 9 ; 19: return (p, q, n, d) ; Thuật toán 3.1. Thuật toán sinh khóa trung thực tuân thủ điều kiện “P2”. 84 3.1.2. Lực lượng khóa của thuật toán 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.3 (Chiều dài tối thiểu và tối đa của các số nguyên tố phụ, mục 1.4.3) nên ước lượng chiều dài theo bit của p1 , p2 : (nlen/16) ≤ log2 p1 , log2 p2 ≤ (nlen/8 - 9). 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 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 đạt khoảng 10% trong tất cả các số nguyên tố (mục 3.4 trong [41]). 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)}≈ 1/8 * các số nguyên tố (2nlen/16, 2nlen/8-9) #{𝑝1} = #{𝑝2} = 2 −3. (𝜋 (2 𝑛𝑙𝑒𝑛 8 −9) − 𝜋 (2 𝑛𝑙𝑒𝑛 16 )) = = 2−3. ( 2 𝑛𝑙𝑒𝑛 8 −9 ( 𝑛𝑙𝑒𝑛 8 −9).ln 2 − 2 𝑛𝑙𝑒𝑛 16 𝑛𝑙𝑒𝑛 16 .ln 2 ) = 2−3. 𝑛𝑙𝑒𝑛 16 .2 𝑛𝑙𝑒𝑛 8 −9−(𝑛𝑙𝑒𝑛−9).2 𝑛𝑙𝑒𝑛 16 ( 𝑛𝑙𝑒𝑛 8 −9). 𝑛𝑙𝑒𝑛 16 .ln 2 > 2𝑛𝑙𝑒𝑛/8−14 𝑛𝑙𝑒𝑛/8 = 2𝑛𝑙𝑒𝑛/8−11 𝑛𝑙𝑒𝑛 (3.1) Vì p là một số nguyên tố nằm trong tập Sp và nằm trong khoảng (√2. 2𝑛𝑙𝑒𝑛/2−1, 2𝑛𝑙𝑒𝑛/2 − 1 ). Ký hiệu s ∈ Sp , ta có s = Ap.i + Bp, (bước 7), Ta có √2. 2𝑛𝑙𝑒𝑛/2−1 < 𝐴𝑝. 𝑖 + 𝐵𝑝 < 2 𝑛𝑙𝑒𝑛/2 − 1 ⇔ √2.2𝑛𝑙𝑒𝑛/2 −1−𝐵 𝐴𝑝 ≤ 𝑖 ≤ 2𝑛𝑙𝑒𝑛/2 −𝐵−1 𝐴𝑝 ⇔ √2.2𝑛𝑙𝑒𝑛/2 −1−𝐵 𝑝1.𝑝2 ≤ 𝑖 ≤ 2𝑛𝑙𝑒𝑛/2 −𝐵−1 𝑝1.𝑝2 ⇔ √2.2𝑛𝑙𝑒𝑛/2 −1−𝐵 2𝑛𝑙𝑒𝑛/4 −18 ≤ 𝑖 ≤ 2𝑛𝑙𝑒𝑛/2 −𝐵−1 2𝑛𝑙𝑒𝑛/4 −18 (p1.p2 = 2nlen/4 – 18, dòng 2 bảng 1.3) 85 ⇒ #{𝑠} = #{𝑖} = 2𝑛𝑙𝑒𝑛/2 −√2.2𝑛𝑙𝑒𝑛/2 −1 2𝑛𝑙𝑒𝑛/4 −18 = (2−√2).2𝑛𝑙𝑒𝑛/2 −1 2𝑛𝑙𝑒𝑛/4 −18 ⇔ 218−1(2−√2).2𝑛𝑙𝑒𝑛/2 2𝑛𝑙𝑒𝑛/4 = 217. 0,6. 2𝑛𝑙𝑒𝑛/4 ≈ 216. 2𝑛𝑙𝑒𝑛/4 = 2𝑛𝑙𝑒𝑛/4+16 Vậy # Sp với mỗi một cặp giá trị p1, p2 là: 2𝑛𝑙𝑒𝑛/4+16 (3.2) Vậy số lượng các số nguyên có thể được tạo ra bởi tập Sp, # Sp = #{p1}. #{p2}.#{i} = 2 𝑛𝑙𝑒𝑛/8−11 𝑛𝑙𝑒𝑛 . 2𝑛𝑙𝑒𝑛/8−11 𝑛𝑙𝑒𝑛 . 2𝑛𝑙𝑒𝑛/4+16 = 2𝑛𝑙𝑒𝑛/2−6 𝑛𝑙𝑒𝑛2 Theo công thức (1.7), ta có Pr[𝑠ố 𝑘 𝑏𝑖𝑡 𝑙à 𝑛𝑔𝑢𝑦ê𝑛 𝑡ố] = 1 𝑘𝑙𝑛2 Số lượng số nguyên tố p, #{p} = 2𝑛𝑙𝑒𝑛/2−6 𝑛𝑙𝑒𝑛2.𝑛𝑙𝑒𝑛/2.𝑙𝑛2 ≈ 2𝑛𝑙𝑒𝑛/2−4 𝑛𝑙𝑒𝑛3 (3.3) Xét cách tạo q: Theo (3.1), ta có: #{𝑞1} = #{𝑞2} = 2𝑛𝑙𝑒𝑛/8−11 𝑛𝑙𝑒𝑛 Ký hiệu u là một số nguyên tố và v là một số nguyên; (u, v ∈ Sq ) và (u, v ∈ {ngoài khoảng điều kiện (1.9)} ⇔ {p - 2nlen/2 -100 ≤ u, v ≤ p + 2nlen/2 -100} (3.4) Vì v ∈ Sq, nên v = Aq.j + Bq , do vậy p - 2nlen/2 -100 ≤ Aq.j + Bq ≤ p + 2nlen/2 -100 ⇔ 𝑝−2𝑛𝑙𝑒𝑛/2−100−𝐵𝑞 𝐴𝑞=𝑞1.𝑞2 ≤ 𝑗 ≤ 𝑝+2𝑛𝑙𝑒𝑛/2−100−𝐵𝑞 𝐴𝑞=𝑞1.𝑞2 #{𝑗} = 𝑝 + 2𝑛𝑙𝑒𝑛/2 −100 − (𝑝 − 2𝑛𝑙𝑒𝑛/2 −100) 2𝑛𝑙𝑒𝑛/4 −18 = 2. 2𝑛𝑙𝑒𝑛/2 −100 2𝑛𝑙𝑒𝑛/4 −18 = 2𝑛𝑙𝑒𝑛/4−81 Vậy #{v} = #{q1}. #{q2}.#{j} = 2𝑛𝑙𝑒𝑛/8−11 𝑛𝑙𝑒𝑛 . 2𝑛𝑙𝑒𝑛/8−11 𝑛𝑙𝑒𝑛 . 2𝑛𝑙𝑒𝑛/4−81 = 2𝑛𝑙𝑒𝑛/2−103 𝑛𝑙𝑒𝑛2 86 #{u} = #{v}. Pr[số k bit là số nguyên tố] = 2𝑛𝑙𝑒𝑛/2−103 𝑛𝑙𝑒𝑛2 . 1 𝑛𝑙𝑒𝑛/2.𝑙𝑛2 ≈ 2𝑛𝑙𝑒𝑛/2−101 𝑛𝑙𝑒𝑛3 Vì q được tạo giống như p và sau p thỏa mãn điều kiện (1.9), nằm ngoài khoảng (3.4), mà giá trị khoảng (3.4) có giá trị: (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.8)) với giá trị là : (2 − √2). 2𝑛𝑙𝑒𝑛/2 −1 ≈ 0,6. 2𝑛𝑙𝑒𝑛/2 −1. Nên #{q} = #{p} - #{u} = 2𝑛𝑙𝑒𝑛/2−4 𝑛𝑙𝑒𝑛3 − 2𝑛𝑙𝑒𝑛/2−101 𝑛𝑙𝑒𝑛3 > 2𝑛𝑙𝑒𝑛/2−5 𝑛𝑙𝑒𝑛3 (3.5) Vậy lực lượng khóa của thuật toán là, #{(p, q, e)} = #{p}.#{q}.#{e} = 2255. 2𝑛𝑙𝑒𝑛/2−4 𝑛𝑙𝑒𝑛3 . 2𝑛𝑙𝑒𝑛/2−5 𝑛𝑙𝑒𝑛3 = 2255. 2𝑛𝑙𝑒𝑛−9 𝑛𝑙𝑒𝑛6 (3.6) 3.2. Đề xuất thuật toán backdoor BD3 3.2.1. Giới thiệu thuật toán 3.2.1.1. Tổng quan thuật toán Thuật toán backdoor BD3 là thuật toán sinh khóa RSA chứa backdoor tuân thủ điều kiện “P2” theo chuẩn FIPS 186-4, có các bước thực hiện dựa trên thuật toán sinh khóa trung thực tuân thủ điều kiện G0 mục 2.1.2. Mục tiêu: xây dựng thuật toán sinh khóa chứa backdoor tạo ra các cặp khóa với các tham số mạnh để sử dụng trong các trường hợp đặc biệt. Ý tưởng thiết kế: - Dựa trên thuật toán tìm số nguyên tố mạnh của John Gordon để xây dựng các số nguyên tố chính (p, q), dựa trên thuật toán sinh số nguyên tố chứng minh được của Maurer để tạo các số nguyên tố phụ. - Tuân thủ điều kiện “P2” theo chuẩn FIPS 186-4. 87 - Khôi phục khóa theo phương pháp phân tích nhân tử của Coppersmith. Điểm độc đáo của thuật toán BD3 là kỹ thuật sử dụng thông tin backdoor được dẫn xuất từ số mũ công khai e, tham số ngẫu nhiên t và kỹ thuật nhúng thông tin backdoor vào các bit thấp của số nguyên tố p dựa theo định lý phần dư Trung Hoa (CRT). Đây là điểm khác biệt hẳn so với các thuật toán trước đó. Với thuật toán BD1, BD2 và các thuật toán của các tác giả trước đó, số nguyên tố p được tạo ngẫu nhiên, thông tin backdoor được nhúng vào số modulus n (trong quá trình tạo số nguyên tố q) nên q phụ thuộc một phần vào p dẫn tới tính tương quan của backdoor chỉ đạt mức “trung bình”. Bản thân việc nhúng thông tin backdoor vào các bit thấp mà vẫn đòi hỏi tính nguyên tố của p là việc làm khó đòi hỏi kỹ thuật đặc biệt. Việc nhúng thông tin backdoor vào số nguyên tố p làm tăng thêm tính an toàn, bảo mật cho backdoor, dẫn tới tham số q được tạo độc lập nên p và q không tương quan (độc lập). Dù thuật toán BD3 được công bố công khai, việc dò tìm tham số mật (số nguyên tố p thuộc khóa riêng), để từ đó trích ra thông tin backdoor sẽ khó hơn rất nhiều so với việc trích thông tin backdoor từ trong số modulus n (việc dò tìm tham số mật, số nguyên tố p, là một việc rất khó và đây cũng chính là vấn đề phá vỡ hệ mật RSA). Thuật toán BD3 có các bước thực hiện như sau: Phần sinh khóa: - Thông tin backdoor: một giá trị ngẫu nhiên t được chọn ngẫu nhiên kết hợp với giá trị mầm e, để tính ra thông tin backdoor, C = ut mod 2nlen/4. - Che giấu thông tin backdoor: Giá trị mầm u được hoán vị (che giấu) từ số mũ công khai, e, thông qua hàm mã mật hóa đối xứng (hoặc băm) FK với khóa K của người thiết kế. - Nhúng thông tin backdoor vào khóa: giá trị C được nhúng vào một nửa các bit thấp của số nguyên tố p , theo định lý phần dư Trung Hoa CRT. 88 Phần khôi phục khóa: - Trích (tìm) lại thông tin backdoor đã mã mật và giải mã mật thông tin backdoor: Sử dụng khóa (bí mật) của người thiết kế tính giá trị mầm u từ tham số công khai e. Giá trị t được lặp để dò tìm thỏa mãn điều kiện với t < m. - Khôi phục tham số mật: giá trị C được tính C = ut mod 2nlen/4 và sử dụng phương pháp phân tích nhân tử của Coppersmith (mục 1.3) để tìm giá trị p’. Nếu thỏa mãn điều kiện (p’ mod 2nlen/4 = C và p’ là số nguyên tố) thì p’ chính là giá trị p cần tìm. - Tính toán toàn bộ các tham số khóa riêng: từ tham số p tính các tham số q, d của khóa riêng. Điểm khác biệt của thuật toán BD3 với các backdoor khác ở chỗ: - Thông tin backdoor: được dẫn xuất từ số mũ công khai e và giá trị ngẫu nhiên t với t < m (ngưỡng do người thiết kế chọn). Việc không sử dụng thông tin backdoor là một phần của các tham số mật (p, q) dẫn đến các tham số được tạo độc lập - có tính tương quan cao (vượt qua nhược điểm của nhiều thuật toán backdoor của các tác giả khác). - Thông tin backdoor được nhúng vào các bit thấp của số nguyên tố p (tham số mật của khóa riêng). Các tham số thuật toán backdoor BD3, G1 : I(𝑘𝑝𝑟𝑖𝑣𝐺1 ,) = (p⌋k/2); E = FK = AES, E = nlen = log2 n , k(E) = (K), M = n, log2 p = log2 q = nlen/2. + Giá trị Bp, Bq: được tính thông qua định lý phần dư Trung Hoa (CRT). + 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 lại trong thuật toán khôi phục khóa. 89 + Hàm RandomProvablePrime() tạo số nguyên tố chứng minh được theo phương pháp của Maurer [41]. 3.2.1.2. Phần thuật toán sinh khóa Phần thuật toán sinh khóa được mô tả dưới dạng sơ đồ khối ở hình 3.2 và mã giả thuật toán ở mục thuật toán 3.2. 90 Sơ đồ khối của phần thuật toán sinh khóa backdoor BD3: Mã giả phần thuật toán sinh khóa backdoor BD3: Input: e, nlen, n1, n2, n3, n4, m Output: p, q, n, d 1: Input: e, nlen, n1, n2, n3, n4, m ; Start e, nlen, n1, n2, n3, n4, m 2 16 < e < 2 256 nlen 1024 Trả về mã lỗi Stop No Tạo số nguyên tố p Tạo các số nguyên tố phụ q1, q2 GCD (q - 1, e) = 1 (1,41 . 2 nlen/2-1 q < 2nlen/2) |p – q| > 2nlen/2 – 100 Yes Yes No Tính n, d 2nlen/ 2 < d< LCM (p-1, q-1) Yes No p, q, n, d Hình 3.2. Sơ đồ khối phần thuật toán sinh khóa của backdoor BD3 GCD (p - 1, e) = 1 (1,41.2 nlen/2-1 p < 2 nlen/2 ) Yes No Tạo số nguyên tố q Chiều dài tối thiểu và tối đa của các số nguyên tố phụ q1, q2 No Yes Tạo các số nguyên tố phụ p1, p2 Chiều dài tối thiểu và tối đa của các số nguyên tố phụ p1, p2 No Yes Tạo số nguyên tố p Chuẩn bị thông tin backdoor 91 2: if (e 2256 or nlen < 1024) then return failure; 3: u = FK(e); //encryption or hash with key (backdoor owner) 4: t = Random(m); // t < m 5: C = ut mod 2nlen/4 ; // generate p 6: p1 = RandomProvablePrime(2𝑛1−1, 2𝑛1) ; 7: p2 = RandomProvablePrime (2𝑛2−1, 2𝑛2) ; 8: Ap = p1.p2. 2nlen/4 ; 9: 𝐵𝑝 = { 1 𝑚𝑜𝑑 𝑝1 −1 𝑚𝑜𝑑 𝑝2 𝐶 𝑚𝑜𝑑 2𝑛𝑙𝑒𝑛/4 ; // using CRT 10: Sp = { Ap.i + Bp }; (i = 1, 2, 3, ) 11:𝑝 = 𝑃𝑟𝑖𝑚𝑒 (𝑆𝑝 ∩ (√2. 2 𝑛𝑙𝑒𝑛/2−1, 2𝑛𝑙𝑒𝑛/2 − 1)) ;such that gcd(p - 1, e) = 1 // generate q 12: q1 = RandomProvablePrime(2𝑛1−1, 2𝑛1) ; 13: q2 = RandomProvablePrime(2𝑛2−1, 2𝑛2) ; 14: Aq = q1.q2 ; 15: 𝐵𝑞 = { 1 𝑚𝑜𝑑 𝑞1 −1 𝑚𝑜𝑑 𝑞2 ; //using CRT 16: Sq ={ Aq.j + Bq }; (i = 1, 2, 3, ) 17: 𝑞 = 𝑃𝑟𝑖𝑚𝑒 (𝑆𝑞 ∩ (√2. 2 𝑛𝑙𝑒𝑛/2−1, 2𝑛𝑙𝑒𝑛/2 − 1)) ;such that gcd(q - 1, e)= 1 18: if ( |p – q| ≤ 2 nlen/2 – 100 ) then go to step 12 ; // compute n, d 19: n = p.q ; 20: d = e–1 mod (LCM(p - 1, q - 1)) ; 92 21: if ( d < 2 nlen/ 2 ) then go to step 12 ; 22: return (p, q, n, d) ; Thuật toán 3.2. Phần thuật toán sinh khóa của backdoor BD3. 3.2.1.3. Phần thuật toán khôi phục khóa Phần thuật toán khôi phục khóa được mô tả dưới dạng sơ đồ khối ở hình 3.3 và mã giả thuật toán ở mục thuật toán 3.3 Sơ đồ khối của phần thuật toán khôi phục khóa backdoor BD3: Mã giả phần thuật toán khôi phục khóa: Input: n, e, m Output: p, q, d Start e, n, m Stop Phân tích nhân tử Coppersmith Tính q, d p, q, d Hình 3.3. Sơ đồ khối phần thuật toán khôi phục khóa của backdoor BD3 p null Yes No Tính thông tin backdoor, C 93 1: Input (n, e, m) ; 2: t = 1; C = 1 ; 3: u = FK(e) ; 4: repeat 5: C = C.u mod 2nlen/4 ; //(C = ut mod 2nlen/4) 6: if C mod 2 = 1 then 7: p = CopperSmith(n, 2nlen/4, C) ; //Coppersmith method 8: t = t + 1 ; 9: until (p null) and (p mod 2nlen/4 = C) and (t < m); 10: q = n / p ; 11: d = e–1 mod (LCM(p - 1, q - 1)) ; 12: return (p, q, d) ; Thuật toán 3.3. Phần thuật toán khôi phục khóa của backdoor BD3. 3.2.2. Đánh giá thuật toán backdoor BD3 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, nhưng không có khóa bí mật của người thiết kế. Người thiết kế sử dụng hệ mật đối xứng, hoặc hàm băm với khóa có độ an toàn (độ dài khóa) tương đương với độ an toàn (độ dài tham số khóa) hệ mật RSA của người dùng (mục 1.4.2), giả sử hệ mật của người dùng an toà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 mục 1.2.4.4, 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: 94 Từ giá trị e, người thiết kế tính u = FK(e) ở (bước 3) và với giá trị t ngẫu nhiên, t < m, (bước 4) tính C = ut mod 2nlen/4. Giá trị C là thông tin backdoor được đặt vào trong giá trị Bp (bước 9) và được đặt vào trong các bit thấp của tập các số Sp và cũng là số nguyên tố p. (Thuật toán sinh khóa luôn tạo được các khóa thỏa mãn điều kiện (chuẩn FIPS 186-4) có chứa backdoor) Xét thuật toán khôi phục khóa: Người thiết kế thực hiện tương tự: tính u = FK(e), Thực hiện vòng lặp tối đa m - 1 lần tính C = ut mod 2nlen/4 tính p = S(n, 2nlen/4, C) theo phương pháp Coppersmith (1.3) vòng lặp kết thúc khi thỏa mãn điều kiện ở bước 9 (p mod 2nlen/4 = C) and (p is prime) and (t < m). Các bước trong vòng lặp luôn tất định và thuật toán kết thúc, số nguyên tố p luôn tìm được, vì giá trị t < m được chọn ngẫu nhiên trong thuật toán sinh khóa. Khi có p, sẽ tính q và d, (ở bước 10, 11). (Thuật toán khôi phục khóa luôn cho phép người thiết kế khôi phục được khóa riêng từ khóa công khai tương ứng). 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. Kẻ tấn công không có khóa riêng của người thiết kế và không phá vỡ được độ an toàn của hệ mật người thiết kế (tính bảo mật). Căn cứ vào mục 1.2.4.4, 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 (bước 6 đến 11). 95 Theo (3.1), ta có #{𝑝1} = #{𝑝2} ≈ 2𝑛𝑙𝑒𝑛/8−11 𝑛𝑙𝑒𝑛 Ký hiệu s ∈ Sp , ta có s = Ap.i + Bp , (bước 10) và #{ s } = #{ i } √2.2𝑛𝑙𝑒𝑛/2 −1−𝐵 𝐴 ≤ 𝑖 2𝑛𝑙𝑒𝑛/2 −1−𝐵 𝐴 ⇔ √2.2𝑛𝑙𝑒𝑛/2 −1−𝐵 2𝑛𝑙𝑒𝑛/4.𝑝1.𝑝2 ≤ 𝑖 ≤ 2𝑛𝑙𝑒𝑛/2 −1−𝐵 2𝑛𝑙𝑒𝑛/4.𝑝1.𝑝2 ⇔ √2.2𝑛𝑙𝑒𝑛/2 −1−𝐵 2𝑛𝑙𝑒𝑛/4.2𝑛𝑙𝑒𝑛/4 −18 ≤ 𝑖 ≤ 2𝑛𝑙𝑒𝑛/2 −1−𝐵 2𝑛𝑙𝑒𝑛/4.2𝑛𝑙𝑒𝑛/4 −18 ⇔ √2.2𝑛𝑙𝑒𝑛/2 −1−𝐵 2𝑛𝑙𝑒𝑛/2 −18 ≤ 𝑖 ≤ 2𝑛𝑙𝑒𝑛/2 −1−𝐵 .2𝑛𝑙𝑒𝑛/2 −18 ⇒#{𝑖} = 2 𝑛𝑙𝑒𝑛 2 −√2.2 𝑛𝑙𝑒𝑛 2 −1 2 𝑛𝑙𝑒𝑛 2 −18 = (2−√2).2 𝑛𝑙𝑒𝑛 2 −1 2 𝑛𝑙𝑒𝑛 2 −18 = 218−1(2 − √2). 2𝑛𝑙𝑒𝑛/2 2𝑛𝑙𝑒𝑛/2 = 217. 0,6 ≈ 216 Vậy số lượng các số nguyên của bởi tập Sp, # Sp = #{p1}. #{p2}.#{i } = 2 𝑛𝑙𝑒𝑛/8−11 𝑛𝑙𝑒𝑛 . 2𝑛𝑙𝑒𝑛/8−11 𝑛𝑙𝑒𝑛 . 216 = 2𝑛𝑙𝑒𝑛/4−6 𝑛𝑙𝑒𝑛2 Theo (1.7), ta có Pr[𝑠ố 𝑘 𝑏𝑖𝑡 𝑙à 𝑛𝑔𝑢𝑦ê𝑛 𝑡ố] = 2 𝑘 , Vậy số lượng p, #{p}= # Sp . Pr[số k bit là nguyên tố] #{p} = 2𝑛𝑙𝑒𝑛/4−6.2 𝑛𝑙𝑒𝑛2.𝑛𝑙𝑒𝑛/2 = 2𝑛𝑙𝑒𝑛/4−4 𝑛𝑙𝑒𝑛3 Xét cách tạo q, vì q được tạo giống như q trong thuật toán 3.1, độc lập với p và thỏa mãn điều kiện (1.9). Theo (3.5), vậy #{𝑞} ≈ 2𝑛𝑙𝑒𝑛/2−5 𝑛𝑙𝑒𝑛3 96 Cách tạo d, cũng giống như trong thuật toán 2.1 và #{d} = #{e}. Xét tỷ lệ giữa lực lượng của G1 và G0, vì q, d được sinh trong G1 giống như trong G0 nên hạng tử #{q}, #{d} có thể bỏ qua, nên tỷ lệ lực lượng giữa G1 và G0 là: 𝑅𝐺1 = 𝑁𝐺1,𝑝 𝑁𝐺0,𝑝 ≈ 2𝑛𝑙𝑒𝑛/4−4/𝑛𝑙𝑒𝑛3 2𝑛𝑙𝑒𝑛/2−4/𝑛𝑙𝑒𝑛3 = 2−𝑛𝑙𝑒𝑛/4 = 2− 1 2 . 𝑛𝑙𝑒𝑛 2 Vì hằng số c = -1/2 trong tỷ lệ giữa hai lực lượng, 𝑅𝐺1, và căn cứ vào mục 1.2.4.4, 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 tạo ngẫu nhiên và được nhúng vào các bit 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. Việc sinh p, q ngẫu nhiên nên phân phối của n 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 n của G1 và G0 là xấp xỉ bằng 0, DG1 ≈ 0. Theo mục 1.2.4.4, tính phân phối của G1 được đánh giá là “tốt”. Tính tương quan: Thông tin backdoor đựợc nhúng vào tham số p. 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 hoặc q và yêu cầu sinh lại q hoặc p thì đều có thể thực hiện được (sinh lại khóa tổng quát). Theo mục 1.2.4.4, tính tương quan giữa các thành phần khóa của G1 được đánh giá đạt mức “tốt”. Độ phức tạp tính toán: Vì p được tạo gần giống như trong G0 nên ta có tp(G0) = tp(G1). Việc tạo q giống như trong G0 nên độ phức tạp tạo n là: tn(G1) = tp + tq = tn 97 Vậy độ phức tạp của thuật toán là: T(G1) = tp + tq = tn . Theo mục 1.2.4.4, độ phức tạp của G1 được đánh giá đạt mức “tốt” vì nó khác biệt không đáng kể đố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 căn cứ vào mục 1.2.4.4 tiêu chí bộ nhớ sử dụng của thuật toán được đánh giá đạt mức “tốt”. 3.2.3. So sánh BD3 với các thuật toán backdoor của các tác giả khác Thuật toán đề xuất backdoor BD3 so sánh với các thuật toán backdoor đã công bố của các tác giả khác (đi trước) có một số điểm sau: 3.2.3.1. Các điểm giống - 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. - Hệ mật của người thiết kế: hệ mật đối xứng (AES). 3.2.3.2. Các điểm khác - Thông tin backdoor: được dẫn xuất từ số mũ công khai e và số nguyên ngẫu nhiên t < m, nên các tham số được tạo độc lập - có tính tương quan cao. - Kỹ thuật nhúng thông tin backdoor vào trong các bit thấp của số nguyên tố p làm cho kẻ tấn công khi khôi phục khóa dò tìm tham số mật (số nguyên tố p) khó hơn rất nhiều so với trích thông tin backdoor từ trong số modulus n (nâng cao độ an toàn cho backdoor). - Tham số vào/ra: tuân thủ điều kiện “P2” của chuẩn FIPS 186-4. 3.2.4. Tóm tắt các điểm nổi bật của thuật toán backdoor BD3 Thuật toán backdoor đề xuất BD3 đã kế thừa các ưu điểm và hạn chế các nhược điểm trong các công trình nghiên cứu về backdoor đã công bố của các 98 tác giả đi trước. Thuật toán backdoor BD3 gồm hai phần: phần thuật toán sinh khóa và phần thuật toán khôi phục khóa, có các điểm nổi bật như sau: -Thuật toán sinh khóa: các số nguyên tố chính được xây dựng dựa trên thuật toán tìm số nguyên tố mạnh của John Gordon [31], các số nguyên tố phụ được tìm theo thuật toán sinh số nguyên tố chứng minh được của Maurer [41]. - Thuật toán khôi phục khóa sử dụng phương pháp phân tích nhân tử của Coppersmith (1.3) để khôi phục lại khóa riêng từ khóa công khai tương ứng. - Các tham số đầu ra và đầu vào của thuật toán backdoor BD3 thỏa mãn các điều kiện “P2” theo chuẩn FIPS 186-4 [27]. - Kỹ thuật trích chọn thông tin backdoor và nhúng thông tin backdoor vào các bit thấp của số nguyên tố p nâng cao độ an toàn cho backdoor. - Được đánh giá “tốt” trên 07 tiêu chí. 3.3. Thử nghiệm thuật toán backdoor BD3 3.3.1. Mục tiêu, phương pháp, môi trường thử nghiệm Mục tiêu, phương pháp, môi trường thử nghiệm, cách thức cài đặt trong thiết bị T-Token và các tiêu chí được thử nghiệm của backdoor BD3 giống như với backdoor BD1, BD2 mục (2.4). 3.3.2. Kịch bản thử nghiệm Trên cơ sở mục tiêu, phương pháp và các tiêu chí thử nghiệm, kịch bản thử nghiệm backdoor BD3 được mô tả trong bảng 3.1 như sau: Bảng 3.1. Kịch bản thử nghiệm thuật toán backdoor BD3 99 Mã KB Mô tả Các bước thực hiện Dữ liệu thử nghiệm Kết quả mong muốn SK_BD3 Thử nghiệm độ phức tạp của thuật toán phần sinh cặp khóa của backdoor BD3 - Chuẩn bị dữ liệu đầu vào. - Gọi hàm sinh khóa của Token - Quan sát kết quả đầu ra: thời gian sinh khóa nlen = 1024, 2048 m= 100, 150, 200 các tham số khác chọn giá trị mặc định Thời gian sinh cặp khóa < 4 giây KP_BD3 Thử nghiệm tính hoàn chỉnh và độ phức tạp thuật toán phần khôi phục khóa của backdoor BD3 - Chuẩn bị dữ liệu đầu vào. - Gọi hàm khôi phục khóa của Token - Quan sát kết quả đầu ra: thời gian khôi phục khóa, số lần thất bại khi khôi phục khóa. nlen = 1024, 2048 m= 100, 150, 200 các tham số khác chọn giá trị mặc định Thời gian khôi phục khóa khóa trung bình < 10 giây, số lần thất bại khi khôi phục khóa = 0 TQ_BD3 Thử nghiệm tính tương quan của backdoor BD3 - Cố định từng tham số e, p, q riêng biệt. - Sinh các tham số còn lại. - Kiểm tra tính đúng đắn của các tham số được tạo ra và sự phù hợp với các tham số cố định. - Chọn ngẫu nhiên các tham số e lẻ, tham số p, q là số nguyên tố. Các tham số e, p, q được tạo độc lập, không tương quan. 3.3.3. Kết quả thử nghiệm thuật toán backdoor BD3 Kết quả thử nghiệm thuật toán backdoor BD3 cho thấy: - Độ phức tạp phần sinh khóa: Thời gian tạo khóa phụ thuộc vào các tham số độ dài số modulus (nlen) và ngưỡng giá trị ngẫu nhiên (m). Với tham số đầu vào nlen = 1024, thời gian thực hiện trung bình khoảng 1,8s chậm hơn 100 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 (khoảng 1,5s). Sự khác biệt về thời gian chạy không đủ để trong quá trình sử dụng người dùng có thể phân biệt được giữa một thiết bị chứa thuật toán sinh khóa trung thực và thiết bị chứa thuật toán sinh khóa có backdoor. - Tính tương quan: tham số e có thể chọn tự do mà không ảnh hưởng đến các tham số còn lại. Cố định tham số p, tham số q được sinh lại tự do. Đảo ngược vai trò của p và q (cố định tham số q, sinh lại tham số p) cho kết quả tương tự. Do vậy, 03 tham số được tạo độc lập với nhau và tính tương quan đạt kết quả “tốt”. - Độ phức tạp phần khôi phục khóa: Tốc độ khôi phục khóa riêng của backdoor BD3 tương đối nhanh, khoảng 2s với nlen = 1024. Việc khôi phục khóa 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 nên tính hoàn chỉnh được đảm bảo. Kết quả thử nghiệm độ phức tạp thuật toán backdoor BD3 được trình bày ở bảng 3.2 và minh họa dưới dạng biểu đồ ở hình 3.4. Bảng 3.2. Kết quả thử nghiệm độ phức tạp thuật toán backdoor BD3 Thứ tự nlen (bit) m Thời gian chạy trung bình Sinh khóa G0 Sinh khóa G1 Khôi phục khóa G1 1 1024 100 1.45 1.74 2.04 2 1024 200 1.45 1.92 2.52 3 1024 300 1.45 2.11 3.01 4 2048 100 2.04 2.42 3.13 5 2048 200 2.04 2.78 3.55 6 2048 300 2.04 3.25 3.94 101 Hình 3.4. Biểu đồ kết quả thử nghiệm độ phức tạp thuật toán backdoor BD3 3.3.4. Đánh giá kết quả thử nghiệm backdoor BD3 Kết quả thử nghiệm của thuật toán backdoor BD3 đã đạt được mục tiêu, yêu cầu đề ra với các thông tin cụ thể sau: - Tính hoàn chỉnh được đảm bảo với tất cả các lần thử nghiệm (tất định). - Tính tương quan: đạt kết quả tốt khi thử nghiệm với 03 tham số e, p, q. - Thời gian thực hiện (độ phức tạp tính toán) của phần sinh khóa có tốc độ chậm hơn một chút (tương đối nhỏ) so với thời gian thực hiện của các thuật toán sinh khóa trung thực tương ứng và cũng gần tương đương với thời gian sinh khóa của một số thiết bị PKI Token có sẵn trên thị trường với cùng độ dài khóa. Thời gian thực hiện (độ phức tạp tính toán) của phần khôi phục khóa tương đối nhanh trên máy tính. 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 Thời gian tạo khóa G0 Thời gian tạo khóa G1 Thời gian khôi phục khóa G1 Th ờ i g ia n t h ự c h iệ n ( s) Kết quả thử nghiệm độ phức tạp backdoor BD3 nlen=1024,m=100 nlen=1024,m=200 nlen=1024,m=300 nlen=2048,m=100 nlen=2048,m=200 nlen=2048,m=300 102 3.4. Ứng dụng backdoor BD3 Từ mục tiêu thiết kế của backdoor BD3 nhằm tạo ra các cặp khóa với các tham số mạnh để sử dụng trong các trường hợp đặc biệt và kết quả thuật toán BD3 có các tham số tuân thủ điều kiện “P2” theo chuẩn FIPS 186-4 nên có các tham số chất lượng cao, bền vững trước các tấn công, có thể sử dụng lâu dài. Bên cạnh đó do tuân thủ điều kiện “P2” theo chuẩn FIPS 186-4, nên thời gian tạo cặp khóa của thuật toán backdoor BD3 lâu hơn một chút so với thời gian tạo khóa của thuật toán backdoor BD1, BD2. Do vậy môi trường ứng dụng tốt nhất đối với backdoor BD3 là trong module tạo khóa của thiết bị HSM. 3.5. Đánh giá các thuật toán backdoor đề xuất Với mỗi backdoor đề xuất BD1, BD2, BD3, đều đã có những đánh giá cụ thể, chi tiết trong phần trình bày của từng thuật toán (tại các mục 2.2, 2.3, 3.2), để làm rõ hơn các ưu, nhược điểm, các backdoor đề xuất cần được phân tích, so sánh giữa các backdoor đề xuất với nhau và phân tích, so sánh giữa các backdoor đề xuất với các backdoor tương đương của tác giả khác. 3.5.1. So sánh 03 thuật toán backdoor đề xuất với nhau 3.5.1.1. Các điểm giống nhau - Tham số đầu vào/ra tuân thủ chuẩn FIPS 186-4. - Thông tin backdoor: một nửa các bit của số nguyên tố p. (BD1, BD3) - Vị trí giấu thông tin backdoor: trong 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 (mục 1.3). - Không sử dụng bộ nhớ (NM, VM). 3.5.1.2. Các điểm khác nhau Các điểm khác nhau giữa 03 thuật toán đề xuất được tóm tắt trong bảng 3.3 103 Bảng 3.3. Các điểm khác nhau giữa 03 thuật toán backdoor đề xuất TT Nội dung Thuật toán BD1 Thuật toán BD2 Thuật toán BD3 1 Hệ mật của người thiết kế Hệ mật khóa công khai: ECIES 128 Hệ mật đối xứng, vd AES 128. Hệ mật đối xứng hoặc hàm băm có khóa. AES 128, HMAC_SHA 256 2 Thông tin backdoor, I(𝑘𝑝𝑟𝑖𝑣𝐺1 ) 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 của p, k = nlen/2, k > s ≥ k – 100 p⌋k/2, một nửa các bit thấp của số nguyên tố p 3 Vị trí nhúng thông tin backdoor Toàn bộ các bit của số modulus n Các bit cao của số modulus n Một nửa các bit thấp của số nguyên tố p 4 Tuân thủ FIPS 186-4 Điều kiện “P1” Điều kiện “P1” Điều kiện “P2” 5 Lực lượng khóa 𝑅𝐺1 “Tốt” 2− 1 2. 𝑛𝑙𝑒𝑛 2 +2 “Tốt”, 2− 1 2. 𝑛𝑙𝑒𝑛 2 “Tốt”, 2− 1 2. 𝑛𝑙𝑒𝑛 2 6 Tính tương quan “Trung bình” “Trung bình” “Tốt” 3.5.1.3. Đánh giá chung về 03 thuật toán đề xuất Cả ba thuật toán backdoor đề xuất đều có các tiêu chí phần lớn được đánh giá tốt, khả thi khi triển khai ứng dụng. Thuật toán backdoor BD1 sử dụng kỹ thuật nhúng thông tin backdoor vào toàn bộ các bit của số modulus n, nên các tham số có tính tương quan tốt nhất và nâng cao được độ an toàn. Thuật toán backdoor BD2 sử dụng lượng thông tin backdoor ít hơn một nửa các bit của số nguyên tố p, nên có lực lượng khóa lớn nhất (so với hai thuật toán còn lại), có 104 thể áp dụng vào những trường hợp cần lực lượng khóa lớn (có nhiều người dùng). Do tuân thủ điều kiện “P2” nên thuật toán backdoor BD3 có thể áp dụng trong những trường hợp có ràng buộc về kích thước số modulus nhỏ (1024 bit), nhưng lại có lực lượng nhỏ (so với hai thuật toán còn lại) và kỹ thuật nhúng thông tin backdoor vào các bit thấp của số nguyên tố p cũng nâng cao độ an toàn cho backdoor. Cả ba thuật toán có phần khôi phục khóa đều sử dụng phương pháp phân tích nhân tử của Coppersmith nên phần khôi phục khóa tương đối đơn giản và thực hiện nhanh. 3.5.2. So sánh với các thuật toán backdoor của các tác giả khác Ba thuật toán backdoor đề xuất so sánh với các thuật toán backdoor đã công bố của các tác giả khác (mục 1.5.2.) có một số điểm sau: 3.5.2.1. Các điểm giống - Vị trí giấu thông tin backdoor: vào trong số modulus n. - Thông tin backdoor: một nửa các bit của số nguyên tố p. (BD1 và BD3). - Khôi phục khóa: dùng phương pháp phân tích nhân tử của Coppersmith. - Hệ mật của người thiết kế: hệ mật khóa công khai RSA, ECIES, hoặc hệ mật đối xứng (AES). 3.5.2.2. Các điểm khác - Kỹ thuật nhúng thông tin backdoor vào trong toàn bộ các bit của số modulus n (BD1). - Kỹ thuật trích thông tin backdoor nhỏ hơn một nửa các bit của số nguyên tố p (BD2). - Kỹ thuật tạo thông tin backdoor từ số mũ công khai e và nhúng thông tin backdoor vào các bit thấp của số nguyên tố p (BD3). - Tham số đầu vào/ra: tuân thủ các điều kiện của chuẩn FIPS 186-4. 105 3.5.2.3. Đánh giá chung Cả ba thuật toán backdoor đề xuất đều kế thừa các ưu điểm và hạn chế các nhược điểm trong các công trình nghiên cứu về backdoor đã công bố của các tác giả đi trước. Ưu điểm lớn nhất và độc đáo của cả ba thuật toán backdoor đề xuất là các tham số tuân thủ các điều kiện của chuẩn FIPS 186-4. Bên cạnh đó, mỗi backdoor BD1, BD2, BD3 đều áp dụng kỹ thuật riêng khác biệt so với các thuật toán backdoor của các tác giả khác và mang lại hiệu quả rõ ràng. 3.6. Kết luận chương 3 Chương 3 giải quyết vấn đề đã đặt ra của Luận án - đề xuất được 01 thuật toán backdoor đối xứng BD3 tuân thủ điều kiện “P2” theo chuẩn FIPS 186-4 với tất cả các tiêu chí được đánh giá tốt. Điểm cốt lõi trong phần sinh khóa của thuật toán backdoor BD3 là dựa trên thuật toán tìm số nguyên tố mạnh của John Gordon để xây dựng các số nguyên tố chính (p, q), dựa trên thuật toán sinh số nguyên tố chứng minh được của Maurer để tạo các số nguyên tố phụ. Điểm độc đáo của thuật toán BD3 là kỹ thuật trích chọn thông tin backdoor từ số mũ công khai e và kỹ thuật nhúng thông tin backdoor vào trong các bit thấp của số nguyên tố p làm tăng thêm tính bảo mật của backdoor. Thuật toán BD3 được thử nghiệm trên thiết bị tự chế tạo T-Token đối với 03 tiêu chí có kết quả thử nghiệm phù hợp với các đánh giá. Backdoor BD3 được đề xuất ứng dụng tốt nhất trong phần (module) tạo khóa của thiết bị HSM. 106 KẾT LUẬN Mật mã được ứng dụng ngày càng rộng rãi để đảm bảo an toàn cho các giao dịch điện tử thì vấn đề đảm bảo an ninh cho cộng đồng khi sử dụng mật mã (PKI) cũng càng trở nên cấp thiết, nhất là trong giai đoạn hiện nay. Ứng dụng backdoor để đảm bảo an ninh cho cộng đồng khi sử dụng mật mã là một giải pháp hiệu quả với chi phí thấp, thời gian thực hiện nhanh, khó bị phát hiện, dễ dàng cài đặt. Việc nghiên cứu các thuật toán sinh khóa chứa backdoor trên hệ mật RSA với các tham số vào/ra thỏa mãn chuẩn FIPS 186-4 có tính thực tiễn cao có thể ứng dụng ngay nhằm đảm bảo an ninh cho hạ tầng PKI cụ thể. A. Kết quả đạt được của Luận án Trên cơ sở các nội dung nghiên cứu Luận án đạt được những kết quả sau: 1. Khảo sát, phân tích, đánh giá các công cụ hình hình thức và các thuật toán sinh khóa RSA chứa backdoor. Tập trung nghiên cứu công cụ hình thức của Arboit [4] và phương pháp phân tích nhân tử của Coppersmith [20] để phân tích, đánh giá backdoor và khôi phục khóa riêng từ khóa công khai tương ứng. 2. Đề xuất được 03 thuật toán sinh khóa chứa backdoor trên hệ mật RSA có các tham số đầu vào và đầu ra tuân thủ chuẩn FIPS 186-4 với các tiêu chí được đánh giá tốt. 03 thuật toán sinh khóa chứa backdoor đề xuất được thử nghiệm trên thiết bị phần cứng tự chế tạo T-Token có các kết quả phù hợp với các đánh giá về mặt lý thuyết. B. Những đóng góp mới của Luận án Với kết quả đạt được như trên, Luận án đã có những đóng góp mới sau: 1. Đề xuất thuật toán backdoor bất đối xứng BD1 tuân thủ điều kiện “P1” theo chuẩn FIPS 186-4 với 06 tiêu chí được đánh giá tốt, 01 tiêu chí (tính tương quan) được đánh giá ở mức trung bình và kỹ thuật nhúng thông tin backdoor 107 vào toàn bộ số modulus n làm tăng tính phân phối và tính bảo mật cho backdoor. 2. Đề xuất thuật toán backdoor đối xứng BD2 tuân thủ điều kiện “P1” theo chuẩn FIPS 186-4 với 06 tiêu chí được đánh giá tốt, 01 tiêu chí (tính tương quan) được đánh giá ở mức trung bình và phương pháp rút gọn thông tin backdoor nhỏ hơn một nửa số các bit của số nguyên tố p , làm tăng lực lượng khóa của backdoor. 3. Đề xuất thuật toán backdoor đối xứng BD3 tuân thủ điều kiện “P2” theo chuẩn FIPS 186-4 với 07 tiêu chí được đánh giá tốt và kỹ thuật trích thông tin backdoor từ số mũ công khai e rồi nhúng vào trong các bit thấp của số nguyên tố p, làm tăng tính bảo mật của backdoor. C. Hướng nghiên cứu tiếp theo 1. Nghiên cứu các mô hình, công cụ hình thức để phân tích và đánh giá backdoor an toàn, sâu sắc và hiệu quả hơn. 2. Nghiên cứu các phương pháp rút gọn thông tin backdoor ít hơn một nửa các bit của số nguyên tố p. Nghiên cứu các phương pháp sử dụng thông tin backdoor khác ngoài hai số nguyên tố p, q. 3. Nghiên cứu các kỹ thuật nhúng thông thông tin backdoor vào số modulus n hoặc e sao cho các tham số của thuật toán sinh khóa chứa backdoor vẫn thỏa mãn chuẩn FIPS 186-4 và các tiêu chí của thuật toán sinh khóa chứa backdoor vẫn được đánh giá là tốt. 4. Nghiên cứu thuật toán sinh khóa chứa backdoor an toàn với các hệ mật mã của người dùng khác như: Elliptic, ... 5. Trên cơ sở các kiến thức, kỹ thuật tạo backdoor an toàn, nghiên cứu các phương pháp, kỹ thuật phòng chống backdoor trong các sản phẩm mật mã hộp đen. 108 CÁC CÔNG TRÌNH KHOA HỌC ĐÃ CÔNG BỐ [1]. 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. [2]. Lê Quang Huy, 2017, “Về một backdoor trong sinh khóa RSA tuân thủ điều kiện “chặt” theo chuẩn FIPS 186-4”, Tạp chí Nghiên cứu Khoa học và Công nghệ quân sự, Viện KH&CNQS, số 52, 12 - 2017, tr 131 - 137. [3]. Lê Quang Huy, 2017, “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”, Tạp chí Nghiên cứu Khoa học và Công nghệ quân sự, Viện KH&CNQS, số Đặc san CNTT, 12 - 2017, tr 162 - 169. [4]. Bạch Nhật Hồng, Lê Quang Huy, 2018, 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, Tạp chí Khoa học Đại học Sư phạm Hà Nội, Trường Đại học Sư phạm Hà Nội, volume 63, số 03 - 2018, tr 99-107 . 109 TÀI LIỆU THAM KHẢO Tiếng Việt: [1]. Nguyễn Thành Trung, (2016), Báo cáo tổng hợp đề 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 Chính phủ. Tiếng Anh: [2]. Achim Pietig, (2015), Functional Specification of the OpenPGP application on ISO Smart Card Operating Systems, Available online at https://g10code.com/docs/openpgp-card-3.0.pdf. [3]. Anderson. R, (1993), A practical rsa trapdoor, Electronics Letters, Volume: 29, Issue: 11, 27 May 1993, Available online at https://www.researchgate.net/publication/3371179_Practical_RSA_trapdoor. [4]. Arboit. G, (2008), Two mathematical security aspects of the RSA cryptosystem, PhD thesis, McGill University, Montreal, Canada, Available online at [5]. Berlekamp E. R, (1970), “Factoring polynomials over large finite fields”, Mathematics of Computation, Vol.24, No.111, pp 713–735, Available online at: 1970-0276200-X/. [6]. Bernhard Esslinger, (2013), The Dark Side of Cryptography: Kleptography in Black-Box Implementations, InfoSecurity Magazine, Available online at: https://www.infosecurity-magazine.com/magazine- features/the-dark-side-of-cryptography-kleptography-in/ [7]. Black Market Reloaded, (2016), The 3 Biggest Darknet Markets, Available online at: https://blackmarketreloaded.org/. [8]. Bleichenbacher D, (1997), On the Security of the KMOV public key cryptosystem, Advances in Cryptology – Crypto ’97, Lecture Notes in Computer Science Vol. 1294, Springer-Verlag, pp. 235–248, Available online at: https://link.springer.com/chapter/10.1007/BFb0052239. 110 [9]. Boneh. D, Durfee. G, Frankel. Y, (1998), An attack on rsa given a small fraction of the private key bits, Proceedings AsiaCrypt '98, Lecture Notes in Computer Science, Vol. 1514, pp: 25--34, Available online at: https://link.springer.com/content/pdf/10.1007%2F3-540-49649-1_3.pdf. [10]. Boneh D, Durfee G, Howgrave-Graham N, (1999), Factoring N = prq for large r, Advances in Cryptology – Crypto ’99, Lecture Notes in Computer Science Vol. 1666, Springer-Verlag, pp. 326–337, Available online at: [11]. Boneh D, Durfee G, (2000), Cryptanalysis of RSA with private key d less than N0.292, IEEE Trans. on Information Theory, Vol. 46(4), pp. 1339– 1349, Available online at: https://link.springer.com/content/pdf/10.1007/3- 540-48910-X_1.pdf. [12]. Bruce Schneier, (1996), Applied Cryptography: Second Edition, Wiley Computer Publishing, John Wiley & Sons, Inc. [13]. Bruce Schneier, (2013), Defending Against Crypto Backdoors, Schneier on Security Blog, Available online at: https://www.schneier.com/blog/archives/2013/10/defending_again_1.html. [14]. Bruce Schneier, (2015), Surreptitiously Weakening Cryptographic Systems, Available online at: https://eprint.iacr.org/2015/097.pdf [15]. Cantor David G, Zassenhaus Hans, (1981), “A new algorithm for factoring polynomials over finite fields”, Mathematics of Computation, Vol.36, No.154, pp 587–592, Available online at: birkmath/20042005spr/483/docs/cantorbaba.pdf. [16]. Carlisle Adams, Steve Lloyd, (2002), Understanding PKI: Concepts, Standards, and Deployment Considerations, Second Edition, Addison-Wesley Professional Longman Publishing Co, Inc. Boston, MA, USA [17]. Chuck Easttom, (2017), An Overview of Cryptographic Backdoors, Journal of Information System Security, Vol 13, Issue 3, p175-183, Available online at: https://dokupdf.com/download/cryptographic-backdoors- _5a01d810d64ab2b9bd783f49_pdf. 111 [18]. Claude Crepeau and Alain Slakmon, (2003), Simple Backdoors for RSA Key Generation, CT-RSA, Lecture Notes in Computer Science, Springer- Verlag Berlin Heidelberg, Available online at https://pdfs.semanticscholar.org/ 0428/db02e8c46cd4b1b8a43359503bd9509034f6.pdf. [19]. Constantinos Patsakis, (2012), Number Theoretic SETUPs for RSA Like Factoring Based Algorithms, Journal of Information Hiding and Multimedia Signal Processing, Volume 3, Number 2, 2012, Available online at: https://pdfs.semanticscholar.org/0d8e/83be56f812efc2cf00464279f24017a ebc6a.pdf. [20]. Coppersmith, (1995), Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities, Journal of Cryptology: Volume 10 Issue 4, Pages 233-260, Available online at https://www.di.ens.fr/~fouque/ens- rennes/coppersmith.pdf. [21]. Dan Shumow, Niels Ferguson, (2007), On the possibility of a back door in the NIST SP800-90 DUAL EC PRNG, Available online at: https://rump2007.cr.yp.to/15-shumow.pdf. [22]. David Wong, (2015), Survey: Lattice Reduction Attacks on RSA, Available online at: https://www.davidwong.fr/papers/david_wong_rsa_lll_boneh_durfee__2015. pdf [23]. Desmedt. Y, (1988), Abuses in cryptography and how to fight them, Advances in Cryptology, CRYPTO 88 pp: 375-389, Available online at: https://static.aminer.org/pdf/PDF/000/119/960/abuses_in_cryptography_and_ how_to_fight_them.pdf. [24]. Domingo Gomez, Jaime Gutierrez, Alvar Ibeas, (2014), Integer Factoring with Extra Information, Available online at: https://pdfs.semanticscholar.org/4aac/e6c842ef7be886f1eb3caabfe3159711dc d3.pdf [25]. Dorothy E. Denning and William E. Baugh, Jr, (1999), Hiding Crimes in Cyberspace, Information, Communication and Society, Vol. 2, No 3, Available online at: https://cryptome.org/hiding-db.htm. 112 [26]. Durfee G, Nguyen P, (2000), Cryptanalysis of the RSA Schemes with Short Secret Exponent from Asiacrypt ’99, Advances in Cryptology – Asiacrypt 2000, Lecture Notes in Computer Science Vol. 1976, Springer, pp. 14–29, Available online at: [27]. FIPS, (2013), FIPS PUB 186-4; Digital Signature Standard, Available online at: 4.pdf. [28]. Hoeij Mark Van, (2002), “Factoring polynomials and the knapsack problem”, Journal of Number Theory, Vol.95, No.2, pp 167–189, Available online at: https://www.math.fsu.edu/~hoeij/knapsack/paper/knapsack.pdf. [29]. Hung-Min SUN, Mu-En WU, Cheng-Ta YANG, (2009), Simple Backdoors on RSA Modulus by Using RSA Vulnerability, Available online at: https://www.researchgate.net/publication/220238838_Simple_backdoors_on_ RSA_modulus_by_using_RSA_vulnerability. [30]. Jean-Loup Richet, (2015), Extortion on the Internet : the Rise of Crypto-Ransomware, Available online at: https://pdfs.semanticscholar.org /a21a/af1ef6b142556212f40279b745cf70db55ca.pdf. [31]. John Gordon, (1984), Strong Primes are Easy to Find, EUROCRYPT 1984: Advances in Cryptology pp 216-223, Available online at: https://link.springer.com/chapter/10.1007/3-540-39757-4_19. [32]. Kaliski Jr, B.S, (1994), Anderson’s RSA trapdoor can be broken, Available online at: download? doi=10.1.1.45.1789&rep=rep1&type=pdf. [33]. Kleinjung Thorsten, (2006), “On polynomial selection for the general number field sieve”, Mathematics of Computation. Vol 75, No 256, pp 2037–2047, Available online at: 256/S0025-5718-06-01870-9/home.html. [34]. Knuth, (1997), The Art of Computer Programming, Third Edition, Addison-Wesley. 113 [35]. Lenstra A. K, Lenstra H. W, and Lovasz L, (1982), Factoring polynomials with rational coefficients, Journal Mathematische Annalen, Volume 261, Pages 515-534, Available online at https://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1982f/art.pdf. [36]. Lenstra H W, (1987), “Factoring integers with elliptic curves”, Annals of Mathematics. Vol 126, No 3 pp 649–673, Available online at: https://wstein.org/edu/124/lenstra/lenstra.pdf. [37]. May. Alexander, (2007), Using LLL-Reduction for Solving RSA and Factorization Problems, The LLL Algorithm: Survey and Applications, pp 315-348, Available online at https://pdfs.semanticscholar.org/ 7c79/49a3c36b2cf625fd39335ff5aaedf74e73d4.pdf. [38]. May. Alexander, (2003), New RSA Vulnerabilities Using lattice Reduction Methods, PhD thesis (Dissertation), frankfurt.de/~dmst/teaching/WS2014/Vorlesung/Alex.May.pdf. [39]. Marcin Gogolewski, Marek Klonowski, Przemysław Kubiak, Mirosław Kutyłowski, Anna Lauks, Filip Zagórski, (2006), Kleptographic Attacks on E-Voting Schemes, Proceedings Conference: Emerging Trends in Information and Communication Security, pp 494-508, Available online at: https://kutylowski.im.pwr.wroc.pl/articles/wele-folie.pdf. [40]. Margaret Rouse, (2017), Backdoor, SearchSecurity, Available online at: https://searchsecurity.techtarget.com/definition/back-door. [41]. Maurer U, (1994), Fast Generation of Prime Numbers and Secure Public Key Cryptographic Parameters, Journal of Cryptology, Volume 8, Issue 3, pp 123–155 Available online at https://pdfs.semanticscholar.org/ e156/f237087fed1710c6f959f1e762432f3f38fa.pdf. [42]. Menezes A, Oorschot P van, Vanstone S, (2001), Handbook of Applied Cryptography, CRC Press. [43]. Miller, Gary L, (1976), “Riemann's Hypothesis and Tests for Primality”, Journal of Computer and System Sciences, 13 (3): 300–317, Available online at: https://www.cs.cmu.edu/~glmiller/Publications/ Papers/Mi76.pdf. 114 [44]. Nicholas Howgrave-Graham, (1997), Finding Small Roots of Univariate Modular Equations Revisited, Cryptography and Coding 1997: pp 131-142, Available online at https://link.springer.com/chapter/ 10.1007/BFb0024458. [45]. Nicholas Howgrave-Graham, (2001), Approximate integer common divisors, Cryptography and Lattices, pp 51-66, Available online at , 1&type=pdf. [46]. Nguyen. P, D. Stehl´e, (2005), Floating-Point LLL Revisited, Advances in Cryptology – Eurocrypt, Lecture Notes in Computer Science Vol. 3494, pp. 215–233, Available online at: https://iacr.org/archive/ eurocrypt2005/34940217/34940217.pdf. [47]. Rabin, Michael O, (1980), “Probabilistic algorithm for testing primality”, Journal of Number Theory, 12 (1): 128–138, Available online at: Dihub#. [48]. RSA Laboratory, (2012), PKCS #1: RSA Cryptography Standard v2.2, EMC, Available online at: labs/standards-initiatives/pkcs-rsa-cryptography-standard.htm. [49]. RSA Laboratory, (2004), PKCS #11: Cryptographic Token Interface Standard v2.2, EMC, Available online at cryptographic-token-interface-standard.htm. [50]. Russell Brandom, (2013), NSA paid $10 million to put its backdoor in RSA encryption, according to Reuters report, The Verge magazine, Available online at: https://www.theverge.com/2013/12/20/5231006/nsa-paid- 10-million-for-a-back-door-into-rsa-encryption-according-to. [51]. Ruxandra F Olimid, (2016), SETUP in Secret Sharing Schemes using Random Values, Available online at: https://eprint.iacr.org/2014/184.pdf 115 [52]. Ryan Martin, (2013), NSA May Have Backdoors Built Into Intel And AMD Processors, eTeknix Magazine, Available online at: https://www.eteknix.com/nsa-may-backdoors-built-intel-amd-processors/. [53]. SageMath, (2017), SageMath Library 8.0, Available online at: https://www.sagemath.org/download-windows.htm. [54]. Simmons. Gustavus J, (1984), The prisoner's problem and the subliminal channel, Advances in Cryptology 84, pp 51-67, Available online at: ography/Spring2009/ThePrisonerProblem.pdf. [55]. Stehlé. D, (2007), Floating-Point LLL: Theoretical and Practical Aspects, LLL+25 Conference, The LLL Algorithm, pp 179-213, Available online at: [56]. Stefan Wüller, Marián Kühnel, Ulrike Meyer, (2016), Information Hiding in the RSA Modulus, IH&MMSec '16 Proceedings of the 4th ACM Workshop on Information Hiding and Multimedia Security, Pages 159-167, Available online at: https://dl.acm.org/citation.cfm?id=2909827.2930804. [57]. Shoup V, (1998), OAEP Reconsidered, Advances in Cryptology – Crypto 2001, Lecture Notes in Computer Science Vol. 2139, Springer-Verlag, pp 239-259, Available online at: [58]. Ting-Yu Lin, Hung-Min Sun and Mu-En Wu, (2006), A Comprehensive Study of Backdoors for RSA Key Generation, Available online at: https://pdfs.semanticscholar.org/ 81ba/54b69761972e256fa67ad833d7f15 b2a1b9d.pdf. [59]. Young A and Yung M, (1996), The Dark Side of “Black-Box” Cryptography or: Should We Trust Capstone?, CRYPTO 1996: Advances in Cryptology, pp 89-103, Available online at viewdoc/download?doi=10.1.1.54.616&rep=rep1&type=pdf. [60]. Young A and Yung M, (1997), Kleptography: Using Cryptography Against Cryptography, EUROCRYPT 1997: Advances in Cryptology, pp 62- 74, Available online at: https://link.springer.com/content/pdf/10.1007/3-540- 69053-0_6.pdf. 116 [61]. Young A and Yung M, (1997), The Prevalence of Kleptographic Attacks on Discrete-Log Based Cryptosystems, CRYPTO 1997: Advances in Cryptology, pp 264-276, Available online at: https://link.springer.com/ content/pdf/10.1007/BFb0052241.pdf. [62]. Young A and Yung M, (2004), Malicious Cryptography, Exposing Cryptovirology, John Wiley & Sons, Available online at: [63]. Young A and Yung M, (2005), Malicious Cryptography Kleptographic Aspects, CT-RSA 2005: Topics in Cryptology, pp 7-18, Available online at: viewdoc/download? doi=10.1.1.120.6265&rep=rep1&type=pdf. [64]. Young A and Yung M, (2005), A Space Efficient Backdoor in RSA and Its Applications, SAC 2005: Selected Areas in Cryptography, pp 128-143, Available online at: https://link.springer.com/chapter/10.1007/11693383_9. [65]. Wiener. M, (1990), Cryptanalysis of short RSA secret exponents, EUROCRYPT 1989: Advances in Cryptology, pp 372-372, Available online at: [66]. Zbigniew Golebiewski, Miroslaw Kutylowski, and Filip Zagórski, (2006), Stealing Secrets with SSL/TLS and SSH - Kleptographic Attacks, CANS 2006: Cryptology and Network Security, pp 191-202, Available online at: https://link.springer.com/chapter/10.1007/11935070_13.