科普 | 密码学极速入门，Part-1

-广受欢迎的加密通讯工具——OpenSSL，其中的部分代码-

关于密码学的内在原理，一直被认为是少数专家或数学家才能涉足的领域，其中的技术细节在大多数人看来就像变魔术一样。考虑到现代密码学的复杂程度，我们可以理解为什么很多人对密码学存在这些误解；但不了解密码学，可能会做出很多弊大于利的决定，比如英国的加密禁令提案（Encryption Ban），澳大利亚的援助和访问法案（Assistance and Access Bill）等。

在本篇指南中，我们会帮助大家掌握学习密码学所需的入门知识、对不同密码学体系的发展历程进行简介，并对当前三个最流行的密码学领域——流密码、分组密码、公钥密码，进行快速上手指导。

密码（Ciphers）

“密码”（Cipher）指的是对消息进行加密或解密的算法，也是密码学的基石。加密算法 (E) 使用密钥 (k) 对消息 (m) 进行加密，并生成密文 (c)；类似地，解密算法 (D) 使用密钥 (k) ，对密文 (c) 进行解密。如下列所示：

-加密算法 ‘E’ 及解密算法 ‘D’ –

上述过程也意味着，一种算法要想被称为“密码”（算法），还必须满足以下的一致性方程特性，确保密文可以被解密。

式子表明着如果你使用密钥 K 对消息进行加密，也能使用密钥 K 对密文进行解密，并得到与原来消息一摸一样的输出。

其中一种最古老、最简单的密码就是凯撒密码（Caesar Cipher）——直接从字母表中选取特定位置，替换掉原消息中的字符。

-凯撒密码出现于公元 50 年，凯撒大帝使用字母表跳三位的字来替换原来的消息内容，用于军事通讯-

下面的例子就是经过后三位字符替换过后的密文形式（上面一行为原文，下面一行为密文）：

凯撒密码可以用下列式子表示：

虽然这种做法符合我们对密码的定义，但是它非常不安全。只要攻击者知道密文是以这种方式加密，就能通过尝试另外 25 种组合进行破译；即使攻击者不知道密文使用了凯撒密码，他们也能够观察到密文中的规律进行破译。

虽然这种做法符合我们对密码的定义，但是它非常不安全。只要攻击者知道密文是以这种方式加密，就能通过尝试另外 25 种组合进行破译；即使攻击者不知道密文使用了凯撒密码，他们也能够观察到密文中的规律进行破译。

在进一步介绍更安全的加密算法之前，我们得先聊聊什么是 Xor 运算。

XOR（异或运算）

Xor 运算 ，又称为 “异或门”，是一种布尔变量逻辑判断，能接收 1 或 0 作为输入：如果输出 1 则表示两个输入不同；输出 0 则表示两个输入相同。 下图的真值表列出了经过异或运算后，所有可能的输入输出组合：

异或运算也经常用符号 ⊕ 来表示：

0 ⊕ 0 = 0

0 ⊕ 1 = 1

1 ⊕ 0 = 1

1 ⊕ 1 = 0

关于异或逻辑，以下有几点重要的特性：

1. 异或运算结合律：a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c
2. 对自身进行异或运算结果为 0 : a ⊕ a = 0
3. 对 0 求异或，结果为自身：a ⊕ 0 = a

根据上述异或运算的规则，我们知道 a ⊕ b ⊕ a 等同于 a ⊕ a ⊕ b，也等于 0 ⊕ b，运算结果为 b。要注意的是，这些异或运算特性只适用在 1 和 0 ，因此对不同 进制 的数字进行异或运算之前，需要先将其转换为二进制。例如：

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

接着，我们可以开始介绍第一种安全密码了。

一次性密码

Frank Miller 在1882 年提出了一次性密码（One-time pad）的概念——加密：将消息和私钥进行异或运算得到密文；解密：将密钥和密文进行异或运算得到原消息，这个过程类似于前面提到的 a ⊕ b ⊕ a = b 。一次性密码的定义如下所示：

该密码的一致性方程也很容易证明：

一次性密码非常容易上手，假设我们要加密一串字段“Message”，首先可以通过 ASCII 字符集 将“Message”转换为二进制数据（由 1 和 0 组成）。

现在，我们需要一组 56 位随机二进制数（私钥）来对明文进行异或运算，该私钥随机程度越高越好！

-从 random.org 生成的随机数-

我们将明文和私钥的每一位进行异或运算。

运算后的结果就是我们的密文了！要解开密文也很简单，我们只需要将密文和刚才生成的私钥进行异或运算，并转码回 ASCII ，就能得到原消息。

