密碼學(xué)概論第1講引論分析課件

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16、著N； D：對(duì)應(yīng)著A。即“FKLQD”經(jīng)Caesar密碼解密恢復(fù)為“CHINA”(不區(qū)分大小寫) 2022/8/2038Caesar數(shù)學(xué)表示加密與解密算法：cE3(m) m+3 mod 26m D3(c) c-3 mod26屬于單字母簡(jiǎn)單替換密碼-單表代換密碼結(jié)構(gòu)過(guò)于簡(jiǎn)單建立字母和數(shù)字間對(duì)應(yīng)關(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)受語(yǔ)言特性的統(tǒng)計(jì)攻擊，單表代換保持明文的統(tǒng)計(jì)

17、特性不變。加密明文hot。hot轉(zhuǎn)化為數(shù)字7，14和19。c Ea,b(m) 7m+3 mod 26密文串?dāng)?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？?jī)蓚€(gè)明文組ju (9，20)和ly(11，24)。july的加密是delw。對(duì)Hill密碼的已知明文攻擊？對(duì)Hill密碼的惟密文攻擊？完全

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

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

20、8舉例明文：cryptography is an applied science密鑰：encry把明文按某一順序排成一個(gè)矩陣，然后按另一順序選出矩陣中字母形成密文密文：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