Tổng quan luận án

Luận án tiến sĩ toán học với nhan đề "New Results in Group Theoretic Cryptology" (tạm dịch: Các kết quả mới trong mật mã học lý thuyết nhóm) do tác giả Michal Sramka thực hiện dưới sự hướng dẫn của Giáo sư Spyros Magliveras tại Khoa Khoa học Toán học thuộc Trường Khoa học Charles E. Schmidt, Đại học Florida Atlantic (Florida Atlantic University - FAU), Hoa Kỳ, hoàn thành và bảo vệ vào tháng 12 năm 2006.

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

Kể từ khi Peter Shor công bố thuật toán lượng tử năm 1994 giải quyết bài toán phân tích thừa số nguyên và bài toán logarit rời rạc trong thời gian đa thức, nền tảng an toàn của các hệ mật mã khóa công khai truyền thống như RSA, Diffie-Hellman và ElGamal đứng trước nguy cơ bị phá vỡ hoàn toàn khi máy tính lượng tử xuất hiện. Tình hình này đặt ra nhu cầu cấp thiết trong việc phát triển các nguyên thủy mật mã mới có khả năng tồn tại trong kỷ nguyên hậu lượng tử (post-quantum era). Một hướng tiếp cận nhận được nhiều sự quan tâm là khai thác các bài toán khó xuất phát từ lý thuyết nhóm (Group Theoretic Cryptology), dựa trên giả định rằng nhiều bài toán quyết định và bài toán tính toán trong cấu trúc nhóm không thể giải quyết hiệu quả bằng máy tính lượng tử, thậm chí một số bài toán quyết định là không thể giải được về mặt thuật toán (như bài toán từ do Max Dehn đặt ra năm 1911).

Tuy nhiên, nhiều đề xuất mở rộng bài toán logarit rời rạc hoặc xây dựng hệ mật dựa trên lý thuyết nhóm tổ hợp xuất hiện trong giai đoạn này bộc lộ những thiếu sót nghiêm trọng về mặt chứng minh an toàn, đánh giá sai độ phức tạp tính toán thực tế hoặc thực chất chỉ là các biến thể tầm thường của những hệ mật cổ điển đã biết. Khoảng trống nghiên cứu mà luận án tập trung giải quyết bao gồm:

  1. Thiếu sót trong việc đánh giá độ an toàn và độ phức tạp tính toán thực tế của các đề xuất mở rộng bài toán logarit rời rạc gần đây (cụ thể là lược đồ mã hóa 2DL của Kashyap và cộng sự năm 2006, cùng lược đồ trao đổi khóa ma trận của Stickel năm 2005).
  2. Sự mơ hồ về mặt toán học và lỗ hổng cấu trúc trong ý tưởng hệ mật khóa công khai dựa trên lý thuyết nhóm tổ hợp của Wagner - Magyarik (1984).
  3. Nhu cầu thiết lập một định nghĩa hình thức, chặt chẽ về việc tổng quát hóa bài toán logarit rời rạc cho các nhóm hữu hạn sinh phi giao hoán, từ đó xây dựng các hàm một chiều (One-Way Functions - OWF), bộ sinh số giả ngẫu nhiên và lược đồ chữ ký có chứng minh an toàn hình thức.

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

Luận án xác định các mục tiêu cụ thể sau:

  1. Nghiên cứu và thám mã các lược đồ mật mã lý thuyết nhóm đã công bố để chỉ ra các điểm yếu cấu trúc, làm rõ độ phức tạp tính toán thực tế và đề xuất thuật toán phá mã tối ưu.
  2. Phân tích, phê phán và tái cấu trúc hệ mật mã khóa công khai kiểu Wagner - Magyarik dựa trên lý thuyết nhóm tổ hợp, giải quyết các câu hỏi thiết kế còn bỏ ngỏ thông qua việc ứng dụng nhóm biến đổi biểu diễn hữu hạn tác động lên xâu ký tự.
  3. Xây dựng định nghĩa tổng quát hóa bài toán logarit rời rạc (DLP) cho các nhóm hữu hạn bất kỳ (đặc biệt là nhóm phi giao hoán).
  4. Thiết lập mô hình xây dựng hàm một chiều (OWF), bộ sinh số giả ngẫu nhiên và lược đồ chữ ký có chứng minh an toàn dựa trên độ khó của bài toán phân tích phần tử trong nhóm xạ ảnh tuyến tính đặc biệt $PSL_2(\mathbb{F}_q)$.

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

  • Đối tượng nghiên cứu: Các cấu trúc đại số trừu tượng (nhóm cyclic hữu hạn, nhóm ma trận tuyến tính tổng quát $GL_n(F)$, nhóm biểu diễn hữu hạn, nhóm biến đổi, nhóm xạ ảnh tuyến tính đặc biệt $PSL_2(\mathbb{F}_q)$); các bài toán tính toán và quyết định trên nhóm (DLP, GDLP, bài toán từ, bài toán lựa chọn từ, bài toán hành động chung, bài toán phân tích phần tử); các giao thức mật mã khóa công khai, trao đổi khóa và lược đồ chữ ký số.
  • Phạm vi không gian và thời gian: Luận án thực hiện trong khuôn khổ chương trình nghiên cứu toán học và mật mã học tại Đại học Florida Atlantic, bảo vệ năm 2006, sử dụng các công bố học thuật tính đến năm 2006.
  • Phạm vi phương pháp: Kết hợp phân tích đại số lý thuyết, chứng minh quy giảm độ phức tạp tính toán (reduction proofs) và kiểm chứng thực nghiệm bằng lập trình song song trên cụm máy tính hiệu năng cao BOCA4 Beowulf.

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

