一種新的基于辛空間的密鑰預分配方案

陳尚弟 張俊梅

(中國民航大學 天津 300300)

1 引言

無線傳感器網絡是由若干低成本且資源有限的傳感器節點組成的一種分布式傳感器網絡，無線傳感器網絡技術是在計算機技術中的突破和創新，作為一種新型的信息收集和處理技術，具有耗能低、成本低、功能齊全等優點，有著非常廣闊的發展前景[1]。隨著它的廣泛應用，網絡安全問題也受到人們的重視。節點在部署到目標區域后容易受到敵方攻擊，如信息在傳輸時被竊聽、篡改、泄密等。在現代密碼學中，信息的保密性主要取決于密鑰的保密性，因此如何管理密鑰成為一個極具挑戰的問題。密鑰預分配是指節點在部署到目標區域前就將密鑰分配給各個傳感器節點。所有的密鑰預分配方案分為密鑰預分配階段、共享密鑰發現階段和路徑密鑰建立階段。

通常從以下4個方面來分析一個密鑰預分配方案是否可行：

(1)網絡規模：方案所能支持的最大傳感器節點數目。

(2)密鑰環大小：每個節點所能存儲的密鑰量。

(3)連通概率：網絡中任意兩個節點之間有共享密鑰的概率，通常用p表示。

(4)損失概率：當s個節點被捕獲時，一條隨機鏈接被破壞的概率，通常用f ail(s)來表示。

若某個節點被敵方捕獲，則該節點內存儲的所有密鑰均被泄露。假設節點Nk被捕，并且節點Na和節點Nb的 共享密鑰存儲在Nk中 ，此時Na和Nb之間的鏈接就斷開了，Na和Nb之間的鏈接稱為損失的鏈接。網絡的損失概率反映了網絡中節點的抗捕獲能力，損失概率越大，節點抗捕獲能力越弱。fail(1)為 當一個隨機節點被捕獲時，節點Na和Nb之間的鏈接被斷開的概率。由此可估算fail(s)=1?(1?fail(1))s。f ail(s)也可通過式(1)表達式直接求得

自Camtepe等人[2]首次提出利用組合設計構造密鑰預分配方案之后，許多基于組合設計的密鑰預分配方案被提出。2010年Pei等人[3]基于有限域上有理正規曲線構造了一個密鑰預分配方案，分析了基于該設計下的密鑰預分配方案的連通概率和損失概率。2015年Bag[4]將網絡分區，每個小區內有普通節點和簇頭兩種傳感器節點，簇頭的數量取決于小區的大小。2017年Chen等人[5]基于可分解設計和有限域上辛幾何構造了一系列密鑰預分配方案。2018年Kumar等人[6]將網絡分區，限制每個小區內的簇頭數量為3，且將每個小區的通信范圍限制在給定小區的 Lee球體區域內。這種做法既提高了節點的抗捕獲能力又降低了對節點的存儲要求。2019年Akhbarifar等人[7]描述了一種可擴展的無線傳感器網絡安全模型，并提出了一種基于組合設計的混合密鑰預分配方案。提出了無線傳感器網絡的安全性仿真方法，并與以往的類似方案進行了比較。同年袁琪等人[8]基于w?平衡不完全區組設計構造了一個密鑰預分配方案。2020年Pang等人[9]分析了基于正交陣列漢明距離的密鑰預分配方案中用于評估連通性和彈性的度量的計算可以簡化。隨后在文獻[10]中給出精確的基于正交陣列的密鑰預分配方案的彈性的計算公式。研究了基于正交陣列的廣播增強密鑰預分發方案的連通性和彈性。同年Choudhary等人[11]提出了一種基于多項式的密鑰預分配方案，討論和分析了不同的密鑰分發協議，并提出了基于稀疏矩陣的高度安全的多項式池密鑰分發技術，以降低存儲和計算復雜度。2021年Belim等人[12]提出了一個廣義的密鑰預分配方案，密鑰材料是基于向量空間元素和向量空間上的對稱算子形成的。

