一種基于橢圓曲線的前向安全數(shù)字簽名

陳輝焱 ，袁 勇 ，萬(wàn)宗杰 ，劉 樂(lè) ，楊 毅

（1.北京電子科技學(xué)院 北京100070；2.西安電子科技大學(xué) 西安 710071）

1 引言

在一般的數(shù)字簽名中，簽名密鑰一旦泄露，不但后面簽名的安全性無(wú)法保證，先前簽名的安全性也無(wú)法保證。為了解決這個(gè)問(wèn)題，幾種不同的方式被提出。很多人嘗試通過(guò)幾個(gè)系統(tǒng)的密鑰分配來(lái)降低密鑰泄露的可能性。就像在參考文獻(xiàn)[1]中提到的，這種方法十分昂貴，以至于對(duì)于個(gè)體用戶來(lái)說(shuō)并不實(shí)用。既然每一個(gè)系統(tǒng)仍然可能遭受相同的攻擊，因此實(shí)際的風(fēng)險(xiǎn)也并沒(méi)有減少。

另一種降低由于密鑰泄露所引起安全性的方法被稱(chēng)為前向安全。主要思想是確保密鑰僅在很短的時(shí)間段內(nèi)使用，當(dāng)前的密鑰泄露并不會(huì)影響前面時(shí)間段的安全性。設(shè)計(jì)一個(gè)如此系統(tǒng)的挑戰(zhàn)在于，在不改變公共信息的前提下改變秘密信息。這種方式在參考文獻(xiàn)[2,3]中在密鑰交換背景下被看作前向安全。在數(shù)字簽名中，前向安全與一些簡(jiǎn)單的方案首先被Anderson[4]提出。Bellare和Miner[5]首次給出了前向安全數(shù)字簽名的正式定義，并基于Fiat A和Shamir A[6]簽名方案給出了兩個(gè)前向安全數(shù)字簽名方案。

前向安全數(shù)字簽名的主要思想是在傳統(tǒng)的數(shù)字簽名方案中添加了“密鑰進(jìn)化算法”。在密鑰進(jìn)化算法中，密鑰被拆分為很多時(shí)間段，在每一個(gè)時(shí)間段中有不同的密鑰。每一個(gè)密鑰被用于簽名特定時(shí)間段的簽名信息，并且在每一個(gè)時(shí)間段結(jié)束時(shí)產(chǎn)生新的密鑰。前一時(shí)間段的密鑰被抹去。就像一般的簽名方案一樣，在所有的時(shí)間段內(nèi)只存在唯一的公鑰。驗(yàn)證算法不僅要檢測(cè)簽名是否有效，而且還要檢測(cè)它是否是在特定的時(shí)間段內(nèi)產(chǎn)生的。因此在一個(gè)具有前向安全的方案中，自適應(yīng)選擇信息的攻擊者即使獲得了當(dāng)前時(shí)間段的密鑰想要偽造前面時(shí)間段的簽名是困難的。特別是過(guò)去的密鑰并不能通過(guò)當(dāng)前的密鑰獲得。在一個(gè)前向安全數(shù)字簽名方案中，即使當(dāng)前的密鑰泄露了，過(guò)去時(shí)間段的簽名仍然是可信的。

目前，多數(shù)前向簽名方案的安全性都是建立在大素?cái)?shù)因子分解和有限域離散對(duì)數(shù)問(wèn)題之上的。隨著用戶對(duì)安全性要求的提高，密鑰長(zhǎng)度勢(shì)必增加，造成了基于乘法群上的數(shù)字簽名方案運(yùn)行速度大大降低，使得現(xiàn)有的前向簽名方案無(wú)法再適應(yīng)擁擠的網(wǎng)絡(luò)、智能卡和無(wú)線終端等資源有限的設(shè)備和環(huán)境，使得前向簽名的實(shí)用性大大減弱。隨著設(shè)備的要求越來(lái)越苛刻，橢圓曲線密碼體制的優(yōu)越性進(jìn)一步體現(xiàn)出來(lái)。對(duì)于具有同樣規(guī)模的密碼參數(shù)，橢圓曲線加密（elliptic curve cryptography，ECC）算法每一字節(jié)密鑰的強(qiáng)度要比RSA和ElGamal密碼系統(tǒng)大得多。而要達(dá)到相同的加密強(qiáng)度，ECC參數(shù)的規(guī)模要比上述兩者小得多。這使得ECC和橢圓曲線數(shù)字簽名算法 （elliptic curve digital signature algorithm，ECDSA）在實(shí)現(xiàn)和實(shí)際應(yīng)用中具有更快的速度和更大的安全優(yōu)勢(shì)[7]。

