第9章-密碼協(xié)議(不經(jīng)意傳輸和擲硬幣協(xié)議).ppt

1、第9章 密碼協(xié)議,2,協(xié)議,協(xié)議是一系列步驟 它包括兩方或多方 設計它的目的是要完成一項任務,3,協(xié)議特點,協(xié)議中的每人都必須了解協(xié)議，并且預先知道所要完成的所有步驟。 協(xié)議中的每人都必須同意遵循它。 協(xié)議必須是不模糊的，每一步必須明確定義，并且不會引起誤解。 協(xié)議必須是完整的，對每種可能的情況必須規(guī)定具體的動作。,4,密碼協(xié)議,密碼協(xié)議，有時也稱作安全協(xié)議，是以密碼學為基礎的消息交換協(xié)議，其目的是在網(wǎng)絡環(huán)境中提供各種安全服務。密碼學是網(wǎng)絡安全的基礎，但網(wǎng)絡安全不能單純依靠安全的密碼算法。安全協(xié)議是網(wǎng)絡安全的一個重要組成部分，我們需要通過安全協(xié)議進行實體之間的認證、在實體之間安全地分配密鑰或其

2、它各種秘密、確認發(fā)送和接收的消息的非否認性等。 密碼協(xié)議包含某種密碼算法. 參與該協(xié)議的伙伴可能是朋友和完全信任的人，或者也可能是敵人和互相完全不信任的人。 在協(xié)議中使用密碼的目的是防止或發(fā)現(xiàn)偷聽者和欺騙.,5,協(xié)議的目的,計算一個數(shù)值想共享它們的秘密部分 共同產(chǎn)生隨機序列 確定互相的身份 同時簽署合同,6,對協(xié)議的攻擊,被動攻擊 主動攻擊 被動騙子 主動騙子 協(xié)議對被動欺騙來說應該是安全的 合法用戶可以發(fā)覺是否有主動欺騙,7,9.5 不經(jīng)意傳輸協(xié)議,設A有一個秘密，想以1/2的概率傳遞給B，即B有50%的機會收到這個秘密，另外50%的機會什么也沒有收到，協(xié)議執(zhí)行完后，B知道自己是否收到了這個

3、秘密，但A卻不知B是否收到了這個秘密。這種協(xié)議就稱為不經(jīng)意傳輸協(xié)議。 例如A是機密的出售者，A列舉了很多問題，意欲出售各個問題的答案，B想買其中一個問題的答案，但又不想讓A知道自己買的是哪個問題的答案。,8,9.5 不經(jīng)意傳輸協(xié)議,1. 基于大數(shù)分解問題的不經(jīng)意傳輸協(xié)議 設A想通過不經(jīng)意傳輸協(xié)議傳遞給B的秘密是整數(shù)n（為兩個大素數(shù)之積）的因數(shù)分解。這個問題具有普遍意義，因為任何秘密都可通過RSA加密，得到n的因數(shù)分解就可得到這個秘密。 協(xié)議基于如下事實： 已知某數(shù)在模n下兩個不同的平方根，就可分解n。,9,9.5 不經(jīng)意傳輸協(xié)議,協(xié)議如下： B隨機選一數(shù)x，將x2 mod n發(fā)送給A。 A（掌

4、握n=pq的分解）計算x2 mod n的4個平方根x和y，并將其中之一發(fā)送給B。由于A只知道x2 mod n，并不知道4個平方根中哪一個是B選的x。 B檢查第步收到的數(shù)是否與x在模n下同余，如果是，則B沒有得到任何新信息；否則B就掌握了x2 mod n的兩個不同的平方根，從而能夠分解n。而A卻不知究竟是哪種情況。 顯然，B得到n的分解的概率是1/2。,10,9.5 不經(jīng)意傳輸協(xié)議,2. “多傳一”的不經(jīng)意傳輸協(xié)議 設A有多個秘密，想將其中一個傳遞給B，使得只有B知道A傳遞的是哪個秘密。設A的秘密是s1,s2,sk，每一秘密是一比特序列。協(xié)議如下： A告訴B一個單向函數(shù)f，但對f-1保密。 設B

