计算机系统信息安全

南京大学计算机系黄皓教授2013年9月17日开场白——一个电话骗局中央电视台《今日说法》报道南京大学计算机系讲义一个电话欺骗(中央电视台今日说法)第1幕—在火车站一个计划到上海的给孩子看病的旅客到达了上海站.
他到公用电话处,拿起电话听筒,拨打在上海的亲戚的电话.
旅客:"喂,是表哥吗"听筒传出:"是,你到了很不巧,因为交通堵塞,我还没有到车站.
你们到人民路的人民商场门口,我到那里接你吧.
"旅客:"好.
"南京大学计算机系讲义一个电话欺骗(中央电视台今日说法)第2幕—在人民商场门口旅客在人民商场的门口等待.
一个中年人向正在等待的旅客走来.
"我是你表哥委托来接你们的.
"交谈后,在准备回表哥家时:中年人:"我刚才在前面一个商店看到了我要一直想买的非常紧俏的相机,今天好不容易看到了,但是我没有带够钱,你们身上有钱吗借给我一点,回去马上给你.
""你要多少""三千""好"你们稍等,我马上回来.
几个警察迅速抓住了这个快速离开的中年人.
旅客过去跟警察说:"这是我表哥的朋友,你抓错人了吧"南京大学计算机系讲义骗子设法知道公用电话的号码.
不断拨这个公用电话的号码.
拨通后等待别人:拿听筒、不听是否拨号音就直接拨电话的人.
骗子可以听到,"鱼儿"的拨号的键盘音.
等待他/她的开始说话.
拿起听筒(这时实际已经通了),拨号(没有实际作用),"喂,是表哥吗""好.
""你要多少""好""是,你到了很不巧,因为交通堵塞,我还没有到车站.
你们到人民路的人民商场门口,我到那里接你吧.
""我刚才在前面一个商店看到了我要买的,但是我没有带够钱,你们身上有钱吗借给我一点,回去马上给你.
""你们稍等,我马上回来.
""三千"骗子用的电话公用电话拨公用电话,等待"鱼儿"拿起听筒…南京大学计算机系讲义62013/10/15课程内容1.
对称密码学2.
非对称密码学3.
密码协议4.
公开密钥基础设施5.
安全模型6.
安全操作系统7.
安全数据库8.
IP安全9.
Web安全10.
安全电子交易11.
安全邮件12.
网络防火墙技术13.
入侵检测技术14.
安全评估技术南京大学计算机系讲义72013/10/15参考书1.
讲稿和各章讲稿所列的参考文献2.
WenboMao(毛文波),现代密码学理论与实践,电子工业出版社,2004年7月.
3.
王立斌,黄征译,计算机安全学—安全的艺术与科学,电子工业出版社,2005年5月.
4.
AllenHarper,ShonHarris等著,杨明军,韩智文,程文俊译,灰帽黑客,清华大学出版社,2012年11月,第1版.
第1章对称密码学南京大学计算机系讲义92013/10/15参考文献1.
WenboMao(毛文波),现代密码学理论与实践,电子工业出版社,2004年7月.
2.
吴文玲,冯登国,张文涛,分组密码的设计与分析,清华大学出版社,2009年10月.
3.
冯登国,密码分析学,清华大学出版社,2000年8月.
4.
BruceChneier,应用密码学,机械工业出版社,2000年1月.
南京大学计算机系讲义102013/10/15一个例子问题两个朋友Alice和Bob想一起外出,但是他们定不下来是去电影院还是歌剧院.
他们达成一个通过抛掷硬币来决定的协议:Alice说:"你选择一面,然后我来抛".
他们约定:如果Bob选择的一面朝上则有Bob决定,否则有Alice决定.
假想这两个朋友尝试再电话上执行这个协议,如果Alice对Bob说:"你选则一面,然后我来抛,并且告诉你是否你赢了".
南京大学计算机系讲义112013/10/15一个例子单向函数对任意整数x,由x计算f(x)是容易的,而给出f(x),要找出对应的原像x是不可能的,不管x是奇数还是偶数.
不可能找出一对整数(x,y),满足x≠y且f(x)=f(y).
南京大学计算机系讲义122013/10/15一个例子协议Alice和Bob已经同意:有一个单向函数ff(x)中的偶数x代表"正面",奇数x代表"背面"①Alice选择一个大随机数x并计算f(x),然后通过电话告诉Bobf(x)的值;②Bob告诉Alice自己对x的奇偶性猜测;③Alice告诉Bobx的值;④Bob验证f(x),并察看他所做的猜测是正确或错误.
只能是猜测,因为f(x)是单向向函数,无法从函数值计算自变量.
Alice只能如实告诉,因为Alice无法找到另一个值y(奇偶性与x不同),f(y)=f(x).
南京大学计算机系讲义132013/10/15一个例子安全性首先,Alice无法找到不同的两个数x和y,其中一个是奇数而另一个是偶数,使其满足f(x)=f(y).
因此,Alice一旦通过电话告诉Bob,f(x)的值(第1步),她也就向Bob就x的值做出了承诺,她无法再改变x的值.
也就是说Alice已经完成了其掷硬币过程.
第二,由于,已知f(x),Bob不能判定出Alice所使用的x是奇数还是偶数,因周而他不得不把其猜测(第2步)真实地给出.
这样,Alice可给出x的值,令Bob相信其猜测是否正确(第3步).
如果Bob利用Alice告诉的x来计算对f(x)(第4步),并与Alice在第1步发送的结果一样,且Bob相信f所具有的性质,则Bob应该相信最终的输赢.
南京大学计算机系讲义142013/10/151.
基本概念—术语消息被称为明文(plaintext).
用某种方法伪装消息以隐藏它的内容的过程称为加密(encryption,encipher).
加了密的消息称为密文(ciphertext).
而把密文转变为明文的过程称为解密(decryption,decipher).
南京大学计算机系讲义152013/10/151.
基本概念—术语使消息保密的技术和科学叫做密码编码学(cryptography).
从事此行的叫密码编码者(cryptographer).
破译密文的科学和技术叫做密码分析学(cryptanalysis).
从事密码分析的专业人员叫做密码分析者(cryptanalyst).
密码学包括密码编码学和密码分析学两者.
现代的密码学家通常也是理论数学家.
南京大学计算机系讲义162013/10/151.
基本概念—密码学的其它作用鉴别消息的接收者应该能够确认消息的来源;入侵者不可能伪装成他人.
完整性消息的接收者应该能够验证在传送过程中消息没有被修改;入侵者不可能用假消息代替合法消息.
抗抵赖发送者事后不可能虚假地否认他发送的消息.
南京大学计算机系讲义172013/10/151.
基本概念—算法和密钥密码算法也叫密码,是用于加密和解密的数学函数.
通常情况下,有两个相关的函数:一个用作加密,另一个用作解密.
明文用M(消息),密文用C表示,加密函数E作用于M得到密文C,用数学表示为:E(M)=C.
相反地,解密函数D作用于C产生MD(C)=M.
先加密后再解密消息,原始的明文将恢复出来,下面的等式必须成立:D(E(M))=M南京大学计算机系讲义182013/10/151.
基本概念—受限制的算法如果算法的保密性是基于保持算法的秘密,这种算法称为受限制的算法.
如果有人无意暴露了这个秘密,所有人都必须改变他们的算法.
南京大学计算机系讲义192013/10/151.
基本概念—现代密码学现代密码学用密钥解决了这个问题,密钥用K表示.
密钥K的可能值的范围叫做密钥空间.
加密和解密运算都使用这个密钥,加/解密函数现在变成:EK1(M)=CDK2(C)=MDK2(EK1(M))=MEK(M)=CDK(C)=MDK(EK(M))=M南京大学计算机系讲义202013/10/151.
基本概念—对称算法和非对称算法对称算法加密密钥能够从解密密钥中推算出来,反过来也成立.
公开密钥算法公开密钥算法用作加密的密钥不同于用作解密的密钥,而且解密密钥不能根据加密密钥计算出来.
南京大学计算机系讲义212013/10/151.
基本概念—密码分析密码分析学是在不知道密钥的情况下.
恢复出明文的科学.
对密码进行分析的尝试称为攻击.
密码分析的一个基本假设:密码分析者已有密码算法及其实现的全部详细资料.
在实际的密码分析中并不总是有这些详细信息的应该如此假设.
如果其他人不能破译算法,即便了解算法如何工作也是徒然,如果连算法的知识都没有,那就肯定不可能破译它.
南京大学计算机系讲义222013/10/15(1)唯密文攻击密码分析者有一些消息的密文这些消息都用同一加密算法加密密码分析者的任务是恢复尽可能多的明文或者最好是能推算出加密消息的密钥来已知:C1=EK(P1),C2=EK(P2),,推导出:P1,P2,,南京大学计算机系讲义232013/10/15(2)已知明文攻击密码分析者不仅可得到一些消息的密文,而且也知道这些消息的明文.
分析者的任务就是用加密信息推出用来加密的密钥或导出一个算法,此算法可以对用同一密钥加密的任何新的消息进行解密.
已知:P1,C1=Ek(P1),P2,C2=Ek(P2),,Pi,Ci=Ek(Pi)推导出:密钥k,或从Ci+1=Ek(Pi+1)推出Pi+1的算法.
南京大学计算机系讲义242013/10/15(3)选择明文攻击分析者不仅可得到一些消息的密文和相应的明文,而且他们也可选择被加密的明文.
这比已知明文攻击更有效.
因为密码分析者能选择特定的明文块去加密,那些块可能产生更多关于密钥的信息,分析者的任务是推出用来加密消息的密钥或导出一个算法,此算法可以对用同一密钥加密的任何新的消息进行解密.
南京大学计算机系讲义252013/10/15(4)选择密文攻击密码分析者能选择不同的被加密的密文,并可得到对应的解密的明文,例如密码分析者存取一个防窜改的自动解密盒,密码分析者的任务是推出密钥.
选择:C1,P1=Dk(C1),C2,P2=Dk(C2),,Ci,Pi=Dk(Ci),推导出:k.
南京大学计算机系讲义262013/10/15最好的算法是那些已经公开的,并经过世界上最好的密码分析家们多年的攻击,但还是不能破译的算法.
美国国家安全局对外保持他们的算法的秘密,但他们有很好的密码分析家在内部工作,他们互相讨论他们的算法,通过执著的审查发现他们工作中的弱点.
南京大学计算机系讲义272013/10/151.
基本概念—密码学目标机密性完整性认证不可抵赖性、公证性南京大学计算机系讲义282013/10/152.
古典密码算法在计算机出现前,密码学由基于字符的密码算法构成.
不同的密码算法是字符之间互相代换或者是互相之间换位,好的密码算法是结合这两种方法,每次进行多次运算.
现在事情变得复杂多了,但原理还是没变.
重要的变化是算法对比特而不是对字母进行变换,实际上这只是字母表长度上的改变,从26个元素变为2个元素.
大多数好的密码算法仍然是代替和换位的元素组合.
南京大学计算机系讲义292013/10/15密码体制P:所有可能的明文组成的有限集.
;C:所有可能的密文组成的有限集;K:所有可能的密钥组成的有限集;对任意的k∈K,都存在一个加密法则ek∈E和相应的解密法则dk∈D,满足:对任意的ek:P→C,dk:C→P,明文x∈P,均有dk(ek(x))=x密码体制:(P,C,K,E,D)南京大学计算机系讲义302013/10/152.
1移位密码令P=C=K=Z26.
对0≤k≤25,x,y,k∈Z26,定义ek(x)=x+kmod26dk(y)=y-kmod26这里a对应0记为af、b对应1记为bf、……、z对应25记为zf;两个字母的运算x+kmod26表示xf+kfmod26所对应的字母.
著名的凯撒密码就是一种移位密码,k=3;移位密码的密钥数量为25.
ABCDEFGHIJKLMNOPQRSTUVWXYZDEFGHIJKLMNOPQRSTUVWXYZABC南京大学计算机系讲义312013/10/152.
2代换(substitution)密码单表代换令P=C=K=Z26.
K由在有限集{0,1,…,25}上所有的置换π组成.
对任意的K,定义:eπ(x)=π(x)dπ(y)=π-1(y)密钥的数量为26!
-1≈7.
21*1026著名的DES算法的密钥数量为256≈7.
21*1016南京大学计算机系讲义322013/10/15字母频率表字母概率字母概率字母概率字母概率A0.
082H0.
061O0.
075W0.
023B0.
015I0.
070P0.
019X0.
001C0.
028J0.
002Q0.
001Y0.
020D0.
043K0.
008R0.
060Z0.
001E0.
127L0.
040S0.
063F0.
022M0.
024T0.
091G0.
020N0.
067U0.
028南京大学计算机系讲义332013/10/15单表代替密码的缺点在单表代替下字母的频度、重复字母模式、字母结合方式等统计特性除了字母名称改变以外,都未发生变化,依靠这些不变的统计特性就能破译单表代换;南京大学计算机系讲义342013/10/152.
2多表代替密码Vigenere密码是由法国密码学家BlaisedeVigenere于1858年提出的一种密码,它是一种以移位代换为基础的周期代换密码.
设m是一个整数.
定义P=C=K=(Z26)m.
对任意的密钥K=(k1,k2,…,km),定义ek(x1,x2,…,xm)=(x1+k1,x2+k2,…,xm+km)dk(y1,y2,…,ym)=(y1-k1,y2-k2,…,ym-km)南京大学计算机系讲义352013/10/15多表代替密码的例子例1设m=6,K=cipher,明文串:thiscryptosystemisnotsecurex=(19,7,8,18,2,17,24,15,19,14,18,24,18,19,4,12,8,18,13,14,19,18,4,2,20,1,4).
密钥:k=(2,8,15,7,4,17):cipher南京大学计算机系讲义362013/10/151978182172415192815741728152115232568023814182418194128187417281574172122152011919129131419184220142815741728151522825819222519密文串为:VPXZGIAXIVWPUBTTMJPWIZITWZT南京大学计算机系讲义372013/10/15多表代替密码的优点在多表代换下,原来明文中的统计特性通过多个表的平均作用而被隐蔽了起来.
多表代换密码的破译要比单表代替密码的破译难得多.
南京大学计算机系讲义382013/10/15多表代替密码的破解(1)1863年,普鲁士军官F.
Kasiski发明了通过分析密文中的字母重复的情况来确定周期多表代替密码的准确周期的方法.
例:密钥:dog,明文:tobeornottobetobeornottobedogdogdogdogdwchhcxqczwchh南京大学计算机系讲义392013/10/15多表代替密码的破解(2)在密文中字符串wchh重复了两次,其间个为9个字符.
这个距离是密钥长度的倍数,可能的密钥长度是1,3,9.
判定了长度之后就可以用频率分析法来破译各个单表代替密码了.
多表代替密码的破解的原因:密钥的长度太短.
南京大学计算机系讲义402013/10/15密钥字长度的确定—重合指数法设x=x1x2.
.
.
.
.
.
xn,x的重合指数定义为x中两个随机字母相同的概率,记为Ic(x).
n是总的字母数,fi是第i个字母出现的次数,i=0,…,25.

