楊 帆

（安徽商貿(mào)職業(yè)技術(shù)學(xué)院電子信息工程系，安徽蕪湖241002）

超球形分布式多播密鑰更新方法研究

楊 帆

（安徽商貿(mào)職業(yè)技術(shù)學(xué)院電子信息工程系，安徽蕪湖241002）

提出了一種超球形的分布式安全多播密鑰管理方案。該方案充分利用了分布式多播中成員之間既獨(dú)立又協(xié)同的特點(diǎn)，解決了安全多播密鑰的更新問(wèn)題，更新效率較高，有效地降低了組密鑰更新的通信開(kāi)銷(xiāo)，且不增加計(jì)算開(kāi)銷(xiāo)和存儲(chǔ)開(kāi)銷(xiāo)，并能很好地保證更新時(shí)的前向安全性和后向安全性。

分布式多播；安全多播；密鑰更新；超球形

目前，分布式多播密鑰管理方案或多或少都存在一些問(wèn)題，如：在Clique［1］方案中，由于組密鑰是基于Diffie-Hellman［2］算法產(chǎn)生的，密鑰傳輸是線性的，故這種方案存在密鑰存儲(chǔ)量、計(jì)算量和通信量的數(shù)量級(jí)偏高的問(wèn)題；基于樹(shù)型的TGDH［3］密鑰管理方案雖然較Clique方案在上述幾個(gè)方面問(wèn)題有所改進(jìn)，但是它存在樹(shù)狀結(jié)構(gòu)不平衡的缺點(diǎn)，當(dāng)節(jié)點(diǎn)分布極度不平衡時(shí)，這種方案會(huì)變成線性的形式。

對(duì)集中式的密鑰管理方案，文獻(xiàn)［4］提出了一種超球形的密鑰組織方式，文獻(xiàn)［5］提出了一種M維幾何球形組播密鑰批量更新方案，它們的實(shí)質(zhì)都是在集中式密鑰管理的基礎(chǔ)上引入了超幾何體。在分布式多播中，由于組密鑰是由成員共同參與產(chǎn)生的，協(xié)同性和獨(dú)立性更加突出，更加適合利用超球模型來(lái)進(jìn)行密鑰的組織和管理，因此筆者將超球模型引入到分布式多播中，提出一種基于超球模型的分布式安全多播密鑰管理方案。

1 密鑰管理機(jī)制

先假設(shè)需要進(jìn)行多播通信的節(jié)點(diǎn)有n個(gè)，將節(jié)點(diǎn)按照一定的規(guī)則進(jìn)行分組，每組m個(gè)，根據(jù)每組節(jié)點(diǎn)的坐標(biāo)可確定M維超球模型的球心及其半徑，該球心即為這m個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)，再將這些父節(jié)點(diǎn)按m個(gè)一組進(jìn)行劃分，再次產(chǎn)生父節(jié)點(diǎn)，按此規(guī)則繼續(xù)劃分，直至產(chǎn)生根節(jié)點(diǎn)為止，這個(gè)根節(jié)點(diǎn)的坐標(biāo)就是超球模型的超級(jí)球心的坐標(biāo)，最后計(jì)算出的半徑就是n個(gè)成員的組密鑰?？梢钥闯?，任意一個(gè)節(jié)點(diǎn)的變化，都會(huì)影響其所在球的球心及與其相關(guān)聯(lián)的所有球的球心坐標(biāo)，而其他球的球心不受影響。為了保證分布式多播的前向和后向安全性，組成員發(fā)生變化時(shí)需要進(jìn)行組密鑰的更新。完成一次組密鑰更新的過(guò)程是：通過(guò)某些組成員對(duì)組密鑰加密后，再將密鑰發(fā)送給多播組中剩余的成員，這些成員用解密密鑰就可計(jì)算得到新的組密鑰。

1.1 組密鑰的生成機(jī)制

組成員相互協(xié)商可以產(chǎn)生一個(gè)共同的密鑰，也就是說(shuō)，不同的分布式多播組能夠安全地協(xié)商出一個(gè)共同的加密密鑰。設(shè)節(jié)點(diǎn)被分成4個(gè)多播組L、R、N、S，L的發(fā)起人是ML，密鑰加密密鑰是KL，R的發(fā)起人是MR，密鑰加密密鑰是KR，N的發(fā)起人是MN，密鑰加密密鑰是KN，S的發(fā)起人是MS，密鑰加密密鑰是KS。這里，對(duì)任意以非葉子節(jié)點(diǎn)（包括最頂節(jié)點(diǎn)）為根節(jié)點(diǎn)的子樹(shù)，可選擇其中一個(gè)葉子節(jié)點(diǎn)作為該子樹(shù)的發(fā)起人。這4個(gè)小組通過(guò)如下步驟產(chǎn)生一個(gè)共同的組密鑰。

