信息安全密碼編碼學

1、1信息安全信息安全密碼編碼學密碼編碼學沈志東沈志東武漢大學武漢大學 國際軟件學院國際軟件學院zd_2為什么需要密碼為什么需要密碼n信息的保護信息的保護n信息的存儲：公開的地方信息的存儲：公開的地方n信息的交換：使用非隱秘介質(zhì)信息的交換：使用非隱秘介質(zhì)n信息的傳輸：通過不安全信道信息的傳輸：通過不安全信道n安全機制安全機制n機密性機密性3密碼編碼學密碼編碼學n基本概念和術(shù)語基本概念和術(shù)語n密碼學的歷史密碼學的歷史n密碼技術(shù)密碼技術(shù)4基本概念和術(shù)語基本概念和術(shù)語n加密加密(encryption)n將報文將報文(或消息或消息)進行編碼，以模糊其含義的過程。進行編碼，以模糊其含義的過程。nencode

2、, enciphern解密解密(decryption)n將加密過的報文恢復為原始形式。將加密過的報文恢復為原始形式。ndecode, deciphern明文明文(plaintext)和密文和密文(ciphertext)n報文的原始方式為明文，加密后成為密文報文的原始方式為明文，加密后成為密文5基本概念和術(shù)語基本概念和術(shù)語n密碼編碼學密碼編碼學(cryptography)n研究對信息進行編碼研究對信息進行編碼,實現(xiàn)對信息的隱蔽實現(xiàn)對信息的隱蔽n密碼專家密碼專家(cryptographer)n密碼分析學密碼分析學(cryptanalytics)n研究加密消息的破譯研究加密消息的破譯(break)或

3、消息的偽造或消息的偽造.n密碼破譯者密碼破譯者(cryptanalyst)n密碼學密碼學(cryptology)n研究信息系統(tǒng)安全保密的科學，包括密碼編碼學和研究信息系統(tǒng)安全保密的科學，包括密碼編碼學和密碼分析學密碼分析學6密碼算法的分類密碼算法的分類n按照保密的內(nèi)容分按照保密的內(nèi)容分n受限制的受限制的(restricted)算法：算法的保密性算法：算法的保密性基于保持算法的秘密?；诒３炙惴ǖ拿孛?。n基于密鑰基于密鑰(key-based)的算法：算法的保密的算法：算法的保密性基于對密鑰的保密。性基于對密鑰的保密。7密碼算法的分類密碼算法的分類n按照明文的處理方法分按照明文的處理方法分n分組密

4、碼分組密碼(block cipher)：將明文分成固定：將明文分成固定長度的組，用同一密鑰和算法對每一塊加長度的組，用同一密鑰和算法對每一塊加密，輸出也是固定長度的密文。密，輸出也是固定長度的密文。n流密碼流密碼(stream cipher)：又稱序列密碼，每：又稱序列密碼，每次加密一位或一字節(jié)的明文。次加密一位或一字節(jié)的明文。 8密碼算法的分類密碼算法的分類n按照密鑰使用方法分按照密鑰使用方法分n對稱密碼算法對稱密碼算法(symmetric cipher)：又稱傳：又稱傳統(tǒng)密碼算法統(tǒng)密碼算法(conventional cipher)或秘密密或秘密密鑰算法、單密鑰算法。鑰算法、單密鑰算法。n非

