密碼基本概念、分類、實現(xiàn)和應用原理

1、學習目標數(shù)據(jù)保密通信模型及基本術語對稱密碼體制及其分類與工作原理公鑰密碼體制及其工作原理數(shù)字簽名技術及其特性消息完整性保護及認證如何定義和衡量密碼體制的安全性本章介紹密碼基本概念、分類、實現(xiàn)和應用原理。23.1 密碼術及發(fā)展3.2 數(shù)據(jù)保密通信模型3.3 對稱密碼體制3.4 公鑰密碼體制3.5 數(shù)字簽名3.5 消息完整性保護3.6 認證3.7 計算復雜理論3.8 密碼分析目 錄3什么是密碼術？4Cryptography?3.1 密碼術及發(fā)展保密性要求即使非授權者獲取了數(shù)據(jù)副本，他也無法從副本中獲得有用的信息。53.1 密碼術及發(fā)展宋曾公亮、丁度等編撰武經(jīng)總要“字驗”公元前405年，斯巴達的將領

2、來山得使用了原始的錯亂密碼；公元前一世紀，古羅馬皇帝凱撒曾使用有序的單表代替密碼；1863年普魯士人卡西斯基所著密碼和破譯技術1883年法國人克爾克霍夫所著軍事密碼學20世紀初，產(chǎn)生了最初的可以實用的機械式和電動式密碼機，同時出現(xiàn)了商業(yè)密碼機公司和市場。第二次世界大戰(zhàn)德國的Enigma密碼轉(zhuǎn)輪機，堪稱機械式古典密碼的巔峰之作。63.1 密碼術及發(fā)展1976年美國政府頒布數(shù)據(jù)加密標準（DES）。1976年Diffie和Hellman發(fā)表的文章密碼學的新動向1978年R.L.Rivest，A.Shamir和L.Adleman實現(xiàn)了RSA公鑰密碼體制1969年哥倫比亞大學的Stephen Wiesn

3、er首次提出“共軛編碼” 概念。1984年H. Bennett 和G. Brassard在此思想啟發(fā)下，提出量子理論BB84協(xié)議1985年Miller和Koblitz首次將有限域上的橢圓曲線用到了公鑰密碼系統(tǒng)中。1989年R.Mathews, D.Wheeler, L.M.Pecora和Carroll等人首次把混沌理論使用到序列密碼及保密通信理論。2001年NIST發(fā)布高級加密標準AES，替代DES作為商用密碼標準。73.1 密碼術及發(fā)展3.2 數(shù)據(jù)保密通信模型3.3 對稱密碼體制3.4 公鑰密碼體制3.5 數(shù)字簽名3.5 消息完整性保護3.6 認證3.7 計算復雜理論3.8 密碼分析目 錄8

4、9如何在開放網(wǎng)絡中保密傳輸數(shù)據(jù)？Secret Transmission?103.2 數(shù)據(jù)保密通信模型對于mM，k1,k2K，有 ，五元組（M,C,K,E,D）稱為一個密碼體制，其中E和D代表具體的密碼算法具體的變換過程或數(shù)學方法?？梢钥闯觯用芸梢钥醋鍪菍⒚荑€與明文混合變換的過程，而解密是從密文中剝離密鑰的過程，因此也稱脫密過程。Kerchhoff假設：一個密碼體制，對于所有的密鑰，加密和解密算法迅速有效；密碼體制的安全性不應該依賴于算法的保密，而僅依賴密鑰的保密。113.1 密碼術及發(fā)展3.2 數(shù)據(jù)保密通信模型3.3 對稱密碼體制3.4 公鑰密碼體制3.5 數(shù)字簽名3.5 消息完整性保護3.

5、6 認證3.7 計算復雜理論3.8 密碼分析目 錄1213如何使用相同的密鑰加/解密數(shù)據(jù)？Symmetric Cryptography?14對稱密碼體制3.3 對稱密碼體制對稱密碼體制分類：分組密碼先將明文劃分成若干等長的塊分組，如每個分組長64比特、128比特，然后再分別對每個分組進行加密，得到等長的密文分組。解密過程類似，有些密碼算法解密算法與加密算法完成一樣，如DES。序列密碼是把明文以位或字節(jié)為單位進行加密，一般是與密鑰（如由密鑰種子產(chǎn)生的任意長度的字節(jié)流）進行混合（最簡單地進行異或運算）獲得密文序列。153.3 對稱密碼體制兩個思想：擴散（Diffusion）：即將明文及密鑰的影響盡

