大規模認知無線電網絡多方密鑰交換協議

摘 要:提出一種適合大規模認知無線電網絡的密鑰交換協議，首先利用拓撲位置將網絡分簇，簇內使用multi party Diffie-Hellman，簇間使用a conference key distribution，通過旅行商問題為密鑰交換協議提供最優路徑。該協議不僅防止被動攻擊，而且通過減少對廣播信道的依賴提高共享密鑰協商過程的效率和成功率，運行效率為O(2max(m))， max(m)為節點數最多的簇中節點數量。

關鍵詞:Ad hoc認知無線電; 多方密鑰交換; 信道切換; 大規模; 安全; 分簇; 旅行商問題

中圖分類號:TP393.04

文獻標志碼:A

文章編號:1001-3695(2010)02-0730-03

doi:10.3969/j.issn.1001-3695.2010.02.090

Multi party key-exchange protocols in large scale cognitive radio network

ZHOU Jian1，2， ZHOU Xian-wei1， SUN Li-yan2

(1. School of Information Engineering， University of Science Technology Beijing， Beijing 100081， China; 2. School of Information Engineering， Anhui University of Finance Economics， Bengbu Anhui 233041， China)

Abstract:This paper put forward a new method， firstly divided cognitive radio network into multiple clusters， secondly used multi party diffie-hellman in cluster and a conference key distribution among clusters， at last key-change protocols selected the optimal path with traveling salesman problem. This protocol not only prevents passive attack， but also improves the efficiency and success rate of sharing key by reducing the reliance on broadcast channels， the efficiency is O(2max(m))， max(m)is the number of nodes in cluster which have the largest number of nodes than other clusters.

Key words:Ad hoc cognitive radio; multi-party key-exchange; switching channel; large scale; security; clustering; traveling salesman problem

自1999年Joseph Mitola 博士首次在其博士論文中提出認知無線電[1]概念以來，該技術已經成為下一代網絡研究[2]的關鍵。網絡中用戶在不干擾注冊用戶(主用戶)[3]通信的前提下，自由使用非授權頻譜資源，通過可配置的認知引擎使網絡具有自組織、動態、分布式、智能等特點，提供了在不同設備、不同頻段、不同政策下、不同組網方式下的靈活通信，改善了頻譜資源短缺的問題。然而傳統無線協議無法滿足非固定頻譜策略[4~7]，因此重新設計認知無線電協議是十分必要的。設計安全、可靠的認知無線電協議是其能否大規模投入應用的關鍵。其中通過破壞信道傳輸，達到增加傳輸延遲，降低網絡性能的攻擊尤為突出，如密鑰耗損攻擊利用鏈路層的頻繁更換信道帶來的時延，攻擊傳輸層的會話密鑰[8，9]。加密技術作為無線網絡安全基礎，研究該種攻擊下的無線網絡密鑰管理，保證密鑰管理的安全、可靠具有重要的現實意義。密鑰交換協議是密鑰管理的重要組成部分。由于動態頻譜的特性使得認知無線電網絡和傳統的Ad hoc網絡在密鑰交換協議設計上具有很大的差別，這種差別不僅體現在網絡結構不同，前者體現在頻譜開放，后者強調了網絡拓撲結構，而且兩者具有不同的信道構成，前者具有多個信道，涉及信道選擇的效率問題，而后者具有統一的單個信道，不涉及信道選擇的效率問題。現有的文獻針對Ad hoc網絡的密鑰交換協議具有較多的研究[10～13]，而前者還沒有相關的文獻進行研究，如果單純地將Ad hoc網絡的密鑰交換協議引入認知無線電網絡而不考慮信道選擇的效率問題是不合適的，因此在考慮信道選擇效率的基礎上設計高效安全的密鑰交換協議，是認知無線電密鑰管理的一個亟待解決的問題。本文通過分析認知無線電信道選擇效率問題，在分簇基礎上結合兩種密鑰交換協議(multi party Diffie-Hellman和confe-rence key distribution system)，設計一種適合大規模認知無線電網絡的密鑰交換協議。

1 信道切換

開放頻譜策略使得認知用戶自由使用頻譜資源，導致通信雙方必須協商相同的信道，這一過程勢必帶來傳輸時延，它不僅影響鏈路層占用通信介質，而且也為路由選擇帶來更大的變化，不僅考慮節點跳數，而且要考慮所選路徑上信道切換次數。這也給需要廣播支持的協議帶來困難，需要網絡協商統一信道。如圖1所示，路徑No1→No6→No5長度短于No1→No2→No3→No4→No5，但是前者的切換次數大于后者，因此具體選路中需要綜合考慮。由于密鑰交換協議是建立在通信協議基礎之上，信道切換也給密鑰交換協議帶來新的問題，其可靠性、效率都需要進一步加以研究。

