[전문가의 세계 - 박주용의 퓨처라마](25)역사를 바꾼 전쟁…전쟁의 승부를 바꾼 ‘암호해독’

블레츨리 파크의 추억(1)-암호와의 전쟁과 21세기 과학기술의 태동

일러스트 김상민 기자

‘완벽한’ 암호 체계의 핵심은 바로 아군끼리만 공유하는 x값의 난수표
다음 숫자를 알 수 없는 난수의 성질을 유지하기 위하여 ‘한 번씩만 사용하는 숫자의 표’라는 뜻
이것을 ‘One-Time Pad’라고 하는데, 카이사르 이후 2100년이 지난 지금
우리가 인터넷뱅킹을 할 때 사용하는 ‘OTP’의 유래이자 원리도 같다

매섭게 차가운 공기로부터 몸을 따뜻하게 지키고자 한 겹 한 겹 더 둘러 입는 옷의 두께만큼 자연으로부터 멀어지게 만들던 겨울이 물러가는 온기의 신호가 스물스물 느껴지더니 어느덧 4월이 되었다. 바람과 햇살을 아무런 장애물 없이 나의 살갗 그대로 맞을 수 있는 자연과의 화해의 계절, 봄이 오고 있다.

몇 해 전 방문학자로 가 있던 영국도 사시사철 으슬으슬 춥고 비가 많이 온다는 인상과는 달리 봄과 여름의 날들은 세계 어디에 내놓아도 부럽지 않을 정도로 맑고 화창한 날씨를 자랑한다. 그랬던 어느 날 나 혼자만의 시간을 며칠 갖게 되어 영국이 자랑하는 모터사이클, 트라이엄프의 보너빌(Bonneville)을 빌려 타고 길을 나섰다. 보너빌은 2차 세계대전 당시 독일군에 포로로 잡힌 연합군 파일럿이 탈출하기 위해 철조망을 뛰어넘으려는 장면으로 유명한 1963년 영화 <대탈주(The Great Escape)>에 나온 이후로 ‘자유’를 상징하는 모터사이클이 되었고, 나는 드디어 그것을 본토에서 타보는 감격에 젖을 수 있게 된 하루였다.

행선지는 ‘블레츨리 파크(Bletchley Park)’. 2차 대전 때 독일군 암호를 깨기 위한 특수연구 임무를 수행하던 곳으로서 지금은 암호 역사 기념관이 되어 관광객들을 맞이하는 곳이다.

전쟁에서 암호를 이용한 비밀 소통의 역사는 전쟁 자체만큼 길 것이다. 작전계획을 우리 편에 안전하게 전달하고 적군으로부터 숨기는 것은 그야말로 목숨이 걸린 중대한 일이었을 테니까.

고대 로마의 장군이자 정치인 율리우스 카이사르(IVLIVS CAESAR·기원전 100~44)는 갈리아(현재의 프랑스·스위스·독일 등 영토의 일부)를 정복한 뒤 폼페이우스(POMPEIVS·기원전 106~48)와의 내전에서 승리하며 로마를 장악한 인물인데, 그의 군대가 사용했다고 하여 그의 이름을 딴 카이사르 암호(Caesar’s Cipher) 체계는 암호학의 아주 기본적인 개념이다.

기원전 48년, 갈리아 전쟁을 마친 카이사르에게 로마 공화국 지도부인 원로원은 관례에 따라 무장을 해제하고 로마로 복귀할 것을 명령한다. 하지만 지도부를 불신하고 야망이 있었던 그는 이를 어기고 자신의 군단과 함께 현재 이탈리아 북부의 루비콘(RVBICON)강을 건너 로마로 진격한다. 아마도 전날 밤 카이사르는 카이사르 암호를 이용해 다음과 같은 지시를 자신의 군단에게 내렸을 것이다. ‘YTRFRTVVBMSFAK.’

이것이 로마 원로원의 지시대로 무장해제를 하라는 뜻인지 원로원을 공격하겠다는 뜻인지에 따라 로마의 역사는 돌이킬 수 없이 바뀔 운명이었고, 카이사르가 움직이기 전에 원로원이 이 암호를 풀어낼 수 있는가에 서로 사활이 걸려 있었을 것이다.

카이사르 암호의 원리는 다음과 같다. 카이사르가 활약하던 시절의 로마 알파벳은 ‘A, B, C, D, E, F, G, H, I, K, L, M, N, O, P, Q, R, S, T, V, X, Y, Z’로 모두 스물세 글자로 되어 있는데(현대 영어와 비교해 J, U, W 세 글자가 빠져 있다), 보내려는 글자를 아군끼리 이미 약속한 숫자 x만큼 알파벳 아래로 움직여 나오는 글자로 대체하는 것이었다. 예를 들어 x가 5였다면 A는 그보다 다섯 글자 뒤인 F로, B는 G로, X는 두 칸을 뒤로 움직인 뒤 남은 만큼 앞으로 움직여 C로 바뀌는 것이었다. 시대와 문명을 가리지 않고 누구나 명심해야 할 격언, ‘개 조심’을 뜻하는 라틴어 ‘CAVE CANEM’은 즉 ‘HFBK HFSKR’이 된다. 이미 x가 5라는 것을 알고 있는 사람이라면 역방향으로 알파벳을 옮김으로써 원메시지를 쉽게 알아낼 수 있다.

