基于对称多项式的无线传感器网络密钥管理方案*

范志英，王传有，古稀林

（1.中国电子科技集团公司第三十研究所，四川 成都 610041；2.中国人民解放军32180部队，北京 100072）

0 引 言

无线传感器网络（Wireless Sensor Network，WSN）是由大量传感器节点组成，通过无线多跳方式进行通信的自组织网络。网络中各节点通过协作感知来采集用户需要的信息，并将采集的信息通过多跳方式传输给数据汇聚中心进行分析处理。无线传感器网络由于良好的自适应性，被广泛用于军事战场、远程医疗以及智能家居等行业。但是，由于工作环境的特殊性和采集信息的敏感性，安全问题是无线传感器网络面临的巨大挑战。密钥管理作为信息安全的基础，已经成为当前传感器网络中最重要的研究课题之一，吸引了国内外大量学者的关注与研究。

由于传感器节点能量供应非常有限且节点信息传输的能量开销远大于计算的能量开销[1-2]，根据二元对称多项式的特点，本文设计了一个适用于无线传感器网络无需交互的密钥动态管理方案（Symmetric Polynomial Dynamic Key Management，PDKM）。在PDKM方案中，利用二元对称多项式的特点，各节点在无需额外信息交互的前提下，均可与其他节点建立配对密钥。配对密钥具有全连通性。同时，设计节点的密钥更新方案和对被俘获的恶意节点进行删除方案等，以保障网络安全有效工作。该密钥更新方案同时具有前向和后向安全性，并以所建立的配对密钥为基础，分别为各节点生成了广播通信所需要的广播密钥。

1 已经有研究成果

Eschenauer和Gligor首先提出了随机密钥预分配方案（E-G方案）[3]。该方案在以下几个方面满足无线传感器网络密钥管理要求：（1）每个节点存储较少的密钥就可建立较高的安全连通率；（2）密钥分配时不需要任何先验信息；（3）部署后节点间的配对密钥建立分布式进行，无需汇聚节点干预，但节点间直接连通率和抗攻击能力成反比，网络连通率越高，网络的抗攻击能力越差。

结合E-G方案与二元对称多项式的性质，Liu提出了基于二元对称多项式的随机密钥预分配方案[4]， 相对于E-G方案来说，建立配对密钥过程相对简单，直接用节点的ID进行计算即可，但同样存在连通率与抗俘获性相悖以及无法进行更新等问题。

2 假设及定义

2.1 前提假设

（1）网络中的每个节点都拥有唯一且确定的ID。

（2）网络中的每个节点与汇聚节点存在一跳或多跳链路。

（3）汇聚节点为计算能力、存储容量、能量供应等较强的节点，且存放于安全区域，在协议设计中不考虑汇聚节点的安全、计算能力及能量供应。

（4）网络中节点均可以预置一些信息，这些信息只能被使用不可被获取。也就是说，即便节点被俘获，这些信息也不能被读取，如工商银行的USB KEY[5]。

2.2 符号定义

为了方便阐述密钥管理方案，表1给出了本文所用的一些符号定义。

表1 方案描述符号表

2.3 相关定义

定义1 二元t次对称多项式对于定义在有限域Fq（q是一个素数）的二元t次多项式f(x,y)，若多项式f(x,y)恒满足f(x,y)=f(y,x)，则称此二元t次多项式f(x,y)为二元t次对称多项式[6]。

对于任意二元t次对称多项式，均具有以下两个性质：

（1）对于有限域Fq内的变量a、b，恒存在f(a,b)=f(b,a)。

（2）至少获得t个f(a,y)（其中a为有限域Fq内一已知数），才可能计算得到二元t次对称多项式f(x,y)[7]。

定义2 配对密钥多项式 节点SNi用来计算与网络内其他节点间的配对密钥的一元多项式称为节点SNi的配对密钥多项式。

3 基于对称多项式的密钥动态管理方案

本方案主要包括配对密钥多项式的分配、配对密钥多项式的更新、新节点的加入、指定节点的删除以及基于已建立的配对密钥的节点广播密钥的动态管理。

3.1 配对密钥多项式分配

配对密钥是整个网络安全通信的基础，本方案主要使用对称多项式来生成配对密钥。节点配对密钥多项式的分配主要分两个阶段进行：预置信息阶段与配对密钥多项式生成阶段，如图1所示。预置信息阶段在节点部署前进行，而配对密钥多项式生成阶段则在节点部署完成后进行。当各节点生成配对密钥多项式后，可利用此多项式与网络内其他节点建立配对密钥。

