現(xiàn)代密碼學(xué)和應(yīng)用-數(shù)字簽名課件

1、現(xiàn)代密碼學(xué)與應(yīng)用 數(shù)字簽名主講人：余艷瑋E-mail: 2022/8/71參考書籍Handbook of Applied Cryptography: Chapter 11Applied Cryptography: Protocols, algorithms, and source code in C：Section 2.6，5.3，23.4；Chapter 202022/8/72大綱一、數(shù)字簽名的基本概念二、RSA和相關(guān)簽名方案三、Fiat-Shamir簽名方案四、DSA和相關(guān)簽名方案五、其他簽名方案2022/8/73一、數(shù)字簽名的基本概念2022/8/74數(shù)字簽名實質(zhì)上是一個數(shù)值它依賴于只有

2、簽名者知道的某個秘密數(shù)以及待簽消息的內(nèi)容它將一條數(shù)字形式的消息與某發(fā)起實體相關(guān)聯(lián)包含：數(shù)字簽名的簽名過程數(shù)字簽名的驗證過程：不需要簽名者的秘密知識 （任何人都可驗證真?zhèn)危?022/8/75數(shù)字簽名的特點簽名是可信(真實)的:任何人都可以方便的驗證簽名的有效性.簽名是不可偽造的:除了合法的簽名者外,任何其它人偽造簽名是困難的，這種困難性指計算上是不可行的。簽名是不可抵賴的：簽名者不能否認自己的簽名。簽名是不可復(fù)制的：如果簽名是從別的地方復(fù)制的，任何人都可發(fā)現(xiàn)消息與簽名的不一致，從而拒絕簽名。簽名的消息是不可修改的2022/8/76數(shù)字簽名的應(yīng)用認證數(shù)據(jù)完整性不可抵賴性大型網(wǎng)絡(luò)的公鑰證書中2022

3、/8/771994年美國政府正式頒發(fā)了美國數(shù)字簽名標(biāo)準(zhǔn)DSS(Digital Signature Standard)1995年我國也制定了自己的數(shù)字簽名標(biāo)準(zhǔn)(GB15851-1995)2004年我國頒發(fā)中華人民共和國電子簽名法2022/8/78相關(guān)術(shù)語消息M：簽名者可將數(shù)字簽名綴于該集合中的元素之后待簽空間Ms：將簽名變換應(yīng)用于該集合中的元素簽名空間S：與消息m關(guān)聯(lián)的元素的集合，被用來將簽名者綁定到消息R：簽名變換2022/8/79數(shù)字簽名方案的分類帶附錄的數(shù)字簽名方案：要求初始消息M作為驗證算法的輸入DSA、ElGamal和Schnorr簽名方案消息可以是任意長度帶消息恢復(fù)的數(shù)字簽名方案：消

4、息可從簽名自身恢復(fù)，不要求初始消息M作為驗證算法的輸入RSA、Rabin等公鑰簽名方案通常消息的長度固定2022/8/710帶附錄的數(shù)字簽名方案M:消息空間=mMh：消息摘要空間= S：消息簽名空間=s*h: Hash函數(shù)SA,k: 簽名變換(1-1映射)VA:驗證變換2022/8/711帶消息恢復(fù)的數(shù)字簽名方案M:消息空間=mMR：消息的冗余值空間= MS：待簽空間S：消息的簽名空間=s*R: 冗余函數(shù)（可逆） (1-1映射)SA,k: 簽名變換(1-1映射)M:消息空間=mMR：消息的冗余值空間= MS：待簽空間S：消息的簽名空間=s*R: 冗余函數(shù)（可逆） (1-1映射)SA,k: 簽名

5、變換(1-1映射)2022/8/712從帶消息恢復(fù)的簽名產(chǎn)生帶附錄的簽名先雜湊消息m；再對該雜湊值h(m)簽名2022/8/713簽名方案的攻擊類型敵手的目標(biāo)是：偽造簽名完全攻克：敵手能計算出私鑰選擇性偽造：敵手能對一個特殊的消息或者預(yù)先選定的一類消息構(gòu)造出正確的簽名存在性偽造：敵手能偽造至少一個消息的簽名，但敵手對被偽造簽名所對應(yīng)的消息幾乎沒有控制能力2022/8/714二、RSA和相關(guān)簽名方案2022/8/715RSA簽名方案有關(guān)RSA簽名的可能攻擊實際中的RSA簽名ISO/IEC 9796規(guī)范PKCS #1規(guī)范2022/8/716RSA是以它的三個發(fā)明者Ron Rivest，Adi Sh

