【计算机网络】第七部分 网络安全(30) 密码学

通过使用密码学 cryptography（基于抽象代数的一门科学），网络安全的大部分能够得到实现。这里简单讨论了密码学，尽可能地减少有关抽象代数的讨论。目标是给出密码学足够多的资料，使得网络安全更加易懂。本文是第31 章和第32章的基础知识。

---

30.1 引言

先介绍一些与密码学相关的问题。首先，需要定义一些术语，然后给出一些分类。

30.1.1 定义

这里定义本章使用的一些术语。

• 密码学 Cryptography ：这个词在希腊语中的意思是"秘密的文字"。然而，现在这个词指的是转换报文、以使其安全且不受攻击的科学和艺术 art of transforming messages to make them secure and immune to attacks 。图30.1显示的是密码学的组成。
  
• 明文与密文：在进行转换之前，变换前的原始的报文称为明文 plaintext 。经过转换后的报文称为密文 ciphertext 。加密算法 encryption algorithm 将明文转换为密文，解密算法 decryption algorithm 将密文转换回明文。发送方使用加密算法，而接收方使用解密算法。
• 密码算法 ciphers ：我们把加密与解密算法合称为密码算法。术语密码算法有时也用来指密码学中不同类型的算法。这并不是说发送方和接收方在安全通信时都需要拥有自己唯一的加密算法，相反，一个密码算法可以为数百万对通信者服务。
• 密钥 key ：是密码算法中参与运算的数值（或数值集）。对报文进行加密，我们需要一个加密算法、一个加密密钥 encryption key 以及明文，并由此产生密文。对报文进行解密，我们需要一个解密算法、一个解密密钥 decryption key 以及密文，并由此复原原始的明文。
• Alice, Bob and Eve ：密码学中，在信息交换的情节里面，通常引入三个人。我们采用 Alice, Bob, Eve 。Alice是需要发送安全数据的人，Bob是数据接收方，Eve是个搅乱Alice和Bob通信的人，她截获报文或者发送她自己伪造的报文。这三个名字代表的是实际发送、或接收数据、或拦截或更改数据的计算机或者进程。

30.1.2 两类算法

我们可以将所有的加密算法（密码算法）分为两类：对称密钥（也称为秘密密钥）加密算法和非对称（公钥）加密算法。图30.2给出分类。

1. 对称密钥密码学

在对称密钥密码学 symmetric-key cryptography 中，发送方（加密）和接收方（解密）使用相同的密钥，即密钥是共享的。发送方使用此密钥和加密算法，对明文数据进行加密，接收方使用相同的密钥和相应的解密算法，对密文进行解密（如图30.3所示）。

2. 非对称密钥密码学

在非对称 asymmetric-key cryptography 或公钥加密中有两个密钥：私钥和公钥。私钥 private key 由接收方保存，而公钥 public key 是公开发布的。如图30.4所示，假设Alice想给Bob发送报文，Alice使用公钥对报文加密。Bob接收到报文后，再用私钥进行解密。

在公钥加密/解密中，用于加密的公钥与用于解密的私钥是不同的。公钥对于公众是可得到的，而私钥只有个人才能使用。

3. 三种类型的密钥

应该已经注意到，在密码学中，我们要处理三种类型的密钥：秘密密钥、公钥及私钥 the secret key, the public key, and the private key 。第一种秘密密钥是在对称密钥密码学中共享使用的；第二、三种分别是在非对称密钥密码学中使用的公钥和私钥。这里使用三种不同的图标代表这三类密钥，将它们相互区分。如图30.5 。

我们比较一下对称与非对称密钥加密。加密可以想像为电子关锁，解密为电子开锁。发送方把报文放入盒子中，并使用密钥锁住盒子；接收方使用密钥打开盒子，并取出报文。区别在于关锁与开锁的机制、以及使用密钥的类型。

在对称密钥密码学中，使用了相同的密钥对盒子关锁和开锁。在非对称密钥密码学中，用一个密钥锁住盒子，而用另外一个密钥打开盒子。如图30.6说明了它们之间的区别。

---

30.2 对称密钥密码学

几千年前，当人们需要交换秘密的时候（例如在战争中），对称密钥密码学就开始诞生了。在网络安全中，我们仍主要使用对称密钥密码学。然而，现代的加密算法变得更为复杂。首先讨论传统的算法，它是面向字符的，然后讨论现代的算法，它是面向位的。

30.2.1 传统加密算法

简单地介绍一些传统的加密算法，这是面向字符的。尽管现在看来，这些传统加密算法已经过时，但主要的目的是——为了说明现代的加密算法是怎样从传统加密算法中演变过来。

可以把传统的对称密钥加密算法分成两大类：替换加密算法和换位加密算法，如图30.7所示。

1. 替换加密算法

替换加密算法 substitution cipher 使用一个符号代替另一符号 A substitution cipher substitutes one symbol with another 。如果明文中的符号是字母，就用一个字母代替另一个。例如，可以用字母 $D$ 代替 $A$ ，$Z$ 代替 $T$ 。如果符号是数字 $0\sim 9$ ，则可以用 $7$ 代替 $3$ ，$6$ 代替 $2$ 。替换加密算法可以分类为单字母替换和多字母替换加密算法。

