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

刘二根，周华静，2，王 霞，2，郭红丽，2

（华东交通大学1.理学院；2.系统工程与密码学研究所，江西 南昌330013）

数字签名是现代密码学的一个重要领域，最早的数字签名是基于证书的，而基于证书的密码学体制存在着证书的颁发，存储，撤销等问题。因此，解决此类问题成为密码学领域的重要研究方面。1985年，Shamir［1］第一次提出基于身份的密码学体制，在该体制下，用户密钥生成完全依赖密钥生成中心（KGC），因此，又不可避免地存在密钥托管问题。随着密码学的日益发展，2003年，Al-Riyami等［2］提出的无证书密码体制，既解决了传统的基于证书密码体制下繁琐的证书管理问题，也解决了基于身份密码体制下的密钥托管问题。基于无证书密码体制的种种优点，该体制一经提出便得到学者们的广泛关注。2005年，Huang等［3］首次比较详细地给出无证书签名方案安全模型的定义，并提出一个具体的基于无证书的签名方案。2007年，Liu等［4］也提出一个无证书签名方案。在接下来的几年里，无证书签名不断发展，学者们先后提出各种无证书签名方案。2008年，樊睿等［5］提出一个效率较高的无证书代理签名方案。2010年，李明祥等［6］提出一个高效的无证书部分盲签名方案。2014年，樊爱宛等［7］提出一个强安全的无证书签名方案，同年又提出另一个无证书签名方案［8］。随后，刘倩等［9］对一个无证书签名方案进行安全性分析，发现其对于两类攻击者的攻击并不安全，因此提出改进方案。通过对文献［9］的分析，发现仍然存在公钥替换攻击且效率不高，在此基础上进行改进，提出新的无证书签名方案。并对改进后的方案进行安全性证明和效率分析。

1 预备知识

1.1 困难问题及假设

定义1离散对数问题（DLP）：设G是一个椭圆曲线群，已知aP∈G，a∈Z*q，其中P为G的生成元，求解a的问题称为离散对数问题。

假设1离散对数困难性假设：如果不存在一个概率多项式时间（PPT）的算法，在时间t内，以一个大于0的概率ε解得群G上的DL问题，则称离散对数困难性假设成立。

1.2 攻击者类型［2］

在无证书密码体制中存在两种类型的攻击者AⅠ和AⅡ，分别具有不同的能力。①类型Ⅰ攻击者AⅠ：AⅠ不知道系统主密钥，但是可以任意替换用户公钥；②类型Ⅱ攻击者AⅡ：AⅡ知道系统主密钥，但是不知道用户个人私钥，也不能替换用户公钥。

2 文献［9］方案分析

2.1 方案回顾

文献［9］提出一个改进的无证书签名方案。方案由系统参数生成、秘密值生成、公钥生成、私钥生成、签名及验证这6个算法组成，方案具体描述如下。

1）系统参数生成：设置系统安全参数为k，KGC（Key Generator Center）选取阶为q的加法循环群G1和乘法循环群G2，其中q≤2k且为素数。双线性对映射为e:G1×G1→G2，选取群G1的一个生成元为P∈G1，并随机选取s∈RZ*q作为系统主密钥，计算Ppub为系统公钥，g为公钥参数。选择两个安全哈希函数H1:{0,1}*×G1→G1，H2:{0,1}*×{0,1}*×G1×G1×G1→Z*q，则系统公开参数可表示为params={q,e,g,G1,G2,P,Ppub,H1,H2}，公开params，保密主密钥s。

2）秘密值生成：签名者A随机选取xA∈Z*q作为自己的秘密值并保存。

3）公钥生成：签名者A计算PKA=xAP作为自己的公钥，将其公开。

4）私钥生成：①部分私钥：设签名者A的身份为IDA，KGC 计算DA=sQA=sH1(IDA)∈G1，将DA作为签名者A的部分私钥，通过秘密信道发送给A；②完整私钥：签名者A收到DA后，计算SA=DA=xA·H1(IDA，PKA)∈G1，则用户完整私钥为SA。

