생일 패러독스, 생일 공격
$n$명의 사람이 있다. 이 사람들의 생일이 모두 다를 확률은 얼마나 될까? $$ \prod_{i=1}^{n-1} \left( 1 - \frac{i}{365} \right) $$ 이다. 이 경우 $n = 23$만 되어도 이미 확률이 절반 이하가 된다. 생각보다 적은 수의 사람이 모여도 꽤 높은 확률로 생일이 같은 두 사람을 찾을 수 있다는 것이 생일 패러독스이다. 이를 이용하여 충돌쌍 하나를 효과적으로 구하는 암호론적 공격이 생일 공격이다. 해시함수의 충돌값을 찾거나, 블록암호를 공격할 때 사용된다. Factoring 문제를 효과적으로 푸는 Pollard's rho 랜덤 알고리즘도 똑같은 원리를 기반으로 한다. 특히 블록암호에서 어떤 함수 $G$에 대해 $G(x) = G(y)$인 서로 다른 문자열 $x,..
