基于六邊形網(wǎng)格組部署的對稱密鑰預(yù)分配模型

龐浩杰 ，常 凱 ， 金 琰， 朱 亮

(1.河南省洛陽正骨醫(yī)院(河南省骨科醫(yī)院)， 鄭州 450016; 2.湖北中醫(yī)藥大學(xué) 信息工程學(xué)院，武漢 430065;3.鄭州輕工業(yè)大學(xué) 計(jì)算機(jī)與通訊工程學(xué)院，鄭州 450002)

0 引言

傳感器網(wǎng)絡(luò)有許多應(yīng)用，如家庭安全監(jiān)控、軍事偵察、環(huán)境監(jiān)測和目標(biāo)跟蹤等等[1-4]。典型的傳感器網(wǎng)絡(luò)通常由大量的微小感知設(shè)備構(gòu)成，這些設(shè)備又稱為傳感器節(jié)點(diǎn)，它們的電池電量和數(shù)據(jù)處理能力有限，并且通常通過短距離無線電信號彼此通信；在許多應(yīng)用中，傳感器節(jié)點(diǎn)通常隨機(jī)分布在特定區(qū)域，以感知和收集有用的信息。

傳感器網(wǎng)絡(luò)最基本的安全要求之一是保證傳感器節(jié)點(diǎn)間發(fā)送信息的保密性和完整性。尤其是傳感器網(wǎng)絡(luò)部署在“敵對”環(huán)境中時(shí)，密鑰的建立在認(rèn)證和加密中起著很重要的作用。攻擊者可以通過對傳感器節(jié)點(diǎn)發(fā)起物理攻擊，或者對不同的通信協(xié)議采用邏輯攻擊來竊聽消息或使網(wǎng)絡(luò)失效[5-6]。因此，傳感器網(wǎng)絡(luò)需要加密和認(rèn)證服務(wù)。由于資源的限制，實(shí)現(xiàn)有效的密鑰建立機(jī)制并不是一項(xiàng)簡單的任務(wù)。除了目前流行的橢圓曲線密碼體制外[7]，對稱密鑰算法[8]也是解決這一問題的可行途徑。

