向婉芹，陳乙源，李 燕

(重慶電力高等?？茖W(xué)校，重慶400050)

Ad hoc網(wǎng)絡(luò)是一種特殊的無線移動網(wǎng)絡(luò)［1］。該網(wǎng)絡(luò)中所有節(jié)點地位平等，無需設(shè)置任何中心控制節(jié)點，是一種動態(tài)對等網(wǎng)絡(luò)(Dynamic Peer Group，DPG)，其研究方法和實施方案都與傳統(tǒng)網(wǎng)絡(luò)有巨大的差別。Ad hoc網(wǎng)絡(luò)中，每個節(jié)點同時擔(dān)當(dāng)終端和路由器的角色，當(dāng)兩個通信節(jié)點在一跳(hop)范圍內(nèi)，可以直接通信;否則，由其他節(jié)點作為路由器中繼轉(zhuǎn)發(fā)它們的通信。節(jié)點可以隨時加入或離開網(wǎng)絡(luò)，任何節(jié)點的故障不會影響整個網(wǎng)絡(luò)的運行。Ad hoc網(wǎng)絡(luò)具有很強的抗毀性，并且可以快速自動組網(wǎng)，在搶險救災(zāi)中具有極大的價值。目前對Ad hoc網(wǎng)絡(luò)研究的一個熱點問題就是如何制定安全高效的組密鑰協(xié)商協(xié)議［2］。

本文利用橢圓曲線密碼體制，結(jié)合密鑰生成樹的思想，提出了一個基于ECC的Ad hoc網(wǎng)組密鑰協(xié)商協(xié)議。該協(xié)議結(jié)合Ad hoc網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，通過密鑰協(xié)商建立并維護虛擬密鑰樹，為動態(tài)變化的Ad hoc網(wǎng)絡(luò)組成員之間的保密通信提供了一種有效的密鑰協(xié)商機制。

1 橢圓曲線密碼體制

1.1 橢圓曲線密碼體制

橢圓曲線密碼體制(Elliptic Curve Cryptography)［3］是近些年發(fā)展起來的一套新的密碼機制，可以描述如下:

定義E(a，b):y2=x3+ax+b為一橢圓曲線，考慮等式K=kG。式中，K，G為E(a，b)上的點，k(k＜n，n為點G的階)的整數(shù)。

根據(jù)密碼學(xué)理論，給定k和G，利用橢圓曲線的加密法則，計算K很容易;但給定K和G，求k就相對困難了，這就是橢圓曲線加密算法采用的難題。其中，G點稱為基點(base point);k(k＜n)稱為私有密碼(private key);K稱為公開密鑰(public key)。

1.2 橢圓曲線密碼體制的安全強度

公鑰密碼的安全性建立在數(shù)學(xué)難題的難解性上［4］。一類是一般群上的離散對數(shù)問題(DLP);另一類是橢圓曲線上的離散對數(shù)問題(ECDLP)。ECDLP是在已知橢圓曲線離散群中一點P和nP后，攻擊者無法獲得n。在同等安全強度要求下，ECDLP所需要的密鑰長度要低得多(見表1)。從表1可看出，采用橢圓曲線密碼的密碼體制具有較高的實現(xiàn)效率。

表1 同等安全強度下密鑰位長度比較

2 密鑰協(xié)商描述符號

2.1 密鑰樹編碼［5］

本文使用的密鑰樹為二叉樹［6］，密鑰樹中第l層第m個節(jié)點 V記為 ＜l，m ＞;根節(jié)點 R記為＜0，0＞。如果V是非葉子節(jié)點，則它有且只有一個左子節(jié)點 ＜l+1，2m＞和一個右子節(jié)點 ＜l+1，2m+1 ＞ 。每個節(jié)點 ＜l，m ＞ 有一個密鑰K＜l，m＞和一個私鑰 BK＜l，m＞。

式中，f(k)=αkmodp;α為設(shè)備固化值。

密鑰樹中每個葉子節(jié)點V:＜l，m ＞對應(yīng)一個Ad hoc 網(wǎng)絡(luò)成員 Mi，并且 K＜l，m＞即為 Mi的會話密鑰。從節(jié)點V到根節(jié)點R的路徑上的所有節(jié)點(包括R)形成Mi的密鑰路徑PKi。PKi中所有節(jié)點的密鑰和私鑰分別為K*i和。K*i中每個節(jié)點(不含R)的兄弟節(jié)點的隱蔽密鑰形成Mi的協(xié)同隱蔽密鑰。

