해시 함수

Hash Function

임의의 크기의 데이터를 입력받아 고정된 크기의 출력을 반환하는 함수

• 예시: 비트별 XOR

  	Bit 1	Bit 2	...	Bit n
  Block 1	$x_{11}$	$x_{12}$	...	$x_{1n}$
  Block 2	$x_{21}$	$x_{22}$	...	$x_{2n}$
  ...	...	...	...	...
  Block m	$x_{m1}$	$x_{m2}$	...	$x_{mn}$
  Hash Output	$y_1$	$y_2$	...	$y_n$

  ex. 두 개의 블록 $x_{11}, x_{12}, \ldots, x_{1n}$/ $x_{21}, x_{22}, \ldots, x_{2n}$을 XOR하여 $y_1, y_2, \ldots, y_n$을 반환

임의 길이의 메시지를 입력받아

고정된 길이의 메시지 다이제스트

를 출력하는 함수 $h$

1. 효율적 계산
   (Computational Efficiency)
   • 입력 $m$이 주어지면 $h(m)$을 효율적으로 계산할 수 있어야 함
2. 단방향성
   or
   원본 숨김 저항성
   (One-way or Pre-image Resistance)
   • $y$가 주어졌을 때 $h(m')=y$를 만족하는 $m'$을 찾는 것이 계산적으로 불가능해야 함
3. 제2 원본 숨김 저항성
   or
   약한 충돌 저항성
   (Second Pre-image Resistance or Weak Collision Resistance)
   • $m$이 주어졌을 때 $h(m')=h(m)$을 만족하는 $m'$을 찾는 것이 계산적으로 불가능해야 함
4. 충돌 저항성
   (Collision Resistance)
   • $m, m'$이 주어졌을 때 $h(m)=h(m')$을 만족하는 $m, m'$을 찾는 것이 계산적으로 불가능해야 함

1. 초기화 벡터 (IV: Initialization Vector)
2. 메시지 블록 (Message Block)
3. 압축 함수:c (Compression Function)
4. 해시 출력 (Hash Output)

1. 초기값
   • $A, B, C, D, E$
2. 라운드 함수
   • $f_t(B, C, D)$ - 라운드 번호 $t$에 따라 다른 논리 연산 수행
3. 비트 순환 이동
   • $A$와 $B$비트는 각각 5 비트와 30비트 순환 이동
   • 순환 이동은 비트를 왼쪽으로 회전시키며, 가장 왼쪽 비트는 가장 오른쪽 비트로 이동
4. 연산 및 업데이트
   • 각 라운드에서 $A, B, C, D, E$는 각각 $f_t$와 다른 연산을 통해 갱신됨
   • $A = f_t(B, C, D) + K_t + W_t + E$와 같은 식으로 갱신

• $A = ((A << 5) + f_t(B, C, D) + E + K_t + W_t)$
• $B = A$ (기존 $A$값을 $B$에 저장)
• $C = B << 30$
• $D = C$
• $E = D$

• $f$는 블록 순열을 위한 함수로, XOR, AND, NOT 연산으로 구성됨