密碼學(xué)基礎(chǔ)[1]

1、密碼學(xué)基礎(chǔ)遷鋼公司運營改善部課程內(nèi)容知識子域：密碼學(xué)基礎(chǔ)概念 理解密碼編碼學(xué)和密碼分析學(xué)的概念 了解科克霍夫原則和影響密碼系統(tǒng)的安全性的基本因素：復(fù)雜程度、密鑰機密性、密鑰長度、初始化向量 了解密碼的基本類型：換位（置換）密碼、替代（代換）密碼、流密碼、分組密碼的概念 了解密碼破解的典型方式：唯密文攻擊、已知明文攻擊、選擇明文攻擊、選擇密文攻擊、旁路攻擊、重放攻擊、統(tǒng)計式攻擊等 掌握密碼體制的分類 了解密鑰管理的概念，包括密鑰管理體制、密鑰交換協(xié)議和密鑰的產(chǎn)生、分配、更換和注銷等。密碼學(xué)發(fā)展第一個階段是從古代到19世紀(jì)末古典密碼（classical cryptography)第二個階段從20世

2、紀(jì)初到1949年近代密碼第三個階段從C.E.Shannon（香農(nóng)） 于1949年發(fā)表的劃時代論文“The Communication Theory of Secret Systems ”開始現(xiàn)代密碼第四個階段從1976年W. Diffie和M. Hellman創(chuàng)造性地發(fā)表了論文“New Directions in Cryptography”開始公鑰密碼古典密碼學(xué)古典密碼體制的安全性在于保持算法本身的保密性，受到算法限制。不適合大規(guī)模生產(chǎn)不適合較大的或者人員變動較大的組織用戶無法了解算法的安全性古典密碼主要有以下幾種：代替密碼（Substitution Cipher）換位密碼（Transposi

3、tion Cipher）代替密碼與換位密碼的組合古典密碼學(xué)分類代替密碼換位密碼古典密碼學(xué)多字母代替單字母代替單表代替密碼多表代替密碼（流密碼）（分組密碼）Substitution cipherPolygram Substitution cipherTransposition CipherMonoalphabetic Substitution cipherPloyalphabetic Substitution cipherStream cipherBlock cipher近代密碼學(xué)20世紀(jì)初到1949年： 主要標(biāo)志是機械密碼/機電密碼，用機電代替手工。 近代密碼體制是用機械或電動機械實現(xiàn)的，最著

4、名的就是轉(zhuǎn)輪機（Rotor Machine）。一次一密亂碼本（1917）發(fā)明者：發(fā)明者：Major Joseph Mauborgne和和AT&T公司的公司的Gilbert Vernam在在1917年發(fā)明。年發(fā)明。應(yīng)用于：應(yīng)用于：報文 s e c r e t 18 5 3 17 5 19 OTP + 15 8 1 12 19 5 7 13 4 3 24 24 g m d c x xOTP（one-time pad ）從理論上是不可破的：v不重復(fù)使用亂碼本（VENONA）v使用不可預(yù)知的隨機數(shù)（物理源，如放射性衰減）舉例：密碼廣播代替？置換？小測試？余則成接受廣播呼叫所使用的密碼本是A 紅

5、樓夢B 朱子家訓(xùn)C 蝴蝶夢 D 康熙字典轉(zhuǎn)輪機Germany: EnigmaUK: TYPEXUS: Converter M-209Germany: ENIGMA（1919）轉(zhuǎn)輪密碼機ENIGMA，由Arthur Scherbius于1919年發(fā)明，4輪ENIGMA在1944年裝備德國海軍。使得英國從1942年2月到12月都沒能解讀德國潛艇的信號。UK:TYPEX打字密碼機英國的TYPEX打字密碼機，是德國3輪ENIGMA的改進(jìn)型密碼機。它在英國通信中使用廣泛，且在破譯密鑰后幫助破解德國信號。US:M-209M-209是哈格林對C-36改進(jìn)后的產(chǎn)品，由Smith-Corna負(fù)責(zé)為美國陸軍生產(chǎn)。

6、它的密碼周期達(dá)到了101,105,950?，F(xiàn)代密碼學(xué)19491975年： 1949年，Shannon的論文“The Communication Theory of Secret Systems” 。 1967年，David Kahn的專著The Code breakers。 1971年1973年，IBM Watson實驗室的Horst Feistel等人發(fā)表的幾篇技術(shù)報告。 1974年，IBM提交了算法LUCIFER，后來成為了DES。Shannon公鑰密碼學(xué)1976年以后： 1976年，Diffie & Hellman的“New Directions in Cryptography”

7、提出了非對稱密鑰密碼。 1977年，Rivest,Shamir & Adleman提出了RSA公鑰算法。 90年代，逐步出現(xiàn)橢圓曲線等其他公鑰算法。公鑰密碼使得發(fā)送端和接收端無密鑰傳輸?shù)谋Ｃ芡ㄐ懦蔀榭赡?！Martin-HellmanWhitfield_Diffie什么是密碼學(xué)密碼學(xué)基本概念密碼體制分類密鑰管理密碼學(xué)基本概念密碼編碼學(xué) Vs 密碼分析學(xué)密碼編碼學(xué)（1）密碼編碼學(xué)是密碼學(xué)的一個分支，研究與信息安全（例如：機密性、完整性、可鑒別性）有關(guān)的數(shù)學(xué)技術(shù)。（2）密碼編碼學(xué)是包含數(shù)據(jù)變換的原理、工具和方法的一門學(xué)科，這種數(shù)據(jù)變換的目的是為了隱藏數(shù)據(jù)的信息內(nèi)容，阻止對數(shù)據(jù)的篡改以及防止未

