第3章分组密码

《第3章分组密码》由会员分享，可在线阅读，更多相关《第3章分组密码（197页珍藏版）》请在装配图网上搜索。

1、第第3章章 分组密码体制分组密码体制3.1 分组密码概述分组密码概述3.2 数据加密标准数据加密标准DES3.4 分组密码的运行模式分组密码的运行模式3.5 IDEA3.6 AES算法算法Rijndaeln单钥分组密码是系统安全的一个重要组成部分单钥分组密码是系统安全的一个重要组成部分n实际应用中对于分组密码可能提出多方面的要求实际应用中对于分组密码可能提出多方面的要求n 安全性安全性n 运行速度运行速度n 存储量（程序的长度、数据分组长度、高速缓存大小）存储量（程序的长度、数据分组长度、高速缓存大小）n 实现平台（硬件、软件、芯片）实现平台（硬件、软件、芯片）n 运行模式运行模式3.1分组密

2、码概述分组密码概述分组密码是将明文消息编码表示后的数字序列分组密码是将明文消息编码表示后的数字序列x0,x1,xi,划分成长为划分成长为n的组的组x=(x0,x1,xn-1)，各各组（长为组（长为n的矢量）分别在密钥的矢量）分别在密钥k=(k0,k1,kt-1)控制控制下变换成等长的输出数字序列下变换成等长的输出数字序列y=(y0,y1,ym-1)（长长为为m的矢量），其加密函数的矢量），其加密函数E：VnKVm，Vn和和Vm分别是分别是n维和维和m维矢量空间，维矢量空间，K为密钥空间，如为密钥空间，如图图3.1所示。它与流密码不同之处在于输出的每一所示。它与流密码不同之处在于输出的每一位数字

3、不是只与相应时刻输入的明文数字有关，而位数字不是只与相应时刻输入的明文数字有关，而是与一组长为是与一组长为n的明文数字有关。在相同密钥下，的明文数字有关。在相同密钥下，分组密码对长为分组密码对长为n的输入明文组所实施的变换是等的输入明文组所实施的变换是等同的，所以只需研究对任一组明文数字的变换规则。同的，所以只需研究对任一组明文数字的变换规则。这种密码实质上是字长为这种密码实质上是字长为n的数字序列的代换密码。的数字序列的代换密码。图图3.1 分组密码框图分组密码框图通常取通常取m=n。若若mn，则为有数据扩展的分组密码；则为有数据扩展的分组密码；若若mn，则为有数据压缩的分组密码。在二元情况

4、则为有数据压缩的分组密码。在二元情况下，下，x和和y均为二元数字序列，它们的每个分量均为二元数字序列，它们的每个分量xi，yiGF(2)。本节将主要讨论二元情况。设计的算本节将主要讨论二元情况。设计的算法应满足下述要求：法应满足下述要求：分组长度分组长度n要足够大，使分组代换字母表中的元要足够大，使分组代换字母表中的元素个数素个数2n足够大，防止明文穷举攻击法奏效。足够大，防止明文穷举攻击法奏效。DES、IDEA、FEAL和和LOKI等分组密码都采用等分组密码都采用n=64，在在生日攻击下用生日攻击下用232组密文成功概率为组密文成功概率为1/2，同时要求，同时要求23264b=215MB存贮

5、，故采用穷举攻击是不现实的。存贮，故采用穷举攻击是不现实的。密钥量要足够大（即置换子集中的元素足够密钥量要足够大（即置换子集中的元素足够多），尽可能消除弱密钥并使所有密钥同等地好，多），尽可能消除弱密钥并使所有密钥同等地好，以防止密钥穷举攻击奏效。但密钥又不能过长，以以防止密钥穷举攻击奏效。但密钥又不能过长，以便于密钥的管理。便于密钥的管理。DES采用采用56比特密钥，看来太短比特密钥，看来太短了，了，IDEA采用采用128比特密钥，据估计，在今后比特密钥，据估计，在今后3040年内采用年内采用80 比特密钥是足够安全的。比特密钥是足够安全的。由密钥确定置换的算法要足够复杂，充分实现由密钥确定

6、置换的算法要足够复杂，充分实现明文与密钥的扩散和混淆，没有简单的关系可循，明文与密钥的扩散和混淆，没有简单的关系可循，能抗击各种已知的攻击，如差分攻击和线性攻击；能抗击各种已知的攻击，如差分攻击和线性攻击；有高的非线性阶数，实现复杂的密码变换；使对手有高的非线性阶数，实现复杂的密码变换；使对手破译时除了用穷举法外，无其它捷径可循。破译时除了用穷举法外，无其它捷径可循。加密和解密运算简单，易于软件和硬件高速实加密和解密运算简单，易于软件和硬件高速实现。如将分组现。如将分组n化分为子段，每段长为化分为子段，每段长为8、16或者或者32。在以软件实现时，应选用简单的运算，使作用于子在以软件实现时，应

7、选用简单的运算，使作用于子段上的密码运算易于以标准处理器的基本运算，如段上的密码运算易于以标准处理器的基本运算，如加、乘、移位等实现，避免用以软件难于实现的逐加、乘、移位等实现，避免用以软件难于实现的逐比特置换。为了便于硬件实现，加密和解密过程之比特置换。为了便于硬件实现，加密和解密过程之间的差别应仅在于由秘密密钥所生成的密钥表不同间的差别应仅在于由秘密密钥所生成的密钥表不同而已。这样，加密和解密就可用同一器件实现。设而已。这样，加密和解密就可用同一器件实现。设计的算法采用规则的模块结构，如多轮迭代等，以计的算法采用规则的模块结构，如多轮迭代等，以便于软件和便于软件和VLSI快速实现。此外，差

