对三个聚合签名方案的密码学分析

陈群山,周豫苹,郝艳华,吴晨煌

（1.闽南师范大学计算机学院,福建漳州363000；2.莆田学院数学学院,福建莆田351100）

对三个聚合签名方案的密码学分析

陈群山1,周豫苹1,郝艳华1,吴晨煌2

（1.闽南师范大学计算机学院,福建漳州363000；2.莆田学院数学学院,福建莆田351100）

聚合签名方案可将n个签名者对n个不同消息的n个签名聚合成一个签名,验证者只需验证聚合签名结果即可确认这n个签名的有效性.对已有的三个聚合签名方案进行安全性分析,给出了对这三个方案的攻击方法,说明它们无法满足不可伪造性的安全要求.

基于身份签名；基于证书签名；聚合签名；安全性分析

1 概述

在2003年EUROCRYPT上,Boneh等［1］首次提出聚合签名的概念,并在BLS短签名方案［2］的基础上构造了一个聚合签名方案.在该方案中,多个签名者的签名可被聚合成一个签名,验证者只需验证聚合后的签名即可确认这些签名的有效性.通过签名的聚合运算,签名的总长度得到了缩短,从而减少了签名的存储空间与验证时间,有效地提高了签名的验证效率.鉴于聚合签名的优势,聚合签名可被广泛地应用于多个领域,因此,聚合签名的概念在提出后即成为研究热点,目前已有各种类型的聚合签名方案被提出［3－6］.

文献［7］和文献［8］分别提出一个基于身份的聚合签名方案,文献［9］同时对文献［7］和［8］中的方案进行分析,发现这两个聚合签名方案并不安全,并分别对原方案进行了改进.文献［10］随后指出文献［9］对文献［7］的改进方案还不安全,并提出一个新的改进的基于身份的聚合签名方案.本文对文献［9,10］中的方案进行了安全性分析,发现文献［9］对文献［8］的改进方案也存在缺陷,攻击者可以伪造单个签名和聚合签名；同时文献［10］对文献［9］的改进结果仍然存在类似文献［7,9］方案中的安全问题,攻击者可以伪造聚合签名.文献［11］利用双线性对构造了一个可证明安全的基于证书的聚合签名方案,本文发现在基于证书的公钥密码体制的安全模型［12］下,该方案无法抵抗A2型攻击者的伪造攻击,攻击者A2甚至在不需要知道签名者私钥的情况下,都可以伪造任意用户对任意消息的合法签名,因此该聚合签名方案也是不安全的.

2 文献［9］的基于身份的聚合签名方案及其安全性分析

2.1 文献［9］方案简述

文献［9］中的基于身份的聚合签名方案由以下6个部分组成：

1）系统设置：PKG选择阶为素数q的循环群G1和G2,G1的生成元为β,构造双线性映射e：G1×G1→G2,Hash函数H0：｛0,1｝＊→G1,H1：｛0,1｝＊×G1→Z＊q.PKG随机选取r∈Z＊q,计算δ＝rβ.系统主私钥为r,系统公钥为δ,系统参数params＝｛G1,G2,e,q,β,δPub,H0,H1｝.

2）密钥提取：设用户Ui身份为IDi,PKG计算Ui的私钥Si＝rH0（IDi）,公钥Pi＝H0（IDi）.

3）单个签名：Ui选取ai∈Zq＊,计算Ri＝aiPi,Ti＝aiSi＋H1（miRi）β.则Ui对消息mi的签名为σi＝（Ri,Ti）.

4）单个签名的验证：签名聚合者计算H1（miRi）,验证等式e（Ti,β）＝e（Ri,δ）e（β,β）H1（miRi）是否成立,若成立则单个签名σi＝（Ri,Ti）有效.

5）签名聚合：签名聚合者收到所有用户Ui的签名σi＝（Ri,Ti）（1≤i≤n）,计算,则（V,R1,R2,…,Rn）为用户Ui（1≤i≤n）对消息mi（1≤i≤n）的聚合签名.

6）聚合签名验证：签名验证者收到聚合签名（V,R1,R2,…,Rn）,验证等式e（V,β）是否成立,若等式成立则聚合签名有效.

2.2 文献［9］方案的安全性分析

假设攻击者A经过签名询问得到某一用户Ui对消息mi的有效签名σi＝（Ri,Ti）,则攻击者A可伪造用户Ui对任意其它消息m′i的有效签名.由Ti＝aiSi＋H1β,可得aiSi＝Ti－H1）β,攻击者可任选ti∈,计算R′i＝tiRi＝tiaiPi,T′i＝tiaiSi＋H1β,则σ′i＝（R′i,T′i）是消息m′i的有效签名.事实上,

