現(xiàn)代密碼學(xué)第9章：身份認(rèn)證

1身份認(rèn)證《現(xiàn)代密碼學(xué)》第9章2本章主要內(nèi)容1、身份認(rèn)證概述2、相互認(rèn)證3、單向認(rèn)證4、身份的零知識(shí)證明技術(shù)5、其他的身份認(rèn)證密碼協(xié)議6、典型的認(rèn)證應(yīng)用31．身份認(rèn)證概述為了保護(hù)網(wǎng)絡(luò)資源及落實(shí)安全政策。需要提供可追究責(zé)任的機(jī)制，這里涉及到三個(gè)概念：認(rèn)證、授權(quán)及審計(jì)。（1）認(rèn)證Authentication：在做任何動(dòng)作之前必須要有方法來(lái)識(shí)別動(dòng)作執(zhí)行者的真實(shí)身份。認(rèn)證又稱為鑒別、確認(rèn)。身份認(rèn)證主要是通過(guò)標(biāo)識(shí)和鑒別用戶的身份，防止攻擊者假冒合法用戶獲取訪問(wèn)權(quán)限。（2）授權(quán)Authorization：授權(quán)是指當(dāng)用戶身份被確認(rèn)合法后，賦予該用戶進(jìn)行文件和數(shù)據(jù)等操作的權(quán)限。這種權(quán)限包括讀、寫(xiě)、執(zhí)行及從屬權(quán)等。（3）審計(jì)Auditing：每一個(gè)人都應(yīng)該為自己所做的操作負(fù)責(zé)，所以在做完事情之后都要留下記錄，以便核查責(zé)任。4用戶對(duì)資源的訪問(wèn)過(guò)程5身份認(rèn)證概述

在現(xiàn)實(shí)生活中，我們個(gè)人的身份主要是通過(guò)各種證件來(lái)確認(rèn)的，比如：身份證、戶口本等。計(jì)算機(jī)網(wǎng)絡(luò)信息系統(tǒng)中，各種計(jì)算資源（如：文件、數(shù)據(jù)庫(kù)、應(yīng)用系統(tǒng)）也需要認(rèn)證機(jī)制的保護(hù)，確保這些資源被應(yīng)該使用的人使用。在大多數(shù)情況下，認(rèn)證機(jī)制與授權(quán)和記賬也緊密結(jié)合在一起。身份認(rèn)證是對(duì)網(wǎng)絡(luò)中的主體進(jìn)行驗(yàn)證的過(guò)程，用戶必須提供他是誰(shuí)的證明。身份認(rèn)證往往是許多應(yīng)用系統(tǒng)中安全保護(hù)的第一道設(shè)防，它的失敗可能導(dǎo)致整個(gè)系統(tǒng)的失敗。6身份認(rèn)證系統(tǒng)包含下列三項(xiàng)主要組成元件：（1）認(rèn)證服務(wù)器(AuthenticationServer)負(fù)責(zé)進(jìn)行使用者身份認(rèn)證的工作，服務(wù)器上存放使用者的私有密鑰、認(rèn)證方式及其他使用者認(rèn)證的相關(guān)資訊。（2）認(rèn)證系統(tǒng)用戶端軟體(AuthenticationClientSoftware)認(rèn)證系統(tǒng)用戶端通常都是需要進(jìn)行登陸(login)的設(shè)備或系統(tǒng)，在這些設(shè)備及系統(tǒng)中必須具備可以與認(rèn)證服務(wù)器協(xié)同運(yùn)作的認(rèn)證協(xié)議。也有些情況下認(rèn)證服務(wù)器與認(rèn)證系統(tǒng)用戶端軟體是集成在一起的。（3）認(rèn)證設(shè)備(Authenticator)認(rèn)證設(shè)備是使用者用來(lái)產(chǎn)生或計(jì)算密碼的軟硬件設(shè)備。身份認(rèn)證概述7

從用戶角度來(lái)看，非法用戶常采用以下手段對(duì)身份認(rèn)證過(guò)程中攻擊：數(shù)據(jù)流竊聽(tīng)(Sniffer)：由于認(rèn)證信息要通過(guò)網(wǎng)絡(luò)傳遞，并且很多認(rèn)證系統(tǒng)的口令是未經(jīng)加密的明文，攻擊者通過(guò)竊聽(tīng)網(wǎng)絡(luò)數(shù)據(jù)，就很容易分辨出某種特定系統(tǒng)的認(rèn)證數(shù)據(jù)，并提取出用戶名和口令?？截?重傳：非法用戶截獲信息，然后再傳送給接收者。修改或偽造：非法用戶截獲信息，替換或修改信息后再傳送給接收者，或者非法用戶冒充合法用戶發(fā)送信息。身份認(rèn)證概述8

適合于各種不同場(chǎng)合的認(rèn)證交換機(jī)制有多種選擇與組合。例如：當(dāng)對(duì)等實(shí)體以及通信手段都可信任時(shí)，一個(gè)對(duì)等實(shí)體的身份可以通過(guò)口令來(lái)證實(shí)。該口令能防止出錯(cuò)，但不能防止惡意行為(特別不能防止重演)。相互鑒別可在每個(gè)方向上使用不同的口令來(lái)完成；當(dāng)每個(gè)實(shí)體信任它的對(duì)等實(shí)體但不信任通信手段時(shí)，抗主動(dòng)攻擊的保護(hù)能夠由口令與加密聯(lián)合提供，或由密碼手段提供。防止重演攻擊的需要雙方握手(用保護(hù)參數(shù))，或時(shí)間標(biāo)記(用可信任時(shí)鐘)。帶有重演保護(hù)的相互鑒別，使用三方握手就能達(dá)到。身份認(rèn)證概述9

當(dāng)實(shí)體不信任(或感到它們將來(lái)可能不信任)它們的對(duì)等實(shí)體或通信手段時(shí)可以使用抗抵賴服務(wù)。使用數(shù)字鑒名機(jī)制和公證機(jī)制就能實(shí)現(xiàn)抗抵賴服務(wù)。這些機(jī)制可與上面b中所述的機(jī)制一起使用。在計(jì)算機(jī)網(wǎng)絡(luò)中，通常采用三種方法驗(yàn)證主體身份。一是只有該主體了解的秘密，如口令、密鑰；二是主體攜帶的物品，如智能卡；三是只有該主體具有的獨(dú)一無(wú)二的特征或能力，如指紋、聲音、視網(wǎng)膜血管分布圖或簽字等。身份認(rèn)證概述10

以前介紹過(guò)消息認(rèn)證的基本概念，事實(shí)上安全可靠的通信除需進(jìn)行消息的認(rèn)證外，還需建立一些規(guī)范的協(xié)議對(duì)數(shù)據(jù)來(lái)源的可靠性、通信實(shí)體的真實(shí)性加以認(rèn)證，以防止欺騙、偽裝等攻擊。本節(jié)以網(wǎng)絡(luò)通信的一個(gè)基本問(wèn)題的解決引出認(rèn)證協(xié)議的基本意義，這一基本問(wèn)題陳述如下：2.相互認(rèn)證11A和B是網(wǎng)絡(luò)的兩個(gè)用戶，他們想通過(guò)網(wǎng)絡(luò)先建立安全的共享密鑰再進(jìn)行保密通信。那么A(B)如何確信自己正在和B(A)通信而不是和C通信呢？這種通信方式為雙向通信，因此，此時(shí)的認(rèn)證稱為相互認(rèn)證。類似地，對(duì)于單向通信來(lái)說(shuō)，認(rèn)證稱為單向認(rèn)證。2.相互認(rèn)證12

A、B兩個(gè)用戶在建立共享密鑰時(shí)需要考慮的核心問(wèn)題是保密性和實(shí)時(shí)性。為了防止會(huì)話密鑰的偽造或泄露，會(huì)話密鑰在通信雙方之間交換時(shí)應(yīng)為密文形式，所以通信雙方事先就應(yīng)有密鑰或公開(kāi)鑰。第2個(gè)問(wèn)題實(shí)時(shí)性則對(duì)防止消息的重放攻擊極為重要，實(shí)現(xiàn)實(shí)時(shí)性的一種方法是對(duì)交換的每一條消息都加上一個(gè)序列號(hào)，一個(gè)新消息僅當(dāng)它有正確的序列號(hào)時(shí)才被接收。但這種方法的困難性是要求每個(gè)用戶分別記錄與其他每一用戶交換的消息的序列號(hào)，從而增加了用戶的負(fù)擔(dān)，所以序列號(hào)方法一般不用于認(rèn)證和密鑰交換。2.1相互認(rèn)證的實(shí)現(xiàn)13保證消息的實(shí)時(shí)性常用以下兩種方法：

時(shí)戳 如果A收到的消息包括一時(shí)戳，且在A看來(lái)這一時(shí)戳充分接近自己的當(dāng)前時(shí)刻，A才認(rèn)為收到的消息是新的并接受之。這種方案要求所有各方的時(shí)鐘是同步的。詢問(wèn)-應(yīng)答 用戶A向B發(fā)出一個(gè)一次性隨機(jī)數(shù)作為詢問(wèn)，如果收到B發(fā)來(lái)的消息（應(yīng)答）也包含一正確的一次性隨機(jī)數(shù)，A就認(rèn)為B發(fā)來(lái)的消息是新的并接受之。保證消息的實(shí)時(shí)性14

