6.1數(shù)字簽名的基本原理6.2RSA數(shù)字簽名*6.3Rabin數(shù)字簽名6.4ElGamal數(shù)字簽名6.5數(shù)字簽名標準——DSS6.6不可否認的簽名習題6.1數(shù)字簽名的基本原理6.1.1數(shù)字簽名的基本概念第4章討論的Hash函數(shù)和消息認證碼能夠幫助合法通信的雙方不受來自系統(tǒng)外部的第三方攻擊和破壞，但卻無法防止系統(tǒng)內通信雙方之間的互相抵賴和欺騙。當Alice和Bob進行通信并使用消息認證碼提供數(shù)據(jù)完整性保護，一方面Alice確實向Bob發(fā)送消息并附加了用雙方共享密鑰生成的消息認證碼，但隨后Alice否認曾經(jīng)發(fā)送了這條消息，因為Bob完全有能力生成同樣的消息及消息認證碼；另一方面，Bob也有能力偽造一個消息及消息認證碼并聲稱此消息來自Alice。如果通信的過程沒有第三方參與的話，這樣的局面是難以仲裁的。因此，安全的通信僅有消息完整性認證是不夠的，還需要有能夠防止通信雙方相互作弊的安全機制，數(shù)字簽名技術正好能夠滿足這一需求。在人們的日常生活中，為了表達事件的真實性并使文件核準、生效，常常需要當事人在相關的紙質文件上手書簽字或蓋上表示自己身份的印章。在數(shù)字化和網(wǎng)絡化的今天，大量的社會活動正在逐步實現(xiàn)電子化和無紙化，活動參與者主要是在計算機及其網(wǎng)絡上執(zhí)行活動過程，因而傳統(tǒng)的手書簽名和印章已經(jīng)不能滿足新形勢下的需求，在這種背景下，以公鑰密碼理論為支撐的數(shù)字簽名技術應運而生。數(shù)字簽名是對以數(shù)字形式存儲的消息進行某種處理，產(chǎn)生一種類似于傳統(tǒng)手書簽名功效的信息處理過程。它通常將某個算法作用于需要簽名的消息，生成一種帶有操作者身份信息的編碼。通常將執(zhí)行數(shù)字簽名的實體稱為簽名者，所使用的算法稱為簽名算法，簽名操作生成的編碼稱為簽名者對該消息的數(shù)字簽名。消息連同其數(shù)字簽名能夠在網(wǎng)絡上傳輸，可以通過一個驗證算法來驗證簽名的真?zhèn)我约白R別相應的簽名者。類似于手書簽名，數(shù)字簽名至少應該滿足三個基本要求：

(1)簽名者任何時候都無法否認自己曾經(jīng)簽發(fā)的數(shù)字簽名；

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

(3)當各方對數(shù)字簽名的真?zhèn)萎a(chǎn)生爭議時，通過仲裁機構(可信的第三方)進行裁決。數(shù)字簽名與手書簽名也存在許多差異，大體上可以概括為：

(1)手書簽名與被簽文件在物理上是一個整體，不可分離；數(shù)字簽名與被簽名的消息是可以互相分離的比特串，因此需要通過某種方法將數(shù)字簽名與對應的被簽消息綁定在一起。

(2)在驗證簽名時，手書簽名是通過物理比對，即將需要驗證的手書簽名與一個已經(jīng)被證實的手書簽名副本進行比較，來判斷其真?zhèn)巍ｒ炞C手書簽名的操作也需要一定的技巧，甚至需要經(jīng)過專門訓練的人員和機構(如公安部門的筆跡鑒定中心)來執(zhí)行。而數(shù)字簽名卻能夠通過一個嚴密的驗證算法準確地被驗證，并且任何人都可以借助這個公開的驗證算法來驗證一個數(shù)字簽名的真?zhèn)?。安全的?shù)字簽名方案還能夠杜絕偽造數(shù)字簽名的可能性。

(3)手書簽名是手寫的，會因人而異，它的復制品很容易與原件區(qū)分開來，從而容易確認復制品是無效的；數(shù)字簽名的拷貝與其原件是完全相同的二進制比特串，或者說是兩個相同的數(shù)值，不能區(qū)分誰是原件，誰是復制品。因此，必須采取有效的措施來防止一個帶有數(shù)字簽名的消息被重復使用。比如，Alice向Bob簽發(fā)了一個帶有他的數(shù)字簽名的數(shù)字支票，允許Bob從Alice的銀行賬戶上支取一筆現(xiàn)金，那么這個數(shù)字支票必須是不能重復使用的，即Bob只能從Alice的賬戶上支取指定金額的現(xiàn)金一次，否則Alice的賬戶很快就會一無所有，這個結局是Alice不愿意看到的。從上面的對比可以看出，數(shù)字簽名必須能夠實現(xiàn)與手書簽名同等的甚至更強的功能。為了達到這個目的，簽名者必須向驗證者提供足夠多的非保密信息，以便驗證者能夠確認簽名者的數(shù)字簽名；但簽名者又不能泄露任何用于產(chǎn)生數(shù)字簽名的機密信息，以防止他人偽造他的數(shù)字簽名。因此，簽名算法必須能夠提供簽名者用于簽名的機密信息與驗證者用于驗證簽名

的公開信息，但二者的交叉不能太多，聯(lián)系也不能太直觀，從公開的驗證信息不能輕易地推測出用于產(chǎn)生數(shù)字簽名的機密信息。這是對簽名算法的基本要求之一。一個數(shù)字簽名體制一般包含兩個組成部分，即簽名算法(SignatureAlgorithm)和驗證算法(VerificatonAlgorithm)。簽名算法用于對消息產(chǎn)生數(shù)字簽名，它通常受一個簽名密鑰的控制，簽名算法或者簽名密鑰是保密的，由簽名者掌握；驗證算法用于對消息的數(shù)字簽名進行驗證，根據(jù)簽名是否有效驗證算法能夠給出該簽名為“真”或者“假”的結論。驗證算法通常也受一個驗證密鑰的控制，但驗證算法和驗證密鑰應當是公開的，以便需要驗證簽名的人能夠方便地驗證。數(shù)字簽名體制(SignatureAlgorithmSystem)是一個滿足下列條件的五元組(M，S，K，SIG，VER)，其中：

