해시 함수 (Hash)
I. 고정 길이 암호화, 해시 함수
해시 함수의 개념
해시는 키 값에서 레코드가 저장되어 있는 주소를 직접 계산 후 산출된 주소로 바로 접근 가능하게 하는 방법 (자료구조)
하나의 문자열을 원래의 것을 상징하는 고정된 길이의 값이나 키로 변환하는 방식 (암호화 정의)
해시 함수의 구성 원칙
| 구성 원칙 | 설명 |
|---|---|
| 압축성 (Compression) | 다양한 가변 길이의 입력에 고정된 크기의 결과값을 출력해야 함 |
| 효율성 (Efficiency) | 어떤 입력 값에 대해서도 해시 값을 구하는데 많은 자원과 노력이 소요 되지 않고 계산 속도가 빨라야 함 |
| 단방향성 (One-Wayness) | 해시 결과 값으로부터 입력 값을 계산하는 것은 불가능 해야 함 |
| 충돌 회피성 (Collision Resistance) | – 약한 충돌 회피성(Weak Collision Resistance) x가 주어졌을 때 H(x’)=H(x)인 x′(≠x)을 찾는 것은 계산적으로 어려워야 한다. 설명) 입력 값과 해시 값을 알고 있을 때 동일한 해시 값을 가지는 다른 입력 값을 찾는 것은 불가능 해야 함 |
| – 강한 충돌 회피성(Strong Collision Resistance) H(x’)=H(x)인 서로 다른 임의의 두 입력 x와 x’을 찾는 것은 계산적으로 어려워야 한다. 설명) 동일한 해시 값을 가지는 서로 다른 메시지 쌍을 찾는 것은 불가능 해야 함 |
II. 해시 함수의 3가지 안정성
| 안정성 | 설명 |
|---|---|
| 역상 (Preimage) 저항성 | 해시 함수와 메시지 다이제스트 y가 주어졌을 때, h(x) = y를 만족하는 x를 찾는 문제이며, 해시 함수에 대해 이러한 역상을 효과적으로 찾을 수 없음 (= 단방향성, One-Wayness) |
| 제2역상 (Sec. Preim.) 저항성 | 입력 값에 대해 해당 입력의 해시 값을 바꾸지 않으면서 입력을 변경하는 것이 계산상 어려움 |
| 충돌 (Collision) 저항성 | 해시 충돌에 대해 안전해야 하고 같은 해시 값을 생성하는 두 입력 값을 찾는 것이 계산상 어려움. 즉, 입력 값과 해시 값에 대해 해시 값을 망가뜨리지 않으면서 입력 값을 수정하는 공격에 대해 안전해야 함 |
III. 해시 암호화의 개념도 및 적용 기술과 유형
해시 암호화의 개념도
해시를 개개의 레코드 슬롯으로 하지 않고, 몇 개의 레코드를 수용할 수 있는 블록(버킷) 공간 이용
버킷 해시의 개요 (충돌 문제 해결 중 한 가지 방법)
해시 암호화의 구성요소
| 용 어 | 주요 개념 |
|---|---|
| 해싱함수 (Hashing Function) | – 키 값으로부터 레코드의 물리적 주소로 사상 시키는 함수 – 데이터 무결성검증, 변조여부 파악을 위해 임의 길이 메시지를 고정길이 메시지(Message digest)로 변환시 사용하는 단방향 함수 |
| 해시 키 (Hash Key) | – 해싱 함수가 레코드 주소를 계산하기 위해 사용하는 레코드의 키 값을 말함 |
| 해시 테이블 (HashTable) | – 해싱 함수에 의해 계산된 주소 – 키 연산에 의해 직접 접근이 가능한 구조 (배열)의 기억장소 |
| 버킷 (Bucket) | – 하나의 주소를 가지면서 하나 이상의 레코드를 저장할 수 있는 파일의 한 구역 – 크기는 같은 주소에 포함 가능한 레코드 수 – 여러 개의 슬롯(slot)으로 구성, |
| 슬롯(slot) | – 한 개의 레코드를 저장 할 수 있는 공간 |
| 직접파일 (Direct File) | – 해싱 방법을 기초로 하여 만들어진 파일 – 레코드를 식별하기 위한 키 값과 저장 장치에 저장되어 있는 레코드 사이의 사상(Mapping) 관계 성립 되어야 함 |
| 충돌 | – 서로 다른 레코드들이 같은 주소로 변환되는 경우 |
| 동거자 | – Synonyms, 해시 함수가 같은 주소로 변환시킨 레코드 |
| 오버플로우 | – 더 이상 빈자리가 없는 과잉 상태 – Bucket에 레코드들이 가득 찬 상태 |
해시 암호화에 적용되는 기술
| 기술 구분 | 내 용 |
|---|---|
| 제산함수 나눗셈법 (Division) | – 나머지 구하는 MOD 연산자 이용 주소 값을 취하는 방식 – 나누고자 하는 값, 즉 제수는 해싱 테이블 크기를 나타냄 – 적재율은 70 ~ 80%가 적당 |
| 중첩함수 (Folding) | – 키 값을 여러 방식으로 접어 값을 합산한 후 버킷(Burket) 주소로 활용 (폴딩법)
|
| 중간제곱함수 (Mid Square) | – 키 값의 중간 N자리를 뽑아 제곱한 후 상대 번지로 사용 – 제곱한 결과를 주소 공간의 크기에 맞도록 조정
|
| 진수변환 (Radix Conversion) | – 주어진 키 값을 특정 진법으로 간주한 후 다른 진법으로 변환 값을 이용하는 기술 |
| 기타 | – 계수분석(Digit Analysis), 대수적 코딩 (Algebraic Coding) |
해시 함수를 적용한 암호화 기술
| 구분 | 설명 | 활용 |
|---|---|---|
| MD5 (Message Digest) | – 128비트 암호화 해시 함수 (결과값이 16개 문자열) – MD4 대체목적 – 1996년 설계상 결함 발견 – 최근 보안 용도로 사용 안함 | – 파일, 메시지의 무결성검사 – 주로 상업적 용도 |
| SHA-1 (Secure Hash Algorithm) | – 160비트 암호화 해시 함수 – 1993년 미국 NIST에 의해 개발 – 가장 많이 사용 되고 있음 – 인터넷 Default 해시 알고리즘 | – 전자 서명 – 주로 정부 기관 |
| HAVAL | – MD를 변형하여 만든 해시함수 – 128비트에서 256비트 까지 다양한 크기의 해시 코드를 만들 수 있음 | – MD5 단점 보완 |
| Tiger | – 64비트 프로세서에 최적화 – 매우 빠른 해싱 기능 – 32비트에서도 빠르게 동작 | -64비트 프로세서 에서의 해시 |
해시 함수의 유형
| 유 형 | 주요 개념 | 적용 사례 |
|---|---|---|
| 폐쇄 해싱 (Closed Hashing) | – 모든 레코드를 한 버킷에 저장시키고, 해싱함수로 버킷 내 주소 계산 방식, – 정적 해싱 기법 | – 컴파일러, 어셈블러의 Symbol Table 구성 |
| 개방 해싱 (Open Hashing) | – 레코드의 증감에 적용하기 위해 동적으로 해싱 함수가 교정되도록 한 기법 – 동적 해싱 기법 | – 데이터베이스 시스템 |
IV. 정적 해싱 (Static Hashing) 기법
정적 해싱 기법의 개념
버킷 주소 집합의 크기를 고정시켜 처리하는 해싱 기법
정적 해싱 기법의 특징
- 현재의 파일 크기에 근거하여 해싱 함수 선택
- 미래의 특정 시점의 파일 크기를 예상하여 해싱 함수 선택
- 파일 크기가 커짐에 따라 주기적으로 해싱 구조 재구성 필요
정적 해싱 기법의 문제점 및 해결 방안
| 구 분 | 문제점 | 내 용 |
|---|---|---|
| 문제점 | Collision | – 복수개의 키 값이 동일 Hash Address 사용 |
| Overflow | – 빈 버킷이 없는 상태에 Hash Address가 다시 지정된 상태 | |
| 해결 방안 | 선형 검색법 | – 충돌이 일어난 그 위치에서 테이블 순으로 차례대로 검색하여 첫 번째 빈 버킷 공간에 레코드 키를 저장하여 충돌을 해결함 |
| 랜덤 검색법 | – 충돌을 유발할 레코드 키를 저장할 수 있는 공간을 찾을 때까지, 난수를 적용하여 해시케이블의 홈 주소를 다음 주소로 선택하여 해결 | |
| 체인 이용법 | – 충돌이 발생한 레코드들을 linked list로 연결하는 방법으로 해시 테이블 자체는 포인터를 배열로 만들고, 같은 버킷에 할당되는 레코드들은 체인으로 연결 |
V. 동적 해싱 (Dynamic Hash) 기법
동적 해싱 기법의 개념
- 데이터베이스가 확장 또는 축소 시 해싱 함수를 동적으로 변경시키는 해싱 기법 (Overflow 발생 시 2배 확장)
- 키 값을 사용하여 이진 트리를 동적으로 변화
확장 해싱 (Extendible Hashing) 기법의 개념
- 동적 해싱의 한 형태이며 트리의 깊이가 2인 특별한 경우
- 해싱 구조의 재구성이 한 번에 한 개의 버킷에서만 발생하므로 상대적 부하 경감
확장 해싱 기법의 장단점
| 구 분 | 주요 내용 |
|---|---|
| 장점 | – 파일의 크기가 크더라도 레코드를 접근하기 위해 디스크 접근이 두 번을 넘기지 않음 따라서, 파일의 크기가 증가하여도 성능이 나빠지지 않음 – 버킷 주소 테이블 크기 작으므로 저장 공간 절약 |
| 단점 | – 버킷 주소 테이블을 생성해야 하는 부담이 있음 – 각각의 버킷 주소가 실제의 버킷을 포인트하고 있으므로, 데이터의 숫자가 적으면 오히려 디스크의 낭비일 수 있음 – 버킷을 버킷 주소를 통해 간접적으로 검색하므로 추가적인 검색이 필요함 |
VI. 충돌 해결 전략 및 해결 방안
Collision 해결 전략
| 방 법 | 주요 내용 |
|---|---|
| Bucket 해싱 | – 버킷: 하나의 주소를 가지면서 하나 이상의 레코드를 저장할 수 있는 파일의 한 구역 – 테이블 엔트리에 몇 개의 키 값이 들어가도록 공간을 만들어 놓음, 충돌시 동일 버킷에 쌓아 놓음 – 버킷 오버플로우 발생 가능, I/O증가로 인한 성능저하, 메모리 낭비 |
| Open Addressing | – 충돌이 발생할 경우 다음 가용 공간에 저장 – 영역을 찾을 때까지 계속 수행 단순 방법 – 별도 포인터나 데이터 스트럭처 사용하지 않음 |
| Closed Addressing | – 같은 해시 값을 가지는 레코드들을 리스트로 만들어 관리 – 충돌을 쉽게 다룰 수 있음 – linked list를 통해 second clustering 데이터 편중 현상 방지 – 데이터 영역이 동적으로 할당되므로 테이블의 크기에 관계없이 다량 레코드 관리 가능 |
Collision 해결 방안
VII. 해시 암호화의 장단점
| 구분 | 주요 내용 |
|---|---|
| 장점 | – ISAM보다 상당히 빠른 검색속도를 지님 – 데이터에 대한 입력이나 삭제가 용이 – 검색시간이 데이터의 양과 무관하게 일정하게 유지 |
| 단점 | – 연속적인 데이터 검색에는 비효율적 – 디스크 공간이 비효율적으로 사용됨 – 디스크 공간을 늘리고 재구조화하게 되면 재 검색을 위한 상당시간 소요됨 |
About The Author
