密码学 ｜ 5.4 碰撞算法与中间相遇攻击

由于找到相匹配的对象通常比找到特定对象要容易得多，于是我们有了一种简单又相对高效的方法。这类方法有很多名称，比如中间相遇攻击、碰撞算法等。

5.4.1 生日悖论

著名的生日悖论清楚地说明了碰撞算法背后的基本思想。在40人的随机小组中，考虑以下两个问题

1. 有人和你同一天生日的概率有多大？

2. 至少有两个人同一天生日的概率有多大？

这两个问题的答案是截然不同的，那么，我们先从简单的起手，解决一下第一个问题。

因此，在40名陌生人中有大约 90% 的概率有两个人具有相同的生日。

大多数人倾向于问题（1）和（2）的答案基本相同，但计算结果却相差甚远。但其实，这还不是被称为生日悖论的问题。生日悖论其实是，只需要23个人就能有50%以上的概率有两个人具有相同的生日，然而需要253个人才能有超过50%的概率找到和你有相同生日的人。

原文始发于微信公众号（山石网科安全技术研究院）：密码学 ｜ 5.4 碰撞算法与中间相遇攻击