암호(暗號)의 세계

김명환 (서울대학교 수리과학부 교수)

1. 들어가는 말

많은 사람들이 21세기를 정보화시대라고 한다. 지난 세기에 탄생한 컴퓨터가 짧은 시간에 눈부신 발전을 거듭하면서 인간의 생활양식을 급격히 변화시키고 있다. 그러한 변화 중 가장 중요한 것이 바로 인터넷의 출현이라고 할 수 있다. 모든 것이 정보화되고 그 정보들이 인터넷을 떠다니고 있다.

정보화시대가 도래하면서 정보의 관리, 특히 정보의 보호가 매우 중요한 과제가 되었다. 국가, 회사, 단체 또는 개인이 반드시 보호해야 하는 비밀정보가 보호되지 못한다면 큰 문제가 될 것이다. 거꾸로 그러한 비밀정보를 반드시 알아내야 하는 쪽에서는 그 정보를 알아내기 위하여 필사적인 노력을 경주할 것이다. 이러한 정보전쟁에서 우리가 어느 편에 속하게 될지는 모르는 일이다. 우리가 개발한 신기술 정보를 지켜야하는 입장이 될 수도 있고, 테러집단의 비밀정보를 알아내야 하는 입장이 될 수도 있는 것이다.

암호(暗號, cryptography)는 이처럼 비밀정보를 교환하기 위하여 생겨났다. 처음에는 주로 군사용으로 사용되었으나 최근에는 전자상거래를 비롯하여 전자우편이나 휴대전화에 이르기까지 그 응용범위가 확대되고 있다. 수학은 이러한 암호의 이론적 토양을 제공할 뿐만 아니라 다양한 암호체계를 만들고 이렇게 만들어진 암호체계의 효용성과 안전성을 분석하는 암호기술의 핵심적인 도구 역할을 담당하고 있다. 이러한 연유로 암호이론과 기술은 이제 수학의 한 분야로 간주되고 있다.

이 강의에서는 고전적인 암호체계의 예, 현대적인 암호체계의 종류, 암호체계의 안전성, 구체적인 암호체계의 예, 다양한 응용 등을 소개한다. 본론으로 들어가기 전에 암호체계의 간단한 예를 하나 들어보자. 편의상 한글의 자모를 다음의 표와 같이 나열하고 각각에 숫자를 대응시킨 다음 한글자모 대신에 이 28개의 숫자를 사용하기로 하자. 단, 이 표는 모두에게 공개된 것으로 간주한다.

이제 송신자씨가 정보원씨에게 '사랑해'라는 메시지를 비밀리에 전달한다고 하자. 즉

(ㅅ,ㅏ,ㄹ,ㅏ,ㅇ,ㅎ,ㅐ)=(12,1,6,1,14,26,21)

를 아무도 모르게 전하고 싶은 것이다. 이것을 평문이라고 하는데 이대로 보내면 누구든 이것이 '사랑해'임을 알게되므로 이것을 적당한 규칙아래 변형하여 보낸다. 예를 들어 각 숫자에 3을 더한다.

이렇게 하면

(12,1,6,1,14,26,21) → (15,4,9,4,17,1,24)

를 얻는다. 이러한 과정을 암호화과정이라고 하고, 이렇게 변형된 (15,4,9,4,17,1,24)를 암호문이라고 한다. 암호화하는 규칙을 모르는 도청자씨가 이 암호문을 훔쳐서 한글자모로 바꾸어보면 (ㅠ,ㄷ,ㅗ,ㄷ,ㅡ,ㅏ,ㅍ)가 되어 무슨 뜻인지 알 수가 없다. 그러나 이러한 규칙을 알고있는 정보원씨는 암호문의 각 숫자에서 3을 빼서

(15,4,9,4,17,1,24) → (12,1,6,1,14,26,21)

를 얻는다. 이 과정을 복호화과정이라고 한다. 이것을 한글자모로 바꾸면 (ㅅ,ㅏ,ㄹ,ㅏ,ㅇ,ㅎ,ㅐ), 즉 '사랑해'가 된다.

2. 고전 암호체계

오랜 암호의 역사를 보면 암호는 주로 군사 외교적인 목적으로 사용되어 왔다. 이미 로마시대에 케사르가 부하 장군들과 암호로 된 편지를 주고받았다고 하며 그 이전에도 그리스 등에서 암호를 사용한 기록이 있는 것을 보면 암호의 역사는 무척 오래되었다고 할 수 있다. 어쨌든 전신(電信)이 사용되기 이전인 19세기 말까지의 암호를 제1세대 암호라고 할 수 있다. 제1세대의 대표적인 암호로는 이동암호, 대치암호, 아핀 암호, 비게네르 암호 등이 있다.

