現(xiàn)代密碼學第7章

1、第7章 數(shù)字簽字和密碼協(xié)議7.1 數(shù)字簽字的基本概念7.2 數(shù)字簽字標準7.3 其他簽字方案7.4 認證協(xié)議7.5 身份證明技術7.6 其他密碼協(xié)議習題數(shù)字簽字由公鑰密碼發(fā)展而來，它在網(wǎng)絡安全，包括身份認證、數(shù)據(jù)完整性、不可否認性以及匿名性等方面有著重要應用。本章首先介紹數(shù)字簽字的基本概念和一些常用的數(shù)字簽字算法，然后介紹身份認證協(xié)議、身份證明技術以及其他一些常用的密碼協(xié)議。上一章介紹的消息認證其作用是保護通信雙方以防第三方的攻擊，然而卻不能保護通信雙方中的一方防止另一方的欺騙或偽造。通信雙方之間也可能有多種形式的欺騙，例如通信雙方A和B（設A為發(fā)方，B為收方）使用圖6.1所示的消息認證碼的基

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

3、，數(shù)字簽字應具有以下性質(zhì)： 能夠驗證簽字產(chǎn)生者的身份，以及產(chǎn)生簽字的日期和時間。 能用于證實被簽消息的內(nèi)容。 數(shù)字簽字可由第三方驗證，從而能夠解決通信雙方的爭議。由此可見，數(shù)字簽字具有認證功能。為實現(xiàn)上述3條性質(zhì)，數(shù)字簽字應滿足以下要求： 簽字的產(chǎn)生必須使用發(fā)方獨有的一些信息以防偽造和否認。 簽字的產(chǎn)生應較為容易。 簽字的識別和驗證應較為容易。 對已知的數(shù)字簽字構造一新的消息或?qū)σ阎南嬙煲患倜暗臄?shù)字簽字在計算上都是不可行的。數(shù)字簽字的產(chǎn)生可用加密算法或特定的簽字算法。1. 由加密算法產(chǎn)生數(shù)字簽字利用加密算法產(chǎn)生數(shù)字簽字是指將消息或消息的摘要加密后的密文作為對該消息的數(shù)字簽字，其用法又根據(jù)

4、是單鑰加密還是公鑰加密而有所不同。7.1.2 數(shù)字簽字的產(chǎn)生方式(1) 單鑰加密如圖7.1(a)所示，發(fā)送方A根據(jù)單鑰加密算法以與接收方B共享的密鑰K對消息M加密后的密文作為對M的數(shù)字簽字發(fā)往B。該系統(tǒng)能向B保證所收到的消息的確來自A，因為只有A知道密鑰K。再者B恢復出M后，可相信M未被篡改，因為敵手不知道K就不知如何通過修改密文而修改明文。具體來說，就是B執(zhí)行解密運算Y=DK(X)，如果X是合法消息M加密后的密文，則B得到的Y就是明文消息M，否則Y將是無意義的比特序列。圖7.1 消息加密產(chǎn)生數(shù)字簽字的基本方式(2) 公鑰加密如圖7.1(b)所示，發(fā)送方A使用自己的秘密鑰SKA對消息M加密后的

5、密文作為對M的數(shù)字簽字，B使用A的公開鑰PKA對消息解密，由于只有A才擁有加密密鑰SKA，因此可使B相信自己收到的消息的確來自A。然而由于任何人都可使用A的公開鑰解密密文，所以這種方案不提供保密性。為提供保密性，A可用B的公開鑰再一次加密，如圖7.1(c)所示。下面以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,n為秘密鑰。 簽字過程。設消息為M，對其簽字為SMd mod n 驗證過程。接收方在收到消息M和

6、簽字S后，驗證 是否成立，若成立，則發(fā)送方的簽字有效。實際應用時，數(shù)字簽字是對消息摘要加密產(chǎn)生，而不是直接對消息加密產(chǎn)生，如圖6.3(a)圖6.3(d)所示。由加密算法產(chǎn)生數(shù)字簽字又分為外部保密方式和內(nèi)部保密方式，外部保密方式是指數(shù)字簽字是直接對需要簽字的消息生成而不是對已加密的消息生成，否則稱為內(nèi)部保密方式。外部保密方式便于解決爭議，因為第3方在處理爭議時，需得到明文消息及其簽字。但如果采用內(nèi)部保密方式，第3方必須得到消息的解密密鑰后才能得到明文消息。如果采用外部保密方式，接收方就可將明文消息及其數(shù)字簽字存儲下來以備以后萬一出現(xiàn)爭議時使用。2. 由簽字算法產(chǎn)生數(shù)字簽字簽字算法的輸入是明文消息

7、M和密鑰x，輸出是對M的數(shù)字簽字，表示為S=Sigx(M)。相應于簽字算法，有一驗證算法，表示為Verx(S,M)，其取值為算法的安全性在于從M和S難以推出密鑰x或偽造一個消息M使M和S可被驗證為真。數(shù)字簽字的執(zhí)行方式有兩類： 直接方式和具有仲裁的方式。1. 直接方式直接方式是指數(shù)字簽字的執(zhí)行過程只有通信雙方參與，并假定雙方有共享的秘密鑰或接收一方知道發(fā)方的公開鑰。7.1.3 數(shù)字簽字的執(zhí)行方式直接方式的數(shù)字簽字有一公共弱點，即方案的有效性取決于發(fā)方秘密鑰的安全性。如果發(fā)方想對已發(fā)出的消息予以否認，就可聲稱自己的秘密鑰已丟失或被竊，因此自己的簽字是他人偽造的?？刹扇∧承┬姓侄危m然不能完全避

8、免但可在某種程度上減弱這種威脅。例如，要求每一被簽字的消息都包含有一個時戳（日期和時間）并要求密鑰丟失后立即向管理機構報告。這種方式的數(shù)字簽字還存在發(fā)方的秘密鑰真的被偷的危險，例如敵手在時刻T偷得發(fā)方的秘密鑰，然后可偽造一消息，用偷得的秘密鑰為其簽字并加上T以前的時刻作為時戳。2. 具有仲裁方式的數(shù)字簽字上述直接方式的數(shù)字簽字所具有的缺陷都可通過使用仲裁者得以解決。和直接方式的數(shù)字簽字一樣，具有仲裁方式的數(shù)字簽字也有很多實現(xiàn)方案，這些方案都按以下方式運行： 發(fā)方X對發(fā)往收方Y(jié)的消息簽字后，將消息及其簽字先發(fā)給仲裁者A，A對消息及其簽字驗證完后，再連同一個表示已通過驗證的指令一起發(fā)往收方Y(jié)。此時

