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

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

Thêm vào BST

Báo xấu

31
lượt xem 2
download

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

Bài viết trình bày đề xuất về một thuật toán sinh khóa RSA chứa backdoor đối xứng tuân thủ điều kiện “lỏng” về tham số khóa theo chuẩn FIPS 186-4. Thuật toán đề xuất dựa trên sự cải tiến thuật toán backdoor trong sinh khóa RSA tại mục 3 trong với các tham số đầu vào và đầu ra thỏa mãn chuẩn FIPS 186-4.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

HNUE JOURNAL OF SCIENCE Natural Sciences 2018, Volume 63, Issue 3, pp. 99-107 This paper is available online at http://stdb.hnue.edu.vn DOI: 10.18173/2354-1059.2018-0010 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 Bạch Nhật Hồng1 và Lê Quang Huy2 Khoa Điện - Điện tử, Trường Đại học Sư phạm Kĩ thuật Hưng Yên 2 Cục Chứng thực số và Bảo mật thông tin, Ban Cơ yếu Chính phủ 1 Tóm tắt. Bài báo trình bày đề xuất về một thuật toán sinh khóa RSA chứa backdoor đối xứng tuân thủ điều kiện “lỏng” về tham số khóa theo chuẩn FIPS 186-4 [1]. Thuật toán đề xuất dựa trên sự cải tiến thuật toán backdoor trong sinh khóa RSA tại mục 3 trong [2] với các tham số đầu vào và đầu ra thỏa mãn chuẩn FIPS 186-4. Để khẳng định các phân tích, đánh giá, thuật toán backdoor đề xuất được thử nghiệm trên một thiết bị PKI-Token với các kết quả phù hợp. Từ khóa: Mật mã, sinh khóa, RSA, backdoor. 1. Mở đầu Backdoor trong các hệ mật mã được nghiên cứu phục vụ nhu cầu (hợp pháp) đảm bảo an ninh chống lại việc sử dụng mật mã thực hiện các hành động tội phạm [3]. Căn cứ vào đặc điểm của hệ mật việc nghiên cứu backdoor tập trung vào phần sinh khóa (key generation) đối với hệ mật bất đối xứng và vào phần mã mật (encryption) đối với hệ mật đối xứng. Tuy nhiên các nghiên cứu đã công bố về backdoor đối với một hệ mật xác định chỉ đề xuất các giải pháp chung trên hệ mật đó chứ chưa đề xuất giải pháp tuân thủ một chuẩn nhất định. Với hệ mật khóa công khai RSA đang được sử dụng phổ biến trong các sản phẩm mật mã (phần cứng, phần mềm), nhiều tổ chức định chuẩn đã công bố các chuẩn ứng dụng trong thực tế. Do vậy để các thuật toán backdoor cho hệ mật RSA có thể ứng dụng được trong thực tế cũng cần thỏa mãn một chuẩn nhất định. Hiện tại chuẩn FIPS 186-4 về chữ kí số do viện tiêu chuẩn quốc gia Mỹ (NIST) công bố có bao gồm hệ mật RSA, được nhiều nhà sản xuất các sản phẩm mật mã tuân thủ. Để có thể ứng dụng đảm bảo an ninh khi sử dụng mật mã, bài báo tập trung nghiên cứu về backdoor trong sinh khóa RSA và đề xuất một thuật toán sinh khóa RSA chứa backdoor đối xứng tuân thủ điều kiện “lỏng” về tham số khóa tại Appendix B.3.1. FIPS 186-4 [1]. 2. Nội dung nghiên cứu 2.1. Cơ sở về backdoor trong sinh khóa RSA 2.1.1. Công cụ hình thức phân tích và đánh giá backdoor Để tạo cơ sở phân tích và đánh giá backdoor, công cụ hình thức của Arboit (mục 4.2 chương 4 trong [5]) với định nghĩa hình thức cụ thể, các tiêu chuẩn đánh giá hiệu quả được sử dụng trong bài báo này và được trình bày tóm tắt tại mục A phần 2 trong [2]. Để đánh giá backdoor, các tiêu chuẩn đánh giá được phân tích, lượng hóa, phân ngưỡng, tổng hợp tại bảng I mục B phần 2 trong [2]. Ngày nhận bài: 19/7/2017. Ngày sửa bài: 1/2/2018. Ngày nhận đăng: 9/2/2018. Tác giả liên hệ: Lê Quang Huy. Địa chỉ e-mail: lequanghuyabc@gmail.com 99 Bạch Nhật Hồng và Lê Quang Huy 2.1.2. Phương pháp phân tích nhân tử của Coppersmith Một vấn đề khó trong lí thuyết số là tìm cách hiệu quả để phân tích nhân tử của một số nguyên. Các thuật toán phân tích nhân tử tốt nhất hiện nay, phương pháp đường cong Ellip và sàng trường số, vẫn có độ phức tạp lũy thừa. Một hướng nghiên cứu được hình thành gần đây là sự nới lỏng bài toán phân tích nhân tử để có thể giải quyết được trong thời gian đa thức. Một sự nới lỏng bài toán phân tích nhân tử có nhiều ứng dụng trong phân tích mã là phân tích nhân tử khi biết một nửa số các bit của số nguyên tố p, sử dụng phương pháp tìm nghiệm nguyên nhỏ của phương trình đa thức modulo một biến của Coppersmith [4]. * Tìm nghiệm nguyên nhỏ của phương trình đa thức modulo một biến Đến nay, chưa có thuật toán tổng quát hiệu quả để tìm nghiệm nguyên của phương trình modulo một biến. Năm 1996, Coppersmith [4] đã đưa ra phương pháp hiệu quả tìm nghiệm nguyên nhỏ của phương trình modulo một biến sử dụng thuật toán rút gọn cơ sở LLL.  Phát biểu bài toán Giả thuyết cho: - N là một số nguyên lớn không biết nhân tử (thừa số) - Đa thức f ∈ Z[x], có bậc d, f (x) = ad xd + ad-1 xd-1 + … + a1x + a0 - Phương trình modulo: f (x) ≡ 0 (mod N) Cần tìm nghiệm nguyên x0 ∈ Z, của phương trình f (x) ≡ 0 (mod N); với | x0 | ≤ X, X là một ràng buộc xác định, x0 thỏa mãn f (x0) ≡ 0 (mod N).  Ý tưởng và cách tìm nghiệm Ý tưởng: rút gọn (biến đổi) bài toán tìm nghiệm nguyên nhỏ của phương trình modulo thành bài toán tìm nghiệm nguyên nhỏ của phương trình trên tập các số nguyên Z. Điều kiện: Giả sử |f (x)| < N với | x | ≤ X, (X là một ràng buộc xác định). Khi đó nghiệm x0 của phương trình đa thức f (x) = 0, cũng là nghiệm của f (x) ≡ 0 (mod N). Ràng buộc X càng lớn thì càng chứa được nhiều nghiệm. Nghiệm x0 của f (x) = 0 trên Z có thể được tìm thấy bằng cách sử dụng các thuật toán tìm nghiệm chuẩn (Sturm sequence). Cách thực hiện: lựa chọn tập đa thức thích hợp để xây dựng đa thức mới là tổ hợp tuyến tính của các đa thức trong tập hợp sao cho vector (hệ số) của đa thức mới có chuẩn Euclide thỏa mãn điều kiện biến đổi phương trình modulo thành phương trình không modulo. Ràng buộc X và các hệ số của đa thức mới được tìm thấy hiệu quả bằng cách áp dụng thuật toán rút gọn LLL. * Phân tích nhân tử số modulo N khi biết một nửa số bit p Phương pháp tìm nghiệm nguyên nhỏ của phương trình đa thức modulo một biến có nhiều ứng dụng rộng rãi. Một ứng dụng quan trọng là: phân tích nhân tử số modulo N = p.q trong thời gian đa thức, khi biết một nửa các bit của số nguyên tố p. Cụ thể, Coppersmith trong [4] đã chứng minh các kết quả sau: Định lí 2.1. Phân tích nhân tử khi biết các bit cao của kp Cho N = p.q, giả sử p > q, gọi k là một số nguyên không phải là bội số của q. Giả sử ta biết được xấp xỉ p’ của kp sao cho: kp  p '  2 N 1 4 Thì có thể phân tích nhân tử N trong thời gian đa thức theo log N. Định lí 2.2. Phân tích nhân tử khi biết các bit cao của p Cho N = p.q, trong đó p, q là các số nguyên tố. Nếu biết một nửa các bit cao (1/4 log2 N) của p, ta có thể phân tích nhân tử N trong thời gian đa thức theo kích thước bit của p. Định lí 2.3. Phân tích nhân tử khi biết các bit thấp của p 100 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 Cho N = p.q trong đó p, q có cùng kích thước bit và p > q. Giả sử biết p0 và M thỏa mãn p0 = p mod M và M ≥ N1/4 thì có thể phân tích nhân tử của N trong thời gian đa thức log2 N. 2.1.3. Thuật toán trung thực tuân thủ điều kiện “lỏng” theo chuẩn FIPS 186-4 Để tạo cơ sở cho việc phân tích và đánh giá thuật toán backdoor đề xuất, điều kiện về tham số và thuật toán trung thực tuân thủ chuẩn FIPS 186-4 được trình bày chi tiết. * Điều kiện “lỏng” về tham số khóa RSA theo FIPS 186-4 Điều kiện “lỏng” về tham số khóa của hệ mật RSA là điều kiện về tham số khóa được mô tả tại mục A2 và mục B tại phần B.3.1 appendix B, FIPS 186-4 [1]. “Lỏng” ở đây được hiểu là yêu cầu “không cao” về tính nguyên tố của tham số p và q (các số có thể nguyên tố), để có không gian khóa lớn. Kí hiệu khóa công khai (n, e), khóa riêng (n, d), n = p.q, với p, q là các số nguyên tố. Kí hiệu nlen là độ dài theo bit của n. Các tham số thỏa mãn điều kiện sau: 1. p và q là các số có thể nguyên tố (probable prime) ngẫu nhiên (nlen ≥ 2048). 2. e được chọn trước khi tạo p, q; e là một số lẻ thỏa mãn: 216 < e < 2256. 3. Các số nguyên tố p và q thỏa mãn các ràng buộc sau: a) (p - 1), (q - 1) nguyên tố cùng nhau với số mũ công khai e. b) 2.  2nlen /21   p, q   2nlen/21  (1) c) p  q  2nlen /2100 (2) 4. Số mũ riêng d, được tạo sau khi tạo p và q, thỏa mãn: 2nlen / 2 < d < LCM (p - 1, q - 1) và d = e-1 mod (LCM (p - 1, q - 1)). * Thuật toán sinh khóa RSA tuân thủ điều kiện “lỏng” (thuật toán G0) Thuật toán sinh khóa RSA trung thực tuân thủ điều kiện “lỏng” theo chuẩn FIPS 186-4 được tóm tắt theo thuật toán tại mục B.3.3. appendix B FIPS 186-4, được mô tả như sau: Input (nlen, e) Output (p, q, n, e, d) 1: if (e < 216 or e > 2256) then return failure ; // generate p 2: p = RandomOddInteger() ; //log2 p =nlen/2    7: if q  2.2nlen /21 then goto step 6 ; nlen/2 – 100 8: if ( |p – q| ≤ 2 ) then go to step 6 ; 9: if (gcd(q - 1, e) ≠ 1) then goto step 6 ; 10: if (not PrimalityTest (q)) then goto step 6 ; // compute n, d 11: n = p.q ; 12: d = e–1 mod (LCM(p - 1, q - 1)) ;  3: if p  2.2nlen /21 then goto step 2 ; 4: if (gcd(p - 1, e) ≠ 1) then goto step 2 ; 5: if (not PrimalityTest (p)) then goto step 2; // generate q 6: q = RandomOddInteger() ; //log2 q =nlen/2 nlen/ 2 13: if ( d < 2 ) then go to step 6 ; 14: return (p, q, n, d) ; 2.3.5. Lực lượng khóa của thuật toán sinh khóa RSA tuân thủ điều kiện “lỏng” Xét cách tạo p: Vì p là một số nguyên tố nằm trong khoảng   2.2nlen /21 , 2nlen /2  1 . 101 Bạch Nhật Hồng và Lê Quang Huy Nên 2 nlen /2 #{ p   2.2nlen /21  } = Pr[số nlen/2 bit nlen /2 là số nguyên tố]. nlen /2 2 2 2 .0, 6.2nlen /21  1, 2.   2nlen /2log2 nlen nlen / 2 nlen nlen 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 (3) (4) -100 – (p - 2 nlen/2 -100 ) = nlen /2 97 2 2 .2nlen /299  nlen / 2 nlen (5) Vì q được tạo giống như p và sau p thỏa mãn điều kiện (2), 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))   với giá trị là : 2  2 .2nlen /21  2nlen /22 . Nên #{q} = #{p} - #{u} = 2nlen /2 2nlen /297 2nlen /21    2nlen /21log2 nlen nlen nlen nlen (6) Vậy lực lượng khóa của thuật toán là, #{(p, q, d)} = {#{p}. #{q)} 2nlen /2 2nlen /21 2nlen 1 = .  nlen nlen nlen 2 2.2. Đề xuất thuật toán sinh khóa RSA chứa backdoor mới (7) 2.2.1. Giới thiệu thuật toán Thuật toán sinh khóa RSA chứa backdoor đề xuất được xây dựng dựa trên việc cải tiến thuật toán backdoor ở mục 3.4. trong [2]. Điểm cải tiến trong thuật toán đề xuất là các tham số đầu vào và đầu ra (p, q, d) thỏa mãn điều kiện “lỏng” theo chuẩn FIPS 186-4. Việc cải tiến chỉ áp dụng cho phần sinh khóa, phần khôi phục khóa không thay đổi. Ý tưởng của thuật toán: tạo số nguyên tố p ngẫu nhiên, trích thông tin backdoor từ p và nhúng vào một giá trị n’ gần với số modulus n. Từ giá trị n’ sẽ tìm ra q, n và d. Thông tin backdoor I(kpriv) = ((p⌉k/2)⌋s - k/2), được trích với độ dài nhỏ hơn một nửa các bit của số nguyên tố p (bước 10). Kỹ thuật nhúng: thông tin backdoor sau khi đã mã mật được ghép vào phía bên phải (các bit thấp) với giá trị ngẫu nhiên (các bit cao) để tạo ra một giá trị có độ dài k = nlen/2 bit, giá trị được ghép này được ghép tiếp vào bên trái (phía các bit cao) với giá trị nlen/2 bit ngẫu nhiên (các bit thấp) tạo thành giá trị có chiều dài nlen bit. (bước 12). Giá trị nlen bit này được sử dụng để tìm ra số nguyên tố q. Các tham số thuật toán: + G1 = Thuật toán đề xuất; G1 = G0 = nlen ≥ 2048; E = AES, E ≥ 128; M = n; log2 p = log2 q = k=nlen/2. + Hàm F: là hàm mã mật hóa đối xứng AES, AES ≥ 128. + Hàm G: {0, 1}2k x {0, 1}k/2 x {0, 1}k/2 → {0, 1}k, hàm này thực hiện phương pháp phân tích nhân tử của Coppersmith (mục 2.2), ví dụ: p = G(n, 2k/2, p div 2k/2). 102 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 Thuật toán đề xuất [sinh khóa RSA] 1: Input (e, s, nlen) ; 2: if (e < 216 or e > 2256) then return failure ; // tạo số nguyên tố p 3: p = RandomOddInteger() ; //log2 p =nlen/2  4: if p  2.2 nlen /21 Start 16 2