빈도분석 (암호)
암호학에서의 빈도분석(頻度分析, frequency analysis 또는 counting letters)이란 평문과 암호문에 사용되는 문자 또는 문자열의 출현빈도를 단서로 이용하는 암호해독법을 말한다. 평문 언어의 통계적 특징을 전제로 하여, 암호문만을 사용해서 해독을 진행하기 때문에, 암호문 단독공격으로 분류된다.
개요
편집평문 한 글자를 다른 글자(또는 숫자나 기호 따위)로 1대1로 변환해서 암호문을 작성하는 단일 환자식 암호에는, 평문과 암호문으로 대응하는 문자의 출현빈도가 일치한다는 특징이 있다. 일반적으로, 평문 문자의 출현빈도는 특정 문자에 치우쳐 있으며, 문장에 상관 없이 거의 일정하기 때문에, 평문 문자의 출현빈도와 암호문 문자의 출현빈도를 대조하는 것으로 평문과 암호문의 문자 대응관계를 특정할 수 있으며, 따라서 암호문을 해독할 수 있다.
사용되는 문자의 종류와 그 출현빈도는 언어에 따라 달라지기 때문에, 빈도분석을 하는 것으로 평문의 언어를 특정할 수 있다. 더욱이, 조직이나 개인에 따라서도 출현빈도에 차이가 있는 경우가 있으며, 빈도분석의 정밀도를 향상시키는 데에 이용된다. 또한, 암호문은 문자로 구성된다고 한정할 수 없으며, 숫자와 기호가 함께 쓰이는 일도 있다. 예를 들면, 평문의 한 글자에 두 자릿수를 대응시키는 폴리비오스의 암호표가 있다. 이 경우에는 암호문의 두 자릿수 숫자가 평문의 한 글자에 대응하는 것을 추정해놓은 상태에서 빈도분석을 시도하게 된다.
빈도분석이 유효한 것은 주로 고전암호의 환자식 암호이며, 9세기에 아라비아인 킨디가 집필한 암호문서의 해독에 관한 수기에 이 해독법의 기술(記述)이 있다. 15세기 즈음에는 르네상스를 통해 유럽에도 퍼져, 비즈네르 암호와 같은 다표식 환자(多表式換字)를 고안하는 동기가 되었고, 20세기에 이를 때까지 새로운 암호방식의 제안과 빈도분석을 바탕으로 하는 해독법의 개량이 되풀이되었다. 20세기 초두에 개발된 기계식 암호에 의해, 단순한 빈도분석은 적용하기 곤란해졌으며, 암호해독은 알고리즘의 수학적 분석을 수반한 연구로 변질해갔다. 현대암호에서는 암호문 단독공격보다도 복잡한 기지평문(旣知平文)이나 선택암호문 조건에서도 안전함을 목표로 설계되어, 이 분야에서는 평문의 언어적인 특징을 단서로 하는 빈도분석은 극복되었다.
빈도분석 방식은 암호를 해독하는 데에만 쓰이는 것이 아니라, 고대문자의 해독에도 이용된다.
적용
편집
영어의 일반적인 문장의 경우, 알파벳 수를 세어 픽토그램을 작성하면(표 참조), 대개 e, t, a, o, i, n, …, j, x, q, z의 순으로 출현하는 것을 알 수 있다. 같은 방식으로 두 문자(연접문자)인 경우, t-h, h-e, i-n, e-r, ... , 세 문자의 경우에는 t-h-e, a-n-d, i-n-g, i-o-n, ... 따위의 순으로 출현빈도가 높다고 알려져 있다. 연접문자의 경우, 'q'의 다음에는 'u'가 출현한다는 것 같은 조건이 붙은 출현빈도에 특징이 있는 경우도 있다. 이 특징을 연접특징이라고 한다. 나아가, 띄어쓰기가 판명된 경우에는, 단어의 출현빈도를 이용할 수 있다.
암호해독에는 출현빈도만이 아닌, 출현간격(반복특징)도 귀중한 단서가 된다. 반복특징에는 자기반복, 상대반복, 일치반복, 문내반복이 있다. 자세한 것은 일치반복률을 참조.
평문 문자의 출현빈도는 문장에 따라 다소 고르지 않을 수 있으며, 암호문이 적은 경우에는 출현 오차도 많아진다. 암호를 사용하는 조직에서는, 고유명사나 문체의 영향으로 일반적인 출현빈도와 달라지는 경우도 있으며, 의도적으로 조작하는 것도 가능하다. 이를테면, e를 한 번도 사용하지 않고 쓰인 소설인 『실종』(조르주 페렉著)이 있다.
해독작업은 출현빈도 따위의 통계량을 단서로 한 문자씩 평문의 문자를 추정하여, 모순이 생기면 다시 돌아가 다음 문자를 시험하는 것을 반복한다. 문자 추정은 출현빈도에 특징이 있는 문자부터 할당하고, 그러면 출현빈도가 높은 문자와 낮은 문자 모두 이용할 수 있다. 문법 상 전후의 단어를 통해 의미를 고려하여 문자으 경우의 수를 좁혀나가는 경우도 있다. 이러한 빈도분석을 실제로 사용하는 해독요원에게는 단순히 문자를 세는 작업을 해낼 능력과 십자말풀이를 푸는 듯한 센스가 요구된다. 제2차 대전 때에 영국과 미국은 신문에 십자말풀이를 게재해서, 암호해독 요원을 모집했다. 문자를 세는 작업의 기계화는 제2차 대전이 되어서 IBM의 기계를 처음으로 시작되었다.
문자의 세계에서는 「황금충」(포, 1843년)이나 「춤추는 인형」(도일, 1903년) 같은 암호 소설에서 이러한 빈도분석의 테크닉이 수수께끼 풀기의 한 장면으로 그려져 있다.
역사
편집빈도분석에 관한 최고(最古)의 기록은 9세기의 킨디가 집필한 암호문서의 해독에 관한 수기이다. 이것은 암호해독법에 관한 최고(最古)의 기록이기도 하다.
이 해독법은 르네상스에 접어들면서 15세기에 유럽에도 퍼져갔다. 당시의 유럽에서는 시프트 암호를 복잡하게 하여 변환 규칙이 간파되지 않도록 고안된 열쇠달린 환자(換字) 따위가 사용되고 있었다. 빈도분석은 환자표가 얼마나 복잡해도 분석가능하며, 이렇게 고안된 것들을 전부 무효화할 수 있다. 16세기에는 외교관에 맞춘 암호문의 대부분이 타국에 의해 해독되었다고 한다. 이렇게 빈도분석을 통해 단일 환자암호의 안전성을 잃게 되면서, 빈도분석에 대한 대책으로 다음과 같은 방식이 고안되었다.
- 동음환자(homophonic substitution cipher) - 평문의 한 글자(e 등)에 복수의 암호문 글자(x, q, z 등)을 대응시켜, 그 하나를 임의로 선택하여 변환하는 것으로, 암호문의 출현빈도가 특정 문자에 치우치는 것을 줄일 있다. 1401년에 동음환자가 사용된 기록이 있다.
- 다표식 환자(polyalphabetic substitution cipher) - 비즈네르 암호(1586년) 따위. 복수의 변환표를 열쇠에 따라 치환하여 사용한다. 평문 한 글자에 대응하는 암호문 글자가 변환표를 따라 치환되어 변화하기 때문에, 암호문 문자의 출현빈도가 교반(攪拌)되어 특정 문자에 치우치는 것을 줄일 수 있다.
- 철자환자(polygraphic substitution cipher）- 플레이페어 암호(1854년)와 힐 암호 등. 복수의 문자를 복수의 문자에 대응시킨다. 두 글자 것은 digram, 세 글자 것은 trigram이라고 부른다. 암호문의 한 글자 단위의 출현빈도를 착란(錯亂)시킬 수 있다.
이러한 신형 환자식 암호, 특히 다표식 환자는 수작업으로 하기에는 암호화와 복호처리가 복잡하므로 초기에는 경원시되었지만, 18세기 즈음부터 다수 채용되면서, 비즈네르 암호는 19세기 중반까지 300년 가까이 해독불가능하다고 여겨졌다. 빈도분석으로 해독할 수 없는 환자식 암호가 퍼지면서, 그것을 꺾을 수 있도록 복수문자의 출현빈도의 고려와 문자열 주기의 특정과 같은 빈도분석을 개량하는 고안도 이루어졌다.
- 카지스키 테스트(19세기) - 1863년에 프로이센의 프리드리히 카지스키가 출판한 서적에서 공개(나중에 찰스 배비지가 1854년경에 발견한 것으로 판명)되었다. 비즈네르 암호는 단순한 빈도분석으로는 해독할 수 없지만, 동일 문자열의 출현주기에서 문자열 주기를 특정하는 것으로 빈도분석을 적용할 수 있다(단순한 시프트 암호로 귀착할 수 있다)는 것이 지적되었다. 다표식 환자에서는 동일 문자열("the"와 같은 문자의 나열)에 대응하는 암호문은 문자열의 길이만큼 바리에이션이 있으며, 문자열 주기에 따라 선택할 수 있기 매누에 암호문 속에 동일한 나열이 출현하는 간격은 (우연히 일치하는 경우를 빼면) 문자열 주기의 공배수가 된다. 문자열 주기의 공배수가 되는 값을 여러 개 모아서 최대공약수를 구하면 문자열 주기를 얻을 수 있다. 주기판정법이라고도 한다.
- 일치반복률(20세기) - 1922년에 미국의 프리드먼이 고안. 문자열 주기를 특정하여 다표식 환자에 빈도분석을 적용할 수 있도록 하는 점은 카지스키 테스트와 같지만, 문자열 주기의 길이를 통계량적으로 다루는 점이 다르다. 암호문에서 임의로 두 문자를 고를 때, 그 두 문자가 일치하는 확률을 문자열 주기의 길이의 기준으로 한다. 확률적인 지표이기에 문자열 주기를 특정할 수 있는 것은 아니다.
개량판도 포함한 빈도분석에 대하여 십분 안전하다고 말할 수 있는 환자식 암호가 실현된 것은, 로터식 암호기(기계식 암호의 일종)가 개발된 20세기 초두가 되고나서의 일이다. 에니그마 암호기에서는 문자열 주기가 26^3=17,576(로터가 3장인 경우)으로 충분이 길어지도록 설계되었다. 이러한 암호기의 대부분도 암호기의 사양 상 특징이나 암호문의 통계적 성질을 분석하는 것으로 해석되어갔다.
참고 문헌
편집- 도로시 E. 데닝『Information Warfare and Security』, 1999년 (2.2.1 단문자 빈도분석）
- 마쓰이 기네오『コンピュータによる 暗号解読法入門』(컴퓨터에 의한 암호해독법 입문), 모리키타 출판, 1990년 (1.6 반복조사 pp.29- 등)