Tóm tắt 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

mật RSA, các tham số đầu vào và đầu ra của thuật toán sinh khóa (hệ mật RSA) chưa tuân thủ một chuẩn xác định nào. - Chưa có thuật toán sinh khóa chứa backdoor nào được đánh giá tốt trên tất cả các tiêu chí. Một số thuật toán sinh khóa chứa backdoor có lực lượng khóa tốt nhưng, không thực hiện được sinh lại khóa một phần. - Một số thuật toán sinh khóa chứa backdoor được đánh giá thất bại khi sử dụng bộ nhớ tĩnh (NM) để lưu thông tin giữa các lần sinh khóa và sử dụng kỹ thuật nhúng thông tin backdoor phức tạp dẫn đến độ phức tạp của thuật toán backdoor từ bậc 2 trở lên. 6 1.6. Những vấn đề luâṇ án cần tâp̣ trung nghiên cứu giải quyết Trên cơ sở phân tích kết quả đạt được và những tồn tại trong các công trình nghiên cứu của các tác giả đi trước về sinh khóa RSA chứa backdoor, luâṇ án cần tâp̣ trung nghiên cứu, tìm kiếm các thuật toán sinh khóa RSA chứa backdoor hiệu quả, kế thừa các ưu điểm, hạn chế, khắc phục các tồn tại trong các thuật toán sinh khóa chứa backdoor đã công bố để có thể ứng duṇg vào các sản phẩm mật mã dạng hộp đen nhằm đảm bảo an ninh cho việc sử dụng mật mã khóa công khai (PKI) thỏa mãn các ràng buộc sau: - Các tham số khóa thỏa mãn chuẩn FIPS 186-4 [26]. - Thông tin backdoor: một nửa các bit của số nguyên tố p hoặc ít hơn. - Vị trí nhúng thông tin backdoor: vào một nửa các bit hoặc toàn bộ các bit của số modulus n mà vẫn đạt được tính tương quan cao. - Hệ mật người thiết kế là hệ mật đối xứng hoặc hệ mật công khai EC với kích thước khối mã nhỏ, thuận tiện cho rút gọn thông tin backdoor. - Các thuộc tính của backdoor (theo mô hình và tiêu chí của Arboit) được đánh giá đạt mức trung bình trở lên - Không sử dụng bộ nhớ (VN, NM) để lưu thông tin giữa các lần sinh khóa và độ phức tạp của thuật toán backdoor nhỏ hơn bậc 2. 1.7. Kết luận chương 1 Chương 1 trình bày kiến thức cơ sở cần thiết cho việc phân tích, đánh giá backdoor và khôi phục lại khóa riêng từ khóa công khai tương ứng. Nội dung của chương 1 tập trung vào trình bày các kiến thức về mô hình hình thức hiệu quả của Arboit [4] để phân tích, đánh giá backdoor và phương pháp phân tích nhân tử của Coppersmith để khôi phục khóa riêng của người dùng từ thông tin backdoor được giấu trong khóa công khai tương ứng. Chương 1 cũng trình bày thêm một số kết quả nghiên cứu về hệ mật RSA, chuẩn FIPS 186-4 [21] và tổng quan một số kết quả nghiên cứu của các tác giả đi trước về backdoor trong sinh khóa RSA. Trên cơ sở đánh giá các kết quả nghiên cứu về backdoor và nhu cầu ứng dụng backdoor để đảm bảo an ninh cho việc sử dụng mật mã, chương 1 nêu vấn đề mà luận án sẽ giải quyết. Các kiến thức được trình bày và vấn đề đặt ra trong chương 1 là cơ sở để giải quyết trong Chương 2 và Chương 3 của Luận án. 7 CHƯƠNG 2. ĐỀ XUẤT THUẬT TOÁN BACKDOOR BD1, BD2 Chương trình bày 02 thuật toán sinh khóa RSA chứa backdoor BD1, BD2 có các tham số tuân thủ điều kiện “P1” theo chuẩn FIPS 186-4. Các thuật toán backdoor BD1, BD2 được phân tích, đánh giá chi tiết, cụ thể theo mô hình hình thức của Arboit, được thử nghiệm trên thiết bị T-Token 2.1. Thuật toán backdoor BD1 2.1.1. Giới thiệu thuật toán backdoor BD1 2.1.1.1. Thiết kế thuật toán Thuật toán backdoor BD1, là thuật toán sinh khóa RSA chứa backdoor bất đối xứng dựa trên ý tưởng của thuật toán PAP với các tham số vào/ra thỏa mãn các điều kiện “P1” theo chuẩn FIPS 186-4. 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 tham số đủ an toàn để sử dụng trong các trường hợp chung. Ý tưởng thiết kế: - Sử dụng ý tưởng của thuật toán PAP: Thông tin backdoor được mã mật và nhúng vào các bit của số modulus n (PAP nhúng vào các bit cao). - Lượng thông tin backdoor chỉ một nửa các bit của số nguyên tố p (cải tiến hơn: PAP sử dụng toàn bộ số nguyên tố p). - Kỹ thuật tạo và nhúng thông tin backdoor vào trong toàn bộ số modulus n dựa trên cơ sở của Bổ đề 2.1. - Các tham số đầu ra tuân thủ điều kiện “P1” của chuẩn FIPS 186-4. Điểm độc đáo của thuật toán BD1 là kỹ thuật tạo và nhúng thông tin backdoor vào toàn bộ số modulus n. Việc trải thông tin backdoor vào toàn bộ các bit của n làm cho đặc trưng thống kê của tham số n tốt hơn, tốt nhất trong các trường hợp nhúng thông tin backdoor và kẻ tấn công khó tìm được thông tin backdoor hơn so với trường hợp nhúng thông tin backdoor vào một phần của n, điều này cũng nâng cao tính an toàn cho backdoor. Thuật toán BD1 có các bước thực hiện như sau: - Phần sinh khóa: 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 hệ mật EC của người thiết kế và được trải đều (nhúng) trong các bit của số modulus n. - Phần khôi phục khóa: tách thông tin backdoor từ một nửa các bit thấp của số modulus n. Sử dụng phương pháp phân tích nhân tử của Coppersmith để tìm lại số nguyên tố p. Từ p tính q và d. 8 2.2.1.2. Phần thuật toán sinh khóa Sơ đồ khối phần thuật toán sinh khóa backdoor BD1 (hình 2.3). Mã giả phần thuật toán sinh khóa backdoor BD1 Input (e, nlen, B1) Output (p, q, n, d) 1: Input (e, nlen, B1) ; 2: if(e 2256 or nlen <2048)then return failure; // generate p 3: p = RandomPrime() ; //log2 p = k 4: if (𝑝 < √2. 2𝑛𝑙𝑒𝑛/2−1) then goto step 3 ; 5: if (gcd(p - 1, e) ≠ 1) then goto step 3 ; 6: if (not (PrimalityTest (p))) then goto step 3 ; // generate q 7: u = 2k mod p ; //log2 q =nlen/2 8: v1 = EncECIES(p⌉k/2,Kpub);//Kpub backdoor owner’s key 9: for i = 0 to B1 Start e, nlen, B1 2 16 < e < 2 256 nlen 2048 Trả về mã lỗi Stop No Tạo số nguyên tố p Chuẩn bị thông tin backdoor GCD (q - 1, e) = 1 q là số có thể nguyên tố (1,41 . 2 nlen/2-1 q < 2nlen/2) |p – q| > 2 nlen/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 2.3. Sơ đồ khối phần thuật toán sinh khóa của backdoor BD1 GCD (p - 1, e) = 1 p là số có thể nguyên tố (1,41.2 nlen/2-1 p < 2 nlen/2 ) Yes No Tạo số nguyên tố q có chèn thông tin backdoor Tính giá trị q Chèn thông tin backdoor vào modulus n 9 10: r = RandomOddInteger() ; //log2 r = k/2 11: v = v1.2k/2 + r ; //v = v1 : r 12: v0 = v mod p ; 13: s0 = (v0 + u2).u-1 mod p ; 14: if (s0 ≤ 2k-1) then 15: s = 2k – s0 ; 16: n = s.2k + v ; // n = s : v 17: q = n / p ; //lemma 2.1 18: if (𝑞 < √2. 2𝑛𝑙𝑒𝑛/2−1) then next i ; 19: if ( |p – q| ≤ 2 nlen/2 – 100 ) then next i ; 20: if (gcd(q - 1, e) ≠ 1) then next i ; 21: if (PrimalityTest (q))) then break ; 22: endfor ; 23: if not (PrimalityTest (q))) then goto step 3; 24: d = e–1 mod (LCM(p - 1, q - 1)) ; 25: if ( d < 2 nlen/ 2 ) then goto step 3 ; 26: return (p, q, n, d) ; Thuật toán 2.2. Phần thuật toán sinh khóa của backdoor BD1 2.2.1.3. Phần thuật toán khôi phục khóa Mã giả phần thuật toán khôi phục khóa backdoor BD1 Input (n, e) Output (p, q, d) 1: Input (n, e) ; 2: v = n mod 2k ; 3: v1 = v div 2k/2 ; 4: p1 = DecECIES(v1, Kpriv);//Kpriv backdoor owner’s key 5: p = S(n, 2k/2, p1) ; //Coppersmith method(1.3.3) 6: q = n / p ; 7: d ≡ e−1 mod φ(n) ; 8: return (p, q, d) ; Thuật toán 2.3. Phần thuật toán khôi phục khóa của backdoor BD1 2.1.2. Đánh giá thuật toán backdoor BD1 Tính bảo mật: Người thiết kế sử dụng lược độ mã mật ECIES củ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 hệ mật RSA của người dùng G1 ≥ 2048. Do vậy tính bảo mật được đánh giá ở mức “tốt”. Tính hoàn chỉnh: 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. Vậy tính hoàn chỉnh đạt mức “tốt”. 10 Lực lượng khóa: 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}, #{e} có thể bỏ qua, ta có: 𝑅𝐺1 = 𝑁𝐺1,𝑞 𝑁𝐺0,𝑞 ≈ 23𝑛𝑙𝑒𝑛/4+1− 𝑙𝑜𝑔2𝑛𝑙𝑒𝑛 2𝑛𝑙𝑒𝑛−1−𝑙𝑜𝑔2 𝑛𝑙𝑒𝑛 = 22−𝑛𝑙𝑒𝑛/4 = 2− 1 2. 𝑛𝑙𝑒𝑛 2 +2 Vì hằng số c = -1/2 trong 𝑅𝐺1 lực lượng của G1 đạt mức “tốt”. Tính phân phối: Thông tin backdoor được mã mật hóa và nhúng vào vị trí cố định trong n. Tuy nhiên vì thông tin backdoor được mã mật hóa bằng 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. Do vậy tính phân phối của G1 được đánh giá ở mức “tốt”. Tính tương quan: Theo cách tạo, q 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. Vậy tính tương quan của G1 được đánh giá đạt mức “trung bình”. Độ phức tạp tính toán: Độ phức tạp tạo n là: tn(G1) = tp + tq + T(ECIES). Vì độ phức tạp của hệ mật ECIES không đáng kể so độ phức tạp của việc tạo p, q, nên độ phức tạp của G1 được đánh giá đạt mức “tốt”. 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á đạt mức “tốt”. 2.1.3. Tóm tắt các điểm nổi bật của thuật toán backdoor BD1 - Các tham số đầu vào, đầu ra thỏa mãn các điều kiện “P1” về tham số khóa RSA theo FIPS 186-4 (mục 1.4.3). - Kỹ thuật nhúng thông tin backdoor vào toàn bộ các bit của số modulus n dựa trên kết quả của bổ đề 2.1. - Sử dụng hệ mật người thiết kế là hệ mật công khai (EC) dẫn tới việc quản lý khóa tốt hơn và chỉ người thiết kế sử dụng được backdoor. - Tốt hơn thuật toán PAP, PHP ở tính bảo mật, lực lượng khóa, thông tin backdoor và độ phức tạp tính toán. - Phần khôi phục khóa sử dụng phương pháp phân tích nhân tử Coppersmith để khôi phục khóa riêng từ khóa công khai tương ứng nên ngắn gọn và đơn giản hơn so với phần khôi phục khóa của PAP và PHP. - Được đánh giá tốt trên 06 tiêu chí, 01 tiêu chí (tính tương quan) được đánh giá ở mức trung bình. 11 2.2. Thuật toán backdoor BD2 2.2.1. Giới thiệu thuật toán BD2 2.2.2.1. Thiết kế thuật toán Thuật toán backdoor BD2 là thuật toán sinh khóa RSA chứa backdoor đối xứng dựa trên ý tưởng của thuật toán Hidden Prime Factor với các tham số thỏa mãn các điều kiện “P1” theo chuẩn FIPS 186-4. 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ố đủ an toàn để dùng trong các trường hợp chung. Ý tưởng thiết kế: - Sử dụng ý tưởng của thuật toán Hidden Prime Factor: Thông tin backdoor được mã mật và nhúng vào các bit cao của số modulus n. - Kỹ thuật trích và nhúng thông tin backdoor vào trong số modulus n dựa trên cơ sở các bổ đề mục 2.4.1. - Các tham số đầu ra tuân thủ điều kiện “P1” của chuẩn FIPS 186-4. Điểm độc đáo của thuật toán BD2 là kỹ thuật trích thông tin backdoor có kích thước ít hơn một nửa các bit của số nguyên tố p. Lượng thông tin backdoor nhỏ hơn sẽ chiếm ít không gian trong khóa công khai dẫn tới tăng lực lượng khóa. Thuật toán BD2 có các bước thực hiện như sau: - Phần sinh khóa: thông tin backdoor là một phần của p được mã mật hóa bởi hệ mật đối xứng F và nhúng vào nửa các bit cao của số modulus n. Điểm khác biệt với các thuật toán trên là phần thông tin backdoor có thể được rút gọn với chiều dài s - k/2 bit, nên có lực lượng lớn hơn. - Phần khôi phục khóa: tách thông tin backdoor từ nửa các bit cao của số modulus n. Giải mã mật thông tin backdoor và sử dụng phương pháp của Coppersmith để tìm lại số nguyên tố p. Từ p tính q và d. 2.2.2.2. Phần thuật toán sinh khóa Sơ đồ khối phần thuật toán sinh khóa backdoor BD2: 12 Mã giả phần thuật toán sinh khóa backdoor BD2 Input (e, nlen, s) Output (p, q, n, d) 1: Input (e, nlen, s) ; 2: if(e 2256 or nlen <2048)then return failure; // generate p 3: p = RandomOddInteger()//log2 p =nlen/2 ; 4: if (𝑝 < √2. 2𝑛𝑙𝑒𝑛/2−1) then goto step 3 ; 5: if (gcd(p - 1, e) ≠ 1) then goto step 3 ; 6: if (not (PrimalityTest (p))) then goto step 3 ; Start e, nlen, s 2 16 < e < 2 256 nlen 2048 Trả về mã lỗi Stop No Tạo số nguyên tố p Chuẩn bị thông tin backdoor GCD (q - 1, e) = 1 q là số có thể nguyên tố (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 2.5. Sơ đồ khối phần thuật toán sinh khóa của backdoor BD2 GCD (p - 1, e) = 1 p là số có thể nguyên tố (1,41.2 nlen/2-1 p < 2nlen/2) Yes No Tạo số nguyên tố q có chèn thông tin backdoor Tính giá trị q Chèn thông tin backdoor vào modulus n 13 // generate q 7: q’ = RandomOddInteger() ; //log2 q =nlen/2 8: n1 = p.q’ ; //k = nlen/2 9: τ = n1⌉ k/2 ; 10: μ = F K((p⌉k/2)⌋s - k/2);//K, backdoor owner’s key 11: r = RandomOddInteger() ; //log2 r = 3k/2 - s 12: n2 = τ . 23k/2 + μ . 23k/2 –s + r ;//n2 = τ : μ : r 13: q = [n2 / p] ; 14: if (𝑞 < √2. 2𝑛𝑙𝑒𝑛/2−1) then goto step 7 ; 15: if ( |p – q| ≤ 2 nlen/2 – 100 ) then go to step 7 ; 16: if (gcd(q - 1, e) ≠ 1) then goto step 7 ; 17: if (not (PrimalityTest (q))) then goto step 7; 18: n = p.q ; // lemma 2.4 19: d = e–1 mod (LCM(p - 1, q - 1)) ; 20: if ( d < 2 nlen/ 2 ) then go to step 7 ; 21: return (p, q, n, d) ; Thuật toán 2.4. Phần thuật toán sinh khóa của backdoor BD2 2.2.2.3. Phần thuật toán khôi phục khóa Mã giả phần thuật toán khôi phục khóa Input (n, e, s) Output (p, q, d) 1: Input (n, e, s) ; 2: μ = ( n⌋3k/2 )⌉s - k/2 ; // lemma 2.4 3: p1 = ([√𝑛])⌉𝑘−𝑠 ; // lemma 2.2 4: p2 = F-1K(μ) ; 5: p3 = p1 . 2 s-k/2 + p2 ; //p3 = p1 : p2, p3 == p⌉k/2 6: p = S(n, 2k/2, p3) ; // Coppersmith method 7: q = n / p ; 8: d ≡ e−1 mod φ(n) ; 9: return (p, q, d) ; Thuật toán 2.5. Phần thuật toán khôi phục khóa của backdoor BD2 2.2.2. Đánh giá thuật toán backdoor BD2 Tính bảo mật: Người thiết kế sử dụng hệ mật đối xứng AES có độ dài tham số an toàn  AES ≥ 128 tương đương với độ dài tham số an toàn của người dùng G1 ≥ 2048. Độ an toàn hệ mật của người thiết kế được lựa chọn tương đương với độ an toàn hệ mật người dùng nên kẻ tấn công không phá vỡ được hệ mật của người dùng thì cũng không phá vỡ được hệ mật của người thiết kế. Tính bảo mật được đánh giá ở mức “tốt”. Tính hoàn chỉnh: Theo thuật toán sinh khóa và thuật toán khôi phục 14 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. Tính hoàn chỉnh được đánh giá mức “tốt”. Lực lượng khóa: 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ó: 𝑅𝐺1 = 𝑁𝐺1,𝑞 𝑁𝐺0,𝑞 ≈ 2𝑛𝑙𝑒𝑛+2−𝑠− 𝑙𝑜𝑔2𝑛𝑙𝑒𝑛 2𝑛𝑙𝑒𝑛−1−𝑙𝑜𝑔2 𝑛𝑙𝑒𝑛 = 23−𝑠 < 2− 𝑘 2+3 = 2− 1 2. 𝑛𝑙𝑒𝑛 2 +3 Hằng số c < -1/2 trong 𝑅𝐺1, lực lượng của G1 được đánh giá ở mức “tốt”. Tính phân phối: Thông tin backdoor được mã mật hóa và nhúng vào vị trí cố định trong n. Vì thông tin backdoor được mã mật hóa bằng mã khối đối xứng (có phân phối đầu ra gần với phân bố đều) nên phần nhúng thông tin backdoor cũng có phân phối gần với phân phối đều. Do vậy phân phối của n có thể gần với phân bố đều và 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 phân phối của G1 được đánh giá ở mức “tốt”. Tính tương quan: Theo cách tạo (từ bước 7 đến bước 17), q phụ thuộc vào p, tham số ngẫu nhiên r và tham số ngẫu nhiên q’. Nếu 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. Do vậy, tính tương quan của G1 đạt mức “trung bình”. Độ phức tạp tính toán: Độ phức tạp tạo n là: tn(G1) = tp + tq = tn nên độ phức tạp của G1 được đánh giá mức “tốt”, tuyến tính với G0 Bộ nhớ sử dụng: Thuật toán không sử dụng bộ nhớ NM và VM nên nó có thuộc tính bộ nhớ sử dụng được đánh giá ở mức “tốt”. 2.2.3. Tóm tắt các điểm nổi bật của thuật toán backdoor BD2 - Các tham số thuật toán thỏa mãn các điều kiện “P1” về tham số khóa RSA theo chuẩn FIPS 186-4. - Thông tin backdoor được rút gọn, cần ít hơn một nửa các bit của số nguyên tố p, dẫn tới lực lượng khóa lớn nhất trong các backdoor đề xuất. - Phần khôi phục khóa sử dụng phương pháp phân tích nhân tử của Coppersmith để khôi phục lại khóa riêng từ khóa công khai tương ứng. - Được đánh giá tốt trên 06 thuộc tính và 01 thuộc tính (tính tương quan) được đánh giá đạt mức trung bình. 15 2.3. Thử nghiệm các thuật toán backdoor BD1, BD2 2.3.1. Mục tiêu, phương pháp, môi trường, tiêu chí thử nghiệm Mục tiêu thử nghiệm nhằm thu thập các thông tin về chất lượng, từ đó đánh giá về khả năng triển khai của các backdoor đề xuất. Phương pháp thử nghiệm: thử nghiệm hộp đen, chạy thuật toán backdoor trong các tình huống (thử nghiệm động). Môi trường thử nghiệm: Thuật toán sinh khóa chứa backdoor có thể thử nghiệm trong module sinh khóa của nhà cung cấp dịch vụ hạ tầng PKI và module sinh khóa của người dùng (thiết bị Token, HSM). Các tiêu chí được thử nghiệm trên thiết bị T-Token: tính hoàn chỉnh, tính tương quan, độ phức tạp; các tiêu chí còn lại không thử nghiệm. 2.3.2. Kết quả thử nghiệm thuật toán backdoor BD1 Hình 2.8. Biểu đồ kết quả thử nghiệm độ phức tạp backdoor BD1 Bảng 2.4. Kết quả thử nghiệm độ phức tạp thuật toán backdoor BD1 Thời gian chạy G0 Thời gian chạy G1 Sinh khóa Khôi phục khóa 2.04s 2.38s 0.03s 2.3.3. Kết quả thử nghiệm thuật toán backdoor BD2 Bảng 2.5. Kết quả thử nghiệm độ phức tạp thuật toán backdoor BD2 Thời gian chạy G0 Thời gian chạy G1 Sinh khóa Khôi phục khóa 2.04 s 2.43 s 0.04 s 0 0.5 1 1.5 2 2.5 Th ờ i g ia n t h ự c h iệ n ( s) Kết quả thử nghiệm độ phức tạp backdoor BD1 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 16 Hình 2.9. Biểu đồ kết quả thử nghiệm độ phức tạp backdoor BD2 2.4. Ứng dụng backdoor BD1, BD2 Từ mục tiêu của các thuật toán backdoor BD1, BD2 là tạo ra các cặp khóa với các tham số đủ an toàn để sử dụng trong các trường hợp chung (trường hợp tạo khóa với số lượng lớn) và kết quả thử nghiệm các thuật toán backdoor BD1, BD2 cho thấy cả hai thuật toán có tốc độ thực hiện phần sinh khóa nhanh, các tham số tuân thủ điều kiện “P1” theo chuẩn FIPS 186-4, do vậy môi trường ứng dụng tốt nhất đối với backdoor BD1, BD2 là trong module tạo khóa của người dùng cuối, thiết bị PKI-Token. 2.5. Kết luận chương 2 Chương 2 giải quyết vấn đề đã đặt ra của Luận án: đề xuất được 02 thuật toán backdoor hiệu quả BD1, BD2. Cả 02 thuật toán backdoor đề xuất có các tham số đầu vào và đầu ra đều tuân thủ các điều kiện “P1” theo chuẩn FIPS 186-4 và có phần lớn các tiêu chí được đánh giá tốt. Điểm nổi bật của backdoor BD1 là kỹ thuật tạo, nhúng thông tin backdoor vào trong toàn bộ số modulus n đạt được tính phân phối tốt nhất và nâng cao tính an toàn. Điểm nổi bật của backdoor BD2 là sử dụng thông tin backdoor ít hơn một nửa các bit của p làm tăng lực lượng khóa. Cả hai thuật toán BD1, BD2 được thử nghiệm trên thiết bị T-Token với các kết quả thử nghiệm phù hợp với các đánh giá. Backdoor BD1, BD2 được đề xuất ứng dụng trong phần tạo khóa của thiết bị PKI-Token. 0 0.5 1 1.5 2 2.5 3 Th ờ i g ia n t h ự c h iệ n ( s) Kết quả thử nghiệm độ phức tạp backdoor BD2 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 17 CHƯƠNG 3. ĐỀ XUẤT THUẬT TOÁN BACKDOOR BD3 Chương này trình bày 01 thuật toán sinh khóa RSA chứa backdoor BD3 với các tham số tuân thủ điều kiện “P2” theo chuẩn FIPS 186-4, kết quả thử nghiệm thuật toán backdoor BD3 trên thiết bị tự chế tạo T-Token. 3.1. Thuật toán backdoor BD3 3.1.1. Giới thiệu thuật toán 3.1.1.1. Ý tưởng xây dựng 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. 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. - 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. 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 và bảo mật cho backdoor. Dù thuật toán BD3 được công bố công khai, việc dò tìm tham số mật (p), để 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. Thuật toán backdoor BD3 có đặc điểm sau: - Phần sinh khóa: Thông tin backdoor được chọn là một giá trị ngẫu nhiên t. Giá trị mầm u được hoán vị từ số mũ công khai, e, thông qua hàm mã mật hóa (hoặc băm) FK với khóa K của người thiết kế. Giá trị C = ut mod 2nlen/4, được nhúng vào một nửa các bit thấp của p. - Phần khôi phục khóa: Người thiết kế tính giá trị u, dò tìm thông tin backdoor t < m, để tính giá trị C (một nửa các bit thấp của p). Giá trị p được khôi phục thông qua phương pháp phân tích nhân tử của Coppersmith. 18 2.3.1.2. Phần thuật toán sinh khóa Sơ đồ khối phần thuật toán sinh khóa: Mã giả phần thuật toán sinh khóa Input: e, nlen, n1, n2, n3, n4, m Output: p, q, n, d 1: Input: e, nlen, n1, n2, n3, n4, m ; 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) ; 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 19 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)) ; 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. 2.3.1.3. Phần thuật toán khôi phục khóa Mã giả phần thuật toán khôi phục khóa: Input: n, e, m Output: p, q, d 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 = S(n, 2nlen/4, C) ; //Coppersmith method 8: t = t + 1 ; 9: until (p mod 2nlen/4 = C) and (p is prime) 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. 20 3.1.2. Đánh giá thuật toán backdoor BD3 Tính bảo mật: 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 tương đương với độ an toàn (độ dài tham số khóa) hệ mật RSA của người dùng. Tính bảo mật được đạt mức “tốt”. Tính hoàn chỉnh: 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. Vậy tính hoàn chỉnh đạt mức “tốt”. Lực lượng khóa: 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 𝑅𝐺1, nên lực lượng của G1 đạt mức “tốt”. Tính phâ