第 3 章 对称密码(共享密钥密码)——用相同的密钥进行加密和解密

第 3 章 对称密码(共享密钥密码)——用相同的密钥进行加密和解密

3.1 炒鸡蛋与对称密码

你做过炒鸡蛋吗?炒鸡蛋是将鸡蛋打到平底锅里,然后将蛋液炒匀。鸡蛋炒好之后就完全分不清原来的蛋黄和蛋白了,也不再是原有的形状了,而是变成了一团混合物。

使用对称密码进行加密,和炒鸡蛋有着异曲同工之妙。为了使原来的明文无法被推测出来,就要尽可能地打乱密文,这样才能达到加密的目的。

炒鸡蛋搅拌的是鸡蛋,而密文打乱的则是比特序列。无论是文本、图像还是音乐,只要能够将数据转换成比特序列,也就能够对其进行加密了。

然而,炒鸡蛋与对称密码有一个很大的不同,那就是炒鸡蛋无法还原成原来的鸡蛋,但密文却必须能够让接收者正确解密才行。因此,如果只是随意地搅拌和混合,则不能称之为加密,而必须仔细设计出一种能够还原的混合方式。

3.2 本章学习的内容

本章我们将学习比特序列运算和 XOR 运算。这两种运算在计算机数据处理中经常出现,因此大家应该在本章中熟悉它们。然后,我们将介绍一种称为一次性密码本的密码系统。一次性密码本是一种绝对无法被破译的密码,这一点已经得到了证明。

之后,我们将具体介绍几种对称密码算法,包括 DES、三重 DES、AES 以及其他一些密码算法。最后,我们将谈一谈在众多对称密码算法中到底应该使用哪一种。

需要注意的是,密码算法有时候会涉及开发者的专利和授权等问题,因此在使用本书中介绍的密码算法时,一定要先调查一下该算法的专利和授权信息。

3.3 从文字密码到比特序列密码

3.3.1 编码

现代的密码都是建立在计算机的基础之上的,这是因为现代的密码所处理的数据量非常大,而且密码算法也非常复杂,不借助计算机的力量就无法完成加密和解密的操作。

计算机的操作对象并不是文字,而是由 0 和 1 排列而成的比特序列。无论是文字、图像、声音、视频还是程序,在计算机中都是用比特序列来表示的。执行加密操作的程序,就是将表示明文的比特序列转换为表示密文的比特序列。

将现实世界中的东西映射为比特序列的操作称为编码(encoding)。例如 midnight(深夜)这个词,我们可以对其中的每个字母逐一进行编码,这种编码规则叫作 ASCII。

m → 01101101
i → 01101001
d → 01100100
n → 01101110
i → 01101001
g → 01100111
h → 01101000
t → 01110100

注意这里的 m01101101 这一转换并不是加密而是编码。尽管在人类看来 01 的序列跟密码没什么两样,但计算机却可以“看懂”这些比特序列,并很快地反应出其所对应的字符串是 midnight

小测验 1 字母→数字的映射和恺撒密码      (答案见 3.10 节)

恺撒密码中所使用的字母表包含 AZ 共 26 个字母。如果我们将A 映射为 0B 映射为 1、……Z 映射为25,那么恺撒密码中平移 3 个字母的加密操作,在这个字母→数字的映射中相当于怎样的运算呢?

3.3.2 XOR

为了让大家理解比特序列运算的概念,我们来介绍一下 XOR 运算。XOR 的全称是 exclusive or,在中文里叫作异或。尽管名字看起来很复杂,但这种运算本身一点都不难。

1 个比特的 XOR

1 个比特的 XOR 运算的规则如下。

0 XOR 0 = 0               (0 与 0 的 XOR 结果为 0)
0 XOR 1 = 1               (0 与 1 的 XOR 结果为 1)
1 XOR 0 = 1               (1 与 0 的 XOR 结果为 1)
1 XOR 1 = 0               (1 与 1 的 XOR 结果为 0)

如果将 0 理解为偶数,将 1 理解为奇数,就可以将 XOR 和一般的加法运算等同起来。

偶数(0)+ 偶数(0)= 偶数(0)
偶数(0)+ 奇数(1)= 奇数(1)
奇数(1)+ 偶数(0)= 奇数(1)
奇数(1)+ 奇数(1)= 偶数(0)

由于 XOR 和加法运算很相似,因此一般用+和○组合而成的符号⊕来表示 XOR

0 ⊕ 0 = 0               (0 与 0 的 XOR 结果为 0)
0 ⊕ 1 = 1               (0 与 1 的 XOR 结果为 1)
1 ⊕ 0 = 1               (1 与 0 的 XOR 结果为 1)
1 ⊕ 1 = 0               (1 与 1 的 XOR 结果为 0)

为了更加直观地理解 XOR,大家可以想象一下黑白棋(奥赛罗棋)中的棋子。

我们将一个棋子保持原状(不翻转)看作 0,将一个棋子翻转到另一面看作 1,那么 XOR 运算就相当于将黑白棋的一个棋子进行翻转的操作。

不翻转(0) ⊕ 不翻转(0) = 不翻转(0)  ——没有翻转
不翻转(0) ⊕ 翻转(1)   = 翻转(1)    ——翻转了一次
翻转(1)   ⊕ 不翻转(0) = 翻转(1)    ——翻转了一次
翻转(1)   ⊕ 翻转(1)   = 不翻转(0)  ——翻转了两次,就等于没有翻转