Luận án điểm lại và kế thừa hệ thống tư liệu học thuật từ nhiều nhánh nghiên cứu liên quan trực tiếp đến lý thuyết nhóm và mật mã học:

Các hướng nghiên cứu trước được trích dẫn

  1. Mật mã học khóa công khai cổ điển và độ phức tạp lượng tử:
    • P. Shor (1994) [29]: Công bố thuật toán lượng tử giải bài toán phân tích thừa số và logarit rời rạc trong thời gian đa thức.
    • W. Diffie và M. Hellman (1976) [7]: Đề xuất giao thức trao đổi khóa Diffie-Hellman.
    • T. ElGamal (1985) [9]: Đề xuất hệ mật mã khóa công khai ElGamal dựa trên bài toán logarit rời rạc.
    • D. Shank (1971) [34]: Đề xuất thuật toán Baby step - Giant step giải bài toán logarit rời rạc với độ phức tạp $O(\sqrt{n})$.
    • A. Odlyzko (1985, 2000) [24, 25] và M. Teske (2001) [30]: Khảo sát toàn diện về các thuật toán và độ phức tạp của bài toán logarit rời rạc.
  2. Lý thuyết chữ ký logarit và phủ trên nhóm hữu hạn:
    • S. Magliveras (2002, 2004) [19, 20]: Phát triển lý thuyết về chữ ký logarit (logarithmic signatures) và phủ (covers) trên nhóm hữu hạn, phân biệt phủ thuần (tame covers) và phủ hoang dã (wild covers) ứng dụng trong mật mã học.
  3. Lý thuyết nhóm tổ hợp và bài toán từ:
    • M. Dehn (1911): Đặt ra bài toán từ (word problem) cho nhóm biểu diễn hữu hạn.
    • P. S. Novikov (1955) và W. W. Boone (1959): Chứng minh sự tồn tại của các nhóm biểu diễn hữu hạn có bài toán từ không thể khử được bằng thuật toán (undecidable).
    • N. R. Wagner và M. R. Magyarik (1984) [37]: Đề xuất hệ mật mã khóa công khai đầu tiên dựa trên bài toán từ trong lý thuyết nhóm tổ hợp.
    • J. C. Birget và cộng sự (1996, 2000, 2004) [1, 2, 3]: Nghiên cứu cấu trúc nhóm Higman-Thompson $G_{3,1}$, chứng minh tính chất $coNP$-đầy đủ của bài toán từ và mô phỏng mạch logic bằng phần tử nhóm.
  4. Các đề xuất mở rộng bài toán logarit rời rạc gần thời điểm nghiên cứu:
    • S. K. Kashyap, B. K. Sharma, A. Banerjee (2006) [16]: Đề xuất bài toán 2DL trên hai phần tử sinh và hệ mã hóa bất đối xứng tương ứng.
    • E. Stickel (2005) [33]: Đề xuất giao thức trao đổi khóa dựa trên hai phần tử không giao hoán trong nhóm ma trận với số mũ Mersenne.
  5. Cơ sở lý thuyết độ phức tạp và hàm một chiều:
    • O. Goldreich (2001, 2004) [12, 13]: Giáo trình nền tảng về mật mã học và độ phức tạp tính toán.
    • J. Håstad, R. Impagliazzo, L. A. Levin, M. Luby (1999) [15]: Chứng minh sự tương đương giữa hàm một chiều và bộ sinh số giả ngẫu nhiên an toàn.
    • J. Rompel (1990) [27]: Chứng minh sự tồn tại của lược đồ chữ ký số an toàn từ hàm một chiều.

Khoảng trống luận án lựa chọn giải quyết

Luận án định vị vị trí học thuật thông qua việc chỉ rõ:

  • Đề xuất 2DL của Kashyap và cộng sự là không xác định chặt chẽ, thực chất hoàn toàn tương đương với hệ mật ElGamal kinh điển và có thể bị phá chỉ bằng một phép tính logarit rời rạc đơn.
  • Ước tính độ phức tạp $(2^n-1)^2$ của Stickel cho giao thức trao đổi khóa ma trận là không chính xác; luận án chứng minh chỉ cần không gian tìm kiếm kích thước $2^n-1$ và thời gian $O(n_1 \log n_1)$ để bẻ khóa hoàn toàn.
  • Ý tưởng của Wagner - Magyarik không dựa trên bài toán từ như nhóm tác giả tuyên bố, mà dựa trên "bài toán lựa chọn từ" (word choice problem) thuộc lớp $NP \cap coNP$; luận án khắc phục sự mơ hồ này bằng việc tích hợp nhóm biến đổi Higman-Thompson.
  • Xây dựng một khung hình thức hóa chuẩn xác cho DLP tổng quát trên nhóm phi giao hoán để tạo hàm một chiều có chứng minh an toàn.

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

Cơ sở lý thuyết và khung phân tích

