誕生日のパラドックス（たんじょうびのパラドックス）とは「何人集まれば、その中に誕生日が同一の2人（以上）がいる確率が、50%を超えるか?」という問題から生じるパラドックスである。鳩の巣原理より、366人（閏日も考えるなら367人）集まれば確率は100%となるが、しかしその5分の1に満たない70人が集まれば確率は99.9%を超え、50%を超えるのに必要なのはわずか23人である。誕生日のパラドックスは論理的な矛盾に基づいているという意味でのパラドックスではなく、結果が一般的な直感と反しているという意味でのパラドックスである。この理論の背景には によって記述された「湖にいる魚の総数の推定」がある。これは、統計学では 法として知られている。上記の確率を求める問題やその類似問題は、誕生日問題とよばれる。部屋に22人の人間がいる。あなたがその部屋に入ったときに、「あなたと同じ」誕生日の人がいる確率は50％ではない。その確率はずっと低い。これは、「あなた以外の人」同士の誕生日が同じであるという可能性は考慮されないからである。それでは、"n"人の中で同じ誕生日の人が少なくとも2人いる場合の確率を計算する。閏年や双子は考えないものとし、誕生日は365日とも等確率であるとする。まずは、"n"人の誕生日が全て異なる場合の確率 "p" を計算する。2人目が1人目と異なっている誕生日である確率は、364/365 である。次に、3人目が1人目2人目と異なる誕生日である確率は 363/365 である。同様に4人目は 362/365、…、"n"人目は (365-"n"+1)/365 となる。つまり、"n"人の誕生日が全て異なる確率は次のようになる。よって、"n"人の中で同じ誕生日の人が少なくとも2人いる場合の確率 "p" は、となり、"n" = 23 のとき、"p" = 0.507… となる。一方、先ほどの、"n"人の部屋に"あなた"が入ったときに、あなたと同じ誕生日の人がいる確率 "p" は、となる。"n" = 23 ならば、"p" = 0.0611… である。"n" が 253 のときに初めて "p" が 0.5 以上となる。この誕生日問題の考え方は、誕生日攻撃と呼ばれる暗号システムへの攻撃法に利用されている。ハッシュ値がNビットの理想的な暗号学的ハッシュ関数があるとする。このとき、あるハッシュ値となるメッセージを探し出す原像攻撃が成功する試行回数の期待値は2/2である。それと比べて、同一のハッシュ値となる2通の異なるメッセージを探し出す衝突攻撃（誕生日攻撃）が成功する試行回数の期待値は、誕生日のパラドックスによって2でありずっと小さい。このことは、暗号学的ハッシュ関数の使用目的にてらしあわせて、必要なハッシュ値の大きさに注意しなければならないことを意味している。原像攻撃に対する耐性が「弱衝突耐性」、誕生日攻撃に対する耐性が「強衝突耐性」である。ブロック暗号アルゴリズムをCTRモードで使用した擬似乱数生成器は、ブロック長をLとしたときに、2程度のブロック分の乱数出力を行うと1/2の確率で真の乱数と区別できる。真の乱数は誕生日のパラドックスから、2ブロック分の乱数の中に同じ値を持つブロックが約1/2の確率で存在する。一方でCTRモードはカウンタが同じ値に戻らないことから同じ値を持つブロックは存在しない。

出典:wikipedia