이 포스팅은 Coursera의 Stanford University Cryptography I - Dan Boneh 강의를 바탕으로 제작되었습니다. Cryptography를 공부하시고자 하는 분들을 위해 조금이나마 기여할 수 있을까하여 포스팅을 지속하기로 결정하였습니다. 



지난강좌에 이어 계속해서 Course Overview를 진행하고 있습니다. 본격적으로 technical한 내용을 진행하기에 앞서서, 지난 역사속의 암호학 변천과정을 알려드리고자 합니다.

암호학의 역사에 관해서는 David Kahn이 저술한 Codebreakers라는 유명한 책이 있습니다.

좌측 원서(데이비드 칸), 우측은 한국어 번역판(이지북 출판, 김동현 옮김)좌측 원서(데이비드 칸), 우측은 한국어 번역판(이지북 출판, 김동현 옮김)
좌측 원서(데이비드 칸), 우측은 한국어 번역판(이지북 출판, 김동현 옮김)

이 책은 암호학의 처음 탄생했던 바벨로니아 시대부터 현재의 인터넷체계에 이르기까지, 그동안의 암호 해독의 역사를 총망라한 전세계적으로 가장 권위 있는 암호 해독 바이블입니다. 참고하시면 좋을 것입니다. 역사적으로 아주 오래 된 암호기법은 대부분 그 취약성이 드러났기 때문에 현재는 사용하지 않는 것이 바람직합니다. 


만약 Alice와 Bob이 안전하게 통신을 하고자 하는데, 그 사이에서 해커(Attacket)가 그들의 대화를 엿들으려고 하는 상황을 가정해봅시다.

이들은 도청을 막기 위해 비밀키(Secret key) K를 사용하기로 합의합니다. Alice 와 Bob은 K값을 알고있지만, 해커는 K값을 모르는 상황입니다. 이때 K를 이용해서 암호화가 진행되는 과정을 그림과 같이 도식화 할 수 있습니다. 암호화(Encryption) 알고리즘을 E로 표현하고, 복호화(Decryption) 알고리즘을 D로 정의하겠습니다. 암호화 알고리즘 E는 원문 메시지(M)과, 비밀키(K)를 input으로 사용합니다. 이를 통해 암호화된 결과문(Cipher Text) C를 output으로 출력합니다. 이 과정을 C:= E(K,M) 로 표현할 수 있습니다. 이렇게 얻어낸 C는 인터넷을 통해 Bob에게 전달됩니다. 그는 전달받은 C를 복호화하려고 합니다. 이때 Alice가 암호화했던 K값을 Bob도 숙지하고있어야 하며, 암호화된 메세지(C)와 비밀키(K)를 input으로하여 복호화(Decryption) 알고리즘 D를 사용합니다. 이를 통해 원문 메세지(original plain text message)였던 M을 얻을 수 있습니다. 이 과정은 M:=D(K,C)로 표현됩니다.

 
방금 설명드린 부분에서 핵심은, 암호화 키와 복호화 키가 동일한 K값을 사용했다는 점입니다. 이것을 대칭키 암호(Symmetric cipher) 라고 부릅니다. (동일하지 않은 키를 사용하는 경우는 비대칭키 암호라고 하고, 이번 강의에서는 대칭키 암호에 관련해서만 다루도록 하겠습니다.) 이처럼 대칭키 방식을 사용한 고전적인 암호에는 어떤것들이 있었는지 살펴보도록 하겠습니다. 가장 단순한 것으로 치환 암호(Substitution Cipher, ‘대치 암호’로 번역한 책도 있음)입니다. 아마 여러분도 모르는 사이에 유치원 어딘가에서 이 방법을 사용하셨을지도 모릅니다. 

