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ố lược đồ chữ ký số dựa trên hệ mật Rabin và RSA", chuyên ngành Cơ sở Toán học cho Tin học (mã số: 9 46 01 10), do nghiên cứu sinh Hoàng Thị Mai thực hiện tại Viện Khoa học và Công nghệ quân sự - Bộ Quốc phòng, dưới sự hướng dẫn khoa học của TS. Nguyễn Hữu Mộng và TS. Ngô Trọng Mại (Hà Nội, 2019).

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

Theo Sách trắng Công nghệ thông tin và Truyền thông Việt Nam năm 2017, hạ tầng mạng Internet băng rộng cố định tại Việt Nam có mức giá cước xếp hạng 1/139 quốc gia và vùng lãnh thổ, với hơn 50 triệu người sử dụng Internet vào năm 2016. Về phương diện pháp lý, Luật Giao dịch điện tử năm 2005 đã thiết lập giá trị pháp lý cho các giao dịch điện tử tương đương với văn bản giấy truyền thống. Sau khi Trung tâm Chứng thực Chữ ký số Quốc gia được thành lập năm 2008, 09 doanh nghiệp đã được cấp phép cung cấp dịch vụ chứng thực chữ ký số công cộng; số lượng chứng thư số phát hành năm 2015 tăng 75% so với năm 2014.

Trong các ứng dụng thực tế của chính phủ điện tử và thương mại điện tử, tồn tại nhiều mô hình giao dịch mật mã có cấu trúc "nhiều-một" (chẳng hạn như các đầu mối tiếp nhận hồ sơ hành chính công, hệ thống kiểm tra tính hợp lệ của phiếu bầu cử trong bầu cử điện tử). Các hệ thống này có đặc điểm là nhiều thực thể gửi dữ liệu đến một thực thể xử lý trung tâm, dẫn đến tần suất xác thực danh tính diễn ra liên tục với khối lượng rất lớn. Do đó, yêu cầu kỹ thuật đặt ra là thuật toán kiểm tra chữ ký số phải có chi phí tính toán và thời gian thực thi thấp. Các lược đồ chữ ký số hiện hành như RSA, DSA và ECDSA khi kiểm tra đều đòi hỏi các phép tính lũy thừa hoặc nhân điểm trên đường cong elliptic với khối lượng tính toán đáng kể. Trong khi đó, lược đồ chữ ký Rabin có chi phí kiểm tra thấp nhất (chỉ cần một phép bình phương modulo) nhưng lại tồn tại hạn chế ở thuật toán tạo chữ ký: phải thực hiện nhiều phép tính ký hiệu Jacobi tốn kém và bị giới hạn ở số mũ kiểm tra $e = 2$ trên các số Blum. Đây chính là khoảng trống nghiên cứu mà luận án tập trung giải quyết.

2. Mục tiêu nghiên cứu

Mục tiêu nghiên cứu của luận án là xây dựng hệ chữ ký số khóa công khai có chi phí kiểm tra chữ ký thấp cho các ứng dụng sử dụng giao dịch mật mã kiểu "nhiều-một".

Để đạt được mục tiêu này, luận án triển khai bốn nội dung nghiên cứu chính:

  1. Nghiên cứu các hệ chữ ký số cơ bản dựa trên các bài toán khó của lý thuyết số: bài toán phân tích số nguyên (FP), bài toán logarithm rời rạc (DLP) và bài toán logarithm rời rạc trên đường cong elliptic (ECDLP).
  2. Lựa chọn lược đồ chữ ký Rabin và RSA làm cơ sở để đề xuất các cải tiến và thiết kế các lược đồ chữ ký số mới.
  3. Nghiên cứu cải tiến chữ ký số Rabin nhằm giảm chi phí thời gian của thuật toán ký, đồng thời đề xuất các lược đồ chữ ký phát triển từ dòng Rabin với số mũ kiểm tra $e = 3$.
  4. Nghiên cứu đề xuất các lược đồ chữ ký kết hợp nguyên lý thiết kế của chữ ký số Rabin và RSA (với số mũ $e = 3$), đồng thời chứng minh các lược đồ đề xuất đáp ứng yêu cầu chi phí thời gian cho các ứng dụng thực tiễn.

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

  • Đối tượng nghiên cứu: Cơ sở toán học lý thuyết số của các hệ mật mã và hệ chữ ký số khóa công khai; các lược đồ chữ ký số có chi phí kiểm tra thấp bao gồm RSA, Rabin, DSA, ECDSA.
  • Phạm vi nghiên cứu: Các cấu trúc đại số và giải thuật lý thuyết số trên vành số nguyên $\mathbb{Z}_n$ (với $n = pq$ là tích của hai số nguyên tố lớn), trường hữu hạn $\text{GF}(p)$, và nhóm điểm của đường cong elliptic trên trường hữu hạn $\mathbb{F}_q$; tập trung vào việc tối ưu hóa chi phí thời gian của các thuật toán tạo và kiểm tra chữ ký số trong các giao dịch mật mã "nhiều-một".

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

