《《數(shù)字簽名技術(shù)》PPT課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《數(shù)字簽名技術(shù)》PPT課件.ppt（47頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、1/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,應(yīng)用密碼學(xué)手冊 數(shù)字簽名,2/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,參考書籍,Handbook of Applied Cryptography: Chapter 11 數(shù)字簽名理論：趙澤茂 應(yīng)用密碼學(xué)： 孫淑玲 應(yīng)用密碼學(xué)：協(xié)議、算法與C源程序W.迪菲,3/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,11.1 引言 11.2 數(shù)字簽名機(jī)制的框架 11.3 RSA和相關(guān)的簽名方案 11.4 Fiat-Shamir簽名方案 11.5 DSA和相關(guān)簽名方案 11.6 一次數(shù)字簽名 11.7 其他數(shù)字簽名 1

2、1.8 帶附加功能的簽名,主要內(nèi)容：,4/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,11.1 引言,本章要研究的問題,本章要考慮的技術(shù)是如何設(shè)計(jì)手寫簽名的數(shù)字相似物數(shù)字簽名,5/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,研究背景,計(jì)算機(jī)網(wǎng)絡(luò)的產(chǎn)生把我們帶進(jìn)一個(gè)信息化社會(huì)。在信息社會(huì)里，大量傳輸和存儲(chǔ)信息的安全保密和防偽問題成為人們關(guān)注的一個(gè)重要課題。,普遍的觀點(diǎn)認(rèn)為，現(xiàn)代密碼技術(shù)是解決信息安全的最有效地方法，因此，密碼學(xué)的研究成為當(dāng)前國際上的一個(gè)熱點(diǎn)。,6/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,數(shù)字簽名的產(chǎn)生,重要證書、證件采用的防 偽技術(shù)是使用特

3、殊材料或 者信息隱藏等,,網(wǎng) 絡(luò),1.否認(rèn) 2.偽造 3.冒充 4.篡改,,數(shù)字簽名,,7/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,數(shù)字簽名標(biāo)準(zhǔn),ISO/IEC 9796是數(shù)字簽名的第一個(gè)國際標(biāo)準(zhǔn)，1991公布。 1994年美國政府正式頒發(fā)了美國數(shù)字簽名標(biāo)準(zhǔn)DSS(Digital Signature Standard) 1995年我國也制定了自己的數(shù)字簽名標(biāo)準(zhǔn)(GB15851-1995) 2004年我國頒發(fā)中華人民共和國電子簽名法,8/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,數(shù)字簽名的原理,9/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,數(shù)字簽名的功

4、能,1.機(jī)密性 2.完整性 3.身份驗(yàn)證 4.防偽造 5.防抵賴 6.防重放攻擊,10/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,數(shù)字簽名技術(shù)的應(yīng)用,用戶登錄 認(rèn)證 數(shù)據(jù)完整性 不可抵賴性 大型網(wǎng)絡(luò)的公鑰證書中 電子交易和電子貨幣等領(lǐng)域,11/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,準(zhǔn)備知識,1.Hash函數(shù)（即雜湊函數(shù)）（見參考書籍1/1.9） 2.冗余函數(shù) 3.整數(shù)因子分解問題（見參考書籍1/3.2） 4.計(jì)算兩個(gè)整數(shù)的最大公因子的歐幾里得算法 （見參考書籍1/2.1.4） 5.擴(kuò)展的歐幾里得算法（見參考書籍1/2.107） 6.模n平方根的困難性（見參考書籍

