转载

读《图解密码技术》(一): 密码

原创文章，转载请注明：转载自Keegan小钢
并标明原文链接： http://keeganlee.me/post/reading/20160629
微信订阅号： keeganlee_me
写于2016-06-29

读《图解密码技术》(一):密码
读《图解密码技术》(二):认证
读《图解密码技术》(二):密钥、随机数和应用技术

以前，对一些密码技术，虽然懂得怎么用，但对其原理却一直不甚了解，比如，用公钥加密后，为什么用私钥就可以解密？DES和AES加密时为什么需要一个初始化向量？想要了解这些密码技术的基本原理，而最近买书时看到了《图解密码技术》这本书，刚好可以解答到我的这些问题，于是，就买回来看了。

而从现在开始，每读一本书，我都会尽量分享我的读书笔记，有两个目的：一是为自己做总结整理，加强记忆和理解；二是可以给还没看过该书的读者提供摘要和指引。好了，接下来进入正文。

前言

《图解密码技术》的目标读者主要包括以下人群：

对密码相关知识感兴趣的人
希望理解公钥密码、数字签名等密码技术原理的人（我就属于此类）
对信息安全感兴趣的人

本书的结构分为三部分：

密码：内容主要包括对密码技术整体性的讲解，以及历史密码、对称密码、公钥密码等保证机密性的密码技术。
认证：内容包括单向散列函数、消息认证码、数字签名、证书等密码技术。
密钥、随机数和应用技术：内容包括密钥、随机数相关的知识，以及PGP、SSL/TLS等应用技术。

本篇文章是关于第一部分的笔记。

密码技术

密码技术的目的很明确，就是为了解决信息安全问题。信息安全可分为四类特性：

机密性 ：为了防止信息被窃听，对应的密码技术有 对称密码 和 公钥密码 。
完整性 ：为了防止信息被篡改，对应的密码技术有 单向散列函数 、 消息认证码 、 数字签名 。
认证：为了防止攻击者伪装成真正的发送者，对应的密码技术有 消息认证码 和 数字签名 。
不可否认性 ：为了防止发送者事后否认自己没有做过，对应的密码技术为 数字签名 。

信息安全和密码技术之间的关系可以用下图来表示：
读《图解密码技术》(一): 密码

接下来就简单了解下这些密码技术：

对称密码 ：也称为共享密钥密码、私钥密码等，是指在加密和解密时使用同一密钥的方式。
公钥密码 ：也称为非对称密码，是指在加密和解密时使用不同密钥的方式。对称密码和公钥密码可以保证数据的机密性。
单向散列函数 ：MD5、SHA-1，就是单向散列函数的例子，使用单向散列函数可以计算出散列值，散列值也称为哈希值、密码校验和、指纹、消息摘要。使用单向散列函数可以保证数据的完整性。
消息认证码 ：消息认证码是一种确认完整性并进行认证的技术，英文名称为message authentication code，简称为MAC。
数字签名 ：数字签名相当于现实世界中的盖章、签字的功能，使用数字签名可以识别篡改和伪装，还可以防止否认。
伪随机数生成器 ：伪随机数生成器并不直接解决信息安全问题，但它承担了密钥生成的重要职责。而密钥的重要性就不用多说了。

一次性密码本

曾经以为，理论上应该没有任何密码是无法破译的。只要通过暴力破解法，无论任何密文总有一天都能够被破译。如今才知道，特例是存在的。这个特例就是 一次性密码本 。即使用暴力破解法，就算破解到世界末日，也破译不了一次性密码本。

一次性密码本其实非常简单，它的原理就是： 将明文与一串随机的比特序列进行XOR运算，即异或运算 。随机的比特序列也称为密钥，密钥的长度需与明文等长。而解密时，则将密文与密钥再进行一次XOR运算，就可以得到明文了。

举例，现在要对midnight这个字符串进行加密，对其进行ASCII编码后得到一串比特序号：
读《图解密码技术》(一): 密码
以上为64比特，然后，随机生成一个同样64比特长的密钥：

