基于橢圓曲線的有代理的多重簽名

摘 要：在研究有代理的多重簽名和橢圓曲線數字簽名的基礎上，提出了一種基于橢圓曲線的有代理的多重簽名方案。其安全性基于求橢圓曲線離散對數的困難，比起已有的方案更加安全、高效，并給出了兩種基于橢圓曲線的有代理的多重簽名方案，即廣播的有代理的多重簽名方案和有序的有代理的多重簽名方案；最后討論了其正確性和安全性。

關鍵詞：橢圓曲線； 代理簽名； 多重數字簽名； 有代理的多重簽名

中圖法分類號：TP309．08 文獻標識碼：A 文章編號：1001-3695(2006)10-0113-03

Multisignature with Some of Proxy Signer Based on Elliptic Curve

YU Chengzun， WANG Caifen， LIU Junlong， JIA Aiku

(College of Mathematics Information Science， Northwest Normal University， Lanzhou Gansu 730073， China)

Abstract:After studying existing multisignature with some of proxy signer， based on elliptic curve， broadcast multisignature with some of proxy signer and ordinal multisignature with some of proxy signer are proposed. Their security rely on the problem of discrete logarithm on elliptic curve， comparing with the existing schemes they are more secure and efficient. At the same time， validity and security of the schemes are discussed.

Key words:Elliptic Curve; Proxy Signature; Multisignature; Multisignature with Proxy Signer

代理簽名作為一種特殊的簽名機制，自1996年Mambo等人[1]提出這一概念后，由于其在許多領域中有著重要的應用而備受人們關注。2000年，伊麗江等人[2]提出了代理多重簽名方案，使代理簽名有了更加廣泛的應用。近年來，王英龍等人[3]提出一種新的簽名方案——有代理的多重簽名方案。在這個多重簽名方案中，允許部分或全部簽名人（原始簽名人）由于某種原因不能簽名時，將簽名委托給他人（代理簽名人）替自己行使簽名權，這樣，對一個消息的多重簽名就可以由一些簽名的代理人和其他的原始簽名人一起完成。顯然，普通的多重簽名和代理多重簽名是有代理的多重簽名的一種特殊形式。所以，有代理的多重簽名方案在實際中有著更加廣泛的應用。

基于橢圓曲線離散對數問題的密碼體制同基于有限域上的離散對數問題（DLP）的密碼系統相比，具有更高的安全性，還具有密鑰短小、運算速度快等優點，并且橢圓曲線系統的參數規模要小得多，GF（2160）上的橢圓曲線系統相當于1 024bits的RSA系統[4]。因此，本文基于橢圓曲線的離散對數問題，提出了一種有代理的多重簽名方案，此方案具有更好的安全性和更高的實用性。與其他簽名體制類似，本文所提出的方案滿足以下基本性質：基本的不可偽造性、有代理的多重簽名的不可偽造性、不可抵賴性、密鑰依賴性和可注銷性。

1 橢圓曲線數字簽名算法（ECDSA）

ECDSA（Elliptic Curve Digital Signature Algorithm）是目前IEEE P1363（Standard Specifications for Public Key Cryptography）的執行標準。

系統參數:GF(q)，E，G，n，h。其中GF(q)是有限域，q是有限域中元素的個數，E是GF(q)上的橢圓曲線，G是E上的一個有理點，稱為基點，G的階為n(n為素數)，h為一個Hash函數。

簽名過程：系統用戶A的私鑰為xA∈{1，2，…，n-1}，其公鑰yA=xAG。

（1）A：隨機選取一個整數k∈{1，2，…，n-1}，計算kG=(x，y)，令r=x mod n；

（2）A：計算s=k-1(h(m)+rxA)mod n；消息m的簽名為(s，r)。

驗證過程：驗證者V對消息m的簽名進行驗證。

（1）V：計算v=s-1r mod n，u=s-1h(m)mod n；

（2）V：計算(x，y)=uG+vyA，令r=x mod n。

判斷r=r是否成立，如果成立則接受簽名，否則拒絕。

2 基于橢圓曲線的廣播的有代理的多重簽名方案

消息發送者Ui，簽名者Ai，其代理人Bi，簽名收集者Uc和簽名驗證者Uv。Ui將消息m同時發送到Ai或是Ai的代理人Bi進行簽名，Ai或其代理人將簽名消息發送給簽名收集者Uc，Uc收到簽名消息后驗證簽名的有效性，如果有效，對簽名進行整理并產生多重簽名，然后將多重簽名發送到Uv進行驗證。Ui不參加數字簽名。

