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

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

無(wú)證書簽名方案的分析及改進(jìn)

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

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

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

在無(wú)證書的密碼體制中存在兩種類型的攻擊模型。第一種攻擊模型是密鑰替換攻擊，即第三方試圖通過(guò)破解用戶的私鑰和替換用戶的公鑰來(lái)冒充用戶，但是第三方并不知道用戶的局部私鑰。第二種攻擊模型是指惡意KGC攻擊，即假定KGC不能替換用戶公鑰，但是它能夠通過(guò)設(shè)置一些特定的系統(tǒng)參數(shù)，獲取用戶的實(shí)際私鑰，進(jìn)而冒充用戶。

文獻(xiàn)[8]提出了一個(gè)高效的無(wú)證書簽名方案，并在隨機(jī)預(yù)言模型下證明了它的安全性。本文通過(guò)對(duì)文獻(xiàn)[8]的方案進(jìn)行分析，發(fā)現(xiàn)該方案在兩種攻擊模型下都是不安全的，同時(shí)為了應(yīng)對(duì)這些問(wèn)題，給出了改進(jìn)方案，改進(jìn)后的方案具有更高的安全性。

1 預(yù)備知識(shí)

雙線性對(duì)：令G1、G2是階為素?cái)?shù)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）可計(jì)算性：?P，Q∈G1，存在一個(gè)有效的算法計(jì)算e(P，Q)。

在群G1上，可以定義以下幾個(gè)密碼學(xué)問(wèn)題：

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

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

2 簡(jiǎn)要回顧文獻(xiàn)[8]的方案

下面簡(jiǎn)要描述文獻(xiàn)[8]中提出的高效的無(wú)證書簽名方案。該方案包括7個(gè)算法，具體如下。

（1）系統(tǒng)參數(shù)生成

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

（2）部分私鑰生成

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

（3）設(shè)置秘密值

（4）設(shè)置私鑰

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

（5）設(shè)置公鑰

用戶計(jì)算其公鑰PID=xPpub。

（6）簽名

已知簽名者的身份為ID，公鑰為PID，私鑰為SID，當(dāng)要對(duì)消息m進(jìn)行簽名時(shí)，簽名者執(zhí)行以下步驟：

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

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

（7）驗(yàn)證

驗(yàn)證者收到對(duì)消息m的簽名σ后，首先計(jì)算 R′= e(V，P)e(QID，PID)-h，然后驗(yàn)證等式h=H2(m||ID||R'||PID)是否成立，當(dāng)?shù)仁匠闪r(shí)，簽名為合法簽名，否則簽名為非法簽名。

3 文獻(xiàn)[8]方案的安全性分析

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

3.1 公鑰替換攻擊

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

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

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

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

驗(yàn)證者收到攻擊者偽造的簽名σ′后，執(zhí)行以下步驟：

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

（2）計(jì)算

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

之所以攻擊者能夠偽造簽名，是因?yàn)樵谠桨钢序?yàn)證者無(wú)法驗(yàn)證公鑰的有效性，而第一類型的攻擊者可以任意地替換用戶的公鑰。

3.2 惡意KGC攻擊

假設(shè)惡意的KGC不知道用戶的公鑰，但可以產(chǎn)生特定的系統(tǒng)參數(shù)，在知道用戶的公鑰的情況下獲取用戶的私鑰。

攻擊方法如下：

（1）當(dāng)KGC產(chǎn)生系統(tǒng)參數(shù)時(shí)，取a∈Z*

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

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

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

4 改進(jìn)的方案

4.1 改進(jìn)的方案

（1）系統(tǒng)參數(shù)生成

與第2章的（1）相同。

（2）設(shè)置秘密值

（3）設(shè)置公鑰

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

（4）部分私鑰生成

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

（5）設(shè)置私鑰

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

（6）簽名

與第2章的（6）相同。

（7）驗(yàn)證

驗(yàn)證者收到對(duì)消息m的簽名σ后，首先驗(yàn)證等式e(PID，P)=e(Ppub，Px)是否成立，若成立，則可知用戶的公鑰有效，然后再驗(yàn)證簽名是否合法，先計(jì)算R′=e(V，P)e(QID，PID)-h，再驗(yàn)證h=H2(m||ID||R′||PID)是否成立，當(dāng)?shù)仁匠闪r(shí)，則簽名為合法簽名，否則簽名為非法簽名。

4.2 不可偽造性

對(duì)于普通的攻擊者，由于不知道用戶的秘密值，同時(shí)也無(wú)法獲取系統(tǒng)主密鑰，若要求出秘密值和系統(tǒng)主密鑰，無(wú)異于求離散對(duì)數(shù)問(wèn)題，所以攻擊者無(wú)法偽造簽名。

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

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

4.3 性能分析

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

現(xiàn)假設(shè)H表示Hash函數(shù)H2運(yùn)算，E表示G2中的冪運(yùn)算，P表示一個(gè)雙線性對(duì)運(yùn)算。P1表示G1中點(diǎn)的長(zhǎng)度。具體比較如表1。

表1 與原方案的比較

5 結(jié)束語(yǔ)

本文對(duì)文獻(xiàn)[8]的方案進(jìn)行安全性分析，指出其中的安全漏洞，并分析了漏洞產(chǎn)生的原因，提出了改進(jìn)的方案。文獻(xiàn)[8]中的方案由于缺乏對(duì)公鑰的有效認(rèn)證，所以無(wú)法抵抗公鑰替換攻擊，同時(shí)原方案構(gòu)造時(shí)也沒(méi)有考慮到惡意的KGC攻擊。為了解決這些問(wèn)題，提出了一個(gè)改進(jìn)的方案，提高了原方案的安全性。

[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的無(wú)證書簽名方案[J].通信學(xué)報(bào)，2008，29（2）：87-94.

[7]張磊，張福泰.一類無(wú)證書簽名方案的構(gòu)造方法[J].計(jì)算機(jī)學(xué)報(bào)，2009，32（5）：940-945.

[8]李鳳銀，劉培玉，朱振方.高效的無(wú)證書簽名方案[J].計(jì)算機(jī)工程與應(yīng)用，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

對(duì)一個(gè)無(wú)證書簽名方案進(jìn)行安全性分析，指出該方案不能抵抗公鑰替換攻擊和惡意的KGC攻擊，即攻擊者可以通過(guò)替換簽名者的公鑰來(lái)偽造任意消息的簽名，惡意的KGC（Key Generation Center）可以獲取用戶的私鑰。分析結(jié)果顯示該方案不能滿足無(wú)證書簽名方案的安全性要求，同時(shí)為了應(yīng)對(duì)這兩種攻擊，提出了改進(jìn)的方案。

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

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.

青島市科技發(fā)展計(jì)劃項(xiàng)目（No.11-2-4-6-（1）-jch）。

葛榮亮（1987—），男，碩士研究生，研究方向?yàn)槊艽a學(xué)；高德智（1963—），男，博士，教授；梁景玲（1986—），女，碩士研究生；張?jiān)疲?985—），女，碩士研究生，研究方向?yàn)樾畔踩-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