基于漢明距離的無線傳感器網絡密鑰預分配方案

（1.中國地質大學 計算機學院 武漢 430074; 2.武漢郵電科學研究院 虹信技術有限責任公司 新一代光纖通信技術和網絡國家重點實驗室 武漢 430074）

摘 要：無線傳感器網絡自身的特征，如網絡規模龐大，動態的拓撲結構，有限的計算、通信和存儲能力等，使得傳統的密鑰分配和管理機制無法直接應用。基于漢明距離提出了一種新的適用于無線傳感器網絡的密鑰預分配方案。該方案將對稱密鑰系統和非對稱密鑰系統結合起來，并借助漢明距離的概念在無線傳感器網絡中實現了密鑰的分配和管理。與隨機密鑰預分配方案相比，本方案在健壯性和安全性方面具有一定的優勢，其計算和存儲開銷也不大，具有一定的實用性。

關鍵詞：漢明距離； 網絡安全； 密鑰預分配； 無線傳感器網絡

中圖分類號：TP393文獻標志碼：A

文章編號：1001-3695(2009)05-1932-03

Key predistribution scheme using Hamming distance for WSN

ZHANG Li-ping1 YU Zhi-gang2

(1. College of Computer Science Technology China University of Geosciences Wuhan 430074 China; 2.State Key Laboratory for New Optical Communication Technologies Networks Hongxin Telecommunication Tachnologies Co.，LTD，Wuhan Research Institute of Posts Telecommunication Wuhan 430074 China)

Abstract:Providing a suitable key establishment scheme in wireless sensor networks is challenging due to all the characteristics of these networks such as dynamically changing topology and limitations of power computation capability and storage resources. This paper presented a key pre-distribution scheme using Hamming distance which was suitable for wireless sensor networks. In this scheme Hamming distance asymmetric and symmetric cryptography were employed to achieve key pre-distribution and exchange in wireless sensor networks. The proposed key predistribution scheme has advantages over random key predistribution scheme in its security and only spends moderate computation cost so it is quite practical.

Key words：Hamming distance; network security; key pre-distribution; wireless sensor network(WSN)

0 引言

無線傳感器網絡由大量功能相同或不同的無線傳感器節點組成，其目的是協作地感知、采集和處理其覆蓋區域中被感知對象的信息，發送給使用者^[1]。與傳統的無線計算機網絡相比，無線傳感器網絡具有其自身的特點：網絡規模龐大；拓撲結構變化快；節點由電池供電，計算能力和通信能力有限。無線傳感器網絡自身的特點使其安全性面臨嚴峻挑戰。密鑰管理機制則是構建安全的無線傳感器網絡的核心技術。由于無線傳感器網絡中所有節點都是對等的，沒有認證中心。此外，其節點的計算、通信和存儲能力也都非常有限。一些傳統的密鑰管理方案，如局部分布式認證授權方案、完全分布式認證授權方案、自發證書方案等，都不能應用于無線傳感器網絡。因此，研究者們針對無線傳感器網絡的特點，對其密鑰分配和管理進行了深入的研究，提出了一些新的密鑰管理方案^[2~4]。

Eschenauer等人^[2]提出了一種基于概率的隨機密鑰預分配方案。在此基礎上Pietro等人^[3]給出了一種新的隨機密鑰預分配方案。該方法的缺點在于只能在概率p的條件下找到共有的密鑰，不能保證每對通信節點都擁有共享密鑰。Chan等人^[4]對該方法進行了改進，提出了q-composite隨機密鑰預分配方案，在該方案中由于每對通信節點能夠共有q個密鑰，從而增強了網絡的安全性，但該方案無法實現鄰居節點的身份認證。以上的這些方案都需要有一個密鑰預分配過程。顯然，這不利于節點的加入和替換，也增加了存儲開銷。

