Bối cảnh và vấn đề nghiên cứu

Trong bối cảnh công nghệ thông tin và mạng Internet phát triển nhanh chóng, việc sử dụng máy tính và các thiết bị cá nhân để lưu trữ, trao đổi dữ liệu ngày càng trở nên phổ biến. Sự chuyển dịch từ các phương thức bảo mật truyền thống mang tính vật lý (như đóng dấu niêm phong thư tín, lưu trữ tài liệu trong két sắt) sang môi trường số đòi hỏi các giải pháp mật mã hóa mạnh mẽ nhằm bảo vệ các thuộc tính an toàn thông tin cốt lõi, bao gồm: tính riêng tư (Confidentiality), tính toàn vẹn (Integrity), tính khả dụng (Availability) và tính không thể chối bỏ (Non-Repudiation).

Trước yêu cầu cấp thiết về an toàn dữ liệu trên mạng truyền thông, đồ án tốt nghiệp tập trung giải quyết các nhiệm vụ nghiên cứu sau:

  1. Hệ thống hóa các khái niệm nền tảng của mật mã học, phân loại các hệ mật mã đối xứng và bất đối xứng, cùng các phương pháp mã hóa cổ điển và hiện đại (DES, Elgamal).
  2. Nghiên cứu sâu cơ sở lý thuyết số học và các định lý toán học phục vụ mật mã học khóa công khai: thuật toán Euclid và Euclid mở rộng, định lý Fermat, hàm số và định lý Euler, thuật toán kiểm tra số nguyên tố Miller-Rabin, định lý số dư Trung Hoa (CRT) và bài toán logarithm rời rạc.
  3. Phân tích chi tiết nguyên lý hoạt động, cấu trúc thuật toán, các khía cạnh tính toán hiệu năng và tính an toàn của hệ mật mã khóa công khai RSA.
  4. Xây dựng chương trình phần mềm thực thi quá trình sinh khóa, mã hóa và giải mã dữ liệu theo thuật toán RSA.
  • Đối tượng nghiên cứu: Hệ thống mật mã khóa công khai RSA và các cấu trúc toán học nền tảng trong vành số học mô-đun.
  • Phạm vi nghiên cứu: Đồ án tiếp cận ở góc độ lý thuyết toán học mật mã và triển khai thuật toán trên máy tính, thực hiện trong khuôn khổ đồ án tốt nghiệp đại học chính quy ngành Điện tử Viễn thông tại Trường Đại học Dân lập Hải Phòng năm 2018.

Cơ sở lý thuyết và phương pháp

Đồ án xây dựng nội dung dựa trên hệ thống cơ sở lý thuyết và công cụ toán học chuyên sâu của ngành mật mã:

  • Mô hình hệ mật mã hình thức: Bộ 5 thành phần $(P, C, K, E, D)$ thỏa mãn điều kiện $d_k(e_k(x)) = x$ với mọi bản rõ $x \in P$, trong đó hàm mã hóa $e_k$ phải là hàm đơn ánh.
  • Lý thuyết số và vành số học mô-đun: Các phép toán trong vành $\mathbb{Z}_m$, vành thương của quan hệ đồng dư modulo $m$, và phép tìm phần tử nghịch đảo modulo thông qua điều kiện $\gcd(a, m) = 1$.
  • Các định lý toán học cốt lõi:
    • Thuật toán Euclid và Euclid mở rộng: Giải phương trình vô định Đi-ô-phăng $a \times x + b \times y = \gcd(a,b)$ để tìm số nghịch đảo modulo.
    • Định lý Fermat và Euler: Định lý Fermat $a^{p-1} \equiv 1 \pmod p$ (với $p$ nguyên tố, $\gcd(a,p)=1$) và dạng tổng quát qua định lý Euler $a^{\phi(n)} \equiv 1 \pmod n$, với $\phi(n)$ là hàm Euler biểu diễn số lượng số nguyên dương nhỏ hơn $n$ và nguyên tố cùng nhau với $n$.
    • Thuật toán kiểm tra số nguyên tố Miller-Rabin: Phân tích $n-1 = 2^k q$ ($q$ lẻ) để kiểm tra tính nguyên tố thông qua hai tính chất của căn bậc hai modulo số nguyên tố.
    • Định lý số dư Trung Hoa (Chinese Remainder Theorem - CRT): Khôi phục số nguyên trong vành $\mathbb{Z}_M$ từ hệ thặng dư theo các mô-đun nguyên tố cùng nhau từng đôi một, giúp phân rã phép tính số học lớn.
    • Bài toán Logarithm rời rạc: Cơ sở cho các hệ mật mã Diffie-Hellman, Elgamal và thuật toán chữ ký số DSA trên nhóm nhân $\mathbb{Z}_p^*$.
  • Phương pháp nghiên cứu: Tác giả kết hợp phương pháp phân tích - tổng hợp lý thuyết toán học mật mã, phương pháp mô hình hóa thuật toán tính toán và phương pháp thực nghiệm lập trình mô phỏng thuật toán trên máy tính.
  • Nguồn dữ liệu: Tài liệu chuẩn mã hóa dữ liệu DES (NBS/NIST 1977), công trình mật mã khóa công khai của Diffie - Hellman (1976), hệ mật RSA của Ronald Rivest, Adi Shamir, Leonard Adleman (1977/1978), cùng hệ thống bảng số nguyên tố nhỏ hơn 2000, bảng giá trị hàm $\phi(n)$ cho 30 số đầu tiên và bảng logarithm rời rạc modulo 19.

