비제네르암호 공략법 - 2 - <프리드만의 암호공격>

이 방법은 1925년 미국의 유명한 암호 해독가인 프리드만(Willam Frederick 프리드만)이 고안했다. 이 테스트의 요점은 바로 『암호문에서 임의로 두 문자를 선택했을 때, 두 문자가 서로 같을 확률은 얼마인가?』 이다. 이 값을 일치지수(index of coincidence)라고 한다.

 개의 문자들로 이루어진 문자열이 있고,

 은 a의 개수,  는 b의 개수, ... ,  은 z의 개수라고 하자.

우선 임의로 두 문자를 택하였을 때 두 문자 모두 a일 확률은 얼마일까?

첫번째 문자가 a일 확률은  이고 두 번째 문자도 a일 확률은  이다.

선택하는 순서는 관계없으므로, 두 문자가 모두 a일 확률은 단순히 두 확률 값을 곱하여

 이다.

그러므로 임의로 선택한 두 문자가 서로 같을 확률은

 이다.

이 값을 일치지수(index of coincidence)라고 하고  로 나타낸다. 프리드만 자신은 κ로 표기했었고, 그런 이유로 Kappa 테스트라고 부르기도 한다.

이제 다른 방법으로 일치지수를 계산해 보자.

자연언어에서 사용하는 문자는 모두 고유의 확률(출현빈도)을 가지고 있다.

a는 확률  을, b는 확률  를, , z는 확률  을 가지고 있다.

영어의 경우 이 확률들은 1장에서 통계적 분석에 의한 암호공격에서 설명했었다.

다루고자 하는 문서에서 임의로 두 문자를 택하였다고 하자.

첫 번째 문자가 a일 확률은  이므로 두 문자 모두 a일 확률은  이다.
(정확히 말하자면 처음의 확률과 두 번째 확률은 아주 미세하게 다르지만 문서가 충분히 길다면 무시해 좋을 정도의 차이이다).

다른 문자의 경우도 마찬가지이므로, 임의로 선택한 두 문자가 서로 같을 확률은

 이다.

당연히 이 값은 국가 혹은 사용언어에 따라 다르다. 예를 들어

● 영어에서는

 이다.

즉 영어 문장에서 임의로 선택한 두 문자가 같아지는 경우가 약 6.5% 라는 의미이다.

● 한편 모든 문자의 출현빈도를 같게 조절해 놓은 이상적인 문서가 있다고 하자. 모든 문자의 확률은

 과 같으므로

?? 이다.

이처럼 모든 문자들을 잘 섞어 놓은 문서에서 두 문자가 서로 같아질 확률은, 아무런 의도가 없는 평범한 영어문서의 경우와 비교하면 약 절반이 된다.

?비제네르 암호로 작성한 암호문에서 일치지수는 어떻게 되어 있을까?

● 공격하고자 하는 암호문에서 각 문자들의 출현빈도(확률)  , ,  들은 모두 세어보면
간단하게 알 수 있다.어떤 문자의 출현빈도가  이고 값이 적절히 크다면,

 은  과 근사하다고 볼 수 있다.

즉 이 확률들의 제곱의 합은 거의 일치지수와 같아질 것이다: 즉

● 문서를 작성할 때 특정한 문자를 집중적으로 사용하면  값은 커지고, 문자들의 빈도를
의도적으로 균등하게 조절했다면 작아질 것이다. 증명은 하지 않겠지만 일치지수의
최소값은 0.038 이다.

● 잠시 단일문자 암호로 되돌아가자. 단일문자 암호는 단순히 문자들을 재배열한 것이므로 암호문과 평문의 일치지수는 달라지지 않는다. 예를 들어 평문에서 a의 확률이 0.082 이었다면, 이 값은 a에 대응하는 암호문자 x의 확률이 된다. 즉 각 문자의 확률도 역시 재배열되므로 전체 제곱의 합은 변하지 않는다. 결국 단일문자 암호에서 일치지수는 변화하지 않는다.

● 한편 다중문자 암호에서는 문자의 출현빈도를 균등화하였으므로 일치지수가 감소한다. 그러므로 어떤 암호문의 일치지수를 계산해 보면 단일문자 암호를 사용했는지 아닌지를 판단할 수 있다. 만약 일치지수가 0.065에 가까우면 단일문자 암호를 사용한 것이고, 0.065보다 현저하게 작으면 아마 다중문자 암호를 사용했을 것이라고 추측할 수 있다.

다시 비제네르 암호로 돌아와 키 단어의 길이를 알아내는 데 일치지수를 어떻게 사용하는지 알아보자. 비제네르 암호는 다중문자 암호이므로 당연히 일치지수가 0.065보다 작아진다. 그러나 얼마나 작아지는가? 대답은 『키 단어의 길이 에 따라서 달라진다』이다.

