網(wǎng)絡(luò)信息安全

1、網(wǎng)絡(luò)信息安全分組密碼1 DES加密算法的背景發(fā)明人：美國IBM公司W(wǎng). Tuchman 和 C. Meyer 1971-1972年研制成功?；A(chǔ)：1967年美國Horst Feistel提出的理論產(chǎn)生：美國國家標準局（NBS)1973年5月到1974年8月兩次發(fā)布通告，公開征求用于電子計算機的加密算法。經(jīng)評選從一大批算法中采納了IBM的LUCIFER方案。標準化：DES算法1975年3月公開發(fā)表，1977年1月15日由美國國家標準局頒布為數(shù)據(jù)加密標準（Data Encryption Standard），于1977年7月15日生效。2DES加密算法的背景美國國家安全局（NSA, National

2、 Security Agency)參與了美國國家標準局制定數(shù)據(jù)加密標準的過程。NBS接受了NSA的某些建議，對算法做了修改，并將密鑰長度從LUCIFER方案中的128位壓縮到56位。1979年，美國銀行協(xié)會批準使用DES。1980年，DES成為美國標準化協(xié)會(ANSI)標準。1984年2月，ISO成立的數(shù)據(jù)加密技術(shù)委員會(SC20)在DES基礎(chǔ)上制定數(shù)據(jù)加密的國際標準工作。3DES的產(chǎn)生-i1973年5月15日, NBS開始公開征集標準加密算法,并公布了它的設(shè)計要求:(1)算法必須提供高度的安全性(2)算法必須有詳細的說明,并易于理解(3)算法的安全性取決于密鑰,不依賴于算法(4)算法適用于所

3、有用戶(5)算法適用于不同應(yīng)用場合(6)算法必須高效、經(jīng)濟(7)算法必須能被證實有效(8)算法必須是可出口的4DES的產(chǎn)生-ii1974年8月27日, NBS開始第二次征集,IBM提交了算法LUCIFER，該算法由IBM的工程師在19711972年研制1975年3月17日, NBS公開了全部細節(jié)1976年,NBS指派了兩個小組進行評價1976年11月23日，采納為聯(lián)邦標準，批準用于非軍事場合的各種政府機構(gòu)1977年1月15日,“數(shù)據(jù)加密標準”FIPS PUB 46發(fā)布5DES的應(yīng)用1979年，美國銀行協(xié)會批準使用1980年，美國國家標準局（ANSI）贊同DES作為私人使用的標準,稱之為DEA（

4、ANSI X.392） 1983年，國際化標準組織ISO贊同DES作為國際標準，稱之為DEA-1該標準規(guī)定每五年審查一次，計劃十年后采用新標準最近的一次評估是在1994年1月，已決定1998年12月以后，DES將不再作為聯(lián)邦加密標準。 6分組密碼的一般設(shè)計原理分組密碼是將明文消息編碼表示后的數(shù)字（簡稱明文數(shù)字）序列，劃分成長度為n的組（可看成長度為n的矢量），每組分別在密鑰的控制下變換成等長的輸出數(shù)字（簡稱密文數(shù)字）序列， 7兩個基本設(shè)計思想 Shannon稱之為理想密碼系統(tǒng)中，密文的所有統(tǒng)計特性都與所使用的密鑰獨立 擴散（Diffusion):明文的統(tǒng)計結(jié)構(gòu)被擴散消失到密文的長度統(tǒng)計特性 ,

5、使得明文和密文之間的統(tǒng)計關(guān)系盡量復雜 混亂(confusion)：使得密文的統(tǒng)計特性與密鑰的取值之間的關(guān)系盡量復雜 8分組密碼實現(xiàn)的設(shè)計原則1 1.要有足夠大分組長度n 2.密鑰空間要盡可能大 3.保證足夠強的密碼算法復雜度 4.軟件實現(xiàn)盡量采用子塊和簡單運算。 5.硬件實現(xiàn)最好加密與解密用同樣結(jié)構(gòu)，以適應(yīng)用超大規(guī)模集成芯片實現(xiàn)。 9設(shè)計原則要求 軟件實現(xiàn)的要求：使用子塊和簡單的運算。密碼運算在子塊上進行，要求子塊的長度能自然地適應(yīng)軟件編程，如8、16、32比特等。應(yīng)盡量避免按比特置換，在子塊上所進行的密碼運算盡量采用易于軟件實現(xiàn)的運算。最好是用處理器的基本運算，如加法、乘法、移位等。10實現(xiàn)

