XOR로 계산하는 암호 해독 (프로젝트 오일러 #59)

현대 암호화 기법 중엔 XOR을 이용하는 방법도 널리 쓰인다.

이 문제는 주어진 데이터가 XOR로 암호화되어있고, 키의 길이가 소문자 3자리일 때 원문^[각주:1]을 구하는 문제이다.

키가 3개이므로 aaa~zzz 까지의 17576(26³) 가지의 키를 일일이 대입해봐도 되지만, 3부분으로 나누어 78(26×3)번만 돌려도 된다.

문제에는 좀 모호하게 적혀있긴 하지만, 원문은 일반적인 영단어로 구성되어 있다고 한다.

즉, 키의 후보값을 넣고 돌렸을 때 결과가 일반적인 영단어에 포함되지 않는 기호가 나타나면 키가 아니라고 볼 수 있는 것이다.

이러한 점을 고려해서 대략 아래와 같은 코드를 작성했다.

#include <stdio.h>
#include <vector>
using namespace std;

inline bool isDecrypedChar(int c)
{
    return (c>=' ' && c<127 && c!='`' && c!='[' && c!=']' && c!='{' && c!='}');
}

bool getCipheredText(const char *filename, vector<int> &ciphered)
{
    FILE *f;
    if (fopen_s(&f, filename, "rt") || !f) return false;

    ciphered.clear();

    int d;
    while (fscanf_s(f, "%d,", &d) == 1) {
        ciphered.push_back(d);
    }
    return true;
}

char getKey(vector<int> &ciphered, int begin) {
    for (char c = 'a'; c <= 'z'; c++) {
        bool success = true;
        for (unsigned i = begin; i < ciphered.size(); i += 3) {
            int decr = ciphered[i] ^ c;

            if (!isDecrypedChar(decr)) {
                success = false;
                break;
            }
        }
        if (success) return c;
    }
    return 0;
}

int printfText(vector<int> &ciphered) {
    int ret = 0;
    for (unsigned i = 0; i < ciphered.size(); i++) {
        if (isDecrypedChar(ciphered[i])) printf("%c", ciphered[i]);
        ret += ciphered[i];
    }
    printf("\n");
    return ret;
}

void decrypt(vector<int> &ciphered, int begin, char key) {
    for (unsigned i = begin; i < ciphered.size(); i += 3) {
        ciphered[i] ^= key;
    }
}

int main(int argc, char* argv[])
{
    vector<int> ciphered;

    if (!getCipheredText("p059_cipher.txt", ciphered)) return 0;

    for (int i = 0; i < 3; i++) {
        char key = getKey(ciphered, i);
        printf("key%d: %d(%c)\n", i+1, key, key);
        decrypt(ciphered, i, key);
    }

    int sum = printfText(ciphered);
    printf("sum = %d\n", sum);

    return 0;
}

그러면 아래와 같은 결과를 볼 수 있다.

key1: 103(g)
key2: 111(o)
key3: 100(d)
(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 e
verything 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 tel
l everyone about the light so that everyone might believe because of his testimo
ny. 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 t
he world. 10 But although the world was made through him, the world didn't recog
nize 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 res
ulting from human passion or plan, this rebirth comes from God.14 So the Word be
came human and lived here on earth among us. He was full of unfailing love and f
aithfulness. And we have seen his glory, the glory of the only Son of the Father
.
sum = 107359

근데, 무슨 이 첨단 과학의 시대에 요한복음이냐… ㅋㅋㅋㅋ

1. 정확히는 원문 아스키 코드의 합 [본문으로]