这种密码简单易用，而且还有个很有意思的特点。一次性密码具有所谓的完全保密性，这意味着从数学角度来说，攻击者不可能从密文（m⊕k 的结果）推得任何原消息的内容，当然也不可能破译。

既然我们已经有了简单易用，且不可能破译的密码，为什么我们还会想用其他的密码呢？根本原因在于，一次性密码虽然很有效，但是他有一些重大的缺陷。

第一个缺陷是，不论我们想要加密什么样的消息，都需要有和原消息一样长或是更长的私钥用于加解密。而且为了让密文接收者能够解密密文，需要有绝对安全的通信方法把私钥给到接收者；这就形成一个悖论，如果有这种安全通道，那不如直接把原消息发过去得了。

第二个缺陷可以从 “一次性密码” 的名称中发现。针对不同消息，同一个私钥每回只能使用一次；如果对多个消息重复使用同一个私钥，其引发的问题可以从数学推导上看出。

假设我们有两条消息 m1 和 m2 ，分别使用相同的私钥 k 进行加密（使得我们的系统变成 “二次性密码”）。通过异或运算，我们会得到以下密文：

从上图，我们可以从密文 C1⊕ C2 得到 m1⊕ m2 。对于攻击者来说，他们就能基于这种关联性，通过各种统计分析、频率分析、模式匹配，或是使用 2006 年提出的自然语言处理方法 ，来获得原消息的内容。我不会深入解释存在这种关联性具体造成的危害（感兴趣的可以看 这里 深入了解），这里只是形象的说明当同一个私钥被使用的次数越多（“三次”、“四次”……？），密码的安全性就越低。

现在我们已经具备 XOR 加密和一次性密码的基础知识，是时候了解其他更实用的加密方法了。

流密码（Stream Ciphers）

一次性密码具有非常好的安全性，这意味着手上只有密文的情况下，攻击者不可能进行破译。但是好的安全性基于长度大于等于原消息的私钥，这使得一次性密码并不实用，因为如果加解密双方有很好的方法来传递消息和私钥，他们直接传递消息就好，没必要进行加密。

为了让一次性密码更加实用，我们引入 “流密码” 的概念。流密码的核心思想是——以“伪随机”密钥替代一次性密码中的 “随机” 密钥，伪随机密钥产生自 密码学安全 伪随机数生成器（ CSPRNG ，Cryptographically Secure Pseudo-random number generator ）。要注意的是，CSPRNG 不同于一般的伪随机数生成器，因为 CSPRNG 产生的数据必须和真实随机数看起来没有区别才行。

CSPRNG 是一种算法（或函数），能产生一长串数字，类似于随机数的性质。因为随机数很难生成，所以 CSPRNG 要依靠种子（seed）来决定初始状态及将来产生的数；CSPRNG 从相对较小的起始种子生成海量的随机数（例如从 128 bit 的种子生成几 GB 的随机数）。如果起始种子是已知的，则随后产生的所有数都是已知的，也就是说 CSPRNG 具有确定性；这也导致CSPRNG 产生的数，其随机程度完全取决于种子的随机程度。

为了让一次性密码更加实用，我们可以根据所需长度，使用伪随机数生成器的输出替换原来的私钥；这样的话只要传递初始种子就可以了。因为 CPRNG 具有确定性，使用相同种子能得到相同输出（也就能得到相同的 key 用来加解密）。

为了更好理解，我们先看看原来的一次性密码：

使用伪随机数生成器的输出 G(K)，替换原来的私钥 K：

使用伪随机数生成器的输出 G(K)，替换原来的私钥 K：

（注：图例中只是其中一种流密码，称为同步流密码。还有一种方法称为 “ 自同步流密码 ”，使用密文中的前几位数计算出密钥中的每一位。）

替换后的私钥可以远远短于要加密的消息，使得分配及管理私钥更为方便，进一步改善了一次性密码不实用的问题。但这种做法也带来了新的问题：

将原来完全随机的私钥替换为安全随机数生成器的输出，会导致私钥长度比原消息短，使得我们的密码不再具有完全保密性。因此流密码的安全性取决于我们的伪随机数生成器的不可预测性。如果可以预测 CSPRNG 的输出，则可以获得明文消息。以下是大家熟知的一些使用弱流密码的密码系统：

802.11b WEP：WEP 是一种给 WiFi 数据做加密的算法，它使用的流密码称为 RC4 。因为流密码中不能一直使用同个密钥，所以长期使用的密钥包含一个每次都会变动的值 “IV”；然而 “IV”只有 24 位，也就是说加密超过 5000 条消息后，就会有五成的概率出现相同的密钥。