1. Các hướng nghiên cứu trước đây được điểm lại

Luận án đã tổng quan và phân tích có hệ thống các công trình nghiên cứu nền tảng và chuyên sâu trong lĩnh vực mật mã khóa công khai:

  • Các hệ mật mã và chữ ký số chuẩn: Diffie và Hellman (1976) phát minh khái niệm mật mã khóa công khai và giao thức trao đổi khóa; Rivest, Shamir và Adleman (1977) công bố hệ mật RSA; M. Rabin (1979) đề xuất hệ chữ ký số Rabin dựa trên bài toán phân tích số nguyên với số mũ $e = 2$; Elgamal (1984) đưa ra hệ mật và chữ ký số dựa trên bài toán logarithm rời rạc; Kravitz (1991) đề xuất thuật toán DSA, được NIST chuẩn hóa trong FIPS 186 (1994) dưới tên gọi Chuẩn chữ ký số (DSS); các tiêu chuẩn ECDSA được công bố trong ANSI X9.62 (1998/2005), FIPS PUB 186-4 (2000/2013), IEEE 1363-2000 và ISO/IEC 15946-2 (2002) với các cơ sở lý thuyết tổng hợp từ Darrel Hankerson, Alfred Menezes, Scott Vanstone (2004).
  • Các hướng nghiên cứu cải tiến lược đồ Rabin: H. C. Williams (1980) đưa ra lược đồ cải tiến Rabin-Williams (RW) giúp giảm số phép tính ký hiệu Jacobi từ 4 xuống còn 1 trong thuật toán ký, được đưa vào chuẩn ISO/IEC 9796; L. Kiesler (1989) kết hợp công thức tính căn bậc hai và ký hiệu Jacobi để cải tiến thuật toán ký Rabin; L. Harn (1994) nghiên cứu các biến thể của hệ mật Rabin; M. Schipani (2013) mở rộng lược đồ Rabin cho modulo $n$ là tích hai số nguyên tố bất kỳ (không cần là số Blum) thông qua việc sử dụng tổng Dedekind $s(m, n)$ thay cho ký hiệu Jacobi.
  • Các nghiên cứu mở rộng số mũ kiểm tra $e = 3$: H. C. Williams (1980), J. Khoo, Gregory J. Bird và Jennifer Seberry (1992), R. Scheidler (1998) đã nghiên cứu các lược đồ chữ ký với số mũ kiểm tra bậc ba; các kỹ thuật giải phương trình đồng dư bậc ba và khai căn bậc ba trên trường hữu hạn được phát triển từ thuật toán Tonelli-Shanks của Adleman, Manders, Miller (1977) và Nozomu Nishihara, Ryuichi Harasawa, Yutaka Sueyoshi, Aichi Kudo (2009).

2. Phân loại cấu trúc lược đồ chữ ký họ RSA/Rabin

Dựa trên mối quan hệ giữa số mũ kiểm tra $e$ và hàm Euler $\phi(n) = (p-1)(q-1)$ với $n = pq$, luận án phân chia các lược đồ chữ ký họ RSA thành ba loại hình:

  • Loại 1: Modulo $n = pq$ thỏa mãn $\gcd(e, \phi(n)) = 1$, tức là $e$ nguyên tố cùng nhau với cả $(p-1)$ và $(q-1)$ (đây là lược đồ RSA truyền thống).
  • Loại 2: Modulo $n = pq$ trong đó cả $(p-1)$ và $(q-1)$ đều là bội của $e$ (đây là lược đồ Rabin với $e = 2$, và các lược đồ mở rộng với $e = 3$).
  • Loại 3: Modulo $n = pq$ trong đó $(p-1)$ là bội của $e$, còn $(q-1)$ nguyên tố cùng nhau với $e$ (dạng kết hợp nguyên lý Rabin và RSA).

3. Khoảng trống nghiên cứu được lựa chọn giải quyết

