數(shù)字簽名課件

1、數(shù)字簽名數(shù)字簽名應(yīng)用的一個(gè)實(shí)例例：用戶A通過(guò)網(wǎng)絡(luò)發(fā)送一條消息，要求銀行從用戶A的賬戶上給用戶B支付5000元。銀行如何確認(rèn)消息確是A發(fā)送的（身份認(rèn)證）？事后，如果A否認(rèn)發(fā)送過(guò)該消息，如何認(rèn)證？（消息認(rèn)證-抗抵賴）A否認(rèn)要求銀行支付的是5000元，而說(shuō)是1000元，銀行如何確認(rèn)？（消息認(rèn)證-抗抵賴）銀行如何向公證機(jī)關(guān)提供證據(jù)？以上問(wèn)題可通過(guò)一種安全機(jī)制數(shù)字簽名實(shí)現(xiàn)。手寫簽名和數(shù)字簽名的對(duì)比手寫簽名和數(shù)字簽名的主要差別所簽文件方面的不同。手寫簽名是文件的物理部分，而數(shù)字簽名不是，還要設(shè)法把簽名“捆綁”到文件上。驗(yàn)證方面的不同。手寫簽名是通過(guò)與真實(shí)的手寫簽名比較進(jìn)行驗(yàn)證，手寫簽名容易偽造，不易鑒別。

2、數(shù)字簽名通過(guò)密碼技術(shù)實(shí)現(xiàn)，難以偽造，并通過(guò)一個(gè)公開(kāi)的算法進(jìn)行驗(yàn)證，這樣“任何人”都能驗(yàn)證數(shù)字簽名?！皬?fù)制”方面的不同。手寫簽名不易復(fù)制，復(fù)制后的簽名容易與原文件區(qū)別。相對(duì)而言，數(shù)字簽名容易復(fù)制，復(fù)制后與原文件一樣。數(shù)字簽名方案的構(gòu)成由兩部分組成：帶有陷門的數(shù)字簽名算法和驗(yàn)證算法。設(shè)M是消息的有限集合，S是簽名的有限集合，K是密鑰的有限集合：數(shù)字簽名算法是一個(gè)映射sig：MKS，s=sigk(m)驗(yàn)證算法也是一個(gè)映射ver：MSTrue,False五元組M,S,K,sig,ver稱為一個(gè)簽名方案（算法）。數(shù)字簽名的一個(gè)實(shí)例（公鑰密碼算法簽名）：數(shù)字簽名的執(zhí)行方式數(shù)字簽名的執(zhí)行方式有兩類：直接進(jìn)行

3、數(shù)字簽名利用仲裁的參與進(jìn)行數(shù)字簽名直接進(jìn)行數(shù)字簽名直接數(shù)字簽名過(guò)程只有通信雙方參與，并假定雙方有共享的秘密密鑰，或者接收一方知道發(fā)送方的公開(kāi)密鑰。例如，接受者可以獲得消息發(fā)送者的公鑰，發(fā)送者用自己的私鑰對(duì)整個(gè)消息或者消息散列碼進(jìn)行簽名來(lái)形成數(shù)字簽名。特點(diǎn)：僅涉及通信雙方有效性依賴發(fā)方密鑰的安全性直接進(jìn)行數(shù)字簽名直接數(shù)字簽名的幾種形式(2) AB：M|EA的私鑰H(M)提供了認(rèn)證簽名：H(M) 受到密碼算法的保護(hù)；只有 A 能夠生成 EA的私鑰H(M)。直接進(jìn)行數(shù)字簽名直接數(shù)字簽名的幾種形式(3) AB：EB的公鑰EA的私鑰(M)B的公鑰加密提供了保密性、A的私鑰簽名提供認(rèn)證(4) AB：EKM

