使用中國剩余定理的群簽名方案

黨佳莉,俞惠芳

(青海師范大學(xué)計(jì)算機(jī)學(xué)院,西寧810008)

使用中國剩余定理的群簽名方案

黨佳莉,俞惠芳

(青海師范大學(xué)計(jì)算機(jī)學(xué)院,西寧810008)

現(xiàn)有群簽名方案存在不能抵抗陷害攻擊和偽造攻擊的問題。為此,將中國剩余定理用于群簽名中,提出一種新的群簽名方案。利用中國剩余定理的數(shù)學(xué)特性,只需簡單計(jì)算就能將一些重要的秘密信息進(jìn)行整合,可以更好地保證成員私鑰和身份的隱密性,同時(shí),能夠較好地控制計(jì)算過程中數(shù)據(jù)的長度,從而簡化計(jì)算過程,在不改變其他合法群成員密鑰的情況下,實(shí)現(xiàn)群成員的加入和撤銷。分析結(jié)果表明,該方案具有匿名性、防偽造性、可跟蹤性、防聯(lián)合攻擊和防重放攻擊等優(yōu)點(diǎn)。

數(shù)字簽名;群簽名;中國剩余定理;有限域;離散對數(shù)

1 概述

數(shù)字簽名主要用來實(shí)現(xiàn)數(shù)據(jù)完整性和不可抵賴性。隨著計(jì)算機(jī)技術(shù)的普及和電子通信技術(shù)的發(fā)展,面對各種各樣的應(yīng)用背景,需要不同的簽名方案,因此,群簽名思想應(yīng)運(yùn)而生。群簽名是由文獻(xiàn)[1]提出的。后來,研究者們對此進(jìn)行了修改和完善。群簽名方案允許任何一個(gè)群成員代表整個(gè)群體對消息進(jìn)行簽名,在出現(xiàn)爭議時(shí),則由群管理員來確定簽名人的身份。同其他數(shù)字簽名一樣,群公鑰能夠?qū)θ汉灻M(jìn)行公開驗(yàn)證。

1995年,文獻(xiàn)[2]提出新的群簽名方案,并提出在群簽名方案中給群體增加新的群成員。2000年,文獻(xiàn)[3]提出在群簽名方案中可以撤銷群成員。

盡管文獻(xiàn)[2-3]方案是安全的,但在每次增加或撤銷一個(gè)成員時(shí)需要做大量的指數(shù)運(yùn)算,帶來額外的繁重開銷。近年來,人們又相繼提出基于RSA[4]、離散對數(shù)[5]、橢圓曲線[6]、雙線性對[7]等的群簽名以及無證書群簽名[8],使得群簽名方案逐漸多樣化。因?yàn)槿汉灻陔娮油镀盵9]、電子現(xiàn)金[10]等實(shí)際問題中具有廣泛的應(yīng)用,所以引起許多研究者的關(guān)注。

基于中國剩余定理的群簽名方案由文獻(xiàn)[11]于2004年提出,該方案不能防止陷害攻擊。后來雖然經(jīng)歷了一些改進(jìn),但仍存在不少問題或缺陷,如文獻(xiàn)[12]方案在防止偽造攻擊和防止陷害攻擊方面存在不足;文獻(xiàn)[13]提出的群簽名方案不能有效防止偽造攻擊和聯(lián)合攻擊。

以上述內(nèi)容為基礎(chǔ),本文提出一種使用中國剩余定理的群簽名方案。給出群簽名的定義、安全性要求以及中國剩余定理的介紹,并討論方案的安全性。

2 預(yù)備知識

2.1 群簽名

一個(gè)普通的群簽名方案[14]可以通過以下概率多項(xiàng)式算法來定義,具體描述如下:

(1)建立:群中心用于產(chǎn)生群公鑰、群成員及群管理員的密鑰的算法。

(2)加入:用戶和群管理員之間的使用戶成為群管理員的交互式協(xié)議。執(zhí)行該協(xié)議可以產(chǎn)生群成員的私鑰和成員證書,并使群管理員得到群成員的私有密鑰。

(3)撤銷:用來撤銷群成員的算法。

(4)簽名:通過簽名算法及群成員的簽名密鑰,對輸入的消息進(jìn)行簽名。

(5)驗(yàn)證:通過驗(yàn)證算法,確定對輸入消息的簽名是否有效。

(6)打開:給定簽名及群私鑰的條件下確定簽名者身份的算法。

2.2 群簽名的安全性

群簽名的安全性[11]從以下方面描述:

