Block Ciphers（课堂笔记整理版）

2026-06-23

Uncategorized

33k words

分组密码（Block Ciphers）— 系统化课堂笔记

本笔记基于 Dan Boneh 密码学课程分组密码章节的全部内容，按照逻辑递进关系重新组织：基础定义 → 迭代构造 → PRF/PRP 理论抽象（核心）→ DES 完整解析 → AES 完整解析 → 攻击方法全景 → PRG→PRF→PRP 理论构造 → 计数器模式应用 → 实战对比。

阅读指引：每节先给出直觉理解（“这个概念的物理意义是什么”），再给出形式化定义（“如何用数学语言精确描述”），最后串联前后逻辑（“为什么这个概念重要，它和前后内容的关系是什么”）。

适配软件工程本科基础薄弱视角，对所有关键概念进行通俗解释和详细展开，补充大量具体数值示例帮助理解。

第一部分：分组密码基础定义

1.1 什么是分组密码 — 从流密码到分组密码

1.1.1 回顾：流密码的工作方式

在流密码中，加密过程是：

c = m ⊕ G(k)

其中 G(k) 是 PRG（伪随机生成器）从短种子 k 扩展出的长密钥流。特点是： - 逐比特处理：明文的每一比特独立与密钥流 XOR - 无固定分组：消息可以是任意长度，PRG 生成对应长度的密钥流 - 加密 = 解密：因为 XOR 是自逆运算，加解密使用完全相同的操作

1.1.2 分组密码的不同思路

分组密码采用完全不同的思路：把明文切成固定大小的”块”（block），每次对一个完整的块做可逆变换。可以想象你有一本”密码字典”——这本书有 2ⁿ 页（n 是分组长度），每页写着一个不同的 n 比特值。加密就是：给定密钥 k，生成一个特定的”翻页规则”（一个置换），把明文所在的页面翻到密文所在的页面。解密就是按照相反的规则翻回来。

形式化定义：分组密码（Block Cipher）是一对确定性算法——加密算法 E 和解密算法 D：

E : 𝒦 × {0, 1}ⁿ → {0, 1}ⁿ

D : 𝒦 × {0, 1}ⁿ → {0, 1}ⁿ

各符号的含义：

符号	含义	示例（AES-128）
𝒦	密钥空间——所有合法密钥的集合	{0, 1}¹²⁸，大小 2¹²⁸
{0, 1}ⁿ	所有 n 比特串的集合（明文空间 = 密文空间）	n = 128，共 2¹²⁸ 个不同的块
E(k,m)	用密钥 k 加密明文块 m，输出密文块 c	c = AES-128-encrypt(k,m)
D(k,c)	用密钥 k 解密密文块 c，还原明文块 m	m = AES-128-decrypt(k,c)

正确性公理（解密必须还原加密——这是密码系统最最基本的要求）：

∀k ∈ 𝒦, ∀m ∈ {0, 1}ⁿ: D(k, E(k,m)) = m

1.1.3 三条硬性约束（区别于流密码的关键特征）

约束	说明	对比流密码
输入输出等长	n 比特入 → n 比特出，长度不扩缩	流密码：输出长度 = 明文长度，无固定分组
确定性算法	E 和 D 都是确定性的（无随机性）	流密码：加密是确定性的（密钥流确定后）
双射/置换	每个密钥 k 定义一个 {0, 1}ⁿ 上的置换	流密码：不要求置换结构

💡 通俗理解：把固定长度的明文块当作一个”大数字”（如 128 比特 = 一个 0 到 2¹²⁸ − 1 之间的整数），用密钥对它做可逆置换——就像给每个数字换一个”伪装身份”。加密是正向查表（明文→密文），解密是反向查表（密文→明文）。输入多少比特，密文就多少比特。

1.1.4 为什么要固定分组长度？

固定分组长度有三个深层原因：

硬件友好：现代 CPU 寄存器是固定宽度的（如 128 位 XMM 寄存器用于 AES-NI 指令）。固定分组可以高效地用硬件直接处理，不需要处理变长数据的额外逻辑。
安全分析可行：固定输入输出空间（大小 2ⁿ），把加密看作 {0, 1}ⁿ 上的一个置换，数学家可以在有限的置换群上进行分析，证明安全性质。
可组合性：分组密码本身只是”积木”——它只能加密恰好 n 比特的消息。但通过不同的工作模式（Mode of Operation），可以将积木组合起来加密任意长度的消息：
- ECB 模式（Electronic Codebook）：每块独立加密（极不安全，不推荐）
- CBC 模式（Cipher Block Chaining）：前一块密文影响后一块加密（需要 IV）
- CTR 模式（Counter Mode）：计数器输入 PRF，变成流密码（推荐）

1.2 经典工业分组密码实例

1.2.1 3DES（Triple DES）

3DES 是对已经弱化的 DES 的”急救方案”——不是设计新密码，而是把 DES 套用三次以增加密钥长度：

加密过程：c = E_k₃(D_k₂(E_k₁(m)))（加密-解密-加密，简称 EDE）
三个独立密钥总长 168 比特（实际有效强度约 112 比特，因为有 meet-in-the-middle 攻击）
为什么中间用解密 D 而不是加密 E？ 为了向后兼容：如果 k₁ = k₂ = k₃，3DES 退化为单 DES，旧的 DES 硬件可以直接使用

1.2.2 AES（Advanced Encryption Standard）

AES 是经过全球公开竞赛选出的现代分组密码标准：

属性	AES-128	AES-192	AES-256
分组长度	128 bit	128 bit	128 bit
密钥长度	128 bit	192 bit	256 bit
轮数	10 轮	12 轮	14 轮
密钥空间	2¹²⁸ ≈ 3.4 × 10³⁸	2¹⁹²	2²⁵⁶

⚠️ 密钥长度与安全性的关系：密钥越长 → 暴力穷举越困难 → 安全性越高，但轮数也越多 → 计算速度越慢。实践中 AES-128 已足够安全（2¹²⁸ 远超当前人类可企及的计算能力），AES-256 用于高安全要求和抗量子计算场景。

第二部分：分组密码的通用构造 — 迭代结构

2.1 迭代思想：为什么需要多轮？

核心矛盾：直接构造一个从 {0, 1}ⁿ 到 {0, 1}ⁿ 的安全置换非常困难——需要描述 2ⁿ 个输入-输出对。但我们可以把一个”弱但简单”的变换重复多次，使其输出在统计上变得”强而复杂”。

类比理解：揉面团。单次揉捏只能影响局部，但如果反复折叠（轮函数 R）+ 旋转（密钥异或），最终面团被充分揉匀（混淆 + 扩散），任何人都无法从成品反推出初始状态。

形式化描述

所有现代分组密码都采用迭代结构：

步骤 1：密钥扩展（Key Expansion）

将短原始主密钥 k 通过固定的密钥编排算法生成一长串回合密钥：

(k₁,k₂,…,k_r) ← KeyExpansion(k)

其中 r 是总回合数。每一轮使用一个不同的回合密钥。

为什么要做密钥扩展？ 三个原因： 1. 打破轮间对称性：如果所有轮使用同一个密钥，轮函数的重复会引入可以利用的统计规律 2. 增加密钥材料：原始密钥可能只有 128 位，但 r 轮共需要 r × n 位子密钥（如 AES-128：11 × 128 = 1408 位），密钥扩展生成这些额外材料 3. 使每轮”不同”：每一轮像是使用不同密钥的”不同密码”，整体难以分析

步骤 2：多轮迭代加密

每一轮使用同一个回合函数 R 处理当前数据状态：

s_i = R(k_i,s_i − 1), i = 1, 2, …, r

其中： - k_i：第 i 轮回合密钥 - s_i − 1：第 i 轮输入状态 - s₀ = m（明文），s_r = c（密文）

解密：将回合密钥逆序使用，每轮应用 R⁻¹（轮函数的逆函数）：

s_i − 1 = R⁻¹(k_i,s_i), i = r, r − 1, …, 1

关键密码学设计原则：混淆与扩散

这两个概念由Claude Shannon在 1949 年的开创性论文中提出，是所有现代分组密码设计的基石：

原则	定义	实现手段	目的
混淆（Confusion）	让密文与密钥之间的关系尽可能复杂、非线性	S 盒（非线性查找表）	阻止攻击者从密文反推密钥
扩散（Diffusion）	让明文/密钥中一个比特的变化”扩散”到密文的多个比特	置换、移位、矩阵运算	增大统计攻击所需的样本量（雪崩效应）

雪崩效应（Avalanche Effect）：理想情况下，明文或密钥的任意 1 个比特翻转应导致密文中约 50% 的比特翻转。这是扩散的量化指标——AES 在 2-3 轮内即可达到完全的雪崩效应。

迭代结构的工程特征总结

特征	说明
不同密码 = 不同 R + 不同 r	DES：r = 16（Feistel 轮函数）；AES-128：r = 10（SPN 轮函数）
轮数确定原则	轮数应足够多，使得所有已知攻击的复杂度都不低于暴力穷举
安全余量	实际轮数通常远多于”刚好安全”的轮数，以应对未来的分析进展

第三部分：PRF 与 PRP — 分组密码的理论抽象

⚠️ 这一部分是整个分组密码章节的理论核心。前面讲的是”工程上怎么做（迭代结构）“，这里讲的是”数学上怎么定义安全（PRF/PRP）“。如果你只有时间深入理解一节，就选这一节。

3.1 为什么需要理论抽象？

直接问”AES 安全吗？“在数学上是无法回答的——因为我们甚至无法严格证明 P ≠ NP，更无法证明某个具体函数是伪随机的。密码学家的工作方式是：

把密码算法抽象成理想的数学对象（PRF / PRP）
对抽象对象建立形式化的安全定义（不可区分游戏）
用归约法（Reduction）证明：如果底层组件安全，则整个构造安全
工程上信任若干”基础假设”（如 AES 是安全 PRP），在此之上搭建整个体系

💡 类比：就像软件工程中你不直接验证每一个二进制指令是否正确，而是假设 CPU 正确执行指令，然后在此基础上验证代码逻辑。密码学中，PRF/PRP 安全就是我们的”CPU 正确性假设”。

3.2 伪随机函数（Pseudo Random Function, PRF）

3.2.1 直觉理解

想象你面前有两个黑盒。黑盒 A 里是一个真随机函数——对每个不同的输入 x，它输出一个完全独立随机选择的值 y（但同一个输入多次查询返回相同的输出——函数毕竟要满足确定性）。黑盒 B 里是一个 PRF——它内部有一个随机选择的密钥 k，对输入 x，它输出 F(k,x)。

你只能通过询问黑盒来观察行为。如果你无论问多少次、问什么问题，都无法可靠地判断哪个是 A 哪个是 B，那么 F 就是一个安全 PRF。

3.2.2 形式化定义

PRF F 定义在三元组 (𝒦,X,Y) 上：

F : 𝒦 × X → Y

𝒦：密钥空间。例如 AES-128 的 𝒦 = {0, 1}¹²⁸
X：输入空间（定义域）。例如 X = {0, 1}¹²⁸
Y：输出空间（值域）。例如 Y = {0, 1}¹²⁸

两个基本要求：