4、|EA的私鑰H(M)密鑰K對(duì)稱加密提供了保密性、 A的私鑰簽名提供認(rèn)證。直接進(jìn)行數(shù)字簽名直接數(shù)字簽名的缺點(diǎn)該方法的有效性依賴于發(fā)送方私鑰的安全性：發(fā)送方如果要抵賴簽名，可能會(huì)聲稱其私鑰丟失或被竊。通常需要采用與私鑰安全性相關(guān)的行政管理控制手段來(lái)制止或至少是削弱這種情況，但威脅在某種程度上依然存在。例如：可以要求被簽名的信息包含一個(gè)時(shí)間戳（日期與時(shí)間），以及要求將已泄密的密鑰立即報(bào)告給管理中心。但攻擊依然存在，因時(shí)間戳也可以偽造。例如X的私鑰在時(shí)間T被竊取，攻擊者可以偽造X的簽名并附上時(shí)間T之前的時(shí)間戳。仲裁數(shù)字簽名方案一方案一：對(duì)稱加密，仲裁者可以看到消息內(nèi)容具體過(guò)程如下：（1）SA：M|ES

5、與A的對(duì)稱密鑰IDs|H(M)其中，IDs是S的身份標(biāo)識(shí)。S以ES與A的對(duì)稱密鑰IDs|H(M)作為對(duì)M的簽名，將M及簽名發(fā)往A。（2）AR：EA與R的對(duì)稱密鑰IDs|M|ES與A的對(duì)稱密鑰IDs|H(M)|TA對(duì)ES與A的對(duì)稱密鑰IDs|H(M)解密后驗(yàn)證S的簽名，驗(yàn)證完后加上IDs、時(shí)間戳T一起加密后發(fā)往R。R將消息解密后，結(jié)果保存以備后用。仲裁數(shù)字簽名方案一方案一的仲裁如果出現(xiàn)爭(zhēng)議，R可聲稱自己收到的M的確來(lái)自S，并將EA與R的對(duì)稱密鑰IDs|M|ES與A的對(duì)稱密鑰IDs|H(M)|T發(fā)給A，由A仲裁。A對(duì)EA與R的對(duì)稱密鑰IDs|M|ES與A的對(duì)稱密鑰IDs|H(M)|T解密，再對(duì)ES

6、與A的對(duì)稱密鑰IDs|H(M)進(jìn)行解密，并通過(guò)H(M)和IDs來(lái)判斷是不是S的簽名。仲裁數(shù)字簽名方案二方案二：對(duì)稱加密，仲裁者不能看到消息內(nèi)容S與A、R與A有共享密鑰，S與R之間也有共享密鑰。過(guò)程如下（1）SA：IDs| EKSRM |EKSAIDs|H(EKSRM)S把EKSAIDs|H(EKSRM)作為簽名和M的加密一起發(fā)送給A。（2）AR：EKARIDs|EKSRM|EKSAIDs|H(EKSRM)|TA對(duì)EKSAIDs|H(EKSRM)解密后驗(yàn)證S的簽名（A始終不見(jiàn)明文M）。A驗(yàn)證完后，加上時(shí)間戳T，再用KAR加密后發(fā)往R。如果發(fā)生爭(zhēng)議，解決方法與方案一相同。仲裁數(shù)字簽名方案二方案二對(duì)

7、消息M提供了保密性，但是與方案一仍存在相同的問(wèn)題如下：（1）A和S可以合謀來(lái)否認(rèn)曾經(jīng)發(fā)送過(guò)某個(gè)消息。（2）A和R也可以合謀來(lái)偽造S的簽名。采用基于公鑰密碼體制的簽名方案可解決這一問(wèn)題。仲裁數(shù)字簽名方案三方案三：公鑰加密，仲裁者不能看到消息內(nèi)容過(guò)程如下：（1）SA：IDs|ES的私鑰IDs|ER的公鑰ES的私鑰MS用私鑰對(duì)M加密實(shí)現(xiàn)簽名，用R的公鑰加密實(shí)現(xiàn)機(jī)密性，任何第三方，包括A都不知消息的內(nèi)容。（2）AR：EA的私鑰IDs|ER的公鑰ES的私鑰M|TA收到S的消息，用S的公鑰對(duì)ES的私鑰IDs|ER的公鑰ES的私鑰M進(jìn)行解密，驗(yàn)證S的身份信息IDs。之后， A將S的身份IDs和S對(duì)消息M的簽

