一種改進(jìn)的橢圓曲線安全代理簽名方案

摘 要:為解決基于橢圓曲線的代理簽名方案的安全問題，提出一種改進(jìn)的抗偽造攻擊的代理簽名方案。該方案通過改進(jìn)代理簽名私鑰生成方式和相應(yīng)的代理簽名驗證等式的方法，提高了基于橢圓曲線的代理簽名方案的安全性。分析表明，新方案解決了以往方案中存在的原始簽名者偽造問題，滿足強(qiáng)代理簽名方案所必須的六種性質(zhì)，具有無須安全通道的優(yōu)點并且更為高效。分析結(jié)果說明，新方案比以往方案具有更好的安全性和更高的實用性。

關(guān)鍵詞:代理簽名; 橢圓曲線; 橢圓曲線離散對數(shù)問題

中圖分類號:TP309

文獻(xiàn)標(biāo)志碼:A

文章編號:1001-3695(2010)02-0685-04

doi:10.3969/j.issn.1001-3695.2010.02.078

Improved secure proxy signature scheme based on elliptic curve

HU Lan-lana，b，c， ZHENG Kang-fenga，b，c， LI Jiana，b， HU Zheng-minga，b，c， YANG Yi-xiana，b，c

(a.Information Security Center， State Key Laboratory of Networking Switching Technology， b.Key Laboratory of Network Information Attack Defence Technology of MOE， c.National Engineering Laboratory for Disaster Backup Recovery， Beijing University of Posts Telecommunications， Beijing 100876， China)

Abstract:To overcome the secure weakness of the existing proxy signature scheme based on elliptic curve， this paper presented an improved proxy signature scheme that could avoid forgery attack. Enhanced the security of the proxy signature scheme based on elliptic curve by improving on the generate form of the private key and the corresponding verification equation of proxy signature. The analysis showed that the new scheme resolved secure problems in the former schemes， met the six aspects of security features needed by strong proxy signature scheme， did not need the support of the secure channel， and was more efficient. The analytic results prove that the new scheme is more secure and practicable.

Key words:proxy signature; elliptic curve; elliptic curve discrete logarithm problem (ECDLP)

0 引言

1996年Mambo等人[1]提出了代理簽名的概念并給出了一種代理數(shù)字簽名方案，此后基于離散對數(shù)和素因子分解的代理數(shù)字簽名方案[2，3]紛紛涌現(xiàn)。代理簽名是指原始簽名者將其簽名權(quán)(部分)授予代理者，代理者可以代表原始簽名者來行使他的簽名權(quán)。通過對以往代理簽名研究的歸納總結(jié)，可以認(rèn)為，一個可被實際應(yīng)用的典型代理簽名方案應(yīng)是具備以下特性的強(qiáng)代理簽名方案[4，5]:

a)可驗證性。對于有效的代理簽名，驗證者能夠確信這個簽名是原始簽名者認(rèn)可的數(shù)字簽名，即不但能驗證代理簽名者生成的代理簽名，也能驗證原始簽名者的授權(quán)。

b)強(qiáng)可區(qū)分性。由代理簽名者所簽署的代理簽名與原始簽名者所產(chǎn)生的簽名是有區(qū)別的，不同的代理簽名者生成的代理簽名之間也有明顯區(qū)別。

c)強(qiáng)不可偽造性。除代理簽名者外，任何人(包括原始簽名者)都不能生成有效的代理簽名。

d)強(qiáng)可鑒別性。對于有效的代理簽名，原始簽名者和任何驗證者都能夠確定代理簽名者的身份。

e)強(qiáng)不可否認(rèn)性。代理簽名者一旦生成一個有效的代理簽名，事后不能否定對這個代理簽名的建立。

f)可控性或阻止濫用。原始簽名者能夠有效控制代理簽名者的代理權(quán)限，包括代理者的身份、代理有效時間、代理簽署消息范圍等。代理簽名密鑰不能用于其他目的。

1 基于橢圓曲線代理簽名方案的優(yōu)越性及相關(guān)研究