有效可计算（Efficiently Computable）：存在多项式时间算法，给定 (k,x) 可以算出 F(k,x)。这意味着 PRF 可以在真实计算机上高效运行。
固定密钥即为确定函数：一旦选定密钥 k，F(k,⋅) 就是一个从 X 到 Y 的确定函数——给同一个 x 永远返回同一个 y。

⚠️ 重要：PRF 不要求具有可逆性！F(k,⋅) 允许多个不同输入映射到同一个输出（碰撞是允许的）。PRF 只是一个”看起来随机”的映射。

3.2.3 全集函数集合 Funs[X,Y] — 理解”真随机函数”

定义 Funs[X,Y] = 所有能从 X 映射到 Y 的函数构成的集合。

这个集合有多大？ 以 AES-128 为例（n = 128）：

|Funs[{0,1}¹²⁸,{0,1}¹²⁸]| = |Y|^|X| = (2¹²⁸)^2¹²⁸ = 2^{128 ⋅ 2¹²⁸}

这是一个极其巨大的数字——远超宇宙中的原子总数（约 10⁸⁰ ≈ 2²⁶⁶）。真随机函数是从这个天文数字般的集合中完全均匀随机选取的。

对比 PRF 的密钥空间：AES-128 只有 2¹²⁸ 个可能的密钥，也就是说，AES-128 只能表示全部可能函数中的 2¹²⁸ 个——这是真随机函数集合的极小真子集（2¹²⁸ vs 2^{128 ⋅ 2¹²⁸}，后者是前者的指数级）。

安全的本质悖论：虽然 PRF 只能实现全部可能函数中的极小一部分（比例约为 2¹²⁸/2^{128 ⋅ 2¹²⁸} ≈ 0），但攻击者限于多项式时间的计算能力，看不出来这些函数和从全集中随机选的函数有什么区别。这就是计算安全的精髓。

3.2.4 安全 PRF 的形式化定义（PRF 区分游戏）

形式化定义是密码学中最重要的思维方式——“游戏”。 把安全性定义成攻击者和挑战者之间的博弈：攻击者赢了 → 密码不安全；攻击者赢不了 → 密码安全。

游戏流程：

挑战者秘密地、均匀随机地抛一枚硬币：
- 若 b = 0（世界 0，真随机）：从 Funs[X,Y] 中完全均匀随机地选取一个函数 f_rand
- 若 b = 1（世界 1，伪随机）：均匀随机选取密钥，固定函数 f_prf = F(k,⋅)
攻击者 𝒜 进行自适应多次询问（Adaptive Queries）：攻击者可以发送任意输入 x₁, x₂, …, x_q（总查询次数 q 由攻击者自定，但必须是多项式级别），挑战者返回对应的函数值 f(x_i)。“自适应” 意味着攻击者可以根据之前的回答来决定下一个查询——不是预先固定的。
攻击者观察所有回答后，输出猜测比特 b′ ∈ {0, 1}，表示他认为自己在哪个世界。

安全判定标准：

定义攻击者 𝒜 针对 PRF F 的区分优势（Advantage）：

Adv_𝒜, F^PRF(λ) = |Pr[𝒜 输出 1∣世界 1（PRF）]−Pr[𝒜 输出 1∣世界 0（真随机）]|

其中 λ 是安全参数（与密钥长度 n 相关）。

F 是安全 PRF，当且仅当：对所有 PPT（概率多项式时间，Probabilistic Polynomial-Time）攻击者 𝒜，Adv_𝒜, F^PRF(λ) 是关于 λ 的可忽略函数。

这个定义中的关键要素解析：

要素	含义	为什么需要
“对所有 PPT 攻击者”	不限制攻击者使用什么策略，只要是在多项式时间内可计算的	安全必须抵御所有可能的高效攻击
“优势可忽略”	攻击者猜对的概率 ≈ 50%（只比随机猜测好一个极小的量）	信息论上不可能 100% 区分（密钥空间远小于函数全集）
“自适应询问”	攻击者可以根据前面的回答调整后续问题	反映真实攻击场景——攻击者是灵活应变的

💡 这与流密码章节中”PRG 输出 vs 真随机串不可区分”的定义逻辑完全一致——都是计算不可区分性（Computational Indistinguishability）思想在不同对象上的应用。

3.3 伪随机置换（Pseudo Random Permutation, PRP）

3.3.1 直觉：PRP = 特殊的 PRF

PRF 不要求输入输出一一对应——两个不同的输入 x₁ ≠ x₂ 完全可能产生相同的输出 F(k,x₁) = F(k,x₂)（即碰撞）。但分组密码必须是可逆的（否则无法解密），所以分组密码不能只是一般的 PRF——它必须是一个置换（一一对应）。

PRP 就是带有这种额外结构约束的 PRF。

3.3.2 形式化定义

E : 𝒦 × X → X

三条约束（区别于普通 PRF）：

输入空间 = 输出空间：X = Y，且 |X| 通常是 2ⁿ（如 2¹²⁸）
双射/一一对应：固定任意密钥 k，E(k,⋅) 是 X 上的一个置换：
- 单射（Injective）：x₁ ≠ x₂ ⇒ E(k,x₁) ≠ E(k,x₂)（不同输入永不可能映射到同一输出）
- 满射（Surjective）：∀y ∈ X, ∃x ∈ X : E(k,x) = y（X 内每个值都能被映射到，没有”落空”的值）
存在高效逆算法 D：∀k, ∀x, D(k,E(k,x)) = x。给定密文和密钥，快速求出唯一原像。

置换全集符号记为 Perm[X]——集合 X 上所有可逆置换的集合。其大小为 |Perm[X]| = (2ⁿ)!（(2¹²⁸)! 这也是天文数字，但远小于 Funs[X,X] 的 (2¹²⁸)^2¹²⁸）。

3.3.3 PRP 的安全定义

与 PRF 的安全定义完全一致：安全 PRP 要求从 Perm[X] 中随机选一个真随机置换，和从 PRP 的密钥空间中随机选一个密钥（得到一个 PRP 置换），二者在计算上不可区分。

注意细微差别：PRP 区分游戏中，世界 0 是从 Perm[X]（所有置换）中随机选取，而非从 Funs[X,X]（所有函数）中随机选取。置换集合比函数集合小得多（(2ⁿ)! vs (2ⁿ)^2ⁿ），但这个差别在多项式查询下是不可区分的。

3.3.4 PRP 实例

算法	数学表示	参数	分组长度
AES-128	E : {0, 1}¹²⁸ × {0, 1}¹²⁸ → {0, 1}¹²⁸	\|𝒦\| = 2¹²⁸	128 bit
AES-256	E : {0, 1}²⁵⁶ × {0, 1}¹²⁸ → {0, 1}¹²⁸	\|𝒦\| = 2²⁵⁶	128 bit
3DES	E : {0, 1}¹⁶⁸ × {0, 1}⁶⁴ → {0, 1}⁶⁴	\|𝒦\| = 2¹⁶⁸	64 bit

3.4 PRP 与 PRF 的包含关系（重点结论）

🔑 核心结论：PRP ⊂ PRF。每一个 PRP 都是 PRF，但 PRF 不一定是 PRP。

PRF（伪随机函数）         ← 只需要"看起来随机"，允许碰撞
  ↑
  │  包含关系
  │
PRP（伪随机置换）         ← 额外要求：一一对应 + 可逆

为什么这个包含关系重要？ 在安全证明中，如果某构造只需要 PRF 的安全性（如计数器模式——你只需要一个”看起来随机的输出”，不需要可逆），而我们用了 PRP（AES），由于 PRP 同时也满足 PRF 的安全定义，该构造仍然是安全的。因为 PRP 除了是 PRF 之外，还”额外”拥有了置换结构——这个”额外”不会伤害安全性。

PRF 到 PRP 的转换（Switching Lemma）：对于 n 比特分组，如果攻击者进行 q 次查询，PRP 与 PRF 的区分优势至多为。这意味着：只要 q ≪ 2^n/2（查询次数远小于生日界），PRP 和 PRF 在实际中就是不可区分的。

对 AES-128：2^n/2 = 2⁶⁴，生日界。只要加密不超过 2⁶⁴ 个块（约 2⁶⁸ 字节 = 295 EB），就无需担心 PRP/PRF 区分问题。

3.5 不安全 PRF 构造反例 — 理解安全”边界”

Boneh 课程中的经典课堂示例，深刻展示了”安全”是一个全局性质——一个微小改动就能摧毁整个安全性。

场景：假设我们有一个已经证明安全的 PRF F : 𝒦 × X → {0, 1}¹²⁸。现在我们试图”改进”它，构造一个新函数 G：

$若（特殊处理输入）若（其余情况不变）$

G 不安全的原因（一次查询即可破解）：

攻击者向预言机发送唯一一次查询 x = 0
观察返回结果：
- 若返回 0¹²⁸（全零串）→ 判断为世界 1（G），因为真随机函数输出全零串的概率仅为 1/2¹²⁸，几乎不可能偶然发生
- 若返回其他值 → 判断为世界 0（真随机）
攻击者的区分优势：Adv ≈ 1 − 1/2¹²⁸ ≈ 1（接近 100% 正确）

分析：G 的”错误”在于它破坏了对所有输入保持统计随机性的要求。真随机函数在 x = 0 时的输出应该和任何其他输入一样是”随机”的。G 在 x = 0 处的确定性行为（永远输出全零）成为一个可检测的指纹。

🔑 核心教训： 1. 即使底层组件 F 是安全的，只要构造中存在固定输入对应固定可预测输出，整体构造就被攻破 2. 安全不是”大部分安全就行”——一个弱点就可能导致全盘崩溃（密码学中不存在”99% 安全”） 3. 函数输出必须对所有可能的输入都保持统计随机性，没有例外

第四部分：DES 完整详解

DES（Data Encryption Standard）虽然已在 2000 年被 AES 正式取代，但它是密码学史上最重要的早期商用分组密码。其 Feistel 网络架构、S 盒非线性设计思想，以及从设计到被破解的完整生命历程，构成了理解分组密码设计哲学的最佳教科书。

4.1 DES 完整发展历史

4.1.1 起源：IBM Lucifer 密码（1970-1973）

1970 年代初：商业加密需求随计算机普及而爆发。IBM 组建密码研究小组，由 Horst Feistel 牵头
Feistel 设计了对称分组密码原型 Lucifer——这是 Feistel 网络架构的首次工程落地
Lucifer 的分组长度为 128 位，密钥长度 128 位

4.1.2 标准化：成为美国联邦标准 DES（1973-1976）

1973 年：美国国家标准局（NBS，后更名为 NIST）公开征集联邦通用分组密码标准
IBM 提交了 Lucifer 的改良版本——分组长度从 128 缩减为 64 位，密钥从 128 缩减为 56 位（据说受 NSA 影响）
NSA（美国国家安全局） 在审核过程中做了两项重要修改：
1. 将密钥长度从 Lucifer 的 128 位缩短为 56 位（后来证明这是 DES 的致命弱点）
2. 重新设计了 S 盒的内部数值——NSA 的设计使 S 盒恰好能抵抗当时尚未公开的差分密码分析技术（IBM 和 NSA 后来承认他们早在 1974 年就知道了差分分析，但将其列为机密）
1976 年：正式公布为 Data Encryption Standard (DES)——全球首个商用标准化分组密码

