如果您对哈希进行无数次哈希处理，您是否会得到唯一的哈希？

#1 楼

如果在有限域中对其结果重复应用泛型函数，则趋向于获得“ rho”结构：在某个点上，您输入的循环的长度为（大约）$ \ sqrt {N} $，其中$ N $是函数的输出空间的大小。对于MD5，$ N = 2 ^ {128} $（MD5输出128位值），因此循环的长度约为$ 2 ^ {64} $个值。您可以“无限地”散列，永远不会得到唯一的值。有关详细信息和图片，请参见此答案。

严格来说，您可能会以唯一值结尾，该值称为固定点，但我们不知道这样的固定点是否真正与MD5存在。对于随机选择的函数，一个定点根本存在的可能性约为$ 63 \％$。但是，存在定点并不意味着您会达到目标。实际上，在大多数情况下，您会以“大内循环”结束。如果有一个固定点，则最终只会以大约$ 1 / \ sqrt {N} $的概率命中它，即很少见。

一般来说，从某些输入和反复进行哈希运算，您总是会走一个循环，而且永远不会结束。不动点是只有一个元素的循环的特例。对于给定的功能，人们希望
有一个“大”循环，您最终会为大多数输入到达，而又有一个几乎没有的循环。

#2 楼

我认为Thomas Pornin的答案远远优于我的答案，但也许这个答案可以简化他的答案。

当您最初对某些数据进行哈希处理时，可能的输入是无限/无限制的。您可以输入“ abcdefghi ...”，“ 123456 ...”等。但是，产生的散列可能性是有限的/有限的。

关于大多数散列函数的妙处之一是它们的输出始终是固定长度。对于MD5，输出始终为128位。这对于以编程方式处理输出并将哈希输出存储在文件/数据库中非常有用，但这意味着可能输出的数量受到限制。对于MD5，限制为$ 2 ^ {128} $（即340,282,366,920,938,463,463,374,607,431,768,211,456）。这看似很高，以至于永远都无法达到，但是理论上我们正在处理无数次的哈希。

因为md5("Anything")的输入只有$ 2 ^ {128} $可能的输出所有后续回合中的都是有限的，大多数哈希函数将通过2^(<Number Bits in Output>/2)产生冲突。 （对于MD5，为$ 2 ^ {64} $。）请考虑以下代码：

String nextInput = "Some initial text here";
while(true){ // Infinite loop
    nextInput = md5(nextInput);
}

由于发生冲突，我们可以预料最终进入一个模式，其中$ round_ {1} $，$ round_ {2} $，$ round_ {3} $，... $ round_ {n} $将导致$ round_ {n} $的输出等于$ round_ {1} $。因此，输出最终将进入类似initialRoundOutput == currentRoundOutput的圆形状态，因此圆形/图案/循环将无限重复。托马斯·珀金（Thomas Pornin）的答案进行了解释，但是设计了散列函数，以便输入数据与输出不同。但是，理论上可能存在这样的输入。请参阅此StackOverflow答案，以获取对此的良好解释。