如果我传入2 ^ 32组字符串,md5碰撞的概率是多少？

Question

如果我传入2 ^ 32组字符串,md5碰撞的概率是多少？

我可以说答案只是2 ^ 32/2 ^ 128 = 1/1.2621774e-29,因为md5 hash的位长是128？

Answer 1

这个问题类似于所谓的"生日悖论".

在概率论中,生日问题或生日悖论涉及在一组n个随机选择的人中,他们中的某些人将拥有相同生日的概率.根据鸽子原则,当人数达到367时,概率达到100%(因为有366个可能的生日,包括2月29日).然而,只有57人达到99%的可能性,23人有50%的可能性.这些结论是基于这样的假设:一年中的每一天(2月29日除外)同样可能是生日.

这个问题背后的数学导致了一种众所周知的加密攻击,称为生日攻击,它使用这种概率模型来降低破解哈希函数的复杂性.

根据维基百科的文章,当从d = 2 ^128个数字的空间中选择n = 2 ^32个随机数时发生碰撞的可能性大约为:

如果你计算出这个计算机会大概是2.7×10 ^-20.这是一个非常小的概率,但请注意它比您提出的计算高9个数量级.