4.1.3 质疑与争议：NSA 是否植入了后门？

DES 公布后，学术界产生了两个核心质疑： 1. 56 位密钥是否太短？ NSA 是否故意削弱了安全强度以便自己能破解？ 2. S 盒是否包含陷门？ NSA 是否在 S 盒中植入了只有自己知道的数学后门？

事后证明： - 56 位密钥确实太短——但这不是陷门，而是 NSA 在安全性与当时计算能力之间的”折中”（也有说法是出口管制考虑） - S 盒非但没有陷门，反而被精心增强了——NSA 设计的 S 盒恰好能抵抗差分密码分析（一种当时未公开的强大攻击技术）。20 年后差分分析被学术界独立重新发现时，研究者才意识到 NSA 早已知道且已做了防护

4.1.4 淘汰过程

1997 年：通过分布式网络（互联网上成千上万的志愿者计算机），成功以暴力穷举攻破 DES——证明 56 位密钥已完全无法提供安全保障
1999 年：专用硬件 Deep Crack（由 EFF 资助）在 22 小时内穷举完整个 DES 密钥空间
2000 年：NIST 选定 Rijndael 为 AES
2001 年：AES 正式成为 FIPS 197 标准，DES 正式退役

4.1.5 DES 的历史地位

贡献	说明
金融行业基石	全球银行跨行清算网络（SWIFT）、电子资金转账、ATM 交易报文加密——运行了 20+ 年
现代密码工程先驱	首次将分组密码大规模部署到商用系统，奠定了硬件实现、密钥管理等工程范式
理论教学范本	Feistel 网络、S 盒非线性、迭代轮函数、雪崩效应——所有现代密码学课程的必讲内容
政府-学术界互动	NSA 对 S 盒的修改引发持续讨论，催生了公开、透明的密码设计文化（后续的 AES 竞赛就是完全公开透明的）

4.2 Feistel 网络 — DES 的底层架构理论

4.2.1 基础定义

输入：长度 2n 比特的明文，拆分为左右两个等长的 n 比特分组： - L₀：左半部分（前 n 比特） - R₀：右半部分（后 n 比特）

轮函数：存在 d 个任意函数（不要求可逆！不要求双射！不要求密码学性质！）：

f₁, f₂, …, f_d : {0, 1}ⁿ → {0, 1}ⁿ

一轮标准 Feistel 变换：

输入输出：2n 位 ↦ 2n 位。

💡 直觉理解：每一轮，“右半部分”直接搬到下一轮的”左半位置”（原封不动），而”左半部分”与轮函数的输出异或后成为下一轮的”右半位置”。这样一半搬家、一半被修改，经过多轮后所有比特都被充分混淆。

Feistel 的图示理解：

其中 ⊕ 表示按位异或。可以看到： - L_i + 1 = R_i（右半直接搬到左半） - R_i + 1 = L_i ⊕ f_i(R_i)（左半被”修改”后成为新的右半）

4.2.2 关键性质：Feistel 网络天然可逆（无需轮函数可逆！）

这是 Feistel 结构最精妙优雅的地方——解密只需要把加密流程”倒过来走一遍”，使用完全相同的轮函数（不需要求轮函数的逆！）。

逆变换（解密）推导：

已知加密最后一轮输出 (L_d,R_d)。解密第一轮执行如下操作：

验证正确性：因为加密最后一轮的定义是： - L_d = R_d − 1 ✓（直接给出解密中 R_d − 1 的值） - R_d = L_d − 1 ⊕ f_d(R_d − 1) = L_d − 1 ⊕ f_d(L_d)（因为 R_d − 1 = L_d）

从第二个等式解出 L_d − 1： R_d = L_d − 1 ⊕ f_d(L_d) ⇒ L_d − 1 = R_d ⊕ f_d(L_d)

因为 (a⊕b) ⊕ b = a。完全吻合！

逐轮反向运算：每轮解密使用相同的 f_i 函数和相同的轮密钥（只是顺序从 d 到 1），最终还原原始 (L₀,R₀)。 为什么不需要 f_i 可逆？ 因为 f_i 永远只出现在异或的一边：L_i ⊕ f_i(R_i)。解密时我们拥有 L_i 的值（它在加密时被直接传递到下一轮），只需要把 f_i(R_i) 再异或一次就消掉了。

💡 这就是为什么 DES 的 S 盒不需要可逆——Feistel 整体结构通过巧妙的交叉异或，把”可逆”的负担从轮函数转移到了自身结构上。这是密码工程史上最精妙的设计之一。

4.2.3 Feistel 安全核心定理（Luby-Rackoff 定理）

论文：How to Construct Pseudorandom Permutations from Pseudorandom Functions（Luby & Rackoff, 1988）

这篇论文获得了密码学最高荣誉之一，它建立了 PRF 和 PRP 之间的理论桥梁。

定理内容：

设 F 是一个安全 PRF（n 位输入 / n 位输出，与随机函数在计算上不可区分）。使用三轮独立密钥的 Feistel 网络（每轮轮函数使用独立密钥的安全 PRF），最终整体构造是一个安全 PRP（伪随机置换）。

轮数与安全性对照表：

Feistel 轮数	安全性	说明
1 轮	不安全	输出的右半部分 = 明文左半 XOR f₁(明文右半)，左半 = 明文右半（直接暴露）
2 轮	不安全	存在可检测的统计偏差（生日界攻击）
3 轮	安全 PRP ✓	Luby-Rackoff 定理——这是安全的最小轮数
4 轮	安全 PRP ✓	更强的安全保证（抵御选择密文攻击）

DES 的对应实现：DES 使用了16 轮 Feistel，远超理论所需的 3-4 轮。多余轮数提供了巨大的安全余量——即使有未知的分析技术能攻破前若干轮，16 轮的深度也使其无法威胁整体安全。

⚠️ 单轮或两轮 Feistel 不满足安全置换！在实际中绝不应使用少于 3 轮的 Feistel 构造。

4.3 DES 完整结构参数

4.3.1 全局参数

参数	值	说明
分组长度	64 bit	输入明文和输出密文均为 64 位
密钥（原始）	64 bit	但其中每字节的最高位（共 8 位）是奇偶校验位，不参与加密
有效密钥	56 bit	2⁵⁶ ≈ 7.2 × 10¹⁶ 种可能
轮数	16 轮	Feistel 迭代
每轮子密钥	48 bit	从 56 位主密钥派生的不同 48 位子密钥
辅助操作	IP（初始置换）、FP（最终置换）	纯比特重排，无密码学作用

4.3.2 完整加密流程（三步走）

64 bit 明文
    │
    ↓
[初始置换 IP]        ← 纯比特重排，无加密作用
    │
    ↓ (L₀=左32位, R₀=右32位)
    │
[第 1 轮 Feistel]    ← 使用子密钥 K₁
    │
[第 2 轮 Feistel]    ← 使用子密钥 K₂
    │
   ...（共 16 轮）...
    │
[第 16 轮 Feistel]   ← 使用子密钥 K₁₆
    │
    ↓ (L₁₆, R₁₆)
    │
[左右交换]           ← 得到 (R₁₆, L₁₆)
    │
    ↓
[最终置换 FP = IP⁻¹] ← 逆初始置换
    │
    ↓
64 bit 密文

步骤详解：

步骤 1：初始置换 IP（Initial Permutation）

对 64 位输入明文按固定的比特位置表重新排列——仅改变比特顺序，不做任何计算。设计初衷无密码学作用，仅适配 1970 年代硬件电路的布线标准（方便在当时的芯片上布线）。IP 和 FP 对安全性没有任何贡献——现代分析中直接忽略。

步骤 2：16 轮 Feistel 迭代（核心）

IP 输出拆分为左 32 位 L₀、右 32 位 R₀。每轮规则：

其中： - K_i：第 i 轮48 位轮密钥，与 F 函数的 48 位扩张输出匹配 - F(R_i − 1,K_i)：DES 核心轮函数，32 位输入 + 48 位密钥 → 32 位输出

步骤 3：末尾交换 + 最终置换 FP

16 轮结束后输出 (L₁₆,R₁₆)。先交换得到 (R₁₆,L₁₆)（因为加密过程没有最后一次交换，解密时需要从 L₁₆, R₁₆ 反推 L₁₅, R₁₅）。然后执行 FP = IP⁻¹，输出 64 位密文。

4.3.3 DES 密钥扩展（Key Schedule）算法

输入 56 位有效主密钥（从 64 位原始密钥中去掉 8 个校验位），通过以下流程生成 16 组 48 位轮密钥：

PC-1 置换：56 位 → 56 位（置换 + 丢弃校验位），分成两半各 28 位 (C₀,D₀)
循环左移：每轮 (C_i,D_i) 各循环左移 1 或 2 位（轮 1/2/9/16 移 1 位，其余移 2 位）
PC-2 压缩置换：从 56 位的 (C_i,D_i) 中选出 48 位 = 本轮子密钥 K_i
重复 16 次

💡 密钥扩展的设计原则：每轮使用主密钥的不同子集（通过循环移位改变选中的位），确保各轮子密钥之间既有相关性（都源自主密钥）又各不相同。

4.4 DES 轮函数 F 完整拆解（32-bit → 32-bit）

F 函数是 DES 中所有密码学操作发生的地方——非线性、混淆、扩散全部集中于此。其余部分（IP、FP、Feistel 框架）都是纯比特搬运。

$函数扩张轮密钥盒替换（非线性）置换$

输入：32 位右半分组 X + 48 位轮密钥 K_i

输出：32 位结果（与左半分组异或，实现混淆）

步骤 1：E 扩张盒（Expansion Box） — 32 bit → 48 bit

功能：将 32 位输入”拉长”到 48 位，使其与 48 位轮密钥长度匹配（这样才能执行按位异或）。

实现方式：纯粹比特复制 + 移位重排——没有密码学运算： - 32 位中的 16 个比特各出现一次 - 32 位中的 16 个比特各出现两次（复制）

例如：输入位置 1→输出位置 2 和 48；输入位置 32→输出位置 1 和 47（具体映射由标准 E 表定义）。

扩张的目的：不仅匹配密钥长度，还实现了一种隐式的扩散——输入的一个比特影响扩张输出中的 2 个位置，进而经 S 盒影响更多位置。

步骤 2：异或轮密钥 — 48 bit ⊕ 48 bit → 48 bit

48 位扩张输出 ⊕ 48 位轮密钥 K_i = 48 位中间结果。这是 F 函数中唯一密钥参与的操作——将密钥信息”注入”数据通路。

步骤 3：S 盒替换（Substitution Box） — DES 安全性的唯一来源

⚠️ 这是整个 DES 中最关键的组件——所有安全性都来自这一步。其余所有操作（E 扩张、P 置换、IP、FP、子密钥异或）都是线性的，只有 S 盒引入了非线性。

将 48 位中间结果平均切分为 8 组（每组 6 bit），依次送入 8 个独立的 S 盒 S₁ ∼ S₈：

每个 S 盒：6 bit 输入 → 4 bit 输出
输入：48 bit → 输出：8 × 4 = 32 bit

