現(xiàn)代密碼學(xué)-第6章數(shù)字簽名-20091202

1、現(xiàn)代密碼學(xué)21世紀(jì)高等學(xué)校計(jì)算機(jī)規(guī)劃教材 Modern Cryptography彭代淵 信息科學(xué)與技術(shù)學(xué)院 2009.9-2010.1作 者：何大可 彭代淵 唐小虎 何明星 梅其祥 出版社：人民郵電出版社1現(xiàn)代密碼學(xué) Modern Cryptography彭代淵 信息科學(xué)與技術(shù)學(xué)院 2009年12月第6章 數(shù)字簽名2第6章 數(shù)字簽名6.1 數(shù)字簽名概念6.2 RSA數(shù)字簽名體制 6.3 ElGamal數(shù)字簽名體制 6.4 其它數(shù)字簽名方案6.5 數(shù)字簽名標(biāo)準(zhǔn)6.6 應(yīng)用36.1 數(shù)字簽名概念在政治、軍事、外交、商業(yè)和日常生活中，人們經(jīng)常需要對(duì)紙質(zhì)材料進(jìn)行簽名。簽名起到確認(rèn)、核準(zhǔn)、生效和負(fù)責(zé)任等

2、多種作用。隨著計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)的發(fā)展，電子商務(wù)、電子政務(wù)和電子金融等系統(tǒng)得到廣泛應(yīng)用，人們需要通過網(wǎng)絡(luò)信息傳輸對(duì)電子的文件、契約、合同、信件和張單等進(jìn)行數(shù)字簽名以替代手寫簽名。46.1 數(shù)字簽名概念簽名是證明當(dāng)事人的身份和數(shù)據(jù)真實(shí)性的一種信息。在傳統(tǒng)的以書面文件為基礎(chǔ)的事物處理中，采用書面簽名的形式，如手簽、手印和印章等。書面簽名得到司法部門的支持，具有一定的法律意義56.1 數(shù)字簽名概念在以計(jì)算機(jī)文件為基礎(chǔ)的現(xiàn)代事物處理中，應(yīng)采用電子形式的簽名，即數(shù)字簽名（digital signature）。數(shù)字簽名的目的是提供一種手段，使得一個(gè)實(shí)體把他的身份與某個(gè)信息捆綁在一起。一個(gè)信息的數(shù)字簽名實(shí)際上是

3、一個(gè)數(shù)，它僅僅依賴于簽名者的密鑰和被簽名的消息。 10011100010100011000sigK密鑰K66.1.1 數(shù)字簽名的基本概念（1）消息空間:由所有任意長(zhǎng)度消息組成的集合 （2）簽名空間: 由所有簽名組成的集合。簽名長(zhǎng)度不超過n。（3）密鑰空間: （4）sigK稱為簽名算法（signing algorithm） 一個(gè)數(shù)字簽名體制是一個(gè)滿足以下條件的五元組: 76.1.1 數(shù)字簽名的基本概念（5）verK稱為驗(yàn)證算法（verification algorithm）（6） 則將數(shù)據(jù)對(duì)（x，y）稱為消息x的一個(gè)數(shù)字簽名，或直接把y稱為消息x的數(shù)字簽名86.1.1 數(shù)字簽名的基本概念數(shù)字簽名

4、基本要求對(duì)每一個(gè)密鑰K, sigK和verK應(yīng)該是多項(xiàng)式時(shí)間函數(shù)verK是公開的函數(shù), 而sigK是保密的 給定一個(gè)消息x, 除了發(fā)送者本人以外, 任何其他人找到滿足verK(x,y)為真的數(shù)字簽名y,應(yīng)該是計(jì)算上不可行的如果攻擊者能夠找到滿足verK(x,y)的數(shù)據(jù)對(duì)(x,y),而發(fā)送者事先又沒有對(duì)x簽名,則稱y是偽造(forgery)的數(shù)字簽名。 數(shù)字簽名算法必須滿足的條件簽名者事后不能否認(rèn)自己的簽名；其他人不能偽造簽名；當(dāng)通信雙方為簽名真?zhèn)伟l(fā)生爭(zhēng)執(zhí)時(shí), 可以由第三方解決爭(zhēng)端96.1.1 數(shù)字簽名的基本概念手寫簽名與數(shù)字簽名的區(qū)別手寫簽名是所簽文件的物理組成部分，數(shù)字簽名必須與所簽文件捆綁