5、對稱密鑰算法非對稱密鑰算法(asymmetric cipher)，又，又稱公開密鑰算法稱公開密鑰算法(public-Key cipher) 。9密碼體制密碼體制加密加密解密解密明文明文P密文密文C明文明文P密鑰密鑰(K)n對稱密碼體制對稱密碼體制(symmetric cryptosystem)n加密密鑰和解密密鑰是相同的加密密鑰和解密密鑰是相同的C=E(K,P)P=D(K, E(K,P)10密碼體制密碼體制加密加密解密解密明文明文P密文密文C明文明文P加密密鑰加密密鑰Ke解密密鑰解密密鑰KdC=E(Ke,P)P=D(Kd, E(Ke,P)n非對稱密碼體制非對稱密碼體制(asymmetric c

6、ryptosystem)n加密密鑰和解密密鑰是成對出現(xiàn)加密密鑰和解密密鑰是成對出現(xiàn)n加密過程和解密過程不同，使用的密鑰也不同加密過程和解密過程不同，使用的密鑰也不同11密碼分析密碼分析n密碼分析學密碼分析學n企圖利用算法的性質(zhì)和明文的一般特性或企圖利用算法的性質(zhì)和明文的一般特性或某些明密文推導出特別的明文或使用的密某些明密文推導出特別的明文或使用的密鑰。鑰。n窮舉攻擊窮舉攻擊n攻擊者對一條密文嘗試所有可能的密鑰，攻擊者對一條密文嘗試所有可能的密鑰，直到得到有意義的明文。直到得到有意義的明文。12密碼的安全性考慮密碼的安全性考慮n無條件安全無條件安全(Unconditionally secure

7、)n無論破譯者有多少密文無論破譯者有多少密文,他也無法解出對應的明文他也無法解出對應的明文,即使他解出了即使他解出了,他也無法驗證結(jié)果的正確性他也無法驗證結(jié)果的正確性.n一次一密一次一密n計算上安全的計算上安全的n破譯密碼的代價超出密文信息的價值破譯密碼的代價超出密文信息的價值n破譯密碼的時間超出密文信息的有效生命期破譯密碼的時間超出密文信息的有效生命期13密碼編碼學密碼編碼學n基本概念和術(shù)語基本概念和術(shù)語n密碼學的歷史密碼學的歷史n密碼技術(shù)密碼技術(shù)14密碼學的發(fā)展史密碼學的發(fā)展史n古代加密方法（手工階段）古代加密方法（手工階段）n古典密碼（機械階段）古典密碼（機械階段）n現(xiàn)代密碼（計算機階段

8、）現(xiàn)代密碼（計算機階段）15古代加密方法古代加密方法n起源于公元前起源于公元前440年出現(xiàn)在古希臘戰(zhàn)年出現(xiàn)在古希臘戰(zhàn)爭中的隱寫術(shù)爭中的隱寫術(shù) (steganography)：通：通過隱藏消息的存在來保護消息。過隱藏消息的存在來保護消息。16古代加密方法古代加密方法n斯巴達人用于加解密的一種軍事設(shè)斯巴達人用于加解密的一種軍事設(shè)備備(Spartan Scytale, 400 B.C.) n發(fā)送者把一條羊皮螺旋形地纏在一個發(fā)送者把一條羊皮螺旋形地纏在一個圓柱形棒上圓柱形棒上n思想：置換（思想：置換（permutation)17古代加密方法古代加密方法n一個叫一個叫Aeneas Tacticus的希臘

9、人在的希臘人在論論要塞的防護要塞的防護一書中對傳輸密文做了最一書中對傳輸密文做了最早的論述。早的論述。n公元前公元前2世紀，一個叫世紀，一個叫Polybius的希臘的希臘人設(shè)計了一種將字母編碼成符號對的方人設(shè)計了一種將字母編碼成符號對的方法，他使用了一個稱為法，他使用了一個稱為Polybius的校驗的校驗表，表中包含許多后來在加密系統(tǒng)中常表，表中包含許多后來在加密系統(tǒng)中常見的方法，如代替與換位。見的方法，如代替與換位。18古典密碼古典密碼n古典密碼的加密方法一般是文字置換，古典密碼的加密方法一般是文字置換，使用手工或機械變換的方式實現(xiàn)。使用手工或機械變換的方式實現(xiàn)。n古典密碼系統(tǒng)已經(jīng)初步體現(xiàn)出

10、近代密碼古典密碼系統(tǒng)已經(jīng)初步體現(xiàn)出近代密碼系統(tǒng)的雛形，它比古代加密方法復雜，系統(tǒng)的雛形，它比古代加密方法復雜，其變化較小。其變化較小。n單表代替密碼：單表代替密碼：Caesar密碼；密碼；n多表代替密碼：多表代替密碼：Vigenere密碼、密碼、Hill密碼；密碼；n轉(zhuǎn)輪密碼：二戰(zhàn)中的轉(zhuǎn)輪密碼：二戰(zhàn)中的Enigma。 19古典密碼古典密碼EngimaTYPEXHagelin C-36 TUNNYHagelin C-48 20現(xiàn)代密碼現(xiàn)代密碼n計算機的發(fā)展使得基于復雜計算的密碼計算機的發(fā)展使得基于復雜計算的密碼成為可能，密碼學成為一門新的學科。成為可能，密碼學成為一門新的學科。n1949年信息論

11、之父年信息論之父C. E. Shannon發(fā)表了發(fā)表了“The Communication Theory of Secret Systems” ，密碼學走上了科學與理性之路，密碼學走上了科學與理性之路n1967年年David Kahn的的The Codebreakersn1971-73年年IBM Watson實驗室的實驗室的Horst Feistel等的幾篇技術(shù)報告等的幾篇技術(shù)報告21現(xiàn)代密碼現(xiàn)代密碼n對稱密鑰密碼算法進一步發(fā)展對稱密鑰密碼算法進一步發(fā)展n1977年年DES正式成為標準正式成為標準n80年代出現(xiàn)年代出現(xiàn)IDEA,RCx,CAST等等n90年代對稱密鑰密碼進一步成熟：年代對稱密鑰

12、密碼進一步成熟：Rijndael, RC6, MARS, Twofish, Serpent等出現(xiàn)等出現(xiàn)n2001年年Rijndael成為成為DES的替代者的替代者,即即AES。22現(xiàn)代密碼現(xiàn)代密碼n公鑰密碼的出現(xiàn)公鑰密碼的出現(xiàn)n1976年年Diffie & Hellman的的“New Directions in Cryptography”提出了公鑰密碼思想。提出了公鑰密碼思想。n1977年年Rivest,Shamir & Adleman提出了提出了RSA公鑰算法公鑰算法n90年代逐步出現(xiàn)橢圓曲線等其他公鑰算法年代逐步出現(xiàn)橢圓曲線等其他公鑰算法n一些新的密碼技術(shù)，如，混沌密碼、量

13、子密一些新的密碼技術(shù)，如，混沌密碼、量子密碼等碼等23密碼編碼學密碼編碼學n基本概念和術(shù)語基本概念和術(shù)語n密碼學的歷史密碼學的歷史n密碼技術(shù)密碼技術(shù)24密碼技術(shù)密碼技術(shù)n對稱加密技術(shù)對稱加密技術(shù)n非對稱加密技術(shù)非對稱加密技術(shù)n消息認證和消息認證和HASH函數(shù)函數(shù)25對稱密碼對稱密碼n傳統(tǒng)加密技術(shù)傳統(tǒng)加密技術(shù)n替換替換 (substitution)：明文中的每一個字符明文中的每一個字符被替換成密文中的另一個字符。接收者對密被替換成密文中的另一個字符。接收者對密文做反向替換就可以恢復出明文。文做反向替換就可以恢復出明文。 n置換置換 (permutation)，又稱換位，又稱換位(transpos

14、ition)：明文的字母保持相同，但打：明文的字母保持相同，但打亂排列的順序。亂排列的順序。26替換密碼替換密碼n簡單替換密碼簡單替換密碼(simple substitution cipher),又又稱單字母密碼稱單字母密碼(monoalphabetic cipher)n明文的一個字符用相應的一個密文字符替換，而明文的一個字符用相應的一個密文字符替換，而且密文所用的字符與一般的明文所用字符屬同一且密文所用的字符與一般的明文所用字符屬同一語言系統(tǒng)。語言系統(tǒng)。n多字母密碼多字母密碼(ployalphabetic cipher)n明文中的字符映射到密文空間的字符還依賴于它明文中的字符映射到密文空間的

15、字符還依賴于它在上下文中的位置。在上下文中的位置。27替換密碼替換密碼單字母替換單字母替換nCaesar密碼密碼n加密：加密：ci = E(pi) = (pi + 3) mod 26n解密：解密： pi = E(ci) = (ci - 3) mod 26A B C D E F G H I J K L M N O P Q R S T U V W X Y ZD E F G H I J K L M N O P Q R S T U V W X Y Z A B C字母字母編碼編碼treaty impossiblewuhdwb lpsrvvleoh明文明文密文密文28替換密碼替換密碼單字母替換單字母替換n

16、一般的愷撒密碼一般的愷撒密碼n加密：加密：ci = E(pi) = (pi + k) mod 26n解密：解密： pi = E(ci) = (ci - k) mod 26n其中其中k為密鑰，為密鑰，1 k 25n一般的愷撒密碼的破譯分析一般的愷撒密碼的破譯分析n已知加密和解密算法已知加密和解密算法n需要測試的密鑰只有需要測試的密鑰只有25個個n明文所用的語言是已知的，且其意義易于識別。明文所用的語言是已知的，且其意義易于識別。n可以采用窮舉攻擊可以采用窮舉攻擊29替換密碼替換密碼單字母替換單字母替換n使用密鑰的愷撒密碼使用密鑰的愷撒密碼n使用密鑰使用密鑰k控制字母表中的排列控制字母表中的排列n

17、密文空間增加密文空間增加(26!)A B C D E F G H I J K L M N O P Q R S T U V W X Y Zw o r d A B C E F G H I J K L M N P Q R S T U V X Y Z字母字母編碼編碼密鑰為密鑰為wordn單表替換密碼單表替換密碼n每條消息用一個字母表（給出從明文字母到密文每條消息用一個字母表（給出從明文字母到密文字母的映射）加密字母的映射）加密30替換密碼替換密碼單字母替換單字母替換n單字母替換的破譯單字母替換的破譯語言的統(tǒng)計特語言的統(tǒng)計特性性n語言的頻率特征語言的頻率特征n連接特征連接特征n重復特征重復特征31替換密

18、碼替換密碼單字母替換單字母替換英文單字母的相對頻率表英文單字母的相對頻率表32替換密碼替換密碼單字母替換單字母替換n頻率特征頻率特征n雙字母：雙字母：TH HE IN ER AN RE ED ON ES ST EN AT TO NT HA ND OU EA NG AS OR TI IS ET IT AR TE SE HI OFn三字母：三字母： THE ING AND HER ERE ENT THA NTH WAS ETH FOR DTH HAT SHE ION INT HIS STH ERS VERn一半的單詞以一半的單詞以e s d t 結(jié)尾結(jié)尾n一半的單詞以一半的單詞以t a s w 開

19、頭開頭nY的使用頻率的使用頻率90%都集中在單詞的結(jié)尾都集中在單詞的結(jié)尾33替換密碼替換密碼單字母替換單字母替換nPlayfair密碼密碼多表多表n1854年由英國科學家年由英國科學家Charles Wheatstone發(fā)明。發(fā)明。n將明文中的雙字母音節(jié)作為一個單元并將其轉(zhuǎn)換將明文中的雙字母音節(jié)作為一個單元并將其轉(zhuǎn)換成密文的成密文的“雙字母音節(jié)雙字母音節(jié)”。n算法基于一個由密鑰詞構(gòu)成的算法基于一個由密鑰詞構(gòu)成的5 5字母矩陣。字母矩陣。 n例：密鑰詞為例：密鑰詞為monarchy，明文為，明文為balloonn如果該字母對兩個字母相同，則它們之間加一個填充字如果該字母對兩個字母相同，則它們之間

20、加一個填充字母，如母，如x ；則明文分為四個字母對：；則明文分為四個字母對：ba lx lo onn落在矩陣同一行的明文字母對中的字母由其右邊的字母落在矩陣同一行的明文字母對中的字母由其右邊的字母替換；替換；on替換成替換成nan落在矩陣同一列的明文字母對中的字母由其下面的字母落在矩陣同一列的明文字母對中的字母由其下面的字母替換；替換；ba替換成替換成ib(或或jb)n其他的每組明文字母對中的字母如下替換：它所在的行其他的每組明文字母對中的字母如下替換：它所在的行是該字母的所在行，列則為另一個字母的所在列。是該字母的所在行，列則為另一個字母的所在列。 lo替換成替換成pm lx替換成替換成su

21、MONARCHYBDEFGI/JKLPQSTUVWXZ密文為：密文為：ibsupmna或或jbsupmna35替換密碼替換密碼單字母替換單字母替換Playfair密碼密碼n有有26 26=676種字母對組合種字母對組合n字符出現(xiàn)幾率一定程度上被均勻化字符出現(xiàn)幾率一定程度上被均勻化n基于字母頻率的攻擊比較困難基于字母頻率的攻擊比較困難n依然保留了相當?shù)慕Y(jié)構(gòu)信息依然保留了相當?shù)慕Y(jié)構(gòu)信息 36替換密碼替換密碼多表替換多表替換nVigenere密碼密碼n替換規(guī)則由替換規(guī)則由26個類似個類似caesar密碼的替換表密碼的替換表組成，其中每一個替換表是對明文字母移組成，其中每一個替換表是對明文字母移位位0

