Birthday Problem (생일 문제)

정의

생일 문제 (Birthday Problem) 는 N 개의 동등한 가능성이 있는 결과에서 무작위로 k 개를 선택할 때 적어도 하나의 충돌이 발생할 확률을 분석하는 문제. 충돌 확률이 50% 를 넘는 k 는 직관보다 훨씬 작은 sqrt(N) 규모이며, 이를 Birthday Paradox (생일 역설) 이라 부름.

N=365 일 때 k=23 만 되어도 충돌 확률이 50% 를 넘는 것이 대표적 예시. 해싱과 암호학에서는 Birthday Attack 이라는 이름으로 2^(n/2) 의 해시 충돌 탐색 비용을 의미함.

문제 상황과 동기

“몇 명이 모여야 생일이 같은 두 사람이 있을 확률이 50% 가 넘을까?” 직관은 “약 183 명 (절반)” 이라고 답하지만 실제는 23 명.

• naive: 모든 쌍을 검사하면 O(k²) 시간. 충돌 확률이 k² 에 비례함을 설명하지 못함.
• birthday analysis: 충돌 없을 확률 P(no collision) = Π (N - i) / N. k ≈ sqrt(2N ln 2) 에서 50% 도달.
• hash 응용: n-bit 해시 (2^n 출력) 에서 2^(n/2) 번만 시도하면 50% 확률로 충돌 발견.

핵심 통찰: 쌍의 개수는 kC2 = k(k-1)/2 이므로 충돌 확률은 k 에 대해 이차식. sqrt(N) 만 넘으면 충돌이 필연적.

시각화

핵심 아이디어

충돌 확률 공식

P(no collision with k people, N days)
  = (N/N) * ((N-1)/N) * ((N-2)/N) * ... * ((N-k+1)/N)
  = N! / ((N-k)! * N^k)

P(collision) = 1 - P(no collision)

근사

e^x ≈ 1 + x 로 근사:
P(no collision) ≈ exp(-k(k-1) / (2N))

P(collision) = 50% 일 때:
  exp(-k²/(2N)) ≈ 0.5
  k ≈ sqrt(2N ln 2) ≈ 1.177 sqrt(N)

해시 충돌 (Birthday Attack)

n-bit 해시: N = 2^n
  sqrt(N) = 2^(n/2)
  50% 충돌 시도 횟수 ≈ 2^(n/2)

예: SHA-256 (256 bit) 은 2^128 번 시도해야 50% 충돌. 현실적으로 불가능한 수.

알고리즘

collision_prob(N, k):
    prob_no = 1.0
    for i = 0 to k-1:
        prob_no *= (N - i) / N
    return 1 - prob_no

find_threshold(N, target=0.5):
    for k = 2 to N:
        if collision_prob(N, k) >= target:
            return k
    return N

birthday_attack(hash_fn, output_space):
    # 평균 2^(n/2) 번 시도
    seen = empty set
    for i = 0 to 2^(n/2):
        h = hash_fn(random_input())
        if h in seen:
            return collision found
        seen.add(h)
    return collision not found

구현

#include <bits/stdc++.h>
using namespace std;
​
int main() {
  // N: 표본 공간 크기 (일), k: 선택 개수 (사람)
  int n, k; cin >> n >> k;
​
  double prob_no = 1.0;
  for (int i = 0; i < k; i++)
      prob_no *= (double)(n - i) / n;
​
  cout << fixed << setprecision(10);
  cout << "P(no collision) = " << prob_no << "\n";
  cout << "P(collision) = " << 1.0 - prob_no << "\n";
​
  // threshold: P(collision) >= 50% 인 최소 k
  int thres = 0;
  double p = 1.0;
  for (int i = 0; i < n; i++) {
      p *= (double)(n - i) / n;
      if (1.0 - p >= 0.5) { thres = i + 1; break; }
  }
  cout << "Threshold k (>=50%) = " << thres << "\n";
  // sqrt(n) approx
  cout << "sqrt(N) = " << sqrt(n) << "\n";
}