(1)M代表消息空間，它是某個字母表中所有串的集合。

(2)S代表簽名空間，它是所有可能的數(shù)字簽名構成的集合。

(3)K代表密鑰空間，它是所有可能的簽名密鑰和驗證密鑰對(sk，vk)構成的集合。

(4)SIG是簽名算法，VER是驗證算法。對于任意的一個密鑰對(sk，vk)∈K，每一個消息m∈M和簽名s∈S，簽名變換SIG：M×K|sk→S和驗證變換VER:M×S×K|vk→{true，false}是滿足下列條件的函數(shù)：由上面的定義可以看出，數(shù)字簽名算法與公鑰加密算法在某些方面具有類似的性質，甚至在某些具體的簽名體制中，二者的聯(lián)系十分緊密，但是從根本上來講，它們之間還是有本質的不同。比如對消息的加解密一般是一次性的，只要在消息解密之前是安全的就行了；而被簽名的消息可能是一個具體法定效用的文件，如合同等，很可能在消息被簽名多年以后才需要驗證它的數(shù)字簽名，而且可能需要多次重復驗證此簽名。因此，簽名的安全性和防偽造的要求應更高一些，而且要求簽名驗證速度比簽名生成速度還要快一些，特別是聯(lián)機的在線實時驗證。6.1.2數(shù)字簽名的特性

綜合數(shù)字簽名應當滿足的基本要求，數(shù)字簽名應具備一些基本特性，這些特性可以分為功能特性和安全特性兩大方面，分別描述如下。

數(shù)字簽名的功能特性是指為了使數(shù)字簽名能夠實現(xiàn)需要的功能要求而應具備的一些特性，這類特性主要如下：

(1)依賴性。數(shù)字簽名必須依賴于被簽名消息的具體比特模式，不同的消息具有不同的比特模式，因而通過簽名算法生成的數(shù)字簽名也應當是互不相同的。也就是說一個數(shù)字簽名與被簽消息是緊密相關、不可分割的，離開被簽消息，簽名不再具有任何效用。

(2)獨特性。數(shù)字簽名必須是根據(jù)簽名者擁有的獨特信息來產(chǎn)生的，包含了能夠代表簽名者特有身份的關鍵信息。惟有這樣，簽名才不可偽造，也不能被簽名者否認。

(3)可驗證性。數(shù)字簽名必須是可驗證的，通過驗證算法能夠確切地驗證一個數(shù)字簽名的真?zhèn)巍?/p>

(4)不可偽造性。偽造一個簽名者的數(shù)字簽名不僅在計算上不可行，而且希望通過重用或者拼接的方法偽造簽名也是行不通的。比如希望把一個簽名者在過去某個時間對一個消息的簽名用來作為該簽名者在另一時間對另一消息的簽名，或者希望將簽名者對多個消息的多個簽名組合成對另一消息的簽名，都是不可行的。

(5)可用性。數(shù)字簽名的生成、驗證和識別的處理過程必須相對簡單，能夠在普通的設備上快速完成，甚至可以在線處理，簽名的結果可以存儲和備份。除了上述功能特性之外，數(shù)字簽名還應當具備一定的安全特性，以確保它提供的功能是安全的，能夠滿足安全需求，實現(xiàn)預期的安全保障。上面的不可偽造性也可以看做是安全特性的一個方面，除此之外，數(shù)字簽名至少還應當具備如下安全特性：

(1)單向性。類似于公鑰加密算法，數(shù)字簽名算法也應當是一個單向函數(shù)，即對于給定的數(shù)字簽名算法，簽名者使用自己的簽名密鑰sk對消息m進行數(shù)字簽名是計算上容易的，但給定一個消息m和它的一個數(shù)字簽名s，希望推導出簽名者的簽名密鑰sk是計算上不可行的。

(2)無碰撞性。即對于任意兩個不同的消息m≠m′，它們在同一個簽名密鑰下的數(shù)字簽名SIGsk(m)=SIGsk(m′)相等的概率是可以忽略的。

(3)無關性。即對于兩個不同的消息m≠m′，無論m與m′存在什么樣的內在聯(lián)系，希望從某個簽名者對其中一個消息的簽名推導出對另一個消息的簽名是不可能的。

數(shù)字簽名算法的這些安全特性從根本上消除了成功偽造數(shù)字簽名的可能性，使一個簽名者針對某個消息產(chǎn)生的數(shù)字簽名與被簽消息的搭配是惟一確定的，不可篡改，也不可偽造。生成數(shù)字簽名的惟一途徑是將簽名算法和簽名密鑰作用于被簽消息，除此之外別無它法。6.1.3數(shù)字簽名的實現(xiàn)方法

