バースデイ・パラドックスと情報セキュリティ
本記事では，バースデイ・パラドックスについて解説したいと思います．
ここで言うパラドックスとは，直感に反する事実を意味しています1論理学的な逆説ではない．．
バースデイ・パラドックスは，誕生日に関する確率の問題です．初めにバースデイ・パラドックスの面白さについて知ってもらい，次に情報セキュリティにおける重要性について簡単に触れたいと思います．
自分と同じ誕生日の人がいる確率は？
問題．
あなたは40人のクラスに所属している．あなたと同じ誕生日の人が同じクラスにいる確率を求めよ．ただし，1年は365日とし，365日どの日も等確率で誕生日になり得るとする2実際の誕生日の分布には偏りがあります．こちらのサイトの記事などを見ると，偏りの大きさが分かるかと思います．
自分を除いたクラスの人数は39人なので，余事象「自分と同じ誕生日の人が一人もいない」を使って，
\begin{aligned}
1 - \left( \frac{364}{365} \right)^{39} \fallingdotseq 0.1014706896664328
\end{aligned}
同じ誕生日の人がいる確率は？
次の問題は，答えを予想してから解いてみましょう．
問題．
40人のクラスに同じ誕生日の人が少なくとも1組いる確率を求めよ．ただし，1年は365日とし，365日どの日も等確率で誕生日になり得るとする．
1から余事象「同じ誕生日の人は一人もいない」の確率を引いて，
\begin{aligned}
1 - \frac{365}{365} \cdot \frac{364}{365} \cdot \cdots \cdot \frac{326}{365} \\
= 1 - \frac{365!}{365^{40}(365-40)!} \\
\fallingdotseq 0.8912318098179489
\end{aligned}
予想より高い確率になった人が多いのではないでしょうか．
これがバースデイ・パラドックスと呼ばれるものです．
同じ誕生日の人がいる確率が0.5を超えるのに何人必要？
問題．
同じクラスの同じ誕生日の人が少なくとも1組いる確率が0.5を超えるためには，最低何人必要か求めよ．
22人のとき，
\begin{aligned}
1 - \frac{365}{365} \cdot \frac{364}{365} \cdot \cdots \cdot \frac{344}{365} \\
= 1 - \frac{365!}{365^{22}(365-22)!} \\
\fallingdotseq 0.475695307662550
\end{aligned}
23人のとき，
\begin{aligned}
1 - \frac{365}{365} \cdot \frac{364}{365} \cdot \cdots \cdot \frac{343}{365} \\
= 1 - \frac{365!}{365^{23}(365-23)!} \\
\fallingdotseq 0.5072972343239854
\end{aligned}
よって，23人のときに確率が0.5を超える．
ハッシュ関数
任意の長さのビット列を入力すると，一定の長さのビット列を出力する関数です．
入力の長さは任意ですが，出力は固定長のビット列となります．この出力のことをハッシュ値と言います．出力から入力を復元できないことが特徴であり，不可逆な変換を行います．そこが暗号とハッシュ関数の大きな違いです．
ハッシュ関数は，情報科学の様々な分野で使われる関数です．
情報セキュリティの場合ですと，文書やソフトウェアなどが本物であるか確かめる，つまりデータの改竄が無いかを確かめるために使われます．
さて，ハッシュ関数には幾つかの満たしておくべき性質があります．その中のひとつが衝突困難性です．衝突困難性とは，同じハッシュ関数に関して，同じハッシュ値となる2つの入力を見つけることの困難さのことです．入力が任意の長さなのに対して，出力の長さは固定なので，ハッシュ値が被ることも当然起こります．ここでバースデイ・パラドックスの話に戻りますが，同じ出力の2つの入力を見つけられる確率は，想像よりも高いことが分かります．
それでは，同じ出力をする2つの入力を見つけるとどのような問題が生じるのか見てみましょう．
同じ出力のデータを利用した攻撃
攻撃の一例を大雑把に説明したいと思います．
設定を説明します．Aさんは文書に，Bさんのデジタル署名をもらいます．文書はハッシュ値によって真贋を判定しているとします．ところがAさんは同じハッシュ値の異なる文書を持っています．一方は良い文書，もう一方は悪い文書です．Aさんの目的は，Bさんを騙して悪い文書にデジタル署名をもらうことです．
さて，それでは攻撃開始です．
AさんはBさんに良い文書を渡して内容を確認してもらいます．Bさんの了承を得られたら，今度は良い文書と悪い文書をすり替えて，悪い文書をBさんに送ります．ハッシュ値は同じなので，Bさんは文書の確認をしない限り，データの改竄に気付きません．Bさんが文書のすり替えに気付かなかった場合，Bさんは悪い文書にデジタル署名をしてしまいます．こうして，Aさんの目的は無事に達成されました．
終わりに
バースデイ・パラドックスは，グループの中に同じ誕生日の人がいる確率が，想像よりも高いというものでした．これだけでも面白いですが，この直感に反する現象が，情報セキュリティでも重要になってきます．今回は僅かな例しか挙げられませんでしたが，数学が様々な形で別分野と繋がっていることを感じてもらえたなら幸いです．
ちなみに，誕生日の偏りを考慮したパースデイ・パラドックスを考えている人がいました．気になる方は，下のリンク先を読んでみてください．
https://qiita.com/HMMNRST/items/8cf920702f2fb1e1e575
