Lecture 2：对称密钥加密¶

学习目标¶

完成本讲后，应当能够：

解释对称加密的基本模型与 Kerckhoffs 原则；
比较 Caesar、简单替换、Vigenère 与一次一密的安全性；
区分流密码与分组密码；
说明 DES 的 Feistel 结构、AES 的四种轮变换；
比较 ECB、CBC、CTR、CFB 的工作方式、随机访问能力和错误传播特性；
根据密钥长度、公开分析、标准化程度和工作模式判断密码方案是否可靠。

先记住这张路线图¶

层次	核心问题	本讲内容
密码目标	如何让窃听者看不懂消息	机密性
密码原语	如何把明文变成密文	Caesar、替换密码、Vigenère、OTP、RC4、DES、AES
安全分析	攻击者如何破解	穷举、频率分析、已知明文、差分与线性密码分析
多分组处理	如何加密长消息	ECB、CBC、CTR、CFB
工程选择	什么方案值得使用	足够的密钥长度、公开算法、标准方案、正确模式

五分钟复习顺序

先背 AES 参数和四种变换，再比较四种工作模式，最后回顾古典密码如何被频率分析与 Kasiski 检验攻破。

1. 对称加密的基本模型¶

对称密钥密码系统使用同一把秘密密钥完成加密和解密：

\[ C = E_K(P), \qquad P = D_K(C) \]

\(P\)：明文（plaintext）
\(C\)：密文（ciphertext）
\(K\)：通信双方共享的秘密密钥
\(E\)、\(D\)：加密与解密算法

对称加密主要提供机密性。算法可以公开，真正需要保密的是密钥。

Kerckhoffs 原则¶

分析安全性时，应假设攻击者完全知道密码系统的设计，只不知道密钥。可靠方案不能依赖“别人不知道算法”来维持安全。

攻击者通常有两个目标：

找到加密密钥；
不找密钥，直接从密文恢复明文。

2. 古典替换密码¶

2.1 Caesar Cipher¶

Caesar 密码把每个字母向后平移固定位置。若字母用 \(0\) 到 \(25\) 表示：

\[ E_k(x) = (x+k) \bmod 26 \]

\[ D_k(y) = (y-k) \bmod 26 \]

它只有 25 个有效密钥，逐一尝试即可破解。

2.2 简单替换密码¶

简单替换密码为 26 个字母选择一个排列，因此密钥空间为：

\[ 26! \approx 2^{88} \]

密钥空间很大，但不代表安全。每个明文字母总映射到同一个密文字母，语言的统计特征仍然保留。

2.3 频率分析¶

频率分析利用自然语言的统计规律：

英文中 e、t 比 z、q 常见；
单字母单词通常是 a 或 I；
常见三字母单词包括 the、and；
双字母、字母前后关系和可猜测短语也会泄露信息。

Crib 指攻击者猜测明文中可能出现的词或短语，例如固定问候语、天气报告或消息结尾。

关键结论

简单替换密码的弱点不在密钥数量，而在它保留了明文的统计结构。

2.4 Vigenère Cipher¶

Vigenère 使用多个 Caesar 字母表。密钥循环使用：

\[ C_i = (P_i + K_{i \bmod m}) \bmod 26 \]

同一个明文字母在不同位置可能变成不同密文字母，因此单一字母频率被打散。

它的主要弱点来自周期性密钥。Kasiski 检验寻找重复密文片段，计算它们之间的距离，并取多个距离的公因数来推测密钥长度。知道密钥长度后，可以把密文拆成若干个 Caesar 密码分别分析。

2.5 Enigma 的启示¶

Enigma 使用插线板与转子实现多表替换，初始状态决定加密过程。它拥有庞大的状态空间，但仍被以下信息削弱：

字母不会被加密成自身；
军事消息存在固定格式和常见短语，可形成 crib；
搜索设备可以快速排除不可能状态。

结论仍然相同：大密钥空间必须配合没有结构性弱点的算法。

3. 一次一密与流密码¶

3.1 One-Time Pad¶

一次一密使用按位异或：

\[ C = P \oplus K, \qquad P = C \oplus K \]

达到理论安全需要同时满足：

密钥真正随机；
密钥长度与消息相同；
每段密钥只使用一次；
密钥安全分发并销毁。

在这些条件下，同一段密文可以对应任意可能的明文，攻击者无法仅凭密文判断真正的消息。缺点是密钥生成、分发和保存成本过高。

3.2 流密码¶

流密码用较短的秘密密钥初始化确定性的密钥流生成器，产生较长的 keystream：

\[ C_i = P_i \oplus Z_i \]

其中 \(Z_i\) 是密钥流。一个安全生成器应保证：即使攻击者观察到较长的密钥流，也不能反推出秘密密钥或预测后续密钥流。

RC4 在课件中用于说明流密码的初始化与密钥流生成过程。其内部状态是 \(0\) 到 \(255\) 的一个排列，每生成一个字节便更新状态并选择一个输出字节。应把 RC4 当作结构与历史案例学习，不要把它当作现代系统的新方案。

