우리가 도서관에서 수만 권의 책 중에 특정 책을 찾는다고 상상해 봅시다. 만약 책들이 아무런 규칙 없이 꽂혀 있다면, 원하는 책을 찾기 위해 모든 책장을 처음부터 끝까지 뒤져야 할 것입니다. 하지만 다행히도 도서관에는 ‘도서 분류 기호’라는 체계가 있습니다. 우리는 책 제목으로 이 고유한 기호를 찾아내고, 그 기호가 가리키는 위치로 곧장 가서 책을 꺼내볼 수 있습니다. 이 마법 같은 ‘도서 분류 기호’의 역할을 컴퓨터 과학의 세계에서 수행하는 것이 바로 ‘해싱 함수(Hashing Function)’입니다.
해싱 함수는 임의의 길이를 가진 데이터(Key)를 입력으로 받아, 고정된 길이의 고유한 값(Hash Value 또는 Hash Code)으로 변환해주는 함수입니다. 마치 모든 사람에게 고유한 ‘지문’이 있듯이, 해싱 함수는 어떤 데이터라도 그 데이터만의 고유한 ‘디지털 지문’을 만들어 줍니다. 이 지문은 원래 데이터가 아주 약간만 달라져도 완전히 다른 모양으로 바뀌는 특징이 있어, 데이터의 빠른 검색, 무결성 검증, 그리고 안전한 비밀번호 저장 등 현대 컴퓨팅의 수많은 영역에서 핵심적인 역할을 수행하고 있습니다.
본 글에서는 이 강력한 해싱 함수의 기본 원리는 무엇이며, 좋은 해싱 함수가 갖추어야 할 조건들은 어떤 것들이 있는지, 그리고 실제 우리 삶 속에서 어떻게 활용되고 있는지를 깊이 있게 탐구해 보겠습니다. 해싱의 세계를 이해하고 나면, 우리가 당연하게 사용하던 수많은 기술들의 이면에 얼마나 정교한 아이디어가 숨어있는지 깨닫게 될 것입니다.
좋은 해싱 함수의 조건: 무엇이 ‘좋은 지문’을 만드는가?
아무 함수나 해싱 함수로 사용할 수 있는 것은 아닙니다. 좋은 해싱 함수는 데이터의 ‘지문’으로서 제 역할을 다하기 위해 몇 가지 필수적인 조건을 만족해야 합니다.
1. 결정론적 (Deterministic)
좋은 해싱 함수는 무엇보다도 ‘결정론적’이어야 합니다. 이는 동일한 입력 값에 대해서는 언제, 어디서, 누가 실행하더라도 항상 동일한 해시 값을 반환해야 함을 의미합니다. 만약 ‘apple’이라는 단어를 해싱할 때마다 다른 결과가 나온다면, 우리는 그 결과를 이용해 데이터를 저장하거나 검색할 수 없을 것입니다. 입력이 같으면 출력이 항상 같아야 한다는 것은 해싱 함수의 가장 기본적이면서도 중요한 전제 조건입니다.
- Good:
hash("apple")→1a2b3c(언제나 동일) - Bad:
hash("apple")→1a2b3c, 다음 실행 시 →9z8y7x
2. 균일성 (Uniformity) 및 빠른 계산
해싱 함수의 결과물인 해시 값은 특정 영역에 집중되지 않고, 가능한 모든 출력 값의 범위에 걸쳐 최대한 균일하게 분포되어야 합니다. 이를 ‘균일성’ 또는 ‘Uniform Distribution’이라고 합니다. 만약 모든 입력 값이 특정 몇 개의 해시 값으로만 쏠려서 변환된다면, 이는 ‘해시 충돌(Hash Collision)’의 가능성을 높여 해시 테이블의 성능을 심각하게 저하시킵니다. 마치 도서관의 모든 책이 ‘컴퓨터’ 분야 서가에만 꽂히도록 분류되는 것과 같습니다. 좋은 해싱 함수는 입력 데이터를 골고루 흩뿌려주는 역할을 해야 합니다.
또한, 해싱 함수 자체의 계산 속도는 매우 빨라야 합니다. 데이터를 저장하고 검색하는 매 순간마다 해싱 함수가 호출되는데, 이 함수 자체의 연산이 복잡하고 느리다면 전체 시스템의 성능에 병목이 될 것입니다.
3. 해시 충돌 저항성 (Collision Resistance)
‘해시 충돌’은 서로 다른 두 개의 입력 값(Key1 ≠ Key2)에 대해 해싱 함수가 동일한 해시 값을 반환(hash(Key1) = hash(Key2))하는 현상을 말합니다. 비둘기집 원리에 따라, 입력 값의 종류가 출력 값의 종류보다 많다면 충돌은 피할 수 없는 숙명입니다. 하지만 좋은 해싱 함수는 이러한 충돌이 발생할 확률을 최대한 낮추도록 설계되어야 합니다.
특히 암호학적 해시 함수에서는 충돌 저항성이 더욱 엄격하게 요구되며, 이는 다시 두 가지 속성으로 나뉩니다.
- 제1 역상 저항성 (Pre-image Resistance): 주어진 해시 값 h에 대해,
hash(x) = h를 만족하는 입력 값 x를 찾는 것이 계산적으로 불가능해야 합니다. 즉, ‘지문’만 보고 원래 ‘사람’을 찾아낼 수 없어야 합니다. 이는 비밀번호 저장에 필수적인 속성입니다. - 제2 역상 저항성 (Second Pre-image Resistance): 특정 입력 값 x가 주어졌을 때,
hash(x) = hash(y)를 만족하는 또 다른 입력 값 y (y ≠ x)를 찾는 것이 계산적으로 불가능해야 합니다. 즉, ‘A의 지문’과 똑같은 ‘B의 지문’을 만들어낼 수 없어야 합니다. 이는 데이터의 위변조를 막는 데 사용됩니다.
이러한 조건들을 만족하는 해싱 함수만이 데이터의 고유한 ‘지문’으로서 신뢰성을 갖고 다양한 분야에서 활용될 수 있습니다.
해싱 함수의 종류와 기법: 어떻게 지문을 만드는가?
해싱 함수를 만드는 방법, 즉 해싱 알고리즘은 매우 다양합니다. 간단한 데이터 구조에 사용되는 단순한 기법부터, 보안을 위해 극도로 복잡하게 설계된 암호학적 해시 함수까지 그 종류와 목적이 다릅니다.
데이터 구조를 위한 해싱 기법
주로 해시 테이블(Hash Table)과 같은 자료구조에서 빠른 데이터 저장을 위해 사용되며, 속도가 매우 중요합니다.
나눗셈법 (Division Method)
가장 간단하고 고전적인 방법입니다. 입력 값(Key)을 해시 테이블의 크기(M)로 나눈 ‘나머지’를 해시 값으로 사용하는 방식입니다.
h(key) = key % M
예를 들어, 크기가 11인 해시 테이블이 있고, 입력 키가 125라면 해시 값은 125 % 11 = 4가 됩니다. 125번 데이터는 해시 테이블의 4번 인덱스에 저장됩니다. 이 방법은 매우 빠르지만, M의 값에 따라 해시 값이 특정 패턴으로 쏠리는 경향이 있어 M을 소수(Prime Number)로 정하는 것이 중요합니다.
곱셈법 (Multiplication Method)
나눗셈법보다 좀 더 복잡하지만, M의 값 선택에 덜 민감하고 비교적 해시 값을 잘 분산시키는 방법입니다.
- 입력 키(key)에 0과 1 사이의 상수 A(보통 황금비의 소수 부분인 0.6180339887…)를 곱합니다.
- 결과값의 소수 부분만 취합니다.
- 여기에 해시 테이블의 크기 M을 곱한 후, 소수점 아래를 버리고 정수 부분만 취합니다.
h(key) = floor(M * (key * A % 1))
이 방식은 M이 2의 거듭제곱일 때도 잘 동작하여 컴퓨터 구조에 친화적이라는 장점이 있습니다.
암호학적 해시 함수 (Cryptographic Hash Function)
데이터의 무결성 검증이나 보안적인 목적으로 사용되는 해시 함수는 앞서 언급한 ‘충돌 저항성’을 매우 높은 수준으로 만족시켜야 합니다. 즉, 해시 값을 통해 원본 데이터를 유추하거나, 동일한 해시 값을 갖는 다른 데이터를 만들어내는 것이 거의 불가능해야 합니다.
MD5 (Message-Digest Algorithm 5)
과거에 널리 사용되었던 128비트 해시 함수입니다. 하지만 현재는 심각한 보안 취약점(충돌을 쉽게 만들 수 있음)이 발견되어, 파일의 무결성 검사 등 제한적인 용도로만 사용될 뿐, 비밀번호 암호화와 같은 보안이 중요한 분야에서는 절대로 사용해서는 안 됩니다.
SHA (Secure Hash Algorithm)
미국 국가안보국(NSA)이 설계한 표준 해시 함수군입니다.
- SHA-1: 160비트 해시 함수로, MD5와 마찬가지로 현재는 안전하지 않은 것으로 간주됩니다.
- SHA-2: SHA-224, SHA-256, SHA-384, SHA-512 등을 포함하는 함수군입니다. 이 중 SHA-256은 현재 블록체인(비트코인 등)을 비롯하여 수많은 보안 시스템과 디지털 서명 등에서 가장 널리 사용되는 매우 안전하고 신뢰성 높은 표준 해시 함수입니다. 256비트(32바이트) 길이의 고정된 해시 값을 생성합니다.
- SHA-3: SHA-2와는 다른 구조로 설계된 차세대 표준 해시 함수로, 보안성을 더욱 강화했습니다.
해싱 함수의 활용: 디지털 세상을 지탱하는 기둥
해싱 함수는 우리 눈에 보이지는 않지만, 현대 IT 기술의 거의 모든 영역에서 핵심적인 역할을 수행하고 있습니다.
1. 초고속 데이터 검색: 해시 테이블 (Hash Table)
해싱 함수의 가장 대표적인 활용처는 ‘해시 테이블(또는 해시 맵)’이라는 자료구조입니다. 해시 테이블은 (Key, Value) 쌍으로 데이터를 저장하는데, 해싱 함수를 이용해 Key를 해시 값(배열의 인덱스)으로 변환하여 Value를 해당 인덱스에 저장합니다.
저장 과정:
put(“사과”, “Apple”)
- “사과”라는 Key를 해싱 함수에 입력:
hash("사과")→ 3 - 배열의 3번 인덱스에 “Apple”이라는 Value를 저장합니다.
검색 과정:
get(“사과”)
- “사과”라는 Key를 해싱 함수에 입력:
hash("사과")→ 3 - 배열의 3번 인덱스로 직접 접근하여 “Apple”이라는 Value를 즉시 찾아냅니다.
이론적으로, 해시 테이블은 데이터의 양(n)에 상관없이 항상 O(1)의 매우 빠른 속도로 데이터를 검색, 삽입, 삭제할 수 있습니다. (물론 해시 충돌이 발생하면 성능이 저하될 수 있으며, 이를 해결하기 위한 Chaining, Open Addressing 등의 기법이 사용됩니다.) 파이썬의 딕셔너리(Dictionary), 자바의 해시맵(HashMap) 등 수많은 프로그래밍 언어에서 핵심적인 데이터 타입으로 사용되고 있습니다.
2. 안전한 비밀번호 저장
만약 웹사이트 데이터베이스에 사용자의 비밀번호가 ‘1234’와 같이 원본 그대로 저장되어 있다면, 데이터베이스가 해킹당하는 순간 모든 사용자의 계정 정보가 유출되는 대재앙이 발생합니다.
이를 방지하기 위해, 시스템은 사용자의 비밀번호를 해싱 함수(주로 SHA-256 이상)를 사용하여 해시 값으로 변환한 뒤 데이터베이스에 저장합니다.
- 회원가입: 사용자가 비밀번호 ‘password123’ 입력 →
hash('password123')→ ‘ef92b778bafe771e…’ 라는 해시 값을 DB에 저장. - 로그인: 사용자가 비밀번호 ‘password123’ 입력 →
hash('password123')→ ‘ef92b778bafe771e…’ 해시 값 생성 → DB에 저장된 해시 값과 일치하는지 비교.
해싱 함수의 ‘제1 역상 저항성’ 덕분에, 해커가 DB를 탈취하여 ‘ef92b778bafe771e…’라는 해시 값을 손에 넣더라도, 이 값으로부터 원래의 비밀번호 ‘password123’을 알아내는 것은 거의 불가능합니다. (실제로는 레인보우 테이블 공격 등을 막기 위해 Salt를 추가하는 등 더 복잡한 과정을 거칩니다.)
3. 데이터 무결성 검증 (Checksum)
우리가 대용량 파일을 인터넷에서 다운로드할 때, 종종 파일과 함께 ‘MD5’나 ‘SHA-256’ 체크섬(Checksum) 값이 함께 제공되는 것을 볼 수 있습니다. 이는 다운로드 과정에서 파일이 손상되거나 변조되지 않았는지, 즉 ‘무결성’을 확인하기 위한 것입니다.
- 파일 제공자는 원본 파일(
original.zip)을 SHA-256 함수로 해싱하여 해시 값(A)을 계산하고, 이 값을 웹사이트에 공개합니다. - 사용자는
original.zip파일을 다운로드합니다. - 사용자는 자신이 다운로드한 파일(
downloaded.zip)을 똑같은 SHA-256 함수로 해싱하여 해시 값(B)을 계산합니다. - 사용자는 자신이 계산한 해시 값
B와 웹사이트에 공개된 해시 값A를 비교합니다. - 만약
A와B가 정확히 일치한다면, 다운로드한 파일은 원본과 동일하며 손상되지 않았음을 100% 확신할 수 있습니다. 만약 단 1비트라도 다르다면, 두 해시 값은 완전히 다른 값이 나오게 됩니다.
이러한 무결성 검증 원리는 블록체인의 핵심 기술이기도 합니다. 블록체인에서 각 블록은 이전 블록의 해시 값을 포함하고 있어, 과거의 거래 내역을 조금이라도 위변조하려는 시도가 있으면 모든 후속 블록의 해시 값이 연쇄적으로 바뀌게 되어 즉시 탐지됩니다.
마무리: 보이지 않는 질서의 설계자
해싱 함수는 임의의 데이터를 고정된 길이의 고유한 ‘지문’으로 변환하는 강력하고 우아한 수학적 도구입니다. 결정론, 균일성, 충돌 저항성이라는 엄격한 조건들을 만족하는 좋은 해싱 함수는, 우리가 매일 사용하는 수많은 기술들의 근간을 이루고 있습니다.
해시 테이블을 통해 우리에게 O(1)의 경이로운 검색 속도를 선물하고, 우리의 소중한 비밀번호를 안전하게 지켜주며, 데이터가 원본 그대로임을 보증하는 신뢰의 인장 역할을 합니다. 복잡하고 무질서해 보이는 데이터의 세계에 보이지 않는 질서와 효율, 그리고 안전을 불어넣는 핵심 설계자, 그것이 바로 해싱 함수의 진정한 가치입니다.