Luận Án Tiến Sĩ: Nghiên Cứu Phát Triển Thuật Toán Sinh Khóa RSA Chứa Backdoor

Luận án tiến sĩ nghiên cứu phát triển thuật toán sinh khóa RSA chứa backdoor, tập trung vào bảo mật và ứng dụng thực tiễn trong lĩnh vực mã hóa.

• Tác giả: Lê Quang Huy
• Người hướng dẫn: TS. Bạch Nhật Hồng
• Trường học: Viện Khoa Học và Công Nghệ Quân Sự
• Chuyên ngành: Cơ sở toán học cho tin học
• Đề tài: Nghiên cứu, phát triển một số thuật toán sinh khóa RSA chứa backdoor
• Loại tài liệu: luận án tiến sĩ
• Năm xuất bản: 2018
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: CƠ SỞ VỀ BACKDOOR TRONG SINH KHÓA
• 1.1. Giới thiệu về backdoor mật mã
• 1.2. Cơ sở về backdoor trong sinh cặp khóa
• 1.3. Phương pháp phân tích nhân tử của Coppersmith
• 1.4. Một số kết quả về hệ mật RSA
• 1.5. Một số kết quả nghiên cứu backdoor trong sinh khóa RSA
• 1.6. Những vấn đề luận án cần tập trung nghiên cứu giải quyết
• 1.7. Kết luận chương 1
• 2. CHƯƠNG 2: ĐỀ XUẤT THUẬT TOÁN BACKDOOR BD1, BD2
• 2.1. Cơ sở cài và đánh giá backdoor
• 2.2. Đề xuất thuật toán backdoor BD1
• 2.3. Đề xuất thuật toán backdoor BD2
• 2.4. Thử nghiệm các thuật toán backdoor BD1, BD2
• 2.5. Ứng dụng backdoor BD1, BD2
• 2.6. Kết luận chương 2
• 3. CHƯƠNG 3: ĐỀ XUẤT THUẬT TOÁN BACKDOOR BD3
• 3.1. Thuật toán sinh khóa trung thực tuân thủ điều kiện “P2”
• 3.2. Đề xuất thuật toán backdoor BD3
• 3.3. Thử nghiệm thuật toán backdoor BD3
• 3.4. Ứng dụng backdoor BD3
• 3.5. Đánh giá các thuật toán backdoor đề xuất
• 3.6. Kết luận chương 3
• KẾT QUẢ ĐẠT ĐƯỢC CỦA LUẬN ÁN
• NHỮNG ĐÓNG GÓP MỚI CỦA LUẬN ÁN
• HƯỚNG NGHIÊN CỨU TIẾP THEO
• CÁC CÔNG TRÌNH KHOA HỌC ĐÃ CÔNG BỐ
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Giới thiệu về backdoor mật mã

Backdoor mật mã là một cơ chế thay đổi thuật toán mật mã, làm yếu đi tính bảo mật, cho phép người tạo backdoor phá vỡ bản mã nhanh hơn so với phương pháp thám mã thông thường. Backdoor có thể được cài đặt trong phần mềm, phần cứng hoặc kết hợp cả hai. Đối tượng của backdoor bao gồm các thuật toán mật mã, giao thức mật mã và bộ sinh số giả ngẫu nhiên. Backdoor được phân loại thành backdoor đối xứng và backdoor bất đối xứng, trong đó backdoor bất đối xứng chỉ có thể sử dụng bởi người thiết kế, ngay cả khi cài đặt được công bố công khai.

1.1. Khái niệm backdoor

Backdoor hay trapdoor là một lối vào ẩn hoặc cách truy cập hệ thống mà không cần thực hiện các thủ tục xác thực thông thường. Trong hệ thống máy tính, backdoor có thể là một công cụ quản trị hoặc một chương trình độc hại được cài đặt để truy cập hệ thống về sau. Backdoor thường không để lại dấu vết và khó phát hiện, có thể tồn tại dưới dạng phần mềm, phần cứng hoặc tính năng ẩn.

1.2. Sự phát triển của backdoor mật mã

Backdoor mật mã được nghiên cứu từ những năm 1980, bắt đầu với khái niệm kênh ngầm của Simmons (1984). Năm 1988, Desmedt khái quát hóa về kênh ngầm và lạm dụng hệ mật. Backdoor mật mã được xem là một dạng tấn công gián tiếp, tạo ra các khóa yếu để làm suy yếu hệ mật. Quá trình phát triển của backdoor mật mã được minh họa qua các giai đoạn từ 1983 đến 2016, với sự xuất hiện của các backdoor đối xứng và bất đối xứng.

II. Cơ sở về backdoor trong sinh khóa RSA

Backdoor trong sinh khóa RSA là một phương pháp để tạo ra các cặp khóa (khóa công khai và khóa riêng) có chứa thông tin ẩn, cho phép người tạo backdoor khôi phục khóa riêng từ khóa công khai. Backdoor trong sinh khóa RSA thường được áp dụng trong các hệ thống PKI (Public Key Infrastructure) để đảm bảo an ninh mạng và phòng chống tội phạm sử dụng mật mã.

2.1. Phương pháp phân tích nhân tử của Coppersmith

Phương pháp phân tích nhân tử của Coppersmith là một công cụ quan trọng để khôi phục khóa riêng từ khóa công khai chứa backdoor. Phương pháp này dựa trên việc tìm nghiệm nguyên của phương trình đa thức modulo một biến, giúp phân tích nhân tử nguyên tố của số modulus RSA. Đây là cơ sở để thiết kế các thuật toán sinh khóa RSA chứa backdoor hiệu quả.

2.2. Chuẩn FIPS 186 4 và hệ mật RSA

Chuẩn FIPS 186-4 quy định các yêu cầu về sinh khóa RSA, bao gồm độ dài khóa, phương pháp sinh số nguyên tố và các điều kiện an toàn. Backdoor trong sinh khóa RSA cần tuân thủ các điều kiện của chuẩn này để đảm bảo tính bảo mật và khó bị phát hiện. Các thuật toán sinh khóa RSA chứa backdoor được đề xuất trong luận án đều tuân thủ chuẩn FIPS 186-4.

