생일 문제

개요

사람이 임의로 모였을 때 그 중에 생일이 같은 두 명이 존재할 확률을 구하는 문제
생일이 같은 사람이 두 사람 이상 존재할 확률이 충분히 높아지게 하기 위해서 최소한 몇 명 이상의 사람이 모여야 하는지를 알아보는 확률론의 문제
생일의 가능한 가짓수는 366개이므로 366명 이상의 사람이 모인다면 비둘기집 원리에 따라 생일이 같은 두 명이 반드시 존재하며, 23명 이상이 모인다면 그 중 두 명이 생일이 같은 확률은 1/2를 넘는다.
얼핏 생각하기에는 생일이 366가지이므로 임의의 두 사람의 생일이 같을 확률은 1/366이고, 따라서 366명쯤은 모여야 생일이 같은 경우가 있을 것이라고 생각하기 쉽다.
그러나 실제로는 23명만 모여도 생일이 같은 두 사람이 있을 확률이 50%를 넘고, 57명이 모이면 99%를 넘어간다.
생일이 같은 두 사람을 찾는 것과 비슷하게, 암호학적 해시 결과가 같은(해시 충돌) 두 입력값을 찾는 것 역시 모든 입력값을 계산하지 않아도 충분히 높은 확률로 해시 충돌을 찾을 수 있다.
이러한 암호 공격을 생일 공격(birthday attack)이라고 부른다.