对称密码体制的介绍及应用

对称密码体制（Symmetric Encryption）也称为秘密密钥密码体制、单密钥密码体制或常规密码体制，其模型如图7-4所示。如果一个密码算法的加密密钥和解密密钥相同，或由其中一个很容易推导出另一个，该算法就是对称密码算法，满足关系：M＝DK（C）＝DK［EK（M）］。

图7-4　对称密码体制模型

一个攻击者（密码分析者）能基于不安全的公开信道观察密文C，但不能接触到明文M或密钥K，他可以试图恢复明文M或密钥K。假定他知道加密算法E和解密算法D，只对当前这个特定的消息感兴趣，则努力的焦点是通过产生一个明文的估计值M′来恢复明文M。如果他也对读取未来的消息感兴趣，就需要试图通过产生一个密钥的估计值K′来恢复密钥K，这是一个密码分析的过程。

对称密码体制的安全性主要取决于两个因素：第一，加密算法必须足够安全，不必为算法保密，仅根据密文就能破译出消息是计算上不可行的；第二，密钥的安全性，即密钥必须保密并保证有足够大的密钥空间。对称密码体制要求基于密文和加密／解密算法的知识能破译出消息的做法在计算上是不可行的。

对称密码算法的优缺点如下：

（1）优点：加密、解密处理速度快，保密程度高等。

（2）缺点有4个。

①密钥是保密通信安全的关键，发信方必须安全、妥善地把密钥护送到收信方，不能泄露其内容。如何才能把密钥安全地送到收信方，是对称密码算法的突出问题。对称密码算法的密钥分发过程复杂，所花代价高；②多人通信时密钥组合的数量会出现爆炸性膨胀，使密钥分发更加复杂化，若有N个用户进行两两通信，总共需要的密钥数为N（N-1）／2个；③通信双方必须统一密钥，才能发送保密的信息。如果发信者与收信者素不相识，这就无法向对方发送秘密信息了；④除了密钥管理与分发问题，对称密码算法还存在数字签名困难问题（通信双方拥有同样的消息，接收方可以伪造签名，发送方也可以否认发送过某消息）。

对称密码算法分两类：一类是对明文的单个位（或字节）进行运算的算法，称为序列密码算法，也称为流密码算法（Stream Cipher）；另一类是把明文信息划分成不同的块（或小组）结构，分别对每个块（或小组）进行加密和解密，称为分组密码算法（Block Cipher）。

1.序列密码

序列密码是将明文划分成单个位（如数字0或1）作为加密单位产生明文序列，然后将其与密钥流序列逐位进行模2加运算，用符号表示为⊕，其结果作为密文的方法。序列密码加密过程如图7-5所示。

图7-5　序列密码加密过程

加密算法：ci＝mi+ki（mod 2）

解密算法：mi＝ci+ki（mod 2）

【例7-1】设明文序列M是一串二进制数据，有M＝（101011001111000011111111）2，密钥K＝（111100001111000011110000）2，则

加密过程：C＝M+K（mod 2）＝（010111000000000000001111）2

解密过程：M＝C+K（mod 2）＝（101011001111000011111111）2

序列密码分为同步序列密码和自同步序列密码两种。同步序列密码要求发送方和接收方必须是同步的，在同样的位置用同样的密钥才能保证正确地解密。如果在传输过程中密文序列有被篡改、删除、插入等错误导致同步失效，则不可能成功解密，只能通过重新同步来实现解密、恢复密文。在传输期间，一个密文位的改变只影响该位的恢复，不会对后继位产生影响。自同步序列密码的密钥的产生与密钥和已产生的固定数量的密文位有关，因此，密文中产生的一个错误会影响到后面有限位的正确解密。所以，自同步密码的密码分析比同步密码的密码分析更加困难。

序列密码具有实现简单、便于硬件计算、加密与解密处理速度快、低错误（没有或只有有限位的错误）传播等优点，但同时也暴露出其对错误的产生不敏感的缺点。序列密码涉及大量的理论知识，许多研究成果并没有完全公开，这也许是因为序列密码目前主要用于军事和外交等机要部门的缘故。目前，公开的序列密码主要有RC4、SEAL等。

