1、本科生必修課現(xiàn)代密碼學(xué)第七章 密碼協(xié)議主講教師：董慶寬 副教授研究方向：密碼學(xué)與信息安全電子郵件：qkdong個人主頁：/qkdong/ 內(nèi)容提要7.1 密碼協(xié)議概述7.2 認(rèn)證協(xié)議基本概念7.3 密鑰建立認(rèn)證協(xié)議7.4 口令認(rèn)證協(xié)議7.5 零知識證明與身份識別協(xié)議7.6 其它密碼協(xié)議簡介7.7 量子密鑰分發(fā)協(xié)議7.8 安全協(xié)議標(biāo)準(zhǔn)2/第七章 密碼協(xié)議7.1 密碼協(xié)議概述協(xié)議是一種有序的過程，每一步必須依次執(zhí)行；需要至少兩個或兩個以上的參與者，且最終要完成某種任務(wù)，即實(shí)現(xiàn)某種功能協(xié)議對參與者一定是完全公開的，且按照規(guī)范動作協(xié)議的基本要求是有效性、公平性和完整性密碼協(xié)議也叫安全協(xié)議，是建立在密碼

2、體制的基礎(chǔ)上的一種交互式通信協(xié)議，借助于密碼算法來達(dá)到安全功能密碼協(xié)議所能實(shí)現(xiàn)的安全功能是多種多樣的身份認(rèn)證、密鑰協(xié)商、消息鑒別、公平拋幣多方計(jì)算、秘密共享、不經(jīng)意傳輸零知識證明密碼協(xié)議的應(yīng)用：安全通信(通信的保密認(rèn)證等)、電子選舉、電子拍賣、公平電子交易3/第七章 密碼協(xié)議：7.1 密碼協(xié)議概述7.2.1 認(rèn)證協(xié)議概述認(rèn)證：一個實(shí)體向另一個實(shí)體證明某種聲稱的東西的過程認(rèn)證協(xié)議：主要目標(biāo)是確認(rèn)某個主體的真實(shí)性，確保信息的安全性安全可靠的通信除需進(jìn)行消息的認(rèn)證外，還需建立一些規(guī)范的協(xié)議對數(shù)據(jù)來源的可靠性、通信實(shí)體的真實(shí)性加以認(rèn)證，以防止欺騙、偽裝等攻擊認(rèn)證的分類身份認(rèn)證：也稱實(shí)體認(rèn)證。驗(yàn)證消息發(fā)

3、送者所聲稱的身份，發(fā)起通信或訪問的實(shí)體是否具有合法身份和相應(yīng)權(quán)限密鑰建立認(rèn)證：生成、獲得加解密密鑰數(shù)據(jù)源認(rèn)證：驗(yàn)證消息與其發(fā)送主體的一致性，數(shù)據(jù)從哪兒來消息完整性認(rèn)證：驗(yàn)證消息是否被篡改這些認(rèn)證常常一起進(jìn)行，也有時單獨(dú)進(jìn)行即通信之前首先進(jìn)行實(shí)體認(rèn)證(身份認(rèn)證)，身份認(rèn)證之后會協(xié)商出會話密鑰用于對每個傳輸數(shù)據(jù)的數(shù)據(jù)源認(rèn)證和完整性認(rèn)證4/第七章 密碼協(xié)議：7.2 認(rèn)證協(xié)議概述7.2.1 認(rèn)證協(xié)議概述身份認(rèn)證有兩個層次：身份證實(shí)和身份識別，二者差別是是否出示身份身份證實(shí)：你是否是你宣稱的你，一般的身份認(rèn)證都是指這種情況驗(yàn)證方首先知道要驗(yàn)證的身份是誰，進(jìn)一步證實(shí)來訪或與之通信的人是否具有該身份一般用于

4、A和B確定通信時所用，通常的網(wǎng)絡(luò)認(rèn)證協(xié)議都是身份證實(shí)具體技術(shù)：輸入個人信息，經(jīng)公式或算法運(yùn)算所得結(jié)果與卡中或數(shù)據(jù)庫中存儲信息經(jīng)公式運(yùn)算所得結(jié)果比較身份識別：我是否知道你是誰驗(yàn)證方不知道來訪人是否為合法身份，沒有比較確定的目標(biāo)，只要滿足某個條件就可判定身份的特點(diǎn)。驗(yàn)證者一般為權(quán)威機(jī)構(gòu)一般在實(shí)體認(rèn)證中需要， 比如判斷來訪者是否是在逃犯，是否為密碼開啟者，是否為本公司員工。通常用指紋、虹膜技術(shù)具體技術(shù)：輸入個人信息，經(jīng)過處理提取模版信息，試著在存儲數(shù)據(jù)庫中找出一個與之匹配的模版而后得出結(jié)論5/第七章 密碼協(xié)議： 7.2 認(rèn)證協(xié)議概述7.2.1 認(rèn)證協(xié)議概述數(shù)據(jù)源認(rèn)證和消息完整性認(rèn)證的區(qū)別(1) 數(shù)據(jù)

5、源認(rèn)證必然涉及通信，是一種安全服務(wù)消息完整性認(rèn)證不一定包含通信，可用于存儲的數(shù)據(jù)(2)數(shù)據(jù)源認(rèn)證一定涉及消息源識別，而消息完整性不一定涉及該過程比如用戶A將一個由用戶C簽名的消息文件發(fā)給用戶B，那么用戶B能夠通過驗(yàn)證C的簽名判斷消息的完整性，但是消息的來源卻不是C而是A(3) 數(shù)據(jù)源認(rèn)證必然涉及確認(rèn)消息的新鮮性，而數(shù)據(jù)完整性卻無此必要一組老的數(shù)據(jù)，或者重放的數(shù)據(jù)可能有完善的數(shù)據(jù)完整性。而數(shù)據(jù)源認(rèn)證要求確認(rèn)收到的消息是新鮮的，即使當(dāng)前新發(fā)送的，而不是舊消息的重放6/第七章 密碼協(xié)議： 7.2 認(rèn)證協(xié)議概述7.2.1 認(rèn)證協(xié)議概述在認(rèn)證的幾個類別里，消息完整性認(rèn)證是最普通的層次，在前幾種認(rèn)證中一般

6、都包含了消息完整性認(rèn)證認(rèn)證需求也不同有的協(xié)議只需要認(rèn)證身份有的協(xié)議除了認(rèn)證身份還需要建立之后通信的密鑰以保護(hù)通信的安全，即身份認(rèn)證與密鑰協(xié)商(密鑰建立認(rèn)證協(xié)議)有的協(xié)議主要是考慮對消息源的認(rèn)證，這時一般首先要認(rèn)證身份并建立密鑰，然后再基于該會話密鑰對傳輸?shù)拿總€消息進(jìn)行認(rèn)證，以使收方確信收到的消息來自發(fā)方，而且不是重放、在順序、時間等方面都是正確的，即完整性對于身份認(rèn)證，主要驗(yàn)證用戶知道什么(如口令、密鑰、私鑰、秘密等)、驗(yàn)證用戶擁有什么(如IC卡等)、驗(yàn)證用戶具有什么特征(如指紋、掌紋、虹膜、DNA等)其中基于口令的身份認(rèn)證是比較重要的一類，具有廣泛的應(yīng)用，因?yàn)橛脩舨恍枰獢y帶或記憶復(fù)雜的密鑰或

