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

網(wǎng)絡(luò)與信息安全數(shù)字簽名1第1頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月第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)用2第2頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.6數(shù)字簽名概念在政治、軍事、外交、商業(yè)和日常生活中，人們經(jīng)常需要對(duì)紙質(zhì)材料進(jìn)行簽名。簽名起到確認(rèn)、核準(zhǔn)、生效和負(fù)責(zé)任等多種作用。隨著計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)的發(fā)展，電子商務(wù)、電子政務(wù)和電子金融等系統(tǒng)得到廣泛應(yīng)用，人們需要通過(guò)網(wǎng)絡(luò)信息傳輸對(duì)電子的文件、契約、合同、信件和張單等進(jìn)行數(shù)字簽名以替代手寫(xiě)簽名。3第3頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.6數(shù)字簽名概念簽名是證明當(dāng)事人的身份和數(shù)據(jù)真實(shí)性的一種信息。在傳統(tǒng)的以書(shū)面文件為基礎(chǔ)的事物處理中，采用書(shū)面簽名的形式，如手簽、手印和印章等。書(shū)面簽名得到司法部門(mén)的支持，具有一定的法律意義4第4頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.6數(shù)字簽名概念在以計(jì)算機(jī)文件為基礎(chǔ)的現(xiàn)代事物處理中，應(yīng)采用電子形式的簽名，即數(shù)字簽名（digitalsignature）。數(shù)字簽名的目的是提供一種手段，使得一個(gè)實(shí)體把他的身份與某個(gè)信息捆綁在一起。一個(gè)信息的數(shù)字簽名實(shí)際上是一個(gè)數(shù)，它僅僅依賴(lài)于簽名者的密鑰和被簽名的消息。10011100010100011000sigK密鑰K5第5頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.6.1數(shù)字簽名的基本概念（1）消息空間:由所有任意長(zhǎng)度消息組成的集合

（2）簽名空間:由所有簽名組成的集合。簽名長(zhǎng)度不超過(guò)n。（3）密鑰空間:（4）sigK稱(chēng)為簽名算法（signingalgorithm）

一個(gè)數(shù)字簽名體制是一個(gè)滿(mǎn)足以下條件的五元組:6第6頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.6.1數(shù)字簽名的基本概念（5）verK稱(chēng)為驗(yàn)證算法（verificationalgorithm）（6）

則將數(shù)據(jù)對(duì)（x，y）稱(chēng)為消息x的一個(gè)數(shù)字簽名，或直接把y稱(chēng)為消息x的數(shù)字簽名7第7頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.6.1數(shù)字簽名的基本概念數(shù)字簽名基本要求對(duì)每一個(gè)密鑰K,sigK和verK應(yīng)該是多項(xiàng)式時(shí)間函數(shù)verK是公開(kāi)的函數(shù),而sigK是保密的

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

