Tổng quan về giáo trình

Chương trình đào tạo đại học và sau đại học ngành Công nghệ Thông tin, An toàn Thông tin và Toán - Tin ứng dụng xác định môn học Bảo mật thông tin là học phần cơ sở chuyên ngành bắt buộc. Trong cấu trúc chương trình, Chương 4: Các hệ mật mã khoá công khai giữ vị trí trung tâm, cung cấp nền tảng toán học và kỹ thuật mật mã hiện đại, chuyển tiếp từ các mô hình mật mã đối xứng cổ điển sang mật mã bất đối xứng (asymmetric cryptography).

Mục tiêu học tập của chương hướng tới việc trang bị cho người học khả năng phân tích, thiết kế và đánh giá độ an toàn của các hệ mật mã khóa công khai. Kết thúc học phần, người học nắm vững bản chất toán học của các hàm một chiều có cửa sập (trapdoor one-way functions), thực hiện thành thạo các thuật toán số học trên vành số nguyên modulo lớn, hiểu rõ cơ chế vận hành của các lược đồ mã hóa kinh điển và nhận diện được các phương pháp thám mã tính toán.

Cấu trúc giáo trình được thiết kế theo hướng tiếp cận hình thức: đi từ việc mô tả các bài toán số học nền tảng, hệ thống hóa công cụ toán học hỗ trợ, định nghĩa cấu trúc đại số của các hệ mật mã, cho đến việc phân tích giải thuật phân tích nhân tử và giải logarithm rời rạc. Điểm đặc sắc của tài liệu là tính chặt chẽ trong chứng minh toán học, kết hợp việc lượng hóa độ phức tạp thuật toán (bậc $O$-lớn) với các ví dụ số học thực tế theo từng bước giải.

Nội dung kiến thức cốt lõi

Các chương/chủ đề chính

