現(xiàn)代密碼學第4章4：差分和線性分析

1、1分組密碼分組密碼:差分密碼分析與線性密碼分析差分密碼分析與線性密碼分析現(xiàn)代密碼學現(xiàn)代密碼學第第4章章(4)2本節(jié)主要內(nèi)容本節(jié)主要內(nèi)容n1 1、差分密碼分析、差分密碼分析n2 2、線性密碼分析、線性密碼分析3 差分密碼分析是迄今已知的攻擊迭代密碼最有效的方法之一，其基本思想是： 通過分析明文對的差值對密文對的差值的影響來恢復某些密鑰比特。1. 差分密碼分析差分密碼分析4 對分組長度為n的r輪迭代密碼，兩個n比特串Yi和Y*i的差分定義為 其中表示n比特串集上的一個特定群運算， 表示 在此群中的逆元。 由加密對可得差分序列： Y0,Y1,Yr 其中Y0和Y*0是明文對，Yi和Y*i(1ir)是第

2、i輪的輸出，它們同時也是第i+1輪的輸入。第i輪的子密鑰記為Ki，F(xiàn)是輪函數(shù)，且Yi=F(Yi-1,Ki)。1*iiiYYY1*iY*iY1.1.差分密碼分析差分密碼分析5定義：r-輪特征(r-round characteristic) 是一個差分序列：0,1,r 其中0是明文對Y0和Y*0的差分， i(1ir)是第i輪輸出Yi和Y*i的差分。 r-輪特征=0,1,r的概率是指在明文Y0和子密鑰K1,Kr獨立、均勻隨機時，明文對Y0和Y*0的差分為0的條件下，第i(1ir)輪輸出Yi和Y*i的差分為i的概率。1.1.差分密碼分析差分密碼分析6定義在r-輪特征=0,1,r中，定義 =P(F(Y)

3、=i|Y=i-1)即 表示在輸入差分為i-1的條件下，輪函數(shù)F的輸出差分為i的概率。 r-輪特征=0,1,r的概率近似看作 。ipip1riip1.1.差分密碼分析差分密碼分析7 對r-輪迭代密碼的差分密碼分析過程可綜述為如下的步驟： 找出一個(r-1)-輪特征(r-1)= 0,1,r-1，使得它的概率達到最大或幾乎最大。 均勻隨機地選擇明文Y0并計算Y*0，使得Y0和Y*0的差分為0，找出Y0和Y*0在實際密鑰加密下所得的密文Yr和Y*r。1.1.差分密碼分析過程差分密碼分析過程8n 若最后一輪的子密鑰Kr（或Kr的部分比特）有2m個可能值Kjr(1j2m)，設(shè)置相應的2m個計數(shù)器j(1j2

4、m)；用每個Kjr解密密文Yr和Y*r，得到Y(jié)r-1和Y*r-1，如果Yr-1和 Y*r-1的差分是r-1，則給相應的計數(shù)器j加1。n 重復步驟，直到一個或幾個計數(shù)器的值明顯高于其他計數(shù)器的值，輸出它們所對應的子密鑰（或部分比特）。1.差分密碼分析過程差分密碼分析過程9 一種攻擊的復雜度可以分為兩部分： 數(shù)據(jù)復雜度和處理復雜度。 數(shù)據(jù)復雜度是實施該攻擊所需輸入的數(shù)據(jù)量； 而處理復雜度是處理這些數(shù)據(jù)所需的計算量。這兩部分的主要部分通常被用來刻畫該攻擊的復雜度。1.密碼分析復雜度密碼分析復雜度10 差分密碼分析的數(shù)據(jù)復雜度是成對加密所需的選擇明文對（Y0,Y*0）個數(shù)的兩倍。差分密碼分析的處理復雜

5、度是從(Yr-1, Yr, Y*r)找出子密鑰Kr（或Kr的部分比特）的計算量，它實際上與r無關(guān)，而且由于輪函數(shù)是弱的，所以此計算量在大多數(shù)情況下相對較小。 因此，差分密碼分析的復雜度取決于它的數(shù)據(jù)復雜度。1.差分密碼分析復雜度差分密碼分析復雜度11 線性密碼分析是對迭代密碼的一種已知明文攻擊，它利用的是密碼算法中的“不平衡（有效）的線性逼近”。 設(shè)明文分組長度和密文分組長度都為n比特，密鑰分組長度為m比特。記 明文分組為P1，P2，Pn， 密文分組為C1，C2，Cn， 密鑰分組為K1，K2，Km。 , , A i jkA iA jA k2 2. . 線性密碼分析線性密碼分析12 線性密碼分析

6、的目標就是找出以下形式的有效線性方程：其中1an,1bn,1cm。 如果方程成立的概率p1/2，則稱該方程是有效的線性逼近。如果 是最大的，則稱該方程是最有效的線性逼近。121212 , , , ,abcP i iiC jjjK k kk12p2. 2. 線性密碼分析線性密碼分析13 設(shè)N表示明文數(shù)，T是使方程左邊為0的明文數(shù)。如果TN/2，則令如果TN/2，則令12102 ,112cpK k kkp12102 ,112cpK k kkp2. 2. 線性密碼分析線性密碼分析14n 從而可得關(guān)于密鑰比特的一個線性方程。對不同的明文密文對重復以上過程，可得關(guān)于密鑰的一組線性方程，從而確定出密鑰比特。2. 2. 線性密碼分析線性密碼分析15 研究表明，當 充分小時，攻擊成功的概率是 這一概率只依賴于 ，并隨著N或 的增加而增加。12p12p12N p2212212xN pedx2. 2. 線性密碼分析線性密碼分析16 如何對差分密碼分析和線性密碼分析進行改進，降低它們的復雜度仍是現(xiàn)在理論研究的熱點，目前已推出了很多改進方法，例如,高階差分密碼分析、截段差分密碼分析（truncated differential cryptanalysis）、不可能差分密碼分析、多重線性密碼分析、非線性密碼分析、劃分密碼分析和差分-線性密碼分析。 再如針對密鑰編排算法的相關(guān)密鑰攻擊、基于Lagrange插