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

Question

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

Answer 1

由于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位).

Answer 2

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

前缀12:54db1011d76dc70a0a9df3ff3e0b390f - > 54db1011d76d137956603122ad86d762

后缀12:df12c1434cec7850a7900ce027af4b78 - > b2f6053087022898fe920ce027af4b78

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

Answer 3

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

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

Answer 4

有可能，但是找到它需要比我们更长的时间，或者会涉及破坏 MD5。