나머지로 지키는 비밀

한 번도 만난 적 없는 두 사람이, 모두가 엿듣는 통신망에서 비밀 열쇠를 맞출 수 있을까요? 답은 시계의 산수와, 1640년 페르마가 편지에 적어 둔 정리 하나에 있습니다.

이 글의 처럼 점선이 그어진 숫자는 좌우로 끌 수 있고(키보드 ←/→도 됩니다), 밑줄 친 말에 마우스를 올리면 그림에서 그 부분이 빛납니다. 그림 속 점들도 직접 끌 수 있습니다. 색이 칠해진 선택지는 눌러서 바꿀 수 있습니다. 휴대폰에서는 마우스를 올리는 대신 누르면 됩니다.

비밀 편지를 주고받으려면 두 사람이 같은 열쇠를 가지고 있어야 합니다. 보내는 사람은 열쇠로 글을 뒤섞고, 받는 사람은 같은 열쇠로 되돌립니다. 어려운 것은 그 열쇠를 건네는 일입니다. 열쇠를 편지에 함께 적어 보내면, 편지를 가로챈 사람도 열쇠를 얻습니다.

그래서 수천 년 동안 답은 하나였습니다. 미리 직접 만나거나, 믿을 만한 전령에게 맡기는 것입니다. 군대와 외교관은 암호책을 봉인해 날랐고, 그 책을 빼앗기면 그동안의 통신이 모두 드러났습니다. 오늘날 여러분의 브라우저는 한 번도 만난 적 없는 은행 서버와 1초도 안 되는 사이에 비밀 열쇠를 맞춥니다. 그 사이에 오가는 신호를 누가 모두 엿듣고 있어도 괜찮습니다.

이 글은 그것이 어떻게 가능한지를 따라갑니다. 재료는 뜻밖에 소박합니다. 나눗셈의 나머지, 2,300년 된 유클리드의 계산법, 그리고 1640년 페르마가 편지에 증명 없이 적어 둔 정리 하나입니다.

1 · 카이사르의 원판시계 위의 덧셈

이 절의 물음은 이것입니다. 가장 오래된 암호는 어떻게 생겼고, 왜 쉽게 풀렸을까? 답을 따라가다 보면 이 글 전체의 도구인 '나머지 산수'가 나옵니다.

아주 오래된 암호에서 시작합시다. 로마의 역사가 수에토니우스는 율리우스 카이사르가 비밀 편지를 쓸 때 글자를 알파벳에서 세 칸씩 밀어 썼다고 전합니다. A 대신 D, B 대신 E를 쓰는 식입니다. 그러면 끝에 있는 X, Y, Z는 어디로 갈까요? 알파벳 끝을 지나 처음으로 돌아가 A, B, C가 됩니다.

끝이 처음과 이어진 줄은 곧 시계입니다. 26개의 글자를 원 위에 늘어놓고, 안쪽 원판을 k칸 돌려 봅시다. 열쇠는 $k =$ 입니다. 평문⁠(plaintext)⁠ 의 글자들은 바깥 고리에서 노랗게, 그 바로 안쪽 글자는 주황으로 빛납니다. 암호문⁠(ciphertext)⁠은 입니다. 숫자 k를 끌어 원판을 돌려 보고, 평문의 글자가 어느 글자로 바뀌는지 그림에서 따라가 보세요.

A를 0, B를 1, …, Z를 25로 적으면 카이사르 암호⁠(Caesar cipher)⁠는 덧셈 한 번입니다. 글자 $x$는 $x + k$가 되고, 26 이상이 되면 26을 뺍니다. 이런 계산을 모듈러 연산⁠(modular arithmetic)⁠이라고 합니다. 26으로 나눈 나머지만 보고 계산하는 산술입니다. X는 23이고, 여기에 3을 더하면 26입니다. 26을 26으로 나눈 나머지⁠(remainder)⁠는 0, 곧 A입니다.

기호를 읽어 봅시다. $x \mapsto x + k$는 "x를 x + k로 보낸다"는 뜻이고, 식 끝의 $\pmod{26}$은 "26으로 나눈 나머지로 계산한다"는 표시입니다('모드 26'이라 읽습니다). 26을 이 계산의 법이라고 부릅니다. 예를 들어 k = 3이면 Y(24)는 24 + 3 = 27이 되고, 27을 26으로 나눈 나머지 1, 곧 B가 됩니다. 이런 산수는 우리도 매일 합니다. 10시에서 5시간 뒤는 3시(12로 나눈 나머지)이고, 월요일에서 9일 뒤는 수요일입니다. 수를 10진법⁠(positional notation)⁠으로 적을 때 마지막 자리는 10으로 나눈 나머지입니다.

열기도 쉽습니다. 원판을 거꾸로 $k$칸 돌리면 됩니다. 그런데 바로 이것이 약점입니다. 열쇠는 0부터 25까지 26가지뿐이니 모두 해 보면 그만입니다. 다음 암호문을 가로챘다고 해 봅시다.

→ 칸 되돌리면 →

그렇다면 열쇠의 가짓수를 늘리면 될까요? 알파벳을 아무 순서로나 섞은 표를 열쇠로 쓰면 가짓수가 $26! = 26 \times 25 \times \cdots \times 1 \approx 4 \times 10^{26}$이나 됩니다. 26!('26 팩토리얼⁠(factorial)⁠')은 26부터 1까지를 모두 곱한 수입니다. A의 짝으로 26글자 가운데 하나, B의 짝으로 남은 25글자 가운데 하나, …를 고르는 방법의 수이기 때문입니다. $10^{26}$은 1 뒤에 0이 26개 붙은 수이니, 1초에 10억 개씩 시험해도 100억 년이 넘게 걸립니다. 흔히 열쇠의 가짓수가 이만큼 많으면 안전하다고 생각하지만, 이런 암호는 풀립니다.

방법의 핵심은 글자를 세는 것입니다. 글이 길어지면 각 글자가 나오는 비율은 대체로 그 언어 고유의 비율에 가까워집니다(큰 수의 법칙⁠(law of large numbers)⁠과 닮은 현상입니다). 영어라면 E가 가장 흔하고(글자의 10분의 1 남짓), T와 A가 그 뒤를 따릅니다. 글자를 섞어 바꿔도 E는 늘 같은 글자로 바뀌니, 암호문에서 가장 자주 나오는 글자는 아마 E를 바꾼 글자일 것입니다. 이렇게 흔한 글자부터 하나씩 짝을 맞춰 가면 열쇠를 하나도 시험하지 않고 표를 되살릴 수 있습니다. 정리하면, 열쇠가 아무리 많아도 한 글자가 늘 같은 글자로 바뀌면 글자의 빈도가 그대로 새어 나옵니다.

푸는 법을 적은 가장 오래된 기록은 9세기 바그다드에서 나왔습니다. 아바스 왕조의 수도였던 이 도시에서 활동한 알킨디의 글입니다. 알킨디는 이슬람 세계의 최고 지도자인 칼리프들의 후원 아래 그리스 철학을 아랍어로 옮기고 해설한 철학자였습니다. 이 방법의 밑바탕에는 쿠란과 하디스의 글자와 낱말을 하나하나 헤아리던 학문 전통이 있었다는 설명도 있습니다. 쿠란은 이슬람의 경전이고, 하디스는 예언자 무함마드의 언행을 모은 것입니다.

이 빈도 분석⁠(frequency analysis)⁠은 글자의 통계⁠(statistics)⁠로 암호를 푼, 기록에 남은 첫 방법입니다. 확률⁠(probability)⁠론이 수학으로 자리 잡기 수백 년 전의 일입니다. 알킨디의 이 논고는 오랫동안 잊혀 있다가 1980년대에 이스탄불의 문서고에서 필사본이 다시 확인되었습니다. 글자를 세어 언어의 통계를 읽는 생각이 20세기에 섀넌의 영어 엔트로피⁠(entropy)⁠와 오늘날의 언어 모델⁠(language model)⁠로 자란 이야기는 「말을 세는 기계」와 「다음 단어를 맞히는 기계」에 있습니다.

'암호'를 뜻하는 영어 낱말 cipher에도 바그다드를 거친 길이 남아 있습니다. 이 낱말은 '비었다', 곧 0을 뜻하는 아랍어 '시프르'에서 왔고, 시프르는 0을 가리키던 산스크리트어 '슌야'를 옮긴 말입니다. 인도의 숫자가 아랍어 책을 거쳐 중세 유럽에 들어오면서 이 말은 라틴어 cifra가 되었고, 처음에는 0을, 다음에는 숫자 하나하나를 뜻했습니다(프랑스어 chiffre는 지금도 '숫자'와 '암호'를 함께 뜻합니다). 그 말이 왜 비밀 글까지 가리키게 되었는지는 확실하지 않습니다. 0이라는 낯선 기호가 알아보기 어려운 것의 상징이 되었다는 설명도 있고, 글자를 숫자로 바꿔 적는 일이 곧 '시프르로 바꾸기'였기 때문이라는 설명도 있습니다. 핑갈라의 운율 계산에서 '비었다'는 표시로 쓰인 슌야 이야기는 「세지 않고 세기」 1절에 있습니다.

빈도 분석을 피하는 길은 열쇠를 자꾸 바꾸는 것이었습니다. 위 그림의 원판은 1467년 무렵 레온 바티스타 알베르티가 책에 적은 암호 원판을 닮았습니다. 건축가이자 인문학자인 그는 오랫동안 로마 교황청에서 문서 일을 했습니다. 다만 그의 안쪽 원판에는 글자가 뒤섞인 순서로 적혀 있었습니다. 교황청 비서와 나눈 대화를 계기로 쓴 이 글에서 알베르티는 몇 낱말마다 원판을 돌려 열쇠를 바꾸자고 제안했습니다. 위 그림으로 치면 글을 쓰는 도중에 $k$를 바꾸는 것입니다. 한 글자가 여러 글자로 바뀌니 빈도가 뭉개집니다.