6、的設(shè)計原則 硬件實現(xiàn)的要求：加密和解密的相似性，即加密和解密過程的不同應(yīng)僅僅在密鑰使用方式上，以便采用同樣的器件來實現(xiàn)加密和解密，以節(jié)省費用和體積。盡量采用標準的組件結(jié)構(gòu)，以便能適應(yīng)于在超大規(guī)模集成電路中實現(xiàn)。11Feistel結(jié)構(gòu)圖12Feistel結(jié)構(gòu)定義加密: Li = Ri-1; Ri = Li-1 F(Ri-1,Ki)解密: Ri-1 = Li Li-1 = Ri F(Ri-1,Ki) = Ri F(Li,Ki)13Feistel結(jié)構(gòu)分析塊大小(64 128).密鑰大小(56 128256).輪數(shù)(16).子密鑰生成. 輪函數(shù)(F).軟件加密/解密速度快.硬件實現(xiàn)容易.結(jié)構(gòu)簡單.分析

7、容易.14DES示意圖15DES: 單輪結(jié)構(gòu)Li = Ri-1 Ri = Li-1F(Ri-1,Ki)16DES:輪函數(shù)F擴展: 32 48S-box: 6 4置換:P17DES:子密鑰生成18DES的描述DES利用56比特串長度的密鑰K來加密長度為64位的明文，得到長度為64位的密文輸入64比特明文數(shù)據(jù)初始置換IP在密鑰控制下16輪迭代初始逆置換IP-1輸出64比特密文數(shù)據(jù)DES算法框圖交換左右32比特 1964位碼64位碼初始變換逆初始變換乘積變換明文密文輸入輸出IPIP-120輸入（64位）58 50 42 34 26 18 10 260 52 44 36 28 20 12 462 54

8、 46 38 30 22 14 664 56 48 40 32 24 16 857 49 41 33 25 17 9 159 51 43 35 27 19 11 361 53 45 37 29 21 13 563 55 47 39 31 23 15 7輸出（64位）初始變換IPL0（32位）R0（32位）21置換碼組 輸入（64位）40 8 48 16 56 24 64 3239 7 47 15 55 23 63 3138 6 46 14 54 22 62 3037 5 45 13 53 21 61 2936 4 44 12 52 20 60 2835 3 43 11 51 19 59 273

9、4 2 42 10 50 18 58 2633 1 41 9 49 17 57 25輸出（64位）逆初始變換IP-122 DES加解密過程令i表示迭代次數(shù)，表示逐位模2求和，f為加密函數(shù)。DES的加密和解密過程表示如下。加密過程：L0R0=IP(64bits明文) Li=Ri-1; Ri=Li-1 f(Ri-1,ki);(64bits密文)=IP-1(R16L16)解密過程： L16R16=IP(64bits密文) Ri-1=Li; Li-1=Ri-1 f(Ri-1,ki);(64bits明文)=IP-1(R0L0)23初始置換IP和初始逆置換IP1 24Li-1（32比特）Ri-1（32比特

10、）Li（32比特）48比特寄存器選擇擴展運算E48比特寄存器子密鑰Ki（48比特）32比特寄存器選擇壓縮運算S置換運算PRi（32比特）Li=Ri-1DES的一輪迭代25左32位右32位Li-1Ri-1擴展48位(明文)64位密鑰作第i次迭代的計算子密鑰Ki48位(密鑰)8組6位碼S1S2S8模2加選擇函數(shù)輸入：6位輸出：4位2632位置換32位LiRi左32位右32位Ri-1Li-1乘積變換中的一次迭代271234567891011.29303132321234545678989101112131213141516171617181920212021222324252425262728292

11、8293032321Ebox選擇擴展運算28選擇壓縮運算29S-Box-i30S-Box-ii31S-Box對每個盒，6比特輸入中的第1和第6比特組成的二進制數(shù)確定的行，中間4位二進制數(shù)用來確定的列。其中相應(yīng)行、列位置的十進制數(shù)的4位二進制數(shù)表示作為輸出。例如的輸入為101001，則行數(shù)和列數(shù)的二進制表示分別是11和0100，即第3行和第4列，其中的第3行和第4列的十進制數(shù)為3，用4位二進制數(shù)表示為0011，所以的輸出為0011。 32 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 150 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 71 0

12、 15 7 4 14 2 13 1 10 6 12 11 9 5 3 82 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 03 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13S10 0 1 0輸入6位：101100輸出4位使用選擇函數(shù)S1的例子0110331234567891011.29303132Pbox1672021291228171152326518311028241432273919133062211425Pbox置換34子密鑰的產(chǎn)生3557 49 41 33 25 17 9 1 58 50 42 34 26 1810 2 59 5

