梅伟锋，沈忠华

(杭州师范大学理学院，浙江 杭州 310036)

随着信息化技术不断深入和互联网的迅速发展，信息安全也越来越重要.数字签名技术是信息安全理论与技术的基础和重要保证之一.然而，在数字签名中，有时候需要由集体而非个人进行签名.门限密码由Shamir[1]于1979年首次提出，目前主要涉及门限秘密共享、门限签名、 门限加/解密、门限密钥托管等研究方向[2].1987年，Desmedt[3]提出了基于群组与群组之间的安全通信的面向群组的密码系统，该系统能够被用于门限签名.1992年，Desmedt等[4]提出了基于RSA和秘密共享的面向群组的(t，n)门限数字签名方案，之后，Li等[5]指出t个或者更多的恶意参与者能形成合谋攻击,从而得到系统的密钥进而伪造签名.

现如今，如何设计具有合谋攻击免疫性的门限签名方案成为一个研究热点.文献[6]中的门限签名方案存在不能抗合谋攻击的缺陷，而文献[7-9]中的方案则不满足身份可追查性.对于以上问题，考虑到椭圆曲线离散对数的难解性，本文提出一个基于椭圆曲线的门限签名方案，它具有抗合谋攻击和可追查性.接下来描述此方案，然后对方案的安全性和可行性进行分析，最后给出一个结论.

1 门限签名方案

假设系统有一个可信任的秘密分发中心(shared distribution center,SDC)，本方案的安全性是基于椭圆曲线的难解性.SDC负责群私钥、群公钥以及其他系统参数的选取.

1.1 系统初始化

不失一般性，假设一个群体中有w个成员，用集合U=(P1,P2,…,Pw)来表示该群体进行签名.B⊂U表示集合U中参与签名的t个成员的子集，不失一般性可假定B=(P1,P2,…Pt)(若有多于t个人想签名，只需要其中的t个人签名即可). 另外选出一个主要负责人Pm，其中Pm不一定是签名参与者.

(2)取E上阶为n的生成元G=(xG,yG)作为基点,即有nG=o，o表示一个无穷原点，基点G公开.

(3)选取两个安全的公开的Hash函数h()，h1().

(4)SDC公开椭圆曲线相关参数(a，b，q，G,h()，h1(),n) .

1.2 密钥生成

(1)SDC为每个成员Pi分别构造其对应的t-1阶秘密多项式

每个成员Pi选择自己唯一的标识号IDi并公开.根据事先确定的门限值t，SDC把每一个成员的一个t-1次多项式fi(x) 通过秘密通道发送给Pi,然后每个成员均向其余成员公开广播aikG,并为集合U中每一位成员Pi(包括自己)计算λij=fi(IDj)(modn)), 并通过广播的形式将λij(j≠i)发给Pj,Pi自己保留λii.

(2)每个成员Pi对接收到其他的w-1个用户发来λij进行验证

(5)通过上面的步骤可知，由于门限值为t，所以在这个系统中任意t个成员联合，就可以利用拉格朗日多项式插值法恢复共享多项式：

这样则有下式成立：

1.3 部分签名的的生成

(1)当要对消息m进行签名时，设参与签名的t个人为B=(P1,P2,…,Pt).主要负责人Pm把要签名的集合B的各个成员身份IDv(v∈(1,t)) 发送给SDC，SDC计算SID=h1(ID1‖ID2‖…‖IDt)并且把SID秘密发送给Pm，SDC保存(SID,(ID1,ID2,…,IDt)).

(2)Pi选择一个随机数ki，ki∈[1,n-1]，计算Qi=kiG，其中ri=xi(modn),如果ri=0，则重新选取随机数ki.

(4)计算l=h(m)，si=(ki+ldi),如果si=0,那么重新选取随机数ki.生成部分签名(m,ri,si).并把部分签名(m,ri,si)发送给Pm.

1.4 Pm对组密钥的签名

1.5 DC对签名的验证

(2) 计算l=h(m),Vi=siG-lTi,如果Vi=0 签名无效.否则令ri为Vi的横坐标.

证明由si=ki+ldi(modn)得

Vi=siG-lTi=(ki+ldi)G-lTi=kiG,即ri=ri′.

1.6 群签名的生成

1.7 群签名的验证

2 方案的安全性和可行性

(1)方案具有门限特性.任何少于t个人成员组成的集合均不能产生一个有效的门限群签名.根据拉格朗日插值定理，只有t个人或多于t个人的时候才能恢复出群私钥f(0)，另外，当少于t个人签名时也无法合成群签名.

(2)根据群公钥Y和各个成员的公钥Ti来推导出群密钥X和各个成员的xi，其困难等价于求解有限域上基于椭圆曲线的离散对数问题.

(3)方案具有匿名性.当签名接收者接收到群签名时，在没有SDC的帮助下是无法知道哪些人参与了签名.

(6)方案能抗合谋攻击.在现有众多门限方案中，t个或多于t个成员合作能够恢复系统秘密多项式函数f(x)，因此t个或多于t个成员能够算出λi=f(IDi)，从而伪造其他成员的份额签名.但是在本方案中， 任何小组不能冒充其他小组生成签名，因为他们不知道ci所以无法计算出其他成员的私钥di.

3 结 论

基于椭圆曲线离散对数的难解性，提出一个有实际应用意义的基于椭圆曲线的门限签名方案，并且讨论了该方案的正确性、可行性和安全性.与经典的ECDSA方案[10]相比，该方案提高了整体运算速度，具有抗合谋攻击和可追查性.

[1]Shamir A. How to share a secret[J].Conlnlun ACM,1979，11:612-613.

[2]周由胜.门限密码相关技术研究[D].北京：北京邮电大学,2011.

[3]Desmedt Y.Society and group oriented cryptography[C]//Advance in Cryptology-CRYPTO' 87. USA :California,1987:120-127.

[4]Desmedt Y, Frankel Y. Shared generation of authenticator and signatures[C]//Advances in Cryptology-CRYPTO′ 91.Berlin: Springer-Verlag,1992:457-469.

[5]LI C M, Lee N Y. Remark on the threshold RSA signature scheme[C]//Advances in CRPTO' 93.Berlin: Springer-Verlag,1994:413-420.

[6]李海峰,蓝才会,左为,等.基于身份的无可信中心的门限群签名方案[J].计算机工程应用,2012,48(32):89-93.

[7]陈洪海,王宏久,于存光.安全的(t,n)门限签名方案[J].沈阳师范大学学报:自然科学版,2012，30(2):172-175.

[8]周敏,索南仁欠.基于椭圆曲线的DSA门限签名[J].青海师范大学学报:自然科学版,2012,30(2):6-8.

[9]徐燕.一个改进的无可信中心的门限签名方案[J].宣宾学院学报,2012,12(6):27-29.

[10]徐莹,孙剑.一种改进的基于椭圆曲线的数字签名方案[J].黑龙江科技学院学报,2012,25(6):66-69.