5、1/3.5.2） 7.求a模素?cái)?shù)p的平方根（見參考書籍1/3.39） 8.模n的二次剩余集(見參考書籍4/11.3.9) 9.剩余類集合 10.勒讓德符號(見參考書籍4/11.3.10) 11.雅可比符號(見參考書籍4/11.3.11),12/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,11.2 數(shù)字簽名機(jī)制的框架,基本定義,1.數(shù)字簽名是一個(gè)數(shù)字串，它將一條數(shù)字形式的消息與某發(fā) 起實(shí)體相關(guān)聯(lián)。,2.數(shù)字簽名生成算法是產(chǎn)生數(shù)字簽名的某種方法。,3.數(shù)字簽名驗(yàn)證算法是檢驗(yàn)一個(gè)數(shù)字簽名是否可信（即是否 真的是由指定的實(shí)體生成）的某種方法。,4.數(shù)字簽名方案（或機(jī)制）由簽名生成算法和相關(guān)

6、的驗(yàn)證算 法組成。,5.數(shù)字簽名的簽名過程包括數(shù)字簽名生成算法，以及某種將 數(shù)據(jù)格式化為可簽名消息的方法。,6.數(shù)字簽名的驗(yàn)證過程包括驗(yàn)證算法，以及某種由消息恢復(fù) 數(shù)據(jù)的方法。,13/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,數(shù)字簽名機(jī)制中的記號,14/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,數(shù)字簽名方案的分類,帶附錄的數(shù)字簽名方案：要求初始消息作為驗(yàn)證算法的輸入 DSA、ElGamal和Schnorr簽名方案 消息可以是任意長度 帶消息恢復(fù)的數(shù)字簽名方案：消息可從簽名自身恢復(fù)，不要求初始消息作為驗(yàn)證算法的輸入 RSA、Rabin等公鑰簽名方案 通常消息的長度固定

7、,15/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,數(shù)字簽名方案的分類,數(shù)字簽名方案,帶消息恢復(fù),帶附錄,隨機(jī)化的,確定性的,隨機(jī)化的,確定性的,,,,,,,針對一個(gè)數(shù)字簽名方案，如果有 R 1，則稱此簽名方案是隨機(jī)化數(shù)字簽名方案，否則稱它是確定性數(shù)字簽名方案。,16/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,帶附錄的數(shù)字簽名方案,M:消息空間=m Mh：消息摘要空間= S：消息簽名空間=s* h: Hash函數(shù) SA,k: 簽名變換(1-1映射) VA:驗(yàn)證變換,17/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,帶消息恢復(fù)的數(shù)字簽名方案,M:消息空間=

8、m MR：消息的冗余值空間= MS：待簽空間 S：消息的簽名空間=s* R: 冗余函數(shù)（可逆） (1-1映射) SA,k: 簽名變換(1-1映射),18/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,從帶消息恢復(fù)的方案得到帶附錄的簽名方案,先雜湊消息m； 再對該雜湊值h(m)簽名,19/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,簽名方案的攻擊類型,敵手的目標(biāo)是：偽造簽名 完全攻克：敵手能計(jì)算出私鑰 選擇性偽造：敵手能對一個(gè)特殊的消息或者預(yù)先選定的一類消息構(gòu)造出正確的簽名 存在性偽造：敵手能偽造至少一個(gè)消息的簽名，但敵手對被偽造簽名所對應(yīng)的消息幾乎沒有控制能力,20/4

9、7,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,11.3 RSA和相關(guān)簽名方案,RSA簽名方案 有關(guān)RSA簽名的可能攻擊 實(shí)際中的RSA簽名 Rabin簽名方案 ISO/IEC 9796規(guī)范 PKCS #1規(guī)范,21/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,RSA簽名方案,RSA是以它的三個(gè)發(fā)明者Ron Rivest，Adi Shamir和Leoard Adleman的名字命名。 RSA算法既可以用于加密，也可以用于數(shù)字簽名。因?yàn)槠浼用茏儞Q是雙射的，所以只要互換加密與解密的角色就可以得到數(shù)字簽名方案。 RSA的安全性基于大數(shù)分解的困難性，該算法已經(jīng)經(jīng)受住了多年深入的密碼分