III. Đề xuất thuật toán backdoor BD1 BD2 và BD3

Luận án đề xuất ba thuật toán sinh khóa RSA chứa backdoor là BD1, BD2 và BD3. Các thuật toán này được thiết kế để tuân thủ các điều kiện an toàn của chuẩn FIPS 186-4, đồng thời cho phép khôi phục khóa riêng từ khóa công khai một cách hiệu quả. Các thuật toán được thử nghiệm trên thiết bị T-Token và cho kết quả phù hợp với đánh giá lý thuyết.

3.1. Thuật toán backdoor BD1 và BD2

Thuật toán BD1 và BD2 được đề xuất với các tham số tuân thủ điều kiện P1 của chuẩn FIPS 186-4. Các thuật toán này sử dụng phương pháp nhúng thông tin backdoor vào khóa công khai và khôi phục khóa riêng từ khóa công khai thông qua phương pháp phân tích nhân tử. Kết quả thử nghiệm cho thấy BD1 và BD2 có độ phức tạp thấp và khó bị phát hiện.

3.2. Thuật toán backdoor BD3

Thuật toán BD3 được đề xuất với các tham số tuân thủ điều kiện P2 của chuẩn FIPS 186-4. BD3 sử dụng phương pháp sinh khóa trung thực và nhúng thông tin backdoor một cách tinh vi hơn so với BD1 và BD2. Kết quả thử nghiệm cho thấy BD3 có độ phức tạp cao hơn nhưng đảm bảo tính bảo mật tốt hơn.

IV. Ứng dụng và đánh giá các thuật toán backdoor

Các thuật toán sinh khóa RSA chứa backdoor được đề xuất có thể ứng dụng trong các hệ thống PKI để đảm bảo an ninh mạng và phòng chống tội phạm sử dụng mật mã. Các thuật toán này cung cấp khả năng khôi phục khóa riêng từ khóa công khai một cách nhanh chóng và hiệu quả, đồng thời tuân thủ các chuẩn an toàn hiện hành.

4.1. Ứng dụng trong hệ thống PKI

Các thuật toán backdoor được ứng dụng trong các module PKI-Token để tạo cặp khóa cho người dùng. Khi cần, cơ quan quản lý có thể khôi phục khóa riêng từ khóa công khai để đảm bảo an ninh cho cộng đồng. Các thuật toán này cũng giúp người dùng nhận biết và phòng chống backdoor trong các sản phẩm mật mã dạng hộp đen.

4.2. Đánh giá hiệu quả và tính bảo mật

Các thuật toán backdoor được đánh giá dựa trên độ phức tạp, khả năng khôi phục khóa riêng và tính khó bị phát hiện. Kết quả thử nghiệm cho thấy các thuật toán đều đáp ứng các yêu cầu về tính bảo mật và hiệu quả, đồng thời tuân thủ các chuẩn an toàn như FIPS 186-4.

Nội dung chính

Tổng quan luận án

Luận án tiến sĩ toán học với đề tài "Nghiên cứu, phát triển một số thuật toán sinh khóa RSA chứa backdoor" do nghiên cứu sinh Lê Quang Huy thực hiện dưới sự hướng dẫn khoa học của TS. Bạch Nhật Hồng và TS. Trần Duy Lai tại Viện Khoa học và Công nghệ Quân sự, chuyên ngành Cơ sở toán học cho tin học (mã số 9 46 01 10), bảo vệ năm 2018.

Tính cấp thiết và khoảng trống nghiên cứu

Hạ tầng khóa công khai (PKI) và hệ mật RSA đóng vai trò nòng cốt trong việc bảo vệ các giao dịch điện tử. Tuy nhiên, các kỹ thuật mã mật cũng bị các đối tượng tội phạm lợi dụng cho các hành vi vi phạm pháp luật:

• Hoạt động tội phạm trực tiếp: Phát tán mã độc tấn công vào các hệ thống hạ tầng trọng yếu như điều khiển nhà máy điện hạt nhân, vệ tinh, vũ khí quân sự, lưới điện, mạng viễn thông, Internet quốc gia, kiểm soát không lưu và giao thông công cộng.
• Hoạt động tội phạm gián tiếp: Giữ bí mật các kênh liên lạc phục vụ khủng bố, chế tạo vật liệu nổ, tống tiền, buôn bán vũ khí, ma túy và giết người.

Thực tế này dẫn đến nhu cầu khôi phục bản rõ từ bản mã mà không có khóa nhằm bảo đảm an ninh cộng đồng. Ba phương thức phá vỡ tính bảo mật hiện nay bao gồm:

1. Thu thập khóa qua con người (mua chuộc, đánh cắp): Mang tính ngẫu nhiên và cục bộ.
2. Thám mã truyền thống: Khó khả thi về thời gian, chi phí khi hệ mật hiện đại sử dụng chuẩn an toàn cao.
3. Sử dụng cơ chế backdoor (cửa hậu): Cho phép khôi phục khóa nhanh, tất định, chi phí thấp, khó bị phát hiện trong các thiết bị hộp đen.

Khoảng trống nghiên cứu được xác định là: Các thuật toán backdoor RSA công bố trước đây thường làm biến dạng phân phối tham số, làm giảm mạnh lực lượng khóa, phụ thuộc vào bộ nhớ tĩnh (NM) hoặc không đáp ứng các tiêu chuẩn an toàn hiện hành như FIPS 186-4.

Mục tiêu và nhiệm vụ nghiên cứu

Mục đích nghiên cứu: Tìm kiếm, xây dựng các thuật toán sinh khóa RSA chứa backdoor hiệu quả nhằm ứng dụng bảo đảm an ninh cho các hạ tầng PKI cụ thể.

Nhiệm vụ nghiên cứu gồm 4 nội dung:

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.
2. Tìm kiếm phương pháp tạo 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.
3. Đề xuất một số thuật toán sinh khóa chứa backdoor tuân thủ chuẩn an toàn xác định (chuẩn FIPS 186-4).
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.

Đối tượng và phạm vi nghiên cứu

