第3章-分组密码

1、 第三章第三章 分组密码分组密码3.1 3.1 分组密码概述分组密码概述3.2 DES3.2 DES3.3 3.3 分组密码运行模式分组密码运行模式3.4 AES3.4 AES3.5 SMS4 3.5 SMS4 一、分组密码概述一、分组密码概述分组密码概述分组密码概述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, x

3、1, xn-1)明文明文x=(x0, x1, xn-1)密文密文y=(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。在。在以软件实现时，应选用简单的运算，使作用于以软件实现时，应选用简单的运算，使作用于子段上的密码运算易于以标准处理器的基本运子段上的密码运算易于以标准处理器的基本运算，如算，如加、乘、移位加、乘、移位等实现，避免用以软件难等实现，避免用以软件难于实现的逐比特

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

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

9、的、元素个数较多的代换集。实用密码体制的集合码体制的集合S S中的元素个数都远小于中的元素个数都远小于2 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-盒的输

10、入和输出关系盒的输入和输出关系nx5 x0 x5 x4 x3 x2 x1 x0 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 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盒的设计

11、准则盒的设计准则 迄今为止，有关方面未曾完全公开有关迄今为止，有关方面未曾完全公开有关DES的的S盒的设计准盒的设计准则。则。Branstead等曾披露过下述准则：等曾披露过下述准则：nP1 S盒的输出都不是其输入的线性或仿射函数。盒的输出都不是其输入的线性或仿射函数。nP2 改变改变S盒的一个输入比特，其输出至少有两比特产生变盒的一个输入比特，其输出至少有两比特产生变化，即近一半产生变化。化，即近一半产生变化。nP3 当当S盒的任一输入位保持不变，其它盒的任一输入位保持不变，其它5位输入变化时位输入变化时(共共有有25 =32种情况种情况)，输出数字中的，输出数字中的0和和1的总数近于相等。

12、的总数近于相等。 这三点使这三点使DES的的S盒能够实现较好的混淆。盒能够实现较好的混淆。Feistel密码结构密码结构乘积密码乘积密码指顺序地执行两个或多个基本密码系统，指顺序地执行两个或多个基本密码系统，使得最后结果的密码强度高于每个基本密码系统产使得最后结果的密码强度高于每个基本密码系统产生的结果生的结果. .Feistel还提出了实现代换和置换的方法。其思想实还提出了实现代换和置换的方法。其思想实际上是际上是Shannon提出的提出的利用乘积密码实现混淆和扩利用乘积密码实现混淆和扩散思想散思想的具体应用。的具体应用。Feistel网络示意图网络示意图输入是分组长为输入是分组长为2w的明

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

14、下参数和特性有关： 分组大小分组大小: : 分组越大则安全性越高，但加密速度就越慢。分组越大则安全性越高，但加密速度就越慢。 密钥大小密钥大小：密钥越长则安全性越高，但加密速度就越慢。：密钥越长则安全性越高，但加密速度就越慢。 轮数轮数：单轮结构远不足以保证安全性，但多轮结构可提供：单轮结构远不足以保证安全性，但多轮结构可提供足够的安全性。典型地，轮数取为足够的安全性。典型地，轮数取为1616。 子密钥产生算法子密钥产生算法：该算法的复杂性越大，则密码分析的困：该算法的复杂性越大，则密码分析的困难性就越大。难性就越大。 轮函数轮函数：轮函数的复杂性越大，密码分析的困难性也越大。：轮函数的复杂性

15、越大，密码分析的困难性也越大。在设计在设计Feistel网络时，还有以下两个方面需要考虑：网络时，还有以下两个方面需要考虑： 快速的软件实现快速的软件实现：在很多情况中，算法是被镶嵌在应用：在很多情况中，算法是被镶嵌在应用程序中，因而无法用硬件实现。此时算法的执行速度是考虑程序中，因而无法用硬件实现。此时算法的执行速度是考虑的关键。的关键。 算法容易分析算法容易分析：如果算法能被无疑义地解释清楚，就可：如果算法能被无疑义地解释清楚，就可容易地分析算法抵抗攻击的能力，有助于设计高强度的算法。容易地分析算法抵抗攻击的能力，有助于设计高强度的算法。Feistel密码结构密码结构 Feistel解密过

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

17、 RDKREF REKLEF REKF REKLEFeistel密码结构密码结构所以解密过程第所以解密过程第1 1轮的输出为轮的输出为LE15RE15，等于加密过程第，等于加密过程第16轮输入左右两半交换后的结果。容易证明这种对应关系在轮输入左右两半交换后的结果。容易证明这种对应关系在16轮中每轮都成立。一般地，加密过程的第轮中每轮都成立。一般地，加密过程的第i轮有轮有因此因此111,iiiiiiLERERELEF REK111,iiiiiiiiiRELELEREF REKREF LE KFeistel密码结构密码结构3.2 美国数据加密标准美国数据加密标准DES（Data Encryptio

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

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

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

21、PUB 46，并设，并设计推出计推出DES芯片。芯片。n1981年美国年美国ANSI 将其作为标准，称之为将其作为标准，称之为DEAANSI X3.92n1983年国际标准化组织年国际标准化组织(ISO)采用它作为标准，称作采用它作为标准，称作DEA-1 美国制定数据加密标准简况美国制定数据加密标准简况nNSA宣布每隔宣布每隔5年重新审议年重新审议DES是否继续作为联邦标准，是否继续作为联邦标准，1988年（年（FIPS46-1）、）、1993年年（FIPS46-2），），1998年不再重年不再重新批准新批准DES为联邦标准。为联邦标准。n虽然虽然DES已有替代的数据加密标准算法，但它仍是迄今

22、为止已有替代的数据加密标准算法，但它仍是迄今为止得到最广泛应用的一种算法，也是一种最有代表性的分组加得到最广泛应用的一种算法，也是一种最有代表性的分组加密体制。密体制。n1993年年4月，月，Clinton政府公布了一项建议的加密技术标准，政府公布了一项建议的加密技术标准，称作密钥托管加密技术标准称作密钥托管加密技术标准EES(Escrowed Encryption Standard)。算法属美国政府。算法属美国政府SECRET密级。密级。美国制定数据加密标准简况美国制定数据加密标准简况nDES发展史确定了发展公用标准算法模式，而发展史确定了发展公用标准算法模式，而EES的制定的制定路线与路线

23、与DES的背道而驰。人们怀疑有陷门和政府部门肆意的背道而驰。人们怀疑有陷门和政府部门肆意侵犯公民权利。此举遭到广为反对。侵犯公民权利。此举遭到广为反对。n1995年年5月月AT&T Bell Lab的的M. Blaze博士在博士在PC机上用机上用45分分钟时间使钟时间使SKIPJACK的的 LEAF协议失败，伪造协议失败，伪造ID码获得成码获得成功。功。1995年年7月美国政府宣布放弃用月美国政府宣布放弃用EES来加密数据，只将来加密数据，只将它用于语音通信。它用于语音通信。n1997年年1月美国月美国NIST着手进行着手进行AES（Advanced Encryption Standard）的

24、研究，成立了标准工作室。）的研究，成立了标准工作室。2001年年Rijndael被批准为被批准为AES标准。标准。nDES（Data Encryption Standard）算法于1977年得到美国政府的正式许可，是一种用56位密钥来加密64位数据的方法。这是IBM的研究成果。nDES是第一代公开的、完全说明细节的商业级现代算法，并被世界公认。美国制定数据加密标准简况美国制定数据加密标准简况DES 算法算法n分组长度为分组长度为64 bits (8 bytes)n密文分组长度也是密文分组长度也是64 bits。n密钥长度为密钥长度为64 bits，有，有8 bits奇偶校验，有效密钥长奇偶校验

25、，有效密钥长度为度为56 bits。n算法主要包括：算法主要包括：初始置换初始置换IP、16轮迭代的乘积变换轮迭代的乘积变换、逆初始置换逆初始置换IP-1以及以及16个子密钥产生器。个子密钥产生器。 DES算法框图算法框图 初始置换初始置换IPIPn将将64 bit明文的位置进行置换，得到一个乱序的明文的位置进行置换，得到一个乱序的64 bit明文组，而后分成左右两段，每段为明文组，而后分成左右两段，每段为32 bit，以，以L L0 0和和R R0 0表示。表示。n逆初始置换逆初始置换IPIP-1-1。将。将1616轮迭代后给出的轮迭代后给出的64 bit组进组进行置换，得到输出的密文组。输

26、出为阵中元素按行置换，得到输出的密文组。输出为阵中元素按行读得的结果。行读得的结果。nIPIP和和IPIP-1-1在密码意义上作用不大，它们的作用在于在密码意义上作用不大，它们的作用在于打乱原来输入打乱原来输入x x的的ASCII码字划分的关系。码字划分的关系。 DES算法（续）算法（续）1 初值置换IP 1. 初始置换初始置换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

27、 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是二元数字。由表是二元数字。由表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

28、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各位的初始顺序将被恢复。各位的初始顺序将被恢复。DES算法（续）算法（续） DES算法轮结构算法轮结构 DES算法（续）算法（续）图图3.7 函数函数F(R,K)的计算过程的计算过程DES算法（续）算法（续）选择压缩运算选择压缩运算S 6 bit 选择函数组选择函数组 4

29、 bit 48 bit 寄存器32 bit 寄存器S1S2S3S4S5S6S7S8DES算法（续）算法（续） 对每个盒对每个盒Si，其，其6比特输入中，第比特输入中，第1个和第个和第6个比个比特形成一个特形成一个2位二进制数，用来选择位二进制数，用来选择Si的的4个代换中个代换中的一个。的一个。6比特输入中，中间比特输入中，中间4位用来选择列。行和位用来选择列。行和列选定后，得到其交叉位置的十进制数，将这个数列选定后，得到其交叉位置的十进制数，将这个数表示为表示为4位二进制数即得这一位二进制数即得这一S盒的输出。盒的输出。 例如，例如，S1的输入为的输入为011001，行选为，行选为01（即第

30、（即第1行），列选为行），列选为1100（即第（即第12列），行列交叉位置的列），行列交叉位置的数为数为9，其，其4位二进制表示为位二进制表示为1001，所以，所以S1的输出为的输出为1001。S盒的每一行定义了一个可逆代换。盒的每一行定义了一个可逆代换。DES算法（续）算法（续）DES的的S1-盒的输入和输出关系盒的输入和输出关系nx5 x0 x5 x4 x3 x2 x1 x0 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 9 0 7 1 0

31、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)DES算法密钥的产生算法密钥的产生子密钥产生器框图子密钥产生器框图 密钥（64 bit ）置换选择1，PC1置换选择2，PC2 Ci(28 bit) Di(28 bit) 循环左移ti+1bit 循环左移ti+1bit除去第8,16, ,64位(8个校验位)kiDES算法密钥的产生（续）算法密钥的产生（续） 和

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

