摘要：隨著網(wǎng)絡(luò)技術(shù)的飛速發(fā)展及網(wǎng)上活動的日益頻繁，信息安全成為一個非常突出的問題，而數(shù)字簽名技術(shù)在保證數(shù)據(jù)的完整性、可控性和不可抵賴性等方面起著極為重要的作用。在對數(shù)字簽名技術(shù)宏觀分析的基礎(chǔ)上，文中主要討論了RSA、ElGamal、DSA、ECDSA等典型簽名方案，并分析了數(shù)字簽名的發(fā)展前景。

關(guān)鍵詞：數(shù)字簽名；RSA；ElGamal；DSA；ECDSA

中圖分類號：TN918文獻標識碼：A文章編號：1009-3044(2008)12-2pppp-0c

Survey and Trend of Digital Signature

LIU Zhao-li1，WEI Shi-min2，LI Xiao-cheng1

(1.Institute of Mathematics Science，Huaibei Coal Teachers College，Huaibei 235000，China; 2.Institute of Computer Science Technology，Huaibei Coal Teachers College，Huaibei 235000，China)

Abstract:With the development of the network technology and the high frequency activity in the network，the secure of information have become a very important problem. Digital signature has very important function in protecting the integrity，controllability and non-repudiation of information.Based on the macro-analysis of digital signature，analyzes several digital signature，i.e. RSA、ElGamal、DSA、ECDSA etc，and the trend of digital signature are analyzed in the paper.

Key words:Digital signature;RSA;ElGamal;DSA;ECDSA

20世紀70年代，公鑰密碼體制的誕生標志了現(xiàn)代密碼學的形成。不久，基于PKI的數(shù)字簽名技術(shù)也隨之產(chǎn)生。自數(shù)字簽名概念提出后，數(shù)字簽名的基礎(chǔ)理論和應用研究引起了世界各國的廣泛重視[1]。理論研究方面，基于各種PKI體制的數(shù)字簽名方案和適應某些特殊要求的數(shù)字簽名方案應運而生，各種數(shù)字簽名的安全性分析和攻擊分析研究也日益火熱；應用研究方面，數(shù)字簽名標準和數(shù)字簽名法案越來越完善，數(shù)字簽名的應用領(lǐng)域越來越廣。1991年8月美國NIST（National Institute of Standard and Technology）公布了數(shù)字簽名標準（DSS）。2000年6月，美國通過數(shù)字簽名法案。進入21世紀，數(shù)字簽名技術(shù)已經(jīng)廣泛運用于商業(yè)、金融、軍事、政府、電子購物等領(lǐng)域。2004年8月，我國正式頒布了《中華人民共和國電子簽名法》，從而確立了電子簽名的法律效力和地位。這部法律有力地保障和支持了我國數(shù)字簽名理論和應用研究的順利進行。

文章分為3部分：第1部分簡要介紹了數(shù)字簽名理論的數(shù)學基礎(chǔ)；第2部分分類討論了基于大素數(shù)因子分解、離散對數(shù)分解和橢圓曲線難題的重要數(shù)字簽名體制；第3部分給出了結(jié)論，并對數(shù)字簽名體制的發(fā)展和努力方向做了展望。

1 數(shù)字簽名的數(shù)學描述

1.1 數(shù)字簽名的形式化定義

數(shù)字簽名，是一種基于公鑰密碼體制的以電子形式存儲的消息簽名，一般包含三個主要過程：系統(tǒng)的初始化過程、簽名產(chǎn)生過程和簽名驗證過程。系統(tǒng)的初始化過程產(chǎn)生數(shù)字簽名用到一切參數(shù)；簽名產(chǎn)生過程中，發(fā)送方利用給定的算法對消息產(chǎn)生簽名；簽名驗證過程中，接收方利用公開的驗證方法對接收到的信息的數(shù)字簽名進行有效驗證。

定義：一個數(shù)字簽名方案包括簽名算法和驗證算法，一般由以下部分組成[2]：

(1)一個明文消息空間M：某字母表中串的集合

(2)一個簽名空間S：可能的簽名集合

(3)一個簽名密鑰空間K：用于生成簽名的可能密鑰集合，和一個認證密鑰空間K'：用于驗證簽名的可能密鑰集合