隨著近兩年計(jì)算機(jī)網(wǎng)絡(luò)以及移動(dòng)通信終端技術(shù)的快速發(fā)展，橢圓曲線密碼體制[8]越來(lái)越受到人們的重視，正逐步成為當(dāng)前主流的公鑰密碼體制。參考文獻(xiàn)[9]提出了一種基于橢圓曲線的前向數(shù)字簽名方案，但是該方案并不具備真正的前向安全性。因?yàn)楣粽咭坏┲懒撕灻巳我鈺r(shí)段的簽名私鑰就可以偽造簽名者任意時(shí)段的簽名。因此本文在研究A-R算法[10]的基礎(chǔ)上，根據(jù)橢圓曲線的相關(guān)知識(shí)構(gòu)建了一種全新的基于橢圓曲線的前向安全數(shù)字簽名方案。該方案具有真正的前向安全性，在下文將會(huì)進(jìn)行詳細(xì)的論述。

2 基本概念

本文用到的符號(hào)說(shuō)明如下。

·Fp：表示有p個(gè)元素的有限域，其特征為大素?cái)?shù)p。

·Zn*：表示有n個(gè)元素的整數(shù)環(huán)Zn除了0元素以外的其他所有元素。

·h(m)：表示信息m用散列函數(shù)進(jìn)行處理后的輸出值。

2.1 前向安全簽名方案的定義及性質(zhì)

前向安全簽名的定義如下。

定義1 （前向安全數(shù)字簽名方案）前向安全數(shù)字簽名方案一般包括密鑰生成算法、密鑰進(jìn)化算法、簽名算法和驗(yàn)證算法?？梢孕问交乇硎緸镕S=(KG,evolving,sign,verify)。下面分別介紹這4個(gè)算法。

· 密鑰生成（key generator，KG）算法：在該算法中，選擇k∈N，T表示方案運(yùn)行的總周期數(shù)，把作為秘密參數(shù)的k、T和其他參數(shù)輸入系統(tǒng)，輸出公鑰PK和初始私鑰SK0。用(PK,SK0)←KG(1k,T)表示。

· 密鑰進(jìn)化（evolving）算法：在該算法中，用戶在本周期(j-1)結(jié)束時(shí)輸入當(dāng)前周期的私鑰SKj-1，輸出下一周期私鑰SKj，然后刪除上一周期的私鑰SKj-1。用SKj←Evo(SKj-1)表 示 。

· 簽名（sign）算法：在該算法中，輸入已知的當(dāng)前周期j、私鑰SKj和要簽名的簽名消息M；輸出該周期對(duì)消息M的簽名(j,ξ)。用(j,ξ)←SgnSKj(M)表示。

·驗(yàn)證（verify）算法：在該算法中，輸入已知的當(dāng)前周期j、公鑰PK、簽名消息M、待驗(yàn)證簽名(j,ξ)；輸出值為0表示拒絕該簽名，輸出值為1表示接受該簽名。用b←VfPK(M,(j,ξ))表示。

在上面4個(gè)算法中，密鑰產(chǎn)生算法和簽名算法為概率性算法；而密鑰進(jìn)化算法和驗(yàn)證算法為確定性算法。約定如果總周期數(shù)為T(mén)，則SKT+1為空字符串。

定義 2 （不可偽造性）不可偽造性（unforgeability）是指在不知道前向安全簽名私鑰的條件下，任何攻擊者都不可能成功偽造任何一個(gè)有效的前向安全簽名。

定義3 （前向安全性）前向安全性（forward-secure）是指在前向簽名方案中，即使入侵者獲得了在t時(shí)刻的密鑰，也無(wú)法還原t時(shí)刻之前的密鑰，從而無(wú)法偽造t時(shí)刻之前的簽名。

