基于批處理驗證的異構(gòu)無線傳感器網(wǎng)絡認證協(xié)議*

單 洪，馬 濤

(解放軍電子工程學院網(wǎng)絡工程系，合肥 230037)

SHAN Hong*，MA Tao

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

認證機制是異構(gòu)無線傳感器網(wǎng)絡安全機制的核心與重要基礎環(huán)節(jié)，安全、高效、低能耗地實現(xiàn)認證，始終是無線傳感器網(wǎng)絡安全研究領域的熱點［1-2］。目前無線傳感器網(wǎng)絡的認證協(xié)議都是針對同構(gòu)網(wǎng)絡的，還沒有適應網(wǎng)絡異構(gòu)特性的認證協(xié)議。隨著傳感器節(jié)點能力的不斷提高，一些計算量較小的公鑰加密算法可以應用于無線傳感器網(wǎng)絡的認證機制設計中，但是數(shù)字簽名驗證所耗費的大量計算資源仍然是阻礙公鑰加密算法在傳感器網(wǎng)絡中廣泛應用的關鍵問題［3-4］。如何高效地完成數(shù)字簽名的驗證是異構(gòu)無線傳感器網(wǎng)絡認證協(xié)議設計的核心問題之一。

1 認證協(xié)議設計

異構(gòu)無線傳感器網(wǎng)絡初始化時每個節(jié)點，包括匯聚節(jié)點(Sink)、高級節(jié)點(H-Sensor)和各類普通節(jié)點(L-Sensor)從可信服務器處獲得各自的公鑰私鑰對(Qi，xi)。傳感器節(jié)點發(fā)送需要認證的消息時首先用私鑰xi生成消息m的 ECDSA［5］簽名(R，σ)，然后將消息及其簽名發(fā)送給目的節(jié)點。由于使用協(xié)議的不同，一些消息可能對響應時間有較高的要求，目的節(jié)點在接收消息后需要立刻進行驗證，并將驗證結(jié)果返回給發(fā)送節(jié)點。因此，基于批處理驗證的消息認證協(xié)議根據(jù)響應要求將消息劃分為高和低兩種不同的優(yōu)先級。如果節(jié)點收到低響應要求的消息，首先判斷是否達到批處理驗證的門限值Th，達到則進行批處理驗證，否則存儲該消息;如果節(jié)點接收到高響應要求的消息，立即進行批處理驗證;在上一輪驗證完成后的時間間隔Tb內(nèi)，即使消息數(shù)目沒有達到批處理驗證的門限值，同樣需要對節(jié)點存儲的消息進行批處理驗證。批處理驗證包括三個階段:子組劃分、組隨機數(shù)生成和簽名驗證。

1.1 子組劃分階段

子組劃分階段的主要任務是將需要進行批處理驗證的消息及其簽名劃分為子組，用于后面的批處理驗證。傳感器節(jié)點選擇子組大小為d，需要進行批處理驗證的n個消息及其簽名為{(m1，R1，σ1)，(m2，R2，σ2)，…，(mn，Rn，σn)}，如果n/d為整數(shù)，則將n個消息及其簽名劃分為n/d個子組，每個子組包括d個元素;否則劃分為?n/d」+1個子組，前?n/d」個子組包括d個元素，最后一個子組包括n-d×?n/d」個元素。

1.2 隨機數(shù)向量組生成階段

隨機數(shù)向量組生成階段負責生成各個子組內(nèi)簽名進行批處理驗證時需要的聯(lián)合稀疏系數(shù)，該系數(shù)是一個隨機數(shù)向量組S，S是由元素{0，1，-1}組成的矩陣，每一行作為一個簽名分量Ri的系數(shù)，共有x行，x為子組中元素的數(shù)目，S由非全零列(列中元素不全為0)與全零列(列中元素全為0)組成［6］。

其中為第i個子組的第j個隨機數(shù)向量，N(，…)為S的非全零列數(shù)目。節(jié)點根據(jù)參數(shù)值以及子組內(nèi)元素數(shù)目x為每個子組產(chǎn)生符合生成條件的隨機數(shù)向量組，首先生成不大于k個非全零列，然后根據(jù)不同的節(jié)點類型選擇不同的替換比例η，選取t個全零列，替換S中的非全零列，從而生成符合傳感器節(jié)點資源要求的隨機數(shù)向量組，全零列占所有列數(shù)的比例應該不大于η。