在单字母替换加密算法 monoalphabetic cipher 中，明文中的字符（或符号）不管其在文本中的位置，在密文中总是替换为某个固定的字符（或符号）。例如，如果算法要求在明文中的字符 $A$ 必须替换为 $D$ ，则每一个字符 $A$ 都必须替换为字符 $D$ 。换句话说，明文和密文中的字符之间的关系是一对一的。

在多字母替换加密算法 polyalphabetic cipher 中，明文中一个字符（或符号）的每次出现，可以采用不同的字符（或符号）替换。明文中的字符与密文中的字符之间的关系是一对多的关系。例如，字符 $A$ 在文本的开始可以改为字符 $D$ ，但在中间可以改为字符 $N$ 。

很明显，如果明文字符和密文字符之间的关系是一对多的话，那么密钥必须告诉我们：诸多可能的字符中哪些可以用来加密。为了达到这个目的，我们需要把文本分成多个字符组，并使用一个密钥集 divide the text into groups of characters and use a set of keys 。例如，我们可以把文本 "THISISANEASYTASK" 按每 $3$ 个字符分为一组，并使用一组 $3$ 个密钥对其进行加密 apply the encryption using a set of 3 keys 。然后我们对接下来的 $3$ 个字符重复这个过程。

【例30.1】下面所示为明文和其相应的密文，请问这是单字母替换加密算法吗？

Plaintext: HELLO
Ciphertext: KHOOR

解：该加密算法可能是单字母替换加密。因为字符 $L$ 出现的地方都加密为字符 $O$ 。

【例30.2】下面所示为明文和其相应的密文，请问这是单字母替换加密算法吗？

Plaintext: HELLO
Ciphertext: ABNZF

解：该加密算法不是单字母替换加密。因为每次字符 $L$ 出现的地方都加密为不同的字符。第一个 $L$ 加密为 $N$ 、第二个为 $Z$ 。

移位加密

最简单的单字母替换加密算法可能就是移位加密 shift cipher 了。假设明文和密文中仅包含大写字母（$A\sim Z$）。在这个加密过程中，加密算法是"后移 key 位字符" shift key characters down ，key 等于某一个数值；解密算法就是"前移 key 位字符" shift key characters up 。例如，如果 key 为 $5$ ，加密算法就是"后移 $5$ 位字符"（向字母结束的方向），解密算法就是"前移 $5$ 位字符"（向字母开始的方向）。当然，如果到了字母的结束或开始的地方，则进行环绕 wrap around ，即它使用模 $26$ 的模运算。

Julius Caesar大帝使用移位加密与他的军官进行通信。正因为这个原因，移位加密有时也称为凯撒密码 Caesar cipher 。凯撒在他的通信中将 key 设为 $3$ 。

【例30.3】使用移位加密算法，key = 15 ，加密报文 "HELLO" 。
解：我们一次加密一位字母，每一位字母后移 $15$ 位。字母 $H$ 加密为 $W$ 、字母 $E$ 加密为 $T$ 、第一个字母 $L$ 加密为 $A$ 、第二个字母 $L$ 也加密为 $A$ 、字母 $O$ 加密为 $D$ 。因此密文为 "WTAAD" 。

【例30.4】使用移位加密算法，key = 15 ，解密报文 "WTAAD" 。
解：我们一次解密一位字母，每一位字母前移 $15$ 位。字母 $W$ 解密为 $H$ 、字母 $T$ 解密为 $E$ 、第一个字母 $A$ 解密为 $L$ 、第二个字母 $A$ 也解密为 $A$ 、最后字母 $D$ 解密为 $O$ 。因此明文为 "HELLO" 。

2. 换位加密算法

在换位加密算法 transposition cipher 中，字符不发生替换，取而代之的是改变字符的位置。在明文中处于首位的字符可能出现在密文的第十位上；而明文中第八位字符则可能出现在密文的首位。换句话说，换位加密算法对符号块中的符号进行重新排序 A transposition cipher reorders (permutes) symbols in a block of symbols ，从而生成密文。

在换位加密算法中，密钥就是符号在明文和密文中位置的映射关系。例如，下面说明了使用了由四个字符组成的符号块。

Plaintext:  2 4 1 3
Ciphertext: 1 2 3 4

经过加密，我们把处于第二位的字符移位到第一位，第四位的字符移位到第二位，以此类推。解密时则相反。为了更有效率，密钥需要更长，这意味着，我们可以对长数据分组进行加密和解密。图30.8说明了使用上面密钥的 $4$ 字符块的加密和解密，该图同时也说明了加密和解密使用了相同的密钥：加密采用了从上到下的移位，而解密则采用从下往上的移位 The encryption applies it from downward while decryption applies it upward 。

【例30.5】使用上面的密钥对报文 "HELLO MY DEAR" 加密。
解：我们首先把空格从报文中移除，然后把文本按照 $4$ 字符为一组进行分块，在第三个分块的末尾处加上一个伪字符 $Z$ ，结果就是 "HELL OMYD EARZ" 。这三个分组的密文是 "ELHLMDOYAZER" 。

【例30.6】利用例30.5，解密报文 "ELHLMDOYAZER" 。
解：结果是 "HELL OMYD EARZ" ，去除伪字符并加入空字符后，我们得到原始的报文 "HELLO MY DEAR" 。

