信息的加密和解密贯穿于人类的外交和战争史。可以说，密码学的发展离不开人类对安全通信的需求。我们首先简要回顾人类对加密和解密算法的探知过程。这部分内容并不涉及质数。（古典密码学的发展历史参考了《密码的奥秘》中的相关内容。）
我们所熟知的最古老加密设备为「斯巴达密码棒」（Scytale），其被广泛适用于公元前 7 世纪的古希腊军事重镇斯巴达。所谓的密码棒就是一根木质的棒子。加密时，发送方把羊皮纸或者皮革带一圈接一圈地缠绕在密码棒上，然后沿着棒子的方向逐行写下完整的信息。信息写完后，将羊皮纸或者皮革带从密码棒上解下来，就得到了一个看上去毫无意义的字母带。接收者收到字母带后，将字母带缠绕在自己的密码棒上，只要接收者和发送者所用的密码棒长度和面数都相同，接收者就可以方便地读取隐藏的信息。
图 2：斯巴达密码棒
http://upload.wikimedia.org/wikipedia/commons/thumb/5/51/Skytale.png/220px-Skytale.png
我们用图来表示密码棒的使用方法。在下面的例子中，信息「THE SCYTALE IS A TRANSPOSITION CIPHER」按照图 3 的方法写在缠在密码棒上的整条皮带上。
图 3：用斯巴达密码棒加密信息「THE SCYTALE IS A TRANSPOSITION CIPHER」
http://www.guokr.com/blog/425174/
写好后，把皮带从密码棒上解下来，结果就呈现为：TNSEHCPIEIOSSPSACHITYETRTRIAAONL。
斯巴达密码棒的加密方法本质上只是打乱了信息的字母顺序。想破解斯巴达密码棒的方法也非常简单，感兴趣的读者们可以试着解读一下，「USSONIERDENCEGDEREFS」对应的原始消息是什么呢？
斯巴达密码棒的加密方法可以看作「格栅」密码的一种。格栅密码是意大利数学家卡尔达诺所发明的加密方法。该方法的原理是，发送方和接收方约定一个栅格和消息的撰写方法。斯巴达密码棒所约定的栅格就是密码棒本身。格栅密码原理上非常简单，但是人们可以在栅格的构造方法中使用非常复杂的技巧。
最为经典的格栅密码是「格子」密码（The Trellis Cipher）[39]，也叫做棋盘密码，其加密方法如图 4 所示。假设待加密的信息是「I WILL BE AT THE NATIONAL GRAND OPERA TODAY.」开始时，将黑色格子置于左边最顶端，在白色格子中垂直书写信息。第二步，在书写 18 个字符之后将棋盘旋转 90 度，这样白色格子就被置于左边最顶端了，继续书写信息。第四步，移除格子，从左到右读取字母：ALDTTIIREENALLOHOOWAARAYGBPEDNINTAT.就是最终的加密结果了。
图 4：用格子密码加密「I WILL BE AT THE NATIONAL GRAND OPERA TODAY」
格栅密码还存在很多变种：栅格可以被设计的更复杂，格子数量可大可小。栅格的使用方法也可以多种多样：可以按照任意角度旋转栅格，可以正反使用栅格，栅格的旋转起点和顺序也可以随意设置。在第一次世界大战中的 1916 年，德国军队就曾在短期内使用格栅密码加密战场信息。但是由于格栅密码仍然不够安全，所以在几个月后就被德国军队弃用了。
上述密码使用起来虽然方便，但不够安全的最主要原因是：本质上我们只是对发送消息的字母顺序进行了扰乱，并没有对字母进行修改。只要破解者知道或者部分知道字母扰乱的方法，就可以破解密码了。随着对密码研究的深入，人类发现加密信息的本质是使用一种发送方和接收方都知道的一个秘密对信息进行处理。只要接收方知道秘密，他就能从加密结果中正确恢复出信息。而作为不知道秘密的破解者，对加密结果就无能为力了。我们之后将发送的信息称为「明文」（Plaintext），将加密结果称为「密文」（Ciphertext），而双方都知道的秘密信息称为「密钥」（Secret Key）。
第一个涉及密钥的加密方法是罗马将军和独裁者凯撒大帝建立的加密方法，称为「凯撒密码」（Caesar Cipher）。凯撒大帝在高卢参加竞选时，在与他的罗马朋友和同事的私人信件中使用了这种加密方法。这个密码对明文进行了简单的移位处理。举例来说，如果明文是字母 A，则向后移位 3 个字母，A 被加密为 D。同理，B 被加密为 E，C 被加密为 F，一直到 W 被加密为 Z。对于 X 来说，移位 3 个字母超过了Z，则返回到字母 A。因此，X 被加密为 A，Y 被加密为 B，Z 被加密为 C。如果接收方也知道要移位 3 个字母，则在解密时把密文往前移位 3 个字母即可。这里，移位的字母数量 3 就可以看成凯撒密码的密钥。举个例子，当移位字母数量为 4 时，信息「REINFORCEMENTS ON THE WAY」的加密结果为：「VIMRJSVGIQIRXW SR XLI AEC」。凯撒密码的缺点是密钥的个数实在是太少了，只有 25 种可能。如果破解者知道密文是由凯撒密码加密的，他可以试遍所有 25 种可能的移位方式，达到解读密文的目的。
图 5：尤里乌斯• 凯撒大帝雕像
https://zh.wikipedia.org/wiki/%E5%B0%A4%E5%88%A9%E7%83%8F%E6%96%AF%C2%B7%E5%87%B1%E6%92%92#/media/File:Bust_of_Gaius_Iulius_Caesar_in_Naples.jpg
凯撒密码实际上是一种「单表代换密码」。所谓单表代换密码，就是把消息中的字母一一替换为另一个字母。例如，当密钥为 3 时，凯撒密码的字母代换表如图 6 所示。
图 6：凯撒密码的字母代换表
既然凯撒密码的缺陷是可能的密钥个数太少，那么我们能不能进一步改进凯撒密码呢？我们制作一个类似凯撒密码的字母代换表，但是每个字母的移位次数并不是固定的。举个例子，我们可以让 A 变为 D，B 变为 C，C 变为 E，以此类推，只要 26 个字母互相之间仍然满足一一映射关系即可。发送方和接收方的密钥就是字母的映射表。这样一来，可能的密钥个数就从 25 个一下扩展成为 26×25×24⋯4×3×2 个，约为 4×1026，是个非常大的数。
更进一步，字母的映射结果不一定还是字母。我们还可以把字母映射成各种符号。最为经典的非字母映射莫过于「猪圈密码」[40]了。由于在 1700 年代，共济会常常使用这种密码进行秘密通信，所以猪圈密码又被称为「共济会密码」。猪圈密码的符号与 26 个字母的对应关系如图 7 所示。如果用猪圈密码加密明文「X MARKS THE SPOT」，则密文如图 8 所示。
图 7：猪圈密码的符号与 26 个字母的对应关系图
https://zh.wikipedia.org/wiki/%E8%B1%AC%E5%9C%88%E5%AF%86%E7%A2%BC#/media/File:Pigpen_cipher_key.svg
如果把猪圈密码和前面提到的改进凯撒密码进行组合后，看起来是一个非常不错的加密方法。古典密码学中有很多类似的方法。这一系列方法在密码学中被称为「单表代换密码」，这是因为本质上我们还是利用了一个字母与字母/图像的一一映射表格对明文进行加密。
图 8：利用猪圈密码加密「X MARKS THE SPOT」的结果
https://zh.wikipedia.org/wiki/%E8%B1%AC%E5%9C%88%E5%AF%86%E7%A2%BC#/media/File:A-pigpen-message.svg
单表代换密码看起来已经是一个非常不错的密码了。然而，这种密码仍然有内在的缺点。由于字母与字母/符号是一一对应的，这就意味着相同明文的代换结果也一定是相同的。然而，语言一般都有其本身的特性。我们可以利用语言本身的特性从加密结果中分析出一些结果。
图 9：英文中字母出现的频率表
https://upload.wikimedia.org/wikipedia/commons/thumb/d/d5/English_letter_frequency_(alphabetic).svg/2000px-English_letter_frequency_(alphabetic).svg.png
以英文为例。英文中每个字母出现的频率是不一样的。随着文本长度的增长，这种规律会愈发明显。图 9 给出了英文中字母出现的频率分布。我们可以看出，字母E在英文中出现的概率最高。随后是 T，A，O 等。由于单表代换密码中，相同字母的代换结果一定相同，因此破解者可以通过分析加密结果中字母/符号出现的频率对单表代换密码进行破译。我们可以考察加密结果中哪个字母出现的频率最高，那个字母的明文很可能就对应 E。另一方面，英文中固定词语出现的频率也会非常高。常用的简单单词，如 THE、IT、IS 等都会频繁出现在发送的信息中。通过英文单词本身的规律，加上适当的尝试后，破解者很可能恢复出明文，同时将字母的映射表也一并恢复出来。
人类需要更加安全的加密方法。意大利文艺复兴时期的天才阿尔伯蒂（Leon Battista Alberti）[41]进一步改进了凯撒密码，并在加密过程中使用了多字母映射表。阿尔伯蒂的此种加密方法在 1553 年被意大利人贝拉索（Giovan Battista Bellaso）[42]改进，并由法国人维吉尼亚（Blaise de Vigenère）[43]所推广。因此，这个密码被称为「维吉尼亚密码」（Vigenère Cipher）[44]。维吉尼亚密码是一个相对很安全的加密系统，自提出后的 300 多年间都未得到破解。因此，这一密码很长时间以来都享有至高荣誉：无法破译的密码（Le chiffre indéchiffrable）。
图 10：维吉尼亚
https://en.wikipedia.org/wiki/Vigen%C3%A8re_cipher#/media/File:Vigenere.jpg
然而，维吉尼亚密码也不是安全的。事实上，以维吉尼亚密码为代表的「多表代换密码」均有安全漏洞。1863 年，德国人卡斯基（Friedrich Kasiski）[45]公开了一份针对维吉尼亚密码等多表代换密码的破解方法，称为「卡斯基检测法」[46]。不过有间接证据表明，早在 1863 年之前的 10 年，英国数学家巴贝奇（Charles Babbage）[47]也提出了类似的破解方法。
军事活动一直是加解密的核心场景。多表代换密码变得不安全后，如何秘密地传递信息重新成为了军事活动中的核心问题。如果传输的军事情报被对方获取并破解，对方就可以根据情报采取行动，在战争中取得巨大的优势。但是，更加安全的加密方法一般意味着更加复杂的加密和解密过程，手工加解密的方式已经变得不太可行。一方面，复杂的加解密过程容易导致发送方在手工加密时发生错误，从而导致接收方无法正确解密密文。另一方面，手工加解密的速度较慢，这会使得友军就无法及时恢复明文，使得发送的明文丧失一定的时效性。
为了方便加密和解密，同时保证安全性，人类开始考虑设计精巧的机器，让机器帮助人类实现信息的快速加解密。在二次世界大战期间，人类发明了多种加密机器。在第二次世界大战期间，英国使用了被称为「X型」（Type X）的密码机[48]。美国人使用了更为先进的「SIGABA」（或称「M-134」）密码机[49]。然而，最为经典的加密机则是第二次世界大战时德军所使用的「恩格玛机」（Engima Machine）[50]。
德国工程师 Arthur Scherbius 于第一次世界大战的末期出于商业用途发明了恩格玛机。它的出现很快得到了德国军方的注意。图 11 为恩格玛机，它由 4 个部分组成：
• 最上面是 3 个「转子」（Rotors），用于设置密钥；
• 然后是「灯盘」（Lampboard），发送方/接收方可以从灯盘上快速得到加密/解密结果；
• 再往下是「键盘」（Keyboard），发送方/接受方通过键盘输入明文/密文；
• 最下面是「插接板」（Plugboard），同样用于设置密钥。
图 11：恩格玛加密机
https://upload.wikimedia.org/wikipedia/commons/3/3e/EnigmaMachineLabeled.jpg
恩格玛机具有两个非常重要的优势。第一，恩格玛机的使用非常方便。设置好密钥和加密/解密模式后，发送方/接收方只需要在键盘上按下明文/密文，灯盘上就会对应地显示密文/明文。图 12 是恩格玛机的使用演示。可以看出，当按下明文 N 时，灯盘上的字母 Y 就被点亮，Y 就是 N 的加密结果。
图 12：恩格玛加密机加密演示
Numberphile 制, 阿尔法小分队科教组译. 158,962,555,217,826,360,000 (Enigma Machine).
http://www.bilibili.com/video/av2883992/. 01 分 16 秒
第二，恩格玛机非常便携。恩格玛机的体积不大，易于携带。德军可以将恩格玛机装在军舰、飞机、甚至坦克上。
第三，恩格玛机的密码似乎非常安全。最初的恩格玛机的转子只有 3 个，插接板也没有那么复杂，还不够安全。波兰密码学家 Marian Rejewski、Jerzy Różycki 和 Henryk Zygalski 研制出了名为「炸弹」的电子计算机，用来对其进行破解。1938 年，恩格玛机将转子个数由 3 个增加到 5 个，使用时需要选择正确的 3 个转子，并按照正确的顺序安装在恩格玛机。与此同时，插接板也变得更加复杂，一共需要正确连接插接板上的 10 对字母。如此的设定使得德军认为恩格玛机是一个牢不可破的系统（Unbreakable System）。
恩格玛机的密钥一共有多少种可能呢？首先，要从 5 个转子中选择 3 个转子，按照正确的顺序安装在恩格玛机上。其次，每个转子有 26 个初始位置，加解密时，每个转子的 26 个初始位置都要正确设定。最后，要按照图 13 的方法，用插线在插接板上正确连接 10 对字母，有其中一对连接错误都不行。
图 13：恩格玛加密机的插接板连接演示
Numberphile 制, 阿尔法小分队科教组译. 158,962,555,217,826,360,000 (Enigma Machine).
http://www.bilibili.com/video/av2883992/. 07 分 39 秒
经过计算可以得到，恩格玛机的密钥总数为 158,962,555,217,826,360,000。即使到了现在，用最快的计算机尝试所有密钥也几乎是不可行的。
图 14：恩格玛加密机的密钥总数
Numberphile 制, 阿尔法小分队科教组译. 158,962,555,217,826,360,000 (Enigma Machine).
http://www.bilibili.com/video/av2883992/. 09 分 52 秒
然而，看起来如此安全的恩格玛机，在剑桥大学的年轻数学家图灵（Alan Turing）[51]面前也并非想象的那样牢不可破。图灵一直从事二进制数学和可编程计算机理论方面的研究。接到英国密码分析中心的招聘后，图灵从波兰的「炸弹」电子计算机入手，分析恩格玛机新增的转子和插接板设置。经过艰苦的努力，图灵利用了恩格玛机的一些瑕疵，设计并实现了新的「炸弹」（Bombe）计算机，用于破解恩格玛机。「炸弹」的破解速度非常快，效率高的时候，「炸弹」可以在 1 小时以内解密所有密文。果然，机器的密码还是要用机器来破解。
图 15：图灵设计并实现「炸弹」的重制机器
http://www.cryptomuseum.com/crypto/bombe/img/bombe_replica_full.jpg
「炸弹」中的很多思想都可以看作现代计算机的雏形。图灵为现代计算机的诞生做出了突出贡献。为了纪念图灵，人们设立「图灵奖」[52]，奖励为计算机做出贡献的计算机科学家们。
密码学家和计算机科学家们继续为安全加密算法的设计做出不懈的努力。他们设计了多种安全可靠的加密算法。比较著名的有 1977 年 1 月由美国国家标准局公布的数据加密标准（Data Encryption Standard，DES）。DES 的出现是现代密码学的标志之一，意味着密码学已经上升为数学和计算机科学的交叉学科。DES 被使用了将近 20 年。为了适应现今的安全要求，1998 年密码学家们推出了一系列替代 DES 的新型算法，如 MARS、RC6、Sperpent、Twofish 等。2000 年 10 月 2 日，美国国家标准和技术协会（National Institution of Standards and Technology，NIST）宣布，经过 3 年多的筛选和测评，比利时密码学家Daemen 和 Rijmen 共同设计的 Rijndael 加密算法成为了新的加密标准。这个新的算法被命名为高级加密标准（Advanced Encryption Standard，AES）[53]。现今，AES 已经被广泛使用。密码学家们仍然没有发现AES的致命缺陷。我们可以认为，到现在为止，AES 仍然是安全的加密算法。
图 16：比利时密码学家 Daemen 与 Rijmen
https://geek.hellyer.kiwi/files/2013/12/aes-devs.jpg
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
