# 해시 충돌과 생일 문제

분야: CS·데이터사이언스
학교급: 고등
정식 URL: https://pi.devxdev.xyz/wiki/math/%ED%95%B4%EC%8B%9C_%EC%B6%A9%EB%8F%8C%EA%B3%BC_%EC%83%9D%EC%9D%BC_%EB%AC%B8%EC%A0%9C

---

<!-- prereq: 확률, 경우의 수, 조합, 해시와 나머지 연산 -->

## 정의

**해시 충돌(hash collision)**이란 해시 함수 $h:X\to Y$($h$는 $X$에서 $Y$로 가는 함수, $X$는 입력 전체 집합, $Y$는 해시값 전체 집합이고 $|Y|=m$)에서 서로 다른 두 입력 $x_1 \neq x_2$가 같은 해시값 $h(x_1)=h(x_2)$를 가지는 현상을 말한다. $|X|>m$이면 이런 충돌이 반드시 존재한다.

**생일 문제(birthday problem)**는 각 사람의 생일이 $m$개의 값(윤년을 제외하면 $m=365$) 중 하나를 서로 독립적으로, 균등한 확률로 갖는다고 할 때, $n$명 중 생일이 같은 두 사람이 적어도 한 쌍 존재할 확률 $P(n)$을 구하는 문제다. 이는 해시 충돌이 일어날 확률을 어림잡는 대표적인 확률 모형이다.

## 직관

해시 충돌을 "생일이 겹치는 사람"에 비유하면, 해시값은 '생일'이고 입력값은 '사람'이다. 얼핏 보면 $n$명이 365개의 생일 중 하나씩 가지므로 겹칠 확률이 작을 것 같지만, 실제로 비교되는 것은 **한 사람 대 특정한 한 사람**이 아니라 **$n$명 중 아무 두 사람의 짝**이다. $n$명 중 만들 수 있는 짝의 개수는 조합으로 $_{n}C_{2}=\dfrac{n(n-1)}{2}$(엔 씨 투)이므로 $n$이 조금만 커져도 짝의 수는 제곱에 가깝게 늘어난다. 그래서 사람 수가 365에 비해 훨씬 적어도 충돌 확률은 빠르게 커진다. 해시 함수도 마찬가지로, 해시값의 가짓수 $m$이 아무리 커도 저장하는 데이터 개수 $n$이 늘면 생각보다 훨씬 빨리 충돌이 발생한다.

## 공식

$n$명 모두 생일이 서로 다른 사건(여사건)의 확률은

$$P(\text{모두 다름}) = \frac{m(m-1)(m-2)\cdots(m-n+1)}{m^n} = \frac{{}_{m}P_{n}}{m^n}$$

($_{m}P_{n}$은 "엠 피 엔"이라 읽으며 서로 다른 $m$개에서 $n$개를 뽑아 순서를 정하는 순열의 수다.) 따라서 구하는 확률은

$$P(n) = 1 - \frac{{}_{m}P_{n}}{m^n}$$

$n$이 $m$에 비해 작을 때는 $1-\frac{i}{m}\approx e^{-i/m}$($e$는 자연로그의 밑, 약 $2.718$)을 이용해

$$P(n) \approx 1 - e^{-\,n(n-1)/(2m)}$$

로 근사할 수 있고, 이 확률이 $\dfrac12$을 넘는 지점은 $n \approx 1.1774\sqrt{m}$이다.

## 예시

$m=365$, $n=4$일 때 여사건의 확률은
$$P(\text{모두 다름}) = \frac{365\cdot364\cdot363\cdot362}{365^4} = \frac{17{,}458{,}601{,}160}{17{,}748{,}900{,}625} \approx 0.9836$$
이므로 $P(4) \approx 1-0.9836 = 0.0164$, 즉 약 $1.6\%$다. 반면 $n=23$이면 계산 결과 $P(23)\approx 0.507$로 절반을 넘는다.

아래는 근사식 $P(n)\approx 1-e^{-n(n-1)/730}$을 사람 수 $n$에 대한 그래프로 나타낸 것이다.


그래프: y=1-exp(-x*(x-1)/730) (정의역 0~60)


## 🌍 실생활 예시

암호학적 해시 함수(예: SHA-256)의 안전한 출력 길이를 정할 때 생일 문제가 그대로 쓰인다. SHA-256의 해시값은 $2^{256}$가지이지만, 생일 문제의 근사식에 따르면 실제로 충돌을 찾는 데 필요한 시도 횟수는 $2^{256}$이 아니라 대략 $\sqrt{2^{256}}=2^{128}$번이면 충분하다(이를 **생일 공격**이라 한다). 그래서 암호학자들은 해시 함수를 설계할 때 목표로 하는 충돌 저항성의 두 배에 해당하는 출력 비트 수를 확보한다.

