Post

Birthday Problem & Attack

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

\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}

이고,

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

이다.

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


Birthday Attack

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

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

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

H: 총 가짓수 ( 365일 )

n: 시도 횟수 ( 사람 수 )

{\displaystyle n(p;H)\approx {\sqrt {2H\ln {\frac {1}{1-p}}}}}

{\displaystyle p=0.5}일 때,{\displaystyle n(0.5;H)\approx 1.1774{\sqrt {H}}}라는 간단한 식이 나온다.

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

This post is licensed under CC BY 4.0 by the author.