是否有MD5固定点，其中md5（x）== x？ [英] Is there an MD5 Fixed Point where md5(x) == x?

问题描述

在MD5转换中是否存在一个固定点，即是否存在x md5（x）== x ？

<由于MD5总和是128位长，所以任何固定点必须也必须是128位长。假设任何字符串的MD5总和均匀分布在所有可能的总和上，那么任何给定的128位字符串是固定点的概率是1 / 2 ¹²⁸ 。

因此，没有128位字符串是固定点的概率是（1 - ¹ / _{2 <128>} ）<2> 128 有一个固定点是1 - （1 - ¹ / _{2 ¹²⁸} ） ^{2 < sup> 128} 。

由于n的极限值为（1 - ¹ / _n ） ⁿ 是 ¹ / _e 和2 <128> 肯定是一个非常大的数字，这个概率几乎就是1 - ¹ / _{em> e} ≈63.21％。

当然，没有实际涉及的随机性。要么有固定点，要么没有固定点。但是，我们可以有63.21％相信有一个固定点。 （另外请注意，这个数字并不取决于密钥空间的大小，如果MD5和为32位或1024位，只要它大于大约4或5位，答案将是相同的）。 p>

Is there a fixed point in the MD5 transformation, i.e. does there exist x such that md5(x) == x?

解决方案

Since an MD5 sum is 128 bits long, any fixed point would necessarily also have to be 128 bits long. Assuming that the MD5 sum of any string is uniformly distributed over all possible sums, then the probability that any given 128-bit string is a fixed point is ¹/_2¹²⁸.

Thus, the probability that no 128-bit string is a fixed point is (1 − ¹/_2¹²⁸)²¹²⁸, so the probability that there is a fixed point is 1 − (1 − ¹/_2¹²⁸)²¹²⁸.

Since the limit as n goes to infinity of (1 − ¹/_n)ⁿ is ¹/_e, and 2¹²⁸ is most certainly a very large number, this probability is almost exactly 1 − ¹/_e ≈ 63.21%.

Of course, there is no randomness actually involved – either there is a fixed point or there isn't. But, we can be 63.21% confident that there is a fixed point. (Also, notice that this number does not depend on the size of the keyspace – if MD5 sums were 32 bits or 1024 bits, the answer would be the same, so long as it's larger than about 4 or 5 bits).

这篇关于是否有MD5固定点，其中md5（x）== x？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！