《新編密碼學》課件第6章 數(shù)字簽名

數(shù)字簽名

提供數(shù)據(jù)來源的真實性、數(shù)據(jù)內(nèi)容的完整性、簽名者的不可否認性以及匿名性等信息安全相關的服務和保障。

用于網(wǎng)絡通信的安全以及各種用途的電子交易系統(tǒng)（如電子商務、電子政務、電子出版、網(wǎng)絡學習、遠程醫(yī)療等）中。6.1數(shù)字簽名的基本原理

概念：

數(shù)字簽名是對以數(shù)字形式存儲的消息進行某種處理，產(chǎn)生一種類似于傳統(tǒng)手書簽名功效的信息處理過程。

它通常將某個算法作用于需要簽名的消息，生成一種帶有操作者身份信息的編碼。示例：Alice和Bob進行通信，并使用消息認證碼提供數(shù)據(jù)完整性保護：情況一：Alice向Bob發(fā)送消息并附加了用雙方共享密鑰生成的消息認證碼，但隨后Alice否認曾經(jīng)發(fā)送了這條消息；情況二：Bob有能力偽造一個消息及認證碼并聲稱此消息來自Alice。

分析：如果通信的過程沒有第三方參與的話，這樣的局面是難以仲裁的。

因此，安全的通信僅有消息完整性認證是不夠的，還需要有能夠防止通信雙方相互作弊的安全機制。

數(shù)字簽名

至少滿足的三個基本要求：1）簽名者任何時候都無法否認自己曾經(jīng)簽發(fā)的數(shù)字簽名；

2）收信者能夠驗證和確認收到的數(shù)字簽名，但任何人都無法偽造別人的數(shù)字簽名；

3）當各方對數(shù)字簽名的真?zhèn)萎a(chǎn)生爭議時，通過仲裁機構(gòu)（可信的第三方）進行裁決。數(shù)字簽名與手寫簽名的差異

1）手寫簽名與被簽文

件物理上是一個整

體，不可分離；2）手書簽名通過物理

比對來判斷真?zhèn)危?/p>

需要一定的技藝甚

至需要專門人員，

機構(gòu)來執(zhí)行；3）手書簽名會因人而

異，復制品易于原

件分開。1）數(shù)字簽名與被簽名

的消息是可以相互

分離的比特串；2）數(shù)字簽名通過一個

嚴密的公開的算法

來驗證簽名的真?zhèn)危?）數(shù)字簽名的拷貝與其原件是完全相同的二進制比特串，無法區(qū)分，需防止簽名重復使用?？偨Y(jié)：

※簽名者必須向驗證者提供足夠多的非保密信息，以便驗證者能夠確認簽名者的數(shù)字簽名；

※簽名者不能泄露任何用于產(chǎn)生數(shù)字簽名的機密信息，以防止他人偽造他的數(shù)字簽名。

因此，簽名算法必須能夠提供簽名者用于簽名的機密信息與驗證者用于驗證簽名的公開信息。數(shù)字簽名體制：組成部分：※簽名算法

※驗證算法用于對消息產(chǎn)生數(shù)字簽名，通常受一個簽名密鑰的控制簽名算法或者簽名密鑰是保密的，有簽名者掌握。用于對消息的數(shù)字簽名進行驗證，通常受一個驗證密鑰的控制，驗證算法和驗證密鑰應該公開。數(shù)字簽名體制五元組

※

代表消息空間，它是某個字母表中所有串的集合；

※

代表簽名空間，它是所有可能的數(shù)字簽名構(gòu)成的集合；

※

代表密鑰空間，它是所有可能的簽名密鑰和驗證密鑰對

構(gòu)成的集合；

※

是簽名算法；是驗證算法。對于任意的一個密鑰對，每一個消息和簽名。

簽名變換：和驗證變換

：是滿足下列條件的函數(shù)：數(shù)字簽名的特性

※兩大方面：—功能特性

