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

《现代密码学》第4章(4) 现代密码学》 章

分组密码: 分组密码差分密码分析与线性密码分析

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

本节主要内容1、差分密码分析 2、线性密码分析

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

1. 差分密码分析差分密码分析是迄今已知的攻击迭 代密码最有效的方法之一，其基本思想 是： 通过分析明文对的差值对密文对 的差值的影响来恢复某些密钥比特。

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

1.差分密码分析 1.差分密码分析对分组长度为n的r轮迭代密码，两个n比 * 1 特串Yi和Y*i的差分定义为 Yi = Yi Yi 其中表示n比特串集上的一个特定群运 * 1 算， i 表示 Yi* 在此群中的逆元。 Y 由加密对可得差分序列： Y0, Y1,…, Yr 其中Y0和Y*0是明文对，Yi和Y*i(1≤i≤r)是 第i轮的输出，它们同时也是第i+1轮的输入。 第i轮的子密钥记为Ki,F是轮函数，且 Yi=F(Yi-1,Ki)。4

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

1.差分密码分析 1.差分密码分析定义：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的概率。5

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

1.差分密码分析 1.差分密码分析定义在r-轮特征 =α0,α1,…,αr中，定义 pi =P( F(Y)=α | Y=α ) i i-1 pi 表示在输入差分为α 的条件下，轮函 即 i-1 数F的输出差分为αi的概率。 r-轮特征 =α0,α1,…,αr的概率近似看 r pi 。 作 ∏i =1

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

1.差分密码分析过程 1.差分密码分析过程对r-轮迭代密码的差分密码分析过程可综 述为如下的步骤： ① 找出一个(r-1)-轮特征 (r-1)= α0,α1,…,αr1,使得它的概率达到最大或几乎最大。 ② 均匀随机地选择明文Y0并计算Y*0,使得 Y0和Y*0的差分为α0,找出Y0和Y*0在实际密钥 加密下所得的密文Yr和Y*r。

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

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。 ③ 重复步骤②,直到一个或几个计数器的 值明显高于其他计数器的值，输出它们所对 应的子密钥(或部分比特)。8

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

1.密码分析复杂度 密码分析复杂度一种攻击的复杂度可以分为两部分： 数据复杂度和处理复杂度。 数据复杂度是实施该攻击所需输入的数 据量； 而处理复杂度是处理这些数据所需的计 算量。这两部分的主要部分通常被用来刻画 该攻击的复杂度。

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

1.差分密码分析复杂度 差分密码分析复杂度差分密码分析的数据复杂度是成对加密 所需

的选择明文对(Y0,Y*0)个数的两倍。 差分密码分析的处理复杂度是从 ( Yr-1, Yr, Y*r)找出子密钥Kr(或Kr的部分比 特)的计算量，它实际上与r无关，而且由于 轮函数是弱的，所以此计算量在大多数情况 下相对较小。 因此，差分密码分析的复杂度取决于它 的数据复杂度。10

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

2. 线性密码分析线性密码分析是对迭代密码的一种已知 明文攻击，它利用的是密码算法中的“不平 衡(有效)的线性逼近”。A[i, j ,L , k ] = A[i ] ⊕ A[ j ] ⊕ L ⊕ A[k ]

设明文分组长度和密文分组长度都为n比 特，密钥分组长度为m比特。记 明文分组为P[1],P[2],…,P[n], 密文分组为C[1],C[2],…,C[n], 密钥分组为K[1],K[2],…,K[m]。11

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

2. 线性密码分析线性密码分析的目标就是找出以下形式 的有效线性方程： P[i1 , i2 ,L , ia ] ⊕ C[ j1 , j2 ,L , jb ] = K [k1 , k2 ,L , kc ] 其中1≤a≤n,1≤b≤n,1≤c≤m。 如果方程成立的概率p≠1/2,则称该方程 p 1 是最大的， 是有效的线性逼近。如果 2 则称该方程是最有效的线性逼近。

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

2. 线性密码分析设N表示明文数，T是使方程左边为0的 明文数。如果T>N/2,则令1 0 p > 2 K [k1 , k2 ,L , kc ] = 1 p < 1 2

如果T<N/2,则令

1 0 p < 2 K [k1 , k2 ,L , kc ] = 1 p > 1 213

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

2. 线性密码分析从而可得关于密钥比特的一个线性方程。 对不同的明文密文对重复以上过程，可得关 于密钥的一组线性方程，从而确定出密钥比 特。

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

2. 线性密码分析p 1 充分小时，攻击成 研究表明，当 2

功的概率是

1 2πN

∫

∞

1 2 N p 2

e

x2 2

dx

p 1 ,并随着N或 这一概率只依赖于 2 1 p 的增加而增加。 2

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

2. 差分和线性密码分析的改进如何对差分密码分析和线性密码分析进行改进， 降低它们的复杂度仍是现在理论研究的热点，目前 已推出了很多改进方法，例如,高阶差分密码分析、 截段差分密码分析(truncated differential cryptanalysis)、不可能差分密码分析、多重线性 密码分析、非线性密码分析、划分密码分析和差分 -线性密码分析。 再如针对密钥编排算法的相关密钥攻击、基于 Lagrange插值公式的插值攻击及基于密码器件的能 量分析(power analysis),另外还有错误攻击、 时间攻击、Square攻击和Davies攻击等。16