Koblitz等人在1985 年將橢圓曲線群引入公鑰密碼理論中，提出了基于橢圓曲線的公鑰密碼體制ECC(elliptic curves cryptosystem)，橢圓曲線公鑰密碼的安全性主要是建立在基于橢圓曲線離散對數(shù)問題(ECDLP)求解的困難性[6，7]。從目前的研究結(jié)果看，橢圓曲線上的離散對數(shù)問題比有限域上的離散對數(shù)問題更加難以處理，具有更高的安全性，還具有密鑰短小、運(yùn)算速度快等優(yōu)點，GF(2160)上的橢圓曲線系統(tǒng)就可以達(dá)到1 024 bit的RSA系統(tǒng)同樣的安全性[8]。因此，基于ECDLP的代理簽名方案比基于有限域上離散對數(shù)問題的相應(yīng)方案具有優(yōu)越性。

在對基于橢圓曲線的代理簽名的研究中，文獻(xiàn)[9， 10]給出了兩種典型的基于橢圓曲線離散對數(shù)問題的代理簽名方案。但文獻(xiàn)[11]指出這兩種方案都存在著原始簽名人的偽造攻擊，即原始簽名人能夠偽造代理簽名。文獻(xiàn)[12]在改進(jìn)橢圓曲線數(shù)字簽名算法的基礎(chǔ)上提出了一種新的橢圓曲線代理簽名方案。文獻(xiàn)[13]指出該方案同樣存在著上述偽造問題。2007年，左為平等人[14]指出以上方案還存在著另外一種原始人偽造攻擊，即原始簽名者可以成功地把一個代理簽名偽造成代理簽名者自己的普通簽名。為了抵御原始簽名者對代理簽名進(jìn)行偽造攻擊，左為平等人提出了一種新的基于橢圓曲線的安全代理簽名方案(以下簡稱ZL方案)。但經(jīng)筆者進(jìn)一步分析發(fā)現(xiàn)，ZL方案依然存在著原始簽名人的偽造攻擊。為此，本文借鑒文獻(xiàn)[15]中代理簽名私鑰構(gòu)造方法，在ZL方案基礎(chǔ)上提出了一個新方案。新方案能有效抵御偽造攻擊，保護(hù)代理簽名者的合法利益。與已有方案相比，新方案更安全、更實用。

2 Z L方案及其不足

ZL方案包括系統(tǒng)初始化、簽名委托、簽名產(chǎn)生和簽名驗證過程四個階段。方案的協(xié)議方為原始簽名者、代理簽名者和簽名驗證者。

2.1 初始化

GF(q):定義的有限域;

q:有限域的元素個數(shù)，其中q=p(p是一大素數(shù))或q=2m;

E:定義在有限域 GF(q) 上的安全橢圓曲線;

P:E上的一個階為素數(shù)n的公開基點，其中P∈E(GF(q));

n:素數(shù)，是P的階，n>2160且n>4q1/2;

h:{0，1}→{0，1}160是美國NIST和NSA設(shè)計的一種安全hash函數(shù);

(xA，YA):原始簽名者 A 的私鑰公鑰對，其中，YA = xAP，xA保密，YA 公開;

(xB，YB):代理簽名者 B 的私鑰公鑰對，其中，YB=xBP，xB保密，YB公開;

mw:授權(quán)證書，主要包含原始簽名者 A 和代理簽名者 B的身份以及授權(quán)范圍和期限等信息。

2.2 代理簽名委托

1)原始簽名者 A 隨機(jī)選取一個整數(shù)kA∈[1，n-1]，計算G=kAP=(xG，yG)，rA=xG mod n，e1=h(mw，rA)，sA=xAe1+kA mod n，然后將(mw，G，sA)秘密地發(fā)送給代理簽名者B。這里(G，sA)實質(zhì)上是A對mw的簽名值。

2)代理簽名者 B 驗證授權(quán)簽名的合法性

