第3章 密码学基础 分组密码体制

1、第第3章章 分组密码体制分组密码体制3.1 分组密码概述（分组密码概述（Feistel密码结构，扩散和密码结构，扩散和混淆混淆）3.2 数据加密标准数据加密标准3.3 差分密码分析与线性密码分析差分密码分析与线性密码分析 *（中途相遇攻击原理中途相遇攻击原理）3.4 分组密码的运行模式分组密码的运行模式3.5 IDEA3.6 AES算法算法Rijndael 习题习题在许多密码系统中，单钥分组密码是系统安全的一在许多密码系统中，单钥分组密码是系统安全的一个重要组成部分，用分组密码易于构造伪随机数生个重要组成部分，用分组密码易于构造伪随机数生成器、流密码、消息认证码（成器、流密码、消息认证码（MA

2、C）和杂凑函数和杂凑函数等，还可进而成为消息认证技术、数据完整性机制、等，还可进而成为消息认证技术、数据完整性机制、实体认证协议以及单钥数字签字体制的核心组成部实体认证协议以及单钥数字签字体制的核心组成部分。实际应用中对于分组密码可能提出多方面的要分。实际应用中对于分组密码可能提出多方面的要求，除了安全性外，还有运行速度、存储量（程序求，除了安全性外，还有运行速度、存储量（程序的长度、数据分组长度、高速缓存大小）、实现平的长度、数据分组长度、高速缓存大小）、实现平台（硬件、软件、芯片）、运行模式等限制条件。台（硬件、软件、芯片）、运行模式等限制条件。这些都需要与安全性要求之间进行适当的折中选择

