ハッシュ衝突確率（誕生日攻撃）の計算
ハッシュ値のビット長と生成回数を入れると、誕生日攻撃の近似式で衝突確率を計算します。衝突する確率がちょうど50パーセントになる生成回数のめやすも出します。
ビット
例：MD5は128、SHA-1は160、SHA-256は256ビットです
回
計算方法
ハッシュ値のビット長をHとすると、取りうる値の数は2のH乗です。誕生日攻撃は、ランダムな入力を繰り返し試し、同じハッシュ値が出る組を探す攻撃で、衝突確率は次の近似式で求めます。
衝突する確率 ＝ 1 − eの（マイナス生成回数 ×（生成回数 − 1）÷（2 × 2のH乗））乗
確率がちょうど50パーセントになる生成回数のめやすは、次の式でも近似できます。
50パーセントになる回数 ＝ 2のH乗 × 2 × 0.693 の平方根
例：128ビットのハッシュでは、約2.2 × 10の19乗回ためすと衝突確率が50パーセントに近づきます。総当たりで鍵そのものを探す攻撃（2のH乗回が必要）より、はるかに少ない回数で済むのが誕生日攻撃の特徴です。
出典：式の定義（誕生日攻撃の近似式。ハッシュ長と生成回数は入力した値を使います）
PR
よくある質問
なぜ鍵の全数探索より少ない回数でぶつかる？
誰かと誰かがぶつかればよい「ペアを探す」問題だからです。n個の中から2つを選ぶ組み合わせの数はおおよそnの2乗に比例して増えるため、2のH乗より小さいnでも十分な組み合わせ数になります。
SHA-256なら安全？
このツールの式で計算すると、256ビットのハッシュで衝突確率が無視できないほど大きくなるには、現実的な時間では試せないほどの回数が必要です。ただし、ハッシュ関数自体に設計上の弱点が見つかった場合は、この理論値より少ない回数で衝突する場合があります。
パスワードのハッシュ化とは関係ある？
誕生日攻撃は、同じ入力を探す「原像攻撃」とは別の考え方です。パスワードのハッシュ化では、ソルトを使って同じパスワードでも異なるハッシュ値になるようにする対策が別に必要です。