9、由于A的存在，X無法對自己發(fā)出的消息予以否認。在這種方式中，仲裁者起著重要的作用并應取得所有用戶的信任。以下是具有仲裁方式數(shù)字簽字的幾個實例，其中X表示發(fā)方，Y表示收方，A是仲裁者，M是消息，XY： M表示X給Y發(fā)送一消息M。例7.1 簽字過程如下： 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

10、表示所發(fā)的消息不是舊消息的重放。Y對收到的內(nèi)容解密后,將解密結(jié)果存儲起來以備出現(xiàn)爭議時使用。如果出現(xiàn)爭議，Y可聲稱自己收到的M的確來自X，并將EKAYIDXMEKXAIDXH(M)發(fā)給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

11、可公正地解決爭議。如果A已取得各方的信任，則X就能相信沒有人能偽造自己的簽字，Y就可相信X不能對自己的簽字予以否認。本例中消息M是以明文形式發(fā)送的，因此未提供保密性，下面兩個例子可提供保密性。例7.2 簽字過程如下： XA: IDXEKXYMEKXAIDXH(EKXYM)。 AY: EKAYIDXEKXYMEKXAIDXH(EKXYM)T。其中KXY是X，Y共享的密鑰，其他符號與例7.1相同。X以EKXAIDXH(EKXYM)作為對M的簽字，與由KXY加密的消息M一起發(fā)給A。A對EKXAIDXH(EKXYM)解密后通過驗證雜湊值以驗證X的簽字，但始終未能讀取明文M。A驗證完X的簽字后，對X發(fā)來

12、的消息加一時戳，再用KAY加密后發(fā)往Y。解決爭議的方法與例7.1一樣。本例雖然提供了保密性，但還存在與上例相同的一個問題，即仲裁者可和發(fā)方共謀以否認發(fā)方曾發(fā)過的消息，也可和收方共謀以偽造發(fā)方的簽字。這一問題可通過下例所示的采用公鑰加密技術的方法得以解決。例7.3 簽字過程如下： XA：IDXESKXIDXEPKYESKXM。 AY：ESKAIDXEPKYESKXMT。其中SKA和SKX分別是A和X的秘密鑰，PKY是Y的公開鑰，其他符號與前兩例相同。第步中，X用自己的秘密鑰SKX和Y的公開鑰PKY對消息加密后作為對M的簽字，以這種方式使得任何第3方（包括A）都不能得到M的明文消息。A收到X發(fā)來的

13、內(nèi)容后，用X的公開鑰可對ESKXIDXEPKYESKXM解密，并將解密得到的IDX與收到的IDX加以比較，從而可確信這一消息是來自于X的（因只有X有SKX）。第步，A將X的身份IDX和X對M的簽字加上一時戳后，再用自己的秘密鑰加密發(fā)往Y。與前兩種方案相比，第3種方案有很多優(yōu)點。首先，在協(xié)議執(zhí)行以前，各方都不必有共享的信息，從而可防止共謀。第二，只要仲裁者的秘密鑰不被泄露，任何人包括發(fā)方就不能發(fā)送重放的消息。最后，對任何第三方（包括A）來說，X發(fā)往Y的消息都是保密的。數(shù)字簽字標準DSS(Digital Signature Standard)是由美國NIST公布的聯(lián)邦信息處理標準FIPS PUB

14、186，其中采用了上一章介紹的SHA和一新的簽字技術，稱為DSA(Digital Signature Algorithm)。DSS最初于1991年公布，在考慮了公眾對其安全性的反饋意見后，于1993年公布了其修改版。7.2 數(shù)字簽字標準首先將DSS與RSA的簽字方式做一比較。RSA算法既能用于加密和簽字，又能用于密鑰交換。與此不同，DSS使用的算法只能提供數(shù)字簽字功能。圖7.2用于比較RSA簽字和DSS簽字的不同方式。7.2.1 DSS的基本方式圖7.2 RSA簽字與DSS簽字的不同方式采用RSA簽字時，將消息輸入到一個雜湊函數(shù)以產(chǎn)生一個固定長度的安全雜湊值，再用發(fā)方的秘密鑰加密雜湊值就形成了

15、對消息的簽字。消息及其簽字被一起發(fā)給收方，收方得到消息后再產(chǎn)生出消息的雜湊值，且使用發(fā)方的公開鑰對收到的簽字解密。這樣收方就得了兩個雜湊值，如果兩個雜湊值是一樣的，則認為收到的簽字是有效的。DSS簽字也利用一雜湊函數(shù)產(chǎn)生消息的一個雜湊值，雜湊值連同一隨機數(shù)k一起作為簽字函數(shù)的輸入，簽字函數(shù)還需使用發(fā)送方的秘密鑰SKA和供所有用戶使用的一族參數(shù)，稱這一族參數(shù)為全局公開鑰PKG。簽字函數(shù)的兩個輸出s和r就構成了消息的簽字(s，r)。接收方收到消息后再產(chǎn)生出消息的雜湊值，將雜湊值與收到的簽字一起輸入驗證函數(shù)，驗證函數(shù)還需輸入全局公開鑰PKG和發(fā)送方的公開鑰PKA。驗證函數(shù)的輸出如果與收到的簽字成分r

