md5 - 如果我传入 2^32 组字符串，md5 冲突的概率是多少？

Question

如果我传入 2^32 组字符串，md5 冲突的概率是多少？

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

Answer 1

这个问题类似于所谓的“生日悖论”。

在概率论中，生日问题或生日悖论涉及在一组n 个随机选择的人中，其中一些人生日相同的概率。根据鸽巢原理，当人数达到 367 时，概率达到 100%（因为有 366 个可能的生日，包括 2 月 29 日）。然而，只有 57 人达到 99% 的概率，而 23 人达到 50% 的概率。这些结论是基于这样的假设，即一年中的每一天（2 月 29 日除外）生日的概率相同。

这个问题背后的数学导致了一种著名的密码攻击，称为生日攻击，它使用这种概率模型来降低破解哈希函数的复杂性。

根据 Wikipedia 文章，从d = 2 ^{128个数字的空间中选择}n = 2 ^{32 个}随机数时发生冲突的几率约为：

如果你进行这个计算，机会大约是 2.7×10 ^-20。这是一个非常小的概率，但请注意它比您建议的计算高 9 个数量级。