是否存在 md5(x) == x 的 MD5 定点? [英] Is there an MD5 Fixed Point where md5(x) == x?

问题描述

MD5 转换中是否有一个不动点，即是否存在 x 使得 md5(x) == x?

解决方案

由于 MD5 和是 128 位长，因此任何定点也必须是 128 位长.假设任何字符串的 MD5 和均匀分布在所有可能的和上，那么任何给定的 128 位字符串是不动点的概率为 ¹/_2¹²⁸.

因此，没有 128 位字符串是不动点的概率是 (1 − ¹/_2¹²⁸)²¹²⁸，所以存在不动点的概率为 1 − (1 − ¹/_2¹²⁸)²¹²⁸.

由于当 n 趋于无穷大时， (1 − ¹/_n)ⁿ 是 ¹/_e 和 2¹²⁸ 肯定是一个非常大的数字，这个概率几乎正好是 1 − ¹/_e ≈ 63.21%.

当然，实际上并没有涉及随机性–要么有一个固定点，要么没有.但是，我们有 63.21% 的把握认为存在一个固定点.(另外，请注意，这个数字不取决于密钥空间的大小——如果 MD5 和是 32 位或 1024 位，答案将是相同的，只要它大于大约 4 或 5 位即可).

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(x) == x 的 MD5 定点?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！