第3章-分组密码体制(new)

1、第第3章章 分组密码体制分组密码体制3.1 分组密码概述分组密码概述3.2 数据加密标准数据加密标准3.3 差分密码分析与线性密码分析差分密码分析与线性密码分析3.4 分组密码的运行模式分组密码的运行模式3.5 IDEA3.6 AES算法算法Rijndael习题习题x=(x0,x1,xn-1)，密钥密钥k=(k0,k1,kt-1) 加密函数加密函数E：VnKVm，K为密钥空间为密钥空间输出数字序列输出数字序列y=(y0,y1,ym-1)（长为长为m的矢量）的矢量）如图如图3.1所示。所示。3.1分组密码概述分组密码概述图图3.1 分组密码框图分组密码框图分组密码实质上是字长为分组密码实质上是字

2、长为n的数字序列的的数字序列的代换密码代换密码。与流密码比较：与流密码比较： 与一组长为与一组长为n的明文数字有关。的明文数字有关。 在相同密钥下，对长为在相同密钥下，对长为n的输入明文组所实施的变换是的输入明文组所实施的变换是等同的，所以只需研究对任一组明文数字的变换规则。等同的，所以只需研究对任一组明文数字的变换规则。用途：用途： 易于构造易于构造伪随机数生成器、流密码、消息认证码伪随机数生成器、流密码、消息认证码（MAC）和杂凑函数和杂凑函数等，等， 消息认证技术、数据完整性机制、实体认证协议消息认证技术、数据完整性机制、实体认证协议以及以及单钥数字签字体制单钥数字签字体制的核心组成部分

3、。的核心组成部分。对分组密码的要求：对分组密码的要求： 安全性安全性、运行速度、存储量（程序的长度、数据分组运行速度、存储量（程序的长度、数据分组长度、高速缓存大小）、实现平台（硬件、软件、芯片）、长度、高速缓存大小）、实现平台（硬件、软件、芯片）、运行模式运行模式等。等。 需要与安全性要求之间进行适当的折中选择。需要与安全性要求之间进行适当的折中选择。通常取通常取m=n。若若mn，则为有数据扩展的分组密码；则为有数据扩展的分组密码；若若mn，则为有数据压缩的分组密码。则为有数据压缩的分组密码。在二元情况下，在二元情况下，x和和y均为二元数字序列，它们的每个分量均为二元数字序列，它们的每个分量

4、xi，yiGF(2)。设计的算法应满足下述要求：设计的算法应满足下述要求： 分组长度分组长度n要足够大。要足够大。 使分组代换字母表中的元素个数使分组代换字母表中的元素个数2n足够大，防止明文足够大，防止明文穷举攻击法奏效。穷举攻击法奏效。 DES、IDEA、FEAL和和LOKI等等: n=64 密钥量要足够大。密钥量要足够大。 尽可能消除弱密钥并使所有密钥同等地好，以防止密尽可能消除弱密钥并使所有密钥同等地好，以防止密钥穷举攻击奏效。但密钥又不能过长，以便于密钥的管理。钥穷举攻击奏效。但密钥又不能过长，以便于密钥的管理。 DES采用采用56比特密钥，看来太短了比特密钥，看来太短了IDEA采用

5、采用128比特密钥比特密钥 置换的算法要足够复杂。置换的算法要足够复杂。 充分实现明文与密钥的扩散和混淆，没有简单的关系充分实现明文与密钥的扩散和混淆，没有简单的关系可循，能抗击各种已知的攻击，如可循，能抗击各种已知的攻击，如差分攻击差分攻击和和线性攻击线性攻击； 有高的非线性阶数，实现复杂的密码变换；有高的非线性阶数，实现复杂的密码变换； 使对手破译时除了用穷举法外，无其它捷径可循。使对手破译时除了用穷举法外，无其它捷径可循。 加密和解密运算简单，易于软件和硬件高速实现。加密和解密运算简单，易于软件和硬件高速实现。 设计的算法采用规则的模块结构，如多轮迭代等，以设计的算法采用规则的模块结构，

6、如多轮迭代等，以便于软件和便于软件和VLSI快速实现；快速实现；差错传播和数据扩展要尽可能地小。差错传播和数据扩展要尽可能地小。 数据扩展。数据扩展。一般无数据扩展，在采用同态置换和随机化加密技术一般无数据扩展，在采用同态置换和随机化加密技术时可引入数据扩展。时可引入数据扩展。 差错传播尽可能地小。差错传播尽可能地小。设计分组密码时的一些常用方法。设计分组密码时的一些常用方法。代换代换、扩散和混淆扩散和混淆、Feistel密码结构密码结构变换是可逆的，称明文分组到密文分组的可逆变换为代换。变换是可逆的，称明文分组到密文分组的可逆变换为代换。不同可逆变换的个数有不同可逆变换的个数有2n!个。个。

