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

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

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

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

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

5、想得到秘密si，他在f的定義域內(nèi)隨機(jī)選取k個(gè)值x1,x2,xk，將k元組(y1,y2,yk)發(fā)送給A，其中,11,9.5 不經(jīng)意傳輸協(xié)議, A計(jì)算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)中哪個(gè)是f(xi)，因此無法確定B得到的是哪個(gè)秘密。,12,9.6 擲硬幣協(xié)議,在某些密碼協(xié)議中要求通信雙方在無第三方協(xié)助的情況下，產(chǎn)生一個(gè)隨機(jī)序列，因?yàn)锳、B之間可能存在不信任關(guān)系

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

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

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

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