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

古典密码的统计分析现代密码学安徽工业大学单表古典密码的统计分析原理：明文的统计规律在密文中能够反映出来，故信息泄露大。多表古典密码的统计分析原理：密钥相同时，相同的明文对应相同的密文。现代密码学安徽工业大学现代密码学安徽工业大学明文的统计规律26个英文字母：e12%t---a---o---i---n---s---h---r6%--9%d---l4%c---u---m---w---f---g---y---p---b1.5%--2.8%v—k---j---x---q---z1%现代密码学安徽工业大学多表古典密码的统计分析步骤1：首先确定密钥的长度：利用Kasiski测试法和重合指数法(indexofcoincidence)步骤2：确定具体的密钥内容：交互重合指数法现代密码学安徽工业大学寻找密文中相同的片段对，计算每对相同密文片段对之间的距离，不妨记为d1,d2,…,di，若令密钥字的长度为m，则m=gcd(d1,d2,…,di)。定理1若两个相同的明文片段之间的距离是密钥长度的倍数，则这两个明文段对应的密文一定相同。反之则不然。若密文中出现两个相同的密文段(密文段的长度m2)，则它们对应的明文（及密钥）将以很大的概率相同。Kasiski测试法：Kasiski于1863年提出现代密码学安徽工业大学进一步判断密钥字的长度是否为m=gcd(d1,d2,…,di).定义1设X=x1x2…xn是一个长度为n的英文字母串，则x中任意选取两个字母相同的概率定义为重合指数，用表示。)(xIc重合指数法(indexofcoincidence)：Wolfefriendman于1920年提出现代密码学安徽工业大学定理1设英文字母A，B,…，Z在X中出现的次数分别为：f0,f1,…,f25则从X中任意选取两个字母相同的概率为证明在X中任意选取两个字母共有种选取的可能；在X中的每个相同的字母中选取两个元素共有种选取的可能。故易证。证毕。)1()1()(250nnffXIiiic2)1(2nnCn2)1(2iifffCi例子现代密码学安徽工业大学已知每个英文字母出现的期望概率，分别记为p0,p1,…,p25，那么X中两个元素相同的概率为：=0.0652502)(iicpXI现代密码学安徽工业大学对于英文的一个随机字母串，每个英文字母出现的期望概率均为1/26，则在X中任意选取两个元素相同的概率为=0.038.2250261icI现代密码学安徽工业大学根据Kasiski测试法得到的m，可以将密文Y按照下列形式排列：表1将Y排列成m行n/m列的形式，设m=0(modn)nmmmmnmmnmmnmyyykyyykyyykyyyk2333322221111现代密码学安徽工业大学若m确实是密钥的长度，则上述矩阵中的每一行都是由同一个密钥ki加密得到，这说明每一行即是一个单表代替，这时计算每一行的重合指数，应该更接近0.065；若m不是密钥的长度，则上述矩阵中的每一行不是由同一个密钥ki加密得到，这说明每一行是一个等概随机的字母串（对密文的要求），这时计算每一行的重合指数，应该更接近0.038。现代密码学安徽工业大学用交互重合指数确定密钥的具体内容定义设X=x1x2…xn和Y=y1y2…yn，是两个长度分别为n和n’的字母串。X和Y的交互重合指数(mutualindexofcoincidence)定义为X中的一个随机元素与Y中的一个随机元素相同的概率，记为),(YXMIc现代密码学安徽工业大学计算表1中的任意两行之间的交互重合指数中的一个随机元素与中的一个随机元素同为字母h(0=h26)的概率为则称为和之间的相对位移(relativeshift)，用表示。由于iYjY),(jicYYMI250hkhkhjipp250hkkhhijpp26mod)(jikkiYjY250hlhhpp250hlhhppl现代密码学安徽工业大学现代密码学安徽工业大学计算具体密钥内容当相对位移不为0时，重合指数的取值范围[0.031,0.045]当相对位移为0时，重合指数取值为0.065。可以统计每两行中英文字母出现的次数f0,f1,…,f25和f’0,f’1,…,f’25记为以g作密钥进行加法加密得到的密文，并穷举计算得到若，则应该接近0.065；若不然，应该接近[0.031,0.045]中的某个值。gjY),(gjicYYMIlg现代密码学安徽工业大学1161227233835510nmnmnmnkyyykyyykyyykyyyK1+i,i=0,……,25K1-k2=5现代密码学安徽工业大学计算具体密钥内容的复杂度分析这样可以得到任意两行之间的相对位移。给定某一行，猜测其密钥值(只有26种可能),其它行的密钥由相对位移唯一确定,这时用穷举法只有26种可能,可得到密钥值。现代密码学安徽工业大学1166286236276现代密码学安徽工业大学现代密码学安徽工业大学现代密码学安徽工业大学习题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）用维吉尼亚密码脱密得结果vahaegduoolctykyoonmuade再使用易位密码脱密得明文Mhaveagoodluckytoyouandme现代密码学安徽工业大学习题2解答：解：f1的逆为：m=15(c-5)mod26=(15c+3)mod26f2的逆为：T‘=（23154）则对C做f2的逆变换得：icfsxbfezi再做f1的逆变换得：thanksalot。