7、图图3.2 n=4的代换密码的一般结构的代换密码的一般结构3.1.1 代换代换问题：问题：1) 分组长度太小，通过对明文的统计分析被攻破。分组长度太小，通过对明文的统计分析被攻破。2) 分组长度很大的可逆代换结构是不实际的。分组长度很大的可逆代换结构是不实际的。对对n比特的代换结构，密钥的大小是比特的代换结构，密钥的大小是n2n比特。如比特。如n=64，密钥大小，密钥大小: 64264=2701021比特，难以处理。比特，难以处理。将将n分成较小的段分成较小的段，例如可选，例如可选n=rn0，其中其中r和和n0都是正都是正整数，将设计整数，将设计n个变量的代换变为设计个变量的代换变为设计r个较

8、小的子代换，个较小的子代换，而每个子代换只有而每个子代换只有n0个输入变量。个输入变量。一般一般n0都不太大，称每个子代换为代换盒，简称为都不太大，称每个子代换为代换盒，简称为S盒。盒。Shannon提出的设计密码系统的两个基本方法提出的设计密码系统的两个基本方法目的目的:抗击敌手对密码系统的统计分析。抗击敌手对密码系统的统计分析。在在Shannon称之为理想密码的密码系统中，密文的所有称之为理想密码的密码系统中，密文的所有统计特性都与所使用的密钥独立。统计特性都与所使用的密钥独立。图图3.2讨论的代换密码就是这样的一个密码系统，然而讨论的代换密码就是这样的一个密码系统，然而它是不实用的。它是

9、不实用的。3.1.2 扩散和混淆扩散和混淆扩散。扩散。将明文的统计特性散布到密文中去，密文中每一位将明文的统计特性散布到密文中去，密文中每一位均受明文中多位影响。均受明文中多位影响。目的：使明文和密文之间的统计关系变得尽可能复杂，以目的：使明文和密文之间的统计关系变得尽可能复杂，以使敌手无法得到密钥。使敌手无法得到密钥。如如明文的统计特性将被散布到密文中，每一字母在密文明文的统计特性将被散布到密文中，每一字母在密文中出现的频率比在明文中出现的频率更接近于相等，双字中出现的频率比在明文中出现的频率更接近于相等，双字母及多字母出现的频率也更接近于相等。母及多字母出现的频率也更接近于相等。可对数据重

10、复执行某个置换，再对这一置换作用于一可对数据重复执行某个置换，再对这一置换作用于一函数，可获得扩散。函数，可获得扩散。1mod26knn iiychrord m混淆。混淆。使密文和密钥之间的统计关系变得尽可能复杂，以使密文和密钥之间的统计关系变得尽可能复杂，以使敌手无法得到密钥。使敌手无法得到密钥。 使用复杂的代换算法可以得到预期的混淆效果，而简使用复杂的代换算法可以得到预期的混淆效果，而简单的线性代换函数得到的混淆效果则不够理想。单的线性代换函数得到的混淆效果则不够理想。扩散和混淆成功地实现了分组密码的本质属性，因而扩散和混淆成功地实现了分组密码的本质属性，因而成为设计现代分组密码的基础。成

11、为设计现代分组密码的基础。发明者发明者 Horst Feistel ，物理学家兼密码学家，在他为，物理学家兼密码学家，在他为 IBM 工作的时候，为工作的时候，为Feistel 密码结构的研究奠定了基础。密码结构的研究奠定了基础。 1973年首次踏上历史舞台。当时美国联邦政府正试图年首次踏上历史舞台。当时美国联邦政府正试图采用采用DES，于是便使用于是便使用Feistel 网络作为网络作为DES 的要素之一。的要素之一。思想：思想：利用乘积密码可获得简单的代换密码，乘积密利用乘积密码可获得简单的代换密码，乘积密码指顺序地执行两个或多个基本密码系统，使得最后结果码指顺序地执行两个或多个基本密码系

12、统，使得最后结果的密码强度高于每个基本密码系统。的密码强度高于每个基本密码系统。Shannon提出的利用乘积密码实现混淆和扩散思想的提出的利用乘积密码实现混淆和扩散思想的具体应用具体应用3.1.3 Feistel密码结构密码结构1.Feistel加密结构加密结构输入：长为输入：长为2w的明文，分成左右的明文，分成左右两半两半L0和和R0，一个密钥一个密钥K。在进行完在进行完n轮迭代后，左右两半轮迭代后，左右两半再合并到一起以产生密文分组。再合并到一起以产生密文分组。 第第i轮迭代的输入为前一轮输出的轮迭代的输入为前一轮输出的函数：函数：Ki：第：第i轮用的子密钥，由加密密轮用的子密钥，由加密密

