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

密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第1頁學(xué)習(xí)目標(biāo)數(shù)據(jù)保密通信模型及基本術(shù)語對稱密碼體制及其分類與工作原理公鑰密碼體制及其工作原理數(shù)字署名技術(shù)及其特征消息完整性保護(hù)及認(rèn)證怎樣定義和衡量密碼體制安全性本章介紹密碼基本概念、分類、實(shí)現(xiàn)和應(yīng)用原理。2

密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第2頁3.1密碼術(shù)及發(fā)展3.2數(shù)據(jù)保密通信模型3.3對稱密碼體制3.4公鑰密碼體制3.5數(shù)字署名3.5消息完整性保護(hù)3.6認(rèn)證3.7計(jì)算復(fù)雜理論3.8密碼分析目錄3

密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第3頁什么是密碼術(shù)？4Cryptography?

密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第4頁3.1密碼術(shù)及發(fā)展保密性要求即使非授權(quán)者獲取了數(shù)據(jù)副本，他也無法從副本中取得有用信息。5

密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第5頁3.1密碼術(shù)及發(fā)展宋曾公亮、丁度等編撰《武經(jīng)總要》“字驗(yàn)”公元前4，斯巴達(dá)將領(lǐng)來山得使用了原始錯(cuò)亂密碼；公元前一世紀(jì)，古羅馬皇帝凱撒曾使用有序單表代替密碼；1863年普魯士人卡西斯基所著《密碼和破譯技術(shù)》

1883年法國人克爾克霍夫所著《軍事密碼學(xué)》20世紀(jì)初，產(chǎn)生了最初能夠?qū)嵱脵C(jī)械式和電動(dòng)式密碼機(jī)，同時(shí)出現(xiàn)了商業(yè)密碼機(jī)企業(yè)和市場。第二次世界大戰(zhàn)德國Enigma密碼轉(zhuǎn)輪機(jī)，堪稱機(jī)械式古典密碼巔峰之作。6密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第6頁3.1密碼術(shù)及發(fā)展1976年美國政府頒布數(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é)StephenWiesner首次提出“共軛編碼”概念。1984年H.Bennett和G.Brassard在此思想啟發(fā)下，提出量子理論BB84協(xié)議1985年Miller和Koblitz首次將有限域上橢圓曲線用到了公鑰密碼系統(tǒng)中。1989年R.Mathews,D.Wheeler,L.M.Pecora和Carroll等人首次把混沌理論使用到序列密碼及保密通信理論。NIST公布高級(jí)加密標(biāo)準(zhǔn)AES，替換DES作為商用密碼標(biāo)準(zhǔn)。7密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第7頁3.1密碼術(shù)及發(fā)展3.2數(shù)據(jù)保密通信模型3.3對稱密碼體制3.4公鑰密碼體制3.5數(shù)字署名3.5消息完整性保護(hù)3.6認(rèn)證3.7計(jì)算復(fù)雜理論3.8密碼分析目錄8密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第8頁9怎樣在開放網(wǎng)絡(luò)中保密傳輸數(shù)據(jù)？SecretTransmission?

密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第9頁10密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第10頁3.2數(shù)據(jù)保密通信模型對于m∈M，k1,k2∈K，有

，五元組（M,C,K,E,D）稱為一個(gè)密碼體制，其中E和D代表詳細(xì)密碼算法——詳細(xì)變換過程或數(shù)學(xué)方法。能夠看出，加密能夠看做是將密鑰與明文混合變換過程，而解密是從密文中剝離密鑰過程，所以也稱脫密過程。Kerchhoff假設(shè)：一個(gè)密碼體制，對于全部密鑰，加密和解密算法快速有效；密碼體制安全性不應(yīng)該依賴于算法保密，而僅依賴密鑰保密。11密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第11頁3.1密碼術(shù)及發(fā)展3.2數(shù)據(jù)保密通信模型3.3對稱密碼體制3.4公鑰密碼體制3.5數(shù)字署名3.5消息完整性保護(hù)3.6認(rèn)證3.7計(jì)算復(fù)雜理論3.8密碼分析目錄12密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第12頁13怎樣使用相同密鑰加/解密數(shù)據(jù)？SymmetricCryptography?密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第13頁14對稱密碼體制密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第14頁3.3對稱密碼體制對稱密碼體制分類：分組密碼先將明文劃分成若干等長塊——分組，如每個(gè)分組長64比特、128比特，然后再分別對每個(gè)分組進(jìn)行加密，得到等長密文分組。解密過程類似，有些密碼算法解密算法與加密算法完成一樣，如DES。序列密碼是把明文以位或字節(jié)為單位進(jìn)行加密，普通是與密鑰（如由密鑰種子產(chǎn)生任意長度字節(jié)流）進(jìn)行混合（最簡單地進(jìn)行異或運(yùn)算）取得密文序列。15

