1、 網(wǎng)絡(luò)與信息安全公鑰密碼和消息認(rèn)證陳宇峰湖北汽車工業(yè)學(xué)院電氣與信息工程學(xué)院Email：13.3 公鑰加密原理回顧一下常規(guī)加密算法的兩個(gè)基本手段是擴(kuò)散和混亂現(xiàn)代加密算法一般都遵循Feistel結(jié)構(gòu)另一個(gè)重要問題是要解決密鑰的分配和共享KDC，關(guān)鍵是密鑰交換協(xié)議2網(wǎng)友小榕打算用E-mail將自己寫的小說加密發(fā)送給網(wǎng)友老狼，但是小榕與老狼之間從未有過密碼通信的約定。如何使老狼能夠讀懂加密的文件呢？假設(shè)小榕與老狼之間的任何E-mail都可能被第三方監(jiān)測到。顯然，如果小榕在E-mail中告訴老狼解密方法，那么讀到E-mail的其他人也能解密讀懂小榕的小說。如何設(shè)計(jì)一個(gè)方案，使得小榕與老狼之間通過若干次E

2、-mail的來往就能夠建立起密碼通信，并且使得監(jiān)聽了他們所有E-mail的人無法破譯小榕的加密文件。問題13Alice委托Bob按照他的指示股票交易假設(shè)Alice指示Bob以10美元的價(jià)格賣出了1萬股股票，不久，該股票升為20美元。Alice起了貪心，一口咬定從未發(fā)過賣出股票的指示，Bob如何辨白？假設(shè)Bob私自以10美元的價(jià)格賣出了1萬股股票，不久，該股票升為20美元。Alice此時(shí)發(fā)現(xiàn)，但Bob一口咬定是遵照Alice的指示賣出股票的，Alice如何證明？問題24素?cái)?shù)： 素?cái)?shù)p是大于1且因子僅為 1和p 的整數(shù)。為簡單起見，下面僅涉及非負(fù)整數(shù)設(shè)a、b為整數(shù)，且不全為0，gcd(a,b)表示

3、a和b的最大公因子如果gcd(a,b)=1，稱a和b互為素?cái)?shù)（互素）。即a和b僅有一個(gè)公因子13.3.0 一點(diǎn)預(yù)備知識(shí)5模運(yùn)算給定任一正整數(shù)n 和任一整數(shù)a，如果用a 除以n，得到商q和余數(shù)r，則以下關(guān)系成立：a = qn + r 0r n如果a是一個(gè)整數(shù)，而n 是一個(gè)正整數(shù)，則定義 a mod n 為a 除以n 的余數(shù)。例如，30 mod 7 = 2注意：如果a mod n = 0，則n是a的一個(gè)因子一點(diǎn)預(yù)備知識(shí)6模運(yùn)算的一些性質(zhì)(a mod n) + (b mod n) mod n = (a + b) mod n(a mod n) - (b mod n) mod n = (a - b) m

4、od n(a mod n) X (b mod n) mod n = (a X b) mod n 若(a X b) mod n = (a X c) mod n，則b mod n = c mod n 一點(diǎn)預(yù)備知識(shí)7如果（a mod n）（b mod n），則稱整數(shù)a 和b 模n 同余，記為a b (mod n)模運(yùn)算的同余性質(zhì)如果n 能夠整除(a b)，即n|(a b) ，則a b mod n反之，如果a b mod n，則n 能夠整除(a b)，即n|(a b)例如：23 8 = 15，而15能夠被5整除， 因此23 8 mod 5， 23和8是模5同余的。一點(diǎn)預(yù)備知識(shí)8公開密鑰加密算法是整個(gè)密

