基于证书的密码体制作为一种新型公钥密码体制，结合了公钥基础设施和基于身份密码体制的优点，克服了其存在问题，从提出开始，就引起了广泛的关注，一系列利用双线性对的基于证书签名方案被相继提出.然而，运行一次双线性对运算所耗费的时间约为椭圆曲线上点乘运算的20倍，是目前较为复杂的密码操作.因此，为了提高效率，无对的基于证书签名对诸如无线传感器网络等能量受限的系统来讲就更具吸引力. 2008年，Liu等^[1]首次提出了一个无对的基于证书签名方案，但是Liu等在其方案中附加一个关于私钥的知识证明来防止替换公钥攻击，导致方案的效率降低.随后，在2009年，Zhang^[2]指出Liu等提出的方案不能抵抗Ⅰ型敌手A_Ⅰ和Ⅱ型敌手A_Ⅱ的攻击，并对其进行了改进，然而改进的方案仍然使用了对运算.同年，Yang等^[3]也提出了无对的基于证书签名方案，而Li等^[4]于2013年也指出Yang等的方案无法抵抗A_Ⅱ的攻击，并给出改进的方案.

杨波等^[5]于2012年利用离散对数问题(DLP, discrete logarithm problem)的困难性提出的基于证书签名方案具有很好的特性，比如方案没有使用映射到点特殊的Hash函数，其签名阶段只需要有限域上的2个加法和2个乘法运算，验证阶段也不需要复杂的双线性对运算，计算效率较高.杨波等^[5]声称所提方案在最强的敌手模型中是安全的，可以抵抗超级A_Ⅰ和超级A_Ⅱ的伪造攻击.然而，当A_Ⅰ替换用户的公钥后，必须向挑战者C提供被替换公钥所对应的秘密值才能获得可通过验证的消息签名对，否则无法证明C模拟的签名和真实签名不可区分，敌手可以不接受C返回的签名而导致模拟过程失败.另外，该签名方案实际上仍然无法抵抗A_Ⅱ的攻击.具体来讲，一个超级敌手A_Ⅱ是一个恶意但被动的认证中心(CA, certificate authority)，该CA在系统初始化阶段就有预谋地针对预选用户设置含有陷门信息的系统参数，这种特殊的系统参数与正常系统参数是不可区分的，因此，相对于其他敌手，CA就拥有更大的优势来计算用户的私钥，进而伪造用户对任意消息的签名.然而，经分析发现，杨波等^[5]的方案甚至不能抵抗一个普通敌手A_Ⅱ的攻击，一个诚实但好奇的CA在得不到任何用户秘密值的情况下，仅通过选取随机参数以及多项式时间内的计算，便能以显著的概率成功伪造任意用户对任意消息的有效签名.笔者讨论了出现这种伪造攻击的原因，并针对原方案的缺陷进行了必要的改进，分析结果表明，改进后的方案在保留原方案计算效率高等优点的同时，有效克服了原方案的安全隐患.

限于篇幅，杨波等^[5]提出的方案不再赘述，下面给出一个诚实但好奇的CA对签名的伪造攻击过程，可证明该方案是不安全的.

1) CA随机选取u^*∈Z_q^*，计算U^*=g^u*(mod p)，h₂^*=H₂(ID‖U^*‖PK_ID‖M), h ₃^*=H₃(ID‖U^*‖PK_ID‖M).

2) CA计算R^*=Y_ID^(-h*3/h₂*)，h₁^*=H₁(R^*‖Y_ID‖ID)，v^*=u^*+xh₁^*h₂^*，最后输出消息M的伪造签名σ^*=(U^*, v^*, R^*).

下面证明伪造签名σ^*=(U^*, v^*, R^*)是有效的.因为

即g^v*=U^*(R^*X^h₁*)^h₂*Y_ID^h₃*成立，这说明σ^*=(U^*, v^*, R^*)是用户ID在公钥Y_ID下对消息M的有效签名，因此，杨波等^[5]的方案无法抵抗普通的Ⅱ型敌手A_Ⅱ的伪造攻击.

对原方案而言，在v=u+z_IDh₂+y_IDh₃中使用2个不同的Hash函数H₂和H₃是必要的.即使2个Hash函数的输入相同，但两者的输出是不同的，而且输出结果具有一定的随机性.若使用相同的Hash函数H，CA只需要计算U^*=g^u*U，h^*=H(ID‖U^*‖PK_ID‖M)，然后计算v^*=u^*+z_ID(h^*－h)+v，就能将σ^*=(U^*, v^*, R)作为伪造的签名输出.很容易验证σ^*也是用户ID在公钥Y_ID下对消息M的有效签名.必须注意到，原方案在证书生成阶段计算的R=g^r(mod p)并没有作为签名阶段的Hash函数H₂和H₃的输入，这是敌手能计算h₂^*、h₃^*和R^*= Y_ID^{(-h₃*/h₂*)}进而伪造签名成功的原因，因此可以将R值绑定到H₂和H₃中来避免这种攻击.

