（计算机软件与理论专业论文）安全组播密钥更新方案的研究.pdf

摘要 随着音频视频会议、多媒体广播、网络协同工作组的出现与迅速发展组播被 广泛应用于一点到多点( o n e t o m a n y ) 和多点到多, 点( m a n y t o m a n y ) 的通信中。安 全组播需要满足：机密l 生( g r o u ps e c r e c y ) 、前向安全( f o r w a r da c c e s sc o n f i d e n t i a l i t y ) 和后向安全( b a c k w a r da c c e s sc o n f i d e n t i a l i t y ) 。只有拥有最新组密钥的当前组成员 能够加密和解密组播报文，每当有成员离开或加入组时必须更新组密钥。 近年来，安全组播的密钥更新( r e k e y i n g ) 问题一直受到关注。逻辑密钥树 l k h ( l o g i c a lk e yh i e r a r c h y ) 方案把密钥更新的复杂度从d ( v ) 降至o ( 1 0 9 n ) ，其 中是组成员的数量。这是一个非常突出的贡献，目前很多关于密钥更新的研究 都是基于l k h 的优化。组成员的加入和离开导致密钥更新，如果组成员变动频繁 发生，或在短时间内集中大量发生，会对系统的性能造成很大的影响。 本文针对安全组播中多成员集中变动引起的密钥更新管理问题，提出一种 l k h 优化方法。文章从成员属性间的内部联系出发，根据相同属性对成员关系 变动的影响因子r i f ( r e k e y i n gi n f l u e n c ef a c t o r s ) ，对成员进行逐级分层聚类，使得 相关度越高的成员在优化后的l k h 中分布越集中。当大量同类成员由于同一个 r i f 的作用集中发生动态变化时，由于他们分布集中，更新过程涉及的分枝较少， 因而能有效地节约平均密钥更新量和更新时所占用的带宽。本文研究基于影响因 子的l k h 优化，并给出相关算法，包括密钥树的构造算法和更新算法。我们还 通过对比分析优化前后的密钥更新代价，证明了上述优化方法对于具有内在联系 的大量同类成员集中发生动态变化的情况十分有效。 关键词安全组播；密钥更新；信息安全 a b s t r a c t m u l t i c a s ti s w i d e l ya p p l i e di no n e t o - m a n y a n dm a n y t o - m a n yc o m m u n i c a t i o n s n o w a d a y s s e c u r em u l t i c a s tn e e d s t o s a t i s f y ：g r o u ps e c r e c y , f o r w a r d a c c e s s c o n f i d e n t i a l i t y , b a c k w a r d a c c e s s c o n f i d e n t i a l i t y t h a ti so n l yt h ec u r r e n tg r o u p m e m b e r sh a v et h en e w e s tg r o u pk e yt oe n c r y p ta n d d e c r y p tt h et r a n s m i s s i o nm e s s a g e s h e n c ew h e n e v e ra ni n d i v i d u a lj o i n so rl e a v e st h eg r o u p ，r e d i s t r i b u t i o no ft h eg r o u p k e yi sn e c e s s a r y f o rt h es i g n i f i c a n ts t a t u so fr e k e y i n g ，d u r i n gr e c e n ty e a r s ，t h e r eh a sb e e nm u c h r e s e a r c ho ni m p r o v i n gt h ep e r f o r m a n c eo fr e k e y i n g t h ei m p o r t a n tw o r ko fl k h a p p r o a c hh a sr e d u c e dt h ec o m p l e x i t yo fr e k e yo p e r a t i o nf r o md ( dt oo ( 1 0 9 n ) ， w h e r eni st h en u m b e ro fg r o u pm e m b e r s i fn oe f f i c i e n ta u x i l i a r ym e a s u r e sa r et a k e nw h i l eg r o u pm e m b e r sl e a v eo rj o i ni n b a t c h e s ，e v e nt h es c a l a b l el o g i c a lk e yh i e r a r c h y ( l k h ) a p p r o a c hw i l l p o s ea b o t t l e n e c ka f t e r f r e q u e n t i n d i v i d u a l r e k e y i n g i n s t e a do fo r g a n i z i n gm e m b e r s r a n d o m l ya n du n o r d e r l yi nt h el e a fn o d e s ，w ep r o p o s ea no p t i m a ll k hs c h e m ef i r s t l y u t i l i z i n gt h es i m i l a ra t t r i b u t e sa n di n t e r n a lc o r r e l a t i o no fg r o u pm e m b e r st h a th a v ea n i m p a c to nb a t c hr e m o v a la sr e k e y i n gi n f l u e n c ef a c t o r s ( r i f ) ，t oc l u s t e rg r o u p m e m b e r sa n df u r t h e rc o n s t r u c ta no p t i m i z a t i o nl o g i ck e yt r e e i no u ra p p r o a c h ，t h e m e m b e r sw i t h h i g h e rc o r r e l a t i o nd e g r e ea c c o r d i n gt o t h er i fd i s t r i b u t em o r e c e n t r a l i z e di nt h el o g i ck e yt r e e w ep r e s e n ti n t a c tc o n s t r u c t i o na l g o r i t h ma n dk e y m a n a g e m e n ts t r a t e g i e sf o ro u ro p t i m i z a t i o nt r e e 。f u r t h e r m o r e ，w ea n a l y z et h e r e k e y i n gp e r f o r m a n c ef o rb a t c hl e a v i n go fo u ra p p r o a c hb yc o m p a r i n gw i t ht h a ti n t r a d i t i o n a ll k ho nw o r s t - c a s ea n da v e r a g e c a s e ，m a k es i m u l a t i o n ，a n ds h o wo u r s c h e m ei sv e r ye f f i c i e n ta n de f f e c t i v ef o rd e p e n d e n tb a t c hr e m o v a lw i t hr e s p e c tt o r e d i s t r i b u t i o na n db a n d w i d t hu s a g ea sw e l l k e y w o r d s s e c u r em u l t i c a s t ；r e k e y i n g ；i n f o r m a t i o ns e c u r i t y 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研究成果。本人在 论文写作中参考的其他个人或集体的研究成果，均在文中以明确方式标明。 本人依法享有和承担由此论文产生的权利和责任。 枞( ：扬一矽 年咱f7 日 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。厦门大学有权保留 并向国家主管部门或其指定机构送交论文的纸质版和电子版，有权将学位论文用 于非赢利目的的少量复制并允许论文进入学校图书馆被查阅，有权将学位论文的 内容编入有关数据库进行检索，有权将学位论文的标题和摘要汇编出版。保密的 学位论文在解密后适用本规定。 本学位论文属于 1 保密( ) ，在年解密后适用本授权书。 2 不保密( ) ( 请在以上相应括号内打“ ) 僦名：物一晚卅 导师签 ：劲口7 年) - 月l7e l 1 年 月n 日 i 第一章绪论 1 1 组播的发展历史 第一章绪论 在i n t e r n e t 发展初期，普遍采用的数据传播方式是单播( u n i c a s t ) 和广 播( b r o a d c a s t ) 1 3 0 - 3 4 。单播是在单台源主机与单台目的主机之间的通讯； 广播是单台源主机与网络中所以其他主机之间的通讯。随着网络带宽资源的 日益丰富，网络会议系统、视频点播系统等流媒体网络应用开始出现。这类 应用通常要求把信息从个源点发送到多个目的地，但并非所有主机，如果 采用广播方式，不仅会造成带宽浪费，严重时还可能由于路由回环引发广播 风暴；如果采用传统的单播方式，让信息源与每一个目的用户逐一建立单独 的连接，发送重复的数据包，既浪费带宽，也增加了服务器的负载。传统的 单播和广播通信方式不能有效满足单点对多点的需求，组播( m u l t i c a s t ) 就 是在这样的背景下产生的。 组播的基本思想是源点只发送一份数据，该数据的目的地址为组播组 ( m u l t i c a s tg r o u p ) 地址，组播组是网络中某个确定节点的子集，组播组中 的所有节点都能接收到同样的数据拷贝，并且只有组播组内的节点才能接收 到该数据。i p 组播在i p 网络中是以尽力传送( b e s t e f f o r t ) 的形式将数据包 发送到组播组。 2 0 世纪8 0 年代中期，斯坦福大学的博士生s e d e e r i n g 发表h o s t g r o u p ：am u l t i c a s te x t e n s i o nt ot h ei n t e r n e tp r o t o c o l ( r f c 0 9 6 6 ) 和h o s t e x t e n s i o n sf o ri pm u l t i c a s t i n g ( r f c 0 9 8 8 ) 两篇论文，提出了i p 组播的可能 性。 1 9 8 8 年，d e e r i n g 等人发表题为距离向量组播路由协议的文章 ( i 疆c 1 0 7 5 ) ，提出了将组播的功能机制增加到数据网i p 层的组播实现体系 结构，这种体系结构成为i p 组播( i pm u l t i c a s t ) 。它是组播路由协议的首次 安全组播密钥更新方案的研究 实践。1 9 9 1 年1 2 月，d e e r i n g 在他的博士论文数据报互连网络中的组播 路由 ( r f c l l l 2 ) 中奠定了组播网络体系结构和路由协议的基础，形成了 i n t e m e t 组管理协议( i g m p ) 的原型，文中对i p 组播的业务提供的方式和 形式进行的描述和定义，被看成是i p 组播的标准业务模型的定义。 1 9 9 2 年，i p 组播主干网m b o n e ( m u l t i c a s tb o n e ) 建立，m b o n e 是一个 相互连接的子网和路由器的集合，支持i p 组播业务流的传送。1 9 9 4 年， r f c1 5 8 4 形成了对o s p f 协议的扩展协议m o s p f 。1 9 9 6 年底，r f c 2 0 2 2 中 出现了对o s p f 协议的扩展协议m o s p f 。1 9 9 7 年，r f c 2 1 8 9 中有核树 ( c b t v 2 ) 组播路由体系结构形成。在随后的两三年中，各种组播协议标准 出台，到了2 0 0 0 年底，各种组播m i b 库的制定标志着组播技术开始向可管 理、可控制方向发展。 i p 组播技术独特的优点在于，在组播网络中，当组播用户数量成倍增 长时，主干带宽不需要随之增加。因此近年来，随着高带宽的多媒体应用的 迅速发展，组播技术已经成为当前网络技术中的研究热点之一。 1 2 组播的应用 随着骨干网带宽增加使因特网视音频成为可能，小区网络中视音频应 用不断丰富。这类依赖于组播技术才能实现的应用的出现，令对组播技术的 支持成为网络建设的一个重要内容。 i p 组播技术的提出是基于对业务通信结构进行优化的思想。在某些业 务中，常常有一定数量的用户在接收一些完全相同的数据流。如果采用i p 单播技术来为这些用户服务，需要发送者为每个用户单独建立一个数据流。 由于这些数据流重复地发送完全相同的数据，所以将大大加重发送主机和通 信网络的负载，同时也比较难以保证对不同接收者的服务的公平性。而组播 技术只要求发送者为同一数据发送一个数据流，通过网络来选择合适的通信 第一章绪论 设备，为不同的用户复制同一数据流来降低主机服务负载、网络通信负 载和实现服务的公平性。 组播应用大致可以分为三类：点对多点应用，多点对点应用和多点对多 点应用 3 5 , 3 6 1 。 1 2 1 点对多点的应用 点对多点应用是指一个发送者，多个接收者的应用形式，这是最常见的 组播应用形式。典型的应用包括： 媒体广播：如演讲、演示、会议等按日程进行的事件。其传统媒体分发 手段通常采用电视和广播。这一类应用通常需要一个或多个恒定速率的 数据流，当采用多个数据流( 如语音和视频) 时，往往它们之间需要同 步，并且相互之间有不同的优先级。它们往往要求较高的带宽、较小的 延时抖动，但是对绝对延时的要求不是很高。 媒体推送：如新闻标题、天气变化、运动比分等一些非商业关键性的动 态变化的信息。它们要求的带宽较低、对延时也没有什么要求。 信息缓存：如网站信息、执行代码和其他基于文件的分布式复制或缓存 更新。它们对带宽的要求一般，对延时的要求也一般。 事件通知：如网络时间、组播会话日程、随机数字、密钥、配置更新、 有效范围的网络警报或其他有用信息。它们对带宽的需求有所不同，但 是一般都比较低，对延时的要求也一般。 状态监视：如股票价格、传感设备、安全系统、生产信息或其他实时信 息。这类带宽要求根据采样周期和精度有所不同，可能会有恒定速率带 宽或突发带宽要求，通常对带宽和延时的要求一般。 1 2 2 多点对点的应用 多点对点应用是指多个发送者，一个接收者的应用形式。通常是双向请 求响应应用，任何一端( 多点或点) 都有可能发起请求。典型应用包括： 安全组播密钥更新方案的研究 资源查找：如服务定位，它要求的带宽较低，对时延的要求一般。 数据收集：它是点对多点应用中状态监视应用的反向过程。它可能由多 个传感设备把数据发回给一个数据收集主机。带宽要求根据采样周期和 精度有所不同，可能会有恒定速率带宽或突发带宽要求，通常这类应用 对带宽和延时的要求一般。 网络竞拍：拍卖者拍卖产品，而多个竞拍者把标价发回给拍卖者。 信息询问：询问者发送一个询问，所有被询问者返回应答。通常这对带 宽的要求较低，对延时不太敏感。 1 2 3 多点对多点的应用 多点对多点应用是指多个发送者和多个接收者的应用形式。通常，每个 接收者可以接收多个发送者发送的数据，同时，每个发送者可以把数据发送 给多个接收者。典型应用包括： 多点会议：通常音视频和白板应用构成多点会议应用。在多点会议中， 不同的数据流拥有不同的优先级。传统的多点会议采用专门的多点控制 单元来协调和分配它们，采用组播可以直接由任何一个发送者向所有接 收者发送，多点控制单元用来控制当前发言权。这类应用对带宽和延时 要求都比较高。 资源同步：如日程、目录、信息等分布数据库的同步。它们对带宽和延 时的要求一般。 并行处理：如分布式并行处理。它对带宽和延时的要求都比较高。 协同处理：如共享文档的编辑。它对带宽和延时的要求一般。 远程学习：这实际上是媒体广播应用加上对上行数据流( 允许学生向老 师提问) 的支持。它对带宽和延时的要求一般。 讨论组：类似于基于文本的多点会议，还可以提供一些模拟的表达。 分布式交互模拟( d i s ) ：它对带宽和时延的要求较高。 第一章绪论 多人游戏：多人游戏是一种带讨论组能力的简单分布式交互模拟。它对 带宽和时延的要求都比较高。 j a ms e s s i o n ：这是一种音频编码共享应用。它对带宽和时延的要求都比 较高。 1 3 组播的安全 i p 组播不能保证只有注册用户才能发送和接收组播数据，主要有以下 三个原因：首先，i p 组播使用u d p ，任何主机都可以向某个组播地址发送 u d p 包，并且低层组播机构将传送这些u d p 包到所有组成员；其次， i n t e r n e t 缺少对于网络层的访问控制；第三，组成员可以随时加入退出组播 组。这几点使得组播安全性问题难以解决。 1 3 1 安全组播概述 缺乏安全机制限制了组播在各种网络业务中得应用。在虚拟会议中，通 常需要确保会议内容的机密性，并且在必要时能够对发言人的身份进行认 证；在多媒体实时点播中，要确保只有付费用户才能看到节目内容。组播协 议缺乏安全机制来满足上述要求，采用明文传输的组播报文在网络上很容易 被偷听、冒充和篡改2 8 1 。 我们把组播的安全需求归纳为如下几点： 保密：只有拥有解密密钥的节点才能解读组播报文的内容。 组成员认证：非组成员无法生成有效的认证信息，进而无法冒充组成员 发送组播报文。 源认证( 抗抵赖) ：组成员无法生成其他组成员的认证信息，进而无法冒 充其他组成员发送组播报文。另一方面，组成员也无法否认其发送的信 息。 匿名性：为组成员提供匿名发言的机制，也就是说，接收方无法从接收到 的组播报文推断出发送方的身份。 气 安全组播密钥更新方案的研究 完整性：提供验证收到的组播报文是否被篡改的手段。 对组播报文加密传输是实现组播保密性的一种方法。加密和解密用的密 钥只有组成员才知道，这样能够确保被加密的报文只有组成员才能解读。组 成员认证也可以利用该密钥来实现，因为只有拥有密钥的组成员才能正确地 生成加密的组播报文。利用多方共享密钥来解决安全问题的关键是密钥的生 成和分发。这种生成和分发必须是排外的，即非组成员无法获得密钥。 源认证完整性和匿名服务通常也要利用双方或多方之间信息的排外共 享。 1 3 2 安全组播密钥管理 安全组播密钥管理通过为组播成员生成、发送和更新组密钥来满足加密 认证等安全需求。组播密钥管理为参与组播的成员生成分发和更新组密钥 ( g r o u pk e y ) 。组密钥是所有组成员都知道的密钥，被用来对组播报文进行加 密解密认证等操作，以满足保密组成员认证完整性等需求。 与单播的密钥管理相比，前向加密( f o r w a r dc o n f i d e n t i a l i t y ) 、后向加密 ( b a c k w a r dc o n f i d e n t i a l i t y ) 和同谋破解是组播密钥管理特有的问题。 前向加密要求主动退出组播的节点或被强制退出的节点( 比如恶意节点) 无法继续参与组播，即无法利用它们所知道的密钥解密后继组播报文和生成 有效的加密报文。重新生成并更新组密钥可以实现前向加密，但要注意的 是，密钥更新报文同样可以被前组成员获得，要防止前组成员从密钥更新报 文中得到新的密钥。 后向加密要求新加入的组成员无法破解它加入前的组播报文。当新成员 加入时更新密钥就可以实现这一点。 组播密钥管理不仅要防止某个节点破解系统，还要防止某几个节点联合 起来同谋破解。如果几个恶意节点联合起来，掌握了足够多的密钥信息，使 得无论系统如何更新密钥都可以获得更新的密钥，导致组播密钥管理的前向 第一章绪论 加密和后向加密失败，或者使得恶意节点可以冒充其他节点进行欺骗( 破解 系统的认证功能) ，我们把这种情况称为同谋破解。组播密钥管理要杜绝同 谋破解或降低同谋破解的概率。 组播密钥管理在设计时还要考虑如下因素的影响： 差异性：组播密钥管理涉及到多个通信实体。这些通信实体之间存在着 各种差异。这些差异包括是否可信任、是否愿意为其他实体提供服务、 是否具有足够的计算能力、是否具有足够的带宽和适当的网络延迟、是 否接受组播报文( 允许存在只发送不接收的实体) 以及是否发送组播报文 ( 允许存在只接收不发送的实体) 等等。组播密钥管理方案在设计时要考 虑这些差异的影响。 可扩展性：可扩展性也是组播密钥管理所要考虑的重点。组播的规模从 几个节点到上万个节点甚至更多，随着组播规模的扩大，保存密钥所占用 的节点存储空间密钥生成所需要的计算量密钥发送所占用的网络带宽密 钥更新的时间延迟和密钥更新的频率都会相应增加。 健壮性：对于单播来说，通信的任一方失败都会使会话终止，而组播中 部分节点的失败不应当影响整个组播会话的继续进行。这就对组播密钥 管理提出了健壮性的要求。 可靠性：可靠性也是一个确保组播密钥管理正确而有效工作的重要因 素。组播密钥管理的控制报文( 包括密钥更新报文组成员关系变动的通 知报文等) 通常利用不可靠的组播进行传输。这种传输存在丢包乱序重 复等情况。设想如果缺乏确保可靠性的机制，一个组成员没有收到密钥 更新报文，它将无法参与后继的组播通信。 1 3 3 安全组播密钥管理的关键问题 组播密钥管理方案的设计，需要统筹考虑通信实体间的差异系统的可扩 展性健壮性和可靠性等诸多因素。与组播的安全需求综合起来，我们把组播 安全组播密钥更新方案的研究 密钥管理所要解决的主要问题归纳如下： 前向加密：确保组成员在退出组后，除非重新加入，否则无法再参与组 播，包括获知组播报文的内容和发送加密报文。 后向加密：确保新加入的组成员无法破解它加入前的组播报文。 同谋破解：避免多个组员联合起来破解系统( 或减少发生的概率) 。 可扩展性：( 1 ) 密钥生成计算量：通常，协同的密钥生成需要较大的计 算量，当节点的计算资源不充足或密钥更新频繁时，要考虑密钥生成给 节点带来的负载。( 2 ) 密钥发布占用带宽：密钥更新报文不应占用过多 的网络带宽。( 3 ) 密钥发布的延迟：密钥更新时要使所有组成员都能及 时地获得新的密钥。 健壮性：当部分组成员失效时，安全组播仍然能够继续工作。 可靠性：确保密钥分发、更新在不可靠的网络环境中的正确实行。 1 4 本文主要工作和篇章结构 本文主要研究安全组播的密钥更新管理问题。在对安全组播密钥更新管 理的相关优化方案进行深入讨论的基础上，从组播成员的相同属性和组成员 发生变动的关联性出发，提出密钥更新影响因子的概念，并将统计学中分层 聚类的思想引入组播密钥管理方案中，结合密钥更新影响因子对现有的 l k h 方案进行优化。本文给出了基于影响因子的l k h 优化方法的完整算 法，包括密钥树的构造算法和各种情况下对应的密钥树更新算法。通过理论 证明和仿真实验，证明上述优化方法对于具有内在联系的大量同类成员集中 发生动态变化的情况十分有效。 本文的篇章结果安排如下： 第一章介绍了组播的发展历史、应用、安全等背景知识，在介绍组播的 安全性时引入了安全组播密钥管理，并分析了它的主要性质和关键问题。 第二章，我们对集中控制方式逻辑密钥树l k h 的密钥管理从构造、更 第一章绪论 新和性能等方面进行深入研究。 第三章，相关工作分析。我们对基于l k h 的相关密钥更新优化方法展 开探讨，讨论分为两部分：针对单成员变动的更新优化方法和针对多成员变 动的批量更新优化方法。 第四章，阐述适用于高关联性组成员批量变动的密钥更新新方法：安全 组播中基于影响因子的l k h 优化方法，详细介绍其优化原理、构造算法、 更新算法和理论性能分析。 第五章，在一个安全组播会议模型下进行仿真实验，通过对几种密钥更 新方案仿真数据的比较和分析，总结出几种组播密钥更新方案对于高关联性 组成员批量变动情况的适应程度和代价比。 第六章对全文进行了总结，并展望了安全组播密钥管理的发展前景。 安全组播密钥更新方案的研究 第二章l k h 方案 2 1 集中控制方式逻辑密钥树的产生 集中控制方式逻辑密钥树l k h ( l o g i c a lk e yh i e r a r c h y ) 方案于1 9 9 8 年在文献【1 ，2 】中提出。在l k h 方案出现之前曾经有三种主要的拓扑结构。 这些结构虽然能满足组播密钥管理的初步要求，但是都存在相当大的缺点。 2 1 1g k m p g k m p ( g r o u pk e ym a n a g e m e n tp r o t o c 0 1 ) 是一种简单的星型拓扑结构 组播密钥管理方案 2 3 2 4 1 。g k m p 由r o o t 集中控制密钥，每个节点都与r o o t 共享一个私钥，如图1 中u f 与r o o t 共享艇，舡用来保证u f 与r o o t 间通信 安全。当u l 加入时，r o o t 在u l 的帮助下生成组密钥报文g k p ( g r o u pk e y p a c k e t ) 。 u lu 2 u 3u n 图1g k m p 密钥管理拓扑结构示意图 g k p 由用来加密组播报文的密钥g t e k ( g r o u pt r a f f i ce n c r y p t i o nk e y ) 和 用来加密g t e k 的密钥g k e k ( g r o u pk e ye n c r y p t i o nk e y ) 。当u l 加入时， r o o t 用k f 加密g k p 后发给u f 。当更换组密钥时，r o o t 用当前g k e k 加密新 生成的g k p 发送给各组成员，由于离开成员拥有当前g k e k ，所以能获得 新的g k p 。g k m p 的缺点是不能保证前向安全，并且保证后向安全的代价 第二章l k h 方案 为d ( 忉。 2 1 2 c l i q u e c l i q u e 2 5 1 是一种利用非对称密钥协议d i f f i e h e l l m a n 2 6 1 的变体来实现组 密钥的生成和发布的组播密钥管理算法。d i f f i e h e l l m a n 协议中通信双方a 和b 要生成共享密钥k ，a 和b 的密钥协商过程为： ( 1 ) a 和b 预先选取两个系统参数p 和g ，其中p 是一个大素数，g 是比 p 小的整数，称为生成元，g 满足：对从1 到( g 一1 ) 的所有整数i ， 存在j 使得i = g m o dp ，p 和g 为公开参数。 ( 2 ) a 选择一个大随机数x p ，计算x = g m o dp ，将x 发送给b 。 ( 3 ) b 选择一个大随机数y p ，计算y - - g ，m o dp ，将y 发送给a 。 ( 4 ) a 计算y 。m o dp = ( g y ) 。m o dp = g 巧m o dp = k ，获得共享密钥k 。 ( 5 ) b 计算x ym o d p = ( g x ) m o dp = g 习m o dp = k ，获得共享密钥k 。 d i f f i e h e l l m a n 协议的安全性依赖于计算离散对数的困难。c l i q u e 将 d h 协议从两个结点扩展到个结点，其中是组成员数，组成员获得共享 密钥k 的计算过程非常繁琐复杂：所有成员先选定参数p 和g ，然后各自选 定随机数x i 并计算g 而。第一个组成员u 1 计算出集合s = g x t ) 传给第二个 组成员u 2 ；u 2 计算出s ：= k 而，g 屯，g 而而) 传给u 3 。s i 中含有从g 而到g 而的 累乘和从g 而到g 而中任选( f 一1 ) 个幂值的累乘。第n 个组成员u n 收到s 万 1 并计算s ，然后将s 。组播给所有其他组成员。最后，所有成员都可以计算 出g 聊“毛m o dp 2 k 。 c l i q u e 用非对称密钥协议进行密钥管理，这在组播密钥管理方案中是非 常少见的。c l i q u e 的共享密钥生成需要个组成员串行计算生成，密钥传 输时间延迟为d ( 忉，总计算量和密钥传输所占用的带宽均为o ( n 2 ) 。因此， c l i q u e 的密钥更新效率很低，扩展性差。 安全组播密钥更新方案的研究 z 1 3i o l u s i o l u s 对组成员进行分组，每个子组有一个组安全代理g s a ( g r o u p s e c u r i t ya g e n t ) ，负责管理该子组，所有g s a 组成一个更高一级的组，由组 安全控制器g s c ( g r o u ps e c u r i t yc o n t r o l l e r ) 管理 2 7 1 。i o l u s 的特点是各个 子组采用独立的组密钥，组播报文在从子组a 传播到子组b 时要被g s a 翻 译，即用a 的组密钥解密，再用b 的组密钥加密。这种设计使得组成员关 系变化所导致的密钥更新被限制在所在子组内部，但另一方面，组播报文的 传输路径被改变了( 穿越子组边界的组播报文必须经过g s a ) ，而且g s a 要负责子组的管理和组播报文的翻译，容易成为系统的瓶颈和失效点。 2 2密钥树的构造 文献【l ，2 】提出的逻辑密钥树l k h ( l o g i c a lk e yh i e r a r c h y ) 方案在确保 前向安全、后向安全和抗同谋破解的基础上较好地解决了可扩展性问题。 l k h 方案把单成员变动引起的密钥更新代价从d ( d 降至o ( 1 0 9 n ) ，其中 是组成员的数量。 2 2 1l k h 方案的数学定义 l k h 方案中安全组播组是一个三元组：( u ，k ，r ) ，其中 u 是用户的非空有限集合： k 是密钥的非空有限集合； r 是u 和k 之间的二元关系集合，即r c ux k ，( “，七) r 当且仅 当组成员“持有密钥k 。 对于每一个安全组播组( u ，k ，尺) ，有两个函数k e y s e t 0 和u s e r s e t 0 ， k e y s e t ( u ) 是用户u 持有的密钥集合，u s e r s e t ( k ) 是持有密钥k 的用户集合。定 义如下： k e y s e t ( u ) = k l ( u ，七) 尺 第二章l k h 方案 u s e r s e t ( k ) = “i ( u ，七) r 当组成员掰离开和加入安全组播组( u ，k ，尺) 时，“与其他组员共 享的每一个密钥j | 2 都必须更新。三元组将更新为( u ，k ，r ) 。 2 2 2 密钥树的初始生成 l k h 密钥树是由组控制器统一管理的密钥树，树的每个节点都对应一 个密钥k ，树的根节点表示组会话密钥g s k ( g r o u ps e s s i o nk e y ) ，叶节点 代表与组成员一一对应的用户私钥p k ( p r i v a t ek e y ) ，中间节点都为辅助节 点。 任意组成员u ，拥有从它的私钥到组会话密钥的整条路径上的所有密 钥。l k h 密钥树的高度h 为叶节点到根节点的最大路径长度；树的维数d 为树中节点的最大子节点数。 对于有个组成员的k 叉平衡密钥树，它的高度h 为( 1 0 9 k n + 1 ) ，组控 制器保存的密钥数为( 1 一k n ) ( 1 一k ) ，每个用户保存的密钥数为h 个。如图 2 中的l k h 密钥树为8 个组成员的二叉平衡密钥树，七1 七8 为成员私钥， k 1 8 为组会话密钥， k e y s e t ( u 1 ) = k l ，k 1 2 ，k 1 4 ，k 1 8 ) ， u s e r s e t ( k 1 4 ) = u 1 ，u 2 ，u 3 ，u 4 。 u 1u 2 0 3 1 1 4 u 51 1 6 1 1 7 u 8 图2l k h 二叉平衡树的满树 安全组播密钥更新方案的研究 2 3 密钥树的更新 为保证组播组的前向安全和后向安全，每当有组成员变动时都必须更新 密钥树。 2 3 1 成员加入 当成员加入安全组播组时，首先向组控制器提出加入申请，组控制器准 予后，为新节点创建一个新的用户节点和用户私钥( 只为组控制器和新成员 共享) 。为了防止新成员解密加入前的组播信息，保证后向安全，组控制器 需要更新接入节点到根节点路径上的所有节点。如图3 中所示，当组成员 u 9 被准许加入后，组控制器分配其私钥节点的，然后将k 1 8 更新为k 1 9 ， 将k 7 8 更新为k 7 9 ，原组成员u 1 u 6 只需知道k 1 9 即可，u 7 ，u 8 和u 9 需 要知道k 1 9 和k 7 8 。 u l u 2 u 3u 4u 5u 6u 7u 8 u 9 离开 t 上 u 9 加入 u ii f 20 3u 4u 5u 60 7u 8 u 9 图3l k h 密钥树的密钥更新 第二章l k h 方案 更新密钥信息的传播方式有以下几种： 2 3 1 1 面向组成员的更新( u s e r o r i e n t e dr e k e y i n g ) 这种方式每个组成员只要用自己持有的一个密钥就可以获得所有更新密 钥。它用更新路径上的每一个旧密钥来加密更新信息，组播给原组成员；用 新成员的私钥加密更新路径上的所有密钥，单播给新成员。如图3 中，有如 下更新( s 代表组控制器， k k 表示用七来加密忌) ： s 一 u 1 ，u 6 ： k 1 9 七l a s 一 u 7 ，1 1 8 ：( k 1 9 ，k 7 9 k 7 8 s t 1 9 ： k 1 9 ，k 7 9 l k 9 这种方式需要h 个更新数据包( 更新路径长为i 1 ) ，更新时所需加密的密 钥数为驴h1 = 竿一1 2 312 面向密钥的更新( k e y - o r i e n t e dr e k e y i n g ) 这种方式中，每个更新密钥都只需被加密一次就可以被所有需要它的原 组成员获得，新成员的更新信息将用私钥单独加密。如在图3 中，将有如下 更新： s 一 u 1 ，u 8 ) ： k 1 9 k t a s u 9 ：i k l 9 k 9 s 一 u 7 ，u 8 ： k 7 9 k 7 8 s u 9 ： k 7 9 的 与面向组成员的更新方式相比，面向密钥的更新方式的加密代价从 丛笔尘一1 降至了2 ( h 1 ) ，但是它需要发送的更新数据包却从h 增至2 ( h 一 1 ) 。 为了减少更新数据包的数量，进行如下整理，将每个组成员需要的更新 数据整理在一个数据包里一次性发送给它，变为： s 一 u i ，u 6 ： k 1 9 k l s 安全组播密钥更新方案的研究 s 一 u 7 ，u 8 ： k 1 9 k 1 8 ， k 7 9 玎8 s u 9 ： k 1 9 ，k 7 9 k 0 这样可以使需要发送的更新密钥包保持为h 个。经过整理的算法为： 1 u 一8 ：加入请求 2 8 u ：对u 进行认证，分发u 的私钥k 3 8 ；在密钥树中找一个接入节点，接入心，用x j 表示接入节点，毛表 示根节点，用x i 一。表示x i 的父节点( i = 1 ，一，二f ) ，令玛+ 。为， 用k ，一，玛表示节点x o ，一，x j 的旧密钥t 随机生成相应的新密钥 k7 ，一，玛 4 f o ri 一0t oj d o 令m = k7 朋，一， k ) 肚 8 一 u s e r s e t 五) 一u s e r s e t ( 墨+ 1 ) ) ：m 5 8 一u ： k ，一，为) 七u 2 3 1 3 面向组播组的更新( g r o u p - o r i e n t e dr e k e y i n g ) 面向组播组的更新方式，加密方式与面向密钥的更新方式相同，但是在 发送时它只有一次组播和一次单播。一次组播把所有原组成员所需的更新信 息发送出去，各原组成员可以从这个更新数据包中选择自己需要的部分；一 次单播是用新成员的私钥信息加密所有更新密钥发送给新成员。如在图3 中，将有如下更新： s 一 u 1 ，u 8 ： k 1 9 k l s ， k 7 9 k t s s u 9 ： k 1 9 ，k 7 9 的 面向组播组的更新方式加密代价同面向密钥的更新方式，为2 ( h 1 ) ，而 只需发送两次更新数据包。 2 3 2 成员离开 当组成员要离开组时，同样要首先向组控制器提出申请，被准许后，组 第二章l k h 方案 控制器将删除离开成员的私钥节点，然后更新离开成员私钥节点的父节点到 根节点路径上的所有节点，以保证前向安全。如在图3 中，当u 9 离开时， 我们删除鹚，组成员u 1 u 6 只要将k 1 9 更新为k 1 8 ，u 7 和u 8 需要把 k 1 9 ，k 7 9 更新为k 1 8 ，k 7 8 。成员离开的更新密钥信息的传播方式同样也有三 种。 2 3 2 1 面向组成员的更新( k e y - o r i e n t e dr e k e y i n g ) 每个组成员用自己持有的一个密钥就可以解密自己所需的更新信息。 如图3 中，有如下更新： s 一 u 1 ，u 2 ，u 3 ： k 1 8 k 1 9 s 一 u 4 ，u 5 ，u 6 l： k 1 8 ) k 1 9 s u 7 ： k 1 8 ，k 7 8 r l s u 8 ：( k 1 8 ，k 7 8 k 8 这种方式，需要用每个更新节点的未更新子节点来加密从该更新节点到 根节点路径上的所有更新节点，需要发送( d 1 ) ( | 1 1 ) 个更新数据包，加密 代价为 ( d - 1 ) ( 1 卅2 + h 一1 ) = ( d - 丁1 ) h ( h - 1 ) 2 3 2 2 面向密钥的更新( k e y o r i e n t e dr e k e y i n g ) 这种方式中，每个更新密钥都被新密钥树它的所有子节点加密一次。如 在图3 中，将有如下更新： s 一 u 1 ，u 2 ，u 3 l： k 1 8 k 1 3 s 一 u 4 ，u 5 ，u 6 )： k 1 8 k 4 6 s u 7 ： k 1 8 k 7 8 ， k 7 8 k 7 s u 8 ： k 1 8 k 7 8 ， k 7 8 船 由于更新路径长为( 1 ) ，所以加密代价为d ( h 一1 ) ，发送的更新数据包 同面向组成员的更新一样，也是( d - 1 ) ( h 1 ) 个。算法为： 安全组播密钥更新方案的研究 1 u 一8 ： 离开请求) 屯 2 8 一u ： 离开许可) k 3 8 ： 找出离开点( 即也的父节点) ，从密钥树中删除气，用x j 。表示 氏曾经所在的节点，x 0 为根节点，用x i 一。表示x i 的父节点 ( i = l ，一，j ) ，随机生成节点x o ，。，x j 的新密钥k 0 ，。，玛 4 f o ri - 0t oj d o 对每一个x i 的孩子节点”设节点y 的密钥为k i fy x i 1 t h e n 令m 一 毛) 。， 五。 ，一， k n g u s e r s e t ( 尉：m 2 3 2 3 面向组播组的更新( g r o u p - o r i e n t e dr e k e y i n g ) 面向组播组的更新加密方法与面向密钥的更新相同，只是发送时是将所 有的更新信息用一个更新数据包组播给所有组成员。如在图3 中，有如下更 新： 令厶代表i k l 8 k 1 3 ，i k l 8 k 4 6 ， k 1 8 k 7 8 令l 代表f k 7 8 k 7 ， k 7 8 k s s f u l9o * - 9 u 8 l ：l 0 ，l l 因此，加密代价为d ( h 1 ) ，发送更新数据包为一次组播。 2 4l k h 方案的性能分析 l k h 密钥树与星型( s t a r ) 拓扑结构的集中控制式密钥管理方案相比， 增加了d ( 忉的辅助节点( 设组成员