基于一種改進橢圓曲線簽名算法的可驗證門限簽名方案

摘要：在一種改進的橢圓曲線數字簽名算法的基礎上，采用Pedersen可驗證門限秘密共享技術，構造了一個基于橢圓曲線的(t，n)可驗證門限數字簽名方案，并分析了它的安全性。該方案穩定性好，并具有魯棒性和抗選擇明文攻擊特性。

關鍵詞：橢圓曲線；門限數字簽名；可驗證

中圖分類號：TP309文獻標識碼：A 文章編號：1009-3044(2008)25-1532-02

A Verifiable Threshold Signature Scheme Based on an Improved Elliptic Curve Digital Signature Algorithm

PENG Qing-jun， LI Xin-ping

(Department of Mathematics， Hunan Institute of Science Technology， Yueyang 414006， China)

Abstract: Using Pedersen verifiable threshold secret sharing technique， a (t，n) verifiable threshold signature scheme is constructed based on an improved ECSDAin this paper. The scheme is stable， robust and able to resisting chosen-plaintext attack. The security analysis of this scheme is proposed.

Key words: elliptic curve; threshold digital signature; verifiable

1 引言

數字簽名[1]是現代密碼學和計算機安全的主要研究領域，它主要解決電子文件的簽字蓋章問題，用于識別電子文件簽署者的身份，保證文件的完整性、真實性、可靠性和不可抵賴性。Shamir[2]和Blakley[3]在1979年分別提出了基于Lagrange(t，n)門限秘密共享體制，它一經提出便受到人們的廣泛關注，成為信息安全和數據保密的重要手段，在數字簽名領域得到廣泛應用。Desmedt和Frankel[4]于1990年將數字簽名和秘密共享方案相結合提出門限簽名的概念。

橢圓曲線密碼體制（ECC）被技術界公認為能比RSA等其他公鑰加密系統提供更好的加密強度、更快的執行速度和更小的密鑰長度[5]。因此，基于ECC的門限簽名機制及其應用的研究現已成為信息安全領域的研究熱點。

不少門限簽名方案都采用Shamir門限秘密共享方案[2]進行秘密共享。但Shamir門限秘密共享方案具有兩大缺點：一是不能抵制分享者欺騙，惡意的分享者在秘密的恢復階段可能會給其他合作者提供假的秘密份額，使得其他合作者無法恢復出正確的秘密；另一個是不能有效的防止分發者欺騙，分發者可能會給某些分享者分發假的秘密份額，使得這些分享者永遠都不能正確恢復被分享的秘密。由于可驗證的門限秘密共享方案在現實生活中更具有實用性，所以自提出以來，就隨之有許多重要成果出現。本文采用Pedersen在文獻[6]中提出的可驗證秘密共享方案，在一個改進的橢圓曲線簽名方案[7]的基礎上，構造了一個基于橢圓曲線的可驗證(t，n)門限簽名方案，并分析了其穩定性與安全性。

2 一種改進的橢圓曲線簽名算法

一般的基于ECC的數字簽名算法ECDSA需要計算有限域上的逆元，而求逆元的運算復雜而費時，且在方案中密鑰分割和合成都是很困難的，所以不能直接運用于門限簽名。從ECDSA及其各種變型簽名方案出發，文獻[7]給出了一個改進的方案：

設系統參數為(Fq，E，P，n，h)，Fq為有限域，E是Fq上的橢圓曲線，P為基點，其階為大素數n，(k， Pk=kP)為公、私密對，待簽名的消息為M。簽名算法：

(1)選取隨機整數t，1≤t≤n-1，計算tP=(x， y)，r=x mod n；

(2)計算e=H(M)，s=t+(er)k mod n；

(3)簽名消息為(M，r，s)。

驗證算法：

(1)計算e=H(M)，u=er mod n；

(2)計算sP-uPk=(x'， y')， r'=x' mod n；

(3)當且僅當r'=r，接受簽名。

上述改進的方案，其安全性與ECDSA方案是完全一樣的。該方案避免了有限域上的求逆運算，因此比ECDSA方案簡單，實現速度也略快，更可以方便的進行秘密分享，更適合用于群組簽名和門限簽名中。

3 基于橢圓曲線的可驗證門限簽名方案

方案分為兩部分：秘密共享過程和門限簽名過程。秘密分享過程采用有可信中心的Pedersen可驗證秘密共享方案[6]，門限簽名過程以上節給出的改進橢圓曲線簽名算法為基礎，并且有一名非簽名成員的簽名集成者DC，負責收集和驗證簽名成員的簽名，把消息和最終的簽名發送給接收者。下面分四個階段來描述：

3.1 系統初始化階段

該方案的安全參數如下：

(1)可信中心CA選取有限域Fq上一條安全的橢圓曲線E(Fq)，保證該橢圓曲線的離散對數問題是難解的。在E(Fq)上選一基點P，P的階數為p（p為一個大素數）。另外，CA還選擇一個單向Hash函數h()。

(2)令組G={U1， U2， … Un}是n個簽名者的集合，簽名者Ui的身份標識IDi是不等于零的正整數，且不同的簽名者Ui具有不同的身份標識IDi，即當i≠j時，IDi≠IDj。

(3)CA隨機選取dG∈Fq作為組G的私鑰，組G的公鑰為YG=dGP∈E(Fq)。CA公開參數Fq， E(Fq)， P， p， YG， h()。

3.2 秘密分享與驗證階段