7、者認(rèn)證信息7/第七章 密碼協(xié)議： 7.2 認(rèn)證協(xié)議概述7.2.2 Daolev-Yao威脅模型與常見攻擊協(xié)議的安全性及形式化分析方法協(xié)議的安全威脅模型：對敵手能力的建模Dolev-Yao安全威脅模型Canetti-Krawczyk(CK) 模型協(xié)議的安全模型：定義協(xié)議的各種安全目標(biāo)如機(jī)密性，完整性等等8/第七章 密碼協(xié)議：7.2 認(rèn)證協(xié)議概述7.2.2 Daolev-Yao威脅模型與常見攻擊協(xié)議的安全性分析方法邏輯分析法：基于信仰和知識對協(xié)議進(jìn)行安全性研究，使用最廣泛，如BAN邏輯等模型檢測法：一種驗(yàn)證有限狀態(tài)系統(tǒng)的自動化分析工具，采用非專門的說明語言和驗(yàn)證工具來對協(xié)議建立模型并加以驗(yàn)證，如C

8、SP等定理證明和專家系統(tǒng)方法：類似證明程序的正確性一樣，將協(xié)議的證明規(guī)約到證明一些循環(huán)不變式，基于計(jì)算復(fù)雜度理論通用形式化分析方法：試圖用一些通用的形式化方法來說明和分析安全協(xié)議。如最弱前置謂詞等方法，Petri網(wǎng)，代數(shù)方法等?？勺C明安全的協(xié)議設(shè)計(jì)基本思想類似于可證明安全的公鑰密碼算法9/第七章 密碼協(xié)議：7.2 認(rèn)證協(xié)議概述7.2.2 Daolev-Yao威脅模型與常見攻擊Dolev-Yao 模型1983 年，Dolev 和Yao 發(fā)表了安全協(xié)議史上的一篇重要論文，主要兩點(diǎn)貢獻(xiàn)其一是將安全協(xié)議本身與安全協(xié)議所具體采用的密碼系統(tǒng)分開在假定密碼系統(tǒng)是“完善”的基礎(chǔ)上討論安全協(xié)議本身的正確性、安全

9、性、冗余性等課題安全協(xié)議的設(shè)計(jì)被劃分為兩個不同的層次:首先研究安全協(xié)議本身的安全性質(zhì),然后討論實(shí)現(xiàn)層次的具體細(xì)節(jié),包括所采用的具體密碼算法等等.10/第七章 密碼協(xié)議：7.2 認(rèn)證協(xié)議概述7.2.2 Daolev-Yao威脅模型與常見攻擊第2點(diǎn)貢獻(xiàn)是，建立了攻擊者模型.他們認(rèn)為,攻擊者的知識和能力不能夠低估,攻擊者可以控制整個通信網(wǎng)絡(luò).Dolev 和Yao 認(rèn)為攻擊者具有如下能力:(1) 可以竊聽所有經(jīng)過網(wǎng)絡(luò)的消息;(2) 可以阻止和截獲所有經(jīng)過網(wǎng)絡(luò)的消息;(3) 可以存儲所獲得或自身創(chuàng)造的消息;(4) 可以根據(jù)存儲的消息偽造消息,并發(fā)送該消息;(5) 可以作為合法的主體參與協(xié)議的運(yùn)行.Dol

10、ev 和Yao 的工作具有深遠(yuǎn)的影響.迄今為止,大部分有關(guān)安全協(xié)議的研究工作都遵循Dolev 和Yao 的基本思想11/第七章 密碼協(xié)議：7.2 認(rèn)證協(xié)議概述7.2.2 Daolev-Yao威脅模型與常見攻擊Canetti-Krawczyk(CK)模型Canetti和Krawczyk于2002年提出了一種分析和設(shè)計(jì)密鑰交換協(xié)議的安全模型.通過模塊化的方法來進(jìn)行協(xié)議的安全設(shè)計(jì)與安全分析，并且采用不可區(qū)分性的方法來定義安全：在允許的攻擊能力下，如果攻擊者不能夠區(qū)分協(xié)議產(chǎn)生的密鑰和一個獨(dú)立的隨機(jī)數(shù)，那就可以說該密鑰交換協(xié)議是安全的.為了區(qū)分各種攻擊，確保信息在被暴露情況下盡可能的安全，該模型根據(jù)攻擊

11、者能夠得到信息的實(shí)際情況將攻擊分為以下三種類型：(1) 攻陷參與者(Party Corruption)：攻擊者能夠隨時攻陷任意一個參與者，并能得到該參與者內(nèi)部存儲的所有信息，包括長期的會話密鑰、秘密私鑰以及和會話相關(guān)的信息。(2) 會話密鑰查詢(Session-Key Query)：攻擊者提供某個參與者的身份和該參與者已經(jīng)完成會話的會話標(biāo)識，就能得到它所產(chǎn)生的會話密鑰。(3) 會話狀態(tài)暴露(Session-State Reveal)：攻擊者提供某個參與者的名字和其中一個尚未完成會話的會話標(biāo)識，就能得到該會話的相關(guān)信息12/第七章 密碼協(xié)議：7.2 認(rèn)證協(xié)議概述7.2.2 Daolev-Yao威

12、脅模型與常見攻擊在CK模型中，共定義了兩種攻擊模型認(rèn)證鏈路敵手模型(Authentication-linked adversary Model，AM)非認(rèn)證鏈路敵手模型(Unauthentication-Linked adversary，UM)。其中，UM中的攻擊者除了可以控制通信鏈路和控制協(xié)議事件的調(diào)度外，還能通過明確的攻擊手段來獲取協(xié)議參與者存儲器中的秘密信息；而AM中的攻擊者僅能傳遞由參與者產(chǎn)生的真實(shí)消息，不能改變或增添消息的內(nèi)容13/第七章 密碼協(xié)議：7.2 認(rèn)證協(xié)議概述7.2.2 Daolev-Yao威脅模型與常見攻擊常見的針對認(rèn)證和密鑰建立協(xié)議的攻擊重放攻擊 Replay atta

13、ck中間人攻擊 Man-in-the-middle已知密鑰攻擊：從以前用過的密鑰確定新密鑰假冒攻擊：Impersonation attack篡改或替換字典攻擊Dictionary attack：針對口令的一類攻擊并行會話攻擊反射攻擊拒絕服務(wù)攻擊 14/第七章 密碼協(xié)議：7.2 認(rèn)證協(xié)議概述概述7.2.3 基本認(rèn)證技術(shù)本節(jié)介紹在各種認(rèn)證協(xié)議實(shí)現(xiàn)中被認(rèn)為很好的結(jié)構(gòu)證明消息的新鮮性和主體活現(xiàn)性的標(biāo)準(zhǔn)機(jī)制雙向認(rèn)證和單向認(rèn)證包含可信第三方的認(rèn)證(一) 消息的新鮮性和主體的活現(xiàn)性消息的新鮮性即實(shí)時性是數(shù)據(jù)源認(rèn)證所不可或缺的一部分，而在這一過程中主體也要考慮通信對端的身份的真實(shí)性及是否在線，即主體活現(xiàn)性，因

14、此證明消息的新鮮性或主體的活現(xiàn)性就成為認(rèn)證協(xié)議的最基本組成部分消息新鮮性經(jīng)常伴隨著主體活現(xiàn)性的認(rèn)證，因此我們就以新鮮性的討論為主，重點(diǎn)考慮消息新鮮性的實(shí)現(xiàn)消息的新鮮性也稱為實(shí)時性15/第七章 密碼協(xié)議：7.2 認(rèn)證協(xié)議概述7.2.3 基本認(rèn)證技術(shù)實(shí)時性(新鮮性)：對防止消息的重放攻擊極為重要，一種方法是對交換的每一條消息都加上一個序列號，一個新消息僅當(dāng)它有正確的序列號時才被接收。這種方法的困難性是要求每個用戶分別記錄與其他每一用戶交換的消息的序列號，從而增加了用戶的負(fù)擔(dān)，所以序列號方法一般不用于認(rèn)證和密鑰交換。實(shí)現(xiàn)消息新鮮性有兩種技術(shù)：時間戳和詢問應(yīng)答機(jī)制時戳如果A收到的消息包括一時戳，且在A