其中時(shí)戳法不能用于面向連接的應(yīng)用過(guò)程，這是由于時(shí)戳法在實(shí)現(xiàn)時(shí)固有的困難性。首先是需要在不同的處理器時(shí)鐘之間保持同步，那么所用的協(xié)議必須是容錯(cuò)的以處理網(wǎng)絡(luò)錯(cuò)誤，并且是安全的以對(duì)付惡意攻擊。第二，如果協(xié)議中任一方的時(shí)鐘出現(xiàn)錯(cuò)誤而暫時(shí)地失去了同步，則將使敵手攻擊成功的可能性增加。保證消息的實(shí)時(shí)性15

最后還由于網(wǎng)絡(luò)本身存在著延遲，因此不能期望協(xié)議的各方能保持精確的同步。所以任何基于時(shí)戳的處理過(guò)程、協(xié)議等都必須允許同步有一個(gè)誤差范圍。考慮到網(wǎng)絡(luò)本身的延遲，誤差范圍應(yīng)足夠大；考慮到可能存在的攻擊，誤差范圍又應(yīng)足夠小。保證消息的實(shí)時(shí)性16

而詢問(wèn)-應(yīng)答方式則不適合于無(wú)連接的應(yīng)用過(guò)程，這是因?yàn)樵跓o(wú)連接傳輸以前需經(jīng)詢問(wèn)\|應(yīng)答這一額外的握手過(guò)程，這與無(wú)連接應(yīng)用過(guò)程的本質(zhì)特性不符。對(duì)無(wú)連接的應(yīng)用程序來(lái)說(shuō)，利用某種安全的時(shí)間服務(wù)器保持各方時(shí)鐘同步是防止重放攻擊最好的方法。通信雙方建立共享密鑰時(shí)可采用單鑰加密體制和公鑰加密體制。保證消息的實(shí)時(shí)性171.單鑰加密體制采用單鑰加密體制為通信雙方建立共享的密鑰時(shí)，需要有一個(gè)可信的密鑰分配中心KDC，網(wǎng)絡(luò)中每一用戶都與KDC有一共享的密鑰，稱為主密鑰。KDC為通信雙方建立一個(gè)短期內(nèi)使用的密鑰，稱為會(huì)話密鑰，并用主密鑰加密會(huì)話密鑰后分配給兩個(gè)用戶。這種分配密鑰的方式在實(shí)際應(yīng)用中較為普遍采用，如Kerberos系統(tǒng)采用的就是這種方式。2.2單鑰加密體制下共享密鑰的的建立18(1)Needham-Schroeder協(xié)議以下是1978年出現(xiàn)的著名的Needham-Schroeder認(rèn)證協(xié)議。這里需建立一個(gè)稱為鑒別服務(wù)器的可信權(quán)威機(jī)構(gòu)（密鑰分發(fā)中心KDC），擁有每個(gè)用戶的秘密密鑰。若用戶A欲與用戶B通信，則用戶A向鑒別服務(wù)器申請(qǐng)會(huì)話密鑰。在會(huì)話密鑰的分配過(guò)程中，雙方身份得以鑒別。①A→KDC：IDA‖IDB‖N1②KDC→A：EKA[KS‖IDB‖N1‖EKB[KS‖IDA]]③A→B：EKB[KS‖IDA]④B→A：EKS[N2]⑤A→B：EKS[f(N2)]Needham-Schroeder協(xié)議19Needham-Schroeder認(rèn)證過(guò)程

其中KDC是密鑰分發(fā)中心，Ra、Rb是一次性隨機(jī)數(shù)，保密密鑰Ka和Kb分別是A和KDC、B和KDC之間共享的密鑰，Ks是由KDC分發(fā)的A與B的會(huì)話密鑰，EX表示使用密鑰X加密。20

式中KA、KB分別是A、B與KDC共享的主密鑰。協(xié)議的目的是由KDC為A、B安全地分配會(huì)話密鑰KS，A在第②步安全地獲得了KS，而第③步的消息僅能被B解讀，因此B在第③步安全地獲得了KS

，第④步中B向A示意自己已掌握KS，N2用于向A詢問(wèn)自己在第③步收到的KS是否為一新會(huì)話密鑰，第⑤步A對(duì)B的詢問(wèn)作出應(yīng)答，一方面表示自己已掌握KS，另一方面由f(N2)回答了KS的新鮮性。Needham-Schroeder協(xié)議21

可見(jiàn)第④、⑤兩步用于防止一種類型的重放攻擊，比如敵手在前一次執(zhí)行協(xié)議時(shí)截獲第③步的消息，然后在這次執(zhí)行協(xié)議時(shí)重放，如果雙方?jīng)]有第④、⑤兩步的握手過(guò)程的話，B就無(wú)法檢查出自己得到的KS是重放的舊密鑰。Needham-Schroeder協(xié)議22

然而以上協(xié)議卻易遭受另一種重放攻擊，假定敵手能獲取舊會(huì)話密鑰，則冒充A向B重放第③步的消息后，就可欺騙B使用舊會(huì)話密鑰。敵手進(jìn)一步截獲第④步B發(fā)出的詢問(wèn)后，可假冒A作出第⑤步的應(yīng)答。進(jìn)而，敵手就可冒充A使用經(jīng)認(rèn)證過(guò)的會(huì)話密鑰向B發(fā)送假消息。Needham-Schroeder協(xié)議23(2)

Needham-Schroeder協(xié)議的改進(jìn)方案之一為克服以上弱點(diǎn)，可在第②步和第③步加上一時(shí)戳，改進(jìn)后的協(xié)議如下：①A→KDC：IDA‖IDB②KDC→A：EKA[KS‖IDB‖T‖EKB[KS‖IDA‖T]]③A→B：EKB[KS‖IDA‖T]④B→A：EKS[N1]⑤A→B：EKS[f(N1)]Needham-Schroeder協(xié)議改進(jìn)一24

其中T是時(shí)戳，用以向A、B雙方保證KS的新鮮性。A和B可通過(guò)下式檢查T(mén)的實(shí)時(shí)性：

|Clock-T|<Δt1+Δt2

其中Clock為用戶（A或B）本地的時(shí)鐘，Δt1是用戶本地時(shí)鐘和KDC時(shí)鐘誤差的估計(jì)值，Δt2是網(wǎng)絡(luò)的延遲時(shí)間。以上協(xié)議中由于T是經(jīng)主密鑰加密的，所以敵手即使知道舊會(huì)話密鑰，并在協(xié)議的過(guò)去執(zhí)行期間截獲第③步的結(jié)果，也無(wú)法成功地重放給B，因B對(duì)收到的消息可通過(guò)時(shí)戳檢查其是否為新的。Needham-Schroeder協(xié)議改進(jìn)一25

以上改進(jìn)還存在以下問(wèn)題：方案主要依賴網(wǎng)絡(luò)中各方時(shí)鐘的同步，這種同步可能會(huì)由于系統(tǒng)故障或計(jì)時(shí)誤差而被破壞。如果發(fā)送方的時(shí)鐘超前于接收方的時(shí)鐘，敵手就可截獲發(fā)送方發(fā)出的消息，等待消息中時(shí)戳接近于接收方的時(shí)鐘時(shí)，再重發(fā)這個(gè)消息。這種攻擊稱為等待重放攻擊。Needham-Schroeder協(xié)議改進(jìn)一26

抗擊等待重放攻擊的一種方法是要求網(wǎng)絡(luò)中各方以KDC的時(shí)鐘為基準(zhǔn)定期檢查并調(diào)整自己的時(shí)鐘，另一種方法是使用一次性隨機(jī)數(shù)的握手協(xié)議，因?yàn)榻邮辗较虬l(fā)送方發(fā)出詢問(wèn)的隨機(jī)數(shù)是他人無(wú)法事先預(yù)測(cè)的，所以敵手即使實(shí)施等待重放攻擊，也可被下面的握手協(xié)議檢查出來(lái)。Needham-Schroeder協(xié)議改進(jìn)一27(3)Needham-Schroeder協(xié)議的改進(jìn)方案之二下面的協(xié)議可解決Needham-Schroeder協(xié)議以及改進(jìn)方案一可能遭受的攻擊：①A→B：IDA‖NA②B→KDC：IDB‖NB‖EKB[IDA‖NA‖TB]③KDC→A：EKA[IDB‖NA‖KS‖TB]‖EKB[IDA‖KS‖TB]‖NB④A→B：EKB[IDA‖KS‖TB]‖EKS[NB]Needham-Schroeder協(xié)議改進(jìn)二28協(xié)議的具體含義如下：①A將新產(chǎn)生的一次性隨機(jī)數(shù)NA與自己的身份IDA一起以明文形式發(fā)往B，NA以后將與會(huì)話密鑰KS一起以加密形式返回給A，以保證A收到的會(huì)話密鑰的新鮮性。Needham-Schroeder協(xié)議改進(jìn)二29②B向KDC發(fā)出與A建立會(huì)話密鑰的請(qǐng)求，表示請(qǐng)求的消息包括B的身份、一次性隨機(jī)數(shù)NB以及由B與KDC共享的主密鑰加密的數(shù)據(jù)項(xiàng)。其中NB以后將與會(huì)話密鑰一起以加密形式返回給B以向B保證會(huì)話密鑰的新鮮性，請(qǐng)求中由主密鑰加密的數(shù)據(jù)項(xiàng)用于指示KDC向A發(fā)出一個(gè)證書(shū)，其中的數(shù)據(jù)項(xiàng)有證書(shū)接收者A的身份、B建議的證書(shū)截止時(shí)間TB、B從A收到的一次性隨機(jī)數(shù)。Needham-Schroeder協(xié)議改進(jìn)二30③KDC將B產(chǎn)生的NB連同由KDC與B共享的密鑰KB加密的IDA‖KS‖TB一起發(fā)給A，其中KS是KDC分配的會(huì)話密鑰，EKB[IDA‖KS‖TB]由A當(dāng)作票據(jù)用于以后的認(rèn)證。KDC向A發(fā)出的消息還包括由KDC與A共享的主密鑰加密的IDB‖NA‖KS‖TB，A用這一消息可驗(yàn)證B已收到第①步發(fā)出的消息（通過(guò)IDB），A還能驗(yàn)證這一步收到的消息是新的（通過(guò)NA），這一消息中還包括KDC分配的會(huì)話密鑰KS以及會(huì)話密鑰的截止時(shí)間TB。Needham-Schroeder協(xié)議改進(jìn)二31④A將票據(jù)EKB[IDA‖KS‖TB]連同由會(huì)話密鑰加密的一次性隨機(jī)數(shù)NB發(fā)往B，B由票據(jù)得到會(huì)話密鑰KS，并由KS得NB。NB由會(huì)話密鑰加密的目的是B認(rèn)證了自己收到的消息不是一個(gè)重放,而的確是來(lái)自于A。Needham-Schroeder協(xié)議改進(jìn)二32