(1) 이동암호(shift cipher): 앞에서 예로 든 암호가 바로 케사르(Caesar)가 사용한 암호로서 이러한 암호를 이동암호라고 한다. 모든 한글자모 0,1,2,···,27을 정해진 수(케사르 암호에서는 3)만큼 28을 법으로 더하여 암호화하고 복호화는 그 반대로 한다.

(2) 대치암호(substitution cipher): 한글자모 0,1,2,···,27을 뒤섞은 순열을 하나 택한다. 예를 들어 순열 21,4,11,···,9를 택하였으면,

0 → 21, 1 → 4, 2 → 11, ···, 27 → 9

로 대체함으로써 암호화하고 복호화는 그 반대로 한다. 이동암호는 대체암호의 한 종류로 볼 수 있다. 예를 들어 순열 3,4,5,···,2를 택하면 케사르 암호가 된다.

(3) 아핀 암호(affine cipher): 두 정수 a, b를 택한다. 단 0≤a,b≤27이고 a는 28과 서로 소이어야 한다. 그런 다음 평문의 각 숫자 m을 c≡am+b (mod 28)로 암호화한다. 단 0≤c≤27. 복호화는 다음과 같이 한다. a는 28과 서로 소이므로 a^*a≡1 (mod 28), 0<a^*≤27을 만족시키는 정수 a^*가 존재한다. 이 a^*를 이용하여 다음과 같이 m를 복원한다.

a^*(c-b) ≡ a^*(am) ≡ (a^*a)m ≡ m (mod 28).

아핀 암호도 대치암호의 일종이라 할 수 있다.

(4) 비게네르 암호(Vigenère cipher): 암호화 키를 하나 택한다. 예를 들어 (5,22,3,14)를 암호화 키로 택했다고 하자. 이때 (ㅅ,ㅏ,ㄹ,ㅏ,ㅇ,ㅎ,ㅐ)=(12,1,6,1,14,26,21)를 다음과 같이 암호화한다.

(12,1,6,1,14,26,21) + (5,22,3,14,5,22,3) = (17,23,9,15,19,20,24) = (ㅡ,ㅐ,ㅗ,ㅠ,ㅣ,ㅋ,ㅍ)

평문의 두 번째 1(ㅏ)은 23(ㅐ)으로, 네 번째 1(ㅏ)은 15(ㅠ)로 바뀌었음을 주목하자. 이처럼 비게네르 암호에서는 같은 한글자모라도 그 위치에 따라 다르게 암호화될 수 있다는 점에서 위의 암호들과 크게 다르다. 복호화는 다음과 같이 하면 된다.

(17,23,9,15,19,20,24) - (5,22,3,14,5,22,3) = (12,1,6,1,14,26,21).

더하기와 빼기는 각 좌표끼리 28을 법으로 계산한다. 이동암호는 비게네르 암호의 특별한 경우로 간주할 수 있다. 예를 들어 암호화 키를 (3,3,3,3)으로 택하면 케사르 암호가 된다.

그 외에도 치환 암호, 뷰포트 암호 등이 있다. 이러한 암호들은 대부분 암호문에 나타나는 숫자(한글자모)의 빈도 수, 주기 등 통계적인 특성을 조사함으로써 해독할 수 있다.

암호는 전신의 등장과 1차 세계대전의 영향으로 크게 발전하였다. 2차 세계대전에서 양측은 매우 정교한 암호체계를 사용하였는데, 연합군이 승리한 가장 중요한 요인 중의 하나가 독일과 일본의 암호를 해독하는데 성공했다는 것이라고 한다. 이 시기에 사용되었던 암호들을 제2세대 암호라고 할 수 있는데 이 암호들은 수학적으로도 약간 진보하였으나 그보다는 긴 블록을 암호화 할 수 있는 복잡한 기계들을 사용함으로써 해독에 엄청난 계산이 필요하도록 한 점이 특징이다. 이러한 기계암호는 한국전쟁 때까지 사용되었다고 하는데 컴퓨터의 출현과 함께 무용지물이 되고 말았다.

