你的生日是什么时候？哈希碰撞背后的数学

# 你的生日是什么时候？——哈希碰撞背后的数学 来源：https://0xkrt26.github.io/math_behind_security/2026/05/08/birthday-problem.html 备注：这篇帖子和之前的有些不同。它更像是一篇散文而不是对话。我尝试了多次重构，但它始终想要保持线性的叙述方式。有时候话题自有其形态，我就随它去了。请享用！ 你和周围的人同一天生日的概率是多少？如果你独自一人在房间里，那概率肯定是零。周围的人越多，概率应该越高。但我告诉你，在一个只有23人的房间里，已经有50%的概率会有两个人的生日是同一天！而且我可以用小学数学很轻松地证明这一点。 计算至少两个人同一天生日的概率是什么意思？这和计算没有人同一天生日的逆概率是一样的： \[P(\text{至少有一个匹配}) = 1 - P(\text{没有匹配})\] 没有匹配意味着每个生日都是独一无二的。这意味着第一个人可以在365天中的任何一天出生，第二个人必须在不同的一天出生，所以他只有364天可选，第三个人只有363天可选……以此类推。让我们用n表示房间里的人数，推导这个公式： \[P(\text{没有匹配}) = \frac{365}{365} \cdot \frac{364}{365} \cdot \frac{363}{365} \dots \frac{365-n+1}{365} = \frac{365!}{365^n(365-n)!}\] 当n=23时： \[P(\text{没有匹配}) = \frac{365!}{365^{23}(365-23)!}= 0.4927\] ……大约50%。 在网上搜索生日悖论后，你可以经常找到另一个公式，它基于计算23人之间所有可能的连接来近似： \[1 - \frac{1}{365} = \frac{364}{365}\] \[\left( \frac{364}{365} \right)^{\binom{23}{2}} \approx 0.4995\] 但让我们来看一些更酷的东西。 你看，这些公式的问题是它们只能用来找出一对同一天生日的人。但是60个人中有三个人同一天生日的概率有多低呢？ 1930年代，一家保险公司的数学部门的员工们试图找出这个问题的答案，因为他们60个同事中有三个人共享同一个生日。他们的计算大概是这样的： 在有60个人的房间里，Alice、Bob和Ray在同一天生日。他们生日匹配的概率是 \[\frac{1}{365} \cdot \frac{1}{365} \cdot \frac{1}{365} = \left( \frac{1}{365} \right)^3\] 对于剩下的57个同事，概率是： \[\left(\frac{364}{365}\right)^{57}\] 而且，除了Alice、Bob和Ray，也可能是Mikel、Ida和Ana或任何其他三人组： \[\binom{60}{3}\] 现在需要做的只是将所有这些概率相乘： \[\binom{60}{3} \cdot \left(\frac{364}{365}\right)^{57} \cdot \left(\frac{1}{365}\right)^3 \approx 0.0006\] 所以数学部门员工得到的结果只是千分之几。而且他们的计算是对的。但同时……也是错的。 1939年，奥地利数学家理查德·冯·米塞斯（Richard von Mises）解释了其原因。他的文章"Über Aufteilungs- und Besetzungswahrscheinlichkeiten"发表在伊斯坦布尔大学学术期刊上，当时他被归类为犹太人并逃离了纳粹政府，后来成为了数学系教授。 冯·米塞斯不仅仅是改变了计算方法。他完全改变了看待这个问题的视角。问题是，人类的大脑非常自我中心，常常忽略全局。数学部门的员工们试图寻找一个特定事件的概率：三个人的生日在某个预先选定的日期相同。但如果我们问的是：“一般来说，我们预期这类事件多久发生一次呢？” 想象你面前有365个盒子。60个球被随机投入这些盒子中。数学部门员工选择了第三个盒子。对他们来说，成功是那个盒子里有三个或更多的球。冯·米塞斯建议观察所有的盒子，计算最后有多少盒子会有三个或更多的球。显然，他对成功的定义要宽泛得多，因此概率也高得多。 米塞斯称这种概率为占用概率（occupancy probability），因为它显示了有多少个盒子——在我们的例子中是日子——被占用了一次、两次、三次等等。 让我们看看他的计算。在这个例子中，我们有n天和k个人在房间里。 每个n被占用的概率是1/n，所以对于所有k个人，它变成： \[\underbrace{\frac{1}{n} \times \frac{1}{n} \times \dots \times \frac{1}{n}}_{k \text{ 次}} = \frac{1}{n^k} = n^{-k}\] 这就是我们计算一个精确序列发生概率的方式。 然后，我们将构建p1的概率，即所有在第一个日历日上有s个人的生日分布。有\[\binom{k}{s}\]种方式从k个人中选出s个，对于剩下的n-1天，有（k-s）个员工可以这样分配： \[(n-1)^{k-s}\] p1的完整公式是： \[p_1 = \binom{k}{s} \cdot n^{-k} \cdot (n-1)^{k-s}\] 我们也可以将'p1'转化为伯努利试验：$$\begin{aligned} p_1 &= \binom{k}{s} \cdot (n-1)^{k-s} \cdot n^{-k} \\ &= \binom{k}{s} \cdot \frac{(n-1)^{k-s}}{n^k} \\ &= \binom{k}{s} \cdot \frac{(n-1)^{k-s}}{n^s \cdot n^{k-s}} \\ &= \binom{k}{s} \cdot \left(\frac{1}{n}\right)^s \cdot \left(\frac{n-1}{n}\right)^{k-s} \\ &= \binom{k}{s} \cdot \left(\frac{1}{n}\right)^s \cdot \left(1 - \frac{1}{n}\right)^{k-s} \end{aligned}$$ $$p = \frac{1}{n} \quad \text{（成功概率）}$$ $$q = 1 - \frac{1}{n} \quad \text{（失败概率）}$$ 这就变成了我们在高中学到的伯努利序列公式。 同样的公式适用于p2、p3...pn，得到： \[p_1 + p_2 + p_3 + \dots + p_n = n \cdot p_1\] 这个和涵盖了所有至少有一天有s个生日的分布。所有有多于这样一天的情况会被多次计算。例如，如果有两天都有s个生日，分布会被计算两次；三天的话会被计算三次，以此类推。 这就像有很多数组表示每天的生日数量（在这个例子中我们只有四天）：对于s = 7：分布（每天生日数）：$$\begin{aligned} \text{Distribution}_1 &: [8, \mathbf{7}, 4, 6] \\ \text{Distribution}_2 &: [4, 5, 3, 2] \\ \text{Distribution}_3 &: [\mathbf{7}, 4, 5, \mathbf{7}] \end{aligned}$$ 数组（检查恰好有$s$天的日子）：$$\begin{aligned} \text{Array}_1 &: [8, 4, \mathbf{7}] \quad \text{（第1天）} \\ \text{Array}_2 &: [\mathbf{7}, 5, 4] \quad \text{（第2天）} \\ \text{Array}_3 &: [4, 3, 5] \quad \text{（第3天）} \\ \text{Array}_4 &: [6, 2, \mathbf{7}] \quad \text{（第4天）} \end{aligned}$$ Distribution1只出现在Array2中，因此只会被计算一次，而Distribution3同时是Array1和Array4的一部分，因此会被计算两次。 这意味着\[n \cdot p1\]为我们提供了一个加权和，可以解释为期望值'E($x_s$)'。我们只需要代入之前已经推导出的p1公式： \[E(x_s) = n \cdot \binom{k}{s} \cdot (n-1)^{k-s} \cdot n^{-k}\] 或者 \[E(x_s) = n \cdot \binom{k}{s} \cdot \left(\frac{1}{n}\right)^s \cdot \left(1 - \frac{1}{n}\right)^{k-s}\] 为了证明60人的群体中有三人同一天生日的情况要常见得多，让我们用数字来验证这个公式： \[\begin{aligned} n &= 365 \\ k &= 60 \\ s &= 3 \\ E(x_3) &= 365 \times \frac{60!}{3! \times (60-3)!} \times \left(\frac{1}{365}\right)^3 \times \left(1 - \frac{1}{365}\right)^{60-3} \approx 0.2196 \end{aligned}\] 或者大约0.22，这与冯·米塞斯在他的论文中给出的数值一致。 "0.22"可能看起来太小，但实际上这意味着，平均每4-5个60人的群体中，就会出现一个三人共享的生日。 \[\frac{1}{0.22} \approx 4.5454\] 这看起来没那么罕见了吧？特别是当我们把它和千分之几的概率相比，后者大约每1500-2000个60人群体才会发生一次。那才是真的罕见。 当然，这些计算没有考虑出生密度的季节变化、双胞胎、选择偏差、闰年等，米塞斯本人在他的文章末尾也明确提到了这些。如果你看统计数据，在北半球，孩子更多地在夏天出生；在美国，他们更有可能在圣诞节和除夕夜被受孕；由于剖宫产和引产，周一和周二也有更高的出生率。 在他的论文中，冯·米塞斯继续计算精确的概率分布，但期望值足以证明数学部门用错误的方式看待这个问题。 期望值还允许我们近似表示哈希表中将发生的碰撞数量，这取决于我们选择的值。 此外，网络安全中有一种特殊的暴力攻击叫做生日攻击（Birthday Attack），它利用生日问题背后的数学原理来创建碰撞，从而破坏系统。攻击者生成随机输入，直到其中两个产生相同的哈希输出。这大约在√n次尝试后会发生。例如，SHA-256有\[2^{256}\]个输出。这将需要\[2^{128}\]次尝试来破解。注意，攻击者不是在等待一个特定的哈希值出现两次，任何碰撞都足以让系统停止工作。 我们之前已经聊过一些关于哈希表中的碰撞问题。(https://0xkrt26.github.io/math_behind_security/2026/04/28/the-accidental-ancestor-Luhn-algorithm.html)现在我们知道，哈希表碰撞背后的数学就是生日问题的数学：日子变成了表字段，人变成了哈希，但计算方法保持不变。 ### 我的来源和进一步阅读： Richard Von Mises, "Über Aufteilungs- und Besetzungswahrscheinlichkeiten" (第313页) (http://alexander.shen.free.fr/vonMises_64_SelectedPapersVol2OCR.pdf)理查德·冯·米塞斯传记 (https://link.springer.com/content/pdf/10.1007/978-3-0348-8787-8_13)康涅狄格大学讲座 (https://www.phys.uconn.edu/~rozman/Courses/P2400_24S/downloads/birthday.pdf)