[译] 密码学速成课

长久以来，密码学的内部工作原理往往被认为是专家和数学家所独有的领域，而它的技术性也很大程度上被归功于魔法。但是，如果能把现代密码学复杂的本质讲出来，其实密码学也是可以理解的。然而，由于对英国提出的『加密禁令』和澳大利亚提出的『援助与访问法案』等主题缺乏了解而导致的许多全球运动，显然是弊大于利的做法。

如果你想要了解密码学，本文将会以速成课的形式讲到你需要知道的几乎所有知识。下面我将简要介绍各种加密系统的历史，并着重讲一下密码学中三种最流行的方向：流密码、分组密码以及公钥密码系统。

密码

密码是密码学的基石。密码就是一组处理信息加密和解密的算法。一个加密算法（E）需要一个密钥（k）和一段信息（m），就可以产生一段密文（c）。同样的，一个解密算法（D）需要一个密钥（k）和一个之前的密文（c）。可以表示成下面的形式：

这意味着要成为一个密码，它必须满足下面的等式才可以成功解密：

这个等式说明了如果你是用密钥 K 加密一段信息，那么你就可以通过密钥 K 解密出相同的信息。

作为最古老也最简单的密码之一的凯撒密码，就是用字母表中固定偏移位置的字母替换一段信息中的每一个对应的字母的加密方法。

在下面的例子中，信息中的每个字母就移动了三个字符：

这个密码可以用数学方法表示成下面的形式：

虽然这种加密方式符合我们对密码的定义，但是它一点也不安全。如果一个攻击者知道使用的是凯撒密码，那么他只需要尝试所有的 25 种组合就可以破译这个密码。即使他不知道使用的是凯撒密码，他也可以通过观察密文中的字母模式来发现使用的就是凯撒密码。

为了接下来要讨论的更安全的加密算法，我们不得不介绍一种运算：XOR（异或）。

XOR

XOR 或者说『异或』门是一种布尔数字逻辑门，它接收两个输入值 0 或者 1，如果这两个输入值不同则返回 1，如果相同则返回 0。它可以用下面的真值表来表示所有输入输出的可能：

这个运算常常用符号⊕来表示，就像下面这样：

0 ⊕ 0 = 0，

0 ⊕ 1 = 1，

1 ⊕ 0 = 1，

1 ⊕ 1 = 0

XOR 有以下几个重要的性质：

1. 结合律：a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c
2. 与自身运算得 0：a ⊕ a = 0
3. 与 0 运算得它本身：a ⊕ 0 = a

这就意味着 a ⊕ b ⊕ a = b，因为根据上面的性质和法则我们知道 a ⊕ a ⊕ b 就等于 0 ⊕ b 等于 b。有一点很重要，那就是这个运算只对零和一有效，所有其他进制的数字必须要先转换成二进制。

87 ⊕ 73 = 1010111b ⊕ 1001001b = 0011110b = 30

现在我们可以开始讲我们第一个安全的密码了。

一次性密码本（One-time pads)

根据 Frank Miller 在 1882 年的描述，一次性密码本（同时也叫 Vernam 密码）就是用密钥和原文进行 XOR 来加密的，然后再用密钥和密文的 XOR 来解密获得原文。根据上面的属性，这样做显然是没有问题的，因为：a ⊕ b ⊕ a = b。一次性密码本定义的这一组加密算法可以用下面的式子表示：

这对密码的相容方程可以用下面的式子证明：

接下来，我们将会通过一个简单的例子来展示一次性密码本用起来有多简单。比如我我们要加密一个单词『Message』。第一步是将这个单词转换成二进制（只有零和一的表示形式）。我们可以根据ASCII character set 来转换每一个字母。

现在我们需要一个随机的 56 位的密钥，用来与原文进行 XOR 运算。在这里密钥尽可能的随机是很重要的。

然后我们对原文的每一位进行 XOR 的运算。

得到的结果就是我们的密文。而要解开这段密文的话，我们只需要做同样的操作，然后再通过 ASCII 转换成字母就大功告成了。

这个密码使用和理解起来都不难，但是它还有一个有趣的特性。那就是一次性密码本拥有完美的保密性，这意味着如果一个攻击者只知道密文（也就是 m⊕k 的结果），那么在数学上想要破译获得原文是完全不可能的。

