現(xiàn)代密碼學(xué)09-安全協(xié)議

現(xiàn)代密碼學(xué)安全協(xié)議第9章2本章內(nèi)容39.1安全協(xié)議概述9.2認(rèn)證協(xié)議9.3秘密共享9.4零知識證明9.1安全協(xié)議概述45兩個(gè)或兩個(gè)以上的參與者為完成某項(xiàng)特定任務(wù)而采取的一系列步驟什么是協(xié)議在日常生活中，幾乎所有的事情都有非正式的協(xié)議電話訂貨下棋、玩撲克選舉投票沒有人認(rèn)真考慮過這些協(xié)議，它們隨時(shí)間的推移而發(fā)展，人們都知道怎樣使用它們，而且它們也很有效6協(xié)議自始至終是個(gè)有序的過程，每個(gè)步驟必須執(zhí)行，在前一步?jīng)]有執(zhí)行完之前，后面的步驟不可能執(zhí)行協(xié)議至少需要兩個(gè)參與者通過協(xié)議必須能夠完成某項(xiàng)任務(wù)協(xié)議的主要特點(diǎn)參與者必須了解協(xié)議，并且預(yù)先知道所要完成的所有步驟參與者必須同意遵循協(xié)議每一步必須明確定義，并且不會引起誤解必須是完整的，對每種可能的情況必須規(guī)定具體的動(dòng)作協(xié)議的其他特點(diǎn)7協(xié)議必須把所有不利條件事先都估計(jì)到，而不能假定一切都是正常的和非常理想的?？匆粋€(gè)協(xié)議是否正確，不能光看在正常情況下是否正確，而且還必須非常仔細(xì)地檢查這個(gè)協(xié)議能否應(yīng)付各種異常情況。協(xié)議很復(fù)雜考慮不利條件不能假定一切正常能否應(yīng)付異常情況8明日正午進(jìn)攻，如何？同意收到“同意”收到：收到“同意”………………這樣的協(xié)議無法實(shí)現(xiàn)！兩軍問題（拜占庭將軍問題）9結(jié)論這樣無限循環(huán)下去，兩邊的藍(lán)軍都始終無法確定自己最后發(fā)出的電文對方是否已經(jīng)收到。沒有一種協(xié)議能使藍(lán)軍100%獲勝。有些問題考慮太全面則無法解決10《莊子·盜跖》：尾生與女子期于梁下，女子不來，水至不去，抱梁柱而死。有些問題考慮不全面會導(dǎo)致嚴(yán)重后果11又稱密碼協(xié)議，使用密碼技術(shù)完成某項(xiàng)特定任務(wù)，并滿足安全需求的協(xié)議。什么是安全協(xié)議在安全協(xié)議中，經(jīng)常使用對稱密碼、公鑰密碼、Hash函數(shù)、偽隨機(jī)序列發(fā)生器等密碼工具。12機(jī)密性完整性認(rèn)證性非否認(rèn)性公平性匿名性

…安全協(xié)議的安全性要求這些要求根據(jù)應(yīng)用場合不同進(jìn)行組合13安全協(xié)議的應(yīng)用電子商務(wù)

信用卡交易電子支票,電子貨幣

電子拍賣

網(wǎng)上銀行

電子政務(wù)

電子選舉

…14安全協(xié)議中的角色協(xié)議參與者攻擊者內(nèi)部/外部攻擊者被動(dòng)/主動(dòng)攻擊者可信第三方(TTP,TrustedThirdParty)用戶都信任的實(shí)體，通常與每個(gè)用戶共享密鑰功能：使用戶之間確認(rèn)彼此身份或共享會話密鑰15Dolev-Yao攻擊者模型攻擊者能做哪些事，不能做哪些事在設(shè)計(jì)和分析安全協(xié)議時(shí)，必須明確一點(diǎn)：16攻擊者能做到的事：能截獲經(jīng)過網(wǎng)絡(luò)的任何消息以合法參與者身份，發(fā)起與任何用戶的對話有機(jī)會成為任何主體發(fā)出消息的接收者能夠冒充任何別的主體給任意主體發(fā)消息17攻擊者不能做到的事：不能猜到從足夠大的空間中選出的隨機(jī)數(shù)沒有正確的密鑰，不能由給定的密文恢復(fù)出明文；也不能從給定的明文構(gòu)造出正確的密文不能從公鑰計(jì)算出相應(yīng)的私鑰不能控制計(jì)算環(huán)境中的許多私有區(qū)域，如離線的存儲器18在現(xiàn)實(shí)世界中，你會交給陌生人一疊現(xiàn)金替你買東西嗎？你沒看到別人洗牌和發(fā)牌，會和他玩三國殺嗎？沒有匿名的保證，你會在選舉中投反對票嗎？網(wǎng)絡(luò)上的協(xié)議參與者可能是完全信任的人，也可能是攻擊者和完全不信任的人。假設(shè)使用網(wǎng)絡(luò)的人都是誠實(shí)的想法，是天真的。天真的想法還有：假設(shè)網(wǎng)管是誠實(shí)的，假設(shè)網(wǎng)絡(luò)設(shè)計(jì)者是誠實(shí)的。19安全協(xié)議設(shè)計(jì)與分析的困難性安全目標(biāo)本身的微妙性表面上十分簡單的目標(biāo)，實(shí)際上十分微妙運(yùn)行環(huán)境的復(fù)雜性實(shí)際上,當(dāng)安全協(xié)議運(yùn)行在一個(gè)十分復(fù)雜的公開環(huán)境時(shí),攻擊者處處存在攻擊者模型的復(fù)雜性必須形式化地描述攻擊者的能力，對攻擊者和攻擊行為進(jìn)行分類和形式化的分析安全協(xié)議本身具有“高并發(fā)性”20好的安全協(xié)議應(yīng)滿足的條件滿足目標(biāo)(應(yīng)用目標(biāo),安全目標(biāo))易于實(shí)現(xiàn)各參與者所需計(jì)算量小、存儲量小通信負(fù)載小(延遲小,占用帶寬小)交互輪數(shù)少9.2認(rèn)證協(xié)議2122認(rèn)證的分類實(shí)體認(rèn)證

