在之前的TODOLIST提到过两本关于密码学的书籍《漫画密码学》以及《图解密码技术》，其实在寒假开始之前就读完了，但是因为拖延症一直没有抽出时间来整理。这次，正好趁着刚刚开学没有太多事情，再回顾一下与密码学学相关的知识。

密码学家的工具箱

《图解密码技术》中给出了密码学家的工具箱，包括六种技术：

1. 对称密码（symmetric cryptography）
2. 公钥密码（public-key cryptography）
3. 单向散列函数（one-way hash function）
4. 消息认证码（message authentication code）
5. 数字签名（digital signature）
6. 伪随机数生成器（pseudo random number generator）

接下来会对这6中密码技术一一讲解。但是在此之前，我们需要理解几条密码与信息安全常识。

密码与信息安全常识

• 不要使用保密的密码算法。因为密码算法的秘密迟早会公诸于世（有历史证明），另外开发高强度的密码算法是非常困难的。而现在世界上公开的被认为强度较高的密码算法，几乎都是经过密码破译者长期破解未果而存活下来的，如果你认为自己开发的密码系统更强，那只能说你可能高估自己的能力了。试图通过对密码算法本身进行保密来确保安全性的行为，称为隐蔽式安全（security by obscurity），这种行为是危险且愚蠢的。

• 使用低强度的密码比不进行任何加密更危险。这是因为用户容易通过“密码”一词获得一种”错误的安全感“，这通常会导致用户在处理一些机密信息的时候麻痹大意。

• 任何密码总有一天会被破解。无论使用任何密码算法所生成的密文，只要将所有可能都密钥全部尝试一遍，总有一天可以破译出来。但是严格来说，绝对不会被破解的密码算法是存在的，这种算法称为一次性密码本，但它并不是一种现实可用的算法。

对称密码

对称密码又称共享密钥密码，它使用相同的密钥进行加密和解密。

DES

DES，即Data Encryption Standard，是1977年提出的一种对称密码。但是现在已经可以在短时间内（小于24小时）对DES的密文进行破解，因此除了用它来解密以前的密文外，将来我们不应该再使用DES了。

DES是以64bit为一个单位来进行加密的对称密码算法，它将64bit的明文通过64bit的密钥（实际为56bit，每隔7bit会设置一个用于错误检查的bit）加密成64bit的密文。

这个64bit的单位称为分组，如果待加密的明文很长，就需要对明文进行迭代（反复），而迭代的具体方式就称为模式。下一小节，我们将着重讲解模式。

DES的是一种16轮循环的Feistel网络，其中Feistel网络的一轮的计算流程如下；

在一个Festel网络中，每一轮都要使用不同的子密钥，并且每一轮结束后，都需要将左侧和右侧数据对调之后，才能作为下一轮的输入。

从XOR的运算性质可知，将每一轮的输出重新作为输入，总会还原出最初的输入（右侧数据、轮函数、子密钥不变，意味着和左侧数据进行XOR的数据也不变）。

下面是Feistel网络的一些性质：

1. Feistel网络的轮数可以任意增加。
2. 加密是无论使用任何函数作为轮函数都可以正确解密，也就是说，轮函数可以无需考虑解密的问题。
3. 加密和解密都可以使用相同的结构实现，只需要把子密钥使用的顺序颠倒。

因为DES已经可以在现实的时间内被暴力破解，所以三重DES，即triple-DES被开发出来，用来加强DES的强度。我们需要的知道的是，三种DES并不是连续进行三次DES加密，而是加密-解密-加密的过程。

AES

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

不同与DES使用Feistel网络作为其基本结构，Rijndael使用SPN结构，并且也是又多个轮组成的，具体的算法就不在这里详述了。

到目前为止还没有出现针对Rijndael的有效攻击。所以，AES将是我们今后对称加密的首选。

分组密码的模式

上面介绍的DES和AES都属于分组密码，如果需要对很长的密文进行加密，就需要对分组密码进行迭代，迭代方法称为分组密码的模式。

模式有很多种，分组密码主要涉及以下5种：

1. ECB模式：Electronic CodeBook mode（电子密码本模式）
2. CBC模式：Cipher Block Chaining mode（密码分组链接模式）
3. CFB模式：Cipher FeedBack mode（密文反馈模式）
4. OFB模式：Output FeedBack mode（输出反馈模式）
5. CTR模式：Counter mode（计数器模式）

