암호학적, 해시 (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)	– 해싱 함수가 레코드 주소를 계산하기 위해 사용하는 레코드의 키 값을 말함
해시 테이블 (Hash Table)	– 해싱 함수에 의해 계산된 주소 – 키 연산에 의해 직접 접근이 가능한 구조 (배열)의 기억장소
버킷 (Bucket)	– 하나의 주소를 가지면서 하나 이상의 레코드를 저장할 수 있는 파일의 한 구역 – 크기는 같은 주소에 포함 가능한 레코드 수 – 여러 개의 슬롯(slot)으로 구성,
슬롯(slot)	– 한 개의 레코드를 저장 할 수 있는 공간
직접파일 (Direct File)	– 해싱 방법을 기초로 하여 만들어진 파일 – 레코드를 식별하기 위한 키 값과 저장 장치에 저장되어 있는 레코드 사이의 사상(Mapping) 관계 성립 되어야 함
충돌	– 서로 다른 레코드들이 같은 주소로 변환되는 경우
동거자	– Synonyms, 해시 함수가 같은 주소로 변환시킨 레코드
오버플로우	– 더 이상 빈자리가 없는 과잉 상태 – Bucket에 레코드들이 가득 찬 상태

라. 해시 암호화에 적용되는 기술

기술 구분	내 용
제산함수 나눗셈법 (Division)	– 나머지 구하는 MOD 연산자 이용 주소 값을 취하는 방식 – 나누고자 하는 값, 즉 제수는 해싱 테이블 크기를 나타냄 – 적재율은 70 ~ 80%가 적당
중첩함수 (Folding)	– 키 값을 여러 방식으로 접어 값을 합산한 후 버킷(Bucket) 주소로 활용
중간제곱함수 (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배 확장)

– 키 값을 사용하여 이진 트리를 동적으로 변화

나. 확장 해싱 (Extendable Hashing) 기법의 개념

• 동적 해싱의 한 형태이며 트리의 깊이가 2인 특별한 경우
• 해싱 구조의 재구성이 한 번에 한 개의 버킷에서만 발생하므로 상대적 부하 경감

다. 확장 해싱 기법의 장단점

구 분	주요 내용
장점	– 파일의 크기가 크더라도 레코드를 접근하기 위해 디스크 접근이 두 번을 넘기지 않음 따라서, 파일의 크기가 증가하여도 성능이 나빠지지 않음 – 버킷 주소 테이블 크기 작으므로 저장 공간 절약
단점	– 버킷 주소 테이블을 생성해야 하는 부담이 있음 – 각각의 버킷 주소가 실제의 버킷을 포인트하고 있으므로, 데이터의 숫자가 적으면 오히려 디스크의 낭비일 수 있음 – 버킷을 버킷 주소를 통해 간접적으로 검색하므로 추가적인 검색이 필요함

 

VI. 충돌 해결 전략 및 해결 방안

가. Collision 해결 전략

방 법	주요 내용
Bucket 해싱	– 버킷: 하나의 주소를 가지면서 하나 이상의 레코드를 저장할 수 있는 파일의 한 구역 – 테이블 엔트리에 몇 개의 키 값이 들어가도록 공간을 만들어 놓음, 충돌시 동일 버킷에 쌓아 놓음 – 버킷 오버플로우 발생 가능, I/O증가로 인한 성능저하, 메모리 낭비
Open Addressing	– 충돌이 발생할 경우 다음 가용 공간에 저장 – 영역을 찾을 때까지 계속 수행 단순 방법 – 별도 포인터나 데이터 스트럭처 사용하지 않음
Closed Addressing	– 같은 해시 값을 가지는 레코드들을 리스트로 만들어 관리 – 충돌을 쉽게 다룰 수 있음 – linked list를 통해 second clustering 데이터 편중 현상 방지 – 데이터 영역이 동적으로 할당되므로 테이블의 크기에 관계없이 다량 레코드 관리 가능

나. Collision 해결 방안

VII. 해시 암호화의 장단점

구분	주요 내용
장점	– ISAM보다 상당히 빠른 검색속도를 지님 – 데이터에 대한 입력이나 삭제가 용이 – 검색시간이 데이터의 양과 무관하게 일정하게 유지
단점	– 연속적인 데이터 검색에는 비효율적 – 디스크 공간이 비효율적으로 사용됨 – 디스크 공간을 늘리고 재구조화하게 되면 재 검색을 위한 상당시간 소요됨