📑 本页目录（点开跳转）
06 · 分组密码
⏱ 25 分钟 ｜ ⭐ 现代对称加密的地基
🎯 一句话
分组密码是一个由密钥控制的、固定长度的置换： 给它 128 bit，还你 128 bit，换个密钥就是完全不同的一张对应表。 几乎所有现代对称加密都建立在它之上。
🧱 一、定义与直觉
$$E_K: \{0,1\}^n \to \{0,1\}^n \quad\text{（可逆，$D_K(E_K(m)) = m$）}$$
💡 人话翻译：
想象一本巨大的字典，它把每个 128 bit 的值映射到另一个 128 bit 的值， 一一对应，没有重复。密钥的作用就是「选哪一本字典」。
K = 密钥A： 0000... → a7f3...
0001... → 9c2e...
...
K = 密钥B： 0000... → 3d81... ← 完全不同的一本
0001... → f0b6...
⭐ 核心概念：PRP 和 PRF
| 概念 | 全称 | 含义 |
|---|---|---|
| PRP | 伪随机置换 | 在固定密钥下，$E_K$ 看起来像一个随机的置换（可逆） |
| PRF | 伪随机函数 | 看起来像一个随机的函数（不要求可逆） |
分组密码的安全目标：它是一个好的 PRP
⭐ 关键定理（PRP/PRF 切换引理）：
当 n 足够大时，PRP 和 PRF 在 q 次查询下的区别 ≈ q²/2ⁿ⁺¹
→ 128-bit 分组，查询 2⁶⁴ 次以内，两者【几乎无法区分】
→ 所以可以【把分组密码当 PRF 用】（第 7 章 CTR 模式就是这么干的）⭐
📐 为什么 PRP 和 PRF 会有差别（想看再点）
随机函数允许碰撞：$f(x_1) = f(x_2)$ 是可能的。 随机置换不允许：它是一一对应的。
所以攻击者的区分策略是：查询 q 次，看有没有出现输出碰撞。
- 对随机函数：由生日界，出现碰撞的概率 ≈ $q^2/2^{n+1}$
- 对随机置换：永远不会碰撞
这就是两者的全部差距。$n=128$、$q = 2^{64}$ 时，这个优势约为 $2^{-1}$ —— 所以实际使用要保证同一密钥下的分组数远小于 $2^{64}$。
💡 这个 $2^{n/2}$ 的界叫「生日界」，它是很多模式的实际安全上限， 也是 AES 的 128-bit 分组在超大数据量下开始吃紧的原因。
🏛️ 二、两种经典结构
① SPN（代换–置换网络）—— AES 走的路
每一轮：
- ShiftRows ← 换位置
- MixColumns ← 列混合，提供【扩散】⭐
- AddRoundKey ← 异或轮密钥
🔗 这就是第 2 章 Shannon 说的混淆与扩散的工程实现： SubBytes 做混淆，ShiftRows + MixColumns 做扩散， 反复多轮，让改动 1 bit 的影响铺满整个分组。
雪崩效应实测：AES 改 1 bit 明文
→ 2 轮后就有约一半的 bit 变化
→ 10 轮后统计上和随机没有区别
② Feistel 网络 —— DES 走的路
把分组劈成左右两半 (L, R)：
L' = R
R' = L ⊕ f(R, K) ← f 可以是【任意】函数，不需要可逆 ⭐
解密：
R = L'
L = R' ⊕ f(L', K) ← 一模一样的结构，倒着跑
💡 Feistel 的漂亮之处： 不管 f 是什么（甚至可以完全不可逆），整体结构一定可逆。 这让设计者可以自由地把 f 设计得尽可能非线性，不用操心可逆性。
副产品：加密和解密可以复用同一套硬件，只是轮密钥顺序相反。
📊 三、该用哪个（以及不该用哪个）
| 算法 | 分组 | 密钥 | 状态 |
|---|---|---|---|
| DES | 64 bit | 56 bit | 💀 已死。1998 年专用机器 56 小时暴力破解 |
| 3DES | 64 bit | 112 bit 有效 | ⚠️ 已弃用。64-bit 分组导致 Sweet32 攻击 ⭐ |
| AES-128/256 | 128 bit | 128/256 | ✅ 默认选择，有硬件指令（AES-NI） |
| ChaCha20 | 流密码 | 256 | ✅ 无硬件加速时更快，移动端首选 |
💥 Sweet32（2016）：3DES 和 Blowfish 的分组只有 64 bit， 由生日界，传输约 2³² 个分组（32GB）就会出现分组碰撞，泄露明文信息。 这是"分组长度"本身导致的攻击，和密钥长度无关 —— 也是为什么现代标准把分组定在 128 bit。
⚠️ 一个常见误解
❌ "AES-256 比 AES-128 安全一倍"
✅ 实际情况：
· AES-128 的 2¹²⁸ 已经远超任何可行的攻击
· 选 AES-256 的真正理由是【抗量子】(Grover 算法把强度减半，
AES-256 → 128 bit 有效强度，见第 23 章) ⭐
· AES-256 轮数更多，性能略低
→ 日常用 AES-128 完全足够；有长期保密需求才上 256
🔬 四、怎么判断一个分组密码是安全的
没有人能"证明" AES 安全 —— 只能说它经受住了所有已知的攻击方法：
| 攻击方法 | 思路 |
|---|---|
| 差分密码分析 | 追踪"明文差值 → 密文差值"的概率偏差 |
| 线性密码分析 | 找"某些明文位 ⊕ 某些密文位 ⊕ 某些密钥位 = 0"的统计偏差 |
| 积分攻击 / 不可能差分 | 构造特殊的明文集合，看输出的结构性质 |
| 相关密钥攻击 | 利用密钥之间的已知关系 |
🔑 一个有意思的历史： DES 在 1977 年的设计就已经对差分密码分析免疫 —— 但差分分析直到 1990 年才被公开发表。 后来证实 IBM 和 NSA 当时就知道这个技术，只是没公开。
💡 这说明了公开审查的价值：AES 是公开竞赛选出来的（1997–2000）， 全世界密码学家攻了三年，这比任何单一机构的背书都可信。
🔗 和站内其他章的关系
| 相关的地方 | 和这一章的关系 |
|---|---|
| 第 2 章 混淆与扩散 | AES 的 SubBytes / MixColumns |
| 第 4 章 PRG | 分组密码在 CTR 下就是 PRG ⭐ |
| 第 5 章 流密码 | CTR 模式把分组密码变成流密码 |
| 第 7 章 工作模式 | 分组密码只能加密 128 bit，长消息怎么办 |
| 第 1 章 侧信道 | AES 的查表实现有缓存计时攻击，要用 AES-NI 或恒定时间实现 ⭐ |
| AI 基础设施 · 显存与带宽墙 | 缓存计时攻击的物理前提，就是那张内存层次表体现的东西：越往下越慢、差好几个数量级，而这个时间差可以测量，查表实现就靠它泄露密钥字节 ⭐ ⚠️ 注意那张表给的是带宽（Shared Memory/L1 比 HBM 约 5 倍），计时攻击吃的是访存延迟之比 —— 后者在 CPU 上（L1 vs DRAM）接近百倍 |
| AI 基础设施 · GPU 到底是什么 | Tensor Core 和 AES-NI 是同一个思路——把热点原语做进指令集；密码学这边还白得一个副产品：硬件实现天然是恒定时间的 |
✅ 检查点
- 分组密码的定义是什么？密钥的作用是什么？
- PRP 和 PRF 的区别？为什么可以把分组密码当 PRF 用？
- 攻击者怎么区分随机置换和随机函数？这给出了什么安全上限？
- SPN 的四个步骤各提供什么？
- Feistel 网络最漂亮的性质是什么？带来什么好处？
- Sweet32 攻击的根因是什么？它和密钥长度有关吗？
- AES-256 比 AES-128 好在哪？真正的理由是什么？
- 为什么说 AES 的公开竞赛比机构背书更可信？
👀 答案
- $E_K: \{0,1\}^n \to \{0,1\}^n$，一个可逆的、固定长度的置换。密钥的作用是选哪一本"字典"（哪个置换）。
- PRP 是伪随机置换（可逆、不碰撞），PRF 是伪随机函数（可碰撞）。因为 PRP/PRF 切换引理：q 次查询下差距约 q²/2ⁿ⁺¹，128-bit 分组在 2⁶⁴ 次查询内几乎无法区分。
- 查询 q 次看有没有输出碰撞——随机函数会碰撞（概率约 q²/2ⁿ⁺¹），随机置换永远不会。这给出 2^(n/2) 的生日界，即同一密钥下的分组数必须远小于 2⁶⁴。
- SubBytes 提供混淆、ShiftRows 换位置、MixColumns 提供扩散、AddRoundKey 混入轮密钥。反复多轮达成雪崩效应。
- 不管 f 是什么（甚至完全不可逆），整体结构一定可逆。好处：设计者可以自由地把 f 做得尽可能非线性；且加解密能复用同一套硬件，只是轮密钥顺序相反。
- 根因是分组长度只有 64 bit。由生日界，约 2³² 个分组（32GB）后出现分组碰撞泄露明文。和密钥长度完全无关——这是分组长度本身导致的，也是现代标准定在 128 bit 的原因。
- 主要是抗量子：Grover 算法把对称密码强度减半，AES-256 → 128 bit 有效强度。AES-128 的 2¹²⁸ 对经典计算机已远超可行范围，日常够用。
- 因为 AES 是 1997–2000 的公开竞赛选出来的，全世界密码学家公开攻了三年。对比：DES 对差分分析的免疫力是 IBM/NSA 私下知道但没公开的——公开审查让"没人攻破"真正有意义。
🛑 可以停在这里
⚡ 走神救援
分组密码 = 由密钥控制的、固定长度的可逆置换（给128bit还128bit），密钥的作用是选哪一本字典。⭐PRP（伪随机置换，可逆不碰撞）vs PRF（伪随机函数，可碰撞）：区分方法是查询 q 次看有没有输出碰撞，差距约 q²/2ⁿ⁺¹ → 生日界 2^(n/2)，所以 128-bit 分组在 2⁶⁴ 次内两者几乎无法区分，因此可以把分组密码当 PRF 用（CTR 模式的理论依据）。两种结构：SPN（AES）——SubBytes 混淆 / ShiftRows 换位 / MixColumns 扩散 / AddRoundKey，多轮迭代达成雪崩（改1bit，2轮后半数bit变化）；Feistel（DES）——L'=R, R'=L⊕f(R,K)，⭐漂亮之处：不管 f 是否可逆整体一定可逆，所以 f 可以尽情非线性，且加解密复用同一套硬件。选型：DES 已死（56bit密钥）、3DES 弃用（💥Sweet32：64-bit 分组，传 32GB 就出现分组碰撞——这是分组长度导致的，和密钥长度无关，也是现代定在128bit的原因）、AES-128 默认够用、ChaCha20 无硬件加速时更快。⚠️AES-256 不是"安全一倍"，真正理由是抗量子（Grover 把强度减半，256→128有效）。安全性无法证明，只能靠经受住差分/线性/积分/相关密钥分析——⭐AES 是公开竞赛选出来的，全世界攻了三年，这比机构背书可信（对比：DES 对差分分析的免疫是 IBM/NSA 私下知道却没公开的）。⚠️ AES 查表实现有缓存计时攻击，要用 AES-NI 或恒定时间实现。
下一节 👉 07-工作模式.md