一次一密与香农：唯一被证明"绝对安全"的密码

全文分三层：

1. 通俗理解：为什么"什么都可能"等于"什么都不知道"
2. 实际用处：华盛顿–莫斯科热线、Venona 计划，以及现代加密为什么不用它
3. 数学原理：完美保密的定义与证明、密钥长度下界、两次一密的崩溃，附手算例子

第一层：通俗理解

1.1 加法加密

把字母换成数字（A=0, B=1, …, Z=25），明文每个字母加上对应位置的密钥字母，模 26：

解密就是减回去。电脑上通常用二进制，"加"就是异或（XOR）。

1.2 为什么破解不了

拿到密文 EQNVZ 的人，可以尝试任何一个 5 字母的密钥：

• 密钥 XMCKL → 明文 HELLO
• 密钥 TQURI → 明文 LATER
• 密钥 RCRVB → 明文 NOWAY

每个 5 字母的单词都对应恰好一个密钥。密钥是完全随机选的，所以每种明文都同样可能。攻击者算力再强也没用：问题不是"算不出来"，而是"答案根本不确定"。

1.3 三个条件缺一不可

1. 真随机：不能是伪随机数，否则攻击者可以去破解生成器；
2. 和消息一样长：密钥不能循环使用；
3. 只用一次：用两次就会崩溃（见 2.2 和 3.4 节）。

第二层：实际用处

2.1 真实使用

• 1917 年：AT&T 的 Vernam 发明了电传打字机上的异或加密；随后 Mauborgne 提出密钥必须随机且只用一次。
• 冷战热线：1963 年古巴导弹危机后建立的华盛顿–莫斯科热线，早期就用一次一密的纸带加密。
• 间谍密码本：特工随身携带印满随机数字的小本子，用一页撕一页（"one-time pad"这个名字就是这么来的）。

2.2 Venona 计划：用了两次就完了

二战期间，苏联因为战时生产压力，重复印制了一部分密码本页。美国陆军的 Venona 计划（1943–1980）利用这些重复使用的密钥，破译了数千条苏联情报电报，揭露了曼哈顿计划中的间谍（如 Klaus Fuchs、Rosenberg 夫妇）。

2.3 为什么现代加密不用它

所以现实中用流密码（ChaCha20、AES-CTR）：用一把短密钥生成"看起来随机"的长密钥流，再异或。安全性从"信息论安全"降为"计算安全"，换来了实用性。参见《LFSR与流密码》。

第三层：数学原理

3.1 完美保密的定义

香农的定义：对任意明文分布、任意明文 $m$ 和密文 $c$，

$$\Pr[M = m \mid C = c] = \Pr[M = m].$$

看到密文前后，你对明文的判断完全没变。等价地，密文的分布与明文无关。

3.2 证明：群里的平移

设消息、密钥、密文都在一个有限群 $(G, +)$ 里（比如 $\mathbb{Z}_{26}^n$ 或 $\mathbb{F}_2^n$），密钥 $K$ 在 $G$ 上均匀随机，与 $M$ 独立，$C = M + K$。

对任意 $m, c \in G$，恰好有一个密钥 $k = c - m$ 使 $m + k = c$。因此

$$\Pr[C = c \mid M = m] = \Pr[K = c - m] = \frac{1}{|G|},$$

与 $m$ 无关。由贝叶斯公式即得完美保密。

用抽象代数的话说：对每个固定的 $m$，平移 $k \mapsto m + k$ 是 $G$ 到自身的双射，均匀分布在双射下仍是均匀分布。

这个证明对任何有限群都成立，Shamir秘密分享的"$k-1$ 份毫无信息"本质上是同一个论证。

3.3 密钥至少和消息一样长

香农还证明：完美保密要求密钥空间 $|\mathcal{K}| \ge |\mathcal{M}|$。

理由：固定一个可能出现的密文 $c$。如果密钥比明文少，那么用所有密钥去解 $c$，最多得到 $|\mathcal{K}| < |\mathcal{M}|$ 个不同明文，于是某个明文 $m$ 永远不可能对应 $c$，即 $\Pr[M = m \mid C = c] = 0 \neq \Pr[M = m]$。

所以"短密钥 + 完美保密"是不可能的，这是信息论层面的定理，不是工程上还没做到。

3.4 手算例子：两次一密

总结