많은 암호 알고리즘들은 기본 구성 요소는 해시 함수라고 알려져 있는 것들이다. 해시 함수가 일방적이라는 성질은 알고리즘을 더 효과적으로 만든다. 암호학에서 사용되는 해시 함수 h는 입력으로 임의의 길이의 메세지를 받으며, 고정된 길이의 출력을 만든다. 또, 해시 함수는 다음과 같은 속성을 만족해야 한다.
1. 메세지 m이 주어졌을 때, 메세지를 줄이는 해시 함수 h(m)은 매우 빠르게 계산되어야 한다.
2. y가 주어졌을 때, h(m´) = y에서 m´을 찾는 것이 불가능해야 한다. 이러한 함수를 일방 함수(one-way function)라 한다.
3. h(m1) = h(m2)에서 메세지 m1, m2를 알아내는 것이 불가능해야 한다. 이러한 성질을 만족하는 함수 h를 충돌 회피에 강한(strongly collision-free) 함수라 한다.
일반적으로, 세번째 조건을 완전히 만족하는 것은 힘들다. 충돌 회피에 좀 더 관대한 경우, 이것을 약한 충돌 회피성(weakly collision-free)을 가진 함수라 하는데, H(x´) = H(x)인 경우, x´ ≠ x를 찾는 것이 불가능한 함수를 말한다.
Reference
Wade Trappe, Lawrence Washington, Introduction to Cryptograhphy with Coding Theory, Second Edition, PEARSON Education
Library/Cryptography