密码学课件：四、古典密码体制的分析

1、古典密码的分析主要内容英文字母的频率特性仿射密码体制的唯密文攻击单表代换密码的统计分析多表代换密码的分析多表代换密码分析举例对Hill密码的已知明文分析古典密码体制：代换（替代）密码单表代换密码多表代换密码转轮密码机置换（换位）密码密码学(Cryptology)分为：密码编码学(Cryptography) 主要研究对信息进行编码，实现对信息的隐蔽。密码分析学(Cryptanalytics) 主要研究加密消息的破译或消息的伪造。密码史表明，密码分析者的成就似乎比密码设计者的成就更令人惊叹！许多在设计之初被认为是“千年不破”的密码体制，没过多久就被密码分析者巧妙地攻破。古典密码体制对已知明文攻击和

2、唯密文攻击非常脆弱。英文字母的频率特性英文字母的频率特性在对大量的英文文章、报纸、小说和杂志进行统计分析，Beker和Piper给出了26个英文字符出现频率的统计结果。（参考文献： cipher systems: the protection of communication）表1字符abcdefg频率0.0820.0150.0280.0430.1270.0220.020字符hijklmn频率0.0610.0700.0020.0080.0400.0240.067字符opqrstu频率0.0750.0190.0010.0600.0630.0910.028字符vwxyz频率0.0100.0230.

3、0010.0200.001英文字母的频率特性英文字母的频率特性将26个英文字符划分成5个部分：（1）字符e的概率大约为0.12（2）字符a,h,i,n,o,r,s,t的概率大约为0.060.09（3）字符d,l的概率大约为0.04（4）字符b,c,f,g,m,p,u,w,y的概率大约为0.0150.023（5）字符j,k,q,v,x,z的概率小于0.01不同类型的文献，如诗歌、小说、科技文献、新闻等的统计结果可能略有差别。英文字母的频率特性出现频率最高的30个双字母组合依次是：th he in er an re ed on es st en at to nt ha nd ou ea ng as

4、 or ti is et it ar te se hi of 出现频率最高的20个三字母组合依次是：the ing and her ere ent tha nth was eth fordth hat she ion int his sth ers ver特别地： the出现的频率几乎是ing的3倍 英文单词以e,s,d,t字母结尾的超过一半 英文单词以t,a,s,w为起始字母的约占一半仿射密码体制的唯密文攻击仿射密码体制的唯密文攻击定义：仿射密码体制令P=C=Z26，K=(k1,k2)Z26Z26：gcd(k1,26)=1。对任意的密钥key=(k1,k2)K，xP，yC，定义： Ekey(

5、x)=(k1x+k2) mod 26 Dkey(y)=k1-1(y-k2) mod 26k1-1表示k1在Z26中的乘法逆，即k1k1-1 =1 mod 26。根据数论中的相关结论，当且仅当gcd(k1,26)=1时，同余方程y(k1x+k2) mod 26有惟一解。仿射密码体制的唯密文攻击例：设明文为china，密钥k=(k1,k2)=(9,2)，用仿射密码加、解密。加密变换：Ek(x)=(k1x+k2) mod 26=(9m+2) mod 26解密变换：Dk(y)=k1-1 (y-k2) mod 26=3(y-2) mod 26明文消息china对应的数字依次为2,7,8,13,0，密文为

6、unwpc，加密过程如下：仿射密码体制的唯密文攻击假设攻击者Eve截获到的密文为：FMXVEDKAPHFERBNDKRXRSREFMORUDSDKDVSHVUFEDKAPRKDLYEVLRHHRH。英文字符的统计结果：表2：频率较大的英文字符依次是：R,D,E,H,K,S,F,V字符ABCDEFGHIJKLM频率2107540500522字符NOPQRSTUVWXYZ频率1120830240210根据表1和表2的结果对比： 可假设：密文R对应明文e，D,E,H,K,S,F,V中的元素与a,h,i,n,o,r,s,t中元素对应。（1）设密文R对应明文e，密文D对应明文t e,R,t,D在Z26中

