網(wǎng)絡(luò)與信息安全第5章數(shù)字簽名

第5章Hash函數(shù)與數(shù)字簽名

網(wǎng)絡(luò)信息安全

1第5章Hash函數(shù)與數(shù)字簽名5.6數(shù)字簽名概念5.7RSA數(shù)字簽名體制5.8ElGamal數(shù)字簽名體制5.9其它數(shù)字簽名方案5.10數(shù)字簽名標(biāo)準(zhǔn)5.11應(yīng)用25.6數(shù)字簽名概念在政治、軍事、外交、商業(yè)和日常生活中，人們經(jīng)常需要對紙質(zhì)材料進(jìn)行簽名。簽名起到確認(rèn)、核準(zhǔn)、生效和負(fù)責(zé)任等多種作用。隨著計算機(jī)網(wǎng)絡(luò)技術(shù)的發(fā)展，電子商務(wù)、電子政務(wù)和電子金融等系統(tǒng)得到廣泛應(yīng)用，人們需要通過網(wǎng)絡(luò)信息傳輸對電子的文件、契約、合同、信件和張單等進(jìn)行數(shù)字簽名以替代手寫簽名。35.6數(shù)字簽名概念簽名是證明當(dāng)事人的身份和數(shù)據(jù)真實性的一種信息。在傳統(tǒng)的以書面文件為基礎(chǔ)的事物處理中，采用書面簽名的形式，如手簽、手印和印章等。書面簽名得到司法部門的支持，具有一定的法律意義45.6數(shù)字簽名概念在以計算機(jī)文件為基礎(chǔ)的現(xiàn)代事物處理中，應(yīng)采用電子形式的簽名，即數(shù)字簽名（digitalsignature）。數(shù)字簽名的目的是提供一種手段，使得一個實體把他的身份與某個信息捆綁在一起。一個信息的數(shù)字簽名實際上是一個數(shù)，它僅僅依賴于簽名者的密鑰和被簽名的消息。10011100010100011000sigK密鑰K55.6.1數(shù)字簽名的基本概念（1）消息空間:由所有任意長度消息組成的集合

（2）簽名空間:由所有簽名組成的集合。簽名長度不超過n。（3）密鑰空間:（4）sigK稱為簽名算法（signingalgorithm）

一個數(shù)字簽名體制是一個滿足以下條件的五元組:65.6.1數(shù)字簽名的基本概念（5）verK稱為驗證算法（verificationalgorithm）（6）

則將數(shù)據(jù)對（x，y）稱為消息x的一個數(shù)字簽名，或直接把y稱為消息x的數(shù)字簽名75.6.1數(shù)字簽名的基本概念數(shù)字簽名基本要求對每一個密鑰K,sigK和verK應(yīng)該是多項式時間函數(shù)verK是公開的函數(shù),而sigK是保密的

給定一個消息x,除了發(fā)送者本人以外,任何其他人找到滿足verK(x,y)為真的數(shù)字簽名y,應(yīng)該是計算上不可行的如果攻擊者能夠找到滿足verK(x,y)的數(shù)據(jù)對(x,y),而發(fā)送者事先又沒有對x簽名,則稱y是偽造(forgery)的數(shù)字簽名。

