해시 (Hash algorithm)

해시란 무엇인가

해시는 다음을 가리키는 말이다.

해시 함수(hash 函數) 또는 해시 알고리즘은 임의의 데이터로부터 짧은 ‘전자 지문’을 만들어내는 방법이다.
해시 값은 데이터를 해시 함수로 가공한 결과를 말한다.
해시 테이블은 자료 구조의 일종으로, 고유 키 값과 그에 따른 자료 값을 짝지을 때 해시 함수를 이용한다.

http://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C

해시 함수(hash function) 또는 해시 알고리즘(hash algorithm)은 임의의 데이터로부터 일종의 짧은 “전자 지문”을 만들어 내는 방법이다. 해시 함수는 데이터를 자르고 치환하거나 위치를 바꾸는 등의 방법을 사용해 결과를 만들어 내며, 이 결과를 흔히 해시 값(hash value)이라 한다. 해시 함수는 결정론적으로 작동해야 하며, 따라서 두 해시 값이 다르다면 그 해쉬값에 대한 원래 데이터도 달라야 한다. (역은 성립하지 않는다) 해쉬 함수의 질은 기대되는 입력 영역에서 얼마나 적은 해시 충돌(서로 다른 두 데이터의 해시 값이 같은 경우)을 일으키느냐로 결정되는데, 충돌이 많이 날수록 서로 다른 데이터를 구별하기 어려워지고 데이터를 검색하는 비용을 늘리기 때문이다.

http://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%95%A8%EC%88%98


쉽게 말해서 해시는, 데이터를 짧게 함축하여 나타내는 것이라고 볼 수 있다.
해시 알고리즘으로는 우리가 자주 사용해 왔던 MD, SHA 등이 있으며 연관 배열도 내부적으로 간단한 해시 알고리즘을 사용한다. 데이터베이스의 인덱스 역시 해시 알고리즘 덕분에 고속 검색이 가능하게 되었다.

MyHash 라는 해시 함수가 있다고 가정하자.
MyHash 함수는 데이터를 계산하여 나오는 결과 해시 값이 0부터 255까지 한정되어 있고, 입력된 데이터의 모든 바이트를 더해서 256으로 나눈 나머지 값을 해시 값으로 쓰인다고 가정한다.

이 함수를 이용하여 해시 값을 구해보면 아래와 같이 단문이든 장문이든 결과 값은 256 미만으로 출력 된다.

195
199
31

만약 PHP가 MyHash 함수를 사용하여 연관 배열을 구현하였다면

hsh 배열의 메모리는 다음과 같은 형태로 저장된다고 볼 수 있다.

이제 hsh 연관배열에서 ‘abcdefghijklmnopqrstuvwxyz’라는 메모리에 저장된 값을 꺼내보자.

우선 abcdefghijklmnopqrstuvwxyz 라는 문자열의 해시 값을 구한다. (결과: 31)
hsh의 배열에서 31번째에 위치한 데이터를 꺼내서 출력한다.

echo $hsh[31];

이처럼 같은 입력 데이터를 해시하면 같은 결과가 나오는 특징이 있어서 해시 값이 같으면 원래의 입력 데이터도 같다고 볼 수 있으나 각 해시 알고리즘(MD5 해시 값은 16바이트(128비트), SHA1 해시 값은 20바이트(160비트)의 어마어마한 결과가 나옴)에 따라서 보장해 주진 않는다. 특히 위에서 예를 든 MyHash는 더욱 더. (MyHash 함수의 ‘cd’의 해시 값은 ‘dc’의 해시 값과 같다)

아무튼 이러한 해시 특징을 이용하면 여러가지 응용이 가능하다.
어떤 다운로드 사이트는 파일의 MD5 해시 값을 명시 하여 다운로드된 파일을 검증하기 위한 용도로 쓰기도 하고, 전자 서명에서는 원문의 내용이 변조되었는지 확인할 수 있도록 해시 알고리즘을 이용한다.

지금까지 해시 알고리즘에 대해서 간단히 설명하였다.
말도 안되는 코드들로 설명했지만, 이해하기 쉽도록 예를 든 것 뿐이며 실제로 MD와 SHA 같은 해시 함수들은 매우 복잡한 연산을 통해 해시 값 충돌이 적고, 충돌되는 서로 다른 데이터의 해시 값을 찾기도 쉽지 않다.

무엇이든 완벽한 것은 없다. 이러한 해시 함수들도 취약점이 드러나고 있는데 특히 MD5 해시는 1996년부터 결함이 발견되었고 SHA1에 대한 공격도 발견되어 보안상 중요한 구현은 SHA2 이상의 알고리즘을 사용할 것을 권장하고 있다.

]]>

도큐멘트 에 올린 글

댓글 남기기