古典密码的统计分析课件.pptVIP

* 在明文中如果两个明文片断所对应的的明文片断之间的距离d时密钥字长度m的倍数，则这两个明文片断所对应的密文片断也一定相等。 古典密码的统计分析 单表古典密码的统计分析 原理：明文的统计规律在密文中能够反映出 来，故信息泄露大。 多表古典密码的统计分析 原理：密钥相同时，相同的明文对应相同的 密文。 明文的统计规律 26个英文字母： e 　　　　　　　　　　　　　　　　　12% t---a---o---i---n---s---h---r　　　　　　6%--9% d---l　　　　　　　　　　　　　　　 　4% c---u---m---w---f---g---y---p---b　　1.5%--2.8% v—k---j---x---q---z　　　　 　　　　　　1% 汉字中单音节出现频率 最常用，出现频率在百分之一以上的有14个音节，它们是： 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个： 我们　　　　　　　　　　　　　　　　　三万次以上 可以 他们　　　　　　　　　　　　　　 二万次以上　 进行 没有 工作 人民 生产 这个 发展 就是 问题 国家 中国 这样 革命 自己 不能 由于 这些 所以 因此 作用 一般 什么 如果 情况 必须 方法 因为 主要 要求 社会 汉字中双音节词出现频率 　　多表古典密码的统计分析 步骤1：首先确定密钥的长度：利用Kasiski测试法和重合指数法(index of coincidence) 步骤2：确定具体的密钥内容：交互重合指数法 寻找密文中相同的片段对，计算每对相同密文片段对之间的距离，不妨记为d1,d2,…,di，若令密钥字的长度为m，则m=gcd(d1,d2,…,di)。 定理1 若两个相同的明文片段之间的距离是密钥长度的倍数，则这两个明文段对应的密文一定相同。 反之则不然。 若密文中出现两个相同的密文段(密文段的长度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=x1x2…xn是一个长度为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中任意选取两个元素相同的概率为 =0.038. 根据Kasiski测试法得到的m，可以将密文Y按照下列形式排列： 表1　将Y排列成m行n/m列的形式，设m=0(modn) 若m