數(shù)字簽名算法必須滿(mǎn)足的條件簽名者事后不能否認(rèn)自己的簽名；其他人不能偽造簽名；當(dāng)通信雙方為簽名真?zhèn)伟l(fā)生爭(zhēng)執(zhí)時(shí),可以由第三方解決爭(zhēng)端8第8頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.6.1數(shù)字簽名的基本概念手寫(xiě)簽名與數(shù)字簽名的區(qū)別手寫(xiě)簽名是所簽文件的物理組成部分，數(shù)字簽名必須與所簽文件捆綁在一起。手寫(xiě)簽名通過(guò)與標(biāo)準(zhǔn)簽名進(jìn)行比較或檢查筆跡來(lái)驗(yàn)證，數(shù)字簽名是通過(guò)驗(yàn)證算法來(lái)驗(yàn)證。手寫(xiě)簽名容易偽造，好的數(shù)字簽名算法應(yīng)該使偽造簽名十分困難。手寫(xiě)簽名不易復(fù)制。數(shù)字簽名是一個(gè)二進(jìn)制串，容易復(fù)制。所以必須防止數(shù)字簽名重復(fù)使用。9第9頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.6.1數(shù)字簽名的基本概念簽名算法進(jìn)行分類(lèi)按應(yīng)用目的普通數(shù)字簽名特殊目的數(shù)字簽名:不可否認(rèn)數(shù)字簽名、盲簽名、群簽名等按驗(yàn)證方法在驗(yàn)證時(shí)需要輸入被簽名信息在驗(yàn)證時(shí)自動(dòng)恢復(fù)被簽名信息按簽名時(shí)是否使用隨機(jī)數(shù)分成確定性數(shù)字簽名隨機(jī)數(shù)字簽名10第10頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.6.2數(shù)字簽名的基本構(gòu)造方法利用Hash函數(shù)和加密算法可以構(gòu)造有效的數(shù)字簽名方案?；贖ash函數(shù)和單鑰密碼算法構(gòu)造數(shù)字簽名11第11頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.6.2數(shù)字簽名的基本構(gòu)造方法基于Hash函數(shù)和雙鑰密碼算法構(gòu)造數(shù)字簽名12第12頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.6.2數(shù)字簽名的基本構(gòu)造方法具有保密作用的數(shù)字簽名雙鑰密碼體制：SK是發(fā)送方的私鑰，PK是發(fā)送方的公鑰，E1和D1分別是加密算法與解密算法。單鑰密碼體制密鑰：K是雙方公用密鑰，E2和D2分別是對(duì)應(yīng)的加密算法和解密算法。13第13頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月

5.6.3數(shù)字簽名的安全需求數(shù)字簽名的攻擊模型唯密鑰攻擊（keyonlyattack）攻擊者E擁有簽名者A的公鑰K，因而能夠計(jì)算驗(yàn)證函數(shù)verK。已知消息攻擊（knownmessageattack）攻擊者E擁有一系列以前由簽名者A所簽名的消息。即E具有數(shù)據(jù)對(duì)（xi，yi），其中xi是消息，yi=sigK(xi)是A對(duì)xi的簽名（i=1,2,…）。選擇消息攻擊（chosenmessageattack）攻擊者E可以選擇一些消息請(qǐng)求簽名者A簽名。即E選擇消息xi，并將xi發(fā)送給簽名者A，請(qǐng)求A對(duì)xi簽名。A計(jì)算yi=sigK(xi)，并將yi發(fā)給E。所以，E具有A的有效數(shù)字簽名（xi，yi）（i=1,2,…）。14第14頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月

5.6.3數(shù)字簽名的安全需求攻擊者對(duì)數(shù)字簽名系統(tǒng)的攻擊目的完全破譯（totalbreak）攻擊者E能確定簽名者A的私鑰K，因而能夠計(jì)算簽名函數(shù)sigK，可以對(duì)任何消息產(chǎn)生有效的簽名。選擇性偽造（selectiveforgery）攻擊者E能以某一個(gè)不可忽略的概率對(duì)另外某個(gè)人選定的消息產(chǎn)生一個(gè)有效的簽名。也就是說(shuō)，如果給E選定一個(gè)消息x，那么他能以一個(gè)正的概率找到x的簽名y=sigK(x)，并且簽名者A以前未對(duì)x簽名。存在性偽造（existentialforgery）攻擊者E至少能夠?yàn)橐粋€(gè)消息產(chǎn)生一個(gè)有效的簽名。也就是說(shuō)，E可能生成一個(gè)數(shù)據(jù)對(duì)（x，y），其中x是消息，y=sigK(x)。簽名者A以前未對(duì)x簽名。15第15頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月

5.6.3數(shù)字簽名的安全需求Hash函數(shù)與數(shù)字簽名的安全性對(duì)消息的散列值簽名16第16頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月

5.6.3數(shù)字簽名的安全需求使用已知消息攻擊的存在性偽造

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

攻擊者E首先找到x’x,使得h(x’)=h(x).然后將消息x發(fā)給簽名者A,并讓A對(duì)消息的散列值h(x)簽名,從而得到y(tǒng)=sigK(h(x)).所以E能夠成功偽造簽名(x’,y).為了阻止這種攻擊,必須要求Hash函數(shù)h是強(qiáng)無(wú)碰撞的.17第17頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月

