一个高效的无证书签名方案分析与改进

刘 倩，范安东，张丽娜，张 愉

（1.成都理工大学a.管理科学学院；b.旅游与城乡规划学院，四川 成都 610059；2.西安科技大学计算机科学与技术学院，陕西 西安 710054）

一个高效的无证书签名方案分析与改进

刘 倩1a，范安东1a，张丽娜2，张 愉1b

（1.成都理工大学a.管理科学学院；b.旅游与城乡规划学院，四川 成都 610059；2.西安科技大学计算机科学与技术学院，陕西 西安 710054）

对一种基于双线性对的高效无证书签名方案进行安全性分析，表明该方案对于公钥替换攻击和恶意的密钥生成中心攻击是不安全的。提出了一种可避免这些攻击的改进方案。在随机预言机模型、离散对数问题和计算Diffie-Hellman问题困难性假设下，证明了改进方案可以抵抗自适应选择消息攻击的存在性伪造。与其他基于双线性对的无证书签名方案相比，改进方案具有较高的计算效率。

无证书签名；双线性对；公钥替换攻击；恶意密钥生成中心攻击；离散对数问题；计算Diffie-Hellman问题

0 引言

为了消除传统的基于公钥基础设施的公钥密码体制［1］（PKC）和基于身份的公钥密码体制［2］（IDPKC）存在的缺陷，解决使用证书和私钥托管的问题，2003年，无证书的公钥密码体制（CL-PKC）首次被文献［3］提出。与ID-PKC类似，CL-PKC也需要一个可信的密钥生成中心（KGC），但在CL-PKC中，用户的私钥是由用户随机选择的秘密值和KGC产生的部分私钥组成，公钥则是由用户自己的秘密值、身份信息和系统参数进行一定的运算产生的。因此，KGC不知道用户的秘密值，就无法得知任何用户的私钥，从而有效地解决了ID-PKC存在的私钥托管问题［4］。

近年来，人们设计了各种数字签名方案，如盲签名，群签名，代理签名［5］等。随着无证书公钥密码体制被提出，各种结合无证书公钥密码体制的签名方案引起了学术界的极大关注［3，6－14］。第一个无证书签名方案被文献［3］提出后，文献［6］立即指出此方案存在公钥替换攻击问题。2007年，文献［7］设计了一个改进方案并且对安全的无证书签名方案模型给出了定义。2008年，文献［8］提出了一个高效的基于ID的无证书签名方案，但文献［9］指出该方案存在公钥替换攻击的问题。2009年，文献［10］提出了在文献［11］的安全模型下的一类无证书签名方案。2010年，文献［12］提出了一个高效无证书签名方案，但文献［13］指出该方案不能阻止两类攻击，即消极不诚实KGC的公钥替换攻击和积极不诚实的KGC攻击。最近，文献［14］提出了高效安全的无证书数字签名方案，但文献［15］指出该方案是不安全的，构造了3种伪造攻击。

文献［16］设计了一种高效的无证书签名方案，验证了它在随机预言机模型下是安全的。本文对该方案进行分析，指出它既不能抵抗公钥替换攻击，也不能抵抗恶意的KGC攻击。针对这些缺陷，本文提出了一种改进方案，并在随机预言模型、离散对数问题（DLP）和计算Diffie-Hellman问题（CDHP）困难性假设下，证明了该方案的安全性，改进方案对于自适应性选择消息的攻击是不可伪造的。

1 背景知识

令G1和G2是具有相同大素数阶q的加法循环群和乘法循环群，P是G1的一个生成元，假设G1和G2中的离散对数问题是难解的。若存在一个映射＾：G1×G1→G2满足下面的性质，则称之为双线性映射：

（1）双线性：对于所有的a，b∈Z*q，P，Q∈G1，都有（aP，bQ）＝（P，Q）ab成立。

（2）非退化性：存在P，Q∈G1，使得（P，Q）≠1。

（3）可计算性：∀P，Q∈G1，能够有一个有效的算法计算＾（P，Q）。

定义1离散对数问题（DLP）：∀P，Q∈G1，求解a∈Z*q使Q＝aP成立。

定义2计算Diffie-Hellman问题（CDHP）：∀P，aP，bP∈G1，a，b∈Z*q，计算abP。

2 已有方案的安全性分析

2.1 公钥替换攻击

