密码学与网络安全_第三章传统对称密钥密码

1、第三章第三章 传统对称密钥密码传统对称密钥密码密码学密码学(Cryptology): 是研究信息系统安是研究信息系统安全保密的科学全保密的科学.密码编码学密码编码学(Cryptography): 研究对信息研究对信息进行编码进行编码,实现对信息的隐蔽实现对信息的隐蔽.密码分析学密码分析学(Cryptanalytics):研究加密研究加密消息的破译或消息的伪造消息的破译或消息的伪造. 3.1 导言导言 明文明文（Plaintext）：）： 原信息的初始形式原信息的初始形式 P 密文密文（CypherText）：编码后的加密信息）：编码后的加密信息 C 加密算法加密算法（Encryption Al

2、gorithm)： C=E (P) 解密算法解密算法 (Decryption Algorithm )： P=D(C) 密码系统满足：密码系统满足：P=D(E(P) 密钥密钥 （Secret Key): 需要使用密钥的加密算法，记为：需要使用密钥的加密算法，记为：C=E(K,P), 加密与解密的密钥相同，即：加密与解密的密钥相同，即：P=D(K,E(K,P) 加密与解密的密钥不同，则：加密与解密的密钥不同，则：P=D(KD,E(KE,P)加密和解密示意图加密和解密示意图 密码分析密码分析是破解密码的科学和艺术，是在不知道密钥的是破解密码的科学和艺术，是在不知道密钥的情况下，恢复出明文的科学。密码

3、分析的任务是情况下，恢复出明文的科学。密码分析的任务是试图破译单条消息试图破译单条消息试图识别加密的消息格式，以便借助直接的解密算法破试图识别加密的消息格式，以便借助直接的解密算法破译后续的全部消息译后续的全部消息试图找到加密算法中的普遍缺陷（无须截取任何消息）试图找到加密算法中的普遍缺陷（无须截取任何消息） 成功的密码分析能恢复出消息的明文或密钥。密码分析成功的密码分析能恢复出消息的明文或密钥。密码分析也可以发现密码体制的弱点，最终得到上述结果。也可以发现密码体制的弱点，最终得到上述结果。 如果密钥通过非密码分析方式丢失，叫做密码泄露。如果密钥通过非密码分析方式丢失，叫做密码泄露。3.1.2

4、 密码分析密码分析1.纯密文攻击纯密文攻击（Ciphertext-Only Attack）。）。 破译者只知加密算法、待破译的密文。破译者只能破译者只知加密算法、待破译的密文。破译者只能得到用同一加密算法加密的消息的密文。得到用同一加密算法加密的消息的密文。 2.蛮力攻击蛮力攻击（brute-force method） 破译者知道算法和密钥域，运用拦截密码的放大，破译者知道算法和密钥域，运用拦截密码的放大，采用所有可能的密钥对密文进行解密，知道明文被采用所有可能的密钥对密文进行解密，知道明文被搞清楚。搞清楚。 3.已知明文攻击已知明文攻击（Known-Plaintext Attack） 破译者

5、已知：加密算法和经密钥加密形成的一个或多破译者已知：加密算法和经密钥加密形成的一个或多个明文个明文密文对，即可以知道一定数量的密文和对应密文对，即可以知道一定数量的密文和对应的明文。的明文。 4.选择明文攻击选择明文攻击（Chosen-ciphertext Attack）。）。 选择明文攻击和已知明文攻击相似，不过明文选择明文攻击和已知明文攻击相似，不过明文/密文对是密文对是由破译者自己选择的。由破译者自己选择的。 5.统计攻击统计攻击（statistical attack）。 破译者找出密文中使用最多的字母，并假设相关明文的破译者找出密文中使用最多的字母，并假设相关明文的字母是字母是E，找出

6、几对后，破译者就可以找到密钥并运用，找出几对后，破译者就可以找到密钥并运用密钥来解密信息。密钥来解密信息。 6.模式攻击模式攻击（pattern attack）。 有些密码将语言特征隐藏起来，但可能在密文忠创建一有些密码将语言特征隐藏起来，但可能在密文忠创建一些模式，破译者可能会采用模式攻击来攻击这些模式来些模式，破译者可能会采用模式攻击来攻击这些模式来破译密文。破译密文。 7.选择密文攻击选择密文攻击（Chosen-Cipher Text Attack） 破译者除了知道加密算法外，还包括他自己选定的密破译者除了知道加密算法外，还包括他自己选定的密文和对应的、已解密的原文，即知道选择的密文和对

7、文和对应的、已解密的原文，即知道选择的密文和对应的明文。应的明文。 代换密码（代换密码（Substitution Cipher），又称替代密码，），又称替代密码，或替换密码，是用代换法进行加密所产生的密码。或替换密码，是用代换法进行加密所产生的密码。 3.2 代换密码（代换密码（Substitution Cipher) 一、单码一、单码代换（代换（Monoalphabetic cipher) 密码明文中的字符与密文中的字符总是一一对应。密码明文中的字符与密文中的字符总是一一对应。 可以看成是可以看成是 Z26 到到Z26的一对一的映射。的一对一的映射。 总共有总共有26！种不同的映射。！种不同

