1 本章概要

本章将介绍历史上几种著名的密码：

凯撒密码
简单替换密码
Enigma

此外，还介绍两种破译密码的方法：

暴力攻击
频率分析

最后，我们还将思考密码算法与密钥之间的关系。
本章所介绍的密码在现在都已经不再适用了，但在寻找密码弱点的方法、破译密码的思路以及密码算法与密钥的关系等方面，这些密码与现在密码技术依然是相通的。

2 凯撒密码

2.1 什么是凯撒密码

凯撒密码是通过将明文中所使用的字母表按照一定的字数“平移”来进行加密的。

2.2 凯撒密码的加密

例如，将 yoshiko 这个女性的名字，加密：
y -> B
o -> R
s -> V
h -> K
i -> L
k -> N
o -> R
这样，明文 yoshiko 就被加密为了密文BRVKLNR。凯撒密码中，将字母表中的字母平移这个操作就是密码的算法，而平移的字母数量则相当于密钥。
在本例中，密钥为3：

2.3 凯撒密码的解密

我们只需要反向平移3个字母就可以解密了：
B -> y
R -> o
V -> s
K -> h
L -> i
N -> k
R -> o
这样就得到了明文 yoshiko，但是密钥 3 必须由发送者和接受者事先约定好。

2.4 用暴力破解来破译密码

通过上面的讲解，我们知道对于发送者用凯撒密码加密过的密文，接受者是能够进行解密的，但是接受者以为的人在看到密文 BRVKLNR ，是否能够进行破译
得到明文呢？在凯撒密码中，密钥就是字母表平移的字数。因此可以按顺序将这 26 种密钥都尝试一遍：
BRVKLNR -> 用密钥 0 解密 -> brvklnr
BRVKLNR -> 用密钥 1 解密 -> aqujkmq
BRVKLNR -> 用密钥 2 解密 -> zptijlp
BRVKLNR -> 用密钥 3 解密 -> yoshiko
……
BRVKLNR -> 用密钥 25 解密 -> cswlmos
尝试一遍都，发现当密钥为 3 时，可以解密出有意义的字符串 yoshiko 。这就意味着我们仅仅根据密文就推测除了密钥和明文，这样的密码有什么用呢？
凯撒密码实在是太脆弱了，无法保护重要的密码。

上面介绍的这种密码破译方法，就是讲所有可能的密钥全部尝试一遍，这种方法称为暴力破解（brute-force attack）。由于这种方法的本质是从所有的密钥
中找出正确的密钥，因此又称为穷举搜索（exhausive search）。

3 简单替换密码

3.1 什么是简单替换密码

将明文中所使用的字母表替换为另一套字母表的密码，如下图就是一个简单替换密码的对应表：

3.2 简单替换密码的加密

按照上图的替换表，对明文 yoshiko　进行加密：
y -> K
o -> B
s -> L
h -> T
i -> J
k -> S
o -> B
就得到密文：KBLTJSB。

3.3 简单替换密码的解密

需要根据使用的替换表进行解密。

3.4 简单替换密码的密钥空间

yoshiko 用凯撒密码（密钥为 3 ）加密后的密文是 BRVKLNR ，二用简单替换密码（密钥为上图）加密后的密文则是 KBLTJSB。单从密文上来看，我们无法
判断出凯撒密码和简单替换密码到底哪一种更难破解。

凯撒密码可以通过暴力破解来破译，但简单替换密码很难通过暴力破解来破译。这是因为简单替换密码中可以使用的密钥数量，比凯撒密码要多得多。

为了确定这一点，我们计算一下简单替换密码中可以使用的密钥总数。一种密码能够使用的“所有密钥的集合”称为密钥空间（keyspace），所有可用密钥的总数就是密钥空间的
大小。密钥空间越大，暴力破解就越困难。

简单替换密码中，明文字母表中的 a 可以对应A，B，C，…，Z 这 26 个字母中的任意一个，b 可以对应除了 a 所对应的字母以为的剩余 25 个字母中的任意一个。
以此类推，我们可以计算出简单替换密码的密钥总数为：
26 * 25 * 24 * 23 * … * 1 = 403291461126605635584000000
即使美妙能够遍历 10 亿个密钥，也要花费 120 亿年的时间。

3.5 用频率分析来破译密码

频率分析利用了明文中的字母的出现频率与密文中的字母的出现频率一致这一特性。例如：

首先，我们统一一下这段密文中每个字母出现的频率：

