第三章分组密码

1、 第三章第三章 分组密码分组密码3.1 3.1 分组密码概述分组密码概述3.2 DES3.2 DES3.3 3.3 分组密码运行模式分组密码运行模式3.4 AES 3.4 AES 一、分组密码概述一、分组密码概述分组密码概述分组密码概述n分组密码是许多系统安全的一个重要组成部分。分组密码是许多系统安全的一个重要组成部分。可用于构造可用于构造n伪随机数生成器伪随机数生成器n流密码流密码n消息认证码消息认证码(MAC)(MAC)和杂凑函数和杂凑函数n消息认证技术、数据完整性机制、实体认证协议以消息认证技术、数据完整性机制、实体认证协议以及单钥数字签字体制的核心组成部分及单钥数字签字体制的核心组成部

2、分。 应用中对于分组密码的要求应用中对于分组密码的要求n安全性安全性n运行速度运行速度n存储量存储量( (程序的长度、数据分组长度、高速缓程序的长度、数据分组长度、高速缓存大小存大小) )n实现平台实现平台( (硬、软件、芯片硬、软件、芯片) )n运行模式运行模式分组密码概述分组密码概述 明文序列明文序列 x1, x2, xi, 加密函数加密函数E: VnKVm 这种密码实质上是字长为这种密码实质上是字长为n的数字序列的代换密码的数字序列的代换密码。 解密算法加密算法密钥k=(k0, k1, kt-1 )密钥k=(k0, k1, kt-1 )明文明文x=(x0, x1, xn-1)明文明文x=

3、(x0, x1, xn-1)密文密文x=(y0, y1, ym-1)分组密码概述分组密码概述n通常取通常取n=m。n若若nm ，则为有数据压缩的分组密码。，则为有数据压缩的分组密码。分组密码设计问题分组密码设计问题 分组密码的设计问题在于找到一种算法，分组密码的设计问题在于找到一种算法，能在密钥控制下从一个足够大且足够好的置能在密钥控制下从一个足够大且足够好的置换子集中，简单而迅速地选出一个置换，用换子集中，简单而迅速地选出一个置换，用来对当前输入的明文的数字组进行加密变换。来对当前输入的明文的数字组进行加密变换。分组密码设计准则n混淆混淆：人们所设计的密码应使用使得：人们所设计的密码应使用使

4、得密钥和明文密钥和明文以及密文以及密文之间的依赖关系相当复杂以至于这种依之间的依赖关系相当复杂以至于这种依赖性对密码分析者来说是无法利用的。赖性对密码分析者来说是无法利用的。n扩散扩散：人们所设计的密码应使得：人们所设计的密码应使得密钥的每一位数密钥的每一位数字影响密文的许多位数字字影响密文的许多位数字以防止对密钥进行逐段以防止对密钥进行逐段破译，而且破译，而且明文的每一位数字也应影响密文的许明文的每一位数字也应影响密文的许多位数字多位数字以便隐藏明文数字统计特性。以便隐藏明文数字统计特性。分组密码算法应满足的要求分组密码算法应满足的要求n分组长度分组长度n要足够大：要足够大： 防止明文穷举攻

5、击法奏效。防止明文穷举攻击法奏效。n密钥量要足够大：密钥量要足够大： 尽可能消除弱密钥并使所有密钥同等地好，以防止密尽可能消除弱密钥并使所有密钥同等地好，以防止密钥穷举攻击奏效钥穷举攻击奏效。n由密钥确定置换的算法要足够复杂：由密钥确定置换的算法要足够复杂： 充分实现明文与密钥的扩散和混淆，没有简单的关系充分实现明文与密钥的扩散和混淆，没有简单的关系可循可循，要能抗击各种已知的攻击。要能抗击各种已知的攻击。 分组密码算法应满足的要求分组密码算法应满足的要求n加密和解密运算简单加密和解密运算简单： 易于软件和硬件高速实现易于软件和硬件高速实现。n数据扩展：数据扩展： 一般无数据扩展，在采用同态置

6、换和随机化加密技一般无数据扩展，在采用同态置换和随机化加密技术时可引入数据扩展术时可引入数据扩展。n差错传播尽可能地小差错传播尽可能地小。 分组密码的实现原则n软件实现的原则软件实现的原则：使用子块和简单的运算。如：使用子块和简单的运算。如将分组将分组n化分为子段，每段长为化分为子段，每段长为8、16或或32。在。在以软件实现时，应选用简单的运算，使作用于以软件实现时，应选用简单的运算，使作用于子段上的密码运算易于以标准处理器的基本运子段上的密码运算易于以标准处理器的基本运算，如算，如加、乘、移位加、乘、移位等实现，避免用以软件难等实现，避免用以软件难于实现的逐比特置换。于实现的逐比特置换。n

7、硬件实现的原则硬件实现的原则：加密解密可用同样的器件来：加密解密可用同样的器件来实现。实现。代换网络代换网络n代换代换是输入集是输入集A到输出到输出A上的双射变换上的双射变换： fk：AA k是控制输入变量，在密码学中则为密钥是控制输入变量，在密码学中则为密钥。n实现代换实现代换fk的网络称作的网络称作代换网络代换网络。双射条件保证。双射条件保证在给定在给定k下可从密文惟一地恢复出原明文下可从密文惟一地恢复出原明文。代换网络代换网络n代换代换fk的集合：的集合： S=fk k KnK是密钥空间。如果网络可以实现所有可是密钥空间。如果网络可以实现所有可能的能的2n!个代换，则称其为全代换网络个代