现在我们有了一个甚至可以手动完成的简单易懂的密码，而且它还是数学层面上不能破解的。那么为什么我们还开发了别的密码系统呢？原因在于，虽然一次性密码本有效且易用，但是它有几个致命的缺点。

第一个主要的问题就是对于任何被发出去的信息，密钥长度必须大于或等于原文的长度。对于接收者来说，为了能够成功的解密，必须存在一个安全的能够给接发双方提供传输密钥的通道。在这种情况下，还不如直接在安全通道上传输原始信息。

这个问题还会因为第二个缺点而更加恶化，而第二个缺点就源自于它的名称。一次性密码本的密钥只能使用一次，这意味着每一条信息都需要通过唯一且随机的密钥来加密。而如果用同样的密钥来加密多条信息的话，会导致一个巨大的问题，这个问题还可以很容易的用数学来证明。

让我们假设有两条信息 m1 和 m2，他们使用同样的密钥 K 来加密。那么我们可以通过 XOR 两条密文来得到下面的结果。

这样我们就获得了 m1⊕m2。而攻击者则可以基于这个结果进行各种各样的分析，例如统计分析、频率分析、模式匹配或者使用这篇论文中提到的自然语言处理。这里我不会详细的解释这样为什么是不安全的，但是如果你感兴趣的话，可以阅读这个答案，它生动形象的解释了为什么这样加密是不安全的。而同样的密钥用来加密的次数越多（比如三次或者四次），显然就会越不安全。

现在我们已经了解了 XOR 加密和一次性密码本的基础知识，接下来我们就可以讲一个更实用的加密方法了。

流密码

一次性密码本最大的优点就是它拥有完美的保密性，这意味着如果攻击者只有密文的话，他是不可能破译获得原文的。然而，拥有完美保密性的同时就意味着密钥长度必须大于或等于原文长度。这就让一次性密码本变得非常不实用，因为如果接收双方拥有一个安全信道来传输密钥，那么他们显然可以用同样的机制来传输原文。

为了让一次性密码本更加实用，接下来让我们介绍『流密码』。流密码的关键点在于用『伪随机』密钥来代替一次性密码本的『随机』密钥，也就是说现在要和信息进行 XOR 的密钥是由 密码安全的伪随机数生成器 或者 CSPRNG 生成的。（注意：这不同于伪随机数生成器，因为由 CSPRNG 生成的数据必须与真随机数没有区别）。

CSPRNG 是一个简单的算法（或者说函数），它可以生成大量的数字，并且非常接近随机数的性质。生成随机数是非常困难，CSPRNG 则是依赖一个 种子 来决定初始状态的（同时这也决定了未来生成的数字）。这个算法允许通过相对较小的初始种子（比如一个 128 位的种子可以生成几个 G 的随机数据）生成巨大量的随机数。如果初始种子被知道了，那么所有的子序列数字的生成也就被知道了，也就是说 CSPRNG 是 确定性的 。因为这个原因，所以生成的数字有多随机就取决于初始种子有多随机了。

为了让一次性密码本有更强的实用性，我们可以将密钥替换成伪随机数生成器生成的我们想要长度的数字，并且可以把初始种子作为一个新的密钥。因为 CSPRNG 是确定性的，使用同样的初始种子会获得同样的输出。

让我们说的更明白一点，这是一个传统的一次性密码本：

给定一个伪随机数生成器 G(K)，我们可以用下面的方法来替换 K：

（注意，这个例子只是一种类型的流密码，叫做同步序列密码。还有一个类似的叫做自同步序列密码，它使用密文中前面的数字来计算加密密钥的每一位数字。

这样实用性方面就比一次性密码本高多了，也就是说现在密钥可以比原文短很多，这样密钥的分发也会更好管理。然而，这种方法还是有一个缺点。

那就是替换密钥之后我们的密码已经不再拥有完美的保密性了，因为密钥比原文短。所以现在安全的流密码都是依赖于不可预测的随机数生成器。如果 CSPRNG 的输出是可以预测的话，那么原文就会被破译。这里有几个著名的使用弱流密码的加密系统。

