[암호론] 정수론과 암호

[폭풍속으로]

정수론과 암호 - 서울대학교 수학과 부교수 김명환

1. 들어가는 말

정수론은 말 그대로 정수의 성질을 연구하는 학문이다. 우리가 1, 2, 3,. . . 등으로 표시되는 정수에 무슨 대단한 비밀이 숨어 있을 것 같지도 않고 혹시 있다고 해도 별 쓸모가 없을 것처럼 보일 것이다. 정수론의 연구주제는 크게 두 가지로 나눌 수 있는데, 하나는 소수(1과 자신 이외에는 약수가 없는 양의 정수)에 대한 연구이고, 다른 하나는 방정식의 정수해에 대한 연구이다. 이러한 연구를 하는 정수론이 일반인들에게 매우 추상적이고 실용성이 없는 학문이라고 느껴지는 것이 어쩌면 당연한 일인지도 모르겠다. 하지만 정수론의 많은 결과들이 수학의 다른 분야뿐만 아니라, 수학 이외의 여러 학문에 응용되어 왔으며, 특히 최근의 정수론을 이용한 암호체계의 발달은 이러한 생각이 잘못된 것임을 보여 주고 있다. 정수론을 이용한 암호체계의 연구 결과 중 일부는 군사 기밀로 분류될 정도로 유용성을 인정받고 있다. 이러한 응용 덕분에 일반인들의 정수론에 대한 이해와 기대가 늘어난 것이 사실이지만, 정수론이 차지하는 수학사적인 비중이나 학문적인 중요성은 이러한 응용성을 배제하더라도 변함이 없음을 강조하고 싶다.


--------------------------------------------------------------------------------

2. 암호

암호(secret code)라는 단어를 들으면 대부분의 사람들은 간첩, 비밀공작, 전쟁 등 군대와 관련된 것을 연상하게 된다. 은밀한 지하실에서 도청한 적의 암호를 해독하려고 애쓰는 암호해독가의 모습이 떠오르기도 한다. 아무튼 일반인들에게 암호는 일상적인 생활과는 관련이 없는, 그야말로 영화에서나 볼 수 있는 것으로 이해되고있다. 이러한 독자들에게 암호가 우리의 일상생활에 어떻게 이용되며 이런 암호체계를 만들기 위해 수학이, 그 중에서도 정수론이 어떻게 사용되는 가를 간단히 설명하고자 한자.

오랜 암호의 역사를 보면 암호는 주로 군사 외교적인 목적으로 사용되어 왔다. 기록에 의하면 이미 시이저가 부하 장군들과 암호로 된 편지를 주고받았다고 하니 암호의 역사는 적어도 2000 년은 된 셈이다. 암호는 전신의 발명과 1 차 세계대전의 영향으로 크게 발전하기 시작하였다. 2 차 세계대전에서 양측은 매우 정교한 암호체계를 사용하였는데, 연합군이 승리한 가장 중요한 요인 중의 하나가 독일과 일본의 암호를 해독하는데 성공했다는 것이라고 한다. 그러나 이러한 사실이 크게 부각되지 못한 것은 아마도 암호에 관한 한 일체의 내용을 드러내고 싶지 않은 정부의 입장 때문이라 생각된다. 한편 대전 후 컴퓨터와 통신기술의 발달에 따라 비 군용 암호의 사용이 급격히 늘어났다. 컴퓨터 통신, 전자우편, 은행간 대금결재 등에 쓰이는 민수용 암호체계는 통신내용을 제 삼자로부터 보호한다는 기본적인 암호의 목적 이외에도, 사용하기 편리하며 다수의 사용자가 이용해도 그 비밀이 유지될 수 있어야 하고, 위장사용, 내용의 변경 등 다양한 공격에도 견딜 수 있어야 한다. 종래 사용되었던 암호는 그것을 만들 때는 안전하다고 믿었지만 거의 모두 해독되고 말았다. 그렇다면 해독 불가능한 암호를 만들 수 있는가 하는 의문이 생긴다. 여기서 우리는 암호를 해독한다는 뜻을 정확하게 할 필요가 있다. 영화나 소설에서 보듯이 적의 암호해독기를 훔치거나 암호책을 복사하는 방법은 확실하기는 하나 이러한 것을 암호해독이라고는 하지 않으며, 이러한 공격에 대하여 안전한 암호는 존재하지 않는다. 암호해독이란 것은 암호로 된 문장에 대하여 가능한 여러 가지 정보를 토대로 그 뜻을 알아내는 일반적인 방법을 찾는 것이다.