22、到到25次后得到的替換單表。次后得到的替換單表。n每個替換單表由一個密鑰字母表示。每個替換單表由一個密鑰字母表示。A B C D E F G H I J K L M N O P Q R S T U V W X Y ZB C D E F G H I J K L M N O P Q R S T U V W X Y Z AC D E F G H I J K L M N O P Q R S T U V W X Y Z A BD E F G H I J K L M N O P Q R S T U V W X Y Z A B CE F G H I J K L M N O P Q R S T U V W X

23、 Y Z A B C DF G H I J K L M N O P Q R S T U V W X Y Z A B C D EG H I J K L M N O P Q R S T U V W X Y Z A B C D E FH I J K L M N O P Q R S T U V W X Y Z A B C D E F GI J K L M N O P Q R S T U V W X Y Z A B C D E F G HJ K L M N O P Q R S T U V W X Y Z A B C D E F G H I A B C D E F G H I J K L M N O P

24、Q R S T U V W X Y ZA BCDEFGHIJVigenere替換表替換表deceptivedeceptivedeceptivewearediscoveredsaveyourself 密鑰密鑰明文明文zicvtwqngrzgvtwavzhcqyglmgj密文密文38置換密碼置換密碼n將明文的字母順序打亂，得到新的排列將明文的字母順序打亂，得到新的排列n最簡單的置換密碼：柵欄技術(shù)最簡單的置換密碼：柵欄技術(shù) 明文明文 meet me after the toga party 置換方法置換方法 m e m a t r h t g p r y e t e f e t e o a a t

