Birthday Problem & Attack

n명의 사람이 있을 때 생일이 같은 사람이 둘 이상 있을 확률이 p(n)이면,

이를 적어도 1명도 겹치지 않을 확률로 바꿀 수 있으므로

이고, 

이다.

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

---

Birthday Attack

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

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

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

 : 총 가짓수 ( 365일 )

  : 시도 횟수 ( 사람 수 )

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

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