썸머 워즈에 등장한 암호에 관하여

썸머 워즈를 보면, 주인공인 켄지가 한밤중에 오즈에게서 긴 숫자 메시지를 받은 뒤 종이에 이리저리 숫자를 적어가며 암호를 푸는 모습을 볼 수 있다. 본인은 오늘 이 암호에 관하여 소개해보려고 한다. 

01. 무슨 암호인가?

켄지가 작품 속에서 열심히 풀던 그 암호의 정체는 "RSA 암호"라고 불리는 현대 암호 중 하나이다. 

어째서 RSA 암호라고 불리느냐, 이 암호를 개발한 사람들의 이름(Rivest, Shamir, Adelman) 가장 앞글자를 따서 이 암호의 이름을 붙였기 때문이다. 

02. RSA 암호의 특징은?

암호를 만들고, 이를 이용해 정보를 주고받기 위해서는 두 개의 열쇠(Key)가 필요하다. 전하고 싶은 메시지를 암호화하기 위한 "암호화 열쇠", 그리고 암호화된 메시지를 풀기 위한 "복호화 열쇠". 

RSA 암호 이전에 고안된 여러 암호들은 이 "암호화 열쇠"와 "복호화 열쇠"가 같았고, 그렇기에 암호화 열쇠를 얻는다는 것은 복호화 열쇠를 얻는다는 것과 마찬가지의 의미였다. 덕분에 암호화 열쇠를 어떤 방식으로든 얻게 된다면 암호문을 푸는 것 또한 수월해졌고, 자연스레 이 암호화 열쇠의 보안이 중요해지게 되었다. 암호화 열쇠를 공개한다는 건 상상조차 못할 일이었다. 

예를 들어보자. 

당신이 K OQXG AQW라는 암호문을 중간에 가로챘다고 가정해보자. 저것이 과연 무슨 뜻일지 잠시 생각해보자. 암호화 열쇠를 모르는 경우 저 암호문이 무엇을 뜻하는지 알아내기 위해서는 꽤 오랜 시간이 걸린다. (물론 간단한 암호기에 숙련된 전문가는 금방 풀 수 있는 암호이기도 하다.) 

하지만 암호화 열쇠가 A→C, B→D, C→E,…와 같은 방식으로 문자 치환 방식이라는 정보를 얻게 된다면, 복호화 열쇠는 C→A, D→B, E→C,…와 같은 방식이라는 정보 또한 자연스럽게 얻게 된다. 즉, 암호를 푸는 것이 굉장히 간단한 작업이 되며, 저 암호문이 I LOVE YOU를 뜻한다는 것을 정말 쉽게 알 수 있다. 

이처럼 암호화 열쇠가 복호화와 직결되기 때문에 암호화 열쇠가 공개된다는 것은 그 암호의 보안성에 치명적인 영향을 끼친다는 것과 같은 말이 된다. 더불어 받는 사람에게 사전에 암호화 열쇠=복호화 열쇠를 넘겨주어야 받는 사람이 그 암호를 해독할수 있다는 점은 자연스레 '암호화 열쇠를 넘겨주는 도중에 암호화 열쇠가 유출될 가능성'을 만들어내고, 이처럼 암호의 보안성을 깰 요소들이 곳곳에 산재해 있었다. 

하지만 RSA 암호는 이전까지의 암호와는 다르게

1. 암호화 열쇠를 공개하고 

2. 암호화 열쇠와 복호화 열쇠가 다르다. 

03. RSA 암호가 뭐길레 이것이 가능할까?

RSA 암호란 기본적으로 두 개의 소수를 가지고 만드는 암호이다. 공개된 암호 열쇠(=n)는 두 개의 소수(=각각 p, q)를 곱한 합성수이며, 복호화 열쇠는 그 두 개의 소수가 된다. 이는 알고 있는 두 소수를 곱해서 암호화 열쇠를 만드는 것은 쉬우나, 공개된 암호화 열쇠를 소인수분해하여 복호화 열쇠를 얻는 것은 어렵다는 "소인수분해의 비대칭성"에 기인한다. 

04. 직접 RSA 암호를 만들고 풀어보자

STEP 1. 암호화, 복호화 열쇠 만들기

n, e는 공개된 열쇠, p, q, d는 비공개된 열쇠이다. 

p와 q는 소수이며, n=pq. 

e×d mod ((p-1)과 (q-1)의 최소공배수) = 1이 되도록 적당한 e와 d를 골라준다. 

예시 : p=5, q=11 

그렇다면 n=55

e는 적당한 양의 정수인 7을 선택해준다. 

p-1=4, q-1=10이므로 p-1과 q-1의 최소공배수는 20

따라서 7d mod 20 = 1, 즉, 7×d를 20으로 나눈 나머지가 1인 d를 찾으면 된다. 이 경우, d=3이다. 

STEP 2. 암호화

전달하고 싶은 평문이 M, 암호문이 C라고 할 때, 암호화 식은 다음과 같다. 