6、amir和Leoard Adleman的名字命名。RSA算法既可以用于加密，也可以用于數(shù)字簽名。RSA的安全性基于大數(shù)分解的困難性，該算法已經(jīng)經(jīng)受住了多年深入的密碼分析，密碼分析者既不能證明也不能否認RSA的安全性，這恰恰說明該算法有一定的可信度。2022/8/7172.1 RSA簽名方案密鑰生成簽名生成簽名驗證2022/8/718RSA簽名方案的密鑰生成實體A執(zhí)行如下操作：獨立地選取兩大素數(shù)p和q(各100200位十進制數(shù)字)計算 n=pq，其歐拉函數(shù)值(n)=(p1)(q1)隨機選一整數(shù)e，1e(n)，滿足gcd(n), e)=1利用擴展的歐幾里德算法，計算e的乘法逆元d=e -1 mod

7、 (n) 公鑰為(n，e) ；私鑰為d。(p, q不再需要，可以銷毀。)2022/8/719RSA簽名方案的簽名生成和驗證(1)實體A執(zhí)行如下操作：計算整數(shù)計算A對m的簽名為s為驗證A的簽名s及恢復(fù)消息m，實體B：獲得A的可信公鑰(n，e)計算驗證恢復(fù)2022/8/720RSA簽名方案的簽名生成和驗證(2)實體A執(zhí)行如下操作：計算消息的散列值H(m)計算A對m的簽名為(m, s)為驗證A的簽名，實體B：獲得A的可信公鑰(n，e)計算比較H(m)與v1，當(dāng)且僅當(dāng)H(m)=v1時，接受簽名2022/8/7212.2 有關(guān)RSA簽名的可能攻擊整數(shù)因子分解 (公鑰為(n，e) )d=e -1 mod

8、(n)分解n=pq再計算出(n)=(p1)(q1)由(n)和e，推導(dǎo)出私鑰dRSA的乘性質(zhì)s1=m1d mod ns2=m2d mod n(s1s2)=(m1m2)d mod n要求冗余函數(shù)R具有非乘性，即R(ab)R(a) R(b) (必要條件）2022/8/722使用RSA的建議(1)參數(shù)的選?。簆,q,e,d。(2)不可使用公共模數(shù)。(3)明文的熵要盡可能的大。(4)盡量使用散列函數(shù)。(5)若RSA的模數(shù)n=2k bits，則：若消息的長度nB時，B有可能無法恢復(fù)消息2022/8/7242.4 ISO/IEC 9796規(guī)范是數(shù)字簽名的第一個國際標(biāo)準(zhǔn)，1991公布。它規(guī)定了一套數(shù)字簽名程序

9、，并采用一種帶消息恢復(fù)的數(shù)字簽名機制主要特點：基于公鑰密碼學(xué)未指定特定簽名算法，但必須是k bits映射為k bits用于簽署有限長度的消息提供消息恢復(fù)描述了必需的消息填充RSA、Rabin算法2022/8/725m (d bits)MP (8z bits)ME (8t bits)MR (16t bits)IR (k bits)s (k bits)2022/8/7262.5 PKCS #1規(guī)范公鑰密碼技術(shù)標(biāo)準(zhǔn)(PKCS)是包含RSA加密和簽名的技術(shù)的一套規(guī)范PKCS #1規(guī)定了RSA簽名采用帶附錄的簽名機制使用Hash函數(shù)(MD2或MD5)2022/8/727MMDDEBmsED2022/8/

10、728三、 Fiege-Fiat-Shamir簽名方案2022/8/729Fiege-Fiat-Shamir簽名方案是由Fiege-Fiat-Shamir身份識別方案轉(zhuǎn)變而來的安全性基于計算模n平方根的困難性簽名生成的計算量遠遠小于RSA簽名適合于需快速執(zhí)行簽名生成、且不限制密鑰空間存儲量的應(yīng)用實體A對消息簽名后，再由實體B來驗證簽名的有效性。具體包含：密鑰生成簽名生成和驗證2022/8/730Fiege-Fiat-Shamir簽名方案的密鑰生成可信中心T選擇兩個素數(shù)p和q(保密，最好用完丟棄)，計算類似RSA的模數(shù)n=pq、并公開n。實體A選擇k個與n互素、且互不相同的隨機整數(shù)作為私鑰s1,

11、 s2, ,sk(1sin)實體A計算vi=si-2 mod n (1ik)實體A的公鑰(v1, v2 , vk; n)，私鑰(s1, s2, ,sk)2022/8/731Fiege-Fiat-Shamir簽名方案的簽名生成和驗證簽名生成。實體A執(zhí)行如下操作：隨機選擇正整數(shù) r (n) ；計算u=r2 mod n計算e=(e1,ek)=h(m|u)，ei0,1 計算A對m的簽名是(e，y)驗證。實體B執(zhí)行如下操作： （已知(e,y)和m)獲得A的可信公鑰(v1, v2 , vk; n)計算 計算e=h(m|w) 當(dāng)且僅當(dāng)e=e時接受簽名2022/8/732簽名驗證的可行性證明實質(zhì)上證明：w=u

