第2.1章-古典密码学.ppt

1、广东技术师范学院-计科院-计算机应用系第2章 密码学概论古典密码学对称密码体制公钥密码体制广东技术师范学院-计科院-计算机应用系密码学发展阶段1949年之前密码学是一门艺术19491975年密码学成为科学1976年以后密码学的新方向公钥密码学广东技术师范学院-计科院-计算机应用系第1阶段古典密码(1/3)密码学还不是科学，而是艺术出现一些密码算法和加密设备密码算法的基本手段是代换(substitution)和置换(permutation)，针对的是字符简单的密码分析手段出现主要特点：数据的安全基于算法的保密广东技术师范学院-计科院-计算机应用系20世纪早期密码机第第1阶段古典密码阶段古典密码(

2、2/3)广东技术师范学院-计科院-计算机应用系第1阶段古典密码(3/3)1883年Kerchoffs第一次明确提出了编码的原则：加密算法应建立在算法的公开不影响明文和密钥的安全。这一原则已得到普遍承认，成为判定密码强度的衡量标准，实际上也成为传统密码和现代密码的分界线。广东技术师范学院-计科院-计算机应用系第2阶段 19491975(1/1)计算机使得基于复杂计算的密码成为可能相关技术的发展1949年Shannon的“The Communication Theory of Secret Systems”提出了两种“安全”，即“理论安全”和“实际安全”，证明了要达到“理论安全”，密钥的长度必须长

3、于或等于明文的长度1967年David Kahn的The Codebreakers1971-73年IBM Watson实验室的Horst Feistel等几篇技术报告主要特点：数据的安全基于密钥而不是算法的保密 广东技术师范学院-计科院-计算机应用系第3阶段 19761976年：Diffie & Hellman 的 “New Directions in Cryptography” 提出了不对称密钥密1977年Rivest,Shamir & Adleman提出了RSA公钥算法90年代逐步出现椭圆曲线等其他公钥算法主要特点：公钥密码使得发送端和接收端无密钥传输的保密通信成为可能广东技术师范学院-计

4、科院-计算机应用系第3阶段 19761977年DES正式成为标准80年代出现“过渡性”的“Post DES”算法,如IDEA,RCx,CAST等90年代对称密钥密码进一步成熟 Rijndael,RC6, MARS, Twofish, Serpent等出现2001年Rijndael成为DES的替代者广东技术师范学院-计科院-计算机应用系基本概念(1/4)密码学(Cryptology): 是研究信息系统安全保密的科学.密码编码学(Cryptography): 主要研究对信息进行编码,实现对信息的隐蔽.密码分析学(Cryptanalytics):主要研究加密消息的破译或消息的伪造.广东技术师范学院-

5、计科院-计算机应用系基本概念(2/4)明文( Plaintext)：消息的初始形式；密文( CypherText)：加密后的形式加密算法(Encryption Algorithm):对明文进行加密操作时所采用的一组规则称作加密算法(Encryption Algorithm).解密算法(Decryption Algorithm):接收者对密文解密所采用的一组规则称为解密算法(Decryption Algorithm)密钥(Key):加密和解密算法的操作通常都是在一组密钥的控制下进行的,分别称为加密密钥(Encryption Key) 和解密密钥(Decryption Key).广东技术师范学院-

6、计科院-计算机应用系基本概念(3/4)记：明文记为P且P为字符序列， P=P1,P2,Pn密文记为C, C=C1,C2,Cn明文和密文之间的变换记为 C=E(P)及P=D(C)其中 C表示密文，E为加密算法；P为明文，D为解密算法我们要求密码系统满足：P=D(E(P)广东技术师范学院-计科院-计算机应用系需要密钥的加密算法，记为：C=E(K,P),即密文消息同时依赖于初始明文和密钥的值。实际上，E是一组加密算法，而密钥则用于选择其中特定的一个算法。 加密与解密的密钥相同，即：P=D(K,E(K,P) 加密与解密的密钥不同，则：P=D(KD,E(KE,P)基本概念(4/4)广东技术师范学院-计科

7、院-计算机应用系密码编码系统分类保密内容密钥数量明文处理的方式广东技术师范学院-计科院-计算机应用系保密内容受限制的（restricted)算法算法的保密性基于保持算法的秘密 基于密钥（key-based)的算法算法的保密性基于对密钥的保密广东技术师范学院-计科院-计算机应用系密钥数量对称密码算法（symmetric cipher)加密密钥和解密密钥相同，或实质上等同，即从一个易于推出另一个又称秘密密钥算法或单密钥算法非对称密钥算法（asymmetric cipher)加密密钥和解密密钥不相同，从一个很难推出另一个又称公开密钥算法（public-key cipher) 公开密钥算法用一个密钥进

