ElGamal-數(shù)字簽名-修改版

1、ElGamal數(shù)字簽名技術(shù)綜述 摘 要 當今社會是一個信息化的社會，計算機以及互聯(lián)網(wǎng)的普及，讓人們的生活越來越方便，但是，信息安全的問題卻日益突出，尤其表現(xiàn)在計算機網(wǎng)絡的安全問題上。現(xiàn)在網(wǎng)絡安全的形式已不容樂觀，不僅嚴重威脅到人們正常的生活，甚至威脅到國家的安全。因此，信息安全的重要性愈發(fā)突出，而信息安全技術(shù)的核心之一就是數(shù)字簽名技術(shù)。如何在信息傳輸過程中保證信息的安全性和真實性，這是數(shù)字簽名技術(shù)所要研究的重要問題。數(shù)字簽名可以解決否認、偽造、篡改、冒充問題。使用數(shù)字簽名技術(shù)使得發(fā)送者發(fā)送的時候不能否認發(fā)送的報文簽名，接受者不能偽造發(fā)送者的報文簽名。ElGamal數(shù)字簽名方案作為目前最為重要的

2、數(shù)字簽名方案之一，極大地促進了現(xiàn)代密碼學的發(fā)展。ElGamal數(shù)字簽名與一般公鑰密碼體制簽名的不同之處，是具有高安全性和實用性。本文介紹ElGamal的基礎(chǔ)知識以及改進后的ElGamal數(shù)字簽名，闡述了基于ElGamal體制盲簽名和多重數(shù)字簽名。關(guān)鍵詞 信息安全 數(shù)字簽名技術(shù) ElGamal 密碼學ABSTRACT Today is an information society, the popularity of computers and the Internet make lives of people more and more convenient. However, the iss

3、ue of information security has become increasingly prominent, espcially in the issues of the computer network security. At present, the form of the network security is not optimistic, not only a serious thread to peoples normal lives, but also even a thread to national security. Therefore, the impor

4、tance of information security become more prominent, and one of the core password of information security technology is the digital signature technology. How in the process of information transmission to ensure information security and authenticy, which is a important issues the digatal signature te

5、chnology to study. The digital signature can be resolved to the problem of deny, forgery, tampering, posing. Using digital signature technology makes the sender can not deny that send message when recipients can not forged signatures, and the senders message signatures.As currently one of the most i

6、mportant digital signature scheme, ElGamal digital signature scheme greatly stimulates the development of modern cryptography. The difference of ElGamal digital signature and the general public key cryptosystem signature is high safety and practicality. In this paper, we introduced the basic knowled

7、ge of ElGamal digital signature technology and improved ElGamal digital signature, list the ElGamal signature technique based on other signature scheme.Keywords Infomation security, Digatal signature technology, ElGamal, Cryptography第一章 緒論1.1研究背景及意義信息在社會中的地位越來越重要，已成為社會發(fā)展的重要戰(zhàn)略資源，信息安全的重要性也日益突出，而信息安全技術(shù)

8、的核心之一就是數(shù)字簽名技術(shù)。同時現(xiàn)代數(shù)字簽名技術(shù)是解決信息安全的比較有效的方法。因此，數(shù)字簽名的研究成為當前國際上的一個研究熱點。而怎樣利用數(shù)字簽名來保證信息在傳輸過程中的安全性和真實性是當前研究的一個重要課題。1.2信息安全的重要性 信息系統(tǒng)安全的中心內(nèi)容是保證信息在系統(tǒng)中的保密性、認證性和完整性。傳統(tǒng)的密碼體制，其主要功能是信息保密，而現(xiàn)代密碼體制還應保證信息在系統(tǒng)的可認證性和完整性，這樣可以保證在公開信道上安全地傳遞信息。為了防止消息被竄改、刪除、重放和偽造，一種有效的方法是使發(fā)送的消息具有被驗證的能力，使接收者能夠識別和確認消息的真?zhèn)?，實現(xiàn)這類功能的密碼系統(tǒng)稱為認證系統(tǒng)。消息的認證性和