7、的值分别为4,17,19,3。 表示成加密函数的形式：Ekey(4)=17，Ekey(19)=3。仿射密码体制中具体加密函数为： Ekey(x)=(k1x+k2) mod 26， gcd(k1,26)=1 。根据假设得到方程组：仿射密码体制的唯密文攻击解方程组，得到Z26上的唯一解 k1=6，k2=19。因gcd(k1,26)=21，说明得到的密钥不合法，因此R对应e，D对应t错误。（2）另设R对应e，E对应t，得Ekey(4)=17，Ekey(19)=4，解方程组得到的密钥不合法。（3）又设R对应e，H对应t ，得Ekey(4)=17，Ekey(19)=7 ，解方程组得到的密钥不合法。仿射密

8、码体制的唯密文攻击（4）再设R对应e，K对应t，得到Ekey(4)=17，Ekey(19)=10，方程组：解方程组，得到唯一解k1=3，k2=5。k1与26互素，密钥合法。对密钥验证其正确性： k1-1=3-1 mod 26=9因此， Dkey(y)=k1-1 (y-k2) mod 26=(9y-19) mod 26。解密密文得到：Algorithms are quite general definitions of arithmetic processes通过解密出的明文消息可理解，密钥正确。仿射密码体制的唯密文攻击单表代换密码的统计分析单表代换密码的统计分析假设截获到的密文为：单表代换密码

9、的统计分析第一步：统计密文中字母的次数和频率字母次数/频率字母次数/频率字母次数/频率A0 /0.000J11/0.065S3 /0.018B1 /0.006K1 /0.006T2 /0.012C15/0.089L0 /0.000U5 /0.030D13/0.077M16/0.095V5 /0.030E7 /0.042N9 /0.054W8 /0.048F11/0.065O0 /0.000X6 /0.036G1 /0.006P1 /0.006Y10/0.060H4 /0.024Q4 /0.024Z20/0.119I5 /0.030R10/0.060单表代换密码的统计分析第二步：分析出现频率最高

10、的字母、双字母、三字母组合。在明文英文中出现频率高的字母和字母组合，对应的密文和密文组合字母在密文中出现的频率也相应的要高。密文频率统计表中，字母Z出现的频率最高，约为0.12， 可假设Z 对应明文e，Dk(Z)=e除Z外，至少出现10次的密文字母为C,D,F,J,M,R,Y ，频率在0.060.095之间。根据明文英文字母频率统计表，猜测可能对应明文字母集合t,a,o,i,n,s,h,r中某一个。单表代换密码的统计分析分析双字母组合出现的频率情况：因已假设Z解密成e，故先考虑与Z结合的双字母组合：-Z（Z在后）出现次数Z-（Z在前）出现次数DZ4ZW4NZ3ZU3RZ2ZR2HZ2ZV2XZ

11、2ZC2FZ2ZD2ZJ2单表代换密码的统计分析在明文两字母组合的统计中（e-）组合为： er,ed,es,en,ea,et（-e）组合为： re, se, teZW（即e-）出现4次，WZ（-e）一次都未出现，则W可能是d,n,a中的一个，同时W出现的概率为0.048 ，而单字母d在明文统计中出现的概率也在0.04附近，猜测： Dk(W)=d单表代换密码的统计分析进一步分析，在明文两字母组合的统计中：（-e）组合为： he,re,te,se（e-）组合为： er,et,es又因为DZ（-e）出现4次，ZD（e- ）出现2次，故可猜测： Dk(D)r,t,s单表代换密码的统计分析在Dk(Z)=

12、e和Dk(W)=d的假设的前提下，继续观察密文发现密文开始部分出现ZRW(e-d)和RZW(-ed)，并且之后还出现RW(-d)。因R在密文中频繁出现，而nd是明文中常见组合，故可猜测： Dk(R)=n单表代换密码的统计分析根据：Ze，Wd，Rn，列出明文和密文的对应关系：单表代换密码的统计分析进一步分析，在明文两字母组合的统计中：（-e）组合为： he,re,te,se（e-）组合为： er,et,es由于NZ(-e)是密文中出现较多的双字母，而ZN(e-)不出现，所以可以猜测Dk(N)=h如果这个猜测正确，则根据第三行的明文片段ne?ndhe(RZCRWNZ)，再根据最初的猜测密文C,D,

