一個安全的門限群簽名方案

尚光龍，曾雪松

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

一個安全的門限群簽名方案

尚光龍，曾雪松

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

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

RSA公鑰密碼體制；門限機制；群簽名

0 引 言

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

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

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

1.1 方案初始化

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

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

①TA隨機選取2個大素數(shù)p和q， 這里要求p和q均是安全的(其安全性要求為2511

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

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

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

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

對xi和νi， TA執(zhí)行如下運算：

①計算νi=H(xi)dmodN

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

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

表1 身份標(biāo)簽

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

1.2 部分簽名的生成和驗證

群簽名的合成和驗證由合成者DC來完成。

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

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

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

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

R=∏rimodN

④Pi完成對M簽名

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

DC通過以下操作來來驗證部分簽名的合法性

合法性證明如下：

1.3 群簽名的生成和驗證

在這一階段，DC合成并驗證最終簽名。

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

Sig=∏sigimodN

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

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 方案分析

以下對上述方案的安全性和性能進行分析。

2.1 安全性分析

(1)欺詐檢測過程分析

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

νie≡H(xi)(modN)

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

(2)抗合謀攻擊

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

(3)欺詐檢測性能分析

定理1 方案中的欺詐檢測機制是完善的。

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

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

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

2.2 方案的計算量分析

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

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

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

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

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

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

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

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

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

廣播成員標(biāo)簽不花費計算量；

故方案初始化階段TA的計算量累計為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)部分簽名的生成和驗證階段計算量分析

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

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

(3)群簽名的生成和驗證階段的計算量分析

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

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

表2 各階段計算量匯總表

3 結(jié) 論

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

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

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

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

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

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

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

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

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

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

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

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

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

[13]王明文,朱清新,卿利,等.無可信中心的門限RSA數(shù)字簽名體制[J].華中科技大學(xué)學(xué)報(自然科學(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

河南省科技廳重點科技攻關(guān)項目(142102210331)

尚光龍(1979-)，男，河南南陽人，碩士研究生，講師，研究方向為信息安全、密碼學(xué)。

TP 309

A

10.3969/j.issn.1673-1492.2017.07.002

來稿日期：2016-10-25