25、密文密文 mematrhtgpryetefeteoaat39置換密碼置換密碼n列置換列置換n換位密碼把明文按行寫入換位密碼把明文按行寫入, ,按列讀出按列讀出T H I S IS A M E SS A G E TO S H O W明文：明文：this is a message to show密文：密文：tssohaasimghseeoistw40置換密碼置換密碼n帶密鑰的列置換帶密鑰的列置換n換位密碼把明文按行寫入換位密碼把明文按行寫入, ,按密鑰規(guī)定讀出字母按密鑰規(guī)定讀出字母的列順序的列順序T H I S IS A M E SS A G E TO S H O W明文：明文：this is a

26、 message to show密鑰：密鑰：35214密文：密文：IMGHISTWHAASTSSOSEEO 41傳統(tǒng)加密機制小結(jié)傳統(tǒng)加密機制小結(jié)n代替密碼和置換密碼代替密碼和置換密碼n對稱密碼的兩個基本運算對稱密碼的兩個基本運算n代替和置換代替和置換(Substitution & permutation)n對稱密碼分析的兩個基本方法對稱密碼分析的兩個基本方法n統(tǒng)計分析法、窮舉法統(tǒng)計分析法、窮舉法n多輪加密多輪加密n數(shù)據(jù)安全基于算法的保密數(shù)據(jù)安全基于算法的保密42對稱密碼對稱密碼n對稱密碼機制提供一個雙向信道：對稱密碼機制提供一個雙向信道：A和和B共享一個秘密密鑰，雙方既能加共享一個秘密

27、密鑰，雙方既能加密信息發(fā)送給對方，也可以解密從對密信息發(fā)送給對方，也可以解密從對方得到的密文信息。方得到的密文信息。n流密碼（流密碼（stream cipher）n分組密碼（分組密碼（block cipher）43對稱密碼對稱密碼n流密碼（流密碼（stream cipher）n每次加密數(shù)據(jù)流的一位或一個字節(jié)每次加密數(shù)據(jù)流的一位或一個字節(jié)n密鑰由密鑰序列發(fā)生器生成用于加密和解密鑰由密鑰序列發(fā)生器生成用于加密和解密的密鑰序列密的密鑰序列n古典流密碼：古典流密碼：Vigenere密碼和密碼和Vernam密碼密碼44對稱密碼對稱密碼n分組密碼分組密碼n將明文分成一段一段，將一段明文作為將明文分成一段一

28、段，將一段明文作為一個分組進行加密，一個分組進行加密，每組分別在密鑰的每組分別在密鑰的控制下變換成等長的輸出密文序列?？刂葡伦儞Q成等長的輸出密文序列。n如：如：We will meet this afternoon. 以以5個字個字符為一組，則得到明文分組：符為一組，則得到明文分組： wewil lmeet thisa ftern oonxx，其中不夠一個分，其中不夠一個分組的采用填充。組的采用填充。45對稱密碼對稱密碼明文明文(p0,.,pn-1)解密解密加密加密密文密文(c1,cn-1)明文明文(p0,.,pn-1)密鑰密鑰(k0,.,km-1)密鑰密鑰(k0,.,km-1)分組密碼模型分

29、組密碼模型加密：加密： C = (c0,cn-1) = E(p0,pn-1) , (k0,km-1) )解密：解密： P = (p0,pn-1) = D(c0,cn-1), (k0,km-1) )46對稱密碼對稱密碼n混淆和擴散混淆和擴散nShannon引見混淆和擴散兩個術(shù)語刻畫密碼引見混淆和擴散兩個術(shù)語刻畫密碼系統(tǒng)的兩個部件。系統(tǒng)的兩個部件。n擴散：使明文的統(tǒng)計特征消散在密文中，擴散：使明文的統(tǒng)計特征消散在密文中，可以讓每個明文字母盡可能的影響多個密可以讓每個明文字母盡可能的影響多個密文字母。即盡可能多的使明密文之間的統(tǒng)文字母。即盡可能多的使明密文之間的統(tǒng)計關(guān)系變得復雜。計關(guān)系變得復雜。n混

30、淆：盡可能使密文和加密密鑰間的統(tǒng)計混淆：盡可能使密文和加密密鑰間的統(tǒng)計關(guān)系復雜，以組織攻擊者發(fā)現(xiàn)密鑰。關(guān)系復雜，以組織攻擊者發(fā)現(xiàn)密鑰。.nFeistel密碼結(jié)構(gòu)密碼結(jié)構(gòu)明文明文(2w位位)FF密文密文(2w位位)第第1輪輪第第n輪輪L0(w位位)R0(w位位)Ln-1(w位位)Rn-1(w位位)K1KnLn(w位位)Rn(w位位)Ln+1(w位位)Rn+1(w位位).48對稱密碼對稱密碼nFesitel密碼結(jié)構(gòu)的具體實現(xiàn)密碼結(jié)構(gòu)的具體實現(xiàn)n分組長度分組長度n密鑰長度密鑰長度n迭代輪數(shù)迭代輪數(shù)n子密鑰產(chǎn)生算法子密鑰產(chǎn)生算法n輪函數(shù)輪函數(shù)n快速加快速加/解密解密n簡化分析難度簡化分析難度49對稱密

31、碼對稱密碼DESn1973年年5月月15日日, NBS公開征集標準加密算法公開征集標準加密算法,并公布了它的設(shè)計要求并公布了它的設(shè)計要求:n算法必須提供高度的安全性算法必須提供高度的安全性n算法必須有詳細的說明算法必須有詳細的說明,并易于理解并易于理解n算法的安全性取決于密鑰算法的安全性取決于密鑰,不依賴于算法不依賴于算法n算法適用于所有用戶算法適用于所有用戶n算法適用于不同應用場合算法適用于不同應用場合n算法必須高效、經(jīng)濟算法必須高效、經(jīng)濟n算法必須能被證實有效算法必須能被證實有效n算法必須是可出口的算法必須是可出口的50對稱密碼對稱密碼DESn1974年年8月月27日日, IBM提交了算法

