해시 충돌: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
앞문단 정리. '충돌 저항성' 문단은 암호학 부분으로 이동함 |
|||
13번째 줄:
[[암호화 해시 함수]]의 중요한 요소 중 하나는 계산적으로 충돌을 찾아내는 것이 불가능해야 한다는 것이다. 해시 함수 출력 값의 충돌을 찾아낼 수 없다면 출판, 간행물의 원본이 변하지 않았음을 확인하는 값으로서 해시 함수의 출력값을 이용할 수 있다. 여기서 충돌을 찾아내는 것이 '불가능'하다고 하는 것은 해시 함수의 출력 값 범위 내에서 어떤 알고리즘을 사용하더라도 해시 충돌을 일으키는 값을 다항시간 내에 찾아낼 수 없다는 것을 의미하며, 여기서 ''가능''하다는 것은 [[생일 공격|생일 공격(Birthday attack)]]의 알고리즘 보다 훨씬 빠르다는 것이다.
해시 충돌을 일으키는 임의의 두 값을 찾는 과정을 '충돌 공격(collision attack)'이라고 한다. 또한 주어진 값에 대해 그 값과 해시 충돌을 일으키는 값을 찾는 것은 [[역상 공격]]이라고 한다. [[암호 공격]]라는 측면에서 보면
=== 충돌 저항성 ===
20번째 줄:
'''약한 충돌 저항성''': 주어진 <math>x</math>에 대해, <math>H(x) = H(y)</math>인 <math>y \neq x</math>를 찾는 것이 어려울 때 해시 함수가 약한 충돌 저항성을 가지고 있다고 한다. 주어진 패스워드를 입력 값으로 해시 함수에 넣고, 그것을 초기 값 (<math>x</math>)이라고 하자. 만약 <math>x</math>에 대한 출력 값과 같은 출력 값을 갖는 또다른 패스워드를 찾을 확률이 해시 함수의 출력 값 범위 내에서 [[무시 가능 함수|무시 가능(negligible)]]할 때 이 함수는 약한 충돌 저항성을 가지고 있다고 한다.
'''강한 충돌 저항성''': <math>H(x) = H(y)</math>와 같이 같은 해시 출력 값을 갖는 <math>x</math>와 <math>y</math>를 찾는 것이 함수의 출력 값 범위 내에서 [[무시 가능 함수|무시 가능(negligible)]]할 때 해시 함수 <math>H</math>는 강한 충돌 저항성을 가진다고 한다.
==같이 보기==
| |||