암호 알고리즘 및 프로토콜의 이해

(주)퓨쳐시스템 암호체계센터

차례

서론
1. 암호의 종류 : 대칭키(비밀키) 암호, 비대칭키(공개키) 암호
고전 암호 : 대입(Substitution) 암호, 치환(Permutation/Transposition) 암호
비밀키 암호
1. 블럭 암호
  - 운영 모드
  - 패딩
2. 스트림 암호
해쉬 함수
MAC 알고리즘
공개키 암호
서명
키 전송/교환 알고리즘

1. 서론

통신을 하는 두 사람이 서로의 통신 내용을 비밀로 하고 싶어하는 것은 매우 자연스러운 현상이다. 이를위해 통신내용을 암호화(Encryption)하여 전달하는 것은 매우 오래전부터 사용되어왔다. 암호의 시작은 기원전 2000년 이전으로 거슬러 올라간다고 추정하기도 한다. 예를들어 다음과 같이 영문 알파벳에서 각 글자를 3글자씩 옆으로 옮겨서 만드는 암호는 로마시대의 Julius Caeser에 의해 사용되었다는 주장이 있고, Caesar 암호라고 블린다.

FUTURE SYSTEM ---- 암호화 ----> IXWXUH VBVWHP

이와같이 암호화는 평문(Plaintext)을 사용자의 암호화키(Encryption Key: 잠금 열쇠)를 사용하여 암호문(Ciphertext)으로 변환하는 과정이다. 암호문으로부터 복호화키(Decryption Key: 풀림 열쇠)를 사용하여 원래의 평문으로 변환하는 과정은 복호화(Decryption)라고 한다. 그러나 키를 사용하지 않고 단지 문자를 다른 기호로 변환하는 것은 변환 규칙을 모르면 변환된 데이타를 읽을 수 없을지라도 암호문이라고는 부르지 않는다 (예: 모오스 부호, 깃발 신호, ASCII 코드 등).

암호를 사용하는 목적으로는 기본적으로 통신하는 당사자 이외의 다른 사람에게 메시지를 알려주지 않기 위한 것이지만 그밖에 다음과 같은 목적으로 암호를 사용한다.

기밀성(Confidentiality) : 암호를 사용하는 1 차적인 목적이다. 허가된 사람 이외에는 그 내용을 알아볼 수 없도록 한다.
무결성(Integrity) : 외부의 요인으로 인해 데이타가 변조(변경, 삽입, 삭제 등) 되었는지를 알 수 있도록 한다.
인증(Authentication) : 통신하고 있는 상대방이 실제로 맞는지를 확인하고, 서로에게 전송한 데이타가 위조되지 않았음을 확인할 수 있도록 한다.
부인방지(Non-repudation) : 이전의 통신내용을 보낸적이 없다고 속일 수 없도록 한다. 즉, 데이타를 받은 사람은 나중이라도 보낸 사람이 실제로 데이타를 보냈다는 것을 증명할 수 있도록 한다.

이외에 세부적으로 다양한 보안 서비스/프로토콜을 가능하게 만드는 것이 암호라고 볼 수 있다.

1.1 암호의 종류

