21.08.10 생일 공격

암호해독공격 중 하나인 생일 공격에 대해 알아보겠다. 

 

사람이 여럿 모였을 때 그 중에 생일이 같은 두 명이 존재할 확률을 생각해보자. 

그 과정은 다음과 같다. 

칠판에 365일을 쓰고 한 사람씩 자신의 생일을 지워나간다고 하면

첫번째 사람이 나와서 자기 생일을 지울 확률은 365일 중에 365일을 선택하므로 확률은 1이다. 

다음 사람이 나와서 첫번째 사람의 생일을 제외한 생일을 지울 확률은 364/365이다. 

n명의 사람들 중 생일이 모두 다를 확률은 아래와 같이 표현할 수 있다. 

최종적으로 생일이 같은 사람이 둘 이상 있을 확률은 전체 확률 1에서 생일이 모두 같지 않을 확률을 제외하므로 

따라서 365명보다 적은 수인 최소 23명만 모여도 생일이 같은 두 사람이 있을 확률이 50%가 넘고 

57명이 모이면 99%를 넘는 것을 확인할 수 있다. 

 

이와 비슷하게 같지 않은 서명문 M과 서명문 M'가 같은 해쉬값 H를 가질 확률을 생각해볼 때, 

(이것을 해시 충돌이라 하고 M과 M'을 충돌쌍이라고 한다.)

 

k비트 해시 함수의 충돌을 발견하기 위해서는 평균적으로 모든 가짓수인 2^k 보다 π/2(2^(k/2))가지의 입력값만 조사하면 되므로

계산 횟수를 크게 감소시킬 수 있다. 이와 같이 해시값이 같은 다른 입력값을 빠르게 찾음으로써 생일 공격을 진행할 수 있다.