基于分組秘密共享的,n門限群題名體制

基于分組秘密共享的,n門限群題名體制

1追蹤簽名者身份門限密碼學(xué)是門限密碼學(xué)的一個(gè)重要分支，門限數(shù)字簽名是門限密碼學(xué)的一個(gè)重要分支。門限組簽名系統(tǒng)是t或更多成員的t合作創(chuàng)造的有效簽名系統(tǒng)。自從Desmedt和Frankel于1991年首次提出(t,n)門限群簽名以后,門限數(shù)字簽名得到了廣泛的研究,提出了各種各樣的(t,n)門限群簽名方案.現(xiàn)有的門限群簽名方案按不同的分類方法一般有以下幾種類型:(1)按數(shù)學(xué)基礎(chǔ)可分為:利用RSA設(shè)計(jì)的或基于離散對(duì)數(shù)設(shè)計(jì)的;(2)按是否可以追查簽名者身份可分為:可以追查簽名者身份的或者不能追查簽名者身份的;(3)按系統(tǒng)參數(shù)的生成可分為:需要可信中心參與的或者不需要有可信中心參與的等.但不管是那種類型,它們都是基于群秘密共享方案的,即群密鑰是群中任意t或更多個(gè)成員共享的秘密,這樣群中t或更多個(gè)成員合謀就可以恢復(fù)秘密多項(xiàng)式,從而可以獲得群密鑰,借助公開(kāi)的身份,他們可以恢復(fù)群中所有成員的密鑰,從而任何一組人可以合謀假冒另一組成員產(chǎn)生代表群的有效簽名和偽造身份追查方程.文獻(xiàn)進(jìn)一步指出了性能良好的門限群簽名應(yīng)該具有的特點(diǎn):群簽名特性、門限特性、簽名驗(yàn)證的簡(jiǎn)單性和匿名性、身份的可追查性、系統(tǒng)的強(qiáng)壯性和穩(wěn)定性.根據(jù)這些特點(diǎn)衡量已有的(t,n)門限群簽名體制,都存在一些弱點(diǎn),所以設(shè)計(jì)出性能良好的(t,n)門限群簽名體制被認(rèn)為是open問(wèn)題.本文給出了一種新的適用于(t,n)門限群簽名的秘密共享方案稱為分組秘密共享方案,并基于分組秘密共享方案設(shè)計(jì)了一類安全的可追查簽名者身份的每次只有t個(gè)人合作簽名的(若有多于t個(gè)人想簽名,只需其中的t個(gè)人簽名即可)方案.(t,n)門限群簽名體制,部分成員合謀無(wú)法獲得任何系統(tǒng)秘密參數(shù),從而可以抵抗合謀攻擊.由于實(shí)際應(yīng)用中n和t往往比較小,如銀行的幾個(gè)部門聯(lián)合對(duì)支票簽名時(shí),能夠代表銀行簽名的部門數(shù)和參與簽名的部門數(shù)并不多,所以該方案對(duì)n和t比較小的情形尤其有效.2生成代表群簽名本節(jié)介紹一種新的適用于(t,n)門限群簽名的分組秘密共享方案,該方案由可信中心預(yù)先設(shè)計(jì)好.分組秘密共享方案的基本思想是:取兩個(gè)大素?cái)?shù)p和q,滿足q|p-1,g是GF(p)中階為q的生成元.群中n個(gè)成員中的任意t個(gè)成員共享一個(gè)秘密fj(0)modq(j=1,2,…,Ctntn),而群秘密是所有Ctntn組共享秘密的和f(0)=Ctn∑j=1∑j=1Ctnfj(0)modq.為了能使任何t個(gè)成員組成的小組(不妨設(shè)他們的共享秘密為fj(0)modq,對(duì)應(yīng)的公鑰為Yj=gfj(0)modp)能夠生成代表群的簽名,可信中心還應(yīng)該計(jì)算ˉfj(0)=f(0)-fj(0)(modq)(ˉYj=gˉfj(0)modp)fj(0)ˉˉˉˉˉˉˉ=f(0)?fj(0)(modq)(Yˉˉˉj=gfj(0)ˉˉˉˉˉˉˉˉmodp),并任選sj,計(jì)算Rj=gsjmodp,從ˉfj(0)=sjRj+Aj(modq)fj(0)ˉˉˉˉˉˉˉ=sjRj+Aj(modq)中解得Aj,然后把(Rj,Aj)給該小組,則該小組可以利用這些信息生成代表群的簽名.系統(tǒng)參數(shù)的選取要求t或更多個(gè)成員的合謀無(wú)法從自己的共享秘密、公開(kāi)的群公鑰、(Rj,Aj)和每個(gè)成員的公鑰中獲取系統(tǒng)秘密參數(shù).可信中心可以按下面的方案選取適當(dāng)?shù)膮?shù).首先任取t對(duì)不同的數(shù)(IDi∈RZq,xi∈RZq)(i=1,2,…,t),分別作為t個(gè)成員的身份和密鑰,利用拉格朗日插值定理構(gòu)造多項(xiàng)式f1(x)=t-1∑i=0∑i=0t?1b1ixi(modq),同時(shí)檢查是否有f1(0)≠0,否則重新選擇某個(gè)IDi或xi,這樣得到t個(gè)成員的共享秘密f1(0);然后再取不滿足多項(xiàng)式f1(x)的第t+1對(duì)不同的數(shù)(IDt+1∈RZq,xt+1∈RZq),與前面的任意t-1對(duì)數(shù)由拉格朗日插值定理構(gòu)造t個(gè)多項(xiàng)式fj(x)=t-1∑i=0bjixi∑i=0t?1bjixi(modq)(j=2,3,…,t+1),滿足所有的共享秘密不等于零且兩兩不等,任意多個(gè)共享秘密的和模q不等于零.按照此法可以取到n對(duì)不同的數(shù)(IDi∈RZq,xi∈RZq)(i=1,2,…,n),構(gòu)造Ctn個(gè)多項(xiàng)式fj(x)=t-1∑i=0bjixi(modq)(j=1,2,…,Ctn),則群秘密多項(xiàng)式為f(x)=Ctn∑j=1fj(x)(modq),群密鑰為f(0)=Ctn∑j=1fj(0)modq,群公鑰為y=gf(0)modp.IDi和xi為群中每個(gè)成員Ui的身份和密鑰,其對(duì)應(yīng)的公鑰為yi=gximodp(i=1,2,…,n).3門限群簽名體制這一節(jié)我們利用分組秘密共享方案構(gòu)造了一類安全的(t,n)門限群簽名體制,它由系統(tǒng)初始化、個(gè)體簽名的生成、個(gè)體簽名的驗(yàn)證和(t,n)門限群簽名的生成、(t,n)門限群簽名的驗(yàn)證四部分組成,設(shè)群中n個(gè)成員為Ui(i=1,2,…,n).3.1不同特征的密鑰的群秘密,引起群中成員的身份和密鑰,計(jì)算群中的公鑰以及群的公鑰改進(jìn)由可信中心按照分組秘密共享方案產(chǎn)生以下參數(shù):1.取兩個(gè)大素?cái)?shù)p和q,滿足q|p-1,g是GF(p)中階為q的生成元,H()是單向抗碰撞Hash函數(shù).2.選取n對(duì)不同的數(shù)(IDi∈RZq,xi∈RZq)(i=1,2,…,n)為群中成員的身份和密鑰,構(gòu)造群秘密多項(xiàng)式f(x)=Ctn∑j=1fj(x)(modq),則群密鑰為f(0)=Ctn∑j=1fj(0)modq,群公鑰為y=gf(0)modp.3.計(jì)算群中每個(gè)成員的公鑰yi=gximodp(i=1,2,…,n),并計(jì)算Ctn組的密鑰fj(0),對(duì)應(yīng)的ˉfj(0)以及相應(yīng)的(Rj,Aj)(j=1,2,…,Ctn).4.可信中心把密鑰xi密送給每個(gè)成員,在只有指定的秘書(DC)可以查閱的公告欄中公布(yi,(SBj,(Rj,Aj)),IDi),并在任何人可以查閱的公告欄中公布(p,q,g,H(),y)(i=1,2,…,n,j=1,2,…,Ctn),其中SBj為第j組成員的身份.3.2個(gè)人信息和簽名消息設(shè)m是被簽名的消息.不失一般性,不妨設(shè)參加(t,n)群簽名的第j組人為(U1,U2,…,Ut),他們一起執(zhí)行下列步驟完成個(gè)體簽名.1.每個(gè)Ui任取ki∈RZq,并計(jì)算ri=gkimodp,并把ri廣播給其他簽名人.2.每個(gè)Ui計(jì)算r=t∏i=1rimodp,并解下列關(guān)于ai的同余方程:xit∏j=1,j≠i-ΙDjΙDi-ΙDj=(r+Η(m?r?RRjjmodp))ki+ai(modq)(1)得到個(gè)人簽名消息(ri,ai).3.每個(gè)Ui把他的個(gè)人簽名消息((ri,ai),IDi)發(fā)送給DC.3.3門限群簽名的計(jì)算DC首先計(jì)算r=t∏i=1rimodp,c=H(m,r,RRjjmodp),然后利用下列方程來(lái)驗(yàn)證個(gè)體簽名的合法性:yt∏j=1,j≠i-ΙDjΙDi-ΙDji=rr+cigai(modp)(i=1,2,?,t)(2)若方程成立則計(jì)算a=t∑i=1ai+Aj(modq),記R=Rj,得到(t,n)門限群簽名(R,a,r).定理1.個(gè)體簽名的正確性可以通過(guò)方程(2)驗(yàn)證.證明.記c=H(m,r,RRjjmodp),由簽名的過(guò)程可知:yt∏j=1,j≠i-ΙDjΙDi-ΙDji=gxit∏j=1,j≠i-ΙDjΙDi-ΙDj=g(r+c)ki+ai=rr+cigai(modp).所以個(gè)體簽名滿足方程(2).證畢.3.4群簽名的驗(yàn)證(t,n)門限群簽名的驗(yàn)證方程為Η(m,r,RRmodp)=Η(m?r?yrr+Η(m,r,RRmodp)ga(modp))(3)定理2.(t,n)門限群簽名的正確性可以通過(guò)方程(3)驗(yàn)證.證明.記c=H(m,r,RRmodp),由簽名的過(guò)程可知:rr+cgaRR=g(r+c)t∑i=1ki+t∑i=1aigAjRR=g(r+c)t∑i=1ki+t∑i=1aiˉYj=gt∑i=1xit∏j=1,j≠i-ΙDjΙDi-ΙDjˉYj=YjˉYj=YjCtn∏i=1,i≠jYi=y(modp).所以群簽名滿足方程(3).證畢.4安全分析4.1惡意攻擊(i)惡意攻擊者無(wú)法通過(guò)偽造個(gè)人簽名獲得群簽名若惡意攻擊者知道ki和xi,則可以偽造個(gè)體簽名消息(ri,ai),必能通過(guò)式(2)的驗(yàn)證,但是從ri和yi中求出ki和xi是離散對(duì)數(shù)問(wèn)題;若惡意攻擊者根據(jù)個(gè)體簽名消息直接解方程(1)獲取ki和xi也是困難的,這是由于方程的三項(xiàng)中只知道其中的一項(xiàng)ai,所以該方程是不可解的;下面討論惡意攻擊者無(wú)法利用替換攻擊偽造滿足式(2)的個(gè)體簽名.設(shè)ri=yuiigvi,由式(2)可得下列同余方程組:{vi(r+c)+ai=0(modq)ui(r+c)=t∏j=1,j≠i-ΙDjΙDi-ΙDj(modq).由于r=t∏i=1rimodp,c=H(m,r,RRjjmodp),所以直接從上面的同余方程組獲得(ui,vi)是困難的,因?yàn)樗媾R解離散對(duì)數(shù)問(wèn)題,而且H()是單向抗碰撞Hash函數(shù).若任選(ui,vi)能滿足上述同余方程組等價(jià)于找到了安全單向函數(shù)H()的碰撞點(diǎn),所以是不可能的,偽造失敗.(ii)惡意攻擊者無(wú)法通過(guò)群簽名驗(yàn)證方程偽造群簽名惡意攻擊者直接通過(guò)群簽名驗(yàn)證方程偽造群簽名是困難的,因?yàn)镠()是單向抗碰撞Hash函數(shù).下面討論惡意攻擊者利用替換攻擊法對(duì)本方案的攻擊無(wú)效.情形1.惡意攻擊者任取Y,則ˉY=yY-1,他能得到ˉY=RRgAmodp或ˉY=RRmodp嗎?(1)惡意攻擊者任取α,計(jì)算Y=gαmodp,他無(wú)法找到滿足ˉY=RRgAmodp(這里R=gsmodp)的s和A,因?yàn)楣粽卟恢罎M足ˉY=gˉαmodp的ˉα,從而無(wú)法從方程ˉα=sR+A中求得s和A.另一方面,若任取s,則R可求,從ˉY=RRgAmodp可求得gA,但無(wú)法求得A因?yàn)檫@是解離散對(duì)數(shù)問(wèn)題.設(shè)R=ˉYugvmodp,則可得到同余方程組:{uR=1(modq)?vR+A=0(modq).顯然,解上面的同余方程組獲得(u,v)是困難的,因?yàn)檫@是離散對(duì)數(shù)問(wèn)題.(2)同理可證,惡意攻擊者無(wú)法得到ˉY=RRmodp.情形2.記c=H(m,r,RRmodp),惡意攻擊者能偽造滿足rr+cgaRR=y(modp)的群簽名(R,a,r)嗎?同情形1的證明方法,設(shè)R=ywrugvmodp,或r=ywRugvmodp,或R=yˉugˉvmodp?r=yugvmodp,這三種攻擊情況對(duì)本方案無(wú)效.4.2性質(zhì)上的密鑰如果t或更多個(gè)成員合謀,可以獲取他們自己共享的密鑰,根據(jù)群秘密多項(xiàng)式的構(gòu)造過(guò)程可知,他們無(wú)法獲知其他成員的密鑰和其他小組共享的秘密,也無(wú)法獲知群密鑰.所以群中t或更多個(gè)成員的合謀無(wú)法獲取任何有效的系統(tǒng)參數(shù),從而他們無(wú)法假冒其他小組生成有效的群簽名.4.3群公鑰若有某個(gè)成員被刪除,則可信中心只需刪除與該成員有關(guān)的一切數(shù)據(jù),如在公告欄中刪除該成員的身份、公鑰和有該成員參加的所有小組的(SBj,(Rj,Aj)),更新群密鑰為ˉf(0)=Ctn-1∑j=1fj(0)modq,群公鑰為y=gf(0)modp,其余參數(shù)不變.由于更新了群密鑰,所以即使被刪除的成員達(dá)到門限值對(duì)系統(tǒng)也無(wú)威脅;同時(shí)根據(jù)4.1節(jié)的分析,被刪除成員與群中成員的合謀對(duì)系統(tǒng)也沒(méi)有威脅.若有新成員加入,利用群秘密多項(xiàng)式的構(gòu)造方法,可信中心為他選擇身份IDn+1和密鑰xn+1,計(jì)算公鑰yn+1,同時(shí)計(jì)算他可能參與的Ct-1n個(gè)秘密多項(xiàng)式,在公告欄中增加Ct-1n個(gè)(SBj,(Rj,Aj)),再增加他的身份IDn+1、公鑰yn+1,更新群公鑰y,其余參數(shù)不變.4.4可信中心查簽方案2:u3000方法簽名驗(yàn)證者只需利用群公鑰驗(yàn)證群簽名,所以不清楚具體是哪些人參與了簽名,具有簽名驗(yàn)證的匿名性.如果事后發(fā)生糾紛,本方案可以追查簽名小組,從而可知哪些成員參加了簽名.可信中心知道每個(gè)簽名小組的公鑰Yj和ˉYj=R