5、想得到秘密si，他在f的定義域內隨機選取k個值x1,x2,xk，將k元組(y1,y2,yk)發(fā)送給A，其中,11,9.5 不經(jīng)意傳輸協(xié)議, A計算zj=f-1(yj)(j=1,2,k)，并將zj sj(j=1,2,k)發(fā)送給B。 由于zi=f-1(yi)=f-1(f(xi)=xi，所以B知道zi，因此可從zi si獲得si。 由于B沒有zj(ji)的信息，因此無法得到sj(ji)，而A不知k元組(y1,y2,yk)中哪個是f(xi)，因此無法確定B得到的是哪個秘密。,12,9.6 擲硬幣協(xié)議,在某些密碼協(xié)議中要求通信雙方在無第三方協(xié)助的情況下，產(chǎn)生一個隨機序列，因為A、B之間可能存在不信任關系

6、，因此隨機序列不能由一方產(chǎn)生再通過電話或網(wǎng)絡告訴另一方。這一問題可通過擲硬幣協(xié)議來實現(xiàn)，擲硬幣協(xié)議有多種實現(xiàn)方式，下面介紹其中的3種。,13,9.6 擲硬幣協(xié)議,1. 采用平方根擲硬幣 協(xié)議如下： A選擇兩個大素數(shù)p、q，將乘積n=pq發(fā)送給B。 B在1和n/2之間，隨機選擇一個整數(shù)u，計算zu2 mod n，并將z發(fā)送給A。 A計算模n下z的4個平方根x和y（因A知道n的分解，所以可做到），設x是x mod n和-x mod n中較小者，y是y mod n和-y mod n中較小者，則由于1un/2，所以u為x和y之一。,14,9.6 擲硬幣協(xié)議, A猜測u=x或u=y，或者A找出最小的i使

7、得x的第i個比特與y的第i個比特不同，A猜測u的第i個比特是0還是1。A將猜測發(fā)送給B。 B告訴A猜測正確或不正確，并將u的值發(fā)送給A。 A公開n的因子。,15,9.6 擲硬幣協(xié)議,因u是B隨機選取的，A不知道u，所以要猜測u只能是計算模n下z的4個平方根，猜中的概率是1/2。再考慮B如何能欺騙A，如果B在A猜測完后能夠改變u的值，則A的猜測必不正確，A可通過 zu2 mod n 檢查出B是否改變了u的值，所以B要想改變u的值就只能在x和y之間進行。而B若掌握x和y，就可通過gcdx-y, n或gcdx+y, n求出p和q，說明B的欺騙與分解n是等價的。,16,9.6 擲硬幣協(xié)議,例9.1 A

8、取p=3,q=7，將n=21發(fā)送給B。 B在1和21/2之間，隨機選擇一個整數(shù)u=2，計算z22 mod n4并將z=4發(fā)送給A。 A計算模21下z=4的4個平方根x=2,-x=19,y=5,-y=16，取x= 2，y= 5。,17,9.6 擲硬幣協(xié)議, A猜測u=5并將猜測發(fā)送給B. B告訴A猜測不正確，并將u=2發(fā)送給A，A檢驗u=2在1和21/2之間且滿足422 mod 21，A知道自己輸了。 A公開n=21的因子p=3,q=7，B檢驗n=pq，知道自己贏了。,18,9.6 擲硬幣協(xié)議,2. 利用單向函數(shù)擲硬幣 設A、B都知道某一單向函數(shù)f(x)，但都不知道該函數(shù)的逆函數(shù)，協(xié)議如下： B

9、選擇一個隨機數(shù)x，求y=f(x)并發(fā)送給A。 A對x的奇偶性進行猜測，并將結果告訴B。 B告訴A猜測正確或不正確，并將x發(fā)送給A。 由于A不知道f(x)的逆函數(shù)，因此無法通過B發(fā)過來的y得出x，即只能猜測x的奇偶性。而B若在A做出猜測以后改變x，A可通過 檢查出來。,19,9.6 擲硬幣協(xié)議,3. 利用二次剩余擲硬幣 設n是兩個大素數(shù)p、q的乘積，即n=pq。整數(shù)a滿足0an和gcd(a,n)=1，則有一半的a，其Jacobi符號 ，而在滿足 的所有a中，只有一半是模n的平方剩余，而判斷a是否為模n的平方剩余與分解n是等價的。,20,9.6 擲硬幣協(xié)議,協(xié)議如下： B選擇p、q，計算n=pq；再選取滿足 的隨機數(shù)a，將n和a發(fā)送給A。 A猜測a