第6讲-经典密码学分析课件

第第6 6讲讲 经典密码学经典密码学o古典加密算法o分组加密算法第6讲 经典密码学古典加密算法1密码学相关术语o密码编码学(cryptography)是密码体制的设计学，而密码分析学(cryptanalysis)则是在未知密钥的情况下从密文推演出明文或密钥的技术。密码编码学与密码分析学合起来即为密码学(cryptology)。o如果不论截取者获得了多少密文，但在密文中都没有足够的信息来惟一地确定出对应的明文，则这一密码体制称为无条件安全的，或称为理论上是不可破的。o如果密码体制中的密码不能被可使用的计算资源破译，则这一密码体制称为在计算上是安全的。密码学相关术语密码编码学(cryptography)是密码体2基本术语o使消息保密的技术和科学叫做密码编码学密码编码学（cryptography），o从事此行业的叫做密码编码者密码编码者（cryptographer），o密码分析者密码分析者（cryptanalyst）是从事密码分析的专业人员，o密码分析学密码分析学（cryptanalysis）就是破译密文的科学和技术。o密码学密码学（cryptology）作为数学的一个分支，包括密码编码学和密码分析学两部分。基本术语使消息保密的技术和科学叫做密码编码学（cryptog3基本术语(续)o消息被称为明文明文(Plaintext)(Plaintext)，用某种方法伪装消息以隐藏它的内容的过程称为加密加密(Encrtption)(Encrtption)，被加密的消息称为密文密文(Ciphertext)(Ciphertext)，而把密文转变为明文的过程称为解密解密(Decryption)(Decryption)o密码算法密码算法(Cryptography Algorithm):(Cryptography Algorithm):是用于加密和解密的数学函数o发送者对明文进行加密操作时所采用的一组规则称作加密算法加密算法(Encryption Algorithm)(Encryption Algorithm)o接收者对密文解密所采用的一组规则称为解密算解密算法法(Decryption Algorithm)(Decryption Algorithm)基本术语(续)消息被称为明文(Plaintext)，用某种方4 加解密过程示意图o加密和解密算法的操作通常都是在一组密钥的控制下进行的,分别称为加密密钥加密密钥(Encryption Key)和解密密钥解密密钥(Decryption Key)明文明文密文加密算法解密算法加密密钥解密密钥 加解密过程示意图加密和解密算法的操作通常都是在一组密钥的控5一般的数据加密模型 E加密算法D解密算法加密密钥 K解密密钥 K明文 X明文 X密文 Y=EK(X)截取者截获篡改密钥源安全信道一般的数据加密模型 ED加密密钥 K解密密钥 K明文 X明文6密码体制o密码体制：它是一个五元组（P,C,K,E,D)满足条件：（1）P是可能明文的有限集；（明文空间）（2）C是可能密文的有限集；（密文空间）（3）K是一切可能密钥构成的有限集；（密钥空间）*（4）任意k K,有一个加密算法 和相应的解密算法 ，使得 和 分别为加密解密函数，满足dk(ek(x)=x,这里 x P。密码体制密码体制：它是一个五元组（P,C,K,E,D)满足条7密码分析密码分析o密码分析学，是攻击者在不知道密钥的情况下，密码分析学，是攻击者在不知道密钥的情况下，恢复出明文的科学。对密码进行分析的尝试称恢复出明文的科学。对密码进行分析的尝试称为攻击（为攻击（Attack)。o攻击密码的方法：攻击密码的方法：穷举法，又称强力法（穷举法，又称强力法（Brute-force）分析法分析法密码分析密码分析学，是攻击者在不知道密钥的情况下，恢复出明文8密码分析oKerchkhoff原则n假设攻击者是在已经密码体制的前提下来破译密码系统的密钥；o最常见的破解类型如下：n唯密文攻击：o攻击者有一些密文，它们是使用同一加密算法和同一密钥加密的；n已知明文攻击：o攻击者不但得到一些密文，而且能够得到这些密文对应的明文；密码分析Kerchkhoff原则9密码分析n3 选择明文攻击：o攻击者不仅得到一些密文和明文，而且能选择用于加密的明文；n4 选择密文攻击：o攻击者可以选择不同的密文来解密，并能够得到解密后的明文；o这一切的目的都是：破译出密钥o一般说来：密码系统应该经得起已知明文的攻击。o如果攻击者无论得到多少密文，都没有足够的信息去恢复明文，则密码系统是无条件安全的。理论上，只有一次一密的系统才能真正实现。密码分析3 选择明文攻击：10古典密码-信息隐藏oSteganography也称隐写术：将秘密消息隐藏在其他消息中。o隐形墨水，字符上的针眼，手写字符的差异，字符上的铅笔记号等o图象中隐写：用消息位代替图象的每个字节的最不重要的位，而肉眼无法看出差异；o隐写术不使用算法或者密钥古典密码-信息隐藏You cant understand11Steganographyo(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.Steganography(a)Three zebras 121.1.移位密码体制移位密码体制(单字母单字母)o设P=C=K=Z/(26),对 ,定义 同时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)1.移位密码体制(单字母)设P=C=K=Z/(26),对 133*.一个密码体制要是实际可用必须满足的特性o每一个加密函数ek和每一个解密函数dk都能有效地计算。o破译者取得密文后，将不能在有效的时间内破解出密钥k或明文x。o一个密码体制是安全的必要条件穷举密钥搜索将是不可行的，即密钥空间将是非常大的。3*.一个密码体制要是实际可用必须满足的特性每一个加密函数e14移位密码o移位密码(substitution cipher)的原理可用一个例子来说明。（密钥是 3）abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABCcaesar cipherFDHVDU FLSKHU明文密文明文 c 变成了密文 F移位密码移位密码(substitution cipher)的15移位密码o移位密码(substitution cipher)的原理可用一个例子来说明。（密钥是 3）abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABCcaesar cipherFDHVDU FLSKHU明文密文明文 a 变成了密文 D移位密码移位密码(substitution cipher)的16移位密码o移位密码(substitution cipher)的原理可用一个例子来说明。（密钥是 3）abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABCcaesar cipherFDHVDU FLSKHU明文密文明文 e 变成了密文 H移位密码移位密码(substitution cipher)的17凯撒密码的改进o凯撒密码只有25个密钥k，非常不安全；o若有意改变字母的排列顺序，可增大密钥空间；o例如：使用密钥nKeyoABCDEFGHIJKLMNOPQRSTUVWXYZokeyabcdfghijlmnopgrstuvwxznspectacularoABCDEFGHIJKLMNOPQRSTUVWXYZospectacularbdfghijkmnoqvwxyzn泄露给破译者的信息更少；凯撒密码的改进凯撒密码只有25个密钥k，非常不安全；182.替换密码体制替换密码体制o设P=C=Z/(26)，K是由26个符号0，1,.,25的所有可能置换组成。任意 ，定义 d(y)=-1(y)=x,-1是的逆置换。注：1*.置换的表示：2*密钥空间K很大，|K|=26!41026，破译者穷举搜索是不行的，然而，可由统计的方式破译它。3*移位密码体制是替换密码体制的一个特例，它仅含26个置换做为密钥空间2.替换密码体制设P=C=Z/(26)，K是由26个符号0，193.仿射密码体制仿射密码体制o替换密码的另一个特例就是仿射密码。加密函数取形式为 要求唯一解的充要条件是gcd(a,26)=1 该体制描述为：设P=C=Z/(26)对 定义 ek(x)=ax+b(mod 26)dk(y)=a-1(y-b)(mod 26)3.仿射密码体制替换密码的另一个特例就是仿射密码。20o例子，设k（7，3），注意到7-1(mod 26)=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,然后加密：解密：例子，设k（7，3），注意到7-1(mod 26)=15,21英文中字母的使用频率 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其他字母使用较少其他字母使用较少最少的是最少的是J K Q X Z英文中字母的使用频率 02468101214ABCDEFGH224.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)中进行的。4.维吉尼亚密码(Vigenere,多字母)设m为一固定的23维基尼亚密码（Vigenere）-示例o若密钥字为deceptive，即m=9o明文wearediscoveredsav的加密过程：n明文：wearediscoeredsavn密钥：deceptivedeceptiven密文：ZICVTWQNGRZGVTWAVZo密钥字母d对应数字3，因而明文字母w在密钥字母d的作用下向后移位3，得到密文字母Z。依次类推；维基尼亚密码（Vigenere）-示例若密钥字为decept24维基尼亚密码（Vigenere）o维基尼亚密码是多表替换体制，分析起来更加困难。o密钥空间大，可能的密钥字达26m o如果秘要字的长度是m，明文中的一个字母能够映射成这m个可能的字母中的一个；o例如，当m=5，密钥空间所含密钥的数量是1.1x107 o明文和密文的字母频率分布相同，仍然能使用统计分析破译 维基尼亚密码（Vigenere）维基尼亚密码是多表替换体制，255.Hill密码体制密码体制o设为某个固定的正整数，P=C=(Z/(26)m,K=Z/(26)上的mm可逆矩阵 对每一个 ,定义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 5.Hill密码体制设为某个固定的正整数，P=C=(Z/(26o事实上yi为x1,x2的线性组合，y1=11x1+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）,有事实上yi为x1,x2的线性组合，y1=11x1+3x2;y27（9,20）（9960,72140）（3,4）且（11,24）(12172,88168)（11,22）于是对 july加密的结果为DELW。为了解密，Bob计算 且 因此，得到了正确的明文“july”（9,20）（9960,72140286.置换密码体制置换密码体制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,取密钥 而6.置换密码体制设m为固定的正整数，P=C=(Z/(2629若给定的明文是：cryptography 首先找分成6个字母长的明文组：crypto|graphy 求得的密文是：YTCOPRAHGYPR注：事实上，置换密码是Hill密码的特例。给定一个集合1,2,.,m的置换矩阵 (置换矩阵是每一行和每一列刚好在一个“1”，而其余元素为“0”的矩阵。)请同学们验证若给定的明文是：cryptography 首先找分成6个字母30对上面例子决定的置换 对应：对上面例子决定的置换 对应：31CIPHER145326attackbeginsatfour置换密码o置换密码(transposition cipher)则是按照某一规则重新排列消息中的比特或字符顺序。密钥顺序明文根据英文字母在 26 个字母中的先后顺序，我们可以得出密钥中的每一个字母的相对先后顺序。因为密钥中没有 A 和 B，因此 C 为第 1。同理，E 为第 2，H 为第 3,，R 为第 6。于是得出密钥字母的相对先后顺序为 145326。CIPHER置换密码置换密码(transposition c32CIPHER145326attackbeginsatfour置换密码o置换密码(transposition cipher)则是按照某一规则重新排列消息中的比特或字符顺序。密钥顺序明文根据英文字母在 26 个字母中的先后顺序，我们可以得出密钥中的每一个字母的相对先后顺序。因为密钥中没有 A 和 B，因此 C 为第 1。同理，E 为第 2，H 为第 3,，R 为第 6。于是得出密钥字母的相对先后顺序为 145326。CIPHER置换密码置换密码(transposition c33CIPHER145326attackbeginsatfour置换密码o置换密码(transposition cipher)则是按照某一规则重新排列消息中的比特或字符顺序。密钥顺序明文根据英文字母在 26 个字母中的先后顺序，我们可以得出密钥中的每一个字母的相对先后顺序。因为密钥中没有 A 和 B，因此 C 为第 1。同理，E 为第 2，H 为第 3,，R 为第 6。于是得出密钥字母的相对先后顺序为 145326。CIPHER置换密码置换密码(transposition c34CIPHER145326attackbeginsatfour置换密码o置换密码(transposition cipher)则是按照某一规则重新排列消息中的比特或字符顺序。密钥顺序明文根据英文字母在 26 个字母中的先后顺序，我们可以得出密钥中的每一个字母的相对先后顺序。因为密钥中没有 A 和 B，因此 C 为第 1。同理，E 为第 2，H 为第 3,，R 为第 6。于是得出密钥字母的相对先后顺序为 145326。CIPHER置换密码置换密码(transposition c35CIPHER145326attackbeginsatfour置换密码o置换密码(transposition cipher)则是按照某一规则重新排列消息中的比特或字符顺序。密钥顺序明文根据英文字母在 26 个字母中的先后顺序，我们可以得出密钥中的每一个字母的相对先后顺序。因为密钥中没有 A 和 B，因此 C 为第 1。同理，E 为第 2，H 为第 3,，R 为第 6。于是得出密钥字母的相对先后顺序为 145326。CIPHER置换密码置换密码(transposition c36CIPHER145326attackbeginsatfour置换密码o置换密码(transposition cipher)则是按照某一规则重新排列消息中的比特或字符顺序。密钥顺序明文根据英文字母在 26 个字母中的先后顺序，我们可以得出密钥中的每一个字母的相对先后顺序。因为密钥中没有 A 和 B，因此 C 为第 1。同理，E 为第 2，H 为第 3,，R 为第 6。于是得出密钥字母的相对先后顺序为 145326。CIPHER置换密码置换密码(transposition c37CIPHER145326attackbeginsatfour密文的得出密钥顺序明文先读顺序为 1 的明文列，即 aba CIPHER密文的得出密钥先读顺序为 1 的明文列，即 ab38CIPHER145326attackbeginsatfour密文的得出密钥顺序明文再读顺序为 2 的明文列，即 cnu CIPHER密文的得出密钥再读顺序为 2 的明文列，即 cn39CIPHER145326attackbeginsatfour密文的得出密钥顺序明文再读顺序为 3 的明文列，即 aio CIPHER密文的得出密钥再读顺序为 3 的明文列，即 ai40CIPHER145326attackbeginsatfour密文的得出密钥顺序明文再读顺序为 4 的明文列，即 tet CIPHER密文的得出密钥再读顺序为 4 的明文列，即 te41CIPHER145326attackbeginsatfour密文的得出密钥顺序明文再读顺序为 5 的明文列，即 tgf CIPHER密文的得出密钥再读顺序为 5 的明文列，即 tg42CIPHER145326attackbeginsatfour密文的得出密钥顺序明文最后读顺序为 6 的明文列，即 ksr 因此密文就是：abacnuaiotettgfksr CIPHER密文的得出密钥最后读顺序为 6 的明文列，即 k43CIPHER145326attackbeginsatfour接收端收到密文后按列写下密钥顺序明文先写下第 1 列密文 aba 收到的密文：abacnuaiotettgfksr CIPHER接收端收到密文后按列写下密钥先写下第 1 列密文44CIPHER145326attackbeginsatfour接收端收到密文后按列写下密钥顺序明文再写下第 2 列密文 cnu 收到的密文：abacnuaiotettgfksr CIPHER接收端收到密文后按列写下密钥再写下第 2 列密文45CIPHER145326attackbeginsatfour接收端收到密文后按列写下密钥顺序明文再写下第 3 列密文 aio 收到的密文：abacnuaiotettgfksr CIPHER接收端收到密文后按列写下密钥再写下第 3 列密文46CIPHER145326attackbeginsatfour接收端收到密文后按列写下密钥顺序明文再写下第 4 列密文 tet 收到的密文：abacnuaiotettgfksr CIPHER接收端收到密文后按列写下密钥再写下第 4 列密文47CIPHER145326attackbeginsatfour接收端收到密文后按列写下密钥顺序明文再写下第 5 列密文 tgf 收到的密文：abacnuaiotettgfksr CIPHER接收端收到密文后按列写下密钥再写下第 5 列密文48CIPHER145326attackbeginsatfour接收端收到密文后按列写下密钥顺序明文最后写下第 6 列密文 ksr 收到的密文：abacnuaiotettgfksr CIPHER接收端收到密文后按列写下密钥最后写下第 6 列密49CIPHER145326attackbeginsatfour接收端从密文解出明文密钥顺序明文最后按行读出明文收到的密文：abacnuaiotettgfksr CIPHER接收端从密文解出明文密钥最后按行读出明文收到的密50CIPHER145326attackbeginsatfour接收端从密文解出明文密钥顺序明文最后按行读出明文收到的密文：abacnuaiotettgfksr CIPHER接收端从密文解出明文密钥最后按行读出明文收到的密51CIPHER145326attackbeginsatfour接收端从密文解出明文密钥顺序明文最后按行读出明文收到的密文：abacnuaiotettgfksr 得出明文：attackbeginsatfour CIPHER接收端从密文解出明文密钥最后按行读出明文收到的密527.置换密码(栅栏技术)o最简单的例子是栅栏技术：按照对角线的顺序写入明文，而按行的顺序读出作为密文。o明文：meet me after the partyo写为：m e m a t r h p r yo e t e f e t e a to密文：mematrhpryetefeteat7.置换密码(栅栏技术)最简单的例子是栅栏技术：按照对角线的53古典密码小结古典密码小结o研究古典密码原理，对于理解、构造和分析研究古典密码原理，对于理解、构造和分析现代密码是十分有益的。现代密码是十分有益的。古典密码小结54序列密码与分组密码 o序列码体制是将明文 X 看成是连续的比特流(或字符流)x1x2，并且用密钥序列 K k1k2中的第 i 个元素 ki 对明文中的 xi 进行加密，即 序列密码与分组密码 序列码体制是将明文 X 看成是连续的比特55序列密码体制 密钥序列产生器种子 I0发端ki密钥序列产生器种子 I0收端ki密文序列明文序列明文序列xixiyiyi在开始工作时种子 I0 对密钥序列产生器进行初始化。按照模 2 进行运算，得出：(9-1)序列密码体制 密钥序列产生器种子发端ki密钥序列产生器种子收56序列密码体制 密钥序列产生器种子 I0发端ki密钥序列产生器种子 I0收端ki密文序列明文序列明文序列xixiyiyi在收端，对 yi 的解密算法为：(9-2)序列密码又称为密钥流密码。序列密码体制 密钥序列产生器种子发端ki密钥序列产生器种子收57序列密码体制的保密性 o序列密码体制的保密性完全在于密钥的随机性。o如果密钥是真正的随机数，则这种体制就是理论上不可破的。这也可称为一次一密乱码本体制。o严格的一次一密乱码本体制所需的密钥量不存在上限，很难实用化。o密码学家试图模仿这种一次一密乱码本体制。目前常使用伪随机序列作为密钥序列。关键是序列的周期要足够长，且序列要有很好的随机性（这很难寻找）。序列密码体制的保密性 序列密码体制的保密性完全在于密钥的随机58