5、碼學(xué)發(fā)展歷史中最偉大的一次革命，也許可以說是唯一的一次革命公開密鑰加密算法依賴于數(shù)學(xué)函數(shù)而不依賴于替代和置換公開密鑰加密算法是非對(duì)稱的，使用兩個(gè)獨(dú)立的密鑰，因此又稱非對(duì)稱加密算法3.3.1 公鑰加密思想9公開密鑰加密在防范密碼攻擊上比常規(guī)加密更安全實(shí)際上，兩者都依賴于密鑰長度和解密的計(jì)算工作量，從抗密碼分析的角度抗，互相之間都不比對(duì)方優(yōu)越公開密鑰加密使得常規(guī)加密過時(shí)實(shí)際上，公開密鑰加密在計(jì)算上相對(duì)的巨大開銷，使得公開密鑰加密更多地用于密鑰管理和數(shù)字簽名應(yīng)用相對(duì)于傳統(tǒng)加密使用密鑰分發(fā)中心的握手協(xié)議，感覺使用公鑰密碼時(shí)密鑰分發(fā)是微不足道的實(shí)際上，公鑰密碼除需要協(xié)議外，還需要中心代理，因此公鑰加密的

6、操作并不簡單或者高效澄清公開密鑰加密算法的誤解10公鑰密碼使得發(fā)送端和接收端在不共享任何秘密消息（密鑰）的前提下即可交換大量秘密信息（實(shí)現(xiàn)保密通信）成為可能！解決密鑰的分配和共享問題解決密鑰組合爆炸的問題公鑰密碼也使得發(fā)送端和接收端在實(shí)現(xiàn)保密通信的同時(shí)各自依然可以保有秘密（私鑰）成為可能！解決數(shù)字簽名問題公鑰加密的兩個(gè)核心11一個(gè)公開密鑰模型由六要素組成：明文（Plaintext）公鑰（Public key）私鑰（Private key）加密算法（Encryption Algorithm）密文（Ciphertext）解密算法（Decryption Algorithm）公開密鑰加密的核心在于基于

7、一個(gè)單向函數(shù)（one-way function，函數(shù)計(jì)算很容易，但逆運(yùn)算不可行）設(shè)計(jì)算法公鑰加密原理每個(gè)用戶生成一對(duì)密鑰對(duì)消息進(jìn)行加密和解密其中一個(gè)密鑰公開，即公鑰；另一個(gè)自己保存，即私鑰如果Bob希望給Alice發(fā)送消息，則用Alice的公鑰加密Alice收到后，用自己的私鑰解密12公鑰加密模型13加密/解密：發(fā)送方用接收方的公鑰加密報(bào)文，接收方用自己的私鑰解密數(shù)字簽名：發(fā)送方用自己的私鑰簽署報(bào)文密鑰交換：雙方合作以便交換會(huì)話密鑰3.3.2 公鑰密碼系統(tǒng)的應(yīng)用14參與方B容易通過計(jì)算產(chǎn)生出一對(duì)密鑰（公開密鑰PUb ，私有密鑰PRb ），公布PUb 發(fā)送方A很容易計(jì)算產(chǎn)生密文接收方B容易計(jì)算解

8、密密文攻擊方即使知道公開密鑰PUb，要確定私有密鑰PRb 在計(jì)算上是不可行的攻擊方即使知道公開密鑰PUb和密文C，要確定明文M在計(jì)算上是不可行的密碼對(duì)互相之間可以交換使用3.3.3 公鑰加密的要求151976年Diffie & Hellman的“New Directions in Cryptography”中首次提出了公開密鑰算法的思想1977年Rivest,Shamir & Adleman提出了RSA公鑰算法90年代逐步出現(xiàn)橢圓曲線等其他公鑰算法3.4 公鑰加密算法16目的：使得兩個(gè)用戶能夠安全地交換密鑰，供以后加密消息時(shí)使用原理找到兩個(gè)公開的數(shù)字：一個(gè)素?cái)?shù)q和一個(gè)整數(shù)，定義為素?cái)?shù)q的一個(gè)本

9、原根，即如果數(shù)值 mod q， 2 mod q， q-1 mod q 是各不相同的整數(shù)并且以某種排列方式組成了從1到q-1的所有整數(shù)對(duì)于一個(gè)小于q的整數(shù)b，可以找到一個(gè)唯一的指數(shù)i，使得 b = i mod q 其中 0i p-1 指數(shù)i稱為b的以為基數(shù)的模q的離散對(duì)數(shù)，記為dlog, q(b)已知離散對(duì)數(shù)計(jì)算b相對(duì)容易，但已知b計(jì)算離散對(duì)數(shù)很困難3.4.2 Diffie-Hellman密鑰交換17 YA= XA mod q，XAqYB= XB mod q，XBqK = (YB)XA mod q = (XB mod q) XA mod q (XB) XA mod q (XA) XB mod q

