改进的无对映射的无证书代理签名方案

汤鹏志，张庆兰，杨俊芳

(华东交通大学 理学院;华东交通大学 系统工程与密码学研究所，南昌 330013)

2003 年，Al－Riyami 和Paterson［1］第一次提出无证书密码体制的概念，同时，并提出了首个无证书签名方案。这种签名方案的部分密钥是由用户和KGC 共同协议产生，解决了基于身份的密码系统中的密钥托管问题。2004 年，Yum 等［2］首次提出无对映射的无证书签名方案。但是，Hu 等［3］指出文献［2］中的方案不能抵抗公钥替换攻击，并在此基础上，提出了一个改进的无双线性对的无证书签名方案。此后，大量的无证书签名方案被提出。［4－9］

1996 年，Mambo，Usuda 和Okamoto［10，11］提出了代理签名。此后，大多数的代理签名方案是在基于证书，或者基于身份的密码体制的基础上提出的。2005 年，Li 等［12］第一次提出了一个无证书代理签名方案。但是，Lu 等［13］指出文献［12］的方案，任何人都能够冒充代理签名者，伪造一个有效的代理签名的缺陷，同时也给出了改进的方案。2010年，许春根等人［14］提出了一种基于离散对数问题的无证书代理签名方案，该方案代理密钥利用Schnorr 短签名产生，计算效率较高;2012 年，张俊茸等人［15］给出了一种新的无证书代理环签名方案，将无证书密码体制、代理签名和环签名三种密码体制的优点结合起来，具有比较高的实用性。2012 年，王圣宝等人［16］提出了一种无双线性配对的无证书签名方案。通过对文献［14］中的方案的分析，发现方案存在公钥被替换的风险，然后结合代理签名，给出了一种改进的基于无对映射的无证书代理签名方案。

1 困难问题

定义1 (DLP 假设)设G 是阶为q 的一个循环群，P 为G 的生成元，对于任意的u ∈Z*q ，已知uP，P，计算u 是离散对数问题，在概率多项式时间(PPT)内，对于任意算法Α，解决DLP困难问题 的优势AdvDLP(Α) = Pr［Α(uP，P) =是可忽略的。

2 文献［16］中的无证书签名方案与安全性分析

2.1 回顾文献［16］中的签名方案

具体方案见文献［16］中的新方案。

2.2 文献［16］中方案的安全性分析

通过对文献［16］中方案的安全性分析发现，方案存在公钥替换攻击，具体的攻击方案参考文献［17］。假设A 为签名者，B 为签名验证者，AI可以查询或者替换A 的公钥。A 的私钥为(xA，DA)，公钥为(XA，RA)，B 的私钥为(xB，DB)，公钥为(XB，RB)。第一类型的攻击者AI冒充签名者A 对消息m 进行签名:

⑴攻击者AI随机选择，w ∈，计算=P = wP－RA－H1(IDA，RA)y;

⑵AI用替换A 的公钥XA(替换A 的私钥xA)，将发送给B，B 把当成A 的公钥;

⑶签名:AI随机选择整数a ∈Z*q ，然后并计算TA= aP，h*= H2(TA|||| IDA|| m)，=将签名σ =发送给签名验证者B;

⑷签名验证:当B 接收到签名σ = (h*，，)和RA，计算h1= H1(IDA，RA)，

由上述等式分析可知，攻击者AI伪造的签名通过了验证者B 的验证。

所以，当攻击者AI替换用户的公钥之后，签名验证者B 无法察觉，即该签名方案有被伪造的的可能。

3 方案改进

3.1 系统参数选取阶段

KGC 利用算法L(1k)，生成参数(G1，q，P)，其中G1是阶为素数q 的循环加法群，P 为G1的生成元。并且在G1中离散对数是难解的。选择安全hash 函数:H1:{0，1}*× G1× G1→，H2:{0，1}*× {0，1}*× {0，1}*→G1，H3:{0，1}*× {0，1}*→G1，H4:{0，1}*×{0，1}*×{0，1}*×G1×G1→G1，KGC 选择s 作为系统主私钥，计算系统主公钥Ppub= sP。系统公开参数为{G1，P，q，Ppub，H1，H2，H3，H4}。