現(xiàn)在的數(shù)字簽名方案大多是基于某個公鑰密碼算法構造出來的。這是因為在公鑰密碼體制里，每一個合法實體都有一個專用的公私鑰對，其中的公開密鑰是對外公開的，可以通過一定的途徑去查詢；而私有密鑰是對外保密的，只有擁有者自己知曉，可以通過公開密鑰驗證其真實性，因此私有密鑰與其持有人的身份一一對應，可以看做是其持有人的一種身份標識。恰當?shù)貞冒l(fā)送方私有密鑰對消息進行處理，可以使接收方能夠確信收到的消息確實來自其聲稱的發(fā)送者，同時發(fā)送者也不能對自己發(fā)出的消息予以否認，即實現(xiàn)了消息認證和數(shù)字簽名的功能。圖6-1給出公鑰算法用于消息認證和數(shù)字簽名的基本原理。圖6-1基于公鑰密碼的數(shù)字簽名體制在圖6-1中，發(fā)送方Alice用自己的私有密鑰skA加密消息m，任何人都可以輕易獲得Alice的公開秘密pkA，然后解開密文c，因此這里的消息加密起不了信息保密的作用?？梢詮牧硪粋€角度來認識這種不保密的私鑰加密，由于用私鑰產(chǎn)生的密文只能由對應的公鑰來解密，根據(jù)公私鑰一一對應的性質，別人不可能知道Alice的私鑰，如果接收方Bob能夠用Alice的公鑰正確地還原明文，表明這個密文一定是Alice用自己的私鑰生成的，因此Bob可以確信收到的消息確實來自Alice，同時Alice也不能否認這個消息是自己發(fā)送的；另一方面，在不知道發(fā)送者私鑰的情況下不可能篡改消息的內容，因此接收者還可以確信收到的消息在傳輸過程中沒有被篡改，是完整的。也就是說，圖6-1表示的這種公鑰算法使用方式不僅能夠證實消息來源和發(fā)送者身份的真實性，還能保證消息的完整性，即實現(xiàn)了前面所說的數(shù)字簽名和消息認證的效果。在上述認證方案中，雖然傳送的消息不能被篡改，但卻很容易被竊聽，因為任何人都可以輕易取得發(fā)送者的公鑰來解密消息。為了同時實現(xiàn)保密和認證的能力，可以將發(fā)送方的私鑰加密和接收方的公鑰加密結合起來，進行雙重加/解密，如圖6-2所示。

在圖6-2中，發(fā)送方Alice先用自己的私鑰skA加密待發(fā)送消息，對消息做簽名處理，然后再用對方Bob的公鑰pkB對簽名后的消息加密，以達到保密的目的；接收方Bob收到消息后先用自己的私鑰skB解密消息，再用對方Alice的公鑰pkA驗證簽名，只有簽名通過驗證的消息，接收者才會接受，其中

。圖6-2基于公鑰密碼的加密和簽名體制也許有人會想象改變圖6-2中發(fā)送方Alice對消息雙重加密的順序,即先使用Bob的公鑰pkB加密，再使用Alice的私鑰skA簽名，然后將收信方Bob解密的順序也做相應修改。這樣做，似乎同樣可以實現(xiàn)消息的保密性和認證性，但是如果真的按這樣的順序來處理的話，可能會有很大的安全隱患。這是因為在這種先加密后簽名的方案中，發(fā)信方產(chǎn)生的密文，也就是在信道上傳輸?shù)拿芪氖?，任何?不妨說是Oscar)都可以用Alice的公鑰pkA來解密c得到，然后再用自己的私鑰skX來加密產(chǎn)生，并仍然發(fā)送給Bob，那么Bob就會以為他收到的消息來自Oscar(而不是Alice)，接下來Bob就會將原本要發(fā)送給Alice的消息轉而發(fā)送給Oscar。也就是說，這種先加密后簽名的方案允許任何用戶Oscar偽裝成合法用戶Alice，并假冒Alice行事。這是一個很大的安全漏洞，因此不能簡單地采用這樣的處理順序。當然，這樣的處理順序也有一個優(yōu)點，那就是如果接收方發(fā)現(xiàn)收到的消息不能通過簽名驗證，就不用再對其解密了，因而減少了運算量，但這點優(yōu)勢明顯抵不上它的安全隱患。在實際應用中，對消息進行數(shù)字簽名，可以選擇對分組后的原始消息直接簽名，但考慮到原始消息一般都比較長，可能以千比特為單位，而公鑰算法的運行速度卻相對較低，因此通常先讓原始消息經(jīng)過Hash函數(shù)處理，再簽名所得到的Hash碼(即消息摘要)。在驗證數(shù)字簽名時，也是針對Hash碼來進行的。通常，驗證者先對收到的消息重新計算它的Hash碼，然后用簽名驗證密鑰解密收到的數(shù)字簽名，再將解密的結果與重新計算的Hash碼比較，以確定簽名的真?zhèn)巍ｏ@然，當且僅當簽名解密的結果與重新計算的Hash碼完全相同時，簽名為真。一個消息的Hash碼通常只有幾十到幾百比特，例如SHA-1能對任何長度的消息進行Hash處理，得到160比特的消息摘要。因此，經(jīng)過Hash處理后再對消息摘要簽名能大大地提高簽名和驗證的效率，而且Hash函數(shù)的運行速度一般都很快，兩次Hash處理的開銷對系統(tǒng)影響不大。數(shù)字簽名的實現(xiàn)方法如圖6-3所示。圖6-3數(shù)字簽名的實現(xiàn)方法經(jīng)過學者們長期持續(xù)不懈的努力，大量的數(shù)字簽名方案相繼被提出，它們大體上可以分成兩大類方案，即直接數(shù)字簽名體制和需要仲裁的數(shù)字簽名體制。

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

直接數(shù)字簽名僅涉及通信雙方，它假定接收方Bob知道發(fā)送方Alice的公開密鑰，在發(fā)送消息之前，發(fā)送方使用自己的私有密鑰作為加密密鑰對需要簽名的消息進行加密處理，產(chǎn)生的密文就可以當作發(fā)送者對所發(fā)送消息的數(shù)字簽名。但是由于要發(fā)送的消息一般都比較長，直接對原始消息進行簽名的成本以及相應的驗證成本都比較高且速度慢，因此發(fā)送者常常先對需要簽名的消息進行Hash處理，然后再用私有密鑰對所得的Hash碼進行上述的簽名處理，所得結果作為對被發(fā)送消息的數(shù)字簽名。顯然這里用私有密鑰對被發(fā)送消息或者它的Hash碼進行加密變換，其結果并沒有保密作用，因為相應的公開密鑰眾所周知，任何人都可以輕而易舉地恢復原來的明文消息，這樣做的目的只是為了數(shù)字簽名。雖然上述直接數(shù)字簽名體制的思想簡單可行，且易于實現(xiàn)，但它也存在一個明顯的弱點，即直接數(shù)字簽名方案的有效性嚴格依賴于簽名者私有密鑰的安全性。一方面，如果一個用戶的私有密鑰不慎泄密，那么在該用戶發(fā)現(xiàn)他的私有密鑰已泄密并采取補救措施之前，必然會遭受其數(shù)字簽名有可能被偽造的威脅。更進一步，即使該用戶發(fā)現(xiàn)自己的私有密鑰已經(jīng)泄密并采取了適當?shù)难a救措施，但仍然可以偽造其更早時間(實施補救措施之前)的數(shù)字簽名，這可以通過對數(shù)字簽名附加一個較早的時間戳(實施補救措施之前的任何時刻均可)來實現(xiàn)。另一方面，如果因為某種原因簽名者在簽名后想否認他曾經(jīng)對某個消息簽過名，他可以故意聲稱他的私有密鑰早已泄密，并被盜用來偽造了該簽名。方案本身無力阻止這種情況的發(fā)生，因此在直接數(shù)字簽名方案中，簽名者有作弊的機會。

