无证书签名方案的分析与改进

赵 洪，喻书涵，韩妍妍，2，李兆斌

（1.北京电子科技学院 电子与通信工程系，北京 100070；2.北京电子科技学院 网络空间安全系，北京 100070）

0 引言

无证书公钥密码体制由Al-Riyami 等［1］在2003 年提出。无证书密码体制中用户的私钥由密钥生成中心（Key Generation Center，KGC）生成的用户部分私钥和用户选择的秘密值构成；用户的公钥由KGC 生成的公钥和秘密值对应的公钥组成。该密码体制无需数字证书，解决了证书管理问题；此外，KGC 只拥有用户部分私钥，能够解决密钥托管问题。

第一个无证书签名方案由Al-Riyami 等［1］提出，此后大量无证书签名方案相继提出。2004 年，Yum 等［2］提出了无证书签名的通用构造；2005 年，Huang 等［3］指出文献［1］方案无法抵抗公钥替换攻击，并给出了改进方案；随后，2006 年Yap等［4］提出一个新的无证书签名方案，但该方案仍无法抵抗敌手的公钥替换攻击。第一个标准模型下的无证书签名方案由Liu 等［5］在2007 年提出，但是无法抵抗恶意KGC 攻击。2012 年，王圣宝等［6］提出一个基于椭圆曲线离散对数问题的无双线性对的方案，该方案在随机预言机模型下可证明是安全的；然而王亚飞等［7］指出文献［6］中方案在第Ⅰ类敌手的公钥替换攻击下是完全不安全的，并且基于椭圆曲线的数字签名算法提出了一个改进方案并证明了该方案的安全性。2014 年，樊爱宛等［8］通过对传统无证书算法顺序的变换对文献［7］中方案进行了改进，并声称该方案高效、可抵抗自适应密文攻击；然而在2016 年，汤永利等［9］针对文献［8］方案进行分析，认为该方案不能抵抗第Ⅰ类强敌手的攻击，并且基于椭圆曲线离散对数改进方案，提出9 个可证明安全的无证书签名方案。2020 年，王菁等［10］指出文献［9］的9 个无证书签名方案中，第1、2、5、8、9 这5 个无证书签名方案无法抵抗第Ⅰ类敌手的替换公钥攻击；然而文献［10］中并未分析文献［9］中其余可抵抗第Ⅰ类敌手攻击的方案是否能够抵抗第Ⅱ类敌手的攻击，并且未对文献［9］中无法抵抗第Ⅰ类敌手攻击的方案进行改进；同样，胡冰洁等［11］只对文献［9］中方案1进行了第Ⅰ类敌手的分析，并没有分析其余方案的安全性。张振超等［12］通过对现有文献［13-18］列举的攻击过程的分析，总结了敌手伪造无证书签名的本质原因是签名方案中公钥具有线性关系，并总结出线性化分析方法。本文使用线性化方程分析的方法，以证明汤永利等［9］提出的9 个无证书签名方案都不具有安全性，并且提出改进方案，该方案在随机预言机模型下是可证明安全的；通过对敌手攻击方式的分析，提出了一类无证书签名验证方案的安全公钥构造格式。

1 预备知识

1.1 困难问题与安全假设

设q是一个大素数，在有限域Fq上定义一个椭圆曲线E/Fq，在该椭圆曲线上的所有点构成一个加法群G，G中有生成元P，P的阶数为q。

定义1椭圆曲线离散对数问题（Elliptic Curve Discrete Logarithm Problem，ECDLP）。对于一个给定的椭圆曲线群G，P、Q是G上两点，α∈，使Q=αP，已知P、G，求α。

ECDLP 假设：对于任何概率多项式时间算法A，都只能以可忽略的优势解决ECDLP。

1.2 无证书签名方案定义回顾

根据文献［1］定义，无证书签名方案包括三个合法参与者：密钥生成中心KGC、签名者和验证者，和以下7 种多项式时间的算法。

建立系统算法（Setup）：KGC 输入安全参数，生成公开的系统参数params和主密钥s，并秘密保存主密钥s。