单个 S 盒的查表规则（具体操作）：

每个 S 盒内部存储一张 4 行 × 16 列 的查找表，共 4 × 16 = 64 个表项，每项为 4 bit 数值。这恰好覆盖全部 2⁶ = 64 种 6 位输入。

给定输入 6 比特 b₀b₁b₂b₃b₄b₅：

行号 = 首尾比特 b₀b₅ 拼接成的 2 位二进制数（值的范围：0 ∼ 3，共 4 行）
列号 = 中间 4 比特 b₁b₂b₃b₄ 拼接成的 4 位二进制数（值的范围：0 ∼ 15，共 16 列）
输出 = 查找表中该行该列交点处的 4 位数值

为什么用首尾比特做行号？ 这是 NSA 特意设计的——让相邻的输入值（汉明距离 1）可能映射到不同的行，从而打散输出分布，抵抗差分攻击。

步骤 4：P 置换盒（Permutation Box） — 32 bit → 32 bit

对 S 盒拼接得到的 32 位结果做纯比特位置的重新排列（移位扩散）。

目的：打散 8 个 S 盒的输出比特——让本轮一个 S 盒的输出比特，在下一轮经 E 扩张后，能影响到多个不同的 S 盒。这样经过若干轮后，每一个输入比特都影响到每一个输出比特（雪崩效应）。

⚠️ E 盒、P 盒、IP、FP、异或轮密钥——这些全部是线性操作（仅涉及按位 XOR 和比特重排）。它们在密码学上等价于固定矩阵的模 2 乘法。如果 S 盒也是线性的，整个 DES 就等价于一个巨大的二元矩阵乘法，几百个明-密文对就可以解出密钥。

4.5 S 盒深度讲解：非线性是 DES 安全的唯一保障

这是 Boneh 课程中最具启发性的部分——通过”如果 S 盒是线性的会怎样”这个思维实验，深刻展示非线性在密码学中的核心地位。

4.5.1 思维实验：假设 S 盒是线性变换

线性函数的定义：输出是输入的线性组合（仅通过按位异或和常数乘法，无非线性查找表）。

如果 DES 的 8 个 S 盒全部是线性变换：

全系统退化：整个 DES 的所有组件（IP + FP + E 扩张 + 轮密钥异或 + P 置换 + 线性 S 盒）全部都是 GF(2) 上的线性操作。这意味着：

存在一个固定的二元矩阵 B（大小 64 × 832）使得：

$密文向量明文向量（位）轮密钥（位）轮密钥（位）轮密钥（位）$

总输入 832 维 = 64（明文）+ 16 × 48（全部轮密钥）= 64 + 768 = 832。

致命漏洞——线性叠加性质：线性变换满足：

DES_k(m₁) ⊕ DES_k(m₂) = DES_k(m₁⊕m₂) ⊕ DES_k(0)

这种严格的代数等式在真随机置换中出现的概率是 1/2⁶⁴（几乎不可能）。攻击者只需收集 832 组明文-密文对（与输入维度相同），即可建立 64 × 832 的线性方程组，通过高斯消元（复杂度 O(832³)，微秒级别）直接解出全部轮密钥 → 还原 56 位主密钥。DES 瞬时崩溃。

4.5.2 随机 S 盒也不安全

也许你会想：既然纯线性 S 盒不行，那就随机填充 S 盒的数值——应该够”非线性”了吧？

实验事实：对随机生成的 S 盒进行统计分析发现——64 种 6 位输入中，大约60 种输入对应的输出仍可以用某个线性函数高概率近似。大部分随机查找表的输入-输出映射天然具有强线性相关性（这是高维二元空间中不可避免的现象）。

这意味着：使用随机 S 盒的 DES 虽然不完全是线性系统，但存在高概率的线性近似（偏差 ε 可能很大），攻击者可以用线性密码分析（见第六部分）以远低于 2⁵⁶ 的复杂度破解。

4.5.3 NSA 如何设计 S 盒：四条硬性约束

NSA 专门设计了 S 盒以对抗已知和可预见的密码分析技术（他们早在 1974 年就知道了差分密码分析）：

设计约束	具体含义	对抗的攻击
极低线性相关性	任何输入比特的线性组合与输出比特的线性组合之间，相关性必须最小化	线性密码分析
差分均匀性	固定输入差分下，输出差分的分布尽可能均匀（无高概率差分对）	差分密码分析
非线性度最大化	每个 S 盒的布尔函数离所有仿射函数的汉明距离尽可能大	所有代数攻击
无简单代数表达式	无法用少量 XOR/AND 运算等价描述 S 盒映射	代数攻击（如插值攻击）
压缩映射	6 位输入 → 4 位输出（非双射），消除可逆性带来的代数结构	利用双射性质的攻击

🔑 S 盒核心定位总结：整个 DES 包含以下组件：IP/FP（纯置换）、E 扩张（复制+移位）、轮密钥异或（XOR）、P 置换（纯置换）——全部是 GF(2) 上的线性操作。S 盒是 DES 中唯一的非线性部件，DES 的全部安全强度 100% 依赖 S 盒的非线性构造。去掉非线性 S 盒 → DES 等价于 832 维线性方程组 → 毫无密码安全可言。

第五部分：AES 高级加密标准 — 深度解析

5.1 AES 的历史与设计竞赛

5.1.1 竞赛流程

时间	事件
1997 年 9 月	NIST 公开征集 AES 候选算法（要求：128 位分组，支持 128/192/256 位密钥）
1998 年 8 月	第一轮：收到来自 12 个国家的 15 份候选方案
1999 年 8 月	第二轮：5 个候选算法入围（MARS, RC6, Rijndael, Serpent, Twofish）
2000 年 10 月	NIST 宣布 Rijndael（比利时密码学家 Joan Daemen 和 Vincent Rijmen 设计）胜出
2001 年 11 月	正式成为美国联邦标准 FIPS 197

评选标准：安全性（最重要）、性能（软件/硬件）、实现灵活性（从 8 位微控制器到超级计算机）、设计简洁性（越简单越容易分析）

5.2 SPN（代换-置换网络）vs Feistel 网络 — 两种架构哲学的对比

直觉对比：DES 的 Feistel 像”折纸”——每次只折一半，反复折叠；AES 的 SPN 像”揉面”——每次全部揉搓，全位参与。

架构差异深度分析

维度	DES（Feistel）	AES（SPN）
每轮处理范围	仅改变一半的位（R_i 被 L_i − 1 ⊕ F(R_i − 1,K_i) 替换，L_i 不变直接搬运）	所有 128 位同时参与变换
S 盒大小	8 个 6→4 S 盒	1 个 8→8 S 盒（作用于每个字节）
S 盒可逆性	不需要——Feistel 整体提供可逆性	必须可逆——SPN 每层自身必须可逆
轮函数结构	F(R_i − 1,K_i) 作用于半分组	整个 4×4 状态矩阵同时变换
加密=解密？	加密和解密使用相同结构（仅轮密钥顺序相反）	加密和解密结构不同（逆 S 盒、逆 ShiftRow、逆 MixColumn）
轮数	16 轮（因每轮只影响一半）	10 轮（因每轮全位参与，效率更高）
设计哲学	“通过半轮重复达到全位混淆”	“每轮全位并行变换，快速达到雪崩”

为什么 AES 更高效？

Feistel 每轮只有 32 位被修改（DES 中的 F 函数输出 32 位），要经过多轮才能让所有 64 位都充分混淆。SPN 每轮 128 位全部参与 S 盒替换和线性扩散，每轮的”混淆强度”更高，所以总轮数更少（10 vs 16），且 128 位 vs 64 位的安全强度也更高。

5.3 AES-128 全局参数与状态表示

参数	值	说明
分组长度	128 bit（16 字节）	所有 AES 版本不变
内部状态	4 行 × 4 列字节矩阵	按列优先顺序排列：前 4 字节填第 0 列，接下来第 1 列…
主密钥	128 bit（16 字节）	密钥也排列为 4×4 字节矩阵
总轮数	10 轮	每轮包含 ByteSub + ShiftRow + MixColumn + AddRoundKey
轮密钥	11 组 128 位子密钥 K₀ ∼ K₁₀	K₀ = 原密钥（初始白化），K₁ ∼ K₁₀ 由密钥扩展生成
最后一轮特殊	无 MixColumn	仅 ByteSub + ShiftRow + AddRoundKey

状态矩阵的字节排列方式

AES 的 16 字节状态排列为 4×4 矩阵时，按列优先顺序：

输入 16 字节: b₀ b₁ b₂ b₃ b₄ b₅ b₆ b₇ b₈ b₉ b₁₀ b₁₁ b₁₂ b₁₃ b₁₄ b₁₅

排列为 4×4 矩阵（列优先）:
┌               ┐
│ b₀  b₄  b₈  b₁₂ │  第 0 行
│ b₁  b₅  b₉  b₁₃ │  第 1 行
│ b₂  b₆  b₁₀ b₁₄ │  第 2 行
│ b₃  b₇  b₁₁ b₁₅ │  第 3 行
└               ┘
  ↑    ↑    ↑     ↑
 第0列 第1列 第2列 第3列

💡 为什么是列优先而不是行优先？因为 MixColumn 操作是按列进行的——列优先排列使同一列的 4 个字节在内存中连续，有利于缓存和 SIMD 优化。

5.4 AES 单轮四大变换详解

5.4.1 ByteSub（字节替换）—— AES 安全核心（唯一非线性层）

输入/输出：对 4×4 状态矩阵的每一个字节（共 16 字节）独立应用 S 盒

s′[i][j] = S-Box[s[i][j]], i, j = 0, 1, 2, 3

AES S 盒的数学结构（区别于 DES 的随机查找表）：

AES 的 S 盒不是随机设计的——它有严格的数学定义，基于有限域 GF(2⁸) 上的运算：

求逆元：将输入字节 x 视为 GF(2⁸)（模不可约多项式 x⁸ + x⁴ + x³ + x + 1）中的元素，计算 x⁻¹（0 的逆元定义为 0）
仿射变换：对逆元结果再应用一个固定的仿射变换（GF(2) 上的矩阵乘法 + 常数异或）

S-Box[x] = M ⋅ x⁻¹ ⊕ c

其中 M 是 8 × 8 的二元固定矩阵，c 是 8 位固定常数向量。

为什么用逆元？ - GF(2⁸) 中的乘法逆元具有已知最高的非线性度之一 - 逆元函数的代数结构简单但行为复杂——输入微小变化导致输出剧烈变化（因为求逆元不是线性运算） - 有坚实的数学理论支撑其安全性分析

仿射变换的作用： - 打破 GF(2⁸) 逆元可能存在的代数结构（如固定点 x = 1 的逆元还是 1） - 使 S 盒没有不动点（S-Box[x] ≠ x 对所有 x 成立）和反不动点（S-Box[x] ≠ x̄）

💡 DES vs AES S 盒对比： - DES：8 个 6→4 S 盒（非双射），数值由 NSA 设计（未公开设计准则），非线性来自”精心挑选的查找表” - AES：1 个 8→8 S 盒（双射），数学公式公开，非线性来自 GF(2⁸) 求逆+仿射变换