Luận án vận dụng bốn trụ cột lý thuyết toán học:

  1. Lý thuyết độ phức tạp tính toán:

    • Các lớp độ phức tạp: $P$ (thời gian đa thức xác định), $NP$ (chứng chỉ ngắn kiểm tra được trong thời gian đa thức), $coNP$ (bác bỏ ngắn kiểm tra được trong thời gian đa thức), $NP \cap coNP$, và $BPP$ (thời gian đa thức xác suất với máy Turing xác suất - PPT).
    • Hàm bỏ qua được (negligible function): Hàm $\mu: \mathbb{N} \to \mathbb{R}$ được gọi là bỏ qua được nếu với mọi đa thức $p$, tồn tại $N$ sao cho $\forall n > N: \mu(n) < 1/p(n)$.
    • Tập hợp các hàm một chiều mạnh (strongly one-way collection of functions) ${f_i: D_i \to {0,1}^*}{i \in I}$ được định nghĩa qua ba thuật toán PPT: Thuật toán chọn chỉ số $I(1^n)$, thuật toán lấy mẫu miền xác định $D(i)$, và thuật toán đánh giá $F(i, x) = f_i(x)$, thỏa mãn điều kiện khó nghịch đảo: $$\Pr[\mathcal{A}(I_n, f{I_n}(X_{I_n})) \in f_{I_n}^{-1}(f_{I_n}(X_{I_n}))] < \frac{1}{p(n)}$$

  2. Lý thuyết nhóm và bài toán logarit rời rạc (DLP):

    • Trong nhóm cyclic hữu hạn $G = \langle \alpha \rangle$ cấp $n$: DLP yêu cầu tìm $x \in [0, n-1]$ sao cho $\alpha^x = \beta$.
    • Giả định tính toán Diffie-Hellman (CDH) và giả định quyết định Diffie-Hellman (DDH) trên bộ ba $(\alpha^x, \alpha^y, \alpha^z)$.
    • Khái niệm chữ ký logarit và phủ: Cho dãy $\Gamma = [A_1, A_2, \dots, A_s]$ các dãy con trong $G$. $\Gamma$ là một phủ nếu mọi phần tử $g \in G$ đều phân tích được thành tích $g = h_1 h_2 \dots h_s$ với $h_i \in A_i$. Nếu phân tích là duy nhất, $\Gamma$ là chữ ký logarit. Phủ được gọi là phủ thuần (tame cover) nếu việc phân tích thừa số thực hiện được trong thời gian đa thức; ngược lại được gọi là phủ hoang dã (wild cover).

  3. Lý thuyết nhóm tổ hợp (Combinatorial Group Theory):

    • Biểu diễn nhóm $G = \langle X, R \rangle$ với tập sinh $X$ và tập quan hệ $R$.
    • Các phép biến đổi viết lại:
      • $(T1)$: Chèn một quan hệ $r \in R \cup R^{-1}$ hoặc quan hệ tầm thường ($x_i x_i^{-1}, x_i^{-1} x_i$).
      • $(T2)$: Xóa một quan hệ $r \in R \cup R^{-1}$ hoặc quan hệ tầm thường tạo thành một khối ký tự liên tiếp.
    • Bài toán từ (Word problem): Xác định xem một từ $w$ trên $X \cup X^{-1}$ có tương đương với từ rỗng (phần tử đơn vị) hay không.
    • Bài toán lựa chọn từ (Word choice problem): Cho trước hai từ $w_0, w_1$ không tương đương; với đầu vào $w$ thỏa mãn điều kiện tiền đề ($w \equiv w_0$ hoặc $w \equiv w_1$), xác định xem $w \equiv w_0$ hay không.

  4. Nhóm biến đổi và nhóm Higman-Thompson:

    • Nhóm tác động trung thành và bắc cầu trên tập các xâu ký tự ${0,1,2}^*$.
    • Nhóm $G = \langle G'{2,3,3}(0,1;#) \cup {x{3,2,1}} \rangle$ liên hệ với nhóm vô hạn biểu diễn hữu hạn đơn $G_{3,1}$ của Higman-Thompson, có bài toán từ thuộc lớp $coNP$-đầy đủ và mô phỏng được các mạch logic tổ hợp trong thời gian $O(|z| + |w|)$.

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

  • Phương pháp toán học quy giảm (Reduction method): Thiết lập các quy giảm thời gian đa thức giữa các bài toán mật mã và các bài toán nền tảng (quy giảm lược đồ Kashyap et al. về ElGamal; quy giảm bài toán tách khóa Stickel về bài toán thuộc nhóm con; quy giảm bài toán SAT mạch logic về bài toán hành động chung).
  • Phương pháp thám mã đại số và tối ưu hóa tìm kiếm: Thiết lập các thuật toán kiểm tra quan hệ thuộc nhóm con kết hợp tìm kiếm nhị phân trên bảng sắp xếp, giảm độ phức tạp thời gian trường hợp xấu nhất xuống $O(n_1 \log n_1)$.
  • Phương pháp thực nghiệm kiểm chứng: Lập trình thuật toán thám mã bằng ngôn ngữ C, biên dịch bằng Intel C-compiler v9, thực thi song song trên cụm máy tính hiệu năng cao BOCA4 Beowulf.

Nguồn tư liệu và dữ liệu thực nghiệm

  • Dữ liệu toán học giải tích: Các cấu trúc trường hữu hạn, ma trận đồng hành của các đa thức bất khả quy bậc 31 trên trường $GF(2)[x]$: $$p(x) = x^{31} + x^3 + 1$$ $$q(x) = x^{31} + x^{30} + x^{29} + x^3 + 1$$
  • Trường mở rộng $F = GF(2)[x] / (x^8 + x^4 + x^3 + x^2 + 1)$ gồm 256 phần tử.
  • Cụm siêu máy tính BOCA4 Beowulf: 44 nút tính toán sử dụng bộ vi xử lý Intel Pentium-IV 2.5 GHz chạy hệ điều hành Linux.

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

