三叉樹結構下的群認證密鑰協商協議

張龍翔

臨沂大學信息學院，山東臨沂 276001

三叉樹結構下的群認證密鑰協商協議

張龍翔

臨沂大學信息學院，山東臨沂 276001

群密鑰協商幫助一組參與者通過在公開但不安全的網絡中交互信息來生成臨時的會話密鑰。這一密鑰可以用來實現參與者的安全目標，如身份認證、安全數據加密等。

根據密鑰建立方式的不同，群密鑰建立協議可分為兩種：一種為密鑰傳輸協議；另一種為密鑰協商協議。密鑰傳輸協議需要一個群控制者來掌握整個群的成員信息，因此一旦這個控制者被攻擊或者停止工作，密鑰建立過程就會失敗。但這種方式也有好處，即在群成員動態變化的情況下，密鑰傳輸協議的效率要更高；相比之下，密鑰協商協議不需要群控制者，群成員通過協商共同建立密鑰，盡管這種密鑰建立方式要消耗更多的計算資源，但由于其不依賴可信第三方，也無需為會話密鑰傳輸而建立安全信道，因此受到研究者和實踐者的青睞。

第一個密鑰協商協議是由Diffie與Hellman[1]提出的，該協議可以保證兩個參與者的安全通信，但是由于原協議沒有驗證參與者身份的環節，因此不能抵抗中間人攻擊。Joux[2]提出了密鑰協商的另一個方向，他利用Weil對構造了首個三方密鑰協商協議，在該方案中，三個參與者僅需各自發送一次消息即可建立會話密鑰，但遺憾的是，Joux協議也不能抵抗中間人攻擊，隨后學者們又提出了大量的適用于不同場景的群密鑰協商協議[3-5]。

顯然，任意群密鑰協商和群密鑰傳輸協議都可用于動態的參與者群。因為每當有新成員加入或退出，該方法都可以通過重啟協議來重新建立會話密鑰。然而，當群成員很多時，協議就會變得效率不高或者消耗大量的計算資源。在這種情況下，動態群密鑰協商應運而生。動態群密鑰協商的最大優點就是當群成員加入或離開時，協議的效率基本穩定。OFT（One-way Function Trees，單向函數樹）是這類協議常用到的函數之一，該函數可以生成密鑰樹，這些密鑰則是從單向函數樹的葉節點或者根節點生成的。1998年，Sherman等人[6]首次將OFT方法用在了動態密鑰協商中，作者同時指出任何一個滿足某些條件的雙方密鑰協商協議都可以擴展為基于OFT的多方密鑰協商。著名的群Diffie-Hellman協議[7]就是由雙方Diffie-Hellman協議擴展而來的基于OFT的群協議。

Reddy和Divya[8]利用OFT技術將基于身份的雙方認證密鑰協商協議進行擴展，得到了首個基于身份的群認證密鑰協商協議。在該協議中，葉子節點代表群眾的參與者。Sheng-Hua Shiau等人[9]的協議也使用的是該技術，不同的是本協議使用的是完全三叉樹結構，即協議中的每個節點代表一個參與者。2003年，Barua等人[10]將文獻[2]進行擴展，得到了基于Joux協議的多方密鑰協商協議。在該協議中，葉子節點代表的是參與者，而每個內部節點（Internal node）則是其所在子樹的代表，但遺憾的是該協議并未對協議的參與者身份進行認證。隨后，Dutta等人利用多簽名解決了該問題[11]。

本文提出了一種新的基于Weil配對的群密鑰協商協議。在新協議中，本方法采用基于身份的認證，并利用完全三叉樹以保證每個節點僅代表一個參與者。當有新成員加入或有成員離開群時，并不是所有的參與者都需要更新各自的計算結果來獲得新的會話密鑰，因此非常適合動態群的應用環境。

1 基礎知識

本章介紹一些本文用到的基礎知識。

假設G1是階為素數q的加群，P是它的生成元；G2是階為素數q的乘群。假定離散對數問題（DLP）在G1和G2中都是困難問題。令e是群G1和G2之間的雙線性映射e:G1×G1→G2。該雙線性映射必須滿足如下性質：

2 新的基于身份的群認證密鑰協商協議

為了順利執行新協議，參與者需要首先在PKG（Private Key Generator）中進行注冊，然后執行密鑰協商階段和成員變更階段。

2.1 初始化階段

本階段的主要任務是協助每個參與者在PKG上完成注冊，注冊完成后參與者就可以在密鑰協商階段生成群會話密鑰。為了完成注冊，PKG首先隨機選擇s∈，計算Ppub=sP作為自己的公鑰并將其公開，這里，s則是PKG的私鑰。

記每個參與者Ui的身份標識和長期公鑰分別為IDi∈{0,1}*和Qi=H(IDi)。參與者Ui將通過如下步驟完成注冊：

2.2 密鑰協商階段

在新協議中，密鑰協商過程基于完全三叉樹結構，每個節點代表一個參與者。圖1是16個參與者的示例。