x=5인 경우 카이사르 암호화 방법.

그런데 x가 5라는 것을 모르는 사람(적군)이라면 ‘YTRFRTVVBMSFAK’라는 카이사르 군단의 메시지를 알기 위해 가능한 x값(1부터 23까지)을 갖고 모든 경우의 수를 따져볼 수밖에 없을 것이다. 즉 아래 표에 나온 것처럼 가능한 모든 ‘해독 메시지’를 만들어봐야 하는데, 국가체제의 존망을 두고 일초가 다급한 상황에서 원로원이 이렇게 시간을 들이는 동안에 카이사르가 루비콘강을 건너고 있었다면, 원로원이 결국 그것이 ‘ROMAM OPPVGNATE’, 즉 ‘로마를 치라’는 뜻이었다는 것을 알아차린 순간에 카이사르는 이미 무방비의 로마에 진입했을지도 모르는 일이다.

[전문가의 세계 - 박주용의 퓨처라마](25)역사를 바꾼 전쟁…전쟁의 승부를 바꾼 ‘암호해독’

물론 이렇게 열네 글자에 불과한 암호에 대해서는 모든 경우의 수를 다 따져보는 단무지(단순·무식·지구력 갑)의 ‘억지 기법(brute force)’을 써볼 만하겠으나, 원메시지가 수천, 수만개 글자로 이루어져 있다면 너무나 긴 시간이 드는 일이라 현실적인 방법이라고 보기 어렵다. 그래서 실제적으로는 저런 억지 기법보다는 ‘빈도 분석(frequency analysis)’이 자주 쓰인다. 이것은 어떤 언어든 알파벳의 각 글자가 등장하는 횟수가 서로 다르다는 데 기반해 있는데, 실제 아주 긴 라틴어 문학작품을 살펴보면(카이사르의 명문인 <갈리아 전기>를 직접 찾아 분석해보았다) 각 글자의 빈도는 다음의 표와 같다(최상위 열 개의 글자만 나와 있다).

이러한 라틴어의 특성을 알고나면 이제 아주 긴 라틴어 암호에서 각 글자의 등장 횟수를 센 뒤 제일 많이 등장하는 글자가 ‘E’를 뜻할 가능성이 높음을 알게 되므로 시간이 많이 걸리는 억지 기법에 비하여 훨씬 더 빠른 해독이 가능해지는 원리인데, 실제 지금까지도 암호 해독의 첫 단계는 이러한 빈도 분석이다.

하지만 ‘경찰을 따돌리려는 도둑’과 ‘도둑을 잡으려는 경찰’의 수법은 서로 앞서거니 뒤서거니 하며 발전하는 법이다. 원로원이 빈도 분석이라는 무기를 갖고 나왔을 때 카이사르는 어떻게 다시 원로원을 따돌릴 수 있을까? 수학적으로 실현 가능한 파훼 방법은 x값을 하나로 정해놓고 전체 메시지를 암호화하는 것이 아니라, 글자마다 새로운 x값을 난수로 발생시켜 암호화하는 것이다. 이렇게 되면 위 표처럼 ‘E, I, V, T…’의 순서대로 빈도가 높은 글자, 낮은 글자가 구별되지 않으므로(즉, 모든 글자가 똑같은 빈도로 등장하게 된다!) 암호 해독 첫걸음인 빈도 분석이 불가능해질 뿐만 아니라, 똑같은 메시지도 매번 다른 암호가 되어 나타나기 때문에 적군은 도무지 종잡을 수 없는 당혹스러운 상황에 빠지게 된다.

예를 들어 이러한 ‘개량된 암호’를 가진 카이사르 군단의 사령부와 일선 부대가 다음과 같은 난수표를 공유하고 있다고 가정하자.

23, 14, 17, 8, 10, 12, 14, 12, 2, 15, 18, 2, 5, 4, 1, 22, 16, 10, 23, 17, 21, 9, 7, 23, 3, 10, 11, 12, 23, 14, 6, 13, 19, 14, 1, 16, 12, 4, 7, 20, 2, 22, 13, 6, 23, 22, 20, 8, 23, 2, 3, 15, 8, 7, 8, 22, 7, 8, 11, 15, 6, 16, 4, 3, 13, 10, 20, 23, 2, 13, 7, 19, 21, 13, 18, 12, 5, 8, 4, 23, 5, 2, 18, 19, 21, 20, 14, 19, 13, 14, 11, 3, 4, 23, 23, 3, 15, 15, 18, 14.

