基于ＤｉｆｆｉｅＨｅｌｌｍａｎ的移動Ａｄ ｈｏｃ網(wǎng)絡(luò)動態(tài)混合密鑰管理策略

（1.中國礦業(yè)大學(xué)， 北京 100083； 2.河南理工大學(xué)， 河南 焦作 454003; 3.空軍第一航空學(xué)院， 河南 信陽 464000）



摘 要：

密鑰管理是解決移動Ad hoc網(wǎng)絡(luò)中安全通信問題的重要環(huán)節(jié)。在分析網(wǎng)絡(luò)特點(diǎn)的基礎(chǔ)上，提出了一種基于DiffieHellman協(xié)議的動態(tài)混合密鑰管理策略(DHKM)。通過網(wǎng)絡(luò)分簇，將多個簇首節(jié)點(diǎn)一起作為權(quán)威機(jī)構(gòu)執(zhí)行管理功能，采用DiffieHellman交換，并利用成員過濾函數(shù)維護(hù)密鑰，適應(yīng)網(wǎng)絡(luò)拓?fù)涞膭討B(tài)變化。結(jié)果表明，DHKM保證了密鑰的完整性和機(jī)密性，并有效減少了密鑰更新對網(wǎng)絡(luò)性能的影響。

關(guān)鍵詞：移動自組化網(wǎng)絡(luò)； 密鑰管理； 動態(tài)混合； 成員過濾函數(shù)

中圖分類號：TP393 文獻(xiàn)標(biāo)志碼：A

文章編號：10013695(2008)12373203



Dynamic hybrid key management strategy for mobile Ad hoc networks based on DiffieHellmantheory



ZHANG Li1，2， YU Zhenwei1， ZHANG Yang3

( 1. China University of Mining Technology， Beijing 100083， China; 2.Henan Polytechnic University， Jiaozuo Henan 454003， China; 3. The First Aeronautic Engineering Institute of the Air Force， Xinyang Henan 464000， China)



Abstract:Secure communication is very important in Ad hoc networks and key management is one of most eminent things in security quality. This paper presented a clusterbased dynamic hybrid key management(DHKM) solution， based on the theory of DiffieHellman. After dynamicallyclustering the mobile nodes distributed randomly， these clusterheads jointly executed administrative functionsrelying on DiffieHellmanprotocol. Utilized member filter function to maintain key management， which accommodated to topological dynamic change.It concludes that DHKMmodel ensuresintegrity，confidentialityand adapts to the special requirements for frequent key refresh.

Key words：mobile Ad hoc networks; key management; dynamic hybrid; member filter function



移動Ad hoc網(wǎng)絡(luò)是由無線節(jié)點(diǎn)組成的多跳、自組織的，沒有任何固定基礎(chǔ)設(shè)施和集中管理機(jī)構(gòu)的網(wǎng)絡(luò)。相對于傳統(tǒng)網(wǎng)絡(luò)，Ad hoc網(wǎng)絡(luò)具有動態(tài)拓?fù)浣Y(jié)構(gòu)、分布式控制、有限帶寬、無線信道的不可靠性等特點(diǎn)。因此，移動Ad hoc網(wǎng)絡(luò)不僅存在傳統(tǒng)無線網(wǎng)絡(luò)具有的安全問題，由于其特殊性，涉及的安全問題更為復(fù)雜^[1~6]。目前，將簇與密鑰管理結(jié)合是Ad hoc網(wǎng)絡(luò)領(lǐng)域新的研究熱點(diǎn)^[7]。采用分簇的密鑰管理策略更符合Ad hoc網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)動態(tài)變化等特性，能有效地解決Ad hoc網(wǎng)絡(luò)面臨的安全性問題。目前提出的有影響的密鑰管理策略有文獻(xiàn)[8~10]等。概括起來其具有以下不足：密鑰刷新耗時(shí)較長；沒有充分考慮動態(tài)節(jié)點(diǎn)引起的密鑰更新；存在密鑰管理策略的可擴(kuò)展性問題等。