12、2022/8/733方案的安全性所有實體都可使用相同的模數(shù)n需要一個可信第三方(TTP)產(chǎn)生素數(shù)p和q，以及每個實體的公鑰和私鑰安全性基于模n平方根的困難性2022/8/734基于身份的Fiege-Fiat-Shamir簽名可對密鑰生成過程作如下修改：TTP選擇兩個素數(shù)p和q(保密，最好用完丟棄)，計算模數(shù)n=pq、并公開n。TTP計算vj=f(IA|j), (1jk)IA含有A的身份信息的比特串f是Hash函數(shù)計算模n下vj-1的一個平方根sj, (1jk)公鑰(v1, v2 , vk; n):只與身份信息IA相關(guān)私鑰 (s1, s2, ,sk)2022/8/735四、DSA和相關(guān)簽名方案2

13、022/8/736ElGamal簽名方案Schnorr簽名方案數(shù)字簽名算法(DSA)帶附錄的簽名方案帶附錄的簽名方案1、安全性都基于Zp*上的離散對數(shù)計算的困難性2、都是隨機化簽名方案2022/8/7374.1 ElGamal簽名方案密鑰生成。實體A執(zhí)行如下操作：隨機產(chǎn)生一個大素數(shù)p，以及乘法群Zp* 的一個生成元g隨機選擇整數(shù) (0 p-1)計算g mod pA的公鑰(p,g,)，私鑰2022/8/7384.1 ElGamal簽名方案簽名生成。實體A執(zhí)行如下操作：隨機一個秘密整數(shù)k (0 p-1) ，并滿足gcd(k,p-1)=1計算r=gk mod p計算k-1 mod (p-1)計算s=

14、k-1h(m)- r mod (p-1)A對m的簽名是(r,s)簽名驗證。B執(zhí)行如下操作： （已知(r,s)和m)獲得A的可信公鑰(p,g,)驗證0rp；否則拒絕接受該簽名計算v1= rrs mod p計算h(m)和v2=gh(m) mod p當(dāng)且僅當(dāng)v1=v2時接受簽名2022/8/739簽名驗證可行性的證明若簽名(r, s)由A生成，則：2022/8/740ElGamal簽名的安全性若敵手要偽造A的簽名，則必須確定s=k-1h(m)- r mod (p-1) （k由敵手選取，但A的私鑰是保密的)。偽造成功的概率為1/p對每個待簽消息，須選擇不同的k（保密）敵手已知(m1,s1,r,k,p)