1）ML、MR、MN、MS根據(jù)自身的坐標(biāo)，計(jì)算出共同的球心，然后計(jì)算出這個(gè)球的半徑，即組密鑰K。

2）ML通過(guò)KL加密K并把它多播給L中的其他成員，MR通過(guò)KR加密K并把它多播給R中的其他成員，MN通過(guò)KN加密K并把它多播給N中的其他成員，MS通過(guò)KS加密K并把它多播給S中的其他成員，直到多播組L、R、N、S中所有成員都安全地接收到新的組密鑰K。

例如：分布式多播組有n=4m個(gè)成員，先將其分成4個(gè)子組，每個(gè)子組包含4m-1個(gè)成員，再將子組繼續(xù)以4個(gè)成員為一組進(jìn)行劃分，直到最后產(chǎn)生若干個(gè)小組，每

個(gè)小組都有4個(gè)成員；然后通過(guò)如下步驟生成組密鑰。

1）第一組的4個(gè)成員M1、M2、M3和M4計(jì)算出所在球的球心O1，然后計(jì)算出半徑R1。

2）第二組M5、M6、M7和M8計(jì)算出所在球的球心O2，然后計(jì)算出半徑R2。

3）以此類(lèi)推，直到最后一組計(jì)算出它們所在球的球心On和半徑Rn。

4）將1）和2）中得到的球心O1、O2、…、On按4個(gè)一組再次進(jìn)行劃分，然后重復(fù)1）和2），直到得到根球心O和根半徑R。這個(gè)根半徑就是分布式多播的組密鑰，如圖1所示。

圖1 n個(gè)成員協(xié)商組密鑰

1.2 組成員的加入和離開(kāi)

當(dāng)有成員加入或離開(kāi)多播組時(shí)，為了保證分布式多播的安全性，組密鑰必須進(jìn)行更新。本文考慮具有16個(gè)成員的分布式多播組的組密鑰更新。

（1）假設(shè)M4請(qǐng)求加入多播組，由用戶M1所在的子組接納，如圖2所示，那么從M1所在球的球心到根球心之間的所有相關(guān)的球心和半徑都會(huì)發(fā)生變化。組密鑰更新的具體步驟如下：

1）M1與M2、M3、M4計(jì)算出新的球心和半徑，這個(gè)新的半徑成為該組新的子組密鑰，記為；

2）M1與M5、M9、M13根據(jù)各組的球心計(jì)算出新的父球心和半徑，這個(gè)新的半徑即為新的組密鑰，記為；

以下表達(dá)式說(shuō)明了組密鑰的更新過(guò)程，如第1行是指以M1用加密發(fā)送給｛M2，M3，M4｝。

M16｝收到更新報(bào)文后，用各自所在子組的子組密鑰解密即可得到。

圖2 成員M4加入時(shí)需要更新的密鑰

（2）假設(shè)M1離開(kāi)多播組，為了保證后向安全性，M1知道的密鑰都需要更新，如圖3所示。

圖3 成員離開(kāi)時(shí)需要更新的密鑰

密鑰更新的步驟如下：

1）M2取代M1成為M3和M4的發(fā)起人；

2）M2與M3、M4共同決定一個(gè)球，計(jì)算出該球的球心和半徑，這個(gè)半徑即為新的子組密鑰；

3）M2與M5、M9、M13根據(jù)各組的球心重新計(jì)算父球心和半徑，以新的半徑作為新的組密鑰，記為；

圖4 成員M1離開(kāi)后的超球結(jié)構(gòu)

2 性能分析

2.1 安全性分析

在本方案中，當(dāng)有成員加入多播組時(shí)，必然會(huì)引起從該成員所在的葉子節(jié)點(diǎn)到超球的根球心這條路徑上的所有節(jié)點(diǎn)的坐標(biāo)的變化，那么這條路徑上的所有相關(guān)球的半徑也會(huì)發(fā)生變化，即這條路徑上所有的密鑰全部更新。新的組密鑰由每組的發(fā)起成員用子組密鑰加密后，安全地傳遞給多播組中的其他成員，使新加入的組成員無(wú)法獲取原來(lái)的組密鑰，也就無(wú)法破解在其加入之前的多播消息，保證了多播的后向安全性。