本文在分析所有節(jié)點(diǎn)均可移動的無線網(wǎng)絡(luò)通信安全需求的基礎(chǔ)上，提出了基于DiffieHellman的動態(tài)混合密鑰管理策略DHKM，利用節(jié)點(diǎn)分簇，采用混合分布式處理，充分利用鄰近節(jié)點(diǎn)的廣播能力，在兼顧安全性的同時(shí)簡化密鑰管理操作，有效控制了密鑰管理對節(jié)點(diǎn)性能的影響。

1 問題描述和相關(guān)定義

1. 1 分簇結(jié)構(gòu)

Ad hoc網(wǎng)絡(luò)由n個自由運(yùn)動節(jié)點(diǎn)組成。圖1所示的是采用分簇結(jié)構(gòu)的，由子網(wǎng)層和虛擬骨干網(wǎng)層（覆蓋層）組成的兩層網(wǎng)絡(luò)模型。虛擬骨干網(wǎng)由簇首組成。簇首和簇結(jié)構(gòu)通過分簇算法自動選舉產(chǎn)生^[11]，選出性能強(qiáng)、生存期長的節(jié)點(diǎn)作為簇首。簇內(nèi)所有節(jié)點(diǎn)均可與簇首直接通信。簇首作為簇的控制節(jié)點(diǎn)具有管理功能，包括加入節(jié)點(diǎn)的身份驗(yàn)證和強(qiáng)制注銷已有節(jié)點(diǎn)；負(fù)責(zé)簇內(nèi)密鑰的分發(fā)，并通過廣播成員過濾函數(shù)控制密鑰的更新。當(dāng)簇成員關(guān)系變化時(shí)，成員過濾函數(shù)也相應(yīng)變化。

1. 2 相關(guān)定義

N為簇首個數(shù)，nij 為第i簇ci內(nèi)第j個節(jié)點(diǎn)。其中：j∈[1，ni]， ni是ci的節(jié)點(diǎn)總數(shù)，ni1表示第i簇ci的簇首。K為各簇首共同生成的加密密鑰。cK為所有成員共享的密鑰。c(i)1-j為ci的節(jié)點(diǎn)nij與簇首共享的簇內(nèi)初始化密鑰，j∈[2，ni]。ni1維護(hù)的成員過濾函數(shù)fi(x)=∑nij=0a(i)jxni-j mod p。其中：p為大素?cái)?shù);a是秩為p的G的本原元；G是模p′即約剩余系Z*p′的真子群;大素?cái)?shù)p′=2p+1;p、a公開。設(shè)h為單向散列函數(shù)，簇首利用過濾參數(shù)集S(i)={S(i)0，S(i)1，…，S(i)m-1}和cK構(gòu)造fi(x)，有

fi(x)=∏ni-1j=0[x-h(S(i)j)]+cK mod p(1)

2 動態(tài)混合密鑰管理（DHKM）

DHKM采用DiffieHellman協(xié)議^[12]進(jìn)行簇內(nèi)的密鑰初始化和簇間K的共享。

2. 1 共享密鑰的初始化

假設(shè)密鑰協(xié)商前各簇首已完成身份認(rèn)證，順序關(guān)系為：n11為第1個簇首；ci簇的簇首ni1作為第i個簇首，并依此類推。初始化過程分為以下三個階段：

a)簇內(nèi)的初始化。首先進(jìn)行簇內(nèi)的DiffieHellman交換，簇首和簇成員節(jié)點(diǎn)共享簇內(nèi)初始化密鑰c(i)1-j。其中：i∈[1，N]；j∈[2，ni]。協(xié)議進(jìn)入b)。

b)簇間密鑰協(xié)商。采用DiffieHellman交換進(jìn)行簇首之間的密鑰協(xié)商。交換由第一個簇首發(fā)起，最后一個簇首生成簇密鑰cK并分發(fā)給其他簇首后結(jié)束。協(xié)商階段分為五步：

(a)n11隨機(jī)產(chǎn)生x1，計(jì)算αx1 mod p，將結(jié)果發(fā)送到n21。