—安全特性指為了使數(shù)字簽名能夠?qū)崿F(xiàn)需要的的功能要求而應具備的一些特性。確保提供的的功能是安全的，能夠滿足安全需求，實現(xiàn)預期的安全保障。功能特性：

1）依賴性2）獨特性3）可驗證性4）不可偽造性5）可用性一個數(shù)字簽名與被簽消息是緊密相關，不可分割的，離開被簽消息，簽名不再具有任何效用。數(shù)字簽名必須是根據(jù)簽名者擁有的獨特消息來產(chǎn)生的，包含了能夠代表簽名者特有身份的關鍵信息。通過驗證算法能夠準切地驗證一個數(shù)字簽名的真?zhèn)?。偽造一個簽名者的數(shù)字簽名不僅在計算上不可行，而且希望通過重用或者拼接的方法偽造簽名也是行不通的。數(shù)字簽名的生成，驗證和識別的處理過程相對簡單，能夠在普通的設備上快速完成，甚至可以在線處理，簽名的結(jié)果可以存儲和備份。安全特性：

1）單向性2）無碰撞性3）無關性

優(yōu)點：從根本上消除了成功偽造數(shù)字簽名的可能性。對于給定的數(shù)字簽名算法，簽名者使用自己的簽名密鑰sk對消息m進行數(shù)字簽名是計算上容易的，但給定一個消息m和它的一個數(shù)字簽名s，希望推導出簽名者的簽名密鑰sk是計算上不可行的。對于兩個不同消息，在相同的簽名密鑰下的數(shù)字簽名相等的概率是可以忽略的。對于兩個不同的消息，從某個簽名者對其中一個消息的簽名推導出對另一個消息的簽名是不可能的。缺陷：不抵抗竊聽?；诠€密碼的數(shù)字簽名體制發(fā)送方簽名算法驗證算法密鑰空間接受方mcmskpk基于公鑰密碼的加密和簽名體制

注意：先簽名，后加密的順序不能顛倒發(fā)送方密鑰空間解密算法加密算法簽名算法驗證算法密鑰空間接受方mzzcmpk2sk2sk1pk1原始信息Hash算法Hash值加密簽名私鑰原始信息Hash算法Hash值驗證公鑰Hash值=?SenderReceiver數(shù)字簽名的實現(xiàn)方法：數(shù)字簽名的分類

※

直接數(shù)字簽名體制

※

可仲裁的數(shù)字簽名體制直接數(shù)字簽名A：EKSa[M]→BB：EKPa[EKSa[M]]只有A具有KSa，可以進行加密（簽名）任何第三方都可以用KPa驗證簽名只提供簽名功能A：EKPb[EKSa[M]]→BB：EKPa[EKSb[EKPb[EKSa[M]]]]提供加密（KPb）和簽名（KSa）功能KSa、KPa

分別是A的私鑰和公鑰直接數(shù)字簽名A：M‖EKSa[H(M)]→BB：h=H(M)；EKPa[EKSa[H(M)]]=h’；h’=h?H(M)受到Hash算法不可逆的保護只有A能夠生成EKSa[H(M)]提供簽名和鑒別功能A：EKPb[M‖EKSa[H(M)]]→B B：EKSb[EKPb[M‖EKSa[(M)]]]；h=H(M)； EKPa[EKSa[H(M)]]=h’；h’=h?提供加密（KPb）、簽名（KSa）和鑒別（H(M)）功能直接數(shù)字簽名的缺點驗證模式依賴于發(fā)送方的公鑰發(fā)送方要抵賴發(fā)送某一信息時，可能會聲稱其私有密鑰丟失或被竊，從而他人偽造了他的簽名。需要采用與私有密鑰安全性相關的行政管理控制手段來制止或至少是削弱這種情況，但威脅在某種程度上依然存在。改進的方式，例如可以要求被簽名的信息包含一個時間戳（日期與時間），并要求將已暴露的密鑰報告給一個授權(quán)中心。仲裁簽名引入仲裁者所有從發(fā)送方A（Alice）到接收方B（Bob）的簽名信息首先送到仲裁者C（Carol）。C將信息及其簽名進行一系列測試，以檢查其來源和內(nèi)容。C將信息加上日期并與驗證通過的指示一起發(fā)給B。前提條件：所有的參與者必須極大地相信這一仲裁機制的工作。仲裁簽名－單密鑰加密方式A與C之間共享密鑰Kac，B與C之間共享密鑰Kbc;A：M‖EKac[IDA‖H(M)]→CA：計算消息M的散列碼H(M)，用A的標識符IDA