이 방법의 원리는 일명 ‘치환 대조표’에 각각의 글자들이 어떻게 매칭되는지 기록해두고, 그대로 대치시키는 것입니다. 예를들어 그림처럼 A->C, B->W, C->N 이런식으로 매칭하여 마지막 Z->A 까지 기록을 해두었습니다. 이 규칙에 따라 “BCZA”라는 텍스트를 암호화 한다면 WNAC가 되겠죠? 그렇다면 반대로 복호화는 어떻게 해야할까요? 위에서 설명했듯이 ‘대칭암호’의 특성에 따라, 암호화와 복호화시에는 같은 key(여기에서는 같은 매칭표)를 사용하여 반대로 작업하면 원문 메세지를 얻을 수 있습니다.


이러한 치환방식의 암호 중 가장 널리 알려진 것이 시저 암호(Caesar cipher, 카이사르 암호라고도 발음)입니다. 고대 로마의 지도자였던 줄리어스 시저(라틴어 IVLIVS CAESAR, 율리우스 카이사르)가 군사적으로 중요한 내용을 보호하기 위해 사용했다고 전해집니다. 현재 기준으로는 이것을 ‘암호화’라고 볼수 있느냐에 대해 의견이 분분하지만, 어쨌든 당시에는 꽤나 유효한 수준이었을 것으로 추정되고, 지금까지도 대중들에게 ‘시저암호’라는 명칭으로 널리 알려져 있습니다.

시저 암호의 작동원리는, 알파벳을 순서대로 일렬로 늘어놓은 후, 각각의 알파벳을 일정한 거리만큼 밀어서(Shift) 치환하는 것입니다. 그림처럼 3칸 밀면(shift by 3) A -> D, B -> E, C -> F .. 이렇게 되겠죠? 밀었더니 알파벳 끝자리를 넘어간다면 다시 첫문자인 A로 돌아와서 X->A, Y -> B가 되고, Z는 -> C 가 됩니다. 이 변환표를 기준으로 모든 평문에 적용하여 변환된 암호문을 얻을 수 있습니다. 엄밀하게 말하면, key가 없는 것이어서 학계에서 인정받기 어려운 것입니다. key가 random하게 설정되어있어야 해독하기가 어려울텐데, 고정된 값인 3으로 설정되어있기 때문에 만약 적군이 이 방식이 어떻게 작동되는지만 간파한다면, 쉽사리 원문으로 복구해낼 수 있을 것입니다.


그렇다면 다시 원래의 치환암호로 돌아와서, key가 무작위로 섞여있는 경우에 대해 생각해보도록 하겠습니다. 이것을 해독할 수 있을까요? 아주 쉽게 가능합니다. 이를 자세히 설명드리기 위해 먼저 암호화의 강도를 측정하는 요소로써 key의 범위(space, 얼마나 다양하고 많은 값을 가질 수 있는지)에 대해 언급하려합니다. 키의 스페이스는 굉장히 중요합니다. 예를들어 알파벳은 26개가 있지요? 그렇다면 각각의 순서를 섞을 수 있는 경우의 수는 얼마가 될까요?

순열(Permutation)에 따르면 26!(팩토리얼)이 됩니다. 이걸 계산하면 약 2^88 정도가 됩니다. 그렇다면 이를 이진수의 bit 단위로 약 88bit로 표현할 수 있다는 것인데요, 이정도면 꽤나 큰 사이즈입니다. key space의 크기로만 보면 적절히 괜찮은 정도로 안전한 수준입니다. 


하지만, 키가 2^88가지의 경우의 수임에도 불구하고  전치암호는 상당히 취약합니다. 

왜냐하면, 실생활에서 쓰이는 영어 단어들의 알파벳의 배치가 모두 동일하지는 않기 때문입니다. 따라서, 영문 텍스트에서 통계적으로 어떤 글자가 더 많이 출현하는지의 빈도수를 체크함으로써, 특정 알파벳이 더 가능성이 높다고 추정할 수 있습니다. 이미 밝혀진 연구에 따르면, 사전에 나와있는 표준 영어단어 가장 많이 사용되는 알파벳은'E'로 12.7%를 차지합니다. (별로 크지 않아보일 수 있지만, 만약 모든 알파벳이 동일하게 분포되어있다고 가정한다면 각각은 모두 4%정도라고 예상해야합니다. 이에비해 통계적으로 12%나 차지한다는 것은 매우 유용한 정보입니다.) 이러한 통계적 사실에 입각하여, 치환된 암호문에서 가장 많이 등장하는 알파벳을 찾아본 후, 그것이 사실은 암호화된 'E'일 것이라고 추측할 수 있습니다.