近年來國內外對密鑰預分配方案的研究很多，但基于各參數未達到最優，本文將在這一方面做研究。本文利用有限域上辛空間中子空間之間的正交關系構造了一個組合設計，并基于該設計構造一個密鑰預分配方案。與其他方案相比本方案中節點的抗捕獲能力非常好，并且隨著網絡規模的擴大，方案的連通概率逐漸趨于1。本文創新點為基于有限域上的辛空間構造了一個組合設計，并基于該設計構造了一個密鑰預分配方案。基于辛空間構造的密鑰預分配方案較少，方法上具有一定的創新性。

2 預備知識

本節介紹組合設計(區組設計)和有限域上辛空間相關知識，其中辛空間的相關概念定理均參見文獻[13]。

2.1 組合設計

定義1[14]令X和B是兩個不相交的有限集合，I為X與B之 間 的2 元 關 系，即X?X×B。D=(X,B,I)為 一個關聯結構，X中的元素稱為點，B中的元素稱為區組，I稱為關聯結構。設x∈X,B∈B，若(xi,Bj)∈I， 則稱點xi與 區組Bj關 聯，并記作xiIBj。

當D=(X,B,I)為有限關聯結構時，通常記|X|=v, |B|=b。為方便X(B)表示與一給定的區組相關聯的點的集合，B(x)表示與一給定的點相關聯的區組的集合，并記|X(B)|=k, |B(x)|=r。另用δ表示與兩個不同的區組同時關聯的點數。

定義2 令v,k,λ,t均為正整數，且v≥k ≥2,λ ≥1,t≤k。D=(X,B,I)是一個關聯結構，2元組(X,B)是 一個部分平衡t?(v,k;λ,0)區組設計，如果滿足下列條件：

(1) |X| = v 。

(2)對任意的B∈B, |B|=k。

(3)X的任意t元子集要么在B的0個區組中同時出現，要么在B的λ個區組中同時出現。

2.2 辛空間

對于Fq上 的2υ×2υ矩陣T，如果TKTT=K，則稱T是關于K的 一個辛矩陣。顯然2υ×2υ階的辛矩陣關于矩陣的乘法構成了一個群，稱為Fq上 的關于K的 2υ階 辛群，記作S P2υ(Fq,K)， 簡記為S P2υ(Fq)。

定理4Fq上 2υ維辛空間中，一給定的(m,s)型子空間中的 (m1,s1) 型子空間的數目N(m1,s1;m,s;2υ)是

3 基于辛空間的密鑰預分配方案的構造

本節利用辛空間V中的( 1,0)型 子空間和( 2,1)型子空間構造一個組合設計，并基于該設計構造了一個密鑰預分配方案。將整個目標區域劃分為若干個大小相同的小區域，每個小區有普通節點和簇頭兩種類型的傳感器節點，簇頭的計算、存儲以及通信能力都優于普通節點。同一小區內的節點或者通過它們之間的共享密鑰直接通信，或者通過小區內的簇頭間接通信，不同小區內的節點只能通過簇頭建立通信。

3.1 部分平衡 2?設計的構造

此時X稱為點集，B稱為區組集。

對x∈X,B∈B， 定義x與B關 聯當且僅當x⊥B。即x與B關 聯當且僅當( 2,1)型 子空間x與( 1,0)型子空間B是正交的。

定理5X中任意兩個不同的點或者與B中0 個區組關聯，或者與 1個區組關聯，即λ= 0 或 1。則(X,B) 是一個部分平衡2?(q4+q2,q2;1,0)區組設計。

證明 令x1和x2是X中任意兩個不同的點，則x1和x2為V中 兩 個不同 的( 2,1) 型 子 空間，并 且dim(x1+x2)=3 或4。

若dim(x1+x2)=3 ，根據2υ維辛空間中存在(m,s)型 子空間的條件，x1+x2是 一個( 3,1)型子空間。 則 (x1+x2)⊥是 一 個( 1,0)型 子 空 間， 故λ=N(1,0;1,0;4) = 1。

若dim(x1+x2)=4 ，則x1+x2是 一 個( 4,2)型子空間，(x1+x2)⊥= { 0} ，故λ= 0。