5、在一起。手寫簽名通過與標(biāo)準(zhǔn)簽名進(jìn)行比較或檢查筆跡來驗(yàn)證，數(shù)字簽名是通過驗(yàn)證算法來驗(yàn)證。手寫簽名容易偽造，好的數(shù)字簽名算法應(yīng)該使偽造簽名十分困難。手寫簽名不易復(fù)制。數(shù)字簽名是一個(gè)二進(jìn)制串，容易復(fù)制。所以必須防止數(shù)字簽名重復(fù)使用。106.1.1 數(shù)字簽名的基本概念簽名算法進(jìn)行分類按應(yīng)用目的普通數(shù)字簽名特殊目的數(shù)字簽名: 不可否認(rèn)數(shù)字簽名、盲簽名、群簽名等按驗(yàn)證方法在驗(yàn)證時(shí)需要輸入被簽名信息在驗(yàn)證時(shí)自動(dòng)恢復(fù)被簽名信息按簽名時(shí)是否使用隨機(jī)數(shù)分成確定性數(shù)字簽名隨機(jī)數(shù)字簽名116.1.2 數(shù)字簽名的基本構(gòu)造方法利用Hash函數(shù)和加密算法可以構(gòu)造有效的數(shù)字簽名方案。基于Hash函數(shù)和單鑰密碼算法構(gòu)造數(shù)字簽名

6、 126.1.2 數(shù)字簽名的基本構(gòu)造方法基于Hash函數(shù)和雙鑰密碼算法構(gòu)造數(shù)字簽名136.1.2 數(shù)字簽名的基本構(gòu)造方法具有保密作用的數(shù)字簽名雙鑰密碼體制：SK是發(fā)送方的私鑰，PK是發(fā)送方的公鑰， E1和D1分別是加密算法與解密算法。單鑰密碼體制密鑰：K是雙方公用密鑰，E2和D2分別是對(duì)應(yīng)的加密算法和解密算法。 14 6.1.3 數(shù)字簽名的安全需求數(shù)字簽名的攻擊模型唯密鑰攻擊（keyonly attack） 攻擊者E擁有簽名者A的公鑰K，因而能夠計(jì)算驗(yàn)證函數(shù)verK。已知消息攻擊（known message attack） 攻擊者E擁有一系列以前由簽名者A所簽名的消息。即E具有數(shù)據(jù)對(duì)（xi，y

7、i），其中xi是消息，yi=sigK (xi)是A對(duì)xi的簽名（i=1, 2, ）。選擇消息攻擊（chosen message attack） 攻擊者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, ）。15 6.1.3 數(shù)字簽名的安全需求攻擊者對(duì)數(shù)字簽名系統(tǒng)的攻擊目的完全破譯（total break） 攻擊者E能確定簽名者A的私鑰K，因而能夠計(jì)算簽名函數(shù)sigK，可以對(duì)任何消息產(chǎn)生有效的簽名。選擇性偽造（selective forgery）

8、攻擊者E能以某一個(gè)不可忽略的概率對(duì)另外某個(gè)人選定的消息產(chǎn)生一個(gè)有效的簽名。也就是說，如果給E選定一個(gè)消息x，那么他能以一個(gè)正的概率找到x的簽名y=sigK(x)，并且簽名者A以前未對(duì)x簽名。存在性偽造（existential forgery） 攻擊者E至少能夠?yàn)橐粋€(gè)消息產(chǎn)生一個(gè)有效的簽名。也就是說，E可能生成一個(gè)數(shù)據(jù)對(duì)（x，y），其中x是消息，y=sigK(x)。簽名者A以前未對(duì)x簽名。16 6.1.3 數(shù)字簽名的安全需求Hash函數(shù)與數(shù)字簽名的安全性對(duì)消息的散列值簽名17 6.1.3 數(shù)字簽名的安全需求使用已知消息攻擊的存在性偽造 攻擊者E從一個(gè)有效的簽名(x, y)開始,其中y=sigK(

9、h(x).然后他計(jì)算z=h(x),并企圖找到xx,使得h(x)=h(x).如果E能做到這一點(diǎn),則(x, y)就是一個(gè)有效的簽名, 從而y是消息x的一個(gè)偽造簽名.為了阻止這種攻擊, 必須要求Hash函數(shù)h是弱無碰撞的.使用選擇消息攻擊的存在性偽造 攻擊者E首先找到xx, 使得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)無碰撞的.18 6.1.3 數(shù)字簽名的安全需求使用唯密鑰攻擊的存在性偽造 當(dāng)簽名算法遭到唯密鑰攻擊時(shí), 即攻擊者E擁有簽名者