部分私钥生成算法（Extract-Partial-Private-Key）：由KGC完成该算法，KGC 输入系统参数params、主密钥s和用户身份标识ID，输出值dID作为用户部分私钥。

用户秘密值生成算法（Set-Secret-Value）：由用户完成该算法，用户输入系统参数params和个人身份标识ID，输出值xID作为用户秘密值。

完整私钥生成算法（Set-Private-Key）：由用户完成该算法，用户输入系统参数params、用户标识ID、秘密值xID和部分私钥dID，输出值sID作为用户完整私钥。

公钥生成算法（Set-Public-Key）：由用户完成该算法，用户输入系统参数params、用户标识ID和秘密值xID，输出值PID作为用户公钥。

签名算法（Sign）：签名者IDA输入消息M、系统参数params、签名者标识ID和私钥sID，输出值σ作为对消息M的签名。

验证算法（Verify）：验证者IDB输入系统参数params、签名者标识ID、签名者公钥PID以及对消息M的签名σ，若签名验证通过，则输出true；若验证不通过，则输出false。

1.3 无书签名的安全模型

根据文献［19-21］的定义，无证书签名的安全模型将敌手按能力划分为两类：第Ⅰ类敌手和第Ⅱ类敌手。其中：第Ⅰ类敌手没有KGC 主密钥，但可以发动替换用户公钥攻击；第Ⅱ类敌手不能替换用户公钥，但是拥有KGC 主密钥。

文献［20］中详细定义了敌手与挑战者之间的游戏过程。

2 汤永利方案的安全性分析

2.1 汤永利方案回顾

汤永利通过对文献［8］中方案的分析，在2016 年给出了具体的攻击方案证明文献［8］中的方案不能抵抗第Ⅰ类强敌手的攻击，并且提出了基于ECDLP 假设的改进方案，具体如下。

1）建立系统算法（Setup）：

①KGC 输入安全参数k，选择大素数q，P为椭圆曲线加法群G中一个q阶生成元。

②KGC 任意选择主密钥s∈，生成KGC 公钥Ppub=sP。

④KGC 公开系统参数params={p，q，G，P，Ppub，H1，H2}，并保存主密钥s。

2）部分私钥生成算法（Extract-Partial-Private-Key）：

①KGC 接收到用户提交的身份标识IDA后，选择随机数rA∈，计算RA=rAP。

②计算dA=rA+sH1(IDA，RA)。

③dA作为用户的部分私钥，RA作为用户的部分公钥，KGC 将(RA，dA)以安全的方式返回给用户。

④用户验证dAP=RA+PpubH1(IDA，RA)等式是否成立，成立则接受，否则拒绝。

3）用户秘密值生成算法（Set-Secret-Value）：

用户随机选择秘密值xA，其中xA∈。

4）完整私钥生成算法（Set-Private-Key）：

生成sA=(dA，xA)作为用户的完整私钥。

5）公钥生成算法（Set-Public-Key）：

①通过用户秘密值xA计算XA=xAP。

②设置PA=(RA，XA)作为用户的完整公钥。

6）签名算法（Sign）：签名者为用户A，要签名的文件为M，验证者为用户B，该算法如下。

①用户A 随机选取t∈，计算T=tP。

②计算哈希值：h2=H2(M，IDA，RA，XA，T)

③根据表1 中列出的9 个无证书签名方案计算部分签名u，用户A 对消息M完成签名σ=(u，T)，发送(IDA，σ，M，PA)给用户B。

7）验证算法（Verify）：用户B 为签名验证者，算法如下。

①B 接收到(IDA，σ，M，PA)之后，计算h1=H1(IDA，RA)，h2=H2(M，IDA，RA，XA，T)。

②B 按照表1 与签名方案计算u对应的公式T′，验证T′=T是否成立，若成立则σ为用户A 对消息M的签名，返回true；否则此签名无效，返回false。

表1 签名验证方案Tab.1 Signature and verification schemes

2.2 线性化方程分析回顾

在文献［12］中，给出线性化方程的定义：假设用户产生的部分公钥为P1，P2，…，Pn，KGC 产生的公钥为Q1，Q2，…，Qn，有若干抗碰撞的哈希函数h1，h2，…，h2n，当验证等式中出现式（1）的等式时称为公钥具有线性关系。