30.2.2 简单的现代加密算法

到目前为止，所学的传统加密算都是面向字符的。随着电脑的出现，加密算法必须要面向位——这是因为需要加密的信息不仅仅是文本，而且可能包含数字、图片、音频以及视频数据——把这些类型的数据转换成位流是很方便的，对流进行加密，然后发送加密之后的位流。

除此之外，当文本在位级进行处理的时候，每一位字符就被 $8$ 位（或 $16$ 位）替代，这意味着符号的数量变成了 $8$ 个（或 $16$ 个）。杂乱 mingling and mangling 的位比杂乱的字符能够提供更多的安全。

现代加密算法与传统算法相比，使用了不同的策略。现代的对称加密算法是简单加密算法的混合，其使用了许多简单的加密算法来达到加密的目的。首先讨论这些简单的加密算法。

1. XOR加密算法

如今，现代的加密算法通常是由一系列的简单加密算法 simple ciphers 组成，这些都是在数学或计算机科学中预定义的简单函数。第一个讨论的是异或加密算法 XOR cipher ，因为它使用了计算机科学中定义的"异或"操作，是自身可逆转的、最简单的加密算法 the simplest cipher which is self-invertible 。图30.9说明了异或加密算法。

XOR操作需要两个数据输入：明文作为第一个数据，密钥作为第二个数据。换句话说，其中一个输入是需要加密的数据块，另一个输入就是密钥。运算后的结果就是加密后的数据块。注意：在XOR加密算法中，你可以发现密钥、明文及密文的长度是相同的，而且它还有一个非常有趣的属性：加密和解密是相同的 the encryption and decryption are the same 。

2. 旋转加密算法

另一个常用的加密算法是旋转加密算法 rotation cipher ，在这算法中，输入的位被向左或向右进行旋转移动。旋转加密算法可以有密钥、也可以无密钥 The rotation cipher can be keyed or keyless 。有密钥，则密钥的值定义了旋转移动的次数；没有密钥，则旋转移动的次数是固定不变的。图30.10举例说明了一个旋转加密算法。注意：旋转加密算法可以认为是「使用位而不是字符的换位加密算法」的特殊案例 the rotation cipher can be considered a special case of the transpositional cipher using bits instead of characters 。

旋转加密算法有一个有趣的属性。如果原始流的长度为 $N$ ， 经过 $N$ 次旋转移动后，我们得到了原始的输入流。这意味着多于 $N-1$ 次的旋转移动是没有意义的，换句话说，旋转移动的次数必须介于 $1$ 和 $N-1$ 之间。

旋转加密的解密算法使用了相同的密钥及相反的旋转方向。如果我们在加密中向右旋转，解密时则向左旋转，反之亦然。

3. 替换加密算法：S-盒

S-盒（替换盒）S-box (substitution box) 是位级的，但与传统的面向字符的替换加密算法是类似的。S-盒的输入是长度为 $N$ 的位流，输出的结果是另一串长度为 $M$ 的位流。$N$ 与 $M$ 并不一定需要相等。图30.11所示为S-盒。

一般情况下，S-盒是没有密钥的 keyless ，它作为加密或解密的一个中间过程。将输入与输出相匹配的函数可能是预定义的一个数学公式或者是一张表。

4. 换位加密算法：P-盒

P-盒（置换盒） P-box (permutation box) 是位级的，与传统的面向字符的换位加密算法类似。它执行位级的换位，对位进行换位 it transposes bits 。它可以通过软件或硬件的方式实现换位，但硬件实现比较快。与S-盒类似，P-盒通常也是没有密钥的。

在P-盒中，通常有 $3$ 种类型的置换：直接置换 straight permutation 、扩充置换 expansion permutation 、以及压缩置换 compression permutation 。如图30.12所示。

在直接置换算法或直接置换的P-盒中，输入与输出的长度是相同的。换句话说，输入的长度是 $N$ ， 则输出的长度也是 $N$ P-盒只有在输入位与输出位相同的情况下，是可逆转的。在扩充置换算法中，输出端口的数量要大于输入端口；在压缩置换算法中，输出端口的数量要小于输入端口。

30.2.3 现代迭代加密

如今的加密算法被称为迭代加密 round ciphers ，因为它包含了多次迭代 rounds ，每一次迭代是由前面介绍的简单加密算法组成的复杂加密算法。在每次迭代中使用的密钥是，是称为迭代密钥 round key 的通用密钥的子集或变体：如果加密算法有 $N$ 次迭代，则密钥生成器产生 $N$ 个密钥 $K_1,K_2,\dots ,K_N$ ，在第 $1$ 次迭代中使用 $K_1$ ，$K_2$ 在第 $2$ 次迭代中使用，以此类推。

在本节中，介绍两种现代对称密钥加密算法：DES与AES。这些加密算法被认为是分组加密 block ciphers ——因为它们把明文分成多个分组，然后使用相同的密钥对各分组进行加密与解密。到现在为止，DES已经成为事实上的标准 de facto standard ，AES是现在正式的标准 formal standard or de jure standard 。

1. 数据加密标准 DES