Chương 1: Introduction

Chương mở đầu hệ thống hóa bối cảnh phát triển của mật mã học, phân định ba phân ngành chính: mật mã học (cryptography), thám mã học (cryptanalysis) và giấu tin (steganography). Tác giả trình bày động lực cốt lõi xuất phát từ sự đe dọa của thuật toán lượng tử Shor (1994) đối với các bài toán phân tích thừa số nguyên và logarit rời rạc cổ điển. Luận án xác định cấu trúc dựa trên kết quả của 4 công trình nghiên cứu độc lập của tác giả nhằm khai thác lý thuyết nhóm cho mật mã học, bao gồm thám mã các lược đồ lỗi thời và đề xuất các cấu trúc mật mã mới.

Chương 2: Preliminaries

Chương này cung cấp hệ thống định nghĩa và cơ sở lý thuyết chuẩn xác làm nền tảng cho toàn bộ luận án:

  • Phân tích chi tiết các lớp độ phức tạp $P, NP, coNP, NP \cap coNP, BPP$, định nghĩa hàm một chiều và hoán vị một chiều có cửa sập.
  • Trình bày bài toán logarit rời rạc truyền thống (DLP), bài toán logarit rời rạc tổng quát (GDLP) trong nhóm cyclic, thuật toán Shank Baby step - Giant step với độ phức tạp thời gian $O(\sqrt{n})$ phép tính nhóm và bộ nhớ $O(\sqrt{n})$ phần tử.
  • Mô tả lược đồ trao đổi khóa Diffie-Hellman, lược đồ mã hóa ElGamal cùng các giả định CDH và DDH.
  • Định nghĩa chữ ký logarit, phủ, phân biệt phủ thuần (tame) và phủ hoang dã (wild); chỉ ra mối liên hệ tương đương giữa bài toán DLP truyền thống và việc phân tích nhân tử trên phủ hoang dã $\Gamma = [A_1, \dots, A_s]$ với $A_i = {1, \alpha^{2^{i-1}}}$.
  • Trình bày lý thuyết nhóm tổ hợp: biểu diễn nhóm $\langle X, R \rangle$, độ dài từ, các phép biến đổi viết lại T1/T2, bài toán từ của Dehn và định lý Novikov - Boone về các nhóm có bài toán từ không khử được.

Chương 3: The Encryption Scheme of Kashyap et al.

Chương 3 tập trung phân tích và thám mã hệ mật mã khóa công khai do Sunil Kumar Kashyap, Birendra Kumar Sharma và Amitabh Banerjee đề xuất năm 2006 dựa trên bài toán logarit rời rạc hai phần tử sinh (2DL) trên nhóm $G = \mathbb{Z}_p^*$:

  • Lược đồ đề xuất: Khóa công khai gồm số nguyên tố $p$, hai phần tử sinh $\alpha, \beta$, $\gamma = \alpha^a \pmod p$ và $\delta = \beta^b \pmod p$. Khóa bí mật là $(a, b)$. Bản mã của thông điệp $x \in \mathbb{Z}_p^*$ với số ngẫu nhiên $k$ là $(y_1, y_2, y_3) = (\alpha^k, \beta^k, x\gamma^k\delta^k \pmod p)$. Quá trình giải mã tính $y_1^{-a} y_2^{-b} y_3 \pmod p$.
  • Kết quả thám mã:
    1. Tác giả chứng minh bài toán 2DL không xác định chặt chẽ. Vì $\beta$ là phần tử sinh nên luôn tồn tại số nguyên $m$ sao cho $\alpha = \beta^m$, dẫn đến $\alpha^a \beta^b = (\beta^m)^a \beta^b = \beta^{ma+b}$.
    2. Để giải mã bản mã $(y_1, y_2, y_3)$, kẻ tấn công không cần tìm $(a, b)$ mà chỉ cần tìm số ngẫu nhiên $k$ bằng cách giải duy nhất 1 bài toán logarit rời rạc truyền thống qua một trong ba cách: $$k = \log_\alpha(y_1) = \log_\beta(y_2) = \log_{\alpha\beta}(y_1 y_2)$$ Sau khi có $k$, thông điệp được khôi phục trực tiếp: $x = y_3 \gamma^{-k} \delta^{-k} \pmod p$.
    3. Luận án chứng minh bằng quy giảm toán học rằng lược đồ này tương đương chính xác với hệ mã hóa ElGamal kinh điển với khóa bí mật $t = ma + b$ và khóa công khai $(\beta, \beta^t)$. Lược đồ của Kashyap và cộng sự đòi hỏi chi phí tính toán cao hơn nhưng độ an toàn hoàn toàn không vượt trội hơn ElGamal.

Chương 4: The Key Exchange Scheme of Stickel

