md5哈希冲突.

Question

如果从1到X计数,其中X是第一个与前一个数字发生md5冲突的数字,那么X是多少？

我想知道我是否使用md5作为序列号,在碰撞之前我可以期望能够枚举多少单位.

Answer 1

从理论上讲,你可以预期X约为2 ^64的碰撞.对于具有的输出的哈希函数ñ位,当你积累了约2第一碰撞出现^N/2输出(也不要紧,你该如何选择输入;连续整数值是没有什么特别在这方面).

当然,MD5已被证明不是一个好的哈希函数.此外,2 ^n/2只是平均值.那么,你为什么不尝试呢？采用MD5实现,哈希您的序列号,看看是否发生了冲突.基本的MD5实现应该能够每秒散布几百万个值,并且使用合理的硬盘,您可以累积几十亿个输出,对它们进行排序,并查看是否存在冲突.

您不需要存储或检查2 ^ 64值来检测周期,这是一个具有O(0)空间要求的聪明算法.看到这篇文章:http://stevekrenzel.com/articles/md5-cycles (4认同)
@John:要搜索大量值中的碰撞,诀窍是按升序对它们进行排序.然后碰撞显示为两个相同的连续值.合并排序仅意味着少量的线性通道; 不涉及骚扰.不过,2 ^ 64还是相当多的. (2认同)