8、换，则称其为全代换网络。代换结构代换网络代换网络n密码设计中需要先定义代换集密码设计中需要先定义代换集S，而后还需定，而后还需定义解密变换集，即逆代换网络义解密变换集，即逆代换网络S S-1-1，它以密文，它以密文y作为输入矢量，其输出为恢复的明文矢量作为输入矢量，其输出为恢复的明文矢量x x。n要实现全代换网络并不容易。因此实用中常要实现全代换网络并不容易。因此实用中常常利用一些简单的基本代换，通过组合实现常利用一些简单的基本代换，通过组合实现较复杂的、元素个数较多的代换集。实用密较复杂的、元素个数较多的代换集。实用密码体制的集合码体制的集合S S中的元素个数都远小于中的元素个数都远小于2

9、2n n! !。 代换盒代换盒(S盒盒) 在密码设计中，可选在密码设计中，可选 n=r n0，其中，其中r和和n0都为正整都为正整数，将设计数，将设计n个变量的代换网络化为设计个变量的代换网络化为设计r个较小的个较小的子代换网络，而每个子代换网络只有子代换网络，而每个子代换网络只有n0个输入变量，个输入变量，称每个子代换网络为代换盒称每个子代换网络为代换盒(Substitution Box) S盒 x5 x4 x3 x2 x1 x0 y3 y2 y1 y0DES的S盒DES的的S1-盒的输入和输出关系盒的输入和输出关系nx5 x0 x5 x4 x3 x2 x1 x0 1 0 1 0 1 1 0

10、 0 列号列号 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 行号行号 0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 3 15 12 8 2 4 9 1 7 5 11 2 14 10 0 6 13 (y3 , y2, y1 , y0)=(0,0,1,0) S S盒的设计准则盒的设计准则 迄今为止，有关方面未曾完全公开有关迄今为止，有关方面未曾完全公开有关DES的的S盒的设计

11、准盒的设计准则。则。Branstead等曾披露过下述准则：等曾披露过下述准则：nP1 S盒的输出都不是其输入的线性或仿射函数。盒的输出都不是其输入的线性或仿射函数。nP2 改变改变S盒的一个输入比特，其输出至少有两比特产生变盒的一个输入比特，其输出至少有两比特产生变化，即近一半产生变化。化，即近一半产生变化。nP3 当当S盒的任一输入位保持不变，其它盒的任一输入位保持不变，其它5位输入变化时位输入变化时(共共有有25 =32种情况种情况)，输出数字中的，输出数字中的0和和1的总数近于相等。的总数近于相等。 这三点使这三点使DES的的S盒能够实现较好的混淆。盒能够实现较好的混淆。Feistel密

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

13、行完n轮迭代后，左右两半再合并到一起以轮迭代后，左右两半再合并到一起以产生密文分组。第产生密文分组。第i i轮迭代的输入为前一轮输出的函数：轮迭代的输入为前一轮输出的函数：其中其中Ki是第是第i轮用的子密钥，由加密密钥轮用的子密钥，由加密密钥K得到。一般地，各轮得到。一般地，各轮子密钥彼此不同而且与子密钥彼此不同而且与K也不同。也不同。111,iiiiiiLRRLF RKFeistel密码结构密码结构Feistel密码结构密码结构Feistel网络的实现与以下参数和特性有关：网络的实现与以下参数和特性有关： 分组大小分组大小: : 分组越大则安全性越高，但加密速度就越慢。分组越大则安全性越高，

14、但加密速度就越慢。 密钥大小密钥大小：密钥越长则安全性越高，但加密速度就越慢。：密钥越长则安全性越高，但加密速度就越慢。 轮数轮数：单轮结构远不足以保证安全性，但多轮结构可提供：单轮结构远不足以保证安全性，但多轮结构可提供足够的安全性。典型地，轮数取为足够的安全性。典型地，轮数取为1616。 子密钥产生算法子密钥产生算法：该算法的复杂性越大，则密码分析的困：该算法的复杂性越大，则密码分析的困难性就越大。难性就越大。 轮函数轮函数：轮函数的复杂性越大，密码分析的困难性也越大。：轮函数的复杂性越大，密码分析的困难性也越大。在设计在设计Feistel网络时，还有以下两个方面需要考虑：网络时，还有以下

15、两个方面需要考虑： 快速的软件实现快速的软件实现：在很多情况中，算法是被镶嵌在应用：在很多情况中，算法是被镶嵌在应用程序中，因而无法用硬件实现。此时算法的执行速度是考虑程序中，因而无法用硬件实现。此时算法的执行速度是考虑的关键。的关键。 算法容易分析算法容易分析：如果算法能被无疑义地解释清楚，就可：如果算法能被无疑义地解释清楚，就可容易地分析算法抵抗攻击的能力，有助于设计高强度的算法。容易地分析算法抵抗攻击的能力，有助于设计高强度的算法。Feistel密码结构密码结构 Feistel解密过程本质上和加密过程是一样的，算法解密过程本质上和加密过程是一样的，算法使用密文作为输入，但使用子密钥使用密

