一種基于橢圓曲線的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