3、。这些都需要与安全性要求之间进行适当的折中选择。3.1分组密码概述分组密码概述明文明文x0,x1,xi,明文分组明文分组 x=(x0, x1, xn-1)，密钥密钥 k=(k0, k1, kt-1)密文分组密文分组 y=(y0,y1,ym-1加密函数加密函数 E：VnKVm图图3.1 分组密码框图分组密码框图通常取通常取m=n。若若mn，则为有数据扩展的分组密码；则为有数据扩展的分组密码；若若mn，则为有数据压缩的分组密码。则为有数据压缩的分组密码。设计的算法应满足下述要求：设计的算法应满足下述要求： 分组长度分组长度n要足够大，使分组代换字母表中的元要足够大，使分组代换字母表中的元素个数素个

4、数2n足够大，防止明文穷举攻击法奏效。足够大，防止明文穷举攻击法奏效。DES、IDEA、FEAL和和LOKI等分组密码都采用等分组密码都采用n=64，在生日攻击下用在生日攻击下用232组密文成功概率为组密文成功概率为1/2，同时要求同时要求23264b=215MB存贮，故采用穷举攻击是存贮，故采用穷举攻击是不现实的。不现实的。 密钥量要足够大（即置换子集中的元素足够密钥量要足够大（即置换子集中的元素足够多），尽可能消除弱密钥并使所有密钥同等地好，多），尽可能消除弱密钥并使所有密钥同等地好，以防止以防止密钥穷举攻击密钥穷举攻击奏效。奏效。但密钥又不能过长，以便于密钥的管理。但密钥又不能过长，以便

5、于密钥的管理。DES采用采用56比特密钥，太短了，比特密钥，太短了，IDEA采用采用128比特密钥，据估计，在今后比特密钥，据估计，在今后3040年内采用年内采用80 比比特密钥是足够安全的。特密钥是足够安全的。 由密钥确定置换的算法要足够复杂，充分实现由密钥确定置换的算法要足够复杂，充分实现明文与密钥的扩散和混淆，没有简单的关系可循，明文与密钥的扩散和混淆，没有简单的关系可循，能抗击各种已知的攻击，如差分攻击和线性攻击；能抗击各种已知的攻击，如差分攻击和线性攻击；有高的非线性阶数，实现复杂的密码变换；使对手有高的非线性阶数，实现复杂的密码变换；使对手破译时除了用穷举法外，无其它捷径可循。破译

6、时除了用穷举法外，无其它捷径可循。 加密和解密运算简单，易于软件和硬件高速实加密和解密运算简单，易于软件和硬件高速实现。如将分组现。如将分组n化分为子段，每段长为化分为子段，每段长为8、16或者或者32。在以软件实现时，应选用简单的运算，使作用于子在以软件实现时，应选用简单的运算，使作用于子段上的密码运算易于以标准处理器的基本运算，如段上的密码运算易于以标准处理器的基本运算，如加、乘、移位等实现，避免用以软件难于实现的逐加、乘、移位等实现，避免用以软件难于实现的逐比特置换。为了便于硬件实现，加密和解密过程之比特置换。为了便于硬件实现，加密和解密过程之间的差别应仅在于由秘密密钥所生成的密钥表不同

7、间的差别应仅在于由秘密密钥所生成的密钥表不同而已。这样，加密和解密就可用同一器件实现。设而已。这样，加密和解密就可用同一器件实现。设计的算法采用规则的模块结构，如多轮迭代等，以计的算法采用规则的模块结构，如多轮迭代等，以便于软件和便于软件和VLSI快速实现。此外，差错传播和数快速实现。此外，差错传播和数据扩展要尽可能地小。据扩展要尽可能地小。 数据扩展尽可能地小。一般无数据扩展，在采数据扩展尽可能地小。一般无数据扩展，在采用同态置换和随机化加密技术时可引入数据扩展。用同态置换和随机化加密技术时可引入数据扩展。 差错传播尽可能地小。差错传播尽可能地小。如果明文和密文的分组长都为如果明文和密文的分

8、组长都为n比特，则明文比特，则明文的每一个分组都有的每一个分组都有2n个可能的取值。为使加密运算个可能的取值。为使加密运算可逆（使解密运算可行），可逆（使解密运算可行），明文的每一个分组都应明文的每一个分组都应产生惟一的一个密文分组，这样的变换是可逆的，产生惟一的一个密文分组，这样的变换是可逆的，称明文分组到密文分组的可逆变换为代换。称明文分组到密文分组的可逆变换为代换。明文到密文，或密文到明文，可由代换表完成表示，明文到密文，或密文到明文，可由代换表完成表示，代换表是可逆的、一对一的映射表。代换表是可逆的、一对一的映射表。见教材见教材P36，表表3-1。不同可逆变换的个数有不同可逆变换的个数

9、有2n!个。个。3.1.1 代换代换图图3.2表示表示n=4的代换密码的一般结构，的代换密码的一般结构，4比特输入比特输入产生产生16个可能输入状态中的一个，由代换结构将这个可能输入状态中的一个，由代换结构将这一状态映射为一状态映射为16个可能输出状态中的一个，每一输个可能输出状态中的一个，每一输出状态由出状态由4个密文比特表示。加密映射和解密映射个密文比特表示。加密映射和解密映射可由代换表来定义，如表可由代换表来定义，如表3.1所示。这种定义法是所示。这种定义法是分组密码最常用的形式，能用于定义明文和密文之分组密码最常用的形式，能用于定义明文和密文之间的任何可逆映射。（见间的任何可逆映射。（

10、见33页表页表3.1）图图3.2 代换结构代换结构如果分组长度太小，系统则等价于古典的代换密码，如果分组长度太小，系统则等价于古典的代换密码，容易通过对明文的统计分析而被攻破。容易通过对明文的统计分析而被攻破。从实现的角度来看，分组长度很大的可逆代换结构从实现的角度来看，分组长度很大的可逆代换结构是不实际的。是不实际的。仍以表仍以表3.1为例，该表定义了为例，该表定义了n=4时从明文到密文的时从明文到密文的一个可逆映射，其中第一个可逆映射，其中第2列是每个明文分组对应的列是每个明文分组对应的密文分组的值，可用来定义这个可逆映射。因此从密文分组的值，可用来定义这个可逆映射。因此从本质上来说，第本

11、质上来说，第2列是从所有可能映射中决定某一列是从所有可能映射中决定某一特定映射的密钥。这个例子中，密钥需要特定映射的密钥。这个例子中，密钥需要64比特。比特。一般地，对一般地，对n比特的代换结构，密钥的大小是比特的代换结构，密钥的大小是n2n比特。如对比特。如对64比特的分组，密钥大小应是比特的分组，密钥大小应是64264=2701021比特，因此难以处理。比特，因此难以处理。实际中常将实际中常将n分成较小的段，例如可选分成较小的段，例如可选n=r n0，其中其中r和和n0都是正整数，将设计都是正整数，将设计n个变量的代换变为个变量的代换变为设计设计r个较小的子代换，而每个子代换只有个较小的子

12、代换，而每个子代换只有n0个输个输入变量。一般入变量。一般n0都不太大，都不太大， 称每个子代换为称每个子代换为代换盒代换盒，简称为，简称为S盒盒。例如例如DES中将输入为中将输入为48比特、输出为比特、输出为32比特的比特的代换用代换用8个个S盒来实现，每个盒来实现，每个S盒的输入端数仅为盒的输入端数仅为6比比特，输出端数仅为特，输出端数仅为4比特。比特。扩散和混淆是由扩散和混淆是由Shannon提出的设计密码系统提出的设计密码系统的两个基本方法的两个基本方法，目的是抗击敌手对密码系统的统，目的是抗击敌手对密码系统的统计分析。计分析。如果敌手知道明文的某些统计特性，如消息中如果敌手知道明文的

13、某些统计特性，如消息中不同字母出现的频率、可能出现的特定单词或短语，不同字母出现的频率、可能出现的特定单词或短语，而且这些统计特性以某种方式在密文中反映出来，而且这些统计特性以某种方式在密文中反映出来，那么敌手就有可能得出加密密钥或其一部分，或者那么敌手就有可能得出加密密钥或其一部分，或者得出包含加密密钥的一个可能的密钥集合。得出包含加密密钥的一个可能的密钥集合。3.1.2 扩散和混淆扩散和混淆所谓扩散，就是将明文的统计特性散布到密文所谓扩散，就是将明文的统计特性散布到密文中去，实现方式是使得密文中每一位由明文中多位中去，实现方式是使得密文中每一位由明文中多位产生产生 。例如对英文消息例如对英

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

15、扩散。1mod26knn iiychrord m混淆混淆是使密文和密钥之间的统计关系变得尽可是使密文和密钥之间的统计关系变得尽可能复杂，以使敌手无法得到密钥。能复杂，以使敌手无法得到密钥。因此即使敌手能得到密文的一些统计关系，由因此即使敌手能得到密文的一些统计关系，由于密钥和密文之间的统计关系复杂化，敌手也无法于密钥和密文之间的统计关系复杂化，敌手也无法得到密钥。使用复杂的代换算法可以得到预期的混得到密钥。使用复杂的代换算法可以得到预期的混淆效果，而简单的线性代换函数得到的混淆效果则淆效果，而简单的线性代换函数得到的混淆效果则不够理想。不够理想。扩散和混淆成功地实现了分组密码的本质属性，扩散和

16、混淆成功地实现了分组密码的本质属性，因而成为设计现代分组密码的基础。因而成为设计现代分组密码的基础。乘积密码乘积密码指顺序地执行两个或多个基本密码系指顺序地执行两个或多个基本密码系统，使得最后结果的密码强度高于每个基本密码系统，使得最后结果的密码强度高于每个基本密码系统产生的结果统产生的结果.Feistel还提出了实现代换和置换的方法。其思还提出了实现代换和置换的方法。其思想实际上是想实际上是Shannon提出的利用乘积密码实现混淆提出的利用乘积密码实现混淆和扩散思想的具体应用。和扩散思想的具体应用。3.1.3 Feistel密码结构密码结构图图3.3 Feistel网络示意图网络示意图1.

17、Feistel加密结构加密结构输入是分组长为输入是分组长为2w的明文和一个密钥的明文和一个密钥K。将每将每组明文分成左右两半组明文分成左右两半L0和和R0，在进行完在进行完n轮迭代后，轮迭代后，左右两半再合并到一起以产生密文分组。其第左右两半再合并到一起以产生密文分组。其第i轮轮迭代的输入为前一轮输出的函数：迭代的输入为前一轮输出的函数：其中其中Ki是第是第i轮用的子密钥，由加密密钥轮用的子密钥，由加密密钥K得到。一得到。一般地，各轮子密钥彼此不同而且与般地，各轮子密钥彼此不同而且与K也不同。也不同。111,iiiiiiLRRLF RKFeistel网络的实现与以下参数和特性有关：网络的实现与

18、以下参数和特性有关： 分组大小分组大小: 分组越大则安全性越高，但加密速度分组越大则安全性越高，但加密速度就越慢。分组密码设计中最为普遍使用的分组大小就越慢。分组密码设计中最为普遍使用的分组大小是是64比特。比特。 密钥大小：密钥越长则安全性越高，但加密速密钥大小：密钥越长则安全性越高，但加密速度就越慢。现在普遍认为度就越慢。现在普遍认为64比特或更短的密钥长度比特或更短的密钥长度是不安全的，通常使用是不安全的，通常使用128比特的密钥长度。比特的密钥长度。 轮数：单轮结构远不足以保证安全性，但多轮轮数：单轮结构远不足以保证安全性，但多轮结构可提供足够的安全性。典型地，轮数取为结构可提供足够的

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

20、被无疑义地解释清算法容易分析：如果算法能被无疑义地解释清楚，就可容易地分析算法抵抗攻击的能力，有助于楚，就可容易地分析算法抵抗攻击的能力，有助于设计高强度的算法。设计高强度的算法。2. Feistel解密结构解密结构Feistel解密过程本质上和加密过程是一样的，解密过程本质上和加密过程是一样的，算法使用密文作为输入，但使用子密钥算法使用密文作为输入，但使用子密钥Ki的次序与的次序与加密过程相反，即第加密过程相反，即第1轮使用轮使用Kn，第第2轮使用轮使用Kn-1，最后一轮使用最后一轮使用K1。这一特性保证了解这一特性保证了解密和加密可采用同一算法。密和加密可采用同一算法。图图3.4 Feis

21、tel加解密过程加解密过程在加密过程中：在加密过程中：在解密过程中在解密过程中161516151516,LERERELEF REK10161510016161516151516151615,LDRDLERERDLDF RDKREF REKLEF REKF REKLE所以解密过程第所以解密过程第1轮的输出为轮的输出为LE15RE15，等于加密等于加密过程第过程第16轮输入左右两半交换后的结果。容易证明轮输入左右两半交换后的结果。容易证明这种对应关系在这种对应关系在16轮中每轮都成立。一般地，加密轮中每轮都成立。一般地，加密过程的第过程的第i轮有轮有因此因此111,iiiiiiLERERELEF

22、REK111,iiiiiiiiiRELELEREF REKREF LEK数据加密标准（数据加密标准（data encryption standard, DES）是迄今为止世界上最为广泛使用和流行的一种分组是迄今为止世界上最为广泛使用和流行的一种分组密码算法，它的分组长度为密码算法，它的分组长度为64比特，密钥长度为比特，密钥长度为56比特，它是由美国比特，它是由美国IBM公司研制的，是早期的称作公司研制的，是早期的称作Lucifer密码的一种发展和修改。密码的一种发展和修改。DES在在1975年年3月月17日首次被公布在联邦记录中，经过大量的公开讨日首次被公布在联邦记录中，经过大量的公开讨论后

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

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

25、ion standard) 的新加密标准。尽管如此，的新加密标准。尽管如此，DES对于推对于推动密码理论的发展和应用毕竟起了重大作用，对于动密码理论的发展和应用毕竟起了重大作用，对于掌握分组密码的基本理论、设计思想和实际应用仍掌握分组密码的基本理论、设计思想和实际应用仍然有着重要的参考价值，下面首先来描述这一算法。然有着重要的参考价值，下面首先来描述这一算法。图图3.5 DES加密算法框图加密算法框图1. 初始置换初始置换1. 初始置换初始置换M1 M2 M3 M4 M5 M6 M7 M8M9 M10 M11 M12 M13 M14 M15 M16 M17 M18 M19 M20 M21 M2

