本科生必修課現(xiàn)代密碼學

1、1/957.1 數(shù)字簽字的基本概念7.2 數(shù)字簽字標準7.3 其它簽字方案7.4 認證協(xié)議7.5 身份證明技術(shù)7.6 其它密碼協(xié)議 本章提要2/957.1 數(shù)字簽字的基本概念數(shù)字簽名由公鑰密碼發(fā)展而來，它在網(wǎng)絡安全方面具有重要的應用，包括身份認證數(shù)據(jù)完整性不可否認性匿名性等本章重點學習數(shù)字簽名的基本概念和一些常用的數(shù)字簽名算法身份認證協(xié)議、身份證明技術(shù)3/957.1.1 數(shù)字簽字應滿足的要求普通的基于對稱密鑰的消息認證方法存在重要缺陷消息認證雖然可以保護通信雙方以防第三方的攻擊，然而卻不能保護通信雙方中的一方防止另一方的欺騙或偽造通信雙方之間可能有多種形式的欺騙例如通信雙方A和B（設A為發(fā)方，

2、B為收方）使用消息認證碼的基本方式通信，則可能發(fā)生以下欺騙： B偽造一個消息并使用與A共享的密鑰產(chǎn)生該消息的認證碼，然后聲稱該消息來自于A。 由于B有可能偽造A發(fā)來的消息，所以A就可以對自己發(fā)過的消息予以否認。數(shù)字簽名可提供消息的不可否認性4/957.1.1 數(shù)字簽字應滿足的要求這兩種欺騙在實際的網(wǎng)絡安全應用中都有可能發(fā)生例如在電子資金傳輸中，收方增加收到的資金數(shù)，并聲稱這一數(shù)目來自發(fā)方。又如用戶通過電子郵件向其證券經(jīng)紀人發(fā)送對某筆業(yè)務的指令，以后這筆業(yè)務賠錢了，用戶就可否認曾發(fā)送過相應的指令。在收發(fā)雙方未建立起完全的信任關(guān)系且存在利害沖突的情況下，單純的消息認證就顯得不夠。數(shù)字簽名技術(shù)則可有

3、效解決這一問題。5/95類似于手書簽名，數(shù)字簽名應具有以下性質(zhì)： 能夠驗證簽名產(chǎn)生者的身份，以及產(chǎn)生簽名的日期和時間 能用于證實被簽消息的內(nèi)容 數(shù)字簽名可由第三方驗證，從而能夠解決通信雙方的爭議由此可見，數(shù)字簽名具有認證功能6/95為實現(xiàn)上述3條性質(zhì)，數(shù)字簽名應滿足以下要求： 簽名的產(chǎn)生必須使用發(fā)方獨有的一些信息以防偽造和否認 簽名的產(chǎn)生應較為容易 簽名的識別和驗證應較為容易 對已知的數(shù)字簽名構(gòu)造一新的消息或?qū)σ阎南?gòu)造一假冒的數(shù)字簽名在計算上都是不可行的7/957.1.2 數(shù)字簽名的產(chǎn)生方式數(shù)字簽名的產(chǎn)生可用加密算法或特定的簽名算法1. 由加密算法產(chǎn)生數(shù)字簽名是指將消息或消息的摘要加密后

4、的密文作為對該消息的數(shù)字簽名其用法又根據(jù)是單鑰加密還是公鑰加密而有所不同(1) 單鑰加密如圖：基于共享密鑰加解密，密文即為簽名如果加密的是消息摘要或有消息冗余，則可提供消息源認證和完整性認證嚴格來說，不能稱為簽名，不具備簽名的要求 8/95(2) 公鑰加密如圖1(b)所示，發(fā)送方A使用自己的秘密鑰SKA對消息M加密后的密文作為對M的數(shù)字簽名，B使用A的公開鑰PKA對消息解密，由于只有A才擁有加密密鑰SKA，因此可使B相信自己收到的消息的確來自A。然而由于任何人都可使用A的公開鑰解密密文，所以這種方案不提供保密性加密的消息應該是消息摘要或有消息冗余為提供保密性，A可用B的公開鑰再一次加密，如圖1

5、(c)所示。9/95下面以RSA簽名體制為例說明數(shù)字簽名的產(chǎn)生過程 體制參數(shù)選兩個保密的大素數(shù)p和q，計算n=pq，(n)=(p-1)(q-1)選一整數(shù)e，滿足1e(n)，且gcd(n),e)=1計算d，滿足de1 mod (n)以e,n為公開鑰,d,p,q為秘密鑰 簽名過程設消息為M，對其簽名為：SM d mod n 驗證過程接收方在收到消息M和簽名S后，驗證MSe mod n是否成立，若成立，則發(fā)送方的簽名有效實際應用時，數(shù)字簽名是對消息摘要加密產(chǎn)生，而不是直接對消息加密產(chǎn)生，如圖6.3(a)圖6.3(d)所示10/95由加密算法產(chǎn)生數(shù)字簽名又分為外部保密方式和內(nèi)部保密方式外部保密方式是指

6、數(shù)字簽名是直接對需要簽名的消息生成而不是對已加密的消息生成，否則稱為內(nèi)部保密方式。外部保密也可說是先簽名再加密，而后者是先加密再簽名外部保密方式便于解決爭議，因為第3方在處理爭議時，需得到明文消息及其簽名如果采用內(nèi)部保密方式，第3方必須得到消息的解密密鑰后才能得到明文消息。如果采用外部保密方式，接收方就可將明文消息及其數(shù)字簽名存儲下來以備以后萬一出現(xiàn)爭議時使用 11/952. 由簽名算法產(chǎn)生數(shù)字簽名簽名算法的輸入是明文消息M和密鑰x，輸出是對M的數(shù)字簽名，表示為S=Sigx(M)相應于簽名算法，有一驗證算法，表示為Ver(S,M)，其取值為Ver(S,M)算法的安全性在于從M和S難以推出密鑰x

7、或偽造一個消息M，使M和S可被驗證為真。12/957.1.3 數(shù)字簽名的執(zhí)行方式數(shù)字簽名的執(zhí)行方式有兩類： 直接方式和具有仲裁的方式1. 直接方式(缺少監(jiān)督的方式)直接方式是指數(shù)字簽名的執(zhí)行過程只有通信雙方參與，并假定雙方有共享的秘密鑰或接收一方知道發(fā)方的公開鑰直接方式的數(shù)字簽名有一公共弱點，即方案的有效性取決于發(fā)方秘密鑰的安全性13/95如果發(fā)方想對已發(fā)出的消息予以否認，就可聲稱自己的秘密鑰已丟失或被竊，因此自己的簽名是他人偽造的可采取某些行政手段，雖然不能完全避免但可在某種程度上減弱這種威脅例如，要求每一被簽名的消息都包含有一個時戳（日期和時間）并要求密鑰丟失后立即向管理機構(gòu)報告這種方式的

