一種高效群簽名方案的設(shè)計(jì)與分析*

白永祥(1.渭南職業(yè)技術(shù)學(xué)院,陜西渭南714000;2.西北大學(xué)信息與科技學(xué)院,陜西西安710127)

一種高效群簽名方案的設(shè)計(jì)與分析*

白永祥1,2
(1.渭南職業(yè)技術(shù)學(xué)院,陜西渭南714000;2.西北大學(xué)信息與科技學(xué)院,陜西西安710127)

基于ElGamal密碼體制及其簽名算法,構(gòu)造了一個(gè)高效安全的群簽名方案。在簽名初始化階段,把群管理者分成兩個(gè)部分T1和T2,T1負(fù)責(zé)簽名群成員的加入,刪除和密鑰發(fā)行。如果發(fā)生爭端需要仲裁,那么可由T2負(fù)責(zé)打開群簽名并進(jìn)行追蹤,這種方法有效地實(shí)現(xiàn)了簽名群中成員的動(dòng)態(tài)管理,具有一定的高效性、安全性和實(shí)用性。方案給出了詳細(xì)的設(shè)計(jì)過程,并對其高效性和安全性進(jìn)行了分析,為群簽名方案的設(shè)計(jì)與實(shí)現(xiàn)提供了一種參考。

數(shù)字簽名算法 群簽名 ElGamal簽名算法

0 引 言

在傳統(tǒng)商務(wù)活動(dòng)中,為了保證交易過程的安全性與真實(shí)性,當(dāng)事人或負(fù)責(zé)人要在書面合同或公文上簽字、蓋章,而在基于互聯(lián)網(wǎng)的電子商務(wù)交易中,合同或文件是以電子文件的形式呈現(xiàn)和傳遞的,傳統(tǒng)的手寫簽名和蓋章在這里是無法使用的,為了保證傳輸和交易的安全性、真實(shí)性及不可抵賴性,起到與手寫簽名或蓋章等同的效果,電子簽名技術(shù)便應(yīng)運(yùn)而生。目前,實(shí)現(xiàn)電子簽名的技術(shù)手段有很多種,相對較成熟的電子簽名技術(shù)還是“數(shù)字簽名”。所謂數(shù)字簽名,就是通過運(yùn)用某種密碼算法生成一系列符號(hào)及代碼組成的電子密碼信息,用來代替手寫簽名或蓋章。數(shù)字簽名技術(shù)廣泛的應(yīng)用于電子商務(wù)和電子政務(wù)等領(lǐng)域中[1],數(shù)字簽名算法可分為一般數(shù)字簽名和特殊數(shù)字簽名算法,其中特殊數(shù)字簽名中的群簽名是當(dāng)前研究熱點(diǎn),對群簽名的深入研究和討論具有重要的作用和意義。

1 相關(guān)理論知識(shí)

1.1 基本概念

(1)數(shù)字簽名

ISO 7498-2對數(shù)字簽名的定義為:“附加在數(shù)據(jù)單元上的一些數(shù)據(jù),或是對數(shù)據(jù)單元所做的密碼變換,這種數(shù)據(jù)和變換允許數(shù)據(jù)單元的接收者用以確認(rèn)數(shù)據(jù)來源及完整性,并保護(hù)數(shù)據(jù),防止(如接收者)偽造”[1]。目前,數(shù)字簽名技術(shù)有兩種機(jī)制,一種是基于證書的簽名;另一種是基于身份的簽名。其中基于證書的機(jī)制又分為兩種:基于大整數(shù)因子分解的數(shù)字簽名;基于離散對數(shù)算法的數(shù)字簽名,本文所討論的ElGamal密碼算法就是基于后者的一種常用算法。

數(shù)字簽名技術(shù)出現(xiàn)以后,迅速得到了廣泛的應(yīng)用。在這一領(lǐng)域,密碼學(xué)家們設(shè)計(jì)了許多種簽名方案,有基于大整數(shù)因子分解的RSA簽名和Rabin簽名;以離散對數(shù)問題為基礎(chǔ)的ElGamal簽名、DSA簽名和Schnorr簽名等;還有基于橢圓曲線離散對數(shù)問題的ECDSA簽名。除此之外,還有一些特殊的數(shù)字簽名:如代理簽名、門限簽名、盲簽名、環(huán)簽名、群簽名等[2]。本文重點(diǎn)討論群簽名算法,一般數(shù)字簽名原理如圖1所示。

