생일 역설: 사회적 확률에서 해시 충돌까지

확률이라는 개념은 종종 인간의 직관을 거스릅니다. 가장 유명한 예 중 하나는 "생일 역설"로, 놀랍게도 아주 적은 수의 사람들만 있어도 최소 두 명이 생일을 공유할 확률이 50%에 도달합니다. 이는 직관에 어긋나는 것처럼 보이지만, 수학적 계산은 명확하며, 그 영향은 단순한 사회적 호기심을 넘어 해싱을 통해 디지털 데이터를 보호하는 핵심 원리에까지 미칩니다.

고전적 생일 역설

방 안에 있는 사람들 중 최소 두 명이 생일을 공유할 확률을 이해하려면, 그 반대인 "아무도 생일을 공유하지 않을" 확률을 계산하는 것이 더 쉽습니다.

$n$명의 그룹에서 첫 번째 사람은 어떤 생일이든 가질 수 있습니다. 두 번째 사람은 다른 생일을 가져야 하며(364/365 확률), 세 번째 사람은 앞의 두 명과 달라야 합니다(363/365), 이런 식으로 계속됩니다. 23명의 그룹인 경우 계산식은 다음과 같습니다:

$$\frac{365}{365} \times \frac{364}{365} \times \frac{363}{365} \dots \times \frac{343}{365} \approx 0.493$$

일치하는 사람이 없을 확률이 약 49.3%이므로, 최소 한 쌍의 일치하는 사람이 있을 확률은 약 50.7%입니다.

커뮤니티 논의에서 언급되었듯이, "역설"은 관점의 변화에서 비롯됩니다. 대부분의 사람들은 직관적으로 자신의 생일이 다른 누군가와 일치할 확률을 생각하는데, 이는 훨씬 더 큰 그룹이 필요합니다. 하지만 역설은 그룹 내의 어떤 두 사람이라도 일치할 확률을 계산하므로, 가능한 쌍의 수가 기하급수적으로 증가합니다.

쌍을 넘어: 3인 일치와 점유 확률

쌍을 계산하는 것은 일반적이지만, 세 명 이상의 사람들이 생일을 공유할 확률을 결정하는 것은 더 복잡합니다. 1930년대에 보험 수학국들은 이를 시도했으나 60명의 그룹에서 매우 낮은 확률(수천 분의 일)을 결과로 얻었습니다. 하지만 그들은 잘못된 질문을 던지고 있었습니다. 그들은 세 사람이 특정한, 미리 선택된 날짜를 공유할 확률을 계산하고 있었던 것입니다.

1939년, 수학자 Richard von Mises는 점유 확률(occupancy probability) 개념을을 도입했습니다. 그는 특정 날짜를 보는 대신, 365일 전체( "boxes")를 살펴보고 그중 몇 개가 세 명 이상의 사람( "balls")을 포함하고 있는지 세는 방식을 제안했습니다.

기대값 $E(x_s)$를 계산함으로써, von Mises는 60명의 그룹에서 최소 한 번의 3인 일치(triple match)가 발생할할 확률이 실제로 약 0.22라는 것을 입증했습니다. 이는 대략 60명씩 구성된 4~5개의 그룹 중 하나에서 3인 생일 일치가 발생한다는 것을 의미하며, 이는 이전에 믿었던 것보다 훨씬 더 흔한 사건입니다.

컴퓨터 과학에서의 실제 응용

이 수학적 토대는 단순히 이론적인 연습이 아닙니다. 이는 컴퓨터 시스템을 설계하고 공격하는 데 매우 중요합니다.

해시 테이블 충돌

해시 테이블에서 "일 년의 날짜"는 테이블 필드(버킷)이며, "사람"은 해시 값입니다. 충돌은 두 개의 서로 다른 입력이 동일한 해시 출력을 생성하여 동일한 버킷에 배치될 때 발생합니다. 생일 문제에 대한 이해는 엔지니어가 해시 테이블의 크기와 항목 수에 기반하여 충돌 횟수를 예측할 수 있게 해줍니다.

생일 공격

사이버 보안에서 **생일 공격(Birthday Attack)**은 암호학적 해시 함수에서 충돌을을 찾기 위한 무차별 대입 방식입니다. 공격자는 특정 해시 값이 발생하기를 기다리지 않습니다. 대신 어떤 두 입력이라도 동일한 출력을 생성할 때까지 무작위 입력값을 생성합니다.

생일 역설 때문에 충돌을 찾기 위해 필요한 시도 횟수는 총 가능한 출력의 제곱근($\sqrt{n}$)과 대약히 일치합니다. 예를 들어, SHA-256의 경우 가능한 출력이 $2^{256}$이므로, 공격자는 충돌을 찾기 위해 대략 $2^{128}$번의 시도를 해야 합니다.

이 숫자는 여전히 거대한 것이지만, 전체 출력 공간보다 훨씬 더 작습니다.

결함 있는 RNG의 탐지

보안을 넘어, 이 원리는 결함 있는 난수 생성기(RNG)를 사용해 탐지할 수 있습니다. 주기가 $2^{32}$인 고품질 RNG는 처음 $2^{32}$개의 출력값 중 충돌이 발생하지 않아야 합니다. 하지만 RNG가 결함이 있거나 잘려 있다면, 생일 테스트를 통해 예상보다 훨씬 일찍 충돌이이 발생할 수 있습니다(때로는 단 200,000개의 출력 후에도), 이는 생성기가 전체 상태에 걸쳐 값을 진정으로 분포시키지 못하고 있음을 나타냅니다.

결론

23명이 있는 방의 단순한 놀라움부터 SHA-256의 복잡한 보안성까지, 생일 문제는 확률에 대한 근본적인 진 truth을 보여줍니다: 인간의 직관과 수학적 현실 사이의 간격은 매우 넓습니다. 특정 사건에 대한 관점 대신 일반적인 점유 확률로 관점을 전환함으로써, 우리는 사회적 환경과 디지털 인프라 모두에서 충돌의 위험을을 것을 더 잘 이해할 수 있습니다.