非葉子節(jié)點 ＜l，m ＞的密鑰可以由其子節(jié)點的密鑰和私鑰協(xié)商生成，計算公式為

由于所有成員的密鑰路徑中都有 K＜0，0＞，因此，組通信密鑰KG為

式中，h(x)為強哈希函數(shù)。

綜上，Mi通過存儲并維護 PKi、K*i、BK*i和CK*i，即可得到組通信密鑰KG;每個成員最多保存并維護密鑰樹的h個節(jié)點(密鑰樹高h)，成員記錄的信息綜合即構(gòu)成一虛擬密鑰樹，如圖1(a)所示。

圖1 網(wǎng)路拓撲結(jié)構(gòu)與密鑰樹

2.2 密鑰樹的建立

假設(shè)網(wǎng)絡(luò)拓撲如圖1(a)所示，所有成員節(jié)點可以知道它們的一跳鄰居節(jié)點。本協(xié)議中，任意節(jié)點均可以發(fā)起密鑰協(xié)商操作，發(fā)起節(jié)點記為S。S向所有鄰居節(jié)點發(fā)出協(xié)議發(fā)起信息，節(jié)點在收到信息后，給出回應(yīng)，S挑選最早回應(yīng)的節(jié)點P組加入密鑰樹，并向P發(fā)出回應(yīng)信息。S響應(yīng)其他回應(yīng)的鄰居節(jié)點。P向其鄰居發(fā)出密鑰樹建立信息，并將回應(yīng)的鄰居節(jié)點加入密鑰樹。直到所有成員都加入密鑰樹，結(jié)果如圖1(b)所示。

如果一個節(jié)點收到多余一條協(xié)議發(fā)起信息，則選擇第一個作為回應(yīng)，其余不予響應(yīng)。如果節(jié)點發(fā)出信息后，沒有鄰居節(jié)點回應(yīng)，則稱其為密鑰樹的葉節(jié)點。

2.3 最左密鑰路徑

設(shè) ＜l，m ＞∈PKi，且 ＜l，m ＞ 為非葉子節(jié)點，若令，且l' ＞ l、m'為偶數(shù)，則L＜l，m＞為相對于 ＜l，m'＞ 的最左密鑰路徑。

利用滿二叉樹的相關(guān)理論，不難證明，每個非葉子節(jié)點的最左密鑰路徑有且只有一條［5］。

3 密鑰協(xié)商協(xié)議

3.1 密鑰協(xié)商初始化

Step1:設(shè)置系統(tǒng)參數(shù) (E(a，b)，α，p)，并依照網(wǎng)絡(luò)拓撲結(jié)構(gòu)，建立密鑰樹。

Step2:密鑰樹中每個葉子節(jié)點 Mi隨機產(chǎn)生xi∈Zp作為密鑰Ki，并計算其私鑰，記為BKi。

Step3:葉子節(jié)點Mi將Ki、BKi發(fā)送給自己的兄弟節(jié)點Mr，并計算共同父節(jié)點Mv的密鑰。并將協(xié)商的結(jié)果進行廣播。

Step4:葉子節(jié)點Mi根據(jù)其他葉子的協(xié)商結(jié)果，對密鑰路徑PKi上的所有非葉子節(jié)點的密鑰進行計算和維護。

3.2 成員加入

如果Mj欲加入網(wǎng)絡(luò)，首先向自己屬于該網(wǎng)絡(luò)的鄰居節(jié)點Mi發(fā)送加入請求，Mi收到請求后對此作出反應(yīng)。為了確保網(wǎng)絡(luò)的安全性，Mj與Mi應(yīng)進行相互認證，待認證通過后，Mi“推薦”Mj加入網(wǎng)絡(luò)，并同時廣播密鑰樹更新信息。成員加入的過程如圖2所示。

圖2 網(wǎng)絡(luò)成員加入過程

Step1:Mj隨機生成Kj和BKj，向Mi發(fā)出加入申請，雙方交換公鑰。

Step2:Mi將自己的密鑰加密發(fā)送給Mj，Mi→

Step3:Mj接到Mi的消息后，解碼得到BKi。利用Kj和BKi計算出二者協(xié)商密碼Kji，并Mj→Mi:

Step4:Mi接受到Mj消息后，通過解碼的到BKj和EKji(BKi)。利用Ki和BKj計算出二者協(xié)商密碼K'ji，進而得 BK'j=DK'ji(EKji(BKj))，如果 BKj=BK'j，則認證成功，否則失敗。認證成功時，如果Mi無兄弟節(jié)點，則Mj成為Mi的兄弟節(jié)點;否則，密鑰樹中生成一新節(jié)點取代Mi的位置，而Mj和Mi都成為該新增節(jié)點的子節(jié)點，并將Mi和Mj協(xié)商的密鑰作為該節(jié)點的密鑰。

Step5:Mi修改K*i中的 K＜l，m＞=Kji，且 Mi→

Step6:Mj收到Mi的消息后，生成自己的密鑰樹信息。

Step7:Mi修改自己的密鑰樹信息。

Step8:Mi廣播密鑰樹的變化，Mi和Mj所在的密鑰樹路徑上的節(jié)點對密鑰進行維護和更新。

設(shè)定網(wǎng)絡(luò)中每個組成員(包括已加入和未加入的)彼此知道對方的公鑰Ki，pub，而其私鑰Ki，pri則完全保密。

3.3 成員退出

成員離開過程圖3所示。

圖3 網(wǎng)絡(luò)成員退出過程

任一葉子節(jié)點 ＜l，m ＞上成員Mi離開，有兩種情況:

1)葉子節(jié)點離開后，其父節(jié)點還有其他的葉子節(jié)點，如圖3a中節(jié)點1的退出。此時，其父節(jié)點的子節(jié)點為非滿，故刪除其父節(jié)點，其兄弟節(jié)點替代其父節(jié)點的位置，并更新密鑰樹。

2)葉子節(jié)點離開后，其父節(jié)點沒有其它的葉子節(jié)點，如圖3a中節(jié)點2的退出。此時，其父節(jié)點的子節(jié)點為非滿，故刪除其父節(jié)點，其兄弟節(jié)點替代其父節(jié)點的位置，并更新密鑰樹。

無論節(jié)點是主動離開還是被動離開，均可用相同的方式更新維護密鑰樹。

4 協(xié)議安全性分析

(1)安全保密性。本協(xié)議的安全性是建立在橢圓曲線密碼體制之上的，對于被動對手而言，要攻破密碼必須破解橢圓曲線上的離散對數(shù)難解問題，因此協(xié)議實現(xiàn)了密鑰的安全保密性。

(2)前向安全性。當(dāng)有新的成員加入時，其所在的密鑰路徑上的所有節(jié)點的密鑰均重新協(xié)商，故無法獲得舊的組密鑰，因而協(xié)議實現(xiàn)了前向安全性。

(3)后向安全性。當(dāng)舊成員離開后，其所在的密鑰路徑上的所有節(jié)點也發(fā)生了密鑰協(xié)商，故無法獲得新的組密鑰，因而協(xié)議實現(xiàn)了后向安全性。

(4)密鑰獨立性。當(dāng)有成員變化時，組通信密鑰KG均會重新計算，且與舊值無關(guān)，因此實現(xiàn)了密鑰的獨立性。

5 結(jié)語

本文主要研究了在Ad hoc網(wǎng)絡(luò)中的行密鑰協(xié)商協(xié)議，結(jié)合橢圓密碼體制和密鑰樹的思想，提出一個密鑰協(xié)商協(xié)議，為動態(tài)變化的Ad hoc網(wǎng)絡(luò)組成員之間的保密通信建立了一種有效的密鑰協(xié)商機制。該協(xié)議具有節(jié)點加入認證功能，并對節(jié)點的動態(tài)退出提供了良好的支持。

［1］ 鄭少仁，王海濤，趙志峰，等.Ad hoc網(wǎng)絡(luò)技術(shù)［M］.北京:人民郵電出版社，2005.

［2］ 王昌達，鞠時光.無線自組網(wǎng)技術(shù)中的安全問題［J］.計算機科學(xué)，2006，(7):121-124.

［3］ 徐永道，高振明，王美琴，等.移動Ad hoc網(wǎng)絡(luò)基于橢圓曲線密碼體制的安全性研究［J］.山東大學(xué)學(xué)報(理學(xué)版)，2004，(4):71-76。

［4］ Stinson D R.密碼學(xué)原理與實踐［M］.北京:電子工業(yè)出版社，2009.

［5］ 何聚厚，李偉華.對等組內(nèi)安全通信密鑰協(xié)商協(xié)議［J］.西北工業(yè)大學(xué)學(xué)報，2003，(4):406-409.

［6］ 霍羅威茨.數(shù)據(jù)結(jié)構(gòu)(C語言版)［M］.北京:機械工業(yè)出版社，2006.