13、钥钥K得到。得到。111,iiiiiiLRRLF RK图图3.3是是Feistel网络示意图网络示意图Feistel网络中每轮结构都相同，每轮中右半数据被作用网络中每轮结构都相同，每轮中右半数据被作用于轮函数于轮函数F后，再与左半数据进行异或运算，这一过程就是后，再与左半数据进行异或运算，这一过程就是上面介绍的代换。上面介绍的代换。每轮的轮函数的结构都相同，但以不同的子密钥每轮的轮函数的结构都相同，但以不同的子密钥Ki作作为参数。代换过程完成后，再交换左、右两半数据，这一为参数。代换过程完成后，再交换左、右两半数据，这一过程称为置换。过程称为置换。这种结构是这种结构是Shannon提出的代换提

14、出的代换置换网络置换网络（substitution -permutation network, SPN）的特有形式。的特有形式。Feistel网络的实现与以下参数和特性有关：网络的实现与以下参数和特性有关： 分组大小。分组大小。分组越大则安全性越高，但加密速度就越慢。分组越大则安全性越高，但加密速度就越慢。 最为普遍使用的分组大小是最为普遍使用的分组大小是64比特。比特。 密钥大小。密钥大小。密钥越长则安全性越高，但加密速度就越慢。密钥越长则安全性越高，但加密速度就越慢。现在普遍认为现在普遍认为64比特或更短的密钥长度是不安全的，通常使比特或更短的密钥长度是不安全的，通常使用用128比特的密钥

15、长度。比特的密钥长度。 轮数。轮数。单轮结构远不足以保证安全性，但多轮结构可提供单轮结构远不足以保证安全性，但多轮结构可提供足够的安全性。典型地，轮数取为足够的安全性。典型地，轮数取为16。 子密钥产生算法。子密钥产生算法。复杂性越大，密码分析的困难性就越大。复杂性越大，密码分析的困难性就越大。轮函数。轮函数。复杂性越大，密码分析的困难性也越大。复杂性越大，密码分析的困难性也越大。在设计在设计Feistel网络时，还有以下两个方面需要考虑：网络时，还有以下两个方面需要考虑： 快速的软件实现。快速的软件实现。在很多情况中，算法是被镶嵌在应用程序中，因而无在很多情况中，算法是被镶嵌在应用程序中，因

16、而无法用硬件实现。此时算法的执行速度是考虑的关键。法用硬件实现。此时算法的执行速度是考虑的关键。 算法容易分析。算法容易分析。如果算法能被无疑义地解释清楚，就可容易地分析算如果算法能被无疑义地解释清楚，就可容易地分析算法抵抗攻击的能力，有助于设计高强度的算法。法抵抗攻击的能力，有助于设计高强度的算法。2. Feistel解密结构解密结构Feistel解密过程本质上和加密过程是一样的，算法使用解密过程本质上和加密过程是一样的，算法使用密文作为输入，但使用子密钥密文作为输入，但使用子密钥Ki的次序与加密过程相反，的次序与加密过程相反，即第即第1轮使用轮使用Kn，第第2轮使用轮使用Kn-1，最后一轮

17、使用最后一轮使用K1。这一特性保证了解密和加密可采用同一算法。这一特性保证了解密和加密可采用同一算法。 图图3.4 Feistel加解密过程加解密过程加密过程由上而下加密过程由上而下解密过程由下而上。解密过程由下而上。加密：加密：LEi和和Rei解密：解密：LDi和和RDi加密过程第加密过程第i轮的输轮的输出是出是LEiREi解密过程第解密过程第16-i轮相轮相应的输入是应的输入是RDiLDi加密过程的最后一轮执行完后，两半输出再经交换，加密过程的最后一轮执行完后，两半输出再经交换，因此密文是因此密文是RE16LE16。解密过程取以上密文作为同一算法的输入，即第解密过程取以上密文作为同一算法的

18、输入，即第1轮输轮输入是入是RE16LE16，等于加密过程第等于加密过程第16轮两半输出交换后的结轮两半输出交换后的结果。果。下面证明解密过程第下面证明解密过程第1轮的输出等于加密过程第轮的输出等于加密过程第16轮输轮输入左右两半的交换值。入左右两半的交换值。在加密过程中：在加密过程中：在解密过程中在解密过程中161516151516,LERERELEF REK10161510016161516151516151615,LDRDLERERDLDF RDKREF REKLEF REKF REKLE所以解密过程第所以解密过程第1轮的输出为轮的输出为LE15RE15，等于加密过程第等于加密过程第16

19、轮输入左右两半交换后的结果。轮输入左右两半交换后的结果。容易证明这种对应关系在容易证明这种对应关系在16轮中每轮都成立。轮中每轮都成立。一般地，加密过程的第一般地，加密过程的第i轮有轮有因此因此111,iiiiiiLERERELEF REK111,iiiiiiiiiRELELEREF REKREF LEK以上两式描述了加密过程中第以上两式描述了加密过程中第i轮的输入与第轮的输入与第i轮输出的轮输出的函数关系，由此关系可得图函数关系，由此关系可得图3.4右边显示的右边显示的LDi和和RDi的取值的取值关系。关系。最后可以看到，解密过程第最后可以看到，解密过程第16轮的输出是轮的输出是RE0LE0