通过上述场景,大家应该能够理解这样一个规律,即两个相同的数进行 XOR 运算的结果一定为 0,因为棋子翻转两次和一次都没有翻转的结果是一样的。

0 ⊕ 0 = 0
1 ⊕ 1 = 0

比特序列的 XOR

上面我们介绍了 1 个比特之间的 XOR 运算,而如果是长比特序列之间的 XOR 运算,则只要对其中每个相对应的比特进行 XOR 运算就可以了。假设我们将 01001100 这个比特序列称为 A,将 10101010 这个比特序列称为 B,那么 ABXOR 运算就可以像下面这样逐一对各个比特进行计算。和加法运算不同的是,XOR 中不需要进位。

由于两个相同的数进行 XOR 运算的结果一定为 0,因此如果将 AB 的结果再与 B 进行 XOR 运算,则结果会变回 A。也就是说,两个公式中的 B 会相互抵消。

可能大家已经发现了,上面的计算和加密、解密的步骤非常相似。

  • 将明文 A 用密钥 B 进行加密,得到密文 AB
  • 将密文 AB 用密钥 B 进行解密,得到明文 A

实际上,只要选择一个合适的 B,仅仅使用 XOR 就可以实现一个高强度的密码。

对同一个比特序列进行两次 XOR 之后就会回到最初的状态。我们不妨来看一幅由很多个点组成的图像。如果将白色的点作为 0,黑色的点作为 1,那么一幅黑白图像就可以表示为 01 的比特序列。我们准备两幅图像,一幅画的是英文字母 D,另一幅是用 01 交替排列形成的图像(蒙版),这两张图像用 XOR 合并之后的样子如图 3-1 所示。从图中可以看出,执行一次蒙版操作后,原来的图像被隐藏(掩盖)了,而执行两次蒙版操作后,就又可以得到原来的图像了。

图 3-1 XOR 对图像的掩盖

如果所使用的蒙版是完全随机的比特序列,则使用 XOR 就可以将原来的图像掩盖起来。但如果蒙版中的比特序列的排列是可以被推测出来的,那么实质上图像就没有被真正掩盖。对于密码技术来说,“是否可以预测”是非常重要的一点。能够产生不可预测的比特序列,对于密码技术的贡献是巨大的。这种不可预测的比特序列就称为随机数。关于随机数我们将在第 12 章详细探讨。

3.4 一次性密码本——绝对不会被破译的密码

下面我们来介绍一次性密码本,顺便练习一下 XOR 运算。

3.4.1 什么是一次性密码本

只要通过暴力破解法对密钥空间进行遍历,无论什么密文总有一天也都能够被破译。然而,本节中将要介绍的一次性密码本(one-time pad)却是一个例外。即便用暴力破解法遍历整个密钥空间,一次性密码本也绝对无法被破译。

3.4.2 一次性密码本的加密

一次性密码本是一种非常简单的密码,它的原理是“将明文与一串随机的比特序列进行 XOR 运算”。如果将硬币的正面设为 0,反面设为 1,则通过不断掷硬币就能够产生这样一串随机的比特序列。

下面我们将明文 midnight 这个字符串通过 ASCII 进行编码并产生一串比特序列。

m        i        d        n        i        g        h        t
01101101 01101001 01100100 01101110 01101001 01100111 01101000 01110100      midnight

在这里,明文被编码为一串长 64 比特的比特序列。

然后我们再来产生一个和明文长度相同的 64 比特的随机比特序列,这个序列就是 XOR 加密的密钥。下面这个比特序列,就是我刚刚掷了 64 次硬币所产生的。

01101011 11111010 01001000 11011000 01100101 11010101 10101111 00011100      密钥

下面我们将明文与密钥的比特序列进行 XOR 运算,并得到一串新的比特序列,这次运算的结果也就是一次性密码本的密文。

{%}

这样产生的比特序列如果硬要显示在计算机上,那么显示结果看上去就像是乱码一样,因此密文通常不会被还原为字符,而是被作为二进制数据来处理。

3.4.3 一次性密码本的解密

解密就是加密的反向运算。也就是说,用密文和密钥进行 XOR 运算,就可以得到明文。

{%}

将这样计算得到的比特序列在计算机上显示成文本,我们就可以看到 midnight 这个字符串了。

3.4.4 一次性密码本是无法破译的

正如上面所讲到的那样,一次性密码本是一种非常简单的密码。如此简单的密码居然无法破译,这真是让人匪夷所思。这里说的无法破译,并不是指在现实的时间内难以破译,而是指即便拥有一种运算能力无穷大的计算机,可以在一瞬间遍历任意大小的密钥空间,也依然无法破译。

为什么一次性密码本是绝对无法破译的呢?我们假设对一次性密码本的密文尝试进行暴力破解,那么总有一天我们会尝试到和加密时相同的密钥,也就能解密出明文 midnight,这是毋庸置疑的事实。然而——下面这一点非常重要——即便我们能够解密出 midnight 这个字符串,我们也无法判断它是否是正确的明文

这是因为在对一次性密码本尝试解密的过程中,所有的 64 比特的排列组合都会出现,这其中既会包含像 aaaaaaaaabcdefghZZZZZZZZ 这样的规则字符串,也会包含 midnightonenightmistress 等英文单词,还会包含 %Ta_AjvXHY(&JY!z5)ER#f6 等看不懂的组合。由于明文中所有可能的排列组合都会出现,因此我们无法判断其中哪一个才是正确的明文(也就是用哪个密钥才能够正确解密)。

