密碼協(xié)議詳解課件

現(xiàn)代密碼學(xué)21世紀(jì)高等學(xué)校計(jì)算機(jī)規(guī)劃教材Modern

Cryptography彭代淵信息科學(xué)與技術(shù)學(xué)院dypeng@2009.9-2010.1作者：何大可彭代淵唐小虎何明星梅其祥出版社：人民郵電出版社1現(xiàn)代密碼學(xué)21世紀(jì)高等學(xué)校計(jì)算機(jī)規(guī)劃教材ModernCr現(xiàn)代密碼學(xué)

Modern

Cryptography彭代淵信息科學(xué)與技術(shù)學(xué)院dypeng@2009年12月第7章密碼協(xié)議2現(xiàn)代密碼學(xué)

ModernCryptography彭代淵第7章密碼協(xié)議7.1密碼協(xié)議概述7.2實(shí)體認(rèn)證協(xié)議

7.3密鑰認(rèn)證協(xié)議

7.4比特承諾協(xié)議

7.5零知識證明與身份識別協(xié)議3第7章密碼協(xié)議7.1密碼協(xié)議概述37.1密碼協(xié)議概述協(xié)議(Protocol)基本概念兩個(gè)或兩個(gè)以上的參與者為完成某項(xiàng)特定任務(wù)而采取的一系列步驟。三層含義協(xié)議是有序的過程，每一步必須依次執(zhí)行協(xié)議至少需要兩個(gè)參與者通過執(zhí)行協(xié)議必須能夠完成某項(xiàng)任務(wù)47.1密碼協(xié)議概述協(xié)議(Protocol)47.1密碼協(xié)議概述協(xié)議(Protocol)特點(diǎn)協(xié)議的參與方必須了解協(xié)議，明確協(xié)議執(zhí)行的所有步驟協(xié)議的參與方都承諾按協(xié)議步驟執(zhí)行協(xié)議協(xié)議必須清楚、完整，對每種可能的情況必須規(guī)定明確、具體的動(dòng)作基本要求有效性公平性完整性57.1密碼協(xié)議概述協(xié)議(Protocol)57.1密碼協(xié)議概述密碼協(xié)議（安全協(xié)議）具有安全功能的協(xié)議——安全協(xié)議安全協(xié)議的設(shè)計(jì)必須采用密碼技術(shù)——密碼協(xié)議具體意義：密碼協(xié)議是建立在密碼體制基礎(chǔ)上的一種交互通信的協(xié)議，它運(yùn)行在計(jì)算機(jī)通信網(wǎng)或分布式系統(tǒng)中，借助于密碼算法來達(dá)到安全功能密碼技術(shù)：隨機(jī)數(shù)生成、加密/解密算法、Hash運(yùn)算、數(shù)字簽名等

安全功能：密鑰建立、密鑰分配、消息鑒別、身份認(rèn)證應(yīng)用系統(tǒng)：電子選舉、電子拍賣、公平電子交易等。67.1密碼協(xié)議概述密碼協(xié)議（安全協(xié)議）密碼技術(shù)：隨機(jī)數(shù)生7.1密碼協(xié)議概述密碼協(xié)議分類—按協(xié)議執(zhí)行的輪數(shù)分2輪協(xié)議3輪協(xié)議，……，n輪協(xié)議密碼協(xié)議分類—按協(xié)議功能分身份認(rèn)證協(xié)議密鑰分配協(xié)議密鑰協(xié)商協(xié)議秘密共享協(xié)議不經(jīng)意傳輸協(xié)議，……77.1密碼協(xié)議概述密碼協(xié)議分類—按協(xié)議執(zhí)行的輪數(shù)分77.1密碼協(xié)議概述密碼協(xié)議分類—按協(xié)議應(yīng)用目標(biāo)分選舉協(xié)議拍賣協(xié)議支付協(xié)議，……密碼協(xié)議分類—按協(xié)議的交互性分交互協(xié)議非交互協(xié)議密碼協(xié)議分類—按協(xié)議第三方性質(zhì)分仲裁協(xié)議裁決協(xié)議自動(dòng)執(zhí)行協(xié)議87.1密碼協(xié)議概述密碼協(xié)議分類—按協(xié)議應(yīng)用目標(biāo)分8第7章密碼協(xié)議7.1密碼協(xié)議概述7.2實(shí)體認(rèn)證協(xié)議

7.3密鑰認(rèn)證協(xié)議

7.4比特承諾協(xié)議

7.5零知識證明與身份識別協(xié)議9第7章密碼協(xié)議7.1密碼協(xié)議概述97.2實(shí)體認(rèn)證協(xié)議認(rèn)證：一個(gè)實(shí)體向另一個(gè)實(shí)體證明某種聲稱的過程認(rèn)證協(xié)議：主要目標(biāo)是確認(rèn)某個(gè)主體的真實(shí)性，確保信息的安全性認(rèn)證協(xié)議分類消息認(rèn)證協(xié)議：驗(yàn)證消息與其主體的一致性實(shí)體認(rèn)證協(xié)議：驗(yàn)證消息發(fā)送者所聲稱的身份密鑰認(rèn)證協(xié)議（認(rèn)證的密鑰建立協(xié)議）：生成、獲得加（解）密密鑰107.2實(shí)體認(rèn)證協(xié)議認(rèn)證：一個(gè)實(shí)體向另一個(gè)實(shí)體證明某種聲稱7.2實(shí)體認(rèn)證協(xié)議身份認(rèn)證協(xié)議：驗(yàn)證用戶知道什么（如口令等）、驗(yàn)證用戶擁有什么（如IC卡等）或驗(yàn)證用戶具有什么特征（如指紋、掌紋、虹膜、DNA等）身口令認(rèn)證協(xié)議（PAP，PasswordAuthenticationProtocol）：通過驗(yàn)證用戶口令來進(jìn)行身份認(rèn)證單向口令身份認(rèn)證協(xié)議協(xié)議7.1簡單口令身份認(rèn)證協(xié)議協(xié)議7.2動(dòng)態(tài)口令身份認(rèn)證協(xié)議

協(xié)議7.3基于口令的智能卡認(rèn)證協(xié)議

