같은 열쇠가 겹칠 확률

한 반에 친구들이 30명 모여 있을 때 생일이 같은 짝이 있는지 확인해 봅니다. 놀랍게도 대부분의 교실에서 같은 생일인 짝이 나옵니다.

나 한 사람과 생일이 같을 확률은 낮지만, 친구들끼리 서로서로 짝지어 비교할 수 있는 쌍의 수가 수백 개나 되기 때문입니다.

생일이 겹치지 않을 확률을 계산해 봅니다. 두 번째 사람은 , 세 번째 사람은 … 사람이 늘어날수록 이 분수들을 계속 곱하게 됩니다.

23명이 모이면 비교할 수 있는 쌍의 수가 쌍이나 됩니다. 곱셈이 누적되면서 모두가 다를 확률은 50% 밑으로 뚝 떨어지고, 겹칠 확률이 절반을 넘어서게 됩니다.

가능한 경우의 수가 개인 해시 공간에서 개의 값을 무작위로 추출할 때 충돌이 발생하지 않을 확률은 입니다.

충돌 확률이 50% 이상이 되는 임계점은 에서 로 도출됩니다. 즉 전체 공간 이 아니라 그 제곱근인 번의 시도만으로 충돌을 일으킬 수 있습니다.

이 원리는 암호학에서 해시 함수의 충돌 저항성을 무너뜨리는 생일 공격(Birthday Attack)의 기초입니다. 64비트 해시 함수는 번이 아니라 단 (약 40억) 번의 대입만으로 위조가 가능해집니다.

이 때문에 현대 블록체인과 전자서명 표준은 안전성을 확보하기 위해 출력 길이를 256비트(SHA-256) 또는 512비트로 대폭 늘려 생일 공격의 위협을 원천 봉쇄합니다.