密码学基础：安全模型、同余算术、古典密码与序列密码

本篇为密码学课程的基础理论篇，系统梳理密码学形式化安全模型、整数同余代数体系、古典密码及其统计分析破解方法，以及序列密码（流密码）与线性反馈移位寄存器（LFSR）的内部机理与周期性质。

---

一、密码学安全模型与攻击者能力边界

一个形式化的对称密码体制由五元组 $(\mathcal{M}, \mathcal{C}, \mathcal{K}, \mathcal{E}, \mathcal{D})$ 构成：

• $\mathcal{M}$ 为明文空间（Plaintext Space）；
• $\mathcal{C}$ 为密文空间（Ciphertext Space）；
• $\mathcal{K}$ 为密钥空间（Key Space）；
• 加密算法 $E_k: \mathcal{M} \to \mathcal{C}$ 与解密算法 $D_k: \mathcal{C} \to \mathcal{M}$。

对于任意明文 $x \in \mathcal{M}$ 与密钥 $k \in \mathcal{K}$，必须满足正确性条件（Correctness）：

$$D_k(E_k(x)) = x.$$

正确性是密码体制可用的最低先决条件，但正确性并不等价于安全性。系统的安全性依赖于攻击者在特定能力边界下无法推断出关于明文或密钥的非平凡信息。

1.1 柯克霍夫原则（Kerckhoffs's Principle）

现代密码学的立论基石是柯克霍夫原则：

密码体制的安全性必须完全建立在密钥的机密性之上，而不能依赖于加密算法本身的保密性。

即使攻击者完全获知了加密算法的全部数学细节、硬件实现电路与软件源代码，只要密钥未泄露，系统依然必须保持安全。企图通过“隐藏算法机制”来实现安全的做法（Security through Obscurity）在现代密码工程中被严格摒弃。

1.2 经典的四大密码分析攻击模型

评估一个密码算法的安全性时，必须严格界定攻击者（Cryptanalyst）所拥有的权限与资源：

flowchart TD
    COA["唯密文攻击 (COA)<br>能力: 仅能拦截截获部分密文 c"] --> KPA["已知明文攻击 (KPA)<br>能力: 拥有若干对应的 (m_i, c_i) 明密文对"]
    KPA --> CPA["选择明文攻击 (CPA)<br>能力: 可自由选择明文 m，获得加密生成的密文 c"]
    CPA --> CCA["选择密文攻击 (CCA)<br>能力: 可自由提交伪造密文 c，获得解密结果 m (除目标密文外)"]

1. 唯密文攻击（Ciphertext-Only Attack, COA）：
   • 攻击者仅能截获或窃听一段或多段密文 $y$。攻击者通常利用明文语言的统计冗余度（如字母频数分布、重复词汇结构）进行分析。
2. 已知明文攻击（Known-Plaintext Attack, KPA）：
   • 攻击者掌握了一定数量由同一密钥生成的明文及其对应的密文对 $(x_i, y_i)$（例如已知文件头部的固定格式或协议握手标记）。目标是反解出全局密钥 $k$ 或后续未见密文。
3. 选择明文攻击（Chosen-Plaintext Attack, CPA）：
   • 攻击者可以临时访问加密设备（Encryption Oracle），能够任意构造特定的明文序列并获得对应的密文（例如构造全零明文或单比特差异明文），借此隔离算法内部的未知变量。
4. 选择密文攻击（Chosen-Ciphertext Attack, CCA）：
   • 攻击者可以临时访问解密设备（Decryption Oracle），能够构造特定的密文并获得解密响应（或解密失败的差错反馈，如 Padding Oracle），目标是推断出未知目标密文对应的明文。

---

二、同余算术与剩余类代数基础

离散模代数是现代密码学算法的算术基石。

2.1 同余关系与基本性质

设 $a, b, n \in \mathbb{Z}$ 且 $n > 0$。若 $n$ 整除差值 $a - b$（即 $n \mid (a - b)$），则称 $a$ 与 $b$ 模 $n$ 同余，记作：

$$a \equiv b \pmod n.$$

