「誕生日攻撃」の版間の差分

m
編集の要約なし
m
'''誕生日攻撃'''(たんじょうびこうげき、[[英語|英]]: birthday attack)は、[[暗号理論]]における暗号攻撃方法の1つ。[[確率論]]における[[誕生日のパラドックス|誕生日問題]]の背後にある数学的理論を利用することからこの名称になっている。関数 ''f'' があるとき、この攻撃の目的は <math>f(x_1)=f(x_2)</math> となるような2つの異なる入力 <math>x_1,x_2</math> を求めることである。この <math>x_1,x_2</math> のような組合せを[[衝突 (計算機科学)|衝突]]と呼ぶため、'''衝突攻撃'''ともいう。
 
衝突を見つける方法は、無作為または擬似乱数的に生成した異なる複数の入力を関数 ''f'' に与えて評価し、複数回同じ値となるまで続けるだけである。前述した誕生日問題から、この方法は思ったより効率的である。特に[[関数 (数学)|関数]] <math>f(x)</math> が <math>H</math> 個の異なる出力をそれぞれ同じ確率で生成し <math>H</math> が非常に大きい場合、<math>f(x_1) = f(x_2)</math> となるような異なる入力 <math>x_1</math> と <math>x_2</math> を得るまでに ''f'' を評価する回数の平均は約 <math>1.25 \cdot \sqrt H</math> 回である。
69

回編集