1古典密码学《现代密码学》第二讲上讲内容回顾 密码学分类 密码学与信息安全的关系本章主要内容 代换密码 置换密码 Hill密码 转轮密码 古典密码的惟密文攻击方法密码分类 代换密码（ substitution ）：代换是古典密码中用到的最基本的处理技巧所谓代换，就是将明文中的一个字母由其它字母、数字或符号替代的一种方法 凯撒密码 仿射密码 单表代换 多表代换 置换密码（ permutation）：将明文字符按照某种规律重新排列而形成密文的过程 Hill密码 转轮密码凯撒密码(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 m n o p q r s t u v w x y Z0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25c = E(p) = (p + k) mod (26)p = D(c) = (c – k) mod (26)明文 p ∈ Z26，密文 c ∈ Z26 ，密钥 k取 [1,25]，只有 25个凯撒密码例 :使用其后的第三个字母代换该字母明文： meet me after the toga party密文： PHHW PH DIWHU WKH WRJD SDUWB恺撒密码的攻击 已知明文和密文、加密和解密算法，需要解同余方程，可以恢复密钥k = (c- p) mod (26)； 穷举攻击：已知密文，且明文为有意义字符，至多尝试 25次，可以恢复明文 .仿射密码（Affine Cipher） 移位密码的扩展明文 p ∈ Z26，密文 c ∈ Z26 ，密钥 k=(a,b) ∈ Z’26× Z26且 gcd(a,26)=1.加密：c = E(p) = (a × p + b) mod 26解密：p = D(c) = (c – b) × a-1mod 26例：令密钥 k=(7,3), 且 gcd(7,26)=1.明文 hot=(7,14,19)加密：(7 × 7 + 3) mod 26 = 0(7 × 14 + 3) mod 26 =23(7 × 19 + 3) mod 26 =6密文为 (0,23,6)=(a,x,g)解密： 7-1=15=-11 mod 26(0- 3) × 15 mod 26 = 7(23- 3) × 15 mod 26 =14(6- 3) × 15 mod 26 =19明文为 (7,14,19)=(h, o,t)仿射密码仿射密码练习：令密钥 k=(9,3), 且 gcd(9,26)=1.明文 hot=(7,14,19)，求加解密过程。
加密：7 *9 +3 =14 mod 2614 *9 +3 =25 mod 2619 *9 +3 =18 mod 269*3-26=1 所以 9-1=3 mod 26解密：（ 14-3） *3 =7 mod 26（ 25-3） *3 =14 mod 26（ 18-3） *3 =19 mod 26 已知两对明文和密文（ p1,c1）和（ p2,c2）、加密和解密算法，需要解 2元同余方程组，可以恢复密钥 k=(a,b)；c1= (a × p1+ b) mod 26c2= (a × p2+ b) mod 26 穷举攻击：已知密文，明文为有意义字符，至多尝试 26*Φ (26)个，可以恢复明文 .仿射密码单表代换密码（Monoalphabetic Cipher） 代换表是 26个字母的任意置换例：加密函数 :NZGRLOUAYMTHXzyxwvutsrqponCSEPWJBIFQVKDmlkjihgfedcba解密函数解密函数:明文明文: if we wish to replace letters密文密文: WI RF RWAJ UH YFTSDVF SFUUFYAyrnictplwdjuzZYXWVUTSRQPONqvbhfoxekamgsMLKJIHGFEDCBA单表代换密码 练习：明文明文: nice work，使用上例中的单表代换，使用上例中的单表代换表，求密文。
表，求密文 密文： X W V F R H Y E单表代换密码 已知明文和密文，可以恢复部分加密函数（解密函数）； 穷举攻击：已知密文，明文为有意义字符，至多尝试 26! = 4 x 1026 个，可以恢复明文代换表的个数为 26！多表代换密码(Polyalphabetic Ciphers)加密明文消息时采用不同的单表代换，由密钥具体决定采用哪个表代换消息，密钥通常是一个词的重复 简化的多表代换密码 ----维吉尼亚密码（Vigenère Cipher ）：由 26个类似 caesar密码的代换表组成多表代换密码 维吉尼亚密码：在长为 m的密码中，任何一个字母可被影射为 26个字母中的一个明文 p ∈ (Z26)m，密文 c ∈ (Z26)m，密钥 k ∈ (Z26)m加密c= (p1+k1 ,,p2+k2 ,,…,pm+km) mod 26;解密p = (c1-k1 ,,c2-k2 ,,…,cm-km) mod 26.多表代换密码 例多表代换密码 练习：明文明文: nice work，密钥：，密钥：hot，求密文 密文： U W V L K H Y Y多表代换密码 已知 m个连续的明文和密文，可以恢复维吉尼亚密码的单表移位量（即密钥）； 穷举攻击：已知密文，明文为有意义字符，至多尝试 26m个，可以恢复明文密钥空间大小是 26^m置换密码 加密变换使得信息元素只有位置变化而形态不变，如此可以打破消息中的某些固定模式（结构）明文 p ∈ (Z26)m，密文 c ∈ (Z26)m，密钥 k ∈ {∏ |定义在 1,2,…,m上的置换 }加密c= (p ∏ (1) ,,p ∏ (2) ,,…,p ∏ (m)) mod 26;解密p = (c ∏-1(1) ,,c ∏-1(2) ,,…,c ∏-1(m)) mod 26.置换密码例 密钥明文： State Key Laboratory of Networking分组： StateK eyLabo ratory ofNetw orking置换： EESLSH SALSES LSHBLE HSYEET HRAEOS425163∏-1(x)654321x246153∏ (x)654321x置换密码 练习：明文明文: nice work求密文和逆置换。
求密文和逆置换Pi(x)X31424321思考：当明文字符不是 4的整数倍怎么办？置换密码 已知多对明文和密文，可以推导置换表（即密钥）； 穷举攻击：已知密文，明文为有意义字符，至多尝试 m！ 个，可以恢复明文分组为 m，至多有 m！个置换希尔密码（Hill cipher）1929年， LesterS. Hill提出明文 p ∈ (Z26)m，密文 c ∈ (Z26)m，密钥 K ∈ {定义在 Z26上 m*m的可逆矩阵 }加密c = p * K mod 26解密p = c * K-1mod 26扩散希尔密码 例希尔密码 置换密码可以看做是希尔密码的特例练习：设 hill密码的密钥如下，求对应置换密码的置换表希尔密码 已知 m组明文和密文、加密和解密算法，需要解 m元同余方程组，可以恢复密钥； 穷举攻击：已知密文，明文为有意义字符，至多尝试 26m*m个，可以恢复明文11 12 1m 11 12 1m 11 12 1mm1 m2 mm m1 m2 mm m1 m2 mmcc c pp p kk kcc c pp p kk k⎡⎤⎡ ⎤⎡⎤⎢⎥⎢ ⎥⎢⎥=⎣⎦⎣ ⎦⎣⎦LLLMMMM M MMM MMMMLLL转轮密码（Rotor Machine） 19世纪 20年代，开始出现机械加解密设备，最典型的是转轮密码机1918年 Arthur Scherbius发明的 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+b mod 26惟密文攻击 统计得到 R(8),D(7),E,H,K(5),S,F,V(4)TSRQPO字母038021频率0457012频率NMLKJIH字母1G0Z2F1Y2E2X5D0W0C4V0B2U5A频率字母频率字母密文出现字母频率统计惟密文攻击 令 R=E(e)， D=E(t)，得到方程组 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 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25解得 a=6 , b= 19 ; 其中 gcd(6,26)=2>1，故猜测错误。
4a b 1719a b 3+ =⎧⎨+ =⎩惟密文攻击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解密得明文： algorithms are quite general definitions of arithmetic processes.惟密文攻击 练习：已知用户用移位密码加密，密文为“KHOOR,HYHUB。