5.6.3數(shù)字簽名的安全需求使用唯密鑰攻擊的存在性偽造

當(dāng)簽名算法遭到唯密鑰攻擊時(shí),即攻擊者E擁有簽名者A的公鑰K.E就可能對(duì)一個(gè)隨機(jī)的散列值z(mì)偽造簽名y=sigK(z).此時(shí),如果Hash函數(shù)h不是單向的,則E可能找到一個(gè)消息x，使得z=h(x).所以E能夠成功偽造一個(gè)簽名(x,y).為了阻止這種攻擊,必須要求Hash函數(shù)h是單向的.18第18頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月第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)用19第19頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月

5.7RSA數(shù)字簽名體制利用RSA加密算法構(gòu)造的數(shù)字簽名稱(chēng)為RAS數(shù)字簽名體制。5.7.1RSA算法描述1．密鑰生成算法選取兩個(gè)大素?cái)?shù)p，q，計(jì)算n=pq，(n)=(p

1)(q

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

20第20頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月

5.7.1RSA算法描述2．簽名算法設(shè)消息為x，則x的RAS簽名是3．驗(yàn)證算法當(dāng)接收方收到簽名（x，y）后，計(jì)算如果x=x’，則y是x的RAS簽名。21第21頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.7.2RSA數(shù)字簽名的安全性1．一般攻擊攻擊方法:設(shè)n與e為用戶(hù)A的公鑰，攻擊者首先隨意選擇一個(gè)數(shù)據(jù)y，并用A的公鑰計(jì)算

x=yemodn，于是可以偽造A的一個(gè)RSA數(shù)字簽名（x，y）。因?yàn)?/p>

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

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

23第23頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.7.2RSA數(shù)字簽名的安全性3．利用簽名進(jìn)行攻擊從而獲得明文攻擊方法

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

因?yàn)閟=re,所以sd=(re)d=modn，r=sdmodn.然后E設(shè)法讓簽名者對(duì)l簽名.于是E又獲得k=ldmodn.攻擊者E再計(jì)算：于是，獲得了秘文x。抵抗措施用戶(hù)不要輕易地對(duì)其他人提供的隨機(jī)數(shù)據(jù)進(jìn)行簽名對(duì)數(shù)據(jù)的Hash值進(jìn)行簽名

24第24頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.7.2RSA數(shù)字簽名的安全性4．對(duì)先加密后簽名方案的攻擊攻擊方法假設(shè)簽名者A采用先加密后簽名的方案把消息x發(fā)送給接收者B,則他先用B的公開(kāi)密鑰eB對(duì)x加密,然后用自己的私鑰dA簽名.設(shè)A的模數(shù)為nA,B的模數(shù)為nB.于是A發(fā)送給B的數(shù)據(jù)為:如果B是不誠(chéng)實(shí)的,那么B可能偽造A的簽名.例如,假設(shè)B想抵賴(lài)收到A發(fā)的消息x,慌稱(chēng)收到的是x1.因?yàn)閚B是B的模數(shù),所以B知道nB的分解,于是能夠計(jì)算模nB的離散對(duì)數(shù).即他能找到k滿(mǎn)足:然后，B再公布他的新公開(kāi)密鑰為keB?，F(xiàn)在B宣布他收到的消息是x1，而不是x。由于下式成立，所以A無(wú)法爭(zhēng)辯。25第25頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.7.2RSA數(shù)字簽名的安全性4．對(duì)先加密后簽名方案的攻擊抵抗措施簽名者A應(yīng)當(dāng)在發(fā)送的數(shù)據(jù)中加入時(shí)間戳，從而可證明是用公開(kāi)密鑰eB對(duì)x加密，而不是用新公開(kāi)密鑰keB對(duì)x1加密。對(duì)數(shù)據(jù)的Hash值進(jìn)行簽名。