雙向口令身份認(rèn)證協(xié)議協(xié)議7.4基于Hash函數(shù)的雙向口令身份認(rèn)證協(xié)議協(xié)議7.5基于對稱密碼的雙向認(rèn)證協(xié)議

協(xié)議7.6基于非對稱密碼的雙向認(rèn)證協(xié)議

117.2實(shí)體認(rèn)證協(xié)議身份認(rèn)證協(xié)議：驗(yàn)證用戶知道什么（如口令第7章密碼協(xié)議7.1密碼協(xié)議概述7.2實(shí)體認(rèn)證協(xié)議

7.3密鑰認(rèn)證協(xié)議

7.4比特承諾協(xié)議

7.5零知識證明與身份識別協(xié)議12第7章密碼協(xié)議7.1密碼協(xié)議概述127.3密鑰認(rèn)證協(xié)議密鑰認(rèn)證協(xié)議：對通信主體A和B及建立的密鑰K進(jìn)行認(rèn)證

只有A、B（或可信第三方TTP）能夠知道KA和B確認(rèn)對方知道KA和B確認(rèn)K是最新建立的137.3密鑰認(rèn)證協(xié)議密鑰認(rèn)證協(xié)議：對通信主體A和B及建立的7.3密鑰認(rèn)證協(xié)議KK主密鑰KA主密鑰KB會(huì)話密鑰K147.3密鑰認(rèn)證協(xié)議KK主密鑰KA主密鑰KB會(huì)話密鑰K147.3密鑰認(rèn)證協(xié)議基于對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議

Needham-Schroeder協(xié)議密鑰分配中心KDC(keydistributioncenter)安全地分發(fā)一個(gè)會(huì)話密鑰Ks給用戶A和B。協(xié)議步驟157.3密鑰認(rèn)證協(xié)議基于對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議157.3密鑰認(rèn)證協(xié)議基于對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議

Needham-Schroeder協(xié)議重放攻擊假定攻擊方C已經(jīng)掌握A和B之間一個(gè)舊的會(huì)話密鑰，且可以中途阻止第(4)步的執(zhí)行

167.3密鑰認(rèn)證協(xié)議基于對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議167.3密鑰認(rèn)證協(xié)議基于對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議

Denning改進(jìn)協(xié)議：運(yùn)用時(shí)間戳T協(xié)議步驟177.3密鑰認(rèn)證協(xié)議基于對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議177.3密鑰認(rèn)證協(xié)議基于對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議

Denning改進(jìn)協(xié)議：運(yùn)用時(shí)間戳T協(xié)議步驟抑制重放攻擊

如果發(fā)送者的時(shí)鐘比接收者的時(shí)鐘要快，攻擊者就可以從發(fā)送者竊聽消息，并在以后當(dāng)時(shí)間戳對接收者來說成為當(dāng)前時(shí)重放給接收者?？朔种浦胤殴舻姆椒◤?qiáng)制各方定期檢查自己的時(shí)鐘是否與KDC的時(shí)鐘同步。采用臨時(shí)隨機(jī)數(shù)(nonce)技術(shù)187.3密鑰認(rèn)證協(xié)議基于對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議抑制重7.3密鑰認(rèn)證協(xié)議基于對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議

KEHN改進(jìn)協(xié)議協(xié)議步驟該協(xié)議可抵抗前兩個(gè)協(xié)議可能遭受的攻擊197.3密鑰認(rèn)證協(xié)議基于對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議該協(xié)議7.3密鑰認(rèn)證協(xié)議基于非對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議

Diffie-Hellman密鑰交換協(xié)議(DH-KEP)協(xié)議步驟公開參數(shù)：大素?cái)?shù)p,p的本原根a共享密鑰：K207.3密鑰認(rèn)證協(xié)議基于非對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議207.3密鑰認(rèn)證協(xié)議基于非對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議

Diffie-Hellman密鑰交換協(xié)議(DH-KEP)協(xié)議步驟公開參數(shù)：大素?cái)?shù)p,p的本原根a共享密鑰：K合理性證明安全性基礎(chǔ)

攻擊者只能得到a,p,YA

,YB，要想求出K,必須先求出XA或XB，這是離散對數(shù)問題217.3密鑰認(rèn)證協(xié)議基于非對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議安全7.3密鑰認(rèn)證協(xié)議基于非對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議

Diffie-Hellman密鑰交換協(xié)議(DH-KEP)例子：設(shè)p=97，a=5(1)A選擇XA=36，計(jì)算YA=aXA=536=50mod97，將YA發(fā)送給B.(2)B選擇XB=58，計(jì)算YB=aXB=558=44mod97，將YB發(fā)送給B.(3)A計(jì)算共享密鑰K=(YB)XA=4436=75mod97.(4)B計(jì)算共享密鑰K=(YA)XB=5058=75mod97.227.3密鑰認(rèn)證協(xié)議基于非對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議227.3密鑰認(rèn)證協(xié)議基于非對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議

Diffie-Hellman密鑰交換協(xié)議(DH-KEP)中間人攻擊YAYZYZYB237.3密鑰認(rèn)證協(xié)議基于非對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議YA7.3密鑰認(rèn)證協(xié)議基于非對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議

加密的密鑰交換協(xié)議(EKE)(協(xié)議7.11)Kerberos協(xié)議(協(xié)議7.12)主要目的是解決分布式網(wǎng)絡(luò)環(huán)境下，客戶訪問網(wǎng)絡(luò)資源的安全認(rèn)證問題。實(shí)現(xiàn)用戶與服務(wù)器之間的相互認(rèn)證；向每個(gè)實(shí)體證實(shí)另一個(gè)實(shí)體的身份；產(chǎn)生會(huì)話密鑰，供客戶和服務(wù)器(或兩個(gè)客戶之間)使用。V5于1994年作為RFC1510公布247.3密鑰認(rèn)證協(xié)議基于非對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議247.3密鑰認(rèn)證協(xié)議基于非對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議

