해싱 함수를 만들자

심지혜·2024년 4월 23일

해싱

해싱은 수학적 알고리즘을 사용하여 데이터를 매핑하고 압축하는 기술입니다. 이 기술은 다양한 크기의 입력 데이터(예: 이미지)를 동일한 크기의 출력 데이터(예: 데이터 지문, 디지털 ID)로 변환합니다. 해시 함수는 임의의 입력 비트열에 대해 일정한 길이의 안전한 출력 비트열을 생성하며, 정보 보호 분야에서 활발히 활용됩니다.

해시 함수의 보안 요구사항

속도: 계산이 용이하고 빨라야 합니다.
결정성: 동일한 입력에 대해 여러 번 해시 함수를 적용해도 동일한 출력이 나와야 합니다.
균일성: 데이터 크기와 상관없이 전반적으로 동일한 양의 해싱을 수행해야 합니다.
고정 크기: 출력은 고정 크기가 되어야 합니다(너무 작으면 충돌이 발생할 수 있습니다).
비가역성: 해시값으로부터 역으로 메시지를 알아낼 수 없어야 합니다(역상 정항성).
아발란치 효과: 정보가 변경되면 단일 문자가 변경되더라도 출력이 크게 변해야 합니다.
충돌 회피: 두 개의 메시지가 같은 해시값을 갖는 것을 충돌이라고 하는데, 이를 발견하지 않도록 해야 합니다.
제2역상 저항성: 최초 메시지가 확인된 상태에서 동일한 해시값이 나오는 다른 입력 메시지를 찾기 어려워야 합니다.

해시 함수 기법

나누기(Division)의 나머지(%)
접기(Folding): Shift Folding, Boundary Folding
중간 제곱(Mid-square): 키를 제곱하고 중간 부분을 결과로 사용
추출(Extraction): 키의 일부만 사용하여 결과로 사용

좋은 해시 함수의 특징

계산이 쉽고 빠름
인덱스 범위에 걸쳐 실제 발생하는 키가 균등한 분포를 가짐
수학적으로 일대일로 관련 키 값 집합을 사용

해시의 활용

해시는 문자열(string)을 기준으로 정보를 기록하고 관리할 때 주로 사용됩니다. 인덱스 기반의 단순 배열을 사용할 수 없는 경우, key:value의 매핑 구조에서 key가 문자열일 때 해시를 활용합니다. 예를 들어, 등록된 전화번호를 기준으로 '개인안심번호'를 생성하는 데 해시가 사용됩니다.

해시는 key:value 매핑 구조입니다.
대부분의 경우 key가 문자열입니다.
put/get/getOrDefault 메서드를 사용하여 데이터를 저장하고 값을 가져올 수 있습니다.

해싱 함수에 대해 간략하게 알아보았으니, 해싱 함수를 만들어 봅시다.

1. 일단 접기

아이디어

고정된 길이를 가져야하니, 문자열을 일정한 길이로 나누는 것이 좋을 것 같습니다.

코드 구현

def folding_hash(input_data, table_size, hash_length=8):
    input_bytes = input_data.encode()
    chunks = [input_bytes[i:i+4] for i in range(0, len(input_bytes), 4)]
    hash_value = sum(map(lambda x: int.from_bytes(x, byteorder='little'), chunks))
    hash_value = hash_value % table_size
    return f"{hash_value:0{hash_length}d}"

테스트

보니까 이게 대부분의 해싱 함수 요구사항을 만족하지 못하는 것 같습니다.

실패!

2. 검색 좀 해보기

아이디어

제 아이디어는 아닌데 이렇게 ASCII 코드 값을 사용하고 2^32로 나머지 연산을 수행해서 길이가 고정되게끔 했습니다.
13은 제가 가장 좋아하는 소수 중에 하나라 넣었습니다.

코드 구현

def custom_hash_function(message):
    hash_value = 0
    for char in message:
        hash_value = (hash_value * 13 + ord(char)) % (2**32)
    return hash_value

테스트

가장 신경썼던 고정 크기 출력을 해결했습니다.
균일성을 만족합니다.
여전히 비가역성, 충돌 회피, 제2역상 저항성을 만족하지 못합니다.

3. 비트 연산 더하기

아이디어

일단 제2역상 저항성을 높이기 위해 비트 연산을 넣기로 했습니다.
AND와 OR, XOR 중에 고민하다가 XOR이 가장 이쁜 것 같아서 선택했습니다.

코드 구현

def custom_hash_function(message):
    hash_value = 0
    for char in message:
        hash_value = (hash_value * 13) ^ (ord(char) << 1) ^ ord(char)
    return hash_value