圖116 個參與者的三叉樹結構

假設密鑰協商群中有n個參與者，每個參與者Ui(i∈{1,2,…,n})的長期公私鑰分別為Qi和Si。在每輪新協議開始時，參與者Ui還將選擇一個隨機數ai作為自己的臨時私鑰。在一個完全三叉樹中，共有四種不同的節點類型：葉節點、只有一個左側子節點的內部節點、有兩個子節點的內部節點、內部節點且有三個子節點。

2.2.1 節點為葉節點(3i＞n)

（1）令ti=ai。

（2）Ui將tiP發送給它的父節點以及它的同級節點。

2.2.2 節點為只有一個左子節點的內部節點(3i-1=n)

四個參與者的會話密鑰都是相等的。

2.3 成員變更階段

顯然，在通信過程中會有成員的退出和加入問題。為了協議的安全性，未加入的或已退出的成員是不能獲取通信群中的消息的。因此本文有必要研究成員的加入和退出協議。

2.3.1 成員加入協議

假設在有新成員加入前，群中共有n個參與者，當有新成員加入時，它將執行如下步驟：

（1）參與者U1首先讓新的參與者Un+1發送群成員的個數和所有成員的公開密鑰。

（3）根據參與者數量n的不同，將有以下三種方式生成會話密鑰：

①n=0mod3

如圖2所示，在這種情況中，當新節點加入后最后一個父節點有三個子節點。

圖2 參與者個數為3的倍數的情景示例

假設新加入者Un+1的父節點是Ui，這時Ui有三個子節點，Un+1的角色類似于U3i+1：

如圖3所示，在這種情況中，當新節點加入后最后一個父節點只有一個子節點。

圖3 參與者個數為模3余1的情景示例

假設新加入者Un+1的父節點是Ui，這時Ui只有一個子節點，其密鑰協商類似于2.2.2節中的過程：

如圖4所示，在這種情況中，當新節點加入后最后一個父節點有兩個子節點。

圖4 參與者個數為模3余2的情景示例

假設新加入者Un+1的父節點是Ui，這時Ui只有一個子節點，其密鑰協商類似于2.2.3節中的過程：

2.3.2 成員離開協議

假設原始的群中共有n個參與者，離開的成員為Ul。這時本方法可以交換Un和Ul的位置，然后刪除Ul以便計算新的會話密鑰。根據l的不同位置，本階段可以分為以下三種情況：

（1）l=n

在這種情況下，Ul是群成員中的最后一個成員，因此協議可以直接刪除掉Ul以生成新的會話密鑰：

①如果n=3k+1，令i=(n+2)/3。當Ul離開群后，參與者Ui有兩個子節點。Ui選擇隨機值a~i作為自己的臨時私鑰，然后根據2.2.3節的步驟生成會話密鑰：

在這種情況下，離開群的參與者的位置是三叉樹的根。因此這時協議可以刪除根節點U1并且用Un代替，然后執行情景（1）中的計算過程。

在這種情況下，協議可以刪除根節點Ul并且用Un代替，然后執行情景（1）中的計算過程。

3 討論

本章重點討論新協議的安全性和計算性能。

3.1 安全性分析

安全性是保證協議能夠運行在實際平臺中的最基本要求。新協議不僅具備已知密鑰安全和密鑰可認證性，還具備前向安全性、密鑰可控制性，并可抵抗密鑰泄露偽裝攻擊。

（1）已知密鑰安全性[12-13]

已知密鑰安全是指，如果一次通信的會話密鑰泄露，本次通信的會話密鑰安全性不會受到影響。在本協議中，假設共有四個參與者U1、U2、U3和U4，那么之前的會話密鑰為如果敵手想要獲得當前的會話密鑰，它必須知道參與者選取的臨時私鑰，而獲得臨時私鑰的唯一方法是求解BDHP問題，顯然，這是一個NP完全問題。因此，新協議具有已知密鑰安全性。

（2）密鑰可認證性

密鑰可認證性是指協議應該保證只有合法的參與者才能參與密鑰協商，沒有經過認證的參與者是不允許進行密鑰協商的。在新協議中，每個參與者都要用自己的長期私鑰對各自的消息進行簽名，同時，當參與者收到發來的消息時要進行驗證。因此，參與者的身份是可以得到保證的。

（3）前向安全性[14]

如果一個參與者的長期私鑰被泄露，那么之前的會話密鑰的安全性不應受到影響，這就是前向安全性的含義。在本協議中，長期私鑰僅用于身份認證，在每次會話中都要依賴于本次會話臨時產生的臨時私鑰來生成會話密鑰，從而保證了協議的前向安全性。

（4）抗密鑰泄露偽裝攻擊[15]

這一性質用來保證敵手在獲得某一個參與者的長期私鑰后去冒充其他參與者。由于在本協議中的長期私鑰被用于身份認證而非密鑰協商，因此本方法無需考慮該攻擊。換句話說，新協議是滿足這一安全要求的。

（5）密鑰控制性[15]