綜上(X,B)是 一個部分平衡2?(q4+q2,q2;1,0)區組設計。 證畢

定理6B中任意兩個不同的區組B1和B2至多與一個點同時關聯。

證明令B1和B2是B中任意兩個不同的區組，則B1和B2為V中兩個不同的( 1,0)型子空間，且dim(B1+B2)=2 ， 同理B1+B2或 者是一個( 2,0)型子空間或者是一個( 2,1)型子空間。

如果B1+B2是 一個( 2,0)型 子空間，則(B1+B2)⊥是一個( 2,0)型 子空間，因此δ=N(2,1;2,0;4)=0。

如果B1+B2是一個( 2,1)型子空間，同樣地(B1+B2)⊥是一個( 2,1) 型子空間，因此δ=N(2,1;2,1;4)=1。 證畢

由此，本文基于辛空間構造了一個組合設計，并計算了該設計的全部參數。

3.2 基于部分平衡 2?設計的密鑰預分配方案的構造

將上述組合設計中的點集與密鑰池中的密鑰建立一一對應的關系，區組與方案中的節點建立一一對應的關系。與每個區組相關聯的點數即為每個節點所能存儲的最大密鑰量，即密鑰環的大小。密鑰環即為與一給定的 ( 1,0) 型 子空間正交的( 2,1)型子空間的個數。特別地，基于該設計的密鑰預分配方案中任意兩個不同的節點至多有一個共享密鑰。部分平衡 2?(q4+q2,q2;1,0)設計到密鑰預分配方案的對應關系如表1所示。

3.3 方案設計

將整個部署區域劃分為若干個大小相同的小區域，Ci表 示網絡中第i個小區，每個小區包含普通節點和簇頭兩種類型的傳感器節點。每個小區內的普通節點均采用基于部分平衡2-設計的密鑰預分配方案，不同小區內節點所用密鑰池各不相同，因此不同小區內的節點無法直接通信。簇頭之間采用完全密鑰預分配方式分發密鑰，即任意兩個簇頭之間都有共享密鑰。本方案中簇頭不僅要為同一小區內兩個沒有共享密鑰的普通節點建立間接通信，還要為不同小區內需要通信的兩個節點建立間接通信。接下來介紹同一小區內普通節點與簇頭如何通信，不同小區內的簇頭如何通信。

3.3.1 小區內普通節點與簇頭節點的通信方式

由于任意兩個普通節點至多共享 1個密鑰，方案的連通概率小于1。為使每個小區內沒有共享密鑰的兩個節點也能通信，考慮利用簇頭作為中間節點為沒有共享密鑰的兩個節點建立間接通信。如何建立簇頭與普通節點之間的通信是一個至關重要的問題。

基本密鑰協議的主要思想是節點部署到目標區域之后，需要通信的兩個節點通過密鑰協商的方式建立它們之間的共享密鑰。如節點Na與其通信范圍內的節點Nb需 要通信時，Na從密鑰列表中隨機選擇一個密鑰ki廣 播，節點Nb接 收到ki后隨機產生一個密鑰kij，隨后將密鑰kij和其身份標識符j用ki加密之后再發送給Na。節點Na將傳回的信息用ki解 密之后就可得到它們之間的共享密鑰kij以及身份標識信息。這樣節點Na和Nb就協商了一個密鑰。

本文方案中每個小區內的普通節點和簇頭之間的通信采用基本密鑰協議。具體方法如下：在節點部署前預先為每個簇頭存儲Fq(8)V中的一個1 維子空間，當同一小區內的普通節點和簇頭需要通信時，這個普通節點從密鑰列表中隨機產生一個密鑰ki并廣播給簇頭。由3.2節知，每個密鑰與V中一個1 維子空間對應，于是簇頭利用ki和 預先存儲的1 維子空間生成一個2維子空間，生成的這個子空間就作為普通節點和簇頭的共享密鑰，記為kij。密鑰kij使用ki加密之后再發送給這個普通節點，這樣普通節點與簇頭就可相互通信。

3.3.2 不同小區內簇頭間的通信方式

