단일 치환 암호법을 복호화하는 방법

암호의 역사

보안 프로토콜의 핵심 원천 기술의 역사에 관하여 살펴본다.

시저암호 (Caesar cipher)

로마 장군 줄리어스 시저가 사용하였다는 암호 (기원전 100년경)
평문으로 사용되는 알파벳을 일정한 문자 수만큼 "평행이동" 시킴으로써 암호화

주어진 키만큼 평행이동 시킨 문자로 암호화 하여 암호문을 생성하고 있다.

복호화는 주어진 키만큼 역으로 계산하여 복호화 하면 되기 때문에 대칭키암호에 해당된다고 볼 수 있다.

만약 메시지가 시저 암호를 통해 암호화 되었다는 정보를 도청자가 알았다면 영어 알파벳은 총 26개이기 때문에 쉽게 모든 키 후보를 대입하여 평문을 도출할 수 있다. => 전사 공격 (brute-force attack)

전사 공격을 막을 수 있는 암호가 없을까?

평문을 구성하는 알파벳을 치환표(비밀키)에 따라 변환시킬 수 있다. 치환표는 전단사함수 (1:1대응)여서 모든 문자에 대응되는 다른 문자가 존재한다.

복호화 과정에 있어서 치환표는 비밀키에 해당되기 때문에 반드시 필요하다. 전사공격에는 안전하지만 평문에 등장하는 문자의 빈도가 암호문에 등장하는 문자의 빈도와 동일하다는 약점이 있다.

시저암호는 키공간이 작아서 brute-force 공격이 가능했다. 키 공간은 암호에서 사용할 수 있는 모든 키 후보들의 집합이며 전체 키 후보들의 개수를 키 공간의 크기라고 부르며 키공간의 크기가 클 수록 전사 공격에 소요되는 시간이 늘어난다. 따라서 단일치환암호는 키공간의 크기(26!)가 크기 때문에 brute-force로 뚫기 어렵다.

단일치환암호가 안전한 것만은 아니다. 원문과 암호문에 등장하는 문자의 빈도 수가 동일하기 때문에 빈도 분석에 취약하다. 빈도 분석은 암호문 속에 영어 알파벳 출현 빈도를 분석하고 자주 등장하는 단어를 이용하여 치환표를 도출해낸다.

예시를 살펴보자 다음은 단일 치환 암호로 암호화된 암호문이다. 해석 하려면 어떻게 해봐야 할까?

문자열을 유심히 살펴볼 것이다. 예를 들어 가장 많이 사용되는 관사 "the"는 항상 동일한 알파벳으로 변환되었을 것이다. 위에서 MEY가 반복되는 것을 미루어 보아 "the" 일 가능성이 있다.

영어 알파벳의 등장 빈도를 살펴볼 필요가 있다. 앞에서 언급듯이 평문과 암호문의 문자열 등장 빈도는 동일하기 때문이다. 통계적으로 일반적인 문자 등장 빈도는 다음과 같다.

알파벳 e가 12.49%로 높은 빈도로 등장하고 있음을 알 수 있으며 알파벳 t도 10% 육박하는 빈도로 등장하고 있다.

통계에 따라 가장 많이 등장하는 영문자를 e로 바꿔본 후에 만이 등장하는 관사 the를 생각하여 다시 문자를 바꿔본다.

이후에는 단어에 기반하여 추정을 하며 역추적 해본다. (try an-error)

위와 같은 방식으로 단일 치환 암호의 치환표를 찾아낼 수 있었다. 실제 원문은 이솝 우화인 여우와 포도이야기 였음을 알 수 있다.

빈도 분석을 통항 암호 해독에는 다음과 같은 특징이 있다.

빈도가 높은 문자 뿐만 아니라 빈도가 낮은 문자도 단서
단어의 맥락을 알면 그것도 단서
암호문이 길면 해독이 용이함
같은 문자가 연속해서 등장하면 그것 또한 단서

빈도 분석에 강한 암호를 만들어 낼 수 없는가?

다중 치환 암호가 있다.

평문에 등장하는 문자의 빈도와 암호문에 등장하는 문자의 빈도를 다르게 만드는 암호 알고리즘
비제네르 암호 (Vigenere cipher)
힐 암호 (Hill Cipher)
에니그마 기계 (Enigma machine)

다중 치환 암호는 다음과 같이 동작한다.

비제네르 암호 (Vigenere cipher)

a, b, c, d, e, f, g h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z
평문: kookmin university
비밀키: abc (1, 2, 3) 평행이동
암호문: lqrlol

힐 암호

영어 알파벳을 숫자로 대응시킨다.
키는 n x n 크기의 행렬로 구성되어있다.
평문을 키와 행렬곱 시킨다.

복호화를 위해 키는 반드시 역행렬이 존재하는 행렬을 사용해야한다.

에니그마

독일의 세르비우스(Arthur Scherbius)가 20세기 초에 발명한 암호화/복호화를 수행하는 기계
에니그마는 독일어로 "수수께끼"를 의미
회전하는 원반과 전기회로를 써서 강력한 암호를 만들고자 시도
발명 당시에는 에니그마를 상용으로 사용
2차 세계대전 때 독일군의 비밀통신 수단으로 사용

키보드를 통해 평문을 입력하면 네트워크를 통해 암호문이 전송된다.

앨리스와 밥은 애니그마 기계가 있어야 암/복호화를 할 수 있다. 또한 날짜별 코드북을 공유하고있으며 암호 기술에서 비밀키에 해당되어 제3자는 모르고 있어야 한다.

에니그마는 단일 치환 암호를 반복해서 사용하여 암호화를 시키는데 에니그마의 설정에 날짜별 코드북이 사용된다. 따라서 하루만 사용할 수 있는 암호가 된다. 매번 알파벳을 입력할 때마다 치환되는 알파벳이 갱신된다. 즉 알파벳을 입력할 때마다 다른 문자로 치환된다는 의미이다.

우리가 비밀통신을 하는 방법은 크게 두가지가 있다.