接着，将明文和密钥进行XOR运算：

这样，密文就产生了。而解密则是反向运算，即将密文与密钥进行XOR运算：

一次性密码本，就是这么简单。那么，为什么它不可破译呢？用暴力破解，尝试所有可能的密钥组合，总能得到midnight啊。问题就在于，即使解密出了midnight这个字符串，也无法判断它是否是正确的明文。因为，所有64比特的排列组合都会出现，那么，解密出来的，除了midnight，还会有onenight、lastnight，以及aaaaaaaa、abcdefgh、ZZZZZZZZ等各种字符串，根本无法判断哪个才是正确的明文。

虽然一次性密码本无法被破译，但它并不实用。最大的缺点就在于每一次通信都需要使用不同的密钥，所以密钥就无法重用了，“一次性”也正是由此而来。而且，每次密钥的生成都必须是无重现性的真正随机数，而不是伪随机数。其他的，密钥的配送、保存、同步也都是比较麻烦。所以，能够使用一次性密码本的，只有机密性重与一切，且可以花费大量财力和人力来生成并配送密钥的场合。据说，大国之间的热线就用了一次性密码本，密钥应该是通过特工直接送到对方手上的。

对称密码

对称密码使用相同的密钥进行加密和解密，作为标准的对称密码主要有 DES 、 三重DES 和 AES ，它们都属于 分组密码 ，即以分组为单位进行处理的密码算法。DES和三重DES的分组长度都是64比特，而AES的分组长度可以为128比特、192比特和256比特中的一种。那么，如果要加密的明文比较长，就需要对密码算法进行迭代，而迭代的方法就称为分组密码的模式。具体有哪些模式，后面再说。

DES

DES(Data Encryption Standard)是一种将64比特的明文加密成64比特的密文的对称密码算法，它的密钥长度是56比特，即7个字节。DES的结构采用的是 Feistel网络 。Feistel网络中，加密的各个步骤称为轮 (round)，整个加密过程就是进行若干次轮的循环。下图是Feistel网络中一轮的计算流程。DES是一种16轮循环的Feistel网络。
读《图解密码技术》(一): 密码
一轮的具体计算步骤如下：

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

其中， 子密钥 指的是本轮加密使用的密钥。每一轮的子密钥都是不同的。 轮函数 的作用则是根据“右侧”和子密钥生成对“左侧”进行加密的比特序列，它是密码系统的核心。

但是，这样一来“右侧”根据没有被加密，因此需要用不同子密钥对一轮的处理重复若干次，并在没两轮之间将左侧和右侧的数据对调。下图展示了一个3轮的Feistel网络：
读《图解密码技术》(一): 密码

那么，Feistel如何解密呢？很简单，只要按照相同的顺序来使用子密钥就可以完成解密了。即将上图中的子密钥1换成了子密钥3，而子密钥3则换成子密钥1，输入的为密文，输出的则为明文了。

无论是任何轮数、任何轮函数，Feistel网络都可以用相同的结构实现加密和解密，且加密的结果必定能够正确解密。因为Feistel网络具有如此方便的特性，因此，被许多分组密码算法使用，包括5个AES最终候选算法中的其中3个算法：MARS、RC6、Twofish。

三重DES

现在DES已经可以在短时间内被暴力破解，因此，其强度大不如前了。为了增强DES的强度，因此出现了三重DES(triple-DES)，将DES重复3次所得到的一种密码算法，通常缩写为3DES，其机制如下图所示：
读《图解密码技术》(一): 密码
明文经过三次DES处理才能变成最后的密文，而由于DES的密钥长度为56比特，因此三重DES的密钥长度则为56*3=128比特。另外，从图中也可以发现，三重DES并不是进行3次DES加密，而是加密-> 解密 ->加密的过程。这是为了向下兼容，即使用DES加密的密文，也可以通过三重DES进行解密。

三重DES的解密过程和加密相反，是以密钥3、密钥2、密钥1的顺序执行解密->加密->解密的操作。即将上图从明文到密文的箭头反过来就是解密的流程了。

AES

