[암호학] 4. 암호체계

[암호학] 4. 암호체계

평문(planetext)은 비밀 유지를 요구하는 통신문, 암호문(ciphertext)은 평문을 일정한 기호 또는 수로 변경한 문서, 복호화(decryption)는 암호문을 평문으로 복원하는 행위, 열쇠(key, '키'라고도 한다)는 평문을 암호문으로 또는 암호문을 평문으로 전환시키는 도구로 전자(평문->암호문)를 암호화 열쇠(키)(encryption key), 후자(암호문->평문)를 복호화 열쇠(키)(decryption key)라고 한다. 

암호기법(cryptography)은 평문을 암호화해서 공격자가 암호문을 해독하기 어렵게 하는 방법이고, 암호해독(cryptanalysis)은 한정된 자료를 가지고 암호문으로부터 평문과 열쇠를 탐지하는 것이다. 

이렇게 암호기법과 암호해독 모두를 연구하는 학문을 암호학(cryptoanalysis)이라고 한다. 

다음은 평문을 암호화하고 복호화하는 과정을 나타낸 것이다.

위의 그림에서 \(P\)는 평문, \(C\)는 암호문을, \(K_{e}\)는 암호화 열쇠, \(K_{d}\)는 복호화 열쇠이다. 

송신자는 먼저 전송할 평문을 적당한 유한수열 \(a_{1},\,a_{2},\,...,\,a_{k}\)로 나타내고, 평문을 암호문으로 전환시키는 암호화 알고리즘으로서 암호화 열쇠 \(K_{e}\)에 의해 결정되는 암호화함수 \(E_{K_{e}}:A\,\rightarrow\,A\)를 이용한다. 즉 \(C=E_{K}(P)\). 

암호문을 받은 수신자는 암호문을 평문으로 복원하기 위한 복호화 알고리즘으로서 열쇠 \(K_{d}\)에 따라 결정되는 복호함수 \(D_{K_{d}}:A\,\rightarrow\,A\)를 사용해 암호문을 본래의 평문으로 복원한다. 즉 \(P=D_{K_{d}}(C)\). 이때 암호화 함수 \(E_{K_{e}}\)와 복호화 함수 \(D_{K_{d}}\)는 일대일 대응이고,$$P=D_{K_{d}}(C)=D_{K_{d}}(E_{K_{e}}(P))=(D_{K_{d}}\circ E_{K_{e}})(P)$$이므로 \(D_{K_{d}}=E_{K_{e}}^{-1}\), 즉 암호화 함수와 복호화 함수는 서로 역함수 관계에 있다. 

암호화는 평문을 암호화하는 방법에 따라 비밀 키 암호체계(secret-key cryptosystem), 공개 키 암호체계(public-key cryptosystem)로 나눈다. 

비밀 키 암호체계에서는 암호화 열쇠 \(K_{e}\)와 복호화 열쇠 \(K_{d}\)가 동일하고, 이 두 열쇠는 송신자와 수신자에게만 알려진 비밀 열쇠이으므로 대칭 암호체계(symmetric cipher system)라고 한다. 

공개 키 암호체계에서는 암호화 열쇠 \(K_{e}\)와 복호화 열쇠 \(K_{d}\)는 서로 다르고, 암호화 열쇠는 공개하나 복호화 열쇠는 비밀로 하므로 비대칭 암호체계(asymmetric cipher system)라고 한다. 

암호는 평문을 암호화하는 방법에 따라 블록 암호(block cipher)와 스트림 암호(stream cipher)로 나눈다. 

블록 암호는 평면을 일정한 길이의 블록으로$$a=\underbrace{\bigcirc\cdots\bigcirc}_{a_{1}}\underbrace{\bigcirc\cdots\bigcirc}_{a_{2}}\cdots\underbrace{\bigcirc\cdots\bigcirc}_{a_{k}}$$와 같이 분할하고 각 블록마다 같은 열쇠를 이용한 암호화 알고리즘 \(E_{k_{e}}\)를 이용해 암호화해서$$b=\underbrace{\bigcirc\cdots\bigcirc}_{b_{1}}\underbrace{\bigcirc\cdots\bigcirc}_{b_{2}}\cdots\underbrace{\bigcirc\cdots\bigcirc}_{b_{k}}$$와 같이 암호문으로 묶어 전환시키고, 이와 같은 암호문의 각 블록마다 같은 열쇠를 이용하여 복호화해서 원래의 평문을 얻는다.    

스트림 암호는 평문과 무관한 무한수열$$s_{0},\,s_{1},\,s_{2},\,\cdots,\,s_{t},\,\cdots$$를 생성하고, 평문을 유한수열 \(a_{0},\,a_{1},\,...,\,a_{k}\)로 나타내어 이 두 수열을 항끼리 더해 얻는 유한수열$$s_{0}+a_{0},\,s_{1}+a_{1},\,...,\,s_{k}+a_{k}$$를 암호문으로 전송한다.

체 \(\mathbb{Z}_{2}=\{0,\,1\}\)의 원소를 값으로 갖는 무한수열 \(\{s_{t}\}\)를 이용하는 경우, 평문을 체 \(\mathbb{Z}_{2}\)의 원소로 구성된 유한수열 \(a_{0},\,a_{1},\,...,\,a_{k}\)로 나타내고,$$b_{i}=a_{i}+s_{i}\,(0\leq i\leq k)$$를 계산해서 암호문 \(b_{0},\,b_{1},\,...,\,b_{k}\)를 전송한다. 암호문을 수신한 자는 체 \(\mathbb{Z}_{2}\)에서$$a_{i}=b_{i}+s_{i}\,(0\leq i\leq k)$$를 계산해 평문 \(a_{0},\,a_{1},\,...,\,a_{k}\)를 얻는다. 

