计算机网络-密码学简介 97页

第2章密码学\n参考文献W.Stallings（杨明等译），编码密码学与网络安全-原理与实践，电子工业出版社。2001年4月。BruceChneier,应用密码学，机械工业出版社，2000年1月。冯登国，密码分析学，清华大学出版社，2000年8月。陈鲁生，沈世镒，现代密码学，科学出版社，2002年7月。22七月20212\n1.基本概念—术语消息被称为明文（plaintext）。用某种方法伪装消息以隐藏它的内容的过程称为加密(encryption,encipher)。加了密的消息称为密文(ciphertext)。而把密文转变为明文的过程称为解密(decryption,decipher)。2021/7/223\n1.基本概念—术语使消息保密的技术和科学叫做密码编码学(cryptography)。从事此行的叫密码编码者（cryptographer）。破译密文的科学和技术叫做密码分析学（cryptanalysis）。从事密码分析的专业人员叫做密码分析者（cryptanalyst）。密码学包括密码编码学和密码分析学两者。现代的密码学家通常也是理论数学家。2021/7/224\n1.基本概念—密码学的其它作用鉴别消息的接收者应该能够确认消息的来源；入侵者不可能伪装成他人。完整性消息的接收者应该能够验证在传送过程中消息没有被修改；入侵者不可能用假消息代替合法消息。抗抵赖发送者事后不可能虚假地否认他发送的消息。2021/7/225\n1.基本概念—算法和密钥密码算法也叫密码，是用于加密和解密的数学函数。通常情况下，有两个相关的函数：一个用作加密，另一个用作解密。明文用M（消息），密文用C表示，加密函数E作用于M得到密文C，用数学表示为：E（M）=C.相反地，解密函数D作用于C产生MD（C）=M.先加密后再解密消息，原始的明文将恢复出来，下面的等式必须成立：D（E（M））=M2021/7/226\n1.基本概念—受限制的算法如果算法的保密性是基于保持算法的秘密，这种算法称为受限制的算法。如果有人无意暴露了这个秘密，所有人都必须改变他们的算法。2021/7/227\n1.基本概念—现代密码学现代密码学用密钥解决了这个问题，密钥用K表示。密钥K的可能值的范围叫做密钥空间。加密和解密运算都使用这个密钥，加/解密函数现在变成：EK1（M）=CDK2（C）=MDK2（EK1（M））=MEK（M）=CDK（C）=MDK（EK（M））=M2021/7/228\n2021/7/229\n1.基本概念—对称算法和非对称算法对称算法加密密钥能够从解密密钥中推算出来，反过来也成立。公开密钥算法公开密钥算法用作加密的密钥不同于用作解密的密钥，而且解密密钥不能根据加密密钥计算出来。2021/7/2210\n1.基本概念—密码分析密码分析学是在不知道密钥的情况下。恢复出明文的科学。对密码进行分析的尝试称为攻击。密码分析的一个基本假设：密码分析者已有密码算法及其实现的全部详细资料。在实际的密码分析中并不总是有这些详细信息的应该如此假设。如果其他人不能破译算法，即便了解算法如何工作也是徒然，如果连算法的知识都没有，那就肯定不可能破译它。2021/7/2211\n（1）唯密文攻击密码分析者有一些消息的密文这些消息都用同一加密算法加密密码分析者的任务是恢复尽可能多的明文或者最好是能推算出加密消息的密钥来已知：C1=EK（P1），C2=EK（P2），，推导出：P1，P2，，2021/7/2212\n（2）已知明文攻击密码分析者不仅可得到一些消息的密文，而且也知道这些消息的明文。分析者的任务就是用加密信息推出用来加密的密钥或导出一个算法，此算法可以对用同一密钥加密的任何新的消息进行解密。已知：P1，C1=Ek（P1），P2，C2=Ek（P2），，Pi，Ci=Ek（Pi）推导出：密钥k，或从Ci+1=Ek（Pi+1）推出Pi+1的算法。2021/7/2213\n（3）选择明文攻击分析者不仅可得到一些消息的密文和相应的明文，而且他们也可选择被加密的明文。这比已知明文攻击更有效。因为密码分析者能选择特定的明文块去加密，那些块可能产生更多关于密钥的信息，分析者的任务是推出用来加密消息的密钥或导出一个算法，此算法可以对用同一密钥加密的任何新的消息进行解密。2021/7/2214\n（4）选择密文攻击密码分析者能选择不同的被加密的密文，并可得到对应的解密的明文，例如密码分析者存取一个防窜改的自动解密盒，密码分析者的任务是推出密钥。已知：C1，P1=Dk（C1），C2，P2=Dk（C2），，Ci，Pi=Dk（Ci），推导出：k。2021/7/2215\n（5）软磨硬泡攻击密码分析者威胁、勒索，或者折磨某人，直到他给出密钥为止。行贿有时称为购买密钥攻击。这些是非常有效的攻击，并且经常是破译算法的最好途径。2021/7/2216\n最好的算法是那些已经公开的，并经过世界上最好的密码分析家们多年的攻击，但还是不能破译的算法。美国国家安全局对外保持他们的算法的秘密，但他们有很好的密码分析家在内部工作，他们互相讨论他们的算法，通过执著的审查发现他们工作中的弱点。2021/7/2217\n密码分析者不是总能知道算法的。例如在二战中美国人破译日本人的外交密码——紫密（PURPLE）[794]就是例子，而且美国人一直在做这种事。如果算法用于商业安全程序中，那么拆开这个程序，把算法恢复出来只是时间和金钱问题。如果算法用于军队的通讯系统中，购买（或窃取）这种设备，进行逆向工程恢复算法也只是简单的时间和金钱的问题。2021/7/2218\n2.古典密码算法在计算机出现前，密码学由基于字符的密码算法构成。不同的密码算法是字符之间互相代换或者是互相之间换位，好的密码算法是结合这两种方法，每次进行多次运算。现在事情变得复杂多了，但原理还是没变。重要的变化是算法对比特而不是对字母进行变换，实际上这只是字母表长度上的改变，从26个元素变为2个元素。大多数好的密码算法仍然是代替和换位的元素组合。2021/7/2219\n代替密码代替密码就是明文中每一个字符被替换成密文中的另外一个字符。接收者对密文进行逆替换就恢复出明文来。在经典密码学中，有四种类型的代替密码简单代替密码：就是明文的一个字符用相应的一个密文字符代替。报纸中的密报就是简单的代替密码。多名码代替密码它与简单代替密码系统相似，唯一的不同是单个字符明文可以映射成密文的几个字符之一，例如A可能对应于5、13、25或56，“B”可能对应于7、19、31或42，等等。2021/7/2220\n多字母代替密码字符块被成组加密，例如“ABA”可能对应于“RTQ”，ABB可能对应于“SLL”等。多表代替密码由多个简单的代替密码构成，例如，可能有5个被使用的不同的简单代替密码，单独的一个字符用来改变明文的每个字符的位置。2021/7/2221\n简单代替密码著名的凯撒密码就是一种简单的代替密码，它的每一个明文字符都由其右边第3个（模26）字符代替（A由D代替，B由E代替W由Z代替X由A代替，Y由B代替，Z由C代替）。它实际上更简单，因为密文字符是明文字符的环移，并且不是任意置换。ABCDEFGHIJKLMNOPQRSTUVWXYZDEFGHIJKLMNOPQRSTUVWXYZABC2021/7/2222\n凯撒密码仅有25个可能的密钥，非常不安全。但是英文的明文有一个特点，不同的英文字母在文章中出现的频率不同。2021/7/2223\n字母频率表字母概率字母概率字母概率字母概率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.0282021/7/2224\n单表代替密码的缺点在单表代替下字母的频度、重复字母模式、字母结合方式等统计特性除了字母名称改变以外，都未发生变化，依靠这些不变的统计特性就能破译单表代换；2021/7/2225\n如果一个明文字母可以任意一个密文字母代替，则有26！中不同的密钥，大约4*1026密钥，比的DES的256=7.2*1016个密钥大10个数量级。2021/7/2226\n多表代替密码Vigenere密码是由法国密码学家BlaisedeVigenere于1858年提出的一种密码，它是一种以移位代换为基础的周期代换密码。d个代换表f＝(f1，f2，…，fd)由d个字母序列给定的密钥k＝(kl，k2，…，kd)∈ZdN决定，其中ki(i=1，2，…，d)确定明文的第i+td个字母(t为正整数)的移位次数。2021/7/2227\n多表代替密码的例子例1设d=6,k=cipher,明文串:thiscryptosystemisnotsecurem=(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),2021/7/2228\n1978182172415192815741728152115232568023814182418194128187417281574172122152011919129131419184220142815741728151522825819222519密文串为：VPXZGIAXIVWPUBTTMJPWIZITWZT2021/7/2229\n多表代替密码的优点在多表代换下，原来明文中的统计特性通过多个表的平均作用而被隐蔽了起来。多表代换密码的破译要比单表代替密码的破译难得多。2021/7/2230\n多表代替密码的破解（1）1863年，普鲁士军官F.Kasiski发明了通过分析密文中的字母重复的情况来确定周期多表代替密码的准确周期的方法。例：密钥：dog，明文：tobeornottobetobeornottobedogdogdogdogdwchhcxqczwchh2021/7/2231\n多表代替密码的破解（2）在密文中字符串wchh重复了两次，其间个为9个字符。这个距离是密钥长度的倍数，可能的密钥长度是1,3,9。判定了长度之后就可以用频率分析法来破译各个单表代替密码了。多表代替密码的破解的原因：密钥的长度太短。2021/7/2232\n密钥长度的确定设x=x1x2......xn,x的重合指数定义为x中两个随机字母相同的概率，记为Ic(x)。我们期望Ic(x)=p1p2......p25=0.065。2021/7/2233\n密钥字的确定设x=x1x2......xn,y=y1y2......yn’,x和y的重合互指数定义为x中的一个随机字母等于y的一个随机字母相同的概率，记为MIc(x)。可以根据重合互指数分析出密钥字。参见：冯登国，密码分析学，清华大学出版社，1.4节。2021/7/2234\nEnigma直到第一次世界大战结束为止，所有密码都是使用手工来编码的，就是铅笔加纸的方式。考虑到不能多次重复同一种明文到密文的转换方式，和民用的电报编码解码不同，加密人员并不能把转换方式牢记于心。转换通常是采用查表的方法，所查表又每日不同，所以解码速度极慢。22七月202135\nEnigma(1)解密一方当时正值春风得意之时，几百年来被认为坚不可破的维吉耐尔(Vigenere)密码和它的变种也被破解。而无线电报的发明，使得截获密文易如反掌。无论是军事方面还是民用商业方面都需要一种可靠而又有效的方法来保证通讯的安全。2021/7/2236\nEnigma(2)1918年，德国发明家亚瑟·谢尔比乌斯(ArthurScherbius)和他的朋友理查德·里特(RichardRitter)创办了谢尔比乌斯和里特公司。这是一家专营把新技术转化为应用方面的企业，很象现在的高新技术公司。谢尔比乌斯负责研究和开发方面，紧追当时的新潮流。他的一个想法就是要用二十世纪的电气技术来取代那种过时的铅笔加纸的加密方法。2021/7/2237\nEnigma(3)谢尔比乌斯发明的加密电子机械名叫ENIGMA，在以后的年代里，它将被证明是有史以来最为可靠的加密系统之一，而对这种可靠性的盲目乐观，又使它的使用者遭到了灭顶之灾。2021/7/2238\nEnigma(4)ENIGMA它可以被分解成相当简单的几部分。下面的图是它的最基本部分的示意图，我们可以看见它的三个部分：键盘、转子和显示器。2021/7/2239\nEnigma(5)2021/7/2240\nEnigma(6)照片左方是一个完整的转子，右方是转子的分解，我们可以看到安装在转子中的电线2021/7/2241\nEnigma(7)当第一个转子转动整整一圈以后，它上面有一个齿拨动第二个转子，使得它的方向转动一个字母的位置。2021/7/2242\nEnigma(7)在此基础上谢尔比乌斯十分巧妙地在三个转子的一端加上了一个反射器，而把键盘和显示器中的相同字母用电线连在一起。反射器和转子一样，把某一个字母连在另一个字母上，但是它并不转动。这么一个固定的反射器它并不增加可以使用的编码数目。它和解码联系起来了。2021/7/2243\nEnigma(8)发信人首先要调节三个转子的方向，使它们处于26*26*26=17576个方向中的一个（事实上转子的初始方向就是密匙，这是收发双方必须预先约定好的）依次键入明文，并把闪亮的字母依次记下来(密文)然后就可以把加密后的消息用比如电报的方式发送出去。当收信方收到电文后，使用一台相同的ENIGMA，按照原来的约定，把转子的方向调整到和发信方相同的初始方向上；依次键入收到的密文，并把闪亮的字母依次记下来，就得到了明文。2021/7/2244\nEnigma(9)当然谢尔比乌斯还可以再多加转子，但是我们看见每加一个转子初始方向的可能性只是乘以了26。尤其是，增加转子会增加ENIGMA的体积和成本。谢尔比乌斯希望他的加密机器是便于携带的；首先他把三个转子做得可以拆卸下来互相交换，这样一来初始方向的可能性变成了原来的六倍。2021/7/2245\nEnigma(10)下一步谢尔比乌斯在键盘和第一转子之间增加了一个连接板。这块连接板允许使用者用一根连线把某个字母和另一个字母连接起来，这样这个字母的信号在进入转子之前就会转变为另一个字母的信号。这种连线最多可以有六根（后期的ENIGMA具有更多的连线），这样就可以使６对字母的信号互换，其他没有插上连线的字母保持不变。当然连接板上的连线状况也是收发信息的双方需要预先约定的。连接板上两两交换6对字母的可能性数目非常巨大，有100391791500种密钥：1.连接板的连接：A/L-P/R-T/D-B/W-K/F-O/Y2.转子的顺序：2,3,13.转子的初始方向：Q-C-W2021/7/2246\nEnigma(11)调整好ENIGMA，现在操作员可以开始对明文加密了。但是我们看到每天只有一个密钥，如果这一天的几百封电报都以这个密钥加密发送的话，暗中截听信号的敌方就会取得大量的以同一密钥加密的信息，这对保密工作来说不是个好兆头。我们记得在简单替换密码的情况下，如果密码分析专家能得到大量的密文，就可以使用统计方法将其破解。2021/7/2247\nEnigma(12)尽管不知道对ENIGMA是否可以采用类似的统计方法，德国人还是留了个心眼。他们决定在按当日密钥调整好ENIGMA机后并不直接加密要发送的明文。相反地，首先发送的是一个新的密钥。连接板的连线顺序和转子的顺序并不改变，和当日通用的密钥相同；想反地，转子的初始方向将被改变。操作员首先按照上面所说的方法按当日密钥调整好ENIGMA，然后随机地选择三个字母，比如说PGH。他把PGH在键盘上连打两遍，加密为比如说KIVBJE（注意到两次PGH被加密为不同的形式，第一次KIV，第二次BJE，这正是ENIGMA的特点，它是一种复式替换密码）。然后他把KIVBJE记在电文的最前面。接着他重新调整三个转子的初始方向到PGH，然后才正式对明文加密。2021/7/2248\nEnigma(13)1929年1月，波兹南大学数学系主任兹德齐斯罗·克里格罗夫斯基(ZdzislawKryglowski)教授开列了一张系里最优秀的数学家的名单，在这张名单上，有以后被称为密码研究“波兰三杰”的马里安·雷杰夫斯基(MarianRejewski)，杰尔兹·罗佐基(JerzyRozycki)和亨里克·佐加尔斯基(HenrykZygalski)。雷杰夫斯基深知“重复乃密码大敌”。在ENIGMA密码中，最明显的重复莫过于每条电文最开始的那六个字母——它由三个字母的密钥重复两次加密而成。德国人没有想到这里会是看似固若金汤的ENIGMA防线的弱点。2021/7/2249\nEnigma(14)汉斯—提罗·施密特(Hans-ThiloSchimdt)于1888年出生在柏林的一个中产阶级家庭里，一次大战时当过兵打过仗。根据凡尔赛条约，战败后的德国进行了裁军，施密特就在被裁之列。退了伍后他开了个小肥皂厂，心想下海从商赚点钱。结果战后的经济萧条和通货膨胀让他破了产。此时他不名一文，却还有一个家要养。2021/7/2250\nEnigma(15)鲁道夫给他的二弟在密码处(Chiffrierstelle)找了个位置。这是专门负责德国密码通讯的机构——ENIGMA的指挥中心，拥有大量绝密情报。汉斯—提罗把一家留在巴伐利亚，因为在那里生活费用相对较低，勉强可以度日。就这样他一个人孤零零地搬到了柏林，拿着可怜的薪水，对大哥又羡又妒，对抛弃他的社会深恶痛绝。2021/7/2251\nEnigma(16)接下来的事情可想而知。如果把自己可以轻松搞到的绝密情报出卖给外国情报机构，一方面可以赚取不少自己紧缺的钱，一方面可以以此报复这个抛弃了他的国家。1931年11月8日，施密特化名为艾斯克(Asche)和法国情报人员在比利时接头，在旅馆里他向法国情报人员提供了两份珍贵的有关ENIGMA操作和转子内部线路的资料，得到一万马克。靠这两份资料，盟国就完全可以复制出一台军用的ENIGMA机。2021/7/2252\nEnigma(17)雷杰夫斯基每天都会收到一大堆截获的德国电报，所以一天中可以得到许多这样的六个字母串，它们都由同一个当日密钥加密而成。比如说他收到四个电报，其中每封电报的开头的六个字母为123456第一封电报：LOKRGM第二封电报：MVTXZE第三封电报：JKTMPE第四封电报：DVYPZX2021/7/2253\nEnigma(18)对于每封电报来说，第一个字母和第四个字母第二个字母和第五个字母第三个字母和第六个字母都是分别由同一个字母加密而来。2021/7/2254\nEnigma(19)第一个字母：ABCDEFGHIJKLMNOPQRSTUVWXYZ第四个字母：___P_____M_RX_____________如果雷杰夫斯基每天可以得到充分多的电报，他就可以把上面这个关系表补充完整第一个字母：ABCDEFGHIJKLMNOPQRSTUVWXYZ第四个字母：FQHPLWOGBMVRXUYCZITNJEASDK2021/7/2255\nEnigma(20)雷杰夫斯基对这样的表格进行了仔细观察。从字母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个字母的循环圈2021/7/2256\nEnigma(21)虽然这些循环圈是由当日密钥，也就是转子的位置，它们的初始方向以及连接板上字母置换造成的，但是每组循环圈的个数和每个循环圈的长度，却仅仅是由转子的位置和它们的初始方向决定的，和连接板上字母交换的情况无关！2021/7/2257\nEnigma(22)首先要取得足够的当日电文来构造字母对应表并且写出字母循环圈；然后根据循环圈的数目和它们的长度从记录表中检索出相对应的转子位置和初始方向；这就是当日的密钥（连接板的情况还未知）。循环圈的个数和长度可以看作是这个密钥的“指纹”——通过建立密钥“指纹”档案，雷杰夫斯基就能及时地把当天的密钥找出来。2021/7/2258\nEnigma(23)每个密钥仅对一个消息使用一次。发方对所发的消息加密，然后销毁乱码本中用过的一页或用过的磁带部分。收方有一个同样的乱码本，并依次使用乱码本上的每个密钥去解密密文的每个字符。收方在解密消息后销毁乱码本中用过的一页或用过的磁带部分。新的消息则用乱码本的新的密钥加密。2021/7/2259\n1.6公开密钥密码学\n公开密钥系统的的特性加密和解密运算是计算上容易的问题，即应该属于P类问题。密码分析应该属于NP完全问题。2021/7/2261\nRSA公开密钥算法2021/7/2262\n素数素数：只能被1和它本身整除的自然数；否则为合数。每个合数都可以唯一地分解出素数因子6=2·3999999=3·3·3·7·11·13·3727641=131·121从2开始试验每一个小于等于√27641的素数。2021/7/2263\n素因子分解的速度整数n的十进制位数因子分解的运算次数所需计算时间（每微秒一次）501.4x10103.9小时759.0x1012104天1002.3x101574年2001.2x10233.8x109年3001.5x10294.0x1015年5001.3x10394.2x1025年2021/7/2264\n定义RSA的密钥p和q是素数（秘密的）r=p·q(r)=(p-1)(q-1)（秘密的）SK是秘密密钥（解密密钥）（秘密的）PK是公开密钥（加密密钥）X是明文（秘密的）Y是密文PK满足：(PK,(r))=1;SK满足：SK·PK=1mod(r)同余如果a和b都是整数，而m是一个固定的正整数，则当m能够整除a-b时，称a,b对模m同余，记为ab(modm)2021/7/2265\n模运算及其性质[a(modn)+b(modn)]modn=(a+b)modn[a(modn)-b(modn)]modn=(a-b)modn[a(modn)·b(modn)]modn=(ab)modn如果a与n互素，则存在b使得a·b=1modn2021/7/2266\nRSA公开密钥密码算法M是明文，n是一个大数加密：C=Memodn解密：M=Cdmodn=Medmodn条件：能找到e,d,n使得对所有的M，当Mn，即密钥长度大于MAC长度。那么如果已知M1和MAC1，MAC1=Ck1(M1)，密码分析者必须对所有可能的密钥值Ki，执行MACi=Cki(N1)。当MAC1=MACi时，则至少找到一个密钥。注意，总共将产生2k个MAC，但只有2k<2n个不同的MAC值。因此，许多密钥能产生这个正确的MAC，但对手却无法确认真正的正确密钥。平均说来，总共2k／2n=2k-n个密钥将产生一个匹配。总共要进行[k/n]+1轮。2021/7/2289\n一个有问题的MACM=X1||X2||…||Xm⊿(M)=X1⊕X2⊕…⊕XmCk(M)=Ek[⊿(M)]如果对手窃取到M||Ck(M)。N=Y1||Y2||…||YmYi任意选定，i=1,…m-1。Ym=Y1⊕Y2⊕…⊕Ym-1⊕⊿(M)Ck(M)=Ck(N)2021/7/2290\n基于的DES的MACM=D1||D2||……||DnO1=Ek(D1)Oi=Ek(Di⊕Oi-1),i=2,…,n2021/7/2291\n散列函数方法(a)提供了保密和鉴别。MH||EDMHEk[M||H(M)]kkH(M)比较2021/7/2292\n散列函数方法(b)散列与加密结果合并为一个整体函数实际上就是一个MAC。E[H(M)]是变长报文M和密钥K的函数值，且它生成一个定长的输出，对不知道该密钥的对手来说是安全的。提供鉴别MHE||MHDEk[H(M)]KKEK(H(M)]比较2021/7/2293\n散列函数方法(c)提供鉴别、抵赖。MHE||MHDEKRa(H(M)]KRaKUaEKRa(H(M)]比较2021/7/2294\n散列函数方法(d)同时提供保密性、鉴别和抵赖。MHE||EDMHDEk[M||EKRa(H(M)]kkKRaKUaEKRa(H(M)]比较2021/7/2295\n散列函数方法(e)通信各方共享一个公共的秘密值s。对报文鉴别。M||H||H[(M||s)]s比较||Hs2021/7/2296\n散列函数方法(f)通过包含报文和散列码的整体进行加密就能对上一种方法(e)增加保密功能M||H||Ek(H[(M||s)])s比较||HsEkH[(M||s)]Dk2021/7/2297