10、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是單向的.19第6章 數(shù)字簽名6.1 數(shù)字簽名概念6.2 RSA數(shù)字簽名體制 6.3 ElGamal數(shù)字簽名體制 6.4 其它數(shù)字簽名方案6.5 數(shù)字簽名標(biāo)準(zhǔn)6.6 應(yīng)用20 6.2 RSA數(shù)字簽名體制利用RSA加密算法構(gòu)造的數(shù)字簽名稱為RAS數(shù)字簽名體制。6.2.1 RSA算法描述1密鑰生成算法選取兩個(gè)大素?cái)?shù)p，q，計(jì)算 n=pq，(n)=( p 1) ( q 1

11、)。任選整數(shù)e，滿足： 0 e (n)，且gcd(e ,(n)=1。用擴(kuò)展Euclidean算法求e模(n)的逆d，即 ed=1 mod (n)。 簽名者的公鑰: n，e，私鑰: p，q，d。 21 6.2.1 RSA算法描述2簽名算法 設(shè)消息為x，則x的RAS簽名是3驗(yàn)證算法 當(dāng)接收方收到簽名（x，y）后，計(jì)算如果x= x，則y是x的RAS簽名。226.2.2 RSA數(shù)字簽名的安全性1一般攻擊攻擊方法: 設(shè)n與e為用戶A的公鑰，攻擊者首先隨意選擇一個(gè)數(shù)據(jù)y，并用A的公鑰計(jì)算 x=ye mod n， 于是可以偽造A的一個(gè)RSA數(shù)字簽名（x，y）。因?yàn)?xd =(ye)d =yed =y mod

12、 n， 所以用戶A對(duì)x的RSA數(shù)字簽名是y。這種攻擊實(shí)際上成功的概率是不高的 因?yàn)閷?duì)于選擇的數(shù)據(jù)y，得到的x=ye mod n具有正確語義的概率是很低的。抵抗措施仔細(xì)設(shè)計(jì)數(shù)據(jù)格式對(duì)數(shù)據(jù)的Hash值進(jìn)行簽名236.2.2 RSA數(shù)字簽名的安全性2選擇消息攻擊攻擊方法: 假設(shè)攻擊者E想偽造消息x的簽名，他容易找到兩個(gè)數(shù)據(jù)x1和x2，使得 攻擊者E設(shè)法讓用戶A分別對(duì)x1和x2 進(jìn)行簽名，得到 然后E可以計(jì)算 于是攻擊者E得到了用戶A對(duì)消息x的RSA數(shù)字簽名y抵抗措施用戶不要輕易地對(duì)其他人提供的隨機(jī)數(shù)據(jù)進(jìn)行簽名對(duì)數(shù)據(jù)的Hash值進(jìn)行簽名 246.2.2 RSA數(shù)字簽名的安全性3利用簽名進(jìn)行攻擊從而獲得

13、明文攻擊方法 假設(shè)攻擊者E已截獲了秘文c=xe mod n，他想求出明文x。于是，他選擇一個(gè)小的隨機(jī)數(shù)r，并計(jì)算 因?yàn)閟=re,所以sd=( re)d= mod n，r=sd mod n.然后E 設(shè)法讓簽名者對(duì)l簽名. 于是E又獲得k=ld mod n. 攻擊者E再計(jì)算： 于是，獲得了秘文x。抵抗措施用戶不要輕易地對(duì)其他人提供的隨機(jī)數(shù)據(jù)進(jìn)行簽名對(duì)數(shù)據(jù)的Hash值進(jìn)行簽名 256.2.2 RSA數(shù)字簽名的安全性4對(duì)先加密后簽名方案的攻擊攻擊方法 假設(shè)簽名者A采用先加密后簽名的方案把消息x發(fā)送給接收者B ,則他先用B的公開密鑰eB對(duì)x加密, 然后用自己的私鑰dA簽名.設(shè)A的模數(shù)為nA,B的模數(shù)為n

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

