해싱(Hashing)

개념(Concept)

● 키(Key) 값을 해시 함수(Hash Function)라는 수식에 대입시켜 계산한 후 나온 결과를 주소로 사용하여 바로 값(Value)에 접근하게 할 수 하는 방법이다.

해시 함수(Hash Function)

● 키(Key) 값을 값(Value)이 저장되는 주소 값으로 바꾸기 위한 수식이다.

해싱(Hashing) 사용 분야

● 보안(Security) : 데이터의 위변조를 막기 위해 전자서명이나 보안 알고리즘에 사용

● 자료 구조(Data Structure) : 기억 공간에 저장된 정보를 보다 빠르게 검색하기 위해 절대주소나 상대주소가 아닌 해시 테이블(Hash Table)을 생성하는 방식

해싱(Hashing) 구현 기법

● 정적 해싱(Static Hashing)

- 고정 크기의 배열을 이용한 방법이다.

- 버킷(Bucket) 주소의 집합을 고정한다.

- 현재 파일의 크기를 고려하여 해시 함수(Hash Function)을 결정한다.

- 미래의 어떤 시점을 기점으로 파일 크기를 예상하여 해시 함수(Hash Function)를 결정한다.

- 파일의 크기가 커짐에 따라 주기적으로 해싱(Hashing) 구조를 재구성해야 한다.

- 구현이 쉽고 간단하다.

- 버킷(Bucket)의 크기를 작게 잡을 경우 충돌(Collision)의 우려가 있고, 크게 잡을 경우 메모리 또는 디스크 낭비의 우려가 있다.

- 데이터의 증감에 따라 해싱(Hashing) 구조를 재구성해야 하기 때문에 추가적인 리소스가 필요하다.

- 데이터의 증가에 따라 검색성능이 떨어진다.

- 제산법(Division)

· 나머지 연산자를 이용하여 버킷 주소(인덱스)를 계산하는 방법

· 버킷 주소(인덱스) = 키(Key) 값 % (전체 버킷 크기)

· 해시된 주소가 고르게 분포되지 않을 수 있기 때문에 일반적으로 전체 버킷의 크기를 소수(Prime Number)로 하여 성능을 향상시킨다.

· 부하율(Load Factor, 전체 버킷에서 사용중인 버킷의 비율)는 70~80%가 적당하다.

<정적 해싱 - 제산법>

- 중간 제곱법(Mid-Square)

· 키(Key) 값을 제곱한 후 결과 값의 중간 부분에 있는 몇 비트만을 선택하여 버킷 주소(인덱스)로 사용

· 제곱된 결과의 중간 비트는 일반적으로 모든 키(Key) 값의 모든 문자에 영향을 받기 때문에 키(Key)를 구성하는 일부 문자가 같을지라도 서로 다른 결과 값을 가질 확률이 높다.

· 버킷 주소(인덱스)를 얻기 위해 사용되는 비트의 수는 전체 버킷의 크기에 따라 달라지고 중간 부분의 자릿수를 n이라 하면 각 키(Key) 값들이 가지는 범위인 전체 버킷의 크기는 이 된다. (2진수를 사용하기 때문)

<정적 해싱 - 중간 제곱법>

- 폴딩법(Folding)

· 키(Key)를 마지막 부분을 제외한 모든 부분의 길이가 동일하게 여러 부분으로 나누고, 이들 부분을 모두 더하거나 XOR 연산을 하여 버킷 주소(인덱스)로 이용하는 방법

· 이동 폴딩(Shift Folding) : 각 부분의 값을 계산하기 위해 마지막을 제외한 모든 부분을 이동시켜 최하위 비트(LSB)가 마지막 부분의 자리와 일치하도록 우측 끝을 맞추어 더한 값을 버킷 주소(인덱스)로 사용하는 방법

<정적 해싱 - 이동 폴딩>

· 경계 폴딩(Boundary Folding) : 원래의 키(Key) 값을 여러 부분으로 나눈 후, 나누어진 각 부분의 경계선을 종이 접듯이 접어 역으로 정렬한 다음 같은 자리에 위치한 수를 더한 값을 버킷 주소(인덱스)로 사용하는 방법

<정적 해싱 - 경계 폴딩>