在CL-PKC中，用户的公钥并没有得到直接验证，从而容易遭受公钥替换攻击。通过分析发现，文献［16］方案易遭受公钥替换攻击。敌手A1可以执行以下步骤来伪造用户对消息M的签名：敌手A1随机选取δ∈Z*q，并设P′ID＝δP，然后随机选择τ∈Z*q，计算，则σ′＝（h′，V′）是身份为ID，公钥为P′ID对消息M的有效签名。容易验证：

2.2 恶意的KGC攻击

文献［16］方案无法抵抗恶意的KGC攻击，当设置系统参数的时候，恶意的KGC就针对用户设置的系统参数和用户的公钥来计算用户的私钥，因此能够伪造用户对消息的签名。伪造签名过程如下：

首先，恶意的KGC随机选取x′∈Z*q，得到用户的私钥S′ID＝x′·DID＝x′s·QID，公钥P′ID＝x′·P0＝x′s·P；然后，随机选择r′∈Z*q，计算，则σ′＝（h′，V′）可以伪造用户的签名。对伪造签名可以进行如下的验证：

综上所述，文献［16］方案对于恶意的KGC攻击是脆弱的。

3 改进方案及其分析

3.1 改进方案

通过对文献［16］方案的分析，一方面，可以通过将用户的公钥公布到系统参数中来阻止攻击者进行公钥替换攻击；另一方面，恶意的KGC很容易计算出部分私钥s·H1（ID），而且原方案中完整的私钥设计的过于简单，进而能计算出完整的私钥x·DID，为此，在KGC生成部分私钥时，可以将用户的身份信息和公钥一起绑定到H1中，对完整的私钥信息进行处理来抵挡恶意的KGC攻击。改进方案的具体描述如下：

（1）秘密值设置：身份为ID的用户随机选择一个x∈Z*q作为秘密值。

（2）公钥生成：秘密值为x的用户（身份为ID）设置其公钥为PID＝x·P。

（3）系统参数生成：输入一个安全参数k，KGC选择满足第1节性质的，G1，G2，P，计算g＝（P， P），并随机选取s∈Z*q作为系统主密钥，记P0＝sP，选择两个安全的Hash函数，设置系统参数

（4）部分私钥提取：KGC检验用户的身份ID，计算部分私钥，然后将DID返回给该用户。

（5）完整私钥生成：具有ID身份的用户把SID＝DID＋x·H1（ID，PID）∈G1作为私钥。

（6）签名算法：签名者输入身份ID，公钥PID，私钥SID和消息M进行签名，选择一个随机数r∈Z*q，计算，然后输出签名σ＝（h，V）。

3.2 改进方案的分析

3.2.1 正确性分析

对改进方案可以进行如下的正确性检验：

由此可见，改进的无证书签名方案是正确的。

3.2.2 安全性分析

在CL-PKC中存在两类敌手［3］。第一类敌手A1：A1可以替换任意用户的公钥，但是无法获得系统的主密钥以及用户的部分私钥；第二类敌手A11：A11相当于恶意的KGC攻击，无法替换任意用户的公钥，但是可以获得系统的主密钥以及用户的部分私钥。下面的定理1和定理2说明了改进方案可以抵抗两类敌手的自适应选择消息攻击的存在性伪造。

定理1在随机预言机模型和DLP、CDHP困难性假设下，改进方案可以抵抗第一类敌手A1的自适应选择消息攻击的存在性伪造。

证明假设A1是第一类敌手，C是一个CDHP的挑战者，输入为（P，aP，bP）时，挑战者C能够利用A1计算abP。

设置参数：挑战者C设置P0＝a·P，生成系统参数并发送给A1，A1可以适应性的执行以下询问。

H1询问：挑战者C维护列表L1，其格式为（ID，PID，α，QID），开始该列表为空。若A1最多执行NH1次H1询问，C在［1，NH1］中随机选取一个值J。当C收到A1对H1（IDi，Pi）的询问时，若i≠J，C随机选择αi∈Z*q，计算Qi＝αiP，Pi＝αiP0，将（IDi，Pi，αi，Qi）加入到L1中，并将Qi返回给A1；否则，C设置PJ＝βP0，αJ＝⊥，QJ＝bP，将（IDJ，PJ，αJ，QJ）加入到L1中，并将QJ返回给A1。

H2询问：C维护列表L2，列表格式为（M，ID，R，P，h），起初该列表初始化为空。当A1询问H2（Mi‖IDi‖Ri‖Pi）时，C随机选择hi∈Z*q，将（Mi，IDi，Ri，Pi，hi）加入到列表L2中，并将hi返回给A1。