3.2 用户密钥生成阶段

对于身份为IDi的用户，随机选择整数xi∈Z*

q ，计算PKi= xiP 作为用户的长期公钥，然后将PKi发送给KGC，KGC 随机选取ri∈Z*q ，计算部分公钥Ri= riP，部分私钥Xi= ri+ sQi，其中Qi= H1(IDi，Ri，PKi)。KGC 将Ri公开，通过安全信道将Xi发送给用户。用户接收到KGC 生成的部分密钥后，可以验证等式Ri+ H1(IDi，Ri，PKi)Ppub= XiP 是否成立，若成立，则说明KGC 生成的密钥合法，接受该密钥，否则拒绝。这样，身份为IDi的用户的完整私钥是(xi，Xi)，完整公钥是(Ri，PKi)。

3.3 代理密钥生成阶段

⑴代理授权阶段

假设A 为原始签名者，B 为代理签名者，原始签名A 人给出一个授权证书mw，授权证书描述了原始签名人，代理签名人的身份信息，授权范围，代理期限等。A 随机选择kA∈Z*q ，计算KA= kAPpub，Sw= xAH2(IDA，KA，mw)+XA，A 将授权签名(Sw，mw，KA)发送给代理签名者B。

⑵代理密钥生成阶段

代理签名者B 收到(Sw，mw，KA)之后，计算QA= H1(IDA，RA，PKA)，然后验证等式SwP = PKA·H2(IDA，KA，mw)+ RA+ QAPpub是否成立。如果成立，则生成代理签名私钥xp= Sw+ xB·H3(mw，IDB)，否则，终止代理过程。

3.4 代理签名阶段

3.5 代理签名验证阶段

当验证者收到B 的签名σ = (s，h)后，计算QA= H1(IDA，RA，PKA)，QB= H1(IDB，RB，PKB)，然后验证s(PKA·H2(IDA，KA，mw)+ RA+ (QA+QB)Ppub+PKB·H3(mw，IDB)+RB+hP)= TB是否成立。若成立，则σ = (s，h)是一个有效的代理签名，否则，签名无效。

4 安全与效率分析

4.1 方案正确性

验证等式成立，所以该代理签名有效。

4.2 随机预言机下可证安全性

对于无证书签名方案一般都存在以下两类攻击者:

(类型1)攻击者AI无法获得系统的主密钥，但是可以替换任意用户的长期公钥;

(类型2)攻击者AII不能替换用户的长期公钥，但可以获得系统的主密钥。

定理2 (类型1 攻击下的不可伪造性)在随机预言机模型和DL 困难问题假设下，对于类型1的攻击者AI，改进的方案在适应性选择消息和选择身份攻击下是存在性不可伪造的。

证明:假设算法C 能解决DL 问题，即输入y= uP，输出u。以算法C 模拟挑战者，与攻击者AI进行交互游戏。假设AI在概率多项式时间内，可向挑战者C 进行多项式有限次H1询问，H2询问，H3询问，H4询问，部分私钥提取询问，部分公钥提取询问，长期密钥提取询问，代理密钥提取询问，公钥替换询问，代理签名询问;列表LH1、LH2、LH3、LH4、LBS、LBG、LCM、LPR、LGT、LQM用于记录每次询问的情况。

系统参数设置:挑战者C，生成系统参数{G1，q，P，Ppub，H1，H2，H3，H4}，并将系统参数发送给攻击者AI;假设系统主公钥Ppub= uP，u (未知)为系统主密钥;目标用户ID*= IDk。

(1)H1询问

当挑战者C 收到攻击者AI关于(IDi，Ri，PKi)的H1询问，C 先查询列表LH1，如果(IDi，Ri，PKi，h1i)在列表LH1中，则C 将h1i返回给A1;否则，C随机选择h1i∈Z*q ，将其作为回答返回给AI，并且将(IDi，Ri，PKi，h1i)添加到列表LH1中。