한편, 암호해독을 비롯한 여러 가지 공격으로부터 암호가 안전하다는 뜻도 정확하게 할 필요가 있다. 무한의 능력을 가진 컴퓨터로 시간과 비용에 제약받지 않는 공격에 대해 안전한 암호체계도 있지만, 그러한 암호는 사용하는 데도 막대한 시간과 비용이 필요하므로 그 쓰임은 매우 제한된다. 어떤 암호체계가 안전하다고 하는 것은 현실적으로 (컴퓨터의 능력, 시간, 비용 등을 감안할 때) 그 해독법을 알아내기가 불가능하기 때문에 안전하다는 것이다. 안전하다고 믿어지는 암호가 해독되는 경우도 있는데, 그러한 경우의 대부분은 새로운 수학적 발견에 의한 것이다. 그러면 암호의 구성원리가 되는 수학에 대하여 간단히 알아보자.


--------------------------------------------------------------------------------

3. '법'에 의한 계산

대부분의 암호체계에서 쓰이는 계산방법은 우리가 알고 있는 보통의 계산방법과는 다르다. 하지만 우리는 이런 계산방법을 매일 쓰고 있다. 시간 계산의 예를 보자. 5 시에서 4시간 후는 9 시라는 것을 식으로 표시하면 5 + 4 = 9 이다. 그런데, 10 시에서 5 시간 후는 3 시가 되며 11 시에서 8 시간 후는 7 시가 된다. 이것을 식으로 표시하면 각각 10 + 5 = 3, 11 + 8 = 7 이다. 우리가 알고 있는 보통 덧셈과는 다르지만 이러한 시간 계산방법은 다른 계산방법과 마찬가지로 산술적으로 많은 성질을 만족시킨다. 이러한 계산방법을 12 를 '법'으로 하는 계산법이라고 하고 '='를 '@ (mod 12)'로 바꾸어 쓴다. 12 를 '법'으로 하는 계산법에서 12 의 배수는 모두 0 과 같은 것으로 간주한다. 마찬가지로 12 로 나누었을 때 나머지가 같은 수들은 모두 같은 것으로 간주하게 된다. 또한 덧셈 이외에 뺄셈과 곱셈도 가능하며, 나눗셈은 제한적으로 가능하다. 예를 들어서, 11 과 83는 12 를 '법'으로 같다. 12 뿐만 아니라 다른 어떤 양의 정수도 '법'으로 이용할 수 있는데, 이러한 '법'에 의한 계산에 대하여, 페르마(Pierre de Fermat 1601-1665)의 이름이 붙은 간단한 정리를 하나 소개하고자 한다. '페르마의 작은 정리' 라고 불리는 이 정리의 증명은 단 몇 줄로 끝날 만큼 간단하지만, 그 내용은 매우 심오하고 유용하다.

그 정리의 내용은 다음과 같다. 만약 p 가 소수이고 a 가 p 로 나누어지지 않으면 ap-1 @ 1 (mod p) 이다. 여기서 (mod p) 는 단지 p 가 '법'이라는 것을 표시하는 기호이다. 정리의 내용 다시 말하면 ap-1 을 p 로 나누면 나머지가 1 이라는 뜻이다. 예를 들어서, 210 @ 1 (mod 11), 즉 210 = 1024 를 11로 나누면 나머지가 1 이다. (실제로 계산해 보라.) 위의 예에서는 직접 계산을 하여도 많은 시간이 걸리지 않지만, 비슷한 계산을 매우 큰 p 에 대해서 할 경우 엄청난 시간을 절약할 수 있음을 알 수 있다. 페르마의 작은 정리는 이처럼 멱승의 '법'에 의한 계산에 아주 유용하게 쓰인다.

