基于ECC的三叉樹(shù)群組密鑰協(xié)商方案

曾繼強(qiáng) 史國(guó)振

1(西安電子科技大學(xué)通信工程學(xué)院 陜西 西安 710071)2(北京電子科技學(xué)院 北京 100070)

0 引 言

對(duì)于語(yǔ)音、視頻會(huì)議等群組會(huì)話中，在不安全的網(wǎng)絡(luò)上進(jìn)行通信，需要一種高效的密鑰協(xié)商協(xié)議來(lái)保證通信安全。在一個(gè)網(wǎng)絡(luò)中，n個(gè)成員在一個(gè)群組中進(jìn)行通信。這n個(gè)成員必須能夠以安全的方式在公共信道進(jìn)行通信，保證群組之外的用戶都不能監(jiān)聽(tīng)合法成員之間的對(duì)話。安全群組通信的一般旨在在小組成員之間建立一個(gè)保密通信的共享會(huì)話密鑰。盡管CCEGK[1]，TGDH[2]，STR[3]采用了樹(shù)形結(jié)構(gòu)實(shí)現(xiàn)了密鑰的協(xié)商，但是都是基于二叉樹(shù)和兩方的Diffie Hellman密鑰交換協(xié)議實(shí)現(xiàn)。文獻(xiàn)[10]在其提出的協(xié)議中引入三叉樹(shù)結(jié)構(gòu)，并使用GDH.2[11]來(lái)限制群組的數(shù)量為3k，其中k是整數(shù)。為了提高加密的效率，基于橢圓曲線密碼體制起到了非常重要的作用，因?yàn)樗痊F(xiàn)有的基于整數(shù)或整數(shù)分解的離散對(duì)數(shù)困難問(wèn)題的方法具有更短的密鑰大小，并且具有相同的安全級(jí)別。橢圓曲線公鑰密碼的使用是由Koblitz[12]在1987提出的，此后，對(duì)橢圓曲線密碼進(jìn)行了大量的工作。文獻(xiàn)[20]將橢圓曲線密碼算法加入到了群組密鑰協(xié)商協(xié)議中，其使用的是基于二叉樹(shù)的結(jié)構(gòu)。文獻(xiàn)[9]提出的群組密鑰協(xié)商協(xié)議使用了橢圓曲線算法，并采用的三叉樹(shù)的群組組織結(jié)構(gòu)，成員之間的協(xié)商過(guò)程主要利用臨時(shí)生成的隨機(jī)數(shù)作為私鑰并將私鑰與一個(gè)大素?cái)?shù)相乘作為公鑰進(jìn)行密鑰協(xié)商。本文在文獻(xiàn)[10]的基礎(chǔ)上提出一種基于橢圓曲線算法的群組密鑰協(xié)商協(xié)議，群組組織結(jié)構(gòu)與文獻(xiàn)[10]一樣采用了三叉樹(shù)結(jié)構(gòu)，該協(xié)議對(duì)于成員的數(shù)量沒(méi)有限制，解決了文獻(xiàn)[10]對(duì)成員數(shù)量限制為3k的缺點(diǎn)，三叉樹(shù)與二叉樹(shù)相比在結(jié)構(gòu)上更加簡(jiǎn)單，有利于減少密鑰樹(shù)的高度，使用三元樹(shù)代替二叉樹(shù)的優(yōu)勢(shì)在文獻(xiàn)[10]已經(jīng)證明。最后本文利用了雙方橢圓曲線DH協(xié)議和三方橢圓曲線DH協(xié)議進(jìn)行群組密鑰的協(xié)商，與文獻(xiàn)[9]使用公私鑰對(duì)進(jìn)行密鑰協(xié)商相比計(jì)算復(fù)雜度更低。由于采用了三方密鑰交換協(xié)議和三叉樹(shù)結(jié)構(gòu)，本方案具有密鑰長(zhǎng)度短計(jì)算量小等優(yōu)勢(shì)，在群組成員較大的情況下本文群組密鑰協(xié)商協(xié)議與現(xiàn)有方案相比具有更高的效率。

1 相關(guān)知識(shí)

文獻(xiàn)[14-17]提出了幾種群組密鑰協(xié)商方法。這些方法可以分為三類:集中式的、分散式的和分布式的。

