2.4　典型对称密钥密码系统

本节将分别介绍对称密钥密码系统的DES、AES和RC4。

2.4.1　数据加密标准（DES）

数据加密标准（Data Encrytion Standard，DES）是美国国家标准局于1977年公布的由IBM公司研制的一种密码系统，它被批准作为非机要部门的数据加密标准，在民用领域应用广泛。DES是一种公认的安全性较强的对称密钥密码系统。自问世以来，一直是密码研究领域的热点，许多科学家对其进行了研究和破译，但至今没有公开文献表明DES已经被彻底破解。

DES是一种分组密码，对二进制数据加密，明文分组的长度为64位，相应产生的密文分组也是64位。

DES密码系统使用64位密钥，但64位中由用户决定的只有56位。DES密钥的产生通常是由用户提供由7个英文字母组成的字符串，英文字母被逐个按ASCII码转化为二进制数，形成总长56位的二进制字符串，字符串的每7位补充1位作为奇偶校验，从而生成总长64位的密钥。

DES密码算法的加密流程如图2-11所示。

总体上看，加密流程可以划分为初始置换IP、子密钥的生成、乘积变换、逆初始置换IP-1四个子步骤。

1.初始置换IP

初始置换（Initial Permuation，IP）是DES加密流程中的第一步，所起的作用是对输入的64位明文进行位置调整，调整将依据初始置换表进行。

DES的初始置换表如图2-12所示。依照初始置换表，明文分组中的第58位，在经过置换后将作为第1位输出；明文分组中的第50位，在经过置换后将作为第2位输出；明文分组中的第7位，在经过置换后将作为第64位输出，以此类推。

经过初始置换产生的64位数据将被划分为两半，其中左边的32位数据块以L0表示，右边的32位数据块以R0表示。

2.子密钥的生成

由64位的密钥生成16个48位的子密钥是DES算法中的重要一步。在子密钥的生成过程中，主要涉及到交换选择1（Permuted Choice 1，PC-1）、交换选择2（Permuted Choice 2，PC-2）及循环左移三种操作。子密钥的生成过程如图2-13所示。

PC-1主要完成两项工作。首先，接收64位密钥并将密钥中作为奇偶校验的8位去除。其次，将56位密钥的顺序打乱，划分为长度相同的两部分，其中一部分作为C0，另外一部分作为D0。C0和D0的组成结构如图2-14和图2-15所示。

以C0为例，输入密钥的第57位作为C0的第1位，输入密钥的第49位作为C0的第2位，以此类推。

循环左移也是子密钥生成过程中的一项重要操作。子密钥生成一共需要迭代16次，每一轮迭代的左移位数在1和2之间变化。在图2-13中循环左移以LSi表示，其中i代表迭代的轮数，如LS1表示第1轮迭代，LS2表示第2轮迭代。每次迭代的循环左移位数如图2-16所示，例如，第1轮和第2轮迭代的左移位数都是1，第3轮迭代的左移位数为2。

在第i轮迭代时，Ci-1和Di-1分别循环左移一定的位数产生Ci和Di。Ci和Di执行合并操作，Ci中的28位在前，Di中的28位在后，合并结果作为PC-2的输入。

PC-2从56位的输入中选择48位产生子密钥。PC-2的选择矩阵如图2-17所示。

第i轮迭代时，Ci和Di合并结果经由PC-2产生子密钥Ki。16轮的迭代将依次产生K1、K2、K3等16个子密钥。

3.乘积变换

乘积变换是DES算法的核心组成部分。乘积变换包含16轮迭代，每一轮迭代使用一个子密钥。乘积变换的输入为64位，在每一轮变换中，64位数据被对半划分为左半部分和右半部分，分别进行处理。

图2-18显示了第一轮乘积变换的基本框图。L0、R0分别代表明文数据的左32位和右32位，使用的密钥K1是在子密钥生成过程中产生的第一个子密钥，输出的L1和R1是第一轮的计算结果。

其他各轮的计算流程与第一轮相同，以i表示轮数，则第i轮的输出Li、Ri与该轮的输入Li-1、Ri-1及Ki之间具有如下关系：

Li=Ri-1；

Ri=Li-1⊕F(Ri-1,Ki)；

其中，函数F被称为加密函数，是DES算法的关键。加密函数的工作流程如图2-19所示，主要包括选择扩展运算E、选择压缩运算S、置换运算P等三种运算，以下分别介绍。

（1）选择扩展运算E

