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

(昆明理工大學 信息工程與自動化學院, 昆明 650500)

?

一種共享驗證門限的多代理多重簽名方案

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

(昆明理工大學 信息工程與自動化學院, 昆明 650500)

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

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

0　引　言

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

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

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

1　基本原理

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

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

(1)對N進行因式分解;

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

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

1.3單向哈希函數(shù)

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

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

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

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

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

(1)選擇一個大素數(shù)N,生成一個t-1次多項式:

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

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

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

2　多重簽名過程

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

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

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

(4)當DC接受到所有的δOi后,驗證下面的等式:

(1)

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

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

當收到(δO,Mw,K,IDO)之后,每個UPi∈GP驗證下面的等式:

(2)

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

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

2.4代理簽名生成階段

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

2.5共享驗證階段

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

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

3　正確性分析

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

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

證明:

所以,

證畢。

定理2在代理簽名驗證階段,簽名驗證人可以通過:

證明:

那么,

又因為,

αRdbtmodN，

所以,

VE=αERdbtmodN。

因此,

證畢。

4　安全性分析

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

4.1不可偽造性

4.2不可否認性和共享驗證性

4.3密鑰的依賴性

4.4私鑰的安全性

5　結(jié)束語

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

[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]. 計算機工程, 2012, 38(9): 131-133.

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

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

[8]王曉明, 符方偉. 指定驗證人的(t,n)門限代理簽名方案[J]. 軟件學報, 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]王志波, 李雄, 杜萍. 共享可驗證的不可否認門限多代理多重簽名方案[J]. 計算機工程與應用, 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]劉幼萍, 吳鋌, 王輝. 強不可偽造的代理多簽名方案[J]. 計算機應用, 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ā)項目(2011CA019)

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

10.3969/j.issn.2095-7262.2014.03.020

TP309

2095-7262(2014)03-0317-06

A