現(xiàn)代密碼學(xué)第2講

1、2022-2-281第二章：第二章：密碼學(xué)基礎(chǔ)一、密碼學(xué)的基本概念一、密碼學(xué)的基本概念二、密碼體制分類二、密碼體制分類三、密碼分析三、密碼分析2022-2-282一、密碼學(xué)的基本概念一、密碼學(xué)的基本概念密碼學(xué)密碼學(xué)(Cryptology)：研究信息系統(tǒng)安全保密的科學(xué)。它包含兩個分支，密碼編碼學(xué)密碼編碼學(xué)(Cryptography)，對信息進(jìn)行編碼實(shí)現(xiàn)隱蔽信息的一門學(xué)問密碼分析學(xué)密碼分析學(xué)(Cryptanalytics)，研究分析破譯密碼的學(xué)問。2022-2-283 幾個概念（一）幾個概念（一）。 = 明文明文(消息)(Plaintext) ：被隱蔽消息。= 密文密文(Ciphertext)或密

2、報密報(Cryptogram)：明文經(jīng)密碼變換成的一種隱蔽形式。=加密加密(Encryption)：將明文變換為密文的過程。=解密解密(Decryption)：加密的逆過程，即由密文恢復(fù)出原明文的過程。加密員加密員或密碼員密碼員(Cryptographer)：對明文進(jìn)行加密操作的人員。2022-2-284 幾個概念（二）幾個概念（二）。 =加密算法加密算法(Encryption algorithm)：密碼員對明文進(jìn)行加密時所采用的一組規(guī)則。=接收者接收者(Receiver)：傳送消息的預(yù)定對象。=解密算法：解密算法：接收者對密文進(jìn)行解密時所采用的一組規(guī)則。=密鑰密鑰(Key)：控制加密和解密算

3、法操作的數(shù)據(jù)處理，分別稱作加密密鑰加密密鑰和解密密鑰解密密鑰。截收者截收者(Eavesdropper)：在信息傳輸和處理系統(tǒng)中的非受權(quán)者，通過搭線竊聽、電磁竊聽、聲音竊聽等來竊取機(jī)密信息。2022-2-285幾個概念（三）幾個概念（三） = 密碼分析密碼分析(Cryptanalysis)：截收者試圖通過分析從截獲的密文推斷出原來的明文或密鑰。 密碼分析員密碼分析員(Cryptanalyst)：從事密碼分析的人。 被動攻擊被動攻擊(Passive attack)：對一個保密系統(tǒng)采取截獲密文進(jìn)行分析的攻擊。 主動攻擊主動攻擊(Active attack)：非法入侵者入侵者(Tamper)、攻擊者攻

4、擊者(Attcker)或黑客黑客(Hacker)主動向系統(tǒng)竄擾，采用刪除、增添、重放、偽造等竄改手段向系統(tǒng)注入假消息，達(dá)到利已害人的目的。2022-2-286保密系統(tǒng)模型保密系統(tǒng)模型信源Mm加密器)(1mEck解密器)(2cDmk接收者m非法接入者搭線信道（主動攻擊）C 搭線信道（被動攻擊）密碼分析員m密鑰源K1k1密鑰源K2k2密鑰信道2022-2-287 保密系統(tǒng)應(yīng)當(dāng)滿足的要求保密系統(tǒng)應(yīng)當(dāng)滿足的要求l系統(tǒng)即使達(dá)不到理論上是不可破的，即prmm=m m=0，也應(yīng)當(dāng)為實(shí)際上不可破的。就是說，從截獲的密文或某些已知明文密文對，要決定密鑰或任意明文在計(jì)算上是不可行的。l系統(tǒng)的保密性不依賴于對加密體

5、制或算法的保密，而依賴于密鑰。這是著名的Kerckhoff原則。l加密和解密算法適用于所有密鑰空間中的元素。l系統(tǒng)便于實(shí)現(xiàn)和使用。2022-2-288認(rèn)證與認(rèn)證系統(tǒng)認(rèn)證與認(rèn)證系統(tǒng)n認(rèn)證系統(tǒng)認(rèn)證系統(tǒng)(Authentication system) 防止消息被竄改、刪除、重放和偽造的一種有效方法,使發(fā)送的消息具有被驗(yàn)證的能力，使接收者或第三者能夠識別和確認(rèn)消息的真?zhèn)巍?shí)現(xiàn)這類功能的密碼系統(tǒng)稱作認(rèn)證系統(tǒng)n保密性保密性 保密性是使截獲者在不知密鑰條件下不能解讀密文的內(nèi)容。n認(rèn)證性認(rèn)證性 使任何不知密鑰的人不能構(gòu)造一個密報，使意定的接收者解密成一個可理解的消息(合法的合法的消息)。2022-2-289安全

