Birthday Paradox

Birthday Paradox에 대해서는 많은 사람들이 올린 글이 있으니 그거 참고하면 더 자세히 나와있겠지만..

참 신기한듯 -_-

모임이 있는데, 각 모임에 있는 사람 중에서 나하고 같은 생일을 가질 사람이 있을 확률이 50%가 넘기 위해서 필요한 사람은 몇명인가가 Birthday Paradox의 문제이다.

딱 보면 진짜 적을거 같은데.. 보니까 그게 아니더라 이거지.

기본적으로, 수업시간에 배운 것에 기반하면
P0 : 모든 사람이 생일이 다 다를 확률
P1 : 1-P0, 즉 문제에서 구하고자 하는 나하고 같은 생일을 가질 사람이 되기 위한 확률

사람이 k명 있고, 생일의 전체 수를 n이라 했을때.. (n=365인건 뻔하지만 좀이따 다룬다)
P0 = 1 * (1-1/n) * (1-2/n) * ... * (1-(k-1)/n)
이란다.
이게 뭔소린가 했는데..
알고 보니까 모든 사람이 생일이 다 다를 확률 해가지고 나온건데..
내가 제대로 이해했는지는 모르겠는데, 일단 써보면..

첫번째 사람은 나고,
두번째 사람은 1-1/n 으로 그 사람이 1번째 사람하고 생일이 같을 확률을 배제한 확률
세번째 사람은 1-2/n 으로 그 사람이 1, 2번째 사람하고 생일이 같을 확률을 배제한 확률
...
k번째 사람은 1-(k-1)/n 으로 그 사람이 1번째부터 k-1번째 사람하고 생일이 같을 확률을 배제한 확률

이란다.
그래서 그거를 다 곱한 값을 근사치로 나타내면,

e^(k(1-k)/2n) 이거란다.

근데 같은 생일 가질 사람이 50% 이상 되는게 문제니까, 같은 생일 안가실 사람이 50% 이하되는걸 P0 로 잡는다.
(50% 넘는거 반대는 50% 이하가 맞지요)

그럼 e^(k(1-k)/2n) ≤ 0.5 니까..
k^2-k ≥ 2n * log2
k^2 ≥ 2nlog2       (근사치이다. 알고리즘 수업시간에 배워서 알겠지만 k^2-k 에서 비교값 하면 k가 무시되는건 진리)
k^2 ≥ 2log2 * n
k ≥ SQRT(2log2) * SQRT(n)  (루트기호 표시하기 귀찮다. 걍 SQRT(n) 으로 받아들여주세요)
   ≥ 1.17 * SQRT(n)  (왜 1.17인지는 공학용 계산기 두들겨보세요)
   ≥ 22.......             (??)

이정도까지 했으면 이제 n 값을 적용시켜야지.
1년 365일이고.. (2월 29일 그딴거 배제시킨다.. 일반적인걸로 가자 좀 제발)
그러므로 n=365니까.. 1.17에다가 SQRT(365) 곱한값이 22쩜 어쩌구저쩌구 (22......) 이거임

그럼 k가 22보다 크거나 같아야 하는데..
k는 사람이다. 사람이 소수점으로 된다는건 지나가던 개도 웃는 소리.

따라서 Birthday Paradox의 최소 인원수의 정답은 23명이다.
어디 다른데 블로그에서 보니까.. 23명일 때의 확률이 0.5073 이라고 해서 자세히 나왔는데.
그것 또한 Birthday Paradox를 구하는 정형화된 방법이니.. 참고해도 괜찮을 것 같다.

http://doortts.tistory.com/entry/%EC%83%9D%EC%9D%BC-%EC%97%AD%EC%84%A4-Birthday-Paradox

(솔직히 저처럼 대충 쓴게 아니라 체계적으로 잘 쓰셨네요. ^_^ 링크만 걸어두겠습니다!)

이게 어따 쓰냐면.. Hash Function 에서 Key 값을 찾아내는데..
수동적으로 일일히 찾아내는게 아니라 Birthday Paradox를 이용하여 키값을 빨리찾아내는 방법을 나타낸댄다.

실제 함수 적용에서는, 약간 다르게 해서 나타낸다.
k를 해쉬 함수의 키값과 동일한 값을 찾아내기 위해서 수행해야 하는 회수로 하고,
(H(k1)=H(k2) 가 되면서 k1<>k2 인 k2값을 찾아내는 것이라고 해야 되나? 그럼 k1는 내 생일, k2는 다른 사람이니까..)
해쉬 함수의 크기가 n bits일 때, 이에 대한 전체 개수는 바로 2^n, 즉 2의 n승 개수를 나타낸다.
즉, 위의 공식을 변형하면, n을 2^n 으로 다 바꿔주면 좋겠다.

부가적으로 2^n에 대해서 설명하자면,
2의 n승의 경우는 해쉬 함수의 사이즈가 n일 때 이에 대한 값을 찾기 위해서 노가다하는 전체 회수를 뜻한다.
예를 들어서, 3bit의 이진 코드가 있다고 하면 그거에 대한 경우의 수는? 2의 3승이니까 8이다.
그런 맥락으로 받아들여라. 즉 n 크기의 전체 시도 회수는 2의 n승, 즉 2^n 이다.


실제 배운 데에서도 보면 이렇게 나온다.

n : size of H()
SQRT(2^n) = 2^(n/2) trials must be infeasible 이라고 나왔다.

이것까지 봐도 이해가 안되는 분들을 위해서, 그렇다면 아까 위에 나온 부분 다시 보면서 적용해 보자.

k ≥ 1.17 * SQRT(2^n)
이게 바로 해쉬 함수에 갖다가 사용하는 부분의 핵심이다. (위에도 말했듯이 n은 2^n으로 다 바꾼다.)
그럼 이거를 다시 변형해서 나타내면, (여기서부터는 수업시간에 배운 그대로가 아닌 내가 이해한 부분이다.)

k ≥ 1.17 * SQRT(2^n)
      1.17 * 2^(n/2)      (이거는 중고등학교 수학만 알아도 바꿀 수 있는 것임)

이 된다.
즉, n bit 의 해쉬 함수가 있으면, 이것의 키값을 찾아내기 위해서 시도하는 회수는
원래대로라면 2^n 이여야 하지만,
실제로는 2^(n/2) * 1.17 이 되고,
1.17은 1에 근사한 값을 나타내기 때문에, 사실상 시도 회수 k는 2^(n/2)라고 해도 좋을 것이다.

한마디로, 해쉬 함수의 키값을 찾아내기, 즉 해킹을 하기 위해서는 반 정도의 승수에 대한 노력만 해도 된다.

그래서 위에 언급된 다른 블로그에서는 이렇게 말씀하신다.
"구 펜티엄 3.2G 짜리로 평균 17초면 값충돌(collision)이 나오는 값이 발견된다고 이야기 하고 있습니다. 요즘에는 이런 생일역설 문제를 줄이기 위해서, 적잖은 경우 128bit 값의 MD5 대신 160bit 를 사용하는 SHA 해시 값을 파일 고유값으로 제공하기도 합니다."

Birthday Paradox를 심심해서 하는게 아니다.
암호화 알고리즘의 암호를 깨는 회수를 줄이는 방안으로 제시된거고,
암호화 알고리즘을 만들 때의 해쉬 함수를 몇 비트로 해야 안전한지에 대한 경각심을 불러일으키기 위해서다.