8、經(jīng)認(rèn)可使用數(shù)據(jù)。（3）密碼編碼學(xué)是論述使明文變得不可懂的密文，以及把已加密的消息變換成可懂形式的藝術(shù)和技巧。密碼分析學(xué)（1）密碼分析學(xué)是密碼學(xué)的一個分支，它與另一個分支學(xué)科密碼編碼學(xué)是兩個相互對立、相互依存、相輔相成、相互促進(jìn)的學(xué)科。（2）密碼分析學(xué)是企圖挫敗編碼技術(shù)以及更一般說來的信息安全服務(wù)的數(shù)學(xué)技術(shù)學(xué)科。（3）密碼分析學(xué)是對密碼體制、密碼體制的輸入輸出關(guān)系進(jìn)行分析，以便推出機密變量、包括明文在內(nèi)的敏感數(shù)據(jù)。有時又稱作密碼破譯學(xué)（code breaking）Kerckhoff原理Auguste Kerckhoff在1883年發(fā)表了一篇論文，認(rèn)為一個密碼系統(tǒng)中唯一應(yīng)該保密的只有密鑰。他認(rèn)為，

9、密碼算法應(yīng)該對外公開，如果一個密碼系統(tǒng)需要保密的越多，可能的弱點也越多。這種觀點對于密碼研究者和私營部門來說已經(jīng)是一種常識，但是軍事部門和政府則不這么認(rèn)為。世界上大部分的政府都研制自己的算法并且不對外公開。Kerchhoff假設(shè)假設(shè)：密碼分析者知道雙方使用的密碼系統(tǒng)，包括明文的統(tǒng)計特性、加解密體制等，唯一不知道的是密鑰。在設(shè)計一個密碼系統(tǒng)時，目標(biāo)是在Kerckhoffs 假設(shè)的前提下實現(xiàn)安全 。密碼分析的典型方式 密碼分析是研究密鑰未知的情況下恢復(fù)明文的科學(xué)，成功的密碼分析恢復(fù)明文或密鑰。 密碼分析常用的方法有以下4類： 唯密文攻擊（cybertext only attack）： 密碼分析者知

10、道一些消息的密文（加密算法相同），并且試圖恢復(fù)盡可能多的消息明文，進(jìn)一步推算出加密消息的密鑰（以便通過密鑰得出更多的消息明文。 已知明文攻擊（known plaintext attack）： 密碼分析者不僅知道一些消息的密文，也知道與這些密文對應(yīng)的明文，并試圖推導(dǎo)出加密密鑰或算法（該算法可對采用同一密鑰加密的所有新消息進(jìn)行解密。密碼分析的典型方式（續(xù)） 選擇明文攻擊（chosen plaintext attack）： 密碼分析者不僅知道一些消息的密文以及與之對應(yīng)的明文，而且可以選擇被加密的明文（這種選擇可能導(dǎo)致產(chǎn)生更多關(guān)于密鑰的信息），并試圖推導(dǎo)出加密密鑰或算法（該算法可對采用同一密鑰加密的所

11、有新消息進(jìn)行解密）。 （暫時控制加密機） 選擇密文攻擊（chosen ciphertext attack）： 密碼分析者能夠選擇不同的密文并能得到對應(yīng)的明文，密碼分析的目的是推導(dǎo)出密鑰。（暫時控制解密機）密碼分析的其他方式 旁路攻擊（side channel） 通過收集“外面”的信息來破解密碼，而不是直接處理“里面”的東西。 檢測加解密過程所消耗的能量，所釋放的輻射來計算過程時間。 重放攻擊（replay attack） 攻擊者捕獲了一些類型的數(shù)據(jù)并重新提交它，寄希望于欺騙接收設(shè)備誤以為這些是合法信息。 時間戳和序列號是對付重放攻擊的兩個對策。 統(tǒng)計式攻擊 利用明文的已知統(tǒng)計規(guī)律進(jìn)行破譯的方法

12、。密碼破譯者對截獲的密文進(jìn)行統(tǒng)計分析，總結(jié)出其統(tǒng)計規(guī)律，并與明文的統(tǒng)計規(guī)律進(jìn)行對照比較，從中提取出明文和密文之間的對應(yīng)或變換信息。明文 vs.密文 明文(Plaintext) ：被隱蔽消息。 密文(Ciphertext)或密報(Cryptogram)：明文經(jīng)密碼變換而成的一種隱蔽形式。 加密員或密碼員(Cryptographer)：對明文進(jìn)行加密操作的人員。加密 vs.解密加密（Encryption）：將明文變換為密文的過程。把可懂的語言變換成不可懂的語言，這里的語言指人類能懂的語言和機器能懂的語言。解密（Decryption）：加密的逆過程，即由密文恢復(fù)出原明文的過程。把不可懂的語言變換成可

13、懂的語言。加密算法密鑰密文明文解密算法密鑰密文明文加密和解密算法的操作通常都是在一組密鑰的控制下進(jìn)加密和解密算法的操作通常都是在一組密鑰的控制下進(jìn)行的行的,分別稱為分別稱為加密密鑰加密密鑰(Encryption Key) 和和解密密鑰解密密鑰(Decryption Key)。密碼算法密碼算法（Cryptography Algorithm）：用于加密和解密操作的數(shù)學(xué)函數(shù)。加密算法（Encryption Algorithm）：發(fā)送者對明文進(jìn)行加密操作時所采用的一組規(guī)則。解密算法（Decryption Algorithm）：接收者對密文進(jìn)行解密操作時所采用的一組規(guī)則。擴散 vs.混亂擴散（Diffu

14、sion） ：將每一位明文數(shù)字的影響盡可能地散布到多個輸出密文數(shù)字中去，以更隱蔽明文數(shù)字的統(tǒng)計特性?；靵y（Confusion）：使得密文的統(tǒng)計特性與明文、密鑰之間的關(guān)系盡量復(fù)雜化。Shannon稱：在理想密碼系統(tǒng)中，密文的所有統(tǒng)計特性都與所使用的密鑰獨立。密碼體制分類（1）受限制的算法 vs.基于密鑰的算法（2）對稱密碼 vs.非對稱密碼（3）分組密碼 vs.流密碼（4）代替密碼 vs.置換密碼受限制的算法 vs.基于密鑰的算法受限制的（restricted）算法：算法的保密性基于保持算法的秘密?；诿荑€（key-based）的算法：算法的保密性基于對密鑰的保密。對稱密碼算法vs非對稱密碼算法