8、错传播和数快速实现。此外，差错传播和数据扩展要尽可能地小。据扩展要尽可能地小。数据扩展。一般无数据扩展，在采用同态置换数据扩展。一般无数据扩展，在采用同态置换和随机化加密技术时可引入数据扩展。和随机化加密技术时可引入数据扩展。差错传播尽可能地小。差错传播尽可能地小。要实现上述几点要求并不容易。首先，要在理论上要实现上述几点要求并不容易。首先，要在理论上研究有效而可靠的设计方法，而后进行严格的安全研究有效而可靠的设计方法，而后进行严格的安全性检验，并且要易于实现。性检验，并且要易于实现。下面介绍设计分组密码时的一些常用方法。下面介绍设计分组密码时的一些常用方法。如果明文和密文的分组长都为如果明文

9、和密文的分组长都为n比特，则明文的每比特，则明文的每一个分组都有一个分组都有2n个可能的取值。为使加密运算可逆个可能的取值。为使加密运算可逆（使解密运算可行），明文的每一个分组都应产生（使解密运算可行），明文的每一个分组都应产生惟一的一个密文分组，这样的变换是可逆的，称明惟一的一个密文分组，这样的变换是可逆的，称明文分组到密文分组的可逆变换为代换。不同可逆变文分组到密文分组的可逆变换为代换。不同可逆变换的个数有换的个数有2n!个。个。3.1.1 代换代换图图3.2表示表示n=4的代换密码的一般结构，的代换密码的一般结构，4比特输入比特输入产生产生16个可能输入状态中的一个，由代换结构将这个可能

10、输入状态中的一个，由代换结构将这一状态映射为一状态映射为16个可能输出状态中的一个，每一输个可能输出状态中的一个，每一输出状态由出状态由4个密文比特表示。加密映射和解密映射个密文比特表示。加密映射和解密映射可由代换表来定义，如表可由代换表来定义，如表3.1所示。这种定义法是所示。这种定义法是分组密码最常用的形式，能用于定义明文和密文之分组密码最常用的形式，能用于定义明文和密文之间的任何可逆映射。（见间的任何可逆映射。（见33页表页表3.1）图图3.2 代换结构代换结构但这种代换结构在实用中还有一些问题需考虑。如但这种代换结构在实用中还有一些问题需考虑。如果分组长度太小，如果分组长度太小，如n=

11、4，系统则等价于古典的代系统则等价于古典的代换密码，容易通过对明文的统计分析而被攻破。这换密码，容易通过对明文的统计分析而被攻破。这个弱点不是代换结构固有的，只是因为分组长度太个弱点不是代换结构固有的，只是因为分组长度太小。如果分组长度小。如果分组长度n足够大，而且从明文到密文可足够大，而且从明文到密文可有任意可逆的代换，那么明文的统计特性将被隐藏有任意可逆的代换，那么明文的统计特性将被隐藏而使以上的攻击不能奏效。而使以上的攻击不能奏效。然而，从实现的角度来看，分组长度很大的可逆代然而，从实现的角度来看，分组长度很大的可逆代换结构是不实际的。仍以表换结构是不实际的。仍以表3.1为例，该表定义了

12、为例，该表定义了n=4时从明文到密文的一个可逆映射，其中第时从明文到密文的一个可逆映射，其中第2列是列是每个明文分组对应的密文分组的值，可用来定义这每个明文分组对应的密文分组的值，可用来定义这个可逆映射。因此从本质上来说，第个可逆映射。因此从本质上来说，第2列是从所有列是从所有可能映射中决定某一特定映射的密钥。这个例子中，可能映射中决定某一特定映射的密钥。这个例子中，密钥需要密钥需要64比特。一般地，对比特。一般地，对n比特的代换结构，比特的代换结构，密钥的大小是密钥的大小是n2n比特。如对比特。如对64比特的分组，密比特的分组，密钥大小应是钥大小应是64264=2701021比特，因此难以处

13、理。比特，因此难以处理。实际中常将实际中常将n分成较小的段，例如可选分成较小的段，例如可选n=rn0，其其中中r和和n0都是正整数，将设计都是正整数，将设计n个变量的代换变为设个变量的代换变为设计计r个较小的子代换，而每个子代换只有个较小的子代换，而每个子代换只有n0个输入个输入变量。一般变量。一般n0都不太大，称每个子代换为代换盒，都不太大，称每个子代换为代换盒，简称为简称为S盒。例如盒。例如DES中将输入为中将输入为48比特、输出为比特、输出为32比特的代换用比特的代换用8个个S盒来实现，每个盒来实现，每个S盒的输入端盒的输入端数仅为数仅为6比特，输出端数仅为比特，输出端数仅为4比特。比特

14、。扩散和混淆是由扩散和混淆是由Shannon提出的设计密码系统的两提出的设计密码系统的两个基本方法，目的是抗击敌手对密码系统的统计分个基本方法，目的是抗击敌手对密码系统的统计分析。如果敌手知道明文的某些统计特性，如消息中析。如果敌手知道明文的某些统计特性，如消息中不同字母出现的频率、可能出现的特定单词或短语，不同字母出现的频率、可能出现的特定单词或短语，而且这些统计特性以某种方式在密文中反映出来，而且这些统计特性以某种方式在密文中反映出来，那么敌手就有可能得出加密密钥或其一部分，或者那么敌手就有可能得出加密密钥或其一部分，或者得出包含加密密钥的一个可能的密钥集合。在得出包含加密密钥的一个可能的