6、可能迅速地散布到較多的輸出密文中，典型操作就是“置換”（Permutation）（如重新排列字符）。混亂（Confusion）：目的在于使作用于明文的密鑰和密文之間的關系復雜化，使得明文和密文、密文和密鑰之間的統(tǒng)計相關特性極小化，從而使統(tǒng)計分析攻擊不能奏效?；靵y通常采用“代換” （Substitution）操作。1617Feistel網(wǎng)絡結構3.3 對稱密碼體制序列密碼（流密碼）將明文流和密鑰流混合（一般為簡單的按字節(jié)或比特位異或）產(chǎn)生密文流。流密碼使用一個“種子密鑰”產(chǎn)生密鑰流（理論上可以是無限長度），通信雙方共享這個“種子密鑰”，按相同方式產(chǎn)生密鑰流。183.1 密碼術及發(fā)展3.2 數(shù)據(jù)保

7、密通信模型3.3 對稱密碼體制3.4 公鑰密碼體制3.5 數(shù)字簽名3.5 消息完整性保護3.6 認證3.7 計算復雜理論3.8 密碼分析目 錄1920如何方便地管理和使用密鑰？Asymmetric Cryptography?3.4 公鑰密碼體制21公鑰加密體制3.4 公鑰密碼體制公鑰密碼就是一種陷門單向函數(shù)f。即：（1）對f的定義域中的任意x都易于計算f(x)，而對f的值域中的幾乎所有的y，即使當f為已知時要計算f-1(y)在計算上也是不可行的。（2）當給定某些輔助信息（陷門信息）時則易于計算f-1(y)。此時稱f是一個陷門單向函數(shù)，輔助信息（陷門信息）作為秘密密鑰。這類密碼一般要借助特殊的數(shù)

8、學問題，如數(shù)論中的大數(shù)分解、離散對數(shù)等數(shù)學難解問題，構造單向函數(shù)，因此，這類密碼的安全強度取決于它所依據(jù)的問題的計算復雜度。223.4 公鑰密碼體制一個公鑰密碼體制是一個七元組(M,C,SK,PK,Gen,Enc,Dec)：明文空間M（Message消息，或Plantext），需要加密的消息表示為m，mM。密文空間C（Ciphertext），明文m經(jīng)過加密變換為密文c，cC。私鑰空間SK（Secret Key），所有可能的私鑰構成。公鑰空間PK（Public Key），所有可能的公鑰構成。密鑰生成算法Gen（Key Generation Algorithm），從可能的私鑰空間中隨機選取一個私鑰

9、kpri（Private Key），kpriSK，算法Gen輸出私鑰kpri和對應的公鑰kpub（Pubklic Key），kpubPK。加密算法Enc（Encryption Algorithm），給定明文m，mM，輸出密文c，c=Enc(m, kpub)，cC。解密算法Dec（Decryption Algorithm），給定密文c，cC，輸出明文m，m=Dec(c, kpri)，mM。233.1 密碼術及發(fā)展3.2 數(shù)據(jù)保密通信模型3.3 對稱密碼體制3.4 公鑰密碼體制3.5 數(shù)字簽名3.5 消息完整性保護3.6 認證3.7 計算復雜理論3.8 密碼分析目 錄2425如何在電子世界中實現(xiàn)簽

10、名？DigitalSignature?3.5 數(shù)字簽名一個假想的例子：某人甲要通過網(wǎng)絡傳輸一份文檔給乙，乙接收到這份文檔，乙能確認這份文檔的真實性嗎（確實來自于甲，而不是其他人冒充甲發(fā)送的）？乙能確定這份文檔的正確性碼（在傳輸過程中沒有被篡改）？甲如果否認曾經(jīng)發(fā)送過該文檔（實際上確實是甲發(fā)送的）怎么辦？2627數(shù)字簽名機制3.5 數(shù)字簽名一個數(shù)字簽名機制是使用一種公鑰密碼，使得一個消息接收者相信接收的消息來自聲稱的消息發(fā)送者（消息主體的識別與鑒別），并信任該消息（消息被正確地傳遞，沒有被篡改完整性保護），同時消息簽名者不能否認簽發(fā)了該消息（不可否認性保護）。283.5 數(shù)字簽名一個數(shù)字簽名體制