在集中式的方法中，必須選定一個(gè)可信的實(shí)體(通常為群組服務(wù)器)進(jìn)行密鑰的生成和分發(fā)，在這種方法中最關(guān)鍵的是如何找到一個(gè)可信的實(shí)體，以及保證該實(shí)體始終可用，在安全性上一旦實(shí)體被攻擊，整個(gè)群組的密鑰將泄露，因此在可行性和安全性上沒(méi)有優(yōu)勢(shì)。

分散式的密鑰協(xié)商方法主要是將群組再進(jìn)行細(xì)分成一個(gè)個(gè)小的子群組，每個(gè)子群組選擇一個(gè)群組控制者來(lái)負(fù)責(zé)群組密鑰的生成和分發(fā)，該方法的主要問(wèn)題是當(dāng)群組用戶較多的時(shí)候，計(jì)算量將非常大，導(dǎo)致效率很低。

分布式的密鑰協(xié)商方法中，密鑰的協(xié)商是由群組成員共同協(xié)商完成的。Steiner等[11]擴(kuò)展了Diffie Hellman協(xié)議基于Diffie Hellman群組密鑰協(xié)商協(xié)議GDH(Group Diffie Hellman key agreement protocol)，這是一個(gè)可以應(yīng)用在多方的密鑰協(xié)商協(xié)議，該協(xié)議中具有n個(gè)用戶的群組需要進(jìn)行n輪的協(xié)商才能得到最后的群組密鑰。特別是在具有大量群組組成員環(huán)境中，協(xié)商的次數(shù)是至關(guān)重要的，因?yàn)樵诔蓡T進(jìn)行協(xié)商完成之前，其他成員無(wú)法進(jìn)行通信。

Kim等[17]提出了一種基于樹(shù)的組密鑰協(xié)議——TGDH。TGDH得到的組密鑰需要二叉樹(shù)中的所有組成員共同完成。與GDH相比，TGDH只需要常數(shù)輪便可完成密鑰的協(xié)商，在計(jì)算量上具有一定優(yōu)勢(shì)。文獻(xiàn)[10,21]基于TGDH提出了一些基于樹(shù)的群組密鑰協(xié)議,文獻(xiàn)[10]第一次介紹三元樹(shù)方法，并將GDH.2[11]作為在群成員中建立一個(gè)共享組密鑰的基本手段。這一方法大大降低了樹(shù)的高度，減少了計(jì)算和通信開(kāi)銷。但是這種方法的主要缺點(diǎn)是它只支持成員數(shù)量為3k的群組，k是任意整數(shù)。文獻(xiàn)[9]對(duì)文獻(xiàn)[8]進(jìn)行了改進(jìn)，雖然考慮了群組成員的變化，但是對(duì)于群組成員的離開(kāi)沒(méi)有進(jìn)行詳細(xì)的闡述。

2 預(yù)備知識(shí)

2.1 橢圓曲線密碼學(xué)

橢圓曲線的一般形式為:

y2=x3+ax+b

在密碼學(xué)中，橢圓曲線方程的變量和系數(shù)僅限于有限域上的元素。因此，對(duì)于上面的方程，x、y是群GF(p)的坐標(biāo)，a、b是p的整數(shù)模，滿足：4a3+27b2≠0(modp)，其中p是有限域上的一個(gè)模素?cái)?shù)。在群GF(p)上的橢圓曲線E由兩個(gè)方程所定義的點(diǎn)(x，y)和一個(gè)額外的點(diǎn)組成(通常為無(wú)窮遠(yuǎn)點(diǎn))。

通常在兩種有限域上定義橢圓曲線:一種是包含素?cái)?shù)p的有限域Fp上，一種是以2為特征值的有限域上。本文采用第一種定義方式來(lái)實(shí)現(xiàn)密鑰的協(xié)商。

在文獻(xiàn)[6,12,14]詳細(xì)描述了ECC的算法過(guò)程。ECC的安全性是基于橢圓曲線離散對(duì)數(shù)問(wèn)題ECDLP(Elliptic Curve Discrete Logarithm Problem)。基于橢圓曲線離散對(duì)數(shù)問(wèn)題陳述如下：給定素?cái)?shù)P和橢圓曲線E，對(duì)Q=kP,在已知P,Q的情況下求出小于P的正整數(shù)k，已知k和P計(jì)算Q比較容易，而由Q和P計(jì)算k則比較困難。

2.2 雙方橢圓曲線Diffie-Hellman協(xié)議

