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

t toán backdoor đã được phân tích tại chương 1, thông qua việc trình bày 02 thuật toán sinh khóa RSA chứa backdoor BD1, BD2 đạt được một số tính năng sau: - Các tham số tuân thủ điều kiện “P1” theo chuẩn FIPS 186-4. - Kỹ thuật nhúng thông tin backdoor vào toàn bộ số modulus n, nâng cao đặc trưng phân phối và tính an toàn của backdoor (BD1). - Sử dụng thông tin backdoor ít hơn một nửa các bit của số nguyên tố p, làm tăng lực lượng khóa của backdoor (BD2). 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ự chế tạo T-Token. Kết quả nghiên cứu về các thuật toán backdoor BD1, BD2 được công bố tại các bài báo [1], [3], [4] trong mục “Các công trình khoa học đã công bố”. 2.1. Cơ sở cài và đánh giá backdoor 2.1.1. Phương pháp cài backdoor trong sinh khóa RSA Mục tiêu cài backdoor trong sinh khóa cho phép người thiết kế từ khóa công khai, (được tạo bởi thuật toán sinh khóa chứa backdoor) khôi phục được khóa riêng tương ứng. Yêu cầu: backdoor được phân tích, thiết kế theo mô hình hình thức của Arboit, có các tiêu chí được đánh giá theo mô hình Arboit (bảng 1.1. mục 1.2.4.4) đạt mức “trung bình” trở lên. Biện pháp thực hiện cài backdoor (phần thuật toán sinh khóa): trích một lượng thông tin backdoor và nhúng vào khóa công khai theo các bước sau: - Lựa chọn thông tin backdoor: thông tin backdoor thường là một phần 44 của khóa riêng được lựa chọn với kích thước càng nhỏ càng tốt. Với hệ mật RSA, trong phạm vi các thuật toán backdoor đề xuất, thông tin backdoor là hoặc có liên quan đến số nguyên tố p. Kích thước thông tin backdoor thường là một phần của tham số p (một nửa số các bit của số nguyên tố p). - Che giấu thông tin backdoor: người thiết kế sử dụng hệ mật đối xứng hoặc bất đối xứng để mã mật thông tin backdoor. - Nhúng thông tin backdoor đã mã mật vào khóa công khai: việc nhúng vào khóa công khai sao cho không ảnh hưởng đến tính chất thống kê của tham số đó. Với hệ mật RSA, trong phạm vi các thuật toán backdoor đề xuất, vị trí nhúng thông tin backdoor thường vào số mũ công khai e hoặc số modulus n hoặc số nguyên tố p. Biện pháp khôi phục khóa riêng (phần khôi phục khóa): sử dụng thông tin backdoor trong khóa công khai để khôi phục khóa riêng theo các bước: - Trích (tách) thông tin backdoor đã mã mật: từ khóa công khai của người dùng sử dụng thông tin về kỹ thuật nhúng thông tin backdoor. Với hệ mật RSA, thông tin backdoor đã mã thường nằm trong số mũ công khai e hoặc số modulus n hoặc số nguyên tố p, tách phần thông tin có chứa backdoor (có độ dài khoảng ¼ số các bit của số modulus n). - Giải mã mật thông tin backdoor: từ thông tin backdoor đã mã được tách, sử dụng khóa (riêng) của người thiết kế để giải mã mật thông tin backdoor. - Khôi phục tham số mật đã được nhúng: sử dụng thông tin backdoor đã được giải mã mật và áp dụng kỹ thuật khôi phục tham số mật để khôi phục. Với hệ mật RSA và trong phạm vi các thuật toán backdoor đề xuất, từ một phần thông tin backdoor (một nửa các bit của nguyên tố p), sử dụng phương pháp phân tích nhân tử của Coppersmith để khôi phục lại toàn bộ thông tin backdoor (số nguyên tố p). 45 - Tính toán toàn bộ các tham số khóa riêng: từ tham số mật đã khôi phục tính các tham số khác của khóa riêng. Với hệ mật RSA từ tham số p khôi phục lại (q, d). 2.1.2. Thuật toán sinh khóa trung thực tuân thủ điều kiện Thuật toán sinh khóa RSA trung thực thường gồm 3 phần: phần tạo số nguyên tố p, tạo số nguyên tố q, tính n và d. Trong mỗi phần của thuật toán, tuy Start e, nlen, các tham số khác 2 16 < e < 2 256 nlen 1024 Trả về mã lỗi Stop No Tạo số nguyên tố p Tạo số nguyên tố q 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 2.1. Sơ đồ khối thuật toán sinh khóa RSA trung thực tuân thủ điều kiện GCD (p - 1, e) = 1 (1,41.2 nlen/2-1 p < 2nlen/2) Yes No Tham số đầu vào Tính n, d Tạo số nguyên tố p Tạo số nguyên tố q 46 thuộc vào yêu cầu của từng tham số mà thuật toán sinh khóa tuân thủ một chuẩn xác định sẽ có những biến thể khác nhau với các bước thực hiện khác nhau. Với các yêu cầu tham số khóa tuân thủ một chuẩn FIPS 186-4, bản thân thuật toán sinh khóa tuân thủ chuẩn FIPS 186-4 cũng phải có thêm các bước thực hiện để thỏa mãn điều kiện (chuẩn). Nhìn chung thuật toán sinh khóa RSA tuân thủ điều kiện xác định được mô tả theo sơ đồ khối ở hình 2.1. Với thuật toán sinh khóa chứa backdoor, để đạt mục tiêu sao cho người thiết kế khôi phục được khóa riêng từ khóa công khai tương ứng, thì thuật toán sinh khóa chứa backdoor cần phải có thêm các bước bổ sung so với thuật toán sinh khóa trung thực. Vì vậy thuật toán sinh khóa chứa backdoor tuân thủ chuẩn FIPS 186-4 cũng có thêm các bước so với thuật toán sinh khóa tuân thủ chuẩn FIPS 186-4. Nhằm đáp ứng mục đích sử dụng của các cặp khóa trong những ngữ cảnh khác nhau, chuẩn FIPS 186-4 (mục 1.4.3.) chia điều kiện về các tham số khóa thành các nhóm cụ thể như: điều kiện “P1” và “P2” (chủ yếu dựa trên điều kiện về tính nguyên tố của các tham số p và q). Để thuận tiện cho quá trình phân tích và đánh giá các backdoor đề xuất, các thuật toán sinh khóa trung thực tuân thủ điều kiện “P1” và điều kiện “P2” được phân tích cụ thể với các đánh giá về lực lượng khóa (mục 2.13 và 3.1). 2.1.3. Thuật toán sinh khóa trung thực tuân thủ điều kiện “P1” theo chuẩn FIPS 186-4 2.1.3.1. Giới thiệu thuật toán Thuật toán sinh khóa trung thực tuân thủ điều kiện “P1” là thuật toán sinh khóa RSA trung thực (thuật toán G0) tuân thủ điều kiện “P1” tại mục 1.4.3 và được mô tả tại mục B.3.3. appendix B FIPS 186-4 [27]. Thuật toán sinh khóa RSA tuân thủ điều kiện “P1” 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 47 thực tuân thủ điều kiện “P1”, các số nguyên tố p, q được tạo dựa trên việc sinh số ngẫu nhiên và kiểm tra tính nguyên tố theo thuật toán của Miller-Rabin [43], [47]. Sau khi được tạo, các tham số đều được kiểm tra thỏa mãn điều kiện “P1” theo FIPS 186-4. Nội dung thuật toán sinh khóa trung thực tuân thủ điều kiện “P1” được mô tả dưới dạng sơ đồ khối ở hình 2.2 và mã giả thuật toán ở mục thuật toán 2.1. Sơ đồ khối thuật toán sinh khóa trung thực tuân thủ điều kiện “P1”: Start e, nlen, các tham số khác 2 16 < e < 2 256 nlen 2048 Trả về mã lỗi Stop No Tạo số nguyên tố p Tạo số nguyên tố q GCD (q - 1, e) = 1 q là số có thể nguyên tố (1,41 . 2 nlen/2-1 q < 2 nlen/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.2. Sơ đồ khối thuật toán sinh khóa RSA trung thực tuân thủ điều kiện P1 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 Tham số đầu vào Tính n, d Tạo số nguyên tố p Tạo số nguyên tố q 48 Mã giả thuật toán sinh khóa trung thực tuân thủ điều kiện “P1”: Input (nlen, e) Output (p, q, n, d) 1: Input (nlen, e) ; 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 ; // generate q 7: q = RandomOddInteger() ; //log2 q =nlen/2 8: if (𝑞 < √2. 2𝑛𝑙𝑒𝑛/2−1) then goto step 7 ; 9: if ( |p – q| ≤ 2 nlen/2 – 100 ) then go to step 7 ; 10: if (gcd(q - 1, e) ≠ 1) then goto step 7 ; 11: if (not (PrimalityTest (q))) then goto step 7 ; // compute n, d 12: n = p.q ; 13: d = e–1 mod (LCM(p - 1, q - 1)) ; 14: if ( d < 2 nlen/ 2 ) then go to step 7 ; 15: return (p, q, n, d) ; Thuật toán 2.1 Thuật toán sinh khóa RSA trung thực tuân thủ điều kiện “P1” 2.1.3.2. Lực lượng khóa của thuật toán Số lượng phần tử e, #{ e }= (2256 - 216)/2 = (2255 - 215) > 2254 (e là số lẻ). 49 Xét cách tạo p: Vì p là một số nguyên tố trong khoảng (√2. 2𝑛𝑙𝑒𝑛/2−1, 2𝑛𝑙𝑒𝑛/2 − 1 ). Nên #{ p } = Pr[số nlen/2 bit là số nguyên tố]. (2𝑛𝑙𝑒𝑛/2 − √2. 2𝑛𝑙𝑒𝑛/2−1) ≈ 1 𝑛𝑙𝑒𝑛 2 𝑙𝑛2 . 0,6. 2 𝑛𝑙𝑒𝑛 2 −1 = 2. 2 𝑛𝑙𝑒𝑛 2 𝑛𝑙𝑒𝑛 = 21+𝑛𝑙𝑒𝑛/2−𝑙𝑜𝑔2𝑛𝑙𝑒𝑛 (2.1) 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) . Vậy #{u}= Pr[số nlen/2 bit là số nguyên tố]. (p + 2nlen/2 -100 – (p - 2nlen/2 -100) = 2 𝑛𝑙𝑒𝑛/2 . 2𝑛𝑙𝑒𝑛/2−99 = 2𝑛𝑙𝑒𝑛/2−97 𝑛𝑙𝑒𝑛 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 ( (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 > 2𝑛𝑙𝑒𝑛/2 −2, nên #{q} = #{p} - #{u} = 2 1+ 𝑛𝑙𝑒𝑛 2 𝑛𝑙𝑒𝑛 − 2 𝑛𝑙𝑒𝑛 2 −97 𝑛𝑙𝑒𝑛 > 2 𝑛𝑙𝑒𝑛 2 𝑛𝑙𝑒𝑛 = 2𝑛𝑙𝑒𝑛/2−𝑙𝑜𝑔2𝑛𝑙𝑒𝑛 (2.2) Vậy lực lượng khóa của thuật toán là, #{(p, q, d)} = #{p}. #{q}.#{e} = 2254. 21+𝑛𝑙𝑒𝑛/2 𝑛𝑙𝑒𝑛 . 2𝑛𝑙𝑒𝑛/2 𝑛𝑙𝑒𝑛 = 2254. 2𝑛𝑙𝑒𝑛+1 𝑛𝑙𝑒𝑛2 (2.3) 2.2. Đề xuất thuật toán backdoor BD1 2.2.1. Bổ đề (lemma) 2.1 Ký hiệu p là một số nguyên tố, r là một số nguyên lẻ sao cho log2 p = 2.log2 r = k. Gọi u = 2k mod p; v0 = v mod p ; s0 = (v0 + u2).u-1 mod p; s = 2k – s0 ;n = s.2k + v (nối s với v, ký hiệu s : v). Thì ta có p | n. 50 Chứng minh: u = 2k mod p ⇒ 2k = m.p + u với m ∈ Z v0 = v mod p ⇒ 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 +u2 – us0 + l.p + v0 = m2p2 + (2mu – ms0 + l).p + u2 + v0 – u (v0 + u2).u-1 mod p = (m2p + 2mu – ms0 + l).p mod p Vậy p | n 2.2.2. Giới thiệu thuật toán backdoor BD1 2.2.2.1. Tổng quan 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 [59] 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. Thuật toán backdoor BD1 được công bố tại bài báo [3] trong mục “Các công trình khoa học đã công bố”. 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 để 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). Ý 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 một nửa 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. 51 - 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, (phân phối của n gần với phân phối đều nhất) và kẻ tấn công khó tìm (trích) đượ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 (các bit cao hoặc các bit thấp 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: một nửa các bit cao của số nguyên tố p. - Che giấu thông tin backdoor: thông tin backdoor được mã mật hóa bởi lược đồ mã mật bất đối xứng ECIES hệ mật EC của người thiết kế. - Nhúng thông tin backdoor vào khóa: thông tin backdoor đã mã mật được trải đều (nhúng) trong toàn bộ các bit của số modulus n. Phần khôi phục khóa: - Trích (tách) thông tin backdoor: tách thông tin backdoor đã mã mật từ một nửa các bit thấp của số modulus n. - Giải mã mật thông tin backdoor: Sử dụng khóa riêng của người thiết kế để giải mã mật thông tin backdoor. - Khôi phục tham số mật: Sử dụng phương pháp phân tích nhân tử của Coppersmith với thông tin backdoor để tìm lại số nguyên tố p. - 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. Các tham số thuật toán: 52 + I(𝑘𝑝𝑟𝑖𝑣𝐺1 ) = (p⌉k/2); G1 = G0 = nlen ≥ 2048; E = ECIES;  E ≥ 128 ; M = n; log2 p = log2 q = 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(). 2.2.2.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 2.3 và mã giả thuật toán ở mục thuật toán 2.2. Sơ đồ khối phần thuật toán sinh khóa backdoor BD1: 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 53 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 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 ; 54 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.2.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 2.4 và mã giả thuật toán ở mục thuật toán 2.3. Sơ đồ khối phần thuật toán khôi phục khóa backdoor BD1: 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) ; Start e, n, m Stop Phân tích nhân tử Coppersmith Tính q, d p, q, d Hình 2.4. Sơ đồ khối phần thuật toán khôi phục khóa của backdoor BD1 Tính thông tin backdoor từ khóa công khai, p1 55 2: v = n mod 2k ; 3: v1 = v div 2k/2 ; 4: p1 = DecECIES(v1, Kpriv) ; // Kpriv backdoor owner’s key 5: p = CopperSmith(n, 2k/2, p1) ; //Coppersmith method 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.2.3. Đánh giá thuật toán backdoor BD1 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, và có khóa công khai của người thiết kế. 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 (mục 1.4.2). Vì kẻ tấn công không có khóa riêng của người thiết kế và độ 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, giả sử hệ mật của người thiết kế an toàn, 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ế. 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: Một nửa các bit của p (thông tin backdoor) được mã mật (bước 7) và nhúng vào giá trị n (từ bước 11 đến bước 16), từ giá trị n tính q = n / p (bước 16), quá trình này dược lặp tối đa B1 lần. Nếu không tìm được q thỏa mãn điều kiện (từ bước 18 đến bước 21) thì quay lại, tạo lại p. Quá trình này được lặp đến khi nào tìm thấy q thỏa mãn điều kiện. Vì lực lượng 56 của q khá lớn #{q}= 2 𝑛𝑙𝑒𝑛 2 −𝑙𝑜𝑔2𝑛𝑙𝑒𝑛 (công thức 2.2) nên thuật toán luôn tìm được q với số lần lặp tạo p nhỏ. (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: Tuần tự thực hiện ngược với thuật toán sinh khóa: tách v là một nửa các bit thấp của n (bước 2), v1 là một nửa các bit cao của v (bước 3). Sử dụng khóa riêng của người thiết kế, giải mã mật v1 ta thu được một nửa các bit của p (bước 4). Sử dụng phương pháp phân tích nhân tử của Coppersmith (mục 1.3) và thông tin về một nửa các bit của p, sẽ tính được toàn bộ giá trị p. Từ p, dễ dàng tính được q và d. (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 thực hiện 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 (từ bước 3 đến bước 6): Vì p được tạo ngẫu nhiên và giống như trong thuật toán 2.2. nên theo (công thức 2.1), ta có #{p} = 2𝑛𝑙𝑒𝑛/2+1 𝑛𝑙𝑒𝑛 = 21+𝑛𝑙𝑒𝑛/2−𝑙𝑜𝑔2𝑛𝑙𝑒𝑛. Xét việc tạo q (từ bước 7 đến bước 22): 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 - 1 giá trị q. Vì q được tính theo n và p (bước 17), nên #{ q }= #{ n / p } . Pr[𝑞 𝑙à 𝑠ố 𝑛𝑔𝑢𝑦ê𝑛 𝑡ố] #{ q } = 2 𝑛𝑙𝑒𝑛 4 . 2−𝑙𝑜𝑔2( 𝑛𝑙𝑒𝑛 2 )−𝑙𝑜𝑔2(𝑙𝑛2) ≈ 2 𝑛𝑙𝑒𝑛 4 −𝑙𝑜𝑔2( 𝑛𝑙𝑒𝑛 2 ) 57 = 2𝑛𝑙𝑒𝑛/4 +1−𝑙𝑜𝑔2𝑛𝑙𝑒𝑛 Vậy số lượng n là: #{n} = #{p} . #{q} = 21+𝑛𝑙𝑒𝑛/2−𝑙𝑜𝑔2𝑛𝑙𝑒𝑛. 2𝑛𝑙𝑒𝑛/4−𝑙𝑜𝑔2(𝑛𝑙𝑒𝑛/2) = 23𝑛𝑙𝑒𝑛/4 +2− 2 𝑙𝑜𝑔2 𝑛𝑙𝑒𝑛 Cách tạo d, cũng giống như trong thuật toán 2.2 và #{d} = #{e}. 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+2− 𝑙𝑜𝑔2𝑛𝑙𝑒𝑛 2𝑛𝑙𝑒𝑛−𝑙𝑜𝑔2 𝑛𝑙𝑒𝑛 = 22−𝑛𝑙𝑒𝑛/4 = 2− 1 2. 𝑛𝑙𝑒𝑛 2 +2 Vì hằng số c = -1/2 trong 𝑅𝐺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 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 và tham số ngẫu nhiên r. Do vậy phân phối của n gần với phân phối đều và khoảng cách thống kê giữa thành phần n của G1 và thành phần n G0 là xấp xỉ bằng 0, DG1 ≈ 0. Căn cứ vào mục 1.2.4.4, 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 (từ bước 7 đến bước 22), q phụ thuộc vào một phần của p và 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 58 cầu ngược lại, tức là cố định q và sinh lại p thì 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). Căn cứ vào mục 1.2.4.4, 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: 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 7 đến bước 22) 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. Căn cứ vào mục 1.2.4.4, độ phức tạp của G1 được đánh giá đạt mức “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 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”. 2.2.4. So sánh thuật toán BD1 với thuật toán PAP và PHP 2.2.4.1. Các điểm giống nhau Một số điểm giống nhau giữa thuật toán BD1 với thuật toán PAP và PHP: - Vị trí giấu thông tin backdoor: trong số modulus n. - Không sử dụng bộ nhớ tĩnh (NM). 2.2.4.2. Các điểm khác biệt Những điểm khác biệt giữa thuật toán BD1 với thuật toán PAP và PHP được tóm tắt trong bảng 2.1. 59 Bảng 2.1 Các điểm khác biệt giữa thuật toán BD1 với thuật toán PAP và PHP TT Nội dung Thuật toán PAP Thuật toán PHP Thuật toán BD1 1 Hệ mật của người thiết kế RSA RSA ECIES 128 2 Thông tin backdoor, I(𝑘𝑝𝑟𝑖𝑣𝐺1 ) Toàn bộ số nguyên tố p Toàn bộ số nguyên tố p p⌉k/2, một nửa các bit cao của số nguyên tố p 3 Vị trí giấu thông tin backdoor Trong các bit cao của số modulus n Trong toàn bộ các bit của số modulus n Trong toàn bộ các bit của số modulus n 4 Tuân thủ chuẩn FIPS 186-4 Không Không Thỏa mãn điều kiện “P1” 5 Tính bảo mật Trung bình Trung bình Tốt 6 Lực lượng khóa 𝑅𝐺1 Trung bình = 2− 1 2 𝑛𝑙𝑒𝑛 2 +𝑙𝑜𝑔2 𝑛𝑙𝑒𝑛 2 Trung bình = 2− 1 2 𝑛𝑙𝑒𝑛 2 +𝑙𝑜𝑔2 𝑛𝑙𝑒𝑛 2 −3 Tốt = 2− 1 2 𝑛𝑙𝑒𝑛 2 +2 7 Độ phức tạp tính toán T(G1) Trung bình T(G1) = tp + tq + T(FK) + T(GK) + T(RSA-k) Trung bình T(G1) = tp + tq + T(RSA-k) Tốt T(G1) = tp + tq + T(ECIES) 8 Khôi phục khóa riêng Giải mã mật trực tiếp từ hệ mật RSA Giải mã mật trực tiếp từ hệ mật RSA Phương pháp phân tích nhân tử của Coppersmith 9 Phần thuật toán khôi phục khóa Cần thử hai lần để tìm ra kết quả Chỉ thực hiện một lần Chỉ thực hiện một lần 60 2.2.5. Tóm tắt các điểm nổi bật của thuật toán backdoor BD1 Thuật toán backdoor BD1 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: - 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 khóa 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 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 để khôi phục lại 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. 2.3. Đề xuất thuật toán backdoor BD2 2.3.1. Các bổ đề 2.3.1.1. Bổ đề (lemma) 2.2 Cho p, q là hai số nguyên tố, có cùng chiều dài k bit và giả sử p < q. Ký hiệu n = p.q, n có độ dài 2k bit. Ký hiệu [√𝑛] là phần nguyên của căn bậc 2 của n. Ký hiệu s là số nguyên nhỏ nhất thỏa mãn (q – p) ≤ 2s, s < k. Ký hiệu div là phép chia lấy thương nguyên. Ta luôn có : 𝑝 < [√𝑛] < 𝑞 và 𝑝 𝑑𝑖𝑣 2𝑠 = [√𝑛] 𝑑𝑖𝑣 2𝑠 (các bit cao từ s tới k trong p và [√𝑛] là giống nhau). 61 Chứng minh: Theo giả thuyết ta có: (q – p) ≤ 2s ⇔ q ≤ p + 2s ⇒ q div 2s ≤ (p + 2s) div 2s ⇔ q div 2s ≤ (p div 2s) + 1. Vì s là số nguyên nhỏ nhất thỏa mãn (q – p) ≤ 2s nên q div 2s = (p div 2s) + 1 Ta có: 𝑝 < [√𝑛] < 𝑞 ⇒ p div 2s ≤ [√𝑛] 𝑑𝑖𝑣 2𝑠 ≤ q div 2s = (p div 2s) + 1 ⇒ p div 2s = [√𝑛] 𝑑𝑖𝑣 2𝑠. Điều này có nghĩa là các bit cao từ s tới k trong p và [√𝑛] là giống nhau hoặc (k - s) bit cao trong p và [√𝑛] giống nhau. 2.3.1.2. Bổ đề (lemma) 2.3 Cho p, q là các số nguyên tố, có cùng chiều dài bit là k bit và giả sử p < q. Ký hiệu n = p.q, ký hiệu nlen là độ dài theo bit của n, nlen = 2k. Ký hiệu [√𝑛] là phần nguyên của căn bậc 2 của n. Ký hiệu s là số nguyên nhỏ nhất thỏa mãn (q – p) ≤ 2s. Ký hiệu v là một số nguyên. Ký hiệu p⌉v là v bit cao của p và ký hiệu p⌋v là v bit thấp của p. Nếu biết được