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

1. 해시 함수 (Hash Function) / 해시 알고리즘 (Hash Algorithm)

  ㅇ 임의 길이의 메세지를 일정 고정 길이의 해시 값으로 변환시켜주는,
     - 단방향성 함수/알고리즘

  ※ [참고 용어]
     - 단방향성,일방향성 (One-way) 
        . 결과값으로는 입력 값을 알 수가 없는 또는 알기가 어려운 성질
     - 프리 이미지 (pre-image)
        . 단방향성 해시 함수의 입력 값
     - 해시 값 (Hash Value)
        . 단방향성 해시 함수의 출력 결과 값
           .. 때론, `Fingerprint`,`메세지 다이제스트(Message Digest)` 이라고도 함


2. 해시 함수 (해시 알고리즘)의 주요 응용

  ㅇ 주로, 메세지(중요 정보)의 무결성 확인
  ㅇ 디지털서명의 생성
     - 메세지에 대한 디지털서명이 아니고, 그 해시 값에 대해서 만 디지털 서명을 함
  ㅇ 메세지인증코드(MAC)의 생성
     - 메세지 내용의 무결성 확인 (변경 검출) 및 메세지 송신자가 진짜인지 인증 (인증 확인)
  ㅇ 일회용 패스워드(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 
     - (1990년대초 미국 Ronald Rivest 교수 제안,개발)
  ㅇ SHA-1, SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512), SHA-3 (KECCAK)
     - (1990년대 중반 이후, MD4,MD5의 개선 대체를 위해, 미국 NIST 공모,공표)