文獻(xiàn)[9]提出的隨機(jī)密鑰預(yù)分配模型離線生成一個(gè)大的密鑰池，每個(gè)傳感器從密鑰池中隨機(jī)選取一個(gè)密鑰子集。通信范圍內(nèi)的任意兩個(gè)節(jié)點(diǎn)只有共享一個(gè)公用密鑰才能相互通信。根據(jù)密鑰池的大小和網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)的數(shù)量，這種體制可以實(shí)現(xiàn)不同的連通性和恢復(fù)能力；文獻(xiàn)[10]提出將部署知識應(yīng)用到基本的隨機(jī)成對密鑰中；文獻(xiàn)[11]通過應(yīng)用部署知識提出了一種密鑰預(yù)分配模型。在這種模型中，把整個(gè)網(wǎng)絡(luò)分成組，每個(gè)組執(zhí)行基本的隨機(jī)密鑰預(yù)分配。一個(gè)組的密鑰池與水平組密鑰池共享(個(gè)密鑰，與對角組密鑰池共享(個(gè)密鑰；從Blom解決方案[12]發(fā)展而來的密鑰矩陣方案還有文獻(xiàn)[13]的多空間密鑰預(yù)分配模型。

文獻(xiàn)[14]提出了采用多項(xiàng)式的隨機(jī)密鑰生成思想。它采用對稱多項(xiàng)式計(jì)算來獲得成對密鑰。這種方案對捕獲的節(jié)點(diǎn)具有t-串謀抵抗能力，即小于t+1個(gè)節(jié)點(diǎn)的攻擊不會泄露任何關(guān)于其他節(jié)點(diǎn)密鑰的信息；文獻(xiàn)[15]基于該思想和基本隨機(jī)密鑰預(yù)分配[9]，提出了隨機(jī)子集分配密鑰預(yù)分配模型。與生成大型密鑰池和創(chuàng)建密鑰環(huán)不同，該方案創(chuàng)建一個(gè)大型多項(xiàng)式池，并從池中為每個(gè)節(jié)點(diǎn)分配一個(gè)多項(xiàng)式子集。這樣，兩個(gè)節(jié)點(diǎn)只有共享至少一個(gè)公用多項(xiàng)式才能相互通信。結(jié)果表明，與文獻(xiàn)[9]模型相比，這種模型提高了恢復(fù)能力；文獻(xiàn)[16]提出了利用預(yù)部署知識的私有多項(xiàng)式預(yù)分配方案，文獻(xiàn)[17]提出了基于8-方形網(wǎng)格的多項(xiàng)式預(yù)分配方案；文獻(xiàn)[18] 針對Sheetal Kalra 方案容易在數(shù)據(jù)庫泄露和用戶智能卡丟失的情況下受到用戶的假冒攻擊、并且不能達(dá)成正確的共享密鑰的分析，基于口令的無線傳感器網(wǎng)絡(luò)認(rèn)證方案，提出了一種改進(jìn)的帶有智能卡的認(rèn)證方案，解決了 Sheetal Kalra 方案中的安全性問題，提供了用戶、傳感器、網(wǎng)關(guān)節(jié)點(diǎn)之間的相互認(rèn)證并達(dá)成正確的共享密鑰。此外，還給出了提出方案的安全性分析，以此證明提出的方案可以滿足無線傳感器網(wǎng)絡(luò)中的安全需求；文獻(xiàn)[19]針對移動異構(gòu)無線傳感器網(wǎng)絡(luò)模型，提出了在一種安全高效的密鑰管理方法。方法采用橢圓曲線密碼學(xué)加密算法實(shí)現(xiàn)移動節(jié)點(diǎn)位置信息到基站的安全上傳，以及基于密鑰哈希的消息認(rèn)證碼來實(shí)現(xiàn)消息源的身份認(rèn)證?；緞t對收集的移動節(jié)點(diǎn)位置信息進(jìn)行統(tǒng)計(jì)分析來協(xié)助完成固定節(jié)點(diǎn)與移動節(jié)點(diǎn)間的身份認(rèn)證及會話密鑰建立。實(shí)驗(yàn)結(jié)果表明，所提出的方法在密鑰建立過程中節(jié)省了網(wǎng)絡(luò)資源，同時(shí)可有效防御攻擊者發(fā)起重放攻擊，節(jié)點(diǎn)復(fù)制攻擊和女巫攻擊等，增強(qiáng)了網(wǎng)絡(luò)的安全性；文獻(xiàn)[20]基于具有節(jié)點(diǎn)移動性的動態(tài)傳感器網(wǎng)絡(luò)安全通信，分析了一種證書無效密鑰管理(CL-EKM,certificate less-effective key management)協(xié)議，保護(hù)數(shù)據(jù)和通信需要適當(dāng)?shù)募用苊荑€協(xié)議。針對具有節(jié)點(diǎn)移動性的動態(tài)傳感器網(wǎng)絡(luò)的安全通信，提出了一種證書無效密鑰管理(CL-EKM)協(xié)議。CL-EKM協(xié)議支持在節(jié)點(diǎn)離開或加入集群時(shí)進(jìn)行高效的密鑰更新，并保證了向前和向后的密鑰保密。該協(xié)議還支持對被破壞的節(jié)點(diǎn)有效的密鑰撤銷，并將節(jié)點(diǎn)被破壞對其他通信鏈路安全的影響降到最低。對方案的安全性分析表明，該方案能夠有效地防御各種攻擊。

上述這些解決方案在采用預(yù)部署知識來提高性能和安全性方面仍有一些局限性。對此，本文提出了一種基于六邊形網(wǎng)格組部署的無線傳感器網(wǎng)絡(luò)對稱密鑰預(yù)分配模型。模型將多項(xiàng)式信息分配到一個(gè)六邊形網(wǎng)格組中的特定區(qū)域內(nèi)有限數(shù)量的傳感器節(jié)點(diǎn)上，從而使得每個(gè)傳感器節(jié)點(diǎn)找到與其相鄰節(jié)點(diǎn)的共享密鑰空間；仿真實(shí)驗(yàn)結(jié)果表明，提出的對稱密鑰預(yù)分配模型不僅具有良好的加密性能，而且相比于其他模型的密鑰方案有更好的內(nèi)存開銷、運(yùn)行時(shí)間和節(jié)點(diǎn)受損攻擊時(shí)的網(wǎng)絡(luò)恢復(fù)能力。

1 相關(guān)模型

1.1 基于Blom思想的密鑰預(yù)分配模型

基于Blom思想提出的密鑰預(yù)分配模型[9]能夠確保組中的任何一對成員都可以計(jì)算公用共享密鑰。用N表示網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)數(shù)目，G為有限域上大小為(t+1)×N的生成矩陣，D為大小為(t+1)×(t+1)的秘密隨機(jī)矩陣，其中t為攻擊者攻擊的節(jié)點(diǎn)個(gè)數(shù)。從矩陣G和D，構(gòu)造一個(gè)N×N的對稱矩陣K，它的元素是節(jié)點(diǎn)之間的成對密鑰，則矩陣K為：

K=(D·G)T·G

(1)