한편 2차 세계대전 중에 사용된 기계암호를 해독하기 위해서는 엄청난 계산을 수행해야 했는데 이를 위하여 초기 컴퓨터의 일종인 콜로서스(Colossus)가 개발되었다. 이 콜로서스의 개발 책임자가 바로 '컴퓨터를 창안한 수학자'로 유명한 튜링(Turing)으로서 그가 당시 영국군의 암호해독 책임자였다는 사실은 컴퓨터의 발명이 암호해독 방법의 연구와 밀접한 관련이 있었음을 말해준다.

Colossus	Enigma	Hagelin

< 그림 2. 기계 암호에 쓰인 기계들 >

3. 현대 암호학

2차 세계대전이 끝난 후 샤논(Shannon)이 발표한 두 편의 논문은 현대 암호학의 시작을 알리는 신호탄이 되었다. 특히 컴퓨터와 통신기술이 비약적으로 발달한 1970년대부터 샤논의 이론 및 이를 바탕으로 발전한 각종 이론들이 이를 뒷받침하는 기술과 합쳐지면서 다양한 첨단 암호기술들이 개발되기 시작하였다.

이들 제3세대 암호의 특징으로 먼저 정수론, 유한군론, 타원곡선, 가환대수, 대수기하, 조합이론, 그래프이론, 격자이론, 확률론, 수리논리 등 다양한 고급 수학이론들을 사용한다는 점을 들 수 있다. 그리고 많은 경우 암호화 알고리즘을 공개하여 그 장단점에 대한 학문적 공론화과정을 거침으로써 효율성과 안전성을 검증 받기도 한다. 제3세대 암호의 또 하나의 특징으로 전자산업 및 통신산업의 놀라운 팽창과 함께 비 군사용 암호의 사용이 급격히 늘어났다는 점을 들 수 있을 것이다. 암호는 이제 전자상거래, 은행간 대금결재, 스마트카드, 전자화폐, 전자입찰 및 경매, 전자투표, 전자우편, 휴대전화 등 우리의 일상생활 전반에 걸쳐 광범위하게 사용되고 있다.

현대의 암호체계는 통신내용을 제3자로부터 보호할 수 있어야 하고(기밀성-secrecy, 혹은 안전성) 사용하기 편리해야한다는(효율성-efficiency) 기본적인 암호의 목적 이외에도 다음의 기능들이 추가적으로 요구되고 있다.

?무결성(integrity): 정보의 사실성, 즉 수신된 정보가 제3자의 공격이나 송신과정에서 변조 되지 않았는지 확인할 수 있어야 한다.

?인증(authentication): 수신된 정보를 적법한 사용자가 보낸 것인지 아니면 적법한 사용자를 가장한 누군가가 보낸 것인지 확인할 수 있어야 한다.

?부인봉쇄(non-repudiation): 송신자가 보낸 정보를 수신자가 받지 않았다고 하거나 보내지도 않은 정보를 받았다고 주장할 수 없어야 하고, 반대로 수신자에게 보낸 정보를 송신자가 보 내지 않았다고 하거나 보내지도 않은 정보를 보냈다고 주장할 수 없어야 한다.

현대 암호체계는 크게 블록 암호, 스트림 암호, 그리고 공개키 암호의 세 종류로 나눌 수 있다. 이러한 암호들을 소개하기 전에 현대적인 암호체계의 기본 개념을 수학적으로 설명해보자.

평문 전체의 집합을 P, 암호문 전체의 집합을 C라 하자. 암호화 과정은 임의의 평문 m∈P에 대하여 암호문 c∈C를 만드는 알고리즘으로 볼 수 있다. 이 알고리즘을 f라 부르자. 이제 K라는 키 공간(key space)을 생각하자. 이 K는 키라고 불리는 원소들로 이루어진 집합이다. 송신자가 e∈K를 선택하면, 이 암호화 키 e에 대하여 암호화 함수

f_e : P → C

가 대응되고 이 함수를 이용하여 평문 m에 대한 암호문 c=f_e(m)를 만들게 된다. 이 암호문 c의 수신자는 f_e의 역함수 f_e^-1를 이용하여 평문 m를 복원할 수 있다. 복호화 알고리즘을 g라 하면, 암호화 키 e에 대하여 복호화 키 d∈K가 존재하고 d에 대응되는 복호화 함수를

g_d : C→ P

라 하면 g_d =f_e^-1이다. 물론 수신자는 g_d를 알고 있거나 쉽게 구할 수 있어야 한다.

g_d (c) = g_d (f_e(m)) = f_e^-1(f_e(m)) = (f_e^-1 f_e)(m) = m.

