一種基于ECC的Ad hoc 網(wǎng)組密鑰協(xié)商協(xié)議

向婉芹，陳乙源，李 燕

(重慶電力高等專科學(xué)校，重慶400050)

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

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

1 橢圓曲線密碼體制

1.1 橢圓曲線密碼體制

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

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

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

1.2 橢圓曲線密碼體制的安全強(qiáng)度

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

表1 同等安全強(qiáng)度下密鑰位長(zhǎng)度比較

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

2.1 密鑰樹(shù)編碼［5］

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

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

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

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

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

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

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

圖1 網(wǎng)路拓?fù)浣Y(jié)構(gòu)與密鑰樹(shù)

2.2 密鑰樹(shù)的建立

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

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

2.3 最左密鑰路徑

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

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

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

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

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

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

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

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

3.2 成員加入

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

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

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

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

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

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

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

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

Step7:Mi修改自己的密鑰樹(shù)信息。

Step8:Mi廣播密鑰樹(shù)的變化，Mi和Mj所在的密鑰樹(shù)路徑上的節(jié)點(diǎn)對(duì)密鑰進(jìn)行維護(hù)和更新。

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

3.3 成員退出

成員離開(kāi)過(guò)程圖3所示。

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

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

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

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

無(wú)論節(jié)點(diǎn)是主動(dòng)離開(kāi)還是被動(dòng)離開(kāi)，均可用相同的方式更新維護(hù)密鑰樹(shù)。

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

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

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

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

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

5 結(jié)語(yǔ)

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

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

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

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

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

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

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