1.3 簽名驗證階段

簽名驗證階段傳感器節(jié)點根據(jù)上一階段生成的隨機數(shù)向量組驗證每個子組的消息及數(shù)字簽名{(m1，R1，σ1)，(m2，R2，σ2)，…，(mx，Rx，σx)}，這需要驗證

圖1 協(xié)議流程

2 性能分析

在相同的錯誤概率時，k的取值要遠遠小于l的取值，這樣就能夠大幅度降低批處理驗證時的多標量乘運算。隨著x的不斷增大，雖然k的取值有一定幅度的減少，但是減少的幅度不大。

表1給出了橢圓曲線在Inverted Edwards坐標［9］表示下，原始方案、小指數(shù)方案、稀疏指數(shù)方案和聯(lián)合稀疏系數(shù)方案驗證n個數(shù)字簽名的計算量。在該坐標系下，橢圓曲線上的點加、倍乘和三倍乘所需運算分別為8M+1Sq、3M+4Sq和9M+4Sq，其中M表示橢圓曲線基域上的乘法運算，Sq表示橢圓曲線上的乘方運算。橢圓曲線的階為p，(?logp」=192)，小指數(shù)方案中參數(shù)l的取值為80，稀疏指數(shù)方案中Hamming重量不大于18，本文提出的聯(lián)合稀疏系數(shù)方案中設子組內(nèi)元素數(shù)量x=3，則非全零列的個數(shù)q≤k，k=18。為簡化分析過程，分析時沒有考慮用全零列替換非全零列的情況。

表1 各類方案計算量 單位:M

簽名驗證時需要對消息進行H(mi)運算，該運算與橢圓曲線上的運算相比計算量很小，分析時可以忽略不計。假設節(jié)點驗證n個數(shù)字簽名，則原始方案需要分別驗證每個數(shù)字簽名，小指數(shù)方案、稀疏指數(shù)方案和聯(lián)合稀疏系數(shù)方案同時驗證n個數(shù)字簽名，所需計算量如下所示，其中A表示點加運算，SM(i)表示標量系數(shù)為i位的多標量乘運算計算量。

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

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

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

由表1可知，采用聯(lián)合稀疏系數(shù)方案進行數(shù)字簽名的批處理驗證與其它方案相比所需計算量最少，效率最高，這是因為聯(lián)合稀疏系數(shù)方案中的標量系數(shù)長度較小，同時其非全零列數(shù)目也較低，因此驗證過程中的倍乘與點加運算數(shù)量大大減少。

3 仿真實驗

采用QualNet進行仿真實驗，1 500 m×1 500 m的仿真場景內(nèi)隨機放置1個Sink、20個H-Sensor和1024個3種類型的L-Sensor(L1、L2、L3)。不同類型的傳感器節(jié)點選擇不同的驗證參數(shù)，包括門限值、子組大小、全零列比例等。具體參數(shù)設置如表2所示。

表2 仿真參數(shù)設置

圖2給出了網(wǎng)絡中3種類型的L-Sensor數(shù)目相等，每個L-Sensor都選取η=0.1全零列替換比例的情況下，傳感器節(jié)點驗證簽名數(shù)目和平均驗證時間消耗的關系。由圖中可以看出，傳感器節(jié)點采用聯(lián)合稀疏系數(shù)方案的平均數(shù)字簽名驗證時間消耗要遠遠小于其他方案的時間消耗。該方案利用批處理方式同時驗證一批數(shù)字簽名，而且驗證時所需的計算量也比較小，因此其時間消耗在所有方案中是最小的。當傳感器節(jié)點驗證20個消息及其數(shù)字簽名時，聯(lián)合稀疏系數(shù)方案的時間消耗分別是原始方案、小指數(shù)方案和稀疏指數(shù)方案的11.3%、41.1%和15.1%。

圖2 傳感器節(jié)點驗證數(shù)字簽名平均時間消耗