图1 配对密钥多项式分配流程

3.1.1 预置信息阶段

节点部署前，需要为节点预置拓扑控制、密钥管理等所需要的信息。此处讨论的预置信息阶段主要是指为各节点生成及预置密钥管理所需的一些信息。

首先，汇聚节点随机生成2个t´次一元多项式p1(x)（如式（2）所示），并为网络中的各节点分别生成唯一的ID。其中，多项式p1(x)、p2(y)均对外保密，且多项式次数t´与整个网络的安全性有关。随着多项式次数t´的增加，整个网络的安全性也随之增加，同时各节点的计算、通信开销也随之增加，用户可以根据需求选择合适的多项式次数t´。

其次，利用生成的多项式p1(x)、p2(y)，分别为各个感知节点生成预置信息p1(n1)、p2(n1)，并将此预置信息预置于相应感知节点中。其中，n1为相应感知节点的ID。同时，各个节点生成的预置信息均对外界以及其他节点保密。另外，汇聚节点保存的多项式p1(x)、p2(y)对外保密。为各个节点采用类似ICBC USB KEY技术进行信息预置，即预置的信息只能被各节点使用，即使节点被俘获，预置信息也不会被外界所获取[2]。

3.1.2 配对密钥多项式生成阶段

当传感器网络部署完成后，感知节点需要根据汇聚节点的广播信息生成配对密钥多项式。配对密钥多项式分配过程如下。

（1）汇聚节点随机生成一个关于变量x、y的二元t次对称多项式f(x,y)，并对生成的多项式f(x,y)以及预置的多项式p1(x)、p2(y)进行乘法运算，得到一个新的二元多项式p´(x,y)，并向所管辖区域内的所有感知节点广播多项式p´(x,y)。其中，SIDRN为生成广播信息的汇聚节点的ID。

（2）当节点SNi接收到汇聚节点SNj的广播信息后，使用其ID作为变量x的值，代入多项式p´(x,y)中进行计算，得到一个关于变量y的一元多项式p´(IDSNi,y)。节点SNi根据多项式p´(IDSNi,y)及预置的p1(IDSNi)、p2(IDSNi)，计算自己的配对密钥多项式fkSNi(y)，同时节点SNi向其邻居节点转发中继节点的广播信息。

当节点根据广播信息计算出自己的配对密钥多项式fkID(y)后，无需进行信息交互，便可与其他节点建立配对密钥。例如：存在节点SNi、SNj，其配对密钥多项式分别为fkSNi(y)、fkSNj(y)，则节点SNi与节点SNj可以利用已建立的配对密钥多项式及对方节点的ID，计们配对密钥fkSNi(IDSNj)。同理，节点SNi可以与汇聚节点SNj建立配对密钥，为fkSNi(SIDRN)。

3.2 配对密钥多项式的更新

各节点使用二元对称多项式生成的配对密钥属于确定性密钥，在使用过程中不发生变化，且二元t´次对称多项式只能提供t´级的安全性——即同一区域中t´个配对密钥多项式被俘获后，此配对密钥多项式可能被计算出来。因此，随着网络工作的进行，节点间的配对密钥可能会被攻击者获知。为了使网络能够长期安全工作，必须更新各节点的密钥。节点间的配对密钥由配对密钥多项式和ID共同产生，而节点的ID是不可变的，因此只有通过更新网络中各节点的配对密钥多项式来实现对节点间密钥的更新。本密钥管理方案采用定期更新的方法更新节点的配对密钥多项式。更新过程分为两个阶段，节点部署前的预处理阶段与节点部署后的分布式更新阶段。配对密钥多项式的更新流程如图2所示。

图2 配对密钥多项式更新流程

3.2.1 预处理阶段

此阶段工作主要在节点部署前进行。

首先，汇聚节点随机生成若干组多项式：

随着网络工作时间的进推移，汇聚节点会根据需求生成更多的多项式组，生成的多项式组对外界和各节点均保密。

其次，服务器采用类似工商银行USB KEY方式（即预置的信息只可使用，不可读取），为每个中继节点顺序预置lr/t个随机生成的多项式组和最小组号，组号从0开始依次累加。其中，lr为中继节点预计最长工作时间，t为进行更新的时间间隔；同时，服务器为每个感知节点使用相同于中继节点的方式预置ls/t组多项式值，其中ls为感知节点预计最长工作时间。多项式值组为按照顺序生成的多项式组以节点ID为变量值，计算得到：

并为每个感知节点预置多项式值组的最小组号，组号从0开始，依次累加。

3.2.2 分布式更新阶段

