密碼學概論第1講引論分析課件

1、密碼學概論朱曉玲（ZXL408）合肥工業(yè)大學計算機與信息學院2022/8/201課程學時 48 課程學分 3 周一周二周三周四周五上午1、2密碼學概論（1-13周）主樓116下午7、8密碼學概論（1-13周）主樓116考核形式：卷面70%，平時30%平時：出勤，作業(yè)，報告 課程安排與考核2022/8/202相關(guān)課程配置結(jié)構(gòu)圖(2011教學計劃)本課程地位：重要的理論和技術(shù)基礎(chǔ)！2022/8/203教材及參考書目現(xiàn)代密碼學第二版，楊波，清華大學出版社，2007密碼編碼學與網(wǎng)絡安全，William Stallings，電子工業(yè)出版社，2001；信息安全數(shù)學基礎(chǔ)，覃中平、張煥國等，清華大學出版社，2

2、006密碼學原理與實踐第二版，電子工業(yè)出版社，Douglas R Slinson著，2003歐密會、美密會、亞密會的高水平會議論文等2022/8/204課程內(nèi)容流密碼分組密碼消息認證和雜湊算法公鑰密碼密鑰分配與密鑰管理數(shù)字簽名和密碼協(xié)議網(wǎng)絡加密與認證2022/8/205第一章 引言1.1 信息安全面臨的威脅1.2 信息安全保障1.3 密碼學的發(fā)展1.4 密碼學的基本概念1.5 幾種古典密碼 2022/8/2062022/8/207保密性？可用性？完整性？真實性？信息安全含義：信息的保密性、完整性、可用性、真實性、不可抵賴性1.1 信息安全面臨的威脅2022/8/208自然威脅自然威脅可能來自于

3、各種自然災害、惡劣的場地環(huán)境、電磁輻射和電磁干擾、網(wǎng)絡設備自然老化等。人為威脅人為攻擊可分為被動攻擊和主動攻擊安全威脅分類2022/8/209保密性完整性真實性可控性不可抵賴性不可否認業(yè)務訪問控制認證業(yè)務保密業(yè)務完整性業(yè)務消息保密（所有消息、單個消息、一個消息中某個特定域）；對業(yè)務流實施保密用于保證通信的真實性；保證通信雙方的通信連接不能被第三方介入保證所接收的消息未經(jīng)復制、插入、篡改、重排或重放；對已毀壞的數(shù)據(jù)進行恢復用于防止通信雙方中的某一方對所傳輸消息的否認（發(fā)出和接收）防止對網(wǎng)絡資源的非授權(quán)訪問，控制的實現(xiàn)方式是認證(如口令)。密碼學是信息安全的核心 1.2 信息安全保障2022/8/

4、20102022/8/20111.3密碼學的發(fā)展三個階段：1949年之前密碼學是一門藝術(shù)19491975年密碼學成為科學1976年以后密碼學的新方向公鑰密碼學 2022/8/2012第1階段古典密碼 密碼學還不是科學,而是藝術(shù) 出現(xiàn)一些密碼算法和加密設備主要特點：數(shù)據(jù)的安全基于算法的保密20世紀早期密碼機2022/8/2013 計算機使得基于復雜計算的密碼成為可能 相關(guān)技術(shù)的發(fā)展1949年Shannon的“The Communication Theory of Secret Systems”，標志著密碼學成為科學（60頁）1967年David Kahn的The Codebreakers1971

5、-1973年IBM Watson實驗室的Horst Feistel等幾篇技術(shù)報告主要特點：數(shù)據(jù)的安全基于密鑰而不是算法的保密Kerchoffs提出這一編碼原則, 成為傳統(tǒng)密碼和現(xiàn)代密碼的分界線第2階段 1949-19752022/8/20141976年：Diffie & Hellman 的 “New Directions in Cryptography” 提出了不對稱密鑰； （12頁）1977年Rivest,Shamir & Adleman提出了RSA公鑰算法90年代逐步出現(xiàn)橢圓曲線等其他公鑰算法主要特點：公鑰密碼使得發(fā)送端和接收端無密鑰傳輸?shù)谋Ｃ芡ㄐ懦蔀榭赡?977年DES正式成為標準對稱密

