数理的解説とは？ わかりやすく解説

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/01 16:19 UTC 版)

「誕生日攻撃」の記事における「数理的解説」の解説

詳細は「誕生日のパラドックス」を参照 次のような実験を考える。 H {\displaystyle H} 個の値の集合から n {\displaystyle n} 個の値を一様かつ無作為に選ぶ（重複もありうる）。この実験で少なくとも1つの値が2回以上選ばれる確率を p ( n ; H ) {\displaystyle p(n;H)} とする。この確率は次のように概算できる。 p ( n ; H ) ≈ 1 − e − n ( n − 1 ) / ( 2 H ) ≈ 1 − e − n 2 / ( 2 H ) {\displaystyle p(n;H)\approx 1-e^{-n(n-1)/(2H)}\approx 1-e^{-n^{2}/(2H)}} 衝突を発見する確率を p {\displaystyle p} 以上とするとき、行わなければならない試行回数の下限を n ( p ; H ) {\displaystyle n(p;H)} とする。すると、上の式から次のような近似が得られる。 n ( p ; H ) ≈ 2 H ln ⁡ 1 1 − p {\displaystyle n(p;H)\approx {\sqrt {2H\ln {\frac {1}{1-p}}}}} 衝突発生確率を0.5とすると、次のようになる。 n ( 0.5 ; H ) ≈ 1.1774 H {\displaystyle n(0.5;H)\approx 1.1774{\sqrt {H}}} 最初の衝突が発生するまでに行わなければならない試行回数を Q ( H ) {\displaystyle Q(H)} とする。この近似は次のようになる。 Q ( H ) ≈ π 2 H {\displaystyle Q(H)\approx {\sqrt {{\frac {\pi }{2}}H}}} 例えば、64ビットの暗号学的ハッシュ関数を使っている場合、約 1.8 × 1019 個の異なる出力がありうる。これらが全て同じ確率で発生する場合（最良ケース）、約 5.1 × 109 回の試行で衝突を発生させることができる。この値を birthday bound と呼び、n-ビットの符号についての birthday bound は 2 n / 2 {\displaystyle 2^{n/2}} となる。他の例は次のようになる。 ビット数出力の個数(H)衝突発生確率 (p)10−1810−1510−1210−910−60.1%1%25%50%75%32 4.3 × 109 2 2 2 2.9 93 2.9 × 103 9.3 × 103 5.0 × 104 7.7 × 104 1.1 × 105 64 1.8 × 1019 6.1 1.9 × 102 6.1 × 103 1.9 × 105 6.1 × 106 1.9 × 108 6.1 × 108 3.3 × 109 5.1 × 109 7.2 × 109 128 3.4 × 1038 2.6 × 1010 8.2 × 1011 2.6 × 1013 8.2 × 1014 2.6 × 1016 8.3 × 1017 2.6 × 1018 1.4 × 1019 2.2 × 1019 3.1 × 1019 256 1.2 × 1077 4.8 × 1029 1.5 × 1031 4.8 × 1032 1.5 × 1034 4.8 × 1035 1.5 × 1037 4.8 × 1037 2.6 × 1038 4.0 × 1038 5.7 × 1038 384 3.9 × 10115 8.9 × 1048 2.8 × 1050 8.9 × 1051 2.8 × 1053 8.9 × 1054 2.8 × 1056 8.9 × 1056 4.8 × 1057 7.4 × 1057 1.0 × 1058 512 1.3 × 10154 1.6 × 1068 5.2 × 1069 1.6 × 1071 5.2 × 1072 1.6 × 1074 5.2 × 1075 1.6 × 1076 8.8 × 1076 1.4 × 1077 1.9 × 1077 この表は、指定した確率で衝突を発生させるのに必要な試行回数を示している（各ハッシュ値の発生確率は等しいと仮定）。ちなみに 10−18 から 10−15 は一般的なハードディスクで訂正できないビット誤りが発生する確率である。したがって、128ビットのMD5を文書のチェックサムとして使用する場合、8200億個の文書までならハードディスクでの誤り発生確率の範囲内に収まると言える（実際にはもっと多数のハッシュ値を生成できる）。 関数の出力が一様に分布しない場合、衝突をもっと早く見つけられることは容易に想像がつく。ハッシュ関数の「バランス」の観念は、誕生日攻撃への関数の耐性を定量化し、MDやSHAなどのよく知られたハッシュの脆弱性を見積もることを可能にする。

※この「数理的解説」の解説は、「誕生日攻撃」の解説の一部です。
「数理的解説」を含む「誕生日攻撃」の記事については、「誕生日攻撃」の概要を参照ください。