一种基于椭圆曲线的WSN密钥管理方案

罗文俊，付海洋

重庆邮电大学计算机科学与技术学院，重庆 400065

一种基于椭圆曲线的WSN密钥管理方案

罗文俊，付海洋

重庆邮电大学计算机科学与技术学院，重庆 400065

1 引言

传感器网络是由大量的传感器节点组成的，每一个传感器节点都具有体积小，价格便宜，使用电池供电，具有无线通信和监测能力等特点。这些节点通常被稠密地部署在目标监测区域内，来达到监测周围环境的目的。无线传感器网络是一个热门的研究课题，它在环境监测、军事领域、国土安全、交通管理、社区安全、森林防火、目标定位和日常生活[1]中都具有广泛的应用前景。由于传感器在应用上的特殊性，节点都被部署在无人区或者敌方区域，所以传感器节点的安全变的至关重要。虽然，现在很多的传感器网络安全技术取得了很大的成功，已经提出了许多安全技术，但是由于在设计传感器网络的协议阶段没有考虑到安全问题，导致传感器网络没有完善的安全体系，所以至今传感器网络仍存在一定的安全隐患问题。在安全方案中，最为重要的是在节点之间、节点与基站之间进行通信时，对信息进行加密和身份认证[2]。由于节点的能量、存储能力和计算能力受到了很大的限制，在安全密码系统中，其核心问题是密钥的分发问题。因此，如何根据无线传感器网络的特点设计合理、安全、高效的密钥分发方案，是提高WSN安全的关键问题。

2 相关工作

在无线传感器网络密钥管理研究的早期，人们根据节点的特殊条件限制，把目光主要集中在对称密码体制上，这是因为对称密码体制的加解密速度较快并且所需存储空间较少。人们普遍认为对称密码体制更适合无线传感器网络，但是对称密码体制在密钥管理方面一直存在着密钥预分配的问题，针对这个问题人们提出了一些密钥管理方案。Eschenauer和Gligor在WSN中最先提出随机密钥预分配方案[3]（E-G方案）。E-G方案在以下方面符合WSN的特点：首先WSN节点仅存储少量密钥就能够使网络得到较高的安全连通率；其次是在密钥预分配时不需要节点的任何先验信息；再次是在部署后节点间的密钥协商无须基站的参与，使得密钥管理具有良好的分布特性。但是该方案中没有密钥更新，缺乏有效的安全机制[4]，同时不安全因素突出，因此后续提出了很多改进方案。q-Composite随机密钥预分配方案[5]中，节点从密钥总数为L的密钥池里预随机选取m个不同的密钥，部署后两个相邻节点至少需要共享q个密钥才能直接建立配对密钥。若共享的密钥数为t＞q，则可使用单向散列函数建立配对密钥K=hash(k1||k2||…||kq)（密钥序列号事先约定）。随着共享密钥阈值的增大，攻击者达到破坏安全链路的难度呈指数增大，但同时对节点的存储空间需求也增大。因此，阈值q的选取是该方案需要着重考虑的一个因素。实验表明[5]当网络中的受损节点数量较少时，该方案的抗毁性比E-G方案要好，但随着受损节点数量的增多，该方案变得越来越差。文献[6]提出了对称多项式随机密钥预分配方案。文献[7]由实验得出椭圆曲线在WSN应用中是容易实现的。1985年，Miller等将椭圆曲线[8]引入密码学中，提出了利用有限域GF(2n)上椭圆曲线的点集所构成的群上定义的离散对数系统，可以构造出基于离散对数的一些公钥体制——椭圆曲线离散对数密码体制（ECDLC），其安全性基于椭圆曲线上离散对数问题的困难性。

3 符号

为了表述清晰，下面列出在本文所使用的符号：

ID表示节点或者簇头的身份表示；

H表示一个簇的簇头；

S表示节点或者簇头的公钥；

P表示节点或者簇头的私钥；

Request表示通信请求标识；

A，B表示普通节点；

R表示一个随机选取的随机数；

Factor密钥生成因子，一个随机数，用来生成通信密钥；

MAC表示对同一消息内其他部分的消息认证码；

EK(...)表示用密钥K对括号内的消息进行加密；

L表示节点的公钥列表大小。

4 密钥管理方案描述

图1 情况（1）、（2）的通信过程