6、鑰密碼進一步成熟 Rijndael,RC6, MARS,Twofish, Serpent等出現(xiàn)2001年Rijndael成為DES的替代者第3階段 1976-2022/8/2015 明文(消息)(Plaintext) ：被隱蔽消息。 密文(Ciphertext)或密報(Cryptogram)：明文經(jīng)密碼變換成的一種隱蔽形式。加密(Encryption)：將明文變換為密文的過程。解密(Decryption)：加密的逆過程，即由密文恢復出原明文的過程。加密員或密碼員(Cryptographer)：對明文進行加密操作的人員。1.3 密碼學的基本概念密碼學(Cryptology)：研究信息系統(tǒng)安全保密

7、的科學。2022/8/2016 加密算法(Encryption algorithm)：密碼員對明文進行加密時所采用的一組規(guī)則。解密算法：接收者對密文進行解密時所采用的一組規(guī)則。密鑰(Key)：控制加密和解密算法操作的數(shù)據(jù)處理，分別稱作加密密鑰和解密密鑰。接收者(Receiver)：傳送消息的預定對象。截收者(Eavesdropper)：在信息傳輸和處理系統(tǒng)中的非授權(quán)者，通過搭線竊聽、電磁竊聽、聲音竊聽等來竊取機密信息。2022/8/2017 密碼分析(Cryptanalysis)：截收者試圖通過分析從截獲的密文推斷出原來的明文或密鑰。 密碼分析員(Cryptanalyst)：從事密碼分析的人。

8、 被動攻擊(Passive attack)：對一個保密系統(tǒng)采取截獲密文進行分析的攻擊。 主動攻擊(Active attack)：非法入侵者(Tamper)、攻擊者(Attcker)或黑客(Hacker)主動向系統(tǒng)竄擾，采用刪除、增添、重放、偽造等竄改手段向系統(tǒng)注入假消息，達到利已害人的目的。2022/8/2018無條件安全和計算安全 無條件安全Shannon指出，僅當密鑰至少和明文一樣長時達到無條件安全（即一次一密） 計算安全 破譯密文的代價超過被加密信息的價值 破譯密文所花時間超過信息的有效期2022/8/2019密碼編碼學(Cryptography)，對信息進行編碼實現(xiàn)隱蔽信息的一門學問密

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

10、還靠點運氣。2022/8/20221.3.1 保密系統(tǒng)模型信源Mm加密器解密器接收者m非法接入者搭線信道（主動攻擊）C 搭線信道（被動攻擊）密碼分析員m密鑰源K1k1密鑰源K2k2密鑰信道明文消息空間M，密文消息空間C，密鑰空間K1和K2，在單鑰體制下K1=K2=K；總體(M,C,K1,K2,EK1,DK2)為保密通信系統(tǒng)2022/8/2023 保密系統(tǒng)應當滿足的要求系統(tǒng)即使達不到理論上是不可破的，即prm=m=0，也應當為實際上不可破的。就是說，從截獲的密文或某些已知明文密文對，要決定密鑰或任意明文在計算上是不可行的。(計算安全)系統(tǒng)的保密性不依賴于對加密體制或算法的保密，而依賴于密鑰。這是