所谓暴力破解,就是按顺序将所有的密钥都尝试一遍,并判断所得到的是不是正确的明文的方法。然而,在一次性密码本中,由于我们无法判断得到的是不是正确的明文,因此一次性密码本是无法破译的。

一次性密码本是由维纳(G.S.Vernam)于 1917 年提出的,并获得了专利,因此又称为维纳密码(Vernam cipher)(该专利已过有效期)。一次性密码本无法破译这一特性是由香农(C. E.Shannon)于 1949 年通过数学方法加以证明的。一次性密码本是无条件安全的(unconditionally secure),在理论上是无法破译的(theoretically unbreakable)。

3.4.5 一次性密码本为什么没有被使用

上面我们只谈了一次性密码本好的方面(对密码破译者来说是不好的方面),然而在现实中,几乎没有人应用一次性密码本,因为它是一种非常不实用的密码,原因如下。

密钥的配送

最大的问题在于密钥的配送。

我们来设想一下使用一次性密码本进行通信的场景。发送者 Alice 使用一次性密码本生成密文并发送出去。发送的密文即便被窃听者 Eve 截获也没关系,因为一次性密码本是绝对无法破译的。

接收者 Bob 收到了 Alice 发来的密文。Bob 要想进行解密,就必须使用和 Alice 进行加密时相同的密钥,因此 Alice 必须将密钥也发送给 Bob,且该密钥的长度和密文是相等的。但这样就产生了一个矛盾——如果能够有一种方法将密钥安全地发送出去,那么岂不是也可以用同样的方法来安全地发送明文了吗?

密钥的保存

在一次性密码本中,密钥的长度必须和明文的长度相等,而且由于密钥保护着明文的机密性,因此必须妥善保存,不能被窃听者窃取。不过,如果能够有办法安全保存与明文一样长的密钥,那不也就有办法安全保存明文本身了吗?也就是说,从一开始我们根本就不需要密码。

通过一次性密码本加密之后,仅凭密文是绝对无法破译出明文的,因此没必要对密文进行保护。然而,为了保护明文,就需要保护和明文一样长的密钥。密钥不能删除或者丢弃,因为没有密钥就无法解密,丢弃密钥就等同于丢弃明文。也就是说,我们只是将“保护明文”这一命题替换成了“保护和明文一样长的密钥”而已,问题并没有得到实质性的解决。

密钥的重用

此外,在一次性密码本中绝对不能重用过去用过的随机比特序列,一次性密码本中的“一次性”也正是由此而来。这是因为作为密钥的比特序列一旦泄露,过去所有的机密通信内容将全部被解密(假设窃听者 Eve 保存了过去所有的通信内容)。

密钥的同步

一次性密码本中还会产生发送者与接收者之间密钥同步的问题。当明文很长时,一次性密码本的密钥也会跟着变长。如果明文是一个大小为 100MB 的文件,则密钥的大小也一定是 100MB。而且在通信过程中,发送者和接收者的密钥的比特序列不允许有任何错位,否则错位的比特后的所有信息都将无法解密。

密钥的生成

在一次性密码本中,需要生成大量的随机数。这里的随机数并不是通过计算机程序生成的伪随机数,而必须是无重现性的真正随机数。

出于上述原因,能够使用一次性密码本的,只有那些机密性重过一切,且可以花费大量财力和人力来生成并配送密钥的场合。例如,据说大国之间的热线就使用了一次性密码本,这种情况下估计会有专门的特工来承担配送密钥的任务,也就是说,特工需要将随机比特序列直接交到对方手中。

综上所述,一次性密码本是一种几乎没有实用性的密码。但是,一次性密码本的思路却孕育出了流密码(stream cipher)。流密码使用的不是真正的随机比特序列,而是伪随机数生成器产生的比特序列。流密码虽然不是无法破译的,但只要使用高性能的伪随机数生成器,就能够构建出强度较高的密码系统。关于流密码我们将在第 4 章详细探讨,关于伪随机数生成器我们将在第 12 章详细探讨。

小测验 2 一次性密码本与压缩      (答案见 3.10 节)

听了一次性密码本的讲解之后,Alice 产生了下面的想法:

虽然一次性密码本的密钥需要与明文等长,但是我手上有数据压缩程序,只要用这个程序对一次性密码本的密钥进行压缩,不就可以把密钥变短了吗?

请问 Alice 的想法正确吗?

3.5 DES

3.5.1 什么是 DES

DES(Data Encryption Standard)是 1977 年美国联邦信息处理标准(FIPS)中所采用的一种对称密码(FIPS 46-3)。DES 一直以来被美国以及其他国家的政府和银行等广泛使用。

然而,随着计算机的进步,现在 DES 已经能够被暴力破解,强度大不如前了。20 世纪末,RSA 公司举办过破译 DES 密钥的比赛(DES Challenge),我们可以看一看 RSA 公司官方公布的比赛结果:1997 年的 DES Challenge I 中用了 96 天破译密钥,1998 年的 DES Challenge II-1 中用了 41 天,1998 年的 DES Challenge II-2 中用了 56 小时,1999 年的 DES Challenge III 中只用了 22 小时 15 分钟。

由于 DES 的密文可以在短时间内被破译,因此除了用它来解密以前的密文以外,现在我们不应该再使用 DES 了。

3.5.2 加密和解密

DES 是一种将 64 比特的明文加密成 64 比特的密文的对称密码算法,它的密钥长度是 56 比特。尽管从规格上来说,DES 的密钥长度是 64 比特,但由于每隔 7 比特会设置一个用于错误检查的比特,因此实质上其密钥长度是 56 比特。