和散列值構(gòu)成簽名，并將消息和經(jīng)Kac加密后的簽名發(fā)送給C；C：EKbc[IDA‖M‖EKac[IDA‖H(M)]‖T]→BC：解密簽名，用H(M)驗證消息M，然后將IDA，M，經(jīng)Kac加密后的簽名和時間戳T一起經(jīng)Kbc加密發(fā)送給B；B：解密C發(fā)來的信息，并將消息M和經(jīng)Kac加密后的簽名保存起來。B不能直接驗證A的簽名問題：C可以看到A給B的所有信息仲裁簽名－單密鑰加密方式驗證簽名B：EKbc[IDA‖M‖EKac[IDA‖H(M)]]→CC：用EKbc恢復IDA，M和簽名EKac[IDA‖H(M)]，然后用EKac解密簽名并驗證散列碼。在這種模式下，B不能直接驗證A的簽名，B認為C的消息正確，只因為他來自于C。因此，雙方必須高度相信C。并且相信C處理爭議時是公正的。A和B之間也可以約定一個對稱密鑰，并使用該密鑰加密明文后，再進行以上的簽名操作，這樣C就無法看到明文的內(nèi)容。問題C與A聯(lián)手可以否認簽名的信息C與B聯(lián)手可以偽造A的簽名仲裁簽名－雙密鑰加密方式A：IDA‖EKSa[IDA‖EKPb[EKSa[M]]]→CA首先用自己的私有密鑰KSa，然后用B的公開密鑰KPb，生成經(jīng)過簽名的密文。最后將該信息以及A的標識符一起用自己的私鑰EKSa簽名后與IDA一起發(fā)送給C。這時加密過的消息對C，以及B以外的其他人都是保密的。C：EKSc[IDA‖EKPb[EKSa[M]]‖T]→BC檢查A的簽名是否有效，并確認消息。然后將包含IDA、經(jīng)A加密并簽名的消息和時間戳的消息用自己的私鑰EKSc簽名后發(fā)送給B。仲裁簽名－的特點在通信之前，各方之間無需共享任何信息，從而避免了聯(lián)手作弊；即使A的私鑰EKSa泄露，只要C的私鑰未泄露，不會有錯誤標定日期的消息被發(fā)送；A發(fā)送給B的消息的內(nèi)容對C和任何除A、B以外的其他人是保密的。引入仲裁簽名只是為了通過仲裁者證明指定信息是由A在指定的時間發(fā)送給B的。并不代表指定信息是由仲裁者簽發(fā)的。6.2RSA數(shù)字簽名

RSA簽名體制是Diffie和Hellman提出數(shù)字簽名思想后的第一個數(shù)字簽名體制，它是由Rivest、Shamir和Adleman三人共同完成的。該簽名體制來源于RSA公鑰密碼體制的思想，將RSA公鑰體制按照數(shù)字簽名的方式運用。RSA數(shù)字簽名

※選取兩個不同的大素數(shù)p和q，計算

※

選取一個與

互素的正整數(shù)

e，并計算出d滿足

,即

d是e模

的逆。

※

最后，公開

n和

e作為簽名驗證密鑰，秘密保存

p、

q和d作為簽名密鑰。RSA數(shù)字簽名體制的消息空間和簽名空間都是Zn，分別對應于RSA公鑰密碼體制的明文空間和密文空間。簽名時：得到的結(jié)果s就是簽名者對消息m的數(shù)字簽名。驗證時：驗證者通過下式判斷簽名的真?zhèn)蜶SA數(shù)字簽名的安全問題

