【正文】 ? 如果已知某數(shù)在模 n下的兩個不同的平方根，就可以分解 n 1. B隨機(jī)選一數(shù) x，將發(fā)給 A 2. A（掌握 n的分解）計算 x2mod n 的四個平方根 177。 零知識證明的基本協(xié)議 例 [Quisquater等 1989] 。 GuillouQuisquater身份識別方案 （ 1） A隨機(jī)選擇一個整數(shù) r, 0≤ r≤ n1，并計算 X= rb mod n。假定任何人計算 c都是不可能的。 認(rèn)證過程： （ 1） A將他的秘密口令傳送給計算機(jī) （ 2）計算機(jī)完成口令的單向函數(shù)計算 （ 3）計算機(jī)把單向函數(shù)值和機(jī)器存儲的值進(jìn)行比較。 弱識別是基于非時變的口令或密碼。 （ 5）驗證者 B驗證 X=αy vemod p. Schnorr身份識別方案 針對一般的交互式用戶身份證明協(xié)議，都必須滿足以下三種性質(zhì)： （ 1）完全性 （ 2）健全性或合理性 （ 3）隱藏性 Schnorr身份識別方案 TA將為協(xié)議選擇下列一些參數(shù)： p及 q是兩個大素數(shù)， α1 ,α 2∈Z P為 q階元 ,對系統(tǒng)的所有參加者包括 A， TA保密 c=logα1α2。 TA將證書 C(A)=(ID(A),v,s)發(fā)送給 A。 P可將 r送出，當(dāng) b=0時則 V可通過檢驗而受騙，當(dāng) b=1時，則 V可發(fā)現(xiàn) P不知 y， B受騙概率為 1/2，但連續(xù) t次受騙的概率將僅為 2t ? V無法知道 P的秘密，因為 V沒有機(jī)會產(chǎn)生 (0,1）以外的信息，P送給 V的消息中僅為 P知道 v的平方根這一事實。 x ,177。 （ 6） B驗證 X=veyb mod n. GuillouQuisquater的基于身份的識別協(xié)議 零知識證明 最小泄露證明和零知識證明 ： 以一種有效的數(shù)學(xué)方法 ， 使 V可以檢驗每一步成立 ， 最終確信 P知道其秘密 ， 而又能保證不泄露 P所知道的其他信息 。 TA選擇一個大素數(shù) b（用作一個安全參數(shù)）和一個公開的 RSA加密指數(shù)。驗證者根據(jù) TA的數(shù)字簽名來驗證用戶 A的公開密鑰。 V檢查 P是否每一輪都能正確應(yīng)答。 如：隨機(jī)號碼、時戳、序列號等。TA將證書 C(A)=(ID(A),v,s)發(fā)送給 A。 （ 6） B驗證 X=veyb mod n. GuillouQuisquater識別協(xié)議 Shamir的基于身份的密碼方案的基本思想 基于身份的身份識別方案 基于身份的密碼方案的安全性主要依賴于以下幾個方面 : （ 1）所使用的密碼變換的安全性 （ 2）存儲在密鑰產(chǎn)生中心的特權(quán)信息的保密性 （ 3）在密鑰產(chǎn)生中心給用戶頒布 Smart卡之前所完成的識別檢測的嚴(yán)格性。 Blum[1986] 最早將其用于零知識證明 。 若 A知道一條回路 ， 如何使 B相信他知道 ，且不告訴他具體回路 ？ 零知識證明的基本協(xié)議 (1) A將 G進(jìn)行隨機(jī)置換 ， 對其頂點進(jìn)行移動 ， 并