Luận án tập trung giải quyết hai khoảng trống chính:

  1. Trong các lược đồ Loại 2 ($e = 2$ và $e = 3$): Loại bỏ hoàn toàn sự phụ thuộc vào việc tính toán ký hiệu Jacobi (vốn có độ phức tạp $O(k^2)$) hoặc tổng Dedekind trong thuật toán tạo chữ ký, giúp tăng tốc độ xử lý tạo chữ ký trong khi vẫn duy trì chi phí kiểm tra ở mức tối thiểu.
  2. Thiết kế và phát triển các lược đồ Loại 3 ($e = 3$): Kết hợp nguyên lý giải phương trình đồng dư của hệ Rabin trên modulo $p$ với tính chất nghịch đảo lũy thừa của hệ RSA trên modulo $q$, từ đó hình thành các lược đồ chữ ký số tất định và xác suất có chi phí kiểm tra thấp và thuật toán tạo chữ ký hiệu quả.

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

1. Cơ sở lý thuyết và các khái niệm toán học

Luận án sử dụng các công cụ và cấu trúc đại số của lý thuyết số và mật mã học:

  • Cấu trúc đại số: Vành số nguyên $\mathbb{Z}_n$, nhóm nhân các phần tử khả nghịch $\mathbb{Z}_n^*$, trường hữu hạn $\text{GF}(p)$, và nhóm điểm $E(\mathbb{F}_q)$ của đường cong elliptic dạng Weierstrass rút gọn: $y^2 = x^3 + ax + b$ với định thức $\Delta = -16(4a^3 + 27b) \neq 0$.
  • Thặng dư bậc hai và ký hiệu đại số: Khái niệm thặng dư bậc hai ($QR_p$) và không thặng dư bậc hai ($NQR_p$); ký hiệu Legendre $\left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod p$; ký hiệu Jacobi $\left(\frac{a}{m}\right) = \prod_{i=1}^t \left(\frac{a}{p_i}\right)^{e_i}$; luật bình phương tương hỗ $\left(\frac{m}{n}\right)\left(\frac{n}{m}\right) = (-1)^{(m-1)(n-1)/4}$.
  • Định lý phần dư Trung Hoa (CRT) và thuật toán Garner: Ánh xạ đẳng cấu $\alpha: \mathbb{Z}_n \to \mathbb{Z}_p \times \mathbb{Z}_q$ cho $a \mapsto (a_p, a_q)$, và công thức tái tạo Garner: $$x = \left(q \cdot (q^{-1} \bmod p) \cdot (x_p - x_q) \bmod p\right) \cdot q + x_q \pmod n$$
  • Khai căn bậc hai và bậc ba trên trường hữu hạn: Thuật toán Tonelli (1891) tìm căn bậc hai modulo số nguyên tố lẻ $p$; phương pháp Tonelli-Shanks mở rộng của Nishihara và cộng sự (2009) để giải phương trình đồng dư $x^3 \equiv a \pmod p$ cho các trường hợp: $p \not\equiv 1 \pmod 3$, $p \equiv 4 \pmod 9$, $p \equiv 7 \pmod 9$, và $p \equiv 1 \pmod 9$.
  • Bổ đề 2.2 của luận án: Với số nguyên tố $p = t \cdot k^s + 1$ thỏa mãn $\gcd(t, k) = 1$, đặt $u = -t^{-1} \bmod k$, giá trị $d = \frac{u(p-1) + k^s}{k^{s+1}}$ là một số nguyên. Áp dụng cho:
    • $k = 2, t \equiv 1 \pmod 2 \implies p \equiv 3 \pmod 4 \implies d = \frac{p+1}{4}$.
    • $k = 3, t \equiv 1 \pmod 3 \implies p \equiv 4 \pmod 9 \implies d = \frac{2p+1}{9}$.
    • $k = 3, t \equiv 2 \pmod 3 \implies p \equiv 7 \pmod 9 \implies d = \frac{p+2}{9}$.

2. Phương pháp nghiên cứu

Luận án kết hợp các phương pháp nghiên cứu toán học và khoa học máy tính:

  • Phương pháp suy diễn và chứng minh toán học: Xây dựng các bổ đề, mệnh đề và định lý để chứng minh tính đúng đắn, tính đầy đủ và tính an toàn của các thuật toán tạo/kiểm tra chữ ký số dựa trên độ khó của bài toán phân tích số nguyên (FP).
  • Phương pháp phân tích độ phức tạp thuật toán: Đánh giá chi phí thời gian chạy dựa trên số lượng thao tác bit (Bit Operations - BO) của các phép tính số học cơ bản trên $\mathbb{Z}_n$, sử dụng phương pháp nhân Karatsuba-Ofman $M(k) = O(k^{\ln 3/\ln 2})$ và phương pháp rút gọn Barrett.
  • Phương pháp phân tích định lượng so sánh: Thiết lập mô hình đánh giá thời gian kiểm tra giữa các hệ chữ ký số chuẩn (RSA, Rabin, DSA, ECDSA) dựa trên các bộ tham số đầu vào có cùng mức độ an toàn (Security level).