圖1 數(shù)字簽名操作過程Fig.1 Digital signature process

(2)群簽名

群簽名(group signature)概念是1991年由Chaum和Heyst聯(lián)合提出[3],所謂群簽名就是在簽名方案中,群體中的任一個(gè)成員可以以匿名的方式代表整個(gè)群體對消息進(jìn)行簽名。同其他數(shù)字簽名一樣,群簽名是可以公開驗(yàn)證的,而且可以只用單個(gè)群公鑰來驗(yàn)證。后來,Camenish、Stadler和Tsudik等人對這個(gè)概念進(jìn)行了修改和完善。群簽名在軍事、政治及經(jīng)濟(jì)等多個(gè)方面有著廣泛的應(yīng)用。

(3)群簽名對安全性的要求

Chaum和Heyst在提出群簽名概念時(shí)規(guī)定,一個(gè)安全的群簽名應(yīng)包含以下三個(gè)屬性:

1)防偽造性:只有群中成員才能對消息進(jìn)行簽名。

2)匿名性:消息接收者雖然能夠檢驗(yàn)群簽名的有效性,卻無法確認(rèn)簽名者的詳細(xì)身份。

3)可追蹤性:如果發(fā)生爭議,可以由團(tuán)體的成員或者第三方識(shí)別,并揭示出簽名者的身份。

隨著群簽名研究與應(yīng)用的不斷深入,對群簽名算法的要求不斷增多,一個(gè)安全的群簽名方案至少應(yīng)具有正確性、不可偽造性、匿名性、無關(guān)聯(lián)性、可跟蹤性、防陷害性和抗聯(lián)合攻擊等特征。

1.2 ElGamal簽名方案

1985年,ElGamal發(fā)表了論文[3],設(shè)計(jì)了一個(gè)巧妙的公鑰密碼體制。ElGamal的研究工作引起了密碼學(xué)領(lǐng)域?qū)＜覀兊臉O大興趣,并持續(xù)到今日。這是因?yàn)镋lGamal密碼算法充分體現(xiàn)了現(xiàn)代密碼學(xué)依賴的數(shù)學(xué)難題應(yīng)用于公鑰密碼系統(tǒng)的安全性?，F(xiàn)代密碼學(xué)技術(shù)都是基于算法復(fù)雜性理論,比如:大整數(shù)因子分解問題(IFP,Integer Factorization Problem);離散對數(shù)問題(DLP,Discrete Logarithm Problem);橢圓曲線離散對數(shù)問題(ECDLP,Elliptic Curve Discrete Logarithm Problem)。著名的RSA密碼體制就是基于IFP難題,基于RSA數(shù)字簽名可以閱讀文獻(xiàn)[4],本文所研究的ElGamal數(shù)字簽名是基于DLP難題。

1.2.1 ElGamal密碼算法

Bob要想通過公共網(wǎng)絡(luò)給Alice發(fā)送消息,Alice首先要生成自己的密鑰,她執(zhí)行下列步驟:

(1)密鑰生成

①隨機(jī)選擇一個(gè)素?cái)?shù)p;

③隨機(jī)選取x沂UZp-1,作為她的私鑰;

④計(jì)算機(jī)自己的公鑰:y←gx(mod p);

⑤公開自己的公鑰(p,g,y),x為她的私鑰。

1.2.2 ElGamal簽名過程

1985年,ElGamal提出了一種基于概率的簽名方案[4],方案中簽名者可以隨機(jī)選擇一個(gè)數(shù),所以對于明文m可以有多種簽名結(jié)果,ElGamal加密算法是基于離散對數(shù)的數(shù)學(xué)難題,具體過程如下:

(1)密鑰創(chuàng)建

(2)簽名生成

要生成消息m的簽名,發(fā)送者隨機(jī)選擇一個(gè)數(shù)

(3)簽名驗(yàn)證

接收者收到簽名數(shù)據(jù)后,由于他知道發(fā)送者的公鑰pukA及(g,p)。對于消息簽名對(m,r,s),接收者可做如下運(yùn)算進(jìn)行驗(yàn)證:

2 方案設(shè)計(jì)