Nội dung trọng tâm của chương 4 bao gồm 6 chủ đề chuyên sâu:

  1. Mô hình mật mã khóa công khai và các bài toán khó: Giới thiệu lược đồ trao đổi Diffie - Hellman (1976), mô hình hệ thống bộ 5 $S = (P, C, K, E, D)$ với cặp khóa $(K', K'')$. Phân tích các bài toán nền tảng: phân tích số nguyên Blum $n = p \cdot q$, bài toán RSA, bài toán thặng dư bậc hai và ký hiệu Jacobi, bài toán căn bậc hai modulo $n$, bài toán logarithm rời rạc trên trường hữu hạn $GF(p)$, $GF(2^m)$ và đường cong Elliptic, bài toán Knapsack (tổng tập con) và bài toán giải mã tuyến tính.
  2. Thuật toán kiểm tra số nguyên tố theo xác suất: Phân loại thuật toán tất định và thuật toán xác suất (Monte Carlo thiên về có/không, Las Vegas). Chi tiết hóa giải thuật Solovay - Strassen dựa trên số giả nguyên tố Euler và ký hiệu Jacobi; giải thuật Miller - Rabin dựa trên phân tích $p - 1 = 2^s \cdot m$.
  3. Công cụ toán học số học và giải thuật tính toán nhanh: Thiết lập định lý phần dư Trung Hoa (CRT), định lý Fermat nhỏ, định lý Euler, định lý Lagrange về cấp phần tử nhóm, phần tử nguyên thủy của nhóm cyclic $\mathbb{Z}_p^*$. Kỹ thuật tính lũy thừa modulo lớn $x^e \bmod n$ thông qua thuật toán bình phương và nhân (Square-and-Multiply) và thuật toán bình phương liên tiếp.
  4. Hệ mật mã RSA và phân tích độ an toàn: Cấu tạo hệ mật Rivest - Shamir - Adleman (1977) trên vành $\mathbb{Z}_n$. Chứng minh tính đúng đắn dựa trên định lý Euler. Phân tích các mô hình thám mã: tấn công khi biết $\phi(n)$ qua phương trình bậc hai $p^2 - (n - \phi(n) + 1)p + n = 0$, giải thuật Las Vegas tìm căn bậc hai không tầm thường của $1 \bmod n$ khi biết số mũ giải mã $d$, và phương pháp khôi phục bản rõ từ rò rỉ bit cấp thấp (parity bit) hoặc phân nửa trên/dưới (half bit) qua tìm kiếm nhị phân.
  5. Hệ mật mã Rabin và các giải thuật phân tích số nguyên: Lược đồ Rabin trên số nguyên Blum $p, q \equiv 3 \pmod 4$ với hàm mã hóa $e_K(x) = x(x+B) \bmod n$ và tính đa trị trong giải mã. Các thuật toán phân tích thừa số nguyên tố: phép chia thử, phương pháp Pollard $p-1$, thuật toán Dixon, thuật toán sàng bậc hai (Quadratic Sieve) của Pomerance, sàng trường số và đường cong Elliptic.
  6. Hệ mật mã ElGamal và các hệ mật dựa trên bài toán NP-đầy đủ: Hệ mật ElGamal (1985) dựa trên logarithm rời rạc, yêu cầu số nguyên tố Sophie Germain $p = 2q + 1$ và rủi ro an toàn khi tái sử dụng số ngẫu nhiên $k$. Các giải thuật giải logarithm rời rạc: thuật toán Shanks (Baby-step Giant-step) và thuật toán Pohlig - Hellman. Hệ mật xếp ba lô Merkle - Hellman trên dãy siêu tăng và hệ mật McEliece xây dựng trên mã sửa sai Goppa $[n, k, d]$ kết hợp ma trận sinh ngụy trang $G' = SGP$.

Kiến thức nền tảng được xây dựng

Giáo trình thiết lập ba khối kiến thức lý thuyết cơ bản:

  • Lý thuyết số học đồng dư và cấu trúc đại số: Cấu trúc nhóm nhân $\mathbb{Z}_n^*$, tính chất nhóm cyclic, cấp của phần tử, thặng dư bậc hai và các phép biến đổi ký hiệu Legendre/Jacobi.
  • Lý thuyết hàm một chiều và cửa sập (Trapdoor One-way Functions): Bản chất của các hàm dễ tính toán theo chiều thuận (thời gian đa thức) nhưng khó đảo ngược nếu không có thông tin cửa sập $z$.
  • Lý thuyết độ phức tạp tính toán: Khái niệm về thuật toán thời gian đa thức $O(\log^d n)$, thời gian mũ $O(n^\alpha)$, định nghĩa lớp bài toán NP-đầy đủ, và nguyên lý rút gọn đa thức giữa các bài toán khó.

Kỹ năng phát triển

  • Kỹ năng kỹ thuật (Technical skills): Cài đặt và thực thi các phép toán modulo lớn, giải phương trình đồng dư bậc nhất/bậc hai, thực hiện thuật toán Euclid mở rộng tìm nghịch đảo modulo, và hiện thực các lược đồ mã hóa RSA, Rabin, ElGamal, Merkle-Hellman, McEliece.
  • Kỹ năng phân tích (Analytical skills): Đánh giá độ an toàn tính toán của khóa dựa trên độ dài bit, nhận diện điểm yếu khi tham số toán học không đạt chuẩn (ví dụ $p-1$ trơn trong Pollard $p-1$, hoặc $p-1$ chỉ có thừa số nhỏ trong Pohlig-Hellman), và phân tích độ phức tạp thời gian/bộ nhớ của các thuật toán thám mã.
  • Kỹ năng thực hành (Practical competencies): Lựa chọn kích thước tham số an toàn trong thực tế (số nguyên Blum $\ge 200$ chữ số, mã Goppa $[1024, 524, 101]$), phát hiện rò rỉ kênh truyền qua các bit chỉ thị.

Phương pháp giảng dạy và học tập

Giáo trình áp dụng phương pháp sư phạm diễn dịch kết hợp quy nạp toán học. Mỗi chủ đề bắt đầu từ việc phát biểu bài toán tổng quát, định nghĩa cấu trúc toán học hình thức, chứng minh các định lý làm tiền đề, thiết lập giải thuật thực thi chi tiết, và củng cố bằng các ví dụ tính toán số học cụ thể.

+-------------------------------------------------------------+
|   Quy trình sư phạm trong giáo trình:                       |
|   1. Định nghĩa bài toán toán học                           |
|      -> 2. Chứng minh định lý & Tính đúng đắn                |
|         -> 3. Mô tả mã giả giải thuật                       |
|            -> 4. Ví dụ tính toán số học cụ thể              |
|               -> 5. Phân tích độ an toàn & Bài toán thám mã  |
|                  -> 6. Hệ thống bài tập tự giải             |
+-------------------------------------------------------------+

Hệ thống ví dụ minh họa trong tài liệu cung cấp số liệu tính toán chi tiết:

  • Tính ký hiệu Jacobi $\left(\frac{7411}{9283}\right)$ qua 4 tính chất rút gọn.
  • Thực thi lũy thừa nhanh $9726^{3533} \bmod 11413 = 5761$ qua bảng 12 bước nhị phân.
  • Sinh khóa và giải mã RSA với $p=53, q=61, n=3233, e=17, d=2753$.
  • Giải mã Rabin với $n=77, B=9, y=22$, tìm 4 bản rõ qua định lý phần dư Trung Hoa.
  • Phân tích số $n=15770708441$ bằng thuật toán Pollard $p-1$ với $B=180$ và phương pháp Dixon với cơ sở nhân tử $B={2, 3, 5, 7, 11, 13}$.
  • Giải logarithm rời rạc $\log_3 525 \bmod 809$ qua thuật toán Shanks với hai danh sách $L_1, L_2$.
  • Lập mã và sửa sai bản tin $x=(1,1,0,1)$ với hệ mật McEliece dùng mã Hamming $[7,4,3]$.

Phương pháp đánh giá người học được xây dựng thông qua hệ thống bài tập cuối chương: tính phần tử nghịch đảo bằng thuật toán Euclid mở rộng, giải hệ phương trình đồng dư tuyến tính bằng CRT, giải phương trình đồng dư bậc hai $x^2 \equiv 4 \pmod{35}$, tính lũy thừa modulo nhanh, và thiết lập tham số cho hệ mật RSA với các điều kiện ràng buộc.

Hướng dẫn tự học: Người học cần tự thực hiện lại các bước biến đổi ma trận và phép tính modulo trong từng ví dụ minh họa bằng tính toán tay trước khi chuyển sang cài đặt các hàm toán học trên môi trường lập trình.

Điểm nổi bật và cập nhật

Giáo trình hệ thống hóa toàn diện các thành tựu nền tảng của mật mã học khóa công khai từ giai đoạn khởi đầu đến các bước phát triển kinh điển:

  • Tích hợp các mốc lịch sử phát triển: Ghi nhận công trình của Diffie và Hellman (1976), hệ mật RSA của Rivest, Shamir và Adleman (1977), hệ mật Merkle - Hellman (1978), hệ mật McEliece (1978), và hệ mật ElGamal (1985).
  • Cập nhật các kết quả thám mã và phá khóa thực tế: Trình bày việc Shamir sử dụng thuật toán quy hoạch nguyên của Lenstra để phá vỡ hệ mật Merkle - Hellman vào đầu những năm 1980. Tài liệu dẫn chứng các mốc phân tích số nguyên thực tế: năm 1983 phân tích số 69 chữ số (thừa số của $2^{251}-1$) do Davis, Holdredye và Simmons thực hiện; năm 1988 Brent phân tích tham số Fermat $2^{2048}-1$ bằng phương pháp đường cong Elliptic; năm 1989 Lenstra và Manasse phân tích số 106 chữ số bằng thuật toán sàng bậc hai phân tán qua thư điện tử.
  • Tiêu chuẩn tham số an toàn kỹ thuật: Giáo trình đưa ra các khuyến nghị về độ dài tham số: số nguyên $n$ trong RSA cần đạt kích thước trên 200 chữ số thập phân ($p, q$ khoảng 150 chữ số); số nguyên tố $p$ trong ElGamal phải có ít nhất 150 chữ số và thuộc dạng Sophie Germain ($p = 2q + 1$); cấu hình tham số mã Goppa trong McEliece là $[1024, 524, 101]$ với $m=10, t=50$, kích thước khóa công khai là ma trận nhị phân cấp $524 \times 1024$.

Đối tượng sử dụng giáo trình

Đối tượng Yêu cầu kiến thức tiên quyết Mục đích & Cách thức sử dụng
Sinh viên đại học (Năm 3, 4 ngành An toàn Thông tin, CNTT, Khoa học Máy tính) Toán rời rạc, Đại số tuyến tính, Cấu trúc dữ liệu và Giải thuật, Lý thuyết số cơ bản Giáo trình chính khóa học phần Bảo mật thông tin; học lý thuyết, làm bài tập tính toán modulo và lập trình mô phỏng thuật toán
Học viên cao học (Chuyên ngành Khoa học Máy tính, Hệ thống Thông tin) Lý thuyết độ phức tạp thuật toán, Đại số trừu tượng (Nhóm, Vành, Trường) Tài liệu nghiên cứu chuyên sâu về an toàn tính toán, phân tích độ phức tạp của các bài toán NP-đầy đủ và thám mã đại số
Giảng viên đại học Chuyên môn Mật mã học và An toàn mạng Khung đề cương bài giảng chuẩn, khai thác hệ thống ví dụ từng bước và ngân hàng bài tập cuối chương
Kỹ sư hệ thống & Tự học Lập trình ứng dụng, Kiến thức cơ bản về mã hóa khóa công khai Tài liệu tham khảo tra cứu cơ chế nội tại của các lược đồ mã hóa (RSA, Rabin, ElGamal) và thuật toán phân tích nhân tử

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

1. Giáo trình này phù hợp với ai?

Tài liệu được thiết kế cho sinh viên đại học từ năm thứ ba trở đi, học viên cao học thuộc khối ngành Công nghệ Thông tin, An toàn Thông tin, Toán - Tin, cũng như các kỹ sư an toàn hệ thống cần hiểu bản chất toán học của các thuật toán mã hóa.

2. Cần kiến thức nền nào để học?

Người học cần hoàn thành các học phần tiên quyết: Toán rời rạc, Đại số đại cương (lý thuyết nhóm cyclic, đồng dư thức), Cấu trúc dữ liệu và Giải thuật (đặc biệt là khái niệm bậc $O$-lớn và phân tích độ phức tạp thời gian/không gian).

3. Điểm khác biệt của giáo trình so với các tài liệu khác là gì?

Giáo trình tập trung sâu vào cơ sở lý thuyết số học hình thức và phân tích định lượng độ an toàn. Tài liệu không dừng lại ở việc mô tả giao thức mà chứng minh chi tiết tính đúng đắn toán học, phân loại rõ thuật toán Monte Carlo/Las Vegas, và trình bày thuật toán thám mã đi kèm độ phức tạp tính toán.

4. Làm sao để tự học giáo trình hiệu quả?

Người học nên tiếp cận tuần tự theo cấu trúc chương: nắm vững các định lý số học nền tảng (mục 4.5), theo dõi chi tiết từng bước của các bảng tính ví dụ mẫu (như bảng tính lũy thừa nhanh, thuật toán Shanks, giải mã McEliece), sau đó tự giải toàn bộ bài tập ở mục cuối chương.

5. Có tài liệu bổ trợ nào kèm theo không?

Tài liệu tích hợp sẵn hệ thống ví dụ có lời giải chi tiết, bảng tính toán trung gian (bảng nhị phân, danh sách sắp thứ tự $L_1, L_2$) và phần bài tập cuối chương gồm các dạng toán tìm nghịch đảo Euclid mở rộng, giải hệ phương trình đồng dư Trung Hoa, và thiết lập lược đồ RSA.

Kết luận

Chương 4 của giáo trình Bảo mật thông tin cung cấp khung lý thuyết hoàn chỉnh và chặt chẽ về các hệ mật mã khóa công khai. Giá trị học thuật cốt lõi của tài liệu nằm ở sự kết hợp giữa các cấu trúc toán học trừu tượng (nhóm cyclic, trường hữu hạn, vành đồng dư, mã Goppa) với việc hiện thực hóa các thuật toán mật mã kinh điển (RSA, Rabin, ElGamal, Merkle - Hellman, McEliece).

Lộ trình học tập khuyến nghị bắt đầu từ việc làm chủ công cụ số học (định lý Euler, định lý Fermat, định lý phần dư Trung Hoa), nghiên cứu thuật toán kiểm tra số nguyên tố xác suất (Solovay - Strassen, Miller - Rabin), phân tích cơ chế sinh khóa/mã hóa/giải mã của từng hệ mật, và kết thúc bằng việc đánh giá các giải thuật thám mã tính toán. Các nguồn tài liệu bổ sung được gợi ý bao gồm các công trình nghiên cứu chuyên sâu về phân tích số nguyên bằng sàng trường số và các hệ mật mã xây dựng trên đường cong Elliptic.