DES 是以 64 比特的明文(比特序列)为一个单位来进行加密的,这个 64 比特的单位称为分组。一般来说,以分组为单位进行处理的密码算法称为分组密码(block cipher),DES 就是分组密码的一种。

DES 每次只能加密 64 比特的数据,如果要加密的明文比较长,就需要对 DES 加密进行迭代(反复),而迭代的具体方式就称为模式(mode)。关于模式我们会在第 4 章详细探讨。

图 3-2 DES 的加密与解密

3.5.3 DES 的结构(Feistel 网络)

DES 的基本结构是由 Horst Feistel 设计的,因此也称为 Feistel 网络(Feistel network)、Feistel 结构(Feistel structure)或者 Feistel 密码(Feistel cipher)。这一结构不仅被用于 DES,在其他很多密码算法中也有应用。

在 Feistel 网络中,加密的各个步骤称为(round),整个加密过程就是进行若干次轮的循环。图 3-3 展现的是 Feistel 网络中一轮的计算流程。DES 是一种 16 轮循环的 Feistel 网络。

图 3-3 Feistel 网络中的一轮

下面我们参照图 3-3 来讲解一下 Feistel 网络的具体结构。

上面的两个方框表示 Feistel 网络中一轮的输入(明文)。输入的数据被等分为左右两半分别进行处理。在图中,左半部分写作“左侧”,右半部分写作“右侧”。

下面的两个方框表示本轮的输出(密文)。输出的左半部分写作“加密后的左侧”,右半部分写作“右侧”。

中间的“子密钥”指的是本轮加密所使用的密钥。在 Feistel 网络中,每一轮都需要使用一个不同的子密钥。由于子密钥只在一轮中使用,它只是一个局部密钥,因此才称为子密钥(subkey)。

轮函数的作用是根据“右侧”和子密钥生成对“左侧”进行加密的比特序列,它是密码系统的核心。将轮函数的输出与“左侧”进行 XOR 运算,其结果就是“加密后的左侧”。也就是说,我们用 XOR 将轮函数的输出与“左侧”进行了合并。而输入的“右侧”则会直接成为输出的“右侧”。

总结一下,一轮的具体计算步骤如下。

(1) 将输入的数据等分为左右两部分。
(2) 将输入的右侧直接发送到输出的右侧。
(3) 将输入的右侧发送到轮函数。
(4) 轮函数根据右侧数据和子密钥,计算出一串看上去是随机的比特序列。
(5) 将上一步得到的比特序列与左侧数据进行 XOR 运算,并将结果作为加密后的左侧。

但是,这样一来“右侧”根本就没有被加密,因此我们需要用不同的子密钥对一轮的处理重复若干次,并在每两轮处理之间将左侧和右侧的数据对调。

图 3-4 展现了一个 3 轮的 Feistel 网络,3 轮加密计算需要进行两次左右对调。对调只在两轮之间进行,最后一轮结束之后不需要对调。

图 3-4 Feistel 网络的加密(3 轮)

Feistel 网络这个名字的由来,也许就是因为其结构图看起来酷似一张网吧。

那么,Feistel 网络应该如何解密呢?例如,我们尝试一下将一轮加密的输出结果用相同的子密钥重新运行一次,这时 Feistel 网络会怎么样呢?结果可能非常令人意外,无论轮函数的具体算法是什么,通过上述操作都能够将密文正确地还原为明文(图 3-5)。关于这一点,大家可以从 XOR 的性质(两个相同的数进行 XOR 的结果一定为 0)进行思考。

图 3-5 用相同的子密钥运行两次 Feistel 网络就能够将数据还原

有多个轮的情况下也是一样的。也就是说,Feistel 网络的解密操作只要按照相反的顺序来使用子密钥就可以完成了,而 Feistel 网络本身的结构,在加密和解密时都是完全相同的(图 3-6)。

图 3-6 Feistel 网络的解密(3 轮)

下面我们来总结一下 Feistel 网络的性质。

最容易发现的一点就是,Feistel 网络的轮数可以任意增加。无论运行多少轮的加密计算,都不会发生无法解密的情况。

其次,我们还可以发现,加密时无论使用任何函数作为轮函数都可以正确解密。也就是说,即便用轮函数的输出结果无法逆向计算出输入的值(即该函数不存在反函数)也没有问题。轮函数可以无需考虑解密的问题,可以被设计得任意复杂。

Feistel 网络实际上就是从加密算法中抽取出“密码的本质部分”并将其封装成一个轮函数。只要使用 Feistel 网络,就能够保证一定可以解密。因此,设计密码算法的人只要努力设计出足够复杂的就可以了。

另外,加密和解密可以用完全相同的结构来实现,这也是 Feistel 网络的一个特点。在 Feistel 网络的一轮中,右半部分实际上没有进行任何处理,这在加密算法中看起来是一种浪费,但却保证了可解密性,因为完全没有进行任何处理的右半部分,是解密过程中所必需的信息。由于加密和解密可以用完全相同的结构来实现,因此用于实现 DES 算法的硬件设备的设计也变得容易了。

综上所述,无论是任何轮数、任何轮函数,Feistel 网络都可以用相同的结构实现加密和解密,且加密的结果必定能够正确解密。

正是由于 Feistel 网络具备如此方便的特性,它才能够被许多分组密码算法使用。在后面即将介绍的 AES 最终候选算法的 5 个算法之中,有 3 个算法(MARS、RC6、Twofish)都是使用了 Feistel 网络。然而,AES 最终选择的 Rijndael 算法却没有使用 Feistel 网络。Rijndael 所使用的结构称为 SPN 结构,我们将在 3.8.2 节详细介绍。