15、看來這一時戳充分接近自己的當(dāng)前時刻， A才認(rèn)為收到的消息是新的并接受之。這種方案要求所有各方的時鐘是同步的詢問-應(yīng)答用戶A向B發(fā)出一個一次性隨機(jī)數(shù)作為詢問，如果收到B發(fā)來的消息（應(yīng)答）也包含一正確的一次性隨機(jī)數(shù)，A就認(rèn)為B發(fā)來的消息是新的并接受之。16/第七章 密碼協(xié)議：7.2 認(rèn)證協(xié)議概述7.2.3 基本認(rèn)證技術(shù)時戳法不能用于面向連接的應(yīng)用過程這是由于時戳法在實(shí)現(xiàn)時固有的困難性首先是需要在不同的處理器時鐘之間保持同步，那么所用的協(xié)議必須是容錯的以處理網(wǎng)絡(luò)錯誤，并且是安全的以對付惡意攻擊第二，如果協(xié)議中任一方的時鐘出現(xiàn)錯誤而暫時地失去了同步，則將使敵手攻擊成功的可能性增加最后還由于網(wǎng)絡(luò)本身存在

16、著延遲，因此不能期望協(xié)議的各方能保持精確的同步。所以任何基于時戳的處理過程、協(xié)議等都必須允許同步有一個誤差范圍?？紤]到網(wǎng)絡(luò)本身的延遲，誤差范圍應(yīng)足夠大；考慮到可能存在的攻擊，誤差范圍又應(yīng)足夠小17/第七章 密碼協(xié)議：7.2 認(rèn)證協(xié)議概述7.2.3 基本認(rèn)證技術(shù)詢問-應(yīng)答方式則不適合于無連接的應(yīng)用過程這是因?yàn)樵跓o連接傳輸以前需經(jīng)詢問-應(yīng)答這一額外的握手過程，這與無連接應(yīng)用過程的本質(zhì)特性不符。對無連接的應(yīng)用程序來說，利用某種安全的時間服務(wù)器保持各方時鐘同步是防止重放攻擊最好的方法關(guān)于有狀態(tài)和無狀態(tài)的協(xié)議如果協(xié)議的運(yùn)行需要一些歷史和當(dāng)前的狀態(tài)作為上下文來維護(hù)，則稱為有狀態(tài)的協(xié)議，這樣一次協(xié)議的運(yùn)行要

17、考慮歷史的狀態(tài)，會造成負(fù)擔(dān)或者失同步等問題如果每次協(xié)議運(yùn)行獨(dú)立于歷史狀態(tài)參數(shù)，則是無狀態(tài)的，實(shí)現(xiàn)和資源的占用更少。18/第七章 密碼協(xié)議：7.2 認(rèn)證協(xié)議概述7.2.3 基本認(rèn)證技術(shù)（二）雙向認(rèn)證與單向認(rèn)證A和B是網(wǎng)絡(luò)的兩個用戶，他們想通過網(wǎng)絡(luò)先建立安全的共享密鑰再進(jìn)行保密通信。A(B)如何確信自己正在和B(A)通信而不是和C通信呢？即雙方的身份認(rèn)證這種通信方式為雙向通信，此時的認(rèn)證稱為相互認(rèn)證雙向認(rèn)證也叫相互認(rèn)證、雙方認(rèn)證等類似地，對于單向通信來說，認(rèn)證稱為單向認(rèn)證19/第七章 密碼協(xié)議：7.2 認(rèn)證協(xié)議概述7.2.3 基本認(rèn)證技術(shù)(三)包含可信第三方的認(rèn)證A和B直接進(jìn)行認(rèn)證的前提是二者之間

18、有共享的密鑰，有時在實(shí)際應(yīng)用中，這種方式并不實(shí)用，因?yàn)橛脩舳鄷r兩兩用戶之間都要共享密鑰，因此一種更為常見的方式是基于可信第三方的認(rèn)證這時，雙方都與可信第三方共享初始密鑰，系統(tǒng)擴(kuò)展性好，便于密鑰管理，借助可信第三方提供的幫助來實(shí)現(xiàn)認(rèn)證和密鑰協(xié)商（參看第8節(jié)的密鑰管理基本方式）可信第三方可以在線也可以離線本課程中將介紹比較典型的身份認(rèn)證協(xié)議或標(biāo)準(zhǔn)20/第七章 密碼協(xié)議：7.2 認(rèn)證協(xié)議概述7.3 密鑰建立認(rèn)證協(xié)議A、B兩個用戶在建立共享密鑰時需要考慮的核心問題是保密性和實(shí)時性保密性：為防止會話密鑰的偽造或泄露，會話密鑰在通信雙方之間交換時應(yīng)為密文形式，所以通信雙方事先就應(yīng)有密鑰或公開鑰實(shí)時性即新鮮

19、性，可使用前述的基本認(rèn)證技術(shù)通信雙方建立共享密鑰時可采用單鑰加密體制和公鑰加密體制本節(jié)主要介紹以下幾種認(rèn)證協(xié)議1. Needham schreoder密鑰分配協(xié)議(基于對稱密鑰技術(shù))2. DH密鑰交換協(xié)議(基于非對稱密碼技術(shù))3. 基于公鑰加密的密鑰分配協(xié)議4. 單向認(rèn)證與密鑰分配協(xié)議21/第七章 密碼協(xié)議：7.3 密鑰建立認(rèn)證協(xié)議7.3.1 NS密鑰分配協(xié)議基于單鑰加密體制設(shè)計(jì)需要有一個稱為鑒別服務(wù)器的可信權(quán)威機(jī)構(gòu)（密鑰分發(fā)中心KDC），網(wǎng)絡(luò)中每一用戶都與KDC有一共享密鑰，稱為主密鑰KDC為通信雙方建立一個短期內(nèi)使用的密鑰，稱為會話密鑰，并用主密鑰加密會話密鑰后分配給兩個用戶這種分配密鑰的

20、方式在實(shí)際應(yīng)用中較為普遍采用，如Kerberos系統(tǒng)采用的就是這種方式Needham-Schroeder協(xié)議1978年，Needham和Schroeder設(shè)計(jì)的著名的采用KDC的密鑰分配過程若用戶A欲與用戶B通信，則用戶A向鑒別服務(wù)器申請會話密鑰。在會話密鑰的分配過程中，雙方身份得以鑒別22/第七章 密碼協(xié)議：7.3 密鑰建立認(rèn)證協(xié)議7.3.1 NS密鑰分配協(xié)議假定兩個用戶A、B分別與密鑰分配中心KDC 有一個共享的主密鑰KA和KB，A希望與B建立一個共享的一次性會話密鑰23/第七章 密碼協(xié)議：7.3 密鑰建立認(rèn)證協(xié)議 AKDC：IDAIDBN1 / A向KDC發(fā)出會話密鑰請求 KDCA：EK

21、AKSIDBN1EKBKSIDA AB： EKBKSIDA BA： EKSN2 AB： EKSf(N2)N1為一次性隨機(jī)數(shù)，可以是時戳、計(jì)數(shù)器或隨機(jī)數(shù)每次的N1都應(yīng)不同，且為防止假冒，應(yīng)使敵手對N1難以猜測。因此用隨機(jī)數(shù)作為這個識別符最為合適。防重放，防篡改7.3.1 NS密鑰分配協(xié)議協(xié)議的目的是由KDC為A、B安全地分配會話密鑰KSA在第步安全地獲得了KS第步的消息僅能被B解讀，因此B在第步安全地獲得了KS 第步中B向A示意自己已掌握KS，N2用于向A詢問自己在第步收到的KS是否為一新會話密鑰，第步A對B的詢問作出應(yīng)答，一方面表示自己已掌握KS，另一方面由f(N2)回答了KS的新鮮性。第、兩

