第6讲 经典密码学

1、第第6 6讲讲 经典密码学经典密码学o古典加密算法o分组加密算法密码学相关术语o密码编码学(cryptography)是密码体制的设计学，而密码分析学(cryptanalysis)则是在未知密钥的情况下从密文推演出明文或密钥的技术。密码编码学与密码分析学合起来即为密码学(cryptology)。o如果不论截取者获得了多少密文，但在密文中都没有足够的信息来惟一地确定出对应的明文，则这一密码体制称为无条件安全的，或称为理论上是不可破的。o如果密码体制中的密码不能被可使用的计算资源破译，则这一密码体制称为在计算上是安全的。 基本术语o使消息保密的技术和科学叫做密码编码学密码编码学（cryptogra

2、phy），o从事此行业的叫做密码编码者密码编码者（cryptographer），o密码分析者密码分析者（cryptanalyst）是从事密码分析的专业人员，o密码分析学密码分析学（cryptanalysis）就是破译密文的科学和技术。o密码学密码学（cryptology）作为数学的一个分支，包括密码编码学和密码分析学两部分。基本术语(续)o消息被称为明文明文(Plaintext)(Plaintext)，用某种方法伪装消息以隐藏它的内容的过程称为加密加密(Encrtption)(Encrtption)，被加密的消息称为密文密文(Ciphertext)(Ciphertext)，而把密文转变为明文的

3、过程称为解密解密(Decryption)(Decryption) o密码算法密码算法(Cryptography Algorithm):(Cryptography Algorithm):是用于加密和解密的数学函数o发送者对明文进行加密操作时所采用的一组规则称作加密算法加密算法(Encryption Algorithm)(Encryption Algorithm)o接收者对密文解密所采用的一组规则称为解密算解密算法法(Decryption Algorithm)(Decryption Algorithm) 加解密过程示意图o加密和解密算法的操作通常都是在一组密钥的控制下进行的,分别称为加密密钥加密密

4、钥(Encryption Key) 和解密密钥解密密钥(Decryption Key)明文明文密文加密算法解密算法加密密钥解密密钥一般的数据加密模型 E加密算法D解密算法加密密钥 K解密密钥 K明文 X明文 X密文 Y = EK(X)截取者截获篡改密钥源安全信道密码体制o密码体制：它是一个五元组（P,C,K,E,D)满足条件： （1）P是可能明文的有限集；（明文空间） （2）C是可能密文的有限集；（密文空间） （3）K是一切可能密钥构成的有限集；（密钥空间） *（4）任意k K,有一个加密算法 和相应的解密算法 ，使得 和 分别为加密解密函数，满足dk(ek(x)=x, 这里 x P。EekD

5、dkCPek:PCdk:密码分析密码分析o密码分析学，是攻击者在不知道密钥的情况密码分析学，是攻击者在不知道密钥的情况下，恢复出明文的科学。对密码进行分析的下，恢复出明文的科学。对密码进行分析的尝试称为攻击（尝试称为攻击（Attack)。o攻击密码的方法：攻击密码的方法： 穷举法，又称强力法（穷举法，又称强力法（Brute-force） 分析法分析法密码分析oKerchkhoff原则n假设攻击者是在已经密码体制的前提下来破译密码系统的密钥；o最常见的破解类型如下：n唯密文攻击：o攻击者有一些密文，它们是使用同一加密算法和同一密钥加密的；n已知明文攻击：o攻击者不但得到一些密文，而且能够得到这些

6、密文对应的明文；密码分析n3 选择明文攻击：o攻击者不仅得到一些密文和明文，而且能选择用于加密的明文；n4 选择密文攻击：o攻击者可以选择不同的密文来解密，并能够得到解密后的明文；o这一切的目的都是：破译出密钥o一般说来：密码系统应该经得起已知明文的攻击。o如果攻击者无论得到多少密文，都没有足够的信息去恢复明文，则密码系统是无条件安全的。理论上，只有一次一密的系统才能真正实现。古典密码-信息隐藏oSteganography也称隐写术：将秘密消息隐藏在其他消息中。o隐形墨水，字符上的针眼，手写字符的差异，字符上的铅笔记号等o图象中隐写：用消息位代替图象的每个字节的最不重要的位，而肉眼无法看出差异