802.11b WEP：WEP 是一个通过 WIFI 加密数据的算法，它使用被称为 RC4 的流密码。因为在流密码中同样的密钥不能被使用多次，所以长期的安全密钥用一个随时变化的值 IV 来串联。然而，IV 只有 24 位，也就是说在加密 5000 条信息之后，同样的密钥就会有 50% 的机会被再次使用。

CSS：Content Scramble System 作为一种数字权限管理的形式被用来加密 DVD，以此来拒绝非授权的内容访问。CSS 使用一个 40 位的密钥，而这个密钥由于只有较小的密钥空间所以可以相对快速的被暴力破解。（虽然密钥只有 40 位，但是因为 CSPRNG 技术的关系，只有在生成 17 位的组合之后这个系统才可以被破解。）

以上已经几乎涵盖了流密码的全部内容，下面让我们进入分组密码。

分组密码

分组密码是另一种加解密数据的方法。一个分组密码由两个算法构成，E 和 D 分别是用来加密和解密的（并且使用同一个密钥 K）。

分组密码主要的知识点在于输入文本的长度总是和结果密文的长度相等也就是固定大小。这个大小就是 Block Size ，它取决于你使用的是哪一种分组密码。还有，密钥 K 的长度（Key Size）也是固定的。有两个很常见的分组密码，他们分别是 3DES（Block Size 是 64 位，Key Size 是 168 位）和 AES（Block Size 是 128 位， Key Size 是 128、192 或 256 位）。

分组密码也被称作 密钥置换 或者 伪随机置换 ，因为它将每一个可能的块都映射到一些其他的块上。这个过程是通过密钥来处理的，密钥决定了哪一个输入块映射到哪一个相对应的密文块上面。因为这是一对一的置换，所以如果知道密钥的话，密文就可以被解密出来。

第一个广为人知的分组密码是 DES（Data Encryption Standard），它是上世纪 70 年代由 IBM 开发的，然后很快人们就发现了它是不安全的，于是就产生了 3DES，而 3DES 也好景不常，就被替换成了 AES（Advanced Encryption Standard），AES 是在美国国家标准与技术研究院呼吁新标准的分组密码后于 1997 年开发的。这里我们会着重讲一下 AES，因为它是现在最常用的分组密码，而 DES 和 3DES 就显得相形见绌了。

现在让我们看一下 AES 是如何工作的。为了简单起见，这里会跳过一些技术细节。如果你想更深入的了解 AES 的相关内容，请查看这篇文章。

AES 和大部分分组密码一样都是通过迭代（就是将输入的文本与一系列密码反复的迭代计算）来工作的。第一步就是将密钥 K（通常来说是 128、192 或者 256 位，这里我们只关注 AES 的 128 位）作为输入，然后将它拓展成一系列环形密钥用来加密我们的信息。

在这里，我们将 128 位（也就是 16 个字节）的输入密钥利用例如 Rijndael key schedule 的密钥拓展算法拓展成 11 个 16 字节的密钥。然后我们将每一轮的密钥 kₙ 和信息 m 作为输入，通过函数 R(kₙ, m) 和之前生成的每一个密钥将信息加密 10次。

因为 AES 是 128 位的块大小，所以我们可以将信息 m 用一个 4x4 的字节矩阵来表示。同时我们也可以将每一轮的密钥用 4x4 的矩阵来表示，这样他们就可以通过代表消息体的单元格来进行 XOR 运算。

首先，输入的信息和第一轮密钥进行 XOR，然后将得到的结果使用下面几个函数进行处理： ByteSub ， ShiftRows 以及 MixColumns （这几个步骤下面会讲到），最后就会得到最新的消息体。接着我们使用每一轮的密钥重复这些步骤 10 次，唯一的区别就是最后一轮不做 MixColumn 处理。最后的消息体再与第 11 轮的密钥进行 XOR 得到我们的结果密文。下面就是之前三个步骤的简要说明：

ByteSub：消息体矩阵中的每一个字节都会用 Substitution Box 中定义的关联字节来替换。

举个例子， 9a 会替换成 b8 。

ShiftRow：每一行都会移动一个确定的数量。第一行不移动，第二行向左移动一次，第三行向左移动两次，第四行向左移动3次。

MixColumns：消息体矩阵的每一列都要进行一个线性变换。