현대 암호체계는 암호화 키와 복호화 키가 서로 '같은가' 또는 '다른가'에 따라 크게 두 가지로 분류한다. 암호화 키와 복호화 키가 서로 같은 경우 비밀키(혹은 대칭키) 암호체계라 하고, 서로 다른 경우 공개키(혹은 비대칭키) 암호체계라 한다.

(1) 비밀키 암호체계(secret-key cryptosystem-SKC): 암호화 키와 복호화 키가 같으므로 이 키들을 비밀로 해야한다. 따라서 이 비밀키를 송수신자가 공유하도록 해야한다는 어려움이 있다. 또한 인증기능이 약하다는 단점이 있다. 공개키 암호체계와 비교할 때, 안전성은 떨어지지만 효율성은 매우 높다. 블록 암호와 스트림 암호가 대표적인 비밀키 암호체계이다.

?블록 암호(block cipher): 긴 평문을 일정한 길이의 블록으로 나누어 블록단위로 암호화하는 방식을 말한다. 64비트 단위로 암호화하는 DES(data encryption standard)와 128비트 단 위로 암호화하는 AES(advanced encryption standard) 등이 대표적인 블록 암호체계이다.

?스트림 암호(stream cipher): 평문을 1비트 단위로 암호화하는 방식을 말한다. 스트림 암호는 키를 키스트림 생성기라는 알고리즘에 입력하여 발생되는 1비트 키의 무한수열로 평문을 암호화한다. OTP(one-time pad)도 스트림 암호의 일종이며, 축소 생성기(shrinking generator) 등 다양한 키스트림 생성기들이 사용되고 있다.

(2) 공개키 암호체계(public-key cryptosystem-PKC): 공개키 암호체계는 1976년 Merkle과 Diffie, Hellman이 처음으로 소개하였다. 암호화 키는 공개하고 복호화 키만 비밀로 하면 되므로 다수의 사용자가 사용하기 편리하다. 또한 키의 교환, 인증, 전자서명 등의 기능이 좋다. 비밀키 암호체계와 비교할 때, 안전성은 강한 것으로 믿어지지만 효율성은 매우 낮기 때문에 아직은 비밀키 암호체계가 더 많이 사용되고 있다. 소수의 성질을 이용한 RSA 암호체계, 유한 체의 성질을 이용한 ElGamal 암호체계, 타원곡선의 성질을 이용한 타원곡선 암호체계 등이 대표적인 공개키 암호체계이다. 우리는 5절에서 RSA 암호체계의 기본원리를 살펴 볼 것이다.

4. 암호의 안전성

종래의 암호는 그것을 만들 때는 안전하다고 믿었지만 거의 모두 해독되고 말았다. 그렇다면 해독 불가능한 암호를 만들 수 있는가 하는 의문이 생긴다. 여기서 우리는 암호를 해독한다는 뜻을 정확하게 할 필요가 있다. 영화나 소설에서 보듯이 적의 암호해독 방법을 훔치거나 암호사용자를 붙잡아 고문을 하거나 하는 방법들은 암호해독이라고는 하지 않으며, 이러한 공격에 대하여 완벽하게 안전한 암호는 존재하지 않는다. 암호해독이란 것은 주어진 암호문에 대하여 여러 가지 단편적인 정보들을 토대로 평문을 복원하는 작업이다. 새로운 암호체계의 개발 못지 않게 중요한 것이 다양한 암호체계에 대한 해독 방법을 찾는 암호분석(cryptanalysis) 기술의 개발이다.

여러 가지 공격으로부터 암호가 안전하다는 뜻도 정확하게 할 필요가 있다. 무한의 능력을 가진 컴퓨터로 시간과 비용에 제약받지 않는 공격에 대해 안전한 암호체계는 없다고 가정한다. 그러한 암호체계가 있다 하더라도 사용하는 데 막대한 시간과 비용이 필요할 것이므로 의미가 없다고 할 수 있다. 어떤 암호체계가 안전하다고 하는 것은 컴퓨터의 능력, 시간, 비용 등을 감안할 때 현실적으로 주어진 시간 내에 그 해독 방법을 알아내기가 불가능하기 때문에 안전하다는 것이다. 안전하다고 믿어지는 암호가 갑자기 해독되는 경우도 있는데, 그러한 경우의 대부분은 새로운 수학적 발견에 의한 것이다.

