Microsoft Word 张彩娟.doc

Size: px

Start display at page:

Download "Microsoft Word - 09-160050-张彩娟.doc"

凤汤
7 years ago
Views:

1 第卷第 6 期网络与信息安全学报 Vo. No.6 06 年 6 月 Chnese Journa of Nework and Inforaon Secury June 06 基于双线性对的多重数字签名方案张彩娟游林 (. 杭州电子科技大学理学院浙江杭州 3008;. 杭州电子科技大学通信学院浙江杭州 3008) 摘要 : 基于双线性对及 3 个困难性问题 (IFP DLP CDHP) 提出了新的多重数字签名方案新方案将广播多重数字签名中签名快速的优点应用到按序多重数字签名改变签名的一般机制使签名者同时进行签名 ; 然后由可信任第三方验证签名验证通过后发送给验证者 ; 最后由验证者将签名转变为按序的同时分析了方案在 3 个困难问题防伪攻击和抗部分成员合谋攻击方面的安全性能新方案具有计算量少算法简单获取签名速度快安全性强等优点关键词 : 多重数字签名 ; 按序签名 ; 广播签名 ; 安全性中图分类号 :TP309 文献标识码 :A do: 0.959/j.ssn x Dga u-sgnaure schee ased on near parng ZHANG Ca-juan YOU Ln (. Coege of Scence Hangzhou Danz Unversy Hangzhou 3008 Chna;. Coege of Councaon Hangzhou Danz Unversy Hangzhou 3008 Chna) Asrac: Based on near parng and hree copcaed proes a new dga u-sgnaure schee was proposed. In he new schee he advanage of fas sgnaure n roadcasng dga u-sgnaure was apped o seuena dga u-sgnaure. By changng he genera echans of sgnaure sgnng coud e done suaneousy y he sgners. Then he sgnaure was sen o verfer afer was verfed y rused hrd pary. The ransforaon fro concurren sgnaure o seuena sgnaure was fnay reazed y he verfer. The secury capaes n hree copcaed proes an-fake aack and an-conspracy aack fro soe eers of he new schee were anayzed. Proposed schee has any advanages over he od ones such as fewer cacuaon sper agorh faser sgnng hgher secury. ey words: dga u-sgnaure seuena sgnaure roadcasng sgnaure secury 引言随着互联网的高速发展人们希望通过电子设备就能实现远距离的快速的交易自 976 年 Dffe 和 Hean [] 首次提出公钥密码体制的概念后数字签名随之产生并开始在商业通信系统中得到广泛应用实际情况中有时需要多个用户对同一消息进行签名这类需要多个实体对同一份合同进行签名的电子对应物就是多重数字签名 [] 自引入多重数字签名的概念后不同的多重数字签名方案相继被提出文献 [3 5] 提出基于收稿日期 : ; 修回日期 : 通信作者 : 张彩娟 @.co 基金项目 : 浙江省重点科技创新团队基金资助项目 (No.03TD03) Foundaon Ie: Zhejang Provnce Scence and Technoogy Innovaon Progra (No.03TD03) 0006-

者同时进行签名 ; 然后由可信任第三方验证签名验证通过后发送给验证者 ; 最后由验证者将签名转变为按序的同时分析了方案在 3 个困难问题防伪攻击和抗部分成员合谋攻击方面的安全性能新方案具有计算量少算法简单获取签名

