第3讲--古典密码的统计分.ppt

1、古典密码的统计分析,王 滨 2005年3月4日,上次课内容回顾,代替密码 单表代替密码的概念及安全性特点 多表代替密码的概念及安全性特点 几个典型的古典密码体制 卡撒密码 维及尼亚密码 维福特密码,单表古典密码的统计分析 原理：明文的统计规律在密文中能够反映出 来，故信息泄露大。 多表古典密码的统计分析 原理：密钥相同时，相同的明文对应相同的 密文。,明文的统计规律,26个英文字母： e 12% t-a-o-i-n-s-h-r6%-9% d-l 4% c-u-m-w-f-g-y-p-b1.5%-2.8% vk-j-x-q-z 1%,汉字中单音节出现频率,最常用，出现频率在百分之一以上的有14个

2、音节，它们是： de shi yi bu you zhi le ji zhe wo yen li ta dao 的是 一 不有之 了机 这我们 里 他 到 次常用音节有33个，它们是： zhong zi guo shang ge men he wei ye da gong jian jiu xiang zhu lai sheng di zai ni xiao ke yao wu yu jie jin chan zuo jia xian quan shuo,从三亿汉字的母体材料中，抽样二千五百万字进行双音节词词频统计，结果是： 频率在一万次以上的双音节词有33个： 我们三万次以上 可以 他们 二

3、万次以上 进行 没有 工作 人民 生产 这个 发展 就是 问题 国家 中国 这样 革命 自己 不能 由于 这些 所以 因此 作用 一般 什么 如果 情况 必须 方法 因为 主要 要求 社会,汉字中双音节词出现频率,多表古典密码的统计分析,步骤1：首先确定密钥的长度：利用Kasiski测试法和重合指数法(index of coincidence) 步骤2：确定具体的密钥内容：交互重合指数法,寻找密文中相同的片段对，计算每对相同密文片段对之间的距离，不妨记为d1,d2,di，若令密钥字的长度为m，则m=gcd(d1,d2,di)。 定理1 若两个相同的明文片段之间的距离是密钥长度的倍数，则这两个明

4、文段对应的密文一定相同。 反之则不然。 若密文中出现两个相同的密文段(密文段的长度m2)，则它们对应的明文（及密钥）将以很大的概率相同。,Kasiski测试法：Kasiski于1863年提出,思考：以多大的概率成立？,P(X1=X2|Y1=Y2) =1-P(X1!=X2;K1!=K2|Y1=Y2) 由于密钥是等概独立的，每个密钥出现的概率为 1/26，这相当于求满足 X1+K1=X2+K2(mod26) 的K1和K2出现的概率。若K1和K2中均有m个字母，且m=3，则 P(X1=X2|Y1=Y2),进一步判断密钥字的长度是否为 m=gcd(d1,d2,di). 定义1设X=x1x2xn是一个长

5、度为n的英文字母串，则x中任意选取两个字母相同的概率定义为重合指数，用 表示。,重合指数法(index of coincidence)：Wolfe friendman于1920年提出,定理1设英文字母A，B,，Z在X中出现的次数分别为： f0,f1,f25 则从X中任意选取两个字母相同的概率为 证明在X中任意选取两个字母共有种 选取的可能；在X中的每个相同的字母中选取两个元素共有 种选取的可能。故易证。证毕。,已知每个英文字母出现的期望概率，分别记为p0,p1,p25，那么X中两个元素相同的概率为： =0.065,对于英文的一个随机字母串，每个英文字母出现的期望概率均为1/26，则在X中任意选

6、取两个元素相同的概率为 =0.038.,根据Kasiski测试法得到的m，可以将密文Y按照下列形式排列： 表1将Y排列成m行n/m列的形式，设m=0(modn),若m确实是密钥的长度，则上述矩阵中的每一行都是由同一个密钥ki加密得到，这说明每一行即是一个单表代替，这时计算每一行的重合指数，应该更接近0.065； 若m不是密钥的长度，则上述矩阵中的每一行不是由同一个密钥ki加密得到，这说明每一行是一个等概随机的字母串（对密文的要求），这时计算每一行的重合指数，应该更接近0.038。,用交互重合指数确定密钥的具体内容,定义设X=x1x2xn和Y=y1y2yn，是两个长度分别为n和n的字母串。X和Y

7、的交互重合指数(mutual index of coincidence)定义为X中的一个随机元素与Y中的一个随机元素相同的概率，记为,计算表1中的任意两行之间的交互重合指数,中的一个随机元素与 中的一个随机元素同为字母h(0=h26)的概率为 则 称为 和 之间的 相对位移(relative shift)，用表示。 由于,计算具体密钥内容,当相对位移不为0时，重合指数的取值范围0.031,0.045 当相对位移为0时，重合指数取值为0.065。 可以统计每两行中英文字母出现的概率f0,f1,f25 和f0,f1,f25 记 为以 g 作密钥进行加法加密得到的密文， 并穷举计算得到 若 ，则应该

8、接近0.065； 若不然，应该接近0.031,0.045中的某个值。,K1+i,i=0,25,K1-k2=5,计算具体密钥内容的复杂度分析,这样可以得到任意两行之间的相对位移。 给定某一行，猜测其密钥值(只有26种可能),其它行的密钥由相对位移唯一确定,这时用穷举法只有26种可能,可得到密钥值。,习题,1、已知某密码的加密方法为：先用易位密码对明文M加密，再对该结果用维吉尼亚密码加密得密文C。若易位密码使用的加密密钥为置换T=（351246），维吉尼亚密码使用的加密密钥为AEF，密文 C=vemaildytophtcmystnqzahj， 求明文M。,习题,2、已知某密码的加密方法为：C=f2(f1(M) 其中变换f1为：c=(7m+5)mod26； 变换f2为置换T=（31254）， 今收到一份用这种密码加密的密文C=ficxsebfiz，求对应的明文M。 f1的逆为： m=15(c-5)mod26=(15c+3)mod26,习题1解答：,解：加密密钥为置换T=（351246），则脱密密钥为置换T=（341526） 用维吉尼亚密码脱密得结果 vahaeg duoolc tykyoo nmuade 再使用易位密码脱密得明文M haveagoodluckytoyouandme,习题2