古典密码技术ppt课件.ppt

《古典密码技术ppt课件.ppt》由会员分享，可在线阅读，更多相关《古典密码技术ppt课件.ppt（97页珍藏版）》请在三一办公上搜索。

1、第1章 密码学概述第2章 古典密码技术第3章 分组密码第4章 公钥密码体制 第5章 散列函数与消息鉴别 第6章 数字签名技术 第7章 密钥管理技术第8章 身份鉴别技术 第9章 序列密码基础 第10章 密码技术应用,课程主要内容,第2章 古典密码技术,本章主要内容替代密码 置换密码 周期置换密码 列置换密码 转轮机密码 古典密码的统计分析 单表替代密码分析 多表替代密码分析 对Hill密码的已知明文分析,这些密码算法大多都十分简单，现在已经很少在实际应用中使用了。但是研究这些密码的原理，对于理解、构造和分析现代实用的密码都是很有益的。,第2章 古典密码技术,2.1 替代密码 (substitut

2、ion cipher)替代是古典密码中用到的最基本的处理技巧之一 ；替代密码是指先建立一个替换表，加密时将需要加密的明文依次通过查表，替换为相应的字符，明文字符被逐个替换后，生成无任何意义的字符串，即密文，替代密码的密钥就是其替换表 ；根据密码算法加解密时使用替换表多少的不同，替代密码又可分为单表替代密码和多表替代密码。 单表替代密码: 密码算法加解密时使用一个固定的替换表； 多表替代密码: 密码算法加解密时使用多个替换表。,第2章 古典密码技术,（1）一般单表替代密码 一般单表替代密码的原理是以26个英文字母集合上的一个置换为密钥，对明文消息中的每个字母依次进行变换。 可描述为：明文空间M和

3、密文空间C都是26个英文字母的集合，密钥空间K=：Z26Z26|是置换，是所有可能置换的集合。 对任意K，定义: 加密变换：e(m)=(m)=c 解密变换：d(c) = -1(c)=m， -1是的逆置换。,2.1.1 单表替代密码,第2章 古典密码技术,abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABC,caesar cipher,FDHVDU FLSKHU,明文密文,密码替代表,第2章 古典密码技术,一般单表替代密码算法特点：密钥空间K很大，|K|=26!=41026 ，破译者穷举搜索计算不可行，1微秒试一个密钥，遍历全部密钥需要1013

4、 年。移位密码体制是替换密码体制的一个特例，它仅含26个置换做为密钥空间。密钥不便记忆。 针对一般替换密码密钥不便记忆的问题，又衍生出了各种形式单表替代密码。,2.1.1 单表替代密码（续）,第2章 古典密码技术,（2）移位密码 明文空间M、密文空间C都是和密钥空间K满足,2.1.1 单表替代密码（续）,表2.1 字母数字映射表,即把26个英文字母与整数0，1，2，25一一对应，如表：,第2章 古典密码技术,加密变换，E=E:Z26Z26, Ek (m) = m + k (mod26)| mM, kK 解密变换，D=D:Z26Z26, Dk (c) = ck (mod26)| cC, kK 解

5、密后再把Z26中的元素转换英文字母。 显然，移位密码是前面一般单表替代密码的一个特例。当移位密码的 密钥k=3时，就是历史上著名的凯撒密码（Caesar）。根据其加密函数特 点，移位密码也称为加法密码。,2.1.1 单表替代密码（续）,abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABC,caesar cipher,FDHVDU FLSKHU,明文密文,第2章 古典密码技术,（3）仿射密码 仿射密码也是一般单表替代密码的一个特例，是一种线性变换。仿射密码的明文空间和密文空间与移位密码相同，但密钥空间为 K=(k1，k2)| k1，k2Z26，

6、gcd(k1，26)=1 对任意mM，cC，k = (k1，k2)K，定义加密变换为： c = Ek (m) = k1 m +k2 (mod 26)相应解密变换为： m = Dk (c) = k11 (ck2) (mod 26),2.1.1 单表替代密码（续）,其中， 。 很明显，k1=1时即为移位密码，而k2=0则称为乘法 密码。,第2章 古典密码技术,【例2.3】设明文消息为china，密钥k=(k1, k2)=(9,2) 试用仿射密码对其进行加密，然后再进行解密。,2.1.1 单表替代密码（续）,明文消息对应的数字序列为（2，7，8，13，0），用仿射密码对明文进行加密 如下：,解密变换