8、的映射。 例例. 明文：明文：hello 密文：密文：KHOOR加密明文：加密明文：P= HELLOC= wtaadC= (P+k) mod 26加密算法：加密算法： 1、加法密码（、加法密码（additive cipher) 解密解密算法：算法：循环移位密码循环移位密码 加密加密: 字母向后移动字母向后移动k位；位； 解密解密: 字母向前移动字母向前移动k位。位。P= (C- k) mod 26 字母表（字母表（k=15） ABCDEFGHIJKLMNOPQRSTUVWXYZ pqrstuvwxyzabcdefghijklmnoH=07 E=04L=11O=1407+15=22 mod 26

9、04+15=19 11+15=0014+15=0322 = w 19 = t00 = a03 = dKey=k密码域密码域大小大小=26历史上，加法没密码被称为移位密码，因为加密算法可历史上，加法没密码被称为移位密码，因为加密算法可以认为是以认为是“向下移动密钥字符向下移动密钥字符”或或“向上移动密钥字符向上移动密钥字符”。 2、移位密码、移位密码 3、Caeser密码密码 加法密码有时候被称为加法密码有时候被称为Caesar密码，密码，Caesar曾利用曾利用长度为长度为3的密钥进行通信。的密钥进行通信。 加法密码易受蛮力攻击的纯密文攻击，加法密码加法密码易受蛮力攻击的纯密文攻击，加法密码的

10、密钥域是非常小的，仅有的密钥域是非常小的，仅有26把密钥。这样破译者把密钥。这样破译者对密文发动蛮力攻击就很容易。然后仅仅靠单个字对密文发动蛮力攻击就很容易。然后仅仅靠单个字母的频率信息要分析密文是困难的，因此还要知道母的频率信息要分析密文是困难的，因此还要知道特殊的字母组合出现频率。特殊的字母组合出现频率。4、密码分析、密码分析例：例： 破译者拦截到如下密文破译者拦截到如下密文 XLILSYWIMWRSAJSVWEPI 通过解密可得到如下明文通过解密可得到如下明文 the house is now for sale加密明文加密明文 (k=7)：P= HELLOC= xczzuC= (Pk)

11、mod 26加密算法：加密算法： 5、乘法密码（、乘法密码（multiplicative cipher) 解密解密算法：算法： P= (Ck-1 ) mod 26H=07 E=04L=11O=14 77=23 mod 26 4 7= 2 mod26 117=25 mod26147=20 mod2623 = x 2 = c25 = z20 = u kZ*26 = 1,3,5,7,9,11,15,17,19,21,23,25Key=k密码域密码域大小大小=12解密：解密：C= xczzuH=07 E=04L=11O=14 2315 = 7 mod 26 215 = 4 mod26 2515 =11

12、 mod26 2015 = 14 mod2623 = x 2 = c25 = z20 = u k=7， 7-1 =15 mod 26 P= HELLO作业：作业：key =7 时，作出相应的乘法密码的密码本。时，作出相应的乘法密码的密码本。 k=3: E(P)=P*3 mod 26，字母表（密码本）：，字母表（密码本）： ABCDEFGHIJKLMNOPQRSTUVWXYZ adgjmpsvybehknqtwzcfilorux 字母对应顺序被打乱。字母对应顺序被打乱。加密明文加密明文 (k1, k2) =(7, 2)P= HELLOC= zebbwC= (Pk1+k2) mod 26加密算法：

