趙之洛,　繆祥華,　唐　鳴,　張　斌

(昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院, 昆明 650500)

?

一種共享驗(yàn)證門限的多代理多重簽名方案

趙之洛,繆祥華,唐鳴,張斌

(昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院, 昆明 650500)

針對(duì)已有的共享可驗(yàn)證門限多代理多重簽名方案不能抵抗合謀攻擊及不真正具有共享驗(yàn)證的問題,基于大數(shù)分解的困難性(RSA)、離散對(duì)數(shù)問題(DLP)、單向哈希函數(shù)和(t,n)門限共享機(jī)制，提出了一種新的共享可驗(yàn)證的門限多代理多重簽名方案。該方案中,任意t1個(gè)或更多的原始簽名者可以將簽名權(quán)委托給代理簽名群;任意t2個(gè)或更多的代理簽名者可以代表原始簽名者依據(jù)授權(quán)進(jìn)行代理簽名;任意t3個(gè)或更多的指定驗(yàn)證者能夠合作完成對(duì)代理簽名有效性的驗(yàn)證。結(jié)果表明,該簽名方案能夠滿足代理簽名的安全性要求。

代理簽名; 門限多代理多重簽名; 共享驗(yàn)證; RSA; 單向哈希函數(shù)

0　引　言

1997年,Kim和Zhang等將(t,n)門限共享體制和代理簽名相互結(jié)合,首次提出了門限代理簽名方案[1-2]。在(t,n)門限代理簽名方案中,不少于t個(gè)代理簽名者能代表原始簽名者簽名,但在一般的門限代理簽名方案中,最終簽名的有效性驗(yàn)證均是采用單獨(dú)的驗(yàn)證者來完成的,這是理想化的情況[1-6]。在多數(shù)實(shí)際情況下,是需要授權(quán)的驗(yàn)證人一起才能驗(yàn)證代理簽名的有效性,例如電子商務(wù)中的電子投標(biāo)和電子選舉等[7-8]。

2004年,Tzeng等[9]提出了一個(gè)不可否認(rèn)的可共享驗(yàn)證的多代理多重簽名方案。隨后,Bao等[10]指出Tzeng等的方案不能抵抗構(gòu)造攻擊,敵手可以在截獲的一個(gè)有效的代理簽名之后構(gòu)造一個(gè)能夠通過驗(yàn)證的偽造代理簽名。2007年,Hsu等[11]又指出Tzeng等的方案不能抵抗合謀攻擊,任何一個(gè)驗(yàn)證者都能在無需其他驗(yàn)證者幫助的情況下驗(yàn)證代理簽名的有效性。2009年,Kang等[12]指出Hsu等的方案也容易受到內(nèi)部攻擊,并且文獻(xiàn)[8-10]的方案不具有(t1,n1)門限性質(zhì)。2011年,王志波等[13]針對(duì)Tzeng等的方案不能抵抗偽造攻擊和不具有共享驗(yàn)證的性質(zhì),提出了一個(gè)基于離散對(duì)數(shù)的不可否認(rèn)和可共享驗(yàn)證的多代理多重簽名方案,但是該方案不能抵抗合謀攻擊,在秘密份額生成階段,每個(gè)原始簽名者的秘密份額為f(IDi),每個(gè)UOi知道IDi的值,那么t1個(gè)或多于t1個(gè)內(nèi)部惡意者合謀即可恢復(fù)出秘密多項(xiàng)式,并獲得群密鑰XO和秘密份額f(IDi),同理,代理群和驗(yàn)證群也會(huì)受到同樣的攻擊,每個(gè)群的私鑰和每個(gè)用戶的秘密份額都會(huì)泄露,從而每個(gè)惡意驗(yàn)證者都能在沒有其他成員的幫助下完成簽名驗(yàn)證,即不具有共享驗(yàn)證性,所以文獻(xiàn)[13]的方案存在安全缺陷。