8、行加密, 而用另一个进行解密其中的加密密钥可以公开,又称公开密钥（public key)，简称公钥。解密密钥必须保密,又称私人密钥（private key)私钥，简称私钥广东技术师范学院-计科院-计算机应用系明文处理方式分组密码（block cipher)将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出也是固定长度的密文。流密码（stream cipher)又称序列密码。序列密码每次加密一位或一字节的明文。广东技术师范学院-计科院-计算机应用系对称密码又名： 传统加密 / 单钥加密/私钥加密 发送方和接收方共享同一个密钥几乎所有的经典加密算法都是这种类型在70年代公钥密码体制被发明之

9、前这是唯一的密码类型。广东技术师范学院-计科院-计算机应用系对称密码简化模型广东技术师范学院-计科院-计算机应用系要求对称密码要安全使用有两个要求:加密算法足够强密钥仅为发送者和接受者知道Y = EK(X)X = DK(Y)加密算法是开放的,大家都知道.所以安全性取决于密钥有安全的通道发放密钥。广东技术师范学院-计科院-计算机应用系密码编码学特征:所使用的加密运算p代换(替换) / 置换密钥数量p单密钥 或私钥 /两个密钥或公钥处理明文的方法p分组 / 流广东技术师范学院-计科院-计算机应用系密码分析试图破译单条消息试图识别加密的消息格式，以便借助直接的解密算法破译后续的消息试图找到加密算法中

10、的普遍缺陷(无须截取任何消息)广东技术师范学院-计科院-计算机应用系密码分析的条件与工具已知加密算法截取到明文、密文中已知或推测的数据项数学或统计工具和技术语言特性计算机技巧与运气广东技术师范学院-计科院-计算机应用系攻击传统密码方法密码分析学穷举攻击广东技术师范学院-计科院-计算机应用系密码分析类型广东技术师范学院-计科院-计算机应用系穷举攻击试遍所有密钥直到有一个合法的密钥能够把密文还原成为明文,就是穷举攻击.广东技术师范学院-计科院-计算机应用系Brute Force Search穷举攻击与密钥的长度正比 假设知道或者能够辨认是否明文广东技术师范学院-计科院-计算机应用系更多定义无条件安

11、全：无论提供的密文有多少，如果由一个加密方案产生的密文中包含的信息不足以唯一地决定对应的明文除了一次一密的方案外，没有无条件安全的算法安全性体现在：破译的成本超过加密信息的价值破译的时间超过该信息有用的生命周期满足这两个条件: 计算上是安全的广东技术师范学院-计科院-计算机应用系第2.1章 经典加密技术替代置换转子机广东技术师范学院-计科院-计算机应用系替代明文的字母由其它字母或数字或符号代替若该明文被视为一个比特序列，则替代涉及到用密文比特模式代替明文比特模式广东技术师范学院-计科院-计算机应用系Caesar 密码已知最早的代换加密算法由 Julius Caesar 发明首先用于军事中Ci=

12、E(Pi)=Pi+3例子:meet me after the toga partyPHHW PH DIWHU WKH WRJD SDUWB广东技术师范学院-计科院-计算机应用系Caesar Cipher定义替换如下: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 zD E F G H I J K L M N O P Q R S T U V W X Y Z A B C给每个字母赋一个数a 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

13、14 15 16 17 18 19 20 21 22 23 24 25则 Caesar 密码如下进行:C = E(p) = (p + k) mod (26)p = D(C) = (C k) mod (26)广东技术师范学院-计科院-计算机应用系恺撒密码的特点单字母密码（简单替换技术）简单，便于记忆缺点：结构过于简单，密码分析员只使用很少的信息就可预言加密的整个结构广东技术师范学院-计科院-计算机应用系分析Caesar Cipher 仅有26种可能替换A 映射到 A,B,.Z 可以循环试验 使用 brute force search 仅仅需要能认识明文即可例如. 解密 ciphertext GC

14、UA VQ DTGCM例:PHHW PH DIWHU WKH WRJD SDUWB1oggv og chvgt vjg vqic rctva2nffu nf bgufs uif uphb qbsuz3meet me after the toga party4ldds ld zesdq sgd snfz ozqsx5678925qiix qi ejxiv xli xske tevxc广东技术师范学院-计科院-计算机应用系改进：单表代换密码不仅仅将字母移位 对字母进行无规则的重新排列对字母进行无规则的重新排列因此密钥是 26 字母长 明文: abcdefghijklmnopqrstuvwxyz 密