• Đố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á thuật toán backdoor; phương pháp trích xuất, mã hóa, nhúng thông tin backdoor; phương pháp khôi phục khóa riêng từ khóa công khai chứa backdoor.
• Phạm vi nghiên cứu: Giới hạn trong bài toán sinh khóa và khôi phục khóa chứa backdoor trên hệ mật khóa công khai RSA.

---

Tổng quan tài liệu và vị trí của luận án

Luận án hệ thống hóa các nghiên cứu nền tảng về kênh ngầm và backdoor mật mã:

• Simmons (1984): Đặt nền móng cho khái niệm kênh ngầm (subliminal channel), cho phép trao đổi thông tin ẩn trong dữ liệu thông thường.
• Desmedt (1988): Khái quát hóa kênh ngầm thành khái niệm "lạm dụng hệ mật" (cryptosystem abuse).
• Young và Yung (1996, 1997, 2005): Sáng lập lĩnh vực Kleptography, giới thiệu mô hình SETUP (Secretly Embedded Trapdoor with Universal Protection) và các thuật toán backdoor bất đối xứng:
  • PAP (Pretty Awful Privacy, 1996): Nhúng số nguyên tố $p$ vào nửa bit cao của modulus $n$, mã hóa bằng RSA của người thiết kế.
  • PAP-2 (1997): Sử dụng hệ mật Elgamal và lược đồ rò rỉ dựa trên bộ nhớ không mất dữ liệu (NM).
  • Primes Private (PP, 2005): Dùng hệ mật Rabin, lưu trạng thái trong bộ nhớ tĩnh NM.
  • EC-SETUP (2005): Dùng trao đổi khóa đường cong Ellip ECDH.
• Anderson (1983) và Kaliski (1994): Thuật toán backdoor đối xứng Anderson dựa trên số bí mật cố định $A$, sau đó bị Kaliski phá vỡ tính bảo mật.
• Howgrave-Graham (2001): Nhúng thông tin nguyên tố $p$ vào số mũ công khai $e$, giải mã bằng phương pháp phân tích nhân tử đa thức modulo.
• Crépeau và Slakmon (2003): Đề xuất 4 thuật toán, trong đó thuật toán thứ tư (Hidden Prime Factor) nhúng một nửa số bit của $p$ vào các bit cao của $n$, sử dụng phương pháp Coppersmith để khôi phục khóa.
• Stefan Wüller, Marián Kühnel và Ulrike Meyer (2016): Thuật toán PHP nhúng nửa bit thấp của $p$ vào modulus $n$.
• Các công trình khác: Ting-Yu Lin và cộng sự (2006), Hung-Min Sun và cộng sự (2009), Constantinos Patsakis (2012) nghiên cứu kỹ thuật nhúng nhằm cải thiện tính phân phối và thời gian thực thi.
• Arboit (2008): Xây dựng khung lý thuyết Secure Backdoor với mô hình 3 thực thể và 7 tiêu chí đánh giá định lượng, định tính.

Thuật toán / Công trình	Tác giả (Năm)	Hệ mật người thiết kế	Vị trí nhúng	Nhược điểm / Hạn chế
Anderson	Anderson (1983), Kaliski (1994)	Tham số cố định $A$	$p, q$	Bị phá vỡ tính bảo mật
Howgrave-Graham	Howgrave-Graham (2001)	Hệ mật đối xứng	Số mũ $e$	Tính tương quan kém, $e$ bị cố định
Hidden Prime Factor	Crépeau - Slakmon (2003)	Hệ mật đối xứng	Bit cao của $n$	Tính tương quan tham số chưa đạt
PAP	Young - Yung (1996)	RSA	Bit cao của $n$	Độ an toàn chỉ đạt một nửa độ dài khóa
PAP-2 / PP	Young - Yung (1997, 2005)	Elgamal / Rabin	Tham số $n$	Phụ thuộc bộ nhớ tĩnh NM
EC-SETUP	Young - Yung (2005)	ECDH	Tham số $n$	Độ phức tạp tính toán lớn ($\ge$ bậc 2)
PHP	Stefan Wüller et al. (2016)	RSA	Bit thấp của $n$	Bảo mật trung bình, chưa chuẩn hóa
BD1, BD2, BD3 (Luận án)	Lê Quang Huy (2018)	Đối xứng / Bất đối xứng	Tham số $n$	Khắc phục NM, chuẩn FIPS 186-4 (P1, P2)

Khoảng trống luận án giải quyết: Xây dựng các thuật toán backdoor RSA bảo đảm tính bảo mật cao, không sử dụng bộ nhớ tĩnh NM, bảo đảm phân phối thống kê của khóa, và thỏa mãn chuẩn FIPS 186-4 theo cả hai điều kiện sinh số nguyên tố ngẫu nhiên ("P1") và sinh số nguyên tố có điều kiện ("P2").

---

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết và mô hình phân tích

Luận án áp dụng khung lý thuyết Secure Backdoor của Arboit (2008), phân tích mối quan hệ giữa 3 đối tượng trong hệ mật hộp đen:

• Người thiết kế (Designer): Cài đặt thuật toán sinh khóa trung thực $G_0$ hoặc thuật toán chứa backdoor $G_1$; có khả năng khôi phục khóa riêng $k_{priv}$ từ khóa công khai $k_{pub}$.
• Người dùng (User): Cung cấp tham số đầu vào, nhận cặp khóa đầu ra từ hộp đen, có thể đo đạc kênh bên nhằm phát hiện dấu hiệu bất thường.
• Kẻ tấn công (Attacker): Phân tích $k_{pub}$ của người dùng và thông tin kênh bên nhằm khôi phục $k_{priv}$ mà không có khóa bí mật của người thiết kế.

Cơ chế nhúng thông tin khóa riêng vào khóa công khai biểu diễn qua ánh xạ $F = M \circ E \circ I$:

• Hàm trích thông tin $I$: Trích xuất một phần khóa riêng sao cho $|I(k_{priv}^1)| < |k_{priv}^1|$.
• Hàm che giấu $E$: Mã hóa thông tin trích xuất bằng hệ mật của người thiết kế.
• Hàm nhúng $M$: Nhúng thông tin đã mã hóa vào khóa công khai $k_{pub}^* = M(E(I(k_{priv}^1)))$.

