安全签密方案在嵌入式设备中的应用

张 席，刘 浩

深圳大学计算机与软件学院，深圳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］提出一种环签密方案及基于身份混合签密方案，虽然改进了算法的安全性，但并未促进算法效率，不适合嵌入式环境应用.本研究利用椭圆曲线，构造基于身份和前向安全的签密算法，具有强安全性及较高效率.目前该方案已用于某海关货物转关系统.

1 签密安全模型

1.1 签密方案的形式化描述

签密方案通常包含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.2 签密安全模型

定义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'为游式过程中随机产生的比特位值.

2 算法描述

椭圆曲线上的每个点表示(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 算法步骤

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 算法分析

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次对称解密运算，无复杂运算，执行效率高.

3 应用分析

为验证本方案的可行性，我们分别在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.