2．1 系統初始化

系統參數:GF(q)，E，G，n，h（定義同ECDSA）。

每一個簽名者Ai的私鑰為di∈{1，2，…，n-1}，其公鑰為ei=di G mod n。簽名者的代理簽名人Bi，對應的私鑰αi∈{1，2，…，n-1}，公鑰βi=αi G mod n。

2．2 代理委托過程

如果Ai需要代理，那么Ai與Bi做以下步驟：

（1）Ai：隨機選取ki∈{1，2，…，n-1}，計算Ki=ki G mod n，σi′=di+kiKi mod n；

（2）Ai→Bi∶（Ki，σi′）；

（3）Bi：驗證σi′G？=ei+KiKi mod n；如果成立，（Ki，σi′）就是一個有效的代理密鑰，否則他拒絕接受這個密鑰而要求Ai重新發送一個有效的代理密鑰，或者終止協議。

（4）Bi：計算自己的簽名密鑰σi=σi′+αiβi mod n。

2．3 簽名生成過程

設Ui（i=1，…，t）對消息m進行多重數字簽名時，假設其中w個用戶是委托其代理人進行的。進一步假設這些代理簽名人為這t個簽名人的前w個，即Ui的組成為（B1，…，Bw，Aw+1，…，At），其中0≤w≤t。

消息的發送者Ui將m發送給每個簽名者Ui，Ui進行如下操作：

(1)Ui：隨機選取ui∈{1，2，…，n-1}，計算Ri=uiG mod n=（xi，yi），ri=xi mod n；

(2)Ui：將Ri發送給其他簽名者；

(3)Ui：計算R=∑ti=1Ri mod n=(x，y)，取R=x mod n；如果Ui是代理簽名者，計算si=uih(m)+R σi mod n；否則計算si=uih(m)+R di mod n；

(4)Ui：將(m，(si，Ri))發送給簽名收集者Uc。

2．4 單用戶簽名驗證過程

Uc收到(m，(si，Ri))進行以下操作：

(1)Uc:計算R=∑ti=1Ri modn=(x，y)，取R=x mod n；

(2)Uc：計算Ri=(xi，yi)，取ri=xi mod n；

(3)Uc：驗證消息簽名(m，(si，Ri))的有效性，如果是代理簽名，Uc計算vi=ei+KiKi+βiβi mod n，否則vi=ei；然后計算Hi=h(m)-1(si G-R vi)mod n=(Xi，Yi)，如果Hi=0，拒絕，否則判斷ri？=Xi mod n，如果等式成立，簽名有效，繼續產生多重簽名，否則簽名無效，終止簽名。

引理1 如果簽名人Ui(i=1，2，…，t)以及簽名收集者Uc都遵守協議，則簽名收集者Uc將總接受Ui(i=1，2，…，t)的單用戶簽名。

證明：如果Ui是代理簽名人

vi=ei+KiKi+βiβi=(di+kiKi+αiβi)G=σi G mod n;

si=uih(m)+R σi

Hi=(Xi，Yi)=h(m)-1(siG-R vi)mod n=h(m)-1(uih(m)

G+R σiG-R σiG)=ui G mod n=(xi，yi)=Ri

如果Ui是原始簽名人

vi=ei=di G mod n; si=uih(m)+R di

Hi=(Xi，Yi)=h(m)-1(siG-R vi)mod n=h(m)-1(uih(m)

G+R di G-R di G)=ui G mod n=(xi，yi)=Ri

由于ri=xi mod n，所以有ri=Xi mod n成立，Ui(i=1，2，…，t)對消息的單用戶簽名將被簽名收集者Uc接受。

2．5 多重簽名產生過程

Uc：計算S=s1+s2+…+st=∑ti=1si mod n，(m，(R，S))即為消息的多重簽名；

Uc：將(m，(R，S))發送給簽名驗證者Uv。

2．6 多重簽名驗證過程

Uv：計算V=∑ti=1ei+∑wi=1(KiKi+βiβi)mod n；