Khung đánh giá backdoor gồm 7 tiêu chí được lượng hóa theo 3 mức:

Tiêu chí	Tốt (Good)	Trung bình (Medium)	Kém / Thất bại (Poor)
1. Tính bảo mật	$l_E \ge l_{G1}$	$l_{G1} > l_E \ge l_{G1}/2$	$l_E < l_{G1}/2$
2. Tính hoàn chỉnh	$\forall k_{pub}: k_{priv} = F^{-1}(k_{pub})$	-	$\exists k_{pub}: k_{priv} \neq F^{-1}(k_{pub})$
3. Lực lượng khóa	$c \ge -1/2$	$-1/2 > c \ge -3/2$	$c < -3/2$
4. Tính phân phối	Khoảng cách thống kê $D_{G1} \approx 0$	$D_{G1} > 0$	-
5. Tính tương quan	Mọi thành phần không tương quan	Tương quan một phần	Các thành phần tương quan
6. Độ phức tạp	Tuyến tính ($a \le 1, c \le 1$)	Bậc dưới 2 ($1 < a < 2$ hoặc $1 < c < 2$)	Bậc từ 2 trở lên ($a \ge 2$ hoặc $c \ge 2$)
7. Bộ nhớ sử dụng	Không dùng VM, NM	Chỉ dùng bộ nhớ động VM	Dùng bộ nhớ tĩnh NM

Phương pháp phân tích nhân tử Coppersmith

Phương pháp Coppersmith (1996) dựa trên bổ đề Howgrave-Graham (1997) và thuật toán rút gọn cơ sở dàn LLL (Lenstra-Lenstra-Lovasz, 1982) hoặc thuật toán $L^2$ (Phong Nguyễn & Stehlé, 2004) để tìm nghiệm nguyên nhỏ của phương trình đa thức modulo một biến:

• Định lý Coppersmith cho bit cao: Cho $N = p \cdot q$. Nếu biết một nửa số bit cao ($1/4 \log_2 N$) của $p$, 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ý Coppersmith cho bit thấp: Nếu biết $p_0$ và $M$ thỏa mãn $p_0 = p \pmod M$ với $M \ge N^{1/4}$, có thể phân tích nhân tử $N$ trong thời gian đa thức tỷ lệ $\log^2 N$.

Hàm thực thi ký hiệu: $\text{CopperSmith}(n, m, p_1)$ với $n$ là modulus, $m = 2^{nlen/4}$ là ngưỡng, $p_1$ là giá trị các bit đã biết của $p$.

Chuẩn FIPS 186-4 và tương đương độ an toàn

Hệ mật RSA có $n = p \cdot q$, độ dài $nlen$. Số mũ công khai $e$ lẻ thỏa mãn $2^{16} < e < 2^{256}$, $\gcd(p-1, e) = 1$, $\gcd(q-1, e) = 1$. Số mũ riêng $d = e^{-1} \pmod{\text{LCM}(p-1, q-1)}$ thỏa mãn $2^{nlen/2} < d < \text{LCM}(p-1, q-1)$.

• Điều kiện "P1": $p, q$ là số nguyên tố ngẫu nhiên (chứng minh được hoặc có thể nguyên tố).
• Điều kiện "P2": $p, q$ sinh theo điều kiện bổ sung với các số nguyên tố phụ $p_1, p_2, q_1, q_2$ là nhân tử của $(p-1), (p+1), (q-1), (q+1)$.

Chiều dài khóa đối xứng	Hàm băm mật mã	Modulus RSA bất đối xứng ($nlen$)
56	112	384
64	128	494
80	160	768
112	224	1792
128	256	2304
256	512	10753

Tham số $nlen$	Chiều dài tối thiểu của $p_1, p_2, q_1, q_2$	Chiều dài tối đa ($p, q$ có thể nguyên tố)	Chiều dài tối đa ($p, q$ nguyên tố chứng minh được)
1024	$> 100\text{ bits } (> nlen/16)$	$< 496\text{ bits}$	$< 239\text{ bits } (= nlen/4 - 17)$
2048	$> 140\text{ bits } (> nlen/16)$	$< 1007\text{ bits}$	$< 494\text{ bits } (= nlen/4 - 18)$
3072	$> 170\text{ bits } (> nlen/16)$	$< 1518\text{ bits}$	$< 750\text{ bits } (= nlen/4 - 18)$

Phương pháp nghiên cứu thực tế

Luận án kết hợp phương pháp mô hình hóa toán học, mô phỏng thuật toán và thực nghiệm vật lý trên thiết bị phần cứng tự chế tạo mang tên T-Token.

---

Nội dung chính theo từng chương

Chương 1: Cơ sở về Backdoor trong sinh khóa

Chương 1 trình bày tổng quan các khái niệm, cơ sở toán học và thực trạng nghiên cứu backdoor trong hệ mật khóa công khai:

• Khái niệm và phân loại backdoor mật mã: Phân biệt backdoor đối xứng và bất đối xứng; làm rõ 3 đặc trưng cơ bản (không khác biệt đầu ra, tính bí mật, khả năng gây hại) và 3 tiêu chí của Schneier (khả năng phát hiện thấp, khả năng chối bỏ cao, thông đồng tối thiểu).
• Mô hình hóa hệ mật hộp đen và phân tích hình thức: Xây dựng cấu trúc hàm nhúng $F = M \circ E \circ I$ và xác lập hệ thống 7 tiêu chí đánh giá của Arboit.
• Cơ sở giải thuật phân tích nhân tử Coppersmith: Mô tả quy trình biến đổi bài toán tìm nghiệm modulo sang bài toán tìm nghiệm trên $\mathbb{Z}$ qua cơ sở dàn LLL và thuật toán $L^2$.
• Yêu cầu chuẩn FIPS 186-4: Phân lập chi tiết hai tập điều kiện tham số "P1" và "P2".
• Đánh giá các nghiên cứu tiền nhiệm: Chỉ ra hạn chế của các giải pháp PAP, PAP-2, PP, EC-SETUP, PHP, Anderson-Kaliski, Howgrave-Graham và Crépeau-Slakmon. Từ đó xác định hướng nghiên cứu trọng tâm của luận án: thiết kế thuật toán backdoor RSA không dùng bộ nhớ NM, bảo đảm tương quan tham số và tuân thủ FIPS 186-4.