13、加密算法： 6、仿射密码（、仿射密码（affine cipher) 解密解密算法：算法： P= (C-k2)k1-1 ) mod 26H=07 E=04L=11O=14 77+2=25 mod 26 4 7+2= 4 mod26 117+2= 1 mod26147+2=22 mod2625 = z 4 = e 1 = b22 = w k1Z*26 = 1,3,5,7,9,11,15,17,19,21,23,25Key=(k1,k2)密码域大小密码域大小12*26=312解密：解密：C= zebbwH=07 E=04L=11O=14 (25-2)15 = 7 mod 26 ( 4-2 )15 =

14、 4 mod26 ( 1-2)15 = 11 mod26 (22-1)15= 14 mod26 k=7， 7-1 =15 mod 26 P= HELLO作业：作业：key =(7,2) 时，作出相应的仿射密码的密码本。时，作出相应的仿射密码的密码本。25 = z 4 = e 1 = b22 = w 8、单码代换减法密码、单码代换减法密码 因为加法密码、减法密码和仿射密码都具有小因为加法密码、减法密码和仿射密码都具有小的密钥域，非常容易遭受蛮力攻击，所以可以在的密钥域，非常容易遭受蛮力攻击，所以可以在相关的明文字符和密文字符之间建立映射，如下相关的明文字符和密文字符之间建立映射，如下图所示：图所

15、示：abcdewxyzNOATRPZSW明文：明文：密文：密文： 二、多码二、多码代换（代换（Polyalphabetic subistitution) 在多码代换中，明文中的一个字符被代换成密文中在多码代换中，明文中的一个字符被代换成密文中的多个字符，明文与密文中的字符总是一对多的对应的多个字符，明文与密文中的字符总是一对多的对应关系。关系。 可以看成是可以看成是 Z26 到到 Z26 的一对多的映射。的一对多的映射。 由于在多码代换中，阴藏了字母的频率特征，可以由于在多码代换中，阴藏了字母的频率特征，可以防范频率统计攻击。防范频率统计攻击。 例如：用两张字母替换表例如：用两张字母替换表E1

16、和和E2 ，分别替换明文信息分别替换明文信息中的奇数和偶数位置的字符，从而打乱密文中的字母中的奇数和偶数位置的字符，从而打乱密文中的字母分布频率特性，以避免遭受频率统计攻击，这种编码分布频率特性，以避免遭受频率统计攻击，这种编码方法称为方法称为“双表密码双表密码”。 类似地，可以构造出更复杂的类似地，可以构造出更复杂的“多表密码多表密码”。选一个字母作密钥：选一个字母作密钥：m= 12 1、自动密钥密码、自动密钥密码（Autokey Cipher)明文流：明文流： a t t a c k I s t o d a y密钥流：密钥流：m a t t a c k i s t o d a加密加密 Ci

17、= Pi + Ki mod 26解密解密 Pi= Ci - Ki mod 26密密 文：文：m t m t c m s a l h r d yPattackistodayP019190021081819143024K120191900210818191430C1219121921218011717314Cmtmtcmsalhrdy密钥域密钥域 26，易受蛮力攻击。，易受蛮力攻击。流密码流密码一战中英军使用的密码。密钥是一个一战中英军使用的密码。密钥是一个5X5的字母的字母方阵方阵，把把26个字母填入其中（个字母填入其中（i, j 填在同一格中）填在同一格中）。 2、PlayFair 密码密码L

18、GDBAQMHECURNI,JFXVSOKZYWTD将明文将明文2 个个字母组成一对。字母组成一对。若两字母相同，嵌入一个伪字母。若两字母相同，嵌入一个伪字母。若最后时奇数，嵌入一个伪字母。若最后时奇数，嵌入一个伪字母。 同行右移；同行右移； 同列下移；同列下移； 否则对角；否则对角； 解密反向。解密反向。密钥域密钥域 25！，不宜进行蛮力攻击。！，不宜进行蛮力攻击。隐藏了单字母的频率。隐藏了单字母的频率。攻击可针对双字母组合的频率。攻击可针对双字母组合的频率。LGDBAQMHECURNI,JFXVSOKZYWTD 加密：加密： 同行右移；同行右移； 同列下移；同列下移； 对角对角顺转。顺转。