6、認(rèn)證系統(tǒng)應(yīng)滿足下述條件安全認(rèn)證系統(tǒng)應(yīng)滿足下述條件l意定的接收者能夠檢驗(yàn)和證實(shí)消息的合法性和真實(shí)性。l消息的發(fā)送者對所發(fā)送的消息不能抵賴。l除了合法消息發(fā)送者外，其它人不能偽造合法的消息。而且在已知合法密文c c和相應(yīng)消息m m下，要確定加密密鑰或系統(tǒng)地偽造合法密文在計(jì)算上是不可行的。l必要時可由第三者作出仲裁。2022-2-2810 完整性完整性(integrity) 在有自然和人為干擾條件下，系統(tǒng)保持檢測錯誤和恢復(fù)消息和原來發(fā)送消息一致性的能力。實(shí)際中常常借助于糾、檢錯技術(shù)和雜湊技術(shù)來保證消息的完整性。2022-2-2811二、密碼體制分類二、密碼體制分類n密碼體制有密碼體制有2大類：大類：

7、n單鑰體制單鑰體制(One-key system)： 加密密鑰和解密密鑰相同。n雙鑰體制雙鑰體制(Two key system)： 加密密鑰和解密密鑰不同。2022-2-2812密碼體制分類密碼體制分類 單鑰體制單鑰體制加密器EK解密器DK密文明文明文K密鑰產(chǎn)生器K2022-2-2813密碼體制分類密碼體制分類 單鑰體制單鑰體制n單鑰體制主要研究問題：單鑰體制主要研究問題：n密鑰產(chǎn)生(Key generation)，n密鑰管理(Key management)。n分類：分類：n流密碼(Stream cipher)n分組密碼(Block cipher)n單鑰體制不僅可用于數(shù)據(jù)加密，也可用單鑰體制不

8、僅可用于數(shù)據(jù)加密，也可用于消息的認(rèn)證于消息的認(rèn)證。2022-2-2814密碼體制分類密碼體制分類 雙鑰體制雙鑰體制雙鑰體制雙鑰體制或公鑰體制公鑰體制(Public key system) (Diffie和Hellman,1976) 每個用戶都有一對選定的密鑰(公鑰k k1；私鑰k k2)，公開的密鑰k k1可以像電話號碼一樣進(jìn)行注冊公布。2022-2-2815公鑰體制的主要特點(diǎn)公鑰體制的主要特點(diǎn)n加密和解密能力分開n可以實(shí)現(xiàn)多個用戶加密的消息只能由一個用戶解讀（用于公共網(wǎng)絡(luò)中實(shí)現(xiàn)保密通信）n只能由一個用戶加密消息而使多個用戶可以解讀（可用于認(rèn)證系統(tǒng)中對消息進(jìn)行數(shù)字簽字）。n無需事先分配密鑰。2