选择扩展运算E的功能是将输入的32位扩展为48位。选择扩展运算E依据选择矩阵进行，选择矩阵如图2-20所示。从选择矩阵可以看出，扩散运算将使50%的输入比特位在输出时出现两次。例如，输入的第1位将作为输出的第2位和第48位在输出时出现两次。选择矩阵通过对输入的巧妙重复实现了位数的扩展。

第i轮乘积变换，通过扩展运算将输入的Ri-1扩展为48位后，与48位的Ki异或，得到48位的输出。

（2）选择压缩运算S

选择压缩运算S把异或操作的48位结果划分为8组，每组6位。进而将每组的6位输入一个S盒，获得长度为4位的输出。S盒共有8个，互不相同，以S1至S8标识，8个S盒的输出连在一起可以得到32位的输出。图2-21至图2-28分别是S1盒至S8盒的组成。

S盒的具体工作过程如下：

1.S盒6位输入的第1位和第6位构成一个2位二进制数，将其转化为十进制数，对应于S盒中的某一行；

2.S盒6位输入的第2、3、4、5位构成一个4位二进制数，将其转化为十进制数，对应于S盒中的某一列；

3.通过前两步确定的行和列在S盒中定位一个十进制数，该数的值域为[0,15]，将其转换为4位的二进制数作为输出。

举例来看，假若S1盒的输入为110111，输入的第1位和第6位数字组成二进制数11，对应于十进制数3，输入的中间4位数字组成二进制数1011，对应于十进制数11。S1盒中第3行第11列对应的数字是14，将14转化为二进制形式，将输出1110。

（3）置换运算P

置换运算P接收32位的输入，按照置换矩阵将输入打乱后，产生32位的输出。置换矩阵如图2-29所示。按照置换矩阵，输入的第16位将作为第1位输出，输入的第7位将作为第2位输出，以此类推。

4.逆初始置换IP-1

逆初始置换（Inverse Initial Permutation，IP-1）是初始置换的逆运算，两者的工作流程相同。如果将64位的一组明文输入初始置换IP，再将得到的结果输入逆初始置换IP-1，明文将被恢复。逆初始置换接收乘积变换的结果，打乱其排列顺序，得到最终的密文。逆初始置换表如图2-30所示。

按照DES加密算法的工作流程，输入的64位明文分组经过初始置换IP以后，在16个48位子密钥的控制下进行16轮迭代，最终通过逆初始置换IP-1得到64位的密文分组。

DES加密算法的核心功能是扰乱输入，从安全性的角度看，恢复加密算法所做的扰乱操作越困难越好。此外，DES加密算法能够表现出良好的雪崩效应，当输入中的某一位发生变化时，输出中的很多位都会出现变化，这使得针对DES进行密码分析非常困难。

5.DES的解密运算

DES的解密与加密使用的是相同算法，仅仅在子密钥的使用次序上存在差别。如果加密的乘积变换过程中依次使用K1、K2、K3、…、K16作为子密钥，那么在解密时将64位的密文输入初始置换IP后，乘积变换的各轮迭代中将依次使用K16、K15、K14、…、K1作为子密钥，完成迭代并将结果输入逆初始置换IP-1后可以恢复64位的明文。

6.DES的安全性

DES作为一种对称密钥密码系统，系统的安全性主要取决于密钥的安全性。一旦密钥泄露，则系统毫无安全可言。如何将密钥安全、可靠地分配给通信双方，在网络通信条件下更为复杂，包括密钥产生、分配、存储、销毁等多方面的问题，统称为密钥管理。密钥管理是影响DES等对称密钥密码系统安全的关键因素，缺乏严密的密钥管理，即使密码算法再好，也很难保证系统的安全性。

由于S盒是DES系统的核心部件，而且其核心思想一直没有公布，一些人怀疑DES的设计者可能在S盒中留有陷门，通过特定的方法可以轻易破解他人的密文，但是这种想法一直没有被证实。

DES系统目前最明显的一个安全问题是采用的密钥为56位，即密钥空间中只有256个密钥。随着计算机处理能力不断增强，短密钥很难抵御穷举攻击，直接影响到算法的安全强度。