암호문에서의 일치지수를 이용하면 키 단어의 길이를 알 수 있다. 공식을 유도하기 위해 지금부터 약간 수학적인 계산을 하겠다. 어려운 계산은 아니지만 혹시 수식에 지루함을 느낀다면 이 절 끝에 있는 결론으로 건너 뛰어도 괜찮다.

 을 키 단어 길이라고 하자. 간단하게 하기 위해 키 단어는 중복되지 않는 문자들로 되어 있다고 한다.

우선 암호문을  개의 열로 배열하여 놓는다. 그러면 1,  ,  ,  번째 문자들이 ?첫번째 열에 오게 되고 이 문자들은 모두 같은 키 단어 문자로 암호화된 것이다.

마찬가지로 두번째 열의 문자들은 키 단어의 두번째 문자로 암호화되어 있다(그림 2.4).

키 단어 문자들

그림 2.4 비제네르 암호의 일치지수

이제 이 형태를 잘 관찰하면 일치지수를 계산할 수 있다.

첫번째 관찰 : 각각의 열은 단일문자 암호이면서 더하기 암호이다. 그러므로 각 열의 일치지수
는 0.065 이다.

한편 서로 다른 열에서 두 문자를 선택할 경우에는 서로 다른 더하기 암호를 무작위로 사용한 것이므로, 두 문자가 서로 같아질 확률도 그야말로 우연에 의한다. 일치지수는 당연히 0.065보다 작아질 것이고, 이 절에서는 0.038이라고 가정한다.

만약 키 단어 문자열이 아주 무작위로 선정되어 있다면 정확히  이다. 그러나 키 단어를 아주 긴 문장, 예를 들어 어떤 책에 있는 문장으로 했다면 이 값은 약간 커질 것이다.)

두번째 관찰 : 이제 한 쌍의 동일 문자들을 전체 문장에서 임의로 선택하는 경우의 수를 계산
해 보자. 을 전체 문자의 수라고 하면 각 열에는 개씩의 문자가 있다. 문서가 충
분히 길다고 하면 소수점 이하는 무시해도 된다.

우선 선택한 문자들이 같은 열에 있을 경우는 몇가지일까? 첫 번째 문자는 전체 문장의 n개 문자에서 하나를 선택하므로 n가지이고, 두번째 문자는 첫번째 문자가 선택된 열에서 다시 동일한 문자를 선택해야 하므로, 두번째 문자를 선택하는 경우의 수는  이다. 그리고 두 문자를 선택하는 순서는 무시해야 하므로 ?같은 열에서 같은 문자 쌍을 선택하는 경우의 수는

 이다.

이제 서로 다른 열에서 같은 문자를 선택하는 경우의 수를 계산해 보자. 앞의 경우와 마찬가지로 우선 첫 번째 문자를 선택하는 경우의 수는 역시 n가지이다. 두 번째 문자는 첫 번째 문자가 속한 열을 제외한 다른 열에서 선택해야 하므로 모두  가지이다. 그러므로 서로 다른 열에서 같은 문자를 선택하는 경우의 수는 모두

 이 된다.

위 사실들을 종합해 보면, 임의로 두 문자를 선택했을 때 같은 문자일 경우의 기대값

 이다.

임의로 두 문자를 선택했을 때 서로 같을 확률은, 기대값을 전체 문자 선택 경우의 수로 나누어서,

이다. 마지막으로 일치지수는 이 확률값과 거의 근사하므로

이다.

키 단어의 길이를 ? 에 관하여 다시 정리하면

 이다.

수식이 다소 복잡하고 이끌어 내는 과정이 길지만 실제 적용할 때는 마지막 수식만 사용하면 되니까 어려울 것은 없다.

전체 문자 수와 각 문자들이 나타나는 횟수를 세고 나면  는 자동으로 계산된다! 그리고 신기한 것은 아주 적은 문자수를 가진 문서에서도 값은 거의 정확하게 알아낼 수 있다는 점이다.

지금까지의 내용을 앞의 예에 적용해 보자. 문자와 빈도수를 계산해 보면

 이므로

임을 알 수 있다. 그러므로 이 식에서 키 단어의 길이  은

이고 5, 10, 15, 20 가운데 5가 키 단어의 길이이다.

키 단어 확정

키 단어의 길이를 알았으므로 키 단어가 무엇인지 알아내는 것은 쉽다. Mr. X는 문자들을 키 단어의 길이에 맞추어서 개의 열로 다시 쓴다. 각 열을 기준으로 하면 같은 키 단어 문자로 암호화했으므로 단일문자 더하기 암호이므로 1장의 암호공격법을 번 반복하면 된다. 그림 2.2의 열에서 가장 많이 나타나는 문자는 Z이고, 평문에서 가장 많이 사용하는 문자인 e가 암호화된 것으로 추측할 수 있으므로 키 단어의 첫 문자는 V이다.

나머지 키 단어도 같은 방법으로 찾아 낼 수 있다.



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