《现代密码学课件110讲第7讲》由会员分享，可在线阅读，更多相关《现代密码学课件110讲第7讲（25页珍藏版）》请在金锄头文库上搜索。
1、2019/6/21,1,第四章 分组密码,一、分组密码概述 二、分组密码运行模式 三、DES 四、AES 五、分组密码的分析,2019/6/21,2,三、美国数据加密标准DES（Data Encryption Standard）,2019/6/21,3,美国制定数据加密标准简况,目的 通信与计算机相结合是人类步入信息社会的一个阶梯，它始于六十年代末，完成于90年代初。计算机通信网的形成与发展，要求信息作业标准化，安全保密亦不例外。只有标准化，才能真正实现网的安全，才能推广使用加密手段，以便于训练、生产和降低成本。,2019/6/21,4,美国制定数据加密标准简况,美国NBS在1973年5月15
2、公布了征求建议。1974年8月27日NBS再次出公告征求建议，对建议方案提出如下要求： 算法必须完全确定而无含糊之处； 算法必须有足够高的保护水准，即可以检测到威胁，恢复密钥所必须的运算时间或运算次数足够大； 保护方法必须只依赖于密钥的保密； 对任何用户或产品供应者必须是不加区分的。,2019/6/21,5,美国制定数据加密标准简况,IBM公司在1971年完成的LUCIFER密码 (64 bit分组，代换-置换，128 bit密钥)的基础上，改进成为建议的DES体制 1975年3月17日NBS公布了这个算法，并说明要以它作为联邦信息处理标准，征求各方意见。 1977年1月15日建议被批准为联邦
3、标准FIPS PUB 46，并设计推出DES芯片。 1981年美国ANSI 将其作为标准，称之为DEAANSI X3.92 1983年国际标准化组织(ISO)采用它作为标准，称作DEA-1,2019/6/21,6,美国制定数据加密标准简况,NSA宣布每隔5年重新审议DES是否继续作为联邦标准，1988年（FIPS46-1）、1993年（FIPS46-2），1998年不再重新批准DES为联邦标准。 虽然DES已有替代的数据加密标准算法，但它仍是迄今为止得到最广泛应用的一种算法，也是一种最有代表性的分组加密体制。 1993年4月，Clinton政府公布了一项建议的加密技术标准，称作密钥托管加密技术
4、标准EES(Escrowed Encryption Standard)。算法属美国政府SECRET密级。,2019/6/21,7,美国制定数据加密标准简况,DES发展史确定了发展公用标准算法模式，而EES的制定路线与DES的背道而驰。人们怀疑有陷门和政府部门肆意侵犯公民权利。此举遭到广为反对。 1995年5月AT&T Bell Lab的M. Blaze博士在PC机上用45分钟时间使SKIPJACK的 LEAF协议失败，伪造ID码获得成功。1995年7月美国政府宣布放弃用EES来加密数据，只将它用于语音通信。 1997年1月美国NIST着手进行AES（Advanced Encryption St
5、andard）的研究，成立了标准工作室。2001年Rijndael被批准为AES标准。,2019/6/21,8,DES 算法,分组长度为64 bits (8 bytes) 密文分组长度也是64 bits。 密钥长度为64 bits，有8 bits奇偶校验，有效密钥长度为56 bits。 算法主要包括：初始置换IP、16轮迭代的乘积变换、逆初始置换IP-1以及16个子密钥产生器。,2019/6/21,9,DES算法框图,输入 64 bit明文数据 初始置换IP 乘积变换 （16轮迭代） 逆初始置换IP-1 64 bit密文数据 输出,标准数据加密算法,2019/6/21,10,初始置换IP,将6
6、4 bit明文的位置进行置换，得到一个乱序的64 bit明文组，而后分成左右两段，每段为32 bit，以L0和R0表示，IP中各列元素位置号数相差为8，相当于将原明文各字节按列写出，各列比特经过偶采样和奇采样置换后，再对各行进行逆序。将阵中元素按行读出构成置换输出。 逆初始置换IP-1。将16轮迭代后给出的64 bit组进行置换，得到输出的密文组。输出为阵中元素按行读得的结果。 IP和IP-1在密码意义上作用不大，它们的作用在于打乱原来输入x的ASCII码字划分的关系，并将原来明文的校验位x8, x16, x64变成为IP输出的一个字节。,2019/6/21,11,2019/6/21,12,乘
7、积变换,它是DES算法的核心部分。将经过IP置换后的数据分成32 bit的左右两组，在迭代过程中彼此左右交换位置。 每次迭代时只对右边的32 bit进行一系列的加密变换，在此轮迭代即将结束时，把左边的32 bit与右边得到的32 bit逐位模2相加，作为下一轮迭代时右边的段，并将原来右边未经变换的段直接送到左边的寄存器中作为下一轮迭代时左边的段。 在每一轮迭代时，右边的段要经过选择扩展运算E、密钥加密运算、选择压缩运算S、置换运算P和左右混合运算。,2019/6/21,13,乘积变换,选择扩展运算E。将输入的32 bit Ri-1扩展成48 bit的输出，令s表示E原输入数据比特的原下标，则E
8、的输出是将原下标s0或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。将前面送来的48 bit数据自左至右分成8组，每组为6 bit。而后并行送入8个S一盒，每个S盒为一非线性代换网络，有4个输出，运算S的框图在图4-4-6中给出。 p.186 图4-4-6 选择压缩运算S 置换运算P
9、。对S1至S8盒输出的32 bit数据进行坐标置换，如图4-4-7所示。置换P输出的32 bit数据与左边32 bit即Ri-1逐位模2相加，所得到的32 bit作为下一轮迭代用的右边的数字段。并将Ri-1并行送到左边的寄存器，作为下一轮迭代用的左边的数字段。 子密钥产生器。将64 bit初始密钥经过置换选择PC1、循环移位置换、置换选择PC2给出每次迭代加密用的子密钥ki，参看图4-4-8。在64 bit初始密钥中有8位为校验位，其位置号为8、16、32、48、56和64。其余56位为有效位，用于子密钥计算。将这56位送入置换选择PC1，参看图4-4-9。经过坐标置换后分成两组，每级为28
10、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
11、 2 2 2 2 2 1 p.187 图4-4-9 置换选择PC1 至此，我们已将DES算法的基本构成作了介绍，加密过程可归结如下：令IP表示初始置换，KS表示密钥运算，i为迭代次数变量，KEY为64 bit密钥，f为加密函数，表示逐位模2求和。,2019/6/21,14,选择压缩运算S,6 bit 选择函数组 4 bit,2019/6/21,15,乘积变换,置换运算P。对S1至S8盒输出的32 bit数据进行坐标置换，置换P输出的32 bit数据与左边32 bit即Ri-1逐位模2相加，所得到的32 bit作为下一轮迭代用的右边的数字段。并将Ri-1并行送到左边的寄存器，作为下一轮迭代用的左
12、边的数字段。 子密钥产生器。将64 bit初始密钥经过置换选择PC1、循环移位置换、置换选择PC2给出每次迭代加密用的子密钥ki，,2019/6/21,16,子密钥产生器框图,密钥（64 bit ）,置换选择1，PC1,置换选择2，PC2,Ci(28 bit),Di(28 bit),循环左移ti+1bit,循环左移ti+1bit,除去第8,16, ,64位(8个校验位),ki,2019/6/21,17,DES的安全性,互补性。DES算法具有下述性质。若明文组x逐位取补，密钥k逐位取补，即y=DESk(x), 则有 这种互补性会使DES在选择明文破译下所需的工作量减半。 弱密钥和半弱密钥。DES
13、算法在每次迭代时都有一个子密钥供加密用。如果给定初始密钥k，各轮的子密钥都相同，即有 k1=k2= =k16 就称给定密钥k为弱密钥(Weak key)。,2019/6/21,18,DES的安全性,若k为弱密钥，则有 DESk(DESk(x)=x DESk-1(DESk-1(x)=x 即以k对x加密两次或解密两次都可恢复出明文。其加密运算和解密运算没有区别。 弱密钥下使DES在选择明文攻击下的搜索量减半。 如果随机地选择密钥，弱密钥所占比例极小，而且稍加注意就不难避开。因此，弱密钥的存在不会危及DES的安全性。,2019/6/21,19,DES的安全性,密文与明文、密文与密钥的相关性。 Mey
14、er1978详细研究了DES的输入明文与密文及密钥与密文之间的相关性。表明每个密文比特都是所有明文比特和所有密钥比特的复合函数，并且指出达到这一要求所需的迭代次数至少为5。Konheim1981用2检验证明，迭代8次后输出和输入就可认为是不相关的了。,2019/6/21,20,DES的安全性,S盒设计。 DES靠S盒实现非线性变换。 密钥搜索机。 对DES安全性批评意见中，较为一致的看法是DES的密钥短了些。IBM最初向NBS提交的建议方案采用112 bits密钥，但公布的DES标准采用64 bits密钥。有人认为NSA故意限制DES的密钥长度。采用穷搜索对已经对DES构成了威胁,2019/6
15、/21,21,二重DES,用DES进行两次加密，但这是否就意味着两重DES加密的强度等价于112 bit密钥的密码的强度？答案是否定的。 中途相遇攻击法(Meet-in-the-Middle Attack) 由Diffie和Hellman1977最早提出，可以降低搜索量其基本想法如下。若有明文密文对(xi,yi)满足 yi=Ek2Ek1xi 则可得 z=Ek1xi=Dk2yi,2019/6/21,22,二重DES,图4-14-1 中途相遇攻击示意图,2019/6/21,23,中途相遇攻击,给定一已知明密文对(x1,y1)，可按下述方法攻击。 以密钥k1的所有256个可能的取值对此明文x1加密，并将密文z存储在一个表中； 从所有可能的256个密钥k2中依任意次序选出一个对给定的密文y1解密，并将每次解密结果z在上述表中查找相匹配的值。一旦找到，则可确定出两个密钥k1和k2； 以此对密钥k1和k2对另一已知明文密文对(x2, y2)中的明文x2进行加密，如果能得出相应的密文y2就可确定k1和k2是所要找的密钥。,2019/6/21,24,中途相遇攻击,对于给定明文x，以两重DES加密将有264个可能的密文。 可能的密钥数为2112个。所以，在给定明文下，将有2112/264 =248个密钥能产生给定的密文。 用另一对64bits明文密文对进行检验，就使虚报率降为248-6