同樣，當(dāng)有成員離開(kāi)多播組時(shí)，從該成員所在的子組到超球的根球心這條路徑上的所有節(jié)點(diǎn)的坐標(biāo)也都會(huì)發(fā)生變化，即將產(chǎn)生新的子組密鑰和多播組密鑰。每組的發(fā)起成員將組密鑰安全地發(fā)送給多播組內(nèi)的剩余成員，而離開(kāi)的成員是無(wú)法計(jì)算出新的子組密鑰和新的組密鑰的，即保證了多播的前向安全性。

2.2 復(fù)雜度分析

從以上分析可以看出，在n個(gè)成員組成的超球模型分布式多播中，只需要進(jìn)行l(wèi)og4n輪迭代運(yùn)算就可以產(chǎn)生組密鑰。

從密鑰存儲(chǔ)的角度來(lái)分析，每一組中除了發(fā)起成員以外，其他成員只參與了該子組的密鑰協(xié)商運(yùn)算，剩下的迭代運(yùn)算都只是由每一組的發(fā)起成員來(lái)完成，組密鑰產(chǎn)生以后，也由發(fā)起成員負(fù)責(zé)將其轉(zhuǎn)發(fā)給各組的其他成員。因此，在基于超球模型的分布式多播中，每個(gè)成員只需要保存兩個(gè)密鑰即可。

當(dāng)有成員加入時(shí)，新加入的成員所在的子組需重新計(jì)算子組密鑰，并和其他的子組進(jìn)行l(wèi)og4n輪迭代運(yùn)算來(lái)產(chǎn)生新的組密鑰。新的組密鑰由各組的發(fā)起成員加密后發(fā)送給各組的成員，共需要進(jìn)行l(wèi)og4n次加密運(yùn)算，故計(jì)算量為O（log4n）。由于每一組中除發(fā)起成員以外，都需要通過(guò)發(fā)送更新報(bào)文進(jìn)行密鑰更新，對(duì)每組4個(gè)成員的多播組來(lái)說(shuō)，通信開(kāi)銷(xiāo)為3log4n。

成員離開(kāi)時(shí)情形與成員加入時(shí)相同，發(fā)起成員需要進(jìn)行l(wèi)og4n輪迭代運(yùn)算產(chǎn)生新的組密鑰，之后進(jìn)行l(wèi)og4n次加密運(yùn)算后發(fā)送給其他多播成員，通信開(kāi)銷(xiāo)為3log4n。

綜上所述，在多播組成員數(shù)為n的情況下，密鑰存儲(chǔ)的復(fù)雜度為O（1），計(jì)算量和通信量為O（log4n），該方案具有良好的可縮放性。

3 結(jié)束語(yǔ)

基于超球模型的分布式密鑰管理方案是將超球模型引入到了分布式多播中，該方案具有良好的擴(kuò)展性和安全性，這種密鑰組織方式可以有效降低密鑰更新時(shí)的開(kāi)銷(xiāo)，提高分布式多播密鑰更新的效率。

［1］STEINER M，WAIDNER M，TSUDIK G.CLIQUES：A New Approach to Group Key Agreement［C］//Proceedings of the The 18thInternational Conference on Distributed Computing Systems，IEEE Computer Society，Baltimore，Maryland，May 10-13，1997，IEEE，1998：380.

［2］DIFFIEW，HELLMANME.NewDirectionsin Cryptography［J］.IEEE Trans onInformation Theory，1976，22（6）：644-654.

［3］KIM Y，PERRIG A，TSUDIK G.Tree-based Group Key Agreement［J］.ACM TransInf Syst Secur，2004，7（1）：60-96.

［4］陳少軍，馮年榮，許勇，等.基于超球形的多播密鑰更新方法［J］.安徽工程科技學(xué)院學(xué)報(bào)（自然科學(xué)版），2007（3）：48-50.

［5］謝海濤，王玉明，楊宗凱，等.一種M維幾何球形組播密鑰批量更新方案［J］.小型微型計(jì)算機(jī)系統(tǒng)，2010（2）：254-258.

【責(zé)任編輯 梅欣麗】

Research on Distributed Multicast Rekeying Schema Based on Super Geometry Sphere

YANG Fan
（Department of ElectronicInformation and Engineering，Anhui Business College，Wuhu 241002，China）

A distributed multicast rekeying schema based on super geometry sphere was proposed.The schema took full advantage of both independent and collaborative features among members of distributed multicast to solve the security problem of multicast rekeying；in the same time，the higher efficiency updating of the program effectively reduced communication overhead of the group rekeying without increasing the computational and storage overhead and it could ensure the forward and backward security while updating.

distributed multicast；multicast security；rekeying；super geometry sphere

TP393

A

2095-7726（2015）12-0040-04

2015-07-01

楊帆（1989-），男，安徽懷寧人，助教，碩士，研究方向：網(wǎng)絡(luò)安全與移動(dòng)互聯(lián)。