适于ad hoc网络安全通信的新签密算法

张串绒，张玉清，李发根，肖鸿

（1. 中国科学院 研究生院，北京100049；2. 空军工程大学 电讯工程学院，陕西 西安 710077；3. 电子科技大学 计算机科学与工程学院，四川 成都 611731）

1 引言

Ad hoc 网络作为一种新型无线网络，能够在没有事先建立基础设施的环境下，由一组带有无线通信装置的移动节点组成多跳步、临时性的自治通信系统。它以其组网迅速、适应性强、成本低廉等优点，可广泛应用于工商、医疗、家庭、办公环境和军事等各个领域，具有广阔的应用前景。但ad hoc网络无中心、分布式管理、资源受限等特点，使其在信息的认证性、机密性、完整性、抗抵赖等安全性及其实现方面产生严重障碍。同时传统网络基于较充足网络资源、固定连接、稳定拓扑、专门路由、命名和目录等多种服务基础上的相关安全措施，不再适于ad hoc 网络，这就要求为ad hoc 网络通信设计专门的安全技术和算法。

在ad hoc 网络的安全通信中，大量信息的存储和传输是同时需要机密性和可认证性保护的。密码学传统上是以“先签名再加密”的方法来同时实现机密性和认证性这2种安全服务的，但这种简单组合的方法，其计算和通信代价是加密和签名的总和，效率较低，不适合ad hoc 网络受限的环境。1997年，文献[1]提出了一种新的密码技术——签密，它能在一个逻辑步内同时实现机密性和可认证性2项安全需求，效率远远高于“先签名再加密”方法，已被公认为是同时实现机密性和可认证性的理想方法。目前，已有许多文献研究将签密技术用于ad hoc 网络的密钥管理、安全路由等安全协议的设计，其中文献[2～6]研究了基于身份的签密算法在ad hoc网络安全协议中的应用。已有研究成果表明，基于身份签密技术对提高 ad hoc 网络通信的安全性及其实现效率具有重要作用。为了进一步提高ad hoc网络通信的安全性和效率，本文研究新的基于身份的签密算法，给出了一个可证明安全的短的基于身份的签密算法，简称S-IDSC，与已有签密算法相比，其计算和传输代价小，能更好地满足ad hoc网络无线通信带宽受限、电池供电、收发设备内存小的特殊环境，高效实现 ad hoc 网络密钥管理、安全路由等通信过程中的安全需求。

2 相关基础

2.1 基于身份签密算法的组成

Malone-Lee在文献[7]中首次提出了基于身份签密思想，给出如下算法结构。

1) 系统建立(setup)：给定系统安全参数k，由密钥生成中心PKG生成系统参数；

2) 密钥提取(extract)：对消息发送者和接收者给出的身份信息 I DA和 I DB，由PKG生成与之相应的公私钥对(dA,QA)和(dB, QB)，并通过秘密信道传给相应用户；

3) 签密(signcrypt)：输入 dA、 I DB和消息m，生成密文σ；

4) 解签密(unsignc)：输入 dB、 IDA和σ，输出m或⊥，输出⊥表明σ为无效签密密文。

目前提出的基于身份签密算法的还有文献[8～11]等。这些基于身份签密算法多是利用椭圆曲线上双线性对来实现的，如 Weil对或改进的 Tate对。所谓双线性对是一种变换，定义如下。

设 G1和 G2是2个q阶的循环群，如果变换e满足如下。

基于椭圆曲线上双线性对的签密算法，具有短的密钥长度和低的通信带宽要求。

2.2 基于身份签密算法的安全性定义

文献[8]定义了一种基于身份签密算法的安全概念，具体如下。

定义 1 保密性：如果没有任何多项式有界的敌手以一个不可忽略的优势赢得以下游戏，则称一个基于身份的签密算法在适应性选择密文攻击下是不可区分的（IND-IBSC-CCA2）。

1) 初始化阶段，挑战者Γ输入安全参数k，运行系统建立算法，并将系统参数 params发送给敌手Ω，保密系统私钥s。