每個小區內放置3個簇頭，且3個簇頭所用密鑰池各不相同。依據所用密鑰池的不同，簇頭可分為3類，同類簇頭可相互通信，不同類型的簇頭無法通信。每個小區內的簇頭用 C Hij表示，其中i表示網絡中第i個 小區，j表示簇頭的類型。例如C H11,CH12和C H13分別表示網絡中第1個小區內的3種類型的簇頭。假設目標區域被劃分為N個小區，則1≤i ≤N, 1≤j ≤3，不同小區內同一類型的簇頭

2 ?(q4+q2,q2;1,0)部分平衡 區組設計 密鑰預分配方案v =|X|=N(2,1;4)=q4+q2 密鑰池大小b=|B|=N(1,0;4)=q3+q2+q+1 方案所能支持的最大傳感器節點數目k =|X(B)|=N(2,1;3,1;4)=q2 密鑰環大小r =|B(x)|=N(1,0;2,1;4)=q+1 包含一給定密鑰的節點數目δ =0或1 任意兩個節點共享的密鑰量

表 1 部分平衡2?(q4+q2,q2;1,0)設計到密鑰預分配方案的對應關系采用完全密鑰預分配方式分發密鑰，所謂完全密鑰預分配即為每個簇頭存儲N?1個 密鑰，這N?1個密鑰恰好為這個簇頭分別與其他N ?1個小區內同類簇頭的共享密鑰。這樣任意兩個同類簇頭均有共享密鑰，簇頭之間的連通概率為1。但隨著小區數量增加，簇頭存儲的密鑰數越來越多，對簇頭的存儲要求會越來越高。

基于上述考慮將每個小區的通信范圍限制在其Lee球體[15]區域內。Lee距離為ρ的Lee球體是由所有與選定小區距離不超過ρ的小區組成的。任意兩個小區之間的距離為這兩個小區的水平距離和垂直距離之和。因此以Ci為 中心的Lee距離為ρ的Lee球體中有2ρ(ρ+1)個 小區(除Ci)，故小區內每種類型的簇頭只需存儲2ρ(ρ+1)個密鑰。此時每個簇頭存儲的密鑰量遠少于未限制小區通信范圍之前所需存儲的密鑰量。例如當目標區域被劃分為 9個小區，且Lee距離為1時，圖1實線區域為C5的Lee距離為1的Lee球體區域。

圖1 ρ = 1 時C 5的Lee球體區域

4 分析

4.1 小區內的連通概率

雖然這個方案的連通概率沒有達到1，但是隨著網絡規模的不斷擴大，連通概率逐漸趨于1。

4.2 損失概率的估算

網絡中的節點易受敵方攻擊，當一個節點被敵方捕獲時，該節點內的所有密鑰均被泄露。損失概率反映了網絡中節點的抗捕獲能力，損失概率越低，節點的抗捕獲能力越強。網絡的損失概率分為局部損失概率和全局損失概率。局部損失概率指一個小區內S個普通節點被捕后，任意兩個未被捕獲的普通節點之間鏈接斷開的概率。全局損失概率指S′個簇頭被捕后，任意兩個小區之間的鏈接被斷開的概率。

4.2.1 局部損失概率

對于任意一對給定的節點Na和Nb，假設它們之間有一個共享密鑰k。由于密鑰k存儲在r個節點中，捕獲除Na和Nb外 其余r?2個節點中的任意一個都會使密鑰k泄露，此時節點Na和Nb之間的鏈接被破壞。 fail(1)為隨機捕獲一個節點，使得節點Na和Nb之間的鏈接被破壞的概率。于是

圖2為不同網絡規模下(q取不同值時)，隨著捕獲的節點數量逐漸增多，網絡的損失概率逐漸增大。且捕獲相同數量的節點時，網絡規模越大，損失概率越小。

圖2 損失概率圖

假設一共有S個普通節點被捕獲，當目標區域被劃分為N個小區時，平均每個小區內有S/N個普通節點被捕獲，于是局部損失概率大致估算為

