[자료구조] cryptographic hash function

수업시간에 cryptographic hash function 내용이 나왔다

hash를 설명하며 교수님은 이렇게 말씀하셨다
어떤 값을 찾기 위해 어떻게 해야할까요?

1. 결과가 나올때까지 하나하나 검색 O(n)
   전공자는 이러면 안된다
2. sorting 후 binary search O(logN)
   not bad.. 하지만 1, 2학년 수준
   정렬이 안되는 상황이 있을 수 있고, 굳이 정렬을?
3. hash table O(1)
   good

-> 어떤 상황에 뭘 사용해야 적절한지 알기 위해 자료구조를 아는 것이다

약간의 울림이 있었다
군대가기 전 2학년때 배운 자료구조 수업에서는 난 아무 생각이 없었다
다시 알아보자

hash
데이터를 효율적으로 다루기 위한 방법중 하나
임의의 길이의 데이터를 고정된 길이의 데이터로 mapping한 값

hash function
임의의 길이의 데이터를 hash로 매핑하는 함수
같은 input은 같은 output

hash table
key, value 형태로 데이터를 저장하는 자료구조
hash function의 hash값을 index로 사용

hashing
hash function에서 hash를 출력하고
hash table에 저장

python dictionary가 hash 테이블을 사용한 자료형이다!

cryptographic hash function
hash function의 일종이지만, 3가지 성질을 더 가진다

• 역상 저항성 : output으로 input을 찾는 것이 더 어렵다
• 제 2 역상 저항성 : output이 바뀌지 않는 input을 찾는 것이 더 어렵다
• 충돌 저항성 : 같은 output을 가지는 input을 찾는 것이 더 어렵다

제 2 역상 저항성과 충돌 저항성이 같은 것 같은데??
-> 공격의 시나리오가 다르다 - 수식을 보니 이해가 된다

• 제 2역상 저항성
  x1, h(x1)을 알고 있을 때 h(x1) = h(x2)인 x2를 찾는 것이 어려움
• 충돌 저항성
  그냥 h(x1) = h(x2)인 x1, x2를 찾는 것이 어려움