페이블 5.1, 370년 미해결 암호 풀었다 — 치환 암호 해독 원리와 빈도 분석

📐 수학 이야기

앤트로픽 페이블 5.1이 1653년 어쿼트가 남긴 64개 숫자 암호를 44분 만에 풀었다. 연구자들이 370년간 시도한 치환 암호 해독과 빈도 분석이 왜 안 통했는지, 카이사르 암호의 모듈러 연산과 키 공간, 책 암호 규칙까지 수식으로 정리했다.

미국 AI 평가기관 발스 AI가 앤트로픽의 페이블 5.1로 17세기 스코틀랜드 작가 토머스 어쿼트의 미해결 암호문 '암호 이중시'를 해독했다고 8월 31일 블로그에 공개했고, AI타임스가 9월 15일 이를 보도했다. 1653년 책에 실린 64개의 숫자는 1899년 학술지에 미해결 문제로 소개된 뒤 370년 넘게 풀리지 않았는데, 페이블 5.1은 44분 동안 17만 6,000토큰을 쓰며 여러 접근을 시험한 끝에 규칙을 찾아냈다. 연구자들이 써 온 치환 암호 해독 기법이 왜 실패했고, 답은 어디에 있었는지 수학으로 따라가 보자.

무슨 일이 있었나 — 64개 숫자, 44분, 32라는 단서

어쿼트의 저서 로고판덱테이시온 맨 끝에는 한 줄에 32개씩 두 줄, 모두 64개의 숫자로 된 암호문이 실려 있다. 이 숫자열은 1899년 영국 교양지 노트 앤 쿼리스에 미해결 문제로 실렸고, 역사 암호 연구자 클라우스 슈메가 꼽은 대표적 미해결 암호 50선에도 올라 있었다. 연구자들은 빈도 분석과 치환 암호, 여러 기호가 한 글자를 나타내는 동음이의 치환까지 시도했지만 뚜렷한 답을 얻지 못했다.

페이블 5.1은 규칙을 밖에서 찾지 않고 책 안에서 찾았다. 암호문 바로 앞에는 어쿼트가 쓴 32개의 프로퀴리테이션이라는 문단이 있고, 저자는 본문에서 32라는 수를 유난히 강조하며 소원이라는 표현을 반복한다. 32개 문단, 한 줄에 32개 숫자, 소원. 이 단서를 연결한 규칙은 i번째 숫자를 i번째 문단의 단어 번호로 읽어 그 단어의 첫 글자를 취하는 것이었다.

그렇게 나온 두 줄은 찰스 2세를 지켜 달라는 왕당파의 기도문이었다. 두 줄 모두 정확히 32글자이고 마지막 단어가 and와 land로 운을 맞추며, 어쿼트가 왕당파였다는 역사와도 맞는다. 발스 AI는 같은 방식으로 1652년 저서에 실린 285개 숫자 암호 팔각시까지 아홉 글자를 제외하고 풀었다고 덧붙였다. 새 암호 해독 기법을 만든 것이 아니라 단서를 끈질기게 찾은 결과라는 것이 발스 AI의 평가다.

치환 암호란? 뜻과 종류

치환 암호는 평문의 글자를 정해진 규칙에 따라 다른 글자나 기호로 바꾸는 방식이다. 글자의 위치는 그대로 두고 정체만 바꾼다는 점에서, 글자는 그대로 두고 순서만 섞는 전치 암호와 구별된다. 한 글자가 늘 같은 기호로 바뀌면 단일 치환 암호, 위치에 따라 다른 규칙이 적용되면 다중 치환 암호, 한 글자를 여러 기호 중 하나로 무작위로 바꾸면 동음이의 치환 암호다.

가장 단순한 치환 암호가 카이사르 암호다. 알파벳에 0부터 25까지 번호를 붙이고 각 글자를 k칸 뒤로 밀면 되는데, Z 다음이 다시 A로 돌아오므로 이것은 26으로 나눈 나머지를 구하는 모듈러 연산이다.

$$E(x) = (x + k) \bmod 26,\qquad D(y) = (y - k) \bmod 26$$

x는 평문 글자의 번호, k는 키, E는 암호화, D는 복호화다. 두 식은 서로 역함수이며 26으로 나눈 나머지만 남긴다.

여기에 곱셈까지 넣으면 아핀 암호가 된다. 곱하는 수 a는 26과 서로소여야 역원이 존재해 복호화가 가능하다.

$$E(x) = (ax + b) \bmod 26,\qquad \gcd(a, 26) = 1$$

26과 서로소인 a는 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25의 12가지뿐이므로 키는 12 곱하기 26, 즉 312개다.

키 공간의 크기 — 26!은 왜 안전하지 않은가

일반적인 단일 치환 암호는 알파벳 26개를 어떤 순서로든 재배열할 수 있으므로 키의 수는 26의 계승이다.

$$26! \approx 4.03 \times 10^{26}$$

가능한 치환 암호 키의 개수다. 1초에 10억 개씩 시도해도 약 4×10^17초, 약 130억 년이 걸려 우주의 나이와 비슷하다.

무차별 대입으로는 못 푸는 셈이지만, 치환 암호는 9세기 아랍 학자 알 킨디 이후 손으로도 풀린다. 키 공간이 크다는 것과 암호가 안전하다는 것은 다른 이야기라는 사실을 치환 암호가 가장 잘 보여준다. 이유는 치환이 글자의 정체만 바꿀 뿐 각 글자가 나타나는 횟수, 즉 빈도 분포를 그대로 옮겨 놓기 때문이다.

빈도 분석의 원리 — 일치 지수와 유니시티 거리