1997年1月28日，美国RSA数据安全公司在Internet上开展了一项名为“秘密密钥挑战（Secret key Challenge）”的竞赛，悬赏一万美元破解一段DES密文。RSA发起此次活动旨在测试DES算法的安全强度。美国科罗拉多州的程序员Rocke Verser设计了一个通过互联网分段运行的密钥搜索程序，采用穷举密钥的方式对DES进行破解。搜索行动被称为DESCHALL，成千上万的志愿者加入到计划中，每个加入的志愿者会被分配一部分密钥空间进行测试。破解活动从1997年3月13日开始，在1997年6月17日，也就是破解活动的第96天，美国盐湖城一个公司职员Michael Sanders成功地找到了密钥，解密出了明文：“The unknown Message is：Strong cryptography makes the world a safer place（高强度的密码技术使世界更安全）”。此次破解一方面说明DES算法绝非坚不可摧，另一方面也显示了互联网上分布式计算的强大能力。

1998年电子新领域基金会（Electronic Frontier Foundation，EFF）为了告诫政府DES的保密性只是在一定范围内，他们花费25万美元制造了一台专用于暴力破解DES算法的计算机，这台计算机被命名为DES深层破解（Deep Crack）。1998年7月13日早上9点，计算机开始破解一段DES密文，在7月15日下午5点成功找到DES密钥，一共只花费了56小时。电子新领域基金会进一步改进了计算机的设计，1999年，EFF用22小时15分就完成了一段DES密文的破解工作。以今天的计算机的运算能力，破解DES密文更容易。

目前，对于DES算法都是通过穷举密钥的方式破解的，还没有发现这种算法在设计上的破绽。

7.3DES算法

在DES的基础上，研究人员在1985年提出了3DES算法，增加了密钥长度。3DES算法在1999年被加入到DES系统中。

3DES算法使用3个密钥，并执行3次DES运算。3DES遵循“加密—解密—加密”的工作流程，3DES的加密过程可以表示为：

c=E(k3,D(k2,E(k1,m)))

其中，m表示明文，c表示密文。E(k,X)表示在密钥k的控制下，使用DES加密算法加密信息内容X。D(k,X)表示在密钥k的控制下，使用DES解密算法解密信息内容X。

3DES的解密运算与加密运算的主体相同，只是密钥的使用顺序存在差异。在加密时如果依次使用k1、k2和k3作为密钥，则解密时将依次使用k3、k2和k1进行解密。解密过程可以表示为：

m=D(k1,E(k2,D(k3,c)))

DES的加密算法和解密算法相同，3DES算法在加密的第二步采用DES解密算法的主要目的是确保3DES能够支持DES，以往使用DES加密的信息也可以通过3DES解密。例如，密文c是明文m在密钥k1的控制下通过DES算法产生的，即：

c=E(k1,m)

密文c可以使用3DES解密，每一步都使用相同的密钥k1即可。具体流程为，

D(k1,E(k1,D(k1,c)))=D(k1,E(k1,m))=D(k1,c)=m

由于使用了3个密钥，3DES的密钥长度为192位，其中去除校验位的有效密钥长度为168位，如此长度的密钥使得穷举破解非常困难。

3DES算法的缺点是执行速度较慢，因为无论采用3DES算法进行加密还是解密，都需要执行3遍DES算法，因此，一个明文分组通过3DES加密需要的时间是使用DES算法加密所需时间的3倍。

2.4.2　高级数据加密标准（AES）

因为DES安全性不足，3DES效率低、小分组导致的安全性不足等问题，l997年4月美国国家标准与技术研究院（NIST）公开征集高级加密标准（Advanced Encryption Standard,AES）算法，并成立了AES工作组。NIST指定AES必须是分组大小为128比特的分组密码，支持密钥长度为128、192和256比特。经过多轮评估、测试，NIST于2000年10月2日正式宣布选中比利时密码学家Joan Daemen和Vincent Rijmen提出的密码算法Rijndael作为AES算法，并在2002年5月26日成为正式标准。因此，AES算法又称为Rijndael算法[1]。

Rijndael算法采用替换/转换网络，每一轮包含三层：

（1）线性混合层：通过列混合变换和行移位变换确保多轮密码变换之后密码的整体混乱和高度扩散。

（2）非线性层：字节替换，由16个S-盒并置而成，主要作用是字节内部混淆。

（3）轮密钥加层：简单地将轮（子）密钥矩阵按位异或到中间状态矩阵上。

S-盒选取的是有限域GF（28）中的乘法逆运算加仿射变换，它的差分均匀性和线性偏差都达到最佳。下面对有限域GF做一个简单说明。

1.有限域和有限环

由不可约多项式m(x)=x8+x4+x3+x+1定义的有限域GF（28）：其中的元素可以表示为一个8比特的字节b：b7b6b5b4b3b2b1b0，也可以表示为多项式：b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+bx+b0，其中b7~b0为0或1。