7、；o隐写术不使用算法或者密钥Steganographyo(a) Three zebras and a tree. (b) Three zebras, a tree, and the complete text of five plays by William Shakespeare.o(a) Three zebras and a tree. o(b) Three zebras, a tree, and the complete text of five plays by William Shakespeare.1.1.移位密码体制移位密码体制( (单字母单字母) )o设P=C=K=Z/(26)

8、,对 ,定义 同时dk(y)=y-k (mod 26)注1*：26个英文字母与模26剩余类集合0,.,25建立一一对应：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 25 2*.当k=3时，为Caesar密码： 若明文： caesar cipher 密文： FDHVDU FLSKHU 实际算法为： 有 同时有，d3(y)=y-3 (mod 26)Pxyxxe)26(mod3)(3KkCykxxek)26(mod

9、)(3*.一个密码体制要是实际可用必须满足的特性o每一个加密函数ek和每一个解密函数dk都能有效地计算。o破译者取得密文后，将不能在有效的时间内破解出密钥k或明文x。o一个密码体制是安全的必要条件穷举密钥搜索将是不可行的，即密钥空间将是非常大的。移位密码o移位密码(substitution cipher)的原理可用一个例子来说明。（密钥是 3） abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABCcaesar cipherFDHVDU FLSKHU明文密文明文 c 变成了密文 F移位密码o移位密码(substitution cipher)的原

10、理可用一个例子来说明。（密钥是 3） abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABCcaesar cipherFDHVDU FLSKHU明文密文明文 a 变成了密文 D移位密码o移位密码(substitution cipher)的原理可用一个例子来说明。（密钥是 3） abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABCcaesar cipherFDHVDU FLSKHU明文密文明文 e 变成了密文 H凯撒密码的改进o凯撒密码只有25个密钥k，非常不安全；o若有意改变字母的排列顺序，可

11、增大密钥空间；o例如：使用密钥nKeyoABCDEFGHIJKLMNOPQRSTUVWXYZokeyabcdfghijlmnopgrstuvwxznspectacularoABCDEFGHIJKLMNOPQRSTUVWXYZospectacularbdfghijkmnoqvwxyzn泄露给破译者的信息更少；2.替换密码体制替换密码体制o设P=C=Z/(26)，K是由26个符号0，1,.,25的所有可能置换组成。任意 ，定义 d (y)=-1(y)=x, -1是的逆置换。 注：1*. 置换的表示： 2*密钥空间K很大，|K|=26! 41026，破译者穷举搜索是不行的，然而，可由统计的方式破译它

12、。3*移位密码体制是替换密码体制的一个特例，它仅含26个置换做为密钥空间K且yxxe)()(252423 3 2 1 025242332103.仿射密码体制仿射密码体制o替换密码的另一个特例就是仿射密码。 加密函数取形式为 要求唯一解的充要条件是gcd( a,26)=1 该体制描述为： 设P=C=Z/(26) 对 定义 ek(x)=ax+b (mod 26) dk(y)=a-1(y-b)(mod 26) )26/(,),26(mod)(Zbabaxxe,1)26,gcd(| )26/()26/(),(aZZbaK,),(Kbak)26/(,Zyxo例子，设k（7，3），注意到7-1(mod 2

13、6)=15,加密函数是ek(x)=7x+3,相应的解密函数是dk(y)=15(y-3)=15y-19 , 易见 dk(ek(x)=dk(7x+3)=15(7x+3)-19 =x+45-19 =x (mod 26) 若加密明文：hot ，首先转换字母h,o,t成为数字7,14,19,然后加密：解密：);26(mod6230333191477GXA19147191919623015英文中字母的使用频率 02468101214A B C D E F G HI J K L MNOP QR S T U V WX Y Z频率频率E使用最多；使用最多；然后是然后是T R N I O A S其他字母使用较少其

14、他字母使用较少最少的是最少的是J K Q X Z4.4.维吉尼亚密码维吉尼亚密码 (Vigenere,多字母多字母)o设m为一固定的正整数，定义P=C=K=(Z/(26)m,对一个密钥K（ k1,k2,km),定义 ek(x1,x2,xm)=(x1+k1,x2+k2,xm+km)=y dk(y1,y2,ym)= (x1-k1,x2-k2,xm-km) =x这里的所有的运算都是在（mod 26)中进行的。维基尼亚密码（Vigenere）-示例o若密钥字为deceptive，即m=9o明文wearediscoveredsav的加密过程：n明文：wearediscoeredsavn密钥：decept

15、ivedeceptiven密文：ZICVTWQNGRZGVTWAVZo密钥字母d对应数字3，因而明文字母w在密钥字母d的作用下向后移位3，得到密文字母Z。依次类推；维基尼亚密码（Vigenere）o维基尼亚密码是多表替换体制，分析起来更加困难。o密钥空间大，可能的密钥字达26m o如果秘要字的长度是m，明文中的一个字母能够映射成这m个可能的字母中的一个；o例如，当m=5，密钥空间所含密钥的数量是1.1x107 o明文和密文的字母频率分布相同，仍然能使用统计分析破译 5.Hill密码体制密码体制o设为某个固定的正整数，P=C=(Z/(26)m, K=Z/(26)上的mm可逆矩阵 对每一个 ,定义

16、ek(x)=xk (mod 26)和 dk(y)=yk-1 (mod 26)注：明文与密文都是 m元的向量（x1, x2 , xm );(y1, y2,ym)，Z/(26)为同余类环。在这个环上的可逆矩阵Amxm,是指行列式detAmxm的值 Z*/(26),它为Z/(26)中全体可逆元的集合。Z*/(26)= a Z/(26)|(a,26)=1， Z*/(26)=1,3,5,7,9,11,15,17,19,21,23,25例子：当 m=2时，明文元素x=(x1,x2),密文元素y=(y1,y2) (y1,y2)=(x1,x2) k 73811Kko事实上yi为x1,x2的线性组合，y1=11

17、x1+3x2;y2=8x1+7x2，一般，将取mm的矩阵K作为我们的密钥：有 y=(y1, y2, ym,)=(x1, x2, xm) 换言之，y=xK;且有x=yK-1 若K= ,可得K-1 = 若对明文july加密，它分成2个元素（j,u),(l,y),分别对应于（9,20）,（11,24）,有mmmmmmkkkkkkkkk212222111211738111123187（9,20） （9960,72140）（3,4） 且（11,24 ） (12172,88168) （11,22）于是对 july加密的结果为DELW。 为了解密，Bob计算 且 因此，得到了正确的明文“july”73811

