hash-collision - 哈希冲突的可能性

Question

如果这是一个重复的问题，我们深表歉意；我发现的大多数都超出了我的想象，所以我可能错过了答案。

对于给定的哈希值，比如 MD5（128 位），与其中 10^12 个哈希值发生冲突的几率是多少？

我的数学不是很好，我想出了这个等式（我认为它是正确的）但不知道如何解决它：

Collision_Chance = 1 - (1 - (1 / 2^128) ) ^ (10^12)

我猜它在 10^-26 左右，这听起来对吗？

谢谢

编辑：我认为我的估计是非常错误的。见生日悖论

Answer 1

您的公式对于 2^128 + 1 个值有何意义？我相信它并没有说碰撞概率是1，所以它不可能是正确的。实际上，我知道它不是——正确的公式相当大且笨拙，但使用分数的指数有很好的近似值。SO不会排版公式，所以我不会尝试在这里写下公式。

搜索的最佳关键词可能是“<a href="http://en.wikipedia.org/wiki/Birthday_attack" rel="nofollow">生日攻击”。

Answer 2

为什么哈希冲突会成为问题？哈希从来没有被设计用来生成独特的值，只是为了促进快速的第一次比较。

如果您在哈希冲突方面遇到问题，则说明您使用错误。