通过在签名阶段将杨波等^[5]的方案在证书生成阶段计算的承诺值R增加为Hash函数的输入之一，提出了一个改进方案，改进方案的系统初始化及密钥生成算法与原方案相同，下面只给出其签名及验证算法.

1) Sign：用户ID随机选取u∈Z_q^*，计算U=g^u(mod p)，h₂=H₂(ID‖Y_ID‖U‖R‖M)，h₃= H₃(ID‖Y_ID‖U‖R‖M)，然后计算v=z_ID+(y_IDh₂+u)h₃，最后将σ=(U, v, R)作为消息M的签名输出.

2) Verify：给定消息签名对(M, σ)、签名者ID的公钥Y_ID，用户计算V=g^v(mod p)，h₁=H₁(R‖Y_ID‖ID)，h₂=H₂(ID‖Y_ID‖U‖R‖M)，h₃=H₃(ID‖Y_ID‖U‖R‖M)，最后验证V=RX^h₁(UY_ID^h₂)^h₃是否成立.

由改进方案可以看出，若CA计算U^*=g^u*后将无法再计算h₂^*和h₃^*，因为此时R^*尚未计算，CA也无法先计算R^*=Y_ID^{(-h₃*/h₂*)}，因为h₂^*和h₃^*的值与R^*绑定，因此改进方案克服了对原方案的攻击.

将目前已提出的无对的基于证书签名与改进方案进行比较，如表 1所示.其中，|g|表示Z_p中元素的长度，|q|表示Z_q中元素的长度，M和E分别表示Z_p的乘法和指数操作.

表 1

表 1

表 1 方案比较分析

表 1 方案比较分析

由表 1分析发现，改进方案无须花费额外的计算代价，保留了原方案计算复杂度低的优点，在签名长度和计算效率上是高效的基于证书签名方案.

参考文献[4]中的证明技巧，下面分别给出改进方案对敌手A_Ⅰ和A_Ⅱ的不可伪造证明.

定理1  若存在一个Ⅰ型敌手A_Ⅰ在T时间内，最多执行q_Hi(i=1, 2, 3) 次Hash询问、q_cu次CreateUser询问、q_usk次Corruption询问、q_rpk次ReplacePublicKey询问、q_cert次CertGen询问和q_sign次Sign询问后，能以Succ_CBS^EF(A_Ⅰ)的概率攻破所提基于证书签名方案，那么存在另外一个适应性选择消息和身份攻击的算法C，能利用A_Ⅰ在期望时间T′≤(q_cu+2q_cert+4q_sign)t_ex+2T内具优势Adv_CBS^EF(A_Ⅰ)≥(1－1/q_H1)^{q_cert+q_sign}Succ_CBS^EF(A_Ⅰ)/q_H1来解决DLP的一个实例，其中t_ex为Z_p上的一次指数运算耗时.

证明  假设C收到了DLP的一个随机实例(g, g^μ)，其目标是输出μ∈Z_q^*.为了利用A_Ⅰ解决DLP，C需要模拟一个挑战者并回答A_Ⅰ的所有询问. C首先置系统公钥为X=g^μ并将系统参数params={p, q, g, X, H₁, H₂, H₃}发送给A_Ⅰ.其次，C随机选取ID_k满足(1≤k≤q_H1)作为游戏的挑战身份，其中q_H1为可询问H₁的最大次数.不失一般性，C需要维护5个初始为空的列表L_cu、L_Hi(i=1, 2, 3) 和L_cert.L_cu用来维护CreateUser、ReplacePublicKey和Corruption询问的记录，L_Hi(i=1, 2, 3) 用来维护Hash询问的记录, L_cert用来维护CertGen询问的记录.下面是C仿真挑战者与A_Ⅰ的交互.

1) CreateUser询问：当A_Ⅰ向C发布对ID_i的公钥询问时，C查看L_cu列表，若存在{ID_i, y_IDi, Y_IDi}，C返回Y_IDi给A_Ⅰ；否则，C随机选取y_IDi∈Z_q^*，计算Y_IDi=g^y_IDi并将Y_IDi返回给A_Ⅰ.最后将{ID_i, y_IDi, Y_IDi}添加到L_cu列表.

2) Hash询问：当A_Ⅰ向C进行H_i(i=1, 2, 3) 询问时，C分别随机选取α_i、β_i、λ_i∈Z_q^*为对应的H_i(i= 1, 2, 3) 值返回给A_Ⅰ，并将对应值分别加入到L_H1{R_i, Y_IDi, ID_i, α_i}、L_H2{ID_i, Y_IDi, U_i, R_i, M_i, β_i}和L_H3{ID_i, Y_IDi, U_i, R_i, M_i, λ_i}列表.