密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第15頁3.3對稱密碼體制兩個(gè)思想：擴(kuò)散（Diffusion）：即將明文及密鑰影響盡可能快速地散布到較多輸出密文中，經(jīng)典操作就是“置換”（Permutation）（如重新排列字符）?；靵y（Confusion）：目標(biāo)在于使作用于明文密鑰和密文之間關(guān)系復(fù)雜化，使得明文和密文、密文和密鑰之間統(tǒng)計(jì)相關(guān)特征極小化，從而使統(tǒng)計(jì)分析攻擊不能奏效。混亂通常采取“代換”（Substitution）操作。16密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第16頁17Feistel網(wǎng)絡(luò)結(jié)構(gòu)密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第17頁3.3對稱密碼體制序列密碼（流密碼）將明文流和密鑰流混合（普通為簡單按字節(jié)或比特位異或）產(chǎn)生密文流。流密碼使用一個(gè)“種子密鑰”產(chǎn)生密鑰流（理論上能夠是無限長度），通信雙方共享這個(gè)“種子密鑰”，按相同方式產(chǎn)生密鑰流。18密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第18頁3.1密碼術(shù)及發(fā)展3.2數(shù)據(jù)保密通信模型3.3對稱密碼體制3.4公鑰密碼體制3.5數(shù)字署名3.5消息完整性保護(hù)3.6認(rèn)證3.7計(jì)算復(fù)雜理論3.8密碼分析目錄19密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第19頁20怎樣方便地管理和使用密鑰？AsymmetricCryptography?密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第20頁3.4公鑰密碼體制21公鑰加密體制密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第21頁3.4公鑰密碼體制公鑰密碼就是一個(gè)陷門單向函數(shù)f。即：（1）對f定義域中任意x都易于計(jì)算f(x)，而對f值域中幾乎全部y，即使當(dāng)f為已知時(shí)要計(jì)算f-1(y)在計(jì)算上也是不可行。（2）當(dāng)給定一些輔助信息（陷門信息）時(shí)則易于計(jì)算f-1(y)。此時(shí)稱f是一個(gè)陷門單向函數(shù)，輔助信息（陷門信息）作為秘密密鑰。這類密碼普通要借助特殊數(shù)學(xué)問題，如數(shù)論中大數(shù)分解、離散對數(shù)等數(shù)學(xué)難解問題，結(jié)構(gòu)單向函數(shù)，所以，這類密碼安全強(qiáng)度取決于它所依據(jù)問題計(jì)算復(fù)雜度。22密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第22頁3.4公鑰密碼體制一個(gè)公鑰密碼體制是一個(gè)七元組(M,C,SK,PK,Gen,Enc,Dec)：明文空間M（Message消息，或Plantext），需要加密消息表示為m，m∈M。密文空間C（Ciphertext），明文m經(jīng)過加密變換為密文c，c∈C。私鑰空間SK（SecretKey），全部可能私鑰組成。公鑰空間PK（PublicKey），全部可能公鑰組成。密鑰生成算法Gen（KeyGenerationAlgorithm），從可能私鑰空間中隨機(jī)選取一個(gè)私鑰kpri（PrivateKey），kpri∈SK，算法Gen輸出私鑰kpri和對應(yīng)公鑰kpub（PubklicKey），kpub∈PK。加密算法Enc（EncryptionAlgorithm），給定明文m，m∈M，輸出密文c，c=Enc(m,kpub)，c∈C。解密算法Dec（DecryptionAlgorithm），給定密文c，c∈C，輸出明文m，m=Dec(c,kpri)，m∈M。23密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第23頁3.1密碼術(shù)及發(fā)展3.2數(shù)據(jù)保密通信模型3.3對稱密碼體制3.4公鑰密碼體制3.5數(shù)字署名3.5消息完整性保護(hù)3.6認(rèn)證3.7計(jì)算復(fù)雜理論3.8密碼分析目錄24密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第24頁25怎樣在電子世界中實(shí)現(xiàn)署名？Digital