10、析，密碼分析者既不能證明也不能否認(rèn)RSA的安全性，這恰恰說明該算法有一定的可信度。,22/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,RSA簽名方案的密鑰生成,實(shí)體A執(zhí)行如下操作： 隨即產(chǎn)生大小相近的兩個(gè)不同大素?cái)?shù)p和q 計(jì)算 n=pq，其歐拉函數(shù)值(n)=(p1)(q1) 隨機(jī)選一整數(shù)e，1e<(n)，滿足gcd((n), e)=1 利用擴(kuò)展的歐幾里德算法，計(jì)算惟一的整數(shù)d， 1d (n),滿足de 1 mod (n) 公鑰為(n，e) ；私鑰為d。(p, q不再需要，可以銷毀。),23/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,RSA的簽名生成與驗(yàn)證,實(shí)體

11、A執(zhí)行如下操作：,為驗(yàn)證A的簽名s且恢復(fù)消息m，B執(zhí)行如下操作：,24/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,RSA簽名實(shí)例講解,1）若Bob選擇了p=11和q13 2）那么，n=11 13=143, (n)=1012120 3）再選取一個(gè)與(n)=120互質(zhì)的數(shù),例如e=7 4）找到一個(gè)值d=103滿足ed1 mod (n) （7103=721，除以120余1） 5）（n=143,e=7）為公鑰，d=103為私鑰。 6）Bob在一個(gè)目錄中公開公鑰：n=143和e=7 7）現(xiàn)假設(shè)Bob想發(fā)送消息85給Alice，他用自己的密鑰 （d=103）進(jìn)行簽名：85103(mod

12、143)=6，于是發(fā)送消息85 和簽名6給Alice 8）當(dāng)Alice接收到消息85和簽名6時(shí)，用Bob公開的公鑰 （e7）進(jìn)行驗(yàn)證：67（mod 143)=85，跟Bob發(fā)送的消 息一致，于是確定該消息是由Bob所發(fā)送，且沒有被修改。,25/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,RSA簽名和RSA加密的異同點(diǎn),相同點(diǎn),都使用一對密鑰：公鑰(n，e)和私鑰d,不同點(diǎn),RSA加密：用公鑰加密，用私鑰解密，多人加密，一人解密 s=me mod n m=sd mod n RSA簽名：用私鑰簽名，用公鑰驗(yàn)證，一人簽名，多人驗(yàn)證 s=md mod n

13、 m=se mod n,26/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,有關(guān)RSA簽名的可能攻擊,整數(shù)因子分解 (公鑰為(n，e) ) de1 mod (n) 分解n=pq 再計(jì)算出(n)=(p1)(q1) 由(n)和e，推導(dǎo)出私鑰d RSA的乘性質(zhì) s1=m1d mod n s2=m2d mod n (s1s2)=(m1m2)d mod n 要求冗余函數(shù)R具有非乘性，即R(ab)R(a) R(b) (必要條件）,為了防止此攻擊，簽署者必須選擇p和q，使得分解n是一個(gè)計(jì)算上不可行的任務(wù)。,為了防止此攻擊，要求冗余函數(shù)R的非乘性。,27/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2

14、020/9/1,實(shí)際中的RSA簽名,通常是：實(shí)體A將消息先簽名再加密，然后發(fā)給B 假設(shè)(nA,eA)和(nB,eB)分別是A和B的公鑰 有以下問題： 1.重分組問題 2.冗余函數(shù)的選擇 3.參數(shù)的選取 4.帶寬效率 5.系統(tǒng)范圍參數(shù) 6.消息長短的比較,28/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,使用RSA簽名的建議,(1)參數(shù)的選?。簆,q,e,d。 (2)不可使用公共模數(shù)。 (3)明文的熵要盡可能的大。 (4)盡量使用散列函數(shù)。 (5)若RSA的模數(shù)n=2k bits，則： 若消息的長度

15、,29/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,Rabin公鑰簽名方案,Rabin公鑰簽名方案與RSA方案類似，不過它使用的公開指數(shù)e是偶數(shù)。為簡單起見，假定e=2.待簽名空間Ms是Qn(模n的二次剩余集)，并且簽名是Qn中元素的平方根。,用到的知識： 1.模n的二次剩余集 2.模n的平方根 3.剩余類的集合 4.合數(shù) 5.勒讓德符號 6.雅可比符號,RSA簽名方案中p和q是不同的素?cái)?shù)，從而(n)=(p1)(q1)是偶數(shù)。而e必須滿足gcd(e, )=1，所以e是奇數(shù)。,30/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,Rabin公鑰簽名方案的密鑰生成,概要：每個(gè)實(shí)