26、2 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 M

27、56 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各位的初始顺序将被恢复。各位的初始顺序将被恢复。图图3.6 DES加密算法的轮结构加密算法的轮结构每轮变换可由以下公式表示：每轮变换可由以下公式表示：111(,)iiiiiiLRRLF RK图图3.7 函数函数F

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

29、行列交叉位置的数为数为9，其，其4位二进制表示为位二进制表示为1001，所以，所以S1的输出为的输出为1001。S盒的每一行定义了一个可逆代换。盒的每一行定义了一个可逆代换。P-盒置换 P-盒置换为：16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 253. 密钥的产生密钥的产生子密钥产生子密钥产生 PC-1(置换选择置换选择1)：（1）舍掉种子密钥）舍掉种子密钥K中的中的8个校验位；个校验位；（2）按照）按照PC-1表作置换，即：表作置换，即： C0=k57k49k41k44

30、k36 前前28位位 D0=k63k55k47k12k4 后后28位位 循环移位循环移位LS：C0 C1 ，D0 D1 PC-2(置换选择置换选择2)（1）删除移位后）删除移位后C1中的第中的第9，18，22，25位和位和D1中中的第的第7，10，15，26位（即删除移位后位（即删除移位后C1 | D1重新重新编号后的第编号后的第9，18，22，25 ，35，38，43，54位）位）（2）按照）按照PC-2表作置换，即得子密钥表作置换，即得子密钥k1置换运算说明置换运算说明置换结果：始终以输入位串的重新编号作为置换结果：始终以输入位串的重新编号作为置换表的输出而得到的结果。置换表的输出而得到的

