碰撞的数学：从生日悖论到哈希安全

“碰撞”的概念在概率论和计算机科学中都处于核心地位。无论是小房间里有两个人的生日相同，还是安全系统中两个不同的输入产生了相同的哈希值，其背后的数学原理都是一样的。理解这些概率往往是违反直觉的，这也就是通常所说的生日悖论。

本文探讨了生日问题的数学基础、由 Richard von Mises 引入的从特定概率到一般概率的转变，以及这些概念如何应用于现代网络安全和哈希表效率。

生日悖论：为什么 23 是神奇数字

乍一看，房间里只需要 23 个人就有 50% 的概率出现两个人的生日相同，这个想法似乎是错误的。直觉往往会产生偏差，因为我们习惯于思考某人与我们特定的生日相同的概率。然而，当我们要寻找的是任何两个人共享任何生日时，悖论就产生了。

为了计算这一点，寻找逆概率会更容易：即该群体中没有人共享生日的概率。对于一个由 $n$ 个人组成的群体：

• 第一个人可以有任何生日 (365/365)。
• 第二个人必须有一个不同的生日 (364/365)。
• 第三人必须与前两人不同 (363/365)。

对于 $n=23$，所有生日都是唯一的概率约为 49.3%，这意味着至少发生一次碰撞的概率为 50.7%。正如一位社区成员所指出的，该悖论中的“惊喜”源于研究对象从你个人转向了群体中的任何两个人。

扩展范围：占用概率

虽然计算配对是直接的，但确定更复杂的碰撞概率——例如在 60 人的群体中出现三人共享生日的概率——则更为困难。20 世纪 30 年代保险数学局的早期尝试通常会导致极低的概率（仅为几千分之一），因为他们关注的是三人共享一个特定、预选日期的概率。

1939 年，数学家 Richard von Mises 将视角转向了“占用概率”。他不再询问某个特定盒子（日期）是否包含三个球（人），而是建议观察所有盒子并计算有多少个盒子包含三个或更多个球。

通过将此视为期望值 $E(x_s)$，数学计算发生了显著变化。对于一个 60 人的群体，三人匹配的期望概率约为 0.22。这意味着在大约每 4-5 个 60 人的群体中，就会发生一次三人生日匹配——这比之前的计算结果显示的要常见得多。

在计算领域的实际应用

这一数学框架不仅是一种好奇心；它是我们在计算机科学中处理数据的基础。

哈希表碰撞

在哈希表中，“日期”变成了表字段，而“人”变成了哈希值。生日问题允许开发者根据所选的表大小和条目数量来近似估算碰撞会发生的情况。这对于维持表性能至关重要，因为过多的碰撞会降低查找速度。

网络安全中的生日攻击

在安全领域，“生日攻击”是一种用于在密码学哈希函数中寻找碰撞的暴力破解方法。攻击者不会等待特定的哈希值出现；他们只需生成随机输入，直到任何两个输入产生相同的输出。

由于生日问题的平方根特性，碰撞可以在大约 $\sqrt{n}$ 次尝试中被找到。例如，对于具有 $2^{256}$ 个可能输出的 SHA-256，攻击者大约需要 $2^{128}$ 次尝试来找到碰撞。虽然这仍然是一个巨大的数字，但它比寻找特定哈希值所需的 $2^{256}$ 次尝试要小得多。

检测 RNG 缺陷

除了安全，这些原理也被用于测试随机数生成器 (RNGs)。一个周期为 $2^{32}$ 且分布完美的 RNG 应该在前 $2^{32}$ 个输出中实现零碰撞。然而，一个真正的随机序列在仅 200,000 次输出后，预计会显示出大约 100 次碰撞。这种差异允许工程师检测 RNG 是否是在返回其状态的 1-to-1 置换，而不是表现得随机。

结论

生日问题告诉我们，碰撞的发生概率远比我们的直觉所暗示的要高。通过从特定目标转向一般占用情况，我们可以更好地预测复杂系统的行为，从房间内的人口统计学到世界上最敏感数据的安全性。