尚光龍，曾雪松

(信陽(yáng)職業(yè)技術(shù)學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,河南 信陽(yáng) 464000)

一個(gè)安全的門限群簽名方案

尚光龍，曾雪松

(信陽(yáng)職業(yè)技術(shù)學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,河南 信陽(yáng) 464000)

目的 針對(duì)門限群簽名中普遍存在的簽名參與者出示假秘鑰進(jìn)行內(nèi)部欺詐或內(nèi)外勾結(jié)欺詐問題，提出一個(gè)安全性增強(qiáng)的門限群簽名方案，并給出安全性論證和計(jì)算量分析。方法 根據(jù)RSA加密體制原理，可信中心TA生成RSA密碼體制相關(guān)參數(shù)，為每個(gè)群成員生成驗(yàn)證片斷和身份標(biāo)簽，同時(shí)利用大整數(shù)分解的困難性和強(qiáng)Hash函數(shù)的單向性，解決門限群簽名中可能存在的門限欺詐問題并改善方案性能；結(jié)果 依據(jù)大整數(shù)分解的困難性和強(qiáng)Hash函數(shù)的單向性，通過驗(yàn)證片段，解決了門限群簽名中可能存在的門限欺詐問題；通過引入成員標(biāo)簽，提高群成員加入和撤銷的效率，改善系統(tǒng)性能；依據(jù)Shamir秘密共享體制，解決簽名偽造問題；同時(shí)也解決了傳統(tǒng)意義上的群簽名需要滿足的抗合謀攻擊等安全問題；最后，對(duì)方案安全性和算法效率進(jìn)行了分析、計(jì)算。結(jié)論 經(jīng)分析論證表明，基于RSA密碼體制和Shamir門限機(jī)制，通過引入驗(yàn)證片斷和成員標(biāo)簽，提出的門限群簽名方案克服了傳統(tǒng)門限群簽名存在的門限欺詐問題，提高了門限群簽名的安全性，改善了方案性能，是一個(gè)符合門限機(jī)制、安全性增強(qiáng)的群簽名方案，具有一定的理論和應(yīng)用價(jià)值。

RSA公鑰密碼體制；門限機(jī)制；群簽名

0 引 言

門限密碼學(xué)發(fā)展至今，衍生出了眾多分支，門限群簽名作為其中的重要組成部分，一直得到學(xué)術(shù)界的廣泛關(guān)注。門限群簽名是引入門限機(jī)制[1]后的特殊群簽名[2-4]，自Desmedt和Frankel于1991年提出后一直得到人們的廣泛關(guān)注，學(xué)術(shù)界也提出了各種不同的簽名方案[5-13]。在數(shù)字簽名方案中，人們關(guān)注和研究的核心是簽名密鑰的管理問題，在門限群簽名方案中，簽名密鑰利用門限方案被分割成若干簽名子密鑰，當(dāng)至少t個(gè)簽名參與者利用分管的簽名子密鑰完成群簽名時(shí)，簽名驗(yàn)證者關(guān)心的是最終形成的簽名是否是n個(gè)簽名人中至少t個(gè)人員確實(shí)參與了簽名，即簽名參與者中是否出現(xiàn)欺詐問題。欺詐問題的表現(xiàn)有合謀攻擊、單個(gè)參與者出示假子密鑰進(jìn)行內(nèi)部欺詐或內(nèi)外勾結(jié)欺詐等。本文依據(jù)RSA加密機(jī)制，利用大整數(shù)分解的困難性和強(qiáng)Hash函數(shù)的單向性，進(jìn)行欺詐檢測(cè)，阻止了內(nèi)部簽名參與者或外部人員的簽名欺詐問題，并對(duì)算法的抗合謀攻擊性能、欺詐檢測(cè)性能進(jìn)行了分析，提出了一個(gè)安全性增強(qiáng)、具有可信中心的門限群簽名方案。

1 基于RSA的安全門限群簽名方案

本文根據(jù)RSA加密體制原理，解決了門限群簽名中可能存在的門限欺詐問題，提高了簽名方案的安全性。假定n個(gè)簽名成員構(gòu)成簽名群G={P1,P2,…,Pn}， 負(fù)責(zé)簽名的t個(gè)成員構(gòu)成群G′={P1,P2,…,Pt}， 為簽名群G的子群。PKI機(jī)制下的可信中心為TA，群G的管理員為簽名群中的特殊成員DC，負(fù)責(zé)簽名合成。

