邹 昌 芝

(荆楚理工学院教育技术中心　湖北 荆门 448000)



可证安全的无证书签密方案

邹 昌 芝

(荆楚理工学院教育技术中心湖北 荆门 448000)

研究了几种新近提出的无对运算的无证书签密方案，发现存在正确性或安全性的缺陷，提出一种新的无对运算的无证书签密方案。新签密方案改变了现有方案的线性密钥结构，能抵抗类型I敌手发起的公钥替换攻击；利用哈希函数将签密者和解签密者的身份以及待签密消息进行绑定，防止内部攻击发生。在随机预言模型下，方案的不可伪造性和机密性被规约为多项式时间敌手求解离散对数DL(DiscreteLogarithm)问题和判定DH(DecisionDiffie-Hellman，DDH)问题，具有可证明安全性。对比已有方案，该方案不仅保证了安全性，而且计算开销和实现成本都较低，适用于在无线传感网络等计算、存储和通信资源受限的应用场景保障数据的机密性、完整性和认证性。

无证书密码学签密双线性对随机预言模型

0　引　言

无证书密码体制[1]CLC(CertificatelessCryptography)在基于身份密码体制[2,3]IBC(Identity-BasedCryptography)的基础上增加一对由用户自主控制的密钥，避免了IBC方案的密钥托管问题。与IBC相同，CLC也不产生用户的公钥证书，简化了基于公钥基础设施(PKI)公钥密码算法的密钥管理方案。因此，CLC一经提出，得到众多研究者的关注，成为信息安全领域的研究新热点之一。

早期的CLC方案基于双线性映射理论，使用计算开销较高的双线性对运算。根据Chen[4]等人的研究，1次双线性对运算的计算开销约等于21次椭圆曲线上的点乘运算。因此，基于双线性映射理论的CLC方案通常计算开销较高。利用Schnorr的短签名机制[5]产生用户部分私钥，Baek[6]等人提出无双线性对运算的CLC算法。无对运算的CLC方案在无线传感网络、无线Mesh网络等计算、存储和通信资源受限的网络环境下具有广阔的应用前景。

签密[7]SC(Signcryption)以低于“签名”+“加密”的开销，同时实现数据的机密性、完整性和认证性，具有重要的研究和应用价值。2008 年，Barbosa等人[8]首次将签密机制引入CLC领域，提出无证书的签密机制(CL-SC)。该方案基于双线性映射理论，并且不能抵抗扩展不可伪造攻击。Barreto[9]提出在签密和解签密算法中不使用双线性对运算的CL-SC方案，但是该方案的密钥产生算法仍使用了双线性对运算，并且被指出不满足机密性和不可否认性。随后，基于Baek[6]等人的研究，一些研究者提出了完全无双线性对的CL-SC方案[10-16]。其中，文献[10,11,13]中提出的几种方案已被指出存在机密性和不可伪造性缺陷[14,17,18]，本文进一步指出，文献[14-16]中的CL-SC方案也存在正确性和安全性缺陷。因此，安全的、无对运算的无证书签密机制还需要进一步研究。

本文提出一种新的可证明安全的和无对运算的CL-SC方案。方案的部分私钥产生算法沿用了Schnorr[5]的短签名机制；通过对签密者和解签密者的部分私钥和私有秘密去线性化，防止CLC体制下类型I敌手发起的公钥替换攻击；利用哈希函数将签密者和解签密者的身份以及待签密消息进行绑定，防止内部攻击发生。在随机预言模型下，本文CL-SC方案被证明满足机密性和不可伪造性。

1　背景知识

1.1数学困难问题及假设

本文无证书签密方案基于椭圆曲线上的非GapDiffie-Hellman(GDH)群[19]。

椭圆曲线上的离散对数DL问题、计算DH(ComputationalDiffie-Hellman,CDH)问题和判定DH问题及相关假设定义如下。

DLP假设不存在概率多项式时间算法能成功解决DL问题。

DDH假设假设G为非GDH群，那么不存在概率多项式时间算法能成功解决DDH问题。

需要指出，对于GDH群[19]，DDH问题是可解的，而对于非GDH群，DDH假设[20]成立。

