基于Merkle身份樹的動態對等群組密鑰協商

摘 要:針對設計高效的分布式密鑰協商方案是動態對等群組組播通信的難點，提出了一個新的基于Merkle身份樹的密鑰協商方案，并具體地分析了子組之間的通信過程，以及組成員動態變化時密鑰的更新過程。結果表明該方案在降低計算和通信代價方面取得了較好的效果。

關鍵詞:動態對等群組; 密鑰協商; 身份樹; 雙線性對

中圖分類號:TP393

文獻標志碼:A

文章編號:1001-3695(2010)02-0682-03

doi:10.3969/j.issn.1001-3695.2010.02.077

Key agreement scheme for dynamic peer groups based on Merkle identity tree

CHEN Li-qing

(School of Computer Engineering， Huaiyin Institute of Technology， Huai’an Jiangsu 223003， China)

Abstract:Designing efficient distributive key agreement scheme was a difficult problem in multicast communication of dyna-mic peer groups. This paper proposed a new key agreement scheme for multicast groups based on Merkle identity tree . Then analyzed the procedures of secret communications between subgroups and updating of group keys with the dynamic change of group members in detail. The analysis shows that the new scheme is efficient in computation and communication.

Key words:dynamic peer groups; key agreement; identity tree; bilinear pairing

組播提供了一種發送者可以同時發送信息到多個接收者的高效通信機制，其通過在路由器上合并重復信息的傳輸，從而有效地節約了帶寬，降低了服務器的負擔。組播通信的方式大致可分為三類:a)一對多，一個發送者和多個接收者，如視頻點播;b)少對多，少數發送者和多個接收者，如GPS;c)多對多，所有成員都是對等體，可以動態地成為發送者或接收者，如分布式系統、視頻電話會議、網絡游戲等。這種方式的組播組又稱為動態對等群組(dynamic peer groups)。

安全組播的一個主要難點是如何確保只有合法的組注冊用戶才能接收到組播通信數據。其中，動態對等群組(DPG)由于顯著的對稱性和動態性，又無疑是最具挑戰性的課題。近年來將密碼學新技術，如基于身份的密碼系統應用到 DPG 的分布式密鑰協商中，已成為新的研究熱點[1~5]。文獻[6]中提出的方案很好地解決了基于身份的密碼系統下單個 KGC 容易成為整個組播體系性能瓶頸的問題，但是其只適用于發送者在組播組外的應用。在其方案中，KGCs 不僅是組成員注冊和密鑰分發的中心，還承擔了外部發送者與組播組之間的消息轉發任務，即 KGCs 將消息分別用各個子組協商出的密鑰加密后轉發給各個子組。而對于那些組內部分或所有成員之間需要相互通信的 DPG 應用，如視頻電話會議，若采用這個方案則存在著 KGCs 計算代價較高、通信延遲等不足。為此，本文在其基礎上提出了一個新的基于 Merkle 身份樹的 DPG 密鑰協商方案，較好地解決了不經過 KGCs 而實現組內成員保密通信的問題。本方案所適用的 DPG 組播體系結構如圖 1 所示。

Merkle 樹是一種特殊的二叉樹，其在每個節點中存儲一個值:對于每一個葉子節點是一條指令加上該指令的hash 值構成;每個父節點下面的所有子節點的hash值組合到一起，再進行hash運算就得到它們的父節點。這個過程一直進行下去，直至得到樹的根節點。Merkle 樹的主要優點是僅需通過對樹根節點的一次簽名運算就可以對樹上所有的葉子節點獨立地提供完整性認證。本文為應用基于身份的密碼系統進行 DPG 組會話密鑰的協商，提出了 Merkle 身份樹的概念。在 Merkle 身份樹中，葉子節點存儲 DPG 組成員身份信息的hash值。

1 預備知識

1.1 雙線性映射

設G1、G2都是階為素數q的循環群，G1的運算記為加法，G2的運算記為乘法。一個雙線性映射(bilinear maps)e^:G1×G1→G2是滿足如下三條性質的映射:

a)雙線性。對于所有的P，Q∈G1，以及a，b∈Zq，e^(aP，bQ)=e^(P，Q)ab。

b)非退化性。若P是G1的一個生成元，e^(P，P)≠1G2。

c)可計算性。存在一個有效的算法來計算e^(P，Q)。

1.2 計算復雜性假設

