保障與安全密碼

1、第三章 密碼學(xué),1、密碼學(xué)的發(fā)展 密碼學(xué)的歷史比較悠久，在四千年前，古埃及人就開始使用密碼來保密傳遞消息。兩千多年前，羅馬國王Julius Caesar（愷撒）就開始使用目前稱為“愷撒密碼”的密碼系統(tǒng)。但是密碼技術(shù)直到20世紀(jì)40年代以后才有重大突破和發(fā)展。特別是20世紀(jì)70年代后期，由于計(jì)算機(jī)、電子通信的廣泛使用，現(xiàn)代密碼學(xué)得到了空前的發(fā)展,密碼學(xué)基礎(chǔ),密碼學(xué)基礎(chǔ),2. 密碼學(xué)作為數(shù)學(xué)的一個(gè)分支，其相關(guān)科學(xué)大致可以分為3個(gè)方面,密碼編碼學(xué)：使消息保密的技術(shù)和科學(xué)（Cryptography），從事此行的叫密碼編碼者（Cryptographer）。 密碼分析學(xué)：破譯密文的技術(shù)和科學(xué)（Crypta

2、nalysis）密碼分析者是從事密碼分析的專業(yè)人員 密碼學(xué)（Cryptology）密碼學(xué)是一門秘密書寫、非授權(quán)解密以及使得非法解密更加困難的規(guī)則的科學(xué)，數(shù)學(xué)理論在目前的密碼學(xué)研究中發(fā)揮著非常重要的作用，其中包含數(shù)論、群論、組合邏輯、復(fù)雜性理論、遍歷理論以及信息論。 包括密碼編碼學(xué)和密碼分析學(xué)兩部分，精于此道的人稱為密碼學(xué)家（Cryptologist），現(xiàn)代的密碼學(xué)家通常也是理論數(shù)學(xué)家,密碼學(xué)的發(fā)展大致經(jīng)過3個(gè)階段： 第一階段是1949年之前，密碼學(xué)是一門藝術(shù)，這階段的研究特點(diǎn)是： 密碼學(xué)還不是科學(xué)，而是藝術(shù)； 出現(xiàn)一些密碼算法和加密設(shè)備； 密碼算法的基本手段出現(xiàn)，主要針對字符；簡單的密碼分析手

3、段出現(xiàn)，數(shù)據(jù)的安全基于算法的保密。 該階段具有代表性的事件是：1883年Kerchoffs第一次明確的提出了編碼的原則： 加密算法應(yīng)建立在算法的公開且不影響明文和密鑰的安全的基礎(chǔ)上。這個(gè)原則得到廣泛承認(rèn)，成為判定密碼強(qiáng)度的衡量標(biāo)準(zhǔn)，實(shí)際上也成為傳統(tǒng)密碼和現(xiàn)代密碼的分界線。 第二階段是1949-1975年，密碼學(xué)成為一門獨(dú)立的科學(xué)，該階段計(jì)算機(jī)的出現(xiàn)使基于復(fù)雜計(jì)算的密碼成為可能。主要研究特點(diǎn)是：數(shù)據(jù)安全基于密鑰而不是算法的保密,第三階段是1976年以后，密碼學(xué)中公鑰密碼學(xué)成為主要研究方向，該階段具有代表性的事件是： 1976年，Diffie和Hellman提出了不對稱密鑰。 1977年，Rive

4、st，Shamir和Adleman提出了RSA公鑰算法。 1977年，DES算法出現(xiàn)。 80年代，出現(xiàn)IDEA和CAST等算法。 90年代，對稱密鑰密碼算法進(jìn)一步成熟，Rijndael，RC6等出現(xiàn)，逐步出現(xiàn)橢圓曲線等其他公鑰算法。 2001年，Rijndael成為DES算法的替代者。 2004年8月，山東大學(xué)信息安全所所長王小云在國際會議上首次宣布了她及她的研究小組對MD5、HAVAL-128、MD4和RIPEMD等四個(gè)著名密碼算法的破譯結(jié)果，引起世界轟動(dòng)。這階段的主要特點(diǎn)是：公鑰密碼使得發(fā)送端和接收端無密鑰傳輸?shù)谋Ｃ芡ㄐ懦蔀榭赡?經(jīng)典密碼學(xué),經(jīng)典的密碼學(xué)是關(guān)于加密和解密的理論，主要用于保密