(b)ni1隨機(jī)產(chǎn)生xi，并依次計(jì)算ax1x2…xi mod p，{ax1x2…xi/xk mod p|k∈[1，i]}，并把這些值送給下一個簇首nj1。其中：i∈[2，N-1]； j=i+1。

(c)若i≠N-1，j=i+1，轉(zhuǎn)到b)執(zhí)行；否則繼續(xù)。

(d)最后一個簇首nN1收到前一個簇首傳來的中間值后，利用自己產(chǎn)生的隨機(jī)數(shù)xN計(jì)算簇間共享密鑰K，另一半公鑰{ax1x2…xN/xi mod p|i∈[1，N-1]}。然后生成隨機(jī)的簇密鑰cK并向其他各簇首發(fā)送一條廣播消息{ax1x2…xN/ximod  p|i∈[1，N-1]}，K+cK mod p。其中:K=ax1x2…xN mod p。

(e)收到nN1的廣播消息后，簇首ni1利用自己的私鑰xi和收到的ax1x2…xN/xi mod p計(jì)算產(chǎn)生K，然后解密cK，i∈[2，N-1]。

c)密鑰分發(fā)。在簇首之間共享K和cK后，簇首分別在簇內(nèi)進(jìn)行密鑰分發(fā)。

(a)簇首ni1利用密鑰c(i)1-j構(gòu)建過濾參數(shù)集S(i)。參數(shù)集元素的選擇遵循條件是

S(i)0=ri，S(i)j=c(i)1-j′， j′=j+1， j∈[1，nj-1](2)

(b)簇首整理fi(x)=∑nij=0a(i)jxni-j mod p，然后在簇內(nèi)廣播fi(x)和h(cK)。

簇內(nèi)普通成員nij收到廣播后，使用共享密鑰c(i)1-j 計(jì)算xij=h(c(i)1-j)，將xij作為變量代入式(1)，得到簇密鑰：

cK=(xij-h(ri)）∏nij=2(xij-h(c(i)1-j))+cK mod p(3)

若某個成員沒有共享密鑰，即使收到廣播并計(jì)算，只能得到一個無效值，無法獲得密鑰。

(c)在所有簇ci，i∈[1，N]完成簇內(nèi)廣播后，網(wǎng)絡(luò)節(jié)點(diǎn)共享密鑰cK，任意兩個節(jié)點(diǎn)或多個節(jié)點(diǎn)之間可以使用密鑰對傳送的消息進(jìn)行加密保護(hù)。

2. 2 新節(jié)點(diǎn)加入

移動Ad hoc網(wǎng)絡(luò)的重要特點(diǎn)是節(jié)點(diǎn)是動態(tài)的，節(jié)點(diǎn)可以隨時(shí)加入和退出網(wǎng)絡(luò)。當(dāng)簇成員關(guān)系發(fā)生改變后需要更換密鑰，防止新加入的節(jié)點(diǎn)使用cK不受限制地訪問截獲加密的舊消息，破壞消息的機(jī)密性。

a)要加入ci的新節(jié)點(diǎn)，nix首先向簇首ni1提出加入申請，ni1對nix的身份進(jìn)行認(rèn)證，通過認(rèn)證后被獲準(zhǔn)加入。nix與ni1進(jìn)行一次DiffieHellman交換，建立雙方共享密鑰c(i)1-x。

b)ni1產(chǎn)生新密鑰c′K并在整個網(wǎng)絡(luò)內(nèi)分發(fā)。為保證網(wǎng)絡(luò)所有節(jié)點(diǎn)安全接收更新密鑰，采用廣播來提高分發(fā)效率。 

(a)ni1向其他簇首廣播K+cK+c′K mod p；收到廣播后，其他簇首先用自己保存的K解密，然后在簇內(nèi)廣播cK+c′K mod p; 擁有cK的任意節(jié)點(diǎn)可解密簇首的廣播消息來獲取新密鑰，從而實(shí)現(xiàn)密鑰的同步更新。