同余关系是整数集上的等价关系，它将整数集划分为 $n$ 个互不相交的等价类（剩余类）。模运算对加法与乘法具有严格的代数相容性：

• $(a + b) \bmod n = \big((a \bmod n) + (b \bmod n)\big) \bmod n$；
• $(a \cdot b) \bmod n = \big((a \bmod n) \cdot (b \bmod n)\big) \bmod n$。

手算技巧：在计算大数的加减乘运算时，可随时在中间步骤对操作数进行模约简，以严格控制数值规模。例如模 13 下：$15 \equiv 2 \equiv -11 \pmod{13}$，$29 \equiv 3 \pmod{13}$，因此 $15 \cdot 29 \equiv 2 \cdot 3 = 6 \pmod{13}$。

2.2 模运算中的“除法”与乘法逆元

在普通实数代数中，“除以 $a$”等价于乘以倒数 $1/a$。但在整数模代数体系 $\mathbb{Z}_n = \{0, 1, \ldots, n-1\}$ 中，不存在分数的概念。

乘法逆元定义：对于整数 $a$，若存在整数 $x$ 使得：

$$a \cdot x \equiv 1 \pmod n,$$

则称 $x$ 为 $a$ 模 $n$ 的乘法逆元（Multiplicative Inverse），记作 $a^{-1} \pmod n$。

[!IMPORTANT]
乘法逆元存在的充要条件：
元素 $a$ 模 $n$ 存在乘法逆元的充分必要条件是 $a$ 与模数 $n$ 互素，即：
$\gcd(a, n) = 1.$

代数证明：
根据裴蜀定理（Bézout's Identity），存在整数 $s, t$ 使得 $sa + tn = \gcd(a, n)$。

• 若 $\gcd(a, n) = 1$，则 $sa + tn = 1$。等式两端取模 $n$，即得 $sa \equiv 1 \pmod n$。此时系数 $s$ 即为乘法逆元；
• 反之，若 $\gcd(a, n) = d > 1$，则对任意整数 $x$，$ax \bmod n$ 必为 $d$ 的倍数，绝不可能等于 1，故逆元不存在。

为什么同余式不能任意两端消去公因数：
在 $\mathbb{Z}_{26}$ 中，$2 \cdot 1 \equiv 2 \cdot 14 \pmod{26}$（因 $28 \equiv 2 \pmod{26}$），但两端消去 2 得到 $1 \equiv 14 \pmod{26}$ 是完全错误的。因为 $\gcd(2, 26) = 2 \ne 1$，数字 2 在模 26 下不存在乘法逆元，消去律失效。

---

三、古典密码与密码分析思想

3.1 移位密码（Caesar 密码）

将英文字母表 A—Z 依序编码为整数 $0, 1, \ldots, 25$。密钥 $k \in \{0, 1, \dots, 25\}$：

• 加密：$y = (x + k) \bmod 26$；
• 解密：$x = (y - k) \bmod 26$。

移位密码的密钥空间极小（$|\mathcal{K}| = 26$）。在唯密文攻击下，攻击者只需尝试全部 25 个非平凡密钥，即可在数秒内通过肉眼识别出可读英语语义，实现彻底穷举爆破。

3.2 单表代换密码与字母频率分析

单表代换密码允许将字母表进行任意双射排列置换。其密钥空间高达：
$|\mathcal{K}| = 26! \approx 4.03 \times 10^{26} \approx 2^{88}.$
该密钥空间已完全足以抵御暴力穷举攻击。

破解核心原理（保留了统计频数特征）：
单表代换是确定性的单字母映射，它完全保留了自然语言中字母的统计出现概率与多字母关联结构。

• 自然英语文本中，各字母的出现频率极不均匀：字符 E 的出现频率高达约 12.7%，紧随其后的是 T（约 9.1%）、A（约 8.2%）、O（约 7.5%）；
• 高频双字母组合包括 th, he, in, er；高频三字母词包括 the, and。

分析流程：

1. 统计密文中各字符出现频次，筛选出最高频候选字母；
2. 假定最高频字符对应明文 E 或 T，列出候选映射；
3. 结合单字母词（a, I）与三字母高频词（the）推导相邻字符；
4. 逐步代入全文，通过上下文的拼写与语义自洽性验证并修正替换表。

