（应用数学专业论文）安全群通信的密钥管理协议.pdf

中文摘要 中文摘要 近年来，安全可靠的群通信已成为研究领域的热点问题，尤其是在 基于群的应用和合作领域，群通信越来越受到人们的关注。设计安全有效 的密钥管理协议面临着重大挑战。其难点在于群的动态性，即群成员可 以在任意时刻加入或退出群。 对于动态对等群，y o n g d e ak i m 等人在 1 中提出了s t r 密钥协商 游议。本文通过运用p a i r i n g 与密钥树结合的方法，推广了s t r 协议， 提出了一个简单、容错、安全的三方密钥协商协议。此外，本文还分析 和讨论了新协议的通信开销和计算开销，并证明了其对于抵抗恶意窃听 和针对群的其它攻击的安全性。 关键词：群密钥协商群通信双线性问题 配对密码协议 中文摘要 a b s t r a c t i nr e c e n t y e a r s ，s e c u r ea n d r e l i a b l e g r o u p c o m m u n i c a t i o ni s a l l i n c r e a s i n g l ya c t i v er e s e a r c ha r e ab yg r o w i n gp o p u l a r i t yi ng r o u p - o r i e n t e da n d c o l l a b o r a t i v ea p p l i c a t i o n o n eo ft h ei m p o r t a n tc h a l l e n g e si st od e s i g ns e c u r e a n de f f i c i e n tg r o u pk e ym a n a g e m e n t t h ed i f f i c u l t yo ft h i sp r o b l e mi sd u et o g r o u pd y n a m i c s y o n g d e ak i me ta 1 p r e v i o u s l yp r o p o s e ds t rp r o t o c o li np a p e r 【1 1 i n t h i s p a p e r ，w ee x t e n d t h es t rp r o t o c o l b yb l e n d i n gp a i r i n g - b a s e d c r y p t o g r a p h yw i t hk e yt r e e s i ty i e l d s as e c u r ep r o t o c o ls u i t et h a ti sb o t h s i m p l ea n df a u l t t o l e r a n t f u r t h e r m o r e ，w ed i s c u s sa n da n a l y z et h en e w p r o t o c o ls u i t e sc o m m u n i c a t i o na n dc o m p u t a t i o n a lc o s ta n dp r o v e i t ss e c u r i t y a g a i n s th o s t i l ee a v e s d r o p p e ra sw e l la sv a r i o u s o t h e ra t t a c k ss p e c i f i ct og r o u p s e t t i n g s k e yw o r d s ：g r o u pk e ya g r e e m e n t g r o u pc o m m u n i c a t i o n b i l i n e a r d i f f i e - h e l l m a n p a i r i n gc r y p t o g r a p h i cp r o t o c o l 绪言 绪言 随着i n t e r n e t 网络技术的迅速发展，出现了诸如多用户参加的视频 音频会议，网络游戏等基于群的应用。安全可靠的群通信因此成为研究 的热点。设计安全、有效的密钥管理机制面临着巨大的挑战。其难点在 于群的动态性，即群成员可以在任意时刻加入或退出群。由群动态性而 产生的问题是当新成员加入群时，这个成员又立即获得新的群密钥，但 不能解读过去的通信密文( 也称后向安全性) ；而当一个群成员退出群时， 不再允许解密以后的通信密文( 后向安全性) 。 一般说来，群密钥管理协议大致分为两类：分布式管理( 密钥协商) 和集中式密钥管理( 密钥分配) 。在密钥协商协议中群密钥由加入群的成 员共同产生，在密钥分配协议中群密钥由中心服务系统产生和分发。动 态对等通信是一种较复杂的群通信方式。然而，集中式密钥管理并不适 用于动态对等群，许多动态对等群需要分布式密钥管理。 从传统的通信服务到分布式服务的改变是当前基于群应用的发展趋 势。这种基于群的分布式协作的应用同样需要安全服务。而实现这些安 全服务的，建立一个共享的群密钥是其关键。于是，人们提出了群密钥 的协商协议c 1 8 2 6 。群密钥协商协议与传统的集中式群密钥管理机制 2 ，3 , 4 不同，它没有中心密钥服务器，群共享的密钥由所有群成员通过 对等协商约定，具有分布武、协作、动态等新特征。 十年前对群通信密钥管理的研究只局限于静态的群组或集中式密钥 管理，对频繁变化的动态对等群( d p g ) 的分布式密钥管理问题，只是 近年来才涌现出了一些方法。分布式密钥管理有两种趋势：1 运用密钥 树有效地产生和更新群密钥。2 椭圆曲线密钥交换协议来实现可证明安 全的密钥协商协议。本文的主要工作是将这两种趋势结合起来，通过将 1 黑龙江大学硕士掌位论文 s t r 协议推广到三方通信，提出了一个基于p a i r i n g 的简单、容错、安全 的密钥协商协议的设计方案。 另外，对于动态对等群，通信开销和计算开销是密钥管理首先要考 虑的重要因素。本文分析和讨论了新协议的通信开销和计算开销，并证 明了其对于抵抗恶意窃听和针对群的其它攻击的安全性。 下面的章节将对群通信密钥管理作深入的探讨。本文在第一章介绍 了密码学的相关理论并从总体上介绍群通信密钥管理。第二章对动态对 等群的密钥管理方案进行深入的研究，选择当前几种有代表性的对动态 对等群的密钥管理方案进行介绍，并就其通信性能进行比较。第三章推 广了s t r 协议，提出了一个基于p a i r i n g 的简单、容错、安全的三方密钥 协商协议的设计方案。第四章证明了新协议的安全性，并将s t r 协议与 之进行性能分析和比较。第五章总结全文并用发展的眼光，从纵向提出 分布式密钥协商协议的发展思路和发展方向。 第1 章密码学相关理论 第1 章密码学相关理论 1 1 协议以及其攻击方法 所谓协议( p r o t o c 0 1 ) 就是两个或两个以上的参与者为完成某项特定 的任务而采取一系列步骤。这个定义包含三层含义： 第一，协议自始至终是有序的过程，每一步骤必须依次执行。 在前一部没有执行完之前，后面的步骤不能执行。 第二，协议至少需要两个参与者。一个人可以通过执行一系列 的步骤来完成某项任务，但它不构成协议。 第三， 通过执行协议必须能够完成某项任务。 安全协议与许多通信协议的显著区别在于它使用了密码技术。在进 行密码协议的设计时，常常要用到某些密码算法。密码协议所涉及的各 方可能是相互信赖的，也可能彼此互不信任。当成千上万的用户在网络 上进行信息交互时，会给网络带来严重的安全问题。例如，非法用户不 必对网络上传输的信息解密，就可能利用网络协议自身存在的安全缺陷， 获取合法用户的某些机密信息( 如用户口令、密钥、用户身份号等) ，从 而冒充合法用户无偿使用网络资源，或窃取网络数据库中的秘密用户文 档。因此，设计安全、有效的通信协议，是密码学和通信领域中一个十 分重要的研究课题。密码协议的目标不仅仅是实现信息的加密传输，而 更重要的是为了解决通信网的安全问题。参与通信协议的各方可能想分 享部分秘密来计算某个值，生个某个随机序列，向对方表明自己的身份 或签订某个合同。在协议中采用密码技术，是防止或检测非法用户对网 络进行窃听和欺骗攻击的关键技术措施。所谓协议是安全的，意味着非 法用户不可能从协议中获得比协议自身所体现出的更多、更有用的信息。 黑龙江大学硕士学位论文 因此，一个好的协议应该具有以下特点： 1 协议涉及的每一方必须事先知道此协议以及要执行的所有步 骤。 2 协议涉及的每一方必须同意遵守协议。 3 协议必须是非模糊的，对协议的每一步都必须确切定义，力求 做到避免产生误解。 4 协议必须是完整的，对每一种可能发生的情况都要作出反应。 5 每一步操作要么由一方或多方进行运算，要么是在各方之间进 行消息传递，二者必居其一。 在分析协议的安全性时，常用的方法是对协议施加各种可能的攻击 来测试其安全度。 密码攻击的目标通常有三种： 1 攻击协议中采用的密码算法； 2 攻击算法和协议中采用的密码技术； 3 攻击协议本身。 本文只考虑对协议自身的攻击，而假设协议中所采用的密码算法和 密码技术均是安全的。 对协议的攻击可分为被动攻击和主动攻击： 被动攻击是指协议外部的实体对协议执行的部分或整体过程实施窃 听。攻击者对协议的窃昕并不影响协议的执行，它所能做的是对协议的 消息尽可能地观察，并试图从中获得协议中涉及到各方都要某些消息。 他们收集协议各方之间传递的消息，并对其进行了密码分析。这种攻击 实际上属于一种唯密文攻击。 主动攻击是攻击者试图改变协议执行中的某些消息已达到获取信 息、破坏系统和获得对资源的非授权的访问。他们可能在协议中引入新 第1 章密码学相关理论 的消息、删除消息、更换消息、重发就消息、干扰信道和修改计算机中 存储的信息。 1 2 群通信和群的密钥管理 1 2 1 群通信 随着i n t e r a c t 网络的飞速发展，一些传统的通信服务转移到网上。出 现了许多基于群合作的应用。例如视频声频会议，网络娱乐游戏，消息 发布，股票报价，文件共享等。对于相应的安全机制( 如保密性、数据 完整性、可靠性) 的要求也日益突出，安全可靠的群通信因此成为近年来 研究的热点 2 2 - 2 6 。 安全群通信( s g c ) 是指群成员之间可相互发送和接收消息，而非群 成员即使在截获部分信息后，也无法从中摄取真正有用的消息。群通信 的安全性对于构建动态对等群网络环境下的分布式应用至关重要。在安 全群通信中，通信层往往用于处理异步网络行为，保证可靠的消息传输。 从而为上层提供高度可靠的群通信服务。当前，安全群通信面临的挑战 是如何设计一个安全高效健壮和可扩展的群密钥管理协议，其目的是使 所有群成员共享一个不为非群成员所知道秘密密钥( 称为群密钥) ，如 何产生、分发这个群密钥的过程称为群豹密钥管理。群密钥管理是其他 群通信安全业务( 如信息的保密性、可用性和完整性) 的前提，也是攻 击者的首选目标。 1 2 2 群密钥管理 群密钥的生成往往通过密钥建立协议来实现。总体上，密钥建立协 议可分为两类：基于某一可信第三方的集中式密钥管理( 也称密钥分配) 一5 - 黑龙江大学硕士学位论文 2 , 3 ，4 和分布式群密钥管理( 也称密钥协商) 1 8 2 6 。 1 集中式密钥管理( 也称密钥分配) 在集中式协议中只有一方( 可信任的第三方或某个群成员) 控制着 整个群，它不需要依赖于任何辅助方法来进行密钥管理，密钥分发过程 比较简单。群的保密性依赖于群的控制器的正常工作，如果控制器失败， 就不能正常地进行密钥生成和分发，群的保密性也无法保证。另外，如 果群较大，一个控制器就很难进行管理，有可能成为性能的瓶颈，这将 造成可扩展性问题。而动态对等群中可能不存在可信第三方，而且群的 动态性决定了经常需要进行密钥更新，因此集中式协议无论是在安全性 方面还是在性能方面都不能满足动态对等群的要求。 2 分布式群密钥管理( 也称密钥协商) 分布式协议要求每个群成员平等地提供一个随机的密钥数值，群密 钥k 是所有密钥数值函数，可以表示成，以，) ，其中，是一个单向函 数，是第i 的成员提供的随机秘密数值，群密钥罔狗计算方法必须满足： 1 每一个提供数值的成员都能计算出k 。 2 在不知道，的情况下，不能得到有关爱的任何信息。 3 所有t 是保密，以便在后续的密钥协商中重复使用。 显然，分布式协议能够避免集中式协议中的可信第三方( 通常易遭 受攻击) 和单点故障问题，可以获得较好的可扩展性和容错能力，同时 也与动态对等群的特点相吻合。因此，动态对等群中的密钥管理一般采 用密钥协商协议。 协议的性能则取决于密钥的构成方式( 即群成员在密钥协商时形成 的通信网络的拓扑结构) ，可以分成环形和树型两类。 第1 章密码学相关理论 早期提出的密钥协商协议大多是基于环的，在这些协议中，1 个成员 按序号组成环，他们共享一个大素数( 坷和口) ，分别独立产生一个秘密值 并计算中间值。然后，把这些中间值按环的方向传递给相关的成员，最 后每个成员都能根据自己在环中所处的位置，利用这些中间值以及自己 的秘密数值计算得到群密钥。不同的协议在消息传递和群密钥的具体计 算方法上会有不同，这就决定了它们的通信开销和计算开销的存在区别。 基于环的协议的计算开销和通信开销随着成员数目的增加而线性增 长，因此可扩展性较差。为了解决可扩展性问题，基于树的协议应遥而 生。其核心思想是把群密钥管理中的两种重要趋势统一起来。使用密钥 树来高效的计算和更新群密钥，使用d i f f i e h e l l m a n 密钥交换来实现具有 可证明安全性的分布式协议。 安全高效的密钥协商机制是保证动态对等群通信系统安全性的关 键，也是动态对等群安全群通信系统能否成为开放式网络环境下的各种 协作式应用的通信框架的决定性因素。 本文主要研究适用于动态对等群的分布式密钥协商协议，其特点是成 员数目较少而且是对等的，不存在层次结构，可以遍布在i n t e r n c t 上，而 且成员关系是动态变化的。 1 3 安全密钥协商的密码学性质 一个实用的群密钥协商协议必须能够高效处理群成员关系的变化，而 且能够抵抗各种被动攻击和主动攻击。它应该具备的安全属性包括：密 钥安全性、前向安全性、后向安全性、密钥独立性、能够抵抗中间人攻 击和已知密钥攻击。安全密钥协商的一个重要安全要求是密钥更新。为 了确保群密钥的安全性和防止旧的群密钥的重新应用，定期的群密钥更 黑龙江大学硕士掌位论文 新是十分必要的。 密钥协商协议设计时还要考虑如下因素的影响： 可扩展性：可扩展性也是密钥协商协议所需要考虑的重点。随着群 规模的扩大，保存密钥所占的存储空间、密钥生成所需的计算开销密钥 更新时间的延迟和密钥更新的频率都会相应增加。 健壮性：对于单个来说，通信的任何一方失败都会使会话终止，而在 动态对等群中，部分群成员的通信失败不应当影响到整个群的会话继续 进行。这就对动态对等群的密钥管理推出了健壮性的要求。 可靠性：动态对等群密钥管理的控制消息( 包括密钥更新消息新成 员关系变动的通知等) 通常利用不可靠的广播进行传输。这种传输存在 丢失乱序重复等情况。如果缺乏确保可靠性的机制，一个群成员没有收 窭| 密钥更新消息，他将无法参与后继的群通信。 我们把动态对等群密钥协商协议所需要解决的基本问题归纳如下： 安全密钥协商具有4 个安全性质：假设一群密钥已被更新m 次，连续 的群密钥序列为k - k o ，j 0 1 群密钥安全性：对于一个被动攻击者计算k k ( v i e i , m ) 是计算上 不可行的。 2 前向安全性：对于一个已知原群密钥连续子集 ，k ) 的被动攻 击者，不能获得任何后面的群密钥k ，( pf ) 。 3 后向安全性：对于一个已知原群密钥连续子集 k ，k i ) 的被动攻 击者，不能获得任何前面的群密钥k ，( fcit ，) 。 4 密钥独立性：对于一个已知群密钥子集必c k 的被动攻击者，不能 获得任何其他的群密钥k + ( k k 。) 。 r 第1 章密码学相关理论 由上述定义可知这4 个的安全性质的关系是显然的。前向安全性和后 向安全性都包含群密钥安全性，密钥独立性包含了其它三条安全性质。 同时，前向安全性和后向安全性一起构成了密钥独立性。 注释 1 上述定义的密钥的安全性允许部分信息的泄漏。因此可确保群密钥 任意比特的不可预测性。 2 用判定群密钥安全性来确保对一个被动攻击者能区分任意群密钥和 任意一个随机变量是计算上不可行的。 3 本文中所定义的前向安全性和后向安全性比 5 ，2 3 中定义的条件更 强。 前向安全性定义为新的群成员不能获得以前的群密钥。 后向安全性定义为原来的群成员不能获得当前和以后的群密钥。 与 5 ，2 3 不同之处在于攻击者主要是指当前和原来的群成员，而本 文中的定义还包含了群密钥不经意泄漏的情况，我们将文中的定义 分别称作弱前向安全性和弱后向安全性。 4 但我们不把密钥的可靠性作为密钥管理协议的一部分。假设所有通 信信道是公开的但是可靠的，即假设在发送消息前发送者先将消息 进行某种数字签名( 例如d s a 和r s a ) ，接收者在接收到消息后需 验证签名。 1 4h a s h 函数 h a s h 函数h 是将任意长的消息m 压缩成某一固定长度的消息摘要的 函数。设输出消息摘要为日，称h = 矗似j 为m 的h a s h 值或散列值。 一个强碰撞自由的h a s h 函数是一个满足下列条件的一个函数： 1h 的输出可以是任意长度的任何消息或文件； 9 黑龙江大学硕士学位论文 2h 的输出的长度是固定的； 3 给定h 和m ，计算 阳j 是容易的； 4 给定i l ，找两个不同的消息肌，m ：，使得 ( ，1 1 ) t h ( m ：) 是计算上不 可行的。 一个强碰撞自由的h a s h 函数暗含着单向性，所以强碰撞自由的 h a s h 函数又称强单向h a s h 函数。在密码学中，强单向h a s h 函数通常 被认为是安全的h a s h 函数。h a s h 函数应用范围广泛，可用于数字签名， 消息的完整性检测，消息的起源认证检测等。在本文所提出的密钥协商 协议中引入了h a s h 函数，能够弥补s t r 协议容易遭受中间人攻击的不 足，从而确保了协议的安全性。 1 5 数字签名 数字签名顾名思义，是一种以电予形式给一个消息签名的方法。数 字签名与传统的手工签名相比一般具有以下几个特点： 1 数字签名方案必须设计把签名“绑”到所签文件上。 2 数字签名方案能通过一个公开的验证算法来验证，这样，任何人均 可验证一个签名，以阻止伪造签名的可能性。 3 数字签名易被拷贝，这就要求消息本身包含诸如日期等信息来达到 所签信息具有新鲜性的目的。 一个数字签名方案至少应满足以下三个条件： 1 签名者事后不能否认自己的签名； 2 接收者能验证签名，而任何其他人都不能够伪造签名； 3 当双方关于签名的真伪发生争执时，第三方能够解决双方之间发生 的纠纷。 第1 章密码学相关理论 一般地，一个数字签名方案主要由两个算法，即签名算法( s i g n a l g o r i t h m ) 和验证算法( v e r i f y a l g o r i t h m ) 组成。签名者可以使用一个 秘密的签名算法s i g ( ) 签一个消息x ，而生成的签名s i g ( x ) 可通过一个公 开的验证算法v c r ( - ，) 来验证，其值是“真”或“假”。一个数字签名方 案可由五元组( p ，爿，k ，s ，y ) 来描述： 1 p 是一切可能的消息组成的一个有限集合。 2 一是一切可能的签名组成的一个有限集合。 3 k 是所有可能的密钥组成的有限集合，即密钥空间。 4 对每一个k e k ，有一个签名算法s i g t ( ) e s 和唯一的一个相对应的 验证算法v e r i ( ，) y ，k e k 。其中s i g g ) ：p a ，v e r t ，( ，) ： p x a 一( 真，假) ， 是满足下列条件的函数： 对每一个消息x e p 和每一个签名yc a ， v e r t ，( x ，) ，) = “真”y s i g o ) 。 注释 1 讹，k e k ，s i g 。( ) 与v e r k ( ，) 都是多项式时间函数。 2 s j 猷) 是保密的，而v e r k ，( ，) 是公开的。 3 敌手伪造签名者对x 的签名，在计算上是不可行的。 由于与传统手工签名相比，数字签名具有非常突出的数字化优势， 因此在该技术被第一次提出之后，它便受到了广泛的关注和重视。目前 关于数字签名的研究主要集中于对公钥密码体制的数字签名的研究。相 应地，各种具体的签名方案也大量涌现，如r s a 方案【6 】、e 1 g a m a l t 亨案【7 】、 数字签名标准d s s 8 等等，有关签名算法的综合性介绍可参见【9 1 1 】。 黑龙江大学硕士学位论文 1 6d 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 9 7 6 年发表的论文“密码学的新方向( n e wd i r e c t i o n i nc r y p t o g r a p h y ) ” 1 2 是密码学发展史上的一个重要的里程碑。第一次 介绍了公钥密码的思想。此外，在论文中，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 密钥交换思想。 假定p 是一个素数，g 是z 。的一个本原元，p 和g 是公开知道的。 d i f f i e h e l l m a n 密钥交换协议可描述为： 1 a 随机地选择a ，0 a a p - 2 ； 2 a 计算g “( r o o d p ) ，并发送给b ； 3 b 随机地选择a 口，0 a 口s p - 2 ； 4 b 计算g “( m o d p ) ，并发送给a ； a 计算k 一( g “) “( m o d p ) ，b 计算k - ( g “p ( 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 假 设。d i f f i e h e l l m a n 密钥交换协议的不足之处是该协议容易遭受中 间入侵攻击。 一个主动攻击者o s c a r 进行中间入侵攻击的基本模式为： a l i c eo s c a r b o b 随机选择吒e 竺一 随机选择以业二 五二l c l随机选择口口 中间攻击者o s c a r 伪装成a l i c e ( b o b ) 和b o b ( a l i c e ) 进行密钥协 商，最终a l i c e 和b o b 都共享一个密钥，从而可任意伪造、修改、截留a l i c e 第1 章密码学相关理论 和b o b 之间的通信。 1 7 椭圆曲线密码体制及椭圆曲线d i f f i e h e l l m a n 问题 椭圆曲线应到密码学上最早由v i c t o r m i u e r 1 3 和n e a lk o b l i t z 1 4 在1 9 8 5 年分别独立提出，其安全强度基于椭圆曲线离散对数问题 ( e c d l p ) ，对非超奇异椭圆曲线，已知好的求解e c d l p 算法是可适用于一 般群的p o l l a r d p 算法及p o h l i g - h e l l m a n ，y 法，这些算法都是指数时间复 杂度的，当椭圆曲线的“有理点数”( 称之为椭圆曲线的阶) 含有较大 素因子时失败。目前普遍认为非超奇异椭圆曲线离散对数问题的难度远 远超过乙+ 上离散对数问题( d l p ) 的难度。至今没有亚指数算法求解 e c d l p ，而有限域上的d l p 已有皿指数算法。这使得椭圆曲线密码体制 ( e c c ) 可以使用长度小得多的密钥。例如在同等安全前提下，1 6 0 倍的 椭圆曲线密码相当于1 0 2 4 位的r s a ，而签名和解密速度要比r s a 快得多。 由于密钥长度短、数字签名速度快、计算数据量小，尤其适合计算资源 和存储资源受限的设备，所以e c c 体制正逐渐应用于实现d i f f i e h e l l m a n 密钥交换协议 1 2 、e l g a m a l 数据加密协议 7 、e l g a m a l 、s c h n o r r 、d s a 签名协议等通信安全协议中。 1 7 1 椭圆曲线 椭圆曲线是由韦尔斯特拉斯( w c i e r s t r a s s ) 方程： y 2 + a l x y + 口3 y 菇3 + 口2 + 4 4 x + 4 6 所确定的平面曲线，其中系数a i ，( f = l ，6 ) 定义在某个域上，可以 是有理数域、实数域、复数域，还可以是有限域，椭圆曲线密码是基于 黑龙江大学硕士学位论文 有限域上椭圆曲线有理点群的一种密码系统。 有限域，鼋z 3 上的椭圆曲线e ( ) 是定义在仿射平面上的3 次方程 y 2 一+ 删+ 6 的所有解与无穷远点0 的并集。记作： e ( ) = “y ) l y 2 = 工3 + 甜+ 6 ，o ，y ) e g x g u o 其中，q 为素数，的特征值c h ( ) _ 2 ，3 ，口，6 ，h 4 a 3 + 2 7 b 2 - o e ( f q ) 中的点数称为椭圆曲线的阶数，记作# e ( ) ，由王，口胱引理 9 可 知碍+ 1 2 石s 样幔) s 口+ 1 + 听 有限域上的椭圆曲线舀( ) 上的点集对点的加法构成，4 6 p f 群，椭圆曲 线上的点满足： 单位元：0 ，p + o - 0 + 尸一尸；一0 0 逆元：- p ，若p 一0 ，y ) - 0 ，则一p 一0 ，一) ，) ，且p + ( 一p ) - 0 结合律：p ，q ，r e ( 只) ，贝咀p + ( q + 胄) - ( p + q ) + r 1 7 2 椭圆曲线上群运算 ( 1 ) 点的加法 令e ，p 2 e ( e ) ，置一“，y ，) ，只一心，y ：) ，则b + p 2 一( x 3 ，) ，) e ( k ) ，其中， 叫2 寸b 胪啮一醚篡 ( 2 ) 点的乘法 令尸= o ，y ) k 为整数，则舻一0 ，y ) + o ，) ，) + + 0 ，y ) ，( k 一1 次加法) 1 4 第1 章密码学相关理论 i i i i i i i i i i i i i i i i i i 鼍i 皇i i i | 宣# i 罩每i i i i i i i i 宣皇i i i i 一i l 点p 的阶数h 是满足n p - 0 的最小整数。 在椭圆曲线密码体制中，一般在e ( e ) 上选取p ；o ，y ) 作为公共基 点，要求这个公共基点的阶n 为一个素数阶，并使n 足够大，p 为生成元， a b e l 群t p - p ，2 p ，n p c _ e ( e ) 是由点p 生成的阶循环子群，以 tp ，来构建密码体制。 在建立椭圆曲线公钥密码系统时，需要选择合适的椭圆曲线参数以 保证系统的安全性。对参数的要求及具体的选择方法可参见文献 9 。 1 7 3 椭圆曲线离散对数问题 给定椭圆曲线e ( e ) ，点p e e ( f q ) ，p 的阶数为厅。对于给定点 r e 。每个结点 拥有一个私钥疋h ，和 一个公钥瓯协一g 岛”( r o o d p ) ，其中g 为z ，的生成元，p 为群z ，+ 的阶。 如果 是非叶子结点，则 包含2 个孩子结点 和 。基于d i f f i e h e l l m a n 协议，非叶子结点 的私钥由 一个子结点的私钥和另一个子结点的公钥生成： 疋“，一( s k “l m ，) 岛”。r o o d p 一( 脒“1 2 v + 1 ，) 妇”m o d p 2 2 第2 章当前动态对等群的密钥协商协议 = g 岛“v 山“”m o d p 。其中g 为z p 的生成元，p 为群z p 的阶。 因为每个结点的公钥是公开的，所以每个群成员都能沿着他的密钥 路径计算路径上的结点的密钥。 图l 是t g d h 协议通信过程的一个可能的密钥树，群中有6 个群成 员 t 到m 6 。j l f 2 通过置k 加，麒。枷，剧t u ，匠m 可以计算k 2 加， 疋。则最终的群密钥e 。加。g ( s ”“”x s “” m o d p ，其中心为每个m ， 的私钥。 m 1m 2m 5m 6 2 2 4 s t r 协议 ( 圈1 ) s t r 协议是t g d h 协议的变体。与t g d h 协议相比，在s t r 协议 中，作者通过牺牲计算开销的方法减少了通信开销。s t r 协议的构建基 于不平衡二叉树。同样地，在不平衡二叉密钥树中的每个叶子结点连接 着群成员m ；，他的私钥由其随机选取，每个群成员拥有其他群成员的 黑龙江大学硕士学位论文 公钥和从他所连接的叶子结点到根结点的密钥路径上的所有私钥。因此， 根结点的私钥被所有群成员共享，故可作为群密钥。 图2 是s t r 协议通信过程的一个密钥树的例子。 删1 ) l n 。1 ， m lm z ( 图2 ) 树有三种类型的节点：叶子结点、中间节点和根结点。每个叶子结 点都代表一个特定的群成员。中间节点刀t 。，有两个孩子节点：低级中间 节点z e 。，和一个叶子结点川，。特别地，以。= 朋t ，( m 1 所在的叶 子结点) 。每个叶子结点删。都有一个由m ，保密的会话密钥，公开的 会话密钥奶- 9 1 ( m o d p ) a 每个中间节点上k 。有一个保密密钥k 和一个 公开的盲密钥蝎= 占q ( r o o d p ) 。每个保密密钥a ，1 ) 是由两的节点间 的d i f f i e h e l l m a n 密钥协商协议得到的，可按如下方式得到： k 暑( 6 喝一1 ) r o o d p 暑( 6 ) 4 r o o d p l 9 1 m o d p ，i 1 根节点e 为所有成员共享的群密钥。 在图2 中群密钥蜀；占1 s 秽( m o d p ) 。 4 ， 第2 章当前动态对等群的密钥协商协议 2 3 几种协议的性能分析与比较 在群通信的密钥协商协议中，通信开销与计算开销是衡量协议是否 有效的最重要的两个因素。通信开销大而计算开销小的协议适用于高速 局域网，因为在这种网络中，通信开销相对于计算开销可以忽略不计。 相反，计算开销大而通信开销小的协议适用于高延迟的广域网，因为在 这种网络中，通信开销才是最重要的因素。一般说来，节省通信开销可能 要增加计算开销，而节省计算开销就要增大通信开销。目前很难有一种 协议做到两全其美。 g d h 协议计算开销很大，但是通信量较少。b d 协议则是通信开销很 大，计算开销较少at g d h 越j 议将计算开销从0 0 ) 降 o ( 1 0 9 ：玎) ，其计 算开销和通信开销都较少。在目前已经提出的这些适用于动态对等群的 密钥协商协议中，实验证明s t r 协议在通信开销方面最好。 在这一节里我们分析单个成员加入、退出，多个成员加入、退出四 个协议的通信开销和计算开销。重点关注轮数，传递消息的总数，指数 运算次数和数字签名的次数。为确保协议的可靠性我们采用r s a 数字签 名，因为在飓数字签名中对于签名的验证十分方便。 表1 将t g d h 、s t r 、g d h 、b d 四种协议进行了比较，见【2 8 】： 设一一群成员个数，k 一群合并个数，m 一加入成员个数，p 一 离开的成员个数。 在t g d h 协议中，设密钥树的深度为h 。t g d h 协议的计算开销依赖 于树的深度，密钥树的平衡性，加入和退出成员的结点位置等因素。在 分析过程中，考虑最坏情况和最大开销。 黑龙江大学硕士学位论文 通信开销计算开销 轮数消息指数 加入 4 i t + 3 以+ 3 退出 l1以一1 g d h 合并 埘+ 3n + 2 ，抖+ 1n + 2 m + 1 分离 11n p 加入 233 h 一3 退出113 h 一3 t g d h 合并 l 0 9 2 k + 1 2 k3 h 一3 分离 r a i n ( 1 0 9 2p + l ， )m i n ( 2 p ， 3 h 一3 加入 23 4 退出11 孕+ 2 锨 合并 2k + 13 m + 1 分离 11 单+ 2 加入 22 n + 23 退出 22 n 一23 b d 合并 2 2 n + 2 m3 分离 2 2 靠一2 p 3 ( 表1 ) b d 协议有一个潜在的开销在表中并没有列出：b d 协议有咒1 次小指 数运算，当n 较大时，这一运算量也相当大的。例如若用平方乘算法来 实现模指数运算b d 协议需要0 ( h ) 次1 0 2 4 位的模乘。g d h 协议、t g d h 第2 章当前动态对等群的密钥协商协议 协议、s t r 协议均需要0 m ) 次模指数运算，而b d 协议有h 一1 次小指数 运算，运算量也相当大，4 种协议中计算量较小的t g d h 协议也需要寻 ( 为二叉树的高) 。 下面我们将就t g d h 、s t r 、g d h 、b d 四个协议的单个成员加入、 退出，多个成员加入、退出4 种成员变化分别进行比较。 单个成员加入：除g d h 协议外，所有协议均需2 轮通信开销。每一轮 中b d 协议需要 个消息传播，而其它协议只需常数个消息传播。g d h 协议 在计算开销上最大，s t r 协议需常数次模指数运算。b d 协议所需指数运 算最少，但存在潜在开销。 单个成员退出：b d 协议的通信开销最大。由于其它协议具有相同的 通信开销，故对于总开销的比较取决于对其计算开销的比较。由表1 可以 看出，t g d h 在处理成员退出时最有效，s t r 和g d h 的计算开销是群的 大小的线性函数，b d 由于其潜在的开销很难比较。 多个成员加入：先比较通信开销。g d h 的通信开销是加入的新成员 的数目的线性函数，b d 和s t r 只需常数轮数，t g d h 的通信开销依赖于 合并群的数目，通常情况下这个数目也是较小的。s t r 需驮次消息传播， 因此s t r 在通信消耗上时最有效的。对于计算开销，b d 只需3 轮模指数 运算，t g d h 的计算开销是群大小的对数函数。s t r 和g d h 的计算开销 是群的大小的线性函数。 多个成员退出：g d h 和s t r 都需1 轮和1 次消息广播，b d 需2 轮，每轮 需h 次消息广播。t g d h 的通信开销最大，所需通信轮数依赖于密钥树的 深度。g d h 和s t r 的计算开销是群的大小的线性函数，t g d h 的计算开 销是退出群个数的对数函数，b d 由于其潜在的开销很难比较。 黑龙江大学硕士学位论文 2 4 本章小结 本章简介了目前适用于动态对等群的几种密钥协商协议：g d h 、 b d 、t g d h 、s t r 等。通过对这些协议的分析和比较，不难得出在这些 密钥协商协议中，s t r 在通信开销方面最好，但计算开销略有增加。但 幸运的是，随着科技的发展，计算速度有了大幅度地增加，而通信开销 的进展不大。 第3 章协议的设计与实现 第3 章协议的设计与实现 由第一章的分析可知，s t r 仅提供了前向安全性和密钥独立性的等 基本安全属性，没有提供密钥认证，因此不能抵抗中间人攻击和已知密 钥攻击等主动攻击。本文利用椭圆曲线上的p a i r i n g 在安全性和灵活性方 面的优势，并运用b d h 密钥交换将不平衡三叉树扩展到s t r 协议提出了 一种基于p a i r i n g 的三方可认证的密钥协商协议，称为b s t r 。b s t r 协议 是一个在安全性和性能方面都满足动态对等群要求的协议。 3 1 符号说明 一群成员个数；c 一当前群成员集a t 一第个i 群成员( i e l l v ) ；i n j ，一密钥树第f 层中间节点。 n 一密钥树的深度：u 叱，一成员鸩对应的叶子结点。 一肼。的会话密钥( k 的临时私钥) ；p 一椭圆曲线上的点( 公开) 。 奶一 公开会话密钥r i p ；啊一h a s h 函数g 2 一z 。 为一 毛，m 2 共享密钥；6 q 一公开密钥k j p 。 ；，一群成员 f ；的密钥树。 b t 。一群成员m ；的包含所有公开密钥的密钥树。 3 2 三叉b s t r 密钥树 图3 是三叉b s t r 密钥树的例子。 黑龙江大学硕士学位论文 删( 1 i n t l ， l k 5 ， ( 图3 ) 树有三种类型的节点：叶子结点、中间节点和根结点。每个叶子结 点都代表一个特定的群成员。中间节点z k 。有三个孩子节点：低级中间 节点j ：k - l 和两个( 或一个) 叶子结点肼。2 a 廿l n 2 0 _ 1 ) + ，特别地， 正，= l 札。( 鸩所在的叶子结点) 。每个叶子结点+ 都有一个由肼； 保密的会话密钥，盲目会话密钥魄ir ；p , ( i e l n ) 。每个中间节点i n 。 有一个保密密钥k 和一个公开的盲密钥6 q 一p ，( j e l l , n ) 。根节点 k 为所有成员共享的群密钥，( 胆为密钥树深度) 。 若己知中间节点以，的一个孩子节点的会话密钥和其他两个节点 的盲密钥可通过计算椭圆曲线上的乘法计算墨。基本的密钥协商协议如 下： 假设所有成员知道密钥树的结构和他们在树中的初始位置。另外，每 个群成员知道自己的会话密钥和其他成员的盲会话密钥，膨。，m ：，m ，可 获得群密钥。 首先，定义一个在群成员活动变化中起特殊作用的群成员，称为组 一3 n 第3 章协议的设计与实现 织者( s p o n s o r ) m 1 ，帆计算 k ：一h ， ( 吃p ，p ) 1 ) 一h 。( ( p ，尸) ”) ，b k 2 = 如p = h 1 啦( r 4 尸，r s p ) 岛) = 皿p p ，p 也) ，矗墨= 玛尸 k = 域p 也_ 1 p ，j p ) 局“- h i p p ，p ) “写一- ) 然后，m ，公开所有盲密钥厶k ，( 1 s f s ”) 。通过这些信息，每个群 成员计算群密钥k 。 图3 中，群密钥玛可由如上递推方法得到。 命题1 若所有成员知道其他成员的盲会话密钥，则至少有三个成员可 以计算出群密钥。 证明：可由群密钥的递推计算得到。即m 。，m ：，m ，密钥树底部的叶子 结点可运用其他成员的盲会话密钥，通过递推计算得到群密钥。 命题2 任何群成员都可计算出群密钥。如果他知道：1 ) 他自己的私 会话密钥，2 ) 他姐妹节点的盲密钥树，3 ) 在密钥树中不低于他的其 他成员的盲会话密钥。 证明：根据群密钥的定义，为计算群密钥， t 成员知道 ，h 吩，奶，嘲m ，6 r 。 3 3b s t r 密钥管理协议 下面依次描述密钥管理的四个协议：单个群成员加入，单个群成员 退出，多个群合并，多个群成员退出。 3 1 黑龙江大学硕士学位论文 所有协议满足共同的特性： 1 每个新成员都拥有一个私钥，这些私钥对产生群密钥所作的贡献平 等。 2 群密钥是所有当前群成员私钥的函数，即k = ，“，r ) ，为j 】l f ，的 私钥。 3 当群扩大时，新成员立即产生私钥，并加入到群密钥的计算中，且 除组织者外其他剩余私钥不变， ( 为确保密钥独立性，组织者修改 其会话密钥。) 4 当群缩小时，离开的成员将其私钥从群密钥的计算中撤离，并且在 剩余的成员中至少有一个改变其会话密钥。 5 所有协议信息由发送者签名，即使用安全可靠的广播信道。 6 总假设三叉b s t r 树是饱和的，组织者m 可通过虚拟新群成员使密 钥树达到饱和。 3 3 1 单个群成员加入协议 假设群有个成员f m l 一，m 。) ，当群通信系统公布有一个新成员加 入时，新成员和原群成员同时收到通知。新成员公布一个包含其盲会话 密钥6 r + 。的加入申请信息。当每个群成员收到这个信息后，决定 “。在 密钥树中的插入的位置。当密钥树的顶端存在虚拟成员时，组织者m ，将 虚拟成员去掉，由m 。取代其位置插入到根节点的孩子节点中。否则， 则肼。创建一个新的根节点z k 掣。将原来密钥树的根结点z t 雌和新成 员叶子结点三。，作为其孩子节点，并虚拟群成员肘，+ ：。然后组织者 第3 罩协议的设计与买现 m 。更改其会话密钥，c t y b q + ，并将当前密钥树丑t 。和所有盲密钥公 布。由命题2 可知，每个成员均可计算出群密钥。事实上， 所有以前的群成员只需知道新成员的盲会话密钥 新成员须知道以前群的盲密钥 下面是单个群成员加入协议的细节描述： 第一步新成员提出加入申请 m “虬凸芷_ c - ( m 1 ，m ， 第二步每个成员 1 确定新成员的位置，通过增加新成员的节点l ：。改变原来密钥树的 结构 2 去掉峨 组织者肠。( 如有必要创建虚拟成员) 产生新的会话密钥0 ，计算研 公布新密钥树b l 。+ m l 些l - - + c u 肘+ i ) 一 m l ，- 一， f + 1 第三步 每个群成员通过口，计算新的群密钥。 图4 是新成员m 。加入到群 m ，m ，) 中的例子，组织者j | l f ，创建虚 拟