13、1 43 35 2719 11 3 60 52 44 3663 55 47 39 31 33 15 7 62 54 46 38 30 2214 6 61 53 45 37 2921 13 5 28 20 12 4置換選擇1密鑰（64位）C0(28位)D0(28位)36Ci(28位)Di(28位)14 17 11 24 1 5 3 28 15 6 21 1023 19 12 4 26 816 7 27 20 13 241 52 31 37 47 5530 40 51 45 33 4844 49 39 56 34 5346 42 50 36 29 32Ki(48位)置換選擇237置換選擇1（PC-

14、1）和置換選擇2（PC-2） 38對DES的討論F函數(shù)(S-Box)設(shè)計原理未知密鑰長度的爭論DES的破譯 弱密鑰與半弱密鑰39S-Box問題1976年美國NSA提出了下列幾條S盒的設(shè)計準則：1. S盒的每一行是整數(shù)0，15的一個置換2. 沒有一個S盒是它輸入變量的線性函數(shù)3.改變S盒的一個輸入位至少要引起兩位的輸出改變4.對任何一個S盒和任何一個輸入X，S（X）和S(X001100）至少有兩個比特不同（這里X是長度為6的比特串）40S-Box問題5.對任何一個S盒，對任何一個輸入對e,f屬于0,1,S(X) S(X11ef00)6. 對任何一個S盒，如果固定一個輸入比特，來看一個固定輸出比特

15、的值，這個輸出比特為0的輸入數(shù)目將接近于這個輸出比特為1的輸入數(shù)目。41密鑰長度關(guān)于DES算法的另一個最有爭議的問題就是擔心實際56比特的密鑰長度不足以抵御窮舉式攻擊，因為密鑰量只有 個 早在1977年，Diffie和Hellman已建議制造一個每秒能測試100萬個密鑰的VLSI芯片。每秒測試100萬個密鑰的機器大約需要一天就可以搜索整個密鑰空間。他們估計制造這樣的機器大約需要2000萬美元。 在CRYPTO93上，Session和Wiener給出了一個非常詳細的密鑰搜索機器的設(shè)計方案，這個機器基于并行運算的密鑰搜索芯片，所以16次加密能同時完成。此芯片每秒能測試5000萬個密鑰，用5760個

16、芯片組成的系統(tǒng)需要花費10萬美元，它平均用1.5天左右就可找到DES密鑰。421997年1月28日，美國的RSA數(shù)據(jù)安全公司在RSA安全年會上公布了一項“秘密密鑰挑戰(zhàn)”競賽，其中包括懸賞1萬美元破譯密鑰長度為56比特的DES。美國克羅拉多洲的程序員Verser從1997年2月18日起，用了96天時間，在Internet上數(shù)萬名志愿者的協(xié)同工作下，成功地找到了DES的密鑰，贏得了懸賞的1萬美元。1998年7月電子前沿基金會（EFF）使用一臺25萬美圓的電腦在56小時內(nèi)破譯了56比特密鑰的DES。1999年1月RSA數(shù)據(jù)安全會議期間，電子前沿基金會用22小時15分鐘就宣告破解了一個DES的密鑰。

17、43DES的破譯1990年，以色列密碼學家Eli Biham和Adi Shamir提出了差分密碼分析法，可對DES進行選擇明文攻擊。線性密碼分析比差分密碼分析更有效 441.弱密鑰與半弱密鑰弱密鑰: EKEK = I，DES存在4個弱密鑰451.弱密鑰與半弱密鑰半弱密鑰: EK1=EK2，至少有12個半弱密鑰46DES設(shè)計原理重復交替使用選擇函數(shù)S和置換運算P兩種變換（confusion + diffusion)使用Feistel方法+K1+K2+Kn472.對DES的S盒疑義 算法的公開性與脆弱性DES的兩個主要弱點：密鑰容量：56位不太可能提供足夠的安全性S盒：可能隱含有陷井（Hidden

18、 trapdoors）DES的半公開性：S盒的設(shè)計原理至今未公布(3) DES的有效密鑰位數(shù)和迭代次數(shù)缺陷 48DES算法存在的問題與挑戰(zhàn)強力攻擊：255次嘗試差分密碼分析法：247次嘗試線性密碼分析法：243次嘗試49對DES攻擊結(jié)果及其啟示1997年1月28日美國RSA數(shù)據(jù)安全公司懸賞“秘密密鑰挑戰(zhàn)”競賽48位的RC5 313小時/3500臺計算機1997年3月13日Rocke Verser設(shè)計一個攻擊程序（DESCHALL），參加的志愿者有78516個，第96天（6月17日晚10：39）Michael Sanders破譯成功，獲1萬美圓獎金。搜索量為24.6%。50密鑰長度(bit)窮舉