3. Nguồn tư liệu và dữ liệu nghiên cứu

  • Các văn bản tiêu chuẩn xử lý thông tin quốc tế: FIPS PUB 186-2, FIPS PUB 186-4 (DSS), NIST SP 800-56, ANSI X9.62, IEEE 1363-2000, ISO/IEC 9796, ISO/IEC 15946-2.
  • Tài liệu chuyên khảo toán học và mật mã học: Công trình của Alfred Menezes, Paul van Oorschot, Scott Vanstone (1996), Henri Cohen (1993), Darrel Hankerson (2004).
  • Dữ liệu thống kê thực tế: Báo cáo của Sách trắng Công nghệ thông tin và Truyền thông Việt Nam (2017) và số liệu của Trung tâm Chứng thực Chữ ký số Quốc gia.

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

Chương 1. Tổng quan về chữ ký số và hướng nghiên cứu phát triển

Chương 1 thiết lập các định nghĩa hình thức về một lược đồ chữ ký số gồm bộ 5 thành phần $(P, K, A, S, V)$, bao gồm tập thông báo $P$, tập khóa bí mật $K$, tập thuật toán ký $A$, tập chữ ký $S$, và tập thuật toán kiểm tra $V$, thỏa mãn các thuộc tính: tính đầy đủ, tính đúng đắn, tính khả thi và tính an toàn trước các kiểu tấn công giả mạo.

Chương này phân tích chi phí thời gian chạy của các phép tính số học trên vành $\mathbb{Z}_n$ (với số nguyên $k$-bit) được tổng hợp tại Bảng 1.1:

Phép toán Độ phức tạp Giải thuật tham chiếu
Cộng hoặc trừ hai số nguyên $k$-bit $O(k)$ Hankerson và cộng sự (2004)
Nhân hai số nguyên $k$-bit, ký hiệu $M(k)$ $O(k^{\ln 3/\ln 2})$ Karatsuba-Ofman
Nhân rút gọn theo modulo $k$-bit $\approx 3 \cdot M(k)$ Barrett
Ký hiệu Jacobi theo modulo $k$-bit $O(k^2)$ Henri Cohen (1993)
Tính nghịch đảo modulo $k$-bit (ký hiệu $I$) $O(k^2/\ln k)$ Henri Cohen (1993)
Chia hai số theo modulo $k$-bit $O(k^2/\ln k)$ Henri Cohen (1993)

Để so sánh chi phí kiểm tra giữa các lược đồ chữ ký số, luận án căn cứ trên bảng kích thước khóa tương đương theo các mức độ an toàn mật mã từ 80 đến 256 bits (Bảng 1.3):

Mức an toàn (bits) 80 (SKIPJACK) 112 (Triple-DES) 128 (AES-Small) 192 (AES-Medium) 256 (AES-Large)
Tham số DL $q$ 160 224 256 384 512
Tham số EC $n$ 160 224 256 384 512
Modulus RSA/Rabin $n$ 1024 2048 3072 8192 15360
Modulus DL $p$ 1024 2048 3072 8192 15360

Trọng tâm của Chương 1 là việc phát biểu và chứng minh Mệnh đề 1.1: "Trong toàn bộ các lược đồ chữ ký được ban hành thành chuẩn với cùng bộ tham số đầu vào cho bởi bảng 1.3 thì các lược đồ dòng Rabin là có chi phí kiểm tra thấp nhất."

Quá trình chứng minh Mệnh đề 1.1 so sánh chi phí thuật toán kiểm tra của Rabin ($T_{\text{RabinVer}}$) với từng lược đồ chuẩn:

  1. So với RSA: Thuật toán kiểm tra RSA với số mũ công khai $e \ge 3$ yêu cầu $T_{\text{RSAVer}} \approx \text{len}(e) + \text{wt}(e) - 2$ phép nhân/bình phương modulo. Trong khi đó, lược đồ Rabin có $e = 2$ nên chỉ cần đúng 1 phép bình phương modulo ($T_{\text{RSAVer}} > 1 = T_{\text{RabinVer}}$).
  2. So với DSA: Thuật toán kiểm tra DSA yêu cầu tính toán 2 phép lũy thừa modulo $p$, tiêu tốn xấp xỉ $T_{\text{DSAVer}} \approx 2(\text{len}(k) + \text{wt}(k) - 2)$ phép nhân hai số $k$-bit, cao hơn rất nhiều so với chi phí của Rabin (xấp xỉ 3 phép nhân hai số $k$-bit).
  3. So với ECDSA: Thuật toán kiểm tra ECDSA trên các đường cong elliptic với số nguyên tố NIST yêu cầu thực hiện các phép nhân vô hướng điểm, cho tổng chi phí $T_{\text{ECDSAVer}} \approx \frac{22}{3}\text{len}(p)M(\text{len}(p)) + 2I(\text{len}(p))$. Tỷ số chi phí giữa ECDSA và Rabin được tính theo công thức: $$\frac{T_{\text{ECDSAVer}}}{T_{\text{RabinVer}}} \approx \frac{22}{9}\text{len}(p)\left(\frac{\text{len}(p)}{\text{len}(n)}\right)^{\ln 3/\ln 2}$$

