無證書簽名方案的分析及改進

葛榮亮，高德智，梁景玲，張 云

山東科技大學 信息科學與工程學院，山東 青島 266510

無證書簽名方案的分析及改進

葛榮亮，高德智，梁景玲，張 云

山東科技大學 信息科學與工程學院，山東 青島 266510

傳統的公鑰密碼系統需要管理用戶的密鑰證書，在管理證書的過程中需要大量的計算和存儲開銷，為了簡化證書的管理過程，1984年Shamir[1]首次提出了基于身份的密碼系統。然而，基于身份的密碼系統存在著固有的密鑰托管問題，為了解決這個問題，2003年Al-Riyami和Paterson[2]首次提出了無證書的密碼系統。在無證書的密碼系統中，用戶的全私鑰由密鑰生成中心KGC（Key Generation Center）和用戶一起合作生成。首先KGC生成用戶的局部私鑰，并通過安全信道發送給用戶，然后用戶結合局部私鑰和自己的秘密值產生實際私鑰，這樣就能有效地解決密鑰托管問題。無證書的密碼系統一經提出就受到了密碼學界的廣泛關注，于是一些無證書的簽名方案被相繼提了出來[3-8]。

在無證書的密碼體制中存在兩種類型的攻擊模型。第一種攻擊模型是密鑰替換攻擊，即第三方試圖通過破解用戶的私鑰和替換用戶的公鑰來冒充用戶，但是第三方并不知道用戶的局部私鑰。第二種攻擊模型是指惡意KGC攻擊，即假定KGC不能替換用戶公鑰，但是它能夠通過設置一些特定的系統參數，獲取用戶的實際私鑰，進而冒充用戶。

文獻[8]提出了一個高效的無證書簽名方案，并在隨機預言模型下證明了它的安全性。本文通過對文獻[8]的方案進行分析，發現該方案在兩種攻擊模型下都是不安全的，同時為了應對這些問題，給出了改進方案，改進后的方案具有更高的安全性。

1 預備知識

雙線性對：令G1、G2是階為素數q的加法群和乘法群，P和Q是G1的生成元，令e:G1×G1→G2是滿足下列條件的雙線性映射：

（1）雙線性：?P,Q∈G1,a,b∈e(aP，bQ)=e(P,Q)ab。

（2）非退化性：存在P，Q∈G1，滿足e(P，Q)≠1。

（3）可計算性：?P，Q∈G1，存在一個有效的算法計算e(P，Q)。

在群G1上，可以定義以下幾個密碼學問題：

離散對數（DLP）問題：設P和Q是群G1中的兩個元素，要找到某一個正數n∈使之滿足Q=nP。

計算Diffie-Hellman（CDH）問題：?a，b∈和P∈，已知(P，aP，bP)，計算abP，如果離散對數問題可解，CDH問題可解，反之，不一定成立。

2 簡要回顧文獻[8]的方案

下面簡要描述文獻[8]中提出的高效的無證書簽名方案。該方案包括7個算法，具體如下。

（1）系統參數生成

KGC選取階為q的加法循環群G1和乘法循環群G2，取G1的生成元P，設雙線性對e:G1×G1→G2。隨機選取系統主密鑰 s∈計算系統公鑰 Ppub=sP,計算 g= e(P，P)，選取Hash函數：H1:{0，1}*→G1，H2:{0，1}*→則系統參數 params={G1，G2，e，P，Ppub，g，H1，H2}。

（2）部分私鑰生成

當給定用戶身份ID，KGC計算用戶的局部私鑰DID= sQID=sH1(ID)，然后通過安全通道將DID發送給用戶。

（3）設置秘密值

（4）設置私鑰

身份為ID的用戶計算其私鑰SID=xDID。

（5）設置公鑰

用戶計算其公鑰PID=xPpub。

（6）簽名

已知簽名者的身份為ID，公鑰為PID，私鑰為SID，當要對消息m進行簽名時，簽名者執行以下步驟：

②計算h=H2(m||ID||R||PID)∈，V=rP+hSID。

③輸出簽名σ=(h，V)。

（7）驗證

