language-agnostic - md5 を使用して衝突の可能性を計算するにはどうすればよいですか?

Question

1 から 256 文字の間で長さが変化するキーがあります*。md5を使用しているときに任意の 2 つのキーが衝突する確率を計算するにはどうすればよいですか(各キーを試行するブルート フォース ソリューションをむき出しにします)。

*文字セットはに制限されています[a-z.-]

Answer 1

これを分析するのに役立つ誕生日のパラドックスを見てみましょう。つまり、MD5 は 128 ビットのハッシュであるため、衝突の可能性が 50% に上昇するには2 ^{64 個のアイテムが必要です。}MD5 がその 128 ビット空間に均等に分散されているという仮定があります。

これらの数値がキー空間に対してどのように積み上げられるかを知りたい場合は、すべてのキーが 256 文字であり、26 ²⁵⁶の可能なキー、つまり 2 ¹⁰²³があり、もちろん、後で衝突する可能性が 100% あると仮定しましょう。 2 ¹²⁸キー :)

Answer 2

誕生日問題をチェックしてください。それはまさにあなたが探しているものです。