以下新方案的設(shè)計(jì)基于ElGamal簽名算法。我們的思路是首先把群管理者分割成兩部分T1,T2, T1負(fù)責(zé)群成員的加入、刪除和密鑰分發(fā);T2負(fù)責(zé)出現(xiàn)爭端的情況下,打開群簽名信息并身份識(shí)別。這種把群管理者分割的方法,在群簽名成員數(shù)量增大的情況下有效的提高了群簽名的效率,使整個(gè)簽名方案更加趨向于實(shí)際應(yīng)用[4]。

方案的中主要符號(hào)代表:m為待簽名的消息, T1,T2為兩個(gè)群管理者,Ui為群中某個(gè)待簽名的用戶,H(·)為一安全的Hash函數(shù),且H:{0,1}*→{0,1}t。

2.1 系統(tǒng)初始化

在群初始化過程中,T1,T2分別為群設(shè)置公鑰和私鑰。具體過程如下:

T1選擇一長度為2l的數(shù)n,且n=p·q,p,q為安全的素?cái)?shù),然后再選定二次剩余QR(n)中的循環(huán)子群G,如果要計(jì)算G中的離散對數(shù),這是一個(gè)數(shù)學(xué)難題,g為G的一個(gè)生成元。

T1隨機(jī)選擇數(shù)x作為自己的私鑰,x沂RG,并通過y=gx(mod n)計(jì)算公鑰。

T2也產(chǎn)生一個(gè)長為2l的RSA模N,且N=P· Q,P,Q也為安全素?cái)?shù),這里有N＜n,并隨機(jī)選擇E, D沂RZ*N,并滿足E·D≡1(modφ(N))。

公鑰為Y={n,y,g,l,E,N};私鑰為{x,p,q,P, Q,D}。

2.2 群成員加入

假設(shè)群中有n個(gè)成員,成員Ui想要加入該群,需要以下操作過程:

T1隨機(jī)選擇xi,且xi沂RG,并計(jì)算Ui=xi+x憶i與yi=gximod n,然后把xi發(fā)送給用戶Ui,(Ui,yi)發(fā)送給T2,并作為Ui的群簽名證書。

2.3 簽名

如果Ui要對消息m進(jìn)行群簽名,具體過程如下:

1)簽名者Ui隨機(jī)選擇ri沂RG,并計(jì)算ci= H(Time椰yi椰g椰gri椰m)和si=ri-cixi,這里Time為時(shí)間戳,然后發(fā)送(Ui,m,ci,si,Time)給T2。

2)T2接到(Ui,m,ci,si,Time)后,首先檢查Time是否與當(dāng)前時(shí)間相一致及用戶Ui是否已經(jīng)撤銷。否則查找與Ui對應(yīng)的yi=gxi,并驗(yàn)證ci= H(Time椰yi椰g椰gsiycii椰m)是否成立,若成立,則可知簽名成立。T2再隨機(jī)選擇r憶i沂RG、Time憶,計(jì)算:

發(fā)送(Time憶椰s憶i椰c憶椰c)給用戶Ui,并把(Ui椰m椰Time椰Time憶椰ci椰si椰r憶i椰c)存儲(chǔ)到與Ui對應(yīng)的簽名列表中,以備日后打開簽名之用。

4)簽名用戶Ui公布對消息m的簽名(Time,,。

2.4 驗(yàn)證

驗(yàn)證者根據(jù)所收到的(Time,Time憶,c,c憶,s)檢驗(yàn)c=(c憶)E(mod N)是否成立,若成立則計(jì)算檢驗(yàn)c= H(Time椰Time憶椰y椰ycgs椰m)。如果上式成立,則接收(Time,Time憶,c,c憶,s)為群成員Ui對消息m的簽名,否則不接收[5]。

2.5 打開

如果出現(xiàn)爭議,群管理者T1就必須打開對消息的簽名,以確定簽名者的真實(shí)身份,這時(shí)只要向T2發(fā)送請求,T2根據(jù)其以前所存儲(chǔ)的有關(guān)簽名的信息查找簽名者的身份并向T1告知。

3 安全性分析

從以上方案可以看出,該方案其實(shí)是一個(gè)El-Gamal簽名方案的多簽名,所以,無論是用戶或者群管理都無法單獨(dú)產(chǎn)生一個(gè)有效的群簽名,即該簽名方案符合群簽名方案的全部安全性要求。

1)正確性:假設(shè)是滓=(Time,Time憶,c,c憶,s)是用戶Ui對消息m的一個(gè)合法簽名,由于(c,s)是某一群成員用戶對群公鑰y沂G基于g為底的離散對數(shù)的簽名,且滿足c=(c憶)E=H(Time椰Time憶椰y椰g椰ycgs椰m),所以,肯定能通過簽名驗(yàn)證[6]。

