張龍翔

臨沂大學(xué)信息學(xué)院，山東臨沂 276001

三叉樹(shù)結(jié)構(gòu)下的群認(rèn)證密鑰協(xié)商協(xié)議

張龍翔

臨沂大學(xué)信息學(xué)院，山東臨沂 276001

群密鑰協(xié)商幫助一組參與者通過(guò)在公開(kāi)但不安全的網(wǎng)絡(luò)中交互信息來(lái)生成臨時(shí)的會(huì)話密鑰。這一密鑰可以用來(lái)實(shí)現(xiàn)參與者的安全目標(biāo)，如身份認(rèn)證、安全數(shù)據(jù)加密等。

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

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

顯然，任意群密鑰協(xié)商和群密鑰傳輸協(xié)議都可用于動(dòng)態(tài)的參與者群。因?yàn)槊慨?dāng)有新成員加入或退出，該方法都可以通過(guò)重啟協(xié)議來(lái)重新建立會(huì)話密鑰。然而，當(dāng)群成員很多時(shí)，協(xié)議就會(huì)變得效率不高或者消耗大量的計(jì)算資源。在這種情況下，動(dòng)態(tài)群密鑰協(xié)商應(yīng)運(yùn)而生。動(dòng)態(tài)群密鑰協(xié)商的最大優(yōu)點(diǎn)就是當(dāng)群成員加入或離開(kāi)時(shí)，協(xié)議的效率基本穩(wěn)定。OFT（One-way Function Trees，單向函數(shù)樹(shù)）是這類協(xié)議常用到的函數(shù)之一，該函數(shù)可以生成密鑰樹(shù)，這些密鑰則是從單向函數(shù)樹(shù)的葉節(jié)點(diǎn)或者根節(jié)點(diǎn)生成的。1998年，Sherman等人[6]首次將OFT方法用在了動(dòng)態(tài)密鑰協(xié)商中，作者同時(shí)指出任何一個(gè)滿足某些條件的雙方密鑰協(xié)商協(xié)議都可以擴(kuò)展為基于OFT的多方密鑰協(xié)商。著名的群Diffie-Hellman協(xié)議[7]就是由雙方Diffie-Hellman協(xié)議擴(kuò)展而來(lái)的基于OFT的群協(xié)議。

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

本文提出了一種新的基于Weil配對(duì)的群密鑰協(xié)商協(xié)議。在新協(xié)議中，本方法采用基于身份的認(rèn)證，并利用完全三叉樹(shù)以保證每個(gè)節(jié)點(diǎn)僅代表一個(gè)參與者。當(dāng)有新成員加入或有成員離開(kāi)群時(shí)，并不是所有的參與者都需要更新各自的計(jì)算結(jié)果來(lái)獲得新的會(huì)話密鑰，因此非常適合動(dòng)態(tài)群的應(yīng)用環(huán)境。

1 基礎(chǔ)知識(shí)

本章介紹一些本文用到的基礎(chǔ)知識(shí)。

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

2 新的基于身份的群認(rèn)證密鑰協(xié)商協(xié)議

為了順利執(zhí)行新協(xié)議，參與者需要首先在PKG（Private Key Generator）中進(jìn)行注冊(cè)，然后執(zhí)行密鑰協(xié)商階段和成員變更階段。

2.1 初始化階段

本階段的主要任務(wù)是協(xié)助每個(gè)參與者在PKG上完成注冊(cè)，注冊(cè)完成后參與者就可以在密鑰協(xié)商階段生成群會(huì)話密鑰。為了完成注冊(cè)，PKG首先隨機(jī)選擇s∈，計(jì)算Ppub=sP作為自己的公鑰并將其公開(kāi)，這里，s則是PKG的私鑰。

記每個(gè)參與者Ui的身份標(biāo)識(shí)和長(zhǎng)期公鑰分別為IDi∈{0,1}*和Qi=H(IDi)。參與者Ui將通過(guò)如下步驟完成注冊(cè)：

2.2 密鑰協(xié)商階段

在新協(xié)議中，密鑰協(xié)商過(guò)程基于完全三叉樹(shù)結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)代表一個(gè)參與者。圖1是16個(gè)參與者的示例。

圖116 個(gè)參與者的三叉樹(shù)結(jié)構(gòu)

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