B收到(mw， G， sA)后，首先檢查授權(quán)證書mw，之后計算:rA=xG mod n，e1=h(mw，rA)，然后驗證等式sAP=YAe1+G是否成立，若成立則說明授權(quán)合法。

2.3 代理簽名生成

對某個消息 m，B代表A生成代理簽名的過程如下:

B首先計算代理簽名之私鑰x=sA+xBYB mod n，然后隨機(jī)選取一個整數(shù)kB∈[1，n-1]，計算Q=kBP=(xQ，yQ)，r=xQ mod n，e2=h(m，r)，s=xe2+kB mod n，則將(m， mw，G，Q，s)作為代理簽名，并將(m，mw，G，Q，s)發(fā)送給簽名驗證者。

2.4 代理簽名驗證

驗證者收到代理簽名(m，mw，G，Q，s)后，利用原始簽名者 A 和代理簽名者 B 的公鑰驗證代理簽名的過程如下:

計算rA=xG mod n，r=xQ mod n，e1=h(mw，rA)，e2=h(m，r)，然后驗證等式sP=Q+e2(G+YBYB +e1YA)是否成立，如果等式成立則認(rèn)為B代理A所做的代理簽名有效，否則無效。

2.5 Z L方案安全性分析

證明ZL方案存在原始簽名人的偽造攻擊如下:

a)原始簽名者 A 隨機(jī)選取一個整數(shù)kA∈[1，n-1]，計算G=kAP-YBYB=(xG， yG)，rA=xG mod n，e1=h(mw，rA)，sA=xAe1+kA mod n。

b)對某個消息m，A隨機(jī)選取一個整數(shù)kB∈[1，n-1]，計算Q=kBP=(xQ，yQ)，r=xQ mod n，e2=h(m，r)，s=sAe2+kB mod n，則將(m，mw，G，Q，s)作為代理簽名，并將(m，mw，G，Q，s)發(fā)送給簽名驗證者。

c)驗證者計算rA=xG mod n，r=xQ mod n，e1=h(mw，rA)，e2=h(m，r)，然后驗證等式sP=Q+e2(G+YBYB+e1YA)是否成立，若等式成立則認(rèn)為(m，mw，G，Q，s)是B代理A所做的有效代理簽名。以下證明上述等式成立:

Q+e2(G+YBYB+e1YA) =Q+e2(kAP-YBYB+YBYB+e1YA)=

Q+e2(kAP+e1xAP)=Q+e2(kA+e1xA) P=kBP+e2sAP=(kB+e2sA)P=sP

由以上分析可見，原始簽名者 A 偽造的代理簽名(m，mw，G，Q，s)能通過簽名驗證者的驗證，被認(rèn)為是B代理A所做的有效代理簽名，從而證明了ZL方案存在原始簽名人的偽造攻擊。

3 新的安全代理簽名方案

系統(tǒng)初始化過程、簽名委托過程同ZL方案，參見2.1、2.2節(jié)。以下僅敘述與ZL方案不同的簽名產(chǎn)生過程和簽名驗證過程。

3.1 代理簽名生成

對某個消息 m，B 代表 A 生成代理簽名的過程如下:

B首先計算代理簽名之私鑰x=sAxB-1 mod n，然后隨機(jī)選取一個整數(shù)kB∈[1，n-1]，計算Q=kBYB=(xQ，yQ)，r=xQ mod n，e2=h(m，r)，s=xe2+kB mod n，則將(m，mw，G，Q，s)作為代理簽名，并將(m，mw，G，Q，s)發(fā)送給簽名驗證者。

3.2 代理簽名驗證

驗證者收到代理簽名(m，mw，G，Q，s)后，首先檢查授權(quán)證書mw，之后利用原始簽名者A和代理簽名者B的公鑰驗證代理簽名的過程如下:

計算rA=xG mod n，r=xQ mod n，e1=h(mw，rA)，e2=h(m， r)，然后驗證等式 sYB=Q+e2(G+e1YA)是否成立，如果等式成立則認(rèn)為B代理A所做的代理簽名有效，否則無效。