16、相等，則驗證了簽字是有效的。DSA是在ElGamal和Schnorr兩個簽字方案(見下一節(jié))的基礎上設計的，其安全性基于求離散對數(shù)的困難性。算法描述如下： (1) 全局公開鑰p：滿足2L-1p2L 的大素數(shù)，其中512L1024且L是64的倍數(shù)。q：p-1的素因子，滿足2159q2160 ，即q長為160比特。g：gh(p-1)/q mod p，其中h是滿足1h1的任一整數(shù)。7.2.2 數(shù)字簽字算法DSA(2) 用戶秘密鑰xx是滿足0 xq的隨機數(shù)或偽隨機數(shù)。(3) 用戶的公開鑰yygx mod p。(4) 用戶為待簽消息選取的秘密數(shù)kk是滿足0kq的隨機數(shù)或偽隨機數(shù)。(5) 簽字過程用戶對消

17、息M的簽字為(r, s)，其中r(gk mod p) mod q,sk-1(H(M)+xr) mod q，H(M)是由SHA求出的雜湊值。(6) 驗證過程設接收方收到的消息為M，簽字為(r,s)。計算w(s)-1 mod q,u1H(M)w mod qu2r w mod q,v(gu1yu2) mod p mod q檢查 ，若相等，則認為簽字有效。這是因為若(M,r,s)=(M,r,s)，則算法的框圖如圖7.3所示，其中的4個函數(shù)分別為sf1H(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 m

18、od qv =f4(y,q,g,H(M),w,r) (g(H(M)w) mod qyrw mod q) mod p mod q圖7.3 DSA的框圖由于離散對數(shù)的困難性，敵手從r恢復k或從s恢復x都是不可行的。還有一個問題值得注意，即簽字產(chǎn)生過程中的運算主要是求r的模指數(shù)運算r=(gk mod p) mod q，而這一運算與待簽的消息無關，因此能被預先計算。事實上，用戶可以預先計算出很多r和k-1以備以后的簽字使用，從而可大大加快產(chǎn)生簽字的速度?；陔x散對數(shù)問題的數(shù)字簽字體制是數(shù)字簽字體制中最為常用的一類，其中包括ElGamal簽字體制、DSA簽字體制、Okamoto簽字體制等。7.3 其他簽

19、字方案 7.3.1 基于離散對數(shù)問題的數(shù)字簽字體制1. 離散對數(shù)簽字體制ElGamal、DSA、Okamoto等簽字體制都可歸結(jié)為離散對數(shù)簽字體制的特例。(1) 體制參數(shù)p：大素數(shù)；q：p-1或p-1的大素因子；g：gRZ*p，且gq1(mod p)，其中gR Z*p表示g是從Z*p中隨機選取的，其中Z*p=Zp-0；x：用戶A的秘密鑰，1xq；y：用戶A的公開鑰，ygx(mod p)。(2) 簽字的產(chǎn)生過程對于待簽字的消息m，A執(zhí)行以下步驟： 計算m的雜湊值H(m)。 選擇隨機數(shù)k：1kq，計算rgk(mod p)。 從簽字方程akb+cx(mod q)中解出s。方程的系數(shù)a、b、c有許多種

20、不同的選擇方法，表7.1給出了這些可能選擇中的一小部分，以(r, s)作為產(chǎn)生的數(shù)字簽字。（見171頁表7.1）(3) 簽字的驗證過程接收方在收到消息m和簽字(r, s)后，可以按照以下驗證方程檢驗： 2. ElGamal簽字體制(1) 體制參數(shù)p：大素數(shù)；g：Z*p的一個生成元；x：用戶A的秘密鑰，xRZ*p；y：用戶A的公開鑰，ygx(mod p)。(2) 簽字的產(chǎn)生過程對于待簽字的消息m，A執(zhí)行以下步驟： 計算m的雜湊值H(m)。 選擇隨機數(shù)k：kZ*p，計算rgk(mod p)。 計算s(H(m)-xr)k-1(mod p-1)。以(r,s)作為產(chǎn)生的數(shù)字簽字。(3) 簽字驗證過程接收

21、方在收到消息m和數(shù)字簽字(r, s)后，先計算H(m)，并按下式驗證： 正確性可由下式證明：3. Schnorr簽字體制(1) 體制參數(shù)p：大素數(shù)，p2512；q：大素數(shù)，q|(p-1)，q2160；g：gRZ*p,且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ù)字簽字。(3) 簽字驗證過程接收方在收到消息m和數(shù)字簽字(e, s)后，先計算rgsy-e(mod

22、 p)，然后計算H(r,m)，并按下式驗證其正確性可由下式證明：4. Neberg-Rueppel簽字體制該體制是一個消息恢復式簽字體制，即驗證人可從簽字中恢復出原始消息，因此簽字人不需要將被簽消息發(fā)送給驗證人。(1) 體制參數(shù)p：大素數(shù)；q：大素數(shù)，q|(p-1)；g：gRZ*p，且gq1(mod p)；x：用戶A的秘密鑰，xRZ*p；y：用戶A的公開鑰，ygx(mod p)。(2) 簽字的產(chǎn)生過程對于待簽字的消息m，A執(zhí)行以下步驟： 計算出 ，其中R是一個單一映射，并且容易求逆，稱為冗余函數(shù)。 選擇一個隨機數(shù)k(0kq)，計算rg-k mod p。 計算 。 計算sxe+k(mod q)。

23、以(e, s)作為對m的數(shù)字簽字。(3) 簽字的驗證過程接收方收到數(shù)字簽字(e, s)后，通過以下步驟來驗證簽字的有效性： 驗證是否0ep。 驗證是否0sq。 計算vgsy-e(mod p)。 計算mve(mod p)。 驗證是否mR(m)，其中R(m)表示R的值域。 恢復出m=R-1(m)。這個簽字體制的正確性可以由以下等式證明：5. Okamoto簽字體制(1) 體制參數(shù)p：大素數(shù)，且p2512;q：大素數(shù)，q|(p-1)，且q2140；g1, g2：兩個與q同長的隨機數(shù)；x1, x2：用戶A的秘密鑰，兩個小于q的隨機數(shù)；y：用戶A的公開鑰，yg-x11g-x22(mod p)。(2) 簽