AES(Advanced Encryption Standard)是取代其前任标准(DES)而成为新标准的一种对称密码算法。AES最终候选算法名单中，总共有5种算法，分为为：MARS、RC6、Rijndael、Serpent、Twofish。但最终被选定为AES的是 Rijndael 算法。

Rijndael使用的并不是Feistel网络，而是 SPN结构 。Rijndael加密中的一轮如下图所示，其分组为128比特，即16字节，加密过程经过4个步骤：SubBytes、ShiftRows、MixColumns、AddRoundKey。
读《图解密码技术》(一): 密码
SubBytes 就是根据一张替换表(S-Box)，将输入中每个字节的值替换成另一个字节的值。 ShiftRows 即将SubBytes的输出以字节为单位进行打乱出路，当然，这种打乱处理也是有规律的。 MixColumns 即对一个4字节的值进行比特运算，将其变成另外一个4字节的值。 AddRoundKey 就是将MixColumns的输出与轮密钥进行XOR处理。至此，一轮就结束了。实际上，在Rijndael中需要重复进行10~14轮计算。

而下图则是一轮解密的流程图，基本也是反向操作，加密时的SubBytes、ShiftRows、MixColumns，解密时分别为反向运算的InvSubBytes、InvShiftRows、InvMixColumns。这是因为Rijndael不像Feistel网络一样能够用同一种结构实现加密和解密。
读《图解密码技术》(一): 密码

对于三种对称密码，DES因为已经很容易被暴力破解，因此不建议再使用；三重DES目前还被银行等机构使用，但其处理速度不高，而且在安全性方面也逐渐显现出了一些问题；AES作为最新标准，安全、快速，而且可以在各种平台上工作，可以算是目前最佳的选择。另外，其他AES最终候选算法也可以作为AES的备份。和Rijndael一样，这些密码算法也都经过了严格的测试，且没有发现任何弱点。

分组模式

DES、AES都属于分组密码，它们只能加密固定长度的铭文。如果需要加密任意长度的明文，就需要对分组密码进行迭代，而迭代方法就称为分组密码的“模式”。分组密码有很多种模式，主要有：ECB、CBC、CFB、OFB、CTR。如果模式选择不恰当，就无法保证机密性。

ECB模式

ECB全称为Electronic CodeBook， 电子密码本模式 ，是最简单的一种模式，它直接将明文分割成多个分组并逐个加密，如下图，其中，加密和解密是指用分组密码算法加密和解密，其中也省略了密钥的描述。
读《图解密码技术》(一): 密码
当最后一个明文分组的内容小于分组长度时，需要用一些特定的数据进行填充。

这种模式的优点就是简单、快速，加密和解密都支持并行计算。而缺点也比较明显，因为每个明文分组都各自独立地进行加密和解密，如果明文中存在多个相同的明文分组，则这些分组最终会被转换为相同的密文分组。这样一来，只要观察一下密文，就可以知道明文中存在怎样的重复组合，并可以以此为线索来破译密码。另外，攻击者可以通过改变密文分组的顺序，或删除密文分组，或替换掉密文分组，就可以达到对明文操纵的目的，而无需破译密码。

CBC模式

CBC全称为Cipher Block Channing， 密文分组链接模式 ，是将前一个密文分组与当前明文分组的内容混合起来进行加密的。在CBC模式中，首先将明文分组与前一个密文分组进行XOR运算，然后再进行加密。加密第一个明文分组时，由于不存在“前一个密文分组”，因此需要事先准备一个长度为一个分组的比特序列来代替“前一个密文分组”，这个比特序列称为 初始化向量 (initialization vector)，通常缩写为IV。一般来说，每次加密时都会随机产生一个不同的比特序列来作为初始化向量。CBC模式的加解密流程如下图：
读《图解密码技术》(一): 密码
CBC模式避免了ECB模式的弱点，明文的重复排列不会反映在密文中。这是推荐使用的一种模式。

CFB模式

