密碼學第11章-密碼協(xié)議課件

第11章密碼協(xié)議概述密鑰分配與密鑰協(xié)商秘密共享身份識別零知識證明

不經(jīng)意傳輸習題第11章密碼協(xié)議概述密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件防止重放攻擊密鑰確證防止重密鑰確證密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件這里TA不同于在線密鑰分配中的TA，他只負責初始化時發(fā)放證書，以及必要時的糾紛處理，一般情況下的密鑰協(xié)商過程不需要TA參與。每個用戶的證書C(U)實際上是此用戶的一個可信的（經(jīng)可信第三方“蓋章”的）驗證簽名算法。注：總假設(shè)證書發(fā)放時TA會驗明身份，不存在冒充這里TA不同于在線密鑰分配中的TA，他只負責初始化時發(fā)放證書密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件W無法偽造U和V的簽名，因此不能成功實施中間人攻擊W無法偽造U和V的簽名，因此不能成功實施中間人攻擊密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件實際上求密鑰只需要將前面三式中的常數(shù)項相加即可實際上求密鑰只需要將前面三密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件u相當于是代表自己身份的密鑰，不可泄露出去仍假設(shè)發(fā)放證書時不存在假冒。即保證證書中的v一定是A提供給TA的這個證書說明：TA能保證(只有)真正的A有v的離散對數(shù)u識別思路？A向B證明他知道u的值u相當于是代表自己身份的密鑰，不可泄露出去仍假設(shè)發(fā)放證書時不密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件零知識洞穴Quisquater和Guillou給出了一個非常形象的例子來解釋零知識證明。在洞穴深處的位置C和位置D之間有一道門，只有知道秘密咒語的人才能打開它。假設(shè)P知道打開門的咒語，P想向V證明自己知道咒語，但又不想向V泄露咒語。P可以利用下列協(xié)議來達到這個目的：零知識洞穴在洞穴深處的位置C和位置D之間有一道門，只有知道秘密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件協(xié)議如下：①B選擇p、q，計算n=pq；再選取滿足

的隨機數(shù)a，將n和a發(fā)送給A。②A猜測a是模n的平方剩余或非平方剩余，并將結(jié)果告訴B。③B告訴A猜測正確或不正確，并將p、q發(fā)送給A④A檢查p、q都是素數(shù)且n=pq。顯然，A猜中的概率是1/2。協(xié)議執(zhí)行完后，A根據(jù)p、q可求出amodn的4個平方根（如果a是模n的平方剩余），以檢查B是否在A猜測完后將結(jié)果做了修改。協(xié)議如下：設(shè)A有一個秘密，想以1/2的概率傳遞給B，即B有50%的機會收到這個秘密，另外50%的機會什么也沒有收到，協(xié)議執(zhí)行完后，B知道自己是否收到了這個秘密，但A卻不知B是否收到了這個秘密。這種協(xié)議就稱為不經(jīng)意傳輸協(xié)議。不經(jīng)意傳輸設(shè)A有一個秘密，想以1/2的概率傳遞給B，即B有501.基于大數(shù)分解問題的不經(jīng)意傳輸協(xié)議設(shè)A想通過不經(jīng)意傳輸協(xié)議傳遞給B的秘密是整數(shù)n（為兩個大素數(shù)之積）的因數(shù)分解。這個問題具有普遍意義，因為任何秘密都可通過RSA加密，得到n的因數(shù)分解就可得到這個秘密。協(xié)議基于如下事實：已知某數(shù)在模n下兩個不同的平方根，就可分解n。1.基于大數(shù)分解問題的不經(jīng)意傳輸協(xié)議協(xié)議如下：①B隨機選一數(shù)x，將x2modn發(fā)送給A。②A（掌握n=pq的分解）計算x2modn的4個平方根±x和±y，并將其中之一發(fā)送給B。由于A只知道x2modn，并不知道4個平方根中哪一個是B選的x。③B檢查第②步收到的數(shù)是否與±x在模n下同余，如果是，則B沒有得到任何新信息；否則B就掌握了x2modn的兩個不同的平方根，從而能夠分解n。而A卻不知究竟是哪種情況。顯然，B得到n的分解的概率是1/2。協(xié)議如下：2.基于離散對數(shù)問題的不經(jīng)意傳輸協(xié)議下一個不經(jīng)意傳輸協(xié)議是非交互的，其中B不向A發(fā)送任何消息。設(shè)系統(tǒng)中所有用戶都知道一個大素數(shù)p、GF(p)-{0}的生成元g和另一大素數(shù)c，但無人知道c的離散對數(shù)。假定計算離散對數(shù)是不可行的，因此從gxmodp和gymodp無法計算gxymodp。協(xié)議中所有運算都在GF(p)中進行。2.基于離散對數(shù)問題的不經(jīng)意傳輸協(xié)議B按如下方式產(chǎn)生公開的加密密鑰和秘密的解密密鑰：隨機選取一個比特i和一個數(shù)x(0≤x≤p-2)，計算yi=gx,y1-i=c(gx)-1，以(y0,y1)作為公開的加密密鑰，以(i,x)作為秘密解密密鑰。由于B不知道c的離散對數(shù)，所以他知道y0和y1兩者其中一個的離散對數(shù)，而A無法知道y0和y1中哪個離散對數(shù)是B已知的。A可通過方程y0y1=c來檢查B的公開加密密鑰是否正確。B按如下方式產(chǎn)生公開的加密密鑰和秘密的解密密鑰：協(xié)議中設(shè)A的兩個秘密s0和s1是二進制數(shù)，是異或運算，若進行異或運算的兩個數(shù)不等長，可在較短數(shù)前面補0。協(xié)議如下：①A在0到p-2之間隨機取兩個整數(shù)k0、k1，對j=0,1計算

