—149—
基于秘密共享的组播密钥更新算法
赵龙泉，苏锦海
(解放军信息工程大学电子技术学院，郑州 450004)
摘 要：提出一种基于秘密共享的组播密钥更新算法。采用二叉逻辑密钥树结构，根据组成员状态变化，利用秘密共享的思想构造广播消
息，使组成员可以逐步计算组密钥，而非组成员不能计算组密钥，从而实现组密钥更新。分析表明，与采用逻辑密钥树的算法相比，该算
法能降低密钥更新时的通信量和计算量，适用于大型的动态群组通信。
关键词：组密钥管理；秘密共享；密钥树；密钥更新
Group Re-keying Algorithm Based on Secret Sharing
ZHAO Long-quan, SU Jin-hai
(Institute of Electronic Technology, PLA Information Engineering University, Zhengzhou 450004, China)
【Abstract】The ideas of group re-keying algorithms based on secret sharing using the LKH tree are proposed in this paper. The algorithms
construct a message using secret sharing with the dynamic change of group members. The group members can reconstruct the new group key. It is
proved that the new algorithms have obvious superiority than that of the previously proposed algorithms on communication and computation, and are
suitable for large dynamic group.
【Key words】group key management; secret sharing; key tree; re-keying
计 算 机 工 程
Computer Engineering第36卷 第21期
Vol.36 No.21 2010年11月
November 2010
·安全技术· 文章编号：1000—3428(2010)21—0149—03文献标识码：A 中图分类号：TP309
1 概述
组播是一种面向组接收者的高效通信方式，有效地节约
了带宽，降低了服务器的负担，可广泛地应用于多媒体远程
教育、分布式系统、网络视频会议等。安全组播的关键问题
是如何实现有效的组密钥管理。在组播通信中，组成员关系
是动态变化的，在成员加入/离开时要及时更新组密钥。尤其
是在一个大型动态多播组中，组成员变动频繁时，如何解决
密钥更新，是组密钥管理的核心问题。
文献[1-2]分别提出了采用逻辑密钥层次(LKH, Logical
Key Hierarchy)的组密钥管理机制，通过增加辅助节点密钥，
有效地降低组成员状态变化时密钥更新的通信次数，减少了
通信量。但是增加了密钥服务器和组成员的密钥存储量。文
献[3]提出的单向函数树(One-Way Function Tree, OFT)算法是
LKH算法的一种改进，通过设置单向函数，减少密钥更新时
的消息长度，将通信代价降低为LKH算法的一半。文献[4]
中提出了一种基于多项式展开的PE-LKH方案，由于不使用
加解密算法，降低了密钥更新时的计算量。
文献[5]提出有恢复能力的组密钥分发方案，文献[6]提出
一种基于秘密共享的、具有无条件安全的多轮撤消算法，使
用门限秘密共享的技术，降低了密钥更新的通信量。但是这
2个方案是平级结构，扩展性受到一定的限制。文献[7]提出
基于门限秘密共享的动态组播密钥协商方案，采用两级分层
分组结构。
本文在LKH的基础上结合秘密共享的思想，提出一个基
于秘密共享的组密钥更新算法。该算法基于二叉逻辑密钥树
结构，利用秘密共享的思想，当组成员状态变化时，通过组
控制器广播的公开消息，使组成员可以逐步计算出组密钥，
而非组成员不能计算组密钥，从而实现组密钥更新。 2 方案描述
本文提出的组密钥更新算法基于二叉逻辑密钥树结构，
使用秘密共享理论和单向函数的方法优化密钥更新的通信量
和计算量。与以往算法比较，本算法具有更好的性能。
2.1 符号定义
符号定义如下：
p：为一个大素数；
Zp：表示模p的剩余类群，所有运算都Zp中；
r：表示密钥更新次数，
()SKr：表示r时的组会话密钥，
()
iKr：表示r时的为节点i的密钥，
:(,)
hhBab：表示组控制器广播的h层的信息，
i：表示节点位置的Huffman编码，
()h：是一个密码学意义上的单向函数，令()(,)
iiryrhkµ=；
()f：表示一个从Huffman编码域到Zp的一一映射，且
0,,0()0
xfx
=≠"；
rµ：表示r次会话时的新鲜因子。
2.2 二叉逻辑密钥树的初始化
组控制器根据潜在的成员数N构建一棵二叉平衡树，密
钥树的高度为lbhN=⎡⎤⎢⎥。树根为组管理者，树叶为组成员，
树的中间节点为逻辑节点。组控制器利用Huffman编码方法
对二叉逻辑密钥树的节点编码，作为节点的位置信息。每个
成员则拥有从所在的叶节点到根的路径上的所有密钥。
在初始化时，即0r=，组控制器GC负责初始化密钥树，
作者简介：赵龙泉(1982－)，男，硕士研究生，主研方向：密钥管理；
苏锦海，教授、博士
收稿日期：2010-04-10 E-mail：zhaolongquan1982@sina.com —150— 随机的选择更新因子
0µ。然后，利用单向函数和秘密共享理
论从下往上配置密钥。假设有一节点为i，2个儿子节点为
2,21ii+，组控制器根据2个儿子节点的密钥和位置信息，利
用Shamir门限方案构造1阶多项式，将0代入，计算节点i的密钥：212
2((0)(0))
(0)(0)(2)
(21)(2)ii
iiyy
Kyfi
fifi+−
=−
+−。依次类推，可以
计算出初始化时的组会话密钥。
以3层的平衡二叉树为例说明逻辑密钥树初始化，如
图1所示。组成员
010u拥有的密钥为
010010{,,,}KKKSK，其中，
SK为组会话通信密钥，
010K为组成员的用户私钥，
001,KK为
辅助节点密钥。以节点密钥
01010011,,KKK为例，父子节点密钥的关系为011010
01010((0)(0))
(0)(0)(010)
(011)(010)yy
Kyf
ff−
=−
−。从初始化
过程可以看出，每个用户的存储量为lbhN=⎡⎤⎢⎥，组控制器的
存储量为21N−，与基本的密钥树结构相同。
图1 二叉平衡逻辑密钥树
2.3 密钥更新
为保证组密钥的安全性，在用户加入和退出时，必须更
新组密钥。针对大型动态用户组，组密钥更新是关键问题。
在密钥更新时，从下而上采用广播的方式，更新发生变化的
节点密钥。下面以图1为例，说明密钥更新的过程。
2.3.1 用户加入
当有新成员申请加入组播组时，为了确保新成员不能访
问以前的通信数据，必须对会话密钥进行更新，更新过程描
述如下：
(1)新成员申请加入组播组。
假设节点011是1个空节点。用户
iu申请加入组播组，
组控制器首先验证成员的身份，确认后将该成员插入成员节
点011，并产生密钥
011K作为该成员的私有密钥，秘密分发
给该成员。为了实现向前访问控制，组控制器需要产生新组
会话密钥(1)SKr+，则需要更新的节点密钥为
0(),(),SKrKr
01011(),()KrKr。
(2)组控制器建立广播信息。
1)组控制器根据两点
010((010),(1))fyr+,
011((011),(1))fyr+，
利用插值定理构造直线：
011010
3010(1)(1)
(,):(1)((010))
(011)(010)yryr
Fxyyyrxf
ff+−+
−+=−
−
2)组控制器将0x=代入直线方程
3(,)Fxy，计算父亲节点
的密钥
013(1)(0)KrF+=；
3)组控制器随机的选择一点
333(,)(,)abFxy∈且不等于以
上3点，作为广播消息
3B；
同理，确定
0(1),(1)SKrKr++，选择广播消息
122:(,),Bab
211:(,)Bab。 (3)组控制器广播消息，消息包括
1231{,,,}
rBBBBµ
+=。
(4)组成员计算更新后的密钥。
当组成员收到消息后，根据所掌握的密钥计算会话密钥。
成员
010011,uu利用私钥和
3B重构
3(,)Fxy，将0x=代入获得
01(1)Kr+，然后再依次计算
0(1),(1)KrSKr++；成员
000001,uu
利用
00(1)Kr+依次计算
0(1),(1)KrSKr++；成员
00101110111,,,uuuu
利用
1(1)Kr+和
1B直接计算(1)SKr+。
通过以上过程分析可知，在有单个成员加入时，组控制
器只需要广播一条公开消息，组成员就可以计算更新后会话
密钥，节省了密钥更新时的通信量。同时，不同位置的用户
的计算量是不同，在密钥更新过程中，不需要使用加密算法，
减少了成员的计算。
2.3.2 用户退出
当有成员离开组播组时，为了确保离开成员不能访问未
来的通信数据，必须对其所拥有的密钥进行更新，更新过程
描述如下：
(1)组成员申请退出组播组。
假设成员
011u退出组播组，则需要更新的节点密钥为
001011(),(),(),()SKrKrKrKr。
(2)组控制器建立广播信息。
1)组控制器随机的选择广播消息
333:(,)Bab，然后根据两
点
33010(,),((010),)abfy，利用插值定理构造一条直线：
3010
3010
3(1)
(,):(1)((010))
(010)byr
Fxyyyrxf
af−+
−+=−
−
2)组控制器将0x=代入
3(,)Fxy，计算节点密钥
013(1)(0)KrF+=；
3)组控制器根据两点
0001((00),(1)),((01),(1))fyrfyr++利
用插值定理构造直线：
0100
200(1)(1)
(,):(1)((00))
(01)(00)yryr
Fxyyyrxf
ff+−+
−+=−
−
4)组控制器将0x=代入，确定
02(1)(0)KrF+=，确定广
播消息
2222:(,)(,)BabFxy∈，且不等于以上3点；
同理，组控制器确定会话密钥(1)SKr+和广播消息
111:(,)Bab。
(3)组控制器广播消息
1231{,,,}
rBBBBµ
+=。
(4)组成员计算更新后的密钥。
当成员收到消息后，根据所掌握的辅助密钥计算会话密
钥。成员
010u利用私钥和
3B重构
3(,)Fxy，将0x=代入获得
01(1)Kr+，然后再依次计算
0(1),(1)KrSKr++；成员
000001,uu
利用
00(1)Kr+依次计算
0(1),(1)KrSKr++；成员
00101110111,,,uuuu利用
1(1)Kr+和
1B直接计算(1)SKr+。
3 方案分析
3.1 安全性分析
从组密钥管理的安全性角度来看，本文算法满足组密钥
管理要求：
(1)组会话密钥安全：
1)在用户变化时，组控制器随机的选取更新因子
rµ，通
过单向函数和更新因子
rµ保证组密钥和辅助节点密钥的新
鲜性和随机性。
2)在密钥更新时，组控制器利用秘密共享理论，构造一
阶多项式，然后广播公开信息，合法组成员可以根据广播信