Project Euler 59: XOR decryption

计算机上的每个字母都对应一个独特的编号，普遍接受的标准是ASCII(美国信息交换标准代码)。例如，大写字母的A的ASCII码是65，星号(*)的ASCII码是42，而小写字母k的代码是107。

一种现代的加密方法是：输入一个文本文件，把其中的字节转化为对应的ASCII码，然后用从秘钥中获得的特定值和每个字节做异或运算。异或函数的一个好处是对密文使用同样的密钥就可以还原出明文，比如\(65\ XOR\ 42=107\)，同时\(107\ XOR\ 42=65\)。

如果密钥的长度和明文的长度一样长并且密钥是完全随机的，那么这个加密就是不可破译的。用户会把加密后的信息和密钥放在不同的地方，如果不能同时获得两者，则不可能解密这条信息。

不幸的是，上述方法对于大部分用户来说是不实用的，所以通常会使用一种修正的方法，也就是用一个密码单词来作为密钥。如果这个密钥单词比想要加密的信息短(通常都是这样)，那么这个密钥就会在整个信息中重复使用。一种折中的方案是：使用一个足够长的密码单词来保证安全，同时这个单词又不至于太长因此更好记住。

通过告诉你以下内容我们把你的任务变得简单了一些：已知密钥包含三个小写的英文字母，同时文本文件p059_cipher.txt包含了加密后的ASCII码，并且明文只包含普通的英文单词。现在请你解密这条信息并且找到原文对应的ASCII码的总和。

分析：这是一道密码学的题目，如果能对相关的密码学背景知识有一定的了解，这道题就会容易很多。如果大家感兴趣的话，可以看一看《码书 : 编码与解码的战争》这本书，这是一本相当精彩的密码学科普读物。作者西蒙·辛格是一位英国数学家，他同时也是《费马大定理 : 一个困惑了世间智者358年的谜》这本书的作者，这本书也相当精彩，能够把枯燥的数学知识写得如此生动有趣，扣人心弦的作者唯实不多。

言归正传，题目已经说了密钥由三个英文小写字母构成，考虑到三个小写字母最多只能构成\(26^3=17576\)种组合，所以这道题也可以用暴力破解的方式。用这一万多个密钥逐个去试，只到原文表现像正常的英文，那么这个密钥就是正确的，这时再把原文对应的ASCII码加总即为题目所求，但显然我们还有其它更好的办法。在《码书》一书中，作者讲述了一种古代非常流行的加密方法，也就是替代法，我们可以把原文的英文字母替换成其它不同的英文字母，比如我们可以把C替换成E，A替换成K，T替换成Z，这样CAT这个单词就变成了EKZ，这种替换映射关系也就是密钥，当信息的接收者收到密文，就可以用这个密钥反推出明文。这个方法大约是在古罗马时期发明的，在很长一段时间里是一种非常安全的加密方法，没有人能够破译，只到欧洲中世纪，阿拉伯学者发现了破解这种密码的方法，也就是频率分析法。在像英语中这种表音文字中，每个字母的使用频率都是相对固定的，比如在英语中，字母E的使用频率最高，约为12.7%；字母T的使用频率其次，约为9.35%；字母Z的使用频率最低，约为0.077%。因此只要我们收集足够多的密文，统计其中各个字母的出现频率，并把这种频率分布和英语的频率分布相对照，就不难猜出密文中的字母与原文中字母的对应关系，从而破解这种密码。

本题中涉及的异或加密法实际上和替代法非常类似，所以也可以用频率分析法破解。首先我们看一下异或加密法的工作原理，对于异或加密不太了解的同学，可以参见这篇维基。假设我现在有一段明文是"hello world!"，我确定一个比明文长度要短的字母组合作为密码单词，比如说密码单词是"god"，包含空格但不包含左右引号的原文长度为12，而密码单词长度为3，所以我们需求循环使用四次密码单词来对原文进行加密。首先我们对字母"h"和字母"g"对应的ASCII码进行异或运算，得到结果是15；然后对字母"e"和字母"o"对应的ASCII码进行异或运算，得到10。依次类推，字母"l"和字母"d"配对，下一个字母"l"和字母"g"配对进行异或运算，最终得到整个密文为[15,10,8,11,0,68,16,0,22,11,11,69]。假如我们要恢复原文，我们只需要对这个密文按照上面加密类似的方式用密码单词进行异或运算，如将15和字母"g"对应的ASCII码103进行异或运算得到104，其对应的英文字母正是"h"。

现在我们看看如何用频率分析法破解异或加密，首先题目已经告诉我们密码单词长度为三，因此我们知道原文的第一个和第四个字母是用密码单词的第一个字母加密的、第二个和第五个字母是用第二个字母、第三个和第六个字母是用第三个字母。之后依次类推。因此，我们可以将密文分为三组，每组密文都是使用同一个密码单词中的字母加密的。然后我们对每一组密文进行频率分析，找到出现频率最高的密文：第一组出现频率最高的密文是69，出现了86次；第二组频率最高的是88，出现了77次；第三组频率最高的是80，出现了103次。在一段正常的英文中，出现频率最高的一般是空格，所以我们猜测上面三个频率最高的密文对应的明文都是空格(正因为此，所以一般加密时都会把原文的空格去掉，否则就会太容易破解了，但是经过尝试我发现题目为了简化在加密时并没有去掉空格)。现在我们只需要把明文也就是空格对应的ASCII码和相应的密文进行异或运算就可以得到密钥了。空格对应的ASCII码是32，首先把32和69进行异或运算得到101，对应的英文字母是"e"；然后把32和88进行异或运算得到120，对应的英文字母是"x"；最后把80和32进行异或运算得到112，对应的英文字母是"p"，因此我们得到密码单词是"exp"。我们可以用这个密码单词对密文进行解密，得到原文如下：

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.

有趣的是，这是欧拉的一篇著名论文中的段落，在这篇论文里他解决了著名的巴塞尔问题，即求出了以下无穷级数的和：
\[ \sum_{k=1}^\infty \frac{1}{k^2}=1+\frac{1}{4}+\frac{1}{9}+\frac{1}{16}+\cdots=\frac{\pi^2}{6} \]

这启发了黎曼进一步研究黎曼\(Zeta\)函数的性质，发现了黎曼\(Zeta\)函数的非平凡零点与质数分布规律之间的隐秘联系，在研究过程中产生的黎曼猜想至今仍是数学领域未被解决的重要猜想之一。

弄清楚了以上原理并知道密码单词之后，代码实现就相对比较简单了。用密码单词中的每个字母逐项与密文进行异或运算获得原文对应的ASCII码再求和，即为题目所求。代码如下：

# time cost = 668 µs ± 3.63 µs

from collections import Counter

def main():
    with open('data/ep59.txt') as f:
        cipher = list(map(int,f.read().split(',')))
    space_ascii = ord(' ')
    key = [Counter(cipher[i::3]).most_common(1)[0][0] ^ space_ascii for i in range(3)]
    cycles = len(cipher)//3
    res = sum([x^y for x,y in zip(cipher,key*cycles)])
    return res