數(shù)字簽名(新)

1、第第7章章 數(shù)字簽名數(shù)字簽名RSA簽名體制二三Rabin簽名體制一 數(shù)字簽名的基本概念一ElGamal簽名體制四五Schnorr簽名體制六DSS簽名體制七ESIGN簽名體制八十十一Okamoto簽名體制離散對數(shù)簽名體制其它簽名體制簡介一 消息認(rèn)證碼的基本用途十二一 雜湊算法/加密/簽名結(jié)合應(yīng)用方案十三第第7章章 數(shù)字簽名數(shù)字簽名九OSS簽名體制一、數(shù)字簽名的基本概念一、數(shù)字簽名的基本概念 收方能夠確認(rèn)或證實發(fā)方的簽名，但不能偽造，簡記為R1-條件。 發(fā)方發(fā)出簽名的消息給收方后，就不能再否認(rèn)他所簽發(fā)的消息，簡記為S-條件。 收方對已收到的簽名消息不能否認(rèn)，即有收報認(rèn)證，簡記為R2-條件。 第三者

2、可以確認(rèn)收發(fā)雙方之間的消息傳送，但不能偽造這一過程，簡記為T-條件。1. 數(shù)字簽名與消息認(rèn)證的區(qū)別數(shù)字簽名與消息認(rèn)證的區(qū)別 當(dāng)收發(fā)者之間沒有利害沖突時，這對于防止第三者的破壞已經(jīng)足夠了。 收方能夠驗證消息發(fā)送者身份是否被篡改； 收方能夠驗證所發(fā)消息內(nèi)容是否被篡改。 當(dāng)收發(fā)雙方存在利害沖突時，單純用消息認(rèn)證技術(shù)就無法解決他們之間的糾紛。必須采用數(shù)字簽名技術(shù)。 數(shù)字簽名能確定消息來源的真實性 數(shù)字簽名能保證實體身份的真實性 數(shù)字簽名是不可否認(rèn)的。2. 數(shù)字簽名與公鑰加密的區(qū)別數(shù)字簽名與公鑰加密的區(qū)別 公鑰加密A采用B的公開密鑰對信息加密，A將密文發(fā)給B；B用自己的私鑰對收到的密文解密，恢復(fù)出明文。

3、 數(shù)字簽名A采用自己的私鑰采用自己的私鑰對消息m簽名，A將m和簽名發(fā)給B；B收到A的簽名后，采用采用A的公鑰的公鑰來驗證簽名的有效性；一個簽名的消息很可能在多年之后才驗證其真實性；數(shù)字簽名可能需要多次驗證；對數(shù)字簽名的安全性和防偽造要求很高；要求簽名速度比驗證速度更快。3. 數(shù)字簽名的分類數(shù)字簽名的分類 按照消息是否被壓縮分類 對整體消息進行簽名； 對壓縮的消息進行簽名。 按照消息/簽名的對應(yīng)關(guān)系劃分 確定性（確定性（deterministic）數(shù)字簽名：）數(shù)字簽名：消息與簽名一一對應(yīng)，對同一消息的簽名永不變化，如RSA和Rabin算法； 隨機化（隨機化（randomized）或概率式數(shù)字簽名

4、）或概率式數(shù)字簽名：對同一消息的簽名是變化的。因此，此類簽名取決于算法中的隨機參數(shù)的取值，如ElGamal算法。4. 簽名體制的構(gòu)成簽名體制的構(gòu)成m 由兩部分構(gòu)成m 簽名算法（signature algorithm）m 驗 證 算 法 （ v e r i f i c a t i o n algorithm）m 安全性約定m 簽名算法或簽名密鑰是秘密的，只有簽名人掌握；m 驗證算法應(yīng)當(dāng)公開，以便于他人進行驗證。Digital SignatureReferencemCSC1720 Introduction to InternetmAll copyrights reserved by C.C. Ch

5、eung 2003.105. 簽名體制的數(shù)學(xué)表示簽名體制的數(shù)學(xué)表示m 一個簽名體制可由量(M, S, K, V)來表示 m M是明文空間m S是簽名的集合m K是密鑰空間m V是驗證函數(shù)的值域，由真、偽組成。m 對于每一個kK，m Mm簽名算法：s = Sigk(m) Sm驗證算法：Verk(s, m) 真，偽 m 簽名體制的安全性在于：m從m和s難于推出簽名者的私鑰k；m很難偽造另外一個消息m，使Verk(s, m) 真 。二、二、RSA數(shù)字簽名體制數(shù)字簽名體制m 令 , p1和p2是大素數(shù)；m 令m, sZn（整數(shù)域）m 選e，并計算出d，使m 將n, e公開（公鑰）, 將p1、p2和d保

