# Cryptography 1

**Chào mừng đến với sê-ri chia sẻ kiến thức Cryptography!**

Xin chào mọi người! Tôi rất vui được chia sẻ với các bạn những kiến thức về **Cryptography** mà tôi đã học được. Đây là bài viết đầu tiên trong chuỗi sê-ri về mật mã, nơi tôi sẽ trình bày những khái niệm quan trọng và cốt lõi của lĩnh vực này. Trước khi bắt đầu, tôi khuyên bạn nên trang bị một số kiến thức toán học nền tảng, đặc biệt là **xác suất rời rạc**, có thể tham khảo tại [Discrete Probability - High School Mathematics Extensions](https://en.wikibooks.org/wiki/High_School_Mathematics_Extensions/Discrete_Probability), và **lý thuyết số cơ bản**, một phần quan trọng trong nhiều thuật toán mật mã, có thể học từ sách [A Computational Introduction to Number Theory and Algebra – Victor Shoup](https://shoup.net/ntb/ntb-v2.pdf).

Trong sê-ri này, tôi chủ yếu tham khảo cuốn sách *A Graduate Course in Applied Cryptography* của Dan Boneh và Victor Shoup, một tài liệu nhập môn rất hay và dễ tiếp cận, có thể xem mục lục tại [đây](https://toc.cryptobook.us/). Nội dung bài viết đầu tiên này sẽ giới thiệu về **mật mã Shannon** – nền tảng đầu tiên của lý thuyết mật mã, cùng với khái niệm **bảo mật hoàn hảo**, định nghĩa chặt chẽ và giới hạn của một hệ mã an toàn tuyệt đối.

Hy vọng mọi người sẽ theo dõi và ủng hộ sê-ri này! Nếu có bất kỳ thắc mắc hay ý kiến đóng góp, hãy để lại bình luận nhé. Bây giờ, hãy cùng bước vào chương đầu tiên: **Mật mã Shannon và bảo mật hoàn hảo!** 🔐

## Định nghĩa mật mã Shannon

Chúng ta sẽ bắt đầu với khái niệm mã hóa, giả sử Alice và Bob chia sẻ một khóa bí mật $k$. Alice muốn gửi một thông điệp $m$ cho Bob qua mạng mà vẫn giữ được tính bí mật của $m$ trước sự nghe lén của kẻ tấn công. Chúng ta sẽ bắt đầu phát triển các kỹ thuật cơ bản để giải quyết vấn đề này.

Ngoài việc truyền thông điệp qua mạng, các kỹ thuật này cũng cho phép Alice lưu trữ một tệp trên đĩa mà không ai khác có quyền truy cập vào đĩa có thể đọc được, nhưng Alice vẫn có thể đọc tệp sau này.

Ta gọi một cơ chế cơ bản để mã hóa một thông điệp bằng một khóa bí mật được gọi là **mật mã** (cipher) hoặc **hệ mã hóa** (encryption scheme). Ta có một khái niệm đơn giản hơn của mật mã, được gọi là **mật mã Shannon** (Shannon cipher). Một mật mã Shannon bao gồm một cặp hai hàm số được gọi là $\mathcal{E} = (E, D)$:

- **Hàm mã hóa $E$** nhận đầu vào là một khóa $k$ và một thông điệp $m$ (còn gọi là bản rõ - plaintext), và tạo ra bản mã $c = E(k, m)$. Ta nói rằng $c$ là bản mã của $m$ dưới khóa $k$.
- **Hàm giải mã $D$** nhận đầu vào là một khóa $k$ và một bản mã $c$, và tạo ra thông điệp $m = D(k, c)$. Ta nói rằng $m$ là bản rõ được giải mã từ $c$ dưới khóa $k$.

- **Tính đúng đắn**: Quá trình giải mã phải khôi phục lại chính xác bản gốc. Điều này có nghĩa là với mọi khóa $k$ và mọi thông điệp $m$, ta phải có:
$$
D(k, E(k, m)) = m
$$

Một cách formal hơn, giả sử:
- $\mathcal{K}$ là tập hợp tất cả các khóa (**không gian khóa**)
- $\mathcal{M}$ là tập hợp tất cả các thông điệp (**không gian thông điệp**)
- $\mathcal{C}$ là tập hợp tất cả các bản mã (**không gian bản mã**)

Khi đó, ta có thể mô tả hàm mã hóa và giải mã là $E: \mathcal{K} \times \mathcal{M} \to \mathcal{C}$ và $D: \mathcal{K} \times \mathcal{C} \to \mathcal{M}$. Và ta nói rằng hệ mã $\mathcal{E}$ được định nghĩa trên bộ ba $(\mathcal{K}, \mathcal{M}, \mathcal{C})$.

Để dễ hiểu hơn, ta có quá trình mã hóa và giải mã như sau. Giả sử Alice và Bob muốn sử dụng một hệ mã để Alice có thể gửi thông điệp cho Bob. Họ cần phải thỏa thuận trước về một khóa bí mật $k \in \mathcal{K}$. Sau khi có khóa:
- Khi Alice muốn gửi thông điệp $m \in M$ cho Bob, cô sẽ mã hóa nó bằng khóa $k$ để nhận được bản mã $c = E(k, m) \in \mathcal{C}$. Sau đó, Alice gửi $c$ cho Bob qua một kênh truyền thông.
- Khi Bob nhận được bản mã $c$, anh ta sẽ giải mã nó bằng khóa $k$, $m = D(k, c)$. Nhờ tính đúng đắn của hệ mã, Bob chắc chắn nhận được chính xác thông điệp $m$ ban đầu.
- Giả định rằng bản mã $c$ không bị thay đổi trong quá trình truyền từ Alice đến Bob. Tuy nhiên, mục tiêu của hệ mã là đảm bảo rằng ngay cả khi kẻ nghe lén thu được $c$, chúng không thể suy luận được quá nhiều về thông điệp $m$.

Trong thực tế, khóa, thông điệp và bản mã thường được biểu diễn dưới dạng chuỗi byte.
- Các khóa thường có độ dài cố định, ví dụ: **128-bit (16 byte)**.
- Thông điệp và bản mã có thể có độ dài cố định hoặc biến đổi, từ một bit duy nhất cho đến một tệp tin lớn như **video 1GB**, **bài hát 10MB**, hoặc **email 1KB**.
- Ngoài dạng chuỗi bit, chúng cũng có thể là các đối tượng toán học khác như **số nguyên, đa thức, ma trận** hoặc **các phần tử trong nhóm số học**.

Trong lý thuyết, ta thường giả định rằng $\mathcal{K}, \mathcal{M}, \mathcal{C}$ là các tập hợp hữu hạn. Điều này giúp đơn giản hóa mô hình, mặc dù trong thực tế, một số hệ thống có thể hỗ trợ thông điệp có độ dài không giới hạn. Tôi sẽ giới thiệu cho các bạn một số ứng dụng được áp dụng.

### **Mật mã One-Time Pad (OTP)**

Mật mã OTP là một hệ mã Shannon $\mathcal{E} = (E, D)$, trong đó khóa, thông điệp và bản mã đều là các chuỗi bit có cùng độ dài $L$, $\mathcal{K} := \mathcal{M} := \mathcal{C} := \{0,1\}^L$. Với khóa $k \in \{0,1\}^L$ và thông điệp $m \in \{0,1\}^L$, quá trình mã hóa và giải mã được định nghĩa như sau:
- **Mã hóa**: $E(k, m) := k \oplus m$
- **Giải mã**: $D(k, c) := k \oplus c$

Trong đó, $\oplus$ là phép toán XOR (exclusive-OR) từng bit. Các tính chất của XOR:
- **Tính giao hoán**: $x \oplus y = y \oplus x$
- **Tính kết hợp**: $x \oplus (y \oplus z) = (x \oplus y) \oplus z$
- **Phần tử trung lập**: $x \oplus 0^L = x$
- **Phép đảo**: $x \oplus x = 0^L$

Kiểm tra tính đúng đắn:
$$
D(k, E(k, m)) = D(k, k \oplus m) = k \oplus (k \oplus m) = (k \oplus k) \oplus m = 0^L \oplus m = m
$$

### **Mật mã One-Time Pad với độ dài biến đổi**

Hệ mã này giống với OTP nhưng cho phép thông điệp có độ dài tối đa $L$.
- **Không gian khóa**: $\mathcal{K} := \{0,1\}^L$
- **Không gian thông điệp và bản mã**: $\mathcal{M} := \mathcal{C} := \{0,1\}^{\leq L}$

Với thông điệp $m$ có độ dài $\ell$, mã hóa và giải mã được định nghĩa như sau:
- **Mã hóa**: $E(k, m) := k[0 \dots \ell -1] \oplus m$
- **Giải mã**: $D(k, c) := k[0 \dots \ell -1] \oplus c$

Trong đó, $k[0 \dots \ell -1]$ là đoạn đầu tiên của khóa $k$ có độ dài $\ell$.

### **Mật mã thay thế (Substitution Cipher)**

Mật mã thay thế là một phương pháp mã hóa trong đó mỗi ký tự trong thông điệp gốc được thay thế bằng một ký tự khác theo một quy tắc nhất định.

- **Bảng chữ cái**: Gồm một tập hợp hữu hạn các ký tự, ví dụ: 26 chữ cái (A–Z) và khoảng trắng.
- **Không gian thông điệp & bản mã**: Là tập hợp tất cả các chuỗi ký tự có độ dài cố định $L$, ký hiệu là $\mathcal{M} = \mathcal{C} = \Sigma^L$.
- **Không gian khóa**: Mỗi khóa là một **hoán vị** (hoán đổi vị trí) của các ký tự trong bảng chữ cái $\Sigma$, tức là tập hợp khóa có kích thước $|\mathcal{K}| = |\Sigma|!$ (rất lớn).

Giả sử ta có một hoán vị khóa $k$, tức là một cách sắp xếp lại các ký tự trong bảng chữ cái:

- **Mã hóa**: Mỗi ký tự trong thông điệp gốc được thay thế bằng ký tự tương ứng theo khóa $k$, $E(k, m) = (k(m[0]), k(m[1]), ..., k(m[L-1]))$. Trong đó, $m[i]$ là ký tự thứ $i$ của thông điệp $m$.
- **Giải mã**: Áp dụng hoán vị ngược $k^{-1}$ để khôi phục thông điệp ban đầu, $D(k, c) = (k^{-1}(c[0]), k^{-1}(c[1]), ..., k^{-1}(c[L-1]))$. Trong đó, $k^{-1}$ là phép hoán vị đảo ngược của $k$, giúp chuyển từ bản mã về bản gốc.

### **Mật mã cộng modulo $n$**

Hệ mã này định nghĩa như sau:
- **Không gian khóa, thông điệp và bản mã**: $\mathcal{K} = \mathcal{M} = \mathcal{C} = \{0, \dots, n-1\}$
- **Mã hóa**: $E(k, m) = (m + k) \mod n$
- **Giải mã**: $D(k, c) = (c - k) \mod n$

Tính đúng đắn: $D(k, E(k, m)) = (m + k - k) \mod n = m$

## Bảo mật hoàn hảo

Cho đến nay, chúng ta chỉ mới định nghĩa cú pháp cơ bản và các yêu cầu về tính đúng đắn của một mật mã Shannon. Tiếp theo, chúng ta cần đặt ra câu hỏi là một mật mã “bảo mật” là gì? Cảm giác mách bảo rằng một mật mã bảo mật là một hệ thống trong đó một thông điệp được mã hóa vẫn được “che giấu tốt”, ngay cả khi kẻ tấn công quan sát được bản mã. Tuy nhiên, việc chuyển hóa khái niệm trực quan này thành một định nghĩa có ý nghĩa toán học và phù hợp với thực tế là một thách thức lớn. Mặc dù các hệ thống mật mã đã được sử dụng trong nhiều thế kỷ, nhưng chỉ trong vài thập kỷ gần đây, các định nghĩa bảo mật chặt chẽ về mặt toán học mới được phát triển.

Tiếp theo, chúng ta sẽ xây dựng khái niệm toán học về **bảo mật hoàn hảo** — đây là tiêu chuẩn vàng trong bảo mật (ít nhất là khi chúng ta chỉ quan tâm đến việc mã hóa một thông điệp duy nhất và không quan tâm đến tính toàn vẹn). Chúng ta cũng sẽ thấy rằng có thể đạt được mức độ bảo mật này; thực tế, chúng ta sẽ chứng minh rằng **one-time pad** thỏa mãn định nghĩa này. Tuy nhiên, **one-time pad** không thực tế vì khóa phải có độ dài bằng thông điệp: nếu Alice muốn gửi một tập tin 1GB cho Bob, họ phải chia sẻ một khóa dài 1GB! Thật không may, điều này không thể tránh khỏi: chúng ta cũng sẽ chứng minh rằng **bất kỳ mật mã nào có bảo mật hoàn hảo cũng phải có không gian khóa ít nhất lớn bằng không gian thông điệp**. Điều này thúc đẩy việc phát triển một định nghĩa bảo mật yếu hơn nhưng vẫn chấp nhận được trong thực tế, cho phép mã hóa thông điệp dài bằng các khóa ngắn.

Nếu Alice mã hóa một thông điệp $m$ bằng khóa $k$, và một kẻ tấn công nghe lén thu được bản mã $c$, thì Alice chỉ có thể giữ $m$ bí mật nếu khóa $k$ khó đoán. Điều này có nghĩa là ít nhất $k$ phải được chọn ngẫu nhiên từ một không gian khóa lớn. Khi nói rằng $m$ được “che giấu tốt”, điều đó có nghĩa là việc xác định $m$ hoàn toàn từ $c$ mà không biết $k$ là rất khó; tuy nhiên, điều này vẫn chưa đủ. Mặc dù kẻ tấn công có thể không biết $k$, nhưng chúng ta giả định rằng hắn biết thuật toán mã hóa và phân bố của khóa $k$. Thực tế, chúng ta sẽ giả định rằng khi một thông điệp được mã hóa, khóa $k$ luôn được chọn ngẫu nhiên theo phân phối đều từ không gian khóa.

Kẻ tấn công cũng có thể có một số kiến thức về thông điệp được mã hóa — do hoàn cảnh, hắn có thể biết rằng tập hợp các thông điệp có thể xảy ra khá nhỏ và biết xác suất của từng thông điệp. Ví dụ, giả sử kẻ tấn công biết rằng thông điệp $m$ có thể là một trong hai khả năng là $m_0 = \text{"ATTACK AT DAWN"}$, $m_1 = \text{"ATTACK AT DUSK"}$ và rằng Alice có xác suất bằng nhau khi chọn một trong hai thông điệp này. Nếu không thấy bản mã $c$, kẻ tấn công có xác suất đoán đúng là 50%. Nhưng khi hắn biết $c$, có thể cả hai thông điệp vẫn có thể xảy ra; tức là tồn tại các khóa $k_0$ và $k_1$ sao cho: $E(k_0, m_0) = c$, $E(k_1, m_1) = c$. Do đó, hắn không thể chắc chắn $m = m_0$ hay $m = m_1$. Tuy nhiên, hắn vẫn có thể đoán. Giả sử có 800 khóa $k_0$ sao cho $E(k_0, m_0) = c$ và 600 khóa $k_1$ sao cho $E(k_1, m_1) = c$. Khi đó, xác suất đoán đúng tối ưu của kẻ tấn công là $\frac{800}{800 + 600} \approx 57\%$. Điều này tốt hơn so với xác suất $50\%$ khi không biết bản mã. Định nghĩa chính thức của bảo mật hoàn hảo loại trừ hoàn toàn khả năng này, tức là việc biết bản mã không làm tăng xác suất đoán đúng thông điệp, cũng như không cho phép xác định bất kỳ thuộc tính nào của thông điệp.

Không trì hoãn thêm nữa, chúng ta định nghĩa bảo mật hoàn hảo một cách chính thức. Trong định nghĩa này, chúng ta xem xét một thí nghiệm ngẫu nhiên trong đó khóa $\mathbf{k}$ được chọn theo phân phối đều từ không gian khóa. Chúng ta ký hiệu $\mathbf{k}$ là biến ngẫu nhiên biểu diễn khóa này. Với mỗi thông điệp $m$, ta định nghĩa $E(\mathbf{k}, m)$ là một biến ngẫu nhiên khác, biểu diễn kết quả của việc áp dụng hàm mã hóa lên khóa ngẫu nhiên $\mathbf{k}$ và thông điệp $m$. Do đó, mỗi thông điệp $m$ sinh ra một biến ngẫu nhiên khác nhau $E(\mathbf{k}, m)$.

### Định nghĩa (Bảo mật hoàn hảo)

Cho $\mathcal{E} = (E, D)$ là một mật mã Shannon được xác định trên bộ $(\mathcal{K}, \mathcal{M}, \mathcal{C})$. Xét một thí nghiệm ngẫu nhiên trong đó biến ngẫu nhiên $k$ được phân phối đều trên tập khoá $\mathcal{K}$. Nếu với mọi $m_0, m_1 \in \mathcal{M}$ và mọi $c \in \mathcal{C}$, ta có $\Pr[E(k, m_0) = c] = \Pr[E(k, m_1) = c]$ thì ta nói rằng $\mathcal{E}$ là một mật mã Shannon bảo mật hoàn hảo.

Có nhiều cách phát biểu tương đương của định nghĩa bảo mật hoàn hảo mà chúng ta sẽ xem xét. Dưới đây là một số phát biểu tương đương:

**Định lý 1** Cho $\mathcal{E} = (E, D)$ là một mật mã Shannon được xác định trên bộ $(\mathcal{K}, \mathcal{M}, \mathcal{C})$. Khi đó, các điều kiện sau là tương đương:

1. $\mathcal{E}$ là bảo mật hoàn hảo.
2. Với mọi $c \in \mathcal{C}$, tồn tại một số nguyên $N_c$ (có thể phụ thuộc vào $c$) sao cho với mọi $m \in \mathcal{M}$, ta có $\left| \{ k \in \mathcal{K} \mid E(k, m) = c \} \right| = N_c$.
3. Nếu biến ngẫu nhiên $k$ được phân phối đều trên $\mathcal{K}$, thì mỗi biến ngẫu nhiên $E(k, m)$, với mọi $m \in \mathcal{M}$, cũng là phần phối đều.

Ta sẽ chứng minh định lý trên. Trước tiên, ta có thể phát biểu lại điều kiện (2) như sau, với mọi $c \in \mathcal{C}$, tồn tại một số $P_c$ (phụ thuộc vào $c$) sao cho với mọi $m \in \mathcal{M}$, ta có $\Pr[E(\mathbf{k}, m) = c] = P_c$. Ở đây, $\mathbf{k}$ là một biến ngẫu nhiên phân phối đều trên $\mathcal{K}$, có nghĩa là $P_c = \frac{N_c}{|\mathcal{K}|}$, trong đó $N_c$ là số lượng khoá $k$ sao cho $E(k, m) = c$ theo phát biểu ban đầu của (2). Từ đây, ta có thể dễ dàng nhận ra rằng $E(k,m)$ cũng là phân phối đều hay nói cách khác phát biểu (2) cũng chính là phát biểu (3).

Tiếp theo, ta sẽ chứng minh $(1) \Rightarrow (2)$. Giả sử $\mathcal{E}$ là bảo mật hoàn hảo. Ta chứng minh điều kiện (2). Lấy một bản mã cố định $c \in \mathcal{C}$. Chọn một thông điệp tuỳ ý $m_0 \in \mathcal{M}$. Đặt $P_c := \Pr[E(k, m_0) = c]$. Từ định nghĩa bảo mật hoàn hảo, với mọi $m \in M$, ta có $\Pr[E(k, m) = c] = \Pr[E(k, m_0) = c] = P_c$. Điều này chứng minh (2).

Cuối cùng, ta chứng minh $(2) \Rightarrow (1)$. Giả sử (2) đúng, ta chứng minh $\mathcal{E}$ là bảo mật hoàn hảo. Xét hai thông điệp bất kỳ $m_0, m_1 \in M$ và một bản mã $c \in \mathcal{C}$. Theo (2), ta có $\Pr[E(k, m_0) = c] = P_c = \Pr[E(k, m_1) = c]$. Điều này đúng với mọi $m_0, m_1$, do đó $\mathcal{E}$ thỏa mãn định nghĩa bảo mật hoàn hảo.

Quay lại với các ví dụ của Shannon, đầu tiên ta sẽ chứng minh rằng **one-time pad** là bảo mật hoàn hảo. Giả sử mật mã Shannon $E = (E, D)$ là một one-time pad và được xác định trên bộ $(\mathcal{K}, \mathcal{M}, \mathcal{C})$, trong đó $\mathcal{K} := \mathcal{M} := \mathcal{C} := \{0,1\}^L$.

Với mọi thông điệp cố định $m \in \{0,1\}^L$ và bản mã $c \in \{0,1\}^L$, tồn tại duy nhất một khoá $k \in \{0,1\}^L$ thỏa mãn phương trình $k \oplus m = c$, cụ thể là $k := m \oplus c$. Do đó, $\mathcal{E}$ thoả mãn điều kiện (ii) trong Định lý 1 (với $N_c = 1$ cho mỗi $c$).

Xét lại **one-time pad có độ dài biến đổi**, Hệ mã này không thỏa mãn định nghĩa bảo mật hoàn hảo của chúng ta, bởi vì một bản mã có cùng độ dài với bản rõ tương ứng. Thật vậy, giả sử ta chọn một chuỗi bất kỳ có độ dài 1, gọi là $m_0$, và một chuỗi có độ dài 2, gọi là $m_1$. Ngoài ra, giả sử $c$ là một chuỗi có độ dài 1 bất kỳ và $k$ là một biến ngẫu nhiên được phân phối đều trên không gian khoá. Khi đó, ta có $\Pr[E(k, m_0) = c] = \frac{1}{2}$ và $\Pr[E(k, m_1) = c] = 0$. Điều này tạo ra một phản ví dụ trực tiếp đối với Định nghĩa về bảo mật hoàn hảo.

Ta có nhận xét rằng one-time pad có độ dài biến đổi không thể thỏa mãn định nghĩa bảo mật hoàn hảo đơn giản vì bất kỳ bản mã nào cũng làm lộ độ dài của bản rõ tương ứng. Tuy nhiên, theo một nghĩa nào đó (mà chúng ta chưa xác định rõ ngay bây giờ), đây là thông tin duy nhất bị rò rỉ. Điều này có thể được xem là một vấn đề của hệ mã hoặc một vấn đề của định nghĩa bảo mật hoàn hảo.

- Một mặt, có thể tưởng tượng những tình huống trong đó độ dài của thông điệp thay đổi đáng kể. Trong trường hợp đó, ta có thể **đệm (pad)** các thông điệp ngắn để làm cho tất cả thông điệp có cùng độ dài, nhưng điều này có thể không thực tế do lãng phí băng thông.
- Mặt khác, trong một số ứng dụng nhất định, việc rò rỉ chỉ riêng độ dài của thông điệp cũng có thể nguy hiểm. Ví dụ, nếu bạn mã hoá một câu trả lời “yes” hoặc “no” cho một câu hỏi, thì độ dài của mã ASCII tương ứng của hai chuỗi này sẽ tiết lộ toàn bộ nội dung. Vì vậy, bạn nên đệm từ “no” để nó có độ dài bằng “yes” (3 ký tự).

Hãy xem xét lại **mật mã thay thế (substitution cipher)**. Có một số cách khác nhau để thấy rằng hệ mã này không bảo mật hoàn hảo.

Ví dụ, chọn hai thông điệp $m_0, m_1 \in \Sigma^L$ sao cho hai thành phần đầu tiên của $m_0$ bằng nhau, nhưng hai thành phần đầu tiên của $m_1$ khác nhau, tức là $m_0[0] = m_0[1],$ nhưng $m_1[0] \neq m_1[1]$. Khi đó, với mỗi khóa $k$ là một hoán vị trên bảng chữ cái $\Sigma$, nếu $c = E(k, m_0)$ thì ta có $c[0] = c[1]$, trong khi nếu $c = E(k, m_1)$, thì $c[0] \neq c[1]$.

Do đó, nếu $k$ được chọn ngẫu nhiên theo phân phối đều trên không gian khóa, thì các phân phối xác suất của $E(k, m_0)$ và $E(k, m_1)$ sẽ không giống nhau vì ta có thể phân biệt được dựa vào 2 thành phần đầu tiên của $c$. Điều này mâu thuẫn với định nghĩa bảo mật hoàn hảo.

Ngay cả điểm yếu mô tả ở trên có thể vẫn còn mang tính lý thuyết. Một kiểu tấn công thực tế hơn vào **mật mã thay thế** có thể diễn ra như sau. Giả sử hệ mã thay thế được dùng để mã hóa các email. Như chúng ta biết, một email thường bắt đầu với **phần tiêu đề chuẩn**, chẳng hạn như chuỗi `"FROM"`. Giả sử bản mã $c \in \Sigma^L$ bị một kẻ tấn công chặn được. Khóa bí mật thực ra chỉ là một hoán vị $k$ trên bảng chữ cái $\Sigma$. Kẻ tấn công biết rằng $c[0 \dots 3] = (k(F), k(R), k(O), k(M))$.

Do đó, nếu thông điệp gốc là $m \in \Sigma^L$, kẻ tấn công có thể xác định được tất cả vị trí trong $m$ nơi xuất hiện chữ **F**, chữ **R**, chữ **O**, và chữ **M**. Chỉ từ thông tin này, cùng với các yếu tố ngữ cảnh của email và các thống kê tần suất chữ cái, kẻ tấn công có thể suy luận được khá nhiều về nội dung thông điệp ban đầu.

Xét **mật mã one-time pad theo phép cộng**. Ta có thể dễ dàng kiểm tra rằng hệ mã này là **bảo mật hoàn hảo**. Thật vậy, nó thỏa mãn điều kiện (ii) trong Định lý 1 (với $N_c = 1$ cho mỗi $c$).

---

Hai định lý tiếp theo sẽ giới thiệu hai cách mô tả khác của **bảo mật hoàn hảo**. Trong định lý đầu tiên, giả sử một kẻ nghe trộm áp dụng một **mệnh đề logic** $\phi$ lên bản mã mà hắn thu được. Mệnh đề $\phi$ là một **hàm Boolean** trên không gian bản mã, có thể rất đơn giản như **hàm kiểm tra tính chẵn lẻ** (tức là kiểm tra số lượng bit 1 trong bản mã là chẵn hay lẻ), hoặc có thể là một phép kiểm tra thống kê phức tạp hơn. Dù cho mệnh đề $\phi$ có tinh vi đến đâu, **bảo mật hoàn hảo** đảm bảo rằng giá trị của nó trên bản mã **không tiết lộ bất kỳ thông tin nào** về thông điệp gốc.

**Định lý 2** Cho hệ mã Shannon $\mathcal{E} = (E, D)$ được định nghĩa trên tập $(\mathcal{K}, \mathcal{M}, \mathcal{C})$. Xét một thí nghiệm ngẫu nhiên trong đó khóa $\mathbf{k}$ là một biến ngẫu nhiên được phân phối đều trên không gian khóa $\mathcal{K}$. Khi đó, $\mathcal{E}$ là **bảo mật hoàn hảo** nếu và chỉ nếu với mọi **mệnh đề** $\phi$ trên không gian bản mã $\mathcal{C}$, và với mọi $m_0, m_1 \in \mathcal{M}$, ta có:$\Pr[\phi(E(\mathbf{k}, m_0))] = \Pr[\phi(E(\mathbf{k}, m_1))]$.

Chứng minh chiều thuận của định lý trên thực chất chỉ là một phép tính đơn giản.

- Giả sử $\mathcal{E}$ là **bảo mật hoàn hảo**, và cho trước một mệnh đề $\phi$, cùng với hai thông điệp $m_0$ và $m_1$.
- Gọi $S := \{c \in \mathcal{C} : \phi(c) \}$ là tập hợp các bản mã thỏa mãn mệnh đề $\phi$, tức là với mọi $c \in S$ thì $\phi(c)$ đúng. Công thức biểu diễn là:

$$
\Pr[\phi(E(\mathbf{k}, m_0))] = \sum_{c \in S} \Pr[E(\mathbf{k}, m_0) = c].
$$

Do tính bảo mật hoàn hảo của $\mathcal{E}$, ta có:

$$
\sum_{c \in S} \Pr[E(\mathbf{k}, m_0) = c] = \sum_{c \in S} \Pr[E(\mathbf{k}, m_1) = c] = \Pr[\phi(E(\mathbf{k}, m_1))].
$$

Tiếp theo, ta chứng minh theo chiều nghịch, giả sử $\mathcal{E}$ **không** bảo mật hoàn hảo. Khi đó, tồn tại $m_0, m_1$ và $c$ sao cho $\Pr[E(\mathbf{k}, m_0) = c] \neq \Pr[E(\mathbf{k}, m_1) = c]$. Xét mệnh đề $\phi$ sao cho nó **đúng** với bản mã $c$ này và **sai** với tất cả các bản mã khác. Khi đó $\Pr[\phi(E(\mathbf{k}, m_0))] = \Pr[E(\mathbf{k}, m_0) = c] \neq \Pr[E(\mathbf{k}, m_1) = c] = \Pr[\phi(E(\mathbf{k}, m_1))]$. (Mâu thuẫn).

---

Định lý tiếp theo phát biểu một cách khác rằng **bảo mật hoàn hảo đảm bảo rằng bản mã không tiết lộ bất kỳ thông tin nào về thông điệp gốc**.

- Giả sử rằng $\mathbf{m}$ là một **biến ngẫu nhiên** được phân phối trên không gian thông điệp $\mathcal{M}$ (không cần phải phân phối đều).
- Giả sử $\mathbf{k}$ là một biến ngẫu nhiên **phân phối đều trên không gian khóa** $\mathcal{K}$, và độc lập với $m$.
- Gọi $\mathbf{c} := E(\mathbf{k}, \mathbf{m})$ là biến ngẫu nhiên phân phối trên không gian bản mã $\mathcal{C}$.

**Hệ quả:** Bảo mật hoàn hảo đảm bảo rằng $\mathbf{c}$ và $\mathbf{m}$ là **hai biến ngẫu nhiên độc lập**. Một cách mô tả tính độc lập này là $\Pr[\mathbf{m} = m \mid \mathbf{c} = c] = \Pr[\mathbf{m} = m], \quad \forall m \in \mathcal{M}, c \in \mathcal{C}$, với xác suất dương.

**Diễn giải trực quan:** Sau khi quan sát một bản mã $c$, ta **không có thêm thông tin nào** về thông điệp gốc $m$ so với trước khi nhìn thấy $c$. Một cách diễn giải khác về tính độc lập này là:

$$
\Pr[\mathbf{c} = c \mid \mathbf{m} = m] = \Pr[\mathbf{c} = c], \quad \forall m \in \mathcal{M}, c \in \mathcal{C}.
$$

Điều này có nghĩa là **việc chọn thông điệp $m$ không ảnh hưởng đến phân phối của bản mã**.

**Lưu ý:** Điều kiện rằng $\mathbf{m}$ và $\mathbf{k}$ là **hai biến ngẫu nhiên độc lập** là điều hợp lý. Khi sử dụng bất kỳ hệ mã nào, **chọn khóa phụ thuộc vào thông điệp** hoặc **chọn thông điệp phụ thuộc vào khóa** đều là một ý tưởng tồi.

**Định lý 3** Cho $\mathcal{E} = (E, D)$ là một mật mã Shannon được định nghĩa trên bộ ba $(\mathcal{K, M, C})$. Xét một thí nghiệm ngẫu nhiên trong đó $\mathbf{k}$ và $\mathbf{m}$ là các biến ngẫu nhiên, thỏa mãn:

- $\mathbf{k}$ được phân phối đều trên $\mathcal{K}$,
- $\mathbf{m}$ được phân phối trên $\mathcal{M}$,
- $\mathbf{k}$ và $\mathbf{m}$ là độc lập.

Định nghĩa biến ngẫu nhiên $\mathbf{c} := E(\mathbf{k}, \mathbf{m})$. Khi đó, ta có:

- Nếu $\mathcal{E}$ là **bảo mật hoàn hảo**, thì $\mathbf{c}$ và $\mathbf{m}$ là **độc lập**.
- Ngược lại, nếu $\mathbf{c}$ và $\mathbf{m}$ là **độc lập**, và mọi thông điệp trong $\mathcal{M}$ có xác suất xuất hiện khác 0, thì $\mathcal{E}$ là **bảo mật hoàn hảo**.

Ta sẽ chứng minh định lý trên. Đầu tiên, **(1) Nếu $\mathcal{E}$ là bảo mật hoàn hảo, thì $\mathbf{c}$ và $\mathbf{m}$ độc lập**. Xét bất kỳ $m \in \mathcal{M}$ và $c \in \mathcal{C}$. Ta cần chứng minh rằng:

$$
\Pr[\mathbf{c} = c \wedge \mathbf{m} = m] = \Pr[\mathbf{c} = c] \Pr[\mathbf{m} = m].
$$

Ta có:

$$
\begin{aligned}
\Pr[\mathbf{c} = c \wedge \mathbf{m} = m] &= \Pr[E(\mathbf{k}, \mathbf{m}) = c \wedge \mathbf{m} = m] \\
&= \Pr[E(\mathbf{k}, m) = c \wedge \mathbf{m} = m]
\end{aligned}
$$

Do $\mathbf{k}$ và $\mathbf{m}$ độc lập, ta có:

$$
\Pr[E(\mathbf{k}, m) = c \wedge \mathbf{m} = m] = \Pr[E(\mathbf{k}, m) = c] \Pr[\mathbf{m} = m].
$$

Vì vậy, để chứng minh tính độc lập, ta chỉ cần chỉ ra rằng:

$$
\Pr[E(\mathbf{k}, m) = c] = \Pr[\mathbf{c} = c].
$$

Thật vậy, ta có:

$$
\Pr[\mathbf{c} = c] = \Pr[E(\mathbf{k}, \mathbf{m}) = c].
$$

Áp dụng quy tắc xác suất toàn phần:

$$
\begin{aligned}
\Pr[\mathbf{c} = c] &= \sum_{m_0 \in \mathcal{M}} \Pr[E(\mathbf{k}, \mathbf{m}) = c \wedge \mathbf{m} = m_0] \\
&= \sum_{m_0 \in \mathcal{M}} \Pr[E(\mathbf{k}, m_0) = c \wedge \mathbf{m} = m_0]
\end{aligned}
$$

Do $\mathbf{k}$ và $\mathbf{m}$ độc lập, ta lại có:

$$
\Pr[E(\mathbf{k}, m_0) = c \wedge \mathbf{m} = m_0] = \Pr[E(\mathbf{k}, m_0) = c] \Pr[\mathbf{m} = m_0].
$$

Do $\mathcal{E}$ là bảo mật hoàn hảo, ta biết rằng:

$$
\Pr[E(\mathbf{k}, m_0) = c] =\Pr[E(\mathbf{k}, m) = c] \quad \forall m_0 \in \mathcal{M}.
$$

Thay vào tổng, ta được:

$$
\Pr[\mathbf{c} = c] = \sum_{m_0 \in \mathcal{M}} \Pr[E(\mathbf{k}, m) = c] \Pr[\mathbf{m} = m_0].
$$

Vì tổng các xác suất $\Pr[\mathbf{m} = m_0]$ trên toàn bộ $\mathcal{M}$ bằng 1, ta suy ra:

$$
\Pr[\mathbf{c} = c] = \Pr[E(\mathbf{k}, m) = c] .
$$

Vậy $\mathbf{c}$ và $\mathbf{m}$ là độc lập.

Đối với chiều suy luận thứ hai, giả sử rằng $\mathbf{c}$ và $\mathbf{m}$ là độc lập, và mỗi thông điệp trong $\mathcal{M}$ xuất hiện với xác suất khác không. Xét $m \in \mathcal{M}$ và $c \in \mathcal{C}$. Chúng ta sẽ chứng minh rằng $\Pr[E(\mathbf{k}, m) = c] = \Pr[\mathbf{c} = c]$, từ đó suy ra ngay lập tức tính bảo mật hoàn hảo. Do $\Pr[\mathbf{m} = m] \neq 0$, ta có:

$$
\begin{aligned}
\Pr[E(\mathbf{k}, m) = c] \Pr[\mathbf{m} = m] &= \Pr[E(\mathbf{k}, m) = c \wedge \mathbf{m} = m] \quad \text{(do $\mathbf{k}$ và $\mathbf{m}$ độc lập)} \\
&= \Pr[E(\mathbf{k}, \mathbf{m}) = c \wedge \mathbf{m} = m] \\
&= \Pr[\mathbf{c} = c \wedge \mathbf{m} = m] \\
&= \Pr[\mathbf{c} = c] \Pr[\mathbf{m} = m] \quad \text{(do $\mathbf{c}$ và $\mathbf{m}$ độc lập)}.
\end{aligned}
$$

Từ đó, chia cả hai vế cho $\Pr[\mathbf{m} = m]$ (vốn khác 0), ta suy ra:

$$
\Pr[E(\mathbf{k}, m) = c] = \Pr[\mathbf{c} = c] = \Pr[E(\mathbf{k}, \mathbf{m})].
$$

Điều này đúng với mọi $m \in \mathcal{M}$ và $c \in \mathcal{C}$, do đó hệ mã $\mathcal{E}$ là bảo mật hoàn hảo.

---

Chúng ta đã để dành tin xấu cho phần cuối. Định lý sau đây cho thấy rằng **bảo mật hoàn hảo** là một khái niệm mạnh đến mức không có hệ mã nào có thể làm tốt hơn **mã OTP (one-time pad)**: **khoá phải có độ dài ít nhất bằng độ dài của thông điệp**.

Hệ quả là rất khó áp dụng các hệ mã **bảo mật hoàn hảo** trong thực tế: nếu Alice muốn gửi cho Bob một tệp video 1GB, thì Alice và Bob phải thỏa thuận trước một khóa bí mật có độ dài **ít nhất 1GB**. Ta có định lý sau.

**Định lý 4 (Định lý của Shannon)**. Cho $\mathcal{E} = (E, D)$ là một hệ mã Shannon được xác định trên $(\mathcal{K, M, C})$. Nếu $\mathcal{E}$ là **bảo mật hoàn hảo**, thì $|\mathcal{K}| \geq |\mathcal{M}|$.

Cũng như mấy định lý trước, ta sẽ đi chứng minh định lý này. Giả sử **ngược lại** rằng $|\mathcal{K}| < |\mathcal{M}|$. Ta sẽ chứng minh rằng hệ mã $\mathcal{E}$ **không thể** bảo mật hoàn hảo bằng cách chỉ ra rằng tồn tại hai thông điệp $m_0, m_1$ và một bản mã $c$ sao cho:

$$
\Pr[E(\mathbf{k}, m_0) = c] > 0, \quad \text{(1)}
$$

$$
\Pr[E(\mathbf{k}, m_1) = c] = 0. \quad \text{(2)}
$$

Trong đó, $\mathbf{k}$ là một biến ngẫu nhiên được phân bố đều trên $\mathcal{K}$.

Chọn một thông điệp bất kỳ $m_0 \in \mathcal{M}$ và một khóa $k_0 \in \mathcal{K}$. Đặt $c := E(k_0, m_0)$. Rõ ràng, phương trình (1) đúng vì có ít nhất một khóa $k_0$ mã hóa được $m_0$ thành $c$. Tiếp theo, xét tập hợp $S := \{ D(k_1, c) \mid k_1 \in \mathcal{K} \}$

Tập $S$ chứa tất cả các thông điệp có thể được giải mã từ bản mã $c$ bằng **một khóa bất kỳ** trong không gian khóa $\mathcal{K}$, nên số lượng thông điệp trong tập $S$ không thể vượt quá số lượng khóa, tức là $|S| \leq |\mathcal{K}| < |\mathcal{M}|$. Vì $|S| < |\mathcal{M}|$, nên **tồn tại** ít nhất một thông điệp $m_1$ thuộc $\mathcal{M}$ nhưng **không thuộc** tập $S$, tức là $m_1 \notin S$. Điều này có nghĩa là **không có khóa nào trong $\mathcal{K}$ có thể giải mã $c$ thành $m_1$**. Ta sẽ chứng minh điều đó.

Giả sử **ngược lại** rằng tồn tại một khóa $k_1$ sao cho $E(k_1, m_1) = c$. Khi đó, do tính **chính xác** của hệ mã (tức là giải mã bản mã với khóa đúng phải thu được thông điệp ban đầu), ta có $D(k_1, c) = D(k_1, E(k_1, m_1)) = m_1$. Điều này có nghĩa là $m_1 \in S$, nhưng điều này **mâu thuẫn với việc ta chọn $m_1 \notin S$**. Do đó, **không thể có khóa $k_1$ nào mã hóa $m_1$ thành $c$**, tức là $\Pr[E(k, m_1) = c] = 0$.

Từ phương trình (1) và (2), ta thấy rằng tồn tại ít nhất một bản mã $c$ **chỉ có thể được sinh ra từ một số thông điệp nhất định**, tức là **xác suất sinh ra một bản mã không đồng đều giữa các thông điệp**. Điều này vi phạm định nghĩa **bảo mật hoàn hảo**, vì trong một hệ mã bảo mật hoàn hảo, mọi thông điệp phải có xác suất sinh ra cùng một bản mã như nhau. Vậy $\mathcal{E}$ **không thể bảo mật hoàn hảo**, chứng minh mệnh đề $|\mathcal{K}| \geq |\mathcal{M}|$.