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

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

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

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

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

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

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

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

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

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

(3)K代表密鑰空間，它是所有可能的簽名密鑰和驗(yàn)證密鑰對(duì)(sk，vk)構(gòu)成的集合。

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

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

數(shù)字簽名的功能特性是指為了使數(shù)字簽名能夠?qū)崿F(xiàn)需要的功能要求而應(yīng)具備的一些特性，這類特性主要如下：

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

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

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

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

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

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

(2)無(wú)碰撞性。即對(duì)于任意兩個(gè)不同的消息m≠m′，它們?cè)谕粋€(gè)簽名密鑰下的數(shù)字簽名SIGsk(m)=SIGsk(m′)相等的概率是可以忽略的。

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

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

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

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

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

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

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

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

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

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

s=SIGsk(m)=mdmodn

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

驗(yàn)證簽名時(shí)，驗(yàn)證者通過(guò)下式判定簽名的真?zhèn)危?/p>

VERvk(m，s)=true

m≡semodn

這是因?yàn)椋愃朴赗SA公鑰密碼體制的解密變換，有

semodn=(md)emodn=medmodn≡m

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

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

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

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

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

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

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

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

u-dmodn。因此，攻擊者容易計(jì)算出

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

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

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

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

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

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

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

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

modn，最后偽造者聲稱y是該合法用戶對(duì)消息x的RSA簽名，達(dá)到了假冒該合法用戶的目的。這是因?yàn)椋摵戏ㄓ脩粲米约旱乃借€d對(duì)消息x合法簽名的結(jié)果正好就是y，即

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

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

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

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

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

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

VER(m，s)=true

m=s2modn

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

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

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

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

與ElGamal公鑰密碼體制一樣，ElGamal簽名體制也是非確定性的，任何一個(gè)給定的消息都可以產(chǎn)生多個(gè)有效的ElGamal簽名，并且驗(yàn)證算法能夠?qū)⑺鼈冎械娜魏我粋€(gè)當(dāng)作可信的簽名接受。ElGamal數(shù)字簽名算法的描述如下：

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

y=gamodp

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

γ=gkmodp

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

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

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

這是因?yàn)?，如果簽名是正確構(gòu)造的，那么

在上述ElGamal數(shù)字簽名算法中，同一個(gè)消息m，對(duì)不同的隨機(jī)數(shù)k會(huì)得到不同的數(shù)字簽名s=(γ，δ)，并且都能通過(guò)驗(yàn)證算法的驗(yàn)證，這就是在前面所說(shuō)的不確定性，這個(gè)特點(diǎn)有利于提高安全性。

例6.1

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

y=gamodp=2127mod467=132

若要對(duì)消息m=100簽名，假設(shè)取隨機(jī)數(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重新計(jì)算對(duì)消息m=100的數(shù)字簽名，則有

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

且

γ=gkmodp=2117mod467=126

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

yγγδ=132292951≡189mod467

而

gmmodp=2100mod467=189

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

gmmodp=2100mod467=189

而

yγγδ=132126126350≡189mod467

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

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

yγγδ≡gmmodp

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

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

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

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

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

m1≠m2modφ(p)，有

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

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

兩式相減，得

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

d|(m1-m2)。記

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

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

于是

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

對(duì)于這d個(gè)可能的候選值，只需利用同余式

γ=gkmodp

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

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

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

gm≡yγ(giyj)δmodp

于是有

gm-iδ≡yγ+jδmodp

若

m-iδ≡0modφ(p)

且

γ+jδ≡0modφ(p)

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

γ=giyjmodp

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

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

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

例6.2

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

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

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

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

那么，簽名驗(yàn)證條件

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

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

φ(p)=bq

g=βtmodp

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

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

γ=β=cq

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

顯然，簽名有效性驗(yàn)證同余式成立，即

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

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

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

然后再計(jì)算γ′，使γ′滿足

γ′≡γumodφ(p)

γ′≡γmodp

顯然，可以通過(guò)中國(guó)剩余定理解出γ′。檢查驗(yàn)證同余式是否成立：

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

DSS使用的算法稱為數(shù)字簽名算法(DigitalSignatureAlgorithm，DSA)，它是在ElGamal和Schnorr兩個(gè)方案基礎(chǔ)上設(shè)計(jì)出來(lái)的，本書省略了有關(guān)Schnorr簽名方案的介紹。

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

(1)一個(gè)長(zhǎng)度為l比特的大素?cái)?shù)p，l的大小在512~1024之間，且為64的倍數(shù)。

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

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

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

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

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

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

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

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

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

g=378mod7879=170

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

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

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

所以

說(shuō)明以上簽名是有效的。6.5.2DSA算法的安全問(wèn)題

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

(1)DSA算法不能用于數(shù)據(jù)加密，也不能用于密鑰分配。DSS只是一個(gè)數(shù)字簽名標(biāo)準(zhǔn)，但當(dāng)時(shí)美國(guó)還沒有法定的公鑰加密標(biāo)準(zhǔn)，因此引起了人們對(duì)DSS的猜疑。

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

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

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

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

現(xiàn)在看來(lái)，DSA算法的安全問(wèn)題并不象當(dāng)初很多人猜測(cè)的那樣可怕，有些涉及安全脆弱性的疑慮并不是DSA算法獨(dú)有的，并且可以在算法的具體實(shí)現(xiàn)過(guò)程中通過(guò)適當(dāng)?shù)拇胧┑靡员苊?。但也不能說(shuō)DSA算法是絕對(duì)完美的，在后來(lái)的分析過(guò)程中，一些有關(guān)安全的瑕疵也多次被提出，主要有以下幾個(gè)方面：

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

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

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

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

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

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

y=sigkey(x)=xamodp對(duì)x，y∈G，通過(guò)執(zhí)行以下協(xié)議來(lái)驗(yàn)證簽名(x，y)的有效性：