现在我们终于可以使用 AES 来加密数据了。但是你很快就会发现这里有一个很明显的限制，就是你不能使用 AES 来一次性加密超过 128 位（16字节）大小的信息。而为了加密超过 16 字节的信息我们还需要介绍一个概念： 工作模式 。

工作模式

一次性加密超过 128 位的信息有各种各样的方法（或者说工作模式）。其中最简单就是著名的 电子密码本 ，也叫做 ECB。

ECB

ECB 是使用分组密码加密大量数据最简单的工作模式。它将信息简单的分成 16 字节的区块，然后使用密钥将这些区块分别加密。当然了，为了满足 16 字节的划分，原文将不得不进行一些填充。举例来说就是，一个 28 字节的信息需要额外的 4 个字节的填充才可以分成两个 16 字节的区块。在信息被分割成区块之后，每一个区块都会使用密钥分别加密。

虽然这很容易理解，但是也带来了一个明显的问题。因为同样的原文区块将会生成同样的密文区块，这种模式很容易被发现。比如下面使用 ECB 加密的位图：

相同信息区域加密后仍然是相同的，所以这样常用的模式仍然可以被分辨出来。为了消除这个影响，我们需要使用一种更加安全的工作模式。

CBC

CBC（Cipher Block Chaining）和 ECB 的工作方式很相似，只有一点点的不同。那就是在原文的每一个区块被加密之前先与上一个区块的密文进行 XOR 运算，这样就可以让每一个原文的区块都是唯一的。而对于第一个区块来说，就是用原文和一个随机生成的 IV（Initialisation Vector）进行 XOR。

我们再加密之前的那个位图来看看，很显然，这样在直觉上就安全多了。

现在我们已经讲了两种主要的工作模式，还有一些其他的工作模式如果你感兴趣的话可以在这里获得更多的信息。

以上就是关于分组密码我们需要知道的全部内容了，接下来让我们进入密码学中最后一个重要的领域。

公钥密码系统

之前我们讲到的所有的加密技术都是 对称加密 ，这意味着加密和解密使用的都是同样的密钥。而公钥密码系统，也就是 非对称加密 使用的是由『公钥』和『私钥』组成的 密钥对 ，并且允许在不安全的信道上进行传输。这部分马上就会讲到。

公钥密码系统常常用来加密服务器之间的通信，比如发送邮件和浏览网页。但是为了简单起见我们用 Alice 和 Bob 来进行说明：

这里我们有两个用户，Alice 和 Bob 在相互发消息。这里虽然我们用两个用户来消息来类比，但是实际上也可以当成是用户和网页以及邮箱服务器进行通信（或者其他的安全通信）。

现在 Alice 和 Bob 可以自由畅通的进行交流。让我们假设这里有一个偷听者可以偷听到所有的对话。这个偷听者只能偷听信息不能影响数据。

在这里，所有发送的数据都可以被攻击者看见，但是他不能篡改信息。在这种情况下，Alice 和 Bob 就不能进行敏感和保密的信息交流，因为所有的信息都会被攻击者得到。

让我们试试之前讨论的 对称加密 ，但是并没有用。

这种方法完全没有用，因为攻击者可以轻松的截获密钥，并用它来解密。Alice 和 Bob 可以用公钥密码系统来避免这种情况，但是什么是公钥密码系统呢？

什么是公钥密码系统？

公钥密码系统是通过用户生成的一对密钥来工作的：一个公钥，一个私钥。公钥可以广泛传播并且公开分发，而私钥只有用户本人知道。在这个系统中，任何人都可以用接收者的公钥对信息进行加密，但是这个密文只能用接收者的私钥解密。

之所以换成非对称加密会有用是因为用来解密的密钥一直是保密的，它永远都不用在信道上传输。就像你这里看到的，使用这个技术这个解决一部分之前的偷听的问题：

即使攻击者可以截获到 Alice 和 Bob 的所有传输信息，他也不能解密任何消息，因为他并没有获得有关私钥的任何信息。

哇哦，这听起来棒极了，但是这又引出了另一个主要的安全隐患。到目前为止，我们仅仅假设了攻击者可以偷听对话，但是不能修改发送的数据。然而如果攻击者可以纂改传输的信息的话，他们就可以进行中间人攻击了。如果 Alice 和 Bob 使用普通的邮件交流，那么就意味着攻击者就是邮局的工作人员。或者当他们使用电脑网络的时候，攻击者可能是 ISP 的工作人员或者有能力接入被使用的网络设备的工作人员。

