《對稱密碼體制》PPT課件.ppt

1、第2章 對稱密碼體制,主講內(nèi)容 1.分組密碼的一般設(shè)計原理 2.DES數(shù)據(jù)加密標準 3.AES加密算法,QUIZE TIME,1.古典密碼的兩個基本操作：、。維吉尼亞密碼是采用什么操作？斯巴達的金腰帶的密鑰是什么？ 2.密碼體制分為、 3. 公鑰密碼體制的兩個密鑰是否相同？ 4.對稱密鑰密碼體制的密鑰是否相同？,對稱密鑰算法,對稱算法就是加密密鑰能夠從解密密鑰中推算出來，反過來也成立。在大多數(shù)對稱算法中，加/解密密鑰是相同的。這些算法也叫秘密密鑰算法或單密鑰算法，它要求發(fā)送者和接收者在安全通信之前，商定一個密鑰。對稱算法的安全性依賴于密鑰，泄漏密鑰就意味著任何人都能對消息進行加/解密。,對稱算

2、法序列密碼,序列密碼的主要原理是，通過偽隨機序列發(fā)生器產(chǎn)生性能優(yōu)良的偽隨機序列，使用該序列加密信息流，（逐比特加密）得到密文序列，所以，序列密碼算法的安全強度完全決定于偽隨機序列的好壞。 序列密碼算法將明文逐位轉(zhuǎn)換成密文。密鑰流發(fā)生器輸出一系列比特流：K1，K2，K3，Ki。密鑰流跟明文比特流P1，P2，P3，Pi ，進行異或運算產(chǎn)生密文比特流。 Ci =PiKi 在解密端，密文流與完全相同的密鑰流異或運算恢復出明文流。 Pi =CiKi,序列密碼,基于移位寄存器的序列密碼應用十分廣泛。一個反饋移位寄存器由兩部分組成：移位寄存器和反饋函數(shù)。移位寄存器的長度用位表示，如果是n位長，稱為n位移位寄

3、存器。移位寄存器每次向右移動一位，新的最左邊的位根據(jù)反饋函數(shù)計算得到，移位寄存器輸出的位是最低位。最簡單的反饋移位寄存器是線形反饋移位寄存器，反饋函數(shù)是寄存器中某些位簡單異或。,對稱算法序列密碼,序列密碼的主要原理是，通過偽隨機序列發(fā)生器產(chǎn)生性能優(yōu)良的偽隨機序列，使用該序列加密信息流，（逐比特加密）得到密文序列，所以，序列密碼算法的安全強度完全決定于偽隨機序列的好壞。 序列密碼算法將明文逐位轉(zhuǎn)換成密文。密鑰流發(fā)生器輸出一系列比特流：K1，K2，K3，Ki。密鑰流跟明文比特流P1，P2，P3，Pi ，進行異或運算產(chǎn)生密文比特流。 Ci =PiKi 在解密端，密文流與完全相同的密鑰流異或運算恢復出

4、明文流。 Pi =CiKi,對稱算法分組密碼要求,（1）分組長度應足夠大。使得不同明文分組的個數(shù)足夠大，以防讓明文被窮學法攻擊。新的算法標推般要求M128。 (2)密鑰空間應足夠大，盡可能消除弱密鑰，從而使所有密鑰同等概率，以防災學密鑰攻擊。同時，密鑰不能太長，以利于密鑰管理。DES采用56比特有效密鑰，現(xiàn)在看來顯然不夠長。今后一段時間內(nèi)，128比特密鑰應該是足夠安全的。,對稱算法分組密碼要求,(3)由密鑰確定的算法要足夠復雜，充分實現(xiàn)明文與密鑰的擴散和混淆，沒有簡單關(guān)系可循，要能抵抗各種已知的攻擊，如差分攻擊和線性攻擊等；另外，還要求有較高的非線性階數(shù)。 (4)軟件實現(xiàn)的要求：盡量使用適合編