9、消息的保密性不同，保密性是使截獲者在不知密鑰的情況下不能解讀密文的內(nèi)容。而認證性是使任何不知密鑰的人不可以構(gòu)造出一個密文，使意定的接收者脫密成一個可理解的消息(合法的消息)。認證理論和技術(shù)是最近20年來隨著計算機通信的普遍應用而迅速發(fā)展起來，它成為保密學的一個重要的領(lǐng)域。 認證系統(tǒng)主要有以下幾個方面的內(nèi)容：(1)消息認證；(2)身份認證；(3)數(shù)字簽名。前兩者的目的是解決在通信雙方利害一致條件下，如何防止第三方偽裝和破壞的問題。而數(shù)字簽名則解決了當通信雙方是竟爭對象時，如何遠距離迅速地用電子簽名代替?zhèn)鹘y(tǒng)的手寫簽名和印簽的問題。 自從1949年Shannon發(fā)表了題為“保密系統(tǒng)的通信理論”以來，

10、隨著信息時代的來臨和數(shù)字通信技術(shù)的飛速發(fā)展，特別是當今的通信與計算機網(wǎng)絡的結(jié)合，將會逐步使用電子郵件來代替?zhèn)鹘y(tǒng)的書面郵件，這些要求使用這種系統(tǒng)的收方對發(fā)方的身份進行確證，這可用數(shù)字簽名來完成。數(shù)字簽名是現(xiàn)代通信中實現(xiàn)消息認證的一種重要手段。1.3數(shù)字簽名的基本概念數(shù)字簽名，就是只有信息的發(fā)送者才能產(chǎn)生的別人無法偽造的一段數(shù)字串，這段數(shù)字串同時也是對信息的發(fā)送者發(fā)送信息真實性的一個有效證明。其是非對稱密鑰加密技術(shù)與數(shù)字摘要技術(shù)的應用。數(shù)字簽名了的文件的完整性是很容易驗證的，而且數(shù)字簽名具有不可抵賴性。數(shù)字簽名的流程如下所示： 數(shù)字簽名的目的是：（1）使收方能夠確證發(fā)方的簽名，但不能偽造；（2）發(fā)

11、方發(fā)出簽了名的消息給收方后，就不能否認它所簽發(fā)的消息；（3）一旦收發(fā)雙方就消息的內(nèi)容和來源發(fā)生爭執(zhí)時，應能給仲裁者提供發(fā)方對所發(fā)消息簽了名的數(shù)據(jù)。1.4 數(shù)字簽名的功能和應用數(shù)字簽名其功能有以下幾個方面： （1）完整性：數(shù)字簽名與原始的文件或其摘要一起發(fā)送給接收方，一旦信息被篡改，接受者可以通過計算機摘要和驗證簽名來判斷該文件無效。 （2）機密性：將報文信息用接收方的公鑰進行解密，以保證信息的機密性。 （3）防偽造：簽名密鑰即私鑰只有簽名者自己擁有，別人不能偽造出正確的簽名數(shù)據(jù)。這就是防偽造特性。 （4）身份認證：數(shù)字簽名中，公鑰是其身份的標志，使用公鑰簽名，如果接受方或驗證方用其公鑰進行驗證

12、并獲通過，那么可以肯定簽名人就是擁有私鑰的那個人。 （5）防抵賴：數(shù)字簽名可作為簽名者簽名操作的依據(jù)，防止抵賴。 （6）防重放攻擊：通常采用對簽名報文的加蓋時間戳或添加處理流水號等技術(shù)，可以防止重放技術(shù)。數(shù)字簽名的應用如下：數(shù)字簽名技術(shù)最早應用于用戶登錄過程。PKI作為電子商務、電子政務的技術(shù)平臺，使得技術(shù)應用、商業(yè)價值、生產(chǎn)力提高成為有機的整體，得到了長足的發(fā)展。到目前為止，全國省市幾乎都建立了自己的CA認證中心，這些CA中心的數(shù)字證書及相關(guān)應用方案被廣泛應用于網(wǎng)上報關(guān)、網(wǎng)上報稅、網(wǎng)上報檢、網(wǎng)上辦公、網(wǎng)上招投標、網(wǎng)上采購、數(shù)字工商等大型電子政務和電子商務工程中。數(shù)字簽名技術(shù)還廣泛應用于電子郵