32、提交了算法LUCIFER，該算法，該算法由由IBM的工程師在的工程師在19711972年研制年研制n1976年年11月月23日，采納為聯(lián)邦標準，批準用于非軍事日，采納為聯(lián)邦標準，批準用于非軍事場合的各種政府機構(gòu)場合的各種政府機構(gòu)n1977年年1月月15日日,“數(shù)據(jù)加密標準數(shù)據(jù)加密標準”FIPS PUB 46發(fā)布。發(fā)布。nFIPS PUB 81 （DES的工作方式）在的工作方式）在1980年公布年公布nFIPS PUB 74（實現(xiàn)和使用（實現(xiàn)和使用DES的指南）于的指南）于1981年公年公布布nFIPS PUB 112規(guī)定了規(guī)定了DES用作口令加密的標準用作口令加密的標準nFIPS PUB 11

33、3 規(guī)定了規(guī)定了DES如何用作計算機數(shù)據(jù)鑒別如何用作計算機數(shù)據(jù)鑒別51對稱密碼對稱密碼DESnDES的應用的應用n1979年，美國銀行協(xié)會批準使用年，美國銀行協(xié)會批準使用n1980年，美國國家標準局（年，美國國家標準局（ANSI）贊同）贊同DES作作為私人使用的標準為私人使用的標準,稱之為稱之為DEA（ANSI X.392）n1983年，國際化標準組織年，國際化標準組織ISO贊同贊同DES作為國作為國際標準，稱之為際標準，稱之為DEA-152對稱密碼對稱密碼DESnDES加密加密n64位明文輸入位明文輸入n56位密鑰輸入位密鑰輸入n64位密文輸出位密文輸出初始置換初始置換第第1輪輪第第2輪輪第

34、第16輪輪32位互換位互換逆初始置換逆初始置換置換選擇置換選擇2置換選擇置換選擇2置換選擇置換選擇2置換選擇置換選擇1循環(huán)左移循環(huán)左移循環(huán)左移循環(huán)左移循環(huán)左移循環(huán)左移64位明文位明文64位密文位密文K1K2K16DES加密算法的一般描述加密算法的一般描述密鑰密鑰初始置換初始置換IP逆初始置換逆初始置換IP-1初始置換把明文的初始置換把明文的第第5858位換到第位換到第1 1位位的位置，第的位置，第5050位換位換到第到第2 2位的位置位的位置, ,是是DESDES算法的最后一步，算法的最后一步，是一次簡單的數(shù)碼移位，是一次簡單的數(shù)碼移位，也與密鑰無關(guān)。它是把乘也與密鑰無關(guān)。它是把乘積變換輸出的

35、積變換輸出的6464位碼重新位碼重新排列，其結(jié)果即為排列，其結(jié)果即為6464位密位密文。文。Li-1(32位位)Ri-1(32位位)擴充置換運算擴充置換運算(E)替換運算替換運算(S盒盒)置換運算置換運算(P)Li-1(32位位)Ri-1(32位位)48b子密鑰子密鑰Ki(48b)32b32b48bDES的一輪迭代的一輪迭代324812162024281 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 591317212529116720212912281711523265

36、18311028241432273919133062211425擴充置換運算擴充置換運算E置換運算置換運算P57對稱密碼對稱密碼n擴充置換的作用擴充置換的作用n產(chǎn)生了與密鑰同長度的數(shù)據(jù)進行異或運算產(chǎn)生了與密鑰同長度的數(shù)據(jù)進行異或運算n產(chǎn)生了更長的結(jié)果，使得在代替運算時能進行產(chǎn)生了更長的結(jié)果，使得在代替運算時能進行壓縮壓縮n輸入的一位將影響兩個替換，所以輸出對輸入輸入的一位將影響兩個替換，所以輸出對輸入的依賴性將傳播得更快，明文或密鑰的一點小的依賴性將傳播得更快，明文或密鑰的一點小的變動應該使密文發(fā)生一個大的變化的變動應該使密文發(fā)生一個大的變化. 這叫雪崩這叫雪崩效應效應(avalanche e

37、ffect)。替換運算替換運算(S盒盒)：對每個盒，對每個盒，6比特輸入中的第比特輸入中的第1和第和第6比比特組成的二進制數(shù)確定的行，中間特組成的二進制數(shù)確定的行，中間4位二進制數(shù)用來確定的位二進制數(shù)用來確定的列，相應行、列位置的十進制數(shù)的列，相應行、列位置的十進制數(shù)的4位二進制數(shù)表示作為輸位二進制數(shù)表示作為輸出。出。DES的的S-BoxDES的的S-Box61子密鑰生成子密鑰生成n外部輸入的外部輸入的56位密鑰位密鑰(64位中去掉位中去掉8個校驗位，個校驗位，即第即第8，16，24，32，40，48，56，64位位) 通過通過置換和移位操作置換和移位操作生成生成加密和解密需要的加密和解密需要

38、的16個個48位的子密鑰。位的子密鑰。具體步驟如下圖。具體步驟如下圖。C0(28位位)D0(28位位)密鑰密鑰(64位位)置換選擇置換選擇1循環(huán)左移循環(huán)左移循環(huán)左移循環(huán)左移C1(28位位)D1(28位位)循環(huán)左移循環(huán)左移循環(huán)左移循環(huán)左移C16(28位位)D16(28位位)置換選擇置換選擇2置換選擇置換選擇2K1(48b)K16(48b)子密鑰的產(chǎn)生子密鑰的產(chǎn)生置換選擇置換選擇157110194958211415059333425160253443521726354491827366371421556261347546153946532831384520233037121522294141711

39、2415328156211019191242681672720132415231374755304051453348444939563453464250362932置換選擇置換選擇2每輪的循環(huán)左移次數(shù)每輪的循環(huán)左移次數(shù)迭代輪數(shù)迭代輪數(shù)12345678910111213141516移位次數(shù)移位次數(shù)112222221222222165DES解密解密nDES的解密算法與加密算法相同，解密密鑰也的解密算法與加密算法相同，解密密鑰也與加密密鑰相同。與加密密鑰相同。n只是解密時只是解密時逆向逆向取用加密時用的密鑰順序。取用加密時用的密鑰順序。n即：加密時第即：加密時第1-16輪回迭代使用的子密鑰順序是輪回

