一個門限代理簽名方案的進一步改進

摘 要：1999年，Sun等人提出了一個門限代理簽名方案，克服了Zhang和Kim等人分別提出的方案的缺點；近來，李繼國等人指出Sun的方案無法抵抗替換公鑰攻擊，并給出了一個改進方案；指出李繼國的方案依然無法抵抗替換公鑰攻擊，同時提出了代理關系轉換攻擊方法，成功地攻擊了他們的方案。該攻擊方法對設計安全的代理簽名有重要的價值。最后給出了門限代理簽名的進一步改進方案。

關鍵詞：數(shù)字簽名； 代理簽名； 門限代理簽名

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

Further Improvement of a Threshold Proxy Signature Scheme

XIE Qi1， YU Xiuyuan2，3

(1.School of Information Engineering， Hangzhou Teachers College， Hangzhou Zhejiang 310036， China; 2.School of Science， Hangzhou Teachers College， Hangzhou Zhejiang 310036， China; 3.Dept. of Mathematics Physics， Quzhou College， Quzhou Zhejiang 324000， China)

Abstract:In 1999， Sun， et al presented a threshold proxy signature， which overcame weaknesses of the schemes proposed by Zhang and Kim， et al， respectively. Recently， Li， et al showed that Sun’s scheme cann’t resist the public key substitution attack， and proposed an improved scheme. However， their improved scheme is still suffer from the public key substitution attack. Additional， a proxy relationship inversion attack on Li’s scheme is proposed， it will provides more information in the design of secure proxy signature scheme. Finally， a further improvement scheme is proposed to eliminate the weaknesses.

Key words:Digital Signature; Proxy Signature; Threshold Proxy Signature

1 引言

1996年，Mambo等人[1]首次提出了代理簽名的概念，一個代理簽名方案允許原始簽名人把自己的簽名權交給指定的代理人（稱為代理簽名人），代理簽名人能夠代表原始簽名人生成有效的代理簽名。由于代理簽名在信息化社會有很好的應用前景，所以代理簽名一提出便進行了廣泛的關注，并得到了深入的研究，提出了各種各樣的代理簽名體制。但一個安全的代理簽名必須滿足不可偽造性、可驗證性、不可否認性、可區(qū)分性等性質[1]。為體現(xiàn)原始簽名者與代理簽名者的公平性，Lee等人[2]提出代理簽名還應該滿足強不可偽造性、強可識別性、強不可否認性和阻止濫用性。

為防止濫用代理簽名權，1997年Kim等人[3]和Zhang[4]分別提出了(t，n) 門限代理簽名方案，原始簽名人把代理簽名密鑰分割成n份并分發(fā)給n個代理簽名人，它要求n個代理簽名人中至少t個人的合作才能生成代表原始簽名人的代理簽名，但是小于t個則不行。Sun等人[5]指出他們的方案都是不安全的，并基于Zhang的方案提出了一個改進算法。Hsu等人[6]指出Sun的方案違背了門限代理的原則，他們的方案中代理簽名的產(chǎn)生不一定完全遵守規(guī)定門限值，并給出了一個改進方案；而李繼國等人[7]指出Sun的方案無法抵抗替換公鑰攻擊，并給出了一個改進方案。

考慮到當代理簽名發(fā)生爭議時，仲裁者必須知道誰是代理簽名的真正簽名者，所以代理簽名具有不可否認性是個十分重要的性質。1999年，Sun[8]提出了具有已知簽名人的不可否認門限代理簽名方案，Hsu等人[9]指出Sun 的方案無法抵抗合謀攻擊并給出了一個改進方案。2004年，Yang等人[10]提出了一個效率優(yōu)于Hsu的不可否認門限代理簽名方案。2000年基于Kim的方案，Hwang等人[11]提出了一個不可否認門限代理簽名方案，然而Hwang and Chen[12]給出的原始簽名人與一個代理簽名人的合謀攻擊方案表明他們的方案是不安全的，Tzeng等人[13]給出了一個更有效的攻擊方案——原始簽名人的假冒攻擊指出了文獻[11]的缺陷，并給出了改進方案。