15、直接對(duì)消息進(jìn)行簽名，而應(yīng)該對(duì)消息的Hash值進(jìn)行簽名。要采用先簽名后加密的方式，而不要采用先加密后簽名的方式。27第6章 數(shù)字簽名6.1 數(shù)字簽名概念6.2 RSA數(shù)字簽名體制 6.3 ElGamal數(shù)字簽名體制 6.4 其它數(shù)字簽名方案6.5 數(shù)字簽名標(biāo)準(zhǔn)6.6 應(yīng)用286.3 ElGamal數(shù)字簽名體制在1985年，ElGamal T. 提出了一個(gè)基于離散對(duì)數(shù)問題的數(shù)字簽名體制，通常稱為ElGamal數(shù)字簽名體制。ElGamal簽名體制的安全性主要是基于有限域上離散對(duì)數(shù)問題的難解性。296.3.1 ElGamal簽名算法描述1參數(shù)生成算法選取一個(gè)大素?cái)?shù)p，gZp*是一個(gè)本原元，p和g是系統(tǒng)

16、公開參數(shù)。任選整數(shù)x，滿足：1xp2。計(jì)算 y=gx mod p. 簽名者的公鑰為y，私鑰為x。2簽名算法 設(shè)MZp*為待簽名的消息。簽名者隨機(jī)選擇一個(gè)秘密整數(shù)k，1kp2，計(jì)算 簽名者對(duì)M的ElGamal簽名為: 簽名者將數(shù)據(jù)(M,(r,s)發(fā)送給接收者。306.3.1 ElGamal簽名算法描述3驗(yàn)證算法 接收方收到簽名(M, (r,s) 后，驗(yàn)證 是否成立，如果等號(hào)成立，則確認(rèn)(r, s)是M的有效簽名。有效性證明 因此，如果（r，s）是M的正確簽名，則一定有316.3.1 ElGamal簽名算法描述ElGamal數(shù)字簽名是一個(gè)隨機(jī)的數(shù)字簽名體制 例6.1 設(shè)p=11，g=2是Z11*的

17、本原元。選取私鑰為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)?26.3.2 ElGamal數(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ì)算水平來看，p至少應(yīng)該是二進(jìn)制512位的素?cái)?shù)，從長(zhǎng)期安全性考慮，應(yīng)使用10

18、24位或更長(zhǎng)的素?cái)?shù)。p1最好有大的素因子私鑰x最好是Zp*的素?cái)?shù)階子群的生成元。336.3.2 ElGamal數(shù)字簽名的安全性 1不知道私鑰的攻擊 假設(shè)攻擊者E不知道私鑰x，要想偽造消息M的簽名(r,s), 則E可能使用的攻擊方式有：(1) 攻擊者已知消息M,選擇一個(gè)值r,再求另一個(gè)值s.此時(shí),因?yàn)橛?所以攻擊者E必須計(jì)算離散對(duì)數(shù)。 (2) 攻擊者已知消息M,選擇一個(gè)值s,再求另一個(gè)值r. 此時(shí), 他必須從同余方程 中求出r。這是一個(gè)到目前為止還沒有可行方法求解的方程，甚至也看不出它與離散對(duì)數(shù)問題有沒有關(guān)系。346.3.2 ElGamal數(shù)字簽名的安全性 1不知道私鑰的攻擊 (3) 攻擊者已知

19、消息M，同時(shí)求(r,s). 即他必須從同余方程 中同時(shí)求出(r,s)?，F(xiàn)在人們對(duì)這個(gè)方程的認(rèn)識(shí)幾乎是一無所有，既沒有人發(fā)現(xiàn)解這個(gè)問題的方法，也沒有人能夠證明不能解這個(gè)問題。 (4)攻擊者選擇數(shù)據(jù)對(duì)(r,s)，求消息M。此時(shí)必須計(jì)算離散對(duì)數(shù)356.3.2 ElGamal數(shù)字簽名的安全性 1不知道私鑰的攻擊 (5)攻擊者同時(shí)選擇數(shù)據(jù)M，r和s，使得(r, s)是M的簽名。這種攻擊方法可能獲得成功。攻擊者首先選擇整數(shù)i和j，0i, jp2，gcd( j, p1)=1，計(jì)算 成立，所以(r, s) 是消息M的有效簽名 該攻擊方法屬于存在性偽造。因此，在使用ElGamal數(shù)字簽名方案時(shí)，不要直接對(duì)消息進(jìn)

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

