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

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


5.4.1 生日悖论

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

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

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

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

一个粗略的答案是,由于任何一个人都有365分之一的机会和你同一天生日,那么在40人中,有人和你生日相同的概率大约为 。 然而,实际上这估计的过高了,因为它重复计算了人群中不止一个人和你同一天生日的次数。准确的答案是通过计算没有人和你同一天生日的概率,然后用  减去该值得出的。
密码学 | 5.4 碰撞算法与中间相遇攻击
此,在40名陌生人中,其中一人与你生日相同的概率仅略高于10%。
现在考虑第二个问题,如果小组中的任何两个人生日相同即可。同样,计算所有40个人的生日不同的概率也更容易。但计算方式发生了变化,因为我们现在要求第  个人的生日与之前的所有  个人生日都不同。因此,计算方式如
密码学 | 5.4 碰撞算法与中间相遇攻击

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

这个计算中唯一值得讨论的部分是第  个人生日与之前  中的任何一个人生日不同的概率公式。在365个可能的生日中,请注意前一个  人占用了其中  个。因此,第  人生日在剩下的 天中的概率为

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


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

版权声明:admin 发表于 2023年1月11日 上午10:35。
转载请注明:密码学 | 5.4 碰撞算法与中间相遇攻击 | CTF导航

相关文章

暂无评论

暂无评论...