用辛幾何構造傳感器的密鑰預分配方案

陳尚弟，文潔晶

（中國民航大學理學院，天津　300300）

?

用辛幾何構造傳感器的密鑰預分配方案

陳尚弟，文潔晶

（中國民航大學理學院，天津300300）

摘要：密鑰管理方案的設計是密碼學中基本且十分重要的研究領域。密鑰預分配是無線傳感器網絡中極具挑戰性的安全問題之一，目的是為無限傳感器網絡設計一個新的密鑰預分配方案。在借鑒Samiran Bag的密鑰預分配方案和有限關聯結構的基礎上，基于有限域上的四維辛幾何，獲得了一個新的無線傳感器網絡密鑰預分配方案。結果表明，本方案能夠有效地提高網絡的連通性，保證節點間均有共享密鑰，從而提高了節點間的連通率。分析表明，與其它一些已有的密鑰預分配方案相比，該方案具有良好的連通性和抗毀性。

關鍵詞：無線傳感器網絡；密鑰分配；密鑰預分配方案；辛幾何

近些年來，隨著傳感技術、計算機技術飛速發展與成熟，帶動了信息科學領域中的一個全新的發展方向——無線傳感器網絡，即具有感知能力、計算能力和通信能力的微型傳感器構成的網絡。該網絡在世界范圍內得到應用，是傳統學科與新興學科交叉的結果。因此由這些微型傳感器構成的無線傳感器網絡（wireless sensor network，W SN）引起了人們的極大關注。

無線傳感器網絡[1-2]是由大量體積小、成本低，具有感知能力、計算能力和通信能力的微型傳感器節點構成的自組織、分布式網絡系統。其目的是在感知、采集和處理網絡覆蓋的地理區域中協作地感知對象的信息，并發布給觀察者。可廣泛應用于軍事中地形偵察、環境與能源的監測、醫療衛生領域護理和監護、交通運輸中的管理和分派、日常生活中的智能居家、反恐斗爭中信息的采集和火災地震等諸多領域，具有巨大的實用價值和商業潛力，引起了國內外學術界廣泛與高度的關注。隨著無線傳感器應用的普及，傳感器網絡的安全[1]顯得日益重要，尤其是其中最基礎和最關鍵的密鑰管理問題。在傳統網絡中，密鑰的管理已有許多國內外的學者和研究人員進行了探索并取得了許多重要的成果，但由于無線傳感網絡自身固有的特點，如無線傳感網絡中無線傳感器的計算能力有限、可通信的物理范圍較小、存儲能力不強，缺乏節點部署的先驗知識等，使得這些成果不能直接應用于無線傳感網絡。因此，密鑰管理方案成為無線傳感器網絡安全的研究熱點與難點。

在無線傳感器網絡中，經過反復的探索與研究，通常使用的是對稱密碼體質與密鑰預分配機制實現安全的信息傳遞，在部署節點以前為其預分配若干密鑰（通常稱為密鑰鏈），部署后，如果不同節點之間需要安全通信，則其可以通過使用共享的密鑰來對信息加密，然后用同樣的密鑰對信息解密（如果沒有共享密鑰就需要建立密鑰路徑來實現安全通信）。目前已有很多無線傳感器網絡的密鑰預分配的研究，包括不確定型隨機分配密鑰方案、隨機型分配密鑰方案的擴展以及之后出現的許多基于組合結構的確定型的密鑰預分配方案，圍繞共享概率、密鑰路徑長度指標、支持的網絡規模、密鑰安全強度等指標進行了大量有階段性成果的工作。