其中的加法定义：两个多项式的和是对应系数模2和的多项式。如：（x6+x4+x2+x+1）+（x7+x+1）=x7+x6+x4+x2；两个字节的和是二进制位进行异或的结果。为简单起见，我们用十六进制数表示一个8比特的字节，则与上面多项式运算对应的表示为：‘57’+‘83’=‘D4’。

其中的乘法定义：两个多项式的乘法是两多项式的乘积再对不可约多项式m(X)取模：如‘57’ב83’=‘C1’，对应的多项式运算为：

第一步：（x6+x4+x2+x+1）×（x7+x+1）=x13+x11+b5x5+b4x4+b3x3+b2x2+b1x+b0；

第二步：（x13+x11+b5x5+b4x4+b3x3+b2x2+b1x+b0）mod (x8+x4+x3cx+1)=x7+x6+1。

如果a(x)×b(x)mod m(x)=1，则称b(x)为a(x)的逆元。

由上面的乘法定义，x与a(x)的乘法结果为：先将a(x)左移一位，若移出的是1，再与‘1B’做异或。

有限环GF（28）[x]/(x4+1)：其中的元素可表示为一个4字节的字，也可以表示为一个最高次数为4的多项式。其中的加法定义同有限域的加法定义，乘法定义则较复杂。

设a(x)=a3x3+a2x2+a1x+a0，b(x)=b3x3+b2x2+b1x+b0，c(x)=a(x)×b(x)=c6x6+c5x5+c4x4+c3x3+c2x2+c1x+c0，其中：

则该环中元素a(x)与b(x)的乘法记为：

d(x)=a(x)⊗b(x)=a(x)×b(x)mod M(x)=d3x3+d2x2+d1x1+d0，其中M(x)=x4+1，

据上面的乘法规则，x⊗b(x)=x×b(x)mod M(x)=b2x3+b1x2+b0x+b3，即只需将字节循环左移位即可。

2.算法描述

1）预处理

如前所述，Rijndael算法的数据块长度和密钥长度可从128比特、192比特和256比特这三种长度中分别独立地选择。先对要加密的数据块进行预处理，使其成为一个长方形的字阵列，每个字含4个字节，占一列，每列4行存放该列对应的4个字节，每个字节含8比特信息。若用Nb表示分组中字的个数（也就是列的个数），则Nb可以等于4、6或8。同样，加密密钥也可看成一个有4行的长方形的字阵列。若用Nk表示密钥中字的个数，则Nk也可以是4、6或8。所以分组阵列中第m个字对应第m列，用am=(am,0,am,1,am,2,am,3)表示，其中每个元素是一个8比特的字节。并有：

am∈GF (28)[x] / (x4+1)，

am,i∈GF(28),(i=1,2,3,4)

Nb等于4时的数据状态如图2-31(a)所示，Nk＝4时的密钥数组如图2-31(b)所示。

2）多轮迭代

进行预处理后，明文分组进入多轮迭代变换，迭代的轮数Nr由Nb和Nk共同决定，可查表。这里的每一轮变换与DES采用的Feistel结构不同，而是在每轮替换和移位时都并行处理整个分组。每一轮包含三层：第一层是非线性层，作用在字节上的非线性字节替换（ByteSub），这个变换可逆，每个字节独立操作，可并行使用多个S盒，以优化最坏情况下的非线性特性（ByteSub），具体实现时可查表计算。第二层是线性混合层，实现线性混合的行移位变换（ShiftRow）和列混合变换（MixColumn），保证多轮变换后密码的整体混乱和高度扩散。其中行移位变换中，分组矩阵的第0行保持不变，第1行循环左移C1位，第2行循环左移C2位，第3行循环左移C3位，从而形成新的状态矩阵，C1、C2和C3的具体值与加密分组长度Nb有关；列混合变换则是将分组矩阵的字列看成是GF(28)[x] / (x4+1)上的多项式，并且与一个固定的多项式c(x)做该有限环中的乘法运算，得到一个新的状态矩阵。在算法的最后一轮，不进行列混合变换。第三层是轮密钥加层，即将分组矩阵与该轮所使用的子密钥矩阵进行按位异或。

算法的轮数Nr由Nb和Nk共同决定，具体值如表2-2所示。