复杂的分组加密算法的一个例子是数据加密标准 Data Encryption Standard, DES 。DES是由IBM设计、并被美国政府接受作为非军事和非机密用途的加密标准。该算法采用 $64$ 位的密钥对 $64$ 位的明文进行加密，如图30.13所示。

(1) DES结构

DES有 $2$ 个换位模块（P-盒）和 $16$ 个复杂的迭代加密模块（它们一直在重复）。尽管 $16$ 个迭代算法概念上是相同的，但每个模块使用的是由源密钥衍生的不同密钥 a different key derived from the original key 。

在最初与最终的置换加密是无密钥的、相互之间进行反转的直接置换 keyless straight permutations that are the inverse of each other 。这个置换加密根据预定义的值对 $64$ 位的输入进行置换。DES的每次迭代都是一个复杂的迭代加密算法。如图30.14所示。需要注意的是：加密迭代算法的结构与解密的结构是不相同的。

(2) DES函数

DES的核心是DES函数 DES function ，DES函数采用了 $48$ 位的密钥，根据最右面 $32$ 位 $R_i$ 产生一个 $32$ 位的输出。这个函数由 $4$ 个操作组成：XOR 、扩充置换、一组S-盒、以及一个直接置换。如图30.15所示。

(3) 三重DES

对DES的批评是密钥太短了。为了加长密钥，提出并实现了三重DES或者 3DES ，它使用三个DES模块，如图30.16所示。注意，加密模块使用的是DES加密-解密-加密 encryption-decryption-encryption 的组合，而解密模块使用的是解密-加密-解密 decryption-encryption-decryption 的组合。

在使用的两个不同版本的3DES是：$2$ 个密钥的3DES和 $3$ 个密钥的3DES：

• 为了使密钥长度达到 $112$ 位，并且同时避免DES遭受类似中间人 man-in-middle 的攻击，设计出使用 $2$ 个密钥的3DES。在这个版本中，第一个和第三个密钥是相同的（密钥 $1=$ 密钥 $3$）；这有一个优势：通过一个单一的DES模块加密的文本，可以用一个新的3DES模块解密，我们只是设置所有的密钥等于密钥 $1$ 。
• 许多算法使用了 $3$ 个密钥的3DES加密算法，这使密钥的长度增加到 $168$ 位。
  

2. 高级加密标准

因为DES的密钥太短，高级加密标准 Advanced Encryption Standard, AES 应运而生。尽管三重DES增加了密钥的长度，但处理的过程太慢。国家标准与技术协会 National Institute of Standards and Technology , NIST 选择Rijndael算法 Rijndael algorithm （这算位根据两个比利时发明人 Vincent Rijmen 与 Joan Daemen 命名）作为AES的基础理论。

AES是一个复杂的迭代加密算法，它有 $3$ 种密钥长度：$128$ 位、$192$ 位及 $256$ 位。即三种不同的配置，具有不同的迭代次数和密钥长度。表30.1所示为数据块、迭代次数及密钥长度之间的相互关系。

在本节中仅讨论 $10$ 次迭代、$128$ 位密钥的配置。其他配置的结构和操作是类似的，它们的区别就在于密钥的生成方式。

通用的结构如图30.17所示。在初始的异或操作后面是 $10$ 次迭代加密，最后一次迭代与前面的迭代稍微有点区别，它缺少一步操作 it is missing one operation 。

尽管 $10$ 次反复的模块几乎是相同的，但每一个模块使用的是从原始密钥衍生出来的不同的密钥。

每次迭代的结构

AES的每次迭代，除了最后一个之外，都是由 $4$ 个可倒转的 invertible 操作组成的加密算法。最后一次迭代仅有 $3$ 个操作。图30.18所示为每次迭代中操作的流程图。每次迭代中，$4$ 个操作中的每个操作 Byte substitution, Byte permutation, Complex operation, AddRoundKey 都使用了一个复杂的加密算法，这已超出了范围。

3. 其他的加密算法

在过去的二十年里，设计并使用了许多其他的对称分组加密算法 symmetric block ciphers 。大部分的这些加密算法有与上面讨论的两种加密算法（DES和AES）相似的特征。通常情况下，它们之间的区别在于分组和密钥的长度、迭代的次数及所用的函数，但基本原理是一致的。

为了在这些加密算法的细节方面不带来负担，对每一个加密算法只给出了简单的描述。

• 国际数据加密算法 International Data Encryption Algorithm, IEDA 是由 XuejiaLai 和 James Massey 发明的。分组长度为 $64$ 位、密钥长度为 $128$ 位，可以通过硬件和软件的方法实现。
• Blowfish算法是由 Bruce Schneier 发明的。分组长度为 $64$ 位，密钥长度介于 $32$ 位与 $448$ 位之间。
• CAST-128算法是由 Carlisle Adams 与 Stafford Tavares 共同发明的。它是由 $16$ 次迭代的 Feistel 加密算法组成的。分组长度为 $64$ 位、密钥长度为 $128$ 位。
• RC5算法是由 Ron Rivest 发明的。这是由不同的分组长度、密钥长度、迭代次数组成的加密算法组合。

30.2.4 运算模式

运算模式 mode of operation 是一种使用（诸如前面讨论的DES、AES之类的）现代分组加密算法 modern block ciphers 的技术（如图30.19）。

1. 电子代码本

