《对称密码学及其应用分组密码的统计测试原理与攻击方法》由会员分享，可在线阅读，更多相关《对称密码学及其应用分组密码的统计测试原理与攻击方法（43页珍藏版）》请在金锄头文库上搜索。
1、北邮信息安全中心 北邮计算机学院 对称密码学及其应用对称密码学及其应用 1 计算机学院 李晖 对称密码学及其应用对称密码学及其应用 第五章第五章 分组密码的统计测试分组密码的统计测试 原理与攻击方法原理与攻击方法 北京邮电大学 北邮信息安全中心 北邮计算机学院 对称密码学及其应用对称密码学及其应用 2 课程目标课程目标 掌握基本的分组密码统计测试方法掌握基本的分组密码统计测试方法 掌握基本的分组密码攻击方法的原理掌握基本的分组密码攻击方法的原理 了解分组密码的线性密码分析的基本思了解分组密码的线性密码分析的基本思 想想 北邮信息安全中心 北邮计算机学院 对称密码学及其应用对称密码学及其应用
2、3 主要内容主要内容 分组密码的统计测试原理分组密码的统计测试原理 分组密码的典型攻击方法分组密码的典型攻击方法 北邮信息安全中心 北邮计算机学院 对称密码学及其应用对称密码学及其应用 4 5.1 分组密码的统计测试原理分组密码的统计测试原理 对分组密码进行统计测试的目的是：断对分组密码进行统计测试的目的是：断 定算法产生的输出是否在统计上难以与定算法产生的输出是否在统计上难以与 真随机数据区别开来。真随机数据区别开来。 按照测试目的分为：按照测试目的分为： 数据变换的有效性测试原理数据变换的有效性测试原理 算法对明文的扩散性测试原理算法对明文的扩散性测试原理 密钥更换的有效性检测原理密钥更换
3、的有效性检测原理 北邮信息安全中心 北邮计算机学院 对称密码学及其应用对称密码学及其应用 5 数据变换的有效性测试原理 随机性测试随机性测试 对用户给定的由若干密文分组组成的样本数对用户给定的由若干密文分组组成的样本数 据文件进行测试据文件进行测试 频数检验：测试密文的频数检验：测试密文的“0”、“1”平衡性平衡性 跟随性检验：测试分组中相邻比特的出现情跟随性检验：测试分组中相邻比特的出现情 况。况。 明密文独立性测试明密文独立性测试 主要是测试密文是否有不依赖于明文统计特主要是测试密文是否有不依赖于明文统计特 性的性质。性的性质。 北邮信息安全中心 北邮计算机学院 对称密码学及其应用对称密码
4、学及其应用 6 频数检验（频数检验（1） 若输出的密文分组是随机的，则首先应该有较好若输出的密文分组是随机的，则首先应该有较好 的“的“0”、“、“l”平衡性。平衡性。 设待测算法的分组长度为设待测算法的分组长度为n比特，有比特，有F个待测密文个待测密文 分组，统计这分组，统计这F个分组中汉明重量为个分组中汉明重量为i 的分组个数，的分组个数， 记为记为Fi 。 Fi应符合应符合二项分布二项分布B(n，12)。 检测方法：检测方法： 与其期望数与其期望数 进行进行拟合拟合 检验检验，将计算结果与自由度为，将计算结果与自由度为n，显著性水平，显著性水平 为为5的的 阈值相比较，来判断是否符合二阈
5、值相比较，来判断是否符合二 项分布项分布B(n，12)。 /2in inECF22北邮信息安全中心 北邮计算机学院 对称密码学及其应用对称密码学及其应用 7 补充：补充：二项分布（二项分布（1） 任意一次试验中，只有事件任意一次试验中，只有事件A发生和不发发生和不发 生两种结果，概率分别是：生两种结果，概率分别是：p和和1-p。若在。若在 相同的条件下，进行相同的条件下，进行n次独立重复试验，次独立重复试验， 设这设这n次试验中次试验中A发生的次数为发生的次数为X，那么在，那么在 n次独立重复试验中，事件次独立重复试验中，事件A恰好发生恰好发生k次次 的概率为的概率为Pn (X=k)=Cnk
6、p k (1- p) n-k (k=0,1,2,n),则称随机变量则称随机变量X服从二项分服从二项分 布。布。 kkn k knpPkC p q北邮信息安全中心 北邮计算机学院 对称密码学及其应用对称密码学及其应用 8 补充：补充：二项分布（二项分布（2） 例：例：如果假设分组长度为如果假设分组长度为4，即，可能分组，即，可能分组 为为0000，0001，1111，共，共16个。个。 分组的汉明重量为分组的汉明重量为0，1，2，3，4；有；有F个待个待 测分组，测分组，则则Fi应该符合二项分布应该符合二项分布。表示：。表示： P(F0)=C04(1/2)0(1/2)4=1/16 P(F1)=C
7、14(1/2)1(1/2)3=4/16=1/4 P(F2)=C24(1/2)2(1/2)2=6/16=3/8 P(F3)=C34(1/2)3(1/2)1=4/16=1/4 P(F4)=C44(1/2)4(1/2)0=1/16 kkn k knpPkC p q北邮信息安全中心 北邮计算机学院 对称密码学及其应用对称密码学及其应用 9 假设检验是统计学中依据一定假设条件，由样本推断总体的一假设检验是统计学中依据一定假设条件，由样本推断总体的一 种方法种方法 假设检验问题：给定假设假设检验问题：给定假设H0，如何利用样本来判断是接受假设，如何利用样本来判断是接受假设 H0，还是拒绝假设，还是拒绝假设
8、H0 假设检验的基本原理：假设检验的基本原理： 小概率事件在一次试验中几乎不可能发生小概率事件在一次试验中几乎不可能发生 依据这一原理，对一个假设检验问题，构造一个事件依据这一原理，对一个假设检验问题，构造一个事件A，使得，使得 在在H0为真的条件下，它发生的概率很小，而为真的条件下，它发生的概率很小，而H0不为真时，不为真时，A发发 生的概率显著变大。然后根据样本观察值来判断这个小概率事生的概率显著变大。然后根据样本观察值来判断这个小概率事 件是否发生了，如果已经发生了，就拒绝件是否发生了，如果已经发生了，就拒绝H0 ；如果没有发生，；如果没有发生， 就接受就接受H0 。 所谓小概率事件是指
9、其概率不超过事先给定的一个小正数所谓小概率事件是指其概率不超过事先给定的一个小正数的的 事件，通常取事件，通常取0.1、0.05和和0.01等较小的数，称为等较小的数，称为显著性水平。显著性水平。 补充：补充：假设检验（假设检验（1） 北邮信息安全中心 北邮计算机学院 对称密码学及其应用对称密码学及其应用 10 补充：拟合检验补充：拟合检验 如何判断一个总体如何判断一个总体X的分布函数是某个给的分布函数是某个给 定的函数定的函数F0(x)呢？呢？ 可以根据客观事物的性质，利用概率论的知可以根据客观事物的性质，利用概率论的知 识进行理论分析来得到所研究的总体分布识进行理论分析来得到所研究的总体分
10、布 从大量的样本数据中推断总体的分布形式。从大量的样本数据中推断总体的分布形式。 这实质是利用样本提供的信息检验假设：这实质是利用样本提供的信息检验假设： 是否成立的假设检验问题。是否成立的假设检验问题。 对假设对假设H0的检验成为拟合检验。的检验成为拟合检验。 )()( :00xFxFXH的分布函数为总体北邮信息安全中心 北邮计算机学院 对称密码学及其应用对称密码学及其应用 11 皮尔逊皮尔逊 检验检验 设总体设总体X是一个离散型随机变量，它的可是一个离散型随机变量，它的可 能取值为能取值为x1，x2，xl，为了检验假设，为了检验假设 ： 抽取容量为抽取容量为n的样本得到的样本得到n个样本数
11、据，个样本数据， 将样本数据按不同的取值进行分组整理，将样本数据按不同的取值进行分组整理， 列成下表所示的频数分布表。列成下表所示的频数分布表。 2lipxXHii.,21 P :0， ix1x2x3xixin1n2n3nin北邮信息安全中心 北邮计算机学院 对称密码学及其应用对称密码学及其应用 12 n个样本数据的频数分布表个样本数据的频数分布表 若若H0为真，为真，X的概率分布表的概率分布表 皮尔逊皮尔逊 检验检验 2北邮信息安全中心 北邮计算机学院 对称密码学及其应用对称密码学及其应用 13 当当n充分大时，事件充分大时，事件 X=xi发生的频率发生的频率ni/n 与理论概率与理论概率
12、pi的差应该很小。于是可以构成的差应该很小。于是可以构成 反映这一差异的一个统计量：反映这一差异的一个统计量： 其中其中kl，称为实际分组数。，称为实际分组数。 这个统计量是实测频数这个统计量是实测频数 ni与理论频数与理论频数 n pi差平方差平方 的加权和。的加权和。 它反映了样本实测频数它反映了样本实测频数ni 与理论频数与理论频数n pi 之间差之间差 异的大小，称这个统计量为皮尔逊异的大小，称这个统计量为皮尔逊 统计量。统计量。 皮尔逊皮尔逊 检验检验 22北邮信息安全中心 北邮计算机学院 对称密码学及其应用对称密码学及其应用 14 当当 H0为真时，为真时， 统计量的值应该小。所统
13、计量的值应该小。所 以皮尔逊统计量的值达到超过某个界限以皮尔逊统计量的值达到超过某个界限 时，就怀疑时，就怀疑 H0的正确性而拒绝的正确性而拒绝 。因此假。因此假 设设H0 的拒绝域为：的拒绝域为： 。的确定依赖的确定依赖 于皮尔逊于皮尔逊 统计量的分布，而统计量的分布，而 的精确的精确 分布难以求得，皮尔逊给出了它的近似分布难以求得，皮尔逊给出了它的近似 分布。分布。 2222皮尔逊皮尔逊 检验检验 2北邮信息安全中心 北邮计算机学院 对称密码学及其应用对称密码学及其应用 15 皮尔逊定理皮尔逊定理 kiiikiiiinnpfpnf pnH12 212 20 或或的统计量为的统计量为设检验假
14、设设检验假设定理定理 . , 1 ),( 50),( 200的个数的个数是被估计的参数是被估计的参数其中其中分布分布的的从自由度为从自由度为上统计量总是近似地服上统计量总是近似地服分布分布中的分布属什么中的分布属什么不论不论为真时为真时则当则当充分大充分大若若rrkHHn , ,0下下如果在假设如果在假设于是于是H),1()(212 2 rknpnpfkiiii . , 00HH否则就接受否则就接受下拒绝下拒绝则在显著性水平则在显著性水平 注意注意 . 5 ,50 ,. , ,2 ii npnnpn或每一个或每一个一般一般根据实践根据实践不太小不太小要足够大要足够大检验法时检验法时在使用在使用 北邮信息安全中心 北邮计算机学院 对称密码学及其应用对称密码学及其应用 16 解解 例例 试检验这颗骰子的六个面是否匀称试检验这颗骰子的六个面是否匀称? )05. 0 ( 取取根据题意需要检验假设根据题意需要检验假设 把一颗骰子重复抛掷把一颗骰子重复抛掷 300 次次, 结果如下结果如下: 305260487040654321 出现的频数出现的频数出现的点数出现的点数H0: 这颗骰子的六个面是匀称的这颗骰子的六个面是