加入用戶A和用戶B進(jìn)行密鑰協(xié)商，雙方橢圓曲線DH密鑰協(xié)商協(xié)議步驟如下：

A生成密鑰K=a1Y。

B生成密鑰K=a2X。

2.3 三方橢圓曲線Diffie-Hellman協(xié)議

三方橢圓曲線Diffie-Hellman協(xié)議基于GDH[5]結(jié)合橢圓曲線實(shí)現(xiàn)了三方(A，B和C)的密鑰協(xié)商，實(shí)現(xiàn)如下：

A、B和C分別選擇自己的私鑰a1、a2、a3并保密。

A計(jì)算出X=a1P并發(fā)送給B。

B計(jì)算出Y1=a2P、Y2=a2X并構(gòu)造集合{X,Y1,Y2}發(fā)送給C。

C計(jì)算出K=a3Y2、Z1=a3Y1和Z2=a3X，把K當(dāng)作群組密鑰，并將剩余的Z1、Z2分別發(fā)送給A和B。

A和B在收到C發(fā)來(lái)的數(shù)據(jù)后計(jì)算出相同的群組密鑰，其中：

A：K=a1Z1

B：K=a2Z2

在三個(gè)成員完成密鑰協(xié)商后，橢圓曲線上有一個(gè)共同的點(diǎn)即：K=a3Y2=a1Z1=a2Z2=a1a2a3P。如果將此密鑰用作會(huì)話密鑰，則必須得到一個(gè)整數(shù)點(diǎn)。獲取該整數(shù)有兩種方法：可逆的和不可逆的[20]。如果需要將會(huì)話密鑰解碼為橢圓曲線中的一個(gè)點(diǎn)，則它是可逆的，否則就是不可逆的。可逆派生將產(chǎn)生一個(gè)會(huì)話密鑰，它使私鑰的長(zhǎng)度加倍。在不可逆轉(zhuǎn)的推導(dǎo)過(guò)程中，我們可以簡(jiǎn)單地使用x坐標(biāo)或?qū)坐標(biāo)進(jìn)行簡(jiǎn)單哈希作為會(huì)話密鑰。

3 本文方案

本文協(xié)議選擇k比特的素?cái)?shù)p和確定如下公共參數(shù)：{Fp,E/Fp,G,P}，其中：

E/Fp：有限域Fp上的橢圓曲線；

G:由E/Fp上點(diǎn)構(gòu)成的循環(huán)群；

P：循環(huán)群G的生成元。

本文協(xié)議主要描述了N個(gè)成員如何共享會(huì)話密鑰的初始化操作操作，并討論了群組的動(dòng)態(tài)變化操作，比如退出，加入等操作。

3.1 初始化

經(jīng)過(guò)第一輪后每一個(gè)分組擁有自己的私鑰(axi,ayi,azi)

每個(gè)分組中的一個(gè)成員作為下一輪的群組控制實(shí)體(GC)出現(xiàn)。本協(xié)議將選取第一個(gè)成員為組控制實(shí)體負(fù)責(zé)表示子群進(jìn)行下一輪的協(xié)商。將每個(gè)子群看作是由每個(gè)GC控制的一個(gè)新節(jié)點(diǎn)。

(4) 如果最后一輪剩下的節(jié)點(diǎn)不足三個(gè)，無(wú)法形成三叉樹(shù)，則使用2.2中的雙方橢圓曲線Diffie-Hellman協(xié)議來(lái)生成會(huì)話密鑰。

下面我們通過(guò)一個(gè)例子來(lái)實(shí)現(xiàn)本文提出方案。假設(shè)一個(gè)群組中由12個(gè)成員組成，如圖1所示。

圖1 12個(gè)成員的群組三叉樹(shù)結(jié)構(gòu)圖

葉子節(jié)點(diǎn)M1,M2,M3,…,M12表示群組中的12個(gè)成員。在第一輪計(jì)算中，12個(gè)成員被分為四個(gè)子組，通過(guò)三方橢圓曲線Diffie-Hellman密鑰交換協(xié)議形成會(huì)話密鑰，并由G1、G2、G3、G4作為子組代表繼續(xù)下一輪的計(jì)算；在第二輪計(jì)算中，由于有四個(gè)節(jié)點(diǎn)，因此在第二輪中只有G1、G2、G3參與協(xié)商，G4將在下一輪進(jìn)行處理，在第二輪的協(xié)商中，按照第一輪的方法G1、G2、G3生成會(huì)話密鑰，并由G5作為代表進(jìn)行下一輪的協(xié)商；在第三輪的協(xié)商中，只剩下G5、G4兩個(gè)節(jié)點(diǎn)，此時(shí)兩個(gè)節(jié)點(diǎn)將通過(guò)雙方橢圓曲線Diffie-Hellman密鑰交換協(xié)議形成會(huì)話密鑰，并由G作為根節(jié)點(diǎn)。最后G5、G4計(jì)算出的會(huì)話密鑰為群組所有成員的共享密鑰。在此過(guò)程中，群組中的通信次數(shù)和計(jì)算量最多情況如表1所示。