部分私钥询问：若IDi＝IDJ，C终止询问；否则检查L1找到（IDi，αi，Qi），计算Di＝αiP0，并将Di返回给A1。若未询问过H1（IDi，Pi），则首先执行H1（IDi，Pi）询问。

公钥询问：C维护列表K1，其格式为（ID，x，PID），开始该列表为空。A1对IDi进行公钥询问时，C首先检查K1，若K1中有一项（IDi，xi，Pi），则C返回Pi给A1；否则，C随机选择xi∈Z*q，计算Pi＝xi·P，返回Pi给A1，将（IDi，xi，Pi）加入到K1中。

公钥替换询问：当C接到A1将用户IDi的公钥（IDi，Pi）替换为（IDi，P′i）时，C检查K1找到（IDi，xi，Pi），并设置xi＝⊥，Pi＝P′i。

秘密值询问：当C接到A1对用户IDi的秘密值询问时，C检查K1找到（IDi，xi，Pi）。若xi＝⊥，说明用户IDi的公钥已经被替换，返回⊥；否则C将xi返回给A1。

签名询问：当A1请求用户IDi对消息Mi进行签名询问时，C随机选择hi∈Z*q，Vi∈G1，并将σ*＝（hi，Vi）返回给A1。

最后，A1输出一个伪造签名（M*，σ*＝（h，V），ID*，P*）。若ID*≠IDJ，C终止询问；反之，由Forking引理［17］可知：C对A1哈希重放后选择一个哈希函数H′2，可以得到一个新的伪造签名（M*，σ*′＝（h′，V′），ID*，P*）。并且它们满足V＝r·P＋h·SID和V′＝r·P＋h′·SID，所以sQID＝abP＝（1＋β）－1×（h－h′）－1（V－V′），这与CDHP的困难性相矛盾。

定理2在随机预言机模型和DLP、CDHP困难性假设下，改进方案可以抵抗第二类敌手A11的自适应选择消息攻击的存在性伪造。

证明假设A11是第二类敌手，C是一个CDHP的挑战者，输入为（P，aP，bP）时，挑战者C能够利用A11计算abP。

设置参数：挑战者C随机选取一个s∈Z*q作为系统主密钥，计算P0＝sP，生成系统参数，将系统参数params和s发送给A11，A11可以适应性的执行以下询问。

H1询问：挑战者C维护列表L1，列表的格式为（ID，PID，α，QID），开始该列表为空。若A11最多执行NH1次H1询问，C在［1，NH1］中随机选取一个值J。当C收到A11对H1（IDi，Pi）的询问时，若i≠J，C随机选择αi∈Z*q，计算Qi＝αiP，将（IDi，Pi，αi，Qi）加入到L1中，并将Qi返回给A11；否则，C设置αJ＝⊥，QJ＝bP，将（IDJ，PJ，αJ，QJ）加入到L1中，并将QJ返回给A11。

H2询问：C维护列表L2，列表格式为（M，ID，R，P，h），起初该列表初始化为空。当A11询问时，C随机选择hi∈Z*q，将（Mi，IDi，Ri，Pi，hi）加入到列表L2中，并将hi返回给A11。

公钥询问：C维护列表K1，其格式为（ID，x，PID），开始该列表为空。A11对IDi进行公钥询问时，C首先检查K1，若K1中有一项（IDi，xi，Pi），则C返回Pi给A11；否则，C随机选择xi∈Z*q，计算Pi＝xi·P，返回Pi给A11，将（IDi，xi，Pi）加入到K1中。

秘密值询问：当C接到A11对用户IDi的秘密值询问时，C检查K1找到（IDi，xi，Pi）。若xi＝⊥，说明用户IDi的公钥已经被替换，返回⊥；否则C将xi返回给A11。

签名询问：当A11请求用户IDi对消息Mi进行签名询问时，C随机选择hi∈Z*q，Vi∈G1，并将σ*＝（hi，Vi）返回给A11。

最后，A11输出一个伪造签名（M*，σ*＝（h，V），ID*，P*）。若ID*≠IDJ，C终止询问；反之，由Forking引理［17］可知：C对A11哈希重放后选择一个哈希函数H′2，可以得到一个新的伪造签名。并且它们满足V＝r·P＋h′·SID和V′＝r·P＋h′·SID，所以xQID＝abP＝（h－h′）－1（V－V′）－sQID，这与CDHP的困难性相矛盾。

因此，在随机预言机模型和DLP、CDHP困难性假设下，改进方案可以抵抗敌手A1和A11的自适应选择消息攻击的存在性伪造。