ECB模式（不应使用）

当最后一个明文分组小于分组长度时，需要使用一些特定的数据来进行填充（padding）。

在ECB模式中，明文分组和密文分组时一一对应的关系，所以只要观察一下密文，就可以知道明文中存在怎样的重复组合，并且可以以此为线索来破译密码。

另外，攻击者无需破译密文就可以操纵明文，因为他只需要改变密文分组的顺序（或者删除、复制某些密文分组），那么相应的明文分组的组合也会被改变。比如某银行的转账请求，本来是A账户向B账户转账1亿元，那么攻击者在不知道明文的情况下，可能修改为B账户向A账户转账1亿元。

CBC模式（推荐使用）

在CBC模式中，首先将明文分组与前一个密文分组进行XOR运算，然后在进行加密运算。当加密第一个明文分组时，由于密文分组不存在，所以需要事先准备一个比特序列，称为初始化向量（initialization vector）。

使用了CBC模式后，即便明文分组1和明文分组2是相等的，密文分组1和密文分组2的值也不一定相等。这就解决了ECB模式中的缺陷。

在CBC模式中，密文分组和明文分组不是一一对应的关系。如果要生成密文分组3，则必须要凑齐明文分组1,2,3才行。另外如果密文分组2损坏，则会导致明文分组2和3都无法复原。

CFB模式（推荐用CTR代替）

在CFB模式中，前一个密文分组会被送回到密码算法的输入端。

在CFB模式中，并没有对明文分组直接进行加密，从明文分组到密文分组，只有一个XOR运算。

对于CFB模式，可以进行重放攻击（replay attack）。假如Alice跟Bob通信，第一次发送的4个密文分组被Mallory截获并保存了最后3个分组，第二天，Alice又使用同样的密钥向Bob发送了4个密文分组，而这次Mallory将这次密文分组的后3个替换为昨天截获的分组。那么Bob收到密文后解密，发现第二个明文分组出错，其他明文分组正常。这时候，Bob可能无法判断明文的可靠性，因为Bob不知道第二个分组是通信错误还是人为攻击。

OFB模式（推荐用CTR代替）

在OFB模式中，密码算法的输出会反馈到密码算法的输入中。

OFB和CFB模式的区别仅在于密码算法的输入源（反馈）不同。CFB中反馈为上一个密文分组，而OFB中反馈为密码算法的前一个输出。

在OFB模式中，和明文XOR所需的比特序列（钥匙流）可以事先通过密码算法生成，这样在加密或者解密的过程中，只需要进行XOR运算就行了，而XOR和运算速度是很快的。换个角度讲，生成密钥流的操作可以和进行XOR的操作并行。

CTR模式（推荐使用）

CTR模式是一种通过将逐次累加的计数器进行加密来生成密钥流的流密码。

每次加密都会生成一个不同的值nonce来作为计数器的初始值。当分组长度为128bit，即16字节时，前8个字节位nonce，这个值在每次加密时必须是不同的。后8个字节为分组序号，会逐次累加。

CTR模式和OFB模式一样，都属于流密码。

公钥密码

公钥密码又称为非对称密码（asymmetric cryptography），使用公钥加密，用私钥解密，或者使用私钥加密，使用公钥解密。

在对称密码中，由于加密和解密的密钥是相同，因此必须向接收者配送密钥。这一问题称为密钥配送问题。

而使用公钥密码，则无需向接收者配送用于解密的密钥，这样就解决了密钥配送问题。

RSA

RSA是一种公钥密码算法，它的名字是由它的三位开发者姓氏首字母组成。RSA可以被用于公钥密码和数字签名。

RSA的加密和解密过程如下；

1
2

密文 = 明文 E mod N    （RSA加密，明文的E次方求mod N 的结果）
明文 = 密文 D mod N    （RSA解密，密文的D次方求mod N 的结果）

加密需要的E和N两个数字，即为公钥(E, N)，其中E是Encryption的缩写。解密需要的D和N两个数组，即为私钥(D, N)，其中D是Decryption的缩写。公钥和私钥合称为密钥对。

当然，D和E并非所有的数字都可以，他们两个有紧密的联系，下面来看如何生成密钥对。

• 求N

用伪随机数生成器（Pseudo Random Number Generator）来生成两个很大的质数p和q（512bit）。

1

N = p*q