數(shù)字簽名算法必須滿足的條件簽名者事后不能否認(rèn)自己的簽名；其他人不能偽造簽名；當(dāng)通信雙方為簽名真?zhèn)伟l(fā)生爭執(zhí)時,可以由第三方解決爭端85.6.1數(shù)字簽名的基本概念手寫簽名與數(shù)字簽名的區(qū)別手寫簽名是所簽文件的物理組成部分，數(shù)字簽名必須與所簽文件捆綁在一起。手寫簽名通過與標(biāo)準(zhǔn)簽名進(jìn)行比較或檢查筆跡來驗證，數(shù)字簽名是通過驗證算法來驗證。手寫簽名容易偽造，好的數(shù)字簽名算法應(yīng)該使偽造簽名十分困難。手寫簽名不易復(fù)制。數(shù)字簽名是一個二進(jìn)制串，容易復(fù)制。所以必須防止數(shù)字簽名重復(fù)使用。95.6.1數(shù)字簽名的基本概念簽名算法進(jìn)行分類按應(yīng)用目的普通數(shù)字簽名特殊目的數(shù)字簽名:不可否認(rèn)數(shù)字簽名、盲簽名、群簽名等按驗證方法在驗證時需要輸入被簽名信息在驗證時自動恢復(fù)被簽名信息按簽名時是否使用隨機(jī)數(shù)分成確定性數(shù)字簽名隨機(jī)數(shù)字簽名105.6.2數(shù)字簽名的基本構(gòu)造方法利用Hash函數(shù)和加密算法可以構(gòu)造有效的數(shù)字簽名方案?；贖ash函數(shù)和單鑰密碼算法構(gòu)造數(shù)字簽名115.6.2數(shù)字簽名的基本構(gòu)造方法基于Hash函數(shù)和雙鑰密碼算法構(gòu)造數(shù)字簽名125.6.2數(shù)字簽名的基本構(gòu)造方法具有保密作用的數(shù)字簽名雙鑰密碼體制：SK是發(fā)送方的私鑰，PK是發(fā)送方的公鑰，E1和D1分別是加密算法與解密算法。單鑰密碼體制密鑰：K是雙方公用密鑰，E2和D2分別是對應(yīng)的加密算法和解密算法。135.6.3數(shù)字簽名的安全需求數(shù)字簽名的攻擊模型唯密鑰攻擊（keyonlyattack）攻擊者E擁有簽名者A的公鑰K，因而能夠計算驗證函數(shù)verK。已知消息攻擊（knownmessageattack）攻擊者E擁有一系列以前由簽名者A所簽名的消息。即E具有數(shù)據(jù)對（xi，yi），其中xi是消息，yi=sigK(xi)是A對xi的簽名（i=1,2,…）。選擇消息攻擊（chosenmessageattack）攻擊者E可以選擇一些消息請求簽名者A簽名。即E選擇消息xi，并將xi發(fā)送給簽名者A，請求A對xi簽名。A計算yi=sigK(xi)，并將yi發(fā)給E。所以，E具有A的有效數(shù)字簽名（xi，yi）（i=1,2,…）。145.6.3數(shù)字簽名的安全需求攻擊者對數(shù)字簽名系統(tǒng)的攻擊目的完全破譯（totalbreak）攻擊者E能確定簽名者A的私鑰K，因而能夠計算簽名函數(shù)sigK，可以對任何消息產(chǎn)生有效的簽名。選擇性偽造（selectiveforgery）攻擊者E能以某一個不可忽略的概率對另外某個人選定的消息產(chǎn)生一個有效的簽名。也就是說，如果給E選定一個消息x，那么他能以一個正的概率找到x的簽名y=sigK(x)，并且簽名者A以前未對x簽名。存在性偽造（existentialforgery）攻擊者E至少能夠為一個消息產(chǎn)生一個有效的簽名。也就是說，E可能生成一個數(shù)據(jù)對（x，y），其中x是消息，y=sigK(x)。簽名者A以前未對x簽名。155.6.3數(shù)字簽名的安全需求Hash函數(shù)與數(shù)字簽名的安全性對消息的散列值簽名165.6.3數(shù)字簽名的安全需求使用已知消息攻擊的存在性偽造

攻擊者E從一個有效的簽名(x,y)開始,其中y=sigK(h(x)).然后他計算z=h(x),并企圖找到x’x,使得h(x’)=h(x).如果E能做到這一點,則(x’,y)就是一個有效的簽名,從而y是消息x’的一個偽造簽名.為了阻止這種攻擊,必須要求Hash函數(shù)h是弱無碰撞的.使用選擇消息攻擊的存在性偽造

攻擊者E首先找到x’x,使得h(x’)=h(x).然后將消息x發(fā)給簽名者A,并讓A對消息的散列值h(x)簽名,從而得到y(tǒng)=sigK(h(x)).所以E能夠成功偽造簽名(x’,y).為了阻止這種攻擊,必須要求Hash函數(shù)h是強(qiáng)無碰撞的.175.6.3數(shù)字簽名的安全需求使用唯密鑰攻擊的存在性偽造

當(dāng)簽名算法遭到唯密鑰攻擊時,即攻擊者E擁有簽名者A的公鑰K.E就可能對一個隨機(jī)的散列值z偽造簽名y=sigK(z).此時,如果Hash函數(shù)h不是單向的,則E可能找到一個消息x，使得z=h(x).所以E能夠成功偽造一個簽名(x,y).為了阻止這種攻擊,必須要求Hash函數(shù)h是單向的.18第5章Hash函數(shù)與數(shù)字簽名5.6數(shù)字簽名概念5.7RSA數(shù)字簽名體制

