密碼算法與應(yīng)用基礎(chǔ)

1、二、對(duì)稱密鑰密碼密碼算法與應(yīng)用基礎(chǔ)1信息安全引論對(duì)稱密鑰密碼對(duì)稱密鑰密碼應(yīng)用基礎(chǔ)公開密鑰密碼數(shù)字簽名與Hash函數(shù)公開密鑰密碼應(yīng)用基礎(chǔ)密鑰交換與密鑰管理內(nèi)容提要2對(duì)稱密鑰密碼概述 古典密碼 Feistel結(jié)構(gòu) DES Some post DES algorithms 分組密碼工作模式 Rijndael 整理發(fā)布3加密與解密加密與解密 加密: E: (X,K) Y, y = E(x,k) 固定k,Ek:X Y Ek是單值映射, Ek(x1) != Ek(x2) if x1 != x2 Ek逆映射解密,記為Dk : Y X 許多時(shí)候,YX,這樣可以執(zhí)行多次加密: EkEk.Ek 4密碼分類密碼系統(tǒng)

2、的幾種分類按執(zhí)行的操作 替換(substitution)與換位(permutation)按密鑰的數(shù)量 單密鑰(對(duì)稱密鑰)與雙密鑰(公開密鑰)按明文處理方式 流密碼(stream cipher)與分組密碼(block cipher)5密碼分析密碼分析(破譯)Ciphertext only 已知: CiphertextKnown plaintext(已知明文攻擊) 已知: 部分明文密文對(duì)Chosen plaintext(選擇明文攻擊) 可以選擇任意明文并得到對(duì)應(yīng)的密文Chosen ciphertext(選擇密文攻擊) 可以選擇部分密文并得到對(duì)應(yīng)的明文6密碼算法的安全性密碼算法的安全性Uncondi

3、tionally secure無(wú)論破譯者有多少密文,他也無(wú)法解出對(duì)應(yīng)的明文,即使他解出了,他也無(wú)法驗(yàn)證結(jié)果的正確性.Onetime padComputationally secure破譯的代價(jià)超出信息本身的價(jià)值;破譯的時(shí)間超出了信息的有效期.7關(guān)于對(duì)稱密碼.關(guān)于對(duì)稱密碼.歷史悠久經(jīng)驗(yàn)比例大理論結(jié)果少算法復(fù)雜 破譯的代價(jià)或者時(shí)間難于準(zhǔn)確估計(jì)密鑰長(zhǎng)度數(shù)據(jù)塊大小8古典密碼Substitution Monoalphabetic cipher Playfair cipher Hill cipher Vigenre cipher Onetime pad Transposition 小結(jié) 9Monoalph

4、abetic cipherCaesar cipher E(p) = (p+3) mod 26 abcdefghijklmnopqrstuvwxyz DEFGHIJKLMNOPQRSTUVWXYZABC 例子: crypt = FUBSW任意的單表替換密碼 abcdefghijklmnopqrstuvwxyz SDVJKLTIOXCFAWQZUPYREGHBNM 例子: crypt = VPNZR10單表替換密碼的破譯密鑰空間為26! 4 * 1026通過字母的使用頻率破譯11Playfair cipher55變換矩陣: I與J視為同一字符C R Y P TO G A H BD E F I K

5、(cryptography)L M N Q SU V W X Z加密規(guī)則:按成對(duì)字母加密 成對(duì)重復(fù)字母加分隔符(如x) balloon ba lx lo on 同行取右邊: rt YC 同列取下邊:fw NY 其他取交叉:ly NC, GK BE12Playfair cipher-例子以前面的55變換矩陣(cryptography)為例:C R Y P TO G A H BD E F I KL M N Q SU V W X ZExamples looklo okUD BD fillfi lx lxIK QU QU jigsawjx ig sa wxQP EH NB XZ cryptocr yp

6、 toRY PT CB13Playfair cipher-小結(jié)Playfair有26*26種字母對(duì)組合字符出現(xiàn)幾率一定程度上被均勻化基于字母頻率的攻擊比較困難依然保留了相當(dāng)?shù)慕Y(jié)構(gòu)信息 14Hill cipher基于矩陣的線性變換: C = KPK是一個(gè)m*m矩陣,在Z26上可逆,即存在K-1使得:KK-1 = I (在Z26上) 17 17 05 04 09 15 K = 21 18 21 K-1 = 15 17 06 02 02 19 24 00 17完全隱藏了字符(對(duì))的頻率線性變換的安全性很脆弱15Vigenre cipher多表代換密碼一個(gè)單代換表的集合密鑰決定何時(shí)使用哪個(gè)單表Vige