2 第 6 期张彩娟等 : 基于双线性对的多重数字签名方案 67 离散对数困难性问题的多重数字签名 ; 文献 [5] 在离散对数困难性的基础上把整数分解问题也应用到签名里使签名方案更安全可靠 ; 文献 [6 8] 给出关于散列函数的发展和其在多重签名中的应用 ; 文献 [9] 把盲签名以及代理签名运用到多重签名中形成新的方案 ; 文献 [0] 中对椭圆曲线密码体制的运用和改进使多重签名方案更加多样化 ; 文献 [] 中提出的针对基于离散对数多重签名方案的攻击和文献 [3] 提出的基于椭圆密码体制的签名方案的攻击使多重签名方案更加完善安全以上文献各有优缺点但其设计思想值得借鉴根据多重签名顺序和过程的不同可分为按序多重签名和广播多重签名文献 [64] 给出基于同样问题的按序和广播种多重签名方案通过比较可以发现按序多重签名方案耗时更久些对重大性和紧急性事件有较大影响例如在按序多重数字签名体系中当消息发送给签名者时若签名者未及时签名则后面的签名者也无法对消息进行签名依此下去每个签名者都耽误一点时间则最后验证者收到签名的时间就会延长很久针对按序多重签名方案这一缺点本文将按序和广播种多重签名在某种程度上结合起来同时又结合离散对数困难性问题整数分解问题以及 Dffe-Hean 计算问题来构造新方案与文献 [5] 的按序多重数字签名方案相比本方案获取签名速度更快运算量更少安全性更高基础知识. 对称双线性对设 G 是椭圆曲线 E( F ) 上的一个加法循环群 G 是有限域 F 上的乘法循环群两者的阶均为令 g 为 G 的生成元假设 G 和 G 中的离散对数问题都是难解的对称双线性对是一个映射 e : G G G 它具有如下属性 ) 双线性性对任意的 P Q G a Z 都有 e( ap Q) e( P Q) a 成立 ) 非退化性对任意的 P Q G 满足 e( P Q) 3) 可计算性存在有效算法对任意的 P Q G e( P Q ) 都能够有效地计算. 困难问题假设定义大整数分解问题 (IFP) 已知个大素数 p 求 n p 是容易的但若由 n 来求 p 和是困难的这就是大整数分解困难问题定义离散对数问题 (DLP) 设 G 为一个循环群对于 P Q G 找到一个整数 a Z 使 Q ap 成立定义 3 Dffe-Hean 计算问题 (CDHP) 对于任意的 a Z 给出 P ap P G 计算出 ap 且满足 ap G.3 基于 SDLP 和 IFP 的多重数字签名方案文献 [5] 提出基于 SDLP 和 IFP 的按序多重数字签名方案简述如下 ) 系统的建立给出签名的顺序 G { D D } D 首先假设一个安全的散列函数 H 对原始消息 M 进行加密得到 H ( M ) ; 其次可信任第三方 T 随机选择个大素数 p 并计算 n p ; 再次选取素数 r 满足 r ( p ) r ( ) ; 然后选择元素 α Ζ n 其中 α 对模 n 的指数为 r ; 最后选择 s Ζ 计算 s β α (od n ) 并公开系统参数 ( α β r n ) ) 签名算法 Sep T 随机选取 4 个整数 a0 0 c0 d0 Ζ r 其中记 h ( a0 + s0 )(od r) k ( c0 + sd ) 0 a0 + s0 h (od r ) 通过计算 P α α (od n ) c0 + sd0 k Q α α (od n ) 获得公钥 ( P Q ) Sep 签名者 D 随机选取个整数 h h k Ζ 计算 α α 并通过安全信道将其发送 k r h h 给 T T 接收之后利用已知参数计算 E α ( α ) k k (od n ) ( s F α α ) (od n ) 随后将 E F 秘密地发送给 D 这样签名者 D 就能利用私钥验证 T 发送给它的 E F 是否正确 Sep3 签名者 D 利用私钥 ( h k E F ) 以及计算得到签名 EF (od n ) 和 g h + k (od r) 并把签名 ( g ) 传给下一个签名者 g D D 接收后验证等式 β PQ (od n ) 是否成立若成立则计算其签名 EF (od n ) 和 g g + h + k (od r) 并发送 ( g ) 给 D 3 3 依此进行下去直到 g β ( ) (od ) r s D 验证 PQ n 成立形成最终签 0006-

献 [3] 提出的基于椭圆密码体制的签名方案的攻击使多重签名方案更加完善安全以上文献各有优缺点但其设计思想值得借鉴根据多重签名顺序和过程的不同可分为按序多重签名和广播多重签名文献 [64] 给出基于同样问题的按序