- 숫자 분석법(Digit-Analysis)

· 키(Key)를 구성하는 수들이 모든 키들 내에서 각 자리별로 어떤 분포인지를 조사하여 비교적 고른 분포를 나타내는 자릿 수를 필요한 만큼 선택하여 버킷 주소(인덱스)로 사용하는 방법

· 파일의 키(Key) 값이 이미 알려진 정적 파일(Static File)인 경우에 유용하며, 삽입과 삭제가 빈번히 발생하는 경우에는 비효율적이다.

<정적 해싱 - 숫자 분석법>

- 기수 변환법(Radix-Exchange)

· 어떤 진법으로 변환된 키(Key)를 다른 진법으로 간주하고 키(Key)를 변환하여 버킷 주소(인덱스)를 얻는 방법

· 배열의 크기가 10의 거듭제곱으로 표현되어 변환된 해당 버킷 주소(인덱스)가 배열의 크기를 초과할 때는 버킷 주소(인덱스)의 최하위 자리부터 배열의 크기가 허용하는 거듭제곱(자릿수)만큼 취하여 버킷 주소(인덱스)로 사용

<정적 해싱 - 기수 변환법>

- 무작위 방법(Pseudo-Random)

· 난수 발생 프로그램을 이용하여 난수를 반생시켜 키(Key)의 버킷 주소(인덱스)를 결정하는 방법

· 보통 난수는 1보다 작은 양의 실수(0<=k<1)로 산출되므로, 배열의 크기인 n을 산출된 난수에 곱하여 (0<=k * n<=(n - 1))까지의 범위 값으로 변환하여 사용하며, 만약 충돌이 발생하게 되면 그 다음 난수를 버킷 주소(인덱스)로 사용

<정적 해싱 - 무작위 방법>

● 동적 해싱(Dynamic Hashing)

- 데이터의 증감에 따라 배열의 크기를 동적으로 변화시키는 방법이다.

- 오버플로우(Overflow) 발생시 테이블의 크기를 2배수로 확장시킨다.

- 버킷(Bucket)의 수를 고정시키지 않고 필요할 때 늘리거나 줄인다.

- 해싱된 키(Key)를 버킷 주소(인덱스)로 사용하는 이진 트리(Binary Tree)를 동적으로 변환하여 사용한다.

- 데이터의 증감에 따라 버킷(Bucket)을 쪼개거나 합치는 과정을 반복한다.

- 버킷(Bucket)을 포인터로 가리키는 버킷 주소(인덱스) 테이블을 생성/유지해야한다.

- 동적으로 변하는 다중 레벨 인덱스(Multi-level Index)를 관리한다.

- 로직이 복잡하다.

- 데이터가 증가해도 검색의 성능이 유지된다.

- 메모리 또는 디스크의 낭비를 줄일 수 있다.

- 연결이나 링크(Link) 같은 것이 사용되지 않기 때문에 접근시간(Access Time)을 일정하게 유지할 수 있다.

- 버킷 주소(인덱스) 테이블을 생성해야 하는 부담이 있다.

- 버킷(Bucket)을 쪼개거나 합치는 과정 중에 부하가 발생한다.

- 버킷(Bucket)을 직접 검색하기보다는 버킷 주소(인덱스)를 통해 간접적으로 검색하는 것이기 때문에 추가적인 검색 횟수가 필요하다.

- 버킷 주소(인덱스) 테이블의 크기를 2배로 늘리는 과정은 시간이 많이 걸리는 작업이다.

- 오버플로우(Overflow)가 발생한 버킷(Bucket)을 2개의 버킷(Bucket)으로 분할한다. 분할법은 해시된 키(Key)의 다음 유효 비트가 0인 키(Key)를 한 버킷(Bucket)에 두고 1인 키(Key)를 다른 버킷(Bucket)에 둔다.

- 디렉터리(Directory)는 각 버킷(Bucket)에 대응하는 비트 열 형태를 구분할 수 있도록 이진 트리(Binary Tree) 형태로 구성한다. 즉, 레벨 i에 있는 노드(Node)는 해시된 키(Key)의 i번째 비트가 0에 해당하는 왼쪽 포인터(Pointer)와 1에 해당하는 오른쪽 포인터(Pointer)를 갖는다. 단, 리프 노드(Leaf Node)는 값을 저장하는 버킷 주소(인덱스)를 갖는다.