3.2.3 效率分析

本文从运算量和安全性两个方面，将改进的新方案与其他无证书签名方案比较，比较结果如表1所示。令P、mul、exp、H分别表示双线性对运算、标量乘运算、幂运算和哈希运算。

表1 新方案与其他无证书签名方案的比较

从表1可以得出：新方案消除了公钥替换攻击和恶意的KGC攻击，运算量没有比文献［16］方案增加，与其他方案相比运算量减少了。

4 结束语

本文通过分析文献［16］方案的安全性，说明了该方案对于公钥替换和恶意的KGC攻击是不安全的。为了有效解决该方案存在的问题，提出了一种改进方案。在随机预言机模型和DLP、CDHP困难性假设下，证明了改进方案可以抵抗自适应选择消息攻击的存在性伪造。与其他基于双线性对的无证书签名方案相比，新方案只使用了两个双线性对运算，执行效率比较高。

［1］ Adams C，Lloyd S.Understanding Public-Key Infrastructure-Concepts，Standards，and Deployment Considerations［M］. Indiana，USA：Sams，1999.

［2］ Shamir A.Identity-Based Cryptosystem and Signature Scheme［C］／／Advances in Cryptology-Crypto’84，LNCS 196.Berlin：Springer-Verlag，1984：47－53.

［3］ Al-Riyami S S，Paterson K G.Certificateless Public Key Cryptography［C］／／Advances in Cryptology-ASIACRYPT’03. Berlin：Springer-Verlag，2003：452－473.

［4］ 张福泰，孙银霞，张磊，等.无证书公钥密码体制研究［J］.软件学报，2011，22（6）：1316－1332.

［5］ 蔡晓秋，王天银，张建中.基于Schnorr签名体制的前向安全的代理签名方案［J］.河南科技大学学报：自然科学版，2005，25（6）：33－36.

［6］ Huang X Y，Susilo W，Mu Y，et al.On the Security of Certificateless Signature Schemes from Asia Crypt’03［C］／／Proceedings of CANS’05.Berlin：Springer-Verlag，2005：13－25.

［7］ Huang X Y，Mu Y，Susilo W，et al.Certificateless Signature Revisited［C］／／Information Security and Privacy，ACISP 2007，LNCS 4586.Berlin：Springer-Verlag，2007：308－322.

［8］ 刘景伟，孙蓉，马文平.高效的基于ID的无证书签名方案［J］.通信学报，2008，29（2）：87－94.

［9］ 樊爱宛，任童童，鲁书喜.一种无证书签名方案的安全性分析及改进［J］.平顶山学院学报，2012，27（2）：59－64.

［10］ 张磊，张福泰.一类无证书签名方案的构造方法［J］.计算机学报，2009，32（5）：940－945.

［11］ Hu B C，Wong D S，Zhang Z，et al.Key Replacement Attack Against a Generic Construction of Certificateless Signature［C］／／Proceedings of ACISP’06.Berlin：Springer-Verlag，2006：235－246.

［12］ 梁红梅，黄振杰.高效无证书签名方案的安全性分析与改进［J］.计算机应用，2010，30（3）：685－687.

［13］ 黄明军，杜伟章.一种无证书签名方案的安全性分析及其改进［J］.计算机应用，2011，31（6）：1536－1538.

［14］ 王丽莎，张建中.一种高效安全的无证书数字签名方案［J］.计算机工程与应用，2012，48（15）：70－73.

［15］ 杜红珍.一个无证书数字签名方案的密码学分析［J］.科学技术与工程，2012，12（33）：9042－9044.

［16］ 李凤银，刘培玉，朱振方.高效的无证书签名方案［J］.计算机工程与应用，2011，47（10）：23－26.

［17］ Pointcheval D，Stern J.Security Proofs for Signature Schemes［C］／／Proceedings of the EUROCRYPT’96.Spain：Saragossa，1996：387－398.

TP309

A

1672－6871（2014）04－0049－05

四川省应用基础计划基金项目（2012JY0033）；国土资源部地学空间信息技术重点实验室开放基金项目（KLGSIT2013－08）；四川省杰出青年学科带头人培养计划基金项目（06ZQ026－014）；四川省教育厅自然科学重点基金项目（2006A116）

刘 倩（1988－），女，陕西户县人，硕士生；范安东（1970－），男，四川西充人，教授，博士，硕士生导师，主要研究方向为密码学与信息安全.

2013－10－25