2)具有匿名性和不可鏈接性:群成員Ui對消息m的群簽名為(Time,Time憶,c,c憶,s),對簽名的驗(yàn)證只是使用T2的公鑰來驗(yàn)證c=(c憶)E(mod N),以及(c,s)是否為某一群成員用戶對群公鑰y沂G基于g為底的離散對數(shù)的簽名,因此協(xié)議中沒有涉及用戶Ui的個(gè)人信息,所以上述方案是無條件匿名的,同時(shí)也具有不可鏈接性。

3)可追蹤性:由于群管理者T2已經(jīng)存儲(chǔ)有群中每一個(gè)成員的列表信息,所以群管理者T1很容易通過T2提供的幫助達(dá)到跟蹤的目的。

4)抗聯(lián)合攻擊:如果沒有提供幫助,根據(jù)強(qiáng)RSA假設(shè)可知,群成員與群管理者不可能構(gòu)造出滿足c=(c憶)E(mod N)的(c,c憶),并計(jì)算出s=ri+r憶i-cx,進(jìn)而完成對群公鑰y沂G基于g為底的離散對數(shù)的簽名,避免了重放攻擊,同時(shí)在群成員加入時(shí),不同的用戶Ui,Uj私鑰滿足xi屹xj,因此除了用戶Ui外,任何人包括群成員集合中的每位成員都不可能偽造一個(gè)正確的群簽名。

我們的方案與其它群簽名方案相比較,有以下優(yōu)點(diǎn):

1)構(gòu)造簡單,易于實(shí)現(xiàn):我們的簽名方案類似于ElGamal簽名方案的多簽名形式,ElGamal簽名方案是一個(gè)經(jīng)典的成熟方案[7]。

2)工作效率高:在一般的群簽名方案中,群公鑰的長度是群成員個(gè)數(shù)n的線性函數(shù)。本簽名方案群簽名長度是固定不變的,不隨群中成員個(gè)數(shù)的變化而線性變化,且簽名長度比其它同類的都短,這是因?yàn)樵谖覀兊姆桨钢泻灻瑑蓚€(gè)時(shí)間表戳和三個(gè)群元素,所以整體群簽名效率較高。

3)具有動(dòng)態(tài)性:群簽名中的成員動(dòng)態(tài)變化是衡量一個(gè)群簽名的關(guān)鍵指標(biāo),在我們的方案中群成員可以隨機(jī)的加入和撤銷。群成員的撤銷簡單快捷,只要T2不提供簽名幫助,便能實(shí)現(xiàn)群成員的即時(shí)撤銷。

總之,群簽名在現(xiàn)代電子商務(wù)、電子選舉和網(wǎng)上投標(biāo)等方面有著重要的應(yīng)用,本方案引入了T1,T2,使得群成員的加入和刪除更加的簡單有效,在群簽名成員數(shù)量不斷增多的情況下,我們的群管理者分割方法靈活性更高,使復(fù)雜的管理變得更加高效,并有效的解決了通信中的密鑰管理問題[8]。

4 結(jié) 語

ElGamal算法即可用于加密,又可用于數(shù)字簽名,其安全性依賴計(jì)算有限域上離散對數(shù)的難度。本文基于ElGamal設(shè)計(jì)了一種高效安全的群簽名方案,在群成員管理方面實(shí)現(xiàn)了動(dòng)態(tài)機(jī)制。雖然使群簽名效率和安全性得到了一定提高,但由于ElGamal數(shù)字簽名長度過大等原因,本方案還存在一些不足。在EIGamal簽名族中最有影響的兩個(gè)變形是Schnorr和DSS簽名體制,這兩種簽名很大的一個(gè)特點(diǎn)是:運(yùn)行在較大有限域中一個(gè)很小的素階子群內(nèi),卻不降低離散對數(shù)的困難問題[9]。所以下一步研究重點(diǎn)應(yīng)加強(qiáng)對本方案的改進(jìn)。

參考文獻(xiàn)：

[1] 關(guān)振勝.公鑰基礎(chǔ)設(shè)施PKI及其應(yīng)用[M].北京:電子工業(yè)出版社,2008:32-43. GUAN Zhen-sheng.Public key Infrastructure PKIand Its Applications[M].Beijing:Electronic Industry Press, 2008:32-43.