21、式,可以抵抗這類攻擊. 386.3.2 ElGamal數(shù)字簽名的安全性 使用ElGamal數(shù)字簽名方案的安全措施 (1) 不要泄露隨機(jī)數(shù)k(2) 不要使用同一個(gè)隨機(jī)數(shù)k給兩個(gè)不同的消息簽名 設(shè)（r，s）是消息M的簽名，（u，v）是消息W的簽名，使用的是同一個(gè)隨機(jī)數(shù)k，則可求出私鑰。 396.3.3 ElGamal簽名體制的變形ElGamal數(shù)字簽名算法有多種變形設(shè)大素?cái)?shù)p是模數(shù)，g是一個(gè)模p的本原元，x為簽名者的私鑰，k為隨機(jī)數(shù)，m為待簽名的消息，（r，s）是對(duì)M的簽名。簽名值的分量r=gk mod p, 分量s由簽名算法確定。ElGamal數(shù)字簽名各種變形的簽名算法和驗(yàn)證算法見下表。406.

22、3.3 ElGamal簽名體制的變形41第6章 數(shù)字簽名6.1 數(shù)字簽名概念6.2 RSA數(shù)字簽名體制 6.3 ElGamal數(shù)字簽名體制 6.4 其它數(shù)字簽名方案6.5 數(shù)字簽名標(biāo)準(zhǔn)6.6 應(yīng)用426.4.1 FiatShamir數(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是公開參數(shù)，p和q是管理中心CA掌握的密鑰。設(shè)h是一個(gè)公開的Hash函數(shù)，

23、k是一個(gè)固定的正整數(shù)。管理中心CA為用戶A產(chǎn)生k個(gè)公開密鑰： yi (i =1,2,k) 是模n的平方剩余再為用戶A產(chǎn)生k個(gè)私鑰（保密） 436.4.1 FiatShamir數(shù)字簽名2.簽名算法: 為了對(duì)消息m進(jìn)行簽名,用戶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ì)算用戶A對(duì)消息m的數(shù)字簽名為 簽名者將數(shù)據(jù)（m，bij，sj）發(fā)送給接收者B 446.4.1 FiatShamir數(shù)字簽名3驗(yàn)證算法: 接收方B收到簽名數(shù)據(jù)（m,b

24、ij,sj）后, 按以下步驟進(jìn)行驗(yàn)證：（1）利用A的公鑰計(jì)算（2）計(jì)算Hash函數(shù)值依次取出其前kt個(gè)比特值，記為（3）比較等式 是否成立。如果kt個(gè)等式全部成立，則數(shù)字簽名有效。否則，數(shù)字簽名無效。456.4.1 FiatShamir數(shù)字簽名該驗(yàn)證算法的正確性 當(dāng)數(shù)據(jù)傳輸正確時(shí)，有466.4.1 FiatShamir數(shù)字簽名例6.4 設(shè)n=35，k=4，用戶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）. 476.4.1 FiatS

25、hamir數(shù)字簽名例6.4 設(shè)n=35，k=4，用戶A的4個(gè)公鑰為：y1 =4，y2 =11，y3 =16，y4 =29。數(shù)字簽名為（1,0,1,1, 26）. 所以數(shù)字簽名有效。接收方驗(yàn)證方法如下。由于486.4.2 一次性數(shù)字簽名一次性簽名方案是指一對(duì)公、私鑰只能用于對(duì)一個(gè)消息進(jìn)行簽名的方案，它通常被用于芯片卡（chipcards)。1978年，M.O. Rabin首次提出一次性簽名方案。在Rabin一次性簽名方案中，簽名算法使用了對(duì)稱加密算法，驗(yàn)證過程需要驗(yàn)證者與簽名者共同參與。1979年，L. Lamport提出一個(gè)類似的方案，不同之處在于驗(yàn)證時(shí)不需要驗(yàn)證者與簽名者交互。該方案由于受到

26、著名密碼學(xué)家Diffie和Hellman的重視而有名。1992年，Bos與Chaum對(duì)Lamport的另一個(gè)更有效的一次性簽名方案做了本質(zhì)的改進(jìn)，并證明了改進(jìn)的簽名方案在選擇消息攻擊下是不可偽造的。496.4.2 Lamport一次性數(shù)字簽名 (1) 密鑰生成：已知單向函數(shù)f：YZ。在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為公鑰。 506.4.2 Lamport一次性數(shù)字簽名 (2) 簽名算法 設(shè)消息x=(xk xk-1x

27、2 x1)是二進(jìn)制串，則對(duì)消息x的簽名為： ui =yi,j | 1ik, xi=j。 (3) 驗(yàn)證算法 若 f(ui) | 1ik包含在公鑰中，則簽名是合法的。516.4.2 Lamport一次性數(shù)字簽名 例6.5 取素?cái)?shù)p=7879，已知3是Z7879的本原元。定義f(x)=3x mod 7879，令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 =2009 mod 7879, z1,1=3810, z2,0=4672, z2,1=4721