3.5.4 差分分析与线性分析

差分分析是一种针对分组密码的分析方法,这种方法由 Biham 和 Shamir 提出,其思路是“改变一部分明文并分析密文如何随之改变”。理论上说,即便明文只改变一个比特,密文的比特排列也应该发生彻底的改变。于是通过分析密文改变中所产生的偏差,可以获得破译密码的线索。

此外,还有一种叫作线性分析的密码分析方法,这种方法由松井充提出,其思路是“将明文和密文的一些对应比特进行 XOR 并计算其结果为零的概率”1。如果密文具备足够的随机性,则任选一些明文和密文的对应比特进行 XOR 结果为零的概率应该为 1\over2 。如果能够找到大幅偏离 1\over2 的部分,则可以借此获得一些与密钥有关的信息。使用线性分析法,对于 DES 只需要 247 组明文和密文就能够完成破解,相比需要尝试 256 个密钥的暴力破解来说,所需的计算量得到了大幅减少。

1Mitsuru Matsui, Linear Cryptanalysis Method for DES Cipher, EUROCRYPT '93 Lecture Notes in Computer Science Volume 765, 1994, pp 386-397.

差分分析和线性分析都有一个前提,那就是假设密码破译者可以选择任意明文并得到其加密的结果,这种攻击方式称为选择明文攻击(Chosen Plaintext Attack,CPA)。

以 AES 为代表的现代分组密码算法,在设计上已经考虑了针对差分分析和线性分析的安全性。

3.6 三重DES

现在 DES 已经可以在现实的时间内被暴力破解,因此我们需要一种用来替代 DES 的分组密码,三重 DES 就是出于这个目的被开发出来的。

3.6.1 什么是三重 DES

三重 DES(triple-DES)是为了增加 DES 的强度,将 DES 重复 3 次所得到的一种密码算法,也称为 TDEA(Triple Data Encryption Algorithm),通常缩写为 3DES

3.6.2 三重 DES 的加密

三重 DES 的加密机制如图 3-7 所示。

图 3-7 三重 DES 的加密

明文经过三次 DES 处理才能变成最后的密文,由于 DES 密钥的长度实质上是 56 比特,因此三重 DES 的密钥长度就是 56×3=168 比特。

从图 3-7 中我们可以发现,三重 DES 并不是进行三次 DES 加密(加密→加密→加密),而是加密→解密→加密的过程。在加密算法中加入解密操作让人感觉很不可思议,实际上这个方法是 IBM 公司设计出来的,目的是为了让三重 DES 能够兼容普通的 DES。

当三重 DES 中所有的密钥都相同时,三重 DES 也就等同于普通的 DES 了。这是因为在前两步加密→解密之后,得到的就是最初的明文。因此,以前用 DES 加密的密文,就可以通过这种方式用三重 DES 来进行解密。也就是说,三重 DES 对 DES 具备向下兼容性(图 3-8)。

图 3-8 三重 DES 也可以作为 DES 来使用

在 DES 的部分我们已经提到过,DES 的加密和解密过程只是改变了子密钥的顺序,而实际进行的处理是相同的。

如果所有密钥都使用相同的比特序列,则其结果与普通的 DES 是等价的。

如果密钥 1 和密钥 3 使用相同的密钥,而密钥 2 使用不同的密钥(也就是只使用两个 DES 密钥),这种三重 DES 就称为 DES-EDE2(图 3-9)。EDE 表示的是加密(Encryption)→解密(Decryption)→加密(Encryption)这个流程。

图 3-9 DES-EDE2

密钥 1、密钥 2、密钥 3 全部使用不同的比特序列的三重 DES 称为 DES-EDE3

3.6.3 三重 DES 的解密

三重 DES 的解密过程和加密正好相反,是以密钥 3、密钥 2、密钥 1 的顺序执行解密→加密→解密的操作。

图 3-10 三重 DES(DES-EDE3)的解密

3.6.4 三重 DES 的现状

尽管三重 DES 目前还被银行等机构使用,但其处理速度不高,除了特别重视向下兼容性的情况以外,很少被用于新的用途。

在日本总务省和经济产业省 2013 年发布的《电子政府相关技术采购中参考的密码清单》2 中,“电子政府推荐使用的密码清单”一项中将 3-key Triple DES 作为 64 比特分组密码列了出来。但考虑到 NIST SP 800-67 的规定,以及其事实性标准的地位,又在脚注中给出了“目前暂且允许使用”的描述。

2即《CRYPTREC 密码清单》[CRYPTREC] :http://www.cryptrec.go.jp/list.html

3.7 AES 的选定过程

本节我们将讲解对称密码的新标准——AES。