15、對稱密碼算法（Symmetric cipher）：加密密鑰和解密密鑰相同，或?qū)嵸|(zhì)上等同，即從一個易于推出另一個。又稱傳統(tǒng)密碼算法（Conventional cipher)、秘密密鑰算法或單密鑰算法。 DES、3DES、IDEA、AES非對稱密碼算法（Asymmetric cipher） ：加密密鑰和解密密鑰不同，從一個很難推出另一個。又叫公鑰密碼算法（Public-key cipher)。其中的加密密鑰可以公開，稱為公開密鑰；解密密鑰必須保密，稱為私人密鑰（private key) 。 RSA、ECC、ElGamal非對稱密碼算法上述運算中，23和7作為兩個密鑰，公開一個，另一個作為私鑰即可。

16、例如：公鑰為7，私鑰為23，則即使攻擊者知道7、187和密文11，但如果他不知道私鑰23，那么他無論如何也算不出明文88。數(shù)學(xué)是多么奇妙??！分組密碼 vs.流密碼分組密碼（Block cipher）：將明文分成固定長度的組，用同一密鑰和算法對每一塊加密，輸出也是固定長度的密文。DES、IDEA、RC2、RC4、RC5流密碼（Stream cipher）：又稱序列密碼，序列密碼每次加密一位或一字節(jié)的明文。One-time padding、Vigenre、Vernam分組密碼模型分組密碼是將明文消息編碼表示后的數(shù)字（簡稱明文數(shù)字）序列，劃分成長度為n的組（可看成長度為n的矢量），每組分別在密鑰的控

17、制下變換成等長的輸出數(shù)字（簡稱密文數(shù)字）序列。 流密碼模型密鑰流密鑰流產(chǎn)生器產(chǎn)生器密鑰密鑰k明文明文m密文密文c流密碼體制模型流密碼體制模型異或運算代替密碼 Vs.置換密碼代替密碼（Substitution Cipher）：就是明文中的每一個字符被替換成密文中的另一個字符。接收者對密文做反向替換就可以恢復(fù)出明文。置換密碼（Permutation Cipher）：又稱換位密碼(Transposition Cipher)：明文的字母保持相同，但順序被打亂了。密鑰管理（1）密鑰的生存周期（2）密鑰的產(chǎn)生（3）密鑰的分配（4）密鑰管理的其他階段密鑰管理 在一種安全策略指導(dǎo)下密鑰的產(chǎn)生、 存儲、分配、刪

18、除、歸檔及應(yīng)用。 處理密鑰自產(chǎn)生到最終銷毀的整個過程中的有關(guān)問題包括系統(tǒng)的初始化、密鑰的產(chǎn)生、存儲、備份/恢復(fù)、裝入、分配、保護(hù)、更新、泄露、撤銷和銷毀等內(nèi)容。 所有的密碼技術(shù)都依賴于密鑰。 密鑰的管理本身是一個很復(fù)雜的課題而且是保證安全性的關(guān)鍵點。 密鑰管理方法因所使用的密碼體制對稱密碼體制和公鑰密碼體制而異。所有的密鑰都有生存期 密鑰的生存周期：授權(quán)使用該密鑰的周期。一個密鑰主要經(jīng)歷以下主要階段： 產(chǎn)生、 分配、 使用、 更新/替換、 撤銷、 銷毀。 原因： 1 擁有大量的密文有助于密碼分析一個密鑰使用得太多了會給攻擊者增大收集密文的機會. 2 假定一個密鑰受到危及或用一個特定密鑰的加密/

19、解密過程被分析則限定密鑰的使用期限就相當(dāng)于限制危險的發(fā)生.密鑰的生存期。密鑰的產(chǎn)生 密鑰長度的選擇 密鑰長度的選擇與具體的應(yīng)用有關(guān)，如加密數(shù)據(jù)的重要性、保密期限長短、可能破譯者的計算能力等。 密鑰的類型 不同種類的密鑰類型產(chǎn)生的方法不同。 密鑰產(chǎn)生的方式 集中式 分散式密鑰的分配 無中心的密鑰分配模式 中心化密鑰分配模式 公鑰密碼體制的密鑰分配無中心的密鑰分配模式(1) A向B發(fā)出建立會話密鑰的請求和一個一次性隨機數(shù)N1。(2) B用與A共享的主密鑰對應(yīng)答的消息加密，并發(fā)給A，應(yīng)答的消息中包括B選取的會話密鑰、B的身份，f(N1)和另一個一次性隨機數(shù)N2。(3) A用新建立的會話密鑰加密f(N

20、2)并發(fā)送給B。中心化密鑰分配模式(1) A向KDC發(fā)出會話密鑰請求。請求內(nèi)容包括A與B的身份以及一次性隨機數(shù)N1。(2) KDC為A的請求發(fā)出應(yīng)答。應(yīng)答內(nèi)容包括：一次性會話密鑰Ks、A的請求、用B與KDC的共享密鑰加密一次性會話密鑰Ks和 A的身份，其中應(yīng)答信息是用A與KDC的共享密鑰加密。中心化密鑰分配模式(續(xù))(3) A存儲會話密鑰，并向B轉(zhuǎn)發(fā)用B與KDC的共享密鑰加密一次性會話密鑰Ks和 A的身份。(4) B使用會話密鑰Ks 加密另一個一次性隨機數(shù)N2 ，并將加密結(jié)果發(fā)送給A。(5) B使用會話密鑰Ks 加密f(N2)，并將加密結(jié)果發(fā)送給B。公鑰密碼體制的密鑰分配 A用B的公鑰加密A的

