http://www.mscs.dal.ca/~selinger/md5collision/上给出的冲突示例显示了两个不同的字符串，其中只有一个很小的字符串数据量已更改为相同的md5，但感觉更像是更改未计入计算的值。我还没有遇到一个例子，其中两个看似随机的事物达到相同的值。我确实尝试了一个小脚本来找出答案，但是显然它的距离不够远。
我的问题的一种形式化是：
最小的是什么$ b \ in \ mathbb N $使得存在$ a \ in [0，b）$与$ \ mathbf {MD5}（a）= \ mathbf {MD5}（b）$存在$
#1 楼
要回答您的问题，我们必须首先声明对于整数$ x $，我们将MD5（$ x $）定义为$ x $编码为位序列的MD5哈希。实际上，MD5期望将一系列位作为输入，而不是整数。我们应该选择常规编码；我选择大端。因此，整数$ 44 $编码为6位序列：101100。这样做可能会导致我错过一半的MD5输入：的确，当将整数转换为最小长度的big-endian无符号编码时，第一个位始终是'1'。尽管编码对于下面的讨论并不重要，但它会影响所需的$ b $的值。实际上，每种编码都会产生另一个$ b $。由于MD5具有$ 128 $位的输出，因此它最多可以具有$ 2 ^ {128} $个不同的输出。如果我使用整数$ 0 $到$ 2 ^ {128} $（含），则我有$ 2 ^ {128} + 1 $：因此从数学上保证了其中至少有两个哈希值相同。换句话说，证明存在整数值$ a $和$ b $使得$ 0 \ leq a
$ b $的实际最小值未知。但是，预计最小的$ b $约为$ 2 ^ {64} $。这来自所谓的生日问题：如果我在一组大小为$ N $的范围内随机获取$ n $的值，那么当$ n $达到$ \ sqrt {N} $时，我将选择之前已经选择的值。大概。
要获得$ b $，实际上必须为$ x $的所有值（从$ 0 $开始）生成MD5（$ x $），直到获得已经拥有的值。 MD5的预期成本很高：$ 2 ^ {64} $在技术范围内，但在家用计算机范围内。在四核x86上，可能期望每秒获得大约$ 2 ^ {26} $ MD5评估；如果拥有良好的GPU，则您可以达到$ 2 ^ {33} $的每秒价格（这个家伙声称要多出$ 2 ^ {36} $，但配备8个GPU）。您仍然需要大约60年才能达到$ 2 ^ {64} $。另一个问题（从长远来看可能会成为一个大问题）是如何检测到您确实获得了两倍的相同散列输出：$ 2 ^ {64} $ 16字节结果将不适合RAM ...实际上，这是搜索问题可能不仅仅是计算所有MD5的问题。
（有些漂亮的碰撞搜索算法需要很少的RAM，但是我不确定它们是否可以应用于精确的碰撞搜索算法。您所说的问题，您不仅要寻找冲突，而且要寻找最小的$ b $值。）
#2 楼
有关基于启发式论证的理论上最小的内容，请参见其他答案。对于带有512位消息的两个具体示例，远远超出了最小值，但只有问题中所链接示例的一半大小
4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2 和（相差两位）
4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2 都具有MD5哈希值
008ee33a9d58b51cfeb425b0959121c9 >
0e306561559aa787d00bc6f70bbdfe3404cf03659e704f8534c00ffb659c4c8740cc942feb2da115a3f4155cbb8607497386656d7d1f34a42059d78f5a8dd1ef （与其他两个位不同）
0e306561559aa787d00bc6f70bbdfe3404cf03659e744f8534c00ffb659c4c8740cc942feb2da115a3f415dcbb8607497386656d7d1f34a42059d78f5a8dd1ef 都具有MD5哈希值
cee9a457e790cf20d4bdaa6d69f01e41 示例1.直接来自Marc Stevens：单块碰撞对于MD5，2012；他使用源代码（了本文的替代链接）解释了他的方法。
示例2摘自谢涛和邓国峰：仅使用单个消息块即可构造MD5冲突，2010年。<问题要求最小的整数，但没有规定整数到消息的映射，特别是字节顺序。在上面，我使用了八位字节串，其中每对十六进制字符都按照big-endian惯例编码一个八位字节，这是惯例。按照MD5的要求，每个4个连续的八位字节都按照little-endian约定形成一个32位字。
鉴于MD5的定义，整数到MD5消息的最自然映射似乎是以二进制形式作为具有Little-endian约定的位字符串。有时填充可以修剪一个位：第二个示例的高位半字节（最后一个十六进制字符）为
e（hex）= 1110（bin），这允许修剪为110（bin）= 6（十六进制），填充将恢复该状态；但在第一个示例中，如果将a（hex）= 1010（bin）修剪为10（bin），则填充会将其更改为0110（bin）= 6（hex），并且poof发生冲突。因此，从第二个示例中可以得出整数作为小尾数位字符串类别中的当前冠军，它允许构建一个具有大尾数值
6fd18d5a8fd75920a4341f7d6d658673490786bbcd..556165300e的511位数字，而另一个具有相同哈希值的较小数字6fd18d5a8fd75920a4341f7d6d658673490786bbc5..556165300e（但不是也许只需运行Marc Stevens的代码并保持找到的最佳值，皇冠就可以回到第一个示例的系列。
br />
评论
$ \ begingroup $
相反的方向-从哈希到数据呢？
$ \ endgroup $
– pbies
20年4月8日在5:19