5、通信。目前，密碼學(xué)已經(jīng)得到了更加深入、廣泛的發(fā)展，其內(nèi)容已經(jīng)不再是單一的加解密技術(shù)，已被有效、系統(tǒng)地用于保證電子數(shù)據(jù)的保密性、完整性和真實(shí)性。保密性就是對數(shù)據(jù)進(jìn)行加密，使非法用戶無法讀懂?dāng)?shù)據(jù)信息，而合法用戶可以應(yīng)用密鑰讀取信息。完整性是對數(shù)據(jù)完整性的鑒別，以確定數(shù)據(jù)是否被非法篡改，保證合法用戶得到正確、完整的信息。真實(shí)性是數(shù)據(jù)來源的真實(shí)性、數(shù)據(jù)本身真實(shí)性的鑒別，可以保證合法用戶不被欺騙,現(xiàn)代密碼技術(shù),現(xiàn)代密碼技術(shù)的應(yīng)用已經(jīng)深入到數(shù)據(jù)處理過程的各個(gè)環(huán)節(jié)，包括：數(shù)據(jù)加密、密碼分析、數(shù)字簽名、信息鑒別、零知識認(rèn)證、秘密共享等。 密碼學(xué)的數(shù)學(xué)工具也更加廣泛，有概率統(tǒng)計(jì)、數(shù)論、代數(shù)、混沌和橢圓曲線等。常

6、用密碼學(xué)專業(yè)術(shù)語包括：消息和加密、鑒別、完整性和抗抵賴性、算法和密鑰、對稱算法和公開密鑰算法（非對稱算法），等等,基本概念,3. 加密（Encrypt)和解密(Decrypt,一般模型都假定Alice和Bob在一個(gè)不安全的信道上通信，而Eve作為第三者(或密碼分析者)總是企圖破譯Alice和Bob之間的通信內(nèi)容。Alice發(fā)送給Bob的信息，通常稱為明文(Plaintext),如英文單詞、數(shù)字符號或數(shù)據(jù),Alice事先用某個(gè)密鑰(Key)對要發(fā)送的信息進(jìn)行加密, 加密過的明文常稱為密文(Cipher Text),然后Alice將密文發(fā)給Bob。Eve可以竊聽到Alice發(fā)給Bob的信息，但無法

7、知道明文；而Bob收到密文后，能利用事先知道的密鑰對密文進(jìn)行解密而獲得明文,基本概念,3. 加密（Encrypt)和解密(Decrypt,通信過程,1) 通信雙方通過協(xié)商選擇并共享一個(gè)密鑰kK。 (2) 發(fā)送方使用加密函數(shù)Ek對明文串進(jìn)行加密得到密文C。 (3) 當(dāng)Bob接到密文串C時(shí)，他使用解密函數(shù)Dk對其進(jìn)行解密，就可以得到原始明文串m,基本概念,3. 加密（Encrypt)和解密(Decrypt,a) 對稱密碼體制,基本概念,3. 加密（Encrypt)和解密(Decrypt,3. 加密（Encrypt)和解密(Decrypt,非對稱密碼體制,4. 密碼學(xué)的作用,密碼學(xué)基礎(chǔ),除了提供機(jī)密

8、性外，密碼學(xué)需要提供三方面的功能：鑒別、完整性和抗抵賴性。這些功能是通過計(jì)算機(jī)進(jìn)行社會交流至關(guān)重要的需求。 機(jī)密性:提供只允許特定用戶訪問和閱讀信息，任何非授權(quán)用戶對信息都不可理解的服務(wù)通過數(shù)據(jù)加密實(shí)現(xiàn)。 數(shù)據(jù)完整性:提供確保數(shù)據(jù)在存儲和傳輸過程中不被未授權(quán)修改（竄改、刪除、插入和重放等）的服務(wù)。通過數(shù)據(jù)加密、數(shù)據(jù)散列或數(shù)字簽名來實(shí)現(xiàn),密碼學(xué)基礎(chǔ),鑒別:提供與數(shù)據(jù)和身份識別有關(guān)的服務(wù)。通過數(shù)據(jù)加密、數(shù)據(jù)散列或數(shù)字簽名來實(shí)現(xiàn) 抗否認(rèn)性:提供阻止用戶否認(rèn)先前的言論或行為的服務(wù)。通過對稱加密或非對稱加密，以及數(shù)字簽名等，并借助可信的注冊機(jī)構(gòu)或證書機(jī)構(gòu)的輔助，提供這種服務(wù),信源,加密機(jī),解密機(jī),接收者

9、,安全信道,密鑰源,竊聽者,x,y,x,k1,加密通信的模型,密鑰源,k2,不安全信道,密碼分析,Shannon模型,信息傳遞的一般問題,信源、信道、信宿 攻擊的種類： 中斷（Interruption)（干擾） 截?。↖nterception) (偵聽） 修改（Modification） 偽造（Fabrication) 角色：通信雙方、可信第三方、不可信第三方 介質(zhì)：軟件、硬件、數(shù)據(jù),數(shù)據(jù)的性質(zhì),Interruption - Interception - Modification - Fabrication,Availability,Availability,Availability,Conf