Signature?密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第25頁3.5數(shù)字署名一個(gè)假想例子：某人甲要經(jīng)過網(wǎng)絡(luò)傳輸一份文檔給乙，乙接收到這份文檔，乙能確認(rèn)這份文檔真實(shí)性嗎（確實(shí)來自于甲，而不是其它人冒充甲發(fā)送）？乙能確定這份文檔正確性碼（在傳輸過程中沒有被篡改）？甲假如否定曾經(jīng)發(fā)送過該文檔（實(shí)際上確實(shí)是甲發(fā)送）怎么辦？26密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第26頁27數(shù)字署名機(jī)制密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第27頁3.5數(shù)字署名一個(gè)數(shù)字署名機(jī)制是使用一個(gè)公鑰密碼，使得一個(gè)消息接收者相信接收消息來自聲稱消息發(fā)送者（消息主體識(shí)別與判別），并信任該消息（消息被正確地傳遞，沒有被篡改——完整性保護(hù)），同時(shí)消息署名者不能否定簽發(fā)了該消息（不可否定性保護(hù)）。28密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第28頁3.5數(shù)字署名一個(gè)數(shù)字署名體制是一個(gè)七元組(M,S,SK,PK,Gen,Sig,Ver)：明文空間M（Message消息，或Plantext），對應(yīng)需要署名消息表示為m，m∈M。密文空間S（Signature），明文m經(jīng)過密碼變換輸出密文s，s∈S。私鑰空間SK（SecretKey），全部可能私鑰組成。公鑰空間PK（PublicKey），全部可能公鑰組成。密鑰生成算法Gen（KeyGenerationAlgorithm），從可能私鑰空間中隨機(jī)選取一個(gè)私鑰kpri（PrivateKey），kpri∈SK，算法Gen輸出私鑰kpri和對應(yīng)公鑰kpub（PubklicKey），kpub∈PK。署名算法Sig（SigningAlgorithm），給定明文m，m∈M，輸出署名s，s=Sig(m,kpri)，

s∈S。加密算法Ver（VerifyingAlgorithm），給定署名s，s∈S，驗(yàn)證署名v=Ver(s,kpuk)，輸出正確或錯(cuò)誤結(jié)果，v∈{True,False}。29密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第29頁30數(shù)字署名機(jī)制密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第30頁3.5數(shù)字署名密碼學(xué)哈希函數(shù)：密碼學(xué)哈希函數(shù)將任意長度輸入轉(zhuǎn)換為特定長度輸出，經(jīng)典算法如MD5、SHA、SHA-256等。一個(gè)密碼學(xué)哈希函數(shù)H應(yīng)具備以下特征：單向性：給定一個(gè)輸入m，輕易計(jì)算哈希值h=H(m)；但反過來，給定一個(gè)哈希值h，計(jì)算原像m是困難?？古鲎残裕阂阎粋€(gè)哈希值h=H(m)，找出另一個(gè)m’，使得H(m’)等于h是困難；同時(shí)任意找到兩個(gè)值c1、c2，使得這兩個(gè)數(shù)哈希值相同，即H(c1)=H(c2)，是困難。31密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第31頁帶署名加密封裝32密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第32頁3.1密碼術(shù)及發(fā)展3.2數(shù)據(jù)保密通信模型3.3對稱密碼體制3.4公鑰密碼體制3.5數(shù)字署名3.5消息完整性保護(hù)3.6認(rèn)證3.7計(jì)算復(fù)雜理論3.8密碼分析目錄33密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第33頁34怎樣保護(hù)通信數(shù)據(jù)完整性？Digital

Signature?密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第34頁3.5消息完整性保護(hù)循環(huán)冗余校驗(yàn)碼（CyclicRedundancyCheck，CRC）?數(shù)字署名?35密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第35頁3.5消息完整性保護(hù)消息認(rèn)證碼（MessageAuthenticationCode，MAC）——帶密碼摘要36密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第36頁3.5消息完整性保護(hù)一個(gè)基于HMAC應(yīng)用實(shí)例，使用HMAC完成一個(gè)經(jīng)典“質(zhì)詢/響應(yīng)”（Challenge/Response）身份認(rèn)證過程：（1）客戶端向服務(wù)器發(fā)出認(rèn)證請求，如一個(gè)登錄請求（假設(shè)是瀏覽器GET請求）。（2）服務(wù)器返回一個(gè)質(zhì)詢（Challenge），普通為一個(gè)隨機(jī)值，并在會(huì)話中統(tǒng)計(jì)這個(gè)隨機(jī)值。（3）客戶端將該隨機(jī)值作為輸入字符串，與用戶口令一起進(jìn)行HMAC運(yùn)算，然后提交計(jì)算結(jié)果給服務(wù)器——響應(yīng)（Response）。（4）服務(wù)器讀取用戶數(shù)據(jù)庫中用戶口令，并使用步驟2中發(fā)送隨機(jī)值做與客戶端一樣HMAC運(yùn)算，然后與用戶返回響應(yīng)比較，假如結(jié)果一致則驗(yàn)證了用戶是正當(dāng)。37密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第37頁3.1密碼術(shù)及發(fā)展3.2數(shù)據(jù)保密通信模型3.3對稱密碼體制3.4公鑰密碼體制3.5數(shù)字署名3.5消息完整性保護(hù)3.6認(rèn)證3.7計(jì)算復(fù)雜理論3.8密碼分析目錄38密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第38頁39怎樣驗(yàn)證主體身份或消息地真實(shí)性？Digital