表1 通信和計(jì)算量

3.2 成員加入

高效的加入和離開(kāi)處理方法對(duì)于動(dòng)態(tài)組密鑰協(xié)議非常重要，因?yàn)槿魏纬蓡T都可以隨時(shí)離開(kāi)和加入這個(gè)組。在本文中加入群組分為兩種：一種是單個(gè)成員的加入，另外一種是多個(gè)成員同時(shí)加入群組。

3.2.1 單個(gè)成員加入群組

3.2.2 多個(gè)成員加入

假設(shè)有m個(gè)成員需要加入群組密鑰為K的N個(gè)成員的群組中。操作步驟如下：

(1) 將要加入群組的m的成員通過(guò)3.1節(jié)的方法形成一個(gè)獨(dú)立的群組，并協(xié)商出群組密鑰假設(shè)為Knew。

(2) 將新的群組合并到要加入的群組中。

(3) 新的群組將群組密鑰廣播給要加入的群組的所有成員并生成新的群組密鑰x1x2P，其中x1、x2表示兩個(gè)群組合并之前各自的群組密鑰。多個(gè)成員的加入需要進(jìn)行消息廣播次數(shù)為：

點(diǎn)乘的次數(shù)為：

式中：h,h′表示n個(gè)成員的群組和m個(gè)成員群組的三叉樹(shù)的深度。在本文中，對(duì)點(diǎn)乘運(yùn)算量是在最壞情況下的討論，在實(shí)際的運(yùn)算中點(diǎn)乘運(yùn)算量比最壞情況下的小得多。

3.3 成員離開(kāi)

如果是單個(gè)成員離開(kāi)，我們可以通過(guò)多次的密鑰協(xié)商重新生成群組密鑰；如果是多個(gè)成員同時(shí)離開(kāi)，此時(shí)的協(xié)商次數(shù)和計(jì)算量比較復(fù)雜，需將剩下的成員按照3.1節(jié)所示的方法重新初始化三叉樹(shù)。

3.3.1 單個(gè)成員退出群組

單個(gè)成員退出群組時(shí)，必須從該成員到三叉樹(shù)的根節(jié)點(diǎn)之間進(jìn)行密鑰更新。如果離開(kāi)成員是子樹(shù)的控制者GC(group controller)，則選擇該子樹(shù)中其他成員作為組控制者，而不需要改變其他子樹(shù)的結(jié)構(gòu)。假設(shè)具有n個(gè)成員的群組中成員m要退出群組，如圖2所示。

圖2 成員m4離開(kāi)過(guò)程

成員m4離開(kāi)群組后，子樹(shù)中剩下成員m5、m6，m5、m6通過(guò)雙方Diffie-Hellman密鑰交換協(xié)議重新協(xié)商群組密鑰為k3，并選取m4為該子樹(shù)的群組控制者，將k3P廣播給子樹(shù)G1，G1和G3通過(guò)雙方Diffie-Hellman密鑰交換協(xié)議得出新的群組密鑰kG′=k1k3P，其中k1為子樹(shù)G1原來(lái)的子組密鑰，該密鑰不需要重新協(xié)商。

成員離開(kāi)所需要的計(jì)算量在最壞的情況下是成員處于三叉樹(shù)的最深節(jié)點(diǎn)，密鑰重新協(xié)商所需次數(shù)為n+3h-2。

3.3.2 多個(gè)成員離開(kāi)群組

當(dāng)有多個(gè)成員同時(shí)退出群組時(shí)，考慮到密鑰的協(xié)商以及計(jì)算復(fù)雜度，本文對(duì)于多個(gè)成員離開(kāi)采用的處理方法是將剩下的成員按照3.1節(jié)方法進(jìn)行三叉樹(shù)重新初始化。假設(shè)有n個(gè)成員的群組中有m個(gè)成員退出，則消息的廣播次數(shù)為：