本文提出了一種新的密鑰預分配方案。該方案利用漢明距離的概念來決定哪些節點之間需要建立共享會話密鑰，并采用橢圓曲線Diffie-Hellman算法和IBE算法共同完成節點間的密鑰協商。然后，再利用協商好的對稱密鑰實現信息的安全傳輸。漢明距離概念的引入以及對稱密鑰與非對稱密鑰的混合使用增加了方案的安全性，降低了節點的存儲和計算開銷，使該方案適用于無線傳感器網絡。

1 預備知識

1.1 漢明距離的基本概念

定義1 設節點a和b的ID分別為aID∈Zn和bID∈Zn，則aID和bID之間的漢明距離定義為HD(a，b)或HD。

定義2 若節點a與x滿足條件HD(a，x)=1，則節點a存儲并管理與x之間的共享密鑰，并定義節點a為x的父節點(PN) x為a的子節點(CN)。

定理1 對給定的a∈Zn，定義Ra={x∈Zn｜HD(a，x)=1}，則｜Ra｜=log2N。其中：Zn={0，1，…，N-1}，N=2m，m＞0^[5]。

無線傳感器網絡中的每個節點都分配一個惟一的ID，并通過在漢明距離中使用節點的ID來構建節點間的內部聯系。例如，與ID=“000”的節點之間的漢明距離為1的節點總數為log28=3個，分別是ID=“001”“010”和“100”的節點。由定理1知，R000={“001”，“010”，“100”}。

1.2 IBE算法

Boneh-Franklin的IBE算法主要包括四個函數：Setup用來完成系統參數的建立；Extract函數用于密鑰的提取；Encrypt和decrypt函數則分別提供加密和解密功能。具體算法如下：

a)Setup：輸入一個安全參數k。

（a）產生一個k位的素數q，以及兩個q階群G1 和G2，選取一個生成元p∈G1，構造一個雙線性映射e^:G1×G1→G2。

（b）隨機選取s∈Zp，計算Ppub=sP。

（c）選擇hash函數H1:{0，1}→G1，H2:G2→{0，1}n，H3:{0，1}n×{0，1}n→Zp，H4:{0，1}n→{0，1}n。

系統的明文空間為M={0，1}n，密文空間為C=G1×{0，1}n×{0，1}n，輸出的系統參數為π={q，G1，G2，e^，n，P，Ppub，H1，H2，H3，H4}，s∈Zq為主密鑰。

b)Extract：對給定的任意一個字符串ID∈{0，1}，生成密鑰。

（a）計算QID=H1(ID)∈G1；

（b）取密鑰為dID=sQID。

c)Encrypt：使用公鑰ID對明文M∈(0，1)n進行加密。

（a）計算QID=H1(ID)；

（b）隨機選取σ∈{0，1}n；

（c）計算r=H3(σ，M)；

（d）加密密文C=〈rP，σH2(grID)，MH4(σ)〉，其中gID=e^(QID，Ppub)∈G2。

d)Decrypt：設C=〈U，V，W〉為密文，如果UG1放棄密文，解密步驟為：

（a）計算VH2(e^(dID，U))=σ；

（b）計算WH4(σ)=M；

（c）計算r=H3(σ，M)，如果U≠rP，放棄密文，否則返回明文M。

IBE算法的安全性是基于Diffie-Hellman問題復雜性的，該算法被證明是IND-ID-CCA安全的^[6]。

2 基于漢明距離的密鑰預分配方案

基于漢明距離的密鑰預分配方案中所使用到的符號的說明如表1所示。

方案的基本思想：首先，對無線傳感器網絡中的每個節點ui，構建集合Rui；然后，ui與Rui集合中相對應的每一個節點之間建立它們的共享密鑰（集合Rui中相對應的每個節點表示集合Rui中每個ID所對應的節點）；最后，構建安全的通信路徑，實現信息的安全傳輸。具體步驟如下：

a)初始化過程。采用一個離線的管理系統負責節點的初始化操作。

（a）為無線傳感器網絡中的每一個節點分配一個惟一的ID作為其身份標志，其中ID∈{0，1，…，N-1}。

（b）運行IBE算法中的setup函數，獲取系統參數π和主密鑰s。

（c）運行IBE算法中的extract函數，得到與節點ID相應的密鑰dID。

