Hash function

입력길이에 상관없이 고정된 길이의 digest를 반환하는 함수
digest길이는 hash 알고리즘마다 다르다

해시함수의 특징

• 입력값이 같으면 항상 같은 digest를 출력한다
• 입력값 a와 b가 조금만 차이나더라도 전혀 다른 digest를 출력한다
• 입력값의 길이에 상관없이 고정된 길이의 digest를 출력한다

해시함수가 단방향이 되기 위한 조건

			H(x) = y

• 강한 일방향성 : 해시 결과값 y로 입력값 x를 도출하는것이 계산적으로 불가능할것
• 약한 일방향성 : H(a) = y 임을 알고있을때 H(b) = y 인 b를 찾기가 계산적으로 불가능할것
• 충돌 저항성 : H(a) = H(b)를 만족하는 (a, b) 페어를 찾기가 계산적으로 불가능할것

위 조건을 만족했을때 해시함수는 단방향 해시함수라고 불리며
message authentication에 사용할 수 있다

HMAC

Hashed Message Authentication Code

단방향 해시함수의 특징으로 인하여 해시 함수는 메시지 위변조를 검출할 수 있다

1. 전체 메시지를 해시하여 digest를 메시지에 포함한다
2. digest를 메시지에 추가하여 전송한다
3. 전송받은 메시지를 해시하여 digest와 digest를 비교한다

이 때 digest가 서로 다르다면 메시지는 위변조 된것이다

hash table

연관배열 구조를 이용하여 해시로 얻어낸 key값에 value를 저장하는 자료구조

해시 테이블은 다음과 같은 요소들로 이루어져있다

• input

  	해시함수의 input값이며 hash table에 저장될 value

• hash function

  	key를 digest로 변환하는 역할을 한다

• digest

  	input값이 해시함수로 인해 변환된 값이며 bucket에 저장될 value의 key값이다

  index로서의 역할을 하기 때문에 해시 충돌을 방지하기 위하여 가능한 한 unique해야 한다

• bucket

  	digest와 input값 페어가 실질적으로 저장되는 저장소

hash table의 특징

장점

• data의 key값이 data를 해시한 값이므로 원하는 값에 접근하기 위해 index를 순회할 필요가 없어
  테이블내 요소가 많아져도 상수시간 내에 값에 접근할 수 있다

단점

• 해시 함수를 위한 추가적인 연산이 필요함
• 해시 테이블의 크기가 유한하기 때문에 key값이 겹쳐 해시 충돌이 발생할수 있다
  충돌이 많이 발생할수록 접근시간은 O(1)에서 O(n)으로 증가한다
• 해시 테이블의 크기가 해시 알고리즘에 의존적이기 때문에 크기가 유한적이며 그에 따라
  적은 양의 데이터를 저장할 시 오버헤드가 생긴다