如果我传入2^32组字符串，那么md5碰撞的概率是多少？
我可以说答案只是2^32/2^128 = 1/1.2621774e-29吗，因为md5哈希的位数为128？
1个回答
26
这个问题类似于所谓的"生日悖论"。
在概率论中，生日问题或生日悖论涉及到从随机选择的n个人中，存在某对人拥有相同生日的概率。通过鸽巢原理，当人数达到367人时（因为有366种可能的生日，包括2月29日），概率达到100％。然而，只要有57个人就可以达到99％的概率，23人则可以达到50％的概率。这些结论基于每年的每一天（除了2月29日）生日是等可能发生的假设。
这个问题背后的数学知识导致了一种著名的密码攻击，称为生日攻击，该攻击使用这种概率模型来降低破解哈希函数的复杂性。
根据维基百科文章，从具有d = 2128个数字的空间中选择n = 232个随机数产生碰撞的机率约为:
如果您计算这个概率，结果约为2.7×10-20。这是一个非常小的概率，但请注意，它比您提出的计算结果高9个数量级。
- John Kugelman
1
9假设MD5算法的哈希分布完全均匀，甚至在这种情况下，发生哈希碰撞的概率仍然很高，因为实际上MD5算法的哈希分布并不均匀。 - neelsg
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接