根据安全椭圆曲线选取的条件选择安全椭圆曲线[9]E和E上的一点G，G的阶为n（n为一个大素数）。在部署节点之前将曲线E，G和其他参数q，a，b，P，n，h预分配给每个节点，并且选择一个对称加密算法DES、AES等对称密码体制。同时每个节点都拥有一个存储其他普通节点的公钥和ID的存储空间。因为节点的存储能力有限，所以节点只存储部分邻居节点的公钥和ID；因为节点的邻居节点数量大于存储空间所能容纳的数量，所以节点所存储的公钥和ID是动态的。

每个节点保存四类密钥[10]：个体密钥，是节点与基站的单独密钥；群密钥，是所有传感器节点共享的密钥；簇密钥，是节点与它的所有邻居节点共享的密钥；对偶密钥，是节点与它每一个邻居节点的单独的密钥。个体密钥和群密钥在节点部署之前被预置在节点内部；簇密钥在网络分簇之后由基站利用个体密钥进行统一分配。本文主要研究的是对偶密钥。

4.1 簇的划分

假设网络的各个节点均匀分布在部署区域内[11]。按照地理位置把整个监测区域划分成若干个子区域，每个子区域内的节点组成一个簇。给每个节点分配一个ID，是节点的唯一标志。每个簇选择一个簇首，簇首保存簇内其他节点的公钥和ID，当簇头需要更新时，旧簇头将这些公钥发送给新的簇头，然后旧簇头将保存的其他节点的公钥和ID删除，成为普通节点，新簇头广播自己的公钥和ID，簇内普通节点将旧簇头的公钥和ID作为普通节点的公钥和ID来进行处理。

4.2 通讯过程

根据节点A和节点B的存储列表可以分为三种情况：

（1）节点A的存储列表有B的公钥，同时节点B的存储列表也有A的公钥。

（2）节点A的存储列表有B的公钥，但是节点B的存储列表没有A的公钥。

（3）节点A的存储列表没有B的公钥（这种情况不用考虑节点B的存储列表是否拥有节点A的公钥，因为节点A没有节点B的公钥节点A就要和簇头通信，然后簇头会把对方的公钥发送回来）。

这里，为了方便理解将通信过程通过交互图来表述，前两种情况如图1所示。节点A想要与节点B通信（简称A和B），首先发送消息1给B说明A想要与B通信。B收到消息1后，首先通过MAC1验证消息完整性，之后验证IDA、IDB和Request，同时保存R。B查找是否拥有A的公钥，如果有，则发送消息2'给A，其中加密密钥K为PA·SB=PB·SA；如果没有，则发送消息2给簇头节点H，H接收到消息后，首先验证消息完整性，之后将消息3发给B，消息4发给A，给出Factor，进行会话密钥计算。B收到消息3后，用计算后的密钥发送消息5给A。A接收消息5后，通过解密得到R。之后进行正常的通信。

第三种情况如图2所示。节点A想要与节点B通信，首先A检查发现自己没有B的公钥，因此A发送消息1给H，说明A想要与B通信。H收到消息1后，首先通过MAC1验证消息完整性，之后验证IDA、IDB和IDh，同时保存R。H查找到B的公钥，则发送消息2给A，发送消息3给B。其中A和B分别用MAC2和MAC3验证消息2和消息3的消息完整性。之后A发送消息4给B，B接收到消息后，首先验证消息完整性，之后将比较消息4中收到的R和消息3中收到的R是否相等，相等则进行之后的安全通信。其中，消息4的加密密钥是由K=PA·SB·Factor=PB·SA·Factor进行加密计算的。

4.3 节点的更新

节点更新主要分为旧节点的退出和新节点的加入。当旧节点退出时，簇头发现节点能量耗尽或者被捕获而没有通过认证，簇头则广播消息通知簇内的其他节点该节点已经不属于这个网络，同时簇头将该节点的公钥和ID广播出去，然后将保存的该节点的公钥和ID删除。簇内的其他节点接收到消息后，判断是否存储了该节点的公钥和ID，如果存储了则将其删除，如果没有存储则不做任何其他处理。由于节点的能量消耗和被捕获的现象存在，使得网络规模发生变化，所以会有新的节点加入到网络内以使网络能够有效的工作，完成指定的任务。在新节点加入时，在部署之前节点已经被预置了公私密钥对和唯一标识ID以及其他的必要信息，当节点被部署到指定区域后，新节点广播自己的公钥和ID，簇头将保存新节点的公钥和ID。

4.4 密钥更新

图2 情况（3）的通信过程

