大規模Ａｄ ｈｏｃ網絡中一種高效的組密鑰協商協議

摘要：移動Ad hoc網絡自身的特點決定了該網絡中節點資源的有限性，所以在移動Ad hoc網絡中構建組密鑰協商協議時，應盡量減少節點的資源開銷。為了解決這個問題，提出了一種基于分簇－K叉樹組模型結構的組密鑰協商協議——CKT－ECC協議。該協議在分簇－K叉樹組模型結構上，采用橢圓曲線密碼體制實施密鑰協商和分配，使得節點在密鑰協商過程中具有低計算開銷和低通信開銷的優勢。與GDH、TGDH組密鑰協商協議相比，本協議有效地降低了節點在密鑰協商過程中的計算開銷和通信開銷，適用于大規模移動Ad hoc網絡。

關鍵詞：Ad hoc網絡； 組密鑰協商； 橢圓曲線； 簇； K叉樹

中圖分類號：TP309.7

文獻標志碼：A

文章編號：1001－3695(2008)06－1817－05

移動Ad hoc網絡是一種新型的移動多跳無線網絡，與傳統的無線網絡不同，它不依賴于任何固定的基礎設施和管理中心。其特點是動態的拓撲結構、有限的資源、多跳的通信以及脆弱的網絡安全等。顯然傳統的密鑰協商協議不能夠直接應用于移動Ad hoc網絡。根據移動Ad hoc網絡自身的特征，在該網絡中進行密鑰的協商和分配時，必須做到不占用節點大量的資源；同時還要求所設計的密鑰協商協議能夠適用于大規模的移動Ad hoc網絡。

文獻[1~3]提出的GDH組密鑰協商協議中，最后一個組成員相當于整個組的控制者，它承擔了大量的計算和通信工作，需要具有較高的能量。而移動Ad hoc網絡中所有節點的資源都是有限的，且能量較低，因此在大規模移動Ad hoc網絡中采用GDH協議進行密鑰協商和分配時會受到單個節點自身資源的限制。文獻[4]提出的TGDH協議避免了單個節點承擔過多計算和通信開銷的問題，但該協議中每個節點均要分擔較多的計算和通信開銷。因而，該協議也很難適用于大規模移動Ad hoc網絡。

文獻[1~4]所提出的組密鑰協商協議都沒有很好地解決在大規模移動Ad hoc網絡中進行組密鑰協商時，所遇到的節點能量受限問題。這就使得在移動Ad hoc網絡中應用這些組密鑰協商協議時會受到網絡規模的限制。

本文提出了一種高效的適用于大規模移動Ad hoc網絡的組密鑰協商協議CKT－ECC協議，該協議較好地解決了在大規模移動Ad hoc網絡中，進行密鑰協商與分配時所遇到的節點能量受限問題。CKT－ECC協議在分簇－K叉樹組模型結構上，采用橢圓曲線密碼體制實施密鑰協商和分配，使得節點在密鑰協商過程中具有低計算開銷與低通信開銷的優勢。本協議與GDH、TGDH組密鑰協商協議相比，有效地降低了節點的計算和通信開銷，適用于大規模的移動Ad hoc網絡。

1DECA聚簇算法描述

DECA[5]聚簇算法能夠將移動Ad hoc網絡中的所有節點劃分成互不相交的簇，并為每個簇選擇一個合適的簇頭管理該簇。根據網絡情況周期性地運行該算法可以有效地保證網絡劃分的合理性以及產生的簇頭的合理性。

DECA聚簇算法中每個節點都維護一張鄰居列表。定義myScore函數為myScore=w1E+w2C+w3I。其中：E 表示節點的剩余能量；C表示節點的連通性；I表示節點標志號，且∑3j=1wi=1。myScore函數用來計算某個節點聲明它自身為簇頭的延遲時間。延遲時間的值通常在0到設定的上限Dmax值之間，其中Dmax是一個需要小心選擇的參數。為了保證該算法能夠快速地在一定的時間內結束，設定了該算法結束的最大時間值Tstop，這個參數的選擇需要考慮到節點的計算能力以及節點的移動性。

DECA聚簇算法共分為三個階段，其代碼如下：

a)Start－Clustering－Algorithm ( )

(a)myScore=w1E+w2C+w3I;

(b)delay= (1000-myScore)/100;