以上協(xié)議為A、B雙方建立共享的會(huì)話密鑰提供了一個(gè)安全有效的手段。再者，如果A保留由協(xié)議得到的票據(jù)，就可在有效時(shí)間范圍內(nèi)不再求助于認(rèn)證服務(wù)器而由以下方式實(shí)現(xiàn)雙方的新認(rèn)證：①A→B：EKB[IDA‖KS‖TB],N′A②B→A：N′B，EKS[N′A]③A→B：EKS[N′B]Needham-Schroeder協(xié)議改進(jìn)二332.公鑰加密體制曾介紹過(guò)使用公鑰加密體制分配會(huì)話密鑰的方法，下面的協(xié)議也用于這個(gè)目的。①A→AS：IDA‖IDB②AS→A：ESKAS[IDA‖PKA‖T]‖ESKAS[IDB‖PKB‖T]③A→B：ESKAS[IDA‖PKA‖T]‖ESKAS[IDB‖PKB‖T‖EPKB[ESKA[KS‖T]]2.3公鑰加密體制下共享密鑰的建立34

其中SKAS、SKA

分別是AS和A的秘密鑰，PKA、PKB分別是A和B的公開(kāi)鑰，E為公鑰加密算法，AS是認(rèn)證服務(wù)器（authenticationserver）。第①步，A將自己的身份及欲通信的對(duì)方的身份發(fā)送給AS。第②步，AS發(fā)給A的兩個(gè)鏈接的數(shù)據(jù)項(xiàng)都是由自己的秘密鑰加密（即由AS簽字），分別作為發(fā)放給通信雙方的公鑰證書(shū)。公鑰加密體制下共享密鑰的建立35

第③步，A選取會(huì)話密鑰并經(jīng)自己的秘密鑰和B的公開(kāi)鑰加密后連同兩個(gè)公鑰證書(shū)一起發(fā)往B。因會(huì)話密鑰是由A選取，并以密文形式發(fā)送給B，因此包括AS在內(nèi)的任何第3者都無(wú)法得到會(huì)話密鑰。時(shí)戳T用以防止重放攻擊，所以需要各方的時(shí)鐘是同步的。公鑰加密體制下共享密鑰的建立36

下一協(xié)議使用一次性隨機(jī)數(shù)，因此不需要時(shí)鐘的同步：①A→KDC：IDA‖IDB②KDC→A：ESKAU[IDB‖PKB]③A→B：EPKB[NA‖IDA]④B→KDC：IDB‖IDA‖EPKAU[NA]⑤KDC→B：ESKAU[IDA‖PKA]‖EPKB[ESKAU[NA‖KS‖IDB]]⑥B→A：EPKA[ESKAU[NA‖KS‖IDB]‖NB]⑦A→B：EKS[NB]公鑰加密體制下共享密鑰的建立37

其中SKAU和PKAU分別是KDC的秘密鑰和公開(kāi)鑰。第①步，A通知KDC他想和B建立安全連接。第②步，KDC將B的公鑰證書(shū)發(fā)給A，公鑰證書(shū)包括經(jīng)KDC簽字的B的身份和公鑰。第③步，A告訴B想與他通信，并將自己選擇的一次性隨機(jī)數(shù)NA發(fā)給B。第④步，B向KDC發(fā)出得到A的公鑰證書(shū)和會(huì)話密鑰的請(qǐng)求，請(qǐng)求中由KDC的公開(kāi)鑰加密的NA用于讓KDC將建立的會(huì)話密鑰與NA聯(lián)系起來(lái)，以保證會(huì)話密鑰的新鮮性。公鑰加密體制下共享密鑰的建立38

第⑤步，KDC向B發(fā)出A的公鑰證書(shū)以及由自己的秘密鑰和B的公開(kāi)鑰加密的三元組{NA,KS,IDB}。三元組由KDC的秘密鑰加密可使B驗(yàn)證三元組的確是由KDC發(fā)來(lái)的，由B的公開(kāi)鑰加密是防止他人得到三元組后假冒B建立與A的連接。第⑥步，B新產(chǎn)生一個(gè)一次性隨機(jī)數(shù)NB,連同上一步收到的由KDC的秘密鑰加密的三元組一起經(jīng)A的公開(kāi)鑰加密后發(fā)往A。第⑦步，A取出會(huì)話密鑰，再由會(huì)話密鑰加密NB后發(fā)往B，以使B知道A已掌握會(huì)話密鑰。公鑰加密體制下共享密鑰的建立39

以上協(xié)議可進(jìn)一步做如下改進(jìn)：在第⑤、⑥兩步出現(xiàn)NA的地方加上IDA，以說(shuō)明NA的確是由A產(chǎn)生的而不是其他人產(chǎn)生的，這時(shí){IDA，NA}就可惟一地識(shí)別A發(fā)出的連接請(qǐng)求。公鑰加密體制下共享密鑰的建立40Diffie-Hellman算法發(fā)明于1976年，是第一個(gè)公開(kāi)密鑰算法。Diffie-Hellman算法不能用于加密與解密，但可用于密鑰分配。密鑰交換協(xié)議(keyexchangeprotocol)是指兩人或多人之間通過(guò)一個(gè)協(xié)議取得密鑰并用于通信加密。在實(shí)際的密碼應(yīng)用中密鑰交換是很重要的一個(gè)環(huán)節(jié)。比如說(shuō)利用對(duì)稱加密算法進(jìn)行秘密通信，雙方首先需要建立一個(gè)共享密鑰。如果雙方?jīng)]有約定好密鑰，就必須進(jìn)行密鑰交換。如何使得密鑰到達(dá)接收者和發(fā)送者手里是件很復(fù)雜的事情，最早利用公鑰密碼思想提出一種允許陌生人建立共享秘密密鑰的協(xié)議叫Diffle-Hellman密鑰交換。Diffie-Hellman共享密鑰的建立41Diffie-Hellman密鑰交換算法是基于有限域中計(jì)算離散對(duì)數(shù)的困難性問(wèn)題之上的。離散對(duì)數(shù)問(wèn)題是指對(duì)任意正整數(shù)x，計(jì)算gxmodP是容易的；但是一般的已知g、Y和P求x使Y=gxmodP是計(jì)算上幾乎不可能的。當(dāng)Alice和Bob要進(jìn)行秘密通信時(shí)，他們可以按如下步驟建立共享密鑰：（1）Alice選取大的隨機(jī)數(shù)x，并計(jì)算X=gx(modP)，Alice將g、P、X傳送給Bob。（2）Bob選取大的隨機(jī)數(shù)y，并計(jì)算Y=gy(modP)，Bob將Y傳送給Alice。（3）Alice計(jì)算K=Yx(modP)；Bob計(jì)算K’＝Xy(modP)，易見(jiàn)，K=K’=gxy(modP)。Alice和Bob獲得了相同的秘密值K。雙方以K作為加解密鑰以對(duì)稱密鑰算法進(jìn)行保密通信。Diffie-Hellman共享密鑰的建立42監(jiān)聽(tīng)者可以獲得g、P、X、Y，但由于算不出x、y，所以得不到共享密鑰K。雖然Diffie-Hellman密鑰交換算法十分巧妙，但由于沒(méi)有認(rèn)證功能，存在中間人攻擊。當(dāng)Alice和Bob交換數(shù)據(jù)時(shí)，Trudy攔截通信信息，并冒充Alice欺騙Bob，冒充Bob欺騙Alice。其過(guò)程如下：Diffie-Hellman共享密鑰的建立43

中間人攻擊44（1）Alice選取大的隨機(jī)數(shù)x，并計(jì)算X=gx(modP)，Alice將g、P、X傳送給Bob，但被Trudy攔截。（2）Trudy冒充Alice選取大的隨機(jī)數(shù)z，并計(jì)算

Z=gz(modP)，Trudy將Z傳送給Bob。（3）Trudy冒充Bob選取大的隨機(jī)數(shù)z，并計(jì)算

Z=gz(modP)，Trudy將Z傳送給Alice。（4）Bob選取大的隨機(jī)數(shù)y，并計(jì)算

Y=gy(modP)，Bob將Y傳送給Alice，但被Trudy攔截。由（1）、（3）Alice與Trudy共享了一個(gè)秘密密鑰gxz，由（2）、（4）Trudy與Bob共享了一個(gè)秘密密鑰gyz。Diffie-Hellman共享密鑰的建立45站間協(xié)議（station-to-stationprotocol）是一個(gè)密鑰協(xié)商協(xié)議，它能夠挫敗這種中間人攻擊，其方法是讓A、B分別對(duì)消息簽名。（1）A→B：gx（2）B→A：gy||Ek(Sb(gy||gx))（3）A→B：Ek(Sa(gx||gy))Diffie-Hellman共享密鑰的建立46