8、名加上T，再用自己的私鑰KRA進(jìn)行簽名后發(fā)往R。仲裁數(shù)字簽名方案三方案三的優(yōu)點(diǎn)：在方案執(zhí)行以前，各方都不必有共享的信息，避免合謀行為只要仲裁者的私鑰不被泄露，任何人包括發(fā)送方就不能重放消息對(duì)任何第三方（包括A），S發(fā)往R的消息都是保密的?；诠€密碼體制的典型數(shù)字簽名方案RSA數(shù)字簽名方案RSA數(shù)字簽名方案在許多安全標(biāo)準(zhǔn)中得到廣泛應(yīng)用。ISO/IEC9796和ANSI X9.30-199x以及美國(guó)聯(lián)邦信息處理標(biāo)準(zhǔn)FIPS 186-2將RSA作為推薦的數(shù)字簽名標(biāo)準(zhǔn)算法之一。RSA數(shù)字簽名方案基本算法如下：3.簽名驗(yàn)證過(guò)程假設(shè)用戶B要驗(yàn)證用戶A對(duì)消息M的簽名，用戶計(jì)算M=SAe mod n其中e為

9、公鑰，通過(guò)判斷M與M是否相等來(lái)確認(rèn)簽名是否確是A所產(chǎn)生，如果不是，拒絕該簽名消息。RSA數(shù)字簽名方案關(guān)于簽名方案的幾個(gè)問(wèn)題：方案對(duì)整個(gè)消息簽名，因RSA速度比較慢，當(dāng)消息比較長(zhǎng)時(shí)，簽名與驗(yàn)證過(guò)程也比較慢。可先對(duì)消息進(jìn)行散列計(jì)算，在對(duì)散列值進(jìn)行簽名以提高速度。安全性基于RSA算法自身的安全性，因d私鑰，簽名不可偽造如果消息M1和M2的簽名分別是S1和S2，可以證明Sig(M1M2)=Sig(M1) Sig(M2)，則只要知道M1,M2,S1,S2，就可偽造M1M2（乘積）的簽名S1S2。作業(yè)：設(shè)用戶A的公鑰為（NA=33，eA=17），用戶B的公鑰為（NB=55，eB=23），用戶A應(yīng)用RSA算

10、法向用戶B傳送消息M=10時(shí)，求A發(fā)送的帶簽名的信息以及用戶B對(duì)簽名的驗(yàn)證。6月5日交。EIGamal數(shù)字簽名方案EIGamal數(shù)字簽名方案是T. EIGamal在1985年發(fā)表關(guān)于EIGamal公開(kāi)密鑰密碼時(shí)給出的兩個(gè)方案之一（另外一個(gè)用于加密）。EIGamal數(shù)字簽名方案有很多變體，其中最重要的有美國(guó)NIST于1991年公布的數(shù)字簽名標(biāo)準(zhǔn)（DSS）中使用的數(shù)字簽名算法DSA。EIGamal數(shù)字簽名方案算法描述1.系統(tǒng)初始化對(duì)系統(tǒng)公共參數(shù)和用戶的密鑰進(jìn)行設(shè)置。（1）系統(tǒng)公共參數(shù)選擇大素?cái)?shù)p，使得Zp中的離散對(duì)數(shù)問(wèn)題為困難問(wèn)題；選擇Zp*上的一個(gè)本原根a（2）用戶選擇密鑰每個(gè)用戶選擇一個(gè)隨機(jī)數(shù)