40、迭代使用的子密鑰順序是k1,k16 ；而解密時使用的子密鑰順序是；而解密時使用的子密鑰順序是k16 , k1 ，產(chǎn)生子密鑰時的循環(huán)移位是產(chǎn)生子密鑰時的循環(huán)移位是向右向右的。的。66DES加密過程的數(shù)學模型加密過程的數(shù)學模型 L0R0=IP(M64) (M64為為64位輸入明文位輸入明文) Ki=ks(i,key) i=1,2,16 (ks表示密鑰運算函數(shù)表示密鑰運算函數(shù),產(chǎn)生產(chǎn)生48位的子密鑰位的子密鑰) Li=Ri-1，Ri=Li-1 f (Ri-1,Ki) (Ri-1,Ki)中涉及到中涉及到E變換、變換、S盒代替、盒代替、P盒變換和異或運算等步盒變換和異或運算等步驟驟 C64=IP-1(L

41、16,R16)67DES解密過程的數(shù)學模型解密過程的數(shù)學模型 L16R16=IP(C64) Ki=ks(i,key) i=16,15,1 Ri-1 = Li Li-1 = Ri (Ri,Ki) M64=IP-1(L0,R0)68對稱密碼對稱密碼DESnDES算法特點算法特點n只使用了標準的算術(shù)與邏輯運算只使用了標準的算術(shù)與邏輯運算n解密算法與加密算法相同，只是子密鑰解密算法與加密算法相同，只是子密鑰的使用次序相反的使用次序相反n適合軟硬件的實現(xiàn)適合軟硬件的實現(xiàn)69對稱密碼對稱密碼DESnDES的破譯的破譯n1990年，以色列密碼學家年，以色列密碼學家Eli Biham和和Adi Shamir提

42、出了差分密碼分析法，可對提出了差分密碼分析法，可對DES進行選擇明文進行選擇明文攻擊。攻擊。n線性密碼分析線性密碼分析(1993)(1993)比差分密碼分析更有效比差分密碼分析更有效 n強力攻擊：平均強力攻擊：平均255次嘗試次嘗試n差分密碼分析法差分密碼分析法n線性密碼分析法線性密碼分析法70對稱密碼對稱密碼3DESn三重三重DES算法需要執(zhí)行三次算法需要執(zhí)行三次DES的加密。一般的加密。一般三重三重DES算法使用兩個算法使用兩個DES密鑰。其算法步驟密鑰。其算法步驟為：為：發(fā)送端用密鑰發(fā)送端用密鑰K1進行進行DES加密；加密；發(fā)送端用密鑰發(fā)送端用密鑰K2對上一結(jié)果進行對上一結(jié)果進行DES解

43、密；解密；發(fā)送端用密鑰發(fā)送端用密鑰K1對上一結(jié)果進行對上一結(jié)果進行DES加密；加密；接收方則相應地使用接收方則相應地使用K1解密，解密，K2加密，再使用加密，再使用K1解密解密 。71對稱密碼對稱密碼3DESDESDES-1DESDES-1DESDES-1K1K2K3明文明文明文明文加密加密解密解密密文密文密文密文72國際數(shù)據(jù)加密算法國際數(shù)據(jù)加密算法(IDEA)IDEA是分組密碼算法，分組長度為是分組密碼算法，分組長度為64位，但密鑰位，但密鑰長度長度128位。位。該算法是用該算法是用128位密鑰對位密鑰對64位二進制碼組成的數(shù)據(jù)位二進制碼組成的數(shù)據(jù)組進行加密的，也可用同樣的密鑰對組進行加密的

44、，也可用同樣的密鑰對64位密文進行位密文進行解密變換。解密變換。IDEA的密鑰比的密鑰比DES的多一倍，增加了破譯難度，的多一倍，增加了破譯難度，被認為是多年后都有效的算法。被認為是多年后都有效的算法。73國際數(shù)據(jù)加密算法國際數(shù)據(jù)加密算法(IDEA)IDEA算法也是通過一系列的加密輪回操作的，每算法也是通過一系列的加密輪回操作的，每輪中也使用壓縮函數(shù)進行變換，只是不使用移位置輪中也使用壓縮函數(shù)進行變換，只是不使用移位置換。換。IDEA中使用的運算有：中使用的運算有：異或異或模模216加法加法模模216+1乘法乘法這三種運算彼此混合可產(chǎn)生很好的效果。運算時這三種運算彼此混合可產(chǎn)生很好的效果。運算

45、時IDEA把數(shù)據(jù)分為四個子分組，每個把數(shù)據(jù)分為四個子分組，每個16位位74對稱密碼對稱密碼AESnAES產(chǎn)生的背景產(chǎn)生的背景n1997年年4月月15日，日，NIST發(fā)起征集高級加密標準發(fā)起征集高級加密標準（Advanced Encryption Standard）AES的活動，的活動，活動目的是確定一個非保密的、可以公開技術(shù)活動目的是確定一個非保密的、可以公開技術(shù)細節(jié)的、全球免費使用的分組密碼算法，作為細節(jié)的、全球免費使用的分組密碼算法，作為新的數(shù)據(jù)加密標準。新的數(shù)據(jù)加密標準。n對對AES的基本要求是：比三重的基本要求是：比三重DES快、至少與三快、至少與三重重DES一樣安全；無類別的；可公開

46、的；無特權(quán)一樣安全；無類別的；可公開的；無特權(quán)的；數(shù)據(jù)分組長度為的；數(shù)據(jù)分組長度為128比特；密鑰長度為比特；密鑰長度為128/192/256比特。比特。75對稱密碼對稱密碼AESnAES產(chǎn)生的背景產(chǎn)生的背景n1998年年8月月12日，在首屆日，在首屆AES會議上指定了會議上指定了15個個候選算法。候選算法。n1999年年3月月22日第二次日第二次AES會議上，將候選名單會議上，將候選名單減少為減少為5個，這個，這5個算法是個算法是RC6，Rijndael，SERPENT，Twofish和和MARS。n2000年年10月月2日，日，NIST宣布了獲勝者宣布了獲勝者Rijndael算法，算法，2