Kerberos協(xié)議(協(xié)議7.12)四個(gè)主體：客戶C，應(yīng)用服務(wù)器V，認(rèn)證服務(wù)器AS，票證授予服務(wù)器TGS。認(rèn)證服務(wù)器與票證授予服務(wù)器又統(tǒng)稱為密鑰分配中心（KDC）。詳細(xì)步驟見教材257.3密鑰認(rèn)證協(xié)議基于非對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議257.3密鑰認(rèn)證協(xié)議對協(xié)議的攻擊類型重放攻擊(ReplayAttacks)重放攻擊是指入侵者捕獲以前協(xié)議運(yùn)行或當(dāng)前協(xié)議運(yùn)行中的消息用于對當(dāng)前協(xié)議運(yùn)行的攻擊已知密鑰攻擊（Known-keyattack)對手從用戶以前用過的密鑰確定新的密鑰的攻擊偽裝攻擊（Impersonationattack）

對手扮演合法實(shí)體進(jìn)行的攻擊字典攻擊(Dictionaryattack)主要針對口令的一種按某種順序進(jìn)行搜索的攻擊267.3密鑰認(rèn)證協(xié)議對協(xié)議的攻擊類型267.3密鑰認(rèn)證協(xié)議對協(xié)議的攻擊類型交錯(cuò)攻擊(Interleavingattack)

把前面一次或多次（或者并行）執(zhí)行協(xié)議的信息有選擇地組合在一起所實(shí)施的攻擊。選擇挑戰(zhàn)攻擊（Chosen-textattack）在挑戰(zhàn)應(yīng)答協(xié)議中對手巧妙地選擇挑戰(zhàn)消息，試圖得到所需的信息。反射攻擊（Reflectionattack）

正在執(zhí)行的協(xié)議中，一方把對方發(fā)送過來的消息再發(fā)回給對方277.3密鑰認(rèn)證協(xié)議對協(xié)議的攻擊類型27第7章密碼協(xié)議7.1密碼協(xié)議概述7.2實(shí)體認(rèn)證協(xié)議7.3密鑰認(rèn)證協(xié)議

7.4比特承諾協(xié)議

7.5零知識證明與身份識別協(xié)議28第7章密碼協(xié)議7.1密碼協(xié)議概述287.4比特承諾協(xié)議股票預(yù)測大師問題股票預(yù)測大師經(jīng)常在講座中給股民推薦股票，可股民按照大師推薦買股票卻常常賺不了錢，然而預(yù)測大師卻生意紅火。為什么？因?yàn)轭A(yù)測大師沒有對股民給出一個(gè)明確的承諾，尤其在股民選擇股票買進(jìn)時(shí)間和賣出時(shí)間上。往往在股民虧本后與預(yù)測大師論理時(shí)，預(yù)測大師總可以用偷換預(yù)測的前提和條件（時(shí)間）來“說服”股民相信大師預(yù)測的正確性297.4比特承諾協(xié)議股票預(yù)測大師問題297.4比特承諾協(xié)議安全比特承諾協(xié)議的直觀描述

A把比特b放入一個(gè)箱子，用一把只有用A自己的鑰匙才能開啟的鎖鎖上這個(gè)箱子，然后把這個(gè)箱子交給B；當(dāng)時(shí)機(jī)成熟時(shí)，A把比特b和打開箱子的鑰匙交給B，B通過打開箱子可以驗(yàn)證比特b的內(nèi)容沒有改動(dòng)，因?yàn)橄渥釉贐的控制之下。307.4比特承諾協(xié)議安全比特承諾協(xié)議的直觀描述307.4比特承諾協(xié)議7.1(比特承諾)給定隨機(jī)數(shù)r和待提交的整數(shù)b，關(guān)于整數(shù)b的比特承諾就是一個(gè)有效算法F使得滿足如下條件：從F(r,b)計(jì)算出b的難度相當(dāng)于攻破某計(jì)算困難性問題的難度；比特承諾F(r,b)的提交者A在以后把比特承諾F(r,b)以不同的方式打開成為F(r,b)的概率是可以忽略的，即提交者不能把比特承諾打開成為不同的方式；在多項(xiàng)式時(shí)間內(nèi)，無法區(qū)分對于兩個(gè)不同數(shù)b和b的F(r,b)和F(r,b)。317.4比特承諾協(xié)議7.1(比特承諾)給定隨機(jī)數(shù)r和7.4比特承諾協(xié)議比特承諾的兩個(gè)安全性要求：屏蔽性（Concealing）：A可用一個(gè)概率多項(xiàng)式時(shí)間算法F(r,b)將二進(jìn)位b屏蔽起來，只有A本人才能打開。即二進(jìn)位b一旦被屏蔽起來便不能被對方B預(yù)測。約束性(Binding)：A根據(jù)二進(jìn)位b及其屏蔽算法，可從屏蔽體中用概率多項(xiàng)式時(shí)間算法打開屏蔽，顯露出惟一的二進(jìn)位b,并讓B進(jìn)行驗(yàn)證。即二進(jìn)位b一旦被屏蔽起來便不能再被屏蔽者修改。327.4比特承諾協(xié)議比特承諾的兩個(gè)安全性要求：327.4比特承諾協(xié)議例：由Goldwasser-Micali公鑰概率加密系統(tǒng)構(gòu)造一種比特承諾協(xié)議令n=pq,p，q是長度相同的大素?cái)?shù)，選擇模n非二次剩余m。（1）A隨機(jī)選擇rZn*,b{0,1},計(jì)算y=F(r,b)=mbr2modn.

并發(fā)送給B。（2）其后A通過揭示b,r來打開y。B只需驗(yàn)證y=mbr2modn.

只要求解模n二次剩余問題是困難的，則從y=F(r,b)計(jì)算出b也是困難的。即由y不能泄露b的任何信息，所以該方案具有屏蔽性。該方案具有約束性。337.4比特承諾協(xié)議例：由Goldwasser-Mical7.4比特承諾協(xié)議拋幣落井協(xié)議（Flippingcoinsintowell）設(shè)想有一口清澈見底的深水井，A站在水井的旁邊，而B遠(yuǎn)離這口水井，A將硬幣拋進(jìn)水井里去，硬幣停留在水井中，現(xiàn)在A能夠看到水井里的結(jié)果，但A不能到水井里去改變硬幣的狀態(tài)（如正反面情況）。當(dāng)A將硬幣拋進(jìn)水井時(shí)，B不能看見水井里的硬幣，只有當(dāng)B猜完硬幣的狀態(tài)后，A才讓B走近井邊，看到井底的硬幣。這個(gè)協(xié)議滿足上面的兩條性質(zhì)。因此稱這樣的比特承諾協(xié)議為拋幣落井協(xié)議（Flippingcoinsintowell）。347.4比特承諾協(xié)議拋幣落井協(xié)議（Flippingcoi7.4比特承諾協(xié)議采用單向函數(shù)的拋幣協(xié)議