5.8ElGamal數(shù)字簽名體制5.9其它數(shù)字簽名方案5.10數(shù)字簽名標(biāo)準(zhǔn)5.11應(yīng)用195.7RSA數(shù)字簽名體制利用RSA加密算法構(gòu)造的數(shù)字簽名稱為RAS數(shù)字簽名體制。5.7.1RSA算法描述1．密鑰生成算法選取兩個大素數(shù)p，q，計算n=pq，(n)=(p

1)(q

1)。任選整數(shù)e，滿足：0e(n)，且gcd(e,(n))=1。用擴(kuò)展Euclidean算法求e模(n)的逆d，即ed=1mod(n)。簽名者的公鑰:{n，e}，私鑰:{p，q，d}。

205.7.1RSA算法描述2．簽名算法設(shè)消息為x，則x的RAS簽名是3．驗證算法當(dāng)接收方收到簽名（x，y）后，計算如果x=x’，則y是x的RAS簽名。215.7.2RSA數(shù)字簽名的安全性1．一般攻擊攻擊方法:設(shè)n與e為用戶A的公鑰，攻擊者首先隨意選擇一個數(shù)據(jù)y，并用A的公鑰計算

x=yemodn，于是可以偽造A的一個RSA數(shù)字簽名（x，y）。因為

xd=(ye)d=yed=ymodn，所以用戶A對x的RSA數(shù)字簽名是y。這種攻擊實際上成功的概率是不高的因為對于選擇的數(shù)據(jù)y，得到的x=yemodn具有正確語義的概率是很低的。抵抗措施仔細(xì)設(shè)計數(shù)據(jù)格式對數(shù)據(jù)的Hash值進(jìn)行簽名225.7.2RSA數(shù)字簽名的安全性2．選擇消息攻擊攻擊方法:假設(shè)攻擊者E想偽造消息x的簽名，他容易找到兩個數(shù)據(jù)x1和x2，使得

攻擊者E設(shè)法讓用戶A分別對x1和x2進(jìn)行簽名，得到然后E可以計算于是攻擊者E得到了用戶A對消息x的RSA數(shù)字簽名y抵抗措施用戶不要輕易地對其他人提供的隨機(jī)數(shù)據(jù)進(jìn)行簽名對數(shù)據(jù)的Hash值進(jìn)行簽名

235.7.2RSA數(shù)字簽名的安全性3．利用簽名進(jìn)行攻擊從而獲得明文攻擊方法

假設(shè)攻擊者E已截獲了秘文c=xemodn，他想求出明文x。于是，他選擇一個小的隨機(jī)數(shù)r，并計算

因為s=re,所以sd=(re)d=modn，r=sdmodn.然后E設(shè)法讓簽名者對l簽名.于是E又獲得k=ldmodn.攻擊者E再計算：

于是，獲得了秘文x。抵抗措施用戶不要輕易地對其他人提供的隨機(jī)數(shù)據(jù)進(jìn)行簽名對數(shù)據(jù)的Hash值進(jìn)行簽名

245.7.2RSA數(shù)字簽名的安全性4．對先加密后簽名方案的攻擊攻擊方法假設(shè)簽名者A采用先加密后簽名的方案把消息x發(fā)送給接收者B,則他先用B的公開密鑰eB對x加密,然后用自己的私鑰dA簽名.設(shè)A的模數(shù)為nA,B的模數(shù)為nB.于是A發(fā)送給B的數(shù)據(jù)為:

如果B是不誠實的,那么B可能偽造A的簽名.例如,假設(shè)B想抵賴收到A發(fā)的消息x,慌稱收到的是x1.因為nB是B的模數(shù),所以B知道nB的分解,于是能夠計算模nB的離散對數(shù).即他能找到k滿足:然后，B再公布他的新公開密鑰為keB?，F(xiàn)在B宣布他收到的消息是x1，而不是x。由于下式成立，所以A無法爭辯。255.7.2RSA數(shù)字簽名的安全性4．對先加密后簽名方案的攻擊抵抗措施簽名者A應(yīng)當(dāng)在發(fā)送的數(shù)據(jù)中加入時間戳，從而可證明是用公開密鑰eB對x加密，而不是用新公開密鑰keB對x1加密。對數(shù)據(jù)的Hash值進(jìn)行簽名。