點(diǎn)乘次數(shù)為：

4 方案比較

本節(jié)將所提出的群組密鑰協(xié)商管理操作與現(xiàn)有的基于二叉樹(shù)的群組密鑰協(xié)商技術(shù)進(jìn)行比較。比較結(jié)果如表2所示，其中表中使用的參數(shù)如下：

n：表示一個(gè)群組中的成員數(shù)量；

m：表示要加入或者離開(kāi)群組的用戶數(shù)量。

表2 性能分析

文獻(xiàn)[20-21]對(duì)于多個(gè)用戶同時(shí)加入的情況沒(méi)有進(jìn)行分析，本文所提出的方案還考慮了多個(gè)成員同時(shí)加入的情況。由表2可得本文所提出的協(xié)議在群組密鑰初始化階段密鑰協(xié)商輪數(shù)、多個(gè)用戶離開(kāi)、初始化階段的消息通信量以及多個(gè)用戶離開(kāi)情況下的消息通信量，與文獻(xiàn)[20-21]相比，在群組用戶數(shù)量較大的情況下有一定的優(yōu)勢(shì)，在效率上則優(yōu)勢(shì)明顯。

5 安全性分析

(1) 密鑰泄露安全性 密鑰泄露是指當(dāng)某個(gè)成員的密鑰被攻擊竊取后，攻擊者只能冒充該成員進(jìn)行群組會(huì)話，而其他成員的密鑰依然是安全的。例如有兩個(gè)成員m1、m2的子樹(shù)，其中m1的公鑰為X=a1P，m2的公鑰為Y=a2P，則會(huì)話密鑰為K=a1a2P，盡管攻擊者獲取了K、a1和P的值，但是仍然無(wú)法獲取a2的值。

(2) 前向安全性和后向安全性 前向安全性是指新加入成員無(wú)法獲取加入群組之前的群組密鑰，因?yàn)槊荑€協(xié)商是基于離散度數(shù)問(wèn)題，給定Q=kP，給定Q和P計(jì)算出k是困難的，而k是由子組組密鑰點(diǎn)乘得到的，因此無(wú)法通過(guò)子組自己的群組密鑰計(jì)算出群組密鑰。后向安全性是指離開(kāi)群組的成員無(wú)法再參與群組密鑰協(xié)商，也不能得到后續(xù)的群組密鑰，因?yàn)殡x開(kāi)的成員從其所在的位置到根節(jié)點(diǎn)將重新進(jìn)行密鑰協(xié)商，因此后續(xù)的會(huì)話將使用重新協(xié)商的會(huì)話密鑰進(jìn)行通信，能保證后向安全性。

(3) 密鑰控制 密鑰控制是指群中任何合法的成員都不能決定或者影響群組密鑰的值。在本文的方案中群組會(huì)話密鑰是由群組所有成員共同協(xié)商完成，因此沒(méi)有任何一個(gè)成員能控制或者提前決定會(huì)話密鑰。

6 結(jié) 語(yǔ)

本文提出了一種高效的群組密鑰協(xié)商協(xié)議。在本方案中使用三叉樹(shù)來(lái)對(duì)群組成員進(jìn)行分組來(lái)代替二叉樹(shù)。群組密鑰的協(xié)商采用基于ECC的三方Diffie-Hellman算法，本文主要描述了群組密鑰的生成過(guò)程，并針對(duì)群組的動(dòng)態(tài)變化對(duì)相應(yīng)的密鑰進(jìn)行更新操作。在群組動(dòng)態(tài)變化時(shí)，未變動(dòng)的成員不需要再重新生成新的隨機(jī)數(shù)，減少了群組變動(dòng)的計(jì)算量。當(dāng)某個(gè)用戶收到攻擊時(shí)，攻擊者只能冒充該成員進(jìn)行通信而其他成員不會(huì)收到影響，相比使用群組密鑰分發(fā)方案更具有可靠性。最后將群組的各種操作的復(fù)雜度與現(xiàn)有的技術(shù)進(jìn)行了比較，表明本方案比現(xiàn)有協(xié)議具有優(yōu)勢(shì)。本文的不足之處在于尚未對(duì)成員進(jìn)行身份認(rèn)證，在接下來(lái)的工作中，將繼續(xù)研究對(duì)成員的身份認(rèn)證以及成員之間的角色劃分。