Chương 4 nghiên cứu và thám mã giao thức trao đổi khóa trong nhóm phi giao hoán do Eberhard Stickel đề xuất năm 2005:

  • Giao thức tổng quát (Scheme 4.1): Cho nhóm phi giao hoán hữu hạn $G$, hai phần tử không giao hoán $\alpha, \beta \in G$ có cấp lần lượt là $n_1, n_2$. Bob chọn bí mật $(r, s)$ và gửi $\gamma = \alpha^r \beta^s$; Alice chọn bí mật $(u, w)$ và gửi $\delta = \alpha^u \beta^w$. Khóa chung được tính là $\kappa = \alpha^{u+r} \beta^{w+s}$.
  • Thể hiện ma trận cụ thể (Scheme 4.2): Sử dụng các ma trận đồng hành $C, D \in GL_n(GF(2))$ của hai đa thức bậc $n$ với cấp nguyên tố Mersenne $2^n-1$, ma trận khả nghịch $T_1, T_2$ trên trường mở rộng $F$, cùng các vô hướng bí mật $a, b \in F^*$. Bob gửi $F' = b C^r T_1 T_2 D^s$; Alice gửi $H = a C^u T_1 T_2 D^w$. Khóa chung là ma trận $K = a b C^{u+r} T_1 T_2 D^{w+s}$.
  • Phân tích thám mã và thuật toán:
    1. Luận án chỉ ra rằng kẻ tấn công chỉ cần tìm được 1 trong 4 tham số bí mật ($r, s, u$ hoặc $w$) là có thể tái tạo hoàn toàn khóa chung (ví dụ: nếu biết $r$, tính khóa $\kappa = \alpha^r \delta \alpha^{-r} \gamma$).
    2. Tác giả xây dựng Thuật toán 4.1 và 4.2 dựa trên việc kiểm tra điều kiện $\alpha^{-i}\gamma \in \langle \beta \rangle$. Phân tích trường hợp xấu nhất chứng minh độ phức tạp thời gian để bẻ khóa lược đồ tổng quát chỉ là $O(n_1 \log n_1)$ phép tính nhóm, với không gian lưu trữ $O(n_2)$ phần tử nhóm (thay vì tìm kiếm vét cạn $(2^n-1)^2$ như tuyên bố của Stickel).
    3. Đối với Scheme 4.2, tác giả xây dựng Thuật toán 4.3 và 4.4 xét ma trận $M = T_2^{-1} T_1^{-1} C^{-i} F'$. Nếu $i = r$, ma trận $M = b D^s$ chỉ chứa tối đa 2 giá trị phần tử ${0, b}$ thuộc $F$; nếu $i \neq r$, $M$ chứa nhiều hơn 2 giá trị khác nhau. Độ phức tạp tìm kiếm giảm xuống chỉ còn $2^n-1 \approx 2^{31}$ phép tính.
  • Kết quả thực nghiệm: Tác giả lập trình Thuật toán 4.3 bằng ngôn ngữ C, biên dịch bằng Intel C-compiler v9 và thực thi trên cụm 44 máy tính BOCA4 Beowulf (Pentium-IV 2.5 GHz). Cuộc tấn công đã tìm ra chính xác cặp khóa $(b, r)$ đối với tham số $n = 31$ trong thời gian chưa đầy 31 giờ.
+---------------------------------------------------------------------------------------------------+
| BẢNG TỔNG HỢP SO SÁNH ĐỘ PHỨC TẠP VÀ HIỆU NĂNG THÁM MÃ GIAO THỨC STICKEL (N = 31)                |
+----------------------+-----------------------------+-------------------------------+--------------+
| Phương pháp          | Không gian tìm kiếm         | Độ phức tạp thời gian         | Bộ nhớ       |
+----------------------+-----------------------------+-------------------------------+--------------+
| Vét cạn (Stickel)    | $(2^{31}-1)^2 \approx 2^{62}$| Rất lớn (bất khả thi năm 2006)| Không đáng kể|
| Thuật toán Sramka    | $2^{31}-1 \approx 2^{31}$   | $O(n_1 \log n_1)$             | $O(n_2)$     |
| Thực nghiệm BOCA4    | $2^{31}-1$ lặp              | < 31 giờ (44 nút Pentium-IV)  | Bảng tra cứu |
+----------------------+-----------------------------+-------------------------------+--------------+

Chương 5: The Public-Key Cryptosystem of Wagner and Magyarik

Chương 5 phân tích phê phán hệ mật Wagner - Magyarik (1984) và đề xuất hệ mật khóa công khai mới dựa trên nhóm biến đổi:

  • Phê phán hệ Wagner - Magyarik:
    1. Lỗi nhận định nền tảng: Hệ thống không dựa trên bài toán từ (word problem) mà thực chất dựa trên "bài toán lựa chọn từ" (word choice problem - một promise problem) thuộc lớp $NP \cap coNP$, do đó không thể đạt tới độ khó $NP$-đầy đủ.
    2. Tính mơ hồ: Không chỉ rõ cách tìm biểu diễn nhóm có bài toán từ khó, cách chọn từ $w_0, w_1$, và tiêu chuẩn dừng cho quá trình viết lại ngẫu nhiên (T1, T2).
    3. Lỗ hổng tấn công bản mã chọn lọc: Tác giả chỉ ra kẻ tấn công có thể khôi phục tập quan hệ bí mật $S$ với độ phức tạp $O(m^2)$ bằng cách mã hóa từ $w_0 s$ và quan sát kết quả giải mã.
    4. Tồn tại khóa thay thế: Mọi ảnh đồng cấu của $G$ có bài toán từ dễ tách được $w_0, w_1$ đều có thể dùng để giải mã mà không cần tìm chính xác tập $S$.
  • Đề xuất hệ mật mã mới dựa trên nhóm biến đổi:
    • Sử dụng nhóm biểu diễn hữu hạn $G = \langle X, R \rangle$ tác động trung thành và bắc cầu lên xâu ký tự ${0,1,2}^*$, có bài toán từ thuộc lớp $coNP$-đầy đủ (dựa trên nhóm Higman-Thompson $G_{3,1}$).
    • Khóa bí mật: Bộ ba xâu ký tự $(x, z, u) \in ({0,1,2}^*)^3$ có độ dài ngẫu nhiên từ $n$ đến $2n$.
    • Khóa công khai: Biểu diễn nhóm $(X, R)$ và hai hệ thống tập từ $(Z_1, \dots, Z_m)$ (để mã hóa bit 0) và $(U_1, \dots, U_m)$ (để mã hóa bit 1) mô phỏng các mạch logic chuyển đổi các xâu trung gian $z_j, u_j$.
    • Thuật toán mã hóa: Chọn ngẫu nhiên $w_j \in Z_j$, ghép thành từ $w_1 \dots w_m$, sau đó áp dụng Thuật toán viết lại ngẫu nhiên 5.1 dựa trên hệ quan hệ đối xứng $(X, R_s)$.
    • Thuật toán giải mã: Tính tác động $(x)w$ trong thời gian $O(|x| + |w|)$. Nếu $(x)w = z$, giải mã ra 0; nếu $(x)w = u$, giải mã ra 1.
  • Các kết quả lý thuyết mở rộng:
    • Chứng minh bài toán lựa chọn từ cho nửa nhóm biểu diễn hữu hạn $S_{np}$ là một bài toán tiền đề $(NP \cap coNP)$-đầy đủ.
    • Định nghĩa "Bài toán hành động chung" (Common action problem) và chứng minh bài toán hành động chung cho mạch logic (Circuit common action problem) là $NP$-đầy đủ thông qua quy giảm từ bài toán Circuit-SAT.

