可证明安全的无对的无证书签名方案研究

王 宁，王亚飞

（1. 黄河水利职业技术学院,河南 开封 475004；2.平顶山学院,河南 平顶山 467000）

0 引言

数字签名在公钥密码学中有着非常重要的地位。 在正常的网络活动中，它能保证用户网络活动的合法性和安全性。 签名可以在传统的公钥基础设施（Public Key Infrastructure，简称PKI）和基于身份的公钥密码学下实现[1]。 传统的PKI 密码学面临着复杂的证书管理问题，而基于身份的密码学存在与生俱来的密钥托管问题，即密钥生产中心（key generator center，简称KGC）知道用户的私钥。 有了用户的私钥，恶意的KGC 就可以很容易模仿用户对消息进行签名等操作。 为了解决以上问题，2003 年，Al-Riyami 等[2]提出了无证书公钥密码学。 在无证书公钥密码学中，用户的私钥由两部分构成，一部分是KGC利用系统的主密钥产生的用户部分私钥，另一部分是由用户自己选择的秘密值。 此外，用户的公钥是由用户自己选取的秘密值所导出的，无需PKI 证书。因此，无证书密码学避免了证书管理和密钥托管问题。

在无证书密码学应用中，一些研究者提出了基于双线性对的无证书数字签名方案[3～7]。 双线性对运算开销较大，一个对运算至少是椭圆曲线上点乘运算的20 倍[10]。 因此，人们又提出了一些基于指数运算的无对的无证书数字签名[8～9]。 然而，一个指数运算至少是椭圆曲线上点乘运算的10 倍[10]。为了进一步提高效率，利用ECDSA 和Schnorr 签名的思想，笔者提出一个无对的无证书签名方案。 新的方案没有双线性对运算和指数运算，方案效率要比其他现有

的无证书签名方案更高。

1 基本理念模型

1.1 困难问题假设

令E/Fq表示定义在有限素域Fq上的椭圆曲线E:y2=x3+ax+bmodq，其中a，b∈Fq，q＞3，4a3+27b2≠0modq。 E/Fq上的点和一个 “无穷远点”O 组成一个群：G={(x,y):x,y∈Fq,E(x,y)=0}U{O}。

令群G 的阶为n。在如下的加运算下，G 形成一个加法循环群：

令P,Q∈G，l 是过点P 和Q 的直线（若P=Q，则l 是过点P 的切线），R 是l 与E/Fq相交的第3 个点。过点R 作垂线交E/Fq于点R'（另一个交点为O），则P+Q=R'。与此相应，可以定义群G 上的乘法运算为：tP=P+L+P(t 次，t∈¢*q)。

在椭圆曲线加法群上，困难问题是，多项式时间算法不能解决它。

椭圆曲线离散对数问题(ECDLP)：给定两个元素P，Q∈G，求整数a∈¢*q，使得P=aQ 成立。

1.2 无证书数字签名的定义

一个无证书数字签名方案[3]由以下6 个算法构成：

（1）系统建立（Setup）。 输入安全参数l，返回系统公共参数params 和系统主密钥s。 KGC 运行该算法，建立了一个无证书系统。

（2）部分私钥提取(Extract-Partial-Private-Key)。输入params，系统主密钥和用户的身份ID，输出部分私钥DID。 KGC 运行该算法，产生用户的部分私钥，并通过安全信道发给相应的用户。

（3）秘密值建立(Set-Secret-Value)。 输入params和用户的身份ID，输出用户的秘密值xID。 系统中每个用户均执行该算法，产生各自的秘密值。

（4）公钥建立(Set-Public-Key)。输入params 和用户的秘密值xID，输出用户公钥pkID。 系统中每个用户执行该算法，产生各自的公钥，并公开公钥。

（5）签名（Sign）。 这是无证书签名算法。 输入params、待签消息m、用户（签名人）的身份ID、公钥pkID、部分私钥DID以及秘密值xID，该算法输出签名σ。

（6）验证(Verify)。 这是一个确定的签名验证算法。 输入params，签名人的身份ID、公钥pkID、消息m 以及签名σ，返回“1”，说明该签名有效，返回“0”说明该签名无效。

1.3 无证书数字签名的安全模型

在无证书密码系统中，有两种类型具备不同能力的敌手A1，A2。 假设A1模拟的是一个不诚实的用户，而A2是一个恶意但被动的KGC。

类型 I 的敌手A1：A1不知道系统主密钥及用户的部分私钥，但可以代替任意用户的公钥。 因为在无证书密码系统中，公钥和持有者之间没有认证存在。

类型II 的敌手A2：A2掌握系统主密钥，知道用户的部分私钥，但它不能替换目标用户的公钥。

