math - 哈希冲突的可能性

Question

我正在根据生日悖论寻找有关MD5，SHA1和SHA256发生碰撞的可能性的精确数学。
我正在寻找类似图形的图形，该图形表示“如果您有10 ^ 8个键，这就是概率。如果您有10 ^ 13个键，这就是概率，依此类推”
我看了无数的文章，但是我很难找到可以提供这些数据的东西。 (对我来说，理想的选择是公式或代码，以针对任何提供的哈希大小计算出此值)

Answer 1

让我们想象一下，我们有一个真正的随机哈希函数，可以从字符串哈希到n位数字。这意味着有2n种可能的哈希码，并且从所有这些可能性中随机地均匀选择每个字符串的哈希码。
生日悖论特别指出，一旦您大致看到√(2k)个项目，发生碰撞的机率就有50％，其中k是不同的可能输出的数量。在散列函数散列为n位输出的情况下，这意味着在发生冲突之前，大约需要2n/2个散列。这就是为什么我们通常选择输出256位的哈希值的原因。这意味着在需要“合理的”碰撞机会之前，我们需要对2128个≈1038个项进行散列处理。使用512位哈希，您大约需要2256个才能获得50％的碰撞机会，而approximately the number of protons in the known universe是2256个。
与n位哈希函数和k个字符串被哈希的冲突概率的精确公式为

1 - 2ⁿ! / (2^kn (2ⁿ - k)!)

这是一个非常棘手的数量，可以直接使用，但是我们可以使用以下表达式获得该数量的近似值

1 - e^-k2/2n+1

因此，要获得(大约)碰撞的概率p，我们可以求解得到

p ≈ 1 - e^-k2/2n+1

1 - p ≈ e^-k2/2n+1

ln(1 - p) ≈ -k²/2ⁿ⁺¹

-ln(1 - p) ≈ k²/2ⁿ⁺¹

-2ⁿ⁺¹ ln(1 - p) ≈ k²

2^(n+1)/2 √(-ln(1 - p)) ≈ k

作为最后的近似，假设我们正在处理p的很小的选择。然后ln(1- p)≈-p，因此我们可以将其重写为

k ≈ 2^(n+1)/2 √p

请注意，这里仍然有一个庞然大物2(n + 1)/2项，因此对于256位哈希，其前导项为2128.5，这是巨大的。例如，为了看到2到50位与256位哈希值发生冲突的机会，我们必须看到多少个项目？那大概是

2^(256+1)/2 √2^-50

= 2^257/2 2^-50/2

= 2^207/2

= 2^153.5.

因此，您将需要数量惊人的散列，以使发生碰撞的可能性极小。图2153.5约为1045，以每十亿分之一秒计算的哈希将花费您比要计算的Universe更长的时间。毕竟，您将获得2-50的成功概率，大约为10-15。
实际上，这就是为什么我们选择如此大量的哈希作为哈希值的原因!这使得偶然发生碰撞的可能性极小。
(请注意，我们今天拥有的哈希函数实际上并不是真正的随机函数，这就是为什么人们建议不要使用MD5，SHA1以及其他暴露出安全性弱点的原因。)
希望这可以帮助!