10、 (XA mod q) XB mod q (YA)XB mod qDiffie-Hellman密鑰交換b = i mod q已知離散對(duì)數(shù)計(jì)算b相對(duì)容易，但對(duì)于大素?cái)?shù)，已知b計(jì)算離散對(duì)數(shù)很困難18只能用于密碼交換對(duì)手若想計(jì)算K，必須通過q，YA， YB來確定私鑰XA或XB，再計(jì)算K但是， XB = dlog, p(YB) ，而離散對(duì)數(shù)的計(jì)算相當(dāng)難Diffie-Hellman密鑰交換19選擇素?cái)?shù)q353，本原根3選擇私鑰XA97，XB233分別計(jì)算相應(yīng)的公鑰： A計(jì)算YA397 mod 353 = 40 B計(jì)算YB3233 mod 353 = 248A計(jì)算K（YB） XA mod 353 2489

11、7 mod 353 160 B計(jì)算K（YA） XBmod 353 40233 mod 353 160 DiffieHellman算法實(shí)例雙方都可以計(jì)算出Key為160，于是交換了密鑰K=16020未進(jìn)行用戶鑒別導(dǎo)致中間人攻擊Diffie-Hellman算法的中間人攻擊21雙方選擇素?cái)?shù)p以及p的一個(gè)本原根a(O知道)A選擇Xap,計(jì)算Ya=aXa mod p, AB: YaO截獲Ya,選擇Xo,計(jì)算Yo=aXo mod p,冒充A B:YoB選擇Xbp,計(jì)算Yb=aXb mod p, B A: YbO截獲Yb,冒充B A:YoA計(jì)算: K1=(Yo)Xa(aXo)XaaXoXa mod pB計(jì)算

12、: K2= (Yo)Xb(aXo)XbaXoXb mod pO計(jì)算: K1=(Ya)XoaXaXo mod p, K2=(Yb)XoaXbXo mod p O永遠(yuǎn)必須實(shí)時(shí)截獲并冒充轉(zhuǎn)發(fā),否則會(huì)被發(fā)現(xiàn) DiffieHellman算法攻擊步驟221977年由MIT的Rivest, Shamir和Adleman 三人提出是一個(gè)分組加密方法，對(duì)于某個(gè)n，明文和密文是0n-1之間的整數(shù)目前被最廣泛地采用采用的單向函數(shù)是大素?cái)?shù)相乘，相乘很容易，但因子分解很困難基于數(shù)論中的歐拉定理實(shí)現(xiàn)3.4.1 RSA公鑰加密算法23加密過程：明文：Mn密文： C = Me mod n解密過程：密文： C明文： Cd mo

13、d n = (Me)d mod n = Med mod n = M問題n，e，d是什么？（密鑰如何生成？）為什么解密過程中的Med mod n = M 成立？（加密解密原理是什么？）RSA算法加解密過程發(fā)送者和接收者都知道n和e的值只有接收者知道d的值即公鑰是KU = e,n私鑰是KR = d,n24選擇兩個(gè)素?cái)?shù)p、q計(jì)算n=p*q計(jì)算n的歐拉函數(shù)選擇一個(gè)整數(shù)e計(jì)算d，滿足公開密鑰KU = e,n私有密鑰KR = d,nRSA算法密碼的生成過程25一個(gè)RSA算法的具體實(shí)例C=Me mod nM=Cd mod n p=17，q=11n=187，e=7，d=23公開密鑰PU = 7,187私有密鑰

