密碼學(xué)基礎(chǔ) 課件 第6章 數(shù)字簽名

數(shù)字簽名4學(xué)時(shí)

數(shù)字簽名的概念數(shù)字簽名與手寫(xiě)簽名的區(qū)別數(shù)字簽名的特征

數(shù)字簽名的原理數(shù)字簽名分類(lèi)

直接數(shù)字簽名仲裁數(shù)字簽名主要內(nèi)容數(shù)字簽名(DigitalSignature)：以電子化形式，使用密碼方法，在數(shù)字消息中嵌入一個(gè)秘密信息，以驗(yàn)證這個(gè)秘密信息是否正確來(lái)達(dá)到識(shí)別的目的，其實(shí)質(zhì)是一種密碼變換。第一節(jié)數(shù)字簽名概述手寫(xiě)簽名的特點(diǎn)：

(1)簽名不可偽造。簽名中包含了簽名者個(gè)人所特有的一些信息，如寫(xiě)字習(xí)慣、運(yùn)筆方法等，是別人很難仿造的。

(2)簽名不可重用。一個(gè)簽名只能對(duì)一份文件起作用，不可能移到別的不同的文件上。第一節(jié)數(shù)字簽名概述手寫(xiě)簽名

(3)文件內(nèi)容不可改變。在文件簽名后，文件的內(nèi)容就不能再變。

(4)簽名不可抵賴。簽名和文件都是物理的實(shí)體，簽名者不能在簽名后還聲稱他沒(méi)簽過(guò)名。手寫(xiě)簽名應(yīng)用：網(wǎng)絡(luò)中的身份認(rèn)證和消息認(rèn)證。特征：

(1)不可否認(rèn)性：簽名者事后不能否認(rèn)。

(2)可驗(yàn)證性：接收者能驗(yàn)證簽名，而任何其他人都不能偽造簽名。

(3)可仲裁性：當(dāng)雙方發(fā)生爭(zhēng)執(zhí)時(shí)，可以由一個(gè)公正的第三方出面解決爭(zhēng)端。第一節(jié)數(shù)字簽名概述數(shù)字簽名的特征構(gòu)成：簽名者、驗(yàn)證者、密鑰、算法、待簽名消息簽名系統(tǒng)的參數(shù)包括：

——消息空間M，所有可能的消息的集合

——簽名空間S，所有可能的簽名的集合

——密鑰空間K，所有可能的密鑰的集合

——簽名者的密鑰，包括公鑰pK和私鑰sK兩部分

——算法：保密的簽名算法S(.)和公開(kāi)的驗(yàn)證算法V(..)第一節(jié)數(shù)字簽名概述數(shù)字簽名的原理(1)A→B：EKRa(M)提供鑒別與簽名只有A具有KRa傳輸中沒(méi)有被篡改任何第三方可以用KUa驗(yàn)證簽名(1’)A→B：EKUb[EKRa(M)]

提供保密、鑒別與簽名第一節(jié)數(shù)字簽名概述直接數(shù)字簽名（DSS）(2)A→B：M||EKRa[H(M)]

提供鑒別及數(shù)字簽名H(M)受到密碼算法的保護(hù)只有A能夠生成EKRa[H(M)](2’)A→B：EKUb[M||EKRa(H(M))]

提供保密性、鑒別和簽名第一節(jié)數(shù)字簽名概述直接數(shù)字簽名（DSS）驗(yàn)證模式依賴于發(fā)送方的保密密鑰發(fā)送方要抵賴發(fā)送某一消息時(shí)，可能會(huì)聲稱其私有密鑰丟失或被竊，從而他人偽造了他的簽名對(duì)策：要求被簽名的信息包含一個(gè)時(shí)間戳（日期與時(shí)間），并要求將已暴露的密鑰報(bào)告給一個(gè)授權(quán)中心X的某些私有密鑰確實(shí)在時(shí)間T被竊取，敵方可以偽造X的簽名及早于或等于時(shí)間T的時(shí)間戳第一節(jié)數(shù)字簽名概述直接數(shù)字簽名的缺點(diǎn)引入仲裁者所有從發(fā)送方X到接收方Y(jié)的簽名消息首先送到仲裁者A，A將消息及其簽名進(jìn)行一系列測(cè)試，以檢查其來(lái)源和內(nèi)容，然后將消息加上日期并與已被仲裁者驗(yàn)證通過(guò)的指示一起發(fā)給Y。第一節(jié)數(shù)字簽名概述仲裁數(shù)字簽名（ADS）當(dāng)X否認(rèn)時(shí)，通過(guò)以下方法解決糾紛：

