📑 本页目录（点开跳转）
05 · 流密码与 Nonce 铁律
⏱ 28 分钟 ｜ ⭐ 一条规则打穿过无数系统
🎯 一句话
流密码就是「用 PRG 模拟 OTP」。 它继承了 OTP 的简洁，也继承了 OTP 最致命的那条禁忌 —— 而这条禁忌在工程上有一个具体的名字：nonce 绝不能重复。
🌊 一、基本结构
密钥流 = PRG(K, nonce, 计数器)
C = M ⊕ 密钥流
⭐ 和 OTP 一模一样，只是密钥流是【生成的】而不是【真随机的】
优点：
| 优点 | 说明 |
|---|---|
| 不需要填充 | 逐比特/逐字节加密，明文多长密文就多长 |
| 加解密是同一套代码 | 都是异或 |
| 可以流式处理 | 数据边来边加密，不用等齐一个分组 |
| 随机访问 | 想解密第 1000 字节？直接算那个位置的密钥流 ⭐ |
💀 二、Nonce 铁律
⭐⭐ 在同一个密钥下，nonce 绝对不能重复。
如果 (K, nonce) 重复了：
密钥流完全相同 → 这就是【密钥复用的 OTP】
C₁ ⊕ C₂ = M₁ ⊕ M₂ ⭐ 第 3 章的灾难原样重演
→ crib dragging → 两条明文互相解开
💡 nonce 到底是什么，怎么用对
nonce = "number used once"
✅ 它【可以公开】—— 通常直接拼在密文前面一起发出去
❌ 它【绝对不能重复】—— 同一个 K 下
注意：nonce 不需要【随机】，只需要【唯一】
（IV 在某些模式下需要随机，这是两回事，见第 7 章）
三种正确做法：
| 做法 | 怎么做 | 风险 |
|---|---|---|
| 计数器 ⭐ | nonce = 0, 1, 2, 3... 持久化保存 | 状态丢失/回滚会重复（虚拟机快照！） |
| 随机 | 每次随机生成 | 生日碰撞：96-bit nonce 用 2⁴⁸ 次后风险不可忽略 |
| 随机扩展版 ⭐⭐ | 用 XChaCha20（192-bit nonce） | 192 bit 随机碰撞概率可忽略，最省心 |
📐 为什么 96-bit 随机 nonce 只能用 2⁴⁸ 次（想看再点）
生日界（第 9 章会详讲）：从 $N$ 个值里随机取 $q$ 个， 出现碰撞的概率约 $q^2/(2N)$。
对 96-bit nonce，$N = 2^{96}$。要让碰撞概率 ≤ $2^{-32}$：
$$\frac{q^2}{2\cdot 2^{96}} \le 2^{-32} \implies q \le 2^{32.5}$$
所以 NIST 建议同一密钥下随机 nonce 的使用次数不超过约 2³²。 超过就该换密钥了。
💡 这就是 XChaCha20 存在的理由：192-bit nonce 让这个限制彻底消失。
💥 真实事故：这条铁律的血债
| 事故 | 发生了什么 |
|---|---|
| WEP（Wi-Fi 加密） | IV 只有 24 bit，繁忙网络几小时就重复 → 无线网络被彻底打穿 |
| PlayStation 3 | ECDSA 签名的 k 值写死成常数 → 私钥被算出，主机被完全越狱 ⭐ |
| 微软 MS-CHAPv2 / PPTP | 密钥流重用 → VPN 流量可解密 |
| KRACK 攻击（2017） | 通过重放握手包强制受害者把 nonce 重置，从而重用密钥流 ⭐ |
| 多个云存储 SDK | 用文件名的哈希当 nonce，同名文件即重复 |
🔑 注意 KRACK 的思路有多毒： 它不攻击算法，它诱导系统自己把 nonce 重置 —— "确保 nonce 不重复"不只是生成时的事，还要防止被强制回滚。
🔧 三、一个反面教材：LFSR
线性反馈移位寄存器曾被大量用于流密码（GSM 的 A5/1、蓝牙的 E0）。
它的优点：
- 硬件实现极其便宜（就是几个触发器和异或门）
- 周期可以达到最大值 $2^n - 1$（当特征多项式是本原多项式时）
- 统计性质极好 —— 能通过各种随机性测试
💥 但它在密码学上是彻底失败的
⭐ 致命弱点：它是【线性】的
Berlekamp–Massey 算法：
给我【2L 个连续输出位】，我能在 O(L²) 时间内
完整重建出这个长度为 L 的 LFSR —— 包括它的抽头和当前状态
→ 然后你能预测【之后所有的输出】，也能回推之前的
例：L = 128 的 LFSR
看 256 位输出（32 字节！）→ 完全破解 💀
🔑 这印证了第 4 章的第一课： LFSR 的统计随机性完美，密码学价值为零。 因为"随机"的定义是"没有任何高效算法能占便宜"，而这里有一个 O(L²) 的算法。
试图修补的尝试，以及它们怎么倒的：
| 修补 | 想法 | 怎么被破的 |
|---|---|---|
| 非线性组合（Geffe 生成器） | 多个 LFSR 的输出过一个非线性函数 | 相关攻击：如果输出和某个 LFSR 有统计相关，就能单独恢复它 ⭐ |
| 非线性滤波 | 对单个 LFSR 的状态取非线性函数 | 代数攻击、快速相关攻击 |
| 不规则钟控（A5/1） | 让各个 LFSR 以不同速度移位 | 时间-存储折中攻击，几分钟破解 GSM 通话 |
💡 "相关攻击"是第 2 章那个教训的重演： 只要能把问题分解成独立的小块，难度就从乘法变成加法。 三个 LFSR 联合搜索是 2^(L₁+L₂+L₃)，分开搜是 2^L₁ + 2^L₂ + 2^L₃。
✅ 四、现代该用什么
❌ 不要用：RC4（有统计偏差，已被禁用）、A5/1、E0、任何自制的 LFSR 方案
✅ 用这些：
├─ ChaCha20 ← 软件实现快，无需硬件加速，移动端首选
├─ AES-CTR ← 有 AES-NI 硬件指令时最快
└─ ⭐ 但实际上你应该用【认证加密】：
ChaCha20-Poly1305 / AES-GCM
（见第 11 章 —— 光加密不够，必须带认证）
🔑 本章最实用的一条建议： 不要单独用流密码。 直接用 AEAD（认证加密）， 它把"加密 + 认证 + nonce 管理"打包成一个不容易用错的接口。
# ✅ 现代的正确做法
from cryptography.hazmat.primitives.ciphers.aead import ChaCha20Poly1305
import os
key = ChaCha20Poly1305.generate_key()
aead = ChaCha20Poly1305(key)
nonce = os.urandom(12) # ⚠️ 每条消息必须不同
ct = aead.encrypt(nonce, b"secret message", b"associated data")
pt = aead.decrypt(nonce, ct, b"associated data") # 篡改会直接抛异常 ⭐
🔗 和站内其他章的关系
| 相关的地方 | 和这一章的关系 |
|---|---|
| 第 3 章 OTP 密钥不能复用 | nonce 铁律就是它的工程版 ⭐ |
| 第 4 章 统计随机 ≠ 密码学安全 | LFSR 是这句话的最佳例证 |
| 第 2 章 分解成小块 | 相关攻击是同一个思路 |
| 第 7 章 CTR 模式 | 把分组密码变成流密码 |
| 第 11 章 AEAD | 流密码正确的用法 |
| AI 基础设施 · 训练稳定性与故障恢复 | ⚠️ nonce 重用最常见的工程成因就在那一章的场景里：从 checkpoint / 虚拟机快照恢复，把计数器一起倒了回去 |
| 智能体教程 · 工具设计 | 那里的防呆设计（Poka-yoke）是这条铁律唯一靠谱的落地方式：nonce 不能靠"记得别复用"，要让复用在接口上根本写不出来 ⭐ |
✅ 检查点
- 流密码的基本结构是什么？它的四个优点？
- Nonce 铁律是什么？违反了会发生什么？
- nonce 需要随机吗？需要保密吗？
- 为什么 96-bit 随机 nonce 有使用次数限制？XChaCha20 怎么解决的？
- KRACK 攻击的思路特别在哪？
- LFSR 统计性质很好，为什么密码学上失败？给我一个具体数字。
- 相关攻击的思路是什么？它和第 2 章哪个教训是同一个？
- 现代应该用什么？为什么不建议单独用流密码？
👀 答案
- 密钥流 = PRG(K, nonce, counter)，C = M ⊕ 密钥流。优点：不需要填充、加解密同一套代码、可流式处理、支持随机访问（想解第 1000 字节直接算那个位置）。
- 同一密钥下 nonce 绝对不能重复。违反则密钥流完全相同 = 密钥复用的 OTP，C₁⊕C₂ = M₁⊕M₂，crib dragging 让两条明文互相解开。
- 不需要随机，只需要唯一；不需要保密，通常直接拼在密文前发出去。（IV 在某些模式下需要随机，那是两回事。）
- 生日碰撞：随机取 q 个值碰撞概率约 q²/2N，96-bit 下 q 超过约 2³² 风险就不可忽略。XChaCha20 用 192-bit nonce，让这个限制彻底消失。
- 它不攻击算法，而是通过重放握手包诱导系统自己把 nonce 重置。教训：确保 nonce 不重复不只是生成时的事，还要防止被强制回滚。
- 因为它是线性的。Berlekamp–Massey 算法只需 2L 个连续输出位，就能在 O(L²) 时间内完整重建 LFSR。L=128 时，看 256 位（32 字节）输出即可完全破解。
- 如果组合输出和某个 LFSR 的输出有统计相关性，就能单独恢复那一个 LFSR。和第 2 章 Kasiski 一样是"把问题分解成独立小块"——联合搜索 2^(L₁+L₂+L₃) 变成 2^L₁+2^L₂+2^L₃。
- 用 ChaCha20-Poly1305 或 AES-GCM 这类 AEAD。不建议单独用流密码是因为光加密不提供完整性（可比特翻转），AEAD 把加密+认证+nonce 管理打包成不容易用错的接口。
🛑 可以停在这里
⚡ 走神救援
流密码=用 PRG 模拟 OTP：密钥流=PRG(K,nonce,counter)，C=M⊕密钥流。优点：不用填充、加解密同一套代码、可流式、支持随机访问。⭐⭐Nonce 铁律：同一密钥下 nonce 绝不能重复——重复则密钥流相同 = 密钥复用的 OTP，C₁⊕C₂=M₁⊕M₂。nonce 只需唯一不需随机，可以公开。三种做法：计数器（⚠️虚拟机快照回滚会重复）、随机（96-bit 只能用约 2³² 次，生日碰撞）、⭐XChaCha20 的 192-bit nonce 最省心。💥血债：WEP（IV仅24bit，几小时就重复）、PS3（k值写死成常数→私钥被算出，主机越狱）、MS-CHAPv2、⭐KRACK（不攻击算法，重放握手包诱导系统自己把 nonce 重置——防重复不只是生成时的事，还要防回滚）。LFSR 是反面教材：硬件便宜、周期达 2ⁿ−1、统计性质完美，但它是线性的——⭐Berlekamp–Massey 只要 2L 个输出位就能 O(L²) 重建整个 LFSR（L=128 时看 32 字节就破）。修补也没救：Geffe 生成器倒于相关攻击（输出与某个 LFSR 统计相关就能单独恢复它，联合搜索 2^ΣL 变成 Σ2^L），A5/1 几分钟破解 GSM。✅现代：ChaCha20 / AES-CTR，但⭐不要单独用流密码，直接用 AEAD（ChaCha20-Poly1305、AES-GCM），它把加密+认证+nonce管理打包成不易用错的接口。
下一节 👉 06-分组密码.md