(1)匿名性:對于給定的群簽名,除群管理員外,任何人想要確定簽名者的身份在計(jì)算上是困難的。

(2)防偽造性:只有合法的群成員才能產(chǎn)生有效的群簽名。

(3)可跟蹤性:當(dāng)簽名出現(xiàn)爭議的時(shí)候,群管理員可以打開一個(gè)簽名,由此確定簽名者的身份,而簽名者不能阻止一個(gè)合法簽名的打開。

(4)防陷害攻擊:任何成員及群管理員都不能以其他成員的名義產(chǎn)生合法的群簽名。

(5)抗聯(lián)合攻擊:群組中的成員不能聯(lián)合產(chǎn)生一個(gè)合法的不可被跟蹤的群簽名。

(6)不可關(guān)聯(lián)性:除群管理員外,任何人想判斷2個(gè)或2個(gè)以上的消息是否由同一個(gè)成員產(chǎn)生是困難的。

2.3 中國剩余定理

設(shè)p1,p2,…,pk是k個(gè)兩兩互素的正整數(shù),則對任意的整數(shù)y1,y2,…,yk,同余式[11]:

一定有解,且解是唯一的。令:

P=p1p2…pk,P=piPi,i=1,2,…,k則同余式組的解可表示為:

其中,P′iPi≡1(modpi),i=1,2,…,k。

3 本文群簽名方案

3.1 系統(tǒng)的建立

已知安全參數(shù)k,群中心選擇2個(gè)大素?cái)?shù):p′和q′,滿足p=2p′+1,q=2q′+1,則p和q為安全素?cái)?shù),并計(jì)算n=pq。然后,群中心隨機(jī)選擇,計(jì)算y≡gx(modp)。接著,群中心定義一個(gè)抗碰撞的哈希函數(shù):h:{0,1}?→{0,1}k,(k=160 bit)。循環(huán)群和的生成元gp和gq,構(gòu)造如下同余方程組:

易知g的階為λ(n)=lcm(p-1,q-1),由g生成的群＜g＞是群中階數(shù)最大的循環(huán)子群。群中心根據(jù)中國剩余定理計(jì)算g并將其公開。

群中心將(x,p,g)作為群中心的私鑰,而y是群中心的公鑰。

假設(shè)系統(tǒng)中有k個(gè)群成員。利用中國剩余定理,能夠求出同余方程組c≡yi(modpi),i=1,2,…,k的解為:

其中,P,P′i,Pi如2.2節(jié)所述。將(n,y,g,c)作為群公鑰發(fā)布。

3.2 群成員的加入

假設(shè)Alice向群中心提出申請,想成為群中心的一個(gè)成員,則需要以下步驟:

(2)重新計(jì)算:

其中,新的P,P′i,Pi都可以由原來的P,P′i,Pi給出,即:

其中,P′k+1Pk+1≡1(modpi)。

(3)群中心重新發(fā)布新的c,然后將(IDk+1,yk+1)發(fā)送給群管理員。則Alice成為群中心的一個(gè)新成員,此時(shí)群中心其他有效成員的簽名密鑰并不發(fā)生改變,群公鑰中只有c發(fā)生改變,但群公鑰的個(gè)數(shù)并不改變。

3.3 群成員的撤銷

設(shè)群中心有k個(gè)成員,并且:

為了撤銷群中的成員Ui,群中心將yi改成另外的一個(gè)隨機(jī)數(shù)并且重新計(jì)算并發(fā)布新的c:

由以上的撤銷過程可以看出,要撤銷群中心的一個(gè)群成員,只需要改變c的值和進(jìn)行一些簡單的計(jì)算,由于P固定不變,c的長度也是不變的,因此整個(gè)群中心公鑰的長度也不變。對于其他合法的群成員,此時(shí),并不需要更新自身的簽名密鑰。因此,以上的撤銷過程,無論對群中心還是群成員都是簡單和高效的。

3.4 簽名的生成

設(shè)群成員Ui要對消息m簽名。選擇一個(gè)隨機(jī)數(shù),計(jì)算。群成員Ui利用私鑰xi對消息m簽名,計(jì)算:

其中,T為簽名的時(shí)間。于是,五元組(m,γi,si,pi,T)即為成員Ui對m的簽名。

3.5 簽名的驗(yàn)證

計(jì)算yi≡c(modpi),進(jìn)而由(IDi,yi)確定簽名者的身份。

4 安全性分析

4.1 防偽造攻擊分析

定理1 假設(shè)Alice是合法群成員,攻擊者截獲了pA,要偽造Alice的簽名(m,γA,sA,pA,T)在計(jì)算上是困難的。