其中建立的會(huì)話密鑰是k=gxy。站間協(xié)議的一個(gè)改進(jìn)版本沒(méi)有使用加密，建立的會(huì)話密鑰仍然是k=gxy。（1）A→B：gx（2）B→A：gy||Sb(gy||gx)（3）A→B：Sa(gx||gy)

站間協(xié)議具有前向保密性（Forwardsecret）。前向保密性是指長(zhǎng)期密鑰被攻破后，利用長(zhǎng)期密鑰建立的會(huì)話密鑰仍具有保密性。站間協(xié)議中A、B的私鑰泄露不影響會(huì)話密鑰的安全。Diffie-Hellman共享密鑰的建立47首先假定雙方已經(jīng)知道對(duì)方的公開(kāi)密鑰，如交換證書(shū)。ISO認(rèn)證的基本步驟如下：（1）A→B：Ra（2）B→A：Certb||Rb||Sb(Ra||Rb||B)其中Ra、Rb是大的隨機(jī)數(shù)，Certb是B的證書(shū)，Sb()表示使用B的私有密鑰進(jìn)行數(shù)字簽名。如果需要雙向認(rèn)證，需要第三步：（3）A→B：Certa||Sa(Ra||Rb||A)這里Sa()表示使用A的的私有密鑰進(jìn)行數(shù)字簽名。2.4公鑰加密體制下的認(rèn)證過(guò)程48現(xiàn)在我們假定雙方不知道對(duì)方的公開(kāi)密鑰。這時(shí)需要一個(gè)可信的第三方T保存公開(kāi)密鑰庫(kù)。Denning-Sacco認(rèn)證協(xié)議如下：（1）A→T：A||B（2）T→A：ST（B||KB）||ST（A||KA）T把用T的私鑰T簽名的B的公鑰KB發(fā)給A。T也把用T的私鑰T簽名的A自己的公鑰KA發(fā)給A。（3）A→B：EB（SA（K||TA））||ST（B，KB）||ST（A，KA）公鑰加密體制下的DS認(rèn)證協(xié)議49A向B傳送隨機(jī)會(huì)話密鑰K、時(shí)間標(biāo)記TA（都用A自己私鑰簽名并用B的公鑰加密）和兩個(gè)簽了名的公開(kāi)密鑰。B用私鑰解密A的消息，然后用A的公鑰驗(yàn)證簽名。以確信時(shí)間標(biāo)記仍有效。在這里A和B兩人都有密鑰K，他們能夠安全地通信。公鑰加密體制下的DS認(rèn)證協(xié)議50但該協(xié)議是有缺陷的。在和A一起完成協(xié)議后，B能夠偽裝是A。其步驟是：（1）B→T：B||C（2）T→B：ST（C||KC）||ST（B||KB）（3）B(A)→C：EC（SA（K||TA））||ST（C||KC）||ST（A||KA）B將以前從A那里接收的會(huì)話密鑰和時(shí)間標(biāo)記的簽名用C的公鑰加密，并和A和C的證書(shū)一起發(fā)給C。C用私鑰解密A的消息，然后用A的公鑰驗(yàn)證簽名。檢查并確信時(shí)間標(biāo)記仍有效。C現(xiàn)在認(rèn)為正在與A交談，B成功地欺騙了C。在時(shí)間標(biāo)記截止前，B可以欺騙任何人。公鑰加密體制下的DS認(rèn)證協(xié)議51這個(gè)問(wèn)題容易解決。在第（3）步的加密消息內(nèi)加上名字：

EB（SA（A||B||K||TA））||ST（A||KA）||ST（B||KB）因?yàn)檫@一步清楚地表明是A和B在通信，所以現(xiàn)在B就不可能對(duì)C重放舊消息。公鑰加密體制下的DS認(rèn)證協(xié)議52

電子郵件等網(wǎng)絡(luò)應(yīng)用有一個(gè)最大的優(yōu)點(diǎn)就是不要求收發(fā)雙方同時(shí)在線，發(fā)送方將郵件發(fā)往接收方的信箱，郵件在信箱中存著，直到接收方閱讀時(shí)才打開(kāi)。郵件消息的報(bào)頭必須是明文形式以使SMTP（simplemailtransferprotocol-簡(jiǎn)單郵件傳輸協(xié)議）或X.400等存儲(chǔ)-轉(zhuǎn)發(fā)協(xié)議能夠處理。然而通常都不希望郵件處理協(xié)議要求郵件的消息本身是明文形式，否則就要求用戶對(duì)郵件處理機(jī)制的信任。3.單向認(rèn)證53

所以用戶在進(jìn)行保密通信時(shí)，需對(duì)郵件消息進(jìn)行加密以使包括郵件處理系統(tǒng)在內(nèi)的任何第3者都不能讀取郵件的內(nèi)容。再者郵件接收者還希望對(duì)郵件的來(lái)源即發(fā)方的身份進(jìn)行認(rèn)證，以防他人的假冒。單向認(rèn)證54

通過(guò)用戶ID和口令進(jìn)行認(rèn)證是操作系統(tǒng)或應(yīng)用程序通常采用的。如果非法用戶獲得合法用戶身份的口令，他就可以自由訪問(wèn)未授權(quán)的系統(tǒng)資源，所以需要防止口令泄露。易猜的口令或缺省口令也是一個(gè)很嚴(yán)重的問(wèn)題，但一個(gè)更嚴(yán)重的問(wèn)題是有的帳號(hào)根本沒(méi)有口令。實(shí)際上，所有使用弱口令，缺省口令和沒(méi)有口令的帳號(hào)都應(yīng)從系統(tǒng)中清除。另外，很多系統(tǒng)有內(nèi)置的或缺省的帳號(hào)，這些帳號(hào)在軟件的安裝過(guò)程中通?？诹钍遣蛔兊摹９粽咄ǔ２檎疫@些帳號(hào)。因此，所有內(nèi)置的或缺省的帳號(hào)都應(yīng)從系統(tǒng)中移出。3.1單向認(rèn)證中的口令認(rèn)證55

