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시켜 사용한다.
factorial 근사는스털링 근사(Sterling approximation)를 사용한 듯.
This post is licensed under CC BY 4.0 by the author.