해시 함수

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
이름을 0~15 사이의 정수값으로 매핑하는 해시 함수의 예. “John Smith”와 “Sandra Dee”라는 두 키 사이에 충돌이 존재한다.

해시 함수(hash function)는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 알고리즘이다. 해시 함수에 의해 얻어지는 값은 해시 값, 해시 코드, 체크섬 또는 해시 등으로 불린다. 해시 함수는 결정론적으로 작동해야 하며, 따라서 두 해시 값이 다르다면 그 해시값에 대한 원래 데이터도 달라야 한다. (역은 성립하지 않는다) 해시 함수의 질은 입력 영역에서의 해시 충돌 확률로 결정되는데, 해시 충돌의 확률이 높을수록 서로 다른 데이터를 구별하기 어려워지고 검색하는 비용이 증가하게 된다.

해쉬함수중에는 암호학적 해쉬함수(Cryptographic Hash Function)와 비암호학적 해쉬함수로 구분되곤 한다.

암호학적 해쉬함수의 종류로는 MD5, SHA계열 해쉬함수가 있으며 비암호학적 해쉬함수로는 CRC32등이 있다.

암호학적 해쉬함수는 역상(pre-image), 제2역상(2nd preimage), 충돌쌍(collision)에 대하여 안전성을 가져야 하며 인증에 이용된다 . 암호학적 해쉬함수는 임의의 길이를 입력 받기는 하지만 MD Strength Padding할 때 길이정보가 입력되므로 최대 길이에 대한 제한이 있다. 예를 들어 패딩시 하위 8비트에 길이정보가 입력 되는 경우에는 해쉬가능한 최대 길이는 0xFF가 되어 255바이트가 된다.(실제 길이정보는 패딩방식에 따라 다를 수 있다)

특징[편집]

해시 함수의 가장 기본적인 성질은 두 해시 값이 다르다면 원래의 데이터도 다르다는 것이다. 이 특징은 해시 함수가 결정적이기 때문이다. 반대로 해시 함수는 단사 함수가 아니다. 같은 해시 값을 갖더라도 원래의 입력값이 같다는 것을 시사하지만 보장해주지는 않는다. 원래 입력의 한 비트만 바뀌더라도 해시 함수의 성질로 인해 해시 값은 크게 달라진다.

같이 보기[편집]