基于橢圓曲線完全自組織Ad hoc網(wǎng)絡(luò)密鑰管理方案

摘要:該文針對目前Ad hoc網(wǎng)絡(luò)密鑰管理方案存在計算量大，可信中心難以確定以及密鑰更新周期大小難以確定的問題，提出一種基于ECC完全自組織Ad hoc密鑰管理方案。該方案為解決計算量大而采用EEC代替RSA， 以完全自組織方式解決可信中心的瓶頸，通過使用雙重密鑰更新機制克服定期更新大小難以確定等問題。本方案具有計算代價小，安全可靠，擴展性好等優(yōu)點，適合大規(guī)模Ad hoc網(wǎng)絡(luò)。

關(guān)鍵詞:Ad hoc網(wǎng)絡(luò);橢圓曲線;密鑰管理;自組織;密鑰更新

中圖分類號:TP309文獻標識碼:A文章編號:1009-3044(2010)11-2598-03

Ad hoc Networks Key Management Scheme Based on Elliptic Curve Completely Self-Organization

SHEN Wu，WANG Tian-qin

(College of Computer and Information Engineering， Henan University， Kaifeng 475004， China)

Abstract: According to the current key management scheme exist large computation，trusted centre and key update cycle size is difficult to determine problems，we proposed a scheme that based on ECC fully self-organization Ad hoc key management in this paper.The sckeme use ECC instead of RSA for large computation;in order to solve trusted centre，we use fully self-organization ; By using a double key update to overcome the regular updating cycle size problem. Computational cost of this program has a small compuation safe ，reliabilityand good scalability for large-scale Ad hoc network.

Key words: Ad hoc network; elliptic curve; key management; Self-organization; key renewing

根據(jù)文獻[1]的定義，無線Ad hoc網(wǎng)絡(luò)是由一組自主無線節(jié)點或終端相互合作而形成 ，獨立于固定基礎(chǔ)設(shè)施的自創(chuàng)造、自組織和自管理網(wǎng)絡(luò)。傳統(tǒng)網(wǎng)絡(luò)的密鑰管理方案一般都采用RSA公鑰算法門限方案[2-3]，基于可信中心的方案[4]，而這些方案不能簡單的移植到移動Ad hoc網(wǎng)絡(luò)中來，因移動Ad hoc網(wǎng)絡(luò)固有的特性，如計算能力小，拓撲動態(tài)變化，所以在這樣的環(huán)境中找到可信的CA是較困難的，再者如果能找到，CA將成為整過系統(tǒng)的瓶頸，如果CA的私鑰被攻破，那么整過網(wǎng)絡(luò)將癱瘓。另外，目前提出的Ad hoc密鑰更新方案多數(shù)是基于RSA的定期更新方案[5]，在這樣的方案中更新周期很難確定，周期過大，系統(tǒng)的安全容易遭到攻擊，周期太小，因頻繁的更新密鑰，系統(tǒng)的效率將大大降低。

本文針對上面的問題提出一種高效的基于ECC的自組織的密鑰管理方案。本方案在與RSA同等安全條件下，具有密鑰長度短，計算代價小等特點;網(wǎng)絡(luò)中的系統(tǒng)密鑰有各個結(jié)點協(xié)同完成，通過門限機制組合成系統(tǒng)密鑰;同時在定期更新的基礎(chǔ)上引入密鑰及時更新機制，從而很好實現(xiàn)了更細周期難以確定的問題。

1 有限域上橢圓曲線密碼體制

要建立基于橢圓曲線的密碼體制，需要類似與因子分解兩個素數(shù)之積和求離散對數(shù)的難題。考慮方程Q=kP，其中Q，P∈EP (a，b)且k

對于ZP上的素曲線，我們使用三次方程，其中變量和系數(shù)在集合﹛0，1，…，p-1﹜中取值，運算為模p運算。

y2mod p=(x2+ax+b)mod p