19、 明文明文 hellohe : EC lx : QZ lo : BX 密文：密文：ECQZBX EC：he QZ：lx BX：lo 解密：解密： 同行同行左左移；移； 同列同列上上移；移； 对角对角反转。反转。明文明文 helxloL映射为映射为Q,BBlaise de Vigenere , 十六世纪法国数学家。十六世纪法国数学家。密钥密钥 k= (k1k2k3km), m26, 循环使用循环使用。加密方法：对位相加（流密钥）加密方法：对位相加（流密钥） Ci= Pi + Ki mod 26解密方法：解密方法： Pi= Ci - Ki mod 26 3、Vigenere 密码密码 密钥密钥:

20、K= PASCAL （m=6）PsheislisteningKpascalpascalpaChhwkswxslgntcg 明文明文: She is listeningi 映射为映射为k,x,t 密钥密钥: K= PASCAL 明文明文: She is listening KPASCALPSHIISLISTENINGIMREADINGTHEYARERUNING A B C D E F G H IJK L M N O P Q R S T U V W X Y ZB C D E F G H IJ K L M N O P Q R S T U V W X Y Z AC D E F G H IJ K L M

21、 N O P Q R S T U V W X Y Z A BD E F G H IJ K L M N O P Q R S T U V W X Y ZA B CE F G H IJ K L M N O P Q R ST U V W X Y Z A B C DF G H IJK L M N O P Q R S T U V W X Y Z A BC D EG H IJK L M N O P Q R ST U V W X Y Z A B C D E FH IJK L M N O P Q R ST U V WX Y Z A B C D E F GIJ K L M N O P Q R S T U V W

22、X Y Z A B C D EFG HJ K L M N O P Q R ST U V W X Y Z A B C D E FG H IK L M N O P Q R S T U V W X Y Z A B C D E F G H IJL M N O P Q R S T U V W X Y Z A B C D E F G H IJKM N O P Q R S T U V W X Y Z A B C D E FG H IJK LN O P Q R S T U V W X Y Z A B C D E F G H IJK L MO P Q R S T U V WX Y Z A B C D E F G

23、 H IJK L M NP Q R S T U V WX Y Z A B C D E F G H IJK LM N OQ R S T U V WX Y Z A B C D E F G H IJK L M N O PR S T U V WX Y Z A B C D E F G H IJK L M N O P QS T U V W X Y Z A B C D E F G H IJK L M N O PQ RT U V W X Y Z A B C D E F G H IJK L M N O PQ R SU V W X Y Z A B C D E F G H IJ K L M N O P Q R ST

24、V WX Y Z A B C D E F G H IJK L M N O P Q R ST UWX Y Z A B C D E F G H IJK L M N O PQ R ST U VX Y Z A B C D E F G H IJK L M N O P Q R STU V WY Z A B C D E F G H IJK L M N O P Q R ST U V W XZ A B C D E F G H IJK L M N O P Q R ST U V W X Y加密时以明文字母选择列，以密钥字母选择行，交点是生成的密文字母。加密时以明文字母选择列，以密钥字母选择行，交点是生成的密文字母。

25、解密时以密钥字母选择行，从中找到密文字母，其所在列即为明文字母。解密时以密钥字母选择行，从中找到密文字母，其所在列即为明文字母。K=YOURP= HOWAREYOUK= YOURYOURYC= FCQRPSSFS Vigenere字母表字母表Leste S Hill , 分组加密，分组加密， 矩阵乘法矩阵乘法 4、Hill 密码（矩阵密码）密码（矩阵密码）密钥密钥 K = (kij) mm ， K mod26 可逆可逆明文分成长度为明文分成长度为 m 的分组的分组 写成矩阵写成矩阵 P r x m加密方法：矩阵乘法加密方法：矩阵乘法 C = P * K mod 26解密方法：解密方法： P =

26、 C*K-1 mod 26m = 4明文：明文：code is ready 排成排成3x4 矩阵矩阵 给定给定4x4密钥密钥矩阵矩阵：K=JHLNEHFGCVOJDXVIcodeisreadyz.明文：明文：code is ready密钥：密钥：K=JHLNEHFGCVOJDXVI明文写成矩阵明文写成矩阵 P =codeisreadyz.密文密文: * = codeisreadyz.JHLNEHFGCVOJDXVIOHKNIHGKLISS. * = 21434818174032425.97111347562211493232181471013876111181818。密密文：文：OHKNIHG