中继节点每隔时间段t，便对其管辖区域内感知节点的配对密钥多项式进行更新，其中更新时间间隔t取决于网络安全性的需求和网络受攻击的强度。随着时间段t的减小，网络安全性增强，同时更新开销，如通信开销、能量消耗、节点存储开销等也会随之增大。整个分布式更新过程主要分为两步完成。

（1）汇聚节点随机生成二元对称多项式f(x,y)，并根据更新轮次号i，选择相应的多项式组{pi,1(x),pi,2(y)}，通过乘法计算得到多项式p´(x,y)，并向节点广播此更新信息。

（2）节点SN收到广播消息后，根据更新轮次找到相应的预置信息{pi,1(IDSN)·pi,2(IDSN)}，计算自己的配对密钥多项式fkSN(y)，同时向其邻居转播汇聚节点的广播信息。

（3）当所有节点均完成以上操作时，更新完成。

3.3 指定节点的删除

工作中，部分节点可能会被攻击者恶意俘获，并对节点进行再编程后重新部署到监测区域，使其成为内部恶意节点。通过定时更新可以防止整个密钥管理系统被破解，但无法删除网络中被俘获节点后的恶意节点。因此，为了整个网络能够正常、安全、有效工作，必须删除这些被俘获节点。在已经建立的配对密钥基础上，设计恶意节点的删除方案，以保障网络的正常工作。整个删除过程由中继节点与管辖区内的感知节点协同合作实现。节点删除主要分三个阶段完成：初始化阶段、中继节点广播阶段以及配对密钥多项式的建立，过程如图3所示。

图3 节点删除过程

3.3.1 初始化阶段

当汇聚节点检测到被俘获节点的数目超过阈值nre时，便进入节点删除初始化阶段。假定一组需要删除的节点组R为{c1,…,cn}。首先，汇聚节点随机产生2个二元t次对称多项式f1(x,y)、f2(x,y)；其次，根据当前更新轮次号i，找到节点内预置的多项式pi,1(x)、pi,2(y)；中继节点生成多项式g1(x)、g2(y)分 别为：

且{IDc1,…,IDcn}为节点组R内各节点的ID，随后进入广播阶段。

3.3.2 广播阶段

汇聚节点向网络中其他节点发送广播删除命令，从而删除区域内需要删除的节点。其中，SIDRN为中继节点RN的感知层ID，且有：

3.3.3 配对密钥多项式建立阶段

当非删除的节点UN收到汇聚节点广播的节点删除命令后，向邻居节点转播中继节点的节点删除命令。同时，节点UN通过汇聚节点的删除命令计算自己的配对密钥多项式，过程如下。

首先，计算多项式值p1´(IDUN,y)与p2´(IDUN,y)：

该感知节点UN的配对密钥多项式为：

普通节点可以通过上述多项式计算与同区域内其他节点的配对密钥。但是，对于已删除的节点，由于其ID代入多项式g1(x)、g2(y)结果均为0，因此无法计算原同区域内节点间的配对密钥，从而实现对区域内指定节点的删除。

3.4 组广播密钥动态管理

传感器节点经常需要向其邻居节点广播信息以及与特定的组成员进行通信。虽然这些应用可以通过与各邻居间的配对密钥一一完成，但会造成节点能量、通信信道以及时间上的浪费。因此，为感知节点建立广播密钥十分必要。本文在已经建立的配对密钥基础上，设计节点组广播密钥的建立及动态管理方案。

邻居节点间广播密钥的建立：当节点完成配对密钥多项式的分配后，便进入广播密钥的建立阶段。在分配配对密钥多项式的过程中，网络中任意节点Ne可以保存其邻居节点ID到表NEINr中。广播密钥建立流程如下：

（1）首先节点Ne随机生成正整数n和与其所有邻居节点的配对密钥{KNr&N1,…,KNr&Ni}。

（2）节点Ne对与其邻居节点的配对密钥分别求哈希值{h(KNr&N1),…,h(KNr&Ni)}。

（3）计算邻居节点广播密钥BKr=n⊕ h(KNr&N1)⊕…⊕h(KNr&Ni)。

（4）分别为每个邻居节点计算BKj´|j=1,…,i值。其中，BKj´=BKr⊕h(KNr&Nj)，并向邻居发送广播密钥建立请求信息。

（5）当邻居节点收到节点Ne的广播密钥建立请求后，计算与节点邻居节点Ne的配对密钥KNj&Nr，并计算出配对密钥的哈希值h(KNj&Nr)，从广播信息中获取BKj´，建立邻居节点Ne的广播密钥BKr=BKj´⊕h(KNj&Nr)。

