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

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

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

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

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

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

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

7、i），其中xi是消息，yi=sigK (xi)是A對xi的簽名（i=1, 2, ）。選擇消息攻擊（chosen message attack） 攻擊者E可以選擇一些消息請求簽名者A簽名。即E選擇消息xi，并將xi發(fā)送給簽名者A，請求A對xi簽名。A計算yi=sigK(xi)，并將yi發(fā)給E。所以，E具有A的有效數(shù)字簽名（xi，yi）（i=1, 2, ）。15 6.1.3 數(shù)字簽名的安全需求攻擊者對數(shù)字簽名系統(tǒng)的攻擊目的完全破譯（total break） 攻擊者E能確定簽名者A的私鑰K，因而能夠計算簽名函數(shù)sigK，可以對任何消息產(chǎn)生有效的簽名。選擇性偽造（selective forgery）

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

9、h(x).然后他計算z=h(x),并企圖找到xx,使得h(x)=h(x).如果E能做到這一點,則(x, y)就是一個有效的簽名, 從而y是消息x的一個偽造簽名.為了阻止這種攻擊, 必須要求Hash函數(shù)h是弱無碰撞的.使用選擇消息攻擊的存在性偽造 攻擊者E首先找到xx, 使得h(x)=h(x). 然后將消息x發(fā)給簽名者A, 并讓A對消息的散列值h(x)簽名, 從而得到y(tǒng)=sigK(h(x). 所以E能夠成功偽造簽名(x, y). 為了阻止這種攻擊,必須要求Hash函數(shù)h是強無碰撞的.18 6.1.3 數(shù)字簽名的安全需求使用唯密鑰攻擊的存在性偽造 當簽名算法遭到唯密鑰攻擊時, 即攻擊者E擁有簽名者

10、A的公鑰K.E就可能對一個隨機的散列值z偽造簽名y=sigK(z). 此時, 如果Hash函數(shù)h不是單向的,則E可能找到一個消息x，使得z=h(x).所以E能夠成功偽造一個簽名(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ù)字簽名標準6.6 應用20 6.2 RSA數(shù)字簽名體制利用RSA加密算法構造的數(shù)字簽名稱為RAS數(shù)字簽名體制。6.2.1 RSA算法描述1密鑰生成算法選取兩個大素數(shù)p，q，計算 n=pq，(n)=( p 1) ( q 1

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

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

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

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

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

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

17、本原元。選取私鑰為x=8，計算公鑰 設簽名者A要對消息M=5進行簽名。簽名者A首先秘密選取一個整數(shù)k=9，計算簽名者A對M=5的ElGamal簽名為（6, 3）。接收者B可以對消息M=5的簽名（6, 3）進行驗證。因為326.3.2 ElGamal數(shù)字簽名的安全性 ElGamal數(shù)字簽名算法的實現(xiàn)需要作一次模指數(shù)運算一次擴展Euclidean算法運算（求隨機數(shù)k的逆元）二次模乘運算前兩個運算可以離線進行是一個隨機的數(shù)字簽名體制 ElGamal數(shù)字簽名體制的參數(shù)pp的選擇與在Zp*中計算離散對數(shù)的算法有直接關系。從目前的計算水平來看，p至少應該是二進制512位的素數(shù)，從長期安全性考慮，應使用10

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

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

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

21、式,可以抵抗這類攻擊. 386.3.2 ElGamal數(shù)字簽名的安全性 使用ElGamal數(shù)字簽名方案的安全措施 (1) 不要泄露隨機數(shù)k(2) 不要使用同一個隨機數(shù)k給兩個不同的消息簽名 設（r，s）是消息M的簽名，（u，v）是消息W的簽名，使用的是同一個隨機數(shù)k，則可求出私鑰。 396.3.3 ElGamal簽名體制的變形ElGamal數(shù)字簽名算法有多種變形設大素數(shù)p是模數(shù)，g是一個模p的本原元，x為簽名者的私鑰，k為隨機數(shù)，m為待簽名的消息，（r，s）是對M的簽名。簽名值的分量r=gk mod p, 分量s由簽名算法確定。ElGamal數(shù)字簽名各種變形的簽名算法和驗證算法見下表。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ù)字簽名標準6.6 應用426.4.1 FiatShamir數(shù)字簽名FiatShamir數(shù)字簽名由A. Fiat和 A. Shamir提出，有時簡記為FS數(shù)字簽名。與RSA數(shù)字簽名相比較，F(xiàn)S數(shù)字簽名的主要優(yōu)勢是速度快，它僅需要RSA的1%4%的模乘法。FS數(shù)字簽名的理論基礎是大整數(shù)素因子分解的困難性。1參數(shù)生成: 選取兩個大素數(shù)p、q，令n=pq。n是公開參數(shù)，p和q是管理中心CA掌握的密鑰。設h是一個公開的Hash函數(shù)，

23、k是一個固定的正整數(shù)。管理中心CA為用戶A產(chǎn)生k個公開密鑰： yi (i =1,2,k) 是模n的平方剩余再為用戶A產(chǎn)生k個私鑰（保密） 436.4.1 FiatShamir數(shù)字簽名2.簽名算法: 為了對消息m進行簽名,用戶A執(zhí)行以下步驟（1）隨機選取一個正整數(shù)t。（2）在1和n之間隨機選取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 446.4.1 FiatShamir數(shù)字簽名3驗證算法: 接收方B收到簽名數(shù)據(jù)（m,b

24、ij,sj）后, 按以下步驟進行驗證：（1）利用A的公鑰計算（2）計算Hash函數(shù)值依次取出其前kt個比特值，記為（3）比較等式 是否成立。如果kt個等式全部成立，則數(shù)字簽名有效。否則，數(shù)字簽名無效。456.4.1 FiatShamir數(shù)字簽名該驗證算法的正確性 當數(shù)據(jù)傳輸正確時，有466.4.1 FiatShamir數(shù)字簽名例6.4 設n=35，k=4，用戶A的4個公鑰為：y1 =4，y2 =11，y3 =16，y4 =29。則A的4個私鑰為：取t=1，r1=16，計算為了簡化，設h(m| R1)=R1=11=1011。即有 數(shù)字簽名為（1,0,1,1, 26）. 476.4.1 FiatS

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

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

27、2 x1)是二進制串，則對消息x的簽名為： ui =yi,j | 1ik, xi=j。 (3) 驗證算法 若 f(ui) | 1ik包含在公鑰中，則簽名是合法的。516.4.2 Lamport一次性數(shù)字簽名 例6.5 取素數(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. 計算公鑰為： 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的簽名。對于x3=0，由i =3，j =0，相應的簽名為u3=y3,0=4285。同理，x2=1相應的簽名為u2=y2,1=2467，x1=1相應的簽名為u1=y1,1=735。所以，對消息x=011的簽名為（4285，2467，735)。526.4.2 Lamport一次性數(shù)字簽名 例6.5 取素數(shù)p=7879，已知3是Z7879的本原元。接收方驗證時計算： 3735 mod 7879=3810, 32464 mod 7879=4721, 34285 mod 7879=268.對手雖然不能從zi,j求出yi,j，但是用這個簽名方案