Thiết kế và triển khai thuật toán

Trong cấu trúc của đồ án, tác giả thiết kế và chi tiết hóa các thuật toán xử lý dữ liệu và mã nguồn cho hệ thống RSA:

1. Quy trình sinh khóa và mã hóa - giải mã

  • Tạo cặp khóa:
    • Chọn hai số nguyên tố ngẫu nhiên phân biệt $p$ và $q$.
    • Tính mô-đun công khai $n = p \times q$ và giá trị hàm Euler $\phi(n) = (p-1)(q-1)$.
    • Chọn số nguyên $e$ thỏa mãn điều kiện $1 < e < \phi(n)$ và $\gcd(e, \phi(n)) = 1$.
    • Tính số mũ giải mã bí mật $d \equiv e^{-1} \pmod{\phi(n)}$ bằng giải thuật Euclid mở rộng.
    • Khóa công khai được công bố là $PU = {e, n}$; khóa cá nhân được giữ bí mật là $PR = {d, n}$.
  • Biến đổi bản rõ và bản mã:
    • Mã hóa: Với khối bản rõ $M < n$, tính bản mã $C = M^e \bmod n$.
    • Giải mã: Với khối bản mã $C$, khôi phục bản rõ $M = C^d \bmod n$.

2. Kỹ thuật tối ưu hóa tính toán

  • Phép lũy thừa nhị phân mô-đun (Square-and-Multiply): Biểu diễn số mũ $b$ dưới dạng nhị phân $b = \sum_{i=0}^{k} b_i 2^i$ ($b_i \in {0, 1}$) để tính $a^b \bmod n$ thông qua chuỗi các phép bình phương và nhân liên tiếp rút gọn theo modulo $n$, giúp giảm thiểu đáng kể chi phí nhân số lớn so với cách tính thông thường.
  • Lựa chọn số mũ công khai $e$ hiệu năng: Thường sử dụng các số có biểu diễn nhị phân ít bit 1 như $e = 65537$ ($2^{16} + 1$), $e = 3$ hoặc $e = 17$.
  • Tăng tốc giải mã bằng định lý số dư Trung Hoa (CRT): Thay vì tính trực tiếp $M = C^d \bmod n$ trên mô-đun lớn $n$, hệ thống chia nhỏ phép tính thành hai thành phần $V_p = C^d \bmod p$ và $V_q = C^d \bmod q$ trên các mô-đun nhỏ hơn rồi khôi phục $M$, giúp tăng tốc độ xử lý.

3. Cài đặt chương trình

  • Chương trình được cài đặt bằng ngôn ngữ lập trình Python thông qua tệp mã nguồn 3.py, hiện thực hóa toàn bộ các hàm số học hỗ trợ, quy trình tạo khóa, chia khối bản rõ và thực thi mã hóa/giải mã RSA.

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

Chương 1: Tổng quan về mật mã học

