1、應用學13.鑒別方案助理教授引言Feige、Fiat和Shamir改進的著名的的零知識證明方案1986年在以色列、歐洲和會議上。鑒別方案可以轉換為數字簽名方案，用一個單向函數取代鑒別者Victor即可。2014-06-0321.簡化方案仲裁方產生n為兩大素數之積，選取v，滿足：x2v mod n有解且v-1 mod n存在則Peggy的公鑰：v私鑰：mins|ssqrt(v-1) mod n2014-06-033協議描述：x=r2 mod nbPeggy選rnVictor選隨機位b(0或1)驗證y2vb是否等于xy計算y=rsb mod n2014-06-0342. Feige-Fiat-Sh

2、amir鑒別方案仲裁方產生n為兩大素數之積，選取vi(1ik)x2vi mod n有解且vimod n存在-1滿足：則Peggy的公鑰：vi私鑰：si = minsqrt(v -1) mod ni2014-06-035協議描述：Peggy選rnx=r2 mod nb1bkVictork位隨機二進制串b b1k計算y r 驗證kyi1kbSmodniy 2bvmodniiii1是否等于x重復t次，則PeggyVictor的概率為1/2kt2014-06-036舉例：n=35=57，則滿足條件的v為：vv-1s=sqrt(v-1)2014-06-037Peggy取4,11,16,29為公鑰，相應的

3、私鑰為：3,4,9,8Peggy選r=16，計算x=r2 mod n=162 mod 35=11Victor發隨機串1101給Peggy(3)Peggy計算y=1631419081 mod 35=31(4)Victor驗證：31241111160291 mod 35=112014-06-0383.加強方案鑒別信息I(如名字、地址等)嵌入協議中。將用單向散列函數，連同一系列j，計算v1,v2,vkH(I,j)Peggy的公鑰為I和一串j值。2014-06-0394.Fiat-Shamir簽名方案初始設置：類似鑒別方案。bij,m,yi(i=1 t)AliceBob根據v1vk計算z1ztk隨機選

4、t個r1rt,計算xi=r 2 mod n,得到位序列ibz y2vmod nijH(m,x1xt),選bij,計算y1ytkiijj1j1by r 驗證簽名H(m,z1zt)開始的kt位是否等于bijSmod nijiij2014-06-031017.2 Guillou-Quisquater方案1.適用于智能卡應用的鑒別方案Peggy的公鑰：J v是一些憑證的集合，記為J。n私鑰：B 滿足JBv 1 mod nPeggy將J發給Victor，為了證明J是他的憑證，必須向Victor證明他知道B。T=rv mod ndPeggy選rnVictor隨機選d,0dv-1D計算DvJd mod n是

5、否等于T計算D=rBdmod n2014-06-031117.2 Guillou-Quisquater方案2.數字簽名方案Alicem,d,J,DBob選rn，計算 T=rv mod n計算d=H(m,T),dv計算D=rBd mod n計算T=DvJd mod n和d=H(m,T)，判斷d是否等于d3.多重簽名方案多個人對同一文件簽名。前提：n,v是系統公有的。Alice和Bob有(JA,BA)和(JB,BB)對消息m簽名，其他人如Carol可驗證簽名。2014-06-031217.2 Guillou-Quisquater方案協議描述TAAliceBob選rA,計算TA=rmod nvTB選

6、r ,計算T =rmod nvABAB計算T=(B) mod n計算T=(TBTA) mod n和d=H(m,T)計算DB=rBBBd mod n和d=H(m,T)DA計算DA=rABmod ndA計算D=DADB mod n，簽名組成：m,d,D,JA,JB2014-06-0313DB17.2 Guillou-Quisquater方案Carol驗證：計算J=JAJB mod n計算T=DvJd mod n和d=H(m,T)驗證d是否等于d2014-06-031417.3 Schnorr算法特點：安全性基于離散對數；簽名很短。前提：兩個大素數p,|p-1以及a1，aq=1 mod p私鑰：隨機選sq公鑰：v，滿足v=a-s mod p2014-06-031517.3 Schnorr算法1.鑒別協議xPeggy選rn計算x=ar mod pVictore隨機選e,-1e2ty計算ayve mod p是否等于x計算y=(r+se) mod p2014-06-031617.3 Schnorr算法2.數字簽名協議Alice選rn計