2) 询问阶段（第一阶段询问），执行以下多项式有界次适应性询问。

密钥提取询问：敌手Ω选择一个身份 I DU，挑战者Γ计算 dU=Extract(I DU)并将结果发给Ω。

签密询问：Ω选择2个身份 I Di和 I Dj、一个明文m。Γ计算并将结果σ发送给Ω。

解签密询问：Ω选择 2个身份 I Di和 I Dj、一个密文σ。Γ首先计算私钥然后计算 U nsignc(σ,dj,I Di)，最后发送结果明文m或符号⊥给敌手Ω。

Ω能根据Γ对他签密提交询问的回答，调整他的询问。

3) Ω输出2个相同长度的明文 m0、m1和他希望挑战的2个身份 I DA和 I DB。I DA和 I DB不能是在2) 中已经执行过密钥提取询问的身份。

5) 第二阶段询问：像 2)中那样，Ω再次执行多项式有界次询问。但是他不能对 I DA和 I DB执行私钥提取询问，也不能对密文σ执行解签密询问。

最后，Ω输出一个值v′作为对v的猜测。如果v′=v，Ω赢得游戏。

定义 2 不可伪造性：如果不存在任何多项式有界的敌手以一个不可忽略的优势赢得以下游戏，则称一个基于身份的签密方案在适应性选择消息攻击下是存在性不可伪造的(EUF-IBSC-CMA)。

1) 初始化阶段：挑战者Γ输入安全参数k，运行系统建立算法，并将系统参数params发送给敌手Ω，并保密系统私钥s。

2) 询问阶段：Ω类似保密性定义中那样执行多项式有界次询问。

3) 最后，Ω输出一个新的三元组(σ*,I D ,I D ))，且这个三元组不是询问阶段签密预

A B言机的输出， I DA也不是询问阶段的密钥提取预言机的输出。如果 U nsignc( σ*,dB, I DA)的结果不是符号⊥，则A赢得游戏。

3 新的基于身份签密算法S-IDSC

系统参数：给定安全参数k，PKG首先选取椭圆曲线上的2个q阶的循环群 (G1,+)和 (G2,⋅)，G1的生成元为P，由 G1和 G2上Weil对或Tate对的变形得到双线性变换记为PKG随机选取自己的私钥 δ ∈ Zq*，计算相应公钥PKG再选取安全的对称密码算法(E,D)和3个散列函数其中l1是身份ID的比特长度，l2是 G1中元素的比特长度，n是明文比特长度。这样，该算法的系统参数是

密钥提取：给出用户的身份 I DU，PKG计算相应的公钥和私钥 dU=δQU；本算法中发送者Alice和接收者Bob的身份公私钥对分别记为(dA, QA)和(dB, QB)。

假定Alice要将消息m签密发送给Bob，他们执行以下签密和解签密过程。

Alice签密：

Alice发送密文σ=(t,r)给Bob，Bob收到密文σ后执行下面解签密。

Bob解签密：

算法的正确性证明：

关于算法要说明的是： dA和 dB本来是 G1上的点，在计算签密中和解签密中时需将它们转换成 Zq*中的数。转换的方法很多，比如，如果 G1是定义在有限域 Zq*上的椭圆曲线上的群，可以用 G1上点的横坐标代表椭圆曲线上的点。关于这点文献[12]有类似说明，可参考。

4 S-IDSC安全性及其效率分析

4.1 安全性分析和证明

假设S-IDSC中所使用的散列函数H1、H2、H3是随机预言机。用符号 qi(i = 1 ,2,3)表示攻击者询问Hi的次数， qs和 qd分别表示攻击者询问签密机和解签密机的次数。

4.1.1 机密性

S-IDSC的机密性是基于双线性对 Diffie-Hellman问题（BDH）的。所谓BDH问题是指：给定(P,a P,b P,c P ) ,计 算其中为未知，P是G1的生成元。

结论 1 对S-IDSC，如果存在一个 IND-IBSCCCA2攻击者Ω能够在t时间内，以ε的优势赢得定义 1中的游戏，那么，就存在一个算法 C，能够在时间内，以的优势解决BDH问题，其中et表示计算一次双线性对运算所需要的时间。