1.2无证书签密方案及其安全模型

无证书的签密方案主要包括：系统建立、部分私钥产生、用户密钥产生、签密和解签密五个算法。部分文献[10,11,14]将用户密钥产生算法细分为私有秘密产生、设置公钥和设置私钥三个算法，本文将这三个算法合并成为用户密钥产生算法。系统建立算法由密钥产生中心(KGC)执行，输入安全参数，输出系统公开参数，建立KGC的主密钥对；部分私钥产生算法由KGC执行，为每位用户产生部分私钥；签密算法由发送者执行，进行签密运算，输出签密密文；解签密算法由接收者执行，输入签密密文，输出明文，或者拒绝(表明签密密文无效)。

一个安全的签密方案[21]至少应实现机密性(选择密文攻击下加密不可区分性，IND-CCA2)和不可伪造性(选择消息攻击下不可伪造性，EUF-CMA)。本文采用文献[21]中定义的两类敌手模型(记为Type-I敌手和Type-II敌手，分别简写为AI和AII)和4类游戏(记为GameI、GameII、GameIII和GameIV)分析CL-SC的安全性。

敌手AI模拟一类外部攻击者，他被允许替换任意用户的公钥和询问未被替换公钥用户的私有秘密，但是他不被允许询问KGC的主密钥和特定用户(用于挑战的用户，本文用ID*代表)的部分私钥。敌手AII模拟恶意的KGC，他可以访问系统主密钥，但他不被允许替换特定用户(用于挑战的用户ID*)的公钥以及访问该用户的私有秘密。

GameI和GameIII模拟AI与挑战者B之间的游戏，GameII和GameIV模拟AII与挑战者B之间的游戏。CL-SC方案的安全性定义为不存在多项式时间敌手(AI和AII)赢得GameI-II-III-IV。限于论文篇幅，详细的安全模型定义请参考文献[21]，本文4.2节给出了较完整的游戏模拟过程。

2　两种CL-SC方案的密码学分析

2.1XZ-CL-SC方案分析

最近，夏昂等[15]提出一种无双线性对的无证书签密方案(记为XZ-CL-SC)，并声称在随机预言模型下具有机密性和不可伪造性。下面简要回顾XZ-CL-SC方案。

解签密用户UB接收到σ后，计算W′=zB·(XA+gH1(IDA,XA) +PH2(IDA,IDB))，解密m‖R‖t=H3(W,IDA)⊕σ，得到t、R；然后验证等式：t·zB·XA=R是否成立。若等式成立，用户UB接受消息m，否则拒绝。

本文分析发现，XZ-CL-SC方案存在三方面的缺陷。

第一，不满足正确性。在签密算法阶段，UA不能计算t=r·yA/xA。因为xA是KGC在计算UA的部分私钥“dA=xA+sQA”时选择的临时秘密参数，不会发送给UA，并且也不能发送给UA。UA一旦知道了xA，那么他可以利用算式“s= (dA-xA)/QAmodq”反求KGC的主密钥。在实际应用中，为了保证KGC主密钥和用户部分私钥的安全，在计算得到dA后，KGC必须删除xA。因此，UA得不到xA，也就不能计算t=r·yA/xA。

第二，该方案不能防止AII的签密伪造攻击。用户UB在整个解签密过程中没有用到UA的完整公钥，仅使用了XA，使得该方案不能有效验证UA在签密算法中是否使用了其私有秘密yA(事实上，没法验证，因为yA与用户的公钥之间没有任何关联)。因此，AII无需使用UA的私有秘密yA就能伪造一个有效的签密密文。

2.2ZW-CL-SC方案分析

针对刘文浩等人文献[11]的CL-SC方案存在的安全缺陷，周才学等人[14]提出一种改进方案 (记为ZW-CL-SC)，简要描述如下。

签密给定待签密消息m、发送者身份IDA，接收者身份IDB，签密过程如下：

文献[14]给出了ZW-CL-SC方案的形式化安全证明，证明其满足机密性和不可伪造性。但是，本文分析发现，在第I类敌手AI攻击下，ZW-CL-SC方案不满足不可伪造性和机密性。下面给出一个攻击实例。

