공부중

  해시 함수는 임의의 길이를 갖는 메시지를 입력으로 하여 고정된 일정 길이의 해시 값(해시 코드)을 출력하는 함수이다. 일방향 해시함수는 해시 값을 고속으로 계산할 수 있다. 또한 이름처럼 일방향성을 가져야 하는데, 이는 해시 값으로부터 메시지를 역산할 수 없다는 것이다. 그리고 메시지가 다르면 해시 값도 달라야 한다. 이러한 성질은 무결성을 위해서 사용된다. 메시지가 조금이라도 다를 경우, 해시 값 또한 다른 값이 되어야 한다. 2개의 다른 메시지가 같은 해시 값을 갖는 것을 충돌(collision)이라고 한다. 일방향 해시함수를 무결성 확인에 쓰기 위해서는 충돌이 없어야 한다. 충돌을 발견하기 어려운 성질을 충돌 내성(collision resistance)이라고 한다. 암호학적 일방향 해시함수는 충돌 내성을 가져야 한다. 암호학적 해시함수는 프리이미지 저항성(preimage resistance), 제2프리이미지 저항성(second preimage resistance), 충돌 저항성(collision resistance)을 가져야 한다.

  프리이미지 저항성은 역상 저항성이라고도 한다. 해시 값 h=H(x)에 대해, x는 h의 선 이미지(preimage)라고 한다. H가 다대일 대응이므로 특정 해시 값 h에 대하여 여러 개의 선 이미지가 존재하게 된다. 프리이미지 저항성이란, 주어진 해시함수 h와 y=h(M)에 대하여 제3자가 y=h(M')를 만족하는 메시지 M'를 발견하는 것이 매우 힘들어야 한다는 성질이다. 제2프리이미지 저항성은 약한 충돌 내성이라고도 한다. 메시지를 쉽게 위조할 수 없게 하는 특성이다. 제3자가 메시지 M과 그것의 메시지 다이제스트 h(M)을 가로챘을 경우, h(M) = h(M')을 만족하는 또 다른 메시지 M'를 생성하기 매우 어려워야 한다는 성질이다. 충돌 저항성은 강한 충돌 내성이라고도 한다. 제3자가 동일한 메시지 다이제스트를 갖는 2개의 메시지 쌍을 구하지 못하게 하는 성질이다. 전자 서명에 이용되는 해시 함수는, 위 3가지 성질과, 해시 값을 고속으로 계산할 수 있다는 성질을 만족시켜야 한다.

  메시지 다이제스트(Message Digest) 알고리즘에는 MD2, MD4, MD5 세 가지가 있으며 RSA를 만든 Rivest가 개발한 것이다. 마지막 버전인 MD5는 메시지를 512 비트로 된 블록들로 나누고 128 비트짜리 메시지 다이제스트를 생성한다. 현재 128 비트짜리 메시지 다이제스트는 충돌 공격에 내성을 갖기 너무 짧다고 알려져있다. 최근에 사용되는 SHA(Secure Hash Algorithm)는 가장 많이 사용되는 해시 함수인데, MD4 해시 함수에 기반하여 만들어졌다. SHA-1은 해시 값이 160 비트이며, 그 뒤로 SHA-256, SHA-384, SHA-512 들이 나오게 되었다. SHA-256, SHA-384, SHA-512는 모두 SHA-2이다. SHA-1은 강한 충돌 내성이 깨졌다고 알려져 있다. SHA-3은 간단한 대체만으로도 SHA-2를 SHA-3으로 교체하는 것이 가능하게끔 해야하는 요구사항을 가지고 있다.