Huang[3]将（类型I/类型II）敌手按能力从弱到强分 成 了3 类：Normal 敌 手、Strong 敌 手 和Super 敌手。对于Super 敌手，即使其在替换用户公钥时不提供该公钥对应的秘密值，也能得到在替换后的公私钥下有效的消息——签名对。 方案如果能够抵抗住Super 敌手的攻击，便能抵抗住Strong 敌手和Normal敌手的攻击。

2 新方案的设置规划

本文提出的无对的无证书签名方案由以下6个算法构成（本方案所计算的整数均需要mod q）。

2.1 系统建立

（1）给定安全参数l，KGC 选择l 比特的大素数q，定义1.1 节所要求的{Fq;E/Fq;G;P}。

（2）选择主密钥s∈¢*q，并计算Ppub=sP。 选择Hash函数H1:{0,1}*×G→Z*q、H1:{0,1}*×G×Z*q→Z*q和H3,H4:{0,1}*×{0,1}*×G3→c*q。

（3）公开系统参数params={Fq,E/Fq,G,P,Ppub,H1,H2}，秘密保存主密钥s。

2.2 部分私钥提取

（1） 输入用户的身份ID 后，KGC 随机选取r0,r1∈¢*q, 计算R0=rop，d0=(r0+H1(ID,R0)s)-1。

（2）计算R1=r1P，并将R1的x 轴坐标，取整求余为x1，然后计算d1=r-11(sx1+H2(ID,R0,x1)。

（3）设置d0为用户的部分私钥，{R0,x1,d1}为用户的部分公钥。

2.3 秘密值建立

身份为ID 的用户随机选取ZID∈¢*q作为自己的秘密值。

2.4 公钥建立

身份为ID 的用户计算ZID=zIDP， 并设置PKID={ZID,R0,x1,d1}为自己的公钥。

2.5 签名

身份为ID 的用户对消息m∈(0，1)*签名如下：（1）随机选取k∈¢*q，计算K=kp。 （2）计算u=H3(m,ID,K,PKID)，w=H4(m,ID,K,PKID)。 （3）计算v=k+ud-10+wziID。 则签名者对消息m 的签名σ=(u,v,w)。

2.6 验证

给定params。 签名者的身份ID 以及对应的公钥PKID ={ZID,R0,x1,d1}。 验 证 者 收 到(m,σ)后，计算Q=d-11x1·Ppub+d-11H2(ID,R0,x1)·P，K'=vp-u[R0+H1(ID,R0)·Ppub]-wZID，将Q 的x 轴坐标为xQ。然后，验证等式xQ=x1和u=H2(ID,m,K',PKID)是否成立。 如果两个等式成立，则输出“接受”，否则，输入“拒绝”。

3 新方案的安全性证明和协议条件比较

3.1 安全性证明

以下在随机预言机模型下，证明新方案的安全性。

定理1：在ECDLP 和随机预言机模型下，所提方案在适应性选择消息和身份攻击下，是抗存在性伪造的。

上述定理可以由下面的引理1 和引理2 推导出。

引理1：在ECDLP 和随机预言机模型下，对于Super 类型I 敌手A1，新方案在适应性选择消息攻击下是抗存在性伪造的。

证明： 假定给算法X 一个离散对数问题的实例：(P,β=aP∈G1)，X 的任务是计算和输出该问题的解a。

X 运行Setup 算法，产生系统参数params={Fq;E/Fq;G;P;Ppub,H1,H2}，其中Ppub=sP。 X 随机挑选IDI(1≤I≤qH1, 是Super 敌手A1访问H1预言机的最大次数) 作为这次游戏的挑战者,发送系统参数params 给A1。

A1执行以下询问：

Create(IDi)：X 维持一个包含元组(IDi,{Ri,d1i,xi,Zi},{d0i,zi})的列表Lcreate。

如果IDi≠IDI，X 随机选择zi∈c*q， 计算Zi=ziP；随机选择d0i,h1i∈c*q，计算Ri=(d0i)-1P-hoiPpub，令h1i=H1(IDi,Ri)；随机选择ri,h2i∈¢*q，记riP 的x 轴坐标为xi, 计算d1i=r-1i(sxi+h2i)，令h2i=H1(IDi,Ri,xi)。

否则，X 随机选择Zi∈¢*q，计算Zi=ziP；随机选择hi∈c*q，doi=⊥,计算Ri=aP-hiPpub, 令hi=H1(IDi,Ri)；随机选择ri,h2i∈c*q，记riP 的x 轴坐标为xi, 计算d1i=r-1i(sxi+h2i)，令h2i=H1(IDi,Ri,xi)。

在列表Lcreate 中记录 (IDi,{Ri,d1i,xi,Zi},{d0i,zi}),在列表LH1记录(IDi,Ri,h1i),在列表LH2中记录(IDi,Ri,xi,h2i)。

不失一般性，我们假定A1在执行以下询问之前已经执行有关ID 的Create 询问。

