Birthday Paradox

文 :
Write :

パラドックス (Paradox) とは，一見筋が通ってるように見えるのに，実は矛盾が生じてたりする事柄を示します．

また，数学的な結論が，逆に直感とはかけ離れてる事柄を表したりもします．Zeno's paradoxes (ゼノンのパラドックス) などが有名です．

Birthday Paradox は元々数学のジャンルですが，通信業界，特に暗号化技術，セキュリティの分野で使われるパラドックスです．

何人かのグループが居るときに，同じ誕生日のペアが居る確率はどれくらいだと思いますか？反対に，例えば同じ誕生日のペアが居る確率が50%，あるいは90%，99%になるには，グループは何人居ればいいと思いますか？

ここでは，うるう年は考えず，1年を365日とします．また，月ごとの出生率のバラつきも考えません．

1年は365日なので，かなりの人数が居ないと，ペアは居ない気がすると思います．実際に計算して見ましょう．

例えば，2人のグループで，同じ誕生日のペアが居る確率はどれくらいになるでしょうか．

これは，1人目の誕生日が決まっているので，もう1人が異なる誕生日である確率は，

と求まります．つまり，逆を返すと，もう1人も同じ誕生日である確率は，

と，なります．

これを，3人のグループ，4人のグループ，と人数を増やしていくと，

つまり，23人のグループで，同じ誕生日のペアが居る可能性が50%を超えることが分かります．

数式で書いてると面倒なので，プログラムにやらせてしまいます．Perlで簡単に書いてみると，

#!/usr/bin/perl

$p = 1;
for ($i = 0; $i < 365; $i++) {
  $p = $p * ((365 - $i) / 365);
  printf("%3d : %3.1f%%\n",  $i + 1, (1 - $p) * 100);
}

のようにして求める事ができます．

このプログラムを実行してみると，23人のグループで50.7%，41人のグループで90.3%，57人のグループで99.0%と分かります．

57人の後は確率はゆっくり増加し，366人で100%になります．(上記プログラムは精度の問題で，もっと早く100%が出てしまいます)

なぜ，Birthday Paradoxが通信業界で使われるかというと，暗号化や電子署名で使われるハッシュ関数に対する攻撃で，Birthday Attackという方法があります．Birthday AttackはBirthday Paradoxと同じ原理に基づいています．

詳細は割愛しますが，メッセージダイジェストを得るハッシュ関数の潜在的な弱点を攻撃する事で，偽のメッセージに対し，正式な電子署名を施すことができます．

数学的には，ハッシュ関数の出力の長さが短いと，思ったより簡単に任意のメッセージダイジェストの組が得られてしまうため，現在では128bit(MD5など)や160bit(SHA)などの，出力の長さをある程度取ったハッシュ関数が用いられます．