해시와 해시 함수

해시 hash : 어떤 길이의 임의 데이터를 고정 길이의 데이터로 매핑하는 것.

해시 함수 : 입력된 데이터에 해시를 실행하여 해시값을 출력하는 함수. 가장 일반적으로 해시함수는 16진수의 해시값을 출력하며, 입력되는 데이터의 형태와 상관없이 출력되는 해시값의 길이가 항상 고정되어 있다.

해시 충돌 : 해시 함수에 입력된 2개의 다른 값이 동일한 해시값을 생성하는 경우. 다만 입력 데이터의 비트 하나만 달라져도 출력되는 해시값이 상상할 수 없을 정도로 달라지므로 해시 충돌은 흔치 않은 일이다. 해시 함수가 잘 정의되었으면 내부 연산이 빠르고 충돌 발생이 적다. 실제 개발 환경에는 프로그래머를 위해 설계된 여러 해시 함수를 볼 수 있다.

해시 테이블 hash table

키와 값으로 구성된 검색 시스템으로, 해시 테이블을 이용하는 탐색을 해싱이라고 한다. 해시 테이블에는 모든 키에 대응하는 값이 있으며 이러한 데이터 구성은 검색 수행 속도를 크게 증가시킨다. 즉, 키를 알면 키에 연결된 값을 즉시 찾을 수 있다. 해싱의 시간 복잡도는 O(1).

해시 테이블은 해시 함수를 사용해 검색을 수행한다. 보통 문자열인 키를 해시 함수에 입력하면, 저장을 위한 데이터 구조(기본적으로 배열)의 인덱스에 매핑된 해시값이 생성된다. 즉, 생성된 해시값을 사용하면 테이블에서 검색이나 추가하려는 요소가 저장된 배열의 인덱스를 계산할 수 있다. 해시값과 배열의 크기 때문에 해시 충돌이 발생할 수도 있는데 이를 방지하기 위해 체이닝chaining이라는 방식으로 해시 테이블을 구현한다.

체이닝은 요소를 단순한 배열이 아닌 연결 리스트인 배열에 저장하는 방식이다. 테이블의 각 인덱스에 할당된 것은 값이 아니라 키와 값을 가진 연결 리스트다. 즉, 해시 함수가 여러 요소에 대해 똑같은 인덱스를 반환하면, 해시값과 해당 요소들을 함께 '연결'하여 해시 테이블의 같은 인덱스에 저장한다. 단, 체이닝을 사용하면 연결 리스트가 길어졌을 때 해시 테이블 검색의 시간 복잡도가 증가할 가능성이 있다.

암호화 vs 해싱

해싱은 컴퓨터 보안 영역에서 주로 사용된다. 이때 해싱과 암호화를 헷갈릴 수 있는데, 먼저 암호화와 관련된 컴퓨터 보안 영역에 대해 간략하게 살펴보자.

암호 시스템 : 평문plaintext 입력을 암호문ciphertext 출력으로 변환하는 일련의 알고리즘. 평문을 암호문으로 변환하는 것을 암호화encryption라고 하며, 암호문을 평문으로 변환하는 것을 복호화decryption라고 한다.
key라는 것을 사용하여 암호화 알고리즘을 보조한다.

대칭 키symmetric key암호 시스템 : 암호화 및 복호화에 같은 키를 사용한다.네트워크를 통해 키를 키를 주고 받는 형식이며 이 과정에서 키를 가로챈 제3자가 메세지를 복호화할 수 있다는 결함이 있다. 이를 해결하기 위해 공개 키 암호 시스템이 개발되었다.

공개 키public key 암호 시스템 : 암호화 및 복호화에 다른 키를 사용한다. 암호화에 사용하는 키를 공개 키라고 하며, 복호화에 사용되는 키를 비밀 키secret key라고 한다.

이를 통해 알 수 있는 것은, 암호화는 정보를 암호화하고 복호화하는 것을 모두 포함하는 양방향 과정인 반면 해싱은 복호화가 필요없는 단방향 과정이라는 점이다.

컴퓨터 보안에서 해시의 역할

컴퓨터 보안에서 해시는 디지털 서명이나 사용자 인증 등 여러 가지 용도로 사용된다. 디지털 서명은 디지털 데이터의 유효성을 검증하는데 사용된다. 데이터에 포함된 소유자의 서명을 통해 수신자를 확인할 수 있다.
일반적으로 사용하는 디지털 서명 방식은 RSA Rivest-Shamir-AdlemanDSA digital signature algorithm 이다.RSA는 디지털 서명과 암호화에 모두 사용할 수 있디만, DSA는 디지털 서명의 생성 및 검증에만 사용할 수 있고 암호화에는 사용할 수 없다. 두 방식 모두 디지털 서명의 보안을 보장하기 위해 해시를 사용한다. RSA 방식의 디지털 서명 과정에서는 암호화하기 전의 데이터에 해시 함수를 사용한다. DSA 방식의 디지털 서명 과정에서는 SHA secure hash algorithm 기반 암호화 해시 함수를 사용한다.

해시는 비밀번호 응용 프로그램 등의 사용자 인증에도 사용할 수 있다. 단방향의 1대1 함수이므로 비밀번호를 사용하는 보안에 적합하기 때문이다. 데이터 베이스에 평문의 비밀번호가 아닌 해시값이 저장되기 때문에 보안이 무너지더라도 비밀번호를 안전하게 지킬 수 있다.

컴퓨터 보안 분야에서는 이 외에도 난수 생성, 메세지 인증 코드 message authentication code MAC, 단방향 함수, 암호 기술자 전용 응용 프로그램 등에 해시를 사용한다.

profile
hello, world

0개의 댓글