（d）將系統參數π、節點ID以及相應的密鑰分配到相對應的節點中，完成節點的初始化操作。

b)每個節點ui構建集合Rui。對無線傳感器網絡中的每一個節點ui，計算與其漢明距離為1的節點ID，構建集合Rui，并存儲該集合Rui。由定理1，節點ui需要存儲log2N個節點的ID值。

c)每個節點ui與集合Rui中相對應的每個節點進行密鑰協商。

（a）節點ui向集合Rui中相對應的所有節點廣播其自己的身份標志IDui，集合Rui中相對應的所有節點獲取節點ui的身份標志IDui。

（b）節點ui與集合Rui中相對應的每個節點（記為vj）進行密鑰協商，建立共享會話密鑰Kui，vj。如圖1所示，具體操作如下：

①節點vj隨機選取一個整數rvj∈(0，q)作為其私鑰，計算公鑰rvjP；然后，采用encrypt函數，使用節點ui的身份標志IDui對節點vj的公鑰rvjP和其身份標志IDvj進行加密，并將加密后的信息發送給節點ui。

②節點ui接收到節點vj發送的信息后，采用decrypt函數進行解密，獲取節點vj的公鑰rvjP和身份標志IDvj。節點ui隨機選取一個整數rui∈(0，q)作為其私鑰，計算公鑰ruiP。然后，應用encrypt函數，使用節點vj的身份標志IDvj對節點ui的公鑰ruiP進行加密，并發送給節點vj。最后，節點ui計算ruirvjP作為它與節點vj共同協商的會話密鑰Kui，vj=ruirvjP。

③節點vj收到節點ui發送的信息后，應用decrypt函數進行解密，獲取節點ui的公鑰ruiP，并計算rvjruiP作為它與節點ui共同協商的會話密鑰Kvj，ui=rvjruiP。

d)構建安全的通信路徑，采用對稱密鑰算法進行數據的加/解密。

（a）在兩個需要進行信息傳輸的節點之間，應用漢明距離構建安全的通信路徑。

（b）采用對稱密鑰和對稱密鑰算法（如DES算法）在安全通信路徑上進行信息傳輸。

舉例，設無線傳感器網絡中節點總數N=8。此時，節點u001要與節點u111進行通信。如圖2所示，節點u001與u111之間存在六條通信路徑，采用安全路徑選擇算法^[5]快速地獲取安全通信路徑u001→u011→u111。節點u001用它與節點u001之間的共享會話密鑰Ku001，u011加密信息M，發送給節點u011。節點u011對接收到的消息進行解密后，用它與節點u111之間的共享會話密鑰Ku011，u111對解密后的信息進行加密，并發送給節點u111。最后節點u111用它與節點u011之間的會話密鑰Ku011，u111解密接收到的信息，獲取M。

當網絡中有節點退出時，安全通信路徑的建立則變成一個概率性問題。文獻[5]的實驗表明當節點退出率小于0.5時，成功建立安全通信路徑的概率大于0.979。此外，若兩個節點間不存在安全通信路徑，則可直接建立它們之間的共享密鑰。

3 安全性分析

本文提出的方案的安全性基于以下三方面：a）IBE算法的安全性；b）橢圓曲線離散對數問題（ECDLP）；c）對稱密鑰系統的安全性。 

基于漢明距離的密鑰預分配方案中的密鑰協商采用的是橢圓曲線Diffie-Hellman密鑰協商協議，該協議的安全性是基于橢圓曲線離散對數問題(ECDLP)的。因此，敵手在不知道密鑰協商雙方任何一方私鑰的情況下無法獲取所協商的會話密鑰。此外，密鑰協商過程中，采用IBE算法對傳輸的公鑰信息進行加密。由于IBE算法被證明是IND-ID-CCA安全的^[6]，從而保證了節點間信息傳輸的安全性。節點通信步驟中，信息傳輸過程的安全性是基于對稱密鑰系統安全性的。若采用的對稱密鑰算法能夠抵抗密文攻擊，則攻擊者無法獲取傳輸信息的內容，除非攻擊者能破解該對稱密鑰算法。