Kết quả định lượng tại Bảng 1.5 chứng minh thời gian kiểm tra của ECDSA lớn hơn Rabin từ 18,18 đến 65,98 lần:

$\text{len}(p)$ (bits) 160 224 256 384 512
$\text{len}(n)$ (bits) 1024 2048 3072 8192 15360
$(\text{len}(p)/\text{len}(n))^{\ln 3/\ln 2}$ 0,053 0,030 0,019 0,008 0,005
$T_{\text{ECDSAVer}} / T_{\text{RabinVer}}$ 65,980 52,408 38,906 23,421 18,182

Chương 2. Cải tiến và phát triển lược đồ chữ ký Rabin

Chương 2 tập trung nghiên cứu các lược đồ chữ ký Loại 2 (trong đó số mũ kiểm tra $e$ là ước của cả $p-1$ và $q-1$). Luận án đề xuất 03 lược đồ chữ ký số mới:

1. Lược đồ chữ ký RW0 (Cải tiến lược đồ Rabin-Williams)

  • Tham số hệ thống: Modulo $n = pq$ với $p, q \equiv 3 \pmod 4$ (số Blum), $c = q^{-1} \bmod p$. Tính trước các giá trị $d_p = 2^{(p+1)/4} \bmod p$, $d_q = 2^{(q+1)/4} \bmod q$, và tham số kết hợp: $$d = \left(c \cdot q \cdot (d_p - d_q) \bmod p\right) \cdot q + d_q \pmod n$$
  • Khóa: Khóa bí mật là $(n, p, q, c, d)$; khóa công khai là $n$.
  • Hàm định dạng: $f(R, H) = \text{Code}(H) + \text{Code}(\text{Hash}(R \parallel H)) \cdot 2^{\text{len}(H)}$.
  • Thuật toán tạo chữ ký (Thuật toán 2.3):
    1. Chọn ngẫu nhiên chuỗi $k$-bit $R$; tính $H = \text{Hash}(m)$ và $u = f(R, H)$; đặt $v = u \bmod n$.
    2. Tính $s_p = v^{(p+1)/4} \bmod p$ và $s_q = v^{(q+1)/4} \bmod q$.
    3. Tính $s = \left(c \cdot q \cdot (s_p - s_q) \bmod p\right) \cdot q + s_q \pmod n$.
    4. Nếu $s^2 \bmod n \notin {v, n - v}$ thì cập nhật $s = d \cdot s \bmod n$.
    5. Nếu $s > n/2$ thì đặt $s = n - s$. Trả về chữ ký $(R, s)$.
  • Thuật toán kiểm tra chữ ký (Thuật toán 2.4):
    1. Kiểm tra $s \in [0, n/2]$; tính $u = f(R, \text{Hash}(m))$ và $v = s^2 \bmod n$.
    2. Chấp nhận chữ ký nếu và chỉ nếu $u \in {v, n - v, 2v, n - 2v}$.
  • Đặc tính kỹ thuật: Dựa trên Bổ đề 2.3 và Mệnh đề 2.2, lược đồ RW0 chứng minh được tính đúng đắn và loại bỏ hoàn toàn việc tính toán ký hiệu Jacobi $\left(\frac{v}{n}\right)$ trong quá trình tạo chữ ký, khắc phục chi phí của lược đồ RW gốc.

2. Lược đồ chữ ký R0 (Cải tiến lược đồ Rabin gốc)

Lược đồ R0 tiếp tục áp dụng nguyên lý tránh tính ký hiệu Jacobi cho lược đồ Rabin 4 nghiệm. Thuật toán tạo chữ ký tính toán trực tiếp nghiệm căn bậc hai modulo $p$ và modulo $q$ rồi kết hợp qua CRT; thuật toán kiểm tra mở rộng tập kiểm tra tương ứng với việc dịch chuyển nghiệm, giúp giảm thiểu thời gian ký mà chi phí kiểm tra tăng lên không đáng kể.