10、identiality,Availability,Integrity,Availability,Authenticity,時(shí)間性,被動(dòng)攻擊,竊聽,獲取消息內(nèi)容,流量分析,主動(dòng)攻擊,中斷,修改,偽造,破壞可用性,破壞完整性,破壞真實(shí)性,密碼體制,一個(gè)滿足下面條件的五元組(P,C,K,E,D)為一個(gè)密碼體制: (1) P是一個(gè)非空有限集合，表示所有的明文空間。 (2) C是一個(gè)非空有限集合，表示所有的密文空間。 (3) K是一個(gè)非空有限集合，表示所有的密鑰空間。 (4) 對任意的kK,都存在一個(gè)加密函數(shù)： Ek(E):PC 和相應(yīng)的解密函數(shù)： Dk(D):CP 對任意的明文mP均有Dk(Ek(m)

11、=m。其中Ek和Dk都必須是單射函數(shù),密碼學(xué)基礎(chǔ),5. 算法與密鑰,算法 是用于加密和解密的數(shù)學(xué)函數(shù) 受限制(restricted)的算法 算法的強(qiáng)度是基于保持算法的秘密 算法強(qiáng)度依賴于密鑰(K)的算法密鑰K的可能值的范圍叫做密鑰空間(keyspace,使用同一密鑰的加/解密(symmetric algorithm) 加密：EK（M）= C 解密：DK（C）= M 等效于 DK（EK（M）=M,密碼學(xué)基礎(chǔ),使用不同密鑰的加/解密(public-key) 加密：EK1（M）= C 解密：DK2（C）= M 等效于 DK2（EK1（M）=M,密碼學(xué)基礎(chǔ),基于密鑰的算法有兩類：對稱算法與公開密鑰算法

12、,密碼學(xué)基礎(chǔ),對稱算法 也叫傳統(tǒng)密碼算法（秘密密鑰算法、單鑰算法），就是加密密鑰能從解密密鑰中推算出來。反過來也成立 對稱算法的數(shù)學(xué)表示,加密：EK（M）= C 解密：DK（C）= M,對稱算法分類,密碼學(xué)基礎(chǔ),序列算法（stream algorithm) 一次只對明文中的單個(gè)位（或字節(jié)）進(jìn)行運(yùn)算的算法。 分組算法（block algorithm) 一次對明文的一組位進(jìn)行運(yùn)算，典型分組長度是64位,公開密鑰算法（public-key algorithm） 也叫非對稱算法,公鑰算法，公開密鑰算法的加密密鑰和解密密鑰不同，而且解密密鑰不能根據(jù)加密密鑰計(jì)算出來，或者至少在可以計(jì)算的時(shí)間內(nèi)不能計(jì)算出來

