两个无证书聚合签名方案的安全性分析

罗 敏 孙 腾 张静茵 李 莉



两个无证书聚合签名方案的安全性分析

罗 敏①孙 腾*①张静茵①李 莉②

①(武汉大学计算机学院 武汉 430072)②(武汉大学国际软件学院 武汉 430072)

张玉磊等人(2015)提出了两种无证书聚合签名方案，并证明其方案在随机预言机模型下是可证明安全的。该文分析张玉磊等人提出的两种方案的安全性，指出了第1种方案可以抵抗两类攻击者的攻击；第2种方案不能抵抗第1类攻击者和第2类攻击者的攻击，给出详细的攻击过程，证明攻击者伪造出的签名可以通过验证，分析了第2种方案存在伪造攻击的原因，提出了改进的方案。

公钥密码体制；无证书聚合签名；KGC被动攻击；计算性Diffie-Hellman问题；签名伪造

1 引言

文献[1]提出了公钥密码体制思想，是现代密码学最重要的发明和进展，对于保护网络中的信息安全有着重大意义。在传统的公钥密码体制中，要求存在一个可信的认证中心给每个用户颁发一个证书，用来绑定用户身份和公钥，因此一旦用户量巨大，证书中心需要管理的证书就会剧增，极大地降低了系统的性能。为了缩减证书管理的规模，文献[2]提出了基于用户身份的公钥密码思想，即用户可以选择自己的身份信息(例如学号，邮箱地址，电话号码等)作为公钥，这样就可以有效地解决传统公钥密码体制中的证书管理问题。随着基于身份的公钥密码思想进一步发展，许多基于身份的加密签名方案被提出[3,4]。然而，基于用户身份的签名方案要求存在一个可信的私钥生成中心，用来根据用户身份生成相应的私钥，依次这种公钥密码体制面临着私钥托管问题，即私钥生成中心可以获得所有用户的私钥，从而可以伪造任意用户对任意消息的签名。

为了同时解决传统公钥密码体制中的证书管理和基于用户身份的公钥密码思想中的私钥托管问题，文献[5]提出了无证书公钥密码体制。在这种体制中，私钥生成中心仅仅生成用户的部分私钥，用户再根据私钥生成中心生成的部分私钥和自己选择的秘密值来独立地生成自己的公钥和私钥，这样就同时解决了证书管理和私钥托管两个问题，所以众多满足不同需求的无证书签名方案不断被提出，如文献[6]提出的等级无证书签名方案以及文献[7]提出的无证书群签名方案等等。

随着应用密码学的不断发展，现实中越来越多地要求个签名者对个不同的消息进行签名。传统的数字签名方案随着的不断增大，签名的长度和验证工作的复杂度都会不断提升。聚合签名能有效地解决这个问题，减少签名长度，降低签名验证和通信的开销。文献[8]首次提出了聚合签名概念，并给出了基于BLS短签名下的构造方案。文献[9]提出基于门限置换的聚合签名方案签名者将签名依次聚合，产生最后的聚合签名。文献[10]将聚合签名与无证书公钥密码机制结合起来，首次提出了无证书聚合签名方案，并给出了两个利用双线性对实现的具体方案。文献[11]提出了一个有效的无证书聚合签名方案，并基于随机预言机模型证明了其安全性。文献[12]提出了一个新型无证书聚合签名方案。文献[13]同样利用双线性对提出了无证书签名方案和无证书聚合签名方案，但文献[14]指出该方案安全性存在问题并给予了改进。

文献[15]基于双线性对提出了一个高效的随机预言机模型下的无证书聚合签名方案，并证明了基于计算性Diffie-Hellman假设，该方案在适应性选择消息攻击下是存在性不可伪造的。文献[16]对文献[15]中的无证书聚合签名方案安全性进行深入分析，指出了文献[15]中的方案依旧存在KGC被动攻击，并且为了克服原方案存在KGC被动攻击的不足，提出了两种改进方案。

本文对文献[16]中张玉磊等人提出的改进方案进行研究和安全性分析，证明了对于无证书聚合签名方案的两类攻击者来说，第1种方案可以抵抗两类攻击者的攻击，而第2种方案无法抵抗两类攻击者的攻击，一旦攻击者获取到用户对一条消息的合法有效的签名，就能够伪造出用户对其他任意消息的合法有效的签名，即第2种方案无法满足弱不可伪造性。

