59. 프로젝트 오일러 #59 : XOR 암호 풀기

이번 문제는 난이도가 5%이기는 하지만, 실제로 정석대로 푼다면 5%보다 높을 것 같네요.

암호를 푸는 방법은 무식한 방법으로 반복대치를 하는 경우가 많습니다.  단순 반복대치를 하면 풀 수는 있겠지만, 보통 수만대의 컴퓨터를 동원해도 몇천년, 몇만년 이상 걸리는 경우가 허다합니다.  양자컴퓨터가 나온다면 좀 달라질 수 있겠지만요.

이 문제에서는 주어진 텍스트에 3글자 소문자로 이루어진 키를 가지고 암호를 푸는 것입니다.  원래 문제 의도(난이도 5%)였다면, 3글자 소문자 키를 생성하고, 그것에 의해서 영어의 일반 언어가 도출되는지를 검사하면 되겠죠.  예를 들어서 a, this, is, are, you, 등등이 될겁니다.

전 고전적인 방법, 즉, 암호키를 알기 힘들다는 가정하에서 풀어보았습니다.  물론 암호키의 길이는 알고 있어야 합니다.  일반적으로 단순 반복 XOR 암호화 방법은 이 방식으로 대부분의 일반 문서는 풀 수가 있습니다.  암호화 키에 비해서 문서가 너무 짧다면 어렵겠지만요.  통계학적인 방법을 이용해서 문제를 풀었습니다.

첫번째, 영어 단어에 많이 포함되는 문자들을 나였했습니다,  i, a, e, o, c, d, g, h, f 가 해당 됩니다.  그리고 공백문자를 까먹어서도 안 되겠죠.

그런 후에 암호화 키 길이에 맞게 반복되는 문자들의 도수 분포를 만듭니다.  그리고 도수 분포에 따라서 위에 자주 나오는 글자들을 대입해보는 것이죠.  그렇게 하면 암호키를 찾아낼 수 있습니다.

실제 실행한 화면은 다음과 같습니다.

12 6 48 8 5 5 18 0 18 28 6 12 2 0 18 25 7 4 5 28 17 15 0 3 0 0 0 0 0 0 
3 2 4 1 0 0 0 1 0 0 0 1 0 0 0 3 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 
0 0 0 0 0 0 70 0 11 0 5 0 0 1 1 0 0 0 1 1 0 2 1 0 0 0 0 1 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

26 16 8 18 0 0 28 35 8 6 31 16 5 3 20 0 0 0 0 0 0 0 5 0 9 6 6 21 20 6 
0 2 0 0 0 0 0 0 1 2 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 2 0 0 4 1 0 0 0 0 
2 0 2 0 0 0 0 1 0 0 0 0 0 0 85 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

11 41 4 11 0 16 3 6 8 7 23 26 24 21 0 1 31 5 5 7 5 0 17 14 0 0 0 0 1 5 
1 0 0 1 0 3 0 1 1 0 1 0 0 0 2 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 77 1 0 0 4 0 4 0 0 0 0 0 0 1 0 1 0 5 2 1 0 0 0 0 0 1 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

keyword = $%&

(The Gospel of John, chapter 1) 1 In the beginning the Word already 
existed. He was with God, and he was God. 2 He was in the beginning 
with God. 3 He created everything there is. Nothing exists that he 
didn't make. 4 Life itself was in him, and this life gives light to 
everyone. 5 The light shines through the darkness, and the darkness 
can never extinguish it. 6 God sent John the Baptist 7 to tell 
everyone about the light so that everyone might believe because of 
his testimony. 8 John himself was not the light; he was only a 
witness to the light. 9 The one who is the true light, who gives 
light to everyone, was going to come into the world. 10 But 
although the world was made through him, the world didn't recognize 
him when he came. 11 Even in his own land and among his own people, 
he was not accepted. 12 But to all who believed him and accepted him, 
he gave the right to become children of God. 13 They are reborn! 
This is not a physical birth resulting from human passion or plan, 
this rebirth comes from God.14 So the Word became human and lived 
here on earth among us. He was full of unfailing love and 
faithfulness. And we have seen his glory, the glory of the only 
Son of the Father.

ans = ******

처음 세줄의 숫자들은 글자들의 돗수분포(histogram)입니다.  통계학적 방법으로 얻어진 keyword는 ***였습니다.  그리고 결과를 표시한 것입니다. 

아래는 제가 짠 소스코드입니다.

돗수분포를 저장하기 위해서 histo라는 변수를 만들었습니다.  일반적으로 ASCII 내에서만 쓴다면 128개만 저장해도 됩니다.

암호화키 길이에 따라서 돗수분포를 달리해줍니다.  암호화 키 길이가 무한대라면, 통계학적 방법에 의해서 암호를 해독하기 힘듭니다.  굉장히 많은 양의 동일암호로 작성된 암호화 문서가 필요합니다.  (이미테이션 게임이라는 영화를 보면 독일군 암호를 푸는 과정이 나오는데, 이 과정에서 암호화키를 찾아내는 알고리즘이 상당히 비슷합니다.)

다소 바보같은 모습의 주인공이고, 실제 당시의 내용과는 좀 다른 부분이 많았지만요.  재미있게 보았네요.  (아 옆길로 샜다.)

그리고 나서 guess 변수에 저장된 영문자들을 이용해서 암호화 키를 찾아내게 됩니다.

#include <stdio.h>
#include <memory.h>

int main()
{
    int histo[3][256];
    char cipher[] =
    {
        #include "p059_cipher.txt"
    };

    memset(histo, 0, sizeof(histo));
    for( int i = 0 ; i < sizeof(cipher) ; i++ )
        histo[i%3][cipher[i]]++;

    for( int i = 0 ; i < 3 ; i++ )
    {
        for( int j = 0 ; j < 128 ; j++ ) printf("%d ", histo[i][j]);
        putchar('\n');
    }

    char keyword[3] = { 0, 0, 0 };

    for( int i = 0 ; i < 3 ; i++ )
    {
        char *guess = " iaeocdghf";
        int maxh = histo[i][0];
        int maxv = 0;
        for( int j = 1 ; j < 128 ; j++ )
            if( maxh < histo[i][j] ) { maxh = histo[i][j]; maxv = j; }
        for( int j = 0 ; *(guess+j) ; j++ )
        {
            char s = *(guess+j)^maxv;
            if( s < 'a' || s > 'z' ) continue;
            int k;
            for( k = 0 ; k < 128 ; k++ )
            {
                if( histo[i][k] == 0 ) continue;
                if( (k^s) < ' ' || (k^s) > 'z' ) break;
            }
            if( k < 128 ) continue;
            keyword[i] = s;
            break;
        }
    }
    printf("keyword = %c%c%c\n", keyword[0], keyword[1], keyword[2]);
    int sum = 0;
    for( int i = 0 ; i < sizeof(cipher) ; i++ )
    {
        putchar(cipher[i]^keyword[i%3]);
        sum += cipher[i]^keyword[i%3];
    }
    putchar('\n');
    printf("ans = %d\n", sum);
}