2.可仲裁的數(shù)字簽名體制

為了解決直接數(shù)字簽名體制存在的問題，可以引入一個可信的第三方作為數(shù)字簽名系統(tǒng)的仲裁者。每次需要對消息進行簽名時，發(fā)信者先對消息執(zhí)行數(shù)字簽名操作，然后將生成的數(shù)字簽名連同被簽消息一起發(fā)送給仲裁者；仲裁者對消息及其簽名進行驗證，通過仲裁者驗證的數(shù)字簽名被簽發(fā)一個證據(jù)來證明它的真實性；最后消息、數(shù)字簽名以及簽名真實性證據(jù)一起被發(fā)送給接收者。在這樣的方案中，發(fā)信者無法對自己簽名的消息予以否認，而且即使一個用戶的簽名密鑰泄密也不可能偽造該簽名密鑰泄密之前的數(shù)字簽名，因為這樣的偽造簽名不可能通過仲裁者的驗證。然而正所謂有得必有失，這種可仲裁的數(shù)字簽名體制比那種直接的數(shù)字簽名體制更加復雜，仲裁者有可能成為系統(tǒng)性能的瓶頸，而且仲裁者必須是公正可信的中立者。下面介紹幾種數(shù)字簽名體制。6.2RSA數(shù)字簽名6.2.1RSA數(shù)字簽名算法

RSA數(shù)字簽名算法系統(tǒng)參數(shù)的選擇與RSA公鑰密碼體制基本一樣，首先要選取兩個不同的大素數(shù)p和q，計算n=p×q;再選取一個與φ(n)互素的正整數(shù)e，并計算出d滿足e×d=1modφ(n)，即d是e模φ(n)的逆;最后，公開n和e作為簽名驗證密鑰，秘密保存p、q和d作為簽名密鑰。RSA數(shù)字簽名體制的消息空間和簽名空間都是Zn，分別對應于RSA公鑰密碼體制的明文空間和密文空間，而密鑰空間為K={n，p，q，e，d}，與RSA公鑰密碼體制相同。當需要對一個消息m∈Zn進行簽名時，簽名者計算

s=SIGsk(m)=mdmodn

得到的結果s就是簽名者對消息m的數(shù)字簽名。

驗證簽名時，驗證者通過下式判定簽名的真?zhèn)危?/p>

VERvk(m，s)=true

m≡semodn

這是因為，類似于RSA公鑰密碼體制的解密變換，有

semodn=(md)emodn=medmodn≡m

可見，RSA數(shù)字簽名的處理方法與RSA加解密的處理方法基本一樣，不同之處在于，簽名時簽名者要用自己的私有密鑰對消息“加密”，而驗證簽名時驗證者要使用簽名者的公鑰對簽名者的數(shù)字簽名“解密”。RSA數(shù)字簽名有效性的驗證正好可以通過5.3節(jié)中RSA解密算法的正確性得到證實。6.2.2RSA數(shù)字簽名算法的安全問題

RSA數(shù)字簽名算法是依據(jù)數(shù)字簽名方式運用RSA公鑰密碼算法產(chǎn)生的，在5.3.2節(jié)中已經(jīng)討論了RSA算法安全性的一些問題，并在5.3.3節(jié)中對如何更安全地選擇RSA算法的參數(shù)給出了一些建議，這些討論和建議對于RSA算法用于數(shù)字簽名同樣有效。

對RSA數(shù)字簽名算法進行選擇密文攻擊可以實現(xiàn)三個目的，即消息破譯、騙取仲裁簽名和騙取用戶簽名，簡述如下：

(1)消息破譯。攻擊者對通信過程進行監(jiān)聽，并設法成功收集到使用某個合法用戶公鑰e加密的密文c。攻擊者想恢復明文消息m，即找出滿足c=memodn的消息m，可以按如下方法進行處理：

第一步，攻擊者隨機選取r<n且gcd(r，n)=1，計算三個值：

u=remodn，y=u×cmodn，t=r-1modn

第二步，攻擊者請求合法用戶用其私鑰d對消息y簽名，得到s=ydmodn。

第三步，由u=remodn可知r=udmodn，所以t=r-1modn=

u-dmodn。因此，攻擊者容易計算出

t×smodn=u-dydmodn=u-dudcdmodn=cdmodn=medmodn=m

即得到了原始的明文消息。

(2)騙取仲裁簽名。仲裁簽名是仲裁方(即公證人)用自己的私鑰對需要仲裁的消息進行簽名，起到仲裁的作用。如果攻擊者有一個消息需要仲裁簽名，但由于公證人懷疑消息中包含不真實的成分而不愿意為其簽名，那么攻擊者可以按下述方法騙取仲裁簽名。

假設攻擊者希望簽名的消息為m，那么他隨機選取一個值x，并用仲裁者的公鑰e計算y=xemodn。再令M=m×ymodn，并將M發(fā)送給仲裁者要求仲裁簽名。仲裁者回送仲裁簽名Mdmodn，攻擊者即可計算

(Mdmodn)×x-1modn=md×yd×x-1modn=md×xed×x-1modn=mdmodn立即得到消息m的仲裁簽名。

(3)騙取用戶簽名。這實際上是指攻擊者可以偽造合法用戶對消息的簽名。比如說如果攻擊者能夠獲得某合法用戶對兩個消息m1和m2的簽名