等式的正確性證明如下:

已知s=xe2+kB mod n，x=sA xB-1 mod n，Q=kBYB，sA=xAe1+kA mod n，則

sYB=(xe2+kB)YB=(sA xB-1e2+kB)YB= sA xB-1e2YB+kBYB=

e2sA xB-1 xBP+Q=e2(xAe1+kA)P+Q=e2(e1xAP+kAP)+Q=

e2(e1YA+G)+Q=Q+e2(G+e1YA)

由此可知等式sYB=Q+e2(G+e1YA)成立。

4 新方案分析

4.1 安全分析

4.1.1 可驗證性

根據(jù)代理簽名(m，mw，G，Q，s)，驗證者利用原始簽名者A和代理簽名者B的公鑰驗證等式 sYB=Q+e2(G+e1YA)是否成立，若等式成立則能夠確信該簽名是B代理A所生成的有效代理簽名。由授權(quán)證書mw及代理簽名等式驗證過程中內(nèi)含的對授權(quán)證書簽名值(G，sA)的檢查(內(nèi)含驗證等式 sA P=YAe1+G是否成立)，驗證者能夠確信這個簽名是原始簽名者授權(quán)認(rèn)可的代理簽名。

4.1.2 強(qiáng)可區(qū)分性

代理簽名(m，mw，G，Q，s)中包含授權(quán)證書mw，在形式上明顯不同于普通簽名，因而與原始簽名者所產(chǎn)生的簽名可以很容易區(qū)分開。如果有多個代理人或者對同一代理人進(jìn)行了多次不同的授權(quán)，則因為在每次代理簽名委托過程中kA是隨機(jī)選擇的，所以每次的代理授權(quán)參數(shù)G不同，再加上授權(quán)證書mw中的授權(quán)信息的不同，從而可以很容易地將不同代理人的代理簽名和同一代理人根據(jù)不同授權(quán)進(jìn)行的代理簽名逐一區(qū)分開。

4.1.3 強(qiáng)不可偽造性

代理私鑰x=sA xB-1 mod n 中包含代理簽名者 B的私鑰xB，其他任何人(包括原始簽名者)由于不知道xB都不能假冒代理簽名者B生成這個代理簽名;又其中授權(quán)參數(shù)sA=xAe1+kA mod n 中又包含原始簽名者A的私鑰xA，只有A授權(quán)的代理簽名者B才能生成有效的代理簽名。以下分析新方案對常見的幾種偽造攻擊的可抵抗性:

a)原始簽名者普通簽名的不可偽造性。在代理簽名方案中，代理簽名者B無法從代理委托請求(mw，G，sA)中求出原始簽名者A的私鑰xA 。這是因為，G=kAP=(xG，yG)，rA=xG mod n，e1=h(mw，rA)，sA=xAe1+kA mod n。其中包含xA的等式中sA的值已知，e1的值可計算得出，若想計算出xA需要知道kA的值，而在等式G=kAP中試圖根據(jù)G計算出kA時將面臨求解橢圓曲線離散對數(shù)問題。因此B不可能利用代理簽名方案中的信息偽造A的普通數(shù)字簽名。進(jìn)而可知其他攻擊者也都難以偽造A的普通數(shù)字簽名。

b)代理簽名者普通簽名的不可偽造性。新方案中代理簽名私鑰x=sA xB-1 mod n，對于原始簽名者A而言，在不知道隨機(jī)數(shù)kB的情況下，已知s=xe2+kB mod n=sA xB-1e2+kB mod n，用ZL方案指出的攻擊方法計算s′=s-sAe2=sA xB-1e2+kB-sAe2 mod n，s′顯然不等于Schnorr簽名算法體制下代理簽名者 B 的普通簽名sB=xBe2+kB mod n。因此，新方案中不存在ZL方案中指出的原始簽名者可利用代理簽名偽造代理簽名者普通簽名的安全缺陷。