14、PR = 23,18726給定兩個(gè)素?cái)?shù)p、q，整數(shù)n=pq整數(shù)e與(n)互質(zhì)（即，二者最大公約數(shù)為1），假設(shè)ed=k(n)+1，（對(duì)某些整數(shù)k）,等價(jià)于： ed1 mod (n)n的歐拉函數(shù)(n)對(duì)于一個(gè)正整數(shù)n，小于n且和n互質(zhì)的正整數(shù)的個(gè)數(shù)，記做： (n)，且，若p，q為素?cái)?shù)，則(n=pq) = (p-1)(q-1)歐拉定理：對(duì)于互質(zhì)的整數(shù)a和n，有a (n) 1 mod n推論：對(duì)于互質(zhì)的數(shù)a、n， 0an，并對(duì)于任意整數(shù)k，下列關(guān)系成立： ak(n)+1=ak(p-1)(q-1)+1a mod n歐拉定理的一個(gè)推論27給定 ed mod (n) = 1，M0, n-1，gcd(M, n

15、)=1, 則：(Me mod n )d mod n = Med mod n = M mod n = M 證明： ed mod (n) = 1 ed = k (n) +1，（對(duì)某些整數(shù)k） Med mod n = Mk(n) +1 mod n = M(Mk(n) mod n) mod n Mk(n) mod n = (M(n) mod n )k mod n = 1k mod n = 1 Med mod n = (M * 1) mod n = MRSA算法的證明28窮舉攻擊數(shù)學(xué)攻擊等效于因子分解：如果竊聽者得到n，但由于不知道它的因子p與q，則很難求出(n)，也就難以求出私鑰d。若竊聽者想強(qiáng)行算出

16、(n)，則需要對(duì)n進(jìn)行因數(shù)分解求得p與q。然而大數(shù)范圍內(nèi)的合數(shù)分解十分困難，因此竊密者很難成功。目前情況看，選用1024到2048bits密鑰（n的位數(shù)）較為合理比常規(guī)加密算法具有更大的計(jì)算復(fù)雜度定時(shí)攻擊：RSA的基本運(yùn)算是乘方取模，這種運(yùn)算的特點(diǎn)是耗費(fèi)時(shí)間精確取決于乘方次數(shù)。如果A能夠監(jiān)視到RSA解密的過程，并進(jìn)行計(jì)時(shí)，就能計(jì)算出d對(duì)RSA算法的攻擊分析29參數(shù)要求p,q選擇：大素?cái)?shù)的選擇很重要，要求p和q在100位以上，n在200位上加密密鑰選擇：為了提高加密速度，通常取e為特定的小整數(shù)，如3或65537RSA算法的參數(shù)要求30DES與RSA性能比較硬件實(shí)現(xiàn)：DES比RSA快1000倍軟件

17、實(shí)現(xiàn)：DES比RSA快100倍31將常規(guī)加密算法的數(shù)據(jù)處理速度和公開密鑰算法對(duì)密鑰的保密功能相結(jié)合利用常規(guī)加密算法加密傳輸數(shù)據(jù)利用公開密鑰算法交換密碼適用于需要交流大批量數(shù)據(jù)的場合安全套接層（SSL）采用了這種解決方案混合加密系統(tǒng)32幾種公鑰加密算法的比較算 法加密/解密數(shù)字簽名密鑰交換RSA是是是Diffie-Hellman否否是數(shù)字簽名標(biāo)準(zhǔn)DSS否是否橢圓曲線是是是333.5 數(shù)字簽名認(rèn)證消息源，保證數(shù)據(jù)完整性不保證保密性343.6 密鑰管理公鑰證書使用公鑰加密來分配密鑰353.6.1 公鑰證書問題：攻擊者偽裝成用戶A廣播其公鑰廣播的公鑰如何保證是可信的？公鑰證書：公鑰，公鑰擁有者ID以及