15、密钥集合。在Shannon称之为理想密码的密码系统中，密文的所称之为理想密码的密码系统中，密文的所有统计特性都与所使用的密钥独立。图有统计特性都与所使用的密钥独立。图3.2讨论的讨论的代换密码就是这样的一个密码系统，然而它是不实代换密码就是这样的一个密码系统，然而它是不实用的。用的。3.1.2 扩散和混淆扩散和混淆所谓扩散，就是将明文的统计特性散布到密文中去，所谓扩散，就是将明文的统计特性散布到密文中去，实现方式是使得明文的每一位影响密文中多位的值，实现方式是使得明文的每一位影响密文中多位的值，等价于说密文中每一位均受明文中多位影响。例如等价于说密文中每一位均受明文中多位影响。例如对英文消息对

16、英文消息M=m1m2m3的加密操作的加密操作其中其中ord(mi)是求字母是求字母mi对应的序号，对应的序号，chr(i)是求序是求序号号i对应的字母。这时明文的统计特性将被散布到对应的字母。这时明文的统计特性将被散布到密文中，因而每一字母在密文中出现的频率比在明密文中，因而每一字母在密文中出现的频率比在明文中出现的频率更接近于相等，双字母及多字母出文中出现的频率更接近于相等，双字母及多字母出现的频率也更接近于相等。在二元分组密码中，可现的频率也更接近于相等。在二元分组密码中，可对数据重复执行某个置换，再对这一置换作用于一对数据重复执行某个置换，再对这一置换作用于一函数，可获得扩散。函数，可获

17、得扩散。1mod26knn iiychrord m分组密码在将明文分组依靠密钥变换到密文分组时，分组密码在将明文分组依靠密钥变换到密文分组时，扩散的目的是使明文和密文之间的统计关系变得尽扩散的目的是使明文和密文之间的统计关系变得尽可能复杂，以使敌手无法得到密钥；混淆是使密文可能复杂，以使敌手无法得到密钥；混淆是使密文和密钥之间的统计关系变得尽可能复杂，以使敌手和密钥之间的统计关系变得尽可能复杂，以使敌手无法得到密钥。因此即使敌手能得到密文的一些统无法得到密钥。因此即使敌手能得到密文的一些统计关系，由于密钥和密文之间的统计关系复杂化，计关系，由于密钥和密文之间的统计关系复杂化，敌手也无法得到密钥

18、。使用复杂的代换算法可以得敌手也无法得到密钥。使用复杂的代换算法可以得到预期的混淆效果，而简单的线性代换函数得到的到预期的混淆效果，而简单的线性代换函数得到的混淆效果则不够理想。混淆效果则不够理想。扩散和混淆成功地实现了分组密码的本质属性，因扩散和混淆成功地实现了分组密码的本质属性，因而成为设计现代分组密码的基础。而成为设计现代分组密码的基础。很多分组密码的结构从本质上说都是基于一个称为很多分组密码的结构从本质上说都是基于一个称为Feistel网络的结构。网络的结构。Feistel提出利用乘积密码可获提出利用乘积密码可获得简单的代换密码，乘积密码指顺序地执行两个或得简单的代换密码，乘积密码指顺

19、序地执行两个或多个基本密码系统，使得最后结果的密码强度高于多个基本密码系统，使得最后结果的密码强度高于每个基本密码系统产生的结果，每个基本密码系统产生的结果，Feistel还提出了实还提出了实现代换和置换的方法。其思想实际上是现代换和置换的方法。其思想实际上是Shannon提提出的利用乘积密码实现混淆和扩散思想的具体应用。出的利用乘积密码实现混淆和扩散思想的具体应用。3.1.3 Feistel密码结构密码结构1.Feistel加密结构加密结构图图3.3是是Feistel网络示意图，加密算法的输入是分组网络示意图，加密算法的输入是分组长为长为2w的明文和一个密钥的明文和一个密钥K。将每组明文分成

20、左右将每组明文分成左右两半两半L0和和R0，在进行完在进行完n轮迭代后，左右两半再合轮迭代后，左右两半再合并到一起以产生密文分组。其第并到一起以产生密文分组。其第i轮迭代的输入为轮迭代的输入为前一轮输出的函数：前一轮输出的函数：其中其中Ki是第是第i轮用的子密钥，由加密密钥轮用的子密钥，由加密密钥K得到。一得到。一般地，各轮子密钥彼此不同而且与般地，各轮子密钥彼此不同而且与K也不同。也不同。111,iiiiiiLRRLF RK图图3.3 Feistel网络示意图网络示意图Feistel网络中每轮结构都相同，每轮中右半数据被网络中每轮结构都相同，每轮中右半数据被作用于轮函数作用于轮函数F后，再与

21、左半数据进行异或运算，后，再与左半数据进行异或运算，这一过程就是上面介绍的代换。每轮的轮函数的结这一过程就是上面介绍的代换。每轮的轮函数的结构都相同，但以不同的子密钥构都相同，但以不同的子密钥Ki作为参数。代换过作为参数。代换过程完成后，再交换左、右两半数据，这一过程称为程完成后，再交换左、右两半数据，这一过程称为置换。这种结构是置换。这种结构是Shannon提出的代换提出的代换置换网置换网络（络（substitution-permutation network,SPN）的特的特有形式。有形式。Feistel网络的实现与以下参数和特性有关：网络的实现与以下参数和特性有关：分组大小分组越大则安全

