信息安全原理及應(yīng)用 第3章對稱密碼體制

1、主要內(nèi)容,分組密碼數(shù)據(jù)加密標(biāo)準(zhǔn)DES高級加密標(biāo)準(zhǔn)AES序列密碼其他對稱加密算法,概述,對稱密碼體制就是在加密和解密是用到的密鑰相同，或者加密密鑰和解密密鑰之間存在著確定的轉(zhuǎn)換關(guān)系。對稱密碼體制又有兩種不同的實現(xiàn)方式，即分組密碼和序列密碼（或稱流密碼）。,流密碼與分組密碼,流密碼每次加密數(shù)據(jù)流中的一位或一個字節(jié)。分組密碼，就是先把明文劃分為許多分組，每個明文分組被當(dāng)作一個整體來產(chǎn)生一個等長（通常）的密文分組。通常使用的是64位

2、或128位分組大小。分組密碼的實質(zhì)，是設(shè)計一種算法，能在密鑰控制下，把n比特明文簡單而又迅速地置換成唯一n比特密文，并且這種變換是可逆的（解密）。,分組密碼,分組密碼算法實際上就是在密鑰的控制下，簡單而迅速地找到一個置換，用來對明文分組進(jìn)行加密變換，一般情況下對密碼算法的要求是：分組長度m足夠大（64~128比特）密鑰空間足夠大（密鑰長度64~128比特）密碼變換必須足夠復(fù)雜（包括子密鑰產(chǎn)生算法）,分組密碼的設(shè)計思想,擴(kuò)散(di

3、ffusion) 將明文及密鑰的影響盡可能迅速地散布到較多個輸出的密文中。產(chǎn)生擴(kuò)散的最簡單方法是通過“置換(Permutation)”（比如：重新排列字符）。混淆(confusion)其目的在于使作用于明文的密鑰和密文之間的關(guān)系復(fù)雜化，是明文和密文之間、密文和密鑰之間的統(tǒng)計相關(guān)特性極小化，從而使統(tǒng)計分析攻擊不能奏效。通常的方法是“代換（Substitution)”（回憶愷撒密碼）。,DES(Data Encryption Stan

4、dard),美國國家標(biāo)準(zhǔn)局NBS于1973年5月發(fā)出通告，公開征求一種標(biāo)準(zhǔn)算法用于對計算機(jī)數(shù)據(jù)在傳輸和存儲期間實現(xiàn)加密保護(hù)的密碼算法。 1975 年美國國家標(biāo)準(zhǔn)局接受了美國國際商業(yè)機(jī)器公司IBM 推薦的一種密碼算法并向全國公布，征求對采用該算法作為美國信息加密標(biāo)準(zhǔn)的意見。經(jīng)過兩年的激烈爭論，美國國家標(biāo)準(zhǔn)局于1977年7月正式采用該算法作為美國數(shù)據(jù)加密標(biāo)準(zhǔn)。1980年12月美國國家標(biāo)準(zhǔn)協(xié)會正式采用這個算法作為美國的商用加密算法。,DE

5、S的實質(zhì),DES是一種對稱密碼體制，它所使用的加密和解密密鑰是相同的，是一種典型的按分組方式工作的密碼。其基本思想是將二進(jìn)制序列的明文分成每64bit一組，用長為64bit(56bit)的密鑰對其進(jìn)行16輪代換和置換加密，最后形成密文。,DES的基本加密流程,加密前，先將明文分成64bit的分組，然后將64bit二進(jìn)制碼輸入到密碼器中，密碼器對輸入的64位碼首先進(jìn)行初始置換，然后在64bit主密鑰產(chǎn)生的16個子密鑰控制下進(jìn)行16 輪乘積

6、變換，接著再進(jìn)行末置換就得到64位已加密的密文。,DES 算法的一般描述,,0.子密鑰產(chǎn)生器,密鑰（64bit）,除去第8，16，… ，64位，共8個校驗位,,置換選擇1（PC-1）,Ci（28bit）,,,Di（28bit）,循環(huán)左移ti+1位,循環(huán)左移ti+1位,,,置換選擇2（PC-2）,,,,Ki（48bit）,,,,,,,置換選擇1,,移位次數(shù)表,若 C1= c1c2…c28，D1= d1d2…d28 則 C2=