密钥流复用

若同一密钥流加密两条消息，则 \(C_1 \oplus C_2 = P_1 \oplus P_2\)。攻击者可以消去密钥流，因此 nonce、IV 或计数器的复用通常是严重错误。

4. 分组密码与 DES¶

分组密码一次处理固定长度的数据块，并在多个数据块上复用同一把密钥。

算法	分组长度	密钥长度	结构
DES	64 bit	56 bit	16 轮 Feistel
AES	128 bit	128、192、256 bit	代换-置换网络

4.1 Feistel 结构¶

每一轮把数据分成左右两半：

\[ L_i = R_{i-1} \]

\[ R_i = L_{i-1} \oplus F(R_{i-1}, K_i) \]

Feistel 的重要特点是轮函数 \(F\) 本身不必可逆，整体结构仍可解密。解密时按相反顺序使用轮密钥。

4.2 好的分组密码应具备的性质¶

混淆（confusion）：隐藏密钥与密文之间的关系；
扩散（diffusion）：明文的一处小变化应影响大量密文位；
完整依赖（completion）：每个密文位最终都应受到各个密钥位影响；
雪崩效应：明文或密钥改变一位，理想情况下约一半输出位改变。

4.3 穷举攻击与密钥空间¶

\(n\) 位密钥共有 \(2^n\) 种可能，平均尝试 \(2^{n-1}\) 次才能找到正确密钥。

已知明文攻击中，攻击者拥有一组明文 \(x\) 与对应密文 \(y\)，依次测试密钥，直到找到满足 \(E_K(x)=y\) 的候选密钥。

DES 的主要现实问题是 56 位密钥过短。3DES 与 DESX 扩大了穷举成本，但现代系统通常采用 AES。

5. AES¶

5.1 必背参数¶

项目	AES 参数
分组长度	固定 128 bit，即 16 byte
密钥长度	128、192、256 bit
轮数	10、12、14 轮
结构	Substitution-Permutation Network，SPN
状态排列	16 字节按列填入 \(4\times4\) 矩阵

AES 先执行一次 AddRoundKey。普通轮包含四种变换，最后一轮省略 MixColumn。

5.2 四种轮变换¶

ByteSub / SubBytes：每个字节通过 S-box 独立替换。解密使用 inverse S-box。
ShiftRow / ShiftRows：第 0 行不移动，第 1、2、3 行分别循环左移 1、2、3 个字节。
MixColumn / MixColumns：每一列在 \(GF(2^8)\) 上做矩阵乘法，让一列中的四个字节互相影响。
AddRoundKey：状态矩阵与当前轮密钥逐位异或。

记忆逻辑：字节替换 -> 行移动 -> 列混合 -> 加轮密钥。

5.3 有限域运算¶

AES 在有限域 \(GF(2^8)\) 中计算，每个字节可以看作次数不超过 7 的二进制系数多项式。

加法就是按位 XOR；
乘法先做多项式乘法，再对不可约多项式取模；
AES 使用：

\[ m(x)=x^8+x^4+x^3+x+1 \]

MixColumn 之所以能同时实现扩散与可逆性，依赖的正是这种有限域矩阵运算。

5.4 Key Expansion¶

AES-128 的 16 字节主密钥扩展为 11 个轮密钥，共 44 个 32-bit word：

初始轮使用 \(w_0\) 到 \(w_3\)；
第 1 轮使用 \(w_4\) 到 \(w_7\)；
第 10 轮使用 \(w_{40}\) 到 \(w_{43}\)。

通常 \(w_i\) 依赖 \(w_{i-1}\) 与 \(w_{i-4}\)。当 \(i\) 是 4 的倍数时，会额外经过包含字节循环、S-box 和轮常数的函数 \(g\)。

6. 分组密码工作模式¶

单个分组密码只能处理一个固定长度的数据块。工作模式规定长消息中的多个分组如何组合。

6.1 ECB¶

\[ C_i = E_K(P_i) \]

各分组独立加密。相同明文块产生相同密文块，因此会泄露重复模式，还允许攻击者重新排列或剪切粘贴密文块。

结论：ECB 适合教学，不适合普通长消息或图像加密。

6.2 CBC¶

\[ C_0 = E_K(P_0 \oplus IV) \]

\[ C_i = E_K(P_i \oplus C_{i-1}) \]

解密为：

\[ P_i = D_K(C_i) \oplus C_{i-1} \]

CBC 使用随机 IV 初始化链。IV 不需要保密。相同明文块处于不同上下文时通常产生不同密文。

6.3 CTR¶

\[ C_i = P_i \oplus E_K(IV+i) \]

CTR 把分组密码变成密钥流生成器。加密与解密都只调用加密函数，并具有以下特点：