22、步用于防止對第步的重放攻擊以上協(xié)議易遭受另一種重放攻擊假定敵手能獲取舊會話密鑰，則冒充A向B重放第步的消息后，就可欺騙B使用舊會話密鑰敵手進(jìn)一步截獲第步B發(fā)出的詢問后，可假冒A作出第步的應(yīng)答敵手就可冒充A使用經(jīng)認(rèn)證過的會話密鑰向B發(fā)送假消息24/第七章 密碼協(xié)議：7.3 密鑰建立認(rèn)證協(xié)議7.3.1 NS密鑰分配協(xié)議(2) Needham-Schroeder協(xié)議的改進(jìn)方案之一在第步和第步加上一時戳，改進(jìn)后的協(xié)議如下： AKDC：IDAIDB KDCA：EKAKSIDBTEKBKSIDAT AB：EKBKSIDAT BA：EKSN1 AB：EKSf(N1)其中T是時戳，用以向A、B雙方保證KS的新

23、鮮性。A和B可通過下式檢查T的實(shí)時性：|Clock-T|t1+t2Clock為用戶（A或B）本地的時鐘t1是用戶本地時鐘和KDC時鐘誤差的估計(jì)值t2是網(wǎng)絡(luò)的延遲時間25/第七章 密碼協(xié)議：7.3 密鑰建立認(rèn)證協(xié)議7.3.1 NS密鑰分配協(xié)議T是經(jīng)主密鑰加密的，所以敵手即使知道舊會話密鑰，并在協(xié)議的過去執(zhí)行期間截獲第步的結(jié)果，也無法成功地重放給B因B對收到的消息可通過時戳檢查其是否為新的以上改進(jìn)還存在以下問題：方案主要依賴網(wǎng)絡(luò)中各方時鐘的同步，這種同步可能會由于系統(tǒng)故障或計(jì)時誤差而被破壞等待重放攻擊：如果發(fā)送方的時鐘超前于接收方的時鐘，敵手就可截獲發(fā)送方發(fā)出的消息，等待消息中時戳接近于接收方的時

24、鐘時，再重發(fā)這個消息這種重放可造成重復(fù)接收等問題26/第七章 密碼協(xié)議：7.3 密鑰建立認(rèn)證協(xié)議7.3.1 NS密鑰分配協(xié)議抗等待重放攻擊方法一：要求網(wǎng)絡(luò)中各方以KDC的時鐘為基準(zhǔn)定期檢查并調(diào)整自己的時鐘方法二：使用一次性隨機(jī)數(shù)的握手協(xié)議這就是NS協(xié)議的另一種改進(jìn)方法(3) Needham-Schroeder協(xié)議的改進(jìn)方案之二 AB：IDANA BKDC：IDBNBEKBIDANATB KDCA：EKAIDBNAKSTBEKBIDAKSTBNB AB：EKBIDAKSTBEKSNBTB是B建議的證書(會話密鑰)截止時間，用于截止時間前再次發(fā)起會話時KS是否可用的判別時間27/第七章 密碼協(xié)議：

25、7.3 密鑰建立認(rèn)證協(xié)議7.3.1 NS密鑰分配協(xié)議協(xié)議的具體含義如下： 中A發(fā)出的新的一次性隨機(jī)數(shù)NA以后將與會話密鑰KS一起以加密形式返回給A，以保證A收到的會話密鑰的新鮮性。 B向KDC發(fā)出與A建立會話密鑰的請求，發(fā)出的一次性隨機(jī)數(shù)NB以后將與會話密鑰一起以加密形式返回給B以向B保證會話密鑰的新鮮性 KDC將B產(chǎn)生的NB連同由KDC與B共享的密鑰KB加密的IDAKSTB一起發(fā)給A，其中KS是KDC分配的會話密鑰EKBIDAKSTB由A當(dāng)作票據(jù)用于以后的認(rèn)證。 A將票據(jù)EKBIDAKSTB連同由會話密鑰加密的一次性隨機(jī)數(shù)NB發(fā)往B，B由票據(jù)得到會話密鑰KS，并由KS得NB。NB由會話密鑰加

26、密的目的是B認(rèn)證了自己收到的消息不是一個重放,而的確是來自于A。28/第七章 密碼協(xié)議：7.3 密鑰建立認(rèn)證協(xié)議7.3.1 NS密鑰分配協(xié)議如果A保留由協(xié)議得到的票據(jù)EKBIDAKSTB ，就可在有效時間范圍內(nèi)不再求助于認(rèn)證服務(wù)器而由以下方式實(shí)現(xiàn)雙方的新認(rèn)證： AB：EKBIDAKSTB，NA BA：NB ，EKSNA AB：EKSNBB在第步收到票據(jù)后，可通過TB檢驗(yàn)票據(jù)是否過時，而新產(chǎn)生的一次性隨機(jī)數(shù)NA ，NB則向雙方保證了沒有重放攻擊以上協(xié)議中時間期限TB是B根據(jù)自己的時鐘定的，因此不要求各方之間的同步29/第七章 密碼協(xié)議：7.3 密鑰建立認(rèn)證協(xié)議7.3.2 基于公鑰加密的會話密鑰分

27、配協(xié)議由于公鑰加密的速度過慢，因此進(jìn)行保密通信不太合適，但用于分配單鑰密碼體制的密鑰卻非常合適1. 簡單分配下圖表示簡單使用公鑰加密算法建立會話密鑰的過程，如果A希望與B通信，可通過以下幾步建立會話密鑰30/第七章 密碼協(xié)議：7.3 密鑰建立認(rèn)證協(xié)議7.3.2 基于公鑰加密的會話密鑰分配協(xié)議 A產(chǎn)生自己的一對密鑰PKA,SKA，并向B發(fā)送PKA|IDA，其中IDA表示A的身份 B產(chǎn)生會話密鑰KS，并用A的公開鑰PKA對KS加密后發(fā)往A A由DSKAEPKAKS恢復(fù)會話密鑰。因?yàn)橹挥蠥能解讀KS，所以僅A、B知道這一共享密鑰。 A銷毀PKA,SKA，B銷毀PKA。A、B現(xiàn)在可以用單鑰加密算法以K

28、S作為會話密鑰進(jìn)行保密通信，通信完成后，又都將KS銷毀這種分配法盡管簡單，但卻由于A、B雙方在通信前和完成通信后，都未存儲密鑰，因此，密鑰泄露的危險(xiǎn)性為最小，且可防止雙方的通信被敵手監(jiān)聽,每次公私鑰由發(fā)方臨時產(chǎn)生但由于公鑰缺少證書管理機(jī)構(gòu)認(rèn)證且非物理傳輸容易受到主動攻擊31/第七章 密碼協(xié)議：7.3 密鑰建立認(rèn)證協(xié)議7.3.2 基于公鑰加密的會話密鑰分配協(xié)議中間人攻擊如果敵手E已接入A、B雙方的通信信道，就可通過以下不被察覺的方式截獲雙方的通信： 與上面的步驟相同 E截獲A的發(fā)送后，建立自己的一對密鑰PKE,SKE，并將PKEIDA發(fā)送給B。 B產(chǎn)生會話密鑰KS后，將EPKEKS發(fā)送出去。 E