15、，很容易就可以計算出敵手已知(m1,s1,r,k,p)，很容易就可以計算出若不同的消息，k相同，則r也相同2022/8/741必須采用雜湊函數(shù)h假設(shè)未采用雜湊函數(shù)，即h(m)=m選取任一整數(shù)對(u,v),gcd(v,p-1)=1，計算：則(r, s)也是對消息m1(=su mod (p-1)的一個有效簽名。存在性偽造！2022/8/742ElGamal簽名方案的變體簽名方案為：u=av+kw mod (p-1)sh(m)rh(m)srrh(m)sh(m)rsrsh(m)srh(m)認證等式簽名方程序號簽名方程為：u=xv+kw mod (p-1)x是私鑰2022/8/7434.2 Schnor

16、r簽名方案密鑰生成。實體A執(zhí)行如下操作： (1)p 及 q 是兩個大素數(shù)，且 q|(p-1); (3)隨機選擇數(shù)a (0aq)，計算y= a mod p (4)A的公鑰是(p,q,y)，私鑰是a2022/8/7444.2 Schnorr簽名方案簽名生成。實體A執(zhí)行如下操作：隨機選擇一個秘密整數(shù)k (0kq)計算r= k mod p，e=h(m|r)和s=ae+k mod qA對m的簽名為(s,e)簽名驗證。B執(zhí)行如下操作： （已知(s,e)和m）獲得A的可信公鑰(p,q,y)計算v= sy-e mod p和e=h(m|v)當(dāng)且僅當(dāng)e=e時接受簽名2022/8/745簽名驗證可行性的證明若(e,

17、s)是A對m的合法簽字，則有v=sy-e=s(-a)e=k=r mod p故，h(m|v)=h(m|r)，即e=e2022/8/746Schnorr簽名方案 vs. ElGamal簽名方案Schnorr簽名方案為Zp*中子集Zq*的生成元簽名較短，由|q|及|H(M)|決定簽名生成只需一次mod q乘法。所需計算量少，速度快。ElGamal簽名方案g為Z*p的生成元，安全性較高簽名長度由|p-1|及|H(M)|決定簽名生成需要兩次（在線）mod (p-1)的乘法運算2022/8/7474.3 DSA-概況由NIST1991年公布1993年公布修改版是美國聯(lián)邦信息處理標(biāo)準(zhǔn)FIPS PUB 186

18、(即DSS)中使用的算法在Elgamal和Schnorr兩個方案基礎(chǔ)上設(shè)計的簽名長度為320bit只能用于數(shù)字簽字，不能用于加密2022/8/7484.3 DSA密鑰生成。實體A執(zhí)行如下操作： (1)選取素數(shù)q ，其中2159 q 2160 (2)選取t (t9)和素數(shù)p，2511+64t q 2512+64t且 q|(p-1); (4)隨機選擇數(shù)a (0aq)，計算y= a mod p (5)A的公鑰是(p,q,y)，私鑰是a2022/8/7494.3 DSA簽名生成。實體A執(zhí)行如下操作：隨機選擇一個秘密整數(shù)k (0kq)計算r= (k mod p) mod q計算k-1 mod qs= k

19、-1h(m)+ar mod qA對m的簽名為(r,s)2022/8/7504.3 DSA簽名驗證。B執(zhí)行如下操作： （已知(r,s)和m）獲得A的可信公鑰(p,q,y)驗證0rq和0sq；否則拒絕該簽名計算w=s-1 mod q 和 h(m)計算u1= wh(m) mod q 和u2=rw mod q計算v= (u1yu2 mod p) mod q當(dāng)且僅當(dāng)v=r時接受簽名2022/8/751簽名驗證可行性的證明若(r,s)是A對m的合法簽字，則有h(m)=-ar+ks (mod q)可推出：wh(m)+arw=k (mod q)即，u1+au2=k mod q(u1 (a)u2 mod p)

20、mod q = (k mod p) mod q即 v=r2022/8/752DSA的爭議（1）DSA的選擇過程不公開，并且提供的分析時間不充分。（2）DSA可能侵犯了其他專利。（3）DSA是由NSA研制的，可能存在餡門。（4）DSA不能用于加密或密鑰分配。（5）DSA比RSA慢，二者產(chǎn)生簽名的速度相同，但簽名驗證DSA比RSA慢40倍。（6）DSA的密鑰長度太短。（7）RSA是一個事實上的標(biāo)準(zhǔn)。2022/8/753五、其他簽名方案2022/8/754仲裁數(shù)字簽名不可否認簽名方案盲簽名方案失敗-停止簽名方案代理簽名團體簽名門限簽名2022/8/7555.1 仲裁數(shù)字簽名2. 3. TTPAB1.

21、 IDA| 4. 消息的簽名KA,KB分別為實體A和B的秘密密鑰;KT是可信第三方(TTP)的秘密密鑰;TTP擁有所有實體的秘密密鑰2022/8/7565.2 不可否認簽名方案驗證協(xié)議要求簽名者合作可以在一定程度上防止復(fù)制或散布產(chǎn)權(quán)所有者（簽名者）所簽字的文件的可能性，從而使產(chǎn)權(quán)所有者可以控制產(chǎn)品的散發(fā)。這在數(shù)字知識版權(quán)保護領(lǐng)域中有用一般的數(shù)字簽名的復(fù)制品也可以來驗證簽名的有效性。如，公開宣傳品的發(fā)布等2022/8/757應(yīng)用在涉及私人隱私的問題上，如簽名的私人信件、商業(yè)函件等，是不希望其他人驗證的。由此1989年，Chaum和Antwerpen等引入了不可否認數(shù)字簽名的概念。假定某公司A制作

22、了一個軟件包。A將該軟件包簽名后賣給實體B。若B決定冒充A將該軟件包復(fù)制后再賣給第三方C，但是沒有A的合作時，B將無法向C驗證該軟件是否正版。2022/8/758密鑰生成實體A執(zhí)行如下操作：(1)選擇素數(shù)p,q，且p=2q+1(2)選擇Zp*的q階子群的生成元 (q = 1 mod p)(3)隨機選取整數(shù)a，并計算y = a mod p(4)A的公鑰為(p,y)，私鑰為a2022/8/759簽名生成和驗證簽名生成。實體A執(zhí)行如下操作：計算s = ma mod pA對消息m的簽名是s驗證：實體B執(zhí)行如下操作：B獲得A的可信公鑰(p,y)B隨機選取秘密整數(shù)x1,x21,2, , q-1B計算z=s

23、x1yx2 mod p，并將z發(fā)送給AA計算w=za-1 mod p，并將w發(fā)送給BB計算w=mx1x2 mod p當(dāng)且僅當(dāng)w=w時，接受簽名2022/8/760 如果簽字者拒絕合作就無法驗證簽名的有效性。但確實是簽字者的數(shù)字簽名，其又拒絕合作時，又如何處理？那么可以在法庭等第三方的監(jiān)督下，啟用拒絕協(xié)議（Disavowal Protocol），以證明簽名的真假。如果對方拒絕參與否認協(xié)議，那么，就是他簽名的；如果不是他簽名的，否認協(xié)議可以確認他沒有簽名。2022/8/761拒絕協(xié)議接收者B選擇隨機數(shù)a、b， 接收者B計算： 將c發(fā)給簽名者A。簽名者A計算： , 將d發(fā)給接收者B； 接收者B驗證：

24、 , 如果等式成立，說明簽名有效，終止協(xié)議。 2022/8/762拒絕協(xié)議接收者再選擇隨機數(shù)i、j, 接收者計算： ，將C發(fā)送給簽名者A ；簽名者A計算： ，將D發(fā)送給接收者B ； 接收者B驗證： 如果等式成立，B接收簽名，并終止協(xié)議。2022/8/763拒絕協(xié)議如果下列等式： 成立，那么接收者B可以判定簽名s是偽造的；否則簽名有效，可說明A在企圖拒絕簽名s。 點評：上面的協(xié)議經(jīng)過了兩個回合，（1）-（4）和（5）-（8）都是認證過程的重復(fù)；最后通過（9）的一致性檢驗可以使接受方B能夠確定出簽名者A是否如實的執(zhí)行了上述規(guī)定的協(xié)議。2022/8/7645.3 盲簽名前面介紹的數(shù)字簽名，簽名者可以

25、查看所簽信息的內(nèi)容，這和日常生活的情形相符合：我們通常需要在知道文件內(nèi)容之后才會簽署。而在有些時候，要求簽名者對所簽署消息是不可見的，就需要盲簽名。盲簽名（blind signature)是由David Chanm于1983年提出的。盲簽名在數(shù)字現(xiàn)金，電子投票等領(lǐng)域都有較大的應(yīng)用價值，特別是目前的數(shù)字現(xiàn)金，大部分都是采用盲簽名的原理實現(xiàn)。2022/8/765盲簽名過程求簽名者進行盲變換仲裁者進行簽名求簽名者進行解盲變換簽名S(M)消息M2022/8/766完全盲簽名協(xié)議 假定請求簽名者為A，簽字者（仲裁者）為B。盲簽名就是要求A讓B簽署一個文件，而不讓B知悉文件的內(nèi)容，僅僅要求以后在需要時B可