7、c2c3…c28 c1， D2= d2d3…d28 d1。,置換選擇2,置換選擇PC-2將C中第9 18 22 25位和 D 中第7 9 15 26位刪去，并將其余數(shù)字置換位置后送出48bit數(shù)字作為第i次迭代時所用的子密鑰ki,Ci Di= b1b2…b56 ，則ki= b14 b17 b11 b24…b36 b29 b32,1.初始置換,將64個明文比特的位置進(jìn)行置換，得到一個亂序的64bit明文組，然后分成左右兩段，每段為32bi

8、t 以L和R表示。,2.乘積變換,Li-1(32比特),Ri-1(32比特),選擇擴(kuò)展運算E,48比特寄存器,子密鑰Ki(48比特),48比特寄存器,選擇壓縮運算S,32比特寄存器,置換運算P,Li(32比特),,,,,,,,,,,,,Ri(32比特),,,,,Li=Ri-1,Ri=Li-1 F(Ri-1,Ki),,選擇擴(kuò)展運算E,對原第 32 1 4 5 8 9 12 13 16 17 20 21 24 25 28 29

9、 各位重復(fù)一次得到數(shù)據(jù)擴(kuò)展。,選擇壓縮運算S,將前面送來的48bit 數(shù)據(jù)自左至右分成8組，每組6bit。然后并行送入8個S盒，每個S盒為一非線性代換網(wǎng)絡(luò)，有4個輸出。,S盒的內(nèi)部結(jié)構(gòu),S盒的內(nèi)部計算,若輸入為b1b2b3b4b5b6其中b1b6兩位二進(jìn)制數(shù)表達(dá)了0至3之間的數(shù)。b2b3b4b5為四位二進(jìn)制數(shù)，表達(dá)0至15之間的某個數(shù)。在S1表中的b1b6行b2b3b4b5列找到一數(shù)m（0≤m≤15），若用二進(jìn)制表示為m1m2m3m4

10、，則m1m2m3m4便是它的4bit輸出。 例如，輸入為001111，b1b6=01=1，b2b3b4b5 =0111=7，即在S1盒中的第1行第7列求得數(shù)1，所以它的4bit輸出為0001。,關(guān)于S盒,S 盒是DES的核心，也是DES算法最敏感的部分，其設(shè)計原理至今仍諱莫如深，顯得非常神秘。所有的替換都是固定的，但是又沒有明顯的理由說明為什么要這樣，有許多密碼學(xué)家擔(dān)心美國國家安全局設(shè)計S盒時隱藏了某些陷門，使得只有他們才可以破譯算法

11、，但研究中并沒有找到弱點。,置換運算P,對S1至S8盒輸出的32bit 數(shù)據(jù)進(jìn)行坐標(biāo)變換 置換P輸出的32bit數(shù)據(jù)與左邊32bit即Ri-1諸位模2相加所得到的32bit作為下一輪迭代用的右邊的數(shù)字段，并將Ri-1并行送到左邊的寄存器作為下一輪迭代用的左邊的數(shù)字段。,3.逆初始置換IP-1,將16輪迭代后給出的64bit組進(jìn)行置換得到輸出的密文組,,,DES的解密,解密算法與加密算法相同，只是子密鑰的使用次序相反。,DES的安全性,

12、DES在20多年的應(yīng)用實踐中，沒有發(fā)現(xiàn)嚴(yán)重的安全缺陷，在世界范圍內(nèi)得到了廣泛的應(yīng)用，為確保信息安全做出了不可磨滅的貢獻(xiàn)。存在的安全弱點：密鑰較短：56位密鑰空間約為7.2*1016。1997年6月Rocke Verser小組通過因特網(wǎng)利用數(shù)萬臺微機(jī)歷時4個月破譯了DES；1998年7月，EFF用一臺25萬美元的機(jī)器，歷時56小時破譯DES。存在弱密鑰：有的密鑰產(chǎn)生的16個子密鑰中有重復(fù)者?；パa對稱性：C=DES(M,K),則C’

13、=DES(M’,K’)，其中，M’,C’,K’是M,C,K的非。,DES具有良好的雪崩效應(yīng),雪崩效應(yīng)：明文或密鑰的微小改變將對密文產(chǎn)生很大的影響。特別地，明文或密鑰的某一位發(fā)生變化，會導(dǎo)致密文的很多位發(fā)生變化。DES顯示了很強(qiáng)的雪崩效應(yīng)兩條僅有一位不同的明文，使用相同的密鑰，僅經(jīng)過3輪迭代，所得兩段準(zhǔn)密文就有21位不同。一條明文，使用兩個僅一位不同的密鑰加密，經(jīng)過數(shù)輪變換之后，有半數(shù)的位都不相同。,多重DES,DES在窮舉攻擊下相