3. Lược đồ chữ ký PCRS (Probabilistic Cubic Rabin Signature)

  • Phát triển dòng Rabin với số mũ kiểm tra $e = 3$, sử dụng các số nguyên tố $p, q \equiv 1 \pmod 3$ (tức 3 là ước của cả $p-1$ và $q-1$).
  • Lược đồ mang tính xác suất thông qua việc chèn mầm ngẫu nhiên. Thuật toán kiểm tra chỉ yêu cầu một phép nâng lên lũy thừa 3 modulo $n$ ($s^3 \bmod n$). Thuật toán tạo chữ ký khai thác thuật toán Tonelli-Shanks khai căn bậc ba trên $\text{GF}(p)$ và $\text{GF}(q)$, đảm bảo hiệu quả thời gian và tính an toàn tương đương bài toán phân tích số Blum bậc ba.

Chương 3. Lược đồ chữ ký kết hợp Rabin và RSA

Chương 3 nghiên cứu thiết kế các lược đồ chữ ký thuộc Loại 3 với số mũ kiểm tra $e = 3$. Cấu trúc hệ thống chọn hai số nguyên tố $p$ và $q$ thỏa mãn: $$p \equiv 1 \pmod 3 \quad (\text{tức } 3 \mid (p-1)) \quad \text{và} \quad q \equiv 2 \pmod 3 \quad (\text{tức } \gcd(3, q-1) = 1)$$

1. Cơ sở toán học cho trường hợp $e = 3$

  • Với modulo $p$: Phương trình $x^3 \equiv a \pmod p$ có nghiệm khi và chỉ khi $a^{(p-1)/3} \equiv 1 \pmod p$. Khi có nghiệm, phương trình có đúng 3 nghiệm phân biệt trong $\text{GF}(p)$.
  • Với modulo $q$: Do $\gcd(3, q-1) = 1$, số 3 khả nghịch modulo $q-1$. Tồn tại duy nhất khóa bí mật $d_q = 3^{-1} \bmod (q-1)$, và phương trình $x^3 \equiv a \pmod q$ luôn có nghiệm duy nhất với mọi $a \in \mathbb{Z}_q$, tính bởi $x = a^{d_q} \bmod q$.
  • Luận án phân tích hàm $CR$ và chứng minh mối liên hệ tương đương giữa bài toán giải phương trình đồng dư bậc 3 trên $\mathbb{Z}_n$ với bài toán phân tích $n$ thành thừa số nguyên tố.

2. Các lược đồ đề xuất

  • Lược đồ tất định DRSA-RABIN3: Sử dụng hàm chuyển đổi định dạng tất định để ánh xạ thông báo $m$ vào không gian thặng dư bậc ba modulo $p$. Người ký sử dụng thuật toán khai căn bậc ba modulo $p$ kết hợp phép lũy thừa $d_q$ modulo $q$, sau đó tổng hợp nghiệm $s$ trên $\mathbb{Z}_n$ qua định lý CRT. Người kiểm tra chỉ cần thực hiện một phép tính $s^3 \bmod n$ và so sánh với giá trị định dạng thông báo.
  • Lược đồ xác suất PRSA-RABIN3: Bổ sung tham số ngẫu nhiên $R$ trong quá trình định dạng thông báo nhằm loại bỏ tính tất định, nâng cao khả năng kháng các cuộc tấn công chọn bản rõ/chọn thông báo.
  • Các phiên bản cải tiến của DRSA-Rabin3 và PRSA-Rabin3: Luận án áp dụng các kỹ thuật tính toán trước (pre-computation) các tham số kết hợp qua CRT tương tự kỹ thuật trong RW0, giúp rút gọn các phép nhân lớn trong thuật toán ký, giảm thiểu thời gian xử lý của người ký và tối ưu hóa kích thước chữ ký truyền thông.

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

1. Đóng góp mới về mặt lý luận khoa học

  1. Chứng minh Mệnh đề 1.1: Xác lập căn cứ toán học định lượng khẳng định trong các lược đồ chữ ký số được chuẩn hóa quốc tế có cùng mức độ an toàn (RSA, Rabin, DSA, ECDSA), các lược đồ thuộc dòng Rabin có chi phí kiểm tra thấp nhất.
  2. Kỹ thuật triệt tiêu phép tính Jacobi: Đề xuất giải pháp loại bỏ hoàn toàn việc tính toán ký hiệu Jacobi trong thuật toán tạo chữ ký của dòng Rabin (thể hiện qua lược đồ RW0 và R0), giải quyết triệt để nút thắt cổ chai về độ phức tạp tính toán $O(k^2)$ mà không làm suy giảm độ an toàn của hệ mật.
  3. Mở rộng lược đồ dòng Rabin với số mũ $e = 3$ (Loại 2): Xây dựng thành công lược đồ chữ ký xác suất PCRS với $e = 3$ khi $3 \mid \gcd(p-1, q-1)$, hoàn thiện quy trình khai căn bậc ba hiệu quả bằng phương pháp Tonelli-Shanks trên trường hữu hạn.
  4. Đề xuất nguyên lý kết hợp Rabin và RSA (Loại 3): Thiết lập mô hình chữ ký kết hợp giữa bài toán khai căn bậc ba (trên $p \equiv 1 \pmod 3$) và lũy thừa RSA (trên $q \equiv 2 \pmod 3$), hình thành các lược đồ DRSA-RABIN3 và PRSA-RABIN3 cùng các bản cải tiến.

