DES的安全性密文和明文教育课件.ppt

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