圖3給出了網(wǎng)絡中3種類型的L-Sensor數(shù)目相等，每個L-Sensor都選取η=0.1全零列替換比例的情況下，傳感器節(jié)點驗證簽名數(shù)目和平均驗證能量消耗之間的關系。由圖3可知，提出的批處理驗證方法大大提高了異構(gòu)無線傳感器網(wǎng)絡數(shù)字簽名驗證的效率，有效地降低了節(jié)點驗證數(shù)字簽名的能量消耗。采用聯(lián)合稀疏系數(shù)方法進行批處理驗證時有效地減少了標量系數(shù)的長度并優(yōu)化了組成結(jié)構(gòu)，因此其能量消耗要小于其他方案。

圖3 傳感器節(jié)點驗證數(shù)字簽名平均能量消耗

圖4給出了網(wǎng)絡中傳感器節(jié)點驗證20個數(shù)字簽名，L1和L2數(shù)目相等，選取η=0.1時，L3節(jié)點數(shù)目和平均驗證能量消耗之間的關系。由圖中可以看出，隨著L3節(jié)點數(shù)目不斷增加，平均驗證能量消耗也隨之增大。這是因為L3節(jié)點的數(shù)字簽名門限值較小，驗證時的計算量要大于L1和L2的計算量，因此平均驗證能量消耗隨著L3節(jié)點數(shù)目的增加而增大。如果不考慮L-Sensor節(jié)點之間的異構(gòu)性，將所有L-Sensor的門限值都設定為3時，則傳感器節(jié)點驗證數(shù)字簽名平均能量消耗要大于考慮L-Sensor節(jié)點之間異構(gòu)性的情況(L1、L2和L3設定不同的門限值)。

圖4 L-Sensor驗證數(shù)字簽名平均時間消耗比較

圖5給出了網(wǎng)絡中 L1、L2和 L3數(shù)目相等，L1、L2和 L3分別選取 η1=0.1，η2=0.2，η3=0.3 全零列替換比例的情況下，3種類型L-Sensor的平均數(shù)字簽名驗證時間消耗的比較。由圖可知L1、L2和L3這3種類型的時間消耗雖然存在一定的差距，但是相差不是很大。這主要是因為雖然L1的門限值較大，減少了一部分驗證的計算量，但是L2和L3的全零列比例比L1大，降低了多標量乘運算中的點加運算次數(shù)，因此其計算量也會相應的減少。

圖5 傳感器節(jié)點驗證數(shù)字簽名平均能量消耗

圖6給出了網(wǎng)絡中3種類型的L-Sensor數(shù)目相等，每個L-Sensor都選取η=0.1全零列替換比例的情況下，各種方案檢測出偽造或虛假簽名的平均時間消耗。由圖可知，聯(lián)合稀疏系數(shù)方案的時間消耗最小，隨著偽造或虛假簽名的比例不斷增大，所有方案的時間消耗都隨之增加，聯(lián)合稀疏系數(shù)方案的增加幅度最小，這是因為其采用了批處理驗證的方法，每個小子集的驗證都運用該方法進行優(yōu)化，從而使得整個檢測的擴展性較好。

圖6 檢測偽造或虛假簽名的平均時間消耗

4 結(jié)論

理論分析與仿真實驗表明該協(xié)議驗證所需計算量較小，具有良好的可擴展性與安全性，有效地降低了數(shù)字簽名驗證的時間和能量消耗。但協(xié)議設計時主要考慮了數(shù)字簽名驗證的優(yōu)化策略，而沒有涉及簽名過程的優(yōu)化。接下來還需要進一步完善該認證協(xié)議，使得基于橢圓曲線的公鑰加密算法能夠在異構(gòu)無線傳感器網(wǎng)絡中更加廣泛地應用。

［1］王麗娜，施德軍，覃伯平，等.基于Merkle散列樹的無線傳感器網(wǎng)絡實體認證協(xié)議［J］.傳感技術學報，2007，20(6):1338-1343.

［2］王建萍，李明，周賢偉.基于聲譽和信任組的無線傳感器網(wǎng)絡實體認證研究［J］.傳感技術學報，2008，21(10):1780-1784.

［3］王剛，溫濤，郭權(quán)，等.WSN中基于身份的高效多播認證協(xié)議［J］.通信學報，2009，30(6):64-69.

［4］龐遼軍，焦李成，王育民.無線傳感器網(wǎng)絡節(jié)點間認證及密鑰協(xié)商協(xié)議［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.