[Proejct Euler] 59. XOR decryption

1. 개요

    문제는 이곳에서 확인할 수 있다. 어떤 문서를 암호화하기 위하여 XOR 연산을 사용할 수 있다. 예를 들어 A는 아스키코드로 65인데 42와 XOR 연산을 하여 107로 암호화할 수 있다. 여기서 42는 키의 역할을 하며 107과 42를 XOR 연산을 하면 65로 복호화가 된다. 복호화가 불가능하게 하기 위해서는 암호화하는 문장과 같은 길이의 무작위 키로 암호화하면 된다. 하지만 이 방법은 실용적이지 못하기 때문에 기억하기 적당한 길이의 키를 전체 메시지에 대하여 돌아가며 적용한다.

    문제에서 주어진 암호문의 키는 영어 소문자 3개라는 것이 알려져 있다. 그 키로 암호문을 해독하고 아스키코드 값의 합을 구하는 것이 문제의 목표이다. 단, 본래의 메시지는 일반적인 영어 문장이다.

2. 구현

    26개의 영어 소문자에서 3개를 복원추출한 후 순서가 있도록 나열하면 키의 후보가 된다. 이를 위하여 반복문 3개를 중첩하여 사용하면 되지만 아름답지 못하다고 생각하여 스택을 사용하여 구현하였다. 해독한 메시지가 일반적인 영어 문장인지 파악하기 위하여 많이 사용하는 단어 5개와 공백이 있는지 검사하였다. 그러한 단어가 무엇인지는 위키피디아를 참고하였다. 단, be동사는 다양한 형태를 지니기 때문에 제외하였다.

# -*- coding: utf-8 -*-
# Project Euler 59

with open('p059_cipher.txt', 'rt', encoding='utf-8') as f:
    dat = list(map(int, f.read().split(',')))

alphabet = 'abcdefghijklmnopqrstuvwxyz'
stack = [['', alphabet]]

# GENERATE KEY
while stack:
    last = stack[-1]
    key_candidate = last[0] + last[1][0]

    if len(key_candidate) == 3:

        # START DECRYPT CODE

        decryption = ''.join(chr(ord(key_candidate[i % 3]) ^ asc) for i, asc in enumerate(dat))
        if all(word in decryption.lower() for word in [' ', 'the', 'of', 'and', 'a', 'to']):
            print('-- KEY CANDIDATE: {0}'.format(key_candidate))
            print('{0}\n'.format(decryption))

        # END DECRYPT CODE

        last[1] = last[1][1:]

        while not stack[-1][1]:
            stack.pop()
            if not stack:
                break
            stack[-1][1] = stack[-1][1][1:]
    else:
        stack.append([key_candidate, alphabet])

key = 'god'
print('KEY: god, ANSWER: {ans}'.format(ans=sum(ord(key[i % 3]) ^ asc for i, asc in enumerate(dat))))

키는 god이며 답은 107359이다.