考慮到李繼國等人[7]指出Sun的方案無法抵抗替換公鑰攻擊，并給出了抵抗替換公鑰攻擊的一般方法和一個改進方案，并稱該改進方案能抵抗替換公鑰攻擊。然而，本文指出他們的方案依然無法抵抗替換公鑰攻擊，同時提出了代理關系轉換攻擊方法，成功地攻擊了他們的方案。該攻擊方法對設計安全的代理簽名有重要的價值。本文提出的兩種攻擊方法同樣能攻擊Hsu等人[6]提出的改進方案；最后給出了門限代理簽名的進一步改進方案。

2 文獻[7]的門限代理簽名方案簡介

設p和q是兩個大素數(shù)，滿足q|(p-1)，隨機選取q階生成元g∈Z*p；h(·)是單向抗碰撞Hash函數(shù)；PGID={EM，Time，Group}記錄代理人的身份，其中，EM表示代理密鑰產(chǎn)生的標記包括參數(shù)t和n，Time表示代理簽名的有效期限，Group表示原始簽名人和代理簽名人的身份信息。每個用戶Pi的私鑰為xi∈Z*q，公鑰為yi=gxi mod p，并得到CA的認證。設P0是原始簽名人，G={P1，P2，…，Pn}是n個代理簽名人。文獻[7]的方案由代理密鑰產(chǎn)生階段、代理簽名產(chǎn)生與驗證三個階段組成。

2．1 代理密鑰產(chǎn)生階段

(1)原始簽名人隨機選取∈RZq，計算并廣播=gk~mod p。

(2)每個Pi∈G隨機選取αi∈RZq，計算ri=gαi mod p，使得ri∈Z*p成立，然后廣播ri。

(3)原始簽名人計算r=∏ni=1ri，=n-1x0h(r，PGID，y0)+(mod q)，并廣播。

(4)每個Pi∈G計算r=∏ni=1ri，并通過下式檢查的正確性：gs~=yn-1h(r，PGID，y0)0 mod p

如果成立，每個Pi∈G計算si=+αi+xiyih(r，PGID，y0)(mod q)。

(5)每個Pi∈G產(chǎn)生一個t-1階的秘密多項式：

fi(x)=si+a(i，1)x+…+a(i，t-1)xt-1 mod q

這里，a(i，1)，…，a(i，t-1)是隨機數(shù)。計算fj(i)（1≤i，j≤n，i≠j）給其他成員，計算并廣播ga(u，v)(1≤u≤n，1≤v≤t-1)。每個Pi收到來自Pj的fj(i)（1≤i，j≤n，i≠j）后，通過下式驗證fj(i)的正確性：

gfj(i)=gs~rjyjyjh(r，PGID，y0)-1(ga(j，1))i（ga(j，2))i2…(ga(j，t-1))it-1mod p

如果成立，記f(x)=∑nj=1fj(x)mod q，則計算

xi′=f(i)=∑ni=1si+a1i+…+at-1it-1 mod q

這里aj=∑ni=1a(i， j) mod p(j=1，…，t-1)。

2．2 代理簽名的產(chǎn)生階段

設D={P1，P2，…，Pt}是t個代理簽名人，他們想對消息m生成代表原始簽名人的代理簽名。他們共同合作執(zhí)行以下步驟：

(1)每個Pi∈D隨機地產(chǎn)生一個t-1階的秘密多項式：

fi′(x)=a(i，0)′+a(i，1)′x+…+a(i，t-1)′xt-1 mod q

然后計算并廣播fj′(i)（1≤i，j≤n，i≠j）和ga(u，v)′(1≤u≤n，1≤v≤t-1)給其他成員。每個Pi收到來自Pj的fj′(i)（1≤i， j≤n，i≠j）后，通過下式驗證fj′(i)的正確性：