驗證者收到對消息m的簽名σ后，首先計算 R′= e(V，P)e(QID，PID)-h，然后驗證等式h=H2(m||ID||R'||PID)是否成立，當等式成立時，簽名為合法簽名，否則簽名為非法簽名。

3 文獻[8]方案的安全性分析

文獻[8]的方案給出了在兩種攻擊模型下的安全性證明，其結果顯示在兩種攻擊模型下方案是安全的，但實際上該方案不能抵抗公鑰替換攻擊和惡意的KGC攻擊，即在它聲明的攻擊模式下是不安全的。

3.1 公鑰替換攻擊

攻擊者可以替換用戶的公鑰，在不知道用戶局部私鑰的情況下來偽造簽名。

現攻擊者要偽造在消息m′上的簽名，偽造方法如下：

（3）計算h′=H2(m′||ID||R′||PID)，V′=vP+h′uQID。

（4）輸出偽造簽名σ′=(h′，V′)。

驗證者收到攻擊者偽造的簽名σ′后，執行以下步驟：

（1）計算QID=H1(ID)。

（2）計算

由此可得R′=R′，即有h′=H2(m′||ID||R′||PID)，所以可知σ′=(h′，V′)是一個有效的簽名。

之所以攻擊者能夠偽造簽名，是因為在原方案中驗證者無法驗證公鑰的有效性，而第一類型的攻擊者可以任意地替換用戶的公鑰。

3.2 惡意KGC攻擊

假設惡意的KGC不知道用戶的公鑰，但可以產生特定的系統參數，在知道用戶的公鑰的情況下獲取用戶的私鑰。

攻擊方法如下：

（1）當KGC產生系統參數時，取a∈Z*

q，設置參數P=aH1(ID)。生成用戶的局部私鑰DID=sQID=sH1(ID)。

（2）用戶獲取局部私鑰后，計算私鑰SID=xDID，公鑰PID=xPpub，并公布公鑰PID。

（3）惡意的KGC獲得公鑰后，計算a-1PID=a-1xPpub= a-1xsP=a-1xsaH1(ID)=xsH1(ID)=SID。進而獲得了用戶的私鑰SID，所以可知原方案無法抵抗惡意的KGC攻擊。

4 改進的方案

4.1 改進的方案

（1）系統參數生成

與第2章的（1）相同。

（2）設置秘密值

（3）設置公鑰

用戶計算其公鑰＜Px，PID＞=＜xP，xPpub＞。

（4）部分私鑰生成

當給定用戶身份ID，KGC計算用戶的局部私鑰DID= sQID=sH1(ID||PID)，然后通過安全通道將DID發送給用戶。

（5）設置私鑰

身份為ID的用戶計算其私鑰SID=xDID。

（6）簽名

與第2章的（6）相同。

（7）驗證

驗證者收到對消息m的簽名σ后，首先驗證等式e(PID，P)=e(Ppub，Px)是否成立，若成立，則可知用戶的公鑰有效，然后再驗證簽名是否合法，先計算R′=e(V，P)e(QID，PID)-h，再驗證h=H2(m||ID||R′||PID)是否成立，當等式成立時，則簽名為合法簽名，否則簽名為非法簽名。

4.2 不可偽造性

對于普通的攻擊者，由于不知道用戶的秘密值，同時也無法獲取系統主密鑰，若要求出秘密值和系統主密鑰，無異于求離散對數問題，所以攻擊者無法偽造簽名。

在第一類型的攻擊模型下，攻擊者可以替換用戶的公鑰＜Px，PID＞，但是不知道系統主密鑰s。由于在驗證階段，需要驗證等式e(PID，P)=e(Ppub，Px)，在此等式中有系統主密鑰s的參與，而攻擊者不知道s而且無法消除s的影響，所以攻擊者無法偽造簽名。

在第二類型的攻擊模型下，惡意的KGC可以產生特定的系統參數，但是無法替換用戶的公鑰。用戶首先生成了公鑰，然后KGC使用用戶公鑰生成局部私鑰，這樣系統參數必須在生成用戶局部私鑰之前生成，從而惡意的KGC無法產生特定的系統參數，所以改進的方案能夠抵抗惡意KGC攻擊。

4.3 性能分析

改進的方案，在簽名階段與原方案步驟一致，在驗證簽名階段，增加了公鑰驗證的過程，即e(PID，P)=e(Ppub，Px)。

現假設H表示Hash函數H2運算，E表示G2中的冪運算，P表示一個雙線性對運算。P1表示G1中點的長度。具體比較如表1。

表1 與原方案的比較

5 結束語

本文對文獻[8]的方案進行安全性分析，指出其中的安全漏洞，并分析了漏洞產生的原因，提出了改進的方案。文獻[8]中的方案由于缺乏對公鑰的有效認證，所以無法抵抗公鑰替換攻擊，同時原方案構造時也沒有考慮到惡意的KGC攻擊。為了解決這些問題，提出了一個改進的方案，提高了原方案的安全性。

[1]Shamir A.Identity-based cryptosystems and signature schemes[C]// LNCS 196：Advances in Cryptology-Crypto'84.Berlin：Springer-Verlag，1984：47-53.

[2]AL-Riyami S，Paterson K.Certificateless public key cryptography[C]//LNCS 2894：AdvanceinCryptography Asiacrypt 2003.Berlin：Springer-Verlag，2003：452-473.

[3]Gorantla M C，Saxena A.An efficient certificateless signature scheme[C]//Proc of CIS'05.Berlin，Germany：Springer-Verlag，2005：110-116.

[4]Huang Xinyin，Mu Yi，Susilo W，et al.Certificateless signature revisited[C]//LNCS 4586：Proc of Acisp 2007.Berlin：Springer，2007：308-322.

[5]Zhang L，Zhang F T，Zhang F G.New efficient certificatelesssignaturescheme[C]//ProceedingsoftheEUC Workshops 2007.Taipei，China：[s.n.]，2007：692-703.

[6]劉景偉，孫蓉，馬文平.高效的基于ID的無證書簽名方案[J].通信學報，2008，29（2）：87-94.

[7]張磊，張福泰.一類無證書簽名方案的構造方法[J].計算機學報，2009，32（5）：940-945.

[8]李鳳銀，劉培玉，朱振方.高效的無證書簽名方案[J].計算機工程與應用，2011，47（10）：23-26.

GE Rongliang,GAO Dezhi,LIANG Jingling,ZHANG Yun

College of Information Science and Engineering,Shandong University of Science and Technology,Qingdao,Shandong 266510,China

This paper analyzes a certificateless signature scheme,and points out the scheme can't resist to the public key replacement attack and the malicious KGC（Key Generation Center）attack.The attacker can forge the signature for any message by substituting the public key of the signer.The malicious KGC can get the private key.The analysis shows that the scheme can not satisfy the safety requirements of the certificateless signature.Meanwhile the improvement measure is proposed to resist these attacks.

certificateless signature;public key replacement attack;malicious Key Generation Center（KGC）attack;bilinear pairing

對一個無證書簽名方案進行安全性分析，指出該方案不能抵抗公鑰替換攻擊和惡意的KGC攻擊，即攻擊者可以通過替換簽名者的公鑰來偽造任意消息的簽名，惡意的KGC（Key Generation Center）可以獲取用戶的私鑰。分析結果顯示該方案不能滿足無證書簽名方案的安全性要求，同時為了應對這兩種攻擊，提出了改進的方案。

無證書簽名；公鑰替換攻擊；惡意密鑰生成中心（KGC）攻擊；雙線性對

A

TP309

10.3778/j.issn.1002-8331.1108-0327

GE Rongliang,GAO Dezhi,LIANG Jingling,et al.Security analysis and improvement of certificateless signature scheme.Computer Engineering and Applications,2013,49（5）：96-98.

青島市科技發展計劃項目（No.11-2-4-6-（1）-jch）。

葛榮亮（1987—），男，碩士研究生，研究方向為密碼學；高德智（1963—），男，博士，教授；梁景玲（1986—），女，碩士研究生；張云（1985—），女，碩士研究生，研究方向為信息安全。E-mail：gerl123@yahoo.cn

2011-08-24

2011-10-17

1002-8331（2013）05-0096-03

CNKI出版日期：2011-12-09 http://www.cnki.net/kcms/detail/11.2127.TP.20111209.1001.022.html