序列密码的安全强度依赖于密钥流产生器所产生的密钥流序列的特性，关键是密钥生成器的设计及收发两端密钥流产生的同步技术。

1）伪随机序列

在序列密码中，一个好的密钥流序列应该满足：具有良好的伪随机性，如极大的周期、极大的线性复杂度、序列中0和1的分布均匀；产生的算法简单；硬件实现方便。

产生密钥流序列的一种简单方法是使用自然现象随机生成，如半导体电阻器的热噪声、公共场所的噪声源等。还有一种方法是使用软件以简单的数学函数来实现，如标准C语言库函数中的rand（）函数，它可以产生介于0～65 535的任何一个整数，以此当作“种子”输入，随后再产生比特流。rand（）函数建立在一个线性同余生成器的基础上，如kn＝akn-1+b（mod m），k0作为初始值，a、b和m都是整数，但这只能作为以实验为目的的例子，不能满足密码学意义上的要求。

产生伪随机数的一个不错的选择是使用数论中的难题。最常用的是BBS伪随机序列生成器，也就是二次方程式残数生成器。首先产生两个大素数p和q，且p＝q＝3（mod 4），设n＝pq，并选择一个随机整数x，x与n是互素的，且设初始输入x0＝x2（mod n），BBS（Blam-Blam-Shab一种伪随机发生器）通过如下过程产生一个随机序列b1，b2，…：

（1）xj＝xj-1（mod n）。

（2）bj是xj的最低有效比特。

例如，设p＝24672462467892469787和q＝396736894567834589803，则

x1，x2，…，x8的值分别如下：

取上述任意一个比特串，当x值为奇数时，b值取1；当x值为偶数时，b值取0，故产生的随机序列b1，b2，…，b8＝0，1，1，1，0，0，0，0。产生密钥流序列的方法很多，常见的方法有线性同余法、线性反馈移位寄存器、非线性反馈移位寄存器、有限自动机和混沌密码等。

2）线性反馈移位寄存器

通常，产生密钥流序列的硬件是反馈移位寄存器。一个反馈移位寄存器由两部分组成：移位寄存器和反馈函数（图7-6）。

移位寄存器由n个寄存器组成，每个寄存器只能存储一个位，在一个控制时钟周期内，根据寄存器当前的状态计算反馈函数f（a1，a2，…，an）作为下一时钟周期的内容，每次输出最右端一位a1，同时，寄存器中所有位都右移一位，最左端的位由反馈函数计算得到。ai（t）表示t时刻第i个寄存器的内容，用ai（t+1）表示ai（t）下一时刻的内容，则有：

图7-6　反馈移位寄存器

移位函数：ai（t+1）＝ai+1（t），其中（i＝1，2，…，n-1）

反馈函数：an（t+1）＝f（a1（t），a2（t），…，an（t））

如果反馈函数f（a1，a2，…，an）＝k1an⊕k2an-1⊕…⊕kna1，其中k∈｛0，1｝，则该反馈函数是a1，a2，…，an的线性函数，对应的反馈移位寄存器称为线性反馈移位寄存器（Linear Feedback Shift Register，LFSR）。

【例7-2】设线性反馈移位寄存器为

对应（k1，k2，k3，k4）＝（0，1，0，1），设初始状态为（a1，a2，a3，a4）＝（0，1，1，1），LFSR在不同时刻的状态见表7-2。

表7-2　LFSR在不同时刻的状态

由表7-2可知，t＝6时的状态恢复到t＝0时的状态，且往后循环。因此，该反馈移位寄存器的周期是6，输出序列为0111100……，表中对应a1的状态。本例中，若反馈函数为a4（t+1）＝a1（t）⊕a4（t），则周期达到15，输出序列为0110010001111010……。对于4级线性反馈移位寄存器而言，所有可能状态为24＝16种，去除全0状态，最大可能周期为15。对于n级线性反馈移位寄存器，不可能产生全0状态，因此，最大可能周期为2n-1，而能够产生最大周期的LFSR是我们所需要的，这就要求线性反馈函数符合一定的条件。关于随机序列的周期及线性复杂度的有关知识，需要读者具备一定的数学基础，本书不再展开讨论。