(身份認(rèn)證)數(shù)據(jù)源認(rèn)證

(消息認(rèn)證)確認(rèn)通信實(shí)體的真實(shí)身份確認(rèn)數(shù)據(jù)發(fā)送者的真實(shí)身份23實(shí)體認(rèn)證目的

向別人證明你是誰？弄清楚他是誰？24實(shí)體認(rèn)證實(shí)體認(rèn)證可分為：

單向認(rèn)證：通信一方認(rèn)證另一方的身份

雙向認(rèn)證：通信雙方彼此認(rèn)證身份25實(shí)體認(rèn)證方法

Knowsth:他知道什么可用于識別他的東西?Havesth：他擁有什么可用于識別他的東西?

Besth：他有什么特征？26實(shí)體認(rèn)證knowsth口令是最常用的認(rèn)證機(jī)制，但安全性較差

易受到泄露、猜測、竊聽、社會工程學(xué)等形式的攻擊什么是弱口令？

短口令

常見單詞

生日

電話號碼

系統(tǒng)預(yù)設(shè)口令……27口令管理措施口令應(yīng)具有一定的長度，包含多種字符類型口令不應(yīng)使用易猜測的數(shù)字或字母組合口令應(yīng)具有一定的生存期口令不應(yīng)使用一定時(shí)間內(nèi)的歷史口令用戶登錄不同系統(tǒng)應(yīng)使用不同的口令系統(tǒng)應(yīng)設(shè)定口令登錄失敗次數(shù)限制口令空間口令時(shí)間口令保護(hù)28與“基于口令的加密(PBE)”的區(qū)別基于口令的加密：利用口令推導(dǎo)出密鑰基于口令的認(rèn)證：利用口令進(jìn)行實(shí)體認(rèn)證例如：登錄電子郵箱、進(jìn)入網(wǎng)上銀行…實(shí)體認(rèn)證knowsth:基于口令的認(rèn)證機(jī)制29需解決的關(guān)鍵問題口令的存儲直接明文存儲口令？一旦得到存儲口令的數(shù)據(jù)庫，就可得到全體人員的口令。風(fēng)險(xiǎn)很大?。?！常用解決方法Needham口令認(rèn)證協(xié)議(利用Hash函數(shù)存儲口令)一次性口令機(jī)制……30原理利用Hash函數(shù)存儲口令，防范攻擊者偷取數(shù)據(jù)庫后得到口令簡單有效，廣泛應(yīng)用于各種系統(tǒng)中UNIX：使用DES代替Hash函數(shù)Discuz！……實(shí)體認(rèn)證knowsth:Needham口令認(rèn)證協(xié)議31用戶名口令散列值zhangxtR$^42@Alice6tT$^2%%……數(shù)據(jù)庫passwordH6tT$^2%%比較usernameAlice缺點(diǎn)無法防范攻擊者在線竊聽口令無法防范離線字典攻擊32為防范在線竊聽口令，可使用一次性口令機(jī)制每次認(rèn)證使用不同的口令要求用戶和系統(tǒng)共享很多口令但管理和保護(hù)大量的口令在技術(shù)上很困難為克服這一缺點(diǎn)，Lamport提出利用多次Hash的方法實(shí)現(xiàn)一次性口令機(jī)制實(shí)體認(rèn)證knowsth:一次性口令機(jī)制33方法舉例系統(tǒng)保存P100用戶保存P99、P98、P97……認(rèn)證過程用戶提交P99系統(tǒng)計(jì)算