由于無線傳感器網絡中節點的計算能力以及內存有限，所以公鑰密碼體制不適合無線傳感網絡（公鑰密碼體制在解密時計算量很大，消耗的能量和占有的內存也很大，故不適用于無線傳感網絡）。如果傳感網絡的每一個節點被分配N-1個密鑰（其中N為傳感網絡節點的個數），雖然保障了每一對通信的節點都有共享密鑰并且抗毀性與安全性達到最大，但是整個網絡的節點個數N很大以至于需要的內存很大，因此這個方案不適用于無線傳感器網絡。如果傳感網絡的每一個節點都分配同一個密鑰（即每一個節點分配一個密鑰），這樣雖然占用的內存最小，但是一個節點被捕獲那么整個網絡就不再安全，此方案的抗毀性及安全性太低，所以也不適用于傳感器網絡。Eschenauer L. 和Gligor V.[3]提出了密鑰預分配方案。無線傳感器的每一個節點在部署之前都分配給他們一些滿足其內存的密鑰，在通信的過程中他們彼此交換其密鑰的ID選取共同的密鑰，或者建立安全的通訊路徑來進行安全通信。

使網絡規模、節點內存及整個網絡的連通性、抗毀性和安全性彼此之間相互制約，沒有一個方案使他們都同時達到最大，所以近些年來許多學者都在探索和研究更好的密鑰預分配方案。

1　相關成果敘述

根據給節點分配密鑰方法的不同，無線傳感器網絡的密鑰預分配方案有以下兩種劃分，即概率不確定型密鑰預分配方案和基于組合結構的確定型密鑰預分配方案。

概率型密鑰預分配方案是一種基于求概率結果的密鑰預分配模型，計算任意兩個節點存在共享密鑰的概率，并且這個值高于一定概率，進而使得整個系統的密鑰共享圖構成以一個確定概率連通的連成圖。隨機密鑰預分配方案有以下兩種：

1）Eschenauer等[3]提出了基本的隨機密鑰預分配方案，目的是達到在確保任意節點之間含有共享密鑰的前提下，盡可能多的減少方案對節點資源的消耗。方案設計的具體過程如下：

a）密鑰分發從一個較大的密鑰空間選取一個密鑰池S，并為每個密鑰分配一個ID。在進行節點部署前，每個節點從密鑰池中隨機地選取k個密鑰構成自己的密鑰環，k大小的選擇要保證每兩個節點存在相同密鑰的概率p大于預先設定的概率值。

b）密鑰發現節點之間通信時，通過交換各自的ID來發現共享密鑰。

c）密鑰路徑的建立在b）不成功時，需要通過與其地理位置上相鄰節點經過若干次信息的傳遞建立一條間接連接兩個通信節點的安全路徑，然后進行安全通信。

在Eschenauer等[3]提出的隨機密鑰預分布模型方案中，兩個節點之間共享密鑰的概率p與密鑰池的大小S及密鑰鏈長度k之間的數學關系如下

2）在E-G方案的基礎上，Chan等[4]對E-G方案的安全性進行改進，提出了q-composite密鑰預分配方案，要求共享密鑰數為q（q>1），此時兩個節點之間共享密鑰的概率p與密鑰池的大小S及密鑰鏈的長度k之間的關系如下

確定型密鑰管理方案是節點的密鑰鏈以某種確定的方式來設計，避免了隨機型方案密鑰分配盲目性的一種密鑰預分配模型。通過合理組合結構可以設計的密鑰鏈，可以充分利用節點存儲空間，提高了節點之間直接通訊的概率。Camtepe等[5]首先將設計理論應用于確定型密鑰預分配方案的設計，給出了基于SBIBD和廣義四邊形的密鑰預分配方案，設計出的方案所含的節點數為n2+ n + 1，密鑰鏈長度為n + 1，并且保障了每對節點之間都共享一個密鑰，所得方案的連通概率比E-G方案更高，并且每個節點所含的密鑰更少（即密鑰鏈的長度更短）。Liu等[6]提出基于多項式的密鑰預分配方案，Lee等[7]提出了基于橫截設計的密鑰預分配方案等，這些模型雖然能夠有效建立密鑰路徑，實現安全通信，保證網絡的安全運行，但無線傳感器不同的節點間共享密鑰概率很低，通信中資源消耗太大。夏戈明[8]提出了一種基于Hamand矩陣與SBIBD設計的密鑰預分配方案，實現了對網絡的連通，并且在一定程度上優化了對能量的消耗，但是支持的網絡規模很小。

