基于中国剩余定理的传感器网络密钥管理协议*

陈琳(长江大学计算机科学学院，荆州湖北434023)

基于中国剩余定理的传感器网络密钥管理协议*

陈琳*
(长江大学计算机科学学院，荆州湖北434023)

无线传感器网络的安全性是目前研究的热点。传统基于临时初始密钥和基于密钥池预分配的方案难以在网络连通性和节点存储计算消耗之间有效平衡，网络生命期内使用固定不变的初始密钥/密钥池难以抵抗节点捕获攻击。本文基于中国剩余定理提出了传感器网络密钥管理协议，每个节点携带较少的密钥素材，能够实现网络最大连通，并具有较少的存储空间和计算与通信能耗;基于时间概念分多个阶段部署传感器节点时，发布的密钥素材在不同的节点部署阶段相应变化，使得网络具有自愈合功能，从而具有较强的抗节点捕获攻击。

无线传感器网络;密钥管理;中国剩余定理;点对密钥;LEAP协议

近年来，无线传感器网络WSNs(Wireless Sensor Networks)在军事和民用领域逐步得到了较广泛的应用，如战场军事侦测与跟踪、医疗防护、环境监测与森林防火等。无论传感器网络部署在何种环境，由于其带宽和资源受限的特点，都比较容易受到多种恶意攻击，因此，传感器网络的安全问题，如网络中信息的机密性、完整性，以及点间消息认证和广播消息认证等问题［1-4］，一直是该领域的研究热点，这些问题的核心就是传感器网络的密钥管理。

通常，传感器节点之间的信息传输使用点对密钥PK(Pairwise Key)进行对称加密以保证数据的机密性，因此，点对密钥的建立是传感器网络安全领域的基本问题。为建立节点间点对密钥，Eschenauer等［1］提出了随机密钥预分配方案(E-G方案)，每个节点随机从密钥池中选取m个密钥形成密钥环，两节点之间通过共同的密钥以一定的概率产生安全链路;Chan等［2］在此基础上提出了改进的q-composite方案，只有当节点间拥有的相同密钥个数超过q个时才建立安全链路。密钥预分配方案存在的不足是需要较多内存空间存储节点密钥环，网络连通性也存在局限。为了提高连通性，LEAP协议［5］提出了基于临时初始密钥(IK:Initial Key)建立点对密钥方案，即在网络部署前为每个传感器节点预置一个共享密钥IK，节点间基于IK和相关信息计算出点对密钥及其他密钥，链路建立后立即删除IK。但传感器网络通常是分阶段部署，在不同部署阶段新加入的节点存在泄露初始密钥IK的可能［6］，这将导致整个网络不安全。

为解决初始密钥泄露给网络带来的风险，文献［3，7-9］基于LEAP协议分阶段部署传感器节点，不同阶段部署的节点具有不同的初始密钥或密钥环。其中，文献［7］基于密钥池［1］思想，在每个阶段更新密钥池中的前向密钥链和后向密钥链;文献［3，8］则使用了初始密钥环，该环包含了一个节点生命周期中，与其他节点具有共同部署阶段的初始密钥。文献［10］则基于双向Hash链的思想，提出了一种抗共谋攻击的自愈组密钥分配方案。在这些方案中，即使节点被捕获，泄露的初始密钥也只是局限在有限的时间范围或有限的部署阶段，从而使得网络能够抗节点捕获攻击，并具有很好的网络连通性，在存在攻击的情况下，网络也具有良好的自愈合功能。

本文基于时间概念分阶段部署节点，在不同阶段采用不同的密钥素材，依据中国剩余定理将不同部署阶段的密钥隐含在广播数据中，继而构建节点间的点对密钥，形成安全数据传输链路;同时在网络安全性、连通性、存储和计算费用开销、网络持续性维护等方面，与已有方案进行比较分析。

1 基于中国剩余定理的密钥管理协议描述

1.1 中国剩余定理

文献［11-12］使用中国剩余定理构建群组密钥。假设无线传感器网络中有n个节点，每个节点i配置一个素数mi作为密钥，且这n个素数互质，即gcd(mi，mj)≡1，i≠j，1≤i，j≤n。

基站计算M=mi·m2·…·mn，Mi=M/mi，及Mi在模mi下的乘法逆元M'i，即满足MiM'i≡1 (mod mi)，i=1，…，n。基站随机选择群组密钥K，0＜K＜p(p为足够大的正整数)，利用群组中n个节点的密钥和K计算n个数，即计算ni=mi-K，i=1，…，n。从而可以计算中国剩余定理的唯一解X=，X中隐藏了群组密钥K。

当合法节点i收到包含X的广播消息，利用自身保存的密钥mi通过1次取模运算和1次减法运算，可以计算出群组密钥K，K=mi-(X mod mi)。对于非授权用户，即使获得了X，要正确计算出隐含的密钥K存在理论上的困难。