密鑰控制性是指密鑰協商協議中的任何一方參與者都不可以事先決定或影響會話密鑰的值。在本文的協議中，密鑰是通過每個參與者利用各自的長期和臨時公私鑰對通過雙線性對計算得到的，顯然不存在由一方參與者事先確定的情況。

表1 性能比較

3.2 性能分析

除了安全性，方案的性能也是影響方案能否用于實際的重要指標。本節將用新方案與文獻[8-9]進行對比。選擇這兩個方案作為比較對象是因為文獻[8-9]都是基于樹狀結構的方案。記R(n)為協議的輪數，B(n)為消息傳輸的數量，P(n)為雙線性對運算數量。如表1所示，顯然本文的方案有明顯的優勢。

4 結論與下一步工作

本文提出了一種在三叉樹結構下的群密鑰協商協議。新協議的每個參與者都可以通過基于身份的認證結構對收到的消息進行認證。為了解決群密鑰協商中成員變動問題，還提出了成員的加入和離開協議。

但是對協議的安全性分析還停留在啟發式論證層面上，沒有給出嚴格的形式化證明，這也是今后要改進的方向。

[1]Diffie W，Hellman M.New directions in cryptography[J]. IEEE Transactions on Information Theory，1976，22（6）：644-654.

[2]Joux A.A one-round protocol for tripartite Diffie-Hellman[C]// LNCS 1838：Proceedings of the 4th International Algorithmic Number Theory Symposium（ANTS-IV）.Berlin：Springer-Verlag，2000：385-394.

[3]鄧少鋒，鄧帆，李益發.有效的強安全組群密鑰交換協議[J].計算機應用，2010，30（7）：1805-1808.

[4]劉雪艷，張強，王彩芬.Ad Hoc網絡中基于身份的簇密鑰協商機制[J].計算機應用，2012，32（8）：2258-2327.

[5]唐宏斌，劉心松.魯棒且高效的遠程認證及密鑰協商協議[J].計算機應用，2012，32（5）：1381-1384.

[6]Sherman A，McGrew D.Key establishment in large dynamic groups using one-way function trees[J].IEEE Trans on Software Engineering，2003，29（5）：444-458.

[7]Kim Y，Perrig A，Tsudik G.Simple and fault-tolerant key agreement for dynamiccollaborativegroups[C]//Proceedings of 7th ACM Conference on Computer and Communication Security，2000：235-244.

[8]Chen L，Kudla C.Identity based authenticated key agreement protocols from pairings[C]//Proc of the 16th IEEE Computer Security Foundations Workshop，2003：219-233.

[9]Xie G.An ID-based key agreement scheme from pairing[EB/OL].（2011-04-20）.http：//eprint.iacr.org/2005/093.pdf.

[10]Barua R，Dutta R，Skrkar P.Extending Joux’s protocol to multiparty key exchange[C]//Proceedings of Indocrypt 2003. Berlin：Springer-Verlag，2003：205-217.

[11]Dutta R，Barua R.Constant round dynamic group key agreement[C]//LNCS 3650：Proceedings of ISC 2005.Berlin：Springer-Verlag，2005：74-88.

[12]Yacobi Y，Shmuely Z.On key distribution systems[C]//Crypto 1989.Berlin：Springer，1989，435：344-355.

[13]Yacobi Y.A key distribution“paradox”[C]//Crypto 1990.Berlin：Springer，1990，537：268-273.

[14]Krawczyk H.HMQV：a high-performance secure Diffie-Hellman protocol[C]//Crypto 2005.Berlin：Springer，2005：546-566. [15]Cheng Qingfeng，Ma Chuangui，Hu Xuexian.A new strongly secure authenticated key exchange protocol[C]//Proc of ISA 2009.Berlin：Springer，2009：135-144.

ZHANG Longxiang

School of Information,Linyi University,Linyi,Shandong 276001,China

Group Key Agreement（GKA）is an important research point in key establishment field.This paper proposes a new ID-based GKA protocol in ternary tree structure.It also considers the situation when some participants change.It discusses the security and computational cost of the new scheme.The result shows that the new protocol realizes the secure key agreement with lower computational cost.

cryptography;secure protocol;group key agreement;bilinear pairing;ternary tree

群密鑰協商是密鑰協商協議的一個重要研究分支。提出了一種在三叉樹結構下基于身份的群認證密鑰協商協議，充分考慮了成員加入和離開時的子協議。還對方案的安全性和性能進行了分析。結果表明，新方案在計算量減少的前提下實現了協議多方的安全密鑰協商。

密碼學；安全協議；群密鑰協商；雙線性對；三叉樹

A

TP309.7

10.3778/j.issn.1002-8331.1305-0038

ZHANG Longxiang.Novel group authenticated key agreement protocol in ternary tree structure.Computer Engineering and Applications,2013,49（24）：83-87.

張龍翔（1976—），通訊作者，男，講師，主要研究領域為網絡安全、模式識別。E-mail：lxzhang76@163.com

2013-05-08

2013-09-02

1002-8331（2013）24-0083-05