생일 문제 (Birthday Problem)

생일 문제(Birthday Problem)는 여러 사람 가운데 생일이 같은 사람이 적어도 두 명 있을 확률을 묻는 확률 문제로, 23명만 모여도 그 확률이 50%를 넘는다는 결과로 알려져 있습니다. 1년 365일에 비해 23명이라는 적은 인원으로도 일치가 일어날 가능성이 높다는 점이 직관과 어긋나 “생일 역설(Birthday Paradox)”이라고도 부릅니다. 암호학에서는 이 원리가 해시 충돌을 찾는 데 필요한 시도 횟수를 추정하는 기준, 즉 생일 한계(birthday bound)로 쓰입니다.

생일 역설: 진짜 역설이 아니라 확률의 문제

생일 역설은 논리적 모순이 아니라 수학적으로 타당한 결과입니다. 직관이 틀리는 이유는 질문을 잘못 읽기 때문입니다. 특정인의 생일이 다른 사람과 일치할 확률이 아니라, 그룹 안의 아무 두 사람이나 생일이 같을 확률을 묻는 것입니다. 이 차이가 확률을 극적으로 변화시킵니다.

23명이 중요한 이유:

• 23명이면 가능한 두 사람 조합은 23 × 22 / 2 = 253쌍입니다. 첫 사람은 22명과, 다음 사람은 21명과… 차례로 비교되므로 비교 횟수가 놀라울 만큼 많아집니다.
• 각 “쌍”은 생일 일치의 기회를 나타냅니다. 한 쌍의 생일이 같을 확률은 1/365로 낮지만, 쌍의 수가 많기 때문에 전체 확률이 높아집니다.
• 정확히 계산하면, 모두의 생일이 다를 확률은 (365/365) × (364/365) × … × (343/365) ≈ 49.3%이므로 적어도 한 쌍이 일치할 확률은 약 50.7%입니다.

결국 “역설”의 원인은 쌍의 수가 인원의 제곱에 비례해 빠르게 늘어난다는 점을 과소평가하는 직관에 있습니다.

암호학에서의 의미: 생일 한계

가능한 값이 N개인 공간에서 무작위 값을 k개 뽑을 때, 충돌(같은 값이 두 번 나오는 것)이 일어날 확률은 대략 k²/(2N)입니다. 즉 충돌 확률은 뽑은 개수에 대해 선형도 기하급수도 아닌 제곱에 비례해 커지며, k가 약 √N에 이르면 충돌이 일어날 가능성이 상당히 높아집니다.

• 해시 충돌: 출력이 n비트인 해시 함수에서는 가능한 값이 2ⁿ개이므로, 약 2^n/2개의 입력을 해시하면 충돌을 찾을 것으로 기대됩니다. 그래서 256비트 해시 함수의 충돌 저항성은 2²⁵⁶이 아니라 약 2¹²⁸ 수준으로 평가합니다.
• 생일 공격: 이 성질을 이용해 서로 다른 두 입력이 같은 해시값을 갖도록 만드는 공격을 생일 공격이라고 합니다. 설계자는 이를 고려해 원하는 보안 수준의 두 배 길이의 해시 출력을 선택합니다.
• 무작위 키와 식별자: 무작위로 만든 256비트 키나 식별자도 같은 원리로 충돌 확률을 계산합니다. 2¹²⁸개에 가까운 값을 만들기 전까지는 충돌 확률이 무시할 수 있을 만큼 작으므로, 실제 사용에서 우연한 충돌은 사실상 일어나지 않습니다.

생일 역설을 이해하는 것의 장점

• 향상된 직관: 확률에 대한 통념을 깨고, 겉보기에 드문 사건이 예상보다 더 자주 발생할 수 있음을 보여줍니다.
• 실용적인 적용: 해시 함수의 출력 길이 선택, 무작위 식별자의 길이 결정, 컴퓨터 과학의 해시 테이블 설계 등에 쓰입니다.

단점 또는 오해

• 진정한 역설이 아님: 놀랍기는 하지만 논리적 모순이 아니라 수학적으로 타당한 결과입니다.
• 단순화된 가정: 50.7%라는 값은 생일이 365일에 고르게 분포한다고 가정한 결과입니다. 실제 생일 분포는 고르지 않으며, 분포가 고르지 않으면 일치 확률은 오히려 조금 더 높아집니다.

실제 예:

1. 학급: 학교 시절 23명 이상인 반이었다면 생일이 같은 학생이 있었을 가능성이 큽니다.
2. 모임: 23명 이상이 모인 자리에서 생일을 확인해 보면 일치하는 사람을 발견하고 놀랄 수도 있습니다.

생일 역설은 확률에 대한 직관이 때로는 오해를 불러일으킬 수 있다는 점을 강조합니다. 겉보기에 작은 그룹과 많은 가능성이 있더라도 일치할 가능성이 놀랍도록 높을 수 있으며, 같은 이유로 해시 함수의 안전성은 출력 길이의 절반 비트 수준으로 평가됩니다.