22、性越高，但加密速度分组大小分组越大则安全性越高，但加密速度就越慢。分组密码设计中最为普遍使用的分组大小就越慢。分组密码设计中最为普遍使用的分组大小是是64比特。比特。密钥大小密钥越长则安全性越高，但加密速度密钥大小密钥越长则安全性越高，但加密速度就越慢。现在普遍认为就越慢。现在普遍认为64比特或更短的密钥长度是比特或更短的密钥长度是不安全的，通常使用不安全的，通常使用128比特的密钥长度。比特的密钥长度。轮数单轮结构远不足以保证安全性，但多轮结轮数单轮结构远不足以保证安全性，但多轮结构可提供足够的安全性。典型地，轮数取为构可提供足够的安全性。典型地，轮数取为16。子密钥产生算法该算法的复杂性越

23、大，则密码子密钥产生算法该算法的复杂性越大，则密码分析的困难性就越大。分析的困难性就越大。轮函数轮函数的复杂性越大，密码分析的困难轮函数轮函数的复杂性越大，密码分析的困难性也越大。性也越大。在设计在设计Feistel网络时，还有以下两个方面需要考虑：网络时，还有以下两个方面需要考虑：快速的软件实现在很多情况中，算法是被镶嵌快速的软件实现在很多情况中，算法是被镶嵌在应用程序中，因而无法用硬件实现。此时算法的在应用程序中，因而无法用硬件实现。此时算法的执行速度是考虑的关键。执行速度是考虑的关键。算法容易分析如果算法能被无疑义地解释清楚，算法容易分析如果算法能被无疑义地解释清楚，就可容易地分析算法抵

24、抗攻击的能力，有助于设计就可容易地分析算法抵抗攻击的能力，有助于设计高强度的算法。高强度的算法。2.Feistel解密结构解密结构Feistel解密过程本质上和加密过程是一样的，算法解密过程本质上和加密过程是一样的，算法使用密文作为输入，但使用子密钥使用密文作为输入，但使用子密钥Ki的次序与加密的次序与加密过程相反，即第过程相反，即第1轮使用轮使用Kn，第第2轮使用轮使用Kn-1，最后一轮使用最后一轮使用K1。这一特性保证了解密和加密可采这一特性保证了解密和加密可采用同一算法。用同一算法。图图3.4的左边表示的左边表示16轮轮Feistel网络的加密过程，右边网络的加密过程，右边表示解密过程，

25、加密过程由上而下，解密过程由下表示解密过程，加密过程由上而下，解密过程由下而上。为清楚起见，加密算法每轮的左右两半用而上。为清楚起见，加密算法每轮的左右两半用LEi和和REi表示，解密算法每轮的左右两半用表示，解密算法每轮的左右两半用LDi和和RDi表示。图中右边标出了解密过程中每一轮的中表示。图中右边标出了解密过程中每一轮的中间值与左边加密过程中间值的对应关系，即加密过间值与左边加密过程中间值的对应关系，即加密过程第程第i轮的输出是轮的输出是LEiREi（表示链接），解密过程表示链接），解密过程第第16-i轮相应的输入是轮相应的输入是RDiLDi。图图3.4 Feistel加解密过程加解密过

26、程加密过程的最后一轮执行完后，两半输出再经交换，加密过程的最后一轮执行完后，两半输出再经交换，因此密文是因此密文是RE16LE16。解密过程取以上密文作为解密过程取以上密文作为同一算法的输入，即第同一算法的输入，即第1轮输入是轮输入是RE16LE16，等于等于加密过程第加密过程第16轮两半输出交换后的结果。下面证明轮两半输出交换后的结果。下面证明解密过程第解密过程第1轮的输出等于加密过程第轮的输出等于加密过程第16轮输入左轮输入左右两半的交换值。右两半的交换值。在加密过程中：在加密过程中：在解密过程中在解密过程中161516151516,LERERELEF REK101615100161615

27、16151516151615,LDRDLERERDLDF RDKREF REKLEF REKF REKLE所以解密过程第所以解密过程第1轮的输出为轮的输出为LE15RE15，等于加密等于加密过程第过程第16轮输入左右两半交换后的结果。容易证明轮输入左右两半交换后的结果。容易证明这种对应关系在这种对应关系在16轮中每轮都成立。一般地，加密轮中每轮都成立。一般地，加密过程的第过程的第i轮有轮有因此因此111,iiiiiiLERERELEF REK111,iiiiiiiiiRELELEREF REKREF LEK以上两式描述了加密过程中第以上两式描述了加密过程中第i轮的输入与第轮的输入与第i轮输轮输

28、出的函数关系，由此关系可得图出的函数关系，由此关系可得图3.4右边显示的右边显示的LDi和和RDi的取值关系。的取值关系。最后可以看到，解密过程第最后可以看到，解密过程第16轮的输出是轮的输出是RE0LE0，左右两半再经一次交换后即得最初的明文。左右两半再经一次交换后即得最初的明文。数据加密标准（数据加密标准（data encryption standard,DES）是迄今为止世界上最为广泛使用和流行的一种分组是迄今为止世界上最为广泛使用和流行的一种分组密码算法，它的分组长度为密码算法，它的分组长度为64比特，密钥长度为比特，密钥长度为56比特，它是由美国比特，它是由美国IBM公司研制的，是早