3 针对汤永利方案的攻击

3.1 第Ⅰ类敌手针对汤永利签名方案的攻击回顾

根据文献［11］对汤永利方案1 进行的公钥替换攻击，第Ⅰ类敌手可以通过控制用户公钥XA消除KGC 公钥Ppub，同时不需要提交更改的用户秘密值xA即可完成伪造签名；在第2、5、8、9 这4 个无证书签名方案中，同样存在等式XA+RA+h1Ppub=0 可以被第Ⅰ类敌手通过相同的方法攻破，因此汤永利等［9］提出的9 个无证书签名方案中，第1、2、5、8、9 这5个无证书签名方案无法抵抗第Ⅰ类敌手攻击。

3.2 第Ⅱ类敌手对汤永利方案3的攻击

文献［10-11］仅仅对汤永利方案进行了第Ⅰ类敌手安全性分析，指出文献［9］中提出的第1、2、5、8、9 这5 个无证书签名方案是不安全的；本文通过线性化方程的方法，对9 个方案进行分析，可以对包括文献［9］中的第3、4、6、7 这4 个第Ⅰ类敌手攻击安全的无证书签名方案在内的所有9 个方案进行第Ⅱ类敌手攻击。

第Ⅱ类敌手拥有KGC 的主密钥s，但是不能替换用户公钥，因此第Ⅱ类敌手通过消除用户秘密值xA作用的方式伪造签名，在文献［9］的无证书签名方案3 中，验证算法中存在形如式（1）的等式h2XA+RA+h1Ppub=0，第Ⅱ类敌手可以使用线性化分析的方法，通过自己控制的KGC 公钥Ppub消除RA和XA，完成对签名的伪造，详细过程如下所述。

1）伪造攻击：第Ⅱ类敌手执行以下操作。

①随机选取一个t′∈，计算T′=t′P。

②选择一条新的消息M′≠M，计算：

结论1 汤永利等［9］的无证书签名方案3 无法抵抗第Ⅱ类敌手进行的恶意KGC 攻击，敌手可以伪造用户对消息的签名，因此该方案是不安全的。

3.3 针对其他签名方案的攻击

通过对签名方案中验证等式的分析发现，在第1、2、5、8、9 这 5 个无证书签名方案中存在等式XA+RA+h1Ppub=0；方案4 中存在等式XA+h2RA+h1h2Ppub=0；方案6 中存在等式h2XA+RA+h1Ppub=0；方案7 中存在等式XA+h2RA+h1h2Ppub=0，因此与攻击方案3 的方法相同，第Ⅱ类敌手可以通过自己控制的KGC 公钥Ppub发起恶意的KGC 攻击，消除RA和XA，完成对签名的伪造。

结论2 汤永利等［9］中的所有无证书签名方案都无法抵抗第Ⅱ类敌手发起的恶意KGC 攻击，该文献中所有方案面对于第Ⅱ类敌手攻击都不安全。

4 改进的无证书签名方案

本章将对文献［9］方案的不安全原因进行分析并改进，改进的方案对第Ⅰ类敌手和第Ⅱ类敌手是安全的，并且给出了安全性证明。

4.1 汤永利等方案不安全原因分析

对于第Ⅰ类敌手，为了成功伪造签名，在无法计算出KGC 主密钥的情况下需要避开KGC 主密钥s。文献［9］方案中存在用户公钥和KGC 公钥的线性关系，敌手可以通过线性的关系控制用户公钥消去KGC 公钥，这样在伪造的过程中可以不使用KGC 的主密钥进行签名，而只使用用户私钥，消去了KGC 作为第三方的参与，变成了敌手与验证者一对一的信息传递，只要是敌手选取的私钥生成的签名就一定可以通过敌手的公钥对签名验证。