16、體生成各自的公鑰和相應(yīng)私鑰。,1.隨機(jī)產(chǎn)生兩個(gè)不同的大素?cái)?shù)p和q,實(shí)體A執(zhí)行如下操作：,2.計(jì)算n=pq,3.A的公鑰是n，私鑰是(p，q),31/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,Rabin方案的簽名生成和驗(yàn)證,概要：實(shí)體A簽署消息m，任何實(shí)體B都可以驗(yàn)證A的簽名，并從中恢復(fù)消息m。,實(shí)體A執(zhí)行如下操作：,為驗(yàn)證A的簽名s且恢復(fù)消息m，B執(zhí)行如下操作：,32/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,簽名驗(yàn)證： B計(jì)算 。既然 ，那么B接受簽名并恢復(fù)出消息,密鑰生成： 實(shí)體A選擇素?cái)?shù)p=7,q=11,計(jì)算n=77.則A的公鑰是n=77,私鑰

17、是(p=7,q=11)。待簽空間(模n的二次剩余集) MS=Qn=1,4,9,15,16,23,25,36,37,53,58,60,64,67,71。為簡單起見，取M=MS，并且設(shè)冗余函數(shù)R是恒等映射(即 ),簽名生成： 消息m=23，A計(jì)算 ，然后找出 模77的一個(gè)平方根。在此，s=10,32,45,67。選取m的簽名為s=45。,Rabin公鑰簽名方案舉例,33/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,Rabin公鑰簽名方案注意問題,1)選擇合適的冗余函數(shù)R對Rabin簽名方案的安全性極為重要。 2)對Rabin方案而言，設(shè)消息m是比特串，則R可以將它賦值為二

18、元表示是該消息的整數(shù)。然而，卻不能保證那個(gè)整數(shù)是模n的二次剩余，這可能導(dǎo)致無法計(jì)算平方根。所以人們試圖嘗試用確定性方法。,為了克服第二種問題，下面給出基本Rabin簽名方案的一種修改版本。此處用到的技術(shù)類似于ISO/IEC 9796標(biāo)準(zhǔn)，它提供一種確定性方法將消息和待簽空間的元素相關(guān)聯(lián)，從而可計(jì)算平方根。,34/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,修改的Rabin公鑰簽名方案,修改的Rabin簽名方案的待簽消息取自：,下表列出了此方案中的集合和一些函數(shù)定義記號：,35/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,修改的Rabin公鑰簽名方案的密鑰生成,概要：每個(gè)

19、實(shí)體生成各自的公鑰和相應(yīng)的私鑰。 實(shí)體A執(zhí)行如下操作：,1.隨機(jī)選擇素?cái)?shù)p3( mod 8)， q7( mod 8)， 并計(jì)算 n = pq， 2.A的公鑰是n，私鑰是d=(n-p-q+5)/8,36/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,1.簽名生成。實(shí)體A執(zhí)行以下操作： (1)計(jì)算 (2)計(jì)算雅可比符號 (3)若J=1，則計(jì)算 (4)若J=-1，則計(jì)算 (5)A對m的簽名是s,修改的Rabin方案的簽名生成與驗(yàn)證(1),37/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,2.簽名驗(yàn)證。實(shí)體B執(zhí)行以下操作： (1)獲得A的可信公鑰n (2)計(jì)算 （注意不需要初