31、结果。4. 解密解密和和Feistel密码一样，密码一样，DES的解密和加密使用同的解密和加密使用同一算法，但子密钥使用的顺序相反。一算法，但子密钥使用的顺序相反。DES加密计算举例加密计算举例DES举例举例DES举例（续）举例（续）为了提高为了提高DES的安全性，并利用实现的安全性，并利用实现DES的现有软的现有软硬件，可将硬件，可将DES算法在多密钥下多重使用。算法在多密钥下多重使用。二重二重DES是多重使用是多重使用DES时最简单的形式，如图时最简单的形式，如图3.8所示。其中明文为所示。其中明文为P，两个加密密钥为两个加密密钥为K1和和K2，密密文为：文为：解密时，以相反顺序使用两个密

32、钥：解密时，以相反顺序使用两个密钥：3.2.2 二重二重DES21 KKCEEP12 KKPDDC图图3.8 二重二重DES因此，二重因此，二重DES所用密钥长度为所用密钥长度为112比特，强度比特，强度极大地增加。极大地增加。然而，假设对任意两个密钥然而，假设对任意两个密钥K1和和K2，能够找出能够找出另一密钥另一密钥K3，使得使得213 KKKEEPEP那么，二重那么，二重DES以及多重以及多重DES都没有意义，因都没有意义，因为它们与为它们与56比特密钥的单重比特密钥的单重DES等价，好在这种假等价，好在这种假设对设对DES并不成立。并不成立。将将DES加密过程加密过程64比特分组到比特

33、分组到64比特分组的映比特分组的映射看作一个置换，如果考虑射看作一个置换，如果考虑264个所有可能的输入个所有可能的输入分组，则密钥给定后，分组，则密钥给定后，DES的加密将把每个输入分的加密将把每个输入分组映射到一个惟一的输出分组。否则，如果有两个组映射到一个惟一的输出分组。否则，如果有两个输入分组被映射到同一分组，则解密过程就无法实输入分组被映射到同一分组，则解密过程就无法实施。对施。对264个输入分组，总映射个数为个输入分组，总映射个数为 2064102!10另一方面，对每个不同的密钥，另一方面，对每个不同的密钥，DES都定义了一个都定义了一个映射，总映射数为映射，总映射数为256N/2