电子代码本模式 electronic code block mode, ECB 是纯分组加密技术。明文被划分成 $N$ 位长度的分组，密文也是由 $N$ 个比特的分组组成，值 $N$ 依赖于使用的加密算法的类型。方法如图30.20所示。

1. 因为密钥、以及加密/解密的算法是相同的，因此在明文中相同的一些分组，在密文中对应的分组也是相同的。例如 ， 在明文中分组 $1,5,9$ 是相同的，则密文中分组 $1,5,9$ 也是相同的。这就会导致了安全隐患，敌人会因为对应的密文分组相同，而猜测推断明文分组是相同的。
2. 如果我们对明文分组重新排序，则密文分组也会重新排序。
3. 每一个分组之间都是独立的。每一个分组都可以独立地进行加密与解密。其中一个分组在加密与解密时发生问题，不影响其他的分组。
4. 在一个分组中发生错误，不会传播到其他的分组 。 如果一个或多个比特在传输过程中被破坏，它只会影响解密后相应明文中的比特，其他的明文块并没有受到影响。如果通道不是无噪声的，那么这将成为一个真正的优点 This is a real advantage if the channel is not noise-free 。

2. 加密分组链

加密分组链模式 cipher block chaining mode, CBC 试图通过在当前块的准备中包含前一个密码块，来缓解ECB模式中发生的问题。如果现在的分组是 $i$ ， 前面的密文分组 $C_{i\_1}$ 则应用到分组 $i$ 的加密中。即，当一个分组完全被加密后、分组被发送，但它的一份拷贝仍保存在寄存器（数据存放的地方）中，用于对下一个分组的加密。

可能对最初的分组有些疑惑，在第一个分组前面是没有密文分组的。在这种情况下，使用了称为初始化向量 initiation vector, IV 的假冒分组 phony block 。发送方与接收方都认可这个预先定义的 IV 。 换句话说，这个 IV 替代了不存在的 $C_0$ ，如图30.21所示。

下面是加密分组链模式的一些特征：

1. 即使密钥和加密/解密算法都相同，在明文中的相同分组对应的密文分组也不相同。例如，在明文中，分组 $1,5,9$ 相同，但在密文中的分组 $1,5,9$ 并不相同。敌人不能从密文中猜测出，那两个分组是相同的。
2. 分组之间是相互依赖的。每一个分组的加密与解密都是基于前一个分组。当一个分组在加密与解密中发生问题时，会影响到其他的分组。
3. 在一个分组中发生错误会传播到其他的分组。如果在传输过程中一个或多个位被破坏， 它会影响到解密后的下一个明文块中的位 bits in the next blocks of the plaintext 。

3. 加密反馈

加密反馈模式 cipher feedback mode, CFM 是专门为这个情况而设计的：我们需要发送或接收 $r$ 位的数据，这里 $r$ 是一个数值，不同于下面要采用的加密算法的分组长度。$r$ 的值可以是 $1,4,8$ 或其他任意的位。

由于所有分组加密算法 block ciphers 一次只能处理一个数据块 work on a block of data at a time ，现在的问题就是：如何对仅仅只有 $r$ 位的数据进行加密。解决的方法是：用加密算法对一个比特块进行加密 let the cipher encrypt a block of bits ，并且只使用其前 $r$ 个比特作为新的密钥（stream key）来加密用户数据的 $r$ 个比特。如图30.22所示。

下面是加密反馈模式的一些特征：

1. 对相同的明文进行加密，如果改变初始化向量，则密文是不相同的。
2. 密文 $C_i$ 依赖于 $P_i$ 及先前的密文分组。
3. 在密文分组中一位或多位发生错误，则会影响到后面的密文分组。

4. 输出反馈

输出反馈模式 output feedback mode, OFB 与CFB非常相似，只有一个不同点。密文中的每一位都独立于前一位或多位 Each bit in the ciphertext is independent of the previous bit or bits ，这就避免了错误的传播。如果在传输的过程中发生了错误，它不会影响到后面的位。注意：在CFB中，发送方与接收方都使用了加密算法。而在OFB中，DES或AES等分组加密算法只能用于创建密钥流 key stream 。创建下一个位流的反馈来源于密钥流的前几位 the previous bits of the key stream ，而不是密文，密文并没有参加密钥流的创建。图30.23说明了OFB模式。

下面是加密反馈模式的一些特征：

1. 对相同的明文进行加密，如果改变初始化向量，则密文是不相同的。
2. 密文 $C_i$ 依赖于明文 $P_i$ 。
3. 在密文分组中，一位或多位发生错误，并不会影响到后面的密文分组。

---

30.3 非对称密钥密码学

在前面几节中讨论了对称密钥密码学。在本节中，介绍非对称密钥（公共密钥密码学）。正如前面所提到的，一个非对称密钥（或者公共密钥）加密算法使用 $2$ 个密钥：一个是公钥，一个是私钥。我们讨论两种加密算法：RSA 和 Diffie-Hellman 。

30.3.1 RSA

最常见的公共密钥加密算法是RSA，RSA是根据它的发明者 Rivest, Shamir, Adleman 而命名的。它使用两个数字：$e$ 和 $d$ ， 作为公钥与密钥。如图30.24所示。