16、文作为输入，但使用子密钥Ki的次序与加密的次序与加密过程相反，即第过程相反，即第1 1轮使用轮使用Kn，第，第2 2轮使用轮使用Kn-1，最后一轮使用最后一轮使用K1。这一特性保证了解密和加密可采。这一特性保证了解密和加密可采用同一算法。用同一算法。Feistel解密结构解密结构 FeistelFeistel加解密过程加解密过程在加密过程中：在解密过程中161516151516,LERERELEF REK10161510016161516151516151615,LDRDLERERDLDF RDKREF REKLEF REKF REKLEFeistel密码结构密码结构所以解密过程第所以解密过程

17、第1 1轮的输出为轮的输出为LE15RE15，等于加密过程第，等于加密过程第16轮输入左右两半交换后的结果。容易证明这种对应关系在轮输入左右两半交换后的结果。容易证明这种对应关系在16轮中每轮都成立。一般地，加密过程的第轮中每轮都成立。一般地，加密过程的第i轮有轮有因此因此111,iiiiiiLERERELEF REK111,iiiiiiiiiRELELEREF REKREF LE KFeistel密码结构密码结构3.2 美国数据加密标准美国数据加密标准DES（Data Encryption Standard）美国制定数据加密标准简况美国制定数据加密标准简况n目的目的 通信与计算机相结合是人类

18、步入信息社会的一通信与计算机相结合是人类步入信息社会的一个阶梯，它始于六十年代末，完成于个阶梯，它始于六十年代末，完成于9090年代初。年代初。计算机通信网的形成与发展，要求信息作业标准计算机通信网的形成与发展，要求信息作业标准化，安全保密亦不例外。只有标准化，才能真正化，安全保密亦不例外。只有标准化，才能真正实现网的安全，才能推广使用加密手段，以便于实现网的安全，才能推广使用加密手段，以便于训练、生产和降低成本。训练、生产和降低成本。 美国制定数据加密标准简况美国制定数据加密标准简况n美国美国NBSNBS（National Bureau of Standards）在在19731973年年5

19、5月月1515公布了征求建议。公布了征求建议。19741974年年8 8月月2727日日NBSNBS再次出公告征求建议，再次出公告征求建议，对建议方案提出如下要求：对建议方案提出如下要求：(1)(1)算法必须提供高度的安全性算法必须提供高度的安全性(2)(2)算法必须有详细的说明算法必须有详细的说明, ,并易于理解并易于理解(3)(3)算法的安全性取决于密钥算法的安全性取决于密钥, ,不依赖于算法不依赖于算法(4)(4)算法适用于所有用户算法适用于所有用户(5)(5)算法适用于不同应用场合算法适用于不同应用场合(6)(6)算法必须高效、经济算法必须高效、经济(7)(7)算法必须能被证实有效算法

20、必须能被证实有效(8)(8)算法必须是可出口的算法必须是可出口的美国制定数据加密标准简况美国制定数据加密标准简况nIBM公司在公司在1971年完成的年完成的LUCIFER密码密码 (64 bit分组，代换分组，代换-置换，置换，128 bit密钥密钥)的基础上，改进成为建议的的基础上，改进成为建议的DES体制体制n1975年年3月月17日日NBS公布了这个算法，并说明要以它作为联公布了这个算法，并说明要以它作为联邦信息处理标准，征求各方意见。邦信息处理标准，征求各方意见。n1977年年1月月15日建议被批准为联邦标准日建议被批准为联邦标准FIPS PUB 46，并设，并设计推出计推出DES芯片

21、。芯片。n1981年美国年美国ANSI （American National Standards Institute）将其作为标准，称之为将其作为标准，称之为DEAANSI X3.92n1983年国际标准化组织年国际标准化组织(ISO，International Organization for Standardization)采用它作为标准，称作采用它作为标准，称作DEA-1 美国制定数据加密标准简况美国制定数据加密标准简况nNSA（National Security Agency）宣布每隔）宣布每隔5年重新审议年重新审议DES是否继续作为联邦标准，是否继续作为联邦标准，1988年（年（FI

22、PS46-1）、）、1993年年（FIPS46-2），），1998年不再重新批准年不再重新批准DES为联邦标准。为联邦标准。n虽然虽然DES已有替代的数据加密标准算法，但它仍是迄今为止已有替代的数据加密标准算法，但它仍是迄今为止得到最广泛应用的一种算法，也是一种最有代表性的分组加得到最广泛应用的一种算法，也是一种最有代表性的分组加密体制。密体制。n1993年年4月，月，Clinton政府公布了一项建议的加密技术标准，政府公布了一项建议的加密技术标准，称作密钥托管加密技术标准称作密钥托管加密技术标准EES(Escrowed Encryption Standard)。算法属美国政府。算法属美国政府

23、SECRET密级。密级。美国制定数据加密标准简况美国制定数据加密标准简况nDES发展史确定了发展公用标准算法模式，而发展史确定了发展公用标准算法模式，而EES(Escrowed Encryption Standard)的制定路线与的制定路线与DES的的背道而驰。人们怀疑有陷门和政府部门肆意侵犯公民权利。背道而驰。人们怀疑有陷门和政府部门肆意侵犯公民权利。此举遭到广为反对。此举遭到广为反对。n1995年年5月月AT&T Bell Lab的的M. Blaze博士在博士在PC机上用机上用45分分钟时间使钟时间使SKIPJACK的的 LEAF协议失败，伪造协议失败，伪造ID码获得成码获得成功。功。19

