汤鹏志 刘启文 左黎明 陈仁群

基于自证明公钥认证的安全高效在线/离线签密方案

汤鹏志 刘启文*左黎明 陈仁群

(华东交通大学理学院 江西 南昌 330013)

基于自证明公钥密码体制，提出一种适用于物联网通信的高效在线/离线签密方案，以解决物联网中因信息在不安全信道上传输而被窃取或篡改的问题。运用随机预言机模型，在适应性选择身份和消息攻击下，证明了新方案的密文是语义安全的，并且签密是存在性不可伪造的。由于新方案无双线性对运算，比现有的在线/离线签密方案更高效。同时，新方案具有可公开验证性以及无密钥托管等优点。

在线/离线 自证明 签密 随机预言机

0 引 言

1990年，Girault首次提出了自证明公钥的概念[1]，以解决基于证书的公钥密码体制中证书管理的问题以及基于身份的公钥密码体制中密钥托管的问题。Girault在文献[1]中提出了第一个基于RSA的自证明公钥认证方案。不过，Saeednia[2]在2003年指出 Girault 所提出的自证明公钥中，由于可信中心可以选择恶意的大整数，使其能够通过求解离散对数得到用户私钥，因此同样存在密钥托管的问题。1997年，Etersen等提出了基于弱Schnorr盲签名的自证明公钥方案[3]，利用弱Schnorr盲签名协议[4]的盲性和存在性不可伪造等特点解决用户密钥托管和公钥认证的问题。相比于无证书公钥密码体制[5]，自证明公钥密码体制具有密钥短，且无公钥替换攻击的漏洞[6]。

1997年，zheng提出了数字签密的概念[7]。数字签密是指能够在一个逻辑步骤内完成数据加密和签名的密码学技术。相比于传统的先签名后加密技术，签密具有计算量小、传输密文更短和效率更高的特点。不过，Zheng的方案是基于证书的且签密不能公开验证。

在线/离线的概念最早由Even等[8]在其数字签名方案中提出，其主要思想是将签名分成离线阶段和在线阶段，一些复杂的、且与待签名消息无关的计算在离线阶段完成；在线阶段只需一些简单的计算即可。An等在文献[9]中对签密安全性做了系统性的分析，将在线/离线的思想应用到签密方案中，提出了在线/离线签密的概念。

在线/离线签密是一种非常实用的技术。特别是在移动互联网中，利用在线/离线签密可以提供高效的解决方案。随着智能终端的普及和第三代、第四代移动通信网络的推广，为物联网产业发展提供了一个强大的基础平台，人们可以利用智能手机很方便地远程控制家中的智能设备。物联网极大地便利人们生活的同时，也增加了个人隐私和数据泄露的风险。因为用户数据在公开信道上传输，存在数据被非授权用户访问或修改的风险。数字签密所提供的机密性和数据完整性机制，可以很好保护数据的机密性和完整性。同时，利用在线/离线的思想将复杂的计算提前完成，在线阶段只需做少量的计算就可得到一个的签密，以解决智能终端的计算能力弱和续航差等问题。

自在线/离线签密的概念提出以来，迅速成为密码学领域的一个研究热点。2005年， Zhang等[10]提出了第一个具体的在线/离线签密方案。2008年，Sun等[11]首次提出了基于身份的在线/离线签密方案。Liu等[12]指出，在文献[10,11]中，离线阶段需要签密接收者的公钥和身份，因此，并不实用。Liu在文献[12]提出了一个改进方案。Selvi等[13]指出Liu等[12]方案是不安全的，并提出了改进方案。2012年，Li等[14]提出了一个在离线阶段更高效的基于身份的在线/离线签密方案。2013年，Luo等[15]提出了一个适用于物联网的高效无证书在线/离线签密方案。Shi等[16]指出Luo等[15]方案存在严重的安全漏洞，攻击者能够仅利用一个签密就可以计算出签密发送者的签密密钥。

基于弱Schnorr盲签名的自证明公钥方案[3]，构造了一个高效安全的在线/离线签密方案。在随机预言机模型下讨论了新方案的机密性和不可伪造性。效率上，与现有的在线离线签弥方案相比，新方案在离线签密阶段和签密验证阶段都具有明显的优势。

1 预备知识

设p是一个大素数。群G1和G2是阶为p的加法循环群和乘法循环群，P是G1的一个生成元。

判定Diff-Hellman问题(DDHP)

2 基于自证明在线/离线签密方案

在线签密 A为签密发送者，公私钥为(sA,PKA)；B为签密接收者，公私钥为(sB,PKB)；m为待签密消息。从离线签密列表中取出一个离线签密对(x,R)，解密，并将(x,R)从离线签密列表中删除。计算k=H2(sA(PKB+H1(IDB,PKB)Ppub),R)，y=k⊕m，v=xH3(m,PKA,PKB,R)+sA。消息m的完整签密为σ=(y,R,v)。