영어 문장에서 E는 약 12.7%, T는 9.1%, A는 8.2% 비율로 나타난다. 단일 치환 암호문에서 가장 자주 보이는 기호는 높은 확률로 E이고, 두 글자 조합 TH, 세 글자 조합 THE의 패턴도 그대로 살아 있다. 빈도 분석은 이 통계적 지문으로 키를 복원하며, 단일 치환인지 다중 치환인지는 일치 지수로 구별한다.

$$IC = \frac{\sum_{i=1}^{26} n_i (n_i - 1)}{N(N-1)}$$

N은 암호문 글자 수, n_i는 i번째 글자의 출현 횟수다. 무작위로 뽑은 두 글자가 같을 확률로, 영어 문장은 약 0.066, 완전 무작위 문자열은 약 0.038이다.

단일 치환 암호문은 글자 이름만 바뀌었으므로 일치 지수가 영어 문장과 같은 0.066 근처에 머문다. 반면 비즈네르 같은 다중 치환은 빈도가 평탄해져 0.038에 가까워진다. 암호문이 몇 글자면 풀리는지는 섀넌의 유니시티 거리가 답한다.

$$U = \frac{H(K)}{D} = \frac{\log_2 26!}{\log_2 26 - H_{\text{lang}}} \approx \frac{88.4}{4.7 - 1.5} \approx 28$$

H(K)는 키의 정보량, D는 언어의 중복도다. 영어 한 글자의 실제 정보량이 약 1.5비트이므로, 단일 치환 암호문은 28글자 정도면 원칙적으로 답이 하나로 정해진다.

어쿼트의 암호는 64개 숫자였으니 치환 암호였다면 충분히 풀렸어야 했다. 그런데 풀리지 않았다. 이것이 바로 이 암호가 치환 암호가 아니라는 신호였다. 숫자들은 글자를 대신하는 기호가 아니라 단어의 위치를 가리키는 색인이었기 때문에, 같은 글자가 매번 다른 숫자로 나타나 빈도 정보가 통째로 사라졌다. 빈도 분석이 통하지 않는 암호에 빈도 분석을 370년 동안 들이댄 셈이다.

페이블 5.1이 찾은 규칙 — 책 암호와 자기 검증

페이블 5.1이 찾은 규칙은 암호학에서 책 암호라고 부르는 방식이다. 키가 별도의 표가 아니라 책 자체이고, 숫자는 책 속 특정 단어의 좌표다. 어쿼트 암호에서는 i번째 숫자가 i번째 문단 안의 단어 번호를 가리키고 그 단어의 첫 글자를 모은다.

$$c_i = \operatorname{first}\big(w_{i,\,n_i}\big),\qquad i = 1, 2, \dots, 32$$

n_i는 암호문의 i번째 숫자, w_{i,j}는 i번째 문단의 j번째 단어, first는 첫 글자를 취하는 함수다. 문단 순서와 숫자 순서가 일대일로 대응한다.

이 풀이가 우연이 아니라는 것도 수학으로 뒷받침된다. 알파벳 26개로 만들 수 있는 32글자 문자열은 26의 32제곱 개인데, 그중 뜻이 통하는 영어 문장의 수는 섀넌의 추정대로 글자당 약 1.3비트의 정보량을 가정하면 2의 41.6제곱 개 정도에 불과하다. 규칙이 틀렸는데도 두 줄 모두 정확히 32글자의 문장이 되고 운까지 맞을 확률은 사실상 0이다.

$$\frac{2^{1.3 \times 32}}{26^{32}} \approx 2^{-109}$$

무작위 32글자 문자열이 뜻이 통하는 영어 문장일 확률의 대략적 크기다. 두 줄이 동시에 문장이 되고 마지막 단어가 운을 맞출 확률은 이보다 훨씬 작다.

나는 대학 시절 정수론 수업의 빈도 분석 과제에서 26!이라는 키 공간이 무의미하다는 것을 직접 확인한 적이 있다. 그때 남은 교훈은 암호의 안전성은 키의 개수가 아니라 평문의 통계가 얼마나 새어 나가는지에 달려 있다는 것이었는데, 어쿼트 암호는 반대로 통계가 전혀 새어 나가지 않아서 문제였다는 점이 흥미롭다.

고등 수학과 연결되는 지점, 그리고 남은 문제

치환 암호는 고등 수학의 여러 단원과 맞닿아 있다. 26!은 순열의 수이고, 카이사르 암호의 나머지 연산은 정수의 나눗셈과 합동식, 빈도 분석은 확률과 통계의 도수분포와 기대도수, 유니시티 거리는 정보량과 로그의 성질이다.

앞서 오픈AI가 나비에-스토크스 방정식 관련 결과를 발표했고, 갈루아 이론의 40년 난제 M23 문제도 AI의 도움으로 풀렸다. 발스 AI는 이번 성과의 의미를 새로운 암호 해독 기법이 아니라, 사람의 관심에서 멀어져 방치된 문제를 AI가 끈질기게 탐색할 수 있게 됐다는 데서 찾는다. 팔각시에 남은 아홉 글자와 CIA 본부의 크립토스 K4처럼 아직 풀리지 않은 암호가 다음 시험대다.

함께 읽으면 좋은 글

유클리드 호제법 원리와 증명, 최소공배수까지 정리 40년 난제 M23 해결 — 갈루아 이론과 역갈루아 문제 정리 벤포드 법칙이란? 뜻과 증명, 회계부정 적발 원리

참고 자료

Vals AI — Claude Fable 5.1 Solves the Cyphral Distich (2026.08.31) AI타임스 — 앤트로픽 페이블 5.1, 370년 미해결 난제 암호 44분 만에 풀었다 (2026.09.15) 위키백과 — 치환 암호