13、件、數(shù)據(jù)交換、電子交易和電子貨幣等領(lǐng)域。安全電子交易SET是MasterCard兩大信用卡公司和多家科技公司于1977年制定的一個在Internet上進行的在線交易的安全標準，SET提供了消費者、商家和銀行間的認證，確保了交易數(shù)據(jù)的安全。完整可靠和交易的不可否認，特別是保證了消費者的隱私。SET已經(jīng)成為了目前最流行通用的安全電子商務標準，他的核心技術(shù)主要有公開密鑰加密、數(shù)字簽名、數(shù)字證書、數(shù)字信封等。SET協(xié)議中的數(shù)字簽名技術(shù)之一是雙重簽名，雙重簽名的特性就是把發(fā)給兩個不同通信實體的兩個不同消息聯(lián)系在一起，兩個通信實體都可以驗證該雙重簽名。第二章 ElGamal 數(shù)字簽名2.1 引言2.1.1

14、研究進展1985年，ELGamal基于離散對數(shù)難題提出一種數(shù)字簽名方案，稱為ELGamal數(shù)字簽名方案。1994年，Harn等人對ELGamal及其類似方案進行了總結(jié)，得出了18個安全可行的方案，即廣義ELGamal簽名方案。同時，Horster 也獨立地提出了“Mata-ELGamal簽名方案”，它是Harn的18個方案的進一步推廣。因為ELGamal型簽名方案是在環(huán)或域上進行的二元運算，容易受到同態(tài)攻擊和代換攻擊，因此，在實際應用ELGamal型簽名方案時，需要將明文m進行處理，即利用hash(m)來代替m。1994年，Nyberg和Rueppel對ELGamal簽名方案進行了攻擊，提出具

15、有消息恢復的簽名方案，稱為N-R數(shù)字簽名方案。Hoster, Michels和Petress利用N-S數(shù)字簽名方案具有較小的簽名長度和消息恢復特性設(shè)計了一種低通信消耗的簽名方案，稱為HMP方案。隨后相繼提出很多種具有消息恢復特性的簽名方案。在簽密方案中，信息簽發(fā)者可以對信息進行加密和簽名，信息接收者可以對接收到的信息進行解密和驗證。當消息量很大時，還可以采用消息鏈接的方式進行處理。2.2 ElGamal 數(shù)字簽名方案本節(jié)給出ELGamal簽名方案原形及其它的幾種變形方案，并分析了這些方案在計算上的優(yōu)缺點以及對方案的安全性進行了比較。2.2.1 ElGamal 密碼體制 （1）ElGamal 密

16、碼體制的原理 密鑰產(chǎn)生過程：首先選擇一素數(shù)p以及兩個小于p的隨機數(shù)g和x，計算。以（y，g，p）作為公開密鑰 ，x作為秘密密鑰。 加密過程：設(shè)欲加密明文消息M，隨機選一與p-1互素的整數(shù)k，計算，密文為。 解密過程：。 這是因為。 （2）利用橢圓曲線實現(xiàn)ElGamal 密碼體制 首先選取一條橢圓曲線，并得，將明文消息m嵌入到曲線上得到點，再對點做加密變換。 取得一個生成元G，和G作為公開參數(shù)。 用戶A選作為秘密鑰，并以作為公開鑰。任一用戶B若想向A發(fā)送消息，可選取一隨機正整數(shù)k，產(chǎn)生以下點作為密文： A 解密時，以密文點對中的第2個點減去用自己的秘密鑰與第1個點的倍乘，即 攻擊者若想由得到，就

17、必須知道k。而要得到k，只有通過橢圓曲線上的兩個已知點G和kG，這意味著必須求橢圓曲線上的離散對數(shù)，因此不可行。（關(guān)于橢圓曲線內(nèi)容，筆者就不在此贅述，請讀者閱讀文獻1中橢圓曲線密碼體制一章）2.2.2 基于離散對數(shù)問題的ElGamal 簽名體制（1） 體制參數(shù)p 大素數(shù)；g 的一個生成元；x 用戶A的秘密鑰，；y 用戶A的公開鑰，。（由于k不能相等）（2） 簽字的產(chǎn)生過程對于待簽字的雜湊值m，A執(zhí)行以下步驟：計算m的雜湊值H(m)。選擇隨機數(shù)k：，計算。 （由于 ）計算。以作為產(chǎn)生的數(shù)字簽字。（3） 簽字的驗證過程接收方在收到消息m和數(shù)字簽字后，先計算，并按下式驗證： 正確性可由下式證明： （