解签密 当签密接收者B收到签密σ=(y,R,v)时，计算加密密钥k=H2(sB(PKA+H1(IDA,PKA)Ppub),R)，解密m=k⊕y，验证签名：vP=H3(m,PKA,PKB,R)·R+PKA+H1(IDA,PKA)·P，若等式成立，则接收消息m，否则拒绝。

3 安全性分析

定理1 解密算法和签名验证等式是正确的。

证明：因为：

sA(PKB+H1(IDB,PKB)Ppub) =sAsBP

=sB(PKA+H1(IDA,PKA)Ppub

那么：

k =H2(sB(PKA+H1(IDA,PKA)Ppub),R)

=H2(sA(PKB+H1(IDB,PKB)Ppub),R)

因此，解密算法是正确的。

由于：

vP =[xH3(m,PKA,PKB,R)+sA]P

=xH3(m,PKA,PKB,R)P+sAP

=H3(m,PKA,PKB,R)R+PKA+H1(IDA,PKA)Ppub

因此，签名验证等式是正确的。

定理2 用户密钥仅授权用户才可访问，并且，是存在性不可伪造。

证明：用户密钥生成协议是一个schonorr弱盲签名方案[4]。用户密钥是由可信中心对用户身份和公钥的盲签名，由schonorr弱盲签名的盲性和存在性不可伪造的性质[17]可知，用户密钥是不可追踪的且是存在性不可伪造的。因此，只有授权用户才可访问其密钥。

定理3 在随机预言机模型和椭圆曲线上的DDH困难问题假设下，对适应性选择身份和消息攻击，密文是IND-CCA2安全的。

证明：设(aP,bP,cP)是群G1中的一个任意的DDH问题实例，即aP、bP、cP已知，a、b、c未知，判断abP=cP是否成立。

假设存在攻击者Att能够在多项式时间t内以优势ε区分密文。现在，构造算法B求解以上DDH问题。算法B模拟挑战者与攻击者Att交互，完成以下步骤：

公钥询问 Att最多能做qP次公钥询问。B维护列表LPK，随机选取1≤K,J≤qP，当B收到Att关于IDi(1≤i≤qP)的公钥询问(假设没有做过IDi的公钥询问)：

密钥提取询问 Att最多能做qE次密钥提取询问，当B收到关于身份IDi的密钥提取询问，(假设已经做过关于身份IDi的公钥询问和H1询问，否则先执行公钥询问和H1询问)：

b) 若i=K或i=J，算法B终止。

签密询问 Att最多能做qS次签密询问；当B收到关于(IDi,IDj,m)的签密询问(其中，IDi是签密发送者，IDj是签密接收者，m是待签密消息)：

a) 若i≠K,J，通过做关于身份IDi的公钥询问、密钥提取询问可得到其公私钥对(si,PKi)，通过做关于身份IDj的公钥询问，可以得到IDj的公钥PKj；那么，通过运行正常的签密算法即可得到关于(IDi,IDj,m)的签密σ，将σ返回给Att。

解签密询问 Att最多能做qD次解签密询问；当B收到关于签密(IDi,IDj,σ=(y,R,v))的解签密询问：

a) 若i≠K,J，通过做关于身份IDi的公钥询问、密钥提取询问可得到其公私钥对(si,PKi)，通过做关于身份IDj的公钥询问，可以得到IDj的公钥PKj；计算PL=siPKj，做关于(PL,R)的H2询问，得到k=H2(PL,R)，解密m=y⊕k，将m返回给Att。

b) 若i=K或i=J，但j≠K,J，通过公钥询问，可以得到IDi和IDj的公钥PKi和PKj，因为j≠K,J，可以通过密钥提取询问，得到IDj的私钥sj。那么通过正常的解签密算法即可得到(IDi,IDj,σ=(y,R,v))的明文m，将m返回给Att。

c) 若i=K，j=J，查询签密列表Lsin，如果Lsin中存在项(IDi,IDj,σ=(y,R,v),m)，则将m返回给Att；否则拒绝解签密。

第二阶段询问 Att可以再做多项式次公钥询问、哈希询问、密钥提取询问、签密询问和解签密询问。但是不能做关于IDJ和IDK的密钥提取询问，且不能做关于挑战σ=(y,R,v)的解签密询问。

猜测 由假设可知Att能够以ε的优势猜得p′=p。那么，算法B能够判断abP=cP，即解决了DDH问题。

下面分析算法B成功优势和所需时间：

t′=t+qPtP+qH1tH1+qH2tH2+qH3tH3+qEtE+qStS+qDtD