7、为：,解：利用扩展的欧几里德算法可计算出 加密变换为：,第2章 古典密码技术,密文消息为unwpc(20,13,22,15,2)。而解密过程如下：,2.1.1 单表替代密码（续）,即恢复明文消息为china。 仿射密码要求(k1, 26)=1 ，否则就会有多个明文字母对应一个密文字母的情况。由于与26互素的整数有12个，故仿射密码密钥空间大小为|K|=1226=312。 若将仿射密码的加密函数换为多项式函数时，即为多项式密码。,第2章 古典密码技术,（4）密钥短语密码 选用一个英文短语或单词串作为密钥，去掉其中重复的字母得到一个无重复字母的字符串，然后再将字母表中的其它字母依次写于此字母串后，

8、就可构造出一个字母替代表。 如密钥为key时，替代表如表2.2所示。,2.1.1 单表替代密码（续）,当选择上面的密钥进行加密时，若明文为“china”，则密文为“yfgmk”。 显然，不同的密钥可以得到不同的替换表，对于明文为英文单词或短语的情况时，密钥短语密码最多可能有26!=41026个不同的替换表。,第2章 古典密码技术,最大问题： 单表替代密码表现出明文中单字母出现的频率分布与密文中相同。 英文单字母出现概率顺序：e, t, o, a, n, i,.，th, er, re, an,，the, ing, ion, 而单表代替密码算法的最大缺陷就在于具有单字母一一的对应关系，它没有将明文

9、字母出现的概率掩藏起来，故在实际应用中，可利用自然语言的统计特性来破译这种密码。 例如，破译者可以统计出所截获密文中的高频率出现的代码，与表中高频率字(字母)相对应，使用猜字法，找出其中的对应关系，推断出密钥，从而破解密码。（书P28，表2.4）,（5）单表替换密码的安全性分析,英文字母出现频率 (不同文献类略有差别),第2章 古典密码技术,英语字母中常见的组合,第2章 古典密码技术,第2章 古典密码技术,多表替代密码的特点是使用了两个或两个以上的替代表。著名的弗吉尼亚密码和Hill密码等均是多表替代密码。（1）弗吉尼亚密码（Vigenere） 弗吉尼亚密码是最古老而且最著名的多表替代密码体制

10、之一，与位移密码体制相似，但弗吉尼亚密码的密钥是动态周期变化的。 该密码体制有一个参数n。在加解密时，同样把英文字母映射为025的数字再进行运算，并按n个字母一组进行变换。 明文空间、密文空间及密钥空间都是长度为n的英文字母串的集合。因此可表示为：,2.1.2 多表替代密码,单表替换密码局限：明文字母(字)与密文字母(字)一一对应。,第2章 古典密码技术,加密变换定义如下： 设密钥 k=(k1,k2,kn), 明文m=(m1,m2,mn), 加密变换为： Ek(m)=(c1,c2,cn) , 其中ci=(mi + ki) (mod26) ，i =1,2,n 对密文 c=(c1,c2,cn),

11、解密变换为： Dk(c)=(m1,m2,mn), 其中 mi=(ci ki)(mod26)，i =1,2,n,2.1.2 多表替代密码（续）,第2章 古典密码技术,【例2.4】设密钥k =cipher，明文消息appliedcryptosystem， 试用弗吉尼亚密码对其进行加密，然后再进行解密。解：由密钥k=cipher，得n=6，密钥对应的数字序列为 (2，8，15，7，4，17)。然后将明文按每6个字母进行分组，并转换这些明文字母为相应的数字，再用模26加上对应密钥数字，其加密过程如表2.3所示。,2.1.2 多表替代密码（续）,密文为：CXTSMVFKGFTKQANZXVO。（解密，略

12、）,（2）希尔（Hill）密码 Hill密码算法的基本思想是将n个明文字母通过线性变换，将它们转换为n个密文字母。解密只需做一次逆变换即可。 算法的密钥K =Z26上的nn可逆矩阵，明文M与密文C 均为n维向量，记为,第2章 古典密码技术,2.1.2 多表替代密码（续）,加密运算： Ek(M)= K M= C (mod 26)解密运算： Dk(C)= K 1 C = M (mod 26) 其中， K 1 称为K在模26上的逆矩阵，有： K K 1 = K 1 K=I ；这里 I 为单位矩阵,第2章 古典密码技术,定理2.1：假设A = ( ai,j) 为一个定义在Z26上的nn矩阵，若A 在模

