无线传感网分布式密钥分配方案综述

是霖骁，吴 蒙

(南京邮电大学 计算机、软件学院，江苏 南京 210003)

无线传感网分布式密钥分配方案综述

是霖骁，吴 蒙

(南京邮电大学 计算机、软件学院，江苏 南京 210003)

近年来，无线传感网以其特殊的军事、商业前景而广泛受到关注，与传统有线网络相比，无线传感网有着自己的优势和特性，而在信息社会，信息安全无疑是研究的一个重要方向。至此，国内外学者对无线传感网的安全性进行了大量研究，尤其是在密钥分配这一方面，首先对密钥分配的概念进行阐述，针对无线传感网自身特点，选取了较为合适的分布式密钥分配方案，分析了几种方案的基本原理，并分别从安全性、通信计算开销和效率等角度分析了其优势和不足，最后，在此基础上进行总结与展望。

无线传感器网；信息安全；密钥分配

近年来，无线传感网(Wireless Sensor Networks, WSN)已经被越来越多的人所关注和研究。这项技术可以更方便地感知客观物理世界，从而极大地丰富了现有网络的功能，并且大大提高了人类认识世界的能力，同时，其安全问题同样受到了广泛关注。随着密码学、密码分析学等学科的发展，加密技术随之应用到了无线传感网中，同时，密钥管理与分配作为密码学的核心，在此方面的研究也有飞速的进展。

无线传感网与一般的网络在各方面都大有不同，一成不变地运用一般网络的密钥分配方法显然是不科学的，所以，本文首先阐述了一些传统的较为经典的密钥管理方案，对它们进行综述，并比较了它们的优势和不足，最后探讨了它们各自的优缺点和适用环境[1-2]。

1 无线传感网概述

1.1 无线传感网概念

微机电系统(Micro-Electro-Mechanism System, MEMS)、片上系统(System on Chip, SoC)、无线通信和低功耗嵌入式技术飞速发展，无线传感器网络(WSN)就在这样的环境下诞生了，并倚仗着其得天独厚的优势带来了21世纪信息世界的一场革命。无线传感网是由大量微小型的传感器节点，部署于想要监控的范围之内，通过自己组网的方式构成一个单跳或者是多跳的网络[3-4]。

1.2 无线传感网的形成

无线传感网的构成和使用一般需要经过如下步骤：

1)在某个带检测区域范围内随机地分配传感器节点。

2)唤醒区域内的节点，节点向周围广播自身信息，并接收周围节点所传输的信息。

3)根据节点所侦听到的邻居节点情况，每个节点通过自组织的方式构成网络。

4)选择适合自己网络的路由算法，与周围节点或基站展开信息通信。

1.3 无线传感网的特点

1)大规模

在所需监控范围通常需要大量传感器节点，所以节点的数量一般都是几千、几万个。此处的大规模性的意义有两层：首先传感器节点的密度很大，在一般情况下，由于节点的脆弱性，通常都会部署很多节点来保证获取信息的可靠性；其次，被侦查区域的面积都是非常广阔的。

2)自组织

众所周知，被侦听的大多数区域是比较偏僻和荒凉的，基础设施、天气环境、网络环境都是多变的，成千上万的节点又是随机部署的，这里要求每个节点要具备自组织的功能，要有自己的供电系统、通信系统等单元模块，可以自己对自己进行管理、配置，甚至是动态更新，从而形成自组织的无线网络。

3)动态性

该无线网络的不稳定因素很多：周围环境的多变性导致了网络的拓扑结构变化频繁，电能耗尽导致节点的失效，失效节点必须从网络中剔除……所以，无线传感网的一套自组织系统还需要能够适应这种多变的特性，从而提升网络的健壮性。

4)微型化

无线传感网的特性决定了用于该网络的传感器节点必须功耗小、体积小、集成化，在设计加密算法、密钥分配及路由选择的时候必须以这一特性为出发点。

2 密钥分配方案

密钥分配是加密中不可缺少，也是较为重要的一个环节，选取合适的、可行的密钥分配方案是进行隐私保护、数据加密的前提。

2.1 集中式密钥分配

在集中式密钥分配方案下，必须选取一个中心节点，用来产生密钥，并传递至通信的每一方。这种情况节点不需要存储大量的会话密钥，只要保存节点与中心节点的加密密钥，而该密钥用于保护传送节点与节点之间的会话密钥，这方面的主要技术是密钥分配中心KDC。

2.2 公开加密密钥分配

该方案主要对应于密码学领域中的公钥密码学(如RSA),公钥加密又称之为非对称加密，顾名思义，通信密钥只有通信的一方知道(“金钥匙”)，其他任意一方都不知道该密钥，而与之对应的公开密钥则对外公开，每个人都可以拿公开密钥与私钥所有者进行会话与通信。此类方案的主流技术是采用CA(证书授权)方案[5]。

