한양과학기술고등학교

에듀테크 프로젝트 대시보드

생일 역설과 생일 공격

생일 역설과 생일 공격

한 교실에 23명만 있어도 생일이 같은 짝이 있을 확률이 50%를 넘는다. 이 "역설"이 왜 참인지, 그리고 해커가 해시 함수를 깨는 데 어떻게 쓰이는지 본다.
핵심. 사람이 k명 있으면 비교할 짝(쌍)은 k(k-1)/2개다. 23명이면 253쌍 — 이 정도면 "어느 한 쌍이라도 겹칠" 확률이 반을 넘는다. 특정 사람과 나의 생일이 같을 확률(1/365)과 누구든 둘이 겹칠 확률을 헷갈리는 데서 직관이 무너진다. 일반화하면, 크기 N인 공간에 무작위 값을 뽑을 때 약 √N개만에 충돌이 생긴다.

1. 생일이 겹칠 확률 곡선

"모두 다를" 확률을 곱해서 빼는 방식이 가장 정확하다. P(겹침) = 1 − (365/365)·(364/365)·(363/365)···((365−k+1)/365). 슬라이더로 인원과 "달력 크기 N"을 바꿔 보라.

23
365
정확한 확률 P(겹침)
50.7%
근사식 1 − e^(−k(k−1)/2N)
50.0%
50%를 넘는 최소 인원
23
N=365에서 곡선은 23명에서 50%, 41명에서 90%, 57명에서 99%를 지난다. 사람 수가 두 배가 아니라 제곱으로 확률에 영향을 준다는 게 핵심이다.

2. 왜 직관이 빗나가나 — "짝"을 세어 보기

나와 생일이 같은 특정 친구를 찾는 거라면 확률은 정말 낮다(1/365). 하지만 생일 역설은 아무 두 사람이면 된다. k명에서 만들 수 있는 짝의 수는:

C(k, 2) = k · (k−1) / 2   →   k=23 이면 253쌍

한 쌍이 안 겹칠 확률은 364/365 ≈ 0.99726. 253쌍이 모두 안 겹칠 확률은 대략 (364/365)253 ≈ 0.4995 — 그래서 "적어도 한 쌍은 겹칠" 확률이 1 − 0.4995 ≈ 50%가 된다. (쌍들이 완전히 독립은 아니라 근사지만 감을 잡기엔 충분하다.)

3. 시뮬레이션: 진짜로 뽑아 보기

크기 N인 달력에 사람을 한 명씩 무작위로 배치하다가 첫 충돌이 나면 멈춘다. 이걸 여러 번 반복하면, 첫 충돌까지 걸린 인원의 평균이 약 1.25·√N에 모인다(N=365 → ≈ 24명).

배치 대기 중…
이번 판 첫 충돌 인원
–
누적 평균 (판수)
–
이론값 1.25·√N
≈ 24

4. 생일 공격: 해시 함수를 반으로 깎는다

해시 함수가 n비트 출력을 내면 가능한 해시값은 N = 2n개다. "주어진 파일과 같은 해시를 갖는 다른 파일"을 찾으려면(제2 역상) 평균 2n번 시도해야 한다. 하지만 공격자가 아무 두 개나 같은 해시면 된다면(충돌), 생일 역설에 의해 √(2n) = 2n/2번이면 충분하다.

충돌 찾기 비용 ≈ 2n/2   (브루트포스 2n의 제곱근)
해시출력 비트제2 역상 (2ⁿ)생일 충돌 (2^(n/2))현실
MD51282¹²⁸2⁶⁴2004년 이후 수 초면 충돌 생성 (완전 붕괴)
SHA-11602¹⁶⁰2⁸⁰2017년 Google SHAttered로 실제 충돌 공개
SHA-2562562²⁵⁶2¹²⁸2¹²⁸는 사실상 불가능 — 그래서 안전
이래서 "128비트 보안"을 원하면 해시 출력은 256비트로 잡는다. 생일 공격이 절반을 먹어치우기 때문이다. 대칭키(AES-128)에는 생일 공격이 없어 128비트로 충분하지만, 충돌 저항이 필요한 해시·서명은 두 배가 필요하다.

충돌 하나로 무엇을 하나

파이썬으로 보는 충돌 탐색(작은 해시)

# 32비트로 잘라낸 해시 → 생일 공격이면 약 2^16 = 65,536번이면 충돌
import hashlib, os

def h(msg):
    return hashlib.sha256(msg).digest()[:4]   # 앞 4바이트(32비트)만 사용

seen = {}
for i in range(1 << 20):
    m = os.urandom(16)
    d = h(m)
    if d in seen and seen[d] != m:
        print("충돌!", i, "번째 시도", seen[d].hex(), m.hex())
        break
    seen[d] = m
# 보통 5만~10만 번 근처에서 걸린다 — 2^32이 아니라 2^16 스케일

5. 정리