目前各類計(jì)算資源主要靠固定口令的方式來(lái)保護(hù)。這種以固定口令為基礎(chǔ)的認(rèn)證方式存在很多問(wèn)題，對(duì)口令的攻擊包括以下幾種：（1）網(wǎng)絡(luò)數(shù)據(jù)流竊聽(tīng)(Sniffer)：攻擊者通過(guò)竊聽(tīng)網(wǎng)絡(luò)數(shù)據(jù)，如果口令使用明文傳輸，則可被非法截獲。大量的通訊協(xié)議比如Telnet、Ftp、基本HTTP都使用明文口令，這意味著它們?cè)诰W(wǎng)絡(luò)上是以未加密格式傳輸于服務(wù)器端和客戶端，而入侵者只需使用協(xié)議分析器就能查看到這些信息，從而進(jìn)一步分析出口令?？诹钫J(rèn)證的攻擊類型56口令認(rèn)證的攻擊類型--竊聽(tīng)57（2）認(rèn)證信息截取/重放(Record/Replay)：有的系統(tǒng)會(huì)將認(rèn)證信息進(jìn)行簡(jiǎn)單加密后進(jìn)行傳輸，如果攻擊者無(wú)法用第一種方式推算出密碼，可以使用截取/重放方式，需要的是重新編寫(xiě)客戶端軟件以使用加密口令實(shí)現(xiàn)系統(tǒng)登錄?？诹钫J(rèn)證的攻擊類型—截取/重放58截取/重放59（3）字典攻擊：根據(jù)調(diào)查結(jié)果可知，大部份的人為了方便記憶選用的密碼都與自己周遭的事物有關(guān)，例如：身份證字號(hào)、生日、車牌號(hào)碼、在辦公桌上可以馬上看到的標(biāo)記或事物、其他有意義的單詞或數(shù)字，某些攻擊者會(huì)使用字典中的單詞來(lái)嘗試用戶的密碼。所以大多數(shù)系統(tǒng)都建議用戶在口令中加入特殊字符，以增加口令的安全性。（4）窮舉攻擊(BruteForce)：也稱蠻力破解。這是一種特殊的字典攻擊，它使用字符串的全集作為字典。如果用戶的密碼較短，很容易被窮舉出來(lái)，因而很多系統(tǒng)都建議用戶使用長(zhǎng)口令?？诹钫J(rèn)證的攻擊類型60（5）窺探：攻擊者利用與被攻擊系統(tǒng)接近的機(jī)會(huì)，安裝監(jiān)視器或親自窺探合法用戶輸入口令的過(guò)程，以得到口令。（6）社交工程：社會(huì)工程就是指采用非隱蔽方法盜用口令等，比如冒充是處長(zhǎng)或局長(zhǎng)騙取管理員信任得到口令等等。冒充合法用戶發(fā)送郵件或打電話給管理人員，以騙取用戶口令等。比如，在終端上可能發(fā)現(xiàn)如下信息：Pleaseenteryourusernametologon:Yourpassword:這很可能是一個(gè)模仿登錄信息的特洛伊木馬程序，他會(huì)記錄口令，然后傳給入侵者?？诹钫J(rèn)證的攻擊類型61（7）垃圾搜索：攻擊者通過(guò)搜索被攻擊者的廢棄物，得到與攻擊系統(tǒng)有關(guān)的信息，如果用戶將口令寫(xiě)在紙上又隨便丟棄，則很容易成為垃圾搜索的攻擊對(duì)象。口令認(rèn)證的攻擊類型62在口令的設(shè)置過(guò)程中，有許多個(gè)人因素在起作用，攻擊者可以利用這些因素來(lái)解密。由于口令安全性的考慮，人們會(huì)被禁止把口令寫(xiě)在紙上，因此很多人都設(shè)法使自己的口令容易記憶，而這就給攻擊者提供了可乘之機(jī)。為防止攻擊猜中口令。安全口令具有以下特點(diǎn)：（1）位數(shù)>6位。（2）大小寫(xiě)字母混合。如果用一個(gè)大寫(xiě)字母，既不要放在開(kāi)頭，也不要放在結(jié)尾。（3）可以把數(shù)字無(wú)序的加在字母中。（4）系統(tǒng)用戶一定用8位口令，而且包括～!@?！纾＆＊<>?:"{}等特殊符號(hào)。安全口令的特點(diǎn)63不安全的口令則有如下幾種情況：（1）使用用戶名（帳號(hào)）作為口令。這種方法便于記憶，可是在安全上幾乎是不堪一擊。幾乎所有以破解口令為手段的黑客軟件，都首先會(huì)將用戶名作為口令的突破口。（2）用用戶名（帳號(hào)）的變換形式作為口令。將用戶名顛倒或者加前后綴作為口令，比如說(shuō)著名的黑客軟件John，如果用戶名是fool，那么它在嘗試使用fool作為口令之后，還會(huì)試著使用諸如fool123、fool1、loof、loof123、lofo等作為口令。不安全口令的類型64（3）使用自己或者親友的生日作為口令。這種口令有著很大的欺騙性，因?yàn)檫@樣往往可以得到一個(gè)6位或者8位的口令，但實(shí)際上可能的表達(dá)方式只有100×12×31=37200種，即使再考慮到年月日三者共有六種排列順序，一共也只有37200×6=223200種。（4）使用常用的英文單詞作為口令。這種方法比前幾種方法要安全一些。如果選用的單詞是十分偏僻的，那么黑客軟件就可能無(wú)能為力了。不安全口令的類型65應(yīng)采取兩個(gè)步驟以消除口令漏洞。第一步，所有弱口令應(yīng)被加強(qiáng)。但是當(dāng)用戶被要求改變或加強(qiáng)他們的弱口令時(shí)，他們經(jīng)常又選擇一個(gè)容易猜測(cè)的。這就導(dǎo)致了第二步，用戶的口令在被修改后，應(yīng)加以確認(rèn)?？梢杂贸绦騺?lái)拒絕任何不符合安全策略的口令。可以采取以下措施來(lái)加強(qiáng)口令的安全性：（1）在創(chuàng)建口令時(shí)執(zhí)行檢查功能。如檢查口令的長(zhǎng)度。（2）強(qiáng)制使口令周期性過(guò)期。也就是定期更換口令。（3）保持口令歷史記錄，使用戶不能循環(huán)使用舊口令。加強(qiáng)口令安全性的措施66可以使用以下幾種方式進(jìn)行基于口令的認(rèn)證：（1）基于單向函數(shù)計(jì)算機(jī)存儲(chǔ)口令的單向函數(shù)值而不是存儲(chǔ)口令。Alice將口令傳送給計(jì)算機(jī)，計(jì)算機(jī)使用單向函數(shù)計(jì)算，然后把單向函數(shù)的運(yùn)算結(jié)果和它以前存儲(chǔ)的單向函數(shù)值進(jìn)行比較。由于計(jì)算機(jī)不再存儲(chǔ)口令表，所以敵手侵入計(jì)算機(jī)偷取口令的威脅就減少了。（2）摻雜口令如果敵手獲得了存儲(chǔ)口令的單向函數(shù)值的文件，采用字典攻擊是有效的。敵手計(jì)算猜測(cè)的口令的單向函數(shù)值，然后搜索文件，觀察是否有匹配的。

Salt是使這種攻擊更困難的一種方法。Salt是一隨機(jī)字符串，它與口令連接在一起，再用單向函數(shù)對(duì)其運(yùn)算。然后將Salt值和單向函數(shù)運(yùn)算的結(jié)果存入主機(jī)中。Salt只防止對(duì)整個(gè)口令文件采用的的字典攻擊，不能防止對(duì)單個(gè)口令的字典攻擊。加強(qiáng)口令安全性的措施67

（3）SKEYAlice輸入隨機(jī)數(shù)R，計(jì)算機(jī)計(jì)算x1=f（R）、x2=f（x1）、…、xn+1=f（xn）。Alice保管x1，x2，x3，。。。，xn這些數(shù)的列表，計(jì)算機(jī)在登錄數(shù)據(jù)庫(kù)中Alice的名字后面存儲(chǔ)xn+1的值。當(dāng)Alice第一次登錄時(shí)，輸入名字和xn，計(jì)算機(jī)計(jì)算f（xn），并把它和xn+1比較，如果匹配，就證明Alice身份是真的。然后，計(jì)算機(jī)用xn代替xn+1。Alice將從自己的列表中取消xn。Alice每次登錄時(shí)，都輸入她的列表中未取消的最后的數(shù)xI，計(jì)算機(jī)計(jì)算f（xI），并和存儲(chǔ)在它的數(shù)據(jù)庫(kù)中的xI+1比較。當(dāng)Alice用完了列表上面的數(shù)后，需要重新初始化。加強(qiáng)口令安全性的措施68為了增強(qiáng)基于口令認(rèn)證的安全，可以采用以下改進(jìn)方案。（1）認(rèn)證過(guò)程有一定的時(shí)延，增大窮舉嘗試的難度。（2）不可預(yù)測(cè)的口令。修改口令登記程序以便促使用戶使用更加生僻的口令。這樣就進(jìn)一步削弱了字典攻擊。（3）對(duì)無(wú)效用戶名的回答應(yīng)該與對(duì)有效用戶名的回答相同。加強(qiáng)口令安全性的措施69

成功地注冊(cè)進(jìn)入系統(tǒng)，必須首先打入一個(gè)有效的用戶名，然后再打入一個(gè)對(duì)該用戶名是正確的口令。如果當(dāng)用戶名有效時(shí)，要延遲1.5秒后才回答，而對(duì)無(wú)效用戶名是立即回答。這樣破壞者就能查明某個(gè)特定的用戶名是否有效。（4）一次性口令固定密碼有被監(jiān)聽(tīng)及猜中的問(wèn)題，如果使用者使用的密碼可以不斷改變就可以防止固定密碼的問(wèn)題，因此這種不斷改變使用者密碼的技術(shù)便被稱作動(dòng)態(tài)口令(DynamicPassword)或者一次性口令OTP(One-timePassword)。其主要思路是在登錄過(guò)程中加入不確定因素，使每次登錄過(guò)程中傳送的信息都不相同，以提高登錄過(guò)程安全性。系統(tǒng)接收到登錄口令后做一個(gè)驗(yàn)算即可驗(yàn)證用戶的合法性。如挑戰(zhàn)/響應(yīng)。用戶登錄時(shí)，系統(tǒng)產(chǎn)生一個(gè)隨機(jī)數(shù)(nonce)發(fā)送給用戶。用戶將自己的口令和隨機(jī)數(shù)用某種單向算法混合起來(lái)發(fā)送給系統(tǒng)，系統(tǒng)用同樣的方法做驗(yàn)算即可驗(yàn)證用戶身份。加強(qiáng)口令安全性的措施70

與雙向認(rèn)證一樣，在此仍分為單鑰加密和公鑰加密兩種情況來(lái)考慮。單向認(rèn)證的加密方案711.單鑰加密對(duì)諸如電子郵件等單向通信來(lái)說(shuō)，無(wú)中心的密鑰分配情況不適用。因?yàn)樵摲桨敢蟀l(fā)送方給接收方發(fā)送一請(qǐng)求，并等到接收方發(fā)回一個(gè)包含會(huì)話密鑰的應(yīng)答后，才向接收方發(fā)送消息，所以本方案與接收方和發(fā)送方不必同時(shí)在線的要求不符。3.2單向認(rèn)證的單鑰加密72

在圖5.1所示的情況中去掉第④步和第⑤步就可滿足單向通信的兩個(gè)要求。協(xié)議如下：①A→KDC：IDA‖IDB‖N1②KDC→A：EKA[KS‖IDB‖N1‖EKB[KS‖IDA]]③A→B：EKB[KS‖IDA]‖EKS[M]單向認(rèn)證的單鑰加密73

本協(xié)議不要求B同時(shí)在線，但保證了只有B能解讀消息，同時(shí)還提供了對(duì)消息的發(fā)方A的認(rèn)證。然而本協(xié)議不能防止重放攻擊，為此需在消息中加上時(shí)戳，但由于電子郵件處理中的延遲，時(shí)戳的作用極為有限。單向認(rèn)證的單鑰加密742.公鑰加密公鑰加密算法可對(duì)發(fā)送的消息提供保密性、認(rèn)證性或既提供保密性又提供認(rèn)證性，為此要求發(fā)送方知道接收方的公開(kāi)鑰（保密性），或要求接收方知道發(fā)送方的公開(kāi)鑰（認(rèn)證性），或要求每一方都知道另一方的公開(kāi)鑰。3.3單向認(rèn)證的公鑰加密75

如果主要關(guān)心保密性，則可使用以下方式：A→B：EPKB[KS]‖EKS[M]