設(shè)A和B使用一個(gè)安全Hash函數(shù)F。(1)A選擇一個(gè)隨機(jī)數(shù)r，并計(jì)算y=F(r)；(2)A將y發(fā)送給B；(3)B猜測r是偶數(shù)（b=0）或奇數(shù)(b=1)，并將猜測結(jié)果發(fā)送給A；(4)如果B的猜測正確，拋幣結(jié)果為正面；如果B的猜測錯(cuò)誤，則拋幣的結(jié)果為反面。A公布此次拋幣的結(jié)果，并將r發(fā)送給B；(5)B確信。357.4比特承諾協(xié)議采用單向函數(shù)的拋幣協(xié)議357.4比特承諾協(xié)議采用單向函數(shù)的拋幣協(xié)議拋幣協(xié)議的安全性取決于F的安全性拋幣協(xié)議，具有如下的性質(zhì)：A必須在B猜測之前拋幣；在聽到B猜測之后A不能再拋幣；B猜測之前不能知道硬幣是怎么落地的。367.4比特承諾協(xié)議采用單向函數(shù)的拋幣協(xié)議36第7章密碼協(xié)議7.1密碼協(xié)議概述7.2實(shí)體認(rèn)證協(xié)議7.3密鑰認(rèn)證協(xié)議7.4比特承諾協(xié)議

7.5零知識證明與身份識別協(xié)議37第7章密碼協(xié)議7.1密碼協(xié)議概述377.5零知識證明與身份識別協(xié)議7.5.1零知識證明例子P要向V證明“P擁有某個(gè)房間的鑰匙”，有兩個(gè)方法：(1)P把鑰匙出示給V，V用這把鑰匙打開該房間的鎖(2)V確定該房間內(nèi)有某一物體，P用自己擁有的鑰匙打開該房間的門，然后把物體拿出來出示給V方法(2)屬于零知識證明零知識證明的基本思想設(shè)P是示證者，V是驗(yàn)證者。P需要向V證明他知道某個(gè)秘密信息，但示證者P在向驗(yàn)證者V證明他知道某個(gè)秘密信息時(shí)不泄露秘密的任何信息。