Chương 2: Đề xuất thuật toán backdoor BD1, BD2

Chương 2 tập trung xây dựng hai thuật toán sinh khóa RSA chứa backdoor BD1 và BD2 đáp ứng điều kiện "P1" của chuẩn FIPS 186-4:

• Thuật toán BD1:
  • Ý tưởng: Trích xuất $1/2$ số bit của số nguyên tố $p$, mã hóa bằng hệ mật của người thiết kế và nhúng vào nửa số bit cao của modulus $n$.
  • Khôi phục khóa: Người thiết kế giải mã thông tin nhúng trong các bit cao của $n$ để lấy lại nửa số bit của $p$, sau đó gọi giải thuật Coppersmith để khôi phục hoàn chỉnh $p$ và tính toán khóa riêng $d$.
  • So sánh với PAP và PHP: Khắc phục sự suy giảm độ an toàn của hệ mật người thiết kế và loại bỏ hoàn toàn việc sử dụng bộ nhớ tĩnh NM.
• Thuật toán BD2:
  • Ý tưởng: Cải tiến kỹ thuật nhúng và cấu trúc hàm che giấu nhằm tối ưu hóa tính phân phối thống kê của modulus $n$, khắc phục các nhược điểm về tính tương quan của thuật toán Hidden Prime Factor (Crépeau & Slakmon).
• Thử nghiệm và đánh giá:
  • Cài đặt thực nghiệm trên thiết bị phần cứng T-Token.
  • Kết quả đo lường độ phức tạp tính toán và thời gian sinh khóa phù hợp với các phân tích lý thuyết, độ trễ sinh khóa không tạo ra sự khác biệt đáng kể so với thuật toán trung thực $G_0$.

Chương 3: Đề xuất thuật toán backdoor BD3

Chương 3 giải quyết bài toán cài đặt backdoor trong điều kiện sinh khóa ngặt nghèo hơn theo chuẩn an toàn:

• Thuật toán sinh khóa trung thực theo điều kiện "P2": Phân tích cấu trúc tạo số nguyên tố $p, q$ thông qua các số nguyên tố phụ $p_1, p_2, q_1, q_2$.
• Đề xuất thuật toán BD3:
  • Thiết kế cấu trúc nhúng thông tin backdoor tương thích với quy trình sinh số nguyên tố có điều kiện, bảo đảm các điều kiện chia hết và ràng buộc kích thước của các số nguyên tố phụ theo FIPS 186-4.
  • Thuật toán khôi phục khóa tích hợp giải thuật phân tích nhân tử Coppersmith cho các tham số sinh theo điều kiện "P2".
• Thử nghiệm và so sánh tổng hợp:
  • Cài đặt kiểm thử thuật toán BD3 trên thiết bị T-Token.
  • Đánh giá tổng hợp 03 thuật toán BD1, BD2, BD3 theo 7 tiêu chí của Arboit. Cả 3 thuật toán đều đạt mức đánh giá "Tốt" ở các tiêu chí quan trọng: tính bảo mật, tính hoàn chỉnh, tính phân phối, không sử dụng bộ nhớ NM và độ phức tạp tính toán ở mức tuyến tính/chấp nhận được.

---

Kết quả và những đóng góp mới

Đóng góp mới về lý luận

1. Hoàn thiện và áp dụng thành công mô hình đánh giá hình thức của Arboit kết hợp với giải thuật phân tích nhân tử Coppersmith vào bài toán thiết kế backdoor trên hệ mật RSA.
2. Đề xuất nguyên lý nhúng và khôi phục khóa tất định cho hệ mật RSA đáp ứng đầy đủ các ràng buộc khắt khe của chuẩn an toàn FIPS 186-4 (cả hai trường hợp điều kiện "P1" và "P2").

Đóng góp mới về thực tiễn

1. Xây dựng hoàn chỉnh 03 thuật toán sinh khóa RSA chứa backdoor:
   • BD1 và BD2: Tuân thủ điều kiện sinh khóa "P1".
   • BD3: Tuân thủ điều kiện sinh khóa có điều kiện "P2".
2. Cài đặt và thử nghiệm thành công các thuật toán trên thiết bị phần cứng thực tế T-Token, chứng minh tính khả thi, tốc độ thực thi tương đương thuật toán trung thực và khả năng che giấu cao đối với các phân tích thống kê, đo đạc kênh bên.
3. Cung cấp giải pháp kỹ thuật phục vụ các cơ quan quản lý nhà nước (quốc phòng, an ninh) trong việc kiểm soát an toàn thông tin hạ tầng PKI, đồng thời cung cấp cơ sở nhận diện nguy cơ backdoor trong các module mật mã hộp đen thương mại.

Kiến nghị và giải pháp đề xuất

• Ứng dụng trong quản lý PKI: Cho phép nhà cung cấp dịch vụ PKI khôi phục khóa riêng của người dùng khi có yêu cầu hợp pháp mà không cần duy trì cơ sở dữ liệu khóa riêng tập trung (vốn tiềm ẩn nguy cơ rò rỉ dữ liệu lớn).
• Tăng cường kiểm chuẩn thiết bị: Khuyến nghị các cơ quan chuyên trách an toàn thông tin xây dựng quy trình kiểm thử thống kê và phân tích kênh bên chuyên sâu đối với các thiết bị mật mã hộp đen nhập khẩu.

---

Hạn chế và hướng nghiên cứu tiếp

Hạn chế của nghiên cứu

• Phạm vi nghiên cứu mới tập trung vào hệ mật khóa công khai RSA, chưa mở rộng sang các hệ mật hiện đại khác đang cùng tồn tại song song trong hạ tầng PKI.
• Việc thực nghiệm trên thiết bị phần cứng T-Token mới giới hạn ở một số cấu hình độ dài khóa xác định theo chuẩn (1024, 2048, 3072 bits).

