1. 해시, 해시 함수, 해시 값 이란?
ㅇ 해시 (Hash)
- ① 다진(뒤범벅된) 고기 요리
- ② 우물 정자 (#, 해시 태그)
- ③ 긴 메세지를 뒤섞어 (정리하여) 고정 길이의 값으로 바꿈
ㅇ 해시 함수 (Hash Function) / 해시 알고리즘 (Hash Algorithm)
- 임의 길이의 메세지를 일정 고정 길이의 해시 값으로 변환시켜주는,
단방향성 함수/알고리즘
- [참고 용어]
. 단방향성,일방향성 (One-way)
.. 결과값으로는 입력 값을 알 수가 없는 또는 알기가 어려운 성질
. 프리 이미지 (pre-image)
.. 단방향성 해시 함수의 입력 값
ㅇ 해시 값 (Hash Value)
- 단방향성 해시 함수의 출력 결과 값
. 때론, `Fingerprint`,`메세지 다이제스트(Message Digest)` 이라고도 함
2. 해시 함수의 주요 응용
ㅇ 주로, 메세지(중요 정보)의 무결성 확인
ㅇ 디지털서명의 생성
- 메세지에 대한 디지털서명이 아니고, 그 해시 값에 대해서 만 디지털 서명을 함
ㅇ 메세지인증코드의 생성
- 메세지 내용의 무결성 확인 (변경 검출) 및 메세지 송신자가 진짜인지 인증 (인증 확인)
ㅇ 일회용 패스워드(OTP)의 생성
ㅇ 세션 키 도출
ㅇ 소프트웨어 배포시 변경 검출
3. 해시 함수의 표현
ㅇ 임의의 길이를 가진 메세지를 (입력 : 메세지),
일정한 고정 길이의 해쉬 값/다이제스트/축약 으로 (출력 : 해시 값),
변환시켜 그 결과값을 역산할 수 없게하는 단방향성 함수
- 해시 함수는 입력 키 이외 별도의 키 가 필요 없음
4. 해시 함수의 주요 요구 사항
ㅇ 임의 길이 메세지가 고정 길이의 해시값을 계산해낼 것
ㅇ 쉽게 계산이 가능해야 함
ㅇ 일방향성
ㅇ 충돌 내성
※ 주요 기본 성질/특성 셋(3)
- 해시 값으로부터 입력 값을 찾아낼 수 없음 (역상 저항성, 일방향성)
. 함수 값 H(M)이 주어질 때, 이부터 키 값 M을 결정하기 어려운 정도
. 이를 pre image 저항성 이라고도 함
- 해시 값이 일치할 것 같은 또다른 입력 값을 찾아낼 수 없음 (두번째 역상 저항성)
. H(M1)이 주어질 때, H(M1) = H(M2)로 값이 같더라도, M2 ≠ M1 라고 확인하기 어려움
. 이를 제2의 pre image 저항성 이라고도 함
- 해시 값이 같은 임의의 두 입력 값을 찾아낼 수 없음 (해시 충돌 저항성)
. M2 ≠ M1 일 때, H(M1) = H(M2) 인 M1과 M2인 쌍을 찾기 어려움
. 이를 충돌 저항성 이라고도 함
5. 해시 함수의 구현 방식
ㅇ 임의의 길이의 비트 열을 고정된 길이의 출력 값인 해시 코드로 손실 압축시킴
- 암호 응용 例) ☞ MD5, SHA 참조
ㅇ 해시 함수 구현 例
- 나눗셈법 : h(k) = k mod m
. 키 값 k를 해쉬테이블 원소 개수 m으로 나눈 나머지를 해시값으로 함
- 곱셈법
- 유니버설 해싱법 등
ㅇ 해시값 충돌 상존
- 계산결과로써 사용가능한 해시값 보다 입력 키 값 개수가 더 크므로 충돌 발생이 가능
6. 해시 함수의 구현 例)
ㅇ MD4, MD5
ㅇ SHA-1, SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512), SHA-3 (KECCAK)