第2讲：古典密码学

1、古典密码学1现代密码学现代密码学第二讲第二讲 密码学密码学(Cryptology)：研究信息系统安全保密的科学。它包含两个分支密码编码学密码编码学(Cryptography)(Cryptography)：对信息进行编码实现隐蔽信息的一门学问：对信息进行编码实现隐蔽信息的一门学问( (明文明文-密文密文) )密码分析学密码分析学(Cryptanalytics)(Cryptanalytics)：研究分析破译密码的学问（密文：研究分析破译密码的学问（密文-明文）明文）密码学的基本概念(2) 明文明文(消息)(Plaintext) ：被隐蔽消息。 密文密文(Ciphertext)或密报密报(Crypt

2、ogram)：明文经密码变换成的一种隐蔽形式。 加密加密(Encryption)：将明文变换为密文的过程。 解密解密(Decryption)：加密的逆过程，即由密文恢复出原明文的过程。 加密员加密员或密码员密码员(Cryptographer)：对明文进行加密操作的人员。密码学的基本概念(3)密码学的基本概念(4) 加密算法加密算法(Encryption algorithm)：密码员对明文进行加密时所采用的一组规则。接收者接收者(Receiver)：传送消息的预定对象。解密算法：解密算法：接收者对密文进行解密时所采用的一组规则。密钥密钥(Key)：控制加密和解密算法操作的数据处理，分别称作加密密

3、钥加密密钥和解密密钥解密密钥。截收者截收者(Eavesdropper)：在信息传输和处理系统中的非受权者，通过搭线窃听、电磁窃听、声音窃听等来窃取机密信息。密码学的基本概念(5) 密码分析密码分析(Cryptanalysis)：截收者试图通过分析从截获的密文推断出原来的明文或密钥。 密码分析员密码分析员(Cryptanalyst)：从事密码分析的人。 被动攻击被动攻击(Passive attack)：对一个保密系统采取截获密文进行分析的攻击。 主动攻击主动攻击(Active attack)：非法入侵者入侵者(Tamper)、攻击者攻击者(Attcker)或黑客黑客(Hacker)主动向系统窜扰

4、，采用删除、增添、重放、伪造等窜改手段向系统注入假消息，达到利已害人的目的。 一个密码系统，通常简称为密码体制，由5部分组成：密码体制基本组成明文空间明文空间M密文空间密文空间C密钥空间密钥空间K加密算法加密算法E解密算法解密算法D信息加密传输的过程w 加密加密: C = E(M,Ke)MCEKeCMKdDw 解密解密: M = D(C, Kd)M-明文 C-密文Ke-加密密钥 Kd-解密密钥E-加密算法 D-解密算法明文加密算法加密密钥K1网络信道解密算法明文解密密钥K2密文用户用户A用户用户B传送给B的信息B收到信息窃听者窃听者CC窃听到的信息窃听到的信息!#$% 根据密钥的使用方式分类根

5、据密钥的使用方式分类 对称密码体制（传统密钥密码体制） 用于加密数据的密钥和用于解密数据的密钥相同，或者二者之间存在着某种明确的数学关系。 加密：EK(M)=C 解密：DK(C)=M 非对称密码体制（公钥密码体制） 用于加密的密钥与用于解密的密钥是不同的，而且从加密的密钥无法推导出解密的密钥。 用公钥KP对明文加密可表示为：EKP(M)=C 用相应的私钥KS对密文解密可表示为：DKS(C)=M密码系统的分类(1) 根据明文和密文的处理方式分类根据明文和密文的处理方式分类 分组密码体制（Block Cipher） 设M为明文，分组密码将M划分为一系列明文块Mi，通常每块包含若干字符，并且对每一块

6、Mi都用同一个密钥Ke进行加密。 M=(M1, M2, ,Mn) ，C=(C1, C2 , ,Cn,)，其中Ci=E(Mi,Ke)， i=1,2,n。 序列密码体制（Stream Cipher） 将明文和密钥都划分为位(bit)或字符的序列，并且对明文序列中的每一位或字符都用密钥序列中对应的分量来加密。 M=(M1, M2, ,Mn) ， Ke=(ke1, ke2,ken)，C=(C1, C2,Cn)，其中Ci=E(mi,kei) ，i=1,2,n。 密码系统的分类(2) 密码分析（破解密码）截收者在不知道解密密钥及通信者所采用的加密体制的细节条件下，对密文进行分析，试图获取机密信息。研究分析