Hướng nghiên cứu tiếp theo

• Nghiên cứu cơ chế và thuật toán sinh khóa chứa backdoor trên các hệ mật khóa công khai dựa trên đường cong Elliptic (ECC/ECDSA).
• Nghiên cứu các phương pháp và công cụ tự động phát hiện backdoor mật mã cài đặt trong các sản phẩm phần cứng, phần mềm mật mã dạng hộp đen.

---

Giá trị tham khảo

Luận án là tài liệu tham khảo chuyên sâu cho các nhóm đối tượng:

• Nghiên cứu sinh, học viên cao học và giảng viên chuyên ngành Toán tin, Mật mã học, An toàn thông tin: Tham khảo phương pháp ứng dụng lý thuyết số, phương pháp Coppersmith, cơ sở dàn LLL và khung đánh giá Secure Backdoor.
• Kỹ sư phát triển phần cứng và phần mềm an toàn thông tin: Tham khảo quy trình hiện thực hóa thuật toán sinh khóa RSA tuân thủ chuẩn FIPS 186-4 trên thiết bị token bảo mật.
• Chuyên gia phân tích và đánh giá an toàn thông tin: Tham khảo các tiêu chí nhận diện, phát hiện kênh ngầm và lỗ hổng chủ ý trong các module mật mã hộp đen.
• Cơ quan quản lý nhà nước về cơ yếu, an ninh, quốc phòng: Tham khảo cơ sở khoa học để xây dựng chính sách quản lý, giám sát các sản phẩm mật mã thương mại và giải pháp bảo đảm an ninh cho các giao dịch điện tử quốc gia.

---

Câu hỏi thường gặp

1. Khung lý thuyết của Arboit đánh giá một thuật toán backdoor qua những tiêu chí nào?

Khung lý thuyết của Arboit (2008) đánh giá thuật toán backdoor qua 7 tiêu chí được phân thành 3 mức (Tốt, Trung bình, Kém/Thất bại):

1. Tính bảo mật ($l_E \ge l_{G1}$).
2. Tính hoàn chỉnh ($\forall k_{pub}, k_{priv} = F^{-1}(k_{pub})$).
3. Lực lượng khóa ($c \ge -1/2$).
4. Tính phân phối ($D_{G1} \approx 0$).
5. Tính tương quan (các thành phần khóa không tương quan).
6. Độ phức tạp tính toán (tuyến tính so với thuật toán trung thực).
7. Bộ nhớ sử dụng (không dùng bộ nhớ động VM và bộ nhớ tĩnh NM).

2. Sự khác biệt giữa điều kiện "P1" và "P2" theo chuẩn FIPS 186-4 trong luận án là gì?

• Điều kiện "P1": Quy định các số nguyên tố $p, q$ được sinh ngẫu nhiên (gồm số nguyên tố chứng minh được hoặc có thể nguyên tố), kết hợp các điều kiện về số mũ $e$ ($2^{16} < e < 2^{256}$), $\gcd(p-1, e) = 1$, $\gcd(q-1, e) = 1$ và cận dưới của $d$.
• Điều kiện "P2": Đòi hỏi ngặt nghèo hơn, yêu cầu $p, q$ phải thỏa mãn điều kiện bổ sung với 4 số nguyên tố phụ $p_1, p_2, q_1, q_2$ lần lượt là nhân tử của $(p-1), (p+1), (q-1), (q+1)$ với các ràng buộc kích thước bit xác định theo $nlen$.

3. Phương pháp phân tích nhân tử Coppersmith đóng vai trò gì trong các thuật toán backdoor đề xuất?

Phương pháp Coppersmith (sử dụng thuật toán rút gọn cơ sở dàn LLL/$L^2$) cho phép tìm nghiệm nguyên nhỏ của phương trình đa thức modulo trong thời gian đa thức. Trong các thuật toán BD1, BD2, BD3, phương pháp này đóng vai trò là công cụ cốt lõi giúp người thiết kế khôi phục lại toàn bộ số nguyên tố $p$ chỉ từ một nửa số bit (bit cao hoặc bit thấp) của $p$ được trích xuất và giải mã từ khóa công khai $n$.

4. Thuật toán BD1 có điểm gì khác biệt so với các thuật toán PAP và PHP trước đó?

• So với PAP (Young & Yung, 1996): BD1 không làm giảm độ an toàn của hệ mật người thiết kế xuống một nửa so với người dùng và không làm xáo trộn phân phối thống kê của $n$.
• So với PHP (Wüller et al., 2016): BD1 chuẩn hóa việc nhúng thông tin theo chuẩn FIPS 186-4, đồng thời cả hai thuật toán đều khắc phục triệt để việc sử dụng bộ nhớ tĩnh NM (vốn là nhược điểm dễ bị phát hiện của các dòng thuật toán PAP-2, PP).

5. Thử nghiệm thực tế của luận án được tiến hành trên thiết bị nào?

Các thuật toán sinh khóa và khôi phục khóa chứa backdoor BD1, BD2, BD3 được cài đặt và kiểm thử thực nghiệm trên thiết bị phần cứng chuyên dụng tự chế tạo mang tên T-Token, qua đó đo lường độ phức tạp tính toán, thời gian sinh khóa thực tế và đánh giá tính ẩn giấu của thuật toán trong môi trường hộp đen.

---

Kết luận

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" của tác giả Lê Quang Huy đã giải quyết bài toán thiết kế các thuật toán sinh khóa RSA chứa backdoor có khả năng khôi phục tất định nhưng vẫn bảo đảm tính ẩn giấu và tuân thủ chuẩn FIPS 186-4. Thông qua việc đề xuất 03 thuật toán BD1, BD2, BD3 dựa trên phương pháp phân tích nhân tử Coppersmith và đánh giá toàn diện theo khung lý thuyết Arboit, công trình đã chứng minh tính khả thi của giải pháp trên thiết bị phần cứng T-Token. Kết quả nghiên cứu mang lại giá trị thiết thực cho công tác bảo đảm an ninh hạ tầng PKI và nâng cao năng lực nhận diện, phòng chống nguy cơ cài cắm cửa hậu trong các thiết bị mật mã hộp đen.