C=M^e mod n

우리가 보내고 싶은 평문 M=13이라고 하자. (현대 암호는 평문을 숫자로 치환한 뒤 암호화하기에 M은 숫자이다.)

그렇다면 암호문 C는

13^7 mod 3 = 62748517을 55로 나눈 나머지 = 7

따라서 C=7이다. 

STEP 3. 복호화

복호화 식은 M=C^d mod n이다. 

당신은 C=7이라는 암호를 받았고, 또한 n=55, e=7이라는 사실을 알고 있는 상황이다. 

만약 당신이 d를 알고 있다면 복호화는 간단하다. 평문 M = 7^3 mod 55 = 343을 55로 나눈 나머지 = 13. 

하지만 만약 d를 모른다면 STEP 1에서 실행했던 복호화 열쇠를 구하는 과정을 통해 d를 구하여야 하는데, 이 과정에서 n의 인수분해가 필요하다. 

그렇다면 문제 하나. C=141, n=437, e=119일 때 M은 무엇일까요?

05. 소인수분해의 어려움을 의심하는 이들을 위해

약간 이상하지 않은가? 분명히 03에서 본인은 

[이는 알고 있는 두 소수를 곱해서 암호화 열쇠를 만드는 것은 쉬우나, 공개된 암호화 열쇠를 소인수분해하여 복호화 열쇠를 얻는 것은 어렵다는 "소인수분해의 비대칭성"에 기인합니다.]

이라고 말했다. 그런데 위 예시를 보면 n의 인수분해가 별로 어려워 보이지 않는다. 

이는 본인이 일부러 n을 인수분해하기 쉬운 숫자로 설정했기 때문이다. 

6을 소인수분해하는 것은 간단하다. 

55를 소인수분해하는 것 또한 간단하다. 

437은 2~3분간 고민하면 답이 나온다. 

하지만 75462131이 어떤 두 소수를 곱한 수인지 구하는 것은 꽤 시간이 걸린다. (75462131은 7591과 9941을 곱한 수이다.)

그리고 보통 RSA 암호를 구축하는 데 쓰이는 소수는 300자리 이상이다. 

다시 썸머 워즈로 돌아와 보자. 

켄지가 풀었던 문장 중 일부인 "the magic words are squeamish ossifrage"는 상당히 유명한 문장 중 하나이다. 

RSA-129라고도 알려져 있는 문장인데, 이 문장이 유명한 이유는 1977년 마틴 가드너의 수학 칼럼에 기고된 100달러짜리 문제와 관련되었기 때문이다. 그 문제가 무엇이냐 하면

Q. 114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541를 소인수분해하라. 

였다. 이는 공개 열쇠 방식의 암호가 얼마나 안전한지 궁금해진 사람들이 일종의 실험을 위해 낸 문제이기도 하다. 

이 문제의 답은 

p=3490529510847650949147849619903898133417764638493387843990820577 

q=32769132993266709549961988190834461413177642967992942539798288533

였으며, 이 문제가 기고된 1977년으로부터 17년이 지난 1994년에 600명의 자발적인 참여자로 구성된 한 팀에 의해 겨우 풀린 문제이다. 슈퍼 컴퓨터도 이 두 소수를 구하는 데 상당히 긴 시간을 필요로 한다. 

위에서 보통 RSA 암호에 쓰이는 소수는 300자리 이상이라고 말했는데, 이 문제의 합성수는 겨우 129자리 정도밖에 되지 않는다. 이 암호의 보안성에 대한 의심이 거의 사라졌으리라 믿는다. 몇몇 사람들이 "가장 큰 소수"와 "소수의 규칙성" 또는 "소수를 구하는 (유용한) 공식"에 집착하는 이유이기도 하다. 

06. 썸머 워즈의 비현실성

썸머 워즈의 주인공 켄지는 이러한 소인수분해를 하룻밤 새에 해낸다. 또한 켄지는 일본 수학 올림피아드 대표를 떨어진 학생이며, 위 문제를 하룻밤 새에 풀어낸 사람이 55명이라는 점 또한 주목할만한 부분이다. 이 얼마나 무서운 세계인가, 슈퍼 컴퓨터의 연산 능력을 능가하는 사람들이 55명이나 존재하는 세계라니.

물론 이런 점이 애니메이션 감상에 방해가 되느냐고 묻는다면 단연코 아니라고 대답할 수 있다. 보통은 이런 사실을 알지도 못할 뿐더러, 위 장면은 작품에서 켄지의 천재성을 강조하는 도구로 쓰일 뿐이다. 이런 사실을 알지 못해도 상관 없으며, 설령 알기 때문에 살짝 거슬리더라도 썸머 워즈는 충분히 수작이며, 굉장히 재밌다. 그렇기에 부디 이러한 점을 너무 신경쓰지 않았으면 좋겠고, 이 내용이 작품을 평가절하하는 원인이 되지 않았으면 좋겠다.