387.5零知識證明與身份識別協(xié)議7.5.1零知識證明387.5零知識證明與身份識別協(xié)議Jean-Jacques等打開洞穴之門的故事C、D之間有一道秘密之門，要打開這道門，需要知道開門的咒語。對任何不知道咒語的人，兩邊的通道都是死胡同。今有一示證者P，知道開門的咒語，他不想讓其他任何人知道這個(gè)咒語，但是又想讓V相信他確實(shí)能通過這道門這個(gè)事實(shí)。即：示證者P向驗(yàn)證者V證明他知道開門的咒語，而在這個(gè)過程中P不向驗(yàn)證者V泄漏咒語的任何信息。397.5零知識證明與身份識別協(xié)議Jean-Jacques等7.5零知識證明與身份識別協(xié)議零知識證明概念假設(shè)P，V是兩個(gè)概率圖靈機(jī)，P有無限的計(jì)算能力，V的計(jì)算能力是多項(xiàng)式的，若一個(gè)交互式證明滿足以下三點(diǎn)，就稱此證明為一個(gè)零知識交互式證明。(1)完備性(Completeness)：如果P的聲明是真的，則V以絕對優(yōu)勢的概率接受P的結(jié)論；(2)有效性(Soundness)：如果P的聲明是假的，則V以絕對優(yōu)勢的概率拒絕P的結(jié)論；(3)零知識性(Zero-knowledge)：無論V采取任何手段，當(dāng)P的聲明是真的，P不違背協(xié)議時(shí)，V除了接受P的結(jié)論以外，得不到其他額外的信息。407.5零知識證明與身份識別協(xié)議零知識證明概念407.5零知識證明與身份識別協(xié)議基于離散對數(shù)的零知識證明協(xié)議P欲向V證明他知道滿足x=modp的x，即知道離散對數(shù)x=log，其中p是一個(gè)大素?cái)?shù)，x是與p互素的隨機(jī)數(shù)。,和p是公開的，x是保密的。P在不泄露x的信息的情況下向V證明他知道x的過程如下：(1)P選擇隨機(jī)數(shù)r(0<r<p1)，計(jì)算h=rmodp，將h發(fā)送給V；(2)V隨機(jī)選擇一整數(shù)或b=0或b=1，發(fā)送給P。(3)P計(jì)算s=(r+bx)mod(p1)，并發(fā)送給V；(4)V驗(yàn)證s=hbmodp；(5)重復(fù)步驟(1)~(4)t次。P欺騙成功的概率為2t。417.5零知識證明與身份識別協(xié)議基于離散對數(shù)的零知識證明協(xié)7.5零知識證明與身份識別協(xié)議7.5.2身份識別協(xié)議用零知識證明設(shè)計(jì)身份識別協(xié)議示證者P在證明自己身份時(shí)不泄露任何信息，驗(yàn)證者V得不到示證者的任何私有信息，但又能有效證明對方身份的協(xié)議。一個(gè)好的身份識別協(xié)議應(yīng)具有以下性質(zhì)。(1)完備性（Completeness）：在P與V都誠實(shí)的情況下，P一定可以讓V識別自己，接受P的身份；(2)有效性（Soundness）：如果P的身份是假的，則V以絕對優(yōu)勢的概率拒絕接受P的身份；(3)不可傳遞性（Non-transferability）：驗(yàn)證者V不能重新使用識別過程中使用過的消息，向第三者證明自己是P，即證據(jù)不可傳遞。427.5零知識證明與身份識別協(xié)議7.5.2身份識別協(xié)議47.5零知識證明與身份識別協(xié)議Fiat-Shamir識別方案(Fiat,Shamir,1986)1.參數(shù)選取選定一個(gè)隨機(jī)模n=pq,p,q是不同的大素?cái)?shù).產(chǎn)生隨機(jī)數(shù)s，且使s2=vmodn.n和v是公開的，p,q,s作為示證者P的秘密。2.一次證明過程(1)P取隨機(jī)數(shù)r(<n)，計(jì)算x=r2modn,將x發(fā)送給驗(yàn)證者V;(2)V將一隨機(jī)比特b發(fā)送給P；(3)若b=0,則P將r發(fā)送給V；若b=1，則P將y=rs發(fā)送給V；(4)若b=0,則V證實(shí)x=r2modn,從而證明P知道s;若b=1，則V證實(shí)xv=y2modn,從而證明P知道s。3．P和V重復(fù)執(zhí)行t次過程2，直到V相信P知道s為止。437.5零知識證明與身份識別協(xié)議Fiat-Shamir識別7.5零知識證明與身份識別協(xié)議Fiat-Shamir識別方案(Fiat,Shamir,1986)Fiat-Shamir協(xié)議性質(zhì)完備性：如果P和V遵守協(xié)議，且P知道s，則應(yīng)答rs應(yīng)是模m下xv的平方根，V接收P的證明，所以協(xié)議是完備的。有效性：P不知道s，他也可取r，發(fā)送給V，V發(fā)送b給P。P可將r送出，當(dāng)b=0時(shí)則V可通過檢驗(yàn)而受騙，當(dāng)b=1時(shí)，則V可發(fā)現(xiàn)P不知s，B受騙概率為1/2，但連續(xù)t次受騙的概率將僅為2t。V無法知道P的秘密447.5零知識證明與身份識別協(xié)議Fiat-Shamir識別7.5零知識證明與身份識別協(xié)議Feige-Fiat-Shamir身份識別協(xié)議(自學(xué)）Schnorr身份識別協(xié)議(自學(xué)）457.5零知識證明與身份識別協(xié)議Feige-Fiat-Sh第6章習(xí)題

PP.176-177,1-1146第6章習(xí)題PP.176-177,1-1146現(xiàn)代密碼學(xué)21世紀(jì)高等學(xué)校計(jì)算機(jī)規(guī)劃教材Modern

Cryptography彭代淵信息科學(xué)與技術(shù)學(xué)院dypeng@2009.9-2010.1作者：何大可彭代淵唐小虎何明星梅其祥出版社：人民郵電出版社47現(xiàn)代密碼學(xué)21世紀(jì)高等學(xué)校計(jì)算機(jī)規(guī)劃教材ModernCr現(xiàn)代密碼學(xué)

Modern

Cryptography彭代淵信息科學(xué)與技術(shù)學(xué)院dypeng@2009年12月第7章密碼協(xié)議48現(xiàn)代密碼學(xué)

ModernCryptography彭代淵第7章密碼協(xié)議7.1密碼協(xié)議概述7.2實(shí)體認(rèn)證協(xié)議

7.3密鑰認(rèn)證協(xié)議

7.4比特承諾協(xié)議

7.5零知識證明與身份識別協(xié)議49第7章密碼協(xié)議7.1密碼協(xié)議概述37.1密碼協(xié)議概述協(xié)議(Protocol)基本概念兩個(gè)或兩個(gè)以上的參與者為完成某項(xiàng)特定任務(wù)而采取的一系列步驟。三層含義協(xié)議是有序的過程，每一步必須依次執(zhí)行協(xié)議至少需要兩個(gè)參與者通過執(zhí)行協(xié)議必須能夠完成某項(xiàng)任務(wù)507.1密碼協(xié)議概述協(xié)議(Protocol)47.1密碼協(xié)議概述協(xié)議(Protocol)特點(diǎn)協(xié)議的參與方必須了解協(xié)議，明確協(xié)議執(zhí)行的所有步驟協(xié)議的參與方都承諾按協(xié)議步驟執(zhí)行協(xié)議協(xié)議必須清楚、完整，對每種可能的情況必須規(guī)定明確、具體的動(dòng)作基本要求有效性公平性完整性517.1密碼協(xié)議概述協(xié)議(Protocol)57.1密碼協(xié)議概述密碼協(xié)議（安全協(xié)議）具有安全功能的協(xié)議——安全協(xié)議安全協(xié)議的設(shè)計(jì)必須采用密碼技術(shù)——密碼協(xié)議具體意義：密碼協(xié)議是建立在密碼體制基礎(chǔ)上的一種交互通信的協(xié)議，它運(yùn)行在計(jì)算機(jī)通信網(wǎng)或分布式系統(tǒng)中，借助于密碼算法來達(dá)到安全功能密碼技術(shù)：隨機(jī)數(shù)生成、加密/解密算法、Hash運(yùn)算、數(shù)字簽名等

安全功能：密鑰建立、密鑰分配、消息鑒別、身份認(rèn)證應(yīng)用系統(tǒng)：電子選舉、電子拍賣、公平電子交易等。527.1密碼協(xié)議概述密碼協(xié)議（安全協(xié)議）密碼技術(shù)：隨機(jī)數(shù)生7.1密碼協(xié)議概述密碼協(xié)議分類—按協(xié)議執(zhí)行的輪數(shù)分2輪協(xié)議3輪協(xié)議，……，n輪協(xié)議密碼協(xié)議分類—按協(xié)議功能分身份認(rèn)證協(xié)議密鑰分配協(xié)議密鑰協(xié)商協(xié)議秘密共享協(xié)議不經(jīng)意傳輸協(xié)議，……537.1密碼協(xié)議概述密碼協(xié)議分類—按協(xié)議執(zhí)行的輪數(shù)分77.1密碼協(xié)議概述密碼協(xié)議分類—按協(xié)議應(yīng)用目標(biāo)分選舉協(xié)議拍賣協(xié)議支付協(xié)議，……密碼協(xié)議分類—按協(xié)議的交互性分交互協(xié)議非交互協(xié)議密碼協(xié)議分類—按協(xié)議第三方性質(zhì)分仲裁協(xié)議裁決協(xié)議自動(dòng)執(zhí)行協(xié)議547.1密碼協(xié)議概述密碼協(xié)議分類—按協(xié)議應(yīng)用目標(biāo)分8第7章密碼協(xié)議7.1密碼協(xié)議概述7.2實(shí)體認(rèn)證協(xié)議

7.3密鑰認(rèn)證協(xié)議

7.4比特承諾協(xié)議

7.5零知識證明與身份識別協(xié)議55第7章密碼協(xié)議7.1密碼協(xié)議概述97.2實(shí)體認(rèn)證協(xié)議認(rèn)證：一個(gè)實(shí)體向另一個(gè)實(shí)體證明某種聲稱的過程認(rèn)證協(xié)議：主要目標(biāo)是確認(rèn)某個(gè)主體的真實(shí)性，確保信息的安全性認(rèn)證協(xié)議分類消息認(rèn)證協(xié)議：驗(yàn)證消息與其主體的一致性實(shí)體認(rèn)證協(xié)議：驗(yàn)證消息發(fā)送者所聲稱的身份密鑰認(rèn)證協(xié)議（認(rèn)證的密鑰建立協(xié)議）：生成、獲得加（解）密密鑰567.2實(shí)體認(rèn)證協(xié)議認(rèn)證：一個(gè)實(shí)體向另一個(gè)實(shí)體證明某種聲稱7.2實(shí)體認(rèn)證協(xié)議身份認(rèn)證協(xié)議：驗(yàn)證用戶知道什么（如口令等）、驗(yàn)證用戶擁有什么（如IC卡等）或驗(yàn)證用戶具有什么特征（如指紋、掌紋、虹膜、DNA等）身口令認(rèn)證協(xié)議（PAP，PasswordAuthenticationProtocol）：通過驗(yàn)證用戶口令來進(jìn)行身份認(rèn)證單向口令身份認(rèn)證協(xié)議協(xié)議7.1簡單口令身份認(rèn)證協(xié)議協(xié)議7.2動(dòng)態(tài)口令身份認(rèn)證協(xié)議

協(xié)議7.3基于口令的智能卡認(rèn)證協(xié)議

雙向口令身份認(rèn)證協(xié)議協(xié)議7.4基于Hash函數(shù)的雙向口令身份認(rèn)證協(xié)議協(xié)議7.5基于對稱密碼的雙向認(rèn)證協(xié)議

協(xié)議7.6基于非對稱密碼的雙向認(rèn)證協(xié)議

577.2實(shí)體認(rèn)證協(xié)議身份認(rèn)證協(xié)議：驗(yàn)證用戶知道什么（如口令第7章密碼協(xié)議7.1密碼協(xié)議概述7.2實(shí)體認(rèn)證協(xié)議

7.3密鑰認(rèn)證協(xié)議

7.4比特承諾協(xié)議

7.5零知識證明與身份識別協(xié)議58第7章密碼協(xié)議7.1密碼協(xié)議概述127.3密鑰認(rèn)證協(xié)議密鑰認(rèn)證協(xié)議：對通信主體A和B及建立的密鑰K進(jìn)行認(rèn)證

只有A、B（或可信第三方TTP）能夠知道KA和B確認(rèn)對方知道KA和B確認(rèn)K是最新建立的597.3密鑰認(rèn)證協(xié)議密鑰認(rèn)證協(xié)議：對通信主體A和B及建立的7.3密鑰認(rèn)證協(xié)議KK主密鑰KA主密鑰KB會(huì)話密鑰K607.3密鑰認(rèn)證協(xié)議KK主密鑰KA主密鑰KB會(huì)話密鑰K147.3密鑰認(rèn)證協(xié)議基于對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議

Needham-Schroeder協(xié)議密鑰分配中心KDC(keydistributioncenter)安全地分發(fā)一個(gè)會(huì)話密鑰Ks給用戶A和B。協(xié)議步驟617.3密鑰認(rèn)證協(xié)議基于對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議157.3密鑰認(rèn)證協(xié)議基于對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議

Needham-Schroeder協(xié)議重放攻擊假定攻擊方C已經(jīng)掌握A和B之間一個(gè)舊的會(huì)話密鑰，且可以中途阻止第(4)步的執(zhí)行

627.3密鑰認(rèn)證協(xié)議基于對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議167.3密鑰認(rèn)證協(xié)議基于對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議

Denning改進(jìn)協(xié)議：運(yùn)用時(shí)間戳T協(xié)議步驟637.3密鑰認(rèn)證協(xié)議基于對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議177.3密鑰認(rèn)證協(xié)議基于對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議

Denning改進(jìn)協(xié)議：運(yùn)用時(shí)間戳T協(xié)議步驟抑制重放攻擊

如果發(fā)送者的時(shí)鐘比接收者的時(shí)鐘要快，攻擊者就可以從發(fā)送者竊聽消息，并在以后當(dāng)時(shí)間戳對接收者來說成為當(dāng)前時(shí)重放給接收者?？朔种浦胤殴舻姆椒◤?qiáng)制各方定期檢查自己的時(shí)鐘是否與KDC的時(shí)鐘同步。采用臨時(shí)隨機(jī)數(shù)(nonce)技術(shù)647.3密鑰認(rèn)證協(xié)議基于對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議抑制重7.3密鑰認(rèn)證協(xié)議基于對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議

KEHN改進(jìn)協(xié)議協(xié)議步驟該協(xié)議可抵抗前兩個(gè)協(xié)議可能遭受的攻擊657.3密鑰認(rèn)證協(xié)議基于對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議該協(xié)議7.3密鑰認(rèn)證協(xié)議基于非對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議

Diffie-Hellman密鑰交換協(xié)議(DH-KEP)協(xié)議步驟公開參數(shù)：大素?cái)?shù)p,p的本原根a共享密鑰：K667.3密鑰認(rèn)證協(xié)議基于非對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議207.3密鑰認(rèn)證協(xié)議基于非對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議

