網(wǎng)絡(luò),信息,安全第四章-公鑰密碼系統(tǒng)課件

第二部分信息加密與信息隱藏

第4章公鑰密碼系統(tǒng)導(dǎo)讀本章我們將討論解密密鑰與加密密鑰不同的情況。非對稱密碼系統(tǒng)的解密密鑰與加密密鑰是不同的，一個(gè)稱為公開密鑰，另一個(gè)稱為私人密鑰（或秘密密鑰），因此這種密碼體系也稱為公鑰密碼體系。公鑰密碼除可用于加密外，還可用于數(shù)字簽名?！吨腥A人民共和國電子簽名法》已于2005年4月1日實(shí)行。2CompanyLogoContents公鑰密碼概述1數(shù)字簽名的算法5

RSA密碼系統(tǒng)2Diffie-Hellman密鑰交換3數(shù)字簽名43CompanyLogo公鑰密碼概述陷門單向函數(shù)公鑰密碼系統(tǒng)是基于陷門單向函數(shù)的概念。單向函數(shù)是易于計(jì)算但求逆困難的函數(shù)，而陷門單向函數(shù)是在不知道陷門信息情況下求逆困難，而在知道陷門信息時(shí)易于求逆的函數(shù)。5CompanyLogo公鑰密碼概述公鑰密碼系統(tǒng)可用于以下三個(gè)方面：

(1)通信保密：此時(shí)將公鑰作為加密密鑰，私鑰作為解密密鑰，通信雙方不需要交換密鑰就可以實(shí)現(xiàn)保密通信。6CompanyLogo公鑰密碼概述(2)數(shù)字簽名：將私鑰作為加密密鑰，公鑰作為解密密鑰，可實(shí)現(xiàn)由一個(gè)用戶對數(shù)據(jù)加密而使多個(gè)用戶解讀。7CompanyLogo公鑰密碼概述公開密鑰算法的特點(diǎn):（1）發(fā)送者用加密密鑰PK對明文X加密后，在接收者用解密密鑰SK解密，即可恢復(fù)出明文，或?qū)憺椋?/p>

DSK(EPK(X))X

解密密鑰是接收者專用的秘密密鑰，對其他人都保密。 此外，加密和解密的運(yùn)算可以對調(diào)，即EPK(DSK(X))X（2）加密密鑰是公開的，但不能用它來解密，即

DPK(EPK(X))X

9CompanyLogo公鑰密碼概述（3）在計(jì)算機(jī)上可以容易地產(chǎn)生成對的PK和SK。（4）從已知的PK實(shí)際上不可能推導(dǎo)出SK，即從PK到SK是“計(jì)算上不可能的”。（5）加密和解密算法都是公開的。10CompanyLogoContentsRSA密碼系統(tǒng)2數(shù)字簽名的算法5公鑰密碼概述1Diffie-Hellman密鑰交換3數(shù)字簽名411CompanyLogoRSA密碼系統(tǒng)（1）加密算法 若用整數(shù)X表示明文，用整數(shù)Y表示密文(X和Y均小于n)，則加密和解密運(yùn)算為：

加密：YXemodn

解密：XYdmodn

13CompanyLogoRSA密碼系統(tǒng)（2）密鑰的產(chǎn)生現(xiàn)在討論RSA公開密鑰密碼體制中每個(gè)參數(shù)是如何選擇和計(jì)算的。①計(jì)算n。用戶秘密地選擇兩個(gè)大素?cái)?shù)p和q，計(jì)算出n

pq。n稱為RSA算法的模數(shù)。②計(jì)算φ(n)。用戶再計(jì)算出n的歐拉函數(shù)

φ(n)(p

1)(q

1)

。③選擇e。用戶從[1,φ(n)1]中選擇一個(gè)與

φ(n)互素的數(shù)e作為公開的加密指數(shù)。14CompanyLogoRSA密碼系統(tǒng)④計(jì)算d作為解密指數(shù)。用戶計(jì)算出滿足下式的ded1modφ(n)即：(ed–1)modφ(n)=0由此推出

