ad hoc網絡具有撤銷機制的密鑰管理方案

孫 梅，張 娟

SUN Mei,ZHANG Juan

淮北師范大學 計算機科學與技術學院，安徽 淮北 235000

College of Computer Science and Technology,Huaibei Normal University,Huaibei,Anhui 235000,China

1 引言

ad hoc網絡是一種無網絡基礎設施的無線自組織網絡。與傳統的網絡相比，ad hoc網絡具有以下特點：（1）自組織性，所有的移動節點都具有路由器和終端節點的雙重身份，節點之間通過分布式算法實現互聯互通；（2）沒有中心認證機構和公鑰基礎設施；（3）網絡拓撲動態變化，網絡中的節點具有移動特性，且節點可能在任意時刻關機或離開網絡；（4）節點的帶寬和能源有限。ad hoc網絡的自組織方式，有限的網絡帶寬和能源，無線通信等特點，使得傳統有線網絡中基于PKI的中心式密鑰管理方案不適用于該網絡。

針對ad hoc網絡的特點——沒有中心認證機構和公鑰基礎設施，將信任分布化是解決ad hoc網絡密鑰管理的一種有效的手段。Zhou和Hatz[1]首先提出了基于(n，t)門限密碼的分布化ad hoc密鑰管理方案，但沒有實現完全分布化，仍需要密鑰產生中心進行系統密鑰的分發。后來Luo[2]等提出了自安全的ad hoc網絡，無需第三方，靠節點相互協作產生并分發系統密鑰。Kong等人[3-4]給出了安全分布式密鑰管理方案，網絡中的所有節點都是服務節點，均可與其他節點完成密鑰服務的功能。上述方案[1-4]都是采用基于證書的RSA公鑰機制實現的，算法的開銷大，且安全性不高。

Khalili[5]提出了基于ID的ad hoc網絡密鑰管理機制。基于ID的密碼體制[6]可以使用較短的密鑰滿足較高的安全要求，適合資源有限的ad hoc網絡。Deng[7]等提出了一種基于ID的ad hoc網絡的密鑰管理方案，以完全分布式安全地建立用戶私鑰；杜春來等[8]提出了一種建立在橢圓曲線域上的基于雙向身份認證的移動ad hoc密鑰管理框架；李慧賢等[9]給出了適合ad hoc網絡無需安全信道的密鑰管理方案，可以在公共信道上傳輸節點密鑰，相對其他方案[5，7]能更好地節省帶寬和節點的能量。以上方案[7-9]都是基于ID的密碼體制的，主要采用橢圓曲線密碼體制，公鑰短，計算量小；采用分布化方式產生系統密鑰和用戶密鑰，有效避免了單點失敗，安全性較好。但是沒有考慮用戶密鑰泄漏，或發生異常后如何撤銷原有密鑰以及重新設定新密鑰等問題。

基于以上原因，本文借鑒文獻[9]的方案，在無需安全信道的基礎上給出了一個具有密鑰撤銷機制的基于身份的ad hoc網絡密鑰管理方案，并在此基礎上實現了用戶簽名。方案在門限密碼學的基礎上采用橢圓密碼體制以完全分布化方式建立系統密鑰。分析表明該方案不僅有良好的容錯性，能有效節省帶寬和計算量，能抵御網絡傳統的主動和被動攻擊等特點，而且可以在密鑰泄漏的情況下，通過注銷用戶密鑰，有效防止攻擊者的偽造攻擊。即使攻擊者成功偽造了用戶的簽名，用戶還可以通過系統簽名注銷消息來證明偽造簽名無效。方案具有更高的安全性。

2 雙線性映射的基本理論

（1）雙線性映射：設 (G1，+)，(G2，·)為階是素數 q 的循環群。稱滿足如下性質的映射e:G1×G1→G2為雙線性映射：

①雙線性性：任意 P,Q∈G1，任意a,b∈Z*q，總有 e(aP，bQ)=e(P，Q)ab。

②非退化性：存在 P,Q∈G1，滿足 e(P，Q)≠1G2。

③可計算性：任意P,Q∈G1，存在一個有效的算法計算e(P，Q)。

（2）相關的困難問題：設P是(G1，+)的一個生成元，給出(G1，+)上的一個困難問題。

