兩個無證書聚合簽名方案的安全性分析

羅 敏 孫 騰 張靜茵 李 莉

?

兩個無證書聚合簽名方案的安全性分析

羅 敏①孫 騰*①張靜茵①李 莉②

①(武漢大學計算機學院 武漢 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年生，博士，副教授，研究方向為網絡安全、協議分析和編譯技術.