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

Question

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

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

Answer 1

这个问题类似于所谓的"birthday paradox" .

In probability theory, the birthday problem or birthday paradox concerns the probability that, in a set of n randomly chosen people, some pair of them will have the same birthday. By the pigeonhole principle, the probability reaches 100% when the number of people reaches 367 (since there are 366 possible birthdays, including February 29). However, 99% probability is reached with just 57 people, and 50% probability with 23 people. These conclusions are based on the assumption that each day of the year (except February 29) is equally probable for a birthday.

The mathematics behind this problem led to a well-known cryptographic attack called the birthday attack, which uses this probabilistic model to reduce the complexity of cracking a hash function.

根据维基百科文章，从 d = 2 的空间中选择 n = 2³² 个随机数时发生碰撞的几率¹²⁸ 数字大约为:

如果您work this calculation out几率约为 2.7×10^-20。这是一个非常小的概率，但请注意，它比您建议的计算高 9 个数量级。