(c)if (delay<0)

(d)then broadcastCluster (myId， myCid， myScore);

(e)else delay Announcement);

(f)Schedule clustering termination.

b)Receiving－Clustering－Message (id， cid， score)

(a)if (id==cid)

(b)then if (myCid==UNKNOWN)

(c)then if (score>myScore)

(d)then myCid=cid;

(e)cancelDelayAnnouncement ( );

(f)broadcastCluster (myId， myCid， score);

(g)else if (score>myScore)

(h)then if (myId==myCid)

(i)then needConversion=true;

(j)else convertToNewCluster ( );

c)Finalize－Clustering－Algorithm ( )

(a)if (needConversion)

(b)then if (! amIHeadforAnyOtherNode ( ))

(c)then converToNewCluster ( );

(d)if (myCid==UNKNOWN)

(e)then myCid=cid;

(f)broadcastCluster (myId， myCid， score);

DECA聚簇算法具有如下幾個特征：a）DECA聚簇算法可以在一定的時間內結束；b）DECA聚簇算法結束后網絡中的每個節點都將屬于且僅屬于一個簇；c）DECA聚簇算法結束后每個簇中的任意兩個節點之間的距離不超過兩跳；d）在整個算法執行過程中每個節點僅發送一次消息；e）該算法的時間復雜度為O(|n1|)。其中：n1為組規模，即移動Ad hoc網絡中節點總數。

2分簇－K叉樹組模型密鑰協商方案(CKT－ECC)

2．1符號

分簇－K叉樹組模型密鑰協商方案(CKT－ECC)中使用到的符號如下：

K：K叉樹的度。

h：分簇－K叉樹組模型中K叉樹的深度。

n1：組規模，即移動Ad hoc網絡中節點總數。

n：組規模為n1時，在移動Ad hoc網絡中由DECA聚簇算法產生的簇的總數。

CLs：第s個簇。 其中：s∈[0，…，n-1]。

CGCLs：第s個簇的簇頭。

ts：簇 CLs中的節點總數。

2．2分簇-K叉樹組模型結構描述

周期性地運行上文所描述的DECA聚簇算法，組規模為n1的移動Ad hoc網絡被劃分成n個適合的子組稱為簇，且每個簇由DECA聚簇算法產生的簇頭進行管理。將每一個簇看成一個邏輯節點，由文獻[6]容易構建K叉樹。分簇－K叉樹組模型節構如圖1所示。設定L0層為分簇－K叉樹組模型節構中根節點所在的最高層，Lh-1層為該結構中的最底層。其中每一個葉子節點對應于移動Ad hoc網絡中的一個簇，其他中間節點為邏輯節點。若簇總數為n=（Kh-1)/(K-1)，則K叉樹為滿K叉樹，除根節點以外，每一層Li（i∈[1，…，h-1]）中含有Ki-1個子組，每個子組含有K個組成員。若簇總數n<(Kh-1)/(K-1)，則根據K叉樹構建算法所得到的K叉樹具有完全K叉樹的某些性質：a）葉子節點只可在層次最大的兩層上出現；b）對任一節點，若其右分支下的子孫的最大層次為l，則其左分支下的子孫的最大層次必為l或l+1。

葉子節點中的組成員U(Lm)(j，k)(m=h-1，h-2)由相應的簇CLs中的簇頭CHCLs充當，即U(Lm)(j，k)=CHCLs。其中：k=s。每個子組SG(Li)j中的第二個組成員充當該子組的子組控制者U(Li)(j，jK+1)=U(Li)SGj，管理SG(Li)j子組。若K叉樹為滿K叉樹，則除了最底層Lh-1層，每層中的子組成員U(Li)(j，k)(Li≠Lh-1)同時也是下一層Li+1層中子組Li+1的子組控制者[7]U(Li)(j，k)=U(Li+1)SGk。若K叉樹不是滿K叉樹而是根據K叉樹構建算法，所得到的具有完全K叉樹某些性質的普通K叉樹，則情況類似。

密鑰路徑概念定義如下：從簇CLs葉子節點開始到K叉樹根節點的路徑稱為CLs密鑰路徑KPs。Ks@KPs表示密鑰路徑KPs上所有的子組密鑰。簇CLs中的每個組成員都將存儲Ks@KPs以及K叉樹的樹型結構。