gfj′(i)=ga(j，0)′(ga(j，1)′)i(ga(j，2)′)i2…(ga(j，t-1)′)it-1 mod p

如果成立，則計算：

xi″=f′(i)=a0′+a1′i+…+at-1′it-1 mod q

這里aj′=∑ti=1a(i，j)′ mod p(j=0，1，…，t-1)。

(2)每個Pi∈D計算K=ga0′mod p和Ti=xi′h(m)+xi″K(mod q)，然后把Ti廣播給D中的其他代理簽名人。當收到所有的Tj(j≠i)后，每個Pi通過下列方程來驗證Tj(j≠i)的有效性:

gTj=[gn∏nk=1rk∏nk=1yykh(r，PGID，y0)k-n∏nk=1(ga(k，1))j∏nk=1(ga(k，2))j2…

∏nk=1(ga(k，t-1))jt-1]h(m)×[∏tk=1ga(k，0)′∏tk=1(ga(k，1)′)j∏tk=1(ga(k，2)′)j2…

∏tk=1(ga(k，t-1)′)jt-1]K mod p

記f′(x)=∑tj=1fj′(x) mod q

f″(x)=f(x)h(m)+f′(x)K mod q

(3)每個Pi∈D能對Ti應用Lagrange 插值多項式計算：

T=f(0)h(m)+f′(0)K mod q

則(r，PGID，K，T)即為消息m的代理簽名。

2．3 代理簽名的驗證階段

驗證者收到消息m的代理簽名(r，PGID，K，T)后，利用下式來驗證代理簽名的正確性：

gT=((y0∏ni=1yyii)h(r，PGID，y0)r)h(m)KK mod p

3 文獻[7]的門限代理簽名方案的密碼學分析

3．1 攻擊1：替換公鑰攻擊

下面給出原始簽名人與某個代理人如Pi合作，利用替換公鑰的方法假冒n個代理簽名人對任意的消息產(chǎn)生一個有效的代理簽名方案。設任取的消息為m′，攻擊方案如下：

（1）由于Pi知道自己代理的子密鑰

xi′=f(i)=∑nj=1sj+∑t-1j=1ajij mod q=x0h(r，PGID，y0)+(n+∑nj=1αj)+h(r，PGID，y0)∑nj=1xjyj+∑t-1j=1ajij(mod q)

其中aj=∑ni=1a(i，j) mod p(j=1，…，t-1)。計算

σ=xi′(h(r，PGID，y0))-1=x0+(n+∑nj=1αj)(h(r，PGID，y0))-1+∑nj=1xjyj+∑t-1j=1ajij(h(r，PGID，y0))-1(mod q)

并把σ發(fā)送給原始簽名人。

（2）原始簽名人計算新的公鑰

y0′=y0(r(ga(j，1))i(ga(j，2))i2…(ga(j，t-1))it-1)(h(r，PGID，y0))-1mod p

并且按需要修改代理證書PGID為PGID′。

（3）原始簽名人任取a∈Z*q，計算r′=gamod p。

（4）原始簽名人任取b∈Z*q，計算K′=gbmod p。

（5）原始簽名人計算T′=(σh(r′，PGID′，y0′)+a)h(m′)+bK′(mod q)，則(r′，PGID′，K′，T′)即為消息m′的有效代理簽名，因為代理簽名的驗證者能驗證該代理簽名的合法性：

((y0′∏ni=1yyii)h(r′，PGID′，y0′)r′)h(m′)(K′)K′=((y0(r(ga(j，1))i(ga(j，2))i2…

(ga(j，t-1))it-1)(h(r，PGID，y0))-1∏ni=1yyii)h(r′，PGID′，y0′)r′)h(m′)(K′)K′=

g((x0+∑ni=1xiyi+(n+∑nj=1aj+∑t-1j=1ajij)(h(r，PGID，y0))-1)h(r′，PGID′，y0′)+a)h(m′)+bK′=

