生日悖论与哈希安全性
一、生日悖论的基本结论
- 经典结论：在一个 23 人的班级里，至少有两人同一天生日的概率大于 50%。
- 悖论之处：365 天对应 365 种生日，看起来 23 人远小于 365，人们直觉上认为概率应该很小。但事实上，概率已经超过一半。
二、为什么会这样？直观理解
-
错误直觉 你可能会认为这是在问“某个人和我同生日”的概率，那大约是 1/365，非常低。
-
正确理解 实际上我们关心的是“任意两人”生日是否相同。
-
23 人之间可以形成的配对数是
$$ C(23,2) = \frac{23 \times 22}{2} = 253 $$
-
每一对就是一个潜在的碰撞机会。配对数量随着人数平方级增长，远比直觉的线性增长快得多。
-
配对效应 随着人数增加，可能的配对数迅速上升：
| 人数 | 配对数 | 至少两人同生日的概率 |
|---|---|---|
| 10 | 45 | 12% |
| 23 | 253 | 50.7% |
| 30 | 435 | 70.6% |
| 50 | 1225 | 97% |
| 60 | 1770 | 99.4% |
三、数学推导
为了算“至少两人相同”的概率，更容易的方法是算反面事件——“所有人生日都不同”的概率：
\[
P(\text{全不同}) = \frac{365}{365} \times \frac{364}{365} \times \frac{363}{365} \times \dots \times \frac{343}{365}
\]
23 个人时：
\[
P(\text{全不同}) \approx 0.4927
\]
所以：
\[
P(\text{至少一对相同}) = 1 - 0.4927 \approx 0.5073 \quad (50.7\%)
\]
四、推广到一般情况：为什么是约 √N
设有一个随机函数，它的输出空间大小为 \(N\)（比如一年 365 天，或者哈希函数输出空间 \(2^n\)）。
- 取 \(k\) 个输入值，配对数大约为 \(k^2/2\)。
- 每对发生碰撞的概率是 \(1/N\)。
- 所有配对无碰撞的概率近似为：
$$ P(\text{无碰撞}) \approx \left(1 - \frac{1}{N}\right)^{k^2/2} \approx e^{-k^2/(2N)} $$
要使碰撞概率达到 50%，即 \(P(\text{无碰撞}) \approx 0.5\)，解得：
\[
k \approx \sqrt{2N \ln 2} \approx 1.177 \sqrt{N}
\]
结论：碰撞出现的“临界样本量”与 \(\sqrt{N}\) 成正比。
五、哈希函数中的应用：生日攻击
-
哈希函数的性质
-
固定长度输出（如 128 位、256 位）。
-
重要的安全性指标之一是“抗碰撞性”：难以找到两个不同输入，输出却相同。
-
两种攻击方式
-
原像攻击：给定一个哈希值，找到一个输入使其对应。需要大约 \(2^n\) 次尝试。
-
生日攻击：寻找任意一对输入碰撞。只需要大约 \(\sqrt{2^n} = 2^{n/2}\) 次尝试。
-
具体数字
| 哈希长度 n | 输出空间 \(2^n\) | 原像攻击复杂度 | 生日攻击复杂度 |
|---|---|---|---|
| 64 位 | \(2^{64}\) | \(2^{64}\) | \(2^{32}\)（约 43 亿） |
| 128 位 | \(2^{128}\) | \(2^{128}\) | \(2^{64}\)（约 1.8×10¹⁹） |
| 256 位 | \(2^{256}\) | \(2^{256}\) | \(2^{128}\)（约 3.4×10³⁸） |
解读：
- MD5（128 位）理论复杂度是 \(2^{128}\)，但生日攻击只需 \(2^{64}\)，已被攻破。
-
SHA-256（256 位）即使遭遇生日攻击也需要 \(2^{128}\)，仍然安全。
-
设计启示
-
哈希函数的抗碰撞强度 ≈ 输出长度的一半。
- 想要 128 位安全强度，必须至少使用 256 位哈希。
六、总结
- 生日悖论揭示了：在大样本空间中，重复出现的概率远比直觉要高。
- 关键原因是：样本量 \(k\) 与潜在配对数 \(k^2/2\) 的平方关系。
- 在密码学中，这直接影响哈希函数的设计。一个 \(n\) 位哈希，其抗碰撞强度只有 \(n/2\) 位。
- 这也是为什么 MD5、SHA-1 等已过时，而 SHA-256、SHA-3 等才符合现代安全标准。