选择线性反馈移位寄存器作为密钥流生成器的主要原因有：适合硬件实现；能产生大的周期序列；能产生具有良好的统计特性的序列；它的结构能够应用代数方法进行很好的分析。实际应用中，通常将多个LFSR组合起来构造非线性反馈移位寄存器，n级非线性反馈移位寄存器严生伪随机序列的周期最大可达2n，因此，研究产生最大周期序列的方法具有重要意义。

3）RC4

RC4是由麻省理工学院的Ron Rivest教授在1987年为RSA公司设计的一种可变密钥长度、面向字节流的序列密码。RC4是目前使用最广泛的序列密码之一，已应用于Microsoft Windows、Lotus Notes和其他应用软件中，特别是应用到SSL协议和无线通信方面。

RC4算法很简单，它以一个数据表为基础，对表进行非线性变换，从而产生密码流序列。其包含两个主要算法：密钥调度算法（Key-Scheduling Algorithm，KSA）和伪随机生成算法（Pseudo Random Generation Algorithm，PRGA）。

KSA的作用是将一个随机密钥（大小为40～256位）变换成一个初始置换表S。过程如下：

（1）S表中包含256个元素S［0］～S［255］，对其初始化，令S［i］＝i，0≤i≤255。

（2）用主密钥填充字符表K，如果密钥的长度小于256 Byte，则依次重复填充，直至将K填满，K＝｛K［i］，0≤i≤255｝。

（3）令j＝0。

（4）对于i，从0～255循环：

①j＝j+S［i］+K［i］（mod 256）。

②交换S［i］和S［j］。

PRGA的作用是从S表中随机选取元素，并产生密钥流。其过程如下：

（1）i＝0，j＝0。

（2）i＝i+1（mod 256）。

（3）j＝j+S［i］（mod 256）。

（4）交换S［i］和S［j］。

（5）t＝S［i］+S［j］（mod 256）。

（6）输出密钥字k＝S［t］。

虽然RC4要求主密钥K至少为40 bit，但为了保证安全强度，目前至少要达到128位。

2.分组密码

设明文消息被划分成若干固定长度的组m＝（m1，m2，…，mn），其中mi＝0或1，i＝1，2，…，n，每一组的长度为n，各组分别在密钥k＝（k1，k2，…，kt）的作用下变换成长度为r的密文分组c＝（c1，c2，…，cr）。分组密码的模型如图7-7所示。

图7-7　分组密码模型

分组密码的本质就是由密钥k＝（k1，k2，…，kn）控制的从明文空间M（长为n的比特串的集合）到密文空间C（长为r的比特串的集合）的一个一对一映射。为了保证密码算法的安全强度，加密变换的构造应遵循下列五个原则：

（1）分组长度足够大。当分组长度n较小时，容易受到暴力穷举攻击（对密码进行逐个推算，直到找出真正密码为止的一种攻击方式），因此要有足够大的分组长度n来保证足够大的明文空间，避免给攻击者提供太多的明文统计特征信息。

（2）密钥量空间足够大，以抵抗攻击者通过穷举密钥破译密文或者获得密钥信息。

（3）加密变换足够复杂，以加强分组密码算法自身的安全性，使攻击者无法利用简单的数学关系找到破译缺口。

（4）加密和解密运算简单，易于实现。分组加密算法将信息分成固定长度的二进制位串进行变换。为便于软、硬件的实现，一般应选取加法、乘法、异或和移位等简单的运算，以避免使用逐个比特转换的方法。

（5）加密和解密的逻辑结构最好一致。如果加密、解密过程的算法逻辑部件一致，那么加密、解密可以由同一部件实现，区别在于所使用的密钥不同，以简化密码系统整体结构的复杂性。