2.2.1 節(jié)點(diǎn)為葉節(jié)點(diǎn)(3i＞n)

（1）令ti=ai。

（2）Ui將tiP發(fā)送給它的父節(jié)點(diǎn)以及它的同級(jí)節(jié)點(diǎn)。

2.2.2 節(jié)點(diǎn)為只有一個(gè)左子節(jié)點(diǎn)的內(nèi)部節(jié)點(diǎn)(3i-1=n)

四個(gè)參與者的會(huì)話密鑰都是相等的。

2.3 成員變更階段

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

2.3.1 成員加入?yún)f(xié)議

假設(shè)在有新成員加入前，群中共有n個(gè)參與者，當(dāng)有新成員加入時(shí)，它將執(zhí)行如下步驟：

（1）參與者U1首先讓新的參與者Un+1發(fā)送群成員的個(gè)數(shù)和所有成員的公開(kāi)密鑰。

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

①n=0mod3

如圖2所示，在這種情況中，當(dāng)新節(jié)點(diǎn)加入后最后一個(gè)父節(jié)點(diǎn)有三個(gè)子節(jié)點(diǎn)。

圖2 參與者個(gè)數(shù)為3的倍數(shù)的情景示例

假設(shè)新加入者Un+1的父節(jié)點(diǎn)是Ui，這時(shí)Ui有三個(gè)子節(jié)點(diǎn)，Un+1的角色類似于U3i+1：

如圖3所示，在這種情況中，當(dāng)新節(jié)點(diǎn)加入后最后一個(gè)父節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)。

圖3 參與者個(gè)數(shù)為模3余1的情景示例

假設(shè)新加入者Un+1的父節(jié)點(diǎn)是Ui，這時(shí)Ui只有一個(gè)子節(jié)點(diǎn)，其密鑰協(xié)商類似于2.2.2節(jié)中的過(guò)程：

如圖4所示，在這種情況中，當(dāng)新節(jié)點(diǎn)加入后最后一個(gè)父節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)。

圖4 參與者個(gè)數(shù)為模3余2的情景示例

假設(shè)新加入者Un+1的父節(jié)點(diǎn)是Ui，這時(shí)Ui只有一個(gè)子節(jié)點(diǎn)，其密鑰協(xié)商類似于2.2.3節(jié)中的過(guò)程：

2.3.2 成員離開(kāi)協(xié)議

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

（1）l=n

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

①如果n=3k+1，令i=(n+2)/3。當(dāng)Ul離開(kāi)群后，參與者Ui有兩個(gè)子節(jié)點(diǎn)。Ui選擇隨機(jī)值a~i作為自己的臨時(shí)私鑰，然后根據(jù)2.2.3節(jié)的步驟生成會(huì)話密鑰：

在這種情況下，離開(kāi)群的參與者的位置是三叉樹(shù)的根。因此這時(shí)協(xié)議可以刪除根節(jié)點(diǎn)U1并且用Un代替，然后執(zhí)行情景（1）中的計(jì)算過(guò)程。

在這種情況下，協(xié)議可以刪除根節(jié)點(diǎn)Ul并且用Un代替，然后執(zhí)行情景（1）中的計(jì)算過(guò)程。

3 討論

本章重點(diǎn)討論新協(xié)議的安全性和計(jì)算性能。

3.1 安全性分析

安全性是保證協(xié)議能夠運(yùn)行在實(shí)際平臺(tái)中的最基本要求。新協(xié)議不僅具備已知密鑰安全和密鑰可認(rèn)證性，還具備前向安全性、密鑰可控制性，并可抵抗密鑰泄露偽裝攻擊。

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

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

（2）密鑰可認(rèn)證性

密鑰可認(rèn)證性是指協(xié)議應(yīng)該保證只有合法的參與者才能參與密鑰協(xié)商，沒(méi)有經(jīng)過(guò)認(rèn)證的參與者是不允許進(jìn)行密鑰協(xié)商的。在新協(xié)議中，每個(gè)參與者都要用自己的長(zhǎng)期私鑰對(duì)各自的消息進(jìn)行簽名，同時(shí)，當(dāng)參與者收到發(fā)來(lái)的消息時(shí)要進(jìn)行驗(yàn)證。因此，參與者的身份是可以得到保證的。

（3）前向安全性[14]