g(σh(r′，PGID′，y0′)+a)h(m′)+bK′=gT′mod p

所以，攻擊成功。

3．2 攻擊2：代理關系轉換攻擊

下面給出n個代理簽名人合作對任意的消息產(chǎn)生一個代理多重簽名方案，驗證者能夠確信該代理簽名是原始簽名人P0代表n個代理簽名人G={P1，P2，…，Pn}產(chǎn)生的代理多重簽名。設任取的消息為m′，攻擊方案如下：

（1）n個代理簽名人修改代理證書PGID為PGID′，著重修改原始簽名群和代理簽名人的身份信息和代理關系，其他內容如簽名文件的類型、代理時間等按需要修改。

（2）任取b∈Z*q，計算K′=gb mod p。

（3）任取a∈Z*q，計算r′=ga mod p。

（4）計算s′=ny0(h(r，PGID，y0))-1=x0y0+y0(h(r，PGID，y0))-1(mod q)。

（5）n個代理簽名人中的任一成員如P1修改自己的公鑰y1為y1′=y1y0(h(r，PGID，y0))-1 mod p

然后，計算群公鑰Y′=y1′y2y3…yn mod p。

（6）G={P1，P2，…，Pn}中的每個成員計算并廣播Ti。

Ti′=((s′n-1+xi)h(r′，PGID′，Y′)+an-1)h(m′)+bK′n-1(mod q)

（7）計算T′=∑ni=1Ti′mod q，則(r′，PGID′，K′，T′)即為消息m′的、由n個代理簽名人假冒原始簽名人P0產(chǎn)生的、代表G={P1，P2，…，Pn}的有效代理簽名。因為代理簽名的驗證者能從PGID′中明確代理關系，而且可以驗證該代理簽名的合法性：

((yy00y1′∏ni=2yi)h(r′，PGID′，Y′)r′)h(m′)(K′)K′=((yy00y1y0(h(r′，PGID，y0))-1∏ni=2yi)h(r′，PGID′，Y′)r′)h(m′)(K′)K′=g((s′+∑ni=1xi)h(r′，PGID′，Y′)+a)h(m′)+bK′=g∑ni=1Ti′=gT′mod p

以上兩種攻擊方案表明文獻[7]的門限代理簽名方案存在安全上的漏洞，這兩種攻擊方法同樣能夠攻擊文獻[6]的門限代理簽名方案。

4 改進方案及其分析

4．1 改進方案

改進方案的系統(tǒng)參數(shù)與文獻[7]的門限代理簽名方案相同，它由代理密鑰產(chǎn)生階段、代理簽名產(chǎn)生與驗證三個階段組成。

4．1．1 代理密鑰產(chǎn)生階段

(1)原始簽名人隨機選取∈RZq，計算并廣播=gk~mod p。

(2)每個Pi∈G隨機選取αi∈RZq，計算ri=gαi mod p，使得ri∈Z*p成立，然后廣播ri。

(3)原始簽名人計算r=∏ni=1ri，=x0y0h(r，PGID，y0，Y)+n(mod q)，然后用(t，n)VSS方案把分配給n個代理人。選取t-1階的秘密多項式：

f0(x)=+a01x+…+a0t-1xt-1 mod q

將c0i=ga0i mod p（i=1，2，…，t-1）公開，將s0i=f0(i) mod q密送給每個Pi∈G。

(4)每個Pi∈G計算r=∏ni=1ri，并通過下式檢查s0i的正確性：

gs0i=yy0h(r，PGID，y0，Y)0n∏t-1j=1(c0j)ij mod p

(5)每個Pi∈G產(chǎn)生一個t-1階的秘密多項式：

fi(x)=αi+xiYh(r，PGID，y0，Y)+a(i，1)x+…+a(i，t-1)xt-1 mod q