由表2可知，當捕獲節點數量較多時，網絡中的節點仍然具有良好的抗捕獲能力。這表明將整個目標區域分為若干小區的方法極大地提高了網絡中節點的抗捕獲能力。

表2 當q =4 , q =5 , q =7 , q =8時的局部損失概率

4.2.2 全局損失概率

同Kumar等人[6]一樣將小區之間的鏈接稱為主鏈接，簇頭之間的鏈接稱為2次鏈接。若Ci和Cj是兩個不同的小區，則Ci和Cj之間存在一條主鏈接。假設Ci1,Ci2和Ci3是Ci中 的3個簇頭，Cj1,Cj2,Cj3是Cj中的3個簇頭。此時有3條2次鏈接，分別為Ci1和Cj1,Cj2和Cj2,Ci3和Cj3。顯然2次鏈接的數量是主鏈接的3倍。在估算全局損失概率時只考慮當S′個簇頭被捕時主鏈接的斷開情況，全局損失概率數學表達式為

事畢，我側臥在沙發上，看見月亮高高地掛在客廳落地窗的上方，地板上那片朦朧的金色月光被玻璃拉門的對扇隔檔切為兩半。

當把每個小區的通信范圍限制在其Lee球體區域內時，靠近部署邊界的小區的Lee球體區域內所包含的小區數量減少，1個小區至多關聯2ρ(ρ+1)條主鏈接。所以整個網絡中至多有Nρ(ρ+1)條主鏈接。事實上，1條主鏈接斷開當且僅當這兩個小區內的3條2次鏈接都要斷開，且捕獲一個簇頭時至多有 2ρ(ρ+1)條 2次鏈接斷開。當S′個簇頭被捕時，可分為下列3種情況：

(1)捕獲的S′個簇頭中只包含其中1種類型的簇頭，則有2S′ρ(ρ+1)條2次鏈接斷開。

(2)捕獲的S′個簇頭中僅包含其中2種類型的簇頭，若類型1簇頭有X個，則有2Xρ(ρ+1)+2ρ(S′?X)(ρ+1)條2次鏈接斷開。

(3)捕獲的這S′個簇頭中包含3種類型的簇頭，假設類型1簇頭有X個，類型2簇頭有Y個，此時有2Xρ(ρ+1)+2Y ρ(ρ+1)+2ρ(S′?X ?Y)(ρ+1)條2次鏈接斷開。

只有在第3種情況發生時，才有可能將兩個小區間的3條2次鏈接都斷開，才有可能斷開1條主鏈接。實際中無法確定捕獲的簇頭包含幾種類型及每種類型的簇頭被捕獲的數量，因此無法得到全局損失概率的理論值。但依據簇頭所采用的密鑰預分配方案，未被捕獲的簇頭之間的鏈接不會被斷開，故簇頭之間的損失概率是極小的。

4.3 節點斷開的估算

當捕獲的節點數量足夠多時，存在未被捕獲的節點所含密鑰泄露的情況。此時該節點不能再使用， 這類節點稱為從網絡中斷開的節點。考慮至少捕獲多少普通節點才能從網絡中斷開一個未被捕獲的普通節點。

因為每個節點都存儲q2個密鑰，并且任意兩個普通節點至多共享一個密鑰，因此至少要捕獲q2個節點才可能斷開小區內的一個普通節點。若整個網絡中一共有K個普通節點被捕獲，平均每個小區捕獲K/N，因此需要滿足K/N ≥q2， 即K≥Nq2。

例如當q= 5時 ，網絡被劃分為9 00個小區，則每個小區有1 56 個節點，每個節點有2 5個密鑰。為了斷開一個未捕獲的節點至少需要捕獲22500個節點。實際上，這是一個非常大的數，因此很難將一個節點從網絡中斷開。

由于簇頭采用完全密鑰預分配方式分配密鑰，因此無論捕獲多少簇頭都不會使得未被捕獲的簇頭從網絡中斷開。

5 與一些其他方案的比較

