信息安全概論第6講

1、信息安全概論第6講2006年3月17日第3章 密碼基礎l突出-概念+算法+作用。l3.1密碼學的基本概念密碼學的基本概念l3.2對稱密碼算法對稱密碼算法 3.1密碼學的基本概念明文密鑰密文脫密加密 密碼編碼學（cryptography） 密碼學（cryptography） 密碼分析學（cryptanalysis）3.1.1密碼編碼對稱密碼系統(tǒng)主要是對信息提供機密性（secrecy）保護，防止敵手在信道上進行竊聽后產生的泄密。對稱密碼系統(tǒng)同時還能保護數(shù)據的完整性（integrity），檢測或恢復敵手對數(shù)據進行的篡改、偽造等破壞。3.1.1密碼編碼定義1 一個對稱密碼系統(tǒng)（Cryptosystem

2、）CS，是一個五元集合CS=M, C, K, e, d，其中： 明文消息空間 ：表示明文消息的集合；密文消息空間 ：表示密文消息的集合；密鑰空間 ：表示密鑰的集合；加密變換 ：表示一個確定的映射脫密變換 ：表示一個確定的映射它滿足下列條件：對于給定的密鑰k，均有對給定的密鑰k，由e和d誘導下列兩個變換也稱為加密/脫密變換。這時，定義1所滿足的條件可以記為 。mM cC kK edcmkCMKe),(: mckMCKd),(: Mmmmkekd,),(,(),(:mkemCMek),(:ckecMCdkmmedkk)(3.1.1密碼編碼通常實用的密碼系統(tǒng)在技術角度上還需要滿足下列三個要求：加、脫

3、密變換e、d對所有密鑰k都有效（防止計算中的阻斷）。密碼系統(tǒng)應易于實現(xiàn)（對任意給定的密鑰k，有高效的加密/脫密計算方法）。1. 密碼系統(tǒng)的安全性僅依賴于密鑰的保密，而不依賴于算法e和d的保密。 密 文c消 息m消 息m發(fā) 送 者Alice接 收 者Bob不 安 全 信 道密 鑰k密 鑰k安 全 信 道攻 擊 者Oscar圖3.2 密碼系統(tǒng)應用參考模型 3.1.2密碼分析唯密文攻擊（ciphertext only attack）： 已知加密方法、明文語言、可能內容，從密文求出密鑰或明文。已知明文攻擊（know-plaintext attack）： 已知加密方法、已知部分明密對，從密文求出密鑰或明

4、文。選擇明文攻擊（chose-plaintext attack）： 已知加密方法，而且破譯者可以把任意（或相當數(shù)量）的明文加密為密文，求密鑰。這對于保護機密性的密碼算法來說，是最強有力的分析方法。選擇密文攻擊（chose-ciphertext attack）： 已知加密方法，而且破譯者可以把任意（或相當數(shù)量）的密文脫密為明文，求密鑰。這對于保護完整性的密碼算法來說，是最強有力的分析方法。3.1.2密碼分析兩個重要概念：絕對安全的（unconditioned secure）。計算上安全（computationally secure）。3.2對稱密碼算法本節(jié)介紹有代表性的分組算法DES、AES和序

5、列算法A5。對其它相關算法僅做簡要的介紹。 3.2.1分組密碼DESDES的明文長度是64 bit，密鑰長度為56 bit，加密后的密文長度也是64 bit（實際中的明文未必恰好是64 bit，所以要經過分組和填充把它們對齊為若干個64 bit的分組，然后逐組進行加密處理。）脫密過程則相反，它首先按照分組進行脫密，然后去除填充信息并進行連接。 DES算法總體流程圖K1K2IPR0L0fR1=L0 f（R0，K1）L1=R0L2=R1L15=R14L16=R15R2=L1 f（R1，K2）R15=L14 f（R14，K15）R16=L15 f（R15，K16）fIP-1K16fOutputInp

6、ut1初始置換IPIP是64個位置的置換，它表示把第58 bit（t58）換到第1個bit位置，把第50 bit（t50）換到第2個bit位置，把第7 bit（t7）換到第64個bit位置。IP58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 462 54 46 38 30 22 14 6 64 56 48 40 32 24 16 857 49 41 33 25 17 9 1 59 51 43 35 27 19 11 361 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7t1 t2 t64 IPt58 t50 t7 I

7、P-1 t1 t2 t642圈函數(shù)323248Li-1LiRi-1擴展變換ES-盒代替P-盒置換RiKi圈函數(shù)原理圖 2圈函數(shù)（1）E變換 32=84 bit 輸入48=86 bit 輸出由輸入32比特按照下圖所示方法擴展，其中有16個比特出現(xiàn)兩次。具體地說輸出的前6比特順次是輸入的第32、1、2、3、4、5比特；輸出的第二個6比特順次是輸入的第4、5、6、7、8、9比特；輸出的第八個6比特順次是輸入的第28、29、30、31、32、1比特。 2圈函數(shù)（2） S-盒 把48比特的數(shù)分成8個6比特的數(shù)，每個6比特查一個S-盒得到4比特的輸出。 48=86 bit 輸入32=84 bit 輸出S-

8、盒2S-盒8S-盒12圈函數(shù)S-盒相當于一張64個4位數(shù)的表，8個S-盒的內容見表3.2。把S-盒看成一個416的矩陣S=(si,j)，其元素取整數(shù)值0-15。給定6比特輸入x=x1 x2 x3 x4 x5 x6，令i= x1 x6+1，j= x2 x3 x4 x5+1，則y= si,j 即為對應的輸出。S114 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 84 1 14 8 13 6 2 11 15 12 9 7 3 10 5 015 12 8 2 4 9 1 7 5 11 3 15 10 0

9、6 13例如S12圈函數(shù)（3）P-盒： 是32個位置的置換，用法和IP類似。P-盒盒16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 253密鑰擴展從64 bit 的帶校驗位的密鑰K（本質上是56 bit密鑰k）中，生成16個48 bit的子密鑰Ki，用于16個圈函數(shù)中：64 bit密鑰（含校驗）PC - 1C0 D0LS164 bit密鑰（含校驗）LS1C1 D1LS2LS2LS16LS16C16 D16 PC-2 K16PC-2K13密鑰擴展（1）PC-1 揀選變換PC-1

10、表示從64 bit中選出56 bit的密鑰k并適當調整比特次序，揀選方法 PC-157 49 41 33 25 17 9 1 58 50 42 34 26 18 10 259 51 43 35 27 19 11 3 60 52 44 36 63 55 47 3931 23 15 7 62 54 46 38 30 22 14 6 61 53 45 3729 21 13 5 28 20 12 43密鑰擴展（2）PC-2 揀選變換PC-1表示從56 bit中選出48 bit的揀選方法 PC-214 17 11 24 1 5 3 28 15 6 21 10 23 19 12 426 8 16 7 27

11、 20 13 2 41 52 31 37 47 55 30 4051 45 33 48 44 49 39 56 34 53 46 42 50 36 29 323密鑰擴展（2）循環(huán)移位 LSi表示對28bit串的循環(huán)左移：當 i=1，2，9，16時，移一位；對其它i，移兩位。當1i16時Ci=LSi (Ci-1)，Di=LSi (Di-1) PC-214 17 11 24 1 5 3 28 15 6 21 10 23 19 12 426 8 16 7 27 20 13 2 41 52 31 37 47 55 30 4051 45 33 48 44 49 39 56 34 53 46 42 50

12、36 29 324脫密脫密是加密的逆變換。其運算與加密相似，但子密鑰的選取次序正好與加密變換相反K1=K16，K16=K1。5DES的安全性 弱密鑰：如果密鑰分成的兩部分（每部分28 bit），分別都是全0或全1，則任一周期（圈函數(shù)）中的子密鑰將完全相同，叫做弱密鑰。此外，如果使圈密鑰只有兩種的叫半弱密鑰。DES算法存在弱密鑰，可能是它的一個弱點。補密鑰：若用X/表示X的補，則：。這可能是一個弱點。密鑰長度：太小，IBM建議用112 bit。差分密碼分析：Eli Biham 與Adi Shamir 1990提出差分密碼分析方法，比窮舉更有效。線性密碼分析：Mitsuru Matsui 于199

13、3年提出線性密碼分析方法。5DES的安全性 1999年使用一百多個CPU，利用并行算法，用23小時左右成功破譯。1999年在互聯(lián)網上，用分割密鑰方法，成功破譯。應該注意到的一個事實是，DES經過了可能是當今最多的分析或攻擊，但未發(fā)現(xiàn)任何結構方面的漏洞。DES算法最終之所以被破譯的關鍵是密鑰的長度問題，用當今計算機處理速度看，56 bit的密鑰對窮搜攻擊已經是太小了一點。所以，后來人們提出的多數(shù)算法把密鑰長度選到80、128 bit甚至256 bit以上。高強度的算法還要求，沒有比窮搜攻擊更加有效的攻擊方案。 3.2.2 三重DES人們認識到DES最大缺陷是使用了短密鑰。為了克服這個缺陷，Tuc

14、hman于1979年提出了三重DES，使用了168bit的長密鑰。1985年成為金融應用標準（見ANSI X9.17），1999年并入美國國家標準與技術研究局NIST的數(shù)據加密標準（見FIPS PUB 46-3）。三重DES，記為TDES使用三倍DES的密鑰長度的密鑰，執(zhí)行3次DES算法，如果把密鑰記為(k1, k2, k3)，則TDES的加密次序是：相應地脫密次序為：這里，m是明文，c是密文，e和d分別為DES的加/脫密算法。所用的加密次序并非是在故弄玄虛，主要是考慮到和已有系統(tǒng)的兼容。巧妙之處在于，當取k1= k2= k3=k時，TDES則退化成普通的DES。FIPS PUB 46-3規(guī)定

15、TDES的另一種使用方式是假定k1 = k3，這時TDES可用于密鑰長度是112bit的數(shù)據加密。因為TDES的基礎算法是DES，它和DES具有相同的對抗密碼分析的能力，同時， 168bit的長密鑰又能有效地抵抗窮搜攻擊。(m)(e(dec123kkk(c)(d(edm321kkk3.2.3 AES盡管TDES在強度上滿足了當時商用密碼的要求，但隨著計算速度的提高和密碼分析技術的不斷進步，造成了人們對DES的擔心。另一方面，DES是針對集成電路實現(xiàn)設計的，對于在計算機系統(tǒng)和智能卡中的實現(xiàn)不大適合，限制著其應用范圍。在上世紀90年代NIST通過詳細論證最終發(fā)起了在全世界范圍內征集DES替代算法標準的活動。其幾個重要階段是：1997.1 發(fā)起征集高級加密標準（AES）的活動；1998.8 接受15個侯選算法；1999.8 選出5個：MARS、RC6、Rijndael、Serpent、Twofish；2000.10 評選結束，宣布Rijndael 最終獲勝。 按照AES算法的設計要求，它應具有下列基本特點：可變密鑰長為128、192、256三種；可變分