8、數(shù)字簽名還存在發(fā)方的秘密鑰真的被偷的危險例如敵手在時刻T偷得發(fā)方的秘密鑰，然后可偽造一消息，用偷得的秘密鑰為其簽名并加上T以前的時刻作為時戳14/952. 具有仲裁方式的數(shù)字簽名可解決直接方式的缺陷具有仲裁方式的數(shù)字簽名也有很多實現(xiàn)方案，這些方案都按以下方式運行： 發(fā)方X對發(fā)往收方Y(jié)的消息簽名后，將消息及其簽名先發(fā)給仲裁者AA對消息及其簽名驗證完后，再連同一個表示已通過驗證的指令一起發(fā)往收方Y(jié)此時由于A的存在，X無法對自己發(fā)出的消息予以否認。在這種方式中，仲裁者起著重要的作用，并應取得所有用戶的信任15/95以下是具有仲裁方式數(shù)字簽名的幾個實例其中X表示發(fā)方，Y表示收方，A是仲裁者，M是消息X

9、Y： M表示X給Y發(fā)送一消息M【例71】 簽名過程如下： XA：MEKXAIDXH(M) AY：EKAYIDXMEKXAIDXH(M)T其中E是單鑰加密算法KXA和KAY分別是X與A共享的密鑰和A與Y共享的密鑰H(M)是M的雜湊值，T是時戳，IDX是X的身份在中，X以EKXAIDXH(M)作為自己對M的簽名，將M及簽名發(fā)往A在中A將從X收到的內(nèi)容和IDX、T一起加密后發(fā)往Y，其中的T用于向Y表示所發(fā)的消息不是舊消息的重放。Y對收到的內(nèi)容解密后,將解密結(jié)果存儲起來以備出現(xiàn)爭議時使用16/95在【例71】中如果出現(xiàn)爭議，Y可聲稱自己收到的M的確來自X，并將EKAYIDXMEKXAIDXH(M)發(fā)給

10、A，由A仲裁，A由KAY解密后，再用KXA對EKXAIDXH(M)解密，并對H(M)加以驗證，從而驗證了X的簽名由于Y不知KXA，因此不能直接檢查X的簽名，但Y認為消息來自于A因而是可信的。所以在整個過程中，A必須取得X和Y的高度信任： X相信A不會泄露KXA，并且不會偽造X的簽名;Y相信A只有在對EKAYIDXMEKXAIDXH(M)T中的雜湊值及X的簽名驗證無誤后才將之發(fā)給Y;X，Y都相信A可公正地解決爭議17/95如果A已取得各方的信任，則X就能相信沒有人能偽造自己的簽名，Y就可相信X不能對自己的簽名予以否認嚴格的說，例71不是簽字協(xié)議，僅僅是具有仲裁能力的認證協(xié)議例71中消息M是以明文

11、形式發(fā)送的，因此未提供保密性，下面兩個例子可提供保密性【例72】 簽名過程如下： XA: IDXEKXYMEKXAIDXH(EKXYM) AY: EKAYIDXEKXYMEKXAIDXH(EKXYM)T其中KXY是X，Y共享的密鑰，其他符號與例1相同18/95X以EKXAIDXH(EKXYM)作為對M的簽名，與由KXY加密的消息M一起發(fā)給A。A對EKXAIDXH(EKXYM)解密后通過驗證雜湊值以驗證X的簽名，但始終未能讀取明文M。A驗證完X的簽名后，對X發(fā)來的消息加一時戳，再用KAY加密后發(fā)往Y。解決爭議的方法與例1一樣。本例雖然提供了保密性，但還存在與上例相同的一個問題即仲裁者可和發(fā)方共謀

12、以否認發(fā)方曾發(fā)過的消息，也可和收方共謀以偽造發(fā)方的簽名這一問題可通過下例所示的采用公鑰加密技術(shù)的方法得以解決19/95【例73】 簽名過程如下： XA：IDXESKXIDXEPKYESKXM AY：ESKAIDXEPKYESKXMT其中SKA和SKX分別是A和X的秘密鑰，PKY是Y的公開鑰，其他符號與前兩例相同。第步中，X用自己的秘密鑰SKX和Y的公開鑰PKY對消息加密后作為對M的簽名，以這種方式使得任何第3方（包括A）都不能得到M的明文消息A收到X的內(nèi)容后，用X的公開鑰可對ESKXIDXEPKYESKXM解密，并將解密得到的IDX與收到的IDX加以比較，從而可確信這一消息是來自于X的（因只有

13、X有SKX）第步，A將X的身份IDX和X對M的簽名加上一時戳后，再用自己的秘密鑰加密發(fā)往Y20/95與前兩種方案相比，第3種方案有很多優(yōu)點。首先，在協(xié)議執(zhí)行以前，各方都不必有共享的信息，從而可防止共謀。第二，只要仲裁者的秘密鑰不被泄露，任何人包括發(fā)方就不能發(fā)送重放的消息。最后，對任何第三方（包括A）來說，X發(fā)往Y的消息都是保密的21/957.2 數(shù)字簽名標準數(shù)字簽名標準DSS(Digital Signature Standard)是由美國NIST公布的聯(lián)邦信息處理標準FIPS PUB 186其中采用了上一章介紹的SHA和一新的簽名技術(shù)，稱為DSA(Digital Signature Algor

14、ithm)DSS最初于1991年公布，在考慮了公眾對其安全性的反饋意見后，于1993年公布了其修改版DSA 是算法, DSS 是標準22/957.2.1 DSS的基本方式首先將DSS與RSA的簽名方式做一比較RSA算法既能用于加密和簽名，又能用于密鑰交換與此不同，DSS使用的算法只能提供數(shù)字簽名功能23/95RSA簽名中，將消息輸入到一個雜湊函數(shù)以產(chǎn)生一個固定長度的安全雜湊值，再用發(fā)方的秘密鑰加密雜湊值就形成了對消息的簽名消息及其簽名被一起發(fā)給收方收方得到消息后再產(chǎn)生出消息的雜湊值且使用發(fā)方的公開鑰對收到的簽名解密這樣收方就得了兩個雜湊值，如果兩個雜湊值是一樣的，則認為收到的簽名是有效的24/

