Tài liệu Nghiên cứu, phát triển một số thuật toán sinh khóa rsa chứa backdoor tomtat luanan _tiengviet

BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ LÊ QUANG HUY NGHIÊN CỨU, PHÁT TRIỂN MỘT SỐ THUẬT TOÁN SINH KHÓA RSA CHỨA BACKDOOR Chuyên ngành: Cơ sở toán học cho tin học Mã số: 9 46 01 10 TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC HÀ NỘI - 2018 Công trình được hoàn thành tại: VIỆN KH&CN QUÂN SỰ - BỘ QUỐC PHÒNG Người hướng dẫn khoa học: 1. PGS. TS. Bạch Nhật Hồng 2. TS. Trần Duy Lai Phản biện 1: GS. TS. Nguyễn Bình Phản biện 2: PGS. TS. Nguyễn Linh Giang Phản biện 3: TS. Lưu Hồng Dũng Luận án sẽ được bảo vệ trước Hội đồng đánh giá luận án cấp Viện, họp tại Viện KH&CNQS Vào hồi giờ ngày tháng năm 2018 Có thể tìm hiểu luận án tại thư viện: - Thư viện Viện Khoa học và Công nghệ quân sự - Thư viện Quốc gia Việt Nam 1 MỞ ĐẦU 1. Tính cấp thiết Sự phát triển của xã hội dẫn tới nhu cầu trao đổi thông tin. Mạng Internet phát triển đã kéo theo các vấn đề gây mất an toàn thông tin. Giải pháp tốt nhất hiện nay là sử dụng mật mã, mật mã khóa công khai để đảm bảo an toàn cho các giao dịch điện tử. Tuy nhiên khi ứng dụng mật mã khóa công khai thì xuất hiện các sự kiện sử dụng mật mã để thực hiện các hành vi trái pháp luật, tội phạm. Từ đó nảy sinh nhu cầu cần có biện pháp để khôi phục, giải mã các dữ liệu đã mã mật để bảo vệ cộng đồng. Hiện tại có 03 cách phổ biến nhất để lấy được bản rõ từ bản mã: 1. Lấy khóa mã thông qua con người: ăn cắp/mua chuộc/hối lộ: chỉ thực hiện được với một số trường hợp xác định và mang tính ngẫu nhiên. 2. Khai thác các lỗ hổng có sẵn trên các sản phẩm mật mã do cố ý tạo ra: Sử dụng backdoor có nhược điểm làm giảm không gian khóa nhưng có ưu điểm khôi phục lại bản mã nhanh, tất định, chi phí triển khai thấp, khó bị phát hiện khi cài đặt trong những sản phẩm mật mã dạng hộp đen. 3. Thám mã (phá vỡ hệ mật bằng các phương pháp toán học): Đã đạt được những kết quả nhất định, tuy nhiên với sự phát triển của các hệ mật mã hiện đại thì việc thám mã để khôi phục lại bản rõ trở nên ngày càng khó và không khả thi cả về chi phí, công sức và thời gian. Trong những năm gần đây, đã phát hiện được một số doanh nghiệp, cơ quan chính phủ cài backdoor vào trong các sản phẩm mật mã và vào trong các chuẩn mật mã. Bên cạnh đó nhiều nghiên cứu về backdoor mật mã đã được công bố và tập trung nhiều vào hệ mật RSA. Đến nay, các nghiên cứu về backdoor mật mã đã công bố hoặc đã bị phát hiện với số lượng ít và chất lượng còn cần nhiều nỗ lực cải tiến hơn nữa. Vậy khi sử dụng mật mã luôn có hai nhu cầu đồng thời tồn tại: nhu cầu bảo vệ thông tin bằng các hệ mật mã và nhu cầu phá vỡ tính bảo mật. Mật mã càng được sử dụng rộng rãi thì nhu cầu đảm bảo an ninh khi sử dụng mật mã ngày càng tăng. Hiện tại việc sử dụng các sản phẩm mật mã trên thế giới và ở Việt Nam diễn ra ngày càng nhiều, kéo theo nhu cầu đảm bảo an ninh cho cộng đồng khi dùng mật mã ngày càng cấp thiết. Từ thực tế ứng dụng, nhu cầu, hiện trạng nghiên cứu, triển khai 2 backdoor mật mã, NCS lựa chọn đề tài “Nghiên cứu, phát triển một số thuật toán sinh khóa RSA chứa backdoor” nhằm nghiên cứu vấn đề đảm bảo an ninh cho việc ứng dụng PKI, chống lại việc sử dụng PKI để thực hiện các hành vi tội phạm. Cụ thể, Luận án nghiên cứu một vấn đề hẹp là “thuật toán sinh khóa RSA có chứa backdoor”, ứng dụng để đảm bảo an ninh cho các hạ tầng PKI. 2. Mục đích, nhiệm vụ nghiên cứu 2.1. Mục đích nghiên cứu Tìm kiếm các thuật toán sinh khóa chứa backdoor hiệu quả để có thể ứng dụng nhằm đảm bảo an ninh cho một hạ tầng PKI cụ thể. 2.2. Nhiệm vụ nghiên cứu - Nghiên cứu các mô hình, công cụ hình thức hiệu quả để phân tích và đánh giá backdoor. - Tìm kiếm phương pháp trích, nhúng thông tin backdoor, phương pháp khôi phục khóa riêng tất định từ khóa công khai chứa backdoor. - Đề xuất một số thuật toán sinh khóa chứa backdoor tuân thủ chuẩn xác định (ví dụ chuẩn FIPS 186-4). - Cài đặt, thử nghiệm các thuật toán sinh khóa chứa backdoor trong các module mật mã tạo khóa dạng hộp đen. 3. Đối tượng, phạm vi nghiên cứu 3.1. Đối tượng nghiên cứu - Mô hình lý thuyết, công cụ hình thức, tiêu chí đánh giá các thuật toán về backdoor trong các hệ mật. - Phương pháp tạo (trích, nhúng thông tin) backdoor. - Phương pháp khôi phục khóa riêng từ khóa công khai có backdoor. 3.2. Phạm vi nghiên cứu Sinh khóa, khôi phục khóa chứa backdoor trên hệ mật RSA. 4. Cơ sở lý luận, thực tiễn và phương pháp nghiên cứu 4.1. Cơ sở lý luận - Lý thuyết về backdoor trong các hệ mật: nhằm tập hợp các kiến thức về phân tích và đánh giá backdoor mật mã. - Hệ mật mã khóa công khai RSA: nhằm nghiên cứu các kiến thức, các tham số, các chuẩn có liên quan và thuật toán sinh khóa của hệ mật. 3 - Phương pháp phân tích nhân tử: nhằm nghiên cứu các phương pháp tìm nghiệm nguyên của phương trình đa thức modulo một biến phục vụ cho việc phân tích nhân tử nguyên tố p, của số modulus RSA. 4.2. Thực tiễn - Nhu cầu ứng dụng của nhà cung cấp hạ tầng khóa công khai cung cấp lại khóa riêng của người dùng mà không phải duy trì CSDL khóa. - Nhu cầu khôi phục lại bản rõ từ bản mã của của các cơ quan quốc phòng, an ninh (khi không biết được khóa riêng của người dùng). - Cung cấp cho người dùng những hiểu biết để nhận biết và phòng chống backdoor khi sử dụng những sản phẩm mật mã dạng hộp đen. 4.3. Phương pháp nghiên cứu Phương pháp nghiên cứu: mô hình hóa, thực nghiệm. 5. Bố cục của Luận án Ngoài các phần mở đầu, kết luận, các công trình khoa học đã công bố, tài liệu tham khảo, Luận án tập trung vào 03 chương: Chương 1: Cơ sở về Backdoor trong sinh khóa Trình bày cơ sở về Backdoor: công cụ mô hình hóa, các tiêu chí đánh giá backdoor; phương pháp phân tích nhân tử của Coppersmith; chuẩn FIPS 186-4, một số kết quả nghiên cứu backdoor trong sinh khóa RSA. Chương 2: Đề xuất thuật toán backdoor BD1, BD2 Trình bày đề xuất 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 BD1, BD2 được phân tích, đánh giá theo mô hình của Arboit, được thử nghiệm trên thiết bị T-Token có kết quả phù hợp với đánh giá. Chương 3: Đề xuất thuật toán backdoor BD3 Trình bày đề xuất về 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. Thuật toán BD3 được phân tích, đánh giá theo mô hình của Arboit, được thử nghiệm trên thiết bị T-Token có các kết quả phù hợp với đánh giá. 4 CHƯƠNG 1. CƠ SỞ VỀ BACKDOOR TRONG SINH KHÓA Chương này trình bày cơ sở về backdoor trong sinh khóa công khai, trong đó tập trung trình bày công cụ hình thức của Alboit, phương pháp phân tích nhân tử của Coppersmith, chuẩn FIPS 186-4 và một số kết quả nghiên cứu về backdoor trong sinh khóa RSA. Trên cơ sở phân tích, đánh giá kết quả nghiên cứu backdoor của các tác giả đi trước, chương 1 nêu vấn đề cần nghiên cứu, giải quyết của luận án. 1.1. Giới thiệu về backdoor mật mã Phần này trình bày khái quát chung về backdoor mật mã bao gồm khái niệm, lịch sử phát triển, một số đặc trưng chung, phạm vi sử dụng của backdoor mật mã. 1.2. Cơ sở về backdoor trong sinh cặp khóa Phần này trình bày mô hình phân tích backdoor, định nghĩa backdoor an toàn và các tiêu chí đánh giá thuật toán sinh khóa chứa backdoor theo các kết quả nghiên cứu của Arboit. 1.3. Phương pháp phân tích nhân tử của Coppersmith Phần này trình bày phương pháp phân tích nhân tử của Coppersmith, cách giải quyết bài toán phân tích nhân tử được nới lỏng là phân tích nhân tử n = p.q 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. 1.4. Một số kết quả về hệ mật RSA Phần này tập trung trình bày các điều kiện về tham số khóa của hệ mật RSA tuân thủ chuẩn FIPS 186-4. 1.5. Một số kết quả nghiên cứu backdoor trong sinh khóa RSA Có hai nhóm kết quả nghiên cứu về backdoor. Nhóm thứ nhất là các công cụ hình thức để phân tích, đánh giá backdoor và nhóm thứ hai là các thuật toán backdoor. Nhóm công cụ hình thức để phân tích và đánh giá backdoor gồm: SETUP (Kleptography) từ các kết quả của Young và Yung và Secure Backdoor từ kết quả của Arboit. Nhóm kết quả thuật toán sinh khóa chứa backdoor của nhiều tác giả khác nhau gồm: các backdoor đối xứng và backdoor bất đối xứng. Một số backdoor đối xứng điển hình 5 gồm: Anderson-Kaliski, Howgrave-Graham, Crépeau-Slakmon. Một số backdoor bất đối xứng điển hình gồm: PAP, PAP-2, Primes Private, ECSETUP, PHP. Các backdoor đối xứng ưu điểm: hệ mật người thiết kế có kích thước khối mã nhỏ thuật tiện cho việc rút gọn thông tin backdoor; có thể chọn độ dài khóa hệ mật người thiết kế có độ an toàn tương đương hoặc lớn hơn độ an toàn tương đương của hệ mật người dùng và nhược điểm: vấn đề quản lý khóa của hệ mật người thiết kế. Các backdoor bất đối xứng có ưu điểm: chỉ duy nhất người thiết kế có thể sử dụng được backdoor (khôi phục được khóa riêng của người dùng) và nhược điểm: nếu dùng hệ mật khác ngoài EC thì có độ dài khối mã lớn nên khó rút gọn thông tin backdoor. có các ưu nhược điểm sau: 1.5.1. Ưu điểm - Công cụ hình thức để phân tích và đánh giá backdoor của Arboit [4] là công cụ hiệu quả, toàn diện hơn để phân tích và đánh giá backdoor. - Một số thuật toán backdoor hiệu quả, với các ưu điểm: + Thông tin backdoor: sử dụng một phần các bit của số nguyên tố p, phần này rút gọn nhất về một nửa các bit của số nguyên tố p. + Vị trí nhúng thông tin backdoor: vào số modulus n với các kỹ thuật nhúng khác nhau mà vẫn đạt được tính tương quan cao. + Sử dụng hệ mật đối xứng để mã mật thông tin backdoor có kích thước khối mã nhỏ thuật tiện cho việc rút gọn thông tin backdoor. 1.5.2. Tồn tại - Các thuật toán sinh khóa chứa backdoor đã công bố chỉ thiết kế chung cho hệ 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 á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 á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 ̣ng 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). Start e, nlen, B1 No 216 < e < 2256 nlen 2048 Yes Tạo số nguyên tố p GCD (p - 1, e) = 1 p là số có thể nguyên tố (1,41.2nlen/2-1 No p < 2nlen/2) Yes Chuẩn bị thông tin backdoor Chèn thông tin backdoor vào modulus n Tạo số nguyên tố q có chèn thông tin backdoor Tính giá trị q Trả về mã lỗi GCD (q - 1, e) = 1 q là số có thể nguyên tố (1,41 . 2nlen/2-1 |p – q| > 2 No q < 2nlen/2) nlen/2 – 100 Yes Tính n, d 2nlen/ 2 < d< LCM (p-1, q-1) No Yes p, q, n, d Stop Hình 2.3. Sơ đồ khối phần thuật toán sinh khóa của backdoor BD1 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 < 216 or 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 9 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: r = RandomOddInteger() ; //log2 r = k/2 v = v1.2k/2 + r ; //v = v1 : r v0 = v mod p ; s0 = (v0 + u2).u-1 mod p ; if (s0 ≤ 2k-1) then s = 2k – s0 ; n = s.2k + v ; // n = s : v q = n / p ; //lemma 2.1 if (𝑞 < √2. 2𝑛𝑙𝑒𝑛/2−1 ) then next i ; nlen/2 – 100 if ( |p – q| ≤ 2 ) then next i ; if (gcd(q - 1, e) ≠ 1) then next i ; if (PrimalityTest (q))) then break ; endfor ; if not (PrimalityTest (q))) then goto step 3; d = e–1 mod (LCM(p - 1, q - 1)) ; nlen/ 2 25: if ( d < 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 𝑛𝑙𝑒𝑛 𝑁𝐺 ,𝑞 23𝑛𝑙𝑒𝑛/4+1− 𝑙𝑜𝑔2 𝑛𝑙𝑒𝑛 𝑅𝐺1 = 1 ≈ 𝑛𝑙𝑒𝑛−1−𝑙𝑜𝑔 𝑛𝑙𝑒𝑛 = 22−𝑛𝑙𝑒𝑛/4 = 2−2. 2 +2 2 𝑁𝐺0 ,𝑞 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 Start e, nlen, s No 216 < e < 2256 nlen 2048 Yes Tạo số nguyên tố p GCD (p - 1, e) = 1 p là số có thể nguyên tố (1,41.2nlen/2-1 No p < 2nlen/2) Yes Chuẩn bị thông tin backdoor Chèn thông tin backdoor vào modulus n Tạo số nguyên tố q có chèn thông tin backdoor Tính giá trị q Trả về mã lỗi GCD (q - 1, e) = 1 q là số có thể nguyên tố (1,41 . 2nlen/2-1 No q < 2nlen/2) |p – q| > 2nlen/2 – 100 Yes Tính n, d 2nlen/ 2 < d< LCM (p-1, q-1) No Yes p, q, n, d Stop Hình 2.5. Sơ đồ khối phần thuật toán sinh khóa của backdoor BD2 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 < 216 or 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 ; 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: 16: 17: 18: 19: nlen/2 – 100 if ( |p – q| ≤ 2 if (gcd(q - 1, e) ≠ 1) if (not (PrimalityTest n = p.q ; d = e–1 mod (LCM(p - 1, ) then go to step 7 ; then goto step 7 ; (q))) then goto step 7; // lemma 2.4 q - 1)) ; nlen/ 2 20: if ( d < 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 ; 3: p1 = ([√𝑛])⌉𝑘−𝑠 ; 4: p2 = F-1K(μ) ; 5: p3 = p1 . 2 s-k/2 + p2 ; 6: p = S(n, 2k/2, p3) ; 7: q = n / p ; 8: d ≡ e−1 mod φ(n) ; 9: return (p, q, d) ; // lemma 2.4 // lemma 2.2 //p3 = p1 : p2, p3 == p⌉k/2 // Coppersmith method 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 𝑛𝑙𝑒𝑛 𝑁𝐺 ,𝑞 2𝑛𝑙𝑒𝑛+2−𝑠− 𝑙𝑜𝑔2 𝑛𝑙𝑒𝑛 𝑅𝐺1 = 1 ≈ 𝑛𝑙𝑒𝑛−1−𝑙𝑜𝑔 𝑛𝑙𝑒𝑛 = 23−𝑠 < 2−2+3 = 2−2. 2 +3 2 𝑁𝐺0 ,𝑞 2 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 Kết quả thử nghiệm độ phức tạp backdoor BD1 Thời gian thực hiện (s) 2.5 2 1.5 1 0.5 0 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 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 2.04s Thời gian chạy G1 Sinh khóa Khôi phục khóa 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 2.04 s Thời gian chạy G1 Sinh khóa Khôi phục khóa 2.43 s 0.04 s 16 Thời gian thực hiện (s) 3 Kết quả thử nghiệm độ phức tạp backdoor BD2 2.5 2 1.5 1 0.5 0 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 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. 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: Start e, nlen, n1, n2, n3, n4, m No 216 < e < 2256 nlen 1024 Yes Chuẩn bị thông tin backdoor 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 Tạo số nguyên tố p Yes Tạo số nguyên tố p GCD (p - 1, e) = 1 (1,41.2nlen/2-1 No p < 2nlen/2) Yes Tạo các số nguyên tố phụ q1, q2 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 Trả về mã lỗi Tạo số nguyên tố q GCD (q - 1, e) = 1 q < 2nlen/2) (1,41 . 2nlen/2-1 No |p – q| > 2nlen/2 – 100 Yes Tính n, d 2nlen/ 2 < d< LCM (p-1, q-1) No Yes p, q, n, d Stop Hình 3.2. Sơ đồ khối phần thuật toán sinh khóa của backdoor BD3 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 < 216 or 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 ) ;