11、著名的Kerckhoff原則。加密和解密算法適用于所有密鑰空間中的元素。系統(tǒng)便于實現(xiàn)和使用。2022/8/20241.3.2 密碼體制分類密碼體制有2大類：單鑰體制(One-key system)： 加密密鑰和解密密鑰相同。雙鑰體制(Two-key system)： 加密密鑰和解密密鑰不同。2022/8/2025密碼體制分類 單鑰體制加密器EK解密器DK密文明文明文K密鑰產(chǎn)生器K2022/8/2026分類：流密碼(Stream cipher)明文逐位加密分組密碼(Block cipher)明文逐組加密單鑰體制不僅可用于數(shù)據(jù)加密，也可用于消息的認證。單鑰體制研究熱點密鑰管理(Key manage

12、ment)。密鑰產(chǎn)生、分配、存儲、銷毀等2022/8/2027密碼體制分類 雙鑰體制雙鑰體制或公鑰體制(Public key system) (Diffie和Hellman,1976) 每個用戶都有一對選定的密鑰(公鑰k1；私鑰k2)，公開的密鑰k1可以像電話號碼一樣進行注冊公布。2022/8/2028公鑰體制的主要特點加密和解密能力分開可以實現(xiàn)多個用戶加密的消息只能由一個用戶解讀（用于公共網(wǎng)絡中實現(xiàn)保密通信）只能由一個用戶加密消息而使多個用戶可以解讀（可用于認證系統(tǒng)中對消息進行數(shù)字簽字）。無需事先分配密鑰。2022/8/2029對稱密碼加解密速度快適合文件加密密鑰管理困難非對稱密碼短消息加密

13、解決密鑰分配和管理問題，適合簽名和認證安全基礎(chǔ)基于一個數(shù)學困難問題綜合運用對稱密碼技術(shù)和非對稱密碼技術(shù)。比較2022/8/2030 1.3.3 密碼可能經(jīng)受的攻擊攻擊類型攻擊者擁有的資源惟密文攻擊加密算法截獲的部分密文已知明文攻擊加密算法，截獲的部分密文和相應的明文選擇明文攻擊加密算法加密黑盒子，可加密任意明文得到相應的密文選擇密文攻擊加密算法解密黑盒子，可解密任意密文得到相應的明文2022/8/2031上述攻擊的目的是確定所使用的密鑰。這四種攻擊類型的強度按序遞增，惟密文攻擊是最弱的攻擊。選擇密文攻擊是最強的一種攻擊。如果一個密碼系統(tǒng)能抵抗選擇密文攻擊 ，那么它能抵抗其余三種攻擊。2022/

14、8/2032密碼分析方法 -窮舉破譯法 對截收的密報依次用各種可解的密鑰試譯，直到得到有意義的明文；只要有足夠多的計算時間和存儲容量，原則上窮舉法總是可以成功的。但實際中，任何一種能保障安全要求的實用密碼都會設計得使這一方法在實際上是不可行的。 2022/8/2033常見的三字母組合：THE、ING、AND、HER、ERE、ENT、THA、NTH、WAS、ETH、FOR、DTH等。 常見的雙字母組合：TH、HE、IN、ER、RE、AN、ON、EN、AT；-統(tǒng)計分析法2022/8/2034其他分析方法線性分析差分分析插值攻擊生日攻擊等等2022/8/20351.4幾種古典密碼代換（Substit

15、ution）密碼。明文中的字母由其他字母、數(shù)字或符號所取代的一種方法 。單表代換多表代換置換（Permutation）密碼。換位就是重新排列消息中的字母。2022/8/2036著名的Caesar密碼設明文為：China加密: C：對應著字母F； h：對應著字母K； i：對應著字母L； n：對應著字母Q； a：對應著字母D。密文為“FKLQD”。Caesar密碼：據(jù)說愷撒率先使用，因此這種加密方法被稱為愷撒密碼?；舅枷胧牵和ㄟ^把字母移動一定的位數(shù)來實現(xiàn)加密和解密。例如，如果密匙是把明文字母的位數(shù)向后移動三位。2022/8/2037解密： F：對應著C； K：對應著H； L：對應著I； Q：對應

