バースデーパラドックスが実証されました

こんにちは！

ミステリー作品が好きなM1のケンフィーです。コナンはもちろん、最近のドラマや映画では、「臨床犯罪学者火村英生の推理」「そして誰もいなくなった」「リバース」「僕だけがいない街」「22年目の告白-私が殺人犯です-」が良かったです。今は「愛したって秘密はある」が気になっています。


さて今回は研究室のブログらしい真面目な話をしようと思います。

研究室のキャンプの出欠確認の集計をしていたときのことです。
出欠確認で生年月日も記入してもらいましたが、この事実に気が付きました。

僕たちの研究室で、同じ誕生日の人がいる！！！


つい先日、数理暗号論という講義で「バースデーパラドックス」という話題が出てきたこともあり、「あー！このことかっ」って心の中で叫んでしまいました(笑)「バースデーパラドックス」が何のことか分からない人も多いと思いますので、以下に簡単に解説します。

■□■□■□■□■□■□■□

まず誕生日が同じになる確率は、1/366。（2/29を含む）

これは確率的に367人以上集めてこれば、必ず誕生日が一致することを表しています。では、50%の確率で誕生日が一致するためには何人以上必要でしょうか？ちなみに、確率論的に50％というのは、体験的に、その事象が起こりやすいと分かる確率です。

一見、367人の半分の187人以上だと考えると思いますが、バースデーパラドックスとは、その直感と反して、かなり少数でも50％の確率が一致するというものです。つまり、誕生日だと、√367≒20人以上集まれば、50％の確率で一致するということになります。

今は誕生日の話をしていますが、このパラドックスは学術的にも応用されています。どの分野で応用されているかというと、離散数学を扱う情報系や通信系で使われています。今回は暗号技術で、バースデーパラドックスがどのように使われているか紹介したいと思います。

まず暗号技術では、モデュロ計算（mod，剰余計算）を使った循環輪を活用します。

例えば、mod13において、等比数列を考えると、

2⇒4⇒8⇒3⇒6⇒12⇒11⇒9⇒5⇒10⇒7⇒1⇒2⇒……
（2の5乗は32ですが、mod13すなわち13で割った余りを取ると、6になります。）

と1～12までの12個の数字が離散的に繰り返されます。（簡単に解読されないためにRSA暗号だと4000個、ECC(楕円曲線)暗号だと200個以上の循環輪が使われます）

暗号では、例えば、2（平文）を7乗して（＝11）、それを暗号文として相手に渡し、受け取った人は、(13-7)乗して平文に戻します（＝復号）。このとき重要なのは、何回かけたか（今の場合7）を第3者に知られないことです。もし、この数字が知られてしまうと、解読されてしまいます。

攻撃者は、入手可能な情報（暗号文や暗号化に必要な情報）を使って、何回かけたか（ECC暗号の場合は何回足したか）を特定しようとします。その手法の一つとして、入手可能な情報を使って、離散的な数字を生成し、数字が一致させて解く攻撃手法があります。

ここで、登場するのが「バースデーパラドックス」です。現在、簡単に解読されないために長い循環輪が利用されています。しかし、どんなに大きな個数の数（nとおく）を使ったとしても、50％の確率で、生成した数字が少し前に生成した数字と一致して、解読するためには、√n個の数字を生成すればよくなります。攻撃するコンピュータは、生成した数字を保存して、新たに生成する数字と比較する必要がありますが、バースデーパラドックスに基づけば、保存する個数は少なく済み、少ないストレージのスペックで十分ということになります。

・・・・・・・・・・・・

現在、スマートフォンが普及し、セキュリティ上の脅威も日々増しています。僕自身、将来的にスマートフォンで仕事をする人が増え、パソコンがクリエイターや研究者、技術者などの専門的なツールになっていくのではないかと考えています。そうなると、暗号技術や暗号数学といった分野もある程度理解していないと、攻撃者に狙われやすくなるような、そんな時代に突入するかもしれませんね。



■□■□■□■□■□■□■□

暗号技術について、もっと知りたい方は
数学が支える情報通信のセキュリティ| 岡山大学 野上 保之 准教授 | 夢ナビTALK