20、，左右两半再经一次交换后即得最初的明文。左右两半再经一次交换后即得最初的明文。数据加密标准（数据加密标准（data encryption standard, DES）美国美国IBM公司研制，是早期公司研制，是早期Lucifer密码的一种发展和修改密码的一种发展和修改迄今为止世界上最为广泛使用和流行的一种分组密码算法分迄今为止世界上最为广泛使用和流行的一种分组密码算法分组长度为组长度为64比特，密钥长度为比特，密钥长度为56比特比特在在1975年年3月月17日首次被公布在联邦记录中，经过大量的公开日首次被公布在联邦记录中，经过大量的公开讨论后，讨论后，DES于于1977年年1月月15日被正式批准

21、并作为美国联邦信息日被正式批准并作为美国联邦信息处理标准，即处理标准，即FIPS-46，同年同年7月月15日开始生效。日开始生效。规定每隔规定每隔5年由美国国家保密局（年由美国国家保密局（national security agency, NSA）作出评估，并重新批准它是否继续作为联邦加密标准。作出评估，并重新批准它是否继续作为联邦加密标准。3.2 数据加密标准数据加密标准最近的一次评估是在最近的一次评估是在1994年年1月，美国已决定月，美国已决定1998年年12月以后将不再月以后将不再使用使用DES。1997年年DESCHALL小组经过近小组经过近4个月的努力，通过个月的努力，通过Inte

22、rnet搜索了搜索了31016个密钥，找出了个密钥，找出了DES的密钥，恢复出了明文。的密钥，恢复出了明文。1998年年5月美国月美国EFF(electronics frontier foundation)宣布，他们以一台宣布，他们以一台价值价值20万美元的计算机改装成的专用解密机，用万美元的计算机改装成的专用解密机，用56小时破译了小时破译了56 比特密钥比特密钥的的DES。美国国家标准和技术协会美国国家标准和技术协会(NIST)已征集并进行了几轮评估、筛选，产已征集并进行了几轮评估、筛选，产生了称之为生了称之为AES(advanced encryption standard) 的新加密标准

23、。的新加密标准。尽管如此，尽管如此，DES对于推动密码理论的发展和应用毕竟起了重大作用，对于推动密码理论的发展和应用毕竟起了重大作用，对于掌握分组密码的基本理论、设计思想和实际应用仍然有着重要的参考对于掌握分组密码的基本理论、设计思想和实际应用仍然有着重要的参考价值。价值。下面首先来描述这一算法。下面首先来描述这一算法。明文分组长为明文分组长为64比特，比特，密钥长为密钥长为56比特。比特。3个阶段：个阶段：初始置换初始置换IP，具有相同功能的具有相同功能的16轮变换，轮变换，逆初始置换逆初始置换IP-1DES的结构和的结构和Feistel密码密码结构完全相同。结构完全相同。3.2.1 DES

24、描述描述图图3.5 DES加密算法框图加密算法框图图图3.5的右边是使用的右边是使用56比特密钥的方法。比特密钥的方法。密钥首先通过一个置换函数，然后，对加密过程的每密钥首先通过一个置换函数，然后，对加密过程的每一轮，通过一个左循环移位和一个置换产生一个子密钥。一轮，通过一个左循环移位和一个置换产生一个子密钥。其中每轮的置换都相同，但由于密钥被重复迭代，所其中每轮的置换都相同，但由于密钥被重复迭代，所以产生的每轮子密钥不相同。以产生的每轮子密钥不相同。1. 初始置换初始置换DES的置换表见表的置换表见表3.2。表。表3.2(a)和表和表3.2(b)分别给出了初始置分别给出了初始置换和逆初始置换

25、的定义：换和逆初始置换的定义：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为了显示这两个置换的确是彼此互逆的，考虑下面为了显示这两个置换的确是彼此互逆的，考虑下面6

26、4比比特的输入特的输入M ：其中其中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如果再取逆初