5、程的子塊和簡單的運算。密碼運算在于塊上進行，要求子塊的長度能適應軟件編程，如8、16、32比特等。應盡量避免按比特置換 。,怎么樣滿足 分組密碼要求,Shannon在1949的論文中介紹了一個新思想：通過“乘積”來組合密碼體制。所謂乘積密碼就是采用m個函數(shù)（密碼）f1,f2,fm的復合，其中每個fi可能是一個代換或置換。Shannon建議交替使用代換和置換兩種方法，即他稱之為混亂（confusion）和擴散（diffusion）的過程，破壞對密碼系統(tǒng)進行的各種統(tǒng)計分析。這種思想在現(xiàn)代密碼體制的設(shè)計中十分重要，深刻影響著數(shù)據(jù)加密標準DES、高級數(shù)據(jù)加密標準AES的設(shè)計。,Shannon的新思想：

6、 “乘積”,擴散，就是將明文的統(tǒng)計特性迅速散布到密文中去，實現(xiàn)方式是使得明文的每一位影響密文中多位的值，即密文中每一位受明文中多位影響；將密鑰的每位數(shù)字盡可能擴散到更多個密文數(shù)字中去，以防止對密鑰進行逐段破譯。根據(jù)擴散原則，分組密碼應設(shè)計成明文的每個比特與密鑰的每個比特對密文的每個比特都產(chǎn)生影響。,Shannon的新思想： “乘積”,混亂的目的在于使明文和密文之間的統(tǒng)計關(guān)系變得盡可能復雜。使用復雜的非線形代換算法可得預期的混淆效果 。 常見的乘積密碼是迭代密碼。典型的迭代密碼定義了一個輪函數(shù)和一個密鑰編排方案，對明文的加密將經(jīng)過多輪迭代。 設(shè)K是一個定長的主密鑰，密碼編排方案用K生成Nr輪個輪

7、密鑰（子密鑰）Ki。輪函數(shù)g以輪密鑰Ki和當前狀態(tài)wi-1作為輸入。 初始狀態(tài)w0=x，明文x，密文y，經(jīng)過所有Nr輪后的狀態(tài)wNr。加密過程是： w0=x wi=g（wi-1, Ki） i = 1,2, Nr 解密過程是： wNr=y wi-1=g-1（wi, Ki） i = Nr,Nr-1,1,Feistel網(wǎng)絡(luò)的結(jié)構(gòu),Feistel提出利用乘積密碼可獲得簡單的代換密碼，乘積密碼指順序地執(zhí)行多個基本密碼系統(tǒng)，使得最后結(jié)果的密碼強度高于每個基本密碼系統(tǒng)產(chǎn)生的結(jié)果。取一個長度為n的分組（n為偶數(shù)），然后把它分為長度為n/2的兩部分：L和R。定義一個迭代的分組密碼算法，其第i輪的輸出取決于前一輪

8、的輸出，F(xiàn)eistel網(wǎng)絡(luò)的結(jié)構(gòu)如下圖：,Feistel網(wǎng)絡(luò)結(jié)構(gòu)圖,SP網(wǎng)絡(luò)結(jié)構(gòu),奧利奧 漢堡在哪里,數(shù)據(jù)加密標準（Data Encryption Standard,DES),背景,發(fā)明人：美國IBM公司 W. Tuchman 和 C. Meyer 1971-1972年研制成功 基礎(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ù)加密標準（D

9、ata Encryption Standard），于1977年7月15日生效,背景,美國國家安全局（NSA, National 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ù)加密的國際標準工作,DES概述,分組加密算法：明文和密文為64位分組長度 對稱算法：加密和解密除密鑰編排不同外，使用同

