差分密码分析和线性密码分析原理

《差分密码分析和线性密码分析原理》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、差分密码分析和线性密码分析原理CONTENTS0102差分密码分析线性密码分析PARTONE差分密码分析差分密码分析是迄今为止已知的攻击迭代分组密码最有效的方法之一，其基本思想是：通过分析明文对的差值对密文对的差值来影响来恢复某些密钥比特当密码分析人员可以进行选择明文分析时，差分密码分析十分有效。已知明文的差分密码分析也是可行的，但是要求已知明密文的量很大差分密码分析简介设计DES的IBM小组知道了差分分析197419911990……Biham和Shamir对多种加密算法和Hash函数进行差分密码分析攻击，结果发表在[BIHA93]中差分密码分析公开发表最早研究是Murphy分析分组密码FE

2、AL【MURP90】差分密码分析的历史6符号定义P表示明文，T表示密文(P,P∗)表示明文对，其异或后得到特定的值：P’,使得P’=P⊕P∗(T,T∗)表示密文对，其异或后得到特定的值T’，使得T’=T⊕T∗带撇的值总是表示差分，P’,T’,a’,A’。例如，a’=a⊕a∗7差分密码分析_DESDES的设计要求之一是确保尽可能的分布均匀例如，明文或密钥的1比特变化，将导致64比特的密文中大约32比特的看起来是不可预测和随机的变化不过对于固定的密钥，DES的差分并不呈现伪随机现象即对于固定明文P和P∗的异或P’T’=T⊕T∗不是均匀分布的8S-Box是非差分均匀的对于输入S盒的6比特的(x,x

3、∗)值对，一共有多少种可能？考虑一个S-box的差分现象：输入值对的差分为x’=x⊕x∗差分值可能有多少种？对于其4比特输出值，y=S(x),y∗=S(x∗)，以及y’=y⊕y∗=S(x)⊕S(x∗)输出差分值有多少种可能？642=409626=6424=16S-Box是非差分均匀的x0123456789abcdefx⊕f’fedcba9876543210S(x)e4d12fb83a6c5907S(x⊕f’)7095c6a38bf21d4ES(x)⊕S(x⊕f’)9444e91bb19e4449输入差分f’=111110S1的差分分布表０.........６３=26-1出现的次数6比特的差分

4、输入x’有64个值：00-3F(16进制，10进制是0-63)4比特的差分输出y’有16个值：0-F(16进制，10进制是0-15)可以看到：第一行除第一列外全为0，因为当x’=x⊕x∗=0，同样的输入出现了两次，因此其输出y’=y⊕y∗=0后面的行：例如，当x’=01时,6个可能的y’中有5个值:0,1,2,4,8呈现0可能次数，就是说不出现。A出现的概率是12/649和C出现的概率是10/64这就是说，S1呈现出很强的不均匀分布这种差分不均匀性对于所有的S盒S1,S2,...,S8都有体现考虑输入异或值为34时，可能的输出异或是：其中：344有两种可能，这种输入对是成双的，即：(α,β

5、)和(β,α)S1的差分分布表对S1构建差分表，发现当输入是13和27时(只看后面的6位)：12S1的差分分布表12列出S1中输入异或值为34的可能的输入值(16进制)：13确定密钥的原理假设已知S1的两个输入是01和35，其异或的结果是34，经过S1之后输出异或的结果是D。查S1的差分分布表，得到输入异或为34，输出异或为D时，可能的输入：14确定密钥的原理14实际上，输入异或的结果是34，与密钥无关，这是因为：因为所以这样就得到：所以，可能的密钥就是15确定密钥的原理此外，假设已知S1的两个输入是21和15，它们异或后的结果是34，输出异或后的结果是3。查S1的差分分布表，得到输入异或为

6、34，输出异或为3时，可能的输入：。16确定密钥的原理16这样就可以从得到可能的密钥值17确定密钥的原理17而正确的密钥值必定同时出现在两个集合因此可以确定密钥是在中的一个。要确定到底是哪一个，需要知道更多的输入输出异或对。以此类推得到此轮密钥18多轮DES的特征差分输入具有很高的或然性，可以直接追踪到多轮的情况，观察到：E扩展中的异或值是线性的：异或值与密钥是无关的：192轮DES的特征差分密码分析20在第一轮中，输入到函数f的差分结果是a’=60000000经f中的扩展变换后，把这部分放进了每个S盒的中间4个比特，顺序是S1：6=0110S2：0=0000S3,...,S8等等因为所有边

7、缘比特都是0，所以S1是唯一的得到非0差分输入的S盒。S1的差分输入是001100=0C而其他所有Ｓ盒S2,...,S8的差分输入都是０2轮DES的特征差分密码分析21察看S1的差分分布表，发现当输入异或x’=0C时，最可能的差分输出y’是E=1110，出现的概率是14/64；其他Ｓ盒的输入一定是x’=0且y’=0Ｓ盒的输入通过置换Ｐ成为f(R,K)的输出。如前所述，f(R,K)的差分输出是而A’与L’异或后