5）签名：签名者A的身份为IDA，签名私钥为SA，待签名消息为m∈{0,1}*，由A执行签名算法。A随机选取一个随机数r∈RZ*q，计算R=gr∈G2，h=H2(m｜｜IDA｜｜R｜｜PKA)∈Z*q，V=r·P+h·SA∈G1，则签名为σ=(h,V)。

6）验证：验证者收到签名后首先计算h=H2(m｜｜IDA｜｜R｜｜PKA)，如果等式e(V,P)e(QA,Ppub+PKA)-h=R成立，则说明签名有效，接受签名，输出1；否则，拒绝，输出0。

2.2 安全性与效率分析

通过对上述方案的分析，发现存在如下缺陷。

缺陷一：该方案存在公钥替换攻击，存在一个类型Ⅰ的攻击者F，可以替换用户公钥，具体攻击为：

攻 击 者F将 签 名 者A的 公 钥 替 换 为PK′A=P-Ppub，并 随 机 选 取 随 机 数 为r′∈RZq*，则R′=gr′，h′=H2(m｜｜IDA｜｜R′｜｜PKA)∈Zq*，计算签名为V′=r′P+h′QA。返回签名σ′=(h′,V′)给验证者。下面证明由攻击者伪造的该签名V′可以通过验证等式

因此，签名可以通过验证等式，也就是说攻击者F将签名者A的公钥替换后伪造的签名σ′=(h′,V′)是有效的。即方案不能抵抗公钥替换攻击。

缺陷二：通过对方案的效率分析，可以看出上述方案在签名的验证阶段使用了两次双线性对运算，而双线性对运算的时间复杂度和计算复杂度都比哈希运算和指数运算的要高的多。因此，使用双线性对运算会使方案效率下降。

3 方案改进

针对上述方案中安全性及效率上的缺陷，提出一个可抗公钥替换攻击且效率更高的无证书签名方案。方案包括系统初始化（Setup）、用户个人密钥生成（UserKeyGen）、部分私钥生成（PartKeyGen）、签名密钥生成（SignKey）、签名（Sign）及验证（Verify）这6个算法。方案描述如下。

1）系统初始化：设系统安全参数为1k，KGC选取一个大素数q≤2k，并生成以q为阶的加法循环群G1和乘法循环群G2，选取群G1的一个生成元P∈G1，并随机选取s∈RZ*q作为系统主密钥，计算Ppub=sP作为系统主公钥。作双线性对映射e:G1×G1→G2，选取两个安全哈希函数分别为：H1：{0,1}*×G1→Zq*，H2：{0,1}*×{0,1}*×G1→Zq*。系统公开参数为params={q,e,G1,G2,P,Ppub,H1,H2}，KGC公开params，保密s。

2）用户个人密钥生成：签名者A随机选取xA∈Zq*作为用户个人私钥，计算XA=xAP作为对应的公钥，公开XA，保密xA。

3）部分私钥生成：此算法由KGC 执行，KGC 随机选取yA∈Zq*，计算DA=s+yA+H1(IDA,XA)作为用户的部分私钥，并通过安全信道发送给A。

4）签名密钥生成：签名者A收到DA后，计算SKA=DA+xAH1(IDA,XA)作为签名密钥，对应的签名公钥为PKA=SKAP。

5）签名：设待签名消息为m∈{0,1}*，签名者A随机选取随机数k∈Zq*，计算K=kP，h=H2(m,IDA,K)，V=SKA-1(k+h)，则消息m对应的签名对为σ=(m,K,h,V)。

6）验证：验证者收到消息m的签名对σ=(m,K,h,V)后，对其进行验证，如果等式K=VPKA-hP成立，则说明签名有效，输出1；否则，签名无效，输出0。

4 新方案的安全性分析

4.1 抗类型Ⅰ攻击者的攻击

定理1新方案可以抵抗类型Ⅰ攻击者的公钥替换攻击。

证明因为类型Ⅰ攻击者可以任意替换用户公钥，但是在改进的新方案中，由于在KGC生成的部分私钥中利用哈希运算将用户个人公钥进行绑定，因此攻击者无法替换用户公钥。即新方案可以抵抗类型Ⅰ攻击者的攻击。