14、對比較脆弱，因此需要用某種算法來替代它，有兩種解決方法：設(shè)計全新的算法；用DES進(jìn)行多次加密，且使用多個密鑰，即多重DES。這種方法能夠保護(hù)用于DES加密的已有軟件和硬件繼續(xù)使用。,二重DES(Double DES),給定明文P和兩個加秘密鑰k1和k2，采用DES對P進(jìn)行加密E，有 密文 C=EK2(EK1(P))

15、 對C進(jìn)行解密D，有 明文 P=DK1(DK2(C)),E,E,,,,,,,P,X,C,K2,K1,加密圖,D,D,,,,,,K2,K1,C,X,P,解密圖,二重DES很難抵擋住中間相遇攻擊法（Meet-in-the-Middle Attack) C=EK2(EK1(P))從圖中可見 X=EK1(P)=

16、DK2(C),若給出一個已知的明密文對（P,C)做：對256個所有密鑰K1做對明文P的加密，得到一張密鑰對應(yīng)于密文X的一張表；類似地對256個所有可能的密鑰K2做對密文C的解密，得到相應(yīng)的“明文”X。做成一張X與K2的對應(yīng)表。比較兩個表就會得到真正使用的密鑰對K1,K2。,帶有雙密鑰的三重DES（Triple DES with Two Keys),Tuchman給出雙密鑰的EDE模式（加密-解密-加密）： C=

17、EK1(DK2(EK1(P))) ……對P加密 P=DK1(EK2(DK1(C))) ……對C解密 這種替代DES的加密較為流行并且已被采納用于密鑰管理標(biāo)準(zhǔn)（The Key Manager Standards ANSX9.17和ISO8732).,E,D,E,D,E,D,,,,,,,,,,,,,,,C,B,A,P,P,A,B,,C,K1,K2,K1,K1,K2,K1,加密圖,解密圖,到目前

18、為止，還沒有人給出攻擊三重DES的有效方法。對其密鑰空間中密鑰進(jìn)行蠻干搜索，那么由于空間太大為2112=5×1033，這實際上是不可行的。注意：1*. Merkle和Hellman設(shè)法創(chuàng)造一個條件，想把中間相遇攻擊（meet-in-the-middle attack）的方法用于三重DES，但目前也不太成功。2*. 雖然對上述帶雙密鑰的三重DES到目前為止還沒有好的實際攻擊辦法，但人們還是放心不下，又建議使用三密鑰的三重D

19、ES，此時密鑰總長為168bits. C=EK3(DK2(EK1(P))),高級加密標(biāo)準(zhǔn)AES,,,,1997年1月，美國國家標(biāo)準(zhǔn)局NIST向全世界密碼學(xué)界發(fā)出征集21世紀(jì)高級加密標(biāo)準(zhǔn)（AES——Advanced Encryption Standard）算法的公告，并成立了AES標(biāo)準(zhǔn)工作研究室，1997年4月15日的例會制定了對AES的評估標(biāo)準(zhǔn)。,AES的要求,（1）AES是公開的；（2）AES為單鑰體制分

20、組密碼；（3）AES的密鑰長度可變，可按需要增大；（4）AES適于用軟件和硬件實現(xiàn)；（5）AES可以自由地使用，或按符合美國國家標(biāo)準(zhǔn)（ANST）策略的條件使用；,算法衡量條件,滿足以上要求的AES算法，需按下述條件判斷優(yōu)劣a. 安全性b. 計算效率c. 內(nèi)存要求d. 使用簡便性e. 靈活性。,AES的評審,,,,1998年4月15日全面征集AES算法的工作結(jié)束。1998年8月20日舉行了首屆AES討論會，對涉及14個國家

21、的密碼學(xué)家所提出的候選AES算法進(jìn)行了評估和測試，初選并公布了15個被選方案，供大家公開討論。 CAST-256， RC-6， CRYPTON-128，DEAL-128， FROG， DFC， LOKI-97， MAGENTA， MARS， HPC, RIJNDAEL， SA