9、022-2-2816三、密碼分析三、密碼分析 截收者在不知道解密密鑰及通信者所采用的加密體制的細(xì)節(jié)條件下，對密文進(jìn)行分析，試圖獲取機(jī)密信息。研究分析解密規(guī)律的科學(xué)稱作密碼分析學(xué)。密碼分析在外交、軍事、公安、商業(yè)等方面都具有重要作用，也是研究歷史、考古、古語言學(xué)和古樂理論的重要手段之一。2022-2-2817密碼分析密碼分析 密碼設(shè)計(jì)和密碼分析是共生的、又是互逆的，兩者密切有關(guān)但追求的目標(biāo)相反。兩者解決問題的途徑有很大差別 密碼設(shè)計(jì)是利用數(shù)學(xué)來構(gòu)造密碼 密碼分析除了依靠數(shù)學(xué)、工程背景、語言學(xué)等知識外，還要靠經(jīng)驗(yàn)、統(tǒng)計(jì)、測試、眼力、直覺判斷能力，有時還靠點(diǎn)運(yùn)氣。2022-2-2818密碼分析方法密

10、碼分析方法-窮舉破譯法窮舉破譯法 對截收的密報依次用各種可解的密鑰試譯，直到得到有意義的明文； 或在不變密鑰下，對所有可能的明文加密直到得到與截獲密報一致為止，此法又稱為完全試湊法完全試湊法(Complete trial-and-error Method)。 只要有足夠多的計(jì)算時間和存儲容量，原則上窮舉法總是可以成功的。但實(shí)際中，任何一種能保障安全要求的實(shí)用密碼都會設(shè)計(jì)得使這一方法在實(shí)際上是不可行的。 2022-2-2819密碼分析方法密碼分析方法分析法分析法 確定性分析法確定性分析法 利用一個或幾個已知量(比如，已知密文或明文-密文對)用數(shù)學(xué)關(guān)系式表示出所求未知量(如密鑰等)。已知量和未知量

11、的關(guān)系視加密和解密算法而定，尋求這種關(guān)系是確定性分析法的關(guān)鍵步驟。 統(tǒng)計(jì)分析法統(tǒng)計(jì)分析法 利用明文的已知統(tǒng)計(jì)規(guī)律進(jìn)行破譯的方法。密碼破譯者對截收的密文進(jìn)行統(tǒng)計(jì)分析，總結(jié)出其間的統(tǒng)計(jì)規(guī)律，并與明文的統(tǒng)計(jì)規(guī)律進(jìn)行對照比較，從中提取出明文和密文之間的對應(yīng)或變換信息。2022-2-2820 密碼可能經(jīng)受的攻擊密碼可能經(jīng)受的攻擊攻擊類型攻擊者擁有的資源惟密文攻擊n加密算法n截獲的部分密文已知明文攻擊n加密算法，n截獲的部分密文和相應(yīng)的明文選擇明文攻擊n加密算法n加密黑盒子，可加密任意明文得到相應(yīng)的密文選擇密文攻擊n加密算法n解密黑盒子，可解密任意密文得到相應(yīng)的明文2022-2-2821無條件安全和計(jì)算安

12、全無條件安全和計(jì)算安全 無條件安全無條件安全 如果算法產(chǎn)生的密文不能給出唯一決定相應(yīng)明文的足夠信息，無論截獲多少密文，花費(fèi)所少時間都不能解密密文。 Shannon指出，僅當(dāng)密鑰至少和明文一樣長時達(dá)到無條件安全（即一次一密） 計(jì)算安全計(jì)算安全 破譯密文的代價超過被加密信息的價值 破譯密文所花時間超過信息的有效期2022-2-2822第三章第三章 流密碼流密碼一、流密碼的基本概念一、流密碼的基本概念二、線性反饋移位寄存器序列二、線性反饋移位寄存器序列三三、B-M綜合算法綜合算法四、非線性序列四、非線性序列2022-2-2823一、流密碼的基本概念一、流密碼的基本概念2022-2-2824 流密碼的

13、基本概念流密碼的基本概念n流密碼是將明文劃分成字符流密碼是將明文劃分成字符( (如單個字母如單個字母) )，或其編碼，或其編碼的基本單元的基本單元( (如如0, 10, 1數(shù)字?jǐn)?shù)字) )，字符分別與密鑰流作用進(jìn)，字符分別與密鑰流作用進(jìn)行加密，解密時以同步產(chǎn)生的同樣的密鑰流實(shí)現(xiàn)。行加密，解密時以同步產(chǎn)生的同樣的密鑰流實(shí)現(xiàn)。n流密碼強(qiáng)度完全依賴于密鑰序列的隨機(jī)性流密碼強(qiáng)度完全依賴于密鑰序列的隨機(jī)性( (Randomness)Randomness)和不可預(yù)測性和不可預(yù)測性( (Unpredictability)Unpredictability)。n核心問題是密鑰流生成器的設(shè)計(jì)核心問題是密鑰流生成器的

