生日悖论与哈希碰撞：为什么 SHA-256 只有 128 位抗碰撞强度

全文分三层：

1. 通俗理解：生日悖论，哈希函数要满足的三个性质
2. 实际用处：区块链、Git、证书，以及 MD5、SHA-1 被攻破的事件
3. 数学原理：$\sqrt{N}$ 的推导、Pollard rho 式的无存储碰撞搜索，附一次真实的截断碰撞实验

第一层：通俗理解

1.1 生日悖论

一年 365 天。问：一个房间里至少多少人，才能让"有两人同一天生日"的概率超过 50%？

直觉往往回答 183（365 的一半）。正确答案是 23。

关键在于，我们问的不是"有人和我同一天生日"，而是"任意两人同一天"。23 个人可以组成 $\binom{23}{2} = 253$ 对，每一对撞上的概率是 $1/365$，253 对加起来，机会就相当可观了。

1.2 哈希函数是什么

哈希函数把任意长的数据压缩成固定长度的"指纹"，比如 SHA-256 输出 256 位。好的哈希函数要满足：

第三条和生日悖论完全对应：碰撞攻击者可以自由选择两个输入，就像在房间里找"任意两人"同生日，所以只需要 $\sqrt{2^n}$ 次。

1.3 碰撞为什么危险

如果能找到两份文件 A、B 哈希相同：让别人对无害的 A 签名（签名实际签的是哈希值），这个签名就同样适用于有害的 B。

第二层：实际用处

哈希函数无处不在

• 区块链：比特币用 SHA-256 做工作量证明和区块链接；以太坊地址是公钥 Keccak-256 哈希的后 20 字节。
• Merkle 树：把成千上万笔交易哈希成一个根，可以用 $\log n$ 个哈希证明某笔交易在区块里。
• Git：每个提交、文件都用哈希命名（历史上是 SHA-1，正在迁移到 SHA-256）。
• 数字签名、证书、密码存储、文件完整性校验。

碰撞攻击的历史

SHAttered 大约用了 $2^{63}$ 次 SHA-1 计算，远少于生日攻击的 $2^{80}$。这说明它利用的是 SHA-1 的结构弱点，而不只是生日悖论。

设计结论：要 128 位安全，抗碰撞场景就要 256 位输出。这就是 SHA-256 成为默认选择的原因。

第三层：数学原理

3.1 生日界的推导

从 $N$ 个可能值中独立均匀地取 $k$ 个，全部不相同的概率是

$$P_{\text{无碰撞}} = \prod_{i=0}^{k-1}\Big(1 - \frac{i}{N}\Big).$$

用 $1 - x \le e^{-x}$（$x$ 小时近似相等）：

$$P_{\text{无碰撞}} \approx \exp\Big(-\sum_{i=0}^{k-1}\frac{i}{N}\Big) = \exp\Big(-\frac{k(k-1)}{2N}\Big) \approx e^{-k^2/(2N)}.$$

令碰撞概率为 $1/2$，解得

$$k \approx \sqrt{2N \ln 2} \approx 1.18\sqrt{N}.$$

代入 $N = 365$，$k \approx 22.5$，和 23 吻合。代入 $N = 2^{256}$，$k \approx 2^{128}$。

3.2 手算例子：真实找一次碰撞

3.3 不需要大内存的碰撞搜索

上面的方法要把所有见过的哈希存下来，$2^{64}$ 规模时内存吃不消。Floyd 判圈的思路可以解决：

把哈希函数 $H$ 看成有限集合上的映射，从 $x_0$ 出发反复迭代 $x_{i+1} = H(x_i)$。因为集合有限，序列迟早进入循环，形状像希腊字母 $\rho$。进入循环的那一刻，两个不同的点映射到了同一个点，这就是一次碰撞。

用"龟兔赛跑"（一个每次走一步，一个每次走两步）就能在 $O(\sqrt{N})$ 时间、$O(1)$ 内存内找到它。这和Diffie–Hellman与离散对数里解离散对数的 Pollard rho 是同一个思想。van Oorschot–Wiener 的并行版本还能让成千上万台机器同时搜索。

3.4 为什么生日界不能被"设计"掉

生日攻击是通用的：它不看哈希函数的内部结构，对任何 $n$ 位输出的函数都有效。所以抗碰撞强度的上限永远是 $n/2$ 位。密码学家能做的只有一件事：把输出加长。

总结