10、一算法 密鑰長度：56位，但每個第8位為奇偶校驗位，可忽略 密鑰可為任意的56位數(shù)，但存在弱密鑰，容易避開 采用混亂和擴散的組合，每個組合先替代后置換，共16輪 只使用了標準的算術(shù)和邏輯運算，易于實現(xiàn),DES加密算法的一般描述,DES加密過程,DES加解密過程,Ek（m） = IP-1T16T15T1IP（m）。其中IP為初始置換，IP-1是IP的逆，Ti，i = 1，2，16是一系列的變換。 解密算法為m=Ek-1 Ek（m）= IP-1T1T2T16IPEk（m）。,DES中的各種置換、擴展和替代,初始置換IP和初始逆置換IP1,IP和IP1,IP,IP1,DES的 一輪迭代,擴展置換-盒

11、32位擴展到48位,擴展,壓縮替代S-盒48位壓縮到32位,共8個S盒,S-盒1,S-盒2,S-盒3,S-盒4,S-盒5,S-盒6,S-盒7,S-盒8,S-盒的構(gòu)造,S-盒的構(gòu)造,DES中其它算法都是線性的，而S-盒運算則是非線性的 S-盒不易于分析，它提供了更好的安全性 所以S-盒是算法的關(guān)鍵所在,S-盒的構(gòu)造準則,S盒的每一行是整數(shù)0，15的一個置換 沒有一個S盒是它輸入變量的線性函數(shù) 改變S盒的一個輸入位至少要引起兩位的輸出改變 對任何一個S盒和任何一個輸入X，S（X）和 S(X001100）至少有兩個比特不同（這里X是長度為6的比特串） 對任何一個S盒，對任何一個輸入對e,f屬于0,1

12、,S(X) S(X11ef00) 對任何一個S盒，如果固定一個輸入比特，來看一個固定輸出比特的值，這個輸出比特為0的輸入數(shù)目將接近于這個輸出比特為1的輸入數(shù)目,S-盒的構(gòu)造要求,S-盒是許多密碼算法的唯一非線性部件,因此,它的密碼強度決定了整個算法的安全強度 提供了密碼算法所必須的混亂作用 如何全面準確地度量S-盒的密碼強度和設(shè)計有效的S-盒是分組密碼設(shè)計和分析中的難題 非線性度、差分均勻性、嚴格雪崩準則、可逆性、沒有陷門,置換p-盒的構(gòu)造,p-盒的構(gòu)造準則,P置換的目的是提供雪崩效應 明文或密鑰的一點小的變動都引起密文的較大變化,DES中的子密鑰的生成,密鑰置換算法的構(gòu)造準則,設(shè)計目標：子密

13、鑰的統(tǒng)計獨立性和靈活性 實現(xiàn)簡單 速度 不存在簡單關(guān)系：( 給定兩個有某種關(guān)系的種子密鑰,能預測它們輪子密鑰之間的關(guān)系) 種子密鑰的所有比特對每個子密鑰比特的影響大致相同 從一些子密鑰比特獲得其他的子密鑰比特在計算上是難的 沒有弱密鑰,DES的 一輪迭代,DES加密算法的一般描述,多重DES,兩重DES,三重DES,Quize time 5 minutes,1.DES是對稱密鑰加密算法還是公鑰加密算法？是分組密碼還是序列密碼？ 2. DES有效密鑰長度位，分組長度位，3DES有效密鑰長度位？ 3. DES用于加密消息還是傳遞密鑰？相對于公鑰，加密速度快還是慢？ 4.序列密碼比分組密碼安全高還是

14、低？ 5. DES是否有弱密鑰？ 6. DES是在古典密碼基本操作基礎(chǔ)上，通過乘積實現(xiàn)的，對嗎？,DES的安全性,F函數(shù)(S-Box)設(shè)計原理未知 密鑰長度的爭論 DES的破譯 弱密鑰與半弱密鑰,破譯DES,1990年，以色列密碼學家Eli Biham和Adi Shamir提出了差分密碼分析法，可對DES進行選擇明文攻擊,差分密碼分析(Differential cryptanalysis),DES經(jīng)歷了近20年全世界性的分析和攻擊，提出了各種方法，但破譯難度大都停留在255量級上。 1991年Biham和Shamir公開發(fā)表了差分密碼分析法才使對DES一類分組密碼的分析工作向前推進了一大步。目

15、前這一方法是攻擊迭代密碼體制的最佳方法，它對多種分組密碼和Hash 函數(shù)都相當有效，相繼攻破了FEAL、LOKI、LUCIFER等密碼。 此法對分組密碼的研究設(shè)計也起到巨大推動作用。,差分密碼分析(Differential cryptanalysis),差分密碼分析是一種攻擊迭代分組密碼的選擇明文統(tǒng)計分析破譯法。 它不是直接分析密文或密鑰的統(tǒng)計相關(guān)性，而是分析明文差分和密文差分之間的統(tǒng)計相關(guān)性。 給定一個r輪迭代密碼，對已知n長明文對X和X，定義其差分為 X=X(X)-1 其中，表示n-bits組X的集合中定義的群運算，(X)-1為X在群中的逆元。,易受攻擊的位置,電話公司 市話局,接線盒,D

16、ES用軟件進行解碼需要用很長時間，而用硬件解碼速度非常快，但幸運的是當時大多數(shù)黑客并沒有足夠的設(shè)備制造出這種硬件設(shè)備。 在1977年，人們估計要耗資兩千萬美元才能建成一個專門計算機用于DES的解密，而且需要12個小時的破解才能得到結(jié)果。所以，當時DES被認為是一種十分強壯的加密方法。,1997年開始，RSA公司發(fā)起了一個稱作“向DES挑戰(zhàn)”的競技賽。 1997年1月，用了96天時間，成功地破解了用DES加密的一段信息； 一年之后，在第二屆賽事上，這一記錄41天 ；1998年7月， “第2-2屆DES挑戰(zhàn)賽（DES Challenge II-2）” 把破解DES的時間縮短到了只需56個小時； “

17、第三屆DES挑戰(zhàn)賽（DES Challenge III）”把破解DES的時間縮短到了只需22.5小時 。,三重DES 解決其密鑰長度問題的方法，即采用三重DES。這種方法用兩個密鑰對明文進行三次加密，假設(shè)兩個密鑰是K1和K2，其算法的步驟： 1. 用密鑰K1進行DES加密。 2. 用K2對步驟1的結(jié)果進行DES解密。 3. 用步驟2的結(jié)果使用密鑰K1進行DES加密 缺點：花費原來三倍時間 優(yōu)點：112位密鑰長度，很“強壯”的加密方式,第2節(jié) AES的起源,1997年9月，NIST征集AES方案，以替代DES。 1999年8月，以下5個方案成為最終候選方案：MARS, RC6, Rijndael

18、, Serpent, Twofish。 2000年10月，由比利時的Joan Daemen和Vincent Rijmen提出的算法最終勝出。（ Rijndael 讀成Rain Doll。） http:/www.esat.kuleuven.ac.be/rijmen/rijndael/,2. AES的設(shè)計原則,能抵抗所有已知的攻擊； 在各種平臺上易于實現(xiàn)，速度快； 設(shè)計簡單。,Rijndael是一個分組密碼算法，其分組長度和密鑰長度相互獨立，都可以改變。,表 1. 分組長度和密鑰長度的不同取值,3. AES 算法的一般描述,Rijndael Round的構(gòu)成,字節(jié)代替,行移位,列混合,+,輪密鑰,

19、一般的輪變換,字節(jié)代替,行移位,+,輪密鑰,最后一輪的輪變換,3. AES 算法加密部分的實現(xiàn),明文分組和密鑰的組織排列方式,Fig 1. 以明文分組為128bits為例組成的陣列,Fig 2. 以明文分組（或密鑰）為128bits、192bits 、256bits為例組成的陣列,狀態(tài)（State）：密碼運算的中間結(jié)果稱為狀態(tài)。 State的表示：狀態(tài)用以字節(jié)為基本構(gòu)成元素的矩陣陣列來表示，該陣列有4行，列數(shù)記為Nb。 Nb=分組長度（bits） 32 Nb可以取的值為4，6，8，對應的分組長度為128， 192， 256 bits。 密碼密鑰（Cipher Key）的表示： Cipher K

20、ey類似地用一個4行的矩陣陣列來表示，列數(shù)記為Nk。 Nk=密鑰長度（bits）32 Nk可以取的值為4，6，8，對應的密鑰長度為128， 192， 256 bits。,Fig 3. 當Nb=6時的狀態(tài)和Nk=4時的密鑰布局,Nb = 6 Block Length = 192 bits,Nk = 4 Key Length = 128 bits,Fig 4. 分組長度和密鑰長度均為128 bits時的Rijndael加密算法框圖,Data / Key Addition,Rnd 0,Rnd 1,Rnd 8,Final Rnd,Key Schedule,Cipher Text,Key,Plain T

21、ext,表 2. 輪數(shù)（Round）的不同取值,Rijndael 之所為能當選AES ,主要是因為: (1) 運算速度快，軟硬件實現(xiàn)都表現(xiàn)出非常好的性能； (2) 對內(nèi)存的需求非常低,很適合于受限制的環(huán)境下； (3) 算法可靠，使用非線性結(jié)構(gòu)S盒,有足夠的安全性； (4) 該 算法能有效抵抗差分分析和線性分析攻擊； (5) Rijndael 是一個分組迭代密碼,被設(shè)計成128/ 192/256 比特三種密鑰長度,可用于加密長度為128/ 192/ 256 比特的分組,相應的輪數(shù)為10/ 12/ 14 ,分組長度和密鑰長度設(shè)計靈活。 (6) 密鑰安裝的時間很好, 具有很高的靈活性。,這個矩陣稱為

22、狀態(tài) （state）,以后所有的變換都是基于這個矩陣進行的，到此，準備工作已經(jīng)完成?，F(xiàn)在按照前面的順序進行加密變換，首先開始第一次循環(huán)的第一個變換：字節(jié)代換(SubByte ()。,字節(jié)代換(SubByte (),查表,根據(jù)其S1,1的值用兩位十六進制數(shù)表示，第一位為行號X，第二位作為列號Y，對S盒進行查表作為對應的輸出。,字節(jié)代換-S盒變換(查表),S12=53,則X=5, Y=3, out9=ed,ShiftRows()(行移位)變換,行變換示意圖,S,S,（列混合）變換：AXS=S形式。,MixColumns()（列混合）變換,S0c(02 S0c)(03 S1c) S2cS3c，但這個

23、結(jié)果可能會超出一個字節(jié)的存儲范圍，所以實際上還要對結(jié)果進行處理。,輪密鑰的添加,AddRoundKey(),輪密鑰的添加,AES 的密鑰調(diào)度 密鑰調(diào)度包括兩個部分：密鑰擴展和輪密鑰選取。,密鑰bit的總數(shù)分組長度（輪數(shù)Round1）例如當分組長度為128bits和輪數(shù)Round為10時，輪密鑰長度為128(101)1408bits。 將密碼密鑰擴展成一個擴展密鑰。 從擴展密鑰中取出輪密鑰：第一個輪密鑰由擴展密鑰的第一個Nb個4字節(jié)字，第二個圈密鑰由接下來的Nb個4字節(jié)字組成，以此類推。,將初始密鑰表示成4X4的矩陣的形式，按列優(yōu)先排列，每一個格子相當于一個字節(jié)，共4X4X8=128bit，其中w0、w1、w2、w3表示初始密鑰，w4、w5、w6、w7表示第二輪擴展后的密鑰，最后一輪是w40、w41、w42、w43。,密鑰擴展,+,+,+,Byte Substitution,ByteRotate,+,Rcon,Wi-4,Wi-3,Wi-2,Wi-1,Wi,Byte Substituion,Byte Rotate,+,Rcons,+,Key expansion,4 = i 4 ( Rnd + 1 ),i mod 4 = 0,i mod 4 != 0,輪密鑰選取,輪密鑰0,輪密鑰1,輪密鑰2,AES的解密算法,解密算法與加密算法不同 每個階段均可逆，因此易證解密函授的確可