信息攻防战：破解与加密

antares

所谓密码，是为了让人解开而存在的。

这话听起来或许有点哲学内涵，不过仔细想想，无论是《福尔摩斯探案》里面的跳舞小人，海盗船长的藏宝日记，还是谍战故事里双方争夺的密信，其实都预设了一个收信人或者受众。这位受众知道该怎么正确地解开密码并读出隐藏的信息，而其他人即使拿到密码也读不出来。

在密码学里，把需要传达的真实消息称为“明文”，加密之后的消息叫作“密文”。从明文转化成密文的流程称为“加密算法”，而算法的核心参数就是“密钥”。收信人知道密钥，就可以通过反算加密算法从密文获得明文，而窃听者拿不到密钥，就很难破解密码。举个例子，你写的日记不希望爸爸妈妈看懂，于是就用一个字母代替同学的名字。那么，“用字母代替名字”就是日记的加密算法，而同学名字对应字母的这张列表就是密钥了。

因此，破译密码的第一步是猜出加密算法是什么。

历史上的经典加密法

总体说来，经典密码可以归类为移位式密码和替换式密码两类。移位式密码，保留原文字母，只改变它们的排列方式。替换式密码，将原文的字母或字母组按规律变成其他的符号。实际上，这两类密码可以交替组合使用，制造出更复杂的加密方式。

“乱码”背后的博弈

随着加密技术的复杂化，破解技术也在进步。围绕着一串意义不明的字符，加密者与破解者多年来一直进行着持续的博弈。

频率分析

频率分析是根据密码中符号出现的频率来猜测明文，找到突破口的破解手法。在英语里，字母“e”出现的频率最高，大约有12%之多，其次是“a”和“t”，分别在8%左右。因此，如果密文足够长，那么出现频率最高的字母很可能代表e。有时还可以根据双字母或多字母组合的出现频率来判断。

在爱伦坡的小说《金甲虫》里就有一段根据这种方法解码的例子。小说里有一段指示海盗宝藏的密码：

LINK

恺撒密码&共济会密码

早在古罗马时代，皇帝恺撒就发明了一种恺撒密码。这种密码会按照字母表把明文的字母往前或往后移若干位。如果往前移3位的話，D会变成A，E会变成B，以此类推。这样，“Et tu，Bruno？”就会被加密成“Hw wx，Euxar？”。聪明的同学立刻可以想到，这种恺撒密码非常容易破解。因为英语可能的字母共有26个，所以密钥也就是移动的位数最多只有25种，即使把所有的可能性都试一遍也不会花太多时间。

更聪明的同学则会想到，我们其实可以让密码破解变得更难一点——如果不是单纯的移位替换，而是把26个字母随机对应到一个新的字母上不就行了吗？这就是最基本的简易替换式密码。很多古老的密码都没有逃出这一体系，例如，其济会密码会把26个字母按照规律改成26个符号。对密码分析而言，使用符号还是使用字母并没有本质区别。但对于破解者来说，当把符号纳入加密替换范畴，这种简易替换式密码就不好使用暴力破解了，因为可能出现的密钥有26！（26的阶乘数，计算得26×25×…×2×1=4.033×1026）个之多。

侦探根据其中出现频率最多的符号是“8”，以及“;48”的组合出现了高达5次为突破口，认为“8”代表字母“e”，而“;48”是单词“the”。幸运的是，这个猜测是对的，因此他就可以继续根据英语语法猜测破解出其他的字母了。

互动问答

感兴趣的同学，可以根据上面的密码与提示，试着自己解读出这段密文所对应的正确明文。

明文为：“A good glass in the bishops hostel in the devils seat twenty-one degrees and thirteen minutes northeast and by north main branch seventh limb east side shoot from the left eye of the deaths head a beeline from the tree through the shot fifty feet out.”

为了防止密码被破解，密码学家们想出了许多强化密码的方法，来增大破解难度。

多表替换加密

使用多组替换表，然后根据位置或前一个字母对每个字母使用不同的替换方式。例如，维热纳尔密码可以视为根据字母位置采用不同密钥加密的恺撒密码。这种密码采用了一张26×26的表格，代表了每个字母在不同密钥行下的加密方式。它的密钥是一个单词，例如KEY。那么明文的第一个字母会用K行密钥加密，第二个字母会用E行密钥加密，第三个使用Y行密钥加密，第四个又回到了K行，以此类推。

要破解多表替换加密也是有可能的。如果我们知道密钥的周期是3（例如前文的KEY），那么就可以通过对密码的第1、4、7、…、（3n+1）位的字母进行频率分析，以确定密钥的第一位。以此类推，最终确定出整个密钥。而有时相同的明文片段会被相同的密钥加密，产生相同的密文片段。这使判断密钥的周期变得可能。

尽管存在破解可能性，但破解这种加密法的难度比简易替换式密码高，其难度随着密钥长度变长而提高。多表替换法的极致是多表非周期加密，这个加密方式使用随机生成的一次性密码本作为密钥。它要求收发双方都拥有相同的密码本，且密码本的长度要多于明文长度。在这种情况下，只要敌人拿不到密钥，密码在数学层面便无法被破解。

多字母加密法

这种加密法把两个或多个字母作为一组进行替换加密。例如，波雷费密码把两个字母作为一组，密钥是一个5×5的字母表。然后根据两个字母在表中的位置决定对应的双字母密文。由于加密单元从26个增加到了26²=676个，频率分析也会变得困难许多。也存在使用更多字母组合的加密法，多字母组合加密和解密的复杂度过高，导致这些加密体系并不实用。

