정수론과 암호

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

암호라는 말을 들으면 대부분의 사람들은 간첩, 비밀공작, 전쟁 등 군과 관련된 것을 연상하게 된다. 오랜 암호의 역사를 보면 암호는 주로 군사 외교적인 목적으로 사용되어 왔다. 2차 세계대전에서 양측은 매우 정교한 암호를 사용했는데 연합군이 승리한 중요한 요인 중에 하나가 암호전에서의 승리라고 한다. 한편, 비 군용 암호의 사용이 급속히 늘어 난 것은 2차 세계대전 이후이다. 컴퓨터와 통신기술의 발달에 따라, 컴퓨터통신, 전자우편, 은행간 대금결재 등에 쓰이는 민수용 암호가 널리 쓰이기 시작하였다. 이러한 민수용 암호는 통신 내용을 제 삼자로 부터 보호한다는 기본적인 목적 외에도, 다수의 사용자가 편리하게 이용할 수 있어야 하고, 위장사용, 내용의 변경 등 다양한 공격에도 견딜 수 있어야 한다.

1970년대에 이런 목적을 두루 충족시키는 □열쇄가 공개된 암호체계(public key cryptosystem)□라는 새로운 암호체계가 제안되었다. 어떤 암호체계도 기본적으로 두 가지 과정을 거치는데 첫째는 □암호화 과정□ 이고 둘째는 □암호해독 과정□이다. 대부분의 암호체계에서는 첫번째 과정을 할 수 있는 사람은 누구나 두번째 과정도 할 수 있다. 따라서 암호화 하는 방법을 적에게 공개한다는 것은 상상할 수도 없었다. 그러나 이들은 이러한 생각이 언제나 옳지는 않다는 것을 알았다. 만약 암호화하는 방법을 알고 있더라도 해독하는 방법을 알아 내기가 매우 힘들다면 암호화하는 방법을 공개해도 큰 피해는 없을 것이다. 이런 생각에서 그들은 □함정함수(trapdoor function)□라는 개념을 만들었다. 암호화 과정을 하나의 함수로 보았을 때, 암호해독 과정은 그 함수의 역함수에 해당되고, 따라서 암호해독이란 그 역함수를 찾아 내는 작업인 것이다. 역함수를 구하기가 매우 어려운 함수를 함정함수라고 하는데, 수학의 세계에는 이러한 함수가 무궁무진하다.

암호에 쓰이는 계산 방법은 우리가 알고 있는 보통의 계산과는 다르다. 하지만 모르는 사이에 우리는 매일 이런 계산을 하고 있다. 시간 계산의 예를 보자. 5시에서 3시간 후는 8시이고 이것을 식으로 쓰면 3 + 5 = 8 이다. 그런데 11시에서 5시간 후는 4시이므로 식으로 표시하면 11 + 5 = 4 가 된다. 이러한 계산법을 12 를 □법□으로 하는 계산이라고 한다. 12 가 아닌 다른 자연수도 □법□으로 이용할 수 있으며, 덧셈과 뺄셈 외에 곱셈과 나눗셈도 가능하다. 이러한 계산에서 페르마(Fermat)의 작은 정리라는, 그의 천재성이 엿보이는 매우 유용한 정리가 있는데 그 내용은 p 가 소수일 때, 정수 a 의 p 승(a 를 p 번 곱한 수)은 p 를 □법□으로 a 와 같다는 것이다.

M.I.T.의 리베스트(Rivest), 샤미르(Shamir), 에이들만(Adleman)에 의하여 제안된 유명한 RSA 암호체계는 페르마의 작은 정리와 함정함수의 개념을 이용한 것이다. 우선 두 개의 크기가 비슷한 큰 소수 p 와 q 를 선택하여 비밀로 한다. 하지만 그것의 곱인 n = pq 는, 암호화 과정에 쓰이는 또 다른 수 E(암호화 열쇄 - encoding key)와 함께 공개한다. 암호송신자는 약속된 방법에 따라 송신문을 수자 M 으로 바꾼 다음, n 을 □법□으로 M 의 E 승을 계산한 값 C 를 송신하는데, 이 C 가 바로 암호문이다. 암호문 C 의 수신자는 이것을 풀기 위해서 D(암호해독 열쇄 - decoding key)가 필요하다. 이 D 는, C 의 D 승을 n 을 □법□으로 계산한 값이 수자화된 송신문 M 과 같아지도록 미리 정해 놓은 수로서 물론 비밀로 해야 한다.  이 방법의 핵심은 제 삼자도 n 과 E 를 알고는 있지만 p 와 q 는 모르기 때문에 D 를 구할 수 없다는 사실이다.

RSA 암호체계의 보안은 자연수의 소인수분해에 달려 있다. 암호문 C 를 도청한 적이 암호해독 열쇄 D 를 알아 내기 위하여는 n = pq 로 소인수분해할 수 있어야 하는데, p 와 q 가 크기가 비슷한 큰 소수라면 이 계산은 현실적으로 불가능하다. 예를 들어, 일초에 백만번의 연산을 할 수 있는 컴퓨터를 이용하여 현재 알려 진 가장 빠른 방법으로 계산한다 해도, 100 자리 수의 소인수분해에 약 100년 정도 걸린다고 한다. (재래식 방법으로는 우주의 역사 보다도 긴 시간이 필요하게 된다.) 따라서 이러한 암호체계는, 소인수분해에 대한 새로운 수학적 발견에 의하지 아니하고서는 깨뜨리기가 불가능한 것이다.

실제로 정수론을 전공하는 많은 수학자들이 효과적인 소수판정방법과 소인수분해방법을 찾는 연구를 하고 있으며, 연구 결과가 군사기밀 혹은 기업비밀로 분류되기도 한다. 소수판정방법의 연구가 안전한 암호화 키를 만들기 위해 필요한 연구라면, 소인수분해방법의 연구는 이러한 암호체계를 깨뜨리기 위해 필요한 연구라고 할 수 있다. 최근에 개발된 소수판정방법에 의하면, 100 자리 수는 약 45초, 200 자리 수는 약 6분 정도 걸린다고 한다. 한편, 버클리대학의 렌스트라(Lenstra)는 최근 타원곡선 이론을 써서 큰 수를 효과적으로 소인수분해하는 기존의 방법과는 전혀 다른 새로운 방법을 발견하여 수학계에 충격과 희망을 주고 있다.

이러한 일은 수학에서 빈번히 일어나는 현상의 한 예로서, 수학자들이 수학 자체의 심오함과 아름다움에 빠져 연구한 결과들이 뜻하지 않은 곳에서 중요한 응용이 발견되어 각광을 받는 경우이다. 많은 수학자들은 그 심오함 때문에 타원곡선을 반 세기 이상 연구해 왔지만 누구도 이것이 소인수분해와 연관될 것을 예상하고 연구하지는 않았다. 페르마도 그의 정리가 암호에 쓰일 것이라고는 꿈에도 생각하지 못했을 것이다.

* 그림 1. 쿠바의 게릴라 지도자 게바라(Guevara)가 카스트로(Castro)

에게 보낸 암호문.

* 그림 2. 가우스 소수가 복소평면상에 분포된 모습. 테이블보 등의

디자인으로 안성맞춤이다.

조선일보 1993년 8월 31일, 23면