两个密钥 $e$ 和 $d$ 之间有一种特殊的关系，讨论这个关系超出了范围。说明一下怎样计算出这两个密钥、而不去证明。

1. 选择密钥

Bob使用以下的步骤选择私钥与公钥：

1. Bob选择两个非常大的素数 $p$ 和 $q$ 。记住素数只能被 $1$ 和它本身整除。
2. Bob将上面两个素数相乘得到 $n$ ， 作为加密与解密的模，即 $n=p\times q$ 。
3. Bob计算另一个整数 $\varphi =(P-1)\times (q-1)$ 。
4. Bob选择一个随机的正数 $e$ ，然后计算出 $d$ ， 使得 $d\times e\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}\varphi$。
5. Bob对外公布 $e$ 和 $n$ ， 保留 $\varphi$ 和 $d$ 作为私钥。

2. 加密

任何一个想发送信息给Bob的人，都可以使用 $e$ 和 $n$ 。例如，如果Alice需要发送信息给Bob，她可以把信息转为整数（一般情况下，选择较小的整数），这就是明文。然后通过使用 $e$ 和 $n$ 计算出密文。
$$C=P^e(\mathrm{m}\mathrm{o}\mathrm{d}n)$$ Alice将密文 $C$ 发送给Bob。

3. 解密

Bob保留 $\varphi$ 和 $d$ 作为私钥。当接收到密文后，他使用私钥 $d$ 对信息进行解密。
$$P=C^d(\mathrm{m}\mathrm{o}\mathrm{d}n)$$

4. 限制

为了RSA能够正常工作，$P$ 的值必须要小于 $n$ 的值。如果 $P$ 是一个很大的整数，则明文需要分成多个分组，使得 $P$ 小于 $n$ 。

【例30.7】Bob选择 $p=7,q=11$ ， 并计算出 $n=7\times 11=77,\varphi =(7-1)\times (11-1)=60$ ，他选择两个密钥 $e$ 和 $d$ ， 如果 $e=13$ ，则 $d=37$ ，因为 $(e\times d)\mathrm{m}\mathrm{o}\mathrm{d}\varphi =13\times 37\%60=1$ 。现在，$e=13,n=77$ 为公钥，$d=37,\varphi =60$ 为私钥。

现在假设Alice发送明文 $5$ 给Bob ，她用公钥 $13$ 对明文 $5$ 进行加密。

明文: 5
C = 5^13 (mod 77) = 26
密文: 26

Bob接收密文 $26$ ，并使用私钥 $37$ 对密文进行解密：

密文: 26
P = 26^37 (mod 77) = 5
明文: 5

Alice发送的明文是 $5$ ，被Bob接收仍旧为明文 $5$ 。

【例30.8】Jennifer为自己创建了一对密钥，她选择 $p=397,q=401$ ，计算出 $n=159197$ ，$\varphi =396\times 400=158400$ 。然后她选择 $e=343$ ，$d=12007(343\times 12007\mathrm{m}\mathrm{o}\mathrm{d}158400=1)$ 。说明如果Ted知道了 $e,n$ ，他如何发送信息给Jennifer。

解：假设Ted想发送报文 "NO" 给Jennifer，他根据相应的字符码，把每一个字符转换为两位数（从 $00$ 到 $25$）。然后连接这两个字符码，得到一个四位的整数，即明文为 $1314$ 。Ted用 $e$ 和 $n$ 对报文进行加密，密文为 $1314^{343}=33677\mathrm{m}\mathrm{o}\mathrm{d}159197$ 。

Jennifer接收到报文 $33677$ 后，使用解密密钥 $d$ 对密文进行解密，如 $33677^{12007}=1314\mathrm{m}\mathrm{o}\mathrm{d}159197$ 。然后Jennifer解码 $1314$ 为报文 "NO" 。图30.25说明了过程。

【例30.9】我们给出一个现实的例子。我们选择 $512$ 位的 $p$ 和 $q$ ， 并计算出 $n$ 与 $\varphi$ 。然后选择 $e$ ， 并用 $\varphi (n)$ 测试相应的素数，计算出 $d$ 。最后显示加密与解密的结果。我们写了一个Java的程序来做这件事情，该类型的计算是计算器不能完成的。

我们随机选择一个 $512$ 位 512-bits 的整数，整数 $p$ 是一个 $159$ 位 159-digit 的数。

p=96130345313583504574191581280615427909309845594996215822583150879647940
45505647063849125716018034750312098666606492420191808780667421096063354
219926661209

整数 $q$ 是 $160$ 位 160-digit 的数。

q=12060191957231446918276794204450896001555925054637033936061798321731482
14848376465921538945320917522527322683010712069560460251388714552496900
0359660045617

我们计算 $n$ ，它是 $309$ 位的整数。

n=11593504173967614968892509864615887523771457375454144775485526137614788
54083263508172768788159683251684688493006254857641112501624145523391829
27162507656772727460097082714127730434960500556347274566628060099924037
10299142447229221577279853172703383938133469268413732762200096667667183
1831088373420823444370953

我们计算 $\varphi$ ， 它也是 $309$ 位的整数。

ϕ=11593504173967614968892509864615887523771457375454144775485526137614788
5408326350817276878&159683251684688493006254857641112501624145523391829
27162507656751054233608492916752034482627988117554787657013923444405716
98958172819609822636107546721186461217135910735864061400888517026537727
1264467341066243857664128