可以證明，若(x3+ax+b)mod p無重復(fù)因子，則基于集合EP(a，b)可以定義一個有限Abel群。這等價于下列條件:

(4a3+27b2)mod p≠0 mod p

為了確保各種橢圓曲線密碼的安全性，需要知道定義在橢圓曲線上的有限abel群中點個數(shù)。在有限群EP( ，b)中，點的個數(shù)N范圍為:

因而，EP( ，b)上點的個數(shù)約等于ZP中元素的個數(shù)，即p個元素。

2 方案的實現(xiàn)

2.1 系統(tǒng)參數(shù)的安全選取

假定V是由n個節(jié)點成員組成的集合:記為V={V1， V2，…， Vn}，系統(tǒng)的公共參數(shù)由每個成員共同協(xié)商確定，記為:(p，q，t，E，A，B， H，{ID1，ID2，…，IDn})，其中:p，q為大素數(shù);t為系統(tǒng)的門限值;E為ZP上的橢圓曲線;A，B為E上階均為q兩個基點;H是公開的單向Hash函數(shù)，IDi為Vi的身份標識，其中i∈(1，2，…，n)。

2.2 系統(tǒng)初始化

第一步:

為了網(wǎng)絡(luò)中節(jié)點在后續(xù)階段能進行有效通信協(xié)商組密鑰，網(wǎng)絡(luò)中每個節(jié)點需在t0產(chǎn)生自己的公私鑰對，節(jié)點Vi∈V，隨機選擇初始私鑰xi0∈Zq，利用橢圓曲線計算Vi公鑰yi0= xi0·B mod p，其中(xi0，yi0)是以上定義的橢圓曲線上的點，并廣播yi0;

當(dāng)每個節(jié)點收到其它節(jié)點廣播的公鑰時，在確保不同的節(jié)點產(chǎn)生不同的公鑰，否則其中一個節(jié)點重新選擇自己的私鑰，并計算yj0，i0=xi0·yi0=xi0·xj0·B mod p，并廣播yj0，i0。

第二步:每個節(jié)點Vi∈V隨機選擇子密鑰份額ai0∈Zq，定義組私鑰為:，組公鑰為:Y=X·B mod p。

第三步:每個節(jié)點Vi∈V隨機選擇系數(shù)ai0，r∈Zq，其中r∈(1，2，…，k-1)構(gòu)造k-1次多項式:

初始驗證參數(shù)的計算:

初始秘密份額的的計算:

pi0，j=fi0(IDj) mod q，其中j∈(1，2，…，n)，

用Vj在t=0時刻的公鑰加密密鑰份額pi0，j，即:秘密份額加密li0，j=ENCj0(Pi0，j)

用節(jié)點Vi在t=0時的私鑰xi0對信息的簽名:

(1)

廣播式(1)和，保密信息Pi0，j

第四步:每個節(jié)點在接收到n-1個加密信息(li0，j=ENCj0(Pi0，j))后

用xi0解密信息得到li0，j=ENCj0(Pi0，j)。為了驗證Vj給Vi的秘密份額的正確性，可以通過下式驗證:

(2)

(如果通過，證明是正確的，否則Vj欺騙Vi并廣播pi0，j失敗)，計算，子組公鑰為:Yi0=pi0·B mod p并廣播子組公鑰Yi0，保存ui0。

通過以上四步就完成了系統(tǒng)中每個節(jié)點的初始化工作，以便在后續(xù)進行子密鑰的更新和組密鑰的生成工作。

3 子密鑰份額的雙重更新

子密鑰份額的雙重更新機制是為了防止一些攻擊者在定期子密鑰份額更新周期內(nèi)攻破系統(tǒng)的組密鑰或有泄露子密鑰份額而設(shè)置的。其中對定期更新或及時新在確保組密鑰不變的前提下對節(jié)點成員密鑰份額進行更新。對于及時跟新，假定系統(tǒng)中每個節(jié)點成員都采用了一些機制來監(jiān)控子密鑰份額是否有泄露。