22、FER+， SERPENT， E-2， TWOFISH。這些算法設(shè)計思想新穎，技術(shù)水平先進(jìn)，算法的強(qiáng)度都超過3-DES，實現(xiàn)速度快于3-DES。,AES的評審,1999年8月9日NIST宣布第二輪篩選出的5個候選算法為： MARS(C.Burwick等,IBM）， RC6TM（R. Rivest等,RSA Lab.)， RIJNDEAL(J. Daemen

23、,比)， SERPENT(R. Anderson等，英、以、挪威)， TWOFISH(B. Schiener)。2000年10月2日，NIST宣布Rijndael作為新的AES,AES加密數(shù)學(xué)基礎(chǔ),群:是一個代數(shù)系統(tǒng)，它由一個非空集合組成，在集合上定義了一個二元運算，其滿足：封閉性：對任意的 ， ；結(jié)合律：對任何的 ，有

24、 ；單位元：存在一個元素 (稱為單位元)，對任意元素有： ；逆元：對任意 ，存在一個元素 (稱為逆元)，使得 。記作：,,,,,,,,,,,交換群與有限群,若群還滿足交換律，即對任何

25、 ，有： ，則稱為交換群(或加法群，阿貝爾群等)。若集合G中只含有有限多個元素，則我們稱 為有限群，此時，把集合G中元素的個數(shù)稱為有限群的階。,,,,群的性質(zhì),群中的單位元是惟一的；消去律成立，即對任意的 ：如果 ，則 如果 ，則 群中的每一元素的逆元是惟一的。,,,域,域是一個代數(shù)

26、系統(tǒng)，它由一個(至少包含兩個元素的)非空集合F組成，在集合F上定義有兩個二元運算：加法與乘法，并滿足下面條件： F的元素關(guān)于加法成交換群，記其單位元為“0”(稱為域的零元) F關(guān)于乘法成交換群，記其單位元為“1”(稱其為域的單位元) 乘法在加法上滿足分配律，即 記為,,,,有限域,若集合F只包含有限個元素，則稱這個域F為有限域。有限域中元素的個數(shù)稱為該有限域的階。若有一任意的素數(shù)P和正整數(shù) ，存在

27、 階有限域，這個有限域記為 。當(dāng) n=1時，有限域 稱為素域。,,,,,GF(28)域上的多項式表示及運算,一個字節(jié)的 元素的二進(jìn)制展開成的多項式系數(shù)為：例如， 上的“37”(為十六進(jìn)制)，其二進(jìn)制為“00110111”，對應(yīng)多項式為：,,,,,GF(28)4域上的多項式表示及運算,一個四個字節(jié)的字(有32比特位)可以看作是域

28、 上的多項式，每個字對應(yīng)于一個次數(shù)小于4的多項式。 兩個 域上的元素相加時，將這兩個元素對應(yīng)多項式系數(shù)相加即得到結(jié)果，相加時采用比特異或來實現(xiàn)。兩個 域上的元素相乘時，要將結(jié)果對一個特定的多項式取模，以使相乘后的結(jié)果還是一個4字節(jié)的向量。,,,,,,,AES加密算法的具體實現(xiàn),AES每輪要經(jīng)過四次變換，分別是 字節(jié)代換運算(SubByte ()) ShiftRows

29、()(行移位)變換 MixColumns()（列混合）變換 AddRoundKey() (輪密鑰的混合)變換 我們用的128bit的密鑰（循環(huán)次數(shù)為10），那么每次加密的分組長為128bit，16個字節(jié)，每次從明文中按順序取出16個字節(jié)假設(shè)為a0a1a2a3a4a5a6a7a8a9a10a11a12a13a14a15，這16個字節(jié)在 進(jìn)行變換前先放到一個4×4的矩陣中。如下頁圖所示：,這個矩陣稱為狀態(tài)

30、（state）,以后所有的變換都是基于這個矩陣進(jìn)行的，到此，準(zhǔn)備工作已經(jīng)完成。現(xiàn)在按照前面的順序進(jìn)行加密變換，首先開始第一次循環(huán)的第一個變換：字節(jié)代換(SubByte ())。,字節(jié)代換(SubByte ()),,查表,字節(jié)代換-S盒變換(查表),S12={53},則X=5, Y=3, out9=ed,,ShiftRows()(行移位)變換,,,,,,,,,,,,,,,,行變換示意圖,S,S′,MixColumns()（列混合）變換,