1.2 基本思想

假设传感器节点分为多个时间阶段部署，被部署的任一节点其生命周期内最多经历Gw个阶段，每个阶段称为一代，相邻代之间的时间间隔不完全相同。如图1所示，表示某个时刻在第Ti代共部署了Ni个节点。每个节点携带了由中国剩余定理确定的相关信息，即密钥素材{ID，Ks，G，m，X，f}，每代的素数m两两不同，中国剩余定理的唯一解X与当前部署代G、前Gw代和后Gw代的素数有关，Ks为节点与基站共享的秘密密钥。

图1 不同代时节点部署及密钥素材

基站首先根据需要选定若干互质且两两不同的素数组成序列，每个素数对应一代。如图2所示，在第i代部署Ni个节点时，选择素数mi，该代部署的节点将与已经部署的前Gw代和将要部署的后Gw代存在通信关系，将这些代对应的素数看成是一个窗口，则目前窗口中包含了n个素数，其序列为{m1，m2，…，mi，mn}，其中第i-Gw代的素数为m1，第i代的素数为mi，第i+Gw代的素数为mn;在第j代部署节点时，其对应的窗口为{p1，p2，…，pj，pn}，此时，i＜j，若i＜j≤i+Gw，说明第i代和第j代部署的节点处于生命活动期，则有pj=mj-i+1。如j=i+ 1时，p1=m2、p2=m3、…。即在新的第i+1一代部署节点时，第i-Gw代中的节点因生命期结束而全部消亡，并退出网络，基站选择的素数序列中的窗口将向右移动一个位置(图2中虚线所示)，新窗口中删除了第i代素数m1，新加入第i+Gw+1代对应的素数。

图2 基于滑动窗口的中国剩余定理示意图

为第i代部署节点时，由基站按照上述中国剩余定理随机选择密钥K，并计算中国剩余定理的唯一解X，当第i代节点广播包含X的信息请求加入网络时，网络中任一收到消息的节点可以计算出K，并认证新加入节点的合法身份，继而通过协商，计算并确定两节点之间通信的点对密钥。

1.3 密钥素材与点对密钥建立

本文为未分层网络模型。节点部署前，基站S为第i代节点设置的密钥素材包括:节点唯一标示符ID、与基站单独共享通信密钥Ks、所属代数Gi、素数为mi、由中国剩余定理计算的唯一解X，及伪随机函数f(·)。

假设节点u预加入网络，其标示符为IDu，所属代为Gi，中国剩余定理唯一解为Xi;网络中的节点v包含的信息为标示符为IDv，所属代为Gj，j＜i≤j+Gw。节点u广播信息，节点v接收信息，信息交互如下:

其中DK(·)表示用密钥K对信息对称加密，noiceu表示节点u产生的随机数，|表示连接符号。节点v收到u的广播信息，按照中国剩余定理计算出K，再计算出节点间点对密钥节点Kvu，Kvu=f(noicev|noiceu);同时节点v通过密钥K解密收到的消息，可以对节点u进行身份验证。

节点u收到v的应答消息。由于u知道密钥K，解密收到的消息并对节点v的身份进行验证，若经过身份认证，可以计算出Kuv，使得Kuv=Kvu。

无论节点u是新节点还是老节点，只要网络中活动的节点v能够接收到u的广播消息，u与v之间就能建立点对密钥。两个节点之间传输数据时，使用两次对称加密算法，分别使用点对密钥和与基站共享的密钥Ks，即Kuv(IDv|IDu|Ks(IDv|M))，表示IDv采集的数据M经过IDu转发，使用Ks加密的目的能保证没有第三方伪造数据。

当两节点u与v不在通信范围时，采用中间节点建立安全的通信链路［2，5］。

1.4 节点离开

节点因为生命期结束或能耗耗尽离开时，自动删除基站为其设置的所有密钥素材。

若基站要将某标示符为r的节点排除在网络之外，通过以下两个步骤完成:

(1)基站广播中国剩余定理唯一解X'。基站首先计算X':基站确定当前处于生命期的每一代及其携带的素数mi，i=1，…，n，随机选定密钥K'，按照中国剩余定理计算出X'并广播如下信息:

若基站要一次性排除多个节点，可以采取如下方式减少信息发送量:

(2)某节点接收到上述广播消息，利用中国剩余定理解析出隐藏的密钥K'，通过K'可以对该消息进行认证，并记录下被排除的一个或者多个节点的标示符，不再响应这些节点的任何请求。

其中，noice'为基站选择的随机数，一个节点可以利用与基站单独共享通信密钥Ks给基站发送消息DKs(r1|…|rq|X'|noice')，以求证删除节点的真实性。

2 协议性能分析