下面所討論的組密鑰協商協議是基于分簇-滿K叉樹組模型結構的，對于其他分簇－K叉樹組模型結構情況類似。

2．3基于分簇－K叉樹組模型的組密鑰協商

本節在2．2節所描述的分簇－滿K叉樹組模型結構上討論如何進行組密鑰的協商和分配。

2．3．1分簇－K叉樹組模型中簇密鑰協商協議

當DECA聚簇算法結束后，組規模為n1的移動Ad hoc網絡劃分成n個互不相交的簇，每個簇都有一個簇頭對該簇進行管理。每個簇中的所有節點依次排列，將myScore的值為第二大的節點排列在第一位，簇頭排列在第二位，其他節點任意依次排列。則在分簇－滿K叉樹組模型的最底層Lh-1層中，簇CLs內的密鑰協商協議如下：

2．3．2分簇－K叉樹組模型組密鑰協商協議

分簇－K叉樹組模型密鑰協商過程共分為三個階段：首先最底層Lh-1層中的所有簇按照2.3.1所描述的簇內密鑰協商協議進行密鑰協商，獲取簇CLs的簇密鑰KCLs，再按類似方法計算Lh-1層中每個子組的子組密鑰；然后Lm層m∈[h-2，…，1]中的每個子組再按照類似的方法分別獲取相應的子組密鑰，直到得到最終的組密鑰K=KSG0(L1)；最后通過安全信道將組密鑰以及相對應的子組密鑰傳送給所有相對應的子組成員和節點。其具體過程如下：

2．4密鑰更新

基于CKT－ECC組密鑰協商協議的密鑰更新方法類似CKT－ECC組密鑰協商協議的執行過程。

1)節點的加入

當有新合法節點Un1+1加入，且此時為簇更新周期之間，則在保持簇總數n不變的情況下，新合法節點Un1+1就近加入某一個簇CLs。該簇中的所有節點包括新加入的節點，重新計算自身的myScore值，選擇新的簇頭管理該簇，并重新運行簇密鑰協商算法，獲取新的簇密鑰KCLs。此外，簇CLs密鑰路徑KPs上的所有子組重新運行子組內密鑰協商協議，更新密鑰路徑KPs上的所有子組密鑰。當組密鑰K的更新完成后，將更新后的子組密鑰從頂層通過安全信道分發給相對應的組成員和節點。

當有新合法節點Un1+1加入且此時為簇更新周期，則在DECA聚簇算法結束后，重新構建分簇－K叉樹組模型，運行CKT－ECC組密鑰協商協議實施新的密鑰協商和分配。

2)節點的退出

當簇CLs中的節點U(s，c)退出時，且該節點不是簇頭CHCLs(CHCLs≠U(s，c))，并且此時正處于簇更新周期之間，則簇內其他節點U(s，t)（t≠c， c∈[0，…， ts-1]）在接收到節點U(s，c)的退出請求后，刪除該節點U(s，c)的信息，重新運行簇內密鑰協商算法，更新簇密鑰KCLs；然后所有位于簇CLs密鑰路徑KPs上的子組都重新運行子組內密鑰協商協議，更新Ks@KPs。組密鑰K的更新完成后，同樣從最高層將更新后的子組密鑰通過安全信道分發給相對應的組成員和節點。若簇CLs中要求退出的節點U(s，c)是該簇的簇頭(CHCLs=U(s，c))，并且此時正處于簇更新周期間，則在刪除節點U(s，c)信息之后，簇CLs中的所有節點重新計算自身的myScore值，選擇新的簇頭管理該簇；并按類似方法進行簇內密鑰與Ks@KPs的更新和分配。

當簇CLs中的節點U(s，c)退出時，且此時為簇更新周期，則在DECA聚簇算法結束后，重新構建分簇－K叉樹組模型，運行CKT－ECC組密鑰協商協議實施新的密鑰協商和分配。

3安全性分析

該協議的安全性基于三方面：a）橢圓曲線密碼體制; b）對稱密鑰加密模式的安全性; c）用于組成員認證的簽名模式的安全性。

3)密鑰分配的安全性

