改進的抗合謀攻擊的門限簽名方案

張建中，謝君琴

陜西師范大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，西安 710062

改進的抗合謀攻擊的門限簽名方案

張建中，謝君琴

陜西師范大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，西安 710062

1 引言

門限簽名是門限密碼學(xué)的主要研究內(nèi)容之一，最初由Desmedt等[1-2]引進。由于門限簽名需要多方參與，與普通的數(shù)字簽名相比，其安全性和健壯性有了很大的提高。但是，自從Li等[3]在Crypto’93提出合謀攻擊的概念以來，如何抵抗合謀攻擊一直是門限簽名體制難以解決的問題。所謂合謀攻擊，是指大于等于門限值的子秘密持有者合謀，可以高概率獲取該群的秘密密鑰，進而偽造該群對任意消息簽名的攻擊[3]。

Harn[4]在1994年提出了一種基于E-Gamal簽名的不需要可信中心的門限簽名方案。2003年，王斌和李建華[5]指出Harn的方案無法抵抗合謀攻擊，并給出了一種改進方案，方案試圖采用聯(lián)合秘密共享技術(shù)[6]達到抵抗合謀攻擊的目的。但隨后，文獻[7-12]對王-李方案從不同角度進行分析改進，以使其能抵抗合謀攻擊，但上述文獻并未從本質(zhì)上抵抗合謀攻擊。于是文獻[13]提出了一種抗合謀攻擊的(t，n)門限簽名方案，但本文通過對其進行安全性分析發(fā)現(xiàn)，該方案不但無法抵抗合謀攻擊，而且極易遭受外部成員與簽名合成者勾結(jié)及內(nèi)部成員與簽名合成者勾結(jié)實施的偽造簽名攻擊。此外，該方案未提供對密鑰影子的驗證，因此無法防止秘密分發(fā)者的不誠實行為。為解決原方案中存在的問題，本文提出了一個改進方案。

2 文獻[13]方案簡介

文獻[13]所提出的方案分為四個階段；初始化階段、部分簽名的生成與驗證階段、門限簽名的生成與驗證階段、成員身份的追查階段。

2.1 初始化階段

群成員組成的集合設(shè)為U(|U|=n)，則U中所有成員共同選擇系統(tǒng)公共參數(shù)：安全大素數(shù)p和q以及Fp上的q階元素g。

（2）Ui在[1，q-1]選一個隨機數(shù)ki，將ki作為自己的私鑰，并計算出yi=gkimodp作為Ui的公鑰。其中，各個成員密鑰選定過程中，其各自公鑰必需滿足如下條件：任意t個成員公鑰之積lj=均不相等，然后構(gòu)造多項式

2.2 部分簽名的生成與驗證階段

如果群中任意t個成員組成集合S(|S|=t)，代表群組對消息m簽名，則其中每個成員Ui(i∈S)按照如下步驟生成部分簽名：

（1）選取隨機整數(shù)ti∈[1，q-1]，并計算將ti保密，而將Ti廣播給S中的其他成員。

（2）在t個成員都廣播過Ti后，各成員計算然后，Ui(i∈S)將自己的私鑰ki與秘密份額λi以及隨機數(shù)ti構(gòu)造部分簽名；si=λiCih(m)+kil-tiTmodq其中，為插值系數(shù)；h(m)為單向強的無碰撞Hash函數(shù)。

（3）成員Ui發(fā)送部分簽名(m，Ti，si，i)給門限簽名合成者DC（可由S中任何一個成員充當），其中i為序號，用于確定成員的公鑰，ri與Ci。

（4）DC根據(jù)成員廣播的數(shù)據(jù)，通過驗證是否成立判斷部分簽名的合法性。

2.3 門限簽名的生成與驗證階段

群組簽名分為兩個部分進行驗證：

（1）簽名接受者通過驗證yh(m)ll≡gsTTmodp是否成立來判斷接收到的簽名是否為指定群組的簽名。

（2）簽名接受者通過驗證D(l)≡0modp是否成立來判斷接收到的簽名是否為群組內(nèi)的合法簽名。

2.4 成員身份的追查階段

3 安全性分析

文獻[13]指出此方案可以在真正意義上抵抗合謀攻擊的安全性結(jié)論。但本文通過分析發(fā)現(xiàn)，惡意的外部成員或內(nèi)部成員當與簽名合成者勾結(jié)時可偽造部分簽名甚至門限簽名。

3.1 已知消息的外部成員偽造攻擊

若攻擊者獲得該群體對消息m的一個有效簽名(m，s，T，l)，則可對任意消息m′偽造一個部分簽名攻擊過程如下：

（1）攻擊者從簽名獲得t個人的公鑰之積l。

3.2 惡意t個成員的合謀攻擊