19、時間4078秒485 小時5659天6441年7210，696年802，738，199年88700，978，948年96179，450，610，898年11211，760，475，235，863，837年128770，734，505，057，572，442，069年DESCHALL搜索速度估算51雙重 DES C = EK2(EK1(P) P = DK1(DK2(C)52雙重 DES安全性中間相會(meet-in-the-middle)攻擊 C = EK2(EK1(P) X = EK1(P) = DK2(C)給定明文密文對(P,C) 對所有256個密鑰,加密P,對結(jié)果排序 對所有256個密鑰,

20、解密C,對結(jié)果排序 逐個比較,找出K1,K2使得EK1(P) = DK2(C)一個明文密文對,誤警次數(shù)2112/264=248兩個明文密文對,誤警次數(shù)248/264=2-1653三重 DESC=EK3(DK2(EK1(P) P=DK1(EK2( DK3(C)54三重 DES分析With two keys: C=EK1(DK2(EK1(P)256可選擇明文256次計算 With three keys: C=EK3(DK2(EK1(P)比two-key更安全Tripe DES速度慢55多重DESDES是否構(gòu)成一個閉合群? 任給K1,K2,是否存在K3,使得:EK1EK2 = EK3Double D

21、ESTriple DES56國際數(shù)據(jù)加密IDEA（InternationalData Encryption Algorithm)算法1990年瑞士聯(lián)邦技術(shù)學院的來學嘉和Massey提出，PES，91年修訂，92公布細節(jié). 設(shè)計目標從兩個方面考慮 加密強度 易實現(xiàn)性 強化了抗差分分析的能力， PGP57IDEA算法特點58IDEA設(shè)計思想1.得到confusion的途徑 按位異或 以216(65536)為模的加法 以216+1 (65537)為模的乘法 互不滿足分配律、結(jié)合律2.得到diffusion的途徑 乘加(MA)結(jié)構(gòu)3.實現(xiàn)上的考慮 軟件和硬件實現(xiàn)上的考慮59IDEA加密算法60IDEA

22、每一輪61IDEA輸出變換階段62IDEA的子密鑰63AES介紹1997年NIST宣布征集AES算法要求: 與Tripe DES比要快且至少一樣安全,分組128位,密鑰128/192/256位1998年確定第一輪15個候選者1999年確定第二輪五個候選者: MARS, RC6, Rijndael, Serpent, Twofish2000年底Rijndael成為勝利者64Rijndael簡介1.不屬于Feistel結(jié)構(gòu)2.加密、解密相似但不對稱3.支持128/192/256(/32=Nb)數(shù)據(jù)塊大小4.支持128/192/256(/32=Nk)密鑰長度5.結(jié)構(gòu)簡單6.速度快6566676869

23、Rijndael結(jié)構(gòu)SubKeyPlaintext BlockKeyAddSubstitutionShiftrowMixcolumnSubKeyKeyAddFinal RoundSubstitutionShiftrowKeyAddSubKeyPlaintext BlockyesNo70717273747576777879808182838485868788有限域GF(28)(一)字節(jié)b=b7b6b5b4b3b2b1b0看成系數(shù)屬于0,1的多項式: b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0如:A7 10100111 x7+x5+x2+x+1加法: 0,1上加法(等

24、價于按位XOR)乘法: 多項式模乘,模為(11B):m(x) = x8+x4+x3+x+1如: (x7+x6+x+1)(x5+x+1)=x12+x11+x5+x2+1 =x6+x4+x2+x mod (x8+x4+x3+x+1)m(x)不可約89有限域GF(28)(二)對次數(shù)低于8的b(x)(非0),擴展Euclid算法可計算出a(x),c(x)使得: b(x)a(x)+m(x)c(x)=1 b(x)a(x)=1 mod m(x) b-1(x)=a(x) mod m(x)集合0255構(gòu)成有限域GF(28)GF(28)上b(x)乘x(02): 記作xtime(b)xb(x)=b7x8+b6x7+

25、b5x6+b4x5+b3x4+b2x3+b1x2+b0 x若b7為0,則從字節(jié)上看是一個左移位;否則,還需要減去m(x),從字節(jié)上看是與1B作XOR.90有限域GF(28)上多項式4-byte向量GF(28)元素為系數(shù)多項式(4次)加法: 對應(yīng)系數(shù)的加法(XOR)乘法: 多項式模乘, M(x)=x4+1xj mod M(x) = xj mod 4 a(x)= a3x3+a2x2+a1x+a0, b(x)= b3x3+b2x2+b1x+b0 d(x) = a(x)b(x) = d3x3+d2x2+d1x+d0 mod M(x) |d0| |a0 a3 a2 a1| |b0| |d1| |a1 a

26、0 a3 a2| |b1| |d2| = |a2 a1 a0 a3| |b2| |d3| |a3 a2 a1 a0| |b3|xb(x) = b3x4+b2x3+b1x2+b0 x = b2x3+b1x2+b0 x+b3 即按字節(jié)循環(huán)左移位.91Rijndael簡介(續(xù))數(shù)據(jù)/密鑰的矩陣表示a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35k00k01k02k03k10k11k12k13k20k21k22k23k30k31k32k33NrNb=4Nb=6Nb=8Nk=4 10 12 14Nk=6 12

27、 12 14Nk=8 14 14 14Number of rounds92Rijndael: overview首輪前執(zhí)行AddRoundKey(State,RoundKey)Round(State,RoundKey) ByteSub(State);ShiftRow(State);MixColumn(State);AddRoundKey(State,RoundKey); FinalRound(State,RoundKey) ByteSub(State);ShiftRow(State);AddRoundKey(State,RoundKey); 93Rijndael: AddRoundKey按字節(jié)在

28、GF(28)上相加(XOR)a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35k00k01k02k03k04k05k10k11k12k13k14k15k20k21k22k23k24k25k30k31k32k33k34k35=b00b01b02b03b04b05b10b11b12b13b14b15b20b21b22b23b24b25b30b31b32b33b34b3594Rijndael: ByteSubByteSub(S-box)非線性、可逆獨立作用在每個字節(jié)上先取乘法的逆,再經(jīng)過GF(2)上一個仿射

29、變換a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35b00b01b02b03b04b05b10b11b12b13b14b15b20b21b22b23b24b25b30b31b32b33b34b35S-boxaijbij95Rijndael: ShiftRow第一行保持不變,其他行內(nèi)的字節(jié)循環(huán)移位96Rijndael: MixColumn示意圖列作為GF(28)上多項式乘以多項式c(x)模M(x) = x4+197Rijndael: MixColumn多項式c(x) = 03x3+ 01x2+ 01x

30、+ 02M(x) = x4+1=(x2+1)(x2+1)c(x)與模M(x) = x4+1互素b(x)=c(x)a(x) |b0| |02 03 01 01| |a0| |b1| |01 02 03 01| |a1| |b2| = |01 01 02 03| |a2| |b3| |03 01 01 02| |a3|c(x)的逆: 0Bx3+ 0Dx2+ 09x+ 0E98Rijndael: AddRoundKey按字節(jié)在GF(28)上相加a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35k00k01k

31、02k03k04k05k10k11k12k13k14k15k20k21k22k23k24k25k30k31k32k33k34k35=b00b01b02b03b04b05b10b11b12b13b14b15b20b21b22b23b24b25b30b31b32b33b34b3599Rijndael: Key schedule(1)主密鑰生成子密鑰數(shù)組, (Nr+1)*Nb個字Nk=6KeyExpansion(byte Key4*Nk, word WNb*(Nr+1) for(i=0;iNk;i+) Wi=(Key4*i, Key4*i|+1, Key4*i+2, Key4*i+3); for(i

32、=Nk;iNb*(Nr+1);i+) temp=Wi-1; if(i%Nk = 0) temp=ByteSub(temp6KeyExpansion(byte Key4*Nk, word WNb*(Nr+1) for(i=0;iNk;i+) Wi=(Key4*i, Key4*i|+1, Key4*i+2, Key4*i+3); for(i=Nk;iNb*(Nr+1);i+) temp=Wi-1; if(i%Nk = 0) temp=ByteSub(temp8)Rconi/Nk; else if(i%Nk = 4) temp=ByteSub(temp8); Wi=Wi-Nktemp; ; ;Rco

33、ni=(xi, 00 , 00 , 00); xi為GF(28)上的數(shù).101Rijndael: encrypt structureRijndael(State,CipherKey) KeyExpansion(CipherKey, ExpandedKey); AddRoundKey(State, ExpandedKey) For(i=1;iNr;+i) ByteSub(State);ShiftRow(State);MixColumn(State);AddRoundKey(State,ExpandedKey+Nb*i); ByteSub(State); ShiftRow(State); AddRoundKey(State, ExpandedKey+Nb*i); 102Rijndael: decrypt structureAddRoundKey()For(i=1;iNr;+i) ByteSub();ShiftRow();MixColumn();AddRoundKey() ByteSub();ShiftRow();AddRoundKe