Hash Function, Hash Algorithm   해시 함수, 해쉬 함수, 해쉬 알고리즘, 해시 알고리즘

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)