Diffie-Hellman密鑰交換協(xié)議(DH-KEP)協(xié)議步驟公開參數(shù)：大素?cái)?shù)p,p的本原根a共享密鑰：K合理性證明安全性基礎(chǔ)

攻擊者只能得到a,p,YA

,YB，要想求出K,必須先求出XA或XB，這是離散對數(shù)問題677.3密鑰認(rèn)證協(xié)議基于非對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議安全7.3密鑰認(rèn)證協(xié)議基于非對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議

Diffie-Hellman密鑰交換協(xié)議(DH-KEP)例子：設(shè)p=97，a=5(1)A選擇XA=36，計(jì)算YA=aXA=536=50mod97，將YA發(fā)送給B.(2)B選擇XB=58，計(jì)算YB=aXB=558=44mod97，將YB發(fā)送給B.(3)A計(jì)算共享密鑰K=(YB)XA=4436=75mod97.(4)B計(jì)算共享密鑰K=(YA)XB=5058=75mod97.687.3密鑰認(rèn)證協(xié)議基于非對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議227.3密鑰認(rèn)證協(xié)議基于非對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議

Diffie-Hellman密鑰交換協(xié)議(DH-KEP)中間人攻擊YAYZYZYB697.3密鑰認(rèn)證協(xié)議基于非對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議YA7.3密鑰認(rèn)證協(xié)議基于非對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議