为了找到破译的线索，我们再来看一下英语文章中所使用的字母的频率，一般的英语文章中出现频率最高的字母是 e 。而上图中出现频率最高的两个字母是 I 和 Y，
我们假设它们中的其中一个是 e 。然后将密文中的 Y 全部替换成 e ，替换后的密文如下：

英语中出现最多的单词是 the ，因此我们可以寻找一下以 e 结尾的 3 个字母的组合，结果我们发现 MEe 这3个字母的组合是最常出现的，而且 MEe 出现在
密文的开头，因此 MEe 很可能就是 the 。于是，我们再假设 M -> t，E -> h。得到如下图的表：

让我们动员自己所有的英文词汇，在上面的文字中继续寻找可能的组合。我们发现中间有一个词 thPee 比较可以，这个词不会就是 three 吧（P -> r）？
除了高频字母以外，密文中的低频字母 Q 也可以找到一些相关的组合。直到得到最后通顺的明文，有以下结论：

除了高频字母以外，低频字母也能够成为线索。
搞清开头和结尾能够称为线索，搞清单词之间的分隔也能够成为线索。
密文越长越容易破译。
同一个字母连续出现能够成为线索（这是因为在简单替换密码中，某个字母在替换表中所对应的另一个字母是固定的）。
破译的速度会越来越快。

4 Enigma

4.1 什么是 Enigma

Enigma 是由德国人于 20 世纪初发明的一种能够进行加密与解密操作的机器。Enigma 这个名字在德语里是“谜”的意思。

4.2 用 Enigma 进行加密通信

Enigma 是一种由键盘、齿轮、电池和灯泡所组成的机器，通过这一台机器就可以完成加密和解密两种操作。

发送者和接收者各自拥有一台 Enigma。发送者用 Enigma 将明文加密，将生成的密文通过无线电发送给接收者。接收者将接收到的密文用自己的 Enigma 解密。

由于发送者和接收者必须使用相同的密钥才能完成密码通信，因此发送者和接收者会事先收到一份叫国防军密码本的册子。发送者和接收者按照册子指示来设置 Enigma。

4.3 Enigma 的构造

Enigma 的构造如下图。它能对字母表中的 26 个字母进行加密和解密操作，这里将字母的数量简化为 4 个：

每当按下 Enigma 上的一个键，就会点亮一个灯泡。而接线板和轮子在每次输入的时候都会变化，这样的组合让 Enigma 看起来像是一个能够动态变化的操作。

4.4 Enigma 的加密

在进行通信之前，发送者金和接收者双方都需要持有国防军密码本，国防军密码本中记载了发送者和接收者需要使用的每日密码。

1.设置 Enigma

发送者查阅国防军密码本，找到当天的每日密码，并按照该密码来设置 Enigma。具体来说，就是接线板和转子排列。

2. 加密通信密码

接下来，发送者需要想出 3 个字母，并将其加密。这 3 个字母称为通信密码。
通信密码的加密也是通过 Enigma 完成的。假设发送者选择的通信密码为 psv，则发送者需要在 Enigma 的键盘上输入两次该通信密码，也就是说需要输入
psvpsv 这 6 个字母。

发送者每输入一个字母，转子就会旋转，同时灯泡亮起，发送者记下亮起的灯泡所对应的字母。输入全部 6 个字母之后，发送者就记下了它们所对应的密文，
假设密文是 ATCDVT（密文用大写字母来表示）。

3. 重新设置 Enigma

接下来，发送者根据通信密码重新设置 Enigma。通信密码中的 3 个字母实际上代表了三个转子的初始位置。每一个转子的上面都印有字母，可以根据字母
来设置转子的初始位置。通信密码 psv 就表示需要将转子 1、2、3 分别转到 p、s、v 所对应的位置。

4. 加密消息

接下来，发送者对消息进行加密。发送者将明文逐字从键盘输入，然后从灯泡中读取所对应的字母并记录下来。例如输入 nacht ，记录下对应的 KXNWP 。

5. 拼接

接下来，发送者将“加密后的通信密码” ATCDVT 与 “加密后的消息” KXNWP 进行拼接，将 ATCDVTKXNWP 作为电文通过无线电发出。

上面就是用 Enigma 进行加密的操作步骤，看来还真是挺麻烦的。

4.5 每日密码与通信密码

每日密码在这里不是用来加密消息的，而是用来加密通信密码的。也就是说，每日密码是一种用来加密密钥的密钥，这种密钥，一般称为密钥加密密钥（Key Encrypting Key，KEY）。

4.6 避免通信错误

在通信密码的加密中，我们需要将通信密码 psv 连续输入两次，即 psvpsv。这是因为接收者可以对通信密码进行校验，避免错误。