11、是一個七元組(M, S, SK, PK, Gen, Sig, Ver)：明文空間M（Message消息，或Plantext），對應需要簽名的消息表示為m，mM。密文空間S（Signature），明文m經(jīng)過密碼變換輸出密文s，sS。私鑰空間SK（Secret Key），所有可能的私鑰構成。公鑰空間PK（Public Key），所有可能的公鑰構成。密鑰生成算法Gen（Key Generation Algorithm），從可能的私鑰空間中隨機選取一個私鑰kpri（Private Key），kpriSK，算法Gen輸出私鑰kpri和對應的公鑰kpub（Pubklic Key），kpubPK。簽名算法S

12、ig（Signing Algorithm），給定明文m，mM，輸出簽名s，s=Sig(m, kpri)， sS。加密算法Ver（Verifying Algorithm），給定簽名s，sS，驗證簽名v=Ver(s, kpuk)，輸出正確或錯誤的結果，vTrue,False。2930數(shù)字簽名機制3.5 數(shù)字簽名密碼學哈希函數(shù)：密碼學哈希函數(shù)將任意長度輸入轉(zhuǎn)換為特定長度輸出，典型的算法如MD5、SHA、SHA-256等。一個密碼學哈希函數(shù)H應具備以下特性：單向性：給定一個輸入m，容易計算哈希值h=H(m)；但反過來，給定一個哈希值h，計算原像m是困難的?？古鲎残裕阂阎粋€哈希值h=H(m)，找出另一

13、個m，使得H(m)等于h是困難的；同時任意找到兩個值c1、c2，使得這兩個數(shù)的哈希值相同，即H(c1)= H(c2)，是困難的。31帶簽名加密封裝323.1 密碼術及發(fā)展3.2 數(shù)據(jù)保密通信模型3.3 對稱密碼體制3.4 公鑰密碼體制3.5 數(shù)字簽名3.5 消息完整性保護3.6 認證3.7 計算復雜理論3.8 密碼分析目 錄3334如何保護通信數(shù)據(jù)的完整性？DigitalSignature?3.5 消息完整性保護循環(huán)冗余校驗碼（Cyclic Redundancy Check，CRC）?數(shù)字簽名?353.5 消息完整性保護消息認證碼（Message Authentication Code，MAC

14、）帶密碼的摘要363.5 消息完整性保護一個基于HMAC的應用實例，使用HMAC完成一個典型的“質(zhì)詢/響應”（Challenge/Response）身份認證過程：（1）客戶端向服務器發(fā)出認證請求，如一個登錄請求（假設是瀏覽器的GET請求）。（2）服務器返回一個質(zhì)詢（Challenge），一般為一個隨機值，并在會話中記錄這個隨機值。（3）客戶端將該隨機值作為輸入字符串，與用戶口令一起進行HMAC運算，然后提交計算結果給服務器響應（Response）。（4）服務器讀取用戶數(shù)據(jù)庫中的用戶口令，并使用步驟2中發(fā)送的隨機值做與客戶端一樣的HMAC運算，然后與用戶返回的響應比較，如果結果一致則驗證了用戶是

15、合法的。373.1 密碼術及發(fā)展3.2 數(shù)據(jù)保密通信模型3.3 對稱密碼體制3.4 公鑰密碼體制3.5 數(shù)字簽名3.5 消息完整性保護3.6 認證3.7 計算復雜理論3.8 密碼分析目 錄3839如何驗證主體的身份或消息地真實性？DigitalSignature?3.6 認證認證（也稱鑒別，Authentication）是證明一個對象身份的過程，換句話講，指驗證者（Verifier，一般為接收者）對認證者（Authenticator，也稱證明者、示證者，又記Certifier，一般為發(fā)送方）身份的真實性的確認方法和過程。403.6 認證對消息自身的認證，即回答“這個消息真實嗎？”、“這個消息正