Chương 6: A Generalization of the DLP and Construction of OWFs

Chương 6 trình bày định nghĩa tổng quát hóa bài toán logarit rời rạc cho các nhóm hữu hạn sinh phi giao hoán bất kỳ:

  • Định nghĩa hình thức bài toán phân tích phần tử trên các hệ sinh của nhóm phi giao hoán.
  • Thiết lập mô hình xây dựng hàm một chiều (OWF) với chứng minh an toàn chặt chẽ dựa trên độ khó của bài toán phân tích phần tử trong nhóm xạ ảnh tuyến tính đặc biệt $PSL_2(\mathbb{F}_q)$ trên trường hữu hạn cấp nguyên tố $q$.
  • Chứng minh rằng từ cấu trúc hàm một chiều này, có thể xây dựng các bộ sinh số giả ngẫu nhiên có độ an toàn chứng minh được (theo định lý Håstad et al.) và các lược đồ chữ ký số an toàn chống lại tấn công giả mạo thông điệp chọn lọc (theo định lý Rompel).

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

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

  1. Làm rõ bản chất độ phức tạp của mật mã học lý thuyết nhóm tổ hợp: Luận án chứng minh rằng các hệ mật dựa trên ý tưởng Wagner - Magyarik không dựa trên bài toán từ kinh điển mà phụ thuộc vào bài toán lựa chọn từ (word choice problem). Tác giả phân loại bài toán này thuộc lớp $NP \cap coNP$ và xây dựng thể hiện $(NP \cap coNP)$-đầy đủ đầu tiên trên cấu trúc nửa nhóm biểu diễn hữu hạn.
  2. Chứng minh tính $NP$-đầy đủ của bài toán hành động chung trên mạch logic: Thiết lập quy giảm toán học từ Circuit-SAT sang Circuit Common Action Problem, tạo nền tảng lý thuyết độ phức tạp vững chắc cho các hệ mật dựa trên nhóm biến đổi.
  3. Hình thức hóa bài toán DLP trên nhóm phi giao hoán: Đưa ra định nghĩa tổng quát hóa cho DLP và thiết lập mô hình toán học chứng minh sự tồn tại của hàm một chiều (OWF) dựa trên bài toán phân tích phần tử trong nhóm xạ ảnh tuyến tính đặc biệt $PSL_2(\mathbb{F}_q)$.

Đóng góp mới về mặt thực tiễn và thám mã

  1. Phá vỡ hoàn toàn lược đồ mã hóa 2DL (Kashyap et al., 2006): Chứng minh tính không xác định chặt chẽ của bài toán 2DL, đưa ra thuật toán khôi phục bản rõ chỉ bằng 1 bài toán DLP đơn và chứng minh sự tương đương toán học với hệ mật ElGamal.
  2. Hạ thấp độ phức tạp và thám mã thành công giao thức trao đổi khóa Stickel (2005):
    • Chứng minh chỉ cần tìm 1 trong 4 số mũ bí mật để phá vỡ toàn bộ khóa chung.
    • Giảm độ phức tạp thời gian trường hợp xấu nhất từ $(2^n-1)^2$ xuống $O(n_1 \log n_1)$ với bộ nhớ $O(n_2)$.
    • Đối với thể hiện ma trận trên $GL_{31}(GF(2))$, giảm số phép tính xuống $2^{31}-1$ và thực nghiệm bẻ khóa thành công trên cụm 44 máy tính BOCA4 Beowulf trong thời gian dưới 31 giờ.
  3. Hiện thực hóa hệ mật mã khóa công khai dựa trên nhóm biến đổi: Đưa ra giải pháp khắc phục triệt để các khiếm khuyết của hệ Wagner - Magyarik thông qua việc sử dụng nhóm liên quan đến nhóm Higman-Thompson $G_{3,1}$ tác động lên xâu ký tự ${0,1,2}^*$, cho phép giải mã tuyến tính $O(|x| + |w|)$ và kháng tấn công bản mã chọn lọc $O(m^2)$.

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

  • Trong thiết kế giao thức mật mã đại số: Tuyệt đối không xây dựng các biến thể logarit rời rạc tuyến tính đơn giản trên nhóm cyclic vì chúng luôn quy giảm được về bài toán logarit rời rạc đơn.
  • Trong lựa chọn tham số an toàn cho nhóm ma trận: Không được tính toán độ an toàn dựa trên tích không gian của hai phần tử không giao hoán ($(2^n-1)^2$) khi đối thủ có thể tách rời các thành phần; kích thước tham số an toàn phải dựa trên cấp của từng phần tử riêng biệt ($2^n-1$).
  • Ứng dụng cấu trúc nhóm biến đổi: Khuyến nghị tiếp tục phát triển các hệ mật mã khóa công khai dựa trên nhóm Higman-Thompson và nhóm $PSL_2(\mathbb{F}_q)$ như những ứng viên tiềm năng cho mật mã học hậu lượng tử.

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

