现代密码学第二讲：古典密码学ppt课件.ppt

《现代密码学第二讲：古典密码学ppt课件.ppt》由会员分享，可在线阅读，更多相关《现代密码学第二讲：古典密码学ppt课件.ppt（57页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物1古典密码学古典密码学现代密码学现代密码学第二讲第二讲我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物上讲内容回顾上讲内容回顾n密码学分类n密码学与信息安全的关系我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物本章主要内容本章主要内容n代换密码n置换密码nHill密码n转轮密码n古典密码

2、的惟密文攻击方法我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物密码分类密码分类n代换密码（ substitution ）：代换是古典密码中用到的最基本的处理技巧。所谓代换，就是将明文中的一个字母由其它字母、数字或符号替代的一种方法。n凯撒密码n仿射密码n单表代换n多表代换n置换密码（permutation）：将明文字符按照某种规律重新排列而形成密文的过程。nHill密码n转轮密码我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个

3、活的生物凯撒密码凯撒密码(caesar cipher)已知最早的代换密码，又称移位密码n代换表（密钥）：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 Cn数学描述:用数字表示每个字母：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) = (

4、p + k) mod (26)p = D(c) = (c k) mod (26)明文p Z26，密文c Z26 ，密钥k取1,25，只有25个我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物凯撒密码凯撒密码例:使用其后的第三个字母代换该字母明文：meet me after the toga party密文：PHHW PH DIWHU WKH WRJD SDUWB我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物恺撒密码的攻

5、击恺撒密码的攻击n已知明文和密文、加密和解密算法，需要解同余方程，可以恢复密钥 k = (c- p) mod (26)；n穷举攻击：已知密文，且明文为有意义字符，至多尝试25次，可以恢复明文.我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物仿射密码（仿射密码（Affine Cipher）n移位密码的扩展明文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-1m

6、od 26我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物例：令密钥k=(7,3), 且gcd(7,26)=1. 明文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

7、)仿射密码仿射密码我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物仿射密码仿射密码练习：令密钥k=(9,3), 且gcd(5,26)=1. 明文hot=(7,14,19)，求加解密过程。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物n 已知两对明文和密文（p1,c1）和（p2,c2）、加密和解密算法，需要解2元同余方程组，可以恢复密钥k=(a,b)；c1 = (a p1 + b) mod 26c2 = (a p2 +

8、b) mod 26n穷举攻击：已知密文，明文为有意义字符，至多尝试26*(26)个，可以恢复明文.仿射密码仿射密码我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物单表代换密码单表代换密码（ Monoalphabetic Cipher ）n代换表是26个字母的任意置换 例：加密函数:我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物单表代换密码单表代换密码n练习：我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个

9、美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物单表代换密码单表代换密码n已知明文和密文，可以恢复部分加密函数（解密函数）；n穷举攻击：已知密文，明文为有意义字符，至多尝试26! = 4 x 1026 个，可以恢复明文代换表的个数为26！我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物多表代换密码多表代换密码(Polyalphabetic Ciphers)加密明文消息时采用不同的单表代换，由密钥具体决定采用哪个表代换消息，密钥通常是一个词的重复。n简化的多表代换密码 -维吉尼亚密码

10、（ Vigenre Cipher ）：由26个类似 caesar密码的代换表组成我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物多表代换密码多表代换密码n维吉尼亚密码：在长为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.我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个

11、美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物多表代换密码多表代换密码n例我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物多表代换密码多表代换密码n练习：我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物多表代换密码多表代换密码n已知m个连续的明文和密文，可以恢复维吉尼亚密码的单表移位量（即密钥）；n穷举攻击：已知密文，明文为有意义字符，至多尝试26m 个，可以恢复明文密钥空间大小是26m我吓了

12、一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物置换密码置换密码n加密变换使得信息元素只有位置变化而形态不变，如此可以打破消息中的某些固定模式（结构） 明文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.我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错

13、：表里边有一个活的生物置换密码置换密码例n密钥明文：she sells sea shells by the sea shore分组：shesel lsseas hellsb ythese ashore置换：ELSEHS SSLASE LBHSEL HEYSTE HEARSO我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物置换密码置换密码n练习：我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物置换密码置换密码n已知多对明文

14、和密文，可以推导置换表（即密钥）；n穷举攻击：已知密文，明文为有意义字符，至多尝试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扩散我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里

15、呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物希尔密码希尔密码n例我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物希尔密码希尔密码n置换密码可以看做是希尔密码的特例。练习：设hill密码的密钥如下，求对应置换密码的置换表。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物希尔密码希尔密码n已知m组明文和密文、加密和解密算法，需要解m元同余方程组，可以恢复密钥；n 穷举攻击：已知密文，明文为有意义字符，至多尝

16、试26m*m个，可以恢复明文11121m11121m11121mm1m2mmm1m2mmm1m2mmcccpppkkkcccpppkkk我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物转轮密码（转轮密码（Rotor Machine）n19世纪20年代，开始出现机械加解密设备，最典型的是转轮密码机1918年Arthur Scherbius发明的EIGMA，瑞典Haglin发明的Haglin，和日军发明的“紫密”和“兰密”都属于转轮密码机。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界

17、里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物转轮密码转轮密码Enigma密码机密码机我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物转轮密码转轮密码我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物惟密文攻击惟密文攻击n在攻击者可以截获（足够）明密文的条件下，易于恢复用户的密钥；n当攻击者只能窃听到密文时，若明文是有意义的（一段话等具有可读性）字符时，利用穷举搜索，可以通过密文解密出对应明文，继而恢复密

