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

曾繼強 史國振

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

0 引 言

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

1 相關(guān)知識

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

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

分散式的密鑰協(xié)商方法主要是將群組再進行細分成一個個小的子群組，每個子群組選擇一個群組控制者來負責群組密鑰的生成和分發(fā)，該方法的主要問題是當群組用戶較多的時候，計算量將非常大，導致效率很低。

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

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

2 預備知識

2.1 橢圓曲線密碼學

橢圓曲線的一般形式為:

y2=x3+ax+b

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

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

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

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

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

A生成密鑰K=a1Y。

B生成密鑰K=a2X。

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

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

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

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

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

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

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

A：K=a1Z1

B：K=a2Z2

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

3 本文方案

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

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

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

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

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

3.1 初始化

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

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

(4) 如果最后一輪剩下的節(jié)點不足三個，無法形成三叉樹，則使用2.2中的雙方橢圓曲線Diffie-Hellman協(xié)議來生成會話密鑰。

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

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

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

表1 通信和計算量

3.2 成員加入

高效的加入和離開處理方法對于動態(tài)組密鑰協(xié)議非常重要，因為任何成員都可以隨時離開和加入這個組。在本文中加入群組分為兩種：一種是單個成員的加入，另外一種是多個成員同時加入群組。

3.2.1 單個成員加入群組

3.2.2 多個成員加入

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

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

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

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

點乘的次數(shù)為：

式中：h,h′表示n個成員的群組和m個成員群組的三叉樹的深度。在本文中，對點乘運算量是在最壞情況下的討論，在實際的運算中點乘運算量比最壞情況下的小得多。

3.3 成員離開

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

3.3.1 單個成員退出群組

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

圖2 成員m4離開過程

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

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

3.3.2 多個成員離開群組

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

點乘次數(shù)為：

4 方案比較

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

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

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

表2 性能分析

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

5 安全性分析

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

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

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

6 結(jié) 語

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