생일 역설 (Birthday Paradox)

누구를 만났는데, 공교롭게도 생일이 같은 사람인 경우가 있습니다.

참, 신기합니다.

전, 생일이 특이한데 1월1일 입니다. 그리고 저랑 생일이 같은 사람을 1명 알고 있습니다. 여자분인데, 처음에 생일이 서로 같은걸 알고는 '아! 운명인가 보다!' 라는 생각은 안했습니다.. (..뭔소린지?-_-)

처음엔 굉장히 신기했는데, 생각해 보면 1년은 365일인지라 쉽게 생가각해서 우리나라 인구를 천 만명쯤 확 줄여서 3650만명이라고 보면, 생일 같은 사람이 대략 10만명은 있는건데요, 이러면 좀 느낌이 다르죠.

어쨌든, 그래도 생일이 같은 사람을 주변에서 보는건 흔한 건 아닌것 같습니다.

<보바 팻의 생일에 모여든 친구들...?>

확률을 따져 보겠습니다.

제 옆에 한 사람이 있습니다. 그럼 저랑 생일이 같을 확률은 1/365 입니다. 다시 말해 365명 정도가 제 옆에서 웅성대고 있어야 겨우 저와 생일이 같은 사람이 1명 정도 존재한다는 겁니다.

그런데 말입니다. 문제 상황을 살짝 바꾸어서

'모임 내에서 서로 생일이 같은 사람이 있을 확률이 50%가 넘게 되는 모임인원'은 몇 명 쯤일까요?

즉, 몇 명쯤이 모여 있으면 50%의 확률로 '어! 뭐야? 둘이 생일이 같은거야?' 라며 인연설을 꺼낼 수 있게 될까요?

뭐, 고등학교때 배운 combination 으로 계산할 수 도 있는데요, 언듯 생각이 나지 않아 계산이 어려워 질 수도 있습니다. 그래서 반대로 생각해 보겠습니다. (1 - 모임 내의 사람들이 모두다 생일이 다를 확률) 로 말입니다.

Case1. 모임 인원이 두 명일 경우

1 - 1/(365 - 내 생일 하루) = 1 - 1/364 = 0.0027 (0.27%) 굉장히 낮죠.

Case2. 모임 인원이 세 명일 경우

1 - 1/(365 - 내 생일 하루)*1/(365 - 내 생일 하루 - 앞 사람 생일 하루) = 1 - 1/364 * 1/363 = 0.008

이런식으로 계산하면 되는데요, 한 번 엑셀로 쭉 계산해 보았습니다.

23명 정도의 모임이 있으면 동전 앞 뒤면 정도의 확률로 같은 생일자가 존재하고, 41명 정도가 되면 90%의 확률로 같은 생일자가 생깁니다.

언듯 생각하면 이상합니다만, 확률적으론 그렇습니다. 이런걸 생일 역설(Birthday Paradox)이라고 한다네요. 자, 뭐, 상식적인 수준으로 알아 둬도 나쁘진 않은 이야기입니다만, 좀더 IT와 관련지어 생각해 보겠습니다.

돌아다니다 보면 사이트에서 파일을 다운로드 받을때에 아래 그림과 같은 메시지를 본 적이 있으실 겁니다.

혹시라도 돌아다니다가 오염된 파일을 받을까봐 단방향 해시함수로 signature 된 코드를 제공하니, 다운 받아서 확인해 보라는 뜻입니다.

MD5 라고 되어 있는 링크를 클릭해 보았습니다.

괴 문자들이 보이는데, 이게 바로 다운 받으려고 하는 httpd-2.2.10.tar.gz 파일에 대한 단방향 해시값(Hash value)입니다. MD5 해시는 128비트, 즉 2의 128제곱의 다른 경우로 해시값이 표기 되며, 내용이 1bit 라도 다르면 다른 해시값이 나오게 되어있습니다.

따라서 이 httpd 압축파일의 해시값과 같은 해시값을 갖는 파일이 존재할 확률은 1/ (3.4 * 10의 38승) 으로, 이정도면 거의 0에 수렴한다고 봐도 무방하죠. 그래서 이 압축파일의 고유성을 MD5 해시값을 통해 증명하는것이 타당한 거죠. (바이러스나 파일손상이 조금만 생겨도 해시값이 달라지니깐요)

그런데 앞서 같은 생일자를 찾는 문제와 같이, 전체 MD5 해시 값들 중 같은 값이 나올 확률을 따져 보면 약간 상황이 달라지는 겁니다. 생일 파라독스 관점에서 접근하면,즉, '특정 값과 같은 값'이 아닌, '군집중 같은 값을 갖는 쌍' 의 관점으로 접근하면, 앞선 그래프처럼 일정 모 집단 이상이 되면 급격하게 확률이 증가되는 구간이 생깁니다.

MD5가 나왔던 1991년 경에는 같은 해시 값을 갖는 객체(target)를 찾을 수 있는 것 조차 쉽지 않아 보였더랬습니다만, 2006년에 발표된 알고리즘( Tunnels in Hash Functions: MD5 Collisions Within a Minute )은 구 펜티엄 3.2G 짜리로 평균 17초면 값충돌(collision)이 나오는 값이 발견된다고 이야기 하고 있습니다.

전 세계가 네트워크로 묶이고, 전체 객체 수가 많아지면서 MD5 해시의 한계가 살짝 드러나는 거죠. 사실 값 충돌(=같은 해시값을 갖는 다른 개체)을 찾아내는 것과 실제 같은 Hash 값을 값은 갖는 개체가 존재하는 것과는 또 별개의 문제일 수 있습니다만, 어쨌든 유일성 증명에서 MD5는 실용적(Pratical)인 수준에서만 쓰이고, Scientific 한 부분에선 쓰이지 않게 되었습니다.

그래서 요즘에는 이런 생일역설 문제를 줄이기 위해서, 적잖은 경우 128bit 값의 MD5 대신 160bit 를 사용하는 SHA 해시 값을 파일 고유값으로 제공하기도 합니다.

<SHA 해시 값도 같이 제공하는 Apache Geronimo >

<16진수 문자열 40자리 짜리인 SHA-1 해시>

자, 별건 아니지만, 이게 바로 Download 받을 때 옆에 나오는 해시값의 비밀입니다. (^_^);