第3章 古典密码技术

1、第第3 3章章 古典密码技术古典密码技术1第第3 3章古典密码技术章古典密码技术本章内容本章内容 代换密码技术代换密码技术 置乱密码技术置乱密码技术 密码分析技术密码分析技术第第3 3章章 古典密码技术古典密码技术2第第3 3章古典密码技术章古典密码技术教学要求教学要求 掌握单表和多表代换密码技术掌握单表和多表代换密码技术 了解置乱密码技术和典型的古典密码了解置乱密码技术和典型的古典密码 了解密码分析的基本概念了解密码分析的基本概念 掌握移位密码和仿射密码的破译方法掌握移位密码和仿射密码的破译方法第第3 3章章 古典密码技术古典密码技术3英文字母与数字的对应关系英文字母与数字的对应关系 明文明

2、文小写字母小写字母密文密文大写字母大写字母第第3 3章章 古典密码技术古典密码技术43.1 3.1 代换密码技术代换密码技术（substitution ciphersubstitution cipher）原理原理使用代换技术实现保密使用代换技术实现保密明文中的字母由其他字母、数字或明文中的字母由其他字母、数字或符号所取代符号所取代具体的代换方案称为密钥具体的代换方案称为密钥类型类型单表代换单表代换多表代换多表代换第第3 3章章 古典密码技术古典密码技术5一、单表代换密码一、单表代换密码特点特点只有一张代换表只有一张代换表相同的明文加密为相同的密文相同的明文加密为相同的密文种类种类一般代换密码一

3、般代换密码特殊代换密码特殊代换密码移位密码移位密码仿射密码仿射密码第第3 3章章 古典密码技术古典密码技术6一、单表代换密码一、单表代换密码1 1、一般代换密码、一般代换密码任意指定字符间的代换关系任意指定字符间的代换关系2626个英文字母的任意代换有个英文字母的任意代换有26！ 41026种种一种代换方案一种代换方案明文：明文：s su ub bs st ti it tu ut ti ionconci ipherpher密文：密文：L LP PH HL LA AE EA AP PA AE EDIKDIKE EONQV ONQV 相同的明文加密相同的明文加密为相同的密文！为相同的密文！密钥量大

4、，但不便记忆和使用。密钥量大，但不便记忆和使用。第第3 3章章 古典密码技术古典密码技术7一、单表代换密码一、单表代换密码1 1、一般代换密码、一般代换密码一种使用密钥字一种使用密钥字communicationcommunication 的代换方案的代换方案明文：明文：substitutionciphersubstitutioncipher密文：密文：QSOQRBRSRBJHMBKTNPQSOQRBRSRBJHMBKTNP 剔除后来重复的字母后，剔除后来重复的字母后，真正的密钥为：真正的密钥为：comuniat comuniat 便于记忆和使用，但便于记忆和使用，但密钥量大大减少！密钥量大大减

5、少！第第3 3章章 古典密码技术古典密码技术82 2、移位密码、移位密码（shift cipher） 符号：明文符号：明文p，密文，密文c，密钥，密钥k 加密：加密： 解密：解密： 密钥量密钥量 kq=26( )(mod26)kceppk( )(mod26)kpdcckk=3k=3时为时为恺撒密码恺撒密码CaesarCaesar。密文字母是明文字母的移位密文字母是明文字母的移位-代换的特例代换的特例第第3 3章章 古典密码技术古典密码技术9CaesarCaesar密码密码(k=3)(k=3)举例举例( )3 (mod26)kcepp( )3 (mod26)kpdcc第第3 3章章 古典密码技术

