哈希冲突概率
Probability of hash collision
我正在寻找一些基于生日悖论的关于 MD5、SHA1 和 SHA256 冲突可能性的精确数学。
我正在寻找类似图表的东西，上面写着“如果你有 10^8 个键，这是概率。如果你有 10^13 个键，这是概率等等”
我看过很多文章，但很难找到能给我这些数据的东西。 （对我来说，理想的选择是为任何提供的哈希大小计算这个的公式或代码）
假设我们有一个真正的随机散列函数，可以从字符串散列到 n 位数字。这意味着有 2n 种可能的哈希码，每个字符串的哈希码都是从所有这些可能性中随机选择的。
生日悖论特别指出，一旦您看到大约 √(2k) 个项目，就有 50% 的几率发生碰撞，其中 k 是不同可能输出的数量。在散列函数散列为 n 位输出的情况下，这意味着您需要大约 2n/2 次散列才能发生冲突。这就是为什么我们通常选择输出 256 位的哈希；这意味着我们需要一个惊人的 2128 ≈1038 个项目在发生“合理”的碰撞之前进行哈希处理。使用 512 位哈希，您需要大约 2256 才能获得 50% 的碰撞机会，而 2256 是 approximately the number of protons in the known universe.
与 n 位哈希函数和 k 个哈希字符串发生冲突的概率的确切公式是
1 - 2n! / (2kn (2n - k)!)
这是一个很难直接处理的数量，但我们可以使用表达式
得到这个数量的近似值
1 - e-k2/2n+1
因此，为了（大致）获得碰撞的概率 p，我们可以求解得到
p ≈ 1 - e-k2/2n+1
1 - p ≈ e-k2/2n+1
ln(1 - p) ≈ -k2/2n+1
-ln(1 - p) ≈ k2/2n+1
-2n+1 ln(1 - p) ≈ k2
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
= 2257/2 2-50/2
= 2207/2
= 2103.5.
所以你需要 惊人的 大量的哈希值才能有 消失的 小几率发生碰撞。算出 2103.5 大约是 1031，以每计算一个哈希计算 1 纳秒，您将花费比计算宇宙长度更长的时间。毕竟，你会得到 2-50 的成功概率，大约是 10-15.
事实上，这正是我们为散列选择如此多位的原因！这使得偶然发生碰撞的可能性极小。
（请注意，我们今天拥有的哈希函数实际上并不是真正的随机函数，这就是为什么人们建议不要使用 MD5、SHA1 和其他暴露了安全漏洞的函数。）
希望对您有所帮助！
我正在寻找一些基于生日悖论的关于 MD5、SHA1 和 SHA256 冲突可能性的精确数学。
我正在寻找类似图表的东西，上面写着“如果你有 10^8 个键，这是概率。如果你有 10^13 个键，这是概率等等”
我看过很多文章，但很难找到能给我这些数据的东西。 （对我来说，理想的选择是为任何提供的哈希大小计算这个的公式或代码）
假设我们有一个真正的随机散列函数，可以从字符串散列到 n 位数字。这意味着有 2n 种可能的哈希码，每个字符串的哈希码都是从所有这些可能性中随机选择的。
生日悖论特别指出，一旦您看到大约 √(2k) 个项目，就有 50% 的几率发生碰撞，其中 k 是不同可能输出的数量。在散列函数散列为 n 位输出的情况下，这意味着您需要大约 2n/2 次散列才能发生冲突。这就是为什么我们通常选择输出 256 位的哈希；这意味着我们需要一个惊人的 2128 ≈1038 个项目在发生“合理”的碰撞之前进行哈希处理。使用 512 位哈希，您需要大约 2256 才能获得 50% 的碰撞机会，而 2256 是 approximately the number of protons in the known universe.
与 n 位哈希函数和 k 个哈希字符串发生冲突的概率的确切公式是
1 - 2n! / (2kn (2n - k)!)
这是一个很难直接处理的数量，但我们可以使用表达式
得到这个数量的近似值1 - e-k2/2n+1
因此，为了（大致）获得碰撞的概率 p，我们可以求解得到
p ≈ 1 - e-k2/2n+1
1 - p ≈ e-k2/2n+1
ln(1 - p) ≈ -k2/2n+1
-ln(1 - p) ≈ k2/2n+1
-2n+1 ln(1 - p) ≈ k2
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
= 2257/2 2-50/2
= 2207/2
= 2103.5.
所以你需要 惊人的 大量的哈希值才能有 消失的 小几率发生碰撞。算出 2103.5 大约是 1031，以每计算一个哈希计算 1 纳秒，您将花费比计算宇宙长度更长的时间。毕竟，你会得到 2-50 的成功概率，大约是 10-15.
事实上，这正是我们为散列选择如此多位的原因！这使得偶然发生碰撞的可能性极小。
（请注意，我们今天拥有的哈希函数实际上并不是真正的随机函数，这就是为什么人们建议不要使用 MD5、SHA1 和其他暴露了安全漏洞的函数。）
希望对您有所帮助！