基于組合設計的確定性管理方案可以大幅度降低密鑰環的存儲空間，但大都存在構造困難、可擴展性問題。本文分為6個部分：①介紹了無線傳感網絡的實際應用背景及密鑰預分配方案問題的提出；②介紹了已有的一些相關結果；③介紹了本文用到的一些相關理論知識；④利用辛空間給出了密鑰預分配的組合方案，其中q是素數或素數的冪；⑤分析了所提出的方案，并與已有的方案進行安全性和連通性對比；⑥總結全文。

2　基礎知識

2.1有限關聯結構

通常用（P）表示與點P關聯的區組集，用（x）表示與區組x關聯的點集。因此（Pi）∩（P）j表示既與點Pi關聯又與點Pj關聯的區組集。通常以v表示點集的

對1≤i≤v，令ri表示中與點Pi關聯的區組數；1≤j≤b，令kj表示中與區組xj關聯的點的個數；對1≤i，j≤v，i≠j，令λi，j表示中同時與點Pi及Pj關聯的區組數。ri叫做點P的重復度，kj叫做區組xj的長度，λi，j叫做Pi與Pj的相遇數，即

上述定義出自文獻[9]。

2.2辛空間簡介

定義2設Fq是q元有限域，q是一個素數的冪。令

有限域Fq上滿足TKTT= K的2v×2v矩陣T的集合關于矩陣的乘法構成一個群，叫做Fq上的2v階辛群，記作Sp2v（Fq）。即

證明設P0也是（m，s）型子空間，因辛群Sp2v（Fq）可遷地作用在同類型的子空間集合上，不妨設

由假設知P與P0是同類型子空間，根據可遷性得知，存在使得P = AP0T，可推出P0T = A-1P。

證明設Q是與P正交的（m'，s'）型子空間，則Q?P⊥。由定理1知，P⊥是（2v-m，v+s-m）型子空間，即求包含在（2v-m，v+s-m）型子空間中的（m'，s'）型子空間的個數，即為N（m'，s'；2v-m，v+s-m；2v）。

上述定理定義出自文獻[10]。

3　密鑰預分配方案構造

給定素數q，在Fq上的四維辛幾何中選取包含一個固定一維子空間的二維子空間全體記為V。

參數的選擇如下：

密鑰鏈節點ni分配的密鑰為包含Pi的所有（3，1）型子空間。每一個ni對應一個Pi，無線傳感器網絡節點組成的集合{n1，n2，…，nM}與集合{P1，P2，…，PN}之間有一個單射。

上述關聯結構和密鑰預分配方案的對應關系如表1所示。

表1　密鑰預分配方案Tab.1 Key pre-distribution schem e

4　方案分析

無線傳感器網絡的密鑰管理方案必須具有連通性和安全性。下面對本文提出方案中的節點存儲能力及這兩個最重要的性能進行分析。

存儲要求下面先計算節點ni存儲的密鑰量。

引理2設節點ni= Pi，則包含Pi的（3，1）型子空間的個數為q + 1。

證明若Pi是（2，0）型子空間，則包含Pi的（3，1）型子空間的個數為N'（2，0；3，1；4）= q + 1。

若Pi是（2，1）型子空間，則包含Pi的（3，1）型子空間的個數為N'（2，1；3，1；4）= q + 1。因此，包含Pi的（3，1）型子空間的個數為q + 1。從上述引理可以得到：

定理3任意一個節點ni存儲的密鑰量為q+ 1。

下面計算任意兩個節點ni與nj共享的密鑰量。

引理3若Pi與Pj都是（2，0）型子空間，則是（3，1）型子空間。

又因Vi、V、Vj都是中的一維子空間，所以。否則Vi、V、Vj兩兩正交，則與最大迷向子空間是二維的相矛盾。即

