【正文】 換，即一一映射，對 264個可能的輸入分組到 264個可能的密文分組的總映射個數(shù)為 (264)! 。 ? 另一方面，對每個不同的密鑰， DES都定義了一個映射，總映射數(shù)為2561017 。因此，可假定用兩個不同的密鑰兩次使用 DES，可得一個新映射，而且這一新映射不出現(xiàn)在單重 DES定義的映射中。 ? 這一假定已于 1992年被證明。所以使用二重 DES產(chǎn)生的映射不會等價于單重 DES加密。 202210202210置 換 空 間 ( 26 4) !D E S二 重 D E S66/149 ? 對二重 DES的中途相遇攻擊 ? 該類攻擊不依賴于 DES的任何特性，可用于攻擊任何分組密碼。 ? 實施正確攻擊時僅有一個名密文對，不能給出解密是否正確的判定信息，需要多個 ? 基本思想： ? 如果有 C=EK2(EK1[P])，那么 X=EK1[P]=DK2[C] ? 如果已知一個明文密文對 (P,C)，攻擊的實施可如下進行： ? 首先，用 256個所有可能的 K1對 P加密，將加密結(jié)果存入一表并對表按 X排序， ? 然后用 256個所有可能的 K2對 C解密，在上述表中查找與 C解密結(jié)果相匹配的項，如果找到，則記下相應(yīng)的 K1和 K2。 ? 最后再用一新的明文密文對 (P?,C?)檢驗上面找到的 K1和 K2，用 K1和 K2對 P ?兩次加密，若結(jié)果等于 C?，就可確定 K1和 K2是所要找的密鑰。 67/149 ? 對已知的明文 P，二重 DES能產(chǎn)生 264個可能的密文 ,而可能的密鑰個數(shù)為 2112，所以平均來說，對一個已知的明文，有 2112/264=248個密鑰可產(chǎn)生已知的密文 ? 即一輪攻擊可將對 (P,C)的密鑰可能空間縮小為 248，誤報率為248個 ? 而再經(jīng)過另外一對明文密文的檢驗，誤報率將下降到 24864=216。所以在實施中途相遇攻擊時，如果已知兩個明文密文對，則找到正確密鑰的概率為 1216 ? 對另一個已知的明文，平均有 248/264=2－ 16個密鑰可產(chǎn)生已知的密文，即有的密文在 248個密鑰空間中沒有對應(yīng)密鑰， 平均不到1個 ，所以兩個對下來，幾乎可以確定密鑰 68/149 兩個密鑰的三重 DES ? 抵抗中途相遇攻擊的一種方法是使用 3個不同的密鑰做 3次加密，從而可使已知明文攻擊的代價增加到 2112。然而，這樣又會使密鑰長度增加到 56 3=168比特，因而過于笨重。 ? 一種實用的方法是僅使用兩個密鑰做 3次加密，實現(xiàn)方式為加密 \|解密 \|加密， 簡記為 EDE( encryptdecryptencrypt)，最早是由Tuchman設(shè)計的，見圖 ，即： E EPBCK1K1( a ) 加 密DK2AD DPBCK1K1EK2A( b ) 解 密兩 個 密 鑰 的 三 重 D E S? C=EK1(DK2(EK1[P])) ? 第二步解密的目的僅在于使得用戶可對 一重DES加密的數(shù)據(jù)解密 ，此方案已在密鑰管理標準 ANS ISO 8732中被采用。 69/149 三個密鑰的三重 DES ?三個密鑰的三重 DES密鑰長度為 168比特，加密方式為 ? C=EK3(DK2(EK1[P])) ? 令 K3=K2或 K1=K2則變?yōu)橐恢?DES ?三個密鑰的三重 DES已在因特網(wǎng)的許多應(yīng)用（如 PGP和 S/MIME）中被采用。 70/149 差分密碼分析和線性密碼分析 ? 差分密碼分析－選擇明文攻擊 ? 差分密碼分析是迄今已知的攻擊迭代密碼最有效的方法之一， ? 其基本思想是： 通過分析明文對的差值對密文對的差值的影響來恢復(fù)某些密鑰比特。 ? 對分組長度為 n的 r輪迭代密碼，兩個 n比特串 Yi和 Yi*的差分定義為 ? ΔYi＝ Yi?(Yi*)－ 1。其中 ?表示 n比特串集上的一個特定群運算， (Yi*)－ 1表示 Yi*在此群中的逆元。 在 DES的差分分析中差分的計算 選擇 Yi197。Yi*，因為 197。運算的單位元是 0元 ? 由加密對可得差分序列： ΔY0,ΔY1,…, ΔYr ? 其中 Y0和 Y0*是明文對， Yi和 Yi* (1?i?r)是第 i輪的輸出，它們同時也是第 i+1輪的輸入。第 i輪的子密鑰記為 Ki， F是輪函數(shù)，且 Yi=F(Yi1,Ki)。 71/149 ? 定義 31： r輪特征 (rround characteristic)Ω是一個差分序列： α0,α1,…, αr ? 其中 α0是明文對 Y0和 Y0*的差分， αi(1≤i≤r)是第 i輪輸出 Yi和 Yi*的差分 ? r輪特征 Ω=α0,α1,…, αr的概率是指在明文 Y0和子密鑰 K1,…, Kr獨立、均勻隨機時，明文對 Y0和 Y0*的差分為 α0的條件下，第 i(1≤i≤r)輪輸出 Yi和 Yi*的差分為 αi的概率。 ? 共有 r個概率值 ? 定義 32：在 r輪特征 Ω=α0,α1,…, αr中，定義 ? piΩ=P(ΔF(Y)=αi|ΔY=αi1) ? 即 piΩ表示在輸入差分為 αi1的條件下，輪函數(shù) F的輸出差分為 αi的概率。 （轉(zhuǎn)移概率） ? r輪特征 Ω=α0,α1,…, αr的概率近似看作 ?i=1～ r piΩ。 72/149 ? 對 r輪迭代密碼的差分密碼分析過程可綜述為如下步驟： ? ① 找出一個 (r1)輪特征 Ω(r1)=α0,α1,…, αr1， 使得它的概率達到最大或幾乎最大。（通過統(tǒng)計分析或者數(shù)學(xué)推導(dǎo)的方法） ? ② 均勻隨機地選擇明文 Y0并計算 Y0*，使得 Y0和 Y0*的差分為 α0，找出 Y0和 Y0*在實際密鑰加密下所得的密文 Yr和 Yr*。 ? 若最后一輪的子密鑰 Kr（或 Kr的部分比特）有 2m個可能值Krj(1≤j≤2m)，設(shè)臵相應(yīng)的 2m個計數(shù)器 Λj(1≤j≤2m)；用每個 Krj解密密文 Yr和 Yr*，得到 Yr1和 Yr1*，如果 Yr1和 Yr1*的差分是 αr1，則給相應(yīng)的計數(shù)器 Λj加 1。 ? ③ 重復(fù)步驟②，直到一個或幾個計數(shù)器的值明顯高于其他計數(shù)器的值，輸出它們所對應(yīng)的子密鑰（或部分比特）。 ? DES的差分攻擊有比上述過程更有效的改進方式。 73/149 ? 上述原理： ? 在 (r1)輪特征下 ， 如果明文對 Y0和 Y0*的選擇使得差分為 α0， 則第 (r1)輪的差分將以較大的概率為 （ ?i=1～ r piΩ）αr1 ? 那么如果已知相應(yīng)的密文對為 Yr和 Yr*， 則窮盡第 r輪子密鑰進行 1輪解密 ， 此時密鑰長度相對小 ， 解密只有一輪 ，速度快 ， 因此可行 ? 解密后的 Yr1和 Yr1*如果差分是 αr1則相應(yīng)的子密鑰可能以較大的概率是正確的 ， 滿足條件的子密鑰的個數(shù)可能有很多個 ， 對他們計數(shù) 。 ? 但如果選擇足夠多對的明文滿足差分為 α0， 則正確的子密鑰所對應(yīng)的計數(shù)將以很大的概率遠遠超過其它的子密鑰的計數(shù) ， 從而破譯出一些密鑰比特 ， 其它的剩余密鑰比特較少可直接采用搜索的辦法 。 74/149 示例 ? 1輪特征 (1)： ?0, ?1 ? ?0 L0?=any R0?=0000000016 ? ?1 L1?= 0000000016 R1?= L0? p＝ 1 ? 1輪特征 (2)： ?0, ?1 ? ?0 L0?= 0000000016 R0?=6000000016 ? ?1 L1?= 6000000016 R1?=0080820226 p=14/64 ? 一個 3輪特征 : ?0, ?1, ?2, ?3 ? ?0 L0?= 4008000016 R0?=0400000016 ? ?1 L1?= 0400000016 R1?=0000000016 p1=1/4 ? ?2 L2?= 0000000016 R2?=0400000016 p2=1 ? ?3 L3?= 0400000016 R3?=4008000016 p3=1/4 ? 3輪特征概率為 p1 p2 p3＝ 1/16 由此 3輪特征可容易破譯僅 4輪加密的DES 75/149 ? 一種攻擊的復(fù)雜度可以分為兩部分： ? 數(shù)據(jù)復(fù)雜度和處理復(fù)雜度。 ? 數(shù)據(jù)復(fù)雜度是實施該攻擊所需輸入的數(shù)據(jù)量； ? 而處理復(fù)雜度是處理這些數(shù)據(jù)所需的計算量。這兩部分的主要部分通常被用來刻畫該攻擊的復(fù)雜度。 ? 差分密碼分析的復(fù)雜度 ? 差分密碼分析的數(shù)據(jù)復(fù)雜度是成對加密所需的選擇明文對（ Y0，Y0*）個數(shù)的兩倍。 ? 差分密碼分析的處理復(fù)雜度是從 (ΔYr1, Yr， Yr*)找出子密鑰 Kr（或Kr的部分比特）的計算量，它實際上與 r無關(guān)，而且由于輪函數(shù)是弱的，所以此計算量在大多數(shù)情況下相對較小。 ? 因此，差分密碼分析的復(fù)雜度取決于它的數(shù)據(jù)復(fù)雜度。 76/149 線性密碼分析－已知明文攻擊 ? 線性密碼分析是對迭代密碼的一種已知明文攻擊，它利用的是密碼算法中的?不平衡（有效）的線性逼近?。 ? 設(shè)明文分組長度和密文分組長度都為 n比特，密鑰分組長度 m比特，記 ? 明文分組為 P[1]， P[2]， … ， P[n]，比特形式 ? 密文分組為 C[1]， C[2]， … ， C[n]， ? 密鑰分組為 K[1]， K[2]， … ， K[m]。 ? 定義 :A[i,j,…, k]=A[i]197。A[j]197。… 197。A[k] ? 線性密碼分析的目標就是找出以下形式的線性方程： ? P[i1,i2,…, ia]197。 C[j1,j2,…, jb]=K[k1,k2,…, kc] ? 其中 1?a?n， 1?b?n， 1?c?m ? 如果對于猜測的密鑰和已知的大量明密文對，方程成立的概率 p≠1/2，則稱該方程是有效的線性逼近。如果 |p1/2|是最大的，則稱該方程是最有效的線性逼近。 77/149 ? 設(shè) N表示明文數(shù)， T是使方程左邊為 0的明文數(shù)。 ? 如果 TN/2，則令 ? K[k1,k2,…, kc]＝ ? 如果 TN/2，則令 ? K[k1,k2,…, kc]＝ ? 從而可得關(guān)于密鑰比特的一個線性方程。 ? 對不同的明文密文對重復(fù)以上過程，可得關(guān)于密鑰的一組線性方程，從而確定出密鑰比特。 ? 研究表明，當(dāng) |p1/2|充分小時，攻擊成功的概率是 ? 這一概率只依賴于 ，并隨著 N或 的增加而增加 ?????2/1,12/1,0pp?????2/1,12/1,0ppdxepN x? ? ?? ?|2/1|2 2/221 ?|2/1| ?pN |2/1| ?p如果方程成立的概率大于 1/2，則由于使得左邊為 0的明文數(shù)T大于總明文數(shù)的一半，在所有方程成立的情況中，左邊得 0的可能性更大，所以此時令右邊取 0。 反之方程不成立的概率大于一半，則左邊 1多，右邊取 1 78/149 ? 對于 n輪 DES，我們假定使用 n1輪的 DES的最佳表達式，即假定已經(jīng)把最后一輪使用 Kn做了解密 ? 密文為 CL||CR則一輪解密后為 CR197。F(CL,Kn) ||CL ? 則構(gòu)造方程 P[i1,i2,…, ia]197。C[j1,j2,…, jb] 197。F(CL, Kn) [e1, e2, …, ed] =K[k1,k2,…, kc] ? 表達式與 F和 Kn有關(guān)，若帶入一個不正確的 Kn，這個等式的有效性顯然就降低了，可使用最大似然法來推導(dǎo) Kn， ? 對于每一個候選的 Kn(i)， 設(shè) Ti使得等式左邊為 0的明文個數(shù) ? 對于最大的 Ti(此時對應(yīng)的子密鑰為 Kn(i))記作 Tmax，最小的記作 Tmin，則當(dāng) |Tmax－ N/2||Tmin－ N/2 |,將 Tmax對應(yīng)的候選者 Kn(i)作為 Kn，并猜定 K[k1,k2,…, kc]＝ 0(p1/2)或 1 (p1/2)，反之同理 ? 選取密鑰的不同 bit位臵，將得到一組線性方程組 79/149 ? 如何對差分密碼分析和線性密碼分析進行改進，降低它們的復(fù)雜度仍是現(xiàn)在理論研究的熱點 ? 目前已推出了很多改進方法，例如 , ? 高階差分密碼分析 ? 截段差分密碼分析（ truncated differential cryptanalysis）、 ? 不可能差分密碼分析 ? 多重線性密碼分析 ? 非線性密碼分析 ? 差分 線性密碼分析。 ? 再如針對密鑰編排算法的相關(guān)密鑰攻擊、基于 Lagrange插值公式的插值攻擊及基于密碼器件的能量分析（ power analysis），另外還有