• 求L（仅在生成密钥对的过程中使用）

L是q-1和p-1的最小公倍数，即least common multiple。

1

L = lcm（p-1, q- 1)

• 求E

E是一个比1大，比L小的数，此外，E和L的最大公约数（greatest common divisor）为1，即E和L互质。

1

1 < E < L，且gcd(E,L) = 1

• 求D

D是由E计算得到的，D、E、L之间必须具备以下关系：

1

1 < D < L，且 E*D mod L = 1

这样N，E，D都求出来了，密钥对自然也就得到了。其中公钥(E, N)是可以任意公开的，私钥(D,N)必须妥善保管。

下图形象地展示了密钥对的生成过程：

对RSA的攻击

关于RSA，我们还需要明白以下几点：

1. 公钥(E,N)和加密解密算法是公开的，任何人都知道。
2. 虽然私钥(D,N)是由公钥(E,N)计算而来，但是却不能由公钥算出私钥。
3. 质数p和q不能被RSA攻击者知道，把p和q交给密码破译者与把私钥交给密码破译者是等价的。

对N进行质因数分解

p和q是破译密码的一个关键点，而N作为公钥的一部分是公开的，且N = p*q。所以，由N求p和q只能通过将N进行质因数分解来完成。我们可以说：

只要发现了对于大整数进行质因数分解的高效算法，RSA就能够被破译。

然而，我们目前还没有这样的算法出现，而且也尚未证明质因数分解是否真的是非常困难的问题，甚至也不知道是否存在一种分解质因数的简单方法。

中间人攻击

除了通过分解N来进行攻击之外，还有一种中间人攻击（man-in-the-middle attack）的攻击方法。

比如Alice想向Bob发送一封情书，于是先发邮件跟Bob要他的公钥，在Bob将自己公钥发送给Alice的过程中，中间人Mallory截获了邮件，并且将Bob的公钥替换为了自己的公钥，并且偷偷保存了Bob的公钥。

Alice在收到Bob的公钥后（其实是Mallory的公钥），将”To Bob: I love you. From Alice”通过公钥加密，并发送给Bob，Mallory再次截获邮件，用自己的私钥解密（因为明文使用自己公钥加密的），看到了”To Bob: I love you. From Alice”。

这时，Mallory冒充Alice重新写了一封邮件”To Bob: I hate you. From Alice”，并用Bob的公钥加密后发送给Bob。

Bob收到邮件后用自己私钥解密，看到””To Bob: I hate you. From Alice”，伤心极了。

公钥密码的问题

公钥密码虽然解决了私钥密码存在的密码配送问题，但是依旧有两个很大的问题；

1. 公钥密码的处理速度远远低于对称密码
2. 公钥密码难以抵御中间人攻击

要解决第一个问题，可以使用混合密码系统，要解决第二个问题，则需要对公钥进行认证。

混合密码系统

混合密码系统，即hybrid cryptosystem，用对称密码来加密明文，用公钥密码来加密对称密码中使用的密钥。

混合密码系统使用了伪随机数生成器、私钥密码、公钥密码这3种技术。其加密和解密过程如下；

单向散列函数

单向散列函数可以用来获取消息的指纹，使用它可以确保信息的完整性（integrity），达到防篡改的功效。

单向散列函数有一个输入和一个输出，输入成为消息（message），输出称为散列值（hash value），摘要（digest），或者指纹（fingerprint）。

单向散列函数的性质

1. 根据任意长度的消息计算出固定长度的散列值。比如SHA-1单向散列函数为例，其计算出的散列值永远是160bit（20字节）。
2. 能够快速计算出散列值。
3. 消息不同，散列值也不同。消息中哪怕只有1bit的不同，也必须有很高的概率产生不同的散列值。
4. 具备单向性，即无法通过散列值反算出消息。（注意，单向散列函数并不是一种加密函数，因为无法通过解密将散列值还原为原来的消息。

抗碰撞性

两个不同的消息产生同一个散列值的情况称为碰撞（collision）。难以发现碰撞的性质称为抗碰撞性（collision resistance）。

单向散列函数必须确保要找到和该条消息具有相同散列值的另外一条消息是非常困难的，这一性质称为弱抗碰撞性。

与弱抗碰撞性相对，要找到散列值相同的两条不同的消息是非常困难的，这一性质称为强抗碰撞性。