古典密码中最基本的变换是替代和置换，其目的是产生尽可能混乱的密文。分组密码同样离不开这两种最基本的变换，替代变换就是经过复杂的变换关系将输入位进行转换，记作S，称为S盒；移位变换就是将输入位的排列位置进行变换，记作P，称为P盒，如图7-8所示。

图7-8　两种基本变换

分组密码由多重S盒和P盒组合而成。S盒的直接作用是将输入位进行某种变换，以起到混乱的作用；P盒的直接作用就是移动输入位的排列位置关系，以起到扩散的作用。分组密码算法就是采用“混乱与扩散”两个主要思想进行设计的，这是Shannon为了有效抵抗攻击者对密码体制的统计分析提出的基本设计思想，也可以认为是分组密码算法设计的基本原理。实现分组密码算法设计的具体操作包括以下三个方面：(www.xing528.com)

（1）替代。替代是指将明文位用某种变换关系变换成新的位，以使所产生的密文是一堆杂乱无章的乱码，这种变换与明文和密钥密切相关，要求尽可能地使密文与明文和密钥之间的关系十分复杂，不便破译者从中发现规律和依赖关系，从而加强隐蔽性。在分组密码算法中采用复杂的非线性替代变换就可达到比较好的混乱效果。

（2）置换。置换是指让明文中的每一位（包括密钥的每一位）直接或间接影响输出密文中的许多位，即将每一比特明文（或密钥）的影响尽可能迅速地作用到较多的输出密文位中去，以便达到隐蔽明文的统计特性。这种效果也称为“雪崩效应”，也就是说，输入即使只有很小的变化，也会导致输出位发生巨大变化。分组密码算法设计中的置换操作就是为了达到扩散的目的。

（3）乘积变换。在分组密码算法设计中，为了增强算法的复杂度，常用的方法是采用乘积变换的思想，即加密算法不仅是简单的一次或两次基本的S盒和P盒变换，而是通过两次或两次以上S盒和P盒的反复应用，也就是迭代的思想，克服单一密码变换的弱点，构成更强的加密结果，以强化其复杂程度。后面介绍的一些分组密码算法，无一例外地都采用了这种乘积密码的思想。

3.数据加密标准——DES

20世纪60年代末，国际商业机器公司（IBM）开始研制计算机密码算法，在1971年结束时，提出了一种称为Luciffer的密码算法，它是当时最好的算法，也是最初的数据加密算法。1973年美国国家标准与技术局征求国家密码标准方案，IBM就提交了这个算法。1977年7月15日，该算法被正式采纳作为美国联邦信息处理标准生效，成为事实上的国际商用数据加密标准被使用，即数据加密标准（Data Encryption Standard，DES）。当时规定其有效期为5年，后经几次授权续用，真正有效期限长达20年。在这20年中，DES算法在数据加密领域发挥了不可替代的作用。进入20世纪90年代以后，由于DES密钥长度偏短等缺陷，不断受到诸如差分密码分析（由以色列密码专家Shamir提出）和线性密码分析（由日本密码学家Matsui等人提出）等各种攻击威胁，使其安全性受到严重的挑战，而且不断传出被破解的消息。鉴于此，美国国家保密局经多年授权评估后认为，DES算法已没有安全性可言，于是，NIST决定在1998年12月以后不再使用DES来保护官方机密，只推荐作为一般商业使用。1999年又颁布新标准，并规定DES只能用于遗留密码系统，但可以使用加密的3DES加密算法。不管怎样，DES的出现推动了分组密码理论的研究，起到了促进分组密码发展的重要作用，而且它的设计思想对掌握分组密码的基本理论和工程应用有着重要的参考价值。

1）DES算法加密过程

DES对64位的明文分组进行操作。通过一个初始置换，将明文分组分成左半部分和右半部分，各32位长。然后进行16轮完全相同的运算，这些运算被称为函数f，在运算过程中数据与密钥结合。经过16轮后，左、右半部分合在一起，再经过一个末置换（初始置换的逆置换），这样该算法就完成了。DES算法的加密过程如图7-9所示。