Chương này cung cấp bức tranh toàn cảnh về lịch sử, khái niệm và nền tảng toán học của mật mã học:

  • Khái niệm và phân loại: Trình bày định nghĩa mật mã học lập mã và mật mã học phân tích; phân tích chi tiết hai nhóm hệ mật:
    • Mật mã đối xứng: Dùng chung khóa cho mã hóa và giải mã (tiêu biểu là DES - Data Encryption Standard, chuyển dịch từ hệ mật LUCIFER của IBM năm 1971 với khối 64 bit, khóa 56 bit). Phân tích các tranh cãi về độ dài khóa 56 bit và cấu trúc hộp S-box của NSA.
    • Mật mã bất đối xứng: Dùng cặp khóa công khai và khóa cá nhân riêng biệt, giải quyết triệt để vấn đề phân phối khóa.
  • Các thuật toán mã hóa cổ điển: Khảo sát mật mã Caesar ($f(p) = (p+3) \bmod 26$), mã thay thế (hoán vị 26 ký tự), mã Vigenère (mã hóa theo nhóm $m$ ký tự với từ khóa $k$), và mã hoán vị.
  • Cơ sở lý thuyết số cho mật mã học:
    • Thiết lập thuật toán Euclid mở rộng để tìm phần tử nghịch đảo trong vành $\mathbb{Z}_m$.
    • Khảo sát các tính chất phân tích thừa số nguyên tố, bảng số nguyên tố nhỏ hơn 2000, và phương pháp xác định ước chung lớn nhất qua số mũ nguyên tố.
    • Trình bày chứng minh toán học cho định lý Fermat ($a^{p-1} \equiv 1 \pmod p$) và định lý Euler ($a^{\phi(n)} \equiv 1 \pmod n$), kèm bảng thống kê 30 giá trị đầu tiên của hàm $\phi(n)$.
    • Phân tích thuật toán kiểm tra số nguyên tố xác suất Miller-Rabin dựa trên hai tính chất của căn bậc hai modulo $p$; chứng minh sai số sau $t$ lần lặp kiểm tra nhỏ hơn $(1/4)^t$ (với $t=10$, xác suất sai số nhỏ hơn $10^{-6}$). Đề cập thuật toán xác định tính nguyên tố AKS (Agrawal, Kayal, Saxena - công bố 2002, xuất bản 2004) và định lý phân bố số nguyên tố ($0.5\ln(n)$ phép thử).
    • Trình bày định lý số dư Trung Hoa (CRT) với hai khẳng định và các bước chứng minh toán học chặt chẽ, kèm ví dụ tính toán trên cặp mô-đun 37 và 49 cho số 973 modulo 1813.
    • Khảo sát bài toán logarithm rời rạc trong $\mathbb{Z}_p^*$, khái niệm căn nguyên thủy modulo $n$, kèm bảng tính chi tiết các dãy số và logarithm rời rạc cho các cơ số 2, 3, 10, 13, 14, 15 theo modulo 19; giới thiệu hệ mật Elgamal.

Chương 2: Mật mã khóa công khai RSA

Chương 2 tập trung phân tích sâu kiến trúc hệ mật mã khóa công khai và thuật toán RSA:

  • Nguyên tắc và mô hình hoạt động:
    • Mô hình 6 thành phần: Bản rõ (Plaintext), Thuật toán mã hóa, Khóa công khai, Khóa cá nhân, Bản mã (Ciphertext), Thuật toán giải mã.
    • Khái niệm hàm một chiều có cửa bẫy (Trapdoor one-way function): Dễ tính toán theo chiều thuận $Y = f_k(X)$, nhưng không thể tính toán đảo $X = f_k^{-1}(Y)$ trong thời gian đa thức nếu không có thông tin bí mật $k$.
    • Hai mô hình ứng dụng cốt lõi: Bảo mật thông tin (người gửi mã hóa bằng khóa công khai của người nhận $PU_b$) và Xác thực/Chữ ký số (người gửi mã hóa bằng khóa riêng của mình $PR_a$). Mô hình kết hợp thực hiện mã hóa hai lớp $Z = E(PU_b, E(PR_a, X))$ để đạt đồng thời tính bí mật và xác thực.