2 密鑰交換協議

有兩類主要密鑰交換協議，即多方Diffie-Hellman密鑰交換協議[12]和Burmester與 Desmedt在1994年設計了一個比多方Diffie-Hellman密鑰交換更為有效的多方密鑰協商方案(a conference key distribution system)[13]。兩種密鑰交換協議有各自的優缺點，前者不使用廣播，通過鄰居節點交換，不需要特定的網絡協議，因而算法設計簡單。然而由于需要多輪交換，協商共享密鑰需要較長時延，不適合節點規模較大的網絡，同時需要可信的第三方指定交互的順序。后者不需要可信第三方支持，因此適用于Ad hoc方式下的認知無線電網絡密鑰協商，然而直接將該協議應用于認知無線電網絡，只適合網絡規模較小、頻譜選擇范圍較窄的情況下，當網絡規模較大，可選頻譜范圍較寬時，該協議就面臨一些問題:a)密鑰交換協議需要廣播協議支持，因此需要協商的廣播信道;b)每個節點都需要廣播一次，如果使用輪詢的方式，網絡規模較大時，容易造成較長延遲，如果使用搶占的方式，容易造成廣播風暴，同時使得搶占物理傳輸介質沖突增加;c)每次廣播都能保證每個節點接收到，網絡規模較小時，容易實現，當網絡規模較大時，很難保證;d)當接收節點與發送節點間距離超過可達的傳送距離時，需要節點轉發，也就需要特定的路由協議支持，當網絡規模較大時，顯然大部分節點都會在可達傳送距離外，增加了網絡負載。因此單獨使用某個密鑰交換協議都不適合Ad hoc方式下的認知無線電網絡，而結合兩者的優點可重新設計一種適合Ad hoc認知無線電網絡的密鑰交換協議。

3 認知無線電多方密鑰交換協議

為了將多方密鑰交換協議靈活高效地應用于認知無線電網絡，根據認知無線電網絡的特性改進了多方密鑰交換協議，顯然在大規模認知無線電網絡中減小多方密鑰交換協議的傳播范圍，可以有效地降低協議的復雜度，提高多方安全協議在大規模認知無線電網絡中的運行效率，而降低網絡協議運行規模的有效方式是對網絡分簇。通過在簇間和簇內兩次執行密鑰交換協議，實現全網絡的共享密鑰。該協議包括三個部分，分別為網絡分簇、簇內密鑰交換、簇間密鑰交換。同時在協議設計中假設參與節點都是誠實可靠的，網絡在密鑰交換時間內是拓撲不變的。

3.1 網絡分簇

將網絡分成多個簇(圖2)，由傳播距離內的節點自組織選擇簇頭，選簇的規則依據拓撲位置信息。為了保證密鑰交換協議的健壯性，使用基于弱連接的分簇算法，并進行改進，維持簇的規模，使之適合密鑰交換協議。un_nodes={N1，N2，…，Nn}為未處理節點集合;select_nodes=為已處理節點集合;d(Ni)為節點度;Ci為簇頭;|{}|求集合內節點數量;neighbor_c(Ci)為簇Ci的鄰居簇;Cj=unit(Cj，Ci)為將Cj、Ci合并為一個簇，簇頭為Cj;threshold為允許簇存在的最少節點數閾值。

如圖2(b)所示，網絡依據節點度的大小選擇簇頭，簇頭選擇其鄰居作為簇成員，完成網絡分簇，如果某個簇的成員數量小于預定值，則將其并入節點數量較少的鄰居簇，如圖2(c)所示，簇C4和C5其成員只有兩個，小于預定值，則將簇C4和C5并入簇C3，如圖2(d)所示。維持簇規模和減少簇的數量有利于密鑰交換協議的效率。

while(un_nodesk≠){

for(i=1;i

{Cj}=neighbor_C(Ci);select_nodes+=Ci+{Nj};

Cs=min(neighbor({Cj}));un_nodes-=Ci+{Nj};}

Cs=unit(Cs，Ci);}}

3.2 簇內密鑰交換

簇內成員較少，并且簇頭可以作為可信第三方節點，因此適合使用Diffie-Hellman密鑰交換協議，由簇頭指定交換順序，簇成員提供共享密鑰成分。然而由于節點間并不是一定直接可達的，由簇頭指定不同的連接次序，具有不同的交換效率。該問題可以歸結為一個哈密頓圈問題，如圖2(d)中的三個簇，上方兩個簇具有哈密頓圈，通過簇頭選擇其中一個哈密頓圈即可，而下方的簇中顯然沒有哈密頓圈，可以使用旅行商問題(TSP)解決該問題。每條邊上權重W=λ|fnodei-fnodej|代表信道切換次數，顯然切換的次數越少越好。