2.3 分布式密钥分配

分布式密钥分配方案没有可信的第三方，也不采用公钥设施，显然该方法与拥有成千上万节点的无线传感网吻合，本文主要讨论的无线传感网中的密钥分配都是基于分布式密钥分配方案。

各种密钥分配方案对比如表1所示。

表1 密钥分配方案的对比

3 无线传感网中密钥的分配

由于无线传感器网络不包括可信的第三方及公钥设施，所以，一般采用分布式密钥分配方案，另外无线传感网节点能量非常有限，所以不适合采用非对称的公钥加密算法，一般都会选取合适的对称加密算法[6]。

3.1 EG方案[7]

3.1.1 主要思想

该模型是Eschenauer和Gligor首先提出来的。首先预先为网络设计一个密钥池，很多密钥对都包含在这个池中，网络根据节点的部署情况选取适当数量的密钥环，然后每个节点互相向周围节点传递自己的密钥信息，每个节点用和邻居节点相同的密钥进行通信。

步骤一：为每个网络分配一个密钥池，数量为P(P的大小根据网络情况自行选取)，在P里面随机选取k个密钥存入节点，然后进行节点的部署；

步骤二：节点向周围的节点广播自己的密钥环情况，邻居节点收到之后与自身的密钥环进行比对，如果有相同的密钥，则选取该密钥进行通信，否则，进入步骤三；

步骤三：若找不到共享密钥，则找到另外的与之存在共享密钥的节点(称为中介节点)，并与之建立多跳连接，这样就基本在每个节点与节点之间分配了不同的通信密钥。

因为有可能发现自身和邻居节点没有共同的密钥，所以该方案无法保证百分之百的连通性。影响该方案连通性的因素有：k的大小，密钥池的数量p，k与p的比例，布置区域的区域状况等。k/p越大，说明在密钥池中选取的密钥数量越多，连通的概率也就越大，但是每个节点预存的密钥很多，节点的开销就会变得很大，p越小，网络的连通性会变得很差，安全性也会很差，只需捕获很少的密钥环，整个网络安全就会瘫痪。反之k/p越小，则连通的概率也就越小，所以合理地权衡以上两个取值之间的关系是该方案的重点。

3.1.2 优缺点

优点：EG方案作为经典的无线网密钥分配方案，的确给人们带来了很大的方便。相比于一成不变的单一密钥来说，EG的出现给网络带来了很高的安全性。而且每个节点仅仅用相对的密钥对就可以基本保证与周围节点的通信；节点与节点之间互相用一对密钥传递信息，减少了基站对其的干涉，整体网络开销得到了保证。

缺点：首先，该方案在理论上不能达到百分之百密钥的分配，必然存在孤立节点；其次，在安全性要求越来越高的今天，其预先共享的密钥池方法的安全问题也越来越多。如果某网络被捕获的节点变多，那么节点中的密钥就会暴露，整个密钥池中的安全密钥就会变得很少；再次，被捕获节点的密钥也可能是其余节点的共享密钥，这样随着节点暴露数量的增多，整个网络的安全性会变得很差。

3.2 q-composite方案

3.2.1 主要思想

Chan-Perrig-Song在EG方案的基础上进行了改进，提出q-composite方案[7-8]，该方案的主要思想是：相邻节点之间若想要通信，共享的密钥环个数至少为q个。万一某节点和邻居节点所共享的密钥数量不止q个，为q′个，那么就结合所有的q′个密钥生成一个通信密钥K。K=hash(k1‖k2‖…‖kq′),至此，该情况下两个节点之间就可以得到一致的通信密钥。

若增加q值可以增加整个网络的抵抗性和健壮性，q的取值越大，网络的安全性就越高。但是减小q值才能获得较为可观的网络连通概率。此外，密钥池的选取同样重要，如果太少，那么攻击者只需获取少量的节点就可以得到很大比例的密钥空间。所以，这个算法的关键思路就是要寻找到一个合适的密钥池的大小。

3.2.2 优缺点

优点：提高了网络的健壮性。同时整个网络的安全性得到了增强，即使一个密钥被捕获，依然不会对节点安全构成威胁。

缺点：密钥池中的密钥数量必须大大增加，为整个网络带来了更重的负担，并会存在大量的冗余信息，随着被捕获节点的数量增多，该方案性能也会变得很差。另外，阈值q的选取也是该方案一个需要重点考虑的因素。

3.3 多路径密钥增强方案

3.3.1 主要思想