將c0,c1,m0,m1發(fā)送給B。②B用自己的秘密解密密鑰計算。由于B不知道y1-i的離散對數(shù)，所以無法得到d1-i和s1-i。注：本協(xié)議相當于“二傳一”不經(jīng)意傳輸。若其中一個為有效秘密一個為空，則成為前一種不經(jīng)意傳輸。協(xié)議中設(shè)A的兩個秘密s0和s1是二進制數(shù)，是異或運3.“多傳一”的不經(jīng)意傳輸協(xié)議設(shè)A有多個秘密，想將其中一個傳遞給B，使得只有B知道A傳遞的是哪個秘密。設(shè)A的秘密是s1,s2,…,sk，每一秘密是一比特序列。協(xié)議如下：①A告訴B一個單向函數(shù)f，但對f-1保密。②設(shè)B想得到秘密si，他在f的定義域內(nèi)隨機選取k個值x1,x2,…,xk，將k元組(y1,y2,…,yk)發(fā)送給A，其中3.“多傳一”的不經(jīng)意傳輸協(xié)議③A計算zj=f-1(yj)(j=1,2,…,k)，并將zjsj(j=1,2,…,k)發(fā)送給B。④由于zi=f

-1(yi)=f

-1(f(xi))=xi，所以B知道zi，因此可從zisi獲得si。由于A不知k元組(y1,y2,…,yk)中哪個是f(xi)，因此無法確定B得到的是哪個秘密。然而如果B不遵守協(xié)議，他用f對多個xj求得f(xj)，就可獲得多個秘密。因此總假定這種“多傳一”協(xié)議中所有用戶都遵守協(xié)議。③A計算zj=f-1(yj)(j=1,2,…,k)，并將4.基于大數(shù)分解問題的“多傳一”不經(jīng)意傳輸協(xié)議設(shè)A有多個秘密，并對自己的每個秘密都使用一個不同的RSA體制加密，A要想向B傳遞其中的一個秘密，就可告訴B加密該秘密的RSA體制模數(shù)的分解。協(xié)議如下：①A構(gòu)造k個RSA加密體制，使得在每個體制中的兩個素數(shù)pj和qj滿足pj≡qj≡3mod4（這樣可保證同一數(shù)a在模nj=pjqj下的兩個平方根有相反的Jacobi符號），將加密密鑰(ej,nj)及加密后的秘密發(fā)送給B，其中j=1,2,…,k。4.基于大數(shù)分解問題的“多傳一”不經(jīng)意傳輸協(xié)議②B選k個數(shù)x1,x2,…,xk，分別計算Jacobi符號

和x2jmodnj

（j=1,2,…,k）。B如果想獲得秘密si，則將x2imodni和發(fā)送給A，而對所有j≠i，將x2jmodnj和