每個(gè)節(jié)點(diǎn)i存儲私有矩陣A=(D·G)T對應(yīng)的第i行。如果節(jié)點(diǎn)i想要與節(jié)點(diǎn)j通信，則它計(jì)算其存儲的行向量與G的第j列的內(nèi)積，得到公用密鑰Ki,j。文獻(xiàn)[13]的多空間密鑰預(yù)分配模型將Blom思想與文獻(xiàn)[9]的基本隨機(jī)密鑰預(yù)分配模型相結(jié)合應(yīng)用于傳感器網(wǎng)絡(luò)。在這種方法中，他們將每個(gè)元組(D,G)生成的密鑰空間表示為密鑰集合。網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)隨機(jī)存儲來自于ω個(gè)預(yù)生成空間的τ個(gè)空間?；诟怕?，任意兩個(gè)節(jié)點(diǎn)可以共享一個(gè)公用空間，該空間可以計(jì)算出一個(gè)公用秘密密鑰。所有密鑰矩陣解決方案都具有閾值t-安全特性，即當(dāng)攻擊者攻擊的節(jié)點(diǎn)不超過t個(gè)時(shí)，未被攻擊的節(jié)點(diǎn)之間的通信仍然是安全的。

1.2 基于Blundo思想的密鑰預(yù)分配模型

基于Blundo思想提出的多項(xiàng)式密鑰預(yù)分配模型[15]采用對稱多項(xiàng)式計(jì)算來獲得成對密鑰，方案使用n個(gè)變量的t次多項(xiàng)式來建立t-安全n-聯(lián)盟的密鑰分配。應(yīng)用于兩個(gè)對象之間的成對密鑰，密鑰預(yù)分配服務(wù)器在一個(gè)有限域Fq上隨機(jī)生成一個(gè)二元t次多項(xiàng)式：

(2)

其中:q是一個(gè)足夠大的素?cái)?shù)，可以容納一個(gè)密碼密鑰，函數(shù)f(x,y)是對稱的即f(x,y)=f(y,x)。每個(gè)節(jié)點(diǎn)有唯一的整數(shù)IDi，加載來自于多項(xiàng)式f(x,y)的信息f(i,y)。這樣，任意兩個(gè)節(jié)點(diǎn)i和j可以計(jì)算節(jié)點(diǎn)i的密鑰Ki,j=f(i,j)和節(jié)點(diǎn)j的密鑰Kj,i=f(j,i)。由于對稱特性，有：

Ki,j=Kj,i

(3)

故兩個(gè)節(jié)點(diǎn)有一個(gè)共用的成對密鑰。

每個(gè)節(jié)點(diǎn)必須存儲t+1個(gè)系數(shù)，每個(gè)系數(shù)有l(wèi)og2q比特(bits)。因此，該模型中每個(gè)節(jié)點(diǎn)的內(nèi)存存儲需求為(t+1)log2q比特。由于存儲密鑰的內(nèi)存開銷很大，這種方案不能直接應(yīng)用于傳感器網(wǎng)絡(luò)，因?yàn)閮?nèi)存的大小按指數(shù)規(guī)律依賴于網(wǎng)絡(luò)的規(guī)模，因此對于資源受限的傳感器節(jié)點(diǎn)等設(shè)備來說是不可行的；對此，本文將通過采用預(yù)部署知識來解決這個(gè)問題，并表明相比其他基于多項(xiàng)式的、應(yīng)用預(yù)期位置知識的方案更具優(yōu)勢；此外，我們在計(jì)算成對密鑰中還加入了一些隨機(jī)數(shù)，這樣，對手就很難對未捕獲節(jié)點(diǎn)的額外安全連接造成破壞。

2 基于六邊形網(wǎng)格組部署的對稱密鑰預(yù)分配模型

在提出本文方案之前，我們將密鑰空間定義為采用Blundo模型生成的一個(gè)t次二元多項(xiàng)式f(x,y)的全部密鑰的集合，密鑰空間中的密鑰數(shù)量表示密鑰空間大小。假設(shè)如果一個(gè)節(jié)點(diǎn)攜帶f(x,y)生成的信息，則它將選擇一個(gè)密鑰空間。任意兩個(gè)選擇公用密鑰空間的節(jié)點(diǎn)總是計(jì)算它們的成對密鑰。

節(jié)點(diǎn)nA選擇密鑰空間fu,v(x,y)，如果它攜帶fu,v(nA⊕RvA,y)的系數(shù)，其中RvA是節(jié)點(diǎn)nA的隨機(jī)值，將在密鑰預(yù)分配階段進(jìn)行描述。當(dāng)兩個(gè)節(jié)點(diǎn)在相同的密鑰空間時(shí)，它們可以計(jì)算成對密鑰來建立安全通道。

本文方案允許傳感器節(jié)點(diǎn)在部署后找到與其相鄰的每個(gè)節(jié)點(diǎn)的公用密鑰空間。方案共分為3個(gè)階段：密鑰預(yù)分配階段、直接密鑰建立階段和間接密鑰建立階段。在部署前執(zhí)行密鑰預(yù)分配階段，將憑證信息預(yù)加載到每個(gè)傳感器節(jié)點(diǎn)。之后，如果兩個(gè)傳感器節(jié)點(diǎn)至少共享一個(gè)共用密鑰空間，則可在它們之間建立一個(gè)直接密鑰，否則，它們可以在間接密鑰建立階段的基礎(chǔ)上商定一個(gè)間接密鑰。