密鑰從最高層分發到相應的子組成員和節點的過程中，密鑰是通過安全信道進行傳輸的，即采用安全的對稱密鑰加密模式進行加密。若采用的對稱密鑰加密模式能夠抵抗密文攻擊，則攻擊者無法獲取簇密鑰、子組密鑰和組密鑰，除非攻擊者能破解對稱密鑰加密模式。

4)具有抗假冒攻擊性

本協議采用可抵抗存在性偽造的簽名算法(如Schnorr)對合法節點的身份進行認證，以抵御攻擊者偽造簽名冒充合法節點的攻擊，實現抗假冒攻擊。

5）具有前向后向安全性

假設攻擊者B在某個時間，是該組中的合法節點。則在CKT－ECC組密鑰協商協議中，當B作為合法節點加入某個簇CLs時，根據密鑰更新過程，簇CLs重新運行簇密鑰協商算法，產生新的簇密鑰。并且簇CLs密鑰路徑KPs上的所有子組均重新運行子組內密鑰協商協議，對密鑰路徑KPs上的所有子組密鑰進行更新，然后將更新的子組密鑰通過安全信道發送給相應的組成員和節點。因此，攻擊者無法獲取其加入前的簇密鑰，組密鑰以及任何子組密鑰。由前面的安全性分析知該攻擊者在不知道任何簇密鑰，子組密鑰以及組密鑰的情況下，將無法破解組內節點在其加入前的通信內容，保證了后向安全性。

同理，當B退出后，B原先所在的簇CLs將對其簇密鑰進行更新，該簇CLs密鑰路徑KPs上的所有子組也相應地更新原有的子組密鑰，并將更新后的子組密鑰通過安全信道進行分發。這樣B原先所知道的簇密鑰，組密鑰以及所有子組密鑰都進行了更新。所以B除非重新加入組，否則將無法破解它離開后組內節點所發送信息的內容，保證了前向安全性。

4性能分析

從計算復雜度和通信復雜度兩方面分析CKT－ECC協議性能。該協議在計算復雜度和通信復雜度這兩方面與TGDH、GDH協議的比較如表1所示。計算代價為指數運算次數。其中，CKT－ECC協議中指數運算指橢圓曲線離散指數運算，其他指有限域離散指數模運算。由文獻[11]知，指數計算量要遠遠高于對稱密鑰的加/解密計算量。因此與指數運算開銷相比，忽略對稱密鑰加/解密的計算開銷。通信代價為節點發送和接收消息數。表1中的h表示分簇－K叉樹組模型中K叉樹的深度或者表示TGDH協議中樹的高度；n1表示組規模；n表示在組規模為n1時，分簇－K叉樹組模型中簇的總數，顯然n＜n1。CKT－ECC協議中h=logkn，TGDH協議中h=log2n1。

CKT－ECC協議中的users指最底層Lh-1層中每個簇CLs中的第二個到第ts-1個節點，其指數運算次數為3，發送消息數為2，接收消息數為4。最底層Lh-1層中每個簇CLs中的第一個節點在簇內密鑰協商過程中的指數運算次數為ts次，發送消息數為1次，接收消息數為ts+1次。第ts個節點在該簇內的密鑰協商過程中的指數運算次數為3，發送消息數為2，接收消息數為3。同理，最底層Lh-1層中每個子組中的第二個到第K-1個組成員，其指數運算次數為6，發送消息數為5，接收消息數為7。第一個組成員的指數運算次數為K+3次，發送消息數為4次，接收消息數為K+4次。第K個組成員的指數運算次數為6，發送消息數為5，接收消息數為5。表1中所給出的SG(L1)0和SG(Lm)j（m∈[2，…，h-1]）中的每個組成員的指數運算次數以及發送接收消息數，是在沒有考慮每個子組中的第一個組成員和第K個組成員的特殊情況下給出的值。下面針對第一個組成員和第K個組成員的特殊情況進行分析。在CKT－ECC協議中，每個子組的子組控制者由該子組的第二個組成員充當，所以第Lm層中SG(Lm)j子組的第一個組成員的指數運算次數不會累加在第Lm－1層中相對應的SG(Lm-1)[j/k]-1子組中的第一個組成員上。因此，子組SG(Lm)j(m∈[2，…，h-1])中僅存在一個子組成員其指數運算次數比表1中的3(h-m+1)有所增加，且其指數運算次數的增量僅為K-3。同理，SG(Lm)j中僅存在一個子組成員其接收消息數比表1中的B要多K-3次。而SG(Lm)j中每個子組成員其發送消息數則不會超過表1中給出的A次。子組SG(L1)0的分析同上。因此，在組規模n1很大的情況下，可以不必考慮這些微小的計算以及通信開銷增量。此外，在CKT－ECC協議中進行簇內密鑰協商時，計算和通信開銷最大的節點是由該簇中myScore值第二大的節點充當的，而在每個子組內進行子組密鑰協商時，組成員則由簇頭充當，有利于CKT－ECC協議的順利運行。