显然攻击者A可用上述方法伪造的用户Ui的签名σ′i＝（R′i,T′i）与其他用户的合法签名产生一个有效的聚合签名.进一步地,攻击者A可以伪造用户Ui（1≤i≤n）对任意消息m′i（1≤i≤n）的有效聚合签名（V,R1,R2,…,Rn）.

3 文献［10］的基于身份的聚合签名方案及其安全性分析

3.1 文献［10］方案简述

文献［10］中的基于身份的聚合签名方案共有6个组成部分.

1）Setup：给定群G,GT,G的生成元P及双线性对e：G×G→GT.随机选取s∈Zm,计算PPub＝sP.选取Hash函数H1：｛0,1｝＊→G,H2：｛0,1｝＊×G×｛0,1｝＊→Zm.系统的公开参数params＝｛G,GT,e,P,PPub,H1,H2｝,系统主密钥为s.

2）Key－Extract：对用户的身份IDi,1≤i≤n,计算用户的公钥为QIDi＝H1（IDi）,私钥为DIDi＝sQIDi.

3）Sign：假设身份为IDi的用户要签名的消息为mi,随机选取ri∈Zm,分别计算Ui＝riP,hi＝H2（mi,Ui,IDi）,Vi＝hiDIDi＋riPPub,则σi＝（Ui,Vi）就是签名结果.

4）Sign－Verify：已知用户身份IDi与公钥QIDi,消息mi及其签名σi,验证者计算hi＝H2（mi,Ui,IDi）,若等式e（P,Vi）＝e（Ui＋hiQIDi,Ppub）成立,则σi是一个有效的签名.

5）Aggregate－Sign：签名聚合者收到σi＝（Ui,Vi）（1≤i≤n）之后,计算则σ＝（U,V）为身份（ID1,ID2,…,IDn）对消息（m1,m2,…,mn）的聚合签名.

6）Aggregate－Verify：当且仅当等式成立,σ＝（U,V）是有效的聚合签名.

3.2 文献［10］方案的安全性分析

设用户A1的身份为ID1,攻击者A2的身份为ID2,则即使没有用户A1的参与,攻击者A2可以通过以下方法生成身份（ID1,ID2）对消息（m1,m2）的有效聚合签名.

A2可随机选取r1,r2∈,分别计算U1＝r1P,h1＝H1（m1,U1,ID1）,U2＝r2P－h1QID1－U1,U＝U1＋U2,V＝h2DID2＋r2PPub.则（U,V）为身份（ID1,ID2）对消息（m1,m2）的聚合签名,易验证以下等式成立：

由此可知,文献［10］的基于身份的聚合签名方案是不安全的,该方案无法阻止攻击者对聚合签名的伪造攻击.

4 文献［11］的基于证书的聚合签名方案及其安全性分析

4.1 文献［11］方案简述

文献［11］中的基于证书的聚合签名方案由6个算法构成：

1）Setup：CA选取阶为素数q的循环群G1和G2,选择G1的生成元P和Q；构造双线性映射e：G1×G1→G2,Hash函数H1：｛0,1｝＊×G1→G1,H2：｛0,1｝＊×｛0,1｝＊×G1×G1→Z＊q；随机选择系统主私钥s∈Z＊q,系统公钥为Ppub＝sP,系统参数params＝｛G1,G2,e,q,P,Q,PPub,H1,H2｝.

2）UserKeyGen：身份为IDi的用户Ui随机选择xi∈Z＊q作为私钥SKi,计算公钥PKi＝xiP.

3）GerGen：Ui发送IDi和PKi给CA,CA计算Qi＝H1（IDi,PKi）,Certi＝sQi,并将Certi作为证书发送给Ui.

4）Sign：Ui随机选取ri∈Z＊q,分别计算Ri＝riP,hi＝H2（mi,IDi,PKi,Ri）,Vi＝riQ＋xihiPpub＋Certi.则用户Ui对消息mi的签名为σi＝（Ri,Vi）.

5）Aggregate：签名聚合者收到用户Ui对消息mi的签名σi＝（Ri,Vi）（1≤i≤n）,计算则σ＝（R1,R2,…,Rn,V）为用户Ui对消息mi（1≤i≤n）的聚合签名结果.

6）Verify：对聚合签名σ＝（R1,R2,…,Rn,V）,签名验证者分别计算Qi＝H1（IDi,PKi）和hi＝H2（mi,IDi,PKi,Ri）（1≤i≤n）,验证等式e（V,P）若等式成立则聚合签名有效,否则签名无效.

4.2 文献［11］方案的安全性分析