3) ReplacePublicKey询问：当A_Ⅰ向C发布对{ID_i, Y′_IDi}的询问时，C检查L_cu列表并将{ID_i, y_IDi, Y_IDi}改为{ID_i, ⊥, Y′_IDi}.

4) CertGen询问：当A_Ⅰ向C发布对{ID_i, z_IDi, R_i}的询问时，C响应如下.

① 若i≠k，C随机选取z_IDi、α_i∈Z_q^*并计算R_i=g^z_IDiX^－α_i，然后检查L_H1列表是否已存在{R_i, Y_IDi, ID_i}，若存在则需要重新选取z_IDi和α_i以防止碰撞. C将{R_i, Y_IDi, ID_i, α_i}和{ID_i, z_IDi, R_i, Y_IDi}分别添加到L_H1和L_cert列表，最后返回{z_IDi, R_i}给A_Ⅰ.

② 若i=k，C终止.

5) Corruption询问：当A_Ⅰ向C发布对ID_i的秘密值询问时，C查看L_cu列表，若存在{ID_i, y_IDi, Y_IDi}，C返回y_IDi给A_Ⅰ；否则，C随机选取y_IDi∈Z_q^*，计算Y_IDi=g^y_IDi并将y_IDi返回给A_Ⅰ.最后将{ID_i, y_IDi, Y_IDi}添加到L_cu列表.

6) Sign询问：当A_Ⅰ向C发布对{ID_i, M_i}的签名询问时，C响应如下.

① 若i≠k且L_cu列表中存在{ID_i, y_IDi, Y_IDi}满足y_IDi≠⊥，即公钥未被替换，则C首先查找L_cert列表中是否存在{ID_i, z_IDi, R_i, Y_IDi}，若不存在则自己对{ID_i, Y_IDi}分别进行CertGen和Corruption询问来产生{z_IDi, y_IDi}，然后直接使用签名算法对消息M进行签名并将结果返回给A_Ⅰ.

② 若i=k，或者i≠k且ID_i对应的公钥Y_IDi被替换过，则A_Ⅰ必须向C提供被替换公钥所对应的秘密值. C首先随机选取v_i、α_i、β_i、λ_i∈Z_q^*，计算U_i= (g^v_iY_IDi^-β_iλ_i)^λ_i-1和R_i=X^－α_i，然后置H₁(R_i‖Y_IDi‖ID_i)=α_i，H₂(ID_i‖Y_IDi‖U_i‖R_i‖M_i)=β_i，H₃(ID_i‖Y_IDi‖U_i‖R_i‖M_i)=λ_i.若H_i(i=1, 2, 3) 列表中已存在对应项，则需要重新选择α_i、β_i、λ_i以防止出现碰撞；否则，C将{R_i, Y_IDi, ID_i, α_i}、{ID_i, Y_IDi, U_i, R_i, M_i, β_i}和{ID_i, Y_IDi, U_i, R_i, M_i, λ_i}添加到L_Hi(i=1, 2, 3) 并将(U_i, v_i, R_i)返回给A_Ⅰ.

假设C在模拟过程中不失败，A_Ⅰ将至少以Succ_CBS^EF(A_Ⅰ)的概率输出目标用户{ID^*, Y_ID^*}对消息M^*的有效伪造签名σ^*=(U^*, v^*, R^*)，满足

(1)

若ID^*≠ID_k，C将终止；否则，根据分叉引理，C通过输入{R, Y_ID, ID}来重放A_Ⅰ对H₁的询问得到{R, Y_ID, ID, α′}并将其添加到L_H1列表.最后，C可在期望时间t=120 686q_H1T/Succ_CBS^EF(A_Ⅰ)输出一个新的有效签名σ′=(U^*, v′, R^*)，满足

(2)

这里需要注意的是，H₂和H₃的输出值h₂^*和h₃^*在C重放A_Ⅰ对H₁的询问前后保持不变.根据式(1) 和式(2)，C最终输出μ=(v^*－v′)/(h₁^*－h′₁)作为DLP一个实例的解.若以下条件同时成立，C具优势Adv_CBS^EF(A_Ⅰ)来求解DLP.

E₁：C在整个模拟过程中不失败.

E₂：A_Ⅰ成功输出伪造签名σ^*=(U^*, v^*, R^*).

E₃：若E₂发生，在(ID^*, σ^*)中有ID^*=ID_k.