我们选择 $e=35535$ ， 然后找到 $d$ 。

e=35535
d=58008302860037763936093661289677917594669062089650962180422866111380593852
82235873170628691003002171085904433840217072986908760061153062025249598844
48047568240966247081485817130463240644077704833134010850947385295645071936
77406119732655742423721761767462077637164207600337085333288532144708859551
36670294831

Alice要发送报文 "THIS IS A TEST" ，这个报文可以通过 $00\sim 26$ 编码方案转换为数值（$26$ 为空字符）。

P=1907081826081826002619041819

Alice计算密文为：

C=p^e=4753091236462268272063655506105451809423717960704917165232392430544529
6061319932856661784341835911415119741125200568297979457173603610127821
8847892741566090480023507190715277185914975188465888632101148354103361
6578984679683867637337657774656250792805211481418440481418443081277305
9004692874248559166462108656

Bob通过 $p=C^d\mathrm{m}\mathrm{o}\mathrm{d}n$ ， 将密文解密，$p$ 为：

P=1907081826081826002619041819

解密后的明文解码后为："THIS IS A TEST" 。

5. 应用

尽管RSA可以对实际的报文进行加密与解密，但如果报文很长，则加解密的过程非常慢。因而，RSA更适合那些短报文，如短的报文摘要（第31章）、或在对称密钥加密系统 symmetric-key cryptosystem 中的对称密钥。实际上，我们将看到，RSA被用于数字签名和其他密码系统中，这些系统通常需要在不访问对称密钥的情况下、加密小报文。在后面也可以看到，RSA也可以用于鉴别。

30.3.2 Diffie-Hellman加密系统

RSA是一个公钥加密系统，并经常用于对称密钥的加密与解密。另一方面，Diffie-Hellman最初设计是用于密钥的交换。在Diffie-Hellman加密系统 Diffie-Hellman cryptosystem 中，两方产生一个对称的会话密钥 session key 用来交换数据，而且无需记住或存储密钥以备将来使用 。他们不需要面对面地对密钥达成共识，这可以通过因特网完成。

让我们看一下：当Alice与Bob需要一个对称密钥来通信时，协议是如何进行工作的。在建立对称密钥之前，两方需要选择两个数 $p$ 和 $g$ 。第一个数 $p$ 是非常大的素数，大概为 $300$ 位的十进制数（$1024$ 位）300 decimal digits (1024 bits) ，第二个数是一个随机数。这两个数并不需要保密，可以在因特网上传送，并且可以是公开的。

1. 过程

图30.26说明了整个过程，步骤如下：

• 步骤 $1$ ：Alice选择一个大的随机数 $x$ ， 并计算出 $R_1=g^x\mathrm{m}\mathrm{o}\mathrm{d}p$ 。
• 步骤 2：Bob选择另一个大的随机数 $y$ ， 并计算出 $R_2=g^y\mathrm{m}\mathrm{o}\mathrm{d}p$ 。
• 步骤 3：Alice发送 $R_1$ 给Bob，注意Alice并不发送 $x$ 的值，它仅发送 $R_1$ 。
• 步骤4：Bob发送 $R_2$ 给Alice，注意Bob并不发送 $y$ 的值，它仅发送 $R_2$ 。
• 步骤 5：Alice计算出 $K=(R_2{)}^x\mathrm{m}\mathrm{o}\mathrm{d}p$ 。
• 步骤6：Bob也计算出 $K=(R_1{)}^y\mathrm{m}\mathrm{o}\mathrm{d}p$ 。

这个会话的对称密钥就是 $K$ 。
$$(g^x\mathrm{m}\mathrm{o}\mathrm{d}p{)}^y\mathrm{m}\mathrm{o}\mathrm{d}p=(g^y\mathrm{m}\mathrm{o}\mathrm{d}p{)}^x\mathrm{m}\mathrm{o}\mathrm{d}p=g^{xy}\mathrm{m}\mathrm{o}\mathrm{d}p$$ Bob已经计算出 $K=(R_1{)}^y\mathrm{m}\mathrm{o}\mathrm{d}p=(g^x\mathrm{m}\mathrm{o}\mathrm{d}p{)}^y\mathrm{m}\mathrm{o}\mathrm{d}p=g^{xy}\mathrm{m}\mathrm{o}\mathrm{d}p$ ，Alice也计算出 $K=(R_2{)}^x\mathrm{m}\mathrm{o}\mathrm{d}p=(g^y\mathrm{m}\mathrm{o}\mathrm{d}p{)}^x\mathrm{m}\mathrm{o}\mathrm{d}p=g^{xy}\mathrm{m}\mathrm{o}\mathrm{d}p$ ，两个人都得到了相同的值，并且Bob不知道 $x$ 的值，而Alice也不知道 $y$ 的值。

【例30.1】举一个普通的例子来说清楚这个过程。例子中使用了小的数，但必须注意到现实中，数是非常大的。假设 $g=7,p=23$ 。步骤如下：