13、F,J,M,R,Y 对应明文t,a,o,i,n,s,h,r，又可猜测Dk(C)=a单表代换密码的统计分析至此， 根据Ze，Wd，Rn，Nh，Ca进一步列出明文与密文的对应关系：单表代换密码的统计分析进一步考虑出现频率第二的密文字母M(频率为0.095)。密文中RNM对应的明文为nh-，说明h-可能是一个单词的首字母，故M可能代表元音字母。因已猜测Dk(C)=a和Dk(Z)=e，对照集合t,a,o,i,n,s,h,r，所以猜测Dk(M)i,o。因Dk(C)=a，又因明文双字母ai比ao的出现次数更多，所以可以先猜测Dk(M)=i。单表代换密码的统计分析至此，根据 Ze，Wd，Rn，Nh，Ca ，

14、Mi进一步列出明文与密文的对应关系：单表代换密码的统计分析进一步分析确定明文o对应的密文。因为o(出现频率为0.0797)是一个常见的明文字母，根据出现超过10次的密文字母C，D，F，J，M，R，YCa，DDk(D)r,s,t，Mi，Rn可猜测相应的密文字母是F,J,Y中的一个。Y的可能性最大，否则为F或J，则由密文CFM(o-i)或CJM(o-i)得到aoi串，这在英文中不存在，故猜测Dk(Y)=o。单表代换密码的统计分析进一步分析至此，Ze，Wd，Rn，Nh，Ca ，Mi ，Yo根据最初的猜测密文C,D,F,J,M,R,Y 对应明文t,a,o,i,n,s,h,r：剩下的三个字母D,F,J

15、对应t,s,r。密文NMD(hi-)出现两次，故猜测D对应s，即Dk(D)=s，这样密文NMD对应his，这与猜测Dk(D)r,s,t不矛盾。因此F,J 对应t,r。对于密文片段HNCMF(-hai-)，猜测对应的明文可能是chair，由此有Dk(H)=c，Dk(F)=r，最后得Dk(J)=t。单表代换密码的统计分析至此，根据Ze，Wd，Rn，Nh，Ca ，Mi ，Yo， Ds，Hc，Fr，Jt进一步列出明文与密文的对应关系：单表代换密码的统计分析第三步：利用类似的分析方法，容易确定其余的密文字母和明文字母的对应关系，最后得到完整的明文： Our friend from Paris exami

16、ned his empty glass with surprise, as if evaporation had taken place while he wasnt looking. I poured some more wine and he settled back in his chair, face tilted up towards the sun.这位巴黎的朋友检查了一下杯子，感到有些惊讶，好像杯里的东西一不留意就消失了。我往杯子里又倒了些酒，他坐回椅子上，抬头望着太阳。单表代换密码的统计分析破译单表代换密码的大致过程：首先，统计密文的各种统计特征，如果密文量比较多，则完成这步后

17、就可确定大部分密文字母；其次，分析双字母、三字母的密文组，以区分元音和辅音字母；最后，分析字母较多的密文，在这一过程中要大胆猜测，若能对应一个或几个词，则大大加快破译。多表代换密码的分析多表代换密码分析与单表代换密码相比，多表代换密码从一定程度上隐藏了明文的统计特征，破译相对困难。在多表代换密码的分析中，首先要确定密钥的长度（或周期），然后再分析确定具体的密钥。常用的确定密钥长度的两种方法：Kasiski测试法和重合指数法。多表代换密码分析公元16世纪晚期，法国外交官维吉尼亚（vigenere）提出维吉尼亚密码，使得对单表置换的频率分析法失效。1863年，普鲁士少校卡西斯基提出Kasiski法

18、，从密钥长度破解维吉尼亚加密体制。Kasiski测试基本思想：当用给定的n个字母周期性地对明文字母加密，通常情况下，相同的明文字母将对应不同的密文字母。但是，当两个相同的明文段在明文序列中间隔的字母数为n的整数倍时，将加密成相同的密文段。反过来，如果有两个相同的密文段，则对应的明文段有可能（可能性很大）相同。Kasiski测试将密文中相同的字母组找出来，并对其相同字母组的距离综合分析，找出距离的最大公因子，就有可能提取出密钥的长度n。例：维吉尼亚密码的简单例子明文：requests additional test明文：reque stsad ditio nalte st密钥：TELEX TEL