綜上所述，對于RSA數(shù)字簽名系統(tǒng)，必須采取如下安全措施：不直接對消息進(jìn)行簽名，而應(yīng)該對消息的Hash值進(jìn)行簽名。要采用先簽名后加密的方式，而不要采用先加密后簽名的方式。26第5章Hash函數(shù)與數(shù)字簽名5.6數(shù)字簽名概念5.7RSA數(shù)字簽名體制5.8ElGamal數(shù)字簽名體制

5.9其它數(shù)字簽名方案5.10數(shù)字簽名標(biāo)準(zhǔn)5.11應(yīng)用275.8ElGamal數(shù)字簽名體制在1985年，ElGamalT.提出了一個基于離散對數(shù)問題的數(shù)字簽名體制，通常稱為ElGamal數(shù)字簽名體制。ElGamal簽名體制的安全性主要是基于有限域上離散對數(shù)問題的難解性。285.8.1ElGamal簽名算法描述1．參數(shù)生成算法選取一個大素數(shù)p，gZp*是一個本原元，p和g是系統(tǒng)公開參數(shù)。任選整數(shù)x，滿足：1≤x≤p2。計算y=gx

modp.簽名者的公鑰為y，私鑰為x。2．簽名算法設(shè)MZp*為待簽名的消息。簽名者隨機(jī)選擇一個秘密整數(shù)k，1≤k≤p2，計算

簽名者對M的ElGamal簽名為:

簽名者將數(shù)據(jù)(M,(r,s))發(fā)送給接收者。295.8.1ElGamal簽名算法描述3．驗證算法接收方收到簽名(M,(r,s))后，驗證

是否成立，如果等號成立，則確認(rèn)(r,s)是M的有效簽名。有效性證明因此，如果（r，s）是M的正確簽名，則一定有305.8.1ElGamal簽名算法描述ElGamal數(shù)字簽名是一個隨機(jī)的數(shù)字簽名體制例5.6設(shè)p=11，g=2是Z11*的本原元。選取私鑰為x=8，計算公鑰設(shè)簽名者A要對消息M=5進(jìn)行簽名。簽名者A首先秘密選取一個整數(shù)k=9，計算簽名者A對M=5的ElGamal簽名為（6,3）。接收者B可以對消息M=5的簽名（6,3）進(jìn)行驗證。因為315.8.2ElGamal數(shù)字簽名的安全性ElGamal數(shù)字簽名算法的實現(xiàn)需要作一次模指數(shù)運算一次擴(kuò)展Euclidean算法運算（求隨機(jī)數(shù)k的逆元）二次模乘運算前兩個運算可以離線進(jìn)行是一個隨機(jī)的數(shù)字簽名體制ElGamal數(shù)字簽名體制的參數(shù)pp的選擇與在Zp*中計算離散對數(shù)的算法有直接關(guān)系。從目前的計算水平來看，p至少應(yīng)該是二進(jìn)制512位的素數(shù)，從長期安全性考慮，應(yīng)使用1024位或更長的素數(shù)。p1最好有大的素因子私鑰x最好是Zp*的素數(shù)階子群的生成元。325.8.3ElGamal數(shù)字簽名的安全性1．不知道私鑰的攻擊假設(shè)攻擊者E不知道私鑰x，要想偽造消息M的簽名(r,s),則E可能使用的攻擊方式有：(1)攻擊者已知消息M,選擇一個值r,再求另一個值s.此時,因為有

所以攻擊者E必須計算離散對數(shù)。

(2)攻擊者已知消息M,選擇一個值s,再求另一個值r.此時,他必須從同余方程中求出r。這是一個到目前為止還沒有可行方法求解的方程，甚至也看不出它與離散對數(shù)問題有沒有關(guān)系。335.8.3ElGamal數(shù)字簽名的安全性1．不知道私鑰的攻擊(3)攻擊者已知消息M，同時求(r,s).即他必須從同余方程中同時求出(r,s)?，F(xiàn)在人們對這個方程的認(rèn)識幾乎是一無所有，既沒有人發(fā)現(xiàn)解這個問題的方法，也沒有人能夠證明不能解這個問題。(4)攻擊者選擇數(shù)據(jù)對(r,s)，求消息M。此時必須計算離散對數(shù)345.8.3ElGamal數(shù)字簽名的安全性1．不知道私鑰的攻擊(5)攻擊者同時選擇數(shù)據(jù)M，r和s，使得(r,s)是M的簽名。這種攻擊方法可能獲得成功。攻擊者首先選擇整數(shù)i和j，0≤i,j≤p2，gcd(j,p1)=1，計算成立，所以(r,s)是消息M的有效簽名