加密的密鑰交換協(xié)議(EKE)(協(xié)議7.11)Kerberos協(xié)議(協(xié)議7.12)主要目的是解決分布式網(wǎng)絡(luò)環(huán)境下，客戶訪問網(wǎng)絡(luò)資源的安全認(rèn)證問題。實(shí)現(xiàn)用戶與服務(wù)器之間的相互認(rèn)證；向每個(gè)實(shí)體證實(shí)另一個(gè)實(shí)體的身份；產(chǎn)生會(huì)話密鑰，供客戶和服務(wù)器(或兩個(gè)客戶之間)使用。V5于1994年作為RFC1510公布707.3密鑰認(rèn)證協(xié)議基于非對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議247.3密鑰認(rèn)證協(xié)議基于非對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議

Kerberos協(xié)議(協(xié)議7.12)四個(gè)主體：客戶C，應(yīng)用服務(wù)器V，認(rèn)證服務(wù)器AS，票證授予服務(wù)器TGS。認(rèn)證服務(wù)器與票證授予服務(wù)器又統(tǒng)稱為密鑰分配中心（KDC）。詳細(xì)步驟見教材717.3密鑰認(rèn)證協(xié)議基于非對稱密碼技術(shù)的密鑰認(rèn)證協(xié)議257.3密鑰認(rèn)證協(xié)議對協(xié)議的攻擊類型重放攻擊(ReplayAttacks)重放攻擊是指入侵者捕獲以前協(xié)議運(yùn)行或當(dāng)前協(xié)議運(yùn)行中的消息用于對當(dāng)前協(xié)議運(yùn)行的攻擊已知密鑰攻擊（Known-keyattack)對手從用戶以前用過的密鑰確定新的密鑰的攻擊偽裝攻擊（Impersonationattack）

對手扮演合法實(shí)體進(jìn)行的攻擊字典攻擊(Dictionaryattack)主要針對口令的一種按某種順序進(jìn)行搜索的攻擊727.3密鑰認(rèn)證協(xié)議對協(xié)議的攻擊類型267.3密鑰認(rèn)證協(xié)議對協(xié)議的攻擊類型交錯(cuò)攻擊(Interleavingattack)

把前面一次或多次（或者并行）執(zhí)行協(xié)議的信息有選擇地組合在一起所實(shí)施的攻擊。選擇挑戰(zhàn)攻擊（Chosen-textattack）在挑戰(zhàn)應(yīng)答協(xié)議中對手巧妙地選擇挑戰(zhàn)消息，試圖得到所需的信息。反射攻擊（Reflectionattack）

正在執(zhí)行的協(xié)議中，一方把對方發(fā)送過來的消息再發(fā)回給對方737.3密鑰認(rèn)證協(xié)議對協(xié)議的攻擊類型27第7章密碼協(xié)議7.1密碼協(xié)議概述7.2實(shí)體認(rèn)證協(xié)議7.3密鑰認(rèn)證協(xié)議

7.4比特承諾協(xié)議

7.5零知識證明與身份識別協(xié)議74第7章密碼協(xié)議7.1密碼協(xié)議概述287.4比特承諾協(xié)議股票預(yù)測大師問題股票預(yù)測大師經(jīng)常在講座中給股民推薦股票，可股民按照大師推薦買股票卻常常賺不了錢，然而預(yù)測大師卻生意紅火。為什么？因?yàn)轭A(yù)測大師沒有對股民給出一個(gè)明確的承諾，尤其在股民選擇股票買進(jìn)時(shí)間和賣出時(shí)間上。往往在股民虧本后與預(yù)測大師論理時(shí)，預(yù)測大師總可以用偷換預(yù)測的前提和條件（時(shí)間）來“說服”股民相信大師預(yù)測的正確性757.4比特承諾協(xié)議股票預(yù)測大師問題297.4比特承諾協(xié)議安全比特承諾協(xié)議的直觀描述