5.4.2 ShiftRow（行移位置换）—— 扩散层 1

对状态矩阵的每一行执行不同量的循环左移：

s′[i][j] = s[i][(j+i) mod 4], i, j = 0, 1, 2, 3

行号 i	移位量	效果
第 0 行	不移位	保持不变
第 1 行	循环左移 1 字节	该行原本第 1 列的元素移动到第 0 列
第 2 行	循环左移 2 字节	该行原本第 2 列的元素移动到第 0 列
第 3 行	循环左移 3 字节	该行原本第 3 列的元素移动到第 0 列

为什么需要 ShiftRow？ ByteSub 是对每个字节独立操作的——如果不做 ShiftRow，同一列 4 个字节之间没有任何交互。ShiftRow 将不同列的字节”调换”到同一列，使下一轮的 MixColumn 能将来自不同列的字节混合。这就是扩散。

5.4.3 MixColumn（列混合）—— 扩散层 2（AES 最精妙的线性层）

对状态矩阵的每一列（4 个字节）独立执行 GF(2⁸) 上的矩阵乘法：

其中所有运算在有限域 GF(2⁸) 上进行（模不可约多项式 x⁸ + x⁴ + x³ + x + 1）。

矩阵中的数值解释： - 01 = GF(2⁸) 中的乘法单位元（即不变） - 02 = 乘以多项式 x（即左移 1 位，若溢出则 XOR 0x1B） - 03 = 02 ⊕ 01（先乘 x，再 XOR 原值）

为什么要选这个特定矩阵？ 1. MDS（Maximum Distance Separable）性质：该矩阵具有最优的扩散特性——输入列中有 k 个非零字节时，输出列中至少有 5 − k 个非零字节（线性分支数为 5） 2. 计算效率高：系数只有 01、02、03，可以用 XOR 和移位快速实现，无需查表 3. 自逆性：解密时的逆 MixColumn 矩阵系数为 0E, 0B, 0D, 09，也是简单的常数

MixColumn 的扩散效果：改变了列的每一个字节，使得单个字节的变化迅速扩散到整列（4 字节）→ 下一轮经 ShiftRow 扩散到不同列 → 再经 MixColumn 扩散到更多列 → 2-3 轮内所有 16 个字节全部受影响（雪崩效应）。

⚠️ AES-128 的最后一轮省略 MixColumn。原因：最后一轮的 MixColumn 不增加安全性（因为密文之后不再被混淆——攻击者可以直接观察密文），省略它可以减少计算量，且使加密和解密最后一轮结构一致。

5.4.4 AddRoundKey（加回合密钥）

当前状态矩阵与回合密钥矩阵逐字节 XOR：

s′[i][j] = s[i][j] ⊕ K_round[i][j]

唯一与密钥相关的操作——将密钥信息”混入”数据通路。由于 XOR 运算极其高效，这一步的计算成本几乎为零。

AES 一轮完整数据流：

当前状态（4×4 矩阵）
    │
    ↓
[ByteSub]       ← 非线性替换（每个字节查 S 盒）
    │
    ↓
[ShiftRow]      ← 横向扩散（行内循环移位）
    │
    ↓
[MixColumn]     ← 纵向扩散（列内矩阵乘法，最后一轮省略）
    │
    ↓
[AddRoundKey]   ← 注入密钥（逐字节 XOR 轮密钥）
    │
    ↓
下一轮状态

5.5 AES 密钥扩展算法

AES-128 需要从 128 位（16 字节）主密钥生成 11 组 128 位（共 176 字节）的轮密钥。算法如下：

K₀ = 主密钥（直接使用——这就是”初始白化”）
对于 i = 1 到 10：
- 取 K_i − 1 的最后一列（4 字节）
- RotWord：循环上移 1 字节
- SubWord：对每个字节应用 AES S 盒
- Rcon：异或一个轮常数（每轮不同，基于 x^i − 1 在 GF(2⁸) 中的值）
- 然后与 K_i − 1 的前 4 列迭代 XOR 生成 K_i 各列

关键安全特性： - K 的第 i 列非线性依赖第 i − 1 列（通过 S 盒） - 轮常数确保不同轮生成的密钥不同 - 密钥扩展是可逆的——给定任意一轮子密钥，可以在一定程度上反推其他子密钥，但这对 AES 在相关密钥攻击场景下的安全性有影响

5.6 AES 硬件加速（AES-NI）

Intel 从 Westmere 架构（2010 年）起在 CPU 中内置了 AES 硬件加速指令集：

指令	功能	对应操作
`AESENC xmm1, xmm2`	执行一轮标准加密	XOR 轮密钥 + ByteSub + ShiftRow + MixColumn
`AESENCLAST xmm1, xmm2`	执行最后一轮加密	XOR 轮密钥 + ByteSub + ShiftRow
`AESDEC xmm1, xmm2`	执行一轮标准解密	XOR 轮密钥 + InvByteSub + InvShiftRow + InvMixColumn
`AESDECLAST xmm1, xmm2`	执行最后一轮解密	XOR 轮密钥 + InvByteSub + InvShiftRow
`AESKEYGENASSIST`	辅助密钥扩展	计算 RotWord + SubWord + Rcon

AES-128 加密仅需：9 × AESENC + 1 × AESENCLAST = 10 条指令，在硬件上约 10 个时钟周期即可完成 128 位的加密。吞吐量可达约 1-3 GB/s（具体取决于 CPU 核心数和工作频率）。

💡 有 AES-NI 硬件加速时，AES 的速度可以和软件流密码（如 Salsa20）媲美甚至更快。这也是 AES 被广泛部署在 TLS、磁盘加密、数据库加密等场景的关键原因——硬件加速使”使用分组密码”不再意味着性能损失。

5.7 AES-256 与相关密钥攻击

AES-256 的特殊弱点：AES-256（14 轮）的密钥扩展算法存在一个设计缺陷——其密钥编排的扩散不如 AES-128 充分。这导致了一种特殊的攻击：

相关密钥攻击（Related-Key Attack）： - 前提条件：攻击者掌握多组使用高度相似密钥加密的明-密文对——任意两个密钥之间的汉明距离（不同比特数）极小 - 攻击效果：利用密钥扩展的结构缺陷，将穷举复杂度从 2²⁵⁶ 降低到约 2¹⁰⁰（理论值） - 实际威胁：极低——2¹⁰⁰ 仍远超出当前计算能力；且前提条件（攻击者能控制密钥之间的相似性）在绝大多数实际系统中不成立

⚠️ 防御：确保密钥随机独立生成（不要使用”密钥 1 和密钥 2 只差一个比特”这样的关联密钥）。在正常实践中，密钥由安全随机数生成器独立生成，相关密钥攻击完全不是威胁。

第六部分：分组密码的攻击方法全景

6.1 攻击分类总览

分组密码的攻击可以从两个完全不同的维度切入：

攻击维度	攻击对象	本质	典型方法
实现层面	密码算法的物理/软件实现	利用物理信息泄露或计算错误	侧信道（计时、功耗、电磁、缓存）、故障注入
数学层面	密码算法本身的数学结构	利用统计偏差或代数性质	线性分析、差分分析、代数攻击

🔑 关键区别：实现攻击不关数学算法的事——即使数学上绝对安全的密码，如果实现在硬件上且没有防护，也可能被侧信道攻击在几秒内破解。反之，数学攻击针对的是密码算法本身的抽象定义——无论用什么方式实现，只要算法存在统计偏差，数学攻击就有效。

6.2 实现层面攻击

6.2.1 侧信道攻击（Side-Channel Attacks）

直觉：密码的数学定义是”干净的”——只有输入和输出。但物理实现会不可避免地泄露额外信息：运行时间、功耗、电磁辐射、缓存访问模式等。这些”附带信号”与密钥比特有统计相关性，攻击者测量这些信号即可绕过数学直接窃取密钥。

计时攻击（Timing Attack）

原理：不同密钥比特参与的代码路径执行时间不同 → 测量总加密时间 → 统计推断密钥比特。

一个简化的示例：

1
2
3

# 如果密钥比特为 1 时多执行一次乘法（耗时 100ns）
if key_bit == 1:
    result *= x  # 额外耗时

攻击者对同一明文用不同密钥猜测重放，测量 100ns 级别的时间差，即可逐位还原密钥。

实战案例：在智能卡上通过高精度计时，可以完整提取 AES-128 密钥（即使数学上 AES 完全安全）。

差分功耗分析（Differential Power Analysis, DPA）

原理：CMOS 电路在处理比特 0 和比特 1 时消耗的电流稍有不同（约几微安到几毫安的差异），通过高精度示波器采集功耗曲线，并结合统计方法，可以逐位还原密钥。

对 DES 的可视化效果： - DES 的 16 轮 Feistel → 功耗曲线清晰出现 16 组高低峰值，一一对应 16 轮运算 - IP 初始置换和 FP 最终置换在曲线首尾有特征波形 - 攻击者可以”看到”轮密钥在硬件中的活动痕迹

攻击流程： 1. 对芯片输入大量随机明文，用高精度示波器记录每次加密的功耗波形 2. 对每个可能的子密钥猜测（如 DES 的 6 位 S 盒输入 → 猜测对应的 6 位子密钥），计算理论功耗值 3. 将理论值与实际功耗做皮尔逊相关性分析（Pearson Correlation） 4. 相关性最高的猜测 = 正确的子密钥 5. 逐 S 盒破解，最终还原完整密钥

6.2.2 故障攻击（Fault Attack）

原理：人为破坏芯片正常运算（制造一个”计算错误”），对比正确密文和错误密文，利用差值反推密钥。

故障制造手段： - 时钟毛刺（Clock Glitch）：超短时钟脉冲导致某些寄存器写入失败 - 电压骤降：瞬时降低供电电压使部分逻辑出错 - 电磁脉冲：用强电磁场干扰芯片内部信号 - 激光注入：用激光精确照射芯片特定区域改变逻辑状态

经典案例：在 AES 加密的最后一轮前注入故障，使某个字节在 ByteSub 前被翻转。错误密文与正确密文之间的差异 = S 盒[正确值] ⊕ S 盒[故障值]，可以直接恢复最后一轮的轮密钥 → 从轮密钥反推主密钥。仅需数对正确/错误密文即可完成攻击。

6.2.3 实现层面防御

防御技术	原理	代价
恒定时间实现	所有代码路径执行时间完全相同（无数据依赖分支）	代码更复杂，可能降低性能
掩码（Masking）	在每次加密前用随机值”掩盖”中间值，使功耗与真实数据脱钩	2-3 倍性能开销
多重运算校验	同一加密运行 2 次，对比结果；不一致则丢弃（故障防御）	2 倍性能开销
硬件防护	金属屏蔽层、光传感器、电压/频率监控	硬件成本增加

🔑 工程核心教训（Boneh 反复强调）： 1. 绝不自行从零实现分组密码——自己实现的 AES 极大概率存在侧信道漏洞 2. 使用经过专业审计的加密库（OpenSSL、BoringSSL、libsodium 等），它们已内置抗侧信道、抗故障设计 3. 自研密码算法 + 自研底层加密实现 = 双重高危

6.3 数学密码分析

6.3.1 暴力穷举基础理论（Exhaustive Search）— 攻击的”基线”