CFB全称为Cipher FeedBack， 密文反馈模式 ，前一个密文分组会被送回到密码算法的输入端，如下图：
读《图解密码技术》(一): 密码
CFB模式中，由密码算法所生成的比特序列称为 密钥流 (key stream)。需要注意的是，CFB模式解密时，密码算法执行的是加密操作，因为密钥流是通过加密操作来生成的。

CFB模式无法抵御重放攻击。因此，一般不建议使用了，推荐用CTR模式代替。

OFB模式

OFB全称为Output-FeedBack， 输出反馈模式 ，密码算法的输出会反馈到密码算法的输入中，如下图：
读《图解密码技术》(一): 密码
OFB模式有个缺陷，如果对密钥流的一个分组进行加密后其结果碰巧和加密前是相同的，那么这一分组之后的密钥流就会变成同一值的不断反复。因此，一般不建议使用了，推荐用CTR模式代替。

CTR模式

CTR全称为CountTeR， 计数器模式 ，是一种通过逐次累加的计数器进行加密来生成密钥流的流密码，如下图：
读《图解密码技术》(一): 密码
CTR模式中，每个分组对应一个逐次累加的计数器，并通过对计数器进行加密来生成密钥流。计数器分为两部分，前部分为 nonce ，这和初始化向量一样，也是一个随机比特序列；后部分为分组序号。

从图中还可以知道，CTR模式对每个分组的处理是相对独立的，这就意味着加密和解密都能够实现并行计算。

CTR模式在错误和机密性方面都具有不错的性质，也没有上面提到的CFB和OFB的弱点，因此，现在都推荐使用CTR了。

关于初始化向量问题

前面讲到的几种模式中，CBC、CFB、OFB都用到了初始化向量IV，而CTR则使用了计数器，计数器的 nonce 部分和初始化向量IV是一样的，只是叫法不同而已。关于初始化向量IV，是一个随机比特序列，为了提高安全性，建议每次加密时都使用不同的值，这样的话，即使有两条相同的明文信息，加密后的密文也是不同的。但是，每一次发送端使用IV对明文加密后，接收端也需要使用同样的IV才能够解密，那么，发送端和接收端如何同步这个IV呢？关于这个问题，书中没有提到。于是，只好自己寻找解决方案。

最简单的方式可能就是，发送端每次发送信息时，将IV和加密后的密文一起发送给接收端。接收端收到信息后，就可以将收到的IV用于解密收到的密文了。而这种方式最明显的缺陷就是IV直接暴露给攻击者了，攻击者就可以利用IV发起攻击，比如使用CBC模式时，攻击者将IV进行比特反转，就可达到操纵明文的目的。攻击者将IV中的任意比特进行反转(1变0，0变1)，则解密后的明文分组中相应的比特也会被反转。

为了避免将IV直接暴露，那将IV进行加密后再发送呢？因为IV的长度和一个分组的长度是等长的，这就不需要考虑分组迭代的问题，即不需要考虑使用什么模式了，直接用密码算法进行加密即可。加密后，攻击者再想通过比特反转IV来操纵明文就困难多了。

密钥配送问题

对称密码中，由于加密和解密都使用同一个密钥，因此就必须向接收者配送密钥，这个问题就称为密钥配送问题。而解决密钥配送问题的方法有几种：

通过事先共享密钥来解决
通过密钥分配中心来解决
通过Diffie-Hellman密钥交换来解决
通过公钥密码来解决

通过事先共享密钥来解决

事先用安全的方式将密钥交给对方，就称为密钥的事先共享。这是密钥配送问题最简单的一种解决方法，但有其局限性。公司内部开发的应用产品，客户端和服务端都是自己开发的，事先共享密钥就很简单，服务端人员生成密钥后直接给到客户端的开发人员就可以了。但这种情况又会带来其他问题，比如密钥在客户端如何才能安全的保存。一般，密钥都是通过硬编码或存为文件的形式保存在客户端的，那么客户端应用一旦被反编译，就很容易窃取到密钥了。

而如果是开放性平台，像微博开放平台、微信开放平台等，要做到事先共享密钥就很有难度了。开发者在开放平台注册的应用，其密钥都是通过平台的管理端给到开发者的，也就是通过了网络，那就存在被窃听的风险了。

