基于批处理验证的异构无线传感器网络认证协议*

单 洪，马 涛

(解放军电子工程学院网络工程系，合肥 230037)

SHAN Hong*，MA Tao

(Department of Network Engineering，Electronic Engineering Institute，Hefei 230037，China)

认证机制是异构无线传感器网络安全机制的核心与重要基础环节，安全、高效、低能耗地实现认证，始终是无线传感器网络安全研究领域的热点［1-2］。目前无线传感器网络的认证协议都是针对同构网络的，还没有适应网络异构特性的认证协议。随着传感器节点能力的不断提高，一些计算量较小的公钥加密算法可以应用于无线传感器网络的认证机制设计中，但是数字签名验证所耗费的大量计算资源仍然是阻碍公钥加密算法在传感器网络中广泛应用的关键问题［3-4］。如何高效地完成数字签名的验证是异构无线传感器网络认证协议设计的核心问题之一。

1 认证协议设计

异构无线传感器网络初始化时每个节点，包括汇聚节点(Sink)、高级节点(H-Sensor)和各类普通节点(L-Sensor)从可信服务器处获得各自的公钥私钥对(Qi，xi)。传感器节点发送需要认证的消息时首先用私钥xi生成消息m的 ECDSA［5］签名(R，σ)，然后将消息及其签名发送给目的节点。由于使用协议的不同，一些消息可能对响应时间有较高的要求，目的节点在接收消息后需要立刻进行验证，并将验证结果返回给发送节点。因此，基于批处理验证的消息认证协议根据响应要求将消息划分为高和低两种不同的优先级。如果节点收到低响应要求的消息，首先判断是否达到批处理验证的门限值Th，达到则进行批处理验证，否则存储该消息;如果节点接收到高响应要求的消息，立即进行批处理验证;在上一轮验证完成后的时间间隔Tb内，即使消息数目没有达到批处理验证的门限值，同样需要对节点存储的消息进行批处理验证。批处理验证包括三个阶段:子组划分、组随机数生成和签名验证。

1.1 子组划分阶段

子组划分阶段的主要任务是将需要进行批处理验证的消息及其签名划分为子组，用于后面的批处理验证。传感器节点选择子组大小为d，需要进行批处理验证的n个消息及其签名为{(m1，R1，σ1)，(m2，R2，σ2)，…，(mn，Rn，σn)}，如果n/d为整数，则将n个消息及其签名划分为n/d个子组，每个子组包括d个元素;否则划分为⎿n/d」+1个子组，前⎿n/d」个子组包括d个元素，最后一个子组包括n-d×⎿n/d」个元素。

1.2 随机数向量组生成阶段

随机数向量组生成阶段负责生成各个子组内签名进行批处理验证时需要的联合稀疏系数，该系数是一个随机数向量组S，S是由元素{0，1，-1}组成的矩阵，每一行作为一个签名分量Ri的系数，共有x行，x为子组中元素的数目，S由非全零列(列中元素不全为0)与全零列(列中元素全为0)组成［6］。

其中为第i个子组的第j个随机数向量，N(，…)为S的非全零列数目。节点根据参数值以及子组内元素数目x为每个子组产生符合生成条件的随机数向量组，首先生成不大于k个非全零列，然后根据不同的节点类型选择不同的替换比例η，选取t个全零列，替换S中的非全零列，从而生成符合传感器节点资源要求的随机数向量组，全零列占所有列数的比例应该不大于η。

1.3 签名验证阶段

签名验证阶段传感器节点根据上一阶段生成的随机数向量组验证每个子组的消息及数字签名{(m1，R1，σ1)，(m2，R2，σ2)，…，(mx，Rx，σx)}，这需要验证

图1 协议流程

2 性能分析

在相同的错误概率时，k的取值要远远小于l的取值，这样就能够大幅度降低批处理验证时的多标量乘运算。随着x的不断增大，虽然k的取值有一定幅度的减少，但是减少的幅度不大。

表1给出了椭圆曲线在Inverted Edwards坐标［9］表示下，原始方案、小指数方案、稀疏指数方案和联合稀疏系数方案验证n个数字签名的计算量。在该坐标系下，椭圆曲线上的点加、倍乘和三倍乘所需运算分别为8M+1Sq、3M+4Sq和9M+4Sq，其中M表示椭圆曲线基域上的乘法运算，Sq表示椭圆曲线上的乘方运算。椭圆曲线的阶为p，(⎿logp」=192)，小指数方案中参数l的取值为80，稀疏指数方案中Hamming重量不大于18，本文提出的联合稀疏系数方案中设子组内元素数量x=3，则非全零列的个数q≤k，k=18。为简化分析过程，分析时没有考虑用全零列替换非全零列的情况。

表1 各类方案计算量 单位:M

签名验证时需要对消息进行H(mi)运算，该运算与椭圆曲线上的运算相比计算量很小，分析时可以忽略不计。假设节点验证n个数字签名，则原始方案需要分别验证每个数字签名，小指数方案、稀疏指数方案和联合稀疏系数方案同时验证n个数字签名，所需计算量如下所示，其中A表示点加运算，SM(i)表示标量系数为i位的多标量乘运算计算量。

原始方案n(1I+2M+2SM(192)+1A)

小指数方案n(1I+2M)+2SM(192)+1A+n×SM(80)+(n-1)A

稀疏指数方案n(1I+2M)+2SM(192)+1A+n×SM(192)+(n-1)A

由表1可知，采用联合稀疏系数方案进行数字签名的批处理验证与其它方案相比所需计算量最少，效率最高，这是因为联合稀疏系数方案中的标量系数长度较小，同时其非全零列数目也较低，因此验证过程中的倍乘与点加运算数量大大减少。

