Birthday Problem
해시 함수의 목적과 특징, 해시값의 안전한 길이, 생일 문제로 알아보는 해시 함수중에서의 의의
Hash Function
- 해시 함수의 목적: 임의 길이의 정보를 하나의 고정 길이 해시값 으로 매핑하는 것, 정보 Abstract라고도 한다. 정보 요약은 인증부호로 볼수도 있으며 정보 인증을 완성한다.
해시 함수의 강건함
- 해시함수가 $h$일때, 정보 특성 Plaintext 공간$X$중, 정보 $x\in X$일때, 계산상 $h(x)=h(x’)$이 되게하는, $x$와 다른 $x’$은 거의 찾을 수 없다
- 해시함수가 $h$일때 $h(x)=h(x’)$를 만족하고 $x’$가 $X$에 속하지 않으며, 동시에 $x$와 서로 다른 $x’$를 찾는것은 어렵다
- 단방향성 해시 함수 $h$가 단방향성이라는 것은 $h$의 역함수 $h^-1$를 통해 해시값$h(x)$의 정보 original text $x$를 얻는 것
해시값의 안전 길이
생일 문제
이것은 생일 역설이라고도 한다. 만약 한 공간에 23명 혹은 23명 이상이 있을 때, 적어도 두사람의 생일이 같을 확률은 $50\%$이상이다. 60명 혹은 그 이상일때는 이러한 확률은 $99%$이상이다.
- 윤년의 특수성을 고려하지 않고, 방 안의 모든 사람의 생일이 모두 같지 않을 확률은,
- 첫 번째 사람이 생일 겹치지 않을 확률은 $\frac{365}{365}$이고,
- 두 번째 사람이 생일이 겹치지 않을 확률은 $1-\frac{1}{365}이고, …,
- $n$ 번째 사람은 $1-\frac{n-1}{365}$으로,
- 모든 사람의 생일이 겹치지 않을 확률:
\(E=1*(1-\frac{1}{365})*...*(1-\frac{n-2}{365}*(1-\frac{n-1}{365})\),
- 반면 겹치는 경우의 확률 $P=1-E$로, $n=23$일때, $P\approx 0.507$; $n=100$일 때, $P=0.9999996$이다
해시 함수에 관한, 생일 역설의 의의
- 길이 $n$의 해시값에 대해, 한번 충돌의 측정 횟수가 $2^2$가 아니라, 대략 $2^{n/2}$ 인 상황이 발생할수있다
- 어떤 길이 40의 해시값은 안전하지 않을 것이고, 그 이유는 대략 100만개의 랜덤 해시값중 하나의충돌을 찾아낼 확률은 $50%$이기 때문이다
- 정보 요약의 길이는 128bit 보다 작아선 안된다.