对于第Ⅱ类敌手，为了成功伪造签名，在无法计算出用户秘密值的情况下只能以避开用户秘密值的方法伪造签名。由于敌手掌握了KGC 的主密钥，可以发动恶意KGC 攻击，因此敌手可以在生成系统参数算法（Setup）中适应性地设置陷门信息，即在设置KGC 公钥时通过巧妙的设计使包含用户秘密值的公钥在计算中被KGC 公钥消除。通过这种方法，在验证签名的过程中无需验证用户公钥和私钥之间的关系，用户的秘密值就失去了作用，敌手达到了避开用户秘密值的目的。在文献［9］中，KGC 公钥与用户公钥存在着线性的关系，敌手可以轻易通过KGC 公钥和用户公钥间的线性关系，控制KGC 公钥消去用户公钥，完成签名伪造。

本文基于方案3 进行改进，通过破坏KGC 公钥和用户公钥之间的线性关系解决文献［9］中存在的问题，并且提出了一种安全的公钥构造格式，这类构造格式不具有线性性质，因此无法通过线性化分析方法伪造，证明了改进的方案在随机预言机模型下是安全的。

4.2 改进的无证书签名方案

1）建立系统算法（Setup）：

①KGC 输入安全参数k，选择素数q，P为椭圆曲线加法群G中一个q阶生成元。

②KGC 随机选择主密钥s∈，生成KGC 公钥Ppub=sP。

③选择两个安全 的Hash 函数H1：{0，1}*→，H2：{0，1}*→。

④KGC 公开系统参数params={p，q，G，P，Ppub，H1，H2}，并保存主密钥s。

2）部分私钥生成算法（Extract-Partial-Private-Key）：

①KGC 接收到用户提交的身份标识IDA后，选择随机数rA∈，计算RA=rAP。

②计算h1=H1(IDA，RA，P，Ppub)；

③计算dA=rA+sh1。

④dA作为用户的部分私钥，RA作为用户的部分公钥，KGC 通过安全的方式将(RA，dA)返回给用户。

⑤用户验证dAP=RA+Ppubh1，若等式不成立，则申请重新生成部分私钥。

3）用户秘密值生成算法（Set-Secret-Value）：用户随机选择秘密值xA，其中xA∈。

4）完整私钥生成算法（Set-Private-Key）：生成sA=(dA，xA)作为用户的完整私钥。

5）公钥生成算法（Set-Public-Key）：

①通过用户秘密值xA计算XA=xAP；

②设置PA=(RA，XA)作为用户的完整公钥。

6）签名算法（Sign）：签名者为用户A，要签名的文件为M，签名者为用户B，算法如下。

①对于消息M，用户A 任选随机值t∈，计算T=tP。

②计算哈希值h2=H2(M，IDA，RA，XA，T)。

③计算u=t-1(h2xA+dA)，生成签名σ=(u，T)，并将消息M，身份标识IDA，用户公钥PA=(RA，XA)以及签名σ=(u，T)发送给验证者B。

7）验证算法（Verify）。当B 接收到消息M和签名后，计算：

判断等式T′=T是否成立，若成立则签名σ有效，输出true，否则输出false，其中T′为验证时的信息。

改进方案的正确性由以下方程保证：

4.3 验证方案中一种安全的公钥构造格式

汤永利等［9］方案无法抵抗敌手攻击的原因在于用户公钥和KGC 公钥在签名验证时存在线性关系。通过签名验证等式的伪造过程可以发现，当与公钥相乘的哈希函数中包含该部分公钥时，无法伪造该公钥。为使验证等式中的所有公钥都无法被敌手替换，本文提出形如式（9）的构造格式，保证敌手无法进行公钥替换攻击。

其中：Xi为用户的公钥；Pi为KGC 公钥。与用户公钥相乘的哈希函数hi中至少需要包含用户的公钥Xi，与KGC 公钥相乘的哈希函数hi+n中至少需要包含KGC 公钥Pi。

通过这种构造格式，将KGC 公钥同对应哈希值关联，任何对于KGC 公钥的修改都会引起哈希值的改变，而哈希值的改变又会影响公钥值，使第Ⅱ类敌手无法轻易地控制KGC公钥的变化，从而无法消除用户公钥。同时，通过将用户公钥与包含用户公钥的哈希函数关联，破坏原有的线性关系，第Ⅰ类敌手无法轻易地控制用户公钥的变化，从而无法达到消除KGC 公钥的目的。该构造格式既保证了签名验证等式的简便性，又避免了公钥之间的线性关系，对无证书签名方案中签名验证等式的安全构造具有参考价值。