定義1 離散對數問題(DLP)。給定加法循環群G1，G1的一個生成元P及任意Q∈G1，求最小非負整數x，使得Q=xP。

定義2 計算Diffie-Hellman問題(CDHP)給定加法循環群G1，G1的一個生成元P和隨機的aP，bP∈G1(a，b未知)，計算abP。

定義3 雙線性逆Diffie-Hellman問題(BIDHP)G1，G2，P和e^如前面所定義，給定(P，aP，bP)。其中a，b∈Zq，計算e^(P，P)a-1b。

復雜性假設:在G1、G2中的DLP，CDHP和BIDHP都是困難問題，即不存在一個多項式時間算法能以不可忽略的概率解決其中任何一個問題。

2 基于Merkle身份樹的DPG密鑰協商方案

2.1 變量標記說明及系統初始化

本方案涉及到如下一些變量標記:

SGID為子組的身份標志;QID為子組的身份標志的hash值;PpubID為子組的公鑰參數;DID為子組的私鑰;h為子組Merkle身份樹的最大高度;Ui為子組中的第i個成員，i∈{1，2，…，t};IDi為Ui的身份標志;Nji為子組Merkle身份樹中第i層的第j個節點;Qji為節點Nji身份標志的hash值;Pji為節點Nji的私鑰;BKji為節點Nji的盲密鑰;Kji為節點Nji的生成密鑰;KGCi為第i個KGC;si為KGCi的主密鑰;n為組播消息的bit長度。

給定系統安全參數1k(k=|q|)，KGCs運行雙線性Diffie-Hellman參數生成算法Ig，生成如前定義的G1、G2，以及一個雙線性映射e∧:G1×G1→G2，G1是階為素數q的循環加法群，G2是與G1相關的階同為q的乘法群，選擇G1的生成元為P。定義一組hash函數:H1:{0，1}→Zq，H2:Zq×Zq→Zq，H3:G2→Zq，H4:{0，1}→G1，H5:G2→{0，1}n，H6:{0，1}n→Zq，H7:{0，1}n→{0，1}n。KGCs發布系統的公共參數為params={G1，G2，e∧，P，H1，H2，H3，H4，H5，H6，H7，n}，組播消息明文空間為M={0，1}n ，密文空間為C=G1×{0，1}n。

2.2 DPG組播成員注冊及子組密鑰協商過程

希望加入DPG組播組的用戶向KGCs注冊成為組的合法成員。KGCs按照組成員所在的地理位置將整個大的DPG組播組劃分為多個子組，為保證一定的通信效率，各個子組的成員數應控制在2h-1(h為實際組播應用中子組Merkle身份樹的最大高度)以內。對于任一個子組，KGCs采用一棵邏輯意義上的平衡二叉樹結構將所有組成員安排在葉子節點。所有的子組Merkle身份樹信息都作為公共信息發布。由圖2可見一棵子組Merkle身份樹的結構。Merkle身份樹中節點采用由上至下、從左向右的標號順序，這種方式更加合理，在子組成員發生變化時，可以使需要更改標記的節點數最少。

Merkle身份樹中的每一個節點分別關聯三個密鑰，即私鑰、盲密鑰和生成密鑰。組成員在注冊時，KGCs將從根節點到此組成員所在葉子節點這條路徑上所有節點(不包括根節點)的私鑰通過秘密信道發送給組成員。此秘密信道是在組成員注冊時與KGCs建立的。葉子節點的生成密鑰也在注冊時各自發送給組成員。所有節點的盲密鑰作為公共信息發布。而中間節點的生成密鑰則要由各個組成員借助已有密鑰由下至上逐層協商得到，最終協商出的根節點的生成密鑰結合子組的身份信息即作為子組成員共享的私鑰，以用于解密接收到的DPG組播消息。