11、x，且1xp-1，計(jì)算y=ax mod p。x作為私鑰用于簽名，y作為公鑰用于驗(yàn)證。公開(kāi)p、a、y，保密私鑰x。EIGamal數(shù)字簽名方案算法描述2.簽名過(guò)程（1）選擇與p-1互素的隨機(jī)數(shù)k，kZp*；（2）簽名方先對(duì)消息M進(jìn)行散列壓縮得到散列碼H(M)，并計(jì)算r=ak mod ps=(H(M)-xr)k-1 mod (p-1)其中x為私鑰。（3）用戶A將(r,s)作為對(duì)消息M的數(shù)字簽名，與消息M一起發(fā)送給接收方。EIGamal數(shù)字簽名方案算法描述3.驗(yàn)證簽名過(guò)程接收方B在收到消息M與簽名(r,s)后進(jìn)行驗(yàn)證。（1）計(jì)算消息M的散列碼H(M)；（2）計(jì)算yrrs mod p和aH(M) mod

12、 p；其中y為簽名方A的公鑰。若yrrsaH(M) mod p，則確認(rèn)簽名有效，否則簽名無(wú)效。EIGamal數(shù)字簽名方案算法描述EIGamal數(shù)字簽名方案對(duì)EIGamal數(shù)字簽名算法的正確性進(jìn)行驗(yàn)證定理1：若(r,s)為合法用戶采用EIGamal數(shù)字簽名算法對(duì)消息M進(jìn)行的簽名，則有yrrs=aH(M) mod p。證明 由于yrrs=(ax)r(ak)s=axraks=axr+ks mod p；又由s=(H(M)-xr)k-1 mod (p-1)；所以有 sk+xr=H(M) mod (p-1)；由模運(yùn)算的性質(zhì)(xy=x(y mod (p) mod p，其中(p)=p-1)有：axr+ks=a

13、H(M) mod p所以有 yrrs=aH(M) mod p。驗(yàn)證算法表述如下：Ver(M,(r,s)=(yrrs mod p=aH(M) mod p)? True: false。EIGamal數(shù)字簽名方案例，設(shè)素?cái)?shù)p=11,a=2是Z11*上的本原根，用戶A選擇私鑰x=8，消息M的散列碼H(M)=5，用戶A選擇的簽名隨機(jī)數(shù)k=9，計(jì)算A用EIGamal數(shù)字簽名算法對(duì)消息M的簽名以及用戶B對(duì)簽名的驗(yàn)證。（1）用戶A計(jì)算公鑰y。y=ax mod p=28 mod 11=3，并把公鑰y=3公開(kāi)。（2）用戶A計(jì)算消息M的簽名。因k=9,(11)=10,gcd(9,10)=1，所以9模10的逆存在，利

14、用歐幾里得算法計(jì)算：k-1 mod (p-1)=9-1 mod 10=9。用戶A計(jì)算： r=ak mod p=29 mod 11=6；s=(H(M)-xr)k-1 mod (p-1)=(5-86)9 mod 10=3EIGamal數(shù)字簽名方案(r,s)=(6,3)，用戶A將(6,3)作為對(duì)消息的簽名，并與消息一起發(fā)送給接收方B。（3）接收方對(duì)消息進(jìn)行驗(yàn)證。計(jì)算yrrs mod p=3663 mod 11=10以及aH(M) mod p=25 mod 11=10兩者相等，則認(rèn)為(6,3)為有效簽名。EIGamal數(shù)字簽名方案EIGamal數(shù)字簽名算法的安全性分析：（1）安全性基于解有限域上的離散

15、對(duì)數(shù)難題：因簽名密鑰x保密，攻擊者要從公開(kāi)驗(yàn)證密鑰y得到x必須求解有限域上的離散對(duì)數(shù)x=loga,py難題。（2） EIGamal數(shù)字簽名算法是一個(gè)非確定性數(shù)字簽名算法，隨機(jī)數(shù)k不同，對(duì)同一個(gè)消息M所產(chǎn)生的簽名不同。（3）在簽名時(shí)使用的隨機(jī)數(shù)k不能被泄露，若泄露，則由s=(H(M)-xr)k-1 mod (p-1)計(jì)算可得 x=(H(M)-ks)r-1 mod (p-1)即得私鑰x，簽名算法被攻破。（4）隨機(jī)數(shù)k不能重復(fù)使用。已證明若能取得兩個(gè)k相同的簽名，則可計(jì)算得到私鑰x。數(shù)字簽名標(biāo)準(zhǔn)DSSDSS是美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)研究所NIST在1994年12月正式頒布的標(biāo)準(zhǔn)FIPS PUB 186標(biāo)準(zhǔn)中