2.1 连通性分析

本文假设网络为非分层模型，基站即为控制部分。基站在不同阶段部署节点，任意阶段部署的节点，能与其通信范围内的任一节点建立点对密钥，建立安全链路。

定理:通信范围内任意两个处于活动状态的节点能够建立点对密钥。

证明:如图2所示，假设第i代节点u和第j代v在彼此的通信范围内，且i＜j，j-Gw≤i，j≥i+Gw，设第i代部署时刻计算Xi时使用的素数序列为{m1，m2，…，mi，mn}，第j代计算Xj时的素数序列为{p1，p2，…，pj，pn}，则两个序列有若干重叠的素数。

根据2.2部分，基站部署节点u时，计算的Xi中包含了第j代的素数pj，因此节点v可以接收到包含了Xi的消息，并使用中国剩余定理获取Xi中嵌入的随机密码Ki，再按照2.3部分计算出点对密钥Kuv，从而与节点u建立安全链路。

同理，当节点v发送Xj消息时，节点u可以接收到包含Xj的消息，并求解出点对密钥Kvu，完成安全链路的建立。

即在通信范围内的两个节点u与v，无论谁首先发起链路建立请求，都可以建立点对密钥，实现安全通信。证毕。

当一跳不能建立连接时，可以通过中间节点建立通信路径和点对密钥。按照此方案，网络可以实现最大连通。

2.2 安全性分析

(1)非法节点对网络的影响。假设网络中的节点都具有合法身份，当第三方入侵，能够获得其他节点广播的消息，即使获得了消息中包含的中国剩余定理的唯一解X，在没有密钥素材的情况下，也难以窃取到X中嵌入的密钥K，或者计算的密钥与K不一致;若第三方发出虚假的消息i|ID|X|DK(i|ID|X |noice)试图连接到网络中某节点，同样由于双方密钥K不一致，会导致通信失败而无法建立连接。

(2)一个节点被捕获时，不影响其他节点采集数据的正确性。在通信范围内的两个节点u与v建立点对密钥时，使用了两个随机数和f(·)运算，如上述的Kvu=f(noicev|noiceu)，同时在u和v通信范围内的第三方可以监听广播信息并解析出noicev与noiceu，并计算出Kvu，否则，第三方只能获得最多一个随机数，难以算出点对密钥。当第三方计算出密钥Kvu，也只能假冒u与v之间链路的下游一方发送错误数据，而不能假冒使用该链路转发数据的其他节点，因为其他节点发送的数据和其标示符一起，被与基站独享的密钥Ks进行了加密，第三方难以伪造采集数据的节点和数据。

(3)网络具有自愈合功能。当多个节点被捕获时，网络面临严重的安全威胁，但是经过多代节点部署以后，网络能够自愈合。理论上，节点被捕获后，其所携带的密钥材料全部泄露，如果当前处于活动状态的每一代均有节点被捕获，则网络面临严重的安全威胁。但是若持续经过Gw代部署，且再无节点被捕获，则由上述滑动窗口的概念，被捕获的节点不再具有滑动窗口内的素数，即使接收到其他节点广播的包含X的信息，也无法计算出隐藏在X中的密钥，网络重新变为安全，即随着时间的推移，网络具有自愈合功能。

若网络中存在节点被捕获，导致传输数据异常、数据包丢弃等，基站利用信任机制［13］发现非法节点，并使用1.4部分的方法，通知不同代部署的节点不响应被捕获节点发出的任何请求，同时，通过捕获节点转发信息的其他节点重新发起安全链路建立请求建立新的安全链路，从而被捕获节点排除在网络之外，保证网络安全。

2.3 空间消耗与计算、通信能耗分析

文献［6］的能耗模型指出，发射功耗是发射数据比特数k和发送距离d的函数;而节点接收数据功耗只与它收到的数据量有关，与发送者距离的远近无关;发送功耗和接收功耗分别用下式表示:

其中，Eelec为收发电路的基本功耗，Eamp为功率放大电路的系数，具体值由硬件特性决定。

本网络模型中，传感器节点携带的密钥素材为{ID，Ks，G，m，X，f}，假设需要的存储空间分别为16 bit、128 bit、16 bit、128 bit、16 bit、160 bit;DK(·)加密结果128 bit;节点距离为1个单位;密钥环大小m=Gw。

构建点对密钥时，本文及其他两种典型的在时间上分阶段进行密钥管理方法［3，7］的节点发送信息能耗、计算能耗和空间消耗等如表1所示。一般情况下，密钥环m≥200［2，5，7］，若假设3种计算的能耗相同，则本文提出的点对密钥构建协议具有最小的通信能耗和计算能耗，由于使用了中国剩余定理，节点密钥素材使用的存储空间也最小。

表1 建立点对密钥的能耗和空间分析

3 总结

