# Problem 59 XOR decryption

## Problem 59: XOR decryption

https://projecteuler.net/problem=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 p059_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.

## 分析

XOR 异或操作可以用于加密，因为它有一个特性：加密和解密可以使用相同的秘钥。如 65 XOR 42 = 107, 107 XOR 42 = 65，65 使用秘钥42加密得到107，107 又可以使用秘钥42解密成65。

## 方法 如分析中的思路

### CPP

#include <iostream>
#include <fstream>
#include <string>
#include <vector>

int main()
{
// 读取文件中的所有数字，转换成字符，保存到cipher中
char line = {0};
std::vector<char> cipher; // 密文
std::ifstream f("p059_cipher.txt");
while(f.getline(line, 32, ',')){
int ascii = atoi(line);
cipher.push_back( (char) ascii );
}
f.close();

// 尝试使用 a~z 来解码
for(char key1 = 'a'; key1 <= 'z'; key1++){
for(char key2 = 'a'; key2 <= 'z'; key2++){
for(char key3 = 'a'; key3 <= 'z'; key3++){

char keys = {key1, key2, key3};
std::vector<char> plainText;
bool isValid = true;
for(int i = 0; i < cipher.size(); i++){
char key = keys[ i % 3];
char plain = cipher[i] ^ key;
// 如果 plain 是不可打印的字符，必然不可能是明文
if( plain < 32 || plain >= 127){
isValid = false;
break;
}

plainText.push_back(plain);
}

if(!isValid) continue;

printf("\n\nkey:%c%c%c\n", key1, key2,key3);
for(int i=0;i<plainText.size(); i++) printf("%c", plainText[i]);
printf("\n");
}
}
}

// 通过上面的尝试解码，从输出的360种可能解码中，最终发现密码为 exp
// 所以使用 exp 来解码，并且统计明文的ASCII码值总和

char keys = {'e', 'x', 'p'};
int sum = 0;
printf("\n\n--- the plain text ---\n");
for(int i = 0; i < cipher.size(); i++){
char key = keys[ i % 3];
char plain = cipher[i] ^ key;
sum += (int)plain;
printf("%c", plain);
}
printf("\n\nthe sum of plain ascii is: %d\n", sum);
return 0;
}

## 答案

129448

An extract taken from the introduction of one of Euler's most celebrated papers, "De summis serierum reciprocarum" [On the sums of series of reciprocals]: I have recently found, quite unexpectedly, an elegant expression for the entire sum of this series 1 + 1/4 + 1/9 + 1/16 + etc., which depends on the quadrature of the circle, so that if the true sum of this series is obtained, from it at once the quadrature of the circle follows. Namely, I have found that the sum of this series is a sixth part of the square of the perimeter of the circle whose diameter is 1; or by putting the sum of this series equal to s, it has the ratio sqrt(6) multiplied by s to 1 of the perimeter to the diameter. I will soon show that the sum of this series to be approximately 1.644934066842264364; and from multiplying this number by six, and then taking the square root, the number 3.141592653589793238 is indeed produced, which expresses the perimeter of a circle whose diameter is 1. Following again the same steps by which I had arrived at this sum, I have discovered that the sum of the series 1 + 1/16 + 1/81 + 1/256 + 1/625 + etc. also depends on the quadrature of the circle. Namely, the sum of this multiplied by 90 gives the biquadrate (fourth power) of the circumference of the perimeter of a circle whose diameter is 1. And by similar reasoning I have likewise been able to determine the sums of the subsequent series in which the exponents are even numbers.