Trích đoạn nội dung tài liệu

chương 1 nêu vấn đề cần nghiên cứu, giải quyết của luận án. Giới thiệu về backdoor mật mã 1. Khái niệm Backdoor Backdoor hay trapdoor, hiểu theo nghĩa chung nhất là “cửa hậu” hay lối vào phía sau. Đối với một hệ thống máy tính backdoor [40] có thể là: - Lối vào ẩn (bí mật) hoặc một cách vào hệ thống mà không phải thực hiện các thủ tục xác thực, hay vượt qua các kỹ thuật bảo vệ thông thường.

Backdoor ở dạng này thường đóng vai trò là một công cụ quản trị. - Là một (đoạn) chương trình độc hại được cài vào một hệ thống (đối tượng bị nhiễm, mục tiêu) để có thể truy nhập được vào hệ thống đó về sau nhằm thực hiện một hành động gây hại tới đối tượng bị nhiễm. Đặc trưng của loại backdoor này là không để lại dấu vết và khó phát hiện. Đối tượng của backdoor thường là một hệ thống máy tính, một hệ thống mật mã, một thuật toán, một hệ thống được bảo vệ vv.

Backdoor cho phép người dùng (hoặc kẻ tấn công) truy cập tới đối tượng bị nhiễm cục bộ hoặc từ xa. 8 Backdoor có thể có dạng một phần ẩn của một chương trình, một chương trình riêng biệt, hoặc có thể là một tính năng phần cứng. Thông thường, backdoor được lén lút cài đặt, nhưng trong một số trường hợp việc cài đặt backdoor là có chủ ý, được biết rộng rãi và có thể hợp pháp. Ví dụ nếu người dùng quên mật khẩu, các nhà sản xuất phải có một cách giúp người dùng lấy lại mật khẩu.

