無雙線性對的無證書廣義簽密方案安全性分析

周才學 劉玲

摘 要：為避免雙線性對運算較耗時的缺陷，提高（廣義）簽密方案效率，學界提出了無雙線性對運算的無證書簽密方案和無雙線性對運算的無證書廣義簽密方案。在隨機預言機模型下證明該方案滿足機密性和不可偽造性。通過具體的攻擊方法證明了前一個方案存在偽造性攻擊而后一個方案存在機密性攻擊，分析了原方案不安全的原因。通過將公鑰進行hash運算對前一個方案進行了改進，通過把簽名部分分成兩部分對后一個方案也進行了改進。對改進方案效率進行分析，結果表明改進方案安全高效。

關鍵詞：無證書簽密;無證書廣義簽密;雙線性對;公鑰替換攻擊;秘鑰托管

DOI：10. 11907/rjdk. 182473

中圖分類號：TP309

文獻標識碼：A文章編號：1672-7800（2019）006-0184-04

Abstract：To avoid the time consuming bilinear pairing operations and improve the efficiency of （generalized） signcryption schemes， we proposed a certificateless signcryption scheme and a certificateless generalized signcryption scheme without bilinear pairing， respectively. The confidentiality and unforgeability of the schemes in the random oracle model were proved. By giving concrete attacks， the former scheme was proved to be vulnerable to forgery attack and the latter one to confidentiality attack. The reason why the original schemes were insecure was analyzed. An improved scheme was given to the former one by hashing the public key and an improved scheme was given to the latter one by dividing the signature part into two parts. At last， the efficiency of the improved schemes was analyzed， which showed they were high efficient.

Key Words：certificateless signcryption; certificateless generalized signcryption; bilinear pairing; public key replacement attack; key escrow

0 引言

傳統公鑰密碼體制需要一個公鑰證書證明某個公鑰是某個人的，但是公鑰證書管理費非常昂貴。為了降低公鑰的管理費用，基于身份的密碼體制[1]被提出。但是基于身份的密碼體制又產生了新的密鑰托管問題，即可信第三方PKG（Private Key Generator）知道所有用戶的私鑰。所以基于身份的密碼體制使用只適用于對PKG絕對信任的場合。

為解決基于身份的密碼體制存在的密鑰托管問題，同時又降低公鑰的管理費用，提出了無證書密碼體制[2]。

加密可以實現信息的保密性，簽名可以實現信息的認證性。為了同時實現認證性和保密性，人們提出了簽密[3]概念。簽密能夠在一個邏輯步驟內同時實現保密性和認證性，且計算代價和通信成本比傳統的“先簽名再加密”要低得多。

廣義簽密[4]是簽密概念的進一步推廣。廣義簽密能用一個算法和一對密鑰實現加密、簽名和簽密3項功能，因而可節省系統存儲空間，降低密鑰管理成本。

無證書簽密[5]和無證書廣義簽密[6]方案常常基于雙線性對[7]實現。雙線性對是一個非常號的密碼學工具，但其計算代價較大，一個雙線性對的計算量可達到橢圓曲線上的點乘運算量的20倍[8]。因此，業界出現了設計無雙線性對運算的無證書（廣義）簽密方案。

2009年，Selvi等[9]首次提出了一個無雙線性對運算的無證書簽密方案，但沒有給出方案的安全性證明。2010年和2011年，朱輝等[10]、劉文浩等[11]和Jing[12]各提出一個無雙線性對運算的無證書簽密方案。2013年，何德彪[13]給出了方案[11]的公鑰替換攻擊，周才學等 [14]給出了方案[11]的一種偽造性攻擊和三種保密性攻擊并提出一個改進方案。由于方案[10]與方案[11]結構類似，所以以上攻擊同樣適合于方案[10]。2014年，Shi等[15]指出方案[12]不能抵抗公鑰替換攻擊并給出一個改進。2016年，鄒昌芝[16]進一步指出方案[14]也存在公鑰替換攻擊并提出一個改進方案。同年，周彥偉等 [17]指出方案[10]存在公鑰替換攻擊并給出一個改進方案。

據筆者所知，目前僅有周彥偉等[18]提出了無雙線性對運算的無證書廣義簽密方案。

