🎲

ハッシュ値が衝突する確率について

2021/08/09に公開3

はじめに

あるデータから一意の値を取得する際に、よくハッシュ値を取る方法が使われる。
その際、衝突する確率がどのくらいなのか気になったので調べてみた。

今回考えること

SHA256 によってハッシュ値を取ることを想定する。この際、 SHA256 が取る値は一様にランダムとする。
ある特定の SHA256 のハッシュ値になる確率(1/2^{256})がどのくらいかを他の確率的な事象で比較する。

確率の比較

事象 2の累乗表記 10の累乗表記 %表示
ロイヤルストレートフラッシュ 1/2^{16.0} 1/10^{4.83} 1.48*10^{-3} %
天和 1/2^{18.3} 1/10^{5.52} 3.03*10^{-4} %
2択20問のテストででたらめ回答で0点 1/2^{20.0} 1/10^{6.02} 9.54*10^{-5} %
宝くじ一等 1/2^{23.2} 1/10^{7.00} 1.00*10^{-5} %
何もせず6Vが生まれる(ポケモンの話) 1/2^{30.0} 1/10^{9.03} 9.31*10^{-8} %
天和四暗刻大四喜字一色 1/2^{49.7} 1/10^{15.0} 1.08*10^{-13} %
センター国語(2020)で適当回答で満点 1/2^{79.6} 1/10^{24.0} 1.12*10^{-22} %
40人クラスの席替えが席替えにならない 1/2^{159} 1/10^{47.9} 1.23*10^{-46} %
54枚のトランプが購入時の並び順になる 1/2^{237} 1/10^{71.4} 4.33*10^{-70} %
100個のサイコロ振ってゾロ目 1/2^{255.911} 1/10^{77.0} 9.18*10^{-76} %
SHA256 が衝突する 1/2^{256} 1/10^{77.1} 8.64*10^{-76} %
※もしかすると間違っているかもしれないが悪しからず

上記の計算結果から、衝突する確率は100個のサイコロを振ってゾロ目が出る確率とほぼ同じと言うことがわかった。

実際にサイコロ100個振ってみた

100個のサイコロを準備した。

それを手にもって振る!

その結果...




































全部ピンじゃねぇかっ・・・!

.
.
.
.
.
.
.
.
.
.
.

まぁ、そんなわけないよね。

あとがき

サイコロ100個振りたかっただけ。

Discussion

スミス祐一郎ルークスミス祐一郎ルーク

面白い記事をありがとうございます!ハッシュ値の衝突が話題になる時って、あるハッシュ値が次に生成したハッシュ値と衝突する確率(1/2^256)の他に、沢山ハッシュ値を生成した場合にその中に衝突している組が存在する確率(誕生日のパラドックスで直感よりも高い値になる)を考える場合が多いので、この記事で触れていただくとどのあたりになるのかなーと気になりました!(母数によって確率は変わるので簡単には表に載せにくいとは思うのですが、、)