if（P100==Hash(P99)）

{驗(yàn)證通過;

保存P99;}用戶丟棄P99初始秘密值wP1=H(w)P2=H(P1)P100=H(P99)系統(tǒng)保存計(jì)算完銷毀用戶保存實(shí)體認(rèn)證knowsth:Lamport的一次性口令機(jī)制34Lamport方案的缺點(diǎn)必須保持同步但可能因?yàn)椴豢煽啃诺阑蛩罊C(jī)出現(xiàn)丟失同步的情況(有可能是攻擊者的破壞所致)35在WEB應(yīng)用中，可以利用SSL建立安全信道，再進(jìn)行基于口令的認(rèn)證方法先使用HTTPS協(xié)議，與服務(wù)器建立安全連接(服務(wù)器必須支持HTTPS)再將用戶名和口令傳送到服務(wù)器進(jìn)行認(rèn)證應(yīng)用方便，安全保護(hù)對用戶透明比如：用瀏覽器登錄電子郵件服務(wù)器實(shí)體認(rèn)證knowsth:利用SSL建立安全信道傳輸口令36點(diǎn)擊“登錄”，瀏覽器地址欄會閃過一個(gè)以“https”開頭的地址，這說明正用SSL安全連接傳送用戶名和口令37實(shí)體認(rèn)證havesth.存儲卡：在磁卡上保存用戶信息；與PIN配合使用智能卡：由一個(gè)或多個(gè)集成電路芯片組成，包含CPU和存儲器，具有數(shù)據(jù)存儲能力和邏輯處理功能……38實(shí)體認(rèn)證besth.生物特征指紋、掌紋、虹膜、視網(wǎng)膜、手形、面部特征、聲音特征動(dòng)態(tài)特征簽名特征鍵盤特征39擴(kuò)展閱讀對實(shí)體認(rèn)證協(xié)議的典型攻擊中間人攻擊舊消息重放交錯(cuò)攻擊平行會話攻擊反射攻擊409.3秘密共享41寶藏問題海盜們把寶藏藏在一個(gè)安全的地方，只有用地圖才能找到。但地圖如何分配呢？各拿一份地圖肯定不行，因?yàn)樗麄儽舜瞬恍湃胃髂玫貓D的一部分也不行，因?yàn)橛腥藖G失他那份的話，就無法復(fù)原地圖如何解決

——秘密共享技術(shù)42秘密共享是什么將秘密分割存儲的密碼技術(shù)秘密共享的目的防止秘密過于集中，以達(dá)到分散風(fēng)險(xiǎn)和容忍入侵的目的43提出時(shí)間Shamir1979年(m,n)門限方案將秘密SK拆成n份任意m(m≤n)份或更多份都可以恢復(fù)SK任何少于m份都不能得到關(guān)于SK的任何有用信息其中，每一份都稱為一個(gè)share（或shadow）門限方案解決秘密共享問題最常用的方法44(3,5)門限方案SKSK3SK5SKSKSK1SK2SK445拉格朗日插值多項(xiàng)式給定有限域Fp中互不相同的整數(shù)x1,…,xn+1,和任意不全為零的整數(shù)k1,…,kn+1，公式

滿足f(xi)=ki，i=1,…,n+1f(x)是一個(gè)n次多項(xiàng)式，稱為拉格朗日插值多項(xiàng)式Shamir的門限方案基于拉格朗日插值多項(xiàng)式46方案描述分割秘密設(shè)待共享秘密為K,令a0=K隨機(jī)產(chǎn)生m-1次多項(xiàng)式

f(x)=(am-1xm-1+…+a1x+a0)modp依次計(jì)算ki=f(xi)，i=1,…,n易知K=f(0),且每一對(xi,ki)都是f(x)函數(shù)曲線上的一個(gè)點(diǎn)ki是每個(gè)參與者的share,必須保密(xi無需保密)47重構(gòu)f(x)

給定k1,k2,…,km共m個(gè)share，對應(yīng)的分別是x1,x2,…,xm。f(x)可由拉格朗日插值多項(xiàng)式給出：恢復(fù)秘密K=f(0)48安全性原理對于m-1次多項(xiàng)式，只需給出m個(gè)點(diǎn)就可以唯一地重構(gòu)，少于m個(gè)share則不能。由此保證K可從m個(gè)share中獲得，而少于m個(gè)辦不到。49舉例：(3,5)的門限方案設(shè)m=3，n=5，p=17，K=13，分割秘密構(gòu)造隨機(jī)多項(xiàng)式f(x)＝(2x2+10x+13)mod17k1=f(1)=(2+10+13)mod17=8k2=f(2)=(8+20+13)mod17=7k3=f(3)=(18+30+13)mod17=10k4=f(4)=(32+40+13)mod17=0k5=f(5)=(50+50+13)mod17=11k1,…,k5便是share,每個(gè)用戶一人一個(gè)50重構(gòu)f(x)