計算Diffie-Hellman問題（CDH問題）：已知(P，aP，bP)，計算abP，其中a,b∈Z*q是未知的。

3 具有密鑰撤銷機制的ad hoc網絡基于身份的密鑰管理方案

本文借鑒文獻[9]的方法由一個離線的局部注冊中心（Local Registration Authority，LRA）來實現用戶身份的鑒別，用戶私鑰的發布不需要安全通道，系統密鑰和用戶私鑰由多個分布式密鑰生成中心（Distributed Key Generation Center，DKGC）協作生成。在該方案中，每個用戶有一個唯一的固定長度的ID來表示身份信息。為了區分用戶各時間段的密鑰，每個用戶在申請密鑰時，隨機選擇一個數K和ID綁定。若在某一時刻用戶發現自己的密鑰異常或泄漏了，可以向密鑰服務節點申請注銷K和ID的綁定，重新選取一個新的隨機數和ID綁定，產生新的密鑰。密鑰服務節點將已注銷的ID與K保存在注銷列表中，并將此注銷消息向全網廣播。當有攻擊者竊取他人私鑰偽造簽名時，其他用戶可以通過查詢注銷列表，發現其偽造行為。

3.1 系統初始化

系統選擇兩個階數同為素數q的群(G1，+)和(G2，·)，P是G1的生成元，e:G1×G1→G2是安全的雙線性映射，{1,2，…，N}，N為網絡節點總數）表示ad hoc網絡中每個節鑰為s，公鑰為Ppub=sP。參與系統密鑰生成的DKGC節點數為 n(1≤n≤N)，門限值為 t(t≤n≤2t-1)。n個DKGC組成一個組播組，它們之間可以使用組播協議通信。每個DKGC節點建立兩個列表：注銷列表和運行列表，注銷列表用來保存用戶注銷過的ID與K的綁定，運行列表用來保存目前用戶正在使用的ID與K的綁定。用戶初始登錄網絡時，可以從離自己最近的DKGC節點復制注銷列表，以后根據系統廣播的注銷消息更新復制的注銷列表。

3.2 系統密鑰產生

每個服務節點 DKGCi(i=1，2，…，n)隨機選擇一個秘密數，建立一個t-1階多項式 fi(x)：

然后向其他DKGC節點發送部分密鑰份額si，j=fi(j)(j≠i)，同時計算 Vi，0=diP ，Vi，k=ai，kP(k=1，2，…，t-1)，并將其在組播組中組播。節點DKGCj收到si，j后驗證等式（1）是否成立。

DKGCj在收到 n-1個有效的 si，j(i≠j)后，計算自身的

3.3 用戶注冊

用戶節點ul（其身份標識為IDl），首先到LRA離線注冊一個盲因子，具體做法如下：

用戶ul選擇一個秘密隨機數計算盲因子 Rl=rlP，然后將(IDl，Rl)提交給LRA。LRA計算Ul=H(IDLRA||IDl||Rl||Tl)，Sigl=s0Ul，Tl為盲因子的有效期。

3.4 用戶密鑰發布

用戶ul要獲得密鑰，可以向離自己最近的一個DKGC節點提交請求信息，具體過程如下：

（1）用戶 ul選擇一個隨機數，并計算Yl=rlH(IDl||Kl||dt)，dt為密鑰生效時間（＞當前時間），然后將{IDl，IDLRA，Rl，Sigl，Tl，Yl，Kl，dt}發送給離自己最近的一個DKGC節點，記為 DKGCi。

（2）DKGCi驗證等式（2），（3）：

若兩式都成立，DKGCi將此請求信息 {IDl，IDLRA，Rl，Sigl，Tl，Yl，Kl，dt} 在組播組中組播，并找出 t-1 個 DKGC 節點（記為 DKGCi(i=1，2，…，t)），共同協作為 ul生成密鑰。DKGCi為ul計算部分密鑰 Xi=siYl，并通過公開信道發送給ul。系統的每個DKGC節點都將用戶的申請信息{IDl，IDLRA，Rl，Sigl，Tl，Yl，Kl，dt}保存在自己運行列表中。

（3）ul收到 DKGCi的 Xi后驗證等式（4）是否成立。