18、由于）2.2.3基于身份的 ElGamal 簽名體制（1） 體制參數(shù) 設(shè)q是大素數(shù)，與分別是階為q的加法群和乘法群，是一個雙線性映射，和是兩個雜湊函數(shù)，是系統(tǒng)的主密鑰，P是的一個生成元。用戶ID的公開鑰和秘密要分別是和。（2） 簽字產(chǎn)生過程 對于待簽字的消息m，A執(zhí)行以下步驟： 選擇隨機數(shù)k：。 計算。 計算。 以(R,S)作為產(chǎn)生的數(shù)字簽字。（3） 簽字的驗證過程 接收方在收到消息m和數(shù)字簽字(R,S)后，先計算，并按下式驗證： 正確性可由下式證明： 2.2.4 安全性分析 （1）整體性攻擊。如果一個攻擊者試圖偽造用戶A 對消息m的簽名，他隨機大素數(shù)地選取一個整數(shù)，攻擊成功的概率為,這對于大

19、素數(shù)來講幾乎是不可能的。如果要從r中求出消息密鑰k，將面臨求解離散對數(shù)的難題。 (2)重復性攻擊。如果對不同的消息使用相同的密鑰，則面臨消息密鑰被暴漏的危險。設(shè),，則。若，則，一旦得到k，就很容易求得x。第三章 基于ElGamal數(shù)字簽名體制的其它簽名方案3.1基于ElGamal體制的盲簽名方案盲簽名是一種特殊的數(shù)字簽名，當用戶A發(fā)送消息m給簽名者B時，一方面要求B對消息簽名，另一方面又有不想讓B知道消息內(nèi)容，也就是簽名者B所簽的消息是經(jīng)過盲化處理的。簽名除具有一般數(shù)字簽名的特征外，還有下面兩個特征： （1）簽名者無法知道所簽消息的具體內(nèi)容，雖然他為這個消息簽了名。（匿名性） （2）即使后來簽

20、名者見到這個簽名時，也不能將之與盲消息對應起來。（不可跟蹤性）其中引入了有向因子，有向盲簽名方案構(gòu)造為:設(shè)，Alice，Bob各自的私鑰和公鑰，現(xiàn)在。Alice需Bob為消息m進行盲簽名。3.1.1盲簽名過程 步驟如下： 步驟1 Alice：隨機選擇盲因子，滿足計算,將M送給Bob。 步驟2 Bob: (1)接受到M后，隨機選擇k，,計算,; （2）求出; （3）將作為簽名送給Alice。 步驟3 Alice：首先，求出,驗證 如果不等式成立，則拒絕接受Bob對盲消息的簽名。然后由對盲消息M的簽名S恢復出對原消息m的簽名s 驗證等式是否成立，決定恢復的s是否正確。方案中各種符號的具體含義分別為

21、：p為一個大素數(shù)，可使中求解離散對數(shù)為困難問題；m為原消息；M為盲化后的消息；s為原消息的簽名；S為盲消息的簽名；g，k，r參數(shù)的意義和ElGamal簽名體制中一致。3.1.2.性能分析 1安全性分析 （1）有向因子的引入使得只有驗簽雙方具有簽名和驗證簽名的權(quán)利，其他參與者和用戶或攻擊者將不具備驗證消息簽名的權(quán)利。攻擊者欲求出，須知道私鑰或，這將面臨求解離散對數(shù)問題。 （2）攻擊者如獲取盲消息M,欲從M中求得私鑰，將面臨離散對數(shù)問題，而如果想求出原消息m，因為t是一大的隨機數(shù)，將面對大整整因子分解的困難。 （3）攻擊者想要從中求得簽名者私鑰，因為k為簽名者隨機選取的大素數(shù)，所以必然面臨大整數(shù)因