2. Ý nghĩa và giải pháp thực tiễn

  • Các lược đồ chữ ký số đề xuất có tốc độ kiểm tra cực nhanh (chỉ cần một phép tính bình phương hoặc lũy thừa ba modulo $n$), đặc biệt thích hợp để triển khai trong các hệ thống dịch vụ công trực tuyến, cổng tiếp nhận hồ sơ hành chính điện tử, hệ thống kiểm phiếu bầu cử điện tử và các máy chủ xác thực chứng thực chữ ký số công cộng (nơi xử lý đồng thời hàng triệu yêu cầu xác thực mỗi ngày).

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

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

Theo phạm vi nghiên cứu được trình bày trong văn bản:

  • Các cấu trúc toán học và lược đồ đề xuất trong luận án tập trung chủ yếu vào các trường hợp số mũ kiểm tra nhỏ ($e = 2$ và $e = 3$).
  • Modulo $n$ được khảo sát dưới dạng tích của hai số nguyên tố lớn ($n = pq$), chưa khảo sát các cấu trúc modulo đa nguyên tố (multi-prime $n = pqr$) hoặc modulo dạng lũy thừa ($n = p^2 q$).

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

Luận án xác định hai hướng phát triển tiếp theo:

  1. Tiếp tục nghiên cứu mở rộng nguyên lý kết hợp và thiết kế các lược đồ chữ ký số cho trường hợp số mũ kiểm tra $e$ là một số nguyên tố tổng quát ($e > 3$).
  2. Nghiên cứu thực nghiệm, đánh giá hiệu năng chi tiết và triển khai ứng dụng các lược đồ chữ ký đề xuất trên các thiết bị phần cứng có tài nguyên tính toán hạn chế (như thẻ thông minh - smart card, vi điều khiển và thiết bị đầu cuối IoT).

Giá trị tham khảo

Luận án là tài liệu tham khảo chuyên khảo có giá trị đối với:

  • Nghiên cứu sinh, học viên cao học và giảng viên: Chuyên ngành Cơ sở Toán học cho Tin học, Toán ứng dụng, Mật mã học và An toàn thông tin; cung cấp phương pháp luận chặt chẽ trong việc phân tích chi phí thuật toán số học, chứng minh tính đúng đắn và độ an toàn của hệ mật khóa công khai.
  • Kỹ sư và chuyên gia an toàn thông tin: Các kỹ sư thiết kế hệ thống tại các tổ chức cung cấp dịch vụ chứng thực chữ ký số (CA), các cơ quan phát triển chính phủ điện tử và doanh nghiệp thương mại điện tử; phần đáng tham khảo nhất là kỹ thuật thiết kế giải thuật ký RW0/R0 và DRSA-RABIN3 nhằm tối ưu hóa năng lực phục vụ của máy chủ xác thực.

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

1. Tại sao các lược đồ dòng Rabin lại có chi phí kiểm tra chữ ký thấp hơn so với RSA, DSA và ECDSA?

Theo chứng minh Mệnh đề 1.1 trong luận án:

  • So với RSA: RSA yêu cầu số mũ $e \ge 3$ nguyên tố cùng nhau với $\phi(n)$, dẫn đến chi phí kiểm tra gồm $\text{len}(e) + \text{wt}(e) - 2$ phép nhân/bình phương modulo. Lược đồ Rabin có $e = 2$ nên chỉ cần đúng 1 phép bình phương modulo.
  • So với DSA: DSA yêu cầu tính 2 phép lũy thừa modulo $p$, tiêu tốn khoảng $2(\text{len}(k) + \text{wt}(k) - 2)$ phép nhân hai số $k$-bit, trong khi Rabin chỉ tốn xấp xỉ 3 phép nhân hai số $k$-bit.
  • So với ECDSA: ECDSA đòi hỏi các phép nhân vô hướng điểm trên đường cong elliptic với chi phí xấp xỉ $\frac{22}{3}\text{len}(p)M(\text{len}(p))$, làm cho thời gian kiểm tra của ECDSA cao hơn Rabin từ 18,18 lần (ở mức an toàn 256 bits) đến 65,98 lần (ở mức an toàn 80 bits).

