md5对短字符串(有限数量的字符串)有任何唯一性保证吗？

Question

所以我理解有证据表明MD5不能保证唯一性,因为宇宙中的字符串多于MD5哈希字符串,但是对于有限数量的字符串是否有任何反证明？

基本上,如果我有最大长度为X的字符串,是否有一个X保证MD5是唯一的？如果是,那那X是什么？如果X的值不止一个,那么X的最大值是多少？

或者是否有任何其他散列算法,SHA-1等的X？

Answer 1

你的问题的答案是肯定的。对于任何哈希函数，都有一个最大长度 X，您将返回唯一的字符串。然而，找到 X 可能非常困难。这个想法是运行这个程序：

X= 0;
For i = 0 onward
   For all strings of length i
      Compute the hash code of that string.
      If a collision is found, return X.
   X = i

这个想法是列出越来越长的字符串，直到找到哈希冲突。最终您将不得不这样做，因为最终您将生成比可能的哈希输出更多的字符串。

按照预期，假设哈希函数实际上非常随机，您需要在发现冲突之前生成 O(√U) 个不同的字符串，其中 U 是哈希函数映射到的空间的大小。对于 256 位哈希值，这是 2 ²⁵⁶。这意味着实际上上面的程序永远不会真正终止，除非散列函数非常糟糕，但理论上这意味着你的数字 X 存在。

希望这可以帮助！