H1-询问：X 模拟H1随机预言机，维持列表LH1，记录元组(IDi,Ri,h1i)。 如果列表中存在，返回h1i，否则随机选择h1i∈c*q返回给A1，并添加到列表LH1中。

H2-询问：X 模拟H2随机预言机，维持列表LH2，记录元组(IDi,Ri,h2i)。 如果列表中存在，返回h2i，否则随机选择h2i∈c*q返回给A1，并添加到列表LH2中。

H3-询问：X 模拟H3随机预言机，维持列表LH3，记录元组(IDi,m,Ki,PKi,h3i)。 如果列表中存在，返回h3i，否则随机选择h3i∈c*q返回给A1，并添加到列表LH3中。

H4-询问：X 模拟H3随机预言机，维持列表LH4，记录元组(IDi,m,Ki,PKi,h4i)。 如果列表中存在，返回h3i，否则随机选择h4i∈c*q返回给A1，并添加到列表LH4中。

Extract-Partial-Private-Key(IDi)：如 果IDi=IDI，则X 中止；否则X 查找列表Lcreate 中对应于IDi的元组(IDi,{Ri,d1i,xi,Zi},{d0i,zi})，返回部分私钥d0i。

Secret-Value-Extract(IDi)：X 查找列表Lcreate中对应于IDi的元组(IDi,{Ri,d1i,xi,Zi},{d0i,zi})，返回秘密值zi。

Public-Key-Replace(IDi,PK'i=(R'i,d1'i,x'i,W'i)：X 首先计算Qi=(d1'i)-1x'i·Ppub+(d1'i)-1H2(IDi,r'i,x'i)·P，Qi的x 轴坐标为xQi。然后验证等式xQi=xi是否成立。如果不成立，则拒绝替换；如果成立，则查找列表Lcreate中对应于IDi的元组(IDi,{Ri,d1i,xi,Zi},{d0i,zi}), 将{Ri,d1i,xi,Zi}替换为{R'i,d1'i,x'i,W'i}。这里需要说明的是，由于{d1i,xi})是符合椭圆曲线数字签名算法ECDSA 的签名，而ECDSA 是不可伪造的， 所以对于任何IDi来说，其Ri，d1i,xi是不可能被敌手替换的， 只有Zi可能被替换。

Public-Key-Request(IDi)：C 查找列表Lcreate中对应于IDi的元组(IDi,Ri,Zi,di,xi)，返回(Ri,Zi)。

Super-Sign 询问： 假设A1作出签名询问(IDi,m)。

如果IDi≠IDI且对应IDi的公钥未被替换，X 知道用户的秘密值和部分私钥，则按照这些私钥产生签名。 否则，X 随机选取ui,vi,wi∈c*q作为签名， 令ui=H3(IDi,m,viP-ui(Ri+H1(IDi,Ri)Ppub)-Zi,PKi)，并将(IDi,m,viP-ui(Ri+H1(IDi,Ri)Ppub)-Zi,PKi,ui)添加到列表LH3中，X 返回一个无碰撞的ui作为H2的输出内容，并传送给A1。

伪造：模拟结束后，最终A1以一个不可忽略的概率输出一个有效签名。如果ID*≠IDI，则X 停止模拟。 否则，由分叉引理，存在算法可以在PPT 时间内生成两个有效签名(IDi,m,K,u1,v1,w1)和(IDi,m,K,u2,v2,w1)，且u1≠u2。 则有以下等式成立：

K=v1P-u1(RI+H1(IDI,RI)Ppub)-w1ZI

K=v2P-u2(RI+H1(IDI,RI)Ppub)-w1ZI

由这两个式子得： (v1-v2)P=(u1-u2)aP

所以有a=(v1-v2)/(u1-u2)， 从而X 解决了ECDLP的一个实例。

引理2：在ECDLP 和随机预言机模型下，对于Super 类型II 敌手A2， 所提方案在适应性选择消息攻击下是抗存在性伪造的。

证明： 假定给算法X 一个离散对数问题的实例：(P，β=aP∈G1)，X 的任务是计算和输出该问题的解a。

X 随机选取s∈c*q作为系统主密钥，计算Ppub=sP，然 后 产 生 系 统 参 数params={Fq；E/Fq；G；P；Ppub，H1，H2}。 X 随机挑选IDI(1≤I≤qH1，是Super 敌手A2访问H1预言机的最大次数) 作为这次游戏的挑战者，发送系统参数params 和s 给A2。 由于A2知道s，它不再询问Extract-Partial-Private-Key。

A2执行以下询问：

Create(IDi)：X 维持一个包含元组(IDi,{Ri,d1i,xi,Zi},{d0i,zi})的列表Lcreate。

