ad hoc网络具有撤销机制的密钥管理方案

孙 梅，张 娟

SUN Mei,ZHANG Juan

淮北师范大学 计算机科学与技术学院，安徽 淮北 235000

College of Computer Science and Technology,Huaibei Normal University,Huaibei,Anhui 235000,China

1 引言

ad hoc网络是一种无网络基础设施的无线自组织网络。与传统的网络相比，ad hoc网络具有以下特点：（1）自组织性，所有的移动节点都具有路由器和终端节点的双重身份，节点之间通过分布式算法实现互联互通；（2）没有中心认证机构和公钥基础设施；（3）网络拓扑动态变化，网络中的节点具有移动特性，且节点可能在任意时刻关机或离开网络；（4）节点的带宽和能源有限。ad hoc网络的自组织方式，有限的网络带宽和能源，无线通信等特点，使得传统有线网络中基于PKI的中心式密钥管理方案不适用于该网络。

针对ad hoc网络的特点——没有中心认证机构和公钥基础设施，将信任分布化是解决ad hoc网络密钥管理的一种有效的手段。Zhou和Hatz[1]首先提出了基于(n，t)门限密码的分布化ad hoc密钥管理方案，但没有实现完全分布化，仍需要密钥产生中心进行系统密钥的分发。后来Luo[2]等提出了自安全的ad hoc网络，无需第三方，靠节点相互协作产生并分发系统密钥。Kong等人[3-4]给出了安全分布式密钥管理方案，网络中的所有节点都是服务节点，均可与其他节点完成密钥服务的功能。上述方案[1-4]都是采用基于证书的RSA公钥机制实现的，算法的开销大，且安全性不高。

Khalili[5]提出了基于ID的ad hoc网络密钥管理机制。基于ID的密码体制[6]可以使用较短的密钥满足较高的安全要求，适合资源有限的ad hoc网络。Deng[7]等提出了一种基于ID的ad hoc网络的密钥管理方案，以完全分布式安全地建立用户私钥；杜春来等[8]提出了一种建立在椭圆曲线域上的基于双向身份认证的移动ad hoc密钥管理框架；李慧贤等[9]给出了适合ad hoc网络无需安全信道的密钥管理方案，可以在公共信道上传输节点密钥，相对其他方案[5，7]能更好地节省带宽和节点的能量。以上方案[7-9]都是基于ID的密码体制的，主要采用椭圆曲线密码体制，公钥短，计算量小；采用分布化方式产生系统密钥和用户密钥，有效避免了单点失败，安全性较好。但是没有考虑用户密钥泄漏，或发生异常后如何撤销原有密钥以及重新设定新密钥等问题。

基于以上原因，本文借鉴文献[9]的方案，在无需安全信道的基础上给出了一个具有密钥撤销机制的基于身份的ad hoc网络密钥管理方案，并在此基础上实现了用户签名。方案在门限密码学的基础上采用椭圆密码体制以完全分布化方式建立系统密钥。分析表明该方案不仅有良好的容错性，能有效节省带宽和计算量，能抵御网络传统的主动和被动攻击等特点，而且可以在密钥泄漏的情况下，通过注销用户密钥，有效防止攻击者的伪造攻击。即使攻击者成功伪造了用户的签名，用户还可以通过系统签名注销消息来证明伪造签名无效。方案具有更高的安全性。

2 双线性映射的基本理论

（1）双线性映射：设 (G1，+)，(G2，·)为阶是素数 q 的循环群。称满足如下性质的映射e:G1×G1→G2为双线性映射：

①双线性性：任意 P,Q∈G1，任意a,b∈Z*q，总有 e(aP，bQ)=e(P，Q)ab。

②非退化性：存在 P,Q∈G1，满足 e(P，Q)≠1G2。

③可计算性：任意P,Q∈G1，存在一个有效的算法计算e(P，Q)。

（2）相关的困难问题：设P是(G1，+)的一个生成元，给出(G1，+)上的一个困难问题。