47、001年年11月出版了最終標準月出版了最終標準FIPS PUB197。76對稱密碼對稱密碼AESnAESn使用的數(shù)學背景：近似代數(shù)使用的數(shù)學背景：近似代數(shù)n不屬于不屬于Feistel結(jié)構(gòu)結(jié)構(gòu)n加密、解密相似但不對稱加密、解密相似但不對稱n支持支持128/32=Nb數(shù)據(jù)塊大小數(shù)據(jù)塊大小n支持支持128/192/256(/32=Nk)密鑰長度密鑰長度n結(jié)構(gòu)簡單、速度快結(jié)構(gòu)簡單、速度快77DES和和AES的比較的比較DESAES日期日期1976年年1999年年分組大小分組大小64b128b密鑰長度密鑰長度56b(有效長度有效長度)128b、192b、256b(可能可能更長更長)加密原語加密原語替換、

48、置換替換、置換替換、移位、位混合替換、移位、位混合算法算法公開公開公開公開設(shè)計基本原理設(shè)計基本原理未公開未公開公開公開選擇過程選擇過程保密保密保密，但接受公開評論保密，但接受公開評論來源來源IBM, 由由NSA加強加強比利時密碼學家比利時密碼學家78對稱密碼對稱密碼n分組密碼的工作模式分組密碼的工作模式n電碼本電碼本(ECB)n密碼分組連接密碼分組連接(CBC)n密碼反饋密碼反饋(CFB)n輸出反饋輸出反饋(OFB)n計數(shù)器計數(shù)器(CTR)79對稱密碼對稱密碼n電碼本電碼本(Electronic Code Book)加密加密p1c1k解密解密c1p1k加密加密pncnk加密加密pncnk.80

49、對稱密碼對稱密碼nECB方式的特點方式的特點n簡單和有效簡單和有效n可以并行實現(xiàn)可以并行實現(xiàn)n不能隱藏明文的模式信息不能隱藏明文的模式信息n相同明文得到的密文相同相同明文得到的密文相同n同樣信息多次出現(xiàn)造成泄漏同樣信息多次出現(xiàn)造成泄漏n對明文的主動攻擊是可能的對明文的主動攻擊是可能的n信息塊可被替換、重排、刪除、重放信息塊可被替換、重排、刪除、重放n誤差傳遞：密文塊損壞誤差傳遞：密文塊損壞導致僅導致僅對應明文塊損壞對應明文塊損壞n適合于傳輸短信息適合于傳輸短信息n密碼分組鏈接密碼分組鏈接(Ciphertext Block Chaining)加密加密p1c1k加密加密cnk.IV加密加密c2kp

50、2.pncn-1解密解密p1c1k解密解密cnk.IV解密解密c2kp2.pncn-182對稱密碼對稱密碼nCBC的特點的特點n能隱藏明文的模式信息能隱藏明文的模式信息n相同明文相同明文得到的得到的密文不同密文不同n使用了初始化向量使用了初始化向量IV（可以用來改變第一塊）（可以用來改變第一塊）n信息塊不容易被替換、重排、刪除、重放信息塊不容易被替換、重排、刪除、重放n誤差傳遞：誤差傳遞：密文塊損壞導致密文塊損壞導致兩兩明文明文塊塊損壞損壞n安全性高于安全性高于ECBn適合于傳輸長度大于適合于傳輸長度大于64位的報文，可以進行用位的報文，可以進行用戶鑒別，是大多系統(tǒng)的標準如戶鑒別，是大多系統(tǒng)的

51、標準如 SSL、IPSec 選擇選擇 丟棄丟棄s位位 |64-s位位n密文反饋模式密文反饋模式(Ciphertext Feedback Block)加密加密c1(s位位)kp1移位寄存器移位寄存器64-s位位|s位位64位位64位位IV參加下一分組加密計算參加下一分組加密計算加密加密選擇選擇 丟棄丟棄s位位 |64-s位位加密加密c2(s位位)kp2移位寄存器移位寄存器64-s位位|s位位64位位64位位IVc1(s位位)同時參加下一分組解同時參加下一分組解密計算密計算_密文反饋模式密文反饋模式(Ciphertext Feedback Block)(Ciphertext Feedback Bl

52、ock)解密解密p1k移位寄存器移位寄存器64-s位位|s位位64位位64位位IV選擇選擇 丟棄丟棄s位位 |64-s位位解密解密解密解密p2k移位寄存器移位寄存器64-s位位|s位位64位位64位位IV選擇選擇 丟棄丟棄s位位 |64-s位位c2(s位位)85對稱密碼對稱密碼nCFB的特點的特點n在分組密碼在分組密碼中使用中使用流密碼的模式流密碼的模式n隱藏了明文模式隱藏了明文模式n需要共同的移位寄存器初始值需要共同的移位寄存器初始值IVn對于不同的消息，對于不同的消息，IV必須唯一必須唯一n誤差傳遞：一個單元損壞影響多個單元誤差傳遞：一個單元損壞影響多個單元 n輸出反饋模式輸出反饋模式(O

53、utput Feedback Block)加密加密c1(s位位)kp1移位寄存器移位寄存器64-s位位|s位位64位位64位位IV參加下一分組參加下一分組加密計算加密計算選擇選擇 丟棄丟棄s位位 |64-s位位加密加密加密加密c2(s位位)kp2移位寄存器移位寄存器64-s位位|s位位64位位64位位IV選擇選擇 丟棄丟棄s位位 |64-s位位輸出反饋模式輸出反饋模式(Output Feedback Block)(Output Feedback Block)c1(s位位) _解密解密p1k移位寄存器移位寄存器64-s位位|s位位64位位64位位IV選擇選擇 丟棄丟棄s位位 |64-s位位同時參