이제 암호 알고리즘의 안전성을 살펴보자. 암호 알고리즘의 중요한 공격방법을 크게 '선택 평문 공격(CPA)', '선택 암호문 공격(CCA1)', '적응선택 암호문 공격(CCA2)' 등 세 가지로 분류할 수 있는데, 이때 암호 알고리즘 f는 공개된 것으로 간주하고 복호화 키를 알아낼 수 있는가가 관건이 된다. 이러한 공격에 대하여 안전한가를 조사, 분석한다.

?선택 평문 공격(chosen plaintext attack-CPA): 공격자가 한꺼번에 선택한 평문들에 대한 암호문이 주어진다는 가정 하에 복호화 키를 찾는 공격.

?선택 암호문 공격(chosen ciphertext attack-CCA1): 공격자가 한꺼번에 선택한 암호문들에 대한 평문이 주어진다는 가정 하에 복호화 키를 찾는 공격.

?적응선택 암호문 공격(adaptively chosen ciphertext attack-CCA2): 공격자가 차례로 선택한 암호문들에 대한 평문이 주어진다는 가정 하에 복호화 키를 찾는 공격.

한편, 공개키 암호체계의 안전성은 이와 같은 공격모델에 대한 안전성과는 다른 개념의 안전성이 요구되는데 크게 다음의 두 가지가 있다.

?구별불능(indistinguishability-IND) 안전성: 임의의 두 평문 m₁, m₂와 그에 대한 두 암호문 c₁, c₂가 있을 때, 공격자가 (m₁,c₁), (m₂,c₂)를 제대로 짝지을 수 있는 확률이 1/2 보다 별로 크지 않아야 안전하다는 개념.

?변조불능(nonmalleability-NM) 안전성: 암호문 c가 주어졌을 때, 공격자가 평문 m은 모른채 m과 어떤 관련이 있는 m'에 대한 암호문 c'을 얻어낼 수 없어야 안전하다는 개념.

공개키 암호체계의 안전성은 위에서 소개한 두 가지의 안전성 개념을 결합하여 사용한다.

5. RSA 암호체계

RSA 암호체계는 1978년에 Rivest와 Shamir, Adleman이 소수의 성질을 이용하여 만든 최초의 공개키 암호체계로서 암호의 개념을 획기적으로 바꾼 것으로 평가되고 있다.

RSA 암호체계는 아직도 가장 많이 사용되고 있는 공개키 암호체계이며 관련 보안소프트웨어 회사인 RSA security는 엄청난 성공을 거두고 있다. RSA 암호체계를 설명하기에 앞서 자연수 m을 법으로 하는 멱승의 계산에 관한 오일러의 정리를 소개하자. 이 정리의 증명은 단 몇 줄로 끝날 만큼 간단하지만, 그 내용은 매우 심오하고 유용하다.

오일러의 정리: 자연수 n에 대하여 a가 n과 서로 소이면

a^Ø(n) ≡1 (mod n)

이다. 여기서 Ø(n)은 n과 서로 소인 0과 n사이의 자연수의 개수를 나타내는 기호이다.

만약 n이 소수 p이면 Ø(p)=p-1이므로

a^p-1 ≡ 1 (mod p)

이 되어 페르마의 작은 정리를 얻는다. 예를 들어, 2¹⁰ ≡ 1 (mod 11), 즉 2¹⁰=1024를 11로 나누면 나머지가 1이다. 이 예에서는 직접 계산을 하여도 많은 시간이 걸리지 않지만, 비슷한 계산을 매우 큰 p에 대해서 할 경우 엄청난 시간을 절약할 수 있음을 알 수 있다.

대부분의 암호체계에서는 암호화를 할 수 있으면 복호화도 할 수 있었다. 따라서 암호화하는 방법을 공개한다는 것은 상상할 수도 없었다. 그러나, Merkle과 Diffie, Hellman은 이러한 생각이 언제나 옳지는 않다는 사실을 주목하였다. 만약 암호화 과정을 알고 있더라도 복호화 과정이 매우 힘들다면 그 암호화 과정을 공개해도 문제될 것이 없을 것이다. 이러한 생각에서 그들은 '함정식 함수'란 개념을 만들었다. 암호화 알고리즘 f와 암호화 키 e를 (따라서 암호화 함수 f_e를) 알고 있더라도 복호화 키 d를 모르면 f_e의 역함수 g_d를 구하는 것이 현실적으로 불가능할 때, f_e를 함정식 함수라고 부른다. 이러한 함정식 함수를 이용하는 암호체계의 백미는 역함수의 계산을 간단히 할 수 있는 조그만 비밀정보(복호화 키 d)로서, 이것만 적에게 숨기면 된다.