其中A用B的公開(kāi)鑰加密一次性會(huì)話密鑰，用一次性會(huì)話密鑰加密消息。只有B能夠使用相應(yīng)的秘密鑰得到一次性會(huì)話密鑰，再用一次性會(huì)話密鑰得到消息。這種方案比簡(jiǎn)單地用B的公開(kāi)鑰加密整個(gè)消息要有效得多。76

如果主要關(guān)心認(rèn)證性，則可使用以下方式：

A→B：M‖ESKA[H(M)]

這種方式可實(shí)現(xiàn)對(duì)A的認(rèn)證，但不提供對(duì)M的保密性。如果既要提供保密性又要提供認(rèn)證性，可使用以下方式：

A→B：EPKB[M‖ESKA[H(M)]]單向認(rèn)證的公鑰加密77

后兩種情況要求B知道A的公開(kāi)鑰并確信公開(kāi)鑰的真實(shí)性。為此A還需同時(shí)向B發(fā)送自己的公鑰證書(shū)，表示為A→B：M‖ESKA[H(M)]‖ESKAS[T‖IDA‖PKA]或A→B：EPKB[M‖ESKA[H(M)]‖ESKAS[T‖IDA‖PKA]]

其中ESKAS[T‖IDA‖PKA]是認(rèn)證服務(wù)器AS為A簽署的公鑰證書(shū)。單向認(rèn)證的公鑰加密78

在很多情況下，用戶都需證明自己的身份，如登錄計(jì)算機(jī)系統(tǒng)、存取電子銀行中的賬目數(shù)據(jù)庫(kù)、從自動(dòng)出納機(jī)ATM(automatictellermachine)取款等。傳統(tǒng)的方法是使用通行字或個(gè)人身份識(shí)別號(hào)PIN(personalidentificationnumber)來(lái)證明自己的身份，這些方法的缺點(diǎn)是檢驗(yàn)用戶通行字或PIN的人或系統(tǒng)可使用用戶的通行字或PIN冒充用戶。4.身份的零知識(shí)證明技術(shù)79

本節(jié)介紹的身份的零知識(shí)證明技術(shù)，可使用戶在不泄露自己的通行字或PIN的情況下向他人證實(shí)自己的身份。身份的零知識(shí)證明技術(shù)80

交互證明系統(tǒng)由兩方參與，分別稱為證明者（prover，簡(jiǎn)記為P）和驗(yàn)證者（verifier，簡(jiǎn)記為V），其中P知道某一秘密（如公鑰密碼體制的秘密鑰或一平方剩余x的平方根），P希望使V相信自己的確掌握這一秘密。交互證明由若干輪組成，在每一輪，P和V可能需根據(jù)從對(duì)方收到的消息和自己計(jì)算的某個(gè)結(jié)果向?qū)Ψ桨l(fā)送消息。比較典型的方式是在每輪V都向P發(fā)出一詢問(wèn)，P向V做出一應(yīng)答。所有輪執(zhí)行完后，V根據(jù)P是否在每一輪對(duì)自己發(fā)出的詢問(wèn)都能正確應(yīng)答，以決定是否接受P的證明。交互證明系統(tǒng)81

交互證明和數(shù)學(xué)證明的區(qū)別是：數(shù)學(xué)證明的證明者可自己獨(dú)立地完成證明，而交互證明是由P產(chǎn)生證明、V驗(yàn)證證明的有效性來(lái)實(shí)現(xiàn)，因此雙方之間通過(guò)某種信道的通信是必需的。交互證明系統(tǒng)須滿足以下要求：①完備性如果P知道某一秘密，V將接受P的證明。②正確性如果P能以一定的概率使V相信P的證明，則P知道相應(yīng)的秘密。交互證明系統(tǒng)82

零知識(shí)證明起源于最小泄露證明。在交互證明系統(tǒng)中，設(shè)P知道某一秘密，并向V證明自己掌握這一秘密，但又不向V泄露這一秘密，這就是最小泄露證明。進(jìn)一步，如果V除了知道P能證明某一事實(shí)外，不能得到其他任何信息，則稱P實(shí)現(xiàn)了零知識(shí)證明，相應(yīng)的協(xié)議稱為零知識(shí)證明協(xié)議。身份的零知識(shí)證明技術(shù)834.1零知識(shí)證明零知識(shí)證明（zero-knowledgeproof）的思想是：證明者Peggy擁有某些知識(shí)（如某些長(zhǎng)期沒(méi)有解決的難問(wèn)題的解決方法），零知識(shí)證明就是在不將該知識(shí)的內(nèi)容泄露給驗(yàn)證者Victor的前提下，Peggy向Victor證明自己擁有該知識(shí)。首先，我們看下面Peggy和Victor之間的一段對(duì)話：84Peggy：“我可以對(duì)密文為C的消息進(jìn)行解密?！盫ictor：“我不相信。請(qǐng)證明。”P(pán)eggy（糟糕的回答）：“密鑰是K，您可以看到消息解密成了M?！盫ictor：“哈哈！現(xiàn)在我也知道了密鑰和消息?！边@里，Peggy雖然證明了自己擁有某些知識(shí)（密鑰K及明文M），卻向Victor泄露了這些知識(shí)。一個(gè)更好的對(duì)話是：Peggy：“我可以對(duì)加密為C的消息進(jìn)行解密。”Victor：“我不相信。請(qǐng)證明。”P(pán)eggy（好的回答）：“讓我們使用一個(gè)零知識(shí)協(xié)議，我將以任意高的概率證明我的知識(shí)（但是不會(huì)將關(guān)于消息的任何情況泄露給您）。”Victor：“好”。Peggy和Victor通過(guò)該協(xié)議……零知識(shí)證明經(jīng)典實(shí)例85零知識(shí)證明經(jīng)典實(shí)例

可以使用洞穴例子來(lái)解釋零知識(shí)，C和D之間存在一個(gè)密門(mén)，并且只有知道咒語(yǔ)的人才能打開(kāi)。Peggy知道咒語(yǔ)并想對(duì)Victor證明，但證明過(guò)程中不想泄露咒語(yǔ)。86零知識(shí)證明經(jīng)典實(shí)例步驟如下：（1）Victor站在A點(diǎn)；（2）Peggy一直走進(jìn)洞穴，到達(dá)C點(diǎn)或者D點(diǎn)；（3）在Peggy消失在洞穴中之后，Victor走到B點(diǎn)；（4）Victor隨機(jī)選擇左通道或者右通道，要求Peggy從該通道出來(lái)；（5）Peggy從Victor要求的通道出來(lái)，如果有必要就用咒語(yǔ)打開(kāi)密門(mén)；（6）Peggy和Victor重復(fù)步驟（1）至（5）n次。87零知識(shí)證明協(xié)議示例88零知識(shí)洞穴分析

如果Peggy不知道這個(gè)咒語(yǔ)，那么只能從進(jìn)去的路出來(lái)，如果在協(xié)議的每一輪中Peggy都能按Victor要求的通道出來(lái)，那么Peggy所有n次都猜中的概率是1/2n。經(jīng)過(guò)16輪后，Peggy只有65536分之一的機(jī)會(huì)猜中。于是Victor可以假定，如果所有16次Peggy的證明都是有效的，那么她一定知道開(kāi)啟C點(diǎn)和D點(diǎn)間的密門(mén)的咒語(yǔ)。89圖的同構(gòu)

我們來(lái)再看一個(gè)零知識(shí)證明的例子。圖是否同構(gòu)是NP完全問(wèn)題，對(duì)于一個(gè)非常大的圖，判斷兩個(gè)圖是否同構(gòu)是非常困難的。對(duì)于圖G1和G2，如果存在一個(gè)一一對(duì)應(yīng)的函數(shù)F：F的定義域是G1的頂點(diǎn)集。F的值域是G2的頂點(diǎn)集。當(dāng)且僅當(dāng)[g1,g2]是G1中的一條邊，[F(g1),F(g2)]才是G2中的一條邊，稱G1和G2同構(gòu)的。假設(shè)Peggy知道圖G1和G2之間同構(gòu)，Peggy使用下面的協(xié)議將使Victor相信G1和G2同構(gòu)：90（1）Peggy隨機(jī)置換G1產(chǎn)生另一個(gè)圖H，并且H和G1同構(gòu)。因?yàn)镻eggy知道G1和H同構(gòu)，也就知道了H和G2同構(gòu)。（2）Peggy把H送給Victor。（3）對(duì)如下兩個(gè)問(wèn)題Victor選擇其中的一個(gè)，要求Peggy證明。但是，Victor不要求兩者都證明。證明G1和H同構(gòu)，或者證明G2和H同構(gòu)。（4）Peggy按Victor的要求證明。（5）Peggy和Victor重復(fù)步驟（1）至（4）n次。圖的同構(gòu)91如果Peggy不知道G1和G2之間的同構(gòu)性，Peggy就只能創(chuàng)造一個(gè)圖或者與G1同構(gòu)或者與G2同構(gòu)。每一輪中Peggy只有50%的機(jī)會(huì)猜中Victor的選擇。又因?yàn)镻eggy在協(xié)議的每一輪都產(chǎn)生一個(gè)新圖H，故不管經(jīng)過(guò)多少輪協(xié)議Victor也得不到任何信息，他不能從Peggy的答案中了解G1和G2的同構(gòu)性。圖同構(gòu)的零知識(shí)證明只具有理論意義，從實(shí)現(xiàn)來(lái)看，是不實(shí)用的。圖的同構(gòu)92例1哈密爾頓（Hamilton）回路