13、。 一般稱加密密鑰為公鑰（public-key），解密密鑰為私鑰（private-key）。比較著名的公鑰密碼算法有：RSA、背包密碼、McEliece密碼、Diffe-Hellman、Rabin、零知識證明的算法、橢圓曲線（Elliptic Curve）、ElGamal算法等等。RSA是最有影響的公鑰加密算法，它能夠抵抗到目前為止已知的所有密碼攻擊?，F(xiàn)今世界上廣為應(yīng)用的PGP郵件加密軟件就是基于RSA算法的,密碼學(xué)基礎(chǔ),公開密鑰算法特點(diǎn) 用作加密的密鑰（也稱公開密鑰）不同于用作解密的密鑰（也稱私人密鑰)。 解密密鑰不能根據(jù)加密密鑰推算出來。 加密密鑰能公開。 有時(shí)也用私人密鑰加密而用公開密鑰

14、解密，這主要用于數(shù)字簽名,6. 密碼協(xié)議,協(xié)議：一系列步驟，其目的是為完成一項(xiàng)任務(wù),密碼學(xué)基礎(chǔ),密碼協(xié)議：是使用密碼學(xué)的協(xié)議 對稱密碼通信（以Alice和Bob通信為例） Alice和Bob協(xié)商用同一密碼系統(tǒng) Alice和Bob協(xié)商同一密鑰 Alice用加密算法和選取的密鑰加密她的明文消息，得到了密文消息 Alice發(fā)送密文消息給Bob Bob用同樣的算法和密鑰解密密文 單向函數(shù),密碼學(xué)基礎(chǔ),例子 已知x，我們很容易計(jì)算f(x),但已知f(x)，卻難于計(jì)算出x. 單向函數(shù)的作用,密碼學(xué)基礎(chǔ),不能用作加密 使用單向函數(shù)進(jìn)行鑒別，其鑒別過程如下： Alice將她的口令傳送給計(jì)算機(jī) 計(jì)算機(jī)完成口令的

15、單向函數(shù)的計(jì)算 計(jì)算機(jī)把單向函數(shù)的運(yùn)算結(jié)果和它以前存儲的值進(jìn)行比較,密碼學(xué)基礎(chǔ),單向散列（Hash)函數(shù),功能 把可變輸入長度串（稱預(yù)映射，pre_image)轉(zhuǎn)換成固定長度的輸出串（稱散列值）。 特點(diǎn) 難于產(chǎn)生兩個(gè)預(yù)映射的值，使它們的散列值相同 散列函數(shù)是公開的，對處理過程不保密。 平均而言，預(yù)映射的單個(gè)位的改變，將引起散列值中一半以上位的改變,已知一個(gè)散列值，要找到預(yù)映射，使它的散列值等于已知的散列值在計(jì)算上是不可行的。 一般情況下，應(yīng)使用不帶密鑰的單向散列函數(shù)，以便任何人都能驗(yàn)證散列值。 說明： 消息鑒別碼（Message Authentication Code, MAC),它是帶有秘密