7、nre cipher使用Caesar密碼作為基礎(chǔ)單代換表集合: EK(P) = (K-a)+P mod 26(子)密鑰與明文一樣長(zhǎng)16Vigenre cipher-例子EK(P) = (K-a)+P mod 26 a b c d e f g h i j k l m 000102 030405 060708 091011 12 n o p q r s t u v w x y z 131415 161718 192021 222324 25key: cryptographycryptographycrplain: yourpackagereadyroomathreecipher:AFSGIOI17

8、Vigenre cipher-破譯依然保留了字符頻率某些統(tǒng)計(jì)信息間距是密鑰長(zhǎng)度整數(shù)倍子串有相同密文: a b c d e f g h i j k l m 000102 030405 060708 091011 12 n o p q r s t u v w x y z 131415 161718 192021 222324 25key: cryptographycryptographycrplain: yourpackagereadyroomathreecipher:AFSGIOI PG PG18Onetime padVigenre本人建議密鑰與明文一樣長(zhǎng)Gillbert Vernam建議密鑰與

9、明文一樣長(zhǎng)并且沒有統(tǒng)計(jì)特性: Ci = Pi Ki進(jìn)一步的改進(jìn)是使用完全隨機(jī)的串作為密鑰: Onetime pad密鑰的交換與保管十分困難加密的信息有長(zhǎng)度限制19Transposition換位密碼把明文按列寫入,按行讀出密鑰包含3方面信息: 行寬,列高,讀出順序key: 4 3 1 2 5 6 7plaintext: a t t a c k p o s t p o n e d u n t i l t w o a m x y zciphertext:TTNAAPTMTSUOAODWCOIXPETZ完全保留字符的統(tǒng)計(jì)信息使用多輪加密可提高安全性20古典密碼小結(jié)Substitution & perm

10、utation密碼分析多輪加密數(shù)據(jù)安全基于算法的保密21分組密碼設(shè)計(jì)要求Diffusion(彌散) 密文沒有統(tǒng)計(jì)特征，明文一位影響密文的多位，密鑰的一位也影響密文的多位Confusion(混淆) 明文與密文、密鑰與密文的依賴關(guān)系充分復(fù)雜結(jié)構(gòu)簡(jiǎn)單、易于分析22Feistel結(jié)構(gòu)圖23Feistel結(jié)構(gòu)定義加密: Li = Ri-1; Ri = Li-1F(Ri-1,Ki)解密: Ri-1 = Li Li-1 = RiF(Ri-1,Ki) = RiF(Li,Ki)24Feistel結(jié)構(gòu)分析Block size(64 128)Key size(56 128256)Number of rounds(1

11、6)Subkey generation Round function(F)Fast software encryption/decryptionEasy hardware implementationSimple structureEase of analysis25DESDES概述DES結(jié)構(gòu)詳解 DES安全性分析 多重DES 26Some post DES algorithmsIDEA BlowfishRC5CAST-12827分組密碼工作模式Electronic Codebook Mode Cipher Block Chaining Mode Cipher Feedback Mode Ou

12、tput Feedback Mode 28AES介紹1997年NIST宣布征集AES算法要求: 與Tripe DES比要快且至少一樣安全,分組128位,密鑰128/192/256位1998年確定第一輪15個(gè)候選者1999年確定第二輪五個(gè)候選者: MARS, RC6, Rijndael, Serpent, Twofish2000年底R(shí)ijndael成為勝利者29有限域GF(28)(一)字節(jié)b=b7b6b5b4b3b2b1b0看成系數(shù)屬于0,1的多項(xiàng)式: b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0如:A7 10100111 x7+x5+x2+x+1加法: 0,1上加法

13、(等價(jià)于按位XOR)乘法: 多項(xiàng)式模乘,模為(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)不可約30有限域GF(28)(二)對(duì)次數(shù)低于8的b(x)(非0),擴(kuò)展Euclid算法可計(jì)算出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+b6x