4.2 抗类型Ⅱ攻击者的攻击

定理2新方案对于类型Ⅱ攻击者的适应性选择消息和身份攻击，在随机预言机模型下是存在性不可伪造的。

证明设一个类型Ⅱ攻击者AⅡ。如果在多项式有界的时间t内，AⅡ能够以一个不可忽略的概率ε伪造一个有效的签名，只需证明，存在一个概率多项式时间的挑战算法Ω 可以利用AⅡ成功解决DL问题，问题实例为，已知(P,aP)，求解a。在下面的证明中，Ω 模拟密钥生成中心，回答AⅡ的一系列适应性询问，用a模拟签名私钥，设目标用户身份为ID*，对应的待签名消息为m*。AⅡ向Ω 进行如下适应性询问：哈希询问、用户个人密钥询问、部分密钥询问、签名密钥询问、签名询问，而Ω 通过维护一些列表模拟对AⅡ的回答。

H1询问：对应的列表格式为L1(IDj,Xj,h1j)，AⅡ向Ω 进行用户身份为IDi的H1询问。Ω 首先检查列表L1，如果列表中存在(IDi,Xi,h1i)的项，则直接返回h1i给AⅡ；否则，列表中不存在(IDi,Xi,h1i)的项，Ω 随机选取h1i∈RZ*q，返回给AII，并将(IDi,Xi,h1i)添加到列表。H2询问：对应的列表格式为L2(mj,IDj,Kj,h2j)，AⅡ向Ω 进行消息为mi，用户身份为IDi的H2询问。Ω检查列表L2，如果列表中存在(mi,IDi,Ki,h2i)的项，直接返回h2i给AⅡ；否则，Ω 随机选取h2i∈RZ*q，并返回给AⅡ，将(mi,IDi,Ki,h2i)添加到列表。

用户个人密钥询问：每一项列表的格式为Ls(IDj,xj,Xj)，AⅡ向Ω 进行用户身份为IDi的签名密钥询问。Ω 先查询列表Ls，如果列表中已经存在(IDi,xi,Xi)的项，直接返回(xi,Xi)给AⅡ。否则：

1）如果IDi≠ID*，Ω 随机选取xi∈RZ*q，计算Xi=xiP，并将(xi,Xi)返回给AⅡ，同时将(IDi,xi,Xi)添加到列表Ls中。

2）如果IDi=ID*，即AⅡ询问的是目标用户的个人密钥，Ω 拒绝回答，返回(⊥,Xi)给AⅡ，并将(IDi,⊥,Xi)添加到列表Ls中。

部分密钥询问：对应的列表中每项的格式为Lk(IDj,Dj)，AⅡ向Ω 进行用户身份为IDi的部分密钥询问。Ω 检查列表Lk，如果列表中存在(IDi,Di)的项，直接返回Di给AⅡ。否则：

1）如果IDi≠ID*，Ω 首先查询列表L1（假设在此之前已经进行过H1询问，否则可以先进行H1询问），得到h1i，随机选取yi，计算Di=s+yi+h1i，并返回给AⅡ，将(IDi,Di)添加到列表。

2）如果IDi=ID*，Ω 拒绝回答，询问终止。

签名密钥询问：相应的列表格式为Lsk(IDj,SKj,PKj)，AⅡ向Ω 询问身份为IDi的用户的签名密钥。Ω 检查列表，如果列表中存在(IDi,SKi,PKi)的项，直接返回(SKi,PKi)给AⅡ。否则

1）如果IDi≠ID*，Ω 查询列表L1，Ls，Lk分别得到相应的h1i，xi及Di的值（假设在此之前已经进行过H1询问，用户个人密钥询问及部分密钥询问，不然可以先进行询问），直接计算SKi=Di+xih1i，PKi=SKi·P，将(SKi,PKi)返回给AⅡ，并将(IDi,SKi,PKi)添加到列表Lsk中。

2）如果IDi=ID*，Ω 拒绝回答，询问终止。

