三、对称密码

1 炒鸡蛋与对称密码

鸡蛋炒好之后就完全分不清原来的蛋黄和蛋白了,使用对称密码进行加密,和炒鸡蛋有着异曲同工之妙。炒鸡蛋搅拌的是鸡蛋,而密文打乱的则是比特序列。
然后,它们最大的不同是,炒鸡蛋无法还原成原来的鸡蛋,但密文却必须能够让接收者正确解密才行。
因此,如果只是随意地搅拌和混合,则不能称之为加密,而必须仔细设计出一种能够还原的混合方式。

2 本章概要

学习比特序列运算和 XOR 运算。以及介绍一种称为一次性密码本的密码系统。
具体介绍几种对称密码算法,包括 DES、三重DES、AES以及其它一些密码算法。
需要注意的是,密码算法有时候会设计开发者的专利和授权等问题,记得先调查一下该算法的专利和授权信息。

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

3.1 编码

计算机操作对象并不是文字,而是由 0 和 1 排列而成的比特序列。执行加密操作的程序,就是将表示明文的比特序列转换为表示密文的比特序列。

3.2 XOR

XOR 的全称是 exclusive or ,中文叫作异或

1. 一个比特的 XOR

0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0
可以理解为硬币翻转:
不翻转 + 不翻转 = 不翻转
不翻转 + 翻转 = 翻转
翻转 + 不翻转 = 翻转
翻转 + 翻转 = 不翻转

2. 比特序列的 XOR

A XOR B = AB
AB XOR B = A
这是因为两个相同的数进行 XOR 运算的结果一定为 0 ,因此 A XOR B XOR B = A。这不就和加密、界面的步骤非常相似么,如下:

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

实际上,只要选择一个合适的 B,仅仅使用 XOR 就可以实现一个高强度的密码。
对同一个比特序列进行两次 XOR 之后就会回到最初的状态。我们不妨来看看一副由很多点组成的图像。如果将白色的点作为 0 ,黑色的点作为 1 ,
那么一副黑白图像就可以表示为 0 和 1 的比特序列。我们转呗两幅图像,一幅画是英文字母 D,另一幅是用 0 和 1 交替排列形成的图像(蒙版),
并进行如下操作:

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

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

4.1 什么是一次性密码本

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

4.2 一次性密码本的加密

它的原理是“将明文与一串随机的比特序列进行 XOR 运算”。如果将硬币的正面设为 0 ,反面设为 1 ,则通过不断掷硬币就能够产生这样一串随机的比特序列。
下面我们将明文 midnight 这个字符串通过 ASCII 进行编码并产生一串比特序列。

接着,我们掷 64 次硬币产生 64 比特的随机比特序列:

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

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

4.3 一次性密码本的解密

用密文和密钥进行 XOR 运算,就可以得到明文:

这样显示在计算上就会是正常的文本: midnight。

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

为什么一次性密码本是绝对无法破译的呢?我们假设对一次性密码本的密文尝试进行暴力破解,那么总有一天我们会尝试到和加密时相同的密钥,但是,
即便我们能够解密出 midnight 这个字符串,我们也无法判断它是否是正确的明文

因为在解密过程中,所有的 64 比特的排列组合都会出现,包括像 aaaaaaaa、bbbbbbbb、ZZZZZZZZ 这样的规则字符串,也会包含 midnight、onenight、
mistress 等英文单词,还会包含乱码看不懂的组合。由于明文中又有的可能排列组合都会出现,因此我们无法判断其中哪一个才是正确的明文(也就是用哪个
密钥才能够正确解密)。

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

一次性密码本无法破译的这一特性是由香农于 1949 年通过数学方法加以证明的。一次性密码本是无条件安全(unconditionally secure)的,
在理论上是无法破译的(theoretically unbreakable)

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

1. 秘钥的配送

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

2. 秘钥的保存

既然能保存和明文一样长度的秘钥,那么不也就有办法安全保存明文本身了吗?也就是说,从一开始我们根本就不需要密码。也就是说,我们只是将“保护明文”
这一命题替换成了“保护和明文一样的秘钥”而已,问题并没有得到实质性的解决。

3. 秘钥的重用

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

4. 秘钥的同步

如果明文是一个大小为 100MB 的文件,则秘钥的大小也一定是 100MB 。而且在通信过程中,发送者和接受者的秘钥的比特序列不允许有任何错位,否则错位
后的比特的所有信息都将无法解密。

5. 秘钥的生成

在一次性密码本中,需要生成大量的随机数。这里的随机数必须是无重现性的真正随机数。因此,能够使用一次性密码本的,只有那些机密性重过一切,且可以
话费大量财力和人力来生成并配送秘钥的场合。

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

5 DES

5.1 什么是 DES

DES(Data Encryption Standard)是 1977 年美国联邦信息处理标准(FIPS)中所采用的一种对称密码。由于其在 1999 年只用了 22 小时就可破译,
因此除了用它来解密以前的密文以外,现在我们不应该再使用 DES 了。

5.2 加密和解密

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

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

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

5.3 DES 的结构(Feistel网络)

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

1. Feistel 网络的加密

输入的数据被分为左右两半分别进行处理,中间的“子密钥”指的是本轮加密所使用的密钥。在 Feistel 网络中,每一轮都需要使用一个不同的子密钥。
由于子密钥只在一轮中使用,它只是一个局部密钥,因此才成为子密钥
轮函数的作用是根据“右侧”和子密钥一起生成中间密钥,这个中间密钥对“左侧”进行加密,轮函数是该密码系统的核心。一轮的步骤总结如下:

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

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