이제 RSA 암호체계를 기본 틀을 살펴보자. 사용자가 몇 명이든 상관없이 각각의 사용자는 두 개의 큰 소수 p와 q를 선택하여 n=pq을 계산하고,

ed ≡ 1 (mod Ø(n)), 0 < e, d < Ø(n) = (p-1)(q-1)

을 만족시키는 두 수 e, d를 한 쌍 택한다. 이제 법으로 쓰일 n과 암호화 키 e는 공개하되, p와 q, 그리고 복호화 키 d는 비밀로 한다. 물론 공개된 (n,e)와 비밀키 d는 사용자마다 다르다. 공개정보가 (n,e)인 정보원씨에게 송신자씨가 평문 m='사랑해'를 암호화해서 보내려면 다음과 같이 하면 된다. (만약 m≥n이면 m을 여러 개의 작은 블록들로 나누어 암호화하면 되므로 0<m<n이라고 가정하자. 또한 m과 n이 서로 소가 아닐 확률은 무시해도 될 정도로 작으므로 gcd(m,n)=1을 가정해도 된다.) 송신자씨는

c ≡ f_e(m) ≡ m^e (mod n), 0 < c < n

를 만족시키는 암호문 c를 구하여 정보원씨에게 전송한다. 암호문 c를 받은 정보원씨는 자신만이 알고있는 복호화 키 d를 이용하여 다음과 같이 평문 m='사랑해'를 복원할 수 있다.

g_d(c) ≡ c^d ≡ (m^e)^d ≡ m^ed ≡ m^Ø(n)u+1 ≡ (m^Ø(n))^u m ≡ m (mod n).

이 경우, 암호화 알고리즘 f와 복호화 알고리즘 g 가 같다.

조금 더 구체적인 예로서, 이번에는 송신자씨가 m=123='즉시탈출'이라는 지령을 적국에 있는 정보원씨에게 보낸다고 하자. 정보원씨의 공개정보를 (n,e) = (437,13)이라 두자. 437=19×23이므로 p=19, q=23이고, Ø(n)=18×22=396, 13×61=793=2×396+1이므로 d=61이다. 평문 m을 암호화 키 e=13을 이용하여 계산하면

123¹³ ≡ 386 (mod 437)

이므로, c=386이라는 암호문을 얻고 이 암호문을 정보원씨에게 전송한다. 암호문 c=386을 받은 정보원씨는 자신의 복호화 키 d=61을 이용하여

386⁶¹ ≡ 123 (mod 437)

을 얻고, 지령대로 '즉시탈출'을 시도한다.

이 방법의 핵심은 제3자인 도청자씨도 정보원씨의 공개정보 (n,e)를 알고는 있지만 p와 q를 모르고, 따라서 Ø(n)=(p-1)(q-1)를 계산할 수가 없으므로 d를 알아 낼 수가 없다는 점이다. 이 암호체계의 보안을 위협하는 것은 단 한가지 뿐으로서, 어렵기로 악명 높은 정수의 소인수분해가 바로 그것이다. Ø(n)을 알면 복호화 키인 d를 구할 수 있다. 그러나 Ø(n)을 계산하기 위해서는 n을 소인수분해 할 수 있어야 하는데 n이 매우 큰 수일 경우, 이 계산은 소인수분해에 대한 획기적인 수학적 발견이 없이는 현실적으로 불가능하다.

이 암호체계는 각 사용자가 자신의 (n,e)를 공개해도 송수신 당사자만이 그 내용을 알 수 있다는 장점 외에도 여러 가지 다양한 좋은 기능을 갖고 있다. 그러한 기능 중의 하나가 서명 기능이다. 정보원씨에게 보내진 메시지가 '사랑해'건 '즉시탈출'이건 간에 정보원씨는 이 메시지가 송신자씨에게서 온 것이라는 것을 어떻게 알 수 있을까? 사실 정보원씨의 공개정보 (n,e)를 이용하면 누구든지 이 메시지를 정보원씨에게 보낼 수 있다. 도청자씨가 보냈을 지도 모른다. 이러한 문제를 해결하는 방법이 바로 서명기법이다. 송신자씨의 공개정보를 (n',b)이라 하고 복호화 키(비밀키)를 a이라 하자. 물론 n'=p'q'이고, 복호화 키 a와 소수 p', q'은 송신자씨만이 알고 있다. 이제 s='송신자'이라 하자. 앞에서와 마찬가지로 0<s<n', gcd(s,n')=1을 가정할 수 있다. 송신자씨는 자신의 비밀키 a를 이용하여