在这种情况下，攻击者可以将 Alice 的公钥保存下来，然后把自己的公钥发送给 Bob。当 Bob 加密了他想发送给 Alice 的信息的时候，实际上他把这条信息发给了攻击者，而攻击者就可以在发送给 Alice 之前获取到这条信息，然后纂改这条信息。

这种攻击之所以可以成功是因为两个主要的缺陷。分别是 完整性 和 认证性 的缺失，也就是说用户没办法确认一条信息有没有受到干扰，同时也没有办法确保接收到的信息就是自己想要的用户发送的。而这些缺陷可以通过 电子签名 和 认证中心 来解决。

电子签名

电子签名就是一种确保信息的内容没有被篡改的方法。就像之前提到的那样，一条被用户公钥加密过的信息只能被它的私钥解密，反之亦然。一条被用户私钥加密的信息也只能被它的公钥解密，所以如果 Alice 可以用她的私钥加密一条信息并发送给 Bob 的话，那么 Bob 就可以用她的公钥来解密，这样就可以确认信息的创建者确实拥有 Alice 的私钥。这个过程被称为『签名』。

因为可以对整个信息进行签名，所以通常来说更有效和简洁的方法就是对信息的加密哈希进行签名然后把它包含在信息里面，这样就可以确保信息在创建之后就没有被更改过了。

注意这里有大量的简化，因为『使用私钥加密』完全就是RSA，而其他的加密系统例如Diffie-Hellman 或者 ECC 使用的是完全不同的签名算法例如ECDSA。

但是即使我们不考虑任何的签名算法，目前我们也只是解决了一个问题。Bob 现在可以安全的确认他收到的信息是由私钥的拥有者发送的，并且这个信息没有被篡改。但是，Bob 仍然无法确认他收到的就是 Alice 的公钥。为了解决这个问题，我们需要介绍 认证中心 。

认证中心

CA（Certificate Authority）是一个可以进行电子签名以及针对用户和实体发布公钥的可信第三方。

这是用认证中心自己的私钥制作的，所以任何人都可以确定一个证书是否是由可信的认证中心所发布。因此是否信任一个用户取决于 CA 密钥的有效性。

实际上，这些证书最常见的用途就是保护网络流量。当你到达一个使用HTTPS 的网页时，你可以在浏览器中查看它的数字证书。

这个系统完全依赖于认证中心发布的证书，所以大部分设备和电脑都会预装可信认证中心的清单以及他们的公钥。

这篇文章已经够长了，所以我们将不会再讲解公钥加密系统内部的工作原理了。感兴趣的话这篇文章详细的讲解了RSA 这个同时提供了保密和签名的加密系统。

流密码、分组密码和公钥加密系统有个明显的差异，那就是流密码和分组密码都是对原文的单独的位和字节进行处理，而公钥加密系统则是只对数字进行处理。这意味着任何信息在加密之前都要转换成数字。所以公钥加密系统在加密大量数据时是低效的。而为了让加密大量数据的效率更高，我们可以将对称加密和非对称加密结合在一起。

这个方法就叫做PGP。在 PGP 中，信息是由随机生成密钥的分组密码进行加密的，然后再将这个密钥用接收者的公钥进行加密。这样密文中就包含了一个加密的随机密钥。

这样就高效多了，因为分组密码在加密大量数据时有优势，而非对称加密用来加密解密需要的密钥。这部分仍然属于公钥密码系统，因为用来解密的密钥只能通过私钥的拥有者来获得。

接下来

感谢大家能够看到这里，本文到这里也就要结束了。到目前为止，你应该可以很好的理解流密码、分组密码和公钥密码系统了，同时这也将帮助你更好的了解现代密码学的状态。

对于那些想了解更多的同学，我强烈建议去学习斯坦福大学的在线课程 Cryptography I Course ，这堂课将会对密码学的技术和理论进行更深入的讲解。还有一个很有用的材料是一本书Crypto 101，这本书将会讲到密码学中很多有用的地方以及如何发现加密系统中一些常见的缺陷。而那些对利用编程对现实世界的加密系统进行展示攻击感兴趣的同学可以看看这个 Cryptopals challenges 。