15、95DSS簽名也利用一雜湊函數(shù)產(chǎn)生消息的一個雜湊值，雜湊值連同一隨機數(shù)k一起作為簽名函數(shù)的輸入簽名函數(shù)還需使用發(fā)送方的秘密鑰SKA和供所有用戶使用的一族參數(shù)，稱這一族參數(shù)為全局公開鑰PKG簽名函數(shù)的兩個輸出s和r就構(gòu)成了消息的簽名(s,r)。接收方收到消息后再產(chǎn)生出消息的雜湊值，將雜湊值與收到的簽名一起輸入驗證函數(shù)，驗證函數(shù)還需輸入全局公開鑰PKG和發(fā)送方的公開鑰PKA。驗證函數(shù)的輸出如果與收到的簽名成分r相等，則驗證了簽名是有效的25/957.2.2 數(shù)字簽名算法DSADSA是在ElGamal和Schnorr兩個簽名方案的基礎上設計的，其安全性基于求離散對數(shù)的困難性。生成簽名長度 320 b

16、it，算法描述如下： (1) 全局公開鑰p：滿足2L-1p2L 的大素數(shù)，其中512L1024且L是64的倍數(shù)q：p-1的素因子，滿足2159q2160 ，即q長為160比特。g：g=h(p-1)/q mod p，h是滿足1h1的任一整數(shù)(2) 用戶秘密鑰xx是滿足0 xq的隨機數(shù)或偽隨機數(shù)(3) 用戶的公開鑰yygx mod p。26/95(4) 用戶為待簽消息選取的秘密數(shù)kk是滿足0kq的隨機數(shù)或偽隨機數(shù)。(5) 簽名過程用戶對消息M的簽名為(r, s)，其中r(gk mod p) mod q sk-1(H(M)+xr) mod q，H(M)是由SHA求出的雜湊值(6) 驗證過程設接收方收

17、到的消息為M，簽名為(r,s)。計算w(s)-1 mod q,u1H(M)w mod qu2rw mod q, v(gu1yu2) mod p mod q檢查v=r 是否成立，若相等，則認為簽名有效這是因為若(M,r,s)=(M,r,s)，則 vgH(M)wgxrw mod p mod qg(H(M)+xr)s mod p mod q gk mod p mod qr27/95算法的框圖如圖7-3所示，其中的4個函數(shù)分別為s=f1H(M),k,x,r,qk-1(H(M)+xr) mod qr=f2(k,p,q,g)(gk mod p) mod qw=f3(s,q)(s)-1 mod qv=f4(

18、y,q,g,H(M),w,r)(g(H(M)w) mod q y rw mod q) mod p mod q由于離散對數(shù)的困難性，敵手從r恢復k或從s恢復x都是不可行的28/95r和k-1可預計算即簽名產(chǎn)生過程中的運算主要是求r的模指數(shù)運算r=(gk mod p) mod q，而這一運算與待簽的消息無關(guān)，因此能被預先計算事實上，用戶可以預先計算出很多r和k-1以備以后的簽名使用，從而可大大加快產(chǎn)生簽名的速度DSA的安全性基于離散對數(shù)，最初建議使用一個共同的模數(shù)p ；現(xiàn)在建議不同的工作組使用不同的 (p,q,g)注意驗證者及任何其它人均不知道x和k同一個用戶所產(chǎn)生的兩個簽名不能使用相同的k，否則

19、會泄漏xGus Simmons 發(fā)現(xiàn)存在潛信道，能夠泄露私鑰29/957.3. 其他簽名方案7.3.1 基于離散對數(shù)問題的數(shù)字簽名體制基于離散對數(shù)問題的數(shù)字簽名體制是數(shù)字簽名體制中最為常用的一類，其中包括ElGamal簽名體制、DSA簽名體制、Okamoto簽名體制等1. 離散對數(shù)簽名體制ElGamal、DSA、Okamoto等簽名體制都可歸結(jié)為離散對數(shù)簽名體制的特例(1) 體制參數(shù)p：大素數(shù)；q：p-1或p-1的大素因子g：gRZp*，且gq1(mod p)，其中g(shù)RZp*表示g是從Zp*中隨機選取的，其中Zp*=Zp-0 x：用戶A的秘密鑰，1xqy：用戶A的公開鑰，ygx(mod p)3

20、0/95(2) 簽名的產(chǎn)生過程對于待簽名的消息m，A執(zhí)行以下步驟： 計算m的雜湊值H(m)。 選擇隨機數(shù)k：1kq，計算 rgk(mod p)。 從簽名方程akb+cx(mod q)中解出s。方程的系數(shù)a、b、c有許多種不同的選擇方法，表7-1給出了這些可能選擇中的一小部分，以(r, s)作為產(chǎn)生的數(shù)字簽名。表7-1 參數(shù)a、b、c可能的置換取值表abcrsH(m)rH(m)s1rH(m) H(m)s1H(m)r rs1H(m)s rs131/95(3) 簽名的驗證過程接收方在收到消息m和簽名(r, s)后，可以按照以下驗證方程檢驗： Ver(y, (r, s), m)=Ture ragbyc