(b)ci的成員控制函數(shù)fi(x)也相應(yīng)地改變。ni1首先改變過濾參數(shù)集S′(i)={r′i，c(i)1-2，c(i)1-3，…，c(n)1-ni，c(i)1-x}；然后利用式(1)重新構(gòu)建f ′i(x)，并在簇內(nèi)廣播f ′i(x)和h(c′K)。

此時(shí)，簇內(nèi)所有成員可以從f ′i(x)推導(dǎo)出新密鑰c′K，新節(jié)點(diǎn)只能獲得c′K，無法得到cK。

2. 3 刪除節(jié)點(diǎn)

當(dāng)某個節(jié)點(diǎn)遭到惡意攻擊或者節(jié)點(diǎn)主動離開時(shí)，簇首需要刪除這個節(jié)點(diǎn)。此時(shí)，需要更新密鑰來保證密鑰的獨(dú)立性。為了阻止擁有舊密鑰的節(jié)點(diǎn)通過非法竊聽獲取新密鑰，假設(shè)nix被從ci中刪除，ni1首先產(chǎn)生新密鑰c′K并向全網(wǎng)分發(fā)，在簇內(nèi)分發(fā)之前，ni1重新生成r′i并將元素c(i)1-x從S′(i)中刪除；然后根據(jù)式(4)重新計(jì)算成員過濾函數(shù)f′i(x)。

f′i(x)=(x-h(r′i))(x-h(c(i)1-2))…

(x-h(c(i)1-(ni-1)))+c′K mod p（4）

最后ni1通過簇間廣播K+cK+c′K mod p向其他簇首分發(fā)新密鑰。其他簇首如nj1首先解密獲得c′K，然后生成新隨機(jī)數(shù)r′j，并根據(jù)式(5)計(jì)算成員過濾函數(shù)f ′j(x)和h(c′K)。

f ′j(x)=(fj(x)-cK)(x-h(r′j))/(x-h(rj))+c′K mod  p(5)

2. 4 簇首變更

若簇首ni1失控或離開，出于安全考慮需要隔離該簇首，并在該簇內(nèi)根據(jù)簇首選取算法選取新的簇首n′i1；然后重新運(yùn)行初始化協(xié)議實(shí)現(xiàn)密鑰更新。只有新簇首n′i1所在的ci運(yùn)行第一階段的初始化。第二階段初始化由第一個簇首發(fā)起，最后一個簇首生成c′K，向其他所有簇首廣播K′+c′K mod p，ni1被排除在外。第k組的簇首{nk1|k≠i}解密c′K后，根據(jù)式(5)重新生成f′i(x)，并在簇內(nèi)廣播f′i(x)和h(c′K)來分發(fā)新密鑰。新簇首n′i1運(yùn)行第三階段的初始化，利用與節(jié)點(diǎn){nij|1＜j≤ni-1}共享的簇初始化密鑰構(gòu)造新成員構(gòu)造函數(shù)f′i(x)；然后通過廣播f′i(x)和h(c′K)在本簇內(nèi)安全分發(fā)c′K。

2. 5 密鑰更新

當(dāng)預(yù)先設(shè)定的壽命過期后，密鑰必須立即更新。更新可以由任意簇首發(fā)起，同時(shí)負(fù)責(zé)生成新密鑰c′K，然后在簇內(nèi)和簇間廣播cK+c′K mod p。收到廣播消息后，各簇首除了解密獲取新密鑰外，還繼續(xù)在其控制域內(nèi)廣播該消息。

3 安全性證明

本方案的安全性依賴于DiffieHellman交換和成員過濾函數(shù)。DiffieHellman交換和成員過濾函數(shù)的安全性已經(jīng)得到證明^{[1，12]}，這也確保了本文密鑰管理策略的安全性。