두번째로 높은 빈도를 차지하는 알파벳은  'T'로 9.1%를 차지합니다. 이번에도 암호문에서 두번째로 자주 등장하는 알파벳을 찾아봅니다. 그리고 그것이 아마 'T'일 것으로 예상할 수 있습니다. 그 다음은 'A'가 8.1%인 것을 이용해 또 적용할 수 있을 것입니다. 이렇게 3가지를 찾아냈다고 해봅시다. 하지만 그 다음부터는 나머지 알파벳들의 통계적 추정치가 전부 '도토리 키재기'이므로, 자주 등장하지 않는 Q나 X마저도 비슷한 정도의 확률로 분포합니다. 한 글자의 빈도수만으로 추정하기에는 한계에 도달했습니다. 지금부터는 다른 방법으로 시도하고자 합니다. Diagram이라고 부르는 이 방법은, 글자와 글자가 조합된 빈도수를 통해 추정을 할 수 있다는 것을 전제로 합니다. 이 역시 일반적으로 집계된 통계에 의하면, 영문에서 HE, AN, IN, TH 등의 조합이 상당히 자주 등장합니다. 그러므로 암호문에서 자주 등장하는 연속된 글자조합이 있다면, 아마도 이 네가지 중 하나일 가능성이 큽니다. 

이런식으로 몇번의 시도를 하고, 실패했다면 또 다른 조합으로 시도하는 것을 반복합니다. Diagram다음으로는 Trigram이 있겠죠? 이렇게 계속 시도하다보면 언젠가 전체 key에 대한 대칭표를 만들어낼 수 있을 것입니다. 물론, 시간이 오래 걸리는 어려운 과정일 것입니다. 이러한 공격방식을 암호문 단독 공격(A cipher text only attack)이라고 부릅니다. 단지 암호문만 가지고서 원래 평문의 통계적 성질, 문장의 특성등으로 추정하여 해독해내는 것입니다. 공격자의 입장에서는 가장 쉽고 단순한 공격이면서 동시에 가장 비효율적인 방법이라 할 수 있습니다. 시저암호에서는 별도의 암호화 키가 없으므로 암호문 단독공격만으로도 쉽게 해독될 수 있습니다. 그러므로 현대에서는 사용하지 않는것이 좋습니다.

그럼 로마시대를 지나 르네상스 시대로 넘어가볼까요? 16세기의 비즈네르에 의해 고안된 비즈네르 암호(Vigenère cipher)입니다. 여기에서는 암호화에 사용할 키를 단어형태로 지정합니다. 예를들어 'CRYPTO'라는 여섯글자짜리 글자를 사용하여 설명하도록 하겠습니다. 우선 원문 메세지인 "WHAT A NICE DAY TODAY"를 준비하고, 그 밑에 암호화 키인 CRYPTO를 적습니다. 원문의 길이만큼 반복해서 여러번 이어서 적습니다. 그 다음에는 원문의 글자와 key의 알파벳을 각각 1부터 26사이의 숫자로 생각하고 더해서 적습니다. 예를들면 Y(25)+A(1)는 Z(26)가 되고, T(20)+A(1)은 U(21)이 됩니다. 만약 더한 합이 Z보다 크게되는 경우에는 다시 A로 되돌아간다고 생각하면 됩니다. 이것을 수식으로 표현하면 나머지 연산(Modular Arithmetic)을 사용하여 %26으로 나타낼 수 있습니다. 비즈네르 암호의 복호화 역시 아주 간단합니다. k + m = c 이므로, m = c - k 가 되겠죠? 암호문 메세지를 준비하고 그 밑에 동일한 암호화 키를 반복에서 적은 후, 두 값을 빼면 원래의 평문을 얻을 수 있습니다.


