hash - md5 哈希冲突。

Question

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

我想知道我是否使用 md5 作为序列号，在发生碰撞之前我可以期望能够枚举多少个单元。

Answer 1

从理论上讲，您可以预期 X 在 2 ⁶⁴附近发生碰撞。对于具有n位输出的散列函数，当您累积大约 2 ^{n/2 个}输出时会出现第一次冲突（无论您如何选择输入；顺序整数值在这方面没有什么特别之处）。

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

Answer 2

我无法回答您的问题，但您正在寻找的是uuid。UUID 序列号对于数百万种产品可能是唯一的，但您可能需要检查数据库以减少发生碰撞的微小机会。

Answer 3

我相信没有人对此做过一些测试

考虑到如果你有一个简单的增量数字，你不需要散列它

Answer 4

据我所知，在 md5 中没有已知的 2^32 冲突（整数大小）

Answer 5

这实际上取决于您输入的大小。完美的散列函数在每个 (input_length / hash_length) 散列中都有冲突。如果您的输入很小，则不太可能发生碰撞，到目前为止，只有一个单块碰撞。

Answer 6

我意识到这是一个老问题，但我偶然发现了它，找到了一个更好的方法，并认为我会分享它。

您的序数 N 有一个上限，所以让我们利用它。假设 N < 2 ³² ≈ 4.3*10 ¹⁰。现在，每次您需要一个新标识符时，您只需选择一个随机的 32 位数字 R 并将其与 R xor N 连接（连接前的零填充）。这会产生一个随机的、唯一的 64 位标识符，您可以只用 16 个十六进制数字表示。

这种方法完全防止了冲突，因为碰巧具有相同随机分量的两个标识符必然具有不同的异或分量。

额外功能：您可以将这样的 64 位标识符拆分为两个 32 位数字，然后将它们相互异或以恢复原始序数。