對RSA數(shù)字簽名算法進行選擇密文攻擊可以實現(xiàn)三個目的，即：

※消息破譯

※騙取仲裁簽名

※騙取用戶簽名消息破譯即得到了原始的明文消息騙取仲裁簽名攻擊者騙取仲裁簽名騙取用戶簽名主要思想：當攻擊者希望某合法用戶對一個消息m進行簽名但該簽名者可能不愿意為其簽名時：

※

將m分解成兩個（多個）更能迷惑合法用戶的消息m1和m2，且滿足m=m1×m2；

※

讓合法用戶對m1和m2分別簽名；攻擊者最終獲得該合法用戶對消息m的簽名。結(jié)論：上述選擇密文攻擊都是利用了指數(shù)運算能夠保持輸入的乘積結(jié)構(gòu)這一缺陷（稱為可乘性）。

因此，任何時候都不能對陌生人提交的消息直接簽名，最好先經(jīng)過某種處理。攻擊方法（續(xù)）1）偽造者Oscar選取一個消息y，并取得某合法用戶的RSA公鑰（n,e）；

2）計算：

3）偽造者聲稱y是該合法用戶對消息x的RSA簽名，達到了假冒該合法用戶的目的。

這是因為，該合法用戶用自己的私鑰d對消息x合法簽名的結(jié)果正好就是y，即：

因此從算法本身不能識別偽造者的假冒行為6.3Rabin數(shù)字簽名

Rabin數(shù)字簽名體制利用Rabin公鑰密碼算法構(gòu)造而成。

由于Rabin公鑰密碼算法與RSA公鑰密碼算法的相似性，Rabin簽名算法與RSA簽名算法也具有類似的相似性。6.3.1Rabin數(shù)字簽名算法Rabin數(shù)字簽名算法的系統(tǒng)參數(shù)包括兩個隨機選取的相異大素數(shù)p和q，及它們的乘積。其中，n為公開密鑰，p和q則需要保密。消息空間和簽名空間都是由同為模p平方剩余和模q平方剩余的正整數(shù)構(gòu)成的集合。簽名時：對一個消息

m∈zn簽名時※判斷消息m是否同時是模

p和模q的平方剩余；

※否：

對m作一個變換，將其映射成滿足要的。

是：對m簽字就是計算模m的平方根，即:

求解合數(shù)模的平方根是困難的，除非能夠?qū)δ?shù)進行素因子分解。即：

知道模數(shù)n的兩個素因子p和q，然后將問題轉(zhuǎn)化成一次同余方程組，再利用中國剩余定理求解。

偽造Rabin簽名是困難的驗證時：

※驗證者計算消息簽名的平方；

※

通過下式確認數(shù)字簽名的真?zhèn)危?/p>

Rabin簽名正確性的驗證是顯而易見的。Rabin簽名算法的安全問題Rabin算法是一種基于平方剩余的公鑰體制，這種體制已經(jīng)被證明它的安全性正好等價于大整數(shù)分解的困難性，但這種體制也容易遭受一種特定的攻擊，其方法如下：攻擊者簽名者XM等待簽名者送回數(shù)字簽名S缺陷

※

它要求被簽消息必須是模的平方剩余

※

若不是，將被簽消息映射到滿足要求的另一個消息m′上，再用m′的Rabin簽名作為原消息的簽名。6.4ElGamal數(shù)字簽名

思想：

ElGamal簽名體制是一種基于離散對數(shù)問題的數(shù)字簽名方案。ElGamal簽名算法是專門為數(shù)字簽名設計的。

ElGamal數(shù)字簽名算法

ElGamal簽名體制也是非確定性的，任何一個給定的消息都可以產(chǎn)生多個有效的ElGamal簽名，并且驗證算法能夠?qū)⑺鼈冎械娜魏我粋€當作可信的簽名接受。ElGamal簽名方案的系統(tǒng)參數(shù)