14、7+b5x6+b4x5+b3x4+b2x3+b1x2+b0 x若b7為0,則從字節(jié)上看是一個(gè)左移位;否則,還需要減去m(x),從字節(jié)上看是與1B作XOR.31有限域GF(28)上多項(xiàng)式4-byte向量GF(28)元素為系數(shù)多項(xiàng)式(4次)加法: 對(duì)應(yīng)系數(shù)的加法(XOR)乘法: 多項(xiàng)式模乘, 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

15、 a0 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)左移位.32Rijndael簡(jiǎn)介不屬于Feistel結(jié)構(gòu)加密、解密相似但不對(duì)稱支持128/192/256(/32=Nb)數(shù)據(jù)塊大小支持128/192/256(/32=Nk)密鑰長(zhǎng)度結(jié)構(gòu)簡(jiǎn)單速度快33Rijndael簡(jiǎn)介(續(xù))數(shù)據(jù)/密鑰的矩陣表示a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31

16、a32a33a34a35k00k01k02k03k10k11k12k13k20k21k22k23k30k31k32k33NrNb=4Nb=6Nb=8Nk=4 10 12 14Nk=6 12 12 14Nk=8 14 14 14Number of rounds34Rijndael: overview首輪前執(zhí)行AddRoundKey(State,RoundKey)Round(State,RoundKey) ByteSub(State);ShiftRow(State);MixColumn(State);AddRoundKey(State,RoundKey); FinalRound(State,Rou

17、ndKey) ByteSub(State);ShiftRow(State);AddRoundKey(State,RoundKey); 35Rijndael: AddRoundKey按字節(jié)在GF(28)上相加(XOR)a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35k00k01k02k03k04k05k10k11k12k13k14k15k20k21k22k23k24k25k30k31k32k33k34k35=b00b01b02b03b04b05b10b11b12b13b14b15b20b21b22b2

18、3b24b25b30b31b32b33b34b3536Rijndael: ByteSubByteSub(S-box)非線性、可逆獨(dú)立作用在每個(gè)字節(jié)上先取乘法的逆,再經(jīng)過GF(2)上一個(gè)仿射變換a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35b00b01b02b03b04b05b10b11b12b13b14b15b20b21b22b23b24b25b30b31b32b33b34b35S-boxaijbij37Rijndael: ShiftRow第一行保持不變,其他行內(nèi)的字節(jié)循環(huán)移位38Rijndael

19、: MixColumn示意圖列作為GF(28)上多項(xiàng)式乘以多項(xiàng)式c(x)模M(x) = x4+139Rijndael: MixColumn多項(xiàng)式c(x) = 03x3+ 01x2+ 01x+ 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+ 0E40Rijndael: AddRoundK