分组可以并行处理；
支持随机读取与随机写入；
不需要填充完整分组；
同一密钥下不能重复使用计数器序列。

6.4 CFB¶

\[ C_0 = P_0 \oplus E_K(IV) \]

\[ C_i = P_i \oplus E_K(C_{i-1}) \]

CFB 也把分组密码用于流式处理，但下一分组依赖上一密文分组，因此不能像 CTR 那样独立并行。

6.5 模式对比¶

模式	是否链式依赖	重复明文是否暴露模式	随机访问	填充	主要风险
ECB	否	是	读写均可	通常需要	模式泄露、剪切粘贴
CBC	是	否	可随机读，不便随机写	需要	IV 使用错误、错误传播
CTR	计数器独立	否	读写均可	不需要	nonce/计数器复用
CFB	依赖前一密文	否	不便	不需要	错误影响当前与下一分组

7. 传输错误与错误传播¶

传输错误指某一位发生翻转；传输丢失指某些位没有到达。若密文的一位错误导致多个明文位错误，就发生了错误传播。

模式	\(C_i\) 中一位出错后的影响
ECB	\(P_i\) 整个分组不可预测，之后恢复正常
CBC	\(P_i\) 整块不可预测，\(P_{i+1}\) 对应位翻转，之后恢复正常
CTR	\(P_i\) 的对应位翻转，不扩散到其他位或分组
CFB	\(P_i\) 对应位翻转，\(P_{i+1}\) 整块受影响，之后恢复正常

8. 实际选择密码方案¶

判断一个对称密码方案时，依次检查：

密钥长度：新系统通常至少使用 128-bit 对称密钥；
算法公开：安全性应来自密钥，而不是算法保密；
公开分析：优先选择经长期公开密码分析的算法；
标准化：优先选择成熟标准及其经过审查的实现；
工作模式：安全的分组密码配错模式仍会泄露数据；
IV/nonce 管理：满足所选模式对随机性或唯一性的要求。

Mifare Classic 使用保密的 Crypto1 算法和 48-bit 密钥。研究人员通过芯片逆向工程重建算法，随后发现更多弱点。这个案例直接说明了“依靠算法保密”无法替代公开分析。

9. 易错点速查¶

块长度不等于密钥长度：AES 的块长度始终是 128 bit。
大密钥空间不自动等于安全：简单替换有约 \(2^{88}\) 个密钥，仍可被频率分析攻破。
OTP 的条件缺一不可：随机、等长、只用一次、安全分发。
CBC 的 IV 不保密：但必须按协议正确生成与传输。
CTR 的计数器不能复用：复用会导致密钥流复用。
AES 最后一轮没有 MixColumn。
Feistel 每轮只处理一半数据，AES 每轮处理整个状态矩阵。
ECB 不隐藏结构：加密后的图像仍可能显现轮廓。

10. 自测题¶

1. 为什么简单替换密码拥有巨大密钥空间，却仍然不安全？

因为它保留了明文语言的字母频率、常见词长和字母组合等统计特征。攻击者不需要穷举全部密钥。

2. Kasiski 检验先恢复什么信息？

先通过重复密文片段之间的距离推测 Vigenère 密钥长度，再分别破解各个 Caesar 子密码。

3. 一次一密为什么理论安全，却很少直接用于普通网络通信？

它要求密钥真正随机、与消息等长、只使用一次，并通过安全渠道分发，密钥管理成本过高。

4. AES-128 的块长度、轮数和轮密钥数量分别是多少？

块长度 128 bit，10 轮，主密钥扩展出 11 个轮密钥，其中包含初始 AddRoundKey 使用的轮密钥。

5. 为什么 ECB 会泄露图像轮廓？

相同明文块使用同一密钥独立加密后产生相同密文块，重复结构没有被隐藏。

6. CBC 与 CTR 的随机访问能力有什么区别？

CBC 可利用前一密文块随机读取目标块，但修改目标明文会影响链式关系，不便随机写。CTR 可以直接计算目标分组的计数器值，因此支持随机读写。

7. CBC 中 \(C_i\) 的一位翻转会影响哪些明文？

\(P_i\) 整块不可预测，\(P_{i+1}\) 的对应位翻转，从 \(P_{i+2}\) 开始恢复正常。

一页背诵清单¶

Text Only

对称加密：同一把密钥加密与解密
Kerckhoffs：算法公开，只有密钥保密
简单替换：26! 很大，但频率分析可破
Vigenère：多表替换，Kasiski 推测密钥周期
OTP：随机、等长、一次使用，P XOR K = C
DES：64-bit block，56-bit key，16 轮 Feistel
AES：128-bit block，128/192/256-bit key，10/12/14 轮
AES 普通轮：SubBytes、ShiftRows、MixColumns、AddRoundKey
ECB：相同明文块产生相同密文块
CBC：与上一密文块链接，需要 IV
CTR：加密计数器后 XOR，支持并行和随机读写
CFB：反馈上一密文块，错误影响当前和下一块