그렇다면 ‘ROMAM OPPVGNATE’(로마를 치라)는 처음엔 ‘REFIYCFDYYHCAI’로, 다음엔 ‘SNELMHNADGQLGR’로, 다음엔 ‘RESOHEQHILVXXD’로 되면서 적군에게는 해독의 난도가 엄청나게 올라가는 반면 이 난수표를 공유하는 아군끼리는 여전히 쉽게 해독할 수 있는 완벽한 암호 체계가 만들어진다.

여기에서 보듯이 이 ‘완벽한’ 암호 체계의 핵심은 바로 아군끼리만 공유하는 x값의 난수표이다. 다음 숫자를 알 수 없는 난수의 성질을 유지하기 위하여 ‘한 번씩만 사용하는 숫자의 표’라는 뜻에서 이것을 One-Time Pad라고 하는데(카이사르 이후 2100년이 지난 지금 우리가 인터넷뱅킹을 할 때 사용하는 OTP의 뜻이 바로 이것이다), 난수표를 지속적으로 아군에게는 공급하고 적군은 못 빼앗아가게 하는 것이 매우 중요하다는 점을 알 수 있다. 필자가 1980년대에 다니던 초등학교는 서울 외곽에서 뒷산을 지고 있는 곳이었는데, 쉬는 시간에 산에 놀러갔다가 숫자가 빼곡히 인쇄된 종이를 주워온 친구에게 선생님이 북한이 남파간첩에게 보내는 난수표를 습득해 신고했다고 칭찬을 해주시던 기억이 난다. 그리고 당시 동네 목욕탕에 가면 ‘간첩 신고 보상 천만원, 간첩선 신고 보상 오천만원’이라는 표어가 붙어 있었던 걸 보면(친구들이랑 우리 크면 바닷가에 가서 간첩선 잡아서 5000만원을 벌자고 맹세하곤 했다) 그 친구는 상도 받았을 것이다.

자 그러면 이쯤에서 보너빌의 감격에 젖어 열심히 찾아 달려가고 있던 블레츨리 파크 이야기로 돌아와보자. 1930년대 말 유럽이 2차 대전으로 불타오르던 시절 미국과 영국 연합군의 고민이 바로 이 암호 해독에 있었다. 유럽 대륙 전체가 히틀러의 나치 독일과 무솔리니의 파시스트 이탈리아에 점령당하자 섬나라였던 영국은 미국으로부터 대서양을 거쳐 오는 전쟁물자 보급에 의존할 수밖에 없었는데, 수면 아래에서 육안 탐지를 피하면서 ‘늑대무리 전술’을 부리던 나치 독일 해군의 우-보트(U-boot·잠수함)에 어마어마한 피해를 입고 있었기 때문이다.

전문가의 세계 - 박주용의 퓨처라마 구독

늑대무리 전술을 쓰던 독일 잠수함들은 20세기의 전기·기계 기술을 활용한 최첨단 암호화 장비인 에니그마(Enigma·‘수수께끼’라는 뜻)를 사용해 끊임없이 교신하고 있었는데, 에니그마는 위에서 소개한 단순한 ‘개량형 카이사르 암호’처럼 글자마다 새로운 난수가 필요한 번거로운 방식이 아니라 하루에 단 하나의 난수만 사용하면서도 하나의 글자가 다른 글자로 변환되는 경우의 수가 무려 1000만에 달하는 아주 효율적이고(나치 독일 입장에서는) 복잡한(연합군 입장에서는) 기계였다. 그래서 연합군에게는 이 암호를 해독하는 것이 전쟁의 승부가 걸린 급선무였기에 이 임무를 바로 블레츨리 파크에 모인 사람들에게 준 것이었다. 그리고 그 가운데는 21세기 과학기술의 선구자 앨런 튜링(Alan Turing·1912~1954)이라는 사람이 있었다. 그의 이야기는 다음에 이어서 해보겠다.

OCCVREMUS ITERVM PROXIMO MENSE(다음달에 또 만납시다)!

▶박주용 교수

서울대학교 물리학과를 졸업하고 미국 미시간대학교(앤아버)에서 통계물리학으로 박사 학위를 받았다. 네트워크와 복잡계 물리학에 기반한 융합 데이터 과학 전문가로서 노트르담대학교, 하버드 의과대학 데이너-파버 암연구소 연구원을 거쳐 현재 카이스트 문화기술대학원에서 문화예술과 과학의 창의성을 연구하고 있으며, AI 이후 시대를 준비하는 카이스트 포스트AI 연구소 소장을 맡고 있다. 학창 시절 미식축구에 빠져 대학팀 랭킹 알고리즘을 고안한 뒤 지금도 빠져 있으며, 시간이 생긴다면 자전거와 모터사이클을 타고 싶어 한다.

박주용 퓨처라마