在设计任何密码分析攻击之前，首先需要考虑基线：直接尝试所有可能的密钥，直到找到正确的那一个。

6.3.1.1 穷举攻击的形式化目标

攻击场景：攻击者掌握若干组已知的明文-密文消息对：

(m_i, c_i=E(k,m_i)), i = 1, 2, …

目标是找到密钥 k，使得 c_i = E(k,m_i) 对所有已知消息对成立。

6.3.1.2 核心引理：一对明-密文几乎唯一确定密钥

引理：若 DES 是一个理想的密码（即从所有 2⁵⁶ 个随机可逆函数中随机选取一个，将 56 位密钥映射到 64 位密文），则对于任意给定的一对明文 m 和密文 c，有超过 99.5% 的概率最多只有一个密钥 k 满足 c = DES(k,m)。

形式化证明：

考虑一个错误的密钥 k′ ≠ k（k 是正确密钥）。在理想密码模型中，DES(k′,m) 是在 2⁶⁴ 个可能的 64 位密文中均匀随机分布的。它恰好等于正确密文 c 的概率为 1/2⁶⁴。

对所有 2⁵⁶ 个可能的密钥取并集界（Union Bound）：

直观理解： - 可能的密钥总数：2⁵⁶ - 可能的密文输出总数：2⁶⁴ - 每个错误密钥”碰巧”匹配正确密文的概率极其微小（1/2⁶⁴） - 所有 2⁵⁶ 个错误密钥的碰撞概率加起来也只有 1/256

因此，对于 DES 而言，一对明文-密文消息对几乎可以唯一确定密钥——该消息对只有一个密钥能将明文映射到密文。

💡 总结：设 |𝒦| 为密钥空间大小，|𝒞| 为密文空间大小。对于单对 PT-CT 消息对，存在多个匹配密钥的概率 ≤ |𝒦|/|𝒞|。只要密钥空间远小于密文空间（即 |𝒦| ≪ |𝒞|），单对消息就能近乎确定唯一密钥。

6.3.1.3 需要多少对明-密文才能唯一确定密钥？

虽然一对消息对已经能高概率唯一确定密钥，但在实践中，多个密钥候选可能碰巧都匹配一对消息对。使用两对消息对可以几乎完全消除这种可能：

密码算法	两对消息对存在歧义的概率	说明
DES（56 位密钥，64 位分组）	≈ 1 − 2⁻⁷¹ 为唯一确定	两对即可满足穷举攻击
AES-128（128 位密钥，128 位分组）	≈ 1 − 2⁻¹²⁸ 为唯一确定	安全性极高

结论：两对明-密文消息对完全足够支撑穷举攻击。问题的关键不在于需要多少消息对，而在于如何高效地在 2⁵⁶ 个密钥中找到那个唯一匹配的密钥。

6.3.1.4 穷举攻击的复杂度

对于 DES（56 位密钥）： - 最坏情况：2⁵⁶ 次加密尝试 - 平均情况：2⁵⁵ 次 - 每个密钥候选需用 1-2 组额外明-密文对验证以排除偶然匹配

判定标准：任何”有效”的密码分析攻击，其复杂度必须严格小于暴力穷举（对 DES < 2⁵⁶，对 AES-128 < 2¹²⁸），否则没有实际意义——因为直接用暴力穷举更简单。

6.3.2 DES 破解挑战（DES Challenge）— 暴力穷举的工程实践

暴力穷举不仅是理论基线，历史上曾被实际用于公开破解 DES。这一系列挑战由 RSA 公司发起，深刻展示了 56 位密钥为何不再安全。

挑战规则

RSA 公司给定若干组明文-密文分组对，挑战者需要找到对应的 DES 密钥，并用该密钥解密后续的密文消息 c₄, c₅, …。

破解时间线

时间	破解方式	耗时	意义
1997 年	分布式网络（互联网上数千名志愿者计算机协同计算）	约 3 个月	首次公开证明 DES 可被暴力穷举攻破
1998 年	分布式网络改进	约 39 天	速度大幅提升
1999 年	专用硬件 Deep Crack（EFF 资助建造）	约 22 小时	专用硬件使穷举 DES 成为低成本操作

🔑 历史结论：56 位密钥不应再继续使用。DES is completely dead。此后 NIST 加速推进 AES 的标准化进程（2000 年选定 Rijndael，2001 年正式成为 FIPS 197 标准）。

6.3.3 增强 DES 对抗穷举攻击

56 位密钥太短是 DES 的致命弱点。但在 AES 被标准化之前（以及大量遗留系统仍需继续运行），工业界需要基于现有 DES 硬件的补救方案。由此产生了若干”加强版 DES”构造。

6.3.3.1 Triple-DES（3DES）— 三次加密的急救方案

加密定义（EDE 模式——Encrypt-Decrypt-Encrypt）：

即 DES 重复运行三次，但中间一次用解密操作 D（而非加密 E）。

三个密钥不能相同：若 k₁ = k₂ = k₃，3DES 退化为单 DES，安全强度不变。

关键参数：

参数	值	说明
总密钥长度	3 × 56 = 168 位	三个独立 DES 密钥
有效安全强度	≈ 112 位	中途相遇攻击可将复杂度降至约 2¹¹²
加密效率	DES 的 1/3	三次完整的 DES 运算

为什么中间用解密 D 而不是加密 E？ 这是为了向后兼容单 DES：若设置 k₁ = k₂ = k₃ = k，则 3E((k,k,k),m) = E(k,D(k,E(k,m))) = E(k,m)（因为 D(k,E(k,m)) = m），3DES 退化为标准单 DES，旧硬件可以直接使用。

6.3.3.2 为何不用双重 DES（Double DES）？

一个自然的想法是：直接做两次 DES 加密，密钥长度 2 × 56 = 112 位：

2E((k₁,k₂), m) = E(k₁, E(k₂, m))

表面上看：2¹¹² 的密钥空间，暴力穷举似乎不可行。 实际上：双重 DES 容易遭受中途相遇攻击（Meet-in-the-Middle Attack），安全强度仅约 2⁶³，远低于预期的 2¹¹²。

6.3.3.3 中途相遇攻击（Meet-in-the-Middle Attack）详解

中途相遇攻击是经典的“空间换时间”算法，利用 DES 的加密-解密对称性，极大程度减少了攻击的时间开销。

攻击原理：

攻击者掌握一对已知明-密文 (m,c)，需要找到密钥对 (k₁,k₂) 满足：

c = E(k₁,E(k₂,m))

由于 DES 的对称性（加解密互为逆运算），上式等价于：

这揭示了攻击的核心：加密方向从明文出发、解密方向从密文出发，二者在中间”相遇”！

攻击步骤：

步骤 1：构建前向表

对所有可能的 k₂ ∈ {0, 1}⁵⁶（全部 56 位密钥），计算 E(k₂,m)，构造一张包含 2⁵⁶ 个条目的查找表：

k₂	E(k₂,m)
00…00	x₁
00…01	x₂
⋮	⋮
11…11	x_2⁵⁶

建表完成后，按中间值排序以便快速查找。

中间值排序：有很多的组，每个组使用其中位数代表，给每个组排序。

步骤 2：反向搜索碰撞

对所有可能的 k₁ ∈ {0, 1}⁵⁶，计算 D(k₁,c)，并在前向表中查找是否存在相等的中间值：

若 D(k₁,c) 等于表中某个 E(k₂,m) → 找到候选密钥对 (k₁,k₂)
即 E(k₂,m) = D(k₁,c) → (k₁,k₂) 是 2DES 的一个碰撞（Collision）

步骤 3：验证候选密钥

用额外的明-密文对验证候选密钥对的正确性（排除偶然碰撞）。

复杂度分析：

资源	量级	说明
时间开销	≈ 2⁶³	建表 2⁵⁶ 次加密 + 搜索 2⁵⁶ 次解密
空间开销	≈ 2⁵⁶ 个表项	存储前向表——每个表项约 16 字节，总计约 2⁶⁰ 字节 ≈ 1 EB（极大但理论可行）

对比： - 暴力穷举 2DES 的朴素复杂度：2¹¹²（遍历所有密钥对） - 中途相遇攻击复杂度：2⁶³ 时间 + 2⁵⁶ 空间 —— 远低于 2¹¹²

中途相遇攻击对 3DES 的威胁：

对于 3DES，中途相遇攻击的复杂度急剧增大： - 需要在”两个方向”中选择一个划分点（如 E(k₃,m) ↔︎ D(k₂,E(k₁,c)) 或 E(k₂,E(k₃,m)) ↔︎ D(k₁,c)） - 最优化攻击的复杂度约 2¹¹⁸，仍远超实际计算能力

因此，尽管 3DES 的效率只有 DES 的 1/3，但其安全性足够（约 112 位等效强度，中途相遇无法实际威胁）。

💡 中途相遇攻击的本质：将”从一端搜索”变成”从两端同时搜索”，在中间检查碰撞。这要求密码的加密和解密具有对称性（知道一端可以计算到中间）。这种”空间换时间”思想在密码分析中广泛应用。

6.3.3.4 DESX — 轻量级增强方案

DESX 是一种比 3DES 更高效的增强方案——通过在分组密码的输入和输出端各 XOR 一个密钥，以极小的性能代价显著增强安全强度。

形式化定义：

记 E 为从 n 位到 n 位的分组密码（如 DES，n = 64）。定义 EX 如下：

密钥结构：

密钥分量	长度	作用
k₁（输出白化）	n 位（与分组等长）	加密后 XOR——保护密文
k₂（内部密钥）	\|k\| 位（原分组密码密钥）	标准加密密钥
k₃（输入白化）	n 位（与分组等长）	加密前 XOR——保护明文
总密钥长度	2n + \|k\| 位	DESX：64 + 56 + 64 = 184 位

性能分析：DESX 在 DES 的基础上仅增加了两次 XOR 操作（块密码前后各一次），XOR 的开销相对于完整的 DES 加密几乎可忽略不计。因此 DESX 的效率与原始 DES 几乎相同。

⚠️ 思考题：为什么必须在内外部都做 XOR？

DESX 在分组密码的内部和外部均进行了 XOR 计算，这是必须的。若仅进行内部 XOR（E(k₂,m⊕k₃)）或仅进行外部 XOR（k₁ ⊕ E(k₂,m)），其加密强度和原始的 DES 没有太大差别。

原因：单侧白化只能阻止部分攻击模型： - 仅外部 XOR（k₁ ⊕ E(k₂,m)）：等同于对密文加了一个固定的掩码。如果攻击者能获得同一明文在不同密钥下的密文，可以通过 XOR 消去 k₁，退化为对 E(k₂,m) 的攻击。 - 仅内部 XOR（E(k₂,m⊕k₃)）：等同于对明文加了固定掩码后再加密。攻击者可以选择差分 (m₁⊕k₃) ⊕ (m₂⊕k₃) = m₁ ⊕ m₂，k₃ 被差分消去，退化为对 E 的差分攻击。

双重白化（内外同时 XOR）使攻击者无法通过简单操作消去任一白化密钥——必须同时面对三个未知量 (k₁,k₂,k₃)，才能显著增加攻击复杂度。