(1)設門限為t，CA隨機產生t-1次多項式：

f(x)=a0+a1x+…+at-1xt-1∈Fq(x)分別計算組G中簽名者Ui∈G的私鑰與公鑰為：di=f(IDi)， Yi=diP。

(2)CA通過安全信道發送di(i=1， 2， L， n)給Ui∈G，并且公開Yi(i=1， 2， …， n)和Ai=aiP(i=1， 2， …， t-1)。

(3)每個Ui∈G接收到di后，可通過計算：

是否成立并且是橢圓曲線上的點來判斷CA分發的di是否為有效密鑰。如果成立，則接受CA，否則拒絕CA并公開di。

定理 如果等式：

成立，則簽名者Ui∈G得到的秘密影子是有效的。

證明：

3.3 門限簽名階段

假設組G={U1，U2，…，Un}中的t個簽名者，不妨設為U1，U2，…，Ut對消息M簽名并發送給接收者B。簽名步驟如下：

(1)首先簽名者Ui(i=1，2，…，t)隨機選取ki，1≤ki≤p-1，并計算Ki=kiP，然后Ui(i=1，2，L，t)發送Ki給簽名合成者DC(Designated Combiner)。

(2)DC通過驗證Ki≠Kj(i≠j)是否成立來檢查Ui，Uj在步驟(1)是否選擇了相同的隨機數。如果Ui，Uj選擇了相同的隨機數，則通知它們重新選取新的隨機數并計算Ki；否則DC計算：

(3)簽名者Ui(i=1，2，…，t)計算e=h(M)， si=ki+erdiCi mod p，其中插值系數：

最后，簽名者Ui(i=1，2，…，t)發送si給DC。

(4)DC接收到部分簽名消息si后，通過驗證如下等式：

siP-Ki=erCiYi

是否成立來驗證部分簽名消息的有效性。如果所有的部分簽名消息si都是有效的，則DC計算：

并且發送簽名信息(M，r，s)給接收者B。

3.4 簽名驗證階段

接收者B接收到簽名消息(M， r， s)后，首先計算e=h(M)，sP-erYG=(x1'，y1')，r'=x1' mod p，當且僅當r=r'，接收簽名。

不難看出，等式r=r'，是否成立取決于方程sP-erYG=K是否成立。

4 穩定性和安全性分析

在該方案中，當有新成員Ui需要加入時，CA只需要向新成員提供一個公開身份，并計算簽名者的私鑰發送給他即可，而系統和老成員的相關參數全都不用進行改動。當需要刪除成員時，只需要將其ID通知為無效的ID。因而具有較好的穩定性。

如果非群成員的攻擊者試圖從群公鑰YG=dGP那里得到群私鑰dG，則他需要解決的是ECDLP，這是行不通的。所以該方案在計算上是安全的。另外，方案通過方程siP-Ki=erCiYi 判斷部分簽名的有效性，可以發現簽名者是否更換分享到的密鑰來進行欺騙，當然，只要更換密鑰的簽名者不超過n-t個，就不會影響到整體簽名。所以該方案魯棒性好。

在抵抗選擇明文攻擊方面，從方程siP-Ki=erCiYi可以看出，si和待簽名消息e=h(M)之間是不存在線性關系的，因而攻擊者無法利用已知的對M的簽名si，來推導出M'的簽名si'。也就是說在di和ki未知的情況下，想找出si和e之間的關系是不可行的，同理，想找出s和e之間的關系也是行不通的。因而，攻擊者即使得到了部分簽名或者群簽名，也無法推斷出密鑰分量。

在防偽造方面，如果內部攻擊者是接收者或DC，試圖偽造對消息M'的簽名，雖然他可以選取t個隨機數ki'用來偽造Ti'，但由于不知道di，他仍然無法偽造si'=ki'+erdiCi mod p，因此偽造簽名也是行不通的。

5 結束語

本文在一種改進的橢圓曲線數字簽名算法的基礎上，采用Pedersen可驗證門限秘密共享技術，構造了一個基于橢圓曲線密碼體制的（t，n）可驗證門限數字簽名方案。由于采用了可驗證技術，文中給出的簽名方案使每個簽名參與者可以驗證他擁有的子秘密的正確性，從而克服了一般采用Shamir共享技術的門限簽名方案的不足。

參考文獻：

[1] Rivest R J，Shamir A L. Adleman a method for obtaining digital signature and public-key cryptosystem[J].Communications of the ACM，1978，21(2):120-126.

[2] Shamir A. How to share a secret[J]. Communications of the ACM，1979，22(11):612-613.

[3] Blakley G R. Safe guarding cryptographic keys[C]. In: Proc of the National Computer Conf， AFIPS Conf. proc， AFIPS Press，1979，313-317.

[4] Desmedt Y， Frankel Y. Threshold cryptosystems[C]. In:Brassard Ged Advances in Cryptology-CRYPTO'89 proceedings LectureNotes in Computer Science 435 Berlin: Springer Verlag，1990，307-315.

[5] 徐秋亮，李大興.橢圓曲線密碼體制[J].計算機研究與發展，1999，36(11):1281-1288.

[6] Pedersen T P. Distributed provers with applications to undeniable signatures[C]. In:Proc of Eurocrypt'91，LNCS 547. Berlin: Springer-Verlag，1991.221-238.

[7] 楊君輝，戴宗鐸，楊棟毅，等.一種橢圓曲線簽名方案與基于身份的簽名協議[J].軟件學報，2000，11(10):1303-1306.