1.1 方案初始化

可信中心TA完成方案初始化工作。

(1)選擇參數(shù)：

①TA隨機(jī)選取2個(gè)大素?cái)?shù)p和q， 這里要求p和q均是安全的(其安全性要求為2511

②選擇2個(gè)參數(shù)e和d使得gcd(e,Φ(N))=1和ed≡(modΦ(N))， 其中Φ(N)=(p-1)(q-1)， 在公告板上公開e和Φ(N), 但把d作為秘密參數(shù)；

④選擇1個(gè)具有強(qiáng)穩(wěn)固性的Hash函數(shù)H；

⑥TA為群管理員生成密鑰對(duì)(k,y)， 其中私鑰k如步驟⑤中計(jì)算， 公鑰y=gkmodN。

(2)對(duì)任意群成員pi分配身份標(biāo)識(shí)為IDi， 并利用安全網(wǎng)絡(luò)發(fā)送給Pi； 為簽名參與者Pi生成私鑰xi=(gf(IDi))dmodN和公鑰yi=gf(IDi)modN； 同時(shí)為檢測(cè)簽名欺詐行為， TA為Pi分配驗(yàn)證片段νi。

對(duì)xi和νi， TA執(zhí)行如下運(yùn)算：

①計(jì)算νi=H(xi)dmodN

②通過安全網(wǎng)絡(luò)將xi和νi分配給Pi秘密保管。

(3)為提高群成員管理效率， TA為每個(gè)成員Pi生成身份標(biāo)簽(Label)(表1),并向全體有效群成員進(jìn)行廣播。身份標(biāo)簽格式如下：

表1 身份標(biāo)簽

當(dāng)Pi為有效成員時(shí)， 可信中心TA將給Tie分配一個(gè)較大的值； 當(dāng)Pi無(wú)效時(shí)，則TA給Tie一個(gè)具體的時(shí)間值。 身份標(biāo)簽IDi由TA實(shí)時(shí)維護(hù)； 當(dāng)簽名群成員出現(xiàn)退群或入群操作時(shí)，TA都要更新標(biāo)簽并通過網(wǎng)絡(luò)對(duì)所有成員進(jìn)行廣播，實(shí)時(shí)更新簽名群。

1.2 部分簽名的生成和驗(yàn)證

群簽名的合成和驗(yàn)證由合成者DC來(lái)完成。

若簽名組G′來(lái)完成對(duì)消息m的簽名， 則G′中每個(gè)成員Pi都執(zhí)行如下算法：

①將自己的IDi發(fā)送給群管理員；

②Pi選取隨即參數(shù)αi， 計(jì)算ri=αiemodN并進(jìn)行廣播；

③當(dāng)Pi從廣播收到ri后， 計(jì)算

R=∏rimodN

④Pi完成對(duì)M簽名

并將(ri,sigi)發(fā)送給DC。

DC通過以下操作來(lái)來(lái)驗(yàn)證部分簽名的合法性

合法性證明如下：

1.3 群簽名的生成和驗(yàn)證

在這一階段，DC合成并驗(yàn)證最終簽名。

對(duì)G′中任意成員Pi， 如果所有的(ri,sigi)都是有效簽名， 則DC生成消息m的群簽名(R,Sig,G′)， 其中

Sig=∏sigimodN

要驗(yàn)證對(duì)消息m的群簽名(R,Sig,G′)是否有效，驗(yàn)證公式如下：

Sige≡yH(m,R,G′)RmodN

群簽名合法性證明如下：

Sige≡(∏sigi)emodN

根據(jù)Lagrange插值公式，改寫為

Sige≡gf(0)H(m,R,G′)RmodN

≡yH(m,R,G′)RmodN

2 方案分析

以下對(duì)上述方案的安全性和性能進(jìn)行分析。

2.1 安全性分析

(1)欺詐檢測(cè)過程分析

對(duì)任意簽名人Pi， 根據(jù)驗(yàn)證片段分配算法， 如果有

νie≡H(xi)(modN)

則Pi不存在欺詐行為，否則存在欺詐行為。如果Pi篡改xi為xi*，則必須計(jì)算νi*， 使得νi*e≡H(xi*)(modN)成立， 但是如果沒有秘密參數(shù)d， 欺詐成功等于攻破RSA密碼體制； 如果欺詐者Pi改νi為νi*， 則必須計(jì)算xi*， 使得H(xi*)≡νi*e(modN)成立，由于Hash函數(shù)具有較好的單向穩(wěn)固性，這也是不可行的。

(2)抗合謀攻擊

假定簽名組中部分成員與群外非法人員進(jìn)行合謀攻擊，由于這些群成員無(wú)法重構(gòu)秘密多項(xiàng)式f(x)， 且群外人員沒有在TA處注冊(cè)，因此無(wú)法偽造簽名。

(3)欺詐檢測(cè)性能分析

定理1 方案中的欺詐檢測(cè)機(jī)制是完善的。

證明：本文中的期中檢測(cè)機(jī)制基于Shamir秘密共享體制，因此屬于完善的(t,n)門限秘密共享體制，在少于t個(gè)有效成員的情況下，簽名不可偽造。

定理2 欺詐者欺詐成功的難度等價(jià)于攻破RSA公鑰密碼體制和單向Hash函數(shù)。

證明：根據(jù)欺詐檢測(cè)過程可知，定理2是成立的(其證明過程見欺詐檢測(cè)過程分析)，在現(xiàn)有計(jì)算能力下，RSA公鑰密碼體制和單向Hash函數(shù)仍有較好的安全性和商密通用價(jià)值。

2.2 方案的計(jì)算量分析

假設(shè)乘法運(yùn)算用M來(lái)表示，Hash運(yùn)算用H來(lái)表示， 冪運(yùn)算用Exp來(lái)表示， 加法運(yùn)算用A來(lái)表示，Gcd表示計(jì)算最大公約數(shù)，本文中提出的算法計(jì)算量分析如下：

(1)參數(shù)初始化階段

在本階段，由于只是完成參數(shù)生成工作，主要由TA以離線方式完成。

步驟①采用1個(gè)乘法運(yùn)算(n=pq)、 2個(gè)加法運(yùn)算(p=2q′+1和q=2q′+1)， 計(jì)算量為1M+2A；

步驟②計(jì)算量為1Gcd+2M； 步驟⑤計(jì)算量為(t-1)(A+Exp)； 步驟⑥計(jì)算量為1 Exp。

因此， 在選擇參數(shù)階段TA的計(jì)算量累計(jì)為：

1M+2A+1Gcd+2M+(t-1)(A+Exp)+1Exp=3M+(t+1)A+1Gcd+tExp

TA計(jì)算每個(gè)Pi的簽名子密鑰xi=(gf(IDi))dmodn及公鑰yi=gf(IDi)modn并計(jì)算驗(yàn)證片段wi=H(xi)dmodn， 因此花費(fèi)的計(jì)算量依次為(t-1)(A+Exp)+2Exp，(t-1)(A+Exp)+1Exp，1H+1Exp，

累計(jì)為2(t-1)A+2(t+1)Exp+1H；

廣播成員標(biāo)簽不花費(fèi)計(jì)算量；

故方案初始化階段TA的計(jì)算量累計(jì)為3M+(t+1)A+1Gcd+tExp+2(t-1)A+2(t+1)Exp+1H=3M+3(t-1)A+1Gcd+(3t+2)Exp+1H。

(2)部分簽名的生成和驗(yàn)證階段計(jì)算量分析

每個(gè)成員Pi都計(jì)算ri=αiemodn， 因此計(jì)算量為tExp； 每個(gè)成員Pi都計(jì)算R=∏rimodn， 花費(fèi)的計(jì)算量為t(t-1)M， 生成部分簽名花費(fèi)的計(jì)算量為t(1H+1Exp+tM)； DC驗(yàn)證部分簽名花費(fèi)的計(jì)算量為1Exp+1H+1Exp+tM=2Exp+1H+tM；

所以本階段需要的總計(jì)算量為：(2t+2)Exp+2t2M+2H。

(3)群簽名的生成和驗(yàn)證階段的計(jì)算量分析

DC合成群簽名采用的計(jì)算量為2(t-1)M， 驗(yàn)證群簽名采取的計(jì)算量為2Exp+1H+M， 因此本階段共需要的計(jì)算量為(2t-1)M+2Exp+1H；

根據(jù)上述分析，本方案各階段計(jì)算量匯總見表2。

表2 各階段計(jì)算量匯總表

3 結(jié) 論

在門限群簽名方案中，群成員的簽名密鑰管理問題一直是學(xué)術(shù)界的研究熱點(diǎn)，特別是成員之間的欺詐問題。在門限群簽名方案中，簽名驗(yàn)證者關(guān)心的是最終形成的簽名是否是n個(gè)簽名人中至少t個(gè)人員確實(shí)參與了簽名，即簽名參與者中是否出現(xiàn)欺詐問題。欺詐問題的表現(xiàn)有合謀攻擊、單個(gè)參與者出示假子密鑰進(jìn)行內(nèi)部欺詐或內(nèi)外勾結(jié)欺詐等。本文基于RSA密碼體制和Hash函數(shù)的穩(wěn)固性理論，探討了門限群簽名的密鑰安全問題，提出了一個(gè)安全性增強(qiáng)的門限群簽名方案。在本方案中，基于Shamir秘密共享體制原理，對(duì)群成員簽名密鑰進(jìn)行欺詐檢測(cè)，解決了成員間的簽名欺詐問題；同時(shí)，也實(shí)現(xiàn)了對(duì)合謀攻擊等問題的克服；最后，對(duì)方案進(jìn)行了安全性分析和算法復(fù)雜度分析。結(jié)果表明，本方案是一個(gè)安全、可行的門限群簽名方案。

[1]SHAMIR A.How to share a secret[J].Communications ACM,1979,24(11):612-613.

[2]王海艷,王汝傳.群簽名方案之比較研究[J].計(jì)算機(jī)應(yīng)用研究,2005(10):93-95.

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

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

[5]張建中,王永峰,張藝林.基于RSA群簽名方案的安全性分析[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(22):121-123.

[6]楊柳,鐘誠(chéng),華蓓.基于P2P網(wǎng)絡(luò)的可驗(yàn)證門限群簽名方案[J].計(jì)算機(jī)應(yīng)用與軟件,2009,26(07):88-89.

[7]楊鏞,張建中,李哲峰.一個(gè)實(shí)用的動(dòng)態(tài)群簽名[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(32)：82-84.

[8]姜燕.基于RSA的群簽名方案的缺陷及改進(jìn)方案[J].計(jì)算機(jī)工程與設(shè)計(jì),2008，29(07)：1655-1657.

[9]劉文琦,魏蕾,楊建華.基于橢圓曲線密碼體制的(t,n)門限群簽名方案[J].大連理工大學(xué)學(xué)報(bào),2007,47(03):429-432.

[10]李海峰,劉云芳.移動(dòng)Ad Hoc網(wǎng)絡(luò)中應(yīng)用自認(rèn)證的(t,n)門限群簽名方案[J].北京聯(lián)合大學(xué)學(xué)報(bào),2006,20(03):19-22.

[11]王斌,潘皓東,李建華.一種安全的門限群簽名方案[J].上海交通大學(xué)學(xué)報(bào)，2002,36(09):1333-1336.

[12]甘元駒,黎群輝.基于因式分解的可證實(shí)的門限群簽名方案[J].鐵道學(xué)報(bào),2003,25(03):69-72.

[13]王明文,朱清新,卿利,等.無(wú)可信中心的門限RSA數(shù)字簽名體制[J].華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版),2006,34(06):33-35.

[責(zé)任編輯：關(guān)金玉 英文編輯：劉彥哲]

A Secure Threshold Group Signature Scheme

SHANG Guang-long,ZENG Xue-song

(Xinyang Vocational and Technical College,Xinyang,Henan,464000,China)

Objective Aiming at the problem of signature participants’ fraud in threshold group signature,this paper proposed a security enhanced threshold group signature scheme to solve this problem,and gave the security analysis and calculation.Methods Based on the intricate nature of factoring problem and the One-way Function,the TA generates the relevant parameters,and the verifying-share and identity tag for each participants.Results To detect the cheat between each participant,by making use of the difficulty of large integer factorization,this paper improved the security of the signature,introduced the concept of Label,solved the member’s addition and deletion in an efficient way,improved the performance of the system.In addition,it solved the problem of the conspiracy attack.At last,we addressed the security of the scheme and analyzed the algorithm.Conclusion Analysis shows that the scheme improved the security of the threshold group signature and the efficiency,which has certain theoretical and application value.

RSA public key cryptosystem;threshold mechanism;group signature

河南省科技廳重點(diǎn)科技攻關(guān)項(xiàng)目(142102210331)

尚光龍(1979-)，男，河南南陽(yáng)人，碩士研究生，講師，研究方向?yàn)樾畔踩?、密碼學(xué)。

TP 309

A

10.3969/j.issn.1673-1492.2017.07.002

來(lái)稿日期：2016-10-25