34、，则令则令如果如果TN/2，则令则令从而可得关于密钥比特的一个线性方程。对不同的从而可得关于密钥比特的一个线性方程。对不同的明文密文对重复以上过程，可得关于密钥的一组线明文密文对重复以上过程，可得关于密钥的一组线性方程，从而确定出密钥比特。性方程，从而确定出密钥比特。12102 ,112cpK k kkp12102 ,112cpK k kkp研究表明，当研究表明，当 充分小时，攻击成功的概率是充分小时，攻击成功的概率是这一概率只依赖于这一概率只依赖于 ，并随着并随着N或或 的的增加而增加。增加而增加。12p12p12N p2212212xN pedx如何对差分密码分析和线性密码分析进行改进，如

35、何对差分密码分析和线性密码分析进行改进，降低它们的复杂度仍是现在理论研究的热点，目前降低它们的复杂度仍是现在理论研究的热点，目前已推出了很多改进方法，例如已推出了很多改进方法，例如,高阶差分密码分析、高阶差分密码分析、截段差分密码分析（截段差分密码分析（truncated differential cryptanalysis）、）、不可能差分密码分析、多重线性不可能差分密码分析、多重线性密码分析、非线性密码分析、划分密码分析和差分密码分析、非线性密码分析、划分密码分析和差分-线性密码分析，再如针对密钥编排算法的相关密线性密码分析，再如针对密钥编排算法的相关密钥攻击、基于钥攻击、基于Lagran

36、ge插值公式的插值攻击及基于插值公式的插值攻击及基于密码器件的能量分析（密码器件的能量分析（power analysis），），另外还另外还有错误攻击、时间攻击、有错误攻击、时间攻击、Square攻击和攻击和Davies攻击攻击等。等。 参考文献参考文献 “Differential Cryptanalysis of the Data Encryption Standard” (差分密码分析差分密码分析) “Linear cryptanalysis Method for DES Cipher” (线线性密码分析性密码分析)分组密码在加密时分组密码在加密时,明文分组的长度是固定的，而明文分组的长度

37、是固定的，而实际应用中待加密消息的数据量是不定的，数据格实际应用中待加密消息的数据量是不定的，数据格式可能是多种多样的。为了能在各种应用场合使用式可能是多种多样的。为了能在各种应用场合使用DES，美国在美国在FIPS PUS 74和和81中定义了中定义了DES的的4种种运行模式，如表运行模式，如表3-5所示。这些模式也可用于其他所示。这些模式也可用于其他分组密码，下面以分组密码，下面以DES为例来介绍这为例来介绍这4种模式。种模式。3.4 分组密码的运行模式分组密码的运行模式ECB(electronic codebook)模式是最简单的运行模式，模式是最简单的运行模式，它一次对一个它一次对一个

38、64比特长的明文分组加密，而且每次比特长的明文分组加密，而且每次的加密密钥都相同的加密密钥都相同，如图，如图3.10所示。当密钥取定时，所示。当密钥取定时，对明文的每一个分组，都有一个惟一的密文与之对对明文的每一个分组，都有一个惟一的密文与之对应。因此形象地说，可以认为有一个非常大的电码应。因此形象地说，可以认为有一个非常大的电码本，对任意一个可能的明文分组，电码本中都有一本，对任意一个可能的明文分组，电码本中都有一项对应于它的密文。项对应于它的密文。3.4.1 电码本（电码本（ECB）模式模式图图3.10 ECB模式示意图模式示意图如果消息长于如果消息长于64比特，则将其分为长为比特，则将其

39、分为长为64比特比特的分组，最后一个分组如果不够的分组，最后一个分组如果不够64比特，则需要填比特，则需要填充。解密过程也是一次对一个分组解密，而且每次充。解密过程也是一次对一个分组解密，而且每次解密都使用同一密钥。图解密都使用同一密钥。图3.10中，明文是由分组长中，明文是由分组长为为64比特的分组序列比特的分组序列P1，P2，PN构成，相应的构成，相应的密文分组序列是密文分组序列是C1，C2，CN。ECB在用于在用于短数据短数据（如加密密钥）时非常理想，（如加密密钥）时非常理想，因此如果需要安全地传递因此如果需要安全地传递DES密钥，密钥，ECB是最合适是最合适的模式。的模式。ECB的的最

40、大特性最大特性是同一明文分组在消息中重复是同一明文分组在消息中重复出现的话，产生的密文分组也相同。出现的话，产生的密文分组也相同。ECB用于用于长消息时可能不够安全长消息时可能不够安全，如果消息有，如果消息有固定结构，密码分析者有可能找出这种关系。例如，固定结构，密码分析者有可能找出这种关系。例如，如果已知消息总是以某个预定义字段开始，那么分如果已知消息总是以某个预定义字段开始，那么分析者就可能得到很多明文析者就可能得到很多明文-密文对。如果消息有重密文对。如果消息有重复的元素而重复的周期是复的元素而重复的周期是64的倍数，那么密码分析的倍数，那么密码分析者就能够识别这些元素。以上这些特性都有