X 随机选择roi,h1i∈¢*q， 计算Ri=r0iP 和d0i=(roi+shoi)-1,令h1i=H1(IDi,Ri)；随机选择ri,h2i∈¢*q，记riP 的x 轴坐标为xi。 计算d1i=r-1i(sxi+h2i)，令h2i=H1(IDi,Ri,xi)。

如果IDi≠IDI，X 随机选择Zi∈¢*q，计算Zi= ziP；否则，X 令zi=⊥，计算Zi=β=aP；

最后，在列表Lcreate中记录(IDi,{Ri,d1i,xi,Zi},{d0i,zi}),在列表LH1中记录(IDi,Ri,h1i),在列表LH2中记录(IDi,Ri,xi,h2i)。

Hi-询问(i=1,2,3,4)同引理1。

Secret-Value-Extract(IDi)：如果IDi=IDI，则X 中止； 否则，X 查找列表Lcreate中对应于IDi的元组(IDi,{Ri,D1i,xi,Zi}, {doi,zi})，返回秘密值zi。

Public-Key-Replace(IDi)：如果IDi=IDI，则X 中止；否则，X 按照引理1 中的Public-Key-Replace 询问进行判断和回答。

Super-Sign 询问： 假设A2作出签名询问(IDi,m)。 X 随机选取ui，vi，wi∈¢*q作为签名，令ui=H3(IDi,m，viP-ui(Ri+H1(IDi,Ri)Ppub)-Zi,PKi)，并将(IDi,m,viP-ui(Ri+H1(IDi,Ri)Ppub)-Zi,PKi,ui)添 加 到 列 表LH3中，X 返回一个无碰撞的ui，作为H2的输出内容，并传送给A2。

伪造：模拟结束后，最终A2以一个不可忽略的概率输出一个有效签名(ID*,m,σ*=(u*,v*)。 如果ID*≠IDI，则X 停止模拟。 否则，由分叉引理，存在算法可以在PPT 时间内生成两个有效签名(IDi,m,K,u1,v1,w1)和(IDi,m,K,u2,v2,w1)，且u1≠u2。 则有以下等式成立：

由这两个式子得： (v1-v2)P=(w1-w2)aP

所以有a=(v1-v2)/(w1-w2)， 从而X 完成了解决ECDLP 问题的一个实例。

3.2 协议条件比较

本节从配对运算（P）、指数运算（E）、点乘运算（M）这3 个运算来进行效率比较。

表1 无证书签名方案比较Table 1 Non-certificate signature plan comparison

在同等安全级别下（椭圆曲线上160 bit 的群元素等同于1024 bit RSA 安全级别）， 运行一次双线性对所需的时间约为有限域上指数运算的10 倍左右。 由表1 可知，所提方案的协议具有较高的效率和较强的安全性。

4 结语

本文提出的无对的无证书签名方案，由于不含双线性对和指数运算，计算开销明显降低，效率较高。在安全性方面，它在椭圆曲线离散对数问题假设下，它能够抵抗住无证书签名的最强攻击类型。因此，安全性较强。

[1] A. Shamir. Identity-based Cryptosystems and Signature Schemes [M]. Advances in Cryptology-Crypto'84, LNCS 196, Berlin: Springer-Verlag, 1985：47-53.

[2] S. Al-Riyami, K. Paterson. Certificateless public key cryptography [M]. ASIACRYPT 2003, LNCS 2894,Berlin: Springer-Verlag, 2003：452-473.

[3] X. Huang, Y. Mu, W. Susilo, D. Wong, and W. Wu.Certificateless signature revisited [M]. ACISP 2007,LNCS 4586, Berlin: Springer-Verlag, 2007：308-322.

[4] H. Du，Q.Wen，Efficient and provably-secure certificateless short signature scheme from bilinear pairings[J]. Computer Standards and Interfaces, 2009,31(2): 390-394.

[5] L. Zhang, F. Zhang, A new provably secure certificateless signature scheme. ICC 2008, IEEE Communications Society.

[6] B. Hu，D. Wong，Z. Zhang，et al.Certificateless signature:a new security model and an improved generic construction[J]. Design, Codes and Cryptography,2007,42:109-126.

[7] K. Choi，J. Park，J. Hwang, et al. Efficient certificateless signature schemes. ACNS'2007[M]. LNCS 4521, Berlin: Springer-Verlag, 2007:443-458.

[8] A. Ge，S. Chen，X. Y. Huang. A concrete certificateless signature scheme without pairings. The 2009 International Conference on Multimedia Information Networking and Security [J]. IEEE Computer Society, 2009(2):374-377.

[9] J. Zhang，J. Mao. An efficient RSA-based certificateless signature scheme [J]. The Journal of Systems and Software(2011)，2011(09):36.

[10] X. Cao，W. Kou，X. Du. A pairing-free identity-based authenticated key agreement protocol with minimal message exchanges [J]. Information Sciences, 2010，180(15)：2895-2903.