해시 함수
해시 함수란?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private void hash(int x){
return x % 5;
}
hash(7);
// 2
hash(8);
// 3
hash(9);
// 4
해시 함수는 입력값을 고정된 길이의 특정 값으로 출력하는 함수이다. 출력 데이터인 해시값은 동일한 입력에는 항상 동일한 값을 리턴한다.
모듈러 연산(나머지 계산)이 대표적인 예시로, 입력값을 나눈 나머지 계산을 해시 함수로 활용하고, 데이터셋은 0부터 나눈 숫자 미만까지 고정된 범위의 해시값으로 변환된다.
특징
단방향성, 결정론적
해시 함수는 입력 값을 해시값으로 변환은 쉽지만, 해시값에서 원래의 값으로 되돌리는 것은 거의 불가능하다.
또한 해시 함수는 같은 데이터 입력 시 항상 동일한 결과, 일정한 길이의 결과값을 리턴해야 한다. 따라서 해시함수를 거친 두 개의 값이 다르다면 해당 값에 대한 원래 데이터 또한 다름을 보장할 수 있어야 한다. 하지만 서로 다른 입력이 동일한 해시 값을 가질 수는 있으며, 이를 해시 충돌이라고 한다.
이런 해시함수의 특징으로 인해 보안, 데이터 무결성 검증 등에 사용되고 있다. 우리가 게임을 할 때 사용하는 플랫폼인 스팀에서 파일에 대한 변조가 일어났는지 확인을 할때 무결성 검사를 하는데, 이런 대용량 데이터에 대해서 변조 여부를 확인할 때 사용하기 좋은 방식이 해시값을 이용한 비교이다.
해시 충돌
1
2
3
4
5
6
7
8
9
10
11
12
13
private void hash(int x){
return x % 5;
}
hash(7);
// 2
hash(12);
// 2
해시 함수에 서로 다른 입력을 넣었는데 동일한 해시값 출력시 해시 충돌이 발생했다고 한다.
좋은 해시함수는 충돌 확률을 매우 낮게 최소화해야 하며, 이러한 요소를 평가하는 척도를 충돌 저항성이라고 한다. 충돌 저항성이 좋다는 것은 해시 함수에 무작위로 데이터를 넣었을 때 결과값이 같은, 해시 함수가 충돌하는 다른 두 개의 입력값을 발견하기 어렵다는 것을 의미한다.
종류
해시 테이블
해시 테이블은 Key, Value 쌍으로 데이터를 저장하는 자료구조이다.
키값을 해싱하여 빠른 속도로 해당되는 값을 탐색할 수 있으며, 평균 시간 복잡도는 O(1) 이다. 만약 데이터 충돌 발생 시 버킷에 추가적으로 연결된 리스트로 검색 범위가 확대되므로 O(N)으로 시간 복잡도가 증가할 수 있다.
MD5
128비트 암호화 해시 함수이다. 주로 프로그램이나 파일이 원본 그대로인지를 확인하는 무결성 검사 등에 사용된다.
하지만 몇 가지 암호화 결함들이 지속적으로 발견되기 시작했고, 심지어 노트북 컴퓨터 한 대의 계산 능력으로 1분 내에 해시 충돌을 찾을 정도의 결함이 발견되기도 하면서 보안 관련 용도로 해당 알고리즘을 사용하는 것은 권장하지 않는다고 한다.
SHA 256
미국 국가안보국(NSA)의 설계에서 시작된 해시함수로, 256비트의 고정된 결과값, 64자리의 문자열을 반환한다. 2^256에 해당하는 경우의 수를 만들수 있어서 해시 충돌로부터 비교적 안전하다.
출력속도가 다른 암호화 알고리즘과 비교해 빠르다는 장점이 있기 때문에 인증서, 블록체인 등에 많이 사용되고 있다.
참고
코드스테이츠, 블록체인 해시함수 정의, 특징, 블록체인 활용 예시, https://www.codestates.com/blog/content/%EB%B8%94%EB%A1%9D%EC%B2%B4%EC%9D%B8-%ED%95%B4%EC%8B%9C%ED%95%A8%EC%88%98
해시넷, 해시함수, http://wiki.hash.kr/index.php/%ED%95%B4%EC%8B%9C%ED%95%A8%EC%88%98
위키백과, 해시 함수, https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%95%A8%EC%88%98
위키백과, 해시 테이블, https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%85%8C%EC%9D%B4%EB%B8%94
망나니개발자, 자료구조 해시테이블(HashTable)이란?, https://mangkyu.tistory.com/102
위키백과, MD5, https://ko.wikipedia.org/wiki/MD5
해시넷, SHA256, http://wiki.hash.kr/index.php/SHA256