2 背景知识

2.1双线性对

(2)离散对数问题(Discrete Logarithm Problem, DLP)：对于未知的，给定的生成元和，没有多项式时间的算法能以不可忽略的概率计算出。

2.2无证书聚合签名方案

无证书聚合签名方案包括以下6个算法：

3 文献[16]的无证书聚合签名改进方案回顾

文献[15]提出的具体方案包括以下6个算法：

(4)部分签名生成算法：用户运行此算法的具体步骤为：

以下仅列出两种方案改进的内容：

(1)改进方案1：

(b)签名生成算法为：

(ii)验证等式(1)是否成立：

若成立则输出真，否则输出假。

(2)改进方案2：

(c)聚合签名生成算法：与原始方案相同。

(ii)验证等式(2)是否成立：

若成立则输出真，否则输出假。

4 文献[16]的改进方案的安全性分析

对于无证书聚合签名方案，一般考虑两类攻击者，1和2。其中1不能获得系统主密钥s，但可以进行公钥替换攻击，它模拟的是普通用户；2可以得到系统主密钥，但不允许进行公钥替换攻击，它模拟的是恶意的KGC。

第1类攻击者1可以进行的预言机询问如下：

第2类攻击者2由于可以获得主密钥，因此不考虑部分私钥询问，也不允许执行公钥替换询问，2可以进行的预言机询问如下：

对于无证书聚合签名方案的两种改进方法，文献[16]证明了在随机预言机模型下它们是安全的，但在本节中，我们将通过具体的伪造过程模拟两类攻击者1和2在两种改进方案中的攻击能力，分析改进方案是否真正安全。

4.1 攻击者1对于改进方案1的签名伪造过程

由于攻击者1不知道系统主密钥，但可进行公钥替换攻击，而公钥，即1可获得用户秘密值，那么1的攻击过程如下所示：

(1)1通过签名询问，输入用户身份，得到用户对消息的签名，其中,。

定理1 改进方案1面对第1类敌手1是安全的。

证明 通过上述分析可以看到，1在伪造签名时必须要计算，而计算必须获得(不能是，否则无法通过验证)，因此是1无法计算的，从而改进方案1面对第1类敌手1是安全的。

4.2攻击者1对于改进方案2的签名伪造过程

由于攻击者1不知道系统主密钥，但可进行公钥替换攻击，而公钥，即1可获得用户秘密值，那么1可以通过以下过程伪造出用户的合法有效的签名：

(1)1通过签名询问，输入用户身份，得到用户对消息的签名，其中,。

定理21通过上述方法伪造出的签名是合法有效的。

由于

验证等式成立，因此1通过上述方法伪造出的签名是合法有效的，通过这个过程，1能够伪造多个用户对多个消息的合法有效的签名，从而1也可以伪造出合法有效的聚合签名。

4.3 攻击者2对于改进方案1的签名伪造过程

由于攻击者2不能进行公钥替换攻击，但可获得主密钥，同时，因此2可获得用户部分私钥，那么2的攻击过程如下所示：

(1)2通过签名询问，输入用户身份，得到用户对消息的签名，其中,。

定理3 改进方案1面对第2类敌手2是安全的。

证明 通过上述分析可以看到，2在伪造签名时必须重新构造新的，但是在的构造中必定要出现，但是要计算，必须获得(不能是，否则无法通过验证)，因此是2无法计算的，从而改进方案1面对第2类敌手2是安全的。

4.4 攻击者2对于改进方案2的签名伪造过程

同样由于攻击者2不能进行公钥替换攻击，但可获得主密钥，同时，因此2可获得用户部分私钥，那么2可以通过以下过程伪造出用户的合法有效的签名：

(1)2通过签名询问，输入用户身份，得到用户对消息的签名，其中,。

(2)2通过签名询问，输入用户身份，得到用户对消息的签名，其中,。

定理42通过上述方法伪造出的签名是合法有效的。

由于

验证等式成立，因此2通过上述方法伪造出的签名是合法有效的，通过这个过程，2能够伪造多个用户对多个消息的合法有效的签名，从而2也可以伪造出合法有效的聚合签名。

