第2.1章 古典密码学

1、第2章 密码学概论古典密码学对称密码体制公钥密码体制日暮苍山兰舟小日暮苍山兰舟小 本无落霞缀清泉 去年叶落缘分定 死水微漾人却亡隐写术加密系统模型密码学发展阶段1949年之前密码学是一门艺术19491975年密码学成为科学1976年以后密码学的新方向公钥密码学第1阶段古典密码(1/3)密码学还不是科学，而是艺术出现一些密码算法和加密设备密码算法的基本手段是代换(substitution)和置换(permutation)，针对的是字符简单的密码分析手段出现主要特点：数据的安全基于算法的保密20世纪早期密码机第1阶段古典密码(2/3)第1阶段古典密码(3/3)1883年Kerchoffs第一次明确

2、提出了编码的原则：加密算法应建立在算法的公开不影响明文和密钥的安全。这一原则已得到普遍承认，成为判定密码强度的衡量标准，实际上也成为传统密码和现代密码的分界线。第2阶段 19491975(1/1)计算机使得基于复杂计算的密码成为可能相关技术的发展1949年Shannon的“The Communication Theory of Secret Systems”提出了两种“安全”，即“理论安全”和“实际安全”，证明了要达到“理论安全”，密钥的长度必须长于或等于明文的长度1967年David Kahn的The Codebreakers1971-73年IBM Watson实验室的Horst Feist

3、el等几篇技术报告主要特点：数据的安全基于密钥而不是算法的保密 第3阶段 19761977年DES正式成为标准80年代出现“过渡性”的“Post DES”算法，如IDEA、RCx、CAST等90年代对称密钥密码进一步成熟 Rijndael、RC6、MARS、Twofish、 Serpent等出现2001年Rijndael成为DES的替代者(AES)第3阶段 19761976年：Diffie & Hellman 的 “New Directions in Cryptography” 提出了不对称密钥密1977年Rivest,Shamir & Adleman提出了RSA公钥算法90年代逐步出现椭圆曲

4、线等其他公钥算法主要特点：公钥密码使得发送端和接收端无密钥传输的保密通信成为可能基本概念(1/4)密码学(Cryptology): 是研究信息系统安全保密的科学.密码编码学(Cryptography): 主要研究对信息进行编码,实现对信息的隐蔽.密码分析学(Cryptanalytics):主要研究加密消息的破译或消息的伪造.基本概念(2/4)明文( Plaintext)：消息的初始形式；密文( CypherText)：加密后的形式加密算法(Encryption Algorithm):对明文进行加密操作时所采用的一组规则称作加密算法(Encryption Algorithm).解密算法(Decr

5、yption Algorithm):接收者对密文解密所采用的一组规则称为解密算法(Decryption Algorithm)密钥(Key):加密和解密算法的操作通常都是在一组密钥的控制下进行的,分别称为加密密钥(Encryption Key) 和解密密钥(Decryption Key).基本概念(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),即密文消息同时依赖于

6、初始明文和密钥的值。实际上，E是一组加密算法，而密钥则用于选择其中特定的一个算法。加密与解密的密钥相同，即：P=D(K,E(K,P)加密与解密的密钥不同，则：P=D(KD,E(KE,P)基本概念(4/4)密码编码系统分类保密内容密钥数量明文处理的方式保密内容受限制的（restricted)算法算法的保密性基于保持算法的秘密 基于密钥（key-based)的算法算法的保密性基于对密钥的保密密钥数量对称密码算法（symmetric cipher)加密密钥和解密密钥相同，或实质上等同，即从一个易于推出另一个又称秘密密钥算法或单密钥算法非对称密钥算法（asymmetric cipher)加密密钥和解密

7、密钥不相同，从一个很难推出另一个又称公开密钥算法（public-key cipher) 公开密钥算法用一个密钥进行加密, 而用另一个进行解密其中的加密密钥可以公开,又称公开密钥（public key)，简称公钥。解密密钥必须保密,又称私人密钥（private key)私钥，简称私钥明文处理方式分组密码（block cipher)将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出也是固定长度的密文。流密码（stream cipher)又称序列密码。序列密码每次加密一位或一字节的明文。对称密码又名： 传统加密 / 单钥加密/私钥加密 发送方和接收方共享同一个密钥几乎所有的经典加密算法都是这

8、种类型在70年代公钥密码体制被发明之前这是唯一的密码类型。对称密码简化模型对称密码要求对称密码要安全使用有两个要求:加密算法足够强密钥仅为发送者和接受者知道Y = EK(X)X = DK(Y)加密算法是开放的,大家都知道.所以安全性取决于密钥有安全的通道发放密钥。密码编码学特征:所使用的加密运算代换(替换) / 置换密钥数量单密钥 或私钥 /两个密钥或公钥处理明文的方法分组 / 流密码分析试图破译单条消息试图识别加密的消息格式，以便借助直接的解密算法破译后续的消息试图找到加密算法中的普遍缺陷(无须截取任何消息)密码分析的条件与工具已知加密算法截取到明文、密文中已知或推测的数据项数学或统计工具和

9、技术语言特性计算机技巧与运气攻击传统密码方法密码分析学穷举攻击密码分析类型穷举攻击试遍所有密钥直到有一个合法的密钥能够把密文还原成为明文,就是穷举攻击.Brute Force Search穷举攻击与密钥的长度正比 假设知道或者能够辨认是否明文更多定义无条件安全：无论提供的密文有多少，如果由一个加密方案产生的密文中包含的信息不足以唯一地决定对应的明文除了一次一密的方案外，没有无条件安全的算法安全性体现在：破译的成本超过加密信息的价值破译的时间超过该信息有用的生命周期满足这两个条件: 计算上是安全的第2.1章 经典加密技术替代置换转子机替代明文的字母由其它字母或数字或符号代替若该明文被视为一个比特