(4)一個有效的密鑰生成算法Gen：N→K×K'，其中K和K'分別為私鑰和公鑰空間

(5)一個有效的簽名算法Sign：M×K→S，

(6)一個有效的驗證算法Verify：M×S×K'→S(True，F(xiàn)alse)

對任意的sk∈K和任意的m∈M，我們用

s←Singnsk(m)

表示簽名變換。

對于任意的私鑰sk∈K，用pk表示與sk相匹配的公鑰。對于m∈M和s∈S，必有

其中，概率空間包括S，M，K和 。

一個有效的數(shù)字簽名方案必須經(jīng)過安全性證明，并具備以下功能：

(1)保證信息的完整性，數(shù)據(jù)不被篡改。根據(jù)單向函數(shù)的性質(zhì)，一旦原始信息被改動，所生成的數(shù)字摘要就會發(fā)生很大的變化，即發(fā)生雪崩效應。因此，通過此種方式，能防止原始信息被篡改；

(2)具有不可否認性。既然只有發(fā)送者可以生成消息的一個數(shù)字簽名，并可以被任何人所驗證，所以就很容易處理關(guān)于是誰生成了該簽名的糾紛，即不可否認性；

(3)具有抗偽性。偽造一個數(shù)字簽名在計算上不可行，無論是通過以后的數(shù)字簽名來構(gòu)造新的消息，還是對給定的消息構(gòu)造一個虛假的數(shù)字簽名。

1.2 數(shù)字簽名方案的數(shù)學基礎(chǔ)

數(shù)字簽名是基于各種公鑰密碼體制的，因此其安全性也依賴于單向陷門函數(shù)的安全性。絕大多數(shù)的數(shù)字簽名方案都是基于以下三個數(shù)學難題：

1.2.1 大素數(shù)因子分解難題

已知兩個大素數(shù)p和q，要求n=pq，非常簡單，只需要1次乘法。但是，若知道n，求p和q則是幾千年來數(shù)論學者的研究難題，當n很大時，則異常困難。這就是所謂的大素數(shù)因子分解問題。目前，對于大于110位的整數(shù)，數(shù)域篩選法是最快的算法，其分解時間為T(n)=O(exp(1.92+0(1))(ln n)1/3(lnlnn2/3))。

1.2.2 素數(shù)域上的離散對數(shù)難題

設(shè) 是一個素數(shù)，g∈F*p是其生成元，已知x∈F*p，求y=gxmodp，非常簡單。但是，若已知y，通過y=gxmodp求x，則非常困難。這就是所謂的離散對數(shù)問題（DLP）。目前，其最快的求解時間復雜度為lzl02.tif 。

1.2.3 橢圓曲線難題

設(shè)p是一個素數(shù)，?P，Q∈E(GF(p))，若存在某整數(shù)k，使得Q=kP，稱k為點Q的橢圓曲線離散對數(shù)（ECDL）。由P，Q，求k的問題就稱為E上的橢圓曲線離散對數(shù)問題（ECDLP）。目前為止，還沒有出現(xiàn)較好的低于指數(shù)級時間的求解算法。

除了上述三個難題之外，還有多項式求根問題、背包問題、二次剩余問題等都可以作為數(shù)字簽名方案的數(shù)學基礎(chǔ)。

2 經(jīng)典數(shù)字簽名方案的探討