4.4 安全性证明

定理1在随机预言机模型下，若AⅠ是一个第Ⅰ类敌手，可以在多项式时间内以不可忽视的优势ε攻破本方案中签名的不可伪造性，那么存在C1作为一个ECDLP 挑战者，可以在多项式时间内以不可忽视的优势ε′≥解决ECDLP。其中：q1为敌手AⅠ对随机预言机H1进行的用户生成查询次数；q2为敌手AⅠ进行的部分私钥查询次数。

证明 假设C1是针对ECDLP 的攻击者，拥有参数(P，aP)，C1的目标是计算出a。C1让其子程序AⅠ成为一个在自适应选择的消息攻击下攻破所提出签名方案的敌手，C1充当挑战者的角色，并且维持列表L、、，其中L列表用于跟踪敌手AⅠ对用户的公钥生成查询；用于追踪敌手AⅠ对预言机H1的询问；用于追踪敌手AⅠ对预言机H2的询问。

1）初始化阶段：挑战者C1设置KGC 公钥为Ppub=aP（隐含条件为系统主密钥s=a），产生系统参数params={p，q，G，P，Ppub，H1，H2}，挑战者将系统参数发送给敌手AⅠ。

2）查询阶段：用户生成查询。挑战者C1随机选取一个索引I，0 ≤I≤q1，q1为敌手AⅠ对随机预言机H1进行的用户生成最大查询次数，挑战者C1创建列表L，列表初始化为空，列表的存储格式为一个五元组(IDi，xi，Xi，Ri，di)，每当敌手根据身份标识IDi进行查询时，挑战者C1查询列表L，并按照如下步骤与敌手进行交互：

3）伪造阶段：敌手AⅠ经过以上查询之后，生成一个关于身份ID*、消息M*的签名σ=(u，T)，若ID*≠IDI，则挑战者C1终止程序；若ID*=IDI，并且敌手AⅠ没有对身份为IDI的消息M*进行过签名查询，敌手AⅠ就生成了一个对于身份ID*，消息M*的有效伪造签名。由于一个伪造签名无法解决挑战者C1的ECDLP，因此挑战者使用分叉引理［22］，选择两个不同的Hash 函数H1，可以获得两个不同的有效签名，故存在另一个有效的伪造签名σ′=(u′，T)，并且以下两个等式成立：

求得a=则挑战者成功地利用敌手AⅠ作为子程序，解决了ECDLP。

定义以下三个事件。

Δ1：敌手AⅠ不查询身份为ID*=IDI的部分私钥。

Δ2：敌手AⅠ成功输出身份为ID*=IDI的伪造签名。

Δ3：敌手AⅠ成功伪造两个不同的有效签名。

AⅠ在查询阶段共进行q2次部分私钥查询，每次查询到身份为IDI的概率为

AⅠ在伪造阶段输出身份为ID*=IDI的伪造签名概率为

已知AⅠ成功输出一个有效伪造签名的概率为ε，根据分叉引理［22］可知，敌手AⅠ成功伪造两个不同的有效签名的概率为

事件Δ3发生的概率即为ε′，若ε是不可忽视的，则挑战者C1可以以的概率解决ECDLP，这一概率也是不可忽视的。

定理2根据文献［20］的定义，在随机预言机模型下，若AⅡ是一个第Ⅱ类敌手，能在多项式时间内以不可忽视的优势ε攻破本方案中签名的不可伪造性，那么存在C2作为一个ECDLP 挑战者，可以在多项式时间内以不可忽视的优势ε′≥解决ECDLP，其中：q1为敌手AⅡ对随机预言机H1进行的用户生成查询次数；q3为敌手AⅡ进行的用户秘密值查询次数。

定理2 的证明同定理1 类似，区别在于敌手AⅡ拥有KGC主密钥，但是不能替换用户公钥，挑战者选定用户IDI的秘密值xI=a。查询过程在此不再赘述。