24、95年年7月美国政府宣布放弃用月美国政府宣布放弃用EES来加密数据，只将来加密数据，只将它用于语音通信。它用于语音通信。n1997年年1月美国月美国NIST着手进行着手进行AES（Advanced Encryption Standard）的研究，成立了标准工作室。）的研究，成立了标准工作室。2001年年Rijndael被批准为被批准为AES标准。标准。nDES（Data Encryption Standard）算法于1977年得到美国政府的正式许可，是一种用56位密钥来加密64位数据的方法。这是IBM的研究成果。nDES是第一代公开的、完全说明细节的商业级现代算法，并被世界公认。美国制定数据加

25、密标准简况美国制定数据加密标准简况DES 算法算法n分组长度为分组长度为64 bits (8 bytes)n密文分组长度也是密文分组长度也是64 bits。n密钥长度为密钥长度为64 bits，有，有8 bits奇偶校验，有效密钥长奇偶校验，有效密钥长度为度为56 bits。n算法主要包括：算法主要包括：初始置换初始置换IP、16轮迭代的乘积变换轮迭代的乘积变换、逆初始置换逆初始置换IP-1以及以及16个子密钥产生器。个子密钥产生器。 DES算法框图算法框图 初始置换初始置换IPIPn将将64 bit明文的位置进行置换，得到一个乱序的明文的位置进行置换，得到一个乱序的64 bit明文组，而后分

26、成左右两段，每段为明文组，而后分成左右两段，每段为32 bit，以，以L L0 0和和R R0 0表示。表示。n逆初始置换逆初始置换IPIP-1-1。将。将1616轮迭代后给出的轮迭代后给出的64 bit组进组进行置换，得到输出的密文组。输出为阵中元素按行置换，得到输出的密文组。输出为阵中元素按行读得的结果。行读得的结果。nIPIP和和IPIP-1-1在密码意义上作用不大，它们的作用在于在密码意义上作用不大，它们的作用在于打乱原来输入打乱原来输入x x的的ASCII码字划分的关系。码字划分的关系。 DES算法（续）算法（续）1 初值置换IP 1. 初始置换初始置换M1 M2 M3 M4 M5

27、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 M64DES算法（续）算法（续） 其中其中Mi是二元数字。由下表得是二元数字。由下表得X=IP(M)为：为：M58 M50 M42 M34 M26 M18