7、解密规律的科学称作密码分析学。密码分析在外交、军事、公安、商业等方面都具有重要作用，也是研究历史、考古、古语言学和古乐理论的重要手段之一。 密码分析密码设计和密码分析是共生的、又是互逆的，两者密切有关但追求的目标相反。两者解决问题的途径有很大差别 密码设计是利用数学来构造密码 密码分析除了依靠数学、工程背景、语言学等知识外，还要靠经验、统计、测试、眼力、直觉判断能力，有时还靠点运气。 密码分析方法分析法 确定性分析法确定性分析法 利用一个或几个已知量(比如，已知密文或明文-密文对)用数学关系式表示出所求未知量(如密钥等)。已知量和未知量的关系视加密和解密算法而定，寻求这种关系是确定性分析法的关

8、键步骤。 统计分析法统计分析法 利用明文的已知统计规律进行破译的方法。密码破译者对截收的密文进行统计分析，总结出其间的统计规律，并与明文的统计规律进行对照比较，从中提取出明文和密文之间的对应或变换信息。 密码可能经受的攻击攻击类型攻击者拥有的资源惟密文攻击v加密算法v截获的部分密文已知明文攻击v加密算法，v截获的部分密文和相应的明文选择明文攻击v加密算法v加密黑盒子，可加密任意明文得到相应的密文选择密文攻击v加密算法v解密黑盒子，可解密任意密文得到相应的明文 密码分析方法-穷举破译法 对截收的密报依次用各种可解的密钥试译，直到得到有意义的明文；一般来说，要获取成功必须尝试所有可能密钥的一半。

9、或在不变密钥下，对所有可能的明文加密直到得到与截获密报一致为止，此法又称为完全试凑法完全试凑法(Complete trial-and-error Method)。 只要有足够多的计算时间和存储容量，原则上穷举法总是可以成功的。但实际中，任何一种能保障安全要求的实用密码都会设计得使这一方法在实际上是不可行的。 古典密码分类 代换密码（ substitution ）：代换是古典密码中用到的最基本的处理技巧。所谓代换，就是将明文中的一个字母由其它字母、数字或符号替代的一种方法。 凯撒密码 仿射密码 单表代换 多表代换 置换密码（permutation）：将明文字符按照某种规律重新排列而形成密文的过程

10、。l一种早期的 希腊变换密码l一张纸条环绕在一个圆柱上 l消息沿着圆柱横写l纸条上的字母看起来是一些随机字母l并不十分安全，密钥是纸条和圆柱的宽度凯撒密码(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凯撒密码例:使用其后的第三个字母代换该字母明文：meet me after the toga party密文：PHHW PH DIWHU WKH WRJD SDU

11、WB恺撒密码的攻击用数字表示每个字母：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个 已知明文和密文、加密和解密算法，需要解同余方程，可以恢复密钥 k = (c- p) mod (26)； 穷举攻击：已知密文，且明文为有意义字符，至多尝试25次

12、，可以恢复明文.3.密码分析（Cryptanalysis of Caesar ciphers） A maps to A,B,.Z 可以简单的实验每个密钥（穷密钥搜索） 给定一些密文，实验每个密钥。 LIZHZLVKWRUHSODFHOHWWHUV Original ciphertext KHYGYKUJVQTGRNCEGNGVVGTU try shift of 1 JGXFXJTIUPSFQMBDFMFUUFST try shift of 2 IFWEWISHTOREPLACELETTERS try shift of 3 * plaintext HEVDVHRGSNQDOKZBDKDSSDQR

13、 try shift of 4 GDUCUGQFRMPCNJYACJCRRCPQ try shift of 5 . MJAIAMWLXSVITPEGIPIXXIVW try shift of 25 eg. break ciphertext GCUA VQ DTGCM 仿射密码（Affine Cipher） 移位密码的扩展明文p Z26，密文c Z26 ，密钥k=(a,b) Z26 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

14、. 明文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)仿射密码 已知两对明文和密文（p1,c1）和（p2,c2）、加密和解密算法，需要解2元同余方程组，可以恢复密钥k=(a,b)；c1 = (a p1 + b) mod 26c2 = (a p2 +

15、b) mod 26 穷举攻击：已知密文，明文为有意义字符，至多尝试26*(26)个，可以恢复明文.单表代换密码 代换表是26个字母的任意置换 例：加密函数:n o p q r s t u v wx y zX HT MY A UOL R GZ Na b c d e f g h i j k l mDK V QF I B J WP E S CNOP QR S T U V WX Y Zz u j d wl p t c i n r yA B C DE FGH I J K L Ms g ma k ex o f h b v q单表代换密码 已知明文和密文，可以恢复部分加密函数（解密函数）； 穷举攻击：已知密

