[Hash] 해쉬함수에 대해

해시함수

해시함수란 임의의 길이의 입력을 받아 고정된 길이의 출력을 하게끔 하는 함수이다.

우리가 만약 메이플 스토리 (참고로 난 안한다. 유서깊은 게임이라 예시로 든다.)를 하기위해 X슨에 가입해야된다고 하자.

우리가 입력해야하는 것은 아이디, 이메일 등과 비밀번호, 개인정보 등 이다.

이 입력받은 데이터를 회사 DB에 고대로 저장하면 회사 직원들도 이걸 볼 수 있고, 혹여나 해킹 당했을 때,
모든 유저의 개인정보가 유출된다는 크나큰 단점이 있다.

그래서 고안된 것이 해시함수이다.
해시함수를 이용해 유저가 입력한 비밀번호를 암호화한 상태로 DB에 저장하면 위의 문제점을 해결 할 수 있다.

특징

1. 해시함수는 동일 input에 대해 동일 output이 유지된다.

2. input이 조금이라도 달라지면 output은 무지막지하게 달라진다.

3. output으로 input의 역추적이 불가하다.

4. 해시 충돌. 다른 input, 동일 output

문제점

해시함수를 이용해 비밀번호를 암호화한다고 한들, 역추적이 완전히 불가능한 것은 아니다.

암호화한 코드는 절대 변하지 않는다. 이것이 큰 문제점이다.

이렇게 암호화된 코드들의 역연산 결과를 모아놓은 곳을 레인보우 테이블(Rainbow Table)이라고 한다.

레인보우 테이블에서 암호화된 코드를 검색하면 이미 해커들이 역연산 해놓은 결과를 알 수 있다.

보완

솔트(Salt)

솔트란 해시함수에 입력값을 넣기 전에 임의의 문자열을 추가하는 것을 의미한다.

만약 A라는 사람과 B라는 사람의 비밀번호가 123으로 같다고 생각해보자.

그냥 해시함수에 넣으면 두 사람의 해시함수값은 같을 것이다.

하지만 임의의 문자열을 각각 붙여
A에게는 ABC123, B는 ZXC123으로 해시함수에 입력하면 같은 비밀번호라 할지라도
다른 해시함수값을 가지게된다.
이는 해시함수의 단점을 보완할 수 있는 안전한 방법이다.

관련 문제

관련해서 쉬운 문제로 백준에 15829번이 있다.

백준 15829번

import sys
n = int(sys.stdin.readline().rstrip())
key = sys.stdin.readline().rstrip()


r = 31
m = 1234567891

#a부터 z까지 고유번호 생성

alpha = list(map(chr, range(97,123)))

result = 0

for i in range(len(key)): #I:현재 인덱스값
    if key[i] in alpha: #만약 알파벳중에 있으면요
        #알파벳 리스트에서 찾은 key[i]의 인덱스값 + 1 * 31**(i+1)을 result에 더합니다.
        result += (alpha.index(key[i]) + 1) * r**(i)


print(result%m)