《分组密码体制》PPT课件.ppt

第第3章章 分组密码体制分组密码体制3.1 分组密码概述分组密码概述3.2 数据加密标准数据加密标准3.3 差分密码分析与线性密码分析差分密码分析与线性密码分析3.4 分组密码的运行模式分组密码的运行模式3.5 IDEA3.6 AES算法算法Rijndael习题习题在许多密码系统中，单钥分组密码是系统安全的一个在许多密码系统中，单钥分组密码是系统安全的一个重要组成部分，用分组密码易于构造伪随机数生成器、重要组成部分，用分组密码易于构造伪随机数生成器、流密码、消息认证码（流密码、消息认证码（MAC）和杂凑函数等，还可和杂凑函数等，还可进而成为消息认证技术、数据完整性机制、实体认证进而成为消息认证技术、数据完整性机制、实体认证协议以及单钥数字签字体制的核心组成部分。实际应协议以及单钥数字签字体制的核心组成部分。实际应用中对于分组密码可能提出多方面的要求，除了安全用中对于分组密码可能提出多方面的要求，除了安全性外，还有运行速度、存储量（程序的长度、数据分性外，还有运行速度、存储量（程序的长度、数据分组长度、高速缓存大小）、实现平台（硬件、软件、组长度、高速缓存大小）、实现平台（硬件、软件、芯片）、运行模式等限制条件。这些都需要与安全性芯片）、运行模式等限制条件。这些都需要与安全性要求之间进行适当的折中选择。要求之间进行适当的折中选择。3.1分组密码概述分组密码概述分组密码是将明文消息编码表示后的数字序列分组密码是将明文消息编码表示后的数字序列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所示。所示。它与流密码不同之处在于输出的每一位数字不是只与它与流密码不同之处在于输出的每一位数字不是只与相应时刻输入的明文数字有关，而是与一组长为相应时刻输入的明文数字有关，而是与一组长为n的的明文数字有关。在相同密钥下，分组密码对长为明文数字有关。在相同密钥下，分组密码对长为n的的输入明文组所实施的变换是等同的，所以只需研究对输入明文组所实施的变换是等同的，所以只需研究对任一组明文数字的变换规则。这种密码实质上是字长任一组明文数字的变换规则。这种密码实质上是字长为为n的数字序列的代换密码。的数字序列的代换密码。图图3.1 分组密码框图分组密码框图通常取通常取m=n。若若mn，则为有数据扩展的分组密码；则为有数据扩展的分组密码；若若mn，则为有数据压缩的分组密码。在二元情况下，则为有数据压缩的分组密码。在二元情况下，x和和y均为二元数字序列，它们的每个分量均为二元数字序列，它们的每个分量xi，yiGF(2)。本节将主要讨论二元情况。设计的算法本节将主要讨论二元情况。设计的算法应满足下述要求：应满足下述要求：分组长度分组长度n要足够大，使分组代换字母表中的元素要足够大，使分组代换字母表中的元素个数个数2n足够大，防止明文穷举攻击法奏效。足够大，防止明文穷举攻击法奏效。DES、IDEA、FEAL和和LOKI等分组密码都采用等分组密码都采用n=64，在生在生日攻击下用日攻击下用232组密文成功概率为组密文成功概率为1/2，同时要求，同时要求23264b=215MB存贮，故采用穷举攻击是不现实的。存贮，故采用穷举攻击是不现实的。密钥量要足够大（即置换子集中的元素足够多），密钥量要足够大（即置换子集中的元素足够多），尽可能消除弱密钥并使所有密钥同等地好，以防止密尽可能消除弱密钥并使所有密钥同等地好，以防止密钥穷举攻击奏效。但密钥又不能过长，以便于密钥的钥穷举攻击奏效。但密钥又不能过长，以便于密钥的管理。管理。DES采用采用56比特密钥，看来太短了，比特密钥，看来太短了，IDEA采采用用128比特密钥，据估计，在今后比特密钥，据估计，在今后3040年内采用年内采用80 比特密钥是足够安全的。比特密钥是足够安全的。由密钥确定置换的算法要足够复杂，充分实现明由密钥确定置换的算法要足够复杂，充分实现明文与密钥的扩散和混淆，没有简单的关系可循，能抗文与密钥的扩散和混淆，没有简单的关系可循，能抗击各种已知的攻击，如差分攻击和线性攻击；有高的击各种已知的攻击，如差分攻击和线性攻击；有高的非线性阶数，实现复杂的密码变换；使对手破译时除非线性阶数，实现复杂的密码变换；使对手破译时除了用穷举法外，无其它捷径可循。了用穷举法外，无其它捷径可循。加密和解密运算简单，易于软件和硬件高速实现。加密和解密运算简单，易于软件和硬件高速实现。如将分组如将分组n化分为子段，每段长为化分为子段，每段长为8、16或者或者32。在以。在以软件实现时，应选用简单的运算，使作用于子段上的软件实现时，应选用简单的运算，使作用于子段上的密码运算易于以标准处理器的基本运算，如加、乘、密码运算易于以标准处理器的基本运算，如加、乘、移位等实现，避免用以软件难于实现的逐比特置换。移位等实现，避免用以软件难于实现的逐比特置换。为了便于硬件实现，加密和解密过程之间的差别应仅为了便于硬件实现，加密和解密过程之间的差别应仅在于由秘密密钥所生成的密钥表不同而已。这样，加在于由秘密密钥所生成的密钥表不同而已。这样，加密和解密就可用同一器件实现。设计的算法采用规则密和解密就可用同一器件实现。设计的算法采用规则的模块结构，如多轮迭代等，以便于软件和的模块结构，如多轮迭代等，以便于软件和VLSI快快速实现。此外，差错传播和数据扩展要尽可能地小。速实现。此外，差错传播和数据扩展要尽可能地小。数据扩展。一般无数据扩展，在采用同态置换和数据扩展。一般无数据扩展，在采用同态置换和随机化加密技术时可引入数据扩展。随机化加密技术时可引入数据扩展。差错传播尽可能地小。差错传播尽可能地小。要实现上述几点要求并不容易。首先，要在理论上研要实现上述几点要求并不容易。首先，要在理论上研究有效而可靠的设计方法，而后进行严格的安全性检究有效而可靠的设计方法，而后进行严格的安全性检验，并且要易于实现。验，并且要易于实现。下面介绍设计分组密码时的一些常用方法。下面介绍设计分组密码时的一些常用方法。如果明文和密文的分组长都为如果明文和密文的分组长都为n比特，则明文的每一比特，则明文的每一个分组都有个分组都有2n个可能的取值。为使加密运算可逆（使个可能的取值。为使加密运算可逆（使解密运算可行），明文的每一个分组都应产生惟一的解密运算可行），明文的每一个分组都应产生惟一的一个密文分组，这样的变换是可逆的，称明文分组到一个密文分组，这样的变换是可逆的，称明文分组到密文分组的可逆变换为代换。不同可逆变换的个数有密文分组的可逆变换为代换。不同可逆变换的个数有2n!个。个。3.1.1 代换代换图图3.2表示表示n=4的代换密码的一般结构，的代换密码的一般结构，4比特输入产比特输入产生生16个可能输入状态中的一个，由代换结构将这一状个可能输入状态中的一个，由代换结构将这一状态映射为态映射为16个可能输出状态中的一个，每一输出状态个可能输出状态中的一个，每一输出状态由由4个密文比特表示。加密映射和解密映射可由代换个密文比特表示。加密映射和解密映射可由代换表来定义，如表表来定义，如表3.1所示。这种定义法是分组密码最所示。这种定义法是分组密码最常用的形式，能用于定义明文和密文之间的任何可逆常用的形式，能用于定义明文和密文之间的任何可逆映射。（见映射。（见33页表页表3.1）图图3.2 代换结构代换结构但这种代换结构在实用中还有一些问题需考虑。如果但这种代换结构在实用中还有一些问题需考虑。如果分组长度太小，如分组长度太小，如n=4，系统则等价于古典的代换密系统则等价于古典的代换密码，容易通过对明文的统计分析而被攻破。这个弱点码，容易通过对明文的统计分析而被攻破。这个弱点不是代换结构固有的，只是因为分组长度太小。如果不是代换结构固有的，只是因为分组长度太小。如果分组长度分组长度n足够大，而且从明文到密文可有任意可逆足够大，而且从明文到密文可有任意可逆的代换，那么明文的统计特性将被隐藏而使以上的攻的代换，那么明文的统计特性将被隐藏而使以上的攻击不能奏效。击不能奏效。然而，从实现的角度来看，分组长度很大的可逆代换然而，从实现的角度来看，分组长度很大的可逆代换结构是不实际的。仍以表结构是不实际的。仍以表3.1为例，该表定义了为例，该表定义了n=4时时从明文到密文的一个可逆映射，其中第从明文到密文的一个可逆映射，其中第2列是每个明列是每个明文分组对应的密文分组的值，可用来定义这个可逆映文分组对应的密文分组的值，可用来定义这个可逆映射。因此从本质上来说，第射。因此从本质上来说，第2列是从所有可能映射中列是从所有可能映射中决定某一特定映射的密钥。这个例子中，密钥需要决定某一特定映射的密钥。这个例子中，密钥需要64比特。一般地，对比特。一般地，对n比特的代换结构，密钥的大小是比特的代换结构，密钥的大小是n2n比特。如对比特。如对64比特的分组，密钥大小应是比特的分组，密钥大小应是64264=2701021比特，因此难以处理。比特，因此难以处理。实际中常将实际中常将n分成较小的段，例如可选分成较小的段，例如可选n=rn0，其中其中r和和n0都是正整数，将设计都是正整数，将设计n个变量的代换变为设计个变量的代换变为设计r个个较小的子代换，而每个子代换只有较小的子代换，而每个子代换只有n0个输入变量。一个输入变量。一般般n0都不太大，称每个子代换为代换盒，简称为都不太大，称每个子代换为代换盒，简称为S盒。盒。例如例如DES中将输入为中将输入为48比特、输出为比特、输出为32比特的代换用比特的代换用8个个S盒来实现，每个盒来实现，每个S盒的输入端数仅为盒的输入端数仅为6比特，输比特，输出端数仅为出端数仅为4比特。比特。扩散和混淆是由扩散和混淆是由Shannon提出的设计密码系统的两个提出的设计密码系统的两个基本方法，目的是抗击敌手对密码系统的统计分析。基本方法，目的是抗击敌手对密码系统的统计分析。如果敌手知道明文的某些统计特性，如消息中不同字如果敌手知道明文的某些统计特性，如消息中不同字母出现的频率、可能出现的特定单词或短语，而且这母出现的频率、可能出现的特定单词或短语，而且这些统计特性以某种方式在密文中反映出来，那么敌手些统计特性以某种方式在密文中反映出来，那么敌手就有可能得出加密密钥或其一部分，或者得出包含加就有可能得出加密密钥或其一部分，或者得出包含加密密钥的一个可能的密钥集合。在密密钥的一个可能的密钥集合。在Shannon称之为理称之为理想密码的密码系统中，密文的所有统计特性都与所使想密码的密码系统中，密文的所有统计特性都与所使用的密钥独立。图用的密钥独立。图3.2讨论的代换密码就是这样的一讨论的代换密码就是这样的一个密码系统，然而它是不实用的。个密码系统，然而它是不实用的。3.1.2 扩散和混淆扩散和混淆所谓扩散所谓扩散，就是将明文的统计特性散布到密文中去，就是将明文的统计特性散布到密文中去，实现方式是使得明文的每一位影响密文中多位的值，实现方式是使得明文的每一位影响密文中多位的值，等价于说密文中每一位均受明文中多位影响。例如对等价于说密文中每一位均受明文中多位影响。例如对英文消息英文消息M=m1m2m3的加密操作的加密操作其中其中ord(mi)是求字母是求字母mi对应的序号，对应的序号，chr(i)是求序号是求序号i对应的字母。这时明文的统计特性将被散布到密文中，对应的字母。这时明文的统计特性将被散布到密文中，因而每一字母在密文中出现的频率比在明文中出现的因而每一字母在密文中出现的频率比在明文中出现的频率更接近于相等，双字母及多字母出现的频率也更频率更接近于相等，双字母及多字母出现的频率也更接近于相等。在二元分组密码中，可对数据重复执行接近于相等。在二元分组密码中，可对数据重复执行某个置换，再对这一置换作用于一函数，可获得扩散。某个置换，再对这一置换作用于一函数，可获得扩散。分组密码在将明文分组依靠密钥变换到密文分组时，分组密码在将明文分组依靠密钥变换到密文分组时，扩散的目的是使明文和密文之间的统计关系变得尽可扩散的目的是使明文和密文之间的统计关系变得尽可能复杂，以使敌手无法得到密钥；能复杂，以使敌手无法得到密钥；混淆是混淆是使密文和密使密文和密钥之间的统计关系变得尽可能复杂，以使敌手无法得钥之间的统计关系变得尽可能复杂，以使敌手无法得到密钥。因此即使敌手能得到密文的一些统计关系，到密钥。因此即使敌手能得到密文的一些统计关系，由于密钥和密文之间的统计关系复杂化，敌手也无法由于密钥和密文之间的统计关系复杂化，敌手也无法得到密钥。使用复杂的代换算法可以得到预期的混淆得到密钥。使用复杂的代换算法可以得到预期的混淆效果，而简单的线性代换函数得到的混淆效果则不够效果，而简单的线性代换函数得到的混淆效果则不够理想。理想。扩散和混淆成功地实现了分组密码的本质属性，因而扩散和混淆成功地实现了分组密码的本质属性，因而成为设计现代分组密码的基础。成为设计现代分组密码的基础。很多分组密码的结构从本质上说都是基于一个称为很多分组密码的结构从本质上说都是基于一个称为Feistel网络的结构。网络的结构。Feistel提出利用乘积密码可获得提出利用乘积密码可获得简单的代换密码，乘积密码指顺序地执行两个或多个简单的代换密码，乘积密码指顺序地执行两个或多个基本密码系统，使得最后结果的密码强度高于每个基基本密码系统，使得最后结果的密码强度高于每个基本密码系统产生的结果，本密码系统产生的结果，Feistel还提出了实现代换和还提出了实现代换和置换的方法。其思想实际上是置换的方法。其思想实际上是Shannon提出的利用乘提出的利用乘积密码实现混淆和扩散思想的具体应用。积密码实现混淆和扩散思想的具体应用。3.1.3 Feistel密码结构密码结构1.Feistel加密结构加密结构图图3.3是是Feistel网络示意图，加密算法的输入是分组长网络示意图，加密算法的输入是分组长为为2w的明文和一个密钥的明文和一个密钥K。将每组明文分成左右两半将每组明文分成左右两半L0和和R0，在进行完在进行完n轮迭代后，左右两半再合并到一轮迭代后，左右两半再合并到一起以产生密文分组。其第起以产生密文分组。其第i轮迭代的输入为前一轮输轮迭代的输入为前一轮输出的函数：出的函数：其中其中Ki是第是第i轮用的子密钥，由加密密钥轮用的子密钥，由加密密钥K得到。一般得到。一般地，各轮子密钥彼此不同而且与地，各轮子密钥彼此不同而且与K也不同。也不同。图图3.3 Feistel网络示意图网络示意图Feistel网络中每轮结构都相同，每轮中右半数据被作网络中每轮结构都相同，每轮中右半数据被作用于轮函数用于轮函数F后，再与左半数据进行异或运算，这一后，再与左半数据进行异或运算，这一过程就是上面介绍的代换。每轮的轮函数的结构都相过程就是上面介绍的代换。每轮的轮函数的结构都相同，但以不同的子密钥同，但以不同的子密钥Ki作为参数。代换过程完成后，作为参数。代换过程完成后，再交换左、右两半数据，这一过程称为置换。这种结再交换左、右两半数据，这一过程称为置换。这种结构是构是Shannon提出的代换提出的代换置换网络置换网络（substitution-permutation network,SPN）的特有形的特有形式。式。Feistel网络的实现与以下参数和特性有关：网络的实现与以下参数和特性有关：分组大小分组越大则安全性越高，但加密速度就分组大小分组越大则安全性越高，但加密速度就越慢。分组密码设计中最为普遍使用的分组大小是越慢。分组密码设计中最为普遍使用的分组大小是64比特。比特。密钥大小密钥越长则安全性越高，但加密速度就密钥大小密钥越长则安全性越高，但加密速度就越慢。现在普遍认为越慢。现在普遍认为64比特或更短的密钥长度是不安比特或更短的密钥长度是不安全的，通常使用全的，通常使用128比特的密钥长度。比特的密钥长度。轮数单轮结构远不足以保证安全性，但多轮结构轮数单轮结构远不足以保证安全性，但多轮结构可提供足够的安全性。典型地，轮数取为可提供足够的安全性。典型地，轮数取为16。子密钥产生算法该算法的复杂性越大，则密码分子密钥产生算法该算法的复杂性越大，则密码分析的困难性就越大。析的困难性就越大。轮函数轮函数的复杂性越大，密码分析的困难性轮函数轮函数的复杂性越大，密码分析的困难性也越大。也越大。在设计在设计Feistel网络时，还有以下两个方面需要考虑：网络时，还有以下两个方面需要考虑：快速的软件实现在很多情况中，算法是被镶嵌在快速的软件实现在很多情况中，算法是被镶嵌在应用程序中，因而无法用硬件实现。此时算法的执行应用程序中，因而无法用硬件实现。此时算法的执行速度是考虑的关键。速度是考虑的关键。算法容易分析如果算法能被无疑义地解释清楚，算法容易分析如果算法能被无疑义地解释清楚，就可容易地分析算法抵抗攻击的能力，有助于设计高就可容易地分析算法抵抗攻击的能力，有助于设计高强度的算法。强度的算法。2.Feistel解密结构解密结构Feistel解密过程本质上和加密过程是一样的，算法使解密过程本质上和加密过程是一样的，算法使用密文作为输入，但使用子密钥用密文作为输入，但使用子密钥Ki的次序与加密过程的次序与加密过程相反，即第相反，即第1轮使用轮使用Kn，第第2轮使用轮使用Kn-1，最后最后一轮使用一轮使用K1。这一特性保证了解密和加密可采用同这一特性保证了解密和加密可采用同一算法。一算法。图图3.4的左边表示的左边表示16轮轮Feistel网络的加密过程，右边表网络的加密过程，右边表示解密过程，加密过程由上而下，解密过程由下而上。示解密过程，加密过程由上而下，解密过程由下而上。为清楚起见，加密算法每轮的左右两半用为清楚起见，加密算法每轮的左右两半用LEi和和REi表示，解密算法每轮的左右两半用表示，解密算法每轮的左右两半用LDi和和RDi表示。表示。图中右边标出了解密过程中每一轮的中间值与左边加图中右边标出了解密过程中每一轮的中间值与左边加密过程中间值的对应关系，即加密过程第密过程中间值的对应关系，即加密过程第i轮的输出轮的输出是是LEiREi（表示链接），解密过程第表示链接），解密过程第16-i轮相应的轮相应的输入是输入是RDiLDi。图图3.4 Feistel加解密过程加解密过程加密过程的最后一轮执行完后，两半输出再经交换，加密过程的最后一轮执行完后，两半输出再经交换，因此密文是因此密文是RE16LE16。解密过程取以上密文作为同解密过程取以上密文作为同一算法的输入，即第一算法的输入，即第1轮输入是轮输入是RE16LE16，等于加密等于加密过程第过程第16轮两半输出交换后的结果。下面证明解密过轮两半输出交换后的结果。下面证明解密过程第程第1轮的输出等于加密过程第轮的输出等于加密过程第16轮输入左右两半的轮输入左右两半的交换值。交换值。在加密过程中：在加密过程中：在解密过程中在解密过程中所以解密过程第所以解密过程第1轮的输出为轮的输出为LE15RE15，等于加密过等于加密过程第程第16轮输入左右两半交换后的结果。容易证明这种轮输入左右两半交换后的结果。容易证明这种对应关系在对应关系在16轮中每轮都成立。一般地，加密过程的轮中每轮都成立。一般地，加密过程的第第i轮有轮有因此因此以上两式描述了加密过程中第以上两式描述了加密过程中第i轮的输入与第轮的输入与第i轮输出轮输出的函数关系，由此关系可得图的函数关系，由此关系可得图3.4右边显示的右边显示的LDi和和RDi的取值关系。的取值关系。最后可以看到，解密过程第最后可以看到，解密过程第16轮的输出是轮的输出是RE0LE0，左右两半再经一次交换后即得最初的明文。左右两半再经一次交换后即得最初的明文。数据加密标准（数据加密标准（data encryption standard,DES）是是迄今为止世界上最为广泛使用和流行的一种分组密码迄今为止世界上最为广泛使用和流行的一种分组密码算法，它的分组长度为算法，它的分组长度为64比特，密钥长度为比特，密钥长度为56比特，比特，它是由美国它是由美国IBM公司研制的，是早期的称作公司研制的，是早期的称作Lucifer密码的一种发展和修改。密码的一种发展和修改。DES在在1975年年3月月17日首次日首次被公布在联邦记录中，经过大量的公开讨论后，被公布在联邦记录中，经过大量的公开讨论后，DES于于1977年年1月月15日被正式批准并作为美国联邦信息处日被正式批准并作为美国联邦信息处理标准，即理标准，即FIPS-46，同年同年7月月15日开始生效。规定每日开始生效。规定每隔隔5年由美国国家保密局（年由美国国家保密局（national security agency,NSA）作出评估，并重新批准它是否继续作为联邦加作出评估，并重新批准它是否继续作为联邦加密标准。密标准。3.2 数据加密标准数据加密标准最近的一次评估是在最近的一次评估是在1994年年1月，美国已决定月，美国已决定1998年年12月以后将不再使用月以后将不再使用DES。1997年年DESCHALL小组小组经过近经过近4个月的努力，通过个月的努力，通过Internet搜索了搜索了31016个密个密钥，找出了钥，找出了DES的密钥，恢复出了明文。的密钥，恢复出了明文。1998年年5月月美国美国EFF(electronics frontier foundation)宣布，他们宣布，他们以一台价值以一台价值20万美元的计算机改装成的专用解密机，万美元的计算机改装成的专用解密机，用用56小时破译了小时破译了56 比特密钥的比特密钥的DES。美国国家标准美国国家标准和技术协会已征集并进行了几轮评估、筛选，产生了和技术协会已征集并进行了几轮评估、筛选，产生了称之为称之为AES(advanced encryption standard)的新加密的新加密标准。尽管如此，标准。尽管如此，DES对于推动密码理论的发展和应对于推动密码理论的发展和应用毕竟起了重大作用，对于掌握分组密码的基本理论、用毕竟起了重大作用，对于掌握分组密码的基本理论、设计思想和实际应用仍然有着重要的参考价值，下面设计思想和实际应用仍然有着重要的参考价值，下面首先来描述这一算法。首先来描述这一算法。图图3.5是是DES加密算法的框图，其中明文分组长为加密算法的框图，其中明文分组长为64比特，密钥长为比特，密钥长为56比特。图的左边是明文的处理过程，比特。图的左边是明文的处理过程，有有3个阶段，首先是一个初始置换个阶段，首先是一个初始置换IP，用于重排明文用于重排明文分组的分组的64比特数据。然后是具有相同功能的比特数据。然后是具有相同功能的16轮变换，轮变换，每轮中都有置换和代换运算，第每轮中都有置换和代换运算，第16轮变换的输出分为轮变换的输出分为左右两半，并被交换次序。最后再经过一个逆初始置左右两半，并被交换次序。最后再经过一个逆初始置换换IP-1（为为IP的逆）从而产生的逆）从而产生64比特的密文。除初始比特的密文。除初始置换和逆初始置换外，置换和逆初始置换外，DES的结构和图的结构和图3.3所示的所示的Feistel密码结构完全相同。密码结构完全相同。3.2.1 DES描述描述图图3.5 DES加密算法框图加密算法框图图图3.5的右边是使用的右边是使用56比特密钥的方法。密钥首先通比特密钥的方法。密钥首先通过一个置换函数，然后，对加密过程的每一轮，通过过一个置换函数，然后，对加密过程的每一轮，通过一个左循环移位和一个置换产生一个子密钥。其中每一个左循环移位和一个置换产生一个子密钥。其中每轮的置换都相同，但由于密钥被重复迭代，所以产生轮的置换都相同，但由于密钥被重复迭代，所以产生的每轮子密钥不相同。的每轮子密钥不相同。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 M37 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 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。和和Feistel网络网络一样，每轮变换可由以下公式表示：一样，每轮变换可由以下公式表示：其中轮密钥其中轮密钥Ki为为48比特，函数比特，函数F(R,K)的计算过程如图的计算过程如图3.7所示。轮输入的右半部分所示。轮输入的右半部分R为为32比特，比特，R首先被扩首先被扩展成展成48比特，扩展过程由表比特，扩展过程由表3.2(c)定义，其中将定义，其中将R的的16个比特各重复一次。扩展后的个比特各重复一次。扩展后的48比特再与子密钥比特再与子密钥Ki异或，然后再通过一个异或，然后再通过一个S盒，产生盒，产生32比特的输出。该比特的输出。该输出再经过一个由表输出再经过一个由表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的的4个代换中的一个。个代换中的一个。6比特输入中，中间比特输入中，中间4位用来选择列。行和列选定后，位用来选择列。行和列选定后，得到其交叉位置的十进制数，将这个数表示为得到其交叉位置的十进制数，将这个数表示为4位二位二进制数即得这一进制数即得这一S盒的输出。例如，盒的输出。例如，S1 的输入为的输入为011001，行选为，行选为01（即第（即第1行），列选为行），列选为1100（即第（即第12列），行列交叉位置的数为列），行列交叉位置的数为9，其，其4位二进制表示为位二进制表示为1001，所以，所以S1的输出为的输出为1001。S盒的每一行定义了一个可逆代换，图盒的每一行定义了一个可逆代换，图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)给出。移位后的结果作为求下一给出。移位后的结果作为求下一轮子密钥的输入，同时也作为置换选择轮子密钥的输入，同时也作为置换选择2的输入。通的输入。通过置换选择过置换选择2产生的产生的48比特的比特的Ki，即为本轮的子密钥，即为本轮的子密钥，作为函数作为函数F(Ri-1,Ki)的输入。其中置换选择的输入。其中置换选择2由表由表3.4(b)定义。（见定义。（见44页表页表3.4）4.解密解密和和Feistel密码一样，密码一样，DES的解密和加密使用同一算法，的解密和加密使用同一算法，但子密钥使用的顺序相反。但子密钥使用的顺序相反。为了提高为了提高DES的安全性，并利用实现的安全性，并利用实现DES的现有软硬的现有软硬件，可将件，可将DES算法在多密钥下多重使用。算法在多密钥下多重使用。二重二重DES是多重使用是多重使用DES时最简单的形式，如图时最简单的形式，如图3.8所示。其中明文为所示。其中明文为P，两个加密密钥为两个加密密钥为K1和和K2，密文密文为：为：解密时，以相反顺序使用两个密钥：解密时，以相反顺序使用两个密钥：3.2.2 二重二重DES图图3.8 二重二重DES因此，二重因此，二重DES所用密钥长度为所用密钥长度为112比特，强度极大比特，强度极大地增加。然而，假设对任意两个密钥地增加。然而，假设对任意两个密钥K1和和K2，能够能够找出另一密钥找出另一密钥K3，使得使得那么，二重那么，二重DES以及多重以及多重DES都没有意义，因为它们都没有意义，因为它们与与56比特密钥的单重比特密钥的单重DES等价，好在这种假设对等价，好在这种假设对DES并不成立。将并不成立。将DES加密过程加密过程64比特分组到比特分组到64比特分组比特分组的映射看作一个置换，如果考虑的映射看作一个置换，如果考虑264个所有可能的输个所有可能的输入分组，则密钥给定后，入分组，则密钥给定后，DES的加密将把每个输入分的加密将把每个输入分组映射到一个惟一的输出分组。否则，如果有两个输组映射到一个惟一的输出分组。否则，如果有两个输入分组被映射到同一分组，则解密过程就无法实施。入分组被映射到同一分组，则解密过程就无法实施。对对264个输入分组，总映射个数为个输入分组，总映射个数为 。另一方面，对每个不同的密钥，另一方面，对每个不同的密钥，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*(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)中值为中值为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(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)AddRoundKey(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”。证明：组合部件证明：组合部件“ByteSubShiftRow”的逆变换原的逆变换原本为本为“InvShiftRowInvByteSub”。由于字节代换由于字节代换（ByteSub）是对每个字节进行相同的变换，故是对每个字节进行相同的变换，故“InvShiftRow”与与“InvByteSub”两个计算部件可两个计算部件可以交换顺序。（证毕）以交换顺序。（证毕）引理引理3.2 设列混合（设列混合（MixColumn）的逆变换为的逆变换为InvMixColumn。则列混合部件与密钥加部件则列混合部件与密钥加部件（AddRoundKey）的组合部件的组合部件“MixColumnAddRoundKey(,Key)”的逆变换为的逆变换为“InvMixColumnAddRoundKey(,InvKey)”。其中密其中密钥钥InvKey与与Key的关系为：的关系为：InvKey=InvMixColumn(Key)。证明：组合部件证明：组合部件“MixColumnAddRoundKey(,Key)”的逆变换原本为的逆变换原本为“AddRoundKey(,Key)InvMixColumn”，由于列混合由于列混合（MixColumn）实际上是线性空间实际上是线性空间GF(28)4上的可逆上的可逆线性变换，因此线性变换，因此“AddRoundKey(