圖中的回路是指始點(diǎn)和終點(diǎn)相重合的路徑，若回路通過(guò)圖的每個(gè)頂點(diǎn)一次且僅一次，則稱為哈密爾頓回路，構(gòu)造圖的哈密爾頓回路是NPC問(wèn)題?，F(xiàn)在假定P知道圖G的哈密爾頓回路，并希望向V證明這一事實(shí)，可采用如下協(xié)議：①P隨機(jī)地構(gòu)造一個(gè)與圖G同構(gòu)的圖，并將交給V。②V隨機(jī)地要求P做下述兩件工作之一：證明圖G和圖同構(gòu)；指出圖的一條哈密爾頓回路。哈密爾頓（Hamilton）回路93③P根據(jù)要求做下述兩件工作之一：證明圖G和圖同構(gòu)，但不指出圖G或圖的哈密爾頓回路；指出圖的哈密爾頓回路，但不證明圖G和圖同構(gòu)。④P和V重復(fù)以上過(guò)程n次。哈密爾頓（Hamilton）回路94

協(xié)議執(zhí)行完后，V無(wú)法獲得任何信息使自己可以構(gòu)造圖G的哈密爾頓回路，因此該協(xié)議是零知識(shí)證明協(xié)議。事實(shí)上，如果P向V證明圖G和圖同構(gòu)，這個(gè)結(jié)論對(duì)V并沒(méi)有意義，因?yàn)闃?gòu)造圖的哈密爾頓回路和構(gòu)造圖G的哈密爾頓回路同樣困難。如果P向V指出圖的一條哈密爾頓回路，這一事實(shí)也無(wú)法向V提供任何幫助，因?yàn)榍髢蓚€(gè)圖之間的同構(gòu)并不比求一個(gè)圖的哈密爾頓回路容易。哈密爾頓（Hamilton）回路95

在協(xié)議的每一輪中，P都隨機(jī)地構(gòu)造一個(gè)與圖G同構(gòu)的新圖，因此不論協(xié)議執(zhí)行多少輪，V都得不到任何有關(guān)構(gòu)造圖G的哈密爾頓回路的信息。注：兩個(gè)圖G1和G2是同構(gòu)的是指從G1的頂點(diǎn)集合到G2的頂點(diǎn)集合之間存在一個(gè)一一映射π，當(dāng)且僅當(dāng)若x、y是G1上的相鄰點(diǎn)，π(x)和π(y)是G2上的相鄰點(diǎn)。哈密爾頓（Hamilton）回路96這里我們介紹著名的Feige-Fiat-shamir零知識(shí)身份認(rèn)證協(xié)議的一個(gè)簡(jiǎn)化方案?？尚刨囍俨眠x定一個(gè)隨機(jī)模數(shù)n，n為兩個(gè)大素?cái)?shù)乘積，實(shí)際中至少為為512位或長(zhǎng)達(dá)1024位。仲裁方產(chǎn)生隨機(jī)數(shù)v，使x2=vmodn，即v為模n的平方剩余，且有v-1modn存在。以v作為Peggy的公鑰，而后計(jì)算最小的整數(shù)s：s=sqrt(v-1)modn作為Peggy的私鑰。實(shí)施身份證明的協(xié)議如下：Fiat-Shamir零知識(shí)身份認(rèn)證協(xié)議簡(jiǎn)化方案97（1）用戶Peggy取隨機(jī)數(shù)r，這里r＜m，計(jì)算x=r2modm，把x送給Victor；（2）Victor把一個(gè)隨機(jī)位b送給Peggy；（3）若b=0，則Peggy將r送給Victor；若b=1，則Peggy將y=rs

送給Victor；（4）若b=0，則Victor驗(yàn)證x=r2modm，從而證實(shí)Peggy知道sqrt(x)；若b=1，則Victor驗(yàn)證x=y2.vmodm，從而證實(shí)Peggy知道s。這是一輪鑒定，Peggy和Victor可將此協(xié)議重復(fù)t次，直到Victor相信Peggy知道s為止。4.2Fiat-Shamir零知識(shí)身份認(rèn)證協(xié)議簡(jiǎn)化方案981.協(xié)議及原理在簡(jiǎn)化的Fiat-Shamir身份識(shí)別方案中，驗(yàn)證者V接受假冒的證明者證明的概率是1/2，為減小這個(gè)概率，將證明者的秘密改為由隨機(jī)選擇的t個(gè)平方根構(gòu)成的一個(gè)向量y=(y1,y2,…,yt)，模數(shù)n和向量x=(y21,y22,…,y2t)是公開(kāi)的，其中n仍是兩個(gè)不相同的大素?cái)?shù)的乘積。Fiat-Shamir身份識(shí)別方案99協(xié)議如下：①P隨機(jī)選r(0<r<n)，計(jì)算a≡r2modn，將a發(fā)送給V。②V隨機(jī)選e=(e1,e2,…,et)，其中ei∈{0,1}(i=1,2,…,t)，將e發(fā)送給P。③P計(jì)算，將b發(fā)送給V。④若，V拒絕P的證明，協(xié)議停止。⑤P和V重復(fù)以上過(guò)程k次。Fiat-Shamir身份識(shí)別協(xié)議原理1001.協(xié)議及原理設(shè)n=pq，其中p和q是兩個(gè)不同的大素?cái)?shù)，x是模n的平方剩余，y是x的平方根。又設(shè)n和x是公開(kāi)的，而p、q和y是保密的。證明者P以y作為自己的秘密。已證明，求解方程x2≡amodn與分解n是等價(jià)的。因此他人不知n的兩個(gè)素因子p、q而計(jì)算y是困難的。P和驗(yàn)證者V通過(guò)交互證明協(xié)議，P向V證明自己掌握秘密y，從而證明了自己的身份。簡(jiǎn)化的Fiat-Shamir身份識(shí)別方案101協(xié)議如下：①P隨機(jī)選r(0<r<n)，計(jì)算a≡r2modn，將a發(fā)送給V。②V隨機(jī)選e∈{0,1}，將e發(fā)送給P。③P計(jì)算b≡ryemodn，即e=0時(shí)，b=r；e=1時(shí)，b=rymodn。將b發(fā)送給V。④若b2≡axemodn，V接受P的證明。簡(jiǎn)化的Fiat-Shamir身份識(shí)別方案102

在協(xié)議的前3步，P和V之間共交換了3個(gè)消息，這3個(gè)消息的作用分別是：第1個(gè)消息是P用來(lái)聲稱自己知道a的平方根；第2個(gè)消息e是V的詢問(wèn)，如果e=0，P必須展示a的平方根，即r，如果e=1，P必須展示被加密的秘密，即rymodn；第3個(gè)消息b是P對(duì)V詢問(wèn)的應(yīng)答。簡(jiǎn)化的Fiat-Shamir身份識(shí)別方案1032.協(xié)議的完備性、正確性和安全性(1)完備性如果P和V遵守協(xié)議，且P知道y，則應(yīng)答b≡ryemodn應(yīng)是模n下axe的平方根，在協(xié)議的第④步V接受P的證明，所以協(xié)議是完備的。Fiat-Shamir身份識(shí)別協(xié)議分析104(2)正確性假冒的證明者E可按以下方式以1/2的概率騙得V接受自己的證明：①E隨機(jī)選r(0<r<n)和，計(jì)算a≡r2x-modn，將a發(fā)送給V。②V隨機(jī)選e∈{0,1}，將e發(fā)送給E。③E將r發(fā)送給V。Fiat-Shamir身份識(shí)別協(xié)議分析105(2)正確性如果假冒者E欺騙V成功的概率大于2-kt，意味著E知道一個(gè)向量A=(a1,a2,…,ak)，其中aj是第j次執(zhí)行協(xié)議時(shí)產(chǎn)生的，對(duì)這個(gè)A，E能正確地回答V的兩個(gè)不同的詢問(wèn)E=(e1,e2,…,ek)、F=(f1,f2,…,fk)（每一元素是一向量），E≠F。由E≠F可設(shè)ej≠fj，ej和fj是第j次執(zhí)行協(xié)議時(shí)V的兩個(gè)不同的詢問(wèn)（為向量），簡(jiǎn)記為e=ej和f=fj，這一輪對(duì)應(yīng)的aj簡(jiǎn)記為a。Fiat-Shamir身份識(shí)別協(xié)議分析106

所以E能計(jì)算兩個(gè)不同的值，即，所以E可由求得的平方根，矛盾。Fiat-Shamir身份識(shí)別協(xié)議分析107(3)安全性協(xié)議的安全性可分別從證明者P和驗(yàn)證者V的角度來(lái)考慮。根據(jù)上面的討論，假冒的證明者E欺騙V成功的概率是1/2，對(duì)V來(lái)說(shuō)，這個(gè)概率太大了。為減小這個(gè)概率，可將協(xié)議重復(fù)執(zhí)行多次，設(shè)執(zhí)行t次，則欺騙者欺騙成功的概率將減小到2-t。Fiat-Shamir身份識(shí)別協(xié)議分析108

下面考慮P的安全性。因?yàn)閂的詢問(wèn)是在很小的集合{0,1}中選取的，V沒(méi)有機(jī)會(huì)產(chǎn)生其他信息，而P發(fā)送給V的信息僅為P知道x的平方根這一事實(shí)，因此V無(wú)法得知x的平方根。Fiat-Shamir身份識(shí)別協(xié)議分析109(3)安全性

Fiat-Shamir身份識(shí)別方案是對(duì)簡(jiǎn)化的Fiat

Shamir身份識(shí)別方案的推廣，首先將V的詢問(wèn)由一個(gè)比特推廣到由t個(gè)比特構(gòu)成的向量，再者基本協(xié)議被執(zhí)行k次。假冒的證明者只有能正確猜測(cè)V的每次詢問(wèn)，才可使V相信自己的證明，成功的概率是2-kt。Fiat-Shamir身份識(shí)別協(xié)議分析110

