【安全】第78讲--分组密码ppt课件

1、第四章 分组密码王 滨2005年3月14日1明文处置方式分组密码block cipher) 将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出也是固定长度的密文。 流密码stream cipher) 又称序列密码。序列密码每次加密一位或一字节的明文。24.1 分组密码的根本原理 定义1 分组密码就是将明文数据按固定长度进展分组，然后在同一密钥控制下逐组进展加密，从而将各个明文分组变换成一个等长的密文分组的密码。 其中二进制明文分组的长度称为该分组密码的分组规模.m1m2m3mnc1c2c3cn3实现原那么: (1) 必需实现起来比较简单,知道密钥时加密和脱密都非常容易,适宜硬件和(或)

2、软件实现. (2) 加脱密速度和所耗费的资源和本钱较低,能满足详细运用范围的需求. 例: 对高速通讯数据的加密-硬件实现; 嵌入到系统软件的加密程序-软件实现; 智能卡内数据的加密-低本钱实现 4平安性设计原那么 1. 混乱原那么(又称混淆原那么)(Confusion)混乱原那么就是将密文、明文、密钥三者之间的统计关系和代数关系变得尽能够复杂，使得敌手即使获得了密文和明文，也无法求出密钥的任何信息；即使获得了密文和明文的统计规律，也无法求出明文的新的信息。可进一步了解为：1明文不能由知的明文，密文及少许密钥比特代数地或统计地表示出来。2密钥不能由知的明文，密文及少许密钥比特代数地或统计地表示出

3、来。5 2. 分散原那么(Diffusion) 分散原那么就是应将明文的统计规律和构造规律散射到相当长的一段统计中去(Shannon的原话)。 也就是说让明文中的每一位影响密文中的尽能够多的位，或者说让密文中的每一位都遭到明文中的尽能够多位的影响。 假设当明文变化一个比特时,密文有某些比特不能够发生变化,那么这个明文就与那些密文无关,因此在攻击这个明文比比特时就可不利用那些密文比特. 6分组密码的设计方法 采用乘积密码： 即经过将一个弱的密码函数迭代假设干次，产生一个强的密码函数，使明文和密钥得到必要的混乱和分散。 在设计迭代函数时，充分利用替代密码和移位密码各自的优点，抵消各自的缺陷，从而经

4、过多次迭代，构成一个强的分组密码算法。 74.2 DES分组密码算法(Date Encipher Standard) 一、背景简介该算法是在美国NSA国家平安局资助下由IBM公司开发的密码算法，其初衷是为政府非的敏感信息提供较强的加密维护。它是美国政府担保的第一种加密算法，并在1977年被正式作为美国联邦信息处置规范。DES主要提供非军事性质的联邦政府机构和私营部门运用，并迅速成为名声最大，运用最广的商用密码算法。8背景发明人：美国IBM公司 W. Tuchman 和 C. Meyer 1971-1972年研制胜利根底：1967年美国Horst Feistel提出的实际产生：美国国家规范局NB

5、S)1973年5月到1974年8月两次发布通告， 公开征求用于电子计算机的加密算法。经评选从一大批算法中采用 了IBM的LUCIFER方案规范化：DES算法1975年3月公开发表，1977年1月15日由美国国家标 准局公布为数据加密规范Data Encryption Standard，于 1977年7月15日生效9背景美国国家平安局NSA, National Security Agency)参与了美国国家规范局制定数据加密规范的过程。NBS接受了NSA的某些建议，对算法做了修正，并将密钥长度从LUCIFER方案中的128位紧缩到56位1979年，美国银行协会同意运用DES1980年，DES成为