20、ey按字節(jié)在GF(28)上相加a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35k00k01k02k03k04k05k10k11k12k13k14k15k20k21k22k23k24k25k30k31k32k33k34k35=b00b01b02b03b04b05b10b11b12b13b14b15b20b21b22b23b24b25b30b31b32b33b34b3541Rijndael: Key schedule(1)主密鑰生成子密鑰數(shù)組, (Nr+1)*Nb個(gè)字Nk=6KeyExpansion(b

21、yte 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(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

22、 = 0) temp=ByteSub(temp8)Rconi/Nk; else if(i%Nk = 4) temp=ByteSub(temp8); Wi=Wi-Nktemp; ; ;Rconi=(xi, 00 , 00 , 00); xi為GF(28)上的數(shù).43Rijndael: encrypt structureRijndael(State,CipherKey) KeyExpansion(CipherKey, ExpandedKey); AddRoundKey(State, ExpandedKey) For(i=1;iNr;+i) ByteSub(State);ShiftRow(State

23、);MixColumn(State);AddRoundKey(State,ExpandedKey+Nb*i); ByteSub(State); ShiftRow(State); AddRoundKey(State, ExpandedKey+Nb*i); 44Rijndael: decrypt structureAddRoundKey()For(i=1;iNr;+i) ByteSub();ShiftRow();MixColumn();AddRoundKey() ByteSub();ShiftRow();AddRoundKey() I_AddRoundKey()I_ShiftRow();I_Byt

24、eSub();For(i=1;iNr;+i) I_AddRoundKey()I_MixColumn();I_ShiftRow();I_ByteSub();I_AddRoundKey() I_AddRoundKey()For(i=1;iNr;+i) I_ShiftRow();I_ByteSub();I_AddRoundKey() I_MixColumn();I_ShiftRow();I_ByteSub();I_AddRoundKey()45Rijndael安全性沒有發(fā)現(xiàn)弱密鑰或補(bǔ)密鑰能抵抗已知的密碼分析手段46DES示意圖47DES: single roundLi = Ri-1 Ri = Li-

25、1F(Ri-1,Ki)48DES: Function FExpansion: 32 48 S-box: 6 4 Permutation: 49DES: Subkey generation50DES安全性分析差分密碼分析 線性密碼分析 密鑰短窮舉破譯 字典攻擊 F函數(shù)(S-Box)設(shè)計(jì)原理未知 輪數(shù)問題弱密鑰與半弱密鑰 小結(jié)51多重DESDES是否構(gòu)成一個(gè)閉合群? 任給K1,K2,是否存在K3,使得:EK1EK2 = EK3Double DES Triple DES 52DES: Expansion table32 | 01 02 03 04 | 0504 | 05 06 07 08 | 090

26、8 | 09 10 11 12 | 1312 | 13 14 15 16 | 1716 | 17 18 19 20 | 2120 | 21 22 23 24 | 2524 | 25 26 27 28 | 2928 | 29 30 31 32 | 0153DES: S-box(S1)14 04 13 01 02 15 11 08 03 10 06 12 05 09 00 0700 15 07 04 14 02 13 01 10 06 12 11 09 05 03 0804 01 14 08 13 06 02 11 15 12 09 07 03 10 05 0015 12 08 02 04 09

27、01 07 05 11 03 14 10 00 06 1354DES: Permutation16 07 20 21 29 12 28 1701 15 23 26 05 18 31 1002 08 24 14 32 27 03 0919 13 30 06 22 11 04 2555DES: 差分密碼分析破解DES: 247個(gè)選擇明文(255個(gè)已知明文)破解Lucifer(18輪128位): 24個(gè)選擇明文221次計(jì)算DES對(duì)差分密碼分析的抵抗力很強(qiáng)56DES: 線性密碼分析破解DES: 243個(gè)已知明文DES對(duì)線性密碼分析的抵抗力稍弱57DES: 窮舉破譯DES密鑰長(zhǎng)度: 56位, 25610

28、17計(jì)算機(jī)能力為100MIPS次(108)/秒,1萬(wàn)臺(tái)計(jì)算機(jī)協(xié)同工作一天，計(jì)算能力為:108*10000*24*360010171017/1017 = 1天58DES: 字典攻擊考慮選擇明文攻擊DES塊大小: 64位, 2641020計(jì)算機(jī)能力為100MIPS(108)/秒,1萬(wàn)臺(tái)計(jì)算機(jī)協(xié)同工作一天，計(jì)算能力為:108*10000*24*360010171020/1017 = 1000天適用于任意64位塊的加密59DES: S-box設(shè)計(jì)準(zhǔn)則S-box是DES的核心(全部非線性所在) S-box每行是015的一個(gè)置換 S-box輸出不是輸入的線性或者放射變換 S-box輸入一位改變, 輸出至少

29、二位改變 S(x)與S(x001100)至少二位不同 S(x) != S(x00ef00), 對(duì)任意e,f0,1 固定一位,其它五位變化,輸出數(shù)字中的0和1的總數(shù)接近相等60DES: 弱密鑰與半弱密鑰弱密鑰: EKEK = I半弱密鑰: EK1 = EK2不影響安全性互補(bǔ)性: 若y=DESk(x),則把x,y,k都取補(bǔ),等式仍然成立.61Double DES C = EK2(EK1(P) P = DK1(DK2(C)62Double DES安全性中間相會(huì)(meet-in-the-middle)攻擊 C = EK2(EK1(P) X = EK1(P) = DK2(C)給定明文密文對(duì)(P,C) 對(duì)

30、所有256個(gè)密鑰,加密P,對(duì)結(jié)果排序 對(duì)所有256個(gè)密鑰,解密C,對(duì)結(jié)果排序 逐個(gè)比較,找出K1,K2使得EK1(P) = DK2(C)一個(gè)明文密文對(duì),誤警次數(shù)2112/264=248兩個(gè)明文密文對(duì),誤警次數(shù)248/264=2-1663Triple DESC=EK3(DK2(EK1(P) P=DK1(EK2( DK3(C)64Triple DES分析With two keys: C=EK1(DK2(EK1(P)256可選擇明文256次計(jì)算 With three keys: C=EK3(DK2(EK1(P)比two-key更安全Tripe DES速度慢65Electronic Codebook