从上述仿真过程易知，C的成功概率Adv_CBS^EF(A_Ⅰ)=Pr[E₁∧E₂∧E₃].若A_Ⅰ查询用户ID^*的证书，由于C不知道μ值，因此C不发生终止的概率Pr[E₁]≥(1－1/q_H1)^{q_cert+q_sign}；C在A_Ⅰ输出一个有效的伪造签名而没有终止的概率Pr[E₂|E₁]=Succ_CBS^EF(A_Ⅰ)；若A_Ⅰ不选择ID^*作为伪造阶段的签名者，那么C也无法解决DLP，此事件不发生的概率Pr[E₃|E₁∧E₂]≥1/q_h1.下面计算Adv_CBS^EF(A_Ⅰ)的下限.

C的运行时间等于它模拟安全性证明的时间与2倍的A_Ⅰ的运行时间之和.在CreateUser、CertGen和Sign询问阶段，分别需要进行q_cu、2q_cert和4q_sign次Z_p上的指数运算，因此C的整个运行时间为T′≤(q_cu+2q_cert+4q_sign)t_ex+2T，证毕.

定理2  若存在一个Ⅱ型敌手A_Ⅱ在T时间内，最多执行q_Hi(i=1, 2, 3) 次Hash询问、q_cu次CreateUser询问、q_usk次Corruption询问、q_rpk次ReplacePublicKey询问和q_sign次Sign询问后，能以Succ_CBS^EF(A_Ⅱ)的概率攻破所提基于证书签名方案，那么存在另外一个适应性选择消息和身份攻击的算法C，能利用A_Ⅱ在期望时间T′≤(q_cu+q_usk+4q_sign)t_ex+2T内具优势Adv_CBS^EF(A_Ⅱ)≥(1－1/q_H1)^{q_usk+q_rpk+q_sign}Succ_CBS^EF(A_Ⅱ)/q_H1来解决DLP的一个实例.

证明  与定理1证明过程类似，C首先随机选取x∈Z_q^*，然后置系统公钥为X=g^x并将系统参数params={p, q, g, X, H₁, H₂, H₃}和x一起发送给A_Ⅱ.下面是C仿真挑战者与A_Ⅱ的交互.

1) CreateUser询问：当A_Ⅱ向C发布对ID_i的公钥询问时，C查看L_cu列表，若有{ID_i, y_IDi, Y_IDi}，C返回Y_IDi给A_Ⅱ.否则，若i≠k，C随机选取Y_IDi∈Z_q^*，计算Y_IDi=g^Y_IDi并将Y_IDi返回给A_Ⅱ，同时将{ID_i, y_IDi, Y_IDi}添加到L_cu列表；若i=k，C直接置Y_IDi=g^μ并将Y_IDi返回给A_Ⅱ，同时将{ID_i, ⊥, Y_IDi}添加到L_cu列表.

2) Hash询问：与定理1中的Hash询问回答类似.

3) Corruption询问：当A_Ⅱ向C询问ID_i的秘密值时，若i≠k，同定理1；若i=k，C终止.

4) ReplacePublicKey询问：当A_Ⅱ向C发布对{ID_i, Y′_IDi}的询问时，若i=k，C终止；否则，C检查L_cu列表并将{ID_i, y_IDi, Y_IDi}改为{ID_i, ⊥, Y′_IDi}.

5) Sign询问：与定理1中的签名询问回答类似.

如果C在证明过程中不退出，A_Ⅱ将至少以Succ_CBS^EF(A_Ⅱ)的概率输出{ID^*, Y_ID^*}对消息M^*的有效伪造签名σ^*=(U^*, v^*, R^*)，满足

(3)

若ID^*≠ID_k，C将终止；否则，C通过输入{ID, Y_ID, U, R, M}来重放A_Ⅱ对H₂的询问得到{ID, Y_ID, U, R, M, β′}并将其添加到L_H2列表.最后，C可在期望时间t=120 686q_H2T/Succ_CBS^EF(A_Ⅱ)输出一个新的有效签名σ′=(U^*, v′, R^*)，满足

(4)

这里需要注意的是，H₁和H₃的输出值h₁^*和h₃^*在C重放A_Ⅱ对H₂的询问前后保持不变.根据式(3) 和式(4)，C最终输出μ=(v^*－v′)/(h₂^*－h′₂)h₃^*作为DLP一个实例的解.同理，C的成功概率为

C的运行时间等于它模拟安全性证明的时间与2倍的A_Ⅱ的运行时间之和.在CreateUser、Corruption和Sign询问阶段，分别需要进行q_cu、q_usk和4q_sign次Z_p上的指数运算，因此C的整个运行时间为T′≤(q_cu+q_usk+4q_sign)t_ex+2T，证毕.

首先指出了杨波等^[5]所提的基于证书签名方案的安全缺陷，然后给出了一个改进方案，最后证明了改进方案的不可伪造性可归约到求解DLP.效率分析结果表明，改进方案是目前效率最高的基于证书签名方案之一，尤其适合计算能力及带宽受限的环境.如何构造在更强的敌手模型下的基于证书签名方案是一个公开问题，是下一步要努力的方向.