【正文】 ? 再如針對密鑰編排算法的相關(guān)密鑰攻擊、基于 Lagrange插值公式的插值攻擊及基于密碼器件的能量分析（ power analysis），另外還有錯誤攻擊。C[j1,j2,…, jb] 197。 反之方程不成立的概率大于一半，則左邊 1多，右邊取 1 78/149 ? 對于 n輪 DES，我們假定使用 n1輪的 DES的最佳表達式，即假定已經(jīng)把最后一輪使用 Kn做了解密 ? 密文為 CL||CR則一輪解密后為 CR197。 ? 對不同的明文密文對重復(fù)以上過程，可得關(guān)于密鑰的一組線性方程，從而確定出密鑰比特。 77/149 ? 設(shè) N表示明文數(shù)， T是使方程左邊為 0的明文數(shù)。 C[j1,j2,…, jb]=K[k1,k2,…, kc] ? 其中 1?a?n， 1?b?n， 1?c?m ? 如果對于猜測的密鑰和已知的大量明密文對，方程成立的概率 p≠1/2，則稱該方程是有效的線性逼近?！?197。 ? 定義 :A[i,j,…, k]=A[i]197。 76/149 線性密碼分析－已知明文攻擊 ? 線性密碼分析是對迭代密碼的一種已知明文攻擊，它利用的是密碼算法中的?不平衡（有效）的線性逼近?。 ? 差分密碼分析的處理復(fù)雜度是從 (ΔYr1, Yr， Yr*)找出子密鑰 Kr（或Kr的部分比特）的計算量，它實際上與 r無關(guān)，而且由于輪函數(shù)是弱的，所以此計算量在大多數(shù)情況下相對較小。這兩部分的主要部分通常被用來刻畫該攻擊的復(fù)雜度。 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ù)雜度。 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ù) 。 ? ③ 重復(fù)步驟②，直到一個或幾個計數(shù)器的值明顯高于其他計數(shù)器的值，輸出它們所對應(yīng)的子密鑰（或部分比特）。（通過統(tǒng)計分析或者數(shù)學(xué)推導(dǎo)的方法） ? ② 均勻隨機地選擇明文 Y0并計算 Y0*，使得 Y0和 Y0*的差分為 α0，找出 Y0和 Y0*在實際密鑰加密下所得的密文 Yr和 Yr*。 （轉(zhuǎn)移概率） ? r輪特征 Ω=α0,α1,…, αr的概率近似看作 ?i=1～ r piΩ。 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的概率。運算的單位元是 0元 ? 由加密對可得差分序列： ΔY0,ΔY1,…, ΔYr ? 其中 Y0和 Y0*是明文對， Yi和 Yi* (1?i?r)是第 i輪的輸出，它們同時也是第 i+1輪的輸入。 在 DES的差分分析中差分的計算 選擇 Yi197。 ? 對分組長度為 n的 r輪迭代密碼，兩個 n比特串 Yi和 Yi*的差分定義為 ? ΔYi＝ Yi?(Yi*)－ 1。 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）中被采用。然而，這樣又會使密鑰長度增加到 56 3=168比特，因而過于笨重。 67/149 ? 對已知的明文 P，二重 DES能產(chǎn)生 264個可能的密文 ,而可能的密鑰個數(shù)為 2112，所以平均來說，對一個已知的明文，有 2112/264=248個密鑰可產(chǎn)生已知的密文 ? 即一輪攻擊可將對 (P,C)的密鑰可能空間縮小為 248，誤報率為248個 ? 而再經(jīng)過另外一對明文密文的檢驗，誤報率將下降到 24864=216。 ? 實施正確攻擊時僅有一個名密文對，不能給出解密是否正確的判定信息，需要多個 ? 基本思想： ? 如果有 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。所以使用二重 DES產(chǎn)生的映射不會等價于單重 DES加密。因此，可假定用兩個不同的密鑰兩次使用 DES，可得一個新映射，而且這一新映射不出現(xiàn)在單重 DES定義的映射中。 ? DES加密是一個代換，即一一映射，對 264個可能的輸入分組到 264個可能的密文分組的總映射個數(shù)為 (264)! 。其中明文為 P，兩個加密密鑰為 K1和 K2 ? 密文為： C=EK2(EK1[P])， ? 解密時，以相反順序使用兩個密鑰： P=DK1(DK2[C]) ? 二重 DES所用密鑰長度為 112比特，強度極大地增加。 64/149 二重 DES ? 為了 提高 DES的安全性 ，并 利用實現(xiàn) DES的現(xiàn)有軟硬件 ，可將 DES算法在多密鑰下多重使用 。 ? 美國國家標準和技術(shù)協(xié)會已征集并進行了幾輪評估、篩選，產(chǎn)生了稱之為 AES(advanced encryption standard) 的新加密標準。 ? 一些強力攻擊的案例： ? 1997年 DESCHALL小組經(jīng)過近 4個月的努力，通過 Inter搜索了 3 1016個密鑰，找出了 DES的密鑰，恢復(fù)出了明文。本章將對差分和線性分析方法進行介紹 63/149 ? DES的評估 ? 規(guī)定 每隔 5年 由美國國家保密局（ national security agency, NSA）作出評估，并重新批準它是否繼續(xù)作為聯(lián)邦加密標準。因此，隨著計算機能力的增強與計算技術(shù)的提高，必須相應(yīng)地增加密碼算法的密鑰長度。 62/149 ? 結(jié)果是：密鑰長度為 40bit和 48bit的 RC5算法被攻破；美國克羅拉多州的程序員 Verser從 1997年 3月 13日 起用了 96天的時間，在 Inter上數(shù)萬名志愿者的協(xié)同工作下 ，于1997年 6月 17日成功地 找到了 DES的密鑰 ，獲得了 RSA公司頒發(fā)的 10000美金的獎勵。 ? 1997年 1月 28日，美國 RSA數(shù)據(jù)安全公司在 RSA安全年會上發(fā)布了一項 ? 秘密密鑰挑戰(zhàn) ? 競賽，分別懸賞 1000美金、 5000美金和10000美金用于攻破不同長度的 RC5密碼算法，同時還 懸賞 10000美金破譯密鑰長度為 56bit的 DES。人們也用 ?2檢驗證明： DES迭代 8輪以后，就可認為輸出和輸入不相關(guān)了。 ? 所幸在總數(shù) 256個可選密鑰中，弱密鑰與半弱密鑰所占的比例極小，如果是隨機選擇， (半 )弱密鑰出現(xiàn)的概率很小，因而其存在性并不會危及 DES的安全。 ? 若 C0與 D0分別是 {00,11,10,01}中任意一個的 14次重復(fù) ，則因這樣的 C0與 D0都對環(huán)移 (無論左或右 )偶數(shù)位具有自封閉性，故 59/149 ? 若 PC11(C0D0)=K,則由 K擴展出來的加密子密鑰為： ? K1,K2,K2,K2,K2,K2,K2,K2, K1, K1, K1, K1, K1, K1, K1, K2 ? 把 C0與 D0各自左環(huán)移一位得 C1與 D1，設(shè) PC11 (C1D1)=K’，則由 K’擴展出來的加密子密鑰為： ? K2, K1, K1, K1, K1, K1, K1, K1, K2,K2,K2,K2,K2,K2,K2, K1 ? 因此，由上述 C0與 D0導(dǎo)致的 K與 K’互為對合； K中只有這些對合對 ? 對于 K，若 K是自己的對合，則稱 K為 DES的一個弱密鑰 ? 若 K存在異于自己的對合，則稱 K為 DES的一個半弱密鑰 60/149 ? 顯然， C0與 D0分別是 {00,11,10,01}中任意一個的 14次重復(fù)的情況共有 42=16種，其中 C0與 D0分別是{00,11}中任意一個的 14次重復(fù)的情況 (計 22=4種 )對應(yīng)弱密鑰；剩下的 (164=12種 )對應(yīng)半弱密鑰 。 iRM C KKMC K)( MDE SC K?58/149 ? 2）弱密鑰與半弱密鑰 . ? 大多數(shù)密碼體制都有某些明顯的?壞密鑰? ? 對于 K和 K’，若由 K擴展出來的加密子密鑰為：K1,K2,…,K 15,K16，而由 K’擴展出來的加密子密鑰卻是：K16,K15,…,K 2,K1，即有 DESK1=DESK’，則稱 K與 K’互為對合 。 ),(),( 1111 iiiiii KRFLKRFL ???? 197。 ? 其中 C2= )( MDE SC K?ba197。 ? 由此 DES在選擇明文攻擊時工作量會減少一半。a 197。b，可得 =F(Ri1,Ki) ? (3)由 197。(1197。 ? 證明： ? 臵換本身的取反特性可以保持 ? (1)若以 K為主密鑰擴展的 16個加密子密鑰記為 K1,K2,…, K16，則以 為主密鑰擴展的 16個加密子密鑰為 ? (2)由 ＝ (1197。 ? S盒的爭論： ? 公眾仍然不知道 S盒的構(gòu)造中是否還使用了進一步的設(shè)計準則（有陷門？） ? 密鑰長度是否足夠？（已經(jīng)證明密鑰長度不夠） ? 迭代的長度？（ 1 32？） 57/149 ? DES的安全性問題 ? 完全依賴于所用的密鑰，即算法是公開的。001100)至少有 2bit不同； ? 對任一 S盒的任意 6bit輸入 x，及 ?, ?? {0,1}，都有 S(x)≠S(x197。一些密碼學(xué)家懷疑美國 NSA(the National Security Agency)設(shè)計 S盒時隱藏了 ? 陷門 ? ，使得只有他們才知道破譯算法，但沒有證據(jù)能表明這一點。 ? S盒作為該密碼體制的非線性組件對安全性至關(guān)重要。 ? 臵換 P的設(shè)計 使每層 S盒的 4bit輸出進入到下一層的 4個不同 S盒 ? 每個 S盒的輸入由分屬上一層中 4個不同 S盒的輸出構(gòu)成。 ?????????????????其它,216,9,2,11,0iiRS i54/149 ? DES加密實例 ? 取 16進制明文 X： 0123456789ABCDEF ? 密鑰 K為： 133457799BBCDFF1 ? 去掉奇偶校驗位以二進制形式表示的密鑰是 ? 00010010011010010101101111001001101101111011011111111000 ? 應(yīng)用初始臵換 IP，我們得到： L0=11001100000000001100110011111111 R0=11110000101010101111000010101010 然后進行 16輪加密。 PC－ 1 PC－ 2 57 49 41 33 25 17 9 14 17 11 24 1 5 1 58 50 42 34 26 18 3 28 15 6 21 10