`自從1979年，G.J.Simmons將數(shù)字簽名應用于美蘇兩國的禁止核試驗條約的驗證工作中以來，數(shù)字簽名技術(shù)引起了學術(shù)界尤其是密碼學界和計算機界的廣泛重視，特別是隨著網(wǎng)絡(luò)的飛速發(fā)展，出現(xiàn)了許多簽名算法。根據(jù)其基于數(shù)學難題的不同，可以分為基于大素數(shù)因子分解難題的數(shù)字簽名方案、基于離散對數(shù)難題的數(shù)字簽名方案、基于橢圓曲線難題的數(shù)字簽名方案和基于離散對數(shù)和大素數(shù)因子分解難題結(jié)合的數(shù)字簽名方案等。

2.1 基于大素數(shù)因子分解難題的數(shù)字簽名方案

基于大素數(shù)因子分解難題的數(shù)字簽名體制的典型代表是RSA簽名體制。此外，還有Rbani簽名方案、Fiat一Shamir簽名方案和Guillou一Quisquater簽名方案等。

RSA算法是當前最著名、應用最廣泛的公鑰體制。它是美國麻省理工學院的Rivest， Shamir和Adleman在1978年提出的一種非對稱加密算法。RSA算法也是第一個既能用于數(shù)字加密，又能用于數(shù)字簽名的算法。RSA數(shù)字簽名體制是采用RSA算法來實現(xiàn)數(shù)字簽名的。當用于數(shù)字簽名時，簽名者使用自己的私鑰來完成簽名，驗證者使用簽名者的公鑰來完成認證。RSA算法已經(jīng)經(jīng)過各界多年的深入分析，到目前為止仍然認為是安全的，且是最為廣泛采用的一種密碼體制。

RSA數(shù)字簽名體制的缺點主要有：(1)產(chǎn)生密鑰很麻煩，受到素數(shù)產(chǎn)生技術(shù)的限制，因而難以做到一次一密。(2)分組長度太大，為保證安全性，至少也要600 bits以上，目前通常都采用1024bits，使運算代價很高，尤其是速度較慢，較對稱密碼算法慢幾個數(shù)量級，且隨著大數(shù)分解技術(shù)的發(fā)展，這個長度還在增加，不利于數(shù)據(jù)格式的標準化。

2.2 基于離散對數(shù)難題的數(shù)字簽名方案

由于離散對數(shù)計算的復雜性，且其指數(shù)運算的化簡和處理比其他運算相對簡單，很容易構(gòu)造不同的方案，因此基于離散對數(shù)難題的數(shù)字簽名方案應用特別廣泛、資源也相當豐富。現(xiàn)在的大部分方案如ElGamal數(shù)字簽名方案、廣義ElGamal數(shù)字簽名方案、Schnorr數(shù)字簽名方案、DSA方案、Neberg一Rueppel簽名方案、Okamoto簽名方案、Miyaji簽名方案等都是基于這個難題進行設(shè)計的。

2.2.1 ElGamal數(shù)字簽名方案

ElGamal數(shù)字簽名方案是ElGamal于1985年基于離散對數(shù)難題提出的。ElGamal數(shù)字簽名方案包含系統(tǒng)初始化、簽名過程和驗證過程。

(1)系統(tǒng)初始化過程

設(shè)p是一個素數(shù)，g∈Zp*是一個生成元，?x(1

(2)簽名過程

對于待簽消息m，簽名方A任意選取一個隨機數(shù)k(

(3)驗證過程

接收方B收到消息m和簽名(r，s)后，驗證gm=yrrs mod p是否成立？如成立，則接收簽名。否則，拒絕簽名。

易見，lzl03.tif。正確性得證。

ElGamal數(shù)字簽名方案提出后，關(guān)于ElGamal數(shù)字簽名方案的改進和推廣不斷出現(xiàn)。1994年，Harn等人對ElGamal數(shù)字簽名方案及其類似方案進行總結(jié)，列出了18個安全可行的方案[3]，得到了廣義ElGamal數(shù)字簽名方案。Horster又對之做了繼續(xù)推廣。我國李繼紅[4]等學者亦對之做了深入研究，取得了一定成果。ElGamal數(shù)字簽名方案容易受到同態(tài)攻擊和代換攻擊，因此在實際應用中，要對明文消息進行Hash函數(shù)處理。

2.2.2 DSA數(shù)字簽名方案

DSA數(shù)字簽名方案是1991年8月美國NIST公布的數(shù)字簽名標準（DSS）中采用的數(shù)字簽名算法。DSA只能簽名，不能用作加密。DSA簽名算法是ElGamal簽名算法和Schnorr簽名算法的變種，具有較大的兼容性和適用性，成為網(wǎng)絡(luò)安全體系的基本構(gòu)件之一。

DSA的簽名和驗證過程中，需要用到比較計算模冪或求逆元的計算，需要耗費大量的時間，為了加快運算速度，一般采用預處理的方法。Yen和Laih從盡可能避免求逆運算的角度對DSA簽名方案進行了改進。

2.3 基于橢圓曲線難題的數(shù)字簽名方案

橢圓曲線研究開始于19世紀，至今已有150多年的歷史了。1985年Miller和Kobilitz分別提出將橢圓曲線理論用于公鑰密碼學，從而形成了橢圓曲線密碼體制（Elliptic Curve Cryptogram，ECC）?；跈E圓曲線的數(shù)字簽名體制通過ECC公開密鑰加密技術(shù)和報文分解函數(shù)實現(xiàn)。簽名方把被簽名文件通過Hash函數(shù)處理后進入簽名函數(shù)，在簽名函數(shù)中使用簽名方的私鑰對文件簽名，并將產(chǎn)生的簽名與文件原文一同發(fā)送給接收方。接收方收到簽名后，文件原文使用相同的散列函數(shù)進行處理，在驗證函數(shù)中接收方使用簽名方的公鑰對文件的簽名進行驗證，從而確認文件是否為偽造的，是否在傳輸過程中被篡改[5]。基于橢圓曲線的數(shù)字簽名具有密鑰短、運算快和安全性高等優(yōu)點，因此在密碼學中占有十分重要的地位，應用領(lǐng)域不斷擴大，而且基于大素數(shù)因子分解、離散對數(shù)等數(shù)學難題的簽名方案理論上幾乎都可以橢圓曲線密碼體制中來。基于橢圓曲線問題的數(shù)字簽名大有取代已有簽名體制之趨勢。

ECDSA是Scott vanstone于1992年提出的，在橢圓曲線上實現(xiàn)了的DSA算法。該簽名方案包括系統(tǒng)初始化、簽名過程和驗證過程。

2.3.1 系統(tǒng)初始化

ECDSA全局參數(shù)為(q，F(xiàn)R，a，b，G，n，h))，其中q為有限域的大小，F(xiàn)R為GF(q)中的一個元素；a，b∈GF(q)且橢圓曲線為y2=x3+ax+b或y2+xy=x3+ax2+b；G=(xG，yG)為基點，G的階為素數(shù)n，n>2160 ，n>2?q；h=#E(GF(q))/n。隨機選取d∈[1，n-1]為私鑰，則Q=dG為相應公鑰。

2.3.2 簽名過程

(1)對于待簽明文消息m，用HASH－1函數(shù)計算e=H(m)，并轉(zhuǎn)化為一個160位的整數(shù)；

(2)任意選取一個隨機整數(shù)k∈[1，n-1]，計算kG=(x1，y1)；

(3)計算r=x1 mod n，如果r為0，則返回（2）重新選擇k；

(4)計算s=k-1(e+dr) mod m，如果s為0，則返回（2）；

(5)得到消息m的簽名為(r，s)。

2.3.3 驗證過程

(1)判斷(r，s)是否屬于[1，n-1]，否則簽名無效；

(2)計算e=H(m)；

(3)計算w=s-1 mod n；

(4)計算u1=ew mod n，u2=rw mod n；

(5)計算X=u1G+u2Q如果X＝0，表示簽名無效；否則x=(x1，y1)，計算v=x1 mod n；

(6)如果v=r則簽名有效；否則無效。

由于X=u1G+u2Q=(u1+u2d)G=kG，r=x(kG)modn，所以v=x1 mod n=x(X)mod n =r，ECDSA的正確性得證。

ECDSA具有安全性高、密鑰長度短、存儲空間小、帶寬要求低、算法靈活和算法速度快等優(yōu)點[6]。經(jīng)過不斷發(fā)展，不同的國際組織基于ECDSA，制定了有關(guān)標準，以推進密碼技術(shù)的廣泛使用和不同操作環(huán)境的互操作性。1998年，國際標準化組織ISO制定15014888一3標準；1999年，美國國家標準化組織ANSI出臺ANSI X9.62標準；2000年，電氣和電子工程師協(xié)會IEEE制定了IEEE1363-2000參考標準；2000年，美國國家標準技術(shù)研究所(NIST)制定了聯(lián)邦信息處理標準[7]FIPS186-2，推薦美國政府使用的15個不同安全級別的橢圓曲線，分為三類：①素域Fp上的隨機橢圓曲線5條（素域的階p分別為：P192，P224，P256，P384，P521）；②二進制域F2m上的隨機橢圓曲線5條（二進制域擴展次數(shù)m分別為:163，233，283，409，571）；③二進制域F2m上的Koblitz橢圓曲線5條(二進制域擴展次數(shù)m分別為:163，233，283，409，571)。(5)密碼標準化組織(SECG)是企業(yè)間為解決密碼標準的互操作性而成立的聯(lián)盟。其SECI規(guī)定了ECDSA、ECIES、ECDH和ECMQV，并嘗試與ANSI、NIST、IEEE及ISO/IEC橢圓曲線標準兼容。在SEC2中推薦了包括15個NIST橢圓曲線在內(nèi)的一些特殊的橢圓曲線。這些標準的制定將為ECDSA進一步發(fā)展提供一個良好的平臺。

2.4 其他簽名方案

除了以上幾種常用的簽名體制外，研究者們還提出了一些特殊用途的數(shù)字簽名方案[1]，如代理簽名(Proxy Signature)、群簽名(Group Signature)、盲簽名(Blind Signature)、多重簽名等等。這幾類簽名體制在電子商務、公共資源的管理、軍事命令的簽發(fā)、金融合同的簽署等方面有著廣泛的應用前景。

3 結(jié)論

目前，基于PKI的數(shù)字簽名體制己經(jīng)廣泛應用于商業(yè)、金融、軍事等領(lǐng)域，尤其是在網(wǎng)絡(luò)通信、電子郵件、電子商務、電子政務方面。數(shù)字簽名還可以應用到訪問控制、軟件驗證、病毒檢測等不同領(lǐng)域。文中較為全面地介紹了目前國際上較為流行的幾種數(shù)字簽名方案，特別是基于橢圓曲線問題的數(shù)字簽名方案。當然，由于篇幅所限，還有一些沒有涉及到，比如MR(message recovery)簽名方案[8]等。

由于數(shù)字簽名技術(shù)廣泛應用仍需解決的一些局限性，如不能充分實現(xiàn)數(shù)字簽名具有的特殊鑒別作用，軟件的普及性還不高，被剝奪了相應權(quán)限后原先的數(shù)字簽名的認證問題等[9]，。特別是，我們國家還沒有自己的ECC標準。因此改進數(shù)字簽名在內(nèi)的安全技術(shù)措施、確定CA認證權(quán)的歸屬和標準制定等問題依然十分關(guān)鍵。相信隨著Internet的快速發(fā)展及其算法的不斷改進和完善，數(shù)字簽名的發(fā)展前景一定會越來越廣闊。

參考文獻：

[1]趙澤茂.數(shù)字簽名理論[M].北京:科學出版社，2007.

[2][英]Webo Mao著.王繼林，伍前紅，等.譯.現(xiàn)代密碼學理論與實踐[M].北京:電子工業(yè)出版社，2006.

[3]Harn L，Xu Y，Perersen H. Design of ElGamal type digital scheme based on discrete logarithm[J].Electronics letters，1994，31(24):2025-2026.

[4]李繼紅.ElGamal數(shù)字簽名方案及其應用研究[D].西安:西安電子科技大學，1999.

[5][加]Douglas R.Stinson，著.馮登國，譯.密碼學原理與實踐[M].北京:電子工業(yè)出版社，2003.

[6]D.Johanson，A.Menezes，S.Vanstone.The elliptic curve digital signature algorithm (ECDSA).Internatinal Journal on Information Security，2001，1:36-63.

[7]Koblitz N. Elliptic curve cryptosystems[J].Mathematics of Computation，1987，48(5):203-209.

[8]Nyberg K，Rueppel RA.Messege recovery for signature schems based on the discrete logarithm[C].Advances in Cryptology-Eurocrypt'94，Berlin:Springer-Verlag，1994.175-190.

[9]斷云所，魏仕民，唐禮勇，等.信息安全概論.北京:高等教育出版社，2003.

收稿日期：2008-01-26

作者簡介：劉兆麗（1979-），女，山東臨沂人，碩士生，研究方向：信息安全；魏仕民，男，教授，碩導。

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文?！?/p>