18、可信第三方署名的數(shù)據(jù)塊第三方：用戶團(tuán)體所信任的CA（Certification Authority，認(rèn)證中心），例如政府機(jī)構(gòu)或金融機(jī)構(gòu)用戶以安全的方式向CA提交公鑰并獲得證書，并發(fā)布該證書目前廣泛使用的公鑰證書格式是X.509363.6.2 利用公鑰分發(fā)密鑰安全通信的雙方必須共享密鑰如何共享密鑰？Diffie-Hellman密鑰交換利用公鑰分配密鑰當(dāng)Bob希望與Alice通信時(shí)準(zhǔn)備消息使用一次性會(huì)話密鑰加密消息（常規(guī)加密）使用Alice的公鑰加密會(huì)話密鑰（公鑰加密）將加密過的會(huì)話密鑰添加到消息上，并向Alice發(fā)送37認(rèn)證目的驗(yàn)證信息的發(fā)送者是真正的而不是冒充的，此為信源識(shí)別驗(yàn)證信息的完整性在

19、傳送或存儲(chǔ)過程中未被篡改、重放或延遲等加密和認(rèn)證的區(qū)別加密保護(hù)消息免受被動(dòng)攻擊（竊聽），消息認(rèn)證保護(hù)消息免受主動(dòng)攻擊（偽造）加密和認(rèn)證同時(shí)是信息系統(tǒng)安全的兩個(gè)方面，是兩個(gè)不同屬性的問題認(rèn)證不能自動(dòng)提供保密性，保密性也不能自動(dòng)提供認(rèn)證功能3.1 消息認(rèn)證方法38消息加密 (Message encryption)用完整信息的密文作為對(duì)信息的認(rèn)證消息認(rèn)證碼MAC (Message Authentication Code)對(duì)信源消息和密鑰的一個(gè)編碼函數(shù)散列函數(shù)(Hash Function)是一個(gè)公開的函數(shù)，將任意長的信息映射成一個(gè)固定長度的信息可用來做認(rèn)證的技術(shù)39可以實(shí)現(xiàn)加密僅發(fā)送方和接收方共享密鑰

20、K提供一定程度的認(rèn)證消息中可以加入檢錯(cuò)碼、序號(hào)和時(shí)間戳傳輸過程中不會(huì)被更改、變序以及延遲不提供簽名接收方可以偽造報(bào)文發(fā)送方可以否認(rèn)報(bào)文3.1.1 常規(guī)加密的認(rèn)證利用數(shù)字簽名技術(shù)能夠?qū)崿F(xiàn)非對(duì)稱加密的消息認(rèn)證。403.1.2 非加密的消息認(rèn)證生成認(rèn)證標(biāo)簽，并附在每一條消息上用于傳輸。消息本身并不會(huì)被加密，所以消息在目的地可讀而與目的地的認(rèn)證功能無關(guān)。無需保密而需要認(rèn)證的情況廣播消息通信一方負(fù)載太大，來不及解密對(duì)程序的認(rèn)證，不需解密就可以運(yùn)行，節(jié)省資源兩種技術(shù)消息認(rèn)證碼和單向散列函數(shù)41消息認(rèn)證碼（MAC）技術(shù)消息認(rèn)證碼：使用密鑰K所產(chǎn)生的一個(gè)小數(shù)據(jù)塊發(fā)送方把MAC附加到消息后面接收方計(jì)算MAC，并

21、與收到的MAC比較42如果計(jì)算得到的MAC與收到的MAC相同可以保證消息未被更改可以保證消息來自其所聲稱的發(fā)送方如果消息包含序號(hào)，就能保證消息順序正確認(rèn)證不考慮解密的問題，所以不要求可逆，這樣，可以把MAC算法設(shè)計(jì)得難以被攻破利用MAC認(rèn)證的分析43單向Hash函數(shù)Hash函數(shù)H()以可變大小的消息M為輸入，產(chǎn)生一個(gè)固定大小的消息摘要H(M)作為輸出與MAC不同，不需要使用密鑰作為輸入三種方法對(duì)消息的哈希值進(jìn)行加密常規(guī)加密公鑰加密不使用加密，而使用秘密值44單向Hash函數(shù)實(shí)現(xiàn)消息認(rèn)證對(duì)消息的哈希值進(jìn)行加密，可以是常規(guī)加密和公鑰加密45在做Hash操作前加入秘密值，傳輸前移去秘密值單向Hash

