（信息与通信工程专业论文）自愈式密钥分配的研究.pdf

摘要 摘要 在保密通信过程中，确保通信安全的办法就是不断的分发新的会话密钥。通 信消息经过这个会话密钥加密后传送。对于群组通信，特别是大规模的动态群组 通信中，参与应用的用户可以在任何时间加入或离开由多方用户组成i 侮一个群组。 这种成员关系的动态性使得非法用户很容易地从群组通信中偷听和窃取数据。同 时，在现有的网络环境，尤其是无线网络、无线自组织网络环境下，通信设施容 易被敌手破坏，用户设备的靠电池供电，这就要求在计算开销、存储开销上必须 高效。自愈式密钥分配使得用户能够恢复丢失的会话密钥，无需再向管理员发送 密钥请求，这可以减少网络堵塞，减轻了管理员的负担。本文由此开展了对自愈 式密钥分配的研究工作。 本文首先全面深入地综述了密钥分配技术的相关研究工作，介绍了自愈式密 钥分配的关键技术，总结了其设计模型。在此基础上，提出改进的设计模型，在 性能上进行了比较。自愈式密钥分配的自愈性可以采用容错纠错技术，当前的容 错纠错技术已经不能满足需求。采用多项式秘密共享技术来达到自愈性。共享型 密钥分配模型其广播通信量与最大会话次数和能被删除的最大用户数有关。在增 长型密钥分配模型中，采用增加额外信息的办法来达到自愈的目的，每次广播的 消息都包含了前面的广播消息。如果某次未收到管理员的广播消息时，那么用户 可以利用后面收到的广播消息恢复出丢失的会话密钥，其特点是广播通信量随会 话次数的增加而增加。在迭代型密钥分配模型中，会话密钥通过哈希函数进行迭 代，只有群组中的用户才能通过哈希函数迭代出会话密钥。迭代模型消除了最大 会话密钥的限制，同时广播信息量大大减少，因为在某次广播消息丢失时，不再 向前面的模型那样通过共享信息或额外信息恢复会话密钥，而是通过迭代法恢复 会话密钥。 对于共享型、增长型模型其广播通信量较大，对实际应用环境要求网络要有 较好的通信效率。本文提出通信优化模型将存储开销变为( t + 1 ) l o g q ，通信开销变 为( 2 f + 2 + j ) l o g q ，迭代模型将通信开销变为( t + l + j ) l o g q ，特别适合无线通信的 应用。 关键字：群组通信，自愈，会话密钥，密钥分配 a b s t r a c t o i l em e t h o df o re n a b l i n gs e c u r ec o m m u n i c a t i o ni sp e r o d i cd i s m m i o n o fan 删 k e yt o 即u pm e m b e r s a l lm e s s a g e se x c h a n g e dw i t h i nt h eg r o u p d u r i n gaf i x e di n t e r v a l o rt 姗e ，0 rs e s s i o na r ec o m u n i c a t e d s e c u r e l yt h r o u g he n c r y p t i o nu n d e rt h i ss e s s i o nk e y i ng r o u pc o m m u n i c a t i o ne s p e c i a l l yd y n a m i cg r o u p c o m m u n i c a t i o ni nw l l i d hu s e r sj o i n 0 rm o v eo u t f r e q u e n t l y , a na d v e r s a r yc a l le a s i l yg e ti n f o r m a t i o nw h i c hi sn o te n t i t l e d t o n la n 砌e 1 1 a b l en e t w o r k ，e s p e c i a l l yi nm o b i l ew i r e l e s sn e t w o r k s ，t h ea d v e r s a r y m a v u l t e n n o n a l l yd i s r u p tt h ew i r e l e s sc o m m u n i c a t i o n ，d e v i c e sa l ep o w e r e d b yb a t t e r i e s , i ti s n e c e s s 哪t oa d a p te f f i c i e n tk e yd i s t r i b u t i o ns c h e m ei nt e r mo f m e m o r ys t o r a g e 觚d c o m m 啪c a t i o nc o m p l e x i t y i ns e l f - h e a l i n gk e y d i s t r i b u t i o ns c h e m eu s e r sa r e c a p a b l eo f r e c 0 v e n n g 1 0 s t s g r o u pk e y so nt h e i ro w n ，w i t h o u tr e q u e s t i n ga d d i t i o n 舰1 1 s m i s s i o n s 舶m m e 鲫pm a n a g e r , t h u sc u t t i n gb a c ko nn e t w o r k t r a f f i c ，d e c r e a s i n gt h el o a d0 nt 1 1 e 鲫u p m 锄a g 锄dr e d u c i n gt h er i s ko f u s e re x p l o s u r et h r o u g ht r a f f i ca n a l y s i s a t 虹r s t , t h i sp a p e rc o n c l u d e sp r e v i o u sk e yd i s t r i b u t i o ni n d e t a i l 廿1 g i v e 1 e d e 丘t i o no fs e l f - h e a l i n gk e y d i s t r i b u t i o n a n a l y s i s e ss o m ee x i s t i n gc o n s t r u c t i o n s ，p r e s e n t s n 踟0 0 n s 咖c t i o i l sw h i c hi s m o r ee f f i c i e n ti nt e r mo fm e m o r y s t o r a g e姐d c o m m 姗c a t i o nc o m p l e x i t y e r r o rc o r r e c t i o nt e c h n i q u e si sn o te n o u g h f o ra p p i i c a t i o n h p r e o u sp a p e r , p o l y n o m i a l - b a s e ds e c r e t s h a r i n gt e c h n i q u ei su s e dt 0r e s s i tp a c k e t l o s s i ns h a r i n gs c h e m e ，b r o a d c a s ts i z e i sd e c i d e db ym a xn u m b e r0 fs e s s i o n s a 1 1 d 舢m b e ro fr e v o k e dm e m b e r s i ng r o w i n g s c h e m e ，u s e r sr e c o v e rp a s t 锄d 觚u r e8 e s s i o n k e y s 碱n ga d d i t i o n a li n f o r m a t i o nf i o mt w or e c e i v e db r o a d c a s tm e s s a g e s t h eb r o a d c a s t s l z eg r o w si ft h es e s s i o nc o n t i n u e s 。i ni t e r a t i v es c h e m e ，s e s s i o nk e y i s 舢v a 硝b vt 1 1 e 1 t c m ：t i c co fh a s hf u n c t i o n o n l yi fh ei sam e m b e ro ft h eg r o u p t h ec o n s t m c t i o n e i i m i n a t e dt h el i m i t a t i o no fms e s s i o n si np r e v i o u sa n d r e d u c et h es i z eo fb r o a d c a s ts i z e c o m p a r i n gt ot h es h a r i n gs c h e m ea n dg r o w i n gs c h e m e m s h a r i n gs c h e m ea n dg r o w i n gs c h e m e ，t h eb r o a d c a s ts i z ei s b i g ，s on l en e 呐o r k m u s tw o r k e f f i c i e n t l y i nn e w l yc o m m m u n i c a t i o nc o n s t r u c t i o nt h es t o r a g eo v e r h e a d i s p + 1 ) l o gq ，t h ec o m m u n i c a t i o no v e r h e a di s ( 2 t + 2 + j ) l o gq ，i nn e w l yi t e r a t i v e c o n s 劬c t i o nt h ec o m m u n i c a t i o no v e r h e a di s ( f + l + j ) l o g qw h i c hi sf i tf o rw 砘l e s s a b s t r a c t n e t w o r k s k e y w o r d s ：g r o u pc o m m u n i c a t i o n , s e l f - h e a l i n g , s e s s i o nk e y ，k e yd i s t r i b u t i o n i i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：盔啦日期砷年j 月矿日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：兰她导师签名：恤 日期：刃纠秘月扩e l r 第一章引言 1 1 研究背景 1 1 1 密钥分配相关介绍 第一章引言 随着网络技术的飞速发展，i n t e m e t i n t r a n e t 网络环境下由多方参与的应用正日 益兴起，如视频点播、多媒体视频会议、在线网络游戏、股市交易、计费电视网 络、分布式网络协同工作等。这类应用可以看作是面向开放式网络环境的群组通 信的应用。对于部署在开放式网络环境下的分布式协同应用来说，参与应用的用 户可以在任何时间加入或离开由多方用户组成的一个群组。这种成员关系的动态 性使得非法用户很容易地从群组通信中偷听和窃取数据。因此，分布式网络环境 下的协同应用对安全性提出了要求和挑战，开放式网络环境下群组通信系统的安 全性也显得十分重要。 开放式网络环境下群通信的安全性主要侧重于群密钥分配管理的研究，近年 来国内外学者提出各种群密钥分配管理，研究重点主要集中在降低群密钥管理性 能、提供群密钥分配方案的可扩展性和健壮性以及提高可证明的安全性等几个方 面。群密钥管理必须考虑密钥更新引起的额外的通信、计算和存储方面的开销以 及协议的高效性，可扩展性针对解决大型动态群密钥管理目标提出的，当群成员 规模较大时，群密钥分配方案能够处理好群规模较大时的“1 影响n 问题，提高 群密钥管理的效率，健壮性是将安全的群密钥管理与可靠的群通信服务有效的结 合起来，从而得到安全的、容错的群密钥分配方案；还有学者将容忍入侵技术和 安全群通信系统结合起来，提出容侵的群密钥分配方案；提高可证明的安全性是 迸一步保证密钥管理方案本身安全性的一种方法，也得到了很多学者的研究，如 可验证的门限秘密共享方案等。 支持安全群通信的基本方法是所有群成员共享一个不为非群成员知晓的密 钥，称为群密钥。如何产生、分发这个密钥的过程称为群密钥分配。它是安全群 通信应用的基础，也是攻击者的首选目标。近几年来，一些中外学者对两类群通 信的群密钥分配问题进行了研究一类是静态或小的群组，一类是频繁变化的大的 群组，尤其是后一类有更多的应用场景对于动态的群组的群密钥分配问题( 称为 电子科技大学硕士学位论文 动态群密钥分配) ，关键是要处理群成员的加入或推退出的安全性。当新的成员加 入群时，这个成员应可以立即获得新的群密钥，但不能解读过去的通信密文( 称 后向安全性) ；而当一个群成员退出群组时，不再允许解密以后的通信密文( 称前 向安全性) 。 在可靠的网络通信中，密钥的分配已经得到了好的解决。现行的网络协议 t c p i p 是一种尽力而为的协议，在会话密钥的传输过程中，会话密钥可能丢失， 解决这个问题的方法有重传会话密钥，在消息中携带额外信息。在网络带宽受限， 多个用户像密钥分发中心请求会话密钥势必会造成网络拥塞，在要求安全性高的 环境，可能会暴露目标。在消息中通过纠错技术可以解决某些问题。如果能够根 据前后会话信息恢复出中间过程的会话密钥，这对降低网络拥塞，降低群组管理 员的负荷，系统的安全性带来好处。自愈式密钥恢复在军事应用，商业领域有着 广泛用途。 1 1 2国内外研究状况 公钥密码体制不需要一个安全信道来交换秘密密钥，但由于公钥密钥体制运 行速度比私钥密码体制运行速度慢得多，所以秘密密钥一般用来加密长的消息。 通信中的两个用户如何选择秘密密钥呢? 在实际应用中，建立秘密密钥的方法有密钥分配和密钥共识。它们稍有不同， 密钥分配是一种机制，利用此机制一方选择秘密密钥，然后把它发送给另一方或 许多方。密钥共识是两方或多方通过公开信道来共同形成秘密密钥的协议。在一 个密钥共识方案中，确定的密钥是双方提供的输入的函数。它们的最终目的是参 与的双方都有相同的密钥。 密钥分配就是使它们在协议结束时有相同的会话密钥。如果让密钥分配者为 每个用户随机选择一个密钥在一个脱离了网络的环境下分发给用户，这样用户和 密钥分发者间都要有一个安全信道，并且每个用户都要保存与其余用户的密钥， 这显然不实际。如何保证用户存储的秘密信息总数最少得到了研究人员的重视。 1 1 2 1b io m 密钥预分配 素数p 公开，对每个用户u ，r u z ，公开，吒不同 黝选择三个随机数口，b ，c z 。，f ( x ，y ) = 口+ 6 0 + y ) + c x y m o d p 对每个用户u ，翻计算g u = 厂( 工，r u ) m o d p ，在安全信道上传送g u 给u 2 第一章引言 【，和矿进行通信，则它们的公共密钥足叫= k 咄= 厂( 乇，r v ) 上述是当七= 1 时的密钥预分配方案，可以证明没有一个用户可以确定另外两 个用户的密钥信息。该方案在尼个用户的联合下是安全的，而且是无条件安全的。 1 1 2 2d i 什i e - h e i l m a n 密钥预分配 在此方案中，个用户【，的某些信息将通过铂发送和签名的证书来鉴别。每 个用户有一个c ( u ) = ( i d ( u ) ，b y ，s i g 列( ( u ) ，6 ( u ) ) ，这里= 口m o d p 方案描述为： ( 1 ) - 个素数p 和一个本原元口z ，公开。 ( 2 ) y 计算k 叫= 口钆卸m o d p = 毛“r o o d p ，y 使用了u 的证书中的公开值钆和 自己的秘密密钥a ，。 ( 3 ) u 计算磁矿= 矿脚m o d p = b r “m o d p ，。u 使用了v 的证书中得到的公开值b r 和它自己的秘密密钥a ，。 由于t a 的签名可以防止他人改变其他人证书上的任何信息，因此对于主动攻 击来说是安全的，对于被动攻击的情况，它等价于以下问题： i = ( p ，口，7 ) ，p 为素数，口z ，是本原元，7 z ，计算蛾a 7 m o d p 这是d i f f i e h e l l m a n 问题。事实上，d i f f i e h e l l m a n 问题等价于解离散对数问 题。 1 1 2 3k e r b e r o s 会话密钥协商 前面的密钥预分配方案中，每对用户可以计算出一个固定的密钥来，但是相 同的密钥使用时间太长就有泄露的危险，因此更好的方法是采用在线方法，在每 次通信中产生一个新的会话密钥，这样网络中的任何用户没有必要存储与其它用 户进行通信的所有密钥，会话密钥将由黝传送，黝负责密钥的更新。 k e r b o r o s 1 可以描述为以下几步： ( 1 ) u 要求黝给一个会话密钥与矿进行通信。 ( 2 ) 翻选择一个随机会话密钥髟，时间标记丁和一个使用期三。 ( 3 ) t a 计算，l 。- - e 肋( 足，z d ( v ) ，t ，三) ，所： - e 彤( k ，z d ( u ) ，t ，三) 传送聊，给【厂。 ( 4 ) u 使用解密函数d 岛从，l l 中计算出k ，t ，l ，i v ( v ) ，然后计鸭= ( 仍( u ) ，r ) ， 它将所，鸭发给矿。 电子科技大学硕士学位论文 ( 5 ) v 使用解密函数d x ，从研：中计算出k ，t ，i d ( u ) ，使用呔从鸭中计算出 丁，z b ( u ) ，并检查r ，1 9 ( u ) 对应值是否相同，相同则计算m 4 = 叮+ 1 ) 并将它发送给 。 ( 6 ) u 使用d 。解密m 。并验证结果丁+ 1 。 在以上方案中，当u 收到m 。时，它使用密钥k 来解密它并验证结果时t + i ， 这确保会话密钥k 已经成功传送给了矿。时间标记丁和使用期三可以防止主动攻击 者把存储的消息在以后再次传送。k e r b e r o s 的缺点之一就是网络中的用户将有一个 同步时钟，因为采用时间来判断会话密钥是否有效。 1 1 2 4 自愈式密钥分配 保证通信安全的一个方法是不断的分发会话密钥，在可靠的网络环境下如何 分发会话密钥已经得到了完善的解决，在不可靠的网络环境下，数据包丢失可能 造成信息无法获得，如果管理员重传，就会造成管理员工作负荷太大，特别是在 用户群多的情况下，频繁的发送消息可能会阻塞网络，并且过多的这种消息对高 安全领域是不适用的，如在军事上可能会暴露目标。交互式的密钥在组成员数很 大时已不适用。如何根据现有的网络协议设计出这样的密钥分配方案得到了国内 外研究人员的广泛关注。 广播加密得到了深入研究，发展为不同的方向，主要有r e k e y 模式和具有跟踪 能力的模式。在文献 3 5 ， 3 7 1 ， 4 1 1 ， 4 3 】， 4 4 】对动态群组的r e k e y 模式进行了研究。 在文献 4 7 】， 4 8 1 ， 4 9 1 ， 5 0 l ， 5 1 中讨论了具有跟踪不信任用户的广播模式。 在文章 2 】、 3 】中有两种密钥分配协议能通过非交互的方式抵抗包丢失，它们 采用基于树的密钥分配方法并对随后消息加入附加信息。在文章 2 中采用纠错码 方法，如果在包丢失后能得到固定数量的包即可恢复以前的包。在文章 3 】中采用 增加补丁的方法，可以抵抗有关联包的丢失。通过增加冗余来实现包的恢复必须 在收到足够多的数据包时才有效，并且采用层次式密钥系统，层次式密钥系统式 有状态的，当树中的密钥更新时，离线成员重新加入会被管理者禁止。并且在层 次式密钥系统中，很多密钥被部分用户知道，泄露这些密钥会造成外部人员进入 系统很难跟踪。 在文章【4 】中采用自愈式密钥分配方法，采用自愈式密钥分配方法，一个用户 可以通过广播的方式与其余成员进行通信。由于采用了水平式密钥系统，这便于 4 第一章引言 跟踪，并且用户可以随时离开这个组。该方法能够抵御t 个用户的共谋攻击，有无 条件安全性。该方法将广播通信量从o ( ( m t 2 + t i n ) l o g q ) 变到o ( t 2 + r o t ) l o gq ，采用了 【5 、 6 中的方法来分发新的秘密密钥。由于密钥分配者的广播消息量，该文提出 了将部分计算量移植到用户端的方法。 自愈功能表现为如果用户在第，次会话时为组成员，在第，次会话为组成员， j 五，则第，次会话密钥可以恢复。在减少广播通信量上，通过在用户端采用 伪随机置换的方法生成多项式来实现。在延长个人秘密密钥的使用时间上，一种 方法是从新分配个人密钥来实现，也可以采用在一个循环群上的s h a m i r 密钥共享 方案。该文采用了后者来生成下一个m 次会话的个人秘密密钥。最后，文章讨论 了在最大广播量为6 4 k b 时，m 的大小与t 的变化关系， 该方案设计中用到了信息论中的熵的概念，使整个结构非常简洁。它具有无 条件安全性，能抵制t 个用户的共谋攻击。 在 8 卜一文对 7 进行了补充，它例举了对 7 】构造的一种攻击方法，还有用户因 为丢包而可能被排除的情况。以及用户与它不属于的组联合恢复会话密钥的情况。 该文还提出了一种只需该成员在组中的一次会话就可以得到所有会话密钥的方 法。 在条件设置上，它要求已被撤出用户不能获得任何会话密钥信息，即使它们 可以把所有的个人密钥和以前收到的广播消息放在一起。在其方案的设计中，所 有的操作都发生在有限域c 中，会话密钥、广播的消息、个人密钥都是只上的元 素。通过证明得出个人秘密信息的熵值满足以下不等式，：f s , ) 彻一j 一1 ) l o g q ，j 为会话序号，m 为总的会话次数，s 为第i 个用户的个人密钥。因此个人密钥至少 m l o g q 位，广播信息量为( ( 肌+ + 1 ) f + 咖+ 1 ) ) l o g g 位。该文中设计了一种只需一次 广播消息，就可以恢复以前所有会话密钥的方案。此时其广播信息量为 l b ，i = j l o g q + 2 t j l o g q 。在密钥使用时间上，文中设计了一种可以永久使用的计算 上安全的个人密钥生成方案，其关键思想是建立在拉格朗日插值公式上。 在文献【9 】一文提出了对文献 7 】的改进方法，将个人密钥分配的通信量从 o ( t 2l o g q ) 降到o ( t l o g q ) ，将会话密钥分配通信量从o ( ( m t 2 + t m ) l o g q ) 降到 o ( m t l o g q ) ，将用户的信息存储量从o ( m 2 l o g q ) 降到o ( m l o g q ) ，该文还提出了平衡 广播量和恢复能力的技术。这大大降低了用户的计算开销和存储量，这些技术对 于无线通信的密钥分发非常有利。 在文献 9 】一文中重点考虑在无线网络环境下，如何进行自愈式密钥分配的设 计。在无线应用环境下，用户频繁的加入和撤出通信组，移动设备在计算和存储 电子科技大学硕士学位论文 上的限制等为自愈式密钥分配带来了新的问题。在条件设置上，在 7 】中不允许任 何会话密钥信息的泄露，但在该文中允许知道的最少密钥信息是b 位。它设计出 一种具有前向和后向安全性的方案。 在文献 1 0 】中为无线自组织网络设计了一种更加高效的自愈式密钥分配方案， 该方案将个人密钥空间复杂度控制在( t + 1 ) l o g q 位，广播消息空间复杂度为 ( 2 f + 2 + j ) l o g q 。 基于逻辑密钥层( 1 0 9 i c a lk e yh i e r a r c h y ) 的密钥分配模型在文献 3 6 、【3 7 1 q b 被提 出，它们采用树结构更新会话密钥以便添加和删除用户。在此模型中群组管理员 存储罢导个密钥，每个用户存储l o g 。刀+ 1 个，d 为树的最大度数，q ! e 3 8 e 3 f r d = 2 口一l 为- - y 树。在文献 3 9 】、【4 0 d p j 甬_ 信开销降为( d - 1 ) l o g 。刀。在文献 4 1 】中研究了通 信开销和存储开销的权衡方法。在文献 4 2 1 5 b 采用布尔函数的方法，用户和管理员 都只需要存储l o g 。栉个密钥，缺点是任意两个用户的联合将得到整个系统密钥。 1 1 3 应用前景 军事应用，高安全部门，如军事上，在大规模无线通信条件下，如何保证信 息的安全，各个军事部门不断的变化，结点随时都可能增加，也可能退出。在特 殊情况下，如结点被敌方俘获时，必须把它从网络中撤除，此外在无线设备电量 不足的情况下，结点也应被撤出，在恢复电量时，能够恢复以前的会话信息。 商业上，在商业谈判中，谈判双方同时进行，不同级别的代表可能参与和离 开，密钥需要不断的更新。 另外在付费电视，信息服务等方面也有广泛的应用。 1 2 研究目的与意义 群组通信作为一种大规模信息资源共享的一种方式，如何保证群组通信的安 全性是一个重要问题。群组通信涉及到通信网络、加密算法、身份认证等。对于 大规模的动态群组通信中，其成员的动态变化为安全性带来了新的挑战。同时现 有的网络基础设施、网络协议对可靠的群组通信也是一个严峻考验。 如何设计一个高效率的密钥分配模型得到了研究人员的重点关注，设计一个 适用于特定环境的群组密钥分配模型非常必要。 6 第一章引言 对自愈式密钥分配进行研究，其意义包括： ( 1 ) 分析现有密钥分配的特点，特别是群组密钥分配的设计方法，找出影响密 钥分配设计模型的各因素之间的关系。 ( 2 ) 分析当前的自愈式密钥分配的设计方法，进行对比分析，总结出一般设计 思路，为设计更多更高效的模型奠定基础。 ( 3 ) 对现有的密钥分配设计模型进行分析，设计出比前面设计模型更高效的的 密钥分配模型。 ( 4 ) 根据不同的应用环境，选择不同的密钥分配方法；在给点的应用场景，选 择不同的参数。 1 3 论文主要工作 在信息安全的学习，特别是密码学的学习中，作者对现有自愈式密钥分配了 深入研究和比较分析，这些研究工作主要包括： ( 1 ) 总结保密通信过程中密钥分配与密钥管理。介绍了单钥加密的密钥分 配。对群组密钥的分配进行了分析，对集中式、分布式、分担式群组密 钥分配进行了分析比较。 ( 2 ) 对自愈式密钥分配模型给出形式化的定义，并对其设计模型进行了介 绍。自愈式密钥分配设计到用户的加入、撤离，在丢包情况下能否恢复 出丢掉的会话密钥信息，能否抵御被删除用户的联合攻击。 ( 3 ) 对现有的密钥分配设计模型进行分析，总结出不同的设计模型。从广播 消息的特点将设计模型概括为共享型、增长型、迭代型。 ( 4 ) 根据现有的设计模型，在存储开销、广播通信量上进行改进，设计出更 加高效的设计模型。 1 4 论文章节安排 论文一共分为五章。 第一章，引言。介绍密钥分配的发展与应用，阐述密钥分配特别是大规模群组 密钥分配中的主要问题，简述论文的主要工作。 第二章，自愈式密钥分配技术。介绍了信息论相关知识，组播通信的原理及群 组通信的相关因素。对群组密钥的分配进行了分析，对集中式、分布式、分担式 7 电子科技大学硕士学位论文 群组密钥分配进行了分析比较。 第三章，自愈式密钥分配相关设计。给出了自愈式密钥分配的形式化定义，介 绍了三种设计方案，s t a d d o n 密钥分配、b l u n d o 密钥分配、“密钥分配并对其性能 进行了分析比较。 第四章，自愈式密钥分配模型的构造研究。针对当前的设计模型的特点总结出 三种设计类型，并对当前的设计模型进行改进，提出更加有效的设计模型。 第五章，总结本文的主要内容，提出未来主要的研究方向。 第二章自愈式密钥分配技术 第二章自愈式密钥分配技术 本文在第二章对现有的密钥分配技术进行了总结，分析了现有的群组密钥分 配的三种类型。为了解决群组密钥特别是大规模群组密钥分配过程中群组成员的 加入，删除引起的密钥更新以及容错要求，本章提出了自愈式密钥分配的相关技 术及设计模型。 本章的安排如下：第一节，提出信息论中相关概念；第二节，介绍组播通信 的原理及安全组播的因素；第三节，介绍群组密钥分配的三种类型：第四节，对 本章进行小结。 2 1相关知识 2 1 1 信息论基础 2 1 1 1 信息量 对于离散信源而言，信源在某时刻输出的符号是随机的。在任何给定时刻， 信源到底会发出什么符号，接受者事先是不知道的，存在不确定性。对于接受者 而言，收到信息后就可以消除或者减小这种不确定性，由于干扰存在，这种不确 定性不能完全消除，但是信源各符号出现的概率大小是确定的。信源是由概率空 间描述的，信源一定，那么概率分布就一定，反之亦然。概率大小决定了信息量 的大小，那么信息到底如何度量呢? 定义2 给定信源x 的概率空间瞄m 苏嘉 剐卟x 的 自信息量定义为 i ( a 。) = - l o g p ( a ，) = 1 0 9 ：妥 ( 2 1 ) 自信息量的单位与所选取对数底数有关。在信息论及相关学科中常取底为2 ， 此时信息量的单位为比特：如果取自然对数( e 为底) ，则单2 位为笛特。 自信息量是该符号出现后提供给接受者的信息量。此外，它还表示信源符号 9 电子科技大学硕士学位论文 的先验证不确定性。对于给定信源，每个符号具有一个先验概率，在信源符号发 出之前存在不确定性。一个出现概率很小的符号，接受者事先很难猜测它是否会 发生，而概率很大的符号，出现的可能性大，很容易猜测它的出现。符号的不确 定性在数量上等于它的自信息量。但两者含有不一样。先验不确定性是信源符号 固有的，而自信息量是信源发出后该符号为接受者提供的信息量，是接受者为消 除该符号不确定性需要获得的信息量。 2 1 1 2 互信息量与条件互信息量 设信源y 的符号取自事件集合召= 6 l ，6 2 ，包) ，相应的概率空间为 p ， = p 刍，p 瓮，：p 复， 满足喜p c 岛，= ，对y - x , y 构成的联合空间，共有 r x s 种取值组合，联合概率空间可以表示为 i x y ll ( a i6 1 ) ( 口l ，包) ( a r9 包) l 【p ( x ，y ) j 【- p ( a ，6 1 ) p ( 口，么) p ( a ，吃) j 根据概率论的知识可知 p ( a ，b ) = p ( b j ) ，j = l ，2 ，j ；p ( 口。，岛) = p ( q ) ，i = 1 ，2 ，； p ( a ，b j ) = 1 事件口i 发生的情况下，事件包出现的条件概率为p 哆t a ，) ；事件包发生的情况下， 事件口。出现的条件概率为p ( 口ji b m ) ，概率之间的关系如下： p ( a i ，屯) - - = p ( a 。) p ( 吃la ；) = p ( 包) p ( 口ii 包) p ( b jl 口j ) = 锗， m ，i b m ) = 帮 1 0 第二章自愈式密钥分配技术 定义2 2 对于给定的两个信源x ，】，对应概率空间分别为 嘲也a i 加魄a 2o 。a e t ， 黝= p p 麓， 事件包y 的出现给出的关于事件口j x 的信息量，( q ；吃) 为 地；妒1 。g 掣 ( 2 2 ) 同样，( 口，；包) = l 。g _ p ( 页b 矿la f ) 定义为事件口，x 的出现的关于事件包，的信息量a 可以证明下列等式成立： l ( b j ；a 。) = i ( a 。；屯) ( 2 3 ) 事件口，x 与事件吃y 之间的互信息量之所以存在是因为两者之间存在相关。如 果两者相互独立，则由于p ( 口，b j ) = p ( a ，) p ( 吃) ，因此，( 口f ；i ) = 0 。互信息量的意 义表示了事件之间的关联性。如果事件包的出现有利于事件口，的出现，那么 i ( a ；屯) o ，如果事件吃的出现不利于事件口，的出现，那么，( q ；包) 0 ，所以 i ( a ，；包) 可正可负，也可为0 。 定义2 3 给定联合概率空间 i 腰ii a t b t口。6 2 ab , l l p ( x ，y ) j 【p ( a 。，6 1 ) p ( 口1 ，6 2 ) p ( a ，以) j 对于事件a 。x 在事件b ，y 的j 条件自信息量定义为 i ( a ，l6 ，) = 一l o g p ( a ，l6 ，)( 2 4 ) 条件信息量，( 口。i6 ，) 是在事件6 ，给定的条件下，关于事件口；的不确定性，当 ( 口，l6 ，) 较大时，则给出的关于事件a 。出现保留较大的不确定性，反之较小。直观 的解释为，设a i 为信源发出的符号，6 ，为接收的符号，如果，( ql6 ，) 较大，则 p ( a ，l6 ，) 较小。从译码角度而言，p ( a ，i6 ，) 越小，在接收为6 ，的条件下，信源发出 的符号为口，的可能性越小，所以关于事件a i 保留的的不确定性越大；反之，如果 ( 口，i6 ，) 较小，则p ( ql6 ，) 较大，接收到符号包后，信源发出的符号为a ，的可能性 电子科技大学硕士学位论文 越大，接收到符号包后，信源符号口剩下的不确定性变小。 定她4 给定联合概率空间已昌， 已魏，p 鑫二矗， ，对于事件 口，j 与事件包y 的联合自信息量定义为 ，( 哆，包) = 一l o g p ( a ，包) ( 2 5 ) 联合自信息量表示事件口。x 与包y 同时出现的先验不确定性。如果x ，y 表示信 源连续输出的两个符号，那么联合自信息量表示信源符号先后输出符号对g ，岛提 供信息量。 2 1 1 3 信源熵 自信息量i ( a ，) 反映了信源单个符号的先验不确定性，或者信源输出某个消息 所包含的信息量，即信源单个消息符号信息量的大小。信源输出的消息不同，各 个消息符号对应的概率不同，即信源单个消息符号信息量的大小。信源输出的消 息不同，各个消息符号对应的概率不同，所包含的信息量也就不同，所以它反映 的只是具体输出消息符号的特性，不能反映信源的总体特性，也不能够作为信源 的信息度量，只是单个符号的信息度量。 定义2 5 自信息量的数学期望为信源的平均自信息量，也称为熵。 l 日( 功= 研i ( a ，) 】- 一p ( a ，) l o g p ( a ，) ( 2 6 ) 1 - - i h ( x ) 表示随机变量x 的熵，不是表示随机变量x 的函数。( z ) 描述了系统的 无规律程度，即在给定时刻系统可能出现的有关状态的不确定性程度。 在信息论中，h ( x ) 表示信源的先验平均不确定性。在消息符号输出之前，表 示确定信源x 所需要的平均信息量，或者在发出消息符号后，表示每个输出消息 符号所给出的信息量平均值。信源的熵日( 工) 反映的是信源的总体特性，信源的统 计特性不同，信息熵也不同。给定信源，相应的概率空间给定，信息熵就确定了。 如果信源符号不同，但是具有相同的统计特性，那么信息熵也是相同的，也就是 说信息熵的值与符号的形式没有关系，与符号的排列顺序也没有关系，只取决于 信源的总体统计规律。 2 1 1 4 条件熵 定义2 6 在联合集( x y ) 上，定义条件自信息量的数学期望 1 2 第二章自愈式密钥分配技术 h ( x i 】，) = 研讹，i 岛) 】一p ( a ，b j ) l ( a ，l 色) ( 2 7 ) i - 1 - l 为集合y 相对于集合石的条件熵。特别地，当彳，y 相互独立时，有 h ( xi 】，) = 日( x )( 2 8 ) 2 1 1 5 联合熵 定义2 7 在联合集合 x ，聊上，定义每对元素 口，6 ，) 同时出现的联合自信息量的 数学期望h ( x y ) = e i ( a ，6 ，) ) 为联合熵，也称共熵。 根据i ( a ，b ，) 的定义，可以得到联合熵的计算公式 h ( x y ) = 一p ( a ，b i ) l o g p ( a ，乃) ( 2 9 ) i = l i = l 联合熵表示了事件x ，y 同时发生的不确定性。对于通信系统而言，如果集合x 表 示信源输出符号，y 表示信宿接收符号，由于信道干扰的存在，输出符号与信宿收 到的符号之间并非一一对应，x 与】，之间都存在不完全一致的不确定性，联合熵 日( 就是彳，】，之间的联合不确定性。 2 1 1 6 交互熵 定义2 8 在联合集 彳，y ) 上，定义互信息量，( 口，；岛) 的数学期望 i c x ；r ) = e ，( 口，；包) ) = p ( a ，b j ) i ( a ，；t ) ( 2 1 0 ) i = 1j - - i 为集合x ，】，之间的平均互信息量。 l ( x ；r ) 的意义就是由集合】，获得的关于z 的平均信息量， 互信息，或者称为平均交信息量或者交互熵。 根据互信息量的定义可以推导出i ( x ；y ) 的计算公式如下： 旭= 喜喜p c a i , b j g 掣 即平均互信息量，简称 ( 2 1 1 ) 互信息量，( x ；即与信息熵h ( x ) 、日( 1 9 和条件熵h ( x i 聊、h ( y i z ) 之间的关系 如下： ，( x ；d = h ( x ) 一h ( xl 聊= h ( y ) 一日( 】，lx ) 因为( x ；y ) = i ( y ；x ) ，i ( x ；y ) 0 ，容易得到h ( x ) h ( xy ) ，当且仅当x 与】，相 互独立时，等式成立。 电子科技大学硕士学位论文 给定三个随机变量彳，】，z ，在给定z 的情况下，x 与】，的互信息量 i ( x ；rz ) = h ( xz ) 一h ( xiz y ) = h ( yz ) 一h ( yz x ) = i ( y ；xz ) 因为条件互信息量i ( x ；rlz ) 非负，因此有h ( xlz ) h ( x1z y ) 2 1 1 7 熵的链式法则 定理3 1 设随机变量墨，x 2 ，x 。服从p ( 五，x 2 ，x 。) ，则有： 日( 五，互，以) = 日( 墨i 五- 1 一，五) ( 2 1 2 ) 2 1 2 有限域基础 2 1 2 1 有限域的定义 有限集合f 上定义了两个二元运算：加法“+ 和乘法“，如果( ，+ ) 是 交换群，f 的非零元素对乘法构成交换群，而且乘法对加法满足分配律，则称 ( ，+ ，- ) 是有限域。 2 1 2 2 有限域的乘法群 任意有限域的非零元构成的乘法群巧为循环群，并称c 的生成元为的 本本原元。反之，设，是域，若，的乘法群c 是循环群，则f 是有限域。 2 1 2 3 有限域上的多项式 有限域f 上定义的多项式集合 f ( x ) = 厂( 力l 厂( 功= 口x ”+ + 口i x + a o ，a l f ，a 。o , n 0 令g ( z ) ，j i l ( z ) 分别为k 次和，次多项式， g ( x ) = 口i x + + 口l x + a o ，a i 0 h ( x ) = 6 ，工+ + 6 l z + 钆，岛0 在f ( x ) 上定义标准的加法和乘法： 1 4 第二章自愈式密钥分配技术 m w - x ( 1 , k ) g ( x ) + j i l ( x ) = ( 口+ 6 j ) 工 f = 曲 k + l g ( 工) j l ( 石) = ，其中c i - a 。b o + a h b l + + 口o b l 。 f 罩o ( f ( x ) ，+ ，) 是有限域f 上的多项式环。 2 1 3 密钥分配 两个用户( 主机、进程、应用程序) 在用单钥密码体制进行保密通信时，首 先必须有一个共享的秘密密钥，而且为防止攻击者得到密钥，还必须时常更新密 钥。因此密码系统的强度依赖于密钥分配技术。两个用户a 和b 获得共享密钥的 方法有以下几种： ( 1 ) 密钥由a 选取并通过物理手段发送给b ； 安全性高，这是人工发送的方式，避免了密钥在网络传输中被截获或纂改的 可能。 通信开销，若只是个别用户想进行保密通信，密钥的人工发送还是可行的。 但对于用户量大的情况不适用了。因为每对用户之间都必须有一共享密钥。如果 有n 个用户，则密钥数目为n ( n 1 ) 2 个，当1 1 很大时，密钥分配的代价非常大，密 钥的人工发送是不可行的。 ( 2 ) 密钥由第三方选取并通过物理手段发送给a 和b ： 同第一种方式相比，只是多了一个第三方，第三方必须是a ，b 可信的，第三 方和每个用户之间有一个安全信道，每个用户必须存储n 1 个密