密码技术中所使用的单向散列函数，不仅需要有弱抗碰撞性，还需要具有强抗碰撞性。

单向散列函数的实例

MD4和MD5，均能够产生128bit（16字节）的散列值。由于现在已经能够产生具有相同散列值的亮条不同的消息，因此它们已经不安全了。

其中MD是消息摘要Message Digest的缩写。

SHA-1、SHA-256、SHA-384、SHA-512都是由NIST设计的单向散列函数，它们的散列值长度分别为160bit，256bit，384bit、512bit。

单向单列函数无法解决的问题

单向散列函数能够辨别出“篡改”，但是无法辨别出“伪装”。

当我们不仅需要验证文件的完整性，同时还有确认这个文件是否真的属于某个发送者时，仅靠完整性检查时不够的，我们还需要认证。

用于认证的技术包括消息验证码和数字签名。消息认证码能够向通信对象保证消息没有被篡改，而数字签名不仅能够向通信对象保证消息没有被篡改，还能够向所有的第三方作出这样的保证。

消息认证码

消息认证码，即Message authenticatioin code，简称MAC，是一种确认完整性，并且对通信对象进行认证的技术。

消息认证码的输入包括任意长度的消息和一个发送者与接受者之间共享的密钥，它可以输出固定长度的数据，这个数据称为MAC值。在使用消息认证码时，消息会和MAC值一起发送，然后消息接收者根据接收到的消息以及共享密钥计算出MAC值，并与接收到的MAC值进行比较。若相同，则通过认证。

我们可以这样认为：消息认证码是一种与共享密钥相关联的单向散列函数，正式因为密钥的存在，才使得除了通信双方以外的冒充者无法通过认证。

消息认证码的实现

消息认证码可以使用单向散列函数来实现（HMAC），也可是使用DES、AES之类的分组密码来实现。具体的实现方法就不在这里详述。

消息认证码的问题

密码配送

消息认证码需要发送者和接收者之间共享密钥，这个共享密钥不能被外人获取。

这样一来，就像对称密码中共享密钥一样，就遇到了密钥配送问题，但是我们可以使用公钥密码来解决这个问题。

重放攻击

另外一个问题是，消息认证码可能遭遇到重放攻击（replay attack）。

比如Alice银行向Bob银行发起了一笔转账请求：”向Mallory账户转账100万”。Mallory保存了这个请求的消息和MAC值，并且连续向Bob银行发送100次该请求，Bob银行每收到消息，就生成MAC值，与收到的MAC比较，总是相等，所以都会通过认证。最终Mallory的账户从100万变成了一亿。

对第三方证明&防止否认

假如Alice借给了Bob 1亿元，但是Bob却死不承认。于是Alice拿出Bob发给它的借条消息和MAC值，以及Alice和Bob共享的密钥，提供给第三方验证者Victor来帮忙证明消息确实是Bob发送的。

但是纵然MAC值是正确的，Victor也无法确定消息发送者是Bob，因为Alice也可以发出这条消息（万一是Alice捏造的消息呢）。

Bob可以向Victor声称”我没有发送过这条消息“，这样的行为就称为”否认（repudiation）。

所以，消息认证码无法对第三方提供证明，也无法防止否认（nonrepudiation）。

而数字签名可以解决这个问题。

数字签名

数字签名就是通过将公钥密码“反过来”使用而实现的，在公钥密码机制中，公钥用来加密，私钥用来解密。但是在数字签名时，发送者通过自己的私钥生成消息签名（表示自己认可该消息），而接收者以及第三方验证者可以通过公钥来验证数字签名。

其中，用私钥加密相当于生成签名，用公钥解密相当于验证签名。由于公钥时公开的，所以任何人都可以使用公钥来验证签名。

数字签名的方法

下面来介绍两种生成和验证数字签名的方法。

• 直接对消息签名

• 对消息的散列值签名

如何防止否认

消息认证码无法放置否认，那为什么数字签名可以防止否认呢？

其实，数字签名是利用了“没有私钥的人事实上无法生成签名”这一性质来实现的，这意味着，只有持有该私钥的人，才能生成该签名。因此，发送者就无法声称“这个签名不是我的”了。

数字签名无法解决的问题

数字签名既可以识别出篡改和伪装，还可以防止否认。也就是说，我们同时实现了确认消息的完整性、进行认证和防止否认。