54、加下一同時參加下一分組解密計算分組解密計算解密解密c2(s位位) _解密解密p2k移位寄存器移位寄存器64-s位位|s位位64位位64位位選擇選擇 丟棄丟棄s位位 |64-s位位88對稱密碼對稱密碼nOFB的特點的特點n利用流密碼的模式利用流密碼的模式n隱藏了明文模式隱藏了明文模式n需要共同的移位寄存器初始值需要共同的移位寄存器初始值IVn誤差傳遞：一個單元損壞只影響對應單元誤差傳遞：一個單元損壞只影響對應單元n對明文的主動攻擊是可能的對明文的主動攻擊是可能的n信息塊可被替換、重放信息塊可被替換、重放n安全性較安全性較CFBCFB差差n計數(shù)器模式計數(shù)器模式(Counter)加密加密計數(shù)器計數(shù)器

55、cikpi解密解密計數(shù)器計數(shù)器pikci90對稱密碼對稱密碼nCTR的特點的特點n利用流密碼的模式利用流密碼的模式n可以并行實現(xiàn)、可以預處理、適用于高速網(wǎng)絡(luò)可以并行實現(xiàn)、可以預處理、適用于高速網(wǎng)絡(luò)n可以隨機訪問加密的數(shù)據(jù)分組可以隨機訪問加密的數(shù)據(jù)分組n隱藏了明文模式，隱藏了明文模式，與與CBC模式一樣安全模式一樣安全n可以處理任意長度的消息可以處理任意長度的消息n誤差傳遞：一個單元損壞只影響對應單元誤差傳遞：一個單元損壞只影響對應單元n對于每次加密，需要使用不同的密鑰的計數(shù)器值對于每次加密，需要使用不同的密鑰的計數(shù)器值n信息塊可被替換、重放信息塊可被替換、重放91密碼技術(shù)密碼技術(shù)n對稱加密技術(shù)

56、對稱加密技術(shù)n非對稱加密技術(shù)非對稱加密技術(shù)n消息認證與消息認證與HASH函數(shù)函數(shù)92對稱密碼的不足對稱密碼的不足n密鑰管理量的困難密鑰管理量的困難n傳統(tǒng)密鑰管理：兩兩分別用一個密鑰時，則傳統(tǒng)密鑰管理：兩兩分別用一個密鑰時，則n個用個用戶需要戶需要C(n,2)=n(n-1)/2個密鑰，當用戶量增大時，個密鑰，當用戶量增大時，密鑰空間急劇增大。密鑰空間急劇增大。n密鑰必須通過某一信道協(xié)商，對這個信道的安密鑰必須通過某一信道協(xié)商，對這個信道的安全性的要求比正常的傳送消息的信道的安全性全性的要求比正常的傳送消息的信道的安全性要高要高n數(shù)字簽名的問題數(shù)字簽名的問題n傳統(tǒng)加密算法無法實現(xiàn)抗抵賴的需求。傳統(tǒng)

57、加密算法無法實現(xiàn)抗抵賴的需求。93公鑰密碼的起源公鑰密碼的起源n公鑰密碼又稱為雙鑰密碼和非對稱密碼公鑰密碼又稱為雙鑰密碼和非對稱密碼n1976年由年由Diffie和和Hellman在其在其“密碼學新方向密碼學新方向”一文中提出的一文中提出的W.Diffie and M.E.Hellman, New Directrions in Cryptography, IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976, PP.644-654）nRivest,Shamir和和Adleman在在1978年提出年提出RSA公公鑰算法鑰算法

58、 Communitions of the ACM. Vol.21.No.2. Feb. 1978, PP.120-12694公鑰密碼的特點公鑰密碼的特點n加密與解密的密鑰不同加密與解密的密鑰不同n公鑰密碼的密鑰是一組密鑰對（公鑰公鑰密碼的密鑰是一組密鑰對（公鑰,私鑰）私鑰）n可以公開的密鑰稱為公鑰，必須保密的密鑰稱為私鑰。可以公開的密鑰稱為公鑰，必須保密的密鑰稱為私鑰。n知道密碼算法和公鑰，從公鑰得到私鑰在計算上知道密碼算法和公鑰，從公鑰得到私鑰在計算上是不可行的是不可行的n兩個密鑰配對使用兩個密鑰配對使用n公鑰加密信息，私鑰解密信息公鑰加密信息，私鑰解密信息n私鑰簽名信息，公鑰驗證簽名私鑰簽

59、名信息，公鑰驗證簽名95公鑰密碼的加密公鑰密碼的加密Hi BobAliceHi BobAliceHi BobAliceHi BobAlice公開公開保密保密96公鑰密碼的簽名公鑰密碼的簽名n數(shù)字簽名數(shù)字簽名n類似于手寫簽名類似于手寫簽名n簽名后不能否認簽名后不能否認n發(fā)生糾紛后，可以在發(fā)生糾紛后，可以在第三方處進行仲裁。第三方處進行仲裁。n具有法律效應具有法律效應數(shù)字簽名數(shù)字簽名97公鑰密碼的簽名公鑰密碼的簽名Hi BobAliceHi BobAlice保密保密公開公開Hi BobAliceAliceHi BobAliceAlice98公鑰密碼的特點公鑰密碼的特點n數(shù)字簽名可以有效的解決如下安

60、全問題數(shù)字簽名可以有效的解決如下安全問題n否認：發(fā)送者事后不承認自己發(fā)送過文件否認：發(fā)送者事后不承認自己發(fā)送過文件n偽造：接收者偽造一份文件，聲稱它來自偽造：接收者偽造一份文件，聲稱它來自發(fā)送者發(fā)送者n冒充：網(wǎng)上的某個用戶冒充另一個用戶接冒充：網(wǎng)上的某個用戶冒充另一個用戶接收或發(fā)送信息收或發(fā)送信息n篡改：接收者對收到的信息進行部分篡改篡改：接收者對收到的信息進行部分篡改 99公鑰密碼的安全性公鑰密碼的安全性n公鑰算法的條件：公鑰算法的條件：n產(chǎn)生一對密鑰是計算可行的產(chǎn)生一對密鑰是計算可行的n已知公鑰和明文，產(chǎn)生密文是計算可行的已知公鑰和明文，產(chǎn)生密文是計算可行的n接收方利用私鑰解密密文是計算可行的接收方利用私鑰解密