方案[17]和[18]均不能達到作者所聲稱的安全性。無證書密碼體制存在兩類攻擊[6]：①攻擊者[AI]不知道系統主私鑰，但可任意替換用戶的公鑰，模擬一般用戶的攻擊;②攻擊者[AII]擁有系統主私鑰，但不能替換用戶的公鑰，模擬的是惡意的KGC （Key Generation Center）攻擊。本文通過給出具體的攻擊方法，顯示方案[17]存在[AII]攻擊者的偽造性攻擊，而方案[18]存在保密性攻擊，由此給出了一種可能的改進并分析了改進方案的效率，分析結果表明改進方案是高效的。

1 方案及安全性分析

1.1 原方案

（1） 系統初始化。給定安全參數[k]，KGC輸出滿足條件[p|q-1]的兩個大素數[p]和[q]。 設[g]為群[Z*p]中的生成元，其階為[q]。KGC選取4個安全Hash函數：[H1：{0，1}L1×][Z*p×Z*p→Z*q]，[H2：{0，1}L1×{0，1}L2×Z*p→Z*q]，[H3：Z*p→][{0，1}L2+|Z*q|]，[H4：{0，1}L1×{0，1}L2×Z*p×Z*p→][Z*q] ，其中[L1]為用戶身份ID的比特長度，[L2]為明文的比特長度，[Z*q]為[Z*q]中元素的比特長度。KGC隨機選取主密鑰[s∈Z*q]，計算[PPub=gs]，則系統公開數為[Params={p，q，g，Ppub，H1，H2，][H3，H4}]，KGC保密主密鑰[s]。

（2） 用戶密鑰生成。①用戶[IDi]隨機選取[xi∈Z*q]作為秘密值，計算[Xi=gxi]。用戶發送[IDi]和[Xi]給KGC;②KGC隨機選取[ri∈Z*q]，計算[Yi=gri]，[yi=ri+s？H1（IDi，Xi，Yi）]。KGC將[yi]通過安全信道發送給[IDi]，則[IDi]的公鑰為[PKi=（Xi，Yi）]，私鑰為[SKi=（xi，yi）];③[IDi]可以通過驗證等式[gyi=Yi？PH1（IDi，Xi，Yi）pub]確定部分私鑰和部分公鑰的正確性。

（3）簽密。設發送者[IDa]，接受者[IDb]，[m∈{0，1}L2]。[IDa]隨機選取[a∈Z*q]，計算[R=ga]，[h1b=H1（IDb，Xb，Yb）]，[h4=H4（IDa，m，Xa，R）]，[h'4=H4（IDa，m，Ya，R）]，[V=（Xb？Yb？][Ph1bpub）a]，[U=h4？（xa+ya）+a？h'4]，[C=（m||U）⊕H3（V）]，[h2=H2][（IDa，R，C）]，[S=a？（xa+ya+h2）-1]。最后，簽密密文為[σ=（h2，S，C）]。

（4）解簽密。接收者[IDb]計算[h1a=H1（IDa，Xa，Ya）]，[R=（Xa？Ya？Ph1apub？gh2）S]，[V=R（xb+yb）]，恢復消息[m||U=C⊕][H3（V）]。然后計算[h4=H4（IDa，m，Xa，R）]，[h'4=H4（IDa，m，][Ya，R）]，驗證等式[gU=（Xa？Ya？Ph1apub）h4？Rh'4] 和[h2=H2（IDa，R，][C）]是否成立。成立則接受[m]，否則拒絕。

1.2 對原方案的偽造性攻擊

設計一個[AII]攻擊者的偽造性攻擊。設發送者為[IDa]，接收者為[IDb]，[AII]隨機選取[r'a∈Z*q]，計算[Y'a=][gr'a（Xa）-1]。對任意消息[m'∈{0，1}L2]，[AII]隨機選取[a∈Z*q]，計算[R=ga]，[h1b=H1（IDb，Xb，Yb）]，[h4=H4（IDa，m'，Xa，R）]，[h'4=H4（IDa，m'，Y'a，R）]，[V=（Xb？Yb？Ph1bpub）a]，[U=h4？（r'a+s？][H1（IDa，Xa，Y'a））+a？h'4]，[C=（m'||U）⊕H3（V）]，[h2=H2（IDa，][R，C）]，[S=a？（r'a+s？H1（IDa，Xa，Y'a）+h2）-1]。最后，偽造的簽密文為[σ=（h2，S，C）]。