首先，要解決傳感器網(wǎng)絡(luò)的部署模型。

2.1 基于六邊形網(wǎng)格組的傳感器節(jié)點(diǎn)部署

在本文模型中，把目標(biāo)區(qū)域劃分為六邊形網(wǎng)格。六邊形網(wǎng)格提供了對圓的最佳近似，比在連續(xù)區(qū)域中可以重復(fù)使用的其他2種幾何圖形(三角形和矩形)所覆蓋的面積更大。與矩形的8個(gè)或三角形的12個(gè)相鄰單元格相比，六邊形有最少的相鄰單元格(6個(gè))。傳感器節(jié)點(diǎn)在單元格上進(jìn)行劃分并分組。這種模型適合于實(shí)際場景，當(dāng)每組的傳感器節(jié)點(diǎn)一起部署時(shí)，預(yù)期的相鄰組更有可能彼此接近。

(4)

式中,(xi,yi)為組Gi中的節(jié)點(diǎn)ni的坐標(biāo)，σ為分布的標(biāo)準(zhǔn)偏差?；诹呅尉W(wǎng)格組的部署模型如圖1所示。

圖1 基于六邊形網(wǎng)格組的部署模型

在描述本文方案的原理之前，定義集群為3個(gè)相鄰組的集合，一個(gè)組有3種類型的集群：1-集群、2-集群和3-集群。對于任何一個(gè)組(i,j)，1-集群包含這個(gè)組(i,j)和組(i+1,j)以及(i+1,j+1)，2-集群包含這個(gè)組(i,j)和組(i,j-1)以及(i-1,j)，3-集群包含這個(gè)組(i,j)和組(i-1,j+1)以及(i,j+1)。

例如在圖1中，對于組(2,2)來說，組(3,2)和組(3,3)屬于1-集群(2,2)，組(2,1)和組(1,2)屬于2-集群(2,2)，組(2,3)和組(1,3)屬于3-集群(2,2)。

在一個(gè)單元格上，分布函數(shù)可能是不均勻的，但可以在部署點(diǎn)之間選擇合適的距離，使得總體分布接近均勻。

2.2 密鑰預(yù)分配階段

此階段的目標(biāo)是將密鑰材料分配給每個(gè)節(jié)點(diǎn)。基于這些密鑰材料，相鄰節(jié)點(diǎn)在部署后可以對密鑰進(jìn)行配對設(shè)置。

這個(gè)任務(wù)是通過離線服務(wù)器完成的。首先，服務(wù)器為每個(gè)集群生成一個(gè)多項(xiàng)式池F，它包含足夠多的t次對稱二元多項(xiàng)式。然后將每個(gè)多項(xiàng)式分配給每個(gè)集群中的所有傳感器節(jié)點(diǎn)。由于每個(gè)單元格屬于3個(gè)集群，所以每個(gè)節(jié)點(diǎn)要存儲3個(gè)t次二元多項(xiàng)式的知識。換句話說，每個(gè)節(jié)點(diǎn)要選擇3個(gè)密鑰空間。算法1所示為多項(xiàng)式預(yù)分配實(shí)現(xiàn)的偽代碼。

這一階段完成后，每個(gè)傳感器節(jié)點(diǎn)存儲一個(gè)節(jié)點(diǎn)ID、3個(gè)空間ID、一個(gè)隨機(jī)值和3個(gè)對應(yīng)于3個(gè)密鑰空間的系數(shù)向量的值。這些密鑰材料將用于下一階段的成對鑰匙建立。

算法1:多項(xiàng)式預(yù)分配算法

Input: 網(wǎng)絡(luò)中的節(jié)點(diǎn)集合N, 集群集合Ψ, 多項(xiàng)式池F

Output: 加載密鑰材料給網(wǎng)絡(luò)中的每個(gè)傳感器節(jié)點(diǎn)

1.For每個(gè)組Gi,j

2.For1-集群(Gi,j)中的每個(gè)組Gu,v

3.If不在polynomial_sharing(Gu,v,Gi,j)中

4.生成一個(gè)f(x,y)

5.把f(x,y)分配給1-集群(Gi,j)

6.Endif

7.Endfor

8.For2-集群(Gi,j)中的每個(gè)組Gu,v

9.If不在polynomial_sharing(Gu,v,Gi,j)中

10.生成一個(gè)f(x,y)

11.把f(x,y)分配給2-集群(Gi,j)

12.Endif

13.Endfor