27、始置换如果再取逆初始置换Y=IP-1(X)=IP-1(IP(M)，可以看出，可以看出，M各位的初始顺序将被恢复。各位的初始顺序将被恢复。2. 轮结构轮结构图图3.6 DES加密算法的轮结构。加密算法的轮结构。首先看图的左半部分。首先看图的左半部分。将将64比特的轮输入分成各为比特的轮输入分成各为32比特的左、右两半，分别记比特的左、右两半，分别记为为L和和R。和和Feistel网络一样，每轮变换可由以下公式表示：网络一样，每轮变换可由以下公式表示：111(,)iiiiiiLRRLF RK轮密钥轮密钥Ki为为48比特，函数比特，函数F(R,K)的计算过程如图的计算过程如图3.7所示。所示。轮输入

28、的右半部分轮输入的右半部分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盒的输入长为盒的输

29、入长为6比特、输出比特、输出长为长为4比特，其变换关系由表比特，其变换关系由表3.3定义，每个定义，每个S盒给出了盒给出了4个代个代换（由一个表的换（由一个表的4行给出）。行给出）。行行 列列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 13S2S8对每个盒对每个盒S

30、i，其其6比特输入中，第比特输入中，第1个和第个和第6个比特形成个比特形成一个一个2位二进制数，用来选择位二进制数，用来选择Si的的4个代换中的一个。个代换中的一个。6比特比特输入中，中间输入中，中间4位用来选择列。行和列选定后，得到其交叉位用来选择列。行和列选定后，得到其交叉位置的十进制数，将这个数表示为位置的十进制数，将这个数表示为4位二进制数即得这一位二进制数即得这一S盒的输出。盒的输出。例如，例如，S1 的输入为的输入为011001，行选为，行选为01（即第（即第1行），列行），列选为选为1100（即第（即第12列），行列交叉位置的数为列），行列交叉位置的数为9，其，其4位二位二进制表

31、示为进制表示为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进行左循环移位，所移位数

32、由进行左循环移位，所移位数由表表3.4(c)给出。移位后的结果作为求下一轮子密钥的输入，给出。移位后的结果作为求下一轮子密钥的输入，同时也作为置换选择同时也作为置换选择2的输入。的输入。通过置换选择通过置换选择2产生的产生的48比特的比特的Ki，即为本轮的子密钥，即为本轮的子密钥，作为函数作为函数F(Ri-1,Ki)的输入。的输入。其中置换选择其中置换选择2由表由表3.4(b)定义。定义。 DES密钥编排中使用的表（表密钥编排中使用的表（表3-4） (a) 置换选择置换选择1 (b) 置换选择置换选择2 (c) 左循环移位位数左循环移位位数 注注. 对对i=1,2,16， Ci、Di分别是由分

33、别是由C0、D0左旋若干比特而得到，至左旋若干比特而得到，至i=16，刚好左旋了刚好左旋了28比特位而回复当初比特位而回复当初，即，即:C16=C0，D16=D0。 PC1PC2574941332517914171124151585042342618328156211010259514335272319124268191136052443616727201326355473931231541523137475576254463812223040514533481466153453729444939563453211352820304464250362932轮数1 2 3 4 5 6 7 8 9

34、 10 11 12 13 14 15 16位数1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1 4解密解密 和和Feistel密码一样，密码一样，DES的解密和加密算法使用同一算法，但的解密和加密算法使用同一算法，但子密钥使用的顺序相反子密钥使用的顺序相反 解密时子密钥的产生有两种方式：解密时子密钥的产生有两种方式： 1）是先由）是先由K产生产生16个子密钥，再逆续使用个子密钥，再逆续使用 2）反序产生。）反序产生。(在前面讲过的密钥扩展过程中若改在前面讲过的密钥扩展过程中若改LSi为为 则也就可以依次产生这逆序的子密钥。则也就可以依次产生这逆序的子密钥。其它, 216, 9 ,

35、 2, 11, 0iiRSi40/149 DES加密实例加密实例 取取16进制明文进制明文X：0123456789ABCDEF 密钥密钥K为：为： 133457799BBCDFF1 去掉奇偶校验位以二进制形式表示的密钥是去掉奇偶校验位以二进制形式表示的密钥是 00010010011010010101101111001001101101111011011111111000 应用初始置换应用初始置换IP，我们得到：，我们得到：L0=11001100000000001100110011111111R0=11110000101010101111000010101010然后进行然后进行16轮加密。最后对

36、轮加密。最后对L16, R16 使用使用IP-1得到密文：得到密文：85E813540F0AB40541/149 DES的设计特色：的设计特色： 在在DES算法中，函数是最基本的关键环节，算法中，函数是最基本的关键环节， 其中其中 用用S-盒实现小块盒实现小块的非线性变换，达到混乱目的；的非线性变换，达到混乱目的； 用用置换置换P实现大块实现大块的非线性变换，达到扩散目的。的非线性变换，达到扩散目的。 置换置换P的设计的设计使每层使每层S-盒的盒的4bit输出进入到下一层的输出进入到下一层的4个不同个不同S-盒盒 每个每个S-盒的输入由分属上一层中盒的输入由分属上一层中4个不同个不同S-盒的输

37、出构成。盒的输出构成。 DES的核心是的核心是S盒，除此之外的计算是属线性的。盒，除此之外的计算是属线性的。 S盒作为该密码体制的非线性组件对安全性至关重要。盒作为该密码体制的非线性组件对安全性至关重要。 S-盒的设计准则还没有完全公开。一些密码学家怀疑美国盒的设计准则还没有完全公开。一些密码学家怀疑美国NSA(the National Security Agency)设计设计S-盒时隐藏了盒时隐藏了“陷门陷门”，使得只有，使得只有他们才知道破译算法，但没有证据能表明这一点。他们才知道破译算法，但没有证据能表明这一点。42/1491976年，美国年，美国NSA披露了披露了S-盒的下述几条设计原

38、则：盒的下述几条设计原则： 每个每个S-盒的每一行是整数盒的每一行是整数015的一个全排列；的一个全排列； 每个每个S-盒的输出都不是其输入的线性或仿射函数；盒的输出都不是其输入的线性或仿射函数； 改变任一改变任一S-盒任意盒任意1bit的输入，其输出至少有的输入，其输出至少有2bit发生变化；发生变化； 对任一对任一S-盒的任意盒的任意6bit输入输入x，S(x)与与S(x 001100)至少有至少有2bit不同；不同； 对任一对任一S-盒的任意盒的任意6bit输入输入x，及，及 , 0,1，都有，都有S(x)S(x 1100)； 对任一对任一S-盒，当它的任一位输入保持不变，其它盒，当它的

39、任一位输入保持不变，其它5位输入尽情变化位输入尽情变化时，所有诸时，所有诸4bit输出中，输出中，0与与1的总数接近相等。的总数接近相等。S盒的争论：盒的争论： 公众仍然不知道公众仍然不知道S盒的构造中是否还使用了进一步的设计准则（有盒的构造中是否还使用了进一步的设计准则（有陷门？）陷门？） 密钥长度是否足够？（已经证明密钥长度不够）密钥长度是否足够？（已经证明密钥长度不够） 迭代的长度？（迭代的长度？（8、16、32？）？）43/149DES的安全性问题的安全性问题 完全依赖于所用的密钥，即算法是公开的。完全依赖于所用的密钥，即算法是公开的。1）取反特性：）取反特性： 对于明文组对于明文组M

40、，密文组，密文组C和主密钥和主密钥K，若，若C=DESK(M)， 则则 ，其中，其中 、 和和 ,分别为分别为M，C和和K的逐位取反。的逐位取反。证明：证明： 置换本身的取反特性可以保持置换本身的取反特性可以保持 (1)若以若以K为主密钥扩展的为主密钥扩展的16个加密子密钥记为个加密子密钥记为K1,K2,K16，则以，则以 为主密钥扩展的为主密钥扩展的16个加密子密钥为个加密子密钥为 (2)由由 (1 a) (1 b)=a b，可得，可得 =F(Ri-1,Ki) (3)由由 b1 a b= ，可得，可得 ，由此得证。，由此得证。 由此由此DES在选择明文攻击时工作量会减少一半。攻击者破译所使用

41、在选择明文攻击时工作量会减少一半。攻击者破译所使用的密钥，选取两个明密文对的密钥，选取两个明密文对(M,C1)和和( ,C2)，并对于可能密钥，并对于可能密钥K计计算出，算出，DESK(M)=C，若，若C=C1或或 C2，则说明密钥为，则说明密钥为K或或 。 其中其中C2=)(MDESCKba 1621,.,KKK),(1iiKRFaba ),(),(1111iiiiiiKRFLKRFLiRMCKKMCK)(MDESCK44/149 2）弱密钥与半弱密钥）弱密钥与半弱密钥. 大多数密码体制都有某些明显的大多数密码体制都有某些明显的“坏密钥坏密钥” 对于对于K和和K，若由，若由K扩展出来的加密子

42、密钥为：扩展出来的加密子密钥为：K1,K2,K15,K16，而由，而由K扩展出来的加密子密钥却是：扩展出来的加密子密钥却是：K16,K15,K2,K1，即有，即有DESK-1=DESK，则称，则称K与与K互为互为对合对合。 在在F256中的中的对合对对合对：在：在DES的主密钥扩展中，的主密钥扩展中，C0与与D0各自独立地循环移位来产生加各自独立地循环移位来产生加(解解)密子密钥。密子密钥。 若若C0与与D0分别是分别是00,11,10,01中任意一个的中任意一个的14次重复次重复，则因这样的则因这样的C0与与D0都对环移都对环移(无论左或右无论左或右)偶数位具有自偶数位具有自封闭性，故封闭性

43、，故45/149 若若PC-1-1(C0D0)=K,则由则由K扩展出来的加密子密钥为：扩展出来的加密子密钥为： K1,K2,K2,K2,K2,K2,K2,K2, K1, K1, K1, K1, K1, K1, K1, K2 把把C0与与D0各自左环移一位得各自左环移一位得C1与与D1，设，设PC-1-1 (C1D1)=K，则由，则由K扩展出来的加密子密钥为：扩展出来的加密子密钥为： K2, K1, K1, K1, K1, K1, K1, K1, K2,K2,K2,K2,K2,K2,K2, K1 因此，由上述因此，由上述C0与与D0导致的导致的K与与K互为对合；互为对合；K中中只有这些对合对只有

44、这些对合对 对于对于K，若，若K是自己的对合，则称是自己的对合，则称K为为DES的一个弱密钥的一个弱密钥 若若K存在异于自己的对合，则称存在异于自己的对合，则称K为为DES的一个半弱密钥的一个半弱密钥46/149 显然，显然，C0与与D0分别是分别是00,11,10,01中任意一个的中任意一个的14次次重复的情况共有重复的情况共有42=16种，其中种，其中C0与与D0分别是分别是00,11中任意一个的中任意一个的14次重复的情况次重复的情况(计计22=4种种)对应弱密钥；对应弱密钥；剩下的剩下的(16-4=12种种)对应半弱密钥对应半弱密钥。 弱密钥与半弱密钥直接引起的弱密钥与半弱密钥直接引起

45、的“危险危险”是在多重使用是在多重使用DES加密中加密中，第二次加密有可能使第一次加密复原；另外，第二次加密有可能使第一次加密复原；另外，弱弱密钥与半弱密钥使得扩展出来的诸加密子密钥至多有两种密钥与半弱密钥使得扩展出来的诸加密子密钥至多有两种差异差异，如此导致原本多轮迭代的复杂结构简化和容易分析。，如此导致原本多轮迭代的复杂结构简化和容易分析。 所幸在总数所幸在总数256个可选密钥中，弱密钥与半弱密钥所个可选密钥中，弱密钥与半弱密钥所占的比例极小，如果是随机选择，占的比例极小，如果是随机选择，(半半)弱密钥出现弱密钥出现的概率很小，因而其存在性并不会危及的概率很小，因而其存在性并不会危及DES

46、的安全。的安全。47/149 显然，显然，C0与与D0分别是分别是00,11,10,01中任意一个的中任意一个的14次次重复的情况共有重复的情况共有42=16种，其中种，其中C0与与D0分别是分别是00,11中任意一个的中任意一个的14次重复的情况次重复的情况(计计22=4种种)对应弱密钥；对应弱密钥；剩下的剩下的(16-4=12种种)对应半弱密钥对应半弱密钥。 弱密钥与半弱密钥直接引起的弱密钥与半弱密钥直接引起的“危险危险”是在多重使用是在多重使用DES加密中加密中，第二次加密有可能使第一次加密复原；另外，第二次加密有可能使第一次加密复原；另外，弱弱密钥与半弱密钥使得扩展出来的诸加密子密钥至

47、多有两种密钥与半弱密钥使得扩展出来的诸加密子密钥至多有两种差异差异，如此导致原本多轮迭代的复杂结构简化和容易分析。，如此导致原本多轮迭代的复杂结构简化和容易分析。 所幸在总数所幸在总数256个可选密钥中，弱密钥与半弱密钥所个可选密钥中，弱密钥与半弱密钥所占的比例极小，如果是随机选择，占的比例极小，如果是随机选择，(半半)弱密钥出现弱密钥出现的概率很小，因而其存在性并不会危及的概率很小，因而其存在性并不会危及DES的安全。的安全。48/149 3)密文与明文、密文与密钥的相关性密文与明文、密文与密钥的相关性. 人们的研究结果表明：人们的研究结果表明：DES的编码过程可使的编码过程可使每个密文比特

48、每个密文比特都是都是所所有明文比特有明文比特和和所有密钥比特所有密钥比特的的复杂混合函数复杂混合函数，而要达到这一要求，而要达到这一要求至少需要至少需要DES的迭代：的迭代：5轮轮。人们也用。人们也用 2-检验证明：检验证明：DES迭代迭代8轮轮以后，就可认为输出和输入不相关了。以后，就可认为输出和输入不相关了。 4）密钥搜索机）密钥搜索机. 在对在对DES安全性的批评意见中，较一致的看法是安全性的批评意见中，较一致的看法是DES的密钥太短！的密钥太短！其长度其长度56bit，致使密钥量仅为，致使密钥量仅为2561017，不能抵抗穷搜攻击，事实，不能抵抗穷搜攻击，事实证明的确如此。证明的确如此

49、。 1997年年1月月28日，美国日，美国RSA数据安全公司在数据安全公司在RSA安全年会上发布了安全年会上发布了一项一项“秘密密钥挑战秘密密钥挑战”竞赛，分别悬赏竞赛，分别悬赏1000美金、美金、5000美金和美金和10000美金用于攻破不同长度的美金用于攻破不同长度的RC5密码算法，同时还密码算法，同时还悬赏悬赏10000美金破译密钥长度为美金破译密钥长度为56bit的的DES。RSA公司发起这场挑战赛是为公司发起这场挑战赛是为了调查在了调查在Internet上分布式计算的能力，并测试不同密钥长度的上分布式计算的能力，并测试不同密钥长度的RC5算法和密钥长度为算法和密钥长度为56bit的的

50、DES算法的相对强度。算法的相对强度。49/149 结果是：密钥长度为结果是：密钥长度为40bit和和48bit的的RC5算法被攻破；美国算法被攻破；美国克罗拉多州的程序员克罗拉多州的程序员Verser从从1997年年3月月13日日起用了起用了96天的天的时间，在时间，在Internet上数万名志愿者的协同工作下上数万名志愿者的协同工作下，于，于1997年年6月月17日成功地日成功地找到了找到了DES的密钥的密钥，获得了，获得了RSA公司颁发的公司颁发的10000美金的奖励。这一事件表明，依靠美金的奖励。这一事件表明，依靠Internet的分布式的分布式计算能力，用穷搜方法破译计算能力，用穷搜

51、方法破译DES已成为可能。因此，随着已成为可能。因此，随着计算机能力的增强与计算技术的提高，必须相应地增加密计算机能力的增强与计算技术的提高，必须相应地增加密码算法的密钥长度。码算法的密钥长度。 5）DES的攻击方法的攻击方法 目前攻击目前攻击DES的主要方法有时间的主要方法有时间-空间权衡攻击、差分攻击、空间权衡攻击、差分攻击、线性攻击和相关密钥攻击等方法，在这些攻击方法中，线线性攻击和相关密钥攻击等方法，在这些攻击方法中，线性攻击方法是最有效的一种方法。本章将对差分和线性分性攻击方法是最有效的一种方法。本章将对差分和线性分析方法进行介绍析方法进行介绍50/149DES的评估的评估 规定规定

52、每隔每隔5年年由美国国家保密局（由美国国家保密局（national security agency, NSA）作）作出评估，并重新批准它是否继续作为联邦加密标准。最近的一次评估出评估，并重新批准它是否继续作为联邦加密标准。最近的一次评估是在是在1994年年1月，美国已决定月，美国已决定1998年年12月以后将不再使用月以后将不再使用DES。 一些强力攻击的案例：一些强力攻击的案例： 1997年年DESCHALL小组经过近小组经过近4个月的努力，通过个月的努力，通过Internet搜索了搜索了31016个密钥，找出了个密钥，找出了DES的密钥，恢复出了明文。的密钥，恢复出了明文。 1998年年5

53、月美国月美国EFF(electronics frontier foundation)宣布，他们以宣布，他们以一台价值一台价值20万美元的计算机改装成的专用解密机，用万美元的计算机改装成的专用解密机，用56小时破译小时破译了了56 比特密钥的比特密钥的DES。 美国国家标准和技术协会已征集并进行了几轮评估、筛选，产生了称美国国家标准和技术协会已征集并进行了几轮评估、筛选，产生了称之为之为AES(advanced encryption standard) 的新加密标准。的新加密标准。 尽管如此，尽管如此，DES对于推动密码理论的发展和应用毕竟起了重大作用，对于推动密码理论的发展和应用毕竟起了重大作

54、用，对于对于掌握分组密码的基本理论、设计思想和实际应用掌握分组密码的基本理论、设计思想和实际应用仍然有着重要的仍然有着重要的参考价值。参考价值。为了提高为了提高DES的安全性，并利用实现的安全性，并利用实现DES的现有软硬件，的现有软硬件，可将可将DES算法在多密钥下多重使用。算法在多密钥下多重使用。二重二重DES是多重使用是多重使用DES时最简单的形式，如图时最简单的形式，如图3.8所示。所示。其中明文为其中明文为P，两个加密密钥为两个加密密钥为K1和和K2，密文为：密文为：解密时，以相反顺序使用两个密钥：解密时，以相反顺序使用两个密钥：3.2.2 二重二重DES21 KKCEEP12 KK

55、PDDC图图3.8 二重二重DES因此，二重因此，二重DES所用密钥长度为所用密钥长度为112比特，强度极大地比特，强度极大地增加。增加。然而，假设对任意两个密钥然而，假设对任意两个密钥K1和和K2，能够找出另一密能够找出另一密钥钥K3，使得使得213 KKKEEPEP那么，二重那么，二重DES以及多重以及多重DES都没有意义，因为它们都没有意义，因为它们与与56比特密钥的单重比特密钥的单重DES等价，好在这种假设对等价，好在这种假设对DES并不并不成立。成立。将将DES加密过程加密过程64比特分组到比特分组到64比特分组的映射看作比特分组的映射看作一个置换，如果考虑一个置换，如果考虑264个

56、所有可能的输入分组，则密钥给个所有可能的输入分组，则密钥给定后，定后，DES的加密将把每个输入分组映射到一个惟一的输的加密将把每个输入分组映射到一个惟一的输出分组。否则，如果有两个输入分组被映射到同一分组，出分组。否则，如果有两个输入分组被映射到同一分组，则解密过程就无法实施。对则解密过程就无法实施。对264个输入分组，总映射个数个输入分组，总映射个数为为 。2064102!10另一方面，对每个不同的密钥，另一方面，对每个不同的密钥，DES都定义了一个映都定义了一个映射，总映射数为射，总映射数为256N/2，则令则令如果如果T6有所不同。有所不同。 当当Nk6时，扩展算法如下时，扩展算法如下

57、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的密钥扩展算法的区别在于：当的密钥扩展算法的区别在于：当

58、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 个轮密钥）由轮密钥缓冲字个轮密

59、钥）由轮密钥缓冲字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,

60、 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*