Y：向A發(fā)送EKay[IDx||M||EKax[IDx||H(M)]]

A：用Kay恢復(fù)IDx，M，和簽名（EKax[IDx||H(M)]），然后用Kax解密簽名并驗(yàn)證散列碼第一節(jié)數(shù)字簽名概述仲裁數(shù)字簽名（ADS）Y不能直接驗(yàn)證X的簽名，Y認(rèn)為消息正確，只因?yàn)樗鼇?lái)自A。因此，雙方都需要高度相信A:X必須信任A沒(méi)有暴露Kax，并且沒(méi)有生成錯(cuò)誤的簽名

Y必須信任A僅當(dāng)散列值正確并且簽名確實(shí)是X產(chǎn)生的情況下才發(fā)送消息（2）雙方都必須信任A能公正地處理爭(zhēng)議第一節(jié)數(shù)字簽名概述仲裁數(shù)字簽名（ADS）(b)單密鑰加密方式，消息對(duì)仲裁者不可見(jiàn)

(1)XA：IDx||EKxy[M]||EKax[IDx||H(EKxy[M])] (2)AY：EKay[IDx||EKxy[M]||EKax[IDx||H(EKxy[M])]||T]X與Y之間共享密鑰Kxy

第一節(jié)數(shù)字簽名概述仲裁數(shù)字簽名（ADS）(c)公鑰加密方式，消息對(duì)仲裁者不可見(jiàn)

(1)XA：IDx||EKRx[IDx||EKUy(EKRx[M])] (2)AY：EKRa[IDx||EKUy[EKRx[M]]||T]X：對(duì)消息M雙重加密：首先用X的私有密鑰KRx，然后用Y的公開(kāi)密鑰KUy。雙重加密的消息對(duì)A以及對(duì)除Y以外的其它人都是保密的。A：檢查X的公開(kāi)/私有密鑰對(duì)是否仍然有效，是則確認(rèn)消息。第一節(jié)數(shù)字簽名概述仲裁數(shù)字簽名（ADS）(c)與(a)(b)相比具有以下好處：

1、在通信之前各方之間無(wú)須共享任何信息，從而避免了聯(lián)手作弊；

2、即使KRx暴露，只要KRa未暴露，就不會(huì)有時(shí)間戳不正確的消息被發(fā)送；

3、從X發(fā)送給Y的消息的內(nèi)容對(duì)A和任何其他人是保密的。第一節(jié)數(shù)字簽名概述仲裁數(shù)字簽名（ADS）掌握數(shù)字簽名的基本概念理解數(shù)字簽名的特征理解數(shù)字簽名的原理及分類(lèi)方法小結(jié)數(shù)字簽名算法第二節(jié)RSA簽名算法ElGamal簽名算法DSA概述DSA簽名過(guò)程主要內(nèi)容Alice的公開(kāi)密鑰：nA,eA；秘密密鑰：dA；消息m簽名算法：驗(yàn)證算法：Alice要對(duì)秘密信息簽名時(shí)，先用私鑰計(jì)算簽名，再用公鑰加密。第二節(jié)常見(jiàn)簽名算法RSA簽名簽名：對(duì)信息m簽名時(shí)，首先選取隨機(jī)數(shù)k(1≤k≤p-2)，k與p-1互素，計(jì)算

r=gk

modps=k-1(m-xr)modp-1或m=xr+ksmodp-1驗(yàn)證：驗(yàn)證者A驗(yàn)證等式是否成立：gm=yrrs