(2)H2询问

当挑战者C 收到攻击者AI关于(IDi，Ki，mw)的H2询问，C 首先查询列表LH2，如果(IDi，Ki，mw，h2i)在列表LH2中，则C 将h2i返回给AI;否则，C 随机选择h2i，将h2i作为回答返回给AI，并且将(IDi，Ki，mw，h2i)添加到列表LH2中。

(3)H3询问

当挑战者C 收到攻击者AI关于(IDi，mw)的H3询问，Q 首先查询列表LH3，如果(IDi，mw，h3i)在列表LH3中，则C 将h3i返回给AI;否则，C 随机选择h3i，将h3i作为回答返回给AI，并且将(IDi，mw，h3i)添加到列表LH3中。

(4)H4询问

当挑战者C 收到攻击者AI关于(IDi，IDj，m，Ti，PKi)的H4询问，Q 首先查询列表LH4，如果(IDi，IDj，m，Ti，PKi，hi)在列表LH4中，则C 将hi返回给AI;否则，C 随机选择hi，将hi作为回答返回给AI，并且将(IDi，IDj，m，Ti，PKi，hi)添加到列表LH4中。

(5)部分私钥提取询问

当C 收到AI关于IDi的部分私钥询问，C 首先查询列表LBS，如果(IDi，Xi)在列表LBS中，则Q将Xi返回给AI;否则:

(a)当i = k 时，终止算法;

(b)当i ≠k 时，Q 先执行H1询问得到h1i，随机选择ri∈Z*q ，计算Xi= ri+ sh1i，将计算得到的Xi作为答复发送给AI，并将(IDi，Xi)记录到列表LBS中。

(6)部分公钥提取询问

当C 收到AI关于IDi的部分公钥询问，C 首先查询列表LBG，如果(IDi，Ri)在列表LBG中，则C将Ri返回给AI;否则，C 随机选择ri，计算Ri=riP，将Ri发送给AI，同时把(IDi，Ri)记录到列表LBG中。

(7)用户长期密钥提取询问

当C 收到AI关于IDi的长期密钥钥提取询问，C 先检查列表LCM，若(IDi，xi，PKi)在列表LCM中，那么C 将相应的(xi，PKi)发送给AI;否则，C 随机选择xi∈Z*q ，计算PKi= xiP，将(xi，PKi)发送给AI，将(IDi，xi，PKi)添加到列表LCM。

(8)公钥替换询问

当C 收到AI关于IDi的公钥替换询问时，C 随机选择x'i∈Z*q ，计算PK'i，用PK'i替换用户公钥PKi，并将(IDi，x'i，PK'i)记录到列表LTH中。

(9)代理密钥询问

当C 收到AI关于IDi的代理密钥提取询问，C先检查列表LPR，若(IDi，xi，PKi)在列表LCM中，那么C 将相应的(xi，PKi)发送给AI;否则，C 随机选择ki∈Z*q ，计算Ki= kiPpub，执行H2、H3询问和部分私钥询问获得h2i、h3i和Xi，计算Swi=xi·h2i+ Xi，xpi= Swi+ xi·h3i。将xpi发送给AI，将(IDi，xpi)添加到列表LPR。

(10)代理签名询问

当C 收到AI关于(IDi，IDj)和mi的代理签名询问时，其中IDi为代理签名者，原始签名者为IDj。C 首先查询列表LQM，若(IDi，IDj，mi，hi，si)已经在列表中，则将相应的代理签名数据发送给AI;否则:

(b)当i = k 时，C 随机选择hk，sk∈Z*q ，执行H1询问、H1获得h1k和h3k，查询列表LBG和LCM获得Rk和PKk，计算Tk= sk·(Swk+PKk·h3k+Rk+ h1k·Ppub+ hkP)。将相应的代理签名数据σk=(hk，sk，mk)发送给AI，并将(IDk，IDj，mk，hk，sk)添加到列表LQM中。

