无证书签名方案的分析及改进

葛荣亮，高德智，梁景玲，张 云

山东科技大学 信息科学与工程学院，山东 青岛 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