24、字的產(chǎn)生過程對于待簽字的消息m，A執(zhí)行以下步驟： 選擇兩個小于q的隨機數(shù)k1,k2RZ*q。 計算雜湊值：eH(gk11gk22(mod p),m)。 計算：s1(k1+ex1)(mod q)。 計算：s2(k2+ex2)(mod q)。以(e, s1, s2)作為對m的數(shù)字簽字。(3) 簽字的驗證過程接收方在收到消息m和數(shù)字簽字(e, s1, s2)后，通過以下步驟來驗證簽字的有效性： 計算vgs11gs22ye(mod p)。 計算e=H(v,m)。 驗證：其正確性可通過下式證明：設n是一個大合數(shù)，找出n的所有素因子是一個困難問題，稱之為大數(shù)分解問題。下面介紹的兩個數(shù)字簽字體制都基于這個問

25、題的困難性。7.3.2 基于大數(shù)分解問題的數(shù)字簽字體制1. Fiat-Shamir簽字體制(1) 體制參數(shù)n：n=pq，其中p和q是兩個保密的大素數(shù)；k：固定的正整數(shù)；y1,y2,yk：用戶A的公開鑰，對任何i(1ik)，yi都是模n的平方剩余；x1,x2,xk：用戶A的秘密鑰，對任何i(1ik)， 。(2) 簽字的產(chǎn)生過程對于待簽字的消息m，A執(zhí)行以下步驟： 隨機選取一個正整數(shù)t。 隨機選取t個介于1和n之間的數(shù)r1,r2,rt，并對任何j(1jt)，計算Rjr 2j(mod n)。 計算雜湊值H(m,R1,R2,Rt)，并依次取出H(m,R1,R2,Rt)的前kt個比特值b11,b1t,b

26、21,b2t,bk1,bkt。 對任何j(1jt)，計算 。以(b11,b1t,b21,b2t,bk1,bkt),(s1,st)作為對m的數(shù)字簽字。(3) 簽字的驗證過程收方在收到消息m和簽字(b11,b1t,b21，,b2t,bk1,bkt),(s1,st)后，用以下步驟來驗證： 對任何j(1jt)，計算 。 計算H(m,R1,R2,Rt)。 驗證b11,b1t,b21,b2t,bk1,bkt是否依次是H(m,R1,R2,Rt)的前kt個比特。如果是，則以上數(shù)字簽字是有效的。正確性可以由以下算式證明：2. Guillou-Quisquater簽字體制(1) 體制參數(shù)n：n=pq，p和q是兩個

27、保密的大素數(shù)；v：gcd(v,(p-1)(q-1)=1；x：用戶A的秘密鑰，xRZ*n；y：用戶A的公開鑰，yZ*n，且xvy1(mod n)。(2) 簽字的產(chǎn)生過程對于待簽消息m，A進行以下步驟： 隨機選擇一個數(shù)kZ*n，計算Tkv(mod n)。 計算雜湊值： e=H(m,T)，且使1ev；否則，返回步驟。 計算skxe mod n。以(e, s)作為對m的簽字。(3) 簽字的驗證過程接收方在收到消息m和數(shù)字簽字(e, s)后，用以下步驟來驗證： 計算出Tsvye(mod n)。 計算出e=H(m,T)。 驗證： 正確性可由以下算式證明：6.1節(jié)介紹過消息認證的基本概念，事實上安全可靠的通

28、信除需進行消息的認證外，還需建立一些規(guī)范的協(xié)議對數(shù)據(jù)來源的可靠性、通信實體的真實性加以認證，以防止欺騙、偽裝等攻擊。本節(jié)以網(wǎng)絡通信的一個基本問題的解決引出認證協(xié)議的基本意義，這一基本問題陳述如下： A和B是網(wǎng)絡的兩個用戶，他們想通過網(wǎng)絡先建立安全的共享密鑰再進行保密通信。那么A(B)如何確信自己正在和B(A)通信而不是和C通信呢？這種通信方式為雙向通信，因此，此時的認證稱為相互認證。類似地，對于單向通信來說，認證稱為單向認證。7.4 認證協(xié)議A、B兩個用戶在建立共享密鑰時需要考慮的核心問題是保密性和實時性。為了防止會話密鑰的偽造或泄露，會話密鑰在通信雙方之間交換時應為密文形式，所以通信雙方事先

29、就應有密鑰或公開鑰。第2個問題實時性則對防止消息的重放攻擊極為重要，實現(xiàn)實時性的一種方法是對交換的每一條消息都加上一個序列號，一個新消息僅當它有正確的序列號時才被接收。但這種方法的困難性是要求每個用戶分別記錄與其他每一用戶交換的消息的序列號，從而增加了用戶的負擔，所以序列號方法一般不用于認證和密鑰交換。7.4.1 相互認證保證消息的實時性常用以下兩種方法： 時戳如果A收到的消息包括一時戳，且在A看來這一時戳充分接近自己的當前時刻， A才認為收到的消息是新的并接受之。這種方案要求所有各方的時鐘是同步的。 詢問-應答用戶A向B發(fā)出一個一次性隨機數(shù)作為詢問，如果收到B發(fā)來的消息（應答）也包含一正確的

30、一次性隨機數(shù)，A就認為B發(fā)來的消息是新的并接受之。其中時戳法不能用于面向連接的應用過程，這是由于時戳法在實現(xiàn)時固有的困難性。首先是需要在不同的處理器時鐘之間保持同步，那么所用的協(xié)議必須是容錯的以處理網(wǎng)絡錯誤，并且是安全的以對付惡意攻擊。第二，如果協(xié)議中任一方的時鐘出現(xiàn)錯誤而暫時地失去了同步，則將使敵手攻擊成功的可能性增加。最后還由于網(wǎng)絡本身存在著延遲，因此不能期望協(xié)議的各方能保持精確的同步。所以任何基于時戳的處理過程、協(xié)議等都必須允許同步有一個誤差范圍?？紤]到網(wǎng)絡本身的延遲，誤差范圍應足夠大；考慮到可能存在的攻擊，誤差范圍又應足夠小。而詢問-應答方式則不適合于無連接的應用過程，這是因為在無連接