在基于证书的签名方案的安全模型［11,12］中,只有同时拥有签名私钥SKi和证书Certi的用户Ui才能产生合法的签名,即使是知道系统主私钥s的第二类型攻击者A2也无法伪造有效的基于证书签名.而在文献［11］所构造的基于证书的聚合签名方案中,攻击者A2可以在没有用户Ui的私钥SKi的情况下伪造用户Ui对任意消息mi的有效签名（1≤i≤n）.

由于A2拥有系统主私钥s,A2可任选ri∈Z＊q,计算Ri＝riP,hi＝H2（mi,IDi,PKi,Ri）,Vi＝riQ＋s（hiPKi＋Qi）,则（Ri,Vi）为用户Ui对消息mi的有效签名.事实上,因为PKi＝xiP,Certi＝sQi,Ppub＝sP,因此Vi＝riQ＋s（hiPKi＋Qi）＝riQ＋shixiP＋sQi＝riQ＋xihiPpub＋Certi,显然签名结果（Ri,Vi）是有效的.

由此,攻击者A2可进一步伪造所有用户Ui（1≤i≤n）对任意消息mi（1≤i≤n）的有效聚合签名σ＝（R1,R2,…,Rn,V）.

5 结语

聚合签名方案可以将多个签名者对不同消息的签名聚合成一个签名,从而有效地提高了签名的验证效率.一个安全的聚合签名方案应同时满足单个签名和聚合签名的不可伪造性要求.本文对文献［9－11］中的三个聚合签名方案进行安全性分析,并分别对这三个方案给出了具体的攻击方法,这些安全性分析对于设计安全高效的聚合签名方案具有一定的参考价值.虽然目前已有各种类型的聚合签名方案已被提出,但部分方案总体效率不高,且很多方案存在安全性缺陷,因此设计实现安全高效的聚合签名方案是有意义的研究课题.

［1］BONEH D,GENTRY C,LYNN B,SHACHAM H.Aggregate and verifiably encrypted signatures from bilinear maps［C］／／EUROCRYPT’03,LNCS 3027.Berlin：Springer－Verlag,2003：416－432

［2］BONEH D,LYNN B,SHACHAM H.Short Signatures from the Weil Pairing［C］／／ASIACRYPT’01,LNCS 2248.Berlin：Springer－Verlag,2001：514－532

［3］GENTRY C,RAMZAN Z.Identity－based aggregate signatures［C］／／PKC’06,LNCS3958.Berlin：Springer－Verlag,2006：257－273

［4］SHIM K A.An ID－Based aggregate signature scheme with constant pairing computations［J］.The Journal of Systems and Software,2010,83：1873－1880［5］杜红珍,黄梅娟,温巧燕.高效的可证明安全的无证书聚合签名方案［J］.电子学报,2013,41（1）：72－76

［6］陈 虎,魏仕民,朱昌杰,杨忆.安全的无证书聚合签名方案［J］.软件学报,2015,26（5）：1173－1180

［7］赵林森.一种基于身份的聚合签名方案［J］.计算机应用与软件,2009,26（9）：279－281

［8］周晓燕,杜伟章.基于身份和Weil对的聚合签名方案［J］.计算机工程与应用,2010,46（15）：106－108

［9］张玉磊,王彩芬.2个聚合签名方案的密码学分析与改进［J］.计算机工程,2011,37（7）：145－147

［10］李艳文,杨 庚.基于身份聚合签名方案的安全性分析与改进［J］.计算机工程与应用,2012,48（28）：101－106

［11］刘云芳,左为平.高效的可证明安全的基于证书聚合签名方案［J］.计算机应用,2014,34（9）：2664－2667

［12］Gentry C.Certificate－Based Encryption and the Certificate Revocation Problem［A］.EUROCRYPT’03［C］,LNCS 2656.Berlin：Springer－Verlag,2003：272－293

Cryptanalysis of Three Aggregate Signature Schemes

CHEN Qunshan1,ZHOU Yuping1,HAO Yanhua1,WU Chenhuang2
（1.College of Computer,MinNan Normal University,Zhangzhou 363000；2.School of Mathematical Putian University,Putian 351100,China）

An aggregate signature scheme could aggregate n signatures on n distinct messages from n signers into a single one,the aggregate signature will convince the verifier that the n signatures are validity.To analyse the security of three aggregate signatures,and present attack methods on the three schemes,which shows that these schemes could not satisfy the requirement of unforgeability.

identity－based signature；certificate－based signature；aggregate signature；security analysis

1672－2027（2016）04－0049－03

TP309

A

2016－07－21

国家自然科学基金项目（61170246,61373140）；福建省自然科学基金项目（2015J10662）福建省中青年教师教育科研项目A

类（JA14202）.

陈群山（1980－）,男,福建莆田人,硕士,闽南师范大学讲师,主要从事密码学研究.