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 )를 사용한 듯.


'Security > Crypto-PKCS' 카테고리의 다른 글

John the ripper  (0) 2016.12.25
Block cipher mode of operation  (0) 2016.11.25
동기식, 비동기식 stream cipher  (1) 2016.11.18
PKCS ( Public Key Cryptography Standards )  (0) 2016.09.14
Base64 Radix64  (0) 2016.08.31