비제네르암호 공략법 - 1 - <카지스키 분석>

물론 오늘날의 현대적 기법을 사용하면 비제네르 암호는 공격할 수 있으며 암호문이 적절하게 길다면 통계적인 방법으로 여러 가지 규칙성을 알아 낼 수 있다. 이 규칙성을 이용하여 암호에 사용된 키 단어를 얻을 수 있다. 비제네르 암호를 성공적으로 공격하는 방법은,프러시아 제독 카지스키(Friedrich Wilhelm Kasiski, 1805-1881)가 1863년 처음으로 발표하였다.

미국인 프리드만(William Frederick Friedman, 1891-1969)은 카지스키의 방법을 보완하는 또 다른 방법을 고안했는데, 두 방법 모두 키 단어의 길이를 결정하는 것이 목표이다.

이 2가지 방법은 암호학적으로 아주 중요한 공격법이므로 지금부터 자세히 소개한다.

이 공격법을 최초로 발표한 사람이 카지스키이지만, 사실  암호공격을 가장 먼저 시도한 사람은 현대 컴퓨터 이론의 선구자로 유명한 영국의 배비지(Charles Babbage, 1792-1871)이다. 특히 배비지는 카지스키가 공격법을 발표하기 9년전에 이미 이 방법을 사용했었다.

 Mr. X가 그림 2.1와 같은 암호문을 입수했고, 어떻게 알았는지는 모르지만 비제네르 암호법을 사용했음을 알고 있다고 하자. Mr. X는 다음과 같은 카지스키, 프리드만 방법을 사용하여 키 단어에 관한 정보를 알아 낼 수 있다.
다음 암호문을 보자.

그림 2.1 암호문

 암호문을 보고 어떤 정보를 얻을 수 있을까? 일정한 문자열이 반복해서 나타나고 있는데 알아보겠는가?

그림 2.2 같은 문자열

기본 아이디어는 다음과 같다. 우선 평문에서 특정한 단어(예 THE)가 반복되어 사용되었다고 해도 이에 대응하는 암호문은 각자 다를 수도 있다. 왜냐하면 같은 단어라 해도, 키 단어의 서로 다른 문자에 의해 암호화될 수도 있기 때문이다. 그러나  같은 단어가 여러번 반복되면, 그 단어의 첫번째 문자가 같은 키 단어 문자로 암호화되는 경우가 있다. 그렇게 되면 그 단어에서 사용한 다른 문자도 같은 모양으로 암호화되어 반복해서 나타난다. 예를 들어 THE가 암호화되어 VXA, GYJ, ... 등 여러 형태로 암호화된다고 해도 많은 횟수로 반복된다면 VXA도 여러번 나타나고, GYJ도 여러 번 나타난다. 그리고 이들이 반복해서 나타나는 간격은 키 단어 길이의 배수일 것이다.

그림 2.3 카지스키 테스트

● 평문의 문자열이  일정한 간격(키 단어 길이의 배수)으로 반복되면, 암호문의 문자열도 일정한 간격으로 반복된다.

Mr. X가 암호문에서 반복되는 문자열을 발견하면, 그 문자열들 사이의 거리가 바로 키 단어 길이의 배수라는 것을 짐작할 수 있다. Mr. X 입장에서는 ``문장이 길수록 공격하기 쉽다''. 암호문에서 한 문자가 반복되는 것을 관찰하는 것은 키 단어 길이를 추측하는데 아무런 도움이 되지 않는다. 그 이유는  평문에서 서로 다른 문자가 다른 키 단어로 암호화되면서 우연히 같은 문자로 암호화될 수도 있기 때문이다. 마찬가지로 두 문자열도 우연히 반복될 수 있다. 하지만 3개 이상인 문자열이 반복된다면 그때부터는 키 단어 길이에 대한 많은 정보를 얻을 수 있다. 그림 2.1의 암호문에서 주의 깊게 살펴보아야 할 문자열들을 표시해 보면 표 2.1와 같다.

반복되는 문자열들이 여러 개가 있는데 중요한 몇 가지 문자열들의 반복 주기를 살펴보자.

OPVF	155	5*31
LVV	20	2*2*5
MGY	20	2*2*5
DVLQ	50	2*5*5
NZZ	25	5*5

표 2.1

표 2.1에서 설명한 바와 같이 이 거리들의 최대 공약수는 5이고, 성급한 공격자라면 키 단어 길이가 5라고 단정할 수도 있다. 사실 대부분의 경우 카지스키 테스트만 사용해도 된다. 그러나 우리의 Mr. X 는 아주 영악하기 때문에 『키 단어 길이가 5라는 강력한 증거가 있다』라는 정도로만 생각한다. 왜 그는 신중해야 하는가? 두 가지 이유가 있다.

 ● 실제 키 단어의 길이가 5라고 해도, 암호문에서 같은 문자열이 5의 배수가 아닌 거리만큼
    떨어져서 반복될 수도 있다. 이런 경우 잘못하면 최대공약수가 1이라고 착각할 수도 있다.
    예에서도 ZZK가 반복되는 거리는 6이다. 그래서 거리들의 최대 공약수를 기계적으로 계
    산할 것이 아니라 약간은 유연하게 사고할 필요가 있다. 전혀 엉뚱한 거리값은 무시할 수
    도 있다.

●  최대공약수가 5라고 해도 실제 키 단어 길이는 10이나 15일 수도 있다. 카지스키 테스트는  키 단어 길이의 약수나 배수가 얼마라는 정도까지 알아내는 데 그친다.

이러한 이유가 있으므로 지금부터 키 단어 길이에 대한 중요한 단서를 찾을 수 있는 또 다른 방법을 설명한다. 대부분의 경우 이 두 가지 방법을 함께 사용하면 키 단어의 길이를 거의 정확하게 알아낼 수 있다.

출처 - http://system.kcu.ac/opendept/crypto/sub/sub02_1.htm