import math
​
def collision_prob(n: int, k: int) -> float:
  prob_no = 1.0
  for i in range(k):
      prob_no *= (n - i) / n
  return 1.0 - prob_no
​
def find_threshold(n: int, target: float = 0.5) -> int:
  prob_no = 1.0
  for i in range(n):
      prob_no *= (n - i) / n
      if 1.0 - prob_no >= target:
          return i + 1
  return n
​
# 대표 값들
for n in [365, 10000, 1000000]:
  k = find_threshold(n)
  print(f"N={n}: threshold k={k}, sqrt(N)={math.sqrt(n):.1f}, "
        f"1.177*sqrt(N)={1.177 * math.sqrt(n):.1f}")
​
# 생일 문제 그래프
print("\nN=365, k별 충돌 확률:")
for k in [10, 23, 30, 50, 100]:
  print(f"  k={k}: P(collision)={collision_prob(365, k):.4f}")

import java.util.*;
import java.io.*;
​
public class Main {
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int n = Integer.parseInt(st.nextToken());
      int k = Integer.parseInt(st.nextToken());
​
      double probNo = 1.0;
      for (int i = 0; i < k; i++)
          probNo *= (double)(n - i) / n;
​
      System.out.printf("P(no collision) = %.10f%n", probNo);
      System.out.printf("P(collision) = %.10f%n", 1.0 - probNo);
​
      // threshold
      double p = 1.0;
      int thres = n;
      for (int i = 0; i < n; i++) {
          p *= (double)(n - i) / n;
          if (1.0 - p >= 0.5) { thres = i + 1; break; }
      }
      System.out.println("Threshold k (>=50%) = " + thres);
      System.out.printf("sqrt(N) = %.2f%n", Math.sqrt(n));
  }
}

365 23

P(no collision) = 0.4927027657
P(collision) = 0.5072972343
Threshold k (>=50%) = 23
sqrt(N) = 19.10

1024 40

P(no collision) = 0.4562627824
P(collision) = 0.5437372176
Threshold k (>=50%) = 38
sqrt(N) = 32.00

복잡도

변형 / 활용

1. Birthday Attack (해시 충돌)

n-bit 해시 함수의 충돌쌍을 찾는 가장 효율적인 일반 공격. 2^(n/2) 번 무작위 입력 + 해시 계산 후 충돌 발견.

• MD5: 2^64 (실제로는 더 작은 비용으로 공격 가능)
• SHA-1: 2^80 (2017 년 Google 이 2^63 비용으로 충돌 공개)
• SHA-256: 2^128 (현실적으로 불가)

2. Meet-in-the-Middle (MITM)

공간을 절반으로 나누어 각각 탐색 후 충돌 찾기. 부분집합 합 문제에서 O(2^(N/2)) 으로 최적화.

3. 확률적 알고리즘 분석

Randomized algorithm 의 실패 확률을 birthday bound 로 분석. Miller-Rabin 소수 판정의 반복 횟수 결정에 사용.

4. 생일 문제 일반화

함정

1. “365/2 = 183” 직관

생일 문제의 직관적 오답. 충돌 확률은 “쌍의 수” (kC2) 에 의존, “개인의 수” 가 아님. sqrt(N) 규모임을 기억.

2. 충돌 = 공격자에게 유리

n-bit 키의 보안 강도는 n 이 아니라 n/2. Birthday Attack 때문에 AES-128 의 보안 강도는 2^128 이 아니라 2^64 정도로 봐야 함.

3. 독립성 가정

생일 문제는 선택이 균등하고 독립적일 때만 성립. 실제 해시 함수가 균일하지 않으면 충돌 확률이 더 높아질 수 있음.

4. k 가 N 에 가까울 때 근사 오류

exp(-k²/(2N)) 근사는 k << N 일 때 유효. k 가 N 에 가까우면 정확한 계승 계산 필요.

BOJ 연습 문제

참고

• 확률
• 해싱 (해시 충돌)
• 폴라드 로 (cycle detection, birthday 응용)
• MITM (중간에서 만나기)