3.3 仿射密码（Affine Cipher）

仿射密码将单表代换推广为一次线性同余变换：

$$y = (a \cdot x + b) \bmod 26.$$

• 参数约束：乘法系数必须满足 $\gcd(a, 26) = 1$。因此 $a$ 只能从 $\{1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25\}$ 共 12 个数中选取，偏置 $b \in \{0, \dots, 25\}$，总密钥空间为 $12 \times 26 = 312$。
• 解密变换推导：
  $y - b \equiv a \cdot x \pmod{26} \implies x = a^{-1} \cdot (y - b) \bmod 26.$
  解密必须先在模 26 下求出乘法逆元 $a^{-1}$，再与 $(y - b)$ 模乘。若参数选取不满足互素条件（如 $a=2$），则不同的明文字符会被映射至相同密文（如 $x=0$ 与 $x=13$ 均映射为 $0$），破坏了映射的双射性，导致密文无法唯一还原。

---

四、序列密码（流密码）与一次一密（OTP）

序列密码将明文按比特流或字符流逐位处理，通过伪随机数发生器（PRNG）生成密钥流序列 $s_0, s_1, s_2, \ldots$：

• 二进制加密：$y_i = x_i \oplus s_i$；
• 二进制解密：$x_i = y_i \oplus s_i$。

加解密算法完全对称，其正确性由异或运算的自反性保证：$(x_i \oplus s_i) \oplus s_i = x_i \oplus 0 = x_i$。

4.1 一次一密（One-Time Pad, OTP）与完美保密性

香农（Claude Shannon）在信息论中从数学上严格证明了：一次一密体制具有完美保密性（Perfect Secrecy / 信息论安全）。即对于任意密文 $y$，其后验概率与先验概率完全相等：

$$P(X = x \mid Y = y) = P(X = x).$$

完美保密性的四大苛刻先决条件：

1. 密钥流必须由真正的物理随机源生成（真正的均匀独立分布）；
2. 密钥长度必须不小于明文长度；
3. 每个密钥流片段绝不重复使用（用后即毁）；
4. 密钥必须安全分发并在通信双方之间绝对保密。

为什么暴力穷举对 OTP 彻底无效：
对于长度为 $\ell$ 的任意密文 $y$，在均匀分布的密钥空间内，存在且仅存在唯一的密钥 $k = x \oplus y$ 将其映射到任意长度为 $\ell$ 的有意义明文 $x$。若攻击者穷举所有可能的 $2^\ell$ 个密钥，将解出全字典中所有语法通顺的合法文本（例如“今晚进攻”、“今晚撤退”、“明日休息”）。所有候选明文在数学后验概率上完全均等，攻击者在信息论上无法获取任何有助于辨识真实意图的信息。

4.2 密钥流复用漏洞（Key Reuse Attack）

在流密码体系中，密钥流的重复使用将导致灾难性的安全崩溃。
设两个不同的明文流 $X_1$ 与 $X_2$ 使用了相同的密钥流 $S$ 进行加密：

$$C_1 = X_1 \oplus S,\qquad C_2 = X_2 \oplus S.$$

攻击者将截获的两段密文进行按位异或：

$$C_1 \oplus C_2 = (X_1 \oplus S) \oplus (X_2 \oplus S) = X_1 \oplus X_2.$$

• 起保护作用的密钥流 $S$ 被完全代数抵消，直接暴露出两个明文的纯异或差值；
• 利用自然语言在 ASCII 编码下的统计特性（例如空格与英文字母异或后的特征模式），攻击者可以高效分离出两份原始明文；
• 一旦攻击者通过猜测获知其中一段明文 $X_1$，即可立即恢复出密钥流 $S = C_1 \oplus X_1$，进而完全解密另一段明文 $X_2$。

---

五、线性反馈移位寄存器（LFSR）原理与周期分析

为了在硬件中以极低的门电路开销生成长周期的伪随机序列，工程上广泛采用线性反馈移位寄存器（LFSR, Linear Feedback Shift Register）。

5.1 硬件结构与状态递推

