截断md5哈希,如何计算发生冲突的几率？

Question

我想将md5哈希截断为大约一半的大小.多少会增加碰撞的几率？如果我要处理大约50万代,我应该担心碰撞吗？那一代人呢？

Answer 1

您正在寻找的数学是在维基百科的生日攻击页面上.

我们考虑以下实验.从一组H值中,我们随机均匀地选择n个值,从而允许重复.设p(n; H)是在该实验期间至少选择一个值多于一次的概率.该概率可以近似为

对于128位,500,000个散列值之间发生冲突的可能性大约为10 ^-28.如果将碰撞空间的大小减半,那么碰撞的几率大约为10 ^-9.也就是说,即使几率大大大于它仍然是非常非常低的.这取决于没有碰撞的重要性.10 ^-9是十亿分之一,所以虽然极不可能,但它在可能性范围内.

以供参考:

10 ²⁸ = 10 octillion = 100亿亿
10 ⁹ = 10亿

Answer 2

有一个有趣的数学问题，称为生日问题，可以处理这种情况。事实上，您推入的条目越多，发生碰撞的机会就越大。

按照上面链接上发布的表格，假设您的摘要均为 64 位（因为单个 MD5 哈希值是 128 位）并且 MD5 具有均匀分布，则两个哈希值发生冲突的可能性非常低。当条目数达到 610,000,000 时，它变得显着（1% 的机会或更多）。