證明:可以根據(jù)攻擊者的身份分為以下2種情況來進(jìn)行討論:

(1)攻擊者不是群成員

由于攻擊者截獲了pA,因此可以計(jì)算出yA≡c(bmodpA)。由于yA≡gxA(modpA),要求解xA等價(jià)于求解有限域上的離散對數(shù)問題,而這個(gè)問題是個(gè)難解問題。

(2)攻擊者是合法群成員

攻擊者利用自己的私鑰xB和截獲的pA,對消息m進(jìn)行簽名:

攻擊者偽造的簽名為(m,γB,sB,pA,T),驗(yàn)證者接收到簽名后計(jì)算:

并通過驗(yàn)證。

則yA≡yB≡c(modpA),即:

定理得證。

4.2 防陷害攻擊分析

定理2 假設(shè)Bob是合法群成員,攻擊者(群成員或者群管理員)即使截獲了pB想要以Bob的名義生成對消息m的合法簽名(m,γB,sB,pB,T)在計(jì)算上是困難的。

證明:利用反證法進(jìn)行證明。

假設(shè)攻擊者能夠以Bob的名義生成對消息m的合法簽名(m,γB,sB,pB,T)。

由于攻擊者截獲了pB,因此可以計(jì)算出yB≡c(modpB)。又因?yàn)?

要計(jì)算xB必須通過yB≡gxB(modpB)來計(jì)算,等價(jià)于求解有限域上的離散對數(shù)問題,因此,在計(jì)算上是困難的。

定理得證。

4.3 防聯(lián)合攻擊分析

定理3 假設(shè)群中共有k+1個(gè)成員,即使其中的k個(gè)成員聯(lián)合,想要求出第k+1個(gè)成員的密鑰(xk+1,yk+1,pk+1)在計(jì)算上是困難的。

證明:利用反證法進(jìn)行證明。

即已知yk+1和pk+1,求xk+1。攻擊者可以執(zhí)行以下操作:

(2)隨機(jī)選擇xi,yi,其中,yi≡gxi(modpi),i= 1,2,…,k。

(3)利用中國剩余定理計(jì)算:

(4)將c,pi,yi(i,j=1,2,…,k+1)和xj,j=1, 2,…,k作為算法φ的輸入,可以得到一組新的密鑰對(xk+1,yk+1,pk+1)。

因此,攻擊者通過以上步驟成功求解了有限域上的離散對數(shù)問題。

定理得證。

4.4 可跟蹤性

定理4假設(shè)群成員Uj可以對消息m進(jìn)行簽名,且不被群管理員跟蹤,則簽名不成立。

證明:利用反證法進(jìn)行證明。

假設(shè)Uj對消息m的簽名為(m,γj,sj,pj,T)而且簽名成立,則可以計(jì)算出群成員Uj的公鑰yj≡c(modpj)

由于在系統(tǒng)建立時(shí),群中心將每一個(gè)群成員的(IDi,yi),i=1,2,…,k發(fā)送給了群管理員,因此群管理員可以根據(jù)群公鑰yj追蹤到IDi,即可以追蹤到簽名的群成員。

定理得證。

4.5 防重放攻擊和匿名性分析

該方案加入時(shí)間標(biāo)志T,接受者收到簽名后,計(jì)算接收時(shí)間與簽名時(shí)間的時(shí)間差,如果超過規(guī)定的時(shí)間,則拒絕簽名。因此,該方案可以防止重放攻擊。

除群管理員以外,任何人根據(jù)簽名者的公共信息確定簽名者的身份在計(jì)算上都是困難的。因此,該方案可以保證群簽名的匿名性。

5 效率分析

通過表1對本文方案和文獻(xiàn)[11-13]進(jìn)行了指數(shù)運(yùn)算次數(shù)的比較,總運(yùn)算次數(shù)依次為4次、7次、8次和7次。

表1 4種方案運(yùn)行不同算法時(shí)指數(shù)運(yùn)算次數(shù)的比較

通過表2對本文方案和文獻(xiàn)[11-13]的性能進(jìn)行了比較,其中,“√”表示方案有此性能;“×”表示方案無此性能。

表2 不同方案的性能對比

分析表1和表2可知,本文方案的計(jì)算效率比文獻(xiàn)[11-13]更高,而且性能也更完善。

6 結(jié)束語