4.7 Enigma 的解密

1.分解

接收者将接受到的电文分解为两部分，即开头的 6 个字母 ATCDVT 和剩下的字母 KXNWP。

2. 设置 Enigma

接收者查阅国防军密码本中的每日密码，并按照该密码设置 Enigma，这一步和发送者进行的操作是相同的。

3. 解密通信密码

接下来，接收者将加密后的通信密码 ATCDVT 进行解密。接收者在 Enigma 的键盘上输入 ATCDVT 这 6 个字母，然后将亮起的灯泡对应的字母 psvpsv 记下来。
因为是 psv 重复两次的形式，所以接收者可以判断在通信过程中没有发生错误。

4. 重新设置 Enigma

接下来，接收者根据通信密码 psv 重新设置 Enigma。

5. 解密消息

接下里，接收者将电文中的剩余部分 KXNWP 逐一输入，将灯泡的结果记下来，得到了 nacht。

4.8 Enigma 的弱点

1. 将通信密码连续输入两次并加密

这样密码破译者知道密文开头的 6 个字母被解密后的明文一定是 3 个字母重复两次的形式

2. 通信密码是人为选定的

有可能使用 aaa、bbb 或者生日，女朋友的名字当做密码。密码系统中使用的密钥不能是人为选定的，而应该使用无法预测的随机数来生成。

3. 必须派发国防军密码本

如果落到敌人手里，就会带来大麻烦。如果现在所使用的国防军密码本被敌人得到，哪怕只泄漏了一本，也必须重新制作新的密码本并发到全军。
必须配送密钥这个问题，将在第五章详解。

4.9 Enigma 的破译

即使得到了 Enigma 的构造，但是由于 Enigma 的设计并不依赖于“隐蔽式安全性”，只要不知道 Enigma的设置（密钥），就无法破译密码。但是，
每日密码在一天之内不会变，即一天内截获的所有通信，都是用同一个密码进行加密的；以及通信密码都会重复两次。以 ATCDVT 为例，即知道第一个字母和
第四个字母，都是由相同的明文加密得到的；另外，由于一个轮子只有26个可能。最终经过了许多密码专家的破译，包括现代计算机之父阿兰图灵，最终破译了这个密码。

5 思考

5.1 为什么吗要将密码算法和密钥分开呢

我们来列举一下本章介绍过的密码系统的“密码算法”和“密钥”。

密码系统	密码算法	密钥
凯撒密码	将明文中的各个字母按照指定的字母数平移	平移的字母数量
简单替换密码	按照替换表对字母表进行替换	替换表
Enigma（通信密码的加密）	使用Enigma密码机，通过接线板的接线方式、三个转子的顺序、每个转子的旋转位置对字母进行替换	接线板的接线方式、转子的顺序、转子的旋转位置
Enigma（通信电文的加密）	使用接线板的接线方式和三个转子的顺序固定的Enigma密码机，按照每个转子的旋转位置对字母进行替换	每个转子的旋转位置

仔细研究一下每一对密码算法和密钥的组合就会发现，在密码算法中必然存在可变部分，而这些可变部分就相当于密钥。当密码算法和密钥都确定时，加密的方法也就确定了。
如果每次加密都必须产生一个新的密码算法，那真是太诡异了。对于已经开发出的一种密码算法，我们总是希望能够重复使用。

将密码算法和密钥分开的意义正在于此。密码算法是需要重复使用的，但在重复使用同一种算法的过程中，该算法被破译的可能性也在逐渐增大。因此，
我们就在密码算法中准备了一些可变部分，并在每次通信时都对这部分进行改变，而这一可变部分就是密钥。

将密码算法和密钥分开考虑，就解决了希望重复使用，但重复使用会增加风险这个难题。

密钥才是秘密的精华。因此，在密码技术中，如何管理密钥是一个重要的课题。这将在第十一章详解。

每个人都可以拥有相同品牌的锁，但每个人都有不同的钥匙。锁的设计师公开的——锁匠都带有详细图的书，而且绝大多数好的设计方案都在公开专利
中进行了描述——但是钥匙是秘密的。

6 本章小结

密码系统：凯撒密码、简单替换密码以及 Enigma。
密码破译：暴力破解、字母频率分析。

7 小测验

凯撒密码中，如果存在如 c -> C， q -> Q这样，明文中的字母被替换成了相同字母的密文的情况。于是Alice就想：如果替换表中不出现这种被替换
为相同字母的情况，那么密文应该会更难被破译吧？请问 Alice 的想法正确吗？