本节的内容参考了 Rijndael 开发者的著作《高级加密标准(AES)算法:Rijndael 的设计》(The Design of Rijndael3,以及 NIST 发布的《关于开发高级加密标准(AES)的报告》(Report on Development of the Advanced Encryption Standard)。

3Jone Daemen、Vincent Rijmen 著。中文版由清华大学出版社 2003 年 3 月出版,谷大武译。——译者注

3.7.1 什么是 AES

AES(Advanced Encryption Standard)是取代其前任标准(DES)而成为新标准的一种对称密码算法。全世界的企业和密码学家提交了多个对称密码算法作为 AES 的候选,最终在 2000 年从这些候选算法中选出了一种名为 Rijndael 的对称密码算法,并将其确定为了 AES。

3.7.2 AES 的选拔过程

组织 AES 公开竞选活动的,是美国的一个标准化机构——NIST(National Institute of Standards and Technology,国家标准技术研究所),该机构所选拔的密码算法,将成为美国的国家标准,即联邦信息处理标准(FIPS)(FIPS-197)。虽然 AES 是美国的标准,但和 DES 一样,它必将成为一个世界性的标准。

参加 AES 竞选是有条件的,这个条件就是:被选为 AES 的密码算法必须无条件地免费供全世界使用。

此外,参加者还必须提交密码算法的详细规格书、以 ANSI C 和 Java 编写的实现代码以及抗密码破译强度的评估等材料。因此,参加者所提交的密码算法,必须在详细设计和程序代码完全公开的情况下,依然保证较高的强度,这就彻底杜绝了隐蔽式安全性(security by obscurity)。

AES 的选拔过程是对全世界公开的。实际上,对密码算法的评审不是由 NIST 来完成的,而是由全世界的企业和密码学家共同完成的,这其中也包括 AES 竞选的参加者。换句话说,参加竞选的密码算法是由包括参加者在内的整个密码学社区共同进行评审的。一旦被找到弱点就意味着该密码算法落选,因此参加者会努力从各个角度寻找其他密码算法的弱点,并向其他参与评审的人进行证明。

像这样通过竞争来实现标准化(standardization by competition)的方式,正是密码算法选拔的正确方式。由世界最高水平的密码学家共同尝试破译,依然未能找到弱点,只有这样的事实才能够证明一种密码算法的强度。

3.7.3 AES 最终候选算法的确定与 AES 的最终确定

1997 年,NIST 开始公开募集 AES。1998 年,满足 NIST 募集条件,即能够进入评审对象范围的密码算法共有 15 个(CAST-256、Crypton、DEAL、DFC、E2、Frog、HPC、LOK197、Magenta、MARS、RC6、Rijndael、SAFER+、Serpent、Twofish),其中 E2 密码算法是由日本提交的。

AES 的选拔并不仅仅考虑一种算法是否存在弱点,算法的速度、实现的容易性等也都在考虑范围内。不仅加密本身的速度要快,密钥准备的速度也很重要。此外,这种算法还必须能够在各种平台上有效工作,包括智能卡、8 位 CPU 等低性能平台以及工作站等高性能平台。

1999 年,在募集到的 15 个算法中,有 5 个算法入围了 AES 最终候选算法名单(AES finalist)。AES 最终候选算法名单如表 3-1 所示。

2000 年 10 月 2 日,Rijndael 力压群雄,被 NIST 选定为 AES 标准。也就是说,比利时密码学家 Joan Daemen 与 Vincent Rijmen 所开发的密码算法,成为了美国的国家标准。正是有了 NIST 当初所设置的参选条件,我们现在才得以自由、免费地使用 AES(Rijndael)。

表 3-1 AES 最终候选算法名单(按英文字母排序)

名称

提交者

MARS

IBM 公司

RC6

RSA 公司

Rijndael

Daemen, Rijmen

Serpent

Anderson, Biham, Knudsen

Twofish

Counterpane 公司

3.8 Rijndael

3.8.1 什么是Rijndael

Rijndael 是由比利时密码学家 Joan Daemen 和 Vincent Rijmen 设计的分组密码算法,于 2000 年被选为新一代的标准密码算法——AES。今后会有越来越多的密码软件支持这种算法。

Rijndael 的分组长度和密钥长度可以分别以 32 比特为单位在 128 比特到 256 比特的范围内进行选择。不过在 AES 的规格中,分组长度固定为 128 比特,密钥长度只有 128、192 和 256 比特三种。

3.8.2 Rijndael 的加密和解密

和 DES 一样,Rijndael 算法也是由多个构成的,其中每一轮分为 SubBytes、ShiftRows、MixColumns 和 AddRoundKey 共 4 个步骤。DES 使用 Feistel 网络作为其基本结构,而 Rijndael 没有使用 Feistel 网络,而是使用了 SPN 结构

Rijndael 的输入分组为 128 比特,也就是 16 字节。首先,需要逐个字节地对 16 字节的输入数据进行 SubBytes 处理。所谓 SubBytes,就是以每个字节的值(0 ~ 255 的任意值)为索引,从一张拥有 256 个值的替换表(S-Box)中查找出对应值的处理。也就是说,要将一个 1 字节的值替换成另一个 1 字节的值。这个步骤用语言来描述比较麻烦,大家可以将它想象成是第 2 章中介绍过的简单替换密码的 256 个字母的版本。图 3-11 所示为 4×4=16 字节的数据中通过 S-Box 替换 1 字节的情形 4

4图 3-11~图 3-17 是根据 The Design of Rijndael [RINJDAEL] 中的图制作而成的。

图 3-11 SubBytes(逐字节替换)

SubBytes 之后需要进行 ShiftRows 处理。这一步是将以 4 字节为单位的行(row)按照一定的规则向左平移,且每一行平移的字节数是不同的。图 3-12 所示为 ShiftRows 中对其中一行进行处理的情形。

图 3-12 ShiftRows(平移行)

ShiftRows 之后需要进行 MixColumns 处理。这一步是对一个 4 字节的值进行比特运算,将其变为另外一个 4 字节值。图 3-13 所示为 MixColumns 中对其中一列(column)进行处理的情形。

图 3-13 MixColumns(混合列)

最后,需要将 MixColumns 的输出与轮密钥进行 XOR,即进行 AddRoundKey 处理。图 3-14 所示为 AddRoundKey 中对其中 1 个字节进行处理的情形。到这里,Rijndael 的一轮就结束了。实际上,在 Rijndael 中需要重复进行 10 ~ 14 轮计算。

图 3-14 AddRoundKey(与轮密钥进行 XOR)

通过上面的结构我们可以发现输入的所有比特在一轮中都会被加密。和每一轮都只加密一半输入的比特的 Feistel 网络相比,这种方式的优势在于加密所需要的轮数更少。此外,这种方式还有一个优势,即 SubBytes、ShiftRows 和 MixColumns 可以分别以字节、行和列为单位进行并行计算。

在 Rijndael 的加密过程中,每一轮所进行的处理为:

SubBytes → ShiftRows → MixColumns → AddRoundKey

而在解密时,则是按照相反的顺序来进行的,即:

AddRoundKey → InvMixColumns → InvShiftRows → InvSubBytes

其中,AddRoundKey 是与轮密钥进行 XOR 运算,因此这一步在加密和解密时是完全相同的,剩下的步骤中名字前面都带有 Inv,这表示与原始步骤相对应的逆运算。图 3-15~图 3-17 所示为解密处理的情形。

图 3-15 InvMixColumns(混合列)

图 3-16 InvShiftRows(平移行)

图 3-17 InvSubBytes(逐字节替换)

3.8.3 Rijndael 的破译

对于 Rijndael 来说,可能会出现以前并不存在的新的攻击方式。尽管本书中没有涉及,但 Rijndael 的算法背后有着严谨的数学结构,也就是说从明文到密文的计算过程可以全部用公式来表达,这是以前任何密码算法都不具备的性质。如果 Rijndael 的公式能够通过数学运算来求解,那也就意味着 Rijndael 能够通过数学方法进行破译,而这也就为新的攻击方式的产生提供了可能。

不过,这也只是一种假设而已,实际上到现在为止还没有出现针对 Rijndael 的有效攻击。

3.8.4 应该使用哪种对称密码呢

前面我们介绍了 DES、三重 DES 和 AES 等对称密码,那么我们到底应该使用哪一种对称密码算法呢?

首先,DES 不应再用于任何新的用途,因为随着计算机技术的进步,现在用暴力破解法已经能够在现实的时间内完成对 DES 的破译。但是,在某些情况下也需要保持与旧版本软件的兼容性。

其次,我们也没有理由将三重 DES 用于任何新的用途,尽管在一些重视兼容性的环境中还会继续使用,但它会逐渐被 AES 所取代。

现在大家应该使用的算法是 AES(Rijndael),因为它安全、快速,而且能够在各种平台上工作。此外,由于全世界的密码学家都在对 AES 进行不断的验证,因此即便万一发现它有什么缺陷,也会立刻告知全世界并修复这些缺陷。

AES 最终候选算法应该可以作为 AES 的备份。和 Rijndael 一样,这些密码算法也都经过了严格的测试,且没有发现任何弱点。但 NIST 最终选择的标准只有 Rijndael,并没有官方认可将其他最终候选算法作为备份来使用。

在日本,密码技术研究与评估委员会(Cryptography Research and Evaluation Committees,CRYPTREC)负责对各种密码技术进行评估。2013 年发布的《CRYPTREC 密码清单》中,将 3-key Triple DES(64 比特分组密码算法)以及 AES、Camellia(128 比特分组密码算法)列入了“电子政府推荐使用的密码清单”。

一般来说,我们不应该使用任何自制的密码算法,而是应该使用 AES。因为 AES 在其选定过程中,经过了全世界密码学家所进行的高品质的验证工作,而对于自制的密码算法则很难进行这样的验证。

小测验 3 对称密码的密钥需要多长?      (答案见 3.10 节)

假设你能够使用的计算能力如下。

  • 每台计算机每秒可尝试 1020 个密钥;
  • 一共有 10100 台计算机;
  • 所有的计算机可运转 1020 年。

在拥有如此强大计算能力的前提下,如果依然要保证无法通过暴力破解遍历整个密钥空间,那么密钥的长度到底需要达到多少比特呢?请从下列选项中选出正确的答案。

(A) 只要 512 比特就够了。

(B) 至少需要 1024 比特。

(C) 至少需要 4096 比特。

(D) 至少需要 1 万比特。

(E) 100 万比特也不够。

备注:这里我们估算的计算能力是远远超过实际情况的。相比之下,超级计算机“京”每秒可执行 1016 次浮点运算,宇宙中所有粒子的总数为 1087 个左右,宇宙的年龄为 1011 年左右。

3.9 本章小结

本章中我们介绍了对称密码,以及 DES、三重 DES、AES 和其他一些密码算法。

使用一种密钥空间巨大,且在算法上没有弱点的对称密码,就可以通过密文来确保明文的机密性。巨大的密钥空间能够抵御暴力破解,算法上没有弱点可以抵御其他类型的攻击。

然而,用对称密码进行通信时,还会出现密钥的配送问题,即如何将密钥安全地发送给接收者。为了解决密钥配送问题,我们需要公钥密码技术。关于密钥配送问题和公钥密码,我们将在第 5 章进行讲解。此外,尽管使用对称密码可以确保机密性,但仅凭这一点还并不能完全放心。例如,当接收到的密文无法正确解密时,如果仅仅向发送者返回一个“出错了”的消息,在某些情况下是非常危险的。因为发送者有可能发送伪造的密文,并利用解密时返回的错误来盗取信息。关于这一点,我们将在 8.5 节中详细讲解。

本章所介绍的几乎所有的密码算法,都只能将一个固定长度的分组进行加密。当需要加密的明文长度超过分组长度时,就需要对密码算法进行迭代。下一章我们将探讨对分组密码进行迭代的方法。

小测验 4 对称密码的基础知识      (答案见 3.10 节)

下列说法中,请在正确的旁边画 ○,错误的旁边画 ×。

(1) 对称密码中,加密的密钥和解密的密钥是相等的。

(2) 将来,当计算机的计算能力足够高时,就可以在现实的时间内破译一次性密码本的密文。

(3) 如果密钥长度为 56 比特,那么用暴力破解找到正确密钥需要平均尝试约 228 次。

(4) 虽然 AES 是一种强度很高的对称密码算法,但在商用情况下需要向 NIST 支付授权费用。

(5) 现在 DES 可以在现实的时间内被破译。

(6) AES 标准所选定的密码算法叫作 Rijndael。

3.10 小测验的答案

小测验 1 的答案:字母→数字的映射和恺撒密码       (3.3.1 节)

密钥为 3 的恺撒密码相当于“加 3 后除以 26 求余数”的运算。之所以要求余数,是因为当遇到 23、24、25 所对应的字母时能够重新返回字母表的开头。

我们将明文中一个字母所对应的数字设为 plain,将加密后的字母所对应的数字设为 cipher,则已知 plain 求 cipher 的公式为:

cipher =(plain + 3)mod 26

其中,mod 是表示求余数的运算符。

小测验 2 的答案:一次性密码本与压缩      (3.4.5 节)

不正确。因为一次性密码本的密钥无论使用任何压缩软件都无法进行压缩。

压缩软件的压缩原理,是找出输入数据中出现的冗余的重复序列,并将它们替换成较短的数据。然而一次性密码本所使用的密钥是随机的,其中不包含任何冗余的重复序列。反过来说,如果一个比特序列能够被压缩,就说明它不是一个随机的比特序列。

小测验 3 的答案:对称密码的密钥需要多长?      (3.8.4 节)

正确答案是“(A) 只要 512 比特就够了。”

首先,我们来计算一年有多少秒。我们多算一点,设一年有 366 天,则:

366×24×60×60 = 31622400

然后,根据已知条件可以计算出能够尝试的密钥总数。

\begin{aligned}10^{20}\times10^{100}\times10^{20}\times31622400&=10^{140}\times31622400\\&=3.16224\times10^{147}\end{aligned}

然后我们再计算一下长度为 512 比特的密钥总数。

2^{512}\fallingdotseq1.340780\times10^{154}

可以看出,512 比特的密钥总数就已经超过了我们根据已知条件所求出的能够尝试的密钥数量了,因此选项 (A) 是正确答案。

当对称密码的密钥长度达到 512 比特时,再继续增加密钥长度对于提高机密性来说已经没有什么实际作用了,反而只会让算法的速度变慢。

小测验 4 的答案:对称密码的基础知识      (3.9 节)

○ (1) 对称密码中,加密的密钥和解密的密钥是相等的。

× (2) 将来,当计算机的计算能力足够高时,就可以在现实的时间内破译一次性密码本的密文。

  计算机的能力再高,也无法破译一次性密码本生成的密文。

× (3) 如果密钥长度为 56 比特,那么用暴力破解找到正确密钥需要平均尝试约 228 次。

  平均尝试次数是密钥总数的大约一半。当密钥长度为 56 比特时,密钥总数为 256 个,它的一半是 255(注意,不是指数 56 变成一半得 28,而是减 1 得 55)。

  因此,当密钥长度为 56 比特时,平均尝试次数为 255 次,大约相当于 3.6×1016 次。

× (4) 虽然 AES 是一种强度很高的对称密码算法,但在商用情况下需要向 NIST 支付授权费用。

  AES 算法无需支付任何授权费,可以自由免费使用。

○ (5) 现在 DES 可以在现实的时间内被破译。

○ (6) AES 标准所选定的密码算法叫作 Rijndael。

目录

  • 译者序
  • 前言
  • 第 1 部分 密码
  • 第 1 章 环游密码世界
  • 第 2 章 历史上的密码——写一篇别人看不懂的文章
  • 第 3 章 对称密码(共享密钥密码)——用相同的密钥进行加密和解密
  • 第 4 章 分组密码的模式——分组密码是如何迭代的
  • 第 5 章 公钥密码——用公钥加密,用私钥解密
  • 第 6 章 混合密码系统——用对称密码提高速度,用公钥密码保护会话密钥
  • 第 2 部分 认证
  • 第 7 章 单向散列函数——获取消息的“指纹”
  • 第 8 章 消息认证码——消息被正确传送了吗
  • 第 9 章 数字签名——消息到底是谁写的
  • 第 10 章 证书——为公钥加上数字签名
  • 第 3 部分 密钥、随机数与应用技术
  • 第 11 章 密钥——秘密的精华
  • 第 12 章 随机数——不可预测性的源泉
  • 第 13 章 PGP ——密码技术的完美组合
  • 第 14 章 SSL/TLS ——为了更安全的通信
  • 第 15 章 密码技术与现实社会——我们生活在不完美的安全中
  • 附录 椭圆曲线密码——密码技术综合测验
  • 附录 A 椭圆曲线密码
  • 附录 B 密码技术综合测验
  • 参考文献