6、古典密码技术103 3、仿射密码、仿射密码 ( (affine cipheraffine cipher) ) 加密：加密： 解密：解密：12()(mod 26)kcepk pk112( )() (mod 26)kpdckck1111111 (mod26)kkk k为 的乘法逆，满足：1)26,gcd(1k12(k ,k )k 密钥第第3 3章章 古典密码技术古典密码技术11仿射密码的密钥量与乘法逆元仿射密码的密钥量与乘法逆元k1-11)26,gcd(1k12 26312qk 密钥量密钥量 k k1 1：1 1，3 3，5 5，7 7，9 9，1111，1515，1717，1919，2121，2

7、323，2525 k k2 2：0 02525k k1 1的乘法逆（的乘法逆（mod 26mod 26）1-1=1, 3-1=9, 5-1=21, 7-1=15, 9-1=3, 11-1=19, 15-1=7, 17-1=23, 19-1=11, 21-1=5, 23-1=17, 25-1=25第第3 3章章 古典密码技术古典密码技术12仿射密码加密实例仿射密码加密实例 密钥：密钥： 加密函数：加密函数： 解密函数：解密函数： 明文：明文：cryptography 加密、解密过程加密、解密过程 )7,3(k()73 (mod 26)kcepp( )15(3) (mod 26)kpdcc1117

8、(mod 26)15k第第3 3章章 古典密码技术古典密码技术13()73 (mod 26)kcepp( )15(3) (mod 26)kpdcc明文字符明文字符y y（2424）的加密、解密过程：）的加密、解密过程： 加密：加密：7 724+3=17115=P 24+3=17115=P （mod 26mod 26） 解密：解密：1515（15-315-3）=15=1512=18024=y 12=18024=y （mod 26mod 26） 第第3 3章章 古典密码技术古典密码技术14试一试 假设k1=7，k2=3，明文为secret，利用仿射密码算法给出对应的密文 （18,4,2,17,4,

9、19）第第3 3章章 古典密码技术古典密码技术15单表代换密码的缺点单表代换密码的缺点 密钥量一般比较小，难以抵抗穷尽搜索攻击密钥量一般比较小，难以抵抗穷尽搜索攻击 即使密钥量很大，但因为没有将明文字母出现的频即使密钥量很大，但因为没有将明文字母出现的频率掩藏起来，所以也很容易受到率掩藏起来，所以也很容易受到频数分析法频数分析法的攻击的攻击明、密文字母的频数再现明、密文字母的频数再现第第3 3章章 古典密码技术古典密码技术16二、多表代换密码二、多表代换密码特点特点有多张代换表有多张代换表相同的明文可以加密为不同的密文相同的明文可以加密为不同的密文保密性能较好保密性能较好典型密码典型密码维吉尼

10、亚密码维吉尼亚密码希尔密码希尔密码第第3 3章章 古典密码技术古典密码技术171 1、维吉尼亚密码、维吉尼亚密码（Vigenere cipherVigenere cipher） 二、多表代换密码二、多表代换密码密钥密钥K=（k1,k2,kn）明文明文P=（p1,p2,pn）密文密文C=（c1,c2,cn）加密：加密： ci=pi+ki （mod 26）解密：解密： pi=ci-ki (mod 26)本质：本质： 多个移位密码多个移位密码密钥量：密钥量：n n位密钥位密钥密钥一般是一个密钥一般是一个单词或一句话去单词或一句话去除后面的重复字除后面的重复字母后构成母后构成)!26(!26nkq第第

11、3 3章章 古典密码技术古典密码技术18维吉尼亚密表维吉尼亚密表第第3 3章章 古典密码技术古典密码技术19维吉尼亚密码举例维吉尼亚密码举例密钥字：密钥字：common明文：明文：cryptography真正密钥：真正密钥：comn（4位分组）位分组）相同的明相同的明文有了不文有了不同的密文同的密文第第3 3章章 古典密码技术古典密码技术202 2、希尔密码、希尔密码 （Hill cipherHill cipher） 明文：明文： 密文：密文： 密钥：密钥：由数学家由数学家Lester HillLester Hill于于19291929年发明年发明二、多表代换密码二、多表代换密码dpppp,2

12、1dcccc,21ddddddkkkkkkkkkk212221212111k k必须满足的条件必须满足的条件 非奇异矩阵，即非奇异矩阵，即|K|K| 0 0； gcd(|K|,26)=1 mod 26gcd(|K|,26)=1 mod 26。第第3 3章章 古典密码技术古典密码技术212 2、希尔密码、希尔密码 加密：加密：mod 26cp k1121121222121212,(mod 26)ddddddddkkkkkkc ccp ppkkk1122mod 26jjjdjdcpkpkpk第第3 3章章 古典密码技术古典密码技术222 2、希尔密码、希尔密码 解密：解密：111211212221

13、21212,(mod 26)ddddddddkkkkkkp ppc cckkk1mod 26pck)26(mod11Ikkkk)26(mod| /*1*1kkkkk*( 1)|(mod 26)ijjiijkk 1*|ijjiijjiIkkkkkkkkkk： 主对角线单位矩阵：的逆矩阵| |：的行列式值：去掉第 行第 列元素后的行列式值：的伴随矩阵： 中第 行第 列的元素第第3 3章章 古典密码技术古典密码技术23希尔密码举例希尔密码举例192221182151717kphot（1 1）确定解密密钥矩阵）确定解密密钥矩阵k k-1-1 ：192221182151717k17 18 1921 2

14、52 17 21 5 18 221 2 17 19 17 215814210714 18071467839393 (mod 26)23 (mod 26) 1726mod2311k)26(mod10681772514182117172217172218212121517192517192212121185171925171922118*k11*14257238425119491517 7181191713615176(mod 26)60110201724017kkk第第3 3章章 古典密码技术古典密码技术24希尔密码举例希尔密码举例192221182151717kphot（2 2）加密）加密 ：

15、将明文字符将明文字符h h、o o、t t变换为数字，分别为变换为数字，分别为7 7、1414、19 19 。171757141921 1821(451409690)2219(91914) (mod 26)()cp kJTO第第3 3章章 古典密码技术古典密码技术25希尔密码举例希尔密码举例192221182151717kphot（3 3）解密）解密149151517624017k()(91914)cJTO149159191415176(657404487)24017(71419)(mod 26)()pc khot第第3 3章章 古典密码技术古典密码技术26希尔密码的特点希尔密码的特点 完全隐

16、藏了单字母的频数完全隐藏了单字母的频数 字母和数字的对应可以改成其它方案，字母和数字的对应可以改成其它方案，使得更不容易攻击成功使得更不容易攻击成功 能比较好地抵抗频数法的分析，对抗能比较好地抵抗频数法的分析，对抗唯密文的攻击强度较高唯密文的攻击强度较高 易受已知明文攻击易受已知明文攻击第第3 3章章 古典密码技术古典密码技术273.2 3.2 置乱密码技术置乱密码技术 置乱（置乱（permutation）也叫换位（）也叫换位（transposition），它通过），它通过打乱明文字符的顺序实现信息的保密。打乱明文字符的顺序实现信息的保密。 由此得到的密码称为由此得到的密码称为置乱密码置乱密码

17、（permutation cipher）或）或换换位密码位密码（transposition caipher）。）。 由于重新排列了消息中的字符，所以打破了明文的结构特性由于重新排列了消息中的字符，所以打破了明文的结构特性 n个明文字符任意置乱的密钥量：个明文字符任意置乱的密钥量：kq=n! 典型处理方法：将明文按行写在一张格纸上，然后再按列的典型处理方法：将明文按行写在一张格纸上，然后再按列的方式读出结果方式读出结果 为了增加变换的复杂性，可以设定读出列的不同次序（即密为了增加变换的复杂性，可以设定读出列的不同次序（即密钥）钥） 第第3 3章章 古典密码技术古典密码技术28置乱密码加密例子置乱

18、密码加密例子 明文明文 The process of transforming plaintext into ciphertext is called encipherment or encryption; the reverse process of transforming ciphertext into plaintext is called decipherment or decryption 按列读出按列读出时，顺序时，顺序大乱！大乱！列越多，列越多，越乱。越乱。第第3 3章章 古典密码技术古典密码技术29更简单的一个例子更简单的一个例子 明文：明文：cryptography is

19、an applied science 密钥：密钥：encry（字母顺序：（字母顺序：23145）（即读出列顺序）（即读出列顺序） 密文：密文： yripdn cohnii rgyaee paspsc tpalce 第第3 3章章 古典密码技术古典密码技术303.3 3.3 密码分析密码分析一、密码分析的基本概念一、密码分析的基本概念密码分析：密码分析：破译破译（breakbreak）、）、攻击攻击( (attackattack) ) 窃密者在不知道解密密钥和通信者所采窃密者在不知道解密密钥和通信者所采用的加密体制的细节的条件下，对截获的密用的加密体制的细节的条件下，对截获的密文进行分析，以获取

20、解密信息（明文或密文进行分析，以获取解密信息（明文或密钥）。钥）。1 1、密码分析的基本过程、密码分析的基本过程分析分析假设假设推断推断证实证实第第3 3章章 古典密码技术古典密码技术312 2、密码分析的基本类型、密码分析的基本类型唯密文攻击唯密文攻击（Ciphertext onlyCiphertext only） 破译者已知：加密算法、待破译的密文破译者已知：加密算法、待破译的密文 已知明文攻击已知明文攻击（Known plaintextKnown plaintext） 破译者已知：加密算法、一定数量的密文和对应的明文破译者已知：加密算法、一定数量的密文和对应的明文 选择明文攻击选择明文攻

21、击（Chosen plaintextChosen plaintext） 破译者已知：加密算法、选定的明文和对应的密文破译者已知：加密算法、选定的明文和对应的密文选择密文攻击选择密文攻击（Chosen ciphertextChosen ciphertext） 破译者已知：加密算法、选定的密文和对应的明文破译者已知：加密算法、选定的密文和对应的明文选择文本攻击选择文本攻击（Chosen textChosen text） 破译者已知：加密算法、选定的明文和对应的密文、选破译者已知：加密算法、选定的明文和对应的密文、选定的密文和对应的明文定的密文和对应的明文 第第3 3章章 古典密码技术古典密码技术3

22、23 3、密码分析的基本方法、密码分析的基本方法（1 1）穷举破译法：蛮力攻击法）穷举破译法：蛮力攻击法对截获的密文依次用可解的密钥试译，直到得到有对截获的密文依次用可解的密钥试译，直到得到有意义的明文；意义的明文；或在不变密钥下，对所有可能的明文加密，直到得或在不变密钥下，对所有可能的明文加密，直到得到与截获密文一致为止。到与截获密文一致为止。任何一种实用的能保障安全的密码，都必须设计得任何一种实用的能保障安全的密码，都必须设计得能够使该方法不可行。途径就是使密钥量极大。能够使该方法不可行。途径就是使密钥量极大。第第3 3章章 古典密码技术古典密码技术33穷举法平均破译时间穷举法平均破译时间

23、宇宙年龄：大约宇宙年龄：大约10101111年！年！第第3 3章章 古典密码技术古典密码技术34（2 2）分析破译法）分析破译法确定性分析法确定性分析法 利用一个或几个已知量（例如明利用一个或几个已知量（例如明- -密对），密对），用数学关系式表示所求未知数（例如密钥）。用数学关系式表示所求未知数（例如密钥）。统计分析法统计分析法 利用明文的某些已知的统计特性破译。利用明文的某些已知的统计特性破译。例如，利用英文字母的频数特性，可以破译例如，利用英文字母的频数特性，可以破译任何单表代换密码。任何单表代换密码。第第3 3章章 古典密码技术古典密码技术35英文字母的频数特性英文字母的频数特性频数比

24、较高的几个英文字母频数比较高的几个英文字母e e、t t、a a、o o、i i、n n、s s、h h、r r第第3 3章章 古典密码技术古典密码技术36二、密码分析举例二、密码分析举例解：解：解密公式为解密公式为 例例3-5 用穷举法破译下面的一段移位密码密文：用穷举法破译下面的一段移位密码密文：UJTUQJQNPJXUWNSLUJTUQJQNPJXUWNSL 1 1、穷举法破译移位密码、穷举法破译移位密码)26(modkcp密文密文 UJTUQJQNPJXUWNSLUJTUQJQNPJXUWNSLk=1 tistpipmoiwtvmrkk=1 tistpipmoiwtvmrkk=2 sh

25、rsoholnhvsulqjk=2 shrsoholnhvsulqjk=3 rgqrngnkmgurtkpik=3 rgqrngnkmgurtkpik=4 qfpqmfmjlftqsjohk=4 qfpqmfmjlftqsjohk=5 peoplelikespringk=5 peoplelikespring密钥密钥 f f（5 5）明文明文people like springpeople like spring 第第3 3章章 古典密码技术古典密码技术37基本过程基本过程 统计密文中各个字母出现的频数统计密文中各个字母出现的频数 根据密文中出现的各个字母的频数，根据密文中出现的各个字母的频数，

26、和英语字母标准频数进行对比分析，和英语字母标准频数进行对比分析，做出假设，推论加密所用的公式做出假设，推论加密所用的公式 证实上述假设或继续作其他假设证实上述假设或继续作其他假设2 2、频数法破译仿射密码、频数法破译仿射密码第第3 3章章 古典密码技术古典密码技术38例例3-6 用频数法破译下面的一段仿射密码密文：用频数法破译下面的一段仿射密码密文： PWUFFOGWCHFDWIWEJOUUNJORSMDWRHVCMWJUPVCCG 破译举例破译举例解解 （1 1）密文字母频数统计：）密文字母频数统计：4141个字符个字符频数较高的密文字母：频数较高的密文字母：W，C，U，F，J，O第第3 3

27、章章 古典密码技术古典密码技术39（2 2）假设与推论、证实）假设与推论、证实频数较高的密文字母：频数较高的密文字母：W，C，U，F，J，O频数较高的明文字母：频数较高的明文字母：e e、t t、a a、o o、i i、n n、s s、h h、r r加密公式：加密公式：解密公式：解密公式： )26(mod)(21kpkpeck)26(mod)()(211kckcdpk1)26,gcd(1k第一次假设：第一次假设： W(22)e(4), C(2)t(19)W(22)e(4), C(2)t(19) )26(mod42221kk )26(mod19221kk 115206 (mod 26)k 111

28、567 64216 (mod 26)k2)26,16gcd()26,gcd(1k 错误错误第第3 3章章 古典密码技术古典密码技术40（2 2）假设与推论、证实）假设与推论、证实频数较高的密文字母：频数较高的密文字母：W，C，U，F，J，O频数较高的明文字母：频数较高的明文字母：e e、t t、a a、o o、i i、n n、s s、h h、r r加密公式：加密公式：解密公式：解密公式： )26(mod)(21kpkpeck)26(mod)()(211kckcdpk1)26,gcd(1k第二次假设：第二次假设： W(22)e(4), U(22)t(19)W(22)e(4), U(22)t(19) )26(mod42221kk 122019(mod 26)kk115224 (mod 26)k 1115247 2416812 (mod 26)k1gcd( ,26)gcd(12,26)2k 错误错误第第3 3章章 古典密码技术古典密码技术41（2 2）