21、身份和一個一次性隨機數(shù)N1后發(fā)給B。 B解密的N1 ，并用A的公鑰加密N1和另一個一次性隨機數(shù)N2 后發(fā)給A。 A用B的公鑰加密N2后發(fā)給B。 B選取一個會話密鑰Ks，用B的私鑰加密后再用A的公鑰加密，發(fā)送給B。 A用A的私鑰和B的公鑰解密得Ks 。密鑰管理的其他階段 密鑰使用 注意內(nèi)存的密鑰泄露。私鑰不出USB Key。 密鑰存儲 現(xiàn)更多存儲在Usb Key中。 密鑰更新 更容易的解決辦法是從舊密鑰中產(chǎn)生新的密鑰。公私鑰對重新生成。 密鑰備份 可信第三方托管或使用主密鑰（公鑰）加密保存。主要針對加密密鑰。 密鑰銷毀(撤銷不同) 物理上徹底粉碎。小結(jié)古典密碼近代密碼現(xiàn)代密碼密碼學(xué)基本概念密碼體

22、制分類密鑰管理對稱密碼算法數(shù)據(jù)加密標(biāo)準(zhǔn)（DES）國際數(shù)據(jù)加密算法（IDEA）高級數(shù)據(jù)加密標(biāo)準(zhǔn)（AES）對稱加密模型密碼學(xué)的目的：Alice和Bob兩個人在不安全的信道上進(jìn)行通信，而破譯者Oscar不能理解他們通信的內(nèi)容。Alice加密機解密機Bob安全信道密鑰源Oscar明文x密文y密鑰k明文x密鑰k數(shù)據(jù)加密標(biāo)準(zhǔn)（DES）DES是一種對稱密鑰算法，密鑰長度為56bits（加上奇偶校驗，通常寫成64bits）。分組加密算法，64 bits為一個分組。基本思想： 混亂（Confusion） 擴散（Diffusion）使用標(biāo)準(zhǔn)的算術(shù)運算和邏輯運算。 DES的產(chǎn)生與應(yīng)用1973年5月15日，NBS開始

23、公開征集標(biāo)準(zhǔn)加密算法，并公布了它的設(shè)計要求: (1) 算法必須提供高度的安全性 (2) 算法必須有詳細(xì)的說明，并易于理解 (3) 算法的安全性取決于密鑰，不依賴于算法 (4) 算法適用于所有用戶 (5) 算法適用于不同應(yīng)用場合 (6) 算法必須高效、經(jīng)濟 (7) 算法必須能被證實有效 (8) 算法必須是可出口的DES的產(chǎn)生1974年8月27日，NBS開始第二次征集，IBM提交了算法LUCIFER。1975年3月17日，NBS公開了全部細(xì)節(jié)。1976年，NBS指派了兩個小組進(jìn)行評價。1976年11月23日，采納為聯(lián)邦標(biāo)準(zhǔn)，批準(zhǔn)用于非軍事場合的各種政府機構(gòu)。1977年1月15日，“數(shù)據(jù)加密標(biāo)準(zhǔn)”F

24、IPS PUB 46發(fā)布。發(fā)明人：美國IBM公司 W. Tuchman 和 C. Meyer 1971-1972年研制成功基礎(chǔ)：1967年美國Horst Feistel提出的理論DES的應(yīng)用1979年，美國銀行協(xié)會批準(zhǔn)使用DES。1980年，美國國家標(biāo)準(zhǔn)局（ANSI）同意DES作為私人使用的標(biāo)準(zhǔn)，稱之為DEA（ANSI X.392）1983年，國際化標(biāo)準(zhǔn)組織（ISO）同意將DES作為國際標(biāo)準(zhǔn)，稱之為DEA-11998年12月以后，美國政府不再將DES作為聯(lián)邦加密標(biāo)準(zhǔn)DES 加密過程 首先把明文分成以64 bit為單位的塊m，對于每個m, 執(zhí)行如下操作 DES(m)=IP-1 T16 T15 .

25、 T2 T1 IP(m) IP，IP-1 ：初始置換 16輪迭代 子密鑰生成DES算法流程輸入輸入64比特明文數(shù)據(jù)比特明文數(shù)據(jù)初始置換初始置換IP在密鑰控制下在密鑰控制下16輪迭代輪迭代初始逆置換初始逆置換IP-1輸出輸出64比特密文數(shù)據(jù)比特密文數(shù)據(jù)交換左右交換左右32比特比特明文IPL0R0fR1L0 fL1R0K1fR2L1 fL2R1K2fR16L15 fL16R15K16IP1密文L15R15Initial PermutationDES解密過程DES解密過程與加密過程完全相似，只不過將16次迭代的子密鑰順序倒過來，即 m = DES-1(c) = IP-1 T1T2.T15 T16 I

26、P(c)可以證明，DES-1 (DES (m) )=mDES的強度密鑰長度 = 56比特強力攻擊 = 嘗試 次差分密碼分析 = 嘗試 次線性密碼分析 = 嘗試 次（但是后兩種攻擊是不實用的）v1976年，耗資年，耗資2000萬美元的計算機，可以在一天中找到密鑰萬美元的計算機，可以在一天中找到密鑰。v1993年，設(shè)計年，設(shè)計100萬美元的計算機，萬美元的計算機，3.5小時用窮舉法找到密小時用窮舉法找到密鑰。鑰。v1998年，年，EFF宣布破譯了宣布破譯了DES算法，耗時不到三天時間，使算法，耗時不到三天時間，使用的是用的是25萬美元的萬美元的“DES破譯機破譯機”。三重DES（3DES ）三重D

