해쉬함수는 다음과 같은 기본 성질을 가져야 합니다.

 

1. 역상 저항성

   주어진 임의의 출력값 y 에 대해, y = h(x) 를 만족하는 입력값 x 를 찾는 것이 계산적으로 불가능하다.

 

2. 두 번째 역상 저항성

   주어진 입력값 x 에 대해 h(x) = h(x'),  x ≠ x' 를 만족하는 다른 입력값 x' 를 찾는 것이 계산적으로 불가능하다.

 

3. 충돌 저항성

    h(x) = h(x') 를 만족하는 임의의 두 입력값 x, x' 를 찾는 것이 계산적으로 불가능하다.

 

위의 성질들이 필요한 이유는 다음과 같은데요 ...

 

일단 위의 3가지 성질을 잘 익혀 두세요 ....

이것은 해쉬함수를 공격하는 방법이기도 합니다~~~

 

<역상 저항성이 필요한 이유>

RSA 알고리즘을 이용한 서명에서 A 가 공개키 (n,e) 를 갖는다고 가정하자.

공격자 C는 임의의 값 y를 선택하여 z = y^e mod n 을 계산하고 y 가 z 에 대한 A 의 서명이라고 주장할 수 있다.

만약 C 가 h(x) = z 인 x 를 찾는다면 위조가 가능하다.

 

<두 번째 역상 저항성이 필요한 이유>

공격자 C 가 h(x) 에 대한 A 의 서명을 관찰한 후 h(x) = h(x') 가 되는 메시지 x' 를 찾아서 A 가 x' 에 서명했다고 주장할 수 있다.

 

<충돌 저항성이 필요한 이유>

공격자 C 가 A 가 서명한 메시지 x 를 정확히 안다면 x 의 이미지의 역상을 찾는 것보다 오히려 충돌쌍인 (x, x') 를 찾는 것이 더 쉬울 수 있기 때문이다.

 

--------------------------------------------------------------------------------------------------------------------------

 

1. 압축 : 임의의 길이의 이진 문자열을 일정한 크기의 이진 문자열로 변환해야 한다.

 

2. 계산의 용이성 : x가 주어지면 H(x)는 계산하기 쉬워야 한다.

 

3. 역상저항성(일방향성) : 입력을 모르는 해시값 y가 주어졌을 때, H(x')=y를 만족하는 x를 찾는 것은 계산적으로 어려워야 한다.

 

4. 2번째 역상저항성(약한 충돌 회피성) : x가 주어졌을 때 H(x')=H(x)인 x'(≠x)을 찾는 것은 계산적으로 어려워야 한다.

 

5. 충돌저항성(강한 충돌 회피성) : H(x')=H(x)인 서로 다른 임의의 두 입력 x와 x'을 찾는 것은 계산적으로 불가능하다.