25252525200c00(1)21I(x)0.
065(1)12iiiiiiiiiifffffnnnnnp假定Y=y1y2…yn是多表密码算法加密后的密文,如果猜测密钥的长度是d,则将Y分成d个密文子串:Y1=y1yd+1y2d+1,Y2=y2yd+1y2d+1…Yd=ydy2dy2d…如果d为密钥字的长度,则Yi的重合指数≈0.
065如果d不是密钥字长度,则Yi的由完全随机的字母组成,所以重合指数Ic(zi)=26/262≈0.
038如果取出的两个字母都是第i个字母,有种2可能.
南京大学计算机系讲义412013/10/15密钥字的确定—重合互指数法假定x=x1x2…xn,y=y1y2…ym,x和y的互指数定义为从x中随机取一个字母和从y中随机取的一个字母相同的概率,记为:MIc(x,y).
如果在x和y中a,b,….
,z出现的次数分别为f0,f1,…,f25和g0,g1,…,g25,则25c0MI(x,y)iiifgnm南京大学计算机系讲义422013/10/15密钥字的确定—重合互指数法假定Y=y1y2…yn是多表密码算法加密后的密文,将Y分成d个密文子串:Y1,Y2,…,Yd,.
考虑Yi中的一个随机字母和Yj中的一个随机字母,两个字母都是A和B的概率分别是11,ijijkkkkpppp我们可以得到:可以看出,MIc(x,y)的估计值只依赖于(ki-kj)mod26,称这个差为Yi与Yj的相对位移.
试验表明相对位移不等于0时,这些估计值在0.
031到0.
045之间,相对位移等于0时,估计值为0.
065.
这里假定在英文文件中,字母A出现的概率是p0,B出现的概率是p1,……,z出现的概率是p25,p-1=p25,p-2=p24,…….
上式中的加减法运算取模mod26.
密文字母A是由密钥ki加密得到的,字母编号0,那么相应的明文字母编号就是-ki.
因此密文字母A出现的概率是p-ki,密文字母B出现的概率是p-kj250250),(hhkkhhkhkhjijijippppYYMIc密钥字的确定—重合互指数法固定Yi,考虑长度为d的密钥字ei=(i,i,……,i),i=0,…25.
用密钥字ei加密Yj,分别得到Yji,i=0,……,25.
计算MIc(Yi,Yjk),0≤k≤25.
当k等于Yi与Yj的相对误差的时候,MIc(Yi,Yjk)的值接近于0.
065.
重合互指数为0.
065的K值就是Yi与Yj的相对误差.
南京大学计算机系讲义432013/10/15南京大学计算机系讲义442013/10/15密钥字的确定—重合互指数法设k=(k1,k2,…,km)为密钥字;固定Y1(k1),猜测ki-k1的差;最后猜测k1.
冯登国,密码分析学,清华大学出版社,1.
4节.
作业编写一个破解程序,完成下列工作之一:1.
猜测密钥长度,用明文字母频率破解密钥.
2.
用重合指数法破解密钥字长度.
3.
用重合互指数法破解密钥.
南京大学计算机系讲义第45页共173页2013/10/15南京大学计算机系讲义462013/10/152.
3置换密码置换:定义在有限集X上的置换为一个双射函数π:X→X.
π-1定义为π的逆函数π(x)=x',π-1(x')=x令m为一整数.
P=C=(Z26)m,K由定义在集合{1,2,…,m}上的置换组成.
对于任意的密钥π(置换),定义加密eπ(x1,x2,…,xm)=(xπ(1),xπ(2),…,xπ(m))dπ(y1,y2,…,ym)=(yπ-1(1),yπ-1(2),…,yπ-1(m))置换密码与替代密码的区别替代密码的明文字母集合与密文字母集合往往是不同的.
置换密码明文字母集合与密文字母集合完全相同.
南京大学计算机系讲义472013/10/15Enigma——诞生直到第一次世界大战结束为止,所有密码都是使用手工来编码的,就是铅笔加纸的方式.
考虑到不能多次重复同一种明文到密文的转换方式,和民用的电报编码解码不同,加密人员并不能把转换方式牢记于心.
转换通常是采用查表的方法,所查表又每日不同,所以解码速度极慢.
南京大学计算机系讲义482013/10/15Enigma—诞生解密一方当时正值春风得意之时,几百年来被认为坚不可破的维吉耐尔(Vigenere)密码和它的变种也被破解.
而无线电报的发明,使得截获密文易如反掌.
无论是军事方面还是民用商业方面都需要一种可靠而又有效的方法来保证通讯的安全.
南京大学计算机系讲义492013/10/15Enigma—诞生1918年,德国发明家亚瑟·谢尔比乌斯(ArthurScherbius)和他的朋友理查德·里特(RichardRitter)创办了谢尔比乌斯和里特公司.
这是一家专营把新技术转化为应用方面的企业,很象现在的高新技术公司.
谢尔比乌斯负责研究和开发方面,紧追当时的新潮流.
他的一个想法就是要用二十世纪的电气技术来取代那种过时的铅笔加纸的加密方法.
南京大学计算机系讲义502013/10/15Enigma—诞生谢尔比乌斯发明的加密电子机械名叫ENIGMA,在以后的年代里,它将被证明是有史以来最为可靠的加密系统之一而对这种可靠性的盲目乐观,又使它的使用者遭到了灭顶之灾.
南京大学计算机系讲义512013/10/15Enigma—原理ENIGMA它可以被分解成相当简单的几部分.
下面的图是它的最基本部分的示意图,我们可以看见它的三个部分:键盘、转子和显示器.
南京大学计算机系讲义522013/10/15Enigma—原理不用的转子或转子在不同的位置给出不同的替代.
南京大学计算机系讲义532013/10/15Enigma—原理照片左方是一个完整的转子右方是转子的分解,我们可以看到安装在转子中的电线南京大学计算机系讲义542013/10/15Enigma—原理当第一个转子转动整整一圈以后,它上面有一个齿拨动第二个转子,使得它的方向转动一个字母的位置.
南京大学计算机系讲义552013/10/15Enigma—原理在此基础上谢尔比乌斯十分巧妙地在三个转子的一端加上了一个反射器,而把键盘和显示器中的相同字母用电线连在一起.
反射器和转子一样,把某一个字母连在另一个字母上,但是它并不转动.
这么一个固定的反射器它并不增加可以使用的编码数目.
它和解码联系起来了:按下密文字母,明文字母会亮.
南京大学计算机系讲义562013/10/15Enigma—加密与解密过程加密1.
发信人首先要调节三个转子的方向,使它们处于26*26*26=17576个方向中的一个(事实上转子的初始方向就是密钥,这是收发双方必须预先约定好的)2.
依次键入明文,并把闪亮的字母依次记下来作为密文字母.
3.
然后就可以把加密后的消息用比如电报的方式发送出去.
解密1.
当收信方收到电文后,使用一台相同的ENIGMA,按照原来的约定,把转子的方向调整到和发信方相同的初始方向上.
2.
依次键入收到的密文,并把闪亮的字母依次记下来,就得到了明文.
南京大学计算机系讲义572013/10/15Enigma—密钥当然谢尔比乌斯还可以再多加转子,但是我们看见每加一个转子初始方向的可能性只是乘以了26.
尤其是,增加转子会增加ENIGMA的体积和成本.
谢尔比乌斯希望他的加密机器是便于携带的;首先他把三个转子做得可以拆卸下来互相交换,这样一来初始方向的可能性变成了原来的六倍.
26*26*26*6=105,456.
南京大学计算机系讲义582013/10/15Enigma—密钥键盘和第一转子之间增加了一个连接板下一步谢尔比乌斯在键盘和第一转子之间增加了一个连接板.
这块连接板允许使用者用一根连线把某个字母和另一个字母连接起来,这样这个字母的信号在进入转子之前就会转变为另一个字母的信号.
这种连线最多可以有6对(后期的ENIGMA具有更多的连线),这样就可以使6对字母的信号互换,其他没有插上连线的字母保持不变.
当然连接板上的连线状况也是收发信息的双方需要预先约定的.
连接板上两两交换6对字母的可能性数目非常巨大,有100391791500种密钥连接板的连接:A/L-P/R-T/D-B/W-K/F-O/Y转子的顺序:2,3,1转子的初始方向:Q-C-W连接板,可以选择若干对互换连接.
南京大学计算机系讲义592013/10/15Enigma—密钥—会话密钥调整好ENIGMA,现在操作员可以开始对明文加密了.
但是我们看到每天只有一个密钥,如果这一天的几百封电报都以这个密钥加密发送的话,暗中截听信号的敌方就会取得大量的以同一密钥加密的信息,这对保密工作来说不是个好兆头.
我们记得在简单替换密码的情况下,如果密码分析专家能得到大量的密文,就可以使用统计方法将其破解.
南京大学计算机系讲义602013/10/15Enigma—密钥—会话密钥尽管不知道对ENIGMA是否可以采用类似的统计方法,德国人还是留了个心眼.
他们决定在按当日密钥调整好ENIGMA机后并不直接加密要发送的明文.
首先发送的是一个新的密钥.
连接板的连线顺序和转子的顺序并不改变,和当日通用的密钥相同;然后将转子的初始方向按照新密钥来设置.
操作方法(1)操作员首先按照上面所说的方法按当日密钥调整好ENIGMA(2)然后随机地选择三个字母,比如说PGH.
(3)把PGH在键盘上连打两遍,加密为比如说KIVBJE(第一次KIV,第二次BJE).
(4)然后他把KIVBJE记在电文的最前面.
接着他重新调整三个转子的初始方向到PGH,然后才正式对明文加密.
发送的报文EMasterKey(SessionKey||SessionKey)||ESessionKey(Text)南京大学计算机系讲义612013/10/15Enigma—被攻击的原因(1)—管理汉斯—提罗·施密特(Hans-ThiloSchimdt)于1888年出生在柏林的一个中产阶级家庭里,一次大战时当过兵打过仗.
根据凡尔赛条约,战败后的德国进行了裁军,施密特就在被裁之列.
退了伍后他开了个小肥皂厂,心想下海从商赚点钱.
结果战后的经济萧条和通货膨胀让他破了产.
此时他不名一文,却还有一个家要养.
南京大学计算机系讲义622013/10/15Enigma—被攻击的原因(1)—管理鲁道夫给他的二弟在密码处(Chiffrierstelle)找了个位置.
这是专门负责德国密码通讯的机构——ENIGMA的指挥中心,拥有大量绝密情报.
汉斯—提罗把一家留在巴伐利亚,因为在那里生活费用相对较低,勉强可以度日.
就这样他一个人孤零零地搬到了柏林,拿着可怜的薪水,对大哥又羡又妒,对抛弃他的社会深恶痛绝.
南京大学计算机系讲义632013/10/15Enigma—被攻击的原因(1)—管理接下来的事情可想而知.
如果把自己可以轻松搞到的绝密情报出卖给外国情报机构,一方面可以赚取不少自己紧缺的钱,一方面可以以此报复这个抛弃了他的国家.
1931年11月8日,施密特化名为艾斯克(Asche)和法国情报人员在比利时接头,在旅馆里他向法国情报人员提供了两份珍贵的有关ENIGMA操作和转子内部线路的资料,得到一万马克.
靠这两份资料,盟国就完全可以复制出一台军用的ENIGMA机.
南京大学计算机系讲义642013/10/15Enigma—波兰人的破解(使用方法)在此以前,密码分析人员通常是语言天才,精通对语言方面特征的分析.
但是既然ENIGMA是一种机械加密装置,波兰总参二局密码处就考虑到,是否一个具有科学头脑的人更适合于它的破译工作呢1929年1月,波兹南大学数学系主任兹德齐斯罗·克里格罗夫斯基(ZdzislawKryglowski)教授开列了一张系里最优秀的数学家的名单,在这张名单上,有以后被称为密码研究"波兰三杰"的马里安·雷杰夫斯基(MarianRejewski),杰尔兹·罗佐基(JerzyRozycki)和亨里克·佐加尔斯基(HenrykZygalski).
雷杰夫斯基深知"重复乃密码大敌".
在ENIGMA密码中,最明显的重复莫过于每条电文最开始的那六个字母——它由三个字母的密钥重复两次加密而成.
德国人没有想到这里会是看似固若金汤的ENIGMA防线的弱点.
南京大学计算机系讲义652013/10/15Enigma—波兰人的破解雷杰夫斯基每天都会收到一大堆截获的德国电报,所以一天中可以得到许多这样的六个字母串,它们都由同一个当日密钥加密而成.
比如说他收到四个电报,其中每封电报的开头的六个字母为123456第一封电报:LOKRGM第二封电报:MVTXZE第三封电报:JKTMPE第四封电报:DVYPZXEMasterKey(SessionKey||SessionKey)南京大学计算机系讲义662013/10/15Enigma—波兰人的破解对于每封电报来说,第一个字母和第四个字母第二个字母和第五个字母第三个字母和第六个字母都是分别由同一个字母加密而来.
南京大学计算机系讲义672013/10/15Enigma—波兰人的破解第一个字母:ABCDEFGHIJKLMNOPQRSTUVWXYZ第四个字母:___P_____M_RX_一天中的MasterKey是固定的,所有的第i个字母都是用同一个字母映射表,i=1,…6.
加密相同的SessionKey得到相同"前6个字母".
雷杰夫斯基每天可以得到充分多的电报,他就可以把上面这个关系表补充完整ABCDEFGHIJKLMNOPQRSTUVWXYZFQHPLWOGBMVRXUYCZITNJEASDK第一个字母:第四个字母:南京大学计算机系讲义682013/10/15Enigma—波兰人的破解雷杰夫斯基对这样的表格进行了仔细观察.
从字母A开始看,它被对应成F;而F在此表中又被对应成W,接下去它被对应成A,我们又回到了最先开始的字母,于是就有了一个循环的字母圈A→F→W→A.
如果考虑所有的字母,雷杰夫斯基就能写出关于此对应表的所有的循环圈:A→F→W→A3个字母的循环圈B→Q→Z→K→V→E→L→R→I→B9个字母的循环圈C→H→G→O→Y→D→P→C7个字母的循环圈J→M→X→S→T→N→U→J7个字母的循环圈注意:一天中针对前6个字母分别考虑.
南京大学计算机系讲义692013/10/15Enigma—波兰人的破解虽然这些循环圈是由当日密钥,也就是转子的位置,它们的初始方向以及连接板上字母置换造成的但是每组循环圈的个数和每个循环圈的长度,却仅仅是由转子的位置和它们的初始方向决定的,和连接板上字母交换的情况无关!
南京大学计算机系讲义702013/10/15Enigma—波兰人的破解首先要取得足够的当日电文来构造字母对应表并且写出字母循环圈;然后根据循环圈的数目和它们的长度从记录表中检索出相对应的转子位置和初始方向;这就是当日的密钥(连接板的情况还未知).
循环圈的个数和长度可以看作是这个密钥的"指纹"—通过建立密钥"指纹"档案,雷杰夫斯基就能及时地把当天的密钥找出来.
南京大学计算机系讲义712013/10/15Enigma—图灵的破解但是这是ENIGMA使用中的一个重大弱点,德国人很可能会发觉这一点并取消这种重复,这样就会使英国密码分析专家的破译手段变得毫无用处.
图灵的任务就是要找到另一种不必利用重复密钥的破译方法.
在分析了以前大量德国电文后,图灵发现许多电报有相当固定的格式,他可以根据电文发出的时间、发信人、收信人这些无关于电文内容的信息来推断出一部分电文的内容.
比方说,要是在六点零五分截获了一份德国电报,它里面八成有Wetter这个词,也就是德文中的"天气".
根据在此之前德国人天气预报电文的死板格式,图灵甚至能相当准确地知道这个词具体在密文的哪个位置.
这就使得图灵想到了用"候选单词"这一方法来破译ENIGMA电文.
(已知明文攻击)南京大学计算机系讲义722013/10/15Enigma—图灵的破解如果在一篇密文中,图灵知道WETTER这个词被加密成了ETJWPX,那么剩下的任务就是要找到将WETTER加密成ETJWPX的初始设置.
但是雷杰夫斯基的天才思想告诉图灵,必须把转子方向变化造成的问题和连接板交换字母造成的问题分开来考虑.
Enigma—图灵的破解图灵并不清楚在密文中出现这个候选单词时的转子状态假设他猜对了这个候选单词把这个候选单词起始时转子的方向记为S,那么在此时ENIGMA把w加密成了E;然后转子转到下一个方向,就是S+1,ENIGMA把e加密成T;在方向S+2上一个不属于这个循环的字母被加密了,这个我们暂且不去管它;接下来在方向S+3,ENIGMA把t加密为W.
注意:S是不知道的,破解的过程就是猜测S的过程.
如何快速猜测南京大学计算机系讲义732013/10/15Enigma—图灵的破解如果三个转子按密钥字的方式设置初始方向,则线路通路如图所示形成闭路:把第一台ENIGMA显示器上的E和第二台ENIGMA显示器上的e连起来,又把第二台上的T和第三台上的t连起来,最后把第三台上的W和第一台上的w连起来(注意ENIGMA上字母没有大小写之分,这里我们只是用大小写来区别密文和明文).
假设连接板上有关的交换字母的连线是下面这样的(三台ENIGMA机上的都一样)E←→L1T←→L2W←→L3当然这里的L1、L2和L3都还是未知的.
注意:如果转轮方向对,按下按键w,灯泡会亮.
如果转轮方向不对,按下按键w,灯泡不会亮.
不断调整初始方向,直到灯泡发亮.
闭路的形成与键盘的连线方式无关.
南京大学计算机系讲义742013/10/15注意不是S+2Enigma—图灵的破解现在假设字母w被输入第一台ENIGMA,它先通过连接板变成了L3,然后通过三个转子经过反射器,再通过三个转子返回连接板;因为我们根据候选单词知道w此时会被加密成E,所以没有经过接线板前它一定是和E对应的L1;L1经过接线板变成E后,直接成了第二台ENIGMA(转子方向是S+1)的输入.
所以根据候选单词知道e此时会被加密成T.
从第一台ENIGMA来的e通过连接板变成了L1,再通过转子和反射器回来变成了连接板上和字母T对应的L2;通过连接板后变成了T,然后这个T又变成第三台ENIGMA机上的输入t.
第三台ENIGMA机的转子方向是S+3,这个传送过来的t会被加密成E,具体的情况和上面第一第二台上的类似.
我们发现现在三台ENIGMA机的线路组成了一个闭合回路,如果在里面加上一个灯泡,它就会亮起来.
这个闭合回路事实上就是那个字母循环圈的形象化.
这个闭合与初始方向有关,与键盘连线无关.
南京大学计算机系讲义752013/10/15假定:E←→L1T←→L2W←→L3L1→L2→L3:如果候选单词选对了话,键盘的连线板的后端就会有一个循环L1→L2→L3,当然不是W→E→T(虽然我们看到W→E→T循环).
Enigma—图灵的破解这个只与转子的初始方向有关.
与连线板连接方法无关.
L1←→E的本质是将T1的L1连接到了T2的L1:L1连接任何一个键,因为这个键与T2的同名键相连,所以也通用连接到了L1同理可以证明与L2是否连接到键T也是无关,与L3是否连接到键W.
分析好了转子初始方向(密钥),连线板就容易了.
南京大学计算机系讲义762013/10/15E←→L1T←→L2W←→L3赵燕枫,密码传奇——最高级的智力最隐蔽的搏杀,科学出版社,2008年4月第1版.
南京大学计算机系讲义772013/10/153.
分组密码的原理分组密码将明文序列分成等长的分组,对每一组用同一加密算法和同一密钥进行加密.
优点:容易被标准化加密解密容易实现同步缺点:算法庞大安全性难以证明南京大学计算机系讲义782013/10/15分组密码的设计准则—安全性原则影响密码算法安全的主要因素是:混乱与扩散ShannonCE.
Communicationtheoryofsecrecysystems,BellSystemTechnologyJournal,1949,28,656-715.
3.
分组密码的原理南京大学计算机系讲义792013/10/15分组密码的设计准则—安全性1扩散(diffusion):密钥的每一位都能影响密文的许多位,以防止对密钥进行逐段破译(减少复杂性);明文的每一位也影响密文的许多位,以便隐蔽明文的统计结构.
通常用线性变换达到扩散的目的.
扰乱(confusion):使得密文和明文与加密密钥之间的关系尽量复杂.
可以用复杂的代换算法来达到这个目的.
通常用非线性的替代变换达到扰乱的目的.
3.
分组密码的原理南京大学计算机系讲义802013/10/15分组密码的设计准则—安全性2抵抗现有的所有攻击抗差分分析抗线性分析安全强度的稳定性3.
分组密码的原理南京大学计算机系讲义812013/10/15分组密码的设计准则—实现原则软件实现原则子块长度自然适应软件编程8,16,32,…尽量避免比特置换.
使用标准处理器的指令:加法、乘法、移位.
硬件实现原则加密和解密实现的相似性,同一个器件即可以用来加密又可以用来解密.
南京大学计算机系讲义822013/10/15分组密码的设计准则—有效性应使得密钥最大限度地起到安全作用有效性差的例子:2n比特的密钥k1,k2解密方法Y=(xk1)k2等效于密钥n比特密钥k=k1k2加密Z=xk南京大学计算机系讲义832013/10/15代换-置换网络SPN—SubstitutionPermutationNetwork设l,m,Nr为整数,πs:{0,1}l→{0,1}l为置换πp:{0,1,…,l·m}→{0,1,…,l·m}为置换P=C={0,1}l·m;k=(k1,k2,…,kNr+1)x=(x1,x2,…xl·m)=x(1)||x(2)||…||x(m)x(i)=(x(i-1)l+1,…,xi·l)forr=1toNr-1dour=wr-1Krfori=1tomdovr(i)=πs(ur(i))wr=(vrπp(1),vrπp(2),…,vrπp(lm),))uNr=wNr-1KNrfori=1tomdovNr(i)=πs(uNr(i))y=vNrKNr+1w0=xX(1)……X(m)X(2)X:替代置换南京大学计算机系讲义842013/10/15乘积密码设S=(P,P,K,E,D)SS=(P,P,KK,E,D)e(k1,k2)(x)=ek2(ek1(x))d(k1,k2)(x)=dk1(dk2(x))如果对于任意的k1k2KK,都存在kK,使得e(k1,k2)(x)=ek(x))则称S为幂等的,即存在SS到S的一一映射,记为SS=S.
如果S为幂等的,则乘积密码SS没有提高安全性;如果S不是幂等的,则多次迭代可能提高安全性.
许多古典密码,如移位密码、代换密码、Vigenere密码和置换密码都是幂等的.
现代密码的每一轮的变换必须不是幂等的.
南京大学计算机系讲义852013/10/15Feistel密码R1=L0F(k1,R0),L1=R0;R2=L1F(k2,R1),L2=R1;Ri=Li-1F(ki,Ri-1),Li=Ri-1;Rn=Ln-1F(kn,Rn-1),Ln=Rn-1;Feistel密码是乘积密码m0=L0,m1=R0,fori=2tondomi=mi-2f(ki-1,mi-1)密文=Ln||Rn=mn-1||mnL0R0L1R1FLnRn明文密文L2R2F········轮函数F不必是可逆的:Ri-1=Lii,Li-1=RiF(ki,Ri-1)南京大学计算机系讲义862013/10/15参考文献:冯登国,吴文玲,分组密码的设计与分析,清华大学出版社,2009年10月第二版.
南京大学计算机系讲义872013/10/154.
对称密钥算法DES南京大学计算机系讲义882013/10/154.
1DES加密算法的背景发明人:美国IBM公司W.
Tuchman和C.
Meyer1971-1972年研制成功.
产生:美国国家标准局(NBS)1973年5月到1974年8月两次发布通告,公开征求用于电子计算机的加密算法.
经评选从一大批算法中采纳了IBM的LUCIFER方案.
标准化:DES算法1975年3月公开发表,1977年1月15日由美国国家标准局颁布为数据加密标准(DataEncryptionStandard),于1977年7月15日生效.
标准的条款中规定每五年对标准重新审查一次.
1983年DES被认证了一次,1987年经过争论DES在获准使用到1992.
1992年仍然没有DES的替代方案,NIST决定在延长DES5年,并在这5年中考虑替代方案.
1997年NIST发起了推选用于保护敏感的无密级的信息的加密算法的活动,最终RIJNDAEL算法胜出成为AES.
南京大学计算机系讲义892013/10/154.
2DES算法1.
输入64位明文M;2.
初始变换IP:IP(M)=L0|R03.
乘积变换:Li=Ri-1,Ri=Li-1f(Ri-1,Ki),i=1,…164.
初始变换逆IP-1,IP-1(L16|R16)南京大学计算机系讲义902013/10/154.
2DES算法64位码64位码初始变换逆初始变换16轮乘积变换明文密文输入输出IPIP-1南京大学计算机系讲义912013/10/1564位明文:M···L0R0IPIP(M)L1=R0R1=L0F(k1,R0)F(k1,R0)L15=R14R15=L14F(k15,R14)F(k16,R15)密文=IP-1(L16||R16)R-1,R0,R1,…R15,R16.
R-1=L0Ri=Ri-2F(ki,Ri-1)i=2,……,16密文=R15||R16L16=R15R16=L15F(k16,R15)IP-1南京大学计算机系讲义922013/10/15初始变换IP输入(64位)58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157输出(64位)L0(32位)R0(32位)4.
2DES算法南京大学计算机系讲义932013/10/15逆初始变换的逆IP-1置换码组输入(64位)40848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725输出(64位)4.
2DES算法南京大学计算机系讲义942013/10/15加密函数f(A,Ki)A(32位)+选择函数组(S1~S8)32位结果(A,Ki)置换运算P32位48位结果轮密钥:Ki扩展置换E4.
2DES算法南京大学计算机系讲义952013/10/15扩展运算EA32位3212345456789891011121312131415161716171819202120212223242524252627282928293031321扩展运算E扩展运算E的结果48位4.
2DES算法南京大学计算机系讲义962013/10/15选择运算012345678910111213141501441312151183106125907101574142131106121195382411481362111512973105031512824917511314100613S11011001020010输入6位输出4位4.
2DES算法101100南京大学计算机系讲义972013/10/15置换运算P选择函数的输出(32位)1672021291228171152326518311028241432273919133062211425置换P加密函数的结果(32位)4.
2DES算法南京大学计算机系讲义982013/10/15第i轮的密码函数Ri-1扩展:E(Ri-1)=E1E2…E8轮密钥:Ki=J1J2…J8S盒的输入:E1J1,E2J2,…E8J8,B1=E1J1,B2=E2J2,…B8=E8J8;共48位S盒的输出:S(B1),S(B2),……S(B8);共32位置换,与Ri-2作异或:Ri64位密钥置换选择1C0(28位)D0(28位)循环左移循环左移C1(28位)D1(28位)置换选择2K1(48位)(56位)循环左移循环左移Ci(28位)Di(28位)置换选择2Ki(48位)(56位)子密钥的计算逻辑轮数左移轮数左移119121102321124212252132621427215282161南京大学计算机系讲义1002013/10/15置换选择157494133251791585042342618102595143352719113605244366355473931331576254463830221466153453729211352820124密钥(64位)C0(28位)D0(28位)4.
2DES算法南京大学计算机系讲义1012013/10/15置换选择2Ci(28位)Di(28位)1417112415328156211023191242681672720132415231374755304051453348444939563453464250362932Ki(48位)4.
2DES算法南京大学计算机系讲义1022013/10/154.
3分组密码的统计测试原理统计测试的目的:断定算法产生的输出是否在统计上难以与真随机数据区分开来.
数据变换的有效性测试原理算法对明文的扩散性测试原理密钥更换的有效性测试原理南京大学计算机系讲义1032013/10/15数据变换的有效性测试原理频数检验:测试密文的"0","1"平衡性若输出的密文是随机的,则首先应该有较好的"0","1"平衡性.
设待测分组密码算法的分组长度为n比特待测密文文件含有F个密文分组统计这F个分组中汉明重量为i的分组个数,记为Fi,与其期望数Ei=F/2n进行Χ2拟合检验,将计算结果与自由度为n,显著性水平为5%的Χ2阈值相比较,来判断Fi是否符合二项分布B(n,1/2).
4.
3分组密码的统计测试原理南京大学计算机系讲义1042013/10/15数据变换的有效性测试原理跟随性检验:跟随性检验测试分组中相邻比特的出现情况.
设待测分组密码算法的分组长度为n比特;对分组取分组中相邻元素的模2加;然后统计模2加后的分组中重量为i的分组个数,记为Gi;与其期望数Ei=Cni*F/2n-1进行拟合Χ2检验;将计算结果与自由度为n-1,显著性水平为5%的Χ2阈值相比较,来判断Gi是否符合二项分布B(n-1,1/2).
4.
3分组密码的统计测试原理南京大学计算机系讲义1052013/10/15数据变换的有效性测试原理明密文独立性测试:明密文独立性测试主要是测试密文是否有不依赖于明文统计特性的性质.
主要考虑两方面的测试:一方面,如果明文具有某种明显的统计特性,算法具有较好的明密文独立性,则明文与其对应的密文的距离应是随机的;设待测分组密码算法的分组长度为n比特,明文文件含有F个分组,则其对应的密文也含有F个分组.
设明文分组集为P={p0,p1,……,pF-1},密文分组集为C={c0,c1,……,cF-1},记录相应的明密文距离D={Di=WH(pici)|0≤i≤F-1}.
统计D中汉明重量为i的分组数,记为Hi.
Ei=Cni*F/2n进行拟合Χ2检验.
将计算结果与自由度为n,显著性水平为5%的Χ2阈值相比较,来判断Hi是否符合二项分布B(n,1/2).
4.
3分组密码的统计测试原理南京大学计算机系讲义1062013/10/15算法对明文的扩散性测试原理从数据变换的有效性考虑,一个分组密码算法对明文的变化应是敏感的,即明文的雪崩现象.
根据分组密码测度中的严格雪崩准则,改变明文分组的任一比特,应导致密文分组中大约一半比特的变化.
设待测分组密码算法的分组长度为n比特,设明文分组P={p0,p1,……,pn-1},pi∈{0,1}设密文分组C={c0,c1,……,cn-1},ci∈{0,1}在固定密钥的情况下,每次改变P中的某个pi,则有Pi={p0,p1,…,pi1,…,pn-1},pi∈{0,1),0≤i≤n-1得到其相应的密文Ci={ci0,ci1,……,cin-1},cik∈{0,1),0≤k≤n-1,0≤i≤n-1计算C与Ci之间的汉明距离di=W(C+Ci),0≤i≤n-1根据随机性要求,密文之间的距离分布应符合二项分布B(n,1/2).
4.
3分组密码的统计测试原理南京大学计算机系讲义1072013/10/15DES的雪崩效应两个明文只有一个比特不同两个密钥只有一个比特不同两个密文平均有一半的比特不同4.
3分组密码的统计测试原理南京大学计算机系讲义1082013/10/15密钥更换的有效性测试原理设待测分组密码算法的分组长度为n比特,密钥长度为m比特.
设明文分组P={p0,p1,……,pn-1},pi∈{0,1}设密文分组C={c0,c1,……,cn-1},ci∈{0,1}密钥K={k0,k1,……,km-1},ki∈{0,1}在固定明文的情况下,每次改变K中的某一位,则有Ki={k0,k1,…,ki1,…,km-1},0≤i≤m-1得到其相应的密文Ci={ci0,ci1,……,cin-1},cik∈{0,1),0≤k≤n-1,0≤i≤m-1计算C与Ci之间的汉明距离di=W(C+Ci),0≤i≤m-1根据随机性要求,密文之间的距离分布应符合二项分布B(n,1/2).
4.
3分组密码的统计测试原理从密钥更换的有效性考虑,一个分组密码算法对密钥的变化应是敏感的,即密钥的雪崩现象.
根据分组密码测度中的严格雪崩准则,改变密钥中任一比特,应导致密文分组中大约一半比特的变化.
南京大学计算机系讲义1092013/10/154.
4DES的安全性—关于S-盒的设计准则与争论这个问题涉及美国国家安全局(NSA)他们修改了IBM的S-盒.
修改后的S-盒满足IBM原先关于S-盒的设计原则.
人们仍因此而怀疑NSA在S-盒中嵌入了陷门使得NSA借助于这个陷门及56比特的短密钥可以解密DES南京大学计算机系讲义1102013/10/15DES的安全性—关于S-盒的设计准则在1990年以前,S-盒的设计准则一直没有公布,直到差分密码分析方法发表后才公布.
公布的S-盒设计准则是:S-盒的每一行是0-15的一个排列;没有一个S-盒接近其输入的线性函数;如果固定输入的最左边,最右边的位固定,变换中间4位,每个可能的4位输出能得到一次.
如果两个输入仅中间2位不同,则输出至少有2位不同;如果两个输入仅差1位,则输出至少有2位不同;如果两个输入前2位不同,后2位已知,则输出不同;具有非零,相同差分的32对输入中,至多有8对具有相同的输出差分;4.
4DES的安全性南京大学计算机系讲义1112013/10/15DES的安全性—关于56比特的短密钥IBM最初提交的方案中密钥是112比特,但是,公布的DES却是56比特,坚持使用56比特短密钥是NSA的意见.
这就使得人们更加相信DES的陷门之说.
分布式穷举攻击:1997年1月28日,美国RSA数据安全公司在Intemet上开展了一项"秘密密钥挑战"的竞赛,悬赏一万美元,破解一段DES密文.
科罗拉多州的程序员R.
Verser设计了一个可以通过互联网分段运行的密钥搜索程序,组织了一个称为DESCHALL的搜索行动,成千上万的的志愿者加入到计划中.
第96天,即竞赛公布后的第140天,1997年6月17日晚上10点39分,美国盐湖城M.
Sanders成功地找到了密钥.
专用搜索机:1998年5月,美国电子边境基金会(EFF,ElectronicFrontierFoundation)宣布,他们用一台价值20万美元的计算机改装成专用设备,56小时就破译了DES.
这样,更加直接地说明了56比特密钥太短了,彻底宣布了DES的终结.
4.
4DES的安全性南京大学计算机系讲义1122013/10/15DES的安全性—并行计算Wiener报道了使用流水线的技术达到每秒5000万个密钥搜索速率的芯片的设计;1993年的价格计算,10万美元的模块包含5760个密钥搜索芯片;DES的搜索结果:造价搜索时间$100,00035小时$1,000,0003.
5小时$10,000,00021分钟4.
4DES的安全性MapReduce南京大学计算机系讲义1132013/10/15DES的安全性—DES的对称性DES算法具有对称:如果用表示按位取补,则:这种对称性,使穷举攻击密钥搜索量可以减少一半.
()()kkDESzDESz4.
4DES的安全性南京大学计算机系讲义1142013/10/15DES的安全性—弱密钥如果对于初始密钥k,生成的子密钥有k1=k2=…=k16,则称k是弱密钥.
DES有4个弱密钥:01010101010101011FlF1F1F1FlF1F1FE0E0E0E0E0E0E0E0FEFEFEFEFEFEFEFE4.
4DES的安全性南京大学计算机系讲义1152013/10/15DES的安全性—半弱密钥如果k1、k2满足DESk2(DESk1(x))=DESk1(DESk2(x))则称k1、k2是互逆的半密钥DES有12个半密钥01FE01FE01FE01FEFE01FE01FE01FE011FE01FE01FEOlFE0E0lFE01FE01FE1lF01E00lE00lE00lE04.
4DES的安全性南京大学计算机系讲义1162013/10/15DES的安全性—代数性质设E是一个密码算法,如果对任意的密钥k1,k2,都存在密钥k3,使得对任意的明文x有:Ek1(Ek2(x))=Ek3(x)则称E是闭合的.
显然,对闭合的加密算法企图通过二重加密来增强体制的安全性是无效的.
设(P,C,E,D,K)是一个密码体制,如果加密算法E是闭合的,且C=P,D=E,则{EkIk∈K}在复合加密运算下是一个群.
1992年,K.
W.
Campbell,M.
J.
Wiener证明了DES不是一个群.
正因以上结论,二重DES,三重DES有一定的价值,其穷举攻击的安全性虽有所改进,然而并非2倍,3倍的密钥量那么坚强.
4.
4DES的安全性南京大学计算机系讲义1172013/10/15Double-DESvs.
Triple-DESC=DES(K2,DES(K1,M))C=DES(K1,DES-1(K2,DES(K1,M)))M=DES-1(K1,DES(K2,DES-1(K1,C)))C=DES(K3,DES(K2,DES(K1,M)))K=K1K2K=K1K2K1K=K1K2K34.
4DES的安全性南京大学计算机系讲义1182013/10/15DES的安全性—关于差分分析对DES的分析发现,DES的S-盒具有差分特性,即:其输出的差分(异或)不能遍历0到15,不是等可能地在0-15之间取值.
根据这点,1990年,以色列密码学家EliBiham和AdiShamir对分组密码提出了差分密码分析方法.
这是一种选择明文攻击最为有效的方法.
虽然对16轮DES没有攻破,但是,如果迭代的轮数降低,则DES可被成功地攻破.
例如,8轮DES在一台PC机上只需要2分钟即可被攻破.
差分分析正是是利用了DES的S-盒输出的差分不能均匀遍历0-15这一特点.
4.
4DES的安全性南京大学计算机系讲义1192013/10/154.
4差分密码攻击迭代密码在下面的意义上是弱的:对于Yi=F(Yi-1,Ki),Y*i=F(Y*i-1,Ki),Yi-1=Yi-1Y*i-1若三元组(Yi-1,Yi,Y*i)的一个或多个值是已知的,则确定子密钥Ki是容易的.
若密文对已知,并且最后一轮的输入差分能一某种方式得到,则一般来说,确定最后一轮的子密钥或者其中一部分是可行的.
Y1Y2Y3Y4Y5Y6Y7Y8Y9Y10Y11Y12Y13Y14Y15Y16Y1*Y2*Y3*Y4*Y5*Y6*Y7*Y8*Y9*Y10*Y11*Y12*Y13*Y14*Y15*Y16*最后一轮的输入差分Y15=Y15Y15*Y16=F(Y15,K16),Y*16=F(Y*15,K16),Y15=Y15Y15*南京大学计算机系讲义1202013/10/15DES差分密码分析设Sj是特定的S-盒(1≤j≤8),(Bj,Bj*)是一对长度为6比特的串.
称Sj的输入异或是BjBj*,Sj的输出异或是Sj(Bj)Sj(Bj*)对每一个S-盒都有64个可能的输入异或,DES有8个S-盒,共有512个这样的分布.
'6''2'''62,jjjjjjBZBBBBBZ**jjjj6jjj对任何记B()={(B,B)|BB=}.
易知|B()|=2=64,且B()={(B,B)|B}.
对中的每一对,我们能计算出的一个输出异或,共计64个异或,它们分布在16个可能的值上,这些分布的不均匀性是差分密码攻击的基础.