张 席,刘 浩
深圳大学计算机与软件学院,深圳518060
Koblitz[1]和 Miller[2]提出的椭圆曲线密钥体系,具有安全性高、密钥量小、灵活性好的特点.2008年,Wajih[3]等人提出在嵌入式系统中实现椭圆曲线的方案.椭圆曲线签密体制基于Diffie-Hellman[4]问题的困难性,其安全性远高于一般离散对数问题.
1984年,Shamir[5]提出基于身份的密码学原理(identity based cryptography).该方案把基于用户身份的信息,如身份证号、姓名、地址、生物特征等作为公钥,不需专门的CA认证机构,减少了证书分发与管理的复杂性[6-7].然而,在以往的密码体系[1-5]中,一旦用户密钥泄露,用户以前及今后发送的信息都不再安全.1997年,Anderson[8]提出前向安全概念.1999年,Bellare和Miner提出首个前向安全的密码方案[9].该方案引入了公钥生存周期概念,将整个生存周期划分为多个时段,公钥在整个生存周期中有效且保持不变,而私钥在不同时段各不相同,每个时段里的私钥保持单向性,即从某个时间段的私钥计算前1个时间段的私钥是不可能的.即使某个时间段私钥泄露,敌手也无法伪造该时段之前和之后的签名,最大限度地降低了私钥泄露带来的风险[10-11].
签密[12](signcryption)是将数字签名与数据加密结合而形成的公钥方案.签密方案允许发送者同时对消息进行签名与数据加密,因此比单独分别执行签名与数据加密更省时,密文长度更小.可广泛应用于资源有限制的设备,如低能量移动设备、智能卡和一些新型传感器.
文献[13-14]提出一种环签密方案及基于身份混合签密方案,虽然改进了算法的安全性,但并未促进算法效率,不适合嵌入式环境应用.本研究利用椭圆曲线,构造基于身份和前向安全的签密算法,具有强安全性及较高效率.目前该方案已用于某海关货物转关系统.
签密方案通常包含4个概率多项式时间算法(probabilistic polynomial time,PPT),即密钥产生、签密、解签密和验证[15].
密钥产生.使用安全参数k产生1个密钥对(sk,pk)(sk,pk)← Keygen(1k).
签 密.输入为安全参数k,消息m,私钥SKu和公钥PKr,输出为密文σ←Signcrypt(1k,m,skU,pkR).其中,m属于定义{0,1}n在明文空间的M;n是k中任意多项式.
解签密.输入为k、σ和skR,输出要么是三维组(m,s,pkU)/reject←Designcrypt(1k,σ,skR),其中m是消息,s是签名,pkU是公钥;要么是reject,表示解签密失败.
验 证.输入k、m、s和公钥pkU,若签名合法,输出true;否则,输出false.数学表达式为true/false←Verify(1k,m,s,pkU).
定义1 完整性.对任意m∈M,(skU,pkU)←Keygen(1k)和(skR,pkR)←Keygen(1k),当skU≠skR时,有(m,s,pkU)← Designcrypt(Signcrypt(m,skU,pkR),skR)和 true← Verify(m,s,pkU).
一般认为安全的签密方案在语义安全上应能抵挡选择密文攻击,在不可伪造性方面应能抵抗选择明文攻击,在匿名的意义上,则不允许密文本身包含标识作者或消息接收者的任何内容[16].
定义2 可信性.若概率多项式时间内敌手不能赢得给定的游戏,则签密方案可在语义安全上抵抗选择密文攻击 (semantically secure against close ciphertext inside attack,SC-IND-CCA)[15].挑战者A的优势定义为
定义3 不可伪造性.一个签密方案是存在不可否认性抵抗选择明文攻击 (existentially unforgeable against chosen message inside attack,SC-EUFCMA)的,若在概率多项式时间,任何伪造者都不能赢得给定的游戏[15].
定义4 密文匿名.若在任何多项式算法内,混淆者都不能赢得给定的游戏[15],则称签密方案是密文匿名且能抵抗选择密文内部攻击 (ciphertext anonymous against chose ciphertext inside attack,SCANON-CCA)的.混淆者D的优势定义为
其中,d,d'与b,b'为游式过程中随机产生的比特位值.
椭圆曲线上的每个点表示(x,y)∈GF(2l).取椭圆曲线上1个n阶有理点G作为基点(满足nG=O)其中,n≤2k,k为系统安全参数.选择3个安全的哈希函数 H0:(0,1)*→ {0,1}l,H1:(0,1)*→{0,1}l和 H2:(0,1)*→ {0,1}l.
算法分为初始化、签密和解签密3个阶段.
2.1.1 初始化
①将每个用户公钥有效期分为T个时段,验证方选择两个大素数p和q,令N=pq,另选择随机整数k(1<k<p)作为私钥,公钥则为Q=kG.
②系统给每个用户分配1个身份标识ID,设签名者身份标识为IDA,选择随机数kA,签名者的初始私钥为SK0=H0(IDA)kAmodN,则签名者的初始公钥为W=SK20TG.
2.1.2 签 密
① 系统进入第i个时段(1<i<T),此时已知i-1时段的私钥SKi-1,通过式 (3)计算当前时段的密钥然后删除 SKi-1.
② 签名者随机选择1个整数t,满足t∈{0,1}n. 令 t'=2T-it,将椭圆曲线上的点 t'× Q=(xpk,ypk)进行编码作为加密所用的密钥.编码函数为然后计算 V=t'G=(x,y),r=x modn.
③设要签名者签名的消息为m,则可在第i时段计算
其中,Z为消息m的加密结果;K是加密密钥;m是要加密的消息;F是对称加密函数.将密文σ=〈Z,i,s,r,V〉发给验证方.
2.1.3 解签密
验证方接收到密文σ后进行以下操作
①验证者用式 (9)计算签名者加密所用密钥
解密签密信息为
则从Z'中可得m、s和r.计算
②若X=0,则拒绝签名;否则计算 r1=x1modn,若r1=r,则接收,反之拒绝.
2.2.1 有效性与正确性验证
由密钥更新算法
签密密钥K=f(t'×Q)=f(t'×k×G),解签密密钥K'=f(kV)=f(k×(t'G))=f(t'×k×G),故K=K'.
2.2.2 算法的安全性
定理1 假定椭圆曲线离散对数 (elliptic curve discrete logarithm problem,ECDLP)困难时,本方案SC-IND-CCA是安全的.
【证】设概率多项式时间内敌手A能以绝对优势赢得定义2中的游戏,则可构造算法B作为敌手A的子程序,用来解决ECDLP难题.
给定B一组ECDLP问题实例(G,V),其中,V=tG.B维持列表L1为H1哈希预言的回答,L2为H2哈希预言的回答,L3为对称密钥预言的回答.
首先对B进行初始化,根据式 (2)和式 (3)产生用户密钥对skU和W.其中,skU私有;W提供给敌手A.
第1个阶段,敌手A进行如下预言查询:
H1预言.对H1(me)的询问,B先检查L1中是否存在H1(me,ge),若存在,则ge作为哈希预言结果;否则在{0,1}l内随机选择g作为对询问的回答,并将H1(me,g)加入表L1中,H2预言与H1预言类似.
对称密钥预言.B在内随机选择t,并计算t×Q=(xpk,ypk).先检查 L3中是否存在(xpk,ypk),若存在则返回其作为对称密钥预言;否则,令K=H1(xpk,ypk),并将(xpk,ypk,K)加入 L3.
签密预言.A选择消息m和公钥WR,当WR≠WU且 WR合法,返回签密值 σ = 〈Z,i,s,r,V〉;否则返回⊥表示拒绝.
解签密预言.A提供密文σ =〈Z,i,s,r,V〉和公钥WR.B先在L3中查询密钥K,利用式 (10)解密得到m.再利用式 (11)~式 (13)验证签密的合法性,若合法,则将m发给敌手;否则,返回⊥拒绝.由于K的数目与椭圆上点的数目相同,即n个,同时要进行H1和H2两次哈希询问,故(K,m)对的数目为n×2l×2l,设对称密钥查询的次数为qK,H1查询的次数为qH1,H2查询的次数为qH2,解签密查询的次数为qus,则多次询问后密文被拒绝的概率小于 qKqH1qH2qus(n × 2l× 2l)-1.
第1个阶段询问完成后,A生成2个相同长度的明文m0,m1∈M和1个合法私钥skS.B任选{0,1},并利用发送者的私钥skS和接收者的公钥pkU计算签密mbˇ,结果σ作为挑战者的密文发送给A.敌手A则继续做类似询问,但不能询问挑战密文的解签密.
设敌手A能猜出挑战者选取的明文,令其优势为ε,用事件E表示至少做了1次对称密钥查询,E表示该事件的补,在真实攻击中有
设 ε =2Pr[b=b']-1=Pr[E],令B 赢得 ECDLP问题的优势为ε',则B成功的优势为ε'≥εqKqH1qH2qus(n ×2l×2l)-1.与假设矛盾.
定理2 设ECDLP困难,本方案SC-EUF-CMA安全.
【证】假定概率多项式时间内伪造者F能够以不可忽略的优势赢得定义3中的游戏,则可构造算法B,利用A作为其子程序来解决ECDLP难题.
H1预言、H2预言及对称密钥预言与定理1类似.因伪造者F拥有密文接收者私钥,所以不需解签密预言.
签密预言.F选择消息m,B选择1个随机数t,通过H1预言和对称密钥预言得到K,再通过H2预言得到消息 m的哈希值,最后算出密文 σ =〈Z,i,s,r,V〉.B将密文σ发送给F.签密过程中B失败的概率至多为 qKqH1qH2(n ×2l×2l)-1.
F输出一个密文σ*,B利用接收者私钥解签密密文σ*,得到m、s和r.利用式 (11) ~式 (13)验证签密的合法性。如合法,则F伪造成功.
令F成功伪造密文优势为ε,则B赢得ECDLP问题概率 ε'≥ε -qKqH1qH2(n ×2l×2l)-1.若 ε 不可忽略,则ε'亦不可忽略,与假设矛盾.
定理3 在假定ECDLP困难前提下,本方案SC-ANON-CCA是安全的.
【证】 假定概率多项式时间内的混淆者D能够以不可忽略优势赢得定义4中游戏,则可构造算法B,利用A作为其子程序来解决ECDLP难题.
与定理1类似,B维持列表L1作为H1哈希预言回答,L2作为H2哈希预言回答,L3作为对称密钥预言回答.
B使用密钥产生算法产生两个不同用户公钥对(skR0,pkR0)、(skR1,pkR1),并将 pkR0和 pkR1给混淆者D.则
令D成功混淆密文的优势为ε,则ε=4Pr[D赢]- 1=3Pr[E]
若ε不可忽略,则ε'也不可忽略,与假设矛盾.
2.2.3 效率分析
本方案签密包括2次hash运算、1次幂模运算、1次异或运算、3次椭圆曲线上的点乘 (即标量乘法)运算和1次对称加密运算.每次解签密需要1次椭圆曲线上的点乘运算、1次异或运算、1次hash运算和1次对称解密运算,无复杂运算,执行效率高.
为验证本方案的可行性,我们分别在4种设备上运算该方案.详见表1、表2和表3.其中表1列出各设备具体配置,表2列举不同签密文本大小应用该方案进行签密和解密时所需时间.由表2可知,工控机上执行本算法,签密1 kbit大小的文本总时间远小于0.1 s,完全满足实际应用,证明方案可行,本方案目前应用在某海关货物转关系统.
表1 测试设备Table 1 Testing devices
表2 执行时间Table 2 Executing time
表3 签密过程中各步骤的执行时间Table 3 Executing time for each step during the signcryption
表3列举了签密过程在工控机上运行1 kbit文本时,各关键步骤的耗时.由表3可见,签密过程中大部分时间是椭圆曲线点乘运算.下一步我们将重点研究如何改进Koblitz曲线点乘算法,以提高算法效率.
[1]Koblitz N.椭圆曲线密码系统[J].计算机科学,1987,48(177):203-209.(英文版)
[2]Miller V.椭圆曲线在密码系统中的应用[C]//密码学会议录-Crypto'85.柏林:施普林格出版社,1986:417-426.(英文版)
[3]Wajih E H Y,Mohsen M,Rached T.一种安全的嵌入式设备椭圆曲线签名方案[C]//信号、电路与系统国际会议论文集.莫纳斯提 (突尼斯):IEEE出版社,2008(7/8/9):1-6.(英文版)
[4]张 席,杭欢花.一种基于强DH加密的高效转换方案[J].武汉大学学报自然科学版,2010,15(5):415-421.(英文版)
[5]Shamir A.基于身份的加密系统与签名方案[C]//密码学会议录-Crypto'84.柏林:施普林格出版社,1984:47-53.(英文版)
[6]张 席,陈泯融,刘 浩,等.无需随机预言模型的基于身份门限解密方案[J].深圳大学学报理工版,2010,37(3):340-346.(英文版)
[7]张 席,陈泯融,杨 玲,等.基于身份多接受者签名方案的安全性分析[J].深圳大学学报理工版,2010,37(4):408-412.(英文版)
[8]Anderson R.公开密钥体系的两个说明[C]//第4届计算机与通信安全会议论文集.苏伊士 (埃及):美国计算机协会,1997:3-6.(英文版)
[9]Bellare M,Miner S K.一种前向安全的数字签名方案[C]//密码学会议录-Crypto'99.柏林:施普林格出版社,1999:431-448.(英文版)
[10]张 席,杭欢花.一种改进的前向安全盲签名方案[J].武汉大学学报理学版,2011,57(5):434-438.
[11]WANG Shu-hong,BAO Fang,DENG R H.具有可证安全性前向安全盲签名方案加密分析[C]//第7届信息与通信安全国际会议论文集.柏林:施普林格出版社,2005:53-60.(英文版)
[12]ZHENG Yu-liang.数字签密如何达到预定的效率:使签密的代价≪签名+加密的代价[C]//密码学会议录-Crypto'97.柏林:施普林格出版社,1997:165-179.(英文版)
[13]LI Fa-gen,Shirase M,Takagi T.基于身份混合加密[C]//ARES(有效性,可靠性,安全性)国际会议论文集.[s.l.]:[s.n.],2009:534-539.(英文版)
[14]LI Chung-ki,YANG Guo-min,WONG D S.等.一种具有密钥私有性的签密方案和它在环签密中的扩展[J].计算机安全期刊,2010,18(3):451-473.(英文版)
[15]YANG Guo-min,WONG D S,DENG Xiao-tie.一种密钥私有签密方案的分析与改进[J].信息安全,2005,3650:218-232.(英文版)
[16]Libert B,Quisquater J-J.差分Diffe-Hellman群中具有密钥私有的签密方案[C]//PKC'04公钥密码学进展会议论文集.柏林:施普林格出版社,2004,2947:187-200.(英文版)
Abstract:1000-2618(2011)05-0421-EA
† This work was supported by the National Natural Science Foundation of China(60903178).
[1]Koblitz N.Elliptic curve cryptosystems[J].Mathematics of Computation,1987,48(177):203-209.
[2]Miller V S.Uses of elliptic curves in cryptography[C]//Proceedings of CRYPTO'85 on Advances in Cryptology.Berlin:Springer-Verlag,1986:417-426.
[3]Wajih E H Y,Mohsen M,Rached T.A secure elliptic curve digitalsignature schemeforembedded devices[C]//International Conference on Signals,Circuits and Systems.Monastir(Tunisia):IEEE Press,2008(7/8/9):1-6
[4]ZHANG Xi,HANG Huan-hua.An efficient conversion scheme for enhancing security of diffie-Hellman-based encryption[J].Wuhan University Journal of Natural Sciences,2010,15(5):415-421.
[5]Shamir A.Identity-based cryptosistems and signature schemes[C]//Proceedings of CRYPTO'84 on Advances in Cryptology.Berlin:Springer-Verlag,1984:47-53
[6]ZHANG Xi,CHEN Min-rong,LIU Hao.Practical identity-based threshold decryption scheme without random oracle[J].Journal of Shenzhen University Science and Engineering,2010,27(3):340-346.
[7]ZHANG Xi,CHEN Min-rong,YANG Ling.Cryptanalysis of an identity-based multi-recipient signcryption scheme[J].Journal of Shenzhen University Science and Engineering,2010,27(4):408-412.
[8]Anderson R.Two remarks on public key on cryptology[C]//Proceedings of the 4th ACM conference on Computer and communications.Zurich(Egypt):Association for Computing Machinery,1997:3-6
[9]Bellare M,Miner S K.A forward-secure digital signature scheme[C]//Proceedings of CRYPTO'99 on Advance in Cryptology.Berlin:Springer-Verlag,1999:431-448.
[10]ZHANG Xi,HANG Huan-hua.A new forward-secure blind signature scheme[J].Journal of Wuhan University:Natural Science Edition,2011,57(5):434-438.(in Chinese)
[11]WANG Shu-hong,BAO Fang,DENG R H.Cryptanalysis of a forward secure blind signature scheme with provable security[C]//7th International Conference on Information and Communications Security.Berlin:Spring-Verlag,2005:53-60.
[12]ZHENG Yu-liang.Digital signcryption or how to achieve cost(signature&encryption)≪cost(signature)+cost(encryption)[C]//Proceedings of CRYPTO'99 on Advances in Cryptology. Berlin:Springer-Verlag,1997:165-179.
[13]LI Fa-gen,Shirase M,Takagi T.Identity-based Hybrid signcryption[C]//International Conference on Reliability and Security.[s.l.]:[s.n.],2009:534-539.
[14]LI Chung-ki,YANG Guo-min,WONG D S,et al.An efficient signcryption scheme with key privacy and its extension to ring signcryption[J].Journal of Computer Security,2010,18(3):451-473.
[15]YANG Guo-min,WONG D S,DENG Xiao-tie.Analysis and improvement of a signcryption scheme with key privacy[J].Information Security,2005,3650:218-232.
[16]Libert B,Quisquater J-J.Effcient signcryption with key privacy from gap Diffe-Hellman groups[C]//In Public Key Cryptography.Berlin:Springer-Verlag,2004,2947:187-200.