비즈네르 암호를 해독하는 것은 어떨까요?(역자 주 : '복호화'는 암호문으로부터 공식적으로 원문을 복구하는 과정이라면, '해독'은 공격적인 방법으로 암호문으로부터 원문을 찾아내려는 시도) 시저암호에서 사용한 공격방법을 비슷하게 응용함으로써 가능합니다. 우선, key의 길이를 알고있다고 가정해봅시다. 이 경우에서 key는 6자리입니다. 이를 토대로 암호문을 6글자씩 끊어서 묶음을 만들어봅시다. 그리고 이 묶음의 첫번째 글자들끼리만 모아서 비교해봅시다. Z, L, W가 되겠네요. 이 세 글자는 전부다 동일한 암호화 키로 변환된 글자입니다. 이런식으로 묶음의 첫번째 글자들만 무수히 많이 모았을 때, 그중 가장 많이 등장하는 알파벳이 있다면 그것의 원문 알파벳은 'E'일 가능성이 큽니다. 위에서 언급했듯이, E는 영어에서 가장 많이 사용되는 알파벳이기 때문입니다. 그러므로 만약 가장 많이 등장한 알파벳이 H라면, H = E + Key 일 것이고, key는 H(8)-E(5)이므로 key가 C(3)이라고 추정할 수 있습니다. 키워드의 첫번째 글자를 알아냈다면, 이제 이 작업을 두번째, 세번째 글자에 대해서도 동일하게 반복합니다. 그리하여 6글자의 키를 모두 알아낼 수 있습니다. 뽑아낸 키를 사용하여 암호문을 원문으로 되돌릴 수 있습니다.


만약, '키의 길이를 알고있다'는 가정이 없을때는 어떻게 해야할까요? 그렇더라도, 별로 큰 문제가 되지는 않습니다. 일단 키의 길이가 1이라고 가정하고 무작정 시도해봅니다. 틀리면 다음엔 2, 다음엔 3.. 이렇게 지속하다보면 결국엔 찾아낼 수 있습니다. 비즈네로 암호 역시 '암호문 단독 공격'만으로 뚫리기 십상입니다. 이제는 다른 새로운 암호가 필요한 때입니다.

그래서 19세기에 새롭게 등장한 암호를 살펴보겠습니다. 이제야 비로소 전자적인 방식을 사용하기 시작합니다. 일명 ROTOR라고 부르는 전자적 모터를 사용해서 암호화를 구현하는 방식을 설계하게됩니다. 이 사진에 나와있는 것처럼 모터를 1개만 사용한 것을 ‘Hibber machine’이라고 부릅니다. 암호화 키를 이쪽 디스크에 저장해두고, 사용자가 입력판에 키를 하나 누를때마다 눈금(notch)이 회전하게 만드는 방식입니다. 그러는 동안 진행되는 과정을 치환표에 저장해두게 됩니다. 이를 위의 그림과 같이 도식화 할 수 있습니다. 첫 글자로 ‘C’를 입력했을 경우, 그것이 ’T’로 치환된다는 내용을 저장할 것입니다. 그리고 rotor가 한번 회전하여 눈금이 변화됩니다. 이렇게 된 후에는 그 다음줄의 글자가 치환표에 대응되게 됩니다. 세번째도 마찬가지입니다. 만약 연속으로 C를 세번 누른다면, 처음에는 T, 다음에는 S, 마지막은 K에 대응될 것입니다. 이것이 싱글-로터 머신이 작동하는 원리입니다. 하지만 이 역시 글자의 통계적 확률을 이용한 암호문 단독 공격에 쉽게 뚫리고 말았습니다. 빈도공격과 통계적 공격인 이때까지도 상당히 유효한 공격이었습니다. 그래서 이후에 등장하는 암호들은 점점 더 복잡해지기 시작했습니다.