1. Alice选择 $x=3$ ， 并计算出 $R_1=7^3\mathrm{m}\mathrm{o}\mathrm{d}23=21$ 。
2. Bob选择 $y=6$ ， 并计算出 $R_2=7^6\mathrm{m}\mathrm{o}\mathrm{d}23=4$ 。
3. Alice发送数值 $21$ 给Bob。
4. Bob发送数值 $4$ 给Alice。
5. Alice 计算出对称密钥 $K=4^3\mathrm{m}\mathrm{o}\mathrm{d}23=18$ 。
6. Bob也计算出对称密钥 $K=21^6\mathrm{m}\mathrm{o}\mathrm{d}23=18$ 。

对Alice与Bob来说，$K$ 值是相同的；$g^{xy}\mathrm{m}\mathrm{o}\mathrm{d}p=7^{18}\mathrm{m}\mathrm{o}\mathrm{d}23=18$ 。

2. Diffie-Hellman的思想

如图30.27所示，Diffie-Hellman的概念是简单但是一流的。我们可以认为，在Alice与Bob之间的密钥是由三部分组成：$g,x,y$ 。第一部分是公开的。每个人都知道密钥的 $1/3$ ，即 $g$ 是公开的值。另外两部分必须由Alice和Bob加入。每一个人加入一部分，Alice为Bob加入第二部分 $x$ ，Bob为Alice加入第二部分 $y$ 。当Alice从Bob接收到了全部密钥的 $2/3$ 后，她在最后部分加入她的 $x$ ，完成了整个密钥；当Bob从Alice接收到了全部密钥的 $2/3$ 后，他在最后部分加入他的 $y$ ，完成了整个密钥。注意到，尽管在Alice手中，密钥由 $g-y-x$ 组成；在Bob手里密钥由 $g-x-y$ 组成，但这两个密钥是相同的，因为 $g^{xy}=g^{yx}$ 。

注意：尽管这两个密钥是相同的，但是Alice还是不能发现Bob使用的值。因为计算是通过模 $p$ 生成的；Alice从Bob接收到的是 $g^y\mathrm{m}\mathrm{o}\mathrm{d}p$ ， 而不是 $g^y$ 。

3. 中间人攻击 Man-in-the-Middle Attack

Diffie-Hellman是一个非常复杂的创建对称密钥的算法。如果 $x,y$ 是一个非常大的值，那么对Eve来说，只知道 $p$ 与 $g$ 的情况下，破解这个密钥是极其困难的。入侵者中途截获 $R_1$ 和 $R_2$ ，还需要确定 $x$ 和 $y$ ， 但从 $R_1$ 和 $R_2$ 中找到 $x$ 与 $y$ 是两件非常困难的工作。即使高端计算机也有可能花上几年的时间，通过尝试各个不同的数值来找到密钥。另外，Alice和Bob在下次需要通信的时候，可能已经更换了密钥。

然而，协议本身的确有自身的弱点。Eve并不需要一定要找到 $x$ 与 $y$ 的值来攻击通信协议。她可以通过产生两个密钥来愚弄Alice与Bob：一个密钥用于Alice与她自己之间，另一个密钥用于Bob与她自己之间。图30.28说明了这个情况。

下面可能会发生：

1. Alice选择 $x$ ，计算 $R_1=g^x\mathrm{m}\mathrm{o}\mathrm{d}p$ ， 并发送 $R_1$ ，给Bob。
2. 入侵者Eve，中途截获了 $R_1$ ，她选择 $z$ ，计算 $R_2=g^z\mathrm{m}\mathrm{o}\mathrm{d}p$ ，并发送 $R_2$ 给Alice和Bob两个人。
3. Bob选择 $y$ ，计算 $R_3=g^y\mathrm{m}\mathrm{o}\mathrm{d}p$ ， 并发送 $R_3$ 给 Alice，被Eve中途截获，永远不能到达Alice。
4. Alice和Eve计算 $K_1=g^{xz}\mathrm{m}\mathrm{o}\mathrm{d}p$ ， 这就成为了Alice与Eve的共享密钥。然而Alice认为这是她与Bob之间的共享密钥。
5. Eve和Bob计算 $K_2=g^{zy}\mathrm{m}\mathrm{o}\mathrm{d}p$ ， 这就成为了Eve与 Bob的共享密钥。然而Bob认为这是他与Alice之间的共享密钥。

换句话说，产生两个密钥替代了原来的一个密钥：Alice与Eve之间一个，Eve与Bob之间一个。当Alice发送用 $K_1$（Alice与Eve共享的）加密的数据给Bob时，它可以被Eve解密并读取。Eve可以发送用 $K_2$（Eve与Bob共享的）加密的报文给Bob，或者她甚至可以更改报文、并发送一个完全新的报文，Bob被愚弄、并充分相信这个报文来自Alice 。在另一个方向上，相同的场景也会发生在Alice方。

这种情况称为中间人攻击 man-in-middle attack ，因为Eve位于中间，她中途截取Alice发送给Bob的 $R_1$ 、和Bob发送给Alice的 $R_3$ 。因为类似于志愿救火队列中人与人传递水桶，所以也称为水桶队列攻击 bucket brigade attack 。

4. 鉴别

如果 Bob与Alice在第一次时相互进行鉴别，就可以避免中间人攻击。换句话说，密钥交换的过程可以结合鉴别方案，来避免中间人攻击。在第31章讨论鉴别。