이 정리의 역도 참인 것이 알려져 있다. 즉, p 로 나누어지지 않는 모든 a 에 대하여, ap-1 @ 1 (mod p) 이면, p 는 소수가 된다. 이제 이러한 간단한 기초지식을 바탕으로 암호에 대해서 알아보자.


--------------------------------------------------------------------------------

4. 키(key)가 공개된 암호

암호학자들은 해독 불가능하면서도 효과적인 암호를 만들기 위하여 많은 노력을 해왔다. 1970년대 말 머어클(Merkle), 디피(Diffie), 헬만(Hellman) 은 키가 공개된 암호(public-key cryptosystem)라는 전혀 새로운 암호체계를 제안했다. 모든 암호체계에는 기본적으로 두 가지 단계가 있는데, 하나는 평문을 암호문으로 바꾸는 '암호화 과정' 이고, 다른 하나는 암호문을 해독하여 평문으로 바꾸는 '복호화 과정'이다. 대부분의 암호체계에서는 첫 번째 과정을 할 수 있는 사람은 누구나 두 번째 과정도 할 수 있다. 따라서 암호화하는 방법을 적에게 공개한다는 것은 상상할 수도 없었다. 그러나, 이들은 이러한 생각이 언제나 옳지는 않다는 사실을 주목하였다. 만약 암호화 과정을 알고 있더라도 복호화 과정이 매우 힘들다면 그 암호화 과정을 공개해도 문제될 것이 없을 것이다. 이러한 생각에서 그들은 '함정식 함수'란 개념을 만들었다. 모든 암호체계에서 암호화 과정이란 M 이라는 평문을 f(M) 이란 암호문으로 바꾸는 함수 f 에 해당되고, 복호화 과정은 그 역함수 f-1 해당된다. 두 과정을 수학적으로 표시하면 f-1(f(M)) = M 이다. f 의 역함수를 구하기가 현실적으로 불가능할 때, 우리는 f 를 함정식 함수라고 부른다. 이러한 함정식 함수를 이용하는 암호체계의 백미는 역함수의 계산을 간단히 할 수 있는 조그만 비밀정보로서, 이것만 적에게 숨기면 되는 것이다.


--------------------------------------------------------------------------------

5. RSA 암호체계

함정식 함수의 개념을 도입하여 여러 가지 암호체계가 제안되었는데 1978년에 리베스트(Rivest), 샤미르(Shamir), 에이들만(Adleman)에 의해 제안된 RSA 암호체계는 페르마의 작은 정리를 이용한 암호체계이다. 우선 두 개의 큰 소수 p 와 q 를 선택하여 비밀로 한다. 하지만 그것의 곱인 n = pq 는 암호화 키로 쓰는 또 다른 수 E 와 함께 공개한다. E 는 (p - 1)(q - 1) 과 서로 소인 (1 이외의 공통의 약수가 없는) 수 중에서 선택한다. 암호화 하고자 하는 문장 M 을 미리 약속된 방법에 따라 숫자의 열 B 로 표시한 후, 역시 미리 약속된 방법에 따라 여러 개의 작은 블록으로 나눈다. 단, 각 블록을 하나의 수라고 생각했을 때 모두 n 보다 작도록 나누어야 한다.