29、期的称作公司研制的，是早期的称作Lucifer密码的一种发展和修改。密码的一种发展和修改。DES在在1975年年3月月17日首次被公布在联邦记录中，经过大量的公开讨日首次被公布在联邦记录中，经过大量的公开讨论后，论后，DES于于1977年年1月月15日被正式批准并作为美日被正式批准并作为美国联邦信息处理标准，即国联邦信息处理标准，即FIPS-46，同年同年7月月15日开日开始生效。规定每隔始生效。规定每隔5年由美国国家保密局（年由美国国家保密局（national security agency,NSA）作出评估，并重新批准它是作出评估，并重新批准它是否继续作为联邦加密标准。否继续作为联邦加密标

30、准。3.2 数据加密标准数据加密标准最近的一次评估是在最近的一次评估是在1994年年1月，美国已决定月，美国已决定1998年年12月以后将不再使用月以后将不再使用DES。1997年年DESCHALL小组经过近小组经过近4个月的努力，通过个月的努力，通过Internet搜索了搜索了31016个密钥，找出了个密钥，找出了DES的密钥，恢复出了明文。的密钥，恢复出了明文。1998年年5月美国月美国EFF(electronics frontier foundation)宣布，他们以一台价值宣布，他们以一台价值20万美元的计算机改装成的万美元的计算机改装成的专用解密机，用专用解密机，用56小时破译了小时

31、破译了56 比特密钥的比特密钥的DES。美国国家标准和技术协会已征集并进行了几轮评估、美国国家标准和技术协会已征集并进行了几轮评估、筛选，产生了称之为筛选，产生了称之为AES(advanced encryption standard)的新加密标准。尽管如此，的新加密标准。尽管如此，DES对于推对于推动密码理论的发展和应用毕竟起了重大作用，对于动密码理论的发展和应用毕竟起了重大作用，对于掌握分组密码的基本理论、设计思想和实际应用仍掌握分组密码的基本理论、设计思想和实际应用仍然有着重要的参考价值，下面首先来描述这一算法。然有着重要的参考价值，下面首先来描述这一算法。图图3.5是是DES加密算法的框

32、图，其中明文分组长为加密算法的框图，其中明文分组长为64比特，密钥长为比特，密钥长为56比特。图的左边是明文的处理比特。图的左边是明文的处理过程，有过程，有3个阶段，首先是一个初始置换个阶段，首先是一个初始置换IP，用于用于重排明文分组的重排明文分组的64比特数据。然后是具有相同功能比特数据。然后是具有相同功能的的16轮变换，每轮中都有置换和代换运算，第轮变换，每轮中都有置换和代换运算，第16轮轮变换的输出分为左右两半，并被交换次序。最后再变换的输出分为左右两半，并被交换次序。最后再经过一个逆初始置换经过一个逆初始置换IP-1（为为IP的逆）从而产生的逆）从而产生64比特的密文。除初始置换和逆

33、初始置换外，比特的密文。除初始置换和逆初始置换外，DES的的结构和图结构和图3.3所示的所示的Feistel密码结构完全相同。密码结构完全相同。3.2.1 DES描述描述图图3.5 DES加密算法框图加密算法框图图图3.5的右边是使用的右边是使用56比特密钥的方法。密钥首先比特密钥的方法。密钥首先通过一个置换函数，然后，对加密过程的每一轮，通过一个置换函数，然后，对加密过程的每一轮，通过一个左循环移位和一个置换产生一个子密钥。通过一个左循环移位和一个置换产生一个子密钥。其中每轮的置换都相同，但由于密钥被重复迭代，其中每轮的置换都相同，但由于密钥被重复迭代，所以产生的每轮子密钥不相同。所以产生的

34、每轮子密钥不相同。1.初始置换初始置换DES的置换表见表的置换表见表3.2。（见。（见40页表页表3.2）表表3.2(a)和表和表3.2(b)分别给出了初始置换和逆初始置分别给出了初始置换和逆初始置换的定义，为了显示这两个置换的确是彼此互逆的，换的定义，为了显示这两个置换的确是彼此互逆的，考虑下面考虑下面64比特的输入比特的输入M：M1 M2 M3 M4 M5 M6 M7 M8M9 M10 M11 M12 M13 M14 M15 M16 M17 M18 M19 M20 M21 M22 M23 M24M25 M26 M27 M28 M29 M30 M31 M32M33 M34 M35 M36 M

35、37 M38 M39 M40M41 M42 M43 M44 M45 M46 M47 M48M49 M50 M51 M52 M53 M54 M55 M56M57 M58 M59 M60 M61 M62 M63 M64其中其中Mi是二元数字。由表是二元数字。由表3.2(a)得得X=IP(M)为：为：M58 M50 M42 M34 M26 M18 M10 M2M60 M52 M44 M36 M28 M20 M12 M4M62 M54 M46 M38 M30 M22 M14 M6M64 M56 M48 M40 M32 M24 M16 M8M57 M49 M41 M33 M25 M17 M9 M1M59

