無線傳感網分布式密鑰分配方案綜述

是霖驍，吳 蒙

(南京郵電大學 計算機、軟件學院，江蘇 南京 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