이렇게 나눈 작은 블록들을 B1, B2, ..., Bt 라고 하자. 각각의 블록 Bi 에 대하여, Ci @ BiE (mod n) 를 계산한 후, 이들을 차례로 나열한 C1 C2 ... Ct 가 바로 암호문이다. 이것을 해독하기 위해서는 복호화 키 D 가 필요한데, D 는 DE @ 1 (mod (p-1)(q-1)) 을 만족시키도록 미리 선택된 수로서, 물론 우리편만 알고 있는 비밀이어야 한다. 페르마 작은 정리를 사용하면, 각각의 Ci 에 대하여, CiD @ (BiE)D @ BiED @ Bi (mod n) 임을 보일 수 있다. 따라서 CiD (mod n) 를 계산하면 Bi 가 얻어 진다.

예를 하나 들어보자. p = 19, q = 23, n = p x q = 437, E = 13, D = 61 이라고 하면, (p - 1)(q - 1) = 396 이고 13 x 61 = 793 = 2 x 396 + 1 이므로 위의 조건을 모두 만족한다. '탈출하라'라는 문장에 대응되는 숫자열이 123 이라고 가정하고, B = 123 을 암호화 키 E = 13 을 이용하여 계산하면 12313 @ 386 (mod 437) 이므로, C = 386 이라는 암호문을 적진에 있는 우리 정보원 X 에게 전송한다. 암호문 386 을 받은 X 는 자신의 복호화 키 D = 61 을 이용하여 38661 @ 123 (mod 437) 을 얻고, 지령받은 대로 '탈출'을 시도한다.

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

이 방법은 여러 사람이 각자의 n 과 E 를 공개하고 교신을 해도 보내는 사람과 받는 사람 외에는 그 내용을 알 수 없다는 장점 이외에도 여러 가지 다양한 기능을 갖고 있다. 그러한 기능 중의 하나가 보내는 사람의 서명이다. 이러한 기능은 두 사람(갑과 을)이 비밀의 복호화 키 D 를 공유하고 서로 교신할 경우 가능해 진다. 예를 들어보자. 어느 날 갑이 암호문을 받고 해독한 결과 '작전개시'라는 내용을 얻었다. 그런데, 이 전문을 을이 보냈다는 것을 어떻게 확신할 수 있는가?

이미 n 과 암호화 키 E 는 공개되었으므로 누구나 '작전개시'라는 전문을 갑에게 보낼 수 있다. 아마 적이 보냈을 지도 모른다. 이러한 문제점을 해결하는 방편으로 을은 자신이 보내는 암호문임을 증명하기 위하여 복호화 키 D 를 이용하여 (을로부터)D (mod n) 를 계산하여 암호문과 함께 보낸다. 갑은 이 사실을 확인하기 위해 암호화 키 E 를 이용하여 (을로부터)DE (mod n) 을 계산함으로써 '을로부터' 온 암호문임을 확인할 수 있게 된다. 복호화 키 D 를 모르는 제 삼자는 이러한 서명을 남길 수 없기 때문이다. 매번 서명을 다르게 함으로써, 제 삼자가 이전에 도청한 전문에서 서명을 복사하여 사용하는 것도 방지할 수 있다.


--------------------------------------------------------------------------------

6. 소수판정과 소인수분해

암호체계의 안전을 보장하는 소인수분해에 대해 알아보기로 하자. 소수는 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, . . . 등으로, 우리가 계산할 수 있는 한 아무런 규칙 없이 끝없이 계속된다. 고대 그리스인들은 모든 양의 정수는 소수들의 곱으로 소인수분해될 수 있음을 알고 있었으며, 주어진 수의 소인수분해 방법이 단 한가지뿐임도 알고 있었다. 하지만 실제로 주어진 정수의 소인수분해를 찾는 것은 생각보다 훨씬 더 어렵다. 따라서 '실용적'으로 가장 중요한 문제는 다음과 같다.

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

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

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

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


--------------------------------------------------------------------------------

7. 끝맺는 말

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

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

더우기, 최근의 컴퓨터의 급속한 발달은 이러한 현상을 가속화하고 있으며, 이러한 맥락에서, 순수수학과 응용수학의 구분이 무의미한 시대가 멀지 않은 것으로 보인다.