Các hạn chế được văn bản đề cập

  1. Độ phức tạp trường hợp xấu nhất so với trường hợp trung bình: Các phân tích độ phức tạp trong luận án chủ yếu thiết lập trên trường hợp xấu nhất (worst-case complexity). Trong an toàn mật mã học, độ phức tạp trường hợp trung bình (average-case complexity) hoặc hầu hết các trường hợp (almost-all case complexity) là thước đo chuẩn xác hơn, nhưng các khái niệm này trong lý thuyết nhóm tổ hợp tại thời điểm nghiên cứu còn gặp nhiều vướng mắc về mặt định nghĩa.
  2. Quy trình viết lại từ ngẫu nhiên trong hệ mật nhóm biến đổi: Thuật toán 5.1 áp dụng các quy tắc viết lại ngẫu nhiên để xóa dấu vết cấu trúc tập từ ban đầu ($Z_j, U_j$), nhưng luận án chưa xác định được chính xác số lần viết lại tối ưu để vừa đảm bảo độ an toàn, vừa tránh làm tăng kích thước bản mã quá mức.
  3. Các giả thuyết lý thuyết chưa được chứng minh trọn vẹn:
    • Tính $(NP \cap coNP)$-đầy đủ của bài toán lựa chọn từ trên nhóm $G = \langle G'{2,3,3}(0,1;#) \cup {x{3,2,1}} \rangle$ mới chỉ được chứng minh trên nửa nhóm $S_{np}$.
    • Tính $NP$-đầy đủ của bài toán hành động chung trên nhóm $G$ mới chỉ chứng minh được khi hạn chế trên tập xâu $0{0,1}^* \cup 0{0,1}^*2$, trường hợp tổng quát vẫn là một giả thuyết mở.
    • Vấn đề tồn tại biểu diễn kích thước tuyến tính theo $n$ cho nhóm đối xứng hữu hạn $S_N$ (với $N = 2^n$) chưa có lời giải.

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

  • Nghiên cứu độ phức tạp trường hợp trung bình cho bài toán từ và bài toán phân tích phần tử trên các nhóm biến đổi.
  • Tối ưu hóa thuật toán viết lại từ ngẫu nhiên nhằm giảm thiểu độ nở bản mã (ciphertext expansion) trong hệ mật nhóm biến đổi.
  • Hoàn thiện chứng minh tính đầy đủ độ phức tạp cho bài toán hành động chung và bài toán lựa chọn từ trên các lớp nhóm cụ thể.

Giá trị tham khảo

Đối tượng thụ hưởng

  • Nghiên cứu sinh và học giả chuyên ngành Mật mã học và Đại số tính toán: Cung cấp tài liệu tham khảo chi tiết về phương pháp thám mã các cấu trúc nhóm phi cyclic, kỹ thuật quy giảm độ an toàn và ứng dụng lý thuyết nhóm tổ hợp trong mật mã học hậu lượng tử.
  • Giảng viên và chuyên gia An toàn thông tin: Sử dụng làm tài liệu giảng dạy chuyên đề cao học về Độ phức tạp tính toán trong mật mã, Thám mã đại số và Các giao thức khóa công khai phi chuẩn.
  • Kỹ sư thiết kế giao thức bảo mật: Tham khảo các phân tích sai lầm cấu trúc từ các lược đồ của Kashyap et al. và Stickel để tránh lặp lại các lỗ hổng khi thiết kế hệ mật mã trên cấu trúc đại số mới.

Các nội dung đáng tham khảo

  • Chương 3 và Chương 4: Phương pháp luận chuẩn mực trong việc phân tích thám mã đại số, kỹ thuật tách tham số và quy trình triển khai tấn công thực nghiệm trên hệ thống máy tính song song hiệu năng cao.
  • Chương 5: Khung lý thuyết chuyển đổi giữa mạch logic tổ hợp và nhóm biến đổi Higman-Thompson tác động lên xâu ký tự, cung cấp phương pháp thiết kế hệ mật giải mã thời gian tuyến tính $O(|x| + |w|)$.
  • Chương 2 và Chương 6: Cơ sở toán học về chữ ký logarit, phủ hoang dã và mô hình chứng minh an toàn cho hàm một chiều dựa trên nhóm $PSL_2(\mathbb{F}_q)$.

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

1. Tại sao bài toán 2DL của Kashyap và cộng sự không làm tăng độ an toàn so với bài toán logarit rời rạc truyền thống?