可见，AI成功地伪造了IDA的签密。

由此证明，ZW-CL-SC方案在AI攻击下不满足不可伪造性和机密性。

3　新的无对运算的CL-SC方案

签密给定待签密消息m、发送者身份和私钥(IDA,dA,xA)、接收者身份和公钥(IDB,RB,XB)，签密过程如下：

2) 计算qB=H1(IDB,RB)和K=u(RB+qBP0)+vXB；

3) 计算g=H2(m,K,U,IDA,IDB)、h=H3(m,K,V,IDA,IDB)和σ=gdA+hxA+u+v；

4) 计算密文c=K⊕(m‖σ)，发送(c,U,V)给IDB。

解签密收到(c,U,V)后，IDB计算K′=dBU+xBV，然后解密消息(m‖σ)=K′⊕c，计算g′=H2(m,K′,U,IDA,IDB)、h′=H3(m,K′,V,IDA,IDB)和qA=H1(IDA,RA)，验证σP=g′(RA+qAP0) +h′XA+U+V是否成立。若等式成立则接受消息m，否则拒绝。

4　分析与比较

4.1正确性分析

本文方案的计算正确性可由下列式子验证。

K′=dBU+xBV=(rB+sqB)uP+xBvP

=u(rB+sqB)P+vxBP=u(rBP+qBsP)+vxBP

=u(RB+qBP0)+vXB=K

(1)

σP=gdAP+hxAP+uP+vP

=g(rA+sqA)P+hXA+U+V

=g(RA+qAP0)+hXA+U+V

(2)

