生日悖论与哈希安全性

一、生日悖论的基本结论

错误直觉 你可能会认为这是在问“某个人和我同生日”的概率，那大约是 1/365，非常低。
正确理解 实际上我们关心的是“任意两人”生日是否相同。
- 23 人之间可以形成的配对数是
  \[C(23,2) = \frac{23 \times 22}{2} = 253\]
- 每一对就是一个潜在的碰撞机会。配对数量随着人数平方级增长，远比直觉的线性增长快得多。
配对效应 随着人数增加，可能的配对数迅速上升：

为了算“至少两人相同”的概率，更容易的方法是算反面事件——“所有人生日都不同”的概率：

\[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$（比如一年 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³⁸）

解读：