‘생일 문제’로 보는 충돌 저항성

충돌 저항성은 소위 ‘생일 문제’에서도 의미를 찾을 수 있습니다. ‘생일 문제’란 임의로 모인 사람들이 있을 때, 그중 생일이 같은 두 명이 있을 확률을 구하는 것입니다. 1년은 365일이므로 생일은 365가지이고, 두 사람의 생일이 같을 확률은 1/365이기에 365명이 모여야 생일이 같은 두 명이 있을 것이라고 생각하기 쉽습니다. 그러나 실제로는 23명만 모여도 생일이 같은 두 명이 있을 확률은 50%가 넘습니다. 57명이 모이면 99%가 넘습니다. 생일이 같은 두 명을 찾는 것과 마찬가지로 해시 결과가 같은 두 입력 값을 찾는 확률도 충분히 높습니다. 이런 관점에서 암호 해독하는 것을 ‘생일 공격(Birthday Attack)’이라고 합니다.