DES算法的特点如下：①分组加密算法。以64位为分组，64位一组的明文从算法一端输入，64位密文从另一端输出；②对称算法。加密和解密用同一密钥；③有效密钥长度为56位。密钥通常表示为64位数，但每个第8位用作奇偶校验，可以忽略；④替代和置换。DES算法是两种加密技术的组合——先替代后置换；⑤易于实现。DES算法只是使用了标准的算术和逻辑运算，其作用的数最多也只有64位，因此用20世纪70年代末期的硬件技术很容易实现。

DES算法的具体加密过程如下：

（1）初始置换IP。

初始置换方法是将64位明文的位置顺序打乱，表7-3中的数字代表64位明文的输入顺序号，表中的位置代表置换后的输出顺序，表中的位置顺序是先按行后按列进行排序。例如，表7-3中第一行第一列的数字为58，表示将原来排在第58位的比特位排在第1位；第一行第二列的数字为50，表示将原来排在第50位的比特位排在第2位，依此类推。不妨设输入位序为m1m2…m64，初始置换后变为m′1m′2…m′n＝m58m50…m7。初始置换表中的位序特征：64位输入按8行8列进行排列，最右边一列按2、4、6、8和1、3、5、7的次序进行排列，往左边各列的位序号依次紧邻其右边一列各序号加8，见表7-3。

图7-9　DES算法的加密过程

表7-3　初始变换IP

（2）乘积变换（16轮迭代）。

乘积变换部分要进行16轮迭代，如图7-10所示。将初始置换得到的64位结果分为两半，记为L0和R0，各32位。设初始密钥为64位，经密钥扩展算法产生16个48位的子密钥，记为K1，K2，…，K16。每轮迭代的逻辑关系为

图7-10　DES算法的乘积变换

其中1≤i≤16，函数是每轮变换的核心变换。

（3）逆初始置换IP-l。

逆初始置换IP-l与初始置换正好相反，见表7-4。例如，处在第1位的比特位置换后排在第58位，处在第2位的比特位置换后排在第50位。逆初始置换后变为m′1m′2…m′64＝m40m8…m25。逆初始置换表7-4中的位序特征：64位输入依然按8行8列进行排列，1～8按列从下往上进行排列，然后是9～16排在右边一列，依次进行排4列，然后从33开始排在第一列的左边，从41开始排在第二列的左边，交叉进行。

表7-4　逆初始变换IP-1

2）乘积变换中的f变换

乘积变换的核心是f变换，它是非线性的，是每轮实现混乱的最关键的模块，输入32位，经过扩展置换变成48位，与子密钥进行异或运算，选择S盒替换，将48位压缩还原成32位，再进行P盒替换，输出32位。如图7-11所示，虚线部分为f变换。详细的变化过程如图7-12所示。

图7-11　一轮迭代过程

图7-12　f变换的计算过程

（1）扩展置换。

扩展置换将32位扩展成48位，按表7-5的排列方式进行重新排列。

表7-5　扩展置换

（2）S盒替换。

将48位按6位分为1组，共8组，也称为8个S盒，记为S1S2…S8。每个S盒产生4位输出。8个S盒的替换表见表7-6。

每个S盒都由4行×16列组成，每行是0～15的一个全排列，每个数字用对应的4位二进制比特串表示，如9用1001表示，7用0111表示。设6位输入为a1a2a3a4a5a6。，将a1a6组成一个两位二进制数，对应S盒表中的行号；将a2a3a4a5。组成一个4位二进制数，对应S盒表中的列号。这样，映射到交叉点的数据就是该S盒的输出。

例如，已知第2个S盒的输入为111101，则a1＝1，a6＝1，a1a6＝（11）2＝3，表明对应的行号为3，（a2a3a4a5）＝（1110）2＝14，表明对应列号为14。查第2个S盒替换表，S2中行号为3，列号为14列的数据为14，化成二进制得到输出为1110。

表7-6　S盒替换表

