（计算机应用技术专业论文）关于密钥协商协议的相关研究.pdf

山东大学硕士学位论文 摘要 本文中我们的工作主要分为两部分，第一部分是构建一个基于身份的多安全 群组密钥协商协议：第二部将上述对等群组的协议扩展到树结构，构建一个适用 于动态的基于树的群组密钥协商协议。 多播的广泛应用，使其成为当前研究的一个热点问题。其中最为核心的就是 多播组的密钥管理问题。目前已有的群组密钥管理协议主要包括群组密钥分配协 议和群组密钥协商协议，他们各有优缺点，适用于不同的情况。本文主要讨论了 密钥协商协议，介绍了协议的分类，协议的发展和具体的协议。 目前，大部分基于身份的密钥协商协议都是针对一个安全群组设计的，这能 简化协商过程中的计算量，但不能满足不同安全群组间密钥协商的需求，并且在 安全性方面存在一定的隐患。在本文中，我们提出一个多安全群组下的基于身份 的可认证的多方密钥协商方案，并对其安全性和效率进行了分析。 考虑到我们协议的动态性较差，我们以上述协议为基础，使用数字签名认证 的方式，构建了一个基于3 叉b 树的群组密钥协商协议。实现了协议的动态性和 可更新性。 未来协议的热点主要集中在构建基于身份的常数轮的大型群组的密钥协商协 议，协议的安全性方面必须满足可认证性，动态性方面必须满足便捷性，同时协 议还要有最小的日常管理和定时更新密钥的代价。 关键词：密钥协商：安全群组；基于身份的：密钥认证 山东大学硕士学位论文 a b s t r a c t o u rw o r ki nt h i sp a p e rc o n s i s t so ft w op a r t s i nt h ef i r s tp a r tw ep r o p o s e a na u t h e n t i c a t e dm u l t i p a r t yk e ya g r e e m e n tp r o t o c o lo fi d b a s e di nw h i c h t h ep a r t i c i p a n t sa r ei nt h ed i f f e r e n ts e c u r i t yd o m a i n s i nt h es e c o n dp a r t w ee x t e n dt h ef o l l o w i n gp r o t o c o lt ot h et r e e b a s e dp r o t o c o la n dg i v ea d y n a m i ct r e e b a s e dg r o u pp r o t o c 0 1 m u l t i c a s tw h i c hi sa p p l i e de x t e n s i v eh a sb e c o m eah o t t e rr e s e a r c ht o p i c n o w t h em o s ti m p o r t a n ti s s u ei st h em a n a g e m e n to ft h em u l t i c a s t a tp r e s e n t g r o u pk e ym a n a g e m e n tp r o t o c o li sm a i n l yd i v i d e di n t og r o u pk e yd i s t r i b u t i o n p r o t o c o la n dg r o u pk e ya g r e e m e n tp r o t o c o l ，b o t ho ft h e mh a v et h e i ro w n c h a r a c t e ra n dc a nb eu s e di nd i f f e r e n ta p p l i c a t i o n s i nt h i sp a p e rw em a i n l y d i s c u s st h eg r o u pk e ya g r e e m e n tp r o t o c o l ，a n di n t r o d u c et h es o r t s t h e d e v e l o p m e n ta n dt h ec o n c r e t ee x a m p l e so ft h ep r o t o c 0 1 n o w , m o s to ft h ek e ya g r e e m e n tp r o t o c o l so fi d - b a s e da r ee x e c u t e di nt h e s a m ed o m a i n t h ea d v a n t a g ei st h e yc a nr e d u c et h eq u a n t i t yo ft h e c o m p u t a ti o n b u tt h e yc a n n o tr e a c ht h er e q u i r e m e n t so fd i f f e r e n td o m a i n s a n de x i s tt h ef l a wi nt h es e c u r i t yo ft h ep r o t o c 0 1 s ow ep r o p o s ea n a u t h e n t i c a t e dm u l t i p a r t yk e ya g r e e m e n tp r o t o c o lo fi d b a s e di nw h i c ht h e p a r t i c i p a n t sa r ei nt h ed i f f e r e n ts e c u r i t yd o m a i n s f u r t h e r m o r e ，w e a n a l y s e si t ss e c u r i t ya n de f f i c i e n c y o nc o n c e r no ft h ew e a k n e s so ft h ep r o t o c o l sm o b i l i t y w eg i v eag r o u p a g r e e m e n tp r o t o c o lo ft e r n a r yb t r e eu s i n gt h ea u t h e n t i c a t i o no ft h e d i g i t a ls i g n a t u r ea n da c h i e v et h em o b i l i t ya n dt h eu p d a t eo ft h ep r o t o c 0 1 t h ef o c u sr e s e a r c ho fa g r e e m e n tp r o t o c o li nf u t u r ei st h ec o n s t a n tb i g g r o u pk e ya g r e e m e n to fi d b a s e d t h ep r o t o c o lm u s th a sa u t h e n t i c a t i o ni n t h es e c u r i t y ，f l e x i b i l i t yi nt h ec h a n g eo fu s e r se n t i t y ，a n dm i n i m i z e s t h ec o s to ft h ed a i l yk e ym a n a g e m e n ta n dt h et i m e l y u p d a t e 山东大学硕士学位论文 k e y w o r d s ：a g r e e m e n tp r o t o c oi ：s e c u rit yd o m a in ：id - b a s e d ：k e y a u t h e n t i c a t i o n i f 原创性声明和关于学位论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律责任由本人承担。 论文作者签名：基! l 鑫挞 日期： 生z 垒：y 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文 论文作者签名 ：盘z 箬夕 山东大学硕士学位论文 第1 章绪论 1 1 前言 随着i n t e m e t 网络的普及和广泛应用，多播也得到了迅速的发展。多播技术 以其能够大大节省网络带宽、发送者资源以及减少网络流量而得到广泛应用，诸 如视频传输、实时信息服务( 如股票报价) 、网络游戏、在线升级等，成为一种高 效、快捷的传输方式。多播中的安全性问题是口多播应用日益中受到关注的问题， 其中群组密钥的安全管理是多播安全的核心问题。 密钥管理又可以分为密钥分配和密钥协商。密钥分配通常称作集中式密钥管 理，其密钥是由一个主体( 群组管理员1 产生并分发给每一个组成员。与密钥分配不 同，密钥协商又称为分布式密钥管理，适用于分散的、无管理中心的群组结构( 如 动态对等群) 。 所谓的密钥协商就是一种能够让通信系统中的两个或者多个参与主体在一个 公开的、不安全的信道上通过通信协商，联合建立一次会话所用的临时会话密钥 的通信机制，该i 临时会话密钥的值是一个由参与各方提供的输入共同作用得到的 对于参与各方而言是相同的函数值。其中任何一方都不能预先决定最终的结果。 而密钥协商的研究重点集中在减少开销和提供密钥认证两个方面。 对于大的群组来说，密钥协商过程中的计算量、通信量和轮数是至关重要的。 通信开销往往是一个方案的重要参数，成为决定其性能的主要因素。也是一个当 前应用的最大瓶颈。因此密钥协商机制必须尽量减少通信量。 在一个密钥协商协议中，如果协议的每一方都确信共享密钥只有协议的参与 者才知道，则称此协议提供了隐含密钥认证( i m p l i c i t k e ya u t h e n t i c a t i o n ) ，如果一个 密钥协商协议提供了密钥认证功能，则称此协议为可认证( a u t h e n t i c a t i o n ) 密钥协商 协议( a k 协议1 。如果一个密钥协商协议既是认证的又是确认( c o n f i r m a t i o n ) ，则 称之为带确认的可认证密钥协商协议( a k c ) 。 对密钥协商协议的攻击分为被动攻击和主动攻击两类，其中最著名的一个主 动攻击方法就是“中间人攻击”。但如果一个密钥协商协议是a k 协议，则可以有效 地抵抗“中间人攻击”。因此，一个实用的密钥协商协议至少应该是一个a k 协议。 山东大学硕士学位论文 一个a k 或a k c 协议，通常还要具有如下的一些安全属性【1 】： ( 1 ) 等献的( c o n t r i b u t o r y ) ：最终的协议结果是由参与协商的各方共同作用所 得，任何一方不能预先决定协议的最终结果。 ( 2 ) 已知密钥安全：通信双方或多方通过执行密钥协商协议所得到的共享秘 密，称为会话密钥。已知密钥安全就是在攻击者已经知道以前的一些会话密钥情况 下。仍然可以建立安全的会话密钥。 ( 3 ) 完全前向安全：通信一方或多方的长期私钥被暴露或破坏，以前通过密钥 协商协议建立的会话密钥仍然是安全的。 ( 4 ) 无密钥控制：任何一方都不能强制会话密钥为一个预先确定的值，也就是 密钥协商所得到的会话密钥值应是随机的。一个a k 或a k c 协议所要求的性能属性 包括：最少阶段数( 即协议执行一次所传输的消息数) ，最低通信开销( 即传输的总比 特数) 以及最低的计算量开销。 自从著名的d i f f l e h e l l m a n t 2 1 协议提出以来，许多两方密钥协商协议和多方密 钥协商协议被提了出来，其中多方密钥协商也叫会议密钥协商或群组密钥协商。 随着网络应用的发展，越来越多的群组通信需要进行密钥协商，以建立共同的会 话密钥进行安全的数据传输。 群组密钥协商过程中需要对用户的真实性进行认证根据对用户身份的认证基 础不同，可将密钥协商协议分为基于用户公钥证书的协议或基于用户身份d 的协 议。根据对协商过程中参与协商的人数或协议方的不同，可以将协议分为两方协 商协议，三方协商协议和多方协商协议( 群组协议) 。根据协商时的通信量是否 与协商的用户数成常数的函数关系，可将协商协议分为常数轮协议和非常数论协 议。 在本文中我们将着重讨论基于身份d 的群组密钥协商协议，而目前针对群组 密钥协商方案的研究主要集中在为大型群组寻找优化的密钥树结构，以实现在总 体计算量，通信量等方面的优化，并考虑到群组的动态性，实现在用户插入、离 开( 包含子群组的合并，分离) 以及密钥及时更新方面的优化。另一方面的研究 集中在如何把用户身份认证和密钥协商相结合，增强协议的安全性。目前的认证 主要是基于秘密共享和签名机制( 如多签名等) 。但是，总的说来这些方面的研 究结果还较为初步。 山东大学硕士学位论文 同时，考虑到目前基于身份的协商协议大多处在一个k c , c ( 密钥生成中心1 ， 也就是说他们使用同一个k g c 提供的相同的主钥s 。而不同机构，不同地理区域 的群组使用相同的主钥参数，也是不合理的。不仅造成计算瓶颈，也带来管理上 的麻烦，这必然在安全性方面大打折扣。如果k g c 的主钥不幸泄漏，后果将将很 严重。即使在正常情况下，k g c 想要对主钥s 进行更新，也会产生巨大的计算量。 本文将就以上问题进行讨论，实现多安全群组下的对等群组密钥协商协议，并将 其扩展到基于树的结构，实现群组的灵活动态性。 1 2 本文的贡献 ( 1 ) 设计了一个多安全群组下的基于身份的对等群组密钥协商协议。对其安 全性采用b r e s s o n ”的攻击模型进行安全证明。 ( 2 ) 扩展上述协议至树状结构，构建一个三叉树的动态协商协议，实现了群 组的动态性。 1 3 本文的组织 本文的第二章按照不同的分类介绍了密钥协商协议的基本情况，包括协议发 展现状以及模型化证明发展的历程。第三章介绍了与协议相关的基础知识，主要 是协议基于的困难性假设问题，以及攻击模型的介绍。第四章介绍了主要的密钥 协商方案。第五章介绍了我们的协商协议方案及其扩展方案。 最后对全文进行了总结，并指出了进一步的研究方向和进一步的思考。 1 4 本章小结 本章介绍了密钥协商协议的概念以及密钥协商的概况，并介绍了本文的贡献 和本文的组织。 山东大学硕士学位论文 第2 章协议的分类、发展 我们将按照协议的分类，分别从不同的角度介绍各类协议的背景以及协议的 发展，以实现对密钥协商协议的发展有整体的了解。 2 1 基于身份和基于证书的协议 按照协议的对用户真实身份的认证基础的不同分类，可将协议分为基于证书 的协商协议和基于身份的协商协议。 群组密钥协商过程中为了对用户进行认证，大多采用传统的p k i 公钥证书方式。 这种方式假设每个用户实体都有一个公私d i f f i e - h e l l m a n 密钥对( 公钥是长期静态 的) ，每个实体都知道其他实体的公钥。证书授权中心( c a ) 通过将用户的身份信 息绑定到用户的静态钥上来给用户发放授权证书。当两个实体想要建立一个协商 会话钥时，需要相互交换短期公钥。通过将短期钥和长期钥相结合的方式来实现 共同的会话钥。用户实体长期公钥的真实性由c a 提供，并保证只有拥有长期静态 钥的实体才能计算会话钥，也就是说会话钥的真实性取决于c a 保证的长期静态公 钥的真实性。 在传统的基于证书的密码系统中，在使用一个用户的公钥之前，人们需要验 证其证书是否正确、合法、有效，其结果是需要大量的存储空间和计算开销来存 储和验证众多用户的公钥证书。为了克服这个缺点，提高系统的效率，s h a m i r t , l 在1 9 8 4 年提出了基于身份的密码系统( i b c 。i d - b a s e dc r y p t o s y s t e m ) 的概念。 2 1 1 基于身份的密码体制的研究背景 s h a r r 一4 ) 的主要观点是：系统中不需要证书，可以使用用户的标识如姓名、p 地址、电子邮件地址等作为公钥，用户的私钥通过一个被称作私钥生成器p k g ( p r i v a t ek e yg e n e r a t o r ) 的可信第三方进行计算得到。基于身份的密码系统使得用户 的公钥能够通过用户的身份信息直接计算出来，不需要保存每个用户的公钥证书， 避免了使用证书带来的存储和管理开销的问题，简化了基于证书的密码系统繁琐 的密钥管理过程。由此可见，基于身份的密码系统是基于证书的公钥密码系统很 山东大学硕士学位论文 好的替代品。基于身份的密码系统中应该满足： ( 1 ) 用户之间既不用交换私钥也不用交换公钥。 ( 2 ) 不需要保持一个公共的证书服务器。 ( 3 ) 只在系统建立阶段需要可信中心服务。 基于身份的密码系统是一个非对称系统，与普通的公钥系统相比不同之处在 于：基于身份的系统中实体公开身份信息是实体的唯一标识，它起着公钥的作用； 特定的用户公开数据不需要明显地验证。如果用户的公共数据不正确，将会导致 使用它的密码交换失败，如加密产生的密文不能正确解密、签名验证或实体验证 失败、密钥协商双方产生的会话密钥不同等。可信第三方用自己的私钥和实体的 公开身份信息计算出该实体的私钥，并安全地传送给用户。这对于防伪造和防伪 装是必要的，只有可信中心能从给定的用户身份信息计算出相应的合法私钥。 2 1 2 基于身份的密钥协商协议的发展 近些年来，各国学者对基于身份的密码系统进行了许多研究，取得了丰富的 成果，许多各种类型的基于身份的加密和数字签名方案以及密钥协商方案被相继 提出。 1 9 8 4 年s h a n d r 【4 j 提出了基于身份的加密、签名、认证设想，这样，在基于身 份的系统中，不需要证书，减少了系统管理开销。到目前为止出现了多种方案， 其中b o n e h 和f r a n k l i n l 5 】在2 0 0 1 年提出了基于w e i l 对的i b e ( i d - b a s e d e n c r y p n o n ) 的方案提供了较好的效率。它使用小的多的密钥长度提供和当前公钥体制相当的 安全等级，不仅减少了通信开销而且降低了加解密操作的复杂度。 自1 9 8 5 年至2 0 0 1 年，研究者们陆续又提出了一些基于身份的加密、签名和 密钥协商等方案。目前，以双线性对为工具，设计形式多样的密协商协议引起了 国内外学者的广泛关注。 2 0 0 0 年j o u x 【6 l 提出了一个三方的密钥协商协议，他利用椭圆曲线上双线性对的 性质设计了一个简单的初步密钥协商协议。这是密码学系统中双线性的首次应用， 也是密钥协商协议的一个重要突破。 2 0 0 2 年s l i l “1 提出了基于身份的可认证双方密钥协商协议。但是方案要求所 有的参与者必须都使用同一个私钥产生器p k g 。c h e na n d k u d l a t 8 1 在文中提出了 山东大学硕士学位论文 个b t s m a r t 更有效的可认证密钥协商协议，并通过安全模型分析了它的安全性。他 们还提出了在s m a r t 的基础上撤销可信第三方的设想( 可能更适合于私人的通信) 。 在2 0 0 2 年，z h a n g ，l i u ，k j m 9 1 结合了h e s s l ”1 的基于的签名思想提出了一个单 轮三方的可认证密钥协商协议，这也是常数轮密钥协商协议的一个实例。x i n j u nd u , y m gw a n g 和j i a n h u ag e t l o 提出了一个类似于b u r m e s t e r 和d e s m e d t i n 的b d 方案，它 是基于d 的两轮多方密钥协商协议，采用数字签名的认证方法。2 0 0 5 年r a t a n ad u t t a 和r a n a b a r u a 1 2 墟出了一个基于树的动态组密钥协商协议，其中采用3 叉b 树的组织 结构，采用对同一个消息的多重签名的方式来实现认证。而签名的认证方式也是最常 用认证方式之一。 总之，由于双线性对被成功地用于构造基于身份的密码系统，极大地推动了 这方面的研究工作，使得基于身份的加密，数字签名方案以及密钥协商的设计和 其相关的应用研究成为密码学的热点之一。虽然如此，实际生活中基于证书的密 钥协商仍然占据主流，因为基于证书的密钥系统有许多未解决的现实问题。 2 1 3 基于身份与基于证书公钥系统的比较 基于身份的密码系统使得用户的公钥能够通过用户的身份信息直接计算出来， 不需要保存每个用户的公钥证书，避免了使用证书带来的存储和管理开销的问题， 简化了基于证书的密码系统繁琐的密钥管理过程。下面对比两个系统的共同点和它 们之间的区别，最后指出基于身份的公钥系统面临的一些问题【1 3 】。 1 基于身份的公钥系统和基于证书的公钥系统的相同之处 ( 1 ) 都属于公开密钥体制，一个公开密钥，可以公布；另一个私有密钥，由 用户保存，严格保密。 ( 2 ) 都是公钥用于加密，私钥用于解密或私钥用于签名，公钥用于验证签名。 ( 3 ) 己知公钥，无法计算出私钥。 ( 4 ) 已知公钥和密文，不能计算出明文。 ( 5 ) 系统的安全性依赖于大整数分解、离散对数问题、椭圆益线求解等数学 难题。 2 基于身份的公钥系统和基于证书的公钥系统的不同之处 ( 1 ) 在基于证书的系统中，用户的d 和证书绑定，需要在验证t c a 的签名后 山东大学硕士学位论文 才能确认。在基于身份的系统中，用户的可以直接得到。 ( 2 ) 在基于证书的系统中，公钥和私钥作为一对密钥同时计算出来。在基于 身份的系统中，公钥和私钥都是由用户的d 计算出来，用户的公钥决定私钥，并 且私钥可以在接收到加密消息之前也可以在之后产生。 ( 3 ) 在基于证书的系统中，用户的公钥必须经过c a 中心的签名，才能被其 它用户接受。在基于身份的系统中，用户的公钥就是d ，无需一个权威机构签名。 ( 4 ) 在基于证书的系统中，需要有一个目录来存放用户的公钥证书，需要保 持一个公共的证书服务器。在基于身份的系统中，由于公钥直接由i d 计算得到， 无需单独的目录存放证书。 3 基于身份的公钥系统面临的问题 ( 1 ) 基于身份的公钥系统天生就有密钥托管功能，p k g 知道所有用户的私钥， 就可以以任何用户的名义对任意消息进行签名，这对签名的不可否认性构成很大 的威胁。 ( 2 ) 基于身份的公钥系统无需证书管理，但是用户的d 管理也是一个麻烦的 问题。 ( 3 ) 在传统的基于证书的系统中，公钥的撤销通常使用证书撤销列表。而在 基于身份的公钥系统中，撤销证书意味着废弃原来的密钥，只能采用其它手段来 实现公钥的撤销，例如可以在用户的口d 上串联一个表示公钥生命周期的时间，但 这也存在周期长短如何确定等问题。 ( 4 ) 当用户数量特别大的时候，基于证书的系统是通过证书链和交叉认证来 实现不同的系统之间互联。而基于身份的公钥系统在大规模使用时，会碰到身份 唯一性问题。 ( 5 ) 需要在p k g 和用户之间提供安全的方法或通道来解决私钥分发问题。 通过以上讨论我们可以看出，基于证书的公钥系统最大的问题就是证书的管理， 证书里面绑定了用户的d 和用户的公钥。为了解决这一问题，提出了基于身份的公 钥密码系统，用户的d 就相当于用户的公钥，只在系统建立阶段需要可信中心的服 务，不需要专门的目录存放证书，大大地减轻了管理的负担，是基于证书的公钥密码 系统很好的代替品，但是基于身份的公钥密码系统也存在着上述一些问题，这些都是 以后研究的方向。 山东大学硕士学位论文 2 2 两方、三方及多方协议 根据参与协议的实体个数的不同，可将协议分为两方协议，三方协议和多方 协议。 2 2 1 两方协议的发展 1 9 7 6 年d i f f i e h e l l m a n 囡提出了第一个两方的单轮密钥协商协议。为密钥协商 的发展做出了里程碑式的贡献。但是其协议不能抵抗中间人攻击。 1 9 8 6 年m a t s u m o t o ，t a k a s h i m a 和i m a i “1 扩展了d i f f i e h e l l m a n 【2 1 协议，提出 了三个隐式的可认证的密钥协商协议m t i ：m n ，a 0 ，m h b 0 和m n ，c 0 。 l a w ，m e n e z e s 和v a n s t o n e 等指出了m 协议的漏洞，并证明 r i a o 与m f i c o 分别易受小子组攻击和未知密钥共享攻击，为此，l a w ，m e n e z e s 和v a n s t o n e i ”1 等在1 9 9 8 年提出了一个高效的可认证的密钥协商协议m q v ，但m q v 协议被证明 并不拥有未知密钥共享的特性。m t i 和m q v 都是基于证书的密钥协商协议。 2 0 0 2 年s m a “刀提出了第一个常数轮的基于d 的可认证的密钥协商协议，但 是方案要求所有的参与者必须都使用同一个私钥产生器( p k g ) 。 同年，c h e l a ，k u d l a 【8 1 给出了一个比s m a r t t 刀协议更高效的基于d 的可认证双 方密钥协商协议，并用m b l l a r e ，dp o m t c h e v a l | 1 6 , 1 7 1 中的正式安全模型对协议进行安 全分析。他们还将s m a r t 的协议扩展到无密钥生产器( p k g ) 和基于多个密钥生成 器( p k g s ) 的情形。 2 2 2 三方协议的发展 2 0 0 0 年j o u x 嘲提出了一个利用椭圆曲线上双线性对性质的简单的三方密协商 协议。这是密码学系统中双线性的首次应用，也是密钥协商协议的一个重要突破。 2 0 0 2 年= z h a n g ，l i u 和确m 纠结合h e s s 的基于的签名，提出了一个基于d 的 单轮可认证的三方密钥协商协议。其协议的安全取决于签名方案的安全和b d h 问 题的难度。 山东大学硕士学位论文 2 2 3 群组协议的发展 另一个密钥协商协议的研究方向就是扩展双方或三方密钥协商到多方，并考 虑成员在任何时间加入或离开多播组的动态情况。这样就扩展了密钥协商的应用， 也是最近几年的研究热点。从实用性的角度看，效率和安全性是设计群组密钥协 商协议的关键，当组成员很多并且是动态的时候，通信的轮数就成为焦点。动态 群组的密钥协商方案必须保证当有成员变动的情况下，会话钥能够及时更薪，以 实现前后向的安全。 根据群组协商的组织结构，可将群组协议分为对等群组协议和基于树的群组协 议。 1 对等群组的发展 1 9 8 2 年，i n g e m e r s o n , b u r m e s t e r 1 1 】和s t e i n e r t 2 0 l 等实现了有两方到多方的扩 展，但是他们的成果都是基于一个被动攻击( 偷听) 者的假设。 因此，s t e i n e r l 2 0 1 等在1 9 9 6 年提出了3 个“协商式”密钥协商协议，推广了 d i f f i e h e l l m a n 方案( 简称d h 问题) 到群组，即g d h 方案。a t e n i s e l 2 2 j 提出了协议的 认证性，并对主动攻击进行了启发式的安全分析。s t e i n e r 等【2 1 1 考虑了组成员增减 变动及更新的一系列不同情况，针对高动态群组引入了一个密钥管理方案 c l i q u e s ，但其方案的安全性分析也只是对主动攻击进行启发式的分析。因此， p e r e i r a 和q u i s q u a t e r t 2 a 1 等人描述了g d h 方案许多潜在的攻击，强调了在协议的安 全方面需要更多的途径来实现更大的保证。 2 0 0 1 年b r e s s o n “2 5 3 1 等对可认证的组密钥协商协议提出了一个正式的安全 模型形式化的攻击者模型，他包含了已存的随机o r a c l e 模型，并完善其没有 的细节( 如s t r o n gc o r r u p t i o n ，c o n c u r r e n ts e s s i o n s ) 。给出了第一个基于s t e i n e r t z 0 1 的可证安全协议，同时考虑了静态和动态的情形，并且协议在d d h 假设下是可证 安全的。 2 基于树的群组密钥协商协议的发展 当用户被组织为层次状时，就会必然的产生基于树的群组密钥协商。根据用 户在树中的结构大体上可以分为l k h 和i o l o u s 两种结构，我们将在以后介绍这两 种结构。 2 0 0 2 年k i m ，p e r r i g 和t s u d i k l 2 5 1 等将两方的d h 协议扩展到基于2 叉树的群 山东大学硕士学位论文 组d h 协议( t g d h ) ，他们还考虑了群组成员变动的动态情况，引入了四个协议： j o m ，l e a v e ，m e r g e 和p a r t i o n 。但他们对主动攻击的安全性分析也完全是启发式 的。 2 0 0 3 年n a l l a 和r e d d y 2 7 1 扩展了s m a r t 的基于d 的单轮可认证的协议到多方 的基于d 的二叉树结构密钥协商协议。b a r u a 2 8 1 等在基本j o u x 6 1 协议的基础上提 出了基于三叉树的非可认证的密钥协商协议，并在文献冽中进一步发展提出了基 于树的可证安全的可认证的群组密钥协商协议，同时在b r e s s o n l 2 4 _ 5 3 1 等的标准模 型中进行了安全分析。 2 0 0 4 年d u r r a 和b a r u a t ”l 设计了一个更为灵活的基于树的协商协议，使用户在 随意的加入和离开后仍能保持群组的树结构，同时拥有最小的密钥更新代价。 2 3 常数轮群组密钥协商协议 根据密钥协商过程中实体协商的次数与交换的时间性，实体数的关系，可将 协议分为常数轮协议和非常数轮协议。对等群组的非常数轮协议的轮数一般是o ( n ) ，基于树的非常数轮协议的轮数一般是0 0 0 9 n ) 。常数轮的密钥协商协议更适 用于大型群组的密钥协商，其中n 为协商的实体数。因为协商的次数不会与用户 数_ 呈o ( 1 0 9 n ) 或者多项式关系甚至更高级次的关系。以下我们将着重讨论常数论的 密钥协商协议。 2 3 1 常数轮协议的发展 1 9 9 4 年b u r m e s t e r 和d e s m e d t f l l l 提出了一个高效的两轮密钥协商协议，也称为 b d 协议，是一个非常著名的常数轮对等群组的密钥协商协议。 1 9 9 8 年b e c k e t 和w i l l i e ”1 为了最小化成员的变动引入了o c t o p u s 协议和c u b e 协议，首建了单轮的群组密钥协商协议并留下了一个公开的问题：是不是任何的 群组密钥协商方案都能满足这个目标。 2 0 0 3 年c h o i h w a n g 和l e e r 3 0 】以基于d 的方式扩展了原b d 协议，协议的安 全性依赖于随机o r a c l e 模型下的c d h 假设。他们还在随机o r a c l e 的 d h b d h ( d e c i s i o nh a s hb i l i n e a rd i f f i e h e l l m a n ) 假设下构造了基于d 的可认证的群 组密钥协商协议，而这两个协议都实现了前向安全。 山东大学硕士学位论文 同在2 0 0 3 年，b o y d 和n i e t o 3 卸提出了一个常数轮的可认证的群组密钥协商协 议，给出了其在随即o r a c l e 下的安全证明，同时满足b e c k e r - w i l l i e 的单轮问题。然 而协议并不能提供前向安全，也就是说，协议的计算是非对称的，需要一个群组 管理员在每次的群组密钥建立的时候执行复杂性为0 ( n ) 的加密和0 ( n ) 的通信。 2 0 0 4 年b r e s s o n 和c a t a l a n o 3 4 1 基于异步网络给出了另一个可证明的可认证静态 群组密钥协商协议，协议基于d d h 假设，采用标准秘密共享技术并结合了e l g m n a l 的加密方案，其中秘密共享是密钥协商的另一个常用的认证方式。然而，协议在 的计算效率方面并不是高效的，并受两方面的通信负荷，即协议执行过程中所有 成员发送的信息总数和整个执行过程中通信的比特数。 b r e s s o n ，c h e v a s s u t ，e s s i a r i 和p o i m c h e v a l t 弱1 引入了一个动态环境下的具有非 常高效的可证安全的群组密钥协商协议，这个协议适用于受限制的设备和无线的 环境。方案由三个协议组成：协议的建立( g k e s e t u p ) ，成员的离开( g k e r e m o v e ) 和成员的加入( g k e j o i n ) 。协议需要2 轮的通信并且被证明在随机o r a c l e 模型下 是安全的。然而，协议需要一个托管人作为基站。后来，n a m ，k i m 和w o n 3 6 , 3 7 1 发现了上述协议在建立( g k es e t u p ) 阶段中的某些缺点，并对其进行了修复。 2 0 0 4 年n a m ，k i m ，y a n g ，w o n “, 3 7 1 调查了目前有线、无线混合网络( 不同 的计算能力) 中贡献式群组密钥协商协议的问题，设计了一个通用的三轮协议。 协议利用用户在计算能力方面的差异并使用了一个自设计的2 轮的非可认证的协 议作为基础构建模块，这个两轮的协议非可认证协议在d d h 假设下对被动攻击是 安全的。 在2 0 0 4 的亚密会上，k m 等p 钾提出了一个非常有效的常数轮的可认证动态群 组密钥协商协议，同时对协议在随机o r a c l e 模型中c d h 假设下进行了安全分析。 2 0 0 5 年d u r r a 和b a r l m l 3 9 1 年提出了一个常数轮的密钥协商协议一d b 协议，这 个协议被认为是b u r m e s t e r 和d e s m e d t ( b d ) 协议的变形，但其比b d 协议更高效 更灵活。 2 4 形式化证明模型的发展 起初对密钥协商协议的安全性分析都是基于启发式的，也就是协商协议的设 计者或分析者对协议可能受到的各种现实攻击进行安全性分析，证明其抗攻击的 山东大学硕士学位论文 强壮性，安全性。这样就存在分析者可能只考虑了主要攻击而忽略了次要攻击。 或者对协议可能受到的攻击分析不全面的问题。 基于以上问题，1 9 9 3 年b e l l a r ea n d r o g a w a y m l 首先提出了认证密钥协商协议 的形式化模型，在他们的基础上，b l a k e w i l s o n ，j o h n s o na n dm e n e z e s1 1 6 1 在1 9 9 7 年 发展了一个适用于分布式计算的安全模型，并给出了在这个模型下安全的a k 协议 的严格安全目标定义。同时他们还给出了具体的a k 协议，并证明它在随机o r a c l e 模型下是安全的。 1 9 9 8 年b e l l a r e ，c a n e ma n dk r a w c z y k 4 1 1 引入了一个使用协议转换工具“模 子”的方法来设计和分析可认证的密钥协商协议。这个转换工具叫认证者编辑者 ( a u t h e n t i c a t o r c o m p i l e r ) ，可将任何的非可认证的协议转换为可认证的协商协议。 基于以上工作，b r e s s o n l 2 4 馏3 1 在0 1 ，0 2 年对可认证的密钥协商协议提出了形 式化的攻击者模型，采用应答的方式模拟攻击者的现实攻击，是协议安全性分析 的一个重要的发展。之后被广泛地用来对两方和多方安全协议进行分析，成为目 前协商协议安全分析的主流和热点。 2 5 本章小结 本章以分类的方式介绍了密钥协商协议以及协议形式化证明模型的发展，使 我们更全面的了解了密钥协商协议的发展历程，并为我们进一步的协议构建提供 了思路。 山东大学硕士学位论文 第3 章相关基础知识介绍 3 1 密码双线性映射 设g 1 ，g 2 是两个阶为g 的群，q 是一个加法群，g 2 是个乘法群，我们假设在 g 1 ，g 2 上求解离散对数是困难的。如果映射e ：g 1 + g l 斗g 2 满足以下特性，我们就称 它为密码双线性映射，他具有以下的特性： ( 1 ) 双线性：对所有的p ，o g 1 ，a , b z ：，e ( a p ，b q ) = e ( p ，q ) 。 ( 2 ) 非退化性：如果p 是g 1 的生成元，那么e ( p ，p ) 就是g 2 的生成元a ( 3 ) 可计算性：存在一个有效的算法计算e ( p ，0 1 。 3 2b d h 假设 ( g i ，g z ，p ) 上的双线性d i m e h e l l m a n d 均难题： 实例：已知( p ，驴，b p ，c p ) ，其中以6 ，c z ：。 问题：输出e ( e ，p ) “g 2 。 对于任何算法a ，如果p r a ( p ，a p ，b p ，印) = e ( e ，p ) “】 s ，我们就说算法4 能 以概率为占的优势解决b d h 问题。 b d h 假设( b i l i n e a rd i m e - h e l l m a na s s u m p t i o n ) ：我们假设b d h 问题是难解 的，也就是说不存在多项式时间算法能以不可忽略的优势解决b d h 问题。 3 3c d h 假设 g l 上的计算d i f f i e h e l l m a n ( c d h ) 难题： 实例：已知( p ，a p ，b p ) ，其中a ，b z ：。 问题：输出a b p 。 g 1 上解决c d h 难题的任一算法a ( 此算法是多项式时间的概率算法，其输出 为0 或1 ) 的优势函数定义为： a d v c 椭d h = p r 陋妒，a p ，b p ，a b p ) = 1 ：a ，6 r z ：】。 c d h 假设：对每一个多项式时间的概率算法a ( 其输出为0 或1 ) ，其觉得问 山东大学硕士学位论文 题的优势a d v 。c d g h 可以忽略。 3 4d d h 假设 g 1 上的判定d i f f i e - h e l l m a n ( d d h ) 难题： 实例：已知( p ，舻，b p ，c o ) ，其中a ，b ，c ez ：。 问题：判定cm o dq 是否等于a bm o dq 。如果等于，那么输出y e s ，否则输 出n o 。 g 1 上解决d d h 难题的任一算法a ( 此算法是多项式时间的概率算法，其输出 为0 或1 ) 的优势函数定义为： a d v ? p z = j p r a ( p ，a p ，b p ，铲) = i - v r a ( p ，a p ，b p ，a b p ) = 1 ：口，b ，c 6 a 石1 g 1 上的d d h 难题是容易解的：通过验证e ( a p ，b p ) = 口( p ，c o ) 可以在多项 式时间内解决g 1 上的d d h 难题。这就是著名的m o v 约化：g l 上的离散对数难 题并不比g 2 上的离散对数难题难解。 d d h 假设：对每一个多项式时间的概率算法a ( 其输出为0 或1 ) ，解决d d h 的优势a d v 。d d a h 可以忽略。 3 5d h b d h 问题 g 1 上的判定d e c i s i o nh a s hb i l i n e a rd i f f i e h e l l m a n 难题： 实例：己知( p ，a p ，b p ，c o ，) ，其中口，b ，c ，z ：，单项函数日：g 2 一艺。 问题：判定，r o o d q 是否等于h ( e ( p p ) “) m o d q ， g 。上解决d d h 难题的任一算法a ( 此算法是多项式时间的概率算法，其输出 为0 或1 ) 的优势函数定义为：a d v 秽= r r a ( p ，a p ，b p ，c p ，) = l 卜v r a ( p ，驴，b p ，妒，日( g ( p ，p ) “) ) = l 】：q b ，v 白z ：| 即：不存在一个多项式时间的概率算法能以不可忽略的优势解决这个d h b d h 问 题。 3 6 基于身份认证的协议初始化 在基于身份的密码体制中，由私钥生成中一c , ( p k g ) 生成一对主公私钥对，主公钥 是公开的。每个用户的公钥就是他的身份d ，而他所对应的私钥要由p k g 生成( 用 山东大学硕士学位论文 户私钥的生成需要用到p k g 的主私钥1 。p k g 为用户生成私钥时要验证用户的身 份，验证的方式可以是离线的。若a l i c e 要与b o b 通信，就用b o b 的d 加密