該攻擊方法屬于存在性偽造。因此，在使用ElGamal數(shù)字簽名方案時，不要直接對消息進(jìn)行簽名，而應(yīng)該對消息的Hash值進(jìn)行簽名。355.8.3ElGamal數(shù)字簽名的安全性1．不知道私鑰的攻擊例5.7設(shè)p=467，g=2是Z467*的本原元，簽名者公鑰y=132。攻擊者選擇整數(shù)i=99，j=179，計算所以（117，41）是消息M=331的有效簽名。365.8.3ElGamal數(shù)字簽名的安全性2．已知消息攻擊假設(shè)攻擊者E知道(r,s)是消息M的簽名,則E可利用它來偽造其它消息的簽名.選擇整數(shù)l,i,j,0l,i,jp2，gcd(lrjs,p1)=1,計算

可見(u,v)是消息W的有效簽名。該攻擊方法屬于存在性偽造使用對消息的Hash值進(jìn)行簽名的方式,可以抵抗這類攻擊.

375.8.3ElGamal數(shù)字簽名的安全性使用ElGamal數(shù)字簽名方案的安全措施(1)不要泄露隨機(jī)數(shù)k(2)不要使用同一個隨機(jī)數(shù)k給兩個不同的消息簽名設(shè)（r，s）是消息M的簽名，（u，v）是消息W的簽名，使用的是同一個隨機(jī)數(shù)k，則可求出私鑰。

385.8.4ElGamal簽名體制的變形ElGamal數(shù)字簽名算法有多種變形設(shè)大素數(shù)p是模數(shù)，g是一個模p的本原元，x為簽名者的私鑰，k為隨機(jī)數(shù)，m為待簽名的消息，（r，s）是對M的簽名。簽名值的分量r=gkmodp,分量s由簽名算法確定。ElGamal數(shù)字簽名各種變形的簽名算法和驗證算法見下表。395.8.4ElGamal簽名體制的變形40第5章數(shù)字簽名5.6數(shù)字簽名概念5.7RSA數(shù)字簽名體制5.8ElGamal數(shù)字簽名體制

5.9其它數(shù)字簽名方案5.10數(shù)字簽名標(biāo)準(zhǔn)5.11應(yīng)用415.9.1FiatShamir數(shù)字簽名FiatShamir數(shù)字簽名由A.Fiat和A.Shamir提出，有時簡記為FS數(shù)字簽名。與RSA數(shù)字簽名相比較，F(xiàn)S數(shù)字簽名的主要優(yōu)勢是速度快，它僅需要RSA的1%4%的模乘法。FS數(shù)字簽名的理論基礎(chǔ)是大整數(shù)素因子分解的困難性。1．參數(shù)生成:選取兩個大素數(shù)p、q，令n=pq。n是公開參數(shù)，p和q是管理中心CA掌握的密鑰。設(shè)h是一個公開的Hash函數(shù)，k是一個固定的正整數(shù)。管理中心CA為用戶A產(chǎn)生k個公開密鑰：

yi(i=1,2,…,k)是模n的平方剩余再為用戶A產(chǎn)生k個私鑰（保密）425.9.1FiatShamir數(shù)字簽名2.簽名算法:為了對消息m進(jìn)行簽名,用戶A執(zhí)行以下步驟（1）隨機(jī)選取一個正整數(shù)t。（2）在1和n之間隨機(jī)選取t個正整數(shù)rj(j=1,2,…,t)，并計算（3）計算Hash函數(shù)值h(m||R1||R2||…||Rt)，依次取出其前kt個比特值，記為

（4）計算用戶A對消息m的數(shù)字簽名為簽名者將數(shù)據(jù)（m，{bij}，{sj}）發(fā)送給接收者B

