해싱 3: 개방 주소법

개방 번지화

체이닝 없이 모든 항목이 테이블에 저장된다.
한 슬롯당 하나의 항목 m >= n
해시 함수는 키 삽입/탐색/삭제를 위한 키의 슬롯의 탐색 순서를 정한다. 하나의 슬롯만 보는 게 아니다.

U : universe of keys

h: U x {0,1,….,m-1} -> {0,1,….,m-1}

= U x trial count -> slot in table

<h(k,0),h(k,1),…,h(k,m−1)> 는 0, 1, … , m − 1의 순열이다. 즉, i를 하나씩 늘려가며 h(k,i)를 다 돌면, 표에 있는 모든 슬롯을 돌게 된다.

Insert(k,v) : 빈 슬롯을 찾을 떄까지 계속 조사하고, 항목을 그 슬롯에 넣는다.

for i in xrange(m):
    if T[h(k,i)] is None:
       T[h(k,i)] = (k,v)
       return
    raise 'full'

Search(k) : 조사를 통해 확인한 슬롯에 있는 키가 k가 아니면, k를 찾을 때까지 또는 빈 슬롯을 찾을 때 까지 계속 조사를 한다. 각각 성공이나 실패를 반환한다.

for i in xrange(m):
    if   T[h(k,i)] is None:
         return None
    elif T[h(k,i)[theta] == k:
         return T[h(k,i)]
    return None

항목을 삭제 시에 슬롯에서 바로 지우면 안된다. 항목을 새로운 표시 DeleteMe로 바꾸고 데이터 삽입시에는 None으로 치고, 탐ㅌ색에는 그러지 않는다.

조사기법

선형조사

h(k,i)=(h’(k)+i) mod m 여기서 h’(k)는 평범한 해시 함수이다.

군집화 집단 : 값이 차있는 연속된 슬롯의 무리는 계속해서 커지고 커질 확률이 점점 높아진다.
0.01 < a < 0.99 이면, 군집의 크기가 Θ(log n)이다.

이중 해싱

h(k,i) = (h1(k) + i*h2(k)) mod m 여기서 h1(k)와 h2(k)는 두개의 평범한 해시 함수이다.

모든 k에 대해 h2(k)와 m이 서로소이면, 모든 슬롯을 확인할 수 있다. h1(k) + i*h2(k) mod m = h1(k) + i + h2(k) mod m -> m divides(i-j)

균일한 해싱 가정

각 키가 가지는 조사 순서가 m!의 무작위 순열 중에 특정 순열일 확률이 균등하다.
개방 주소법을 써서 n개의 항목을 m 크기에 표에 삽입했다고 가정한다. 균일한 해싱을 가정하면, 다음 연산의 기대 비용은 <= 1/1-a이다. 여기서 a = n/m(<1)이다.

증명

k라는 키를 가진 항목을 삽입하고 싶다고 가정한다. 그리고 그 항목이 표에 없다면,
- 첫 조사가 성공할 확률은 m-n/m=:p 이다.
- 첫 조사가 실패하면, 두 번째 조사가 성공할 확률은 m-n/m-1 >= m-n/m = p
- 첫 번째와 두 번째 조사를 실패하면, 세번째 탐색이 성공할 확률은 m-n/m-2 >= m-n/m = p => 모든 시도가 적어도 p 이상의 성공 확률을 가진다.

성공까지 기대 시도 횟수 1/p = 1/1-a

데이터 탐색과 삭제는 O(1/(1-a)) 만큼 걸린다.

개방 주소법 vs 체이닝

개방 주소법 : 더 나은 캐시 성능(더 나은 메모리 사용, 포인터를 쓸 필요 없음)
체이닝 : 저갲율(적재율이 70%를 넘으면 저하된다. 적재율이 1을 넘으면 안된다.)과 해시함수(개방 주소법은 군집화를 막아야 한다.)에 제한이 적다.

암호학적 해싱

암호학적 해시 함수는 임의의 데이터를 받아 정해진 크기의 문자열과 (암호화된) 해시 값을 반환한다. 고의 또는 실수로 데이터가 바뀌면 해시 값도 바뀐다. 암호화된 데이터는 대부분 메시지라고 불리는데, 해시 값이 메시지 다이제스트 또는 다이제스트라고도 불린다.

이상적인 암호학적 해시 함수는 이러한 특성을 가진다. 다음에서 d가 해시 함수의 출력값의 비트 크기이다. m은 2^d이라고 생각하면 된다. d는 대부분 160 또는 그 이상이다. 이러한 해시 함수는 해시 테이블을 인덱싱하기 위해서도 쓰지만 컴퓨터 보안 응용에 많이 쓰인다.

암호 해독 해시 함수의 특성

일방성 (One-Way, OW) : y ∈ {0, 1}^d 가 주어졌을 때 h(x)=y의 x를 찾는 것은 불가능하다. 무작위의 d-bit벡터를 골랐을 때, 그 벡터를 해시 값으로 가지는 입력 값을 찾지 못한다.
충돌 저항 (Collision-resistance, CR) : h(x) = h(x’)을 만족시키는 두 개의 다른 x와 x’은 존재하지 않는다. 이렇게 두 가지 입력 값이 같은 해시 값을 가지는 것을 충돌이라 부른다.
목표 충돌 저항 (Target collision-resistance, TCR) : x가 주어진 상태에서 x와 x’은 다르고 h(x) = h(x’)인 x’을 찾는 것은 거의 불가능하다.

응용

비밀번호 저장소: 컴퓨터에 PW가 아닌 h(PW)를 저장한다. 사용자가 PW′를 입력하면 h(PW′)를 계산해 저장되어 있는 h(PW)와 비교한다. 해시 함수는 OW를 만족해야 한다. 상대방이 PW나 PW′를 모르기 때문에 TCR이나 CR이 필요없다. 많은 비밀번호가 같은 해시 값을 가지면 문제지만, 약간의 충돌은 보안에 큰 영향을 끼치지 않는다.
파일 변경 탐지기: F라는 각 파일 마다 h(F)를 안전하게 저장한다. F가 바뀌었는지는 h(F)를 다시 계산해보면 알 수 있다. 해시 함수가 TCR을 만족해야 한다. 상대방이 h(F)를 바꾸지 않고 F를 바꿀 수 있으면 안된다.
디지털 서명: 공개된 키 암호 해독에서, 앨리스가 PKA라는 공개된 키와 SKA라는 개인 키가 있다고 하자. 앨리스가 개인 키를 써서 σ = sign(SKA,M)을 만들고, 메시지 M에 서명을 할 수 있다. 앨리스의 공개된 키 PKA를 아는 사람은 앨리스의 서명의 진위여부를 verify(M,σ,PKA)가 true인지를 통해 알 수 있다. 상대방은 서명을 위조하려 한다. 큰 M의 경우, h(M)을 서명하는 게 M에 서명하는 것보다 쉽다. 즉, σ = sign(SKA,h(M)). 그러면 CR을 만족해야 한다. h(x) = h(x’)이면, 상대방이 A에게 x를 서명하라 하고 앨리스가 x0에 서명했다고 말할 수 없어야 한다.

출처

MIT 파이썬을 이용한 알고리즘