綜上所述，對(duì)于RSA數(shù)字簽名系統(tǒng)，必須采取如下安全措施：不直接對(duì)消息進(jìn)行簽名，而應(yīng)該對(duì)消息的Hash值進(jìn)行簽名。要采用先簽名后加密的方式，而不要采用先加密后簽名的方式。26第26頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月第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)用27第27頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.8ElGamal數(shù)字簽名體制在1985年，ElGamalT.提出了一個(gè)基于離散對(duì)數(shù)問(wèn)題的數(shù)字簽名體制，通常稱(chēng)為ElGamal數(shù)字簽名體制。ElGamal簽名體制的安全性主要是基于有限域上離散對(duì)數(shù)問(wèn)題的難解性。28第28頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.8.1ElGamal簽名算法描述1．參數(shù)生成算法選取一個(gè)大素?cái)?shù)p，gZp*是一個(gè)本原元，p和g是系統(tǒng)公開(kāi)參數(shù)。任選整數(shù)x，滿(mǎn)足：1≤x≤p2。計(jì)算y=gx

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

簽名者對(duì)M的ElGamal簽名為:

簽名者將數(shù)據(jù)(M,(r,s))發(fā)送給接收者。29第29頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.8.1ElGamal簽名算法描述3．驗(yàn)證算法接收方收到簽名(M,(r,s))后，驗(yàn)證

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

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

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

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

可見(jiàn)(u,v)是消息W的有效簽名。該攻擊方法屬于存在性偽造使用對(duì)消息的Hash值進(jìn)行簽名的方式,可以抵抗這類(lèi)攻擊.37第37頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.8.3ElGamal數(shù)字簽名的安全性使用ElGamal數(shù)字簽名方案的安全措施(1)不要泄露隨機(jī)數(shù)k(2)不要使用同一個(gè)隨機(jī)數(shù)k給兩個(gè)不同的消息簽名設(shè)（r，s）是消息M的簽名，（u，v）是消息W的簽名，使用的是同一個(gè)隨機(jī)數(shù)k，則可求出私鑰。

38第38頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.8.4ElGamal簽名體制的變形ElGamal數(shù)字簽名算法有多種變形設(shè)大素?cái)?shù)p是模數(shù)，g是一個(gè)模p的本原元，x為簽名者的私鑰，k為隨機(jī)數(shù)，m為待簽名的消息，（r，s）是對(duì)M的簽名。簽名值的分量r=gkmodp,分量s由簽名算法確定。ElGamal數(shù)字簽名各種變形的簽名算法和驗(yàn)證算法見(jiàn)下表。39第39頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.8.4ElGamal簽名體制的變形40第40頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月第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)用41第41頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.9.1FiatShamir數(shù)字簽名FiatShamir數(shù)字簽名由A.Fiat和A.Shamir提出，有時(shí)簡(jiǎn)記為FS數(shù)字簽名。與RSA數(shù)字簽名相比較，F(xiàn)S數(shù)字簽名的主要優(yōu)勢(shì)是速度快，它僅需要RSA的1%4%的模乘法。FS數(shù)字簽名的理論基礎(chǔ)是大整數(shù)素因子分解的困難性。1．參數(shù)生成:選取兩個(gè)大素?cái)?shù)p、q，令n=pq。n是公開(kāi)參數(shù)，p和q是管理中心CA掌握的密鑰。設(shè)h是一個(gè)公開(kāi)的Hash函數(shù)，k是一個(gè)固定的正整數(shù)。管理中心CA為用戶(hù)A產(chǎn)生k個(gè)公開(kāi)密鑰：

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

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

43第43頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.9.1FiatShamir數(shù)字簽名3．驗(yàn)證算法:接收方B收到簽名數(shù)據(jù)（m,{bij},{sj}）后,按以下步驟進(jìn)行驗(yàn)證：（1）利用A的公鑰計(jì)算（2）計(jì)算Hash函數(shù)值依次取出其前kt個(gè)比特值，記為（3）比較等式是否成立。如果kt個(gè)等式全部成立，則數(shù)字簽名有效。否則，數(shù)字簽名無(wú)效。44第44頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.9.1FiatShamir數(shù)字簽名該驗(yàn)證算法的正確性