6、美国规范化协会(ANSI)规范1984年2月，ISO成立的数据加密技术委员会(SC20)在DES根底上制定数据加密的国际规范任务10 DES初次被同意运用五年，并规定每隔五年由美国国家严密局作出评价，并重新同意它能否继续作为联邦加密规范。最近的一次评价是在1994年1月，美国已决议1998年12月以后将不再运用DES。由于按照现有的技术程度，采用不到几十万美圆的设备，就可破开DES密码体制。目前的新规范是AES，它是由比利时的密码学家Joan Daemen和Vincent Rijmen设计的分组密码Rijndael荣代尔。111 DES分组密码算法 二、算法概述一根本参数分组加密算法：明文和密

7、文为64位分组长度对称算法：加密和解密除密钥编排不同外，运用同一算法密钥长度：有效密钥56位，但每个第8位为奇偶校验位，可忽略密钥可为恣意的56位数，但存在弱密钥，容易避开采用混乱和分散的组合，每个组合先替代后置换，共16轮只运用了规范的算术和逻辑运算，易于实现12输入64比特明文数据初始置换IP在密钥控制下16轮迭代初始逆置换IP-1输出64比特密文数据DES加密过程13加密框图14置 换定义4.1 ：设S是一个有限集合， 是从S到S的一 个映射。假设对恣意的u，v，当uv 时，(u) (v),那么称是S上的一 个置换。15初始置换与逆初始置换输入和输出比特的序号从左向右编排为1, 2, 3

8、, ,64含义:输出的第1比特是输入的第58比特,该表示方法实现方便.16IP和IP-1IPIP117二加密算法Li32位Ri32位Li-132位Ri-132位fDES的第 i 圈加密构造图Ki18DES加密算的圈函数-属于Feistel模型:Li32位Ri32位Li-132位Ri-132位fDES的圈函数的构造它等价于两个对合变换:Ki19留意无论f函数如何选取，DES的圈函数是一个对合变换。20DES的 F 函数12321 E盒扩展 扩展变换的作用是将输入的32比特数据扩展为48比特数据扩展22 E盒扩展 扩展方式: (1) 将输入的32比特每4比特为一组分为8块; (2)分别将第m-1块

9、的最右比特和第m+1块的最左比特添到第m块的左边和右边,构成输出的第k个6比特块. 主要缘由:硬件实现简单23DES的 F 函数1224紧缩替代S-盒48位紧缩到32位1 2 3 4 5 643 44 45 46 47 48 1 2 3 4 29 30 31 32 25 S盒行和列的序号从0起算。26 S-盒的构造27S-盒的构造要求S-盒是算法的独一非线性部件,因此,它的密码强度决议了整个算法的平安强度提供了密码算法所必需的混乱作用非线性度、差分均匀性、严厉雪崩准那么、可逆性、没有陷门28DES的 F 函数12329 P盒置换将S-盒变换后的32比特数据再进展P盒置换，置换后得到的32比特即

10、为 f 函数的输出。含义:P盒输出的第1个元是输入的第16个元。 根本特点： 1P盒的各输出块的4个比特都来自不同的输入块； 2 P盒的各输入块的4个比特都分配到不同的输出块之中； 3 P盒的第t输出块的4个比特都不来自第t输入块。30 例: 利用DES算法和全0密钥对输入10000001 19600000进展1圈加密的结果。 1输入的右半部分是19600000 = 0001 1001 0110 0000 0000 0000 0000 0000 2经E盒扩展后变为000011 110011 101100 000000 000000 000000 000000 3与全0子密钥模2加后变为0000

11、11 110010 101100 000000 000000 000000 000000 4查S盒后的32比特输出为 f 8 3 7 2 c 4 d1111 1000 0011 0111 0010 1100 0100 1101 5经P盒后得F函数的32比特输出:9cd89aa7= 1001 1100 1101 1000 1001 1010 1010 0111 6将F函数的输入放到左边,将F函数的输出与圈函数的左半输入模2加后放到右边,的圈函数的64比特输出为 19600000 8cd89aa6 31DES中的子密钥的生成32置换选择1：从64比特密钥中取出56个有效比特。置换选择2：从56个密

