誕生日攻撃

誕生日攻撃（たんじょうびこうげき、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> 回である。