modp

若正確，則(r，s)為m的合法簽名，否則為非法簽名。第二節(jié)常見(jiàn)簽名算法ElGamal簽名1991年美國(guó)國(guó)家標(biāo)準(zhǔn)局NIST將數(shù)字簽名算法DSA作為其數(shù)字簽名標(biāo)準(zhǔn)(DigitalSignatureStandard，DSS)，DSA是ElGamal數(shù)字簽名算法的變形。使用了安全散列函數(shù)SHA-1，以長(zhǎng)度小于264bits的明文作為輸入，產(chǎn)生160bit的消息摘要作為DSA的輸入。驗(yàn)證簽名時(shí)必須使用相同的散列函數(shù)。數(shù)字簽名算法DSA簽名：對(duì)明文m

(1,q)，簽名者選取隨機(jī)整數(shù)k，1≤k≤p-2且k與p-1互素，計(jì)算r=(gk

modp)modqs=k-1(H(m)+xr)modq其中kk-1modq≡1(r，s)即為消息m的數(shù)字簽名。數(shù)字簽名算法DSA驗(yàn)證：計(jì)算w=s-1modq

u1=H(m)wmodqu2=rwmodqv=[(gu1yu2)modp]modq檢驗(yàn)v=r是否成立。數(shù)字簽名算法DSA簽名者對(duì)消息m=1234簽名：選擇隨機(jī)數(shù)k=50，得k-1(mod101)=99計(jì)算簽名：r=(17050(mod7879)(mod101)=2518(mod101)=94s=(1234+75*94)99(mod101)=97簽名為(1234,94,97)Example數(shù)字簽名算法DSA掌握RSA簽名算法掌握ElGamal簽名算法理解隨機(jī)數(shù)在簽名中的作用理解DSA簽名過(guò)程小結(jié)橢圓曲線簽名第三節(jié)ECDSA算法ECDSA中的閾下信道ECDSA算法的變形主要內(nèi)容ECDSA(EllipticCurveDigitalSignatureAlgorithm)——DSA算法在橢圓曲線上的模擬。1992年，作為NIST所征集的DSS候選算法之一，ScottVanstone提出了ECDSA算法。后來(lái)被各標(biāo)準(zhǔn)化組織廣泛接受，1998年被ISO作為ISO14888-3標(biāo)準(zhǔn)，1999年被ANSI作為ANSIX9.62標(biāo)準(zhǔn)，2000年被IEEE作為IEEE1363-2000標(biāo)準(zhǔn)，同年被FIPS作為FIPS186-2標(biāo)準(zhǔn)。ECDSA簡(jiǎn)介1.方案建立設(shè)U為簽名方，V為驗(yàn)證方：(1）U建立橢圓曲線域參數(shù)T=(p，a，b，G，n，h)；(2）U建立自己的密鑰對(duì)（dU,QU），QU

=dUG；(3）U選擇一個(gè)Hash函數(shù)；(4）U

通過(guò)可靠的方式將所選擇的Hash函數(shù)和建立的橢圓曲線域參數(shù)T傳遞給V。算法描述2.簽名算法(1）選擇臨時(shí)密鑰對(duì)(k，R)，其中R=kG=(xR，yR)與域參數(shù)T相關(guān)(2）令r=xR

(modn)，如果r=0,返回1(3）計(jì)算待簽消息的hash值H=Hash(M)，將H轉(zhuǎn)換成整數(shù)e(4）計(jì)算s

k-1(e+rdU)(modn)，如果s=0,返回1(5）輸出S=(r，s)為數(shù)字簽名算法描述3.驗(yàn)證算法(1）如果r,s

[1,n-1],驗(yàn)證失敗(2）計(jì)算待簽消息的hash值H=Hash(M)，將H轉(zhuǎn)換成整數(shù)e(3）計(jì)算u1

es-1(modn)，u2

rs-1(modn)(4）計(jì)算R=(xR，yR)=u1G+u2QU，如果R=O,驗(yàn)證失敗(5）令v=

xR

(modn)，如果v=r，驗(yàn)證成功，否則驗(yàn)證失敗算法描述對(duì)ECDLP的攻擊ECDSA算法的安全性基于ECDLP問(wèn)題的困難性。如果一種攻擊能夠從簽名者U的公鑰恢復(fù)出私鑰，攻擊者就可以偽造出U對(duì)任何消息的數(shù)字簽名。目前，當(dāng)基點(diǎn)的階為大素?cái)?shù)時(shí)，素?cái)?shù)域上的ECDLP是不可解的。對(duì)密鑰生成的攻擊在密鑰生成過(guò)程中用到了秘密隨機(jī)或偽隨機(jī)數(shù)，不安全的隨機(jī)或偽隨機(jī)數(shù)生成器將直接導(dǎo)致密碼被攻破。攻擊思路對(duì)哈希函數(shù)的攻擊簽名和驗(yàn)證階段使用的哈希函數(shù)必須具備單向和抗沖突的特性。如果哈希函數(shù)不能抵抗沖突，攻擊者可能會(huì)發(fā)現(xiàn)消息(M1;M2)的碰撞，在U對(duì)消息M1簽名后可以偽造出對(duì)消息M2的簽名。基于無(wú)效域參數(shù)和無(wú)效公鑰的攻擊ECDSA的安全性依賴于U使用的有效域參數(shù)，無(wú)效的域參數(shù)對(duì)Pohlig-Hellman攻擊不免疫。U應(yīng)該確保所采用的域參數(shù)是有效的。V在驗(yàn)證之前也應(yīng)該檢驗(yàn)這些參數(shù)的有效性。攻擊思路閾下信道——在密碼協(xié)議中，存在一些特殊的編碼方法或數(shù)學(xué)結(jié)構(gòu)，可以用于傳輸秘密消息。閾下信道主要存在于數(shù)字簽名和認(rèn)證協(xié)議中。簽名者（發(fā)送方）可以將秘密信息隱藏在數(shù)字簽名之中，驗(yàn)證者（接收方）通過(guò)事先約定的某種協(xié)議或參數(shù)恢復(fù)出閾下信息，這種秘密通信方式很難被第三方檢測(cè)到。與一般的加密傳輸相比，閾下信道具有更高的安全性。ECDSA中的閾下信道如果簽名中的附加數(shù)據(jù)量為αbit，其中βbit用來(lái)保證簽名的安全性，則理論上最大可以傳遞α-β

bit的閾下信息。利用了全部或幾乎全部α-βbit的附加數(shù)據(jù)的閾下信道為寬帶閾下信道，只利用了一小部分的為窄帶閾下信道。恢復(fù)閾下信息時(shí)需要簽名者密鑰的方式定義為方式I，不需要的定義為方式Ⅱ。在方式I中，簽名者的密鑰同時(shí)也是該閾下信道的恢復(fù)密鑰。ECDSA中的閾下信道在ECDSA中，由于s

k-1

(e+rdU)(modn)，可得k

s-1

(e+rdU)(modn)，（r,s）和e為簽名對(duì)于驗(yàn)證者V來(lái)說(shuō)，只要事先知道簽名者U的私鑰dU就可以恢復(fù)出k來(lái)。于是以k作為閾下信息，可以實(shí)現(xiàn)方式I的閾下信道。ECDSA中的閾下信道在數(shù)字簽名協(xié)議中補(bǔ)充以下步驟，就能設(shè)計(jì)出閾下通信協(xié)議：信道建立U為發(fā)送方，V為接收方:(1）U執(zhí)行方案建立協(xié)議。建立參數(shù)T,(dU,QU),Hash。(2）U將私鑰dU,秘密傳輸給V。ECDSA中的閾下信道閾下信息隱藏(1）U對(duì)秘密消息編碼，得到一整數(shù)k。(2）U建立臨時(shí)密鑰對(duì)(k，R)，其中R=kG=(xR，yR)和域參數(shù)T相關(guān)。(3）U執(zhí)行以上簽名算法。ECDSA中的閾下信道閾下信息恢復(fù)(1）V執(zhí)行驗(yàn)證協(xié)議。(2）V計(jì)算

k

s-1(e+rdU)(modn)，恢復(fù)閾下信息。(3)V對(duì)k解碼恢復(fù)原始的秘密信息。ECDSA中的閾下信道ECDSA算法中的簽名附加數(shù)據(jù)量為（logn+logp）bit，而閾下信息k為lognbit，該信道是一種寬帶信道。按照目前對(duì)橢圓曲線參數(shù)的安全要求，通過(guò)這個(gè)信道可傳輸192bit以上的閾下信息。ECDSA中的閾下信道簽名算法(1）選擇臨時(shí)密鑰對(duì)(k，R)，其中R=kG=(xR，yR)和域參數(shù)T相關(guān)。(2）令r=xR(modn)，如果r=0,返回1。 (3）計(jì)算待簽名消息的hash值H=Hash(M)，將H轉(zhuǎn)換成整數(shù)e。(4）計(jì)算s

dU-1(rk-e)(modn)，如果s=0,返回1。(5）輸出S=(r，s)為數(shù)字簽名。ECDSA算法的變形一驗(yàn)證算法(1）如果r,s

[1,n-1],驗(yàn)證失敗。(2）計(jì)算待簽消息的hash值H=Hash(M)，將H轉(zhuǎn)換成整數(shù)e(3）計(jì)算u1

er-1(modn),u2

sr-1(modn)(4）計(jì)算R=(xR，yR)=u1G+u2QU，如果R=O,驗(yàn)證失敗。(5）令v=

xR(modn)，如果v=r,驗(yàn)證成功，否則驗(yàn)證失敗。這個(gè)改進(jìn)方案中，可以預(yù)計(jì)算dU-1，將計(jì)算結(jié)果存儲(chǔ)下來(lái)作為簽名參數(shù)，在每次簽名時(shí)模乘dU-1即可，于是模逆轉(zhuǎn)化為模乘，運(yùn)算量將減小。ECDSA算法的變形一簽名算法(1）選擇臨時(shí)密鑰對(duì)(k，R)，其中R=kG=(xR，yR)和域參數(shù)T相關(guān)；(2）令r=xR(modn)，如果r=0,返回1；(3）計(jì)算待簽名消息的hash值H=Hash(M)，將H轉(zhuǎn)換成整數(shù)e；(4）計(jì)算s

k(e+rdU)-1(modn)，如果s=0,返回1；(5）S=(r，s)作為數(shù)字簽名。ECDSA算法的變形二驗(yàn)證算法(1)如果r,s

[1,n-1],驗(yàn)證失敗；(2)計(jì)算待簽名消息的hash值H=Hash(M)，將H轉(zhuǎn)換成整數(shù)e；(3)計(jì)算u1

es(modn),u2

rs(modn)；(4)計(jì)算R=(xR，yR)=u1G+u2QU，如果R=O,驗(yàn)證失敗。(5)令v=

xR(modn)，如果v=r,驗(yàn)證成功，否則驗(yàn)證失敗。ECDSA算法的變形二掌握ECDSA簽名過(guò)程理解閾下信道的含義理解如何在ECDSA中利用閾下信道進(jìn)行信息隱藏了解ECDSA的兩種變形小結(jié)第四節(jié)盲簽名三、盲簽名的原理及典型算法(重點(diǎn))二、盲簽名的產(chǎn)生背景----電子投票主要內(nèi)容：一、盲簽名的基本概念盲簽名

盲簽名:是一類(lèi)特殊的數(shù)字簽名,消息持有者希望簽名者對(duì)他的消息作數(shù)字簽名，但又不想讓簽名看到消息的真實(shí)內(nèi)容。一、盲簽名的基本概念1、遠(yuǎn)程匿名投票20世紀(jì)80年代，密碼學(xué)家DavidChaum就建立過(guò)一個(gè)遠(yuǎn)程匿名投票模型設(shè)立一個(gè)選舉委員會(huì)，其職責(zé)為：

規(guī)定選票格式。

確認(rèn)選民身份。

統(tǒng)計(jì)選票。二、電子投票問(wèn)題（盲簽名產(chǎn)生的背景）條件：所有投票人散居各城市，無(wú)法集中，利用普通郵政系統(tǒng)投票。選民選委會(huì)資格審查票數(shù)統(tǒng)計(jì)

①②⑤③④

1、遠(yuǎn)程匿名投票

二、電子投票問(wèn)題（盲簽名產(chǎn)生的背景）用電子手段解決以下三個(gè)關(guān)鍵問(wèn)題：（1）如何使選委會(huì)看不到選票內(nèi)容？（2）選舉委員會(huì)如何蓋章？（3）選民如何確認(rèn)收回的選票沒(méi)有被做上記號(hào)？2、電子投票二、電子投票問(wèn)題（盲簽名產(chǎn)生的背景）1、盲簽名的特性（1）簽名人看不到所簽的“文件內(nèi)容”。（2）簽名人無(wú)法建立文件與他的簽名之間的聯(lián)系。三、盲簽名的原理及算法消息持有者簽名者M(jìn)S=S(M)M=B(M)S=B-1(S

)

2、盲簽名的原理盲化盲簽名解盲

消息持有者希望簽名者對(duì)他的消息作數(shù)字簽名，但又不想讓簽名者看到消息的真實(shí)內(nèi)容。三、盲簽名的原理及算法1.不可偽造性除了簽名者本人外，任何人都不能以他的名義生成有效的盲簽名。2.不可抵賴性簽名者簽署了某個(gè)消息后將無(wú)法否認(rèn)自己對(duì)消息的簽名。3.盲性簽名者不可能得到消息的具體內(nèi)容。4.不可跟蹤性一旦消息的簽名公開(kāi)后，簽名者不能確定自己何時(shí)簽署的這條消息。一個(gè)好的盲簽名算法應(yīng)該具有以下的性質(zhì)：

三、盲簽名的原理及算法3、基于RSA密碼的盲簽名算法（1）參數(shù)選取（同RSA公鑰密碼）：選定p,q為大素?cái)?shù)，計(jì)算n=pq。選取秘密密鑰d，要求gcd(d,φ(n))=1。計(jì)算e,滿足de=1modφ(n)。

e,n公開(kāi)，其它參數(shù)均保密。三、盲簽名的原理及算法RSA數(shù)字簽名過(guò)程AliceBobn,epublicdprivates≡md

modngcd(m,n)=1m≡se

modnsSetp1:選定M，隨機(jī)數(shù)R。計(jì)算M

=ReM

modn簽名者消息持有者Setp2:計(jì)算S

=M

d

modnStep3:S=R-1S

modn

=M

dmodnStep4:驗(yàn)證

Semodn？=M（2）簽名算法三、盲簽名的原理及算法（3）分析MM

(M,S)(M

，S

)

簽名人對(duì)簽的“文件內(nèi)容”是看不見(jiàn)的。即使公布文件內(nèi)容，簽名人也不能把文件與他所作的簽名聯(lián)系起來(lái)。

三、盲簽名的原理及算法（4）與普通RSA簽名比較MS=M

dmodnRSA簽名RSA盲簽名M?=S

emodnS

=M

dmodnM?=S

emodnMM

S=R-1S

modn三、盲簽名的原理及算法1.密鑰的長(zhǎng)度；2.盲簽名的長(zhǎng)度；3.盲簽名的算法和驗(yàn)證算法。盲簽名的可操作性和實(shí)現(xiàn)速度取決于：三、盲簽名的原理及算法4、盲簽名技術(shù)的應(yīng)用現(xiàn)狀（1）匿名電子投票系統(tǒng)（2）電子商務(wù)系統(tǒng)中的匿名支付

Microsoft公司的eWallet系統(tǒng)。三、盲簽名的原理及算法主要內(nèi)容：（1）盲簽名