c)代理簽名的不可偽造性。新方案中代理簽名驗證等式為sYB=Q+e2(G+e1YA) ，偽造代理簽名等價于求(s，Q，G，e1，e2)使得上述等式成立。由于哈希函數(shù)的單向性，攻擊者必須先確定哈希函數(shù)所有參數(shù)(mw，rA，m，r)的值。其中rA=xG mod n，r =xQ mod n，xG、xQ分別為點Q，G的橫坐標(biāo)，從而必須先確定(Q，G)的值。又由于驗證等式中的YB不像ZL方案那樣和G或Q處于相同的構(gòu)成項位置，因而無法通過構(gòu)造G或Q的值消去。一旦(mw，m，Q，G)的值確定了，則e1，e2的值就確定了，從而驗證等式sYB=Q+e2(G+e1YA)等號右邊的值就確定了，求解s將面臨求解橢圓曲線離散對數(shù)問題。其他任何人(即使是原始簽名者)也不能偽造代理簽名。

4.1.4 強(qiáng)可鑒別性

對于有效的代理簽名(m，mw，G，Q，s)，授權(quán)證書mw中包含代理簽名者的身份信息，代理簽名驗證時要用到代理簽名者B的公鑰YB ，原始簽名者和任何驗證者在驗證代理簽名時都能夠確定代理簽名者的身份，因此方案具有強(qiáng)可鑒別性。

4.1.5 強(qiáng)不可否認(rèn)性

從上面強(qiáng)不可偽造性可知，只有經(jīng)授權(quán)的代理簽名者才能生成這個代理簽名，代理簽名者一旦生成一個有效代理簽名，事后不能否定對這個代理簽名的建立，因此方案具有強(qiáng)不可否認(rèn)性。

4.1.6 可控性或阻止濫用

原始簽名者能夠通過授權(quán)證書mw 有效控制代理簽名者的代理權(quán)限，包括代理者的身份、代理有效時間、代理簽署消息范圍等。因mw受安全hash函數(shù)的保護(hù)，最終的代理簽名驗證等式中要用到e1=h(mw，rA)，對mw的竄改會導(dǎo)致代理簽名不能通過驗證從而使其無效。因此，代理簽名者B只能在規(guī)定的授權(quán)范圍和期限內(nèi)代表原始簽名者A進(jìn)行簽名，且即使B將代理權(quán)限轉(zhuǎn)交給第三方C，C也不可能代表原始簽名者A進(jìn)行簽名。所以代理簽名密鑰不能用于其他目的，方案具有較好的可控性。

4.1.7 無須安全信道

方案中代理授權(quán)為(mw，G，sA)，其中(G，sA) 實質(zhì)上是原始簽名者A對授權(quán)證書mw的簽名值，mw中明確了A 、B的身份及代理關(guān)系，sA是由原始簽名者的私鑰xA和mw決定的。由于代理私鑰x=sA xB-1 mod n。其中包含了由A的私鑰來保證不可竄改的授權(quán)參數(shù)sA ，由哈希值e1 來保證不可竄改的授權(quán)證書mw ，以及B的私鑰xB ，竊聽者D即使截獲了代理授權(quán)值，也無法冒充代理簽名者B生成代表A的代理簽名，也無法將代理簽名者改為自己生成代表A的代理簽名。因而方案不需要安全傳輸信道的支持。

4.2 效率分析

由于新方案系統(tǒng)初始化過程、簽名委托過程同ZL方案，僅需比較與ZL方案不同的簽名產(chǎn)生過程和簽名驗證過程的效率。

本文所描述方案的簽名產(chǎn)生過程由兩部分組成:一是代理簽名私鑰的生成，二是用代理簽名私鑰進(jìn)行簽名。新方案與ZL方案在用代理簽名私鑰進(jìn)行簽名方面的運(yùn)算過程類似，計算量的差異存在于代理簽名私鑰生成過程。ZL方案代理簽名私鑰生成需一次橢圓曲線乘法和一次模加運(yùn)算，新方案需一次模逆和一次模乘運(yùn)算。其中最費(fèi)時的是橢圓曲線乘法，其他運(yùn)算與橢圓曲線乘法運(yùn)算相比幾乎可忽略不計。因而新方案更為高效。

