第7章-传统加密技术课件

第第7章章 传统加密技术传统加密技术第7章-传统加密技术第第7章章 传统加密技术传统加密技术单表代换密码Caesar密码 公元前1世纪，凯撒大帝（视频）Caesar Ciphercan define transformation as:明码表A B C D E F G H I J K L M N O P Q R S T U V W X Y Z密码表 D E F G H I J K L M N O P Q R S T U V W X Y Z A B Cveni，vidi，viciYHAL YLGL YLFLCaesar CipherMathematically give each letter a numbera b c d e f g h i j k l m0 1 2 3 4 5 6 7 8 9 10 11 12n o p q r s t u v w x y Z13 14 15 16 17 18 19 20 21 22 23 24 25Mathematical expression:c=E(p)=(p+3)mod 26 p=D(c)=(c 3)mod 26 Cryptanalysis of Caesar Cipher 已知加密和解密算法需测试的密钥只有25个明文所用的语言是已知的，且其意义易于识别所以可以采用穷举攻击分析方法单表代换密码（Monoalphabetic Cipher）rather than just shifting the alphabet could shuffle(jumble)the letters arbitrarily each plaintext letter maps to a different random ciphertext letter key is 26 letters long rather than just 1 lettere.g.：abcdefg hijklmn opq rst uvw xyz key:DKVQFIB JWPESCX HTM YAU OLR GZNPlaintext:ifwewishtoreplacelettersCiphertext:WIRFRWAJUHYFTSDVFSFUUFYA Monoalphabetic Cipher SecurityKey space:26!,i.e.about 4 x 1026 possibilitiesSecure?!WRONG!Key Size(bits)Number of Alternative KeysTime required at 1 decryption/sTime required at 106 decryptions/s26 characters(permutation)26!=4 10262 1026 s=6.4 1012 years6.4 106 yearsCryptanalysis of monoalphabetic cipherArabian scientists,9th centurykey concept-monoalphabetic substitution do not change relative letter frequencies human languages are redundant English Letter FrequenciesLanguage Redundancyletters are not equally commonly used in English E is by far the most common letter followed by T,R,N,I,O,A,S other letters like Z,J,K,Q,X are fairly rare have tables of single,double&triple letter frequencies for various languagesExample Cryptanalysis*given ciphertext:UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQcount relative letter frequenciesguess P as e and Z as tguess ZW is th and hence ZWP is the,and ZWSZ is thatUZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ t a e e te a that e e a a tVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX e t ta t ha e ee a e th t aEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ e e e tat e the et proceeding with trial and error finally get:it was disclosed yesterday that several informal butdirect contacts have been made with politicalrepresentatives of the vietcong in moscow多表代换密码 polyalphabetic substitution ciphers another approach to improving security is to use multiple cipher alphabets makes cryptanalysis harder with more alphabets to guess and flatter frequency distribution use a key to select which alphabet is used for each letter of the message use each alphabet in turn repeat from start after end of key is reached Vigenre Cipher此类算法中最著名且最简单的simplest polyalphabetic substitution cipher is the Vigenre Ciphereffectively multiple Caesar ciphers key is multiple letters long K=k1 k2.kd ith key letter specifies ith alphabet to use use each alphabet in turn repeat from start after d letters in messagedecryption simply works in reverse Examplewrite the plaintext out write the keyword repeated above ituse each key letter as a caesar cipher key encrypt the corresponding plaintext lettereg using keyword deceptiveplaintext:w e a r e discoveredsaveyourself 22 4 0 17 4key:d e c e p tivedeceptivedeceptive 3 4 2 4 15ciphertext:25 8 2 21 19 Z I C V T WQNGRZGVTWAVZHCQYGLMGJ 3行行22列列Security of Vigenre Ciphershave multiple ciphertext letters for each plaintext letter 每个明文字母对应多个密文字母hence letter frequencies are obscuredbut not totally lostDistinguish attack区分单表还是Vigenre的步骤see if look monoalphabetic or notstart with letter frequencies 是否满足语言的统计特性if not,then need to determine number of alphabets,since then can attach each 密钥词的长度Kasiski Methodmethod developed by Babbage(1854);Kasiski(1863)repetitions in ciphertext give clues to period 重复次数给出线索same plaintext+same keyword same ciphertext Determine the length of keyE.g.repeated“VTW”in previous example ZICVTWQNGRZGVTWAVZHCQYGLMGJ suggests key size of 3 or 9Attack each monoalphabetic cipher individually using same techniques as beforeOne-Time Pad 一次一密if a truly random key as long as the message is used,the cipher will be secure One-Time pad,Joseph Mauborgnethe key is used only once is unbreakable since ciphertext bears no statistical relationship to the plaintextsince for any plaintext&any ciphertext there exists a key mapping one to otherproblems in generation&safe distribution of keyExamplesendmoremoney18413312 14 17412 14 13424901723 15 21 14 11 112891414 109312 18 23 25 15 127BECKJDMSXZPMHcashnotneeded2018713 14 19 134434325422322 15 19519 21 12841414 109312 18 23 25 15 127BECKJDMSXZPMHPlaintext:key:Ciphertext:Plaintext:key:Ciphertext:Transposition Ciphers 置换密码Hide the message by rearranging the letter order without altering the actual letters usedcan recognise these since have the same frequency distribution as the original text Rail Fence cipher栅栏密码write message letters out diagonally over a number of rows then read off cipher row by roweg.write message out as:m e m a t r h t g p r y e t e f e t e o a a tgiving ciphertextMEMATRHTGPRYETEFETEOAATColumn Transposition Ciphersa more complex schemewrite letters of message out in rows over a specified number of columnsthen reorder the columns according to some key before reading off the rowsKey:4 3 1 2 5 6 7Plaintext:a t t a c k p o s t p o n e d u n t i l t o m o r r o wCiphertext:TTNO APTR TSUM AODO COIR KNLO PETW多次置换密码：按照上述算法多次置换。多次置换密码：按照上述算法多次置换。Enigma上个世纪20年代，德国发明家亚瑟谢尔比乌斯发明著名的Enigma 密码机。它主要由经电线相连的键盘、转子和显示器组成，转子本身也集成了26条线路，把键盘的信号对应到显示器不同的小灯上去多表代换密码不仅仅如此，因为当键盘上一个键被按下时，相应的密文在显示器上显示，然后转子的方向就自动地转动一个字母的位置（在图中就是转动1/6圈，而在实际中转动1/26圈）。3 cylinders have 263=17576 alphabetsProduct Ciphers第二次世界大战中，在破译密码过程中，原本是以语言学家和人文学者为主的解码团队中加入了科学家。首先是波兰人利用德军电报中前几个字母的重复出现，破解了早期的Enigma密码机，而后又将破译的方法告诉了法国人和英国人。英国人在计算机理论之父图灵的带领下，通过寻找德国人在密钥选择上的失误，并成功夺取德军的部分密码本，获得密钥，以及进行选择明文攻击等等手段，破解出相当多非常重要的德军情报。Summary传统对称密码使用代换或置换技术。代换技术将明文元素映射为密文元素置换技术将明文元素的位置进行系统的置换。代换技术的代表算法：凯撒密码，单表代换密码，多表代换密码，一次一密；置换技术的代表算法：栅栏密码，多步置换密码。扩展阅读The code book,密码故事(中文版)，英 Simon SinghThe codebreakers,破译者(中文版)，美卡恩密码的奥秘（全彩）作者:（美）伦德编著，刘建伟等译 出版社:电子工业出版社 出版时间:2015年3月