📑 本页目录（点开跳转）
03 · 一次一密与完美保密
⏱ 22 分钟 ｜ ⭐⭐ 唯一数学上完美的加密
🎯 一句话
有一种加密方案，即使攻击者有无限算力也永远破不了 —— 这是可以严格证明的。 它简单到用一行就能写完。而它几乎没人用。 这两件事都很重要。
🔐 一、方案本身：异或
密钥 K：和消息【一样长】的随机比特串
加密： C = M ⊕ K
解密： M = C ⊕ K
（⊕ 是异或：相同为 0，不同为 1）
为什么解密能work：
C ⊕ K = (M ⊕ K) ⊕ K = M ⊕ (K ⊕ K) = M ⊕ 0 = M ✅
↑ 任何数异或自己 = 0
例：
M = 1 0 1 1 0 0 1 0
K = 0 1 1 0 1 0 1 1
─────────────── ⊕
C = 1 1 0 1 1 0 0 1
解密：C ⊕ K
C = 1 1 0 1 1 0 0 1
K = 0 1 1 0 1 0 1 1
─────────────── ⊕
1 0 1 1 0 0 1 0 = M ✅
🏆 二、完美保密：它到底"完美"在哪
定义（Shannon）：对任意明文 m 和任意密文 c， $$\Pr[M = m \mid C = c] = \Pr[M = m]$$
💡 人话翻译：
看到密文之后，你对明文的了解，和看到之前【一模一样】。 密文没有提供任何信息。
💡 一个能立刻感受到的例子
假设消息是 2 bit，攻击者截获了密文 C = 11
他能推出什么？
├─ 如果 M = 00，那 K 必须是 11 ← 可能，K 是随机的
├─ 如果 M = 01，那 K 必须是 10 ← 也可能
├─ 如果 M = 10，那 K 必须是 01 ← 也可能
└─ 如果 M = 11，那 K 必须是 00 ← 也可能
⭐ 每一种明文都【恰好对应一个】同样可能的密钥
→ 四种明文的可能性完全相等
→ 密文什么也没告诉他
📐 严格证明（三行，想看再点）
对任意 m、c，满足 $C = M \oplus K$ 的密钥唯一：$k = m \oplus c$。
由于 K 均匀随机且独立于 M：
$$\Pr[C = c \mid M = m] = \Pr[K = m\oplus c] = 2^{-n}$$
这个值与 m 无关。代入贝叶斯公式：
$$\Pr[M=m\mid C=c] = \frac{\Pr[C=c\mid M=m]\Pr[M=m]}{\Pr[C=c]} = \frac{2^{-n}\Pr[M=m]}{2^{-n}} = \Pr[M=m]$$
∎
💡 证明的核心就一句：每个 (m, c) 对都恰好对应唯一一个等概率的密钥。
🔑 注意这个保证有多强：它不依赖任何计算假设。 攻击者有量子计算机、有一万年时间，都没有用 —— 信息根本不在密文里，不是"算不出来"，是"不存在"。
💀 三、三个致命的限制
① 密钥必须和消息一样长
📐 Shannon 定理：这是数学上的下界（想看再点）
若一个方案满足完美保密，则密钥空间必须 ≥ 明文空间（即 $|\mathcal{K}| \ge |\mathcal{M}|$）。
反证：设 $|\mathcal{K}| < |\mathcal{M}|$。固定一个密文 c， 考虑集合 $S = \{ \text{Dec}_k(c) : k \in \mathcal{K} \}$，则 $|S| \le |\mathcal{K}| < |\mathcal{M}|$。
于是存在明文 $m^* \notin S$，即 $\Pr[M = m^* \mid C = c] = 0$。 但只要 $\Pr[M = m^*] > 0$，就违反了完美保密。∎
💡 后果：要安全传 1GB 的数据，先得安全传 1GB 的密钥
→ 但如果你已经有了一条能安全传 1GB 的信道，
你干嘛不直接用它传数据？ ⭐
这就是 OTP 的根本困境。
② 密钥只能用一次 ⭐⭐
这是本章最重要的一条，也是整个密码学里最常被违反的规则。
如果用同一个 K 加密两条消息：
C₁ = M₁ ⊕ K
C₂ = M₂ ⊕ K
───────────────
C₁ ⊕ C₂ = M₁ ⊕ M₂ ⊕ K ⊕ K = M₁ ⊕ M₂ ⭐ 密钥被消掉了！
→ 攻击者【不需要密钥】就拿到了两条明文的异或
拿到 M₁ ⊕ M₂ 能干什么 —— crib dragging：
自然语言有巨大冗余。攻击者猜一段常见文字（crib），
比如 " the "，把它在 M₁⊕M₂ 上逐位置滑动：
在每个位置 i 计算： (M₁⊕M₂)[i:] ⊕ " the "
├─ 如果猜错 → 得到一串乱码
└─ 如果猜对 → 得到【另一条消息在那个位置的真实文字】⭐
比如冒出 "ing t"
→ 然后用新得到的片段当作新的 crib，继续滑
→ 像填字游戏一样，两条消息【互相解开对方】
💥 真实事故： - 苏联 VENONA 计划（1940s）：苏联情报机构复用了一次性密码本， 美国因此破译了数千份电报，暴露了大批间谍。 - 微软 PPTP（MS-CHAPv2）、WEP 无线加密：都因 IV/密钥流重用被打穿。 - 2017 年多个"加密聊天 App"：用固定 nonce，等于密钥复用。
③ 不提供完整性
OTP 完美保护【机密性】
但攻击者仍然可以翻转任意 bit（第 1 章讲过）
C' = C ⊕ Δ → 解密得到 M ⊕ Δ
⭐ "完美保密"只是四个目标里的一个
🔑 一个重要的认知：「完美保密」不等于「完美安全」。 Shannon 的定理只覆盖机密性。
🌉 四、这个困境怎么破 → 整个现代密码学
OTP 的问题：密钥必须和消息一样长
💡 关键的一步妥协：
如果我们放弃"对抗无限算力"，
只要求"对抗【多项式时间】的攻击者"呢？
→ 那就可以用一个【短的种子】，
通过某个算法【拉长】成一串"看起来随机"的比特流
→ 用它代替真正的随机密钥
真 OTP： K（1GB 真随机） ⊕ M
现代方案： G(seed)（种子 128 bit → 拉成 1GB） ⊕ M
↑ 这个 G 就是【伪随机数生成器 PRG】
| 一次一密 | 现代对称加密 | |
|---|---|---|
| 安全强度 | 信息论安全（无限算力也没用） | 计算安全（多项式时间攻击者破不了） |
| 密钥长度 | = 消息长度 | 128/256 bit，固定 |
| 依赖假设 | 无 | 存在安全的 PRG / 分组密码 |
| 实用性 | ❌ 几乎不可用 | ✅ 到处都是 |
🔑 这个妥协是整个现代密码学的起点。 从"绝对安全但不可用"，换到"在合理假设下安全且好用"。 🔗 第 4 章就讲这个 G 该满足什么条件。
💡 那 OTP 今天还有用吗
有，但场景极窄：
| 场景 | 为什么 |
|---|---|
| 外交/军事的红色电话 | 可以用外交邮袋提前运送密钥本，消息量小 |
| 量子密钥分发（QKD）的下游 | QKD 负责分发密钥，OTP 负责加密 |
| 需要长期保密的极敏感数据 | 抗"先收集，等以后再解密"（第 23 章）⭐ |
🔗 和站内其他章的关系
| 相关的地方 | 和这一章的关系 |
|---|---|
| 第 1 章：加密不提供完整性 | OTP 也不例外，"完美保密"≠"完美安全" |
| 第 2 章：维吉尼亚被 Kasiski 破 | 那是"密钥太短且重复"的极端版；OTP 是它的极限 |
| 后面的流密码 | 就是"用 PRG 模拟 OTP" |
| 后面的 nonce 铁律 | 本质就是"别把 OTP 的密钥用两次" ⭐ |
| 机器学习基础 · 决策树与集成学习 | 那里的信息熵 / 信息增益就是完美保密用的同一把尺子：完美保密 = 密文对明文的信息增益恰好为 0 ⭐ |
| 数学原理 · 没有免费的午餐 | 同一种"必须先付代价"的定理形状：那边想要泛化就得先交出归纳偏置，这边想要完美保密就得先交出和消息一样长的密钥 |
✅ 检查点
- OTP 的加解密公式是什么？为什么解密能work？
- 完美保密的定义是什么？用人话说一遍。
- 为什么说这个保证"不依赖任何计算假设"？
- Shannon 定理说密钥至少要多长？这导致了什么根本困境？
- 密钥复用会泄露什么？攻击者拿到它之后怎么做？
- OTP 提供完整性吗？"完美保密"和"完美安全"的区别？
- 现代密码学是通过放弃什么、换来了什么？
👀 答案
- C = M ⊕ K，M = C ⊕ K。因为 (M⊕K)⊕K = M⊕(K⊕K) = M⊕0 = M——任何数异或自己等于 0。
- Pr[M=m | C=c] = Pr[M=m]。人话：看到密文之后你对明文的了解，和看到之前一模一样，密文没提供任何信息。
- 因为信息根本不在密文里——每个 (m,c) 对都恰好对应唯一一个等概率的密钥，所有明文的可能性完全相等。不是"算不出来"，是"不存在"。攻击者有量子计算机也没用。
- 密钥空间 ≥ 明文空间，即密钥至少和消息一样长。困境：要安全传 1GB 数据得先安全传 1GB 密钥——但如果你已经有能安全传 1GB 的信道，为什么不直接传数据？
- C₁⊕C₂ = M₁⊕M₂（密钥被消掉了）。攻击者用 crib dragging：猜一段常见文字在异或结果上滑动，猜对时会冒出另一条消息的真实文字，再拿它当新 crib 继续滑，两条消息互相解开对方。
- 不提供。攻击者仍能翻转任意 bit（C'=C⊕Δ → 解密得 M⊕Δ）。"完美保密"只覆盖机密性这一个目标。
- 放弃对抗无限算力（信息论安全），换来只需短密钥——用 PRG 把 128 bit 种子拉长成任意长的伪随机流。代价是引入了计算假设。
🛑 可以停在这里
⚡ 走神救援
OTP：C = M ⊕ K，K 是和消息等长的真随机串。⭐完美保密（Shannon）：Pr[M=m|C=c]=Pr[M=m]——看到密文后对明文的了解和看之前一模一样，证明核心是每个(m,c)对恰好对应唯一一个等概率密钥。这个保证不依赖任何计算假设：信息根本不在密文里，量子计算机也没用。三个致命限制：①密钥必须和消息等长（Shannon 定理是数学下界）→ 根本困境：要安全传1GB得先安全传1GB密钥，那为什么不直接传数据 ②⭐⭐密钥只能用一次——复用则 C₁⊕C₂ = M₁⊕M₂，密钥被消掉，攻击者用 crib dragging（猜常见词滑动，猜对就冒出另一条消息的真实文字，再当新crib继续）让两条消息互相解开对方；💥真实事故：苏联 VENONA（复用密码本，美国破译数千电报）、WEP、MS-CHAPv2 ③不提供完整性（仍可比特翻转）→ ⭐"完美保密"≠"完美安全"。破局 = 整个现代密码学的起点：放弃对抗无限算力，只要求对抗多项式时间攻击者 → 用 PRG 把短种子拉长成伪随机流代替真随机密钥 → 信息论安全换成计算安全，密钥从 1GB 降到 128 bit。OTP 今天仅用于：外交专线、QKD 下游、需要抗"先收集后解密"的极敏感数据。
下一节 👉 04-伪随机.md