115

MD5 変換に不動点はありますか。つまり、x は存在しmd5(x) == xますか?

4

7 に答える 7

140

MD5 の合計は 128 ビット長であるため、固定小数点も必ず 128 ビット長でなければなりません。任意の文字列の MD5 和が可能なすべての和に一様に分布していると仮定すると、任意の 128 ビット文字列が固定小数点である確率は1/2 128です。

したがって、128 ビット文字列が不動点ではない確率は (1 − 1 / 2 128 ) 2 128であるため、不動点が存在する確率は 1 − (1 − 1 / 2 128 ) 2 128です。

n が (1 − 1 / n ) nの無限大になるときの極限は1 / eであり、2 128は間違いなく非常に大きな数であるため、この確率はほぼ正確に 1 − 1 / e ≈ 63.21% です。

もちろん、実際にはランダム性は関係ありません。固定点がある場合とない場合のどちらかです。しかし、固定点があることを 63.21% 確信できます。(また、この数値はキースペースのサイズに依存しないことに注意してください。MD5 の合計が 32 ビットまたは 1024 ビットの場合、約 4 または 5 ビットより大きい限り、答えは同じになります)。

于 2008-10-25T04:34:57.737 に答える
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ビットの入力の場合に最適化されたアルゴリズムを生成できることを願っています。これらの簡略化された方程式は、効率的な検索のためにいくつかの優れた言語でプログラムするか、または抽象的に再度処理して、一度に1ビットを割り当て、矛盾に注意することができます。出力が入力と一致していないことを知るには、出力の数ビットを確認するだけで済みます。

于 2009-05-23T01:40:10.463 に答える
-1

おそらくですが、それを見つけるには、私たちが持っているよりも時間がかかるか、MD5 を侵害する必要があります.

于 2008-10-25T02:24:03.023 に答える
-8

2 つの解釈があり、どちらかを選択できる場合、不動点を見つける確率は 81.5% に増加します。

  • 解釈 1:バイナリの MD5 出力の MD5 はその入力と一致しますか?
  • 解釈 2: 16 進数の MD5 出力の MD5 はその入力と一致しますか?
于 2009-05-06T15:32:34.790 に答える
-23

MD5は入力が512ビット長で出力が128ビット長なので、厳密にはそれはありえないと言えます。

于 2009-05-06T15:29:02.520 に答える