31、傳輸以前需經(jīng)詢問|應答這一額外的握手過程，這與無連接應用過程的本質(zhì)特性不符。對無連接的應用程序來說，利用某種安全的時間服務器保持各方時鐘同步是防止重放攻擊最好的方法。通信雙方建立共享密鑰時可采用單鑰加密體制和公鑰加密體制。1. 單鑰加密體制正如5.1節(jié)所介紹的，采用單鑰加密體制為通信雙方建立共享的密鑰時，需要有一個可信的密鑰分配中心KDC，網(wǎng)絡中每一用戶都與KDC有一共享的密鑰，稱為主密鑰。KDC為通信雙方建立一個短期內(nèi)使用的密鑰，稱為會話密鑰，并用主密鑰加密會話密鑰后分配給兩個用戶。這種分配密鑰的方式在實際應用中較為普遍采用，如下一章介紹的Kerberos系統(tǒng)采用的就是這種方式。(1) Ne

32、edham-Schroeder協(xié)議5.1節(jié)中圖5.1所示的采用KDC的密鑰分配過程，可用以下協(xié)議（稱為Needham-Schroeder協(xié)議）來描述： AKDC：IDAIDBN1 KDCA： EKAKSIDBN1EKBKSIDA AB：EKBKSIDA BA：EKSN2 AB：EKSf(N2)式中KA、KB分別是A、B與KDC共享的主密鑰。協(xié)議的目的是由KDC為A、B安全地分配會話密鑰KS，A在第步安全地獲得了KS，而第步的消息僅能被B解讀，因此B在第步安全地獲得了KS ，第步中B向A示意自己已掌握KS，N2用于向A詢問自己在第步收到的KS是否為一新會話密鑰，第步A對B的詢問作出應答，一方面表

33、示自己已掌握KS，另一方面由f(N2)回答了KS的新鮮性?？梢姷凇刹接糜诜乐挂环N類型的重放攻擊，比如敵手在前一次執(zhí)行協(xié)議時截獲第步的消息，然后在這次執(zhí)行協(xié)議時重放，如果雙方?jīng)]有第、兩步的握手過程的話，B就無法檢查出自己得到的KS是重放的舊密鑰。然而以上協(xié)議卻易遭受另一種重放攻擊，假定敵手能獲取舊會話密鑰，則冒充A向B重放第步的消息后，就可欺騙B使用舊會話密鑰。敵手進一步截獲第步B發(fā)出的詢問后，可假冒A作出第步的應答。進而，敵手就可冒充A使用經(jīng)認證過的會話密鑰向B發(fā)送假消息。(2) Needham-Schroeder協(xié)議的改進方案之一為克服以上弱點，可在第步和第步加上一時戳，改進后的協(xié)議如下：

34、 AKDC：IDAIDB KDCA：EKAKSIDBTEKBKSIDAT AB：EKBKSIDAT BA：EKSN1 AB：EKSf(N1)其中T是時戳，用以向A、B雙方保證KS的新鮮性。A和B可通過下式檢查T的實時性： |Clock-T|t1+t2其中Clock為用戶（A或B）本地的時鐘，t1是用戶本地時鐘和KDC時鐘誤差的估計值，t2是網(wǎng)絡的延遲時間。以上協(xié)議中由于T是經(jīng)主密鑰加密的，所以敵手即使知道舊會話密鑰，并在協(xié)議的過去執(zhí)行期間截獲第步的結(jié)果，也無法成功地重放給B，因B對收到的消息可通過時戳檢查其是否為新的。以上改進還存在以下問題： 方案主要依賴網(wǎng)絡中各方時鐘的同步，這種同步可能會由

35、于系統(tǒng)故障或計時誤差而被破壞。如果發(fā)送方的時鐘超前于接收方的時鐘，敵手就可截獲發(fā)送方發(fā)出的消息，等待消息中時戳接近于接收方的時鐘時，再重發(fā)這個消息。這種攻擊稱為等待重放攻擊?？箵舻却胤殴舻囊环N方法是要求網(wǎng)絡中各方以KDC的時鐘為基準定期檢查并調(diào)整自己的時鐘，另一種方法是使用一次性隨機數(shù)的握手協(xié)議，因為接收方向發(fā)送方發(fā)出詢問的隨機數(shù)是他人無法事先預測的，所以敵手即使實施等待重放攻擊，也可被下面的握手協(xié)議檢查出來。(3) Needham-Schroeder協(xié)議的改進方案之二下面的協(xié)議可解決Needham-Schroeder協(xié)議以及改進方案一可能遭受的攻擊： AB：IDANA BKDC：IDBN

36、BEKBIDANATB KDCA：EKAIDBNAKSTBEKBIDAKSTBNB AB：EKBIDAKSTBEKSNB協(xié)議的具體含義如下： A將新產(chǎn)生的一次性隨機數(shù)NA與自己的身份IDA一起以明文形式發(fā)往B，NA以后將與會話密鑰KS一起以加密形式返回給A，以保證A收到的會話密鑰的新鮮性。 B向KDC發(fā)出與A建立會話密鑰的請求，表示請求的消息包括B的身份、一次性隨機數(shù)NB以及由B與KDC共享的主密鑰加密的數(shù)據(jù)項。其中NB以后將與會話密鑰一起以加密形式返回給B以向B保證會話密鑰的新鮮性，請求中由主密鑰加密的數(shù)據(jù)項用于指示KDC向A發(fā)出一個證書，其中的數(shù)據(jù)項有證書接收者A的身份、B建議的證書截止時

37、間TB、B從A收到的一次性隨機數(shù)。 KDC將B產(chǎn)生的NB連同由KDC與B共享的密鑰KB加密的IDAKSTB一起發(fā)給A，其中KS是KDC分配的會話密鑰，EKBIDAKSTB由A當作票據(jù)用于以后的認證。KDC向A發(fā)出的消息還包括由KDC與A共享的主密鑰加密的IDBNAKSTB，A用這一消息可驗證B已收到第步發(fā)出的消息（通過IDB），A還能驗證這一步收到的消息是新的（通過NA），這一消息中還包括KDC分配的會話密鑰KS以及會話密鑰的截止時間TB。 A將票據(jù)EKBIDAKSTB連同由會話密鑰加密的一次性隨機數(shù)NB發(fā)往B，B由票據(jù)得到會話密鑰KS，并由KS得NB。NB由會話密鑰加密的目的是B認證了自己收