- 특정 키(Key)를 검색하고자 할 경우, 해시된 키(Key, 이진 비트열)를 기준으로 디렉터리(Directory)를 검색하여 버킷 주소(인덱스)를 얻는다.

● 확장 해싱(Extendible Hashing)

- 동적 해싱(Dynamic Hashing) 기법에서 가장 많이 사용하는 방법으로 트리의 깊이가 2인 특별한 경우다.

- 사용할 수 있는 비트열을 모두 사용하지 않고 일부 비트열만을 사용한 후 더 많은 버킷(Bucket)이 필요한 경우 비트열을 하나씩 추가한다.

- 해싱(Hashing) 구조의 재구성이 한 번에 하나의 버킷(Bucket)에서만 발생하므로 상대적으로 부하가 적다.

- 부가적인 접근 구조(Directory)를 저장하며, 해시 함수(Hash Function) 적용 결과인 이진수 표현을 기반으로 한다.

- 데이터의 수에 따라 버킷(Bucket)의 수가 변한다.

- 디렉터리(Directory) : 2d(d : 전역 깊이)개의 버킷 주소(인덱스)를 갖는 배열이며, 해시된 키(Key)의 처음 d개 비트를 디렉터리(Directory) 배열의 인덱스 값으로 결정하는데 사용한다.

- 2d개의 디렉터리(Directory) 엔트리는 서로 다른 버킷 주소(인덱스)를 유지할 필요가 없다.

- 처음 d'(d' : 지역 깊이)개의 비트 값이 갖는 키(Key)가 하나의 버킷(Bucket)에 저장될 수 있으면 여러 디렉터리(Directory) 엔트리가 같은 버킷 주소(인덱스)를 유지하며, 각 버킷(Bucket)내의 해시된 키(Key)가 기반으로 하는 비트의 수 d'를 지역 깊이라고 한다.

- 지역 깊이 d'과 전역 깊이 d가 같은 버킷(Bucket)에서 오버플로우(Overflow)가 발생할 경우, 디렉터리(Directory) 배열 내의 엔트리 수는 2배가 된다.

- 어떤 키(Key)를 삭제한 후, 모든 버킷(Bucket)에 대해 d > d'인 경우 디렉터리(Directory) 배열내의 엔트리 수는 절반이 된다.

- 대부분의 키(Key)의 검색은 2개의 블록 접근(디렉터리(Directory)에 대한 블록 접근, 버킷(Bucket)에 대한 블록 접근)을 필요로 한다.

- 장점

· 파일의 크기가 크더라도 레코드를 접근하기 위해 디스크 접근이 두 번을 넘기지 않는다.

· 버킷 주소(인덱스) 테이블의 크기가 작으므로 저장공간이 절약된다.

- 단점

· 버킷 주소(인덱스) 테이블을 생성해야 하는 부담이 있다.

· 각각의 버킷 주소(인덱스)가 실제의 버킷(Bucket)을 포인트하고 있으므로 데이터의 숫자가 적으면 오히려 디스크의 낭비가 발생할 수 있다.

· 버킷(Bucket)을 버킷 주소(인덱스)를 통해 간접적으로 검색하므로 추가적인 검색이 필요함

<확장 해싱1>

<확장 해싱2>

보안(Security) 분야에서의 해싱(Hashing)

- 해당 부분은 나중에 추가로 다루면서 수정 -

● 위에 설명된 해싱(Hashing) 구현 기법은 자료 구조(Data Structure) 분야에서 많이 사용하는 방법이다.

● 보안(Security) 분야에서는 데이터의 무결성과 메시지 인증에 사용하며 정보 보호의 여러 메커니즘에 사용된다.

● 고정되지 않은 임의의 길이의 비트열을 입력으로 하여 고정된 길이의 해시 코드(Hash Code)를 생성하여 암호학적으로 풀 수 없는 키(Key)를 만들어 내는 것이다.

● 사용 용도

- 전자 서명 : 메시지 전송시 송신자가 전자 서명을 하여 위변조를 막음

