《对称密钥密码》PPT课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,*,对称密钥密码,*,2,对称密钥密码,1,对称密钥密码,对称密钥密码,流密码,(Stream Ciphers),根据一次一密获得,密钥相对较短,密钥被扩展为更长的密钥流(,keystream),Keystream,被用做一次一密的密钥,只用到了混淆,分组密码(,Block cipher),根据电码本密码获得,分组密码密钥决定电码本,每个密钥生成一个不同的电码本,混淆和扩散都得到利用,2,对称密钥密码,流密码,Stream Ciphers,3,对称密钥密码,流密码,现在已不如分组密码流行,本节讨论一种流密码,A5/1,基于线性移位寄存器（硬件实现）,用于,GSM,移动通信系统,4,对称密钥密码,流密码原理,流密码使用,n,比特长的密钥,K,，并将其扩展为更长的密钥流。,将密钥流与明文做异或运算，得到密文,C,。,密钥流的使用方法与一次一密中的密钥相同。,解密时将密文与密钥做异或运算得到明文。,函数可表示为,StreamCipher(K)=S,K,是密钥，,S,是和一次一密中对等的密钥流,5,对称密钥密码,A5/1,原理1,A5/1,使用,3,个线性移位寄存器(,LFSR),寄存器,X,:19 bits(,x,0,x,1,x,2,x,18,),寄存器,Y,:22 bits(,y,0,y,1,y,2,y,21,),寄存器,Z,:23 bits(,z,0,z,1,z,2,z,22,),三个寄存器共有64,bits,密钥,K,采用64,bits,。初始时密钥,K,被载入3个寄存器,6,对称密钥密码,A5/1,原理2,对每一步做,:,m,=major(,x,8,y,10,z,10,),Major,（多数）,函数定义,:major(0,1,0)=0,and major(1,1,0)=1,如果,x,8,=,m,那么,X,寄存器,进行移位运算,t,=,x,13,x,16,x,17,x,18,x,i,=,x,i,1,for,i,=18,17,1 and,x,0,=,t,如果,y,10,=,m,那么,Y,寄存器,进行移位运算,t,=,y,20,y,21,y,i,=,y,i,1,for,i,=21,20,1 and,y,0,=,t,如果,z,10,=,m,那么,Z,寄存器,进行移位运算,t=,z,7,z,20,z,21,z,22,z,i,=,z,i,1,for,i,=22,21,1 and,z,0,=,t,密钥流比特最后由,x,18,y,21,z,22,产生,7,对称密钥密码,A5/1,原理3,每次运算获得一个比特,密钥用于初始化三个寄存器,每个寄存器是否进行移位操作由,M,(,x,8,y,10,z,10,),决定,密钥流比特由三个最右端比特进行,XOR,运算获得,y,0,y,1,y,2,y,3,y,4,y,5,y,6,y,7,y,8,y,9,y,10,y,11,y,12,y,13,y,14,y,15,y,16,y,17,y,18,y,19,y,20,y,21,z,0,z,1,z,2,z,3,z,4,z,5,z,6,z,7,z,8,z,9,z,10,z,11,z,12,z,13,z,14,z,15,z,16,z,17,z,18,z,19,z,20,z,21,z,22,X,Y,Z,x,0,x,1,x,2,x,3,x,4,x,5,x,6,x,7,x,8,x,9,x,10,x,11,x,12,x,13,x,14,x,15,x,16,x,17,x,18,8,对称密钥密码,A5/1,实例,在这种情况下,m,=maj(,x,8,y,10,z,10,),=maj(,1,0,1,)=,1,寄存器,X,进行移位,Y,不进行移位,Z,进行移位,密钥流比特由最右端比特进行,XOR,操作而得,此例,密钥流比特是,0,1 0=1,最后用密钥流和明文做,XOR,运算进行加密和解密,1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1,0,0,0,1,X,Y,Z,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,9,对称密钥密码,流密码总结,密钥流的产生看似很复杂，但用硬件实现很简单,产生速度与计算机时钟速度相当（可与语音同步）,从一个,64,位密钥可产生无穷多密钥流,最终会产生密钥流循环！,10,对称密钥密码,流密码总结,因为过去基于软件的密码系统不能产生高速比特流，流密码曾十分辉煌，当今，基于软件的密码系统的出现，使分组密码成为主流,密码流的未来,?,密码学家,Shamir:“,密码流已步入死亡-,the death of stream ciphers”-2004,或许太夸张,但分组密码是现今主流,11,对称密钥密码,分组密码,Block Ciphers,12,对称密钥密码,(Iterated),分组密码（迭代）,密文和明文均是固定长度的分组(,block),通过若干轮使用轮函数(,round function),迭代产生密文,轮函数的输入由前一轮的输出和密钥组成,分别设计一个安全的分组密码或者一个高速的算法不难，但既安全又高效的算法则非常困难,通常用软件实现,13,对称密钥密码,Feistel,密码,(Cipher),Feistel,密码,是分组密码的一种,(,分组,),原则，不是一种特殊的密码,将明文分解成右半部分和左半部分,:,明文,=,(L,0,R,0,),对于每一轮,i=1,2,.,n,计算：,L,i,=R,i,1,R,i,=L,i,1,F(R,i,1,K,i,),此处,F,是,轮函数,K,i,是第,i,轮的 子密钥,(subkey),密文,=,(L,n,R,n,),14,对称密钥密码,Feistel,密码解密,解密,:,密文,=,(L,n,R,n,),对每轮,i=n,n,1,1,计算,R,i,1,=L,i,L,i,1,=R,i,F(R,i,1,K,i,),此处,F,是,轮函数,K,i,是第,i,轮的 子密钥,subkey,明文,=,(L,0,R,0,),此算法对所有函数,F,都适用,但只对特定函数来说是安全的,优点在于所有安全性问题可以转化为轮函数,F,的问题,15,对称密钥密码,DES,密码,20,世纪,70,年代提出,DES(Data Encryption Standard),根据,IBM,公司提出,Feistel,密码之一的,Lucifer,密码设计,当时，密码技术除被政府和军方所研究及掌握，民间及商业对此尚无研究,但计算机的发展，数据加密对商业至关重要,美国标准局,(NBS),提出了对密码算法的征集,获胜者将成为美国政府及实际上的产业界标准,因参与者不多，最终由唯一,IBM,提出的,Lucifer,算法获得,16,对称密钥密码,DES,密码,由于技术力量不足，,NBS,求助于政府密码机构,NSA(National Security Agency),由于,NSA,专门负责政府及军方高级敏感信息加密研究，开始不愿参与民间密码开发,后被怀疑在,DES,中植入后门，使,NSA,很容易破解,DES,Lucifer,算法经过修改成为,DES,主要修改为将密钥长度由,128,位减为,64,位，并且,64,位中有,8,位势用来校验奇偶性的，实际密钥长度由为,56,。破译难度降低了,2,72,倍，难怪被指动过手脚,17,对称密钥密码,DES,密码归纳,DES,是,16,轮的,Feistel,结构密码,DES,的分组长度是,64,位,DES,使用,56,位密钥,DES,每一轮使用,48,位的子密钥，每个子密钥是由,56,位的密钥的子集构成的,DES,竟是住了时间的考验，其遭受攻击只是因为密钥过短，而不是存在比穷举更为有效的攻击方法,18,对称密钥密码,DES,的分析,DES,是一种,Feistel,原理的密码系统（将明文分为两部分，然后迭代）,64,位为一个分段,56,位长的密钥,经过,16,论迭代,每步迭代采用,48,位长的子密钥,(?),每步迭代很简单,安全性主要取决于,“S,盒,”,每个,S,盒将,6,位映射为,4,位,19,对称密钥密码,L,R,扩展,移位,移位,密钥,密钥,S,盒,压缩,L,R,28,28,28,28,28,28,48,32,48,32,32,32,32,DES,的一轮,48,32,K,i,P,置换,20,对称密钥密码,DES,的扩展组合,输入,32,位,(,图中,L,、,R),0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1516,16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 3116,输出,48,位,(,经过扩展）,31 0 1 2 3 4,3 4,5 6 7 812,7 8 9 10 11 12,11 12,13 14 15 1612,15 16 17 18 19 20,19 20,21 22 23 2412,23 24 25 26 27 28,27 28,29 30 31 012,21,对称密钥密码,DES,的,S,盒,8,个,S,盒,每个,S,盒将,6,位输入映射到,4,位输出,下图为,1,号,S,盒,输入,bits(0,5),确定列数,输入,bits(1,2,3,4),确定行数,|0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111,-,00|1110 0100 1101 0001 0010 1111 1011 1000 0011 1010 0110 1100 0101 1001 0000 0111,01|0000 1111 0111 0100 1110 0010 1101 0001 1010 0110 1100 1011 1001 0101 0011 1000,10|0100 0001 1110 1000 1101 0110 0010 1011 1111 1100 1001 0111 0011 1010 0101 0000,11|1111 1100 1000 0010 0100 1001 0001 0111 0101 1011 0011 1110 1010 0000 0110 1101,矩阵中的四位输出是,0,，,1,2,F,的某种置换排列。,22,对称密钥密码,DES,的,P,置换,输入,32,位,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15,16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31,输出,32,位,15 6 19 20 28 11 27 16 0 14 22 25 4 17 30 9,1 7 23 13 31 26 2 8 18 12 29 5 21 10 3 24,P,置换并非出于安全性考虑，至今仍被认为是一个历史谜团，一个可能的解释是使算法难以用软件实现,(,当初使用的是特殊硬件,),。,23,对称密钥密码,DES,的子密钥,56,位的,DES,密钥,序号,0,1,2,55,左半部分密钥比特,LK(28bit),49 42 35 28 21 14 7,0 50 43 36 29 22 15,8 1 51 44 37 30 23,16 9 2 52 45 38 31,右半部分密钥比特,RK(28bit),55 48 41 34 27 20 13,6 54 47 40 33 26 19,12 5 53 46 39 32 25,18 11 4 24 17 10 3,24,对称密钥密码,DES,的子密钥,子密钥的产生式一个循环过程，该过程是安全性的关键。最终结果是选择,56,位中的,48,位成为子密钥。,对于,i=1,2,.,16,轮,赋值,LK=(LK,循环左移位,r,i,位,),赋值,RK=(RK,循环左移位,r,i,位,),左半部分的子密钥,K,i,是,LK