ed=tφ(n)+1(t是大于等于1的正整數(shù)）⑤得出所需要的公開密鑰和秘密密鑰：公開密鑰(即加密密鑰)PK{e,n}秘密密鑰(即解密密鑰)SK{d,n}其中，p、q、φ?(n)和d就是秘密的陷門(四項(xiàng)并不是相互獨(dú)立的)，這些信息不可以泄露。15CompanyLogoRSA密碼系統(tǒng)例子:說明RSA的加/解密過程。選p=5，q=11，則n=pq=55，φ?(n)=(p?1)(q?1)=40明文空間為在閉區(qū)間[1,54]內(nèi)且不能被5和11整除的數(shù)。如果明文m同n不是互為素?cái)?shù)，就有可能出現(xiàn)消息暴露情況，這樣我們就可能通過計(jì)算n與加密以后的m的最大公約數(shù)來分解出n。17CompanyLogoRSA密碼系統(tǒng)一個(gè)明文同n有公約數(shù)的概率小于1/p+1/q，因此，對于大的p和q來說，這種概率是非常小的。選擇e=7，則d=23。由加/解密公式可以得到加密表如表4-1所示。

18CompanyLogo加密表明文密文明文密文明文密文明文密文11149285242482181636293943323421783126465144918173243475364119243434482772821213631491482231237385169424293847521312232616391953371372734146545419CompanyLogoDiffie-Hellman密鑰交換Diffie-Hellman算法

Diffie-Hellman算法是第一個(gè)公開密鑰算法，發(fā)明于1976年。Diffie-Hellman算法能夠用于密鑰分配，但不能用于加密或解密信息。21CompanyLogoDiffie-Hellman密鑰交換Diffie-Hellman算法的安全性在于在有限域上計(jì)算離散對數(shù)非常困難。定義素?cái)?shù)p的本原根(PrimitiveRoot)為一種能生成1～p?1所有數(shù)的一個(gè)數(shù)，即如果a為p的本原根，則amodp，a2modp，…，ap?1modp兩兩互不相同，構(gòu)成1～p?1的全體數(shù)的一個(gè)排列(例如p=11，a=2)。對于任意數(shù)b及素?cái)?shù)p的本原根a，可以找到一個(gè)惟一的指數(shù)i，滿足：b=aimodp,0≤i≤p?1

稱指數(shù)i為以a為底模p的b的離散對數(shù)。22CompanyLogoDiffie-Hellman密鑰交換如果Alice和Bob想在不安全的信道上交換密鑰，他們可以采用如下步驟：(1)Alice和Bob協(xié)商一個(gè)大素?cái)?shù)p及p的本原根a，a和p可以公開；(2)Alice秘密產(chǎn)生一個(gè)隨機(jī)數(shù)x，計(jì)算X=axmodp，然后把X發(fā)送給Bob；(3)Bob秘密產(chǎn)生一個(gè)隨機(jī)數(shù)y，計(jì)算Y=aymodp，然后把Y發(fā)送給Alice；(4)Alice計(jì)算k=Yxmodp；(5)Bob計(jì)算k'=Xymodp。

23CompanyLogoDiffie-Hellman密鑰交換下面用一個(gè)例子來說明上述過程。Alice和Bob需進(jìn)行密鑰交換，如圖4-3所示，則：

二者協(xié)商后決定采用素?cái)?shù)p=353及其本原根a=3。Alice選擇隨機(jī)數(shù)x=97，計(jì)算X=397mod353＝40，并發(fā)送給Bob。Bob選擇隨機(jī)數(shù)y=233，計(jì)算Y=3233mod353＝248，并發(fā)送給Alice。Alice計(jì)算k=Yxmodp＝24897mod353=160。Bob計(jì)算k'=Xymodp＝40233mod353=160。

k和k'?即為秘密密鑰.25CompanyLogoDiffie-Hellman密鑰交換26CompanyLogo中間人攻擊Alice用密鑰k1給Bob發(fā)送消息；Carol截獲消息后用k1解密就可讀取消息；然后將獲得的明文消息用k2加密(加密前可能會對消息作某些修改)后發(fā)送給Bob。對Bob發(fā)送給Alice的消息，Carol同樣可以讀取和修改。造成中間人攻擊的原因是Diffie-Hellman密鑰交換不認(rèn)證對方。利用數(shù)字簽名可以挫敗中間人攻擊。29CompanyLogo認(rèn)證的Diffie-Hellman密鑰交換密鑰交換雙方通過數(shù)字簽名和公鑰證書相互認(rèn)證可以挫敗中間人攻擊。在密鑰交換之前，密鑰交換的雙方Alice和Bob各自擁有公鑰/私鑰對和公開密鑰證書，Alice和Bob簽名算法和驗(yàn)證算法分別為SigA、SigB、VerA、VerB?？尚胖行腡A也有一個(gè)簽名方案，簽名算法為SigTA，公開的簽名驗(yàn)證算法為VerTA，Alice和Bob持有一個(gè)證書：

