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

古典密码的统计分析 王滨2005年3月4日 上次课内容回顾 代替密码单表代替密码的概念及安全性特点多表代替密码的概念及安全性特点几个典型的古典密码体制卡撒密码维及尼亚密码维福特密码 单表古典密码的统计分析原理 明文的统计规律在密文中能够反映出来 故信息泄露大 多表古典密码的统计分析原理 密钥相同时 相同的明文对应相同的密文 明文的统计规律 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 z 1 汉字中单音节出现频率 最常用 出现频率在百分之一以上的有14个音节 它们是 deshiyibuyouzhilejizhewoyenlitadao的是一不有之了机这我们里他到次常用音节有33个 它们是 zhongziguoshanggemenheweiyedagongjianjiuxiangzhulaishengdizainixiaokeyaowuyujiejinchanzuojiaxianquanshuo 从三亿汉字的母体材料中 抽样二千五百万字进行双音节词词频统计 结果是 频率在一万次以上的双音节词有33个 我们三万次以上可以他们二万次以上进行没有工作人民生产这个发展就是问题国家中国这样革命自己不能由于这些所以因此作用一般什么如果情况必须方法因为主要要求社会 汉字中双音节词出现频率 多表古典密码的统计分析 步骤1 首先确定密钥的长度 利用Kasiski测试法和重合指数法 indexofcoincidence 步骤2 确定具体的密钥内容 交互重合指数法 寻找密文中相同的片段对 计算每对相同密文片段对之间的距离 不妨记为d1 d2 di 若令密钥字的长度为m 则m gcd d1 d2 di 定理1若两个相同的明文片段之间的距离是密钥长度的倍数 则这两个明文段对应的密文一定相同 反之则不然 若密文中出现两个相同的密文段 密文段的长度m 2 则它们对应的明文 及密钥 将以很大的概率相同 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中任意选取两个字母相同的概率定义为重合指数 用表示 重合指数法 indexofcoincidence Wolfefriendman于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确实是密钥的长度 则上述矩阵中的每一行都是由同一个密钥ki加密得到 这说明每一行即是一个单表代替 这时计算每一行的重合指数 应该更接近0 065 若m不是密钥的长度 则上述矩阵中的每一行不是由同一个密钥ki加密得到 这说明每一行是一个等概随机的字母串 对密文的要求 这时计算每一行的重合指数 应该更接近0 038 用交互重合指数确定密钥的具体内容 定义设X x1x2 xn和Y y1y2 yn 是两个长度分别为n和n 的字母串 X和Y的交互重合指数 mutualindexofcoincidence 定义为X中的一个随机元素与Y中的一个随机元素相同的概率 记为 计算表1中的任意两行之间的交互重合指数 中的一个随机元素与中的一个随机元素同为字母h 0 h 26 的概率为则称为和之间的相对位移 relativeshift 用表示 由于 计算具体密钥内容 当相对位移不为0时 重合指数的取值范围 0 031 0 045 当相对位移为0时 重合指数取值为0 065 可以统计每两行中英文字母出现的概率f0 f1 f25和f 0 f 1 f 25记为以g作密钥进行加法加密得到的密文 并穷举计算得到若 则应该接近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 用维吉尼亚密码脱密得结果vahaegduoolctykyoonmuade再使用易位密码脱密得明文Mhaveagoodluckytoyouandme 习题2