和，那么他馬上就可以偽造出該用戶對新消息m3=m1×m2的簽名。因此，當攻擊者希望某合法用戶對一個消息m進行簽名但該簽名者可能不愿意為其簽名時，可以將m分解成兩個(或多個)更能迷惑合法用戶的消息m1和m2，且滿足m=m1×m2，然后讓合法用戶對m1和m2分別簽名，攻擊者最終獲得該合法用戶對消息m的簽名。容易看出，上述選擇密文攻擊都是利用了指數(shù)運算能夠保持輸入的乘積結構這一缺陷(稱為可乘性)。因此一定要記住，任何時候都不能對陌生人提交的消息直接簽名，最好先經(jīng)過某種處理，比如先用單向Hash函數(shù)對消息進行Hash運算，再對運算結果簽名。

以上這些攻擊方法都是利用了模冪運算本身具有的數(shù)學特性來實施的。還有一種類似的構成RSA數(shù)字簽名體制安全威脅的攻擊方法，這種方法使任何人都可以偽造某個合法用戶的數(shù)字簽名，方法如下：偽造者Oscar選取一個消息y，并取得某合法用戶(被偽造者)的RSA公鑰(n，e)，然后計算x=ye

modn，最后偽造者聲稱y是該合法用戶對消息x的RSA簽名，達到了假冒該合法用戶的目的。這是因為，該合法用戶用自己的私鑰d對消息x合法簽名的結果正好就是y，即

SIGsk(x)=xdmodn=(ye)dmodn=yedmodn≡y

因此從算法本身不能識別偽造者的假冒行為。如果偽造者精心挑選y，使x具有明確的意義，那么造成的危害將是巨大的。*6.3Rabin數(shù)字簽名

Rabin數(shù)字簽名體制利用Rabin公鑰密碼算法構造而成，由于Rabin公鑰密碼算法與RSA公鑰密碼算法的相似性，Rabin簽名算法與RSA簽名算法也具有類似的相似性。6.3.1Rabin數(shù)字簽名算法

Rabin數(shù)字簽名算法的系統(tǒng)參數(shù)包括兩個隨機選取的相異大素數(shù)p和q，以及它們的乘積n=p×q，其中n為公開密鑰，p和q則需要保密。消息空間和簽名空間都是由同為模p平方剩余和模q平方剩余的正整數(shù)構成的集合。使用Rabin簽名體制對一個消息m∈Zn簽名時，首先要確保消息m既是模p的平方剩余，同時也是模q的平方剩余。如果消息m不能滿足這一要求，可以先對m作一個變換，將其映射成滿足要求的m′。這里假設消息m已滿足要求，對m簽名就是計算m模n的平方根，即

由5.4節(jié)關于Rabin公鑰密碼體制的討論知道，求解合數(shù)模的平方根是困難的，除非能夠對模數(shù)進行素因子分解，即知道模數(shù)n的兩個素因子p和q，然后將問題轉化成一次同余方程組，再利用中國剩余定理求解。因此，偽造Rabin數(shù)字簽名是困難的。

驗證Rabin數(shù)字簽名時，驗證者只需計算消息簽名的平方，然后通過下式確認數(shù)字簽名的真?zhèn)?/p>

VER(m，s)=true

m=s2modn

Rabin數(shù)字簽名正確性的驗證是顯而易見的。6.3.2Rabin數(shù)字簽名算法的安全問題

無論是用于數(shù)據(jù)加密還是消息簽名，Rabin算法都可以看做是RSA算法的一個特例，這使得它在算法安全性問題上與RSA算法具有極大的相似性，前面5.3節(jié)和6.2節(jié)所討論的RSA算法的安全問題基本上都適合Rabin算法。另外，我們還知道Rabin算法是一種基于平方剩余的公鑰體制，這種體制已經(jīng)被證明它的安全性正好等價于大整數(shù)分解的困難性，但這種體制也容易遭受一種特定的攻擊，其方法如下：攻擊者選取一個x，計算出x2=Mmodn；再將M發(fā)送給簽名者簽名，并等待簽名者回送數(shù)字簽名s。由5.4節(jié)的知識知道，簽名者對M的簽名可能有四個結果，其中包括±xmodn，因此攻擊者有1/2的概率得到一個非±xmodn的簽名，進而解出p和q，達到分解n的目的。也就是說，攻擊者有1/2的機會攻破此系統(tǒng)。所以，在使用Rabin體制時要非常小心，否則可能不安全；而RSA體制則沒有這個缺點。

Rabin數(shù)字簽名算法的另一個缺陷是它要求被簽消息必須是模n的平方剩余，否則就需要將被簽消息映射到滿足要求的另一個消息上，再用后者的Rabin簽名作為原消息的簽名，這給方案的應用造成很大的不便。后來，Rabin又對他的方案進行了改進，使任何消息都能直接被簽名，這里不再進行介紹。6.4ElGamal數(shù)字簽名

ElGamal數(shù)字簽名體制是一種基于離散對數(shù)問題的數(shù)字簽名方案。不同于既能用于加密又能用于數(shù)字簽名的RSA算法，ElGamal數(shù)字簽名算法是專門為數(shù)字簽名設計的，它與用于加密的ElGamal公鑰加密算法并不完全一樣?，F(xiàn)在，這個方案的修正形式已被美國國家標準與技術協(xié)會采納為用于數(shù)字簽名標準(DSS)的數(shù)字簽名算法。6.4.1ElGamal數(shù)字簽名算法

與ElGamal公鑰密碼體制一樣，ElGamal簽名體制也是非確定性的，任何一個給定的消息都可以產(chǎn)生多個有效的ElGamal簽名，并且驗證算法能夠將它們中的任何一個當作可信的簽名接受。ElGamal數(shù)字簽名算法的描述如下：

ElGamal數(shù)字簽名算法的系統(tǒng)參數(shù)包括：一個大素數(shù)p，且p的大小足以使Zp上的離散對數(shù)問題難以求解；的生成元g以及一個任取的秘密數(shù)a；一個由g和a計算得到的整數(shù)y，且滿足