本文分析了传感器网络中基于初始密钥和基于密钥池密钥管理协议。针对存在的不足，利用中国剩余定理，在不同时间阶段部署节点的情况下，提出了新的密钥管理协议建立节点间的点对密钥，新方案能够在节点携带较少密钥素材的情况下，使用较少的通信和计算能耗，实现网络最大连通，并具有网络自愈合功能。协议存在的不足是没有考虑网络分层的环境，并且传输数据时采用两次加密，在中间节点进行数据融合时会增加计算开销，需要进一步研究扩展中国剩余定理的应用;另外，密码体制可以有效抵御外部攻击，而对于来自内部的攻击，还需要通过信任机制有效识别非法节点并将之排除在网络之外。

［1］Eschenauer L，Gligor V D.A Key-Management Scheme for Distributed Sensor Networks［C］//ACM CCS’02，2002:41-47.

［2］Chan H，Perrig A，Song D.Random Key Predistribution Schemes for Sensor Networks［C］//IEEE SP’03，2003:197-213

［3］Tian Biming，Han Song，Liu Liu，et al.Towards Enhanced Key Management in Multi-Phase ZigBee Network Architecture［J］. Computer Communications 2012(35):579-588

［4］Arvind Seshadri，Mark Luk，Adrian Perrig.SAKE:Software Attesta-tion for Key Establishment in Sensor Networks［J］.Ad Hoc Networks，2011(9):1059-1067

［5］Zhu S，Setia S，Jajodia S.Leap:Efficient Security Mechanisms for Large-Scale Distributed Sensor Networks［C］//ACM CCS，2003: 62-72.

［6］Liu Zhixin，Qing Chao，Zhen Ga，et al.A Distributed Energy-Efficient Clustering Algorithm with Improved Coverage in Wireless Sensor Networks［J］.Future Generation Computer Systems，2012 (28):780-790

［7］Castelluccia C，Spognardi A.A Robust Key Pre-Distribution Protocol for Multiphase Wireless Sensor Networks［C］//IEEE Secure Com，2007:351-360.

［8］Jang J，Kwon T，Song J.A Time-Based Key Management Protocol for Wireless Sensor Networks［C］//Information Security Practice and Experience，2007:314-328.

［9］王国军，吕婷婷，过敏意.无线传感器网络中基于临时初始密钥的密钥管理协议［J］.传感技术学报，2007，20(7):1581-1586

［10］王秋华，汪云路，王小军，等.无线传感器网络中抗共谋的自愈组密钥分配方案［J］.传感技术学报，2013，26(2):221-227

［11］李凤华，王巍，马建峰.适用于传感器网络的分级群组密钥管理［J］.电子学报，2008，36(12):2045-2011

［12］Xinliang Z，Chin-Tser H，Manton M.Chinese Remainder Theorem Based Group Key Management［C］//Proceedings of the 45th ACM Southeast Conference(ACMSE 2007).Winston-Salem，Northarolina，USA:ACM Press，2007:266-271

［13］Yu Yanli，Li Keqiu，Zhou Wanlei，etal.Trust Mechanisms in Wireless Sensor Networks:Attack Analysis and Countermeasures［J］. Journal of Network and Computer Applications，2012(35):867 -880

陈琳(1972-)，男，湖北荆州人，长江大学计算机科学学院教授、博士、硕士生导师、计算机科学学院副院长，主要研究方向为计算机网络、传感器网络、网络安全，chenlin@yangtzeu. edu.cn。

A Novel Key Management Scheme Based on the Chinese Remainder Theorem for Wireless Sensor Networks*

CHEN Lin*

(Yangtze University，College of Computer Science，Jingzhou Hubei434023，China)

Research ofsecurity problem in wireless sensor networks(WSNs)is a challenging hotspot over the last ten years.Traditional schemes those based on temporary initial key and key pre-distribution using key pools are difficult to be tradeoff between the network connectivity and node storage space，and the same initial key or the key pool in these approaches is also vulnerable to againstnode capture attacks，this leaves key managementas a fundamentalresearch topic in the field of WSNs security.In this paper，a novel time-based key management scheme for WSNs using the Chinese Remainder Theorem is proposed，in our strategy each sensor node with fewer key material is deployed over different time stage，and the important parameter in key materials change correspondingly over time.We introduce the process of pair-wise key create，node addition and revocation，and show thatthe proposed key management solution can achieve maximum network connectivity with less energy consumption about communication and calculation，and also make the network has self-healing function and strong resistance to node capture attack.

wireless sensor networks;key management;china remainder theorem;pairwise key;LEAP protocol

TP393.17

A

1004－1699(2014)05－0687－05

10.3969/j.issn.1004－1699.2014.05.022

项目来源:湖北省自然科学基金项目(2011CDC126)

2014-03-04

2014-04-21