14.For3-集群(Gi,j)中的每個(gè)組Gu,v

15.If不在polynomial_sharing(Gu,v, Gi,j)中

16. 生成一個(gè)f(x,y)

17. 把f(x,y)分配給3-集群(Gi,j)

18.Endif

19.Endfor

20.Endfor

2.3 直接密鑰建立階段

在傳感器節(jié)點(diǎn)部署到目標(biāo)區(qū)域后，每個(gè)傳感器節(jié)點(diǎn)必須找到與其相鄰節(jié)點(diǎn)的共享密鑰空間。假設(shè)節(jié)點(diǎn)nA具有3個(gè)空間IDfi,fj,fk，需要與其鄰居發(fā)現(xiàn)共享密鑰空間。它廣播一個(gè)1-跳發(fā)現(xiàn)消息—密鑰空間發(fā)現(xiàn)消息(KSDM,key-space discovery message)如下：

(nA,RvA,H(fi⊕RvA),H(fj⊕RvA),H(fk⊕RvA))

(5)

式中,H為哈希函數(shù)，⊕為異或運(yùn)算。

當(dāng)A的一個(gè)鄰居(設(shè)為B)接收到這個(gè)消息時(shí)，它會發(fā)現(xiàn)它可以與A共享3個(gè)、1個(gè)或不共享公用密鑰空間。類似地，節(jié)點(diǎn)A也接收到B的KSDM消息并發(fā)現(xiàn)公用密鑰空間。如果共享至少1個(gè)公用密鑰空間，則B和A之間的成對密鑰在B點(diǎn)計(jì)算如下：

KB,A=f(nB⊕(RvB,nA⊕RvA)

(6)

在獲得KB,A之后，節(jié)點(diǎn)B從它的內(nèi)存中刪除RvA值。計(jì)算A點(diǎn)的成對密鑰的過程與此類似。由于二元多項(xiàng)式的對稱性，所以：

KA,B=KB,A

(7)

完成這一階段后，除了前一階段的密鑰空間信息和一個(gè)隨機(jī)值外，每個(gè)節(jié)點(diǎn)還存儲一個(gè)與其相鄰節(jié)點(diǎn)的成對密鑰列表。

2.4 間接密鑰建立階段

如果兩個(gè)相鄰節(jié)點(diǎn)之間沒有公用密鑰空間，則需要通過一個(gè)或多個(gè)中間節(jié)點(diǎn)建立一個(gè)路徑密鑰，實(shí)現(xiàn)過程如下。

在直接密鑰建立階段之后，每個(gè)節(jié)點(diǎn)A知道其安全鄰接節(jié)點(diǎn)的集合SA。源節(jié)點(diǎn)A希望與其鄰居B建立一個(gè)成對密鑰，但是B和A不共享任何密鑰空間。在這種情況下，A生成一個(gè)會話密鑰KS，并找到在SA中與節(jié)點(diǎn)B有相同的組ID或包含節(jié)點(diǎn)B的組的相鄰組ID的節(jié)點(diǎn)C，然后節(jié)點(diǎn)A向節(jié)點(diǎn)C發(fā)送一條包含通過密鑰KA,C加密的KS消息。然后，節(jié)點(diǎn)C通過密鑰KC,B保護(hù)的安全通道向B發(fā)送會話密鑰，則密鑰KS作為節(jié)點(diǎn)A和節(jié)點(diǎn)B之間的成對密鑰。

在以上3個(gè)階段完成之后，每個(gè)節(jié)點(diǎn)都存儲一個(gè)包含鄰居的IDs和對等的密鑰表。密鑰材料的存在使得傳感器網(wǎng)絡(luò)能夠增加新的節(jié)點(diǎn)供后面替換。

2.5 傳感器節(jié)點(diǎn)的添加和刪除

為了增加一個(gè)新的傳感器節(jié)點(diǎn)，密鑰建立服務(wù)器只需要將相關(guān)的多項(xiàng)式共享預(yù)先分配給新節(jié)點(diǎn)，類似于預(yù)分配階段。由于密鑰空間的大小是有限的，添加的傳感器越多，該單元中的安全性就越低；刪除方法很簡單。每個(gè)傳感器節(jié)點(diǎn)只需要存儲一個(gè)與自身共享至少一個(gè)二元變量多項(xiàng)式的被破壞傳感器的黑名單IDs。如果有超過t個(gè)被破壞節(jié)點(diǎn)共享同一個(gè)多項(xiàng)式，則擁有該多項(xiàng)式的非被破壞節(jié)點(diǎn)將刪除該多項(xiàng)式和所有相關(guān)的被破壞節(jié)點(diǎn)。

算法2為密鑰建立和分配實(shí)現(xiàn)的偽代碼。

算法2:密鑰建立和分配算法

1.ForN中每個(gè)傳感器節(jié)點(diǎn)nADo

2. 對nA的預(yù)加載數(shù)據(jù)生成并插入一個(gè)隨機(jī)值RvA;

3.Endfor

4.For(中每個(gè)集群CiDo

5.從F中獲取一個(gè)二元多項(xiàng)式fi(x,y);

6.ForCi中每個(gè)節(jié)點(diǎn)nADo

8. 插入nA的預(yù)加載數(shù)據(jù){bj|j=0,...,t};

9. 將多項(xiàng)式的ID(也稱為了空間-ID)fi插入到nA;

10.Endfor

11.從F中刪除fi(x,y);

12.Endfor

3 算法仿真實(shí)驗(yàn)結(jié)果及分析

仿真中采用的度量指標(biāo)如下。

1)網(wǎng)絡(luò)連通性：包括局部連通性和全局連通性。局部連通性是指一個(gè)節(jié)點(diǎn)可以在其傳輸范圍內(nèi)與相鄰節(jié)點(diǎn)連接的概率。全局連通性是最終密鑰圖G中形成最大獨(dú)立連通部分的傳感器節(jié)點(diǎn)數(shù)目與整個(gè)網(wǎng)絡(luò)的大小之比。

2)內(nèi)存開銷和運(yùn)行時(shí)間：內(nèi)存開銷為模型中在節(jié)點(diǎn)上存儲密鑰材料的內(nèi)存需求，運(yùn)行時(shí)間為密鑰空間形成和分配，直至最終兩個(gè)節(jié)點(diǎn)獲得成對密鑰所消耗的時(shí)間。

