现代密码学第二讲古典密码学-2

《现代密码学》》第二讲古典密码学钾索大沴niJIMUUtuMWIYJIPUSHAWI.LlLJMMUfcKJhllUM1■密码学分类■密码学与信息安全的关系上讲内容回顾钾索九峰riLIJIMLrUIUM.QSIIYJIR»VIAWIlLLJMMUfcKJhllUM本章主要内容■代换密码■置换密码■HHI密码■转轮密码■古典密码的惟密文攻击方法>外彙大沴iLIJIWLUUM.UUIV□!KMFSAW:lLit密码分类■代换密码(substitution):代换是古典密码中用到的最基本的处理技巧。所谓代换，就是将明文屮的一个字母由其它字母、数字或符号替代的一种方法。■凯撒密码■仿射密码■单表代换■$剝饿■置换密码(permutation):将明文字符按照某种规律重新排列而形成密文的过程。・Hill密码■转轮密码钾索大沴iLIJIMlrJIPUSHAWlilt乂称移位密码匕知最早的代换密码，■代换表（密钥）：abcdefghijk1mnoDEFGHIJKLMNOPQB■数学描述：用数字表示每个字母：abcdefghijk1mno0123456761011121314j凯撒密码(caesarcipher)c-

E(p)=(p+k)mod(26)p=D(<^=(c-A)mod(26)明文密文密钥嫌［1,25］，只有25个孓钾索人沴:LlJiMLJI諱UC『«AWIlLLjM1zcyBXAw2VYuXtw5VruqTpsz53UMr17q6PX52凯撒密码例:使用其后的第三个字母代换该字母明文：meetmeafterthetogaparty密文：PHHWPHDIWHUWKHWRJDSDUWB＞处孓钾索人冷riLIJIMUUMMUUIY:J|K»lfAm:lllLJM'2恺撒密码的攻击■已知明文和密文、加密和解密算法，需要解同余方程，可以恢复密钥k=(c-p)mod(26)；■穷举攻击：已知密文，且明文为有意义字符，至多尝试25次，可以恢复明文.处＜钾索人冷riLIJIMUUMMUUIY:J|K»lfAm:lllLJM'J仿射密码(AffineCipher)■移位密码的扩展明文peZ26,密文c^Z26,密钥k=(afb)eZ26xZ26,且gcd(a,26)=l・定理设,对任意的,同余方程ax=b(modm)有唯一解的充分必要备件是gcd(a，〃?)=1gcd(<zP/?z)=\a~la=\，称殆是元，JL为伞一dk

(y)==d~[(ax+b—b)=a~Yax=xmod26j仿射密码___例：令密钥k={7f3)f

且gcd(7,26)=l.明文hot=(7,14,19)加密：(7X7+3)

mod26=0(7X14+為

mod26=23(7X19+3^

mod26=6密文为(0,23,6>(a,x,g)解密:7-1=15=41mod26(0-J)X15mod26=7(23-$X15mod26=14(6-3X15mod26=19明文为(7,14,19)=(h,O,t)钾索大沴anjiMb□!pucfsmM仿射密码练习：令密钥々=(兒3),且gcd(5,26)=l.明文hot=(7,14,19)，求加解密过程。>孓钾索人冷riLIJIMUUMMUUIY:J|K»lfAm:lllLJM'i仿射密码■己知两对明文和密文和（仍,G）、加密和解密算法，需要解2元同余方程组，可以恢复密钥r.—

Yn.-kH\mnd故拉必數扒川、假设a>ljr?>2且均为整敖，如果gc如，m）=l，则称a与W互素。中所有与m互素的敖的个敖是M.扒_的计算Il假定/h=np1/，Pi豸不相同素敖，於⑽j-i・/=i仿射密碭的密匍空问大小是W彡⑽单表代换密码(MonoalphabeticCipher)-代换表是26个字母的任意置换1b密函数：解密函数:abCdefgha1«Jk1mn0PqrstuVv\XyzDKVqFIBJVIPESCXH丁YAUQLRGzN明文：ifwewishtoreplaceletters密文：WlRFRWAJUHYFTSDVFSFUUFYAABcDEFGHIJKLMNCPQRSTl|VYZsgrrlak6X0fhbVqzujdv\1Ptcinry分嚏却愛大聲UluMQUlYJIILieJMMUfcKJhllUBlt屬J单表代换密码■练习：明文：nicework,求密文>孓钾索人冷riLIJIMUUMMUUIY:J|K»lfAm:lllLJM'j单表代换密码■已知明文和密文，可以恢复部分加密函数（解密函数）；■穷举攻击：已知密文，明文为有意义字符，至多尝试26!=4x1026个，可以恢复明文126!＞处孓钾索人冷riLIJIMUUMMUUIY:J|K»lfAm:lllLJM'.多表代换密码j(PolyalphabeticCiphers)加密明文消息吋采用不同的单表代换，巾密钥具体决定采用哪个表代换消息，密钥通常是一个词的重复。■简化的多表代换密码维吉尼亚密码(VigenereCipher):由26个类似caesar密码的代换表组成处＜钾索人冷riLIJIMUUMMUUIYAm:lllLJM'多表代换密码■维吉尼亚密码：在长为m的密码中，任何一个字母可被影射为26个字母中的一个明文pe(Z26)m,密文c

e(Z26)m

,密钥k

e(Z26)m加密口(厂1+々1:巧+々2,,…,mod26;解密P

=(q-^1rC2^2rf

…，cm-kjmod26.5釙嚏钾索大學riLIJWbUMMUSIIYJIK»VIAWIHLJMMUfcKJhlNJUtABCDtFGH1_JKLM^QPQRSTUVWXYZAABCDEFGH(J^LMfdOPORSTUVWXYZBBCDEFGHIJKLMNOPORSTUVWXYZACCDEFGHIjKLMNOPQRSTUVWXVZABnnPF/zui|yiMunonncTiiuw^vTARrEEFGH1JKLMNOPQRSTUVWXYZABCDlfFGM1JlttMNnpnRSTUVMiX¥7ARrnFGGH1JICLMNOPQRSTUVWXV2A0CDEFHHIJKLMriOPQRSTLVWXYZABCDEFG11JKLMNOPORSfUVWXYZA0CDEFGHJJKLMNCPORSTUVWXYZABCDEFGH1KIt1MWOPARATiWWXYTAAr^FFAH1JLLMNOPQRSTUVV/XYZABCDEFGH1\K1MMNOPORSTUVWXYZABCOEFGH1fKLNNOPQRSTUVWXYZABCDEFGH1JKLMOOPQRSTUVWXYZA0CDEFGH1JKLMNVHUKh1UVWXYZA«<Utr(JM1JILMWUQQRSTIJVWXYZA6CDEFGH1JKLMNOPRRSTUVWXYZABCDEFGHt」KLMN0P0SSTUVWXYZABCDEFGH1JKLMNOPQRTTUVWXYZA8CDEFGH1JKIMNOPCRSUUVWXYZABCDEFCH1JKLMNOPQRSTVVWXtZABCDEFGHI|KLMNOPQRSTUwWXYZABCtJEFGHIJKLMNOPQRSTUVXXYZABCDEFGHIJKLMNOPQRSTUVWYY7ARCDFFGH1JtCLMWOPQR5TUVWXzZABCDEfGHIJKLMNOPQRSTUVWXYKey:GOOGLEPlaintext:BUYYOUTUBECiphertext:HIMEZYZIPKShl"ILIJIMUUluNLEItilYJIK»FtAVJtLLCJMMUluKJhllCRlt多表代换密码■练习:明文：nicework,密钥：hot,求密文。>孓钾索人冷riLIJIMUUMMUUIY:J|K»lfAm:lllLJM'多表代换密码■□己知m个连续的明文和密文，可以恢复维吉尼亚密码的单表移位量（即密钥）；■穷举攻击：已知密文，明文为有意义字符，至多尝试26m个，可以恢复明文密钥中间大小圮26Am处＜钾索人冷riLIJIMUUMMUUIY:J|K»lfAm:lllLJM'1置换密码■加密变换使得信息元素只有位置变化而形态不变，如此可以打破消息中的某些岡定模式(结构)明文pE(Z26)m，密文CE(Z26)m，密钥々G{ri|定义在1,2,…，爪上的置换}加密口(厂n⑴'戶n(2)…，戶n(m))mod26;解密P=(rn\i)f,cn\2)•••'rn

rnod26.3^分＜钾索大學riLIJWbUMHKIIVJIPU9IIiLLLJMMUfcKJhllU^tj置换密码例■密钥351642X6.35i642明文:shesellsseashellsbytheseashore分组：sheselIsseashellsbytheseashore置换：ELSEHSSSLASELBHSELHEYSTEHEARSO>孓钾索人冷riLIJIMUJ|AWiLlLJM14置换密码■练习：明文：nicework求密文。X1234Pi(x)2413钾索九峰riLIJIMLrUIUM.QSIIYJIR»VIAWIlLLJMMUfcKJhllUMj置换密码■已知多对明文和密文，可以推导置换表（即密钥）；■穷举攻击：已知密文，明文为有意义字符，至多尝试m!个，可以恢复明文3-*分组为m，至多有m!个置换处＜钾索人冷riLIJIMUUMMUUIY:J|K»lfAm:lllLJM'希尔密码(Hillcipher)1929年，LesterS.Hill提出明文pe(Z26)m，密文ce(Z26)m，密钥定义在Z26上m*m^］可逆矩阵｝加密c二p丸Kmod26解密K1mod26®钾索大沴■LIJIHLCMKMIGWILLCJMMUfcKJhllURltjl希尔密码■例加密解密8、<718、K=K-'=J7,<23fll8、(920)=(99+60,72+140)=(3,4)i37)》rtf呷電人孕・LIJBMbUhMWIY□!KMV£IlLUMMU*4CAIK)_£18、lh=(9.20)4希尔密码■置换密码可以看做是希尔密码的特例。练习：设hill密码的密钥如下，求对应置换密码的置换表。<0010、=00011000<0100>>孓钾索人冷riLIJIMUJ|AWiLlLJM14希尔密码■己知m组明文和密文、加密和解密算法，需要解m元同余方程组，可以恢复密钥；安全强度（M是素數，糢數为合數，不是任意矩阵可是）26'醐当m=5,强度是2655~2625-2117通过矩阵，将信息均匀分布到每个m表向量的每个分量中，具有软好的随机性j转轮密码(RotorMachine)■19世纪20年代，开始出现机械加解密设备，最典型的是转轮密码机1918年ArthurScherbius发明的EIGMA,瑞典Haglin发明的Haglin,和曰军发明的“紫密”和“兰密”都属于转轮密码机。＞处孓钾索人冷riLIJIMUUMMUUIYAm:lllLJM';转轮密码-4——---Enigma密码机钾索大沴niJIMUUtuMWIYJIPUSHAWI.LlLJMMUfcKJhllUM5*slVwroll*niixlmmriHnrhiMnHnrdInitiHlM'ltbigZ转轮密码tlirvLiiuntiimnioii2115=*-x:h，IS1，i：95HlJ11--'■h2iiX!tQ7'1022H1i2HLt5111715y161725JSIK”)20，42«h\^'4211AAB<nFF.HIJKLMsnru-ksLIVXiUJHK,dinxbonofmmionskinncjnsrriv-liiirni.rMurdiiScitinn»ft<r，，『•<■k<y>imkr4惟密文攻击■在攻击者可以截获（足够）明密文的条件下，易于恢复用户的密钥；■当攻击者只能窃听到密文时，若明文是有意义的（一段话等具有可读性）字符时，利用穷举搜索，可以通过密文解密出对应明文，继而恢1Z密钥。（穷平价杂度収決1当攻击者只能窃听到密文时，是否有其它更有效攻击方法？？若明义是无意义的随机卞符时，攻击者是riLIJWbUlMKWhJIPUSHAWJ惟密文攻击人类的语言存在冗余，以英文文档为例■字母e是使用频率最高的■其次是T,R,N,I,O,A,S■很少使用■A、I、U很少用在词尾，E、N、R常出现在词尾。E、S、D作为字母结尾字母的单词超过一半，T、A、S、W为起始字母的单词约占一半。>孓钾索人冷riLIJIMUUMMUUIYAm:lllLJM'j惟密文攻击□频率>孓钾索人冷riLIJIMUUMMUUIY:J|K»lfAm:lllLJM'c2.75%d4.25%e12.70%f2.23%g2-02%h6‘09%i6.97%j0.15%k0.77%14.03%m2.41%n6‘mo7.61%p1.93%q0.10%r5.99%s6.33%t9.06%u2.76%v0,98%w2.36%x0.

15%yL97%z0.07%i惟密文攻jr■_于双字母组合，三字母组合。SingleLetterDoubleLetterTripleLetterETHTHE丁HEANDINTIONERATIIREFOR0ONTHAAANTERENlESK.---r"riLIJIMbUIUM.K1IIYJIPUGFtAM>1|HLJMMUkKJhllVML4惟密文攻击■统计攻击（频率攻击）麵假设：根据分析假设某些结论。推断:在假设的前提下，推断出一些结论。■双频.字母跟随关系■构词规则■词义■验证发展：填上破译出的字母，根据词义、构词规则不断发展芳钾索大沴riLIJVHbUIMMHUIY□!POCICAW:l纛4惟密文攻击■移位密码、仿射密码和单表代换密码都没有破坏明文的频率统计规律，吋以直接用统计分析法■例：截取一段仿射密码的密文mod26FMXVEDKAPHFERBNDKRXRSREFMORUDSDKDVSHVUFEDKAPRKDLYEVLRHHRH＞处孓钾索人冷riLIJIMUUMMUUIY:J|K»lfAm:lllLJM'惟密文攻击统计得到R(8),D(7),E,H,K(5),S,F,V(4)密文出现字母频率统计＞处孓钾索人冷riLIJIMUUMMUUIY:J|K»lfAm:lllLJM'字母频率字母频率字母频率字母频率A2H501U2B1I0P2V4C0J0Q0W0D7K5R8X2E5L2S3Y1F4Ml2丁0Z0G0N14惟密文攻击■令R=E(e)，D=E(t),得到方程组■abcdefghijk1.mnopqrstuvwxyZ■01234567891011121314151617181920212223242S(4a+b=17\19a+b=3解得a:6zb-19;其屮gcd(6,26)=2〉l，故猜测错误。>孓钾索人冷riLIJIMUUMMUUIY:J|K»lfAm:lllLJM'令R=E(e)，E=E(t)?a=13R=E(e)，H=E(t)?a=8R=E(e)，K=E(t),a=3,b=5,第3组解有效，则解密函数p=(c-5)*3-1=9c-19□解密得明文：algorithmsarequitegeneraldefinitionsofarithmeticprocesses.®钾索大沴riEDiMLuh|M.Q^il¥JItAW4HL惟密文攻击2>34惟密文攻击■练习：已知用户用移位密码加密，密文为“KHOOR,_UBRQH”，用统计法求密钥和对应明文■abcdefghijk1.mnopqrstuvwxyZ•012345678910111213141516171819202122232425■H(4),0,R(2),K(l),Q(l),丫(1),U(l),B(l)H..e,也就是e+x=h得4+x=7，密钥为3解密:hello，everyone>孓钾索人冷riLIJIMUUMMUUIYAm:lllLJM'惟密文攻击维吉尼亚密码由m个移位密码构成，移位密码不改变字符的芬布，敁者能确定m，则可以换到每个瘃位密码的位移量k■克思斯基测试（Kasiski）_若用给定的m个密钥表周期地对明文字母加密，则当明文冇两个相同字母组（K度大丁•3）在明文序列屮间擗的字母数为m的倍数时，这两个明k字母组对应的密文字每殖必賴向。■但反过來，若密文屮出现阿个相同的字母组，它们所对hv的明文_7母组未必相同，佴相同的可能性很人。■将密文中相同的字母组找出来，并对其相同字母数综合研究，找出它们觀舢觀dl鰣認翻就有可能>孓钾索人冷riLIJIMUUMMUUIY:J|K»lfAm:lllLJM'j惟密文攻击■例SEVOAHMAERATBIAXXWTNXBEEOPHBSBQMQEQERBWRVXUOAKXAOSXXWEAHBWGJMMQMNKGRFVCSXWTRZXWIAKLXFPSKAUTEMND<?MGTSXMXBTUIADNGMGPSRELXNJELXvrvprtulhdnqwtwdtygbphxtfaljhasvbfxngll^hr|ZBWELEKMSJTKNBUWRJGNMGJSGLXFEYPHAGNRBIEQJTAMRVLCRREMNDGLXRRIMGNSNRW^JHAEYEVTAQEBBIPEEWEVKAKOEWADKKMXMTBjdcHMTKDNVR2lcHR|：LQOHPWQAIIWXNRMGWOIfFKEECHR出现5个位置:1,166,236,276,286距离差：165,235,275,285,gcd(165,235,275,285)=5猜测m=5卹索大聲■LLMMUUUMWIYOlKHIS美％lLC3MMU<4ICAIK)IIK4惟密文攻击■重合指数法(CoincidenceIndex)设一f］语玄由n个李母构成，每■个李母发生的柷卒为Pi

，則重合拍政是拍其中两个n随机元素相同的板卒的和，记Cl=^p-

。J=1-完全随机的文本CI=0.0385,—个有意义的英文文本€1=0-065钾索大沴riLIJWUJIK»llAWiLlLJMMUfcKJhlMJM惟密文攻击__■实际使用ci的估计值cr:■L：密文长。-fi：密文符号i发生的数目。■作用：■区分单表代换密码和多表代换密码■确定两段文本是否是同一种方法进行加密■确定维吉尼亚密码的m值大聲riUJWGJIK»llAU>iLlLJMMUfcKJhirCRItommqcckuegdgizrncomoqeglxxxczvbckmyomxhiemrdezpnevhovvbkkrcssepkcjuefmakntdrxbiemrkoommayIyIigzsdiaknvoiqxgkkkvjmrdkbbxfqnemxdrlbcjhpztvvixyetnirgnomrzrreikioxrusxcretv■例cr(ci)=0.0412cr(C2)=0.0445zaozygyukndwpiouoriyrhhbzxrceayvxuvrxkcmaxstxsepbrxcsIrukvbxtgzuggdwhxmxcsxbiktnslrjzhbxmspungzrgkudxnaufcmrzxjrywymi_«冋一加密方法今钾索大學JIPU$r«ILL'L惟密文攻击pbnXpVwre4惟密文攻击1,对于不冋的m,重新对密文m分组2,对不同的分组，分别求取重合指数Q046195COQ400CCC.0.M3472000O-WUUmm

:C当m为5吋，重合指数平均接近P0.0650.0W40.33l7tt3.0W5363.0*2310.034^32C.C47&.30.042323G.G5C2&20電kJLitl

OU今3SaQ&KM0.⑽CM甘-€*c•--y"iLIJIMUUMMUIIIYJIPUSHAWiLlLJMMU<uK>IIUi|&0.040.C53333C.C333330.02G667C.0265GT5.::€«C-

0&04)29D的_4C0C4MS&.&5C277067159100^^3640101S4C惟密文攻击•当两个類卒分布类似对，X值相对委志。___Pi：并号i在笫一个分布中发生的板卒Ai：符号i在第二个分布中发生的概卒■拟重合指数法-Chi測武＞分孓钾索人冷riLIJIMLrUIUM.QSIIYJIR»VIAWIlLLJMMUfcKJhllUM;=l惟密文攻击■对于一个移位密码I.疣计每个字母的频敦：儿…，Z:f26人Po='钾索九峰riLIJIMLrUIUM.QSIIYJIR»VIAWIlLLJMMUfcKJhllUM2.令舎丈长度为n’=n/mr26孛母的概半分布:12.00%10,00%:.得通常丈本的孛C4.00%2,00%0.00%abcdefghI

iklninopqrstuvwxxi11JLI1_.4惟密文攻击<对概半分布A，/V"，Z^行移^ii(0<z<25),得到序利巧=P26-i，…，P25，P。，朽，…，5、对分布乃与Q计箅相关卷枳26Correia—咕必二IP。+j)mod26*^77=06>得到最大相关值(wre/ation(PrQ)对应的i为移往量的估计值。"芳(分<钾索大沴,,-*fcriLIJWbUhM.qVI¥□!KHICAWHHLJMMUkKJblURIt惟密文攻击CHREEVOAHMAERATBIAXXWTNXBEEOPHBSBQMQEQERBWRVXUOAKXAOSXXWEAHBWGJMMWIRZXWIAKLXFPSKAUTEMNDCMGTSXMXBTU1ADNGMGPSRELXNJELXVRXP