A把比特b放入一個(gè)箱子，用一把只有用A自己的鑰匙才能開啟的鎖鎖上這個(gè)箱子，然后把這個(gè)箱子交給B；當(dāng)時(shí)機(jī)成熟時(shí)，A把比特b和打開箱子的鑰匙交給B，B通過打開箱子可以驗(yàn)證比特b的內(nèi)容沒有改動(dòng)，因?yàn)橄渥釉贐的控制之下。767.4比特承諾協(xié)議安全比特承諾協(xié)議的直觀描述307.4比特承諾協(xié)議7.1(比特承諾)給定隨機(jī)數(shù)r和待提交的整數(shù)b，關(guān)于整數(shù)b的比特承諾就是一個(gè)有效算法F使得滿足如下條件：從F(r,b)計(jì)算出b的難度相當(dāng)于攻破某計(jì)算困難性問題的難度；比特承諾F(r,b)的提交者A在以后把比特承諾F(r,b)以不同的方式打開成為F(r,b)的概率是可以忽略的，即提交者不能把比特承諾打開成為不同的方式；在多項(xiàng)式時(shí)間內(nèi)，無法區(qū)分對于兩個(gè)不同數(shù)b和b的F(r,b)和F(r,b)。777.4比特承諾協(xié)議7.1(比特承諾)給定隨機(jī)數(shù)r和7.4比特承諾協(xié)議比特承諾的兩個(gè)安全性要求：屏蔽性（Concealing）：A可用一個(gè)概率多項(xiàng)式時(shí)間算法F(r,b)將二進(jìn)位b屏蔽起來，只有A本人才能打開。即二進(jìn)位b一旦被屏蔽起來便不能被對方B預(yù)測。約束性(Binding)：A根據(jù)二進(jìn)位b及其屏蔽算法，可從屏蔽體中用概率多項(xiàng)式時(shí)間算法打開屏蔽，顯露出惟一的二進(jìn)位b,并讓B進(jìn)行驗(yàn)證。即二進(jìn)位b一旦被屏蔽起來便不能再被屏蔽者修改。787.4比特承諾協(xié)議比特承諾的兩個(gè)安全性要求：327.4比特承諾協(xié)議例：由Goldwasser-Micali公鑰概率加密系統(tǒng)構(gòu)造一種比特承諾協(xié)議令n=pq,p，q是長度相同的大素?cái)?shù)，選擇模n非二次剩余m。（1）A隨機(jī)選擇rZn*,b{0,1},計(jì)算y=F(r,b)=mbr2modn.

并發(fā)送給B。（2）其后A通過揭示b,r來打開y。B只需驗(yàn)證y=mbr2modn.

只要求解模n二次剩余問題是困難的，則從y=F(r,b)計(jì)算出b也是困難的。即由y不能泄露b的任何信息，所以該方案具有屏蔽性。該方案具有約束性。797.4比特承諾協(xié)議例：由Goldwasser-Mical7.4比特承諾協(xié)議拋幣落井協(xié)議（Flippingcoinsintowell）設(shè)想有一口清澈見底的深水井，A站在水井的旁邊，而B遠(yuǎn)離這口水井，A將硬幣拋進(jìn)水井里去，硬幣停留在水井中，現(xiàn)在A能夠看到水井里的結(jié)果，但A不能到水井里去改變硬幣的狀態(tài)（如正反面情況）。當(dāng)A將硬幣拋進(jìn)水井時(shí)，B不能看見水井里的硬幣，只有當(dāng)B猜完硬幣的狀態(tài)后，A才讓B走近井邊，看到井底的硬幣。這個(gè)協(xié)議滿足上面的兩條性質(zhì)。因此稱這樣的比特承諾協(xié)議為拋幣落井協(xié)議（Flippingcoinsintowell）。807.4比特承諾協(xié)議拋幣落井協(xié)議（Flippingcoi7.4比特承諾協(xié)議采用單向函數(shù)的拋幣協(xié)議

設(shè)A和B使用一個(gè)安全Hash函數(shù)F。(1)A選擇一個(gè)隨機(jī)數(shù)r，并計(jì)算y=F(r)；(2)A將y發(fā)送給B；(3)B猜測r是偶數(shù)（b=0）或奇數(shù)(b=1)，并將猜測結(jié)果發(fā)送給A；(4)如果B的猜測正確，拋幣結(jié)果為正面；如果B的猜測錯(cuò)誤，則拋幣的結(jié)果為反面。A公布此次拋幣的結(jié)果，并將r發(fā)送給B；(5)B確信。817.4比特承諾協(xié)議采用單向函數(shù)的拋幣協(xié)議357.4比特承諾協(xié)議采用單向函數(shù)的拋幣協(xié)議拋幣協(xié)議的安全性取決于F的安全性拋幣協(xié)議，具有如下的性質(zhì)：A必須在B猜測之前拋幣；在聽到B猜測之后A不能再拋幣；B猜測之前不能知道硬幣是怎么落地的。827.4比特承諾協(xié)議采用單向函數(shù)的拋幣協(xié)議36第7章密碼協(xié)議7.1密碼協(xié)議概述7.2實(shí)體認(rèn)證協(xié)議7.3密鑰認(rèn)證協(xié)議7.4比特承諾協(xié)議

7.5零知識證明與身份識別協(xié)議83第7章密碼協(xié)議7.1密碼協(xié)議概述377.5零知識證明與身份識別協(xié)議7.5.1零知識證明例子P要向V證明“P擁有某個(gè)房間的鑰匙”，有兩個(gè)方法：(1)P把鑰匙出示給V，V用這把鑰匙打開該房間的鎖(2)V確定該房間內(nèi)有某一物體，P用自己擁有的鑰匙打開該房間的門，然后把物體拿出來出示給V方法(2)屬于零知識證明零知識證明的基本思想設(shè)P是示證者，V是驗(yàn)證者。P需要向V證明他知道某個(gè)秘密信息，但示證者P在向驗(yàn)證者V證明他知道某個(gè)秘密信息時(shí)不泄露秘密的任何信息。

847.5零知識證明與身份識別協(xié)議7.5.1零知識證明387.5零知識證明與身份識別協(xié)議Jean-Jacques等打開洞穴之門的故事C、D之間有一道秘密之門，要打開這道門，需要知道開門的咒語。對任何不知道咒語的人，兩邊的通道都是死胡同。今有一示證者P，知道開門的咒語，他不想讓其他任何人知道這個(gè)咒語，但是又想讓V相信他確實(shí)能通過這道門這個(gè)事實(shí)。即：示證者P向驗(yàn)證者V證明他知道開門的咒語，而在這個(gè)過程中P不向驗(yàn)證者V泄漏咒語的任何信息。857.5零知識證明與身份識別協(xié)議Jean-Jacques等7.5零知識證明與身份識別協(xié)議零知識證明概念假設(shè)P，V是兩個(gè)概率圖靈機(jī)，P有無限的計(jì)算能力，V的計(jì)算能力是多項(xiàng)式的，若一個(gè)交互式證明滿足以下三點(diǎn)，就稱此證明為一個(gè)零知識交互式證明。(1)完備性