古典密码统计分析

古典密码学统计分析 全面

古典密码的统计分析王 滨 2005年3月4日 年 月 日

古典密码学统计分析 全面

解放军信息工程大学电子技术学院

上次课内容回顾代替密码 单表代替密码的概念及安全性特点 多表代替密码的概念及安全性特点 几个典型的古典密码体制 卡撒密码 维及尼亚密码 维福特密码

现代密码学

古典密码学统计分析 全面

解放军信息工程大学电子技术学院

单表古典密码的统计分析 原理： 原理：明文的统计规律在密文中能够反映出 来，故信息泄露大。 故信息泄露大。 多表古典密码的统计分析 原理：密钥相同时， 原理：密钥相同时，相同的明文对应相同的 密文。 密文。 现代密码学

古典密码学统计分析 全面

解放军信息工程大学电子技术学院

现代密码学

古典密码学统计分析 全面

解放军信息工程大学电子技术学院

明文的统计规律26个英文字母： 26个英文字母 个英文字母： e t---a---o---i---n---s---h---r ---a---o---i---n---s---h---r d---l ---l c---u---m---w---f---g---y---p---b ---u---m---w---f---g---y---p---b v—k---j---x---q---z ---j---x---q---z 12% 6%--9% 6%--9% 4% 1.5%--2.8% 1.5%--2.8% <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:确定具体的密钥内容： 步骤 ：确定具体的密钥内容：交互重合指数法

现代密码学

古典密码学统计分析 全面

解放军信息工程大学电子技术学院Kasiski测试法：Kasiski于1863年提出 测试法： 测试法 于 年提出 寻找密文中相同的片段对， 寻找密文中相同的片段对，计算每对相同密文片段对 之间的距离，不妨记为d1,d2,…,di,若令密钥字的长度为 之间的距离，不妨记为 m,则m=gcd(d1,d2,…,di)。 , 。 定理1 若两个相同的明文片段之间的距离是密钥长度 定理 的倍数，则这两个明文段对应的密文一定相

同。 的倍数，则这两个明文段对应的密文一定相同。 反之则不然。 反之则不然。 若密文中出现两个相同的密文段(密文段的长度 若密文中出现两个相同的密文段 密文段的长度m>2), 密文段的长度 ， 则它们对应的明文(及密钥)将以很大的概率相同。 则它们对应的明文(及密钥)将以很大的概率相同。

现代密码学

古典密码学统计分析 全面

解放军信息工程大学电子技术学院

思考：以多大的概率成立？P(X1=X2|Y1=Y2) =1-P(X1!=X2;K1!=K2|Y1=Y2) 由于密钥是等概独立的，每个密钥出现的概率为 1/26,这相当于求满足 1/26 X1+K1=X2+K2(mod26) 的K1和K2出现的概率。若K1和K2中均有m个字母， 且m>=3,则 3 P(X1=X2|Y1=Y2) ≥ 1 1 ≥ 0.999999 26

现代密码学

古典密码学统计分析 全面

解放军信息工程大学电子技术学院 重合指数法(index 重合指数法(index of coincidence):Wolfe coincidence): friendman于1920年提出 friendman于1920年提出 进一步判断密钥字的长度是否为 m=gcd(d1,d2,…,di). 定义1 设X=x1x2…xn是一个长度为n的英文字母 串，则x中任意选取两个字母相同的概率定义为重合指 数，用 I c (x) 表示。

现代密码学

古典密码学统计分析 全面

解放军信息工程大学电子技术学院定理1 设英文字母A,B,…,Z在X中出现的次数分别为： f0,f1,…,f25 则从X中任意选取两个字母相同的概率为Ic (X ) =25

∑ f (fi =0 i

i

1)

n(n 1)

证明

在X中任意选取两个字母共有种 种选取的可能。故易证。证毕。n (n 1) 2

选取

2 的可能；在X中的每个相同的字母中选取两个元素共有 Cn =

f i ( f i 1) C = 22 fi

现代密码学

古典密码学统计分析 全面

解放军信息工程大学电子技术学院

已知每个英文字母出现的期望概率，分别记为 已知每个英文字母出现的期望概率， p0,p1,…,p25,那么X中两个元素相同的概率 ，那么 中两个元素相同的概率 为：I c ( X ) ≈ ∑ pi2i =0 25

=0.065

现代密码学

古典密码学统计分析 全面

解放军信息工程大学电子技术学院

对于英文的一个随机字母串， 对于英文的一个随机字母串，每个英文字 母出现的期望概率均为1/26,则在X中任 ，则在 中任 母出现的期望概率均为 意选取两个元素相同的概率为 1 Ic ≈ ∑ i =0 26 25 2

=0.038.

现代密码学

古典密码学统计分析 全面

解放军信息工程大学电子技术学院

根据Kasiski测试法得到的 ，可以将密文 按照下列形式排 测试法得到的m,可以将密文Y按照下列形式排 根据 测试法得到的 列： 排列成m行 列的形式， 表1 将Y排列成 行n/m列的形式，设m=0(modn) 排列成 列的形式k1 k2 k3 M km y1 y2 y3 M ym ym+1 y m+ 2 y m +3 M y 2m L L L M L ynm+1 y n m+ 2 y n m +3 M yn

现代密码学

古典密码学统计分析 全面

解放军信息工程大学电子技术学院

确实是密钥的长度， 若m确实是密钥的长度，则上述矩阵中的每一行 确实是密钥的长度 都是由同一个密钥k 加密得到， 都是由同

一个密钥 i加密得到，这说明每一行即是一 个单表代替，这时计算每一行的重合指数，应该更接 个单表代替，这时计算每一行的重合指数， 近0.065; ; 不是密钥的长度， 若m不是密钥的长度，则上述矩阵中的每一行不 不是密钥的长度 是由同一个密钥ki加密得到， 是由同一个密钥 加密得到，这说明每一行是一个等 加密得到 概随机的字母串(对密文的要求),这时计算每一行 概随机的字母串(对密文的要求),这时计算每一行 ), 的重合指数，应该更接近 的重合指数，应该更接近0.038。 。

现代密码学