- 부인 방지 : 메시지 수신자가 수신한 메시지를 부인하거나 이의를 제기할 경우를 방지하기 위한 서비스

● 해시 함수(Hash Function)의 조건

- 입력의 크기에 제한이 없는 가변적인 길이를 수용해야 한다.

- 출력은 고정된 길이를 가져야 한다.

- 해시 함수(Hash Function)의 입력은 어떠한 값이 들어와도 계산이 쉬워야 한다.

- 해시 함수(Hash Function)는 일방향성(One-way Function, 역변환 불가)이어야 한다.

- 해시 함수(Hash Function)는 충돌(Collision)이 없거나 적어야 한다.

● SNEFRU

- 1990년 R.C. Merkle에 의해 제안됨

- 128/254 bit 암호화 알고리즘

● N-HASH

- 1989년 일본의 NTT의 미야구치 등이 발표함

● MD4

- 1990년 Ron Rivest에 의해 개발된 MD5의 초기 버전

- 입력 데이터로부터 128bit 메시지 축약을 만듬으로서 데이터 무결성을 검증하는데 사용되는 알고리즘

※ MD4의 설계 원칙

1) 수학적인 가정없이 안전한 해시 함수(Hash Function)를 설계

2) 해시 함수(Hash Function)의 수행 속도는 가능한 빨라야 함, 특히, 소프트웨어로 구현했을 때의 속도를 고려함

3) 알고리즘이 단순하며 구현이 용이해야 함

4) Little-Endian 구조(Word의 최하위 바이트가 low-address 바이트 위치에 있는 구조)를 고려한 알고리즘을 설계함.

● MD5

- 1992년 Ron Rivest에 의해 개발됨

- 널리 사용되는 해시 알고리즘이지만 충돌 회피성에서 문제점이 있다는 분석이 있으므로 기존의 응용과는 호환으로만 사용하고 더 이상 사용하지 않도록 하고 있음

※ MD4와의 차이점

1) MD4는 16단계의 3라운드를 사용하나 MD5는 16단계의 4라운드를 사용함

2) MD4는 각 라운드에서 한번씩 3개의 기약 함수를 사용하지만 MD5는 각 라운드에서 한번씩 4개의 기약 논리 함수를 사용함

3) MD4는 마지막 단계의 부가를 포함하지 않지만 MD5의 각 단계는 이전 단계의 결과에 부가됨.

● SHA(Secure Hash Algorithm)

- 1993년 미국 NIST에 의해 개발되었고 가장 많이 사용되고 있는 방식

- SHA1은 DSA에서 사용하도록 되어 있으며 많은 인터넷 응용에서 기본 해시 알고리즘으로 사용됨

- SHA256, SHA384, SHA512는 AES의 키(Key) 길이인 128, 192, 256 비트에 대응하도록 출력 길이를 늘린 해시 알고리즘임

● RMD

- RMD128, RMD160은 RIPE 프로젝트의 RIPEMD나 MD4, MD5를 대신하기 위하여 고안된 해시 알고리즘임

- 128 비트의 출력을 내는 RMD128은 역시 충돌 회피성에서 문제점이 있음

- RMD160은 효율성은 떨어지지만 안전성 높인 것으로 많은 인터넷 표준에서 널리 채택되고 있음

- RMD256과 RMD320은 각각 RMD128과 RMD160을 확장한 것임

참고 자료(References)

[Naver 재조(whwo161) 블로그] https://blog.naver.com/whwo161/221075172430

[iLiFO Ji-Dum 해싱 개요] http://www.jidum.com/jidums/view.do?jidumId=163

[Naver 기루(skyjjw79) 블로그] http://blog.naver.com/PostView.nhn?blogId=skyjjw79&logNo=220875535595&parentCategoryNo=&categoryNo=61&viewDate=&isShowPopularPosts=true&from=search

[KimKyungKun SlidesShare 해싱(Hashing)] https://www.slideshare.net/KimKyungKun/hashing-10748635

[Naver 코로문(koromoon) 블로그] https://blog.naver.com/PostView.nhn?blogId=koromoon&logNo=120172847516&proxyReferer=https%3A%2F%2Fwww.google.co.kr%2F