435.9.1FiatShamir數(shù)字簽名3．驗證算法:接收方B收到簽名數(shù)據(jù)（m,{bij},{sj}）后,按以下步驟進(jìn)行驗證：（1）利用A的公鑰計算（2）計算Hash函數(shù)值依次取出其前kt個比特值，記為（3）比較等式

是否成立。如果kt個等式全部成立，則數(shù)字簽名有效。否則，數(shù)字簽名無效。445.9.1FiatShamir數(shù)字簽名該驗證算法的正確性

當(dāng)數(shù)據(jù)傳輸正確時，有455.9.1FiatShamir數(shù)字簽名例5.8設(shè)n=35，k=4，用戶A的4個公鑰為：y1=4，y2=11，y3=16，y4=29。則A的4個私鑰為：取t=1，r1=16，計算為了簡化，設(shè)h(m||R1)=R1=11=1011。即有

數(shù)字簽名為（{1,0,1,1},{26}）.

465.9.1FiatShamir數(shù)字簽名例5.9設(shè)n=35，k=4，用戶A的4個公鑰為：y1=4，y2=11，y3=16，y4=29。數(shù)字簽名為（{1,0,1,1},{26}）.

所以數(shù)字簽名有效。接收方驗證方法如下。由于475.9.2一次性數(shù)字簽名一次性簽名方案是指一對公、私鑰只能用于對一個消息進(jìn)行簽名的方案，它通常被用于芯片卡（chipcards)。1978年，M.O.Rabin首次提出一次性簽名方案。在Rabin一次性簽名方案中，簽名算法使用了對稱加密算法，驗證過程需要驗證者與簽名者共同參與。1979年，L.Lamport提出一個類似的方案，不同之處在于驗證時不需要驗證者與簽名者交互。該方案由于受到著名密碼學(xué)家Diffie和Hellman的重視而有名。1992年，Bos與Chaum對Lamport的另一個更有效的一次性簽名方案做了本質(zhì)的改進(jìn)，并證明了改進(jìn)的簽名方案在選擇消息攻擊下是不可偽造的。485.9.2——Lamport一次性數(shù)字簽名

(1)密鑰生成：已知單向函數(shù)f：Y→Z。在Y中隨機(jī)選取y1,0，y1,1，y2,0，y2,1，…，yk,0，yk,1

為私鑰。計算zi,j=f(yi,j)（1ik，j=0,1），單向函數(shù)f及z1,0，z1,1，z2,0，z2,1，…，zk,0，zk,1為公鑰。495.9.2——Lamport一次性數(shù)字簽名

(2)簽名算法設(shè)消息x=(xkxk-1…x2

x1)是二進(jìn)制串，則對消息x的簽名為：{ui=yi,j

|1ik,xi=j}。(3)驗證算法

若{f(ui)|1ik}包含在公鑰中，則簽名是合法的。505.9.2——Lamport一次性數(shù)字簽名

例5.10取素數(shù)p=7879，已知3是Z7879的本原元。定義f(x)=3x

mod7879，令k=3。取私鑰：y1,0=5831,y1,1=735,y2,0=803,y2,1=2467,y3,0=4285,y3,1=6449.計算公鑰為：

z1,0=f(y1,0)=35831

=2009mod7879,

z1,1=3810,

z2,0=4672,z2,1=4721,

z3,0=268,z3,1=5731.

求消息x=011的簽名。對于x3=0，由i=3，j=0，相應(yīng)的簽名為u3=y3,0=4285。同理，x2=1相應(yīng)的簽名為u2=y2,1=2467，x1=1相應(yīng)的簽名為u1=y1,1=735。所以，對消息x=011的簽名為（4285，2467，735)。515.9.2——Lamport一次性數(shù)字簽名

例5.11取素數(shù)p=7879，已知3是Z7879的本原元。接收方驗證時計算：3735mod7879=3810,32464mod7879=4721,34285mod7879=268.對手雖然不能從zi,j求出yi,j，但是用這個簽名方案對兩個不同的消息簽名時，對手就能偽造出另一些消息的簽名。例如，在例6.5中，對手知道011和101的簽名分別是（y3,0，y2,1，y1,1)和（y3,1，y2,0，y1,1)，顯然（y3,1，y2,1，y1,1)和（y3,0，y2,0，y1,1)分別是111和001的簽名。