引理4若Pi是（2，0）型子空間，Pj是（2，1）型子空間，則是（3，1）型子空間。

引理5若Pi與Pj都是（2，1）型子空間，則是（3，1）型子空間。

定理4任意兩個節點ni與nj的共享密鑰量為1。

證明由上述幾個引理可知，兩個節點所對應的子空間，則這兩個子空間的交是一維子空間的二維子空間構成一個（3，1）型子空間，即節點ni與nj的共享密鑰量為1。

由以上分析可知，所構造方案的參數（q2+ q + 1，q + 1，1）為射影平面的參數，因此得到了一種新的構造射影平面的方法。

無線傳感器網絡的密鑰管理方案必須具有連通性和安全性。下面就對本文提出方案中的這兩個最重要的性能進行分析。

連通性連通性就是一個網絡中任何兩個節點至少共享一個密鑰的概率。在此方案中，從共享密鑰來分析，任兩個節點擁有多個共享密鑰，能保證任何兩個節點共享一個密鑰，共享概率為1，明顯高于其它方案，如表2所示。

表2　比較不同方案的連通性Tab.2 Difference from different schem es

表2中，A-G、S-B、P-S分別出自于文獻[11-13]。在大部分現有文獻[14-18]中，W SN的全局連通性都只有0.6左右。

安全性如果某個節點被敵人所捕獲，則該節點存儲的密鑰等信息不再安全。節點ni與nj之間的共享密鑰都在節點nk中，一旦節點nk被捕獲，則節點ni與nj之間的連接就會破壞。定義損失概率為

抗毀性是影響無線傳感器網絡應用方面的一個很重要的因素。假設攻擊者可以隨機或者選擇性地攻擊節點，對此做最壞的假設，假設攻擊者選擇性地攻擊節點。如果一個攻擊者足夠聰明和幸運，可以掌控整個無線傳感網絡，然后從中挑選其想要的節點。因為每個節點含有一個密鑰鏈，每個密鑰鏈中有q + 1個密鑰，由于本文給出的方案中有q2+ q + 1個節點，一個足夠聰明的攻擊者至少需要q + 1個密鑰鏈才能恢復密鑰池中所有的密鑰（因為q（q + 1）= q2+ q，所以q個密鑰鏈恢復不了整個密鑰池）。這時兩個節點的通信是不安全的。

由以上分析可知，如果W SN中部署1 723（412+ 41 + 1 = 1 723）（這里的q = 41）個傳感器節點，當有41個節點被捕獲時，整個密鑰池被攻破。

5　結語

無線傳感器網絡越來越廣泛，其安全性越來越受到人們的關注，其中密鑰分配和管理是無線傳感器網絡安全的熱點研究問題。無線傳感器網絡不同于傳統網絡，考慮到其能量供應、計算能力、存儲容量的限制，密鑰分配機制有其自身的特點。在現有方案中，基于概率的隨機預分配方案存在共享概率和密鑰路徑長度無法得到確定性保證的問題，并且在節點密鑰組長度受限的情況下難以支持較大規模的網絡。本文在介紹了無線傳感器網絡特點的基礎上，對目前已有的隨機型和確定型密鑰預分配方案的設計進行詳細分析，以較高的概率保證鄰居節點之間建立對立密鑰，同時也解決了原始方案中的安全問題。

參考文獻：

[1]孫利民.無線傳感器網絡[M].北京：清華大學出版社，2005.

[2] AKYILDIZ IF，SU W，SANKARASUBRAMANIAM Y.A survey on sensornetworks[J].IEEE Communications，2002，40（8）：102-114.

[3] ESCHENAUER L，GLIGOR V D.A Key-Management Scheme for Distributed Sensor Networks[C]//Proc of the9th ACM Confon Computer and CommunicationsSecurity.New York：ACM Press，2002：41-47.