一个级数为 $m$ 的二进制 LFSR 由 $m$ 个触发器单元 $(s_{i+m-1}, \ldots, s_{i+1}, s_i)$ 与若个异或门构成：

• 每一时钟节拍，最右端的最低位 $s_i$ 移出寄存器作为输出密钥比特；
• 其余各位整体向右平移一位；
• 最左端注入的新比特由特定位置（抽头系数 $c_j \in \{0, 1\}$）的线性模 2 加法（异或）反馈产生：

$$s_{i+m} = \sum_{j=0}^{m-1} c_j s_{i+j} \pmod 2 = c_{m-1}s_{i+m-1} \oplus \cdots \oplus c_1 s_{i+1} \oplus c_0 s_i.$$

对应的特征反馈多项式定义为：
$P(x) = x^m + c_{m-1}x^{m-1} + \dots + c_1 x + c_0.$

5.2 状态转移实例（3 位 LFSR）

设 3 级 LFSR 的反馈多项式为 $P(x) = x^3 + x^2 + 1$，对应递推关系式为 $s_{i+3} = s_{i+2} \oplus s_i$（抽头为 $c_2 = 1, c_1 = 0, c_0 = 1$）。
设初始非零状态为 $(s_2, s_1, s_0) = (1, 0, 0)$：

时钟拍号 $i$	当前寄存器状态 $(s_{i+2}, s_{i+1}, s_i)$	输出比特 $s_i$	新反馈位 $s_{i+3} = s_{i+2} \oplus s_i$
0	1 0 0	0	$1 \oplus 0 = 1$
1	1 1 0	0	$1 \oplus 0 = 1$
2	1 1 1	1	$1 \oplus 1 = 0$
3	0 1 1	1	$0 \oplus 1 = 1$
4	1 0 1	1	$1 \oplus 1 = 0$
5	0 1 0	0	$0 \oplus 0 = 0$
6	0 0 1	1	$0 \oplus 1 = 1$
7	1 0 0	（状态复原，周期循环开始）	—

输出的周期密钥流为 0011101，其周期恰好为 $2^3 - 1 = 7$。

5.3 周期定理与本原多项式（Primitive Polynomial）

$m$ 级 LFSR 的状态总数为 $2^m$。由于递推是线性的，全零状态 $(0,0,\dots,0)$ 的反馈位恒为 0，只能在自身形成自环。因此非零状态所能达到的理论极大周期为 $2^m - 1$（达到该最大周期的输出序列称为 m 序列）。

反馈多项式的代数性质	对应的状态转移环结构
本原多项式（Primitive）	所有 $2^m - 1$ 个非零状态连成单个遍历全空间的最大长度单一环
不可约但非本原多项式	非零状态空间分裂为若干个周期相等且均严格小于 $2^m - 1$ 的独立子环
可约多项式（Reducible）	非零状态空间分裂为多个不同周期的子环，周期强烈依赖初始初值选取

代数辨析：在二元有限域 $\mathrm{GF}(2)$ 上，多项式不可约仅意味着其不能分解为低次多项式的乘积；而本原多项式进一步要求其根是域乘法群的本原元。本原多项式必然是不可约多项式，但不可约多项式不一定是本原多项式。

5.4 为什么 LFSR 不能单独用作强安全密码体制？

尽管采用本原多项式的 LFSR 能够生成统计伪随机性质良好、周期极长的比特流，但单 LFSR 在现代密码学中绝不可直接作为安全的流密码。

弱点根源：线性代数可解性。
由于状态转移完全由模 2 线性方程描述，攻击者在已知明文攻击下，只需截获连续的 $2m$ 个密钥流比特，即可构建 $m$ 个线性方程，利用高斯消元法或 Berlekamp-Massey 算法，在 $O(m^2)$ 的多项式时间内完全反解出寄存器的级数 $m$、全部反馈系数 $c_i$ 以及当前寄存器状态，从而精确预测未来的全部密钥序列。

工程对策：实用的流密码（如 A5/1、Trivium、Grain）必须在多个不同级数的 LFSR 之间引入非线性组合生成器（Nonlinear Combining Function）或非线性钟控跳步机制，以彻底破坏线性代数可解性。