[TIL] 해시값, 해시함수, 해시테이블

김형주·2021년 4월 24일
0

해시테이블(hash table)

이게 뭐냐 하면 hashtag(#) 모양으로 생긴 table일 것이다.라고 유추했는데 맞는지 확인해봐야겠다.
전혀 아니었다. 해시테이블이라는 자료구조를 알아보기전에 해시(hash)라는 것에 대해 먼저 알아보는 시간을 가지자.

hash? 해시?

해시넷이라는 사이트에서는 이렇게 정의를 내리고 있다.

해시(hash)란 다양한 길이를 가진 데이터고정된 길이를 가진 데이터로 매핑(mapping)한 값이다.

그래서 이게 뭔 쌉소린가 싶기는 한데(솔직히 해시계가 먼저 생각났다.), 쉽게 말하고자 하면 이렇다. 어떤 값(key)를 받아서 이걸 hashingfunction(해시함수)에 집어넣어서 어떤 알고리즘에 의해서 뚝딱하고 같은 길이의 데이터로 변환된다는 말이다. 결국엔 이렇게 만들어진 값이 해시코드(hash code), 혹은 해시값(hash value)이라고 부르는 것이다. 단방향 암호화 기법의 일종인데, 이게 또 단방향 암호화라는 말을 꺼내니까 새삼 파고들기 무서워진다. 일단 이해한 이야기를 그림으로 나타내보자.

해시함수(hashing function)


자 그럼 이제 해시함수가 뭔지 알았다. 실제로 내가 구현할 수는 없겠지만, 어떤 값을 가지고 최종적으로 통일된 포맷의 어떠한 결과물을 내는 것. 그리고 그 결과물을 가지고 원래 넣었던 input을 가지고 뚝딱뚝딱해서 동일한 길이의무슨 값(해시코드)을 만들어내는 것이다.

해시함수의 특징

  • 입력 값이 일부만 변경되어도 전혀 다른 해시값을 출력한다. = 이걸 눈사태 효과라고 부른단다.
  • 입력값 상관없이 고정된 길이의 해시값을 출력한다.
  • 복호화 불가능하다. [단방향 암호화 기법 - 암호화는 되는데, 복호화는 안됨]
  • 복잡하지 않은 알고리즘으로 구현되기 때문에 상대적으로 CPU, 메모리 같은 시스템 자원을 덜 소모한다.
  • 같은 입력값에 대해서는 같은 출력값을 항상 보장한다.

위 그림에 나와있는 것과 동일한 내용이다. 암호화 기법이므로, 동일 input에 대해선 같은 해시값을 내야하고 다른 input에 대해서는 해시값이 완전 달라야 한다. 복호화가 불가능하고, 알고리즘 자체는 가볍게 짜여지는 모양이다.

해시 함수의 문제점

  • 해시함수의 특징 중 자원소모가 적어 처리속도가 빠르다고 했지만, 이건 장점이자 단점인데,
    무차별 대입 공격을 받을 수 있기 때문이다. (해시값이 암호라고 하면, 암호를 찾기위해 해시함수에 무차별적으로 값을 대입해서 찾으려고 할 수 있다는 말 같다.)
  • 레인보우 테이블 공격
    : 해시함수(MD-5, SHA-1, SHA-2)를 사용하여 만들어낼 수 있는 값들을 대량으로 저장한 표다.
    : MD-5가 쉽게 복호화될 수 있다는 것을 보여준 해킹비법 중 하나이다.
    이 얘기는 결과로 나올 수 있는 해시값들을 저장해놓고, input을 대입해가면서 해시를 예측하는 방법인 것 같다.

MD-5 (Message-Digest algorithm 5)

  • 임의의 길이를 입력받아 128bit 길이의 해시값을 출력한다.
  • 단방향 알고리즘
  • 현재는 심각한 보안문제로 인하여 MD5를 보안 관련 용도로 사용하지 않는다.
  • 2008년에는 MD5의 결함을 이용해 SSL 인증서를 변조하는 것이 발견되었다.

사용 목적

해시함수의 가장 큰 특징은 입력값이 일부만 변경되도 완전 다른 값이 나오는 함수다. 이러한 특징으로 인해, 해시함수를 사용하는 목적은 메시지의 오류나 변조를 탐지할 수 있는 무결성이다. 이 기술을 사용하는 대표적인 예는 블록체인이라고 한다. 그 외에 비밀번호, 전자서명, 전자투표, 전자상거래 등에서 사용된다.

그럼 해시테이블은 뭔데?


위에서 본 것처럼 해시함수는 암호화하는 과정에도 쓰인다는 것을 알았는데, 해시함수가 포함된 해시테이블이라는 것은 다른 것을 떠나서 일단은 해시값을 이용한 자료구조라는 것이다.

이거보다가 갑자기 희소배열 공부하고싶어서 떠남

profile
만물에 관심이 많은 잡학지식사전이자, 새로운 도전을 꿈꾸는 주니어 개발자 / 잡학지식에서 벗어나서 전문성을 가진 엔지니어로 거듭나자!

1개의 댓글

comment-user-thumbnail
2021년 4월 24일

지옥의 해시테이블

답글 달기