## ⚠️ 흔한 실수

- **잘못된 생각**: "23명이면 365일 중 겨우 23일만 채우니 생일이 겹칠 확률은 낮을 것이다." → **왜 틀렸는가**: 비교 대상은 한 사람이 아니라 $n$명 중 아무 두 사람의 짝이며, 그 개수는 $_{n}C_{2}=\dfrac{n(n-1)}{2}$로 늘어난다. $n=23$이면 짝이 $253$개나 되어 겹칠 기회가 많다.
- **잘못된 생각**: $P(n)$을 $n \times \dfrac{1}{365}$처럼 단순히 곱해서 구할 수 있다. → **왜 틀렸는가**: 이렇게 하면 한 사람이 여러 짝에 동시에 속해 사건들이 겹치는 것을 무시하게 된다. 옳은 방법은 여사건(모두 생일이 다름)의 확률을 구해 $1$에서 빼는 것이다.
- **잘못된 생각**: "해시값의 가짓수 $m$이 충분히 크면(예: $2^{256}$) 충돌은 사실상 불가능하다." → **왜 틀렸는가**: 생일 문제에 의해 충돌 확률이 $\dfrac12$을 넘는 지점은 $m$이 아니라 $\sqrt{m}$ 규모이므로, $m$의 크기만 보고 안전하다고 단정하면 안 된다.

## 확인 문제

1. 학생 $32$명이 있는 학급에서 "생일이 같은 두 사람이 존재한다"는 사건의 여사건을 말로 서술하고, 그 확률을 구하는 식을 순열 기호 $_{365}P_{32}$를 이용해 세워라. (계산은 하지 않아도 된다)
2. $n=10$명일 때의 짝의 개수 $_{10}C_{2}$와 $n=23$명일 때의 짝의 개수 $_{23}C_{2}$를 각각 구하고, 사람 수가 약 $2.3$배 늘었을 뿐인데 확률이 크게 뛰는 이유를 짝의 개수 변화로 설명하라.
3. 해시함수의 출력값 가짓수가 $m=2^{16}=65536$일 때, 근사식 $n\approx 1.1774\sqrt{m}$을 이용하여 충돌 확률이 $50\%$를 넘기 시작하는 대략적인 해시 개수 $n$을 구하라.

정답 보기:

1. 여사건은 "$32$명의 생일이 모두 서로 다르다"이며, 그 확률은 $\dfrac{{}_{365}P_{32}}{365^{32}}$이므로 구하는 확률은 $1-\dfrac{{}_{365}P_{32}}{365^{32}}$이다.
2. $_{10}C_{2}=\dfrac{10\cdot9}{2}=45$, $_{23}C_{2}=\dfrac{23\cdot22}{2}=253$. 짝의 개수가 $45$에서 $253$으로 약 $5.6$배 늘어났으므로, 사람 수가 조금만 늘어도 겹칠 기회(짝)는 훨씬 빠르게 늘어나 확률이 크게 뛴다. 이것이 바로 사람 수가 제곱에 가깝게 확률에 영향을 주는 이유다.
3. $\sqrt{m}=\sqrt{65536}=256$이므로 $n\approx 1.1774\times256\approx301.4$, 즉 약 $301$개 정도의 해시값이 모이면 충돌 확률이 $50\%$를 넘기 시작한다.



## 관련 개념

- 확률 — 여사건과 독립사건의 확률 계산이 생일 문제 공식의 기초가 된다.
- 경우의 수, 조합 — 짝의 개수 $_{n}C_{2}$와 순열 $_{m}P_{n}$ 계산에 쓰인다.
- 해시와 나머지 연산 — 해시 함수의 정의와 충돌의 발생 원리를 다룬다.
- 블룸 필터 — 해시 충돌 확률을 직접 활용해 설계되는 자료구조다.

---

관련 개념:
- 해시와 나머지 연산 (/wiki/math/%ED%95%B4%EC%8B%9C%EC%99%80_%EB%82%98%EB%A8%B8%EC%A7%80_%EC%97%B0%EC%82%B0)
- 확률 (/wiki/math/%ED%99%95%EB%A5%A0)
- 경우의 수 (/wiki/math/%EA%B2%BD%EC%9A%B0%EC%9D%98_%EC%88%98)
- 조합 (/wiki/math/%EC%A1%B0%ED%95%A9)
- 블룸 필터 (/wiki/math/%EB%B8%94%EB%A3%B8_%ED%95%84%ED%84%B0)