《第3讲--古典密码的统计分析》由会员分享,可在线阅读,更多相关《第3讲--古典密码的统计分析(25页珍藏版)》请在金锄头文库上搜索。
1、古典密码的统计分析,单表古典密码的统计分析 原理:明文的统计规律在密文中能够反映出 来,故信息泄露大。 多表古典密码的统计分析 原理:密钥相同时,相同的明文对应相同的 密文。,明文的统计规律,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%,多表古典密码的统计分析,步骤1:首先确定密钥的长度:利用Kasiski测试法和重合指数法(index of coincidence) 步骤2:确定具体的密钥内容:交互重合指数法,寻找密文中相同的片段对,计算每对相同密文片段对之间的距离,不妨
2、记为d1,d2,di,若令密钥字的长度为m,则m=gcd(d1,d2,di)。 定理1 若两个相同的明文片段之间的距离是密钥长度的倍数,则这两个明文段对应的密文一定相同。 反之则不然。 若密文中出现两个相同的密文段(密文段的长度m2),则它们对应的明文(及密钥)将以很大的概率相同。,Kasiski测试法:Kasiski于1863年提出,进一步判断密钥字的长度是否为 m=gcd(d1,d2,di). 定义1设X=x1x2xn是一个长度为n的英文字母串,则x中任意选取两个字母相同的概率定义为重合指数,用 表示。,重合指数法(index of coincidence):Wolfe friendman
3、于1920年提出,定理1设英文字母A,B,,Z在X中出现的次数分别为: f0,f1,f25 则从X中任意选取两个字母相同的概率为 证明在X中任意选取两个字母共有种 选取的可能;在X中的每个相同的字母中选取两个元素共有 种选取的可能。故易证。证毕。,例子,已知每个英文字母出现的期望概率,分别记为p0,p1,p25,那么X中两个元素相同的概率为: =0.065,对于英文的一个随机字母串,每个英文字母出现的期望概率均为1/26,则在X中任意选取两个元素相同的概率为 =0.038.,根据Kasiski测试法得到的m,可以将密文Y按照下列形式排列: 表1将Y排列成m行n/m列的形式,设m=0(modn)
4、,若m确实是密钥的长度,则上述矩阵中的每一行都是由同一个密钥ki加密得到,这说明每一行即是一个单表代替,这时计算每一行的重合指数,应该更接近0.065; 若m不是密钥的长度,则上述矩阵中的每一行不是由同一个密钥ki加密得到,这说明每一行是一个等概随机的字母串(对密文的要求),这时计算每一行的重合指数,应该更接近0.038。,用交互重合指数确定密钥的具体内容,定义设X=x1x2xn和Y=y1y2yn,是两个长度分别为n和n的字母串。X和Y的交互重合指数(mutual index of coincidence)定义为X中的一个随机元素与Y中的一个随机元素相同的概率,记为,计算表1中的任意两行之间的
5、交互重合指数,中的一个随机元素与 中的一个随机元素同为字母h(0=h26)的概率为 则 称为 和 之间的 相对位移(relative shift),用表示。 由于,计算具体密钥内容,当相对位移不为0时,重合指数的取值范围0.031,0.045 当相对位移为0时,重合指数取值为0.065。 可以统计每两行中英文字母出现的次数f0,f1,f25 和f0,f1,f25 记 为以 g 作密钥进行加法加密得到的密文, 并穷举计算得到 若 ,则应该接近0.065; 若不然,应该接近0.031,0.045中的某个值。,K1+i,i=0,25,K1-k2=5,计算具体密钥内容的复杂度分析,这样可以得到任意两行
6、之间的相对位移。 给定某一行,猜测其密钥值(只有26种可能),其它行的密钥由相对位移唯一确定,这时用穷举法只有26种可能,可得到密钥值。,1,166,286,236,276,习题,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解答:,解:f1的逆为: m=15(c-5)mod26=(15c+3)mod26 f2的逆为:T=(23154) 则对C做f2的逆变换得:icfsxbfezi 再做f1的逆变换得:thanksalot。,