其中，tP是一次公钥询问所需的时间，tH1、tH2、tH3分别是一次哈希询问所需的时间，tE是一次密钥提取询问所需的时间，tS和tD分别是一次签密和一次解签密所需的时间；容易知道，tPtH1、tH2、tH3、tE、tS和tD都是多项式有界的。而t、qP、qH1、qH2、qH3、qE、qS以及qD都是多项式有界的；因此，t′是多项式有界。

所以，算法B能够在多项式有界的时间t′内，以不可忽略的优势Adv解决DDH问题；这与DDH问题的困难性相矛盾。故假设不成立，在适应性选择身份和消息攻击，密文是IND-CCA2安全的。

定理4 在随机预言机模型和椭圆曲线上的离散对数困难问题的假设下，对适应性选择身份和消息攻击，签密是存在性不可伪造的(CCA2)。

证明：反证法。假设存在攻击者Att能够在多项式有界的时间t，以不可忽略的概率ε伪造签密。

对于椭圆曲线上群G中任意CDH问题实例Q=aP，Q已知，a未知，现构造算法B计算a。算法B模拟挑战者与攻击者Att交互，完成以下步骤：

系统设置 同定理3。

公钥询问 Att最多能做qP次公钥询问。B维护列表LPK，随机选取1≤K≤qP，用a模拟身份IDK的密钥；当B收到Att关于IDi(1≤i≤qP)的公钥询问(假设没有做过IDi的公钥询问)：

H2询问 Att最多能做qH2次H2哈希询问。B通过维护列表L2来模拟随机预言机H2，列表L2初始状态为空。具体过程同定理3。

H3询问 Att最多能做qH3次H3哈希询问。B通过维护列表L3来模拟随机预言机H3，列表L3初始状态为空。具体过程同定理3。

密钥提取询问 Att最多能做qE次密钥提取询问，当B收到关于身份IDi的密钥提取询问，(假设已经做过关于身份IDi的公钥询问和H1询问，否则先执行公钥询问和H1询问)：

b) 若i=K，算法B终止。

签密询问 Att最多能做qS次签密询问；当B收到关于(IDi,IDj,m)的签密询问(其中，IDi是签密发送者，IDj是签密接收者，m是待签密消息)：

a) 若i≠K，通过做关于身份IDi的公钥询问、密钥提取询问可得到其公私钥对(si,PKi)，通过做关于身份IDj的公钥询问，可以得到IDj的公钥PKj；那么，通过运行正常的签密算法即可得到关于(IDi,IDj,m)的签密σ，将σ返回给Att。

解签密询问 Att最多能做qD次解签密询问；当B收到关于签密(IDi,IDj,σ=(y,R,v))的解签密询问：

a) 若i≠K，通过做关于身份IDi的公钥询问、密钥提取询问可得到其公私钥对(si,PKi)，通过做关于身份IDj的公钥询问，可以得到IDj的公钥PKj；计算PL=siPKj，做关于(PL,R)的H2询问，得到k=H2(PL,R)，解密m=y⊕k，将m返回给Att。

b) 若i=K，那么j≠K，通过公钥询问，可以得到IDi和IDj的公钥PKi和PKj，因为j≠K，可以通过密钥提取询问，得到IDj的私钥sj。那么通过正常的解签密算法即可得到(IDi,IDj,σ)的明文m，将m返回给Att。

vP =h3·R+PKA+H1(IDA,PKA)·P

=h3·R+aP

(1)

(2)

下面分析算法B成功的概率和所需时间。

t′= t+qPtP+qH1tH1+qH2tH2+qH3tH3+qEtE+qStS+qDtD

其中，tP是一次公钥询问所需的时间，tH1、tH2、tH3分别是一次哈希询问所需的时间，tE是一次密钥提取询问所需的时间，tS和tD分别是一次签密和一次解签密所需的时间；容易知道，tPtH1、tH2、tH3、tE、tS和tD都是多项式有界的。而t、qP、qH1、qH2、qH3、qE、qS以及qD都是多项式有界的；因此，t′是多项式有界。

因此，算法B能够在多项式有界的时间t′内，以不可忽略的概率ε′解决离散对数问题Q=aP。这与离散对数问题困难的假设相矛盾，所以不存在攻击者Att能够在多项式有界的时间t，以不可忽略的概率ε伪造签密。故定理得证。

4 性能分析

表1 性能比较

5 结 语

在线/离线签密方案在移动互联网中有着广阔的应用前景。目前，智能终端应用主要是基于C/S架构的，数据在公开信道上传输，在线/离线签密方案可以确保数据完整性和机密性，同时，也可以用于客户端远认证。对此，提出了一种基于自证明的安全高效的在线/离线签密方案，在随机预言机模型下，证明了方案的安全性。新方案在离线签密阶段和签密验证阶段有着明显的优势。但是，在线签密阶段的计算复杂度并没有太大的优势，因此，下阶段的工作是在此基础上，进一步降低在线签密阶段的计算复杂度。