14、設(shè)計(jì)。n保持收發(fā)兩端密鑰流的精確同步是實(shí)現(xiàn)可靠解密的關(guān)保持收發(fā)兩端密鑰流的精確同步是實(shí)現(xiàn)可靠解密的關(guān)鍵技術(shù)鍵技術(shù)。2022-2-2825流密碼的框圖流密碼的框圖kI 安 全 信 道 kI KG KG ki ki mi ci ci mi Eki(mi) Eki(mi)2022-2-2826 流密碼的框圖流密碼的框圖n消息流：消息流：m=m1m2mi，其中，其中mi M。n密文流：密文流：c=c1c2ci=Ek1(m1)Ek2(m2) Eki(mi)，ci C。n密鑰流：密鑰流：ki，i 0。 一個完全隨機(jī)的非周期序列，可以實(shí)現(xiàn)一次一密體制。但一個完全隨機(jī)的非周期序列，可以實(shí)現(xiàn)一次一密體制。但需要

15、無限存儲單元和復(fù)雜的輸出邏輯函數(shù)需要無限存儲單元和復(fù)雜的輸出邏輯函數(shù)f f。 i i是第是第i i時刻時刻密鑰流生成器的內(nèi)部狀態(tài)，以存儲單元的存數(shù)矢量描述。密鑰流生成器的內(nèi)部狀態(tài)，以存儲單元的存數(shù)矢量描述。n加法流密碼：加法流密碼： ci=Eki(mi)=mi ki2022-2-2827有限狀態(tài)自動機(jī)有限狀態(tài)自動機(jī)FA(Finite state Automation)n具有離散輸入和輸出（輸入集和輸出集均具有離散輸入和輸出（輸入集和輸出集均有限）的一種數(shù)學(xué)模型有限）的一種數(shù)學(xué)模型n有限狀態(tài)集有限狀態(tài)集S=si|i=1,2,ln有限輸入字符集有限輸入字符集X= Xi|i=1,2,mn有限輸出字符

16、集有限輸出字符集Y= Yk|k=1,2,nn轉(zhuǎn)移函數(shù)轉(zhuǎn)移函數(shù)nYjf 1(sj ,Xj)nSj+1 f 2(sj ,Xj)第第j時刻輸入時刻輸入Xj X ，輸出輸出YjY 2022-2-2828例2-1nS=s1,s2,s3,X=x1, x2,x3,Y=(y1,y2,y3)n轉(zhuǎn)移函數(shù)轉(zhuǎn)移函數(shù)f1x1x2X3s1s2s3y1y2y3y3y1y2y2y3y1f2x1x2X3s1s2s3s2s3s1s1s2s3s3s1s22022-2-2829FA的狀態(tài)圖表示 若輸入為若輸入為x1x2x1x3x3x1初始狀態(tài)初始狀態(tài)s1輸出為輸出為y1y1y2y1y3y12022-2-2830作為作為FAFA的密鑰流產(chǎn)生器的密鑰流產(chǎn)生器n同步流密碼的密鑰流產(chǎn)生器可同步流密碼的密鑰流產(chǎn)生器可看為一個參數(shù)為看為一個參數(shù)為k的的FAFAn輸出集輸出集Z Z，狀態(tài)集，狀態(tài)集，狀態(tài)轉(zhuǎn)移，狀態(tài)轉(zhuǎn)移函數(shù)函數(shù)和輸出函數(shù)和輸出函數(shù)，初態(tài)，初態(tài) 0 0n設(shè)計(jì)的關(guān)鍵是設(shè)計(jì)的