31、S’0c＝({02} ● S0c)⊕({03} ● S1c)⊕ S2c⊕S3c，但這個結(jié)果可能會超出一個字節(jié)的存儲范圍，所以實際上還要對結(jié)果進(jìn)行處理。,3.4 序列密碼 (流密碼),“一次一密”密碼在理論上是不可攻破的。流密碼則由“一次一密”密碼啟發(fā)而來。流密碼目前的理論已經(jīng)比較成熟，工程實現(xiàn)也比較容易，加密效率高，在許多重要領(lǐng)域得到應(yīng)用?！耙淮我幻堋泵艽a使用的密鑰是和明文一樣長的隨機(jī)序列，密鑰越長越安全，但長密鑰的存儲、分配都很

32、困難。,流密碼的密鑰流,流密碼的關(guān)鍵就是產(chǎn)生密鑰流的算法，該算法必須能夠產(chǎn)生可變長的、隨機(jī)的、不可預(yù)測的密鑰流。保持通信雙方的精確同步是流密碼實際應(yīng)用中的關(guān)鍵技術(shù)。由于通信雙方必須能夠產(chǎn)生相同的密鑰流，所以這種密鑰流不可能是真隨機(jī)序列，只能是偽隨機(jī)流。,,明文流,密文流,密鑰流,,,,,流密碼的結(jié)構(gòu),典型的流密碼每次加密一位或一個字節(jié)明文。將初始密鑰(種子)輸入到發(fā)生器，輸出一個隨機(jī)數(shù)(密鑰)。,偽隨機(jī)字節(jié)發(fā)生器(密鑰流發(fā)生器)

33、,,明文字節(jié)流M,,,密文字節(jié)流C,密鑰K,,,k,異或加密,,偽隨機(jī)字節(jié)發(fā)生器(密鑰流發(fā)生器),,,,密鑰K,,,k,異或解密,明文字節(jié)流M,11001100 明文01101100 密鑰流10100000 密文,,,設(shè)計流密碼需要考慮的因素,密鑰流的周期要長。偽隨機(jī)數(shù)發(fā)生器產(chǎn)生的并非完全隨機(jī)的序列，它是一個產(chǎn)生確定的比特流的函數(shù)，該比特流最終將產(chǎn)生重復(fù)。重復(fù)的周期越長，相當(dāng)于密鑰越長，密碼分析也就越

34、困難。密鑰流應(yīng)盡可能地接近于一個真正的隨機(jī)數(shù)流的特征。例如1和0的個數(shù)應(yīng)大致相同。密鑰流越隨機(jī)，加密所得的密文也越隨機(jī)，分析就越困難。偽隨機(jī)數(shù)發(fā)生器的輸出取決于輸入的密鑰的值。,RC4流密碼,RC4是Ron Rivest為RSA公司在1987年設(shè)計的一種流密碼。它是一種可變密鑰長度、面向字節(jié)操作的流密碼。RC4可能是應(yīng)用最廣泛的流密碼用于SSL/TLS(安全套接字/傳輸層安全協(xié)議)用于IEEE802.1無線局域網(wǎng)中的WEP協(xié)

35、議。,RC4算法,輸入：一個256個字節(jié)的表示0---255的狀態(tài)矢量S、密鑰K(長度為kenlen)輸出：密鑰字節(jié)流*初始化*For i=0 to 255 doS[i]=i;T[i]=K[i mod keylen]; //臨時矢量T(256字節(jié))*置換*j=0;For i=0 to 255 doj=(j+S[i]+T[i]) mod 256; Swap(S[i], S[j]);

36、 //S仍然包含所有值為0到255的元素,*密鑰流的生成*i=0,j=0;While(true)i=(i+1) mod 256;j=(j + S[i]) mod 256;swap(S[i],S[j]);t=(S[i]+S[j]) mod 256;k=S[t];加密中，將k的值與下一明文字節(jié)異或；解密中，將k的值與下一密文字節(jié)異或。,精品課件！,精品課件！,其他對稱密碼,IDEA由旅居瑞士的華人來學(xué)嘉和他的導(dǎo)

37、師J.L. Massey共同開發(fā)的。IDEA使用128位密鑰，明文和密文分組長度為64位。已被用在多種商業(yè)產(chǎn)品中。CLIPPER密碼采用SKIPJACK算法，明文和密文分組長度為64位，密鑰長度為80位。BlowfishBlowfish允許使用最長為448位的不同長度的密鑰，并針對在32位處理器上的執(zhí)行進(jìn)行了優(yōu)化。TwofishTwofish使用128位分組，可以使用128、192或256位密鑰。CAST-128CAST