伪造过程:AI执行多项式有限次询问后，在多项式时间内，以不可忽略的概率，可以输出对消息m 的有效的签名数据，即AI随机选择a，s'i∈Z*

由上述过程可知，AI通过向C 进行多项式有限次询问后，伪造出一个有效的签名，挑战者C根据伪造出的签名，在多项式内，解决了DLP，但是这与DLP 的困难性矛盾，所以在随机预言机模型和DLP 困难性的假设下，该方案是存在性不可伪造的。

定理4 (类型2 攻击下的不可伪造性)在随机预言机模型和DLP 困难问题假设下问题假设下，对于类型2 的攻击者AII，改进的方案在适应性选择消息和选择身份攻击下是存在性不可伪造的。

证明:假设算法C 能解决DL 问题，即输入y= vP，输出v(v 为代理签名者的私钥)。

攻击者AII在多项式时间内，可向C 进行多项式有限次H1询问，H2询问，H3询问，H4询问，部分密钥提取询问，用户长期私钥提取询问，公钥提取询问，代理密钥询问，代理签名询问;列表LH1、LH2、LH3、LH4、LBM、LSK、LPK、LPR、LQM用于记录每次询问的情况。

(1)H1、H2、H3和H4询问过程与定理1 相同

(2)部分密钥提取询问

当C 收到AII关于IDi的部分密钥询问，C 首先查询列表LBM，如果(IDi，Ri，Xi)在列表LBM中，则C 将(Ri，Xi)返回给AII;否则:C 先执行H1询问，获得h1i，随机选择ri∈Z*q ，计算Ri= riP，Xi= ri+ sh1i，把(Ri，Xi)发送给AII，并将(IDi，Ri，Xi)记录在列表LBM中。

(3)用户长期私钥提取询问

当C 收到AII关于IDi的长期私钥提取询问，Q先检查列表LSK。若(IDi，xi)在列表LSK中，那么C 将相应的xi发送给AII;否则:

(a)当i ≠k 时:C 随机选择xi∈z*q ，计算PKi= xiP。把(IDi，xi)添加到列表LSK中，并将相应的xi发送给C;

(b)当i = k 时:终止算法。

(4)用户长期公钥提取询问

当C 收到AII关于IDi的公钥提取询问，C 首先检查列表LPK。若(IDi，xi，PKi)在列表LPK中，则将PKi返回给A2;否则:

(a)当i ≠k 时:C 随机选择xi∈Z*q ，计算PKi= xiP 将PKi发送给AII，并把(IDi，xi，PKi)添加到列表。

(b)当i = k 时:用户IDk的公钥为PKk= uP，用⊥来表示用户的长期私钥，将PKk发送给AII，并把(IDi，⊥，PKi)添加到列表LPK中。

(5)代理密钥提取询问

当C 收到AII关于IDi的代理密钥提取询问，C先检查列表LPR，若(IDi，xi，PKi)在列表LCM中，那么C 将相应的(xi，PKi)发送给AI;否则:

(a)当i ≠k 时，C 随机选择ki∈Z*q ，计算Ki= kiPpub，执行H2、H3询问和部分私钥询问获得h2i、h3i和Xi，计算Swi= xi·h2i+ Xi，xpi= Swi+ xi·h3i。将xpi发送给AI，将(IDi，xpi)添加到列表LPR。

(b)当i = k 时:终止算法。

(6)代理签名询问

伪造过程:AII执行多项式有限次询问后，在多项式时间内，以不可忽略的概率，可以输出对消息m 的有效的签名数据，即AII随机选择a，s'i∈Z*

q ，计算T'i= (a + xi)P，h'i= H4(IDi，IDi，m，Ti，PKi)，h1i= H1(IDi，Ri，PKi)，然后输出对m的伪造签名σ'i= (h'i，s'i)。假设伪造签名有效，挑战者C 输出作为DL 问题的答案;否则，C 无法解决DL 问题。