29、截獲B發(fā)送的消息后，由DPKEEPKE KS解讀KS。 E再將EPKAKS發(fā)往A?，F(xiàn)在A和B知道KS，但并未意識到KS已被E截獲。A、B在用KS通信時，E就可以實(shí)施監(jiān)聽32/第七章 密碼協(xié)議：7.3 密鑰建立認(rèn)證協(xié)議7.3.2 基于公鑰加密的會話密鑰分配協(xié)議2. 具有保密性和認(rèn)證性的密鑰分配既可防止被動攻擊，又可防止主動攻擊假定A、B雙方已完成公鑰交換，可按以下步驟建立共享會話密鑰： A用PKB的公開鑰加密A的身份IDA和一個一次性隨機(jī)數(shù)N1后發(fā)往B，其中N1用于惟一地標(biāo)識這一業(yè)務(wù)33/第七章 密碼協(xié)議：7.3 密鑰建立認(rèn)證協(xié)議7.3.2 基于公鑰加密的會話密鑰分配協(xié)議 B用PKA加密N1和B

30、新產(chǎn)生的一次性隨機(jī)數(shù)N2后發(fā)往A。B發(fā)來的消息中N1的存在可使A相信對方的確是B A選一會話密鑰KS，然后將M=EPKBESKAKS| N2發(fā)給B，其中用B的公開鑰加密是為保證只有B能解讀加密結(jié)果，用A的秘密鑰加密是保證該加密結(jié)果只有A能發(fā)送 B以DPKADSKBM恢復(fù)會話密鑰注意：這個方案是教材5.2.2節(jié)方案的修訂，原方案是有漏洞的，即第4條消息容易被重放，假設(shè)敵手知道上次通話時協(xié)商的會話密鑰Ks，以及A對Ks的簽名和加密，則通過簡單的重放即可實(shí)現(xiàn)對B的欺騙，解決的方法是將第3和第4條消息合并發(fā)送34/第七章 密碼協(xié)議：7.3 密鑰建立認(rèn)證協(xié)議7.3.2 基于公鑰加密的會話密鑰分配協(xié)議以上

31、是假設(shè)收發(fā)雙方已經(jīng)互相知道對方公鑰)，以下協(xié)議也用于此目的(但事先不知道彼此公鑰) AAS：IDAIDB ASA：ESKASIDAPKATESKASIDBPKBT AB： ESKASIDAPKATESKASIDBPKBT EPKBESKAKST其中SKAS、SKA 分別是AS和A的秘密鑰，PKA、PKB分別是A和B的公開鑰，E為公鑰加密算法，AS是認(rèn)證服務(wù)器，Ks是要協(xié)商的會話密鑰時戳T用以防止重放攻擊，所以需要各方時鐘同步35/第七章 密碼協(xié)議：7.3 密鑰建立認(rèn)證協(xié)議B的證書可省去A發(fā)送證書請求AS恢復(fù)雙方證書7.3.2 基于公鑰加密的會話密鑰分配協(xié)議下一協(xié)議使用一次性隨機(jī)數(shù)保護(hù)新鮮性，因

32、此不需要時鐘的同步： AKDC：IDAIDB KDCA：ESKAUIDBPKB AB：EPKBNAIDA BKDC：IDBIDAEPKAUNA KDCB：ESKAUIDAPKAEPKBESKAUNAKSIDB BA：EPKAESKAUNAKSIDBNB AB：EKSNB其中SKAU和PKAU分別是KDC的秘密鑰和公開鑰36/第七章 密碼協(xié)議：7.3 密鑰建立認(rèn)證協(xié)議協(xié)議可進(jìn)一步做如下改進(jìn)： 在第、兩步出現(xiàn)NA的地方加上IDA，以說明NA的確是由A產(chǎn)生的而不是其他人產(chǎn)生的，這時IDA，NA就可惟一地識別A發(fā)出的連接請求7.3.3 Diffie-Hellman 密鑰交換DH密鑰交換是W.Diffi

33、e和M.Hellman于1976年提出的第一個公鑰密碼算法，已在很多商業(yè)產(chǎn)品中得以應(yīng)用算法的唯一目的是使得兩個用戶能夠安全地交換密鑰，得到一個共享地會話密鑰，算法本身不能用于加、解密算法的安全性基于求離散對數(shù)的困難性過程如圖，其中p是大素?cái)?shù)，a是p的本原根，p和a作為公開的全程元素37/第七章 密碼協(xié)議：7.3 密鑰建立認(rèn)證協(xié)議7.3.3 Diffie-Hellman 密鑰交換38/第七章 密碼協(xié)議：7.3 密鑰建立認(rèn)證協(xié)議簡單的密鑰交換協(xié)議(未認(rèn)證的容易受到中間人攻擊)7.3.4 單向認(rèn)證39/第七章 密碼協(xié)議：7.3 密鑰建立認(rèn)證協(xié)議電子郵件等網(wǎng)絡(luò)應(yīng)用不要求收發(fā)雙方同時在線郵件消息的報(bào)頭必

34、須是明文形式以使SMTP或X.400等存儲-轉(zhuǎn)發(fā)協(xié)議能夠處理SMTP（simple mail transfer protocol-簡單郵件傳輸協(xié)議）通常都不希望郵件處理協(xié)議要求郵件的消息本身是明文形式，否則就要求用戶對郵件處理機(jī)制的信任所以用戶在進(jìn)行保密通信時，需對郵件消息進(jìn)行加密以使包括郵件處理系統(tǒng)在內(nèi)的任何第3者都不能讀取郵件的內(nèi)容。再者郵件接收者還希望對郵件的來源即發(fā)方的身份進(jìn)行認(rèn)證，以防他人的假冒。與雙向認(rèn)證一樣，在此仍分為單鑰加密和公鑰加密兩種情況來考慮7.3.4 單向認(rèn)證40/第七章 密碼協(xié)議：7.3 密鑰建立認(rèn)證協(xié)議1. 單鑰加密單向通信時無中心的密鑰分配情況不適用，因?yàn)樾枰帐?/p>

35、在圖5-1所示的情況中去掉第步和第步就可滿足單向通信的兩個要求。協(xié)議如下： AKDC：IDAIDBN1 KDCA：EKAKSIDBN1EKBKSIDA AB：EKBKSIDAEKSM本協(xié)議不要求B同時在線，但保證了只有B能解讀消息，同時還提供了對消息的發(fā)方A的認(rèn)證然而本協(xié)議不能防止重放攻擊，如第步，為此需在消息中加上時戳，但由于電子郵件處理中的延遲，時戳的作用極為有限7.3.4 單向認(rèn)證41/第七章 密碼協(xié)議：7.3 密鑰建立認(rèn)證協(xié)議2. 公鑰加密公鑰加密算法可對發(fā)送的消息提供保密性、認(rèn)證性或既提供保密性又提供認(rèn)證性，為此要求發(fā)送方知道接收方的公開鑰（保密性），或要求接收方知道發(fā)送方的公開鑰（

36、認(rèn)證性），或要求每一方都知道另一方的公開鑰如果主要關(guān)心保密性，則可使用以下方式： AB：EPKBKSEKSM其中A用B的公開鑰加密一次性會話密鑰，用一次性會話密鑰加密消息。只有B能夠使用相應(yīng)的秘密鑰得到一次性會話密鑰，再用一次性會話密鑰得到消息。這種方案比簡單地用B的公開鑰加密整個消息要有效得多7.3.4 單向認(rèn)證42/第七章 密碼協(xié)議：7.3 密鑰建立認(rèn)證協(xié)議如果主要關(guān)心認(rèn)證性，則可使用以下方式： AB：MESKAH(M)這種方式可實(shí)現(xiàn)對A的認(rèn)證，但不提供對M的保密性。如果既要提供保密性又要提供認(rèn)證性，可使用以下方式： AB：EPKBMESKAH(M)后兩種情況要求B知道A的公開鑰并確信公開

