생일 문제

모인 사람 수에 따라 생일이 같은 두 사람이 있을 확률이 얼마나 되는지를 보이는 그래프. 가로축이 사람 수,그리고 세로축이 확률을 나타낸다. 23명이 모였을 때 확률이 0.5를 넘어감을 보여 준다.

생일 문제(生日問題)란 사람이 임의로 모였을 때 그 중에 생일이 같은 두 명이 존재할 확률을 구하는 문제이다. 생일의 가능한 가짓수는 365개(2월 29일을 고려할 경우 366개)이므로 366명 이상의 사람이 모인다면 비둘기집 원리에 따라 생일이 같은 두 명이 반드시 존재하며, 23명 이상이 모인다면 그 중 두 명이 생일이 같은 확률은 1/2를 넘는다.

생일 문제는 일반적인 인간의 직관과 다른 결과를 가지는 것으로 알려져 있다. 얼핏 생각하기에는 생일이 365가지이므로 임의의 두 사람의 생일이 같을 확률은 1/365이고, 따라서 365명쯤은 모여야 생일이 같은 경우가 있을 것이라고 생각하기 쉽다. 그러나 실제로는 23명만 모여도 생일이 같은 두 사람이 있을 확률이 50%를 넘고, 57명이 모이면 99%를 넘어간다.

생일이 같은 두 사람을 찾는 것과 비슷하게, 암호학적 해시 결과가 같은(해시 충돌) 두 입력값을 찾는 것 역시 모든 입력값을 계산하지 않아도 충분히 높은 확률로 해시 충돌을 찾을 수 있다. 이러한 암호 공격을 생일 공격(birthday attack)이라고 부른다.

확률 계산

만약 366명 이상의 사람이 있다면 비둘기집 원리에 따라 생일이 같은 두 사람이 존재해야 한다. 365명 이하의 사람이 있을 경우를 계산한다. $n$명의 사람이 있을 때 그 중 생일이 같은 사람이 둘 이상 있을 확률을 $p(n)$이라고 한다면, 반대로 모든 사람의 생일이 다를 확률 $\bar p(n)$은 $1-p(n)$이 된다. 먼저 $\bar p(n)$을 구해보면, 두 번째 사람의 생일은 첫 번째 사람과 다르고, 세 번째 사람의 생일은 첫 번째와 두 번째 모두와 달라야 하므로 다음과 같은 식을 얻을 수 있다.

$\begin{align} \bar p(n) &= 1 \times \left(1-\frac{1}{365}\right) \times \left(1-\frac{2}{365}\right) \cdots \left(1-\frac{n-1}{365}\right) \\ &= { 365 \times 364 \cdots (365-n+1) \over 365^n } \\ &= { 365! \over 365^n (365-n)!} \end{align}$

가 되고, 최종적으로 구하고자하는 생일이 같은 사람이 둘 이상 있을 확률 $p(n)$은

$\begin{align} p(n) &= 1 - { 365! \over 365^n (365-n)!} \end{align}$

가 된다. 여기서, n≤365 인 자연수이고, !는 계승을 의미한다.

이 $p(n)$값을 특정 n 값에 대해 계산하면 다음과 같다.

n	p(n)
10	12%
20	41%
30	70%
50	97%
100	99.99996%

즉, 50명만 모이면 그 가운데 2명 이상의 생일이 같을 확률이 97%이고, 100명이 모이면 거의 1에 가까워진다는 것을 알 수 있다.