由上述过程可知，AII通过向C 进行多项式有限次询问后，伪造出一个有效的签名，挑战者C根据伪造出的签名，在多项式内，解决了DLP，但是这与DLP 的困难性矛盾，所以在随机预言机模型和DLP 困难性的假设下，该方案是存在性不可伪造的。

5 小结

在王圣宝［16］等人的方案的基础上，与代理签名相结合，给出了一种能抵抗公钥替换攻击的无对映射的代理签名方案。改进的代理签名方案增加授权和代理密钥生成的过程，安全性更高，而且改进的方案没有双线性的运算，效率高，计算量小。同时，也给出了在随机预言机模型和困难问题的假设下，改进方案的在两种类型攻击下的不可伪造性的具体的证明过程。

［1］ AL－RIYAMI SS，PATERSON KG.Certificateless public key cryptography［A］.Proc of Asiacrypt 2003 ［C］.Springer－Verlag，Berlin，2003:452－473.

［2］ YUM DH，LEE PJ.Generic construction of certificateless signature［A］.In Information Security and Privacy:9th Australasian Conference，ACISP 2004［C］.Springer－Verlag，2004:200－211.

［3］HU B，WONG D，ZHANG Z，et al.Key replacement attack against a generic construction of certificateless signature［A］.Proc of 11th Australasian Conference on Information Security and Privacy［C］.Melbourne，Australia，2006:235－246.

［4］ HUANG X，SUSILO W，MU Y，et al.On the security of certificateless signature schemes［A］.Asiacrypt 2003［C］.2005:13－25.

［5］ GORANTLA MC，SAXENA A.An efficient certificateless signature scheme［A］.Proc of CIS’05［C］.Springer－Verlag，2005:110－116.

［6］CAO X，PATERSON KG，KOU W.An Attack on a Certificateless Signature Scheme［R］.Cryptology ePrint Archive，2006.

［7］ CHOI KY，PARK JH，HWANG J，et al.Efficient certificateless signature schemes［A］.Proc of ACNS’07［C］.Springer－Verlag，2007:443－458.

［8］ SHIM KA.Breaking the short certificateless signature scheme［J］.Information Sciences，2009，179(3):303－306.

［9］ YUAN Y，LI D，TIAN L，et al.Certificateless signature scheme without random oracles［A］.ISA 2009［C］.2009:31－40.

［10］M Mambo，K Usuda，E Okamoto.Proxy signatures:Delegation of the Power to sign messages ［J］ .IEICE Trans.Fundamentals，1996，79(9):1338－1353.

［11］M Mambo，K Usuda，E Okamoto.Proxy signatures for delegating signing operation［A］.3rdACM Conference on Computer and Communications Security(CCS.96)［C］. New York:ACM Press，1996:48－57.

［12］Li X，Chen K，Sun L.Certificateless Signature and Proxy Signature Schemes from Bilinear Pairings［J］.Lithuanian Mathematical Journal，2005，45(1):76－83.

［13］Lu Rongbo，He Dake，Wang Changji.Cryptanalysis and Improvement of a Certificateless Proxy Signature Scheme from Bilinear Pairings［C］.Qingdao:Proc of the 8th ACIS International Conference on Software Engineering，Artificial Intelligence，Networking and Parallel/Distributed Computing，2007:285－290.

［14］许春根，张傲红，陈海滨. 一种基于离散对数问题的无证书代理签名方案［J］. 南京理工大学学报(自然科学版)，2010，34(6):733－737.

［15］张俊茸，任平安，韩牟，等. 一种新的无证书的代理环签名方案［J］. 计算机工程与应用，2012，48(2):63－65.

［16］王圣宝，刘文浩，谢琪. 无双线性配对的无证书签名方案［J］. 通信学报，2012，33(4):93－98.

［17］何德彪. 无证书签密机制的安全性分析［J］.2013，24(3):618－622.