37、鑰的真實(shí)性。為此A還需同時向B發(fā)送自己的公鑰證書，表示為AB：MESKAH(M)ESKASTIDAPKA或 AB：EPKBMESKAH(M)ESKASTIDAPKA其中ESKASTIDAPKA是認(rèn)證服務(wù)器AS為A簽署的公鑰證書7.4.1 口令認(rèn)證協(xié)議43/第七章 密碼協(xié)議：7.4 口令認(rèn)證協(xié)議口令認(rèn)證一般用于系統(tǒng)登錄時的身份認(rèn)證，有時也基于口令認(rèn)證來協(xié)商密鑰系統(tǒng)登錄時的口令認(rèn)證協(xié)議可以用口令，也可以替換成指紋等生物特征最簡單的是明文發(fā)送口令或生物特征，系統(tǒng)存儲該特征的hash值，系統(tǒng)收到口令或特征后計(jì)算hash值進(jìn)行比對復(fù)雜的安全的方式是不明文發(fā)送口令，而是與系統(tǒng)基于該口令進(jìn)行交互，甚至協(xié)商出

38、密鑰一個經(jīng)典的方法是Needham口令認(rèn)證協(xié)議主機(jī)存儲用戶名IDu及其口令Pwd的hash值(或單向函數(shù)值)登陸時，首先用戶提交身份IDu，然后主機(jī)提示輸入口令，用戶根據(jù)提示輸入口令Pwd，主機(jī)驗(yàn)證其hash值是否等于事先存儲的hash值在Unix系統(tǒng)中的口令認(rèn)證協(xié)議即采用此種方法，單向函數(shù)使用的是DES算法，即用用戶的口令加密64bit的連0串，其中DES算法也做了適當(dāng)修改一次口令認(rèn)證協(xié)議S/KEY口令登陸時的明文發(fā)送無法防止在線口令攻擊，所以希望每次發(fā)送的口令最好不一樣，此即一次口令認(rèn)證。同時為了多次登陸，這些口令應(yīng)該能由一個口令導(dǎo)出，即它們是相關(guān)的Lamport的一次口令方案主機(jī)H存儲初

39、始口令為(IDu, hashn(Pwd)，n)，U記住Pwd，H中當(dāng)前口令記錄是(IDu, hashc(Pwd)，c)，其中c大于等于1且小于等于n登陸時首先提交身份Idu，H提示U輸入口令；U計(jì)算hashc-1(Pwd)發(fā)給H，h計(jì)算一次hash并檢查當(dāng)前口令是否滿足hashc)；H更新U的當(dāng)前口令記錄為(Idu, hashc-1(Pwd)，c-1)其中n和c用于同步，以免受到攻擊44/7.4.1 口令認(rèn)證協(xié)議第七章 密碼協(xié)議：7.4 口令認(rèn)證協(xié)議本節(jié)我介紹基于口令的遠(yuǎn)程認(rèn)證協(xié)議，收發(fā)雙方除了基于口令認(rèn)證身份外，還要協(xié)商會話密鑰。我們以Islam等提出的協(xié)議為例給出一個示例方案。口令是一種低

40、熵密鑰1. 符號假設(shè)IDA：用戶A的身份標(biāo)識；S：遠(yuǎn)程服務(wù)器的身份標(biāo)識；D：候選口令字典集；PWA：用戶UA的口令；UA：UA= PWA xP；dS：服務(wù)器S的高熵密鑰；SK:用戶和服務(wù)器協(xié)商出的會話密鑰；PS: PS= dSxP；G是素?cái)?shù)階q的加法交換群(主要是橢圓曲線群)；P：群G的生成元；h():hash函數(shù)；|：字符串的連接；2. 系統(tǒng)初始化協(xié)議所有用戶和服務(wù)器協(xié)商好橢圓曲線密碼系統(tǒng)參數(shù)，服務(wù)器選擇的系統(tǒng)私鑰和公鑰對為(dS, PS)。然后服務(wù)器選擇一哈希函數(shù)h()，如SHA-256，和密鑰導(dǎo)出函數(shù)kdf：Gp0,1n，公布參數(shù)Ep(a,b),P,PS,n,h(),kdf3. 注冊協(xié)議

41、1）UA S: 用戶選擇自己的身份標(biāo)識IDA和口令PWA,計(jì)算UA= PWA xP，通過安全信道發(fā)送IDA,UA給服務(wù)器S2) 服務(wù)器S收到上一步消息后把 保存在數(shù)據(jù)庫內(nèi)45/7.4.2 基于口令的認(rèn)證與密鑰協(xié)商第七章 密碼協(xié)議：7.4 口令認(rèn)證協(xié)議4. 用戶認(rèn)證和密鑰協(xié)商協(xié)議用戶希望登陸到遠(yuǎn)程服務(wù)器并和服務(wù)器協(xié)商會話密鑰的時候，首先輸入身份IDA和口令PWA ，并執(zhí)行如下協(xié)議1）UA S: 用戶選擇一隨機(jī)數(shù)r，并計(jì)算RA=rP，TA=r x PWA xP+rPS，HA=h(rxPWAxPS，TA，RA)，然后給服務(wù)器發(fā)去消息 2) SUA : 服務(wù)器接到1）步發(fā)來的消息后做如下運(yùn)算：(1)

42、驗(yàn)證IDA的合法性，如果不正確則停止協(xié)議，否則繼續(xù)以下協(xié)議(2) 計(jì)算K=dSxRA(3) 提取rxUA=TA-K=rxPWAxP，然后計(jì)算HA*=h(dSx(TA-K), TA，RA)(4) 驗(yàn)證HA*是否等于HA，如果不等終止協(xié)議，否則繼續(xù)執(zhí)行(5) 選擇一個隨機(jī)數(shù)s，并計(jì)算Ts=rxUA+sxPS和Hs=h(sxPS)(6) 服務(wù)器發(fā)送消息給用戶 46/7.4.2 基于口令的認(rèn)證與密鑰協(xié)商第七章 密碼協(xié)議：7.4 口令認(rèn)證協(xié)議47/7.4.2 基于口令的認(rèn)證與密鑰協(xié)商第七章 密碼協(xié)議：7.4 口令認(rèn)證協(xié)議3）UA S: (1) 用戶接到2)中服務(wù)器發(fā)來的消息后，執(zhí)行如下協(xié)議(2) 計(jì)算s

43、xPS=TS-rxUA, HS*=h(sxPS)(3) 檢查HS*是否等于HS，如果不等則停止協(xié)議，否則繼續(xù)(4) 計(jì)算HAS=(rxUA, sxPS)并發(fā)送消息IDA, HAS給服務(wù)器4） SUA : Access granted/denied服務(wù)器S計(jì)算 HSA=(rxUA, sxPS),并把HSA和HAS比較，如果不等則服務(wù)器發(fā)Access denied給用戶，否則發(fā)送Access granted給用戶表示認(rèn)證成功當(dāng)協(xié)議執(zhí)行完畢，用戶和服務(wù)器共享秘密會話密鑰SK=h(IDA, TA，TS，RA， HS ， HAS ，K)其中K=(rxPWA)xsxPS=(sxdS) xrxUA=rx s