签名询问：AⅡ向Ω 询问用户身份为IDi，待签名消息为mi的签名询问。如果IDi≠ID*，Ω 查询列表L2和Lsk，得到h2i及SK，并随机选取ki∈RZq*，计算Vi=SKi-1(ki+h2i)，返回给AⅡ；如果IDi=ID*且mi=m*，Ω 查询列表L2，得到h2i的值，随机选取ki∈RZq*，计算Ki=kiP，再计算Vi=(Ki+h2iP)PKA-1，将Vi返回给AⅡ。

攻击与挑战：最后，经过若干轮的询问，AⅡ可以成功伪造出目标用户ID*对于消息m*的签名σ*=(m*,K*,h*,V*) ，根据Forking 引理［10］知，通过对哈希运算进行分叉，AⅡ还可以输出另一个有效签名，下面看算法Ω 利用AⅡ解决困难问题。

由于AⅡ输出的2个伪造签名都是有效的，因此满足验证等式

联立式（2）式（3）得V*PK*-h*P=-，因此

也就是说，挑战者Ω 成功解决了离散对数困难问题，这与困难性假设矛盾。因此，对于类型Ⅱ攻击者，在适应性选择消息和身份攻击下满足存在性不可伪造。

5 效率比较

将改进后的新方案与其他签名方案进行效率比较，其中P表示双线性对运算，H表示哈希运算，E表示指数运算，M表示标量乘运算，结果如表1所示。

表1 各方案效率比较Tab.1 The efficiency comparison of each scheme

由于双线性对运算的时间复杂度和计算复杂度都较高，一次双线性对运算的计算复杂度分别是指数运算和哈希运算的7倍和21倍；时间复杂度是指数运算的10倍［5］。从表1可以看出，本文方案全文没有使用双线性对运算，效率较高。

6 结束语

通过对文献［9］的分析和研究，发现文献［9］中的方案在安全性和效率方面都存在漏洞，因此对其进行改进，并在随机语言机模型下证明了改进方案满足存在不可伪造性。将本文方案与已有无证书签名方案进行效率比较，发现本文方案在效率上具有优势。

[1]SHAMIR A.Identity-Based Cryptosystem and Signature Scheme[C]//Advances in Cryptology-Crypto′84.Berlin: Springer-Verlag,1984:47-53.

[2]AL-RIYAMI S,PATERSON K G.Certificateless Public Key Cryptography[C]//Advances in Cryptology-ASIACRYPT′03.Berlin:Springer-Verlag,2003:452-473.

[3]HUANG X,SUSILO W,MU Y,et al.On the security of a certificateless signature Schemes from Asia Crypt′03[C]//Proceedings of CANS′05.Berlin:Springer-Verlag,2005:13-25.

[4]LIU J K, AU M H, SUSILO W.Self-generated-certificate public key cryptography and certificateless signature/encryption scheme in the standard model [C]// Proc ACM Symposium on Information, Computer and Communications Security.New York:ACM Press,2007:302-311.

[5]樊睿,王彩芬,蓝才会,等.新的无证书代理签名方案[J].计算机应用,2008,28(4):915-917.

[6]李明祥,杜光辉,罗新方.高效的无证书部分盲签名方案[J].计算机工程与设计,2010,31(22):4817-4819.

[7]樊爱宛,杨照峰,谢丽明.强安全无证书签名方案的安全性分析和改进[J].通信学报,2014,35(5):118-123.

[8]樊爱宛,申远,赵伟艇.无证书签名方案的安全性分析与改进[J].计算机应用,2014,34(8):2342-2344,2349.

[9]刘倩,范安东,张丽娜,等.一个高效的无证书签名方案分析与改进[J].河南科技大学学报:自然科学版,2014,35(4):49-53.

[10]POINTCHEVAL D,STERN J.Security Proofs for Signature Schemes[C]//Proceedings of the EUROCRYPT′96.Spain:Saragossa,1996:387-398.

[11]王丽莎,张建中.一种高效安全的无证书数字签名方案[J].计算机工程与应用,2012,48(15):70-73.

[12]张磊,张福泰.一类无证书签名方案的构造方法[J].计算机学报,2009,32(5):940-945.

[13]陈玲玲,亢保元,张磊.一种高效的基于身份的代理盲签名方案[J].华东交通大学学报,2008,25(1):113-116.