现代密码学第4章4：差分和线性分析.ppt

分组密码:差分密码分析与线性密码分析 本节主要内容 1、差分密码分析 2、线性密码分析 差分密码分析是迄今已知的攻击迭代密码最有效的方法之一，其基本思想是： 通过分析明文对的差值对密文对的差值的影响来恢复某些密钥比特。 对分组长度为n的r轮迭代密码，两个n比特串Yi和Y*i的差分定义为 其中表示n比特串集上的一个特定群运算， 表示 在此群中的逆元。 由加密对可得差分序列： ΔY0,ΔY1,…,ΔYr 其中Y0和Y*0是明文对，Yi和Y*i(1≤i≤r)是第i轮的输出，它们同时也是第i+1轮的输入。第i轮的子密钥记为Ki，F是轮函数，且Yi=F(Yi-1,Ki)。 定义：r-轮特征(r-round characteristic) Ω是一个差分序列：α0,α1,…,αr 其中α0是明文对Y0和Y*0的差分， αi(1≤i≤r)是第i轮输出Yi和Y*i的差分。 r-轮特征Ω=α0,α1,…,αr的概率是指在明文Y0和子密钥K1,…,Kr独立、均匀随机时，明文对Y0和Y*0的差分为α0的条件下，第i(1≤i≤r)轮输出Yi和Y*i的差分为αi的概率。 定义在r-轮特征Ω=α0,α1,…,αr中，定义 =P(ΔF(Y)=αi|ΔY=αi-1) 即 表示在输入差分为αi-1的条件下，轮函数F的输出差分为αi的概率。 r-轮特征Ω=α0,α1,…,αr的概率近似看作 。 对r-轮迭代密码的差分密码分析过程可综述为如下的步骤： ① 找出一个(r-1)-轮特征Ω(r-1)= α0,α1,…,αr-1，使得它的概率达到最大或几乎最大。 ② 均匀随机地选择明文Y0并计算Y*0，使得Y0和Y*0的差分为α0，找出Y0和Y*0在实际密钥加密下所得的密文Yr和Y*r。 1.差分密码分析过程 若最后一轮的子密钥Kr（或Kr的部分比特）有2m个可能值Kjr(1≤j≤2m)，设置相应的2m个计数器Λj(1≤j≤2m)；用每个Kjr解密密文Yr和Y*r，得到Yr-1和Y*r-1，如果Yr-1和 Y*r-1的差分是αr-1，则给相应的计数器Λj加1。 ③ 重复步骤②，直到一个或几个计数器的值明显高于其他计数器的值，输出它们所对应的子密钥（或部分比特）。 一种攻击的复杂度可以分为两部分： 数据复杂度和处理复杂度。 数据复杂度是实施该攻击所需输入的数据量； 而处理复杂度是处理这些数据所需的计算量。这两部分的主要部分通常被用来刻画该攻击的复杂度。 差分密码分析的数据复杂度是成对加密所需的选择明文对（Y0,Y*0）个数的两倍。差分密码分析的处理复杂度是从 (ΔYr-1, Yr, Y*r)找出子密钥Kr（或Kr的部分比特）的计算量，它实际上与r无关，而且由于轮函数是弱的，所以此计算量在大多数情况下相对较小。 因此，差分密码分析的复杂度取决于它的数据复杂度。 线性密码分析是对迭代密码的一种已知明文攻击，它利用的是密码算法中的“不平衡（有效）的线性逼近”。 设明文分组长度和密文分组长度都为n比特，密钥分组长度为m比特。记 明文分组为P[1]，P[2]，…，P[n]， 密文分组为C[1]，C[2]，…，C[n]， 密钥分组为K[1]，K[2]，…，K[m]。 线性密码分析的目标就是找出以下形式的有效线性方程： 其中1≤a≤n,1≤b≤n,1≤c≤m。 如果方程成立的概率p≠1/2，则称该方程是有效的线性逼近。如果 是最大的，则称该方程是最有效的线性逼近。 设N表示明文数，T是使方程左边为0的明文数。如果TN/2，则令 如果TN/2，则令 从而可得关于密钥比特的一个线性方程。对不同的明文密文对重复以上过程，可得关于密钥的一组线性方程，从而确定出密钥比特。 研究表明，当 充分小时，攻击成功的概率是 这一概率只依赖于 ，并随着N或 的增加而增加。 如何对差分密码分析和线性密码分析进行改进，降低它们的复杂度仍是现在理论研究的热点，目前已推出了很多改进方法，例如,高阶差分密码分析、截段差分密码分析（truncated differential cryptanalysis）、不可能差分密码分析、多重线性密码分析、非线性密码分析、划分密码分析和差分-线性密码分析。