1、 第三章第三章 分组密码分组密码3.1 3.1 分组密码概述分组密码概述3.2 DES3.2 DES3.3 AES 3.3 AES 3.4 3.4 分组密码运行模式分组密码运行模式一、分组密码概述一、分组密码概述分组密码概述分组密码概述n分组密码是许多系统安全的一个重要组成部分。分组密码是许多系统安全的一个重要组成部分。可用于构造可用于构造n伪随机数生成器伪随机数生成器n流密码流密码n消息认证码消息认证码(MAC)(MAC)和杂凑函数和杂凑函数n消息认证技术、数据完整性机构、实体认证协议以消息认证技术、数据完整性机构、实体认证协议以及单钥数字签字体制的核心组成部分及单钥数字签字体制的核心组成部
2、分。 应用中对于分组码的要求应用中对于分组码的要求n安全性安全性n运行速度运行速度n存储量存储量( (程序的长度、数据分组长度、高速缓程序的长度、数据分组长度、高速缓存大小存大小) )n实现平台实现平台( (硬、软件、芯片硬、软件、芯片) )n运行模式运行模式分组密码概述分组密码概述 明文序列明文序列 x1, x2, xi, 加密函数加密函数E: VnKVn 这种密码实质上是字长为这种密码实质上是字长为m的数字序列的代换密码的数字序列的代换密码。 解密算法加密算法密钥k=(k0, k1, kt-1 )密钥k=(k0, k1, kt-1 )明文明文x=(x0, x1, xm-1)明文明文x=(x
3、0, x1, xm-1)密文密文x=(y0, y1, ym-1)分组密码概述分组密码概述n通常取通常取n=m。n若若nm，则为有数据扩展的分组密码。，则为有数据扩展的分组密码。n若若nm，则为有数据压缩的分组密码。，则为有数据压缩的分组密码。分组密码设计问题分组密码设计问题 分组密码的设计问题在于找到一种算法，分组密码的设计问题在于找到一种算法，能在密钥控制下从一个足够大且足够好的能在密钥控制下从一个足够大且足够好的置换子集中，简单而迅速地选出一个置换，置换子集中，简单而迅速地选出一个置换，用来对当前输入的明文的数字组进行加密用来对当前输入的明文的数字组进行加密变换。变换。分组密码设计准则n混
4、淆混淆：人们所设计的密码应使用使得密钥和明文以及密文之间的依赖关系相当复杂以至于这种依赖性对密码分析者来说是无法利用的。n扩散扩散：人们所设计的密码应使得密钥的每一位数字影响密文的许多位数字以防止对密钥进行逐段破译，而且明文的每一位数字也应影响密文的许多位数字以便隐藏明文数字统计特性。分组密码算法应满足的要求分组密码算法应满足的要求n分组长度分组长度n要足够大：要足够大： 防止明文穷举攻击法奏效。防止明文穷举攻击法奏效。n密钥量要足够大：密钥量要足够大： 尽可能消除弱密钥并使所有密钥同等地好，以防止密尽可能消除弱密钥并使所有密钥同等地好，以防止密钥穷举攻击奏效钥穷举攻击奏效。n由密钥确定置换的
5、算法要足够复杂：由密钥确定置换的算法要足够复杂： 充分实现明文与密钥的扩散和混淆，没有简单的关系充分实现明文与密钥的扩散和混淆，没有简单的关系可循可循，要能抗击各种已知的攻击。要能抗击各种已知的攻击。 分组密码算法应满足的要求分组密码算法应满足的要求n加密和解密运算简单加密和解密运算简单： 易于软件和硬件高速实现易于软件和硬件高速实现。n数据扩展：数据扩展： 一般无数据扩展，在采用同态置换和随机化加密技一般无数据扩展，在采用同态置换和随机化加密技术时可引入数据扩展术时可引入数据扩展。n差错传播尽可能地小差错传播尽可能地小。 分组密码的实现原则n软件实现的原则软件实现的原则：使用子块和简单的运算
6、。如：使用子块和简单的运算。如将分组将分组n化分为子段，每段长为化分为子段，每段长为8、16或或32。在。在以软件实现时，应选用简单的运算，使作用于以软件实现时，应选用简单的运算，使作用于子段上的密码运算易于以标准处理器的基本运子段上的密码运算易于以标准处理器的基本运算，如算，如加、乘、移位加、乘、移位等实现，避免用以软件难等实现，避免用以软件难于实现的逐比特置换。于实现的逐比特置换。n硬件实现的原则硬件实现的原则：加密解密可用同样的器件来：加密解密可用同样的器件来实现。实现。代换网络代换网络n代换代换是输入集是输入集A到输出到输出A上的双射变换上的双射变换： fk：AA k是控制输入变量，在
7、密码学中则为密钥是控制输入变量，在密码学中则为密钥。n实现代换实现代换fk的网络称作的网络称作代换网络代换网络。双射条件保证。双射条件保证在给定在给定k下可从密文惟一地恢复出原明文下可从密文惟一地恢复出原明文。代换网络代换网络n代换代换fk的集合：的集合： S=fk k KnK是密钥空间。如果网络可以实现所有可是密钥空间。如果网络可以实现所有可能的能的2n!个代换，则称其为全代换网络个代换，则称其为全代换网络。n全代换网络密钥个数必须满足条件：全代换网络密钥个数必须满足条件：k 2n! 代换结构代换网络代换网络n密码设计中需要先定义代换集密码设计中需要先定义代换集S，而后还需定，而后还需定义解
8、密变换集，即逆代换网络义解密变换集，即逆代换网络S S-1-1，它以密文，它以密文y作为输入矢量，其输出为恢复的明文矢量作为输入矢量，其输出为恢复的明文矢量x x。n要实现全代换网络并不容易。因此实用中常要实现全代换网络并不容易。因此实用中常常利用一些简单的基本代换，通过组合实现常利用一些简单的基本代换，通过组合实现较复杂的、元素个数较多的代换集。实用密较复杂的、元素个数较多的代换集。实用密码体制的集合码体制的集合S S中的元素个数都远小于中的元素个数都远小于2 2n n! !。 代换盒代换盒(S盒盒) 在密码设计中，可选在密码设计中，可选 n=r n0，其中，其中r和和n0都为正整都为正整数
9、，将设计数，将设计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 0 列号列号 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 行号行号 0 14 4 13 1 2 1
10、5 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盒的设计准盒的设计准则。则。Branstead等曾披露过下述准则：等曾披露过下述准则：nP1 S盒的输出都不是其输入的线性或仿射函数。盒的输
11、出都不是其输入的线性或仿射函数。nP2 改变改变S盒的一个输入比特，其输出至少有两比特产生变盒的一个输入比特，其输出至少有两比特产生变化，即近一半产生变化。化，即近一半产生变化。nP3 当当S盒的任一输入位保持不变，其它盒的任一输入位保持不变，其它5位输入变化时位输入变化时(共共有有25 =32种情况种情况)，输出数字中的，输出数字中的0和和1的总数近于相等。的总数近于相等。 这三点使这三点使DES的的S盒能够实现较好的混淆。盒能够实现较好的混淆。Feistel密码结构密码结构乘积密码乘积密码指顺序地执行两个或多个基本密码系统，指顺序地执行两个或多个基本密码系统，使得最后结果的密码强度高于每个
12、基本密码系统产使得最后结果的密码强度高于每个基本密码系统产生的结果生的结果. .Feistel还提出了实现代换和置换的方法。其思想实还提出了实现代换和置换的方法。其思想实际上是际上是Shannon提出的提出的利用乘积密码实现混淆和扩利用乘积密码实现混淆和扩散思想散思想的具体应用。的具体应用。Feistel网络示意图网络示意图输入是分组长为输入是分组长为2w的明文和一个密钥的明文和一个密钥K。将每组明文分成左右。将每组明文分成左右两半两半L0和和R0，在进行完，在进行完n轮迭代后，左右两半再合并到一起以轮迭代后，左右两半再合并到一起以产生密文分组。第产生密文分组。第i i轮迭代的输入为前一轮输出
13、的函数：轮迭代的输入为前一轮输出的函数：其中其中Ki是第是第i轮用的子密钥，由加密密钥轮用的子密钥，由加密密钥K得到。一般地，各轮得到。一般地，各轮子密钥彼此不同而且与子密钥彼此不同而且与K也不同。也不同。111,iiiiiiLRRLF RKFeistel密码结构密码结构Feistel密码结构密码结构Feistel网络的实现与以下参数和特性有关：网络的实现与以下参数和特性有关： 分组大小分组大小: : 分组越大则安全性越高，但加密速度就越慢。分组越大则安全性越高，但加密速度就越慢。 密钥大小密钥大小：密钥越长则安全性越高，但加密速度就越慢。：密钥越长则安全性越高，但加密速度就越慢。 轮数轮数：
14、单轮结构远不足以保证安全性，但多轮结构可提供：单轮结构远不足以保证安全性，但多轮结构可提供足够的安全性。典型地，轮数取为足够的安全性。典型地，轮数取为1616。 子密钥产生算法子密钥产生算法：该算法的复杂性越大，则密码分析的困：该算法的复杂性越大，则密码分析的困难性就越大。难性就越大。 轮函数轮函数：轮函数的复杂性越大，密码分析的困难性也越大。：轮函数的复杂性越大，密码分析的困难性也越大。在设计在设计Feistel网络时，还有以下两个方面需要考虑：网络时，还有以下两个方面需要考虑： 快速的软件实现快速的软件实现：在很多情况中，算法是被镶嵌在应用：在很多情况中，算法是被镶嵌在应用程序中，因而无法
15、用硬件实现。此时算法的执行速度是考虑程序中，因而无法用硬件实现。此时算法的执行速度是考虑的关键。的关键。 算法容易分析算法容易分析：如果算法能被无疑义地解释清楚，就可：如果算法能被无疑义地解释清楚，就可容易地分析算法抵抗攻击的能力，有助于设计高强度的算法。容易地分析算法抵抗攻击的能力，有助于设计高强度的算法。Feistel密码结构密码结构 Feistel解密过程本质上和加密过程是一样的，算法解密过程本质上和加密过程是一样的，算法使用密文作为输入，但使用子密钥使用密文作为输入，但使用子密钥Ki的次序与加密的次序与加密过程相反，即第过程相反，即第1 1轮使用轮使用Kn，第，第2 2轮使用轮使用Kn
16、-1，最后一轮使用最后一轮使用K1。这一特性保证了解密和加密可采。这一特性保证了解密和加密可采用同一算法。用同一算法。Feistel解密结构解密结构 FeistelFeistel加解密过程加解密过程在加密过程中：在解密过程中161516151516,LERERELEF REK10161510016161516151516151615,LDRDLERERDLDF RDKREF REKLEF REKF REKLEFeistel密码结构密码结构所以解密过程第所以解密过程第1 1轮的输出为轮的输出为LE15RE15，等于加密过程第，等于加密过程第16轮输入左右两半交换后的结果。容易证明这种对应关系在轮
17、输入左右两半交换后的结果。容易证明这种对应关系在16轮中每轮都成立。一般地，加密过程的第轮中每轮都成立。一般地，加密过程的第i轮有轮有因此因此111,iiiiiiLERERELEF REK111,iiiiiiiiiRELELEREF REKREF LE KFeistel密码结构密码结构3.2 美国数据加密标准美国数据加密标准DES（Data Encryption Standard）美国制定数据加密标准简况美国制定数据加密标准简况n目的目的 通信与计算机相结合是人类步入信息社会的一个阶梯，通信与计算机相结合是人类步入信息社会的一个阶梯，它始于六十年代末，完成于它始于六十年代末，完成于90年代初。
18、计算机通信网的形年代初。计算机通信网的形成与发展，要求信息作业标准化，安全保密亦不例外。只成与发展，要求信息作业标准化，安全保密亦不例外。只有标准化，才能真正实现网的安全，才能推广使用加密手有标准化，才能真正实现网的安全，才能推广使用加密手段，以便于训练、生产和降低成本。段，以便于训练、生产和降低成本。 美国制定数据加密标准简况美国制定数据加密标准简况n美国美国NBS在在1973年年5月月15公布了征求建议。公布了征求建议。1974年年8月月27日日NBS再次出公告征求建议，对建议方案提出如下再次出公告征求建议，对建议方案提出如下要求：要求：(1)算法必须提供高度的安全性算法必须提供高度的安全
19、性(2)算法必须有详细的说明算法必须有详细的说明,并易于理解并易于理解(3)算法的安全性取决于密钥算法的安全性取决于密钥,不依赖于算法不依赖于算法(4)算法适用于所有用户算法适用于所有用户(5)算法适用于不同应用场合算法适用于不同应用场合(6)算法必须高效、经济算法必须高效、经济(7)算法必须能被证实有效算法必须能被证实有效(8)算法必须是可出口的算法必须是可出口的美国制定数据加密标准简况美国制定数据加密标准简况nIBM公司在公司在1971年完成的年完成的LUCIFER密码密码 (64 bit分组，代分组，代换换-置换，置换，128 bit密钥密钥)的基础上，改进成为建议的的基础上，改进成为建
20、议的DES体体制制n1975年年3月月17日日NBS公布了这个算法，并说明要以它作为公布了这个算法，并说明要以它作为联邦信息处理标准，征求各方意见。联邦信息处理标准，征求各方意见。n1977年年1月月15日建议被批准为联邦标准日建议被批准为联邦标准FIPS PUB 46，并，并设计推出设计推出DES芯片。芯片。n1981年美国年美国ANSI 将其作为标准，称之为将其作为标准，称之为DEAANSI X3.92n1983年国际标准化组织年国际标准化组织(ISO)采用它作为标准，称作采用它作为标准，称作DEA-1 美国制定数据加密标准简况美国制定数据加密标准简况nNSA宣布每隔宣布每隔5年重新审议年
21、重新审议DES是否继续作为联邦标准，是否继续作为联邦标准，1988年（年（FIPS46-1）、）、1993年（年（FIPS46-2），），1998年不再重年不再重新批准新批准DES为联邦标准。为联邦标准。n虽然虽然DES已有替代的数据加密标准算法，但它仍是迄今为止已有替代的数据加密标准算法，但它仍是迄今为止得到最广泛应用的一种算法，也是一种最有代表性的分组加得到最广泛应用的一种算法，也是一种最有代表性的分组加密体制。密体制。n1993年年4月，月，Clinton政府公布了一项建议的加密技术标准，政府公布了一项建议的加密技术标准，称作密钥托管加密技术标准称作密钥托管加密技术标准EES(Escro
22、wed Encryption Standard)。算法属美国政府。算法属美国政府SECRET密级。密级。美国制定数据加密标准简况美国制定数据加密标准简况nDES发展史确定了发展公用标准算法模式，而发展史确定了发展公用标准算法模式，而EES的制定的制定路线与路线与DES的背道而驰。人们怀疑有陷门和政府部门肆意的背道而驰。人们怀疑有陷门和政府部门肆意侵犯公民权利。此举遭到广为反对。侵犯公民权利。此举遭到广为反对。n1995年年5月月AT&T Bell Lab的的M. Blaze博士在博士在PC机上用机上用45分分钟时间使钟时间使SKIPJACK的的 LEAF协议失败，伪造协议失败，伪造ID码获得成
23、码获得成功。功。1995年年7月美国政府宣布放弃用月美国政府宣布放弃用EES来加密数据，只将来加密数据，只将它用于语音通信。它用于语音通信。n1997年年1月美国月美国NIST着手进行着手进行AES（Advanced Encryption Standard）的研究，成立了标准工作室。）的研究，成立了标准工作室。2001年年Rijndael被批准为被批准为AES标准。标准。nDES（Data Encryption Standard）算法于1977年得到美国政府的正式许可，是一种用56位密钥来加密64位数据的方法。这是IBM的研究成果。nDES是第一代公开的、完全说明细节的商业级现代算法，并被世界
24、公认。美国制定数据加密标准简况美国制定数据加密标准简况DES 算法算法n分组长度为分组长度为64 bits (8 bytes)n密文分组长度也是密文分组长度也是64 bits。n密钥长度为密钥长度为64 bits，有，有8 bits奇偶校验，有效密钥长奇偶校验，有效密钥长度为度为56 bits。n算法主要包括：初始置换算法主要包括：初始置换IP、16轮迭代的乘积变换、轮迭代的乘积变换、逆初始置换逆初始置换IP-1以及以及16个子密钥产生器。个子密钥产生器。 DES算法框图算法框图 输入 64 bit明文数据 初始置换IP 乘积变换 （16轮迭代） 逆初始置换IP-1 64 bit密文数据 输出
25、 标准数据加密算法初始置换初始置换IPIPn将将64 bit明文的位置进行置换，得到一个乱序的明文的位置进行置换，得到一个乱序的64 bit明文组，而后分成左右两段，每段为明文组，而后分成左右两段，每段为32 bit，以，以L0和和R0表示，表示，IP中各列元素位置号数相差为中各列元素位置号数相差为8，相当于将原明，相当于将原明文各字节按列写出，各列比特经过偶采样和奇采样置文各字节按列写出，各列比特经过偶采样和奇采样置换后，再对各行进行逆序。将阵中元素按行读出构成换后，再对各行进行逆序。将阵中元素按行读出构成置换输出。置换输出。n逆初始置换逆初始置换IPIP-1-1。将。将16轮迭代后给出的轮
26、迭代后给出的64 bit组进行置组进行置换，得到输出的密文组。输出为阵中元素按行读得的换，得到输出的密文组。输出为阵中元素按行读得的结果。结果。nIP和和IPIP-1-1在密码意义上作用不大，它们的作用在于打乱在密码意义上作用不大，它们的作用在于打乱原来输入原来输入x x的的ASCII码字划分的关系。码字划分的关系。n（1）IP置换表和IP-1逆置换表。输入的64位数据按IP表置换进行重新组合，并把输出分为L0和R0两部分，每部分各32位，其IP表置换如表2-3所示。5850423426181026052443628201246254463830221466456484032241685749
27、413325179159514335271911361534537292113563554739312315740848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725 Li-1(32bit) Ri-1(32bit) 选择扩展运算 E 48 bit寄存器 按bit模2加密 48 bit寄存器 选择压缩运算 S 32 bit寄存器 置换运算 P 按bit模2和 Li (32bit) Ri (32bit)乘积变换框图乘积
28、变换框图密钥产生器nLi = Ri-1nRi= Li f(Ri-1 ,Ki) （i=1,2,3, ,16）乘积变换乘积变换n它是它是DES算法的核心部分。将经过算法的核心部分。将经过IP置换后的数据分成置换后的数据分成32 bit的左右两组，在迭代过程中彼此左右交换位置。的左右两组，在迭代过程中彼此左右交换位置。n每次迭代时只对右边的每次迭代时只对右边的32 bit进行一系列的加密变换，在此进行一系列的加密变换，在此轮迭代即将结束时，把左边的轮迭代即将结束时，把左边的32 bit与右边得到的与右边得到的32 bit逐位逐位模模2相加，作为下一轮迭代时右边的段，并将原来右边未经相加，作为下一轮迭
29、代时右边的段，并将原来右边未经变换的段直接送到左边的寄存器中作为下一轮迭代时左边变换的段直接送到左边的寄存器中作为下一轮迭代时左边的段。的段。n在每一轮迭代时，右边的段要经过在每一轮迭代时，右边的段要经过选择扩展运算选择扩展运算E E、密钥加、密钥加密运算、选择压缩运算密运算、选择压缩运算S S、置换运算、置换运算P P和左右混合运算和左右混合运算。乘积变换乘积变换 选择扩展运算选择扩展运算E E。将输入的。将输入的32 bit Ri-1扩展成扩展成48 bit的输出，令的输出，令s表示表示E原输入数据比特的原下标，则原输入数据比特的原下标，则E的输出是将原下标的输出是将原下标s 0或或1(m
30、od 4)的各比特重复一次得到的，即对原第的各比特重复一次得到的，即对原第32, 1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29各位都重复一次各位都重复一次,实现数据扩实现数据扩展。将表中数据按行读出得到展。将表中数据按行读出得到48 bit输出。输出。 密钥加密运算密钥加密运算。将子密钥产生器输出的。将子密钥产生器输出的48 bit子密钥子密钥ki与选择与选择扩展运算扩展运算E输出的输出的48 bits数据按位模数据按位模2相加。相加。 选择压缩运算选择压缩运算S S。将前面送来的将前面送来的48 bit数据自左至右分成数据自左至右
31、分成8组，组，每组为每组为6 bit。而后并行送入。而后并行送入8个个S一盒，每个一盒，每个S盒为一非线性代盒为一非线性代换网络，有换网络，有4个输出，运算个输出，运算S的框图在图的框图在图4-4-6中给出。中给出。 p.186 图图4-4-6 选择压缩运算选择压缩运算S 置换运算置换运算P P。对。对S1至至S8盒输出的盒输出的32 bit数据进行坐标置换，如图数据进行坐标置换，如图4-4-7所示。置换所示。置换P输出的输出的32 bit数据与左边数据与左边32 bit即即Ri-1逐位模逐位模2相加，所得到的相加，所得到的32 bit作为下一轮迭代用的右边的数字段。并作为下一轮迭代用的右边的
32、数字段。并将将Ri-1并行送到左边的寄存器，作为下一轮迭代用的左边的数并行送到左边的寄存器，作为下一轮迭代用的左边的数字段。字段。 子密钥产生器。将子密钥产生器。将64 bit初始密钥经过初始密钥经过置换选择置换选择PC1PC1、循环移位、循环移位置换、置换选择置换、置换选择PC2PC2给出每次迭代加密用的子密钥给出每次迭代加密用的子密钥ki，参看图，参看图4-4-8。在。在64 bit初始密钥中有初始密钥中有8位为校验位，其位置号为位为校验位，其位置号为8、16、32、48、56和和64。其余。其余56位为有效位，用于子密钥计算。将位为有效位，用于子密钥计算。将这这56位送入置换选择位送入置
33、换选择PC1，参看图，参看图4-4-9。经过坐标置换后分。经过坐标置换后分成两组，每级为成两组，每级为28 bit，分别送入，分别送入C寄存器和寄存器和D寄存器中。在各寄存器中。在各次迭代中，次迭代中，C和和D寄存器分别将存数进行左循环移位置换，移寄存器分别将存数进行左循环移位置换，移位次数在表位次数在表4-4-2中给出。每次移位后，将中给出。每次移位后，将C和和D寄存器原存数寄存器原存数送给置换选择送给置换选择PC2，见图，见图4-4-10。置换选择。置换选择PC2将将C中第中第9、18、22、25位和位和D中第中第7、9、15、26位删去，并将其余数字置换位位删去，并将其余数字置换位置后送
34、出置后送出48 bit数字作为第数字作为第i次迭代时所用的子密钥次迭代时所用的子密钥ki。 p.186 p.186 图图4-4-7 置换运算置换运算P 图图4-4-8 子密钥产生器框图子密钥产生器框图 表表4-4-2 移位次数表移位次数表 第第i次迭代次迭代 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 1 p.187 图图4-4-9 置换选择置换选择PC1 至此，我们已将至此，我们已将DES算法的基本构成作了介绍，加密过程可归算法的基本构成作了介绍，加密过程可归结如下：令结如
35、下：令IP表示初始置换，表示初始置换，KS表示密钥运算，表示密钥运算，i为迭代次数为迭代次数变量，变量，KEY为为64 bit密钥，密钥，f为加密函数，为加密函数， 表示逐位模表示逐位模2求和。求和。32 123454567898910 11 12 1312 13 14 15 16 1716 17 18 19 20 2120 21 22 23 24 2524 25 26 27 28 2928 29 30 31 32 1nE变换的算法是从Ri-1的32位中选取某些位，构成48位，即E将32位扩展为48位。变换规则根据E位选择表，如表2-5所示。选择压缩运算选择压缩运算S 6 bit 选择函数组选
36、择函数组 4 bit 48 bit 寄存器32 bit 寄存器S1S2S3S4S5S6S7S8乘积变换乘积变换 置换运算置换运算P P。对对S1至至S8盒输出的盒输出的32 bit数据进行坐数据进行坐标置换，置换标置换，置换P输出的输出的32 bit数据与左边数据与左边32 bit即即Ri-1逐位模逐位模2相加，所得到的相加，所得到的32 bit作为下一轮迭代用作为下一轮迭代用的右边的数字段。并将的右边的数字段。并将Ri-1并行送到左边的寄存器，并行送到左边的寄存器，作为下一轮迭代用的左边的数字段。作为下一轮迭代用的左边的数字段。 子密钥产生器子密钥产生器。将将64 bit初始密钥经过初始密钥
37、经过置换选择置换选择PC1PC1、循环移位置换、置换选择、循环移位置换、置换选择PC2PC2给出每次迭代给出每次迭代加密用的子密钥加密用的子密钥ki，1672021291228171152326518311028241432273919133062211425子密钥产生器框图子密钥产生器框图 密钥（64 bit ）置换选择1，PC1置换选择2，PC2 Ci(28 bit) Di(28 bit) 循环左移ti+1bit 循环左移ti+1bit除去第8,16, ,64位(8个校验位)kiDES的的安全性安全性n互补性互补性。DES算法具有下述性质。若明文组算法具有下述性质。若明文组x逐位取逐位取补
38、，密钥补，密钥k逐位取补，即逐位取补，即y=DESk(x), 则有则有 这种互补性会使这种互补性会使DES在选择明文破译下所需的工在选择明文破译下所需的工作量减半。作量减半。n弱密钥和半弱密钥弱密钥和半弱密钥。DES算法在每次迭代时都有一算法在每次迭代时都有一个子密钥供加密用。如果给定初始密钥个子密钥供加密用。如果给定初始密钥k，各轮的子，各轮的子密钥都相同，即有密钥都相同，即有 k1=k2= =k16 就称给定密钥就称给定密钥k为弱密钥为弱密钥(Weak key)。)(xDESyKDES的的安全性安全性若若k为弱密钥，则有为弱密钥，则有 DESk(DESk(x)=x DESk-1(DESk-
39、1(x)=x 即以即以k对对x加密两次或解密两次都可恢复出明文。其加密加密两次或解密两次都可恢复出明文。其加密运算和解密运算没有区别。运算和解密运算没有区别。 弱密钥下使弱密钥下使DES在选择明文攻击下的搜索量减半。在选择明文攻击下的搜索量减半。 如果随机地选择密钥，弱密钥所占比例极小，而且稍加如果随机地选择密钥，弱密钥所占比例极小，而且稍加注意就不难避开。因此，弱密钥的存在不会危及注意就不难避开。因此，弱密钥的存在不会危及DES的的安全性。安全性。DES的的安全性安全性密文与明文、密文与密钥的相关性密文与明文、密文与密钥的相关性。 Meyer1978详细研究了详细研究了DES的输入明文与密文
40、及密钥与的输入明文与密文及密钥与密文之间的相关性。表明每个密文比特都是所有明文比密文之间的相关性。表明每个密文比特都是所有明文比特和所有密钥比特的复合函数，并且指出达到这一要求特和所有密钥比特的复合函数，并且指出达到这一要求所需的迭代次数至少为所需的迭代次数至少为5。Konheim1981用用 2检验证明，检验证明，迭代迭代8次后输出和输入就可认为是不相关的了次后输出和输入就可认为是不相关的了。DES的的安全性安全性S S盒设计盒设计。 DES靠靠S盒实现非线性变换。盒实现非线性变换。密钥搜索机密钥搜索机。 对对DES安全性批评意见中，较为一致的看法是安全性批评意见中，较为一致的看法是DES的
41、的密钥短了些。密钥短了些。IBM最初向最初向NBS提交的建议方案采用提交的建议方案采用112 bits密钥，但公布的密钥，但公布的DES标准采用标准采用64 bits密钥。有人认密钥。有人认为为NSA故意限制故意限制DES的密钥长度。采用穷搜索对已经的密钥长度。采用穷搜索对已经对对DES构成了威胁构成了威胁DES算法的安全性 nDES算法正式公开发表以后，引起了一场激烈的争论。1977年Diffie和Hellman提出了制造一个每秒能测试106个密钥的大规模芯片，这种芯片的机器大约一天就可以搜索DES算法的整个密钥空间，制造这样的机器需要两千万美元。n1993年R.Session和M.Wien
42、er给出了一个非常详细的密钥搜索机器的设计方案，它基于并行的密钥搜索芯片，此芯片每秒测试5107个密钥，当时这种芯片的造价是10.5美元，5760个这样的芯片组成的系统需要10万美元，这一系统平均1.5天即可找到密钥，如果利用10个这样的系统，费用是100万美元，但搜索时间可以降到2.5小时。可见这种机制是不安全的。nDES的56位短密钥面临的另外一个严峻而现实的问题是：国际互联网Internet的超级计算能力。1997年1月28日，美国的RSA数据安全公司在互联网上开展了一项名为“密钥挑战”的竞赛，悬赏一万美元，破解一段用56位密钥加密的DES密文。n一位名叫Rocke Verser的程序员
43、设计了一个可以通过互联网分段运行的密钥穷举搜索程序，组织实施了一个称为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数据安
44、全会议期间，电子前沿基金会用22小时15分钟就宣告破解了一个DES的密钥。n尽管DES有这样那样的不足，但是作为第一个公开密码算法的密码体制成功地完成了它的使命，它在密码学发展历史上具有重要的地位。二重二重DES 用用DES进行两次加密，但这是否就意味着两重进行两次加密，但这是否就意味着两重DES加密的强度等价于加密的强度等价于112 bit密钥的密码的强度？密钥的密码的强度？答案是否定的。答案是否定的。 中途相遇攻击法中途相遇攻击法(Meet-in-the-Middle Attack) 由由Diffie和和Hellman1977最早提出，可以降低搜最早提出，可以降低搜索量其基本想法如下。若有
45、明文密文对索量其基本想法如下。若有明文密文对(xi,yi)满足满足 yi=Ek2Ek1xi 则可得则可得 z=Ek1xi=Dk2yi 二重二重DES 图图4-14-1 中途相遇攻击示意图中途相遇攻击示意图 zEEDDxiyixizyi k1 k1k2k2中途相遇攻击中途相遇攻击给定一已知明密文对给定一已知明密文对(x1,y1)，可按下述方法攻击。，可按下述方法攻击。n以密钥以密钥k1的所有的所有256个可能的取值对此明文个可能的取值对此明文x1加密，并加密，并将密文将密文z存储在一个表中；存储在一个表中；n从所有可能的从所有可能的256个密钥个密钥k2中依任意次序选出一个对给中依任意次序选出一
46、个对给定的密文定的密文y1解密，并将每次解密结果解密，并将每次解密结果z在上述表中查在上述表中查找相匹配的值。一旦找到，则可确定出两个密钥找相匹配的值。一旦找到，则可确定出两个密钥k1和和k2；n以此对密钥以此对密钥k1和和k2对另一已知明文密文对对另一已知明文密文对(x2, y2)中的明中的明文文x2进行加密，如果能得出相应的密文进行加密，如果能得出相应的密文y2就可确定就可确定k1和和k2是所要找的密钥。是所要找的密钥。中途相遇攻击中途相遇攻击n对于给定明文对于给定明文x，以两重，以两重DES加密将有加密将有264个可能的密文。个可能的密文。n可能的密钥数为可能的密钥数为2112个。所以，
47、在给定明文下，将有个。所以，在给定明文下，将有2112/264 =248个密钥能产生给定的密文。个密钥能产生给定的密文。n用另一对用另一对64bits明文密文对进行检验，就使虚报率降为明文密文对进行检验，就使虚报率降为248-64=2-16。n这一攻击法所需的存储量为这一攻击法所需的存储量为2568 Byte，最大试验的加密，最大试验的加密次数次数2256 =257。这说明破译双重。这说明破译双重DES的难度为的难度为257量级。量级。三重三重DES加密加密加密：加密：y=Ek1Dk2Ek1 x解密：解密：x=Dk1Ek2Dk1yn称其为加密称其为加密-解密解密-加密方案，简记为加密方案，简记
48、为EDE(encrypt-decrypt-encrypt)。n此方案已在此方案已在ANSI X9.17和和ISO 8732标准中采用，并在标准中采用，并在保密增强邮递保密增强邮递(PEM)系统中得到利用。系统中得到利用。n破译它的穷举密钥搜索量为破译它的穷举密钥搜索量为2112 51035量级，而用差量级，而用差分分析破译也要超过分分析破译也要超过1052量级。此方案仍有足够的安全量级。此方案仍有足够的安全性。性。3.3 高级加密标准高级加密标准 AES AES提出提出n1997年年1月，美国月，美国NIST向全世界密码学界向全世界密码学界发出征集发出征集21世纪高级加密标准（世纪高级加密标准
49、（AESAdvanced Encryption Standard）算法）算法的公告，并成立了的公告，并成立了AES标准工作研究室，标准工作研究室，1997年年4月月15日的例会制定了对日的例会制定了对AES的评的评估标准。估标准。n AES的要求（1）AES是公开的；是公开的；（2）AES为单钥体制分组密码；为单钥体制分组密码；（3）AES的密钥长度可变，可按需要增大；的密钥长度可变，可按需要增大；（4）AES适于用软件和硬件实现；适于用软件和硬件实现；（5）AES可以自由地使用，或按符合美国国家可以自由地使用，或按符合美国国家标准（标准（ANST）策略的条件使用；）策略的条件使用；算法衡量条
50、件n满足以上要求的满足以上要求的AES算法，需按下述条算法，需按下述条件判断优劣件判断优劣na. 安全性安全性nb. 计算计算效率效率nc. 内内存要求存要求nd. 使用使用简便性简便性ne. 灵活性。灵活性。AES的评审的评审n 1998年年4月月15日全面征集日全面征集AES算法的工作结束。算法的工作结束。1998年年8月月20日举行了首届日举行了首届AES讨论会，对涉及讨论会，对涉及14个国家的密码个国家的密码学家所提出的候选学家所提出的候选AES算法进行了评估和测试，初选并算法进行了评估和测试，初选并公布了公布了15个被选方案，供大家公开讨论。个被选方案，供大家公开讨论。 CAST-2
