암호 전쟁의 최신 무기는 ‘수학’

모름지기 정보란 중요한 자원이어서 여러 사람이 공유할수록 그 가치는 떨어진다. 모두가 아는 정보는 가치있는 정보가 아니다. 정보를 아느냐 모르느냐에 따라 사람의 생사가 갈리기도 하고, 전쟁의 승패가 갈리기도 한다.

이러니 누군가와 정보를 공유하려면 제3자에게 누설되지 않아야 하지만, 사람이 주고 받는 말이나 글은 다른 사람이 듣고 읽기 쉬운 법. 낮말 듣는 새와 밤말 듣는 쥐를 피할 수 없다면, 정보를 주고 받는 사람만 알 수 있는 보조 정보를 이용하는 수밖에 없다. 그것이 바로 암호이다.

정보를 주고 받는 사람이 둘뿐이라면 그나마 간단하다. 둘만 아는 비밀 단어를 정하는 것만으로도 중요한 정보가 마구 노출되는 일이 줄어든다. 이런 건 사내 비밀 연애만 봐도 알 수 있는 일이다.

그러나 정보를 주고 받는 사람들의 규모가 커지고 전달하려는 내용이 복잡해지면, 비밀 단어 몇 개를 정하는 정도로는 별 쓸모가 없다. 어떻게 하면 비밀을 유지하면서 효율적으로 정보를 주고 받을 수 있을까?

황금벌레의 암호

가장 단순한 암호는 글자를 바꾸는 것이다. 역사적으로 보면 알파벳의 각 글자를 정해진 수만큼 다음 글자로 바꾸는 방식인 카이사르 암호가 있다. 예를 들어, A는 D로, B는 E로, C는 F로 차례대로 바꾸는 식이다. 그러나 이 방식의 암호는 글자 몇 번 바꾸어 보는 걸로 너무쉽게 풀린다. 영어라면 최악의 경우 26번만 시도해 보면 된다.

조금 더 풀기 어렵게 하려면, 순서가 드러나지 않도록 글자를 바꾸는 순서를 뒤섞거나, 아예 다른 기호로 바꾸어 버리는 것을 생각할 수 있다. 이 경우, 몇 글자 옮기면 되는지만 알면 되는 카이사르 방식에 비해 보조 정보가 훨씬 많이 필요하다. 다음 암호문이 한 예이다.

53‡‡†305))6*;4826)4‡.)4‡);806*;48†8¶60))85;;]8*;:‡

