我正在寻找一些基于生日悖论的关于 MD5、SHA1 和 SHA256 冲突可能性的精确数学。
我正在寻找类似图表的东西，上面写着“如果你有 10^8 个键，这就是概率。如果你有 10^13 个键，这就是概率等等”
我看过很多文章，但我很难找到能给我这些数据的东西。（对我来说，理想的选择是计算任何提供的哈希大小的公式或代码）
问问题
12991 次
1 回答
36
假设我们有一个真正的随机散列函数，可以从字符串散列到 n 位数字。这意味着有 2 n 个可能的哈希码，并且每个字符串的哈希码都是从所有这些可能性中均匀随机选择的。
生日悖论特别指出，一旦你看到大约 √(2k) 个项目，就有 50% 的机会发生碰撞，其中 k 是不同的可能输出的数量。在散列函数散列到 n 位输出的情况下，这意味着在发生冲突之前您将需要大约 2 n/2 个散列。这就是为什么我们通常选择输出 256 位的散列；这意味着我们需要一个惊人的 2 128 ≈10 38 个项目散列，然后才有“合理”的碰撞机会。使用 512 位哈希，您需要大约 2 256才能获得 50% 的碰撞机会，而 2 256大约是已知宇宙中的质子数。
与 n 位散列函数和散列的 k 个字符串发生冲突的概率的确切公式是
1 - 2 ！/ (2 kn (2 n - k)!)
这是一个很难直接处理的量，但是我们可以使用表达式得到这个量的一个不错的近似值
1 - e -k 2 /2 n+1
因此，为了（大致）获得碰撞的概率 p，我们可以求解得到
p ≈ 1 - e -k 2 /2 n+1
1 - p ≈ e -k 2 /2 n+1
ln(1 - p) ≈ -k 2 /2 n+1
-ln(1 - p) ≈ k 2 /2 n+1
-2 n+1 ln(1 - p) ≈ k 2
2 (n+1)/2 √(-ln(1 - p)) ≈ k
作为最后一个近似值，假设我们正在处理非常小的 p 选择。那么 ln(1 - p) ≈ -p，所以我们可以将其重写为
k ≈ 2 (n+1)/2 √p
请注意，这里仍然有一个怪物 2 (n+1)/2项，因此对于 256 位散列，前导项是 2 128.5，这简直是巨大的。例如，我们必须看到多少项才能获得 2 -50的与 256 位哈希发生冲突的机会？那大约是
2 (256+1)/2 √2 -50
= 2 257/2 2 -50/2
= 2 207/2
= 2 103.5。
因此，您需要数量惊人的散列才能使发生冲突的机会微乎其微。假设 2 103.5大约是 10 31，在计算每个散列一纳秒的情况下，计算所需的时间比计算宇宙的长度要长。毕竟，你会得到 2 -50的成功概率，大约是 10 -15。
事实上，这正是我们为散列选择如此大量位的原因！这使得偶然发生碰撞的可能性极小。
（请注意，我们今天拥有的哈希函数实际上并不是真正的随机函数，这就是为什么人们建议不要使用 MD5、SHA1 和其他暴露了安全漏洞的函数。）
希望这可以帮助！
于 2020-06-30T23:36:42.633 回答