证明C接收了一个随机的 BDH问题实例他的目标是计算出e(P,P )abc，其中算法 C将攻击者Ω作为它的子程序利用。结论1的证明分模拟阶段和分析阶段2个阶段进行。

1) 模拟阶段

C需要维护 L1,L2, L3,Ls, Ld5张列表，用它们来记录C对Ω询问 H1,H2, H3,S igncrypt,Unsignc的回答，这些列表初始时是空的， L1,L2, L3分别用于跟踪Ω对预言机 H1,H2, H3的询问，Ls和 Ld分别用于模拟签密预言机和模拟解签密预言机。

H1询问：C首先从 {1 ,2,…,q1}中选取2个随机数 i,j。Ω对 H1进行多项式有限次询问，对Ω的第i次询问，回答 H1(I Di) = a P，对Ω的第j次询问，回答 H1(I Dj)= b P。由于 a P,bP是 BDH问题实例中的值，因此， I Di和 I Dj的私钥 di、 dj就分别是acP、bcP（C并不能计算出这些值），而BDH问题的值 e (P,P )abc可由算出。对第e≠i、j次的询问，C从Z*q中随机取一值be，计算，并将(I De, be)添加到 L1中，给出回答值 Qe。

H2询问：C首先检查列表 L2中是否存在(ωe, k2,e)。如果列表 L2含有该条目，C把条目中给出的回答 k2,e输出给Ω；否则，C从 Z*q中随机取一值 k2，将 (ωe,k2)添加到 L2中并输出 k2。

H3询问：C首先检查列表 L3中是否存在。如果列表 L3含有该条目，C把条目中给出的回答 re输出给Ω；否则，C从 Zq*中随机取一个值r，将添加到 L3中并输出值r。

密钥提取询问：当Ω询问 E xtract(I DA)时，如果或j，那么C将失败并终止模拟；否则，在列表 L1中查找对应的条目，C计算 I DA的私钥并给Ω。

签密询问：任何时候Ω可以选择消息m和 2个身份 I DA和 I DB，对进行签密询问（此前已经对 I DA和 I DB进行过密钥提取查询）。①如果，C可通过密钥提取算法Extract(I DA)计算出 I DA的私钥 dA，然后简单地运行签密运算 S igncrypt(m,dA, QB)即可。②如果或但，C按如下过程模拟 S igncrypt(m,dA, QB)：首先在 L1中找到(I DB, dB)，然后从 Z*q中随机选取x′和s′，计算可以从上述 H2询问获得)，计算 r ′ ← H3(k1′,m)，并检查 H3的条目中是否已经有三元组 ( k1′,m,r ′)，且如果是这样，C重复以上过程，另选x′和s′，直到找到的三元组的前两元在 H3的条目中没出现过，并将此条目添加到 L3，再计算相应的最后将签密密文给Ω，这个签密密文在Ω看来是有效的。③如果 I DA和IDB就是 I Di和 I Dj，那么，C从 Zq*中随机选取x*和s*，计算再任选，计算(可从对 H2的询问获得)，计算，类似②检查 H 中是否已经有相应3的三元组如有，重复该过程，直到找到的三元组的前两元在 H3的条目中没出现过为止，并将此条目添加到L3，计算t*←E(s*m)，C最后

解签密询问：当攻击者Ω观察到关于 I Di和IDj的签密密文时，它可能要 C解密σ*。这种情况下，C就告知他该密文无效。当签密密文是关于 I DA和 I DB的，但不是 I Di和IDj时，Ω收到该解签密询问，首先计算(可从对 H2的询问获得)，计算检查是否在L3中，如果不在，C拒绝解密该密文；否则，C解签密恢复出m。

2) 分析阶段

下面对上述模拟进行分析，计算C成功的概率。如果Ω在第一阶段对 I Di和 I Dj执行密钥提取询问，C将失败。而在 q1次密钥提取询问中，选择(I D,I D )的方法有 c2种，因此，Ω选择身份 I D和