3.1 子密鑰份額定期更新

第一步:定期更新初始化

網(wǎng)絡(luò)中每個節(jié)點成員Vi∈V隨機選擇多項式系數(shù)ait，r∈Zq，其中r∈(1，2，…，k-1)，構(gòu)造k-1次多項式:

并計算更新驗證參數(shù):

δit，r=αit，r·B mod p

同時計算更新子密鑰份額:

ψit，r=Hit(IDj) mod p，其中j∈(1，2…，n) (3)

然后用成員節(jié)點Vj∈V的上一個周期的公鑰yjt-1加密信息得:ζit，j=ENCjt-1(ψit，j)。

用節(jié)點成員Vi的上一個周期的私鑰xit-1信息簽名得:

并廣播式3和下面式4:

(4)

保存更新子密鑰份額ψit，j。

第二步:驗證階段

每個網(wǎng)絡(luò)成員節(jié)點Vi接收到n-1個ζit，j，用xit-1解密的得到上一個周期的秘密份額:ψit，i，然后通過下式(5)進行驗證:

(5)

如果上式通過驗證，則證明ψjt，i是正確的，然后計算節(jié)點成員Vi更新密鑰份額:

如果上式通不過驗證，則證明ψjt，i是不正確的，然后節(jié)成員Vi想網(wǎng)絡(luò)中廣播ψjt，i更新失敗。

第三步:更新階段

網(wǎng)絡(luò)中節(jié)點成員Vi需把原來的多項式更新為新的多項式:如下式(6)所示:

(6)

計算更新后的驗證參數(shù)不向網(wǎng)絡(luò)中廣播:如下式(7)所示:

(7)

計算成員節(jié)點Vi更新后的子組私鑰:

，計算并廣播子組公鑰份額:

，并向網(wǎng)絡(luò)中廣播子組公鑰份額。銷毀上一個周期的子組公鑰Yit-1。

網(wǎng)絡(luò)中每個成員節(jié)點隨機選擇τit∈Zq，更新周期t的節(jié)點成員私鑰:

xit=xit-1+τit·γit(mod q)，并銷毀上一個周期的私鑰xit-1，然后向網(wǎng)絡(luò)中廣播更新公鑰:yit=yit-1+τit-1·Yit(mod p)，并保存網(wǎng)絡(luò)所有其它節(jié)點成員公鑰{yjt}∈(1，2，…，n)。

3.2 子密鑰份額及時更新

對于子密鑰份額的及時更新，和上面子密鑰定時更新所基于原理基本相同，下面簡要進行概述。

情況一:網(wǎng)絡(luò)在執(zhí)行第N次子密鑰更新前，如果在監(jiān)控m時間內(nèi)，沒有發(fā)現(xiàn)某些節(jié)點有泄露或泄露嫌疑的子密鑰的情況下時，不對密鑰進行任何更新工作。

情況二:若在執(zhí)行第N次子密鑰更新前，在監(jiān)控m時間內(nèi)發(fā)現(xiàn)存在某些節(jié)點有泄露或泄露嫌疑的子密鑰的情況下，再判斷子密鑰泄露的數(shù)量。如果不大于門限值t，暫時不進行密鑰跟新工作，若大于門限值，立即進行密鑰更新工作。

4 方案的性能分析

4.1 安全性分析

4.1.1 被動攻擊分析和主動攻擊分析:

本方案的安全性是基于橢圓曲線離散對數(shù)的難解性的，任何攻擊者從廣播的信息中無法獲得系統(tǒng)私鑰信息;被動攻擊者從初始驗證參數(shù)βi，0=ai，1·A mod p得到βi，0是不可能的，因此，任何節(jié)點無法得到系統(tǒng)私鑰;在系統(tǒng)公鑰的生成過程中，任何從誠實成員的子系統(tǒng)公鑰都沒法到子系統(tǒng)私鑰，從而無法求出系統(tǒng)私鑰來;被動攻擊者無法從公鑰Y=X·B mod p中求出系統(tǒng)私鑰。