6、密（私鑰）。m 對mZn，定義簽名：s = Sigk(m) =md mod n 給定m, s，驗證： m se mod n ?)(mod1ned21ppn體制參數(shù)簽名過程驗證過程13.13mSigning and Verifyingm13.5.1 ContinuedmFigure 13.7 RSA digital signature scheme13.14mRSA Signature on the Message Digestm13.5.1 ContinuedmFigure 13.8 The RSA signature on the message digestRSA簽名體制的安全性簽名體制的

7、安全性m 顯然，由于只有簽名者知道私鑰d，根據(jù)RSA體制知，其他人不可能偽造簽名；m 易于證實m, s是否是合法的消息m, 簽名s對，只要計算 m se mod n 即可。 RSA體制的安全性依賴于n=p1p2分解的困難性。討論安全性四、四、ElGamal簽名體制簽名體制m p：一個大素數(shù)，可使Zp中求解離散對數(shù)為困難問題；m g：是群ZP*的一個生成元或本原元素；m M：消息空間，為ZP*；m S：簽名空間，為ZP-1；m x：用戶秘密鑰，xZP*m ygx mod pm p, g, y為公鑰，x為秘密鑰。m 選擇秘密隨機數(shù)k ZP*，m Mm 計算：H(m)m 計算：r=gk mod pm

8、 計算：s=H(m)-xrk-1 mod (p-1) 簽名為Sigk(m)=(r, s)，將m和(r, s)送給對方。體制參數(shù)簽名過程ElGamal簽名體制簽名體制m 收信人收到m和(r, s) ；m 計算：H(m)；m 驗證：Verk(H(m), (r, s)=真 yrrs gH(m) mod p； 左邊： yrrs gxrgsk mod p g(rx+sk) mod p 而(rx+sk) H(m) mod p-1 故： yrrs gH(m) mod pm 選擇p=467, g=2, x=127, 則有y gx 2127 132 mod 467m 若待送消息m的雜湊值H(m)=100，選隨機

9、數(shù)k=213 注意：(213, 466)=1, 且213-1 mod 466=431m 則：r=2213=29 mod 467, s=(100-127*29)431=51 mod 466。m 驗證：(1)收信人計算H(m)=100， (2)驗證：132292951=189 mod 467 2100=189 mod 467驗證過程例子ElGamal簽名體制的安全性簽名體制的安全性m在不知消息,簽名對時，偽造簽名相當(dāng)于求離散對數(shù)；m如果攻擊者掌握了同一隨機數(shù)k下的兩個消息m1, m2的合法簽名（r1, s1）（r2, s2），就會構(gòu)造如下的方程： m1=r1x+s1k m2=r2x+s2k 可見：

10、攻擊者解此方程可以求出x和k。要確保此簽名體制的安全性，就必須保證每次簽名時，選擇不同的隨機數(shù)k。討論安全性五、五、Schnorr簽名體制簽名體制m p, q：大素數(shù), q|p-1, 確保Zp中求解離散對數(shù)為困難問題；m g：是Zp中乘群ZP*的一個元素，且gq1 mod p；m M：消息空間，為ZP*；m S：簽名空間，為ZP* ZP-1；m x：用戶秘密鑰，1xqm y：用戶公鑰，ygx mod pm p, q, g, y為公鑰，x為秘密鑰。m 用戶選擇秘密隨機數(shù)kZq， m Mm 計算：w=gk mod p m 計算：r=H(w|m)m 計算：s=k+xr mod p 簽名：Sigk(m

11、)=(r, s)作為簽名，將m和(r, s)送給對方。體制參數(shù)簽名過程13.20m13.5.3 Schnorr Digital Signature SchememFigure 13.11 General idea behind the Schnorr digital signature schemem收信人收到消息m和簽名(r, s)m計算：H(m)m 計算：w=gsy-r mod pm 計算：H(w|m)m 驗證H(w|m)=r ？即 Ver(y, (e, s), m)=真Schnorr簽名驗證：m在ElGamal體制中，g為Zp的本原元素；在Schnorr體制中，g為Zp*中的子集Zq*的

12、本原元，它不是Zp* 的本原元。m Schnorr的簽名長度要比ElGamal短，由|q|及|H(m)|決定。m w=gk mod p可以預(yù)先計算，簽名只需1次乘法和1次加法，所以簽名速度非常快，適用于智能卡應(yīng)用。 由于Schnorr簽名較短，其安全性要比ElGamal簽名差 。Schnorr簽名體制的安全性簽名體制的安全性Schnorr與ElGamal的區(qū)別安全性六、六、DSS簽名體制簽名體制m 1991年8月由NIST公布m 1994年5月19日由NIST正式公布m 1994年12月1日正式成為美國聯(lián)邦信息處理標(biāo)準(zhǔn)m 它是基于ElGamal和Schnorr簽名體制設(shè)計的m 該簽名體制有較好

13、的兼容性和適用性，已經(jīng)成為網(wǎng)絡(luò)安全體系的基本構(gòu)件之一。m DSA是DSS簽名標(biāo)準(zhǔn)中所采用的數(shù)字簽名算法； 此算法由D. W. Kravitz設(shè)計。 DSS概況什么是DSADSS簽名算法簽名算法DSAm p：大素數(shù), , 512L1024；m q：(p-1)的素因子，且2159q2160，即字長160bm g：gh(p-1)/q mod p，且1h1m x：選擇用戶私鑰，1xqm y：計算用戶公鑰，ygx mod pm p, q, g, y為公鑰，x為私鑰。m 用戶選擇秘密隨機數(shù)k，0kqm 計算：H(m)m 計算：r=(gk modp)mod qm 計算：s=k-1(H(m)+xr) mod

14、qm 簽名：Sigk(m)=(r, s)，將m和(r, s)送給對方。LLp212體制參數(shù)簽名過程DSS簽名算法簽名算法DSAm 收信人收到m和(r, s) ；m 計算：H(m)；m 計算：w=s-1 mod qm 計算：u1=H(m)w mod qm 計算：u2=rw mod q m 計算：v=(gu1yu2) mod p mod qm 驗證：v r ? 證明： v=(gu1yu2) mod p mod q =g H(m)wyrw mod p mod q =g H(m)wgxrw mod p mod q =gH(M)+xrw mod p mod q 而： H(m)+xrw = H(m)+xr

15、s-1=k mod q 所以：v=gk mod q= r 驗證過程DSS簽名框圖簽名框圖p q g rsxkDSS簽名驗證框圖簽名驗證框圖y q g rvDSS簽名算法的公眾反應(yīng)簽名算法的公眾反應(yīng)m RSA公司想以RSA算法為標(biāo)準(zhǔn)m RSA指出：RSA可以加密，而DSA不能用于加密；m DSA是由NSA開發(fā)的，可能設(shè)有陷門；m DSA的簽名驗證速度比RSA慢，不適合聯(lián)機在線驗證；m RSA是一個事實上的標(biāo)準(zhǔn)，而DSS與現(xiàn)行標(biāo)準(zhǔn)不相容；m DSA未經(jīng)公開選擇，還沒有足夠的時間進行分析證明；m DSA可能侵犯了其他專利，如Schnorr簽名算法，Diffie-Hellman的密鑰分配算法；m DS

16、S中模數(shù)為512b所限定的密鑰量太小，現(xiàn)已經(jīng)改為凡是512-1024b中可被64除盡的數(shù)，均可供使用。RSA公司反應(yīng)強烈DSS簽名算法的實現(xiàn)速度簽名算法的實現(xiàn)速度14sOff card14sN/A0.035s15s16s1.5s注：注：PC機80386/33M，模皆為512b七、七、ESIGN簽名體制簽名體制m n=p2q：大合數(shù), 公開鑰；m p, q：兩個大素數(shù)，作為秘密鑰；m M：消息空間m S：簽名空間m k：安全參數(shù)（它的作用后面討論） m 用戶選擇秘密隨機數(shù)r，0rpqm 計算：H(M)m 計算：w=大于等于(H(M)-rk) mod n/pq的最小整數(shù)m 計算：s= r + (w

17、/krk-1) mod p pq Sigk(M, k)=s 作為簽名，將M和s送給對方。體制參數(shù)簽名過程m 收信人收到M和s；m 計算：H(M)；m 計算：srk mod nm 計算：a，它是大于等于2n/3的最小整數(shù)m 驗證：Verk(H(M), s)=真 H(M) sk 且sk mod n H(M)+2am 此算法可以采用預(yù)計算來提高簽名速度 (1) 發(fā)方預(yù)計算：u=rk mod n; v=1/(krk-1) mod p (2) 計算w：w=大于等于(H(M)-u) mod n/pq的最小整數(shù) 計算s：s = r + (wv mod p) pq m 通過預(yù)計算，可以使簽名速度提高10倍。

18、k=2,3時, 被破解。作者建議k=8,16,32,64,128,256,1024 ESIGN簽名算法簽名算法驗證過程討論mESIGN在美國、加拿大、英國、法國、德國和意大利申請了專利。m 分析表明，此算法要比RSA，ElGamal及DSA速度快。m 其安全性與RSA或Rabin體制同樣安全。ESIGN簽名算法簽名算法討論八、八、Okamoto簽名體制簽名體制m p, q：大素數(shù), p至少為512bit；m q: (p-1)的素因子，且q長約140 bitm g1, g2: 是全局公鑰，與q同長的隨機數(shù); m s1, s2: 是秘密鑰，與q同長的隨機數(shù);m M：消息空間，MZP*；m S：簽名

19、空間，為ZP* ZP-1；m v：用戶公鑰，vg1-s1 g2-s2 mod pm p, q, g1, g2, v為公鑰， s1, s2為秘密鑰。 m 用戶選擇兩秘密隨機數(shù)r1, r2，0r1, r2qm 計算：e=H(g1r1 g2r2 mod p, M)m 計算：y1=(r1 + es1) mod qm 計算：y2=(r2 + es2) mod q Sigk(M, k)=S=(e, y1, y2) 為簽名，將M和S 送給對方。體制參數(shù)簽名過程m 收信人收到M和S=(e, y1, y2) ；m 驗證：Verk(M, e, y1, y2)=真 H(g1y1 g2y2 vemod p，M) =

20、e g1y1 g2y2 vemod p= g1 (r1 + es1) g2 (r2 + es2) (g1-s1 g2-s2)e mod p = g1 r1 g2 r2 mod p 所以： H(g1y1 g2y2 vemod p，M) = H(g1r1 g2r2 mod p, M) = eOkamoto簽名算法簽名算法驗證過程討論九、九、OSS簽名體制簽名體制m n：大整數(shù)（不必知道其分解）；m k： 隨機數(shù)，滿足(k, n)=1m h：滿足h= -k-2 mod nm M：消息空間，MZP*；m S：簽名空間，為ZP* ZP*；m h, n為公鑰，k為秘密鑰。 m 用戶選擇隨機數(shù)r，滿足 (r

21、, n)=1 m 計算：s1=(M/r+r)/2 mod n，m 計算：s2=k(M/r-r)/2 mod nSigk(M, k)=S=(s1, s2)作為M的簽名，將M和(s1, s2)送給對方。體制參數(shù)簽名過程m 收信人收到M和=(s1, s2) ；m 計算：M= s12+hs22 mod n；m 驗證：Verk(H(M), r, s)=真 M M ； 因為： M=(M/r+r)/2 )2 +h (k(M/r-r)/2)2 mod n =M2/r2+2M+r2-M2/r2+2M-r2/4 mod n =4M/4 mod n =M mod n OSS簽名算法簽名算法Ong-Schnorr-S

22、hamir驗證過程OSS簽名算法簽名算法m 對于以上由二次或三次多項式構(gòu)造的簽名，已被證明是不安全的；m 四次多項式方案也已被攻破。m Okamoto曾提出一種補救措施。 ESIGN是由Okamoto和Sharaishi在OSS的基礎(chǔ)上提出的數(shù)字簽名方案。 討論十、離散對數(shù)簽名體制十、離散對數(shù)簽名體制m p：大素數(shù)m q: (p-1)的大素因子m g：g ZP*，且滿足gq=1 mod pm M：消息空間，MZP*；m S：簽名空間；m x：用戶秘密鑰，1xqm y：用戶公鑰，ygx mod pm p, q, g, y為公鑰，x為秘密鑰。m 用戶選擇一次性秘密隨機數(shù)k，0kqm 計算：H(m)

23、m 計算：r=gk mod pm 簽字方程：ak = b + cx mod q Sigk(m)=(r, s)作為簽名，將m和(r, s)送給對方。體制參數(shù)簽名過程所有以上的簽名體制均可看成其一個特例！所有以上的簽名體制均可看成其一個特例！簽名的驗證過程簽名的驗證過程 收端收到消息m和簽名(r, s)后，可以按照以下驗證方程檢驗： Ver(M, r, s)=真 ragbyc mod q簽名算法中簽名算法中a, b, c的取值的取值rs H(m)rk=s+H(m)x mod qrH(m)srk=H(m)+sx mod qsr H(m)sk=r+H(m)x mod q sH(m)rsk=H(m)+r

24、x mod qH(m)srH(m)k=s+rx mod qH(m)rsH(m)k=r+sx mod q簽名方程簽名方程ak=b+cx對應(yīng)的簽名算法對應(yīng)的簽名算法rk=s+H(m)x mod qrr=gsyH(m) mod pYen, Laihrk=H(m)+sx mod qrr=gH(m)ys mod pAgnew, Yenrk=r+H(m)x mod qrr=gH(m)ys mod psk=H(m)+rx mod qrs=gH(m)yr mod pElGamal, DSAH(m)k=s+rx mod qrH(m)=gsyr mod pSchnorr, NybergH(m)k=r+sx mod

25、 qrH(M)=grys mod p十一、其他簽名體制十一、其他簽名體制不可否認(rèn)簽名不可否認(rèn)簽名為什么需要不可否認(rèn)簽名？普通簽名可以精確地被復(fù)制，適合公開聲明之類文件的散發(fā)；但是對于個人或公司信件，特別是有價值文件的簽名，如果也可以隨意復(fù)制和散發(fā)，就可能造成災(zāi)難。這類簽名要求在簽名者合作下，才能驗證簽名。無簽名者合作，不可能驗證簽名，從而可以防止復(fù)制和散布他所簽的文件。這一性質(zhì)可以可以用于知識產(chǎn)權(quán)的保護等，在電子出版物的知識產(chǎn)權(quán)保護中將大顯身手。產(chǎn)權(quán)擁有者可以控制產(chǎn)品的發(fā)布。1989年Chaum和Antwerpen提出不可否認(rèn)簽名的概念其他簽名體制其他簽名體制防失敗簽名防失敗簽名（Fail-S

26、top Signature）這是一種強化安全性的數(shù)字簽名，可防范有充足計算資源的攻擊者。當(dāng)A的簽名受到攻擊，甚至在分析出A的私鑰的情況下，攻擊者也難以偽造A的簽名。同時，A也難以對自己的簽名進行抵賴。它是一種一次性簽名方案，即給定密鑰只能簽署一個消息。1991年由Pfitzmann和Waidner提出其他簽名體制其他簽名體制盲簽名盲簽名（Blind Signature）對于一般的數(shù)字簽名來說，簽名者總是要先知道文件內(nèi)容后才簽名，這是正常的應(yīng)用情形。但是有時需要某人對一個文件簽名，但又不想讓他知道所簽署的文件內(nèi)容。在選舉投票和數(shù)字貨幣協(xié)議中，會用到此簽名體制。盲簽名在電子商務(wù)系統(tǒng)中，有重要的應(yīng)用

27、。1983年由Chuam最先提出其他簽名體制其他簽名體制群簽名群簽名（Group Signature）只有群中的成員才能代表群體簽名。接收到簽名的人可以用公鑰驗證群簽名，但不可能知道由群體中的那個成員所簽。發(fā)生爭議時，由群體中的成員或可信賴機構(gòu)識別群簽名的簽名者。這類簽名可以用于項目投標(biāo)。例如：所有參有投標(biāo)的公司組成一個群體，且每個公司都匿名地采用群簽名對自己的標(biāo)書簽名。當(dāng)選中了一個滿意的標(biāo)書后，招標(biāo)方就可以識別出簽名的公司，而其他標(biāo)書仍保持匿名。中標(biāo)方若想反悔已無濟于事，因為在沒有他參與的情況下，仍可以正確地識別出簽名人是誰。1991年由Chaum和van Heyst最先提出其他簽名體制其他簽名體制代理簽名代理簽名（Proxy Signature）代理簽名就是某人授權(quán)其代理進行的簽名，在委托簽名時，簽名密鑰不交給代理人。代理簽名有如下幾個特性： l不可區(qū)分性：代理簽名與委托人的簽名不可區(qū)分；l不可偽造性：只有委托人和代理人可以建立合法的簽名；l代理簽名的差異