根據(jù)協(xié)議的第④步，V的驗(yàn)證方程是

，當(dāng)時(shí)，驗(yàn)證方程成立，V接受E的證明，即E欺騙成功。因的概率是1/2，所以E欺騙成功的概率是1/2。Fiat-Shamir身份識(shí)別協(xié)議分析111另一方面，1/2是E能成功欺騙的最好概率，否則假設(shè)E以大于1/2的概率使V相信自己的證明，那么E知道一個(gè)a，對(duì)這個(gè)a他可正確地應(yīng)答V的兩個(gè)詢問(wèn)e=0和e=1，意味著E能計(jì)算b21≡amodn和b22≡axmodn，即，因此E由即可求得x

的平方根y，矛盾。Fiat-Shamir身份識(shí)別協(xié)議分析1126.1智力撲克協(xié)議假設(shè)兩個(gè)人A和B通過(guò)計(jì)算機(jī)網(wǎng)絡(luò)進(jìn)行智力撲克比賽，比賽中不用第三方做裁判。發(fā)牌者可由任一方擔(dān)任，發(fā)牌過(guò)程應(yīng)滿足以下要求：5.其他密碼協(xié)議113①任一副牌（即發(fā)給參賽人員手中的牌）是等可能的。②發(fā)給A、B手中的牌沒(méi)有重復(fù)的。③每人都知道自己手中的牌，但卻不知對(duì)方手中的牌。④比賽結(jié)束后，每一方都能發(fā)現(xiàn)對(duì)方的欺騙行為（如果有的話）。5.1智力撲克協(xié)議114

為滿足這些要求，A、B之間必須以加密形式交換一些信息。在下面的協(xié)議中，加密體制可以是單鑰密碼也可以是公鑰密碼，設(shè)EA和EB、DA和DB分別表示A和B的加密變換和解密變換，在比賽結(jié)束之前，這些變換都是保密的，比賽結(jié)束后予以公布用以證明比賽的公正性。要求加密變換滿足交換律，即對(duì)任意消息M有：EA(EB(M))=EB(EA(M))5.1智力撲克協(xié)議115

比賽開(kāi)始前A、B協(xié)商好用以表示52張牌的消息w1,w2,…,w52，協(xié)議中設(shè)A為發(fā)牌人，并設(shè)給每人發(fā)5張牌。協(xié)議如下：①B先洗牌，然后用EB對(duì)52個(gè)消息分別加密，將加密結(jié)果EB(wi)發(fā)送給A。②A從收到的52個(gè)加密的消息中隨機(jī)選5個(gè)EB(wi)，并發(fā)送給B，B用自己的解密變換DB對(duì)這5個(gè)值解密，解密后的值作為發(fā)給自己的一副牌。因?yàn)锽的加密變換EB和解密變換DB都是保密的，所以A無(wú)法知道B手中的牌。智力撲克協(xié)議116③A另選5個(gè)EB(wi)，用EA加密后發(fā)送給B。④B用DB對(duì)收到的值解密后再發(fā)送給A，A用DA對(duì)收到的值解密后作為發(fā)給自己的一副牌，這是因?yàn)锽發(fā)送給A的值是DB(EA(EB(wi)))=DB(EB(EA(wi)))=EA(wi)其中用到加密變換的交換律。5.1智力撲克協(xié)議117

下面考慮該協(xié)議是否滿足發(fā)牌過(guò)程的4個(gè)要求。對(duì)第②個(gè)要求，B可在協(xié)議的第③步檢查A發(fā)來(lái)的5個(gè)值是否和第②步發(fā)來(lái)的5個(gè)值有重復(fù)。為滿足第4個(gè)要求，可在比賽結(jié)束后公開(kāi)所有的加密變換和解密變換，雙方都可檢查對(duì)方的牌看是否有欺詐。對(duì)第①個(gè)和第③個(gè)要求來(lái)說(shuō)，關(guān)鍵在于加密變換EB的強(qiáng)度，由EB(wi)可能得不出wi，但有可能得出wi的部分信息。例如，wi是一個(gè)比特串，則有可能從EB(wi)得出wi的最后一個(gè)比特，因此A可將52個(gè)值EB(w1),EB(w2),…,EB(w52)分成兩個(gè)子集，A在發(fā)牌時(shí)可將發(fā)給B的牌集中在某一子集中，因此使得第①個(gè)和第③個(gè)要求無(wú)法滿足。5.1智力撲克協(xié)議118

在某些密碼協(xié)議中要求通信雙方在無(wú)第三方協(xié)助的情況下，產(chǎn)生一個(gè)隨機(jī)序列，因?yàn)锳、B之間可能存在不信任關(guān)系，因此隨機(jī)序列不能由一方產(chǎn)生再通過(guò)電話或網(wǎng)絡(luò)告訴另一方。這一問(wèn)題可通過(guò)擲硬幣協(xié)議來(lái)實(shí)現(xiàn)，擲硬幣協(xié)議有多種實(shí)現(xiàn)方式，下面介紹其中的3種。5.2擲硬幣協(xié)議1191.采用平方根擲硬幣協(xié)議如下：①A選擇兩個(gè)大素?cái)?shù)p、q，將乘積n=pq發(fā)送給B。②B在1和n/2之間，隨機(jī)選擇一個(gè)整數(shù)u，計(jì)算z≡u(píng)2modn，并將z發(fā)送給A。③A計(jì)算模n下z的4個(gè)平方根±x和±y（因A知道n的分解，所以可做到），設(shè)x′是xmodn和-xmodn中較小者，y′是ymodn和-ymodn中較小者，則由于1<u<n/2，所以u(píng)為x′和y′之一。平方根擲硬幣協(xié)議120④A猜測(cè)u=x′或u=y′，或者A找出最小的i使得x′的第i個(gè)比特與y′的第i個(gè)比特不同，A猜測(cè)u的第i個(gè)比特是0還是1。A將猜測(cè)發(fā)送給B。⑤B告訴A猜測(cè)正確或不正確，并將u的值發(fā)送給A。平方根擲硬幣協(xié)議121⑥A公開(kāi)n的因子。因u是B隨機(jī)選取的，A不知道u，所以要猜測(cè)u只能是計(jì)算模n下z的4個(gè)平方根，猜中的概率是12。再考慮B如何能欺騙A，如果B在A猜測(cè)完后能夠改變u的值，則A的猜測(cè)必不正確，A可通過(guò)

檢查出B是否改變了u的值，所以B要想改變u的值就只能在x′和y′之間進(jìn)行。而B(niǎo)若掌握x′和y′，就可通過(guò)gcd{x′-y′,n}或gcd{x′+y′,n}求出p和q，說(shuō)明B的欺騙與分解n是等價(jià)的。平方根擲硬幣協(xié)議122

例2本例是采用平方根擲硬幣的一個(gè)具體實(shí)現(xiàn)過(guò)程：①A取p=3,q=7，將n=21發(fā)送給B。②B在1和21/2之間，隨機(jī)選擇一個(gè)整數(shù)u=2，計(jì)算z≡22modn≡4并將z=4發(fā)送給A。③A計(jì)算模21下z=4的4個(gè)平方根x=2,-x=19,y=5,-y=16，取x′=2，y′=5。平方根擲硬幣協(xié)議123④A猜測(cè)u=5并將猜測(cè)發(fā)送給B\.⑤B告訴A猜測(cè)不正確，并將u=2發(fā)送給A，A檢驗(yàn)u=2在1和21/2之間且滿足4≡22mod21，A知道自己輸了。⑥A公開(kāi)n=21的因子p=3,q=7，B檢驗(yàn)n=pq，知道自己贏了。平方根擲硬幣協(xié)議1242.利用單向函數(shù)擲硬幣設(shè)A、B都知道某一單向函數(shù)f(x)，但都不知道該函數(shù)的逆函數(shù)，協(xié)議如下：①B選擇一個(gè)隨機(jī)數(shù)x，求y=f(x)并發(fā)送給A。②A對(duì)x的奇偶性進(jìn)行猜測(cè)，并將結(jié)果告訴B。③B告訴A猜測(cè)正確或不正確，并將x發(fā)送給A。由于A不知道f(x)的逆函數(shù)，因此無(wú)法通過(guò)B發(fā)過(guò)來(lái)的y得出x，即只能猜測(cè)x的奇偶性。而B(niǎo)若在A做出猜測(cè)以后改變x，A可通過(guò)

檢查出來(lái)。單向函數(shù)擲硬幣協(xié)議1253.利用二次剩余擲硬幣設(shè)n是兩個(gè)大素?cái)?shù)p、q的乘積，即n=pq。整數(shù)a滿足0<a<n和gcd(a,n)=1，則有一半的a，其Jacobi符號(hào)，而在滿足

的所有a中，只有一半是模n的平方剩余，而判斷a是否為模n的平方剩余與分解n是等價(jià)的。二次剩余擲硬幣協(xié)議126協(xié)議如下：①B選擇p、q，計(jì)算n=pq；再選取滿足

的隨機(jī)數(shù)a，將n和a發(fā)送給A。②A猜測(cè)a是模n的平方剩余或非平方剩余，并將結(jié)果告訴B。③B告訴A猜測(cè)正確或不正確，并將p、q發(fā)送給A。④A檢查p、q都是素?cái)?shù)且n=pq。顯然，A猜中的概率是1/2。協(xié)議執(zhí)行完后，A根據(jù)p、q可求出amodn的4個(gè)平方根（如果a是模n的平方剩余），以檢查B是否在A猜測(cè)