16、密鑰的單向散列函數(shù)，散列值是預(yù)映射的值和密鑰的函數(shù),密碼學(xué)基礎(chǔ),公開密碼通信（以Alice和Bob通信為例） Alice從數(shù)據(jù)庫中得到Bob的公開密鑰 Alice用Bob的公開密鑰加密消息， 然后發(fā)送給Bob Bob用自己的私人密鑰解密Alice發(fā)送的消息,混合密碼通信 Bob將他的公開密鑰發(fā)給Alice Alice產(chǎn)生隨機(jī)會話密鑰K，用Bob的公開密鑰加密，并把加密的密鑰EKBP(K)送給Bob,密碼學(xué)基礎(chǔ),Bob用他的私人密鑰解密Alice的消息，恢復(fù)出會話密鑰：DKBPri(EKBPub(K) = K 他們兩人用同一會話密鑰K對他們的通信消息進(jìn)行加密,密碼學(xué)基礎(chǔ),數(shù)字簽名（以采用公開密碼

17、技術(shù)為例） Alice用她的私人密鑰對文件加密，從而對文件簽名 Alice將簽名的文件傳給Bob Bob用Alice的公開密鑰解密文件，從而驗(yàn)證簽名,密鑰交換 對稱密碼學(xué)的密鑰交換 假設(shè)：Alice和Bob每人和KDC共享一個(gè)秘密密鑰，分別為,密碼學(xué)基礎(chǔ),密碼學(xué)基礎(chǔ),Alice呼叫KDC，并請求一個(gè)與Bob通信的會話密鑰 KDC產(chǎn)生一隨機(jī)會話密鑰，并對它的兩個(gè)副本加密：一個(gè)用，另一個(gè)用，KDC發(fā)這兩個(gè)副本給Alice Alice對她的會話密鑰的副本解密 Alice將Bob會話密鑰的副本轉(zhuǎn)發(fā)給Bob Bob對他的會話密鑰的副本解密 lice和Bob用這個(gè)會話密鑰安全的通信,密碼學(xué)基礎(chǔ),公開密碼學(xué)

18、的密鑰交換,密碼學(xué)基礎(chǔ),Alice從KDC提到Bob的公開密鑰 Alice產(chǎn)生出隨機(jī)會話密鑰，用Bob的公開密鑰加密它，然后將它傳給Bob Bob用他的私人密鑰解密Alice的消息 兩人用同一會話密鑰對他們的通信進(jìn)行加密,K= DKPri(EKPub(K,密碼學(xué)基礎(chǔ),密碼學(xué)基礎(chǔ),6密碼分析 密碼分析學(xué)是在不知道密鑰的情況下，恢復(fù)出明文的科學(xué)。成功的密碼分析能恢復(fù)出消息的明文或密鑰。密碼分析也可以發(fā)現(xiàn)密碼體制的弱點(diǎn)，最終得到上述結(jié)果。密鑰通過非密碼分析方式的丟失叫做泄露。 常用的密碼分析攻擊有四類。 （1）唯密文攻擊（Cipher Text-Only Attack）。密碼分析者有一些消息的密文，

19、這些消息都用同一加密算法加密。密碼分析者的任務(wù)是恢復(fù)盡可能多的明文，或者最好是能推算出加密消息的密鑰來，以便可采用相同的密鑰解出其他被加密的消息,密碼學(xué)基礎(chǔ),2）已知明文攻擊（Known-Plaintext Attack）。密碼分析者不僅可得到一些消息的密文，而且也知道這些消息的明文。分析者的任務(wù)就是用加密信息推出用來加密的密鑰或推導(dǎo)出一個(gè)算法，此算法可以對用同一密鑰加密的任何新的消息進(jìn)行解密,密碼學(xué)基礎(chǔ),3）選擇明文攻擊（Chosen-Plaintext Attack）。分析者不僅可得到一些消息的密文和相應(yīng)的明文，而且他們也可選擇被加密的明文。這比已知明文攻擊更有效。因?yàn)槊艽a分析者能選擇特定

20、的明文塊去加密，那些塊可能產(chǎn)生更多關(guān)于密鑰的信息，分析者的任務(wù)是推出用來加密消息的密鑰或?qū)С鲆粋€(gè)算法，此算法可以對用同一密鑰加密的任何新的消息進(jìn)行解密。(這種攻擊常常是通過跟蹤Alice發(fā)給Bob的明文串來分析。,密碼學(xué)基礎(chǔ),4）選擇密文攻擊（Chosen-Cipher Text Attack）。密碼分析者能選擇不同的被加密的密文，并可得到對應(yīng)的解密的明文，例如密碼分析者存取一個(gè)防竄改的自動(dòng)解密盒，密碼分析者的任務(wù)是推出密鑰。 （5）自適應(yīng)選擇明文攻擊（Adaptive-Chosen-Plaintext Attack）。這是選擇明文攻擊的特殊情況。密碼分析者不僅能選擇被加密的明文，而且也能基于

21、以前加密的結(jié)果修正這個(gè)選擇。在選擇明文攻擊中，密碼分析者還可以選擇一大塊被加密的明文，而在自適應(yīng)選擇密文攻擊中，可選取較小的明文塊，然后再基于第一塊的結(jié)果選擇另一明文塊，依此類推,密碼學(xué)基礎(chǔ),6）選擇密鑰攻擊（Chosen-Key Attack）。這種攻擊并不表示密碼分析者能夠選擇密鑰，它只表示密碼分析者具有不同密鑰之間的關(guān)系的有關(guān)知識。 （7）軟磨硬泡攻擊（Rubber-Hose Cryptanalysis）。這種攻擊是對密碼設(shè)計(jì)者威脅、勒索，或者折磨某人，直到他給出密鑰為止。行賄有時(shí)稱為購買密鑰攻擊（purchase-key attack）。這些是非常有效的攻擊，并且經(jīng)常是破譯算法的最好途

22、徑,7算法的安全性 不同的密碼算法具有不同的安全等級。如果破譯算法的代價(jià)大于加密數(shù)據(jù)的價(jià)值，破譯算法所需的時(shí)間比加密數(shù)據(jù)保密的時(shí)間更長，用單密鑰加密的數(shù)據(jù)量比破譯算法需要的數(shù)據(jù)量少得多，那么這種算法可能是安全的。 Shannon理論：僅當(dāng)密鑰至少和明文一樣長時(shí)才無條件安全。 如果不論密碼分析者有多少密文，都沒有足夠的信息恢復(fù)出明文，那么這個(gè)算法就是無條件保密的，只有一次一密亂碼本，才是無條件安全的。所有其它的密碼系統(tǒng)在唯密文攻擊中都是可破的 （蠻力攻擊,密碼學(xué)基礎(chǔ),破譯算法可分為不同的類別，安全性的遞減順序?yàn)椋?全部破譯。密碼分析者找出密鑰 K，這樣 DK（C）=P。 全盤推導(dǎo)。密碼分析者找到

23、一個(gè)代替算法在不知道密鑰 K的情況下，等價(jià)于DK（C）=P。 局部推導(dǎo)。密碼分析者從截獲的密文中找出明文。 信息推導(dǎo)。密碼分析者獲得一些有關(guān)密鑰或明文的信息。這些信息可能是密鑰的幾個(gè)位、有關(guān)明文格式的信息等,條件與工具： 已知加密消息，已知加密算法，截取到明文、密文中已知或推測的數(shù)據(jù)項(xiàng)，數(shù)學(xué)或統(tǒng)計(jì)工具和技術(shù)，語言特性，計(jì)算機(jī)，技巧與運(yùn)氣,加密算法的好與壞破譯難度 - 理論難度，如解密運(yùn)算需1012年（分析技巧可以降低破譯代價(jià)） - 運(yùn)算能力，飛速發(fā)展,密碼破譯,密碼破譯的原則: 遵循觀察與經(jīng)驗(yàn) 方法:采用歸納與演繹 步驟:分析、假設(shè)、推測和證實(shí) 三大要素： 語言的頻率特征： e 連接特征: q

24、 u, I e x, 重復(fù)特征: th, tion , tious,5. 英語字母使用頻率,第四章 傳統(tǒng)密碼學(xué),密碼學(xué)更關(guān)心在計(jì)算上不可破譯的密碼系統(tǒng)。如果一個(gè)算法用（現(xiàn)在或?qū)恚┛傻玫降馁Y源（公開數(shù)據(jù) ）都不能破譯，這個(gè)算法則被認(rèn)為在計(jì)算上是安全的。 可以用不同方式衡量攻擊方法的復(fù)雜性： 數(shù)據(jù)復(fù)雜性。用作攻擊輸入所需的數(shù)據(jù)量。 處理復(fù)雜性。完成攻擊所需要的時(shí)間，這個(gè)經(jīng)常叫做工作因素。 存儲需求。進(jìn)行攻擊所需要的存儲量。 作為一個(gè)法則，攻擊的復(fù)雜性取這三個(gè)因素的最小化，有些攻擊包括這三種復(fù)雜性的折中：存儲需求越大，攻擊可能越快,好”密碼體制的若干特性,1 Shannon標(biāo)準(zhǔn) 2 混淆(Diffusion) 與擴(kuò)散(Confusion) 3 完善保密性（Perfect Secrecy） 4 冗余度（Redundancy）與唯一解距離(Unicity Distance) 5 乘積密碼（Product Cipher） 6 編碼與密碼體制,1 Shannon標(biāo)準(zhǔn),1）為了確定加密和解密算法所必需的密文量應(yīng)擁有相當(dāng)?shù)膭趧?dòng)強(qiáng)度，也就是說，一個(gè)簡單的密碼體制它足以抵擋少量的密文的丟失，被竊或者抵擋一個(gè)攻擊者在很短時(shí)間內(nèi)擁有相當(dāng)?shù)拿芪摹?/p>