생일의 역설

"생일의 역설"은 확률 이론에서 사용되는 개념으로, 예상보다 적은 수의 무작위 선택이 있을 때 일치 또는 중복 항목이 나타날 확률이 높다는 것을 설명합니다. 이는 "생일 문제"라고도 알려져 있으며, 이 이름은 다음과 같은 상황에서 유래되었습니다:

예를 들어, 365일 중에서 어떤 특정한 날과 같은 생일을 가진 사람을 찾으려면 평균적으로 약 183명의 사람을 확인해야 할 것입니다. 하지만 어떤 두 사람이 같은 생일일 확률은 23명의 사람만 모여도 약 50%에 이릅니다. 이는 많은 사람들이 처음에 예상할 수 있는 것보다 훨씬 적은 수입니다. 이러한 현상을 "생일의 역설"이라고 부릅니다.

컴퓨터 과학과 암호학에서는 "생일의 역설"이 중요한 역할을 합니다. 특히, 해시 함수의 충돌을 찾는데 이용되며, 이를 "생일 공격"이라고 부릅니다. 해시 함수는 주어진 입력에 대해 고정된 크기의 출력(해시값)을 생성하는 함수입니다. "생일의 역설"에 따르면, 해시 함수의 출력 공간의 크기의 제곱근에 비례하는 수의 무작위 입력을 선택하면 같은 해시값을 가진 두 개의 입력(충돌)을 찾을 확률이 높아집니다. 이러한 성질을 이용하여 해시 함수의 보안성을 공격하는 경우가 있습니다.