3 68 网络与信息安全学报第卷名 EF (od n ) 及 g g + h + k (od r ) 并将签名 ( g ) 发送给验证者 3) 签名的验证验证者接收到 ( g ) 后利用公钥进行检验若 g β ( PQ ) (od n ) 成立则最终签名为 ( g ) 3 新的多重数字签名方案 3. 系统的建立首先可信任第三方 C 选择大素数并取阶为的循环群 G G 其中 G 是加法群 G 是乘法群且 g 为 G 的生成元则有双线性映射 e : G G G 其次选取散列函数 H :{ 0} Ζ 并对原始消息 M 进行加密得到 H( M) 再次给出规定的签名顺序 Γ ( U U U ) 最后将签名顺序 Γ 发送给签名验证者并公布系统参数 ( G G H M e g ) 3. 签名算法 Sep 可信任第三方 C 通过随机选取 a Z 来产生其私钥 ( a ) 并计算 e( g g ) a e ( g g ) eg ( ag) e ( g g) e( g g ) e ( g g ) a 令 T e ( g g) A e ( g g) B e ( g g) 得到公钥 ( T A B ) Sep 签名者 U 随机选取大素数 p 令 n p 同时选择满足条件 ( p ) 的计算 n 以及满足条件 c odn 的 c 得到系统公钥 c 3 记 A Ae ( g g) B Be ( g g) 通过计算得到签名者 U 的私钥 ( n A B ) 4 U 利用私钥计算 e( g g) e ( g g) 和签名 S AB 并通过安全信道将 ( e ( g g) S ) 秘密地发送给可信任第三方 C Sep3 可信任第三方 C 利用它的私钥及 ( A B e ( g g )) 来验证 ( + ) S AB AB e ( g g) 是否成立若成立 C 将 ( S c T ) 作为签名发送给验证者 ; 否则发送空消息 3.3 签名的验证当验证者接收到所有签名 ( S c T ) 后需 j ( ) 根据签名顺序 Γ 进行逐一验证若 S T + cj cj c ( ) A B ( j ) 成立而 S T + A B c j c c 不成立则判定签名者 ( U U + U ) 的签名均是无效的反之若 S T cj ( + ) cj cj j A B c ( j ) 都成立则计算 S Π S C c 并将 ( S C T ) 作为最终的签名因为 c S Π S ( + ) c ( AB e ( g g)) Π Π c ( AB ) T ( AB ) T ( + ) C ( + ) 这样形成的最终签名长度是固定的与签名者的个数无关上述按序签名方案是在文献 [5] 的基础上进行改进的与文献 [5] 相比本文引入了双线性对并选取了不同的 n 使方案的安全性更高 ; 同时又改变了按序签名的体制使签名经过了可信任第三方和验证者双重的验证更加真实可靠 ; 且新方案中可信任第三方产生的私钥量较小节省了密钥存储空间 ; 此外新方案在整个签名生成的过程中运算量较小获取签名速度快签名的长度也是固定的不随签名者的变化而改变 4 效率及安全性分析 4. 效率分析本文提出的新方案与文献 [5] 在运算量和签名时间上的比较如表所示记号说明 : T 表示乘法运算 T e 表示幂运算 T 表示加法运算表示消息从发送给 U 开始 a 到签名结束所消耗的时间 T 表示从消息发出后到所有签名结束需要的总时间由表可知本文方案在签名所需总时间和签名生成过程中所需运算量上都占有极大优势显然新方案获取签名的速度更快运算量更少效率更高 4. 安全性分析 4.. 困难问题 IFP: 由于 ( G G e g c ) 是公开参数任何人都能求出 e( g g ) 但是不能求得 e ( g g ) 因为大素数 p 是未知的从而 n 也是未知的所以没有

名顺序 Γ ( U U U ) 最后将签名顺序 Γ 发送给签名验证者并公布系统参数 ( G G H M e g ) 3.

4 第 6 期张彩娟等 : 基于双线性对的多重数字签名方案 69 表个方案运算效率对比方案签名所需总时间 T 生成签名签名验证总运算量文献 [5] 方案 (4n ) T (3n ) Te (n ) Ta + + T Te + 4nT + 3 nte + (n ) Ta 本文方案 ax( ) nt nte + nt (n ) Te ( n ) Ta nt + (3n + ) Te + ( n ) Ta 人可以通过 c 和来求得从而得到 e ( g g ) 求解的难度等价于大整数的分解问题 DLP: 因为 e( g g ) 是可以由公共参数求得的同时 e ( g g) T 是公开的所以任何人想要通过 e( g g ) 和 e ( g g ) 来找到 Z 使 e ( g g) e ( g g ) 成立是不可能的因为寻找 Z 的过程实际就是解决离散对数问题的过程 CDHP: 假设攻击者可以通过某种方式截获签名者 U 发送给可信任第三方 C 的秘密消息 e ( g g ) 由于 e( g g ) 和 e ( g g ) 是易得或易知的所以攻击者根据获得的信息 e ( g g ) 来求 e ( g g ) 是困难的求解 e ( g g ) 的难度相当于解决 Dffe-Hean 计算问题 4.. 防伪攻击假设一个攻击者想要伪装成签名者 U 对原始消息 M 进行签名根据本文所提签名算法可知攻击者可以随机选取大素数 p 和其中要满足条件 ( p ) 随后通过计算 n p ( ) e g g e ( g g) 以及满足等式 c odn 的 c 来伪造 n e ( g g ) 和 c 并将 c 公开最后攻击者通过计算 S Ae ( g g)( Be ( g g)) 来伪造签名 ( S c T ) 显然该签名可以通过验 c ( ) c c 证者的验证因为 S + T A B 成立但是攻击者不知道签名者 U 与可信任第三方 C 之间的秘密信道因此无法将伪造的 ( e ( g g) S ) 发送给 C 也无法通过 C 的验证从而无法通过 C 将伪造的签名发送给验证者即该方案有效地防止了攻击者的伪造攻击 4..3 抗部分成员合谋攻击本文方案在一定程度上将按序多重签名与广播多重签名结合起来先由每个签名者 U 独立地进行签名 ( S c T ) 然后将 ( S c T ) 交给可信任第三方 C 进行验证验证通过后由 C 将签名直接发送给验证者验证者接收到所有签名 ( S c T ) 后按照预定的顺序对签名进行逐一验证验证成功后再统一形成总的签名 ( S C T ) 正是由于该算法中签名者 U 进行签名时是各自独立的且每个签名 ( S c T ) 要经过 C 的验证才能发送给验证者所以整个方案中没有通过签名者相互合作而形成的公私钥即部分成员之间是无法通过合谋来伪造任何东西的从上面安全性的分析可以看出双线性对的引入不同 n 的选取以及新结构的构造使新方案更安全防攻击能力更强 5 结束语针对按序多重数字签名方案获取签名速度慢的特点本文改变了传统按序签名的体制将按序和广播签名在一定程度上结合起来形成新的按序多重签名体制新方案具有运算量少算法简单获取签名速度快安全性强等优点同时方案中新的构造方法为签名节省了大量时间极具推广性是具有发展潜力的多重数字签名方案参考文献 : [] DIFFIE W HELLMAN M E. New drecons n crypography[j]. IEEE Transacons on Inforaon Theory 976 (6): [] ITAURA. A puc-key cryposyse suae for dga u-sgnaures[j]. Nec Research & Deveopen 983 7(): [3] LU L R ZENG J J UANG Y H e a. A new u-sgnaure schee ased on dscree ogarh proe and s dsrued copuaon[j]. Chnese Journa of Copuers 00 5(): [4] BURMESTER M DESMEDT Y DOI H e a. A srucured egaa-ype u-sgnaure schee[c]//the 3rd Inernaona Workshop on Pracce and Theory n Puc ey Crypography. c000: [5] DÍAZ R D ENCINAS L H MASQUÉ J M. A u-sgnaure schee ased on he SDLP and on he IFP[C]// Inernaona Conference on Copuaona Inegence n Secury for Inforaon Syses. c0:

何人想要通过 e( g g ) 和 e ( g g ) 来找到 Z 使 e ( g g) e ( g g ) 成立是不可能的因为寻找 Z 的过程实际就是解决离散对数问题的过程 CDHP: 假设攻击者可以通过某种方式截获签名者 U 发送给可信任第三方 C 的秘密消息 e (

5 70 网络与信息安全学报第卷 [6] ZHANG J H WEI Y Z WANG Y M. Dga u-sgnaures schee ased on RSA[J]. Journa of Chna Insue of Councaons 003 4(8): [7] U.S. Deparen of Coerce. Secure Hash sandard-shs: federa nforaon processng sandards pucaon 80-4[M]. Creae Space Independen Pushng Pafor 0. [8] NOROOZI E DAND S M SABOUHI A e a. A new dynac hash agorh n dga sgnaure[j]. Advanced Machne Learnng Technooges and Appcaons 0 3(): [9] GUO W ZHANG J Z LI Y P e a. Mu-proxy srong nd uanu sgnaure schee[j]. Inernaona Journa of Theoreca Physcs 06 55(3): -3. [0] LI F XUE Q. Two proved proxy u-sgvcdnaure schees ased on he epc curve cryposyse[m]//copung and Inegen Syses. Bern Hedeerg: Sprnger 0: [] CHOUSEY R SIVASHANARI R SINGHAI P. ECDLP ased proxy u-sgnaure schee[m]//advances n Copung and Inforaon Technoogy. Bern Hedeerg: Sprnger 0: [] HAN X X WANG G P BAO F e a. An aack o u-sgnaure schees ased on dscree ogarh[j]. Chnese Journa of Copuers 004 7(8): [3] LIU Y LUO P DAI Y Q. Aack on dga u-sgnaure schee ased on epc curve cryposyse[j]. Journa of Copuer Scence & Technoogy 007 (): [4] WANG X F ZHANG J WANG S P. Dga u-sgnaure schee and s secury roof[j]. Chnese Journa of Copuer 008 3(): 作者简介 : 张彩娟 (993-) 女山西大同人杭州电子科技大学硕士生主要研究方向为信息安全与密码学游林 (966-) 男江西临川人杭州电子科技大学教授主要研究方向为信息安全与密码学

Advanced Machne Learnng Technooges and Appcaons 0 3(): 583-589. [9] GUO W ZHANG J Z LI Y P e a. Mu-proxy srong nd uanu sgnaure schee[j]. Inernaona Journa of Theoreca Physcs 06 55(3): -3.

Microsoft Word 版权页_新版_.doc

Microsoft Word 版权页_新版_.doc 第卷第 6 期网络与信息安全学报 Vo. No.6 06 年 6 月 Chnese Journa of Nework and Inforaon Secury June 06 基于双线性对的多重数字签名方案张彩娟游林 (. 杭州电子科技大学理学院浙江杭州 3008;. 杭州电子科技大学通信学院浙江杭州 3008) 摘要 : 基于双线性对及 3 个困难性问题 (IFP DLP CDHP) 提出了新的多重数字签名方案