Signature?密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第39頁3.6認(rèn)證認(rèn)證（也稱判別，Authentication）是證實(shí)一個(gè)對象身份過程，換句話講，指驗(yàn)證者（Verifier，普通為接收者）對認(rèn)證者（Authenticator，也稱證實(shí)者、示證者，又記Certifier，普通為發(fā)送方）身份真實(shí)性確實(shí)認(rèn)方法和過程。40密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第40頁3.6認(rèn)證對消息本身認(rèn)證，即回答“這個(gè)消息真實(shí)嗎？”、“這個(gè)消息正確嗎？”，換句話講，確認(rèn)這個(gè)消息是正當(dāng)用戶生成且在傳遞過程中沒有被篡改。41消息發(fā)送實(shí)體認(rèn)證，人或設(shè)備，即回答“是某人嗎？”、“是某臺(tái)設(shè)備嗎？”、“是某個(gè)軟件嗎？”。對實(shí)體認(rèn)證深入目標(biāo)，往往是為了決定將什么樣特權(quán)（Privilege）授權(quán)（Authorizing）給該身份實(shí)體。密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第41頁3.6認(rèn)證零知識(shí)證實(shí)——一個(gè)有趣“魔咒”認(rèn)證方法洞穴問題：如圖有一個(gè)洞穴，在洞穴深處C點(diǎn)與D點(diǎn)間有一道門，設(shè)P知道打開該門咒語，其它人不知道咒語無法打開此門。那么現(xiàn)在P怎樣向驗(yàn)證者V證實(shí)他知道咒語但又不告訴V咒語是什么呢？42密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第42頁3.1密碼術(shù)及發(fā)展3.2數(shù)據(jù)保密通信模型3.3對稱密碼體制3.4公鑰密碼體制3.5數(shù)字署名3.5消息完整性保護(hù)3.6認(rèn)證3.7計(jì)算復(fù)雜理論3.8密碼分析目錄43密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第43頁44怎樣定義一個(gè)密碼系統(tǒng)是安全？Digital

Signature?密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第44頁3.7計(jì)算復(fù)雜理論理論安全性（也稱無條件安全）：假如含有沒有限計(jì)算資源密碼分析者也無法破譯一個(gè)密碼系統(tǒng)（密碼體制），則稱該密碼系統(tǒng)是理論安全?？勺C實(shí)安全性：假如從理論上能夠證實(shí)破譯一個(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.安全定義密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第45頁3.7計(jì)算復(fù)雜理論運(yùn)算所需時(shí)間T和存放所需空間S，它們都是n函數(shù)，記為T(n)和S(n)，也稱為時(shí)間復(fù)雜度和空間復(fù)雜度。假如

，其中c>0，那么稱該算法運(yùn)算時(shí)間是多項(xiàng)式階。假如

，其中p(n)是關(guān)于n一個(gè)多項(xiàng)式，則稱該算法運(yùn)算時(shí)間是指數(shù)階。462.安全度量密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第46頁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ī)約為問題Y，而且Y本身就是NP問題，則稱Y是一個(gè)NP完全問題，記為NPC。假如能夠找到一個(gè)計(jì)算序列作為解密算法，那么密碼分析者在不知道計(jì)算序列情況下求解問題（稱為客觀求解）在計(jì)算上是不可行。473.計(jì)算理論密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第47頁目錄3.1密碼術(shù)及發(fā)展3.2數(shù)據(jù)保密通信模型3.3對稱密碼體制3.4公鑰密碼體制3.5數(shù)字署名3.5消息完整性保護(hù)3.6認(rèn)證3.7計(jì)算復(fù)雜理論3.8密碼分析48密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第48頁49怎樣攻擊密碼系統(tǒng)？Digital

Signature?密碼基本概念分類實(shí)現(xiàn)和應(yīng)用原理第49頁3.8密碼分析惟密文攻擊（Ciphertextonly）：破譯者已知東西只有兩樣：加密算法、待破譯密文。已知明文攻擊（Knownplaintext）：破譯者已知東西包含：加密算法和經(jīng)密鑰加密形成一個(gè)或多個(gè)明文-密文對，即知道一定數(shù)量密文和對應(yīng)明文。選擇明文攻擊（Chosenplaintext）：破譯者除了知道加密算法外，他還能夠選定明文消息，并能夠知道該明