當(dāng)數(shù)據(jù)傳輸正確時(shí)，有45第45頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.9.1FiatShamir數(shù)字簽名例5.8設(shè)n=35，k=4，用戶(hù)A的4個(gè)公鑰為：y1=4，y2=11，y3=16，y4=29。則A的4個(gè)私鑰為：取t=1，r1=16，計(jì)算為了簡(jiǎn)化，設(shè)h(m||R1)=R1=11=1011。即有

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

46第46頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.9.1FiatShamir數(shù)字簽名例5.9設(shè)n=35，k=4，用戶(hù)A的4個(gè)公鑰為：y1=4，y2=11，y3=16，y4=29。數(shù)字簽名為（{1,0,1,1},{26}）.

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

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

為私鑰。計(jì)算zi,j=f(yi,j)（1ik，j=0,1），單向函數(shù)f及z1,0，z1,1，z2,0，z2,1，…，zk,0，zk,1為公鑰。49第49頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.9.2——Lamport一次性數(shù)字簽名

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

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

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

若{f(ui)|1ik}包含在公鑰中，則簽名是合法的。50第50頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.9.2——Lamport一次性數(shù)字簽名

例5.10取素?cái)?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.計(jì)算公鑰為：

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

=2009mod7879,

z1,1=3810,

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

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

求消息x=011的簽名。對(duì)于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。所以，對(duì)消息x=011的簽名為（4285，2467，735)。51第51頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.9.2——Lamport一次性數(shù)字簽名

例5.11取素?cái)?shù)p=7879，已知3是Z7879的本原元。接收方驗(yàn)證時(shí)計(jì)算：3735mod7879=3810,32464mod7879=4721,34285mod7879=268.對(duì)手雖然不能從zi,j求出yi,j，但是用這個(gè)簽名方案對(duì)兩個(gè)不同的消息簽名時(shí)，對(duì)手就能偽造出另一些消息的簽名。例如，在例6.5中，對(duì)手知道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的簽名。

52第52頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.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，它把長(zhǎng)為k的字符串映射到A的n元子集，這里2kC2nn53第53頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.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)制串，則對(duì)消息x的簽名為：{a1，a2，…，an}={yj|j(x)}。(3)驗(yàn)證算法

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

|j(x)}，則{a1，a2，…，an}是對(duì)x的合法簽名。54第54頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.9.3——Bos-Chaum

一次性數(shù)字簽名

由于f是單向函數(shù)，對(duì)手不可能偽造消息的Bos-Chaum簽名。如果使用Bos-Chaum方案簽了兩個(gè)消息，則對(duì)手容易偽造Bos-Chaum簽名。例如，令n=4，容易計(jì)算出(110010)={2，4，6，8}，φ(010011)={2，3，4，7}。已知對(duì)110010的Bos-Chaum簽名為{y2，y4，y6，y8}，對(duì)010011的Bos-Chaum簽名為{y2，y3，y4，y7}，容易得到對(duì)111100的Bos-Chaum簽名為{y2，y4，y7，y8}。所以該簽名方案是一次性簽名方案。55第55頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月56第56頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.9.4不可否認(rèn)數(shù)字簽名(3)驗(yàn)證協(xié)議假設(shè)簽名者A想否認(rèn)一個(gè)“由簽名生成算法構(gòu)造出來(lái)的”合法簽名，其方式有：①拒絕參與驗(yàn)證協(xié)議；②錯(cuò)誤地執(zhí)行驗(yàn)證協(xié)議；③即使驗(yàn)證協(xié)議成功，也斷言簽名是偽造的。對(duì)于前者很明顯，而后兩種情況難以防范。使用“否認(rèn)協(xié)議”（disavowalprotocol）能夠確定是簽名者A試圖否認(rèn)一個(gè)由簽名算法得出的簽名，還是簽名本身是偽造的。否認(rèn)協(xié)議由兩遍驗(yàn)證協(xié)議組成。57第57頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.9.4不可否認(rèn)數(shù)字簽名(4)否認(rèn)協(xié)議進(jìn)行一致性檢驗(yàn)，若C=C，則s是對(duì)m的偽造簽名；若CC，則s是對(duì)m的合法簽名，簽名者試圖否認(rèn).58第58頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.9.4不可否認(rèn)數(shù)字簽名否認(rèn)協(xié)議的性質(zhì)性質(zhì)1如果驗(yàn)證者和簽名者都正確執(zhí)行協(xié)議，則必有C=C，說(shuō)明s是對(duì)m的偽造簽名，即性質(zhì)2性質(zhì)359第59頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.9.5盲簽名