22、子分解的困難；而欲從中求出k，也會同樣面臨求解離散對數(shù)問題。 2方案特點 （1）將發(fā)送方的私鑰引入對消息的盲化，即,相比于原有的盲化方法，提高了盲消息的抗攻擊性能。 （2）在本方案中，引入有向因子，使得只有特定收發(fā)方才具有對消息進行簽名的能力，攻擊者無法通過對消息進行簽名而對簽名進行跟蹤。在ElGamal簽名體制基礎(chǔ)上，設(shè)計了一種新的盲簽名技術(shù)。在簽名過程中通過有向因子的引入，實現(xiàn)了定向用戶驗簽的功能，并且將私鑰引入對消息的盲化過程，提高了算法的安全性能。該方案將加密和盲簽名融為一體，具有較高的安全性和實用性就，必將有利于推動電子商務的發(fā)展并使盲簽名技術(shù)在選舉投票、數(shù)字貨幣協(xié)議、電子支付系統(tǒng)等

23、中得以廣泛的應用。3.2基于ElGamal體制的多重數(shù)字簽名方案在數(shù)字簽名應用中，有時需要多個用戶對同一文件進行簽名和認證，比如，一個公司發(fā)表的聲明涉及到財務部、開發(fā)部、銷售部、售后服務部等部門，需要這些部門簽名認可，那么，需要這些部門對這個聲明文件進行簽名。能夠?qū)崿F(xiàn)多個用戶對同一文件進行簽名的數(shù)字簽名方案稱為多重數(shù)字簽名方案。根據(jù)不同的簽名過程，多重數(shù)字簽名方案可分兩類：廣播多重數(shù)字簽名和有序多重簽名方案。以下就基于ElGamal體制的廣播多重數(shù)字簽名展開具體闡述。基于ElGamal體制的廣播多重數(shù)字簽名是指在簽名過程中，簽名組成員之間沒有簽名的先后順序，但要求必須有一個簽名收集者，最終完成

24、整個簽名。在廣播多重數(shù)字簽名方案中，文件發(fā)送者同時將文件發(fā)送給每一位簽名者進簽名，然后簽名者將簽名文件發(fā)送到簽名收集者，由收集者對簽名文件進行整理并發(fā)送給簽名驗證者，簽名驗證者驗證多重簽名的有效性。下圖描述了廣播多重數(shù)字簽名方案。過程如圖4-2所示： 簽名發(fā)送者文件簽名者簽名收集者簽名收集者圖4-2廣播多重簽名過程方案描述:方案包含系統(tǒng)初始化、簽名和驗證過程，方案的參與者有消息發(fā)送者、若干簽名者、簽名收集者和。（1）系統(tǒng)初始化 每一位簽名者任意選取作為的私鑰，并計算作為公鑰。公開參數(shù)有p,g, (i=1,2，、n)和h。（2）簽名過程 將m發(fā)送給每一位簽名者,隨機選取,計算,發(fā)送給其他每一位簽

25、名者;收到后計算然后再計算,將簽名（m,( ,)）發(fā)送到。收到后，其中，首先按照上式計算R，然后驗證方程是否成立。若成立，說明的簽名是對的，否則，不接受，要求重新簽名或放棄本次簽名。計算,則多重簽名是。 （3）驗證過程當收消息后，驗證等式為 如果等式成立，認為簽名有效，否則，簽名無效?；贓lGamal體制的多重簽名方案有以下特點：（1） 多重簽名是每個簽名成員生成部分簽名，以合作的方式生成多重簽名；（2） 部分簽名的方式固定，不隨簽名人員的改變而變化；（3） 部分簽名算法和驗證算法的復雜度與簽名人數(shù)無關(guān)，還具有簡單的初始化過程，在簽名時具有隨機性，在簽名過程中無需求逆，具有更高的實用性和安全性。第四章 總結(jié)與感想 本文較系統(tǒng)地介紹了信息安全在當今社會的重要地位，其中強調(diào)數(shù)字簽名技術(shù)在信息安全中的重要作用，而ElGamal作為一種重要的數(shù)字簽名技