12、钥比特中取出48个作为子密钥33移位次数意想不到的效果：子密钥存放器的内容经16次迭代后又回到原来的设置。34三脱密算法 脱密构造与加密构造完全一样，只不过是所运用的子密钥的顺序正好相反! 加密子密钥： 脱密子密钥：35DES的加密和脱密变换加密： y=IP-1。fek16 。 D 。 。 D 。 fek2 。 D 。 fek1 。 IP(x)脱密 x=IP-1。fdk16 。 D 。 。 D 。 fdk2 。 D 。 fdk1 。 IP(y)留意(1)加密密钥eki和脱密密钥dki的关系： dki=ek(16-i)(2)最后一圈假设添加交换那么无法正常脱密： y=IP-。D 。fek16 。

13、 D 。 。 D 。 fek2 。 D 。 fek1 。 IP(x) x=IP-。fdk16 。 D 。 。 D 。 fdk2 。 D 。 fdk1 。 D 。 IP(y)36DES分组密码算法小结 (3)根本参数分组长度：64比特密钥长度：64比特有效密钥长度：56比特迭代圈数：16圈每圈子密钥长度：48比特 (4) 编码环节 6进4出的S盒变换逐位模2加变换比特移位变换P盒 (1)密码模型 Feistel模型 (2) F函数模型 S-P网络实现性能: 软件实现慢、硬件实现块；可全部用布尔电路实现比特扩展变换E盒比特抽取变换PC1、PC2和IP37穷举攻击分析 穷举攻击就是对一切能够的密钥逐

14、个进展脱密测试, 直到找到正确密钥为止的一种攻击方法. 穷举攻击判别正确密钥的方法： 将利用实验密钥脱密得到的能够明文与已掌握的明文的信息相比较，并将最吻合的那个实验密钥作为算法输出的正确密钥。 穷举攻击又称为穷尽攻击、强力攻击、蛮干攻击等。只需明文不是随机的，就可实施穷举攻击。38穷举攻击的算法 知条件：知密文c及对应的明文m. Step 1 对每个能够密钥k,计算c=D(k,m),并判别c=c能否成立.不成立时前往Step1检验下一个能够密钥,成立时将k作为候选密钥,并执行Step 2. Step 2 利用其它条件对作k进一步确认.确认经过时输出,算法终止.否那么前往Step1检验下一个能

15、够密钥.39穷举攻击算法的计算复杂性 定理 设密钥在密钥空间K中服从均匀分布，且没有等效密钥,那么穷举攻击平均需求检验完 个密钥后才找到正确密钥。结论: 对DES算法的穷举攻击平均计算复杂性为255.40DES的平安性 F函数(S-Box)设计原理未知 密钥长度的争论 DES的破译 弱密钥与半弱密钥41DES密钥长度关于DES算法的另一个最有争议的问题就是担忧实践56比特的密钥长度缺乏以抵御穷举式攻击，由于密钥量只需 个 早在1977年，Diffie和Hellman已建议制造一个每秒能测试100万个密钥的VLSI芯片。每秒测试100万个密钥的机器大约需求一天就可以搜索整个密钥空间。他们估计制造

16、这样的机器大约需求2000万美圆42DES密钥长度在CRYPTO93上，Session和Wiener给出了一个非常详细的密钥搜索机器的设计方案，这个机器基于并行运算的密钥搜索芯片，所以16次加密能同时完成。破费10万美圆，平均用1.5天左右就可找到DES密钥美国克罗拉多洲的程序员Verser从1997年2月18日起，用了96天时间，在Internet上数万名志愿者的协同任务下，胜利地找到了DES的密钥，博得了悬赏的1万美圆43DES密钥长度1998年7月电子前沿基金会EFF运用一台25万美圆的电脑在56小时内破译了56比特密钥的DES1999年1月RSA数据平安会议期间，电子前沿基金会用22小时1