节点秘钥的更新是由簇头决定的，并且更新是随机发生的。因为除了首次部署节点的时候节点是同一时间开始进入网络的，随着旧节点的退出和新节点的加入，节点的秘钥使用时间变得不一致，有的节点的密钥使用时间较长，存在不安全因素，所以需要及时更新秘钥。有的节点秘钥使用时间较短，一段时间内不用更新秘钥。如果秘钥更新的时间采用统一的时间段进行更新会浪费资源，因此采用随机更新秘钥的方法。簇头更新节点秘钥的时候将节点的公钥以广播的方式发送出去，节点接收到消息后判断是否是对自己的密钥进行更新，如是，则接受如下操作：当节点得到肯定是自己的密钥被更新，则与簇头通信发送请求获得私钥。簇头收到请求后将节点的私钥发送给请求节点完成秘钥更新。当其他节点收到广播消息时，首先判断是否自己是更新的对象，如不是，则查看自己的内存列表是否有更新对象的公钥，如果存储了更新对象的密钥，则更新相应的公钥，如果没有则不作任何操作。

5 分析

提出的密钥管理方案的主要思想是把密钥预分配思想与KDC（密钥分配中心）思想相结合，根据网络部署环境的特点，因为WSN是面向应用的，所以对于特定的环境需要不同的方案，本文针对特殊的部署环境，提出一种无线传感器网络密钥管理方案，其中公钥列表和命中率是这里研究的两大关键问题。命中率在这里定义为通讯中目标节点的公钥在公钥列表的概率。根据路由算法的分析可以得出源节点在通讯的过程中选择下一跳节点是有一定规律的。根据经典的随机图理论，节点的度d与网络节点总数n存在以下关系：

其中，pc为全网连通概率。若节点的期望邻居节点数为，则两个相邻节点共享一个密钥的概率为在仿真阶段设置节点为10 000个，pc为0.999 9，所以d为取整为19，同时取节点的期望邻居节点数为60；在仿真过程中取公钥列表L的大小为50。

为了达到保证传感器网络中节点安全的目的，传感器节点内保存的密钥信息越少越好，这样当敌人捕获节点后能够获得的信息越少，网络越安全。但是节点保存的信息越少越不利于网络的连通性。如果条件允许，可以为节点添加硬件来阻止被捕获节点的信息泄露，但是根据实际情况来看，传感器节点都是廉价的，加入硬件的成本过高，不适合传感器网络。因此，由于成本限制，通常没有防篡改装置，攻击者可以获得被俘获节点内的所有秘密信息。图3给出了本文方案与E-G、q-Composite方案在抗节点俘获能力方面的比较结果。这里，设置E-G、q-Composite方案中的密钥环长度为200，密钥连通率为0.33，其中q-Composite方案中q取2。

图3 抗节点俘获能力分析图

图4给出了本文方案与E-G、q-Composite方案在存储消耗方面的比较结果。这里，设置E-G、q-Composite方案中的密钥连通率为0.33，q-Composite中q取2。由图4可知，对于相同规模的WSN，本文方案比E-G方案和q-Composite方案的存储消耗少，因为本文方案中存储在节点内的密钥链要短。

图4 存储消耗分析图

由于本文方案中相邻节点所存储的密钥是动态变化的，即节点间可以动态建立共享密钥，所以在共享密钥发现阶段，相邻节点之间均可以建立会话密钥。可见，对于本文提出的密钥管理方案，密钥连通率为100%。图5给出了本文方案与E-G、q-Composite方案在密钥连通性方面的比较。这里需要说明的是，E-G方案和q-Composite方案密钥池的大小均为10 000。

图5 密钥连通性分析图

本文方案采用基于椭圆曲线的密钥管理方案，椭圆曲线密码是目前最著名的也是最有潜力的一种公钥密码系统。由于其所基于的数学问题的困难性，椭圆曲线密码体制被公认为是目前已知的公钥密码体制当中每位提供加密强度最高的一种体制。并且结合对称密码体制，通过簇头产生节点间的通信秘钥。

计算开销、内存开销都介于随机密钥预分配方案和基于密钥分配中心方案之间。但是与随机密钥预分配方案相比，在牺牲了一个可以接受的资源的同时提供了对接点的认证能力，在该方案提出的密钥管理方案中，簇头在通信的过程中可以对节点进行认证，同时节点也可以对簇头进行认证，可以更好地保证网络的安全性。

6 结束语