15、文: DKVQFIBJWPESCXHTMYAUOLRGZN明文文本: ifwewishtoreplaceletters密文文本: WIRFRWAJUHYFTSDVFSFUUFYA 广东技术师范学院-计科院-计算机应用系任意替换：26！4x1026 可能的key，大于56位DES的密钥空间。基于语言统计规律仍可破译单表代换密码广东技术师范学院-计科院-计算机应用系单表代换密码安全性共有 26! = 4 x 1026 密钥 有这么多密钥应该安全了吧！ !WRONG! 问题是人类语言的统计特性广东技术师范学院-计科院-计算机应用系语言的冗余特性人类语言是冗余的 例如 th lrd s m shphr

16、d shll nt wnt 每个字母被使用的频率不相同 在英语中 e 是被用的最多的字母 接着是 T,R,N,I,O,A,S 其他的字母用的很少 。例如 Z,J,K,Q,X 有单个字母，两个字母和三个字母出现的频率表 广东技术师范学院-计科院-计算机应用系英语中字母出现的频率广东技术师范学院-计科院-计算机应用系密码分析学中的应用单表替换不改变统计特性 由阿拉伯科学家在9世纪发现这个规律计算密文中每个字母出现的频率然后与已知的统计特性相比较 对于 Caesar 密码来说寻找最常出现的和最不常出现的字母 最常出现: E,T,R,N,I,O,A,S最不常出现: JK, X-Z对于单表替换要确认每个

17、字母的对应关系可以使用最常出现的那些单个字母，双字母对和三字母对。广东技术师范学院-计科院-计算机应用系解密例子给定密文:UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ计算每个字母出现的相对频率 猜测 P & Z 对应 e & t假设 ZW 是 th ，因此 ZWP 就是the继续试验可以得到下面的明文:it was disclosed yesterday that several informal b

18、utdirect contacts have been made with politicalrepresentatives of the viet cong in moscow例：例：UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ广东技术师范学院-计科院-计算机应用系Playfair 密码在单表替换中长密钥并没有提供足够的理想的安全性 增强安全性的一个途径是对多个字母组合进行加密 Playfair 密

19、码就是这样做的密码就是这样做的由 Charles Wheatstone在 1854发明, 但是由他的朋友 Baron Playfair 名字命名广东技术师范学院-计科院-计算机应用系Playfair 密钥矩阵是一个 由密钥决定的5X5矩阵首先填入密钥矩阵剩余部分填入其他的字母例如. 使用密钥 MONARCHYMONARCHYBDEFGIKLPQSTUVWXZ广东技术师范学院-计科院-计算机应用系加密和解密算法广东技术师范学院-计科院-计算机应用系Playfair 密码的安全性相对于单表替换密码来说安全性增强了有 26 x 26 = 676 字母对 需要对 676 字母对进行分析 因此生成的密文

20、更复杂 被广泛的使用的了很多年 (例如. US & British military in WW1) 给定几百个密文就能被破解 因为他还是保留了明文的结构 广东技术师范学院-计科院-计算机应用系广东技术师范学院-计科院-计算机应用系题目当海军上尉John F .Kennedy下令日本毁灭者击沉美国巡逻艇PT-109时，澳大利亚的无线站截获了一条用Playfair密码加密的消息：KXJEY UREBE ZWEHE WRYTU HEYFSKREHE GOYFI WTTTU OLKSY CAJPOBOTEI ZONTX BYBWT GONEY CUZWRGDSON SXBOU YWRHE BAAHY

21、 USEDQ密钥为royal new zealand navy。请解密这条消息。广东技术师范学院-计科院-计算机应用系Plyafair解答(1/4)加密步骤：1.填充5*5矩阵2.落在矩阵同一行的明文字母对由其右边的字母代换3.落在矩阵同一列的明文字母对由其下面的字母代换4.其他的每组明文字母对按如下方式变换：它所在的行是该字母的行，列则为另一字母所在的列广东技术师范学院-计科院-计算机应用系Plyafair解答(2/4)解密步骤：1.填充5*5矩阵2.落在矩阵同一行的明文字母对由其左边的字母代换3.落在矩阵同一列的明文字母对由其上边的字母代换4.其他的每组明文字母对按如下方式变换：它所在的行

22、是该字母的行，列则为另一字母所在的列广东技术师范学院-计科院-计算机应用系Plyafair解答(3/4)密钥： royal new zealand navy去掉空格，去掉重复字母：royalynewzdv构造5*5矩阵R O Y A LN E W Z DV B C F GH I/J K M PQ S T U X广东技术师范学院-计科院-计算机应用系Plyafair解答(4/4)明文分组，每两个一组：KX JE YU RE BE ZW EH EW RY TU HE YF SK RE HE GO YF IW TT TU OL KS YC AJ PO BO TE IZ ON TX BY BW TG