本節將本文方案與一些其它方案就連通概率、局部損失概率進行比較。因方案設計上的差異，有些方案(除Kumar方案外)并沒有區分局部損失概率和全局損失概率，因此比較時將我們方案的局部損失概率和其他方案的損失概率進行比較。圖3和圖4分別為連通概率和損失概率對比圖，表3給出各個方案的參數。表4為符號表。

表3 各個方案的參數

表4 符號表

圖3 連通概率對比圖

Pei等人[3]基于有限域上有理正規曲線構造了一個密鑰預分配方案，記為RNC。將射影空間PG(n,Fq)中 的點看作區組設計中的點集，PG(n,Fq)中所有有理正規曲線作為區組集構造了一個強部分平衡設計。當n= 2時，基于該設計下的密鑰預分配方案具有良好性能。該方案的連通性隨著密鑰環的增大而逐漸下降，連通概率劣于本文方案，且隨著節點捕獲數量的增加，損失概率逐漸趨于1，遠高于我們方案的損失概率。

Kumar等人[6]利用對稱設計構造了一個密鑰預分配方案，也將部署區域劃分為若干個大小相同的小區。雖然方案的連通概率恒為1，優于我們的方案，但由圖4可知捕獲相同數量的普通節點時，該方案的局部損失概率高于我們方案的局部損失概率。且由于該方案簇頭之間采用基于對稱設計的密鑰預分配方案，因此當捕獲足夠多的簇頭時存在未被捕獲的簇頭從網絡中斷開的情況，而本文方案無論捕獲多少簇頭均不會有這種情況。

Bechkit等人[16]基于一種組合設計構造了一個密鑰預分配方案，記作NU-KP。由于該方案連通概率較低。于是為了提高方案的連通概率作者將該方案修改進一步提出方案t-UKP。在與t-UKP比較中取t=2。從圖3和圖4可看到，這兩個方案的連通概率以及節點的抗捕獲能力均不及本文方案。

圖4 損失概率對比圖

袁琪等人[8]基于3維空間構造w-平衡不完全區組設計，并基于該設計構造了密鑰預分配方案，記作Ex-w-BIBD。該方案連通概率較差，且損失概率也遠高于本文方案的損失概率，方案的各個性能較差。

Ruj等人[17]提出了成對和三重密鑰分配，該方案記作TKP。該方案中密鑰鏈大小為k，且4≤k≤q。 方案所能支持的最大傳感器數目為2q2。雖然該方案的損失概率較低，但仍然高于我們方案的損失概率，且該方案網絡的連通性較差，遠低于本文方案的局部連通概率。

圖3為本文方案與其他幾個方案在密鑰環大小相近時，方案的連通概率對比圖。其中各個方案的密鑰環大小在4,9,16,25,49,64,81,121,169,256,289這些值上下輕微波動。圖4為網絡規模相近時，本文方案與其他幾個方案在捕獲相同節點數時，方案的局部損失概率對比圖。特別地，RNC中q=4，NU-KP中q=5 ，2-UKP中q=7，Kumar方案中q=9 ，Ex-w-BIBD中q=8 ，以及TKP中q=23。從中可看到本文方案在連通概率逐漸趨于 1時還能保證較低的損失的概率。

6 結束語

本文基于有限域上辛空間中子空間之間的正交關系構造了一個新的組合設計。將目標區域劃分為若干個大小相同的小區，每個小區有普通節點和簇頭兩種傳感器節點。同一小區內的節點采用基于有限域上辛空間構造的密鑰預分配方案來分配密鑰，小區內的節點或者通過共享密鑰直接通信，或者通過簇頭間接通信。簇頭之間采用完全密鑰預分配方式分配密鑰，不同小區內的節點必須通過簇頭建立通信。

與其他方案相比本文方案既降低了網絡的損失概率，又保證了在網絡規模逐漸增大時網絡的連通概率逐漸趨于1，即并沒有以嚴重犧牲網絡的連通概率來提高節點的抗捕獲能力。此外將網絡分區的方法也有效地提高了網絡中節點的抗捕獲能力，并降低了對方案中所能支持的最大傳感器數目的要求。但本方案仍有不足之處，與其他方案相比相同規模下本文方案中每個節點存儲的密鑰量較多，需要進一步研究和改進。