C(A)=(ID(A),VerA,SigTA(ID(A),VerA))

C(B)=(ID(B),VerB,SigTA(ID(B),VerB))其中ID(A)為用戶身份信息,證書C(A)由TA事先簽發(fā)30CompanyLogoAlice和Bob產(chǎn)生共享秘密密鑰的過程(1)Alice秘密產(chǎn)生一個(gè)隨機(jī)數(shù)x，計(jì)算X=axmod

p，然后把X發(fā)送給Bob；(2)Bob秘密產(chǎn)生一個(gè)隨機(jī)數(shù)y，首先計(jì)算Y=aymodp，然后計(jì)算k=Xymodp

和yB=SigB(Y,X),最后，Bob把(C(B),Y,yB)發(fā)送給Alice；(3)Alice計(jì)算k=Yxmodp，并使用VerB

驗(yàn)證yB

，使用VerTA驗(yàn)證C(B)；計(jì)算yA=SigA(Y,X),并將結(jié)果(C(A),yA)發(fā)給用戶Bob(4)Bob使用VerA

驗(yàn)證yA,使用VerTA驗(yàn)證C(A)。31CompanyLogoAlice和Bob產(chǎn)生共享秘密密鑰的過程簡要分析抗擊中間入侵攻擊的過程。若攻擊者Carol插在用戶Alice和Bob之間，顯然Carol可能截獲Alice發(fā)送的X，并將其替換為X′=ax’modp,然后Carol截獲Bob發(fā)送的Y=aymodp和SigB(Y,X′)。攻擊者Carol有可能將Y替換為Y′=ay’modp,或?qū)igB(Y,X′)替換為SigB(Y′,X)，但由于Carol不知道Bob的簽名算法SigB，所以他無法計(jì)算SigB(Y′,X)。同樣，Carol也無法知道A的簽名SigA。這樣就達(dá)到了抗擊中間人攻擊的目的。32CompanyLogo三方或多方Diffie-Hellman33CompanyLogo三方或多方Diffie-Hellman(1)?Alice選取一個(gè)大隨機(jī)整數(shù)x，計(jì)算X=axmodp，然后把X發(fā)送給Bob；(2)?Bob選取一個(gè)大隨機(jī)整數(shù)y，計(jì)算Y=aymodp，然后把Y發(fā)送給Carol；(3)?Carol選取一個(gè)大隨機(jī)整數(shù)z，計(jì)算Z=azmodp，然后把Z發(fā)送給Alice；(4)?Alice計(jì)算Z‘=Zxmodp并發(fā)送Z’?給Bob；(5)?Bob計(jì)算X'=Xymodp并發(fā)送X'?給Carol；34CompanyLogo三方或多方Diffie-Hellman(6)?Carol計(jì)算Y‘=Yzmodp并發(fā)送Y’?給Alice；(7)?Alice計(jì)算k=Y'xmodp；(8)?Bob計(jì)算k=Z'ymodp；(9)?Carol計(jì)算k=X'zmodp。

共享秘密密鑰k等于axyzmodp。這個(gè)協(xié)議很容易擴(kuò)展到更多方。35CompanyLogoContents數(shù)字簽名4數(shù)字簽名的算法5

RSA密碼系統(tǒng)2Diffie-Hellman密鑰交換3公鑰密碼概述136CompanyLogo數(shù)字簽名數(shù)字簽名概述在文件上手寫簽名長期以來被用作作者身份的證明，或表示同意文件的內(nèi)容。簽名為什么會如此引人注目呢？1.簽名是可信的。2.簽名不可偽造。3.簽名不可重用。4.簽名的文件是不可改變的。5.簽名是不可抵賴的。37CompanyLogo數(shù)字簽名在現(xiàn)實(shí)生活中，關(guān)于簽名的這些陳述沒有一個(gè)是完全真實(shí)的。

公鑰密碼學(xué)使得數(shù)字簽名成為可能。用私鑰加密信息，這時(shí)就稱為對信息進(jìn)行數(shù)字簽名。將密文附在原文后，稱為數(shù)字簽名。其他人用相應(yīng)的公鑰去解密密文，將解出的明文與原文相比較，如果相同則驗(yàn)證成功，這稱為驗(yàn)證簽名。