41、助于密者就能够识别这些元素。以上这些特性都有助于密码分析者，有可能为其提供对分组的代换或重排的码分析者，有可能为其提供对分组的代换或重排的机会。机会。ECB优缺点小结优缺点小结 优点：优点：加密短数据，如对密钥的加密，效率较高。加密短数据，如对密钥的加密，效率较高。 缺点：缺点：（1 1）难抗已知明文攻击，特别是有固定格式的长消）难抗已知明文攻击，特别是有固定格式的长消息不适合；息不适合；（2 2）信息有周期规律出现，易破译。例如每隔一页）信息有周期规律出现，易破译。例如每隔一页为为6464位（倍数），每隔一页的页眉都相同：位（倍数），每隔一页的页眉都相同：“科科大毕业设计大毕业设计”，易破译

42、出此局部明文，从而找到，易破译出此局部明文，从而找到密钥密钥k k；（3 3）明文分组在消息中重复，则也有重复的密文分）明文分组在消息中重复，则也有重复的密文分组。组。为了解决为了解决ECB的安全缺陷，可以让重复的明文分组的安全缺陷，可以让重复的明文分组产生不同的密文分组，产生不同的密文分组，CBC（cipher block chaining）模式就可满足这一要求。模式就可满足这一要求。加密算法的输入是当前明文分组和前一次密文加密算法的输入是当前明文分组和前一次密文分组的异或，分组的异或，因此加密算法的输入不会显示出与这次的明文因此加密算法的输入不会显示出与这次的明文分组之间的固定关系，所以重

43、复的明文分组不会在分组之间的固定关系，所以重复的明文分组不会在密文中暴露出这种重复关系。密文中暴露出这种重复关系。3.4.2 密码分组链接（密码分组链接（CBC）模式模式图图3.11 CBC模式示意图模式示意图解密时，每一个密文分组被解密后，再与前一解密时，每一个密文分组被解密后，再与前一个密文分组异或，即个密文分组异或，即（设设 ）因而产生出明文分组。因而产生出明文分组。 11111KnnKKnnnnnnnD CCDE CPCCPCP1nKnnCECP在产生第在产生第1个密文分组时，需要有一个初始向个密文分组时，需要有一个初始向量量IV与第与第1个明文分组异或。解密时，个明文分组异或。解密时

44、，IV和解密算和解密算法对第法对第1个密文分组的输出进行异或以恢复第个密文分组的输出进行异或以恢复第1个明个明文分组。文分组。IV对于收发双方都应是已知的，为使安全性最对于收发双方都应是已知的，为使安全性最高，高，IV应像密钥一样被保护应像密钥一样被保护，可使用，可使用ECB加密模加密模式来发送式来发送IV。保护保护IV的原因如下：的原因如下： 如果敌手能欺如果敌手能欺骗接收方使用不同的骗接收方使用不同的IV值，敌手就能够在明文的第值，敌手就能够在明文的第1个分组中插入自己选择的比特值，这是因为：个分组中插入自己选择的比特值，这是因为：1111KKCEIVPPIVDC用用X(i)表示表示64比

45、特分组比特分组X的第的第i个比特，那个比特，那么么 ，由异或的性质得由异或的性质得其中撇号表示比特补。上式意味着其中撇号表示比特补。上式意味着如果敌手篡如果敌手篡改改IV中的某些比特，则接收方收到的中的某些比特，则接收方收到的P1中相应的比中相应的比特也发生了变化，从而使接收方不能得到真实的特也发生了变化，从而使接收方不能得到真实的P1分组。分组。 11KP iIV iDCi 11KP iIV iDCiCBC优缺点小结优缺点小结 优点：优点： 克服了克服了ECB的第（的第（3）个缺点，即）个缺点，即CBC中重复的明文中重复的明文分组不会在密文中暴露重复关系。分组不会在密文中暴露重复关系。 缺点

46、：缺点：（1）如何保护）如何保护IV不被篡改；不被篡改； 学生？学生？（2）存在）存在“比特错误传播比特错误传播”特性，例如特性，例如Ci中有中有1位错，位错，则会影响则会影响Pi+1（？）（？），错误传播有限。错误传播有限。110()(),1,=iKiiiKiiCEPCPDCCiCIV其中规定+1+1()iKiiPDCC显然，如上所述，如上所述，DES是分组长为是分组长为64比特的分组密码，比特的分组密码，但利用但利用CFB（cipher feedback）模式或模式或OFB模式可模式可将将DES转换为流密码转换为流密码。流密码不需要对消息填充，。流密码不需要对消息填充，而且运行是实时的。因

47、此如果传送字母流，可使用而且运行是实时的。因此如果传送字母流，可使用流密码对每个字母直接加密并传送。流密码对每个字母直接加密并传送。流密码具有密文和明文一样长这一性质，因此，流密码具有密文和明文一样长这一性质，因此，如果需要发送的每个字符长为如果需要发送的每个字符长为8比特，就应使用比特，就应使用8比比特密钥来加密每个字符。特密钥来加密每个字符。3.4.3 密码反馈（密码反馈（CFB）模式模式图图3.12 3.12 CFBCFB模式示意图模式示意图( (密文反馈密文反馈) )解密时解密时，将收到的密文单元与加密函数的输出，将收到的密文单元与加密函数的输出进行异或。注意进行异或。注意这时仍然使用