16세기에는 열쇠 낱말의 글자만큼 칸 수를 바꿔 가며 미는 방식이 나왔습니다. 1553년 베네치아에서 조반 바티스타 벨라소가 발표했고, 뒤에 프랑스의 외교관 블레즈 드 비즈네르의 이름이 붙은 암호입니다. 오늘날의 표준형으로 적으면, 평문과 열쇠 글자열을 글자마다 26을 법으로 더하는 일입니다. 예를 들어 열쇠 낱말이 KEY(10, 4, 24)이면 첫 글자는 10칸, 둘째 글자는 4칸, 셋째 글자는 24칸 밀고, 넷째 글자부터 다시 10칸, 4칸, 24칸을 되풀이합니다. 오랫동안 '풀 수 없는 암호'로 불리던 이 방식은 1863년 프로이센의 퇴역 장교 카지스키가 열쇠 낱말의 길이를 알아내는 방법을 발표하면서 무너졌습니다. 길이만 알면 나머지는 카이사르 암호 여러 개로 쪼개지기 때문입니다. 카지스키가 처음은 아니었을지도 모릅니다. 1854년 런던의 찰스 배비지는 한 발명가가 '새 암호'라며 내놓은 이 방식을 공개 도전에 응해 풀었지만 방법은 밝히지 않았습니다. 계산하는 기계를 설계한 그 배비지입니다(「기계가 풀 수 없는 문제」). 1980년대에 덴마크의 연구자 올레 프랑크센이 배비지의 노트를 조사해, 그가 카지스키와 같은 방법을 이미 쓰고 있었음을 보였습니다. 왜 발표하지 않았는지는 확실하지 않습니다. 크림 전쟁 중이던 영국 정부가 비밀로 두기를 원했으리라는 추측이 있지만, 이를 뒷받침하는 문서는 없습니다.

2 · 곱하기로 섞기되돌릴 수 있는 곱셈

이 절의 물음은 이것입니다. 나머지 산수에서 곱셈은 언제 되돌릴 수 있을까? 이 물음의 답이 뒤에 나올 모든 암호의 뼈대가 됩니다.

더하기 대신 곱하기로 섞으면 어떨까요? 글자 $x$를 $ax + b$로 보내는 것입니다(26으로 나눈 나머지로 계산합니다). 예를 들어 a = 3, b = 0이면 B(1)는 3, 곧 D가 되고, J(9)는 27을 26으로 나눈 나머지 1, 곧 B가 됩니다. 곱하기는 글자를 더 복잡하게 흩어 놓습니다. 대신 조심할 것이 하나 생깁니다. 서로 다른 두 글자가 같은 글자로 가 버리면, 받는 사람은 원래 어느 글자였는지 알 수 없습니다.

위 줄의 $x$에서 아래 줄의 $ax + b$로 선을 그어 봅시다. 법은 $n =$ (알파벳이면 26), 곱하는 수는 $a =$ , 더하는 수는 $b =$ 입니다. 세 숫자를 끌어 보면서 아래 줄에 분홍 점(여러 선이 겹친 칸)이 생기는 때를 찾아보세요.

$n = 26$, $b = 0$으로 두고 $a = 2$로 바꿔 보세요. 짝수를 곱한 결과는 늘 짝수이고, 26이 짝수라서 26을 빼도 짝수로 남습니다. 그래서 홀수 칸에는 아무 선도 닿지 않고, 짝수 칸마다 두 글자가 겹칩니다. 예를 들어 B(1)는 2로 가고, O(14)도 28을 26으로 나눈 나머지 2로 갑니다. $a = 13$이면 더 심해서 두 칸(0과 13)에 모든 글자가 몰립니다. 반대로 a = 3이면 겹치는 칸이 하나도 없습니다. 규칙은 이렇습니다. $a$와 $n$의 최대공약수⁠(greatest common divisor)⁠가 1일 때, 곧 둘이 서로소⁠(coprime)⁠일 때, 그리고 그때에만 선이 겹치지 않습니다. $b$는 모든 선을 같은 칸 수만큼 옆으로 옮길 뿐이라 겹침과 상관없습니다.

까닭은 두 방향으로 나뉩니다. 먼저 $a$와 $n$에 1보다 큰 공약수 $d$가 있으면 $ax$도 $n$도 $d$의 배수라서, $ax$를 $n$으로 나눈 나머지도 늘 $d$의 배수입니다(a = 2, n = 26이면 d = 2이고 나머지는 늘 짝수입니다). $n$개의 글자가 $n/d$개의 칸에 몰리니 겹칠 수밖에 없습니다.

