張建中，謝君琴

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

改進(jìn)的抗合謀攻擊的門限簽名方案

張建中，謝君琴

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

1 引言

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

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

2 文獻(xiàn)[13]方案簡(jiǎn)介

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

2.1 初始化階段

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

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

2.2 部分簽名的生成與驗(yàn)證階段

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

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

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

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

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

2.3 門限簽名的生成與驗(yàn)證階段

群組簽名分為兩個(gè)部分進(jìn)行驗(yàn)證：

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

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

2.4 成員身份的追查階段

3 安全性分析

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

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

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

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

3.2 惡意t個(gè)成員的合謀攻擊

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

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

y=gF(0)modp，故

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

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

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

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

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

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

4 改進(jìn)的方案

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

4.1 初始化階段

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

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

①計(jì)算λ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ù)下式是否成立驗(yàn)證其正確性，若不成立則拒絕λi，j。

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

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

4.2 部分簽名的生成與驗(yàn)證階段

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

4.3 門限簽名的生成與驗(yàn)證階段

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

群組簽名分為三個(gè)部分進(jìn)行驗(yàn)證：

（1）判斷等式TT=llmodp是否成立，若成立則認(rèn)為簽名無效，否則進(jìn)行下一步驗(yàn)證。

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

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

4.4 改進(jìn)方案的安全性分析

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

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

5 結(jié)論

通過對(duì)原有方案進(jìn)行安全性分析，指出原方案存在一些安全隱患，即存在已知消息的外部成員偽造攻擊，惡意成員的合謀攻擊以及內(nèi)部成員的偽造攻擊。為了克服這些缺陷，本文給出了改進(jìn)方案，并對(duì)改進(jìn)方案的安全性進(jìn)行了分析，分析表明改進(jìn)方案不但能抵抗原方案中存在的偽造攻擊，而且能從真正意義上抵抗合謀攻擊，實(shí)現(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].計(jì)算機(jī)學(xué)報(bào)，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é)報(bào)，2007，42（4）：461-467.

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

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

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

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

[13]蔡永泉，張恩，賀敬陽.抗合謀攻擊的（t，n）門限簽名方案[J].北京工業(yè)大學(xué)學(xué)報(bào)，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ǔ)上，針對(duì)提出的攻擊給出了一種改進(jìn)方案；對(duì)改進(jìn)方案的安全性進(jìn)行了分析。結(jié)果表明：改進(jìn)方案不僅能從根本上抵抗合謀攻擊和偽造簽名攻擊，而且通過對(duì)消息恢復(fù)方程的應(yīng)用保護(hù)了簽名者的秘密信息和廣播數(shù)據(jù)，同時(shí)通過構(gòu)造安全的分布式密鑰生成協(xié)議保證了群公鑰的可計(jì)算性，因此比原方案具有更高的安全性。

門限簽名；合謀攻擊；偽造性；內(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.

國(guó)家自然科學(xué)基金（No.61173190）；陜西省自然科學(xué)基金計(jì)劃研究項(xiàng)目（No.2009JM8002，No.2010JQ8027）；陜西省教育廳科學(xué)研究計(jì)劃基金資助項(xiàng)目（No.2010JK829，No.2010JK398，No.12JK1003）；中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金資助（No.GK201002041）。

張建中（1960—），男，博士，教授，研究方向?yàn)樾畔踩c密碼學(xué)及認(rèn)證理論；謝君琴（1988—），通訊作者，女，碩士研究生，研究方向?yàn)槊艽a學(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