📑 本页目录（点开跳转）
04 · 伪随机
⏱ 25 分钟 ｜ ⭐ "看起来随机"这句话怎么变严格
🎯 一句话
我们要用一个短种子造出一长串"随机"比特来代替 OTP 的密钥。 但"看起来随机"这个说法太模糊了 —— 这一章把它变成一个精确的、可证伪的定义。 而且这个定义会颠覆你对"随机性测试"的直觉。
🎲 一、先说清楚：什么不算随机性的标准
一个序列：
0 1 1 0 1 0 0 1 1 0 1 0 0 1 1 0 ...
它通过了：
✅ 0 和 1 的个数几乎相等
✅ 卡方检验
✅ 游程检验（连续相同位的分布正常）
✅ 频谱检验
✅ NIST 随机性测试全套
⭐ 但如果我告诉你：它是 LFSR 生成的，
那么看到前 2L 位，就能预测出后面【所有】位（第 5 章）
→ 它在统计上完美，在密码学上一文不值
🔑 本章第一课： 「统计随机」和「密码学安全」是两件完全不同的事。
统计测试问的是"分布对不对"；密码学问的是"有没有任何高效算法能占到便宜"。 前者是有限的一组检查，后者是对所有可能的攻击算法量化。
📐 二、PRG 的定义：不可区分性
定义：函数 $G: \{0,1\}^s \to \{0,1\}^\ell$（$\ell \gg s$，即"拉伸"） 是一个安全的 PRG，如果对任意多项式时间的判别器 $D$：
$$\Big|\Pr[D(G(U_s)) = 1] - \Pr[D(U_\ell) = 1]\Big| \le \text{negl}(s)$$
💡 人话翻译：
把「G 拉出来的串」和「真随机串」放在你面前，你分不出哪个是哪个。 不管你用什么方法（任何多项式时间算法），猜对的概率都不比抛硬币好多少。
想象一个游戏：
裁判抛硬币决定：
├─ 正面 → 给你 G(随机种子) 的输出
└─ 反面 → 给你一串真随机比特
你看完之后猜是哪种。
⭐ 如果你的正确率不能显著超过 50%，G 就是安全的
💡 这个定义为什么这么设计
| 设计选择 | 为什么 |
|---|---|
| "对任意判别器 D" | 不是列举有限种测试，而是覆盖所有可能的攻击 ⭐ |
| "多项式时间" | 承认无限算力必然能破（穷举种子），只要求高效攻击者做不到 |
| "negl 可忽略" | 优势必须比任何多项式的倒数还小，不能是 1% 这种"很小" |
💡 注意这个定义的形状：它把"安全"变成了一个可证伪的命题 —— 只要有人拿出一个具体的高效判别器 D，方案就死了。 🔗 这个"用不可区分性定义安全"的模式会在第 8 章再次出现， 那是整套教程的思维转折点。
🔮 三、Yao 定理：不可区分 ⟺ 不可预测
有另一个看起来更直观的定义：
Next-bit 不可预测性：给定输出的前 i−1 位， 任何高效算法都无法以显著优于 1/2 的概率猜中第 i 位。
Yao 定理（1982）：
$$\text{不可区分} \iff \text{next-bit 不可预测}$$
💡 为什么这个定理很有用： "不可区分"难验证（要对抗所有判别器）， "不可预测"好验证得多（只要证明预测下一位很难）。
有了 Yao 定理，你可以证简单的那个，白得难的那个。
📐 证明思路：混合论证（想看再点）
难的方向是「不可预测 ⟹ 不可区分」，用混合论证（hybrid argument）：
构造 $\ell+1$ 个分布：$H_i$ = 前 i 位来自 G，后 $\ell-i$ 位是真随机。
- $H_0$ = 全真随机
- $H_\ell$ = 全部来自 G
若 D 能以优势 ε 区分 $H_0$ 和 $H_\ell$，则由三角不等式， 必存在某个 i 使 D 能以优势 ≥ ε/ℓ 区分相邻的 $H_{i-1}$ 和 $H_i$。
而这两个分布只在第 i 位上不同（一个来自 G，一个真随机）—— 所以这个 D 可以直接改造成一个第 i 位的预测器。∎
💡 "混合论证"是密码学证明里最常用的工具： 把一个大差距拆成一串小差距，说明至少有一步的差距不小。
🌱 四、种子从哪来：熵源
⚠️ PRG 再安全，种子可预测的话一切归零
种子必须来自【真正的物理随机】：
├─ 硬件噪声（热噪声、振荡器抖动）
├─ CPU 指令 RDRAND / RDSEED
├─ 操作系统熵池：/dev/urandom、getrandom()、CryptGenRandom
└─ 用户输入的时间抖动（鼠标、键盘）
该用什么，不该用什么：
# ❌ 绝对不要：这是给模拟和游戏用的，可预测
import random
key = random.randbytes(32) # 💀 Mersenne Twister，看到 624 个输出即可完全还原
# ✅ 正确
import secrets
key = secrets.token_bytes(32) # ⭐ 走操作系统的 CSPRNG
import os
key = os.urandom(32) # ⭐ 同样正确
| 语言 | ✅ 该用 | ❌ 别用 |
|---|---|---|
| Python | secrets、os.urandom |
random |
| Java | SecureRandom |
Random |
| JavaScript | crypto.getRandomValues |
Math.random |
| Go | crypto/rand |
math/rand |
| C/C++ | getrandom() / BCryptGenRandom |
rand() |
💥 真实事故 —— 三个都是同一个错误： - Debian OpenSSL（2006–2008）：一行"清理未初始化内存"的改动， 让熵源只剩进程 ID → 可能的 SSH 密钥只剩 32768 个，两年后才被发现。 - Android Bitcoin 钱包（2013）：
SecureRandom初始化有缺陷， 导致签名用的 k 值重复 → 私钥被算出来，钱被盗（第 17 章会讲原理）。 - 各类嵌入式设备：开机时熵池是空的，生成的密钥高度重复 —— 有研究扫描全网发现成千上万台设备共用同一把 RSA 私钥。🔑 共同的教训：随机数是密码系统里最安静的失效点。 它坏掉的时候什么都不会报错 —— 加密照常工作，只是不再安全。
🏗️ 五、实践中的 PRG 长什么样
理论上：G 是一个抽象的拉伸函数
工程上：几乎总是【用分组密码或哈希在 CTR 模式下跑】
例：CTR_DRBG（NIST 标准）
输出 = AES_K(1) ‖ AES_K(2) ‖ AES_K(3) ‖ ...
↑ 计数器递增
例：ChaCha20 的密钥流生成
输出 = ChaCha20(K, nonce, 0) ‖ ChaCha20(K, nonce, 1) ‖ ...
🔗 第 7 章 CTR 模式讲的就是这个结构。 "把分组密码当 PRG 用"是现代对称加密的核心套路。
⚠️ 一个容易被忽略的性质：前向安全
如果攻击者【某一刻】拿到了 PRG 的内部状态，
他能不能算出【之前】的输出？
❌ 简单的 CTR 结构：能（状态就是 K 和计数器，往回倒即可）
✅ 带 reseed / 状态单向更新的设计：不能 ⭐
→ 这就是为什么 /dev/urandom 会周期性地混入新熵
🔗 和站内其他章的关系
| 相关的地方 | 和这一章的关系 |
|---|---|
| 第 3 章：OTP 密钥太长 | PRG 就是为了解决它 |
| 第 3 章：计算安全的妥协 | PRG 的定义就是这个妥协的形式化 |
| 第 5 章 LFSR | 统计完美但密码学上失败的典型 |
| 第 8 章 IND-CPA | 同一个"不可区分"模式 ⭐ |
| Kaggle · 数据泄露与外部数据 | 「对抗验证」训一个二分类器区分训练集和测试集——那就是本章定义里的判别器 D，AUC≈0.5 就是"不可区分" ⭐ |
| 模型上线之后 · 版本回溯与可复现 | ⚠️ 同一个 random，两个相反的目标：那边固定种子是要"任何人都能复现"，这里的要求恰恰是"任何人都不能预测" |
| AI 基础设施 · 训练稳定性与故障恢复 | checkpoint 清单里那一行「随机数状态」——那边把 PRG 状态当资产存下来，在这里存下来就等于泄露密钥（本章的前向安全） ⭐ |
✅ 检查点
- 为什么"通过了 NIST 随机性测试"不代表密码学安全？
- PRG 的安全定义是什么？用人话说一遍。
- 这个定义为什么要说"对任意判别器"而不是列举几种测试？
- Yao 定理说了什么？它为什么有用？
- 混合论证的基本思路是什么？
random.randbytes和secrets.token_bytes的区别？为什么前者致命？- 举一个随机数失效导致的真实事故，说明它的教训。
- 什么是 PRG 的前向安全？
👀 答案
- 因为统计测试是有限的一组检查（分布对不对），而密码学要求的是没有任何高效算法能占到便宜。LFSR 输出能通过全套统计测试，但看到前 2L 位就能预测后面所有位。
- 对任意多项式时间判别器 D，D 区分 G 的输出和真随机串的优势可忽略。人话：把 G 拉出来的串和真随机串放你面前，你分不出哪个是哪个。
- 因为列举测试只能覆盖你想到的攻击；"对任意判别器"覆盖所有可能的攻击，并且让"安全"成为一个可证伪的命题——有人拿出一个具体的高效 D，方案就死了。
- 不可区分 ⟺ next-bit 不可预测。有用是因为不可区分难验证（要对抗所有判别器），不可预测好验证——证简单的那个，白得难的那个。
- 构造一串中间分布 H₀（全真随机）到 H_ℓ（全来自 G），相邻两个只差一位。若能以优势 ε 区分两端，则必有某相邻对能以 ε/ℓ 区分，而它可以直接改造成第 i 位的预测器。
random是 Mersenne Twister，为模拟和游戏设计，看到 624 个输出就能完全还原内部状态；secrets走操作系统的 CSPRNG。- Debian OpenSSL：熵源被误删只剩进程 ID，可能的 SSH 密钥只剩 32768 个，两年才发现。教训：随机数是最安静的失效点——坏了不报错，加密照常工作，只是不再安全。
- 攻击者拿到当前内部状态后，无法回推出之前的输出。简单 CTR 结构不满足（往回倒计数器即可），需要状态单向更新或周期性 reseed。
🛑 可以停在这里
⚡ 走神救援
⭐第一课：「统计随机」≠「密码学安全」——LFSR 输出能通过 NIST 全套统计测试，但看到前 2L 位就能预测后面所有位。统计测试是有限的一组检查，密码学要求没有任何高效算法能占便宜。PRG 定义（不可区分性）：对任意多项式时间判别器 D，区分 G(种子) 和真随机串的优势可忽略；人话：两串放你面前你分不出哪个是哪个。三个设计要点："任意判别器"覆盖所有攻击（而非列举测试）、"多项式时间"承认无限算力必破、"negl"要求优势比任何多项式倒数还小。⭐这个定义让"安全"变成可证伪命题——拿出一个具体高效的 D 方案就死。Yao 定理：不可区分 ⟺ next-bit 不可预测——有用是因为不可区分难验证、不可预测好验证，证简单的白得难的；证明用混合论证（把大差距拆成一串小差距，必有一步差距不小）。种子必须来自真物理熵：⚠️ Python 用
secrets/os.urandom绝不用random（Mersenne Twister，624个输出即可还原）；JavaSecureRandom不用Random，JScrypto.getRandomValues不用Math.random。💥 三大事故同一根因：Debian OpenSSL（熵只剩进程ID，SSH密钥只剩32768种，两年才发现）、Android 比特币钱包（k 值重复导致私钥被算出）、嵌入式设备开机熵池为空（全网成千上万台共用同一把 RSA 私钥）→ ⭐随机数是密码系统里最安静的失效点，坏了不报错。工程上 PRG 几乎总是用分组密码在 CTR 模式下跑（CTR_DRBG、ChaCha20）。前向安全：拿到当前状态能否回推之前输出——简单 CTR 不行，需要状态单向更新或 reseed。
下一节 👉 05-流密码与Nonce铁律.md