該方案中所產生的會話密鑰都是惟一的，與隨機密鑰分配算法相比避免了多對節點擁有相同的共享密鑰，從而增強了網絡的安全性。此外，由于會話密鑰的惟一性，當某個節點被破獲后，不會暴露其他節點之間的會話密鑰信息，不會威脅其它節點的安全，更不會影響全網的安全，從而保證了網絡的健壯性。而在隨機密鑰分配算法中，網絡的健壯性則是一個概率性問題 [7]。因此，本文的方案在健壯性方面與目前的隨機密鑰分配算法相比更具有優越性。

4 性能分析

1）內存開銷 每個節點ui需要保存的信息有IBE算法中需要用到的參數、集合Rui、log2N個共享密鑰。

2）算法復雜性 節點間的密鑰協商采用的是橢圓曲線Diffie-Hellman密鑰協商協議。在同樣安全強度下，與其他一些已知的密鑰協商協議（如Diffie-Hellman密鑰協商協議）相比，所需要的密鑰長度要少得多，計算開銷較小，密鑰帶寬也較小。此外，密鑰協商過程中用到的IBE算法，只在網絡拓撲結構形成時的會話密鑰建立過程中使用到。在沒有新節點加入且節點間存在安全通信路徑的情況下，一旦節點間建立好了會話密鑰，以后通信數據的加密采用的是對稱密鑰模式，不再需要應用IBE算法。另外，橢圓曲線類型的算法比通常的非對稱密鑰系統的計算代價要低，在安全性和復雜性方面具有一定優勢。

隨機密鑰分配方法中每對相鄰節點共享密鑰數與密鑰子空間維數和節點密鑰數相關。對維數1 000的密鑰子空間，每個節點存儲50個密鑰，存在共享密鑰的概率為0.9^[7]。密鑰發現過程中需要進行哈希函數運算、異或運算以及節點間的通信運算。因此，本文的方案與隨機密鑰分配方案相比，算法的復雜性處在同一層次。

5 結束語

無線傳感器網絡自身的特點使其安全機制面臨嚴峻挑戰。密鑰管理機制則是構建安全的無線傳感器網絡的核心技術。本文提出了一種基于漢明距離的無線傳感器網絡密鑰預分配方案，該方案將對稱和非對稱密鑰系統結合起來，充分利用了它們各自的優點，并借助漢明距離的概念實現了密鑰的分配和管理。它與隨機密鑰預分配方案相比，在計算和存儲方面開銷處在同一層次，在健壯性和安全性方面則具有一定的優勢。

參考文獻：

［1］ AKYILDIZ L F WEILIAN S SANKARASUBRAANIAM Y et al. A survey on sensor networks[J]. IEEE Communication Magazine 2002 40(8):102-114.

[2]ESCHENAUER L GLIGOR V D.A key-management scheme for distributed sensor networks[C]//Proc of the 9th ACM Conference on Computer and Communications Security. Washington DC:ACM Press 2002:41-47.

[3]PIETRO R D MANCINI L V ANDMEI A. Random key assignment for secure wireless sensor networks[C]//Proc of ACM Workshop on Security in Ad hoc and Sensor Networks(SASN’03) . Washington DC:ACM Press 2003:62-71.

[4]CHAN Hao-wen，PERRIG A SONG D. Random key pre-distribution schemes for sensor networks[C]//Proc of IEEE Symposium on Research in Security and Privacy. New York:IEEE Press 2003:197-213.

[5]LEE S L JEUN I K SONG J S. Mixed key management using Hamming distance for mobile Ad hoc networks[C]//Proc of ICCS’07. Berlin: Springer 2007:665-672.

[6]BONECH D FRANKLIN M. Identity-based encryption from the Weil pairing[C]//Advances in Cryptology-Crypto. Berlin:Springer 2001:213-229.

[7]楊庚，王江濤，程宏兵，等.基于身份加密的無線傳感器網絡密鑰分配方法[J].電子學報，2007 35（1）：180-184.