해시

Hash

• 하나의 문자열을 원래의 것을 상징하는 더 짧은 길이의 값이나 키로 변환하는 것. 값을 알아보지 못하고 복구하지 못하게 하려는 의도도 있고, 인덱싱을 빠르게 하기 위한 의도도 있다.
  • 예를 들어 어떤 규칙에 따라 abcd를 37, xyz를 28로 변환한다. (이 규칙에 따르면 어느 누가 언제 abcd를 변환 하더라도 항상 37이 나온다. 그리고 수학적으로 37로는 abcd를 유추할 수가 없다.) abcd, xyz라는 값을 숨기고 37, 28만 사용하기 위함일 수도 있다. 또는 숨길 의도는 없이 그냥 긴 대상을 호출하기 쉽도록 짧은 값으로 만들기 위함일수도 있다.

1 이름 표현

해시는 원래 해싱 또는 해시 함수를 통해 만들어진 값을 말한다. 예를 들어 위 정의 파트에서 예로 든, abcd를 37로 만드는 경우라면 37이 해시값이다. 따라서 기술의 이름을 표현하자면 "해싱" 또는 "해시 알고리즘" 등으로 불려야 하지만, 한국에서는 "해시"를 "해시 한다"라는 동사 형태로 쓰고 실무적으로 "해시"를 해싱 기술을 통칭하는 말로 사용하고 있다. 미국 등에서 말하는 해시, 즉 만들어진 결과 값은 우리는 "해시 값"이라고 부른다. 따라서 문서 제목을 그대로 "해시"로 유지한다.

• "해싱"으로 검색하면 "해시"로 연결된다.

2 간단한 원리

항상 같은 입력값에 대해 같은 출력값이 나오고, 출력값으로 입력값 복구가 불가능하다는 것에 대해 의구심을 가지는 경우가 있는데, 가장 간단하게 예를 들자면 "나머지"를 구하는 과정을 생각해보면 된다. 예를 들어

• 1234
• 5679
• 7899

이런 숫자를 해싱할 때 그냥 나누기 11을 해보자

• 1234%11 = 2
• 5679%11 = 3
• 7899%11 = 1

여기서 우리는 결과로 나온 2, 3, 1만 사용할 것이다. 그리고 우리가 "2"라고 했을 때 1234를 유추할 수 있을 가능성은 매우 낮다. 왜냐면 2가 나오는 경우는 1234 왜에도 13, 24, 35 등등 수 없이 많기 때문이다.

그럼 다른 입력값을 넣었음에도 같은 출력값이 여러번 나와서 충돌이 생기는게 아니냐? 라고 반문할 수도 있는데 그건 사실이다. 모든 해시는 충돌 가능성이 있다. 하지만 여러가지 수학적인 방법을 통해 더 알아보기 힘들고, 그럼에도 더 충돌이 적어지도록 만드는 것이 해시 알고리즘의 본질이다.

3 해시 함수 종류

• 제곱법 : 키값을 제곱한 후에 중간의 몇자리를 선택하고 그 중간 값을 주소로 이용
• 제산법 : 레코드 키 값을 소수로 나누어 나머지 값을 주소로 결정
• 중첩법(폴딩법) : 길이를 동일하게 여러 부분으로 나누고, 더하거나 XOR 하여 주소 이동
• 숫자분석법 : 각 숫자의 분포를 이용해서 균등한 분포의 숫자를 선택해서 사용
• 기수 변환법 : 주어진 키의 값을 다른 진법으로 변환하여 얻은 값을 주소로 사용
• 무작위 방법 : 난수를 발생, 탐색을 위한 해시의 경우 충돌이 발생하면 다음 난수를 이용

4 개념 및 용어

• 해시 함수(Hash function) : 데이터를 키로 변환하는 함수. 예를 들어 길고 복잡한 문자열을 짧고 단순한 문자열로 변경
• 홈 주소(Home address): 해시 함수에 의해 변환된 키값의 주소
• 해시 테이블(Hash table): 해시 함수가 키값을 생성할때 참조하는 테이블
• 버킷(Bucket): 하나의 주소를 갖는 파일의 한 구역. 버킷의 크기는 같은 주소에 포함될 수 있는 레코드의 수
• 슬롯(Slot): 한개의 레코드를 저장 할 수 있는 공간. 한 버킷 안에 여러개의 슬롯이 있다.
• 충돌(Collision): 다른 레코드가 같은 키를 가지는 충돌 현상. 레코드는 버킷의 다음 슬롯에 들어감
• 동의어(Synonym): 동일한 홈 주소로 인하여 충돌이 일어난 레코드의 집합. 키값이 같은 레코드의 집합으로, 동의어가 슬롯의 갯수보다 많으면 오버플로우가 일어날 수 있다.
• 오버플로(Overflow) : 한 홈 주소의 버킷 내에 더 이상의 레코드를 저장할 슬롯이 없는 상태

5 해시의 보안성

• 충돌 저항성: 동일한 출력을 산출하는 서로 다른두 입력을 계산적으로 찾기 어려운 성질
  • 강한 충돌 저항성: H(X) = H(Y) 인 서로 다른 임의의 두 입력 X, Y 를 찾는 것은 계산적으로 어려워야 한다.
  • 약한 충돌 저항성: X가 주어졌을 때 H(X) = H(Y) 인 X!=Y 것을 찾는 것은 계산적으로 어려워야 한다.
• 역상 저항성: 해시값 m에 대해 H(X) = m을 만족하는 X값을 찾기 어려운 성질
  • 제2역상 저항성: 해시값 m에 대해 h(x)=h(x'), x≠x'를 만족하는 x'를 찾는 것이 어려운 성질

6 대표적 해시 함수

• MD5
• SHA
• HAS
• RIPEMD(RMD)

7 오버플로우 처리 기법

• 개방 주소법(Open Addressing)
  • 선형 방법(Linear Method)이라고도 함
  • Collision이 발생했을 때 순차적으로 다음 빈 버킷을 찾아 저장
• 폐쇄 주소법(Close Addressing)
  • Overflow된 레코드들을 별도의 Overflow 영역에 저장하고 Chain(Pointer)으로 홈 버킷에 연결
  • Direct Chaining: 해시표 내의 빈 자리(Cylinder Overflow Area)에 Overflow 레코드를 보관
  • Indirect Chaining: 해시표와는 별도의 기억공간(Independent Overflow Area)에 Overflow 레코드를 보관
• 재해싱(Rehashing)
  • Collision이 발생하면 새로운 해싱 함수로 새로운 홈 주소를 구하는 방식

8 해시 탐색

레코드 키 값을 어떤 해싱 함수에 의해 주소로 변환시켜 해당 주소 위치에 레코드를 저장하는 방식으로 키 변환 값이 같은 경우 오버플로우 문제가 발생하지만 검색할 때 찾고자 하는 레코드의 키 값을 주소 변환에 의 해 해당 위치를 검색하므로 조사 횟수가 상당히 작은 방식

• 특정 데이터가 저장된 기억장소의 주소를 관리하기 위한 사상테이블(Mapping Table)을 정의하기 위해 해시를 사용
• 빠르다는 장점 때문에 운영체제 및 직접 접근파일을 구성하는데 사용된다.
• 사상 테이블의 용량부족으로 인한 Overflow가 발생할 수 있다.
• 동일한 주소를 만들어 내는 두 개 이상의 키 값인 동의어(Synonym)에 의해 충돌(Collision)이 발생 할 수 있다.