提出了一种新的基于椭圆曲线的密钥管理方案，在本文方案中，节点间的初次通讯都是通过簇头来实现的。后续通信节点通过查找自己的公钥列表和身份标识列表降低了节点与簇头的通信消耗，减少了能量损耗；并且节点的添加和删除更加方便，密钥更新更加简单安全。本文方案还有一些地方需要完善，有待于进一步研究与实践。后续工作主要集中在对公钥列表L大小和命中率的研究，找到一个符合实际需求的L以及确定命中率的规律，是接下来的研究重点。

[1]任丰原，黄海宁，林闯.无线传感器网络[J].软件学报，2003，14（7）：1282-1291.

[2]裴庆祺，沈玉龙，马建峰.无线传感器网络安全技术综述[J].通信学报，2007，28（8）：113-122.

[3]Eschenauer L，Gligor V.A key management scheme for distributed sensor networks[C]//Proc of the 9th ACM Conf on ComputerandCommunicationsSecurity.NewYork：ACM Press，2002：41-47.

[4]曾迎之，苏金树，夏艳，等.无线传感器网络安全认证技术综述[J].计算机应用与软件，2009，26（3）：55-58.

[5]Chan H，Peig A，Song D.Random key pre-distribution schemes for sensor networks[C]//Proc of the 2003 IEEE Symp on Security and Privacy.Washington D C：IEEE Computer Society，2003：197-213.

[6]Liu D，Ning P.Establishing pair-wise keys in distributed sensor networks[C]//Proc of the 10th ACM Conf on Computer and Communications Security.New York：ACM Press，2003：52-6I.

[7]Wander A S，Gura N，Eberle H，et al.Energy analysis of publickey cryptography for wireless sensor networks[C]//Proceedings of the 3rd IEEE International Conference on Pervasive Computing，Galveston，Texas，USA，2005.

[8]Miller V.Use of elliptic curves in cryptography[C]//Proc of CRYPTO’85.Berlin：Springer-Verlag，1985，218：417-426.

[9]张玉忠，贺江华，沐士光.安全椭圆曲线选取研究[J].中国科技纵横，2010（15）：214-215.

[10]Zhu S，Setia S，Jajodia S.LEAP：efficient security mechanisms for large-scale distributed sensor networks[C]//Proceedings of the 10th ACM Conference on Computer and Communication Security（CCS’03）.Washington DC：IEEE Computer Society，2003.

[11]宗家然，王阳阳.椭圆曲线在WSN的密钥管理中的应用[J].电脑知识与技术，2010，6（4）：828-830.

LUO Wenjun,FU Haiyang

School of Computer Science and Technology,Chongqing University of Posts and Telecommunications,Chongqing 400065,China

For security communication in the limited resources of Wireless Sensor Networks（WSN）,according to the routing algorithm thought and network environment features of deployment,this paper puts forward a key management scheme based on Elliptic Curve Cryptosystem（ECC）and pubic-key list changing dynamically.The nodes realize two regimes to switch by searching public-key list,and the scheme is based on ECC,so safety gets enough assurance.In combination with the advantages of both mechanisms,and having the authentication function of node,the scheme is better in accord with requirements of WSN. Key words：Wireless Sensor Network（WSN）;elliptic curve;security;session key;public-key list;hit rate

为在有限资源的无线传感器网络上进行安全的通信，根据路由算法思想和网络部署环境的特点，提出了一种基于椭圆曲线的节点存储邻居节点公钥动态变化的密钥管理方案。在方案中，每个节点使用公钥列表保存邻居节点的公钥，通过对公钥列表的查找决定通信密钥的协商过程，通过对公钥列表的大小进行分析，确定最佳列表长度。该方案基于椭圆曲线密钥体制，安全性得到了足够的保证，并且具有节点认证的功能，更符合无线传感器网络的要求。

无线传感器网络；椭圆曲线；安全；会话密钥；公钥列表；命中率

A

TP309

10.3778/j.issn.1002-8331.1201-0133

LUO Wenjun,FU Haiyang.One way of key management scheme based on elliptic curve for WSN.Computer Engineering and Applications,2013,49（19）：88-91.

国家自然科学基金（No.60963023）；重庆市科委自然科学基金（No.CSTC2010BB2402）；重庆邮电大学人才引进基金。

罗文俊（1964—），男，博士，研究方向：信息安全；付海洋（1987—），男，硕士研究生，研究方向：网络信息安全，无线通信安全。E-mail：f357131652@126.com

2012-01-16

2012-03-15

1002-8331（2013）19-0088-04

CNKI出版日期：2012-06-01http://www.cnki.net/kcms/detail/11.2127.TP.20120601.1457.039.html