Tiêu chí so sánh Mã hóa thông thường (Đối xứng) Mã hóa khóa công khai (Bất đối xứng)
Yêu cầu hoạt động Cùng một thuật toán và một khóa bí mật dùng cho cả mã hóa và giải mã; người gửi và người nhận phải chia sẻ khóa an toàn. Một thuật toán mã hóa và một thuật toán giải mã liên kết; sử dụng cặp khóa riêng biệt (khóa công khai và khóa cá nhân).
Yêu cầu an ninh Khóa bí mật phải được bảo vệ tuyệt đối; biết thuật toán và bản mã không thể suy ra khóa. Khóa cá nhân phải được giữ bí mật; không thể tính toán suy ra khóa cá nhân từ khóa công khai và bản mã.
Ưu điểm Tốc độ tính toán và giải mã nhanh, phù hợp mã hóa khối lượng dữ liệu lớn. Giải quyết triệt để bài toán phân phối khóa; hỗ trợ tạo lập chữ ký số và xác thực nguồn gốc.
Nhược điểm Quản lý khóa phức tạp khi mạng lưới mở rộng; khó thực hiện xác thực và chống chối bỏ. Tốc độ giải mã chậm hơn; chi phí tính toán lũy thừa số học lớn.
  • Thuật toán RSA chi tiết:
    • Do Ron Rivest, Adi Shamir và Leonard Adleman công bố năm 1977 tại MIT. Kích thước mô-đun $n$ điển hình trong thực tế là 1024 bit (khoảng 309 chữ số thập phân).
    • Phân tích toán học chứng minh quan hệ nghịch đảo $M^{ed} \equiv M \pmod n$ dựa trên định lý Euler.
    • Ví dụ số học thực nghiệm trong văn bản:
      • Khởi tạo: Chọn $p = 17, q = 11 \implies n = 17 \times 11 = 187$.
      • Tính hàm Euler: $\phi(n) = (17 - 1)(11 - 1) = 16 \times 10 = 160$.
      • Chọn khóa công khai: $e = 7$ (thỏa mãn $\gcd(7, 160) = 1$).
      • Tính khóa bí mật: $d = 23$ (vì $23 \times 7 = 161 = 1 \times 160 + 1 \equiv 1 \pmod{160}$).
      • Quá trình mã hóa bản rõ $M = 88$: $$C = 88^7 \bmod 187 = [(88^4 \bmod 187) \times (88^2 \bmod 187) \times (88^1 \bmod 187)] \bmod 187$$ $$88^1 \bmod 187 = 88;\quad 88^2 \bmod 187 = 7744 \bmod 187 = 77;\quad 88^4 \bmod 187 = 59969536 \bmod 187 = 132$$ $$C = (88 \times 77 \times 132) \bmod 187 = 894432 \bmod 187 = 11$$
      • Quá trình giải mã bản mã $C = 11$: $$M = 11^{23} \bmod 187 = [(11^1) \times (11^2) \times (11^4) \times (11^8) \times (11^8)] \bmod 187 = 79720245 \bmod 187 = 88$$
  • Xử lý khối dữ liệu và các dạng tấn công:
    • Phân tích cơ chế mã hóa nhiều khối (chia nhỏ thông điệp thành các khối 4 chữ số thập phân, đại diện cho 2 ký tự chữ và số).
    • Khảo sát các kỹ thuật thám mã: tấn công vét cạn (brute-force), tấn công phân tích thừa số nguyên tố mô-đun $n$, và tấn công thông điệp ngắn đối với khóa công khai nhỏ $e = 3$ qua định lý số dư Trung Hoa (phòng chống bằng cách chèn thêm các bit giả ngẫu nhiên vào bản rõ).

Chương 3: Chương trình mã hóa và giải mã RSA

  • Trình bày mô tả thuật toán và cấu trúc mã nguồn thực thi của chương trình.
  • Toàn bộ thuật toán sinh khóa, mã hóa và giải mã RSA được đóng gói và thực thi thông qua tệp chương trình 3.py viết bằng ngôn ngữ Python.