38、到的消息不是一個重放,而的確是來自于A。以上協(xié)議為A、B雙方建立共享的會話密鑰提供了一個安全有效的手段。再者，如果A保留由協(xié)議得到的票據(jù)，就可在有效時間范圍內(nèi)不再求助于認證服務器而由以下方式實現(xiàn)雙方的新認證： AB：EKBIDAKSTB,NA BA：NB，EKSNA AB：EKSNBB在第步收到票據(jù)后，可通過TB檢驗票據(jù)是否過時，而新產(chǎn)生的一次性隨機數(shù)NA、NB則向雙方保證了沒有重放攻擊。以上協(xié)議中時間期限TB是B根據(jù)自己的時鐘定的，因此不要求各方之間的同步。2. 公鑰加密體制第5章曾介紹過使用公鑰加密體制分配會話密鑰的方法，下面的協(xié)議也用于這個目的。 AAS： IDAIDB ASA：ESKA

39、SIDAPKATESKASIDBPKBT AB：ESKASIDAPKATESKASIDBPKBTEPKBESKAKST其中SKAS、SKA 分別是AS和A的秘密鑰，PKA、PKB分別是A和B的公開鑰，E為公鑰加密算法，AS是認證服務器（authentication server）。第步，A將自己的身份及欲通信的對方的身份發(fā)送給AS。第步，AS發(fā)給A的兩個鏈接的數(shù)據(jù)項都是由自己的秘密鑰加密（即由AS簽字），分別作為發(fā)放給通信雙方的公鑰證書。第步，A選取會話密鑰并經(jīng)自己的秘密鑰和B的公開鑰加密后連同兩個公鑰證書一起發(fā)往B。因會話密鑰是由A選取，并以密文形式發(fā)送給B，因此包括AS在內(nèi)的任何第3者都無

40、法得到會話密鑰。時戳T用以防止重放攻擊，所以需要各方的時鐘是同步的。下一協(xié)議使用一次性隨機數(shù)，因此不需要時鐘的同步： AKDC：IDAIDB KDCA：ESKAUIDBPKB AB：EPKBNAIDA BKDC：IDBIDAEPKAUNA KDCB：ESKAUIDAPKAEPKBESKAUNAKSIDB BA：EPKAESKAUNAKSIDBNB AB：EKSNB其中SKAU和PKAU分別是KDC的秘密鑰和公開鑰。第步，A通知KDC他想和B建立安全連接。第步，KDC將B的公鑰證書發(fā)給A，公鑰證書包括經(jīng)KDC簽字的B的身份和公鑰。第步，A告訴B想與他通信，并將自己選擇的一次性隨機數(shù)NA發(fā)給B。第

41、步，B向KDC發(fā)出得到A的公鑰證書和會話密鑰的請求，請求中由KDC的公開鑰加密的NA用于讓KDC將建立的會話密鑰與NA聯(lián)系起來，以保證會話密鑰的新鮮性。第步，KDC向B發(fā)出A的公鑰證書以及由自己的秘密鑰和B的公開鑰加密的三元組NA,KS,IDB。三元組由KDC的秘密鑰加密可使B驗證三元組的確是由KDC發(fā)來的，由B的公開鑰加密是防止他人得到三元組后假冒B建立與A的連接。第步，B新產(chǎn)生一個一次性隨機數(shù)NB,連同上一步收到的由KDC的秘密鑰加密的三元組一起經(jīng)A的公開鑰加密后發(fā)往A。第步，A取出會話密鑰，再由會話密鑰加密NB后發(fā)往B，以使B知道A已掌握會話密鑰。以上協(xié)議可進一步做如下改進： 在第、兩步

42、出現(xiàn)NA的地方加上IDA，以說明NA的確是由A產(chǎn)生的而不是其他人產(chǎn)生的，這時IDA，NA就可惟一地識別A發(fā)出的連接請求。電子郵件等網(wǎng)絡應用有一個最大的優(yōu)點就是不要求收發(fā)雙方同時在線，發(fā)送方將郵件發(fā)往接收方的信箱，郵件在信箱中存著，直到接收方閱讀時才打開。郵件消息的報頭必須是明文形式以使SMTP（simple mail transfer protocol-簡單郵件傳輸協(xié)議）或X.400等存儲-轉(zhuǎn)發(fā)協(xié)議能夠處理。然而通常都不希望郵件處理協(xié)議要求郵件的消息本身是明文形式，否則就要求用戶對郵件處理機制的信任。7.4.2 單向認證所以用戶在進行保密通信時，需對郵件消息進行加密以使包括郵件處理系統(tǒng)在內(nèi)的任

43、何第3者都不能讀取郵件的內(nèi)容。再者郵件接收者還希望對郵件的來源即發(fā)方的身份進行認證，以防他人的假冒。與雙向認證一樣，在此仍分為單鑰加密和公鑰加密兩種情況來考慮。1. 單鑰加密對諸如電子郵件等單向通信來說，圖5.2所示的無中心的密鑰分配情況不適用。因為該方案要求發(fā)送方給接收方發(fā)送一請求，并等到接收方發(fā)回一個包含會話密鑰的應答后，才向接收方發(fā)送消息，所以本方案與接收方和發(fā)送方不必同時在線的要求不符。在圖5.1所示的情況中去掉第步和第步就可滿足單向通信的兩個要求。協(xié)議如下： AKDC：IDAIDBN1 KDCA：EKAKSIDBN1EKBKSIDA AB：EKBKSIDAEKSM本協(xié)議不要求B同時在

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

45、鑰加密整個消息要有效得多。如果主要關心認證性，則可使用以下方式： 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簽署的公鑰證書。在很多情況下，用戶都需證明自己的身份，如登錄計算機系統(tǒng)、存取電子銀行中的賬目數(shù)據(jù)庫、從自動出納機ATM(auto

46、matic teller machine)取款等。傳統(tǒng)的方法是使用通行字或個人身份識別號PIN(personal identification number)來證明自己的身份，這些方法的缺點是檢驗用戶通行字或PIN的人或系統(tǒng)可使用用戶的通行字或PIN冒充用戶。7.5 身份證明技術本節(jié)介紹的身份的零知識證明技術，可使用戶在不泄露自己的通行字或PIN的情況下向他人證實自己的身份。交互證明系統(tǒng)由兩方參與，分別稱為證明者（prover，簡記為P）和驗證者（verifier，簡記為V），其中P知道某一秘密（如公鑰密碼體制的秘密鑰或一平方剩余x的平方根），P希望使V相信自己的確掌握這一秘密。交互證明由若干