發(fā)送給A。③對每一j，A計算x2jmodnj的平方根和平方根的Jacobi符號，比較每一平方根的Jacobi符號是否與第②步收到的Jacobi符號相同，將Jacobi符號相同的那一平方根發(fā)送給B。④B現(xiàn)在獲得x2imodni的兩個不同的平方根，因此能夠分解ni，求出解密密鑰di，進一步求出si；而對j≠i，B在第③步收到的平方根是自己已知的，因此無法求出nj和sj。②B選k個數(shù)x1,x2,…,xk，分別計算Jacobi符號因為A不知道B選擇的是哪個i，因此不知道B獲得的是哪個秘密。協(xié)議中仍假定A、B都遵守協(xié)議，否則B在第②步進行欺騙的話，A仍無法識別。因為A不知道B選擇的是哪個i，因此不知道B獲得的是哪個秘密。例7.7在上述協(xié)議中，設(shè)A用于加密某個秘密s的RSA體制的模數(shù)n=2773=47×59，滿足47≡59≡3mod4。B在第②步選擇的相應(yīng)x=2001，計算x2modn=20012mod2773=2562及如果B想獲得s，則將(2562,1)發(fā)送給A例7.7在上述協(xié)議中，設(shè)A用于加密某個秘密s的RSA體制的第③步，A如下計算2562mod2773的平方根：求2562mod47=24,2562mod59=25，求出24在mod47時的平方根為±27，25在mod59時的平方根為±5，由中國剩余定理求出平方根為±27·59·4±5·47·54，即349，772，2001，2424。因，A將349或2424發(fā)送給B。第③步，A如下計算2562mod2773的平方根：第④步，B由gcd{2773,349+2001}=47或gcd{2773,2424-2001}=47得n的一個因子，從而得到n的分解式47×59。若B不想獲得s，則將(2562,-1)發(fā)送給A，A將772或2001發(fā)送給B，因772≡2001mod2773，所以B未收到任何新信息。第④步，B由gcd{2773,349+2001}=47第11章密碼協(xié)議概述密鑰分配與密鑰協(xié)商秘密共享身份識別零知識證明

不經(jīng)意傳輸習題第11章密碼協(xié)議概述密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件防止重放攻擊密鑰確證防止重密鑰確證密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件這里TA不同于在線密鑰分配中的TA，他只負責初始化時發(fā)放證書，以及必要時的糾紛處理，一般情況下的密鑰協(xié)商過程不需要TA參與。每個用戶的證書C(U)實際上是此用戶的一個可信的（經(jīng)可信第三方“蓋章”的）驗證簽名算法。注：總假設(shè)證書發(fā)放時TA會驗明身份，不存在冒充這里TA不同于在線密鑰分配中的TA，他只負責初始化時發(fā)放證書密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件W無法偽造U和V的簽名，因此不能成功實施中間人攻擊W無法偽造U和V的簽名，因此不能成功實施中間人攻擊密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件實際上求密鑰只需要將前面三式中的常數(shù)項相加即可實際上求密鑰只需要將前面三密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件u相當于是代表自己身份的密鑰，不可泄露出去仍假設(shè)發(fā)放證書時不存在假冒。即保證證書中的v一定是A提供給TA的這個證書說明：TA能保證(只有)真正的A有v的離散對數(shù)u識別思路？A向B證明他知道u的值u相當于是代表自己身份的密鑰，不可泄露出去仍假設(shè)發(fā)放證書時不密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件零知識洞穴Quisquater和Guillou給出了一個非常形象的例子來解釋零知識證明。在洞穴深處的位置C和位置D之間有一道門，只有知道秘密咒語的人才能打開它。假設(shè)P知道打開門的咒語，P想向V證明自己知道咒語，但又不想向V泄露咒語。P可以利用下列協(xié)議來達到這個目的：零知識洞穴在洞穴深處的位置C和位置D之間有一道門，只有知道秘密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件密碼學第11章-密碼協(xié)議課件協(xié)議如下：①B選擇p、q，計算n=pq；再選取滿足

