[알고리즘] 알고리즘 Hash function

1. 해시 함수의 개념

해시 함수는 입력값(데이터)을 고정된 크기의 해시 값 또는 해시 코드로 변환하는 수학적 함수이다. 주로 데이터베이스, 암호화, 디지털 서명, 데이터 무결성 검증 등 다양한 컴퓨터 과학 분야에서 활용된다. 해시 함수의 가장 중요한 특징은 입력값이 약간만 달라져도 결과값이 크게 달라지는 `민감도`를 갖추고 있으며, 일정한 시간 내에 입력값을 해시값으로 빠르게 변환할 수 있어야 한다. 해시 함수는 일방향성(one-wayness)을 가져, 해시값으로부터 원래 데이터를 역산하는 것이 극히 어렵다. 예를 들어, 비밀번호 저장에는 해시 함수를 이용해 원문을 숨기고, 이를 통해 데이터 유출 시 원본 정보 유출을 방지한다. 해시 함수의 또 다른 중요한 특징은 충돌 저항성이다. 이는 서로 다른 두 입력값이 같은 해시값을 갖는 경우가 극히 드문 특징이며, 이상적인 해시 함수는 충돌 확률이 매우 낮다. 예를 들어, 현재 사용되는 SHA-256 해시 함수는 2의 256제곱(약 1.16×10의 77승) 가지의 가능한 해시값을 만들어 내는데, 이는 사실상 충돌이 발생하지 않을 정도로 안전하다고 평가받는다. 해시 함수는 빠른 계산 속도와 함께, 소량의 입력 …