通过密钥分配中心来解决

当使用密钥分配中心时，需要通信的双方可以事先在密钥分配中心注册，然后密钥分配中心给每个注册方发送一个密钥，不同注册方的密钥是不同的。那么，当某个发送端需要向某个接收端发送消息时，通信流程如下：

发送端向密钥分配中心发起希望与接收端通信的请求；
密钥分配中心随机生成一个会话密钥，该会话密钥是供发送端和接收端在本次通信中使用的临时密钥，我们简称为 TempKey ；
密钥分配中心查询出发送端的密钥，即发送端注册时分配的密钥，我们简称为 SenderKey ；
密钥分配中心使用 SenderKey 对 TempKey 进行加密，加密后的密文称为 CipherTempKeyToSender ，并发送给发送端；
密钥分配中心用同样的方式查询出接收端的密钥，简称为 ReceiverKey ；
密钥分配中心再用 ReceiverKey 对 TempKey 进行加密，加密后的密文称为 CipherTempKeyToReceiver ，并发送给接收端；
发送端对来自密钥分配中心的 CipherTempKeyToSender ，用自己的密钥即 SenderKey 进行解密，得到 TempKey ；
发送端将要发送给接收端的消息用 TempKey 进行加密，然后发送给接收端；
接收端对来自密钥分配中心的 CipherTempKeyToReceiver ，用自己的密钥即 ReceiverKey 进行解密，也得到 TempKey ；
接收端收到发送端的密文后，用 TempKey 对密文进行解密；
通信完毕，发送端和接收端都删除 TempKey 。

这个通信过程还挺复杂的，总的来说就是，发送端和接收端通信时是使用密钥分配中心分配的临时密钥进行加密和解密的。这种方案，密钥分配中心的安全性就显得非常重要了。如果攻击者入侵了密钥分配中心，盗取到所有密钥，则后果很严重。

通过Diffie-Hellman密钥交换来解决

在Diffie-Hellman密钥交换中，进行加密通信的双方需要交换一些信息，而这些信息即便被窃听者窃听到也没有问题。根据所交换的信息，双方可以各自生成相同的密钥，而窃听者却无法生成相同的密钥。

虽然这种方法叫“密钥交换”，但实际上双方并没有真正交换密钥，而是通过计算生成出了一个相同的共享密钥。因此，这种方法也称为 Diffie-Hellman密钥协商 。支撑Diffie-Hellman密钥交换算法的是有限群的离散对数问题的复杂度。

通过公钥密码来解决

公钥密码类似于投币寄物柜。首先，将物品放入寄物柜中。然后，投入硬币并拔出钥匙，就可以将寄物柜关闭了。关闭后的寄物柜，没有钥匙是无法打开的。只要有硬币，任何人都可以关闭寄物柜，但寄物柜一旦被关闭，再怎么投币也无法打开。要打开寄物柜只能使用钥匙，而不是硬币。因此可以说，硬币是 关闭寄物柜的密钥 ，而钥匙是 打开寄物柜的密钥 。

在公钥密码中，加密和解密的密钥是不同的。只要拥有加密密钥，任何人都可以进行加密，但没有解密密钥是无法解密的。接收者事先将加密密钥发送给发送者，这个加密密钥即便被窃听者获取也没有问题。发送者使用加密密钥对通信内容进行加密并发送给接收者，而只有拥有解密密钥的人（即接收者本人）才能够进行解密。这样一来，就用不着将解密密钥配送给接收者了，也就是说，不存在密钥配送问题了。

公钥密码

公钥密码中，密钥分为加密密钥和解密密钥两种。加密密钥一般是公开的，因此也被称为公钥 (public key)。解密密钥则绝对不能公开，因此也称为私钥 (private key)。公钥和私钥是一一对应的，一对公钥和私钥统称为 密钥对 (key pair)。由公钥加密的密文，只有配对的私钥才能够解密。