因此,針對(duì)已有方案的缺陷,綜合已提出各種方案的研究成果,筆者提出一種新的可共享驗(yàn)證的門限多代理多重簽名方案,該方案彌補(bǔ)已有方案的缺陷,可以抗合謀攻擊和偽造攻擊,滿足門限代理簽名的安全性要求[14-15]。

1　基本原理

1.1大整數(shù)分解難題

設(shè)N=pq,其中p、q是兩個(gè)大素?cái)?shù)。整數(shù)e和d滿足ed≡1modφ(N),其中φ(N)=(p-1)(q-1),是歐拉函數(shù),那么下面三種假設(shè)是計(jì)算不可行的:

(1)對(duì)N進(jìn)行因式分解;

(2)已知C和e,求一個(gè)整數(shù)M使得Me≡CmodN;

(3)已知M和C,求一個(gè)整數(shù)d使得Cd≡MmodN。1.2離散對(duì)數(shù)難題

1.3單向哈希函數(shù)

一個(gè)單向哈希函數(shù)h(·)可以作用在任意長(zhǎng)度的消息上,對(duì)于函數(shù)h(·),可以在一個(gè)確定的多項(xiàng)式時(shí)間內(nèi)從x計(jì)算出y=h(x)。但是已知y=h(x)求x是計(jì)算不可行的。

單向哈希函數(shù)的弱抗碰撞是指:對(duì)于給定的x1,要找到一個(gè)x2滿足h(x1)=h(x2)是計(jì)算上不可行的。

單向哈希函數(shù)的強(qiáng)抗碰撞是指:要找到一對(duì)不同的消息x1和x2,使得h(x1)=h(x2)是計(jì)算上不可行的。

1.4(t,n)門限共享機(jī)制

在(t,n)門限共享機(jī)制中,將一個(gè)密鑰D按照一定的計(jì)算方式碎化,分配給n個(gè)不同的用戶保管。t或者t個(gè)以上的用戶一起合作可以恢復(fù)出密鑰D,并且少于t個(gè)用戶合作不能恢復(fù)出密鑰D。(t,n)門限共享機(jī)制的過程可以用數(shù)學(xué)方式表達(dá)如下:

(1)選擇一個(gè)大素?cái)?shù)N,生成一個(gè)t-1次多項(xiàng)式:

f(x)=D+a1x+a2x2+…+ai-1xi-1modN,

(2)秘密份額分發(fā)過程:假設(shè)xi(i=1,2,…,t-1)代表n個(gè)不同用戶,那么每個(gè)用戶得到的秘密份額就是si=f(xi)modN。

(3)密鑰恢復(fù)過程:需要t或t個(gè)以上的用戶合作,才能通過拉格朗日插值公式將密鑰D恢復(fù)出來:

2　多重簽名過程

2.1系統(tǒng)初始化階段

在簽名系統(tǒng)中假設(shè)存在一個(gè)可信的秘密份額分發(fā)中心(Share Distribution Center, SDC),主要負(fù)責(zé)生成系統(tǒng)參數(shù),秘密選取p=2p′+1和q=2q′+1為兩個(gè)強(qiáng)素?cái)?shù),其中,p′和q′是兩個(gè)大素?cái)?shù);N是p和q的乘積,即N=pq;r=2p′q′;E滿足E和r互素(GCD(E,r)=1)且E≈1050;α是有限域GF(q)中的本原元;h(·)是一個(gè)單向哈希函數(shù);Mw是委托證書,其中記錄了所有原始簽名者、代理簽名者以及簽名驗(yàn)證者的身份標(biāo)志,參數(shù)(t1,n1)、(t2,n2)、(t3,n3)和有效的授權(quán)代理時(shí)間等;IDO表示實(shí)際參與的原始簽名者的身份,IDP表示實(shí)際參與的代理簽名者的身份。其中{p,q,p′,q′,α,r}保密,{N,E,h(·)}公開。

