Hashing(해싱)
- 해시(hash)란 단방향 암호화 기법으로 해시함수(해시 알고리즘)를 이용하여 고정된 길이의 암호화된 문자열로 바꿔버리는 것을 의미
- Hash Table(해시 테이블)과 Hash Function(해시 함수)으로 구성됨
- 해시테이블(Hash Table, Hash Map이라고도 불림)은 Key와 Value를 갖는 자료구조
Hash Collision(해시 충돌)
Chaining(체이닝)
- 버켓 내에 연결리스트(Linked List)를 할당하여, 버켓에 데이터를 삽입하다가 해시 충돌이 발생하면 연결리스트로 데이터들을 연결하는 방식
- 버켓이 꽉 차더라도 연결리스트로 계속 늘려가기에, 데이터의 주소값은 바뀌지 않는다.(Closed Addressing)
Open Addressing(개방 주소법)
- 해시 충돌이 일어나면 다른 버켓에 데이터를 삽입하는 방식
- 선형 탐색(Linear Probing): 해시충돌 시 다음 버켓, 혹은 몇 개를 건너뛰어 데이터를 삽입한다.
- 제곱 탐색(Quadratic Probing): 해시충돌 시 제곱만큼 건너뛴 버켓에 데이터를 삽입(1,4,9,16..)
- 이중 해시(Double Hashing): 해시충돌 시 다른 해시함수를 한 번 더 적용한 결과를 이용함.
Hash Function
해시함수는 임의의 길이의 데이터를 입력받아 일정한 길이의 비트열로 반환 시켜주는 함수이다.
입력값의 길이가 달라도 출력값은 언제나 고정된 길이로 반환한다.
동일한 값이 입력되면 언제나 동일한 출력값을 보장한다.
간단한 hash function
- 제산잔여해싱(divide and remainder): 주소수보다 작고 제일큰 Prime number 로 나눈다.
- 중간제곱해싱(mid-square): 제곱후 가운데 자리수 추출
- 중첩해싱(folding): 숫자를 접어서 더 한후 접은 자리수 만큼 추출
- 숫자추출방법(digit extraction): 의미 있다고 판단되는 몇가지 자리수만 추출하는 방법(예 학번,주민등록번호)
- 숫자이동변환(shifting): 중앙을 중심으로 주소길이만큼 나눈 후 좌우를 각각 시프트 시켜서 더하는 방법
- 진수변환(radix conversion): 키값을 다른진수로 변환 주소자리만큼 추출
암호화 해시 함수?
해시함수의 부분집합으로 역상저항성과 제2역상저항성 그리고 충돌저항성을 가지고 있어 암호화에 활용될 수 있는 경우를 의미.
- 역상저항성: 입력값 A에 의해 B가 출력되었다면, 출력된 B값만 주어졌을 때 입력값인 A값을 찾는 것이 계산적으로 불가능함을 의미한다.
- 제2역상저항성: 입력값 A와 출력값 B가 모두 주어졌을 때, 똑같은 B를 반환하는 A2 를 찾아내거나 만들어내는 것이 계산적으로 불가능함을 의미한다.
- 단방향 암호화: 양방향 암호화가 A를 B로 암호화하고 다시 B를 A로 복호화하여 원본 내용을 확인할 수 있다면, 단방향 암호화는 A로 만들어진 B를 가지고 다시 A로 역산할 수 없다.
- 충돌저항성: 똑같은 B라는 출력값이 나오는 X가 단일하지 않고 중복이 되는 또 다른 Xn을 발견하는 것이 계산적으로 어려운 성질을 의미한다. 충돌저항성은 제2역상저항성의 외부효과(부수효과, Side effect) 이자 부분집합 이다.
- 압축효과: 암호화 해시 함수가 반환하는 일정한 길이의 작은 해시값만으로 크기가 거대한 데이터의 무결성을 보장할 수 있는 외부효과를 의미한다. 예를 들어 SHA-256의 경우 100GB의 파일도 단 256bit의 해시값으로 그 내용의 무결성을 보장할 수 있다.
출처 및 참고
iOS시작~