在t個 Xi被驗證通過后，計算密鑰：

3.5 用戶密鑰的注銷和新密鑰的申請

（1）如果用戶ul發現密鑰異常或泄漏，可以向離自己最近的DKGC節點（記為DKGCk）提交注銷密鑰的申請信息rq，rq中包括用戶的身份 IDl，隨機數Kl，以及注銷時間（≥當前時間）等。如果用戶需要新的用戶密鑰，同時提交{IDl，IDLRA，Rl，Sigl，Tl，Yl'，Kl'，dt'}等信息，其中為用戶ul選擇的一個新的不重復隨機數，Yl'=rlH(IDl||Kl'||dt')，dt'為新密鑰生效時間（＞注銷時間和當前時間）。

（2）DKGCk對申請信息進行審核，即驗證等式（2）和（5）：

若審核通過，首先，DKGCk在網絡中廣播取消IDl和Kl的綁定，其他節點（包括DKGC節點）將IDl和Kl以及注銷時間添加到自己的注銷列表中，DKGC節點在運行列表中刪除IDl和Kl的綁定；然后，DKGCk在組播組中組播rq和{IDl，IDLRA，Rl，Sigl，Tl，Yl'，Kl'，dt'}，并找出 t-1個DKGC節點（記做 DKGCi(i=1，2，…，t)），共同協作為 ul生成密鑰。DKGCi為 ul計算 σi=siH(rq)和 Xi'=siYl'，并通過公開信道發送給ul；最后，系統的各DKGC節點將新的綁定信息 {IDl，IDLRA，Rl，Sigl，Tl，Yl'，Kl'，dt'}保存到自己的運行列表中。

（3）ul收到DKGCi的 Xi后驗證下列等式是否成立。

在t個 Xi被驗證通過后，計算密鑰：

和注銷消息的系統簽名：

3.6 用戶簽名

本文的簽名方案是對Hess[10]的基于身份的簽名方案進行了擴展，Hess的方案安全性建立在CDH問題難解的基礎上，且已在Random Oracle模型下證明是CPA（選擇明文攻擊）安全的。

若用戶uk需要ul為信息m簽名，那么ul隨機選擇一個秘密數 w∈Z*q，計算 γ=e(P，P)w，得到消息m的Hash值v=H1(m||γ||dt1)，dt1為簽名時間，產生簽名：

ul將簽名{λ，IDl，Kl，dt，m，v，dt1}(dt1≥ dt)發送給用戶uk，uk收到后檢查自己是否有注銷列表，若無，則向離自己最近的DKGC發送復制注銷列表的請求，在復制的注銷列表中，uk檢查 IDl，Kl，dt是否存在，若存在，則認定簽名無效。否則計算 γ'=e(λ，P)e(H(IDl||Kl||dt)， -Ppub)v，當且僅當v=H1(m||γ′||dt1)時接受簽名。

4 密鑰管理方案及用戶簽名方案的正確性分析

定理2 用戶簽名{λ，IDl，Kl，dt，m，v，dt1}(dt1≥dt)的有效性可以通過注銷列表和等式v=H1(m||γ'||dt1)來驗證。

證明 假如綁定信息 IDl，Kl，dt(dt1≥dt)出現在注銷列表中說明用戶ul在dt時刻已經注銷了自己的密鑰，所以本次簽名是無效的。若密鑰未被注銷則可以計算：

5 密鑰管理方案及用戶簽名方案的安全性和性能分析

5.1 密鑰管理方案的安全性分析

本方案的安全性基于橢圓曲線上的離散對數問題的困難性，同時采用了基于盲簽名的傳輸方案，保證了在公共通道上傳輸用戶密鑰的安全性。

（1）和文獻[9]相比，本文提出的方案也可以達到第III級信任[9]，即信任用戶和可信第三方（Trust Third Party，TTP）不知道用戶的私鑰，若TTP產生了假的用戶公鑰，可以證明該公鑰為假。

在本文方案中，每個DKGC節點只發布了用戶ul的部分私鑰，它并不知道用戶的完整私鑰。如果有惡意的DKGC節點假冒ul欺騙其他DKGC節點，它首先要選擇一個rl′∈，偽造LRA的簽名為。其他DKGC節點可以通過等式（2）來進行驗證，發現其偽造行為，即e(Sigl'，P)≠e(Ul'，PLRA)，所以惡意的DKGC節點無法偽造 ul。如果LRA要假冒用戶ul，它選擇一個，計算 Rl''=rl''P ，Ul''=H(IDLRA||IDl||Rl''||Tl)和簽名Sigl''=s0''Ul''，然后向某個DKGC發送請求信息，系統中至少有一個DKGC節點能根據運行列表中的Sigl≠Sigl''識別出惡意的LRA偽造了用戶ul，所以LRA也無法偽造用戶ul。其他的惡意節點想偽造ul，需要從 Rl=rlP，PLRA=s0P中計算出rl和 s0，這是離散對數問題。所以本文方案可以達到第III級信任。

（2）同文獻[9]，本文的密鑰管理方案也具有容錯性，即使有n-t個服務節點被攻擊，系統還可以提供密鑰服務。證明方法參見文獻[9]。

（3）同文獻[9]，本文在密鑰發布過程中能抵御主動攻擊，包括重放攻擊，中間人攻擊，內部攻擊。同時也能抵御被動攻擊。證明方法見文獻[9]。

5.2 用戶簽名方案的安全性分析

（1）安全模型

基于身份數字簽名方案的攻擊模型[11]，即攻擊者A和挑戰者C進行以下對局：

①運行系統初始化算法并將系統參數給A。

②A行以下詢問：

hash詢問，C計算輸入消息的hash值，并把結果給A。

身份詢問，給定一個身份ID，C返回給A與該ID對應的私鑰。

簽名詢問，給定一個身份ID和消息M，返回給A一個ID對M的簽名λ。

③A 輸出 (ID′，M′，λ′)并認為 λ′是 ID′對 M′的簽名。如果λ′是有效的簽名并且(ID'，M')沒有進行過簽名詢問，則稱攻擊者A贏得對局。

定理3假設G1中CDH問題是困難的，提出的基于身份的用戶簽名方案在隨機預言模型下抗適應性選擇消息和給定身份攻擊。

證明 假設攻擊者A能攻破用戶簽名方案，利用A能構造一個有效的算法C，C可以解G1中的CDH問題，即給定(P，aP，bP)，C欲計算 abP 。C具有{IDl，Kl，dt，Yl，yl}列表，C置PPub=aP，并如下回答A的詢問。

①ID-hash詢問。當A詢問 ＜IDi，Ki，dti＞ 的hash值時，如果 IDi=IDl，Ki=Kl，dti=dt，C 給 A 回答 H(IDi||Ki||dti)=

②密鑰提取詢問。當A詢問 ＜IDik，Kik，dtik＞的密鑰值的私鑰。A不能詢問 ＜IDl，Kl，dt＞ 對應的私鑰bP。

③消息hash詢問。A可以進行qH次消息hash詢問，息hash值返回給A。

④簽名詢問。A詢問IDit對消息mit的簽名，C按照如下步驟回答：

證畢。

（2）在密鑰泄漏的情況下，通過注銷用戶密鑰，可有效防止攻擊者的偽造攻擊。

如果用戶ul密鑰泄露了，他可以向DKGC節點申請注銷密鑰。系統通過廣播注銷消息，使其他用戶都知道IDl和Kl的綁定已經被注銷了，若在此之后有人提交了簽名{λ，IDl，Kl，dt，m，v，dt1}(dt1≥ dt)，則可以認定該簽名無效；假如有新用戶初始登錄網絡，并且沒有收到該注銷消息，他可以選擇從某個DKGC節點復制注銷列表而得知該注銷消息。即使有惡意的DKGC節點偽造了假的注銷列表，使該簽名有效，ul還可以通過系統簽名注銷消息σ=sH(rq)證明該密鑰已經在dt1之前被注銷了。因此，通過注銷用戶密鑰可有效防止攻擊者的偽造攻擊，同時又不影響密鑰注銷之前的簽名，因為在注銷列表中有密鑰注銷的時間，用戶簽名時有簽名時間，只要簽名時間小于注銷時間就認為簽名是有效的。

5.3 性能分析

本文采用節點身份作為它的公鑰，不需要額外的公鑰生成和傳輸過程。方案的實現主要基于橢圓曲線密碼體制，該體制計算量小，安全性高[12]。因此，該方案比傳統的公鑰算法的ad hoc密鑰管理方案[1-4]具有更低的計算代價和通信代價。本文方案中，用戶密鑰的發布無需安全通道，與現有文獻[5，7]相比，能節省通信代價和計算代價[9]。另外本文方案中，密鑰服務節點形成了一個組播組，對于驗證數據采用組播傳輸代替文獻[8-9]的全網廣播，有效節省了通信帶寬——如文獻[9]系統密鑰產生需要單播n(n-1)次，廣播2n次通信，用戶密鑰發布需要單播2t次；而本文方案系統密鑰產生需要單播n(n-1)次，組播n次，廣播n次，用戶密鑰發布需要單播1+t次，組播1次。本文在注銷密鑰后，重新申請密鑰時，只需用戶自己重新選定一個隨機數，并不需要更換用戶的ID，不需要LRA重新鑒定身份，有效節省了通信帶寬和計算量。對于注銷的密鑰，本文使用注銷列表來保存，只有在密鑰泄漏或異常才可能注銷密鑰，這些情況是比較少的，所以注銷列表并不是很大，不會過多占用節點的存儲空間，ad hoc網絡的節點有能力滿足方案的要求。

6 結語

本文針對ad hoc可能會出現的密鑰泄漏，異常，離開網絡等情況，將密鑰撤銷機制應用在密鑰管理中，不僅有效減少了密鑰泄漏后給用戶帶來的損失，而且不會影響密鑰泄漏前用戶簽名的有效性。方案同時將組播技術應用在ad hoc網絡中，節省了系統的帶寬和節點的能量，另外采用門限方案增強了系統的健壯性，具有較好的理論和實用價值。

[1]Zhou L，Hass Z J.Securing ad hoc networks[J].IEEE Network，1999，13（6）：24-30.

[2]Luo H，Zefros P，Kong J，et al.Self-securing ad hoc wireless networks[C]//Proceedings of the Seventh IEEE Symposium on Computers and Communications（ISCC’02）.Taormina：IEEE Press，2002：548-555.

[3]Kong J，Zefros P，Luo H，et al.Providing robust and ubiquitous security support for mobile ad-hoc networks[C]//Proceedings of 9th International Conference on Network Protocols（ICNP’01）.Riverside，CA：IEEE Press，2001：251-260.

[4]Luo H，Kong J，Zerfos P，et al.Ubiquitous and robust access control for mobile ad hoc networks[J].ACM Transactions on Networking，2004，12（6）：1049-1063.

[5]Khalili A，Katz J，Arbaugh W A.Toward secure key distribution in truly ad-hoc networks[C]//Proceedings of the Symposium on Applications and the Internet Workshops（SAINT’03）.Orlando，FL，USA：IEEE Press，2003：342-346.

[6]Boneh D，Franklin M K.Identity-based encryption from the Weil pairing[J].SIAM Journal of Computing，2003，32（3）：586-615.

[7]Deng H，Mukherjee A，Agrawal D P.Threshold and identitybased key management and authentication for wireless ad hoc networks[C]//The International Conference on Information Technology：Coding and Computing（ITCC’04）.Las Vegas，USA：IEEE Press，2004：107-110.

[8]杜春來，胡銘曾，張宏莉.在橢圓曲線域中基于身份認證的移動ad hoc密鑰管理框架[J].通信學報，2007，28（12）：53-59.

[9]李慧賢，龐遼軍，王育民.適合ad hoc網絡無需安全信道的密鑰管理方案[J].通信學報，2010，31（1）：112-117.

[10]Hess F.Efficient identity based signature schemes based on pairings[C]//LNCS 2595：Selected Areas in Cryptography（SAC 2002）.Berlin：Springer-Verlag，2003：310-324.

[11]Pointcheval D，Stern J.Security proofs for signature schemes[C]//EUROCRYPT’96.Berlin：Springer-Verlag，1996：387-398.

[12]Boneh D，Lynn B，Shacham H.Short signatures from the Weil pairing[C]//LNCS 2248：Advances in Cryptology-Asiacrypt 2001.Berlin：Springer-Verlag，2001：514-532.