然而，要正确使用数字签名，有一个重要前提，那就是用于验证签名的公钥必须属于真正的发送者。

为了能够确认自己得到的公钥是否合法，我们需要使用公钥证书，所谓公钥证书，就是将公钥当作一条消息，由一个可信的第三方对其签名的结果。

证书

公钥证书（Public-Key Certificate, PKC），简称证书（certificate），除了包含公钥之外，还记有姓名、组织、邮箱、地址等个人信息，以及认证机构（Certification Authority, CA)所施加的数字签名。

认证机构，就是能够认定“公钥确实属于此人”并能够生成数字签名的个人或者组织。比如世界著名的Symantec以及Comodo公司。

证书的应用场景

下图展示了Alice通过认证机构（Trent）获取Bob的公钥，并且将消息经过Bob公钥加密并传递给Bob的过程。

证书标准规范X.509

证书是由认证机构颁发的，如果证书的格式千奇百怪就很不方便。鱼人，X.509规范便应运而生。

X.509规范大体包含以下3部分内容：

1. 签名前的证书：签名对象的信息
2. 数字签名算法
3. 数字签名

我们可以从浏览器中导出证书，保存成base64格式，大致如下：

公钥基础设施

仅指定证书的规范还不足以支持公钥的实际运用，我们还需要其他很多的规范，比如证书应该由谁来颁发，如何颁发，私钥泄露是应该如何作废证书等。这一系列的工作将交由公钥基础设施（Public-Key Infrastructre, PKI）来制定。

上一小节我们提到的X.509这样的规范就是PKI的一种。关于PKI更详细的内容，这里就不详述。

基于口令的密码

基于口令的密码（Password Based Encryption, PBE），顾名思义，就是一种根据口令来生成密钥，并用该密钥进行加密的方法。

在PBE中，我们通过口令和盐生成KEK，再用这个密钥来生成CEK，最后使用CEK来加密消息。

PBE的加密和解密

使用PBE加密的过程如下：

使用PBE解密的过程如下：

盐的作用

盐是由伪随机数生成器生成的随机数。在生成KEK时，盐和口令一起被输入单向散列函数。

盐是用来防御字典攻击的，在生成KEK时加盐，盐的长度越大，候选KEK的数量也就越大，暴力破解也就越难。

随机数

随机数是不可预测性（unpredictability）的源泉。回忆上面讲到的知识，以下场景可能会用到随机数：

1. 生成密钥：用于对称密码和消息认证码
2. 生成密钥对：用于公钥密码和数字签名
3. 生成初始化向量：用于分组密码的CBC、CFB、OFB模式
4. 生成nonce：用于分组密码的CTR模式
5. 生成盐：用于基于口令的密码（PBE）

随机数的性质

我们将随机数的性质分为3类：

1. 随机性：不存在统计学偏差，是完全杂乱的序列（弱伪随机数）
2. 不可预测性：不能从过去的数列推测下一个出现的数（强伪随机数）
3. 不可重现性：除非将数列本身保存下来，否则不能重现相同的数列（真随机数）

上面的性质从上到下，越来越严格。在密码技术中使用的随机数，仅具有随机性是远远不够的，至少还要具备不可预测性。

另外，我们需要明白，仅靠软件是无法生成真随机数的，因为运行软件的计算机本身仅具备有限的内部状态。如果要生成具备不可重现性的随机数列，只能从不可重现的物理现象中获取信息，比如周围的温度和声音的变化，用户鼠标移动的位置信息等。

伪随机数生成器

可以生成伪随机数的软件称为伪随机数生成器（Pseudo Random Number Generator，PRNG）。

伪随机数生成器需要外部输入一个种子（seed）来生成伪随机数列。伪随机数种子是一串随机的比特序列，根据种子就可以生成专属于自己的伪随机数列，因此，种子需要自己保密。

具体的伪随机数生成方法有很多种，比如线性同余法（不能用于密码技术）、单向散列函数法、密码法等，这里就不详述。

最后

以上就是密码技术的基础部分，我们可以通过PGP（Pretty Good Privacy）这个将密码技术完美结合到一起的软件来进行实践。

除此之外，关于密码技术的应用还有待继续学习，比如SSL/TLS（Secure Socket Layer/Transport Layer Security）的相关知识。

总之，只有完美的密码，没有完美的人。在安全问题中，人就是一个特点巨大的弱点。所以，提高安全意识才是王道。