应用密码学第78讲--分组密码

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第四章 分组密码,1,明文处理方式,分组密码block cipher),将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出也是固定长度的密文。,流密码stream cipher),又称序列密码。序列密码每次加密一位或一字节的明文。,2,4.1 分组密码的根本原理,定义1,分组密码就是将明文数据按,固定长度,进行分组，然后在同一密钥控制下逐组进行加密，从而将各个明文分组变换成一个等长的密文分组的密码。,其中二进制明文分组的长度称为该分组密码的,分组规模,.,m,1,m,2,m,3,m,n,c,1,c,2,c,3,c,n,3,实现原那么:,(1)必须实现起来比较简单,知道密钥时加密和脱密都十分容易,适合硬件和(或)软件实现.,(2)加脱密速度和所消耗的资源和本钱较低,能满足具体应用范围的需要.,例:对高速通信数据的加密-硬件实现;,嵌入到系统软件的加密程序-软件实现;,智能卡内数据的加密-低本钱实现,4,平安性设计原那么,1.混乱原那么(又称混淆原那么)(Confusion),混乱原那么就是将密文、明文、密钥三者之间的统计关系和代数关系变得尽可能复杂，使得敌手即使获得了密文和明文，也无法求出密钥的任何信息；即使获得了密文和明文的统计规律，也无法求出明文的新的信息。,可进一步理解为：,1明文不能由的明文，密文及少许密钥比特代数地或统计地表示出来。,2密钥不能由的明文，密文及少许密钥比特代数地或统计地表示出来。,5,2.扩散原那么(Diffusion),扩散原那么就是应将明文的统计规律和结构规律散射到相当长的一段统计中去(Shannon的原话)。,也就是说让明文中的每一位影响密文中的尽可能多的位，或者说让密文中的每一位都受到明文中的尽可能多位的影响。,如果当明文变化一个比特时,密文有某些比特不可能发生变化,那么这个明文就与那些密文无关,因而在攻击这个明文比比特时就可不利用那些密文比特.,6,分组密码的设计方法,采用乘积密码：,即通过将一个弱的密码函数迭代假设干次，产生一个强的密码函数，使明文和密钥得到必要的混乱和扩散。,在设计迭代函数时，充分利用代替密码和移位密码各自的优点，抵消各自的缺点，从而通过屡次迭代，形成一个强的分组密码算法。,7,4.2,DES,分组密码算法,(,Date Encipher Standard),一、背景简介,该算法是在美国NSA国家平安局资助下由IBM公司开发的密码算法，其初衷是为政府非机密的敏感信息提供较强的加密保护。它是美国政府担保的第一种加密算法，并在1977年被正式作为美国联邦信息处理标准。DES主要提供非军事性质的联邦政府机构和私营部门使用，并迅速成为名声最大，使用最广的商用密码算法。,8,背景,创造人：美国IBM公司 W.Tuchman 和 C.Meyer,1971-1972年研制成功,根底：1967年美国Horst Feistel提出的理论,产生：美国国家标准局NBS)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年，美国银行协会批准使用DES,1980年，DES成为美国标准化协会(ANSI)标准,1984年2月，ISO成立的数据加密技术委员会(SC20)在DES根底上制定数据加密的国际标准工作,10,DES首次被批准使用五年，并规定每隔五年由美国国家保密局作出评估，并重新批准它是否继续作为联邦加密标准。最近的一次评估是在1994年1月，美国已决定1998年12月以后将不再使用DES。因为按照现有的技术水平，采用不到几十万美元的设备，就可破开DES密码体制。目前的新标准是AES，它是由比利时的密码学家Joan Daemen和Vincent Rijmen设计的分组密码Rijndael荣代尔。,11,1,DES,分组密码算法,二、算法概述,一根本参数,分组加密算法：明文和密文为,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,64,含义:,输出的第1比特是输入的第58比特,该表示方法实现方便.,16,IP,和,IP,-1,IP,IP,1,17,二加密算法,L,i,（,32,位）,R,i,（,32,位）,L,i-1,（,32,位）,R,i-1,（,32,位）,f,DES,的第,i,圈加密结构图,K,i,18,DES,加密算的圈函数-,属于,Feistel模型,:,L,i,（,32,位）,R,i,（,32,位）,L,i-1,（,32,位）,R,i-1,（,32,位）,f,DES,的圈函数的结构,它等价于两个对合变换:,K,i,19,注意,无论f函数如何选取，DES的圈函数是一个对合变换。,20,DES,的,F,函数,1,2,3,21,E,盒扩展,扩展变换的作用是将输入的,32,比特数据扩展为,48,比特数据,扩展,22,E,盒扩展,扩展方式:,(1)将输入的,32,比特每4比特为一组分为8块;,(2)分别将第,m-1块的最右比特和第m+1块的最左比特添到第m块的左边和右边,形成输出的第k个6比特块.,主要原因:,硬件实现简单,23,DES,的,F,函数,1,2,24,压缩替代,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-,盒的构造,27,S-,盒的构造要求,S-盒是算法的唯一非线性部件,因此,它的密码强度决定了整个算法的平安强度,提供了密码算法所必须的混乱作用,非线性度、差分均匀性、严格雪崩准那么、可逆性、没有陷门,28,DES,的,F,函数,1,2,3,29,P,盒置换,将,S-,盒变换后的,32,比特数据再进行,P,盒置换，置换后得到的,32,比特即为,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加后变为,000011 110010 101100 000000 000000 000000 000000,4查S盒后的32比特输出为 f 8 3 7 2 c 4 d,1111 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,31,DES,中的子密钥的生成,32,置换选择,1：,从64比特密钥中取出56个有效比特。,置换选择,2,：,从56个密钥比特中取出48个作为子密钥,33,移位次数,意想不到的效果：,子密钥存放器的内容经16次迭代后又回到原来的设置。,34,三脱密算法,脱密结构与加密结构完全相同，只不过是所使用的子密钥的顺序正好相反,!,加密子密钥：,脱密子密钥：,35,DES,的加密和脱密变换,加密：,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。D。D。fek2。D。fek1。IP(x),x=IP-。fdk16。D。D。fdk2。D。fdk1。D。IP(y),36,DES,分组密码算法小结,(3)根本参数,分组长度：64比特,密钥长度：64比特,有效密钥长度：56比特,迭代圈数：16圈,每圈子密钥长度：48比特,(4)编码环节,6,进,4,出的,S,盒变换,逐位模2加变换,比特移位变换,P,盒,(1)密码模型,Feistel模型,(2),F函数模型,S-P网络,实现性能:,软件实现慢、硬件实现块；可全部用布尔电路实现,比特扩展变换,E,盒,比特抽取变换,PC,1,、PC,2,和,IP,37,穷举攻击分析,穷举攻击就是对所有可能的密钥逐个进行脱密测试,直到找到正确密钥为止的一种攻击方法.,穷举攻击判断正确密钥的方法：,将利用试验密钥脱密得到的可能明文与已掌握的明文的信息相比较，并将最吻合的那个试验密钥作为算法输出的正确密钥。,穷举攻击又称为穷尽攻击、强力攻击、蛮干攻击等。只要明文不是随机的，就可实施穷举攻击。,38,穷举攻击的算法,条件：密文c及对应的明文m.,Step 1 对每个可能密钥k,计算c=D(k,m),并判断c=c是否成立.不成立时返回Step1检验下一个可能密钥,成立时将k作为候选密钥,并执行Step 2.,Step 2 利用其它条件对作k进一步确认.确认通过时输出,算法终止.否那么返回Step1检验下一个可能密钥.,39,穷举攻击算法的计算复杂性,定理,设密钥在密钥空间,K,中服从均匀分布，且没有等效密钥,则穷举攻击平均需要检验完 个密钥后才找到正确密钥。,结论:,对,DES,算法的穷举攻击平均计算复杂性为,2,55,.,40,DES的平安性,F,函数(,S-Box),设计原理未知,密钥长度的争论,DES,的,破译,弱密钥与半弱密钥,41,DES,密钥长度,关于DES算法的另一个最有争议的问题就是担忧实际56比特的密钥长度缺乏以抵御穷举式攻击，因为密钥量只有 个,早在1977年，Diffie和Hellman已建议制造一个每秒能测试100万个密钥的VLSI芯片。每秒测试100万个密钥的机器大约需要一天就可以搜索整个密钥空间。他们估计制造这样的机器大约需要2000万美元,42,DES,密钥长度,在,CRYPTO93,上，,Session,和,Wiener,给出了一个非常详细的密钥搜索机器的设计方案，这个机器基于并行运算的密钥搜索芯片，所以,16,次加密能同时完成。花费,10,万美元，平均用,1.5,天左右就可找到,DES,密钥,美国克罗拉多洲的程序员,Verser,从,1997,年,2,月,18,日起，用了,96,天时间，在,Internet,上数万名志愿者的协