프로젝트 오일러 59번

문제는 다음과 같다.

Each character on a computer is assigned a unique code and the preferred standard is ASCII (American Standard Code for Information Interchange). For example, uppercase A = 65, asterisk (*) = 42, and lowercase k = 107.

A modern encryption method is to take a text file, convert the bytes to ASCII, then XOR each byte with a given value, taken from a secret key. The advantage with the XOR function is that using the same encryption key on the cipher text, restores the plain text; for example, 65 XOR 42 = 107, then 107 XOR 42 = 65.

For unbreakable encryption, the key is the same length as the plain text message, and the key is made up of random bytes. The user would keep the encrypted message and the encryption key in different locations, and without both "halves", it is impossible to decrypt the message.

Unfortunately, this method is impractical for most users, so the modified method is to use a password as a key. If the password is shorter than the message, which is likely, the key is repeated cyclically throughout the message. The balance for this method is using a sufficiently long password key for security, but short enough to be memorable.

Your task has been made easy, as the encryption key consists of three lower case characters. Using cipher.txt (right click and 'Save Link/Target As...'), a file containing the encrypted ASCII codes, and the knowledge that the plain text must contain common English words, decrypt the message and find the sum of the ASCII values in the original text.

59번은 아스키코드로 암호화된 문장을 풀어내는 문제이다. 문제를 이해하지 못하는 분들을 위해서 암호화하는 과정을 간단하게 설명하자면 다음과 같다.

I love you

라는 문장을 암호화 한다고 해 보자. 암호하 하기 위해서는 암호화 key가 필요한데, 암호문을 주고 받는 사람들끼리만 알고 있어야 하는 것이다. 이 문제에서는 이 암호화 키로 세 개의 소문자를 사용했다고 한다.  편의상 그 암호화 키가 a, b, c 라고 한다면 위의 문장은 다음과 같이 암호화 할 수 있다.

I love you  각각의 알파벳을 아스키코드로 나타내면 다음과 같다.

I=73

공백=32

l=108

o=111

v=118

e=101

공백=32

y=121

o=111

u=117

또한 암호화 키로 사용된 a, b, c의 아스키코드는 다음과 같다.

a=97

b=98

c=99

암호화는 암호화 하려는 문장과 이 암호화키를 순서대로 XOR연산을 하면서 수행된다.예를 들어,

I XOR a = 73^97 =40

여기서 XOR 연산은 I 의 아스키코드인 73을 이진수로 바꾼 1001001과 a의 아스키코드인 97을 이진수로 바꾼 1100001에 대해서 다음과 같이 계산된다.

1001001

1100001

--------------

0101000

즉 자리수끼리 비교하여 같은 숫자가 나오면 0, 서로 다른 숫자가 나오면 1을 연산 결과로 얻게 된다.

(만약 그 결과가 0일 경우 둘다 1이어서 0이 되었는지, 둘다 0이어서 0이 되었는지 알 수 없고, 결과가 1인 된 경우도 어떤 쪽이 1이고 어떤 쪽이 0이었는지 알 수가 없기 때문에 기본적인 암호화에 사용되는 듯 하다.)

XOR 연산의 결과로 나온 이진수를 십진수로 바꾸면 101000=40 이 된다. 아스키코드값으로 40을 갖는 문자는 ( 이므로 I를 암호화하면 ( 가 되는 것이다. 이미 눈치 채셨겠지만 암호를 풀때는 이 ( 의 아스키코드인 40을 이진수로 바꾼 값과, 암호화 키인 a 의 아스키코드인 97을 이진수로 바꾼 수를 XOR 연산하여 I 라는 문자를 얻게 된다.

0101000

1100001

-------------

1001001

다음에는 공백에 해당하는 아스키코드 32와 두 번째 암호화 키인 b 의 아스키코드 98을 XOR 연산하여 아스키코드 66을 얻어내게 되고, 아스키코드 66에 해당하는 문자는 B 가 되어 공백은 B 로 암호화 된다. (이진수로 바꿔서 XOR 연산하는 과정은 각자 해 보시길...)

다음 부터는 아마 어떤 식으로 암호화가 되는지 알 수 있을 것이다. 이때 주어진 문장보다 암호화 키의 숫자가 작기 때문에 암호화 키는 순서대로 계속 반복하면서 암호화를 하게 된다. 즉, (l 은 c) 와 다시 (o 는 a) 와 (v 는 b)와 (e 는 c)와 이런식으로...

이렇게 하여 암호화 하게 되면 처음 문장과는 전혀 다른 엉뚱한 문장이 나오게 되고, 이 엉뚱한 문장을 풀기 위해서는 암호화 키 abc를 반드시 알고 있어야만 가능하게 된다.

이 문제에서 준 cipher.txt 라는 파일에는 암호화된 문장의 아스키코드 값들이 들어 있다. 문제에서는 암호화키로 누군지 알 수 없는 소문자 3개를 사용했다고 얘기하고 있고, 이 암호문을 풀어보라고 얘기하고 있다. 영어의 소문자가 26개 이므로 암호화 키가 될 수 있는 세 개 소문자들의 조합은 \(26 \times 25 \times 24\) 개가 가능하게 된다.

이 문제를 어떻게 풀까 고민하다가 일단은 모든 조합에 대해서 암호문을 풀어 보았고, 그걸 스캔하다가 멀쩡한 영어문장이 나오는 알파벳의 조합을 찾아내게 되었다. 정말로 무식하기 그지 없지만 어떻게 시도해야 할지 모르기 때문에 일단은 이런 방법을 사용했었다.
이  방법 말고는 뭐가 있을까 고민을 하던 중 고수님의 조언을 들을 수가 있었는데, 그 분 말씀이 영어 문장에서 가장 많이 등장하는 알파벳이 뭘까 고민하라는 것이었다. 뭘까 뭘까 고민을 했었는데, 그 분의 답이 바로 띄어쓰기 즉 공백 이라는 것이 아닌가? 그러니까 여러 조합을 조사하면서 공백이 가장 많이 나오는 소문자의 조합을 찾아보라는 조언을 해 주셨다. ㅋㅋㅋ 역시 무식하면 손발이 고생한다는 말이 맞는 듯...

풀이는 각자 해 보시고, 암호를 풀면 다음과 같은 문장을 얻을 수 있다.

(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.