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

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

2、i輪的輸出，它們同時(shí)也是第i+1輪的輸入。第i輪的子密鑰記為Ki，F(xiàn)是輪函數(shù)，且Yi=F(Yi-1,Ki)。1*iiiYYY1*iY*iY1.1.差分密碼分析差分密碼分析5定義：r-輪特征(r-round characteristic) 是一個(gè)差分序列：0,1,r 其中0是明文對(duì)Y0和Y*0的差分， i(1ir)是第i輪輸出Yi和Y*i的差分。 r-輪特征=0,1,r的概率是指在明文Y0和子密鑰K1,Kr獨(dú)立、均勻隨機(jī)時(shí)，明文對(duì)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 對(duì)r-輪迭代密碼的差分密碼分析過(guò)程可綜述為如下的步驟： 找出一個(gè)(r-1)-輪特征(r-1)= 0,1,r-1，使得它的概率達(dá)到最大或幾乎最大。 均勻隨機(jī)地選擇明文Y0并計(jì)算Y*0，使得Y0和Y*0的差分為0，找出Y0和Y*0在實(shí)際密鑰加密下所得的密文Yr和Y*r。1.1.差分密碼分析過(guò)程差分密碼分析過(guò)程8n 若最后一輪的子密鑰Kr（或Kr的部分比特）有2m個(gè)可能值Kjr(1j2m)，設(shè)置相應(yīng)的2m個(gè)計(jì)數(shù)器j(1j2

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

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

6、的目標(biāo)就是找出以下形式的有效線性方程：其中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)于密鑰比特的一個(gè)線性方程。對(duì)不同的明文密文對(duì)重復(fù)以上過(guò)程，可得關(guān)于密鑰的一組線性方程，從而確定出密鑰比特。2. 2. 線性密碼分析線性密碼分析15 研究表明，當(dāng) 充分小時(shí)，攻擊成功的概率是 這一概率只依賴于 ，并隨著N或 的增加而增加。12p12p12N p2212212xN pedx2. 2. 線性密碼分析線性密碼分析16 如何對(duì)差分密碼分析和線性密碼分析進(jìn)行改進(jìn)，降低它們的復(fù)雜度仍是現(xiàn)在理論研究的熱點(diǎn)，目前已推出了很多改進(jìn)方法，例如,高階差分密碼分析、截段差分密碼分析（truncated differential cryptanalysis）、不可能差分密碼分析、多重線性密碼分析、非線性密碼分析、劃分密碼分析和差分-線性密碼分析。 再如針對(duì)密鑰編排算法的相關(guān)密鑰攻擊、基于Lagrange插