一個大素數(shù)p；

的生成元g；

任取的秘密數(shù)a；

一個由g和a計算得到的整數(shù)y；P的大小足以使Zp上的離散對數(shù)問題難以解決y滿足：

這些系統(tǒng)參數(shù)構(gòu)成ElGamal數(shù)字簽名的密鑰K=（p,g,a,y）,其中（p,g,y）是公開密鑰，a是私有密鑰。簽名時：驗證時：例6.1若要對消息m=100簽名時，假設取隨機數(shù)k=213且則有：（續(xù)）且所以，得到一個新的數(shù)字簽名s=（126，350）（續(xù)）驗證時：

對于第一個數(shù)字簽名s=（29,51），有

而：（續(xù)）

對于第二個數(shù)字簽名s=(126，350)，仍然有

而：

所以，兩個數(shù)字簽名都是有效的。對ElGamal簽名算法的可能攻擊

ElGamal數(shù)字簽名算法的安全性依賴于求解離散對數(shù)問題的困難性，如果求解離散對數(shù)已經(jīng)不再困難了，那么ElGamal數(shù)字簽名算法也就沒有任何意義了。

在假定離散對數(shù)問題依然難以求解的情況下，ElGamal簽名方案仍然存在一些安全威脅。

這些安全威脅首先來自于對方案使用不當而造成的可能攻擊，包括兩個方面：

※

對簽名中使用的隨機整數(shù)k保管不當，發(fā)生

泄露；

※

重復使用簽名隨機數(shù)k。隨機整數(shù)k保管不當注意：這時整個系統(tǒng)完全被破壞，攻擊者可以隨意偽造該簽名者的數(shù)字簽名。重復使用k可以使攻擊者易于計算出簽名者的私有密鑰a。具體做法：

設和分別是某個簽名者對消息和的簽名，且

，有：

兩式相減，得：設：

那么，

所以，

記：

則等式變成且

由于

所以，由擴展的歐幾里得算法求出：

得：

故：，

利用同余式：

即可測出唯一正確的k。

找到簽名隨機數(shù)k，即可計算出簽名者的私有密鑰a。偽造簽名攻擊

方法一：由此可見，攻擊者可以在惟密鑰的情況下進行存在性偽造。

設：i和j是上的整數(shù)且可表示為：

那么簽名驗證條件是：于是有：若且

則上式成立。因此，在給定的i和j，且的條件下，很容易利用這兩個同余式求出和，結(jié)果如下：

顯然，按照種方法構(gòu)造出來的是消息的有效簽名，但它是偽造的。例6.2

設，，。選取和那么，

計算：

（435,425）是對消息m=285的有效簽名，這可以從下面的式子得到驗證：方法二：此方法屬于已知消息攻擊存在性偽造，偽造簽名者需要從合法簽名者的某個已知簽名消息開始，來偽造一個新消息簽名。具體實現(xiàn)：

計算：

那么，簽名條件

于是，偽造出一個是的有效簽名。小結(jié)這兩種偽造簽名的攻擊都是對ElGamal數(shù)字簽名的存在性偽造，對抗這種存在性偽造的簡單辦法是使消息格式化。

※

最簡單的消息格式化機制：

在消息中嵌入一個可識別的部分；

※最有效的消息格式化機制：對消息進行Hash函數(shù)處理；方法三：小結(jié)

先計算：

然后計算，使?jié)M足

顯然，可以通過中國剩余定理解出。

歷史背景：

數(shù)字簽名標準DSS（DigitalSignatureStandard）是由美國國家標準技術(shù)協(xié)會NIST于1991年8月公布，并于1994年12月1日正式生效的一項美國聯(lián)邦信息處理標準。6.5數(shù)字簽名標準DSS

DSS的數(shù)字簽名算法