19、EX TELEX TELEX TE密文：CAVKTBLTEUQWSWJGEALTBL明文中包含字母序列est两次，而这两次又碰巧被同样的密钥片段加密，因而对应的密文都是TBL。因此有结论：est位于密钥周期的整数倍处。故有：相同字母组的距离反映了密钥长度n的有关信息。 TBL距离相隔为15，是n的3倍。Kasiski测试例如：对一段密文的字母组合的距离统计如表表中，出现重复字母组距离中最多的因子是3，所以密钥长度最有可能是3。Kasiski测试字母序列距离字母序列距离PQA150=2523ROPY81=34RET42=723DER57=193FRT10=25RUN117=1332测试过程如下：

20、搜索长度至少为2的相邻的一对对相同的密文段，记下它们之间的距离。而密钥长度n可能就是这些距离的最大公因子。Kasiski测试二战时期破译日军紫密的美军情报部门SIS （Signals Intelligence Service）的牵头人William Frederick Friedman （威廉.弗雷德里克.弗里德曼）在其专著The Index of Coincidence and its Applications in Cryptography中给出重合指数法。重合指数法思路：完全按照语法规则形成的英文文本中字母重复出现的频率与完全无意义的英文文本（如多表代换加密形成的密文）中字母重复出现的频

21、率显然存在差别。重合指数法重合指数定义：设X=x1x2xn是一个长度为n的英文字母串，从X中的随机取两个字母，这两个字母相同的概率称为重合指数，记为Ic(x)。显然，从X中任意选取两个字母共有Cn2种方法。假设26个字母A,B,Z在X中出现次数分别为f0,f1,f25，则 f0+f1+f25 =n。选取的两个字母同时为A,B,Z中的某个i的情形共有Cfi2种，0i25，因此，有：重合指数法字符abcdefg频率0.0820.0150.0280.0430.1270.0220.020字符hijklmn频率0.0610.0700.0020.0080.0400.0240.067字符opqrstu频率0

22、.0750.0190.0010.0600.0630.0910.028字符vwxyz频率0.0100.0230.0010.0200.001 英文出版资料的Ic(x)：对大量英文资料中各字母出现的频率进行统计，结果见表。将英文字母A,B,Z的期望概率分别记为p0,p1,p25。重合指数法 英文出版资料的Ic(x)：因此，从英文资料中随机取两个字母，这两个字母同时为第i个字母的概率为pipi，0i25，所以英文资料的重合指数为：重合指数法 字母完全随机出现的英文文本的Ic(x)如果考虑来自26个字母表的完全没有意义的随机文本，则每个字母都以相同的概率1/26出现。如果从中随机取两个字母，这两个字母同

23、时为同一个英文字母的概率为(1/26)2，所以完全随机文本的重合指数为：Ic(x)=26(1/26)2=0.0385重合指数法 单表代换密码的Ic(x)：如果X是由单表代换得到的密文，则显然各个密文字母的期望概率与各个明文字母的期望概率相同，因此，仍然有重合指数法 多表代换密码的Ic(x)：设Y=y1y2yn是由维吉尼亚密码体制得到的密文，将Y排列成 行m列的矩阵，各行仍然记为y1,y2,ym。如果m确实是密钥字的长度，则y1,y2,ym是单表代换密码得到的密文，因此仍然有：如果m不是密钥字的长度，则y1,y2,ym就是介于完全无意义的随机文本与单表代换密码得到的文本之间的文本，因此：0.03

24、85Ic(x)0.065由此，可求得密钥长度m。 重合指数法结论：（1）通过计算Ic(x)是否接近0.065可求得密钥字的长度m，即可得到加密周期。（2）另外，可用于分析两个密文是否用同样的方式加密。比如接收到两段密文文本C1、C2，若Ic1(x)Ic2(x)，则这两段密文极有可能加密方式相同。重合指数法在古典密码的分析中， Chi-测试：（1）可用来确定是否采用了相同或不同的代换（2）简化多表代换为单表代换-test(Chi-测试)定义：计算其中，pi表示符号i在第一个分布发生的概率； qi表示符号i在第二个分布发生的概率。当两个频率分布类似时， 的值相对较高。Chi-测试提供了对两个频率分