min∑ni=1∑nj=1cijxij，xij=1 收貨商訪問城市i后緊接訪問j0 否則

雖然旅行商問題是一個NP問題，然而簇內節點較少，因此簇頭可以短時間內得到旅行商問題的最優解，以簇i為例，通過簇頭Ci計算得到以簇頭為開始節點和尾節點，通過網絡所有節點最少一次，且其邊權重和為最小的路徑pathi。由每個參與方各選擇一個秘密指數xij，最后構造一個秘密值gxi1xi2…xim。其中:m為簇內成員數量，令G是一個階數為素數q的乘法循環群，g為其任一生成元，則群成員Ni1，Ni2，…，Nim的共享密鑰協商過程如下:

a)簇頭計算得到簇內最小路徑pathi，發送給每個簇內成員，簇頭作為開始節點和結束節點。

b)簇成員接收pathi，根據路徑得到自己的上一跳節點和下一跳節點。

c)1≤j≤m ，Nij選擇xij∈RZq，計算gxij，將gxij發送給Nt((j+1)mod m)。

d)第k∈(1，m-1]輪，計算g{xig|g∈[(j-k)mod m，j]}，將結果發送給Ni((j+1)mod m)。

e)在m-1輪之后，所有參與者可以計算出一個共同的密鑰gxi1xi2…xim。

f)簇頭節點也得到共同的密鑰gxi1，xi2，…，xim，執行簇間密鑰交換協議。

g)簇成員等待簇頭進行簇間密鑰交換協議。

3.3 簇間密鑰交換

簇頭通過路由協議執行簇間密鑰交換協議，協議設計如下，協議的參與者為簇頭C1，C2，C3，…，Cn，此外，令C0=Cn，C1=Cn+1即Ci=Ci mod n。

a)簇頭節點Ci將Zi=gxi1xi2…xim組播給其他參與者簇頭節點C-i。

b)Ci計算Xi=(Zi+1Zi-1)xi，將Xi組播給其他參與者C-i。

c)Ki為簇間密鑰，即網絡共享密鑰，Ci計算Ki=Znxii-1Xn-1iXn-2i+1…Xi+n-2=g∑ki=1(∏mj=1xij∏mh=1xi+1h)。

d)由簇頭向簇內節點廣播共享密鑰，全網絡共享密鑰g∑ki=1(∏mj=1xij∏m'h=1xi+1h)。

e)結束。

根據下式容易檢查，如果上述所有的參與者均按照上述步驟操作，他們將共享同一密鑰。

Ai-1=Zxii-1=gxi-1xiAi=ZxiiXi=gxixi+1Ai=ZxiiXiXi+1=gxi+1xi+2An=ZxiiXiXi+1…Xi+n=gxn+1xn+2ki=Ai-1AiAi+1…Ai+n-2=gx1x2+x2x3+…xn-1xn

為了獲取共享密鑰，每個參與方簇頭Ci都付出自己的貢獻gxi1xi2…xim，不同的參與者構成的群體最終協商出的密鑰也是不同的，每個參與者需要經歷兩輪交互，發送兩個消息，最多執行四個模指數運算和n2/2+3n/2-3個乘法運算，該協議能夠保證被動攻擊下的安全。

4 協議分析

1)安全性 該協議建立在離散對數難解問題基礎上，能夠有效抵御被動攻擊。從簇內密鑰的安全性看，被動攻擊者在獲取p，g，gxij，要想獲得簇內共享密鑰gxi1xi2…xim，就需要得到xi1，xi2，…，xij-1，xij+1，…，xim。由于這些指數是保密的，對任意指數的求解，都意味著求解離散對數問題;從簇間密鑰的安全性看，被動攻擊者在獲取p，g，gxi1xi2…xim，要想獲取簇間共享密鑰g∑ki=1(∏mj=1xij∏m'h=1xi+1h)，就需要得到指數x11x12…x1j…x1n，x21x22…x2j…x2n，…，xi1xi2…xij…xin，xn1xn2…xnj…xnn，由于這些指數是保密的，對任意指數的求解，也意味著求解離散對數問題。因此可以說，該協議的簇間密鑰和簇內密鑰的安全性都是依賴于離散對數問題的困難性。密鑰交換分為兩個階段，分別運行在不同規模的網絡中，首先在局部的簇內，然后在簇頭間，減少了被干擾的機會。當簇內部分節點受到攻擊，簇頭阻斷被攻擊節點使其不影響整體網絡的密鑰管理。

2)復雜性 密鑰交換的第一階段只在簇內進行，具有局部性，通過簇頭可以有效地實現Diffie-Hellman密鑰交換，根據鏈路的頻譜切換次數計算權重，利用旅行商模型提高密鑰交換效率;密鑰交換的第二階段在簇間進行，只有簇頭節點參與，減少了密鑰交換的運行規模，總的運行效率為O(2max(m))。max(m)為節點數最多的簇的節點數量，比單純運行Diffie-Hellman的效率(O(n)，n為網絡節點數)有較大提高(n>>m)。同時共享密鑰的建立無須廣播，不會產生廣播風暴。密鑰交換的成功率高，相對于使用單一的密鑰交換協議，有效地縮短了時延，減少沖突。