16、文，明文为有意义字符，至多尝试26! = 288个，可以恢复明文代换表的个数为26！一般单表代换密码简单的方法给出密钥写出密钥（删除重复字母）write key (with repeated letters deleted) 在其下面依次写出剩余字母（以横、纵行）按列读取字母得到密文。then read off by columns to get ciphertext equivalents 举例给定密钥字 STARWARS 去掉重复字母得到 STARW 填写剩余字母： STARW BCDEF GHIJK LMNOP QUVXY Z 按列读取字母得到密文 Plain: ABCDEFGHIJKL

17、MNOPQRSTUVWXYZ Cipher: SBGLQZTCHMUADINVREJOXWFKPY 可以用这个密钥加密、解密 例如 Plaintext: I KNOW ONLY THAT I KNOW NOTHING Ciphertext: H UINF NIAP OCSO H UINF INOCHIT 多表代换密码(Polyalphabetic Ciphers) 加密明文消息时采用不同的单表代换，由密钥具体决定采用哪个表代换消息，密钥通常是一个词的重复。 简化的多表代换密码 -维吉尼亚密码（ Vigenre Cipher ）：由26个类似 caesar密码的代换表组成多表代换密码 维吉尼亚密

18、码：在长为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，求密文.多表代换密码 已知m个连续的明文和密文，可以恢复维吉尼亚密码的单表移位量（即密钥）； 穷举攻击：已知密文，明文为有意义字符，至多尝试26m 个，可以恢复明文密钥空间大小是26m置换密码 加密变换使得信息元素只有位置变化而形态不变，如此可以打破消息中

19、的某些固定模式（结构） 明文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.置换密码例 密钥明文：she sells sea shells by the sea shore分组：shesel lsseas hellsb ythese ashore置换：EESLSH SALSES LSHBLE HSYEET HRAEOS置换密码X1234Pi(x)2413置换密码 已知多对明文和密文，可以推导置换表

20、（即密钥）； 穷举攻击：已知密文，明文为有意义字符，至多尝试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-1 mod 26扩散希尔密码 例希尔密码 置换密码可以看做是希尔密码的特例。练习：设hill密码的密钥如下，求对应置换密码的置换表。希尔密码 已知m组明文和密文、加密和解密算法，需要解m元同余方程组，可以恢复密钥； 穷举攻击：已知密文，明文为有意义字符，至多尝试

21、26m*m个，可以恢复明文11121m11121m11121mm1m2mmm1m2mmm1m2mmcccpppkkkcccpppkkk9。ADFGVX 乘积密码 这样命名是因为变换仅依赖与 ADFGVX 在WW1有德国人使用，并被英国人破译 方法： 使用一个固定的替换表，把每个明文字母映射成一个字母对 (row-col index) 在用一个带密钥的块变换把每个对分解then 利用带密钥的块变换写下所有字母对 写出密文（按块密码形式）ADFGVX Substitution Table A D F G V X A K Z W R 1 F D 9 B 6 C L 5 F Q 7 J P G X G

22、 E V Y 3 A N V 8 O D H 0 2 X U 4 I S T M 11。 ADFGVX ADFGVX 加密举例加密举例 Plaintext: PRODUCTCIPHERS Intermediate Text: FG AG VD VF XA DG XV DG XF FG VG GA AG XG 带密钥的块变换矩阵： D E U T S C H Key 2 3 7 6 5 1 4 Sorted Order F G A G V D V F X A D G X V D G X F F G V G G A A G X G Ciphertext: DXGX FFDG GXGG VVVG V

23、GFG CDFA AAXA 转轮密码（Rotor Machine） 19世纪20年代，开始出现机械加解密设备，最典型的是转轮密码机 1918年Arthur Scherbius发明的EIGMA，瑞典Haglin发明的Haglin，和日军发明的“紫密”和“兰密”都属于转轮密码机。转轮密码Enigma密码机密码机转轮密码Dan BonehRotor Machines (cont.)Most famous: the Enigma (3-5 rotors)# keys = 264 = 218 (actually 236 due to plugboard) 惟密文攻击 在攻击者可以截获（足够）明密文的条件下，易于恢复用户的密钥； 当攻击者只能窃听到密文时，若明文是有意义的（一段话等具有可读性）字符时，利用穷举搜索，可以通过密文解密出对应明文，继而恢复密钥。（穷举搜索的复杂度取决于密钥空间的大小，古典密码体制的密钥空间通常比较小。）惟密文攻击人类的语言存在冗余，以英文文档为例 字母 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为起始字