y=gamodp

這些系統(tǒng)參數(shù)構成ElGamal數(shù)字簽名算法的密鑰K=(p，g，a，y)，其中(p，g，y)是公開密鑰，a是私有密鑰。在對一個消息m∈Zp簽名時，簽名者隨機選取一個秘密整數(shù)k∈且gcd(k,φ(p))=1，計算

γ=gkmodp

δ=(m-aγ)k-1modφ(p)

將得到的(γ，δ)作為對消息m的數(shù)字簽名，即簽名s=SIGa(m，k)=(γ，δ)，ElGamal數(shù)字簽名體制的簽名空間為Zp×Zφ(p)。驗證一個消息m的ElGamal數(shù)字簽名時，驗證者對收到的消息m及其簽名s=(γ，δ)按下式驗證其真?zhèn)危?/p>

VER(m，γ，δ)=trueyγγδ≡gmmodp

這是因為，如果簽名是正確構造的，那么

在上述ElGamal數(shù)字簽名算法中，同一個消息m，對不同的隨機數(shù)k會得到不同的數(shù)字簽名s=(γ，δ)，并且都能通過驗證算法的驗證，這就是在前面所說的不確定性，這個特點有利于提高安全性。

例6.1

假設選取p=467，Z467的生成元g=2，簽名者的私有密鑰a=127，那么有

y=gamodp=2127mod467=132

若要對消息m=100簽名，假設取隨機數(shù)k=213且

k-1modφ(p)=213-1mod466=431

則有

γ=gkmodp=2213mod467=29

δ=(m-aγ)k-1modφ(p)=(100-127×29)×431mod466=51

因此，得到的數(shù)字簽名是s=(29，51)。假如另取k=117重新計算對消息m=100的數(shù)字簽名，則有

k-1modφ(p)=117-1mod466＝235

且

γ=gkmodp=2117mod467=126

δ=(m-aγ)k-1modφ(p)=(100-127×126)×235mod466=350所以，又得到一個新的數(shù)字簽名是s=(126，350)。下面來驗證這兩個數(shù)字簽名。對于第一個數(shù)字簽名s=(29，51)，有

yγγδ=132292951≡189mod467

而

gmmodp=2100mod467=189

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

gmmodp=2100mod467=189

而

yγγδ=132126126350≡189mod467

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

由于驗證ElGamal數(shù)字簽名算法只是核實同余式y(tǒng)γγδ≡gmmodp是否成立，因此攻擊者可以考慮通過偽造能夠滿足該同余式的數(shù)偶(γ，δ)來攻擊此方案。在不知道簽名者私有密鑰a的情況下，攻擊者想偽造這樣的數(shù)偶(γ，δ)，并使之能夠成為某個消息m的數(shù)字簽名，他可以選定一個值作為γ，然后試圖找出合適的δ，但這必需計算離散對數(shù)logγ(gmy-λ)。同樣，攻擊者也可以通過選擇δ來尋找合適的γ，而這必需求解同余方程

yγγδ≡gmmodp

來獲得γ，但目前這類方程還沒有可行的解法。如果試圖通過嘗試不同的γ以得到m，仍然需要計算離散對數(shù)logg(yγγδ)。最后，如果攻擊者通過選擇γ和δ，然后計算出m，那么他再一次面臨求解離散對數(shù)logg(yγγδ)。因此，ElGamal數(shù)字簽名算法的安全性依賴于求解離散對數(shù)問題的困難性，如果求解離散對數(shù)已經(jīng)不再困難了，那么ElGamal數(shù)字簽名算法也就沒有任何意義了。

在假定離散對數(shù)問題依然難以求解的情況下，ElGamal數(shù)字簽名算法仍然存在一些安全威脅，這些安全威脅首先來自于對算法使用不當而造成的可能攻擊，它包括如下兩個方面：

(1)對簽名中使用的隨機整數(shù)k保管不當，發(fā)生泄露。如果攻擊者知道k的話，那么只要攻擊者能夠再獲得簽名者對某一個消息m的合法簽名s=(γ，δ)，就可以非常容易地計算出簽名者的私有密鑰a=(m-kδ)γ-1modφ(p)。這時整個系統(tǒng)完全被破壞，攻擊者可以隨意偽造該簽名者的數(shù)字簽名。

(2)對ElGamal方案的另一個誤用是重復使用簽名隨機數(shù)k。這同樣可以使攻擊者易于計算出簽名者的私有密鑰a，具體做法如下：

設(γ，δ1)和(γ，δ2)分別是某個簽名者對消息m1和m2的簽名，且

m1≠m2modφ(p)，有

m1=aγ+kδ1modφ(p)

m2=aγ+kδ2modφ(p)

兩式相減，得

m1-m2≡k(δ1-δ2)modφ(p)設d=gcd(δ1-δ2，φ(p))，那么d|φ(p)且d|(δ1-δ2)，所以

d|(m1-m2)。記

則等式變成由于gcd(δ′，p′)=1，所以可以用擴展的歐幾里德算法求出(δ′)-1modp′，然后得到

k=m′(δ′)-1modp′

于是

k=m′(δ′)-1+ip′modφ(p)，i∈{0，1，…，d-1}

對于這d個可能的候選值，只需利用同余式

γ=gkmodp

逐一驗證，即可檢測出惟一正確的那個k。找到了簽名隨機數(shù)k，就可以像上述(1)一樣計算出簽名者的私有密鑰a。

除了使用不當造成的安全威脅以外，ElGamal簽名方案還面臨著偽造簽名的攻擊。有多種方法可以偽造出ElGamal數(shù)字簽名，分述如下：

(1)第一種偽造方法，僅需知道合法簽名者的簽名驗證密鑰(即公開密鑰)，即可通過任意選擇的γ，構造出δ和m，使(γ，δ)恰好是該簽名者對消息m的簽名。由此可見，攻擊者可以在惟密鑰的情況下進行存在性偽造。設i和j是［0，p-2］上的整數(shù)且γ可表示為γ=giyjmodp。那么簽名驗證條件是