20、始消息m） (3) (4) (5) (6) (7)驗(yàn)證 ；否則拒絕 (8),修改的Rabin方案的簽名生成與驗(yàn)證(2),38/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,修改的Rabin公鑰簽名方案舉例,密鑰生成：A選擇p=19，q=31，并計(jì)算n=pq=589和d=(n-p-q+5)/8=68。則A的公鑰是n=589，私鑰是d=68.下表列出了待簽名空間MS的每個(gè)元素及其雅可比符號。,39/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,修改的Rabin公鑰簽名方案舉例(續(xù)),簽名生成：,簽名驗(yàn)證：,40/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,ISO

21、/IEC 9796 規(guī)范,是數(shù)字簽名的第一個(gè)國際標(biāo)準(zhǔn)，1991公布。 它規(guī)定了一套數(shù)字簽名程序，并采用一種帶消 息恢復(fù)的數(shù)字簽名機(jī)制 主要特點(diǎn)： 基于公鑰密碼學(xué) 未指定特定簽名算法，但必須是k bits映射為k bits 用于簽署有限長度的消息 提供消息恢復(fù) 描述了必需的消息填充 RSA、Rabin算法,41/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,PKCS#1規(guī)范,公鑰密碼技術(shù)標(biāo)準(zhǔn)(PKCS)是包含RSA加密和簽名的技術(shù)的一套規(guī)范 PKCS #1 不采用RSA簽名方案的消息恢復(fù)特性 采用帶附錄的簽名機(jī)制 使用Hash函數(shù)(MD2或MD5),42/47,蘭州交通大學(xué)電子與信息

22、工程學(xué)院,2020/9/1,11.4 Fiat-Shamir簽名方案,是由Fiege-Fiat-Shamir身份識別方案轉(zhuǎn)變而來的 安全性基于計(jì)算模n平方根的困難性 簽名生成的計(jì)算量遠(yuǎn)遠(yuǎn)小于RSA簽名 適合于需快速執(zhí)行簽名生成、且不限制密鑰空間存儲(chǔ)量的應(yīng)用 實(shí)體A對消息簽名后，再由實(shí)體B來驗(yàn)證簽名的有效性。具體包含： 密鑰生成 簽名生成和驗(yàn)證,43/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,Feige-Fiat-Shamir簽名方案的密鑰生成,隨機(jī)產(chǎn)生不同的私密素?cái)?shù)p和q(保密，最好用完丟棄)，計(jì)算n=pq，并公開n。 選擇正整數(shù)k及k個(gè)與n互素、且互不相同的隨機(jī)整數(shù)作為私鑰s1

23、, s2, ,sk(1si

24、B執(zhí)行如下操作： （已知(e,y)和m) 1.獲得A的可信公鑰(v1, v2 , vk)和n 2.計(jì)算 3.計(jì)算e=h( m || w ) 4.當(dāng)且僅當(dāng)e=e時(shí)接受簽名,概要：實(shí)體A簽署任意長的二元消息m。任意實(shí)體B都可以用A的公鑰驗(yàn)證該簽名。,45/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,簽名驗(yàn)證可行性的證明,實(shí)質(zhì)上證明：w=u,46/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,Feige-Fiat-Shamir簽名方案的安全性,1.與RSA簽名方案不一樣，該方案所有實(shí)體都可以使用相同的模數(shù)n。在這種情形下，需要一個(gè)可信第三方(TTP)產(chǎn)生素?cái)?shù)p和q，以及每個(gè)實(shí)體的公鑰和私鑰。 2. Feige-Fiat-Shamir簽名方案的安全性基于計(jì)算模n平方根的困難性。已經(jīng)證明：只要因子分解是困難的，h是隨機(jī)函數(shù)，并且si互不相同，那么該方案對自適應(yīng)選擇消息攻擊就是安全的。,47/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,謝 謝！,