36、 M51 M43 M35 M27 M19 M11 M3M61 M53 M45 M37 M29 M21 M13 M5M63 M55 M47 M39 M31 M23 M15 M7如果再取逆初始置换如果再取逆初始置换Y=IP-1(X)=IP-1(IP(M)，可以可以看出，看出，M各位的初始顺序将被恢复。各位的初始顺序将被恢复。2.轮结构轮结构图图3.6是是DES加密算法的轮结构。加密算法的轮结构。图图3.6 DES加密算法的轮结构加密算法的轮结构首先看图的左半部分。将首先看图的左半部分。将64比特的轮输入分成各为比特的轮输入分成各为32比特的左、右两半，分别记为比特的左、右两半，分别记为L和和R。和

37、和Feistel网络一样，每轮变换可由以下公式表示：网络一样，每轮变换可由以下公式表示：111(,)iiiiiiLRRLF RK其中轮密钥其中轮密钥Ki为为48比特，函数比特，函数F(R,K)的计算过程如的计算过程如图图3.7所示。轮输入的右半部分所示。轮输入的右半部分R为为32比特，比特，R首先首先被扩展成被扩展成48比特，扩展过程由表比特，扩展过程由表3.2(c)定义，其中定义，其中将将R的的16个比特各重复一次。扩展后的个比特各重复一次。扩展后的48比特再与比特再与子密钥子密钥Ki异或，然后再通过一个异或，然后再通过一个S盒，产生盒，产生32比特比特的输出。该输出再经过一个由表的输出。该

38、输出再经过一个由表3.2(d)定义的置换，定义的置换，产生的结果即为函数产生的结果即为函数F(R,K)的输出。的输出。图图3.7 函数函数F(R,K)的计算过程的计算过程F中的代换由中的代换由8个个S盒组成，每个盒组成，每个S盒的输入长为盒的输入长为6比比特、输出长为特、输出长为4比特，其变换关系由表比特，其变换关系由表3.3定义，每定义，每个个S盒给出了盒给出了4个代换（由一个表的个代换（由一个表的4行给出）。行给出）。（见（见42页表页表3.3）对每个盒对每个盒Si，其其6比特输入中，第比特输入中，第1个和第个和第6个比特个比特形成一个形成一个2位二进制数，用来选择位二进制数，用来选择Si

39、的的4个代换中的个代换中的一个。一个。6比特输入中，中间比特输入中，中间4位用来选择列。行和列位用来选择列。行和列选定后，得到其交叉位置的十进制数，将这个数表选定后，得到其交叉位置的十进制数，将这个数表示为示为4位二进制数即得这一位二进制数即得这一S盒的输出。例如，盒的输出。例如，S1 的输入为的输入为011001，行选为，行选为01（即第（即第1行），列选为行），列选为1100（即第（即第12列），行列交叉位置的数为列），行列交叉位置的数为9，其，其4位位二进制表示为二进制表示为1001，所以，所以S1的输出为的输出为1001。S盒的每一行定义了一个可逆代换，图盒的每一行定义了一个可逆代换，

40、图3.2（在（在3.1.1节）表示节）表示S1第第0行所定义的代换。行所定义的代换。3.密钥的产生密钥的产生再看图再看图3.5和图和图3.6，输入算法的，输入算法的56比特密钥首先经比特密钥首先经过一个置换运算，该置换由表过一个置换运算，该置换由表3.4(a)给出，然后将给出，然后将置换后的置换后的56比特分为各为比特分为各为28比特的左、右两半，分比特的左、右两半，分别记为别记为C0和和D0。在第在第i 轮分别对轮分别对Ci-1和和Di-1进行左循进行左循环移位，所移位数由表环移位，所移位数由表3.4(c)给出。移位后的结果给出。移位后的结果作为求下一轮子密钥的输入，同时也作为置换选择作为求

41、下一轮子密钥的输入，同时也作为置换选择2的输入。通过置换选择的输入。通过置换选择2产生的产生的48比特的比特的Ki，即为即为本轮的子密钥，作为函数本轮的子密钥，作为函数F(Ri-1,Ki)的输入。其中置的输入。其中置换选择换选择2由表由表3.4(b)定义。（见定义。（见44页表页表3.4）4.解密解密和和Feistel密码一样，密码一样，DES的解密和加密使用同一算的解密和加密使用同一算法，但子密钥使用的顺序相反。法，但子密钥使用的顺序相反。为了提高为了提高DES的安全性，并利用实现的安全性，并利用实现DES的现有软的现有软硬件，可将硬件，可将DES算法在多密钥下多重使用。算法在多密钥下多重使

42、用。二重二重DES是多重使用是多重使用DES时最简单的形式，如图时最简单的形式，如图3.8所示。其中明文为所示。其中明文为P，两个加密密钥为两个加密密钥为K1和和K2，密密文为：文为：解密时，以相反顺序使用两个密钥：解密时，以相反顺序使用两个密钥：3.2.2 二重二重DES21 KKCEEP12 KKPDDC图图3.8 二重二重DES因此，二重因此，二重DES所用密钥长度为所用密钥长度为112比特，强度极比特，强度极大地增加。然而，假设对任意两个密钥大地增加。然而，假设对任意两个密钥K1和和K2，能够找出另一密钥能够找出另一密钥K3，使得使得213 KKKEEPEP那么，二重那么，二重DES以

43、及多重以及多重DES都没有意义，因为它都没有意义，因为它们与们与56比特密钥的单重比特密钥的单重DES等价，好在这种假设对等价，好在这种假设对DES并不成立。将并不成立。将DES加密过程加密过程64比特分组到比特分组到64比比特分组的映射看作一个置换，如果考虑特分组的映射看作一个置换，如果考虑264个所有个所有可能的输入分组，则密钥给定后，可能的输入分组，则密钥给定后，DES的加密将把的加密将把每个输入分组映射到一个惟一的输出分组。否则，每个输入分组映射到一个惟一的输出分组。否则，如果有两个输入分组被映射到同一分组，则解密过如果有两个输入分组被映射到同一分组，则解密过程就无法实施。对程就无法实

44、施。对264个输入分组，总映射个数个输入分组，总映射个数为为 。2064102!10另一方面，对每个不同的密钥，另一方面，对每个不同的密钥，DES都定义了一个都定义了一个映射，总映射数为映射，总映射数为256N/2，则令则令如果如果T6有所不同。有所不同。当当Nk6时，扩展算法如下时，扩展算法如下 KeyExpansion(byteKey4*Nk,WNb*(Nr+1)for(i=0;i Nk;i+)Wi=(Key4*i,Key4*i+1,Key4*i+2,Key4*i+3);for(i=Nk;i 6时，扩展算法如下：时，扩展算法如下：KeyExpansion(byte Key4*Nk,WNb*

45、(Nr+1)for(i=0;i Nk;i+)Wi=(Key4*i,Key4*i+1,Key4*i+2,Key4*i+3);for(i=Nk;i 6与与Nk6的密钥扩展算法的区别在于：当的密钥扩展算法的区别在于：当i为为Nk的的4的倍数时，须先将前一个字的倍数时，须先将前一个字Wi-1经过经过SubByte变换。变换。以上两个算法中，以上两个算法中，Rconi/Nk 为轮常数，其值与为轮常数，其值与Nk无关，定义为（字节用十六进制表示，同时理无关，定义为（字节用十六进制表示，同时理解为解为GF(28)上的元素）：上的元素）：Rcon i=(RCi,00,00,00)其中其中RCi 是是GF(28

46、)中值为中值为xi-1的元素，因此的元素，因此RC1=1(即即01)RCi=x(即即02)RCi-1=xi-1(2)轮密钥选取轮密钥选取轮密钥轮密钥i（即第即第i 个轮密钥）由轮密钥缓冲字个轮密钥）由轮密钥缓冲字WNb*i到到WNb*(i+1)给出，如图给出，如图3.23所示。所示。图图3.23 Nb=6且且Nk=4时的密钥扩展与轮密钥选取时的密钥扩展与轮密钥选取4.加密算法加密算法加密算法为顺序完成以下操作：初始的密钥加；加密算法为顺序完成以下操作：初始的密钥加；(Nr-1)轮迭代；一个结尾轮。即轮迭代；一个结尾轮。即Rijndael(State,CipherKey)KeyExpansion

47、(CipherKey,ExpandedKey);AddRoundKey(State,ExpandedKey);for(i=1;i Nr;i+)Round(State,ExpandedKey+Nb*i);FinalRound(State,ExpandedKey+Nb*Nr)其中其中CipherKey是种子密钥，是种子密钥，ExpandedKey是扩展是扩展密钥。密钥扩展可以事先进行（预计算），且密钥。密钥扩展可以事先进行（预计算），且Rijndael密码的加密算法可以用这一扩展密钥来描密码的加密算法可以用这一扩展密钥来描述，即述，即Rijndael(State,ExpandedKey)AddRo

48、undKey(State,ExpandedKey);for(i=1;i Nr;i+)Round(State,ExpandedKey+Nb*i);FinalRound(State,ExpandedKey+Nb*Nr)5.加解密的相近程度及解密算法加解密的相近程度及解密算法首先给出几个引理。首先给出几个引理。引理引理3.1 设字节代换（设字节代换（ByteSub）、）、行移位行移位（ShiftRow）的逆变换分别为的逆变换分别为InvByteSub、InvShiftRow。则组合部件则组合部件“ByteSubShiftRow”的逆变换为的逆变换为“InvByteSubInvShiftRow”。证明

49、：组合部件证明：组合部件“ByteSubShiftRow”的逆变换原的逆变换原本为本为“InvShiftRowInvByteSub”。由于字节代换由于字节代换（ByteSub）是对每个字节进行相同的变换，故是对每个字节进行相同的变换，故“InvShiftRow”与与“InvByteSub”两个计算部件可两个计算部件可以交换顺序。（证毕）以交换顺序。（证毕）引理引理3.2 设列混合（设列混合（MixColumn）的逆变换为的逆变换为InvMixColumn。则列混合部件与密钥加部件则列混合部件与密钥加部件（AddRoundKey）的组合部件的组合部件“MixColumnAddRoundKey(,

50、Key)”的逆变换的逆变换为为“InvMixColumnAddRoundKey(,InvKey)”。其中密钥其中密钥InvKey与与Key的关系为：的关系为：InvKey=InvMixColumn(Key)。证明：组合部件证明：组合部件“MixColumnAddRoundKey(,Key)”的逆变换原本为的逆变换原本为“AddRoundKey(,Key)InvMixColumn”，由于列混合由于列混合（MixColumn）实际上是线性空间实际上是线性空间GF(28)4上的可上的可逆线性变换，因此逆线性变换，因此“AddRoundKey(,Key)InvMixColumn”=“InvMixCol

51、umnAddRoundKey(,InvMixColumn(Key)”（证毕）证毕）引理引理3.3 将某一轮的后两个计算部件和下一轮的前将某一轮的后两个计算部件和下一轮的前两个计算部件组成组合部件，该组合部件的程序为两个计算部件组成组合部件，该组合部件的程序为MixColumn(State)；AddRoundKey(State,Key(i);ByteSub(State);ShiftRow(State)则该组合部件的逆变换程序为则该组合部件的逆变换程序为InvByteSub(State);InvShiftRow(State);InvMixColumn(State);AddRoundKey(Stat

52、e,InvMixColumn(Key(i)证明：这是引理证明：这是引理3.1和引理和引理3.2的直接推论。的直接推论。注意到在引理注意到在引理3.3所描述的逆变换中，第所描述的逆变换中，第2步到第步到第4步在形状上很像加密算法的轮函数，这将是解密算步在形状上很像加密算法的轮函数，这将是解密算法的轮函数。注意到结尾轮只有法的轮函数。注意到结尾轮只有3个计算部件，因个计算部件，因此可以得到如下定理。此可以得到如下定理。定理定理3.2 Rijndael密码的解密算法为顺序完成以下操密码的解密算法为顺序完成以下操作：初始的密钥加；作：初始的密钥加；(Nr-1)轮迭代；一个结尾轮。轮迭代；一个结尾轮。其

53、中解密算法的轮函数为其中解密算法的轮函数为InvRound(State,RoundKey)InvByteSub(State);InvShiftRow(State);InvMixColumn(State);AddRoundKey(State,RoundKey)解密算法的结尾轮为解密算法的结尾轮为InvFinalRound(State,RoundKey)InvByteSub(State);InvShiftRow(State);AddRoundKey(State,RoundKey)设加密算法的初始密钥加、第设加密算法的初始密钥加、第1轮、第轮、第2轮、轮、第、第Nr轮的子密钥依次为轮的子密钥依次为k

54、(0),k(1),k(2),k(Nr-1),k(Nr)则解密算法的初始密钥加、第则解密算法的初始密钥加、第1轮、第轮、第2轮、轮、第、第Nr轮的子密钥依次为轮的子密钥依次为k(Nr),InvMixColumn(k(Nr-1),InvMixColumn(k(Nr-2),InvMixColumn(k(1),k(0)。证明：这是上述证明：这是上述3个引理的直接推论。个引理的直接推论。综上所述，综上所述，Rijndael密码的解密算法与加密算法的密码的解密算法与加密算法的计算网络相同，只是将各计算部件换为对应的逆部计算网络相同，只是将各计算部件换为对应的逆部件。件。3-1(1)设设M是是M的逐比特取补

55、，证明在的逐比特取补，证明在DES中，如中，如果对明文分组和加密密钥都逐比特取补，那么得到果对明文分组和加密密钥都逐比特取补，那么得到的密文也是原密文的逐比特取补，即的密文也是原密文的逐比特取补，即如果如果Y=DESK(X)那么那么Y=DESK(X)提示：提示：对任意两个长度相等的比特串对任意两个长度相等的比特串A和和B，证明证明(AB)=AB。(2)对对DES进行穷搜索攻击时，需要在由进行穷搜索攻击时，需要在由256个密钥个密钥构成的密钥空间进行。能否根据构成的密钥空间进行。能否根据(1)的结论减小进的结论减小进行穷搜索攻击时所用的密钥空间。行穷搜索攻击时所用的密钥空间。习题习题3-2 证明

56、证明DES的解密变换是加密变换的逆。的解密变换是加密变换的逆。3-3 在在DES的的ECB模式中，如果在密文分组中有一模式中，如果在密文分组中有一个错误，解密后仅相应的明文分组受到影响。然而个错误，解密后仅相应的明文分组受到影响。然而在在CBC模式中，将有错误传播。例如在图模式中，将有错误传播。例如在图3.11中中C1中的一个错误明显地将影响中的一个错误明显地将影响P1和和P2的结果。的结果。(1)P2后的分组是否受到影响？后的分组是否受到影响？(2)设加密前的明文分组设加密前的明文分组P1中有中有1比特的错误，问这比特的错误，问这一错误将在多少个密文分组中传播？对接收者产生一错误将在多少个密

57、文分组中传播？对接收者产生什么影响？什么影响？3-4 在在8比特比特CFB模式中，如果在密文字符中出现模式中，如果在密文字符中出现1比特的错误，问该错误能传播多远？比特的错误，问该错误能传播多远？3-5 在实现在实现IDEA时，最困难的部分是模时，最困难的部分是模216+1乘法乘法运算。以下关系给出了实现模乘法的一种有效方法，运算。以下关系给出了实现模乘法的一种有效方法，其中其中a和和b是两个是两个n比特的非比特的非0整数：整数：注意：注意：(ab mod 2n)相应于相应于ab的的n个最低有效位，个最低有效位，(ab div 2n)是是ab右移右移n位。位。mod2div 2,mod2div

58、 2mod 21mod2div 221,mod2div 2nnnnnnnnnnababababababababab(1)证明存在惟一的非负整数证明存在惟一的非负整数q和和r使得使得ab=q(2n+1)+r。(2)求求q和和r的上下界。的上下界。(3)证明证明q+r2n+1。(4)求求(ab div 2n)关于关于q的表达式。的表达式。(5)求求(ab mod 2n)关于关于q和和r的表达式。的表达式。(6)用用(4)和和(5)的结果求的结果求r的表达式，说明的表达式，说明r的含义。的含义。3-6(1)在在IDEA的模乘运算中，为什么将模数取为的模乘运算中，为什么将模数取为216+1而不是而不是216?(2)在在IDEA的模加运算中，为什么将模数取为的模加运算中，为什么将模数取为216而而不是不是216+1?