16、采用的數(shù)字簽名算法稱為DSA（Digital Signature Algorithm），而散列算法采用SHA-1。DSA是EIGamal數(shù)字簽名方案的改進(jìn)，安全性仍然基于有限域上計(jì)算離散對(duì)數(shù)的困難性。已在許多數(shù)字簽名標(biāo)準(zhǔn)中推薦使用。DSA數(shù)字簽名算法描述1. DSA的參數(shù)p是素?cái)?shù)，要求2N-1p2N，512N1024，即N的長(zhǎng)度在512到1024bit之間，且N為64的倍數(shù)。q|(p-1)，且q是素?cái)?shù)，2159q2160，即q的長(zhǎng)度為160位。g=h(p-1)/q mod p，其中h是整數(shù)，滿足1h1。隨機(jī)選取整數(shù)x作為私鑰，要求0 xq。計(jì)算用戶的公鑰y=gx mod p。參數(shù)中，p、q以及

17、g是公開(kāi)的系統(tǒng)參數(shù)，x是私鑰，y是公鑰。在第步中，給定x計(jì)算y容易，但是給定y求x困難。DSA數(shù)字簽名算法描述2. 簽名過(guò)程用戶A對(duì)消息M進(jìn)行數(shù)字簽名，發(fā)給用戶B驗(yàn)證。（1）發(fā)送方選取隨機(jī)數(shù)整數(shù)k，0kq，并對(duì)k保密；（2）發(fā)送方計(jì)算r=(gk mod p) mod qs=k-1(H(M)+xr) mod q其中x為私鑰，H(M)為用SHA-1生成散列碼，k-1是k模q的乘法逆，(r,s)即為簽名。為安全起見(jiàn)，每次簽名的k應(yīng)不同，且若r=0或s=0，則另選k重新計(jì)算。DSA數(shù)字簽名算法描述3. 簽名驗(yàn)證過(guò)程B收到消息M,r,s后，首先驗(yàn)證0r,sq，如果通過(guò)則計(jì)算w=s-1 mod q;u1=

18、H(M)w mod q;u2=rw mod q;v=(gu1yu2) mod p mod q。其中y是公鑰。若v=r，則確認(rèn)簽名合法。DSA數(shù)字簽名算法描述簽名驗(yàn)證過(guò)程正確性的證明定理2 設(shè)p和q是素?cái)?shù)且滿足q|(p-1)，h是小于p的正整數(shù)， g=h(p-1)/q mod p，則gq mod p=1，并且假如m=n mod q，則gm=gn mod p。證明：p是素?cái)?shù)且h小于p，故h,p互素。根據(jù)費(fèi)爾馬定理有 gq=(h(p-1)/q)qh(p-1)1 mod p；由于m=n mod q，有m=n+kq其中k為整數(shù)，則gm=gn+kq=gngkq=gn(gq)k=gn mod pDSA數(shù)字簽

19、名算法描述簽名驗(yàn)證過(guò)程正確性的證明定理3 如果(r,s)是合法用戶A采用DSA數(shù)字簽名算法對(duì)消息M的簽名，則一定有v=r成立。證明：考慮v=(gu1yu2 mod p) mod q，而y=gx mod p，有DSA數(shù)字簽名算法描述簽名驗(yàn)證過(guò)程正確性的證明而s=k-1(H(M)+xr) mod q，因此s-1=k(H(M)+xr)-1 mod q，也就是 s-1(H(M)+xr)=k mod q由定理2有所以有DSA數(shù)字簽名算法描述例，假設(shè)q=23，p=47，并取h=17，用戶A選擇了x=10作為自己的簽名私鑰，取k=19，H(M)=15，試計(jì)算消息M的簽名并對(duì)簽名驗(yàn)證。計(jì)算g=h(p-1)/q mod p=17(47