26、以對他所簽署的文件進行仲裁。那么可以通過下面稱為完全盲簽名的協(xié)議來完成； （1）A把文件用一個隨機數(shù)乘之，該隨機數(shù)常稱為盲因子（Blinding Factor）。 （2）A將上面處理后的文件盲文件傳送給B。2022/8/767 （3）B對盲文件簽名。 （4）A取回B的簽名結(jié)果，并用盲因子除之，得到B對原文件的簽名。 顯然，在上面的協(xié)議中，如果簽名函數(shù)與乘法可交換，那么上述協(xié)議成立。否則盲變換不能用乘法，而采用其他變換方法。2022/8/768基于RSA的盲簽名算法第一個盲簽名算法的實現(xiàn)是D.Chaum于1985年提出的，該算法使用了RSA算法。下面設(shè)定簽名者B的公鑰參數(shù)為e，私鑰參數(shù)為d，而模為n。 下面A讓B進行盲簽名，簽署消息M： A盲變換：選用盲因子k,1kM ,計算： 將t傳送給BB簽名：B對t進行簽名，計算 ，將簽名S(t)傳送給AA取得簽名：A計算： 該簽名算法顯然成立，S其實就是B對消息M進行的RSA簽名2022/8/769 那么上面協(xié)議中，B可以獲得文件內(nèi)容嗎？如果盲因子是完全隨機數(shù)，顯然B不能獲得所簽署文件內(nèi)容，即使他簽署了A的上萬份文件。但是這些文件確實是他簽署的，并且可以在以