使用公钥密码通信时，流程如下：
读《图解密码技术》(一): 密码
那么，密钥对是如何生成的呢？为什么用公钥加密的密文能用私钥解密呢？要理解公钥密码的原理，需要先理解一些数学上的问题，mod运算是基础。

公钥密码是基于数学上困难的问题来保证机密性的，比如利用质因数分解的困难度、mod运算下求离散对数的困难度、mod运算下求平方根的困难度，等等。现在使用最广泛的公钥密码算法RSA就是利用了大整数质因数分解问题的困难度。

数学原理

要理解RSA算法的原理，就要先理解一些mod运算方面的知识。mod运算，其实就是“除法求余数的运算”，比如：

27 mod 12 = 3 表示27除以12的余数等于3

加法和乘法都非常简单，比如：

(6 + 7) mod 12 = 13 mod 12 = 1
7 * 7 mod 12 = 49 mod 12 = 1

减法和除法则可以看成加法和乘法的逆运算，比如：

(7 + N) mod 12 = 0 7加上几除以12的余数为0？
7 * M mode 12 = 1 7乘以几除以12的余数为1？

这里，N 和 M 都要求大于等于 0 小于 12。N 还是很容易算出来的，答案是5。而 M 一下子就比较难算出来，可以用暴力破解把0~11都代入 M 计算一下结果，最终可以得到 M = 7。接着，看另一个算式：

N * M mod 12 = 1

如果没有 mod 12，那 N 和 M 就是互为倒数。此处的话，我们还要加上“在以12为模的世界中”这个条件。在一般的算术中，互为倒数可以写成：

N * 1/N = 1

那么，在以12为模的世界中，在0到11的数字中，是不是每一个数都存在相应的倒数呢？实际上，mod运算中“某个数是否存在倒数”这个问题，与RSA中“一个公钥是否存在相对应的私钥”这个问题是直接相关的。下表列出了结果：
读《图解密码技术》(一): 密码
存在倒数的只有1、5、7、11，这些数有怎样的性质呢？其实，在 mod 12 的世界中，存在倒数的数，它们和12之间的最大公约数都是1，也可以说是和12互质的数。那么，如果是在 mod 14 的世界中，存在倒数的则有1、3、5、9、11、13。

接着，看看乘方的mod运算又是怎样的。比如，现在要求 7^4 mod 12，最笨的方法就是将7^4直接算出结果，然后除以12求余。而快速的计算方法则是在计算的中间步骤求mod，如下：

7^4 mod 12 = 7*7*7*7 mod 12 = ((7*7 mod 12) (7*7 mod 12)) mod 12 = ((49 mod 12) (49 mod 12)) mod 12 = 1*1 mod 12 = 1

在中间步骤求mod，可以避免计算大整数的乘积。这种在计算过程中求mod来计算乘方的方法，也是RSA的加密和解密算法中所使用的方法。

接着，再看看对数，即乘方的逆运算。mod运算中的对数称为离散对数，比如：

7^N mod 13 = 8

这里N应该等于几呢？像下面这样依次尝试一遍，可以得到 N = 9：
读《图解密码技术》(一): 密码
当数字很大时，求离散对数就会非常困难，而且非常耗时。到现在也还没有发现能够快速求出离散对数的算法。也因此，有很多公钥算法都运用了离散对数。

RSA

RSA是现在使用最广泛的公钥密码算法，但RSA不只用于公钥密码，也用于数字签名。关于数字签名下一篇文章再讲。

在RSA中，明文、密钥和密文都是数字。RSA的加密过程可以用下列公式来表达，其中，Plaintext 指明文，Cipher 指密文：

Cipher = Plaintext^E mod N （RSA加密）

RSA的密文是对明文的数字的 E 次方求 mod N 的结果。换句话说，就是将明文和自己做 E 次乘法，然后将其结果除以 N 求余数，这个余数就是密文。因此，只要知道 E 和 N 这两个数，任何人都可以完成加密的运算。所以说，E 和 N 是RSA加密的密钥，也就是说，E 和 N 的组合就是密钥。另外，E 是加密(Encryption)的首字母，N 是数字(Number)的首字母。

