1、密码学第二讲 古典密码2 2上节回顾n信息论n保密通信模型n密码分析n算法安全性3 3上节回顾1信息论n问题：有4个外表完全相同的硬币，其中3个重量完全一样，有一个重量不相同的伪币，用无砝码的天平，试问要做多少次的比较，可以找到这枚伪币并鉴别伪币轻重？4明文明文加密算法解密算法信道CMMC攻击者加密钥解密钥密钥 KKeKd安全信道上节回顾2通信保密模型5上节回顾2通信保密模型nKerckhoffs准则 假定攻击者知道加密/解密算法。要避免密码被攻击就要依靠密钥。n假定密码是足够安全的，不需要隐藏加密/解密算法。n例：DES-EES-AESn密码设计的公开原则核心密码：内部公开设计、评估商用密码
2、：公开设计、使用6 6上节回顾1信息论n解：事件V为找出伪币，可能有8个结论，他们是等概率，故H（V）= log28事件Ui为每次天平称的结果H（Ui）= log23令Ak=U1U2U3Uk为连续用k次天平的事件， k最少为2次只用只用2次比较可以解决次比较可以解决Example 3中的问题吗中的问题吗?7上节回顾2通信保密模型按照明文的处理方法分类n分组密码(block cipher)：将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出也是固定长度的密文。n流密码(stream cipher)：又称序列密码，每次加密一位或一字节的明文。按照密钥使用方法分类n对称密码算法(symmet
3、ric cipher)：又称传统密码算法(conventional cipher)或秘密密钥算法、单密钥算法。n非对称密钥算法(asymmetric cipher)，又称公开密钥算法(public-Key cipher) 或双钥密码算法。8上节回顾3密码分析n按攻击方法分类 穷举攻击统计分析攻击数学分析攻击n按攻击者可利用的数据资源分类唯密文攻击已知明文攻击选择明文攻击选择密文攻击9 9算法安全性n破译密码算法的代价数据复杂性时间复杂性空间复杂性n“计算上不可行计算上不可行” “工程上不可行工程上不可行”1010算法安全性n无条件安全如果无论攻击者得到多少密文，都没有足够的信息去恢复明文，那么
4、该算法就是无条件安全的理论上，只有“一次一密”的系统才能做到11算法安全性n除“一次一密”之外，所有的加密算法都不是无条件安全的。n实际可使用的密码应尽量满足：破译密码的代价超出密文信息的价值破译密码的时间超出密文信息的有效生命期 计算上安全：满足上述两条标准中的任意一条即可。12算法安全性事件概率备注每天被闪电杀死的概率90亿分之一233 9109赢得国家发行彩票头等奖的可能性4百万分之一222 4106赢得国家发行彩票头等奖并且在同一天被闪电杀死的概率1/255每年淹死的可能性59000分之一21659000一生死于交通事故的可能性88分之一2788到下一个冰川年代的时间14000年214
5、14000到太阳 变成新星的时间109年（10亿）230 109行星的年龄109年（10亿）230 109宇宙的年龄1010年（100亿）234 101013算法安全性n穷举攻击 (假设普通PC执行一次解密约需要1s)密钥大小(位)密钥个数每微秒执行一次解密所需时间每微秒执行一百万次解密所需的时间32232=4.3109231s=35.8mins2.15ms56256=7.21016255s=1142years10.01hours1282128=3.410382127s=5.41024years5.41018years1682168=3.710502167s=5.91036years5.910
6、30years26个字母的排列组合26!=4102621026s=6.41012years6.4106years14算法安全性nTOP500是全世界最权威的超级计算机排名榜。从1993年起，作为对全球已安装的超级计算机进行排名的权威机构，国际TOP500组织以计算机实测速度为基准，每年两次发布世界上最快的500台超级计算机排名。其中2011年6月榜单： 美国256个（5个 Top10）中国62个 （2个 Top10）15算法安全性n2010年11月14日，全球超级计算机前500强排行榜 国防科学技术大学 ，“天河一号” ，每秒2570万亿次。美国橡树岭国家实验室， “美洲豹”超级计算机，每秒1
7、750万亿次。中国曙光公司，“星云”高性能计算机，每秒1270万亿次。 16算法安全性n2011-06-22国际TOP500组织宣布，日本超级计算机“京”（K computer）以每秒8162万亿次运算速度成为全球最快的超级计算机，这是时隔7年，日本再回超级计算机榜单榜首。 “京”在日语中的意思是万万亿 。由日本富士通公司研发，日本理化学研究所组装 。整个超级计算机系统拥有8万个处理器，每个处理器配备8个处理核心。 17密码学的一些结论：密码学的一些结论：公开设计原则：密码的安全只依赖于密钥的保密，公开设计原则：密码的安全只依赖于密钥的保密，不依赖于算法的保密；不依赖于算法的保密；理论上绝对安
8、全的密码是存在的：一次一密；理论上绝对安全的密码是存在的：一次一密；理论上，任何实用的密码都是可破的；理论上，任何实用的密码都是可破的；我们追求的是计算上的安全。我们追求的是计算上的安全。计算上的安全：使用可利用的计算资源不能破译。计算上的安全：使用可利用的计算资源不能破译。 18思考题思考题19第二讲 古典密码n换位法（置换）n替代法（替代）n古典密码的分析20 古典密码古典密码 虽然用近代密码学的观点来看，许多虽然用近代密码学的观点来看，许多古典密码是很不安全的，或者说是极易古典密码是很不安全的，或者说是极易破译的。破译的。但是我们不能忘记古典密码在但是我们不能忘记古典密码在历史上发挥的巨
9、大作用。历史上发挥的巨大作用。 另外，另外，编制古典密码的基本方法对于编制古典密码的基本方法对于编制近代密码仍然有效。编制近代密码仍然有效。21密码学的发展史密码学的发展史n古代加密方法（手工阶段）n古典密码（机械阶段）n现代密码（计算机阶段）22古代加密方法古代加密方法n起源于公元前440年出现在古希腊战争中的隐写术 (steganography)：通过隐藏消息的存在来保护消息.n是现今信息隐藏的始祖 23隐写术n字符标记：印刷或打印的文本字母经选择用铅笔重写。该标记通常不可见，除非该纸以一定的角度对着亮光看。n不可见墨水：使用一些物质来书写，但不留下任何可见痕迹，除非加热该纸或在该纸上涂上
10、某种化学药品。n扎小孔：在所选的字母上扎小孔，这些小孔通常不可见，除非把该纸放在光的前面。n格孔密写卡：将它覆盖在一张纸上从格孔中写入密件，然后在纸上余下部分填入其它字句，使它像一般信件。24n例如：格孔密写卡密文：王先生： 来信收悉，你的盛情难以报答。我已在昨天抵达广州。秋雨连绵，每天需备伞一把。大约本月中旬即可返回，再谈。 弟：李明 明文：情报在雨伞把中。明文：情报在雨伞把中。25古代加密方法古代加密方法nPhaistos圆盘，一种直径约为160mm的Cretan-Mnoan粘土圆盘，始于公元前17世纪。表面有明显字间空格的字母，至今还没有破解。26nhttp:/en.wikipedia.
11、org/wiki/Phaistos_Disc27http:/en.wikipedia.org/wiki/Phaistos_DiscnSide A:02-12-13-01-18/ 24-40-12 29-45-07/ 29-29-34 02-12-04-40-33 27-45-07-12 27-44-08 02-12-06-18-? 31-26-35 02-12-41-19-35 01-41-40-07 02-12-32-23-38/ 39-1102-27-25-10-23-18 28-01/ 02-12-31-26/ 02-12-27-27-35-37-21 33-23 02-12-31-26
12、/ 02-27-25-10-23-18 28-01/ 02-12-31-26/ 02-12-27-14-32-18-27 06-18-17-19 31-26-12 02-12-13-01 23-19-35/ 10-03-38 02-12-27-27-35-37-21 13-01 10-03-38nSide B:02-12-22-40-07 27-45-07-35 02-37-23-05/ 22-25-27 33-24-20-12 16-23-18-43/ 13-01-39-33 15-07-13-01-18 22-37-42-25 07-24-40-35 02-26-36-40 27-25-3
13、8-0129-24-24-20-35 16-14-18 29-33-01 06-35-32-39-33 02-09-27-01 29-36-07-08/ 29-08-13 29-45-07/ 22-29-36-07-08/ 27-34-23-25 07-18-35 07-45-07/ 07-23-18-24 22-29-36-07-08/ 09-30-39-18-07 02-06-35-23-07 29-34-23-25 45-07/28http:/en.wikipedia.org/wiki/Phaistos_Disc29古代加密方法古代加密方法n斯巴达人用于加解密的一种军事设备(Sparta
14、n Scytale, 400 B.C.) 发送者把一条羊皮螺旋形地缠在一个圆柱形棒上思想：置换（permutation)30古代加密方法古代加密方法n斯巴达人用于加解密的一种军事设备(Spartan Scytale, 400 B.C.)n例：明文Help me I am under attack. 31古代加密方法古代加密方法n一个叫Aeneas Tacticus的希腊人在论要塞的防护一书中对传输密文做了最早的论述。n公元前2世纪，一个叫Polybius的希腊人设计了一种将字母编码成符号对的方法，他使用了一个称为Polybius的校验表，表中包含许多后来在加密系统中常见的方法，如代替与换位。3
15、2密码学的发展史密码学的发展史n古代加密方法（手工阶段）n古典密码（机械阶段）n现代密码（计算机阶段）33古典密码古典密码n古典密码系统已经初步体现出近代密码系统的雏形，它比古代加密方法复杂，其变化较小。n古典加密技术主要使用代替或者置换技术。n古典密码使用手工或机械变换的方式实现。34两种基本加密技术n代换（代替、替换）技术将明文字母替换成其它字母、数字或符号的方法。n置换（换位）技术保持明文的所有字母不变，只是打乱明文字母的位置和次序。35置换密码置换密码n将明文的字母顺序打乱，得到新的排列最简单的置换密码：栅栏技术 明文明文 meet me after the toga party 置换
16、方法置换方法 m e m a t r h t g p r y e t e f e t e o a a t 密文密文 mematrhtgpryetefeteoaat36古典密码置换密码n把明文中的字母重新排列，字母本身不变，把明文中的字母重新排列，字母本身不变，但其位置改变了，这样编成的密码称为置但其位置改变了，这样编成的密码称为置换密码。换密码。最简单的置换密码是把明文中的字母顺序倒过来，然后截成固定长度的字母组作为密文。明文：明晨明晨5点发动反攻。点发动反攻。 MING CHEN WU DIAN FA DONG FAN GONG密文：GNOGN AFGNO DAFNA IDUWN EHCGN
17、 IM37置换密码置换密码n列置换以固定的宽度把明文按行写入,按列读出 T H I S I S A M E S S A G E T O S H O W明文：明文：this is a message to show密文：密文：tssohaasimghseeoistw 38 例如：明文：MING CHEN WU DIAN FA DONG FAN GONG矩阵：MINGCH 选出顺序：按列按列 ENWUDI ANFADO 改变矩阵大小和取出序列改变矩阵大小和取出序列 NGFANG 可得到不同的密码可得到不同的密码 ONG密文：MEANO INNGN NWFFG GUAA CDDN HIOGb把明文按
18、某一顺序排成一个矩阵， 然后按另一顺序选出矩阵中的字母以形成密文，最后截成固定长度的字母组作为密文。39置换密码置换密码n带密钥的列置换把明文以固定宽度按行写入,按密钥规定的列次序按列读出字母明文：明文：this is a message to show密钥：密钥：43152密文：密文：IMGHISTWHAASTSSOSEEO T H I S I S A M E S S A G E T O S H O W4 3 1 5 240古典密码n换位法思路n打乱明文中各字母的顺序，使明文中的单词错乱，隐蔽其含义41古典密码n换位法方法n加密时，将明文的字符（一维数据）按照一定顺序放入高维空间（一维以上）
19、中，然后按照另一种顺序取出字符，形成密文（一维数据）n解密时，先将密文按照相应顺序放入高维空间中，再按照原始顺序取出明文42理论上：理论上：、置换密码的加密钥是置换矩阵、置换密码的加密钥是置换矩阵 p ， 解密钥是置换矩阵解密钥是置换矩阵 p-1 。、置换密码经不起已知明文攻击。、置换密码经不起已知明文攻击。 1 2 3 n a1 a2 a3 anP =43置换密码置换密码n置换密码除了排列字母和重新读取外，不需要另外的工作，处理时间是一个常量。存储空间与报文长度相关。完全保留字符的统计信息使用多轮加密可提高安全性44习 题已 知 换 位 密 码 的 换 位 表 为 ：（2,7,5,3,8,4
20、,6,1），试对明文 software 加密。答案：45习 题已 知 换 位 密 码 的 换 位 表 为 ：（2,7,5,3,8,4,6,1），试对明文 software 加密。答案：orwfetas46古典密码n换位法算法特点：易于手工操作，明密文都是字符串且等长算法缺陷：明文密文中的各字母出现次数是相同的，只是位置不同，密码分析员可以通过移动字母顺序进行破译经不起“已知明文攻击”47两种基本加密技术n代换（代替、替换）技术将明文字母替换成其它字母、数字或符号的方法。n置换（换位）技术保持明文的所有字母不变，只是打乱明文字母的位置和次序。48 首先构造一个或多个密文字母表，然后用密首先构造一
21、个或多个密文字母表，然后用密文字母表中的字母或字母组来代替明文字母或字文字母表中的字母或字母组来代替明文字母或字母组，各字母或字母组的相对位置不变，但其本母组，各字母或字母组的相对位置不变，但其本身改变了。这样编成的密码称为代替密码。身改变了。这样编成的密码称为代替密码。 单表代替密码单表代替密码 多表代替密码多表代替密码 多名代替密码多名代替密码49古典密码n替代法简单替代多表替代同音替代组合替代50n简单代替密码，又称为单字母代替密码：它将明文的一个字符用相应的一个密文字符代替。使用一个字母表（明文的一个字母总是被同一个固定的字母代换）的简单代替密码也称为单表代替密码。例如：Caesar密
22、码。n多字母代替密码：它是对多于一个字母进行代换例如：Playfair密码；Hill密码。n多表代替密码：是将明文消息中出现的同一个字母，在加密时不是完全被同一个固定的字母代换，而是根据其出现的位置次序，用不同的字母代换。例如： Vigenere密码。51 只使用一个密文字母表，并且用密文字母表中只使用一个密文字母表，并且用密文字母表中的一个字母来代替明文字母表中的一个字母。的一个字母来代替明文字母表中的一个字母。A a a0 0 , a , a1 1 ,., a ,., an-1n-1 B B b b0 0 , b , b1 1 ,., b ,., bn-1n-1 定义一个由定义一个由A A
23、到到 B B的映射：的映射：f:ABf:AB f(a f(ai i )= b )= bi i M =M =（m m0 0 , m , m1 1 ,., m ,., mn-1n-1 ）, ,C =(f(mC =(f(m0 0 ),f(m ),f(m1 1 ),.,f(m ),.,f(mn-1n-1 ) )。 简单代替密码的密钥就是简单代替密码的密钥就是映射函数映射函数f f或或密文密文字母表字母表 B。52、加法密码加法密码A A和和B B是有是有 n个字母的字母表。个字母的字母表。定义一个由定义一个由A A到到B B的映射：的映射：f:ABf:AB f(a f(ai i )= b )= bi
24、i=a=aj j j=i+k mod nj=i+k mod n加法密码是用明文字母在字母表中后加法密码是用明文字母在字母表中后面第面第 k k个字母来代替。个字母来代替。K=3 K=3 时是著名的凯撒密码。时是著名的凯撒密码。53代换密码代换密码单字母代换单字母代换nCaesar密码：公元前50年，由Julius Caesar 发明，最早用在军方。将字母表中的每个字母，用它后面的第3个字母代替 。加密：c = E(3,p) = (p + 3) mod 26解密：p = E(3,c) = (c - 3) mod 26A B C D E F G H I J K L M N O P Q R S T
25、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 C字母字母编码编码 明文：明文：System models 密文：密文：Vbvwhp prghov54替代法n单表代替密码举例n设密钥为k，加密规则是f(x) = (x + k) mod 26n当k = 3时明文 M = FIGHTATNIGHT ，被加密成密文Ek(M) = ILJKWDWQLJKWnC语言的实现方式c=(a-A)+k)%26)+A;选择具有自反特点的加密函数nf(a)=(k-a) mod 2655代换密码代换密码单字母代换单字母代换n一般的恺撒密码加密：
26、c = E(k,p) = (p + k) mod 26解密： p = E(k,c) = (c - k) mod 26其中k为密钥，1 k 25n一般的恺撒密码的破译分析已知加密和解密算法需要测试的密钥只有25个明文所用的语言是已知的，且其意义易于识别。因此：可以采用穷举攻击56练习练习n密文：PHHW PH DIWHV WKH WRJD SDVWB n算法：一般的凯撒密码n明文: ?meet me after the toga party 57已知加密和解密算法需要测试的密钥只有25个明文所用的语言是已知的，且其意义易于识别。因此：可以采用穷举攻击58Caesar 密码安全性 n上面的例子说明
27、，凯撒密码不足以对抗穷举攻击。因此是不安全的。n这个例子说明一个密码体制安全至少要能够抵抗穷举密钥搜索攻击，普通的做法是将密钥空间变得足够大。n但是，很大的密钥空间并不是保证密码体制安全的充分条件，下面的例子可以说明这一点。 59代换密码代换密码单表代换单表代换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 Zw o r d A B C E F G H I J K L M N P Q R S T U V X Y Z字母字母编码编码密钥词为密钥词为word60单表代换分析n密钥空间增加(2
28、6!)，穷举搜索这么多的密钥很困难n但这并不表示该密码不容易破解n破解这类密码的突破点是由于语言本身的特点是充满冗余的，每个字母使用的频率不相等 n而单表代换密码没有改变字母相对出现的频率n明文字母的统计特性在密文中能够反映出来, 当通过统计密文字母的出现频率，可以确定明文字母和密文字母之间的对应关系61、乘法密码乘法密码A A和和B B是有是有n个字母的字母表。个字母的字母表。定义一个由定义一个由A A到到B B的映射：的映射：f:ABf:AB f(a f(ai i )= b )= bi i= a= aj j j=ik mod nj=ik mod n 其中，其中，(n,k)=1(n,k)=1
29、。注意：只有注意：只有(n,k)=1(n,k)=1，才能正确解密，才能正确解密62、乘法密码乘法密码A A要求要求k与与n互素。这是因为仅当（互素。这是因为仅当（k，n）=1时，才存在两时，才存在两个整数个整数x,y使得使得xk+yn =1,才有才有xk=1 mod n，才有，才有i=xj mod n，密码才能正确解密。，密码才能正确解密。 例如，取例如，取k=13时，因为时，因为(13,26)=131，便会出现，便会出现： f(A)=f(C)=f(E)= f(G)=f(I)=f(K)= f(M)=f(O)=f(Q)= f(S)= f(U)= f(W)=f(Y)=Af(B)=f(D)=f(F)
30、= f(H)=f(J)=f(L)= f(N)=f(P)=f(R)= f(T)= f(V)= f(X)= f(Z)=N整个密文字母表只包含整个密文字母表只包含A和和N两个字母，密文将不两个字母，密文将不能正确解密。能正确解密。 63、乘法密码乘法密码A A要求要求k与与n互素。这是因为仅当（互素。这是因为仅当（k，n）=1时，才时，才存在两个整数存在两个整数x,y使得使得xk+yn =1,才有才有xk=1 mod n，才有才有i=xj mod n，密码才能正确解密。，密码才能正确解密。 例如，取例如，取k=5时，因为时，因为(5,26)=1，得，得： A=A,B,C,D,E,F,G,H,I,J,
31、K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,ZB=A,F,K,P,U,Z,E,J,O,T,Y,D,I,N,S,X.C,H,M,R,W,B,G,L,Q,V64、乘法密码乘法密码k的取值范围？的取值范围？ 65乘法密码乘法密码k的取值范围？的取值范围？ 欧拉函数：少于或等于n的数中与n互质的数的数目n(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4).(1-1/pn), n其中p1, p2pn为x的所有质因数，x是不为0的整数 n若x=p1p2,则(x)=(p1-1)(p2-1)66仿射密码密码A A和和B B是有是有n个字母的字母表。个字母的字母表。定义一
32、个由定义一个由A A到到B B的映射：的映射：f:ABf:AB f(a f(ai i )= b )= bi i= a= aj j j= ikj= ik1 1+ k+ k0 0 mod n mod n 要求：要求：1 10 01 10 0 67密钥词组代替密码：密钥词组代替密码： 随机选一个词语，去掉其中的重随机选一个词语，去掉其中的重复字母，写到矩阵的第一行，从明文复字母，写到矩阵的第一行，从明文字母表中去掉这第一行的字母，其余字母表中去掉这第一行的字母，其余字母顺序写入矩阵。然后按列取出字字母顺序写入矩阵。然后按列取出字母构成密文字母表。母构成密文字母表。6869替代法n简单替代特点n易于手
33、工操作，明密文都是字符串且等长，明文中的字母在密文中都以其他字母所取代缺陷n明文字母的出现次数与相应密文字母的出现次数是相同的，因而明文中的字母统计特性在密文中也存在，容易被攻击。（例如：明文中字母e出现得最多，而加密后字母h出现得最多）70代换密码代换密码多字母代换多字母代换nPlayfair密码1854年由英国科学家Charles Wheatstone发明。将明文中的双字母音节作为一个单元并将其转换成密文的“双字母音节”。算法基于一个由密钥词构成的55字母矩阵。 71n例：密钥词为monarchy，明文为balloon如果该字母对两个字母相同，则它们之间加一个填充字母，如x ；则明文分为四
34、个字母对：ba lx lo on落在矩阵同一行的明文字母对中的字母由其右边的字母替换；on替换成na落在矩阵同一列的明文字母对中的字母由其下面的字母替换；ba替换成ib(或jb)其他的每组明文字母对中的字母如下替换：它所在的行是该字母的所在行，列则为另一个字母的所在列。 lo替换成pm lx替换成suMONARCHYBDEFGI/JKLPQSTUVWXZ密文为：密文为：ibsupmna或或jbsupmna72Playfair密码的安全性密码的安全性nPlayfair密码的安全性比单表代换密码提高了许多 n双字母共有26 x 26 = 676 组合，因此频率统计分析表中需要676 条统计数据 n
35、Playfair 密码中比单表代换更好地隐藏了明文中单字母的结构 n在第一次世界大战中被英军作为最好的密码系统使用，在第二次世界大战中也曾经被美军和盟军大量使用 n当然现在看来，该密码的安全性是很低的，它还保留了明文的部分特征，只要给定几百个字母的密文情况下，该加密方法就可以破解 73练习：练习： Playfair加密加密n假设密钥是cipher，使用Playfair算法加密如下明文：Playfair cipher was actually invented by wheatston 74练习：练习： Playfair加密加密n由密钥词cipher可构建密钥矩阵：n将明文按照两个字母分组为 p
36、l ay fa ir ci ph er wa sa ct ua lx ly in ve nt ed by wh ea ts to nxn则密文为 BS DW RB CA IP HE CF IK QB HO QF SP MX EK ZC MU HF DX YI IF UT UQ LZ CI/JPHERABDFGKLMNOQSTUVWXYZ75代换密码代换密码多字母代换多字母代换nHill 密码密码是1929年由数学家lester Hill发明的一种多字母代换密码 n加密算法将m个明文字母替换成m个密文字母(Hillm密码表示m个明文字母为一组) n这种代换由 m个线性方程决定n如果m=3，则该密
37、码系统可以表示为： 76n用向量或者矩阵表示为：n其中C和M是长度为3的列向量，分别代表密文和明文，K是一个33的矩阵，代表加密密钥n运算按照模26执行。 77Hillm 密码加密过程 n将明文字母以m个字母为单位进行分组，若最后一组没有m个字母，则补足没有任何实际意义的哑字母（双方事先可以约定这些字母），并用数字表示这些字母；n选择一个m阶可逆方阵K，称为Hillm密码的加密矩阵；n对每m个字母为一组的明文字母，用它对应的值构成一个m维向量M； n计算密文的值C=KM mod26，然后反查字母表的值，得到对应的m个密文字母；n同样处理明文的其他组。78Hillm 密码解密过程n解密要用到K的
38、逆矩阵K-1作为解密密钥n解密过程：K-1C=K-1KM=M79古典密码的穷举分析古典密码的穷举分析1.1.单表代替密码分析单表代替密码分析加法密码加法密码因为因为f(af(ai i)= b)= bi i=a=aj j j=i+k mod nj=i+k mod n所以所以k=1,2k=1,2，. ,n-1,. ,n-1,共共n-1n-1种可能，密钥空种可能，密钥空间太小。以英文为例，只有间太小。以英文为例，只有2525种密钥。种密钥。经不起穷举攻击。经不起穷举攻击。801.1.单表代替密码分析乘法密码因为f(ai )= bi=aj j=ik mod n，且（k,n）=1。所以k共有（n）种可能
39、，密钥空间更小。对于英文字母表，n=26，k=1,3,5,7,9,11,15,17,19,21,23,25 取掉1，共11种，比加法密码更弱。经不起穷举攻击。81古典密码的穷举分析古典密码的穷举分析1.1.单表代替密码分析单表代替密码分析密钥词语代替密码密钥词语代替密码因为密钥词语的选取是随机的，所以密文字母因为密钥词语的选取是随机的，所以密文字母表完全可能穷尽明文字母表的全排列。表完全可能穷尽明文字母表的全排列。 以英文字母表为例，以英文字母表为例，n=26n=26，所以共有，所以共有2626！种可！种可能的密文字母表。能的密文字母表。 26 26！44 10102626用计算机也不可能穷举
40、攻击。用计算机也不可能穷举攻击。注意：穷举不是攻击密钥词语代替密码的唯一注意：穷举不是攻击密钥词语代替密码的唯一方法。方法。82古典密码的统计分析古典密码的统计分析密钥词组单表代替密码的统计分析密钥词组单表代替密码的统计分析 任何自然语言都有自己的统计规律。任何自然语言都有自己的统计规律。如果密文中保留了明文的统计特征，就可用统如果密文中保留了明文的统计特征，就可用统计方法攻击密码。计方法攻击密码。由于单表代替密码只使用一个密文字母表，一由于单表代替密码只使用一个密文字母表，一个明文字母固定的用一个密文字母来代替，所个明文字母固定的用一个密文字母来代替，所以密文的统计规律与明文相同。以密文的统
41、计规律与明文相同。因此，单表代替密码可用统计分析因此，单表代替密码可用统计分析攻破。攻破。83古典密码的统计分析古典密码的统计分析n英语的统计规律英语的统计规律 每个单字母出现的频率稳定。每个单字母出现的频率稳定。 最高频率字母最高频率字母 E E 次高频率字母次高频率字母 T A O I N S H R T A O I N S H R 中高频率字母中高频率字母 D L D L 低频率字母低频率字母 C U M W F G Y P B C U M W F G Y P B 最低频率字母最低频率字母 V K J X Q Z V K J X Q Z 84字母 期望值 实际值 %A 8.0 7.5 *
42、B 1.5 1.4 *C 3.0 4.1 *D 4.0 3.2 *E 13.0 12.7 *F 2.0 2.3 *G 1.5 1.9 *H 6.0 3.8 *I 6.5 7.7 *J 0.5 0.2 K 0.5 0.4 *L 3.5 3.8 *M 3.0 3.0 *N 7.0 7.0 *O 8.0 7.5 *P 2.0 3.0 *Q 0.2 0.2R 6.5 6.7 *S 6.0 7.3 *T 9.0 9.2 *U 3.0 2.8 *V 1.0 1.0 *W 1.5 1.4 *X 0.5 0.3 *Y 2.0 1.6 *Z 0.2 0.1每个*代表0.5%字母总数为: 67375单字母频率分布
43、图 85英文字母统计特性英文字母统计特性英文单字母的相对频率表英文单字母的相对频率表86n单字母按照出现频率的大小可以分为下面5类： (1) e：出现的频率大约为0.127 (2) t, a, o, I, n, s, h, r：出现的频率大约在0.06-0.09之间 (3) d, l：出现的频率约为0.04 (4) c, u, m, w, f, g, y, p, b：出现的频率大约在0.015-0.028之间 (5) v, k, j, x, q, z：出现的频率小于0.01英文字母统计特性英文字母统计特性87古典密码的统计分析古典密码的统计分析n英语的统计规律英语的统计规律 频率最高的双字母组
44、：频率最高的双字母组： TH HE IN ER AN RE ED ONTH HE IN ER AN RE ED ON ES ST EN AT TO NT HA ND ES ST EN AT TO NT HA ND OU EA NG AS OR TI IS ET OU EA NG AS OR TI IS ET IT AR TE SE HI OF IT AR TE SE HI OF 88古典密码的统计分析古典密码的统计分析n英语的统计规律英语的统计规律 频率最高的三字母组：频率最高的三字母组： THE ING AND HER ERE ENT THA WASTHE ING AND HER ERE E
45、NT THA WAS ETH FOR DHT HAT SHE ION HIS ERS ETH FOR DHT HAT SHE ION HIS ERS VER VER 其中其中THETHE的频率是的频率是INGING的的3 3倍！倍！ 89n双字母和三字母组合都有现成的统计数据，常见的双字母组合和三字母组合统计表能够帮助破解密文。n频率最高的30个双字母（按照频率从大到小排列）： th he in er an re ed on es st en at to nt ha nd ou ea ng as or ti is et it ar te se hi of n 频率最高的20个3字母（按照频率从
46、大到小排列）： the ing and her ere ent tha nth was eth for dth hat she ion int his sth ers ver英文字母统计特性英文字母统计特性90古典密码的统计分析古典密码的统计分析n英语的统计规律英语的统计规律 英文单词以英文单词以E E，S S，D D，T T为结尾的超过一半。为结尾的超过一半。英文单词以英文单词以T T，A A，S S，W W为起始字母的约占一为起始字母的约占一半。半。还有其它统计规律！还有其它统计规律！ 91替代法n多表代替思路n采用多个代替密钥交替加密明文，以减弱频率特性92代换密码代换密码多表代换多表代
47、换n多表代换：在明文消息中采用不同的单表代换。n特征：采用相关的单表替换规则集由密钥决定给定替换的具体规则93代换密码代换密码多表代换多表代换nVigenere密码1858年法国密码学家维吉尼亚提出替换规则由26个类似caesar密码的替换表组成，其中每一个替换表是对明文字母移位0到25次后得到的替换单表。每个替换单表由一个密钥字母表示。94单表代替密码的安全性不高，一个原因是一个明文字母只由一个密文字母代替。构造多个密文字母表，在密钥的控制下用相应密文字母表中的一个字母来代替明文字母表中的一个字母。一个明文字母有多种代替。 Vigenere密码：著名的多表代替密码95明文A B C D E
48、F G H I J K L M N O P Q R S T U V W X Y ZA 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 ZB B C D E F G H I J K L M N O P Q R S T U V W X Y Z AC C D E F G H I J K L M N O P Q R S T U V W X Y Z A BD D E F G H I J K L M N O P Q R S T U V W X Y Z A B CE E F G H I J K L M N O P Q R S T U V W X Y Z A
49、 B C DF F G H I J K L M N O P Q R S T U V W X Y Z A B C D EG G H I J K L M N O P Q R S T U V W X Y Z A B C D E FH H I J K L M N O P Q R S T U V W X Y Z A B C D E F GI I J K L M N O P Q R S T U V W X Y Z A B C D E F G HJ J K L M N O P Q R S T U V W X Y Z A B C D E F G H IK K L M N O P Q R S T U V W X
50、 Y Z A B C D E F G H I JL L M N O P Q R S T U V W X Y Z A B C D E F G H I J KM M N O P Q R S T U V W X Y Z A B C D E F G H I J K LN N O P Q R S T U V W X Y Z A B C D E F G H I J K L MO O P Q R S T U V W X Y Z A B C D E F G H I J K L M NP P Q R S T U V W X Y Z A B C D E F G H I J K L M N OQ Q R S T U
