生日悖论理论及在哈希函数碰撞中的应用

一、生日悖论（Birthday Paradox）介绍

二、生日悖论的数学解释

（一）计算所有人生日都不同的概率

数学推导

示例计算

（二）至少有两个人生日相同的概率

三、哈希函数碰撞与生日悖论的关系思考

（一）哈希函数碰撞中的应用

组合数量

计算碰撞概率

（二）具体应用中的示例

数字签名

数据完整性

（三）防御策略

四、总结和思考

干货分享，感谢您的阅读！

当我们谈论生日时，我们常常会联想到庆祝、礼物和美好的回忆。每一年，我们都在日历上标记着自己和亲朋好友的生日，因为生日不仅是一年中的特殊日子，更是连接人与人之间情感的纽带。然而，在数学和概率的世界里，生日的意义可能远超出我们的想象。

想象一下，当你身处一个房间里，随机地与一些陌生人打招呼，有多大可能会发现两个人竟然生日是同一天？这种可能性看似微小，但实际上却远远超出我们的直觉。这就是著名的生日悖论（Birthday Paradox）。

一、生日悖论（Birthday Paradox）介绍

生日悖论并不是一个真正意义上的悖论，而是概率论中的一种有趣现象，它告诉我们，尽管在较小的群体中两个或多个个体共享生日的概率很高，但这违背了直觉。具体来说，它指出在一个有23人的群体中，至少有两个人生日相同的概率超过50%。这个现象之所以如此引人注目，是因为它与我们日常生活中对概率的直觉相悖。

二、生日悖论的数学解释

假设一年有365天（忽略闰年），我们希望计算在n个人中至少有两个人生日相同的概率。

（一）计算所有人生日都不同的概率

当我们讨论所有人生日都不同的概率时，我们要考虑的是在一个给定数量的人中，每个人的生日都是唯一的情况下，概率是多少。

数学推导

假设一年有365天（忽略闰年），如果有 n 个人，我们需要计算他们的生日都不相同的概率，则概率计算步骤：

第一个人的生日可以是任意一天，概率为 $\frac{365}{365}$ .
第二个人的生日不能与第一个人相同，概率为 $\frac{364}{365}$ .
第三个人的生日不能与前两个人相同，概率为 $\frac{363}{365}$ .
以此类推，第 n 个人的生日不能与前 n−1 个人相同，概率为 $\frac{365-n+1}{365}$ .

所有人生日都不相同的概率是上述所有概率的乘积。数学上可以表示为：

这个乘积可以进一步简化为：

其中，n 是群体中的人数，! 表示阶乘。这个公式反映了随着人数 n 的增加，生日都不相同的概率会逐渐减小，因为随着人数增加，避免生日重复的可能性变得更加困难。

示例计算

假设有一个小群体，如 n=5 人：

计算结果约为 0.972，即约为 97.2% 的概率，这意味着在一个有5个人的群体中，他们的生日都不相同的概率非常高。这种概率计算展示了生日悖论的一个方面：尽管在较小的群体中，生日重复的概率并不低，但这种现象确实存在，这与我们通常的直觉相去甚远。

（二）至少有两个人生日相同的概率

这是所有事件的概率减去没有人生日相同的概率：

当n = 23时，计算所有人生日都不同这个概率：

直接使用计算器计算后，当n = 23时其值约等于0.4927，则至少有两个人生日相同的概率为：

因此，在23个人的群体中，至少有两个人生日相同的概率大于50%。

我们的直觉往往认为对于两个特定的人生日相同的概率是1/365，这样的概率很小，所以很难想象在一个较小的群体中有两个人生日相同的概率会超过50%。但实际上，这个问题的关键在于组合数，因为我们不是在考虑某两个人的生日，而是在考虑任意两个人的生日。随着群体人数增加，比较的组合数量也增加，导致生日相同的概率迅速增加。

生日悖论展示了概率直觉和实际情况之间的差异，提醒我们在处理概率问题时，要依赖数学计算而不是直觉。