本文提出一種使用中國剩余定理的群簽名方案。該方案在不改變其他有效群成員密鑰的同時(shí),加入時(shí)間參數(shù),在防止重放攻擊方面具有明顯優(yōu)勢。分析結(jié)果表明,該方案可以安全高效地實(shí)現(xiàn)群成員的加入和撤銷,且效率較高。下一步將構(gòu)建使用中國剩余定理的群盲簽名方案。

[1] Chaum D,Heyst V E.Group Signatures[C]//Proceedings of EUROCRYPT’91.Berlin,Germany:Springer-Verlag, 1991:257-265.

[2] Chen L,Pedersen T.New Group Signature Schemes[C]// ProceedingsofEUROCRYPT’94.Berlin,Germany: Springer-Verlag,1995:171-181.

[3] Kim H,Lim J,Lee D.Efficient and Secure Member Deletion in Group Signature Schemes[C]//Proceedings of the 3rd International Conference on Information Security and Cryptology.Berlin,Germany:Springer-Verlag,2000:150-161.

[4] 李鳳銀,禹繼國,鞠宏偉.一種基于RSA的群簽名[J].計(jì)算機(jī)工程與設(shè)計(jì),2006,27(16):2955-2957.

[5] 徐光寶,張建中.一種基于離散對數(shù)的群簽名方案[J].計(jì)算機(jī)工程,2005,31(9):143-144.

[6] 謝 冬,李佳佳,沈忠華.一種新的基于橢圓曲線的門限群簽名方案[J].杭州師范大學(xué)學(xué)報(bào):自然科學(xué)版, 2013,12(1):57-60.

[7] 袁 艷.基于雙線性對的數(shù)字簽名的研究與設(shè)計(jì)[D].武漢:湖北工業(yè)大學(xué),2011.

[8] 陳 虎,宋如順.無證書群簽名方案[J].計(jì)算機(jī)工程, 2009,35(9):130-132.

[9] 喬匯東,胡 瑛.基于群簽名的電子投票方案[J].湖南工程學(xué)院學(xué)報(bào):自然科學(xué)版,2012,22(4):23-27.

[10] 王鳳和.群簽名及其在電子現(xiàn)金中的應(yīng)用研究[D].西安:西安電子科技大學(xué),2006.

[11] 陳澤文,張龍軍,王育民,等.一種基于中國剩余定理的群簽名方案[J].電子學(xué)報(bào),2004,32(7):1062-1065.

[12] 胡 斌,施榮華,婁 悅.一種改進(jìn)的基于中國剩余定理的群簽名方案[J].計(jì)算機(jī)工程與應(yīng)用,2006, 42(24):115-117.

[13] 李 俊,崔國華,劉志遠(yuǎn).一個(gè)群簽名方案的密碼學(xué)分析與改進(jìn)[J].電子學(xué)報(bào),2007,35(4):778-781.

[14] 鞠宏偉.3類新型的數(shù)字簽名方案研究[D].濟(jì)南:山東師范大學(xué),2005.

編輯 劉 冰

Group Signature Scheme Using Chinese Remainder Theorem

DANG Jiali,YU Huifang
(School of Computer,Qinghai Normal University,Xining 810008,China)

Some existing group signatures can not resist the defects of exculpability and unforgeability.In order to solve this problem,this paper applies the Chinese remainder theorem to group signature,and proposes a secure group signature scheme using Chinese remainder theorem.Using the mathematical properties of Chinese remainder theorem,only simple calculation to some important secret information integration can better ensure the privacy of the private key and identity. At the same time,this scheme can effectively control the length of the data in the process of calculation,thus,it simplifies the process of calculation.Under not changing the secret key of other group member,the group member can be added or revoked efficiently.Analysis results show that this scheme has anonymity,unforgeability,traceability,coalition-resistance and coalition-replay attacks.

digital signature;group signature;Chinese remainder theorem;finite field;discrete logarithm

黨佳莉,俞惠芳.使用中國剩余定理的群簽名方案[J].計(jì)算機(jī)工程,2015,41(2):113-116.

英文引用格式:Dang Jiali,Yu Huifang.Group Signature Scheme Using Chinese Remainder Theorem[J].Computer Engineering,2015,41(2):113-116.

1000-3428(2015)02-0113-04

:A

:TP309

10.3969/j.issn.1000-3428.2015.02.022

國家自然科學(xué)基金資助項(xiàng)目(61363080);教育部春暉計(jì)劃基金資助項(xiàng)目(Z2012094)。

黨佳莉(1988-),女,碩士研究生,主研方向:密碼學(xué),信息安全;俞惠芳,副教授、博士研究生。

2014-03-28

:2014-04-23E-mail:yuhuifang@qhnu.edu.cn