（3）P盒替换。

P盒替换就是将S盒替换后的32位作为输入，按表7-7的顺序重新排列，得到的32位结果即为f（）函数的输出f（Ri-1，Ki）。

表7-7　P盒替换

3）子密钥的生成

初始密钥长度为64位，但每个第8位是奇偶校验位，分布在第8、16、24、32、40、48、56和64位的位置上，目的是用来检错，实际的初始密钥长度是56位。在DES算法中，每一轮迭代需要使用一个子密钥，子密钥是从用户输入的初始密钥中产生的。图7-13所示为各轮子密钥产生的流程图。

图7-13　子密钥的产生流程

子密钥的生成过程包括置换选择1（PC-1）、循环左移、置换选择2（PC-2）等变换，分别产生16个子密钥。

（1）置换选择1（PC-1）。

对于64位初始密钥K，按表7-8中置换选择表PC-1进行重新排列。不难算出，丢掉了其中8的整数倍位置上的比特位，置换选择1后的变换结果是56位。将前28位记为C0，后28位记为D0。

表7-8　“置换选择1（PC-1）”的置换表

（2）循环左移。

在不同轮次，循环左移LSi（1≤i≤16）的位数不同，见表7-9。第一轮循环左移LS1＝1，第二轮循环左移LS2＝1，第三轮循环左移LS3＝2，依此类推。

表7-9　循环左移的位数

（3）置换选择2（PC-2）。

与置换选择1相同，对输入的32位比特串按表7-10中的置换选择表PC-2进行重新排列，输出即为子密钥。

表7-10　“置换选择2（PC-2）”的置换表

4.DES解密过程

DES解密过程的逻辑结构与加密过程一致，但应注意以下两点：

（1）第16轮迭代结束后须将左右两个分组交换位置，即将L16与R16交换顺序。

（2）解密过程中使用的子密钥的顺序与加密时的顺序正好相反，依次为K16，K15，…，K1，即当把64位密文作为明文输入时，解密过程的第1轮迭代使用子密钥K16，第2轮迭代使用子密钥K15，…，第16轮迭代使用子密钥K1，同理，第16轮迭代后须交换顺序，最终输出得到64位明文。

5.DES算法的安全隐患

现在来看，DES算法具有以下3点安全隐患：

（1）密钥太短。DES的初始密钥实际长度只有56位，批评者担心这个密钥长度不足以抵抗穷举搜索攻击，穷举搜索攻击破解密钥最多尝试的次数为256次，不太可能提供足够的安全性。1998年以前，只有DES破译机的理论设计，1998年后出现实用化的DES破译机。

（2）DES的半公开性。DES算法中的8个S盒替换表的设计标准（指详细准则）自DES公布以来仍未公开，替换表中的数据是否存在某种依存关系，用户无法确认。

（3）DES迭代次数偏少。DES算法的16轮迭代次数被认为偏少，因此在以后的DES改进算法中，都不同程度地进行了提高。

6.三重DES应用

针对DES密钥位数和迭代次数偏少等问题，有人提出了多重DES来克服这些缺陷，比较典型的是2DES、3DES和4DES等几种形式，实用中一般广泛采用3DES方案，即三重DES。它有以下4种使用模式：

（1）DES-EEE3模式：使用三个不同密钥（K1，K2，K3），采用三次加密算法。

（2）DES-EDE3模式：使用三个不同密钥（K1，K2，K3），采用加密-解密-加密算法。

（3）DES-EEE2模式：使用两个不同密钥（K1＝K3，K2），采用三次加密算法。

（4）DES-EDE2模式：使用两个不同密钥（K1＝K3，K2），采用加密-解密-加密算法。

3DES的优点：密钥长度增加到112位或168位，抗穷举攻击的能力大大增强；DES基本算法仍然可以继续使用。

3DES的缺点：处理速度相对较慢，因为3DES中共需迭代48次，同时，密钥长度也增加了，计算时间明显增大；3DES算法的明文分组大小不变，仍为64位，加密的效率不高。