是否有MD5固定点,其中md5(x)== x？

MD5转换中是否存在固定点,即是否存在x md5(x) == x？

1> Adam Rosenfi..：

---

由于MD5总和是128位长,所以任何固定点也必须是128位长.假设任何字符串的MD5和均匀地分布在所有可能的和,然后,任何给定的128位串是一个固定点的概率为¹ / _{2 ¹²⁸}.

因此,没有128位串是一个固定点的概率是(1 - ¹ / _{2 ¹²⁸})^{2 128},使得存在一个固定点的概率为1 - (1 - ¹ / _{2 ¹²⁸})^{2 128}.

由于限制正进行到(1 -无穷大¹ / _Ñ)^Ñ是¹ / _ë,和2 ¹²⁸是肯定一个非常大的数字,这个概率是几乎完全1 - ¹ / _Ë ≈63.21%.

当然,实际上并没有随机性 - 要么有固定点要么没有固定点.但是,我们可以63.21%确信存在固定点.(另请注意,此数字不取决于键空间的大小 - 如果MD5总和为32位或1024位,则答案将相同,只要它大于约4或5位).

---

是.大数字和模数形成大致随机分布.如果他们没有,你会不断碰撞.md5的性质迫使其输出随机分布.

---

你真的可以假设任何字符串的MD5总和均匀分布在所有可能的总和上吗？

---

我用你的答案作为这个答案的基础:http://security.stackexchange.com/questions/3851/can-a-file-contain-its-md5sum-inside-it/5609#5609

2> 小智..：

---

我的暴力尝试找到了12个前缀和12个后缀匹配.

前缀12:54db1011d76dc70a0a9df3ff3e0b390f - > 54db1011d76d137956603122ad86d762

后缀12:df12c1434cec7850a7900ce027af4b78 - > b2f6053087022898fe920ce027af4b78

博客文章:https: //plus.google.com/103541237243849171137/posts/SRxXrTMdrFN

3> Kibbee..：

---

由于散列是不可逆的,因此很难弄清楚.解决这个问题的唯一方法是计算散列的每个可能输出的散列,看看你是否想出了匹配.

详细说来,MD5哈希中有16个字节.这意味着有2 ^(16*8)= 3.4*10 ^ 38种组合.如果计算16字节值的散列需要1毫秒,那么计算所有这些散列需要10790283070806014188970529154.99年.

---

是的,如果你必须尝试*每一个*.但是你只需要尝试所有可能的输入来验证没有固定点.如果有一个固定点(亚当罗森菲尔德的回答表明可能存在),那么就需要一个幸运的猜测.

---

@Naaff:"只需要尝试每一个可能的输入" - 这比尝试每个哈希更容易,怎么样？恰恰相反,因为几个可能的输入可能会散列到相同的输出中.