2. Feistel 网路的解密

我们尝试一次下将一轮加密的输出结果用相同的子密钥重新运行一次,结果可能非常令人意外,无论轮函数的具体算法是什么,通过上述操作都能够将密文
正确地还原为明文。关于这一点,可以从 XOR 的性质(两个相同的数进行 XOR 的结果一定为 0 )进行思考。

有多个轮的情况下也是一样的。也就是说, Feistel 网络的解密操作只要按照相反的熟悉怒来使用子密钥就可以完成了。下图是三轮加密图:

下图是解密示意图:

3. Feistel 网络的性质

Feistel 网络的轮数可以任意增加。无论运行多少轮的加密计算,都不会发生无法解密的情况。以及加密时无论使用任何函数作为轮函数都可以正确解密。
最后是加密和解密可以用完全相同的结构来实现。在 Feistel 网络的一轮中,右半部分实际上没有任何处理,这在加密算法中看起来是一种浪费,
但却保证了可解密性。

6 三重 DES

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

6.1 什么是三重 DES

三重 DES(triple-DES)是为了增加 DES 的强度,将 DES 重复 3 次所得到的一种密码算法。

6.2 三重 DES 的加密


经过三次 DES 处理CIA能变成最后的密文,由于 DES 秘钥的长度实质上是 56 比特,因此三重 DES 的秘钥长度就是 56 * 3 = 168 比特。
从上图中,我们发现,三重 DES 并不是进行三次 DES 加密,而是加密-解密-加密的过程,实际上这是 IBM 公司设计出来的,目的是为了让三重 DES
能够兼容普通的 DES。当三重 DES 所有秘钥都相同的时候就相当于普通的 DES 了。因此,以前用 DES 加密的密文,就可以通过这种方式用三重 DES
来进行解密。也就是说三重 DES 对 DES 具备向下兼容性。

6.3 三重 DES 的解密

解密过程与加密过程顺序相反。

6.4 三重 DES 的现状

其处理速度不高,而且在安全性方面也逐渐显现了一些问题,但还被银行等机构使用。

7 AES 的选定过程

7.1 什么是 AES

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

7.2 AES 的选定过程

组织 AES 公开竞选活动的,是美国的一个标准化机构——NIST,参加 AES 竞选的条件是:被选为 AES 的密码算法必须无条件地免费供全世界使用。
此外,参与者还必须提交密码算法的详细规格书、以 ANSIC 和 Java 编写的实现代码以及抗密码破译强度的评估等材料。因此,在提交了详细设计和程序代码
完全公开的情况下,就杜绝了隐蔽式安全性(security by obscurity)。

评审者也是参与者,通过发现别人的弱点,实现竞争,最终实现标准化,正是密码算法选定的正确方式。只有由世界最高水平的密码学家共同尝试破译,依然未能
找到弱点,这样才能够证明一种密码算法的强度。

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

8 Rijndael

8.1 什么是 Rijndael

由比利时密码学家 Joan Daemon 和 Vincent Rijmen 设计的分组密码算法。

8.2 Rijndael 的加密和解密

和 DES 一样, Rijndael 算法也是由多个轮所构成,但是 Rijndael 使用了 SPN 结构,Rijndael 的输入分组为 128 比特,也就是 16字节。
首先,需要逐个字节地对 16 字节地输入数据进行 SubBytes 处理,即将一个 1 字节地值替换成另一个 1 字节地值,可以想象成简单替换密码。
SubBytes 之后进行 ShiftRows处理,即将 SubBytes 的输出以字节单位进行打乱处理,这种打乱是有规律的。然后进行 MixColumns 处理,即对
一个 4 字节地值进行比特运算,将其变成另一个 4 字节值,最后与轮秘钥进行 XOR ,进行 AddRoundkey处理。这就是一轮。
实际上,在 Rijndael 需要重复进行 10 ~ 14 次计算。
![][14]
它在一轮使用了 SubBytes、ShiftRows、MixColumns 分别存在反向运算 InvSubBytes、InvShiftRows、InvMixColumns,分别按字节、行、列进行并行计算。

8.3 Rijndael 的破译

对 Rijndael 来说,可能会出现以前并不存在的新的攻击方法。它的算法背后有着严谨的数学结构,也就是说从明文到密文的计算过程可以全部用公司来表达。

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

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

介绍了 DES、三重 DES、和 AES 等对称密码。那么我们到底用哪种呢?
一般来说不应该使用任何任何自制的密码算法,而是应该使用 AES。

9 本章小结

本章介绍了对称密码,以及 DES、三重 DES、AES密码算法。

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

然后用对称密码进行通信时,还会出现秘钥的配送问题。为了解决秘钥配送问题,我们需要公钥密码技术,将在第五章详解。
本章所介绍的几乎所有的密码算法,都只能讲一个固定长度的分组进行加密。当需要加密的明文长度超过分组长度时,就需要对密码算法进行迭代。下一章将
探讨对分组密码进行迭代的方法。

10 小测验

  1. 一次性密码本的秘钥可以进行压缩变短。
  2. 对称密码中,加密的秘钥和解密的秘钥是相等的。
  3. 如果秘钥长度为 56 比特,那么用暴力破解找到正确秘钥需要平均尝试约 2^28 次。
  4. 三重 DES 的秘钥空间是 DES 秘钥空间的三倍大。
  5. 现在 DES 可以在限时的时间内被破译。
  6. AES 标准选定的密码算法叫 Rijndael。

注:秘钥长度为 56 比特,则秘钥空间(秘钥总数)是 2^56,平均时间除以 2 ,为 2^55。
压缩算法在于:重复。