5 原因分析和改进建议

无证书安全模型中的不可伪造性一般分为两种，弱不可伪造性和强不可伪造性。其中弱不可伪造性指的是，对于未进行过签名询问的消息，攻击者无法根据进行过签名询问的其他消息签名对伪造出对其的合法签名；强不可伪造性指的是对于进行过签名询问的消息，攻击者无法伪造出新的合法签名。显然强不可伪造性在无证书安全模型中是更强的安全性要求。

从上述具体的攻击过程可以看出，第2类改进方案存在攻击，原因在于攻击者可以实现“弱签名询问”，即攻击者在进行签名询问时，必须要提供他替换的公钥的秘密值，因此两类方案无法满足弱不可伪造性。

我们可以根据改进方案1的思想，对改进方案2进行进一步改进，使其满足弱不可伪性。即将元素嵌入,中，即使得,。这样1在伪造签名时必须计算,的值，而要计算,，必须获得，由于1无法获得，因此,是1无法计算的，从而改进方案2面对第1类敌手1是安全的；而2在伪造签名时必须重新构造新的，在的构造中必定要出现,，但是要计算,，必须要知道,的值，而要计算,，必须获得，因此,是2无法计算的，从而改进方案2面对第2类敌手2是安全的。

6 结论和效率分析

文献[15]基于双线性对提出了一种具体的无证书聚合签名方案，并在随机预言机模型中证明了其安全性，文献[16]对文献[15]的方案进行了深入分析，证明了此方案中的密钥生成中心KGC可以伪造出用户对任意消息的签名，同时为了避免这种情况提出了两种改进方案。我们对这两种改进后的方案进行了分析，通过给出具体的攻击过程，我们证明了文献[16]的两种方案中，方案1面对两类攻击者的攻击时是安全的；方案2会被两类攻击者攻击，即两类攻击者可以在方案2中伪造出合法有效的签名。

在效率方面，我们将两种最终改进方案与其他同类方案进行了对比，结果如表1所示，其中定义为双线性对运算，为中的标量乘运算，为群中的元素长度，为签名者的数量，忽略其他耗时较少的普通加法乘法及哈希函数运算。

表1无证书聚合签名方案性能比较

从表1可以看出，在签名生成阶段本文改进方案需要4个标量乘运算，虽然比其他两种同类方案多出1个标量乘运算，但由于对运算的计算量高于标量乘运算，因此本文改进方案在聚合签名验证阶段运算量小于文献[11]中的方案，和文献[13]中的方案持平。在聚合签名长度方面，本文的改进方案2中的聚合签名长度仅为2个群中的元素长度，而文献[13]中的方案和本文改进方案1中的聚合签名长度都与签名者的数量正相关。因此综合考虑，本文的改进方案2不仅能满足安全性要求，也有更高的效率，更加适合应用于实际中。

参考文献

[1] DIFFIE W and HELLMAN M E. New directions in cryptography[J]., 1976, 22(6): 644-654.

[2] SHAMIR A. Identity-based cryptosystems and signature schemes[C]. Advances in Cryptology-CRYPTO’84, Berlin, Springer-Verlag, 1984: 47-53.

[3] 王竹, 戴一齐, 顺顶锋. 普适安全的基于身份的签名机制. 电子学报, 2011, 39(7): 1613-1617.

WANG Zhu, DAI Yiqi, and YE Dingfeng. Universally composable identity-based signature[J]., 2011, 39(7): 1613-1617.

[4] DU Hongzhen and WEN Qiaoyan. An efficient identity-based short signature scheme from bilinear pairings[C]. IEEE Computer Society,Washington D.C., USA: 2007: 725-729.

[5] AL-RIYAMI S S and PATERSON K G. Certificateless public key cryptography[C]. Advances in Cryptology- ASIACRYPT’03, Berlin, Springer-Verlag, 2003: 452-473.

[6] ZHANG Lei, WU Qianhong, JOSEP D F,. Signatures in hierarchical certificateless cryptography: Efficient constructions and provable security[J]., 2014, 272(10): 223-237. doi: 10.1016/j.ins.2014.02.085.