4 仿真验证

通过使用OPNET Modeler网络模拟仿真平台上采集到的数据，对PDKM的连通性、节点开销、抗俘获性以及动态性分别进行分析，并与已有的密钥管理方案进行比较。

4.1 连通性

网络中节点的连通性分为两类：局部连通性与全局连通性。

4.1.1 局部连通性

局部连通性是指网络中每个节点与邻居节点间可以直接建立配对密钥的概率。在无线传感器网络中，确保节点可以与邻居节点建立配对密钥是密钥管理方案设计中的一个重要方面。而现有的基于随机密钥预分配的密钥管理方案中，由于采用了分布式平面网络结构，节点通过预置的共享密钥建立配对密钥。由于每个节点中的预置密钥为密钥池的一个子集，为了保证整个网络的健壮性，任意两节点间有相同的预置密钥的概率始终远小于1，且此概率随着预置密钥的数目的增加而增加，但安全性随之降低。

本方案中，网络中各节点使用自己以及对方的ID通过对称多项式建立配对密钥，因此只要知道同区域中对方的ID，均可计算出相应的配对密钥，网络的局部连通率为1。而随机密钥预分配方案（E-G方案）的局部连通率与节点内预置的密钥数量有关，连通率为1-((S-k)!)2/((S-2k)!S!)[3]，其中S为密钥池的大小，k为节点内预置密钥的数量；q-Composite随机密钥预分配方案由于两节点间的共享密钥大于等于q时，才可建立通信。因此，当q=1时，此方案连通率与E-G方案相同；当q＞1时，节点间的其中S为密钥池数目，m为节点内部署的节点数。网络中节点的局部连通率随着内置密钥数量的增加而增加，但同时网络的安全性随着节点预置密钥数量的增加而降低。节点预置密钥的数量与网络局部连通率的关系图如图4所示。

图4 网络的局部连通性

由图4可知，其他基于随机密钥预分配的密钥管理方案随着预置密钥信息的增加，网络的局部连通率逐渐增加。随着节点预置密钥数逐渐趋近于密钥池大小，网络的局部连通率逐渐趋近于1；而本协议在预置基本信息后，网络的局部连通率一直为1。因此，本协议在局部连通率方面优势明显。

4.1.2 全局连通性

全局连通性是指网络中任意两节点之间建立安全通信密钥的概率。在传感器网络中，覆盖控制、连通控制以及路由寻找等操作对网络的正常有效运行非常重要。而当网络在执行覆盖控制、连通控制以及路由寻找等控制操作时，网络中的节点都需要与同区域内其他非邻居节点进行通信。因此，全局连通性也是无线传感器网络密钥管理方案一个非常重要的性能指标。

与局部连通性类似，本方案采用二元对称多项式生成配对密钥，每个节点在预置了基本信息后，在获知同区域内需要建立配对密钥的节点ID的前提下，可与其建立配对密钥，因此整个网络的全局连通率恒为1。而对于其他基于随机密钥预分配的密钥管理方案[9-11]，网络的全局连通率与局部连通率相等，且恒小于1，且随着预置密钥信息的数量无限接近于1，网络中节点的抗俘获性急剧下降。连通率为

4.2 通信开销

密钥管理过程中节点的开销主要包括密钥分配更新过程中的通信开销和计算开销。从表2可知，节点通信开销占到能量总开销的98%[12]，且文献[13]指出，节点每发送1 bit的能量消耗与执行100条指令的能耗相当，因此减小密钥管理的通信开销对延长网络工作寿命有着重要作用。

表2 无线传感器网络各模块能量损耗比例

假定每个感知节点隶属于一个中继节点。本方案中的通信开销主要包括三个部分——配对密钥多项式的分配、配对密钥的建立以及配对密钥的更新。在配对密钥多项式的分配阶段，每个节点转发nst+1个广播数据包，包的大小为(t+t´)2×32 bit；在配对密钥建立阶段，节点不需要任何信息发送，就可建立配对密钥，通信开销为0；密钥更新时，通信开销为(t+t´)2×32 bit。文献[8]中提出的基于随机预分配的方案，假定整个网络的连通率为80%，初始化阶段通信开销为0，每个节点与邻居节点建立密钥的通信开销为：

其中p´为两节点的连通率，ns为每个节点预置的密钥个数，Sb为通信包的大小。图5给出了各节点在p´分别为80%、90%、95%、98%时的通信 开销。

图5 网络连通率与通信开销

4.3 网络扩展性