28、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 M7DES算法（续）算法（续） 如果再取逆初始置换如果再取逆初始置换Y=IP-1(X)=IP-1(IP(M)，可以，可以看出，看出，M各位的初始顺序将被恢复。各位的初始顺序将

29、被恢复。DES算法（续）算法（续） DES算法轮结构算法轮结构 DES算法（续）算法（续）图图3.7 函数函数F(R,K)的计算过程的计算过程DES算法（续）算法（续）DES算法（续）算法（续） 对每个盒对每个盒Si，其，其6比特输入中，第比特输入中，第1个和第个和第6个比个比特形成一个特形成一个2位二进制数用来选择行，中间位二进制数用来选择行，中间4位用来位用来选择列。行和列选定后，得到其交叉位置的十进制选择列。行和列选定后，得到其交叉位置的十进制数，将这个数表示为数，将这个数表示为4位二进制数即得这一位二进制数即得这一S盒的输盒的输出。出。 例如，例如，S1的输入为的输入为011001，行

30、选为，行选为01（即第（即第1行），列选为行），列选为1100（即第（即第12列），行列交叉位置的列），行列交叉位置的数为数为9，其，其4位二进制表示为位二进制表示为1001，所以，所以S1的输出为的输出为1001。S盒的每一行定义了一个可逆代换。盒的每一行定义了一个可逆代换。DES算法（续）算法（续）DES的的S1-盒的输入和输出关系盒的输入和输出关系nx0 x5 x0 x1 x2 x3 x4 x5 1 0 1 0 1 1 0 0 列号列号 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 行号行号 0 14 4 13 1 2 15 11 8 3 10 6 12 5

31、 9 0 7 1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 3 15 12 8 2 4 9 1 7 5 11 2 14 10 0 6 13 (y0 , y1, y2 , y3)=(0,0,1,0)P置换DES算法密钥的产生算法密钥的产生置换选择置换选择1置换选择置换选择1DES算法密钥的产生（续）算法密钥的产生（续） 和和Feistel密码一样，密码一样，DES的解密和的解密和加密使用同一算法，但子密钥使用的顺加密使用同一算法，但子密钥使用的顺序相反。序相反。DES解密解密DES的

32、的安全性安全性n互补性互补性。DES算法具有下述性质。若明文组算法具有下述性质。若明文组x逐位取逐位取补，密钥补，密钥k逐位取补，即逐位取补，即y=DESk(x), 则有则有 这种互补性会使这种互补性会使DES在选择明文破译下所需的工在选择明文破译下所需的工作量减半。作量减半。n弱密钥和半弱密钥弱密钥和半弱密钥。DES算法在每次迭代时都有一算法在每次迭代时都有一个子密钥供加密用。如果给定初始密钥个子密钥供加密用。如果给定初始密钥k，各轮的子，各轮的子密钥都相同，即有密钥都相同，即有 k1=k2= =k16 就称给定密钥就称给定密钥k为弱密钥为弱密钥(Weak key)。)(xDESyKDES的

33、的安全性安全性若若k为弱密钥，则有为弱密钥，则有 DESk(DESk(x)=x DESk-1(DESk-1(x)=x 即以即以k对对x加密两次或解密两次都可恢复出明文。其加密运加密两次或解密两次都可恢复出明文。其加密运算和解密运算没有区别。算和解密运算没有区别。 弱密钥下使弱密钥下使DES在选择明文攻击下的搜索量减半。在选择明文攻击下的搜索量减半。 如果随机地选择密钥，弱密钥所占比例极小，而且稍加如果随机地选择密钥，弱密钥所占比例极小，而且稍加注意就不难避开。因此，弱密钥的存在不会危及注意就不难避开。因此，弱密钥的存在不会危及DES的安的安全性。全性。DES的的安全性安全性S S盒设计盒设计。

34、 DES靠靠S盒实现非线性变换。盒实现非线性变换。密钥搜索机密钥搜索机。 对对DES安全性批评意见中，较为一致的看法是安全性批评意见中，较为一致的看法是DES的密钥短的密钥短了些。采用穷搜索对已经对了些。采用穷搜索对已经对DES构成了威构成了威胁胁DES算法的安全性 nDES算法正式公开发表以后，引起了一场激烈的争论。1977年，Diffie和Hellman提出了制造一个每秒能测试106个密钥的大规模芯片，这种芯片的机器大约一天就可以搜索DES算法的整个密钥空间，制造这样的机器需要两千万美元。n1993年，R.Session和M.Wiener给出了一个非常详细的密钥搜索机器的设计方案，它基于并

35、行的密钥搜索芯片，此芯片每秒测试5107个密钥，当时这种芯片的造价是10.5美元，5760个这样的芯片组成的系统需要10万美元，这一系统平均1.5天即可找到密钥，如果利用10个这样的系统，费用是100万美元，但搜索时间可以降到2.5小时。可见这种机制是不安全的。nDES的56位短密钥面临的另外一个严峻而现实的问题是：国际互联网Internet的超级计算能力。1997年1月28日，美国的RSA数据安全公司在互联网上开展了一项名为“密钥挑战”的竞赛，悬赏一万美元，破解一段用56位密钥加密的DES密文。n一位名叫Rocke Verser的程序员设计了一个可以通过互联网分段运行的密钥穷举搜索程序，组织

36、实施了一个称为DESHALL的搜索行动，成千上万的志愿者加入到计划中，在计划实施的第96天，即挑战赛计划公布的第140天，1997年6月17日晚上10点39分，美国盐湖城Inetz公司的职员Michael Sanders成功地找到了密钥，在计算机上显示了明文：“The unknown message is: Strong cryptography makes the world a safer place”。n1998年7月电子前沿基金会（EFF）使用一台25万美元的电脑在56小时内破译了56比特密钥的DES。n1999年1月RSA数据安全会议期间，电子前沿基金会用22小时15分钟就宣告破解了

37、一个DES的密钥。n尽管DES有这样那样的不足，但是作为第一个公开密码算法的密码体制成功地完成了它的使命，它在密码学发展历史上具有重要的地位。二重二重DES zEEDDxiyixizyi k1 k1k2k2二重二重DES 用用DES进行两次加密，但这是否就意味着两重进行两次加密，但这是否就意味着两重DES加密的强度等价于加密的强度等价于112 bit密钥的密码的强度？密钥的密码的强度？答案是否定的。答案是否定的。 中途相遇攻击法中途相遇攻击法(Meet-in-the-Middle Attack) 由由Diffie和和Hellman1977最早提出，可以降低搜最早提出，可以降低搜索量其基本想法如

38、下。若有明文密文对索量其基本想法如下。若有明文密文对(xi,yi)满足满足 yi=Ek2Ek1xi 则可得则可得 z=Ek1xi=Dk2yi 中途相遇攻击中途相遇攻击给定一已知明密文对给定一已知明密文对(x1,y1)，可按下述方法攻击。，可按下述方法攻击。n以密钥以密钥k1的所有的所有256个可能的取值对此明文个可能的取值对此明文x1加密，加密，并将密文并将密文z存储在一个表中；存储在一个表中；n从所有可能的从所有可能的256个密钥个密钥k2中依任意次序选出一个对中依任意次序选出一个对给定的密文给定的密文y1解密，并将每次解密结果解密，并将每次解密结果z在上述表在上述表中查找相匹配的值。一旦找

39、到，则可确定出两个密中查找相匹配的值。一旦找到，则可确定出两个密钥钥k1和和k2；n以此对密钥以此对密钥k1和和k2对另一已知明文密文对对另一已知明文密文对(x2, y2)中的中的明文明文x2进行加密，如果能得出相应的密文进行加密，如果能得出相应的密文y2就可确就可确定定k1和和k2是所要找的密钥。是所要找的密钥。三重三重DES加密加密加密：加密：y=Ek1Dk2Ek1 x解密：解密：x=Dk1Ek2Dk1yn称其为加密称其为加密-解密解密-加密方案，简记为加密方案，简记为EDE(encrypt-decrypt-encrypt)。n此方案已在此方案已在ANSI X9.17和和ISO 8732标

40、准中采用，并标准中采用，并在保密增强邮递在保密增强邮递(PEM)系统中得到利用。系统中得到利用。n破译它的穷举密钥搜索量为破译它的穷举密钥搜索量为2112 51035量级，而量级，而用差分分析破译也要超过用差分分析破译也要超过1052量级。此方案仍有足量级。此方案仍有足够的安全性。够的安全性。3.3 分组密码的运行模式分组密码的运行模式填充填充(Padding) 给定加密消息的长度是随机的，按给定加密消息的长度是随机的，按64 bit分组分组时，最后一组消息长度可能不足时，最后一组消息长度可能不足64 bit。可以填。可以填充一些数字，通常用最后充一些数字，通常用最后1 1字节作为填充指示符字

41、节作为填充指示符（PI）。它所表示的十进制数字就是填充占有的它所表示的十进制数字就是填充占有的字节数。字节数。数据尾部、填充字符和填充指示符一起数据尾部、填充字符和填充指示符一起作为一组进行加密。作为一组进行加密。 数据填 充PI 主要工作模式主要工作模式 即使有了安全的分组密码算法，也需要采用适即使有了安全的分组密码算法，也需要采用适当的工作模式来隐蔽明文的统计特性、数据的格当的工作模式来隐蔽明文的统计特性、数据的格式等，以提高整体的安全性，降低删除、重放、式等，以提高整体的安全性，降低删除、重放、插入和伪造成功的机会。插入和伪造成功的机会。n电码本电码本(ECB(ECB，Electroni

42、c CodeBookElectronic CodeBook) )n密码分组链接模式密码分组链接模式(CBC,Cipher(CBC,Cipher Block Chaining) Block Chaining) n密码反馈模式密码反馈模式(CFB,Cipher(CFB,Cipher Feedback) Feedback)n输出反馈模式输出反馈模式(OFB,Output(OFB,Output Feedback) Feedback) 电码本电码本ECB模式模式n直接利用加密算法分别对分组数据组加密。直接利用加密算法分别对分组数据组加密。n在给定的密钥下，同一明文组总产生同样的密文在给定的密钥下，同一明

43、文组总产生同样的密文组。这会暴露明文数据的格式和统计特征。组。这会暴露明文数据的格式和统计特征。 明文数据都有固定的格式，需要以协议的形式定明文数据都有固定的格式，需要以协议的形式定义，重要的数据常常在同一位置上出现，使密码义，重要的数据常常在同一位置上出现，使密码分析者可以对其进行统计分析、重传和代换攻击分析者可以对其进行统计分析、重传和代换攻击。 电码本电码本ECB模式模式 电码本电码本ECB模式模式 ECB在用于在用于短数据短数据（如加密密钥）时非常理想，因此（如加密密钥）时非常理想，因此如果需要安全地传递如果需要安全地传递DESDES密钥，密钥，ECBECB是最合适的模式。是最合适的模

44、式。 ECB的的最大特性最大特性是同一明文分组在消息中重复出现的是同一明文分组在消息中重复出现的话，产生的密文分组也相同。话，产生的密文分组也相同。 ECB用于用于长消息时可能不够安全长消息时可能不够安全，如果消息有固定结，如果消息有固定结构，密码分析者有可能找出这种关系。构，密码分析者有可能找出这种关系。密码分组链接密码分组链接CBC模式模式 为了解决为了解决ECB的安全缺陷，可以让重复的明文分组的安全缺陷，可以让重复的明文分组产生不同的密文分组，产生不同的密文分组，CBC（cipher block chaining）模式就可满足这一要求。模式就可满足这一要求。 加密算法的输入是加密算法的输

45、入是当前明文分组当前明文分组和和前一次密文分组前一次密文分组的异或，因此加密算法的输入不会显示出与这次的明的异或，因此加密算法的输入不会显示出与这次的明文分组之间的固定关系，所以重复的明文分组不会在文分组之间的固定关系，所以重复的明文分组不会在密文中暴露出这种重复关系。密文中暴露出这种重复关系。 CBC模式示意图模式示意图CBC的优缺点n优点：能隐蔽明文的数据模式，在某种程度上能防止数据纂改，诸如重放、嵌入和删除等。n缺点：会出现传播错误，对同步差错敏感（增加或丢失一个或多个比特）。CBC的错误传播的错误传播1. 1. 明文有一组中有错，会使以后的密文组都受影明文有一组中有错，会使以后的密文组

46、都受影响，但经解密后的恢复结果，除原有误的一组外，响，但经解密后的恢复结果，除原有误的一组外，其后各组明文都正确地恢复。其后各组明文都正确地恢复。2.2.若在传送过程中，某组密文组若在传送过程中，某组密文组y yi i出错时，则该组出错时，则该组恢复的明文恢复的明文xxi i和下一组恢复数据和下一组恢复数据xxi+1i+1出错。出错。再后面的组将不会受再后面的组将不会受y yi i中错误比特的影响。中错误比特的影响。k-比特密码反馈比特密码反馈CFB模式模式n若待加密消息必须按字符若待加密消息必须按字符(如电传电报如电传电报)或按或按比特处理时，可采用比特处理时，可采用CFB模式模式。nCFB

47、实际上是将加密算法实际上是将加密算法DES作为一个密钥作为一个密钥流产生器，当流产生器，当k1时就退化为前面讨论的流时就退化为前面讨论的流密码了。密码了。nCFB与与CBC的区别是反馈的密文长度为的区别是反馈的密文长度为k，且不是直接与明文相加，而是反馈至密钥产且不是直接与明文相加，而是反馈至密钥产生器。生器。CFB模式示意图模式示意图密码反馈密码反馈CFB模式模式nCFB的优点的优点n它特别适于用户数据格式的需要。它特别适于用户数据格式的需要。n能隐蔽明文数据图样，也能检测出对手对于密能隐蔽明文数据图样，也能检测出对手对于密文的篡改。文的篡改。nCFB的缺点的缺点n对信道错误较敏感，且会造成

48、错误传播。对信道错误较敏感，且会造成错误传播。nCFB也需要一个初始矢量，并要和密钥同时进也需要一个初始矢量，并要和密钥同时进行更换。行更换。输出反馈输出反馈OFB模式模式n将分组密码算法作为一个密钥流产生器，其输出将分组密码算法作为一个密钥流产生器，其输出的的k-bit密钥直接反馈至分组密码的输入端，同时密钥直接反馈至分组密码的输入端，同时这这k-bit密钥和输入的密钥和输入的k-bit明文段进行对应位模明文段进行对应位模2相相加。加。n克服了克服了CBC和和CFB的错误传播所带来的问题。的错误传播所带来的问题。 n对于密文被篡改难以进行检测对于密文被篡改难以进行检测n不具有自同步能力，要求

49、系统要保持严格的同步不具有自同步能力，要求系统要保持严格的同步比较和选用比较和选用nECB模式，简单、高速，但最弱、易受重发攻击，模式，简单、高速，但最弱、易受重发攻击，一般不推荐。一般不推荐。nCBC适用于文件加密，但较适用于文件加密，但较ECB慢。安全性加强。慢。安全性加强。当有少量错误时，也不会造成同步错误。当有少量错误时，也不会造成同步错误。nOFB和和CFB较较CBC慢许多。每次迭代只有少数慢许多。每次迭代只有少数bit完成加密。若可以容忍少量错误扩展，则可换来完成加密。若可以容忍少量错误扩展，则可换来恢复同步能力，此时用恢复同步能力，此时用CFB。在字符为单元的流。在字符为单元的流

50、密码中多选密码中多选CFB模式。模式。nOFB用于高速同步系统，不容忍差错传播。用于高速同步系统，不容忍差错传播。3.4 高级加密标准高级加密标准 AES AES提出提出n1997年年1月，美国月，美国NIST向全世界密码学界向全世界密码学界发出征集发出征集21世纪高级加密标准（世纪高级加密标准（AESAdvanced Encryption Standard）算法）算法的公告，并成立了的公告，并成立了AES标准工作研究室，标准工作研究室，1997年年4月月15日的例会制定了对日的例会制定了对AES的评的评估标准。估标准。n AES的要求（1）AES是公开的；是公开的；（2）AES为单钥体制分组

51、密码；为单钥体制分组密码；（3）AES的密钥长度可变，可按需要增大；的密钥长度可变，可按需要增大；（4）AES适于用软件和硬件实现；适于用软件和硬件实现；（5）AES可以自由地使用，或按符合美国国家可以自由地使用，或按符合美国国家标准（标准（ANST）策略的条件使用；）策略的条件使用；算法衡量条件n满足以上要求的满足以上要求的AES算法，需按下述条算法，需按下述条件判断优劣件判断优劣na. 安全性安全性nb. 计算计算效率效率nc. 内内存要求存要求nd. 使用使用简便性简便性ne. 灵活性。灵活性。AES的评审的评审n 1998年年4月月15日全面征集日全面征集AES算法的工作结束。算法的工

52、作结束。1998年年8月月20日举行了首届日举行了首届AES讨论会，对涉及讨论会，对涉及14个国家的密码个国家的密码学家所提出的候选学家所提出的候选AES算法进行了评估和测试，初选并算法进行了评估和测试，初选并公布了公布了15个被选方案，供大家公开讨论。个被选方案，供大家公开讨论。 CAST-256， RC-6， CRYPTON-128，DEAL-128， FROG， DFC， LOKI-97， MAGENTA， MARS， HPC, RIJNDAEL， SAFER+， SERPENT， E-2， TWOFISH。n这些算法设计思想新颖，技术水平先进，算法的强度都这些算法设计思想新颖，技术水平

53、先进，算法的强度都超过超过3-DES，实现速度快于，实现速度快于3-DES。 AES的评审的评审n1999年年8月月9日日NIST宣布第二轮筛选出的宣布第二轮筛选出的5个个候选算法为：候选算法为： MARS(C.Burwick等等,IBM）， RC6TM（R. Rivest等等,RSA Lab.)， RIJNDEAL(J. Daemen,比比)， SERPENT(R. Anderson等，等，英、以、挪威英、以、挪威)， TWOFISH(B. Schiener)。n2000年年10月月2日，日，NIST宣布宣布Rijndael作为新的作为新的AESAES算法设计思想n抵抗所有已知的攻击；n在多

54、个平台上速度快，编码紧凑；n设计简单。nRijndael没有采用Feistel结构，轮函数由3个不同的可逆均匀变换构成的，称为3个层n均匀变换是指状态的每个bit都用类似的方法处理轮函数的3层n线性混合层线性混合层n确保多轮之上的高度扩散；确保多轮之上的高度扩散；n非线性层非线性层n将具有最优的将具有最优的“最坏情况非线性特性最坏情况非线性特性”的的S盒并行使用；盒并行使用；n密钥加层密钥加层n单轮子密钥简单的异或到中间状态上，实现单轮子密钥简单的异或到中间状态上，实现一次性掩盖。一次性掩盖。算法说明算法说明n密钥长度可变，各自可独立指定为密钥长度可变，各自可独立指定为128、192、256比

55、特。比特。n状态状态n算法中间的结果也需要分组，称之为状态，状态可算法中间的结果也需要分组，称之为状态，状态可以用以字节为元素的矩阵阵列表示，该阵列有以用以字节为元素的矩阵阵列表示，该阵列有4行，行，列数列数Nb为分组长度除为分组长度除32n种子密钥种子密钥n以字节为元素的矩阵阵列描述，阵列为以字节为元素的矩阵阵列描述，阵列为4行，列数行，列数Nk为密钥长度除为密钥长度除321.1. Rijndael数学基础数学基础定义定义一个由一个由 组成的字节组成的字节b可表示为系数为可表示为系数为0，1的二进制多项式：的二进制多项式： 定义定义在在 上的加法定义为二进制多项式的加法，且其上的加法定义为二

56、进制多项式的加法，且其系数模系数模2。定义定义 在在 上的乘法（用符号上的乘法（用符号表示）定义为二进制多表示）定义为二进制多项式的乘积模一个次数为项式的乘积模一个次数为8的不可约二进制多项式，此的不可约二进制多项式，此不可约多项式为（十六进制为不可约多项式为（十六进制为11B） 上面定义的乘法在上面定义的乘法在 上满足结合律，且有一个本原元上满足结合律，且有一个本原元（02）。）。 01234567bbbbbbbb01223344556677bxbxbxbxbxbxbxb8(2 )GF8(2 )GF843( )1m xxxxx8(2 )GF定义定义 在在 上的二进制多项式上的二进制多项式b(

57、x)的乘法逆为满足方程的乘法逆为满足方程式式 的二进制多项式的二进制多项式a(x)，记为，记为 定义定义 函数函数xtime(x)定义为定义为 上的上的xb(x)。其运算如下：。其运算如下：若若b7 =0，则，则xb(x)的结果就是把字节的结果就是把字节b左移一位；若左移一位；若b7 =1，则结果需异或则结果需异或1B。定义定义 有限域有限域 上的多项式是系数取自上的多项式是系数取自 元素的多项元素的多项式，这样，一个式，这样，一个4字节向量与一个次数小于字节向量与一个次数小于4的多项式的多项式相对应。相对应。定义定义 上的多项式的加法定义为相应项系数相加。上的多项式的加法定义为相应项系数相加

58、。 因为在域因为在域 上的加是简单的按位异或，所以在域上的加是简单的按位异或，所以在域 上的两向量的加也就是简单的按位异或。上的两向量的加也就是简单的按位异或。8(2 )GF( ) ( )mod( )1a x b xm x )(1xb8(2 )GF8(2 )GF8(2 )GF(2)GF(2)GF8(2 )GF定义定义 上的多项式上的多项式 和和 相乘模相乘模 的的积（表示为积（表示为 ）为）为 ，其系数由下面其系数由下面4个式子得到：个式子得到： ， ， ， ，利用该定义有利用该定义有 。8(2 )GF0112233)(axaxaxaxa0112233)(bxbxbxbxb14x( )( )

59、( )c xa x b x0112233)(cxcxcxcxc312213000babababac322310011babababac332011022babababac3012112033babababac3102132)(bxbxbxbxbx可将上述计算表示为321001233012230112303210bbbbaaaaaaaaaaaaaaaacccc注意到M(x)不是GF(28)上的不可约多项式（甚至也不是GF(2)上的不可约多项式），因此非0多项式的这种乘法不是群运算。不过在Rijndael密码中，对多项式b(x)，这种乘法运算只限于乘一个固定的有逆元的多项式a(x)= a3x3+a

60、2x2+a1x+a0。定理3.1 系数在GF(28)上的多项式a3x3+a2x2+a1x+a0是模x4+1可逆的，当且仅当矩阵在GF(28)上可逆。0321103221033210aaaaaaaaaaaaaaaa证明：a3x3+a2x2+a1x+a0是模x4+1可逆的，当且仅当存在多项式h3x3+h2x2+h1x+h0(a3x3+a2x2+a1x+a0)(h3x3+h2x2+h1x+h0)=1 mod(x4+1)因此有(a3x3+a2x2+a1x+a0)(h2x3+h1x2+h0 x+h3)=x mod (x4+1)(a3x3+a2x2+a1x+a0)(h1x3+h0 x2+h3x+h2)=x