md5 - 2^32 セットの文字列を渡した場合、md5 衝突の確率はどのくらいですか?

Question

2^32 セットの文字列を渡した場合、md5 衝突の確率はどのくらいですか?

md5 ハッシュのビット長が 128 であるため、答えは 2^32/2^128 = 1/1.2621774e-29 と言えますか?

Answer 1

この質問は、いわゆる「誕生日のパラドックス」に似ています。

確率論では、誕生日の問題または誕生日のパラドックスは、ランダムに選択されたn人のセットで、それらのペアの一部が同じ誕生日を迎える確率に関係します。鳩の巣原理によ​​り、人数が367人に達すると確率は100％になります（2月29日を含めて366人の誕生日が考えられるため）。ただし、わずか57人で99％の確率に達し、23人で50％の確率に達します。これらの結論は、1年の各日（2月29日を除く）が同じように誕生日になる可能性があるという仮定に基づいています。

この問題の背後にある数学は、誕生日攻撃と呼ばれるよく知られた暗号化攻撃につながりました。これは、この確率モデルを使用して、ハッシュ関数のクラッキングの複雑さを軽減します。

ウィキペディアの記事によると、d = ^{2128個の数字のスペースから}n =2 ^32個の乱数を選択した場合の衝突の可能性は、おおよそ次のとおりです。

この計算を実行すると、確率は約2.7× ^10-20になります。これは非常に小さな確率ですが、提案された計算よりも9桁高いことに注意してください。