本章将主要讨论二元情况也是当前分组密码研究的主流4 Ü分组密码的作用分组密码的作用l加密加密(适合软硬件实现适合软硬件实现)l构成其它密码功能的基本模块构成其它密码功能的基本模块l1. 构造伪随机数生成器用于构造伪随机数生成器用于产生性能良好的随机数产生性能良好的随机数§适合产生少量随机数适合产生少量随机数l2. 构造流密码构造流密码§速度比移位寄存器慢得多，但软件实现方便速度比移位寄存器慢得多，但软件实现方便§采用适当的分组链接模式采用适当的分组链接模式(CFB或或OFB)可实现可实现l3. 消息认证和数据完整性保护消息认证和数据完整性保护§通过用于构造消息认证码通过用于构造消息认证码(MAC)和杂凑函数等来实现和杂凑函数等来实现5 Ü分组密码算法设计的研究发展概况分组密码算法设计的研究发展概况Ü（一）古典密码学阶段（一）古典密码学阶段l1）算法保密，出现了）算法保密，出现了代换代换和和置换置换的方法的方法l2）产生了乘积密码的思想）产生了乘积密码的思想l指顺序地执行两个或多个基本密码系统，使最后结果的密码强度高于每个指顺序地执行两个或多个基本密码系统，使最后结果的密码强度高于每个基本密码系统的强度，多轮加密基本密码系统的强度，多轮加密(3.1.3(3.1.3节节1 1段段) )l3）基尔霍夫准则：早在）基尔霍夫准则：早在1883年荷兰密码学家年荷兰密码学家A.Kerckhoffs就在其就在其《《军事密码学军事密码学》》中提出如下密码设计准则：中提出如下密码设计准则：la. 密码系统应该是密码系统应该是计算安全计算安全的；的；lb. 密钥密钥由通信双方由通信双方事先约定好事先约定好，并根据一定协议进行更换；，并根据一定协议进行更换；lc. 密码系统应该易于使用；密码系统应该易于使用；ld. 密码系统应该精确而有效；密码系统应该精确而有效；le. 除了密钥，密码系统的所有细节都为对手所知除了密钥，密码系统的所有细节都为对手所知。
l还提出了一次一密的密码设计方法，直接促进了流密码研究还提出了一次一密的密码设计方法，直接促进了流密码研究6 Ü（二）（二）近代密码学阶段近代密码学阶段(1949-1975)-分组密码的酝酿期分组密码的酝酿期l1）计算机技术的发展，开始了密码学面向商业应用的设计）计算机技术的发展，开始了密码学面向商业应用的设计l2））Shannon的工作：的工作：1949年，年，C. E. Shannon(1916~2002 )建立了保密建立了保密系统的通信理论，系统的通信理论，50-70年代年代Shannon的工作起着决定性的指导作用的工作起着决定性的指导作用对密码理论的贡献主要有两点对密码理论的贡献主要有两点l其一，用信息论刻划了密码学中的安全性其一，用信息论刻划了密码学中的安全性§提出了提出了语言冗余度和语言冗余度和““熵熵””的概念，论述了破译密码需要多少信息量的概念，论述了破译密码需要多少信息量§定义了定义了““计算安全计算安全””与与““无条件安全无条件安全””；前者与破译密码的价值有效；前者与破译密码的价值有效性和时间有效性有关后者是指无论破译者有多少密文也无法解出对性和时间有效性有关后者是指无论破译者有多少密文也无法解出对应的明文，即使解出也无法验证结果的正确性应的明文，即使解出也无法验证结果的正确性(One-Time-Pad)(One-Time-Pad)l其二，提出了密码设计中的扩散准则和混淆准则其二，提出了密码设计中的扩散准则和混淆准则§在一次一密无法实现的情况下，这两个准则是设计密码体制的最基本在一次一密无法实现的情况下，这两个准则是设计密码体制的最基本准则。
准则Shannon的思想今天仍然是设计密码体制极其重要的指导准则的思想今天仍然是设计密码体制极其重要的指导准则l3））Smith关于关于Lucifer密码的设计研究密码的设计研究l4））Feistel网络的密码结构网络的密码结构7 Ü（三）现代密码学阶段－走向成熟（三）现代密码学阶段－走向成熟l1）密码学由专门应用转向商业应用）密码学由专门应用转向商业应用l美国数据加密标准美国数据加密标准DES(Data Encryption Standard)是最重大的标是最重大的标志它和公钥密码体制的提出是现代密码学的开端和密码学发展史志它和公钥密码体制的提出是现代密码学的开端和密码学发展史上两个重要里程碑是近代密码学研究重要结晶上两个重要里程碑是近代密码学研究重要结晶l2））DES加密算法的公开及其在商用数据加密中的广泛应用，加密算法的公开及其在商用数据加密中的广泛应用，激发了人们对密码学的研究兴趣，密码学进入了一个新的激发了人们对密码学的研究兴趣，密码学进入了一个新的时期时期l3）现代分组密码研究的发展）现代分组密码研究的发展l早期的研究基本上是围绕早期的研究基本上是围绕DES进行的，推出了一些类似的算法，例进行的，推出了一些类似的算法，例如：如：LOKI，，FEAL，，GOST等。
等8 l20世纪世纪90年代，对年代，对DES算法研究更加深入，特别是差分密码分析算法研究更加深入，特别是差分密码分析（（differential cryptanalysis）和线性密码分析（）和线性密码分析（linear cryptanalysis）的提出，迫使人们不得不研究新的密码结构的提出，迫使人们不得不研究新的密码结构§IDEA密码打破了密码打破了DES类密码的垄断局面类密码的垄断局面l随后出现了随后出现了SQUARE、、SHARK、、SAFER-64等采用了等采用了结构非常清结构非常清晰的代替晰的代替—置换（置换（SP）网络）网络§从理论上给出了最大差分特征概率和最佳线性逼近优势的界，证明了从理论上给出了最大差分特征概率和最佳线性逼近优势的界，证明了密码对差分密码分析和线性密码分析的安全性密码对差分密码分析和线性密码分析的安全性l1997~2000年间美国高级加密标准年间美国高级加密标准AES的征集活动以及的征集活动以及2000~2003年间欧洲年间欧洲NESSIE计划的实施，再次掀起了密码研究的计划的实施，再次掀起了密码研究的新高潮新高潮§15个个AES候选算法和候选算法和24个个NESSIE终选算法反映了当前密码设计的水终选算法反映了当前密码设计的水平，也可以说是近几年研究成果的一个汇总。
平，也可以说是近几年研究成果的一个汇总9 Ü目前对分组密码安全的讨论主要包括差分目前对分组密码安全的讨论主要包括差分密码分析、线性密码分析和强力攻击等密码分析、线性密码分析和强力攻击等l1990年年Biham和和Shamir差分密码分析方法差分密码分析方法以及以及1993年年Mitsuru Matsui线性密码分析线性密码分析方法的问方法的问世，都极大丰富了密码学的内容世，都极大丰富了密码学的内容l从理论上讲，从理论上讲，差分密码分析和线性密码分析是差分密码分析和线性密码分析是目前攻击分组密码的最有效的方法目前攻击分组密码的最有效的方法，而从实际，而从实际上说，上说，强力攻击是攻击分组密码最可靠的方法强力攻击是攻击分组密码最可靠的方法10 Ü一些现行的标准一些现行的标准l3DES、、IDEA、、AESl3GPP标准中的算法标准中的算法 KASUMIl我国国家标准我国国家标准SMS4，现在改为了，现在改为了SM4lNESSIE分组密码算法分组密码算法(欧欧)lMISTY1，，过渡型的标准，日本人过渡型的标准，日本人Eisaku Takeda设计设计lCamellia，，普通型的标准（普通型的标准（AES算法也可用），日本人算法也可用），日本人Shiho Moriai与与Mitsuru Matsui设计设计lSHACAL2，，高级型的标准，法国人高级型的标准，法国人Helena Handschuh和和David Naccache设计设计l瑞典人瑞典人Jakob Jonsson和美国人和美国人Burt Kaliski设计的设计的RC6RC611 Ü分组密码领域有待继续研究和完善的理论和实际问题分组密码领域有待继续研究和完善的理论和实际问题l如何设计可证明安全的密码算法；如何设计可证明安全的密码算法；l如何加强现有算法及其工作模式的安全性；如何加强现有算法及其工作模式的安全性；l如何测试密码算法的安全性；如何测试密码算法的安全性；l如何设计安全的密码组件，例如如何设计安全的密码组件，例如S-盒、扩散层及密钥扩散算法等。
盒、扩散层及密钥扩散算法等Ü分组密码没有非常有效的数学分析工具分组密码没有非常有效的数学分析工具l需要实践检验需要实践检验Ü参考资料参考资料：：《《对称密码学对称密码学》》胡予濮，张玉清等著胡予濮，张玉清等著Ü 《《密码分析学密码分析学》》冯登国冯登国12 Ü分组密码算法设计满足的要求：分组密码算法设计满足的要求：ÜI. 应用要求：应用要求：l实际应用中对于分组密码可能提出多方面的要求，除了实际应用中对于分组密码可能提出多方面的要求，除了安全性安全性外，还有：外，还有：l运行速度运行速度l存储量（程序的长度、数据分组长度、高速缓存大小）存储量（程序的长度、数据分组长度、高速缓存大小）l实现平台（硬件、软件、芯片）、实现平台（硬件、软件、芯片）、l运行模式等限制条件运行模式等限制条件l这些都需要与安全性要求之间进行适当的折中选择这些都需要与安全性要求之间进行适当的折中选择13 ÜII. 算法设计的要求算法设计的要求l分组密码设计在于找到一种算法，能在密钥控制下从一个足够分组密码设计在于找到一种算法，能在密钥控制下从一个足够大且足够好的置换子集中，简单而迅速地选出一个置换，用来大且足够好的置换子集中，简单而迅速地选出一个置换，用来对当前输入的明文数字组进行加密变换对当前输入的明文数字组进行加密变换l①① 分组长度分组长度n要足够大，使分组代换字母表中的元素个要足够大，使分组代换字母表中的元素个数数2n足够大，防止明文穷举攻击法奏效。
足够大，防止明文穷举攻击法奏效需要明文相需要明文相关性和统计特性关性和统计特性)lDES、、IDEA、、FEAL和和LOKI等分组密码都采用等分组密码都采用n=64，在生日，在生日攻击下用攻击下用232组密文成功概率为组密文成功概率为1/2，同时要求，同时要求232×64b=215MB＝＝32GB存贮，故现在采用穷举攻击已经可以实现存贮，故现在采用穷举攻击已经可以实现(时间存储攻击时间存储攻击)l生日攻击：生日攻击：(请参考请参考6.2.3节节)随机选取随机选取n个人，至少有两个人生日个人，至少有两个人生日相同的概率为相同的概率为 P＝＝1－－365×364×…×(365－－n+1)/365n l当当n＝＝64时时 p＝＝0.997近乎于近乎于114 Ü②② 密钥量要足够大（即置换子集中的元素足够多）密钥量要足够大（即置换子集中的元素足够多）l尽可能消除弱密钥并使所有密钥同等地好，以防止密钥穷举攻击尽可能消除弱密钥并使所有密钥同等地好，以防止密钥穷举攻击奏效但密钥又不能过长，以便于密钥的管理但密钥又不能过长，以便于密钥的管理lDES采用采用56比特密钥，太短比特密钥，太短lIDEA采用采用128比特密钥，够用比特密钥，够用l据估计，在今后据估计，在今后30～～40年内采用年内采用80比特密钥是足够安全的比特密钥是足够安全的Ü③③ 由密钥确定置换的算法要足够复杂，充分实现明文与密由密钥确定置换的算法要足够复杂，充分实现明文与密钥的扩散和混淆，没有简单的关系可循，能抗击各种已知钥的扩散和混淆，没有简单的关系可循，能抗击各种已知的攻击的攻击l如差分攻击和线性攻击如差分攻击和线性攻击l有高的非线性阶数，实现复杂的密码变换有高的非线性阶数，实现复杂的密码变换l使对手破译时除了用穷举法外，无其它捷径可循使对手破译时除了用穷举法外，无其它捷径可循15 Ü④④ 加密和解密运算简单，易于软件和硬件高速实现加密和解密运算简单，易于软件和硬件高速实现l使用子块和简单的运算使用子块和简单的运算l如将分组如将分组n划分为子段，每段长为划分为子段，每段长为8、、16或者或者32l在软件实现时，应选用简单的运算，使作用于子段上的密码运算易于以标准在软件实现时，应选用简单的运算，使作用于子段上的密码运算易于以标准处理器的基本运算，如加、乘、移位等实现，避免用软件难于实现的逐比特处理器的基本运算，如加、乘、移位等实现，避免用软件难于实现的逐比特置换置换l加解密算法应具有相似性加解密算法应具有相似性l为了便于硬件实现，加密和解密过程之间的差别应仅在于由秘密密钥所生成为了便于硬件实现，加密和解密过程之间的差别应仅在于由秘密密钥所生成的密钥表不同而已。
这样，加密和解密就可用同一器件实现的密钥表不同而已这样，加密和解密就可用同一器件实现l设计的算法采用规则的模块结构设计的算法采用规则的模块结构，如多轮迭代等，以便于软件和，如多轮迭代等，以便于软件和VLSI快快速实现速实现l多轮迭代多轮迭代是乘积密码的特例，指同一基本加密结构的多次执行是乘积密码的特例，指同一基本加密结构的多次执行l若以一个简单函数若以一个简单函数f，进行多次迭代，就称其为迭代密码进行多次迭代，就称其为迭代密码l每次迭代称作一轮每次迭代称作一轮(Round)相应函数相应函数f 称作轮函数称作轮函数l每一轮输出都是前一轮输出的函数，即每一轮输出都是前一轮输出的函数，即y(i)=f[y(i-1), k(i)]，其中，其中k(i)是第是第i轮迭轮迭代用的子密钥，由秘密密钥代用的子密钥，由秘密密钥k通过密钥生成算法产生通过密钥生成算法产生 16 Ü⑤⑤ 数据扩展数据扩展l一般无数据扩展，在采用同态置换和随机化加密技术时一般无数据扩展，在采用同态置换和随机化加密技术时(如公钥密码如公钥密码)可引入数据扩展可引入数据扩展Ü⑥⑥ 差错传播尽可能地小差错传播尽可能地小l1比特的传输错误不会影响更多比特的正确解密比特的传输错误不会影响更多比特的正确解密Ü要实现上述几点要求并不容易。
要实现上述几点要求并不容易l首先，要在理论上研究有效而可靠的设计方法首先，要在理论上研究有效而可靠的设计方法l而后进行严格的安全性检验而后进行严格的安全性检验l并且要易于实现并且要易于实现l下面介绍设计分组密码时的一些常用方法下面介绍设计分组密码时的一些常用方法17 3.1.1代换代换Ü为使加密运算可逆为使加密运算可逆(使解密运算可行使解密运算可行)，明文的每一，明文的每一个分组都应产生惟一的一个密文分组，这样的变换个分组都应产生惟一的一个密文分组，这样的变换是可逆的是可逆的l称明文分组到密文分组的可逆变换为代换称明文分组到密文分组的可逆变换为代换(与古典密码中与古典密码中代换表同义代换表同义)l即代换是输入集即代换是输入集A到输出集合到输出集合A 上的双射变换：上的双射变换：l fk：：AA l式中，式中，k k是控制输入变量，即密钥是控制输入变量，即密钥l密钥密钥k k决定了使用哪一个代换，是代换函数的一部分决定了使用哪一个代换，是代换函数的一部分l双射条件保证在给定双射条件保证在给定k k下可从密文惟一恢复明文下可从密文惟一恢复明文18 l代换的数量代换的数量l如果明文和密文的分组长都为如果明文和密文的分组长都为n比特，则明文的每一比特，则明文的每一个分组都有个分组都有2n个可能的取值，则个可能的取值，则不同可逆变换的个数不同可逆变换的个数有有2n!个个。
§2n的全排列的全排列l代换网络：代换网络：l实现代换实现代换fk的运算网络称作代换网络的运算网络称作代换网络(由多个运算组由多个运算组件组成件组成)l常利用一些简单的基本代换，通过组合，实现较复杂常利用一些简单的基本代换，通过组合，实现较复杂的、元素个数较多的代换集，即代换网络的、元素个数较多的代换集，即代换网络19 Ü代换结构代换结构l下图表示下图表示n=4的代换密码的一般结构的代换密码的一般结构l4比比特特输输入入产产生生16个个可可能能输输入入状状态态中中的的一一个个，，由由代代换换结结构构将将这这一一状状态态映映射射为为16个个可可能能输输出出状状态态中中的的一一个个，，每每一一输输出出状态由状态由4个密文比特表示个密文比特表示 l共有共有24！！=16!种可能置换种可能置换20 Ü加密映射和解密映射也可由加密映射和解密映射也可由代换表代换表来定义，这种定义来定义，这种定义法是分组密码最常用的形式，能用于定义明文和密文法是分组密码最常用的形式，能用于定义明文和密文之间的任何可逆映射之间的任何可逆映射Ü表表3-1 对应的代换表对应的代换表明文明文 密文密文明文明文 密文密文密文密文 明文明文密文密文 明文明文0000 11100001 01000010 11010011 00010100 00100101 11110110 10110111 10001000 00111001 10101010 01101011 11001100 01011101 10011110 00001111 01110000 11100001 00110010 01000011 10000100 00010101 11000110 10100111 11111000 01111001 11011010 10011011 01101100 10111101 00101110 00001111 0101加密代换加密代换解密代换解密代换21 Ü这种代换结构中分组长度不宜太小这种代换结构中分组长度不宜太小l如如果果分分组组长长度度太太小小，，如如n=4，，系系统统则则等等价价于于古古典典的的代代换换密密码码，，容容易易通通过过对对明明文文的的统统计计分分析析而而被被攻破。
攻破l这这个个弱弱点点不不是是代代换换结结构构固固有有的的，，只只是是因因为为分分组组长长度度太太小小如如果果分分组组长长度度n足足够够大大，，而而且且从从明明文文到到密密文文可可有有任任意意可可逆逆的的代代换换，，那那么么明明文文的的统统计计特性将被隐藏而使以上的攻击不能奏效特性将被隐藏而使以上的攻击不能奏效22 Ü分组长度也不宜很大分组长度也不宜很大l会使代换表规模呈几何级数增加会使代换表规模呈几何级数增加l仍以表仍以表3.1为例，该表定义了为例，该表定义了n=4时从明文到密文的一个时从明文到密文的一个可逆映射，其中第可逆映射，其中第2列是每个明文分组对应的密文分组列是每个明文分组对应的密文分组的值，可用来定义这个可逆映射的值，可用来定义这个可逆映射l从本质上来说，第从本质上来说，第2列是从所有可能映射中决定某一特列是从所有可能映射中决定某一特定映射的密钥这个例子中，密钥总量需要定映射的密钥这个例子中，密钥总量需要64比特l一般地，对一般地，对n比特的代换结构，密钥的大小是比特的代换结构，密钥的大小是n×2n比特如对如对64比特的分组，密钥大小应是比特的分组，密钥大小应是64×264=270≈1021比特，比特，因此难以处理。
如果可用一个函数来描述映射，则密钥因此难以处理如果可用一个函数来描述映射，则密钥量就是量就是n23 Ü解决办法解决办法l实际中常将分组实际中常将分组n分成较小的段，如可选分成较小的段，如可选n=r·n0，其中，其中r和和n0都是正整数，都是正整数，将设计将设计n个变量的代换变为设计个变量的代换变为设计r个较个较小的子代换，而每个子代换只有小的子代换，而每个子代换只有n0个输入变量个输入变量l一般一般n0都不太大，称每个子代换为代换盒，简称为都不太大，称每个子代换为代换盒，简称为S盒例如例如DES中将输入为中将输入为48比特、输出为比特、输出为32比特的代换用比特的代换用8个个S盒来实现，每个盒来实现，每个S盒的输入端数仅为盒的输入端数仅为6比特，输出端比特，输出端数仅为数仅为4比特24 3.1.2 扩散和混淆扩散和混淆Ü扩散和混淆扩散和混淆(diffusion and confusion)是由是由Shannon提出的设计密码系统的两个基本方法，提出的设计密码系统的两个基本方法，目的是抗击敌手对密码系统的统计分析目的是抗击敌手对密码系统的统计分析l如果敌手知道如果敌手知道明文的某些统计特性明文的某些统计特性，如消息中不同字母，如消息中不同字母出现的频率、可能出现的特定单词或短语，出现的频率、可能出现的特定单词或短语，而且这些统而且这些统计特性以某种方式在密文中反映出来计特性以某种方式在密文中反映出来，那么敌手就有可，那么敌手就有可能得出能得出加密密钥或其一部分，加密密钥或其一部分，或者得出或者得出包含加密密钥的包含加密密钥的一个可能的密钥集合一个可能的密钥集合25 l在在Shannon称之为理想密码的密码系统中，密文的所称之为理想密码的密码系统中，密文的所有统计特性都与所使用的密钥独立有统计特性都与所使用的密钥独立。
下图的代换密码下图的代换密码就是这样的一个密码系统，然而它是不实用的就是这样的一个密码系统，然而它是不实用的26 Ü扩散：就是将明文的统计特性散布到密文中去扩散：就是将明文的统计特性散布到密文中去l实现方式是使得明文的每一位影响密文中多位的值，等价实现方式是使得明文的每一位影响密文中多位的值，等价于说密文中每一位均受明文中多位影响于说密文中每一位均受明文中多位影响l例如对英文消息例如对英文消息M=m1m2m3…的加密操作的加密操作lyn=chr( i=1,2,…,kord(mn+i)(mod 26))l其中其中ord(mi)是求字母是求字母mi对应的序号，对应的序号，chr(i)是求序号是求序号i对应的字母对应的字母l这时明文的统计特性将被散布到密文中这时明文的统计特性将被散布到密文中l因而每一字母在密文中出现的频率比在明文中出现的频率更接近于因而每一字母在密文中出现的频率比在明文中出现的频率更接近于相等，双字母及多字母出现的频率也更接近于相等相等，双字母及多字母出现的频率也更接近于相等l在二元分组密码中，可对数据重复执行某个置换，再对这在二元分组密码中，可对数据重复执行某个置换，再对这一置换作用于一函数一置换作用于一函数(代换代换)，可获得扩散，可获得扩散。
置换置换+代换代换)l扩散的目的是使明文和密文之间的统计关系变得尽可能复扩散的目的是使明文和密文之间的统计关系变得尽可能复杂杂，以使敌手无法得到密钥，以使敌手无法得到密钥27 Ü混淆混淆l是使密文和密钥之间的统计关系变得尽可能复杂，以使是使密文和密钥之间的统计关系变得尽可能复杂，以使敌手无法得到密钥敌手无法得到密钥l即使敌手能得到密文的一些统计关系，由于密钥和密文之间的即使敌手能得到密文的一些统计关系，由于密钥和密文之间的统计关系复杂化，敌手也无法得到密钥统计关系复杂化，敌手也无法得到密钥l使用复杂的代换算法使用复杂的代换算法可以得到预期的混淆效果可以得到预期的混淆效果l简单的线性代换函数得到的混淆效果则不够理想简单的线性代换函数得到的混淆效果则不够理想Ü扩散和混淆成功地实现分组密码本质属性，因而扩散和混淆成功地实现分组密码本质属性，因而成为设计现代分组密码的基础成为设计现代分组密码的基础28 3.1.3 Feistel 密码结构密码结构Ü分组密码的结构：分组密码的结构：l是指实现密码算法的组件结构是指实现密码算法的组件结构l主要基于两种运算：代换（主要基于两种运算：代换（ Substitution ）和置换（）和置换（ Permutation ））Ü实际中，需要加密，也需要解密，因此，有两种方法：实际中，需要加密，也需要解密，因此，有两种方法：l1. 定义每个代换、置换的逆，这样增加了复杂度定义每个代换、置换的逆，这样增加了复杂度l2. 定义一种结构，容易求逆，这样可以使用基本的相同编码或硬件用于加定义一种结构，容易求逆，这样可以使用基本的相同编码或硬件用于加密和解密，比如密和解密，比如S-P网络网络ÜS-P网络：是代换网络：是代换-置换乘积密码的现代形式置换乘积密码的现代形式l在在Shannon 1949 的文章中，介绍了代换的文章中，介绍了代换-置换网络置换网络(SPN)的思想的思想 ，这种，这种思想形成了现代密码的基础思想形成了现代密码的基础lSPN主要基于代换和置换两种最基本的密码运算主要基于代换和置换两种最基本的密码运算lShannon 把这两种运算组合在一起，将一些把这两种运算组合在一起，将一些 S-boxes 由由 P-box 连接，连接，这种变换叫做这种变换叫做混合变换混合变换（（mixing transformations））29 Ü目前分组密码所采用的整体结构可分为：目前分组密码所采用的整体结构可分为：ÜS-P网络（最基本的结构）网络（最基本的结构）lSP的网络结构非常清晰，例如的网络结构非常清晰，例如Safer+、、Serpent、、IDEA、、AES等等lS一般被称为混淆层，主要起混淆作用一般被称为混淆层，主要起混淆作用lP一般被称为扩散层，主要起扩散作用。
一般被称为扩散层，主要起扩散作用l在明确在明确S和和P的某些密码指标后，设计者的某些密码指标后，设计者能估计能估计SP型密码抵抗差分密型密码抵抗差分密码分析和线性密码分析的能力码分析和线性密码分析的能力SP网络和网络和Feistel网络相比，可以网络相比，可以得得到更快速的扩散到更快速的扩散，但是，但是SP密码的加密码的加/解密通常不相似解密通常不相似ÜFeistel结构（一种特殊的结构（一种特殊的S-P结构）结构）l例如例如DES、、CAST-256、、DEAL、、DFC、、E2等等l加解密相似加解密相似是是Feistel型密码的一个实现优点，但它在密码的型密码的一个实现优点，但它在密码的扩散似乎扩散似乎有些慢有些慢，例如需要两轮才能改变输入的每一个比特不过在实用中似，例如需要两轮才能改变输入的每一个比特不过在实用中似乎并不会形成较大的影响，只要轮数足够多乎并不会形成较大的影响，只要轮数足够多Ü其他密码结构（例如其他密码结构（例如Frog和和HPC）采用非正规结构，安全性不好）采用非正规结构，安全性不好30 ÜFeistel结构结构l早期，很多成功的分组密码的结构从本质上说都是基于一个称早期，很多成功的分组密码的结构从本质上说都是基于一个称为为Feistel网络的结构网络的结构ÜFeistel提出利用乘积密码可获得简单代换密码提出利用乘积密码可获得简单代换密码l乘积密码乘积密码指顺序地执行两个或多个基本密码系统，使得最后结指顺序地执行两个或多个基本密码系统，使得最后结果的密码强度高于每个基本密码系统产生结果果的密码强度高于每个基本密码系统产生结果l乘积密码的特例乘积密码的特例是是迭代密码迭代密码，采用多个相同的基本密码系统顺，采用多个相同的基本密码系统顺次执行次执行(如如Feistel结构结构)ÜFeistel还提出了实现代换和置换的方法。
还提出了实现代换和置换的方法l其思想实际上是其思想实际上是Shannon提出的提出的利用乘积密码实现混淆和扩散利用乘积密码实现混淆和扩散思想的具体应用思想的具体应用31 Ü1．．Feistel 加密结构加密结构lHorst Feistel, （（working at IBM Thomas J Watson Research Labs ））l70年代初设计了这样年代初设计了这样的结构，我们现在叫的结构，我们现在叫做做Feistel cipher l图图3-3是是Feistel网络示网络示意图意图32 ÜFeistel结构描述结构描述l1)加密算法的输入：是分组长为加密算法的输入：是分组长为2w的明文和一个密钥的明文和一个密钥Kl2)将每组明文分成左右两半将每组明文分成左右两半L0和和R0l3)在进行完在进行完n轮迭代后，左右两半再合并到一起以产生轮迭代后，左右两半再合并到一起以产生密文分组密文分组l4)其第其第i 轮迭代的输入为前一轮输出的函数：轮迭代的输入为前一轮输出的函数：lLi＝＝Ri－－1lRi＝＝Li－－1 F(Ri－－1, Ki)l其中其中Ki是第是第i 轮用的子密钥，由加密密钥轮用的子密钥，由加密密钥K得到。
一般地，得到一般地，各轮子密钥彼此不同而且与各轮子密钥彼此不同而且与K也不同33 ÜFestal网络中的代换：网络中的代换：lFestal网络中每轮结构都相同，每轮中右半数据被作用于轮函数网络中每轮结构都相同，每轮中右半数据被作用于轮函数F后，再与左半数据进行异或运算，这一过程就是上面介绍的代换后，再与左半数据进行异或运算，这一过程就是上面介绍的代换l每轮的每轮的轮函数的结构都相同轮函数的结构都相同，但以，但以不同的子密钥不同的子密钥Ki作为参数作为参数l可起到混淆等效果可起到混淆等效果ÜFestal网络中的置换：网络中的置换：l代换过程完成后，再交换左、右两半数据，这一过程称为置换代换过程完成后，再交换左、右两半数据，这一过程称为置换l这种结构是这种结构是Shannon提出的代换提出的代换—置换网络（置换网络（substitution-permutation network, SPN）的特有形式的特有形式l在代换中也包含一些置换运算在代换中也包含一些置换运算l可起到扩散等效果可起到扩散等效果34 ÜFeistel网络的实现与以下参数和特性有关：网络的实现与以下参数和特性有关： Ü①① 分组大小分组大小 l分组越大则安全性越高，但加密速度就越慢。
分组密码设计中最为分组越大则安全性越高，但加密速度就越慢分组密码设计中最为普遍使用的分组大小是普遍使用的分组大小是64比特128比特比特Ü②② 密钥大小密钥大小l密钥越长则安全性越高，但加密速度就越慢现在普遍认为密钥越长则安全性越高，但加密速度就越慢现在普遍认为64比特比特或更短的密钥长度是不安全的，通常使用或更短的密钥长度是不安全的，通常使用128比特的密钥长度比特的密钥长度Ü③③ 轮数轮数 l单轮结构远不足以保证安全性，但多轮结构可提供足够的安全性单轮结构远不足以保证安全性，但多轮结构可提供足够的安全性典型地，轮数取为典型地，轮数取为16Ü④④ 子密钥产生算法子密钥产生算法l该算法的复杂性越大，则密码分析的困难性就越大该算法的复杂性越大，则密码分析的困难性就越大Ü⑤⑤ 轮函数轮函数 l轮函数的复杂性越大，密码分析的困难性也越大轮函数的复杂性越大，密码分析的困难性也越大35 Ü在设计在设计Feistel网络时，还有以下两个方面需要考虑网络时，还有以下两个方面需要考虑 Ü①① 快速的软件实现快速的软件实现l在很多情况中，算法是被镶嵌在应用程序中，因而无法用在很多情况中，算法是被镶嵌在应用程序中，因而无法用硬件实现。
此时算法的执行速度是考虑的关键硬件实现此时算法的执行速度是考虑的关键Ü②② 算法容易分析算法容易分析l如果算法能被无疑义地解释清楚，就可容易地分析算法抵如果算法能被无疑义地解释清楚，就可容易地分析算法抵抗攻击的能力，有助于设计高强度的算法抗攻击的能力，有助于设计高强度的算法36 Ü2. Feistel 解密结构解密结构lFeistel解密过程本质上和加密过程是一样的解密过程本质上和加密过程是一样的l算法算法使用密文作为输入使用密文作为输入，但，但使用子密钥使用子密钥Ki的次的次序与加密过程相反序与加密过程相反，即第，即第1轮使用轮使用Kn，第，第2轮使轮使用用Kn-1，，……，最后一轮使用，最后一轮使用K1l这一特性保证了解密和加密可采用同一算法这一特性保证了解密和加密可采用同一算法37 l加密过程由上而下，加密过程由上而下，每轮的左右两半用每轮的左右两半用LEi和和REi表示表示l解密过程由下而上，解密过程由下而上，每轮的左右两半用每轮的左右两半用LDi和和RDi表示表示Ü图中右边标出了解密过图中右边标出了解密过程中每一轮的中间值与程中每一轮的中间值与左边加密过程中间值的左边加密过程中间值的对应关系对应关系l即加密过程第即加密过程第i轮的轮的输出是输出是LEi‖REi（（‖表示链接）表示链接）l解密过程第解密过程第17-i轮相轮相应的输入是应的输入是RDi‖LDi38 Ü加密过程的最后一轮执行完后，两半输出再经交换，因此密文是加密过程的最后一轮执行完后，两半输出再经交换，因此密文是RE16‖LE16。
解密过程取以上密文作为同一算法的输入，即第解密过程取以上密文作为同一算法的输入，即第1轮输入轮输入是是RE16‖LE16，等于加密过程第，等于加密过程第16轮两半输出交换后的结果轮两半输出交换后的结果Ü下面证明解密过程第下面证明解密过程第1轮的输出等于加密过程第轮的输出等于加密过程第16轮输入左右两半交轮输入左右两半交换值换值l在加密过程中：在加密过程中：lLE16＝＝RE15lRE16＝＝LE15 F(RE15, K16)l在解密过程中在解密过程中lLD1＝＝RD0=LE16＝＝RE15lRD1＝＝LD0 F(RD0, K16)＝＝RE16 F(RE15, K16)l ＝＝[LE15 F(RE15, K16)] F(RE15, K16)＝＝LE15l所以解密过程第所以解密过程第1轮的输出为轮的输出为LE15‖RE15，等于加密过程第，等于加密过程第16轮输入左右轮输入左右两半交换后的结果容易证明这种对应关系在两半交换后的结果容易证明这种对应关系在16轮中每轮都成立轮中每轮都成立 39 Ü一般地，加密过程的第一般地，加密过程的第i轮有轮有lLEi＝＝REi-1lREi＝＝LEi-1 F(REi-1, Ki)Ü因此因此lREi-1＝＝LEilLEi-1＝＝REi F(REi-1, Ki)=REi F(LEi, Ki)Ü以上两式描述了加密过程中第以上两式描述了加密过程中第i轮的输入与第轮的输入与第i轮输出的函轮输出的函数关系，由此关系可得图数关系，由此关系可得图3-4右边显示的右边显示的LDi和和RDi的取值的取值关系。
关系Ü最后可以看到，解密过程第最后可以看到，解密过程第16轮的输出是轮的输出是RE0‖LE0，左右，左右两半再经一次交换后即得最初的明文两半再经一次交换后即得最初的明文 40 3.2 数据加密标准数据加密标准DESÜDES的产生的产生l美国国家标准局美国国家标准局1973年开始研究除国防部外的其它部门的计算机系年开始研究除国防部外的其它部门的计算机系统的数据加密标准统的数据加密标准l于于1973年年5月月15日和日和1974年年8月月27日先后两次向公众发出了征求加密日先后两次向公众发出了征求加密算法的公告加密算法要达到的目的（通常称为算法的公告加密算法要达到的目的（通常称为DES 密码算法要求）密码算法要求）主要为以下四点：主要为以下四点： l（（1））提供高质量的数据保护提供高质量的数据保护，防止数据未经授权的泄露和未被察觉，防止数据未经授权的泄露和未被察觉的修改；的修改； l（（2））计算安全性计算安全性：具有相当高的复杂性，使得破译的开销超过可能：具有相当高的复杂性，使得破译的开销超过可能获得的利益，同时又要便于理解和掌握；获得的利益，同时又要便于理解和掌握； l（（3））基尔霍夫准则基尔霍夫准则：：DES密码体制的安全性应该不依赖于算法的保密码体制的安全性应该不依赖于算法的保密，其安全性仅以加密密钥的保密为基础；密，其安全性仅以加密密钥的保密为基础； l（（4））可行性可行性：实现经济，运行有效，并且适用于多种完全不同的应：实现经济，运行有效，并且适用于多种完全不同的应用。
用 41 lDES在在1975年年3月月17日首次被公布在联邦记录中日首次被公布在联邦记录中l经过大量的公开讨论后，经过大量的公开讨论后，1977年年1月月15日美国政府颁日美国政府颁布：布：采纳美国采纳美国IBM公司设计的方案公司设计的方案作为作为非机密数据非机密数据的的正式数据加密标准（正式数据加密标准（DES, Data Encryption Standard），），DES被正式批准并作为美国联邦信息被正式批准并作为美国联邦信息处理标准，即处理标准，即FIPS-46，同年，同年7月月15日开始生效日开始生效l它的分组长度为它的分组长度为64比特，密钥长度为比特，密钥长度为56比特，是早比特，是早期的称作期的称作Lucifer密码的一种发展和修改密码的一种发展和修改ÜDES是迄今为止世界上最为广泛使用和流行的是迄今为止世界上最为广泛使用和流行的一种分组密码算法一种分组密码算法l1996年以后，主要是年以后，主要是3DES42 3.2.1 DES描述描述Ü图图4.5是是DES加加密算法的框图密算法的框图l其中明文分组长其中明文分组长为为64比特，密比特，密钥长为钥长为56比特图的图的左边是明文的处理过程，，有3个阶段:l2)具有相同功能的具有相同功能的16轮轮变换，每轮中都有置换和代换运算，变换，每轮中都有置换和代换运算，第第16轮变换的输出分为左右两半，并被交换次序。
轮变换的输出分为左右两半，并被交换次序l3)最后再经过一个最后再经过一个逆初始置换逆初始置换IP-1（为（为IP的逆）从而产生的逆）从而产生64比比特的密文特的密文 l1)初始置换初始置换IP，用于重排明，用于重排明文分组的文分组的64比特数据比特数据除初始置换和逆初始置换外，除初始置换和逆初始置换外，DESDES的结的结构和图构和图4.3 4.3 所示的所示的FeistelFeistel密码结构完密码结构完全相同全相同43 Ü图图4.5的右边是使用的右边是使用56比特密钥的方法比特密钥的方法l密钥首先通过一个置换函数密钥首先通过一个置换函数PC-1，，l然后，对加密过程的每一轮，通过一个左循环移位和然后，对加密过程的每一轮，通过一个左循环移位和一个置换产生一个子密钥其中每轮的置换都相同，一个置换产生一个子密钥其中每轮的置换都相同，但由于密钥被重复迭代，所以产生的每轮子密钥不相但由于密钥被重复迭代，所以产生的每轮子密钥不相同44 Ü1.初始置换初始置换ÜDES的初始置换见表的初始置换见表3-2l表表3-2(a)和和3-2(b)分别给出了初始置换和逆初始置换的定义，这两分别给出了初始置换和逆初始置换的定义，这两个置换是互逆的。
个置换是互逆的l64比特的明文比特的明文M以以8比特为一行，共比特为一行，共8行以行顺序编号行以行顺序编号l由表由表3-2(a)得得X=IP(M)，由，由3-2(b)得得 Y＝＝IP-1(X)=IP-1(IP(M))=M45 Ü和和Feistel网络一样，每轮变换可由以下公式表示：网络一样，每轮变换可由以下公式表示：lLi＝＝Ri－－1 Ri＝＝Li－－1 F(Ri－－1, Ki)l其中轮密钥其中轮密钥Ki为为48比特＝＝Ü2.轮结构轮结构Ü图图3-6是是DES加密加密算法的轮结构算法的轮结构Ü首先看图的左半首先看图的左半部分将64比特比特的轮输入分成各的轮输入分成各为为32比特的左、比特的左、右两半，分别记右两半，分别记为为L和和R46 Ü函数函数F(R,K)的计算过程的计算过程l如图如图4.7所示轮输入的右半部分所示轮输入的右半部分R为为32比特，比特，R首先被扩展成首先被扩展成48比特，扩展过程由表比特，扩展过程由表3.2(c)定义，其定义，其中将中将R的的16个比特各重个比特各重复一次复一次扩展后的扩展后的48比特再与子密钥比特再与子密钥Ki异或，然后再通过异或，然后再通过一个一个S盒，产生盒，产生32比特的输出。
比特的输出该输出再经过一个由表该输出再经过一个由表3.2(d)定义的置换定义的置换P，产生，产生的结果即为函数的结果即为函数F(R,K)的输出47 Ü扩展置换E和置换P48 Ü代换盒代换盒 S (substitution box)lF中的代换由中的代换由8个个S盒组成，每个盒组成，每个S盒的输入长为盒的输入长为6比特、输出长为比特、输出长为4比比特，其变换关系由表特，其变换关系由表3.3定义，每个定义，每个S盒给出了盒给出了4个代换（由一个表的个代换（由一个表的4行给出）见行给出）见42页表页表3.3））ÜDES的的S盒定义盒定义行行 列列0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15S1012314 4 13 1 2 15 11 8 3 10 6 12 5 9 0 70 15 7 4 14 2 13 1 10 6 12 11 9 5 3 84 1 14 8 13 6 2 11 15 12 9 7 3 10 5 015 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13S2……………S8……49 Ü对每个盒对每个盒Sil其其6比特输入中，比特输入中，第第1个和第个和第6个比特个比特形成一个形成一个2位二进制位二进制数，用来选择数，用来选择Si的的4个代换中的一个个代换中的一个l中间中间4位用来选择列位用来选择列。
行和列选定后，得到其交叉位置行和列选定后，得到其交叉位置的十进制数，将这个数表示为的十进制数，将这个数表示为4位二进制数即得这一位二进制数即得这一S盒盒的输出Ü例如，例如，S1 的输入为的输入为011001l则行选为则行选为01（即第（即第1行），列选为行），列选为1100（即第（即第12列）列）l行列交叉位置的数为行列交叉位置的数为9，其，其4位二进制表示为位二进制表示为1001，所以，所以S1的输出为的输出为1001ÜS盒的每一行定义了一个可逆代换盒的每一行定义了一个可逆代换l图图3-2（在（在3.1.1节）表示节）表示S1第第0行所定义的代换行所定义的代换50 Ü3．密钥的产生．密钥的产生l实际上，实际上，K是长度为是长度为64的位的位串，其中串，其中56位是密钥，位是密钥，8位位是奇偶校验位（为了检错），是奇偶校验位（为了检错），在密钥编排的计算中，这些在密钥编排的计算中，这些校验位可略去校验位可略去ÜDES密钥编排算法结构图密钥编排算法结构图lLSi表示循环左移一个或两个表示循环左移一个或两个位置位置l其中其中i为为1，，2，，9，，16循环移循环移1位，其余循环移两位位，其余循环移两位51 Ü过程：过程：l(1) 给定给定64位的密钥位的密钥K，放弃奇偶校验位（，放弃奇偶校验位（8，，16，，…，，64）形成连续的）形成连续的56比特的密钥比特的密钥l(2)再看图再看图3-5和图和图3-6，输入算法的，输入算法的56比特密钥首先经比特密钥首先经过一个置换运算过一个置换运算PC-1，该置换由表，该置换由表3.4(a)给出给出l然后将置换后的然后将置换后的56比特分为各为比特分为各为28比特的左、右两半，比特的左、右两半，分别记为分别记为C0和和D0l(3)在第在第i 轮分别对轮分别对Ci-1和和Di-1进行左循环移位，所移位数进行左循环移位，所移位数由表由表3.4(c)给出。
给出l移位后的结果作为求下一轮子密钥的输入，同时也作为移位后的结果作为求下一轮子密钥的输入，同时也作为置换选择置换选择2 PC-2的输入通过置换选择的输入通过置换选择2产生的产生的48比特比特的的Ki，即为本轮的子密钥，作为函数，即为本轮的子密钥，作为函数F(Ri-1,Ki)的输入其中置换选择其中置换选择2由表由表3.4(b)定义定义52 ÜDES密钥编排中使用的表（表密钥编排中使用的表（表3-4）） (a) 置换选择置换选择1 (b) 置换选择置换选择2Ü (c) 左循环移位位数左循环移位位数l注注. ①①对对i=1,2,…,16，， Ci、、Di分分别别是是由由C0、、D0左左旋旋若若干干比比特特而而得得到到，，至至i=16，，刚好左旋了刚好左旋了28比特位而回复当初比特位而回复当初，即，即:C16=C0，，D16=D0 PC－－1PC－－2574941332517914171124151585042342618328156211010259514335272319124268191136052443616727201326355473931231541523137475576254463812223040514533481466153453729444939563453211352820304464250362932轮数 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16位数 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 153 Ü4．解密．解密l和和Feistel密码一样，密码一样，DES的解密和加密算法使用同一算法，但的解密和加密算法使用同一算法，但子子密钥使用的顺序相反密钥使用的顺序相反Ü解密时子密钥的产生有两种方式：解密时子密钥的产生有两种方式：l1）是先由）是先由K产生产生16个子密钥，再逆续使用个子密钥，再逆续使用l2）反序产生。
反序产生在前面讲过的密钥扩展过程中若改在前面讲过的密钥扩展过程中若改LSi为为ll则也就可以依次产生这逆序的子密钥则也就可以依次产生这逆序的子密钥54 ÜDES加密实例加密实例l取取16进制明文进制明文X：：0123456789ABCDEFl密钥密钥K为：为： 133457799BBCDFF1l去掉奇偶校验位以二进制形式表示的密钥是去掉奇偶校验位以二进制形式表示的密钥是l00010010011010010101101111001001101101111011011111111000l应用初始置换应用初始置换IP，我们得到：，我们得到：L0=11001100000000001100110011111111R0=11110000101010101111000010101010然后进行然后进行16轮加密最后对轮加密最后对L16, R16 使用使用IP-1得到密文：得到密文：85E813540F0AB40555 ÜDES的设计特色：的设计特色：Ü在在DES算法中，函数是最基本的关键环节，算法中，函数是最基本的关键环节，Ü其中其中l用用S-盒实现小块盒实现小块的非线性变换，达到混乱目的；的非线性变换，达到混乱目的；l用用置换置换P实现大块实现大块的非线性变换，达到扩散目的。
的非线性变换，达到扩散目的l置换置换P的设计的设计使每层使每层S-盒的盒的4bit输出进入到下一层的输出进入到下一层的4个不同个不同S-盒盒l每个每个S-盒的输入由分属上一层中盒的输入由分属上一层中4个不同个不同S-盒的输出构成盒的输出构成ÜDES的核心是的核心是S盒，除此之外的计算是属线性的盒，除此之外的计算是属线性的lS盒作为该密码体制的非线性组件对安全性至关重要盒作为该密码体制的非线性组件对安全性至关重要lS-盒的设计准则还没有完全公开一些密码学家怀疑美国盒的设计准则还没有完全公开一些密码学家怀疑美国NSA(the National Security Agency)设计设计S-盒时隐藏了盒时隐藏了“陷门陷门”，使得只有他们才知道破译算法，但没有证据能表明这一点使得只有他们才知道破译算法，但没有证据能表明这一点56 Ü1976年，美国年，美国NSA披露了披露了S-盒的下述几条设计原则：盒的下述几条设计原则：l每个每个S-盒的每一行是整数盒的每一行是整数0~15的一个全排列；的一个全排列；l每个每个S-盒的输出都不是其输入的线性或仿射函数；盒的输出都不是其输入的线性或仿射函数；l改变任一改变任一S-盒任意盒任意1bit的输入，其输出至少有的输入，其输出至少有2bit发生变化；发生变化；l对任一对任一S-盒的任意盒的任意6bit输入输入x，，S(x)与与S(x 001100)至少有至少有2bit不同；不同；l对任一对任一S-盒的任意盒的任意6bit输入输入x，及，及 , {0,1}，都有，都有S(x)≠S(x 1100)；；l对任一对任一S-盒，当它的任一位输入保持不变，其它盒，当它的任一位输入保持不变，其它5位输入尽情变化时，所位输入尽情变化时，所有诸有诸4bit输出中，输出中，0与与1的总数接近相等。
的总数接近相等ÜS盒的争论：盒的争论：l公众仍然不知道公众仍然不知道S盒的构造中是否还使用了进一步的设计准则（有陷门？）盒的构造中是否还使用了进一步的设计准则（有陷门？）l密钥长度是否足够？（已经证明密钥长度不够）密钥长度是否足够？（已经证明密钥长度不够）l迭代的长度？（迭代的长度？（8、、16、、32？）？）57 ÜDES的安全性问题的安全性问题l完全依赖于所用的密钥，即算法是公开的完全依赖于所用的密钥，即算法是公开的Ü1）取反特性：）取反特性：l对于明文组对于明文组M，密文组，密文组C和主密钥和主密钥K，若，若C=DESK(M)，， 则则 ，，其中其中 、、 和和 ,分别为分别为M，，C和和K的逐位取反的逐位取反Ü证明：证明：l置换本身的取反特性可以保持置换本身的取反特性可以保持l(1)若以若以K为主密钥扩展的为主密钥扩展的16个加密子密钥记为个加密子密钥记为K1,K2,…,K16，则以，则以 为主密为主密钥扩展的钥扩展的16个加密子密钥为个加密子密钥为l(2)由由 ＝＝(1 a) (1 b)=a b，可得，可得 =F(Ri-1,Ki)l(3)由由 b＝＝1 a b= ，可得，可得 ＝＝ ，由此得证。
由此得证l由此由此DES在选择明文攻击时工作量会减少一半攻击者破译所使用的密钥，在选择明文攻击时工作量会减少一半攻击者破译所使用的密钥，选取两个明密文对选取两个明密文对(M,C1)和和( ,C2)，并对于可能密钥，并对于可能密钥K计算出，计算出，DESK(M)=C，若，若C=C1或或 ＝＝C2，则说明密钥为，则说明密钥为K或或 l其中其中C2=58 Ü2）弱密钥与半弱密钥）弱密钥与半弱密钥. l对合对合l大多数密码体制都有某些明显的大多数密码体制都有某些明显的“坏密钥坏密钥”，对于，对于K和和K §若由若由K扩展出来的加密子密钥为：扩展出来的加密子密钥为：K1, K2, …, K15, K16§而由而由K 扩展出来的加密子密钥却是：扩展出来的加密子密钥却是：K16, K15, …, K2, K1l即有即有DESK-1=DESK ，则称，则称K与与K 互为互为对合对合l在在F256中的中的对合对对合对：：l在在DES的主密钥扩展中，的主密钥扩展中，C0与与D0各自独立地循环移位来产生各自独立地循环移位来产生加加(解解)密子密钥密子密钥l若若C0与与D0分别是分别是{00,11,10,01}中任意一个的中任意一个的14次重复次重复，则，则因这样的因这样的C0与与D0都对环移都对环移(无论左或右无论左或右)偶数位具有自封闭性偶数位具有自封闭性59 l若若PC-1-1(C0D0)=K,则由则由K扩展出来的加密子密钥为：扩展出来的加密子密钥为：lK1, K2, K2, K2, K2, K2, K2, K2, K1, K1, K1, K1, K1, K1, K1, K2l把把C0与与D0各自左环移一位得各自左环移一位得C1与与D1，设，设PC-1-1 (C1D1)=K ，则由，则由K 扩展出来的加密子密钥为：扩展出来的加密子密钥为：lK2, K1, K1, K1, K1, K1, K1, K1, K2, K2, K2, K2, K2, K2, K2, K1l因此，由上述因此，由上述C0与与D0导致的导致的K与与K 互为对合；互为对合；K中只有中只有这些对合对这些对合对l对于对于K，若，若K是自己的对合，则称是自己的对合，则称K为为DES的一个弱密钥的一个弱密钥l若若K存在异于自己的对合，则称存在异于自己的对合，则称K为为DES的一个半弱密钥的一个半弱密钥60 l显然，显然，C0与与D0分别是分别是{00,11,10,01}中任意一个的中任意一个的14次重次重复的情况共有复的情况共有42=16种种l其中其中C0与与D0分别是分别是{00,11}中任意一个的中任意一个的14次重复的情况次重复的情况(计计22=4种种)对应弱密钥；对应弱密钥；l剩下的剩下的(16-4=12种种)对应半弱密钥对应半弱密钥。
l弱密钥与半弱密钥直接引起的弱密钥与半弱密钥直接引起的“危险危险”是在多重使用是在多重使用DES加密中加密中，，第二次加密有可能使第一次加密复原；另外，第二次加密有可能使第一次加密复原；另外，弱密钥与半弱密钥使弱密钥与半弱密钥使得扩展出来的诸加密子密钥至多有两种差异得扩展出来的诸加密子密钥至多有两种差异，如此导致原本多轮迭，如此导致原本多轮迭代的复杂结构简化和容易分析代的复杂结构简化和容易分析l所幸在总数所幸在总数256个可选密钥中，弱密钥与半弱密钥所占的比个可选密钥中，弱密钥与半弱密钥所占的比例极小，如果是随机选择，例极小，如果是随机选择，(半半)弱密钥出现的概率很小，弱密钥出现的概率很小，因而其存在性并不会危及因而其存在性并不会危及DES的安全61 Ü3)密文与明文、密文与密钥的相关性密文与明文、密文与密钥的相关性. l人们的研究结果表明：人们的研究结果表明：DES的编码过程可使的编码过程可使每个密文比特每个密文比特都是都是所所有明文比特有明文比特和和所有密钥比特所有密钥比特的的复杂混合函数复杂混合函数，而要达到这一要求，而要达到这一要求至少需要至少需要DES的迭代：的迭代：5轮轮。
人们也用人们也用 2-检验证明：检验证明：DES迭代迭代8轮轮以后，就可认为输出和输入不相关了以后，就可认为输出和输入不相关了Ü4）密钥搜索机）密钥搜索机.l在对在对DES安全性的批评意见中，较一致的看法是安全性的批评意见中，较一致的看法是DES的密钥太短！的密钥太短！其长度其长度56bit，致使密钥量仅为，致使密钥量仅为256≈1017，不能抵抗穷搜攻击，事，不能抵抗穷搜攻击，事实证明的确如此实证明的确如此l1997年年1月月28日，美国日，美国RSA数据安全公司在数据安全公司在RSA安全年会上发布安全年会上发布了一项了一项“秘密密钥挑战秘密密钥挑战”竞赛，分别悬赏竞赛，分别悬赏1000美金、美金、5000美金和美金和10000美金用于攻破不同长度的美金用于攻破不同长度的RC5密码算法，同时还密码算法，同时还悬赏悬赏10000美金破译密钥长度为美金破译密钥长度为56bit的的DESRSA公司发起这场挑战赛是为公司发起这场挑战赛是为了调查在了调查在Internet上分布式计算的能力，并测试不同密钥长度的上分布式计算的能力，并测试不同密钥长度的RC5算法和密钥长度为算法和密钥长度为56bit的的DES算法的相对强度。
算法的相对强度62 l结果是：密钥长度为结果是：密钥长度为40bit和和48bit的的RC5算法被攻破；美国算法被攻破；美国克罗拉多州的程序员克罗拉多州的程序员Verser从从1997年年3月月13日日起用了起用了96天天的时间，在的时间，在Internet上数万名志愿者的协同工作下上数万名志愿者的协同工作下，于，于1997年年6月月17日成功地日成功地找到了找到了DES的密钥的密钥，获得了，获得了RSA公公司颁发的司颁发的10000美金的奖励这一事件表明，依靠美金的奖励这一事件表明，依靠Internet的分布式计算能力，用穷搜方法破译的分布式计算能力，用穷搜方法破译DES已成为可能因已成为可能因此，随着计算机能力的增强与计算技术的提高，必须相应此，随着计算机能力的增强与计算技术的提高，必须相应地增加密码算法的密钥长度地增加密码算法的密钥长度Ü5））DES的攻击方法的攻击方法l目前攻击目前攻击DES的主要方法有时间的主要方法有时间-空间权衡攻击、差分攻击、空间权衡攻击、差分攻击、线性攻击和相关密钥攻击等方法，在这些攻击方法中，线线性攻击和相关密钥攻击等方法，在这些攻击方法中，线性攻击方法是最有效的一种方法。
本章将对差分和线性分性攻击方法是最有效的一种方法本章将对差分和线性分析方法进行介绍析方法进行介绍63 ÜDES的评估的评估l规定规定每隔每隔5年年由美国国家保密局（由美国国家保密局（national security agency, NSA）作）作出评估，并重新批准它是否继续作为联邦加密标准最近的一次评估是出评估，并重新批准它是否继续作为联邦加密标准最近的一次评估是在在1994年年1月，美国已决定月，美国已决定1998年年12月以后将不再使用月以后将不再使用DESl一些强力攻击的案例：一些强力攻击的案例：l1997年年DESCHALL小组经过近小组经过近4个月的努力，通过个月的努力，通过Internet搜索了搜索了3×1016个密个密钥，找出了钥，找出了DES的密钥，恢复出了明文的密钥，恢复出了明文l1998年年5月美国月美国EFF(electronics frontier foundation)宣布，他们以一台价值宣布，他们以一台价值20万美元的计算机改装成的专用解密机，用万美元的计算机改装成的专用解密机，用56小时破译了小时破译了56 比特密钥的比特密钥的DESl美国国家标准和技术协会已征集并进行了几轮评估、筛选，产生了称之美国国家标准和技术协会已征集并进行了几轮评估、筛选，产生了称之为为AES(advanced encryption standard) 的新加密标准。
的新加密标准l尽管如此，尽管如此，DES对于推动密码理论的发展和应用毕竟起了重大作用，对对于推动密码理论的发展和应用毕竟起了重大作用，对于于掌握分组密码的基本理论、设计思想和实际应用掌握分组密码的基本理论、设计思想和实际应用仍然有着重要的参考仍然有着重要的参考价值64 3.2.2 二重二重DESÜ为了为了提高提高DES的安全性的安全性，并，并利用实现利用实现DES的现有软硬件的现有软硬件，，可将可将DES算法在多密钥下多重使用算法在多密钥下多重使用Ü二重二重DES是多重使用是多重使用DES时最简单的形式，如图时最简单的形式，如图4.8所示其中明文为其中明文为P，两个加密密钥为，两个加密密钥为K1和和K2l密文为：密文为：C=EK2(EK1[P])，，l解密时，以相反顺序使用两个密钥：解密时，以相反顺序使用两个密钥： P=DK1(DK2[C])Ü二重二重DES所用密钥长度为所用密钥长度为112比特，强度极大地增加比特，强度极大地增加65 Ü是否与单重是否与单重DES等价？等价？l假设对任意两个密钥假设对任意两个密钥K1和和K2，若能够找出另一密钥，若能够找出另一密钥K3，使得，使得EK2(EK1[P])=EK3[P]，则它们与，则它们与56比特密钥的单重比特密钥的单重DES等价，那么，二等价，那么，二重重DES以及多重以及多重DES都没有意义，都没有意义，好在这种假设对好在这种假设对DES并不成立并不成立。
lDES加密是一个代换，即一一映射，对加密是一个代换，即一一映射，对264个可能的输入分组到个可能的输入分组到264个可个可能的密文分组的总映射个数为能的密文分组的总映射个数为(264)!> l另一方面，对每个不同的密钥，另一方面，对每个不同的密钥，DES都定义了一个映射，总映射数为都定义了一个映射，总映射数为256<1017<< 因此，可假定用两个不同的密钥两次使用因此，可假定用两个不同的密钥两次使用DES，可，可得一个新映射，而且这一新映射不出现在单重得一个新映射，而且这一新映射不出现在单重DES定义的映射中定义的映射中l这一假定已于这一假定已于1992年被证明所以使用二重年被证明所以使用二重DES产生的映射不会等价于产生的映射不会等价于单重单重DES加密66 Ü对二重对二重DES的中途相遇攻击的中途相遇攻击l该类攻击不依赖于该类攻击不依赖于DES的任何特性，可用于攻击任何分组密码的任何特性，可用于攻击任何分组密码l注意：实施正确攻击时仅有一个名密文对，不能给出密钥是否正注意：实施正确攻击时仅有一个名密文对，不能给出密钥是否正确的判定信息，需要多个确的判定信息，需要多个Ü基本思想：基本思想：l如果有如果有 C=EK2(EK1[P])，那么，那么X=EK1[P]=DK2[C]l如果已知一个明文密文对如果已知一个明文密文对(P,C)，攻击的实施可如下进行：，攻击的实施可如下进行：l首先，用首先，用256个所有可能的个所有可能的K1对对P加密，将加密结果存入一表并对加密，将加密结果存入一表并对表按表按X排序，排序，l然后用然后用256个所有可能的个所有可能的K2对对C解密，在上述表中查找与解密，在上述表中查找与C解密结解密结果相匹配的项，如果找到，则记下相应的果相匹配的项，如果找到，则记下相应的K1和和K2。
l最后再用一新的明文密文对最后再用一新的明文密文对(P ,C )检验上面找到的检验上面找到的K1和和K2，用，用K1和和K2对对P 两次加密，若结果等于两次加密，若结果等于C ，就可确定，就可确定K1和和K2是所要是所要找的密钥找的密钥67 Ü对已知的明文对已知的明文P，二重，二重DES能产生能产生264个可能的密个可能的密文文,而可能的密钥个数为而可能的密钥个数为2112，所以平均来说，对，所以平均来说，对一个已知的明文，有一个已知的明文，有2112/264=248个密钥可产生已个密钥可产生已知的密文知的密文l即一轮攻击可将对即一轮攻击可将对(P,C)的密钥可能空间缩小为的密钥可能空间缩小为248，误报率为，误报率为248个个Ü而再经过另外一对明文密文的检验，误报率将下而再经过另外一对明文密文的检验，误报率将下降到降到248-64=2-16所以在实施中途相遇攻击时，如所以在实施中途相遇攻击时，如果已知两个明文密文对，则找到正确密钥的概率果已知两个明文密文对，则找到正确密钥的概率为为1-2-16l对另一个已知的明文，平均有对另一个已知的明文，平均有248/264=2－－16个密钥可产生已知的个密钥可产生已知的密文，即有的密文在密文，即有的密文在248个密钥空间中没有对应密钥，个密钥空间中没有对应密钥，平均不到平均不到1个个，所以两个对下来，几乎可以确定密钥，所以两个对下来，几乎可以确定密钥68 3.2.3 两个密钥的三重两个密钥的三重DESl抵抗中途相遇攻击的一种方法是使用抵抗中途相遇攻击的一种方法是使用3个不同的密钥做个不同的密钥做3次加密，次加密，从而可使已知明文攻击的代价增加到从而可使已知明文攻击的代价增加到2112。
然而，这样又会使密钥然而，这样又会使密钥长度增加到长度增加到56×3=168比特，因而过于笨重比特，因而过于笨重l一种实用的方法是仅使用两个密钥做一种实用的方法是仅使用两个密钥做3次加密，实现方式为加密次加密，实现方式为加密\|解密解密\|加密，加密，简记为简记为EDE( encrypt-decrypt-encrypt)，最早是由，最早是由Tuchman设计的，见图设计的，见图4.9，即：，即：lC=EK1(DK2(EK1[P]))l第二步解密的目的仅在第二步解密的目的仅在于使得用户可对于使得用户可对一重一重DES加密的数据解密加密的数据解密，，此方案已在密钥管理标此方案已在密钥管理标准准ANS X.917和和ISO 8732中被采用中被采用 69 3.2.4 三个密钥的三重三个密钥的三重DESÜ三个密钥的三重三个密钥的三重DES密钥长度为密钥长度为168比特，比特，加密方式为加密方式为lC=EK3(DK2(EK1[P]))l令令K3=K2或或K1=K2则变为一重则变为一重DESÜ三个密钥的三重三个密钥的三重DES已在因特网的许多应用已在因特网的许多应用（如（如PGP和和S/MIME）中被采用。
中被采用70 3.3 差分密码分析和线性密码分析差分密码分析和线性密码分析Ü3.3.1 差分密码分析－选择明文攻击差分密码分析－选择明文攻击l差分密码分析是迄今已知的攻击迭代密码最有效的方法之一，差分密码分析是迄今已知的攻击迭代密码最有效的方法之一，l其基本思想是：其基本思想是： 通过分析通过分析明文对明文对的的差值差值对对密文对密文对的的差值差值的影响来恢复的影响来恢复某些密钥比特某些密钥比特Ü对分组长度为对分组长度为n的的r轮迭代密码，两个轮迭代密码，两个n比特串比特串Yi和和Yi*的差分定的差分定义为义为lΔYi＝＝Yi (Yi*)－－1其中 表示表示n比特串集上的一个特定群运算，比特串集上的一个特定群运算，(Yi*)－－1表示表示 Yi*在此群中的逆元在此群中的逆元在在DES的差分分析中差分的计算的差分分析中差分的计算选择选择Yi Yi*，因为，因为 运算的单位元是运算的单位元是0元元Ü由加密对可得差分序列：由加密对可得差分序列：ΔY0,ΔY1,…,ΔYrl其中其中Y0和和Y0*是明文对，是明文对，Yi和和Yi* (1 i r)是第是第i轮的输出，它们同时也轮的输出，它们同时也是第是第i+1轮的输入。
第轮的输入第i轮的子密钥记为轮的子密钥记为Ki，，F是轮函数，且是轮函数，且Yi=F(Yi-1,Ki)71 Ü定义定义3-1：：r-轮特征轮特征(r-round characteristic)Ω是一个差分是一个差分序列：序列：α0,α1,…,αrl其中其中αα0 0是明文对是明文对Y0和和Y0*的差分，的差分，ααi(1≤i≤r)是第是第i轮输出轮输出Yi和和Yi*的差分的差分lr-轮特征轮特征ΩΩ= =αα0 0, ,αα1 1,…,,…,ααr r的概率是指在明文的概率是指在明文Y0和子密钥和子密钥K1,…,Kr独立、均匀随机时，明文对独立、均匀随机时，明文对Y0和和Y0*的差分为的差分为αα0 0的条件下，第的条件下，第i(1≤i≤r)轮输出轮输出Yi和和Yi*的差分为的差分为ααi i的概率l共有共有r个概率值个概率值Ü定义定义3-2：在：在r-轮特征轮特征Ω=α0,α1,…,αr中，定义中，定义l p pi iΩΩ= =P P( (ΔFΔF( (Y Y)=)=ααi| |ΔYΔY= =ααi-1 1) )l即即p pi iΩΩ表示在输入差分为表示在输入差分为ααi-1 1的条件下，轮函数的条件下，轮函数F的输出差分为的输出差分为ααi i的概率。
的概率转移概率）（转移概率）l r-轮特征轮特征ΩΩ= =αα0 0, ,αα1 1,…,,…,ααr r的概率近似看作的概率近似看作 i=1～～r p piΩΩ72 Ü对对r-轮迭代密码的差分密码分析过程可综述为如下步骤：轮迭代密码的差分密码分析过程可综述为如下步骤： l①① 找出一个找出一个(r-1)-轮特征轮特征Ω(r-1)=αα0 0, ,αα1 1,…,,…,ααr-1-1，，使得它的概率达使得它的概率达到最大或几乎最大到最大或几乎最大通过统计分析或者数学推导的方法通过统计分析或者数学推导的方法））l②② 均匀随机地选择明文均匀随机地选择明文Y0并计算并计算Y0*，，使得使得Y0和和Y0*的差分为的差分为αα0 0，，找出找出Y0和和Y0*在实际密钥加密下所得的密文在实际密钥加密下所得的密文Yr和和Yr*l若若最后一轮的子密钥最后一轮的子密钥Kr（或（或Kr的部分比特）有的部分比特）有2m个可能值个可能值Krj(1≤j≤2m)，设置相应的，设置相应的2m个计数器个计数器Λj(1≤j≤2m)；；用每个用每个Krj解密密文解密密文Yr和和Yr*，得到，得到Yr-1和和Yr-1*，如果，如果Yr-1和和Yr-1*的差分是的差分是αr-1，，则给相应的计数器则给相应的计数器Λj加加1。
l③③ 重复步骤重复步骤②②，直到一个或几个计数器的值明显高于其他计数器，直到一个或几个计数器的值明显高于其他计数器的值，输出它们所对应的子密钥（或部分比特）的值，输出它们所对应的子密钥（或部分比特）ÜDES的差分攻击有比上述过程更有效的改进方式的差分攻击有比上述过程更有效的改进方式73 Ü上述原理：上述原理：l在在(r-1)-轮轮特特征征下下，，如如果果明明文文对对Y0和和Y0*的的选选择择使使得得差差分分为为α0，，则则第第(r-1)轮轮的的差差分分将将以以较较大大的的概概率率为为（（ i=1～～r piΩ））αr-1l那那么么如如果果已已知知相相应应的的密密文文对对为为Yr和和Yr*，，则则穷穷尽尽第第r轮轮子子密密钥钥进进行行1轮轮解解密密，，此此时时密密钥钥长长度度相相对对小小，，解解密密只只有有一一轮轮，，速度快，因此速度快，因此可行可行l解解密密后后的的Yr-1和和Yr-1*如如果果差差分分是是αr-1则则相相应应的的子子密密钥钥可可能能以以较较大大的的概概率率是是正正确确的的，，满满足足条条件件的的子子密密钥钥的的个个数数可可能能有很多个，对他们计数有很多个，对他们计数。
l但但如如果果选选择择足足够够多多对对的的明明文文满满足足差差分分为为α0，，则则正正确确的的子子密密钥钥所所对对应应的的计计数数将将以以很很大大的的概概率率远远远远超超过过其其它它的的子子密密钥钥的的计计数数，，从从而而破破译译出出一一些些密密钥钥比比特特，，其其它它的的剩剩余余密密钥钥比特较少可直接采用搜索的办法比特较少可直接采用搜索的办法74 示例示例Ü1轮特征轮特征(1)：： 0, 1l 0 L0 =any R0 =0000000016l 1 L1 = 0000000016 R1 = L0 p＝＝1Ü1轮特征轮特征(2)：： 0, 1l 0 L0 = 0000000016 R0 =6000000016l 1 L1 = 6000000016 R1 =0080820016 p=14/64Ü一个一个3轮特征特征: 0, 1, 2, 3l 0 L0 = 4008000016 R0 =0400000016l 1 L1 = 0400000016 R1 =0000000016 p1=1/4l 2 L2 = 0000000016 R2 =0400000016 p2=1l 3 L3 = 0400000016 R3 =4008000016 p3=1/4l3轮特征概率特征概率为p1× p2× p3＝＝1/16由此由此3 3轮特征轮特征可容易破译可容易破译仅仅4 4轮加密的轮加密的DESDES75 Ü一种攻击的复杂度可以分为两部分：一种攻击的复杂度可以分为两部分：l数据复杂度和处理复杂度。
数据复杂度和处理复杂度l数据复杂度是实施该攻击所需输入的数据量；数据复杂度是实施该攻击所需输入的数据量；l而处理复杂度是处理这些数据所需的计算量这两部分的主要部而处理复杂度是处理这些数据所需的计算量这两部分的主要部分通常被用来刻画该攻击的复杂度分通常被用来刻画该攻击的复杂度Ü差分密码分析的复杂度差分密码分析的复杂度l差分密码分析的数据复杂度是成对加密所需的选择明文对（差分密码分析的数据复杂度是成对加密所需的选择明文对（Y0，，Y0*）个数的两倍个数的两倍l差分密码分析的处理复杂度是从差分密码分析的处理复杂度是从(ΔYr-1, Yr，，Yr*)找出子密钥找出子密钥Kr（或（或Kr的部分比特）的计算量，它实际上与的部分比特）的计算量，它实际上与r无关，而且由于轮函无关，而且由于轮函数是弱的，所以此计算量在大多数情况下相对较小数是弱的，所以此计算量在大多数情况下相对较小Ü因此，差分密码分析的复杂度取决于它的数据复杂度因此，差分密码分析的复杂度取决于它的数据复杂度76 3.3.2 线性密码分析－已知明文攻击线性密码分析－已知明文攻击Ü线性密码分析是对迭代密码的一种已知明文攻击，它利用的是密码算法中的线性密码分析是对迭代密码的一种已知明文攻击，它利用的是密码算法中的“不平衡（有效）的线性逼近不平衡（有效）的线性逼近”。
Ü设明文分组长度和密文分组长度都为设明文分组长度和密文分组长度都为n比特，密钥分组长度比特，密钥分组长度m比特，记比特，记l 明文分组为明文分组为P[1]，，P[2]，，…，，P[n]，比特形式，比特形式l 密文分组为密文分组为C[1]，，C[2]，，…，，C[n]，，l 密钥分组为密钥分组为K[1]，，K[2]，，…，，K[m]Ü定义定义:A[i,j,…,k]=A[i] A[j] … A[k]Ü线性密码分析的目标就是找出以下形式的线性方程：线性密码分析的目标就是找出以下形式的线性方程：lP[i1,i2,…,ia] C[j1,j2,…,jb]=K[k1,k2,…,kc]l其中其中1 a n，，1 b n，，1 c ml即即P中的某中的某a个个bit和和C中的某中的某b个比特与个比特与K中某中某c个比特满足线性方程个比特满足线性方程Ü如果对于猜测的密钥和已知的大量明密文对，方程成立的概率如果对于猜测的密钥和已知的大量明密文对，方程成立的概率p≠1/2，则称该方，则称该方程是有效的线性逼近如果程是有效的线性逼近如果|p-1/2|是最大的，则称该方程是最有效的线性逼近。
是最大的，则称该方程是最有效的线性逼近等于等于1/2时说明随机性很好，再多明密文对也不暴露任何信息时说明随机性很好，再多明密文对也不暴露任何信息77 Ü设设N表示明文数，表示明文数，T是使方程左边为是使方程左边为0的明文数的明文数Ü如果如果T>N/2，则令，则令lK[k1,k2,…,kc]＝＝Ü如果如果T
反之方程不成立的概率大于反之方程不成立的概率大于一半，则左边一半，则左边1多，右边取多，右边取178 Ü对于对于n轮轮DES，我们假定使用，我们假定使用n-1轮的轮的DES的最佳表达式，的最佳表达式，即假定已经把最后一轮使用即假定已经把最后一轮使用Kn做了解密做了解密l密文为密文为CL||CR则一轮解密后为则一轮解密后为CR F(CL,Kn) ||CLl则构造方程则构造方程P[i1,i2,…,ia] C[j1,j2,…,jb] F(CL, Kn) [e1, e2, …, ed] =K[k1,k2,…,kc]Ü表达式与表达式与F和和Kn有关，若带入一个不正确的有关，若带入一个不正确的Kn，这个等式，这个等式的有效性显然就降低了，可使用最大似然法来推导的有效性显然就降低了，可使用最大似然法来推导Kn，，l对于每一个候选的对于每一个候选的Kn(i)，，设设Ti使得等式左边为使得等式左边为0的明文个数的明文个数l对于最大的对于最大的Ti(此时对应的子密钥为此时对应的子密钥为Kn(i))记作记作Tmax，最小的记作，最小的记作Tmin，则当，则当|Tmax－－N/2|>|Tmin－－N/2 |,将将Tmax对应的候选者对应的候选者Kn(i)作为作为Kn，并猜定，并猜定K[k1,k2,…,kc]＝＝0(p>1/2)或或1 (p<1/2)，反之同理，反之同理l选取密钥的不同选取密钥的不同bit位置，将得到一组线性方程组位置，将得到一组线性方程组79 Ü如何对差分密码分析和线性密码分析进行改进，如何对差分密码分析和线性密码分析进行改进，降低它们的复杂度仍是现在理论研究的热点降低它们的复杂度仍是现在理论研究的热点l目前已推出了很多改进方法，例如目前已推出了很多改进方法，例如,l高阶差分密码分析高阶差分密码分析l截段差分密码分析（截段差分密码分析（truncated differential cryptanalysis）、）、l不可能差分密码分析不可能差分密码分析l多重线性密码分析多重线性密码分析l非线性密码分析非线性密码分析l差分差分-线性密码分析。
线性密码分析l再如针对密钥编排算法的相关密钥攻击、基于再如针对密钥编排算法的相关密钥攻击、基于Lagrange插值公插值公式的插值攻击及基于密码器件的能量分析（式的插值攻击及基于密码器件的能量分析（power analysis），），另外还有错误攻击、时间攻击、另外还有错误攻击、时间攻击、Square攻击和攻击和Davies攻击等最新的有最新的有Cubic攻击攻击80 3.4 分组密码的运行模式分组密码的运行模式Ü分组密码在加密时分组密码在加密时明文分组的长度是固定的，而实际应明文分组的长度是固定的，而实际应用中待加密消息的数据量是不定的，数据格式可能是多用中待加密消息的数据量是不定的，数据格式可能是多种多样的种多样的由于加密数据一般包含多个分组，选择合适由于加密数据一般包含多个分组，选择合适的运行模式可避免固定格式带来的安全隐患的运行模式可避免固定格式带来的安全隐患Ü为了能在各种应用场合使用为了能在各种应用场合使用DES，美国在，美国在FIPS PUS 74和和81中定义了中定义了DES的的4种运行模式，如表种运行模式，如表3.5Ü这些模式也可用于其他分组密码，下面以这些模式也可用于其他分组密码，下面以DES为例来介为例来介绍这绍这4种模式种模式81 Ü表表3-5 DES的运行模式的运行模式模式模式描述描述用途用途电码本本(ECB)(ECB)模式模式每个明文每个明文组独立地以同一密独立地以同一密钥加密加密传送短数据送短数据( (如一如一个加密密个加密密钥) )密密码分分组链接接(CBC)(CBC)模式模式加密算法的加密算法的输入是当前明文入是当前明文组与前一与前一密文密文组的异或的异或传送数据分送数据分组；；认证密密码反反馈(CFB)(CFB)模式模式每次只每次只处理理输入的入的j j比特，将上一次的比特，将上一次的密文作加密算法的密文作加密算法的输入以入以产生生伪随随机机输出，出，该输出再与当前明文异或出再与当前明文异或以以产生当前密文生当前密文传送数据流；送数据流；认证输出反出反馈(OFB)(OFB)模式模式与与CFBCFB类似不同之似不同之处是本次加密算法的是本次加密算法的输入入为前一次加密算法的前一次加密算法的输出出有有绕信道上信道上( (如如卫星通信星通信) )传送送数据流数据流计数器数器(CTR)(CTR)模式模式对计数器依次用数器依次用k k加密后与明文异或加密后与明文异或适合并行，可随适合并行，可随机机访问82 3.4.1电码本电码本(ECB)模式模式ÜECB(electronic codebook)模式是最简单的运行模式模式是最简单的运行模式l加密时：一次对一个加密时：一次对一个64比特比特长的明文分组加密，而且长的明文分组加密，而且每每次的加密密钥都相同次的加密密钥都相同l就像有一个非常大的密文就像有一个非常大的密文电码本电码本l最后一个分组如果不够最后一个分组如果不够64比比特，则特，则需要填充需要填充l解密过程也是一次对一个分解密过程也是一次对一个分组解密，而且每次解密都使组解密，而且每次解密都使用同一密钥用同一密钥消息划分为消息划分为64比特的分组比特的分组明文分组序列为明文分组序列为P1，，P2，，…，，PN，，相应的密文分组序列是相应的密文分组序列是C1，，C2，，…，，CN83 ÜECBECB在用于短数据（如加密密钥）时非常理想在用于短数据（如加密密钥）时非常理想l因此如果需要安全地传递因此如果需要安全地传递DESDES密钥，密钥，ECBECB是最合适的模式是最合适的模式ÜECBECB用于长消息时可能不够安全用于长消息时可能不够安全lECBECB下同一明文分组在消息中重复出现时产生的密文分组也相同下同一明文分组在消息中重复出现时产生的密文分组也相同l结构化明文，结构化明文，如果已知消息总是以某个预定义字段开始，那么分析者如果已知消息总是以某个预定义字段开始，那么分析者就可能得到很多明文－密文对，比如就可能得到很多明文－密文对，比如图像的头格式图像的头格式就是一种固定结构就是一种固定结构l消息有重复部分，消息有重复部分，如果消息有重复的元素而重复的周期是如果消息有重复的元素而重复的周期是6464的倍数，的倍数，那么密码分析者就能够识别这些元素那么密码分析者就能够识别这些元素l这些特性都有助于密码分析者，有可能为其提供对分组的代换或重排的机这些特性都有助于密码分析者，有可能为其提供对分组的代换或重排的机会会ÜECB模式特点总结模式特点总结l对明文分组后逐一加密对明文分组后逐一加密l适合短消息加密适合短消息加密l应用于长消息时可能受到攻击应用于长消息时可能受到攻击l往往需要填充往往需要填充84 3.4.2密码分组链接密码分组链接(CBC)模式模式ÜCBC（（cipher block chaining）模）模式可让重复的明文分组产生不同的密式可让重复的明文分组产生不同的密文分组文分组ÜCBC模式一次对一个明文分组加密，模式一次对一个明文分组加密，每次加密使用同一密钥每次加密使用同一密钥Ü加密算法的输入是当前明文分组和前加密算法的输入是当前明文分组和前一次密文分组的异或一次密文分组的异或l所以所以重复的明文分组不会在密文中暴重复的明文分组不会在密文中暴露出这种重复关系露出这种重复关系。
Ü解密时，每一个密文分组被解密后，解密时，每一个密文分组被解密后，再与前一个密文分组异或，即再与前一个密文分组异或，即lDK[Cn] Cn-1= DK[EK[Cn-1] Pn] Cn-1l= Cn-1 Pn Cn-1= Pnl（设（设Cn=EK[Cn-1] Pn]））l因而产生出明文分组因而产生出明文分组 85 Ü产生第产生第1个密文分组，个密文分组，需要有一个初始向量需要有一个初始向量IV与第与第1个明文个明文分组异或分组异或l解密时，解密时，IV和解密算法对第和解密算法对第1个密文分组的输出进行异或以恢复第个密文分组的输出进行异或以恢复第1个明文分组个明文分组ÜIV对于收发双方都应是已知的，对于收发双方都应是已知的，为使安全性最高，为使安全性最高，IV应像应像密钥一样被保护，可使用密钥一样被保护，可使用ECB加密模式来发送加密模式来发送IVÜ保护保护IV的原因如下：的原因如下：l如果敌手能欺骗接收方使用不同的如果敌手能欺骗接收方使用不同的IV值，敌手就能够在明文的第值，敌手就能够在明文的第1个分组中插入自己选择的比特值，这是因为：个分组中插入自己选择的比特值，这是因为：lC1=EK[IV P1]，，P1= IV DK[C1]l用用X(i)表示表示64比特分组比特分组X的第的第i个比特，那么个比特，那么P1(i)= IV(i) DK[C1](i)，由异或的性质得，由异或的性质得P1(i) = IV(i)DK[C1](i)，撇号表示比特补。
撇号表示比特补l上式意味着上式意味着如果敌手篡改如果敌手篡改IV中的某些比特，则接收方收到的中的某些比特，则接收方收到的P1中中相应的比特也发生了变化相应的比特也发生了变化86 ÜCBC模式特点模式特点：：l消息分组，消息分组，加密算法的加密算法的输入是当前明文入是当前明文组与前一密文与前一密文组的异或，的异或，利用一个初始向量开始：利用一个初始向量开始： lCi= DESK(Pi XOR Ci-1) C-1 =IV l初始向量初始向量IV需要保护需要保护l由于由于CBC 模式的链接机制，适合加密长度大于模式的链接机制，适合加密长度大于64比特比特的消息的消息l除用于加密外，还可以用来进行用户认证除用于加密外，还可以用来进行用户认证(消息认证消息认证)l错误传播：影响当前解密分组和下一分组错误传播：影响当前解密分组和下一分组87 3.4.3 密码反馈密码反馈(CFB)模式模式Ü利用利用CFB（（cipher feedback）模式或）模式或OFB模式模式可将可将DES转换转换为流密码为流密码流密码不需要对消息填充，而且运行是实时的流密码不需要对消息填充，而且运行是实时的l因此如果传送字母流，可使用流密码对每个字母直接加密并传送。
因此如果传送字母流，可使用流密码对每个字母直接加密并传送l流密码具有密文和明文一样长这一性质，因此，如果需要发送的每个流密码具有密文和明文一样长这一性质，因此，如果需要发送的每个字符长为字符长为8比特，就应使用比特，就应使用8比特密钥来加密每个字符如果密钥长超比特密钥来加密每个字符如果密钥长超过过8比特，则造成浪费比特，则造成浪费Ü图图3-2是是CFB模式示意图，设传送的每个单元（如一个字符）模式示意图，设传送的每个单元（如一个字符）是是j比特长，通常取比特长，通常取j=8，与，与CBC模式一样，明文单元被链接模式一样，明文单元被链接在一起，使得密文是前面所有明文的函数在一起，使得密文是前面所有明文的函数88 89 Ü 加密时，加密算法的输入是加密时，加密算法的输入是64比特移位寄存器，其初值为比特移位寄存器，其初值为某个初始向量某个初始向量IVl加密算法输出的最左加密算法输出的最左(最高有效位最高有效位)J比特与明文的第一个比特与明文的第一个单元单元P1进行异或，产生密文的第一个单元进行异或，产生密文的第一个单元C1,并传送该单并传送该单元l然后将移位寄存器的内容左移然后将移位寄存器的内容左移j位并将位并将C1送入移位寄存器送入移位寄存器最右边的最右边的j位。
位l这一过程一直进行到明文的所有单元都被加密为止这一过程一直进行到明文的所有单元都被加密为止 Ü解密时，将收到的密文单元与加密函数的输出进行异或解密时，将收到的密文单元与加密函数的输出进行异或注意这时仍然使用加密算法而不是解密算法，原因如下：注意这时仍然使用加密算法而不是解密算法，原因如下： l设设Sj(X)是是X的的j个最高有效位，那么个最高有效位，那么C1= P1 Sj[E(IV)]，，l因此因此P1= C1 Sj[E(IV)]l可证明以后各步也有类似的这种关系可证明以后各步也有类似的这种关系90 ÜCFB模式除能获得保密性外，还能用于认证模式除能获得保密性外，还能用于认证ÜCFB特点：特点：l消息被看作字符流或消息被看作字符流或bit流流 ，采用移位寄存器，适合数，采用移位寄存器，适合数据以比特或字节为单位出现，适合加密数据流据以比特或字节为单位出现，适合加密数据流l分组密文的输出中选择某固定分组密文的输出中选择某固定j比特与字符或比特异或比特与字符或比特异或生成密文，并把结果反馈到下一阶段生成密文，并把结果反馈到下一阶段l标准允许反馈任意比特标准允许反馈任意比特 (1,8 or 64 or whatever)，记作，记作 CFB-1, CFB-8, CFB-64 etc lCFB-64 ：： Ci =Pi XOR DESK (Ci-1) C-1 = IVl错误传播：错误传播：1个比特密文传输错误会传播约个比特密文传输错误会传播约64/j个分组个分组l仅需要实现加密算法仅需要实现加密算法91 3.4.4 输出反馈输出反馈(OFB)模式模式ÜOFB（（output feedback）模）模式的结构类似于式的结构类似于CFBl不同之处如下：不同之处如下：OFB模式是将加模式是将加密算法的输出反密算法的输出反馈到移位寄存器，馈到移位寄存器，而而CFB模式中是模式中是将密文单元反馈将密文单元反馈到移位寄存器到移位寄存器92 ÜOFB模式的优点是传输过程中的比特错误不会被传播模式的优点是传输过程中的比特错误不会被传播l例如例如C1中出现中出现1比特错误，在解密结果中只有比特错误，在解密结果中只有P1受到影响，以后各明文单受到影响，以后各明文单元则不受影响。
元则不受影响l而在而在CFB中，中，C1也作为移位寄存器的输入，因此它的也作为移位寄存器的输入，因此它的1比特错误会影响解比特错误会影响解密结果中各明文单元的值密结果中各明文单元的值ÜOFB的缺点是它比的缺点是它比CFB模式更易受到对消息流的篡改攻击模式更易受到对消息流的篡改攻击l比如在密文中取比如在密文中取1比特的补，那么在恢复的明文中相应位置的比特也为原比特的补，那么在恢复的明文中相应位置的比特也为原比特的补因此使得敌手有可能通过比特的补因此使得敌手有可能通过对消息校验部分的篡改和对数据部分对消息校验部分的篡改和对数据部分的篡改，而以纠错码不能检测的方式篡改密文的篡改，而以纠错码不能检测的方式篡改密文ÜOFB的特点的特点：：l消息作为比特流，移位寄存器消息作为比特流，移位寄存器l分组加密的输出与被加密的消息相异或分组加密的输出与被加密的消息相异或l比特差错不容易传播比特差错不容易传播(适合有扰信道，比如卫星等适合有扰信道，比如卫星等)l只需要实现加密算法只需要实现加密算法l不适合认证不适合认证93 Ü效率效率l可并行加密，可并行加密，l因为计数器模式因为计数器模式各块儿可单独处各块儿可单独处理理l可预处理，可预处理，l明文不参与密钥明文不参与密钥产生产生l吞吐量仅受可使用吞吐量仅受可使用并行数量的限制并行数量的限制Ü简单性简单性l只要求实现加密只要求实现加密算法算法Ü可证明安全可证明安全Ü加密数据块的随机访问加密数据块的随机访问l要访问第要访问第n块，直接将计数器加块，直接将计数器加n即可解密该块即可解密该块5. CTR计数器模式计数器模式94 Ü分组密码运行模式的发展分组密码运行模式的发展l除了前述的除了前述的5种加密模式外，有时还希望完成认证的功种加密模式外，有时还希望完成认证的功能，因此人们研究了多种功能不同的运行模式能，因此人们研究了多种功能不同的运行模式lNIST从从2000年开始致力于这方面的研究，先后推出面年开始致力于这方面的研究，先后推出面向向AES的一些运行模式的一些运行模式Ü各类分组密码运行模式包括：各类分组密码运行模式包括：l保密模式保密模式 NIST800-38A(下面前下面前5种种)lECB电码本、电码本、CBC分组链接、分组链接、CFB密文反馈、密文反馈、OFB输出反馈、输出反馈、CTR计数器模式、计数器模式、 2DEM(用于图像加密用于图像加密)95 Ü认证模式认证模式 （本质上是利用分组密码构造消息认证码（本质上是利用分组密码构造消息认证码MAC））lCBC-MAC：基于：基于DES的的CBC模式构造消息认证码模式构造消息认证码MAC ANSI X9.17lCMAC：基于密码的消息认证码，：基于密码的消息认证码，NIST SP800-38Bl3GPP-MAClPMAC：可并行计算的：可并行计算的MACÜ认证保密模式（同时提供认证和保密的模式）认证保密模式（同时提供认证和保密的模式）lCCM：： (CTR+CBC-MAC) 用于用于IEEE 802.x的的WPAN、、WLAN、、WMAN NIST800-38ClGCM、、AESKW、、OCBlNIST计划增加两个特殊用途的认证保密模式：计划增加两个特殊用途的认证保密模式：GCM 和和AESKW，，GCM 计划用计划用于强认证的环境，于强认证的环境，AESKW计划用于特殊数据计划用于特殊数据(如密钥如密钥)的认证保密的认证保密Ü国产：国产：lCCTR模式模式(连接与计数器，串行认证）连接与计数器，串行认证）lPMB模式（并行多重分组，并行认证）模式（并行多重分组，并行认证）96 3.5 IDEA算法算法ÜIDEA(International Data Encryption Algorithm)是是瑞士联邦技术学院的瑞士联邦技术学院的James Massey和来学嘉等人和来学嘉等人提出的加密算法提出的加密算法Ü第一版第一版IDEA于于1990年公布年公布，来学嘉等人在，来学嘉等人在EuroCrypt 90年会上提出了分组密码建议年会上提出了分组密码建议PES(Proposed Encryption Standard)。
Ü1991年，在年，在Biham和和Shamir提出差分密码分析提出差分密码分析之后，之后，在在EuroCrypt 91年会上，来学嘉等人又提出了年会上，来学嘉等人又提出了PES的修正版的修正版IPES(Improved PES)Ü1992年设计者又将年设计者又将IPES改名为改名为IDEA这是近些年来这是近些年来提出的分组密码中一个很成功的方案，已在提出的分组密码中一个很成功的方案，已在PGP中中采用采用(主要用于邮件加密主要用于邮件加密) 97 Ü国际密码研究协会国际密码研究协会lInternational Association for Cryptologic Research lhttp://www.iacr.orgÜ国际上的七大密码会国际上的七大密码会l欧密会欧密会(EuroCrypt)l美密会美密会(Crypt) l亚密会亚密会(AsiaCrypt)l公钥密码学年会公钥密码学年会(PKC，，Public Key Cryptography )lRSA国际会议国际会议l软件工程基础软件工程基础(FSE)l密码硬件与嵌入式系统密码硬件与嵌入式系统(CHES，，Cryptographic Hardware and Embedded Systems)98 Ü目前目前IPES已经商品化，并改名为已经商品化，并改名为IDEA。
lIDEA已由瑞士的已由瑞士的Ascom公司注册专利，以商业目的使用公司注册专利，以商业目的使用IDEA算算法必须向该公司申请许可法必须向该公司申请许可l这是这是IDEA算法使用不够广泛的原因之一算法使用不够广泛的原因之一ÜIDEA的分组长度的分组长度64位，密钥长度为位，密钥长度为128位位l抗强力攻击能力比抗强力攻击能力比DES强，同一算法既可加密也可解密强，同一算法既可加密也可解密Ü从理论上讲，从理论上讲，IDEA属于属于“强强”加密算法，至今还没有出加密算法，至今还没有出现对该算法的有效攻击算法现对该算法的有效攻击算法lIDEA能抗差分分析和相关分析；能抗差分分析和相关分析；lIDEA似乎没有似乎没有DES意义下的弱密钥；意义下的弱密钥；lIDEA的的“混淆混淆”和和“扩散扩散”设计原则来自三种运算，它们易于软、设计原则来自三种运算，它们易于软、硬件实现（加密速度快）硬件实现（加密速度快）99 3.5.1 设计原理设计原理Ü1. 密码强度密码强度l密码强度主要是通过混淆和扩散来实现密码强度主要是通过混淆和扩散来实现l混淆：是通过使用以下三种运算而获得，混淆：是通过使用以下三种运算而获得，3种运算都有两个种运算都有两个16比特的比特的输入和一个输入和一个16比特的输出：比特的输出：l①①逐比特异或，表示为逐比特异或，表示为 l②②模模216(65536)整数加法表示为整数加法表示为+，其输入和输出作，其输入和输出作16位无符号整数处理位无符号整数处理l③③模模216＋＋1(65537)整数乘法，表示为整数乘法，表示为⊙ ⊙，其输入和输出中除，其输入和输出中除16位全为位全为0作作为为216处理外，其余都作为处理外，其余都作为16位无符号整数处理。
位无符号整数处理IDEA的的S盒），盒），注意乘注意乘法群无法群无0元，这样元，这样216个元素刚好构成乘法群个元素刚好构成乘法群l216＋＋1＝＝65537是一个素数是一个素数l例如例如 0000000000000000⊙ ⊙1000000000000000=1000000000000001l这是因为这是因为216×215 mod (216+1)=－－215＝－＝－215＋＋216＋＋1＝＝215＋＋1100 l表表3－－6给出了操作数为给出了操作数为2比特长时比特长时3种运算的运算表种运算的运算表l在表中加法为模在表中加法为模22，，l乘法为模乘法为模22＋＋1，且，且0作作22处理，如果处理，如果X⊙ ⊙Y＝＝22则则X⊙ ⊙Y＝＝0XYX YX⊙⊙YX Y0 000 000 000 001 011 011 011 012 102 102 102 103 113 113 113 110 001 012 103 110 001 012 103 110 001 012 103 110 001 012 103 110 001 012 103 111 012 103 110 002 103 110 001 013 110 001 012 101 010 003 112 100 001 012 103 113 112 100 001 012 103 111 010 000 001 012 103 111 010 003 112 102 103 110 001 013 112 101 010 00101 Ü在以下意义下，在以下意义下，3种运算是不兼容的：种运算是不兼容的：l①① 3种运算中任意两种都种运算中任意两种都不满足分配律不满足分配律，例如，例如 la (b c)≠(a b) (a c)l②② 3种运算中任意两种都种运算中任意两种都不满足结合律不满足结合律，例如，例如 la (b c)≠(a b) cÜ3种运算结合起来使用可对算法的输入提供复杂种运算结合起来使用可对算法的输入提供复杂的变换，从而使得的变换，从而使得对对IDEA的密码分析比对仅使的密码分析比对仅使用异或运算的用异或运算的DES更为困难更为困难。
102 Ü扩散：算法中扩散是由称为扩散：算法中扩散是由称为乘乘加加（（multiplication/addition, MA）结构（）结构（见图见图3.14）的基本）的基本单元实现的单元实现的l该结构的输入是两个该结构的输入是两个16比特的子比特的子段和两个段和两个16比特的子密钥比特的子密钥l输出也为两个输出也为两个16比特子段比特子段l这一结构在算法中重复使用了这一结构在算法中重复使用了8次，次，获得了非常有效的扩散效果获得了非常有效的扩散效果103 Ü2．实现．实现lIDEA可方便地通过软件和硬件实现可方便地通过软件和硬件实现l①① 软件实现采用软件实现采用16比特子段处理，可通过使用比特子段处理，可通过使用容易编程的容易编程的加法、移位加法、移位等运算实现算法的等运算实现算法的3种运种运算算l②② 硬件由于加、解密相似，差别仅为使用密钥硬件由于加、解密相似，差别仅为使用密钥的方式，因此可用同一器件实现再者，算法的方式，因此可用同一器件实现再者，算法中规则的模块结构，可方便中规则的模块结构，可方便VLSI的实现的实现104 3.5.2 加密过程加密过程Ü最后的输出变换也产生最后的输出变换也产生4个个16比特的子段，比特的子段，链接起来后形成链接起来后形成64比特的密文分组。
比特的密文分组Ü每轮迭代还需使用每轮迭代还需使用6个个16比特的子密钥比特的子密钥Ü最后的输出变换需使用最后的输出变换需使用4个个16比特的子密钥，比特的子密钥，所以子密钥总数为所以子密钥总数为52Ü图图3－－15右半部分表示由初始的右半部分表示由初始的128比特密钥比特密钥产生产生52个子密钥的子密钥产生器个子密钥的子密钥产生器Ü加密过程由连续的加密过程由连续的8轮迭轮迭代和一个输出变换组成代和一个输出变换组成Ü算法将算法将64比特的明文分组分成比特的明文分组分成4个个16比特的子段比特的子段Ü每轮迭代以每轮迭代以4个个16比特的子段比特的子段作为输入，输出也为作为输入，输出也为4个个16比比特的子段特的子段105 Ü1.轮结构轮结构lIDEA第第1轮结构如右图，以后各轮也轮结构如右图，以后各轮也都是这种结构，但所用的子密钥和轮都是这种结构，但所用的子密钥和轮输入不同输入不同lIDEA不是传统的不是传统的Feistel密码结构密码结构l每轮开始时有一个变换，该变换的输每轮开始时有一个变换，该变换的输入是入是4个子段和个子段和4个子密钥个子密钥l变换中的运算是两个乘法和两个加法变换中的运算是两个乘法和两个加法l输出的输出的4个子段经异或运算形成了两个子段经异或运算形成了两个个16比特的子段作为比特的子段作为MA结构的输入结构的输入lMA结构也有两个输入的子密钥，输结构也有两个输入的子密钥，输出是两个出是两个16比特的子段比特的子段l最后，变换的最后，变换的4个输出子段和个输出子段和MA结构结构的两个输出子段经过异或运算产生这的两个输出子段经过异或运算产生这一轮的一轮的4个输出子段个输出子段106 l注意，由注意，由X2产生的输出子段和由产生的输出子段和由X3产生的输出子段交换位置后形成产生的输出子段交换位置后形成W12和和W13，目的在于进一步增加混淆，目的在于进一步增加混淆(扩散扩散)效果，使得算法更易抵抗效果，使得算法更易抵抗差分密码分析差分密码分析Ü输出变换输出变换l算法的第算法的第9步是一个输出变换。
它的结构和每一轮开始的变换结构一样，步是一个输出变换它的结构和每一轮开始的变换结构一样，不同之处在于输出变换的第不同之处在于输出变换的第2个和第个和第3个输入首先交换了位置，个输入首先交换了位置，目的在目的在于撤销第于撤销第8轮输出中两个子段的交换轮输出中两个子段的交换l还需注意，第还需注意，第9步仅需步仅需4个子密钥，而前面个子密钥，而前面8轮中每轮需要轮中每轮需要6个子密钥个子密钥107 Ü2.子密钥的产生子密钥的产生l加密过程中加密过程中52个个16比特子密钥是由比特子密钥是由128比特的加密密钥比特的加密密钥按如下方式产生按如下方式产生l前前8个子密钥个子密钥Z1，，Z2，，…，，Z8直接从加密密钥中取，即直接从加密密钥中取，即Z1取前取前16比特（最高有效位），比特（最高有效位），Z2取下面的取下面的16比特，依比特，依次类推次类推l然后加密密钥循环左移然后加密密钥循环左移25位位，再取下面，再取下面8个子密钥个子密钥Z9，，Z10，，…，，Z16，取法与，取法与Z1，，Z2，，…，，Z8的取法相同的取法相同l这一过程重复下去，直到这一过程重复下去，直到52子密钥都被产生为止子密钥都被产生为止108 Ü3．解密过程．解密过程l解密与加密过程基本相同，但使用的密钥不同，解密密钥解密与加密过程基本相同，但使用的密钥不同，解密密钥U1，，U2，，…，，U52是由加密子密钥按如下方式生成。
是由加密子密钥按如下方式生成l (1)第第i (i=1,2,…,9)轮解密的前轮解密的前4个子密钥是由加密过程个子密钥是由加密过程第第(10-i)轮的前轮的前4个子密钥得出：个子密钥得出：l其中第其中第1个和第个和第4个解密子密钥取为相应的第一个和第四个加密子个解密子密钥取为相应的第一个和第四个加密子密钥模密钥模216＋＋1乘法逆元乘法逆元l第二和第三个子密钥的取法为：第二和第三个子密钥的取法为：l当轮数为当轮数为i=2,..,8时取为相应的时取为相应的第三个和第二个第三个和第二个加密子密钥的模加密子密钥的模216加法逆元，加法逆元，l当当i=1和和9时，取为相应的时，取为相应的第二个和第三个第二个和第三个加密子密钥的模加密子密钥的模216加法加法逆元l(2)第第i(i=1,…,8)轮解密的后两个子密钥轮解密的后两个子密钥等于加密过程的第等于加密过程的第(9-i)轮的后两个子密钥轮的后两个子密钥109 Ü表表3－－7是对以上关系的总结其中是对以上关系的总结其中Zj的模的模216+1乘法逆元为乘法逆元为Zj-1，满足，满足: Zj⊙ ⊙Zj-1=1 mod(216+1)l因因216+1是一素数，所以每一个不大于是一素数，所以每一个不大于216的非的非0整数都有一个惟一的整数都有一个惟一的模模216+1乘法逆元。
乘法逆元lZj的模的模216加法逆元为－加法逆元为－Zj，满足：－，满足：－Zj Zj=0 mod 216l表表3-7IDEA加密、解密子密钥表加密、解密子密钥表轮数轮数加密子密钥加密子密钥解密子密钥解密子密钥12345678输出输出Z1 ,Z2 ,Z3 ,Z4 ,Z5 ,Z6 ,Z7 ,Z8 ,Z9 ,Z10,Z11,Z12,Z13,Z14,Z15,Z16,Z17,Z18,Z19,Z20,Z21,Z22,Z23,Z24,Z25,Z26,Z27,Z28,Z29,Z30,Z31,Z32,Z33,Z34,Z34,Z36,Z37,Z38,Z39,Z40,Z41,Z42,Z43,Z44,Z45,Z46,Z47,Z48,Z49,Z50,Z51,Z52U1 ,U2 ,U3 ,U4 ,U5 ,U6 ,U7 ,U8 ,U9 ,U10,U11,U12,U13,U14,U15,U16,U17,U18,U19,U20,U21,U22,U23,U24,U25,U26,U27,U28,U29,U30,U31,U32,U33,U34,U34,U36,U37,U38,U39,U40,U41,U42,U43,U44,U45,U46,U47,U48,U49,U50,U51,U52Z49-1,-Z50,-Z51,Z52-1,Z47,Z48,Z43-1,-Z45,-Z44,Z46-1,Z41,Z42,Z37-1,-Z39,-Z38,Z40-1,Z35,Z36,Z31-1,-Z33,-Z32,Z34-1,Z29,Z30,Z25-1,-Z27,-Z26,Z28-1,Z23,Z24,Z19-1,-Z21,-Z20,Z22-1,Z17,Z18,Z13-1,-Z15,-Z14,Z16-1,Z11,Z12,Z7-1 , -Z9 , -Z8 ,Z10-1,Z5 , Z6 ,Z1-1 , -Z2 , -Z3 ,Z4-1110 Ü下面验证解密下面验证解密过程的确可以过程的确可以得到正确的结得到正确的结果。
果Ü图图3 3－－1818中左边中左边为加密过程，为加密过程，由上至下，右由上至下，右边为解密过程，边为解密过程，由下至上由下至上Ü将每一轮进一将每一轮进一步分为两步，步分为两步，第第1 1步是变换，步是变换，其余部分作为其余部分作为第第2 2步，称为子步，称为子加密111 Ü现在从下往上考虑对加密过程最后一个输出变换，以下关现在从下往上考虑对加密过程最后一个输出变换，以下关系成立：系成立：lY1=W81⊙ ⊙Z49 Y2=W83 Z50 Y3=W82 Z51 Y4=W84⊙ ⊙Z52Ü解密过程中第解密过程中第1轮的第轮的第1步产生以下关系：步产生以下关系： lJ11=Y1⊙ ⊙U1 J12=Y2 U2 J13=Y3 U3 J14=Y4⊙ ⊙U4Ü将解密子密钥由加密子密钥表达并将将解密子密钥由加密子密钥表达并将Y1,Y2,Y3,Y4代入以下关代入以下关系，有系，有lJ11=Y1⊙ ⊙Z49-1=W81⊙ ⊙Z49⊙ ⊙Z49-1= W81 lJ12=Y2 －－Z50= W83 Z50 －－Z50=W83 lJ13=Y3 －－Z51= W82 Z51 －－Z51=W82 lJ14=Y4⊙ ⊙Z52-1=W81⊙ ⊙Z52⊙ ⊙Z52-1=W84 Ü可见解密过程第可见解密过程第1轮第轮第1步的输出等于加密过程最后一步输入步的输出等于加密过程最后一步输入中第中第2个子段和第个子段和第3个子段交换后的值。
个子段交换后的值112 Ü从图从图3－－16，可得以下关系：，可得以下关系：lW81=I81 MAR(I81 I83，，I82 I84)lW82=I83 MAR(I81 I83，，I82 I84)lW83=I82 MAL(I81 I83，，I82 I84)lW84=I84 MAL(I81 I83，，I82 I84)lV11=J11 MAR(J11 J13,J12 J14)l =W81 MAR(W81 W82,W83 W84)l =I81 MAR(I81 I83，，I82 I84) l MAR [I81 MAR(I81 I83，，I82 I84) l I83 MAR(I81 I83，，I82 I84), l I82 MAL(I81 I83，，I82 I84) l I84 MAL(I81 I83，，I82 I84)] l =I81 MAR(I81 I83，，I82 I84) l MAR(I81 I83，，I82 I84)l =I81l类似地类似地 V12=I83 V13=I82 V14=I84ÜMAR(X,Y)是是MA结构输入为结构输入为X和和Y时的右边输出，时的右边输出，MAL(X,Y)是是左边输出左边输出Ü解密过程第解密过程第1轮第轮第2步的输出等于步的输出等于加密过程倒数第加密过程倒数第2步输入中第步输入中第2个个子段和第子段和第3个子段交换后的值。
个子段交换后的值Ü同理可证图同理可证图3-18中每步都有上述中每步都有上述类似关系，这种关系一直到类似关系，这种关系一直到lV81=I11 V82=I13 V83=I12 V84=I14l即除第即除第2个子段和第个子段和第3个子段交换个子段交换位置外，解密过程的输出变换与位置外，解密过程的输出变换与加密过程第加密过程第1轮第轮第1步的变换完全步的变换完全相同l所以，除第所以，除第2个子段和第个子段和第3个子段个子段交换位置外，解密过程的输出变交换位置外，解密过程的输出变换与加密过程第换与加密过程第1轮第轮第1步的变换步的变换完全相同完全相同Ü所以最后可知，整个解密过程的所以最后可知，整个解密过程的输出等于整个加密过程的输入输出等于整个加密过程的输入113 3.6 AES算法算法—RijndaelÜAES候选算法产生过程候选算法产生过程lDES已走到尽头其已走到尽头其56比特密钥实在太小，虽然三重比特密钥实在太小，虽然三重DES可以解决密可以解决密钥长度的问题，但是钥长度的问题，但是DES的设计主要针对硬件实现，而今在许多领域，的设计主要针对硬件实现，而今在许多领域，需用软件方法来实现，需用软件方法来实现，3DES的效率相对较低的效率相对较低l鉴于此鉴于此 ,1997年年4月月15日，美国日，美国ANSI发起征集发起征集AES（（advanced encryption standard）的活动，并为此成立了）的活动，并为此成立了AES工作小组。
此次活工作小组此次活动的目的是确定一个非保密的、可以公开技术细节的、全球免费使用动的目的是确定一个非保密的、可以公开技术细节的、全球免费使用的分组密码算法，以作为新的数据加密标准的分组密码算法，以作为新的数据加密标准l1997年年9月月12日，美国联邦登记处公布了正式征集日，美国联邦登记处公布了正式征集AES候选算法的通候选算法的通告对AES的基本要求是：的基本要求是：l比三重比三重DES快快l至少与三重至少与三重DES一样安全一样安全l数据分组长度为数据分组长度为128/192/256比特比特l密钥长度为密钥长度为128/192/256比特114 Ü1998年年8月月12日日l在在首届首届AES候选会议候选会议（（first AES candidate conference）上）上公布了公布了AES的的15个候选算法个候选算法，任由全世界各机构和个人攻击和评论，这，任由全世界各机构和个人攻击和评论，这15个个候选算法是候选算法是CAST256、、CRYPTON、、E2、、DEAL、、FROG、、SAFER+、、RC6、、MAGENTA、、LOKI97、、SERPENT、、MARS、、Rijndael、、DFC、、Twofish、、HPC。
Ü1999年年3月月l在在第第2届届AES候选会议候选会议上经过对全球各密码机构和个人对候选算法分析上经过对全球各密码机构和个人对候选算法分析结果的讨论，从结果的讨论，从15个候选算法中选出了个候选算法中选出了5个这5个是个是lRC6、、Rijndael、、SERPENT、、Twofish和和MARSÜ2000年年4月月13日至日至14日日l召开了召开了第第3届届AES候选会议候选会议,继续对最后继续对最后5个候选算法进行讨论个候选算法进行讨论Ü2000年年10月月2日日lNIST宣布宣布Rijndael作为新的作为新的AES至此，经过至此，经过3年多的讨论，年多的讨论，Rijndael终于脱颖而出终于脱颖而出 115 ÜRijndael 由比利时的由比利时的Joan Daemen和和Vincent Rijmen设计，算法的原型是设计，算法的原型是Square算法，它的设计策略是算法，它的设计策略是宽轨迹策略（宽轨迹策略（wide trail strategy）l宽轨迹策略是针对差分分析和线性分析提出的宽轨迹策略是针对差分分析和线性分析提出的l它的最大优点是可以给出算法的最佳差分特征的概率及最它的最大优点是可以给出算法的最佳差分特征的概率及最佳线性逼近的偏差的界；由此，可以分析算法抵抗差分密佳线性逼近的偏差的界；由此，可以分析算法抵抗差分密码分析及线性密码分析的能力。
码分析及线性密码分析的能力ÜRijndael使用使用非线性结构的非线性结构的S-boxes，表现出足够的，表现出足够的安全余地安全余地116 ÜRijndale在在无论有无反馈模式无论有无反馈模式的计算环境下的硬，的计算环境下的硬，软件中都能显示出其非常好的性能；软件中都能显示出其非常好的性能；l它的它的密钥编排的时间很好密钥编排的时间很好，也，也具有很高的灵活性具有很高的灵活性；；lRijndael的非常的非常低的内存需求低的内存需求也使它很适合用于受限的环也使它很适合用于受限的环境；境；ÜRijndael的操作简单，并的操作简单，并可抵御时间和能量攻击可抵御时间和能量攻击，，此外，它还有许多未被特别强调的防御性能；此外，它还有许多未被特别强调的防御性能；lRijndael在在分组长度和密钥长度的设计上也很灵活分组长度和密钥长度的设计上也很灵活，算法，算法可根据分组长度和密钥长度的不同组合提供不同的迭代次可根据分组长度和密钥长度的不同组合提供不同的迭代次数数l虽然这些特征还需更深入地研究，短期内不可能被利用，虽然这些特征还需更深入地研究，短期内不可能被利用，但最终，但最终，Rijndael内在的迭代结构会显示良好的潜能来防内在的迭代结构会显示良好的潜能来防御入侵行为御入侵行为117 Ü特点：特点：l不属于不属于Feistel结构结构(采用宽轨迹策略，抗差分和采用宽轨迹策略，抗差分和线性攻击线性攻击)l加密、解密相似但不对称加密、解密相似但不对称l支持支持128/192/256(/32=Nb )数据块大小数据块大小l支持支持128/192/256(/32=Nk)密钥长度密钥长度l有较好的数学理论作为基础，安全，性能好，效有较好的数学理论作为基础，安全，性能好，效率高，易用和灵活等优点（内存需求很低，很适率高，易用和灵活等优点（内存需求很低，很适合受限环境）合受限环境）l结构简单、速度快结构简单、速度快118 3.6.1 Rijndael的数学基础和设计思想的数学基础和设计思想Ü1. 有限域有限域GF(28)l有限域中的元素可以用多种不同的方式表示。
有限域中的元素可以用多种不同的方式表示对于任意素数的方对于任意素数的方幂，都有惟一的一个有限域幂，都有惟一的一个有限域，，因此因此GF(28)的所有表示是同构的的所有表示是同构的，，但不同的表示方法会影响到但不同的表示方法会影响到GF(28)上运算的复杂度上运算的复杂度l本算法采用传统的多项式表示法：本算法采用传统的多项式表示法：l将将b7b6b5b4b3b2b1b0构成的字节构成的字节b看成系数在看成系数在GF(2)={0,1}中的多项式中的多项式 b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0Ü例如：例如： l十六进制数十六进制数‘57’对应的二进制为对应的二进制为01010111，看成一个字节，对应，看成一个字节，对应的多项式为的多项式为x6+x4+x2+x+1119 ÜAES的理论基础定义在的理论基础定义在GF(28) ,其基本的运算有其基本的运算有三种，分别为加法，乘法和三种，分别为加法，乘法和x乘Ü加法：加法：l在多项式表示中，在多项式表示中，GF(28)上两个元素的和仍然是一个次上两个元素的和仍然是一个次数不超过数不超过7的多项式，其系数等于两个元素对应系数的的多项式，其系数等于两个元素对应系数的模模2加（比特异或）。
加（比特异或）Ü例如：例如： l ‘57’+‘83’=‘D4’，用多项式表示为，用多项式表示为l(x6+x4+x2+x+1)+(x7+x+1)=x7+x6+x4+x2 (mod m(x))l用二进制表示为用二进制表示为 01010111+10000011=11010100l由于每个元素的加法逆元等于自己，所以减法和加法同由于每个元素的加法逆元等于自己，所以减法和加法同120 Ü乘法：乘法：l要计算要计算GF(28)上的乘法，必须先确定一个上的乘法，必须先确定一个GF(2)上的上的8次次不可约多项式，不可约多项式，GF(28)上两个元素的乘积就是这两个多上两个元素的乘积就是这两个多项式的模乘，在项式的模乘，在Rijndael密码中，这个密码中，这个8次不可约多项次不可约多项式确定为式确定为 m(x)=x8+x4+x3+x+1l它的十六进制表示为它的十六进制表示为‘11B’二进制为二进制为100011011Ü例如，例如，‘57’·‘83’=‘C1’可表示为以下的多可表示为以下的多项式乘法：项式乘法：l(x6+x4+x2+x+1)×(x7+x+1)=x7+x6+1(mod m(x))Ü乘法运算虽然不是标准的按字节的运算，但也是乘法运算虽然不是标准的按字节的运算，但也是比较简单的计算部件。
比较简单的计算部件121 Ü以上定义的以上定义的乘法满足交换律乘法满足交换律，且，且有单位元有单位元‘01’Ü逆元逆元，对任何次数小于，对任何次数小于8的多项式的多项式b(x)，可用推广，可用推广的欧几里得算法得的欧几里得算法得l b(x)a(x)+m(x)c(x)=1l 即即a(x)·b(x)=1 mod m(x)，因此，因此a(x)是是b(x)的乘法逆元的乘法逆元Ü再者，再者，乘法还满足分配律乘法还满足分配律：：la(x)·(b(x)+c(x))=a(x)·b(x)+a(x)·c(x)Ü所以，所以，256个字节值构成的集合，在以上定义的加个字节值构成的集合，在以上定义的加法和乘法运算下，有有限域法和乘法运算下，有有限域GF(28)的结构的结构l非非0元的乘法满足元的乘法满足Abel群，加法满足群，加法满足Abel群，＋群，＋,×满足分配率满足分配率122 ÜX乘乘lGF(28)上还定义了一个运算，称之为上还定义了一个运算，称之为x乘法，其定义为乘法，其定义为lx·b(x)= b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0x(mod m(x))l如果如果b7=0，求模结果不变，否则为乘积结果减去，求模结果不变，否则为乘积结果减去m(x)，即求乘积结果与，即求乘积结果与m(x)的异或。
的异或Ü由此得出由此得出x（十六进制数（十六进制数‘02’））乘乘b(x)可以可以先对先对b(x)在字节内左移一位在字节内左移一位（最后一位补（最后一位补0），），若若b7=1，则再与，则再与‘1B’（其二进制为（其二进制为00011011））做做逐比特异或逐比特异或来实现，来实现，该运算记为该运算记为b=xtime(a)l在专用芯片中，在专用芯片中，xtime只需只需4个异或x的幂乘运算可以重复应用的幂乘运算可以重复应用xtime来实现而任意常数乘法可以通过对中间结果相加实现而任意常数乘法可以通过对中间结果相加实现Ü例如，例如，‘57’·‘13’可按如下方式实现：可按如下方式实现： l‘57’·‘02’=xtime(57)=‘AE’；；l‘57’·‘04’=xtime(AE)=‘47’；；l‘57’·‘08’=xtime(47)=‘8E’；；l‘57’·‘10’=xtime(8E)=‘07’；；’10’即即16l‘57’·‘13’=‘57’·(‘01’ ‘02’ ‘10’) =‘57’ ‘AE’ ‘07’=‘FE’123 Ü2. 系数在系数在GF(28)上的多项式上的多项式l4个字节构成的向量个字节构成的向量可以表示为可以表示为系数在系数在GF(28)上的次数小于上的次数小于4的多项式的多项式l多项式的加法就是对应系数相加，即多项式的加法就是对应系数相加，即4字节向量的逐比特异或字节向量的逐比特异或l规定多项式的乘法运算必须要取模规定多项式的乘法运算必须要取模M(x)=x4+1，这样使得次数小于，这样使得次数小于4的的多项式的乘积仍然是一个次数小于多项式的乘积仍然是一个次数小于4的多项式，将多项式的模乘运算记的多项式，将多项式的模乘运算记为为 l设设a(x)=a3x3+a2x2+a1x+a0，，b(x)=b3x3+b2x2+b1x+b0，， c(x)=c3x3+c2x2+c1x+c0，，lc(x)=a(x) b(x) mod (x4+1) 而而xj mod (x4+1)=xj mod 4，所以，所以lc0=a0b0 a3b1 a2b2 a1b3lc1=a1b0 a0b1 a3b2 a2b3lc2=a2b0 a1b1 a0b2 a3b3lc3=a3b0 a2b1 a1b2 a0b3xj mod (x4+1)= xj+x(j-4)(x4+1) mod (x4+1) 124 Ü可将上述计算表示为可将上述计算表示为l ＝＝l注意到注意到M(x)不是不是GF(28)上的不可约多项式（甚至也不是上的不可约多项式（甚至也不是GF(2)上的不上的不可约多项式），因此非可约多项式），因此非0多项式的这种乘法不是群运算。
多项式的这种乘法不是群运算l不过在不过在Rijndael密码中，对多项式密码中，对多项式b(x)，这种乘法运算只限于乘一个，这种乘法运算只限于乘一个固定的有逆元的多项式固定的有逆元的多项式a(x)=a3x3+a2x2+a1x+a0Ü定理定理1 系数在系数在GF(28)上的多项式上的多项式a3x3+a2x2+a1x+a0是模是模x4+1可逆的，当且仅当矩阵可逆的，当且仅当矩阵Ü在在GF(28)上可逆125 Ü证明：证明：la3x3+a2x2+a1x+a0是模是模x4+1可逆的，当且仅当存在多项式可逆的，当且仅当存在多项式h3x3+h2x2+h1x+h0，使得，使得(a3x3+a2x2+a1x+a0)( h3x3+h2x2+h1x+h0)=1 mod(x4+1)l因此有因此有l(a3x3+a2x2+a1x+a0)( h2x3+h1x2+h0x+h3)=x mod(x4+1) l(a3x3+a2x2+a1x+a0)( h1x3+h0x2+h3x+h2)=x2 mod(x4+1)l(a3x3+a2x2+a1x+a0)( h0x3+h3x2+h2x+h1)=x3 mod(x4+1)；；l将以上关系写成矩阵形式即得将以上关系写成矩阵形式即得l ＝＝Üc(x)=x b(x)定义为定义为x与与b(x)的模的模x4+1乘法，即乘法，即c(x)=x b(x)l=b2x3+b1x2+b0x+b3。
其矩阵表示中，除其矩阵表示中，除a1=‘01’外，其他所有外，其他所有ai=‘00’，即，即l ＝＝l因此因此x（或（或x的幂）模乘多项式相当于对字节构成的向量进行字节循环移位的幂）模乘多项式相当于对字节构成的向量进行字节循环移位126 Ü3.设计思想设计思想ÜRijndael密码的设计力求满足以下密码的设计力求满足以下3条标准：条标准： l①① 抵抗所有已知的攻击抵抗所有已知的攻击square攻击攻击)l②② 在多个平台上速度快，编码紧凑在多个平台上速度快，编码紧凑8/16/32位平台，加解密相似位平台，加解密相似)l③③ 设计简单设计简单结构化，没有复杂运算结构化，没有复杂运算)l当前的大多数分组密码，其轮函数是当前的大多数分组密码，其轮函数是Feistel结构，即将中间状态的部分结构，即将中间状态的部分比特不加改变地简单放置到其他位置比特不加改变地简单放置到其他位置lRijndael没有这种结构，其轮函数是由没有这种结构，其轮函数是由3个不同的可逆均匀变换组成的，个不同的可逆均匀变换组成的，称它们为称它们为3个个“层层”l所谓所谓“均匀变换均匀变换”是指状态的每个比特都是用类似的方法进行处理的是指状态的每个比特都是用类似的方法进行处理的。
l不同层的特定选择大部分是建立在不同层的特定选择大部分是建立在“宽轨迹策略宽轨迹策略”的应用基础上的的应用基础上的l简单地说，简单地说，“宽轨迹策略宽轨迹策略”就是提供抗线性密码分析和差分密码分析能力的就是提供抗线性密码分析和差分密码分析能力的一种设计一种设计127 Ü为实现宽轨迹策略，轮函数为实现宽轨迹策略，轮函数3个层中的每一层个层中的每一层都有自己的功能都有自己的功能l 线性混合层线性混合层 确保多轮之上的高度扩散；确保多轮之上的高度扩散；l 非线性层非线性层 将具有最优的将具有最优的“最坏情况非线性特最坏情况非线性特性性”的的S盒并行使用盒并行使用l 密钥加层密钥加层 单轮子密钥简单地异或到中间状态单轮子密钥简单地异或到中间状态上，实现一次性掩盖上，实现一次性掩盖128 l在第一轮之前，用了一个在第一轮之前，用了一个初始密钥加层初始密钥加层l许多密码的设计中都在轮变换之前和之后用了密钥加许多密码的设计中都在轮变换之前和之后用了密钥加层，如层，如IDEAIDEA、、SAFERSAFER和和BlowfishBlowfishl在不知道密钥的情况下，对最后一个密钥加层以后的在不知道密钥的情况下，对最后一个密钥加层以后的任一层（或者是当进行已知明文攻击时，对第一个密任一层（或者是当进行已知明文攻击时，对第一个密钥加层以前的任一层）可简单地剥去。
钥加层以前的任一层）可简单地剥去l因此初始密钥加有如下作用：使加解密相似、因此初始密钥加有如下作用：使加解密相似、对安全对安全性无意义、有利于差分分析性无意义、有利于差分分析l为了使加密算法和解密算法在结构上更加接近，最后为了使加密算法和解密算法在结构上更加接近，最后一轮的线性混合层与前面各轮的线性混合层不同一轮的线性混合层与前面各轮的线性混合层不同，这，这类似于类似于DESDES的最后一轮不做左右交换可以证明这种的最后一轮不做左右交换可以证明这种设计不以任何方式提高或降低该密码的安全性设计不以任何方式提高或降低该密码的安全性129 3.6.2 算法说明算法说明lRijndael是一个迭代型分组密码，其分组长度和密钥长度都可变，是一个迭代型分组密码，其分组长度和密钥长度都可变，各自可以独立地指定为各自可以独立地指定为128比特、比特、192比特、比特、256比特比特Ü3.1状态、种子和轮数状态、种子和轮数l类似于明文分组和密文分组，算法的中间结果也须分组，称类似于明文分组和密文分组，算法的中间结果也须分组，称算法中算法中间结果的分组为状态间结果的分组为状态，所有的操作都在状态上进行所有的操作都在状态上进行。
l状态可以用状态可以用以字节为元素以字节为元素的矩阵阵列表示，该阵列有的矩阵阵列表示，该阵列有4行，列数记为行，列数记为Nb，，Nb等于分组长度除以等于分组长度除以32l 例如例如128比特密钥加密比特密钥加密192比特的明文，则明文和密钥被表示成下比特的明文，则明文和密钥被表示成下面的状态面的状态a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35k00k01k02k03k10k11k12k13k20k21k22k23k30k31k32k33130 Ü种子密钥类似地用一个以字节为元素的矩阵阵列表示种子密钥类似地用一个以字节为元素的矩阵阵列表示l该阵列有该阵列有4行，列数记为行，列数记为Nk，，Nk等于分组长度除以等于分组长度除以32表3.8是是Nb=6的状态和的状态和Nk=4的种子密钥的矩阵阵列表示的种子密钥的矩阵阵列表示Ü有时可将这些分组当作一维数组有时可将这些分组当作一维数组，其，其每一元素是每一元素是上述阵列上述阵列表示中的表示中的4字节元素构成的列向量字节元素构成的列向量l数组长度可为数组长度可为4、、6、、8，数组元素下标的范围分别是，数组元素下标的范围分别是0~3、、0~5和和0~7。
4字节元素构成的列向量有时也称为字字节元素构成的列向量有时也称为字Ü算法的输入和输出被看成是由算法的输入和输出被看成是由8比特字节构成的一维数组比特字节构成的一维数组l其元素下标的范围是其元素下标的范围是0~(4Nb –1)，因此输入和输出以字节为单位，因此输入和输出以字节为单位的分组长度分别是的分组长度分别是16、、24和和32，其元素下标的范围分别是，其元素下标的范围分别是0~15、、0~23和和0~31Ü输入的种子密钥也看成是由输入的种子密钥也看成是由8比特字节构成的一维数组比特字节构成的一维数组l其元素下标的范围是其元素下标的范围是0~(4Nk –1)，因此种子密钥以字节为单位的，因此种子密钥以字节为单位的分组长度也分别是分组长度也分别是16、、24和和32，其元素下标的范围分别是，其元素下标的范围分别是0~15、、0~23和和0~31131 Ü算法的输入算法的输入l包括最初的明文输入和中间过程的轮输入包括最初的明文输入和中间过程的轮输入l以字节为单位按以字节为单位按a00a10a20a30a01a11a21a31…的的列优先顺序列优先顺序放置到状态阵列中放置到状态阵列中l同理，种子密钥以字节为单位按同理，种子密钥以字节为单位按k00k10k20k30k01k11k21k31…的顺序放置到种子密的顺序放置到种子密钥阵列中。
钥阵列中Ü算法的输出算法的输出l包括中间过程的轮输出和最后的密文输出包括中间过程的轮输出和最后的密文输出l也是以字节为单位按相同的顺序从状态阵列中取出也是以字节为单位按相同的顺序从状态阵列中取出l若输入（或输出）分组中第若输入（或输出）分组中第n个元素对应于状态阵列的第个元素对应于状态阵列的第(i, j)位置上的元素，位置上的元素，则则n和和(i, j)有以下关系：有以下关系：li=n mod 4; j= n/4 ; n=i+4j（由于是列优先，行是余数，列是商）（由于是列优先，行是余数，列是商）Ü迭代的轮数：迭代的轮数：记为记为Nr，，Nr与与Nb和和Nk有关，表给出了有关，表给出了Nr与与Nb和和Nk的关系的关系NrNb=4Nb=6Nb=8Nk=4101214Nk=6121214Nk=8141414132 Ü2.轮函数轮函数lRijndael的轮函数由的轮函数由4个不同的计算部件组成，分别是：个不同的计算部件组成，分别是：l字节代换（字节代换（ByteSub）、行移位（）、行移位（ShiftRow））l列混合（列混合（MixColumn）、密钥加（）、密钥加（AddRoundKey））Ü(1) 字节代换（字节代换（ByteSub））l字节代换是非线性变换，独立地对状态的每个字节进行。
代换表（即字节代换是非线性变换，独立地对状态的每个字节进行代换表（即S-盒）是可逆的，由以下两个变换的合成得到：盒）是可逆的，由以下两个变换的合成得到： l①① 首先，将字节看作首先，将字节看作GF(28)上的元素，上的元素，映射到自己的乘法逆元，映射到自己的乘法逆元，‘00’映射到自己映射到自己l②② 其次，对字节做如下的（其次，对字节做如下的（GF(2)上的，可逆的）仿射变换：上的，可逆的）仿射变换：Ü = +Ü上述上述S-盒对状态的所有字节所做的变换记为盒对状态的所有字节所做的变换记为ByteSub (State)133 Ü图图3.19是字节代换示意图是字节代换示意图ÜByteSub的逆变换的逆变换由代换表的逆表做字节代换，由代换表的逆表做字节代换，可通过如下两步实现可通过如下两步实现: l首先进行仿射变换的逆变换首先进行仿射变换的逆变换l再求每一字节在再求每一字节在GF(28)上逆元上逆元S盒aijbija00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35b00b01b02b03b04bk05b10b11b12b13b14b15b20b21b22b23b24b25b30b31b32b33b34b35134 Ü(2) 行移位（行移位（ShiftRow））l行移位是将状态阵列的各行进行循环移位，不同状行移位是将状态阵列的各行进行循环移位，不同状态行的位移量不同。
态行的位移量不同l第第0行不移动行不移动l第第1行循环左移行循环左移C1个字节个字节l第第2行循环左移行循环左移C2个字节个字节l第第3行循环左移行循环左移C3个字节个字节l位移量位移量C1、、C2、、C3的取值与的取值与Nb有关，由表有关，由表3.10给出NbC1C2C3412361238134行移位和字节代行移位和字节代换可交换顺序换可交换顺序135 l按指定的位移量对状态的行进行的行移位运算按指定的位移量对状态的行进行的行移位运算记为记为ShiftRow(State)图图3.20是行移位示意图是行移位示意图lShiftRow的逆变换的逆变换是对状态阵列的后是对状态阵列的后3列分别以列分别以位移量位移量Nb-C1、、Nb-C2、、Nb-C3进行循环移位，使进行循环移位，使得第得第i行第行第j列的字节移位到列的字节移位到(j+Nb-Ci) mod Nb左移0位左移1位左移2位左移3位a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35a00a01a02a03a04a05a11a12a13a14a15a10a22a23a24a25a20a21a33a34a35a30a31a32136 Ü（（3）列混合（）列混合（MixColumn））l在列混合变换中，在列混合变换中，将状态阵列的每个列视为将状态阵列的每个列视为GF(28)上的多项式，再与上的多项式，再与一个固定的多项式一个固定的多项式c(x)进行模进行模x4+1乘法乘法。
当然要求当然要求c(x)是模是模x4+1可逆的可逆的多项式，否则列混合变换就是不可逆的，因而会使不同的输入分组对多项式，否则列混合变换就是不可逆的，因而会使不同的输入分组对应的输出分组可能相同应的输出分组可能相同Rijndael的设计者给出的的设计者给出的c(x)为为（系数用十六（系数用十六进制数表示）：进制数表示）： c(x)=‘03’x3+‘01’x2+‘01’x+‘02’lc(x)是与是与x4+1互素的，因此是模互素的，因此是模x4+1可逆的列混合运算也可写为矩阵可逆的列混合运算也可写为矩阵乘法设b(x)= c(x) a(x)，则，则l ＝＝l这个运算需要做这个运算需要做GF(28)上的乘法，但由于所乘的因子是上的乘法，但由于所乘的因子是3个固定的元素个固定的元素02、、03、、01，所以这些乘法运算仍然是比较简单的所以这些乘法运算仍然是比较简单的137 Ü对状态对状态State的所有列所做的列混合运算记为的所有列所做的列混合运算记为MixColumn（（State））Ü 图图3.21是列混合运算示意图是列混合运算示意图。
ÜÜ列混合运算的逆运算是类似的列混合运算的逆运算是类似的l即每列都用一个特定的多项式即每列都用一个特定的多项式d(x)相乘ld(x)满足满足(‘03’x3+‘01’x2+‘01’x+‘02’) d(x)=‘01’l由此可得由此可得d(x)=‘0B’x3+‘0D’x2+‘09’x+‘0E’c(x)a0ja1ja2ja3jb0jb1jb2jb3ja00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35b00b01b02b03b04b05b10b11b12b13b14b15b20b21b22b23b24b25b30b31b32b33b34b35138 Ü(4) 密钥加（密钥加（AddRoundKey）） l密钥加是将轮密钥简单地与状态进行逐比特异或轮密密钥加是将轮密钥简单地与状态进行逐比特异或轮密钥由种子密钥通过密钥编排算法得到，轮密钥长度等于钥由种子密钥通过密钥编排算法得到，轮密钥长度等于分组长度分组长度Nbl状态状态State与轮密钥与轮密钥RoundKey的密钥加运算表示为的密钥加运算表示为lAddRoundKey (State, RoundKey)l图图3.22是密钥加运算示意图。
是密钥加运算示意图l密钥加运算的逆运算是其自身密钥加运算的逆运算是其自身a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35k00k01k02k03k04k05k10k11k12k13k14k15k20k21k22k23k24k25k30k31k32k33k34k35=b00b01b02b03b04k05b10b11b12b13b14b15b20b21b22b23b24b25b30b31b32b33b34b35139 Ü综上所述，组成综上所述，组成Rijndael轮函数的计算部件简捷轮函数的计算部件简捷快速，功能互补快速，功能互补轮函数的伪C代码如下：如下：lRound (State, RoundKey)l{ ByteSub (State);l ShiftRow (State);l MixColumn (State);l AddRoundKey (State, RoundKey)l}140 Ü结尾轮的轮函数与前面各轮不同，将结尾轮的轮函数与前面各轮不同，将MixColumn这一步这一步去掉。
其伪去掉其伪C代码如下：代码如下： lFinalRound (State, RoundKey)l{l ByteSub (State);l ShiftRow (State);l AddRoundKey (State, RoundKey)l}Ü在以上伪在以上伪C代码记法中，代码记法中，State、、RoundKey 可用指针类可用指针类型，函数型，函数Round、、FinalRound、、ByteSub、、ShiftRow、、MixColumn、、AddRoundKey都在指针都在指针State、、RoundKey所指向的阵列上进行运算所指向的阵列上进行运算141 Ü3．密钥编排．密钥编排l密钥编排指从种子密钥得到轮密钥的过程，它由密钥编排指从种子密钥得到轮密钥的过程，它由密钥扩密钥扩展展和和轮密钥选取两部分轮密钥选取两部分组成其基本原则如下：组成其基本原则如下： l1）轮密钥的比特数等于分组长度乘以轮数加）轮密钥的比特数等于分组长度乘以轮数加1；例如要；例如要将将128比特的明文经过比特的明文经过10轮的加密，则总共需要轮的加密，则总共需要（（10+1））*128=1408比特的密钥比特的密钥l2）种子密钥被扩展成为扩展密钥）种子密钥被扩展成为扩展密钥l3）轮密钥从扩展密钥中取，其中第）轮密钥从扩展密钥中取，其中第1轮轮密钥取扩展密轮轮密钥取扩展密钥的前钥的前Nb个字，第个字，第2轮轮密钥取接下来的轮轮密钥取接下来的Nb个字，如此个字，如此下去下去142 Ü(1) 密钥扩展密钥扩展Ü扩展密钥是扩展密钥是以以4字节字为元素字节字为元素的一维阵列，表示为的一维阵列，表示为W[Nb*(Nr+1)]，其，其中前中前Nk个字取为种子密钥，以后每个字按递归方式定义个字取为种子密钥，以后每个字按递归方式定义l扩展算法根据扩展算法根据Nk≤6和和Nk>6有所不同。
有所不同Ü①①当当Nk 6时，扩展算法如下时，扩展算法如下lKeyExpansion (byte Key[4*Nk] , word W[Nb*(Nr+1)])l{l for (i =0; i < Nk; i ++)lW[i]=(Key[4* i],Key[4* i +1],Key[4* i +2],Key[4* i +3] );l for (i =Nk; i
Ü可以看出可以看出l扩展密钥的前扩展密钥的前Nk个字即为种子密钥个字即为种子密钥l之后的每个字之后的每个字W[i]等于前一个字等于前一个字W[i-1]与与Nk个位置之前的字个位置之前的字W[i- Nk]的异或；的异或；l不过当不过当i/Nk为整数时，须先将前一个字为整数时，须先将前一个字W[i-1]经过以下一系列的变换：经过以下一系列的变换： l1字节的循环移位字节的循环移位RotByte→用用S盒进行变换盒进行变换SubByte→异或轮常数异或轮常数Rcon[i/Nk]144 Ü②②当当Nk>6时，扩展算法如下时，扩展算法如下lKeyExpansion (byte Key[4*Nk] , word W[Nb*(Nr+1)])l{l for (i=0; i < Nk; i ++)lW[i]=(Key[4* i], Key[4* i +1], Key[4* i +2], Key[4* i +3] );lfor (i =Nk; i 6与与Nk≤6的密钥扩展算法的区别在于：当的密钥扩展算法的区别在于：当i为为Nk的的4的的倍数时，须先将前一个字倍数时，须先将前一个字W[i-1]经过经过SubByte变换。
变换Ü以上两个算法中，以上两个算法中，Rcon[i/Nk] 为轮常数，其值与为轮常数，其值与Nk无关，定义为（字节用十六进制表示，同时理无关，定义为（字节用十六进制表示，同时理解为解为GF(28)上的元素）：上的元素）：l Rcon [i]=(RC[i], ‘00’, ‘00’, ‘00’)l 其中其中RC[i] 是是GF(28) 中值为中值为xi-1的元素，因此的元素，因此lRC[1] =1(即即‘01’)lRC[i] = x(即即‘02’)·RC[i-1]= xi-1146 Ü(2) 轮密钥选取轮密钥选取l轮密钥轮密钥i（即第（即第i 个轮密钥）由轮密钥缓冲字个轮密钥）由轮密钥缓冲字W[Nb* i]到到W[Nb*(i+1)]给出，如图给出，如图3.23所示lNb=6且且Nk=4时的密钥扩展与轮密钥选取时的密钥扩展与轮密钥选取W0W1W2W3W4W5W6W7W8W9W10W11W12W13W14……轮密钥轮密钥0轮密钥轮密钥1……147 Ü4．加密算法．加密算法Ü加密算法为顺序完成以下操作：初始的密钥加；加密算法为顺序完成以下操作：初始的密钥加；(Nr-1)轮迭代；一个结尾轮。
即轮迭代；一个结尾轮即lRijndael (State, CipherKey)l{lKeyExpansion (CipherKey, ExpandedKey);lAddRoundKey (State, ExpandedKey);lfor (i=1; i
首先给出几个引理Ü引理引理3.1 设字节代换（设字节代换（ByteSub）、行移位）、行移位（（ShiftRow）的逆变换分别为）的逆变换分别为InvByteSub、、InvShiftRowl则组合部件则组合部件“ByteSub→ShiftRow”的逆变换为的逆变换为“InvByteSub→InvShiftRow”l证明：组合部件证明：组合部件“ByteSub→ShiftRow”的逆变换原本的逆变换原本为为“InvShiftRow→InvByteSub”由于字节代换由于字节代换（（ByteSub）是对每个字节进行相同的变换，故）是对每个字节进行相同的变换，故“InvShiftRow”与与“InvByteSub”两个计算部件可以两个计算部件可以交换顺序证毕）交换顺序证毕）150 Ü引理引理3.2 设列混合（设列混合（MixColumn）的逆变换为）的逆变换为InvMixColumn 则列混合部件与密钥加部件则列混合部件与密钥加部件（（AddRoundKey）的组合部件）的组合部件“MixColumn→AddRoundKey (·, Key)”的逆变换的逆变换为为“InvMixColumn→AddRoundKey (·, InvKey)”l其中密钥其中密钥InvKey与与Key的关系为：的关系为：InvKey=InvMixColumn (Key)151 Ü证明：证明：l组合部件组合部件“MixColumn→AddRoundKey (·, Key)” 的逆变的逆变换原本为换原本为“AddRoundKey (·, Key)→InvMixColumn”，，l由于列混合（由于列混合（MixColumn）实际上是线性空间）实际上是线性空间GF(28)4上的上的可逆线性变换，因此可逆线性变换，因此“AddRoundKey (·,Key)→InvMixColumn”l=“InvMixColumn→AddRoundKey (·, InvMixColumn (Key))”（证毕）（证毕）l由由t(x)=a(x)*c(x)+key(x),知逆向列混淆后知逆向列混淆后 t(x)*c-1(x)= a(x)+key(x)*c-1(x),从而从而a(x) = t(x)*c-1(x) + key(x)*c-1(x),所以逆的列混淆后应该加上轮密钥列混淆后的结果所以逆的列混淆后应该加上轮密钥列混淆后的结果152 Ü引理3.3 将某一轮的后两个计算部件和下一轮的前两个计算部件组成将某一轮的后两个计算部件和下一轮的前两个计算部件组成组合部件，该组合部件的程序为组合部件，该组合部件的程序为lMixColumn (State)；；l AddRoundKey (State, Key(i));l ByteSub (State);l ShiftRow (State)Ü则该组合部件的逆变换程序为则该组合部件的逆变换程序为lInvByteSub (State);l InvShiftRow (State);l InvMixColumn (State);l AddRoundKey (State, InvMixColumn (Key(i)))Ü证明：这是引理证明：这是引理3.1和引理和引理3.2的直接推论。
的直接推论l注意到在引理注意到在引理3.3所描述的逆变换中，第所描述的逆变换中，第2步到第步到第4步在形状上很像加密算步在形状上很像加密算法的轮函数，这将是解密算法的轮函数注意到结尾轮只有法的轮函数，这将是解密算法的轮函数注意到结尾轮只有3个计算部件，个计算部件，因此可以得到如下定理因此可以得到如下定理153 Ü定理定理3-2 Rijndael密码的解密算法为顺序完成以下操作：初始的密钥加；密码的解密算法为顺序完成以下操作：初始的密钥加；(Nr-1)轮迭代；一个结尾轮其中解密算法的轮函数为轮迭代；一个结尾轮其中解密算法的轮函数为lInvRound (State, RoundKey)l{l InvByteSub (State);l InvShiftRow (State);l InvMixColumn (State);l AddRoundKey (State, RoundKey)l}Ü解密算法的结尾轮为解密算法的结尾轮为lInvFinalRound (State, RoundKey)l{l InvByteSub (State);l InvShiftRow (State);l AddRoundKey (State, RoundKey)l}154 Ü设加密算法的初始密钥加、第设加密算法的初始密钥加、第1轮、第轮、第2轮、轮、…、第、第Nr轮的子密钥依次为轮的子密钥依次为lk(0), k(1), k(2), …, k(Nr-1), k(Nr)Ü则解密算法的初始密钥加、第则解密算法的初始密钥加、第1轮、第轮、第2轮、轮、…、第、第Nr轮的子密钥依次为轮的子密钥依次为lk(Nr), InvMixColumn (k(Nr-1)), InvMixColumn (k(Nr-2)), …,InvMixColumn (k(1)), k(0)。
Ü证明：这是上述证明：这是上述3个引理的直接推论个引理的直接推论l综上所述，综上所述，Rijndael密码的解密算法与加密算法的计算网密码的解密算法与加密算法的计算网络相同络相同，只是将各计算部件换为对应的逆部件只是将各计算部件换为对应的逆部件155 Ü作业：作业：p76,1,2,3,4,5,6Ü已知明文为已知明文为01234567的的ASCII码表示的码表示的128比特比特Ü密钥：密钥：k1是是01011011的的7次重复，次重复，k2是是00001110的的7次重复构成的一共次重复构成的一共112比特密钥比特密钥Ü编写编写EDE的加解密程序，对明文进行加密，并进的加解密程序，对明文进行加密，并进行解密验证行解密验证Ü(1个月以后交个月以后交),11月中旬月中旬l1.编写的代码；编写的代码；2.运行结果截屏；运行结果截屏；3只交电子版只交电子版156 。