일반적으로 암호화를 하기 위해서는 사용자의 암호화키가 필요하다 (Caeser 암호에 있어서는 ``3"을 암호화키라고 볼 수 있다). 복호화를 하기 위해서는 암호문으로 변환하는 방법(키 만큼 알파벳을 옆으로 옮김)을 알아야 하고 또한 복호화키가 필요하다. Caeser 암호의 경우는 암호화키와 복호화키가 서로 같다. 즉, 같은 키를 사용하여 반대방향으로 알파벳을 옮기면 원래의 평문을 얻을 수가 있다. 이와같이 암호화키와 복호화키가 서로 같은 암호를 대칭키 암호(Symmetric Cryptosystem)라고 한다. 반면에 암호화키와 복호화키가 서로 다른 암호를 비대칭키 암호(Asymmetric Cryptosystem)라고 한다.

그림 1 : 암호시스템의 종류

대칭키 암호를 사용하여 통신을 하고자 할때는 그림 1 과 같이 송신자와 수신자가 서로 공유하고 있는 키가 필요하다. 이 키는 암/복호화에 모두 사용되므로 제 삼자에게 노출되어서는 안되는 비밀키이다. 이런의미에서 대칭키 암호를 비밀키 암호라고도 부른다. 비밀키 암호는 어떤 두사람 사이에도 하나의 비밀키가 필요하므로 그림 2 와 같이 n명의 구성원에서 1명이 증가하면 n개의 키가 필요하게 된다.

그림 2 : 비밀키 암호에 구성원이 증가하는 경우

비밀키 암호를 사용하기 위해서는 무엇보다도 통신하고자 하는 두 사람이 서로만 알고있는 비밀키를 공유하는 지에 대한 방법이 있어야 한다. 구성원이 많을수록 비밀키의 공유가 어려워질 수 밖에 없다.

비대칭키 암호의 가장 큰 특징은 암복호화에 사용되는 키가 다를뿐만아니라 이중 암호화키는 누구에게나 공개하고 복호화키는 자신만이 간직하는 비밀키로 사용하는 것이다. 이때 공개된 암호화키로부터 복호화키를 알아낼 수는 없어야 한다. 그러면 사용자 A가 사용자 B에게 메세지를 전송하고자 할때, 공개된 A의 암호화키를 이용하여 메세지를 암호화하여 A에게 전송할 수가 있고, A는 자신만이 알고있는 복호화키를 사용하여 암호문을 복호화할 수가 있다. 이런의미에서 비대칭키 암호를 공개키 암호라고도 부른다.

따라서 비밀키 암호화 달리 공개키 암호는 각 사용자마다 1쌍(공개키-비밀키)의 키만 가지고 있으므로 1명이 증가하면 2개의 키만 추가로 필요하다. 구성원의 수가 많을수록 비밀키 암호의 키의 개수가 공개키 암호의 키의 개수보다 훨씬 많이 필요하다.

인원수	비밀키 암호	공개키 암호
n	n(n-1)/2	2n
10	45	20
10000	49995000	20000

표 1 : 필요한 키의 개수

비밀키 암호인 경우 암호화/복호화를 같은 키를 비밀로 하면 되므로 암호화 방법으로 사용할 수 있는 방법들이 매우 다양하다. 그러나 공개키 암호인 경우 암호화키와 복호화키가 서로 다르고 암호화키는 공개되므로 암호화키로부터 복호화키를 알아낼 수 없도록 해야하는 제약이 있다. 비밀키 암호는 그 기원을 알 수 없을 정도로 오래되었지만 공개키 암호는 최근(1970년대)에 수학적으로 어려운 문제를 기반하여 고안되었다. 대표적으로 합성수의 소인수분해 문제를 이용한 RSA를 예로 들 수 있다. 일반적으로 비밀키 암호의 암복호화 속도는 매우 빠르지만, 공개키 암호는 어려운 수학연산을 이용해야 하므로 암복호화 속도가 매우 느리다.

2. 고전 암호

고전적으로 사용된 암호는 모두 비밀키 암호에 속한다. 즉, 통신을 원하는 양쪽은 미리 암호문을 생성하는 방법과 다시 암호문으로부터 평문을 얻는 방법을 알고있어야하고 이때 필요한 비밀키를 서로 공유하고 있다고 가정한다. 고전적인 암호로는 크게 대입(Substitution) 암호, 치환(Permutation) 암호등이 있다. 두가지 방법을 혼합하여 분석이 어려운 암호를 생성하기도 한다.

대입 암호 : 각각의 글자를 다른 글자에 대응시키는 방법.
서론에서 예를 든 Caesar 암호는 대입 암호의 특수한 예로 볼 수 있다. Caesar 암호는 알파벳에서 오른쪽으로 3글자 옆에 있는 글자에 대응시키는 방법이고, 그 밖에 다양한 방법으로 각 글자를 다른 글자에 대응시킬 수 있다.

평문 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

암호문 Q A Z W S X E D C R F V T G B Y H N U J M I K O L P

표 2 : 대입 암호의 예
표 2 의 방법으로 다음과 같이 암호화 할 수 있다.

FUTURE SYSTEM ---- 암호화 ----> XMJMNS ULUJST
그러나 일정길이 이상의 암호문을 알고 있을때, 각각의 글자가 쓰인 개수를 통계적으로 분석하면 많은 정보를 얻을 수가 있다. 예를 들면 영문에서 가장 많이 쓰이는 글자는 `E', `T'이므로 암호문에서 가장 많이 쓰인 글자를 `E' 혹은 `T'로 간주하는 것은 매우 자연스럽다. 또한 `TH', `THE'등과 같이 두글자 세글자중 빈도수가 높은 것들을 이용하면 암호문에서 많은 글자에 대한 정보를 알 수 있다.
치환 암호 : 글자를 바꾸지 않고 놓인 위치를 변경하는 방법. 교환(Transposition) 암호라고도 불린다.
이 방법은 문장을 일정 단위의 블럭으로 나누어서 배열한 뒤에 평문을 정해진 방법에 따라서 읽어서 암호문을 얻는다. 이런 종류의 암호는 평문을 읽는 방법에 따라 매우 다양한 방법으로 암호문을 생성할 수가 있다.
예를 들면 블럭의 크기를 6이라고 하고, 암호화에 필요한 키를 'HOTDOG'라고 하자 (HOTDOG는 알파벳순서로 346152에 대응된다).
```
                    HOTDOG
                    346152
                    ------
                    FUTURE      --- 암호화 --->     UEFURT
                    SYSTEM                          TMSYES
```
위의 방법은 평문의 각 블럭마다 키의 순서대로 읽는 방법으로써 암호문 'UEFURT TMSYES'를 얻는다.
또다른 방법으로는 배열된 평문을 블럭 단위로 읽지 않고 열(column) 단위로 읽는데 순서는 키에서 정의한 순서대로 읽는 방법도 있다. 그러면 암호문 'UTEMFS UYRETS'를 얻는다.

평문	`A B C D E F G H I J K L M N O P Q R S T U V W X Y Z`
암호문	`Q A Z W S X E D C R F V T G B Y H N U J M I K O L P`

3. 비밀키 암호

비밀키 암호 알고리즘은 대칭키 암호라고도 불리는데, 양 당사자가 동일한 비밀키를 공유하고 있음을 가정하고 비밀키를 이용하여 암복호화를 수행한다(그림 3). 비밀키 암호 알고리즘은 컴퓨터 구현시 속도가 매우 빠르다는 등의 장점이 있으나, 최근의 internet 환경에서 키교환, 키관리 등에서 많은 문제가 있다. 이에 공개키(비대칭키) 암호를 사용하여 키교환, 키관리 및 디지털 서명 등을 하고, 이 때 교환된 키를 이용하여 대칭키 암복호화 알고리즘으로 실질적인 데이타의 암복호화를 수행한다.

대표적인 대칭키 암복호화 알고리즘으로는 블록암호인 DES가 있으며 전세계적으로 널리 사용되었으나 짧은 키 길이 등으로 인한 안전성의 문제로 최근 AES 블록암호 알고리즘이 선정되어 표준화 절차가 진행중이다.

그림 3 : 비밀키 암호의 암복호화

비밀키 암호는 크게 나누어서 다음과 같이 블럭 암호화 스트림 암호로 분류한다.

블럭 암호: 평문을 일정한 단위로 나누어서 각 단위마다 암호화 과정을 수행하여 블럭 단위로 암호문을 얻는 방법이다.
스트림 암호: 평문과 같은 길이의 키 스트림을 생성하여 평문과 키를 비트단위로 합하여(bitwise exclusive OR) 암호문을 얻는 방법이다.

3.1 블럭 암호

블록암호 알고리즘은 비밀키를 이용하여 고정된 크기의 입력블록을 고정된 크기의 출력블록으로 변형하는 암호 알고리즘에 의해 암복호화 과정을 수행하며, 이 때 출력블록의 각 비트는 입력블록과 키의 모든 비트에 영향을 받는다. 현대 블록암호 알고리즘의 대부분은 대치와 치환의 반복에 의하여 강력한 암호 알고리즘이 설계될 수 있다는 Shannon의 이론에 근거하여 설계되었다.

블록암호 알고리즘의 구조는 Feistel Network과 SPN (Substitution-Permutation Network)로 나뉜다.
Feistel 구조는 입력을 좌우 블록으로 분할하여 한 블록을 라운드 함수에 적용시킨 후의 출력 값을 다른 블록에 적용하는 과정을 좌우블록에 대해 반복적으로 시행하는 방식으로, 라운드 키가 역순으로 작용한다는 점을 제외하면 암/복호화 과정이 동일하고 라운드 함수에 대한 제약 조건이 없어 DES를 비롯한 대부분의 블록암호에 채택되어 사용되고 있다. Feistel 구조를 채택한 블록암호 알고리즘으로는 DES, LOKI, CAST, Blowfish, MISTY, RC5, CAST256, E2, Twofish, RC6, Mars 등이 있다.
최근에는 입력 블록을 좌우로 나누지 않고 입력 전체 블록에 대해 한번에 변화시키는 SPN 구조가 많이 연구되고 있는데, 이는 라운드 함수가 역변환이 되어야 한다는 등의 제약이 있지만 더 많은 병렬성(parallelism)을 제공하기 때문에 암복호화 알고리즘의 고속화가 요구되고 최근의 컴퓨터 프로세스(CPU)가 더 많은 병렬성을 지원하는 등의 현 추세에 부응하는 방식이라 할 수 있다. 이 방식을 사용하는 블록암호 알고리즘은 SAFER, IDEA, SHARK, Square, CRYPTON, Rijndael, SAFER+, Serpent 등이 있다.

블록암호 알고리즘을 특징하는 요소로는 다음과 같은 것이 있으며, 이러한 요소에 의해 전체 블록암호의 안전성이 결정된다.

Block Size : 입출력 블록의 비트수로, 일반적으로 더 클수록 더 안전하다고 보지만 암/복호화 과정에서 시간이 더 걸린다. 주로 64비트가 널리 쓰였지만, 최근에는 128비트를 채택하고 있다.
Key Size : 비밀키의 비트수로, 일반적으로 더 클수록 이 역시 라은드 키를 생성할 때 시간이 더 걸린다. DES는 56비트를 사용하였는데 작은 키의 크기로 인하여 안전성에 큰 문제가 되었고, 최근에는 128비트나 그 이상을 주로 사용한다.
Round-key Generation : 비밀키로부터 각 라운드에서 사용할 키를 생성하는 과정으로, 유사시 라운드 키가 누출되더라도 비밀키는 안전해야 한다.
Round Function : 암복호화를 수행하는 핵심함수로 다양한 암호분석을 거쳐 안전하게 만들어져야 한다.
Number of rounds : 한 번의 암복호화를 위해 반복하는 Round Function의 횟수로, 많을수로 더 안전하다고 보지만 암/복호화 과정에서 시간이 더 걸린다. 근본적으로 한 번의 Round Function으로 충분한 안전성을 확보할 수는 없기 때문에 Round Function에 대한 다양한 암호분석을 통해 충분한 안전성을 얻을 수 있도록 라운드 횟수를 결정한다.

가장 널리 알려진 암호인 DES도 블럭 암호에 속하는데, DES는 1970년대 초기에 IBM에서 개발된 LUCIFER를 바탕으로 수정보완된 것으로 미국의 연방표준(Federal Information Processing Standard:FIPS) FIPS-46(revised FIPS46-1, FIPS46-2)으로 채택되었고, 표준으로 채택된 뒤에 매 5년마다 재 사용을 승인을 받아서 사용되어 왔는데, 1998년이후로는 안전성에 문제가 있어서 더 이상 승인을 받지 못했다.
DES는 짧은 키 길이(56 비트)를 사용하므로 현재의 컴퓨터 성능으로 빠르게 비밀키를 찾아낼 수 있다. 그림 4 는 1초에 90,000,000,000 개의 키를 테스트하여 약 5일안에 DES의 비밀키를 찾아낼 수 있는 컴퓨터이다 (http://www.cryptography.com/des/index.html 참조). 실제로 이것을 이용하여 1998년 RSA DES Challenge II의 암호문을 56시간 만에 해독하였고, 이후 1999년1월에는 Distributed.net과 함께 1초에 약 245,000,000,000 개의 키를 테스트 하여 RSA DES Challenge III를 22 시간 15분 만에 암호문을 해독하였다.

그림 4 : DES Cracker

DES의 안전성 문제가 부각되자, 미 상무성이 주관이 되어 1997년부터 DES를 대체할 새로운 블럭 암호 AES(Advanced Encryption Standard)의 공모를 시작하였다. 1998년 1차 심사대상으로 15개의 후보를 선정하였는데, 이중 아시아권에서는 (주)퓨쳐시스템의 CRYPTON과 일본 NTT의 E2 알고리즘이 후보에 올랐다. 15개의 후보를 1999년 2차 심사대상으로 5개 알고리즘 -- RIJNDAEL, RC6, MARS, SERPENT, TWOFISH -- 으로 압축하였고, 이후 다시 1년여 동안의 심사를 거쳐서 2000년 10월 RIJNDAEL을 최종 AES 알고리즘으로 선정하여, FIPS로 제정 절차를 밟고 있는 중이다.

그밖에 현재 많은 응용들에서 사용되고 있는 블럭 암호로는 DES의 짧은 키 길이를 극복하기 위하여 DES를 세번 반복하여 사용하는 3DES가 있고, RSA의 Rivest가 개발한 RC5, 인터넷 표준등에서 많이 사용되는 IDEA 등이 있다. 히 SEED는 정보보호센터(KISA)에서 개발된 국내 표준 알고리즘이다. 다음의 표 3 는 각 알고리즘의 블럭의 크기와 키의 길이를 나타낸것이다.

알고리즘	블럭의 크기(bit)	키의 길이(bit)	암/복호화 속도(Mbps)
DES	64	56	73.8/74.1
3DES	64	112, 168	25.1/25.2
IDEA	64	128	57.6/57.2
RIJNDAEL	128	128, 192, 256	130.0/135.0
SEED	128	128	88.2/88.8
CRYPTON	128	0 - 256	130.9/130/0

표 3 : 블럭 암호 (PIII 450MHz, Win98, MSVC++6.0)

3.1.1 운영 모드

블록암호 알고리즘은 64 또는 128비트인 블록 단위로 암복호화를 수행하므로, 일반적인 데이타를 암복호화하는 경우 복수개의 블록을 처리하여야 한다. 이 때 각 블록들간의 연관성 또는 의존성을 주는 방식을 Mode라고 한다. 주로 사용되는 mode는 ECB, CBC, CFB, OFB, Counter mode 등이 있으며, 그 장단점을 고려하여 적절히 사용하여야 한다.

ECB(Electronic Code Book) 모드는 가장 단순한 방식으로 각 블록을 독립적으로 암복호화한다. 이 방식은 동일한 평문블록은 동일한 암호문을 생성하는데 이는 안전성에 있어서 이런 점은 바람직하지 않다. 이러한 이유로 ECB 모드는 일반적으로 잘 사용하지는 않는다.

그림 5 : ECB 모드

CBC(Cipher Block Chining) 모드는 이전 블록의 암호문과 현재의 평문블록을 XOR(exclusive or)한 후 그 결과를 암호화하여 암호문을 생성한다. 맨 처음 블록은 초기값 IV와 XOR하여 사용하며, 이때 사용하는 IV는 비밀일 필요는 없지만 송수신자가 같은 IV를 사용해야만 올바른 결과를 얻을 수 있다. 이 방식은 모든 평문블록이 마지막 암호문블록에 영향을 미치기 때문에 MAC 값을 생성하는 경우에 유용하게 사용할 수 있다.

그림 6 : CBC 모드

CFB(Cipher FeedBack) 모드는 초기치를 암호화한 값과 평문블럭을 XOR 하여 암호문블럭을 생성하고 그 암호문을 초기치로 하여 다시 암호화한 값과 평문블록을 XOR하여 암호문블록을 반복하여 생성하는 방식이다. 암호화에서는 특정 입력이 이후로 영향을 미치지만, 복호화에서는 특정 암호문의 오류가 계속적으로 이후에 영향을 미치지는 않는다는 특징이 있다.

OFB(Output FeedBack) 모드는 초기치 IV를 암호화하고 그 값을 다시 암호화하는 과정을 반복함으로써 생성된 수열과 평문 수열을 XOR하여 암호문을 생성하는 방식으로, 주로 블록암호 시스템을 스트림암호 시스템처럼 사용하고자 할 때 이용된다. 이 방식에서 암호문의 오류는 복호화 과정에서 대응되는 한 블록에만 영향을 미치므로, 영상이나 음성과 같은 digitized analog신호에 많이 사용된다. 복호화 할 때 IV가 다르면 전혀 다른 평문이 되므로 반드시 초기값을 같게 해야 한다.

Counter 모드는 초기치 IV와 IV+1, IV+2, ...을 암호화하여 생성된 수열과 평문수열을 XOR하여 암호문을 생성하는 방식이다. 병렬성이 뛰어나고, 비밀키와 IV가 주어지면 미리 계산할 수 있어 평문이 주어지면 바로 암호문을 만들 수 있다는 장점이 있지만, 동일한 비밀키와 IV를 반복하여 사용할 경우 안전성에 문제가 생긴다는 약점이 있다.

3.1.2 패딩

블럭 암호는 평문을 블럭 단위로 암호화해야 하므로 평문이 블럭의 크기의 배수가 아닐때는 이것을 맞추어 주는 방법이 필요하다. OFB mode의 경우는 스트림암호처럼 작동하기 때문에 별도의 padding이 필요하지 않지만, ECB와 CBC mode인 경우는 padding 과정이 필수적이다. 주로 사용되는 padding 방식으로는 PKCS Padding, OneAndZeroes padding, CTS padding 등이 있다.

PKCS Padding은 padding되는 바이트 수를 바이트 단위로 추가하여 필요한 크기의 블록을 만드는 방식으로 입력데이터가 블록크기의 배수일 때는 한 블록만큼 암호문이 증가한다는 특성이 있다.

OneAndZeroes는 비트 단위로 맨 처음에 1을 추가하고 이후에 필요한만큼의 0을 추가하여 원하는 만큼의 padding을 추가하는 방식으로, 거의 모든 해쉬알고리즘에서 사용하는 padding 방식이다.

CTS padidng은 평문의 마지막 두 블록 적절히 처리하여 암호문의 크기가 평문의 크기보다 증가하지 않도록 하는 방식으로 입력데이터가 1블록 이하이면 적용할 수 없다는 단점이 있지만, 하드드라이브 상에서의 파일 암호화와 같이 암호문의 크기가 평문보다 크기 않아야 하는 응용에서 CBC 모드 등을 사용할 수 있도록 한다.

위의 padding 방식 이외에도, 상위응용에서 적당한 처리를 통해 입력된 평문이 항상 블록크기의 배수라고 가정하는 NoPadding 방식이나, 상위응용에서 평문의 크기에 대한 정보를 가지고 있는 응용이나 MAC 등과 같이 복호화 과정이 불필요한 응용에 적용할 수 있는 방식으로 필요한 길이의 0을 추가하는 ZeroPadding 등이 있다.

3.2 스트림 암호

스트림 암호는 비밀키 암호의 하나로 블럭의 크기를 1로 하여 블럭마다 각각 다른 키를 사용하여 암호문을 생성하는 것으로 볼 수 있다. 그러므로 스트림 암호를 사용하기 위해서는 평문(P1, P2, ... , Pn)과 같은 크기의 키 스트림(K1, K2, ... , Kn)이 필요하다 (그림 7 참조).

그림 7 : Stream 암호

CBC 모드의 블럭 암호는 전송도중이나 암/복호화 과정중에서 오류가 발생하면 오류가 발생한 블럭뿐만아니라 다른 블럭까지 오류가 확산되어 암호문을 올바르게 복호화할 수 없게 된다. 이에 비해 스트림 암호는 각 단위마다 각각 다른 비밀키로 암호화를 수행하게 되므로 오류가 일어난 곳 이외에 다른 곳은 영향을 미치지 않는다. 또한 블럭의 크기가 1 이고 이전 블럭의 결과와 상관없이 암/복호화가 가능하므로 블럭 암호에 비해 메모리에 저장할 필요가 없고 고속의 암복호화가 가능하다. 키 스트림을 한번만 사용하는 것을 One-Time Pad라고 부르고, 이론적으로 One-Time Pad를 사용한 암호는 해독할 수 없다.

일반적으로 사용되는 스트림 암호는 블럭의 단위를 1 비트로 하여 평문과 같은 길이의 키 스트림을 XOR하여 암호문을 생성한다. 암/복호화에 사용될 키 스트림은 사용자 사이에 미리 교환되는 경우도 있으나, 일반적으로 사용자의 비밀키로부터 키 스트림 생성함수를 이용하여 필요한 길이만큼을 생성한다. 키 스트림 생성함수를 예측 가능한 함수를 사용하면 스트림 암호는 쉽게 해독이 된다. 예를 들어 키 스트림 생성함수로 n개의 단계를 가지는 Linear Feedback Shift Register를 사용할 때, 연속된 2n개의 키 스트림(즉, 연속된 2n개의 평문과 암호문의 쌍)을 알고 있으면 사용자의 비밀키를 알 수가 있다.

4. 해쉬함수

해쉬함수는 그림 8 과 같이 임의의 길이의 비트스트링을 고정된 길이의 출력값인 해쉬코드로 압축시키는 함수이다.

그림 8 : 해쉬 함수

해쉬함수가 만족해야하는 성질은 다음과 같다.

주어진 출력에 대하여 입력값을 구하는 것이 계산상 불가능하다 (일방향성).
주어진 입력에 대하여 같은 출력을 내는 또 다른 입력을 찾아내는 것이 계산상 불가능하다.
같은 출력을 내는 임의의 서로 다른 두 입력 메세지를 찾는 것이 계산상 불가능하다 (강한 충돌 회피성).

위와 같은 성질은 만족하는 해쉬함수는 데이터의 무결성, 인증, 부인 방지 등에서 응용되는 중요한 함수 중의 하나이다. 일례로 전자서명의 경우 몇 바이트에서 수 기가바이트에 이르는 다양한 크기의 메시지를 직접 전자서명 프로토콜에서 사용한다는 것은 문제가 있으므로, 메시지를 해쉬코드로 압축하고 이를 이용하여 전자서명값을 생성한다. 이 때 또다른 어떤 메시지가 동일한 해쉬코드를 생성한다면 위의 전자서명값은 또다른 메시지에 대한 서명도 되므로 큰 문제가 발생한다. 실제로 이러한 문제가 발생하지 않는 것은 해쉬함수가 강한 충돌회피성을 가지고 있으므로, 이론적으로 동일한 해쉬코드를 가지는 메시지가 무한히 존재함에도 불구하고 현실적으로 동일한 해쉬코드를 가지는 한 쌍의 메시지를 찾을 수는 없기 때문이다.

해쉬함수에는 블록암호 알고리즘과 같은 기존의 알고리즘들을 이용하여 구성할 수도 있으나 안전성과 효율성면에서 전용 해쉬 함수를 사용하는 것이 바람직하다.

Birthday 공격에 의하면 출력길이 n인 해쉬함수에 대해 2^n/2 정도의 연산이면 충돌쌍을 찾을 수 있다. 특히 128 비트 출력을 가지는 MD5의 충돌회피성에서 문제점이 있다는 것이 밝혀졌으므로 현재는 출력길이 160 비트 이상의 해쉬함수를 사용하도록 권장되고 있다.

대표적인 해쉬함수로는 1993년 NSA에 의해 설계된 SHA를 1995년에 수정/보완한 SHA-1이 있으며 미 연방 표준으로 채택되었다. SHA-1은 160 비트의 출력을 가지며 대부분의 공격에 강한 저항성을 갖는다. 그러나 AES의 키 길이가 128, 192, 256 비트를 지원함에 따라서 출력길이가 256, 384, 512 비트인 해쉬함수의 필요하게 되어 현재 SHA-256, SHA-384, SHA-512가 개발중에 있다.

HAS-160은 SHA-1과 MD5의 장점을 취하여 국내 표준 해쉬 함수로 개발된 것으로 SHA-1과 마찬가지로 160 비트의 출력길이를 갖는다. HAS-160은 국내 표준 서명 알고리즘인 KCDSA에 사용된다.

5. MAC 알고리즘

메시지 인증 코드(Message Authentication Code:MAC)는 데이타가 변조(수정, 삭제, 삽입 등)되었는지를 검증할 수 있도록 데이타에 덧붙이는 코드이다. 종이 문서의 경우 원래의 문서를 고치거나 삭제하거나 하는 경우 그 흔적이 남아서 변조되었는지를 확인하지만 디지털 데이타인 경우 일부의 비트가 변경되거나 혹은 임의의 데이타가 삽입되거나 일부가 삭제되어도 흔적이 남지 않는다. 이런 문제를 해결하기 위하여 원래의 데이타로만 생성할 수 있는 값을 데이타에 덧붙여서 확인하도록 하는 것이 MAC이다. 이때, 변조된 데이타에 대해서 MAC을 생성하여 MAC도 바꿔치기할 가능성이 있으므로 MAC의 생성과 검증은 반드시 비밀키를 사용하여야 한다.

그림 9 : MAC의 생성

전송 받은 데이타에 대해서 데이타의 무결성을 확인하기 위해서는 MAC을 생성할때 사용된 같은 비밀키를 이용하여 같은 방법으로 MAC을 생성하여 전송 받은 MAC값과 비교한다. 따라서 MAC을 사용하려면 통신하는 양쪽에서 MAC에 사용될 비밀키를 공유하고 있어야 한다.

MAC을 생성하는 함수로는 해쉬함수을 이용한 HMAC이 있다. HMAC은 해쉬함수의 입력에 사용자의 비밀키와 메시지를 동시에 포함하여 해쉬코드를 구하는 방법이다. MAC을 통해서 데이타의 무결성을 검증하기 위해서는 같은 MAC값을 갖는 서로다른 두개 이상의 메시지를 쉽게 구할 수 있으면 안되므로 해쉬함수의 일방향성이나 강한 충돌 회피성등이 필수적이다.

또다른 방법으로는 블럭 암호의 CBC 모드를 사용하는 CBC-MAC이 있다. 이 방법은 데이타를 선택된 블럭 암호로 CBC 모드를 사용하여 암호화한 뒤에 최종 암호문 블럭을 가지고 MAC 값을 구하는 방법이다. 이때의 MAC의 안전성은 사용된 블럭 암호의 안전성에 의존한다.

6. 공개키 암호

비밀키 암호를 사용하면 안전한 통신이 가능하다. 그러나 비밀키 암호를 사용하기 위한 전제조건은 통신 당사자들 만이 알고있는 비밀키를 공유하고 있거나 비밀키를 전달할 수 있는 안전한 경로가 있어야 한다는 것이다. 일반적으로 안전한 경로를 가지고 있기는 어려우므로 미리 공유된 비밀키가 없다면 비밀키 암호를 사용할 수가 없다.

이런 문제점을 해결하기 위하여 1970년대에 공개키 암호(Public Key Cryptosystem:PKC)의 개념이 등장하였다. 비밀키 암호에서는 두 사람이 하나의 비밀키를 공유하지만 공개키 암호에서는 각 사람마다 한쌍의 키를 가진다. 공개키 암호의 키중 하나 e는 암호화하는데 사용되며 모든 사람에게 공개되고, 나머지 하나 d는 복호화하는데 사용되며 사용자만이 비밀로 간직한다. 이때 d는 e로부터 유도하는 것이 현실적으로 불가능해야 하고 그림 10 과 같이 공개키 e를 사용하여 암호화한 것을 다시 비밀키 d를 사용하여 복호화하면 원래의 메시지를 얻을 수 있어야한다.

그림 10 : 공개키 암호의 암복호화

그러면 A가 평문 P를 B에게 전송할때는 그림 11 과 같이 B의 공개키를 사용하여 암호화하면 B는 암호문을 자신만의 비밀키로 복호화할 수 있다.

그림 11 : 공개키 암호의 전송

공개키 암호를 구성을 하기위해서는 다음과 같은 성질을 만족해야 한다.

암호문을 복호화하면 원래의 평문을 얻어야 한다: P=Decrypt(Encrypt(P)).
암호화 하는 함수 Encrypt는 누구나 계산할 수 있다.
비밀키(복호화키)를 모르면 Decrypt는 현실적으로 계산하기 어렵다.
비밀키(복호화키)를 알고 있으면 Decrypt를 쉽게 계산할 수 있다.
공개키(암호화키)로부터 비밀키(복호화키)를 구하는 것은 현실적으로 불가능하다.
사용자의 공개키와 사용자의 신분(Identity)를 연결할 수 있는 공개키 기반 구조(Public Key Infrastructure:PKI)가 필요하다.

위의 성질들을 만족하기 위하여 공개키 암호의 암/복호화 함수의 대부분은 수학적으로 어려운 문제들에 바탕을 두고 있다. 대표적으로 합성수의 인수 분해 문제를 바탕으로 한 것이 RSA 암호이다. RSA는 현재 가장 널리 사용되는 공개키 암호 알고리즘이다.

RSA의 기반이 되는 일반적인 합성수의 소인수분해로는 1999년 2월에는 140 자리의 RSA 합성수가 인수분해되었고, 1999년 8월 22일에는 155 자리(512 비트)의 RSA 합성수가 인수분해되었다. 여기에 사용된 컴퓨터(PC, workstation)는 수백대가 분산되어 처리되었으며 5개월이 넘는 시간이 걸렸다. 이것은 140 자리의 합성수를 인수분해하는 것보다 약 4배 정도 더 많은 시간(CPU time)이다. 비록 수 개월이 걸렸지만 512 비트의 합성수가 인수분해되었으므로 1024 비트 이상의 합성수를 사용할 것을 권장하고 있다.

그 밖의 공개키 암호로는 유한체의 이산 대수 문제를 바탕으로 한 것이 ElGamal 암호, 배낭 문제(Knapsack problem)를 바탕으로 한 Knapsack 암호, 부호 이론을 바탕으로 한 McEliece, 타원 곡선의 이산 대수 문제를 이용한 것이 타원 곡선 암호 등이 있다.

소인수분해 : RSA, Rabin encryption
유한체의 이산대수 : Elgamal, Diffie-Hellman, XTR
타원곡선의 이산대수 : Elliptic Curve Cryptosystem(ECC)
부호이론(Coding theory) : McEliece
배낭문제 : Knapsack 암호
기타 : NTRU (격자이론), Braid-group Cryptosystem (매듭이론)

참고 : Handbook of Applied Cryptography, Chapter 8 - Public-Key Encryption (36 pages), Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone, CRC Press, 1999.

7. 서명

서명(Digital signature)은 데이타의 위조를 막고, 부인 방지를 위한 방법으로 MAC과 같이 데이타의 변조도 검증 할수 있게 한다. 일반적으로 종이 서류의 동일인의 모든 서명이 같겠지만 디지털 데이타인 경우 모든 데이타에 대해서 같은 서명을 사용해서는 안되는 것은 너무도 당연하다. 디지털 서명은 각 데이타 마다 서로 다른 서명을 생성하고 본인 이외에 제삼자가 서명을 생성해서 안된다. 또한 MAC과는 달리 자신의 서명을 누구나 검증할 수 있어야 한다. 따라서 비밀키 방식의 MAC으로는 서명을 생성할 수가 없고 공개키 방식을 사용하게 된다. 공개키 방식을 사용하므로 공개키 암호와 마찬가지로 공개키 기반 구조(PKI)가 필요하다.

그림 12 : 서명의 생성

서명의 생성은 그림 12 와 같이 서명자의 비밀키(서명키)를 사용하여 서명을 생성한다. 이때 서명의 대상이 되는 데이타는 평문 전체에 대해서 하지 않고 평문을 해쉬한 해쉬값에 대해서 서명을 생성한다. 일반적으로 공개키 방식은 그 연산 시간이 매우 오래 걸릴뿐만아니라 모든 평문에 대해서 서명을 생성하게 되면 서명의 길이가 평문의 크기만큼 커지게 되므로 바람직하지 않다. 해쉬함수의 일방향성과 강한 충돌 회피성을 이용하면 해쉬값에 대해서만 서명을 생성하여도 평문 전체에 대해서 하는 것과 같은 효과를 얻을 수가 있다.

그림 13 : 서명의 검증

서명의 검증은 그림 13 과 같이 서명자의 공개키(검증키)를 사용하여 서명을 검증한다. 전송받은 데이타에서 서명과 메시지를 나누어 서명값으로는 서명자의 공개키를 이용하여 해쉬값을 구하고, 메시지로는 직접 해쉬함수를 사용하여 해쉬값을 구하여 두개의 해쉬값을 비교함으로써 메시지에 대한 서명을 검증할 수가 있다.

대표적인 서명함수로는 RSA를 이용하는 방법과 미 연방 표준으로 채택하고 있는 DSS(Digital Signature Standard)가 있다. RSA를 이용하는 방법은 RSA의 암호화 같은 방법이지만 사용자의 복호화키를 서명키로 사용하고 암호화키를 검증키로 사용한다. DSS는 해쉬함수로 반드시 SHA-1을 이용하도록 되어있다.

소인수분해 : RSA
유한체의 이산대수 : DSS(DSA)
타원곡선의 이산대수 : Elliptic Curve DSA(ECDSA)

참고 : Handbook of Applied Cryptography, Chapter 11 - Digital Signatures (64 pages), Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone, CRC Press, 1999.

8. 키 교환 알고리즘

공개키 암호는 기본 함수들은 수학적으로 어려운 문제들을 바탕으로 하고 있으므로 암복호화 연산의 속도는 비밀키 암호에 비해 매우 느릴뿐만아니라 많은 시스템 리소스를 차지하게된다. 따라서 공개키 암호를 사용하여 실제의 데이타를 암복호화하는 것은 현실적으로 어려운 일이다. 그러나 비밀키 암호를 사용하기 위해서는 미리 비밀키를 공유하거나 안전한 통신 채녈을 사용하여 세션키를 전송을 하는 것이 필요하다. 이러한 점에서 모든 데이타가 아닌 단지 비밀키 방식으로 암복호화를 할때 필요한 세션키만을 공개키 방식으로 서로 공유를 하는 것이 자연스러운 해결책이다.

통신의 방법에 따라서 e-mail과 같은 일방향성 통신이거나 혹은 서버와 클라이언트 환경등에서는 송신자나 클라이언트가 일방적으로 사용할 세션키를 설정하여 상대방에게 전송하여도 무방하다. 이때는 그림 14 와 같이 세션키를 상대방의 공개키로 암호화하여 전송하고 세션키를 사용하여 비밀키 암호 알고리즘으로 원래의 데이타를 암호화하여 전송하면 된다.

그림 14 : 세션키의 전송

그러나 세션키를 한쪽에서 설정을 하면 비밀키의 설정방법이 의심스러운 경우가 있을 수 있다. 이때는 양쪽에서 각자 생성한 비밀 정보를 사용하여 둘만이 공유하는 새로운 세션키를 생성하는 것이 바람직하다. 대부분의 키 교환 알고리즘은 1976년에 발표된 Diffie-Hellman 알고리즘에 기초한다. DH 알고리즘은 유한체의 이산 로그 문제의 어려움에 바탕을 둔 알고리즘이다. 실수(real number)에서 로그는 매우 쉽게 계산할 수 있지만 유한체 위에서 정의된 로그(이산 로그라고 부름)는 계산하기가 매우 어렵다.

사용자 A, B가 있을때 DH 알고리즘은 그림 15 와 같은 순서로 이루어진다.

그림 15 : Diffie-Hellman 키 교환

A와 B는 각자가 비밀 정보 xa와 xb를 생성하여 간직한다.
xa와 xb로부터 공개정보 ya와 yb를 계산한다. 여기서 x로부터 y를 계산하기는 쉽지만 반대로 y로부터 x를 계산하는 것은 이산 로그의 성질로 인해 현실적으로 불가능하다.
A와 B는 각각 ya와 yb를 서로에게 전송한다.
A는 xa와 yb를 이용하고, B는 xb와 ya를 이용하여 공통의 비밀정보 z를 유도한다. 여기서 x와 y로부터 z를 유도하는 것은 쉽게 계산되며, A와 B의 계산의 결과는 서로 같다.

위와 같은 DH 알고리즘을 응용하는 방법에따라서 다양한 프로토콜이 존재하고, 또한 유한체 대신에 타원 곡선을 사용하면 타원 곡선을 이용한 Diffie-Hellman 키 교환 알고리즘이 된다.

유한체의 이산대수 : various DH scheme
타원곡선의 이산대수 : various ECDH scheme

참고 : Handbook of Applied Cryptography, Chapter 12 - Key Establishment Protocols (53 pages), Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone, CRC Press, 1999.

'개발자 기본 소양 > 암호학' 카테고리의 다른 글

암호/보안기술 연구정보 (0)	2009.03.02
전자서명 (digital signature) (0)	2009.03.02
해쉬함수 (hash function) (0)	2009.03.02
블록암호 (block cipher) (0)	2009.03.02
국가 표준 암호 알고리즘 (1)	2009.03.02

April weather

암호 알고리즘 및 프로토콜의 이해