거꾸로 서로소일 때 두 글자 $x$, $y$가 겹쳤다면 $ax$와 $ay$의 나머지가 같으니, 그 차이 $a(x - y)$가 $n$의 배수입니다. 곧 $n$이 $a(x - y)$를 나눕니다. $n$은 $a$와 서로소이니 $x - y$를 나누어야 하고(3절의 베주 항등식⁠(Bézout's identity)⁠으로 확인할 수 있습니다), 0부터 $n - 1$ 사이에서 그런 두 수는 $x = y$뿐입니다. 두 수의 차이가 n보다 작으니 n의 배수⁠(multiple)⁠가 되려면 0이어야 하기 때문입니다.

그때 곱하기 $a$는 $n$개의 칸을 $n$개의 칸과 빠짐없이 하나씩 짝짓는 전단사⁠(bijective)⁠이고, 그 짝짓기를 되돌리는 곱셈 $a^{-1}$('a의 역수⁠(inverse)⁠'라 읽습니다)이 있습니다. 법 26에서 3의 역수는 9입니다. 3 × 9 = 27이고 27을 26으로 나눈 나머지가 1이니, 3을 곱한 뒤 9를 곱하면 제자리로 돌아옵니다. 이렇게 역수가 있는 수를 법 $n$의 단원이라고 부르고, 단원의 개수를 $\varphi(n)$로 씁니다(오일러 피 함수⁠(Euler's totient function)⁠, 'φ(n)'은 '피 n'이라 읽습니다). 26과 서로소인 수는 1부터 25까지의 홀수 가운데 13을 뺀 12개이니 φ(26) = 12입니다.

$n$을 29나 23 같은 소수⁠(prime number)⁠로 바꿔 보세요. 0이 아닌 모든 $a$가 단원이 됩니다. 소수 $p$는 1부터 $p - 1$까지의 어떤 수와도 1 말고는 공약수가 없기 때문입니다. 정리하면, 법 n에서 곱하기 a를 되돌릴 수 있는 것은 a와 n이 서로소일 때, 그리고 그때뿐이고, 법이 소수이면 0 말고는 모두 되돌릴 수 있습니다.

이 산수에 이름과 기호를 붙인 사람은 가우스입니다. 1801년, 스물네 살의 가우스는 『산술 연구』의 첫머리에서 $n$으로 나눈 나머지가 같은 두 수를 합동⁠(congruence)⁠이라 부르고, 등호를 닮은 기호 ≡로 적었습니다. 아래 식은 "a와 b는 법 n으로 합동이다"라고 읽습니다. 예를 들어 17과 5는 12로 나눈 나머지가 둘 다 5이고, 차이 12가 12로 나누어떨어지니 17 ≡ 5 (mod 12)입니다. 시계로 말하면 17시는 5시입니다.

이 관계는 등호처럼 세 성질을 모두 만족하는 동치관계⁠(equivalence relation)⁠입니다. 모든 수는 자기와 합동이고(반사), $a \equiv b$이면 $b \equiv a$이며(대칭), $a \equiv b$이고 $b \equiv c$이면 $a \equiv c$입니다(추이). 그래서 정수⁠(integer)⁠ 전체가 서로 겹치지 않는 $n$개의 덩어리로 나뉩니다. 나머지가 같은 수끼리 한 덩어리입니다. 법 3이면 {…, −3, 0, 3, 6, …}, {…, −2, 1, 4, 7, …}, {…, −1, 2, 5, 8, …}의 세 덩어리입니다.

모듈러 연산은 이 덩어리들을 하나의 수처럼 더하고 곱하는 일입니다. 어느 대표를 골라 계산해도 결과는 같은 덩어리에 떨어집니다. 법 3에서 해 봅시다. 4와 1은 같은 덩어리이고, 5와 2도 같은 덩어리입니다. 4 + 5 = 9와 1 + 2 = 3은 둘 다 나머지 0, 4 × 5 = 20과 1 × 2 = 2는 둘 다 나머지 2입니다. 일반적으로는 $a$ 대신 $a + sn$을, $b$ 대신 $b + tn$을 골라도 합은 $n$의 배수만큼, 곱은 $(at + bs + stn)n$만큼만 달라지기 때문입니다. 곱을 전개하면 $(a + sn)(b + tn) = ab + (at + bs + stn)n$이니까요.

가우스가 『산술 연구』를 낸 1801년에 그는 시야에서 사라진 소행성 세레스의 궤도⁠(orbit)⁠도 계산했고, 그해 말 천문학자들이 그가 예측한 자리 근처에서 세레스를 다시 찾으면서 유명해졌습니다(「잃어버린 소행성」).

3 · 되돌리는 수 찾기유클리드의 호제법

이 절의 물음은 이것입니다. 2절에서 곱하기 a는 a와 n이 서로소일 때 되돌릴 수 있다고 했습니다. 그렇다면 되돌리는 수 $a^{-1}$는 실제로 어떻게 찾을까? 법이 수백 자리여도 빨리 찾을 수 있어야 합니다.

법 26에서 7을 되돌리는 수는 15입니다. $7 \times 15 = 105 = 4 \times 26 + 1$이니까요. 수가 작으면 곱셈표를 뒤져 찾으면 됩니다. 하지만 이 글의 끝에서는 수백 자리의 법을 쓰게 됩니다. 그런 곱셈표는 우주에 있는 원자를 다 써도 적을 수 없습니다. 지름길은 기원전 300년 무렵 유클리드의 『원론』 7권에 이미 있습니다.

두 수의 최대공약수를 구하는 방법으로, 흔히 가장 오래된 알고리즘(정해진 단계를 차례로 따르면 답이 나오는 계산 절차)의 하나로 꼽힙니다. 큰 수를 작은 수로 나눕니다. 그다음에는 방금 나눈 작은 수를 나머지로 나누고, 나머지가 0이 될 때까지 이를 되풀이합니다. 마지막으로 나온 0 아닌 나머지가 최대공약수입니다. 26과 7로 해 봅시다.

마지막 0 아닌 나머지가 1이니 26과 7의 최대공약수는 1, 곧 둘은 서로소입니다. 이것이 통하는 까닭은 $x = qy + r$일 때 $x$와 $y$의 공약수가 곧 $y$와 $r$의 공약수이기 때문입니다($r = x - qy$이니까요). x와 y를 둘 다 나누는 수는 x − qy도 나누고, 거꾸로 y와 r을 둘 다 나누는 수는 x = qy + r도 나눕니다. 수는 작아져도 공약수는 그대로입니다.

그림으로는 가로 $n =$ , 세로 $a =$ 인 직사각형에서 가장 큰 정사각형을 떼어 내고, 남은 직사각형에서 같은 일을 되풀이하는 것입니다. 26 × 7 직사각형에서는 한 변이 7인 정사각형 세 개를 떼면 5 × 7이 남습니다. 26 = 3 × 7 + 5와 같은 일입니다. 그림 아래의 단계 버튼으로 한 번에 나눗셈 하나씩 진행하며, 떼어 낸 정사각형과 오른쪽 식을 함께 보세요.

왼쪽 열은 나눗셈입니다. 중요한 것은 오른쪽 열입니다. 나머지는 언제나 $n$과 $a$를 몇 배씩 더하고 뺀 모양으로 쓸 수 있습니다. 처음 두 수가 그렇고, 새 나머지는 앞의 두 수에서 "위의 것 − 몫 × 아래 것"으로 만들어지니 그 모양이 계속 이어집니다.

26과 7로 손으로 따라가 봅시다. 첫 나머지는 5 = 26 − 3 × 7입니다. 다음 나머지는 2 = 7 − 1 × 5이고, 여기에 방금 적은 5를 넣으면 2 = 7 − (26 − 3 × 7) = 4 × 7 − 26입니다. 마지막 1 = 5 − 2 × 2에 두 식을 넣으면 1 = (26 − 3 × 7) − 2 × (4 × 7 − 26) = 3 × 26 − 11 × 7입니다. 26의 배수 3 × 26은 나머지만 보면 0이니, −11 × 7이 법 26에서 1과 같습니다. −11에 26을 더한 15가 7의 역수입니다.

일반적으로 적으면, 마지막 0 아닌 나머지, 곧 최대공약수가 1이라면

입니다. $s \cdot n$은 $n$의 배수라서 나머지만 보면 사라지기 때문입니다. 이렇게 최대공약수를 $n$과 $a$의 정수배의 합으로 적은 식을, 18세기 프랑스 수학자 에티엔 베주의 이름을 따 베주 항등식이라고 부릅니다. 이 계산법은 확장 유클리드 호제법⁠(extended Euclidean algorithm)⁠이라고 합니다. 정수의 경우는 17세기 초 프랑스의 바셰 드 메지리아크가 이미 적었고, 베주는 이를 다항식⁠(polynomial)⁠으로 넓혔습니다.

이 방법은 빠릅니다. 나머지는 두 단계마다 절반 아래로 줄어듭니다. 26, 7, 5, 2, 1에서 보듯 한 칸 건너 나머지를 보면 26 → 5, 7 → 2, 5 → 1로 매번 절반보다 작아집니다. 그래서 나눗셈 횟수는 수의 크기가 아니라 자릿수를 따라 늡니다. 1844년 프랑스의 수학자 가브리엘 라메는 그 횟수가 작은 수를 10진법으로 적은 자릿수의 5배를 넘지 않음을 보였습니다. 수백 자리의 수라도 나눗셈 수천 번 안에 끝납니다.

라메는 가장 오래 걸리는 경우가 이웃한 피보나치 수라는 것도 보였습니다. 피보나치 수는 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …처럼 앞의 두 수를 더해 다음 수를 만드는 수열입니다. $n = 55$, $a = 34$로 해 보세요. 55 = 1 × 34 + 21, 34 = 1 × 21 + 13, …처럼 몫이 마지막 단계를 빼면 모두 1이라 정사각형이 한 개씩만 떨어져 나가고, 남은 직사각형의 가로세로 비가 한동안 황금비(약 1.618) 근처에 머뭅니다. 몫들을 차례로 적으면 $n/a$의 연분수⁠(continued fraction)⁠가 됩니다. 연분수란 분수를 '정수 + 1/(정수 + 1/(…))' 꼴로 풀어 쓴 것으로, 그 정수들이 바로 호제법의 몫입니다.

정리하면, 유클리드 호제법⁠(Euclidean algorithm)⁠은 나눗셈을 되풀이해 최대공약수를 구하고, 그 과정을 거꾸로 적으면 역수까지 얻습니다. 게다가 자릿수에 비례하는 횟수면 끝납니다.

1부터 $N$까지에서 두 수를 고르게 뽑으면, 둘이 서로소일 확률은 $N$이 커질수록 $6/\pi^2 \approx 0.608$에 다가갑니다. 정수 전체에서 '고르게' 뽑을 수는 없으니 이렇게 극한⁠(limit)⁠으로 말해야 정확합니다. 두 수가 함께 소수 $p$의 배수일 확률은 약 $1/p^2$이고, 모든 소수에 대해 이를 피할 확률을 곱하면 $\prod_p (1 - 1/p^2)$입니다($\prod_p$는 '모든 소수 p에 대해 곱하라'는 기호입니다). 이 곱이 바젤 문제⁠(Basel problem)⁠의 답 $\pi^2/6$의 역수라서, 원과 관계없어 보이는 곳에 π가 나옵니다.

되돌리는 수를 찾는 이 계산은 유럽 밖에서 먼저 쓸모를 얻었습니다. 쓰인 곳은 천문과 달력이었습니다. 499년 오늘날 인도 파트나 근처의 쿠수마푸라에서 아리아바타가 쓴 천문서 『아리아바티야』에는, $ax + by = c$를 만족하는 정수 $x$, $y$를 찾는 방법이 짧게 실려 있습니다. 뒤의 주석가들은 이것을 '쿠타카⁠(kuttaka)⁠', 곧 '잘게 빻기'라 불렀습니다. 큰 두 수를 나눗셈으로 거듭 줄여 가는 모양이 이 절의 호제법과 같습니다. 인도의 천문학자들은 이것으로 행성들이 몇 바퀴 돌았는지, 기준일에서 며칠이 지났는지를 거꾸로 계산했습니다. 중국에서는 3–5세기 무렵의 『손자산경⁠(Sunzi Suanjing)⁠』이 "3으로 나누면 2, 5로 나누면 3, 7로 나누면 2가 남는 수는?"이라고 물었습니다(답은 23입니다). 1247년 남송의 관리 진구소는 『수서구장』에서 이런 문제를 일반적으로 푸는 방법을 적었고, 그 핵심 단계에 '대연구일술', 곧 '1을 구하는 방법'이라는 이름을 붙였습니다. 서로소인 $a$와 $m$이 주어지면 $a$에 곱해 $m$으로 나눈 나머지가 1이 되는 수, 곧 이 절에서 구한 역수를 찾는 절차입니다. 진구소는 이 방법을 천문 관청의 역법 계산가들에게서 배웠다고 전합니다. 6절에서 쓰는 중국인의 나머지 정리⁠(Chinese remainder theorem)⁠라는 이름도 이 전통에서 왔습니다.

4 · 거듭제곱의 고리페르마 소정리⁠(Fermat's little theorem)⁠

이 절의 물음은 이것입니다. 같은 수를 나머지 산수로 거듭 곱하면 어떤 무늬가 생길까? 여기서 나오는 규칙 하나, 페르마 소정리가 5–6절의 두 암호를 떠받칩니다.

이제 같은 수를 거듭 곱해 봅시다. $a^k$는 a를 k번 곱한 수입니다('a의 k제곱'). $a, a^2, a^3, \dots$을 $n$으로 나눈 나머지는 시계 위에서 어떻게 움직일까요? 법 11에서 2로 손으로 해 봅시다. 매번 2를 곱하고 11로 나눈 나머지만 남기면 1, 2, 4, 8, 16 → 5, 10, 20 → 9, 18 → 7, 14 → 3, 6, 12 → 1입니다. 열 번 곱하니 1로 돌아왔습니다.

그림으로 따라가 봅시다. 법 $n =$ , 밑 $a =$ 입니다. $a^k$를 $k =$ 까지 따라가 봅니다. 왼쪽 그림에서는 곱할 때마다 옮겨 가는 칸을, 오른쪽 그림에서는 여러 a가 1로 돌아오기까지 몇 번 곱해야 하는지를 봅니다. ▶ 1부터 곱해 가기

왜 반드시 돌아올까요? 시계에는 칸이 $n$개뿐입니다. 그런데 $1, a, a^2, \dots, a^n$은 $n + 1$개이니, 어떤 칸은 두 번 밟게 됩니다. 비둘기 n + 1마리가 비둘기집 n개에 들어가면 어느 집에는 두 마리가 들어가는 것과 같은 이치입니다(비둘기집 원리⁠, pigeonhole principle⁠). 한번 밟은 칸에 다시 오면 그다음부터는 같은 길을 되풀이하니, 길은 언젠가 고리가 됩니다.

그런데 그 고리가 왜 하필 출발점 1로 돌아올까요? $a$가 단원이면 곱하기 $a$를 되돌릴 수 있습니다. $a^i \equiv a^j$이면($i < j$) 양쪽에 $a^{-i}$(a의 역수를 i번 곱한 것)를 곱해 $1 \equiv a^{j-i}$를 얻습니다. 곧 j − i번 곱하면 이미 1에 와 있었다는 뜻입니다. 그래서 처음으로 겹치는 칸은 출발점 1입니다. 고리에 꼬리가 없습니다.

$n = 12$, $a = 2$로 바꿔 보세요. 2는 12와 서로소가 아니라서 되돌릴 수 없습니다. 길은 1로 돌아오지 못하고, 꼬리 달린 ρ 모양으로 어딘가에 갇힙니다.

$a$를 거듭 곱해 처음으로 1에 돌아올 때까지 곱한 횟수를 $a$의 위수라고 합니다. 법 7에서 2는 2, 4, 1로 세 번 만에 돌아오니 위수가 3입니다. 법 11에서 2의 위수는 앞에서 본 대로 10입니다.

오른쪽 그림은 모든 $a$의 위수를 한꺼번에 보여 줍니다(단원이 아닌 $a$는 1로 돌아오지 못하니 막대가 없습니다). 막대들은 아무 높이에서나 멈추지 않습니다. 모두 $\varphi(n)$의 약수(옅은 가로선)에서 멈춥니다. 법 11이면 φ(11) = 10이고, 위수는 1, 2, 5, 10 가운데 하나입니다. 1의 위수는 1, 10의 위수는 2(10 × 10 = 100 = 9 × 11 + 1), 3의 위수는 5, 2의 위수는 10입니다.

까닭은 곱하기 $a$가 단원 전체를 똑같은 길이의 고리 여러 개로 나누기 때문입니다. 법 11에서 3으로 해 보면, 1에서 출발한 고리는 1 → 3 → 9 → 5 → 4 → 1이고, 이 고리에 없는 2에서 출발한 고리는 2 → 6 → 7 → 10 → 8 → 2입니다. 길이 5짜리 고리 두 개가 단원 열 개를 겹침 없이 나눠 가집니다.

일반적으로 적으면 이렇습니다. 단원 $u$에서 출발한 고리 $u, ua, ua^2, \dots$는 1에서 출발한 고리의 모든 칸에 $u$를 곱한 것이라 길이가 같습니다(위의 예에서 2에서 출발한 고리는 1에서 출발한 고리에 2를 곱한 것입니다). 또 두 고리가 한 칸이라도 겹치면 그 칸에서부터 똑같은 길을 도니 두 고리는 통째로 같습니다. 결국 단원 $\varphi(n)$개를 같은 길이의 고리들이 겹침 없이 나눠 가지니, 고리의 길이는 $\varphi(n)$의 약수⁠(divisor)⁠일 수밖에 없습니다. 그러니 $\varphi(n)$번 곱하면 어느 단원이든 1로 돌아옵니다. 고리의 길이가 φ(n)의 약수이니 φ(n)번 곱하는 것은 고리를 정확히 몇 바퀴 도는 것이고, 그러면 출발점 1에서 멈추기 때문입니다. 아래 식의 세로 막대 ∣는 '왼쪽이 오른쪽을 나눈다'는 뜻입니다.

이것이 오일러의 정리입니다. $a$와 $n$이 서로소이면 $a^{\varphi(n)} \equiv 1 \pmod n$입니다. 말로 읽으면 "a를 φ(n)번 곱해 n으로 나누면 나머지가 1"입니다. 서로소라는 조건은 빼면 안 됩니다. 위의 $n = 12$, $a = 2$처럼 1로 영영 돌아오지 않는 수가 생깁니다.

$n$이 소수 $p$이면 $\varphi(p) = p - 1$이므로(1부터 p − 1까지가 모두 p와 서로소입니다), $p$의 배수가 아닌 모든 $a$에 대해 $a^{p-1} \equiv 1 \pmod p$가 됩니다. 이것이 페르마 소정리입니다. 예를 들어 p = 7, a = 3이면 3⁶ = 729 = 104 × 7 + 1이고, 앞에서 본 대로 법 11에서 2¹⁰도 1입니다. 정리하면, 나머지 산수에서 단원을 φ(n)번 곱하면 반드시 1로 돌아오고, 법이 소수 p이면 p − 1번이면 됩니다.

$n = 11$에서는 2, 6, 7, 8이 노란 막대입니다. 위수가 φ(11) = 10까지 닿는 수들입니다. 이런 $a$를 원시근이라 합니다. 원시근의 거듭제곱은 모든 단원을 한 바퀴에 돕니다. 법 11에서 2의 거듭제곱 1, 2, 4, 8, 5, 10, 9, 7, 3, 6이 1부터 10까지를 한 번씩 거치는 것을 앞에서 보았습니다.

그러면 단원끼리의 곱셈은 지수의 덧셈이 됩니다. $a^i \cdot a^j = a^{i+j}$이고, 지수는 $\varphi(n)$에서 다시 0으로 감깁니다. 법 11에서 8 × 5를 계산하는 대신, 8 = 2³, 5 = 2⁴이니 지수를 더해 2⁷ = 7을 얻습니다. 실제로 8 × 5 = 40 = 3 × 11 + 7입니다. 이것은 단위원(반지름이 1인 원)을 $\varphi(n)$등분한 1의 거듭제곱근⁠(roots of unity)⁠을 곱하는 일, 곧 각도를 더해 회전⁠(rotation)⁠하는 일(복소수 곱셈⁠(complex multiplication)⁠)과 똑같은 구조입니다. 원을 φ(n)등분한 눈금 위에서, 곱하기가 '눈금 몇 칸 더 돌기'가 되는 것입니다.

가우스는 소수인 법에는 원시근이 늘 있음을 증명했습니다. 원시근이 있는 법은 1, 2, 4와 홀수 소수 $p$의 거듭제곱 $p^k$, 그 두 배 $2p^k$뿐입니다. $n = 8$이나 $12$에는 노란 막대가 하나도 없는 것도 확인해 보세요. 두 경우 모두 $\varphi(n) = 4$인데, 단원의 위수는 1 아니면 2입니다.

1640년 페르마는 이 사실을 수학 애호가 프레니클 드 베시에게 보낸 편지에 적었습니다. 증명은 보내지 않고, 너무 길어질까 걱정된다는 말만 덧붙였습니다. 처음 출판된 증명은 1736년 무렵 오일러의 것입니다. 다만 라이프니츠는 1683년 이전에 거의 같은 증명을 원고로 남겼고, 이 원고는 1894년에야 하노버 도서관의 유고에서 주목받았습니다. 오일러는 1763년에 발표한 논문에서 이 정리를 소수가 아닌 법으로 넓혔습니다. 이때 쓴 개수 $\varphi(n)$에 오늘날의 기호 φ를 붙인 사람은 가우스입니다.

페르마가 정리를 편지에 적은 데는 까닭이 있습니다. 학술지가 아직 없었습니다. 최초의 학술지인 파리의 『주르날 데 사방』과 런던의 『철학 회보』가 나온 것은 페르마가 죽은 해인 1665년입니다. 그 전까지 유럽의 학자들은 편지로 결과를 나누었고, 그 한가운데에 파리 미니모회 수도원의 수도사 마랭 메르센이 있었습니다. 그는 툴루즈의 페르마, 네덜란드의 데카르트, 이탈리아의 학자들에게서 온 편지를 베껴 다른 이들에게 돌렸습니다.

같은 길로 국가의 비밀도 오갔습니다. 1628년 툴루즈 동쪽 레알몽을 포위한 왕군이 위그노(프랑스의 개신교도)의 암호 편지를 가로챘을 때 앙투안 로시뇰이 이를 풀었다고 전합니다. 그 뒤 로시뇰은 루이 13세의 재상 리슐리외 추기경과 루이 14세의 해독가가 되었습니다. 수학을 나르던 편지와 해독가의 책상에 오르던 편지는 같은 우편로를 탔습니다.

5 · 열쇠를 건네지 않고 맞추기디피–헬먼

이 절의 물음은 머리말의 물음 그대로입니다. 한 번도 만난 적 없는 두 사람이, 모두가 엿듣는 통신망에서 같은 비밀 수를 맞출 수 있을까?

1970년대에 컴퓨터 통신망이 커지면서 열쇠를 건네는 문제는 훨씬 급해졌습니다. 사용자가 1,000명이면 짝은 약 50만 개입니다. 1,000명이 저마다 나머지 999명과 짝을 지으면 1,000 × 999이고, 한 짝을 두 번 셌으니 2로 나누면 499,500입니다. 그 모든 짝이 미리 만나서 열쇠를 나눌 수는 없습니다. 그때까지 암호 연구는 거의 정보기관 안의 일이었습니다. 1976년 스탠퍼드의 휫필드 디피와 마틴 헬먼은 공개 학술지에 실은 논문을 이렇게 시작했습니다.

우리는 오늘 암호학 혁명의 문턱⁠(threshold)⁠에 서 있다.— 휫필드 디피·마틴 헬먼, 「암호학의 새로운 방향」(1976)

그들이 찾은 재료는 한쪽으로는 쉽고 거꾸로는 어려운 계산입니다. 거듭제곱이 그렇습니다. $2^{a} \bmod p$('2의 a제곱을 p로 나눈 나머지')는 제곱을 거듭하면 지수가 수백 자리여도 곱셈 몇천 번이면 구해집니다. 예컨대 $2^{64}$은 2를 63번 곱할 필요 없이 2 → 4 → 16 → 256 → …처럼 여섯 번 제곱하면 되고, 매번 나머지만 남기니 수가 커지지도 않습니다. 지수가 64처럼 딱 떨어지지 않아도 됩니다. 2²³이라면 23 = 16 + 4 + 2 + 1이니, 제곱을 거듭해 얻은 2¹⁶, 2⁴, 2², 2¹을 곱하면 됩니다.

하지만 결과만 보고 지수 $a$를 되찾는 문제(이산로그⁠, discrete logarithm⁠)는 다릅니다. 법 101에서 2를 몇 번 곱해야 53이 되는지 물으면, 1번, 2번, 3번, …을 차례로 시험하는 것 말고는 뾰족한 길이 보이지 않습니다. 물론 하나씩 다 시험하는 것보다 나은 방법들은 있습니다. 그래도 거듭제곱처럼 자릿수가 늘어도 계산량이 자릿수의 거듭제곱 정도로만 느는 방법은 알려져 있지 않습니다. 아래 그림은 의 값을 $k = 1$부터 100까지 찍은 것입니다. 식을 눌러 곱셈과 거듭제곱을 바꿔 보면 차이가 보입니다.

곱셈을 고르면 점들이 가지런한 두 줄로 늘어섭니다. 거듭제곱을 고르면 점들이 흩뿌려집니다. 도청자는 노란 점선의 높이 A를 알지만, 그 높이의 점이 가로 어디에 있는지는 하나씩 확인해 볼 수밖에 없습니다.

디피–헬먼 열쇠 교환은 이렇습니다. 소수 $p = 101$과 밑 $g = 2$는 모두에게 공개합니다. 2는 법 101의 원시근이어서, 그 거듭제곱이 1부터 100까지 모든 값을 한 번씩 거칩니다. 암호학에서 흔히 쓰는 이름대로 두 사람을 앨리스와 밥이라 합시다. 두 사람은 각자 비밀 수를 하나씩 고릅니다. 앨리스의 비밀은 $a =$ , 밥의 비밀은 $b =$ 입니다. 각자 $g$를 제 비밀 수만큼 거듭제곱한 결과 A와 B를 공개 통신망으로 보냅니다. 그리고 받은 수를 다시 제 비밀 수만큼 거듭제곱합니다. 두 숫자를 끌어 비밀 수를 바꿔 보고, 아래 식 둘째 줄의 두 결과가 늘 같은지 보세요.

손으로 확인할 수 있게 더 작은 수로 한 번 해 봅시다. 공개된 법이 11, 밑이 2이고, 앨리스의 비밀이 3, 밥의 비밀이 4라고 합시다. 앨리스는 2³ = 8을, 밥은 2⁴ = 16을 11로 나눈 나머지 5를 보냅니다. 앨리스는 받은 5를 세제곱해 125 = 11 × 11 + 4에서 4를 얻고, 밥은 받은 8을 네제곱해 4096 = 372 × 11 + 4에서 역시 4를 얻습니다. 도청자는 8과 5를 보았습니다. 하지만 열쇠 4를 얻는 알려진 방법은 모두 비밀 3이나 4를 되찾는 데서 출발합니다.

두 사람의 결과가 같은 이유는 $(g^b)^a = g^{ab} = (g^a)^b$이기 때문입니다. 거듭제곱을 거듭제곱하면 지수끼리 곱해진다는 규칙입니다. 위의 예라면 (2⁴)³과 (2³)⁴이 모두 2¹²입니다. 나머지만 남겨도 이 규칙은 그대로입니다. 둘은 한 번도 비밀을 보내지 않았는데 같은 수 $K$를 얻었고, 이제 이 수를 열쇠로 쓰면 됩니다. 도청자는 $p, g, A, B$를 모두 보았습니다. 하지만 $A$와 $B$에서 $K$를 곧바로 만드는 방법은 알려져 있지 않고, 알려진 공격은 $a$나 $b$를 되찾는 데서 출발합니다. 이산로그라는 이름은 보통의 로그에서 왔습니다. 실수⁠(real number)⁠ 위의 지수함수⁠(exponential function)⁠는 매끄럽게 커지니 로그로 쉽게 되돌릴 수 있습니다. 하지만 나머지를 취하는 순간 값이 시계를 여러 바퀴 돌아 흩어지고, 되돌리기가 어려워집니다.

흔히 이것으로 통신이 완전히 안전해진다고 생각하지만, 여기서 막은 것은 엿듣기만 하는 도청자입니다. 중간에 끼어들어 앨리스에게는 밥인 척, 밥에게는 앨리스인 척하는 공격자는 두 사람과 각각 따로 열쇠를 맞출 수 있습니다. 그래서 실제로는 상대가 진짜인지 확인하는 전자서명⁠(digital signature)⁠을 함께 씁니다.

정리하면, 디피–헬먼 열쇠 교환은 "거듭제곱은 쉽고 지수를 되찾기는 어렵다"는 비대칭과 "거듭제곱의 순서를 바꿔도 결과가 같다"는 규칙 두 가지로, 비밀을 보내지 않고 비밀을 맞춥니다.

남은 문제가 하나 있었습니다. 디피와 헬먼은 누구나 잠글 수 있지만 한 사람만 열 수 있는 자물쇠, 곧 공개키 암호라는 개념을 논문에서 내놓았습니다. 하지만 그런 자물쇠를 만들 구체적인 함수⁠(function)⁠는 찾지 못했습니다. 비슷한 시기에 버클리의 학생이던 랠프 머클도 독자적으로 공개 통신로에서 열쇠를 맞추는 방법을 연구하고 있었습니다.

머클의 생각은 처음에 두 번 거절당했습니다. 1974년 컴퓨터 보안 수업의 과제 제안서로 냈을 때 담당 교수는 받아들이지 않았고, 학술지에 보낸 첫 원고도 심사에서 돌아왔습니다. 머클은 수업을 그만두고도 연구를 이어 갔고, 논문 「안전하지 않은 통로에서의 안전한 통신」은 1978년에야 실렸습니다. 공개적인 연구에는 다른 종류의 압력도 있었습니다. 1977년 여름, 국가안보국(NSA) 직원 조지프 마이어는 개인 자격이라며 전기전자공학회(IEEE)에 편지를 보내, 암호 논문을 공개 학회에서 발표하면 무기 수출 규제를 어길 수 있다고 경고했습니다. 학회는 그해 10월 코넬 대학의 정보 이론 심포지엄을 예정대로 열었고, 몇몇 대학원생의 논문은 법적 부담을 덜려고 지도 교수인 헬먼이 대신 발표했습니다. 정부의 조치는 없었습니다.

6 · 누구나 잠그고, 한 사람만 연다RSA

이 절의 물음은 이것입니다. 누구나 잠글 수 있지만 한 사람만 열 수 있는 자물쇠를 어떻게 만들까?

1977년, MIT의 세 사람 로널드 라이베스트, 아디 샤미르, 레너드 애들먼이 그 자물쇠를 찾았습니다. 세 사람의 머리글자를 딴 RSA 암호⁠(RSA cryptosystem)⁠입니다. 발명자들의 회고에 따르면 라이베스트와 샤미르가 방식을 내놓으면 애들먼이 깨는 일이 몇 달 동안 되풀이되었고, 그렇게 무너진 방식이 40개를 넘었습니다. 그해 4월 한 학생의 집에서 유월절 저녁을 보내고 돌아온 밤, 잠들지 못한 라이베스트가 새 착상을 밤새 논문 꼴로 적었습니다. 이번에는 애들먼도 깨지 못했다고 합니다.

재료는 이 글에서 이미 모두 만들었습니다. 4절의 오일러 정리⁠(Euler's theorem)⁠와 3절의 역수 계산입니다.

먼저 두 소수를 몰래 고릅니다. 여기서는 $p =$ , $q =$ 입니다(끌면 소수만 골라 멈춥니다). 그 곱 $n = pq$와 지수 $e$는 세상에 공개합니다. 지금 $e =$ 입니다. 여기서 $e$는 자연로그⁠(natural logarithm)⁠의 밑이 아니라 '암호화(encryption)'의 머리글자이고, 뒤에 나올 $d$는 '복호화(decryption)'의 머리글자입니다. 누구든 메시지 $m$을 $c = m^e \bmod n$으로 잠글 수 있습니다. 지금 메시지는 $m =$ 입니다. 여는 열쇠 $d$는 $e$를 법 $\varphi(n)$에서 되돌리는 수이고, 주인만 압니다. 2절의 규칙대로 이런 $d$는 $e$가 $\varphi(n)$과 서로소일 때만 있습니다.

처음 값으로 따라가 봅시다. p = 11, q = 17이면 n = 187이고, φ(n)은 뒤에서 볼 공식으로 10 × 16 = 160입니다. e = 7을 법 160에서 되돌리는 수는 23입니다. 7 × 23 = 161 = 160 + 1이니까요(3절의 호제법으로 찾습니다). 메시지 m = 42를 잠그면 $42^7$을 187로 나눈 나머지 15가 암호문 c입니다. 주인은 15를 23제곱해 187로 나눈 나머지를 구하고, 그 값은 정확히 42입니다. 숫자들을 끌어 바꾸면 아래 식이 새 값으로 다시 계산됩니다.

왜 열릴까요? $d$는 $ed = 1 + k\,\varphi(n)$이 되도록 고른 수입니다(k는 어떤 자연수입니다. 위의 예에서는 7 × 23 = 1 + 1 × 160이니 k = 1). 그러면 오일러 정리 $m^{\varphi(n)} \equiv 1$ 덕분에

입니다. 한 줄씩 읽으면, 잠갔다 여는 것은 m을 ed번 곱하는 것이고, ed는 φ(n)의 몇 배에 1을 더한 수이며, m을 φ(n)번 곱할 때마다 1이 곱해지는 셈이니 m 하나만 남는다는 것입니다. $m$이 $p$나 $q$의 배수여서 오일러 정리를 바로 쓸 수 없을 때도, $p$와 $q$로 따로 나눠 따져 보면(중국인의 나머지 정리) 같은 결론이 나옵니다. 이 정리는 p로 나눈 나머지와 q로 나눈 나머지를 알면 pq로 나눈 나머지가 하나로 정해진다는 것이라, 두 소수에서 각각 m으로 돌아오면 n = pq에서도 m으로 돌아옵니다.

왼쪽 그림에서 점들을 보세요. $e$가 $\varphi(n)$과 서로소이면, 어느 세로줄에도, 어느 가로줄에도 점이 정확히 하나씩 있습니다. 잠그기는 $0, 1, \dots, n-1$을 뒤섞는 전단사이고, 그 모습은 무작위처럼 보입니다. 열기는 이 뒤섞기를 되돌리는 함수입니다. 역함수⁠(inverse function)⁠의 그래프가 원래 그래프를 대각선에 비춘 모양이듯, 복호화는 노란 점을 대각선 건너편으로 옮깁니다. $p = 11$, $q = 17$일 때 $e = 5$처럼 $\varphi(n) = 160$과 서로소가 아닌 지수를 고르면 한 가로줄에 여러 점이 몰립니다. 2절의 곱셈 암호에서 본 것과 같은 고장입니다.

자물쇠의 비밀은 $d$를 구하려면 $\varphi(n)$이 필요하다는 데 있습니다. $n = pq$이면 1부터 $n$까지의 수 중 $p$의 배수 $q$개와 $q$의 배수 $p$개를 빼고, 두 번 뺀 $n$ 하나를 다시 더해 $\varphi(n) = pq - p - q + 1 = (p-1)(q-1)$입니다(포함배제 원리⁠, inclusion–exclusion principle⁠). n = 187이면 187 − 17 − 11 + 1 = 160입니다(11의 배수 17개, 17의 배수 11개, 둘 다의 배수인 187 하나). $p$와 $q$를 알면 이 계산은 한 줄이지만, 공개된 것은 $n$뿐입니다.

공격자에게 알려진 가장 곧은 길은 $n$을 소인수분해⁠(prime factorization)⁠하는 것입니다. 거꾸로 $\varphi(n)$을 알아내면 $p + q = n - \varphi(n) + 1$에서 $p$와 $q$가 곧바로 나옵니다. 두 수의 합과 곱(n)을 알면 두 수는 이차방정식 하나로 정해지기 때문입니다. 위의 예라면 p + q = 187 − 160 + 1 = 28이고, 곱해서 187, 더해서 28인 두 수는 11과 17입니다. 그러니 $\varphi(n)$을 구하는 일은 인수분해만큼 어렵습니다.

장난감 크기에서는 이렇게 쉽습니다. 실제로 흔히 쓰는 $n$은 2048비트, 10진법으로 617자리입니다. 오른쪽 그림의 자릿수를 끌어 바꿔 보세요. 지금은 자리입니다.

곱하기는 학교에서 배운 방식으로 해도 자릿수의 제곱에 비례하는 계산이라, 수백 자리여도 순식간입니다. 작은 수부터 차례로 나누기는 $\sqrt n$(제곱하면 n이 되는 수)번쯤 나눠 봐야 합니다. 두 소인수 가운데 작은 쪽이 $\sqrt n$ 이하이기 때문입니다. n의 자릿수가 하나 늘면 n은 10배, $\sqrt n$은 약 3.16배($\sqrt{10}$)가 되니 시간이 약 3배씩 늘어나고, 금세 그림 밖으로 솟구칩니다. 지금 알려진 가장 빠른 일반적인 방법은 수체 체⁠(number field sieve)⁠라는 알고리즘입니다. 이름의 '체'는 에라토스테네스의 체⁠(sieve of Eratosthenes)⁠처럼 수많은 후보를 걸러 내는 단계에서 왔습니다. 이 방법의 비용은 차례로 나누기보다 훨씬 느리게 늘지만, 자릿수의 어떤 거듭제곱보다도 빨리 커집니다. 617자리라면 초당 $10^{18}$번 계산하는 컴퓨터로 1년을 돌려도(그림의 회색 점선) 한참 모자랍니다. 곱하기는 쉽고 되돌리기는 어렵다는 이 비대칭이 자물쇠입니다.

다만 이 비대칭은 증명된 사실이 아닙니다. 소인수분해에 빠른 방법이 정말 없는지는 아무도 모릅니다. 1994년 미국의 수학자 피터 쇼어는, 양자역학의 원리로 계산하는 양자 컴퓨터⁠(quantum computer)⁠가 충분히 크게 만들어진다면 소인수분해와 이산로그를 빠르게 풀 수 있음을 보였습니다.

그래서 요즘에는 양자 컴퓨터로도 풀기 어렵다고 여겨지는 다른 수학 문제에 기댄 새 암호로 옮겨 가고 있습니다. 대표적인 것이 격자 문제입니다. 바둑판의 교차점처럼 규칙적으로 늘어선 점들(격자)이 수백 차원 공간에 있을 때, 주어진 점에 가장 가까운 격자점⁠(lattice point)⁠을 찾는 것 같은 문제입니다. 2차원에서는 쉽지만 차원이 수백이면 양자 컴퓨터로도 빠른 방법이 알려져 있지 않습니다. 미국 국립표준기술연구소(NIST)는 2016년 말 전 세계의 암호학자들에게 후보를 공모해 8년 동안 공개적으로 깨 보게 했습니다. 그리고 2024년 8월 격자 문제⁠(lattice problem)⁠에 기댄 열쇠 교환 방식(ML-KEM) 등을 새 표준으로 정했습니다. 공모 도중에 유력한 후보 몇몇이 실제로 깨졌습니다. 방식을 모두 공개하고 모두가 공격하게 하는 것이 오늘날 암호를 믿게 되는 방법입니다(8절의 케르크호프스).

정리하면, RSA는 두 소수의 곱 n과 지수 e를 공개하고, 여는 지수 d는 φ(n) = (p − 1)(q − 1)을 아는 사람만 계산할 수 있게 한 자물쇠입니다. φ(n)을 알려면 n을 소인수분해해야 하고, 그것이 어렵다고 믿어집니다.

남은 준비물이 하나 있습니다. 수백 자리의 소수는 어디서 구할까요? 소수가 무한히 많다는 사실은 유클리드도 증명했습니다. 얼마나 흔한지는 소수 정리⁠(prime number theorem)⁠가 알려 줍니다. $x$ 근처의 넓은 구간에서 수를 고르게 하나 뽑으면, 소수일 확률은 약 $1/\ln x$입니다. ln은 자연로그로, 수가 10배 커질 때마다 약 2.3씩 늘어나는 느린 함수입니다. 1024비트(309자리) 수라면 약 2.3 × 309 ≈ 710, 곧 $\ln x \approx 710$이니, 홀수만 골라 시험하면 평균⁠(mean)⁠ 355개쯤에 하나꼴로 소수가 나옵니다. 짝수를 빼면 소수일 확률이 두 배가 되기 때문입니다. '평균 몇 번째에 나오는가'를 기댓값⁠(expected value)⁠이라 합니다.

소수인지 확인하는 데는 페르마의 정리를 뒤집어 씁니다. $n$이 소수라면 $n$의 배수가 아닌 $a$에 대해 $a^{n-1} \equiv 1$이어야 하니, $a^{n-1} \not\equiv 1 \pmod n$이면 $n$은 확실히 소수가 아닙니다. 예를 들어 n = 15, a = 2이면 2¹⁴를 15로 나눈 나머지가 4이니, 15를 나눠 보지 않고도 소수가 아님을 압니다. 하지만 이 시험을 통과했다고 소수라는 보장은 없습니다. $n$과 서로소인 모든 밑에서 시험을 통과하는 합성수(카마이클 수⁠, Carmichael number⁠)가 드물게 있고, 가장 작은 것이 $561 = 3 \cdot 11 \cdot 17$입니다. 흔히 이 시험을 통과하면 소수라고 생각하지만, 561은 통과하는데도 합성수입니다.

그래서 실제로는 이를 보완한 밀러–라빈 판정법을 씁니다. 합성수⁠(composite number)⁠가 무작위로 고른 밑 하나의 시험을 통과할 확률은 $1/4$ 이하라서, 밑을 바꿔 $k$번 되풀이하면 틀릴 확률이 $(1/4)^k$ 아래로 내려갑니다. 이렇게 동전 던지기를 계산에 섞는 방법을 무작위 알고리즘⁠(randomized algorithm)⁠이라고 부릅니다.

'어렵다고 믿는다'와 '어렵다'의 차이는 공개키 암호⁠(public-key cryptography)⁠의 첫 세대에서 이미 드러났습니다. 1978년 머클과 헬먼은 RSA와 다른 자물쇠를 내놓았습니다. 수 여러 개 가운데 몇 개를 골라 주어진 합을 만드는 '배낭 문제⁠(knapsack problem)⁠'는 일반적으로 어렵다고 알려져 있었습니다. 두 사람은 주인만 아는 쉬운 배낭 문제를 곱셈과 나머지로 감춰, 어려운 문제처럼 보이게 했습니다. 그러나 1982년 샤미르는 이렇게 감춘 배낭에는 일반적인 배낭 문제에 없는 규칙이 남아 있어서 비밀 열쇠 없이 빠르게 풀린다는 것을 보였습니다(논문은 1984년). 문제 전체가 어렵다고 해서 그 문제의 특별한 경우까지 어렵다는 보장은 없었던 것입니다. 증명이 기대던 가정이 실제로는 서로 다른 두 가지였다는 이 구도는 「틀린 증명이 만든 수학」의 오류들과 닮았습니다.

7 · 수학 밖으로푸는 사람들

이 절은 수학을 잠시 내려놓고 사람들을 봅니다. 암호를 푸는 일은 누가, 무엇을 위해 해 왔고, 그 일이 언제 수학자의 일이 되었을까?

1절에서 본 대로 암호의 역사는 만드는 쪽과 푸는 쪽의 경쟁입니다. 그 경쟁은 늘 권력이 있는 곳에서 벌어졌습니다. 르네상스 이탈리아의 도시국가들은 서로의 궁정에 대사를 상주시키고 암호 편지로 보고를 받았습니다. 베네치아는 1506년 무렵 조반니 소로를 공식 암호 비서로 두고 가로챈 외국 편지를 풀게 했습니다.

해독이 한 여왕의 목숨을 가른 곳은 1586년 잉글랜드입니다. 차틀리 저택에 갇혀 있던 스코틀랜드 여왕 메리는 맥주통에 숨겨 드나든 암호 편지로 엘리자베스 1세 암살 계획(배빙턴 음모)에 동의했습니다. 편지는 모두 엘리자베스의 국무장관 프랜시스 월싱엄의 첩보망이 가로챘고, 해독가 토머스 펠리프스가 풀었습니다. 메리의 암호는 글자 바꾸기에, 자주 쓰는 낱말을 뜻하는 기호 몇십 개를 더한 것이어서, 알킨디의 빈도 분석으로 충분했습니다. 메리는 이 편지를 증거로 재판을 받고 1587년 처형되었습니다.

전신이 퍼지자 암호로 오가는 전문의 규모가 달라졌습니다. 1914년 전쟁이 나자 영국은 독일의 대서양 해저 전신선을 끊었고, 독일의 외교 전문은 영국을 거치는 선로로 돌아가야 했습니다. 1917년 1월 독일 외무장관 치머만은 멕시코 주재 대사에게 전보를 보냈습니다. 미국이 참전하면 멕시코와 동맹을 맺고 텍사스·뉴멕시코·애리조나를 되찾게 돕겠다는 제안이었습니다. 이 전보는 런던 해군본부의 해독반 '40호실'에서 풀렸습니다. 미국이 4월에 참전한 데에는 경고 없이 중립국의 배까지 공격하겠다는 독일의 무제한 잠수함 작전과 함께, 3월 초 미국 신문에 실린 이 전보도 힘을 보탰습니다.

2차 세계대전에서 해독은 수학자들의 일이 되었습니다. 독일군의 에니그마⁠(Enigma)⁠는 글자를 하나 칠 때마다 회전자(가장자리의 접점 26개를 뒤섞인 배선으로 이은 바퀴)가 돌아 치환이 바뀌는 기계였습니다. 원래 배선이 $R$인 회전자가 $k$칸 돌아가 있으면, 그 배선은 한 칸 밀기 $P$를 앞뒤로 붙인 $P^{-k} R\, P^{k}$가 됩니다. 글자를 $k$칸 밀어 원래 배선에 넣고, 나온 글자를 다시 $k$칸 되돌린다는 뜻입니다. 식은 오른쪽부터 읽고, $P^{k}$는 한 칸 밀기를 k번, $P^{-k}$는 한 칸 되돌리기를 k번 하라는 뜻입니다. 1절의 카이사르 이동과 2절의 전단사, 곧 글자들을 빠짐없이 서로 맞바꾸는 규칙인 치환을 이어 붙인 것입니다.

그래서 이 기계를 처음 뚫은 것도 치환의 수학이었습니다. 1932년 12월 바르샤바의 폴란드 암호국에서 수학자 마리안 레예프스키는 치환의 순환 구조⁠(cycle type)⁠에 관한 정리와 프랑스 정보부가 얻어 온 문서를 함께 써서 회전자의 배선을 재구성했습니다. 어떤 치환이든 A → F → C → A처럼 글자들이 돌아가는, 서로 겹치지 않는 고리(순환)들로 쪼개집니다. 그 정리는, 치환 $R$ 앞뒤에 어떤 치환 $P$와 그 역 $P^{-1}$을 붙여 $P^{-1} R\, P$ 꼴로 바꾸어도 고리들의 길이 구성(예: 길이 10짜리 둘, 길이 3짜리 둘)은 변하지 않는다는 것입니다. 글자의 이름표만 바꿔 붙일 뿐, 누가 누구를 따라 도는 모양은 그대로이기 때문입니다. 레예프스키는 가로챈 암호문에서 이런 고리 길이를 읽어 내 배선을 거꾸로 추적했습니다. 전쟁 몇 주 전인 1939년 7월, 폴란드는 바르샤바 근교 피리에서 그 방법과 복제 기계를 영국과 프랑스에 넘겼습니다.

바통을 이어받은 영국은 블레츨리 파크에 수학자, 언어학자, 체스 선수를 모았습니다. 수학자 앨런 튜링은 폴란드의 해독 기계 봄바를 발전시켜 봄베⁠(bombe)⁠라는 전기 기계를 설계했습니다. 암호문 속 어딘가에 들어 있으리라 추측한 평문 조각(예: 날씨 보고의 WETTER)을 기준으로, 그와 모순되는 회전자 설정을 기계적으로 지워 나가는 장치입니다. 소수를 거르는 체와 같은 생각입니다(「소수를 세는 사람들」). 1945년 블레츨리에서 일한 1만 명 가까운 사람 가운데 약 4분의 3이 여성이었습니다. 독일군 최고 사령부의 전신 암호(로렌츠 암호⁠, Lorenz cipher⁠)를 풀려고 1944년 이곳에서 가동한 진공관 기계 콜로서스⁠(Colossus)⁠는 전자식 디지털 계산기의 초기 형태 가운데 하나가 되었습니다(「기계가 풀 수 없는 문제」 6절).

절대 풀리지 않는 암호는 없을까요? 있습니다. 1917년 AT&T의 기술자 길버트 버냄은 전신 부호의 각 비트에 열쇠 테이프의 비트를 2를 법으로 더하는, 곧 배타적 논리합⁠(exclusive or)⁠을 취하는 기계를 만들었습니다. 미 육군의 조지프 모보인은 여기에 열쇠 테이프를 완전히 무작위로 만들고 한 번만 쓰자는 조건을 덧붙였습니다. 1절의 카이사르 암호를 글자마다 다른 무작위 열쇠로 한 번씩만 하는 셈입니다. 1949년 섀넌은 일회용 난수표라 불리는 이 방식이 완벽히 안전하다는 것을 증명했습니다. 완벽한 안전을 얻으려면 열쇠가 메시지만큼 길어야 한다는 것도 증명했습니다. 뒤의 증명은 개수를 세는 논증입니다. 열쇠의 가짓수가 메시지의 가짓수보다 적으면, 가로챈 암호문 하나를 모든 열쇠로 풀어 보아도 나오는 평문이 가능한 평문을 다 덮지 못합니다. 그러면 도청자는 적어도 어떤 평문은 후보에서 지울 수 있으니 완벽하지 않습니다(「불가능의 증명」 6절). 규칙을 어기면 무너집니다. 전쟁 중 소련의 암호 제작소는 쏟아지는 수요에 쫓겨 이미 나눠 준 열쇠 일부를 다시 찍었고, 미국의 해독 계획 베노나는 두 번 쓰인 열쇠를 찾아내 1940년대 소련 정보 전문 수천 건을 부분적으로 풀었습니다.

유클리드에서 오늘까지 이 글의 수학과 그 수학이 놓인 역사입니다. 수학 줄(파랑)의 사건⁠(event)⁠들이 오랫동안 역사 줄(분홍)의 해독 경쟁과 따로 흐르다가, 1970년대에 한데 만나는 것을 보세요. 지도의 파란 선은 편지, 분홍과 주황 선은 가로챈 편지와 전보, 넘겨준 기계입니다.

8 · 쓸모없던 수학2,000년이 걸린 자물쇠

이 절의 물음은 이것입니다. 암호와 아무 관계 없던 수학이 어떻게 전 세계 통신의 자물쇠가 되었고, 그 자물쇠는 누구의 것인가?

이 글의 재료는 대부분 암호와 아무 관계 없이 만들어졌습니다. 유클리드와 페르마, 오일러와 가우스에게 정수론⁠(number theory)⁠은 수 자체의 아름다움을 캐는 일이었습니다. 20세기 초까지도 정수론은 가장 순수한 수학, 그래서 쓸모와는 가장 먼 수학의 대표로 여겨졌습니다.

정수론이나 상대성이론이 전쟁에 쓰일 목적을 찾아낸 사람은 아직 아무도 없으며, 앞으로 여러 해 동안 누가 그렇게 할 것 같지도 않다.— G. H. 하디, 『어느 수학자의 변명』(1940)

하디의 예상은 빗나갔습니다. 한 세대 뒤 정수론은 전 세계 통신의 자물쇠가 되었습니다. 하디가 이 책을 쓰던 1940년, 케임브리지 킹스 칼리지의 젊은 연구원 튜링은 이미 블레츨리 파크에서 순열⁠(permutation)⁠의 수학으로 에니그마와 씨름하고 있었습니다. 하디가 가장 쓸모없다고 여긴 소수의 분포가 어떤 법칙을 따르는지, 그리고 그 법칙이 어떻게 암호의 보증이 되었는지는 「소수를 세는 사람들」에 있습니다. 1977년 8월 『사이언티픽 아메리칸』의 마틴 가드너 수학 칼럼에는 RSA 발명자들이 낸 문제가 실렸습니다. 129자리 수 하나와 그 수로 잠근 메시지를 공개하고, 푸는 사람에게 100달러를 주겠다는 것이었습니다. 당시 알려진 방법과 가장 빠른 컴퓨터로는 4경 년($4 \times 10^{16}$년)쯤 걸린다는 어림도 함께 실렸습니다.

17년 뒤인 1994년, 인터넷으로 모인 600명쯤의 자원봉사자가 각자 컴퓨터의 남는 시간을 보태 여덟 달쯤 계산한 끝에 이 수를 인수분해했습니다. 계산을 빠르게 만든 것은 컴퓨터만이 아니었습니다. 그사이 인수분해 알고리즘⁠(algorithm)⁠이 크게 발전한 덕이 컸습니다. 풀린 메시지는 이랬습니다.

THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE
(마법의 주문은 '비위 약한 수염수리')— RSA-129 도전 문제의 평문, 1994년에 해독

이 이야기에는 숨은 장이 있습니다. 1970년 무렵 영국의 통신 정보기관 GCHQ의 제임스 엘리스는 열쇠를 미리 나누지 않는 암호가 원리적으로 가능하다는 생각을 내부 보고서로 남겼습니다. 1973년 막 입사한 수학자 클리퍼드 콕스가 이를 실현하는 방법을 떠올렸습니다. 두 소수의 곱을 공개하는, RSA와 거의 같은 방법이었습니다(공개 지수로 $n$ 자체를 쓴 점이 달랐습니다). 이듬해 동료 맬컴 윌리엄슨은 디피–헬먼과 같은 열쇠 교환을 찾았습니다. 이 연구는 모두 기밀이었고, 1997년에야 공개되었습니다. 엘리스는 공개 몇 주 전에 세상을 떠났습니다. 그래서 공개키 암호를 누가 처음 발명했느냐는 물음에는 두 가지 답이 있습니다. 먼저 생각한 사람들과, 세상에 내놓은 사람들입니다.

두 발명의 운명이 갈린 것은 암호가 오랫동안 국가의 일이었기 때문입니다. 1952년 창설된 미국 국가안보국(NSA)은 오랫동안 이름조차 잘 드러나지 않았고, 미국 정부는 암호 기술을 무기로 분류해 수출을 통제했습니다. 1977년 정부 표준이 된 DES 암호는 NSA가 설계에 관여해 열쇠가 56비트로 짧아졌다는 의심을 받았고, 디피와 헬먼은 곧 그 길이가 너무 짧다고 비판했습니다. 1998년 전자 프런티어 재단(EFF)이 만든 전용 기계가 DES 열쇠를 56시간 만에 찾아내 그 비판이 옳았음을 보였습니다.

그사이 1990년대에는 '암호 전쟁'이 벌어졌습니다. 1991년 필 짐머먼이 누구나 쓸 수 있는 공개키 암호 프로그램 PGP를 내놓자, 미국 정부는 수출 규제 위반 혐의로 그를 수사했고, 수사는 1996년에 끝났습니다. 1993년에는 정부가 열쇠 사본을 보관하는 클리퍼 칩을 내놓았다가 반발 속에 거둬들였습니다. 수출 규제는 2000년 무렵 크게 풀렸습니다.

공개키 암호는 두 번 발명되었습니다. 첼트넘(GCHQ)에서는 기밀로 묻혔고, 스탠퍼드와 MIT에서는 학술지와 잡지로 공개되었습니다. 포트미드(NSA)와 워싱턴, 볼더를 눌러 그 뒤의 논쟁도 따라가 보세요.

그 밑에 깔린 물음은 수학이 아니라 윤리와 정치의 문제입니다. 1890년 보스턴의 두 법률가 워런과 브랜다이스는 즉석 사진과 대중 신문의 시대를 맞아, 사생활을 '혼자 있을 권리'로 내세웠습니다. 공개키 암호 덕분에 그 권리를 수학으로 뒷받침할 수 있게 되었지만, 같은 수학이 범죄자와 적대 세력의 통신도 지킵니다. 2013년 NSA의 대규모 통신 감시가 폭로된 뒤 웹의 기본 암호화가 빠르게 퍼진 것도, 수사기관이 암호에 '뒷문'을 요구하는 논쟁이 되풀이되는 것도 이 긴장에서 나옵니다.

이 논쟁의 바탕에는 19세기의 원칙 하나가 있습니다. 1883년 네덜란드 출신의 언어학자 오귀스트 케르크호프스는 암호의 안전이 방식의 비밀이 아니라 열쇠의 비밀에만 기대야 한다고 썼습니다. 방식을 모두 공개해도 열쇠만 지키면 된다면, 암호는 국가만이 아니라 누구나 가질 수 있는 도구가 됩니다. 공개키 암호는 그 원칙을 끝까지 밀고 간 것입니다. 이 글의 모든 수학이 공개되어 있어도, 여러분의 비밀 열쇠만 새지 않으면 됩니다.

9 · 이어지는 길나머지가 여는 문

시계 위의 산수는 수학의 여러 갈래와 이어집니다.

• 그림으로: 시계의 $k$번 점을 $2k$번 점과 이으면, 곱셈표 한 줄에서 하트 모양 곡선이 떠오릅니다(원 위의 곱셈표⁠, times tables on a circle⁠).
• 행렬⁠(matrix)⁠로: 1929년 미국의 수학자 레스터 힐은 글자 여러 개를 묶어 26을 법으로 행렬을 곱하는 암호를 만들었습니다. 되돌리려면 역행렬⁠(inverse matrix)⁠이 필요하고, 그러려면 행렬식⁠(determinant)⁠이 26과 서로소여야 합니다. 2절의 규칙이 행렬로 옮겨 간 것입니다.
• 회전으로: 원시근의 거듭제곱이 단원 $\varphi(n)$개를 한 바퀴 도는 모습은 복소평면⁠(complex plane)⁠에서 $e^{2\pi i/\varphi(n)}$을 곱해 가는 회전과 같은 구조입니다. 곱셈을 회전으로 보는 이야기는 「곱셈은 회전이다」에 있습니다.
• 연분수로: RSA에서 여는 열쇠 $d$를 너무 작게 고르면, 공개된 $e/n$의 연분수에서 $d$가 드러난다는 공격이 알려져 있습니다(암호학자 마이클 위너, 1990). 유클리드 호제법이 공격자의 도구도 됩니다.
• 확률로: 실제 전자서명은 긴 문서를 짧은 지문(해시⁠, hash⁠)으로 줄여서 잠급니다. 서로 다른 두 문서의 지문이 우연히 겹칠 확률은 생일 문제⁠(birthday problem)⁠가 알려 줍니다. 지문이 $b$비트라면 문서를 $2^{b}$개가 아니라 $2^{b/2}$개쯤만 모아도 겹치는 쌍이 나올 확률이 40%에 가까워집니다. 그래서 지문은 충분히 길어야 합니다.
• 곡선으로: 1985년 닐 코블리츠와 빅터 밀러는 따로따로, 나머지의 곱셈 대신 타원곡선($y^2 = x^3 + ax + b$ 꼴의 식이 그리는 곡선) 위의 점을 '더하는' 연산으로 디피–헬먼을 할 수 있음을 보였습니다. 이 방식은 같은 안전성을 훨씬 짧은 열쇠로 얻을 수 있어 오늘날 널리 쓰입니다. 같은 1980년대에 타원곡선⁠(elliptic curve)⁠은 페르마의 마지막 정리⁠(Fermat's Last Theorem)⁠를 푸는 열쇠로도 떠올랐습니다. 1993년 와일스의 증명에 빈틈이 드러났다가 메워진 이야기는 「틀린 증명이 만든 수학」 8절에 있습니다.
• 대화로 하는 증명: 1985년 샤피 골드바서, 실비오 미칼리, 찰스 래코프는 비밀을 하나도 드러내지 않고 "나는 비밀을 안다"는 것만 확인시키는 대화, 곧 영지식 증명⁠(zero-knowledge proof)⁠을 내놓았습니다. 확인하는 쪽이 무작위로 질문하고 증명하는 쪽이 매번 답하는 방식이라, 증명을 두 사람의 게임으로 읽는 생각과 이어집니다(「이기는 쪽이 존재한다」 8절).
• 완벽한 비밀의 값: 섀넌이 증명한 '열쇠는 메시지만큼 길어야 한다'는 한계는 경우의 수⁠(number of cases)⁠를 세어 얻은 불가능성입니다. 같은 개수 세기 논증이 압축과 정렬의 한계를 긋는 모습은 「불가능의 증명」 6절에 있습니다.
• 소수의 분포로: 열쇠를 만들 때마다 수백 자리 소수를 찾을 수 있는 것은, 소수가 드물어도 그 밀도($x$ 근처에서 약 $1/\ln x$)를 예측할 수 있기 때문입니다. 그 이야기는 「소수를 세는 사람들」에서 이어집니다.
• 풀기 어려운 문제들: 그래프의 모든 꼭짓점⁠(vertex)⁠을 한 번씩 도는 길을 찾는 문제처럼, 답을 확인하기는 쉽지만 찾기는 어려워 보이는 문제들이 있습니다. 「일곱 다리의 도시」를 보세요.
• 틀린 비트 고치기: 비밀을 지키는 것만큼 신호를 지키는 것도 수학입니다. 해밍 거리⁠(Hamming distance)⁠로 오류를 찾아 고치는 부호는 「까마귀와 택시」에서 다룹니다.
• 줄이기와 잠그기: 1949년 섀넌은 정보 이론의 도구로 비밀 통신을 분석했습니다. 좋은 암호문은 무작위처럼 보여 더 줄일 수 없으니, 압축은 암호화보다 먼저 해야 합니다. 여분을 짜내는 압축과 거꾸로 여분을 더하는 오류 정정 부호⁠(error-correcting code)⁠는 「짧게 보내기」에서 다룹니다.
• 암호 해독에서 계산 이론⁠(theory of computation)⁠으로: 블레츨리의 튜링이 1936년에 이미 무엇을 계산할 수 있는지 정의했던 이야기와 P 대 NP 문제⁠(P versus NP problem)⁠는 「기계가 풀 수 없는 문제」에 있습니다. P = NP, 곧 답을 빨리(다항 시간⁠(polynomial time)⁠에) 확인할 수 있는 문제는 모두 빨리 풀 수도 있다면, 인수분해도 다항 시간에 풀립니다(인수분해는 답을 곱해 보기만 하면 확인되니까요). 그 다항식의 차수가 터무니없이 크지 않다면 RSA는 무너집니다. 하지만 거꾸로 P ≠ NP라고 해서 인수분해가 어렵다는 보장은 없습니다. 알킨디의 빈도 분석이 언어의 통계학으로 자란 이야기는 「말을 세는 기계」에 있습니다.