28、, 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)。526.4.2 Lamport一次性數(shù)字簽名 例6.5 取素?cái)?shù)p=7879，已知3是Z7879的本原元。接收方驗(yàn)證時(shí)計(jì)算： 3735 mod 7879=3810, 32464 mod 7879=4721, 34285 mod 7879=268.對(duì)手雖然不能從zi,j求出yi,j，但是用這個(gè)簽名方案

29、對(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的簽名。 536.4.2 Bos-Chaum 一次性數(shù)字簽名 Bos-Chaum一次性簽名方案的簽名比Lamport方案的簽名短。設(shè)A=1，2，2n是2n元集合，B是A的所有n元子集構(gòu)成的集合，則有|B|=C2nn。定義Bos-Chaum簽名方案使用的單射函數(shù)為： ：0,1kB， 它把長(zhǎng)為k的字符串映射到A的n元子集，這里2k

30、 C2nn546.4.2 Bos-Chaum 一次性數(shù)字簽名 (1) 密鑰生成 設(shè) f：YZ是單向函數(shù)，取y1，y2，y2nY作為私鑰，z1，z2，z2nZ作為公鑰，其中f(yi)=zi (1i2n)。(2) 簽名算法 設(shè)消息x=(xkxk-1x2x1)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的合法簽名。556.4.2 Bos-Chaum 一次性數(shù)字簽名 由于f是單向函數(shù)，對(duì)手不可能偽造消息的Bos-Chaum簽名。 如果使用Bos-Chaum方案

31、簽了兩個(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。所以該簽名方案是一次性簽名方案。566.4.3 不可否認(rèn)數(shù)字簽名對(duì)于以前討論的數(shù)字簽名，任何人都可以對(duì)簽名進(jìn)行驗(yàn)證。但在某些特殊應(yīng)用條件下，需要在簽名者參加的情況下才能進(jìn)行驗(yàn)證。具有這種性質(zhì)的數(shù)字簽名稱為不可否認(rèn)簽名方案(undeniable si

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

33、twerpen在1989年提出的不可否認(rèn)數(shù)字簽名方案 (1) 密鑰生成(2) 簽名算法 對(duì)消息m的簽名是: s=mx mod p。586.4.3 不可否認(rèn)數(shù)字簽名 (3) 驗(yàn)證協(xié)議 假設(shè)簽名者A想否認(rèn)一個(gè)“由簽名生成算法構(gòu)造出來的”合法簽名，其方式有：拒絕參與驗(yàn)證協(xié)議；錯(cuò)誤地執(zhí)行驗(yàn)證協(xié)議；即使驗(yàn)證協(xié)議成功，也斷言簽名是偽造的。對(duì)于前者很明顯，而后兩種情況難以防范。使用“否認(rèn)協(xié)議”（disavowal protocol）能夠確定是簽名者A試圖否認(rèn)一個(gè)由簽名算法得出的簽名，還是簽名本身是偽造的。否認(rèn)協(xié)議由兩遍驗(yàn)證協(xié)議組成。596.4.3 不可否認(rèn)數(shù)字簽名 (4) 否認(rèn)協(xié)議 進(jìn)行一致性檢驗(yàn)，若C=C

34、，則s是對(duì)m的偽造簽名；若CC，則s是對(duì)m的合法簽名，簽名者試圖否認(rèn).606.4.3 不可否認(rèn)數(shù)字簽名 否認(rèn)協(xié)議的性質(zhì) 性質(zhì)1 如果驗(yàn)證者和簽名者都正確執(zhí)行協(xié)議，則必有C=C，說明s是對(duì)m的偽造簽名，即 性質(zhì)2 性質(zhì)3616.4.4 盲簽名 對(duì)于前面介紹的數(shù)字簽名，簽名者知道所簽名的消息。但在數(shù)字現(xiàn)金、電子投票等應(yīng)用領(lǐng)域，要求簽名者不能知道所簽名的消息。簽名者對(duì)所簽署消息和對(duì)消息的簽名都不可見的數(shù)字簽名稱為盲簽名（blind signature） 盲簽名由D. Chaum在1982年首次提出 626.4.4 盲簽名 盲簽名過程 A是消息m的擁有者, 稱為求簽名者B稱為簽名者 盲簽名需要兩個(gè)基本

35、構(gòu)件：1) 求簽名者A知道的盲化函數(shù)f 及脫盲函數(shù)g。f與g必須滿足： g(SB(f(m)=SB(m)。2)簽名者B的數(shù)字簽名方案SB。636.4.4 盲簽名 考慮盲簽名在電子貨幣中的應(yīng)用，例如顧客A得到銀行B對(duì)錢款m的盲簽名后，自己算出銀行的真正簽名SB(m)。在支付時(shí)提交出m和SB(m)，銀行能驗(yàn)證SB(m)是否為m的合法簽名，但不知道這是誰的一筆消費(fèi)。從而使A保持匿名狀態(tài)，即消費(fèi)行為不受到監(jiān)控。 646.4.4基于RSA公鑰密碼系統(tǒng)的Chaum盲簽名Chaum提出的盲簽名方案是基于RSA公鑰密碼系統(tǒng)的 (1) 密鑰生成: 選取素?cái)?shù)p、q，令nB=pq，1bB(nB)且gcd(bB, nB

36、)=1，隨機(jī)選取1aB(nB)使得aBbB1 mod (nB)。 簽名者B的公鑰是（nB，bB），私鑰是aB。656.4.4基于RSA公鑰密碼系統(tǒng)的Chaum盲簽名(2)盲簽名協(xié)議：設(shè)需簽名的消息為m (3)盲簽名驗(yàn)證算法 666.4.4基于離散對(duì)數(shù)問題的盲簽名 瑞士學(xué)者J. Lcamenisch, J. M. Pivetean提出了基于離散對(duì)數(shù)問題的盲簽名 (1) 密鑰生成: 簽名者選擇兩個(gè)大素?cái)?shù)p，q，q|(p1)，在Zp*上離散對(duì)數(shù)問題是難解問題。a是Zp*的q階元。選取私鑰x，令y=ax mod p，（p，q，a，y）為公鑰。 676.4.4基于離散對(duì)數(shù)問題的盲簽名 (2)盲簽名協(xié)議：