16、著N； D：對應著A。即“FKLQD”經(jīng)Caesar密碼解密恢復為“CHINA”(不區(qū)分大小寫) 2022/8/2038Caesar數(shù)學表示加密與解密算法：cE3(m) m+3 mod 26m D3(c) c-3 mod26屬于單字母簡單替換密碼-單表代換密碼結(jié)構(gòu)過于簡單建立字母和數(shù)字間對應關(guān)系2022/8/2039移位密碼c Ek(m) m+k mod 26m Dk(c) c-k mod26仿射密碼c Ea,b(m) am+b mod 26m Da,b(c) a-1(c-b) mod26 (a,26) 1考慮上述密碼的安全性所有單表代換密碼都難以經(jīng)受語言特性的統(tǒng)計攻擊，單表代換保持明文的統(tǒng)計

17、特性不變。加密明文hot。hot轉(zhuǎn)化為數(shù)字7，14和19。c Ea,b(m) 7m+3 mod 26密文串數(shù)字是為0，23和6，即AXG。其他的單表代換密碼2022/8/2040加密Ci AMi+B(mod N)解密Mi A-1(Ci-B)(mod N)A是mod N的n*n的可逆陣B一般取0向量Mi=（m1,m2,mn）T明文分組Ci=（c1,c2,cn）T密文分組i=1,2,多表代換密碼-Hill密碼2022/8/2041假定密鑰是A=加密明文july？兩個明文組ju (9，20)和ly(11，24)。july的加密是delw。對Hill密碼的已知明文攻擊？對Hill密碼的惟密文攻擊？完全

18、隱藏了單字母的頻率2022/8/2042Hill密碼的破譯(已知明文攻擊)輸入明文、密文各2個分組，設（m0,m1），（m2,m3）和對應的（c0,c1），（c2,c3）滿足A= mod 26。 2022/8/2043模m下逆矩陣的存在性判斷和求解在對于22矩陣A= ，如果逆矩陣存在，由線性代數(shù)A-1= 。在模26下， A-1 = ( )-1 mod 26。矩陣A的逆存在的充分條件是 在模26下存在逆元。2022/8/2044算法描述及實現(xiàn)選擇一個二階可逆方陣a，即 Hill 密碼的密鑰矩陣。將明文字符串轉(zhuǎn)化為數(shù)字。分組，每兩個數(shù)字作為一組m（2 維列向量），假設明文為偶數(shù)個字符。方陣a乘以m

19、，得新2 維列向量c=am mod 26。重復步驟，直到所有分組被加密。將數(shù)字轉(zhuǎn)化為密文字符串。加密算法描述2022/8/2045運行結(jié)果2022/8/2046單表代換與多表代換密碼比較單表代換密碼對單個字母密碼加密密碼分析許多統(tǒng)計信息未變換唯密文攻擊可行的多表代換密碼對多個字母同時密碼加密密碼分析統(tǒng)計信息隱藏已知明文攻擊可行多表代換密碼的破譯要比單表代換密碼難2022/8/2047置換密碼單表或多表密碼都是代換密碼置換密碼是重新排列消息中的字母，以便打破密文的結(jié)構(gòu)特性的密碼最簡單的置換密碼是把明文中字母順序倒過來如：cryptography加密為：yhpargotpyrc2022/8/204

20、8舉例明文：cryptography is an applied science密鑰：encry把明文按某一順序排成一個矩陣，然后按另一順序選出矩陣中字母形成密文密文：yripdn cohnii rgyaee paspsc tpalce 2022/8/2049M1 M2 M3 M4 M5 M6 M7 M8M9 M10 M11 M12 M13 M14 M15 M16 M17 M18 M19 M20 M21 M22 M23 M24M25 M26 M27 M28 M29 M30 M31 M32M33 M34 M35 M36 M37 M38 M39 M40M41 M42 M43 M44 M45 M46 M47 M48M49 M50 M51 M52 M53 M54 M55 M56M57 M58 M59 M60 M61 M62 M63 M64M58 M50 M42