10、序列，则替代涉及到用密文比特模式代替明文比特模式Caesar 密码已知最早的代换加密算法由 Julius Caesar 发明首先用于军事中Ci=E(Pi)=Pi+3例子:meet me after the toga partyPHHW PH DIWHU WKH WRJD SDUWBCaesar 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

11、 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 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 仅仅需要能认识明文即可例如. 解

12、密 ciphertext GCUA 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 密文: DKVQFIBJWPESCX

13、HTMYAUOLRGZN明文文本: ifwewishtoreplaceletters密文文本: WIRFRWAJUHYFTSDVFSFUUFYA 任意替换：26！41026 可能的key，大于56位DES的密钥空间。基于语言统计规律仍可破译单表代换密码单表代换密码安全性共有 26! = 4 x 1026 密钥 有这么多密钥应该安全了吧！!WRONG! 问题是人类语言的统计特性语言的冗余特性人类语言是冗余的 例如 th lrd s m shphrd shll nt wnt 每个字母被使用的频率不相同 在英语中 e 是被用的最多的字母 接着是 T,R,N,I,O,A,S 其他的字母用的很少 。例如

14、 Z,J,K,Q,X 有单个字母，两个字母和三个字母出现的频率表 英语中字母出现的频率密码分析学中的应用单表替换不改变统计特性 由阿拉伯科学家在9世纪发现这个规律计算密文中每个字母出现的频率然后与已知的统计特性相比较 对于 Caesar 密码来说寻找最常出现的和最不常出现的字母 最常出现: E,T,R,N,I,O,A,S最不常出现: JK, X-Z对于单表替换要确认每个字母的对应关系可以使用最常出现的那些单个字母，双字母对和三字母对。解密例子给定密文:UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQ

15、UZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ计算每个字母出现的相对频率 猜测 P & Z 对应 e & t假设 ZW 是 th ，因此 ZWP 就是the继续试验可以得到下面的明文:it was disclosed yesterday that several informal butdirect contacts have been made with politicalrepresentatives of the viet cong in moscow例：UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSX

16、AIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQPlayfair 密码在单表替换中长密钥并没有提供足够的理想的安全性 增强安全性的一个途径是对多个字母组合进行加密 Playfair 密码就是这样做的由 Charles Wheatstone在 1854发明, 但是由他的朋友 Baron Playfair 名字命名Playfair 密钥矩阵是一个由密钥决定的55矩阵首先填入密钥矩阵剩余部分填入其他的字母例如. 使用密钥 MONARCHYMONARCHYBDEFGIKLPQSTUVWXZ加密和

17、解密算法Playfair 密码的安全性相对于单表替换密码来说安全性增强了有 2626 = 676 字母对 需要对 676 字母对进行分析 因此生成的密文更复杂 被广泛的使用的了很多年 (例如. US & British military in WW1) 给定几百个密文就能被破解 因为他还是保留了明文的结构 题目当海军上尉John F .Kennedy下令日本毁灭者击沉美国巡逻艇PT-109时，澳大利亚的无线站截获了一条用Playfair密码加密的消息：KXJEY UREBE ZWEHE WRYTU HEYFSKREHE GOYFI WTTTU OLKSY CAJPOBOTEI ZONTX BY

18、BWT GONEY CUZWRGDSON SXBOU YWRHE BAAHY USEDQ密钥为royal new zealand navy。请解密这条消息。Plyafair解答(1/4)加密步骤：1.填充55矩阵2.落在矩阵同一行的明文字母对由其右边的字母代换3.落在矩阵同一列的明文字母对由其下面的字母代换4.其他的每组明文字母对按如下方式变换：它所在的行是该字母的行，列则为另一字母所在的列Plyafair解答(2/4)解密步骤：1.填充5*5矩阵2.落在矩阵同一行的明文字母对由其左边的字母代换3.落在矩阵同一列的明文字母对由其上边的字母代换4.其他的每组明文字母对按如下方式变换：它所在的行是

19、该字母的行，列则为另一字母所在的列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 XPlyafair解答(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 ON EY CU ZW RG DS ON SX BO UY WR HE BA

20、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 OF TWELVE X REQUEST ANY INFORMATION X多

21、表代换密码另一种增强安全性的方法是 使用多表替换 破坏统计特性使用相关的单表代换规则用密钥选择决定使用那个代换表 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 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

22、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 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

23、 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 YVigenre Cipher维吉尼亚密本加密 举例：若我们选用明文为：Vigenere ciphere，密钥则选用以上26个字母所组成的任一单词或词组如：radio。见下表：相同字母加密为不同的密文(如字母e)不同的字母加密为相同的密文(如字母H)例子例如使用密钥 deceptive密钥: deceptivedeceptivedeceptive明文: wearediscoveredsaveyourself密文: ZICVTWQNGRZGVTWAVZHCQYGLMGJ Hill密码C1=(K11P1+K12P2+K13P3)mod26C2=(K21P1+K22P2+K23P3)mod26C3=(K31P1+K32P2+K33P3)mod26C=KPHill完全隐藏了单字母的频率，如果m=3，也隐藏了两个字母的频率攻击：题目构造一个用选择明文破译H