44、xdSxPWAxP7.5 身份識別技術(shù)48/第七章 密碼協(xié)議：7.5 身份識別技術(shù)在很多情況下，用戶都需證明自己的身份如登錄計(jì)算機(jī)系統(tǒng)存取電子銀行中的賬目數(shù)據(jù)庫從自動出納機(jī)ATM(automatic teller machine)取款等傳統(tǒng)的方法使用通行字(口令)個人身份識別號PIN(personal identification number)來證明自己的身份這些方法的缺點(diǎn)是檢驗(yàn)用戶通行字或PIN的人或系統(tǒng)可使用用戶的通行字或PIN冒充用戶身份的零知識證明技術(shù)使用戶在不泄露自己的通行字或PIN的情況下向他人證實(shí)自己的身份7.5.1 交互證明系統(tǒng)49/第七章 密碼協(xié)議：7.5 身份識別技術(shù)交互

45、證明系統(tǒng)由兩方參與，分別稱為證明者(prover，簡記為P)和驗(yàn)證者(verifier，簡記為V)其中P知道某一秘密（如公鑰密碼體制的秘密鑰或一平方剩余x的平方根），P希望使V相信自己的確掌握這一秘密交互證明由若干輪組成在每一輪，P和V可能需根據(jù)從對方收到的消息和自己計(jì)算的某個結(jié)果向?qū)Ψ桨l(fā)送消息比較典型的方式是在每輪V都向P發(fā)出一詢問，P向V做出一應(yīng)答所有輪執(zhí)行完后，V根據(jù)P是否在每一輪對自己發(fā)出的詢問都能正確應(yīng)答，以決定是否接受P的證明7.5.1 交互證明系統(tǒng)50/第七章 密碼協(xié)議：7.5 身份識別技術(shù)交互證明和數(shù)學(xué)證明的區(qū)別是：數(shù)學(xué)證明的證明者可自己獨(dú)立地完成證明交互證明是由P產(chǎn)生證明、V

46、驗(yàn)證證明的有效性來實(shí)現(xiàn)，因此雙方之間通過某種信道的通信是必需的。交互證明系統(tǒng)須滿足以下要求： 完備性如果P知道某一秘密，V將接受P的證明 正確性如果P能以一定的概率使V相信P的證明，則P知道相應(yīng)的秘密7.5.2 零知識證明51/第七章 密碼協(xié)議：7.5 身份識別技術(shù)零知識證明起源于最小泄露證明在交互證明系統(tǒng)中，設(shè)P知道某一秘密，并向V證明自己掌握這一秘密，但又不向V泄露這一秘密，這就是最小泄露證明進(jìn)一步，如果V除了知道P能證明某一事實(shí)外，不能得到其他任何信息，則稱P實(shí)現(xiàn)了零知識證明，相應(yīng)的協(xié)議稱為零知識證明協(xié)議7.5.2 零知識證明52/第七章 密碼協(xié)議：7.5 身份識別技術(shù)如圖7-4表示一個

47、簡單的迷宮，C和D之間有一道門，需要知道秘密口令才能打開P向V證明自己能打開這道門，但又不愿向V泄漏秘密口令7.5.2 零知識證明53/第七章 密碼協(xié)議：7.5 身份識別技術(shù)V在協(xié)議開始時停留在位置A；P一直走到迷宮的深處，隨機(jī)選擇位置C或位置D；P消失在迷宮中后，V走到位置B，然后命令P從某個出口返回位置B；P服從V的命令，必要時利用秘密口令打開C與D之間的門；P和V重復(fù)以上過程n次7.5.2 零知識證明54/第七章 密碼協(xié)議：7.5 身份識別技術(shù)協(xié)議中，如果P不知道秘密口令，就只能從來路返回B，而不能走另外一條路。P每次猜對V要求走哪一條路的概率是1/2，因此每一輪中P能夠欺騙V的概率是1

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

49、 ，并將G交給V。 V隨機(jī)地要求P做下述兩件工作之一： 證明圖G和圖 G同構(gòu)；指出圖 G的一條哈密爾頓回路。 P根據(jù)要求做下述兩件工作之一： 證明圖G和圖 G同構(gòu)，但不指出圖G或圖G的哈密爾頓回路；指出圖 的哈密爾頓回路，但不證明圖G和圖 同構(gòu)。 P和V重復(fù)以上過程n次。7.5.2 零知識證明56/第七章 密碼協(xié)議：7.5 身份識別技術(shù)協(xié)議執(zhí)行完后，V無法獲得任何信息使自己可以構(gòu)造圖G的哈密爾頓回路，因此該協(xié)議是零知識證明協(xié)議。事實(shí)上，如果P向V證明圖G和圖G同構(gòu)，這個結(jié)論對V并沒有意義，因?yàn)闃?gòu)造圖G的哈密爾頓回路和構(gòu)造圖G的哈密爾頓回路同樣困難。如果P向V指出圖的一條哈密爾頓回路，這一事實(shí)也

50、無法向V提供任何幫助，因?yàn)榍髢蓚€圖之間的同構(gòu)并不比求一個圖的哈密爾頓回路容易。在協(xié)議的每一輪中，P都隨機(jī)地構(gòu)造一個與圖G同構(gòu)的新圖，因此不論協(xié)議執(zhí)行多少輪，V都得不到任何有關(guān)構(gòu)造圖G的哈密爾頓回路的信息。注：兩個圖G1和G2是同構(gòu)的是指從G1的頂點(diǎn)集合到G2的頂點(diǎn)集合之間存在一個一一映射，當(dāng)且僅當(dāng)若x、y是G1上的相鄰點(diǎn)，(x)和(y)是G2上的相鄰點(diǎn)。7.5.3 簡化的Fiat-Shamir身份識別方案57/第七章 密碼協(xié)議：7.5 身份識別技術(shù)1. 協(xié)議及原理設(shè)n=pq，其中p和q是兩個不同的大素?cái)?shù)x是模n的平方剩余y是x的平方根n和x是公開的，而p、q和y是保密的證明者P以y作為自己的秘

51、密已證明，求解方程y2x mod n與分解n是等價(jià)的。因此他人不知n的兩個素因子p、q而計(jì)算y是困難的P和V通過交互證明協(xié)議，P向V證明自己掌握秘密y，從而證明了自己的身份7.5.3 簡化的Fiat-Shamir身份識別方案58/第七章 密碼協(xié)議：7.5 身份識別技術(shù)協(xié)議如下： P隨機(jī)選r (0rn)，計(jì)算ar2 mod n，將a發(fā)送給V。 V隨機(jī)選e0,1，將e發(fā)送給P。 P計(jì)算brye mod n，即e=0時，b=r；e=1時，b=ry mod n。將b發(fā)送給V。 若b2axe mod n，V接受P的證明。在協(xié)議的前3步，P和V之間共交換了3個消息，這3個消息的作用分別是： 第1個消息是P

52、用來聲稱自己知道a的平方根；第2個消息e是V的詢問，如果e=0，P必須展示a的平方根，即r，如果e=1，P必須展示被加密的秘密，即ry mod n；第3個消息b是P對V詢問的應(yīng)答。7.5.3 簡化的Fiat-Shamir身份識別方案59/第七章 密碼協(xié)議：7.5 身份識別技術(shù)2. 協(xié)議的完備性、正確性和安全性(1) 完備性如果P和V遵守協(xié)議，且P知道y，則應(yīng)答brye mod n應(yīng)是模n下axe的平方根在協(xié)議的第步V接受P的證明，所以協(xié)議是完備的(2) 正確性假冒的證明者E可按以下方式以1/2的概率騙得V接受自己的證明： E隨機(jī)選r(0rn)和e0,1，計(jì)算ar2x-e mod n，將a發(fā)送給

