암호학 - Hash Function

Hash 함수는 정확히 암호학 ... ... 이라기 보다는 일종의 압축(?) 알고리즘이라고 볼 수 있습니다만,

보안 응용분야에 널리(?) 사용되고 있기 때문에 ... 암호학의 범주안에 들어오는 것 같아 소개를 합니다 ...

처음에 Hash 함수를 압축 알고리즘이라고 표현을 했는데,

엄밀히 말하면 ... ... 임의의 메시지를 줄여서 특별한 정보로 만드는것 ... 이라고 봐야겠네요 ...
그 특별한 정보를 몇몇 책에는 메시지의 '지문'과 같은것 이라고 표현을 하기도 합니다
즉, Hash 값은 ... 원 메시지를 대신할 수 있는 작은 값으로 볼 수 있습니다.

하지만 ... 문제는 ... ... N:M 의 함수에서 ... N<M 이라면 결국 어딘가에는 충돌쌍이 존재한다는 거지요 ... ...

그래서 Hash는 충돌쌍을 예측하기 매우 어렵게 만들어야 합니다...

이 Hash에 대한 얘기는 ... ... 가장 흔하게 알려진게 ... Birthday Paradox ... 지요
http://en.wikipedia.org/wiki/Birthday_Paradox

그럼 왜 Hash가 필요하냐 ... ... ... 그것은 바로 효율때문입니다 ...
앞서 전자서명(http://reinliebe.tistory.com/29)에 대한 설명을 했었는데

결국 메시지의 n제곱을 계산해야하기 때문에, 메시지 길이가 길면 연산시간이 매우 오래걸리지요 ...
따라서 원본 메시지를 대신할 그 무엇인가가 필요하게 되고 ...
실제로 그런 용도로 많이 쓰입니다 ...



앞서 RSA를 언급하면서 썼던 공인인증서 예입니다 ...

서명 해시 알고리즘에 SHA1 이라고 적힌 것을 볼 수 있습니다 ...
알게 모르게 Hash 알고리즘은 주변에서 이미 널리 사용되고 있지요 ...

결국 최종적으로 ...
Hash 알고리즘은 ...

1. 입력값보다 출력값이 작아야 한다.
2. 계산이 용이해야 한다.
3. 출력값을 보고 입력값을 예측할 수 없어야 한다.
4. 같은 Hash값을 갖는 서로다른 입력값이 알려지면 안된다(찾기 어려워야 한다)

... 이정도로 줄일 수 있겠네요 ...

출처 - http://reinliebe.tistory.com/