任何主動攻擊者要想獲得滿足的，根據(jù)上面的知識可求出ζ'it，改變子系統(tǒng)公鑰Yit'=pit'·B mod p，最后篡改系統(tǒng)公鑰。然而，根據(jù)雜湊函數(shù)的性質(zhì)，要想獲得有效的ζit’是不可能的，所以主動攻擊者無法篡改公鑰;主動攻擊者由γit、Фit和Hit求出Yit'≠Yit來滿足，根據(jù)雜湊函數(shù)的性質(zhì)也是不可能的，所以主動攻者擊最終也無法篡改系統(tǒng)公鑰。

4.1.2 效率分析

通過上面的安全性分析可知我們的方案具有較好的安全性能。本方案為了安全需要，在協(xié)商系統(tǒng)子密鑰份額時，節(jié)點的私鑰和公鑰由節(jié)點自己產(chǎn)生和計算，通信量雖然有所增加，但這是必不可少的。因為在不存在任何信任關(guān)系的的移動Ad hoc網(wǎng)絡(luò)中，利用基于各個參與者都是誠實可信的假設(shè)的密鑰共享是不可靠的。所以本方案采用了可驗證的秘密共享代替基本門限方案，實際上每個節(jié)點只不過增加了驗證時的計算開銷。另外，為了防止系統(tǒng)私鑰的泄露問題，本方案采用了雙重更新機制，由此每個節(jié)點多增加一輪的計算和通信量。其它方案中由可信中心CA或基于身份方案中TA為新節(jié)點分配密鑰份額雖然簡單，但響應(yīng)節(jié)點將泄露自己的密鑰份額，且請求方對接收到的密鑰份額并沒有要求驗證，所以在移動Ad hoc網(wǎng)絡(luò)中其實是不實用的也不現(xiàn)實。我們的方案可根據(jù)網(wǎng)絡(luò)的具體分布和大小等因素來選擇適當(dāng)?shù)母轮芷趖，加入及時更新有效解決了更新周期過大易帶來安全隱患，過小造成系統(tǒng)效率下降的問題，以達到最好的效果。

5 總結(jié)

本文通過對目前的Ad hoc網(wǎng)絡(luò)密鑰管理方案的分析，發(fā)現(xiàn)其存在的問題有，計算代價大，存在可信中心瓶頸，密鑰更新周期難以確定等問題，本方案提出了一種高效的Ad hoc網(wǎng)絡(luò)密鑰管理方案，該案具有計算代價小，網(wǎng)絡(luò)節(jié)點通過自組織方式協(xié)商系統(tǒng)密鑰，有效地防止了可信中心被攻擊的危險。通過引入密鑰及時更新有效提高了系統(tǒng)使用單一的密鑰定期更新的效率問題，適合大規(guī)模Ad doc網(wǎng)絡(luò)使用。

參考文獻:

[1] Perkins C E.Ad Hoc Networking[M].Addison Wesley Professional，2000.

[2] Lehane B，DoyleL，O_Mahony D.Shared RSA key generation in a mobile ad hoc network[C].Proceedings of IEEE Military Communications Conference (MILCOM2003)，2003.

[3] Ertaul L，Chavan N.Security of Ad Hoc Networks and Threshold Cryptography[Z].Wirelesscom，2005.

[4] Wu B，Wu J，F(xiàn)ernandezE，et al.Secure and Ef?cient Key Management in Mobile Ad Hoc Networks[C].Proc. of 19th IEEE International Parallel Distributed Processing Symposium，2005.

[5].徐春香，魏仕民，肖國鎮(zhèn).定期更新防欺詐的秘密共享方案[J].計算機學(xué)報，2002，25(6):657-660.