如果一個(gè)參與者的長(zhǎng)期私鑰被泄露，那么之前的會(huì)話密鑰的安全性不應(yīng)受到影響，這就是前向安全性的含義。在本協(xié)議中，長(zhǎng)期私鑰僅用于身份認(rèn)證，在每次會(huì)話中都要依賴于本次會(huì)話臨時(shí)產(chǎn)生的臨時(shí)私鑰來(lái)生成會(huì)話密鑰，從而保證了協(xié)議的前向安全性。

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

這一性質(zhì)用來(lái)保證敵手在獲得某一個(gè)參與者的長(zhǎng)期私鑰后去冒充其他參與者。由于在本協(xié)議中的長(zhǎng)期私鑰被用于身份認(rèn)證而非密鑰協(xié)商，因此本方法無(wú)需考慮該攻擊。換句話說(shuō)，新協(xié)議是滿足這一安全要求的。

（5）密鑰控制性[15]

密鑰控制性是指密鑰協(xié)商協(xié)議中的任何一方參與者都不可以事先決定或影響會(huì)話密鑰的值。在本文的協(xié)議中，密鑰是通過(guò)每個(gè)參與者利用各自的長(zhǎng)期和臨時(shí)公私鑰對(duì)通過(guò)雙線性對(duì)計(jì)算得到的，顯然不存在由一方參與者事先確定的情況。

表1 性能比較

3.2 性能分析

除了安全性，方案的性能也是影響方案能否用于實(shí)際的重要指標(biāo)。本節(jié)將用新方案與文獻(xiàn)[8-9]進(jìn)行對(duì)比。選擇這兩個(gè)方案作為比較對(duì)象是因?yàn)槲墨I(xiàn)[8-9]都是基于樹(shù)狀結(jié)構(gòu)的方案。記R(n)為協(xié)議的輪數(shù)，B(n)為消息傳輸?shù)臄?shù)量，P(n)為雙線性對(duì)運(yùn)算數(shù)量。如表1所示，顯然本文的方案有明顯的優(yōu)勢(shì)。

4 結(jié)論與下一步工作

本文提出了一種在三叉樹(shù)結(jié)構(gòu)下的群密鑰協(xié)商協(xié)議。新協(xié)議的每個(gè)參與者都可以通過(guò)基于身份的認(rèn)證結(jié)構(gòu)對(duì)收到的消息進(jìn)行認(rèn)證。為了解決群密鑰協(xié)商中成員變動(dòng)問(wèn)題，還提出了成員的加入和離開(kāi)協(xié)議。

但是對(duì)協(xié)議的安全性分析還停留在啟發(fā)式論證層面上，沒(méi)有給出嚴(yán)格的形式化證明，這也是今后要改進(jìn)的方向。

[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]鄧少鋒，鄧帆，李益發(fā).有效的強(qiáng)安全組群密鑰交換協(xié)議[J].計(jì)算機(jī)應(yīng)用，2010，30（7）：1805-1808.

[4]劉雪艷，張強(qiáng)，王彩芬.Ad Hoc網(wǎng)絡(luò)中基于身份的簇密鑰協(xié)商機(jī)制[J].計(jì)算機(jī)應(yīng)用，2012，32（8）：2258-2327.

[5]唐宏斌，劉心松.魯棒且高效的遠(yuǎn)程認(rèn)證及密鑰協(xié)商協(xié)議[J].計(jì)算機(jī)應(yīng)用，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

群密鑰協(xié)商是密鑰協(xié)商協(xié)議的一個(gè)重要研究分支。提出了一種在三叉樹(shù)結(jié)構(gòu)下基于身份的群認(rèn)證密鑰協(xié)商協(xié)議，充分考慮了成員加入和離開(kāi)時(shí)的子協(xié)議。還對(duì)方案的安全性和性能進(jìn)行了分析。結(jié)果表明，新方案在計(jì)算量減少的前提下實(shí)現(xiàn)了協(xié)議多方的安全密鑰協(xié)商。

密碼學(xué)；安全協(xié)議；群密鑰協(xié)商；雙線性對(duì)；三叉樹(shù)

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—），通訊作者，男，講師，主要研究領(lǐng)域?yàn)榫W(wǎng)絡(luò)安全、模式識(shí)別。E-mail：lxzhang76@163.com

2013-05-08

2013-09-02

1002-8331（2013）24-0083-05