對于葉子節點，Qji=H1(IDji);對于中間節點，Qji=H2(Q2j-1i+1，Q2ji+1)。假定當前處于工作狀態的是KGCv，則其為節點Nji生成私鑰和盲密鑰的過程為，KGCv首先計算Pji=(Qji+sv)-1P和TKji=(Qji+sv)P。其中sv為KGCv的主密鑰，Pji和TKji分別作為Nji的私鑰和臨時密鑰，且臨時密鑰僅為KGCs所掌握。KGCv為組成員隨機選擇一個生成密鑰Kji∈Zq，并連同從根節點到此組成員所在葉子節點這條路徑上所有節點(不包括根節點)的私鑰一起通過秘密信道安全單播發送給注冊組成員。定義K2j-1i+1TK2ji+1和K2ji+1TK2j-1i+1為節點Nji的一對盲化因子，則節點N2j-1i+1和N2ji+1的盲密鑰分別為BK2j-1i+1=K2j-1i+1TK2ji+1，BK2ji+1=K2ji+1TK2j-1i+1。所有盲密鑰作為公共信息發布。利用已知的私鑰和盲密鑰，中間節點Nji的左孩子節點N2j-1i+1和右孩子節點N2ji+1可分別計算其父節點Nji的生成密鑰Kji。

對于左孩子節點N2j-1i+1:

Kji=H3(e^(P2j-1i+1，BK2ji+1)K2j-1i+1)=

H3(e^((Q2j-1i+1+sv)-1P，K2ji+1(Q2j-1i+1+sv)P)K2j-1i+1)=

H3(e^(P，P)K2ji+1K2j-1i+1)

(1)

對于右孩子節點N2ji+1:

Kji=H3(e^(P2ji+1，BK2j-1i+1)K2ji+1)=

H3(e^((Q2ji+1+sw)-1P，K2j-1i+1(Q2ji++sw)P)K2ji+1)=

H3(e^(P，P)K2ji+1K2j-1i+1)

(2)

如此逐層向上，最終每個組成員都可計算出根節點的生成密鑰K11。注意式(1)和(2)中，sv區別于sw表明了一組KGCs的作用所在，即每個組成員都隨機地與任意一個KGC聯系，注冊并獲得相應的密鑰，卻不影響子組成員最后可以協商出同一個密鑰，從而實現了分布式管理，大大減輕了單個KGC的工作負擔，提高了DPG組播系統的可擴展性。

仍以圖2為例，U2從KGCs處獲得了K23以及P23、P12，所有節點的盲密鑰為公共信息。則U2計算K11的過程如下:

首先計算K12

K12=H3(e∧(P23，BK13)K23)=H3(e∧((Q23+sv)-1P，

K13(Q23+sv)P)K23)=H3(e∧(P，P)K13K23)

(3)

然后再計算K11

K11=H3(e∧(P12，BK22)K12)=H3(e∧((Q12+sw)-1P，

K22(Q12+sw)P)K12)=H3(e∧(P，P)K12K22)

(4)

若從U3或U4的角度出發，計算K22，可得

K22=H3(e^(P，P)K23k34)

(5)

將式(3)和(5)代入式(4)，可進一步將K11轉換為如下形式:

K11=H3(e^(P，P)H3(e^(P，P)K13K23)H3(e^(P，P)K33K43))(6)

由式(6)顯見，子組成員最終協商出的根節點的生成密鑰僅與子組成員所關聯的葉子節點的生成密鑰有關。

2.3 DPG組播通信過程

2.3.1 發送者在組內

假定圖2中子組的身份標志為SGA，則QA=H4(SGA)。采用文獻[7]中的安全性要求更高的基于身份的加密方案Full Ident。則子組SGA的公鑰參數PpubA=K11P，私鑰DA=K11QA。其中:K11為子組SGA中成員協商出的根節點的生成密鑰;P為G1的生成元。KGCs處公開所有子組的身份標志以及對應的公鑰。

子組SGB中的某個成員給子組SGA發送消息的過程為，從KGCs處公布的信息中獲得QA和PpubA，然后隨機選擇σ∈{0，1}n，計算r=H6(σ，M)。對于M∈M，加密后的密文為

C=〈U，V，W〉=〈rP，σH5(e∧(QA，PpubA)r)，MH7(σ)〉

子組SGA中成員解密過程如下:

a)首先計算VH5(e∧(DA，U))，

VH5(e∧(DA，U))=VH5(e∧(K11QA，rP))=

VH5(e∧(QA，K11P)r)=VH5(e∧(QA，PpubA)r)=σ′

b)再計算WH7(σ′)=M′，

c)最后令r′=H6(σ′，M′)，若U≠r′P，則拒絕接收此密文;否則，M′即為解密后的明文。

2.3.2 發送者在組外