gm≡yγ(giyj)δmodp

于是有

gm-iδ≡yγ+jδmodp

若

m-iδ≡0modφ(p)

且

γ+jδ≡0modφ(p)

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

γ=giyjmodp

δ=-γj-1modφ(p)

m=-γij-1modφ(p)

顯然，按照這種方法構造出來的(γ，δ)是消息m的有效簽名，但它是偽造的。

例6.2

如例6.1，設p=467，g=2，y=132。假如選擇

i=209和j=147，那么j-1modφ(p)=149。計算

(435，425)是對消息m=285的有效簽名，這可以從下面的式子得到驗證：

(2)第二種偽造方法屬于已知消息攻擊的存在性偽造，偽造簽名者需要從合法簽名者的某個已簽名消息開始，來偽造一個新消息的簽名。假定(γ，δ)是消息m的有效簽名，h、i、j是［0，p-2］上的三個整數(shù)且gcd(hγ-jδ，φ(p))=1。計算

那么，簽名驗證條件

顯然成立。于是偽造出一個(λ，μ)是m′的有效簽名。這兩種偽造簽名的攻擊都是對ElGamal數(shù)字簽名的存在性偽造，目前似乎還不能將其演化成選擇性偽造，對抗這種存在性偽造的簡單辦法是使消息格式化。最簡單的消息格式化機制是在消息中嵌入一個可識別的部分，如簽名者的身份數(shù)據(jù)，使消息成為類似這樣的格式m=M‖ID。而最有效的消息格式化機制是對消息進行Hash函數(shù)處理，如果簽名者在簽名之前先對消息進行Hash函數(shù)處理，這兩種存在性偽造攻擊方法就不能對ElGamal簽名體制造成實際的威脅。這里再一次發(fā)現(xiàn)了安全Hash處理的重要性。

(3)第三種偽造方法，如果系統(tǒng)參數(shù)p和g滿足如下條件：

φ(p)=bq

g=βtmodp

其中，q是一個足夠大的素數(shù)，b是一個僅具有小的素因子的數(shù)，β=cq，且c<b。

對于某個合法用戶的公鑰y，計算對數(shù)loggy是困難的。但是，如果將底數(shù)換成gq，求解yq的離散對數(shù)是容易的，且該離散對數(shù)為z=amodb。因此，下面的同余式成立：現(xiàn)在，可以偽造該合法用戶的簽名如下：

γ=β=cq

δ=t(m-cqz)modφ(p)

顯然，簽名有效性驗證同余式成立，即

因此，(γ，δ)是消息m的有效簽名，在其生成過程中沒有使用合法簽名者的私鑰a，只是使用了amodb。

這種攻擊方法雖然是一種選擇性偽造攻擊，但容易發(fā)現(xiàn)在這個攻擊方法中，γ是一個可以被q整除的值，而q是φ(p)的大素因子。因此，在簽名驗證時，如果要求驗證γ不能被q整除，則可以防范這種簽名偽造攻擊。

(4)第四種偽造方法，該方法在γ>p條件下可行。假設(γ，δ)是對消息m的有效簽名，可以通過下面的步驟偽造對任意一個消息m′的數(shù)字簽名。先計算

然后再計算γ′，使γ′滿足

γ′≡γumodφ(p)

γ′≡γmodp

顯然，可以通過中國剩余定理解出γ′。檢查驗證同余式是否成立：

因此，(γ′，δ′)是消息m′的有效簽名，但它是偽造出來的，因為并沒有使用簽名的私有密鑰。如果在驗證簽名時檢查γ<p，就足以阻止這種簽名偽造攻擊。這是因為在上面用中國剩余定理計算出來的γ′是一個p(p-1)量級的量。6.5數(shù)字簽名標準——DSS數(shù)字簽名標準(DigitalSignatureStandard，DSS)是由美國國家標準技術協(xié)會于1991年8月公布，并于1994年12月1日正式生效的一項美國聯(lián)邦信息處理標準。DSS本質上是ElGamal數(shù)字簽名體制，但它運行在較大有限域的一個小的素數(shù)階子群上，并且在這個有限域上，離散對數(shù)問題是困難的。在對消息進行數(shù)字簽名之前，DSS先使用安全的Hash算法SHA-1對消息進行Hash處理，然后再對所得的消息摘要簽名。這樣，不僅可以確保DSS能夠抵抗多種已知的存在性偽造攻擊，同時相對于ElGamal等數(shù)字簽名體制，DSS簽名的長度將會大大地縮短。6.5.1DSS的數(shù)字簽名算法

DSS使用的算法稱為數(shù)字簽名算法(DigitalSignatureAlgorithm，DSA)，它是在ElGamal和Schnorr兩個方案基礎上設計出來的，本書省略了有關Schnorr簽名方案的介紹。

DSA的系統(tǒng)參數(shù)如下：

(1)一個長度為l比特的大素數(shù)p，l的大小在512~1024之間，且為64的倍數(shù)。

(2)p-1即φ(p)的一個長度為160比特的素因子q。

(3)一個q階元素g∈。g可以這樣得到，任選h∈，如果h(p-1)/qmodp>1，則令g＝h(p-1)/qmodp，否則重選h∈。

(4)一個用戶隨機選取的整數(shù)a∈，并計算出y=gamodp。

(5)一個Hash函數(shù)H：{0，1}*|→Zp。這里使用的是安全的Hash算法SHA-1。

這些系統(tǒng)參數(shù)構成DSA的密鑰空間K={p，q，g，a，y，H}，其中(p，q，g，y，H)為公開密鑰，a是私有密鑰。

為了生成對一個消息m的數(shù)字簽名，簽名者隨機選取一個秘密整數(shù)k∈Zq，并計算出