接收者[IDb]收到[σ=（h2，S，C）]后，計算[h1a=H1（IDa，][Xa，Y'a）]，[R=（Xa？Y'a？Ph1apub？gh2）S][=（Xa？gr'a（Xa）-1？Ph1apub？gh2）S][=（gr'a？Ph1apub？gh2）S]，[=（gr'a+s？H1（IDa，Xa，Y'a）+h2）S=ga]，[V=R（xb+yb）]，由此[IDb]可以正確地恢復消息[m'||U=C⊕H3（V）]。然后計算[h4=H4（IDa，m'，Xa，R）]，[h'4=H4（IDa，m'，Y'a，R）]，[（Xa？Y'a？][Ph1apub）h4？Rh'4=（Xa？gr'a（Xa）-1？Ph1apub）h4？Rh'4][=（gr'a？Ph1apub）h4？Rh'4=][gh4？（r'a+s？H1（IDa，Xa，Y'a））+a？h'4=gU]，從而驗證等式[gY=（Xa？Y'a？][Ph1apub）h4？Rh'4]成立。顯然另外一個驗證等式[h2=H2（IDa，R，][C）]也是成立的，從而偽造的[σ=（h2，S，C）]合法。

1.3 改進方法

用戶[IDa]的公鑰由兩部分組成，一部分是用戶自己計算的部分公鑰[Xa]，另一部分是KGC計算的部分公鑰[Ya]。這兩部分公鑰都沒有證書，于是KGC通過替換[Ya]為[Y'a]實施攻擊。這樣，對于KGC并不需要知道用戶的秘密值就可偽造用戶簽密，從而像基于身份的密碼系統一樣存在密鑰托管問題，沒有達到無證書密碼目的。這種攻擊成功的原因是因為在簽密算法中[xa]和[ya]存在簡單的線性關系。

當然這種偽造性攻擊可以被[IDa]否定。[IDa]出示部分私鑰[Ya]和[ya]，通過驗證[gya=Ya？PH1（IDa，Xa，Ya）pub]等式可以確定[Ya]和[ya]的正確性，從而說明[Y'a]不正確，這樣一來[IDa]的密鑰也就暴露了。另外，對于接收者只要簽名就能通過驗證等式，其不會去與簽名者確認[Y'a]是否正確，而對于接收者在自動執行程序時這種攻擊更有效。

一種可能的改進方法是在[ya]前加上另外一個Hash值，比如[h4=H4（IDa，m，Xa，Ya，R）]，即在簽密階段把原方案的[U=h4？（xa+ya）+a？h'4]改成[U=h4？xa+h4？ya+a？h'4]。這種改進沒有改變方案所基于的困難問題，所以采用與原方案類似的證明方法，改進方案具有安全性。

改進方案比原方案多了一次hash計算，而hash計算時間與指數運算相比可忽略不計[19]，因此改進方案是高效的。

2 無雙線性簽密方案

2.1 原方案

（1）系統初始化。給定安全參數[k]，KGC生成一個階為素數[q？（q>2k）]的循環群[G]。設[P]是[G]的一個生成元，KGC隨機選取[s∈Z*q]作為主密鑰，計算[Ppub=s？P]。KGC選取3個安全Hash函數：[H0：{0，1}L1×G×G→Z*q]，[H1：{0，1}L1×][G×G→{0，1}L2]，[H2：{0，1}L1×{0，1}L2×G×G][→Z*q] 。其中，[L1]為身份[ID]的比特長度，[L2]為明文消息[m]的比特長度。KGC定義一個特殊函數[Fun（A，ID）=0，？ID=？A，？其它]，其中[A]為非0的任意值，[ID]為身份標識，[？]表示空。則系統公開參數為[Params={q，G，P，Ppub，][Fun（），H0，H2，H2}]，KGC保密主密鑰[s]。

（2） 用戶密鑰生成。①用戶[IDi]隨機選取[xi∈Z*q]作為秘密值，計算[Xi=xi？P]。用戶發送[IDi]和[Xi]傳給KGC;②KGC隨機選取[ri∈Z*q]，計算[Yi=ri？P]，[yi=s+ri？H0（IDi，][Xi，Yi）]。KGC將[yi]通過安全信道發送給[IDi]，則[IDi]的公鑰為[PKi=（Xi，Yi）]，私鑰為[SKi=（xi，yi）]。[IDi]通過驗證等式[yi？P=Ppub+Yi？H0（IDi，][Xi，Yi）]確定部分私鑰和部分公鑰的正確性。

（3） 廣義簽密。設發送者為[IDa]，接收者為[IDb]，[m∈{0，1}L2]。[IDa]隨機選取[a∈Z*q]，計算[R=a？P]，[V=a？][（Xb+Yb？H0（IDb，Xb，Yb）+Ppub）] ， [h=Fun（H1（IDb，R，V），IDb）]，[c=m⊕h]，[h2=H2（IDa，c，Xa，R）]，[h'2=H2（IDa，][c，Ya，R）] ，[sig=Fun（ya+h2？xa+h'2？a，IDa）]。最后，簽密文為[σ=][（R，sig，c）]。①假如[IDa=？]且[IDb≠？]，則[sig=0]。[σ=（R，][sig=0，c）]是一個加密;②假如[IDa≠？]且[IDb=？]，則[h=0]。[c=m⊕h=m⊕0=m]。[σ=（R，sig，c=m）]是一個簽名;③假如[IDa≠？]且[IDb≠？]，則[σ=（R，sig，c）]是一個簽密。

（4）解廣義簽密。①如果[sig=0]，則[σ=（R，sig=0，c）]是一個加密。接收者[IDb]計算[V=（xb+yb）？R]，[h=H1（IDb，][R，V）]，恢復消息[m=c⊕h];②如果[c=m]，則[σ=（R，sig，][c=m）]是一個簽名。接收者計算[h2=H2（IDa，][c，Xa，R）]，[h'2=H2（IDa，c，Ya，R）]，驗證等式[sig？P=Ppub+][Ya？H0（IDa，][Xa，Ya）+h2？Xa+h'2？R] 是否成立。成立則接受簽名，否則拒絕;③[σ=（R，S，C）]是一個簽密。接收者[IDb]計算[h2=H2（IDa，c，Xa，R）]，[h'2=H2（IDa，c，Ya，R）]，驗證等式[sig？P=Ppub+Ya？H0（IDa，Xa，Ya）+h2？Xa+h'2？R]是否成立。如果等式不成立，則[IDb]拒絕該簽密;否則計算[V=（xb+yb）？R]，[h=H1（IDb，R，V）]，恢復消息[m=c⊕h]。

2.2 對原方案的機密性攻擊

這里顯示方案在加密模式下不具有作者所稱的機密性。根據原文安全模型，攻擊者取[IDa=？]且[IDb≠？]。攻擊者選擇兩個等長的消息[（m*0，m*1）]發送給挑戰者。 挑戰者選擇一個隨機比特[η∈{0，1}]，計算[m*η]的挑戰密文[σ*=（R*，sig*=0，c*）]返回給攻擊者，于是有[c*=m*η⊕h*]。攻擊者任取一個[m∈{0，1}L2]，計算[c'=m⊕c*]。則攻擊者生成一個與挑戰密文不同的新密文[σ'=（R*，sig*=0，c'）]。攻擊者要求挑戰者解密。顯然挑戰者返回的解密結果是[m⊕m*η]。由于知道[m]，攻擊者就可計算出[m*η]，從而正確猜測出[η]值。

2.3 討論與改進

廣義簽密算法可應用于加密、簽名和簽密3種模式，在討論安全性時要分別討論加密的安全性、簽名的安全性和簽密的安全性。在加密模式下沒有把一個IND-CPA（indistinguishability-chosen plaintext attack）安全方案轉化為IND-CCA2（indistinguishability-chosen ciphertext attack）的一般方法，比如增加Mac（message authentication code）或增加一次性簽名等，因而通過本文給出的攻擊顯示方案達不到IND-CCA2安全。一種改進是把[sig=Fun（ya+h2？xa+][h'2？a，IDa）]改成[sig=Fun（ya+h2？xa，][IDa）+h'2？a]。這樣在加密模式下[sig≠0]，從而在解密算法中就有個約束條件，要驗證等式[sig？P=h'2？R]是否成立。由于改進方案不改變算法所基于的困難問題，所以采用與原方案類似的證明方法，改進方案安全性得以證明。

由于改進方案與原方案相比沒有增加任何其它計算量，因此改進方案與原方案一樣是高效的。

3 結語

本文分析了一個無雙線性對的無證書簽密方案和一個無雙線性對的無證書廣義簽密方案，指出前一個方案存在偽造性攻擊而后一個方案存在機密性攻擊。分析了原方案不安全的原因并給出了一種可能的改進。分析了改進方案的效率，結果表明改進方案是高效的。下一步的工作是研究標準模型下的高效方案。

參考文獻：

[1] ZHOU C X. Identity based generalized proxy signcryption scheme[J]. Information Technology and Control， 2016， 45（1）： 13-26.

[2] CHEN Y C， TSO R. A survey on security of certificateless signature schemes[J]. IETE Technical Review， 2016， 33（2）： 115-121.

[3] LI F G， HAN Y N， JIN C H. Practical signcryption for secure communication of wireless sensor networks[J]. Wireless Personal Communications， 2016， 89（4）： 1391-1412.

[4] WEI G Y， SHAO J， XIANG Y. Obtain confidentiality or/and authenticity in big data by id-based generalized signcryption[J]. Information Sciences， 2015（318）： 111-122.

[5] DU H Z. Efficient certificateless signcryption from bilinear pairings[J]. International Journal of Security and its Applications， 2016， 10（4）： 303-316.

[6] ZHOU C X， ZHOU W， DONG X W. Provable certificateless generalized signcryption scheme[J]. Designs， Codes and Cryptography， 2014， 71（2）： 331-346.

[7] 李發根，吳威峰. 基于配對的密碼學[M]. 北京：科學出版社，2014.

[8] CHEN L， CHENG Z， SMART N P. Identity-based key agreement protocols from pairings[J]. International Journal Information Security， 2007，6（4）： 213-241.

[9] SELVI S S D， VIVEK S S， RANGAN C P. Cryptanalysis of certificateless signcryptionn scheme and an efficient construction without pairing[C]. 5th International Conference on Information Security and Cryptology （Inscrypt）. Beijing： Springer-Verlag， 2009： 75-92.

[10] 朱輝， 李暉， ?王育民. 不使用雙線性對的無證書簽密方案[J]. 計算機研究與發展， 2010， 47（9）： 1587-1594.

[11] 劉文浩， 許春香. 無雙線性配對的無證書簽密方案[J]. 軟件學報， 2011， 22（8）： 1918-1926.

[12] JING X. Provably secure certificateless signcryption scheme without pairing[C].2011 International Conference on Electronic & Mechanical Engineering and Information Technology. Harbin： IEEE， 2011： 4753-4756.

[13] 何德彪. 無證書簽密機制的安全性分析[J]. 軟件學報， 2013， 24（3）： 618-622.

[14] 周才學， 王飛鵬. 改進的無雙線性對的無證書簽密方案[J]. 計算機科學， 2013， 40（10）： 139-143.

[15] SHI W B， KUMAR N， GONG P， et al. Cryptanalysis and improvement of a certificateless signcryption scheme without bilinear pairing[J]. Frontiers of Computer Science， 2014， 8（4）： 656-666.

[16] 鄒昌芝. 可證安全的無證書簽密方案[J]. 計算機應用與軟件， 2016， 33（3）： 327-333.

[17] 周彥偉， 楊波， 張文政. 不使用雙線性映射的無證書簽密方案的安全性分析及改進[J]. 計算機學報， 2016， 39（6）： 1257-1266.

[18] 周彥偉， 楊波， 張文政. 可證安全的高效無證書廣義簽密方案[J]. 計算機學報， 2016， 39（3）： 543-551.

[19] HE D B， CHEN J H， HU J. An ID-based proxy signature schemes without bilinear pairings [J]. Annals of Telecommunications， 2011， 66（11-12）： 657-662.

（責任編輯：杜能鋼）