加密和解密过程分别需要Nr+1个子密钥。每一轮子密钥的长度都要与加密分组的长度Nb相等，并保证各轮密钥长度的和（比特数）等于分组长度乘以轮数加1（如分组长为128比特，轮数是10，则轮密钥需要：128×11=1408比特）。其产生方法是先将加密密钥（k0k1k2…kNk-1）扩展为一个扩展密钥，在扩展时根据加密密钥的长度不同采用不同的扩展方法，加密密钥长度为128比特和192比特的采用同一种方法，长度为256比特的采用另一种方法。扩展后，第一轮子密钥由该扩展密钥中第一组的Nb个字构成，第二轮密钥由第二组的Nb个字构成，如此类推。

AES的解密算法结构与加密算法结构基本相同，只不过每一步变换都是加密算法的逆变换，这也是为什么AES属于对称密码体制的原因。另外解密的密钥生成时采用的扩展方法与加密略有不同。

完整的AES加密和解密过程如图2-32所示。

3.安全性分析

根据对Rijndael算法的理论分析，可以证明AES算法进行8轮以上即可对抗线性密码分析、差分密码分析，亦可抵抗专门针对Square算法提出的Square攻击。如果用穷举法破译，则由于穷举密钥搜索的运算量取决于加密密钥的长度。当密钥长度分别为128比特、192比特和256比特时，对应的运算量分别为2127、2191和2255。

AES算法的优点是设计简单，分组长度及密钥长度可变，且都易于扩充，可以方便地用软件快速实现。

2.4.3　RC4

与DES和AES不同的是，RC4（Rivest Cipher 4）是一种流密码算法，是由Ron Rivest在1987年设计出的密钥长度可变的加密算法簇。起初该算法是商业机密，直到1994年，才公诸于众。由于RC4具有算法简单，运算速度快，软硬件实现十分容易等优点，使其在一些协议和标准里得到了广泛应用，如IEEE802.11无线局域网安全协议WEP与WPA（将在第5章介绍）、传输层安全协议TLS和安全套接字层协议SSL（将在第7章介绍）的早期版本中均使用了RC4算法。

在介绍RC4算法过程之前，先介绍几个概念：

（1）密钥流（key stream）：RC4算法的关键是根据明文和密钥生成相应的密钥流，密钥流的长度和明文、密文的长度是相同的。

（2）状态向量S：长度为256，S[0]S[1] .....S[255]，一般将S称为S盒（S-box）。每个单元都是一个字节，算法运行的任何时候，S都包括0~255的8比特数的排列组合，只不过值的位置发生了变换。

（3）临时向量T：长度也为256，每个单元也是一个字节。如果密钥的长度是256字节，就直接把密钥的值赋给T，否则，轮转地将密钥的每个字节赋给T。

（4）密钥K：长度为1~256字节，注意密钥的长度（keylen）与明文长度、密钥流的长度没有必然关系，通常密钥的长度为16字节（128比特）。

RC4算法包括以下几个步骤：

（1）初始化S和T：首先初始化状态向量S，然后用密钥K初始化临时向量&##119879;，具体过程如图2-33(a)所示，用C代码表示如下：

（2）置换：用T产生S的初始置换，具体过程如图2-33(b)所示，用C代码表示如下：

（3）通过伪随机数生成算法（Pseudo-Random Generation Algorithm，PRGA）得到密钥流k，对数据D进行加密，过程如图2-33(c)所示，用C代码表示如下：

（4）解密：密文与密钥流k进行异或运算得到明文，过程与加密一样，用C代码表示如下：

由于RC4算法加密采用的是异或运算（XOR），所以，一旦子密钥序列出现了重复，密文就有可能被破解。那么，RC4算法生成的子密钥序列是否会出现重复呢？由于存在部分弱密钥，使得子密钥序列在不到100万字节内就发生了完全的重复，如果是部分重复，则可能在不到10万字节内就能发生重复，因此，推荐在使用RC4算法时，必须对加密密钥进行测试，判断其是否为弱密钥。

当密钥长度超过128位时，以当前的技术而言，RC4是很安全的，RC4也是唯一对2011年TLS 1.0 BEAST攻击免疫的常见密码。近年来RC4爆出多个漏洞，安全性有所下降。例如，2015年比利时鲁汶大学的研究人员Mathy Vanhoef与Frank Piessens，公布了针对RC4加密算法的新型攻击方法，可在75小时内取得Cookie的内容。因此，2015年IETF发布了RFC 7465，禁止在TLS中使用RC4，NIST也禁止在美国政府的信息系统中使用RC4。著名的分布式代码管理网站Github从2015年1月5日起也停止对RC4的支持。