간단히 정리하자면 임의의 \(s_{t}\in\mathbb{Z_{2}}\)에 대해 \(\mathbb{Z}_{2}\)에서 \(s_{t}+s_{t}=0\)이 되는 원리를 이용해 유한수열로 나타낸 평문에 무한수열 \(s_{t}\)를 더해 암호화하고, 다시 무한수열 \(s_{t}\)를 더해서 평문을 얻는다. 

스트림 암호체계는 대수학을 기반으로 연구가 진행되고, 여기서 이용되는 무한수열은 선형 시프트 레지스터(linear shift register)라는 유한 상태 기계(finite state machine)를 이용해 생성하고, 이 수열은 여러 가지 열쇠에 따라 변한다. 이 수열은 수학적 특성을 수학적으로 분석할 수 있고, 알고리즘을 실현하기 쉽기 때문에 널리 이용된다.    

암호의 역사

암호의 변천을 고대 암호와 2차 세계대전을 전후로 한 근대 암호 및 현대 암호로 나눈다. 고대 암호와 근대 암호는 문자의 전치를 이용한 전치 암호(transposition cipher)와 문자를 다른 문자로 치환하는 환자 암호(substitution cipher), 환자 암호와 전치 암호를 복합한 적 암호(product cipher)로 분류한다. 

고대 암호

 

가장 오래된 암호는 기원전 400년경 고대 그리스인들이 사용한 스키테일(scytale)이라고 불리는 전치 암호이다. 이 방법은 전달하려는 평문을 재배열하는 방법으로 굵기가 있는 막대기에 종이(파피루스)를 감아 평문을 가로로 쓴 다음 종이를 풀면 평문의 각 문자가 재배치되어 평문의 내용을 알지 못하게 된다. 암호문을 받은 사람은 보낸 사람이 사용한 막대기와 단면적(반지름)이 같은 막대기에 암호문이 적힌 종이를 감고 가로로 읽어서 평문을 얻는다.

(스키테일 암호. 이 막대를 스키테일이라고 불러서 '스키테일 암호'라고 부른다.) 

최초의 환자 암호로 로마의 카이사르(Caesar, 시저)가 사용한 카이사르 암호이다. 이 암호 방식은 평문의 각 문자를 우측으로 3문자씩 이동시켜 그 위치에 대응하는 다른 문자를 치환함으로써 평문을 암호문으로 변환하는 암호 방식이다. 이 암호문에서 평문으로 복호화하는 방법은 역처리, 즉 암호문 문자를 좌측으로 3문자씩 이동시켜 평문을 얻는다.

(카이사르 암호의 암호화) 

근대 암호

17세기부터 수학의 발전과 더불어 암호도 발전하기 시작했으나 본격적 근대 수학을 도입한 과학적 근대 암호는 20세기부터 발전하기 시작했다.

프랑스 외교관 비즈네르(Vigenere)가 고안한 암호방식, 플레이페어(Playfair)가 만든 2문자 조합암호 이후 1, 2차 세계대전을 거쳐 암호에 대한 연구가 시작되었다. 

근대 암호의 기초가 된 논문은 1920년에 프리드먼(Friedman)이 발표한 "일치 반복률과 암호 응용", 섀넌(Shannon)이 발표한 "비밀 시스템의 통신이론"이다. 

프리드먼은 2차 세계대전 중 독일군의 에니그마(ENIGMA) 암호와 일본군이 사용하던 무라사키 암호를 해독했고, 섀넌은 확률론을 기반으로 한 정보이론을 창시하고 원리적으로 해독 불가능한 암호 방식을 제안했다. 

근대 암호는 1, 2차 세계대전이 연구촉진의 계기가 되었지만, 기술적으로는 전신 기술의 발달과 세계대전의 종전 후 전자계산기가 출현해서 암호화, 복호화, 암호해독의 속도가 빨라져서 암호 실용화의 연구가 활발해졌다.

현대 암호

1970년대 후반에 스탠퍼드 대학의 디피(Diffie)와 헬만(Hellman)의 논문 "New Directions in Cryptography"에서 처음 공개키(열쇠) 암호 방식의 개념을 발표한 것이 계기가 되었다. 

기존의 관용 암호 방식(공통키 암호 방식)은 동일한 암호화 키(열쇠)를 사용하기 때문에 송신자와 수신자는 비밀통신을 하기 전 반드시 열쇠를 사전에 보관하고 있어야 한다. 반면에 공개키 암호 방식은 암호화 키와 복호화 키를 분리해서 암호화 키는 공개하고 복호화 키는 비밀로 보관하도록 한다. 이 방식은 송신자가 수신자에게 평문을 암호화해서 전송할 때, 수신자의 공개 암호화 키로 평문을 암호화해서 전송하면 수신자는 자신이 비밀로 보관한 복호화 키로 암호문을 복호화 해서 평문을 얻는다.

공개키 암호 방식의 구체적 방식은 1978년에 MIT(메사추세츠 공과대학)의 라이베스트(Rivest), 샤미르(Shamir), 애들먼(Adleman)에 의해 실현되었고, 자신들의 이름 첫 자를 따서 RSA암호라고 명명했다. 

RSA암호 이후로 다양한 암호 방식들이 발표되고 있다. 

참고자료:

암호학과 부호이론, 박승안, 경문사

현대 암호학 제 6판, 원동호, 그린

https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%82%A4%ED%85%8C%EC%9D%BC

https://ko.wikipedia.org/wiki/%EC%B9%B4%EC%9D%B4%EC%82%AC%EB%A5%B4_%EC%95%94%ED%98%B8