因為成員公鑰在群內(nèi)公布，惡意t個成員合謀可偽造群內(nèi)任意t個成員對消息m′的門限簽名，具體步驟如下：

（1）惡意t個成員利用插值多項式可恢復(fù)群私鑰F(0)。（2）獲得成員Ui的公鑰yi(i=1，2，…，t)，選擇計算則消息m′的門限簽名為(m′，s′，T′，l)。

y=gF(0)modp，故

3.3 內(nèi)部單個成員的偽造攻擊

假設(shè)U1想讓Ui(i=2，3，…，t)與他合作對消息m′進行簽名，Ui拒絕，但同意對m簽名，則攻擊過程如下：

（1）Ui(i=2，3，…，t)，隨機選取ki，ti∈[1，q-1]，并計算，將yi，Ti廣播給S中成員。

（2）U1等待，直到收到所有yi，Ti，然后選擇t1，k1∈[1，q-1]：

②計算d=h(m)h(m′)modp，T′=Tdmodp，l′=ldmodp。

（3）U1最終可偽造消息m′的門限簽名為(m′，s′，T′，l′)，且可通過驗證方程。

4 改進的方案

方案由初始化階段、部分簽名的生成和驗證階段、門限簽名的生成和驗證階段三部分構(gòu)成，具體分析了改進方案安全性。

4.1 初始化階段

設(shè)U(|U|=n)為群成員組成的集合，U中所有成員共同選擇系統(tǒng)公開參數(shù)：p，q為安全的大素數(shù)（其中q|p）；g為Fp中的階為q的元素。

（1）每個成員Ui隨機選取作為自己的唯一標識號并公布，同時根據(jù)事先確定的門限值t，隨機選定一個t-1次多項式，并按下述方式將fi(xj)在n個成員中分發(fā)：

①計算λi，j=fi(xj)modq，將其秘密分發(fā)給成員Uj(j= 1，2，…，n，j≠i)，Ui自己保留λi，i。

③成員Uj(j=1，2，…，n，j≠i)收到λi，j后，根據(jù)下式是否成立驗證其正確性，若不成立則拒絕λi，j。

（2）各成員Ui計算出秘密份額然后定義，也通過廣播方式發(fā)送給其他成員。

（3）Ui在[1，q-1]選一個隨機數(shù)ki，將ki作為自己的私鑰，并計算出作為Ui的公鑰。其中，各個成員密鑰選定過程中，其各自公鑰必需滿足如下條件：任意t個成員公鑰之積

4.2 部分簽名的生成與驗證階段

（4）成員Ui發(fā)送部分簽名(m，Ti，si，i)給門限簽名合成者DC（可由S中任何一個成員充當），其中i為序號，用于確定成員的公鑰、ri與Ci。

4.3 門限簽名的生成與驗證階段

若DC收到了t份部分簽名(m，Ti，si，i)，則計算若TT=ll則拒絕合成，否則計算，則最終的群組簽名即為(m，s，T，l)。

群組簽名分為三個部分進行驗證：

（1）判斷等式TT=llmodp是否成立，若成立則認為簽名無效，否則進行下一步驗證。

（2）簽名接受者通過驗證yh(m)ll≡gsTTmodp是否成立來判斷接收到的簽名是否為指定群組的簽名。

（3）簽名接受者通過驗證D(l)≡0modp是否成立來判斷接收到的簽名是否為群組內(nèi)的合法簽名。

4.4 改進方案的安全性分析

改進方案不但保持了原方案部分簽名和門限簽名驗證等式的正確性，實現(xiàn)了成員的身份追查，而且還可抵抗文中提出的三種攻擊。

（3）改進方案對簽名合成者及簽名驗證者加限制條件使TT≠llmodp，從而可以抵抗3.2節(jié)中提出的合謀攻擊。另外，對簽名方程的改進即用h(m，T)代替h(m)可以抵抗3.3節(jié)中的攻擊。因為若一個不誠實的簽名者想通過上述方法來偽造任何消息的一個門限簽名，他必須計算一個值T′，使得下列兩個方程滿足：d=h(m,T)-1h(m,T′)modp,T′=Tdmodp。但是，使這兩個方程同時成立是較困難的，因為假設(shè)h(.)是一個單向無碰撞的Hash函數(shù)，即找到一個新的消息m′使對任何d滿足d=h(m，T)-1h(Tdmodp，m′)modp是不可行的，其中T，m給定。

5 結(jié)論

通過對原有方案進行安全性分析，指出原方案存在一些安全隱患，即存在已知消息的外部成員偽造攻擊，惡意成員的合謀攻擊以及內(nèi)部成員的偽造攻擊。為了克服這些缺陷，本文給出了改進方案，并對改進方案的安全性進行了分析，分析表明改進方案不但能抵抗原方案中存在的偽造攻擊，而且能從真正意義上抵抗合謀攻擊，實現(xiàn)成員的身份追查，因此具有更高的安全性。

