유니버설 해싱

IT 위키

유니버설 해싱(Universal Hashing)은 해시 함수의 집합 중에서 하나를 무작위로 선택하여 사용하는 해싱 기법으로, 모든 키 쌍이 충돌할 확률이 최소화되도록 보장하는 해시 방식이다. 해시 함수가 고정되지 않고 무작위로 선택되기 때문에, 입력에 의존적인 공격이나 최악의 성능을 회피할 수 있다는 장점이 있다.

1 개념[편집 | 원본 편집]

  • 일반적인 해시 테이블은 해시 함수가 고정되어 있음 → 충돌 위험 존재
  • 유니버설 해싱은 해시 함수의 집합 H에서 무작위로 하나의 해시 함수 h ∈ H를 선택
  • 임의의 키 쌍 x ≠ y에 대해 충돌할 확률이 낮도록 H가 설계됨

2 정의[편집 | 원본 편집]

해시 함수 집합 H가 유니버설(universal)하다는 것은 다음 조건을 만족함:

  • 임의의 서로 다른 키 x ≠ y에 대해,
  • 선택된 해시 함수 h ∈ H에서 충돌 확률이 다음과 같을 때:
    • Pr[h(x) = h(y)] ≤ 1/m
  • 여기서 m은 해시 테이블의 크기

유니버설 해시 함수 예시

  • 모듈러 기반 해시 함수
    • 정수 키 x에 대해, 소수 p > u (키 공간 크기), 그리고 임의의 a ∈ {1,...,p−1}, b ∈ {0,...,p−1}에 대해:
ha,b(x) = ((a⋅x + b) mod p) mod m
  • 이 함수 집합은 유니버설이며, a, b를 무작위로 선택함

3 시뮬레이션[편집 | 원본 편집]

해시 대상: apple, pear, kiwi, lime, mango

  • 각 단어를 고정 길이 벡터로 변환 (알파벳을 숫자 1~26로 매핑하고, 부족하면 0으로 패딩)
  • 예) "lime" → (12, 9, 13, 5, 0)

해시 함수 형태: ha(x) = (a0 + a1·x1 + a2·x2 + a3·x3 + a4·x4 + a5·x5) mod m[1]

  • a = (a0, ..., a5)는 랜덤 벡터 (각 요소는 0~28)
  • x = (x1, ..., x5)는 단어를 숫자로 변환한 벡터
  • m은 해시 테이블의 크기
    • 여기선 가장 타이트하게 해시 대상의 수인 5로 한다.

a값은 미리 정해진 고정 난수값이다. 예를 들어 의사 난수 생성기에서 시드값을 정해놓으면 항상 같은 난수를 사용할 수 있다.[2]

  • 여기선 임의로, a = [20, 3, 0, 23, 8]

해시값을 만들어보자

  • h(apple) = (20 + 3×1 + 0×16 + 23×16 + 8×12 + 7×5) mod 5 = (20 + 3 + 0 + 368 + 96 + 35) mod 5 = 522 mod 5 = 2
  • h(pear) = (20 + 3×16 + 0×5 + 23×1 + 8×18 + 7×0) mod 5 = (20 + 48 + 0 + 23 + 144 + 0) mod 5 = 235 mod 5 = 0
  • h(kiwi) = (20 + 3×11 + 0×9 + 23×23 + 8×9 + 7×0) mod 5 = (20 + 33 + 0 + 529 + 72 + 0) mod 5 = 654 mod 5 = 4
  • h(lime) = (20 + 3×12 + 0×9 + 23×13 + 8×5 + 7×0) mod 5 = (20 + 36 + 0 + 299 + 40 + 0) mod 5 = 395 mod 5 = 0
  • h(mango) = (20 + 3×13 + 0×1 + 23×14 + 8×7 + 7×15) mod 5 = (20 + 39 + 0 + 322 + 56 + 105) mod 5 = 542 mod 5 = 2

0과 2 두가지 키에서 충돌이 발생했다. 이와 같이 mod 5를 하기 때문에 각 키별 충돌 가능성은 1/5이다. 이 확률을 더 줄이기 위해 보통 해시 테이블은 여유 있게(over-provisioning) 잡는다. 그리고 충돌을 최소화하기 위해 FKS 해싱을 사용한다.

4 장점[편집 | 원본 편집]

  • 충돌 확률을 수학적으로 상한선 아래로 제한할 수 있음
  • 입력 키 분포와 상관없이 성능 유지 가능
  • 보안 해시, 암호학적 해시와 달리 계산이 빠르고 간단

5 단점[편집 | 원본 편집]

  • 해시 함수 설정에 추가적인 무작위 요소가 필요
  • 해시 함수를 매번 선택하거나 유지해야 하므로 구현이 약간 복잡해짐

6 응용[편집 | 원본 편집]

7 같이 보기[편집 | 원본 편집]

8 참고 문헌[편집 | 원본 편집]

  • Carter, J. L., & Wegman, M. N. (1979). Universal classes of hash functions. Journal of Computer and System Sciences
  • Cormen, T. H. et al. (2009). Introduction to Algorithms. MIT Press
  • Mitzenmacher, M., & Upfal, E. (2005). Probability and Computing. Cambridge University Press

9 각주[편집 | 원본 편집]

  1. ↑ 실제 실무적으론 해시 함수가 저렇게 단순 곱셈 및 덧셈이기보단 좀 더 복잡한 다항식으로 구성된다.
  2. ↑ 일시적으로 사용되는 세션 내 암호화에선 이 난수값이나 난수 생성을 위한 시드값이 세션에 저장될 수도 있다.
원본 주소 "https://itwiki.kr/index.php?title=유니버설_해싱&oldid=40918"