计算Diffie-Hellman问题（CDH问题）：已知(P，aP，bP)，计算abP，其中a,b∈Z*q是未知的。

3 具有密钥撤销机制的ad hoc网络基于身份的密钥管理方案

本文借鉴文献[9]的方法由一个离线的局部注册中心（Local Registration Authority，LRA）来实现用户身份的鉴别，用户私钥的发布不需要安全通道，系统密钥和用户私钥由多个分布式密钥生成中心（Distributed Key Generation Center，DKGC）协作生成。在该方案中，每个用户有一个唯一的固定长度的ID来表示身份信息。为了区分用户各时间段的密钥，每个用户在申请密钥时，随机选择一个数K和ID绑定。若在某一时刻用户发现自己的密钥异常或泄漏了，可以向密钥服务节点申请注销K和ID的绑定，重新选取一个新的随机数和ID绑定，产生新的密钥。密钥服务节点将已注销的ID与K保存在注销列表中，并将此注销消息向全网广播。当有攻击者窃取他人私钥伪造签名时，其他用户可以通过查询注销列表，发现其伪造行为。

3.1 系统初始化

系统选择两个阶数同为素数q的群(G1，+)和(G2，·)，P是G1的生成元，e:G1×G1→G2是安全的双线性映射，{1,2，…，N}，N为网络节点总数）表示ad hoc网络中每个节钥为s，公钥为Ppub=sP。参与系统密钥生成的DKGC节点数为 n(1≤n≤N)，门限值为 t(t≤n≤2t-1)。n个DKGC组成一个组播组，它们之间可以使用组播协议通信。每个DKGC节点建立两个列表：注销列表和运行列表，注销列表用来保存用户注销过的ID与K的绑定，运行列表用来保存目前用户正在使用的ID与K的绑定。用户初始登录网络时，可以从离自己最近的DKGC节点复制注销列表，以后根据系统广播的注销消息更新复制的注销列表。

3.2 系统密钥产生

每个服务节点 DKGCi(i=1，2，…，n)随机选择一个秘密数，建立一个t-1阶多项式 fi(x)：

然后向其他DKGC节点发送部分密钥份额si，j=fi(j)(j≠i)，同时计算 Vi，0=diP ，Vi，k=ai，kP(k=1，2，…，t-1)，并将其在组播组中组播。节点DKGCj收到si，j后验证等式（1）是否成立。

DKGCj在收到 n-1个有效的 si，j(i≠j)后，计算自身的

3.3 用户注册

用户节点ul（其身份标识为IDl），首先到LRA离线注册一个盲因子，具体做法如下：

用户ul选择一个秘密随机数计算盲因子 Rl=rlP，然后将(IDl，Rl)提交给LRA。LRA计算Ul=H(IDLRA||IDl||Rl||Tl)，Sigl=s0Ul，Tl为盲因子的有效期。

3.4 用户密钥发布

用户ul要获得密钥，可以向离自己最近的一个DKGC节点提交请求信息，具体过程如下：

（1）用户 ul选择一个随机数，并计算Yl=rlH(IDl||Kl||dt)，dt为密钥生效时间（＞当前时间），然后将{IDl，IDLRA，Rl，Sigl，Tl，Yl，Kl，dt}发送给离自己最近的一个DKGC节点，记为 DKGCi。

（2）DKGCi验证等式（2），（3）：

若两式都成立，DKGCi将此请求信息 {IDl，IDLRA，Rl，Sigl，Tl，Yl，Kl，dt} 在组播组中组播，并找出 t-1 个 DKGC 节点（记为 DKGCi(i=1，2，…，t)），共同协作为 ul生成密钥。DKGCi为ul计算部分密钥 Xi=siYl，并通过公开信道发送给ul。系统的每个DKGC节点都将用户的申请信息{IDl，IDLRA，Rl，Sigl，Tl，Yl，Kl，dt}保存在自己运行列表中。

（3）ul收到 DKGCi的 Xi后验证等式（4）是否成立。

在t个 Xi被验证通过后，计算密钥：