簽名驗證過程中，ZL方案需兩次哈希、四次橢圓曲線乘法和三次橢圓曲線加法運(yùn)算;新方案需兩次哈希、三次橢圓曲線乘法和兩次橢圓曲線加法運(yùn)算。顯然，新方案的效率要高于ZL方案。

5 結(jié)束語

本文首先介紹了文獻(xiàn)[14]提出的基于橢圓曲線的代理簽名方案并構(gòu)造了針對該方案的原始簽名人偽造攻擊;然后提出新的方案，并驗證了新的安全代理簽名方案避免了以往方案所存在的安全問題，滿足引言中所列出的典型代理簽名方案應(yīng)具備的六個方面的安全特性。新方案具有橢圓曲線密碼體制安全性高、密鑰短小、運(yùn)算速度快等優(yōu)點，具備強(qiáng)代理簽名方案所應(yīng)有的性質(zhì)，且無須安全信道，具有更強(qiáng)的抗攻擊性和更高的實用價值。

參考文獻(xiàn):

[1]MAMBO M， USUDA K， OKAMOTO E. Proxy signature: delegation of the power to sign messages[J]. IEICE Trans on Fundamentals of Electronics Communications and Computer Sciences，1996， E79A(9):1338-1354.

[2]祁明， HARN L. 基于離散對數(shù)的若干新型代理簽名方案[J]. 電子學(xué)報， 2000，28(11):114-115.

[3]SHAO Zu-hua. Proxy signature schemes based on factoring[J]. Information Processing Letters， 2003，85(3): 137-143.

[4]LEE B， KIM H， KIM K. Strong proxy signature and its applications[C]//Proc of Symposium on Cryptography and Information Security. Oiso， Japan :[s.n.]， 2001:603-608.

[5]楊偉強(qiáng)， 徐秋亮. 典型代理簽名方案的分析與改進(jìn)[J]. 計算機(jī)

工程與應(yīng)用， 2004，40(9): 152-154.

[6]KOBLITZ N. Elliptic curve cryptosystems[J]. Mathematics of Computation，1987，48(1): 203-209.

[7]MILLER V S. Use of elliptic curve in cryptography[C]//Proc of Advances in Cryptology-Crypto’85.New York: Springer-Verlag，1986:417-426.

[8]CAELLI W J， DAWSON E P， REA S A. PKI， elliptic curve cryptography， and digital signatures [J]. Computers and Security， 1999，18(1): 47-66.

[9]CHEN T S， LIU T P， HWANG G S， et al. An improvement of proxy-protected proxy multi-signature scheme[C]//Proc of the 13th International Conference on Information Management.2002:33-40.

[10]CHEN T S， CHUNG Y F， HWANG G S. Efficient proxy multi-signature schemes based on the elliptic curve cryptosystem[J]. Compu-ters Security，2003，22(6):527-534.

[11]曹天杰，林東岱，薛銳. 基于橢圓曲線的代理多簽名方案的安全性分析[J]. 小型微型計算機(jī)系統(tǒng)，2006，27(5):798-801.

[12]紀(jì)家慧，李大興.新的代理多簽名體制[J].計算機(jī)研究與發(fā)展， 2004，141(14):715-719.

[13]吳旭輝，沈慶浩.一種代理多簽名體制的安全性分析[J].通信學(xué)報， 2005，26(7):119-122.

[14]左為平， 李海峰. 一種安全的橢圓曲線代理簽名方案[J]. 佳木斯大學(xué)學(xué)報:自然科學(xué)版， 2007，25(4): 495-497.

[15]CHANG M H， CHEN I T， CHEN M T. Design of proxy signature in ECDSA[C]//Proc of the 8th International Conference on Intelligent Systems Design and Applications. Kaohsiung City， Taiwan:[s.n.]， 2008: 17-22.