给出樊爱宛等无证书签名方案的一个伪造攻击,攻击显示第Ⅰ类强攻击者能成功伪造任意用户对任意消息的有效签名.分析发现原方案不安全的原因在于,签名阶段选取的随机数没有与消息M关联起来,通过将签名阶段选取的随机数与消息M相关的Hash函数值进行绑定的方式给出了改进方案,其中安全性最优的方案在签名阶段只需1个点乘,在验证阶段需要4个点乘,可抵抗第Ⅰ类超级攻击者、第Ⅱ类超级攻击者的攻击;其余方案在签名阶段只需1个点乘,在验证阶段需要3个点乘,可抵抗第Ⅰ类强攻击者、第Ⅱ类超级攻击者的攻击,针对现实世界的攻击者是安全的.改进方案在椭圆曲线离散对数困难性假设下是可证明安全的.
A forgery attack on Fan Aiwan et al's certificateless signature scheme was presented. It is found that the strong type Ⅰ adversary could forge any user's valid signature on any message. The reason of this problem is that the random number selected in the signature generation phase is not associated with the message M. To improve the original scheme's security, the improved schemes in which the random number selected in the signature generation phase is bound to the hash function value of message M was proposed. The scheme proposed can resist both super type Ⅰ and type Ⅱ adversary, and it only needs one scalar multiplication in signature generation phase and four scalar multiplications in signature verification phase; the other schemes proposed can resist strong type Ⅰ and super type Ⅱ adversary and are secure against the attacker in the real world. In addition, they only need one scalar multiplication in signature generation phase, and three scalar multiplications in signature verification phase. The improved schemes are provably secure under the intractability of elliptic curve discrete logarithm problem.
Al-Riyami和Paterson于2003年提出了无证书公钥密码体制[1]，解决了基于身份的密码体制的密钥托管问题. Huang等[2]提出的无证书签名的安全模型定义了普通攻击者、强攻击者、超级攻击者. 对普通攻击者来说，只能得到目标签名者在原始公钥下的消息签名对. 对强攻击者来说，若能在替换用户公钥时，提交替换公钥所对应的秘密值，则能够得到替换公钥下的消息签名对. 对超级攻击者来说，在替换用户公钥时即使不提交替换公钥所对应的秘密值，也能够得到替换公钥下的消息签名对，这表示存在一个实体，能够从攻击者选择的替换公钥里提取出秘密值，并用此秘密值和用户的部分私钥产生签名，但并不确定在现实世界里存在这样的攻击者.
在无证书签名方面，自Al-Riyami和Paterson[3]提出第1个无证书签名方案以来，已有大量的基于双线性对的无证书签名方案被提出. 曹雪菲等[4]对一个高效的无证书签名方案进行了替换公钥攻击，进而提出一个安全的改进方案，在随机预言机模型下给出了安全性证明. 由于双线性对运算比较昂贵，使用双线性对的签名方案普遍存在计算效率不高的问题，因此设计不依赖双线性对的无证书签名方案成为近几年的研究热点. 2012年，Gong等[5]基于椭圆曲线提出一个不使用双线对的无证书签名方案，并声称该方案是可证明安全的，但Yeh等[6]指出其方案不能抵抗第Ⅰ类超级攻击者的攻击，并给出了补救机制. 王圣宝等[7]提出一个新的高效的无证书签名方案，并基于离散对数困难假设证明了方案的安全性. 王亚飞等[8]指出文献[7]的方案是完全不安全的，并基于椭圆曲线数字签名算法和Schnorr提出一个改进方案，其方案在随机预言机模型下是可证明安全的. 樊爱宛等[9]针对文献[8]的签名方案提出一个改进方案，并声称该方案在自适应选择消息攻击下是存在性不可伪造的，其效率较高. 2014年，Kim等[10]基于格困难问题提出一个无证书签名方案，该方案对于恶意但被动的密钥生成中心(KGC，key generation center)是可证明安全的.
笔者对文献[9]的签名方案进行了安全性分析，发现其不能抵抗第Ⅰ类强攻击者的伪造攻击. 为改进其安全性，提出一类可证明安全的无证书签名方案，方案的安全性基于椭圆曲线离散对数困难假设，在文献[2]的安全模型下给出了严谨的安全性证明.
1 数学困难问题及假设椭圆曲线离散对数问题(ECDLP，elliptic curve discrete logarithm problem)： 给定椭圆曲线E(FP)上阶为n的点P及O∈〈P〉,确定整数l∈[0,n-1]，使得O=[l]P成立. 假设C是一多项式时间算法，算法C解决ECDLP的优势定义为 αCECDLP=Pr[C(P,O)=l,l∈Zq*].
椭圆曲线离散对数困难假设：若不存在多项式时间算法C能在多项式时间内以至少ε的优势解决ECDLP，则称ECDLP困难假设成立.
2 对樊爱宛等的方案的安全性分析对文献[9]的方案进行安全性分析，发现文献[9]的方案不能抵抗第Ⅰ类强攻击者T的攻击. 攻击过程如下：
1) 攻击者T通过签名询问得到用户A的一个有效签名对(M,
2) 攻击者T为任意一个消息M′产生伪造的签名：
①计算h′=H2(ID,M′,ZID,RID,K)；
②计算h=H2(ID,M,ZID,RID,K)；
③计算v′=v-hzID+h′zID；
④得到消息M′的一个消息签名对(M′,
3) 接收者B收到(M′,
通过上述步骤攻击者T能够成功伪造任意用户对任意消息的有效签名，文献[9]的方案不能抵抗第Ⅰ类强攻击者的攻击，当然也就不能抵抗第Ⅰ类超级攻击者的攻击.
分析上述攻击能够成功的原因：虽然文献[9]的方案在签名时选取了随机数k，但在签名公式中k并没有与消息M关联起来，从而使攻击者能够利用截获的消息签名对为任意的消息产生伪造的签名.
3 改进的无证书签名方案本节提出一类可证明安全的无证书签名方案.
1) 生成系统参数：输入安全参数k，选择两个大素数p、q，满足q|p-1. 设P为循环群G中一个阶为q的生成元. 选择两个安全的Hash函数：H1:{0,1}*→Zq*，H2：{0,1}*→Zq*. KGC选择系统主密钥s,计算系统公钥PPUB=sP，公开系统参数params={p,q,G,P,PPUB,H1,H2}，秘密保存系统主密钥s.
2) 部分私钥生成：用户向KGC提交用户身份标识I，KGC选取随机数rI∈Zq*，计算RI=rIP，DI=rI+sH1(I,RI)，DI作为用户的部分私钥，RI作为用户的部分公钥，KGC把部分私钥DI、部分公钥RI安全地传送给用户.
用户验证DIP=RI+PPUBH1(I,RI)是否成立，若成立，则判定DI是有效的用户部分私钥；否则，判定DI无效.
3) 生成秘密值：用户随机选择秘密值xI∈Zq*.
4) 生成私钥：生成用户的完整私钥WI=(DI,xI).
5) 生成公钥：计算XI=xIP，用户的公钥PI=(RI,XI). 用户通过可靠方式将其公钥PI公布.
6) 签名：假定A为签名者，签名过程如下.
① A选取随机数z∈Zq*，计算ZA=zP.
② 计算h2=H2 (M,I,ZA,RI,XI).
③ 根据表1的公式计算u，表1共给出9个有效的签名方案，对消息M的签名为σ=(ZA,u).
在签名阶段，对u的计算公式如表1所示共给出9种；在验证阶段，对Z′ A的计算公式对应的也有9种.
7) 验证：假定B为消息的接收者，B收到消息M及M的签名σ以后，计算h1=H1 (I,RI)，h2=H2 (M,I,ZA,RI,XI)，按表1的公式计算Z′ A，验证ZA=Z′ A是否成立. 若成立，则σ为A对消息M的有效签名；否则，此签名无效.
|
表1 签名与验证表 |
改进后的签名方案将签名时选取的随机数z与消息M相关的Hash函数值h2进行了绑定，虽然攻击者能够计算出伪造消息的Hash函数值h2，但因不知道随机数z，攻击者无法利用所截获的消息签名对伪造消息的签名.
第1、2种方案针对第Ⅰ类超级攻击者、第Ⅱ类超级攻击者在适应性选择消息和身份攻击下是存在性不可伪造的. 下面给出第1种签名方案的安全性证明.
定理1 在随机预言模型下,假设在多项式时间内，攻击者AⅠ(设AⅠ为第Ⅰ类超级攻击者)最多能做qc次用户生成询问、qppk次部分私钥询问，若AⅠ能够在多项式时间内以一个不可忽略的概率βAⅠ,supercma,cida成功攻破所提方案，那么存在一个算法C在多项式时间内能够以αCECDLP≥${1 \over {{q_{\rm{C}}}}}\left( {1 - {1 \over {{q_{\rm{C}}}}}} \right)$qppkβAⅠ,supercma,cida的概率解决ECDLP的一个实例.
证明 假定用算法C来解决ECDLP的一个实例(P,aP)，目标是求取a的值. 算法C利用AⅠ(AⅠ为第Ⅰ类超级攻击者)作为子程序来解决这个ECDLP，算法C随机选择J∈[1,qC]作为这次游戏的挑战身份.
算法C运行系统参数生成算法，输出系统参数和系统主密钥. 算法C将系统主密钥保密，将系统参数发送给AⅠ.
AⅠ可以适应性地进行多项式数量级次数的以下询问.
用户生成询问：创建列表Lc，初始化为空，元组的格式为(I,RI,DI,xI,XI). 对用户I进行用户生成询问时，若Lc中存在对应元组(I,RI,DI,xI,XI)，则返回PI给AⅠ，否则按以下步骤生成用户.
1) 若I≠J，随机选择xI∈Zq*，计算XI=xIP，随机选择h1,DI∈Zq*，计算RI=DIP-PPUB h1，在列表Lc中添加元组(I,RI,DI,xI,XI)，并在列表LH1中添加元组(I,RI,h1)，返回PI=(RI,XI)给AⅠ.
2) 若I=J，随机选择xI∈Zq*，计算XI=xI P，令DI=⊥，随机选择h1,rI∈Zq*，计算RI=rIP，在列表Lc中添加元组(I,RI,DI,xI,XI)，并在列表LH1中添加元组(I,RI,h1)，返回PI=(RI,XI)给AⅠ.
H1询问：算法C模拟H1随机预言机，维护列表LH1，列表初始化为空，列表元组的格式为(I,RI,h1). 当算法C收到AⅠ对H1 (I,RI)的询问时，查看列表LH1中是否存在对应项(I,RI,h1). 若存在，返回h1给AⅠ；若不存在，则选取随机数h1∈Zq*，返回h1给AⅠ，并在LH1中添加元组(I,RI,h1).
H2询问：算法C模拟H2随机预言机，创建列表LH2，列表初始化为空，列表元组的格式为(M,I,ZA,RI,XI,h2). 当算法C收到AⅠ对H2 (M,I,ZA,RI,XI)询问时，查看列表LH2中是否存在对应项(M,I,ZA,RI,XI,h2). 若存在，返回h2给AⅠ；若不存在，算法C随机选择h2∈Zq*，返回h2给AⅠ，并在LH2中添加元组(M,I,ZA,RI,XI,h2).
部分私钥询问：算法C收到AⅠ对用户I的部分私钥询问时，若I=J，则算法C终止；否则，查看列表Lc中是否存在对应项(I,RI,DI,xI,XI)，若存在，返回DI给AⅠ，若不存在，则先进行用户生成询问，再返回DI给AⅠ.
公钥替换询问：算法C收到AⅠ对用户I的公钥替换询问(I,X′ I)时，算法C检索Lc找到对应项(I,RI,DI,xI,XI)，将XI替换为X′ I，并设置xI=⊥.
秘密值询问：算法C收到AⅠ对用户I的秘密值询问时，算法C检索Lc找到对应项(I,RI,DI,xI,XI)，若xI=⊥，表明用户I的公钥已被替换，因此算法C无法回答AⅠ的秘密值询问，算法C返回⊥；否则，算法C返回xI.
签名询问：算法C随机选择h2,u∈Zq*，计算ZA=h2-1 (uP-XI-RI-h1PPUB)，返回σ=(ZA,u)给AⅠ，并将(M,I,ZA,RI,XI,h2)添加到列表LH2中.
伪造：最后，AⅠ输出一个有效的消息签名对(I*,M,σ=(ZA,u)),若I*≠J，算法C终止；否则，根据二叉引理[11]，选择不同的Hash函数H1，可以得到另外一个z值相同的消息签名对(I*,M,σ′=(ZA,u′))，则有以下等式成立.
u=xI+rI+sh1+zh2
(1)
u′=xI+rI+sh′ 1+zh2
(2)
由式(1)和式(2)得
u-u′=sh1-sh′ 1
AⅠ不询问I*部分私钥的概率至少${\left( {1 - {1 \over {{q_{\rm{C}}}}}} \right)^{q{\rm{ppk}}}}$. 又AⅠ输出的是I=I*的伪造签名的概率至少为${{1 \over {{q_{\rm{C}}}}}}$，则有
$\alpha _{\rm{C}}^{{\rm{ECDLP}}} \ge {1 \over {{q_{\rm{C}}}}}{\left( {1 - {1 \over {{q_{\rm{C}}}}}} \right)^{q{\rm{ppk}}}}\beta _{{{\rm{A}}_{{\rm{I}},\sup {\rm{er}}}}}^{{\rm{cma}},{\rm{cida}}}$
若βAⅠ,supercma,cida为不可忽略的，又${1 \over {{q_{\rm{C}}}}}{\left( {1 - {1 \over {{q_{\rm{C}}}}}} \right)^{q{\rm{ppk}}}}$为常数，则算法C成功解决ECDLP的概率αCECDLP为不可忽略的.
定理2 在随机预言模型下,假设在多项式时间内，攻击者AⅡ(设AⅡ为第Ⅱ类超级攻击者)最多能做qC次用户生成询问、qs次秘密值询问，若AⅡ能够在多项式时间内以一个不可忽略的概率βAⅡ,supercma,cida成功攻破所提方案，那么存在一个算法C在多项式时间内能够以αCECDLP≥${1 \over {{q_{\rm{C}}}}}{\left( {1 - {1 \over {{q_{\rm{C}}}}}} \right)^{q{\rm{s}}}}$βAⅡ,supercma,cida的概率解决ECDLP的一个实例.
定理2的证明与定理1的证明类似，这里不再赘述.
第3～9种方案针对第Ⅰ类强攻击者、第Ⅱ类超级攻击者在适应性选择消息和身份攻击下是存在性不可伪造的. 以第3种签名方案为例，挑战者与攻击者之间模拟上述游戏，在游戏的最后，AⅠ输出一个有效的消息签名对(I*,M,σ=(ZA,u)). 若I*≠J，算法C终止；否则，根据二叉引理，选择2个不同的Hash函数H2，可以得到另外1个z值相同的消息签名对(I*,M,σ′=(ZA,u′))，从而得到2个z值相同的有效的伪造，则有以下等式成立.
uz=xIh2+DI
(3)
u′ z=xIh′ 2+DI
(4)
由式(3)和式(4)得
u′ (xI h2+DI)=u(xIh′ 2+DI)
通过秘密值询问得到xI，求得DI=${{\left( {u'{h_2} - uh{'_2}} \right){x_{\rm{I}}}} \over {u - u'}}$，则算法C利用AⅠ作为子程序成功地解决了ECDLP的一个实例.
同样地，在游戏的最后，AⅡ输出一个有效的消息签名对(I*,M,σ=(ZA,u)),若I*≠J，算法C终止；否则，根据二叉引理，选择不同的Hash函数H2，可以得到另外1个z值相同的伪造(I*,M,σ′=(ZA,u′))，则有以下等式成立.
uz=xIh2+DI
(5)
u′ z=xIh′ 2+DI
(6)
由式(5)和式(6)得
u′ (xIh2+DI)=u(xIh′ 2+DI)
从上述方案的公钥求取秘密值，相当于求解离散对数难题，而众所周知，离散对数问题是难解的，目前，在现实世界里并不存在拥有第Ⅰ类超级攻击者能力的攻击者，所提的第3～9种签名方案是安全的.
5 效率对比分析把所提的无证书签名方案与已有的具有代表性的无证书签名方案进行比较，如表2所示，用S表示标量乘运算，N表示逆运算.
|
|
表2 所提的签名方案与已有签名方案的比较 |
1)所提出的第1、2种签名方案与文献[8]方案均能够抵抗第Ⅰ类超级攻击者、第Ⅱ类超级攻击者的攻击，文献[9]方案只能抵抗第Ⅰ类普通攻击者、第Ⅱ类超级攻击者的攻击. 所提出的第1种无证书签名方案相比文献[8]方案在签名阶段减少了一个逆运算，所提出的第2种无证书签名方案相比文献[8]方案在验证阶段减少了一个逆运算.
2)所提出的第3～9种无证书签名方案能够抵抗第Ⅰ类强攻击者、第Ⅱ类超级攻击者的攻击，在签名阶段只需要1个点乘，在验证阶段只需要3个点乘，针对现实世界的攻击者是安全的，而文献[9]方案针对现实世界的攻击者是不安全的.
6 结束语对文献[9]的无证书签名方案进行了安全性分析，指出其方案不能抵抗第Ⅰ类强攻击者的伪造攻击，对于现实世界的攻击者是不安全的. 为此，提出了改进方案，改进方案克服了原方案的安全缺陷，具有更高的安全性.
| [1] | Al-Riyami S S, Paterson K G. Certificateless public key cryptography[C]//Laih C S. Proc. of the ASIACRYPT 2003. LNCS 2894, Berlin:Springer-Verlag, 2003:452-473.[引用本文:1] |
| [2] | Huang Xinyi, Mu Yi, Susilo W, et al. Certificateless signature revisited[C]//Pieprzyk J, Ghodosi H, Dawson E. Proc. of the ACISP 2007. LNCS 4586, Heidelberg:Springer-Verlag, 2007:308-322.[引用本文:2] |
| [3] | Al-Riyami S S, Paterson K G. Certificateless public key cryptography[C]//Proc of Asiacrypt 2003. Berlin:Springer-Verlag, 2003:452-473.[引用本文:1] |
| [4] | 曹雪菲, Kenneth G Paterson, 寇卫东. 对一类无证书签名方案的攻击与改进[J]. 北京邮电大学学报, 2008, 31(2):64-67. Cao Xuefei, Kenneth G Paterson, Kou Weidong. An attack on a certificateless signature scheme and its improvement[J]. Journal of Beijing University of Posts and Telecommunications, 2008, 31(2):64-67.[引用本文:1] |
| [5] | Gong Peng, Li Ping. Further improvement of a certificateless signature scheme without pairing[J]. International Journal of Communication Systems, 2012, 27(10):2083-2091.[引用本文:1] |
| [6] | Yeh K H, Tsai K Y, Kuo R Z, et al. Robust certificateless signature scheme without bilinear pairings[C]//IT Convergence and Security (ICITCS), 2013 International Conference on.[s.l.]:IEEE, 2013:1-4.[引用本文:1] |
| [7] | 王圣宝, 刘文浩, 谢琪. 无双线性配对的无证书签名方案[J]. 通信学报, 2012, 33(4):93-98. Wang Shengbao, Liu Wenhao, Xie Qi. Certificateless signature scheme without bilinear pairings[J]. Journal on Communications, 2012, 33(4):93-98.[引用本文:2] |
| [8] | 王亚飞, 张睿哲. 强安全无对的无证书签名方案[J]. 通信学报, 2013, 34(2):94-100. Wang Yafei, Zhang Ruizhe. Strongly secure certificateless signature scheme without pairings[J]. Journal on Communications, 2013, 34(2):94-100.[引用本文:5] |
| [9] | 樊爱宛, 杨照峰, 谢丽明. 强安全无证书签名方案的安全性分析与改进[J]. 通信学报, 2014, 33(1):18-21. Fan Aiwan, Yang Zhaofeng, Xie Liming. Security analysis and improvement of strongly secure certificateless signature scheme[J]. Journal on Communications, 2014, 33(1):18-21.[引用本文:7] |
| [10] | Kim K S, Jeong I R. A new certificateless signature scheme under enhanced security models[J]. Security and Communication Networks, 2014, 8(5):801-410.[引用本文:1] |
| [11] | Pointcheval D, Stern J. Security proofs for signature schemes[J]. Lecture Notes in Computer Science, 1996, 1070:387-398.[引用本文:1] |