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

一種高效群簽名方案的設計與分析*

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

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

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

0 引 言

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

1 相關理論知識

1.1 基本概念

(1)數(shù)字簽名

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

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

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

(2)群簽名

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

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

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

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

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

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

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

1.2 ElGamal簽名方案

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

1.2.1 ElGamal密碼算法

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

(1)密鑰生成

①隨機選擇一個素數(shù)p;

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

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

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

1.2.2 ElGamal簽名過程

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

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

(2)簽名生成

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

(3)簽名驗證

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

2 方案設計

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

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

2.1 系統(tǒng)初始化

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

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

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

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

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

2.2 群成員加入

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

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

2.3 簽名

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

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

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

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

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

2.4 驗證

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

2.5 打開

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

3 安全性分析

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

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

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

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

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

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

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

2)工作效率高:在一般的群簽名方案中,群公鑰的長度是群成員個數(shù)n的線性函數(shù)。本簽名方案群簽名長度是固定不變的,不隨群中成員個數(shù)的變化而線性變化,且簽名長度比其它同類的都短,這是因為在我們的方案中簽名包含兩個時間表戳和三個群元素,所以整體群簽名效率較高。

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

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

4 結 語

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

參考文獻：

[1] 關振勝.公鑰基礎設施PKI及其應用[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] 劉傳領,范建華.RSA非對稱加密算法在數(shù)字簽名中的應用研究[J].通信技術,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)代密碼學理論與實踐[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.應用密碼學協(xié)議、算法與C源程序[M].第2版.吳世忠,祝世雄,張文政等譯.北京:機械工業(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] 胡向東,魏琴芳,胡蓉.應用密碼學[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] 鄧安文.密碼學-加密演算法[M].北京:中國水利出版社,2006:131-152. DENG An-wen.Cryptography-Encryption algorithm [M].Beijing:China Water Conservancy Press,2006: 131-152.

[9] 張文麗,趙峰.Hash簽名在電子商務中的應用[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

陜西省教育廳專項科研計劃項目資助(No.2013JK1085);渭南市科技創(chuàng)新扶持資金資助(No.2013JCYJ-6);渭南職業(yè)技術學院科研基金項目資助(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—),男,碩士,副教授,主要研究方向為網(wǎng)絡與信息安全。

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