H=h(m)-1(S×G-R×V）mod n=（X，Y）；

如果H=0，則拒絕這個簽名，否則，判斷R?=X mod n，如果成立則接受這個簽名。

定理1 如果簽名收集者Uc和簽名驗證者Uv都遵守協議，則簽名驗證者Uv總接受此多重簽名。

證明：V=(∑wi=1(di+kiKi+αiβi)+∑ti=w+1di)G=(∑wi=1σi+∑ti=w+1di)G

S=∑ti=1si=∑wi=1(uih(m)+R σi)+∑ti=w+1(uih(m)+R di)

H=(X，Y)=h(m)-1(S×G-R×V)=h(m)-1(∑wi=1(uih(m)+R σi)+∑ti=w+1(uih(m)+R di)-(∑wi=1σi+∑ti=w+1di)R)

G=∑ti=1uiG=∑ti=1Ri=R=(x，y)

由于R=x mod n，因此R=X mod n成立，簽名收集者Uc的多重簽名將被驗證者接受。

2．7 安全性分析

（1）基本的不可偽造性。在這個有代理的多重簽名方案中，Bi雖然得到了σi′和Ki，但他不能從中推斷出di。這是因為Ki=ki G mod n，從Ki中獲得ki相當于解橢圓曲線上的對數問題，同時σi′=di+kiKi mod n，不知道Ki也就不能獲得di。因而Bi不能偽造Ai的普通簽名，由此也說明了任何其他攻擊者也都難以偽造原始者Ai的簽名。

（2）有代理的多重簽名的不可偽造性。由于Bi知道ui和σi，所以只有Bi能生成代理簽名，甚至Ai也不能偽造該代理簽名。

（3）不可抵賴性。由于任何人都不能偽造原始者Ai的簽名，所以Ai不能否認他的一個有效的簽名。由于除了Bi外，任何人（包括Ai）都不能偽造Bi的代理簽名，所以Bi不能否認他的一個有效的代理簽名。

（4）密鑰依賴性。在這個簽名體制中，對簽名人是原始簽名者的情況，si是Ai的私鑰di的函數，即它依賴于di；對簽名人是代理簽名者的情況，si是Ai的私鑰di和Bi的私鑰αi的函數，即它依賴于di和αi。

（5）可注銷性。Ai如果想注銷Bi擁有的代理簽名密鑰σi，那么就可以向大家廣播一條消息，宣布Ki不再有效，從而Bi生成的代理簽名隨之失效。

3 基于橢圓曲線的有序的有代理的多重簽名方案

3．1 系統初始化

參數同上述基于廣播的有代理的多重簽名方案一致，消息發送者Ui預先設計一種簽名順序（U1，U2，…，Ut），并將這種簽名順序發送給每一位簽名者Ui和簽名驗證者Uv。

3．2 委托過程

與上述基于廣播的有代理的多重簽名方案的委托過程相同。

3．3 簽名的產生過程

Ui將消息m發送給第一位簽名人U1，設s0=0。U1，U2，…，Ut按照消息發送者Ui預先設計的簽名順序（U1，U2，…，Ut）依次簽名。那么，當Ui收到（m，（si-1，ri-1）和Rj(j=1，2，…，i-1)之后，首先要對前i-1個簽名人進行驗證：

（1）Ui：如果前面的簽名人Uj(j=1，2，…，i-1)是代理簽名人，則令vj=ej+KjKj+βjβj mod n;

若是前面的簽名人Uj(j=1，2，…，i-1)是原始簽名人，則令vj=ej mod n。

（2）Ui：計算R=∑i-1j=1Rj mod n=(x，y)，取R=x mod n；

計算Hi=h(m)-1(si-1G-∑i-1j=1rjvj)=(Xi，Yj)，如果Hi=0，認為簽名無效，否則繼續驗證。驗證R？=Xi mod n，如果等式成立，Ui認為前i-1簽名人對消息m的簽名有效，Ui繼續簽名；否則認為簽名無效，拒絕繼續對消息簽名。

（3）Ui：隨機選取ui∈{1，2，…，n-1}，計算Ri=uiG mod

n=（xi，yi），ri=xi mod n。

（4）Ui：如果Ui是代理簽名者，他計算si=si-1+uih(m)+riσi mod n；

否則若Ui是原始簽名者，Ui計算si=si-1+uih(m)+

ridi mod n。

（5）Ui：將(m，(si，Ri))送給下一個簽名人，將Ri分別發送到以后的簽名者及簽名驗證者。

引理2 如果U1，U2，…，Ui-1以及Ui都遵守協議，則Ui將接受前i-1個簽名人的多重簽名，并繼續對消息進行簽名。

證明：如果Uj(j=1，2，…，i-1)是代理簽名人

vj=ej+KjKj+βjβj mod n=(dj+kjKj+αjβj)G=σj G mod n

siG=(si-1+uih(m)+riσi)G=∑ij=1(ujh(m)G+rjvj)mod n;

如果Uj(j=1，2，…，i-1)是原始簽名人

vj=ej=dj G mod n;si G=(si-1+uih(m)+ridi)G=∑ij=1(ujh(m)

G+rjvj);

于是，對任意的Uj(j=1，2，…，i-1)有

Hi=(Xi，Yi)=h(m)-1(si-1G-∑i-1j=1rjvj)=h(m)-1∑i-1j=1(ujh(m)G+rjvj-rjvj)=∑i-1j=1ujG=∑i-1j=1Rj=R=(x，y);

因為有R=x mod n，所以R=Xi mod n成立，前i-1個簽名人的多重簽名將被簽名者Ui接受。

3．4 簽名驗證過程

第i個簽名者Ui要對前i-1個簽名人進行驗證，Uv要對所有的簽名者的簽名進行驗證。那么，驗證者進行如下的操作。

（1）Uv：如果前面的簽名人Ui(i=1，2，…，t)是代理簽名人，則令vi=ei+KiKi+βiβi mod n;

若前面的簽名人Ui(i=1，2，…，t)是原始簽名人，則令

vi=ei mod n。

（2）Uv：計算R=∑ti=1Ri mod n=(x，y)，取R=x mod n；

計算H=h(m)-1(siG-∑ti=1rivi)mod n=(X，Y)，若H=0，認為簽名無效，否則繼續驗證。驗證R？=X mod n，如果等式成立，Uv認為對消息m的多重簽名有效；否則認為簽名無效。

定理2 如果U1，U2，…，Ut以及簽名驗證者Uv都遵守協議，則Uv將接受這個多重簽名。

證明：同引理2證明相似，不論Ui(i=1，2，…，t)是原始簽名人，還是代理簽名人，一定有下式成立：H=(X，Y)=h(m)-1(siG-∑ti=1rivi)mod n=∑ti=1Ui G=∑ti=1Ri=R=(x，y)。

由于R=x mod n，因此有R=X mod n成立，此多重簽名將被簽名驗證者Uv接受，即這個有序的有代理的多重簽名方案是正確的。

3．5 安全性分析

該方案的安全性分析與廣播的有代理的多重簽名方案類似，這里不再重復分析。

4 結束語

本文將橢圓曲線簽名體制應用于有代理的多重簽名之中，提出了基于橢圓曲線的有代理的多重簽名方案。此方案不僅具有橢圓曲線簽名體制密鑰短小、運算速度快的特點，更滿足了有代理的多重簽名的安全需求，從而使有代理的多重簽名方案具有更強的抗攻擊性和更高的實用性。

參考文獻：

[1]Mambo M， et al. Proxy Signature for Delegating Signing Operation[C]. Proc.of the 3rd ACM Conference on Computer and Computer and Communications Security， New York: ACM Press， 1996.48-57.

[2]Yi Lijiang， et al. Proxy Multisignature Scheme:A New Type of Proxy Signature Scheme[J]. Electronic Letters， 2000，36(6):527-528.

[3]王英龍，王連海.一種新的簽名——有代理的多重簽名研究[J]. 計算機工程與應用，2005，41(10):77-79.

[4]Koblitz N. Elliptic Curve Cryptosystems[J]. Mathematics of Computation， 1987，48:203-209.

[5]王連海，徐秋亮.基于橢圓曲線密碼體制的代理簽名方案研究[J].計算機應用研究，2004，21(4):122123.

[6]Li Jiguo， Cao Zhenfu， Zhang Yichen， et al. Cryptographic Analysis and Modification of Proxy Multisignature Scheme[J]. High Technology Communication， 2003，13(4):1-5.

作者簡介：

于成尊（1982-），男，河南南陽人，碩士研究生，主要研究方向為信息安全、網絡安全；王彩芬（1963-），女，教授，博士，主要研究方向為信息安全、電子商務中協議的安全以及協議的形式化分析；劉軍龍（1981-），男，甘肅平涼人，碩士研究生，主要研究方向為信息安全、網絡安全；賈愛庫（1970-），男，甘肅慶陽人，碩士研究生，主要研究方向為信息安全、網絡安全。

注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文