23、ON EY CU ZW RG DS ON SX BO UY WR HE BA AH YU SE DQ每组进行解密：PT BO AT ON EO WE NI NE LO ST IN AC TI ON IN BL AC KE TT ST RA IT TW OM IL ES SW ME RE SU CO VE XC RE WO FT WE LV EX RE QU ES TA NY IN FO RM AT IO NX重新组合，得到：PT BOAT ONE OWE NINE LOST IN ACTION IN BLACKETT STRAIT TWO MILES SW MERESU COVE X CREW

24、 OF TWELVE X REQUEST ANY INFORMATION X广东技术师范学院-计科院-计算机应用系多表代换密码另一种增强安全性的方法是 使用多表替换 破坏统计特性使用相关的单表代换规则用密钥选择决定使用那个代换表 广东技术师范学院-计科院-计算机应用系Vigenre Cipher 明文密钥 密文 a b c d e f g h i j k l m n o y zabcdefghijklmnoZA B C D E F G H I J K L M N O Y ZB C D E F G H I J K L M N O P Z AC D E F G H I J K L M N O P

25、R A BD E F G H I J K L M N O P R S B CE F G H I J K L M N O P R S T C DF G H I J K L M N O P R S T U D EG H I J K L M N O P R S T U V E F H I J K L M N O P R S T U V W F G I J K L M N O P R S T U V W X G H J K L M N O P R S T U V W X Y H I K L M N O P R S T U V W X Y Z I J L M N O P R S T U V W X Y

26、Z A J K M N O P R S T U V W X Y Z A B K L N O P R S T U V W X Y Z A B C L M O P R S T U V W X Y Z A B C D M NZ A B C D E F G H I J K L M N X Y广东技术师范学院-计科院-计算机应用系Vigenre Cipher维吉尼亚密本加密 举例：若我们选用明文为：Vigenere ciphere，密钥则选用以上26个字母所组成的任一单词或词组如：radio。见下表：p相同字母加密为不同的密文(如字母e)p不同的字母加密为相同的密文(如字母H)广东技术师范学院-计科院-

27、计算机应用系例子例如使用密钥 deceptive密钥: deceptivedeceptivedeceptive明文: wearediscoveredsaveyourself密文: ZICVTWQNGRZGVTWAVZHCQYGLMGJ 广东技术师范学院-计科院-计算机应用系广东技术师范学院-计科院-计算机应用系Hill密码C1=(K11P1+K12P2+K13P3)mod26C2=(K21P1+K22P2+K23P3)mod26C3=(K31P1+K32P2+K33P3)mod26C=KPHill完全隐藏了单字母的频率，如果m=3，也隐藏了两个字母的频率攻击：广东技术师范学院-计科院-计算机应

28、用系题目构造一个用选择明文破译Hill密码算法的例子。广东技术师范学院-计科院-计算机应用系一次一密如果每次加密都用与明文一样长的真随机密钥，将是最安全的。 叫做一次一密，每个密钥只能用一次。这是无法破解的！缺点生产大规模随机密钥有实际困难密钥的分配与保护困难广东技术师范学院-计科院-计算机应用系置换密码现在看看一种新的密码：置换密码 通过调整字母的顺序来保密 没有替换原有的字母广东技术师范学院-计科院-计算机应用系置换密码一种更复杂的方法把明文按照给定的列数一行行的写入然后根据密钥调整列Key: 4 3 1 2 5 6 7Plaintext: a t t a c k p o s t p o

29、n e d u n t i l t w o a m x y zCiphertext: TTNAAPTMTSUOAODWCOIXKNLYPETZ 广东技术师范学院-计科院-计算机应用系广东技术师范学院-计科院-计算机应用系乘积密码由于语言的统计特性使得使用替换或置换进行加密并不安全可以交替的使用多种加密方式: 两种替换得到更复杂的替换结果 两种置换得到更复杂的置换结果 替换后再进行置换得到的结果相对更复杂！ 这种思想是从经典密码到现代密码体制的桥梁！广东技术师范学院-计科院-计算机应用系转子机在现代密码体制发明前转子机是最常见的乘积密码二战中广泛使用German Enigma, Allied H

30、agelin, Japanese Purpleimplemented a very complex, varying substitution cipherused a series of cylinders, each giving one substitution, which rotated and changed after each letter was encryptedwith 3 cylinders have 263=17576 alphabets广东技术师范学院-计科院-计算机应用系ENIGMA广东技术师范学院-计科院-计算机应用系隐写术是加密的一种替代在消息中隐藏信息using only a subset of letters/words in a longer message marked in some wayusing invisible inkhiding in LSB in graphic image or sound file缺点：high overhead to hide relatively few info bits广东技术师范学院-计科院-计算机应用系隐写术广东技术师范学院-计科院-计算机应用系小结我们这章讨论了:一些经典的密码技术和术语单表替代密码利用字母出现的频率进行解密Playfair 密码多表替换密码置换密码乘积密码和转子机隐写术