18、73811 )20, 9(1123187)4 , 3()24,11(1123187)22,11(6.置换密码体制置换密码体制o设m为固定的正整数，P=C=(Z/(26)m, K是由1,2,.,m的所有置换构成，对一个密钥K，定义 e (x1, x2,., xm)=(x(1),.,x(m) 和 d (y1, y2,., ym)=(y(1),.,y(m) 这里1为的逆置换。注：这里的加密与解密仅仅用了置换，无代数运算。例子： 设m=6, 取密钥 而) 6452)(31 (264564135231) 5462)(31 (4625541362311若给定的明文是：cryptography 首先找分成6

19、个字母长的明文组：crypto|graphy 求得的密文是：YTCOPRAHGYPR注：事实上，置换密码是Hill密码的特例。给定一个集合1,2,.,m的置换矩阵 (置换矩阵是每一行和每一列刚好在一个“1”，而其余元素为“0”的矩阵。)请同学们验证YTCOPRroptopcytryccryptoAHGYPRryphypgahraggraphy否则若0)(1)(ijkkKijnmij对上面例子决定的置换 对应：000010001000100000000001010000000100K00100000001001000000000110000000010011KKCIPHER145326attac

20、kbeginsatfour置换密码o置换密码(transposition cipher)则是按照某一规则重新排列消息中的比特或字符顺序。 密钥顺序明文根据英文字母在 26 个字母中的先后顺序，我们可以得出密钥中的每一个字母的相对先后顺序。因为密钥中没有 A 和 B，因此 C 为第 1。同理，E 为第 2，H 为第 3,，R 为第 6。于是得出密钥字母的相对先后顺序为 145326。 CIPHER145326attackbeginsatfour置换密码o置换密码(transposition cipher)则是按照某一规则重新排列消息中的比特或字符顺序。 密钥顺序明文根据英文字母在 26 个字母中

21、的先后顺序，我们可以得出密钥中的每一个字母的相对先后顺序。因为密钥中没有 A 和 B，因此 C 为第 1。同理，E 为第 2，H 为第 3,，R 为第 6。于是得出密钥字母的相对先后顺序为 145326。 CIPHER145326attackbeginsatfour置换密码o置换密码(transposition cipher)则是按照某一规则重新排列消息中的比特或字符顺序。 密钥顺序明文根据英文字母在 26 个字母中的先后顺序，我们可以得出密钥中的每一个字母的相对先后顺序。因为密钥中没有 A 和 B，因此 C 为第 1。同理，E 为第 2，H 为第 3,，R 为第 6。于是得出密钥字母的相对先

22、后顺序为 145326。 CIPHER145326attackbeginsatfour置换密码o置换密码(transposition cipher)则是按照某一规则重新排列消息中的比特或字符顺序。 密钥顺序明文根据英文字母在 26 个字母中的先后顺序，我们可以得出密钥中的每一个字母的相对先后顺序。因为密钥中没有 A 和 B，因此 C 为第 1。同理，E 为第 2，H 为第 3,，R 为第 6。于是得出密钥字母的相对先后顺序为 145326。 CIPHER145326attackbeginsatfour置换密码o置换密码(transposition cipher)则是按照某一规则重新排列消息中的

23、比特或字符顺序。 密钥顺序明文根据英文字母在 26 个字母中的先后顺序，我们可以得出密钥中的每一个字母的相对先后顺序。因为密钥中没有 A 和 B，因此 C 为第 1。同理，E 为第 2，H 为第 3,，R 为第 6。于是得出密钥字母的相对先后顺序为 145326。 CIPHER145326attackbeginsatfour置换密码o置换密码(transposition cipher)则是按照某一规则重新排列消息中的比特或字符顺序。 密钥顺序明文根据英文字母在 26 个字母中的先后顺序，我们可以得出密钥中的每一个字母的相对先后顺序。因为密钥中没有 A 和 B，因此 C 为第 1。同理，E 为第

24、 2，H 为第 3,，R 为第 6。于是得出密钥字母的相对先后顺序为 145326。 CIPHER145326attackbeginsatfour密文的得出密钥顺序明文先读顺序为 1 的明文列，即 aba CIPHER145326attackbeginsatfour密文的得出密钥顺序明文再读顺序为 2 的明文列，即 cnu CIPHER145326attackbeginsatfour密文的得出密钥顺序明文再读顺序为 3 的明文列，即 aio CIPHER145326attackbeginsatfour密文的得出密钥顺序明文再读顺序为 4 的明文列，即 tet CIPHER145326attac

25、kbeginsatfour密文的得出密钥顺序明文再读顺序为 5 的明文列，即 tgf CIPHER145326attackbeginsatfour密文的得出密钥顺序明文最后读顺序为 6 的明文列，即 ksr 因此密文就是：abacnuaiotettgfksr CIPHER145326attackbeginsatfour接收端收到密文后按列写下密钥顺序明文先写下第 1 列密文 aba 收到的密文：abacnuaiotettgfksr CIPHER145326attackbeginsatfour接收端收到密文后按列写下密钥顺序明文再写下第 2 列密文 cnu 收到的密文：abacnuaiotett

26、gfksr CIPHER145326attackbeginsatfour接收端收到密文后按列写下密钥顺序明文再写下第 3 列密文 aio 收到的密文：abacnuaiotettgfksr CIPHER145326attackbeginsatfour接收端收到密文后按列写下密钥顺序明文再写下第 4 列密文 tet 收到的密文：abacnuaiotettgfksr CIPHER145326attackbeginsatfour接收端收到密文后按列写下密钥顺序明文再写下第 5 列密文 tgf 收到的密文：abacnuaiotettgfksr CIPHER145326attackbeginsatfour接收端收到密文后按列写下密钥顺序明文最后写下第 6 列密文 ksr 收到的密文：abacnuaiotettgfksr CIPHER145326attackbeginsatfour接收端从密文解出明文密钥顺序明文最后按行读出明文收到的密文：abacnuaiotettgfksr CIPHER145326attackbeginsatfour接收端从密文解出明文