해싱이란
해시(hash)란 다양한 길이를 가진 데이터를 해쉬함수(hash function)를 활용하여 고정된 길이의 데이터로 매핑(mapping)한 값입니다. 이를 이용하여 특정한 배열의 인덱스나 위치를 입력하고자 하는 데이터의 값을 이용해 저장하거나 찾을 수 있습니다다.
해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 주소또는 색인 삼아 데이터를 키(key)와 함께 저장하는 자료구조이다.
해시의 장단점
장점
1. 데이터 검색, 저장 속도가 빠르다.
2. 충돌이 없다면 해쉬테이블은 시간복잡도 O(1)로 짧다!
단점
1. 일반적으로 저장공간이 좀더 많이 필요하다.
2. 여러 키에 해당하는 주소가 동일한 경우 충돌을 해결하기 위한 별도 자료구조가 필요하다.
해시의 활용
사이버 보안
사이버 공간은 해싱을 광범위하게 사용합니다. 보안상의 이유로 좋은 해시 함수는 항상 단방향 해시 방법을 사용하는 단방향 절차입니다. (key -> 해시 함수 -> data 로만 변환이 되기 때문에 단방향이라고 합니다.) 이렇게 하면 해커가 원본 데이터를 얻기 위해 신속하게 해시를 리버스 엔지니어링할 때 암호화가 쓸모가 없게 됩니다.
블록 체인
임의 길이의 입력 항목이 정의된 길이의 출력 항목을 미러링하도록 하는 기술을 말합니다. 암호화폐의 블록체인 응용 프로그램의 경우 가변 기간의 트랜잭션은 특정 해싱 알고리즘에 의해 처리되며 모두 설정된 길이의 출력을 생성합니다. 이는 입력 트랜잭션의 기간에 관계없이 적용됩니다.
블록체인에서 해싱이 사용되는 이유는 무엇입니까? 해싱은 블록체인의 각 블록에 고유한 ID를 부여하므로 블록체인을 변경하면 데이터가 변형되는 영향을 끼치므로 사실상 복제가 불가능합니다.
해시 충돌
해시 충돌은 해시 함수를 사용하여 서로 다른 입력 값에 대해 동일한 해시 값이 생성되는 현상을 말합니다. 이는 해시 함수의 출력 범위가 입력 공간보다 작기 때문에 발생할 수 있습니다.
예를 들어 해시 함수가 우선, 간단한 해시 함수를 정의해보겠습니다. 이 예시에서는 문자열을 입력으로 받고, 문자열의 각 문자의 ASCII 값을 더한 후 모듈러 연산을 이용하여 해시 값을 계산하는 해시 함수를 사용하겠습니다.
h(s) = (∑(s[i]) % 10)
입력 1 : "abc"
해시 값 : h("abc") = (97 + 98 + 99) % 10 = 294 % 10 = 4
입력 2: "acb"
해시 값 : h("acb") = (97 + 99 + 98) % 10 = 294 % 10 = 4
이런식으로 동일한 해시 값을 나타나게 될 수도 있습니다.
해시 충돌이 발생하는 주요 이유는 해시 함수의 출력 범위가 입력 공간보다 작기 때문입니다. 해시 함수는 임의의 크기를 가진 데이터를 고정된 크기의 해시 값으로 매핑하는 함수입니다. 이 것이 장점으로 작용할 수 도 있지습니다. 하지만 모든 상황을 포함하면 데이터의 크기는 무한하지만, 인간이 만든 해시 함수의 효율을 위해서 출력 범위는 유한하므로 서로 다른 입력에 대해 동일한 해시 값이 생성될 수 있습니다.
이러한 충돌을 확인하기 위해서 최근에 올렸던 비둘기집 원리를 활용하여서 입력값을 제한 할 수 있습니다.
해시 알고리즘 MD5로 예를 들면, 128비트로 구성된 결과값, 즉 32자리의 16진수 값을 반환한다. 이 문자열의 길이는 변하지 않는다. 한 비트 단위는 0 혹은 1이라는 두 가지 경우의 수를 가진다는 점에서 128비트는 총 2^128 만큼의 경우의 수를 표현할 수 있다. 예를 들어 입력 된 값이 2^128보다 많다면 되면 최소한 한 쌍의 입력 값은 그 결과 값이 동일하고 해시 충돌이 무조건 일어날 것 입니다.
해시 함수 코딩하기
저는 FNV-1a 해시 알고리즘을 활용해서 코딩을 해보았습니다.
방식은 다음과 같습니다.
1.해시 값을 초기값으로 설정합니다.
2. 입력 데이터의 각 바이트(왼쪽에서 오른쪽으로)에 대해 다음을 수행합니다:
- 현재 바이트를 해시 값과 XOR 연산합니다.
- 해시 값을 고정된 소수로 곱합니다
- 최종 결과로 얻은 해시 값을 출력으로 반환합니다.
def fnv_hash(input_data):
# FNV 해시를 사용한 소수(prime)와 초기값(offset basis) 설정
FNV_PRIME = 0x00000100000001B3
FNV_OFFSET_BASIS = 0x6C62272E07BB014262B821756295C58D
# 입력 데이터가 바이트 유사 객체인지 확인
if not isinstance(input_data, (bytes, bytearray)):
input_data = str(input_data).encode('utf-8')
# 해시 값을 초기값으로 설정
hash_value = FNV_OFFSET_BASIS
# FNV-1a 해시 알고리즘 수행
for byte in input_data:
hash_value ^= byte
hash_value *= FNV_PRIME
# 128비트 해시 값을 반환
return hash_value & 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
input_data = "hello world!"
hash_result = fnv_hash(input_data)
print(hash_result) # 10진수
print(hex(hash_result)) #16진수읽어주셔서 감사합니다.
