03 · 一次一密与完美保密

对任意 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) 对都恰好对应唯一一个等概率的密钥。

若一个方案满足完美保密，则密钥空间必须 ≥ 明文空间（即 $|\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$，就违反了完美保密。∎

1. C = M ⊕ K，M = C ⊕ K。因为 (M⊕K)⊕K = M⊕(K⊕K) = M⊕0 = M——任何数异或自己等于 0。
2. Pr[M=m | C=c] = Pr[M=m]。人话：看到密文之后你对明文的了解，和看到之前一模一样，密文没提供任何信息。
3. 因为信息根本不在密文里——每个 (m,c) 对都恰好对应唯一一个等概率的密钥，所有明文的可能性完全相等。不是"算不出来"，是"不存在"。攻击者有量子计算机也没用。
4. 密钥空间 ≥ 明文空间，即密钥至少和消息一样长。困境：要安全传 1GB 数据得先安全传 1GB 密钥——但如果你已经有能安全传 1GB 的信道，为什么不直接传数据？
5. C₁⊕C₂ = M₁⊕M₂（密钥被消掉了）。攻击者用 crib dragging：猜一段常见文字在异或结果上滑动，猜对时会冒出另一条消息的真实文字，再拿它当新 crib 继续滑，两条消息互相解开对方。
6. 不提供。攻击者仍能翻转任意 bit（C'=C⊕Δ → 解密得 M⊕Δ）。"完美保密"只覆盖机密性这一个目标。
7. 放弃对抗无限算力（信息论安全），换来只需短密钥——用 PRG 把 128 bit 种子拉长成任意长的伪随机流。代价是引入了计算假设。