37、設(shè)A需簽名的消息為m，盲簽名由簽名者B開始 (3)盲簽名驗(yàn)證算法 68第6章 數(shù)字簽名6.1 數(shù)字簽名概念6.2 RSA數(shù)字簽名體制 6.3 ElGamal數(shù)字簽名體制 6.4 其它數(shù)字簽名方案6.5 數(shù)字簽名標(biāo)準(zhǔn)6.6 應(yīng)用696.5.1 美國(guó)數(shù)字簽名標(biāo)準(zhǔn)數(shù)字簽名標(biāo)準(zhǔn)（DSS: Digital Signature Standard）由美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)研究所（NIST）于1991年提出，并于1994年正式成為美國(guó)聯(lián)邦信息處理標(biāo)準(zhǔn)（FIPS PUB186），這標(biāo)志著數(shù)字簽名已得到政府的支持。DSS使用的簽名算法稱為數(shù)字簽名算法（DSA: Digital Signature Algorithm）。

38、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ān)法律，正式承認(rèn)數(shù)字簽名的法律意義。這是數(shù)字簽名得到法律支持的重要標(biāo)志。 706.5.1 美國(guó)數(shù)字簽名標(biāo)準(zhǔn)(1) 算法參數(shù): DSA使用的參數(shù)如下 p，q，g是公開參數(shù)，可為一組用戶公用x和y分別為一個(gè)簽名者的私鑰和公鑰，私鑰x用于產(chǎn)生簽名，必須保密 所有這些參數(shù)可在一定時(shí)間內(nèi)固定716.5.1 美國(guó)數(shù)字簽名標(biāo)準(zhǔn)(2) 簽名算法：設(shè)SHA是一個(gè)安全hash函數(shù) 726.5.1 美國(guó)數(shù)字簽名標(biāo)準(zhǔn)(3) 驗(yàn)證算法736.5.2 俄羅斯數(shù)字簽名標(biāo)準(zhǔn) 1994年俄羅斯頒布了自己的數(shù)字簽名標(biāo)準(zhǔn)（GOST），1995年啟用，官方稱為GOST R34.1094。GOST算法使用的單向H