요즘 출판되는 책의 맨 뒷면을 보면 책마다 서로 다른 ISBN 번호가 인쇄되어 있는 것을 볼 수 있습니다. 책을 분류하는 것과 같은 관리 목적에서 이 ISBN 번호는 매우 유용하게 사용될 것입니다. 누군가가 어떤 책을 가지고 있다면 단지 책의 뒷면을 보는 것만으로도 쉽게 그 책의 ISBN 번호를 알 수 있습니다. 하지만 ISBN 번호를 알고 있다고 하더라도 컴퓨터나 분류표의 도움 없이 도서관에서 그 번호에 해당하는 책을 찾아내는 것은 대단히 어려운 일이 될 것입니다. 일반적으로 해쉬알고리즘은 ISBN과 같은 특성을 가지는 고정된 짧은 길이의 데이터로 생각할 수 있습니다.
책보다 좀 더 전산적인 관점으로 이동하여 정수의 범위에서 살펴보도록 하겠습니다. 해쉬알고리즘을 설명하기 위해 정수의 범위에서 살펴보는 이유는 우리가 표현할 수 있는 모든 전자적 형태의 문서(데이터)는 하나의 정수로 표현할 수 있기 때문입니다. "abcd" 라는 문자열 데이터는 1,633,837,924라는 정수로 표현할 수 있습니다. 1K바이트의 데이터라면 대략 2,400자리 정도의 정수로 표현될 것입니다. 해쉬알고리즘은 정수의 형태로 표현된 전자문서로부터 고정된 길이의 정수를 얻는 방법으로 통상적으로 계산합니다.
- 부연설명 -
문자열 "abcd"를 ASCII 방식으로 인코딩하면 { 0x61, 0x62, 0x63, 0x64 } 가 됩니다. 이를 연접하면 16진수 값 0x61626364 또는 10진수 값 1,633,837,924 의 정수로 표현할 수 있습니다. 1,024 바이트의 데이터를 정수 n이라고 하면 n < 2 ^ (8 * 1024) 가 됩니다. 따라서, n의 자리수 = log(n) < log(2 ^ (8 * 1024)) = 8 * 1024 * log(2) = 2466.04 가 되어 10진수로 최대 2467 자리 정수가 만들어집니다.
정수의 형태로 표현된 전자문서의 개념을 파악하였다면, 이로부터 고정된 길이의 정수를 얻는 방법에 대해 살펴보겠습니다. 임의의 정수로부터 고정된 길이의 정수를 얻는 가장 간단한 방법으로 정수를 특정한 값으로 나눈 나머지를 구하는 것을 생각해 볼 수 있습니다. 모든 정수의 나머지 연산에 대한 결과값은 0 ~ [제수-1] 의 값에 반드시 포함되므로 [제수-1]에 해당하는 고정된 길이의 정수를 얻게되는 것입니다.
- 부연설명 -
위에서 살펴본 방법으로 해쉬알고리즘을 하나 간단하게 설계해 보도록 하겠습니다. 정수를 10 으로 나눈 나머지를 계산하는 방법을 새로 설계한 해쉬알고리즘이라고 하겠습니다. 우리가 어떤 정수(가령 위에서 예를 든 1,633,837,924)를 가지고 있다고 하면 10으로 나눈 나머지 값(4)은 금방 계산해 낼 수 있습니다. 하지만 특정한 나머지 값(4)로 부터 우리가 처음 가지고 있던 그 정수를 유추해 내는 것은 거의 불가능합니다.
해쉬알고리즘이 되기 위해서는 위에서 나열한 기본적인 요건 이외에도 또 다른 중요한 문제가 남아 있습니다. 나머지 연산의 경우 비록 특정한 나머지 값으로부터 처음 가지고 있던 정수를 유추하는 것은 불가능하다고 할지라도 같은 나머지 값을 가지는 무수히 많은 정수를 찾을 수 있다는 점입니다. ISBN의 예로 돌아가서 같은 ISBN 번호를 가지는 서로 다른 책이 무수히 많이 존재한다면 이는 관리상 엄청난 문제를 야기할 것이 틀림없습니다. 이렇게 해쉬알고리즘을 수행한 결과값과 같은 결과 값을 가지는 다른 데이터를 발견하였을 경우 이를 해쉬알고리즘에서 충돌(Hash Collision)이 발생하였다고 합니다. 값의 범위가 무한대인 정수값을 고정된 크기의 작은 정수로 줄이는 것이기 때문에 해쉬알고리즘의 충돌은 필연적으로 발생할 수 밖에 없습니다. 다만 이를 충분히 어렵게 하여 충돌이 발생하는 것을 찾아내는 것이 시간상으로나 비용상 불가능하게 만드는 것이 해쉬알고리즘을 설계하는 가장 기본적인 원칙입니다. 잘 설계된 해쉬알고리즘은 다음과 같은 특성을 가집니다.
- 해쉬알고리즘은 어떤 크기의 입력도 받아 들일 수 있어야 한다.
- 해쉬알고리즘의 계산 결과는 고정된 길이의 정수로 나타난다.
- 해쉬알고리즘은 주어진 입력으로부터 쉽게 계산 결과를 얻을 수 있어야 한다.
- 해쉬알고리즘의 계산 결과가 주어졌을 때, 원래의 입력 값을 찾는 것이 계산 불가능해야 한다. [일방향성]
- 어떤 입력 값이 주어졌을 때, 같은 계산 결과를 얻을 수 있는 다른 입력 값을 찾는 것이 계산 불가능해야 한다. [약한 충돌회피성]
- 같은 계산 결과를 얻을 수 있는 임의의 서로 다른 두 입력 값을 찾는 것이 계산 불가능해야 한다. [강한 충돌회피성]
해쉬알고리즘이 갖추어야 할 여섯 가지 특성 중에서 처음 셋은 기본적 특성을 정리한 것입니다. 임의의 정수를 입력으로 받아야 하므로 입력의 크기에 제한을 받아서는 안되며 고정된 길이는 앞에서 설명한 것과 같습니다. 빠른 계산 속성은 필요요건이라기 보다 요구사항으로 판단하시면 될 것입니다.
네 번째 항목은 일방향 특성을 나타냅니다. 고정된 길이의 작은 정수로 매핑하는 것이므로 해쉬결과값으로부터 원래의 데이터를 찾는 것이 불가능함은 당연한 내용입니다.
다섯 번째 항목과 여섯 번째 항목은 모두 해쉬 알고리즘의 충돌을 얼마나 방지할 수 있는가에 관한 내용으로 얼핏 비슷한 말처럼 보이기도 합니다. 일반적으로 다섯 번째 항목의 조건을 완화한 것이 여섯 번째 항목에 해당되는 것입니다. 특정한 경우에 해당하는 것을 찾는 것보다 일반적인 법칙을 찾는 것이 어렵듯이, 다섯 번째 항목의 충돌을 찾아내는 것 보다는 여섯 번째 항목의 충돌을 찾는 것이 훨씬 쉽습니다. 이는 여섯 번째 조건을 만족하는 것이 다섯 번째 조건만을 만족하는 것보다 해쉬충돌의 방지라는 면에서 훨씬 강력하다는 것을 의미합니다. 일반적으로 다섯 번째 해쉬알고리즘의 특성을 약한 충돌회피성(Weak Collision Resistance)이라고 하고 여섯 번째 해쉬알고리즘의 특성을 강한 충돌회피성(Strong Collision Resistance)이라고 합니다. 해쉬알고리즘의 충돌회피성에 관해서는 따로 설명하도록 하겠습니다.
해쉬알고리즘은 앞에서 설명한 대칭키 알고리즘과 공개키 알고리즘에 비해 상대적으로 덜 알려져 있지만, 사용빈도 및 중요성은 위의 두 알고리즘 보다 높습니다. 약한 충돌회피성이 있기 때문에 원래의 데이터가 위변조 되었는지 확인하기 위한 용도로 많이 사용되며 원래의 데이터를 대표할 수 있는 고정된 크기의 값이기 때문에 서명 등의 용도로 활용됩니다. 부가적으로 난수 생성이나 메시지 인증코드 등에서 활용되고 있습니다. 대표적인 해쉬알고리즘으로는 MD5, SHA-1, SHA-2 등의 외산 알고리즘과 HAS-160의 국산 알고리즘이 있습니다. 공인인증체계에서는 SHA-1을 주로 사용하며 부분적으로 HAS-160을 사용할 수 있도록 되어 있습니다.
