[정보보호이론] Chapter 3 일방향 해시함수
요약
컴퓨터로 처리하는 메시지에 대해서도 지문이 있었으면 할 때가 있습니다. 이 때는 2개의 메시지가 동일한지 아닌지를 조사할 때 메시지를 직접 비교하는 것이 아니라, 메시지의 지문을 비교하여 판정합니다.
일방향 해시 함수
만약 어제의 파일과 오늘의 파일이 같은 파일인지 무결성 점검을 해야한다고 생각해봅니다. 어제의 파일 전체를 안전한 장소에 보존해두고 오늘의 파일과 비교하는 방법이 있습니다.
이것보다 더 좋은 방법은 어제의 파일을 일방향 해시함수를 거쳐 그 결과인 해시값을 저장해두고, 오늘의 파일에서 해시값을 구해 이를 비교하는 것입니다.
일방향 함수의 예를 한 가지 만들어보겠습니다. 입력되는 숫자를 23으로 나누는 메커니즘을 생각해봅니다. 그리고 그 몫을 소수로 표시했을 때 소숫점 이하 7자리부터 10자리까지 4자리 숫자에 주목합니다.
345689 를 23으로 나누면 몫은 15029.95652173913043…… 이 됩니다. 여기서 소숫점 이하 7자리부터 10자리의 수는 7391이 되고 이 4자리 수가 입력 345689에 대 한 출력이 됩니다. 예로 들은 이 함수는 일방향 함수가 분명합니다. 왜냐하면 7391로부터 345689를 계산하고, 6521로부터 87967654를 역으로 계산해낼 함수 를 찾을 수 없기 때문입니다.
일방향 해시 함수(one-way hash function)에는 입력과 출력이 각각 1개씩 있습니다.
- 입력 = 메시지(message)
- 출력 = 해시 값(hash value)
해시함수에 입력되는 메시지는 인간이 읽을 수 있는 문서일 필요는 없습니다. 화상 파일이라도, 음성 파일이라도 상관없습니다. 일방향 해시 함수는 메시지가 실제로 무엇을 나타내고 있는지를 알 필요는 없습니다. 일방향 해시 함수는 어떤 메시지든지 단지 비트열로서 취급하며, 그 비트 열을 기초로 해시 값을 계산합니다.
해시 값의 길이는 메시지의 길이와는 관계가 없습니다. 메시지가 1비트라도, 1메가바이트라도, 100기가 바이트라도 일방향 해시 함수는 고정된 길이의 해시 값을 출력으로 배출합다. 예를 들면 SHA-1이라는 일방향 해시 함수에서는 해시 값은 항상 160비트(20바이트)입니다.
일방향 해시 함수의 성질
- 임의의 길이 메시지로부터 고정 길이의 해시 값을 계산한다
- 해시 값을 고속으로 계산할 수 있다
- 메시지가 다르면 해시 값도 다르다
- 일방향성을 갖는다
충돌
2개의 다른 메시지가 같은 해시 값을 갖는 것을 충돌collisio이라고 합니다. 일방향 해시 함수를 무결성 확인에 사용하기 위해서는 충돌이 발견되서는 안됩니다.
위의 예제에서 우리가 입력으로 사용한 값은 A = 345689 이었고 출력으로 얻은 출력 값은 7391 이었습니다. 이제 동일한 일방향 함수에 새로운 입력으로 B = 232.8395049993 을 넣어보면 몫은 10.1234567391 가 된다. 따라서 출력되는 값은 7391이 됩니다. 이것을 보면 두 개의 서로 다른 입력 A와 B에 대해서 동일한 출력 값을 배출한다는 것을 알 수 있습니다.
충돌을 발견하는 것이 어려운 성질을 가리켜 충 돌 내성(collision resistance)라고 부릅니다. 암호 기술에서 사용되는 일방향 해시 함수는 충돌 내성을 가질 필요가 있습니다.
해시 함수관련 용어
아래는 동의어를 나타냅니다.
- 일방향 해시 함수
- 메시지 다이제스트 함수 Message Digest Function
- 메시지 요약 함수
- 암호적 해시 함수
- 입력 메시지
- 프리 이미지 pre image
- 출력 해시 값
- 메시지 다이제스트 Message Digest
- 핑거프린트 Fingerprint
- 무결성
- 완전성
- 보전성