2.2秘密份額生成階段

SDC執(zhí)行以下步驟:

(3)SDC分別為GO、GP、GV生成構(gòu)造t1-1、t2-1和t3-1次秘密多項(xiàng)式如下:

(3)每個(gè)UOi∈DO通過公開信道將δOi發(fā)送給指定秘書(Designated Clerk, DC)。

(4)當(dāng)DC接受到所有的δOi后,驗(yàn)證下面的等式:

(1)

如果式(1)成立,則說明UOi∈DO是合法的原始簽名者,δOi和kOi的值是合法的。如果不成立,DC要求原始簽名者重新發(fā)送一個(gè)合法值。然后,DC計(jì)算δO:

(5)DC向GP公示(δO,Mw,K,IDO)。

當(dāng)收到(δO,Mw,K,IDO)之后,每個(gè)UPi∈GP驗(yàn)證下面的等式:

(2)

如果式(2)成立,每個(gè)UPi∈GP計(jì)算δPi作為自己的代理簽名密鑰:

如果不成立,則拒絕接受此δO,并向原始簽名人詢問一個(gè)合法值。

2.4代理簽名生成階段

(3)當(dāng)接收到這些SPj之后,DC需要驗(yàn)證其有效性,計(jì)算下面等式是否成立:

2.5共享驗(yàn)證階段

(1)根據(jù)Mw、IDO、IDP,每個(gè)驗(yàn)證者UVi∈DV可以從CA處獲得原始簽名者和代理簽名者的公鑰。并且能夠知道實(shí)際參與的原始簽名者和實(shí)際參與的代理簽名者。

(4)每個(gè)UVi∈DV可以通過下式驗(yàn)證消息M的代理簽名的有效性:

3　正確性分析

定理1在代理授權(quán)份額生成階段,每個(gè)代理簽名人UPi∈DP可以通過驗(yàn)證:

來確定代理授權(quán)的有效性。

證明:

所以,

證畢。

定理2在代理簽名驗(yàn)證階段,簽名驗(yàn)證人可以通過:

證明:

那么,

又因?yàn)?

αRdbtmodN，

所以,

VE=αERdbtmodN。

因此,

證畢。

4　安全性分析

該方案的安全性主要是基于RSA問題、單向哈希函數(shù)求逆難題以及(t,n)門限秘密分享方案的安全性。

4.1不可偽造性

4.2不可否認(rèn)性和共享驗(yàn)證性

4.3密鑰的依賴性

4.4私鑰的安全性

5　結(jié)束語

基于RSA密碼體制提出了一種新的可共享可驗(yàn)證的((t1,n1),(t2,n2),(t3,n3))門限多代理多重簽名方案。該方案中的影子密鑰作為秘密份額,其安全性受到RSA問題難解性的保護(hù),內(nèi)部惡意者合謀攻擊也無法獲得秘密多項(xiàng)式和群私鑰。在授權(quán)份額和代理簽名的生成過程中加入單向哈希函數(shù),保證合法的授權(quán)和代理簽名不被偽造。同時(shí),任意t3個(gè)以上的驗(yàn)證者可以合作驗(yàn)證簽名的有效性。該方案從根本上克服了已有方案的缺陷,并符合代理簽名的安全性要求。

[1]KIM S, PARK S, WON D. Proxy signatures revisited[C]//Proceedings of the 1st International Conference. [S. 1.]: Springer, 1997: 223-232.

[2]ZHANG K. Threshold proxy signature schemes[C]//Proceedings of the 1st International Workshop. [S.l.]: Springer, 1998: 282-290.

[3]HWANG MINSHIANG, LUJUILIN, LIN IUONCHANG.A practical (t,n) threshold proxy signature scheme based on the RSA cryptosystem[J]. IEEE Transactions on Knowledge and Data Engineering, 2003, 15(6): 1552-1560.

