《第3讲古典密码的统计分ppt课件》由会员分享，可在线阅读，更多相关《第3讲古典密码的统计分ppt课件（26页珍藏版）》请在金锄头文库上搜索。
1、古典密码的统计分析古典密码的统计分析 王王 滨滨2005年年3月月4日日现代密码学现代密码学解放军信息工程大学电子技术学院解放军信息工程大学电子技术学院上次课内容回顾上次课内容回顾n n代替密码代替密码代替密码代替密码 单表代替密码的概念及安全性特点单表代替密码的概念及安全性特点单表代替密码的概念及安全性特点单表代替密码的概念及安全性特点 多表代替密码的概念及安全性特点多表代替密码的概念及安全性特点多表代替密码的概念及安全性特点多表代替密码的概念及安全性特点n n几个典型的古典密码体制几个典型的古典密码体制几个典型的古典密码体制几个典型的古典密码体制 卡撒密码卡撒密码卡撒密码卡撒密码 维及尼亚
2、密码维及尼亚密码维及尼亚密码维及尼亚密码 维福特密码维福特密码维福特密码维福特密码现代密码学现代密码学解放军信息工程大学电子技术学院解放军信息工程大学电子技术学院单表古典密码的统计分析单表古典密码的统计分析原理原理：明文的统计规律在密文中能够反映出：明文的统计规律在密文中能够反映出 来，故信息泄露大。来，故信息泄露大。多表古典密码的统计分析多表古典密码的统计分析原理原理：密钥相同时，相同的明文对应相同的：密钥相同时，相同的明文对应相同的 密文。密文。现代密码学现代密码学解放军信息工程大学电子技术学院解放军信息工程大学电子技术学院现代密码学现代密码学解放军信息工程大学电子技术学院解放军信息工程大
3、学电子技术学院明文的统计规律明文的统计规律2626个英文字母：个英文字母：个英文字母：个英文字母：e e 12% 12% t-a-o-i-n-s-h-rt-a-o-i-n-s-h-r6%-9% 6%-9% d-ld-l 4% 4% c-u-m-w-f-g-y-p-bc-u-m-w-f-g-y-p-b1.5%-2.8%1.5%-2.8%vvk-j-x-q-zk-j-x-q-z 1%2)，则它们对应的明文（及密钥）将以很大的概率相同。，则它们对应的明文（及密钥）将以很大的概率相同。Kasiski测试法：测试法：Kasiski于于1863年提出年提出现代密码学现代密码学解放军信息工程大学电子技术学院
4、解放军信息工程大学电子技术学院思考：以多大的概率成立？ 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是一个长度为n的英文字母串，则x中任意选取两个字母相同的概率定义为重合指数，用 表示。重合指数法重合指数
5、法重合指数法重合指数法(index of coincidence)(index of coincidence)：Wolfe Wolfe friendmanfriendman于于于于19201920年提出年提出年提出年提出现代密码学现代密码学解放军信息工程大学电子技术学院解放军信息工程大学电子技术学院定理1设英文字母A，B,，Z在X中出现的次数分别为：f0,f1,f25则从X中任意选取两个字母相同的概率为 证明在X中任意选取两个字母共有种 选取的可能；在X中的每个相同的字母中选取两个元素共有 种选取的可能。故易证。证毕。现代密码学现代密码学解放军信息工程大学电子技术学院解放军信息工程大学电子技术
6、学院已知每个英文字母出现的期望概率，分别记为已知每个英文字母出现的期望概率，分别记为p0,p1,p25，那么，那么X中两个元素相同的概率中两个元素相同的概率为：为： =0.065 现代密码学现代密码学解放军信息工程大学电子技术学院解放军信息工程大学电子技术学院对于英文的一个随机字母串，每个英文字对于英文的一个随机字母串，每个英文字母出现的期望概率均为母出现的期望概率均为1/26，则在，则在X中任中任意选取两个元素相同的概率为意选取两个元素相同的概率为=0.038.现代密码学现代密码学解放军信息工程大学电子技术学院解放军信息工程大学电子技术学院根据根据Kasiski测试法得到的测试法得到的m，可
7、以将密文，可以将密文Y按照下列形式排按照下列形式排列：列：表表1将将Y排列成排列成m行行n/m列的形式，设列的形式，设m=0(modn)现代密码学现代密码学解放军信息工程大学电子技术学院解放军信息工程大学电子技术学院 若若m确实是密钥的长度，则上述矩阵中的每一行确实是密钥的长度，则上述矩阵中的每一行都是由同一个密钥都是由同一个密钥ki加密得到，这说明每一行即是一加密得到，这说明每一行即是一个单表代替，这时计算每一行的重合指数，应该更接个单表代替，这时计算每一行的重合指数，应该更接近近0.065； 若若m不是密钥的长度，则上述矩阵中的每一行不不是密钥的长度，则上述矩阵中的每一行不是由同一个密钥是
8、由同一个密钥ki加密得到，这说明每一行是一个等加密得到，这说明每一行是一个等概随机的字母串（对密文的要求），这时计算每一行概随机的字母串（对密文的要求），这时计算每一行的重合指数，应该更接近的重合指数，应该更接近0.038。现代密码学现代密码学解放军信息工程大学电子技术学院解放军信息工程大学电子技术学院用交互重合指数确定密钥的具体内容定义定义设设X=x1x2xn和和Y=y1y2yn，是两个长度分别为，是两个长度分别为n和和n的字母串。的字母串。X和和Y的交互重合指数的交互重合指数(mutual index of coincidence)定义为定义为X中的一个随机元素与中的一个随机元素与Y中的一
9、中的一个随机元素相同的概率，记为个随机元素相同的概率，记为 现代密码学现代密码学解放军信息工程大学电子技术学院解放军信息工程大学电子技术学院计算表1中的任意两行之间的交互重合指数中的一个随机元素与 中的一个随机元素同为字母h(0=h26)的概率为则 称为 和 之间的相对位移(relative shift)，用表示。由于 现代密码学现代密码学解放军信息工程大学电子技术学院解放军信息工程大学电子技术学院计算具体密钥内容n当相对位移不为0时，重合指数的取值范围0.031,0.045n当相对位移为0时，重合指数取值为0.065。n可以统计每两行中英文字母出现的概率f0,f1,f25 和f0,f1,f2
10、5n记 为以 g 作密钥进行加法加密得到的密文，n并穷举计算得到 n若 ，则应该接近0.065；n若不然，应该接近0.031,0.045中的某个值。现代密码学现代密码学解放军信息工程大学电子技术学院解放军信息工程大学电子技术学院K1+i,i=0,25K1-k2=5现代密码学现代密码学解放军信息工程大学电子技术学院解放军信息工程大学电子技术学院计算具体密钥内容的复杂度分析 这样可以得到任意两行之间的相对位移。给定某一行，猜测其密钥值(只有26种可能),其它行的密钥由相对位移唯一确定,这时用穷举法只有26种可能,可得到密钥值。现代密码学现代密码学解放军信息工程大学电子技术学院解放军信息工程大学电子
11、技术学院习题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)m
12、od26现代密码学现代密码学解放军信息工程大学电子技术学院解放军信息工程大学电子技术学院习题1解答：解：加密密钥为置换T=（351246），则脱密密钥为置换T=（341526）用维吉尼亚密码脱密得结果 vahaeg duoolc tykyoo nmuade再使用易位密码脱密得明文M haveagoodluckytoyouandme现代密码学现代密码学解放军信息工程大学电子技术学院解放军信息工程大学电子技术学院习题2解答：解：f1的逆为：m=15(c-5)mod26=(15c+3)mod26f2的逆为：T=（23154）则对C做f2的逆变换得：icfsxbfezi再做f1的逆变换得：thanksalot。现代密码学现代密码学解放军信息工程大学电子技术学院解放军信息工程大学电子技术学院下节课讲授的主要内容Shannon理论理论n 密码体制的数学模型密码体制的数学模型n 熵及其性质熵及其性质