53、V V隨機(jī)選e0,1，將e發(fā)送給E E將r發(fā)送給V根據(jù)協(xié)議的第步，V的驗(yàn)證方程是r2axe mod nr2x-exe mod n，當(dāng)e=e 時，驗(yàn)證方程成立，V接受E的證明，即E欺騙成功7.5.3 簡化的Fiat-Shamir身份識別方案60/第七章 密碼協(xié)議：7.5 身份識別技術(shù)e=e的概率是1/2，所以E欺騙成功的概率是1/2另一方面，1/2是E能成功欺騙的最好概率否則假設(shè)E以大于1/2的概率使V相信自己的證明那么E知道一個a，對這個a他可正確地應(yīng)答V的兩個詢問e=0和e=1，意味著E能計(jì)算b12a mod n和b22ax mod n，即b22/b12x mod n，因此E由b2/b1 m

54、od n即可求得x的平方根y，矛盾7.5.3 簡化的Fiat-Shamir身份識別方案61/第七章 密碼協(xié)議：7.5 身份識別技術(shù)(3) 安全性協(xié)議的安全性可分別從證明者P和驗(yàn)證者V的角度來考慮。V的安全性，要求驗(yàn)證方被騙概率可忽略根據(jù)上面的討論，假冒的證明者E欺騙V成功的概率是1/2，對V來說，這個概率太大了。為減小這個概率，可將協(xié)議重復(fù)執(zhí)行多次，設(shè)執(zhí)行t次，則欺騙者欺騙成功的概率將減小到2-t。7.5.3 簡化的Fiat-Shamir身份識別方案62/第七章 密碼協(xié)議：7.5 身份識別技術(shù)也可一次進(jìn)行多個詢問，這時證明方先發(fā)送多個r的平方給V，V返回多個詢問bit，P對每一個比特進(jìn)行回答，

55、這樣一輪協(xié)議就完成了如ai=ri2mod n， 詢問ei,i=1,t, 回答bi=riyei mod n，驗(yàn)證P的安全性，證明方消息無泄漏因?yàn)閂的詢問是在很小的集合0,1中選取的，V沒有機(jī)會產(chǎn)生其他信息，而P發(fā)送給V的信息僅為P知道x的平方根這一事實(shí)，因此V無法得知x的平方根。7.5.4 Fiat-Shamir身份識別方案 63/第七章 密碼協(xié)議：7.5 身份識別技術(shù)1. 協(xié)議及原理在簡化的Fiat-Shamir身份識別方案中，驗(yàn)證者V接受假冒的證明者證明的概率是1/2，為減小這個概率，將證明者的秘密改為由隨機(jī)選擇的t個平方根構(gòu)成的一個向量y=(y1,y2,yt)，模數(shù)n和向量x=(y12,y

56、22,yt2)是公開的，其中n仍是兩個不相同的大素?cái)?shù)的乘積。協(xié)議如下： P隨機(jī)選r(0r，|（水平和垂直偏振方向）和園偏振光子的兩個態(tài)| / ，|（左旋和右旋偏振方向）的互補(bǔ)性實(shí)現(xiàn)量子編碼，這種互補(bǔ)性滿足測不準(zhǔn)原理線偏振和圓偏振是共軛的，他們各自的兩個態(tài)是正交的，但兩種偏振光子的狀態(tài)互不正交注意光子在傳輸過程產(chǎn)生的振動的方向是任意的，水平和垂直是相對于某一個參照系而言的編碼方案如表71/7.7.2 BB84量子密鑰分配協(xié)議第七章 密碼協(xié)議：7.7 量子密鑰分發(fā)協(xié)議符號位或0或1測量時主要采用偏振濾光器，偏振濾光器只允許某一方向的偏振光通過，其他方向的偏振光則以一個概率轉(zhuǎn)移到偏振器的方向，如果角

57、度減小，其概率較大光子極化可在任意兩個正交的方向進(jìn)行測量，選擇測量基“基 極化態(tài)” 線偏振方向， 表示為“基 極化態(tài)” 圓偏振方向，表示為若光子脈沖在某一坐標(biāo)軸方向極化，可在該坐標(biāo)軸方向進(jìn)行測量；若在其他的軸向進(jìn)行測量，將得到隨機(jī)結(jié)果：這是實(shí)現(xiàn)密鑰分配的基礎(chǔ) 72/7.7.2 BB84量子密鑰分配協(xié)議第七章 密碼協(xié)議：7.7 量子密鑰分發(fā)協(xié)議BB84協(xié)議的實(shí)現(xiàn)過程1）Alice以線偏振和圓偏振光子的四個偏振方向?yàn)榛A(chǔ)產(chǎn)生一個隨機(jī)量子比特串S=s1, s2, , sn其中每一個si是四個偏振方向之一2）Alice通過量子 傳輸信道將量子比特串S發(fā)送給Bob，任何相鄰的量子比特間的時間間隔均為3）

58、Bob選定一個隨機(jī)測量基序列，MB=m1b, m2b, , mnb，測量他收到的光子，其中mib, ， 和分別表示針對線偏振光子和圓偏振光子的測量基4）Bob通過經(jīng)典信道通知Alice他所選定的測量基序列MB5）Alice通知Bob所采用的測量基中哪些是正確的，哪些是錯誤的6）Alice和Bob保存測量基相同的測量結(jié)果，放棄測量基不一致的測量結(jié)果。7）根據(jù)所選用的測量基序列的出錯率判定是否有攻擊存在。記0為出錯率閾值，若出錯率0,繼續(xù)執(zhí)行下面的步驟，否則中止協(xié)議73/7.7.2 BB84量子密鑰分配協(xié)議第七章 密碼協(xié)議：7.7 量子密鑰分發(fā)協(xié)議8）Alice和Bob按照下面的方式將量子態(tài)編碼成

59、二進(jìn)制比特：|為0，|為1，| / 為0，|為1由此獲得原密鑰9）采用數(shù)據(jù)協(xié)商的方式對原密鑰進(jìn)行糾錯處理。Alice和Bob公開地選取原密鑰中的一個隨機(jī)比特位置子集，并比較該子集中比特的校驗(yàn)位是否相同。若Alice和Bob所選子集的校驗(yàn)位相同，放棄子集中的一個比特。對k個獨(dú)立的子集重復(fù)校驗(yàn)位的比較操作，確保Alice和Bob共享密鑰相同的概率為1-2-k10）采用保密加強(qiáng)技術(shù)對經(jīng)過協(xié)商處理后的密鑰作進(jìn)一步的處理，以提高密鑰的保密性，并最終獲得安全密鑰74/7.7.2 BB84量子密鑰分配協(xié)議第七章 密碼協(xié)議：7.7 量子密鑰分發(fā)協(xié)議以無噪聲BB84量子密碼協(xié)議 為例階段一：基于量子信道的通信

60、(光纖或自由空間)Alice每次傳輸單個位，對應(yīng)光子的一個極化狀態(tài)，被要求等概率地使用基極化或基極化方式接收方測量儀的極化方式設(shè)置得與發(fā)送方一致，就能保證正確地接收，否則正確接收的概率是50%由于基極化和基極化的測量儀不兼容，根據(jù)Heisenberg測不準(zhǔn)原理，沒有人能夠以高于75%的準(zhǔn)確率收到Alice傳輸?shù)墓庾?.7.3 量子密鑰分配的通信模型第七章 密碼協(xié)議：7.7 量子密鑰分發(fā)協(xié)議75/第二階段：基于公共信道的兩過程通信（通過電話線或互聯(lián)網(wǎng)）過程一：原密鑰的確定Bob通過公共信道告訴Alice他對每一個收到位的測量設(shè)置，Alice通過與自己的設(shè)置進(jìn)行比較，向Bob返回正確的設(shè)置位。雙方