该方案也是在EG的基础上改进得到。假设网络中两个节点A，B，它们取得通信联络之后，发现从A到B有k条不同的路线，节点A产生K个随机数x1，x2…，xk，然后通过每条路径把随机数传输至节点B，节点B根据传送而至的各个随机数进行操作产生新的用于通信的密钥。

3.3.2 优缺点

优点：安全性有了质的提升，想要捕获密钥，攻击者必须要捕获每条路径上的一共k个随机数。

缺点：通信的前提是要找出节点和节点间的每条路径，所以计算所花的开销会很大。鉴于该方案的高能耗，该方案仅仅适用于规模性较小的网络，或者对于安全性能要求较高的网络中，或者在EG方案的基础上用该方法来保护一些比较重要的传感器节点。

3.4 Blundo方案

3.4.1 主要思想

首先有限域GF(q)上构造t阶的对称多项式

(1)

式中：系数ai,j=aj,i(0≤i≤t,0≤j≤t)是一个对称的多项式并且系数自行选取，即有f(x,y)=f(y,x)。节点部署前，会给每个节点指定一个标识符ID，假设有2个节点之间(如标识ID为u,v)想要互相通信，则只要通过交换该ID就可以建立一对共享密钥，如u把y=v带入算出f(u,v)，同理v也算出f(u,v)，则f(u,v)即为共享密钥。

3.4.2 优缺点

优点：该方案下的节点理论上可以和任意的节点取得安全连接并且进行通信，不仅仅局限于相邻的节点之间。

缺点：从理论上来说，该方案在被捕获节点小于t的情况下，是比较安全的，但是同样当被捕获节点大于某阈值时，安全性就大大降低了，而且该方法的计算开销较大。

3.5 Blom方案[9-10]

3.5.1 主要思想

Blom构造密钥对的依据是对称矩阵，首先，可信服务器在有限域GF(q)上生成(λ+1)×N的一个矩阵G(其中q为一个大质数)

(2)

式中：G公开；N表示拥护总数目。

D是一个(λ+1)×(λ+1)的随机矩阵，且D对称，定义A=(DG)T,那么显然A是一个N×(λ+1)的矩阵，于是有

AG=(DG)TG=GTDTG=GTDG=GTAT=(AG)T

(3)

由式(3)可知，AG为对称矩阵。假设节点i和j之间要通信，那么节点i把A第i行A(i)和G第i列G(i)存入节点，同理，节点j把A(j)和G(j)存入节点，即i点有A(i)G(i),j点有A(j)G(j),再通过公开G交换G(i)和G(j),此时可以算出Kij=A(i)G(j)=A(j)G(i)=Kji，则Kij=Kji即为通信密钥。如图1所示。

图1 Blom方案示意图

3.5.2 优缺点

优点：λ称为安全系数，该方案具有λ-secure特性，即只需要确保网络中被捕获的节点个数小于λ，就可以证明该网络是安全的。

缺点：Blom方案的前提是每个节点所存储的密钥长度比较大，于是由此带来的开销、能耗就变得较大。所以，该方案比较适合小规模的传感网。

4 仿真及性能对比

本文在理论分析的基础上，做出合理假设，利用MATLAB数学仿真对以上几种方法的各项性能做对比。假设节点的个数N=10000，度=50(即邻居节点个数)，密钥池中存储的密钥数量P=1 000，密钥环个数R=50，q=3。

根据表2可以看出，Blundo和Blom方案是基本可以保证每个点之间的连通性，而EG和多路径方案不能保证百分之百的连通率，至于q-composite，随着q取值的增大，连通性只会越来越差，但同时，其抗毁性也会越好。

表2 连通性分析

根据表3可以看出，在节点个数为10000甚至更多的情况之下，t与λ的取值也会很大，而且基于多项式的方案中计算和矩阵的计算开销就会更大，E-G方案和q-composite开销绝大部分依赖于密钥对数量的选取上，开销相对适中，而多路径在此之上还要加上n条路径选取的计算和通信开销。

表3 开销分析

抗毁性也是WSN中非常重要的指标之一，指攻击者能否根据已经捕获的节点来破译未捕获节点的能力。为得出抗毁性结论，做出以下仿真模型：假设攻击者能够任意捕获某个节点，WSN中20个节点受到攻击后，其余未遭受攻击的节点也被捕获的概率为p，多路径n取2，其余参数与上述仿真假设一致，根据表4可以看出，E-G方案的p最高，说明其抗毁性最差。多路径的抗毁性是根据其n条路径决定的，q-composite方案抗毁性相对较好，至于Blundo和Blom，它们分别是t、λ安全的，显然，一般WSN中的取值肯定大于20，所以相对来说，这两种方案的安全性较高。

表4 抗毁性分析