CSS：DVD Forum 使用内容扰乱系统（CSS, Content Scramble System）来管理 DVD 的数字版权，使得仅有获得授权的应用才能访问 DVD 内容。CSS 使用 40 位的密钥，而 40 位的密钥空间较小，可以相对快速地暴力激活成功教程。（尽管密钥是 40 位，但考虑到 CSPRNG 的技术特点，只要猜出 17 位组合后，系统便可能被完全激活成功教程。）

现在我们也掌握了流密码的知识，可以进一步讨论下一个密码系统——分组密码。

分组密码（Block Ciphers）

分组密码是另一种能用于加解密数据的方法。分组密码包含两种算法：E 用于加密，D 用于解密，同时也用到了密钥 K 。

分组密码的核心在于，要加密的明文和输出的密文长度始终相同，为一固定量。该固定量称为 “block size”（译者注：不要与区块链语境下的 “block size” 搞混哦；后文将该词译为 “消息大小”），大小取决于所使用的分组密码算法。另外，私钥 K 的长度被称为密钥大小，也是固定量。常见的两种分组密码分别是 3DES 及 AES —— 3DES 具有 64 位的消息大小和 168 位的密钥； AES 具有 128 位的消息大小和 128 、192 或 256 位的密钥。

因为分组密码把可能的区块映射到其他的每一个区块，所以也被称为 “用密钥完成的置换”（Keyed Permutations） 或是 “伪随机置换”（Pesudorandom Permutations）。非常重要的一点是，私钥决定了输入的区块和相关密文区块的映射关系，而且是一对一排列的，所以只要知道私钥就能解密密文。

第一个比较重要的分组密码是 1970 年代 IBM 开发的数据加密标准（ DES ），但 DES 并不安全，很快就被 3DES 取代；紧接着 3DES 又被 1997 年开发的高级加密标准（ AES ）所取代。AES 是在国家标准与技术研究所（ National Institute of Standards and Technology ）的要求下制定的标准化分组密码。 AES 是当今使用的最常见的分组密码，重要性大大超过 DES 和 3DES ，所以我将着重介绍 AES 。

在我解释 AES 到底是怎么运作之前，先提醒一下我会跳过很多技术细节，如果有人对这深入这方面领域有兴趣，可以从 这里 获得你想要的。

AES 及大部分分组密码，都是通过迭代进行运作的，输入的文本消息会使用连续的密钥以迭代的方式进行加密。第一步是获得一个密钥 K，密钥一般是 128 位、192 位或 256 位的，在这里我们只演示 128 位的 AES；然后拿该密钥推导出一系列的 Round Keys 来加密我们的消息。

上图例子中，我们输入 128 位（16 字节）的密钥，并通过 Rijndael 密钥方法 将密钥扩展成 11 个 16 字节的子密钥。接着，AES 将原消息放入轮次函数 R(k n , m) 进行独立加密计算，每次计算把扩展出来的轮次密钥 k n 及消息状态 m 作为输入，总共进行 10 次。

因为 AES 只能用在 128 位的消息上，因此我们把输入的消息 m 表示成 4×4 矩阵的单字节单元，同时也能把轮次密钥 表示成 4×4 的矩阵，这样就可以对消息及其中间状态进行异或运算了。

首先，输入的消息和第一个轮次密钥进行 XOR ，再通过字节替代（ ByteSub ）、行位移（ ShiftRows ）、列混淆（ MixColumns ）等运算，输出转变后的消息状态作为结果（这些步骤会在后面做解释）。接着我们使用不同的轮次密钥重复上述这些步骤 10 次，唯一的不同点在于最后一次的计算不包含列混淆（ MixColumns ）。最终的消息状态和第十一个轮次密钥（k 10 ）进行异或计算，得到最后的输出。下面简述了每一轮次的计算中包含的三种步骤：

字节替代（ ByteSub ）：根据替换表，将消息状态矩阵中的每一个字节，替换为相应的字节。

-在 AES 使用的替换表中，每一个字节单元以 16 进制表示。如，字节 9a 会替换为 b8 –

行位移（ ShiftRows ）：定量移动每一行。第一行不移动，第二行左移一位，第三行左移两位，第四行左移三位。

列混淆（ MixColumns ）：对消息状态中每一列进行线性变换。

目前为止，我们已经能使用 AES 来加密数据。然而，你可能很快能发现 AES 的局限性——没办法在只用一次 AES 的情况下，对超过 128 位（或 16 字节）的消息进行加密。要对超过 16 字节的消息进行加密，我们需要引入 模式加密（ Modes of operation ） 概念。