[1]Desmedt Y.Society and group oriented cryptography：a new concept[C]//Advances in Cryptology-Crypto’87 Proceedings. Berlin：Springer-Verlag，1988：120-127.

[2]Desmedt Y，F(xiàn)rankel Y.Shared generation of authenticators and signature[C]//Advances in Cryptology-Crypto’91 Proceedings. Berlin：Springer-Verlag，1991：457-469.

[3]Li C，Hwang T，Lee N.Remark on the threshold RSA signature scheme[C]//Advances in Crypto’93 Proceedings.Berlin：Springer-Verlag，1994：413-420.

[4]Harn L.Group-oriented（t，n）signature scheme and digital multisignature[J].IEE Proceedings of Computers and Digital Techniques，1994，141（5）：307-311.

[5]王斌，李建華.無可信中心的（t，n）門限簽名方案[J].計算機學(xué)報，2003，26（11）：1581-1584.

[6]Rosaio G，Stanislaw J，Hugo K.Robust threshold DSS signatures[J].Information and Computation，2001，164（1）：54-84.

[7]Xie Qi，Yu Xiuyuan.A new（t，n）threshold signature scheme withstanding the conspiracy attack[J].Wuhan University Journal of Natural Sciences，2005，10（1）：107-110.

[8]張文芳，何大可，王宏霞，等.具有可追查性的抗合謀攻擊的（t，n）門限簽名方案[J].西南交通大學(xué)學(xué)報，2007，42（4）：461-467.

[9]羅敏，李璇，施榮華.一類（t，n）門限群簽名方案的安全性分析[J].計算機工程與應(yīng)用，2005，41（5）：44-45.

[10]郭麗峰，程相國.一個無可信中心的（t，n）門限簽名方案的安全性分析[J].計算機學(xué)報，2006，29（11）：2013-2016.

[11]高煒，于曉東.對一個無可信中心的（t，n）門限簽名方案的改進[J].計算機學(xué)報，2010，46（1）：84-86.

[12]徐光寶，姜東煥.具有特權(quán)者的門限簽名方案[J].計算機工程與應(yīng)用，2011，47（9）：83-85.

[13]蔡永泉，張恩，賀敬陽.抗合謀攻擊的（t，n）門限簽名方案[J].北京工業(yè)大學(xué)學(xué)報，2011，37（8）：1231-1234.

ZHANG Jianzhong,XIE Junqin

College of Mathematics and Information Science,Shaanxi Normal University,Xi’an 710062,China

An improved threshold signature scheme is proposed to overcome the weakness of Cai et al’s scheme.The security of this scheme is analyzed.The results show that the improved scheme can not only resist conspiracy attacks and forgery attacks essentially,but also protect the personal broadcasted information with applying message recovery equation.In addition,it can realize the computing ability of group’s public key by constructing a secure distributed key generation protocol.As a result,the improved scheme is securer than the former schemes.

threshold signature;conspiracy attack;forgery ability;inside attack

在分析蔡永泉等的抗合謀攻擊的(t，n)門限簽名方案安全缺陷的基礎(chǔ)上，針對提出的攻擊給出了一種改進方案；對改進方案的安全性進行了分析。結(jié)果表明：改進方案不僅能從根本上抵抗合謀攻擊和偽造簽名攻擊，而且通過對消息恢復(fù)方程的應(yīng)用保護了簽名者的秘密信息和廣播數(shù)據(jù)，同時通過構(gòu)造安全的分布式密鑰生成協(xié)議保證了群公鑰的可計算性，因此比原方案具有更高的安全性。

門限簽名；合謀攻擊；偽造性；內(nèi)部攻擊

A

TP309.2

10.3778/j.issn.1002-8331.1205-0088

ZHANG Jianzhong,XIE Junqin.Improved threshold signature scheme for resisting conspiracy attack.Computer Engineering and Applications,2013,49（18）：52-55.

國家自然科學(xué)基金（No.61173190）；陜西省自然科學(xué)基金計劃研究項目（No.2009JM8002，No.2010JQ8027）；陜西省教育廳科學(xué)研究計劃基金資助項目（No.2010JK829，No.2010JK398，No.12JK1003）；中央高?；究蒲袠I(yè)務(wù)費專項資金資助（No.GK201002041）。

張建中（1960—），男，博士，教授，研究方向為信息安全與密碼學(xué)及認證理論；謝君琴（1988—），通訊作者，女，碩士研究生，研究方向為密碼學(xué)。E-mail：jzzhang@snnu.edu.cn

2012-05-15

2012-06-28

1002-8331（2013）18-0052-04

CNKI出版日期：2012-08-16 http://www.cnki.net/kcms/detail/11.2127.TP.20120816.1045.004.html