3 仿真实验

采用QualNet进行仿真实验，1 500 m×1 500 m的仿真场景内随机放置1个Sink、20个H-Sensor和1024个3种类型的L-Sensor(L1、L2、L3)。不同类型的传感器节点选择不同的验证参数，包括门限值、子组大小、全零列比例等。具体参数设置如表2所示。

表2 仿真参数设置

图2给出了网络中3种类型的L-Sensor数目相等，每个L-Sensor都选取η=0.1全零列替换比例的情况下，传感器节点验证签名数目和平均验证时间消耗的关系。由图中可以看出，传感器节点采用联合稀疏系数方案的平均数字签名验证时间消耗要远远小于其他方案的时间消耗。该方案利用批处理方式同时验证一批数字签名，而且验证时所需的计算量也比较小，因此其时间消耗在所有方案中是最小的。当传感器节点验证20个消息及其数字签名时，联合稀疏系数方案的时间消耗分别是原始方案、小指数方案和稀疏指数方案的11.3%、41.1%和15.1%。

图2 传感器节点验证数字签名平均时间消耗

图3给出了网络中3种类型的L-Sensor数目相等，每个L-Sensor都选取η=0.1全零列替换比例的情况下，传感器节点验证签名数目和平均验证能量消耗之间的关系。由图3可知，提出的批处理验证方法大大提高了异构无线传感器网络数字签名验证的效率，有效地降低了节点验证数字签名的能量消耗。采用联合稀疏系数方法进行批处理验证时有效地减少了标量系数的长度并优化了组成结构，因此其能量消耗要小于其他方案。

图3 传感器节点验证数字签名平均能量消耗

图4给出了网络中传感器节点验证20个数字签名，L1和L2数目相等，选取η=0.1时，L3节点数目和平均验证能量消耗之间的关系。由图中可以看出，随着L3节点数目不断增加，平均验证能量消耗也随之增大。这是因为L3节点的数字签名门限值较小，验证时的计算量要大于L1和L2的计算量，因此平均验证能量消耗随着L3节点数目的增加而增大。如果不考虑L-Sensor节点之间的异构性，将所有L-Sensor的门限值都设定为3时，则传感器节点验证数字签名平均能量消耗要大于考虑L-Sensor节点之间异构性的情况(L1、L2和L3设定不同的门限值)。

图4 L-Sensor验证数字签名平均时间消耗比较

图5给出了网络中 L1、L2和 L3数目相等，L1、L2和 L3分别选取 η1=0.1，η2=0.2，η3=0.3 全零列替换比例的情况下，3种类型L-Sensor的平均数字签名验证时间消耗的比较。由图可知L1、L2和L3这3种类型的时间消耗虽然存在一定的差距，但是相差不是很大。这主要是因为虽然L1的门限值较大，减少了一部分验证的计算量，但是L2和L3的全零列比例比L1大，降低了多标量乘运算中的点加运算次数，因此其计算量也会相应的减少。

图5 传感器节点验证数字签名平均能量消耗

图6给出了网络中3种类型的L-Sensor数目相等，每个L-Sensor都选取η=0.1全零列替换比例的情况下，各种方案检测出伪造或虚假签名的平均时间消耗。由图可知，联合稀疏系数方案的时间消耗最小，随着伪造或虚假签名的比例不断增大，所有方案的时间消耗都随之增加，联合稀疏系数方案的增加幅度最小，这是因为其采用了批处理验证的方法，每个小子集的验证都运用该方法进行优化，从而使得整个检测的扩展性较好。

图6 检测伪造或虚假签名的平均时间消耗

4 结论

理论分析与仿真实验表明该协议验证所需计算量较小，具有良好的可扩展性与安全性，有效地降低了数字签名验证的时间和能量消耗。但协议设计时主要考虑了数字签名验证的优化策略，而没有涉及签名过程的优化。接下来还需要进一步完善该认证协议，使得基于椭圆曲线的公钥加密算法能够在异构无线传感器网络中更加广泛地应用。

［1］王丽娜，施德军，覃伯平，等.基于Merkle散列树的无线传感器网络实体认证协议［J］.传感技术学报，2007，20(6):1338-1343.

［2］王建萍，李明，周贤伟.基于声誉和信任组的无线传感器网络实体认证研究［J］.传感技术学报，2008，21(10):1780-1784.

［3］王刚，温涛，郭权，等.WSN中基于身份的高效多播认证协议［J］.通信学报，2009，30(6):64-69.

［4］庞辽军，焦李成，王育民.无线传感器网络节点间认证及密钥协商协议［J］.传感技术学报，2008，8(21):1422-1426.

［5］Seog Chung Seo，Hyung Chan Kim，Ramakrishna R S.A New Security Protocol Based on Elliptic Curve Cryptosystems for Securing Wireless Sensor Networks［J］.Lecture Notes in Computer Science，2006，4097:291-301.

［6］An Liu，Peng Ning.TinyECC:A Configurable Library for Elliptic Curve Cryptography in Wireless Sensor Networks［C］//Proceedings of the 7th International Conference on Information Processing in Sensor Networks，2008:245-256.

［7］Don B Johnson，Alfred J Menezes，Scott Vanstone.Elliptic Curve Digital Signature Algorithm［Z/OL］.http://www.certicom.com/resources/download/ecdsa.ps.

［8］Jung Hee Cheon，Dong Hoon Lee.Use of Sparse and/or Complex Exponents in Batch Verification of Exponentiations［J］.IEEE Transactions on Computers，2006，55(12):1536-1542.

［9］Daniel J.Bernstein，Tanja Lange.Inverted Edwards Coordinates［C］//17th Applied Algebra，Algebraic Algorithms，and Error Correcting Codes Symposium，2007.