現(xiàn)在，已有很多國家制訂了電子簽名法。《中華人民共和國電子簽名法》已于2004年8月28日第十屆全國人民代表大會常務(wù)委員會第十一次會議通過，并已于2005年4月1日開始施行。38CompanyLogo數(shù)字簽名的方法基本的數(shù)字簽名協(xié)議是簡單的：1.Alice用她的私鑰對文件加密，從而對文件簽名。2.Alice將簽名的文件傳給Bob。3.Bob用Alice的公鑰解密文件，從而驗(yàn)證簽名。這個(gè)協(xié)議不需要第三方去簽名和驗(yàn)證。甚至協(xié)議的雙方也不需要第三方來解決爭端；如果Bob不能完成第3步，那么他知道簽名是無效的。39CompanyLogo這個(gè)協(xié)議也滿足我們期待的特征：1.簽名是可信的。當(dāng)Bob用Alice的公鑰驗(yàn)證信息時(shí)，他知道是由Alice簽名的。2.簽名是不可偽造的。只有Alice知道她的私鑰。3.簽名是不可重用的。簽名是文件的函數(shù)，并且不可能轉(zhuǎn)換成另外的文件。4.被簽名的文件是不可改變的。如果文件有任何改變，文件就不可能用Alice的公鑰驗(yàn)證成功。5.簽名是不可抵賴的。Bob不用Alice的幫助就能驗(yàn)證Alice的簽名。40CompanyLogo數(shù)字簽名的方法

在實(shí)際的實(shí)現(xiàn)過程中，采用公鑰密碼算法對長文件簽名效率太低。為了節(jié)約時(shí)間，數(shù)字簽名協(xié)議經(jīng)常和單向散列函數(shù)一起使用。Alice并不對整個(gè)文件簽名，只對文件的散列值簽名。1.Alice產(chǎn)生文件的散列值。2.Alice用她的私鑰對散列值加密，憑此表示對文件簽名。3.Alice將文件和散列簽名送給Bob。4.Bob用Alice發(fā)送的文件產(chǎn)生文件的散列值，然后用Alice的公鑰對簽名的散列值解密。如果解密的散列值與自己產(chǎn)生的散列值相同，簽名就是有效的。41CompanyLogo多重簽名采用單向散列函數(shù)，是容易的：1.Alice對文件的散列值簽名。2.Bob對文件的散列值簽名。3.Bob將他的簽名交給Alice。4.Alice把文件、她的簽名和Bob的簽名發(fā)給Carol。5.Carol驗(yàn)證Alice和Bob的簽名。Alice和Bob能同時(shí)或順序地完成1和2，Carol可以只驗(yàn)證其中一人的簽名而不用驗(yàn)證另一人的簽名。42CompanyLogo帶加密的數(shù)字簽名通過把公鑰密碼和數(shù)字簽名結(jié)合起來，我們能夠產(chǎn)生一個(gè)協(xié)議，可把數(shù)字簽名的真實(shí)性和加密的安全性合起來。想象你寫的一封信：簽名提供了原作者的證明，而信封提供了秘密性。43CompanyLogo帶加密的數(shù)字簽名1.Ailce用她的私鑰對信息簽名：SA(M)2.Alice用Bob的公鑰對簽名的信息加密，然后送給Bob：EB(SA(M))3.Bob用他的私鑰解密：DB(EB(SA(M)))=SA(M)4.Bob用Alice的公鑰驗(yàn)證并且恢復(fù)出信息：VA(SA(M))=M44CompanyLogoContents數(shù)字簽名的算法5數(shù)字簽名4

RSA密碼系統(tǒng)2Diffie-Hellman密鑰交換3公鑰密碼概述145CompanyLogo數(shù)字簽名算法DSA1991年8月，美國NIST公布了用于數(shù)字簽名標(biāo)準(zhǔn)DSS的數(shù)字簽名算法DSA，1994年12月1日正式采用為美國聯(lián)邦信息處理標(biāo)準(zhǔn)。DSA中用到了以下參數(shù)：(1)?p為L位長的素?cái)?shù)，其中，L為512～1024之間且是64倍數(shù)的數(shù)。(2)?q是160位長的素?cái)?shù)，且為p-1的因子。(3)?g=h(p-1)/qmodp，其中，h是滿足1＜h＜p-1且h(p-1)/qmodp大于1的整數(shù)。(4)?x是隨機(jī)產(chǎn)生的大于0而小于q的整數(shù)。(5