Trong nhóm cyclic hữu hạn $G = \mathbb{Z}_p^*$, mọi phần tử đều là lũy thừa của một phần tử sinh $\beta$. Do đó, phần tử sinh thứ hai $\alpha$ luôn có dạng $\alpha = \beta^m$ với một số nguyên $m$ nào đó. Khi đó, biểu thức $\alpha^a \beta^b$ thực chất quy về $\beta^{ma+b}$. Ngoài ra, trong bản mã $(y_1, y_2, y_3) = (\alpha^k, \beta^k, x\gamma^k\delta^k)$, kẻ tấn công chỉ cần giải duy nhất 1 bài toán logarit rời rạc truyền thống từ $y_1 = \alpha^k$ hoặc $y_2 = \beta^k$ để tìm ra số ngẫu nhiên $k$, từ đó khôi phục trực tiếp bản rõ $x = y_3 \gamma^{-k} \delta^{-k} \pmod p$ mà không cần tìm các khóa bí mật $(a, b)$.

2. Điểm sai lầm then chốt trong ước tính độ an toàn của Eberhard Stickel đối với giao thức trao đổi khóa ma trận là gì?

Eberhard Stickel tuyên bố rằng kẻ tấn công phải tìm kiếm trên toàn bộ không gian $(2^n-1)^2$ gồm các cặp số mũ $(r, s)$. Tuy nhiên, tác giả Michal Sramka chứng minh rằng kẻ tấn công không cần tìm cả hai số mũ mà chỉ cần tìm duy nhất 1 trong 4 số mũ bí mật ($r, s, u$ hoặc $w$) là có thể khôi phục toàn bộ khóa chung. Nhờ vậy, không gian tìm kiếm thực tế giảm từ $(2^n-1)^2$ xuống chỉ còn $2^n-1$, đưa độ phức tạp thời gian trường hợp xấu nhất về $O(n_1 \log n_1)$ với bộ nhớ $O(n_2)$.

3. Kết quả thực nghiệm thám mã giao thức Stickel của tác giả đạt được hiệu năng như thế nào?

Tác giả đã cài đặt thuật toán thám mã bằng ngôn ngữ C (biên dịch bằng Intel C-compiler v9) và chạy trên cụm 44 máy tính BOCA4 Beowulf (mỗi nút sử dụng chip Intel Pentium-IV 2.5 GHz chạy Linux). Với tham số an toàn $n = 31$ trên trường mở rộng gồm 256 phần tử, hệ thống đã quét qua không gian $2^{31}-1$ trạng thái và tìm ra chính xác duy nhất một nghiệm bí mật trong thời gian chưa đầy 31 giờ.

4. Sự khác biệt căn bản giữa bài toán từ (word problem) và bài toán lựa chọn từ (word choice problem) trong hệ Wagner - Magyarik là gì?

Bài toán từ của Dehn là bài toán quyết định tổng quát: kiểm tra xem một từ bất kỳ $w$ có tương đương với từ rỗng (phần tử đơn vị) trong biểu diễn nhóm hay không. Trong khi đó, bài toán lựa chọn từ là một bài toán tiền đề (promise problem): cho trước hai từ cố định $w_0, w_1$ và biết trước rằng đầu vào $w$ chắc chắn tương đương với $w_0$ hoặc $w_1$, yêu cầu xác định xem $w \equiv w_0$ hay không. Bài toán lựa chọn từ thuộc lớp độ phức tạp $NP \cap coNP$, dễ giải quyết hơn nhiều so với bài toán từ tổng quát và không thể đạt tới độ khó $NP$-đầy đủ.

5. Nhóm biến đổi nào được tác giả lựa chọn để xây dựng lại hệ mật mã khóa công khai thay thế mô hình Wagner - Magyarik?

Tác giả sử dụng nhóm biến đổi biểu diễn hữu hạn $G = \langle G'{2,3,3}(0,1;#) \cup {x{3,2,1}} \rangle$, một cấu trúc liên hệ mật thiết với nhóm đơn vô hạn biểu diễn hữu hạn $G_{3,1}$ của Higman-Thompson. Nhóm này tác động trung thành và bắc cầu lên tập xâu ký tự ${0,1,2}^*$, có bài toán từ thuộc lớp $coNP$-đầy đủ và cho phép tính toán tác động của từ lên xâu ký tự trong thời gian xác định tuyến tính $O(|z| + |w|)$.

Kết luận

Luận án tiến sĩ của Michal Sramka đã đóng góp những kết quả quan trọng cho lĩnh vực mật mã học lý thuyết nhóm thông qua việc kết hợp chặt chẽ giữa phân tích đại số lý thuyết, chứng minh độ phức tạp tính toán và thám mã thực nghiệm. Tác giả đã chứng minh sự thiếu an toàn và vô hiệu hóa các đề xuất mở rộng logarit rời rạc của Kashyap et al. và Stickel, đồng thời chỉ ra bản chất lý thuyết độ phức tạp $NP \cap coNP$ của bài toán lựa chọn từ trong hệ mật Wagner - Magyarik. Trên cơ sở đó, luận án đã xây dựng thành công hệ mật mã khóa công khai mới dựa trên nhóm biến đổi Higman-Thompson và thiết lập mô hình tổng quát hóa bài toán logarit rời rạc cho nhóm phi giao hoán $PSL_2(\mathbb{F}_q)$ với các chứng minh an toàn hình thức.