以上通信過程考慮的是組內成員相互通信的應用場景，如視頻電話會議。實際上，對于發送者在組外的一般意義的組播應用，如視頻點播，此方案同樣適合。具體過程是，外部發送者首先將會話密鑰通過上述方案加密發送給各子組，從而所有的合法組成員便可解密獲得會話密鑰;然后發送者用會話密鑰加密真正的組播通信數據，發送到組播組。

2.4 新成員加入過程

仍以圖2所示的子組為例，假設有新成員U5要求加入，則KGCs更新子組Merkle身份樹，如圖3所示。

顯見，圖中虛線部分為U5加入后受到影響的節點。U4被關聯到新的葉子節點ID14上，U5則在其兄弟節點ID24上。更新子組Merkle身份樹的一個基本原則是確保每個節點(除根節點)都有兄弟節點。KGCs為受影響的節點重新計算hash值、私鑰和盲密鑰，并選擇K24∈Zq，連同P24、P43和P22一起安全單播給U5。需要注意的是，KGCs應將更新后的P22發送給U3，以及更新后的P22、P43和P14發送給U4，而U5加入前的K43仍可作為K14使用。

子組Merkle身份樹更新后，U1~U5協商更新后的K11的過程與2.2節類似，不再詳述。由于根節點到U5所在葉子節點這條路徑所有節點的私鑰和盲密鑰都已更新，U5便無法計算出其加入之前子組的K11，也就無法獲得子組以前的私鑰，自然也無法解密組之前的通信內容，從而保證了組播的前向安全要求。

需要說明的是，此例考慮的是單個或少量成員加入的情形，當有大量成員同時要求加入組播組時，KGCs為之創建一個新子組的計算和通信代價要遠小于逐個更新各子組的代價。

2.5 組成員退出過程

以圖3所示的變化后的子組為例，假設成員U4和U5同時退出子組，則更新后的子組Merkle身份樹如圖4所示。

為確保更新后的子組Merkle身份樹中每個節點(除根節點)都有兄弟節點，U3被提升關聯到節點ID22上。與加入過程類似，KGCs為受影響的節點重新計算hash值、私鑰和盲密鑰。此例中，即KGCs需要將更新后的P22發送給U3。U1到U3重新協商出一個新的K11。退出的U4和U5由于不掌握更新的P22，便無法計算出更新的K11，從而保證了組播的后向安全要求。

3 安全性分析

從密鑰協商安全性要求的角度來看，本方案可滿足其要求:

a)組會話密鑰安全。每輪密鑰協商過程中都有一個隨機數σ∈{0，1}n，基于DLP、CDHP和BIDHP困難問題假設，被動攻擊者通過竊聽組廣播消息獲取組會話密鑰在計算上是不可行的。

b)前向安全。當有新成員Uj加入組播組時，子組身份樹的根節點到Uj所在節點這條路徑上所有的私鑰和盲密鑰都將更新，Uj則無法計算其加入組之前所在子組K11的及私鑰，保證了前向安全。

c)后向安全。對于退出組播組的成員Ul，同樣由于其所在子組身份樹信息的更新，也無法計算出其退出后的K11，從而保證了后向安全。

d)抗合謀攻擊。對于退出組播組的一組成員，即使其合謀也無法計算出所在子組的K11。

4 計算與通信代價分析

從上述過程可知，在整個安全組播生命期內，KGCs只負責系統初始化、成員注冊以及運行過程中組成員動態變化時公共信息的更新工作。具體地說，其需要維護并公開發布兩張表，即各子組Merkle身份樹信息表{SGID，IDji，Qji，BKji，IDLchild，IDRchild}和各子組公鑰信息表{SGID，QID，PpubID，UUsers}。其中:IDLchild、IDRchild分別指節點Nji的左、右孩子節點的身份信息，若Nji為葉子節點，則其IDLchild和IDRchild記為“-”，Nusers指子組SGID當前的成員數，NUsers≤2h-1。

對于各子組中的每個成員，則需要在本地保密并維護表{IDji，Qji，Pji}，以保存和更新KGCs發來的從其所在葉子節點到子組根節點(根節點除外)這條路徑上所有節點的私鑰。

前文已定義每棵子組Merkle身份樹的最大高度為h，則每個成員最多需要在本地保存(h-1)條相關節點私鑰信息。

子組成員協商密鑰時，每個成員最多需要作(h-1)次pairing運算。

當某個成員需要與t個子組進行通信時，