密码

我们所面临的第二个挑战是对加密的消息进行解密。我们首先一起来看看替换加密，即使用一个字母替换另一个字母。对其中替换关系的描述称为密钥，可以通过26个字母的字符串来表示它：第一个字母替换“a”，第二个字母替换“b”等。以下是通过替换密码密钥对消息进行加密(Pthon的库函数maketrans和translate可以实现大部分功能）：

可能所有代码中最简单的就是移位加密，它是一种替换加密方法，在这种加密方法中，消息中的每个字母都由其后面的第n个字母进行替换。如果n=1，那么“b”替换“a”，“c”替换“b”……直到“a”替换“z”。移位加密也被称为凯撒(Cesar)加密法；它们在公元前50多年很先进。变换(sift)函数使用移位加密的方法进行编码：

在不知道密钥的情况下进行解密，我们遵循和分段相同的方法：定义一个模型（我们将继续采用单元单词概率方式），枚举候选项并选择最有可能的。由于只需要考虑26种候选移位，所以我们可以尝试全部候选移位。

为了实现这一点，我们定义函数logPwords，它和函数Pwords相似，但是它返回的是概率的自然对数值，其输入可以是一个很长的字符串，也可以是一个单词序列：

这一切都太简单了。为了查看为什么简单，观察以下26个候选项，以及它们的概率对数值：

当你扫描列表时，刚好一条线很明显，类似英语；而Pwords和我们的直觉一致，假设该行的概率的对数值是-25（即10^-25），它的可能性是任何其他候选项的10⁵⁰倍多。

代码编写者通过消除单词之间的标点符号、空格和大小写区别，使得解码者的工作变得更加困难。采用这种方式，解码者无法从简短的单词如“I”、“a”和“the”中得到任何线索，也无法猜测省略符号（'）之后的字符应该是“s”还是“t”。函数shift2是一种加密方法，它删除了非字符的数据，把所有的字符都转换成小写，然后再应用变换加密方法：

以下是破译这段代码的一种方式，通过枚举每个候选项，对每个候选项分段，并选择概率值最高的那个分段：

我们一起来看它是如何工作的：

这还是太简单了。我们一起来看看通用的密码替换方案，在这种方案中，任何字母都可以被其他字母替换。现在我们无法继续枚举所有的概率，因为总共有26！（约4×10²⁶）种密钥，而不再仅仅是26种。Simon Singh（编码鼻祖）编写的《The Code Book》提供了五种策略（我们自己在后面增加了第六种）来破解密码：

1.字母一元模型频率。匹配消息中的常用字母到英语中的常用字母（如“e”），匹配不常用字母到不常用字母（如“z”）。

2.双字字母分析。加密消息中的双字字母，在消息解密后还是双字字母。考虑最生僻和最常用的双字字母。

3.找常见的单词如“the”、“and”和“of”。单字母单词通常是“a”或“I”。

4.可能的话，获取一个由你处理的消息类型所组成的词频表。如军事消息使用军事术语等。

5.猜测一个单词或者短语。例如，如果你觉得消息可能包含“your faithful servant”，就大胆猜测它。

6.使用单词模式。例如，加密单词“abbccddedf”很可能表示“bookkeeper”，因为在词典库中没有其他单词满足这种模式。

对于单词间不包含空格的消息，策略3和策略6都不适合。策略1和策略2每种只包含26种概率，而且似乎目标受众是有一定记忆和计算能力的分析人员，而不是一个计算机程序。策略4和策略5是为了某个特殊用途，而不是通用的解码方式。看起来我们只能依赖于自己提出的策略6。但是我们知道应该如何实现该方法。

第一，定义一个概率模型：我们可以采用处理移位加密时所用的方式来评估候选项：对文本分段，计算单词的概率。但是考虑该方法的第二个步骤，刚开始几个（或者几千个）候选项可能是很差的候选。在开始探索时，我们没有任何类似于单词的东西，因此在刚开始就对文本分段的意义不大。然而，我们可能（或者只是碰巧）对一行的几个字母进行解码，生成有意义的结果。因此，我们使用N元文法模型而不是单词来构建语言模型。我们应该采用字母二元文法模型？还是三元文法模型？抑或五元文法模型？我选择字母三元文法模型是因为它是能够表示常用词（策略3）的最短的文法模型。我通过一个单词二元字母数据文件（不能只看词汇文件，因为需要考虑单词边际间的字母三元文法模型），对三元字母（删去了空格和标点符号）进行计数，生成数据文件count_3l。它总共包含26³=17576个三元字母组合。以下是出现频率最高和最低的10个三元字母组合：

三元字母组合的概率计算如下：

第二，枚举候选项：我们无法考虑全部的4×10²⁶种可能的密钥，而似乎没有什么方法可以像文本分段那样，系统性地消除非最优候选项。这种情况下，需要本地搜索策略，如“爬山算法”(hll climbing)。假设你想要到达最高峰，但是没有地图。通过爬山算法的策略，你可以从随机位置x开始，向相邻位置走一步。如果该位置比之前位置高，继续从那里开始“爬山”；如果不是，则考虑x的另一个相邻位置。当然，如果你从地球上随机一个位置开始步行上山，你可能无法到达珠穆朗玛峰的顶部。更有可能的是，你到达了某个地方的小山头，或者困在一个平原里到处走。因此，我们为爬山算法增加了随机次数的重试。在完成这些步骤后，我们开始从一个新的随机位置从头开始。

以下是通用的爬山算法。它包含起始位置x，我们正试着优化的函数f，生成一个位置的相邻位置的函数neighbors，以及最多采取的步骤。（如果变量调试是真实的，它会输出最佳的位置x及其分值）。

为了使用爬山算法来解码，我们需要指定参数。我们将要搜索的位置是纯文本（解码后的）消息。我们将试着最大化三元字母组词频，因此，设置函数f=logP3letters。从根据随机的密钥解码生成的x位置开始，做随机次数的重试，但是当从每次重试中收集候选项时，我们会根据segment2，选择最佳的一个候选项，而不是根据函数logP3letters：

现在，我们需要定义相邻消息函数neighboring_msgs，它生成下一步要尝试的消息的解码。我们首先尝试“修复”不可能的二元字母组。举个例子，最不频繁出现的二元字母组合“jq”的概率是0.0001%，它比最频繁出现的二元字母组合“in”和“th”的概率低5万倍。因此，如果我们在消息中看到“jq”，我们试着把“j”和其他每一个字母进行交换，同样也交换“q”。如果一个交换生成更频繁的二元字母组，那么我们生成由这次交换得到的消息。在遍历20次最不可能出现的二元字母组“修复”后，我们考虑随机交换：

我们一起来看看它的效果如何。我们将从Robert Raynard的书《Secret Code Breaker》(Sith和Daniel；见http：//secretcodebreaker.com)中抽取一些密码来尝试这种策略。首先是一则“热身”的加密消息：

解码后的消息，除了“crypt analyst”本应该是一个单词，其他都是正确的。（这个词不在我们的词库中，但是它在1300亿的单词库中）。注意最后一个字符（加密文本的“E”）是为了使所有分块都是五个字母一组而增加的。

以下是来自第一次世界大战时德国间谍Baron August Schluga的真正的密文：

以下是在1992年，美国国家安全委员会(KB)向美国前中央情报局(CA)主席Aldrich Ames发送的密文，Aldrich Ames在1994年被判为间谍：

以下是在1943年德国的U-Boat命令的密文被截获并且被解码，从而挽救了联合战舰护航队：

解码后的消息混淆了“y”和“x”。分析人员会意识到“conyov”应该是单词“convoy”，因此“point yd”应该是“point vd”。我们的程序从未考虑到这种可能性，因为正确文本的三元字母组合概率比这里结果所显示的要低。通过发明一种更好的打分函数，它不会陷于局部最优中，我们可能可以解决这个问题。或者我们可以增加第二层次的爬山搜索：通过第一次搜索生成的候选项，以segment2作为打分函数来简单搜索。我们将把它作为练习留给读者。