RSA的解密和加密一样简单，可以用下面的公式来表达，其中，Plaintext 指明文，Cipher 指密文：

Plaintext = Cipher^D mod N （RSA解密）

对表示密文的数字的 D 次方求 mod N 就可以得到明文。换句话说，将密文和自己做 D 次乘法，再对其结果除以 N 求余数，就可以得到明文。这里的数字 N 和加密时的 N 是相同的。D 和 N 组合起来就是RSA的解密密钥，因此，D 和 N 的组合就是私钥。另外，D 是解密(Decryption)的首字母。

整理一下，RSA的加密和解密如下图：
读《图解密码技术》(一): 密码
由于 E 和 N 是公钥，D 和 N 是私钥，因此求 E、D 和 N 这三个数就是生成密钥对。密钥对的生成步骤如下：
1. 求N：N = p * q
其中，p、q 是需要事先准备的两个很大的质数。p 和 q 太小的话，密码会变得容易破译，但太大的话计算时间又会变得很长。一般来说，p 和 q 的长度都是512比特以上，N 的长度为1024以上。
2. 求L：L = lcm(p-1, q-1)
L 是仅在生成密钥对的过程中使用的数，它是 p-1 和 q-1 的最小公倍数。
3. 求E：1 < E < L && gcd(E, L) = 1
E 是一个比 1 大、比 L 小的数。此外，E 和 L 的最大公约数必须为 1，即 E 和 L 互质，这样可以保证一定存在解密时需要使用的数 D。
4. 求D：1 < D < L && E * D mod L = 1
D 也是是一个比 1 大、比 L 小的数，而且是由数 E 计算得到的。从 E * D mod L = 1 这条公式得知，要保证存在满足条件的 D，就需要保证 E 和 L 的最大公约数为 1。简单来说，E * D mod L = 1 保证了对密文进行解密时能够得到原来的明文。

公钥密码的问题

公钥密码虽然可以避免密钥配送问题，但也存在两个很大的问题：
1. 公钥密码的处理速度远远低于对称密码；
2. 公钥密码难以抵御中间人攻击。

如果用公钥密码去处理很长的消息，那么，公钥密码速度慢的缺点就会显露无疑。所以，一般，不会用公钥密码直接处理消息。而是和对称密码相结合，采用混合密码系统。关于混合密码系统，下面再说。

对于第二个问题，是因为公钥是公开的，任何人都可以获取，也包括攻击者。所谓中间人攻击，就是攻击者混入发送者和接收者中间，对发送者伪装成接收者，对接收者伪装成发送者的攻击方式。如下图所示：
读《图解密码技术》(一): 密码
在这种情况下，就没有机密性可言了，因为发送者用来加密的其实是攻击者的公钥，攻击者拦截到信息后就可以用自己的私钥解密出来，再用之前拦截到的接收者的公钥对伪造的消息加密后发给接收者。

仅靠公钥密码本身，是无法防御中间人攻击的。要防御中间人攻击，还需要一种手段来确认所收到的公钥是否真的属于接收者，这种手段称为认证。针对上面的情况，我们可以使用公钥的证书。关于认证和证书，下一篇文章再讲。

混合密码系统

混合密码系统是将对称密码和公钥密码的优势相结合的方法，加密消息使用快速的对称密码，而用公钥密码来加密对称密码的密钥。因为对称密码的密钥一般比消息本身要短，因此公钥密码速度慢的问题就可以忽略了。另外，对称密码使用的密钥是临时生成的会话密钥。混合密码系统的加密过程如下图：
读《图解密码技术》(一): 密码
从图中就可得知：
1. 会话密钥是随机生成的，因此，每次加密的会话密钥都会不同；
2. 混合密码系统的明文是用对称密码加密的，而加密使用的密钥就是上一步生成的会话密钥；
3. 用公钥密码对会话密钥进行加密，形成了加密后的会话密钥；
4. 将加密后的会话密钥和加密后的消息组合在一起，就是混合密码系统的密文。