3)對捕獲節(jié)點(diǎn)攻擊的恢復(fù)能力：對手通常發(fā)起節(jié)點(diǎn)捕獲攻擊，以竊聽網(wǎng)絡(luò)中的安全通道，或者利用捕獲節(jié)點(diǎn)泄露的密鑰材料進(jìn)行節(jié)點(diǎn)復(fù)制攻擊。在此分析中，我們評價(jià)節(jié)點(diǎn)破壞攻擊對剩余網(wǎng)絡(luò)通信的影響，即對手能夠發(fā)現(xiàn)一個(gè)二元多項(xiàng)式的概率，這意味著它們可以泄露所有由這個(gè)多項(xiàng)式得到的加密安全連接。

3.1 系統(tǒng)配置

采用表1中的設(shè)置進(jìn)行仿真和數(shù)值分析。在這種場景下，假設(shè)節(jié)點(diǎn)部署遵循二維高斯分布，其PDF函數(shù)如式(1)所示。

表1 仿真設(shè)置

3.2 網(wǎng)絡(luò)連通性

假設(shè)A(ni,nj)和B(ni,nj)為事件，節(jié)點(diǎn)ni為節(jié)點(diǎn)nj的鄰居，它們共享至少1個(gè)共用密鑰空間。局部連通性可以計(jì)算為：

Plocal=P(B(ni,nj)|A(ni,nj))=

(8)

節(jié)點(diǎn)ni∈Gi為節(jié)點(diǎn)nj(xj,yj)的鄰居的概率是在節(jié)點(diǎn)nj周圍半徑為R的圓上的PDFf(ni)的積分：

(9)

由于nj按式(1)分布在組Gj中，所以ni∈Gi為nj∈Gj的鄰居的概率為：

(10)

因此:

(11)

用S(Gi)表示Gi相鄰組的集合，則有：

(12)

由于傳感器節(jié)點(diǎn)是在給定的組中以相等的概率被選擇的，因此局部連通性可以計(jì)算為：

(13)

用d=k×σ表示兩個(gè)相鄰單元格的兩個(gè)部署點(diǎn)之間的距離(k為比例系數(shù))，這個(gè)值會影響網(wǎng)絡(luò)的局部連通性和全局連通性。當(dāng)k值較大時(shí)，則一個(gè)組中幾乎每個(gè)節(jié)點(diǎn)都位于自己的單元格區(qū)域內(nèi)，而且相鄰節(jié)點(diǎn)都來自自己的組。在這種情況下，局部連通性非常高，但網(wǎng)絡(luò)完全被分割成單獨(dú)的部分，這意味著全局連通性非常低；當(dāng)d值較小時(shí)，可能局部連通性較低，但全局連通性較高。因此，選擇合適的d值會影響網(wǎng)絡(luò)的連通性。由于無線傳感器網(wǎng)絡(luò)中密鑰建立的最終目標(biāo)是形成盡可能高的全局連通性網(wǎng)絡(luò)，因此必須適當(dāng)選擇相鄰部署點(diǎn)的距離d的值。