Kết quả và đóng góp

  • Kết quả tính toán và thực nghiệm: Đồ án đã diễn giải chi tiết và chứng minh tính đúng đắn của thuật toán RSA cùng các cấu trúc toán học liên quan thông qua nhiều bộ số liệu cụ thể:
    • Tính toán thành công ví dụ RSA quy mô nhỏ: $p=17, q=11, n=187, e=7, d=23$, mã hóa bản rõ $M=88$ cho bản mã $C=11$ và giải mã chính xác về $M=88$.
    • Tính toán ví dụ RSA với $p=101, q=113, n=11413, \phi(n)=11200, b=3533, a=6597$, mã hóa bản rõ $M=9726$ thành $C=5761$ và giải mã về $9726$.
    • Minh họa thuật toán Elgamal với $p=2579, \alpha=2, a=765$, khóa công khai $\beta=949$, mã hóa bản rõ $M=1299$ với số ngẫu nhiên $k=853$ thành cặp $(y_1=435, y_2=2396)$ và giải mã chính xác về 1299.
    • Minh họa kiểm tra số nguyên tố Miller-Rabin với $n=29$ (xác nhận nguyên tố) và $n=221$ (phát hiện hợp số).
  • Giải pháp và đề xuất kỹ thuật của tác giả:
    • Đề xuất áp dụng mô hình bảo mật hỗn hợp (hybrid cryptography): sử dụng mật mã khóa công khai RSA để trao đổi khóa phiên và sử dụng mật mã đối xứng để mã hóa dữ liệu truyền thông nhằm tối ưu tốc độ.
    • Đề xuất kỹ thuật chèn bit giả ngẫu nhiên (padding) để chống lại các cuộc tấn công đoán trước thông điệp hoặc tấn công định lý thặng dư Trung Hoa khi sử dụng số mũ nhỏ $e=3$.
    • Ứng dụng kỹ thuật nhân bình phương nhị phân và định lý số dư Trung Hoa (CRT) để tối ưu hóa hiệu năng tính toán lũy thừa mô-đun lớn trong quá trình mã hóa và giải mã.
  • Đóng góp của đề tài: Hệ thống hóa hoàn chỉnh cơ sở toán học mật mã từ lý thuyết số đến thuật toán thực tế, đồng thời hiện thực hóa thành công chương trình mã hóa/giải mã RSA thông qua mã nguồn Python 3.py.

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

  • Hạn chế:
    • Các ví dụ tính toán số học và thử nghiệm thuật toán trong đồ án chủ yếu được minh họa trên các số nguyên có kích thước nhỏ và trung bình nhằm phục vụ mục đích kiểm chứng lý thuyết toán học.
    • Chương trình chưa đi sâu vào việc triển khai một cơ sở hạ tầng khóa công khai (PKI) hoàn chỉnh để quản lý, cấp phát và thu hồi chứng chỉ số trong môi trường mạng thực tế quy mô lớn.
  • Hướng nghiên cứu tiếp:
    • Mở rộng chương trình với các bộ sinh số nguyên tố ngẫu nhiên cực lớn (độ dài khóa 1024 bit, 2048 bit hoặc cao hơn) đáp ứng tiêu chuẩn an toàn hiện đại.
    • Tích hợp kiểm tra tính nguyên tố Miller-Rabin với số vòng lặp $t$ lớn trong quy trình tự động sinh khóa.
    • Ứng dụng mô hình mã hóa RSA vào các giao thức ký số điện tử và xây dựng hệ thống truyền thông bảo mật lai ghép kết hợp thuật toán mã hóa đối xứng.

Giá trị tham khảo

Đồ án là tài liệu tham khảo hữu ích cho:

  • Sinh viên và học viên: Thuộc các chuyên ngành Điện tử Viễn thông, Công nghệ Thông tin, An toàn Thông tin và Toán tin ứng dụng cần tài liệu nghiên cứu về lý thuyết số học mật mã và thuật toán khóa công khai.
  • Phần nội dung đáng tham khảo nhất:
    • Toàn bộ các bước chứng minh toán học và bảng tính mẫu trong Chương 1 (thuật toán Euclid mở rộng, hàm Euler, thuật toán Miller-Rabin, CRT và bảng logarithm rời rạc modulo 19).
    • Phân tích chi tiết quy trình tính toán lũy thừa nhị phân (Square-and-Multiply) và ví dụ số học từng bước của thuật toán RSA trong Chương 2.
    • Cấu trúc triển khai mã nguồn Python cho thuật toán RSA trong Chương 3 (3.py).

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