드디어 그 유명한 ‘에니그마’가 등장합니다. 에니그마는 그리스어로 ‘수수께끼’를 뜻합니다. 아마 많은분들이 익히 들어보셨을거라 생각합니다. 에니그마는 로터머신의 조금더 복잡한 형태라고 이해하시면 됩니다. 최소 3~5개의 로터를 사용하는 것이지요. 그렇기 때문에 에니그마에도 다양한 버젼이 있습니다. 위의 사진은 3개의 로터를 사용하는 에니그마입니다. 각각의 로터로 인해 26^3의 키 space를 갖게됩니다. 또한, 입력할 때에 각각의 로터들이 회전하는 비율이 저마다 다르게 설정되어 있기 때문에 쉽게 추론하기 어렵습니다. key의 크기를 계산해보자면 26^4이고, 대략 2^18이 됩니다. 이는 현대적 기준에서보면 매우 작은 수준이기 때문에 전수조사 공격(Brute-force Attack)으로도 쉽게 무력화시킬 수 있습니다. 하지만 에니그마가 사용되던 당시에는 굉장히 어려웠던 것입니다. 그리하여 세계대전에서 독일의 군사기밀을 다룰 때 아주 유용하게 사용되었습니다. 하지만 안타깝게도 오랫동안 난공불락으로 여겨졌으나 폴란드의 암호국, 프랑스, 영국의 블레츨리 파크(Bletchley Park)의 암호학자들에 의해 해독되고 말았습니다. 아마 이때부터 ‘기계방식의 암호’의 시대는 끝이났다고 볼수 있습니다. 이후로는 디지털 방식의 암호가 급히 진전되기 시작합니다. 정부도 이러한 목적으로 컴퓨터의 중요성을 깨닫게 되었고, 덕분에 디지털 산업이 발전할 수 있는 모태가 되었습니다.

이처럼 컴퓨터와 암호산업이 발전하였고, 데이터 암호화 표준(Data Encryption Standard)의 필요성이 대두되기 시작했습니다. 곧 미국 국립표준기술연구소(NIST)등 정부차원에서 표준화를 위한 시도를 하였고, 1974년 IBM에서 개발하고 제안한 알고리즘이 채택되었습니다. 이는 2^56 크기의 키 스페이스를 가졌는데, 당시에는 매우 풀기 어려운 수준이었습니다. DES에서 또하나 놀라운 특징은, Rotor machine이 한번에 한 글자씩 암호화했던 것에 비해, DES는 한번에 8글자(즉, 2^8 = 64bit)씩 처리할 수 있었다는 점입니다. 구체적인 구현은 다음번 강의에서 진행하도록 하겠습니다. 하지만 DES 역시 현재는 그 취약성이 드러났고, 전수조사공격(Brute Force Search)로 손쉽게 해독될 수 있음이 증명되었습니다. 키 스페이스가 좁기 때문에 현재의 컴퓨팅 파워로는 매우 짧은시간안에 모든 경우의 수를 조사해볼 수 있기 때문입니다. 그러므로 DES는 안전하지 않으며, 여러분의 프로젝트에서 사용하지 않기를 권고합니다. 안타깝게도 많은 골동품 수준의 프로그램들(Legacy system)에서는 당시에 유행했던 DES를 여전히 사용하고 있는것으로 보입니다. 부디, 앞으로는 절대 사용하지 마시길 바랍니다.


(역주 : DES란 최초에 IBM에서 제안했던 특정 알고리즘만을 지칭하는 것이 아니라, ‘표준’을 의미합니다. 따라서 IBM의 ‘루시퍼’ 암호가 탈락된 후 2001년에 공모전을 통해 새로운 표준으로 AES가 채택되었으며, 지금 사용되는 DES는 AES입니다.) 


요즘에 사용되는 암호들(Salsa20 등)은 보통 128bit 키를 사용합니다. 이전것들과 비교하면 꽤 커졌지만, 언젠가 이것들도 부족해질 것입니다. 지난 과거역사동안 다양한 암호 알고리즘이 많았지만, 그중 일부분만을 선택적으로 소개해드렸습니다. 역사 이야기는 이쯤해두고, 이제부터는 본격적으로 암호의 기술적인 부분을 언급하고자 합니다. 또한 현대적인 암호화 표준에 대해서도 다음시간부터 자세히 다루도록 하겠습니다.

CPUU님의 창작활동을 응원하고 싶으세요?