WSN有个特点是动态性，即不断会有新节点加入，旧节点退出，另外整体的网络规模也会随着各种情况不断变化，所以网络的扩展性也是必不可少的需要讨论研究的特性之一，下面简单分析一下各方案的扩展性能(见表5)：对于E-G和q-composite方案，在有新的节点加入时，只需要在密钥池中按照原来的方式继续抽取密钥环，相对操作比较简单，多路径方案需要找出它与相邻节点的每条路径，而Blundo和Blom是基于多项式和矩阵的，若网络节点产生变化，则会带来很多的计算开销。

表5 扩展性分析

5 小结

无线传感网的安全性问题正受到越来越多的关注。本文基于无线传感网介绍了常用的一些密钥分配方法，并且重点介绍了随机密钥预分配的一些方案，事实证明该方案比较适用于大规模无线传感网。另外也分析比较了各个方案的优缺点[5,11]，总的来说，面对拓扑复杂、环境变化较快的无线传感网来说，不能一味地套用一成不变的经典方案，要根据实际的网络，综合考虑开销、环境、后期的密钥更新等综合因素，折中选择相对性价比高的密钥分配方案。另外，节点和预分配密钥的浪费问题，随着网络拓扑的变化、密钥的更新、如何更新等问题也需要在密钥管理方案上进行进一步探究。

[1]CHONG C Y, KUMAR S P.Sensor networks: evolution, opportunities, and challenges[J].Proceedings of the IEEE, 2003, 91(8): 1247-1256.

[2]AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y, et al.Wireless sensor networks: a survey[J].Computer networks, 2002, 38(4): 393-422.

[3]OZDEMIR S, XIAO Y.Integrity protecting hierarchical concealed data aggregation for wireless sensor networks[J].Computer Networks, 2011, 55(8): 1735-1746.[4]KARLOF C, SASTRY N, WAGNER D.TinySec: a link layer security architecture for wireless sensor networks[C]//Proc.the 2nd International Conference on Embedded Networked Sensor Systems.[S.l.]：ACM Press, 2004: 162-175.

[5]ATZORI L，IERA A，MORABITO G．The internet of things: a survey[J].Computer Networks, 2010,54(15) : 2787-2805．

[6]1LAI B C，KIM S H，VERBAUWHEDE I． Scalable session key construction protocol for wireless sensor networks[C]//Proc.IEEE Workshop on Large Scale Real Time and Embedded Systems(LARTES) .[S.l.]：IEEE Press，2002：132-140.

[7]CHAN H, PERRIG A, SONG D.Random key predistribution schemes for sensor networks[C]//Proc.In the 2003IEEE Symposium on Security and Privacy.Washington:IEEE Computer Society, 2003: 197-213.

[8]杨庚，王江涛，程宏兵，等．基于身份加密的无线传感器网络密钥分配方法[J].电子学报，2007，35( 1)：180-184.

[9]BLOM R.An optimal class of symmetric key generation systems[C]//Proc.In the Eurocrypt 84workshop on Advances in Cryptology: Theory and Application of Cryptographic Techniques.New York: Springer-Verlag, 1984: 335-338.

[10]曾迎之.无线传感网密钥管理关键技术研究[D].长沙：国防科学技术大学,2009.

[11]MIORANDI D,SICARI S,DE PELLEGRINI F,et al.Internet of things: vision，applications and research challenges[J].Ad Hoc Networks,2012,10( 7) : 1497-1516．

是霖骁(1990— )，硕士生，主研无线传感网的隐私保护；

吴 蒙，教授，主研无线通信与信号处理技术、无线网络安全与通信系统的信息安全。

责任编辑：薛 京

Survey of Distributed Key Distribution on WSN

SHI Linxiao，WU Meng

(SchoolofComputerScience&Technology,SchoolofSoftware,NanjingUniversityofPostsandTelecommunications,Nanjing210003,China)

In recent years, Wireless Sensor Network (WSN) has attracted public attention as its promising future of military and commercial applications.Compared to traditional wired network, WSN has its distinguished characteristics and advantages.Information security is undoubtedly an important direction of research in the age of information explosion.Until now, researchers have done a lot of research on security of wireless sensor networks, particularly in terms of key distribution.Firstly, the concept of key distribution is described.Secondly, the characteristics of wireless sensor networks are analyzed, and compared them from safety and efficiency.Finally, the future research direction is discussed.

WSN；information security；key distribution

【本文献信息】是霖骁，吴蒙.无线传感网分布式密钥分配方案综述[J].电视技术,2015，39(3).

国家“973”计划项目(2011CB302903)；南京市科技发展计划重大项目(201103003)

TN915

A

10.16280/j.videoe.2015.03.019

2014-07-17