48、加密算法而不是解密这时仍然使用加密算法而不是解密算法算法，原因如下：，原因如下： 设设Sj(X)是是X的的j个最高有效位，那么个最高有效位，那么因此因此可证明以后各步也有类似的这种关系。可证明以后各步也有类似的这种关系。CFB模式除能获得保密性外，还能用于认证。模式除能获得保密性外，还能用于认证。11jCPSE IV11jPCSE IVCFB优缺点小结优缺点小结 优点：优点： 形成流密码方式传送，可对传送的位数灵活控制，或形成流密码方式传送，可对传送的位数灵活控制，或1位，或位，或8位（位（1个字母）等；个字母）等； 缺点：缺点： 有有“比特错误传播比特错误传播”特性，同特性，同CBC。C C

49、i i中有中有1 1位出错，则会影响位出错，则会影响P Pi i和和P Pi+1i+1，对于传播来讲，就只有，对于传播来讲，就只有P Pi+1i+1，故，故错误传播有限。错误传播有限。j64jj1j64jj10(IV)|()(IV)|()1,=() :() :iiKiiiKiCPSESLCPCSESLCiCIVSx AAxx AAx其 中规 定的 高位 ； L的 低位 。OFB（output feedback）模式的结构类似于模式的结构类似于CFB，见图见图3.13。不同之处如下：。不同之处如下：OFB模式是将加密算法模式是将加密算法的输出反馈到移位寄存器，而的输出反馈到移位寄存器，而CFB模

50、式中是将密文模式中是将密文单元反馈到移位寄存器。单元反馈到移位寄存器。3.4.4 输出反馈输出反馈(OFB)模式模式图图3.13 3.13 OFBOFB模式示意图（输出反馈）模式示意图（输出反馈）OFB模式的优点是传输过程中的比特错误不会模式的优点是传输过程中的比特错误不会被传播被传播（因为（因为OFB中各个密文分组的形成是中各个密文分组的形成是“独立独立”的，不依赖于前面的密文分组）。的，不依赖于前面的密文分组）。OFB的缺点是它比的缺点是它比CFB模式更易受到对消息流模式更易受到对消息流的篡改攻击的篡改攻击，比如在密文中取，比如在密文中取1比特的补，那么在比特的补，那么在恢复的明文中相应位

51、置的比特也为原比特的补（异恢复的明文中相应位置的比特也为原比特的补（异或运算的特性）。或运算的特性）。因此使得敌手有可能通过对消息校验部分的篡因此使得敌手有可能通过对消息校验部分的篡改和对数据部分的篡改，而改和对数据部分的篡改，而以纠错码不能检测的方以纠错码不能检测的方式式篡改密文，即使完整性检查失效。篡改密文，即使完整性检查失效。OFB模式缺点：完整性检查失效模式缺点：完整性检查失效:1011011.:1111011.( 2)( ),|( ), | ()00011011. :01011011.( )iiiiiiiiiiiiiiiiPCChH P C hhH PChPCPPH P 正常 被攻击

52、加密 第 位被篡改，取补 前提：敌手已知解密 ： ( )iiihH Ph 来学嘉（来学嘉（X. J. Lai）和和J. L. Massey提出的第提出的第1版版IDEA（international data encryption algorithm，国际数据加密算法）于国际数据加密算法）于1990年公布，当时称为年公布，当时称为PES（proposed encryption standard，建议加密标准）。建议加密标准）。1991年，在年，在Biham和和Shamir提出差分密码分析之后，提出差分密码分析之后，设计者推出了改进算法设计者推出了改进算法IPES，即改进型建议加密即改进型建议加密

53、标准。标准。1992年，设计者又将年，设计者又将IPES改名为改名为IDEA。这这是近年来提出的各种分组密码中一个很成功的方案，是近年来提出的各种分组密码中一个很成功的方案，已在已在PGP中采用。中采用。3.5 IDEA算法中明文和密文分组长度都是算法中明文和密文分组长度都是64比特，密钥比特，密钥长长128比特。其设计原理可从强度和实现两方面考比特。其设计原理可从强度和实现两方面考虑。虑。1. 密码强度密码强度算法的强度主要是通过有效的混淆和扩散特性而得算法的强度主要是通过有效的混淆和扩散特性而得以保证。以保证。3.5.1 设计原理设计原理IDEA三种运算三种运算(1) (X+Y) mod