Backdoor mật mã Backdoor mật mã là một cơ chế thay đổi (làm yếu đi) thuật toán mật mã xác định, cung cấp cho người tạo backdoor một cách để phá vỡ các bản mã trong khoảng thời gian nhỏ hơn nhiều so với phương pháp thám mã tốt nhất (mục abstract trong [17]). Trong ứng dụng thực tế, sự hiện diện (tồn tại) của backdoor mật mã cho thấy các thông điệp dữ liệu đã mã mật (bản mã) dễ bị thám mã (phá vỡ) hơn. Đối tượng cụ thể của backdoor mật mã là các thuật toán, các giao thức mật mã và các bộ sinh số giả ngẫu nhiên. Mật mã được sử dụng trong Backdoor mật mã bao gồm hệ mật đối xứng và hệ mật bất đối xứng (mục 12.

Backdoor mật mã sau đây gọi tắt là backdoor và tùy theo hệ mật sử dụng nên được gọi là backdoor đối xứng hoặc backdoor bất đối xứng. Với backdoor đối xứng, người tìm thấy backdoor có thể sử dụng được nó. Backdoor bất đối xứng thì chỉ được sử dụng bởi kẻ tấn công (người thiết kế backdoor) ngay cả khi toàn bộ cài đặt của nó được công bố công khai. Backdoor có thể được cài đặt bằng phần mềm hoặc phần cứng hoặc kết hợp cả hai.

Sự phát triển của backdoor mật mã Backdoors mật mã là một trường hợp đặc biệt của kênh ngầm, được nghiên cứu từ những năm 1980 bởi Gus Simmons. Năm 1984, Simmons [54], đã giới thiệu khái niệm về kênh ngầm (vụng trộm), trong đó thông tin được trao đổi bí mật trong các thông điệp dữ liệu thông thường. Năm 1988, Desmedt [23] khái quát hóa về các kênh ngầm và gọi chúng là “lạm dụng” hệ mật, hay sử 9 dụng hệ mật theo cách mà nó không được chủ định. Ví dụ, khóa công khai RSA có thể được sử dụng để lưu trữ thông tin mà người tạo ra nó muốn truyền tải tới người khác.

Backdoor mật mã là một dạng đặc biệt của lạm dụng hệ mật, trong đó khóa công khai được tạo ra có khả năng cung cấp cho người thiết kế backdoor mật mã cách truy cập (tính toán) được khóa riêng tương ứng. Backdoor mật mã được đặt vào trong khóa công khai và hình thành kênh truyền từ người thiết kế (thông qua bộ tạo khóa) đến người dùng và quay trở lại người thiết kế. Đặc điểm của kênh truyền này là không sử dụng bất kỳ giao thức bổ sung nào vì khóa công khai được công bố rộng rãi trên kho (thư mục công cộng) chứa khóa. Ở góc độ khác backdoor mật mã được xem là một loại tấn công gián tiếp đặc biệt hay tấn công khóa yếu trong đó người thiết kế tạo ra các khóa chứa backdoor ẩn.

Nói chung, khóa yếu làm cho hệ mật hoạt động theo cách không mong muốn, khóa yếu tạo thành điểm yếu của hệ mật [14]. Quá trình phát triển của backdoor mật mã được minh họa tại hình 1. Các backdoor chưa công bố 1983 1988 1993 1996 1997 2001 2003 2005 2016 Simmons Desmedt Anderson Young Young Howgrave- Crepeau& Young Stefan &Yung &Yung Graham Slakmon &Yung Wüller Các kênh ngầm backdoors (Subliminal channels) Đã bị phá vỡ Đối xứng Bất đối xứng (broken) (symmetric) (asymmetric) Hình 1. Quá trình phát triển của backdoor mật mã [4] 1.

Đặc trưng chung của backdoor mật mã Các backdoor mật mã có một số đặc trưng chung sau (mục general conceps trong [17]): 10 - Không khác biệt đầu ra: khi so sánh đầu ra của hệ thống trung thực (không chứa backdoor) với đầu ra của hệ thống chứa backdoor, thì không có sự khác biệt nào. Nếu đầu ra có thể phân biệt được, thì có thể so sánh kết quả đầu ra của hệ thống nghi ngờ với hệ thống trung thực để phát hiện ra sự tồn tại của backdoor. - Bí mật: nhìn chung backdoor không làm giảm sự an toàn của hệ mật. Việc sử dụng backdoor chỉ dành riêng cho người tạo ra nó.

- Khả năng gây hại: backdoor cung cấp cách để người tạo ra backdoor có thể gây hại tới hệ mật. Đây là mục đích chính của backdoor mật mã. Bruce Schneier [13] mô tả ba tiêu chí bổ sung của backdoor mật mã: - Khả năng bị phát hiện thấp: Backdoor càng ít (lý tưởng nhất là không) gây ảnh hưởng đến hoạt động bình thường của hệ thống, thì càng tốt. Kích thước backdoor càng nhỏ càng tốt, lý tưởng nhất là giống như các đoạn mã thông thường.

- Khả năng chối bỏ cao: Nếu bị phát hiện, backdoor cần làm cho người khác tin rằng đó là một sai lầm, một lỗi, một sự vô tình hay một tai nạn. - Thông đồng tối thiểu: Càng nhiều người biết về backdoor, thì khả năng giữ bí mật càng thấp. Vì vậy, backdoor càng được ít người biết càng tốt. Nhìn chung một backdoor mật mã cần: thứ nhất cho phép kẻ tấn công phá vỡ sự an toàn của bản mã, thứ hai nó phải tương đối dễ sử dụng, thứ ba nó sẽ gây hại cho một số lượng lớn các bản mã.

Phạm vi sử dụng của backdoor mật mã 1. Backdoor trong các hệ mật, giao thức Hiện nay nhiều công trình nghiên cứu về backdoor trong các hệ mật, trong các giao thức mật mã và trong các bộ sinh số giả ngẫu nhiên đã được công 11 bố. Backdoor trong các hệ mật mã được nghiên cứu trên các hệ mật RSA [60], [63], [64], Elgamal [60], [61], EC [64] và được cài đặt trên các thuật toán như sinh khóa (key generation), mã mật (encryption), chữ ký số (digital signature), trao đổi khóa (key exchange). Backdoor trong các giao thức mật mã được nghiên cứu cho các giao thức SSL/TLS, SSH [22], biểu quyết điện tử (E-Vote scheme) [39], lược đồ chia sẻ (Secret Sharing Schemes) [51].

Backdoor trong các bộ sinh số giả ngẫu nhiên đã được cài đặt như: Dual_EC_DRBG [21]. Backdoor trong các hệ mật Mục tiêu của backdoor là gây hại tới bản mã (đánh cắp được thông tin bí mật) của người dùng với số lượng lớn và ổn định trong một thời gian xác định. Các thông tin bí mật này thường được mã mật bởi hệ mật đối xứng hoặc hệ mật bất đối xứng. Đối với hệ mật đối xứng, thời gian sử dụng khóa của người dùng thường là ngắn hay sử dụng tạm (khóa phiên) nên đối tượng của backdoor trong hệ mật đối xứng thường tập trung thuật toán mã mật (encryption backdoor).

Đối với hệ mật bất đối xứng, thời gian sử dụng khóa của người dùng thường ổn định và được duy trì trong một khoảng thời gian nhất định nên đối tượng của backdoor trong hệ mật bất đối xứng thường tập trung vào khóa của người dùng, cụ thể hơn là tập trung vào thuật toán sinh khóa (key generation backdoor). Một lĩnh vực nghiên cứu về backdoor bất đối xứng được khởi xướng lần đầu tiên năm 1996, bởi Adam Young và Moti Yung [59] gọi là Kleptography. Kleptography là lĩnh vực nghiên cứu về backdoor bất đối xứng cho các hệ mật và được xem là một kỹ thuật tấn công mật mã sử dụng các phương pháp mật mã. Các tấn công kleptographic đã được thiết kế cho các thuật toán sinh khóa RSA [59], [60], [61], [63], [64], trao đổi khóa Diffie-Hellman [59], thuật toán ký số DSA [59], và cho các giao thức mật mã như SSL, SSH [22].

Một số biện pháp, kỹ thuật phòng chống tấn công kleptographic được trình bày trong mục Counter Measures [6], [17]. Cơ sở về backdoor trong sinh cặp khóa 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 được trích dẫn trong [4]. Vấn đề khi cung cấp, sử dụng sản phẩm mật mã hộp đen Mật mã khóa công khai đang được ứng dụng rộng rãi, để đảm bảo an toàn cho các giao dịch điện tử. Các sản phẩm ứng dụng mật mã xuất hiện ngày càng nhiều theo hướng sản phẩm chuyên dụng và sản phẩm đa năng, dưới dạng module phần mềm hoặc thiết bị phần cứng.

Đặc trưng của các sản phẩm mật mã này là được cung cấp dưới dạng hộp đen (nhà sản xuất công bố đặc tả sản phẩm, khi sử dụng, người dùng chỉ truy nhập được đầu vào và đầu ra chứ không nắm được chi tiết cấu trúc và hoạt động nội tại). Khi được cài đặt ở dạng hộp đen, một hệ mật mã có thể được thiết kế để làm rò rỉ thông tin của người dùng, để nhà sản xuất (người thiết kế) có thể tấn công người dùng bằng cách khôi phục thông tin bí mật của người dùng từ đầu ra của hệ thống mật mã. Tấn công backdoor trong sinh khóa: Người dùng cuối nhận được một module mật mã hộp đen có dạng phần cứng hoặc phần mềm tạo ra cặp khóa công khai và riêng của một hệ mật xác định. Module tạo khóa này có chứa backdoor được thiết kế theo cách để người thiết kế có thể tính toán được khoá riêng từ khoá công khai tương ứng.

Những module sinh khóa như vậy được gọi là bộ sinh khóa có chứa backdoor và nó tạo ra các khóa ẩn yếu. Với lý do bảo vệ tài sản trí tuệ, các nhà sản xuất sản phẩm mật mã không muốn công bố cấu trúc và hoạt động nội tại (thiết kế, mã nguồn) của sản phẩm mật mã hộp đen.