본문내용
1. 암호학 해시함수와 암호시스템
1.1. 해시함수란?
해시함수란 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 해시 함수에 의해 얻어지는 값은 해시 값, 해시 코드, 해시 체크섬 또는 간단하게 해시라고 한다. 암호학적 해시 함수는 현대 암호학에서 중요한 역할을 수행하고 있는데, 무결성, 메시지 인증 등에 사용되고 있다. 비 암호학적 컴퓨터 응용 분야에 사용되고 있는 일반 해시 함수와 비교할 때 두 경우 모두 큰 정의역에서 작은 치역으로의 함수라는 점에서 유사하다. 해시 함수는 임의의 길이 메시지를 입력하여 고정된 길이의 해시 값(해시 코드)을 출력한다.
1.2. 해시함수의 특징
해시함수의 특징은 다음과 같다.
첫째, 해시함수는 압축성과 계산의 용이성을 만족해야 한다. 해시함수 h는 임의 길이의 입력 x를 고정된 비트 길이를 갖는 출력 값 h(x)에 대응시키며, 함수 h와 입력 값 x에 대해 h(x)를 계산하기 쉽다""이다.
둘째, 해시함수 h가 가져야 할 기본 성질은 역상 저항성, 두 번째 역상 저항성, 충돌 저항성이다. 역상 저항성은 주어진 임의의 출력 값 y에 대해 y=h(x)를 만족하는 입력 값 x를 찾는 것이 계산적으로 불가능한 성질이다. 두 번째 역상 저항성은 주어진 입력 값 x에 대해 h(x)=h(x'), x ≠ x'를 만족하는 다른 입력값 x'를 찾는 것이 계산적으로 불가능한 성질이다. 충돌 저항성은 h(x)=h(x')을 만족하는 임의의 두 입력값 x, x'을 찾는 것이 계산적으로 불가능한 성질이다. 이러한 성질들은 서로 다른 입력 값에서 동일한 출력 값이 나오면 안 된다는 것을 의미한다""이다.
셋째, 해시함수의 정의에는 일방향 해시함수와 충돌 저항 해시함수가 있다. 일방향 해시함수는 압축성, 역상 저항성, 두 번째 역상 저항성을 만족하는 해시함수이며, 충돌 저항 해시함수는 압축성, 두 번째 역상 저항성, 충돌 저항성을 만족하는 해시함수이다""이다.
넷째, 메시지 인증코드 알고리즘은 비밀키 k를 파라미터로 갖는 함수 h_k의 집합으로, 계산의 용이성, 압축성, 계산의 저항성 등의 성질을 만족한다""이다.
1.3. 해시함수의 정의
해시함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 해시 함수에 의해 얻어지는 값은 해시 값, 해시 코드, 해시 체크섬 또는 간단하게 해시라고 한다.
해시함수의 정의는 다음과 같다. 첫째, 압축성을 만족해야 한다. 함수 h는 임의 길이의 입력 x를 고정된 비트 길이를 갖는 출력 값 h(x)에 대응시킨다. 둘째, 계산의 용이성을 만족해야 한다. 함수 h와 입력 값 x에 대해, h(x)는 계산하기 쉽다.
해시함수 h가 가져야할 기본 성질로는 역상 저항성, 두 번째 역상 저항성, 충돌 저항성이 있다. 역상 저항성은 주어진 임의의 출력 값 y에 대해, y=h(x)를 만족하는 입력 값 x를 찾는 것이 계산적으로 불가능한 것을 의미한다. 두 번째 역상 저항성은 주어진 입력 값 x에 대해 h(x)=h(x'), x != x'를 만족하는 다른 입력값 x'를 찾는 것이 계산적으로 불가능한 것을 의미한다. 충돌 저항성은 h(x)=h(x')을 만족하는 임의의 두 입력값 x, x'을 찾는 것이 계산적으로 불가능한 것을 의미한다.
해시함수는 일방향 해시 함수와 충돌 저항 해시함수로 나뉜다. 일방향 해시 함수는 역상 저항성과 두 번째 역상 저항성을 갖는 해시 함수이다. 충돌 저항 해시함수는 두 번째 역상 저항성과 충돌 저항성을 갖는 해시 함수이다.
1.4. 메시지 인증코드 알고리즘
메시지 인증코드 알고리즘은 비밀키 k를 파라미터로 갖는 함수 h_k의 집합이며, 다음과 같은 성질을 만족해야 한다""
첫째, 계산의 용이성이다. 주어진 키 k와 입력 x에 대해 h_k(x)를 계산하기 쉬워야 한다""
둘째, 압축성이다. 함수 h_k는 임의 길이의 입력 x에 대해 고정된 n비트의 값을 출력해야 한다""
셋째, 계산의 저항성이다. 주어진 입력-출력 쌍 (x_i, h_k(x_i))에 대해 h(x)=h(x_i), x != x_i를 만족하는 다른 입력-출력 쌍 (x, h_k(x))를 찾는 것이 계산적으로 불가능해야 한다""
이러한 메시지 인증코드 알고리즘은 통신 중의 오류나 수정, 그리고 '거짓 행세'를 검출하는 데 사용될 수 있다""
1.5. 해시함수에 대한 공격
해시함수에 대한 공격은 크게 세 가지로 나눌 수 있다.
첫째, 일방향 해시함수에 대한 공격이다. 일방향 해시함수는 입력값 x에 대해 해시값 y=h(x)를 계산하기는 쉽지만, 주어진 해시값 y에 대해 역상 x를 찾거나, 주어진 쌍 (x,h(x))에 대해 h(x')=h(x)를 만족하는 x'를 찾는 것이 계산적으로 불가능하도록 구현된다. 하지만 이런 일방향 해시함수에 대해서도 다양한 공격 방식이 시도되는데, 대표적인 공격으로는 생일 공격과 무차별 대입 공격이 있다. 생일 공격은 생일 역설을 이용하여 h(x)=h(x')인 쌍을 찾아내는 공격이고, 무차별 대입 공격은 가능한 모든 입력값을 시도해서 해시값을 찾아내는 방식이다. 이런 공격들에 대해서는 충분한 길이의 해시값을 사용하거나 솔트 값을 추가하는 등의 방어책이 필요하다.
둘째, 충돌 저항 해시함수에 대한 공격이다. 충돌 저항 해시함수는 서로 다른 입력값 x, x'에 대해 h(x)=h(x')를 만족하는 것이 계산적으로 불가능하도록 구현된다. 하지만 이런 충돌 저항 해시함수에 대해서도 생일 공격을 활용하여 충돌을 찾아내는 방식이 있다. 이를 방어하기 위해서는 더 긴 해시값을 사용하거나 해시함수의 구조를 복잡하게 만드는 방법이 있다.
셋째, 메시지 인증코드에 대한 공격이다. 메시지 인증코드는 비밀키 k를 파라미터로 갖는 해시함수 h_k를 사용하여 메시지에 대한 인증 정보를 생성한다. 이때 공격자는 비밀키에 대한 어떠한 정보도 없이, 주어진 입력-출력 쌍 (x_i,h_k(x_i))에 대해 h_k(x')=h_k(x)이면서 x != x'인 새로운 입력-출력 쌍 (x,h_k(x))을 찾는 것이 목표이다. 이를 방어하기 위해서는 비밀키의 길이를 충분히 길게 설정하고, 키 관리를 철저히 하는 등의 방법이 필요하다.
종합하면, 해시함수에 대한 다양한 공격 방식이 존재하지만, 충분한 길이의 해시값 사용, 솔트 값 추가, 복잡한 구조의 해시함수 설계, 철저한 키 관리 등을 통해 이를 효과적으로 방어할 수 있다. 최근에는 SHA-3와 같은 신뢰성 높은 해시함수가 개발되어 사용되고 있다.
1.6. 해시함수의 적용 분야
1.6.1. 자료구조 분야
자료구조 분야에서 해시함수는 중요한 역할을 담당한다. 해시함수는 임의의 길이의 데이터를 고정된 길이의 데이터로...