這里，a(i，1)，…，a(i，t-1)是隨機數(shù)。計算fj(i)(1≤i，j≤n，i≠j)給其他成員，計算并廣播ga(u，v)(1≤u≤n，1≤v≤t-1)。每個Pi收到來自Pj的fj(i)(1≤i，j≤n，i≠j)后，通過下式驗證fj(i)的正確性：

gfj(i)=rjyYh(r，PGID，y0，Y)j-1(ga(j，1))i(ga(j，2))i2…(ga(j，t-1))it-1 mod p

如果成立，記f(x)=∑nj=1fj(x)mod q，每個Pi 計算xi′=f(i)，則f(0)=∑ni=1αi+Yh(r，PGID，y0，Y)∑ni=1xi(mod q)。

4．1．2 代理簽名的產(chǎn)生階段

設D={P1，P2，…，Pt}是t個代理簽名人，他們想對消息m生成代表原始簽名人的代理簽名，并共同合作執(zhí)行以下步驟：

(1)每個Pi∈D隨機地產(chǎn)生一個t-1階的秘密多項式：

fi′(x)=a(i，0)′+a(i，1)′x+…+a(i，t-1)′xt-1mod q

然后計算并廣播fj′(i)(1≤i，j≤n，i≠j)和ga(u，v)′(1≤u≤n，1≤v≤t-1)給其他成員。每個Pi收到來自Pj的fj′(i)(1≤i，j≤n，i≠j)后，通過下式驗證fj′(i)的正確性：

gfj′(i)=ga(j，0)′(ga(j，1)′)i(ga(j，2)′)i2…(ga(j，t-1)′)it-1mod p

如果成立，則計算：

xi″=f′(i)=a0′+a1′i+…+at-1′it-1mod q

這里aj′=∑ti=1a(i，j)′mod p(j=0，1，…，t-1)。

(2)每個Pi∈D計算K=ga0′mod p和Ti=(s0i+xi′)h(m，K，r，PGID，y0，Y)+xi″K(mod q)，然后將Ti廣播給D中的其他代理簽名人。當收到所有的Tj(j≠i)后，每個Pi通過下列方程來驗證Tj(j≠i)的有效性：

gTj=(yy0h(r，PGID，y0，Y)0∏t-1j=1(c0j)ijrYYh(r，PGID，y0，Y)×∏nk=1(ga(k，1))j

∏nk=1(ga(k，2))j2…∏nk=1(ga(k，t-1))jt-1)h(m，K，r，PGID，y0，Y)×(∏tk=1ga(k，0)′

∏tk=1(ga(k，1)′)j∏tk=1(ga(k，2)′)j2…∏tk=1(ga(k，t-1)′)jt-1)K mod p

記f′(x)=∑tj=1fj′(x)mod q

f″(x)=(f0(x)+f(x))h(m)+f′(x)K mod q

(3)每個Pi∈D能對Ti應用Lagrange 插值多項式計算：

T=(+f(0))h(m)+f′(0)K mod q

則(r，PGID，K，T)即為消息m的代理簽名。

4．1．3 代理簽名的驗證階段

驗證者收到消息m的代理簽名(r，PGID，K，T)后，利用下式來驗證代理簽名的正確性：

gT=((yy00YY)h(r，PGID，y0，Y)r)h(m，K，r，PGID，y0，Y)KK mod p

4．2 改進方案的安全性分析

下面討論改進的方案能夠抵抗我們提出的攻擊方法和文獻[6]中提出的攻擊方法的攻擊。

利用攻擊1的方法進行攻擊，原始簽名人與某個代理人如Pi合作，則可以計算

σ=(xi′+)(h(r，PGID，y0，Y))-1=(x0y0+∑nj=1xjY)+(n+∑nj=1αj+∑t-1j=1ajij)(h(r，PGID，y0，Y))-1(mod q)