表2所示為通過改變k來得到不同的d值獲得的局部連通性和全局連通性?？梢钥吹?，當(dāng)兩個(gè)相鄰單元格的兩個(gè)部署點(diǎn)之間的距離過小(k=0.4,0.6,0.8或1.0)時(shí)，在任意節(jié)點(diǎn)A，其周圍分布著許多非相鄰單元格的節(jié)點(diǎn)，這些節(jié)點(diǎn)不與節(jié)點(diǎn)A共享任何密鑰空間，因此降低了局部連通性和全局連通性；而當(dāng)選擇合適的部署點(diǎn)距離值時(shí)，模型能夠獲得較高的局部和全局連通性，如當(dāng)k=1.5時(shí)，全局連通性為0.999 0，即網(wǎng)絡(luò)中只有0.01%的節(jié)點(diǎn)是浪費(fèi)的。

表2 仿真結(jié)果

3.3 內(nèi)存開銷和運(yùn)行時(shí)間

在無線傳感器網(wǎng)絡(luò)協(xié)議設(shè)計(jì)中，長壽命是關(guān)鍵目標(biāo)。在本文模型中，我們最小化相鄰節(jié)點(diǎn)之間發(fā)現(xiàn)公用密鑰空間的廣播數(shù)據(jù)需求，1-跳廣播消息長度為：

節(jié)點(diǎn)ID的大小+ Rv的大小+3×H的大小(bits)

(14)

用于存儲從多項(xiàng)式得到的密鑰材料的內(nèi)存大小為：

M=3×(t+1)log2q+節(jié)點(diǎn)ID的大小+Rv的大小(bits)

(15)

這個(gè)值連同共享一個(gè)多項(xiàng)式的節(jié)點(diǎn)數(shù)量影響成對密鑰建立之前節(jié)點(diǎn)受攻擊的恢復(fù)能力。這將在3.4中詳細(xì)討論。

將本文模型與文獻(xiàn)[13]～[15]的模型在不同網(wǎng)絡(luò)規(guī)模下的內(nèi)存開銷即所需要的內(nèi)存大小進(jìn)行比較，結(jié)果如表3所示。從表3可見，不同模型隨著網(wǎng)絡(luò)規(guī)模的增大，內(nèi)存開銷也增大，這是因?yàn)橐瓿筛喙?jié)點(diǎn)間的密鑰空間計(jì)算、交換和配對，但是本文模型的內(nèi)存開銷始終是最小的。這是由于本文模型在密鑰建立階段將全部節(jié)點(diǎn)進(jìn)行集群分組，而且盡可能使傳感器節(jié)點(diǎn)均勻分布，減少了密鑰分配和建立階段計(jì)算空間的存儲開銷和信息交換。

表3 不同模型的內(nèi)存開銷比較

將本文方案與文獻(xiàn)[13]～[15]的模型在不同網(wǎng)絡(luò)規(guī)模下的的運(yùn)行時(shí)間進(jìn)行比較，結(jié)果如表4所示。從表4可以看到，不同模型隨著網(wǎng)絡(luò)規(guī)模的增大，運(yùn)行時(shí)間也是增加的，這是由于隨著節(jié)點(diǎn)數(shù)目的增大，不僅增加了節(jié)點(diǎn)部署和多項(xiàng)式分配的時(shí)間開銷，更重要的要花更多時(shí)間完成密鑰空間的計(jì)算和配對；但是本文模型在密鑰建立階段采用了密鑰材料的預(yù)加載和1-跳密鑰空間發(fā)現(xiàn)消息來實(shí)現(xiàn)相鄰節(jié)點(diǎn)的共享密鑰空間分配，所以仍然有最小的運(yùn)行時(shí)間。

表4 不同模型的運(yùn)行時(shí)間比較

運(yùn)行時(shí)間/ms網(wǎng)絡(luò)規(guī)模本文模型文獻(xiàn)[13]模型文獻(xiàn)[14]模型文獻(xiàn)[15]模型 N=2 0001 295 2 0791 664 1 648N=4 0002 045 2 8232 456 2 418N=6 0002 879 3 6763 246 3 217N=8 000 3 759 4 6864 245 4 203N=10 0004 768 5 7665 379 5 318

3.4 對捕獲節(jié)點(diǎn)攻擊的恢復(fù)能力

由于傳感器網(wǎng)絡(luò)工作環(huán)境通常比較惡劣，傳感器節(jié)點(diǎn)很容易被捕獲并泄露信息。捕獲的傳感器節(jié)點(diǎn)數(shù)量依賴于多項(xiàng)式的次數(shù)，也就是存儲密鑰材料的內(nèi)存。對捕獲節(jié)點(diǎn)攻擊的恢復(fù)能力定義為當(dāng)x個(gè)節(jié)點(diǎn)被攻破時(shí)，泄漏一個(gè)多項(xiàng)式的概率，這相當(dāng)于在未受損的傳感器節(jié)點(diǎn)之間泄漏直接密鑰。