22、函數(shù)實(shí)現(xiàn)消息認(rèn)證46Hash函數(shù)很重要：消息認(rèn)證，數(shù)字簽名Hash函數(shù)目標(biāo)是為數(shù)據(jù)產(chǎn)生“指紋”， Hash函數(shù)H必須具有以下性質(zhì)：H能用于任何大小的數(shù)據(jù)分組H產(chǎn)生定長輸出對(duì)任何給定的x，H(x)要易于計(jì)算，能用軟/硬件實(shí)現(xiàn)單向性質(zhì)：對(duì)于給定的哈希值h，尋找x使得H(x)h在計(jì)算上不可行，即不能從h反推出x對(duì)給定的x，尋找不等于x的y，使得H(x)H(y)在計(jì)算上不可行（抗弱碰撞性），即不能找到具有相同散列值的可替換消息尋找任何的(x,y)對(duì)，使得H(x)H(y)在計(jì)算上不可行（抗強(qiáng)碰撞性），即抗生日攻擊3.2 安全散列函數(shù)和HMAC47在集合X中，(1.17*n0.5)個(gè)隨機(jī)元素散列的結(jié)果產(chǎn)生

23、一個(gè)碰撞的概率為50%任找23(1.17*3650.5)人，從中能選出兩個(gè)人，他們具有相同生日的概率至少為1/2生日攻擊給出消息尺寸的下界一個(gè)40bit的消息摘要是不安全的,因?yàn)閚=240，即在220(大約100萬) 個(gè)隨機(jī)散列值中找到一個(gè)碰撞的概率為1/2 生日攻擊48發(fā)送方A（攻擊者）偽造兩組消息，一組為與該消息具有相同涵義的2m/2種變種，另一組為構(gòu)造的偽造消息的2m/2種變種，例如，可以用制表符取代空格，從而產(chǎn)生消息變種比較上述兩個(gè)集合，從中找出具有相同hash碼的一對(duì)消息。根據(jù)生日悖論，成功的概率大于0.5攻擊者首先拿有效消息的變種進(jìn)行消息簽名，用其私鑰對(duì)m位的hash碼加密并將加密

24、后的hash碼附于消息之后，并發(fā)送給接收方B日后攻擊者A可以用與有效消息的hash碼相同的那條偽造消息與B進(jìn)行對(duì)質(zhì)這樣，如果hash碼長度為64位，則攻擊代價(jià)僅為232一般要求hash碼長度超過128位實(shí)施生日攻擊49對(duì)每個(gè)數(shù)據(jù)塊進(jìn)行按位異或一個(gè)改進(jìn)的簡單方法是對(duì)每個(gè)分組獲得的散列值進(jìn)行循環(huán)移位3.2.2 簡單散列函數(shù)50如果對(duì)消息和hash碼都加密，則簡單hash函數(shù)還很有用，但是要注意順序問題如果給定消息塊序列是X1, X2, ,XN，將hash碼定義為逐塊異或，并把hash碼作為最后一個(gè)數(shù)據(jù)塊XN+1，即 XN+1= X1 X2 XN然后用CBC模式加密消息和hash碼，產(chǎn)生加密消息Y1

25、, Y2, ,YN,YN+1然后解密得XN+1 X1 X2 XN(IV DK(Y1) (Y1 DK(Y2) (YN-1 DK(YN) 但是如果密文順序發(fā)生變化，hash碼不會(huì)變化簡單散列函數(shù)513.2.3 安全散列函數(shù)（SHA512）用SHA-512生成消息摘要，輸入2128bits，輸出512bits52步驟1：附加填充比特，填充比特串的最高數(shù)為1，其余各位均為0，長度與896模1024同余步驟2：附加長度值，128位步驟3：初始化散列緩沖區(qū)步驟4：處理1024bits的分組序列，處理過程見下圖步驟5：輸出。所有N個(gè)1024bits的分組都處理完成后，最終輸出即為512bits的報(bào)文摘要SHA-512邏輯步驟53單個(gè)1024bits分組的SHA-512處理過程ABCDEFGH分別是64位寄存器，組成512位緩沖區(qū)80輪迭代，在第t輪，使用從當(dāng)前正在處理的1024bits