525.9.3——Bos-Chaum

一次性數(shù)字簽名

Bos-Chaum一次性簽名方案的簽名比Lamport方案的簽名短。設(shè)A={1，2，…，2n}是2n元集合，B是A的所有n元子集構(gòu)成的集合，則有|B|=C2nn。定義Bos-Chaum簽名方案使用的單射函數(shù)為：：{0,1}kB，它把長為k的字符串映射到A的n元子集，這里2kC2nn535.9.3——Bos-Chaum

一次性數(shù)字簽名

(1)密鑰生成

設(shè)f：Y→Z是單向函數(shù)，取y1，y2，…，y2nY作為私鑰，z1，z2，…，z2nZ作為公鑰，其中f(yi)=zi(1i2n)。(2)簽名算法

設(shè)消息x=(xkxk-1…x2x1)2是二進(jìn)制串，則對消息x的簽名為：{a1，a2，…，an}={yj|j(x)}。(3)驗證算法

計算集合C={f(ai),1in}和(x)。如果C={zj

|j(x)}，則{a1，a2，…，an}是對x的合法簽名。545.9.3——Bos-Chaum

一次性數(shù)字簽名

由于f是單向函數(shù)，對手不可能偽造消息的Bos-Chaum簽名。如果使用Bos-Chaum方案簽了兩個消息，則對手容易偽造Bos-Chaum簽名。例如，令n=4，容易計算出(110010)={2，4，6，8}，φ(010011)={2，3，4，7}。已知對110010的Bos-Chaum簽名為{y2，y4，y6，y8}，對010011的Bos-Chaum簽名為{y2，y3，y4，y7}，容易得到對111100的Bos-Chaum簽名為{y2，y4，y7，y8}。所以該簽名方案是一次性簽名方案。555.9.4不可否認(rèn)數(shù)字簽名對于以前討論的數(shù)字簽名，任何人都可以對簽名進(jìn)行驗證。但在某些特殊應(yīng)用條件下，需要在簽名者參加的情況下才能進(jìn)行驗證。具有這種性質(zhì)的數(shù)字簽名稱為不可否認(rèn)簽名方案(undeniablesignaturescheme).它們可以應(yīng)用在如下場合：

1）實體A希望訪問實體B控制的“安全區(qū)域”。實體B在授予實體A訪問權(quán)之前，要求A對“訪問時間、日期”進(jìn)行簽名。另一方面，實體A不希望別人了解這個事實，即沒有實體A的參與，實體B不能通過出示實體A的簽名及驗證，來證明“實體A訪問該區(qū)域”這一事實。2）某公司A開發(fā)的一個軟件包。A將軟件包和他對軟件包的不可否認(rèn)簽名賣給用戶B。B當(dāng)場驗證A的簽名，以便確認(rèn)軟件包的真實性。用戶B想把該軟件包的拷貝私自賣給第三者。由于沒有公司A參與，第三者不能驗證軟件包的真實性。從而保護(hù)了公司A的利益

565.9.4不可否認(rèn)數(shù)字簽名Chaum和vanAntwerpen在1989年提出的不可否認(rèn)數(shù)字簽名方案(1)密鑰生成(2)簽名算法

對消息m的簽名是:s=mxmodp。575.9.4不可否認(rèn)數(shù)字簽名(3)驗證協(xié)議假設(shè)簽名者A想否認(rèn)一個“由簽名生成算法構(gòu)造出來的”合法簽名，其方式有：①拒絕參與驗證協(xié)議；②錯誤地執(zhí)行驗證協(xié)議；③即使驗證協(xié)議成功，也斷言簽名是偽造的。對于前者很明顯，而后兩種情況難以防范。使用“否認(rèn)協(xié)議”（disavowalprotocol）能夠確定是簽名者A試圖否認(rèn)一個由簽名算法得出的簽名，還是簽名本身是偽造的。否認(rèn)協(xié)議由兩遍驗證協(xié)議組成。585.9.4不可否認(rèn)數(shù)字簽名(4)否認(rèn)協(xié)議進(jìn)行一致性檢驗，若C=C，則s是對m的偽造簽名；若CC，則s是對m的合法簽名，簽名者試圖否認(rèn).595.9.4不可否認(rèn)數(shù)字簽名否認(rèn)協(xié)議的性質(zhì)性質(zhì)1如果驗證者和簽名者都正確執(zhí)行協(xié)議，則必有C=C，說明s是對m的偽造簽名，即性質(zhì)2性質(zhì)3605.9.5盲簽名