i j q1iIDj作为挑战身份的概率大于。在第二阶段询问中，如果Ω对执行 H2询问，C将失败，同理，在对 H2的 q2次询问中Ω不对执行 H2询问的概率大于q1。在对签2密机的一次询问中，由于 C失败的概率最多为那么，q 次签密机询问失败的概率最多为s，则C成功的概率至少是1因此，C 解决 BDH 问题的优势至少为。在C的计算时间方面，每次签密和解签密询问都是最多需要1次双线性对运算。

4.1.2 不可伪造性

S-IDSC的不可伪造性是基于椭圆曲线上离散对数困难问题（ECDL问题）的。ECDL问题是指：已知计算使得，其中P是 G1的生成元。

结论 2假设椭圆曲线上离散对数问题是困难的，那么在随机预言机模型下，S-IDSC是适应性选择消息攻击下存在性不可伪造的。

如果一个敌手能伪造一个S-IDSC中的签名，那么他就能伪造文献[12]中椭圆曲线上的短签名SECDSS1。文献[1]指出在离散对数困难问题下，如果将散列函数视为随机函数，那么，签名标准算法DSS的变体 SDSS1是在适应性选择消息攻击下存在性不可伪造的；因此，在椭圆曲线离散对数问题困难假设和随机预言机模型下，S-IDSC是在适应性选择消息攻击下存在性不可伪造的。

4.2 效率分析

S-IDSC与已有基于身份的签密算法相比，效率明显提高，这主要体现在计算量和通信量两方面。首先，从基于身份签密中涉及的主要运算：双线性对运算（P）、标量乘(M)和指数运算(E)来考察，S-IDSC的签密算法需要1个双线性对运算和1个标量乘运算，不需要指数运算；其解签密算法需要 1个双线性对运算和2个标量乘运算，也不需要指数运算，因此，S-IDSC共需要2个双线性对运算，3个标量乘运算，不需要指数运算。要特别说明的是，S-IDSC中的2个双线性对运算都是可以预计算的。进一步，考察S-IDSC的传输量，在S-IDSC中，需要传输的信息是σ=(t,r)，传输量是用表1给出本文算法与目前已有的几个重要基于身份签密算法的效率比较。在表1中， x( + y )表示x次双线性对运算，y次双线性对预运算。

表1 S-IDSC与已有重要基于身份签密算法的效率比较

5 S-IDSC在ad hoc网络中应用说明

对ad hoc网络来说，密钥必须由网络节点自己动态生成并分发。在密钥分发或传递过程中常常需要安全秘密信道，以确保密钥分发过程的机密性和认证性，不仅如此，ad hoc网络无线链路、微型终端、电池供电等特殊网络环境，要求所使用的安全方案必须是轻量级的，力求最小的计算和传输量以节省资源。S-IDSC计算和传输代价低，从而可缩短密钥分发的时间、节省带宽资源，能有效地实现ad hoc网络的密钥管理的安全要求。下面以文献[13]中ad hoc网络的基于身份的(,)tn门限密钥管理中服务节点系统密钥份额更新为例，说明S-IDSC在ad hoc网络安全协议中的应用方法。基于 S-IDSC的ad hoc网络(,)tn门限密钥管理中服务节点系统密钥份额更新协议过程如下。

1) 初始化：由离线的PKG选择ad hoc网络的的系统参数，包括S-IDSC中的系统参数。

2) 更新请求：为了提高网络的可用性，假设整个ad hoc网络被划分成定长时段，在每个时段结束前，各服务节点必须要为自己请求下一时段的新系统密钥份额。为此，请求节点广播请求信息；收到该信息的邻居服务节点，验证请求节点的身份，验证通过，该邻居节点为请求节点生成部分新系统密钥份额，并对该份额进行签密运算，将所得到的签密密文通过公开信道发送给请求节点。