21、 (mod p)2.ElGamal簽名體制(1) 體制參數(shù)p：大素數(shù)； g：Zp*的一個生成元；x：用戶A的秘密鑰，xRZp* ； y：用戶A的公開鑰，ygx(mod p)。32/95(2) 簽名的產(chǎn)生過程對于待簽名的消息m，A執(zhí)行以下步驟： 計算m的雜湊值H(m) 選擇隨機數(shù)k：kZp*，gcd(k,p-1)=1，計算rgk(mod p) 計算sk-1(H(m)-xr) (mod p-1)以(r,s)作為產(chǎn)生的數(shù)字簽名注意在公開參數(shù)一樣的情況下，任何兩次簽名的會話密鑰k應不等(3) 簽名驗證過程接收方收到m和數(shù)字簽名(r, s)后，先計算H(m)，并按下式驗證： Ver(y, (r, s),

22、 H(m)=Ture gH(m)rsyr (mod p)正確性可由下式證明：rsyrgrxgksgrx+H(m)-rxgH(m) (mod p)33/953. Schnorr簽名體制(1) 體制參數(shù)p：大素數(shù)，p2512； q：大素數(shù)，q|(p-1)，q2160；g：gRZp*,且gq1(mod p)；x：用戶A的秘密鑰，1xq；y：用戶A的公開鑰，ygx(mod p)。(2) 簽名的產(chǎn)生過程對于待簽名的消息m，A執(zhí)行以下步驟： 選擇隨機數(shù)k：1kq，計算 rgk(mod p)。 計算e=H(r, m)。 計算sxe+k(mod q)。以(e, s)作為產(chǎn)生的數(shù)字簽名。34/95(3) 簽名驗

23、證過程接收方在收到消息m和數(shù)字簽名(e, s)后，先計算rgsy-e(mod p)，然后計算H(r,m)，并按下式驗證Ver(y, (e, s), m)=Ture H(r,m) =e其正確性可由下式證明：rgsy-egxe+k-xer (mod p)35/957.3.2 基于大數(shù)分解問題的數(shù)字簽名體制設n是一個大合數(shù)，找出n的所有素因子是一個困難問題，稱之為大數(shù)分解問題。下面介紹的兩個數(shù)字簽名體制都基于這個問題的困難性。1. Fiat-Shamir簽名體制(1) 體制參數(shù)n：n=pq，其中p和q是兩個保密的大素數(shù)；k：固定的正整數(shù)；y1,y2,yk：用戶A的公開鑰，對任何i(1ik)，yi都是

24、模n的平方剩余；x1,x2,xk：用戶A的秘密鑰，對任何i(1ik)，xi mod n。36/95(2) 簽名的產(chǎn)生過程對于待簽名的消息m，A執(zhí)行以下步驟： 隨機選取一個正整數(shù)t。 隨機選取t個介于1和n之間的數(shù)r1,r2,rt，并對任何j(1jt)，計算Rjrj2(mod n)。 計算雜湊值H(m,R1,R2,Rt)，并依次取出H(m,R1,R2,Rt)的前kt個比特值b11,b1t, b21,b2t, bk1,bkt。 對任何j(1jt)，計算sjrj (mod n)。以(b11,b1t, b21,b2t, bk1,bkt),(s1,st)作為對m的數(shù)字簽名。37/95(3) 簽名的驗證過

25、程收方在收到消息m和簽名(b11,b1t, b21,b2t, bk1,bkt),( s1,st)后，用以下步驟來驗證： 對任何j(1jt)，計算Rjsj2 (mod n)。 計算H(m,R1,R2,Rt)。 驗證b11,b1t, b21,b2t, bk1,bkt是否依次是H(m,R1,R2,Rt)的前kt個比特。如果是，則以上數(shù)字簽名是有效的。正確性可以由以下算式證明：Rjsj2 (mod n)(rj )2 rj2 rj2Rj mod n38/952. Guillou-Quisquater簽名體制(GQ簽名體制)(1) 體制參數(shù)n：n=pq，p和q是兩個保密的大素數(shù)； v：gcd(v,(p-1

26、)(q-1)=1；x：用戶A的秘密鑰，xRZn*；y：用戶A的公開鑰，yR Zn*，且xvy1 mod n(2) 簽名的產(chǎn)生過程對于待簽消息m，A進行以下步驟： 隨機選擇一個數(shù)kZn*，計算 Tkv(mod n)。 計算雜湊值： e=H(m,T)，且使1ev；否則，返回步驟。 計算skxe mod n。以(e, s)作為對m的簽名。39/95(3) 簽名的驗證過程接收方在收到消息m和數(shù)字簽名(e, s)后，用以下步驟來驗證： 計算出Tsvye(mod n)。 計算出e=H(m,T)。 驗證：Ver(y, (e, s), m)=Ture e=e正確性可由以下算式證明：Tsvye(mod n)(k

27、xe)vye(mod n) kv(xvy)e(mod n)kv(mod n)T40/957.3.3 基于身份的數(shù)字簽字體制1. ElGamal簽字體制(1)體制參數(shù)體制參數(shù)與4.8.3節(jié)相同。設q是大素數(shù)，G1,G2分別是階為q的加法群和乘法群e:G1G1G2是一個雙線性映射H1：0,1*G1*和H2：G2 0,1n是兩個雜湊函數(shù)sZq*是系統(tǒng)的主密鑰，P是G1的一個生成元。用戶ID的公開鑰和秘密鑰分別是QIDH1(ID) G1*和dIDs QID41/95(2)簽字的產(chǎn)生過程對于待簽字的消息m，A執(zhí)行以下步驟：選擇隨機數(shù)kZq*計算RkP(xR,yR)計算S(H2(m)P+xRdID)k-1

28、以(R,S)作為產(chǎn)生的數(shù)字簽字(3)簽字的驗證過程接收方在收到消息m和數(shù)字簽字(R,S)后，先計算H2(m)，并按下式驗證：Ver(QID,(R,S),H2(m)=Turee(P,P)H2(m) e(Ppub,QID)xR正確性可由下式證明：e(R,S)=e(kP,(H2(m)P+xRdID)k-1)=e(P,P)H2(m) e(P,QID)xRs =e(P,P)H2(m) e(Ppub,QID)xR42/957.4 認證協(xié)議安全可靠的通信除需進行消息的認證外，還需建立一些規(guī)范的協(xié)議對數(shù)據(jù)來源的可靠性、通信實體的真實性加以認證，以防止欺騙、偽裝等攻擊，一般分為三個層次：數(shù)據(jù)完整性認證：防止篡改

29、，重排，重放等等數(shù)據(jù)源認證：使得通信業(yè)務與具體實體捆綁認證，數(shù)據(jù)由哪個實體而來實體認證：發(fā)起通信或訪問的實體是否具有合法身份和相應權(quán)限這些認證常常一起進行，也有時單獨進行通信之前首先進行實體認證(身份認證)，身份認證之后會協(xié)商出會話密鑰用于對每個傳輸數(shù)據(jù)的數(shù)據(jù)源認證和完整性認證實體認證(身份認證)包括身份證實和身份識別：43/95身份證實你是否是你宣稱的你驗證方首先知道要驗證的身份是誰，進一步證實來訪或與之通信的人是否具有該身份一般用于A和B確定通信時所用，通常的網(wǎng)絡認證協(xié)議都是身份證實具體技術(shù)：輸入個人信息，經(jīng)公式或算法運算所得結(jié)果與卡中或數(shù)據(jù)庫中存儲信息經(jīng)公式運算所得結(jié)果比較身份識別我是否

30、知道你是誰驗證方不知道來訪人是否為合法身份，沒有比較確定的目標，只要滿足某個條件就可判定身份的特點。驗證者一般為權(quán)威機構(gòu)一般在實體認證中需要， 比如判斷來訪者是否是在逃犯，是否為密碼開啟者，是否為本公司員工。通常用指紋、虹膜技術(shù)具體技術(shù)：輸入個人信息，經(jīng)過處理提取模版信息，試著在存儲數(shù)據(jù)庫中找出一個與之匹配的模版而后得出結(jié)論44/95認證協(xié)議的典型用途是：身份認證與會話密鑰協(xié)商身份認證和密鑰協(xié)商往往同時進行如Kerberos認證系統(tǒng)(NS協(xié)議)、X.509、SSL、TLS、IPSec/IKE本節(jié)以網(wǎng)絡通信的一個基本問題的解決引出認證協(xié)議的基本意義，這一基本問題陳述如下：A和B是網(wǎng)絡的兩個用戶，

31、他們想通過網(wǎng)絡先建立安全的共享密鑰再進行保密通信。A(B)如何確信自己正在和B(A)通信而不是和C通信呢？即雙方的身份認證這種通信方式為雙向通信，此時的認證稱為相互認證類似地，對于單向通信來說，認證稱為單向認證這里的認證主要是身份證實45/957.4.1 相互認證A、B兩個用戶在建立共享密鑰時需要考慮的核心問題是保密性和實時性保密性：為了防止會話密鑰的偽造或泄露，會話密鑰在通信雙方之間交換時應為密文形式，所以通信雙方事先就應有密鑰或公開鑰實時性：對防止消息的重放攻擊極為重要實現(xiàn)實時性的一種方法是對交換的每一條消息都加上一個序列號，一個新消息僅當它有正確的序列號時才被接收。這種方法的困難性是要求

32、每個用戶分別記錄與其他每一用戶交換的消息的序列號，從而增加了用戶的負擔，所以序列號方法一般不用于認證和密鑰交換。46/95保證消息的實時性常用以下兩種方法： 時戳如果A收到的消息包括一時戳，且在A看來這一時戳充分接近自己的當前時刻， A才認為收到的消息是新的并接受之。這種方案要求所有各方的時鐘是同步的詢問-應答用戶A向B發(fā)出一個一次性隨機數(shù)作為詢問，如果收到B發(fā)來的消息（應答）也包含一正確的一次性隨機數(shù)，A就認為B發(fā)來的消息是新的并接受之。47/95時戳法不能用于面向連接的應用過程這是由于時戳法在實現(xiàn)時固有的困難性首先是需要在不同的處理器時鐘之間保持同步，那么所用的協(xié)議必須是容錯的以處理網(wǎng)絡錯

33、誤，并且是安全的以對付惡意攻擊第二，如果協(xié)議中任一方的時鐘出現(xiàn)錯誤而暫時地失去了同步，則將使敵手攻擊成功的可能性增加最后還由于網(wǎng)絡本身存在著延遲，因此不能期望協(xié)議的各方能保持精確的同步。所以任何基于時戳的處理過程、協(xié)議等都必須允許同步有一個誤差范圍?？紤]到網(wǎng)絡本身的延遲，誤差范圍應足夠大；考慮到可能存在的攻擊，誤差范圍又應足夠小48/95詢問-應答方式則不適合于無連接的應用過程這是因為在無連接傳輸以前需經(jīng)詢問-應答這一額外的握手過程，這與無連接應用過程的本質(zhì)特性不符。對無連接的應用程序來說，利用某種安全的時間服務器保持各方時鐘同步是防止重放攻擊最好的方法49/95通信雙方建立共享密鑰時可采用單

34、鑰加密體制和公鑰加密體制1. 單鑰加密體制需要有一個可信的密鑰分配中心KDC，網(wǎng)絡中每一用戶都與KDC有一共享的密鑰，稱為主密鑰KDC為通信雙方建立一個短期內(nèi)使用的密鑰，稱為會話密鑰，并用主密鑰加密會話密鑰后分配給兩個用戶這種分配密鑰的方式在實際應用中較為普遍采用，如Kerberos系統(tǒng)采用的就是這種方式50/95(1) Needham-Schroeder協(xié)議以下是1978年出現(xiàn)的著名的Needham-Schroeder認證協(xié)議。即為5.1節(jié)中圖5-1所示的采用KDC的密鑰分配過程這里需建立一個稱為鑒別服務器的可信權(quán)威機構(gòu)（密鑰分發(fā)中心KDC），擁有每個用戶的秘密密鑰若用戶A欲與用戶B通信，則

35、用戶A向鑒別服務器申請會話密鑰。在會話密鑰的分配過程中，雙方身份得以鑒別51/95 AKDC：IDAIDBN1 KDCA：EKAKSIDBN1EKBKSIDA AB：EKBKSIDA BA：EKSN2 AB：EKSf(N2)協(xié)議的目的是由KDC為A、B安全地分配會話密鑰KSA在第步安全地獲得了KS第步的消息僅能被B解讀，因此B在第步安全地獲得了KS 第步中B向A示意自己已掌握KS，N2用于向A詢問自己在第步收到的KS是否為一新會話密鑰，第步A對B的詢問作出應答，一方面表示自己已掌握KS，另一方面由f(N2)回答了KS的新鮮性。第、兩步用于防止對第步的重放攻擊52/95以上協(xié)議易遭受另一種重放攻

36、擊假定敵手能獲取舊會話密鑰，則冒充A向B重放第步的消息后，就可欺騙B使用舊會話密鑰敵手進一步截獲第步B發(fā)出的詢問后，可假冒A作出第步的應答敵手就可冒充A使用經(jīng)認證過的會話密鑰向B發(fā)送假消息53/95(2) Needham-Schroeder協(xié)議的改進方案之一在第步和第步加上一時戳，改進后的協(xié)議如下： AKDC：IDAIDB KDCA：EKAKSIDBTEKBKSIDAT AB：EKBKSIDAT BA：EKSN1 AB：EKSf(N1)其中T是時戳，用以向A、B雙方保證KS的新鮮性。A和B可通過下式檢查T的實時性：|Clock-T|t1+t2Clock為用戶（A或B）本地的時鐘t1是用戶本地時

37、鐘和KDC時鐘誤差的估計值t2是網(wǎng)絡的延遲時間。54/95T是經(jīng)主密鑰加密的，所以敵手即使知道舊會話密鑰，并在協(xié)議的過去執(zhí)行期間截獲第步的結(jié)果，也無法成功地重放給B因B對收到的消息可通過時戳檢查其是否為新的以上改進還存在以下問題：方案主要依賴網(wǎng)絡中各方時鐘的同步，這種同步可能會由于系統(tǒng)故障或計時誤差而被破壞等待重放攻擊：如果發(fā)送方的時鐘超前于接收方的時鐘，敵手就可截獲發(fā)送方發(fā)出的消息，等待消息中時戳接近于接收方的時鐘時，再重發(fā)這個消息這種重放至少可以影響Ks的有效期，也可造成重復接收等問題55/95抗等待重放攻擊方法一：要求網(wǎng)絡中各方以KDC的時鐘為基準定期檢查并調(diào)整自己的時鐘方法二：使用一次

38、性隨機數(shù)的握手協(xié)議這就是NS協(xié)議的另一種改進方法(3) Needham-Schroeder協(xié)議的改進方案之二 AB：IDANA BKDC：IDBNBEKBIDANATB KDCA：EKAIDBNAKSTBEKBIDAKSTBNB AB：EKBIDAKSTBEKSNBTB是B建議的證書(會話密鑰)截止時間，用于截止時間前再次發(fā)起會話時KS是否可用的判別時間56/95協(xié)議的具體含義如下： A將新的一次性隨機數(shù)NA與自己的身份IDA一起以明文形式發(fā)往B，NA以后將與會話密鑰KS一起以加密形式返回給A，以保證A收到的會話密鑰的新鮮性。 B向KDC發(fā)出與A建立會話密鑰的請求，表示請求的消息包括B的身份、

39、一次性隨機數(shù)NB以及由B與KDC共享的主密鑰加密的數(shù)據(jù)項。其中NB以后將與會話密鑰一起以加密形式返回給B以向B保證會話密鑰的新鮮性請求中由主密鑰加密的數(shù)據(jù)項用于指示KDC向A發(fā)出一個證書，其中的數(shù)據(jù)項有證書接收者A的身份、B建議的證書截止時間TB、B從A收到的一次性隨機數(shù)。57/95 KDC將B產(chǎn)生的NB連同由KDC與B共享的密鑰KB加密的IDAKSTB一起發(fā)給A，其中KS是KDC分配的會話密鑰EKBIDAKSTB由A當作票據(jù)用于以后的認證。KDC向A發(fā)出的消息還包括由KDC與A共享的主密鑰加密的IDBNAKSTBA用這一消息可驗證B已收到第步發(fā)出的消息（通過IDB）A還能驗證這一步收到的消息

40、是新的（通過NA），這一消息中還包括KDC分配的會話密鑰KS以及會話密鑰的截止時間TB。 A將票據(jù)EKBIDAKSTB連同由會話密鑰加密的一次性隨機數(shù)NB發(fā)往B，B由票據(jù)得到會話密鑰KS，并由KS得NB。NB由會話密鑰加密的目的是B認證了自己收到的消息不是一個重放,而的確是來自于A。58/95如果A保留由協(xié)議得到的票據(jù)EKBIDAKSTB ，就可在有效時間范圍內(nèi)不再求助于認證服務器而由以下方式實現(xiàn)雙方的新認證： AB：EKBIDAKSTB，NA BA：NB ，EKSNA AB：EKSNBB在第步收到票據(jù)后，可通過TB檢驗票據(jù)是否過時，而新產(chǎn)生的一次性隨機數(shù)NA ，NB則向雙方保證了沒有重放攻擊

41、以上協(xié)議中時間期限TB是B根據(jù)自己的時鐘定的，因此不要求各方之間的同步59/952. 公鑰加密體制曾介紹過使用公鑰加密體制分配會話密鑰的方法(前提是收發(fā)雙方已經(jīng)互相知道對方公鑰)，以下協(xié)議也用于此目的(但事先不知道彼此公鑰) AAS：IDAIDB ASA：ESKASIDAPKATESKASIDBPKBT AB： ESKASIDAPKATESKASIDBPKBT EPKBESKAKST其中SKAS、SKA 分別是AS和A的秘密鑰，PKA、PKB分別是A和B的公開鑰，E為公鑰加密算法，AS是認證服務器時戳T用以防止重放攻擊，所以需要各方時鐘同步B的證書可省去60/95第步，A將自己的身份及欲通信的

42、對方的身份發(fā)送給AS第步，AS發(fā)給A的兩個鏈接的數(shù)據(jù)項都是由自己的秘密鑰加密（即由AS簽字），分別作為發(fā)放給通信雙方的公鑰證書第步，A選取會話密鑰并經(jīng)自己的秘密鑰和B的公開鑰加密后連同兩個公鑰證書一起發(fā)往B。因會話密鑰是由A選取，并以密文形式發(fā)送給B，因此包括AS在內(nèi)的任何第3者都無法得到會話密鑰時戳T用以防止重放攻擊，所以需要各方時鐘同步61/95下一協(xié)議使用一次性隨機數(shù)，因此不需要時鐘的同步： AKDC：IDAIDB KDCA：ESKAUIDBPKB AB：EPKBNAIDA BKDC：IDBIDAEPKAUNA KDCB：ESKAUIDAPKAEPKBESKAUNAKSIDB BA：EP

43、KAESKAUNAKSIDBNB AB：EKSNB其中SKAU和PKAU分別是KDC的秘密鑰和公開鑰62/95第步，A通知KDC他想和B建立安全連接。第步，KDC將B的公鑰證書發(fā)給A，公鑰證書包括經(jīng)KDC簽字的B的身份和公鑰。第步，A告訴B想與他通信，并將自己選擇的一次性隨機數(shù)NA發(fā)給B。第步，B向KDC發(fā)出得到A的公鑰證書和會話密鑰的請求，請求中由KDC的公開鑰加密的NA用于讓KDC將建立的會話密鑰與NA聯(lián)系起來，以保證會話密鑰的新鮮性。63/95第步，KDC向B發(fā)出A的公鑰證書以及由自己的秘密鑰和B的公開鑰加密的三元組NA,KS,IDB。三元組由KDC的秘密鑰加密可使B驗證三元組的確是由K

44、DC發(fā)來的，由B的公開鑰加密是防止他人得到三元組后假冒B建立與A的連接。第步，B新產(chǎn)生一個一次性隨機數(shù)NB,連同上一步收到的由KDC的秘密鑰加密的三元組一起經(jīng)A的公開鑰加密后發(fā)往A。第步，A取出會話密鑰，再由會話密鑰加密NB后發(fā)往B，以使B知道A已掌握會話密鑰。以上協(xié)議可進一步做如下改進： 在第、兩步出現(xiàn)NA的地方加上IDA，以說明NA的確是由A產(chǎn)生的而不是其他人產(chǎn)生的，這時IDA，NA就可惟一地識別A發(fā)出的連接請求64/95以上協(xié)議稍微擴展就是著名的Kerberos協(xié)議它是工作在應用層的認證協(xié)議解決的問題：在一個公開的分布式環(huán)境中，工作站上的用戶希望訪問分布在網(wǎng)絡中的服務器(可能是多個)上的

45、服務服務器希望能夠限制授權(quán)用戶的訪問，并能對服務請求進行鑒別Kerberos的主要功能：認證、授權(quán)、記賬與審計Kerberos系統(tǒng)在一個分布式的Client/Server體系機構(gòu)中采用一個或多個Kerberos服務器提供一個認證服務。Kerberos系統(tǒng)基于對稱密鑰構(gòu)建，提供一個基于可信第三方的認證服務65/95Kerberos不是為每一個服務器構(gòu)造一個身份認證協(xié)議，而是提供一個中心認證服務器，提供用戶到服務器和服務器到用戶的認證服務該中心認證服務器執(zhí)行密鑰管理和控制的功能，維護一個保存所有客戶密鑰的數(shù)據(jù)庫。該中心認證服務器即為可信第三方每當兩個用戶要進行安全通信及認證請求時，Kerberos

46、認證服務器就產(chǎn)生會話密鑰Kerberos系統(tǒng)使用56位DES加密算法加密網(wǎng)絡連接，并且提供用戶身份的認證66/95Kerberos認證協(xié)議的體系結(jié)構(gòu)圖和每次登陸執(zhí)行一次和每種服務執(zhí)行一次和每個服務的每次會話執(zhí)行一次67/9568/95這個過程可以通過如下的例子來理解把西電網(wǎng)絡看成一個提供網(wǎng)頁、郵件、FTP、數(shù)據(jù)庫等多個服務的網(wǎng)絡那么有一個認證中心在網(wǎng)絡中心，還有一個票據(jù)服務器用于對每一種服務的接入授權(quán)每一個西電用戶都在認證中心注冊了自己的賬號現(xiàn)在用戶Alice想要訪問西電的FTP服務器，則采用如下步驟（1）如果Alice還未登陸系統(tǒng)，則首先向認證中心認證，并請求訪問票據(jù)許可服務器，認證中心在檢

47、驗了用戶身份后發(fā)給Alice一個訪問票據(jù)許可服務器的票據(jù)，如果已經(jīng)登陸則不需此步驟（2）如果Alice要訪問一個服務，如FTP，但還沒有被授權(quán)訪問，則將認證中心的票據(jù)及要訪問的服務提交給票據(jù)許可服務器，認證后票據(jù)許可服務器發(fā)給Alice一個服務許可票據(jù)，用于訪問FTP服務器，如果已經(jīng)有有效票據(jù)則不需此步驟。（3）用戶Alice要訪問FTP服務，在每次會話建立前，將服務許可票據(jù)提交給FTP服務器，驗證后即可訪問資源69/957.4.2 單向認證電子郵件等網(wǎng)絡應用不要求收發(fā)雙方同時在線郵件消息的報頭必須是明文形式以使SMTP或X.400等存儲-轉(zhuǎn)發(fā)協(xié)議能夠處理SMTP（simple mail tr

48、ansfer protocol-簡單郵件傳輸協(xié)議）通常都不希望郵件處理協(xié)議要求郵件的消息本身是明文形式，否則就要求用戶對郵件處理機制的信任所以用戶在進行保密通信時，需對郵件消息進行加密以使包括郵件處理系統(tǒng)在內(nèi)的任何第3者都不能讀取郵件的內(nèi)容。再者郵件接收者還希望對郵件的來源即發(fā)方的身份進行認證，以防他人的假冒。與雙向認證一樣，在此仍分為單鑰加密和公鑰加密兩種情況來考慮70/951. 單鑰加密單向通信時無中心的密鑰分配情況不適用，因為需要握手在圖5-1所示的情況中去掉第步和第步就可滿足單向通信的兩個要求。協(xié)議如下： AKDC：IDAIDBN1 KDCA：EKAKSIDBN1EKBKSIDA AB

49、：EKBKSIDAEKSM本協(xié)議不要求B同時在線，但保證了只有B能解讀消息，同時還提供了對消息的發(fā)方A的認證然而本協(xié)議不能防止重放攻擊，如第步，為此需在消息中加上時戳，但由于電子郵件處理中的延遲，時戳的作用極為有限71/952. 公鑰加密公鑰加密算法可對發(fā)送的消息提供保密性、認證性或既提供保密性又提供認證性，為此要求發(fā)送方知道接收方的公開鑰（保密性），或要求接收方知道發(fā)送方的公開鑰（認證性），或要求每一方都知道另一方的公開鑰如果主要關(guān)心保密性，則可使用以下方式： AB：EPKBKSEKSM其中A用B的公開鑰加密一次性會話密鑰，用一次性會話密鑰加密消息。只有B能夠使用相應的秘密鑰得到一次性會話密

50、鑰，再用一次性會話密鑰得到消息。這種方案比簡單地用B的公開鑰加密整個消息要有效得多。72/95如果主要關(guān)心認證性，則可使用以下方式： AB：MESKAH(M)這種方式可實現(xiàn)對A的認證，但不提供對M的保密性。如果既要提供保密性又要提供認證性，可使用以下方式： AB：EPKBMESKAH(M)后兩種情況要求B知道A的公開鑰并確信公開鑰的真實性。為此A還需同時向B發(fā)送自己的公鑰證書，表示為AB：MESKAH(M)ESKASTIDAPKA或 AB：EPKBMESKAH(M)ESKASTIDAPKA其中ESKASTIDAPKA是認證服務器AS為A簽署的公鑰證書73/957.5 身份證明技術(shù)在很多情況下，

51、用戶都需證明自己的身份如登錄計算機系統(tǒng)存取電子銀行中的賬目數(shù)據(jù)庫從自動出納機ATM(automatic teller machine)取款等傳統(tǒng)的方法使用通行字(口令)個人身份識別號PIN(personal identification number)來證明自己的身份這些方法的缺點是檢驗用戶通行字或PIN的人或系統(tǒng)可使用用戶的通行字或PIN冒充用戶身份的零知識證明技術(shù)可使用戶在不泄露自己的通行字或PIN的情況下向他人證實自己的身份74/957.5.1 交互證明系統(tǒng)交互證明系統(tǒng)由兩方參與，分別稱為證明者（prover，簡記為P）和驗證者（verifier，簡記為V）其中P知道某一秘密（如公鑰密碼

52、體制的秘密鑰或一平方剩余x的平方根），P希望使V相信自己的確掌握這一秘密交互證明由若干輪組成在每一輪，P和V可能需根據(jù)從對方收到的消息和自己計算的某個結(jié)果向?qū)Ψ桨l(fā)送消息比較典型的方式是在每輪V都向P發(fā)出一詢問，P向V做出一應答所有輪執(zhí)行完后，V根據(jù)P是否在每一輪對自己發(fā)出的詢問都能正確應答，以決定是否接受P的證明75/95交互證明和數(shù)學證明的區(qū)別是：數(shù)學證明的證明者可自己獨立地完成證明交互證明是由P產(chǎn)生證明、V驗證證明的有效性來實現(xiàn)，因此雙方之間通過某種信道的通信是必需的。交互證明系統(tǒng)須滿足以下要求： 完備性如果P知道某一秘密，V將接受P的證明 正確性如果P能以一定的概率使V相信P的證明，則P

53、知道相應的秘密76/957.5.2 簡化的Fiat-Shamir身份識別方案1. 協(xié)議及原理設n=pq，其中p和q是兩個不同的大素數(shù)x是模n的平方剩余y是x的平方根n和x是公開的，而p、q和y是保密的證明者P以y作為自己的秘密已證明，求解方程y2x mod n與分解n是等價的。因此他人不知n的兩個素因子p、q而計算y是困難的P和V通過交互證明協(xié)議，P向V證明自己掌握秘密y，從而證明了自己的身份77/95協(xié)議如下： P隨機選r (0rn)，計算ar2 mod n，將a發(fā)送給V。 V隨機選e0,1，將e發(fā)送給P。 P計算brye mod n，即e=0時，b=r；e=1時，b=ry mod n。將b

54、發(fā)送給V。 若b2axe mod n，V接受P的證明。在協(xié)議的前3步，P和V之間共交換了3個消息，這3個消息的作用分別是： 第1個消息是P用來聲稱自己知道a的平方根；第2個消息e是V的詢問，如果e=0，P必須展示a的平方根，即r，如果e=1，P必須展示被加密的秘密，即ry mod n；第3個消息b是P對V詢問的應答。78/952. 協(xié)議的完備性、正確性和安全性(1) 完備性如果P和V遵守協(xié)議，且P知道y，則應答brye mod n應是模n下axe的平方根在協(xié)議的第步V接受P的證明，所以協(xié)議是完備的(2) 正確性假冒的證明者E可按以下方式以1/2的概率騙得V接受自己的證明： E隨機選r(0rn)

55、和e0,1，計算ar2x-e mod n，將a發(fā)送給V V隨機選e0,1，將e發(fā)送給E E將r發(fā)送給V根據(jù)協(xié)議的第步，V的驗證方程是r2axe mod nr2x-exe mod n，當e=e 時，驗證方程成立，V接受E的證明，即E欺騙成功79/95e=e的概率是1/2，所以E欺騙成功的概率是1/2另一方面，1/2是E能成功欺騙的最好概率否則假設E以大于1/2的概率使V相信自己的證明那么E知道一個a，對這個a他可正確地應答V的兩個詢問e=0和e=1，意味著E能計算b12a mod n和b22ax mod n，即b22/b12x mod n，因此E由b2/b1 mod n即可求得x的平方根y，矛盾

56、。80/95(3) 安全性協(xié)議的安全性可分別從證明者P和驗證者V的角度來考慮。V的安全性，要求驗證方被騙概率可忽略根據(jù)上面的討論，假冒的證明者E欺騙V成功的概率是1/2，對V來說，這個概率太大了。為減小這個概率，可將協(xié)議重復執(zhí)行多次，設執(zhí)行t次，則欺騙者欺騙成功的概率將減小到2-t。P的安全性，證明方消息無泄漏因為V的詢問是在很小的集合0,1中選取的，V沒有機會產(chǎn)生其他信息，而P發(fā)送給V的信息僅為P知道x的平方根這一事實，因此V無法得知x的平方根。81/957.5.3 零知識證明零知識證明起源于最小泄露證明在交互證明系統(tǒng)中，設P知道某一秘密，并向V證明自己掌握這一秘密，但又不向V泄露這一秘密，

57、這就是最小泄露證明進一步，如果V除了知道P能證明某一事實外，不能得到其他任何信息，則稱P實現(xiàn)了零知識證明，相應的協(xié)議稱為零知識證明協(xié)議82/95【例7-4】 圖7-4表示一個簡單的迷宮，C和D之間有一道門，需要知道秘密口令才能打開P向V證明自己能打開這道門，但又不愿向V泄漏秘密口令83/95V在協(xié)議開始時停留在位置A；P一直走到迷宮的深處，隨機選擇位置C或位置D；P消失在迷宮中后，V走到位置B，然后命令P從某個出口返回位置B；P服從V的命令，必要時利用秘密口令打開C與D之間的門；P和V重復以上過程n次。協(xié)議中，如果P不知道秘密口令，就只能從來路返回B，而不能走另外一條路。P每次猜對V要求走哪一

58、條路的概率是1/2，因此每一輪中P能夠欺騙V的概率是1/2。假定n取16，則執(zhí)行16輪后，P成功欺騙V的概率是1/2161/65536。于是，如果P16次都能按V的要求返回，V即能證明P確實知道秘密口令。還可以看出，V無法從上述證明過程中獲取絲毫關(guān)于P的秘密口令的信息，所以這是一個零知識證明協(xié)議。84/95【例75】 哈密爾頓（Hamilton）回路圖中的回路是指始點和終點相重合的路徑，若回路通過圖的每個頂點一次且僅一次，則稱為哈密爾頓回路構(gòu)造圖的哈密爾頓回路是NPC問題。求兩個圖同構(gòu)也是困難問題現(xiàn)在假定P知道圖G的哈密爾頓回路，并希望向V證明這一事實，可采用如下協(xié)議： P隨機地構(gòu)造一個與圖G

59、同構(gòu)的圖 ，并 將交給V。 V隨機地要求P做下述兩件工作之一： 證明圖G和圖 同構(gòu)；指出圖 的一條哈密爾頓回路。 P根據(jù)要求做下述兩件工作之一： 證明圖G和圖 同構(gòu)，但不指出圖G或圖 的哈密爾頓回路；指出圖 的哈密爾頓回路，但不證明圖G和圖 同構(gòu)。 P和V重復以上過程n次。85/95協(xié)議執(zhí)行完后，V無法獲得任何信息使自己可以構(gòu)造圖G的哈密爾頓回路，因此該協(xié)議是零知識證明協(xié)議。事實上，如果P向V證明圖G和圖 同構(gòu)，這個結(jié)論對V并沒有意義，因為構(gòu)造圖 的哈密爾頓回路和構(gòu)造圖G的哈密爾頓回路同樣困難。如果P向V指出圖的一條哈密爾頓回路，這一事實也無法向V提供任何幫助，因為求兩個圖之間的同構(gòu)并不比求一個圖的哈密爾頓回路容易。在協(xié)議的每一輪中，P都隨機地構(gòu)造一個與圖G同構(gòu)的新圖，因此不論協(xié)議執(zhí)行多少輪，V都得不到任何有關(guān)構(gòu)造圖G的哈密爾頓回路的信息。注：兩個圖G1和G2是同構(gòu)的是指從G1的頂點集合到G2的頂點集合之間存在一個一一映射，當且僅當若x、y是G1上的相鄰點，(x)和(y)是G2上的相鄰點。86/957.5.4 Fiat-Shamir身份識別方案 1. 協(xié)議及原理在簡化的Fiat-Shamir身份識別方案中，驗證者V接受假冒的證明者證明的概率是1/2，為減小這個