2. Kỹ thuật cải tiến chính của lược đồ RW0 so với lược đồ Rabin-Williams (RW) truyền thống là gì?

Trong lược đồ RW truyền thống của Williams (1980), thuật toán tạo chữ ký bắt buộc phải thực hiện 1 phép tính ký hiệu Jacobi $\left(\frac{v}{n}\right)$ với độ phức tạp $O(k^2)$ để xác định tính chính phương của thông báo. Lược đồ RW0 của luận án tính toán trước tham số $d$ trong khóa bí mật và thực hiện tính toán nghiệm căn $s_p, s_q$ trực tiếp qua CRT. Nếu điều kiện bình phương kiểm tra không thỏa mãn ${v, n-v}$, thuật toán chỉ cần thực hiện phép nhân $s = d \cdot s \bmod n$, qua đó loại bỏ hoàn toàn phép tính ký hiệu Jacobi khi ký.

3. Ba loại cấu trúc của các lược đồ họ RSA được phân loại trong luận án khác nhau như thế nào?

  • Loại 1: Modulo $n = pq$ có $\gcd(e, (p-1)(q-1)) = 1$ (lược đồ RSA kinh điển).
  • Loại 2: Modulo $n = pq$ có cả $(p-1)$ và $(q-1)$ đều chia hết cho $e$ (lược đồ Rabin với $e = 2$ và lược đồ PCRS với $e = 3$).
  • Loại 3: Modulo $n = pq$ có $(p-1)$ chia hết cho $e$ nhưng $\gcd(e, q-1) = 1$ (lược đồ kết hợp DRSA-RABIN3 và PRSA-RABIN3 với $e = 3$).

4. Thuật toán khai căn bậc ba modulo số nguyên tố $p$ xử lý các trường hợp của $p$ như thế nào?

Thuật toán Tonelli-Shanks mở rộng trong luận án phân chia thành 4 trường hợp để giải phương trình $x^3 \equiv a \pmod p$:

  1. $p \not\equiv 1 \pmod 3$: Nghiệm duy nhất $r = a^{3^{-1} \bmod (p-1)} \bmod p$.
  2. $p \equiv 4 \pmod 9$: Nghiệm $r = a^{(2p+1)/9} \bmod p$.
  3. $p \equiv 7 \pmod 9$: Nghiệm $r = a^{(p+2)/9} \bmod p$.
  4. $p \equiv 1 \pmod 9$: Biểu diễn $p-1 = 3^s \cdot t$ (với $\gcd(3, t) = 1$), tìm căn nguyên thủy bậc ba của đơn vị $g = d^{(p-1)/3} \bmod p \neq 1$, sau đó dùng vòng lặp xác định số mũ $m$ để triệt tiêu sai số và tính nghiệm $r = a^e D^{m/3} \bmod p$.

5. Nguyên lý hoạt động của lược đồ kết hợp DRSA-RABIN3 ở Chương 3 là gì?

Lược đồ DRSA-RABIN3 kết hợp hai cơ chế trên hai nhân tử nguyên tố của $n = pq$: trên trường $\text{GF}(p)$ (với $3 \mid (p-1)$), hệ thống sử dụng thuật toán khai căn bậc ba; trên trường $\text{GF}(q)$ (với $\gcd(3, q-1) = 1$), hệ thống sử dụng phép lũy thừa RSA với số mũ bí mật $d_q = 3^{-1} \bmod (q-1)$. Sau đó, định lý phần dư Trung Hoa (CRT) được dùng để ghép hai kết quả thành chữ ký $s$ trên $\mathbb{Z}_n$, cho phép kiểm tra tính hợp lệ bằng duy nhất một phép tính $s^3 \bmod n$.

Kết luận

Luận án đã giải quyết bài toán tối ưu hóa chi phí thời gian kiểm tra chữ ký số phục vụ các mô hình giao dịch mật mã "nhiều-một" thông qua việc nghiên cứu phát triển các hệ chữ ký số dựa trên hệ mật Rabin và RSA. Bằng các phương pháp toán học chặt chẽ, tác giả đã chứng minh ưu thế về tốc độ kiểm tra của dòng Rabin so với các chuẩn quốc tế RSA, DSA và ECDSA, đồng thời đề xuất thành công các lược đồ chữ ký mới (RW0, R0, PCRS, DRSA-RABIN3, PRSA-RABIN3) giúp loại bỏ phép tính ký hiệu Jacobi và tối ưu hóa quá trình tạo chữ ký. Các kết quả đạt được của luận án đóng góp cả về mặt lý thuyết nền tảng trong chuyên ngành Cơ sở Toán học cho Tin học lẫn khả năng ứng dụng thực tiễn trong xây dựng hạ tầng chính phủ điện tử và thương mại điện tử.