給定k1=8,k3=10,k5=11,重構(gòu)如下：恢復(fù)K=f(0)=1351門限方案的圖形化—視覺密碼提出者Shamir等目的將寫有秘密信息的圖片拆分成n張,至少m張(m≤n)才能恢復(fù)原來的圖片優(yōu)點(diǎn)安全性高：相當(dāng)于“一次一密”計(jì)算開銷低：恢復(fù)原圖片時(shí)，用幻燈機(jī)即可，無需計(jì)算機(jī)參與52(2,3)的視覺密碼方案寫有秘密信息的原圖片天王蓋地虎寶塔鎮(zhèn)河妖53一個(gè)實(shí)際的例子9.4零知識證明5455Peter：我知道瑞士銀行計(jì)算機(jī)系統(tǒng)的口令Victor：我才不信，你不知道Peter：我就知道Victor：拉倒吧，別忽悠Peter：我確實(shí)知道Victor：你怎么證明Peter悄悄說出了口令Victor：艾瑪，現(xiàn)在我也知道了，我去告訴小紅Peter一臉黑線-_-|||一個(gè)小故事56我知道某個(gè)秘密我想向別人證明“我確實(shí)知道這個(gè)秘密”除此之外，我不想讓別人獲得關(guān)于該秘密的任何知識應(yīng)該怎么辦？——零知識證明57什么叫“獲得知識”：本來有些事Victor自己干不了，但通過與Peter的交流，在不需要?jiǎng)e人參與的情況下，這些事Victor自己可以干了，就稱“Victor從Peter那里獲得了知識”相反的，與Peter交流之后，這些事Victor自己還是干不了，就稱“Victor從Peter那里沒獲得知識”(Victor所能干的事情并沒有因?yàn)榕cPeter交流而變得更多)58零知識證明協(xié)議應(yīng)滿足三個(gè)特性：完備性：誠實(shí)證明者可以壓倒性概率使校驗(yàn)者接受自己的宣稱正確性：不誠實(shí)證明者欺騙校驗(yàn)者的概率可以忽略不計(jì)零知識：校驗(yàn)者無法獲得關(guān)于秘密的任何知識59設(shè)Peter(證明者)知道可打開C和D之間暗門的咒語，不知道者都將走進(jìn)死胡同Peter向Victor(校驗(yàn)者)證明自己知道咒語，但不讓Victor知道關(guān)于咒語的任何知識ABCD零知識洞穴零知識證明概念圖解60解決咒語問題的零知識證明協(xié)議Victor站在A點(diǎn)Peter進(jìn)入洞中任一點(diǎn)C或DPeter進(jìn)洞后，Victor走到B點(diǎn)Victor隨機(jī)叫Peter：從左邊或右邊出來Peter按要求執(zhí)行(可借助咒語)Peter和Victor重復(fù)執(zhí)行①～⑤共n次ABCD61分析：完備性如果Peter知道咒語，他總能正確回答Victor的提問。正確性如果Peter不知道咒語，他只能從原路返回到B點(diǎn)，因此每一輪他欺騙Victor的概率是1/2，n輪成功欺騙的概率是1/2n,是可以忽略的。零知識從協(xié)議執(zhí)行可知，與Peter交互后，Victor無法獲得關(guān)于咒語的任何知識62零知識洞穴問題可以轉(zhuǎn)化為數(shù)學(xué)問題，Peter知道解決某個(gè)難題的秘密（相當(dāng)于咒語），而Victor通過與Peter交互以驗(yàn)證其真實(shí)性。63結(jié)論

如果單向函數(shù)是存在的，任何一個(gè)NP問題都存在零知識證明相關(guān)論文Goldwasser,Micali,Rackoff.Theknowledgecomplexityofinteractive-proofsystems.Proc.of17thACMSym.onTheoryofComputation,pp.291-304,1985.NP與零知識證明G0NP與零知識證明舉例—圖同構(gòu)證明兩個(gè)圖G0和G1是同構(gòu)的（置換為δ）Alice向Bob證明：他知道兩個(gè)圖是如何同構(gòu)的

也即證明自己知道δG1δ

G0基本原理G1δ

Gπ

G與G1的置換？π

o

δG與G0的置換為πG0G1πGC=0or1δ

證明過程如下G0G1C=0or1Gπδ

G0G1GC’C=0or1C’=0or1πδ

G0G1GC=0or1C’=0or1x=πifc=c’x=π

o

δifc≠c’xπC’δ

G0G1GC=0or1C’=0or1x=πifc=c’x=π

o

δifc≠c’xπC’δ

檢查x是否是G與Gc’的同構(gòu)關(guān)系n

輪G0G172協(xié)議描述：Alice如下執(zhí)行：