t ≡ s^a (mod n'), 0 < t < n'

을 만족시키는 서명 t를 계산하여 앞서의 암호문 c와 함께 전송한다. 정보원씨는 c와 t를 받아 c는 앞에서와 같이 복호화하여 평문 m을 얻고, t는 송신자씨의 공개키 b를 이용하여 다음과 같이 s='송신자'을 복원할 수 있다.

t^b ≡ (s^a)^b ≡ s^ab ≡ s^Ø(n')u+1 ≡ (s^Ø(n'))^u s ≡ s (mod n').

이러한 서명은 송신자씨의 비밀키 a를 모르는 도청자씨로서는 만들 수가 없는 것이다. 각 사용자가 자신의 공개정보를 수시로 바꿈으로서 이 암호체계의 안전성을 더 강화할 수 있다.

이제 RSA 암호체계의 안전을 보장하는 소인수분해에 대해 알아보기로 하자. 소수는

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, . . ., 2^6972593-1, . . ., 2^13466917-1, . . .

등으로, 우리가 계산할 수 있는 한 아무런 규칙 없이 끝없이 계속된다. 먼 옛날부터 사람들은 모든 자연수는 소수들의 곱으로 소인수분해 될 수 있으며, 주어진 수의 소인수분해 방법이 단 한가지뿐임이 알고 있었다. 하지만 실제로 주어진 정수의 소인수분해를 찾는 것은 생각보다 훨씬 더 어렵다. 따라서 '실용적'으로 가장 중요한 문제는 다음과 같다.

- 주어진 수가 소수인지 알아내는 효과적인 방법을 찾아라.

- 주어진 수를 효과적으로 소인수분해 하는 방법을 찾아라.

전자는 암호체계를 만들기 위해 필요한 것이고 후자는 암호체계를 깨뜨리기 위해, 또한 암호체계가 얼마나 안전한지 알아보기 위해 필요하다. '효과적'이란 말은 숫자의 크기에 비해 계산의 횟수가 너무 빨리 증가하지 않는다는 뜻이다. 얼마 전까지만 해도 위의 두 문제에 대한 해답은 매우 '비효과적'인 방법들뿐이었다. 주어진 수의 소인수를 찾아내거나, 그 수가 소수임을 알아내는 가장 직접적인 방법은 '나누어 보는 것'인데 이 방법은 물론 매우 비효과적이다. 일초에 백만 번의 계산을 할 수 있는 컴퓨터로 30 자리 수를 이렇게 계산하는데 하루, 40 자리 수는 백만 년, 그리고 50 자리 수를 계산하는데는 우주의 역사보다도 긴 시간이 필요하다!

지난 이십여 년 간 많은 수학자들이 효과적인 소인수분해 방법을 연구한 결과 상당히 유용한 방법들이 개발되었다. 현재까지 알려 진 가장 빠른 방법으로 계산하면, 75자리 수는 한달, 100자리 수는 백년 정도가 소요된다고 한다. 소수판정법에도 많은 발전이 있었다. 많은 수학자들의 노력으로 효과적인 소수판정법들이 실용화되어 100자리 수를 판정하는데 약 45초, 200자리 수는 약 6분 정도면 충분하다고 한다. 결국 RSA 암호체계는 소수판정은 빨리 할 수 있지만 소인수분해에는 많은 시간이 걸리는 현실을 이용한 암호체계이다.

물론 이러한 시간이 컴퓨터의 발달로 어느 정도 줄어 들 수는 있지만, 근본적인 해결책이 될 수는 없다. 새로운 수학적 발견만이 유일한 근본적인 해결책이며, 최근 Lenstra가 타원곡선 이론을 이용하여 획기적인 소인수분해 방법을 발견한 것은 그러한 좋은 예라고 할 수 있다. Lenstra의 방법은 기존의 방법과는 전혀 다른 방법이어서 수학계에 충격과 희망을 주고 있다. 그의 방법은 현재까지 알려진 가장 빠른 방법으로서, 인수가 3 개 이상이거나 차이가 큰 두개의 인수가 있을 때, 특히 효과적인 것으로 알려져 있다.

그런데 이러한 일은 수학의 세계에서 빈번히 일어나는 현상이다. 즉, 수학이 호기심에서 출발하여 그 자체의 완전함과 아름다움을 추구하며 발전하다가, 갑자기 생각지도 않던 중요한 응용이 발견되는 이러한 예는 허다하다. 수학자들이 자연스러운 호기심과 심오한 아름다움 때문에 타원곡선을 반세기 이상 연구해 왔지만 어느 누구도 그것이 소인수분해에 응용될 것을 예상하고 연구하지는 않았다. 페르마나 오일러도 그들의 정리가 암호에 쓰일 것이라고는 꿈에도 생각하지 않았을 것이다. 컴퓨터의 급속한 발달은 이러한 현상을 가속화하고 있으며, 이러한 맥락에서, 순수수학과 응용수학의 구분이 무의미한 시대가 멀지 않은 것으로 보인다.

6. 끝맺는 말

암호의 기능은 점점 더 다양해지고 있다. 전자산업이 발달함에 따라 다양한 기능을 가진 암호체계를 필요로 하는 경우가 폭발적으로 늘어나고 있으며, 이미 암호는 현대인의 일상생활 곳곳에서 쉽게 찾을 수 있다. 아파트 현관이나 회사의 출입문의 시건 장치, 컴퓨터의 패스워드로부터 은행계좌나 신용카드의 비밀번호, 전자우편이나 휴대전화 내용의 암호화에 이르기까지 이루 헤아릴 수가 없다. 전자화폐, 전자입찰, 전자투표 등에서도 핵심은 암호기술이다.

예를 들어 전자 입찰을 생각해보자. 나의 입찰가를 암호화해서 제출했을 때, 다른 입찰자가 나의 입찰가를 몰라야 할 뿐만 아니라 나의 입찰가보다 조금 높은 금액의 암호문을 만들 수 없어야 한다. 또 낙찰된 후에 내가 애초의 입찰가를 부인할 수 없어야 한다. 더 나아가 입찰시행기관의 누구도 입찰이 마감되기 전에 나의 입찰가를 미리 알아내어 다른 입찰자에게 알려줄 수 없어야 한다. 전자투표의 경우도 마찬가지이다. 각 투표자가 투표지를 암호화하여 제출했을 때, 투표자 외에는 어느 누구도 그 내용을 몰라야 하고 또 변조할 수도 없어야 한다. 두 번 이상 투표할 수 없도록 해야하며, 부정 투표자가 있어도 안되며, 그러면서도 정확한 집계가 이루어져야 하고 그 결과에 잘못이 없음을 확인할 수 있어야 한다.

새로운 암호의 응용은 위에서 언급한 것들 외에도 무수히 많다. 인터넷상에서 음악이나 영상 등의 디지털제품 판매에 있어서도 가장 시급한 과제는 암호기술이다. 중요한 비밀정보를 다루는 기관의 컴퓨터시스템에 대한 해킹과 방어는 전쟁이나 다름없으며 이러한 네트웍보안의 핵심도 암호기술이다. 암호의 새로운 응용에 대하여 최근에 활발히 연구되고 있는 대표적인 것 두 가지만 더 예를 들어보자.

?영지식 증명(zero knowledge proof-ZKP): 내가 아는 중요한 정보에 대하여 그 내용에 관한 것은 일체 알려주지 않으면서 내가 그 정보를 알고 있음을 상대방에게 증명해 보이는 방법.

?다자간 계산(multi-party computation-MPC): 다수의 사용자가 각각 자신만이 아는 정보를 소유한 상태에서 각자의 정보는 노출시키지 않으면서 모두에게 필요한 새로운 정보를 계산 하여 공유하는 방법.

이러한 조건들은 단순히 암호문을 주고받을 수 있는 암호체계로는 도저히 만족시킬 수 없는 조건들로서, 이러한 까다로운 조건들을 모두 만족시킬 수 있는 암호체계를 만들기 위해서는 고급 수학이론의 도움이 절대적이다.

정보화시대를 맞아 암호의 중요성이 대두되고 있다. 우리는 산업적인 측면에서의 필요성을 주로 언급하였지만 국가안보의 관점에서 보게되면 암호이론과 기술의 수준은 국가의 존망과 직결되는 문제가 된다. 암호이론과 기술의 수준에서 뒤쳐지면, 평화시에는 정보속국 내지는 정보식민지로 전락하게 될 것이고 전시에는 패망하게 될 것이기 때문이다.

?내 정보는 네 정보, 네 정보도 네 정보

?내 정보는 내 정보, 네 정보는 네 정보

?내 정보는 내 정보, 네 정보도 내 정보

우리는 어디에 해당되는가? 정보화시대에 항상 염두에 두어야 할 질문이다.