s(γ，δ)就是消息m的數(shù)字簽名，即SIGa(m，k)=(γ，δ)。由此可見，DSA的簽名空間為Zq×Zq，簽名的長度比ElGamal體制短了許多。驗證DSA數(shù)字簽名時，驗證者知道簽名者的公開密鑰是(p，q，g，y，H)，對于一個消息—簽名對(m，(γ，δ))，驗證者計算下面幾個值并判定簽名的真實性：這是因為，如果(γ，δ)是消息m的有效簽名，那么

圖6-4所示為DSA數(shù)字簽名算法的基本框圖。圖6-4DSA數(shù)字簽名算法基本框圖例6.3

取q=101，p=78q+1=7879。由于3是的一個生成元，因此取

g=378mod7879=170

g是上的一個q階元素。假設簽名者的私有密鑰為a=87，那么

y=gamodp=17087mod7879=3226現(xiàn)在，假如該簽名者要對一個消息摘要為SHA-1(m)=132的消息m簽名，并且簽名者選擇的秘密隨機數(shù)為k=79，則簽名者需要計算

因此，(99，57)是對消息摘要為132的消息m的簽名。要驗證這個簽名，需要進行下面的計算：

所以

說明以上簽名是有效的。6.5.2DSA算法的安全問題

DSS公布以后，引起了學術界和產(chǎn)業(yè)界的廣泛關注，大家對它的反應更多的是批評和譴責，認為它的政治性強于學術性。NIST隨后開展了一次征求意見活動，到1992年2月活動結束時，共收到109篇評論。概括起來，評價的意見主要體現(xiàn)在以下幾個方面：

(1)DSA算法不能用于數(shù)據(jù)加密，也不能用于密鑰分配。DSS只是一個數(shù)字簽名標準，但當時美國還沒有法定的公鑰加密標準，因此引起了人們對DSS的猜疑。

(2)DSA算法比RSA慢。DSA與RSA生成數(shù)字簽名的速度相當，在驗證簽名時DSA比RSA要慢10到40倍。

(3)DSA算法的密鑰長度太短。最初的DSA模數(shù)為512比特，由于DSA算法的安全性依賴于求解離散對數(shù)問題的困難性，這種規(guī)模的離散對數(shù)已不能保證長期的安全，因此后來NIST將DSA的密鑰設置為可變的，變化范圍在512比特到1024比特之間。

(4)DSA算法由美國國家安全局(NSA)研制，其設計過程不公開，提供的分析時間不充分，懷疑其中可能存在陷門。這主要是擔心政府借機干涉公民的隱私。

(5)其他意見。比如DSA算法可能侵犯別人的專利；RSA經(jīng)受了多年的分析已成為一個事實標準，并產(chǎn)業(yè)界已投入了大量資金；等等。

現(xiàn)在看來，DSA算法的安全問題并不象當初很多人猜測的那樣可怕，有些涉及安全脆弱性的疑慮并不是DSA算法獨有的，并且可以在算法的具體實現(xiàn)過程中通過適當?shù)拇胧┑靡员苊狻５膊荒苷fDSA算法是絕對完美的，在后來的分析過程中，一些有關安全的瑕疵也多次被提出，主要有以下幾個方面：

(1)攻擊秘密數(shù)k。k是簽名者選取的秘密數(shù)，每一次簽名都需要一個新的k，而且應該是隨機選取的。如果攻擊者能夠恢復一個簽名者對消息簽名時使用的秘密數(shù)k，那么就可以導出簽名者的簽名私鑰a。更危險的是，如果一個簽名者使用同一個秘密數(shù)k對兩個不同的消息進行簽名，那么攻擊者只要能夠截獲這兩個消息及其簽名，則根本不需要求解k就可以直接導出簽名者的簽名私鑰a，進而能夠偽造該簽名者的數(shù)字簽名。因此，在DSA的應用中，隨機秘密數(shù)k非常敏感，一定要十分小心。通常借助一個好隨機數(shù)生成器來應對這個問題，避免出現(xiàn)安全漏洞。

(2)共用模數(shù)的危險。DSA算法并沒有為所有用戶指定一個共享的公共模數(shù)，但在具體的應用中可能會要求所有人都使用相同的p和q，這畢竟會給算法的實現(xiàn)帶來一定的方便。雖然現(xiàn)在還沒有發(fā)現(xiàn)共用模數(shù)會有什么問題，但對攻擊者來說，共用模數(shù)顯然是一個誘人的目標。

(3)DSA的閾下信道。Simmons發(fā)現(xiàn)在DSA算法中存在一種閾下信道。該閾下信道允許簽名者在其簽名中嵌入秘密消息，只有知道密鑰的人能提取簽名者嵌入的秘密消息。Simmons聲稱，DSA“提供了至今發(fā)現(xiàn)的最合適于閾下信道通信的環(huán)境”。然而，NIST和NSA沒有對這種閾下信道做任何解釋，人們有理由懷疑他們是否早已知道這種閾下信道的存在。6.6不可否認的簽名不可否認的簽名(UndeniableSignature)由Chaum和vanAntwerpen在1989年提出來。不可否認的簽名最主要的一個特點是如果沒有簽名者Alice的合作，簽名的有效性就得不到驗證。這就防止了由Alice簽署的消息在沒有經(jīng)過Alice本人同意而被復制和分發(fā)的可能性。該簽名方案中驗證過程將通過口令—響應(Challenge-and-Response)協(xié)議來實現(xiàn)。一個不可否認的簽名由三部分組成：簽名算法、驗證協(xié)議和否認協(xié)議。Chaum和vanAntwerpen提出的不可否認的簽名算法描述如下：

(1)簽名方案。簽名方案包括簽名算法和驗證協(xié)議兩部分。

設p=2q+1是一個使得是q素數(shù)并且在Zp上的離散對數(shù)問題是難以處理的素數(shù)，α∈是一個階為q的元素，1≤a≤q-1。令β=αamodp，G表示上階為q的乘法子群。

設M=S=G，定義K={(p，a，α，β):β=αamodp}，其中p、α、β是公鑰，a是私鑰。對于key=(p，a，α，β)和x∈G，定義

y=sigkey(x)=xamodp對x，y∈G，通過執(zhí)行以下協(xié)議來驗證簽名(x，y)的有效性：