DiffieHellman交換是有限域離散對數(shù)計(jì)算難題，并且給定ZP域內(nèi)三個隨機(jī)數(shù)a，b，c、〈aa，ab，ac〉和〈aa，ab，aab〉是多項(xiàng)式不可分離的。成員過濾函數(shù)屬于有限域模運(yùn)算問題，若非法節(jié)點(diǎn)接收到成員過濾函數(shù)，其標(biāo)準(zhǔn)形式為a0xm+a1xm-1+…+am-1x+am mod p。其中的常數(shù)項(xiàng)為h(ri)h(c(i)1-2)h(C(i)1-3)…h(huán)(c(i)1-ni)+cK mod p。因此，很難從常數(shù)項(xiàng)中分離出cK。即使非法用戶獲得某個過濾參數(shù)h(c(i)1-j)，也無法利用單向散列函數(shù)h反向推導(dǎo)出c(i)1-j，更無法進(jìn)一步從fi(x)中推導(dǎo)出cK。

4 結(jié)束語

基于Ad hoc網(wǎng)絡(luò)自組織、無中心、拓?fù)浣Y(jié)構(gòu)動態(tài)的特性，本文提出了基于DiffieHellman協(xié)議的動態(tài)混合密鑰管理策略。使用分簇結(jié)構(gòu)，虛擬骨干網(wǎng)上的簇首聯(lián)合起來作為權(quán)威機(jī)構(gòu)具有管理功能，適應(yīng)網(wǎng)絡(luò)拓?fù)涞膭討B(tài)變化，充分利用無線網(wǎng)絡(luò)的廣播特性，使用密鑰共享機(jī)制，確保了密鑰管理的認(rèn)證、完整和機(jī)密性。下一步工作的重點(diǎn)是進(jìn)一步把DHKM與Ad hoc路由協(xié)議相結(jié)合，并評價(jià)安全路由協(xié)議以及其性能。

參考文獻(xiàn)：

[1]MICHAE ST， CENE T， MZCHAEL W. DiffieHellman key distribution extended to group communication[C]//Proc of the 3rd ACM Conference on Computer and Communications Security. New York: ACM Press， 1996:3137.

[2]ZHOU Lidong， HAAS Z J. Securing Ad hoc networks[J]. IEEE Network，1999，13(6):2430. 

[3]OTHMAN J B， XUE Xiaoyan. Security equipment in Ad hoc networks[C]//Proc of the 55th Vehicular Technology Conference. 2002:18191823.

[4]BURMESTER M， DESMEDT Y. A secure and efficient conference key distribution system[C]//Proc of CryptologyEUROCRYPT’94. Berlin: SpringerVerlag， 1994:275286. 

[5]傅堅(jiān)，張翎.無線Ad hoc網(wǎng)動態(tài)密鑰管理問題的研究[J].電子與信息學(xué)報(bào)，2006，28(5):815819.

[6]李昕，劉建輝，成誠，等.基于PKI的P2P信任關(guān)系[J].遼寧工程技術(shù)大學(xué)學(xué)報(bào)，2007，26(3):412414.

[7]許力，錢曉聰.移動自組網(wǎng)環(huán)境下基于圖論的智能優(yōu)化分簇策略[C]//2005年中國計(jì)算機(jī)大會論文集.北京：清華大學(xué)出版社. 2005：1015.

[8]BECHLER M， HOF H J， KREFT D， et al. A clusterbased security architecture for Ad hoc networks[C]//Proc of IEEE INFOCOM’04. Washington DC: IEEE Computer Society， 2004:23932403.

[9]SEUNCHUN J，CHANIL P， DAESEON C， et al. Clusterbased trust evaluation scheme in Ad hoc network[J]. ETRL Journal，2005，27(4):465468.

[10]LI Xiangyang， WANG Yu，F(xiàn)RIEDER O. Efficient hybrid key agreement protocol for wireless Ad hoc networks[C]//Proc of the 11th International Conference on Conputer Cornmunications and Networks. 2002:404409.

[11]CHATTERJEE M， DAS S K， TURGUT D.WCA: a weighted clustering algorithm for mobile Ad hoc networks[J].Journal of Cluster Computing: Mobile Ad hoc Networking， 2002，5(7):193204.

[12]DIFFIE W， HELLMAN M. New directions in cryptography[J]. IEEE Trans on Information Theory，1976，22(6):644654.