移位式密码

前文中介绍过，这种加密方式不会替换原文中字母，而是改变其排列顺序。最经典的列移位法会把明文排成若干列，然后根据顺序依次读指定的列。例如，密钥是3-4-2-1，而明文是I LOVE CRYPTOGRAPHY的话，就会首先把明文写成：

然后按照列顺序写成WGHOROPIEPRYLCTA。破解时则需要猜测密钥长度，并观察哪些长度下会出现和英语近似的结构。“二战”时期德国使用了双重移位的密码，将移位式密码加密后的密文用另一个密钥再加密一次。法国人设计出了一种方法，可以在截获多条长度相同的密文之后快速破解，因此德军舍弃了这种加密算法。

不仅是数学那么简单

我们前面介绍的各种加密与破解算法，都是数学层面的交锋。但实际上，当破解专家们拿到一段密文后，要想破解出明文，可不仅仅是做数学题那么简单（其实数学题也挺难的）。

1.获得尽可能多的密文信息。

拿到密文后，先问“十万个为什么”。这到底是一段密文，还是单纯的涂鸦？它的明文是哪种语言？可能代表什么内容？这段密文可能是用哪种密码体系加密的？有没有可能通过其他方式拿到密钥？

这些问题对于破解密码是至关重要的，它们代表这些密文所包含的信息。要获得这些信息，所依赖的更多是细致的调查分析、社会工程相关知识，甚至是破解者突然闪现的灵感。

现代的密码分析一般假定密码系统是满足严格的数学逻辑的，但在解读伏尼契手稿或是罗塞塔石碑这类的古文书时，这些条件都不一定满足。例如，18世纪的一份叫作Copiale cipher的文书中包含了罗马字母、希腊字母和杂乱的抽象符號，人们将罗马字母和希腊字母提取出来，但一直无法成功破解，最后他们发现只有那些抽象符号有实际意义，而所有字母只是代表空格，这才最终破解了这份文书。

①香农的信息论

克劳德·艾尔伍德·香农，美国数学家。香农信息论是以概率论、随机过程为基本研究工具，研究广义通信系统的整个过程，而不是整个环节，并以编、译码器为重点，其关心的是在不涉及具体环节的情况下研究最优系统的性能及如何达到该性能。信息论将信息的传递作为一种统计现象来考虑，给出了估算通信信道容量的方法。信息传输和信息压缩是信息论研究中的两大领域。这两个方面又由信息传输定理、信源-信道隔离定理相互联系。

2.获取尽可能多的样本。

这包括使用同一密钥加密的密文和对应某些已知密文的明文片段，通过分析大量明文与相应密文的关系，就有可能反推出密钥。能获取的密文越多，破解密码也就越容易。实际上，破解密码所需要的密文样本数是有下限的，这取决于可能的密钥种类数和明文的信息密度。如果低于下限的话，很可能有多种不同的密钥都能破解出合理的明文。而实际可以破译的密码通常要求密文量至少是下限的4倍。

英语的简易替换密码所需要的破译下限是大约28个字母，所以实际可以破译的密码通常需要有100个字母以上。对这方面感兴趣的同学可以去了解一下香农的信息论①。有些密码体系在只有密文的情况下弱点较小，但是一旦知道一小部分明文片段就非常容易破解，例如上文介绍的列移位法，只要知道一段明文，密钥就显而易见了。

3.根据密码体系的特点和文本的语言特征寻找规律。

到这一步我们才进入了数学的领域。一方面，文本规律可以帮助我们判断加密算法是什么。另一方面，知道加密算法之后也有助于我们猜测或排除密钥。例如，简易替换式密码的频率分析法用到了英语的字母频率和简易替换不改变字母频率的特点。“二战”时期破解德军最强密码机“Enigma”的时候，则利用了该密码机不可能将字母加密成同样的字母的特点，使得盟军可以利用获得的明文片段排除大量可能的密钥。

4.暴力求解。

通常是使用大型计算机遍历所有可能的密钥，并找出唯一正确的一个。上面的所有步骤，都是为了让这一步变得可行。只要密码系统公开，且样本量足够多，就只有唯一的一个密钥能让反解出的明文看起来合理。这时，破解密码就只取决于时间和计算量——那些所谓强的加密法，只表示以目前的计算力水平难以在有效时间内破解而已。从图灵破译“Enigma”开始，破译密码就不再是手动的工作，而是大型计算机的领域。1976年推出的DES加密法所使用的56位密钥长度在当时被认为是安全的，但随着计算力和破解算法的发展，到了2008年，用DES加密法所加密的密码已经可以在一天之内被破解了。

互动问答

听完这些，我们可以回头来看一下怪盗的留言，并试着根据下面的提示思考一下怪盗采用了什么加密手段，明文和密钥分别是什么。

1.这段密码留言并不是通常意义上的密码。虽然是发给我们的，但怪盗并没有留下明确的加密算法和密钥。

2.这段留言是为了让我们解开而存在的。密文不长，但是又能破解，那么加密算法的选项就不太多了。

解析 因为表演欲过剩的怪盗目的是将信息传达出去，而不是用密码难倒馆长一行， 所以采用了比较简单的恺撒密码，明文为：“bishangming”，是将密码“lscrkxqwsxq”中每个字母在字母表里右移10位后生成，密钥为10。