해시 함수

해싱

해싱 어떤 데이터를 작은 크기의 데이터로 변환하여 테이블에 담는 데이터 관리 기법이다. 해싱을 사용하면 데이터를 빠른 속도로 검색할 수 있다는 장점이 있다. 그리고 이 해싱은 암호화, 복호화의 개념과 만나 전자서명에도 사용이 된다.

해시 함수

해싱을 하는 방법은 다양하게 존재한다. 임의로 어떤 데이터를 변환 하겠다고 정했다면 그 방법이 바로 해시 함수가 되는 것이다. 예를 들어 “문자를 한칸씩 뒤로 옮기는 변환”이라는 해시 함수를 생각했다면, “ABC”라는 문자는 “BCD”가 되는 것이다.(예시에 불과하며, 속도적 이득은 거의 없다고 볼 수 있다.) 해시 함수는 보통 원문을 단방향으로 해싱하는 용도로 쓰이며 역방향으로 원문을 알아내는 방법은 계산상 불가능해야 좋은 해시 함수라고 할 수 있다.

충돌

해시 함수는 한가지 결정적인 단점을 안고 있는데 그것은 바로 다른 원문이 같은 해시값을 가질 수 있다는 것이다. 그리고 그것을 “충돌”이라고 부른다. 충돌이 일어날 가능성이 낮아야 좋은 해시 함수라고 할 수 있다.

이러한 충돌이 발생했을 때 대처하는 몇가지 방법이 있다. 크게 두가지로 나뉜다.

1. Open addressing
   
   • 선형 탐사 : 해시값이 겹쳐 테이블이 차있다면, 테이블의 그 다음 인덱스에 넣는다.
   • 제곱 탐사 : 충돌값을 테이블의 (인덱스 + 1^2), (인덱스 + 2^2),… 따위에 넣는다.
   • 이중 해시 : 여러 해시 함수를 준비하여 충돌이 일어나면 다른 해시 함수를 사용하여 넣는다.
     기타 등등…
2. Close addressing
   
   • 버켓 : 충돌값을 배열에 넣는다.
   • 체이닝 : 충돌값을 연결리스트에 넣는다.

암호학적 해시 함수

해시 함수의 일종으로, 데이터를 고정된 길이의 해시값으로 출력하는 함수이다. 각 메시지 마다 해시값이 다르기 때문에 해시 함수는 메시지의 무결성을 확인하는 방법으로 메시지의 내용이 변경되지 않았다는 것을 보장해준다. 또한, 일방향 함수를 포함하고 있기 때문에 해시값에서 원문을 재현할 수는 없고 같은 해시값을 가진 다른 데이터를 작성하는 것도 극히 어렵다. 즉, 앞서 말한 충돌이 잘 일어나지 않고, 원문을 알아내기 어려운 좋은 해시 함수를 말한다.

이러한 해시 함수는 다음과 같은 특성을 갖는다.

• 역상 저항성 : 주어진 해시 값에 대해, 그 해시 값을 생성하는 입력값을 찾는 것이 계산상 어렵다. 즉, 해시 함수는 제 1 역상 공격에 대해 안전해야 한다. 이 성질은 일방향 함수와 연관되어 있다.
• 제 2 역상 저항성 : 입력 값에 대해, 그 입력의 해시 값을 바꾸지 않으면서 초기 입력 값과 다른 입력값을 찾는 것이 계산상 어렵다. 즉, 해시 함수는 제 2 역상 공격에 대해 안전해야 한다.
• 충돌 저항성 : 해시함수는 해시 충돌에 대해 안전해야 한다. 같은 해시 값을 생성하는 두 개의 입력값을 찾는 것이 계산상 어려워야 한다.

대표적인 함수의 종류로는 MD5, SHA-1 등이 있고, 최근에는 이 해싱 함수들이 분석이 되면서 SHA-256이나 SHA-512 등을 사용한다.

출처 : http://www.terms.co.kr/hashing.htm

         https://ko.wikipedia.org/wiki/%EC%95%94%ED%98%B8%ED%95%99%EC%A0%81_%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