29、對兩個不同的消息簽名時，對手就能偽造出另一些消息的簽名。 例如，在例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的簽名。 536.4.2 Bos-Chaum 一次性數(shù)字簽名 Bos-Chaum一次性簽名方案的簽名比Lamport方案的簽名短。設A=1，2，2n是2n元集合，B是A的所有n元子集構成的集合，則有|B|=C2nn。定義Bos-Chaum簽名方案使用的單射函數(shù)為： ：0,1kB， 它把長為k的字符串映射到A的n元子集，這里2k

30、 C2nn546.4.2 Bos-Chaum 一次性數(shù)字簽名 (1) 密鑰生成 設 f：YZ是單向函數(shù)，取y1，y2，y2nY作為私鑰，z1，z2，z2nZ作為公鑰，其中f(yi)=zi (1i2n)。(2) 簽名算法 設消息x=(xkxk-1x2x1)2是二進制串，則對消息x的簽名為： a1，a2，an= yj | j(x)。(3) 驗證算法 計算集合C=f(ai), 1in和(x)。如果C=zj | j(x)，則a1，a2，an是對x的合法簽名。556.4.2 Bos-Chaum 一次性數(shù)字簽名 由于f是單向函數(shù)，對手不可能偽造消息的Bos-Chaum簽名。 如果使用Bos-Chaum方案

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

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

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

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

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

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

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

38、2000年1月美國政府將RSA和橢圓曲線密碼引入數(shù)字簽名標準DSS，進一步豐富了DSS的算法。目前，DSS的應用已十分廣泛，并被多個國際標準化組織采納作為標準。美國的一些州已經(jīng)通過相關法律，正式承認數(shù)字簽名的法律意義。這是數(shù)字簽名得到法律支持的重要標志。 706.5.1 美國數(shù)字簽名標準(1) 算法參數(shù): DSA使用的參數(shù)如下 p，q，g是公開參數(shù)，可為一組用戶公用x和y分別為一個簽名者的私鑰和公鑰，私鑰x用于產(chǎn)生簽名，必須保密 所有這些參數(shù)可在一定時間內(nèi)固定716.5.1 美國數(shù)字簽名標準(2) 簽名算法：設SHA是一個安全hash函數(shù) 726.5.1 美國數(shù)字簽名標準(3) 驗證算法736.5.2 俄羅斯數(shù)字簽名標準 1994年俄羅斯頒布了自己的數(shù)字簽名標準（GOST），1995年啟用，官方稱為GOST R34.1094。GOST算法使用的單向H