47、輪組成，在每一輪，P和V可能需根據(jù)從對方收到的消息和自己計算的某個結(jié)果向?qū)Ψ桨l(fā)送消息。比較典型的方式是在每輪V都向P發(fā)出一詢問，P向V做出一應答。所有輪執(zhí)行完后，V根據(jù)P是否在每一輪對自己發(fā)出的詢問都能正確應答，以決定是否接受P的證明。7.5.1 交互證明系統(tǒng)交互證明和數(shù)學證明的區(qū)別是： 數(shù)學證明的證明者可自己獨立地完成證明，而交互證明是由P產(chǎn)生證明、V驗證證明的有效性來實現(xiàn)，因此雙方之間通過某種信道的通信是必需的。交互證明系統(tǒng)須滿足以下要求： 完備性如果P知道某一秘密，V將接受P的證明。 正確性如果P能以一定的概率使V相信P的證明，則P知道相應的秘密。1. 協(xié)議及原理設n=pq，其中p和q是

48、兩個不同的大素數(shù)，x是模n的平方剩余，y是x的平方根。又設n和x是公開的，而p、q和y是保密的。證明者P以y作為自己的秘密。4.1.8節(jié)已證明，求解方程x2a mod n與分解n是等價的。因此他人不知n的兩個素因子p、q而計算y是困難的。P和驗證者V通過交互證明協(xié)議，P向V證明自己掌握秘密y，從而證明了自己的身份。7.5.2 簡化的Fiat-Shamir身份識別方案協(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發(fā)送給V。 若b2axe mod n，V

49、接受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詢問的應答。2. 協(xié)議的完備性、正確性和安全性(1) 完備性如果P和V遵守協(xié)議，且P知道y，則應答brye mod n應是模n下axe的平方根，在協(xié)議的第步V接受P的證明，所以協(xié)議是完備的。(2) 正確性假冒的證明者E可按以下方式以1/2的概率騙得V接受自己的證明： E隨機選r(0rn)和 ，計算ar2x- mod n，將a發(fā)送給V

50、。 V隨機選e0,1，將e發(fā)送給E。 E將r發(fā)送給V。根據(jù)協(xié)議的第步，V的驗證方程是 ，當 時，驗證方程成立，V接受E的證明，即E欺騙成功。因 的概率是1/2，所以E欺騙成功的概率是1/2。另一方面，1/2是E能成功欺騙的最好概率，否則假設E以大于1/2的概率使V相信自己的證明，那么E知道一個a，對這個a他可正確地應答V的兩個詢問e=0和e=1，意味著E能計算b21a mod n和b22ax mod n，即 ，因此E由 即可求得x的平方根y，矛盾。(3) 安全性協(xié)議的安全性可分別從證明者P和驗證者V的角度來考慮。根據(jù)上面的討論，假冒的證明者E欺騙V成功的概率是1/2，對V來說，這個概率太大了。

51、為減小這個概率，可將協(xié)議重復執(zhí)行多次，設執(zhí)行t次，則欺騙者欺騙成功的概率將減小到2-t。下面考慮P的安全性。因為V的詢問是在很小的集合0,1中選取的，V沒有機會產(chǎn)生其他信息，而P發(fā)送給V的信息僅為P知道x的平方根這一事實，因此V無法得知x的平方根。零知識證明起源于最小泄露證明。在交互證明系統(tǒng)中，設P知道某一秘密，并向V證明自己掌握這一秘密，但又不向V泄露這一秘密，這就是最小泄露證明。進一步，如果V除了知道P能證明某一事實外，不能得到其他任何信息，則稱P實現(xiàn)了零知識證明，相應的協(xié)議稱為零知識證明協(xié)議。7.5.3 零知識證明例7.4 圖7.4表示一個簡單的迷宮，C與D之間有一道門，需要知道秘密口令

52、才能將其打開。P向V證明自己能打開這道門，但又不愿向V泄露秘密口令。可采用如下協(xié)議： V在協(xié)議開始時停留在位置A。 P一直走到迷宮深處，隨機選擇位置C或位置D。 P消失后，V走到位置B，然后命令P從某個出口返回位置B。 P服從V的命令，必要時利用秘密口令打開C與D之間的門。 P和V重復以上過程n次。圖7.4 零知識證明協(xié)議示例協(xié)議中，如果P不知道秘密口令，就只能從來路返回B，而不能走另外一條路。此外，P每次猜對V要求走哪一條路的概率是1/2，因此每一輪中P能夠欺騙V的概率是1/2。假定n取16，則執(zhí)行16輪后，P成功欺騙V的概率是1/216=1/65536。于是，如果P16次都能按V的要求返回

53、，V即能證明P確實知道秘密口令。還可以看出，V無法從上述證明過程中獲取絲毫關于P的秘密口令的信息，所以這是一個零知識證明協(xié)議。例7.5 哈密爾頓（Hamilton）回路圖中的回路是指始點和終點相重合的路徑，若回路通過圖的每個頂點一次且僅一次，則稱為哈密爾頓回路，構造圖的哈密爾頓回路是NPC問題?，F(xiàn)在假定P知道圖G的哈密爾頓回路，并希望向V證明這一事實，可采用如下協(xié)議： P隨機地構造一個與圖G同構的圖 ，并將交給V。 V隨機地要求P做下述兩件工作之一： 證明圖G和圖 同構； 指出圖的一條哈密爾頓回路。 P根據(jù)要求做下述兩件工作之一： 證明圖G和圖 同構，但不指出圖G或圖 的哈密爾頓回路； 指出圖

54、 的哈密爾頓回路，但不證明圖G和圖 同構。 P和V重復以上過程n次。協(xié)議執(zhí)行完后，V無法獲得任何信息使自己可以構造圖G的哈密爾頓回路，因此該協(xié)議是零知識證明協(xié)議。事實上，如果P向V證明圖G和圖 同構，這個結(jié)論對V并沒有意義，因為構造圖 的哈密爾頓回路和構造圖G的哈密爾頓回路同樣困難。如果P向V指出圖 的一條哈密爾頓回路，這一事實也無法向V提供任何幫助，因為求兩個圖之間的同構并不比求一個圖的哈密爾頓回路容易。在協(xié)議的每一輪中，P都隨機地構造一個與圖G同構的新圖，因此不論協(xié)議執(zhí)行多少輪，V都得不到任何有關構造圖G的哈密爾頓回路的信息。注：兩個圖G1和G2是同構的是指從G1的頂點集合到G2的頂點集合

55、之間存在一個一一映射，當且僅當若x、y是G1上的相鄰點，(x)和(y)是G2上的相鄰點。1. 協(xié)議及原理在簡化的Fiat-Shamir身份識別方案中，驗證者V接受假冒的證明者證明的概率是1/2，為減小這個概率，將證明者的秘密改為由隨機選擇的t個平方根構成的一個向量y=(y1,y2,yt)，模數(shù)n和向量x=(y21,y22,y2t)是公開的，其中n仍是兩個不相同的大素數(shù)的乘積。7.5.4 Fiat-Shamir身份識別方案協(xié)議如下： P隨機選r(0rn)，計算ar2 mod n，將a發(fā)送給V。 V隨機選e=(e1,e2,et)，其中ei0,1(i=1,2,t)，將e發(fā)送給P。 P計算 ，將b發(fā)送

56、給V。 若 ，V拒絕P的證明，協(xié)議停止。 P和V重復以上過程k次。2. 協(xié)議的完備性、正確性和安全性(1) 完備性若P和V遵守協(xié)議，則V接受P的證明。(2) 正確性如果假冒者E欺騙V成功的概率大于2-kt，意味著E知道一個向量A=(a1,a2,ak)，其中aj是第j次執(zhí)行協(xié)議時產(chǎn)生的，對這個A，E能正確地回答V的兩個不同的詢問E=(e1,e2,ek)、F=(f1,f2,fk)（每一元素是一向量），EF。由EF可設ejfj，ej和fj是第j次執(zhí)行協(xié)議時V的兩個不同的詢問（為向量），簡記為e=ej和f=fj，這一輪對應的aj簡記為a。所以E能計算兩個不同的值， 即 ，所以E可由 求得的平方根，矛盾

57、。(3) 安全性Fiat-Shamir身份識別方案是對簡化的FiatShamir身份識別方案的推廣，首先將V的詢問由一個比特推廣到由t個比特構成的向量，再者基本協(xié)議被執(zhí)行k次。假冒的證明者只有能正確猜測V的每次詢問，才可使V相信自己的證明，成功的概率是2-kt。假設兩個人A和B通過計算機網(wǎng)絡進行智力撲克比賽，比賽中不用第三方做裁判。發(fā)牌者可由任一方擔任，發(fā)牌過程應滿足以下要求： 7.6 其他密碼協(xié)議 7.6.1 智力撲克 任一副牌（即發(fā)給參賽人員手中的牌）是等可能的。 發(fā)給A、B手中的牌沒有重復的。 每人都知道自己手中的牌，但卻不知對方手中的牌。 比賽結(jié)束后，每一方都能發(fā)現(xiàn)對方的欺騙行為（如果

58、有的話）。為滿足這些要求，A、B之間必須以加密形式交換一些信息。在下面的協(xié)議中，加密體制可以是單鑰密碼也可以是公鑰密碼，設EA和EB、DA和DB分別表示A和B的加密變換和解密變換，在比賽結(jié)束之前，這些變換都是保密的，比賽結(jié)束后予以公布用以證明比賽的公正性。要求加密變換滿足交換律，即對任意消息M有： EA(EB(M)=EB(EA(M)比賽開始前A、B協(xié)商好用以表示52張牌的消息w1,w2,w52，協(xié)議中設A為發(fā)牌人，并設給每人發(fā)5張牌。協(xié)議如下： B先洗牌，然后用EB對52個消息分別加密，將加密結(jié)果EB(wi)發(fā)送給A。 A從收到的52個加密的消息中隨機選5個EB(wi)，并發(fā)送給B，B用自己的

59、解密變換DB對這5個值解密，解密后的值作為發(fā)給自己的一副牌。因為B的加密變換EB和解密變換DB都是保密的，所以A無法知道B手中的牌。 A另選5個EB(wi)，用EA加密后發(fā)送給B。 B用DB對收到的值解密后再發(fā)送給A，A用DA對收到的值解密后作為發(fā)給自己的一副牌，這是因為B發(fā)送給A的值是DB(EA(EB(wi)=DB(EB(EA(wi)=EA(wi)其中用到加密變換的交換律。下面考慮該協(xié)議是否滿足發(fā)牌過程的4個要求。對第個要求，B可在協(xié)議的第步檢查A發(fā)來的5個值是否和第步發(fā)來的5個值有重復。為滿足第4個要求，可在比賽結(jié)束后公開所有的加密變換和解密變換，雙方都可檢查對方的牌看是否有欺詐。對第個和

60、第個要求來說，關鍵在于加密變換EB的強度，由EB(wi)可能得不出wi，但有可能得出wi的部分信息。例如，wi是一個比特串，則有可能從EB(wi)得出wi的最后一個比特，因此A可將52個值EB(w1),EB(w2),EB(w52)分成兩個子集，A在發(fā)牌時可將發(fā)給B的牌集中在某一子集中，因此使得第個和第個要求無法滿足。在某些密碼協(xié)議中要求通信雙方在無第三方協(xié)助的情況下，產(chǎn)生一個隨機序列，因為A、B之間可能存在不信任關系，因此隨機序列不能由一方產(chǎn)生再通過電話或網(wǎng)絡告訴另一方。這一問題可通過擲硬幣協(xié)議來實現(xiàn)，擲硬幣協(xié)議有多種實現(xiàn)方式，下面介紹其中的3種。7.6.2 擲硬幣協(xié)議1. 采用平方根擲硬幣協(xié)