13、26上可逆，则有： A 1= ( det A ) 1 A* (mod 26 ) ； 这里A*为矩阵A的伴随矩阵。,例如，,在n = 2的情况下，有下列推论：,第2章 古典密码技术,这时11mod26=1，所以K的逆矩阵为：,2.1.2 多表替代密码（续）,【例2.5】设明文消息为good，试用n2，密钥 的Hill密码对其进行加密，然后再进行解密。,解：将明文划分为两组：(g，o ) 和 (o，d )，即（6，14）和（14，3）。加密过程如下：,因此，good的加密结果是wmwl。显然，明文不同位置的字母“o”加密成的密文字母不同。,第2章 古典密码技术,为了解密，由前面计算有 ，可由密文解

14、密计算出明文：,2.1.2 多表替代密码（续）,因此，解密得到正确的明文“good”。,第2章 古典密码技术,Hill密码特点：可以较好地抑制自然语言的统计特性，不再有单字母替换的一一对应关系，对抗“惟密文攻击”有较高安全强度。密钥空间较大，在忽略密钥矩阵K可逆限制条件下，|K|=26nn 易受已知明文攻击及选择明文攻击（详见2.3节相关分析）。（3）一次一密密码（One Time Pad） 若替代码的密钥是一个随机且不重复的字符序列，这种密码则称为一次一密密码，因为它的密钥只使用一次。 该密码体制是美国电话电报公司的Joseph Mauborgne在1917年为电报通信设计的一种密码，所以又

15、称为Vernam密码。Vernam密码在对明文加密前首先将明文编码为（0，1）序列，然后再进行加密变换。,2.1.2 多表替代密码（续）,第2章 古典密码技术,设m=(m1 m2 m3 mi )为明文,k=(k1 k2 k3 ki )为密钥,其中mi,ki (0,1), i1, 则加密变换为： c=(c1 c2 c3 ci ) ,其中ci mi ki , i1,2.1.2 多表替代密码（续）,m=(m1 m2 m3 mi ) ,其中mi ci ki , i1,这里为模2加法（或异或运算）,解密变换为：,在应用Vernam密码时，如果对不同的明文使用不同的随机密钥，这时Vernam密码为一次一密

16、密码。 由于每一密钥序列都是等概率随机产生的，敌手没有任何信息用来对密文进行密码分析。香农（Claude Shannon）从信息论的角度证明了这种密码体制在理论上是不可破译的。但如果重复使用同一个密钥加密不同的明文，则这时的Vernam密码就较为容易破译。,算法描述：,第2章 古典密码技术,2.1.2 多表替代密码（续）,若敌手获得了一个密文c=(c1 c2 c3 ci ) 和对应明文m=(m1 m2 m3 mi ) 时，就很容易得出密钥 k=(k1 k2 k3 ki ) ，其中ki ci mi ，i1。 故若重复使用密钥，该密码体制就很不安全。,实际上Vernam密码属于序列密码，加密解密方

17、法都使用模2加，这使软硬件实现都非常简单。但是，这种密码体制虽然理论上是不可破译的，然而在实际应用中，真正的一次一密系统却受到很大的限制，其主要原因在于该密码体制要求： 密钥是真正的随机序列； 密钥长度大于等于明文长度； 每个密钥只用一次（一次一密）。 这样，分发和存储这样的随机密钥序列，并确保密钥的安全都是很因难的；另外，如何生成真正的随机序列也是一个现实问题。因此，人们转而寻求实际上不对攻破的密码系统。,第2章 古典密码技术,替代时基于一个55的字母矩阵。字母矩阵构造方法同密钥短语密码类似。 例如，密钥K= playfair is a digram cipher，去除重复字母后，K=pla

18、yfirsdgmche，可得字母矩阵如图2.1。,2.1.2 多表替代密码（续）,（4）Playfair密码 Playfair密码是一种著名的双字母单表替代密码，实际上属于一种多字母替代密码，它将明文中的双字母作为一个单元对待，并将这些单元转换为密文字母组合。,第2章 古典密码技术,对每一明文字母对P1、P2的加密方法如下：（1）若P1、P2在同一行，密文C1、C2分别是紧靠P1、P2右端的字母；（2）若P1、P2在同一列，密文C1、C2分别是紧靠P1、P2下方的字母；（3）若P1、P2不在同一行，也不在同一列，则C1、C2是由P1、P2确定的矩形其它两角的字母，且C1和P1在同一行，C2和P

19、2在同一行；（4）若P1P2，则两个字母间插入一个预先约定的字母，如x，并用前述方法处理； 如balloon，则以ba lx lo on 来加密。（5）若明文字母数为奇数，则在明文尾填充约定字母。 算法还约定字母矩阵中第一列看做最后一列的右边一列，表中第一行看做最后一行的下一行。,2.1.2 多表替代密码（续）,Playfair密码 （续）,加密举例，明文：P = playfair cipher,明文分组：pl ay fa ir ci ph er密文分组：LA YF PY RS MR AM CD,第2章 古典密码技术,Playfair密码特点：,Playfair密码与简单的单一字母替代法密码相

