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

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

2、來(lái)山得使用了原始的錯(cuò)亂密碼；公元前一世紀(jì)，古羅馬皇帝凱撒曾使用有序的單表代替密碼；1863年普魯士人卡西斯基所著密碼和破譯技術(shù)1883年法國(guó)人克爾克霍夫所著軍事密碼學(xué)20世紀(jì)初，產(chǎn)生了最初的可以實(shí)用的機(jī)械式和電動(dòng)式密碼機(jī)，同時(shí)出現(xiàn)了商業(yè)密碼機(jī)公司和市場(chǎng)。第二次世界大戰(zhàn)德國(guó)的Enigma密碼轉(zhuǎn)輪機(jī)，堪稱機(jī)械式古典密碼的巔峰之作。63.1 密碼術(shù)及發(fā)展1976年美國(guó)政府頒布數(shù)據(jù)加密標(biāo)準(zhǔn)（DES）。1976年Diffie和Hellman發(fā)表的文章密碼學(xué)的新動(dòng)向1978年R.L.Rivest，A.Shamir和L.Adleman實(shí)現(xiàn)了RSA公鑰密碼體制1969年哥倫比亞大學(xué)的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ā)布高級(jí)加密標(biāo)準(zhǔn)AES，替代DES作為商用密碼標(biāo)準(zhǔn)。73.1 密碼術(shù)及發(fā)展3.2 數(shù)據(jù)保密通信模型3.3 對(duì)稱密碼體制3.4 公鑰密碼體制3.5 數(shù)字簽名3.5 消息完整性保護(hù)3.6 認(rèn)證3.7 計(jì)算復(fù)雜理論3.8 密碼分析目 錄8

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

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

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

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

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

9、kpri（Private Key），kpriSK，算法Gen輸出私鑰kpri和對(duì)應(yīng)的公鑰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 密碼術(shù)及發(fā)展3.2 數(shù)據(jù)保密通信模型3.3 對(duì)稱密碼體制3.4 公鑰密碼體制3.5 數(shù)字簽名3.5 消息完整性保護(hù)3.6 認(rèn)證3.7 計(jì)算復(fù)雜理論3.8 密碼分析目 錄2425如何在電子世界中實(shí)現(xiàn)簽

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

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

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

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

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

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

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

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

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

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