现代密码学第二讲：古典密码学

1古典密码学《现代密码学》第二讲上讲内容回顾密码学分类密码学与信息安全的关系本章主要内容代换密码置换密码Hill密码转轮密码古典密码的惟密文攻击方法密码分类代换密码（substitution）：代换是古典密码中用到的最基本的处理技巧。所谓代换，就是将明文中的一个字母由其它字母、数字或符号替代的一种方法。凯撒密码仿射密码单表代换多表代换置换密码（permutation）：将明文字符按照某种规律重新排列而形成密文的过程。Hill密码转轮密码凯撒密码(caesarcipher)已知最早的代换密码，又称移位密码代换表（密钥）：abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABC数学描述:用数字表示每个字母：abcdefghijklmnopqrstuvwxyZ012345678910111213141516171819202122232425c=E(p)=(p+k)mod(26)p=D(c)=(c–k)mod(26)明文p∈Z26，密文c∈Z26，密钥k取[1,25]，只有25个凯撒密码例:使用其后的第三个字母代换该字母明文：meetmeafterthetogaparty密文：PHHWPHDIWHUWKHWRJDSDUWB恺撒密码的攻击已知明文和密文、加密和解密算法，需要解同余方程，可以恢复密钥k=(c-p)mod(26)；穷举攻击：已知密文，且明文为有意义字符，至多尝试25次，可以恢复明文.仿射密码（AffineCipher）移位密码的扩展明文p∈Z26，密文c∈Z26，密钥k=(a,b)∈Z26×Z26,且gcd(a,26)=1.加密：c=E(p)=(a×p+b)mod26解密：p=D(c)=(c–b)×a-1mod26例：令密钥k=(7,3),且gcd(7,26)=1.明文hot=(7,14,19)加密：(7×7+3)mod26=0(7×14+3)mod26=23(7×19+3)mod26=6密文为(0,23,6)=(a,x,g)解密：7-1=15=-11mod26(0-3)×15mod26=7(23-3)×15mod26=14(6-3)×15mod26=19明文为(7,14,19)=(h,o,t)仿射密码仿射密码练习：令密钥k=(9,3),且gcd(5,26)=1.明文hot=(7,14,19)，求加解密过程。已知两对明文和密文（p1,c1）和（p2,c2）、加密和解密算法，需要解2元同余方程组，可以恢复密钥k=(a,b)；c1=(a×p1+b)mod26c2=(a×p2+b)mod26穷举攻击：已知密文，明文为有意义字符，至多尝试26*Φ(26)个，可以恢复明文.仿射密码单表代换密码（MonoalphabeticCipher）代换表是26个字母的任意置换例：加密函数:nopqrstuvwxyzXHTMYAUOLRGZNabcdefghijklmDKVQFIBJWPESC解密函数:明文:ifwewishtoreplaceletters密文:WIRFRWAJUHYFTSDVFSFUUFYANOPQRSTUVWXYZzujdwlptcinryABCDEFGHIJKLMsgmakexofhbvq单表代换密码练习：明文:nicework，求密文。单表代换密码已知明文和密文，可以恢复部分加密函数（解密函数）；穷举攻击：已知密文，明文为有意义字符，至多尝试26!=4x1026个，可以恢复明文代换表的个数为26！多表代换密码(PolyalphabeticCiphers)加密明文消息时采用不同的单表代换，由密钥具体决定采用哪个表代换消息，密钥通常是一个词的重复。简化的多表代换密码----维吉尼亚密码（VigenèreCipher）：由26个类似caesar密码的代换表组成多表代换密码维吉尼亚密码：在长为m的密码中，任何一个字母可被影射为26个字母中的一个明文p∈(Z26)m，密文c∈(Z26)m，密钥k∈(Z26)m加密c=(p1+k1,,p2+k2,,…,pm+km)mod26;解密p=(c1-k1,,c2-k2,,…,cm-km)mod26.多表代换密码例多表代换密码练习：明文:nicework，密钥：hot，求密文。多表代换密码已知m个连续的明文和密文，可以恢复维吉尼亚密码的单表移位量（即密钥）；穷举攻击：已知密文，明文为有意义字符，至多尝试26m个，可以恢复明文密钥空间大小是26^m置换密码加密变换使得信息元素只有位置变化而形态不变，如此可以打破消息中的某些固定模式（结构）明文p∈(Z26)m，密文c∈(Z26)m，密钥k∈{∏|定义在1,2,…,m上的置换}加密c=(p∏(1),,p∏(2),,…,p∏(m))mod26;解密p=(c∏-1(1),,c∏-1(2),,…,c∏-1(m))mod26.置换密码例密钥明文：shesellsseashellsbytheseashore分组：shesellsseashellsbytheseashore置换：ELSEHSSSLASELBHSELHEYSTEHEARSO置换密码练习：明文:nicework求密文。X1234Pi(x)2413置换密码已知多对明文和密文，可以推导置换表（即密钥）；穷举攻击：已知密文，明文为有意义字符，至多尝试m！个，可以恢复明文分组为m，至多有m！个置换希尔密码（Hillcipher）1929年，LesterS.Hill提出明文p∈(Z26)m，密文c∈(Z26)m，密钥K∈{定义在Z26上m*m的可逆矩阵}加密c=p*Kmod26解密p=c*K-1mod26扩散希尔密码例希尔密码置换密码可以看做是希尔密码的特例。练习：设hill密码的密钥如下，求对应置换密码的置换表。希尔密码已知m组明文和密文、加密和解密算法，需要解m元同余方程组，可以恢复密钥；穷举攻击：已知密文，明文为有意义字符，至多尝试26m*m个，可以恢复明文11121m11121m11121mm1m2mmm1m2mmm1m2mmcccpppkkkcccpppkkk转轮密码（RotorMachine）19世纪20年代，开始出现机械加解密设备，最典型的是转轮密码机1918年ArthurScherbius发明的EIGMA，瑞典Haglin发明的Haglin，和日军发明的“紫密”和“兰密”都属于转轮密码机。转轮密码Enigma密码机转轮密码惟密文攻击在攻击者可以截获（足够）明密文的条件下，易于恢复用户的密钥；当攻击者只能窃听到密文时，若明文是有意义的（一段话等具有可读性）字符时，利用穷举搜索，可以通过密文解密出对应明文，继而恢复密钥。（穷举搜索的复杂度取决于密钥空间的大小，古典密码体制的密钥空间通常比较小。）当攻击者只能窃听到密文时，是否有其它更有效攻击方法？？若明文是无意义的随机字符时，攻击者是否可以获得明文或密钥的相关信息？？惟密文攻击人类的语言存在冗余，以英文文档为例字母e是使用频率最高的其次是T,R,N,I,O,A,SZ,J,K,Q,X很少使用A、I、U很少用在词尾，E、N、R常出现在词尾。E、S、D作为字母结尾字母的单词超过一半，T、A、S、W为起始字母的单词约占一半。惟密文攻击02468101214ABCDEFGHIJKLMNOPQRSTUVWXYZ频率惟密文攻击对于双字母组合,三字母组合惟密文攻击统计攻击（频率攻击）假设：根据分析假设某些结论。推断：在假设的前提下，推断出一些结论。双频字母跟随关系构词规则词义验证发展：填上破译出的字母，根据词义、构词规则不断发展惟密文攻击移位密码、仿射密码和单表代换密码都没有破坏明文的频率统计规律，可以直接用统计分析法例：截取一段仿射密码的密文c=ap+bmod26惟密文攻击统计得到R(8),D(7),E,H,K(5),S,F,V(4)字母频率字母频率字母频率字母频率A2H5O1U2B1I0P2V4C0J0Q0W0D7K5R8X2E5L2S3Y1F4M2T0Z0G0N1密文出现字母频率统计惟密文攻击令R=E(e)，D=E(t)，得到方程组abcdefghijklmnopqrstuvwxyZ012345678910111213141516171819202122232425解得a=6,b=19;其中gcd(6,26)=21，故猜测错误。4ab1719ab3惟密文攻击1、令R=E(e)，E=E(t)？a=132、R=E(e)，H=E(t)?a=83、R=E(e)，K=E(t),a=3,b=5,第3组解有效，则解密函数p=(c-5)*3-1=9c-19解密得明文：algorithmsarequitegeneraldefinitionsofarithmeticprocesses.惟密文攻击练习：已知用户用移位密码加密，密文为“KHOOR,HYHUBRQH”，用统计法求密钥和对应明文abcdefghijklmnopqrstuvwxyZ012345678910111213141516171819202122232425H(4),O,R(2),K(1),Q(1),Y(1),U(1),B(1)H------e,也就是e+x=h得4+x=7，密钥为3解密：hello，everyone惟密文攻击维吉尼亚密码由m个移位密码构成，移位密码不改变字符的分布，故若能确定m，则可以找到每个移位密码的位移量k克思斯基测试（Kasiski）若用给定的m个密钥表周期地对明文字母加密，则当明文中有两个相同字母组(长度大于3)在明文序列中间隔的字母数为m的倍数时，这两个明文字母组对应的密文字母组必相同。但反过来，若密文中出现两个相同的字母组，它们所对应的明文字母组未必相同，但相同的可能性很大。将密文中相同的字母组找出来，并对其相同字母数综合研究，找出它们的相同字母数的最大公因子，就有可能提取出有关密钥字的长度m的信息。惟密文攻击例CHR出现5个位置：1,166,236,276,286距离差：165,235,275,285，gcd(165,235,275,285)=5猜测m=5惟密文攻击重合指数法（CoincidenceIndex）完全随机的文本CI=0.0385，一个有意义的英文文本CI=0.065惟密文攻击实际使用CI的估计值CI’：L：密文长。fi：密文符号i发生的数目。作用：区分单表代换密码和多表代换密码确定两段文本是否是同一种方法进行加密确定维吉尼亚密码的m值惟密文攻击例CI’(C1)=0.0412CI’(C2)=0.0445同一加密方法惟密文攻击1,对于不同的m,重新对密文m分组2,对不同的分组，分别求取重合指数当m为5时，重合指数平均接近于0.065惟密文攻击拟重合指数法惟密文攻击对于一个移位密码惟密文攻击惟密文攻击CHREEVOAHMAERATBIAXXWTNXBEEOPHBSBQMQEQERBWRVXUOAKXAOSXXWEAHBWGJMMQMNKGRFVGXWTRZXWIAKLXFPSKAUTEMNDCMGTSXMXBTUIADNGMGPSRELXNJELXVRVPRTULHDNQWTWDTYGBPHXTFALJHASVBFXNGLLCHRZBWELEKMSJIKNBHWRJGNMGJSGLXFEYPHAGNRBIEQJTAMRVLCRREMNDGLXRRIMGNSNRWCHRQHAEYEVTAQEBBIPEEWEVKAKOEWADREMXMTBHHCHRTKDNVRZCHRCLQOHPWQAIIWXNRMGWOIIFKEE密文子串的拟重合指数密文子串的交互重合指数（续）明文Thealmondtreewasintentativeblossom.Thedayswerelonger,oftenendingwithmagnificenteveningsofcorrugatedpinks