DSS數(shù)字簽名標準使用的算法稱為數(shù)字簽名算法DSA（DigitalSignatureAlgorithm），它是在ElGamal和Schnorr兩個方案基礎上設計出來的。DSA的系統(tǒng)參數(shù)※※※

※一個用戶隨機選取的整數(shù)，并計算出※一個Hash函數(shù)H：。

這些系統(tǒng)參數(shù)構(gòu)成DSA的密鑰空間：

其中，

為公開密鑰，a是私有密鑰。簽名時：

對消息m生成數(shù)字簽名時，隨機選取一個秘密整數(shù)，并計算出：

就是消息m的數(shù)字簽名，即

由此可見，DSA的簽名空間為，簽名的長度比ElGamal體制短了許多。驗證者知道簽名者的公開密鑰驗證時：對于一個消息-簽名對，計算下面幾個值并判定簽名的真實性：這是因為，如果是消息的有效簽名，那么DSA數(shù)字簽名算法基本框圖

m

f1f3f2SHA-1

SHA-1f4比較m

p,q,gkaqwkv例6.3假設簽名者的私有密鑰為a=87，那么，簽名時：

假如該簽名者要對一個消息摘要為SHA-1（m）=132的消息m簽名，并且簽名者選擇的秘密隨機數(shù)為k=79，則需要計算：因此，（99,57）是消息m的簽名驗證時：

計算：

所以，

說明以上簽名是有效的。DSA算法的評價

DSA算法不能用于數(shù)據(jù)加密，也不能用于密鑰分配；DSA算法比RSA慢；DSA算法的密鑰長度；驗證簽名時DSA比RSA慢10到40倍密鑰長度變化范圍在512比特到1024比特之間DSA算法的安全問題

主要有以下幾個方面：

攻擊秘密數(shù)k；

共用模數(shù)的危險；DSA的閾下信道；

允許簽名者在其簽名中嵌入秘密消息,只有知道密鑰的人能提取簽名者嵌入的秘密消息.小結(jié)數(shù)字簽名與公鑰加密的區(qū)別簽名加密HashSIGHash解密比較mmsskAs=SIGsk

(Hash(m))pkA發(fā)送方加密算法解密算法接收方密鑰空間mmc發(fā)送方A(,)pkAskA接收方B(,)pkBskBpkBskB發(fā)送方A接收方BAB小結(jié)數(shù)字簽名與公鑰加密的區(qū)別數(shù)字簽名與消息加密的結(jié)合使用特殊數(shù)字簽名隨著網(wǎng)絡技術(shù)和電子商務的迅猛發(fā)展,迫切需要解決網(wǎng)上數(shù)據(jù)傳輸安全以及交易雙方的身份識別和認證。簡單模擬手寫簽名的普通簽名已不能完全滿足應用的需要,許多新的應用環(huán)境要求數(shù)字簽名能支持一些特殊的功能,因此，需要在基本數(shù)字簽名技術(shù)的基礎上進行擴展，以滿足這些特殊的需求。特點：

如果沒有簽名者Alice的合作，簽名的有效性就得不到驗證。好處：防止了由Alice簽署的消息在沒有經(jīng)過Alice本人同意而被復制和分發(fā)的可能性。1.不可否認簽名簽名的構(gòu)成組成：

簽名算法

驗證協(xié)議

否認協(xié)議參數(shù)生成密鑰空間為:

其中是公鑰，是私鑰。對于消息，簽名者計算

簽名驗證協(xié)議隨機選取參數(shù)e1,e2e1e2

c

d

當且僅當Bob認為簽名合法

否認協(xié)議隨機選取參數(shù)e1,e2e1e2

c

d計算隨機選取CD計算

當且僅當Bob認為簽名是偽造的。Alice能使Bob相信一個無效的簽名是一個偽造簽名Alice能使Bob以一個很小的概率相信一個有效的簽名是偽造的不可否認數(shù)字簽名的應用

軟件公司A發(fā)行了一套最新的軟件.它向用戶承諾,此軟件不含