27、KLISSe 映射为映射为N,K K-1 = codeisreadyz.OHKNIHGKLISS. * = 21434818174032425.21522315019399311170471471013876111181818。2152231501939931117047解密：解密： P = C*K-1 mod 26* K-1 = 密文：密文：OHKNIHGKLISS每发送一次信息，改变一次密钥。每发送一次信息，改变一次密钥。密钥完全随机生成，密钥长度固定。密钥完全随机生成，密钥长度固定。 5、一次一密密码（、一次一密密码（One-time-pad OTP）加密方法：加密方法： Ci = Pi

28、 * Ki mod 26解密方法：解密方法： Pi = Ci-*Ki mod 26明文：明文：P = how are you密钥：密钥： K= NCBTZQARXPhowareyoUP714220174241420K132119251601723C20162319162024517CUQXTQUYFR加密下一条加密下一条信息时信息时,更换密码更换密码使用非重复的使用非重复的随机字母序列随机字母序列加密，会使至今能使用的任何密码分加密，会使至今能使用的任何密码分析工具失效析工具失效。 “完美完美”的替换密码的替换密码一次性密钥（一次性密钥（One Time PadOTP）相同的相同的PAD，发方

29、与收方绝对同步；，发方与收方绝对同步；打印、分发、保存与使用问题打印、分发、保存与使用问题 ?长随机数序列（对长随机数序列（对OTP的近似实现）：的近似实现）： ri+1=ri*c+b mod w 其中其中w c和和b为常数为常数,为计算机能表示的最大整数为计算机能表示的最大整数最初，最初，AT&T 使用使用 Vernam密码机实现一次一密的加密，密码机实现一次一密的加密， 故又称故又称 Vernam 密码。密码。 导致密码机导致密码机出出 现现 6、Enigma 密码机密码机Sherbius 发明，第二次世界大战中德军使用。发明，第二次世界大战中德军使用。二战中已被破解（盟军获得了机器的复制

30、品，加上计算机）二战中已被破解（盟军获得了机器的复制品，加上计算机）“埃尼格玛埃尼格玛”之父谢尔比乌斯却未能看到之父谢尔比乌斯却未能看到“埃尼格玛埃尼格玛”被广泛使被广泛使用并对第二次世界大战所产生的重大影响，他于用并对第二次世界大战所产生的重大影响，他于1929年年5月因骑月因骑马时发生意外伤重而死马时发生意外伤重而死 Enigma 密码机的构造密码机的构造基于转轮密码的原理基于转轮密码的原理 26键的键盘，用于输入明文和密文键的键盘，用于输入明文和密文装有装有26个灯泡的灯板，加密时显示密文字符，解密时显示明文个灯泡的灯板，加密时显示密文字符，解密时显示明文字符字符26个插头的接线板，个插

31、头的接线板，13条连线，其连接每天更换条连线，其连接每天更换3个转轮，每天从个转轮，每天从5个转轮中选出。转轮分成快、中、慢三种。个转轮中选出。转轮分成快、中、慢三种。转轮有转轮有26格，快轮每打一字转一格，快轮转一圈使中轮转一格，格，快轮每打一字转一格，快轮转一圈使中轮转一格，中轮转一圈使慢轮转一格。中轮转一圈使慢轮转一格。有一反射器，固定但不事先接线有一反射器，固定但不事先接线插板插板灯板灯板键盘键盘换位密码是采用移动字母位置的方法进行加密的。换位密码是采用移动字母位置的方法进行加密的。 它把明文中的字母重新排列，字母本身不变，但位置变了。它把明文中的字母重新排列，字母本身不变，但位置变了

32、。 3.3 换位密码（换位密码（Transporsition Cipher) 如：把明文中的字母的顺序倒过来写，然后以固定长度的如：把明文中的字母的顺序倒过来写，然后以固定长度的字母组发送或记录。字母组发送或记录。明文：明文：computer systems密文：密文：sm etsy sretupmoc换位并没有改变字母，可能的攻击方法：换位并没有改变字母，可能的攻击方法： 单字母频率攻击单字母频率攻击 蛮力攻击：考虑所有可能的排列蛮力攻击：考虑所有可能的排列 模式攻击：模式攻击： 1、无密钥、无密钥换位换位栅栏密码（栅栏密码（rail fence cipher) 明文：明文：WHAT YOU