2.2 基于的困難問(wèn)題

定義4 （橢圓曲線離散對(duì)數(shù)問(wèn)題）給定一個(gè)橢圓曲線曲線E，P為橢圓曲線上的一點(diǎn)，且階為大素?cái)?shù)n。選取一隨機(jī)數(shù)k∈，可以很容易計(jì)算出Q=kP。但是如果知道P和Q，求解k卻是十分困難的。

定義5 （大數(shù)分解問(wèn)題）p和q為兩個(gè)大素?cái)?shù)，N=p·q。知道p和q求解N是容易的，但是如果知道N想要求出p和q卻變得十分困難。

3 基于橢圓曲線的前向安全簽名設(shè)計(jì)

（1）密鑰生成算法

·選取一條在域FP上的安全橢圓曲線E，取屬于E上的一點(diǎn)P，其階為大素?cái)?shù)n。

· 設(shè)方案的總周期為T(mén)。隨機(jī)選取兩個(gè)不同的大素?cái)?shù)p1和p2，計(jì)算N=p1p2且N＞n。

· 取整數(shù)d0∈，輸出私鑰SK0=d0。

（2）密鑰進(jìn)化算法

（3）簽名算法

①取整數(shù)k，使k∈。

②計(jì)算k2T+1-jP=(x,y)，r=xmodn。若r=0，則轉(zhuǎn)到步驟①。

③計(jì)算消息的散列值e=h(m||r||j)，s=SKjekmodn。若s=0，則轉(zhuǎn)到步驟①。

④發(fā)送簽名(j,ξ)和信息m給驗(yàn)證者，其中ξ=(r,s)。

（4）驗(yàn)證算法

· 取得公鑰PK=(P,E,n,Q)，簽名(j,ξ)和信息m，驗(yàn)證r,s∈。

· 計(jì)算e=h(m||r||j)。

· 計(jì)算(se-1)2T+1-jQ=(x1,y1)。

· 計(jì)算v=x1modn。

· 計(jì)算v=r，若成立，簽名有效；否則簽名無(wú)效。

4 安全性分析

4.1 正確性

所以本方案顯然是正確的。

4.2 前向安全性

（1）密鑰進(jìn)化算法的前向安全性

（2）簽名算法的前向安全性

假如攻擊者已經(jīng)獲得了第j時(shí)段的私鑰，它如果想要第j時(shí)段的私鑰來(lái)偽造第j-1時(shí)段的簽名，如式（2）：

通過(guò)上面的分析，本方案解決了攻擊者一旦知道了簽名人任意時(shí)段的簽名私鑰，在不知道前面時(shí)刻私鑰的情況下就可以偽造簽名者任意時(shí)段簽名的問(wèn)題。

因此，通過(guò)以上兩部分的系統(tǒng)分析可以得出：當(dāng)攻擊者知道第j時(shí)段的簽名以及私鑰時(shí)，攻擊者無(wú)法偽造j時(shí)段之前的簽名。所以本簽名方案具有真正意義上的前向安全性。

4.3 抗偽造性

PK作為簽名算法的公鑰，如果攻擊者想通過(guò)公鑰PK中的參數(shù)Q來(lái)獲取私鑰SKj，那么他將面臨橢圓曲線的離散對(duì)數(shù)問(wèn)題。因此攻擊者是無(wú)法通過(guò)公鑰來(lái)獲取簽名者的私鑰SKj。簽名s作為簽名在j時(shí)段的簽名重要組成部分，由s=SKjekmodn可知，如果攻擊者想通過(guò)s得到實(shí)際簽名私鑰SKj就必須知道k的值。而如果想要求解k就要面臨橢圓曲線離散對(duì)數(shù)的求解問(wèn)題，因此攻擊者無(wú)法通過(guò)s獲得簽名私鑰SKj。由前面的驗(yàn)證算法可知，如果攻擊者在不知道私鑰SKj和k的情況下，想用一個(gè)偽造的私鑰進(jìn)行簽名，則驗(yàn)證無(wú)法通過(guò)，具體證明過(guò)程如下。