16、確嗎？”，換句話講，確認這個消息是合法用戶生成的且在傳遞過程中沒有被篡改。41消息發(fā)送實體認證，人或設備，即回答“是某人嗎？”、“是某臺設備嗎？”、“是某個軟件嗎？”。對實體認證的進一步目的，往往是為了決定將什么樣的特權（Privilege）授權（Authorizing）給該身份的實體。3.6 認證零知識證明一種有趣的“魔咒”認證方法洞穴問題：如圖有一個洞穴，在洞穴深處C點與D點間有一道門，設P知道打開該門的咒語，其他人不知道咒語無法打開此門。那么現(xiàn)在P如何向驗證者V證明他知道咒語但又不告訴V咒語是什么呢？423.1 密碼術及發(fā)展3.2 數(shù)據(jù)保密通信模型3.3 對稱密碼體制3.4 公鑰密碼體制

17、3.5 數(shù)字簽名3.5 消息完整性保護3.6 認證3.7 計算復雜理論3.8 密碼分析目 錄4344如何定義一個密碼系統(tǒng)是安全的？DigitalSignature?3.7 計算復雜理論理論安全性（也稱無條件安全）：如果具有無限計算資源的密碼分析者也無法破譯一個密碼系統(tǒng)（密碼體制），則稱該密碼系統(tǒng)是理論安全的?？勺C明安全性：如果從理論上可以證明破譯一個密碼系統(tǒng)的代價（困難性）不低于求解某個已知的數(shù)學難題，則稱該密碼系統(tǒng)是可證安全的。計算安全性：如果使用已知的最好的算法和利用現(xiàn)有的（或密碼系統(tǒng)生命周期內(nèi)）最大的計算資源仍然不可能在合理的時間完成破譯一個密碼系統(tǒng)，則稱該密碼系統(tǒng)是計算安全的。451.

18、 安全的定義3.7 計算復雜理論運算所需的時間T和存儲所需的空間S，它們都是n的函數(shù)，記為T(n)和S(n)，也稱為時間復雜度和空間復雜度。如果 ，其中c0，那么稱該算法運算的時間是多項式階的。如果 ，其中p(n)是關于n的一個多項式，則稱該算法運算時間是指數(shù)階的。462. 安全的度量3.7 計算復雜理論使用確定算法可以在多項式時間內(nèi)求解的問題稱為P問題。在多項式時間內(nèi)可以用非確定性算法求解的問題稱為NP問題。如果一個問題X可以在多項式時間內(nèi)用確定性算法轉(zhuǎn)化為問題Y，而Y的解可以在多項式時間內(nèi)用確定性算法轉(zhuǎn)化為X的解，則稱問題X可以規(guī)約化為問題Y。因此，如果某類NP問題中任何一個問題可以規(guī)約為

19、問題Y，而且Y本身就是NP問題，則稱Y是一個NP完全問題，記為NPC。如果能夠找到一個計算序列作為解密算法，那么密碼分析者在不知道計算序列的情況下求解問題（稱為客觀求解）在計算上是不可行的。473. 計算理論目 錄3.1 密碼術及發(fā)展3.2 數(shù)據(jù)保密通信模型3.3 對稱密碼體制3.4 公鑰密碼體制3.5 數(shù)字簽名3.5 消息完整性保護3.6 認證3.7 計算復雜理論3.8 密碼分析4849如何攻擊密碼系統(tǒng)？DigitalSignature?3.8 密碼分析惟密文攻擊（Ciphertext only）：破譯者已知的東西只有兩樣：加密算法、待破譯的密文。已知明文攻擊（Known plaintext）：破譯者已知的東西包括：加密算法和經(jīng)密鑰加密形成的一個或多個明文-密文對，即知道一定數(shù)量的密文和對應的明文。選擇明文攻擊（Chosen plaintext）：破譯者除了知道加密算法外，他還可以選定明文消息，并可以知道該明文對應的加密密文。例如，公鑰密碼體制中，攻擊者可以利用公鑰加密他任意選定的明文。503.8 密碼分析選擇密文攻擊(Cho