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

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

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

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

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

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

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

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

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

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

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

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

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

13、將明文劃分成字符流密碼是將明文劃分成字符( (如單個字母如單個字母) )，或其編碼，或其編碼的基本單元的基本單元( (如如0, 10, 1數(shù)字數(shù)字) )，字符分別與密鑰流作用進，字符分別與密鑰流作用進行加密，解密時以同步產生的同樣的密鑰流實現(xiàn)。行加密，解密時以同步產生的同樣的密鑰流實現(xiàn)。n流密碼強度完全依賴于密鑰序列的隨機性流密碼強度完全依賴于密鑰序列的隨機性( (Randomness)Randomness)和不可預測性和不可預測性( (Unpredictability)Unpredictability)。n核心問題是密鑰流生成器的設計核心問題是密鑰流生成器的設計。n保持收發(fā)兩端密鑰流的精確同

14、步是實現(xiàn)可靠解密的關保持收發(fā)兩端密鑰流的精確同步是實現(xiàn)可靠解密的關鍵技術鍵技術。2022-5-2625流密碼的框圖流密碼的框圖kI 安 全 信 道 kI KG KG ki ki mi ci ci mi Eki(mi) Eki(mi)2022-5-2626 流密碼的框圖流密碼的框圖n消息流：消息流：m=m1m2mi，其中，其中mi M。n密文流：密文流：c=c1c2ci=Ek1(m1)Ek2(m2) Eki(mi)，ci C。n密鑰流：密鑰流：ki，i 0。 一個完全隨機的非周期序列，可以實現(xiàn)一次一密體制。但一個完全隨機的非周期序列，可以實現(xiàn)一次一密體制。但需要無限存儲單元和復雜的輸出邏輯函數(shù)需

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

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