[1] Girault M.Self-certified public keys[C]//Advances in Cryptology-EUROCRYPT’91,LNCS 547,Berlin:Springer-Verlag,1991:491-497.

[2] Shahrokh Saeednia.A note on Girault’s self-certified model[J].Information processing letters,2003,86(6):323-327.

[3] Holger Petersen,Patrick Horster.Self-certified keys-Concepts and Applications[C]//Proc.Communications and Multimedia Security’97,Athens:Chapman Hall,1997:102-116.

[4] Horster P,Michels M,Petersen H.Hidden signature schemes based on the discrete logarithm problem and related concepts[C]//Proc.Communications and Multimedia Security,Chapman & Hall,1995:149-156.

[5] Al-Riyami S,Paterson K.Certicateless public key cryptography[C]//Laih CS,ed.Proc.of the Int’l Association for Cryptdology Research 2003.LNCS 2894,Berlin: Springer-Verlag,2003:452-473.

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

[7] Zheng Y.Digital signcryption or how to achieve cost (signature & encryption) << cost(signature) + cost(encryption)[C]//Advances in Cryptology-CRYPTO’97,LNCS 1294,Berlin:Springer-Verlag,1997:165-179.

[8] Even S,Goldreich O,Micali S.On-line/offline digital signatures[C]//Proc.CRYPTO 89.LNCS 2442,1989:263-277.

[9] An J,Dodis Y,Rabin T.On the Security of Joint Signature and Encryption[C]//Proc.EUROCRYPT 2002,LNCS 2332,2002:83-107.

[10] Zhang F,Mu Y,Susilo W.Reducing security overhead for mobile network[C]//Proceedings of the Advanced information networking and applications,Taipei,Taiwan,2005:398-403.

[11] Sun D,Huang X,Mu Y,et al.Identity-based on-line/off-line signcryption[C]//Proceedings of the Network and parallel computing,Shanghai,China,2008:34-41.

[12] Liu J K,Baek J,Zhou J Y.Online/offline identity-based signcryption re-visited[C]//Proceedings of the Information Security ane Cryptology,LNCS, vol.6584,Springer-Verlag: Berlin,2011:36-51.

[13] Selvi S S D,Vivek S S,Rangn C P.Identity based online/offline signcryption scheme[EB/OL].Crytology ePrint Archieve,2010.Available at:http://eprint.iacr.org/2010/376.pdf.

[14] Li F G,Khan M K,Alghathbar K,et al.Identity-based online/offline signcryption for low power devices[J].Journal of Network and Computer Applications,2012,35(1):340-347.

[15] Luo M,Tu M,Xu J.A security communication model based on certificateless online/offline signcryption for Internet of Things[J].Security and Communication Networks,2013,10.1002/Sec.836.

[16] Shi Wenbo,Neeraj Kumar,Gong Peng,et al.On the security of a certificateless online/offline signcryption for internet of things[J].Peer-to-Peer Netw.New York:Springer Science and Bussiness Media,2014,doi:10.1007/s12083-014-0249-3.

[17] Pointcheval D,Stern J.Security Proofs for Signatures[C]//LNCS 1070,Advances in Cryptology:Proc.Eurocrypt’96,Springer,1996:387-398.

SECURE AND EFFICIENT ONLINE/OFFLINE SIGNCRYPTION SCHEME BASED ON SELF-CERTIFIED PUBLIC KEY AUTHENTICATION

Tang Pengzhi Liu Qiwen*Zuo Liming Chen Renqun

(SchoolofBasicScience,EastChinaJiaotongUniversity,Nanchang330013,Jiangxi,China)

To solve the problem that in Internet of Things the information transmitted over an insecure channel may be eavesdropped or tampered, we proposed a new efficient online/offline signcryption scheme based on self-certified public key authentication suitable for Internet of Things. It was proved that the cipher of new scheme was indistinguishable and the signcryption was existentially unforgeable against the attacks of adaptive chosen message and identity in random oracle model. Because of without bilinear pairing operation, the new scheme was more efficient than those existing online/offline signcryption schemes. At the same time, it has the properties that can be verified in public and without key escrow.

Online/offline Self-certified Signcryption Random oracle model

2014-10-12。国家自然科学基金项目(61240025，61472138)；江西省高校科技落地计划项目(KJLD12067)；华东交通大学校立科研基金项目(11JC04)。汤鹏志，教授，主研领域：信息安全。刘启文，硕士生。左黎明，副教授。陈仁群，硕士生。

TP301

A

10.3969/j.issn.1000-386x.2016.04.066