陳尚弟，文潔晶

（中國民航大學(xué)理學(xué)院，天津　300300）

?

用辛幾何構(gòu)造傳感器的密鑰預(yù)分配方案

陳尚弟，文潔晶

（中國民航大學(xué)理學(xué)院，天津300300）

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

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；密鑰分配；密鑰預(yù)分配方案；辛幾何

近些年來，隨著傳感技術(shù)、計算機(jī)技術(shù)飛速發(fā)展與成熟，帶動了信息科學(xué)領(lǐng)域中的一個全新的發(fā)展方向——無線傳感器網(wǎng)絡(luò)，即具有感知能力、計算能力和通信能力的微型傳感器構(gòu)成的網(wǎng)絡(luò)。該網(wǎng)絡(luò)在世界范圍內(nèi)得到應(yīng)用，是傳統(tǒng)學(xué)科與新興學(xué)科交叉的結(jié)果。因此由這些微型傳感器構(gòu)成的無線傳感器網(wǎng)絡(luò)（wireless sensor network，W SN）引起了人們的極大關(guān)注。

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

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

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

使網(wǎng)絡(luò)規(guī)模、節(jié)點內(nèi)存及整個網(wǎng)絡(luò)的連通性、抗毀性和安全性彼此之間相互制約，沒有一個方案使他們都同時達(dá)到最大，所以近些年來許多學(xué)者都在探索和研究更好的密鑰預(yù)分配方案。

1　相關(guān)成果敘述

根據(jù)給節(jié)點分配密鑰方法的不同，無線傳感器網(wǎng)絡(luò)的密鑰預(yù)分配方案有以下兩種劃分，即概率不確定型密鑰預(yù)分配方案和基于組合結(jié)構(gòu)的確定型密鑰預(yù)分配方案。

概率型密鑰預(yù)分配方案是一種基于求概率結(jié)果的密鑰預(yù)分配模型，計算任意兩個節(jié)點存在共享密鑰的概率，并且這個值高于一定概率，進(jìn)而使得整個系統(tǒng)的密鑰共享圖構(gòu)成以一個確定概率連通的連成圖。隨機(jī)密鑰預(yù)分配方案有以下兩種：

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

a）密鑰分發(fā)從一個較大的密鑰空間選取一個密鑰池S，并為每個密鑰分配一個ID。在進(jìn)行節(jié)點部署前，每個節(jié)點從密鑰池中隨機(jī)地選取k個密鑰構(gòu)成自己的密鑰環(huán)，k大小的選擇要保證每兩個節(jié)點存在相同密鑰的概率p大于預(yù)先設(shè)定的概率值。

b）密鑰發(fā)現(xiàn)節(jié)點之間通信時，通過交換各自的ID來發(fā)現(xiàn)共享密鑰。

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

在Eschenauer等[3]提出的隨機(jī)密鑰預(yù)分布模型方案中，兩個節(jié)點之間共享密鑰的概率p與密鑰池的大小S及密鑰鏈長度k之間的數(shù)學(xué)關(guān)系如下

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

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

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

2　基礎(chǔ)知識

2.1有限關(guān)聯(lián)結(jié)構(gòu)

通常用（P）表示與點P關(guān)聯(lián)的區(qū)組集，用（x）表示與區(qū)組x關(guān)聯(lián)的點集。因此（Pi）∩（P）j表示既與點Pi關(guān)聯(lián)又與點Pj關(guān)聯(lián)的區(qū)組集。通常以v表示點集的

對1≤i≤v，令ri表示中與點Pi關(guān)聯(lián)的區(qū)組數(shù)；1≤j≤b，令kj表示中與區(qū)組xj關(guān)聯(lián)的點的個數(shù)；對1≤i，j≤v，i≠j，令λi，j表示中同時與點Pi及Pj關(guān)聯(lián)的區(qū)組數(shù)。ri叫做點P的重復(fù)度，kj叫做區(qū)組xj的長度，λi，j叫做Pi與Pj的相遇數(shù)，即

上述定義出自文獻(xiàn)[9]。

2.2辛空間簡介

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

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

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

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

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

上述定理定義出自文獻(xiàn)[10]。

3　密鑰預(yù)分配方案構(gòu)造

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

參數(shù)的選擇如下：

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

上述關(guān)聯(lián)結(jié)構(gòu)和密鑰預(yù)分配方案的對應(yīng)關(guān)系如表1所示。

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

4　方案分析

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

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

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

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

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

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

下面計算任意兩個節(jié)點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任意兩個節(jié)點ni與nj的共享密鑰量為1。

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

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

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

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

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

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

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

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

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

5　結(jié)語

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

參考文獻(xiàn)：

[1]孫利民.無線傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社，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]夏戈明，黃遵國，王志英.基于對稱平衡不完全區(qū)組設(shè)計的無線傳感器網(wǎng)絡(luò)密鑰預(yù)分配方案[J].計算機(jī)研究與發(fā)展，2008，45（1）：154-164.

[9]沈顥.組合設(shè)計理論[M].上海：上海交通大學(xué)出版社，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.

（責(zé)任編輯：楊媛媛）

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—），男，山西應(yīng)縣人，教授，博士，研究方向為代數(shù)、圖論、編碼與密碼.

收稿日期：2014-10-31；修回日期：2014-12-23基金項目：中央高?；究蒲袠I(yè)務(wù)費(fèi)專項（ZXH2012K005）；國家自然科學(xué)基金項目（61179026）

中圖分類號：O157

文獻(xiàn)標(biāo)志碼：A

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