6.3.4 线性密码分析（Linear Cryptanalysis）— 统计偏差的艺术

核心洞察（Matsui, 1993）：理想随机置换中，任意”明文子集的 XOR ⊕ 密文子集的 XOR”等于”密钥子集的 XOR”的概率严格为 1/2（没有偏差）。如果实际分组密码中存在一个微小偏差 ε，使概率变为 1/2 + ε，那么通过收集约 1/ε² 组明-密文对，就可以通过”多数投票”从统计上还原密钥比特。

形式化：寻找线性近似关系

其中 m[i] 表示明文第 i 比特，c[j] 表示密文第 j 比特，k[l] 表示密钥第 l 比特。ε 称为线性偏差（Linear Bias）。

对 DES 的线性攻击（Matsui’s Algorithm 1）：

参数	值	说明
偏差来源	DES 第 5 个 S 盒的微弱线性相关性	S 盒设计不够”远离线性”
线性偏差 ε	≈ 2⁻²¹	每对明-密文有约 (1/2+2⁻²¹) 的概率满足线性关系
所需明-密文对	≈ 1/ε² = 2⁴² 对	统计”多数投票”需要这么多样本才能可靠地辨别出 ε 级别的偏差
直接恢复密钥比特	14 bit	通过线性关系可以直接恢复 14 位密钥
剩余暴力穷举	56 − 14 = 42 bit（2⁴²）	剩余 42 位密钥暴力穷举
总攻击复杂度	≈ 2⁴³	远小于暴力穷举的 2⁵⁶（快约 2¹³ = 8192 倍）

🔑 核心教训：密码内部任意一处（哪怕是单个 S 盒）的微小线性相关性，都可以被”放大”成完整的密码分析攻击。这解释了为什么 NSA 在设计 DES S 盒时如此强调”低线性相关性”。

6.3.5 差分密码分析（Differential Cryptanalysis）

核心洞察（Biham & Shamir, 1990）：不关注比特本身，而关注比特差分（XOR 差）。选择一对明文 m₁, m₂ 使其输入差分 Δm = m₁ ⊕ m₂ 为特定值（如某个特定比特位置的差异），观察对应密文差分 Δc = c₁ ⊕ c₂ 的分布。如果某些输入差分导致输出差分以高于均匀概率出现，就可利用此偏差进行攻击。

差分分析与线性分析的对比：

维度	线性密码分析	差分密码分析
分析对象	单个明-密文对的比特线性关系	一对明文的差分值及其对应密文差分值
攻击模型	已知明文攻击（Known Plaintext）	选择明文攻击（Chosen Plaintext——攻击者可以选择明文对）
利用的弱点	S 盒的线性近似偏差	S 盒的差分分布不均匀
DES 所需样本	2⁴² 对	2⁴⁷ 对（差分对）
NSA 防御	设计 S 盒最小化线性相关性	设计 S 盒最小化高概率差分对（NSA 早在 1974 年就做了这件事！）

💡 历史趣闻：NSA 在 1974 年设计 S 盒时就知道了差分密码分析（并做了防御），而学术界直到 1990 年才由 Biham 和 Shamir 独立重新发现这一技术。当差分分析发表后，NSA 密码学家私下说”我们等了 16 年你们才发现”。

6.4 量子攻击：Grover 算法

直觉：在 N 个物品中找到唯一个满足某条件的那个，经典计算机平均要检查 N/2 个，最坏 N 个。量子计算机利用量子叠加和振幅放大，只需约步——平方根加速。

对对称密钥密码的影响：

	经典穷举复杂度	Grover 量子复杂度	等效安全强度
DES（56 位）	2⁵⁶	2²⁸ ≈ 2.68 × 10⁸	极不安全——现代计算机秒破
AES-128	2¹²⁸	2⁶⁴	≈ 64 位安全（当前算力难以企及，但已接近边界）
AES-192	2¹⁹²	2⁹⁶	≈ 96 位安全
AES-256	2²⁵⁶	2¹²⁸	≈ 128 位安全（量子计算机也无破解可能）

🔑 落地结论： - 若大规模容错量子计算机（数百万量子比特）实现，所有对称密码安全强度减半 - 简单地加倍密钥长度就能防御 Grover 算法（128 → 256） - 长期保存的数据（“先存储，后解密”攻击模型）应优先使用 AES-256 - ⚠️ 当前现状：2024 年最大的通用量子计算机仅约 1000 个物理量子比特，距离运行 Grover 破解 AES 还需数十年

第七部分：理论构造 — PRG → PRF → PRP

这是 Boneh 课程中最具理论深度的章节。它回答了一个根本性问题：分组密码（PRP）的存在性——能否从更基础的原语（PRG）出发，经纯数学构造得到 PRP？ 答案是肯定的，且构造链条极其优美。

7.1 完整推导链路

$安全构造安全（轮）安全（分组密码）$

意义： - 理论：证明了只要存在安全 PRG（等价于 P ≠ NP），就一定存在安全分组密码——分组密码不是魔法，它有坚实的理论基础 - 工程：实践中我们直接使用 AES（一个原生的 PRP），不经过这些构造——因为理论构造的效率远低于原生 PRP。但理解这个链条意味着理解为什么”AES 可以作为 PRF 使用”（通过 PRP ⊆ PRF 和 PRP/PRF Switching Lemma）

7.2 第一步：由 PRG 构造 1-bit PRF

设安全 PRG G : 𝒦 → 𝒦 × 𝒦（输出扩展为种子的两倍长度，分成左右两半）。

定义 1-bit PRF F——输入空间只有 {0, 1}，即只能接受 1 比特输入：

$若（取输出的左半）若（取输出的右半）$

引理：若 G 是安全 PRG，则 F 是安全 1-bit PRF。

证明直觉：区分 F 和 1-bit 输入的真随机函数 f : {0, 1} → 𝒦，等价于区分 PRG 输出 (F(k,0),F(k,1)) = (G(k)[0],G(k)[1]) = G(k) 和真随机对 (r₀,r₁)。而这正是 PRG 安全的定义——所以如果 PRG 是安全的，F 就是安全的。

7.3 第二步：GGM 构造 — 扩展为 n-bit PRF

GGM = Goldreich-Goldwasser-Micali (1986)。三人都是图灵奖级别的密码学巨匠。

核心思想：用二叉树递归扩展输入空间。

构建一棵深度为 n 的完全二叉树： - 根节点（第 0 层）：存储种子 k - 每个内部节点：运行一次 PRG，产生左右两个子密钥，分别送给左右子节点 - 路径选择：输入 x = x₁x₂…x_n（n 个比特，从高位到低位）决定从根到叶的路径： - x₁ = 0 走左边，x₁ = 1 走右边（第一层选择） - x₂ = 0 走左边，x₂ = 1 走右边（第二层选择） - …以此类推 - 叶子节点的值 = F(k,x) 的最终输出

以 2-bit PRF 为例说明递归构造：

第一层：G(k) = (k₀,k₁)，其中 k₀ = G(k)[0], k₁ = G(k)[1]

第二层：G(k₀) = (k₀₀,k₀₁), G(k₁) = (k₁₀,k₁₁)

最终：

安全性证明思路（混合论证 Hybrid Argument）： 1. 假设存在攻击者 𝒜 能区分 GGM-PRF 与真随机函数 2. 构造 n + 1 个混合世界：H₀ = 全部真随机（真随机函数），H_n = 全部伪随机（GGM-PRF）；H_i 表示前 i 层使用 PRG（伪随机），第 i + 1 层起使用真随机 3. 𝒜 能区分 H₀ 和 H_n → 必存在某个相邻对 H_i 和 H_i + 1 能被区分 4. H_i 和 H_i + 1 的唯一区别是第 i + 1 层节点用的是 PRG 输出还是真随机值 → 这恰好构成一个 PRG 区分器！ 5. 与 PRG 安全矛盾 → GGM-PRF 安全

工程现实： - 极度低效：对于 128 位输入（如 AES），需要连续运行 128 次 PRG → 开销是 AES 的上百倍 - 价值在于理论：证明了 PRG ⇒ PRF 的可行性，是密码学基础理论的里程碑 - 实际替代：工程中直接使用 AES（原生 PRP/PRF），不经过 GGM 构造

7.4 第三步：Luby-Rackoff — 从 PRF 到 PRP

结论：将 3 轮独立密钥 Feistel 网络的轮函数替换为安全 PRF → 得到安全 PRP（分组密码）。

这完成了整个链条：PRG → PRF → PRP。从理论上证明了”只要存在安全的伪随机生成器，就能构造出安全的分组密码”。

第八部分：计数器模式 — 将 PRF 变成并行流密码

8.1 问题背景

分组密码本身只能加密恰好一个 n 比特的块。但现实中需要加密的消息可能是任意长度的。需要将分组密码这个”积木”以某种方式组合起来加密长消息——这就是工作模式（Mode of Operation）。

计数器模式（CTR Mode） 是其中最重要的工作模式之一——它把分组密码（PRF）变成了一个可并行的流密码。

8.2 参数设定

PRF：F : 𝒦 × {0, 1}ⁿ → {0, 1}ⁿ
密钥：k ∈ 𝒦（PRF 的密钥）
需求输出：t ⋅ n 比特（共 t 个 n 比特分组，例如加密 t × 128 比特的消息）
计数器：0, 1, 2, …, t − 1（用 n 比特表示，对于 AES-128 最多支持 2¹²⁸ 个计数）

8.3 构造定义

计数器模式 PRG G(k)：

每个计数器作为 PRF 的输入，PRF 输出一个 n 比特块。拼接所有输出即为 t ⋅ n 位密钥流。加密时将其与明文逐块异或：

密文 = m₀ ⊕ F(k,0) ∥ m₁ ⊕ F(k,1) ∥ … ∥ m_t − 1 ⊕ F(k,t−1)

8.4 独有优势：天然可并行

这是计数器模式相比于其他工作模式（如 CBC——密文分组链接模式）的最大优势：

工作模式	并行加密	并行解密	随机访问
CTR 模式	✅ 可以	✅ 可以	✅ 可以（加密第 i 块无需知道第 i − 1 块）
CBC 模式	❌ 不可以	✅ 可以	❌ 不可以

并行实现： - 核心 1：计算 F(k,0), F(k,2), F(k,4), …（偶数块） - 核心 2：计算 F(k,1), F(k,3), F(k,5), …（奇数块） - CPU 核心 3：计算 F(k,8), F(k,9), F(k,10), …（另一段）

多核心同时计算不同计数器的 PRF 值 → 加密速度随核心数线性提升。

💡 在需要高吞吐量的场景中（如 TLS 服务器每秒加密 GB 级别数据），CTR 模式的并行性结合 AES-NI 硬件加速，可以实现极高的性能。ChaCha20-Poly1305（流密码）和 AES-128-GCM（分组密码 CTR 模式）是现代 TLS 1.3 的两种主要对称加密方案。

8.5 安全性归约证明

定理：若 F 是安全 PRF，则计数器模式构造的 G 是安全 PRG（即输出的 t ⋅ n 位密钥流与真随机串计算不可区分）。

证明思路：