27、ES加密，密鑰長度為168比特, k=k1k2k3DESDES-1DESmck1k2k1DES-1DESDES-1mck1k2k1雙密鑰三重雙密鑰三重DES加密，密鑰長度為加密，密鑰長度為112比特比特, k=k1k2DESDES-1DESmck1k2k3DES-1DESDES-1mck3k2k1國際數(shù)據(jù)加密算法（IDEA）IDEA（International Encryption Alogorithm)國際數(shù)據(jù)加密算法。 Xuejia Lai 和James Massey公布IDEA密碼算法第一版，1992年曾改過?！耙牢铱磥?，該算法是目前一公開的最好和最安全的分組密碼算法” 應(yīng)用密碼學(xué)，p2

28、26。強化了抗差分分析的能力，目前已經(jīng)最為PGP的一部分。IDEA算法IDEA算法用了三種數(shù)學(xué)運算： 模216異或算法，常用 表示； 模216加法，表示為 X+Y=Z mod(216)；常用 表示； 模216+1 乘法，表示為 X*Y=Z mod(2161)；常用 表示；IDEA 分組長度64比特 ，分4組，每組長度為16比特，表示為：X1、X2、X3和X4密鑰長度 128比特同一算法既可以加密，也可用于解密。軟件實現(xiàn)IDEA比DES快兩倍現(xiàn)在還沒有資料證明它有什么弱點。 IDEA算法流程乘法：X Y Z mod(216+1)加法：X Y Z mod(216)異或：X Y Z mod(216)

29、X1X2X3X4Z1(1)Z2(1)Z3(1)Z4(1)Z5(1)Z6(1)8輪輪Z1(9)Z2(9)Z3(9)Z4(9)16bit高級數(shù)據(jù)加密標(biāo)準(zhǔn)（AES）1997年4月15日，（美國）國家標(biāo)準(zhǔn)技術(shù)研究所（NIST）發(fā)起征集高級加密標(biāo)準(zhǔn)（Advanced Encryption Standard）AES的活動，活動目的是確定一個非保密的、可以公開技術(shù)細(xì)節(jié)的、全球免費使用的分組密碼算法，作為新的數(shù)據(jù)加密標(biāo)準(zhǔn)。對AES的基本要求是：比三重DES快、至少與三重DES一樣安全、數(shù)據(jù)分組長度為128比特、密鑰長度為128/192/256比特。1997年9月12日，美國聯(lián)邦登記處公布了正式征集AES候選算

30、法的通告。作為進(jìn)入AES候選過程的一個條件，開發(fā)者承諾放棄被選中算法的知識產(chǎn)權(quán)。AES1998年8月12日，在首屆AES會議上指定了15個候選算法。1999年3月22日第二次AES會議上，將候選名單減少為5個，這5個算法是RC6，Rijndael，SERPENT，Twofish和MARS。2000年4月13日，第三次AES會議上，對這5個候選算法的各種分析結(jié)果進(jìn)行了討論。2000年10月2日，NIST宣布了獲勝者Rijndael算法。2001年11月，NIST將AES定為聯(lián)邦信息處理標(biāo)準(zhǔn)FIPS PUB197。用于保護(hù)政府部門敏感但不機密的信息（sensitive but not classi

31、fied） 2002年5月正式生效。NIST對AES的評判標(biāo)準(zhǔn)安全性是最重要的判斷因素，包括：v算法對各種攻擊方法的抵抗能力；v算法的數(shù)學(xué)基礎(chǔ)的安全性證明；v算法輸出的隨機性；v與其他算法的安全性比較等。成本因素：v在各種不同平臺上的運行速度；v存儲空間的需求；v知識產(chǎn)權(quán)方面的成本。AES特點算法及其實現(xiàn)的特性考慮：1、簡單，因為簡單的算法才易于分析，如果有弱點也容易被發(fā)現(xiàn)；2、靈活，能夠在不同類型的應(yīng)用中安全有效地實現(xiàn)（如序列密碼、哈希函數(shù)等）；3、對于硬件/軟件實現(xiàn)的適應(yīng)性等。 分組長度為128bit， 密鑰長度為128 bits, 192 bits, 256 bits。 128-bit

32、key = 10輪 192-bit key = 12輪 256-bit key = 14輪AES框圖AES算法流程AES安全性沒有發(fā)現(xiàn)弱密鑰或補密鑰能有效抵抗目前已知的攻擊算法線性攻擊差分攻擊對稱密碼算法的優(yōu)缺點 優(yōu)點： 效率高，算法簡單，系統(tǒng)開銷小 適合加密大量數(shù)據(jù) 明文長度與密文長度相等 缺點： 需要以安全方式進(jìn)行密鑰交換 密鑰管理復(fù)雜小結(jié)DES是應(yīng)用最廣泛的對稱密碼算法（由于計算能力的快速進(jìn)展，DES已不再被認(rèn)為是安全的）；IDEA在歐洲應(yīng)用較多；AES將是未來最主要，最常用的對稱密碼算法。常用對稱密碼算法算法算法密鑰長度密鑰長度 迭代次數(shù)迭代次數(shù)數(shù)學(xué)運算數(shù)學(xué)運算應(yīng)用應(yīng)用DES5616X

33、OR, S-BoxKerberos,SET3DES112 or 16848XOR,S-BoxPGP,S/MIMEIDEA1288XOR, , PGPBlowFish最大最大44816XOR, S-Box,RC5最大最大2048255+,，XORCAST-1284012816+,，S-BoxPGP公鑰密碼算法3.1 公鑰密碼算法3.2 常用的公鑰密碼算法3.3 公鑰密碼算法的應(yīng)用公鑰密碼體制的思想 不同于以往的加密技術(shù)，公鑰密碼體制是建立在數(shù)學(xué)函數(shù)基礎(chǔ)上的，而不是建立在位方式的操作上的。更重要的是，與只使用單一密鑰的傳統(tǒng)加密技術(shù)相比，它在加/解密時，分別使用了兩個不同的密鑰：一個可對外界公開，稱