根据式(1)，IDB能正确解密消息(m‖σ)；同样的，由于K′=K，可得：g′=g，h′=h，根据式(2)，等式σP=g((RA+qAP0)+h(XA+U+V成立。因此，本文签密方案从计算上是有效的，具有正确性。

4.2安全性分析

证明假设存在Type-I敌手AI，攻破本文的无证书签密方案，那么，必然存在算法B利用AI解决DDH问题。即，给定DDH挑战实例(P,aP,bP,T)∈G4，B判定T=abP，或者只是G上的一个随机成员。下面算法模拟B利用AI解决DDH问题。

初始化输入安全参数k，B运行系统建立算法，产生参数(p,q,G,P,P0)发送给AI。这里，设定系统公钥P0=aP，主密钥未知。哈希函数Hi(i=1,2,3)被模拟为B控制下的随机预言机。

第1阶段询问AI执行多项式有界次的以下询问。

用户创建询问B维护初始为空的列表LID，格式为。提交用户身份IDi，如果元组在LID中已存在，则忽略；否则，B执行H1询问，取得qi，然后：

部分私钥询问提交用户身份IDi，如果IDi=ID*，B终止游戏；否则，B返回对应的部分私钥di作为应答。

私有秘密询问提交用户身份IDi，B返回对应的私有秘密xi作为应答。

公钥询问提交用户身份IDi，B返回IDi的公钥。

签密询问B维护初始为空的列表LS，格式为。AI提交待签密消息mi、发送者身份IDa和接收者身份IDb(为了不失普遍性，要求IDa≠IDb)。

否则，IDa≠ID*，B按照签密算法进行计算，并根据需要执行Hi(i=1,2,3)询问和密钥询问，然后返回签密密文(ci,Ui,Vi)；

最后，B将插入LS，将和分别插入L2和L3。

解签密询问提交密文(ci,Ui,Vi)、发送者身份IDa和接收者身份IDb，如果IDb≠ID*，B计算Ki=dbUi+xbVi，解密消息(mi‖σi)=Ki⊕ci，查询列表L2和L3，如果L2中存在元组和L3中存在，取得gi和hi，验证等式σiP=gi(Ra+qaP0)+hiXa+Ui+Vi成立，则返回mi作为应答；否则，L2或L3中不存在相应表项，或者存在相应表项，但验证等式不成立，则返回⊥；否则，IDb=ID*，B不具有ID*的完整私钥，不能解密密文，那么B检索列表LS，如果LS中存在表项与之匹配，即五项相等，B返回mi作为应答(这里，LS中存在相应表项，表明该签密由B产生，根据签密询问算法，(ci,Ui,Vi)为一个有效的签密密文)；否则，LS中不存在相应表项，返回⊥。

第2阶段询问AI可以继续执行以上询问，但不能询问ID*的部分私钥，以及针对挑战密文(c*,U*,V*)的解签密询问。

猜测最后，AI输出其猜测位τ′。如果τ′=τ，那么B返回1，表明T=abP；否则τ′≠τ，那么B返回0，表明T是G上的一个随机值。(在游戏过程中P0=aP，t-1U*=bP，a和b未知)。

假设至多创建了qu个用户，执行了qi次Hi询问(i=1,2,3)、qpa次部分私钥询问、qsk次私有秘密询问、qpk次公钥询问、qpr次公钥替换询问、qs次签密询问和qus次解签密询问。

证毕。

证明假设存在Type-II敌手AII，攻破本文的无证书签密方案，那么，必然存在算法B利用AII解决DDH问题。

第1阶段询问AII执行多项式有界次的以下询问。

H1、H2、H3询问与定理1相同。

用户创建询问提交用户身份IDi，如果元组在LID中已存在，则忽略；否则，B执行H1询问，取得qi，然后：

部分私钥询问提交用户身份IDi，B返回对应的部分私钥di作为应答。

私有秘密询问提交用户身份IDi，如果IDi=ID*，B终止游戏；否则，B返回对应的私有秘密xi作为应答。

公钥询问与定理1相同。

签密询问AII提交待签密消息mi、发送者身份IDa和接收者身份IDb。

否则，IDa≠ID*，B按照签密算法计算，并根据需要执行Hi(i=1,2,3)询问和密钥询问，然后返回签密文(ci,Ui,Vi)；

最后，B将插入LS，并将和分别插入L2和L3。

解签密询问与定理1相同。

第2阶段询问AII可以继续执行以上询问，但不能询问ID*的私有秘密，以及针对挑战密文(c*,U*,V*)的解签密询问。

猜测最后，AII输出其猜测位τ′。如果τ′=τ，那么B返回1，表明T=abP；否则τ′≠τ，那么B返回0，表明T是G上的一个随机值(在游戏过程中，X*=aP，t-1V*=bP，a和b未知)。

假设至多创建了qu个用户，执行了qi次Hi询问(i=1,2,3)、qpa次部分私钥询问、qsk次私有秘密询问、qpk次公钥询问、qpr次公钥替换询问、qs次签密询问和qus次解签密询问。

证毕。

证明假设存在Type-I敌手AI，攻破本文的无证书签密方案，那么，必然存在算法B利用AI解决DL问题。即，给定DL问题挑战实例(P,aP)∈G2，B计算a。

初始化与定理1相同。

询问与定理1相同。

伪造询问阶段结束后，AI提交挑战用户身份(ID*,IDb)、挑战消息m*及其签密文(c*,U*,V*)。

B计算K*=dbU*+xbV*，解密消息(m*‖σ*)=K*⊕c*。根据分叉引理[22]，B利用预言机重放攻击技术可以得到两个合法的签名(m*,ID*,IDb,U*,V*,σ*,g*,h*)和(m*,ID*,IDb,U*,V*,σ**,g**,h*)。其中，σ*≠σ**，g*≠g**。并且满足：

σ*=g*d*+h*x*+u*+v*

σ**=g**d*+h*x*+u*+v*

那么，B计算：

σ**-σ*=(g**d*+h*x*+u*+v*)-

(g*d*+h*x*+u*+v*)

=(g**-g*)d*

作为对DL问题的回答(在游戏过程中：P0=aP)。

假设至多创建了qu个用户，执行了qi次Hi询问(i=1,2,3)、qpa次部分私钥询问、qsk次私有秘密询问、qpk次公钥询问、qpr次公钥替换询问、qs次签密询问和qus次解签密询问。

证毕。

证明假设存在Type-II敌手AII，攻破本文的无证书签密方案，那么，必然存在算法B利用AII解决DL问题。

初始化与定理2相同。

询问询问阶段与定理2相同。

伪造询问阶段结束后，AII提交挑战用户身份(ID*,IDb)、挑战消息m*及其签密文(c*,U*,V*)。

B计算K*=dbU*+xbV*，解密消息(m*‖σ*)=K*⊕c*。根据分叉引理[22]，B利用预言机重放攻击技术[22]可以得到两个合法的签名(m*,ID*,IDb,U*,V*,σ*,g*,h*)和(m*,ID*,IDb,U*,V*,σ**,g*,h**)。其中，σ*≠σ**，h*≠h**。并且满足：

σ*=g*d*+h*x*+u*+v*

σ**=g*d*+h**x*+u*+v*

那么，B计算：

σ**-σ*=(g*d*+h**x*+u*+v*)-

(g*d*+h*x*+u*+v*)

=(h**-h*)x*

作为对DL问题的回答(在游戏过程中：X*=aP)。

假设至多创建了qu个用户，执行了qi次Hi询问(i=1,2,3)、qpa次部分私钥询问、qsk次私有秘密询问、qpk次公钥询问、qpr次公钥替换询问、qs次签密询问和qus次解签密询问。

证毕。

4.3分析与对比

表1对比了几种无对运算的CL-SC方案。表中计算开销为签密与解签密算法的总和，只统计了每种方案的指数运算E(基于乘法循环群)和点乘运算M(基于加法循环群)的次数，其他运算的计算量相对较低。

表1　无对的无证书签密方案比较

本文方案汲取了上述方案的经验教训，在安全性方面做出两点改进，一是，改变了部分私钥与私有秘密之间的线性结构，采用随机参数u、v、g、h分别对签密者和解签密者的两个密钥去线性化；二是，利用哈希函数H2和H3将签密者、解签名者身份以及待签密消息进行绑定，除非哈希碰撞事件发生，否则不能实施文献[14]所描述的内部攻击。

上述分析可见，到目前为止，仅有SSP-CL-SC[12]方案真正实现了可证明安全性，未发现相关攻击实例报道。与SSP-CL-SC方案对比，本文方案在不降低安全性的同时，更加简化。比如，本文密钥结构更简单。SSP-CL-SC方案定义了额外的密钥参数，但是该密钥参数对增强安全性没有实际意义(签密和解签密算法中都没有使用，具体请参考文献[12]第6节)，反而增加了计算开销和实现成本。

5　结　语

本文提出一种新的基于椭圆曲线密码的无证书签密方案。基于椭圆曲线上的DL假设和DDH假设，本文方案在随机预言模型下被证明满足机密性和不可伪造性，实现了可证明安全。此外，本文分析指出现有几个无证书签密方案存在正确性或安全性方面的缺陷。无对的无证书签密方案计算开销远低于基于双线性映射理论的签密方案，适合计算、存储和通信资源有限的无线传感设备，实现对数据的机密性、完整性和认证性保护。

[1]AlRiyamiSS,PatersonKG.Certificatelesspublickeycryptography[C].ASIACRYPT2003,LNCS2894,Berlin:Springer-Verlag,2003:452-473.

[2]ShamirA.Identity-basedcryptosystemsandsignatureschemes[C]//ProceedingsofCRYPTO1984,LNCS196,Berlin:Springer-Verlag,1985:47-53.

[3]BonehD,FranklinMK.Identity-basedEncryptionfromtheWeilPairing[C]//Proc.ofCRYPTO’01.Berlin,Germany:Springer-Verlag,2001:213-229.

[4]ChenL,ChengZ,SmartNP.Identity-Basedkeyagreementprotocolsfrompairings[J].InternationalJournalofInformationSecurity,2007,6(4):213-241.

[5]SchnorrCP.Efficientsignaturegenerationforsmartcard[J].JournalofCryptology,1991,4(3):161-174.

[6]BaekJ,SafaviR,SusiloW.Certificatelesspublickeyencryptionwithoutpairing[C]//Proceedingsofthe8thInternationalConferenceonInformationSecurity,LNCS3650,Berlin:Springer-Verlag,2005:134-148.

[7]ZhengYL.Digitalsigncryptionorhowtoachievecost(signature&encryption)<

[8]BarbosaM,FarshimP.Certificatelesssigncryption[C]//ProceedingsoftheACMSymp.onInformation,ComputerandCommunicationsSecurity(ASIACCS2008).NewYork,ACM,2008:369-372.

[9]BarretoP,DeusajuteAM,CruzE,etal.Towardefficientcertificatelesssigncryptionfrom(andwithout)bilinearpairings[EB/OL].2008.[2014-05-13].http://www.redes.unb.br/ceseg/anais/2008/data/pdf/st03_03_artigo.pdf.

[10] 朱辉,李晖,王育民.不使用双线性对的无证书签密方案[J].计算机研究与发展,2010,47(9):1587-1594.

[11] 刘文浩,许春香.无双线性配对的无证书签密方案[J].软件学报,2011,22(8):1918-1926.

[12]SelviSSD,VivekSS,RanganCP.Cryptanalysisofcertificatelesssigncryptionschemesandanefficientconstructionwithoutpairing[C]//InformationSecurityandCryptology.SpringerBerlinHeidelberg,2011:75-92.

[13]JingX.Provablysecurecertificatelesssigncryptionschemewithoutpairing[C]//ElectronicandMechanicalEngineeringandInformationTechnology(EMEIT),2011InternationalConferenceon.IEEE,2011:4753-4756.

[14] 周才学,王飞鹏.改进的无双线性对的无证书签密方案[J].计算机科学,2013,40(10):139-143.

[15] 夏昂,张龙军.一种新的无双线性对的无证书安全签密方案[J].计算机应用研究,2014,31(2):532-535.

[16] 高键鑫,吴晓平,秦艳琳,等.无双线性对的无证书安全签密方案[J].计算机应用研究,2014, 31(4):1195-1198.

[17] 何德彪.无证书签密机制的安全性分析[J].软件学报,2013,24(3):618-622.

[18] 简岩.两种无证书签密方案的密码学分析[J].制造业自动化,2013,35(2):83-85.

[19]OkamotoT,PointchevalD.Thegap-problems:Anewclassofproblemsforthesecurityofcryptographicschemes[C]//PublicKeyCryptography.SpringerBerlinHeidelberg,2001:104-118.

[20]BonehD.Thedecisiondiffie-hellmanproblem[M]//Algorithmicnumbertheory.SpringerBerlinHeidelberg,1998:48-63.

[21]LiuZ,HuY,ZhangX,etal.Certificatelesssigncryptionschemeinthestandardmodel[J].InformationSciences,2010,180(1):452-464.

[22]PointchevalD,SternJ.Securityargumentsfordigitalsignaturesandblindsignatures[J].Journalofcryptology,2000,13(3):361-396.

APROVABLYSECURECERTIFICATELESSSIGNCRYPTIONSCHEME

ZouChangzhi

(Modern Educational Technology Center,Jingchu University of Technology,Jingmen 448000,Hubei,China)

Thestudyonseveralnewlyproposedcertificatelesssigncryptionschemeswithoutpairingoperationfoundthattherearethecorrectnessflawsorsecurityflaws.Therefore,weproposedanewcertificatelesssigncryptionschemewithoutpairing.Thenewsigncryptionschemechangesthelinearstructureoftwokeysincurrentscheme,andisabletoresistthepublickeyreplacementattacklaunchedbythetypeIadversary;anditbondstheidentitiesofsigncryptionsenderandreceptorwiththemessagetobesignedtheencryptionbyadoptingtwohashfunctionstopreventinternalattacks.TheunforgeabilityandconfidentialityofthenewsigncryptionschemecouldbededucedtoapolynomialtimeadversarytoresolvethediscretelogarithmproblemanddecisionDiffieHellmanproblem,whichwereprovablysecure,intherandomoraclemodel.Comparingwithexistingschemes,thenewschemenotonlyensuresthesecurity,itscomputationaloverheadandimplementationcostsarealsolower,andissuitableforprotectingdataconfidentiality,integrityandauthenticationincomputing,storingandcommunicationresources-constrainedscenarios,likethewirelesssensornetworks.

CertificatelesscryptographySigncryptionBilinearpairingRandomoraclemodel

2014-06-17。邹昌芝，讲师，主研领域：服务器技术，网络安全。

TP3

ADOI:10.3969/j.issn.1000-386x.2016.03.077