《《數(shù)字簽名技術(shù)》PPT課件.ppt》由會員分享，可在線閱讀，更多相關(guān)《《數(shù)字簽名技術(shù)》PPT課件.ppt（47頁珍藏版）》請在裝配圖網(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ù)字簽名機制的框架 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è)計手寫簽名的數(shù)字相似物數(shù)字簽名,5/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,研究背景,計算機網(wǎng)絡(luò)的產(chǎn)生把我們帶進一個信息化社會。在信息社會里，大量傳輸和存儲信息的安全保密和防偽問題成為人們關(guān)注的一個重要課題。,普遍的觀點認(rèn)為，現(xiàn)代密碼技術(shù)是解決信息安全的最有效地方法，因此，密碼學(xué)的研究成為當(dāng)前國際上的一個熱點。,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ù)字簽名的第一個國際標(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.機密性 2.完整性 3.身份驗證 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.計算兩個整數(shù)的最大公因子的歐幾里得算法 （見參考書籍1/2.1.4） 5.擴展的歐幾里得算法（見參考書籍1/2.107） 6.模n平方根的困難性（見參考書籍
5、1/3.5.2） 7.求a模素數(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ù)字簽名機制的框架,基本定義,1.數(shù)字簽名是一個數(shù)字串，它將一條數(shù)字形式的消息與某發(fā) 起實體相關(guān)聯(lián)。,2.數(shù)字簽名生成算法是產(chǎn)生數(shù)字簽名的某種方法。,3.數(shù)字簽名驗證算法是檢驗一個數(shù)字簽名是否可信（即是否 真的是由指定的實體生成）的某種方法。,4.數(shù)字簽名方案（或機制）由簽名生成算法和相關(guān)
6、的驗證算 法組成。,5.數(shù)字簽名的簽名過程包括數(shù)字簽名生成算法，以及某種將 數(shù)據(jù)格式化為可簽名消息的方法。,6.數(shù)字簽名的驗證過程包括驗證算法，以及某種由消息恢復(fù) 數(shù)據(jù)的方法。,13/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,數(shù)字簽名機制中的記號,14/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,數(shù)字簽名方案的分類,帶附錄的數(shù)字簽名方案：要求初始消息作為驗證算法的輸入 DSA、ElGamal和Schnorr簽名方案 消息可以是任意長度 帶消息恢復(fù)的數(shù)字簽名方案：消息可從簽名自身恢復(fù)，不要求初始消息作為驗證算法的輸入 RSA、Rabin等公鑰簽名方案 通常消息的長度固定
7、,15/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,數(shù)字簽名方案的分類,數(shù)字簽名方案,帶消息恢復(fù),帶附錄,隨機化的,確定性的,隨機化的,確定性的,,,,,,,針對一個數(shù)字簽名方案，如果有 R 1，則稱此簽名方案是隨機化數(shù)字簽名方案，否則稱它是確定性數(shù)字簽名方案。,16/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,帶附錄的數(shù)字簽名方案,M:消息空間=m Mh：消息摘要空間= S：消息簽名空間=s* h: Hash函數(shù) SA,k: 簽名變換(1-1映射) VA:驗證變換,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)是：偽造簽名 完全攻克：敵手能計算出私鑰 選擇性偽造：敵手能對一個特殊的消息或者預(yù)先選定的一類消息構(gòu)造出正確的簽名 存在性偽造：敵手能偽造至少一個消息的簽名，但敵手對被偽造簽名所對應(yīng)的消息幾乎沒有控制能力,20/4
9、7,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,11.3 RSA和相關(guān)簽名方案,RSA簽名方案 有關(guān)RSA簽名的可能攻擊 實際中的RSA簽名 Rabin簽名方案 ISO/IEC 9796規(guī)范 PKCS #1規(guī)范,21/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,RSA簽名方案,RSA是以它的三個發(fā)明者Ron Rivest，Adi Shamir和Leoard Adleman的名字命名。 RSA算法既可以用于加密，也可以用于數(shù)字簽名。因為其加密變換是雙射的，所以只要互換加密與解密的角色就可以得到數(shù)字簽名方案。 RSA的安全性基于大數(shù)分解的困難性，該算法已經(jīng)經(jīng)受住了多年深入的密碼分
10、析，密碼分析者既不能證明也不能否認(rèn)RSA的安全性，這恰恰說明該算法有一定的可信度。,22/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,RSA簽名方案的密鑰生成,實體A執(zhí)行如下操作： 隨即產(chǎn)生大小相近的兩個不同大素數(shù)p和q 計算 n=pq，其歐拉函數(shù)值(n)=(p1)(q1) 隨機選一整數(shù)e，1e<(n)，滿足gcd((n), e)=1 利用擴展的歐幾里德算法，計算惟一的整數(shù)d， 1d (n),滿足de 1 mod (n) 公鑰為(n，e) ；私鑰為d。(p, q不再需要，可以銷毀。),23/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,RSA的簽名生成與驗證,實體
11、A執(zhí)行如下操作：,為驗證A的簽名s且恢復(fù)消息m，B執(zhí)行如下操作：,24/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,RSA簽名實例講解,1）若Bob選擇了p=11和q13 2）那么，n=11 13=143, (n)=1012120 3）再選取一個與(n)=120互質(zhì)的數(shù),例如e=7 4）找到一個值d=103滿足ed1 mod (n) （7103=721，除以120余1） 5）（n=143,e=7）為公鑰，d=103為私鑰。 6）Bob在一個目錄中公開公鑰：n=143和e=7 7）現(xiàn)假設(shè)Bob想發(fā)送消息85給Alice，他用自己的密鑰 （d=103）進行簽名：85103(mod
12、143)=6，于是發(fā)送消息85 和簽名6給Alice 8）當(dāng)Alice接收到消息85和簽名6時，用Bob公開的公鑰 （e7）進行驗證：67（mod 143)=85，跟Bob發(fā)送的消 息一致，于是確定該消息是由Bob所發(fā)送，且沒有被修改。,25/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,RSA簽名和RSA加密的異同點,相同點,都使用一對密鑰：公鑰(n，e)和私鑰d,不同點,RSA加密：用公鑰加密，用私鑰解密，多人加密，一人解密 s=me mod n m=sd mod n RSA簽名：用私鑰簽名，用公鑰驗證，一人簽名，多人驗證 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 再計算出(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是一個計算上不可行的任務(wù)。,為了防止此攻擊，要求冗余函數(shù)R的非乘性。,27/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2
14、020/9/1,實際中的RSA簽名,通常是：實體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ù)的選取：p,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是不同的素數(shù)，從而(n)=(p1)(q1)是偶數(shù)。而e必須滿足gcd(e, )=1，所以e是奇數(shù)。,30/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,Rabin公鑰簽名方案的密鑰生成,概要：每個實
16、體生成各自的公鑰和相應(yīng)私鑰。,1.隨機產(chǎn)生兩個不同的大素數(shù)p和q,實體A執(zhí)行如下操作：,2.計算n=pq,3.A的公鑰是n，私鑰是(p，q),31/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,Rabin方案的簽名生成和驗證,概要：實體A簽署消息m，任何實體B都可以驗證A的簽名，并從中恢復(fù)消息m。,實體A執(zhí)行如下操作：,為驗證A的簽名s且恢復(fù)消息m，B執(zhí)行如下操作：,32/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,簽名驗證： B計算 。既然 ，那么B接受簽名并恢復(fù)出消息,密鑰生成： 實體A選擇素數(shù)p=7,q=11,計算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計算 ，然后找出 模77的一個平方根。在此，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ù)。然而，卻不能保證那個整數(shù)是模n的二次剩余，這可能導(dǎo)致無法計算平方根。所以人們試圖嘗試用確定性方法。,為了克服第二種問題，下面給出基本Rabin簽名方案的一種修改版本。此處用到的技術(shù)類似于ISO/IEC 9796標(biāo)準(zhǔn)，它提供一種確定性方法將消息和待簽空間的元素相關(guān)聯(lián)，從而可計算平方根。,34/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,修改的Rabin公鑰簽名方案,修改的Rabin簽名方案的待簽消息取自：,下表列出了此方案中的集合和一些函數(shù)定義記號：,35/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,修改的Rabin公鑰簽名方案的密鑰生成,概要：每個
19、實體生成各自的公鑰和相應(yīng)的私鑰。 實體A執(zhí)行如下操作：,1.隨機選擇素數(shù)p3( mod 8)， q7( mod 8)， 并計算 n = pq， 2.A的公鑰是n，私鑰是d=(n-p-q+5)/8,36/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,1.簽名生成。實體A執(zhí)行以下操作： (1)計算 (2)計算雅可比符號 (3)若J=1，則計算 (4)若J=-1，則計算 (5)A對m的簽名是s,修改的Rabin方案的簽名生成與驗證(1),37/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,2.簽名驗證。實體B執(zhí)行以下操作： (1)獲得A的可信公鑰n (2)計算 （注意不需要初
20、始消息m） (3) (4) (5) (6) (7)驗證 ；否則拒絕 (8),修改的Rabin方案的簽名生成與驗證(2),38/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,修改的Rabin公鑰簽名方案舉例,密鑰生成：A選擇p=19，q=31，并計算n=pq=589和d=(n-p-q+5)/8=68。則A的公鑰是n=589，私鑰是d=68.下表列出了待簽名空間MS的每個元素及其雅可比符號。,39/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,修改的Rabin公鑰簽名方案舉例(續(xù)),簽名生成：,簽名驗證：,40/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,ISO
21、/IEC 9796 規(guī)范,是數(shù)字簽名的第一個國際標(biāo)準(zhǔn)，1991公布。 它規(guī)定了一套數(shù)字簽名程序，并采用一種帶消 息恢復(fù)的數(shù)字簽名機制 主要特點： 基于公鑰密碼學(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ù)特性 采用帶附錄的簽名機制 使用Hash函數(shù)(MD2或MD5),42/47,蘭州交通大學(xué)電子與信息
22、工程學(xué)院,2020/9/1,11.4 Fiat-Shamir簽名方案,是由Fiege-Fiat-Shamir身份識別方案轉(zhuǎn)變而來的 安全性基于計算模n平方根的困難性 簽名生成的計算量遠遠小于RSA簽名 適合于需快速執(zhí)行簽名生成、且不限制密鑰空間存儲量的應(yīng)用 實體A對消息簽名后，再由實體B來驗證簽名的有效性。具體包含： 密鑰生成 簽名生成和驗證,43/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,Feige-Fiat-Shamir簽名方案的密鑰生成,隨機產(chǎn)生不同的私密素數(shù)p和q(保密，最好用完丟棄)，計算n=pq，并公開n。 選擇正整數(shù)k及k個與n互素、且互不相同的隨機整數(shù)作為私鑰s1
23、, s2, ,sk(1si
24、B執(zhí)行如下操作： （已知(e,y)和m) 1.獲得A的可信公鑰(v1, v2 , vk)和n 2.計算 3.計算e=h( m || w ) 4.當(dāng)且僅當(dāng)e=e時接受簽名,概要：實體A簽署任意長的二元消息m。任意實體B都可以用A的公鑰驗證該簽名。,45/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,簽名驗證可行性的證明,實質(zhì)上證明：w=u,46/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,Feige-Fiat-Shamir簽名方案的安全性,1.與RSA簽名方案不一樣，該方案所有實體都可以使用相同的模數(shù)n。在這種情形下，需要一個可信第三方(TTP)產(chǎn)生素數(shù)p和q，以及每個實體的公鑰和私鑰。 2. Feige-Fiat-Shamir簽名方案的安全性基于計算模n平方根的困難性。已經(jīng)證明：只要因子分解是困難的，h是隨機函數(shù)，并且si互不相同，那么該方案對自適應(yīng)選擇消息攻擊就是安全的。,47/47,蘭州交通大學(xué)電子與信息工程學(xué)院,2020/9/1,謝 謝！,
《數(shù)字簽名技術(shù)》PPT課件.ppt