敌手AⅡ经过多轮查询之后，生成一个关于身份ID*、消息M*的签名σ=(u，T)，若ID*≠IDI，则挑战者C2终止；若ID*=IDI，并且敌手AⅡ没有对身份为IDI的消息M*进行过签名查询，那么敌手AⅡ就生成了一个对于身份ID*、消息M*的有效伪造签名，根据分叉引理［22］可知，选择两个不同的Hash函数H2，可以获得两个不同的有效签名，故存在另一个有效的伪造签名σ′=(u′，T)，并且以下两个等式成立：

其中：xI=a，可以求得则挑战者C2成功地利用敌手AⅡ作为子程序，解决了ECDLP。

文献［9］在验证方案上存在用户和KGC 公钥的线性关系，使敌手可以进行公钥替换攻击和恶意KGC 攻击，而改进后的方案通过增加哈希函数中的输入和验证等式的改进方法，加强了用户各部分公钥之间、用户公钥与KGC 公钥之间的关联程度，各部分公钥之前的系数不再是与该部分公钥无关的哈希值，而是含有该公钥的哈希函数，通过这种方法破坏了原有的线性性质，使敌手很难通过线性方程消除其余公钥。上述安全性证明将攻破签名方案的不可伪造性问题规约到了ECDLP 上，而ECDLP 是已经证明了的困难性问题，因此改进后的方案可以抵抗第Ⅰ类敌手和第Ⅱ类敌手攻击，该签名方案具有不可伪造性，在随机预言机模型下是安全的。

5 安全性与效率分析

将本文方案与文献［7-9］方案进行效率比较，其中相较于点乘运算、求逆运算的开销，散列运算、点加运算、大数加法运算和模运算时间都可忽略不计。本文用F 表示点乘运算，M 表示求逆运算。

由表2 可知，本文方案签名阶段只需要1F+1M，验证阶段只需要2F+1M。本文验证阶段只需要2F 的原因是：根据文献［23］中定义，诸如aP1+bP类的运算可以进行快速计算。经分析，文献［7-9］中的方案存在安全缺陷，其中文献［7］中的方案不能抵抗第Ⅰ类敌手发起的公钥替换攻击；文献［8］中的方案是完全不安全的，既不能抵抗第Ⅰ类敌手也不能抵抗第Ⅱ类敌手攻击；文献［9］中的9 个方案当中，第1、2、5、8、9 这5 个无证书签名方案不能抵抗第Ⅰ类敌手发起的公钥替换攻击，9 个方案对于第Ⅱ类敌手攻击是完全不安全的。在计算效率方面，本文提出的方案相较于文献［7-8］减少了验证阶段的点乘运算，提高了计算效率。

对于基于椭圆曲线的无证书签名方案，本文选择了曲线secp160r1，使用MIRACL 库在8 GB 内存，1.80 GHz 的CPU 环境中进行仿真。结果如下：

在仿真环境下得到单个点乘运算的平均时间开销约为0.552 706 ms，求逆运算的平均时间开销约为0.024 728 ms，图1 对比了存在的各个无证书签名方案的签名、验证以及总体方案的计算开销。各个方案的实际运行时间与表2 中分析所得的计算时间相符。与文献［7-8］方案相比，改进方案的验证时间明显减少；与文献［9］方案相比，在保证了安全的情况下，方案的运行时间持平。

表2 各方案安全性与效率分析Tab.2 Safety and efficiency analysis of each scheme

图1 现有方案计算开销对比Fig.1 Cost comparison of existing schemes

6 结语

本文对文献［9］中的所有无证书签名方案进行了分析，指出所有的方案都不能抵抗第Ⅱ类敌手的攻击，为此提出了改进方案，改进方案可以抵抗第Ⅰ类敌手和第Ⅱ类敌手攻击，具有更高的安全性。同时本文提出了一种在签名方案中安全的公钥构造格式，将该格式使用在签名验证等式的构造中，可以有效抵抗敌手的替换公钥攻击，相关结论对构造安全的无证书签名方案有参考意义。