hash - SHA1 冲突的概率

Question

给定一组 100 个相同长度的不同字符串，您如何量化字符串的 SHA1 摘要冲突不太可能发生的概率......？

Answer 1

SHA-1 生成的 160 位哈希值是否足够大以确保每个块的指纹都是唯一的？假设具有均匀分布的随机散列值、n 个不同数据块的集合和一个生成 b 位的散列函数，发生一次或多次碰撞的概率 p 的边界是块对的数量乘以发生碰撞的概率给定的一对将发生碰撞。

（来源：http ://bitcache.org/faq/hash-collision-probabilities ）

Answer 2

那么，碰撞的概率是：

1 - ((2^160 - 1) / 2^160) * ((2^160 - 2) / 2^160) * ... * ((2^160 - 99) / 2^160)

想想在 10 个空间中 2 个项目发生碰撞的概率。第一个项目是唯一的，概率为 100%。第二个是唯一的，概率为 9/10。所以两者都是唯一100% * 90%的概率是 ，碰撞的概率是：

1 - (100% * 90%), or 1 - ((10 - 0) / 10) * ((10 - 1) / 10), or 1 - ((10 - 1) / 10)

这不太可能。你必须有更多的字符串才能成为一个遥远的可能性。

看看维基百科这个页面上的表格；只需在 128 位和 256 位的行之间进行插值。

Answer 3

那是生日问题- 这篇文章提供了很好的近似值，可以很容易地估计概率。实际概率将非常非常低 - 请参阅此问题作为示例。