對于前面介紹的數(shù)字簽名，簽名者知道所簽名的消息。但在數(shù)字現(xiàn)金、電子投票等應(yīng)用領(lǐng)域，要求簽名者不能知道所簽名的消息。簽名者對所簽署消息和對消息的簽名都不可見的數(shù)字簽名稱為盲簽名（blindsignature）盲簽名由D.Chaum在1982年首次提出615.9.5盲簽名

盲簽名過程A是消息m的擁有者,稱為求簽名者B稱為簽名者盲簽名需要兩個基本構(gòu)件：1)求簽名者A知道的盲化函數(shù)f及脫盲函數(shù)g。f與g必須滿足：g(SB(f(m)))=SB(m)。2)簽名者B的數(shù)字簽名方案SB。625.9.5盲簽名

考慮盲簽名在電子貨幣中的應(yīng)用，例如顧客A得到銀行B對錢款m的盲簽名后，自己算出銀行的真正簽名SB(m)。在支付時提交出m和SB(m)，銀行能驗證SB(m)是否為m的合法簽名，但不知道這是誰的一筆消費。從而使A保持匿名狀態(tài)，即消費行為不受到監(jiān)控。635.9.5—基于RSA公鑰密碼系統(tǒng)的Chaum盲簽名Chaum提出的盲簽名方案是基于RSA公鑰密碼系統(tǒng)的(1)密鑰生成:選取素數(shù)p、q，令nB=pq，1<bB<(nB)且gcd(bB,nB)=1，隨機(jī)選取1<aB<(nB)使得aBbB≡1mod(nB)。簽名者B的公鑰是（nB，bB），私鑰是aB。645.9.5—基于RSA公鑰密碼系統(tǒng)的Chaum盲簽名(2)盲簽名協(xié)議：設(shè)需簽名的消息為m

(3)盲簽名驗證算法655.9.5—基于離散對數(shù)問題的盲簽名

瑞士學(xué)者J.Lcamenisch,J.M.Pivetean提出了基于離散對數(shù)問題的盲簽名(1)密鑰生成:簽名者選擇兩個大素數(shù)p，q，q|(p1)，在Zp*上離散對數(shù)問題是難解問題。a是Zp*的q階元。選取私鑰x，令y=axmodp，（p，q，a，y）為公鑰。

665.9.5—基于離散對數(shù)問題的盲簽名

(2)盲簽名協(xié)議：設(shè)A需簽名的消息為m，盲簽名由簽名者B開始(3)盲簽名驗證算法67第5章數(shù)字簽名5.6數(shù)字簽名概念5.7RSA數(shù)字簽名體制5.8ElGamal數(shù)字簽名體制

5.9其它數(shù)字簽名方案5.10數(shù)字簽名標(biāo)準(zhǔn)5.11應(yīng)用685.10.1美國數(shù)字簽名標(biāo)準(zhǔn)數(shù)字簽名標(biāo)準(zhǔn)（DSS:DigitalSignatureStandard）由美國國家標(biāo)準(zhǔn)技術(shù)研究所（NIST）于1991年提出，并于1994年正式成為美國聯(lián)邦信息處理標(biāo)準(zhǔn)（FIPSPUB186），這標(biāo)志著數(shù)字簽名已得到政府的支持。DSS使用的簽名算法稱為數(shù)字簽名算法（DSA:DigitalSignatureAlgorithm）。2000年1月美國政府將RSA和橢圓曲線密碼引入數(shù)字簽名標(biāo)準(zhǔn)DSS，進(jìn)一步豐富了DSS的算法。目前，DSS的應(yīng)用已十分廣泛，并被多個國際標(biāo)準(zhǔn)化組織采納作為標(biāo)準(zhǔn)。美國的一些州已經(jīng)通過相關(guān)法律，正式承認(rèn)數(shù)字簽名的法律意義。這是數(shù)字簽名得到法律支持的重要標(biāo)志。695.10.1美國數(shù)字簽名標(biāo)準(zhǔn)(1)算法參數(shù):DSA使用的參數(shù)如下p，q，g是公開參數(shù)，可為一組用戶公用x