[7] CHEN Hu, ZHU Changjie, and SONG Rushun. Efficient certificateless signature and group signature schemes[J]., 2010, 47(2): 231-237.

[8] BONEN D, GENTRY C, LYNN B,. Aggregate and verifiably encrypted signatures from bilinear maps[C]. Advances in Cryptology-EUROCRYPT’03, Berlin, Springer- Verlag, 2003: 416-432. doi: 10.1007/3-540-39200-9_26.

[9] LYSYANSKAYA A, MICALI S, REYZIN L,. Sequential aggregate signatures from trapdoor permutations[C]. Advances in Cryptology-EUROCRYPT’04, Berlin, Springer- Verlag, 2004: 74-90. doi: 10.1007/978-3-540-24676-3_5.

[10] GONG Zheng, LONG Yu, HONG Xuan,. Two certificateless aggregate signatures from bilinear maps[C]. Proceedings of the IEEE SNPD’07, Qingdao, China: 2007, 3: 188-193. doi: 10.1109/SNPD.2007.132.

[11] ZHANG Lei and ZHANG Futai. A new certificateless aggregate signature scheme[J]., 2009, 32(6): 1079-1085. doi: 10.1016/j.comcom.2008.12.042.

[12] YU Xiuying and HE Dake. New certificateless aggregate signature scheme[J]., 2014, 31(8): 2485-2487.

[13] XIONG Hu, GUAN Zhi, CHEN Zhong,. An efficient certificateless aggregate signature with constant pairing computations[J]., 2013, 219: 225-235. doi: 10.1016/j.ins.2012.07.004.

[14] HE Debiao, TIAN Miaomiao, and CHEN Jianhua. Insecurity of an efficient certificateless aggregate signature with constant pairing computations[J]., 2014, 268: 458-462. doi: 10.1016/j.ins.2013.09.032.

[15] 明洋, 赵祥模, 王育民. 无证书聚合签名方案[J]. 电子科技大学学报, 2014, 43(2): 188-193. doi: 10.3969/j.issn.1001-0548. 2014.02.005.

MING Yang, ZHAO Xiangmo, and WANG Yumin. Certificateless aggregate signature scheme[J]., 2014, 43(2): 188-193. doi: 10.3969/j.issn.1001-0548.2014.02. 005.

[16] 张玉磊, 李臣意, 王彩芬, 等. 无证书聚合签名方案的安全性分析和改进[J]. 电子与信息学报, 2015, 37(8): 1994-1999. doi: 10.11999/JEIT141635.

ZHANG Yulei, LI Chenyi, WANG Caifen,. Security analysis and improvements of certificateless aggregate signature schemes[J].&, 2015, 37(8): 1994-1999. doi: 10.11999/ JEIT141635.

Security Analysis on Two Certificateless Aggregate Signature Schemes

LUO Min①SUN Teng①ZHANG Jingyin①LI Li②

①(,,430072,)②(,,430072,)

Zhang. (2015) proposed two certificateless aggregate signature schemes, and they demonstrated that both of their schemes are provably secure in the random oracle model. This paper analyzes the security of two schemes proposed by Zhang. and indicates that the first scheme can resist the attacks by Type 1 and Type 2 adversaries, and the second scheme can not resist the attacks by Type 1 and Type 2 adversaries. The study shows the processes of concrete forgery attacks, and proves the validity of the forged signature by attackers. The reasons of forgery attacks in the second scheme are analyzed, and the modified scheme is proposed.

Public key cryptography; Certificateless aggregate signature; KGC passive attack; Computational Diffie-Hellman problem; Signature forgery

TP309

A

1009-5896(2016)10-2695-06

10.11999/JEIT151350

2015-12-01；改回日期：2016-05-27；网络出版：2016-07-14

孙腾 sunt@whu.edu.cn

国家自然科学基金(61402339)

The National Natural Science Foundation of China (61402339)

罗 敏： 男，1974年生，博士，副教授，研究方向为网络安全与数据挖掘.

孙 腾： 男，1989年生，硕士，研究方向为密码学与网络安全.

张静茵： 女，1994年生，硕士，研究方向为密码学与网络安全.

李 莉： 女，1976年生，博士，副教授，研究方向为网络安全、协议分析和编译技术.