3)可行性 該密鑰交換協議的第一階段，簇形成可以利用基于弱鏈接的協議基礎上進行簡單修改，即增加第四步即可;第二階段，通過簇節點獲取簇內的局部拓撲圖，指定交換次序;第三階段，簇間的密鑰交換可以運行于現有Ad hoc路由協議之上，不需要重新設計新的協議。

5 結束語

本文分析了Ad hoc認知無線電網絡中密鑰交換出現的問題，當網絡規模較大，由于信道切換延遲和動態頻譜選擇，使得單一的密鑰交換協議都不能保障Ad hoc認知無線電網絡快速協商共享密鑰。在分簇的基礎上，結合兩類密鑰交換協議的優點，設計適合大規模認知無線電網絡的密鑰交換協議，通過旅行商問題解決信道切換延遲的最優路徑選擇問題，提高了密鑰交換的效率，避免了密鑰交換協議運行所帶來的廣播風暴，減小了網絡的負載。從安全性、效率、可行性三個方面分析該協議的性能，證明該協議適合Ad hoc認知無線電網絡。在下一步的工作中，通過仿真模擬實驗進一步驗證其可靠性和可行性，并在此協議的基礎上設計防止主動攻擊的機制。

參考文獻:

[1]POWELL C. ET docket no 03-222 notice of proposed rule making and order[S]. Washington:Federal Communications Commission， 2003.

[2]MITOLA J， MAGUIRE G. Cognitive radio: making software radios more personal[J].IEEE Personal Communications.1999，6(4):13-18.

[3]AKYILDIZ I F， LEE W， VURAN M C，et al.Next generation /dynamic spectrum access/cognitive radio wireless networks: a survey[J]. Computer Networks. 2006， 50(13):2127-2159.

[4]CORMIOB C，CHOWDHURYA K R.A survey on MAC protocols for cognitive radio network[J].Ad hoc Networks.2009，7(7): 1315-1329.

[5]ZHAO Qing，TONG Lang，SWAMI A，et al.Decentralized cognitive MAC for opportunistic spectrum access in Ad hoc networks:a POMPD framework[J]. IEEE Journal on Selected Areas in Communications. 2007，25(13): 589-600.

[6]SU Hang，ZHANG Xi.Opportunistic MAC protocols for cognitive radio based wireless networks[C]//Proc of the 41st IEEE CISS Conference.Baltimore， MD:IEEE Information Sciences and Systems.2007:363-368.

[7]BRODERSEN R W，WOLISZ A，CABRIC D，et al.Corvus: a cognitive radio approach for usage of virtual unlicensed spectrum[R].Berkeley:Wireless Research Center (BWRC)，2004.

[8]AAD I，HUBAUX J P，KNIGHTLY E W.Denial of service resilience in Ad hoc networks[C]//Proc of the 10th Annual International Conference on Mobile Computing and Networking.2004:202-215.

[9]MATHUR C N，SUBBALAKSHMI K P. Security issues in cognitive radio networks[M]// CHEN K C， PRASAD R. Cognitive networks. Oxford:Wiley，2007: 272-290.

[10]JOUX A.An one round protocol for tripartite Diffie-Hellman[C]//Proc of Algorithmic Number Theory.Heidelberg: Springer-Verlag.2000: 385-394.

[11]MENZES A，QU M，VANSTONE S. Some new key agreement protocols providing mutual implicit authentication[C]//Proc of Selected Area in Cryptography.Nashville， TN:[s.n.]， 1995:22-32.

[12]BRESSON E，CHEVASSUT O，POINTCHEVAL D. Provably authenticated group Diffie-Hellman key exchange:the dynamic case[C]//Proc of Advances in Crytology-Proceedings of AsiaCrypt.Heidelberg: Springer-Verlag，2001:290-309.

[13]BURMESTER M， DESMEDT Y. A secure and efficient conference key distribution system[C]//Proc ofAdvances in Cryptology-EUROCRYPT’94.Heidelberg: Springer-Verlag，1995:275-286.