🏠 总目录📚 本教程 04 · 伪随机 ← →
📑 本页目录（点开跳转）

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（随机种子）真随机比特观察者看输出，再猜来源
方框表示不同角色或分支，箭头表示信息去向；图下保留各项的详细说明。

图下说明

💡 这个定义为什么这么设计

设计选择 为什么
"对任意判别器 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$ 位是真随机。

若 D 能以优势 ε 区分 $H_0$ 和 $H_\ell$，则由三角不等式， 必存在某个 i 使 D 能以优势 ≥ ε/ℓ 区分相邻的 $H_{i-1}$ 和 $H_i$。

而这两个分布只在第 i 位上不同（一个来自 G，一个真随机）—— 所以这个 D 可以直接改造成一个第 i 位的预测器。∎

💡 "混合论证"是密码学证明里最常用的工具： 把一个大差距拆成一串小差距，说明至少有一步的差距不小。

🌱 四、种子从哪来：熵源

关键信息

该用什么，不该用什么：

# ❌ 绝对不要：这是给模拟和游戏用的，可预测
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()

💥 真实事故 —— 三个都是同一个错误：

🔑 共同的教训：随机数是密码系统里最安静的失效点。 它坏掉的时候什么都不会报错 —— 加密照常工作，只是不再安全。

🏗️ 五、实践中的 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 状态当资产存下来，在这里存下来就等于泄露密钥（本章的前向安全） ⭐

✅ 检查点

  1. 为什么"通过了 NIST 随机性测试"不代表密码学安全？
  2. PRG 的安全定义是什么？用人话说一遍。
  3. 这个定义为什么要说"对任意判别器"而不是列举几种测试？
  4. Yao 定理说了什么？它为什么有用？
  5. 混合论证的基本思路是什么？
  6. random.randbytes 和 secrets.token_bytes 的区别？为什么前者致命？
  7. 举一个随机数失效导致的真实事故，说明它的教训。
  8. 什么是 PRG 的前向安全？
👀 答案
  1. 因为统计测试是有限的一组检查（分布对不对），而密码学要求的是没有任何高效算法能占到便宜。LFSR 输出能通过全套统计测试，但看到前 2L 位就能预测后面所有位。
  2. 对任意多项式时间判别器 D，D 区分 G 的输出和真随机串的优势可忽略。人话：把 G 拉出来的串和真随机串放你面前，你分不出哪个是哪个。
  3. 因为列举测试只能覆盖你想到的攻击；"对任意判别器"覆盖所有可能的攻击，并且让"安全"成为一个可证伪的命题——有人拿出一个具体的高效 D，方案就死了。
  4. 不可区分 ⟺ next-bit 不可预测。有用是因为不可区分难验证（要对抗所有判别器），不可预测好验证——证简单的那个，白得难的那个。
  5. 构造一串中间分布 H₀（全真随机）到 H_ℓ（全来自 G），相邻两个只差一位。若能以优势 ε 区分两端，则必有某相邻对能以 ε/ℓ 区分，而它可以直接改造成第 i 位的预测器。
  6. random 是 Mersenne Twister，为模拟和游戏设计，看到 624 个输出就能完全还原内部状态；secrets 走操作系统的 CSPRNG。
  7. Debian OpenSSL：熵源被误删只剩进程 ID，可能的 SSH 密钥只剩 32768 个，两年才发现。教训：随机数是最安静的失效点——坏了不报错，加密照常工作，只是不再安全。
  8. 攻击者拿到当前内部状态后，无法回推出之前的输出。简单 CTR 结构不满足（往回倒计数器即可），需要状态单向更新或周期性 reseed。

🛑 可以停在这里

⚡ 走神救援

先记住这几件事

下一节 👉 05-流密码与Nonce铁律.md

打卡记录保存在你的浏览器里，首页能看到总进度