MD5 变换中是否存在固定点，即是否存在 x 使得md5(x) == x?
Jack
问问题
20019 次
7 回答
140
由于 MD5 和的长度为 128 位，因此任何固定点也必须是 128 位长。假设任何字符串的 MD5 和均匀分布在所有可能的和上，那么任何给定的 128 位字符串是不动点的概率是1 / 2 128。
因此，没有 128 位字符串是不动点的概率为 (1 - 1 / 2 128 ) 2 128，因此存在不动点的概率为 1 - (1 - 1 / 2 128 ) 2 128。
由于 (1 − 1 / n ) n的 n 趋于无穷大的极限是1 / e，并且 2 128肯定是一个非常大的数字，所以这个概率几乎正好是 1 − 1 / e ≈ 63.21%。
当然，实际上并不涉及随机性——要么有一个固定点，要么没有。但是，我们可以有 63.21% 的把握有一个固定点。（另外，请注意，这个数字不取决于密钥空间的大小——如果 MD5 和是 32 位或 1024 位，则答案将是相同的，只要它大于大约 4 或 5 位）。
于 2008-10-25T04:34:57.737 回答
14
我的蛮力尝试找到了 12 个前缀和 12 个后缀匹配。
前缀 12：54db1011d76dc70a0a9df3ff3e0b390f -> 54db1011d76d137956603122ad86d762
后缀 12：df12c1434cec7850a7900ce027af4b78 -> b2f6053087022898fe920ce027af4b78
博文：https: //plus.google.com/103541237243849171137/posts/SRxXrTMdrFN
于 2015-03-09T12:09:10.483 回答
11
由于哈希是不可逆的，因此很难弄清楚。解决这个问题的唯一方法是计算散列的每个可能输出的散列，看看你是否想出了一个匹配项。
详细地说，一个 MD5 散列中有 16 个字节。这意味着有 2^(16*8) = 3.4 * 10 ^ 38 种组合。如果计算一个 16 字节值的哈希值需要 1 毫秒，那么计算所有这些哈希值需要 10790283070806014188970529154.99 年。
于 2008-10-25T02:24:13.337 回答
2
虽然我没有是/否的答案，但我的猜测是“是”，而且可能有 2^32 个这样的固定点（用于位串解释，而不是字符串解释）。我正在积极研究这个问题，因为它看起来是一个很棒的、简洁的谜题，需要大量的创造力（如果你不立即满足于蛮力搜索的话）。
我的方法如下：将其视为数学问题。我们有 128 个布尔变量和 128 个根据输入（应该匹配）来描述输出的方程。通过插入算法表中的所有常量和填充位，我希望方程可以大大简化，以产生针对 128 位输入情况优化的算法。这些简化的方程然后可以用一些很好的语言编程以进行有效的搜索，或者再次抽象地处理，一次分配单个位，注意矛盾。您只需要查看输出的几位就知道它与输入不匹配！
于 2009-05-23T01:40:10.463 回答
-1
可能，但发现它需要比我们更长的时间，或者会涉及妥协 MD5。
于 2008-10-25T02:24:03.023 回答
-8
有两种解释，如果任一种选择，找到固定点的概率增加到 81.5%。
- 解释1：二进制MD5输出的MD5是否匹配其输入？
- 解释2：十六进制的MD5输出的MD5是否匹配其输入？
于 2009-05-06T15:32:34.790 回答
-23
严格来说，由于 MD5 的输入是 512 位，输出是 128 位，我会说从定义上来说这是不可能的。
于 2009-05-06T15:29:02.520 回答