随着网络工作时间的推移，网络中需要新加入一些节点以保证网络的正常工作。而PDKM允许用户按照应用需要为网络增加新的节点，且节点的增加过程中使用了中继节点认证与汇聚节点认证的双层认证机制，保证网络中所添加的节点是用户所增加的节点而非恶意节点。而对于E-G等方案，虽然网络可以支持新节点的加入，但在节点增加过程中，每个节点像网络初始化时为每个节点预置密钥信息，并通过向邻居节点发送请求加入网络，但这些方案中的节点增加过程均无认证功能，即恶意节点有可能冒充新增节点向邻居节点发送请求，从而达到窃听网络信息或DoS攻击等。因此，PDKM的扩展性要明显优于文献[4，10-11]中提出的密钥管理方案。

4.4 抗攻击性

节点被恶意俘获是传感器网络面临的安全问题，因为恶意俘获不仅会破坏节点的正常工作，而且会读取节点中的一些信息，对网络的安全性产生极大危害。因此，抗俘获性是判定传感器网络密钥管理性能的一个非常重要的标识。

文献[7]提出，对于基于t次二元对称多项的密钥管理方案中，恶意节点可能通过俘获节点获得节点中生成的配对密钥多项式。通过反向计算，计算网络中的配对密钥多项式，从而达到对整个密钥管理系统的破解。当俘获的节点数小于t+1时，这些被获取的配对密钥多项式对网络的密钥管理不会产生任何威胁，网络可以正常工作；而当获得的配对密钥多项式大于t+1时，即t+1个正常节点中的一元配对密钥多项式被敌方获后，可能通过这些配对密钥多项式计算整个网络中生成配对密钥所用的二元对称多项式，从而使整个网络配对密钥管理崩溃，导致整个网络无法正常工作。因此，使用的二元多项式的次数越高，网络的抗俘获越好，安全性越高，但节点的存储开销及配对密钥多项式分配、更新时的通信开销也随之增大。图6给出了PDKM协议在抗攻击性方面与其他密钥管理方案的比较 示意图。

图6 被俘获节点比率与网络安全连通受损率

PDKM协议适用于网络规模较小的传感器网络。当汇聚节点检测到被俘获的节点数超过设定阀值时，就更新整个网络密钥系统，从而保证密钥管理系统的安全性，且节点的更新开销非常小。由于生成配对密钥的二元对称多项式由中继节点随机生成的对称多项式部分以及中继节点预置的一元多项式组两部分组成，当敌方俘获中继节点后，只能获取中继节点随机生成的对称多项式部分，无法获取预置的多项式组，因此同样无法获取感知节点的配对密钥多项式，且每个感知节点都有备用的中继节点，因此中继节点的俘获对网络的正常工作不会产生很大影响。

4.5 动态性

动态性是指网络中节点间的密钥能否进行动态更新。PDKM以较小的计算及通信开销进行节点密钥的动态更新。当被俘获的节点数超过t+2t´或更新时间间隔到达后，中继节点便会对其所管辖的感知节点进行密钥更新。本协议中的密钥更新同时具备前向安全性与后向安全性，即使在一段时间内密钥管理被破解，但是当网络更新密钥后，整个网络的密钥管理将重新恢复安全。此外，更新密钥使用的多项式值随着更新而不断更换，可保障网络密钥管理系统更新的安全、有效性。

同时，本方案配合外来入侵系统使用。当监测到网络中被俘获节点超过俘获阈值t+t´后，便删除监测到的被俘获节点；且当需要加入新节点时，每个节点预置最新用于配对密钥多项式更新的多项式值组，从而保障网络的密钥管理的安全性不会随着网络工作的进行而降低。但是，对于E-G等方案，这些节点的配对密钥无法进行更新，随着网络工作的进行，一些节点被俘获，其内预置的密钥环会被敌方获得，网络的安全性随着工作的进行而逐渐降低；网络中新增加节点预置的密钥环有可能已经被敌方所获知，从而使得一些节点一进入网络便无法正常工作；即使服务喊叫获得一些已被俘获节点的信息，也无法将这些节点删除，整个网络的安全性会随着工作的进行越来越差，最终导致整个网络无法正常工作而彻底崩溃。

5 结 语

根据无线传感器网络的特点，基于二元对称多项式的性质，提出了无需交互的密钥动态管理方案PDKM，有效减少了节点的通信开销，提高了网络的工作寿命。PDKM同时支持密钥的动态更新、组广播密钥的建立和指定节点的删除等。仿真结果表明：PDKM密钥管理方案在通信开销、抗毁性以及动态性方面具有较大优势。