[2] Chaum,Heyst.Group Signatures[J].Advances in Cryptology-EUROCRYPT'91,LNCS 547.Berlin:Spring-Verlog,1991:257-265.

[3] ElGamal.A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms[J].IEEE Transactions on Information Theory 1985,31(4):469-472.

[4] 劉傳領(lǐng),范建華.RSA非對稱加密算法在數(shù)字簽名中的應(yīng)用研究[J].通信技術(shù),2009,42(03):192-196. LIU Chuan-ling,FAN Jian-huan.Application of RSA A-symmetrical Encryption Algorithm in Digital Signature [J].Journal of Communications Technology,2009(03): 192-196.

[5] 毛文波.現(xiàn)代密碼學(xué)理論與實(shí)踐[M].王繼紅,伍前紅譯.北京:電子工業(yè)出版社,2006:184-189. BAOWen-bo.ModernCryptography Theory and Practice [M].Translated by WANG Ji-hong,WU Hong-qian. Beijing:Electronic Industry Press,2006:184-189.

[6] [美]Bruce Schneier.應(yīng)用密碼學(xué)協(xié)議、算法與C源程序[M].第2版.吳世忠,祝世雄,張文政等譯.北京:機(jī)械工業(yè)出版社,2010:374-368. Bruce Schneier.Applied Cryptography Protocols,Algorithm,and Source Code C[M].Second Edition.Translated by WU Shi-zhong,ZHU Shi-xiong,ZHANGWen-zheng etc.Beijing:Mechanical Industry Press,2010:374-368.

[7] 胡向東,魏琴芳,胡蓉.應(yīng)用密碼學(xué)[M].北京:電子工業(yè)出版社,2011:201-211. HU Xiang-dong,WEI Qin-fang,HU Rong.Modern Cryptography Theory and Practice[M].Beijing:Electronic Industry Press,2006:184-189.

[8] 鄧安文.密碼學(xué)-加密演算法[M].北京:中國水利出版社,2006:131-152. DENG An-wen.Cryptography-Encryption algorithm [M].Beijing:China Water Conservancy Press,2006: 131-152.

[9] 張文麗,趙峰.Hash簽名在電子商務(wù)中的應(yīng)用[J].計(jì)算機(jī)與數(shù)字工程,2014(03):130-135. ZHANGWen-li,ZHAO Feng.Hash Signature Application in Electronic Commerce[J].Computer and Digital Engineering,2014(3):130-135.

Design and Analysis of Efficient Group-Signature Scheme

BAIYong-xiang1,2
(1.Weinan Vocational&Technical College,Weinan Shaanxi714000,China; 2.College of Information Science and Technology,Northwest University,Xi'an Shaanxi710127,China)

Based on ElGamal signature system,an efficient group-signature scheme is proposed.In the initialization phase of signature,the group-manager is divided into two parts——T1 and T2,T1 is responsible for the accession and deletion of group members and distribution of secret-key for the group members.In case of dispute,T2 is responsible for opening group-signature and tracking.This scheme could effectively achieve dynamic management of the group-signature,and has certain efficiency,safety and practicability.A detailed design is given,and its efficiency and security analyzed.Thismay serve as a reference for the design and implementation of group-signature scheme.

digital signature algorithm;group-signature;ElGamal signature algorithm

Special research project in shaanxi province department of education fund(2013JK1085);Weinan support funding for science and technology innovation(2013 JCYJ-6);Weinan vocational and technical college scientific research fund project funding(WZYY201324,WZYY201336)

date：2014-09-03;Revised date：2014-12-30

陜西省教育廳專項(xiàng)科研計(jì)劃項(xiàng)目資助(No.2013JK1085);渭南市科技創(chuàng)新扶持資金資助(No.2013JCYJ-6);渭南職業(yè)技術(shù)學(xué)院科研基金項(xiàng)目資助(No.WZYY201324,WZYY201336)

TP309.7

A

1002-0802(2015)02-0214-05

10.3969/j.issn.1002-0802.2015.02.020

2014-09-03;

2014-12-30

白永祥(1970—),男,碩士,副教授,主要研究方向?yàn)榫W(wǎng)絡(luò)與信息安全。

BAIYong-xiang,(1970-),male,M.Sci., associate professor,mainly engaged in network and information security.