Birthday Problem & Attack

n명의 사람이 있을 때 생일이 같은 사람이 둘 이상 있을 확률이 p(n)이면, 이를 적어도 1명도 겹치지 않을 확률로 바꿀 수 있으므로

이고,

이다.

p(n) = 0.5일 때 n은 22.xxx이므로 23명 이상일 때 p(n)은 50% 이상이 된다.

---

Birthday Attack

암호학적 해시 함수의 해시 충돌을 찾아내기 위해 몇 번의 시도가 필요한지를 알아내기 위한 방법이다.

실제 birthday attack에서는 가짓수가 365가 아닌 2^24 등 매우 큰 수인데, factorial ( 계승 ) 을 사용하면 계산이 어렵다.

따라서 적당히 approximation시켜 사용한다.

: 총 가짓수 ( 365일 )

: 시도 횟수 ( 사람 수 )

일 때,라는 간단한 식이 나온다.

factorial 근사는 스털링 근사(Sterling approximation)를 사용한 듯.