20、比有了很大的进步。（1）虽然仅有26个字母，但有2626676种双字母组合因此识别各种双字母组合要困难得多。（2）各个字母组的相对频率要比双字母组合呈现出大得多的范围，使得频率分析困难得多。 因此， Playfair密码过去长期被认为是不可破的，它被英国陆军在第一次世界大战中作为一流密码系统使用，并在第二次世界大战中仍被美国陆军和其他同盟国大量使用。 但 Playfair密码还是相对容易攻破，因为它仍然使许多明文语言的结构保存完好，能够被密码分析者所利用。几百字的密文通常就可以攻破该密码。,第2章 古典密码技术,第2章 古典密码技术,如密本密码、连锁式密码(无密钥, 密文自身密钥, 明文自身密

21、钥)等。基本思路： 将一组字符（包括文字、单词、语句甚至短文）分别用各自不同的其它文字群来代替，如： the-ABD，sh-AD， 早期的数字传呼机短语代码等等。 实际上，使用暗语传递消息就可看成是多字母替换的一种应用（称为密本密码，codetext ）。,（5）其他替换密码算法：,第2章 古典密码技术,方法：利用明文的首位字母作为加密初始密钥（如位移密码），然后再把得到的密文字母作为后面相邻字母的密钥逐次进行加密。解密时则将相邻左边的字母作为密钥进行解密。 如：this-MTBT shee-KRVZ,如一种连锁式密码算法,（5）其他替换密码算法：,特点：字符替换不再具有一对一的替换关系，数据

22、内容彼此相关，通信中存在误码扩散问题。 这种使数据内容彼此相关的思想广泛被现代基于计算机处理的加密算法用来进行数据完整性的保护。（其他改进算法，如明文自身密钥、密文自身密钥等）,t+tM; (19+1912 mod26)h+MT; (7+1219 mod26)i+TB; (8+191 mod26)s+BT; (18+119 mod26),第2章 古典密码技术,置换密码又称为换位密码；置换密码通过改变明文消息各元素的相对位置，但明文消息元素本身的取值或内容形式不变；在前面的替代密码中，则可以认为是保持明文的符号顺序，但是将它们用其它符号来替代；这种密码是把明文中各字符的位置次序重新排列来得到密文

23、的一种密码体制。实现的方法多种多样。直接把明文顺序倒过来，然后排成固 定长度的字母组作为密文就是一种最简单的置换密码。 下面再给出几种典型的置换密码算法。,2.2 置换密码 ( Permutation Cipher ),第2章 古典密码技术,2.2.1 周期置换密码周期置换密码是将明文字符按一定长度n分组，把每组中的字符按1，2，n的一个置换重排位置次序来得到密文的一种加密方法。其中的密钥就是置换，在的描述中包含了分组长度的信息。解密时，对密文字符按长度n分组，并按的逆置换-1把每组字符重排位置次序来得到明文。,2.2 置换密码 ( 续 ),第2章 古典密码技术,2.2.1 周期置换密码（续）