54、2(2) (X+Y) mod 2n(3) (X.Y) mod (2n+1)对于对于“整数乘法整数乘法”运算运算 ，若，若X或或Y为为0，则视，则视X或或Y为为2n；若；若X.Y为为2n，则视乘积结果为，则视乘积结果为0.算法中扩散是由称为乘加算法中扩散是由称为乘加（multiplication/addition, MA）结构结构的基本单元实的基本单元实现的。该结构的输入是两个现的。该结构的输入是两个16比特的子段和两个比特的子段和两个16比特的子密钥，输出也为两个比特的子密钥，输出也为两个16比特的子段。这一比特的子段。这一结构在算法中重复使用了结构在算法中重复使用了8次，获得了非常有效的次，

55、获得了非常有效的扩散效果扩散效果。每一轮两个子段交换，起混淆作用，以抗差分密码每一轮两个子段交换，起混淆作用，以抗差分密码分析。分析。图图3.14 MA结构结构2. 实现实现IDEA可方便地通过软件和硬件实现。可方便地通过软件和硬件实现。 软件软件实现采用软件软件实现采用16比特子段处理，可通过使比特子段处理，可通过使用容易编程的加法、移位等运算实现算法的用容易编程的加法、移位等运算实现算法的3种运种运算。算。 硬件由于加、解密相似，差别仅为使用密钥的硬件由于加、解密相似，差别仅为使用密钥的方式，因此可用同一器件实现。再者，算法中规则方式，因此可用同一器件实现。再者，算法中规则的模块结构，可方

56、便的模块结构，可方便VLSI的实现。的实现。图图3.15 IDEA的加密框图的加密框图图图3.16 IDEA第第1轮的轮结构轮的轮结构1. 轮结轮结构构图图3.17 IDEA的输出变换的输出变换2. 子密钥的产生子密钥的产生加密过程中加密过程中52个个16比特的子密钥是由比特的子密钥是由128比特比特的加密密钥按如下方式产生的：的加密密钥按如下方式产生的： 前前8个子密钥个子密钥Z1，Z2，Z8直接从加密密钥中取，即直接从加密密钥中取，即Z1取前取前16比特比特（最高有效位），（最高有效位），Z2取下面的取下面的16比特，依次类推。比特，依次类推。然后加密密钥循环左移然后加密密钥循环左移25位

57、，再取下面位，再取下面8个子密钥个子密钥Z9，Z10，Z16，取法与取法与Z1，Z2，Z8的取法的取法相同。这一过程重复下去，直到相同。这一过程重复下去，直到52子密钥都被产生子密钥都被产生为止。为止。（画图描述）（画图描述）3. 解密过程解密过程解密过程和加密过程基本相同，但子密钥的选解密过程和加密过程基本相同，但子密钥的选取不同。解密子密钥取不同。解密子密钥U1，U2，U52是由加密子是由加密子密钥按如下方式得到（将加密过程最后一步的输出密钥按如下方式得到（将加密过程最后一步的输出变换当作第变换当作第9轮）：轮）： 第第i(i=1,9)轮解密的前轮解密的前4个子密钥由加密过程第个子密钥由加

58、密过程第(10-i)轮的前轮的前4个子密钥得出：个子密钥得出：其中第其中第1和第和第4个解密子密钥取为相应的第个解密子密钥取为相应的第1和和第第4个加密子密钥的模个加密子密钥的模216+1乘法逆元，第乘法逆元，第2和第和第3个个子密钥的取法为：子密钥的取法为： 当轮数当轮数i=2,8时，取为相应的时，取为相应的第第3个和第个和第2个加密子密钥的模个加密子密钥的模216加法逆元。加法逆元。i=1和和9时，取为相应的第时，取为相应的第2个和第个和第3个加密子密钥的模个加密子密钥的模216加法逆元。加法逆元。 第第i(i=1,8)轮解密的后两个子密钥等于加密过轮解密的后两个子密钥等于加密过程第程第(

59、9-i)轮的后两个子密钥。轮的后两个子密钥。下面验证解密过程的确可以得到正确的结果。下面验证解密过程的确可以得到正确的结果。图图3.18中左边为加密过程，由上至下，右边为解密中左边为加密过程，由上至下，右边为解密过程，由下至上。将每一轮进一步分为两步，第过程，由下至上。将每一轮进一步分为两步，第1步是步是变换变换，其余部分作为第，其余部分作为第2步，称为步，称为子加密子加密。图图3.18 IDEA加密和解密框图加密和解密框图（加密）子加密：（加密）子加密：W81=I81 MAR(I81 I83，I82 I84)W82=I83 MAR(I81 I83，I82 I84)W83=I82 MAL(I8

60、1 I83，I82 I84)W84=I84 MAL(I81 I83，I82 I84)（加密）变换：（加密）变换：Y1=W81 Z49 Y2=W83 + Z50Y3=W82 + Z51 Y4=W84 Z52解密过程中第解密过程中第1轮的第轮的第1步产生以下关系：步产生以下关系： J11=Y1 U1 J12=Y2 + U2J13=Y3 + U3 J14=Y4 U4（解密）变换：（解密）变换：J11=Y1 Z-149= W81 Z49 Z-149= W81J12=Y2 + -Z50=W83 + Z50 + -Z50=W83J13=Y3 + -Z51=W82 + Z51 + -Z51=W82J14=Y