18、钥。（穷举搜索的复杂度取决于密钥空间的大小，古典密码体制的密钥空间通常比较小。）当攻击者只能窃听到密文时，是否有其它更有效攻击方法？若明文是无意义的随机字符时，攻击者是否可以获得明文或密钥的相关信息？我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物惟密文攻击惟密文攻击人类的语言存在冗余，以英文文档为例n字母 e 是使用频率最高的 n其次是 T,R,N,I,O,A,S n Z,J,K,Q,X 很少使用nA、I、U很少用在词尾，E、N、R常出现在词尾。E、S、D作为字母结尾字母的单词超过一半，T、A、S、W为起

19、始字母的单词约占一半。 我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物惟密文攻击惟密文攻击我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物惟密文攻击惟密文攻击n对于双字母组合, 三字母组合我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物惟密文攻击惟密文攻击n统计攻击（频率攻击）n假设：根据分析假设某些结论。n推断：在假设的前提下，推

20、断出一些结论。n双频n字母跟随关系n构词规则n词义n验证发展：填上破译出的字母，根据词义、构词规则不断发展 我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物惟密文攻击惟密文攻击n移位密码、仿射密码和单表代换密码都没有破坏明文的频率统计规律，可以直接用统计分析法n例：截取一段仿射密码的密文 c=ap+b mod 26我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物惟密文攻击惟密文攻击n统计得到R(8),D(7),E,H,K

21、(5),S,F,V(4)密文出现字母频率统计我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物惟密文攻击惟密文攻击n令R=E(e)，D=E(t)，得到方程组na b c d e f g h i j k l m n o p q r s t u v w x y Zn0 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解得a=6 , b= 19 ; 其中gcd(6,26)=21，故猜测错误。4ab1719ab3我吓了一跳，蝎子是多么丑

22、恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物惟密文攻击惟密文攻击1、 令R=E(e)，E=E(t)？a=132、R=E(e)，H=E(t)? a=83、R=E(e)，K=E(t), a=3,b=5,第3组解有效，则解密函数p=(c-5)*3-1=9c-19解密得明文：algorithms are quite general definitions of arithmetic processes.我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生

23、物惟密文攻击惟密文攻击n练习：已知用户用移位密码加密，密文为“KHOOR,HYHUB RQH”，用统计法求密钥和对应明文na b c d e f g h i j k l m n o p q r s t u v w x y Zn0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25nH(4), O,R(2), K(1), Q(1), Y(1), U(1), B(1) H-e, 也就是e+x=h得4+x=7，密钥为3解密：hello，every one我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的

24、世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物惟密文攻击惟密文攻击维吉尼亚密码由m个移位密码构成，移位密码不改变字符的分布，故若能确定m，则可以找到每个移位密码的位移量kn克思斯基测试（Kasiski ）n若用给定的m个密钥表周期地对明文字母加密，则当明文中有两个相同字母组(长度大于3)在明文序列中间隔的字母数为m的倍数时，这两个明文字母组对应的密文字母组必相同。n但反过来，若密文中出现两个相同的字母组，它们所对应的明文字母组未必相同，但相同的可能性很大。n将密文中相同的字母组找出来，并对其相同字母数综合研究，找出它们的相同字母数的最大公因子，就有可能提取出有关密钥字的长

25、度m的信息。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物惟密文攻击惟密文攻击n例CHR出现5个位置：1,166,236,276,286距离差：165,235,275,285，gcd(165,235,275,285)=5 猜测 m=5我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物惟密文攻击惟密文攻击n重合指数法（Coincidence Index）n完全随机的文本CI=0.0385，一个有意义的英文文本CI=0.06

26、5我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物惟密文攻击惟密文攻击n实际使用CI的估计值CI：nL：密文长。：密文长。nfi：密文符号i发生的数目。n作用：n区分单表代换密码和多表代换密码n确定两段文本是否是同一种方法进行加密n确定维吉尼亚密码的m值我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物惟密文攻击惟密文攻击n例CI (C1)= 0.0412CI (C2)= 0.0445同一加密方法我吓了一跳，蝎子是多么丑恶

27、和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物惟密文攻击惟密文攻击1, 对于不同的m,重新对密文m分组2,对不同的分组，分别求取重合指数当m为5时，重合指数平均接近于0.065我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物惟密文攻击惟密文攻击n拟重合指数法我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物惟密文攻击惟密文攻击n对于一个移位密码我吓了一跳，蝎子

28、是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物惟密文攻击惟密文攻击我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物惟密文攻击惟密文攻击CHREEVOAHMAERATBIAXXWTNXBEEOPHBSBQMQEQERBWRVXUOAKXAOSXXWEAHBWGJMMQMNKGRFVGX我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物密文子串的拟重合指

29、数密文子串的拟重合指数我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物密文子串的交互重合指数（续）密文子串的交互重合指数（续）我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物明文明文The almond tree was in tentative blossom. The days were longer, often ending with magnificent evenings of corrugated pink

30、 skies. The hunting season was over,with hounds and guns put away for six months. The vineyards were busy again as the well-organized farmers treated their vines and the more lackadaisical neighbors hurried to do the pruning they should have done in November.我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是

31、我也感到愉快，证实我的猜测没有错：表里边有一个活的生物惟密文攻击惟密文攻击n移位密码、仿射密码和单表代换密码都没有破坏明文的频率统计规律，可以直接用统计分析法n维吉尼亚密码nKasiski测试和重合指数确定密钥长度mn密文按m分组后，利用频率分析或拟重合指数分析得到每个单表的密钥n利用单表密钥恢复明文我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物主要知识点小结主要知识点小结n代换密码n置换密码nHill密码n转轮密码n古典密码的惟密文攻击方法我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物作业作业nP43页 第4题（2）（4）（6）我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物57THE END！