25、布进行比较的方式。-test(Chi-测试)例：假设收到两个密文C1、C2，它们都是移位密码体制的密文。设C1的替代表是通过原字母表移动k1个字母得到； C2的替代表是原字母表移动k2个字母得到。如果k1=k2，说明C1、C2是由相同位移替代密码加密，这时较大，因为C1的统计特性与C2类似。反之k1k2，值将要小一些。-test(Chi-测试)-测试可简化多表代换为单表代换。例：维吉尼亚密码，密钥、明文、密文如下：明文：execute these commands密钥：RADIO密文：VXHKI KEWPS JEFWA DAQLG-test(Chi-测试)例1：为了还原密文到明文，用下面的矩阵

26、表示：第一行为密钥；第一列R下的字母通过“减”R解密；第二列A下的字母通过“减”A解密；，可以看成：第一、二、三、四、五列分别是不同移位密码加密的结果。-test(Chi-测试)例1：考虑密钥中每个字母的相对距离如下：现在，把密文中第二列提前9个位置，第二列提前12个位置，这样，用密钥RADIO加密的密文，转换为只用R加密的密文。也就是，把多表代换密码的解密转换成单表代换密码的解密。-test(Chi-测试)例1：密码分析者可能没有密钥字母的相对距离的信息，Chi-测试提供了发现这个距离的线索。在例中，密文列被移位后，使得可用单表代换密码分析解密。如果两列是用同样单表代换加密的，则两列的值相同

27、，而且是最大值。分析者通过尝试距离值进行Chi-测试，直到得到这一列和第一列的最大值出现，然后就可用和第一列同样的方式解密。-test(Chi-测试)多表代换密码分析举例例2：在很短的时间内收到两段密文如下。密文C1：密文C2：例2：在很短的时间内收到两段密文如下。（1）判断C1和C2是否是采用同样的方式加密？根据公式：计算重合指数：Ic1(x)=0.0421，Ic2(x)=0.0445Ic1(x)和Ic2(x)相差很小，可假定C1和C2是用同样方式加密。例2：在很短的时间内收到两段密文如下。（2）采用Kasiski测试计算加密周期Ic1(x)=0.0421，Ic2(x)=0.0445因Ic1

28、(x)与Ic2(x)在（0.0385，0.065）之间，可猜测是采用多表代换密码体制加密。Kasiski测试：首先找到重复字母序列以及之间的距离；再进行因子分解，发现数字7出现最频繁，则周期可能是7。例2：在很短的时间内收到两段密文如下。（3）将密文写成7列的矩阵形式如下例2：在很短的时间内收到两段密文如下。（4）计算每一列的重合指数Ic(列1)=0.0522，Ic(列2)=0.0801，Ic(列3)=0.0734Ic(列4)=0.0744，Ic(列5)=0.0705，Ic(列6)=0.0717Ic(列7)=0.0606观察每一列的重合指数，每一列都是用一个单表代换密码加密。例2：在很短的时间

29、内收到两段密文如下。（5）将多表代换的密文转化为某个单表代换的密码重复移动各列字母，移动的距离分别是125，并分别计算相对于第一列的值，最大值用下划线标出。根据以上结果推知，相对于第1列的距离：列2:13,列3:22,列4:7例2：在很短的时间内收到两段密文如下。（5）将多表代换的密文转化为某个单表代换的密码重复移动各列字母，移动的距离分别是125，并分别计算相对于第一列的值，最大值用下划线标出。根据以上结果推知，相对于第1列的距离：列5:2,列6:9,列7:15例2：在很短的时间内收到两段密文如下。（6）转化成单表代换密码根据各距离值转化的结果如下：例2：在很短的时间内收到两段密文如下。（7）采用单表代换密码体制的破译方法进行分析具体过程作为课外作业。对Hill密码的已知明文分析对Hill密码的已知明文分析希尔密码。定义：Hill密码体制密钥K=Z26上的nn可逆矩阵，明文P与密文C均为n维向量，记为其中，C=KP mod 26，P=K-1C mod 26。K-1为K在模26上的逆矩阵，满足：KK-1=K-1K=I mod 26，I为单位矩阵。H