假设存在攻击者能区分 G(k) 与真随机 t ⋅ n 位串
将 G(k) 中的 PRF 替换为真随机函数
此时 G(k) 变成 (f(0),f(1),…,f(t−1))——因为 f 是真随机函数，这些输出是完全独立均匀随机的（注意：计数器永不重复，所以 f(0), f(1), … 是对 f 的不同输入，真随机函数对不同输入的输出是独立的）
所以替换后的输出是真正的随机串 → 任何攻击者都无法区分
如果攻击者在第 2 步和第 3 步之间的行为有差别 → 可构造区分器区分 PRF F 和真随机函数 → 与 PRF 安全矛盾
因此 G(k) 是安全 PRG

归约的直观理解：如果流密码不安全 → 就能区分 PRF 和真随机 → PRF 不安全。因我们知道 PRF 是安全的，所以流密码也必须是安全的。

8.6 注意事项

计数器不可重复使用：与非重复使用的 Nonce 一样，同一个密钥 k 下计数器值 (0,1,2,…) 必须保证唯一。如果多个消息使用相同的计数器和密钥 → Two-Time Pad。
计数器溢出：对 AES-128，计数器空间为 2¹²⁸，如果加密超过 2¹²⁸ 个块（≈ 2¹³² 字节 ≈ 5 × 10²⁷ TB），计数器会回绕。实际上这个量远超任何可能的应用场景。
Nonce 处理：实际中使用 Nonce∥Counter 拼接作为 PRF 输入，其中 Nonce 对每个消息唯一，计数器对消息内每个块递增。

第九部分：分组密码 vs 流密码全面对比

9.1 性能对比

维度	流密码	分组密码（纯软件）	分组密码（硬件加速）
加密方式	逐比特/逐字节 XOR	固定块整体置换	固定块整体置换
纯软件速度	快（~600 MB/s Salsa20）	较慢（~200 MB/s 纯软件 AES）	—
硬件加速速度	较少硬件支持	—	极快（~3 GB/s AES-NI）
典型应用	移动设备、IoT	无硬件加速的服务器	现代 x86/ARM 服务器

9.2 功能对比

维度	流密码	分组密码
理论抽象	PRG	PRP（也是 PRF）
输入/输出	无固定分组，任意长度	固定 n 比特分组
可逆性	XOR 自逆（加解密完全一致）	需要独立的 E 和 D 函数
构造 MAC	需额外设计（如 Poly1305）	可直接构造（CBC-MAC, CMAC, GCM）
工作模式	天然支持任意长度消息	需要工作模式（CTR/CBC/GCM）扩展
抗误用	对 Nonce 重复极度敏感	对 IV 重复也敏感，但部分模式（如 SIV）可缓解

9.3 实践中的使用建议

场景	推荐方案	理由
TLS 1.3 网络加密	AES-128-GCM 或 ChaCha20-Poly1305	行业标准，硬件加速 / 纯软件效率均高
磁盘/文件加密	AES-256-XTS	固定块，可随机访问，抗篡改
数据库字段加密	AES-256-GCM	需认证加密（防篡改）
低功耗 IoT	ChaCha20-Poly1305 或轻量 AES	无硬件 AES 时流密码更快
长期归档加密	AES-256-GCM	抗量子（256 位密钥 Grover 后仍有 128 位安全）

附录一：全章核心公式速查

概念	公式 / 说明
分组密码定义	E : 𝒦 × {0, 1}ⁿ → {0, 1}ⁿ, D : 𝒦 × {0, 1}ⁿ → {0, 1}ⁿ
正确性公理	∀k, m : D(k,E(k,m)) = m
迭代加密	s_i = R(k_i,s_i − 1), s₀ = m, s_r = c
PRF 定义	F : 𝒦 × X → Y（不要求可逆，允许碰撞）
PRF 全集大小	\|Funs[X,Y]\| = \|Y\|^\|X\|
PRP 定义	E : 𝒦 × X → X（一一对应 + 可逆）
PRP ⊆ PRF	每个 PRP 都是 X = Y 且可逆的 PRF
PRF 区分优势	Adv_𝒜, F^PRF = \|Pr [𝒜(F(k,⋅))=1] − Pr [𝒜(f_rand)=1]\|
PRP/PRF Switching Lemma	区分优势 ≤ q²/2^n + 1（q 次查询，n 位分组）
Feistel 一轮	L_i + 1 = R_i, R_i + 1 = L_i ⊕ f_i(R_i)
Feistel 逆变换	R_i − 1 = L_i, L_i − 1 = R_i ⊕ f_i(L_i)
Luby-Rackoff 定理	3 轮独立密钥 PRF Feistel = 安全 PRP
DES 全局参数	64 bit 分组 / 56 bit 有效密钥 / 16 轮 Feistel
DES F 函数	E 扩张(32→48) → XOR 轮密钥 → 8×S 盒(6→4) → P 置换
DES S 盒查表	行号 = b₀b₅, 列号 = b₁b₂b₃b₄, 输出 = 查找表[行][列]
线性 DES 崩溃	832 组明-密文对 → 线性方程组 → 直接解出密钥
AES 全局参数	128 bit 分组 / 128/192/256 密钥 / 10/12/14 轮 SPN
AES S 盒结构	S-Box[x] = M ⋅ x⁻¹ ⊕ c（GF(2⁸) 逆元+仿射）
AES 四大步	ByteSub → ShiftRow → MixColumn → AddRoundKey
AES 最后一轮	无 MixColumn
MixColumn 矩阵	4×4 MDS 矩阵（GF(2⁸)），分支数 = 5
AES-NI 指令	AESENC（一轮）/ AESENCLAST（最后轮）/ AESKEYGENASSIST
GGM 构造	PRG → 二叉树递归（深度 n，n 次 PRG 调用）→ n-bit PRF
GGM 2-bit PRF	F(k,00) = G(G(k)[0])[0], F(k,01) = G(G(k)[0])[1], …
计数器模式	G(k) = (F(k,0),F(k,1),…,F(k,t−1))
DES 穷举碰撞概率	Pr [∃k′≠k:c=DES(k,m)=DES(k′,m)] ≤ 2⁵⁶ × 2⁻⁶⁴ = 1/256
3DES 加密	3E((k₁,k₂,k₃),m) = E(k₁,D(k₂,E(k₃,m)))（EDE 模式）
3DES 密钥空间	3 × 56 = 168 位（有效强度 ≈ 112 位）
2DES 中途相遇	时间 2⁶³，空间 2⁵⁶，远低于朴素穷举的 2¹¹²
中途相遇核心等式	E(k₂,m) = D(k₁,c)（利用 DES 加解密对称性）
DESX 加密	EX((k₁,k₂,k₃),m) = k₁ ⊕ E(k₂,m⊕k₃)
DESX 密钥长度	64 + 56 + 64 = 184 位（输出白化 + DES + 输入白化）
线性攻击 DES	偏差 ε = 2⁻²¹（第 5 个 S 盒），2⁴² 对明密文，总复杂度 2⁴³
差分攻击	利用 S 盒差分分布不均，需 2⁴⁷ 对选择性明文对
Grover 量子攻击	暴力穷举复杂度 O(2ⁿ) → O(2^n/2)
DES 量子安全	2²⁸（极不安全）
AES-128 量子安全	2⁶⁴（接近边界）
AES-256 量子安全	2¹²⁸（量子安全）

附录二：易错点与考点标注（基础薄弱重点记忆）

分组密码输入输出长度一定相等（n 位入 → n 位出），流密码不限
PRF 允许碰撞（多对一），PRP 绝对无碰撞（一一对应、可逆）
PRP ⊆ PRF：PRP 是带置换结构的特殊 PRF，反过来不成立
Feistel（DES）整体提供可逆性，轮函数 f_i 不需要可逆；SPN（AES）每一步变换自身必须可逆
DES 淘汰根本原因不是架构缺陷，是 56 位密钥空间过小可暴力穷举
DES 的 S 盒是唯一非线性组件，去掉非线性 → DES 退化为线性方程 → 瞬时崩溃
AES 的 S 盒数学设计 = GF(2⁸) 逆元 + 仿射变换，DES 的 S 盒 = NSA 精心挑选的查找表
IP/FP 只是比特重排，无混淆/扩散能力，与安全性无关
E 盒（扩张）和 P 盒（置换）均为线性操作，它们做的是扩散而非混淆
计数器模式最大亮点是并行，传统序列密码（如 LFSR/RC4）必须串行
旁道攻击不破解数学算法，利用物理泄露（时间、功耗、电磁）；线性攻击是纯数学分析
相关密钥攻击仅在密钥人为高度相似时有效，正常随机生成密钥的场景完全无威胁
DES 分组 64 bit ≠ 有效密钥 56 bit，8 位是奇偶校验位（每字节最高位）
3DES 中间操作是解密 D（不是 E），目的是向后兼容单 DES
AES 最后一轮省略 MixColumn，不增加安全性且使加解密结构一致
GGM 构造理论完备但极度低效（128 次 PRG 调用 vs 10 轮 AES），不实际使用
Luby-Rackoff 定理 = 安全 PRF 经过 3 轮 Feistel 变成安全 PRP（分组密码的理论基础）
PRP/PRF Switching Lemma：查询次数 q ≪ 2^n/2 时 PRP 和 PRF 不可区分
安全性证明统一范式 = 不可区分游戏 + 归约法，是 Boneh 课程贯穿始终的方法论
分组密码纯软件速度比流密码慢（约 1/6），但 AES-NI 硬件加速后差距消失
单对 PT-CT 消息对几乎唯一确定 DES 密钥：错误密钥匹配概率 ≤ 2⁵⁶/2⁶⁴ = 1/256，即正确密钥唯一的概率 > 99.5%
中途相遇攻击本质：将”从一端穷举搜索”变为”从两端同时搜索，在中间检查碰撞”——空间换时间的经典应用
2DES 不安全：中途相遇攻击复杂度仅 2⁶³（时间）+ 2⁵⁶（空间），远低于预期的 2¹¹²
DESX 双重白化必须同时存在：仅内部 XOR 或仅外部 XOR 均无法有效增加安全强度——攻击者可通过差分或 XOR 消去单侧白化密钥
3DES 中途相遇复杂度约 2¹¹⁸：虽然存在理论攻击，但远超实际计算能力，3DES 在实践中仍是安全的（约 112 位等效强度）

📚 复习建议（按依赖关系分层阅读）：

第一层（基础，先读）： - 第一部分：理解分组密码的输入-输出定义和正确性公理 - 第二部分：理解迭代结构、混淆与扩散的区别

第二层（理论核心，精读）： - 第三部分：PRF/PRP 的安全定义和不安全构造反例——这是全章最重要的理论基础

第三层（工程实践，重点）： - 第四部分：DES 的 Feistel 网络和 S 盒非线性原理——理解”非线性为什么关键” - 第五部分：AES 的 SPN 结构和四大变换——理解现代分组密码的设计

第四层（安全性，选读）： - 第六部分：攻击方法分类——理解密码可以在哪些层面被攻击

第五层（进阶理论，有余力再读）： - 第七部分：PRG→PRF→PRP 理论构造——定理证明型内容（GGM、Luby-Rackoff） - 第八部分：计数器模式的构造与安全归约

Categories

Tags

Archives

Recent Posts