3) 更新生成：请求节点解签密密文，获得邻居服务节点为它生成的部分新系统密钥份额，然后通过可验证秘密共享中的方法验证份额的正确性。在(,)tn门限密钥管理中，当请求节点收到并解签密了t个邻居服务节点的签密密文，得到t个正确的部分新系统密钥份额后，请求节点利用Lagrange插值公式，将这t个部分新的系统密钥份额进行合成，生成自己的新系统密钥份额。

此过程中由于S-IDSC的应用，实现了系统私钥共享分额信息在ad hoc网络公开信道的高效安全传输。

6 结束语

签密作为同时实现机密性和可认证性的重要密码工具，对解决ad hoc网络目前面临的安全问题具有重要意义。本文给出了一种新的基于身份的签密算法S-IDSC，并证明了其在随机预言机模型下是可证明安全的；关于新签密算法S-IDSC的效率，通过与已有基于身份签密算法的比较，体现出新签密算法的高效性。尤其是其低的计算和传输需求，能很好满足ad hoc网络通信实现安全性的要求。通过对新签密算法在ad hoc网络密钥管理安全协议中应用的简述，说明了这种基于身份的新签密算法在ad hoc网络通信安全协议中的使用方法。在此特别指出，研究适合于ad hoc网络安全通信的签密算法，并将研究成果用于 ad hoc 网络安全协议是必须加强的一个重要方向，这不仅是密码学应用研究的需要，也是ad hoc 网络广泛应用的迫切需要。

[1] ZHENG Y L. Digital signcryption or how to achieve cost (signature &encryption) ＜＜ cost (signature) + cost (encryption)[A]. Cryptology-CRYPTO’97, LNCS1294[C]. Berlin, New York, Tokyo, 1997.165-179.

[2] LI F G, HU Y P, ZHANG C R. An identity-based signcryption scheme for multi-domain ad hoc networks[A]. ACNS 2007, LNCS 4521[C].2007. 373-384.

[3] KIM H, SONG J, YOON H. A practical approach of ID-based cryptosystem in ad hoc networks[A]. Wireless Communications and Mobile Computing[C]. 2007. 909-917.

[4] DENG H, AGRAWAL D P. TIDS∶ threshold and identity-based security scheme for wireless ad hoc networks[J]. Ad Hoc Networks, 2004,2 (3)∶ 291-307.

[5] LI J F, WEI D W, KOU H Z. Identity-based and threshold key management in mobile ad hoc networks[A]. International Conference on Wireless Communications, Networking and Mobile Computing 2006.(WiCOM 2006)[C]. 2006.1-4.

[6] KAMAT P, BALIGA A, Trappe W. An identity-based security framework for VANETs[A]. VANET’06[C]. Los Angeles, California, USA.2006. 94-95.

[7] MALONE-LEE J. Identity based signcryption[EB/OL]. http∶//eprint.iacr.org/2002/098/.

[8] LIBERT B, QUISQUATER J. A new identity based signcryption schemes from pairings[A]. 2003 IEEE Information Theory Workshop[C]. Paris, France, 2003. 155-158.

[9] CHOW S S M, YIU S M, HUI L C K. Efficient forward and provably secure ID-based signcryption scheme with public verifiability and public ciphertext authenticity[A]. Information Security and Cryptology-ICISC 2003, LNCS 2971[C]. Berlin, Springer-Verlag, 2004,352-369.

[10] CHEN L, MALONE-LEE J. Improved identity-based signcryption[A].Public Key Cryptography-PKC 2005, LNCS 3386[C]. Berlin,Springer-Verlag, 2005.362-379.

[11] BARRETO P S L M B, LIBERT N. Efficient and provably secure identity-based signatures and signcryption from bilinear maps[A].Advances in Cryptology-ASIACRYPT 2005, LNCS 3788[C]. Berlin,Springer-Verlag, 2005. 515-532.

[12] ZHENG Y, IMAI H. How to construct effcient signcryption schemes on elliptic curves[J]. Information Processing Letters, 1998, 68∶227-233.

[13] LI G S, HAN W B. A new scheme for key manegement in ad hoc networks[A]. ICN2005, LNCS 3421[C]. 2005. 242-249.