9

MD5ハッシュ文字列よりも多くの文字列が宇宙にあるため、MD5が一意性を保証できないという証拠があることは理解していますが、有限数の文字列の逆証明はありますか?

基本的に、最大長 X の文字列がある場合、MD5 が一意であることが保証されている X はありますか? はいの場合、その X は何ですか? また、X に複数の値がある場合、X の最大値はいくつですか?

または、他のハッシュアルゴリズム、SHA-1などにそのようなXはありますか?

4

2 に答える 2

2

ここで優れた回答を要約すると、MD5 衝突を引き起こす最も短い文字列のペアは何ですか?

MD5 に対する既知の最短の攻撃では、2 つの入力ブロック、つまり 128 バイトまたは 1024 ビットが必要です。

N ビットを出力する任意のハッシュ アルゴリズムの場合、入力をほぼランダムに分散すると仮定すると、約sqrt(2^N)入力で衝突の可能性が 50% を超えると想定できます。たとえば、MD5 は 128 ビットにハッシュされるため、すべての 64 ビット入力間で衝突が予想されます。これは、均一にランダムなハッシュを想定しています。弱点があると、衝突が発生すると予想される前に入力の数が減少します。

于 2012-05-15T03:50:58.797 に答える
1

あなたの質問への答えはイエスです。どのハッシュ関数にも、一意の文字列が返される最大長 X があります。ただし、X を見つけるのは非常に難しい場合があります。アイデアは、このプログラムを実行することです：

X= 0;
For i = 0 onward
   For all strings of length i
      Compute the hash code of that string.
      If a collision is found, return X.
   X = i

アイデアは、ハッシュの衝突が見つかるまで、ますます長い文字列をリストすることです。最終的には、可能なハッシュ出力よりも多くの文字列を生成するため、最終的にはそうする必要があります。

予想通り、ハッシュ関数が実際にはかなりランダムであると仮定すると、衝突を見つける前に O(√U) 個の異なる文字列を生成する必要があります。ここで、U はハッシュ関数がマップする空間のサイズです。256 ビット ハッシュの場合、これは 2 256です。これは、実際には、ハッシュ関数がかなり壊れていない限り、上記のプログラムが実際に終了することは決してないことを意味しますが、理論的には、数値 X が存在することを意味します。

お役に立てれば！

于 2012-05-15T03:47:39.573 に答える