此外，CKT－ECC協議中的組密鑰協商算法是基于橢圓曲線密碼體制設計的。除超奇異橢圓曲線和異常曲線外，ECC的求解算法都是指數時間算法[12]。因此，在同樣安全強度下，與其他一些已知的加密算法如RSA相比，所需要的密鑰長度要少得多，計算開銷較小，密鑰帶寬也較小。安全強度越高，ECC的優越性越高。

以上分析得出，CKT－ECC協議與TGDH、GDH組密鑰協商協議相比，有效地降低了大規模移動Ad hoc網絡中節點在進行安全的組密鑰協商時所需要的資源開銷。

5結束語

隨著移動Ad hoc網絡的應用與發展，其密鑰管理問題日益成為研究熱點。本文提出的適用于大規模移動Ad hoc網絡的組密鑰協商協議，在分簇－K叉樹組模型結構上采用橢圓曲線密碼體制實施密鑰協商和分配，使得節點在密鑰協商過程中具有低計算開銷與低通信開銷的優勢，較好地解決了在大規模移動Ad hoc網絡中進行密鑰協商時所遇到的節點能量受限問題。本協議與TGDH、GDH組密鑰協商協議相比，有效地降低了節點在密鑰協商過程中的計算開銷和通信開銷，減少了大規模移動Ad hoc網絡中節點的資源消耗，適用于大規模的移動Ad hoc網絡。

參考文獻：

[1]STEINER M， TSUDIK G， WAIDNER M. Differ－Hellman key distribution extended to group communication[C] //Proc of Usenix Conference on Computer and Communications Security. New York:ACM Press， 1996:31－37.

[2]STEINER M， TSUDIK G， WAIDNER M. DLIQUES:a new approach to group key agreement[C] //Proc of the 18th International Confe－rence on Distributed Computing Systems.Washington DC: IEEE Computer Society， 1998:380－387.

[3]STEINER M， TSUDIK G， WAIDNER M. Key agreement in dynamic peer groups[J].IEEE Trans on Parallel and Distributed Systems， 2000， 11(8):769－780.

[4]KIM Y， PERRING A， TSUDIK G. Tree－based group key agreement[J]. ACM Trans on Information and System Security， 2004， 7(1):60－96.

[5]LI J H， LEVY R， YU M. A scalable key management and clustering scheme for Ad hoc networks[C] //Proc of INFOSCALE’06. New York:ACM Press， 2006:1－10.

[6]LI D， SAMPALLI S. An efficient group key establishment in location－aided mobile Ad hoc networks[C] //Proc of PE－WASUN’05. New York:ACM Press， 2005:57－64.

[7]CHEE J， TEO M， TAN C. Energy－efficient and scalable group key agreement for large Ad hoc networks[C] //Proc of PE－WASUN'05. New York:ACM Press， 2005:114－121.

[8]SMART N. The discrete logarithm problem on elliptic curves of traces one[J]. Journal of Cryptology， 1999， 12(3):193－196.

[9]MENEZES A， OKAMOTO T， VANSTONE S. Reducing elliptic curve logarithms to logarithms in a finite field[J].IEEE Trans on Information Theory， 1993， 39(5):1639－1646.

[10]OORSCHOT P， WIENER M. Parallel collision search with cryptanalytic applications[J]. Journal of Cryptology， 1999，12(1): 1－28.

[11]TRAPPE W， WANG Y， LIU K J.Resource－aware conference key establishment for heterogeneous networks[J]. IEEE/ACM Trans on Networking， 2005， 13(1):134－146.

[12]SUN M， SU C， HUANG C， et al. Design of a scalable RSA and ECC crypto－processor[C] //Proc of ASP－DAC. New York:ACM Press， 2003: 495－498.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文