原始簽名人計算新的公鑰y0′滿足(y0′)y0′=yy00(r(ga(j，1))i(ga(j，2))i2…(ga(j，t-1))it-1)(h(r，PGID，y0，Y)-1 mod p

是不可能的，除非他們能夠解離散對數(shù)問題。

利用攻擊2的方法進行攻擊，n個代理簽名人合作，其中某個代理人如P1需要修改公鑰成y1′，需滿足(y1′)y1′=yy11(h(r，PGID，y0，Y))-1 mod p，這也是不可能的，除非他們能夠解離散對數(shù)問題。另一方面，盡管原始簽名人的公鑰y0與n個代理簽名人的公鑰積Y在門限代理簽名的驗證方程中的表現(xiàn)形式似乎具有對稱關系（yy00YY），但n個代理簽名人無法修改代理證書PGID，所以驗證者不會誤認相互之間的代理關系。

由于我們提出的改進方案中結合了文獻[6]中的改進方案，所以也能抵抗文獻[6]中提出的代理簽名的產(chǎn)生不一定完全遵守規(guī)定門限值的弱點。所以，我們提出的改進方案是安全的。

5 結論

本文對文獻[7]提出的門限代理簽名的改進方案進行了密碼學分析，指出他們的方案依然無法抵抗替換公鑰的攻擊，同時提出了一種新的攻擊方法——代理關系轉換攻擊，成功地攻擊了他們的方案。該攻擊方法對設計安全的代理簽名有重要價值，提出的兩種攻擊方法同樣能攻擊Hsu等人[6]提出的改進方案。最后給出了門限代理簽名的進一步改進方案。

參考文獻：

[1]M Mambo， K Usuda， E Okamoto. Proxy Signatures: Delegation of the Power to Sign Messages[J]. IEICE Trans. on Fundamentals， 1996，E79A(9):13381354.

[2]B Lee， H Kim， K Kim. Strong Proxy Signature and Its Application[C]. Proc.of ACISP， 2001.603-608.

[3]S Kim， S Park， D Won. Proxy Signatures， Revisited[C]. Proc. of ICICS， Berlin:SpringerVerlag，1997.223-232.

[4]K Zhang. Threshold Proxy Signature Schemes[C]. Information Security Workshop，1997.191197.

[5]H M Sun， N Y Lee， T Hwang. Threshold Proxy Signatures[J]. IEE Proc.of Computers Digital Techniques， 1999，146(5):259-263.

[6]C L Hsu， T S Wu， T C Wu. Improvement of Threshold Proxy Signature Scheme[J]. Applied Mathematics and Computation， 2003，136:315-321.

[7]李繼國，曹珍富.一個改進的門限代理簽名方案[J].計算機研究與發(fā)展，2002，39(11):15131518.

[8]H M Sun. An Efficient Nonrepudiable Threshold Proxy Signature Scheme with Known Signers[J]. Comput. Commun.， 1999，22(8): 717-722.

[9]C L Hsu， T S Wu， T C Wu. New Nonrepudiable Threshold Proxy Signature Scheme with Known Signers[J]. The Journal of Systems and Software， 2001，58:119124.

[10]C Y Yang， S F Tzeng， M S Hwang. On the Efficiency of Nonrepudiable Threshold Proxy Signature Scheme with Known Signers[J]. The Journal of Systems and Software， 2004，73:507-514.

[11]M S Hwang， I C Lin， E J L Lu. A Secure Nonrepudiable Threshold Proxy Signature Scheme with Known Signers[J]. Informatica，2000，11(2):137144.

[12]S J Hwang， C C Chen. Cryptanalysis of Nonrepudiable Threshold Proxy Signature Scheme with Known Signers[J]. Fundamental Informaticae， 2003，14(2):205-212.

[13]S F Tzeng， M S Hwang， C Y Yang. An Improvement of Nonrepudiable Threshold Proxy Signature Scheme with Known Signers[J]. Computers Security， 2004，23:174178.

作者簡介：

謝琪（1968-），男，浙江上虞人，副教授，博士，主要研究方向為密碼學和信息安全;于秀源（1942-），男，山東章邱人，教授，博導，博士，主要研究方向為數(shù)論及其應用、密碼學和信息安全。

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