3.5 用户密钥的注销和新密钥的申请

（1）如果用户ul发现密钥异常或泄漏，可以向离自己最近的DKGC节点（记为DKGCk）提交注销密钥的申请信息rq，rq中包括用户的身份 IDl，随机数Kl，以及注销时间（≥当前时间）等。如果用户需要新的用户密钥，同时提交{IDl，IDLRA，Rl，Sigl，Tl，Yl'，Kl'，dt'}等信息，其中为用户ul选择的一个新的不重复随机数，Yl'=rlH(IDl||Kl'||dt')，dt'为新密钥生效时间（＞注销时间和当前时间）。

（2）DKGCk对申请信息进行审核，即验证等式（2）和（5）：

若审核通过，首先，DKGCk在网络中广播取消IDl和Kl的绑定，其他节点（包括DKGC节点）将IDl和Kl以及注销时间添加到自己的注销列表中，DKGC节点在运行列表中删除IDl和Kl的绑定；然后，DKGCk在组播组中组播rq和{IDl，IDLRA，Rl，Sigl，Tl，Yl'，Kl'，dt'}，并找出 t-1个DKGC节点（记做 DKGCi(i=1，2，…，t)），共同协作为 ul生成密钥。DKGCi为 ul计算 σi=siH(rq)和 Xi'=siYl'，并通过公开信道发送给ul；最后，系统的各DKGC节点将新的绑定信息 {IDl，IDLRA，Rl，Sigl，Tl，Yl'，Kl'，dt'}保存到自己的运行列表中。

（3）ul收到DKGCi的 Xi后验证下列等式是否成立。

在t个 Xi被验证通过后，计算密钥：

和注销消息的系统签名：

3.6 用户签名

本文的签名方案是对Hess[10]的基于身份的签名方案进行了扩展，Hess的方案安全性建立在CDH问题难解的基础上，且已在Random Oracle模型下证明是CPA（选择明文攻击）安全的。

若用户uk需要ul为信息m签名，那么ul随机选择一个秘密数 w∈Z*q，计算 γ=e(P，P)w，得到消息m的Hash值v=H1(m||γ||dt1)，dt1为签名时间，产生签名：

ul将签名{λ，IDl，Kl，dt，m，v，dt1}(dt1≥ dt)发送给用户uk，uk收到后检查自己是否有注销列表，若无，则向离自己最近的DKGC发送复制注销列表的请求，在复制的注销列表中，uk检查 IDl，Kl，dt是否存在，若存在，则认定签名无效。否则计算 γ'=e(λ，P)e(H(IDl||Kl||dt)， -Ppub)v，当且仅当v=H1(m||γ′||dt1)时接受签名。

4 密钥管理方案及用户签名方案的正确性分析

定理2 用户签名{λ，IDl，Kl，dt，m，v，dt1}(dt1≥dt)的有效性可以通过注销列表和等式v=H1(m||γ'||dt1)来验证。

证明 假如绑定信息 IDl，Kl，dt(dt1≥dt)出现在注销列表中说明用户ul在dt时刻已经注销了自己的密钥，所以本次签名是无效的。若密钥未被注销则可以计算：

5 密钥管理方案及用户签名方案的安全性和性能分析

5.1 密钥管理方案的安全性分析

本方案的安全性基于椭圆曲线上的离散对数问题的困难性，同时采用了基于盲签名的传输方案，保证了在公共通道上传输用户密钥的安全性。

（1）和文献[9]相比，本文提出的方案也可以达到第III级信任[9]，即信任用户和可信第三方（Trust Third Party，TTP）不知道用户的私钥，若TTP产生了假的用户公钥，可以证明该公钥为假。

在本文方案中，每个DKGC节点只发布了用户ul的部分私钥，它并不知道用户的完整私钥。如果有恶意的DKGC节点假冒ul欺骗其他DKGC节点，它首先要选择一个rl′∈，伪造LRA的签名为。其他DKGC节点可以通过等式（2）来进行验证，发现其伪造行为，即e(Sigl'，P)≠e(Ul'，PLRA)，所以恶意的DKGC节点无法伪造 ul。如果LRA要假冒用户ul，它选择一个，计算 Rl''=rl''P ，Ul''=H(IDLRA||IDl||Rl''||Tl)和签名Sigl''=s0''Ul''，然后向某个DKGC发送请求信息，系统中至少有一个DKGC节点能根据运行列表中的Sigl≠Sigl''识别出恶意的LRA伪造了用户ul，所以LRA也无法伪造用户ul。其他的恶意节点想伪造ul，需要从 Rl=rlP，PLRA=s0P中计算出rl和 s0，这是离散对数问题。所以本文方案可以达到第III级信任。

（2）同文献[9]，本文的密钥管理方案也具有容错性，即使有n-t个服务节点被攻击，系统还可以提供密钥服务。证明方法参见文献[9]。

（3）同文献[9]，本文在密钥发布过程中能抵御主动攻击，包括重放攻击，中间人攻击，内部攻击。同时也能抵御被动攻击。证明方法见文献[9]。

5.2 用户签名方案的安全性分析

（1）安全模型

基于身份数字签名方案的攻击模型[11]，即攻击者A和挑战者C进行以下对局：

①运行系统初始化算法并将系统参数给A。

②A行以下询问：

hash询问，C计算输入消息的hash值，并把结果给A。

身份询问，给定一个身份ID，C返回给A与该ID对应的私钥。

签名询问，给定一个身份ID和消息M，返回给A一个ID对M的签名λ。

③A 输出 (ID′，M′，λ′)并认为 λ′是 ID′对 M′的签名。如果λ′是有效的签名并且(ID'，M')没有进行过签名询问，则称攻击者A赢得对局。

定理3假设G1中CDH问题是困难的，提出的基于身份的用户签名方案在随机预言模型下抗适应性选择消息和给定身份攻击。

证明 假设攻击者A能攻破用户签名方案，利用A能构造一个有效的算法C，C可以解G1中的CDH问题，即给定(P，aP，bP)，C欲计算 abP 。C具有{IDl，Kl，dt，Yl，yl}列表，C置PPub=aP，并如下回答A的询问。

①ID-hash询问。当A询问 ＜IDi，Ki，dti＞ 的hash值时，如果 IDi=IDl，Ki=Kl，dti=dt，C 给 A 回答 H(IDi||Ki||dti)=

②密钥提取询问。当A询问 ＜IDik，Kik，dtik＞的密钥值的私钥。A不能询问 ＜IDl，Kl，dt＞ 对应的私钥bP。

③消息hash询问。A可以进行qH次消息hash询问，息hash值返回给A。

④签名询问。A询问IDit对消息mit的签名，C按照如下步骤回答：

证毕。

（2）在密钥泄漏的情况下，通过注销用户密钥，可有效防止攻击者的伪造攻击。

如果用户ul密钥泄露了，他可以向DKGC节点申请注销密钥。系统通过广播注销消息，使其他用户都知道IDl和Kl的绑定已经被注销了，若在此之后有人提交了签名{λ，IDl，Kl，dt，m，v，dt1}(dt1≥ dt)，则可以认定该签名无效；假如有新用户初始登录网络，并且没有收到该注销消息，他可以选择从某个DKGC节点复制注销列表而得知该注销消息。即使有恶意的DKGC节点伪造了假的注销列表，使该签名有效，ul还可以通过系统签名注销消息σ=sH(rq)证明该密钥已经在dt1之前被注销了。因此，通过注销用户密钥可有效防止攻击者的伪造攻击，同时又不影响密钥注销之前的签名，因为在注销列表中有密钥注销的时间，用户签名时有签名时间，只要签名时间小于注销时间就认为签名是有效的。

5.3 性能分析

本文采用节点身份作为它的公钥，不需要额外的公钥生成和传输过程。方案的实现主要基于椭圆曲线密码体制，该体制计算量小，安全性高[12]。因此，该方案比传统的公钥算法的ad hoc密钥管理方案[1-4]具有更低的计算代价和通信代价。本文方案中，用户密钥的发布无需安全通道，与现有文献[5，7]相比，能节省通信代价和计算代价[9]。另外本文方案中，密钥服务节点形成了一个组播组，对于验证数据采用组播传输代替文献[8-9]的全网广播，有效节省了通信带宽——如文献[9]系统密钥产生需要单播n(n-1)次，广播2n次通信，用户密钥发布需要单播2t次；而本文方案系统密钥产生需要单播n(n-1)次，组播n次，广播n次，用户密钥发布需要单播1+t次，组播1次。本文在注销密钥后，重新申请密钥时，只需用户自己重新选定一个随机数，并不需要更换用户的ID，不需要LRA重新鉴定身份，有效节省了通信带宽和计算量。对于注销的密钥，本文使用注销列表来保存，只有在密钥泄漏或异常才可能注销密钥，这些情况是比较少的，所以注销列表并不是很大，不会过多占用节点的存储空间，ad hoc网络的节点有能力满足方案的要求。

6 结语

本文针对ad hoc可能会出现的密钥泄漏，异常，离开网络等情况，将密钥撤销机制应用在密钥管理中，不仅有效减少了密钥泄漏后给用户带来的损失，而且不会影响密钥泄漏前用户签名的有效性。方案同时将组播技术应用在ad hoc网络中，节省了系统的带宽和节点的能量，另外采用门限方案增强了系统的健壮性，具有较好的理论和实用价值。

[1]Zhou L，Hass Z J.Securing ad hoc networks[J].IEEE Network，1999，13（6）：24-30.

[2]Luo H，Zefros P，Kong J，et al.Self-securing ad hoc wireless networks[C]//Proceedings of the Seventh IEEE Symposium on Computers and Communications（ISCC’02）.Taormina：IEEE Press，2002：548-555.

[3]Kong J，Zefros P，Luo H，et al.Providing robust and ubiquitous security support for mobile ad-hoc networks[C]//Proceedings of 9th International Conference on Network Protocols（ICNP’01）.Riverside，CA：IEEE Press，2001：251-260.

[4]Luo H，Kong J，Zerfos P，et al.Ubiquitous and robust access control for mobile ad hoc networks[J].ACM Transactions on Networking，2004，12（6）：1049-1063.

[5]Khalili A，Katz J，Arbaugh W A.Toward secure key distribution in truly ad-hoc networks[C]//Proceedings of the Symposium on Applications and the Internet Workshops（SAINT’03）.Orlando，FL，USA：IEEE Press，2003：342-346.

[6]Boneh D，Franklin M K.Identity-based encryption from the Weil pairing[J].SIAM Journal of Computing，2003，32（3）：586-615.

[7]Deng H，Mukherjee A，Agrawal D P.Threshold and identitybased key management and authentication for wireless ad hoc networks[C]//The International Conference on Information Technology：Coding and Computing（ITCC’04）.Las Vegas，USA：IEEE Press，2004：107-110.

[8]杜春来，胡铭曾，张宏莉.在椭圆曲线域中基于身份认证的移动ad hoc密钥管理框架[J].通信学报，2007，28（12）：53-59.

[9]李慧贤，庞辽军，王育民.适合ad hoc网络无需安全信道的密钥管理方案[J].通信学报，2010，31（1）：112-117.

[10]Hess F.Efficient identity based signature schemes based on pairings[C]//LNCS 2595：Selected Areas in Cryptography（SAC 2002）.Berlin：Springer-Verlag，2003：310-324.

[11]Pointcheval D，Stern J.Security proofs for signature schemes[C]//EUROCRYPT’96.Berlin：Springer-Verlag，1996：387-398.

[12]Boneh D，Lynn B，Shacham H.Short signatures from the Weil pairing[C]//LNCS 2248：Advances in Cryptology-Asiacrypt 2001.Berlin：Springer-Verlag，2001：514-532.