的隨機數(shù)a，將n和a發(fā)送給A。②A猜測a是模n的平方剩余或非平方剩余，并將結(jié)果告訴B。③B告訴A猜測正確或不正確，并將p、q發(fā)送給A④A檢查p、q都是素數(shù)且n=pq。顯然，A猜中的概率是1/2。協(xié)議執(zhí)行完后，A根據(jù)p、q可求出amodn的4個平方根（如果a是模n的平方剩余），以檢查B是否在A猜測完后將結(jié)果做了修改。協(xié)議如下：設(shè)A有一個秘密，想以1/2的概率傳遞給B，即B有50%的機會收到這個秘密，另外50%的機會什么也沒有收到，協(xié)議執(zhí)行完后，B知道自己是否收到了這個秘密，但A卻不知B是否收到了這個秘密。這種協(xié)議就稱為不經(jīng)意傳輸協(xié)議。不經(jīng)意傳輸設(shè)A有一個秘密，想以1/2的概率傳遞給B，即B有501.基于大數(shù)分解問題的不經(jīng)意傳輸協(xié)議設(shè)A想通過不經(jīng)意傳輸協(xié)議傳遞給B的秘密是整數(shù)n（為兩個大素數(shù)之積）的因數(shù)分解。這個問題具有普遍意義，因為任何秘密都可通過RSA加密，得到n的因數(shù)分解就可得到這個秘密。協(xié)議基于如下事實：已知某數(shù)在模n下兩個不同的平方根，就可分解n。1.基于大數(shù)分解問題的不經(jīng)意傳輸協(xié)議協(xié)議如下：①B隨機選一數(shù)x，將x2modn發(fā)送給A。②A（掌握n=pq的分解）計算x2modn的4個平方根±x和±y，并將其中之一發(fā)送給B。由于A只知道x2modn，并不知道4個平方根中哪一個是B選的x。③B檢查第②步收到的數(shù)是否與±x在模n下同余，如果是，則B沒有得到任何新信息；否則B就掌握了x2modn的兩個不同的平方根，從而能夠分解n。而A卻不知究竟是哪種情況。顯然，B得到n的分解的概率是1/2。協(xié)議如下：2.基于離散對數(shù)問題的不經(jīng)意傳輸協(xié)議下一個不經(jīng)意傳輸協(xié)議是非交互的，其中B不向A發(fā)送任何消息。設(shè)系統(tǒng)中所有用戶都知道一個大素數(shù)p、GF(p)-{0}的生成元g和另一大素數(shù)c，但無人知道c的離散對數(shù)。假定計算離散對數(shù)是不可行的，因此從gxmodp和gymodp無法計算gxymodp。協(xié)議中所有運算都在GF(p)中進行。2.基于離散對數(shù)問題的不經(jīng)意傳輸協(xié)議B按如下方式產(chǎn)生公開的加密密鑰和秘密的解密密鑰：隨機選取一個比特i和一個數(shù)x(0≤x≤p-2)，計算yi=gx,y1-i=c(gx)-1，以(y0,y1)作為公開的加密密鑰，以(i,x)作為秘密解密密鑰。由于B不知道c的離散對數(shù)，所以他知道y0和y1兩者其中一個的離散對數(shù)，而A無法知道y0和y1中哪個離散對數(shù)是B已知的。A可通過方程y0y1=c來檢查B的公開加密密鑰是否正確。B按如下方式產(chǎn)生公開的加密密鑰和秘密的解密密鑰：協(xié)議中設(shè)A的兩個秘密s0和s1是二進制數(shù)，是異或運算，若進行異或運算的兩個數(shù)不等長，可在較短數(shù)前面補0。協(xié)議如下：①A在0到p-2之間隨機取兩個整數(shù)k0、k1，對j=0,1計算

將c0,c1,m0,m1發(fā)送給B。②B用自己的秘密解密密鑰計算。由于B不知道y1-i的離散對數(shù)，所以無法得到d1-i和s1-i。注：本協(xié)議相當于“二傳一”不經(jīng)意傳輸。若其中一個為有效秘密一個為空，則成為前一種不經(jīng)意傳輸。協(xié)議中設(shè)A的兩個秘密s0和s1是二進制數(shù)，是異或運3.“多傳一”的不經(jīng)意傳輸協(xié)議設(shè)A有多個秘密，想將其中一個傳遞給B，使得只有B知道A傳遞的是哪個秘密。設(shè)A的秘密是s1,s2,…,sk，每一秘密是一比特序列。協(xié)議如下：①A告訴B一個單向函數(shù)f，但對f-1保密。②設(shè)B想得到秘密si，他在f的定義域內(nèi)隨機選取k個值x1,x2,…,xk，將k元組(y1,y2,…,yk)發(fā)送給A，其中3.“多傳一”的不經(jīng)意傳輸協(xié)議③A計算zj=f-1(yj)(j=1,2,…,k)，并將zjsj(j=1,2,…,k)發(fā)送給B。④由于zi=f

-1(yi)=f

-1(f(xi))=xi，所以B知道zi，因此可從zisi獲得si。由于A不知k元組(y1,y2,…,yk)中哪個是f(xi)，因此無法確定B得到的是哪個秘密。然而如果B不遵守協(xié)議，他用f對多個xj求得f(xj)，就可獲得多個秘密。因此總假定這種“多傳一”協(xié)議中所有用戶都遵守協(xié)議。③A計算zj=f-1(yj)(j=1,2,…,k)，并將4.基于大數(shù)分解問題的“多傳一”不經(jīng)意傳輸協(xié)議設(shè)A有多個秘密，并對自己的每個秘密都使用一個不同的RSA體制加密，A要想向B傳遞其中的一個秘密，就可告訴B加密該秘密的RSA體制模數(shù)的分解。協(xié)議如下：①A構(gòu)造k個RSA加密體制，使得在每個體制中的兩個素數(shù)pj和qj滿足pj≡qj≡3mod4（這樣可保證同一數(shù)a在模nj=pjqj下的兩個平方根有相反的Jacobi符號），將加密密鑰(ej,nj)及加密后的秘密發(fā)送給B，其中j=1,2,…,k。4.基于大數(shù)分解問題的“多傳一”不經(jīng)意傳輸協(xié)議②B選k個數(shù)x1,x2,…,xk，分別計算Jacobi符號

和x2jmodnj

（j=1,2,…,k）。B如果想獲得秘密si，