[4]HSU C L, WU T S, WU T C.New nonrepudiable threshold proxy signature scheme with known signers[J]. The Journal of Systems and Software, 2001, 58(2): 119-124.

[5]王勇兵. 門限混合代理多重簽名方案[J]. 計(jì)算機(jī)工程, 2012, 38(9): 131-133.

[6]周孟創(chuàng). 秘密共享與代理簽名及其應(yīng)用研究[D]. 鄭州: 解放軍信息工程大學(xué), 2012.

[7]覃征, 閆焱, 王立. 特殊簽名及其在電子商務(wù)中的應(yīng)用[J]. 計(jì)算機(jī)應(yīng)用研究, 2003, 20(6): 1-3.

[8]王曉明, 符方偉. 指定驗(yàn)證人的(t,n)門限代理簽名方案[J]. 軟件學(xué)報(bào), 2005, 16(6): 1190-1196.

[9]TZENG S F, YANG C Y, HWANG M S. A nonrepudiable threshold multi-proxy multi-signature scheme with shared verification[J]. Future Generation Coputer Systens, 2004, 20(5): 887-893.

[10]BAO H, CAO Z, WANG S. Improvement on tong et als nonrepudiable threshold multi-proxy multi-signature scheme with shared verification[J]. Applied Mathematics and Computation, 2005, 169(2): 1419-1430.

[11]CHIENLUNG HSU, KUOYU TSAI, PEILING TSAI. Cryptanalysis and improvement of nonrepudiable threshold multi-proxy multi-signature schemewith shared verification[J]. Information Sciences, 2007, 177(2): 543-549.

[12]BAOYUAN KANG, COLIN BOYD, ED DAWSON. A novel nonrepudiable threshold multi-proxy multi-signature scheme with shared verification[J]. Computers and Electrical Engineering, 2009, 35(1): 9-17.

[13]王志波, 李雄, 杜萍. 共享可驗(yàn)證的不可否認(rèn)門限多代理多重簽名方案[J]. 計(jì)算機(jī)工程與應(yīng)用, 2011, 47(9): 93-127.

[14]SAMAMEH MASHHADI. Analysis of frame attack on hsu et al’s non-repudiable threshold[J]. Scientia Iranica, 2012, 19(3): 674-679.

[15]劉幼萍, 吳鋌, 王輝. 強(qiáng)不可偽造的代理多簽名方案[J]. 計(jì)算機(jī)應(yīng)用, 2012, 32(S1): 68-73.

(編輯李德根)

A shared verification threshold multi-proxy multi-signature scheme

ZHAOZhiluo,MIAOXianghua,TANGMing,ZHANGBin

(College of Information Engineering & Automation, Kunming University of Science & Technology, Kunming 650500, China)

This paper features a novel shared verification threshold multi-proxy multi-signature scheme as an alternative to existing shared verification threshold multi-proxy multi-signature scheme which suffers from its inability to resist collusion attack and its actual absence of the property of shared verification. This scheme draws on the difficulty in factorizing large integer(RSA), discrete logarithm problem(DLP), the one-way Hash function, and the (t,n) threshold secret sharing scheme. The scheme is unique in that anyt1or more of original signers can delegate the signing capability to the proxy group; anyt2or more of proxy signers can sign a message on behalf of the original group for a specified verifier group; and anyt3or more of verifiers can perform a joint verification of the validity of the proxy signature from the proxy group. The analysis shows that the scheme can fulfill the security requirements of proxy signature.

proxy signature; threshold multi-proxy multi-signature scheme; shared verification; RSA; one-way hash function

2013-11-21

云南省科技廳社發(fā)項(xiàng)目(2011CA019)

趙之洛(1988-),男,江蘇省東臺(tái)人,碩士,研究方向:信息安全理論與技術(shù)及代理數(shù)字簽名,E-mail:zeki2008@163.com。

10.3969/j.issn.2095-7262.2014.03.020

TP309

2095-7262(2014)03-0317-06

A