截断MD5哈希，我如何计算发生碰撞的概率？

Question

19

我想要将一个md5哈希值截短到一半左右的长度。这会增加碰撞的概率吗？如果我处理大约500,000个生成值，我应该担心碰撞吗？那1百万个生成值呢？

- dc.

只是为了澄清问题，您是说您想从一个已知存在漏洞的弱哈希算法开始，然后故意使它更加脆弱吗？ - Craig Tullis

8

他并不一定是出于安全原因而使用哈希函数。 - hedgedandlevered

2个回答

1

有一个有趣的数学问题叫做生日悖论问题，它处理了这种情况。事实是，你插入的条目越多，发生碰撞的几率就越高。

根据上面链接发布的表格，假设你的摘要每个都是64位（因为单个MD5哈希是128位），并且MD5具有均匀分布，那么两个哈希值发生碰撞的可能性非常低。在610,000,000个条目时，这变得显著（1％或更高）。

- zneak

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- John Kugelman · Accepted Answer

你需要查看维基百科上的生日攻击页面以获得所需的数学知识。

我们考虑以下实验。从一组H个值中，我们随机选择n个值，允许重复。设p(n; H)为在此实验期间至少选择一个值超过一次的概率。这个概率可以近似为

使用128位，500,000个哈希值之间发生冲突的概率约为10^-28。如果将碰撞空间的大小减半，则碰撞的概率约为10^-9。也就是说，即使概率大得多，它仍然非常非常低。这取决于是否关键是没有冲突。10^-9约为十亿分之一，因此虽然极不可能但仍在可能的范围内。

供参考：

10²⁸ = 一千亿亿 = 十万亿亿亿
10⁹ = 十亿