文獻(xiàn)[14]表明，基于多項(xiàng)式的方案具有t-安全性：即除非公開了一個(gè)二元多項(xiàng)式的超過t個(gè)多項(xiàng)式共享，否則對手不會知道使用該多項(xiàng)式建立的非受損節(jié)點(diǎn)的成對密鑰。因此，本文模型的安全性依賴于共享同一多項(xiàng)式的傳感器節(jié)點(diǎn)的平均數(shù)量，即期望位于3個(gè)相鄰六邊形單元格中的傳感器節(jié)點(diǎn)的數(shù)量。

把期望位于一個(gè)單元格內(nèi)的傳感器節(jié)點(diǎn)的平均數(shù)量表示為Nc，則共享一個(gè)多項(xiàng)式的傳感器節(jié)點(diǎn)的平均數(shù)量可計(jì)算為：

(16)

式中，?為傳感器節(jié)點(diǎn)密度。

如前所述，存儲密鑰材料的內(nèi)存需求為M(bits)，因此二元多項(xiàng)式的次數(shù)為：

t=[M/3]-1

(17)

只要NG≤t，本文模型就能很好地抵抗節(jié)點(diǎn)捕獲。換句話說，受損的傳感器節(jié)點(diǎn)不會導(dǎo)致非受損傳感器節(jié)點(diǎn)之間共享的直接密鑰受損。

由于攻擊是隨機(jī)的，假設(shè)網(wǎng)絡(luò)中有一小部分傳感器節(jié)點(diǎn)pc被攻擊者破壞。在具有多項(xiàng)式共享的NG個(gè)傳感器節(jié)點(diǎn)中，正好有i個(gè)傳感器節(jié)點(diǎn)被攻擊的概率可以計(jì)算為：

(18)

因此，二元多項(xiàng)式被破壞的概率可計(jì)算為：

(19)

圖2所示為本文模型在不同部署點(diǎn)距離d節(jié)點(diǎn)受損攻擊時(shí)仿真得到的網(wǎng)絡(luò)恢復(fù)能力?？梢钥吹剑渴瘘c(diǎn)距離越長即單元格越大，對節(jié)點(diǎn)受損攻擊的網(wǎng)絡(luò)恢復(fù)能力越脆弱。這是因?yàn)楫?dāng)單元格較大時(shí)，在一個(gè)單元格中有更多的傳感器節(jié)點(diǎn)共享一個(gè)密鑰空間，從而導(dǎo)致安全性降低。

圖2 不同部署點(diǎn)距離下節(jié)點(diǎn)受損攻擊時(shí)網(wǎng)絡(luò)的恢復(fù)能力

圖3所示為本文模型在不同內(nèi)存大小M(bits)情形下節(jié)點(diǎn)受損攻擊時(shí)仿真得到的網(wǎng)絡(luò)恢復(fù)能力?？梢钥吹?，隨著內(nèi)存的增大，網(wǎng)絡(luò)的恢復(fù)能力增強(qiáng)，這是因?yàn)槎囗?xiàng)式的次數(shù)更高，就越不容易被攻擊破壞。

圖3 不同內(nèi)存大小情形下節(jié)點(diǎn)受損攻擊時(shí)網(wǎng)絡(luò)的恢復(fù)能力

圖4所示為不同模型的傳感器節(jié)點(diǎn)被攻擊時(shí)的網(wǎng)絡(luò)恢復(fù)能力比較?？梢?，與文獻(xiàn)[13]、[14]和[15]模型相比，本文模型在節(jié)點(diǎn)受損時(shí)的具有更好的安全性。這是由于本文模型存在密鑰預(yù)分配階段，而且離線服務(wù)器為每個(gè)集群生成一個(gè)包含足夠多的t次對稱二元多項(xiàng)式多池，然后將每個(gè)多項(xiàng)式分配給每個(gè)集群中的所有傳感器節(jié)點(diǎn)，以確保每個(gè)節(jié)點(diǎn)都要存儲3個(gè)t次二元多項(xiàng)式的共享知識，對手更難獲得融合多個(gè)節(jié)點(diǎn)的密鑰材料，從而提高了安全性。

圖4 傳感器節(jié)點(diǎn)被攻擊時(shí)不同模型的網(wǎng)絡(luò)恢復(fù)能力比較

4 結(jié)束語

本文提出了一種可實(shí)現(xiàn)的基于多項(xiàng)式的密鑰預(yù)分配模型，它利用了高斯分布的預(yù)部署知識。同時(shí)還表明了模型在網(wǎng)絡(luò)連通性、通信開銷和內(nèi)存需求等方面具有的優(yōu)勢。它還可以抵御非捕獲節(jié)點(diǎn)間受損附加密鑰的攻擊；未來的研究將集中在部署誤差率對網(wǎng)絡(luò)連通性的影響和分析多跳間接密鑰建立的可能性。