1. Hệ mật mã khóa công khai giải quyết được những nhược điểm cơ bản nào của hệ mật mã đối xứng?
Mật mã khóa công khai giải quyết được hai khó khăn lớn nhất của mã hóa đối xứng: loại bỏ yêu cầu phải có một kênh truyền an toàn để chia sẻ khóa bí mật giữa hai bên (bài toán phân phối khóa) và cung cấp cơ chế tạo lập chữ ký số giúp xác thực nguồn gốc thông điệp cũng như chống chối bỏ trách nhiệm.

2. Kỹ thuật tính lũy thừa nhị phân (Square-and-Multiply) hoạt động như thế nào để tối ưu tốc độ tính toán trong RSA?
Thay vì thực hiện hàng loạt phép nhân liên tiếp $a^b = a \times a \times \dots \times a$ (đòi hỏi $b-1$ phép nhân), thuật toán phân tích số mũ $b$ thành chuỗi nhị phân $b = \sum b_i 2^i$. Sau đó, quá trình tính toán chỉ cần lặp lại các phép bình phương liên tiếp kết hợp với phép nhân khi gặp bit 1 và liên tục rút gọn theo mô-đun $n$, giúp giảm đáng kể số lượng phép tính và giữ cho các giá trị trung gian không bị bùng nổ kích thước.

3. Vì sao việc chọn số mũ công khai nhỏ $e = 3$ lại tiềm ẩn rủi ro bảo mật và cách khắc phục là gì?
Nếu chọn $e = 3$ và cùng một thông điệp $M$ được gửi cho 3 người nhận khác nhau với các mô-đun nguyên tố cùng nhau $(n_1, n_2, n_3)$, kẻ tấn công có thể dùng định lý số dư Trung Hoa (CRT) để tính $M^3 \bmod (n_1 n_2 n_3)$. Vì $M < n_i$ nên $M^3 < n_1 n_2 n_3$, kẻ tấn công chỉ cần khai căn bậc 3 thông thường trên tập số thực để khôi phục trực tiếp $M$. Để phòng ngừa, văn bản chỉ rõ cần chèn thêm các bit giả ngẫu nhiên vào bản rõ trước khi mã hóa.

4. Xác suất sai số của thuật toán kiểm tra số nguyên tố Miller-Rabin được kiểm soát như thế nào?
Với một số lẻ $n$ là hợp số, xác suất để thuật toán Miller-Rabin đưa ra kết quả không xác định (không phát hiện ra $n$ là hợp số) với một cơ số $a$ ngẫu nhiên là nhỏ hơn $1/4$. Khi thực hiện lặp lại phép thử $t$ lần độc lập với các giá trị $a$ khác nhau, xác suất để một hợp số vượt qua tất cả $t$ lần thử nhỏ hơn $(1/4)^t$. Ví dụ với $t = 10$, xác suất sai số chỉ còn dưới $10^{-6}$, đảm bảo độ tin cậy thực tế rất cao.

5. Trong ví dụ số học mẫu của đồ án, các tham số khóa và kết quả mã hóa/giải mã thông điệp $M=88$ được tính toán như thế nào?
Với hai số nguyên tố $p = 17, q = 11$, tác giả xác định mô-đun $n = 187$ và $\phi(n) = 160$. Khóa công khai được chọn là $e = 7$, từ đó tính được khóa bí mật $d = 23$ qua giải thuật Euclid mở rộng. Khi mã hóa bản rõ $M = 88$, kết quả bản mã thu được là $C = 88^7 \bmod 187 = 11$. Khi giải mã, phép tính $M = 11^{23} \bmod 187$ khôi phục chính xác giá trị ban đầu là $88$.

Kết luận

Đồ án tốt nghiệp "Xây dựng chương trình mã hóa và giải mã RSA" của sinh viên Lê Thế Trị đã hệ thống hóa toàn diện cơ sở lý thuyết số học và nguyên lý hoạt động của mật mã học khóa công khai. Tác giả đã chứng minh chặt chẽ các định lý toán học nền tảng, phân tích chi tiết quy trình tính toán hiệu năng và các khía cạnh an toàn của hệ mật RSA. Đồng thời, đề tài đã hiện thực hóa thành công thuật toán bằng mã nguồn Python 3.py, mang lại giá trị tham khảo rõ ràng cho sinh viên và người nghiên cứu trong lĩnh vực an toàn thông tin và kỹ thuật viễn thông.