*8†83(88)5*†;46(;88*96*?;8)*‡(;485);5*†2:*‡(;4956*

2(5*—4)8¶8*;4069285);)6†8)4‡‡;1(‡9;48081;8:8‡1;4

8†85;4)485†528806*81(‡9;48;(88;4(‡?34;48)4‡;161;:

188;‡?;

위의 해괴한 암호문은 에드거 앨런 포(Edgar Allan Poe, 1809-1849)의 걸작 단편 “황금벌레(The Gold-Bug)”에 등장한다. 글자를 바꾸는 방법이 26!≈4.03×10²⁶가지이므로, 시행착오로 하나하나 바꿔 보는 방식으로는 해독할 수 없다. 그러나 이런 암호 체계는 통계적인 방식을 동원하면 어렵지 않게 풀 수 있다.  소설 속 주인공은 기호가 나타나는 빈도를 분석하여, 가장 많이 나타난 기호 ;가 영어에서 가장 자주 쓰이는 글자 e라는 식으로 암호문을 풀어 나간다. 암호문에 약간의 비밀 단어가 쓰였지만 뛰어난 추리력으로 주인공은 결국 캡틴 키드가 숨겨 놓은 보물을 발견한다.

이런 장면은 암호학자 샤미르(Adi Shamir)가 말한 보안의 3원칙을 연상시킨다.

첫째, 절대적으로 안전한 체계는 존재하지 않는다.

둘째, 취약점을 반으로 줄이려면 비용을 두 배로 늘려야 한다.

셋째, 암호는 일반적으로 우회하는 것이지 뚫는 것이 아니다.

에니그마(Enigma)

황금벌레에 나온 암호와 같은 방식은 초보적인 단계여서, 암호문을 해독하는 것이 그리 어렵지 않다. 실제로 포는 독자들이 비슷한 방식으로 만들어 보낸 암호를 모조리 해독해 내기도 하였다. 빈도 분석법을 피하기 위하여 e를 두 가지 문자로 대체한다거나 하는 방식이 쓰이기도 하지만, 그래 봐야 난이도가 획기적으로 높아지거나 하지는 않는다.

이런 점을 극복하기 위하여, 기계 장치를 써서 문자를 바꾸는 경우의 수를 대폭 늘이는 방법을 사용할 수 있다. 대표적인 것으로, 제2차 세계 대전에서 독일이 사용하였던 장치인 에니그마(Enigma)를 들 수 있다. 타자기처럼 생긴 이 기계는, 회전자와 배선판을 끼워 넣는 방법에 따라 글자를 치환하는 방법이 무려 1.6×10²⁰가지에 달하여 그때까지 알려져 있던 방식으로는 암호를 깨뜨릴 수가 없었다.

에니그마(Enigma) ⓒ ScienceTimes

실제로 독일군은 연합군이 에니그마 암호를 해독하는 것은 불가능하다고 믿어 의심치 않았기에, 전쟁이 끝날 때까지 에니그마를 사용하였다. 그러나, 영국은 에니그마 암호를 해독하기 위해 여러 분야의 전문가들을 그야말로 있는 대로 긁어 모아, 블레츨리 파크(Bletchley Park)에 연구소를 만들었다. 엄청난 끈기에 천재적인 통찰력, 그리고 여기에 행운이 겹치면서, 영국은 난공불락이던 에니그마를 해독하는 데 성공하였다. 암호 해독이라는 보이지 않는 전쟁에서 승리한 연합군은 결국 제2차 세계 대전을 승리로 이끌 수 있었다.

블레츨리 파크에서 단연 두각을 드러낸 인물은 수학자 튜링(Alan Turing, 1912-1954)이었다. 수학에서 “계산”이 어떤 의미인지를 탐구했던 그는 컴퓨터의 기본 원리를 구상하였고, 이 이론 상의 기계는 에니그마를 해독하던 경험을 바탕으로 하여 콜로서스(Colossus)라는 컴퓨터로 구현되었다. 군사 기밀이었던 탓에 미국에서 만든 에니악(ENIAC)보다 늦게 공개되었지만, 지금은 블레츨리 파크에서 만들었던 콜로서스가 세계 최초의 전자식 컴퓨터로 인정되고 있다.

공개키 암호

암호문을 만들거나 푸는 과정에 필요한 보조 정보를 키(key)라 부른다. 전통적인 암호 체계에서는 암호를 만드는 방법을 알면 푸는 방법도 알 수 있으므로, 암호를 만드는 키와 암호를 푸는 키가 동일하다 할 수 있다.

이 두 키가 다른 암호 체계가 가능할까? 그러니까, 암호를 만드는 방법과 암호를 푸는 방법이 전혀 달라서, 어느 한쪽 정보로는 다른 쪽 정보를 알 수 없는 상황이 가능하겠냐는 것이다.

리베스트(Ronald Rivest), 샤미르(Adi Shamir), 에이들먼(Leonard Adleman) 세 사람이 고민하던 것이 바로 이 질문이었다. 언뜻 생각하기에는 불가능해 보이는 이 상황은, 한쪽 방향은 계산이 쉽지만, 반대쪽 방향은 계산이 어려운 함수를 이용하여 만들어낼 수 있다. 세 사람은 여러 함수를 생각하다가, 두 소수의 곱셈은 간단하지만, 그 곱을 소인수분해하는 것은 대단히 어렵다는 데 생각이 미쳤다. 이 사실을 이용한 암호 체계에서 암호를 만드는 것은 쉽지만, 암호를 깨는 것은 지극히 어려웠다.

두 소수 101과 103을 예로 RSA의 원리를 알아보자. 컴퓨터에서 모든 문자는 수로 바꾸어 생각할 수 있으므로, 수를 암호화하는 과정만 생각하면 된다. 암호를 받을 사람은 암호화키로 (10403,7)을 공개한다. 여기서 10403은 101과 103의 곱이고, 7은 (101-1)×(103-1)과 서로소인 수를 하나 고른 것이다. 암호를 만드는 키를 공개한다는 점에서 이러한 암호 체계를 공개키 암호 체계라 부른다.

이제 암호를 보내는 상황을 생각해 보자. 예를 들어 수 10을 보내려면, 10을 7번 곱한 다음 10403으로 나눈 나머지인 2717을 보낸다. 암호를 받는 쪽에서는 2717을 8743번 곱한 다음 10403으로 나눈 나머지를 구하면 그 결과가 다시 10이 된다. 난데없이 등장한 8743은 암호를 푸는 키로, 암호를 받을 사람이 비밀로 간직하는 수이다. 이 수는 유클리드 호제법을 이용하면 7과 (101-1)×(103-1)로부터 간단히 구할 수 있다.

중간에 암호문을 가로챈 사람이 이 암호를 풀려면 공개되어 있는 키인 10403과 7로부터 비밀인 키 8743이라는 수를 이끌어낼 수 있어야 한다. 그러나 10403이 두 소수 101과 103의 곱이라는 사실을 모르고는 8743을 알아내는 것이 거의 불가능하다.

세 사람은 이 암호 체계에 이름의 머리글자를 따서 RSA라는 이름을 붙이고, RSA 암호를 제공하는 회사를 차렸다. 이것이 바로 현재 전 세계에서 가장 널리 쓰이고 있는 암호이다.  “리만 가설(Riemann Hypothesis)이 증명되면 모든 암호를 깰 수 있다.”라는 이상한 주장도 RSA가 소수의 성질에 기반하고 있기 때문에 생긴 일종의 미신(?)이라 하겠다.

리베스트, 샤미르, 에이들먼은 RSA를 개발한 공로로 2002년에 전산학 분야의 노벨상이라 불리는 튜링상(Turing award)를 수상하였다.

암호의 발전

현대 사회에서 암호는 군사적인 목적 이외에도 수많은 일상생활에서 사용되고 있다. 인터넷 웹브라우저에서 중요한 정보들이 암호화 되어 전송되는 덕분에 전자상거래라는 새로운 기술이 개발될 수 있었다. 이제는 암호를 풀지 않은 채로 암호문의 내용을 다루는 놀라운 기술까지 개발되어 있다. 비유하자면, 1을 암호화한 암호문과 2를 암호화한 암호문으로부터 1+2=3을 암호화한 암호문을 만들어낼 수 있는 셈이다.

지금도 수많은 암호 체계가 제안되었다가, 생각지도 못한 방식으로 깨지는 일이 흔하다. 널리 쓰이고 있는 RSA에 극소수만 알고 있는 우회로가 있을지도 모르는 일이다. 정말로 그렇다면 새로운 암호는 어떤 원리로 구현되어야 할까? 암호의 세계에서는 그야말로 창과 방패의 끝없는 전쟁이 벌어지고 있다.

 ScienceTimes