일방향 해시함수 용어 정리

1. 정의역 (Domain, D)

• 정의: 해시 함수에 입력될 수 있는 모든 가능한 값들의 집합입니다.
• 특징:
  • 보통 임의 길이의 문자열이나 데이터가 정의역에 해당합니다.
  • 예: 텍스트 파일, 비밀번호, 이미지, 바이너리 코드 등.
• D는 매우 큽니다. 실질적으로는 무한에 가까운 크기를 갖습니다. 예를 들어, 길이가 최대 1MB인 문자열들을 정의역으로 삼는다면 경우의 수는 상상할 수 없을 정도로 많습니다.

---

2. 치역 (Range, R)

• 정의: 해시 함수가 출력할 수 있는 모든 가능한 해시값들의 집합입니다.
• 특징:
  • 해시 함수는 일반적으로 고정된 크기의 출력값을 제공합니다.
  • 예: SHA-256은 항상 256비트(32바이트) 해시 값을 출력 ⇒ ∣R∣=2256|R| = 2^{256}∣R∣=2256 가지 경우의 수.
• 이는 정의역보다 훨씬 작습니다. 그래서 ∣D∣>∣R∣|D| > |R|∣D∣>∣R∣ 라고 표현합니다.

---

3. 해시 함수 h : D → R

• 정의: 임의 길이의 입력(정의역)을 고정 길이의 출력(치역)으로 매핑하는 함수입니다.
• 조건 ∣D∣>∣R∣:
  • 이는 비둘기집 원리 (Pigeonhole Principle) 에 의해, 반드시 충돌(collision)이 존재함을 의미합니다.
  • 즉, 서로 다른 입력 x1≠x2∈Dx_1 \ne x_2 \in Dx1​=x2​∈D 에 대해 h(x1)=h(x2)h(x_1) = h(x_2)h(x1​)=h(x2​) 인 경우가 존재하게 됩니다.
• 하지만 좋은 해시 함수는 이런 충돌을 찾기 어렵게 설계됩니다.

---

일방향 해시 함수는 다음 세 가지 성질을 만족해야 함

1. 일방향성 (One-wayness): 입력을 알 때 출력은 쉽게 계산 가능하지만, 출력을 알 때 입력을 역으로 찾는 것은 계산적으로 어려움.
2. 약한 충돌 저항성 (Second-preimage resistance): 주어진 입력 xxx 와 h(x)h(x)h(x) 가 있을 때, h(x)=h(x′)h(x) = h(x')h(x)=h(x′) 를 만족하는 다른 x′x'x′ 를 찾는 것이 어렵다.
3. 강한 충돌 저항성 (Collision resistance): h(x1)=h(x2)h(x_1) = h(x_2)h(x1​)=h(x2​) 를 만족하는 어떤 두 값 x1≠x2x_1 \ne x_2x1​=x2​ 를 찾는 것이 어렵다.