[자료구조] 해시 알고리즘

- 해시 알고리즘

• 임의 길이의 메시지를 일정 고정 길이의 해시 값으로 변환시켜주는 단방향성 함수/알고리즘
• 해시 값으로는 입력 값을 찾아낼 수 없음(일방향성)
• 해시 값이 일치할 것 같은 또 다른 입력 값을 찾아낼 수 없음(역상저항성)
• 해시 값이 같은 임의의 두 입력 값을 찾아낼 수 없음(해시 충돌 저항성)
• 인증서의 지문 = 인증서의 주요정보(발급대상, 발급대상의 공개키, 발급자, 발급자의 서명)를 해시한 값

 

- 해시 테이블

• key: 매핑 전 원래 데이터의 값, hash value(인덱스): 매핑 후 데이터의 값
• key-value 쌍에서 key 값을 테이블에 저장 시, key 값을 해시 함수를 이용해 계산 후 결과값을 배열의 인덱스로 저장하는 방식
• 해시 함수: key 값 k를 입력 받아 0부터 배열크기-1 사이의 값인 key의 해시 값 h(k) 출력
• 충돌
  key보다 해시 값의 개수가 더 적기 때문에, 다른 k 값이 동일한 h(k)값을 가져 동일한 slot에 저장되는 경우
  (slot: 데이터가 저장되는 곳)
  
• Chaining 방법 – 충돌 최소화
  동일한 해시 값이 출력되어 충돌이 발생하면, 그 위치에 있던 데이터에 key 값을 포인터로 뒤이어 연결(연결리스트 형태)

 

- 해시 알고리즘 구현 방식

• 나눗셈법: 키 값 k를 해시 테이블 원소 개수 m으로 나눈 나머지가 해시 값
  h(k) = k mod m
• 곱셈법
• 유니버셜 해싱법
• MD5, SHA-1, SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512)
• SHA
  MD5 취약성 개선/대체하기 위함
  SHA-1: 512비트 블록 단위 처리, 160 비트(20바이트) 해시 값 생성, 속도 빠름
  SHA-2: 256은 256비트(32바이트), 384는 384비트, 512는 512비트의 해시 값 생성