34、為“公鑰”；一個只有所有者知道，稱為“私鑰”。公鑰和私鑰之間具有緊密聯(lián)系，用公鑰加密的信息只能用相應(yīng)的私鑰解密，反之亦然。同時，要想由一個密鑰推知另一個密鑰，在計算上是不可能的。 公鑰密碼算法公鑰密碼的重要特性單向陷門函數(shù)公鑰密碼的重要特性 加密與解密由不同的密鑰完成加密: XY: Y = EKU(X)解密: YX: X = DKR(Y) = DKR(EKU(X) 知道加密算法，從加密密鑰得到解密密鑰在計算上是不可行的。 兩個密鑰中任何一個都可以用作加密而另一個用作解密（不是必須的）。X = DKR(EKU(X) = EKU(DKR(X)單向陷門函數(shù)(1)給定 x，計算 y=f(x) 是容易的

35、；(2)給定 y, 計算x使 y=f(x) 是困難的。(3)存在，已知 時，對給定的任何 y，若相應(yīng)的 x 存在，則計算 x 使 y=f(x)是容易的。注：1*. 僅滿足(1)、(2)兩條的稱為單向函數(shù)；第(3)條稱為陷門性， 稱為陷門信息。 2*. 當(dāng)用陷門函數(shù) f 作為加密函數(shù)時，可將 f 公開，這相當(dāng)于公開加密密鑰。該密鑰稱為公鑰，記為Pk。 f函數(shù)的設(shè)計者將 保密，用作解密密鑰，稱為私鑰，記為Sk。由于 f 是公開的，任何人都可將信息 x 加密成 y=f(x)，但只有設(shè)計者擁有Sk，因此僅有他可解出 x=f-1(y)。 3*.第(2)條性質(zhì)表明竊聽者由截獲的密文 y=f(x) 推測 x

36、 是不可行的。常用的公鑰密碼算法RSA (Rivest - Shamir Adleman），1977 在一個算法中實現(xiàn)簽名和加密 私鑰 = 簽名和解密 公鑰 = 簽名檢驗和加密 有專利權(quán)，2000年9月到期ECC（Elliptic Cure Crytosystem），1985 基于有限域上橢圓曲線有理點群的密碼系統(tǒng) 更快的具有更小密鑰長度的公開密碼系統(tǒng) 功能同RSA：數(shù)字簽名，密鑰管理，加密RSA公鑰密碼體制1977年由Ron Rivest、Adi Shamir和Len Adleman發(fā)明，1978年正式公布。RSA是一種分組加密算法。明文和密文在0n-1之間，n是一個正整數(shù)。該算法的數(shù)學(xué)基礎(chǔ)

37、是初等數(shù)論中的Euler（歐拉)定理，并建立在大整數(shù)因子的困難性之上。目前應(yīng)用最廣泛的公鑰密碼算法。只在美國申請專利，且已于2000年9月到期。(Left to Right: Ron ivest, Adi hamir, Len Adleman)2002年圖靈獎獲得者-RSA-2002RSA算法操作過程密鑰產(chǎn)生1. 取兩個大素數(shù) p, q , 保密;2. 計算n=pq，公開n;3. 計算歐拉函數(shù)(n) =(p-1)(q-1)；4. 任意取一個與(n) 互素的小整數(shù)e，即 gcd (e,(n) )=1; 1e(n)，公開e，作為公鑰用于加密（或簽名驗證）。5. 尋找d，使得： de 1 mod (

38、n) , 作為私鑰保密，即de =k(n) +1。 RSA 算法加密/解密過程 密鑰對（KU, KR）:KU=e, n , KR=d, n 加密過程：把待加密的內(nèi)容分成k比特的分組，k log2n，并寫成數(shù)字，設(shè)為M：C = Me mod n 解密過程M = Cd mod nRSA加密過程舉例p=7,q=17, n=7*17=119，(n)=(7-1)(17-1)=96選e=5, gcd (e, (n) = gcd (5, 96)=1;計算d，使得 ed 1 mod 96 , 即 ed= k*96+1, 取 k=4，則d= 77 公開(e,n)=(5,119)，將d 保密，丟棄p, q。明文：

39、m=19加密： 19 5 66 mod 119 , c= 66解密： 6677 mod 119 =? 用RSA算法進(jìn)行數(shù)字簽名mAlice: (KUa KRa), KUbEncryptHashKRaEKRa(H(m)mHashEncryptBob: (KUb KRb), KUaKUa= ?H(m)H(m)RSA 算法的安全性和性能攻擊方法 蠻力攻擊：對所有密鑰都進(jìn)行嘗試。 數(shù)學(xué)攻擊：等效于對兩個素數(shù)乘積(n)的因子分解。大數(shù)的因子分解是數(shù)論中的一個難題。運算速度運算速度橢圓曲線密碼體制 橢圓曲線上的離散對數(shù)問題 點Q和點P是有限域上的橢圓曲線的兩個點，在等式mP=P+P+P=Q中，已知m和點P

40、求點Q比較容易，反之已知點Q和點P求m卻是相當(dāng)困難的，這個問題稱為橢圓曲線上點群的離散對數(shù)問題。 橢圓曲線應(yīng)用到密碼學(xué)上最早是由Neal Koblitz 和Victor Miller在1985年分別獨立提出的。 橢圓曲線密碼體制是目前已知的公鑰體制中，對每比特所提供加密強度最高的一種體制。橢圓曲線密碼體制 橢圓曲線加密 基于橢圓曲線的ElGamal公鑰密碼算法 基于橢圓曲線的DSA（ECDSA） 橢圓曲線密鑰協(xié)商 基于橢圓曲線的密鑰協(xié)商問題，即ECC Diffie-Hellman 橢圓曲線簽密 基于橢圓曲線密碼體制的簽密方案 基于橢圓曲線密碼體制的（t,n）門限簽密方案ECC vs. RSAM

41、IPS年表示用每秒完成100萬條指令的計算機所需工作的年數(shù)ECC vs. RSAECC vs. RSAECC應(yīng)用 無線Modem的實現(xiàn) 對分組交換數(shù)據(jù)網(wǎng)加密，實現(xiàn)快速Deffie-Hellman密鑰交換 Web服務(wù)器的實現(xiàn) 可節(jié)省計算時間和帶寬 集成電路卡的實現(xiàn) ECC無需協(xié)處理器即可在標(biāo)準(zhǔn)卡上實現(xiàn)快速、安全的數(shù)字簽名，RSA難以實現(xiàn)ECC 的小結(jié) 安全性能更高（160位等同RSA的1024位） 計算量小，處理速度快 存儲空間占用小 帶寬要求低 應(yīng)用前景非常好，特別在移動通信、無線設(shè)備上的應(yīng)用。Diffie-Hellman算法 第一個發(fā)表的公開密鑰算法，1976 用于通信雙方安全地協(xié)商一個會話

42、密鑰 只能用于密鑰交換 基于離散對數(shù)計算的困難性 主要是模冪運算：a p mod n Diffie-Hellman 密鑰交換算法全局公開的參數(shù)：q 是一個素數(shù)，a q , a是q 的一個原根選擇一個私有的 ， 滿足：計算公開的 ： 選擇一個私有的 , 滿足：計算公開的 ： 計算會話密鑰 計算會話密鑰 EK(m)(modqayAxA)(modqayBxB)(mod)(qykAxB)(mod)(qykBxAqxAqxBAxBxAyByAyByAliceBobElGamal算法安全性基于離散對數(shù)問題（Discrete Logarithm Problem, DLP）缺點 需要隨機數(shù) 密文長度加倍準(zhǔn)備

43、公開參數(shù)：素數(shù)p，Zp*中本原元g， 私鑰a，公鑰b=ga mod p加密 對明文1=m=p-1，選隨機數(shù)k 密文(c1, c2)，c1=gk mod p, c2=mbk mod p解密 mc2 (c1a)-1mbk (gk)a)-1 m(ga)k (g-ka) m mod p數(shù)字簽名算法（DSA）1991年, NIST 提出了 數(shù)字簽名算法（DSA）,并把它用作數(shù)字簽名標(biāo)準(zhǔn)（DSS），招致大量的反對，理由如下： DSA 不能用于加密或密鑰分配 DSA是由 NSA研制的，可能有后門 DSA的選擇過程不公開，提供的分析時間不充分 DSA比RSA慢（1040倍） 密鑰長度太?。?12位） DSA可

44、能侵犯其他專利 RSA是事實上的標(biāo)準(zhǔn)公鑰密碼的應(yīng)用算法算法加加/解密解密數(shù)字簽名數(shù)字簽名密鑰交換密鑰交換RSA是是是是是是Dieffie-Hellman否否否否是是DSS否否是是否否 加密加密/解密解密 數(shù)字簽名數(shù)字簽名(身份鑒別身份鑒別) 密鑰交換密鑰交換基于公鑰密碼的加密過程AliceBob基于公鑰密碼的鑒別過程AliceBob基于公鑰密碼的密鑰交換User AUser BYaYb計算：計算：K=(Yb)Xa mod p計算計算K=(Ya)Xb mod p隨機生成隨機生成Xa p計算：計算：Ya=aXa mod p隨機生成隨機生成Xb p計算：計算：Yb=aXb mod pDiffie-H

45、ellman 密鑰交換算法密鑰交換算法對公鑰密碼算法的誤解公鑰密碼算法比對稱密碼算法更安全？ 任何一種現(xiàn)代密碼算法的安全性都依賴于密鑰長度、破譯密碼的工作量，從對抗分析角度，沒有一方更優(yōu)越。公鑰密碼算法使得對稱密碼算法成為了過時技術(shù)？ 公鑰密碼算法計算速度較慢，通常用于密鑰管理和數(shù)字簽名。 對稱密碼算法將長期存在。使用公開密鑰加密，密鑰分配變得非常簡單？ 密鑰分配既不簡單，也不有效。公鑰密碼體制的優(yōu)缺點 優(yōu)點： 解決密鑰傳遞的問題 大大減少密鑰持有量 提供了對稱密碼技術(shù)無法或很難提供的服務(wù)（數(shù)字簽名） 缺點： 計算復(fù)雜、耗用資源大 非對稱會導(dǎo)致得到的密文變長小結(jié) RSA 數(shù)學(xué)基礎(chǔ): IFP(I

46、nteger Factorization Problem) 加/解密、密鑰交換、數(shù)字簽名 使用最廣泛ECCElGamal 數(shù)學(xué)基礎(chǔ): DLP(Discrete Logarithm Problem) 加/解密、密鑰交換、數(shù)字簽名 DSA 作為數(shù)字簽名最好，并且無專利費，可以隨意獲取。 Diffie-Hellman 密鑰交換算法 哈希函數(shù)哈希函數(shù)概念MD5算法SHA-1算法消息鑒別碼數(shù)字簽名Hash函數(shù) Hash函數(shù)函數(shù)是將任意長度的消息映射成一個較短的定長輸出報文的函數(shù),如下形式: h = H(M), M是變長的報文,h是定長的散列值. 數(shù)學(xué)性質(zhì)：對任意給定的x, H(x) 易于(軟硬件實現(xiàn))計

47、算，且滿足： 單向性: 對任意給定的碼h, 尋求x使得H(x)=h 在計算上是不可行的; 弱抗碰撞性: 任意給定分組x, 尋求不等于x的y, 使得H(y)= H(x)在計算上不可行; 強抗碰撞性: 尋求對任何的(x, y)對, 使得 H(x)=H(y)在計算上不可行.Hash函數(shù)的特點 H能夠應(yīng)用到任意長度的數(shù)據(jù)上。 H能夠生成大小固定的輸出。 對干任意給定的x，H（x）的計算相對簡單。 對于給定的散列值h，要發(fā)現(xiàn)滿足H（x）h的x在計算上是不可行的。 對于給定的消息x，要發(fā)現(xiàn)另一個消息y滿足H（y）H（x）在計算上是不可行的。 主要的散列算法： MD5（128位）、SHA（160位）等bY0

48、nIV=CV0fbY1nfbYL-1nCVL-1fCV1nnIV = 初始值初始值CV = 鏈接值鏈接值Yi = 第第i 個輸入數(shù)據(jù)塊個輸入數(shù)據(jù)塊f = 壓縮算法壓縮算法n = 散列碼的長度散列碼的長度b = 輸入塊的長度輸入塊的長度安全安全Hash函數(shù)的一般結(jié)構(gòu)函數(shù)的一般結(jié)構(gòu)CVLCV0=IV= initial n-bit valueCVi=f(CVi-1, Yi-1) (1 i L)H(M) = CVLHash函數(shù)MD5 算法MD： Message Digest，消息摘要 輸入：任意長度的消息 輸出：128位消息摘要 處理：以512位輸入數(shù)據(jù)塊為單位MD5 (RFC 1321) devel

49、oped by Ron Rivest (“R” of the RSA )at MIT in 90s.MD5 算法流程SHA-1 算法 SHA（Secure Hash Algorithm，安全哈希算法 ）由美國國家標(biāo)準(zhǔn)技術(shù)研究所NIST開發(fā)，作為聯(lián)邦信息處理標(biāo)準(zhǔn)于1993年發(fā)表（FIPS PUB 180），1995年修訂，作為SHA-1(FIPS PUB 180-1)，SHA-1基于MD4設(shè)計。 輸入：最大長度為264位的消息； 輸出：160位消息摘要； 處理：輸入以512位數(shù)據(jù)塊為單位處理.SHA-1和MD5的一個循環(huán)比較SHA1/ MD5 散列值長度 MD5 128bits SHA1 160

50、bits 安全性 SHA1看來好些，但是SHA1的設(shè)計原則沒有公開 速度 SHA1慢些 （openssl speed md5/sha1:）type 16 bytes 64 bytes 256 bytes 1024 bytes 8192 bytesmd5 5425.31k 19457.48k 55891.45k 104857.60k 143211.40ksha1 5104.58k 16008.41k 37925.33k 57421.81k 68241.68k消息鑒別碼v在網(wǎng)絡(luò)通信中，有一些針對消息內(nèi)容的攻擊方法 偽造消息 竄改消息內(nèi)容 改變消息順序 消息重放或者延遲v消息認(rèn)證：對收到的消息進(jìn)行驗

51、證，證明確實是來自聲稱的發(fā)送方，并且沒有被修改過。 如果在消息中加入時間及順序信息，則可以完成對時間和順序的認(rèn)證消息認(rèn)證的三種方式 Message encryption：用整個消息的密文作為認(rèn)證標(biāo)識 接收方必須能夠識別錯誤 MAC：一個公開函數(shù)，加上一個密鑰產(chǎn)生一個固定長度的值作為認(rèn)證標(biāo)識 Hash function：一個公開函數(shù)將任意長度的消息映射到一個固定長度的散列值，作為認(rèn)證標(biāo)識MAC: Message Authentication Code 使用一個雙方共享密鑰生成一個固定大小的數(shù)據(jù)塊并加入到消息中稱為密碼校驗。 用戶A和用戶B，共享密鑰K，對于消息M， MAC=CK(M) 如果接收方

52、計算的MAC與收到的匹配，則 接收者可以確信消息M未被改變 接收者可以確信消息來自所聲稱的發(fā)送者 如果消息中含有序列號，則可以保證正確的消息順序 MAC函數(shù)類似于加密函數(shù)，但不需要可逆性。因此在數(shù)學(xué)上比加密算法被攻擊的弱點要少MAC 定義 MAC函數(shù) 取某個明文在Key的作用下的特征P | MAC(P, K) 驗證時，判斷明文和MAC是否相符 討論 MAC中可以使用對稱加密 MAC不需要可逆 這使MAC容易設(shè)計，也更不容易被破解 防范重放攻擊，加注時間、報文序號* 對稱MAC不能提供簽名特性MAC的動機 為了鑒別而加密整個報文不夠方便 對稱加密整個報文是個浪費 即使同時為了保密，也有另外的辦法

53、和體制 用非對稱加密速度太慢，每秒僅百來筆 后來引入了簽名體制 鑒別和加密的分離帶來靈活性 確實有時只要鑒別而不用(或不能)加密 如法律文書、公開信、聲明、公告、公證、鑒定等 如軟件鑒別/防病毒、網(wǎng)絡(luò)管理報文等MAC的用法引入哈希函數(shù) 在生成MAC的過程中，沒有必要整個報文被加密 MAC不需要能恢復(fù)原文 MAC的計算過程中體現(xiàn)的核心思想，就是把明文的特征唯一地體現(xiàn)到MAC中 因此，只要報文的某種形式的濃縮特征即可 Key還是必要的 從報文產(chǎn)生特征的數(shù)學(xué)方法HASH函數(shù) 先計算特征，再把特征加密的思想 于是就有了散列函數(shù)和MAC的結(jié)合MAC = C(Hash(Message), Key)哈希運算完整性用戶A用戶B數(shù)據(jù)數(shù)據(jù)哈希值哈希算法數(shù)據(jù)哈希值哈希值哈希算法如果哈希值匹配，說明數(shù)據(jù)有效 用戶A發(fā)送數(shù)據(jù)和哈希值給用戶 BHMAC 把HASH值和一個Key結(jié)合起來 沒有使用加密