암호학의 과거와 미래 : 우리는 막을 것이다. 늘 그랬듯이 1편

1. 들어가며

유명 SF영화 중 ‘인터스텔라’라는 근미래 보다 조금 더 미래를 배경으로 한 영화가 있다. 점점 황폐해져가는 지구를 대체할 인류의 터전을 찾기 위해 새롭게 발견된 시공간의 틈을 통해 항성 간(Interstellar) 우주 여행을 떠나는 이야기이다. 이 과정에서 불가항력인 상황이 계속 주어지고 이것들을 어떻게 해서든 해결해 나가기 때문에 캐치프레이즈로 ‘We will find a way. We always have’라는 문장이 자주 쓰인다. 인류는 어떠한 문제가 닥치면 언제나 그랬듯이 방법을 찾아왔다. 이러한 과정을 봤을 때 암호학의 발전과도 유사하다고 느꼈다. 암호학 역시 어떠한 문제가 발생되면 그것을 해결해 오는 방식으로 발전돼 왔기 때문이다.

2. 고대암호와 근대암호

가족들과의 대화 같은 사적인 대화는 다른 사람들에게 공개하기가 꺼려진다. 고대 로마에서도 마찬가지였다. 과거 로마의 황제였던 ‘줄리어스 시저’는 가족과 연락을 하기 위해 서신을 보내곤 하였는데 전달 과정 중 그 내용들이 조금씩 새어 나가는 문제가 발생하였다고 한다. 그래서 ‘줄리어스 시저’는 고민 끝에 모든 단어의 알파벳을 세글자씩 밀려 쓰는 방법으로 글을 암호화하여 작성하였다고 한다. 즉 A는 D로, B는 E로 바꿔 쓰는 방식이었다. 이러한 방식은 암호문을 원래의 문장으로 되돌리기, 즉 복호화하려면 문자를 좌측으로 세글자씩 당겨 원래의 문장인 평문을 얻을 수 있다. 송신자와 수신자는 몇 문자씩 이동할지를 사전에 정의하고 공유하여 암호문의 기밀성을 유지하였다. 이후 이러한 방식을 암호학계에서는 ‘시저 암호’라고 부르게 되었다고 한다.

자료2. ‘시저 암호’의 암호화 방식

이렇게 다른 문자로 바꿔버리는 ‘시저 암호’의 ‘치환(Substitution)’ 암복화 방식은 ‘고대 암호’의 주된 형태이며 이는 몇 자리씩 시프트 하였는지만 알면 금방 해독이 되어버리는 취약성을 가진다. 그렇기 때문에 ‘근대 암호’에 들어서면서 이러한 문제를 해결하기 위해 ‘치환’ 이외에도 문자의 위치를 섞어버리는 ‘전치(Transposition)’라는 개념을 함께 도입하게 되었고 이것을 응용하여 현재까지도 계속 쓰이고 있다. 그렇지만 ‘치환’과 ‘전치’만을 주로 사용했던 '근대 암호' 초기에는 결과적으로 해독에 시간이 더 걸렸을 뿐이지 완벽하지는 않았다.

자료3. ‘치환(Substitution)’과 ‘전치(Transposition)’

알파벳은 A부터 Z까지 26자가 있는데 각 알파벳들의 출현 빈도를 조사해보면 보편적으로 자주 쓰이는 알파벳 A, E, T를 알 수 있다[자료4]. 예를 들어 암호문에서 X, Y, Z가 빈번하게 자주 사용된다면 이것들을 A, E, T라고 가정해보고 분석해 보는 것은 효율 높은 해독 방법이 될 수 있다. 즉, 다시 말하면 취약한 암호 방식이라고 여길 수 있다. 이러한 이유로 일정한 규칙성을 갖고 다른 문자로 바꾸는 ‘치환’과 문자 또는 단어의 위치를 섞어버리는 ‘전치’는 문장의 구조에만 영향을 주었기 때문에 과거에는 언어학자가 암호해독의 주를 이루었다. 그렇지만 암호 해독을 자동으로 할 수 있는 고성능 연산 기기가 등장하고 수학의 발전에 의해 암호의 안전성을 확률적으로 표현하기 시작함에 따라 암호해독은 점차 수학자가 주를 이루게 되었다.

자료4. 각 알파벳의 출현 빈도 분석 그래프

3. 현대암호

인류의 과학 기술은 전쟁을 통해 비약적으로 발전하였듯 암호학도 전쟁을 통해 크게 발전되었다. 제2차 세계대전 당시 독일군은 자체 개발한 암복호화 기기 ‘에니그마’를 보안 통신에 사용하였다. ‘에니그마’로 생성된 암호문은 암호 규칙을 모를 경우, 해독 시 약 18억 5천만 가지의 경우의 수를 만들어 낼 수 있을 정도의 놀라운 성능을 자랑하였고 암호 규칙이 24시간마다 바뀌기 때문에 해독 불가능한 암복호화 기기로 생각되었다. 그렇지만 연합군은 ‘에니그마’를 해독하기 위해 많은 노력을 기울였고 결국 영국의 ‘앨런 튜링’이 최초의 디지털 컴퓨터를 만들어 내어 18억 5천만 가지라는 경우의 수를 뚫고 ‘에니그마’ 해독에 성공하였다. 그 결과 세계대전 향방에 결정적인 영향을 끼쳤다. 이후 ‘앨런 튜링’에 의해 ‘튜링 머신(Turing Machine)’이라는 개념이 창안되고 현대 컴퓨터의 기본 모델이 정립되며 컴퓨터과학에 초석을 다지게 된다.

자료5. ‘에니그마’의 모형

이렇듯 컴퓨터의 발전은 암호학에 있어서 매우 중요한 부분을 차지한다. 컴퓨터는 반복하여 대량의 연산을 매우 빠르게 대신 처리해 주는 기기이기 때문에 매우 큰 경우의 수를 갖는 암호 해독에 있어서 많은 영향을 끼친다. 나아가 해독 불가능한 암호 알고리즘을 개발, 검증하기 위해 쓰이기 때문에 컴퓨터의 발전은 암호학의 발전으로도 이어진다.

이후 ‘현대 암호’에 들어서는 과거의 암호 알고리즘으로는 기밀성을 유지하기 어렵고 비효율적이라는 것을 깨닫고 본격적으로 키Key라는 개념을 도입하게 된다. 키를 도입함으로써 ‘현대 암호’에서 가장 큰 특징 중 하나인 ‘비선형(Non-linear)’ 성질을 갖게 되어, 과거 비효율적이던 암호 알고리즘에서 매우 간단하고 효율 좋은 암호 알고리즘으로 탈바꿈하게 된다.

과거 암호 알고리즘에서 사용되던 ‘치환’과 ‘전치’는 기본적으로 변화하기 전의 문자와 후의 문자가 서로 1:1로 매칭이 된다. 예를들어 세글자씩 밀려쓴 ‘시저 암호’의 경우, A는 D와 1:1매칭이 된다. 이러한 관계를 ‘선형(Linear)’이라 하고 1:n 매칭이 되는 것을 ‘비선형(Non-linear)’이라고 한다.