33、 CAN LEARN FROM THIS BOOK分组排列为两排：分组排列为两排：W A Y U A L A N R M H S O K H T O C N E R F O T I B O 得到密文得到密文 WAYUALANRMHSOK HTOCNERFOTIBOX W AYU ALA N R M HS O KHTO C NERFOTIB O X加密：加密：竖写横读竖写横读解密：解密：横写竖读横写竖读将明文字符分割成为五个一行的分组，排进表格中。将明文字符分割成为五个一行的分组，排进表格中。 明文：明文：WHAT YOU CAN LEARN FROM THIS BOOK分组排列为：分组排列为：

34、 表格表格换位换位WHATYOUCANLEARNFROMTHISBOOKXXX密文则以下面的形式读出：密文则以下面的形式读出： WOLFHOHUERIKACAOSXTARMBXYNNTOX这里的密钥是分组数这里的密钥是分组数5。解密：解密：竖写横读竖写横读加密：加密：横写竖读横写竖读明文：明文：meet me at the park分组排列为：分组排列为： meetmeattheparkX加密：加密： MMTAEEHREAEKTTPX换位对应一个置换：换位对应一个置换：1234567891011121314151615913261014371115481216 2、有密钥、有密钥换位密码换位密

35、码密钥密钥 K 就是一个指定的置换。就是一个指定的置换。明文：明文：Enemy attacks tonight !3145212345例如：把明文分成例如：把明文分成5个字母一段。个字母一段。每段都按照密钥指定的置换方式进行换位。每段都按照密钥指定的置换方式进行换位。密钥密钥 K =EnemyattackstonightzEEMYNTAACTTKONSHITZG2513412345 K-1 =密文：密文：EEMYNTAACT TKONSHITZGEEMYNTAACTTKONSHITZGEnemyattackstonightz1234512345换位盒换位盒明文：明文：Enemy attacks

36、 tonight !31452 把长度为把长度为20的明文横排在的明文横排在45的矩阵里的矩阵里, 每一列都按照每一列都按照密钥指定的置换方式进行换位。密钥指定的置换方式进行换位。密钥密钥 K =enemYattackstonightz25134 K-1 =横读得密文：横读得密文： EEMYNTAACT TKONSHI TZGK eemYntaacttkonshitzg明文：明文：Enemy attacks tonight !31452密钥密钥 K =enemYattackstonightz25134 K-1 =竖竖读得密文：读得密文： ETTHEAKIMA OTYCNZNTSG K eemY

37、ntaacttkonshitzg解密：解密： 竖竖写入表格中；写入表格中； 逆向换列；横读即可逆向换列；横读即可 横横读得密文：读得密文： EEMYNTAACT TKONSHITZG 解密：解密： 横横写入表格中；写入表格中； 逆向换列；横读即可逆向换列；横读即可 矩阵表示换位：矩阵表示换位：31452 K =enemYattackstonightz25134 K-1 = eemYntaacttkonshitzg0100000001100000010000010= 0010010000000100000101000eemYntaacttkonshitzgenemyattackstonightz

38、 = 3、将两种方法结合起来、将两种方法结合起来将换位方法重复两次将换位方法重复两次经过两次换位盒经过两次换位盒enemYattackstonightzeemYntaacttkonshitzg明文：明文： Enemy attacks tonight !中间文本：中间文本：ETTHEAKIMAOTYCNZNTSG（按列读出）（按列读出） 密文：密文： TIYTEAOZHMCSEANGTKTN （按列读出）（按列读出） ettheakimaotycnzntsgTEHETIAMAKYOCNTTZSGN31452 K =组合换组合换位：不同密钥，多次组合位：不同密钥，多次组合31452换位盒换位盒K1 53214 K2 =25413K3 =enemYattackstonightzeemYntaacttkonshitzg K1 =attheakimaotycnzntsgettahaikamnytocgtnzs换位盒换位盒K2 eangtiyttktnaaozhmcsaagenyytit