24、,设n为固定的正整数，P = C = (Z26)n , K是由 1，2，n 的所有置换构成。对一个密钥K，定义： 加密变换： E (m1, m2,., mn) = (m(1),., m(n) =( c1, c2,., cn),周期置换密码可描述为:,第2章 古典密码技术,2.2.1 周期置换密码（续）,解：密钥长度是6，所以按周期长度6对明文分组，对每组字母用密钥 进行重排得到对应的加密结果。明文分组为：crypto|graphy，再利用置换密钥进行加密变换，得：E (crypto) = (ytcopr); E (graphy) = (ahgypr) 即密文消息为ytcoprahgypr。,注

25、意：置换密码密钥的不同表示方式,显然由加密置换可求出逆置换，-1=（3 6 1 5 2 4），根据密文和逆置换-1即可直接明文。,第2章 古典密码技术,必须要指出的是，置换密码在实质上是Hill密码的特例。所以置换密码属线性变换的密码。,2.2.1 周期置换密码（续）,给定一个集合1，2， . . .，n的置换，写出置换矩阵为：,；表示仅第i行中第(i)个元素为1，其余为零。,这时，置换矩阵是每一行和每一列都刚好有一个“1”，而其余元素为“0”的稀疏矩阵。如上例的加解密置换 =(3 5 1 6 4 2)， -1=（3 6 1 5 2 4），对应的置换矩阵为：,第2章 古典密码技术,= (3 5

26、 1 6 4 2) -1=（3 6 1 5 2 4）,Hill加密： 解密：,可见，置换密码实质上是输入分组的一个线性变换。,第2章 古典密码技术,这种密码的加密方法就是将明文按行填写到一个列宽固定（设为m）的表格或矩阵中；然后按（1，2，m）的一个置换交换列的位置次序，再按列读出即得密文。,2.2.2 列置换密码,明文：This boy is a worker,密钥为 (4，3，2，1)。,【思考】如果明文字母的长度不是列宽m的整倍数，加解密时会有什么问题，应如何处理？,其它置换密码：列变位密码、图形置换密码等等。,【基本原理】先按一定的方向把明文输入到某种预先规定的图形中，再按另一种方向输

27、出密文字符。不足部分填入约定字符。,例2.8,密文：sior iywe hoak tbsr,第2章 古典密码技术,2.3 转轮机密码,(Rotor Machine),转轮机的基本结构由一个键盘、若干灯泡和一系列转轮组成，如图1.4（a）所示。,最著名的是恩尼格马(Enigma，“哑谜”)。 在第二次世界大战期间由德国人使用。 4轮ENIGMA在1944年装备德国海军，据说英国从1942年2月到12月都没能解读德国潜艇的信号。 二次大战期间，波兰和英国人破译了德国的Enigma ；美国密码分析人员攻破了日本的RED， ORANGE和PURPLE，使盟军获胜起到了重要作用.,第2章 古典密码技术,

28、精密的转轮,第2章 古典密码技术,相邻排列的三个转子,转子的结构,具有V形刻痕的外环显示触点A位置的一个标记字母环金属触点连接触点与管脚的线路管脚调节器轴方便操作员转动的外环棘轮（防止倒转）,第2章 古典密码技术,一个恩尼格玛密码机转子的左侧，此图显示了平整的金属触点。,这个转子的右侧，此图显示了它的金属管脚。,一个转轮的侧面,第2章 古典密码技术,连接触点和管脚的线路,该线路使触点和管脚一一对应，但两边并非按字母顺序连接，每个型号的转子都有其固定的连接方式,第2章 古典密码技术,转轮机基本组成:,键盘 转子 显示器,转轮机组成示意图,第2章 古典密码技术,再按“a”,再按“a”,第2章 古典

29、密码技术,德国人的军用Enigma有3个转轮。转轮机中还有一个反射器，结构如下图所示意。,反射器有何作用？,第2章 古典密码技术,实际上键盘和第一个转子之间还有一块有块连接板！,键盘,第一个转子,实际对应26字母连接板上的交换线共有6根！,初始设置,ABBICE,AEBQCT,第2章 古典密码技术,问题：1.密钥是什么？ 转子的初始位置或状态； 三个转子之间的相互位置； 连接板的连线状况。2.密钥空间多大？ 三个转子不同位置或状态组成26262617576种可能性； 三个转子间不同的相对位置为6种（3!6）可能性； 若连接板上连接线数量为p（13），共有连接方式：,如，p=10时，N=1507

30、38274937250种可能性！ 密钥空间：1757661507382749372501.58961019如果再考虑每个转子内部连接线，可能性更多! “暴力破译法”？，难！,破解ENIGMA,波兰人在1934年，研究出了破译ENIGMA的方法。德国人在1938年底又对ENIGMA作了大幅度改进。1939年7月25日，波兰情报部门邀请英国和法国的情报部门共商合作破译ENIGMA。 1939年7月，英国情报部门在伦敦以北约80公里的一个叫布莱奇利的地方征用了一所庄园。一个月后，鲜为人知的英国政府密码学校迁移到此。不久，一批英国数学家也悄悄来到这所庄园，破译恩尼格玛密码的工作进入了冲刺阶段。在这里刚

31、开始时只有五百人，战争结束时已经增加到了七千人。 为了破译ENIGMA，英国人将国内最优秀的数学家悉数招进庄园。其中就有从剑桥来的图灵,正是他打破了ENIGMA不可战胜的神话。 虽然英国人成功的破译了ENIGMA，但是他们极好地隐藏了这一点，使得战争的进程大大加速 。,第2章 古典密码技术,ENIGMA实验,器材： ENIGMA 仿真机。电码本，德国空军电报员使用的密码本，部分信息如：,第2章 古典密码技术,所谓ringsetting是指在将转子放入Enigma机前对转子外环/字母环的设置，即将字母上的某个指定字母与转子上的一个固定标记对齐。,第2章 古典密码技术,2.4 古典密码的破解（统计

32、分析）,密码设计是利用数学来构造密码（密码编码学） 在对密码进行安全分析时，一般假设密码分析者知道密码体制，即Kerckhoffs假设，密码分析重点在获取密钥。 移位密码、仿射密码、维吉尼亚密码、置换密码等对己知明文攻击都是非常脆弱的。即使用惟密文攻击，大多数古典密码体制都容易被攻破。大多数古典密码体制都不能很好隐藏明文消息的统计特征。 语言的统计特性： 语言的频率特征 连接特征 重复特征 下面就针对单表替代密码、多表替代密码和Hill密码来介绍利用英文语言的统计特征和密码特点，运用惟密文攻击或已知明文攻击等方式破译古典密码的基本方法。,第2章 古典密码技术,2.4 古典密码的破解（续）,密码

33、分析除了依靠数学、工程背景、语言学知识外， 还要靠经验、统计、测试、眼力、直觉判断力 .有时还要靠点运气 密码破译的原则: 遵循观察与经验方法:采用归纳与演绎步骤:分析、假设、推测和证实,2.4.1 单表替代密码分析 对于单表替代密码，加法密码和乘法密码的密钥量比较小，可利用穷举密钥的方法进行破译。 仿射密码、多项式密码的密钥量也只有成百上千，古代密码分析者企图用穷举全部密钥的方法破译密码可能会有一定困难，然而计算机出现后这就很容易了。,第2章 古典密码技术,2.4 古典密码的破解（续）,2.4.1 单表替代密码分析 对于单表替代密码，加法密码和乘法密码的密钥量比较小，可利用穷举密钥的方法进行

34、破译。仿射密码、多项式密码的密钥量也只有成百上千，古代密码分析者企图用穷举全部密钥的方法破译密码可能会有一定困难，然而计算机出现后这就很容易了。 本质上，密文字母表是明文字母表的一种排列。但企图使用计算机穷举一切密钥来破译密钥词组替代密码也是计算不可行的。,第2章 古典密码技术,2.4.1 单表替代密码分析（续）,本质上，密文字母表是明文字母表的一种排列。但企图使用计算机穷举一切密钥来破译密钥词组替代密码也是计算不可行的。 穷举不是攻击密码的惟一方法，密码分析者便可利用语言的统计特性进行分析。如果明文语言的这种统计特性在明文中有所反映，密码分析者便可通过分析明文和密文的统计规律而破译密码。 通

35、过对大量英文语言的研究可以发现，每个字母出现的频率不一样，e出现的频率最高。如果所统计的文献足够长，便可发现各字母出现的频率比较稳定。 如表2.4所示（表中字母出现频率为字母出现次数除以文本字母总数）。,第2章 古典密码技术,表2.4 26个英文字母出现频率统计表,2.4.1 单表替代密码分析（续）,第2章 古典密码技术,（1）设x是一个长度任意的英文字母串，即x=x1x2x3xm，其中xi 是字母，m不确定。现在问：从x中随机地抽取两个字母，它们为相同字母的概率是多少？ 26 (1/26)2=1/26=0.0385（2）如果x是一篇随便选取的英语文章，令p1表示字母 a 出现的概率，p2表示

36、字母 b 出现的概率，p26表示字母 z 出现的概率。那么，抽到两个相同字母的概率就是 p12+p22+p262=0.0687 一个事实：对于单表代替密码加密得到的密文， 0.0687这个数据不变。,一个概率问题,第2章 古典密码技术,一般过程：假定，推翻，再假定，再推翻，直至破译。 对密文字母的频数、使用频率和连接次数进行统计； 根据了解到的密码编制人员的语言修养，以及手中掌握的密文的统计规律，多方比较，对明文的语种和密码种类作出假定； 将假定语种的字母频率与密文字母频率进行比较； 首先找出密文中频率最高的字母； 根据字母的频率特征、连接特征、重复特征，从最明显的单词或字母开始，试探进行；

37、总结,单表密码破译概要,第2章 古典密码技术,通过对26个英文字母出现频率的分析，可以有以下结果： （1）e出现的频率最大，约为0.13； （2）t，a，o，i，n，s，h，r出现频率约在0.060.1之间； （3）d，l出现的频率在0.04附近； （4）c，u，m，w，f，g，y，p，b出现的频率约在0.015 0.029之间； （5）v，k，j，x，q，z出现的频率小于0.01。 在密码分析中，除了考虑单字母统计特性外，掌握双字母、三字母的统计特性以及字母之间的连缀关系等信息也是很有用的。 出现频率最高的30个双字母组合依次是： thheineranreedonesstenattontha

38、,2.4.1 单表替代密码分析（续）,第2章 古典密码技术,ndoueangasortiisetitartesehiof 出现频率最高的20个三字母组合依次是：特别的，the出现的频率几乎是ing的3倍，这在密码分析中很有用。此外，统计资料还表明：英文单词以e，s，d，t字母结尾的超过一半。英文单词以t，a，s，w为起始字母的约占一半。以上这些统计数据是通过非专业性文献中的字母进行统计得到的。对于密码分析者来说，这些都是十分有用的信息。除此之外，密码分析者对明文相关知识的掌握对破译密码也是十分重要的。,2.4.1 单表替代密码分析（续）,theing and her ere enttha nt

39、h was eth for dth hat she ion int his sth ers ver,第2章 古典密码技术,字母和字母组的统计数据对于密码分析者是十分重要的。因为它们可以提供有关密钥的许多信息。对于字母e比其它字母的频率都高得多，如果是单表替代密码，可以预计大多数密文都将包含一个频率比其它字母都高的字母。当出现这种情况时，猜测这个字母所对应的明文字母为e，进一步比较密文和明文的各种统计数据及其分布，便可确定出密钥，从而破译单表替代密码。 下面通过一个具体实例来说明如何借助于英文语言的统计规律来破译单表替代密码。该例子取自参考文献1。【例2.9】设某一段明文经单表替代密码加密后的密

40、文如下： YIFQ FMZR WQFY VECF MDZP CVM R ZWNM DZVE JBTX CDDUMJ NDIF EFMD ZCDM QZKC EYFC JMYR NCWJ CSZR EXCH ZUNMXZ NZUC DRJX YYSM RTMEYIFZ WDYV ZVYF ZUMR ZCRW NZDZJJ XZWG CHSM RNMD HNCM FQCH ZJMX JZWI EJYU CFWD JNZDIR 试分析出对应密文。为了表述更加清楚，本例的密文用大写字母，明文用小写字母。,2.4.1 单表替代密码分析（续）,第2章 古典密码技术,解：将加密变换记为Ek，解密变换记为Dk

41、，密文中共有168个字母。 第一步：统计密文中各个字母的出现次数和频率，如表2.5所示。 表2.5 例2.9中各个密文字母的出现次数和频率,2.4.1 单表替代密码分析（续）,第2章 古典密码技术,第二步：从出现频率最高的几个字母及双字母组合、三字母组合开始，并假定它们是英语言中出现频率较高的字母及字母组合对应的密文，逐步推测各密文字母对应的明文字母。 从表2.5可以看出，密文字母Z出现的次数高于任何其他密文字母，出现频率约为0.12。因此，可以猜测： ，除Z外，出现至少10次的密文字母为C，D，F，J，M，R，Y，它们的出现频率约在0.060.095之间。因此，可以猜测密文字母C，D，F，J

42、，M，R，Y可能对应于明文字母集合t，a，o，i，n，s，h，r 中的字母，但不能肯定是哪一个。 因为已经假设密文Z解密成e，现在考虑密文中形如Z和Z的双字母的出现情况，Z的双字母情况如表2.6所示。,2.4.1 单表替代密码分析（续）,第2章 古典密码技术,表2.6 例2.9密文中包含字母Z的双字母出现次数 从表2.6可以发现，DZ和ZW出现4次；NZ和ZU出现3次；RZ，HZ，XZ，FZ，ZR，ZV，ZC，ZD和ZJ出现2次。 由于ZW出现4次而WZ一次也为出现，同时W出现的频率为0.048，故可猜测,2.4.1 单表替代密码分析（续）,第2章 古典密码技术,又因为DZ出现4次，ZD出现2

43、次，故可猜测 但具体是哪一个还不太清楚。 在 和 的假设前提下，继续观察密文会注意到密文开始部分出现的ZRW和RZW，并且在后面还出现了RW，因为R在密文中频繁出现，而nd是一个明文中常见的双字母组，因此可以猜测 到目前为止，已经得到了3个密文字母可能对应的明文字母，下面列出明文与密文的部分对应关系：,2.4.1 单表替代密码分析（续）,第2章 古典密码技术,2.4.1 单表替代密码分析（续）,第2章 古典密码技术,由于NZ是密文中出现较多的双字母组，而ZN不出现，所以可以猜测 。如果这个猜测是正确的，则根据明文片段nendhe又可以猜测 。结合这个假设，明文与密文的部分对应关系进一步又有：,

44、2.4.1 单表替代密码分析（续）,第2章 古典密码技术,现在再考虑出现次数排在第二的密文字母M，由前面分析，已密文段RNM对应的明文为nh，这说明h可能是一个明文单词的首字母，所以M可能代表明文中的一个元音字母。因为前面猜测已经使用了 和 所以猜测 。因为明文双字母ai比ao的出现次数更多，所以可以先猜测 ，这样明文与密文的部分对应关系进一步又有：,2.4.1 单表替代密码分析（续）,第2章 古典密码技术,2.4.1 单表替代密码分析（续）,第2章 古典密码技术,下面再来确定明文o对应的密文。因为o是一个常见的明文字母，所以可以猜测相应的密文字母是D、F、J、Y中的一个。Y的可能性最大，否则

45、由密文片段CFM或CJM将得到长串的元音字母aoi，这在英文中是不太可能的。因此，可以猜测 剩下密文字母中三个出现次数较高的字母是D、F、J，可以猜测它们 ，密文中三字母NMD出现了两次，故可猜测 ，这样，密文NMD对应的明文三字母组为his，这与前面假设 是一致的。 对于密文片段HNCMF，可猜测它对应的明文可能是chair，由此又有 ， 。这样，通过排除法有 。,2.4.1 单表替代密码分析（续）,第2章 古典密码技术,2.4.1 单表替代密码分析（续）,第2章 古典密码技术,第三步：利用与上述分析类似的方法，可以很容易地确定其余密文字母和明文字母的对应关系，最后，将得到的明文加上标点符号

46、，得到完整的明文如下： Our friend from Paris examined his empty glass with surprise，as if evaporation had taken place while he wasnt lookingI poured some more wine and he settled back in his chair, face tilted up towards the sun 以上讨论的是破解一般单表替代密码的统计分析方法，如果已知所用的密码体制（例如，对于位移密码、加法密码、乘法密码和仿射密码等），则相内的分析工作会更简单一些。,2.4

47、.1 单表替代密码分析（续）,第2章 古典密码技术,从该例子可以看出，破译单表替代密码的大致过程是： 首先，统计密文的各种统计特征，如果密文量比较多，则完成这步后便可确定出大部分密文字母； 然后，分析双字母、三字母密文组，以区分元音和辅音字母； 最后，分析字母较多的密文，在这一过程中大胆使用猜测的方法，如果猜对一个或几个词，就会大大加快破译过程。,2.4.1 单表替代密码分析（续）,第2章 古典密码技术,多表替代密码从一定程度上隐藏了明文消息的一些统计特征，破译相对较为困难；在多表替代密码的分析中，首先要确定密钥的长度，也就是要确定所使用的加密表的个数，然后再分析确定具体密钥；确定密钥长度的常

48、用方法两种，即Kasiski测试法（Kasiski test）和重合指数法（index of coincidence）。,2.4.2 多表替代密码分析,破译思路： 设法找出单密表数(关键词长度)，将多表替换单表替换，再破译单表替换密码。,弗吉尼亚密码示例,重要事实： 用给定的n个字母表周期性地对明文字母加密，则当两个相同的明文段在明文序列中间隔的字母数为n的整数倍时，将加密成相同的密文段。,第2章 古典密码技术,2.4.2 多表替代密码分析,设单密表数为9（如密钥为 deceptive）：明文序列： wearediscoveredsaveyourself 密钥序列： deceptivedece

49、ptivedeceptive 密文序列：ZICVTWQNGRZGVTWAVZHCQYGLMGJ （位置差正好是9 的倍数。）,【举例】,做一个宽度为9的矩阵如右图：,多表替代密码分析：例2.11（P35 ）,第2章 古典密码技术,考虑下面一个维吉尼亚密码的简单例子： 明文：requests additional test 密钥：TELEXTEL EXTELEXTEL EXTE 密文：CAVKTBLT EUQWSWJGEA LTBL 明文包含字母序列est两次，而这两次又碰巧被同样的密钥片段加密，因而对应的密文都是TBL。 事实：序列est位于密钥长度5（或周期）的整倍数处(15)。显然，相同字

50、母组的距离反映了密钥长度n的相关信息。 Kasiski的测试过程如下：搜索长度至少为2的相邻的一对对相同的密文段，记下它们之间的距离。而密钥长度n可能就是这些距离的最大公因子。,2.4.2 多表替代密码分析（续）,第2章 古典密码技术,2.4.2 多表替代密码分析（续）,表2.7 重复字母组及距离示例,第2章 古典密码技术,2. 重合指数法 如果考虑来自26个字母表的完全随机文本，则每个字母都以相同的概率1/26出现，假定另一个随机文本放在第一个的下面，在上下位置出现相同字母a的概率为 ，在两个随机文本的上下位置找到任意两个相同字母总的概率为 。但实际上，由于英文字母出现的概率是不同的（见表2