對(duì)于前面介紹的數(shù)字簽名，簽名者知道所簽名的消息。但在數(shù)字現(xiàn)金、電子投票等應(yīng)用領(lǐng)域，要求簽名者不能知道所簽名的消息。簽名者對(duì)所簽署消息和對(duì)消息的簽名都不可見(jiàn)的數(shù)字簽名稱(chēng)為盲簽名（blindsignature）盲簽名由D.Chaum在1982年首次提出60第60頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.9.5盲簽名

盲簽名過(guò)程A是消息m的擁有者,稱(chēng)為求簽名者B稱(chēng)為簽名者盲簽名需要兩個(gè)基本構(gòu)件：1)求簽名者A知道的盲化函數(shù)f及脫盲函數(shù)g。f與g必須滿(mǎn)足：g(SB(f(m)))=SB(m)。2)簽名者B的數(shù)字簽名方案SB。61第61頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.9.5盲簽名

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

(3)盲簽名驗(yàn)證算法64第64頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.9.5—基于離散對(duì)數(shù)問(wèn)題的盲簽名

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

65第65頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.9.5—基于離散對(duì)數(shù)問(wèn)題的盲簽名

(2)盲簽名協(xié)議：設(shè)A需簽名的消息為m，盲簽名由簽名者B開(kāi)始(3)盲簽名驗(yàn)證算法66第66頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月第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)用67第67頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.10.1美國(guó)數(shù)字簽名標(biāo)準(zhǔn)數(shù)字簽名標(biāo)準(zhǔn)（DSS:DigitalSignatureStandard）由美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)研究所（NIST）于1991年提出，并于1994年正式成為美國(guó)聯(lián)邦信息處理標(biāo)準(zhǔn)（FIPSPUB186），這標(biāo)志著數(shù)字簽名已得到政府的支持。DSS使用的簽名算法稱(chēng)為數(shù)字簽名算法（DSA:DigitalSignatureAlgorithm）。2000年1月美國(guó)政府將RSA和橢圓曲線密碼引入數(shù)字簽名標(biāo)準(zhǔn)DSS，進(jìn)一步豐富了DSS的算法。目前，DSS的應(yīng)用已十分廣泛，并被多個(gè)國(guó)際標(biāo)準(zhǔn)化組織采納作為標(biāo)準(zhǔn)。美國(guó)的一些州已經(jīng)通過(guò)相關(guān)法律，正式承認(rèn)數(shù)字簽名的法律意義。這是數(shù)字簽名得到法律支持的重要標(biāo)志。68第68頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.10.1美國(guó)數(shù)字簽名標(biāo)準(zhǔn)(1)算法參數(shù):DSA使用的參數(shù)如下p，q，g是公開(kāi)參數(shù)，可為一組用戶(hù)公用x和y分別為一個(gè)簽名者的私鑰和公鑰，私鑰x用于產(chǎn)生簽名，必須保密

所有這些參數(shù)可在一定時(shí)間內(nèi)固定69第69頁(yè)，課件共79頁(yè)，創(chuàng)作于2023年2月5.10.1美國(guó)數(shù)字簽名標(biāo)準(zhǔn)(2)簽名算法：設(shè)SHA是一個(gè)安全hash函數(shù)70