假設(shè)攻擊者偽造j時(shí)段的私鑰′，隨機(jī)選取隨機(jī)數(shù)計(jì)算 s′=SKj′ek′mod n，k′2T+1-jP=(x′,y′) 和 r′=x′mod n，進(jìn)而偽造 j時(shí)段的簽名記為(j,ξ′)，其中 ξ′=(r′,s′)，但是在驗(yàn)證過(guò)程中，由于：

因此，驗(yàn)證無(wú)法通過(guò)，本方案具有較強(qiáng)的抗偽造性。

5 方案性能

通過(guò)對(duì)基于橢圓曲線的前向安全數(shù)字簽名方案的4個(gè)算法的描述能夠發(fā)現(xiàn)：在密鑰進(jìn)化算法中采用的是二次剩余運(yùn)算；在簽名算法中只進(jìn)行了一次點(diǎn)乘運(yùn)算和零次模逆運(yùn)算；在驗(yàn)證算法中只進(jìn)行了一次點(diǎn)乘運(yùn)算和一次模逆運(yùn)算。在基于橢圓曲線的數(shù)字簽名算法中最耗費(fèi)時(shí)間的就是點(diǎn)乘運(yùn)算和模逆運(yùn)算，因此，本方案的簽名與驗(yàn)證速度是非?？焖俚?，計(jì)算效率也是相當(dāng)可觀的。

6 結(jié)束語(yǔ)

橢圓曲線密碼已成為當(dāng)前的主流密碼算法，在人們的日常生活中發(fā)揮著越來(lái)越大的作用。本文基于橢圓曲線的離散對(duì)數(shù)問(wèn)題構(gòu)造了一種基于橢圓曲線的高效前向安全數(shù)字簽名方案，并有力地保證了新簽名方案的正確性和安全性，在電子商務(wù)或電子政務(wù)等領(lǐng)域中，具有廣泛的應(yīng)用前景。

1 Bellare M,Rogaway P.The exact security of digital signatures:how to sign with RSA and Rabin.Proceedings of Cryptology-Eucocrypt 1996 Lecture Notes in Computer Science(LNCS),Cambridge,UK,1996:399～416

2 Guillou L,Quisquater J.A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory.Proceedings of Cryptology-Eurocrypt 1988 Lecture Notes in Computer Science(LNCS),Davos,Switzerland,1988

3 Micali S.Asecure and Efficient Digital Signature Algorithm.Technical Report,MIT/LCS/TM-501,1994

4 Anderson R.Two remarks on public-key cryptology.Proceedings of the 4th Annual Computer and Communications Security(ACM),Zurich,Switzerland,1997

5 Bellare M,MinerS K.A forward-secure digitalsignature scheme.Proceedings of the 19th Annual International Cryptology Conference,Santa Barbara,CAL,USA,1999:431～448

6 Fiat A,Shamir A.How to prove yourself:practical solutions to identification and signature problems. Proceedings of Cryptology-Crypto’86,Santa Barbara,CAL,USA,1986:186～194

7 隋愛(ài)芬，楊義先，鈕心忻等.基于橢圓曲線密碼的可認(rèn)證密鑰協(xié)商協(xié)議的研究.北京郵電大學(xué)學(xué)報(bào)，2004,27(3):28～32

Sui A F,Yang Y X,Niu X X,et al.Research on the authenticated key agreement protocol based on elliptic curve cryptography.JournalofBeijing University ofPosts and Telecommunications,2004,27(3):28～32

8 蔡滿春，楊義先，胡正明.基于橢圓曲線密碼機(jī)制的一種電子現(xiàn)金方案.北京郵電大學(xué)學(xué)報(bào)，2004,27(2):44～47

Cai M C,Yang Y X,Hu Z M.Electronic cash scheme based on elliptic curve cryptosystem.Journal of Beijing University of Posts and Telecommunications,2004,27(2):44～47

9 王尚平,候紅霞,李敏.基于橢圓曲線的前向安全數(shù)字簽名方案.計(jì)算機(jī)工程與應(yīng)用，2006(18):150～151

Wang S P,Hou H X,Li M.A forward-secure digital signature scheme based on elliptic curves.Computer Engineering and Applications,2006(18):150～151

10 Michel A,Leonid R.A new forward-secure digital signature scheme.Proceedings of Advances in Cryptology-Asiacrypt 2000,Kyoto,Japan,2000:116～129