Publish the lock, keep the key.
수천 년간 암호의 대전제는 하나였습니다 — 보내는 이와 받는 이가 같은 비밀(열쇠)을 미리 나눠 가져야 한다. 그런데 1970년대, 누구도 만난 적 없는 두 사람이 열쇠를 통째로 공개하고도 비밀을 주고받는 방법이 나옵니다. 카이사르의 암호부터 에니그마를 거쳐, 지금 이 주소창의 자물쇠를 지키는 RSA까지 — 암호의 발상이 어떻게 뒤집혔는지 따라가 봅니다.
가장 오래된 암호 중 하나는 카이사르 암호입니다. 알파벳을 정해진 칸수만큼 밀어 쓰는 것 — 밀기 \(3\)이면 A→D, B→E. 받는 쪽은 거꾸로 \(3\)칸 당겨 읽죠. ‘밀기 칸수’가 곧 열쇠이고, 보내는 이와 받는 이가 이 칸수를 미리 똑같이 알고 있어야 합니다.
카이사르처럼 ‘밀기’만 하지 말고, 알파벳 26글자를 아무렇게나 짝지어 바꾸면(단일치환 암호) 열쇠의 수는 \(26! \approx 4\times10^{26}\)가지 — 전수조사는 우주의 나이로도 불가능합니다. 그런데도 이 암호는 허무하게 무너집니다. 같은 평문 글자는 늘 같은 암호 글자로 바뀌기 때문에, 글자의 빈도 지문이 그대로 남거든요. 영어에서 가장 흔한 글자는 E(약 12.7%), 그다음 T·A·O… 그러니 암호문에서 가장 많이 나온 글자가 곧 E일 공산이 크죠. 이렇게 빈도 순위를 맞춰 가는 것이 빈도 분석입니다.
이를 막으려 나온 게 비즈네르 암호입니다. 키워드를 정해 글자마다 밀기 칸수를 바꿔 가며
적용하죠(예: 키 KEY면 11·5·25·11·5·25…칸씩). 같은 평문 글자가 위치에 따라 다른 암호
글자가 되니 빈도 지문이 뭉개져, 300년간 ‘해독 불가능한 암호’로 불렸습니다. 하지만 19세기에
배비지와 카지스키가 약점을 찾아냅니다 — 암호문에 같은 토막이 반복되면 그 간격은 대개 키 길이의
배수입니다. 간격들의 최대공약수로 키 길이 \(n\)을 알아낸 뒤, 암호문을 \(n\)개의 열로 쪼개면 각 열은
다시 단순한 카이사르 암호 — 열마다 빈도 분석을 돌리면 끝이죠. 다중치환이 단일치환 여러 개로 도로
풀려버린 겁니다.
2차 대전의 독일군 에니그마는 비즈네르의 발상을 기계로 극한까지 밀어붙였습니다. 타자기처럼 생긴 이 기계는 플러그보드 → 회전하는 로터(회전자) 3개 → 반사판을 거쳐 다시 거꾸로 돌아 나오며 글자를 바꿉니다. 결정적으로, 키를 한 번 누를 때마다 로터가 한 칸 돌아 치환표가 매 글자 달라지죠 — 사실상 주기가 어마어마한 비즈네르입니다. 로터 배열·시작 위치·플러그보드 조합까지 더하면 열쇠의 수가 \(10^{20}\)을 한참 넘어, 독일군은 해독 불가를 확신했습니다.
그러나 무너졌습니다. 첫 균열은 구조적 결함이었어요 — 반사판 탓에 어떤 글자도 자기 자신으로는
암호화되지 않습니다(A가 A가 될 수 없음). 이 한 가지 제약이 후보를 무더기로 쳐냅니다. 폴란드의
마리안 레예프스키가 순열의 군론으로 배선을 역설계해 첫 해독기 ‘봄바’를 만들었고, 이어
블레츨리 파크의 앨런 튜링과 고든 웰치먼이 봄브(Bombe)를 제작합니다. 비결은 크립
(crib) — 매일 같은 시각의 일기예보 WETTER나 의례적인 HEIL HITLER처럼
들어 있을 게 뻔한 평문을 가정해, ‘자기 자신 불가’ 규칙과 모순되는 로터 설정을 기계가 초고속으로
걸러내는 것이었죠.
카이사르부터 에니그마까지, 이 모든 암호에는 끝내 같은 치명적 약점이 있었습니다 — 열쇠를 어떻게 안전하게 건네느냐. 송신자와 수신자가 같은 열쇠(코드북·로터 설정)를 미리 나눠 가져야 했고, 그 순간이 늘 위험했죠. 이 2천 년의 전제를, 1970년대가 뒤집습니다.
1976년, 디피·헬먼·머클(그리고 비밀리에 영국 GCHQ)이 상식을 뒤집습니다. 잠그는 도구와 여는 도구를 분리하자는 것. 누구나 가져다 잠글 수 있는 열린 자물쇠(공개키)를 사방에 뿌려두되, 그걸 여는 열쇠(개인키)는 나만 갖습니다. 당신에게 비밀을 보내려는 사람은 내 공개 자물쇠로 잠그기만 하면 되고 — 한 번 잠그면 자물쇠 주인조차도 열쇠 없이는 못 엽니다. 열쇠를 미리 나눌 필요가 사라진 거죠.
이게 가능하려면 한쪽으로만 쉬운 계산이 필요합니다 — 잠그기(정방향)는 쉽고, 열쇠 없이 풀기(역방향)는 사실상 불가능한 일방향 함수. 그 재료를 수론이 내놓습니다.
핵심 재료는 모듈러 거듭제곱입니다. 큰 수 \(n\)으로 나눈 나머지 세계(시계 산술)에서 \(m^e \bmod n\)을 구하는 건 빠릅니다. 하지만 그 결과만 보고 거꾸로 원래 수를 알아내는 건 — \(n\)의 소인수를 모르는 한 — 엄청나게 어렵습니다. 이 비대칭이 자물쇠의 정체입니다.
1977년 리베스트·샤미르·애들먼이 이 발상을 구체화합니다. 큰 소수 두 개 \(p,q\)를 골라:
암호화·복호화는 모듈러 거듭제곱 한 번씩입니다.
$$ c \equiv m^{e} \pmod n, \qquad m \equiv c^{d} \pmod n $$되돌아오는 이유는 오일러 정리에서 곧장 나옵니다: \(ed\equiv1\pmod{\varphi(n)}\)이라 \(c^{d}\equiv m^{ed}\equiv m^{1+k\varphi(n)}\equiv m\pmod n\). 아래에서 작은 소수로 직접 돌려 보세요.
공격자는 공개키 \((n,e)\)를 다 압니다. 개인키 \(d\)를 구하려면 \(\varphi(n)=(p-1)(q-1)\)이 필요하고, 그러려면 \(n\)을 소인수분해해 \(p,q\)를 알아내야 합니다. 그런데 수백 자리 \(n\)의 소인수분해는 현존 컴퓨터로 수십억 년이 걸리죠. RSA의 안전은 바로 이 한 가지 가정에 통째로 걸려 있습니다 — "큰 수의 소인수분해는 현실적으로 어렵다."
"비밀을 지키려면 비밀을 나눠야 한다"는 수천 년의 전제를, 수론은 "자물쇠는 공개하고 열쇠만 숨겨라"로 뒤집었습니다. 덕분에 한 번도 만난 적 없는 서버와 당신의 브라우저가 매 순간 안전하게 비밀을 주고받죠. 그 모든 것이 소수와 나머지 산술이라는, 가장 오래된 수학 위에 서 있습니다.