第 5 章 · XOR 与一次一密

古典密码在字母层面折腾了两千年,全被统计学击垮。现代密码换了个战场:比特。而比特世界里最基础、最优雅的加密操作,就是一个你写 Android 代码时早就用过的运算符——异或(XOR)。

一、XOR:自己就是自己的逆

异或(^)的规则一句话:两个比特相同得 0,不同得 1。

a	b	a ⊕ b
0	0	0
0	1	1
1	0	1
1	1	0

它有一个让密码学家一见倾心的性质:用同一个值 XOR 两次,会回到原点。

P ⊕ K ⊕ K = P

这意味着加密和解密是同一个操作:明文 XOR 密钥 = 密文;密文 XOR 密钥 = 明文。不需要设计单独的解密逻辑,一个 ^ 走天下。所有现代对称密码(包括 AES、ChaCha20)在最底层都用 XOR 把密钥"混"进数据。

DEMO XOR 位级可视化

明文(一个字符)

密钥字节(一个字符)

看最下面一行:把密文再和同一密钥 XOR 一次,就精确还原了明文。加密即解密。

二、一次一密:完美,但有代价

现在把 XOR 用到极致。一次一密(One-Time Pad, OTP)的规则:

密钥是一串真随机比特,和明文一样长;
密钥只用一次,用完即弃;
加密就是明文逐位 XOR 密钥。

1949 年,信息论之父克劳德·香农证明了 OTP 具有完美保密性(perfect secrecy):密文不泄露关于明文的任何信息。直觉是这样的——给定任意一段密文,对于每一种可能的明文,都存在恰好一个密钥能把它加密成这段密文,而这些密钥全都等概率。

完美保密的含义

攻击者哪怕拥有无限的计算能力,面对一段 OTP 密文,也只能得出"明文可能是任何等长字符串"——密文把 ATTACK 和 RETREAT 加密成完全无法区分的东西。这是密码学能给出的最强承诺,强到"量子计算机也无能为力"。它不依赖任何"计算困难"的假设,是信息论安全,而非我们后面所有算法依赖的计算安全。

既然如此完美,为什么你的手机不用 OTP?因为那三条规则每一条都是工程噩梦:

密钥和明文一样长。要加密 1 GB 视频,就得先安全地分发 1 GB 密钥——可你要是有安全信道传 1 GB 密钥,干嘛不直接用它传视频?"先有鸡还是先有蛋"。
密钥必须真随机。用伪随机数(PRNG)生成就不再是 OTP,完美保密立刻失效(它退化成了流密码,见第 6 章)。
绝不能重用。下面就让你亲眼看看,重用一次会有多惨。

OTP 真的被用过

冷战时期的间谍确实携带印着随机数字的"一次性密码本"(小册子,用完撕掉烧毁)。莫斯科与华盛顿之间的热线也用过 OTP。它在"不惜代价保护极少量极高价值信息"的场景里是真实存在的——只是这个场景和"给十亿台手机加密聊天记录"相去甚远。

三、两次一密:密钥重用的自爆现场

OTP 的 "One-Time" 三个字是用血写的。假设 Alice 偷懒,用同一把密钥 K 加密了两条消息:

C₁ = P₁ ⊕ K
C₂ = P₂ ⊕ K

攻击者 Eve 把两段密文 XOR 到一起,密钥 K 直接消失了:

C₁ ⊕ C₂ = (P₁ ⊕ K) ⊕ (P₂ ⊕ K) = P₁ ⊕ P₂

现在 Eve 手里有 P₁ ⊕ P₂——两段明文的异或,密钥彻底出局。这看起来还是乱码,但英文有大量冗余(还记得第 3 章吗?),Eve 可以玩一个叫 crib-dragging(拖字)的游戏:猜 P₁ 里某处可能有个常见词(比如 " the "),把它和 P₁⊕P₂ 的对应位置 XOR——如果猜对了,吐出来的就是 P₂ 在那一段的明文!读出来通顺,就说明两处都猜中了,顺藤摸瓜就能还原整句。

下面的 Demo 让你当一回 Eve。两条消息用了同一把密钥(你看不到密钥)。在下方输入你对某条消息某处的猜测,拖动位置,看另一条消息的明文从乱码里浮现出来。

DEMO 两次一密破解台(crib-dragging)

你猜某条明文里有这个词

把它对齐到位置 = 0

C₁⊕C₂ ⊕ 你的猜测 → 若猜对,这里会浮现另一条消息的明文片段

试着把 crib 设成 " the "、" and "、" you " 等常见词,拖动位置。当浮现出通顺的字母时,你就同时破解了两条消息在这一段的内容——而你从未接触过密钥。

这不是历史课,这是 CVE

密钥/nonce 重用是流密码和 OTP 类方案最常见的真实漏洞之一。经典案例:微软 PPTP、802.11 的 WEP、以及无数把 AES-CTR/GCM 的 nonce 写死或用计数器却在重启后归零的 App。只要同一个密钥流被用来 XOR 两段不同数据,上面这套攻击就成立。第 9 章我们会看到,AES-GCM 的 nonce 重用甚至比这更致命——它不仅泄露明文,还会泄露认证密钥。

四、通往实用加密的桥

OTP 给了我们一个完美的理想,却因为"密钥要和明文一样长"而无法落地。工程师的妥协非常直接:

如果我能用一把短密钥,生成一长串"看起来足够随机"的比特流,再拿它去 XOR 明文,不就好了?

这串由短密钥"拉长"出来的伪随机比特,就叫密钥流(keystream);生成它的算法就是流密码。我们用"计算上无法与随机区分"换掉了 OTP 的"信息论上完美",换来了可用性。代价是:一旦生成器可预测、或密钥流被重用,前面那套攻击立刻回归。下一章,我们就来拆流密码。

本章要点

XOR 自逆:P ⊕ K ⊕ K = P,所以加密与解密是同一操作,是一切对称密码的底层零件。
一次一密 = 真随机、等长、一次性密钥的 XOR,被证明具有完美(信息论)保密性。
它不实用:密钥分发困难、必须真随机、绝不能重用。
密钥重用即自爆:C₁⊕C₂ = P₁⊕P₂,借助语言冗余用 crib-dragging 即可还原双方明文。