[4] CHAN H，PERRIG A，SONG D X.Random Key Pre-Distribution Schemes for Sensor Networks[C]//Proc of2003 IEEE Symp on Research in Securityand Privacy.New York：ACM Press，2003：197-213.

[5] CAMTEPE S A，YENER B.Combinatorial Design of Key DistributionMechanisms forW ireless Sensor Networks[C]//Proc of the 9th European Symp on Research in Computer Security.Berlin：Springer，2004：293-308.

[6] LIU D，NING P.Establishing Pair-W ise Keys in Distributed Sensor Networks[C]//Proc of the 10th ACM Confon Computer and CommunicationsSecurity.New York：ACM Press，2003：52-61.

[7] LEE J，STINSON D R.Deterministic Key Pre-Distribution Schemes for Distributed Sensor Networks[C]//Proc of the 11th Int W orkshop on Selected Areas in Cryptography.Berlin：Springer，2004：1-14.

[8]夏戈明，黃遵國，王志英.基于對稱平衡不完全區組設計的無線傳感器網絡密鑰預分配方案[J].計算機研究與發展，2008，45（1）：154-164.

[9]沈顥.組合設計理論[M].上海：上海交通大學出版社，2008.

[10] W AN Z X.Geometry ofClassical Groups over Finite Field[M].Lund：Student Literature，1993.

[11] PERRIG A，STANKOVIC J，W AGNER D.Security in sensor networks [J].Communicationsof the ACM，2004，47（6）：53-57.

[12]RUJS，ROY B.Key Pre-Distribution Using Partially Balanced Designs inW ireless Sensor Networks[C]//Proceedings of ISPA 2007.Canada： Niagara Falls，2007：431-445.

[13] CAMTEPE S A，YENER B.Combinatorial Design of Key Distribution Mechanisms forW ireless Sensor Networks[C]//Proc of the 9th European Symp on Research in Computer Security.Berlin：Springer，2004：293-308.

[14]PATERSON M B，STINSON D R.A unified approach to combinatorial key predistribution schemes for sensornetworks[J].DesCodesCryptogr，2014，71：433-457.

[15]Chen C Y，Chao H C.A survey ofkey predistribution inwirelesssensor networks[EB/OL].（2011-07-13）[2014-10-26].http：//www.arxiv.org.

[16] MARTIN K M.On the Applicability of Combinatorial Designs to Key Predistribution forW ireless Sensor Networks[C]//IW CC，2009.Lecture Notes in Computer Science，2009，5557：124-145.

[17] MARTIN K M.The rise and fall and rise of combinatorial key predistribution[J].Leture Notes in Computer Science，2011，6544：92-98.

[18]PEID Y，DONG JW，RONG C M.A novelkey predistribution scheme forwirelessdistributed sensorneyworks[J].SciChina Inf Sci，2010，53：288-298.

（責任編輯：楊媛媛）

Key pre-distribution schem e based on sym plectic geom etry for w ireless sensor networks

CHEN Shangdi，W EN Jiejing
（College of Science，CAUC，Tianjin 300300，China）

Abstract：The design of keymanagementscheme，whosemain objective is to provide secure and reliable communication，is one of themost importantparts of securitymechanism ofwireless sensornetwork.W ith regard to the limitation of power，computation and storge recourse ofwireless sensor network，a key pre-distribution scheme based on the 4-dimensional symplectic geometry ofwireless sensor networks is proposed.The obtained results show that the scheme considerably enhances the network scalability，and it has achieved good connectivity and good overallperformance.

Key words：wirelesssensornetwork（W SN）；key distribution；key pre-distribution scheme；symplectic geometry

作者簡介：陳尚弟（1964—），男，山西應縣人，教授，博士，研究方向為代數、圖論、編碼與密碼.

收稿日期：2014-10-31；修回日期：2014-12-23基金項目：中央高校基本科研業務費專項（ZXH2012K005）；國家自然科學基金項目（61179026）

中圖分類號：O157

文獻標志碼：A

文章編號：1674-5590（2016）01-0059-06