33、各轮的子，各轮的子密钥都相同，即有密钥都相同，即有 k1=k2= =k16 就称给定密钥就称给定密钥k为弱密钥为弱密钥(Weak key)。)(xDESyKDES的的安全性安全性若若k为弱密钥，则有为弱密钥，则有 DESk(DESk(x)=x DESk-1(DESk-1(x)=x 即以即以k对对x加密两次或解密两次都可恢复出明文。其加密运加密两次或解密两次都可恢复出明文。其加密运算和解密运算没有区别。算和解密运算没有区别。 弱密钥下使弱密钥下使DES在选择明文攻击下的搜索量减半。在选择明文攻击下的搜索量减半。 如果随机地选择密钥，弱密钥所占比例极小，而且稍加如果随机地选择密钥，弱密钥所占比例极

34、小，而且稍加注意就不难避开。因此，弱密钥的存在不会危及注意就不难避开。因此，弱密钥的存在不会危及DES的安的安全性。全性。DES的的安全性安全性S S盒设计盒设计。 DES靠靠S盒实现非线性变换。盒实现非线性变换。密钥搜索机密钥搜索机。 对对DES安全性批评意见中，较为一致的看法是安全性批评意见中，较为一致的看法是DES的密钥短的密钥短了些。采用穷搜索对已经对了些。采用穷搜索对已经对DES构成了威构成了威胁胁DES算法的安全性 nDES算法正式公开发表以后，引起了一场激烈的争论。1977年，Diffie和Hellman提出了制造一个每秒能测试106个密钥的大规模芯片，这种芯片的机器大约一天就可

35、以搜索DES算法的整个密钥空间，制造这样的机器需要两千万美元。n1993年，R.Session和M.Wiener给出了一个非常详细的密钥搜索机器的设计方案，它基于并行的密钥搜索芯片，此芯片每秒测试5107个密钥，当时这种芯片的造价是10.5美元，5760个这样的芯片组成的系统需要10万美元，这一系统平均1.5天即可找到密钥，如果利用10个这样的系统，费用是100万美元，但搜索时间可以降到2.5小时。可见这种机制是不安全的。nDES的56位短密钥面临的另外一个严峻而现实的问题是：国际互联网Internet的超级计算能力。1997年1月28日，美国的RSA数据安全公司在互联网上开展了一项名为“密钥

36、挑战”的竞赛，悬赏一万美元，破解一段用56位密钥加密的DES密文。n一位名叫Rocke Verser的程序员设计了一个可以通过互联网分段运行的密钥穷举搜索程序，组织实施了一个称为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月电子前沿

37、基金会（EFF）使用一台25万美圆的电脑在56小时内破译了56比特密钥的DES。n1999年1月RSA数据安全会议期间，电子前沿基金会用22小时15分钟就宣告破解了一个DES的密钥。n尽管DES有这样那样的不足，但是作为第一个公开密码算法的密码体制成功地完成了它的使命，它在密码学发展历史上具有重要的地位。二重二重DES zEEDDxiyixizyi k1 k1k2k2二重二重DES 用用DES进行两次加密，但这是否就意味着两重进行两次加密，但这是否就意味着两重DES加密的强度等价于加密的强度等价于112 bit密钥的密码的强度？密钥的密码的强度？答案是否定的。答案是否定的。 中途相遇攻击法中途

38、相遇攻击法(Meet-in-the-Middle Attack) 由由Diffie和和Hellman1977最早提出，可以降低搜最早提出，可以降低搜索量其基本想法如下。若有明文密文对索量其基本想法如下。若有明文密文对(xi,yi)满足满足 yi=Ek2Ek1xi 则可得则可得 z=Ek1xi=Dk2yi 中途相遇攻击中途相遇攻击给定一已知明密文对给定一已知明密文对(x1,y1)，可按下述方法攻击。，可按下述方法攻击。n以密钥以密钥k1的所有的所有256个可能的取值对此明文个可能的取值对此明文x1加密，加密，并将密文并将密文z存储在一个表中；存储在一个表中；n从所有可能的从所有可能的256个密钥

39、个密钥k2中依任意次序选出一个对中依任意次序选出一个对给定的密文给定的密文y1解密，并将每次解密结果解密，并将每次解密结果z在上述表在上述表中查找相匹配的值。一旦找到，则可确定出两个密中查找相匹配的值。一旦找到，则可确定出两个密钥钥k1和和k2；n以此对密钥以此对密钥k1和和k2对另一已知明文密文对对另一已知明文密文对(x2, y2)中的中的明文明文x2进行加密，如果能得出相应的密文进行加密，如果能得出相应的密文y2就可确就可确定定k1和和k2是所要找的密钥。是所要找的密钥。中途相遇攻击中途相遇攻击n对于给定明文对于给定明文x，以两重，以两重DES加密将有加密将有264个可能个可能的密文。的密

40、文。n可能的密钥数为可能的密钥数为2112个。所以，在给定明文下，个。所以，在给定明文下，将有将有2112/264 =248个密钥能产生给定的密文。个密钥能产生给定的密文。n用另一对用另一对64bits明文密文对进行检验，就使虚报明文密文对进行检验，就使虚报率降为率降为248-64=2-16。n这一攻击法所需的存储量为这一攻击法所需的存储量为2568 Byte，最大试，最大试验的加密次数验的加密次数2256 =257。这说明破译双重。这说明破译双重DES的难度为的难度为257量级。量级。三重三重DES加密加密加密：加密：y=Ek1Dk2Ek1 x解密：解密：x=Dk1Ek2Dk1yn称其为加密

41、称其为加密-解密解密-加密方案，简记为加密方案，简记为EDE(encrypt-decrypt-encrypt)。n此方案已在此方案已在ANSI X9.17和和ISO 8732标准中采用，并标准中采用，并在保密增强邮件在保密增强邮件(PEM)系统中得到利用。系统中得到利用。n破译它的穷举密钥搜索量为破译它的穷举密钥搜索量为2112 51035量级，而量级，而用差分分析破译也要超过用差分分析破译也要超过1052量级。此方案仍有足量级。此方案仍有足够的安全性。够的安全性。3.3 分组密码的运行模式分组密码的运行模式填充填充(Padding) 给定加密消息的长度是随机的，按给定加密消息的长度是随机的，

42、按64 bit分组分组时，最后一组消息长度可能不足时，最后一组消息长度可能不足64 bit。可以填。可以填充一些数字，通常用最后充一些数字，通常用最后1 1字节作为填充指示符字节作为填充指示符（PI）。它所表示的十进制数字就是填充占有的它所表示的十进制数字就是填充占有的字节数。字节数。数据尾部、填充字符和填充指示符一起数据尾部、填充字符和填充指示符一起作为一组进行加密。作为一组进行加密。 数据填 充PI 主要工作模式主要工作模式 即使有了安全的分组密码算法，也需要采用适即使有了安全的分组密码算法，也需要采用适当的工作模式来隐蔽明文的统计特性、数据的格当的工作模式来隐蔽明文的统计特性、数据的格式

43、等，以提高整体的安全性，降低删除、重放、式等，以提高整体的安全性，降低删除、重放、插入和伪造成功的机会。插入和伪造成功的机会。n电码本电码本(ECB)(ECB)n密码分组链接模式密码分组链接模式(CBC) (CBC) n密码反馈模式密码反馈模式(CFB)(CFB)n输出反馈模式输出反馈模式(OFB)(OFB)n计数模式（计数模式（CTRCTR） 电码本电码本ECB模式模式 电码本电码本ECB模式模式n直接利用加密算法分别对分组数据组加密。直接利用加密算法分别对分组数据组加密。n在给定的密钥下，同一明文组总产生同样的密文在给定的密钥下，同一明文组总产生同样的密文组。这会暴露明文数据的格式和统计特

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

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

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

47、误的一组外，其后各组明文都正确地恢复。其后各组明文都正确地恢复。2.2.若在传送过程中，某组密文组若在传送过程中，某组密文组y yi i出错时，则该组出错时，则该组恢复的明文恢复的明文x xi i和下一组恢复数据和下一组恢复数据x xi+1i+1出错。再后出错。再后面的组将不会受面的组将不会受y yi i中错误比特的影响。中错误比特的影响。k-比特密码反馈比特密码反馈CFB模式模式n若待加密消息必须按字符若待加密消息必须按字符(如电传电报如电传电报)或按或按比特处理时，可采用比特处理时，可采用CFB模式。模式。nCFB实际上是将加密算法实际上是将加密算法DES作为一个密钥作为一个密钥流产生器，

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

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

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

51、播。用于高速同步系统，不容忍差错传播。计算器模式计算器模式 Counter(CTR)CTR的优点n效率n可并行加密n预处理n吞吐量仅受可使用并行数量的限制n加密数据块的随机访问n可证明安全n简单性（只要求实现加密算法）3.4 高级加密标准高级加密标准 AES AES提出提出n1997年年1月，美国月，美国NIST向全世界密码学界向全世界密码学界发出征集发出征集21世纪高级加密标准（世纪高级加密标准（AESAdvanced Encryption Standard）算法）算法的公告，并成立了的公告，并成立了AES标准工作研究室，标准工作研究室，1997年年4月月15日的例会制定了对日的例会制定了对

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

53、。灵活性。AES的评审的评审n 1998年年4月月15日全面征集日全面征集AES算法的工作结束。算法的工作结束。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

54、-2， TWOFISH。n这些算法设计思想新颖，技术水平先进，算法的强度都这些算法设计思想新颖，技术水平先进，算法的强度都超过超过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日，

55、日，NIST宣布宣布Rijndael作为新的作为新的AESAES算法设计思想n抵抗所有已知的攻击；n在多个平台上速度快，编码紧凑；n设计简单。nRijndael没有采用Feistel结构，轮函数由3个不同的可逆均匀变换构成的，称为3个层n均匀变换是指状态的每个bit都用类似的方法处理轮函数的3层n线性混合层线性混合层n确保多轮之上的高度扩散；确保多轮之上的高度扩散；n非线性层非线性层n将具有最优的将具有最优的“最坏情况非线性特性最坏情况非线性特性”的的S盒并行使用；盒并行使用；n密钥加层密钥加层n单轮子密钥简单的异或到中间状态上，实现单轮子密钥简单的异或到中间状态上，实现一次性掩盖。一次性掩盖

56、。什么是域什么是域nF是一个非空集合，定义了加法、乘法两是一个非空集合，定义了加法、乘法两个二元运算，对这两个运算封闭个二元运算，对这两个运算封闭n加法满足：对于任意加法满足：对于任意a,b,cFna+b=b+a；交换律；交换律n(a+b)+c=a+(b+c)；结合律；结合律n存在存在0 F，使得，使得a+0=a；有零元；有零元n存在存在-a F，使得，使得a+(-a)=0；有负元；有负元什么是域？（续）什么是域？（续）n乘法满足：对于任意乘法满足：对于任意a,b,cFnab=ba；交换律；交换律n(ab) c=a(bc)；结合律；结合律n存在存在e F，使得，使得ae=a；有单位元；有单位元

57、n存在存在a-1 F，使得，使得aa-1 =e；有逆元；有逆元n乘法对加法满足分配率乘法对加法满足分配率na(b+c)=ab+ac群群n什么是群？什么是群？n集合集合n集合集合+二元运算二元运算n二元运算满足封闭性、结合律二元运算满足封闭性、结合律n有单位元有单位元n有逆元有逆元n若满足交换律，则称为交换群，此时群若满足交换律，则称为交换群，此时群中运算可认为是加法，也称为加群中运算可认为是加法，也称为加群环环n集合集合n集合集合+加法加法+乘法乘法n加法交换群加法交换群n乘法满足结合律乘法满足结合律n加法和乘法满足分配率加法和乘法满足分配率域域n集合集合+加法加法+乘法乘法n有单位元的交换环

58、有单位元的交换环n非零元构成乘法交换群非零元构成乘法交换群群、环的例子nZn=0，1，2，n-1n加法和乘法运算皆为模加法和乘法运算皆为模n运算运算n在所定义的运算下，在所定义的运算下，Zn是有单位元的交是有单位元的交换环换环nZn在什么情况下是域？在什么情况下是域？域的例子nZn中若所有非零元构成交换群，则中若所有非零元构成交换群，则Zn为为域域n引理：整数引理：整数a在模在模n乘法下有逆元，当且乘法下有逆元，当且仅当仅当a与与n互素。互素。n所有与所有与n互素的元素构成交换群互素的元素构成交换群n1n-1都与都与n互素，则互素，则n为素数为素数n对于任一素数对于任一素数p，Zp为域为域多项

59、式环和扩域域的性质有限域的结构n有限域的三条结构定理有限域的三条结构定理定理定理1 设设F是一个特征为素数是一个特征为素数p的有限域，则的有限域，则F中的中的元素个数为元素个数为pn，n是一个正整数。是一个正整数。定理定理2 （存在性存在性）对于任何素数）对于任何素数p和任意正整数和任意正整数n，总存在一个有限域恰好含有总存在一个有限域恰好含有pn个元素。个元素。定理定理3 （惟一性惟一性）任意两个）任意两个q=pn元域都同构，即元域都同构，即pn元域在同构意义下是惟一的。元域在同构意义下是惟一的。域的性质（续）nF是域是域Zp或记为或记为GF(p)，f(x)是是F上的不上的不可约多项式可约多

60、项式nGF(pn)= Fx/(f(x)可看作是可看作是F上的上的n维向量空间维向量空间n1，x，x2，xn-1是是GF(pn)在在F上的上的一组基一组基n有限域的所有非零元构成一循环群，即有限域的所有非零元构成一循环群，即存在生成元存在生成元 使得所有的元素使得所有的元素都可以表示成都可以表示成的方幂的方幂()*nGF p1.1. Rijndael数学基础数学基础定义定义一个由一个由 组成的字节组成的字节b可表示为系数为可表示为系数为0，1的二进制多项式：的二进制多项式： 定义定义在在 上的加法定义为二进制多项式的加法，且其上的加法定义为二进制多项式的加法，且其系数模系数模2。定义定义 在在