어떤 메세지 전체에 대해서 서명을 하는 것은, 메세지가 길 경우 불리한 점이 많다. 이와 같은 문제를 해결하기 위해, 해시 함수가 사용된다. 즉, 서명은 메세지 자체보다는 메세지의 해시값에 대해서 이루어진다.
해시 함수 h(m)은 알려져 있으며, Alice는 h(m)을 계산한다. h(m)은 메세지 m에 비해서 크기가 줄어든 결과를 출력하며, h(m)에 대한 서명을 훨씬 빨리 이루어진다. Alice는 sig(h(m))을 계산하며, 이것을 원래의 메세지 m에 대한 서명으로 사용하게 된다. 즉, (m, sig(h(m))은 원래의 메세지의 서명을 대신하게 된다.
이와 같은 방법은 안전한가? 예를 들어, Eve가 Alice의 서명된 메세지 (m, sig(h(m))을 가지고 있다고 해보자. Eve는 Alice의 메세지 m을 위조한 m1을 가지고 있다고 하자. m1을 유효한 Alice의 서명으로 만들기 위해서는, sig(h(m)) ≡ sig(h(m1))을 알아야 하며, 부분적으로 h(m) ≡ h(m1)을 찾아야 한다. 하지만 해시 함수는 once-way function이며, 더구나 강한 충돌 회피성을 가진 해시 함수(strongly collision-free)라면, Eve는 이 서명에 대한 m = m1을 찾을 수 없다.
물론, Eve는 sig(h(m1))을 새로 만들어낼 수 있지만, 이것은 의미없다.
Reference
Wade Trappe, Lawrence Washington, Introduction to Cryptography with Coding Theory, Second Edition, PEARSON Education
해시 함수 h(m)은 알려져 있으며, Alice는 h(m)을 계산한다. h(m)은 메세지 m에 비해서 크기가 줄어든 결과를 출력하며, h(m)에 대한 서명을 훨씬 빨리 이루어진다. Alice는 sig(h(m))을 계산하며, 이것을 원래의 메세지 m에 대한 서명으로 사용하게 된다. 즉, (m, sig(h(m))은 원래의 메세지의 서명을 대신하게 된다.
이와 같은 방법은 안전한가? 예를 들어, Eve가 Alice의 서명된 메세지 (m, sig(h(m))을 가지고 있다고 해보자. Eve는 Alice의 메세지 m을 위조한 m1을 가지고 있다고 하자. m1을 유효한 Alice의 서명으로 만들기 위해서는, sig(h(m)) ≡ sig(h(m1))을 알아야 하며, 부분적으로 h(m) ≡ h(m1)을 찾아야 한다. 하지만 해시 함수는 once-way function이며, 더구나 강한 충돌 회피성을 가진 해시 함수(strongly collision-free)라면, Eve는 이 서명에 대한 m = m1을 찾을 수 없다.
물론, Eve는 sig(h(m1))을 새로 만들어낼 수 있지만, 이것은 의미없다.
Reference
Wade Trappe, Lawrence Washington, Introduction to Cryptography with Coding Theory, Second Edition, PEARSON Education