84 2010,46(1) Computer Engineering and Applications计算机工程与应用 对一个无可信中心的( ,n)门限签名方案的改进 高炜1,于晓冬2 GAO Wei ,YU Xiao-dong2 1.哈尔滨师范大学恒星学院数学与计算机系,哈尔滨150025 2.哈尔滨师范大学计算机学院,哈尔滨150025 1.Department of Mathematics and Computer,Harbin Normal University Star College,Harbin 150025,China 2.College of Computer,Harbin Normal University,Harbin 150025,China E—mail:gaoweispw@sina.com.cn GAO Wei,YU Xiao-dong.Improvement of(f,n)threshold signature scheme without trusted party.Computer Engineering and AppHcations,2010。46(1):84-86. Abstract:In a(t,n)threshold signature scheme,any set of t players can signature for an arbitrary message while any set of less than t players can not issue a signature at al1.The secret key is distributed among n parties with the help of a trusted party or without it by running an interactive protocol among all parties.In 2006,Guo et a1.pointed out that the scheme is insecure by analyzing the scheme of Wang et a1.The paper improves Wang et al’S scheme and avoids universally forging signature and insider attack. Key words:digital signature;threshold signature;secret sharing;insider attack;universally forging attack 摘要:一个(f,n)门限签名方案中,任何t个成员的集合能够对任意的消息产生签名而任何少于t个成员的集合都不能发行签 名。其中密钥通过可信中心或没有可信中心,通过所有的成员运行交互式协议在n个成员中分配。2006年,郭丽峰对王斌等的方 案进行了安全性分析,指出王等的方案是不安全的,该文对王的方案进行了改进,使其抗广泛性攻击及内部攻击。 关键词:数字签名;门限签名;秘密共享;内部攻击;广泛性攻击 DOI:10.3778 ̄.issn.1002—8331.2010.O1.027 文章编号:1002—8331(2010)01—0084—03 文献标识码:A 中图分类号:TP309.7 1引言 案不能抵抗外部伪造攻击和内部合谋攻击,进而证明了王斌 (t,n)门限签名是门限密码学研究的重要内容。自1991年 等 的方案是不安全的。 Desmedt和Frankel0首次提出( ,n)门限签名方案以来,门限签 在文献[6】方案的基础上,提出了一种基于离散对数的可以 名的研究取得了很大发展 。使用门限代理签名方案,数字签 抵抗文献[7】攻击的无可信中心的( ,n)门限签名,并对改进的 名能够由一个群体产生而不是由个体产生。在门限签名方案 门限签名方案的安全性进行了证明。 中,私钥由n个用户的群体共享,而不像普通签名中,私钥仅有 单个用户持有。为了对给定的消息产生一个有效的签名,每个 2改进的EIGamal方案 用户对消息产生部分签名,然后组合产生整体签名。1994年 该文和文献[6]都使用了改进的E1Gamal签名方案,该方案 Ham[5j提出了两个基于离散对数的门限群签名方案,一个是有 主要步骤如下: 可信中心的,—个是无可信中心的。由于在许多特定的应用环 选择一个大素数P和素域 上的生成元g,用户 从[1, 境下,一个可被所有小组成员信任的可信中心并不存在,所以 p-1]中选一个数托作为私钥,公钥 'g modp。 不需要可信中心的门限群签名方案就显得很具有吸引力,但在 当用户 对消息m进行签名时, 首先从[1,p-11中选一 Ham的无可信中心方案中,任意的t个人可通过他们掌握的数 据恢复任意成员的私钥,进而得到群私钥。2003年王斌和李建 个随机数 计算ri=g‘roodp。 华 利用联合秘密共享技术对Ham的方案进行了改进,该方案 Si:xim k ri mod(p一1) (1) 弥补了Ham方案的成员私钥易被恢复的安全漏洞,但2006年 s ∈[1,p-2】,m = (m),其中h(・)是一个单向函数,用于增 郭丽峰和程相国[71对文献[6】的安全性进行了分析,指出了该方 加消息的冗余性。(ri s )即用户 对m的签名。接收方可按公 作者简介:高炜(1976一),女,助教,研究方向:信息安全;于晓冬(1978~),男,讲师,研究方向:演化处理。 收稿日期:2008—07—21 修回13期:2038一10—20 高 炜,于晓冬:对一个无可信中心的(t, )门限签名方案的改进 2010,46(1)85 式(2)验证 对消息m的签名: DC,i为序号,用于确定G。 (,, ) 一格m。dp 3文献【6】的方案 (2) 3.3群体签名的生成阶段 群签名的生成者Dc先根据收到的签名验证同余式(5)是 否成立,成立则根据集合Si计算 =∑ 即 UE =文献[6】所提出的方案分为三个阶段:密钥生成阶段、部分 签名生成阶段和群签名的生成阶段。 ∑(A Ci)h(m)一r∑( ∈ “E s )mod g (6) 3.1密钥生成阶段 首先,每个成员 对外公开自己的唯一标示号/Di,根据 事先确定的门限值t,每个组成员 选定一个f一1次多项式 那么最终的群体签名为m, ,r,R)。 任何群签名的接收者都可以验证下面的等式是否成立: S rood g, 为其余n一1个成员,计算A ( )orod q,并通过 广播方式将A 发送给其他成员 。 在每个成员都完成上面的步骤后,组成员 可以计算A : ∑ .fm。d g,即AF∑ (,D )mod g。现在定义—个新函数 )= j=l j=l ∑ ( )mod g,虽然 不知道 ),但不难知道AF ≈)。 在 j=l [1,p-1]上选一个随机数 ,把 A五 mod g作为组成员 的密 钥,而 = ‘modp作为 的公钥。令ri=g 。roodp, 把ri通过 广播的方式发给其他成员。 每个成员可计算R=17 mod_p,由于门限值为t, 个成员 i=1 利用多项式插值: o):f∑ \i=i )・n二 )j=l,, £一 / m。d 9可以恢复 F(0),然后就把y: xR m。dp作为组的公钥,相应的组密钥 为 0)+∑k mod q o 仁l 3.2部分签名生成阶段 首先经协商确定哪些组成员将参与群签名,参与群签名的 组成员形成集合5,在集合5中按成员编号的递增顺序来排列 组成员。然后S中的每个成员 在I1,q-1】上选一个新随机数 t ,接下来 计算 ‘modp和z 。 modp,其中k 为组成 员 在密钥生成阶段选择的随机数,(ki) 为 在素域上的逆 元。 把 和z 通过广播的方式发送给参与签名的其他成员。 在收到其他成员发送的 和z 后, 从s中选最前面的t个成 员,形成集合s ,集合Sl中也按成员编号的递增顺序来排列组 成员。 计算r=兀modp,然后根据下面的同余式求解s : ∈S k: ̄(kjt Ci)xh(m)-rxt;rood g (3) 式(3)等价于 (A Ci) ̄h(m)一rXt x(k ) rood q (4) 式(4)的C :}:t,兀_二|≠i xi一 一为插值系数。 . 根据式(4)可以验证 。( ) :( )“ ‘m。dp (5) 把(m,ri Yi, ,i)发送给指定群体的签名的生成者 /=(yxR )“…mod P (7) 郭丽峰等在文献[7冲对上述方案进行了分析,指出该方 案不能抵抗外部伪造攻击和内部伪造攻击,因此该方案是不 安全的。 4该文方案 提出了—个基于离散对数的无可信中心的( , )门限签名 方案,方案主要分为三个阶段:密钥生成阶段、部分签名生成阶 段和群签名生成阶段。 4.1密钥生成阶段 首先,每个成员 对外公开自己的唯一标示号 ,根 据事先确定的门限值t,每个组成员 选定一个t一1次多项 式 rood q,u/为其余 一1个成员,计算A。 ( )mod q,并通 过广播方式将A 发送给其他成员 。 在每个成员都完成上面的步骤后,组成员 可以计算A = ∑Aj, ̄modg,即AF∑ (,D )orodq。现在定义—个新函数 )= J:I =I ( )rood q,虽然 不知道F(x),但不难知道A =F(托)。Ui J=1 在【1,p-1]1-_选一个随机数 ,把 ;rood q作为组成员 的 密钥,而y ‘modp作为 的公钥。令 ‘modp,Ni modp, 把 通过广播的方式发给其他成员。 每个成 ̄…t=t13 ̄汁算R=兀riorodp,由于门限值为c'f个成员 l=l f t \ 利用多项式插值:,(0)=l∑F(x。)・兀 lorod q。可以恢 \I 1 j=l0≠ l— / 复F(0),然后就把y: × m。dp作为组的公钥,相应的组密 钥 为 0)+ k mod q。 1 4.2部分签名生成阶段 首先经协商确定哪些组成员将参与群签名,参与群签名的 组成员形成集合s,在集合s中按成员编号的递增顺序来排列 组成员。然后S中的每个成员 在【1,q-1]上选—个新随机数 ti接下来 计算 modp和z 。 ’modp,其中k 为组成 员 在密钥生成阶段选择的随机数,(ki) 为k 在素域上的逆 元。 把 、Z 和Yi通过广播的方式发送给参与签名的其他成 员。在收到其他成员发送的 、 和Y 后, 从s中选最前面的 86 2010,46(1) Computer Engineering and Applications计算机工程与应用 或成员私钥%等价于求解离散对数问题,这在计算上是不可 t个成员,形成集合S,集合s 中也按成员编号的递增顺序来排 列组成员。 计算r=:兀 m。dp, n modp,且r≠肘,然后 uj ES “ES 行的。假如攻击者得到一个或多个成员签名,通过等式s产 ()tiCi) ̄h(m,r)一 ;( ) + 求解施的概率为l向,当q足够大 时,得到筏的概率几乎为0。 根据下面的同余式求解.s : k 5 ( Ci) ̄h(m,r)一rxt +rxlk rood q (8) (2)群中任意t个成员合谋无法获取群私钥和成员私钥 根据成员多项式的构造可知,t个成员合谋就可以获取群 式(8)等价于 5F(A Ci)xh(m,r)一rxt x(k ) + rood q (9) 中某个成员的多项式,即获取多项式中的常数项 ,。+ ),但 式(9)的Ci:n—!L为插值系数。 j=1,j#i xi 根据式(9)可以验证 ‘( ) :( )“ ‘.^(m。dp (10) 把(m,ri,s Y, ,Ni, )发送给指定群体的签名的生成者 DC,i为序号,用于确定G。 4.3群体签名的生成阶段 群签名的生成者DC先根据收到的签名验证同余式(10) 是否成立,成立则根据集合Si计算s=∑ 即 HE 5 s:∑(A ) (m,r)一r∑(f m。d q (11) “E 5 E s‘ 那么最终的群体签名为(m,M,s,r,R o 任何群签名的接收者都可以验证下面的等式是否成立: :(yxR )“ ・ modp r≠ ) (12) 5安全性分析 5.1正确性证明 (1)部分签名的正确性 如果(m,ri yi, , ,i)是 对消息m 的签名,则一定能 满足式(10)。因为: ‘( ) ‘ .( ‘) m。dp ‘m _ . rt,m。dp: J‘’ ‘ - moo dp=P( Y ) ’‘ (2)群签名的正确性 如果(m,M,s,r,R)是集合s中t个成员对消息m的合法 签名,则一定满足等式(12)。因为: / . .(兀 ,, ~ _|. ,“ ~modp: E 5 ^m .,  ̄.rxjg . g mod,P tyXK : yxR-1= , …,. .‘L(1 丌1Y1),mod p: p= (y×R ) . m0dp 5.2私钥的安全性 (1)通过群公钥和签名无法获取群私钥或成员私钥 群公钥y=gF xR mod P,各成员的公钥Yl=g m。d p= modp,因为ki是保密的,所以通过Y和yi来求解群私钥 由于di是保密的,所以即使t个成员合谋也无法知道某个成 员的私钥.,= 而群私钥等于所有成员私钥的和,所以t个人合 谋也无法获得群私钥,因此在这种情况下,群私钥的私钥都是 安全的。 5.3签名的不可伪造性 提出的方案是抗内部攻击和外部攻击的 ,因此方案是安 全的。 5.4签名的匿名性和可追踪性 在方案中,由于Dc对外公布的是 JEA l1 moB dp,所以, 只有签名合成者DC才知道参与签名的t个成员的身份,而验 证者只能验证群签名,并不知道是谁参与了签名。如果事后发 生纠纷,可以通过DC揭示参与签名的t个成员身份。 6总结 提出了一个新的基于离散对数的无可信中心(t,,Ol'q限方 案。该方案弥补了郭丽峰等方案的不足防止内部攻击、外部攻 击和合谋攻击。最后给出了方案的安全性分析,在理论上证明 了方案是安全的。 参考文献: [1]Desmedt Y,Frankel Y.Shared generation of authenticators and sig- natures[C]//Proceeding of Cryptology-CRYPTO’91.Berlin:Springer- Verlag,1991:457—469. 【2 Li2】 C M,Hwang T,Lee N Y.Remark on the threshole RSA signa— ture scheme[C]//Stinosn D.LNCS 773:Advances in Cryptology— CRYPTO’91.Berlin:Springer-Verlag,1994:413—420. [3]Gennaro R,Jareeki S,Krawczyk H,et a1.Robust threshold DSS[C]B Maurer U.LNCS 1109:Advances in Cryptology—EUROCRYPT’96. Berlin:Springer,1996:157—172. [41 Wang C T.Lin C H.Threshold signature schemes with traceable signers in group communications[J].Computer Communications,1998, 21(8):771—776. [5]Ham L.Group—oriented(t,n)threshold digital singature scheme and digital multisignature[J].IEE Proceedings of Computers and Diigtal nad Technique,1994,141(5):307—313. 【6】王斌,李建华.无可信中心的(t,n)门限签名方案【J】_计算机学报, 2003,26(11):1581-1584. [7】郭丽峰,程相国.一个无可信中心的(£,n)门限签名方案的安全性分 析[J】.计算机学报,2006,29(11):2013—2017.