资源描述：
《开放网络环境中安全群通信的密钥管理技术研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
上海交通大学博士学位论文开放网络环境中安全群通信的密钥管理技术研究姓名：李明申请学位级别：博士专业：计算机应用指导教师：白英彩20031101 申请上海交通大学博士学位论文摘要较好的灵活性和通用性，也可以用于其它采用客户端-后台程序结构的群通信系统。最后以电子集市为例，描述了基于Spread的通用安全框架在群环境中的应用。关键词：密钥协商；动态对等群；基于身份的密码系统；Pairing；安全群通信平台；通用安全框架II 申请上海交通大学博士学位论文摘要ABSTRACTWiththerapiddevelopmentofthenetwork,alotofapplicationsbasedonthegroupcommunicationappear.Theresearchonsecurityserviceforreliablegroupcommunicationsystemsisnowaninterestingarea,andofwhichkeymanagementschemeisthemostdifficultpart.Thisthesisfocusesonthekeymanagementschemesofdynamicpeergroups.Afterstudyingofexistingschemes,wecometotheconclusionthatkeyagreementschemesbasedontreecanfitdynamicpeergroupsbest.However,theexistingschemespresentdrawbacksinperformanceorsecurityattributes.Becausebetterperformanceandsecurityarecontradictions,itisverydifficulttoimprovethesetwothingsatthesametime.Thereforethekeyagreementschemesproposedinthisthesisareinthreekinds.First,ourgoalistodecreasethecost,andthetripletreeisintroducedintothegroupkeyagreement.Second,ageneralmethodisintroducedtoprovideimplicitkeyauthenticationforbinarytreebasedschemes.Thentwoauthenticatedkeyagreementschemesareproposed.Finally,wecombinetheaboveworkandproposetwoauthenticatedtripletreebasedgroupkeyagreementschemes.Thecontributionsofthisthesisareasfollows:1.ThetripletreeandPairingarecombinedtobuildanefficientgroupkeyagreementschemePTDH.Thecommunicationalcostcausedbytheincreaseofthegroupmemberscanbeignored.ItscomputationalcostisO(log3n).Becausethecostoftree-basedschemesdependsontheheightofthetrees,using3-arytreecandecreasethecost.Astheresult,PTDHismoreefficientthanbinarytree-basedschemes.Inaddition,Pairingcanbringhighersecurityandflexibility,whichmakesPTDHsuitablefordifferentapplications.2.Anauthenticatedtwo-partykeyagreementprotocolPAGKAbasedonPairingisproposedandthenextendedtomulti-party.PAGKAinvolvesmembers’long-termkeysandsessionrandomsinthegroupkeytoprovideresistancetoknown-keyattacksandman-in-the-middleattacks.TheideabehindPAGKAcanbeusedasageneralapproachtoextendauthenticatedtwo-partykeyagreementprotocoltogroupsettings.Toavoidthecostcausedbyusingsignatures,anauthenticatedprotocolIAGKAispresentedbyextendingatwo-partyidentitybasedprotocoltogroupsettings.3.Inordertoprovideconfidentialandintegratedcommunicationserviceforgroupapplications,PAGKA,IAGKAandAGDHareimplementedandintegratedwithareliableIII 申请上海交通大学博士学位论文摘要groupcommunicationsystemSpreadtoconstitutealayeredsecuregroupcommunicationplatformprototype.Theexperimentshowsthatthetwonewschemes,PAGKAandIAGKA,canfitthedynamicpeergroupbetterthanAGDH.ThegeneralsecurityframeworkforSpreadisstudiedinthisthesis.Differentimplementationschemescanbeusedintheframeworkaccordingtotherequirementofusers.Sotheframeworkisflexibleandscalable,anditcanbeusedinothergroupcommunicationsystemswithclient-daemonarchitecture.Finally,takingthecommunicationplatformofE-marketplaceasanexample,theapplicationofthegeneralsecurityframeworkforgroupcommunicationsystemsisdescribedindetail.Keywords:keyagreement,dynamicpeergroup,Identity-BasedEncryption,Pairing,ellipticcurvecryptosystem,securegroupcommunicationplatform,generalsecurityframeworkIV 上海交通大学学位论文原创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均己在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签日期：2一吗年，，月船日 上海交通大学学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权上海交通大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。保密口，在年解密后适用本授权书。本学位论文属于不保密口。(请在以上方框内打“√”)学位论文作者签名ElTa：罗年寥月多D日指导教师签名：≤7夥日钟纩月沙 申请上海交通大学博士学位论文目录图表目录图1-1密钥树.........................................................-8-图2-1BDH与其它困难问题的归约关系..................................-14-图2-2成员加入群时TGDH密钥树的更新.................................-18-图2-3成员离开群时TGDH密钥树的更新.................................-18-图2-4STR密钥树....................................................-19-图2-5成员加入群时STR密钥树的更新..................................-20-图2-6成员离开群时STR密钥树的更新..................................-20-图3-1PTDH密钥树...................................................-27-图3-2成员加入群时PTDH密钥树的更新.................................-28-图3-3PTDH成员加入协议.............................................-30-图3-4PTDH成员离开协议.............................................-31-图3-5成员离开群时PTDH密钥树的更新.................................-32-图4-1基于Pairing的两方密钥协商协议................................-38-图4-2PAGKA密钥树..................................................-40-图4-3PAGKA加入协议................................................-41-图4-4成员加入群时PAGKA密钥树的更新................................-42-图4-5PAGKA离开协议................................................-43-图4-6成员离开群时PAGKA密钥树的更新................................-43-图5-1IAGKA密钥树..................................................-49-图5-2成员加入群时IAGKA密钥树的更新................................-50-图5-3成员离开群时IAGKA密钥树的更新................................-55-图6-1TAK-4协议....................................................-58-图6-2两方TAK-4协议................................................-58-图6-3TPAGKA密钥树.................................................-59-图6-4成员加入群时TPAGKA密钥树的更新...............................-60-图6-5成员离开群时TPAGKA密钥树的更新...............................-61-图6-6基于身份的可认证的三方密钥协商协议............................-62-图6-7基于身份的可认证的两方密钥协商协议............................-62-图6-8TIAGKA密钥树.................................................-63-图7-1安全群通信框架................................................-68-图7-2局域环境中成员加入群时的执行时间..............................-75-图7-3局域环境中成员离开群时的执行时间..............................-76-图7-4广域环境中成员加入群时的执行时间..............................-77-图7-5广域环境中成员离开群时的执行时间..............................-78-图8-1Spread体系结构...............................................-82-图8-2认证框架......................................................-83-图8-3加入控制过程..................................................-85-图8-4权限决策过程..................................................-86-图8-5PAM的体系结构................................................-89-图8-6电子集市应用的认证框架........................................-89-V 申请上海交通大学博士学位论文目录表2-1TGDH复杂性分析...............................................-17-表2-2STR复杂性分析................................................-21-表2-3AGKA复杂性分析...............................................-23-表3-1PTDH方案使用的符号...........................................-26-表3-2PTDH复杂性分析...............................................-34-表4-1PAGKA方案使用的符号..........................................-39-表4-2PAGKA复杂性分析..............................................-45-表5-1DH和ECC密码操作的执行时间...................................-55-表5-2IAGKA复杂性分析..............................................-55-表6-1TPAGKA复杂性分析.............................................-65-表6-2TIAGKA复杂性分析.............................................-65-表7-1IBEAPI使用的主要数据结构....................................-70-表7-2PAGKA使用的主要数据结构......................................-71-VI 申请上海交通大学博士学位论文目录ListofFiguresandTablesFigure1-1KeyTree................................................................................................................-8-Figure2-1ReductionRelationshipbetweenBDHandOtherProblems...............................-14-Figure2-2TGDHTreeUpdate(Join)....................................................................................-18-Figure2-3TGDHTreeUpdate(Leave).................................................................................-18-Figure2-4KeyTreeforSTR................................................................................................-19-Figure2-5STRTreeUpdate(Join).......................................................................................-20-Figure2-6STRTreeUpdate(Leave)....................................................................................-20-Figure3-1KeyTreeforPTDH.............................................................................................-27-Figure3-2PTDHTreeUpdate(Join)....................................................................................-28-Figure3-3PTDHJoinProtocol............................................................................................-30-Figure3-4PTDHLeaveProtocol.........................................................................................-31-Figure3-5PTDHTreeUpdate(Leave).................................................................................-32-Figure4-1Pairing-basedTwo-partyKeyAgreementProtocol.............................................-38-Figure4-2KeyTreeforPAGKA..........................................................................................-40-Figure4-3PAGKAJoinProtocol.........................................................................................-41-Figure4-4PAGKATreeUpdate(Join).................................................................................-42-Figure4-5PAGKALeaveProtocol......................................................................................-43-Figure4-6PAGKATreeUpdate(Leave)..............................................................................-43-Figure5-1IAGKAKeyTree................................................................................................-49-Figure5-2IAGKATreeUpdate(Join)..................................................................................-50-Figure5-3IAGKATreeUpdate(Leave)...............................................................................-55-Figure6-1TAK-4.................................................................................................................-58-Figure6-2Two-partyTAK-4................................................................................................-58-Figure6-3TPAGKAKeyTree.............................................................................................-59-Figure6-4TPAGKATreeUpdate(Join)...............................................................................-60-Figure6-5TPAGKATreeUpdate(Leave)............................................................................-61-Figure6-6Identity-basedTripartyKeyAgreementProtocol...............................................-62-Figure6-7Identity-basedTwo-partyKeyAgreementProtocol............................................-62-Figure6-8TIAGKAKeyTree..............................................................................................-63-Figure7-1ArchitectureofSecureGroupCommunication...................................................-68-Figure7-2CostofMemberJoininLAN.............................................................................-75-Figure7-3CostofMemberLeaveinLAN..........................................................................-76-Figure7-4CostofMemberJoininWAN.............................................................................-77-Figure7-5CostofMemberLeaveinWAN..........................................................................-78-Figure8-1ArchitectureofSpread........................................................................................-82-Figure8-2ArchitectureofAuthentication............................................................................-83-Figure8-3ProcessofAdmissionControl.............................................................................-85-Figure8-4ProcessofAuthorizationDecision......................................................................-86-Figure8-5ArchitectureofPAM...........................................................................................-89-Figure8-6ArchitectureofAuthenticationinE-marketplace................................................-89-VII 申请上海交通大学博士学位论文目录Table2-1ComplexityAnalysisforTGDH...........................................................................-17-Table2-2ComplexityAnalysisforSTR...............................................................................-21-Table2-3ComplexityAnalysisforAGKA...........................................................................-23-Table3-1NotationsforPTDH..............................................................................................-26-Table3-2ComplexityAnalysisforPTDH............................................................................-34-Table4-1NotationsforPAGKA...........................................................................................-39-Table4-2ComplexityAnalysisforPAGKA.........................................................................-45-Table5-1TimeCostforDH&ECC....................................................................................-55-Table5-2ComplexityAnalysisforIAGKA.........................................................................-55-Table6-1ComplexityAnalysisforTPAGKA......................................................................-65-Table6-2ComplexityAnalysisforTIAGKA.......................................................................-65-Table7-1DataStructureforIBEAPI...................................................................................-70-Table7-2DataStructureforPAGKA...................................................................................-71-VIII 申请上海交通大学博士学位论文绪论第1章绪论1.1研究背景、目标及意义随着网络技术的飞速发展和Internet规模的爆炸性增长，在开放性网络环境下出现了各种各样的分布式群通信（GroupCommunication）应用。这些应用服务在网络协议栈的许多层和现代计算的许多应用领域都十分常见，如网络多址传送、电视电话会议、分布式仿真、备份服务器（如数据库、Web等）及其它群件应用等等。它们通常工作在缺乏安全的开放网络环境（如Internet）中，其网络用户群具有动态性（称该用户群为动态对等群，Dynamicpeergroups，动态对等群），群成员可以随时加入或离开，并且采[1]用多对多的通信模式。群通信的安全性对于构建动态对等群网络环境下的分布式应用至关重要。在安全群通信中，通信层往往用于处理异步网络行为，保证可靠的、顺序的消息传输，从而为上层提供高度可靠的群通信服务。当前，安全群通信面临的挑战是如何设计一个安全、高效、健壮和可扩展的群密钥管理方案，其目的是使群通信中的参与各方得到一个共享密钥，称为群密钥（groupkey）。群密钥可用于加密、认证和签名等安全服务。由此可见，群密钥管理是其它群通信安全业务（如信息的保密性、可用性和完整性）的前提。另外，群密钥管理的开销几乎相当于群通信系统安全的全部代价，因为可以通过选用流密码等高速密码算法来减少加密开销，利用每秒几个G比特的MAC算法使得提供完整性所需要的开销很小，而密钥管理往往需要耗时的指数运算以及群成员之间通信的额外开销。群密钥的生成往往通过密钥建立（KeyEstablishment）协议来实现。总体上，密钥建立协议可分为两类：基于某种可信第三方（TTP）的（集中式）密钥分配（Key[1]Distribution）协议和（分布式）密钥协商（KeyAgreement）协议。在集中式协议中，只有一方（可信任的第三方或某个群成员）控制整个群，它不需要依赖于任何辅助方来进行密钥管理，密钥分发过程比较简单。群的保密性依赖于群控制器的正常工作，如果控制器失败，就不能正常地进行密钥生成和分发，群的保密性也就无法保证。另外，如果群较大，一个控制器就很难进行管理，有可能成为性能的瓶颈，这就造成了可扩展性问题。而动态对等群中可能不存在可信第三方，并且群的动态性决定了经常要进行群密钥更新，因此集中式协议无论在安全性方面还是在性能方面都不能满足动态对等群的要求。-1- 申请上海交通大学博士学位论文绪论分布式协议则要求每个成员平等地提供一个随机的密钥数值，群密钥K是所有密钥数值的函数，可以表示成f(,,)rr1"n，其中f()是一个单向函数，ri是第i个成员提供的随机秘密数值。群密钥的计算方法必须保证：（1）每一个提供密钥数值的成员都能计算出K。（2）在不知道任何ri的情况下不能得到有关K的任何信息。[4]（3）所有ri是秘密的，以便在后续的密钥协商过程中重复使用。显然分布式协议能够避免集中式方案中的可信第三方和单点故障问题，可以获得较好的可扩展性和容错能力，同时也与动态对等群的特点相吻合。因此，动态对等群中的密钥管理一般采用密钥协商协议。动态对等群的高度动态性意味着经常要进行密钥重发，这就要求对密钥协商的开销进行严格限制。但性能和安全性是一对矛盾，往往顾此失彼，因此密钥协商方案要力求在性能和安全性两个方面达到平衡。这也正是本文的研究重点，具体目标是：（1）设计满足动态对等群安全要求的、高效的、可扩展的密钥协商方案。（2）实现所设计的方案，并集成到一个可靠的群通信系统中。（3）研究如何将安全的动态对等群系统作为实现各种协作式应用系统的底层通信框架。安全高效的密钥协商机制是保证动态对等群通信系统安全性的关键，也是动态对等群安全群通信系统能否成为开放式网络环境下各种协作式应用的通信框架的决定性因素，因此对其的研究与实现具有重要的理论意义和巨大的实用价值，拥有广阔的应用前景。1.2研究现状及不足近年来，动态对等群中的密钥协商技术逐渐成为Internet安全通信中新的研究热点[2]。主要集中在协议的可扩展性、健壮性以及提供可证明的安全性三个方面。在群通信中，群成员的增加以及频繁的成员关系变化都会导致实现现有的密钥协商协议的代价越来越高，因此有必要提高协议的可扩展性。为了得到安全、健壮的群密钥协商方案，必须把安全的群密钥协商协议与可靠的群通信服务有效的结合起来。群密钥协商涉及到多个成员，协商过程比两方协商复杂得多，更容易受到形式多样的攻击。仅通过简单的攻击分析很难确保协议的安全，因此需要把各种可能的攻击抽象出来，并通过严格的证明[3]来说明协议对攻击的抵抗能力，即提供可证明的安全性。下面将首先介绍群密钥协商方案在安全性和性能方面可能达到的目标，然后概述前-2- 申请上海交通大学博士学位论文绪论人在该领域的相关工作。1.2.1群密钥协商方案的目标在理想情况下，密钥协商方案应该能够使指定的成员共享一个密钥，该密钥随机地均匀分布在密钥空间中，并且任何未授权的个体（计算能力有限）都不能得到关于该密[4]钥的任何信息。但在实际情况下，达到上述抽象目标是非常困难的，并且准确描述协议的具体目标也很困难。尽管如此，在过去几年中提出了一些具体的安全性目标和性能[4]目标。其中安全属性主要有以下几个方面：假设群密钥改变了m次，群密钥的序列集合表示为K={K0,…,Km}。（1）群密钥保密（GroupKeySecrecy）确保被动攻击者不能计算出任何一个群密钥Ki。（2）后向保密（BackwardSecrecy）知道群密钥的一个连续子集（如：{Ki,Ki+1,…,Kj}）的被动攻击者不能得到任何后续群密钥Kl（0≤i，对于成员M1来说，其计算过程如下：kRr<2,0>kR==<>1,0R<>2,1<>0,0<1,1><1,1>（1.5）由此可见，只要M1能得到盲密钥R<1,1>、R<2,1>就能计算出群密钥。-7- 申请上海交通大学博士学位论文绪论K=k<0,0>groupkeyblindedkeyk/bkr/R<1,0><1,0><1,1><1,1>secretkeyM3secretshareblindedkeyr/Rr/R<2,0><2,0><2,1><2,1>MM21图1-1密钥树Figure1-1KeyTreeTGDH方案的安全性依赖于DDH问题的困难性。DDH保证了群密钥的保密性，即使被动攻击者知道所有盲密钥也不能计算出群密钥。当成员关系发生变化时，需要更新群密钥，使之包含新的秘密信息，因此相应的群密钥也发生了变化，从而保证了前向保密和后向保密。该方案的通信轮数为常数。取模求幂运算的次数则取决于密钥树的高度和密钥树的平衡程度以及新成员加入群时插入点的位置或当前成员离开群时离开点的位置。早期的密钥管理方案要同时考虑减小计算开销和通信开销，而二者是一对矛盾，往往顾此失彼。幸运的是在过去十几年中，计算机的计算能力有了大幅度提高，相比之下，网络速度的提高远远不能满足需要，这使得网络延迟（特别是广域网）成为影响性能的[12]主要因素。在这种情况下，要使得协议更高效，就有必要适当增加计算量，而尽量减少通信量。另外一种基于树的密钥协商方案STR就采用了这种设计思想。STR方案的密钥树是一种完全不平衡的二叉树，而TGDH方案则尽量保持密钥树平衡。STR方案可以看作TGDH方案的特殊情况，因此计算密钥的方法是相同的，不同的是密钥树的更新方法和发起人的选择方法。STR方案是目前通信开销最小的一种方案，它对于每种成员关系事件的通信轮数都是常数。所提供的安全属性与TGDH方案相同。虽然TGDH和STR方案提供了很好的性能，但都假设成员间的通信是真实可靠的，没有提供密钥认证，很显然不能抵抗主动攻击。AGKA和AGKA-G是目前仅有的两种[13]提供密钥认证的基于树的群密钥协商方案，都是由Perrig提出的。它们的密钥树结构与TGDH相同，只是在每一轮执行可认证的两方密钥协商协议。在AGKA方案中，认证是通过数字签名和PKI来实现的。当两个成员交换信息时，它们首先要对幂、对方在-8- 申请上海交通大学博士学位论文绪论密钥树中的位置以及时间戳进行签名。为了避免使用证书和PKI所引起的大量通信开销和计算开销，Perrig引入了Günther的认证方案。该方案使用一个密钥认证中心KAC来预认证用户，并分发相应的私有信息和公共信息。AGKA-G的每一轮密钥协商中的两个成员利用这些信息和临时信息来生成中间节点的密钥，然后分别用该节点的左右两个子节点的密钥加密后广播，只有相关的合法成员才能解密得到新生成的密钥。AGKA和AGKA-G方案的安全性是建立在DDH问题之上的，提供了隐含密钥认证、前向保密、后向保密等安全属性。但由于认证是间接的，因此没有提供完善前向保密。方案需要执行的轮数由密钥树的高度决定，需要交换的信息数与群成员数目成正比，求幂运算的次数也取决于密钥树的高度。由此可见，虽然这两种方案提供了密钥认证，但其开销比前两种无认证的方案大得多。1.3主要研究内容及成果在充分研究了现有群密钥协商方案的优点和不足的基础上，本文把研究重点放在适用于动态对等群的基于树的方案上，提出了五种新方案。这些新方案在尽量减少开销的前提下提供了密钥认证、完善前向保密等安全属性。基于树的方案的通信开销或计算开销取决于密钥树的高度，因此要减小开销，应该尽量减小密钥树的高度。而多叉树的高度小于具有相同叶节点数目的二叉树的高度。基于上述思想，本文第3章将三叉树和超奇异椭圆曲线上的Pairing结合起来，提出了一种高效的群密钥协商机制PTDH。为了适应动态对等群的高度动态性，减小密钥协商的开销，同时提供对主动攻击的抵抗能力，本文第4章和第5章通过不平衡二叉树把可认证的两方密钥协商协议扩展到多方，提出了两种高效的可认证的群密钥协商方案PAGKA和IAGKA。其中，PAGKA[25]方案把本文提出的一种基于椭圆曲线上的TatePairing的可认证的两方密钥协商协议与目前通信量最小的无认证方案STR结合起来，在保持STR性能优势的基础上，弥补了STR不能抵抗主动攻击的不足。IAGKA是一种基于身份的方案，把不平衡二叉树与基于身份的密码机制结合起来，不但保持了良好的性能，而且提供了隐含密钥认证和完善前向保密等安全属性。本文第6章将PTDH、PAGKA和IAGKA三种方案的思想结合起来，把三叉树引入到可认证的密钥协商协议中去，提出了分别与PAGKA和IAGKA相对应的两种方案：基于Pairing和三叉树的可认证的群密钥协商协议TPAGKA以及基于身份和三叉树的可认证的群密钥协商协议TIAGKA。这两种方案的通信开销随成员数目的增加而增长的幅-9- 申请上海交通大学博士学位论文绪论度可忽略，计算开销为On(log)，比PAGKA和IAGKA的开销小。在安全性方面所提3供的服务与PAGKA和IAGKA相当。[29]本文第7章实现了PAGKA、IAGKA和AGDH三种方案，并与群通信系统Spread集成起来，构成了一个分层的安全群通信平台原型。我们在该平台上测试了三种方案的加入协议和离开协议的性能，通过比较可知，这两种新方案能够更好地适应动态对等群在性能方面的要求。上述安全群通信平台仅保证了群通信的保密性和完整性，对客户的访问权限没有任何控制，而要实现一个实用的安全群通信平台，必须加入访问控制机制。本文第8章研究了群通信系统的通用安全框架，给出了适用于Spread系统的身份认证框架、加入控制框架和访问控制框架。最后以电子集市中的通信平台为例，描述了群通信系统通用安全框架的应用。1.4论文结构本文的结构如下：第2章是介绍了椭圆曲线密码机制、有代表性的基于树的无认证群密钥协商方案和可认证的群密钥协商方案。第3章详细阐述了基于三叉树的群密钥协商方案PTDH。第4章提出基于TatePairing的群密钥协商方案PAGKA，并进行了详细的性能和安全性分析。第5章给出了基于身份的群密钥协商方案IAGKA的详细描述。第6章利用三叉树分别对PAGKA和IAGKA方案进行扩展，提出两种可认证的群密钥协商方案TPAGKA和TIAGKA。第7章实现了PAGKA、IAGKA和AGDH三种方案，并与Spread系统集成起来，构成一个安全的群通信平台。我们在该平台上测试了这三种方案的执行时间，并进行了比较。第8章研究了Spread系统的通用安全框架，并以电子集市中的通信平台为例，描述了该框架的应用。第9章总结所做的工作，并提出了下一步的研究方向。-10- 申请上海交通大学博士学位论文群密钥协商的相关工作第2章群密钥协商的相关工作2.1密码学基础2.1.1公开密钥密码学公钥密码机制是由WhitfieldDiffie和MartinHellman在1976年的美国国家计算机[15]会议上首次提出的。他们在稍后出版的开创性论文“NewDirectionsinCryptography（密[16]码学新方向）”中提出了第一个公开密钥算法——Diffie-Hellman算法，其安全性源于在有限域上计算离散对数比计算幂更困难。Diffie-Hellman算法能够用于两方之间的密钥协商，但不能用于加密或解密。假设进行协商的两方分别是A和B。首先它们协商一个大素数p，α是模p的本原元。这两个素数可以是公开的，因此可以通过不安全的途径来协商。协商过程如下：（1）A和B分别选择一个大的随机整数x∈[1,p-1]和y∈[1,p-1]。x（2）A计算X=αmodp。y（3）B计算Yp=αmod。（4）A和B交换X和Y。x（5）A计算KY=modp。y（6）B计算KX=modp。xy协商后的秘密密钥Kp=αmod。窃听者（被动攻击者）只知道p、α、X和Y，但无法通过计算离散对数来恢复x和xyy，因此不能计算出秘密密钥K。而如果攻击者E（主动攻击者）把α和α分别替换成αx和αy，那么E就能计算出A和B分别计算得到的密钥αxy和αxy，因此能够解密二者交换的加密信息。由此可见，基本的DH协议不能抵抗中间人攻击。1976年以后，除DH算法外，还提出了多种公开密钥算法，其中有很多是不安全的。[17]如：Merkle-Hellman背包算法把一个NP完全问题（背包难题）应用于公开密码学，[18]能用于加密，由AdiShamir改进后也可以用于数字签名，但该算法是不安全的。RSA[19]算法是第一个比较完善的公开密钥算法，既能用于加密，也能用于数字签名。RSA的安全性基于大素数分解的难度。其公开密钥和私有密钥是一对大素数的函数，从公开-11- 申请上海交通大学博士学位论文群密钥协商的相关工作[20][21]密钥和密文中恢复出明文的难度等价于分解两个大素数之积。ElGamal算法可用于[22]加密和数字签名，其安全性依赖于计算有限域上离散对数的难度。DSA签名算法是Schnor和ElGamal签名算法的变型，其安全性基础也是有限域上的离散对数问题。1988年，WhitfieldDiffie提出，绝大多数公开密钥算法都是基于以下三种疑难问题[23][24]之一：（1）背包问题：给定一个互不相同的数组成的集合，找出一个子集，其和为N。x（2）离散对数：如果p是素数，g和M是整数，找出x满足gM≡(mod)p。（3）因子分解：设N是两个素数的乘积，则（a）分解N。（b）给定整数M和C，寻找d满足dM≡CN(mod)。e（c）给定整数e和C，寻找M满足M≡CN(mod)。2（d）给定整数x，判断是否存在整数y满足x≡yN(mod)。实践证明，并不是所有基于这些问题的公开密钥算法都是安全的。公开密钥算法的强度更多地取决于它所基于问题的复杂性。公开密钥密码学如此狭窄的数学基础令人担忧，因子分解或离散对数问题的突破将使所有公开密钥算法不安全。2.1.2椭圆曲线密码机制自1985年NeilKoblitz和VictorMiller分别提出了椭圆曲线密码系统（EllipticCurveCryptosystemECC）以来，ECC逐步成为一个备受关注的密码学分支，1997年以后更是[59]形成了一个研究热点。椭圆曲线密码体制的优点是在安全性相当的前提下可以使用比传统公开密钥密码机制短得多的密钥。一般认为，对于p阶域上的椭圆曲线密码体制，当p的长度为160[60]位时，其安全性相当于使用1024位模数的RSA。密钥短意味着较低的带宽和存储要求，这在某些应用中可能是决定性的因素。椭圆曲线密码体制的优点还在于它所依赖的数学难题不是传统的大整数分解或素数域乘法群上的离散对数问题。因为大整数分解及离散对数问题目前受到亚指数算法的严重威胁，并且数学背景狭窄。这引起人们的担忧，并努力寻找新的数学难题作为密码资源。椭圆曲线资源丰富，同一个有限域上存在着大量不同的椭圆曲线，这为安全性增加了额外的保证，也为软、硬件实现带来方便。由于椭圆曲线上的一次群运算最终化为其对应有限域上不超过15次的乘法运算，因而便于实现。-12- 申请上海交通大学博士学位论文群密钥协商的相关工作在执行速度方面，目前难以对椭圆曲线密码体制与现有密码体制（如RSA、DSA等）作出准确的定量比较。粗略地说，椭圆曲线密码体制的执行速度比对应的离散对数[61]体制快，签名和解密比RSA快，但签名验证和加密比RSA慢。对椭圆曲线密码体制的安全性分析也引起了各国密码学家及有关部门的关注与重视，但成果却并不丰硕，也许这可视为椭圆曲线密码体制具有高强度的一种证据。因此大多数密码学家对这种密码[59]体制的前景持乐观态度，认为近期在某些领域可能取代RSA、DSA等密码(签名)体制。现有的椭圆曲线密码体制都是从其它群中平移而来，并未针对椭圆曲线产生新型密码体制，而这种平移主要是对基于离散对数问题的密码体制。x设G是有限域Fq上的一个循环子群，a,b∈G，若存在正整数x使得a=b，则x称为在群G中b的以a为底的离散对数，记为x=logb。给定a,b∈G，求x=logbaa称为G中的离散对数问题。特别地，E(Fq)是Fq上的一个椭圆曲线，若P,Q∈E(Fq)，求正整数x使得xP=Q，称为椭圆曲线离散对数问题。2.1.3Pairing假设G1是一个q阶的加法群，G2是一个q阶的乘法群，则Pairing就是一个便于计[62]算的双线性映射eGGˆ:11×→G2。典型情况下，G1是一个有限域上的一个椭圆曲线群的子群，G2是相关有限域上的乘法群的一个子群，eˆ则可以从该椭圆曲线上的Weil[63][64]Pairing或TatePairing派生出来。另外，我们假设存在一个元素P∈G1使得ePPˆ(,)1≠。对于Q,W,Z∈G1，双线性映射eˆ具有以下性质：eQWZˆˆ(,+)(,)(,)=eQWeQZiˆ(2.1)eQWZˆˆ(,+=)eQZeWZ(,)iˆ(,)(2.2)若a∈Zq，QG∈1，则aQ表示Q与自身相加a-1次。由eˆ的双线性性质可以得到如下结论：对任意Q,W∈G1，a,b∈Zq，有abeˆ(aQ,bW)=eˆ(abQ,W)=eˆ(Q,abW)=eˆ(Q,W)="(2.3)最初，WeilPairing的存在被认为对密码学来说是一件坏事。例如，Menezes、Okamoto[63]和Vanstone发现在一些被称为超奇异椭圆曲线（supersingularcurves）的特殊曲线上，通过WeilPairing可以把椭圆曲线上的离散对数问题规约成有限域上的离散对数问题。[26]因此最初超奇异椭圆曲线是被排除在ECC之外的，直到Joux提出了一种基于超奇异-13- 申请上海交通大学博士学位论文群密钥协商的相关工作椭圆曲线上的WeilPairing的三方Diffie-Hellman协议才改变了这种情况。Joux的文章[27][65][66][67][68][69]发表之后，出现了大量其它应用，包括基于身份的密码机制和签名算法。基于Pairing的密码系统的安全性基础是Bi-linearDiffie-Hellman（BDH）假设，即abc给定P,aP,bP,cP∈G1，在多项式时间内计算出ePPˆ(,)是不可行的。相对于其它困难问题（如：DL、CDH、DDH）来说，对BDH的研究还很不成熟，但我们可以通过它[65]们之间的归约关系来说明BDH的安全性。G1和G2是两个q（大素数）阶循环群，相关困难问题的定义如下：（1）DDH：给定PxPyPzP,,,∈G；判断xyP=zP?G11xyzxyz（2）DDH：给定gggg,,,∈G；判断g=g?G22（3）CDH：给定PxPyP,,∈G；计算出xyP。G11xyxy（4）CDH：给定ggg,,∈G；计算出g。G22x（5）DLg：给定,g∈Gx；计算出。G22（6）DL：给定PxP,；计算出。xG1（7）BPI：给定QGePQ∈∈,(,)ˆG；计算出。P12xyz（8）BDH：给定PxPyPzP,,,∈G；计算出ePPˆ(,)。1BDH可以归约成大部分传统的离散对数问题和DH问题，但还不存在从其它问题到BDH的归约。图2-1给出了上述问题的归约关系，其中B⇒A表示由问题B到问题A的多项式图灵归约，倾斜的箭头也表示归约。BDH⇒CDHG⇒DLG⇒DLG112DDHG⇒CDHG⇒BPI22图2-1BDH与其它困难问题的归约关系Figure2-1ReductionRelationshipbetweenBDHandOtherProblems2.1.4基于身份的密码机制1984年，Shamir提出了基于身份的密码体制（Identity-basedEncryptionIBE），其初[71]衷是简化Email系统的证书管理。事实上，IBE能够简化任何需要管理大量公钥的系-14- 申请上海交通大学博士学位论文群密钥协商的相关工作统，因为IBE不把大量的公钥存储在系统中，而是由用户名派生出公钥。从1984年至[72][73][74][75][76][27]今已经提出了多种基于身份的密码方案。Boneh和Franklin提出的基于[27]Weilpairing的系统是其中较高效的一种，因为它是工作在椭圆曲线上的，而椭圆曲线密码体制的优点就在于用小得多的密钥长度达到与当前常用公钥体制相同的安全等级，这不仅减少了通信开销而且降低了加解密操作的复杂度。Boneh-FranklinIBE系统是建立在双线性映射eGGˆ:11×→G2（G1和G2是q阶循环群）之上的，其安全性基础是BDH假设。系统的核心是一个密钥生成中心（KGC），负责在系统初始化时产生系统参数并根据用户的身份为其产生私钥。系统的建立过程如下：KGC随机选择一个主密钥s∈[1,q-1]和一个随机点PG∈1，计算PKGC=sP并公布(,PPKGC)。身份为ID的用户的公/私钥对为（QID,SID），其中QHID()=ID，*HG:0,1{}→1是一个散列函数，SID=sQID，由KGC计算给出。存储在KGC中的主密钥可以通过门限密码技术分成多个子密钥，每个子密钥存储在不同的地方，从而构成一个分布式KGC。用户的私钥可以由分布式KGC通过标准的秘密共享算法来生成，并且不需要重新构造主密钥，这使得整个系统更加健壮。目前用于公钥密码体制的Pairing有WeilPairing和TatePairing两种，二者具有相[65][70]似的属性，但TatePairing在计算时比WeilPairing更高效。虽然Boneh-FranklinIBE系统使用了WeilPairing，为了进一步提高效率，本文在实现具体方案时用TatePairing代替其中的WeilPairing。2.2群密钥协商方案由于本文的研究重点是基于树的群密钥协商方案，因此本节主要介绍其中较好的两[11][12]种TGDH和STR。2.2.1TGDH方案TGDH协议具有如下特点：（1）最终的群密钥包含所有成员的秘密信息。（2）群增大时，新成员的秘密信息作为群密钥的一部分，旧成员的秘密信息保持不变。（3）群减小时，剩余成员中至少有一个成员的秘密信息要改变。-15- 申请上海交通大学博士学位论文群密钥协商的相关工作（4）发送者对所有消息进行签名。本文第1.2.2节简要介绍了TGDH的基本协议，本节主要介绍当成员关系发生变化时密钥更新的过程。这里所指的成员关系变化主要是新成员加入群或当前成员离开群。为了提供前向保密和后向保密，必须在成员关系发生变化时，更新一部分节点的密钥信息，成员要计算出新群密钥就必须知道这些信息。为了减少重复计算，进一步提高效率，每个协议都根据一定的原则确定一个成员负责计算这些信息，并广播给其它成员，这个特殊成员称为发起人。下面说明密钥更新协议的执行过程。2.2.1.1密钥更新协议当新成员加入群时，插入节点是最右最浅的节点，以确保插入不会增加密钥树的高度。如果密钥树是平衡二叉树，那么新成员就成为根节点。以插入节点为根的子树中最右边的叶节点是发起人。它首先要改变自己的秘密密钥，然后计算所有被改变的秘密密钥和盲密钥。并且把新密钥树上所有的盲密钥广播给其它成员。其它成员接收到消息后计算出新的群密钥。图2-2显示了成员M4加入群{M1,M2,M3}时密钥树的变化。M3是发起人，它执行如下操作：（1）把节点<1,1>更名为<2,2>；（2）产生一个新的内部节点<1,1>和一个新的叶节点<2,3>；（3）把节点<1,1>作为节点<2,2>和<2,3>的父节点。因为所有成员都知道bk<2,3>和bk<1,0>，因此M3能够计算出新的群密钥K<0,0>。所有其它成员也分别执行步骤（1）和步骤（2），但不能立即计算出群密钥。只有接收到发'起人M3广播的盲密钥（包括：bk<2,0>、bk<2,1>、bk<1,1>和bk<2,2>），每个成员才能计算出'k<1,0>新的群密钥。对M1和M2来说，群密钥为bk<>1,1。对M3来说，群密钥为'k<>2,2'k<>2,3bkkb<>1,1=bkk<>2,3kb<>1,1k<>2,2<>1,0<>1,0。对M4来说，群密钥为bk<>1,0=bk<>1,0。当有成员离开群时，以离开成员的兄弟节点为根的子树中最右边的叶节点是发起人。发起人先选择一个新的秘密密钥，计算密钥路径上的所有密钥，并向群广播新的盲密钥集合，这样所有的成员都能够计算出新的群密钥。图2-3显示了成员M3离开群{M1,M2,M3,M4,M5}时密钥树的变化。M3离开群后，每个剩余成员删除节点<1,1>和<2,2>。''''密钥树更新后，发起人M5产生一个新的秘密密钥k<2,3>，计算k<1,1>、k<>0,0、bk<>2,3和'bk，并广播其中的盲密钥。接收到该广播消息后，所有成员都能计算出新的群密钥。<>1,1-16- 申请上海交通大学博士学位论文群密钥协商的相关工作'k<1,0>对M1和M2来说，群密钥为bk<>1,1。对M4来说，群密钥为:'k'bk'k<2,2>bk<>1,1=bk<>2,3（2.4）<>1,0<>1,0对M5来说，群密钥为：'kb''kk<2,3>bk<>1,1=bk<>2,2（2.5）<>1,0<>1,02.2.1.2安全性与复杂性分析TGDH协议的安全性依赖于DDH问题。由上一节中的描述可以看出，每当有成员加入或离开群时，发起人总是要改变自己的秘密密钥，使得处在发起人所对应的叶节点到根节点之间的节点的密钥发生变化，最终产生一个新的群密钥，并且该密钥不能由旧密钥推算出来。因此该协议提供的安全属性包括：群密钥保密、前向保密、后向保密和密钥独立。很显然，它没有提供密钥认证，因为在整个协商过程中没有包含能唯一标识群成员身份的秘密信息。通信开销的衡量指标是通信的轮数、单播次数和广播次数。计算开销是通过比较各协议中取模求幂操作和签名/验证操作的执行次数来粗略衡量的，考虑到分布式系统的特点，在协议的最后一步进行并行运算可以缩短计算时间。因为TGDH协议的开销取决于成员数目、密钥树的平衡程度以及成员加入或离开的位置，表2-1给出了TGDH协议在理想情况下的最大开销，并与GDH协议进行了比较。表2-1TGDH复杂性分析Table2-1ComplexityAnalysisforTGDH方案事件轮数单播广播签名验证取模求幂TGDH加入202223h-4离开101113h-4GDH加入4n＋214n+3n+3离开10111n-1注：n是当前群成员的数目，h是密钥树的高度。由表2-1可以看出，TGDH协议的通信开销为常数，计算开销为O(logn)。相比之下，GDH的加入协议的通信开销远远大于TGDH，为O(n)，而离开协议的通信开销与TGDH相当。GDH的计算开销大于TGDH，为O(n)。-17- 申请上海交通大学博士学位论文群密钥协商的相关工作BeforeJoinAfterJoin<0,0><0,0>NewNode<1,0><1,1><1,0><1,1>M3<2,0><2,1><2,0><2,1><2,2><2,3>M1M2M1MM3M42SponsorNewMember图2-2成员加入群时TGDH密钥树的更新Figure2-2TGDHTreeUpdate(Join)BeforeLeaveAfterLeave<0,0><0,0><1,0><1,1><1,0><1,1><2,0><2,1><2,2><2,3><2,0><2,1><2,2><2,3>MMMM1245MMM123<3,6><3,7>MM45Sponsor图2-3成员离开群时TGDH密钥树的更新Figure2-3TGDHTreeUpdate(Leave)-18- 申请上海交通大学博士学位论文群密钥协商的相关工作2.2.2STR方案STR方案可以看作是TGDH方案的一种特殊情况。两种方案使用完全相同的密钥计算方法，只是密钥树的结构不同。TGDH使用的密钥树是平衡二叉树，而STR使用的是一种完全不平衡的二叉树，目的是尽量减少通信开销。图2-4给出了STR密钥树的例子。在本节中，我们主要讨论密钥更新协议。IN<4>k4LN<4>IN<3>k/bkr/R3344INM4<2>k/bkr/R2233LNM<3>3IN<1>r1/R1r2/R2LN<2>LN<1>M1M2图2-4STR密钥树Figure2-4KeyTreeforSTR2.2.2.1密钥更新协议成员关系变化后，群密钥也必须改变。STR协议的核心思想与TGDH类似，即改变一些成员的秘密密钥，引起密钥树中内部节点的密钥的变化，发起人计算这些新密钥，并把包含所有盲密钥的密钥树广播给所有成员。最终每个成员都能利用这些盲密钥和自己的秘密密钥计算出群密钥。两种方案密钥树结构的不同使得发起人的选择原则略有不同。图2-5给出了M4加入群{M1,M2,M3}时密钥树的变化，发起人是最顶端的叶节点，即M3。当M3广播了所有盲密钥（包括新计算出来的）后，所有成员都能利用自己的秘'''密密钥和接收到的盲密钥计算出新的群密钥：M4用bk3可以计算出k4，M1和M2用R3和'R也可以计算出k。44-19- 申请上海交通大学博士学位论文群密钥协商的相关工作NewNodeBeforeJoinAfterJoinINk'<4>4IN<3>k3LN<4>LN<3>IN<3>k'/bk'r/R3344INr/R<2>k/bk3322MM43NewMemberLN<2>SponsorIN<2>k/bkr'/R'IN2233<1>r/Rr/R1122LN<1>MLN<3>3M1M2IN<1>r/Rr/R1122LNLN<2><1>M1M2图2-5成员加入群时STR密钥树的更新Figure2-5STRTreeUpdate(Join)INk<4>4AfterLeaveBeforeLeaveLNIN<3>k3'<4>IN<3>k3/bk3r4/R4LN<3>M4IN<2>k'/bk'r3/R322INM4<2>k2/bk2r3/R3LN<3>LNM<2>3IN<1>r/Rr'/R'1122INLN<1><1>r/Rr/RLNLN1122<2>M<1>M12MM21Sponsor图2-6成员离开群时STR密钥树的更新Figure2-6STRTreeUpdate(Leave)-20- 申请上海交通大学博士学位论文群密钥协商的相关工作图2-6给出了成员M3离开群{,,M14"}M时的密钥树变化。假设群中当前有n个成员，成员Md（d≤n）要离开群。如果d>1，则发起人Ms是要离开成员下面的叶节'点，即Md-1，否则Ms是M2。当发起人M2广播了盲密钥bk2后，所有成员都能计算出''''群密钥：M4用bk2可以计算出k3，M1用R2也可以计算出k3。表2-2给出了STR与TGDH的复杂性分析。由表2-2可知，STR加入协议的通信开销与TGDH相当。加入协议的计算开销为常数，但离开协议的计算开销较大，为O(n)。表2-2STR复杂性分析Table2-2ComplexityAnalysisforSTR方案事件轮数单播广播签名验证取模求幂STR加入202115离开101113n/2-1TGDH加入203223h/2-1离开101113h/2-1注：n是当前群成员的数目，h是密钥树的高度。2.3可认证的群密钥协商方案本文第1章简要介绍了两种可认证的基于树的群密钥协商方案，AGKA和AGKA-G。这两种方案的协商过程完全相同，只是提供认证的方法不同。在本节中，我们以AGKA为例来说明在群密钥协商过程中提供密钥认证的方法。2.3.1基本协议AGKA使用的密钥树与TGDH类似，是平衡二叉树。基本的密钥协商过程可分成如下三步：(1)每个成员Mi在CA注册其公钥KMi，并假设所有群成员都知道该密钥。选择**适当的大素数p和Z的生成元α。每个成员选择一个随机数r∈Z，并把处在第d层pip的密钥k设为ri。-21- 申请上海交通大学博士学位论文群密钥协商的相关工作(2)j从1到d，执行：构造第l（l=d-j）层的所有密钥k，其中1≤v≤2l。对每个v，用（j,v,l）作为参数执行协议key_agreement。(3)key_agreement(intj,intv,intl):kj代表当前的轮数，v是当前层l中的节点号。根节点为的子树中最左边的叶节点是vl=(v-1)*2j+1，最右边的叶节点是vr=v*2j。从左子树中随机选择一个成员Mi’（vl≤i’≤(vl+vr-1)/2），从右子树中随机选择一个成员Mi’’（(vl+vr+1)/2≤i’’≤vr）。节点左边的密钥的序号是v’=2v-1，右边的密钥的序号是v’’=2v。M'*→:ααkk<+lv1,′′>mod,'pitS,',(<+lv1,>mod,,)pit′′，其中t’是最近的时间戳。iMi′M''→*:ααkk<+lv1,'′′>mod,'','',pitS(<+lv1,′>mod,,)pit′′′′，其中t’’是最近的一个时iMi′′间戳。两个子树中的所有成员都能验证数字签名，并计算出新密钥：kp=(αkk<+lv1,′′>mod)<+lv1,′>modp<>lv,=(αkk<+lv1,′′>mod)p<+lv1,′>modp（2.6）=αkk<+lvlv1,′′><+1,′>modp如果有一个签名无效，就通知整个群，并把不诚实的成员排除在群之外。最终，所有成员Mi都能共享群密钥，并知道从它所对应的叶节点到根节点路径上的所有密钥。同时，所有成员都知道其它任何一个成员至少被另一个成员认证一次。2.3.2密钥更新协议虽然文献[13]并未给出成员关系发生变化时密钥更新的过程，但我们可以把无认证协议的密钥更新方法应用到AGKA中去，二者的差别就在于是否使用了可认证的两方密钥协商过程。成员加入协议如下：（1）初始化：假设当前有n个成员，新成员被插入到离根节点最近的叶节点上。原来处在的节点被提到。从该叶节点到根节点的所有密钥*kl⎡⎤i(0≤≤′l)都要被更新。新成员Mi选择一个随机数rip∈Z，并设置k=ri。<>l′,⎢⎥l′⎢⎥2（2）j从1到l，循环构造密钥k，其中l’=d-j，v＝⎡i/2j⎤，即以（j,v,l’）为参数执行协议key_agreement。（3）最终包括新成员在内的所有成员都能计算出新的群密钥，并知道从它所对应-22- 申请上海交通大学博士学位论文群密钥协商的相关工作的叶节点到根节点路径上的所有密钥。同时所有成员都确认新成员至少被认证一次。成员离开协议如下：（1）初始化：假设要离开成员对应的节点是，那么从该叶节点到根节点的所有密钥kl(0≤′≤−l1)都要被更新。以节点为根的子树提高一层。⎡⎤i<>l′,⎢⎥l′⎢⎥2（2）j从1到l-1，循环构造密钥k，其中l’=d-j，v＝⎡i/2j⎤。以（j,v,l’）为参数执行协议key_agreement。（3）最终所有剩余成员都能计算出新的群密钥，并且离开成员不能计算出该密钥。2.3.3安全性与复杂性分析在AGKA方案中，认证是通过数字签名和PKI来实现的。当两个成员交换信息时，它们首先要对幂、对方在密钥树中的位置以及时间戳进行签名。AGKA提供了成员间的隐含认证，并且不需要完全认证（任何两个成员都必须相互认证）或指定一个成员（如发起人）与所有其它成员进行相互认证。因此AGKA能够抵抗主动攻击（如：中间人攻击）。由于该方案中每个成员都只知道从它所对应的叶节点到根节点的路径上所有节点的密钥，因此能够保证前向保密和后向保密。表2-3给出了AGKA方案的通信开销和计算开销。由于加入协议和离开协议的开销取决于新成员插入的位置和离开成员在密钥树上的位置，因此我们分别给出了最好情况和最坏情况下的开销。表2-3AGKA复杂性分析Table2-3ComplexityAnalysisforAGKA方案事件轮数单播广播签名验证取模求幂加入204244离开102122AGKA（最好）加入h02hh2h2h离开h-102h-2h-12h-22h-2（最坏）注：n是当前群成员的数目，h是密钥树的高度。因为AGKA密钥树会随着成员的加入而成为平衡二叉树，但成员的离开会破坏密钥树的平衡，因此是一种尽力平衡的二叉树。由表2-3可知，AGKA方案的平均开销，即当新成员和离开成员处在密钥树中间位置时的开销为O(logn)，取决于密钥树的高度。-23- 申请上海交通大学博士学位论文群密钥协商的相关工作2.4小结本章对后续章节涉及的技术背景做了简要介绍，主要是椭圆曲线密码机制、Pairing和基于身份的密码机制。通过本文第1章的分析可以看出，在基于树的分布式密钥协商方案中，每个成员同等地控制群，平均分担计算开销和通信开销，比较适用于使用多对多通信机制的动态对等群。因此，本文的研究重点是基于树的密钥协商方案。在本章中，还介绍了两种无认证的协商方案和一种可认证的协商方案，并分析了它们的安全性和复杂性。本文的研究工作在继承上述方案优点的基础上弥补它们在性能（减小计算开销或通信开销）或安全性（主要是提供隐含密钥认证）方面的不足。同时借鉴集中式方案中的方法，并根据对等群的要求进行扩展。-24- 申请上海交通大学博士学位论文基于Pairing和三叉树的群密钥协商方案第3章基于Pairing和三叉树的群密钥协商方案对高延迟网络上的应用来说，通信开销成为决定其性能的主要因素，因此密钥管理方案必须尽量减少通信量；另一方面，动态对等群的密钥管理必须具有较强的可扩展性，这就要求成员数目的增加所引起的计算开销的增长速度尽可能小。在安全性方面，密钥管理方案必须能够适应成员关系的动态变化，当新成员加入群或当前成员离开群时要重新协商群密钥，即提供后向保密和前向保密。几乎所有基于树的密钥管理方案的开销都取决于密钥树的高度，而多叉树的高度不大于具有相同数目叶节点的二叉树的高度，当叶节点的数目很大时，多叉树的高度远远小于二叉树的高度，因此从理论上讲，用多叉树代替二叉树能够减小密钥管理的开销。三叉树是结构最简单的一种多叉树，每个内部节点有两个或三个子节点，因此节点的插入和删除操作都比较简单，很适合作为密钥协商的数据结构。根据以上分析，我们把三叉树和超奇异椭圆曲线上的Pairing结合起来，提出了一种高效的群密钥协商机制PTDH。该机制的通信开销随成员数目的增加而增长的幅度可忽略，三叉树的使用使得其计算开销为O(log3n)。它提供了前向保密和后向保密。从性能和安全性两方面来看，该机制适用于高延迟网络中的动态对等群。3.1基于Pairing的密钥协商Pairing的性质及其在密码学中的应用已在本文第2章中介绍过，在此不再赘述。[26]首先我们在现有的一种基于Pairing的三方协议的基础上提出了一种基于Pairing的两方协议，然后利用三叉密钥树把三方协议和两方协议扩展到多方。下面分别简单介绍这两种协议。3.1.1基于Pairing的三方密钥协商协议*假设A、B和C要协商一个密钥，首先它们分别选择一个随机数abc,,∈Z，然后qab广播aP、bP和cP。接收到所有广播后，A计算Ke=ˆ(,)bPcP，B计算Ke=ˆ(,)aPcP，ABcabcC计算K=eaPbPˆ(,)。由Pairing的性质可知所有密钥都等于Ke=ˆ(,)PP，这CABC可以作为三方的共享密钥。-25- 申请上海交通大学博士学位论文基于Pairing和三叉树的群密钥协商方案3.1.2基于Pairing的两方密钥协商协议*假设A和B要协商一个密钥，首先它们分别选择一个随机数ab,∈Z，然后交换qabaP和bP，这样A能计算KeA=ˆ(,)bPQ，B能计算KeB=ˆ(,)aPQ，而KA和KB都等ab于Ke=ˆ(,)PQ。AB以上述协议为基础，我们提出了基于三叉树的群密钥协商方案。3.2基于Pairing和三叉树的群密钥协商方案3.2.1密钥树在PTDH方案的描述中使用了下列符号：表3-1PTDH方案使用的符号Table3-1NotationsforPTDH符号含义Mi第i个群成员：i∈{1,…,n}第i层的第j个节点P、Q计算Pairing时使用的点*HHG:2→Zq是一个安全的散列函数k节点的秘密密钥bkk的盲密钥（Hk()<>ij,P）riMi的随机秘密密钥briri的盲密钥（rPi）CertiMi的证书TMi构造的密钥树BT包含k个成员的所有盲密钥的密钥树本方案使用的密钥树如图3-1所示。三叉树的所有内部节点（包括根节点）都只有2或3棵子树，群成员对应叶节点。为了便于构造该密钥树，每个节点中都保存一个代表其子树个数的数值（取值为0、2、3）。很显然，这个数值在成员加入或离开时会发生变化。-26- 申请上海交通大学博士学位论文基于Pairing和三叉树的群密钥协商方案<0,0>2<1,0><1,1>32<2,0><2,1><2,2><2,3><2,4>00000MMMMM12345图3-1PTDH密钥树Figure3-1KeyTreeforPTDH3.2.2基本协议所有节点（除根节点外）都有一个秘密密钥/盲密钥对，盲密钥是对秘密密期进行点乘操作得到的。叶节点的秘密密钥由对应的成员随机产生，内部节点的秘密密钥是该节点的所有子节点进行密钥协商（三方协商或两方协商）的结果。群密钥就是根节点的秘密密钥，它是所有叶节点的秘密密钥信息的函数。我们把第i层第j个节点N的秘密密钥记作k，对应的盲密钥记作bk。N的子节点分别记作N、N和N。第m个成员产生的秘密密钥是rm。则k可如下计算：⎧⎫r，若N是叶节点m<>ij,⎪⎪kk=⎨⎬ebkˆ(,)bk<+il1,2+>，若N有三个子节点<>ij,<+il1,><+il1,+>1(3.1)⎪⎪ekˆ(,bkQ)，若N有两个子节点⎩⎭<+il1,><+il1,+>1由此可见，群密钥的计算是一个递归过程。每个成员需要计算从它所对应的叶节点到根节点的路径上所有节点（图3-1中的黑色节点）的秘密密钥，在计算过程中还需要得到这些节点的兄弟节点（图3-1中的灰色节点）的盲密钥。下面以成员M1为例说明计算根密钥k<0,0>的过程。首先M1生成秘密密钥r（1k<2,0>），并得到M2和M3的盲密钥bk<2,1>和bk<2,2>，这样M1就能计算出：k=(ebkˆ,bk)k<2,0>(3.2)<>1,0<>2,1<>2,2然后M1利用盲密钥bk<1,1>就能计算出根密钥：ke=ˆ(,kbkQ)(3.3)<>0,0<><>1,01,1-27- 申请上海交通大学博士学位论文基于Pairing和三叉树的群密钥协商方案下面将具体描述密钥重发协议。为了减少计算量和通信量，指定一个成员作为发起人负责计算内部节点的盲密钥并广播给相关成员。3.2.3成员加入协议假设群当前有n个成员{M1,…,Mn}，新成员Mn+1广播一个包含其证书和随机盲密钥的加入请求消息。发起人Ms负责验证Mn+1的证书，若验证通过，则在更新密钥树以后重新计算密钥树上所有被改变的密钥。为了减小开销，应尽量使得新节点的插入不增加密钥树的高度，同时要尽量减少受影响的密钥的数目。因此我们把新节点插入到距离根节点最近的子节点数目最少的（0个或2个）最左边的节点上。如果插入点是叶节点，那么该叶节点就是发起人。否则，以插入点为根的子树中最左边的层次最高的叶节点是发起人。新节点插入的典型情况如图3-2(a)、(b)、(c)、(d)所示。图3-3描述了新成员加入群时密钥重发的一般过程。对图3-2(a)给出的M6加入时的情况，发起人M4更新秘密密钥r’4后重新计算图中所有黑色节点的密钥，然后广播相应盲密钥。最后所有成员都能利用自己的秘密密钥和BT<6>中的盲密钥计算出新的群密钥。如：M、M、M用ebkˆ(,)'brk<1,0>能计算出k’；M用ebkˆ(,)bk'r5能计123<>1,15<0,0>5<>1,0<>1,1'erbrQˆ(,)'计算出k’ˆ(,)k<1,1>算出k’<0,0>；M6用64<1,1>，然后用ebk<>1,0br5也能计算出k’<0,0>。<0,0>3<1,2><1,0><1,1>320M5<2,0><2,1><2,2><2,3><2,4>00000M1M2M3M4M6SponsorNewcomer(a)图3-2成员加入群时PTDH密钥树的更新Figure3-2PTDHTreeUpdate(Join)-28- 申请上海交通大学博士学位论文基于Pairing和三叉树的群密钥协商方案<0,0>2<1,0><1,1>30M10Newcomer<2,0><2,1><2,2>333<3,0><3,1><3,2><3,3><3,4><3,5><3,6><3,7><3,8>000000000M1M2M3M4M5M6M7M8M9Sponsor(b)<0,0>3<1,0><1,1><1,2>330M7Newcomer<2,0><2,1><2,2><2,3><2,4><2,5>000000M1M2M3M4M5M6Sponsor(C)图3-2续1-29- 申请上海交通大学博士学位论文基于Pairing和三叉树的群密钥协商方案<0,0>3<1,0><1,1><1,2>332<2,0><2,1><2,2><2,3><2,4><2,5><2,6><2,7>00020000M1M2M3M6M9M7M8<3,0><3,1>SponsorNewcomer00MM45(d)图3-2续2(1)新成员Mn+1：Mn+1Certn+1,brn+1{M1,…,Mn}(2)所有成员：验证Mn+1的证书，更新密钥树。把新节点插入到最高层的子节点数目最少的最左边的节点上。如果插入点是叶节点，那么该叶节点就是发起人Ms。否则，以插入点为根的子树中最左最高的叶节点是发起人。(3)发起人Ms：'更新自己的秘密密钥r，然后计算所有被改变的密钥，最后把包含所有盲密s钥的密钥树BT广播给群。MsBT{M1,…,Mn+1}(4)所有成员：利用BT中的相关盲密钥（处在从成员对应的叶节点到根节点路径上的所有节点的兄弟节点对应的盲密钥）计算出群密钥。图3-3PTDH成员加入协议Figure3-3PTDHJoinProtocol-30- 申请上海交通大学博士学位论文基于Pairing和三叉树的群密钥协商方案3.2.4成员离开协议假设群中当前有n个成员，成员Md（d≤n）要离开群。发起人Ms是以Md的父节点为根的子树中距离根节点最近的最左边的叶节点对应的成员。Ms先改变自己的秘密密钥，计算所有被改变的密钥，然后广播盲密钥，从而启动密钥重发过程。图3-4给出了密钥重发的一般过程。图3-5给出了成员M7离开群{M1、M2、M3、M4、M5、M6、M7}时的密钥树变化，发起人是M1。M1更新了秘密密钥以后，计算出图中所有黑色节点的秘密密钥，并广播相应的盲密钥br1、bk<2,0>和bk<1,0>。接收到这些盲密钥以后，所ebrbrˆ(,)'r2和ebrbrˆ(,)'r3计算出有成员都能计算出新的群密钥。如：M2和M3分别用1312’ekˆ(,'bkQ)’ekˆ(,bk'Q)k<1,0>，然后用<><>1,01,1计算出k<0,0>；M4、M5和M6用<><>1,11,0计算出’k<0,0>。(1)所有成员：更新密钥树，删除Md对应的节点。(2)距离根节点最近的最左边的叶节点对应的成员是发起人Ms：生成新的秘密密钥'r，计算所有被改变的密钥，然后把包含被改变的盲密钥的密s钥树BT广播给剩余成员。MsBT{M1,…,Mn}─{Md}(3)每个成员分别计算群密钥。图3-4PTDH成员离开协议Figure3-4PTDHLeaveProtocol3.3安全性分析上述密钥管理方案的安全性是基于BDH假设的，提供了群密钥保密、后向保密和前向保密，下面分别进行说明。3.3.1群密钥保密对于每种成员关系变化事件，发起人都会更改自己的随机秘密密钥，这会引起从该[27]成员所对应叶节点到根节点路径上所有内部节点的密钥发生变化。由BDH假设可知根密钥是随机的，因此新密钥与旧密钥相同的概率可忽略。另外，被动攻击者要从截获-31- 申请上海交通大学博士学位论文基于Pairing和三叉树的群密钥协商方案的盲密钥推导出相应的秘密密钥相当于解决G1上的离散对数问题，因此也是不可行的。总之，被动攻击者不可能计算出群密钥，即提供了群密钥保密。<0,0>2<1,0><1,1><1,2>320M7Memberto<2,0><2,1><2,2><2,3><2,4>Leave00020MMMM1236Sponsor<3,0><3,1>00MM45图3-5成员离开群时PTDH密钥树的更新Figure3-5PTDHTreeUpdate(Leave)3.3.2后向保密和前向保密这里所考虑的被动攻击者A可以是非群内成员（外部攻击者）也可以是群内成员（内部攻击者），下面分别进行讨论。3.3.2.1外部攻击者假设A是一个外部攻击者，且A知道的信息包括当前的群密钥和所有盲密钥，由G2上离散对数问题的难解性可知A不能从这些信息推导出任何秘密密钥。当成员关系发生变化时发起人更新自己的秘密密钥，使得群密钥和一部分盲密钥发生变化，由BDH假设可知在不知道任何秘密信息的情况下A所知道的信息不足以使它计算出旧的群密钥，即提供了后向保密。当A知道旧的群密钥时，分析过程与上述情况类似，A也不可能计算出当前的根密钥，即提供了前向保密。3.3.2.2内部攻击者对于内部攻击者来说，我们只需要说明A知道的信息与一个外部攻击者相同。-32- 申请上海交通大学博士学位论文基于Pairing和三叉树的群密钥协商方案假设A是一个新成员，当它加入时发起人更新自己的秘密信息，引起从A对应的叶节点到根节点路径上的密钥发生变化，这使得A所能得到的关于旧密钥树的信息仅限于没有改变的盲密钥，与外部攻击者相同。假设A是一个已经离开群的旧成员，当它离开时发起人更新自己的秘密信息，使得A知道的所有秘密密钥都被改变了，只有一些盲密钥仍然有效，与外部攻击者知道的信息相同。通过以上分析可知，上述方案提供了后向保密和前向保密。3.4复杂性分析群成员在进行密钥协商时根据其功能可以分成三类：引起成员关系变化的成员、发起人和普通成员。由于每一类成员执行不同的操作，因此三类成员的计算量和通信量是不同的，而且也不可能同步完成密钥协商过程。我们把每个成员接收到成员关系变化通知的时间记作StartedEvent[i]（1≤i≤n），每个成员接收到新成员关系的时间记作FinishedEvent[i]（1≤i≤n），那么每个成员更新成员关系所需要的时间是TimeEvent[i]=FinishedEvent[i]-StartedEvent[i]。从整个群的角度来看，更新成员关系所需要的时间是TimeMax=max(TimeEvent[i])，即从发生群成员关系事件开始到每个成员都计算出群密钥。TimeMax包括整个密钥协商过程的通信时间和计算时间以及群通信系统提供基本成员关系服务所需要的时间。从用户的角度来看，成员关系变化事件所需要的时间是一个n平均值TimeAvg=([∑TimeEventi])/n。显然，TimeMax比TimeAvg大，二者的差别主i=1要是由于每个成员在发起人广播了盲密钥以后计算群密钥时开销不同而造成的，并且差距会随着成员数目的增加而增大。由图3-3和3-4可知，本方案的通信开销（通信的轮数、单播次数和广播次数）是常数，不随成员数目的增加而增加。因为发起人和新成员都会引起从它们所对应的叶节点到根节点路径上所有节点的密钥发生变化，而本方案确保它们都处在离根节点尽可能近的位置，因此其计算开销取决于密钥树的高度以及新节点的插入位置（或离开成员的位置）和发起人的位置。在该方案中，每个成员的计算开销是不同的，发起人的开销最大，其它成员的开销则取决于它们在密钥树上的位置。对加入成员来说，当新节点插入到根节点上时，计算开销最小，只需要1次点乘操作和一次Pairing操作。当新节点插入到最底层的内部节点上时，计算开销最大，点乘和Pairing操作的次数为On(log)，取决于密钥树的高度。3当有成员离开群时，发起人的位置决定了计算开销的大小。-33- 申请上海交通大学博士学位论文基于Pairing和三叉树的群密钥协商方案下面我们把PTDH方案与TGDH进行复杂性比较。两种方案的计算开销是通过比较各协议中最费时的密码操作的执行次数来粗略衡量的。TGDH使用了标准的DH密码方案，其中取模求幂操作最费时。PTDH使用的椭圆曲线密码方案中，最费时的是点乘和TatePairing操作。我们在计算开销时假设TGDHn密钥树是平衡的，PTDH的密钥树高度也保持最小（⎡log⎤+1），即理想情况下的最大⎢3⎥开销TimeMax，表3-2给出了比较结果。表3-2PTDH复杂性分析Table3-2ComplexityAnalysisforPTDH方案事件轮数单播广播取模求幂点乘TatePairingTGDH加入2023log⎡⎢n⎤⎥−1离开1013log⎡⎢n⎤⎥−1PTDH加入2023log⎡n⎤−42log⎡⎤n−2⎢3⎥⎢⎥3离开101nn3log⎡⎤−42log⎡⎤−2⎢3⎥⎢⎥3由表3-2可以看出，TGDH和PTDH的通信轮数相同，都为常数，其通信总量分别为On(log)和On(log)（取决于所含盲密钥的数目），所以PTDH的通信开销随成员3数目的增加而增长的幅度比TGDH小。对于动态对等群来说，成员数目较少，因此通信总量的增长不会对通信时间产生很大影响。换言之，两种方案都能很好地适应高延迟网络中的群应用。*在本文中G1是FP上椭圆曲线群的q阶子群；G2是F2的q阶子群。在PIII1GHzPCP上，DH方案（p是1024位，q是160位）的取模求幂操作需要6.9ms，ECC方案（p是192位，q是160位）的点乘和TatePairing的执行时间分别是3.34ms和4.05ms（发起人在计算被改变的密钥时，会利用上一次密钥协商时的结果，实现Pairing的预运算，以进一步提高效率）。通过计算可知，PTDH的计算开销明显比TGDH小。而且随着成员数目的不断增大，PTDH计算开销的增长速度明显小于TGDH。当成员数小于729时，PTDH的理想情况下（密钥树的高度为7）的最大开销仍然小于100ms。因此对于使用该方案的群应用来说，网络延迟是决定其性能的关键因素。-34- 申请上海交通大学博士学位论文基于Pairing和三叉树的群密钥协商方案3.5小结对开放式高延迟网络环境下的动态对等群应用来说，通信开销成为决定其性能的主要因素，同时还要保证成员数目的增加所引起的计算开销的增长幅度尽可能小。在本章中，我们从密钥树的结构入手，在群密钥协商中引入多叉树，提出了一种使用三叉树的分布式密钥协商方案PTDH。该方案的通信开销为常数，计算开销随成员数目的增加而增加的幅度小于使用二叉树的方案。在PTDH方案中，我们还使用了椭圆曲线密码机制，ECC在安全性和灵活性方面的优势使得该方案能够避免使用传统密码机制的方案所受到的安全性威胁，并且在具体实现时能够通过选择不同的曲线和参数来满足系统的不同要求。方案提供的安全属性包括群密钥保密、前向保密和后向保密。文中对这些属性进行了详细的分析证明。对方案的复杂性进行了理论分析，并且与当前性能最好的TGDH方案进行了比较。分析表明PTDH方案能够更好地满足高延迟网络上动态对等群的安全要求。-35- 申请上海交通大学博士学位论文基于Pairing的可认证的群密钥协商协议第4章基于Pairing的可认证的群密钥协商方案在开放的网络环境下，存在各种各样的安全威胁，特别是一些主动攻击者，由于它们能够随意插入、删除或修改信息，很容易通过假冒合法成员攻击无认证的方案，因此提供密钥认证是一个非常重要的目标。提供密钥认证一定会增加通信量和计算量，而动态对等群的高度动态性又决定了我们必须限制其开销。从本文第2章的分析可以看出，基于密钥树的分布式方案比较适合动态对等群，因为这类方案在成员关系发生变化时重发密钥的开销较小，并且每个成员都能平等地控制群密钥的产生。因此本章的研究重点是基于树的可认证的群密钥协商方案。[6][7][8][9][12][13]目前已经提出了一些适用于动态对等群的基于树的密钥协商方案，试验证明STR在通信开销方面最好，主要是因为不平衡二叉树的使用使得密钥的更新非常简单灵活。但在安全性方面，STR仅提供了前向保密和密钥独立等基本安全属性，没有提供密钥认证，因此不能抵抗中间人攻击和已知密钥攻击等主动攻击。虽然AGKA和AGKA-G提供了密钥认证，但这种认证只是在每一轮密钥协商过程中随机选出的两个成员之间的认证，而不是群内任意两个成员之间的直接认证，所以该方案很容易受到中间人攻击。由此可以得出结论，仅通过多次执行可认证的两方密钥协商协议并不能得到一个可认证的群密钥协商协议。根据以上分析，我们首先利用椭圆曲线上的Pairing在安全属性和灵活性方面的优势，提出了一种基于Pairing的两方可认证的密钥协商协议，然后利用不平衡二叉树把该协议扩展到群，得到一种在安全性和性能方面都能满足动态对等群要求的方案。该方案通过引入群公钥证书并在群密钥中结合群和成员的长期密钥和临时密钥，提供了隐含密钥认证以有效地对抗中间人攻击。协议同时提供了密钥独立和完善前向保密以及对抗已知密钥攻击等安全属性。另外，该方案的设计思想可以作为把可认证的两方DH协议扩展到群环境的一种通用方法。4.1基于Pairing的两方密钥协商协议Pairing的性质以及其在密码学中的应用已在本文第2章中介绍过，在此不再赘述。下面给出一种基于Pairing的可认证的两方密钥协商协议。假设进行协商的双方是A和B，在初始阶段由一个证书中心（CA）为它们提供证书，用于把用户身份与长期密钥（公钥）绑定在一起。用户A的证书的格式如下：CertA=(IA||µA||P||Q||SCA(IA||µA||P||Q))。-37- 申请上海交通大学博士学位论文基于Pairing的可认证的群密钥协商协议其中，IA代表A的身份标识字符串，||代表数据项的串接，SCA代表CA的签名。用*户A的长期公钥是µA=xP，其中x∈Zq是A的长期私钥。元素P和Q是公开的，用于指明构造µA以及临时公钥所使用的元素。协议的执行过程如图4-1所示：aPCertA(1)ABYZZZZZZZZZZXbPCertB(2)ke=+ˆ((bPHbPy||P)yP,Q)aHaPxPx+1(||)A1(3)ke=+ˆ((aPHaPx||P)xP,Q)bHbPyPy+1(||)B1(4)ke=ˆ(,)PQ(aHaPxPxbHbPyPy++11(||))((||))AB图4-1基于Pairing的两方密钥协商协议Figure4-1Pairing-basedTwo-partyKeyAgreementProtocol*在上述协议中“||”代表数据项的串接。设Sa=∈{|PbPa,bZ且PG∈}，则q1*HS:→Z是一个散列函数。A和B的长期私钥/长期公钥对分别是（x,xP）和（y,yP）。1q*它们分别随机选取整数ab,∈Z作为临时私钥，然后把相应的临时公钥aP(bP)和证书q发送给对方。最后A和B都能利用自己的长期密钥和临时密钥以及对方的长期公钥和临时公钥计算出共享密钥。该协议提供了本文第1.2.1节中列出的除显式密钥认证外的所有安全属性。因为协商后的共享密钥中包含了两方的长期密钥和临时密钥，而且临时密钥是随机选取的，这就保证了会话密钥之间的独立性，同时长期密钥的泄漏也不会导致旧共享密钥的泄漏。攻击者通过窃听或修改协议中的两条消息来与A或B共享一个密钥是不可能的，因为BDH假设决定了它不能计算出所需要的临时私钥和长期私钥，即提供了隐含密钥认证。我们把上述协议与不平衡二叉树结合起来，提出了一种高效的可认证的群密钥协商方案PAGKA，这里给出了新成员加入群和老成员离开群时密钥协商的过程。-38- 申请上海交通大学博士学位论文基于Pairing的可认证的群密钥协商协议4.2基于Pairing的可认证的群密钥协商方案4.2.1基本符号和密钥树在PAGKA方案的描述中我们使用了下列符号：表4-1PAGKA方案使用的符号Table4-1NotationsforPAGKA符号含义Mi第i个群成员：i∈{1,…,n}IN第j层的内部节点LN成员Mi对应的叶节点P，Q用于计算Pairing的两个点kiM1…Mi之间共享的密钥（IN的临时私钥）bkiki的公开密钥（kiP）riMi的随机秘密数值（LN的临时私钥）briri的公开密钥（riP）yiMi的长期私钥byiMi的长期公钥（yiP）yG群的长期私钥byG群的长期公钥（yGP）CertiMi的证书（包含byi）CertG群的证书（包含yGP）BT成员Mi构造的包含所有公开密钥的密钥树图4-2显示了有三个成员的群的密钥树。每个叶节点LNi与一个群成员相关联，每个内部节点INi用于保存密钥协商过程中的中间结果。由于内部节点不对应于群成员，在密钥协商过程中，内部节点所包含的中间结果是由特定成员发送给其它成员的。虽然内部节点没有身份信息，但仍被看作参与密钥协商的一方，因此为了提供认证，也必须使合法成员能够确认内部节点的身份。上述问题可以通过引入一个与内部节点相关联的群长期公钥yPG来解决，相应的长期私钥yG只有合法的群成员知道。叶节点LNi的临-39- 申请上海交通大学博士学位论文基于Pairing的可认证的群密钥协商协议时私钥r是由Mi随机选择的，而内部节点INi(>1)的临时私钥k是其两个子节点进iii行第4.1节所描述的可认证的两方密钥协商的结果。kIN33y/yPinternalnode'sGGprivate/publickeypairmember'sshort-termprivate/publickeypairk/kP,IN22r/rP,y/yP2y/yP3333GGmember'slong-termprivate/publickeypairLN3group'slong-termprivate/publickeypairr/rP,y/yPr/rP,y/yP11112222IN/LNLN112图4-2PAGKA密钥树Figure4-2KeyTreeforPAGKA群密钥k可以如下递归计算：i⎧⎪kr=⎪⎪11⎨⎪kH((,Q)eˆP((kHkPyii−−121++GP)yrHrG)i((i2iPyiP)yi))⎪⎪⎩ii(1>)=1(4.1)其中||代表数据项串接，H1和H2是两个散列函数：*HG:→Z(4.2)12p**H2:S→Zp({S=uPvP|,uv∈∈Zp&PG1})(4.3)适用于动态对等群的解决方案应该考虑动态的成员关系变化，下面给出成员加入群和成员离开群时的密钥协商过程。4.2.2成员加入协议假设群G当前有n个成员{,,}M"M，新成员M要加入群。图4-3给出了加1nn+1入协议的执行过程。图4-4给出了M加入群{,,}MMM时密钥树的变化。发起人是4123M3。当M3广播了密钥树BT<4>后，所有成员都能利用自己的私钥和BT<4>中的公钥计算出新的群密钥：-40- 申请上海交通大学博士学位论文基于Pairing的可认证的群密钥协商协议M计算：4'kk=Heb(((ˆˆ',Q)(,⋅ePyQ)Hb23()kyPG)((rHb42444+ryPy)))(4.4)43G1M和M计算新群密钥的过程如下：12'kr''=Heb(((ˆˆ,Q)(⋅eby,Q)HbryPkHbkyPy233()()222+())GG)(4.5)3313''kr=Heb(((ˆˆ,Q)(⋅eby,Q)HbryP244())((kHb323+kyPy)GG))(4.6)4414(1)MG→:rPCertnnn+++111(2)所有成员：更新密钥树，创建一个新的根节点IN和一个叶节点LN，原来的根节点IN成为IN的左子节点，LN对应IN的右子节点。(3)发起人Mn（即密钥树更新前最顶端的叶节点）：'r生成新的临时私钥n，然后计算被改变的临时密钥。(4)MnBT||Certn||Es(yG)||yGQG∪{Mn+1}（其中，s是Mn计算出来的新群密钥）(5)每个成员：分别计算出群密钥，然后解密得到yG，这样Mn＋1就可以得到yG，而其它成员都可以验证新群密钥的正确性。图4-3PAGKA加入协议Figure4-3PAGKAJoinProtocol-41- 申请上海交通大学博士学位论文基于Pairing的可认证的群密钥协商协议AfterJoinBeforeJoinkIN44y/yPNewNodeGGkIN33y/yPGGk'/k'P,33INr/rP,y/yP3y/yP4444GGk/kP,IN22r/rP,y/yP2y/yP3333GGLN4NewMemberLN3k/kP,IN22r'/r'P,y/yPSponsor2y/yP3333GGr/rP,y/yPr/rP,y/yP11112222LN3IN/LNLNSponsor112r/rP,y/yPr/rP,y/yP11112222IN/LNLN112图4-4成员加入群时PAGKA密钥树的更新Figure4-4PAGKATreeUpdate(Join)4.2.3成员离开协议假设群中当前有n个成员，成员M()in≤要离开群。如果i>1，则发起人M是is要离开成员下面的叶节点，即M，否则M是M。接收到成员离开事件通知后，每i−1s2个剩余成员执行图4-5所示的协议过程。图4-6给出了M离开群{,,,}MMMM时31234'密钥树的变化。发起人是M，当M广播了临时公钥bk后，所有成员都能计算出群222密钥：'M用Heb(((ˆˆk',Q)(,⋅ePyQ)HbkyPrHbryPy22()(G)42444+()))可以计算出k'；412G3M计算新群密钥的过程如下：1'kr''=Heb(((ˆˆ,Q)(⋅eby,Q)HbryP222())((rHb121+ryPy)GG))(4.7)2212''kr'=Heb(((ˆˆ,Q)(⋅eby,Q)HbryP244())((kHb222+kyPy)GG))(4.8)3414-42- 申请上海交通大学博士学位论文基于Pairing的可认证的群密钥协商协议（1）所有剩余成员：更新密钥树，删除Mi对应的节点LN及其父节点IN，把叶节点LN放到原来IN的位置或把IN放到原来IN的位置。（2）发起人Ms：'生成新的临时私钥rs以及新的群长期私钥yG’，计算所有被改变的临时密钥，然后用新的群密钥加密yG’。MsBT||Es(yG’){M1,…,Mn}─{Md}（3）每个成员分别计算出群密钥，并更新群长期密钥。图4-5PAGKA离开协议Figure4-5PAGKALeaveProtocolkIN4BeforeLeave4y/yPAfterLeaveGGk',3IN3y'/y'PGGk3/k3P,r4/r4P,IN3yG/yGPy/yP44LNk'/k'P,r/rP,4IN22442y'/y'Py/yPGG44k/kP,r/rP,IN2233LN2y/yPy/yP3GG33LNMembertor/rP,r'/r'P,31122Leavey/yPy/yP1122r/rP,y/r/rP,y/yP222IN/LNLN1111yP1122IN/LNLN112Sponsor图4-6成员离开群时PAGKA密钥树的更新Figure4-6PAGKATreeUpdate(Leave)4.3安全性分析PAGKA的安全性基础是BDH假设，在所有群成员都正确执行协议的情况下，它提供了密钥独立、隐含密钥认证、完善前向保密、抵抗中间人攻击等安全属性，下面分别进行分析。-43- 申请上海交通大学博士学位论文基于Pairing的可认证的群密钥协商协议4.3.1密钥独立因为每种成员关系变化事件所对应的密钥协商过程至少要更改一个成员的临时私钥，这会引起从该成员所对应叶节点到根节点路径上所有内部节点的密钥发生变化。而叶节点的临时私钥都是随机选择的，根据BDH假设可知，被动攻击者在不知道合法成员的长期私钥的情况下从旧密钥推导出新密钥或从当前密钥计算出旧密钥都是不可能的，即提供了密钥独立。4.3.2隐含密钥认证对隐含密钥认证可以分以下两类情况进行分析。对于被动攻击，攻击者可以得到的信息仅限于协议执行过程中传输的消息，由这些消息计算出成员的私钥信息或群公钥都是不可能的，所以也就不能得到任何成员计算出的群密钥。而主动攻击者能够插入、删除或修改协议中的消息，由于密钥计算过程中需要把成员的长期密钥和临时密钥紧密结合，简单地修改消息不能帮助攻击者计算出任何长期密钥信息，虽然这使得合法的群成员最终不能计算出共享密钥，但攻击者也不能得到任何群密钥。4.3.3完善前向保密攻击者要得到旧的群密钥就必须能够计算出至少一个内部节点的临时私钥：kH=((,Q)eˆP((kHkPyii−−121++GP)yrHrG)i((i2iPyiP)yi))ii(1>)1=Heb()((ˆˆky,Q)(⋅eP,Q)HkPyPrHrPyPy21(iGiii−))((+2)i)1iG−1=Hebr()((,Q)(,Q)ˆˆ⋅ebyHb21()rbiiy)(ki−−+Hb2()kyPyiGG1)1ii(4.9)假设所有成员的长期私钥{,,}yy"以及群长期私钥y都被泄漏了，由上式可以1nG看出，攻击者要计算出k还必须得到合法成员随机产生的临时私钥r。由BDH假设和ii散列函数的性质可知，攻击者由旧密钥计算出r是不可能的。因此PAGKA提供了完善i前向保密。4.3.4抵抗中间人攻击群长期私钥的引入使得没有身份信息的中间节点有了向除发起人以外的其它群成员提供认证的方法。因此，主动攻击者在不知道y的情况下，仅通过替换发起人发送G的中间节点对应的盲密钥，并不能导致群密钥泄露。-44- 申请上海交通大学博士学位论文基于Pairing的可认证的群密钥协商协议与PAGKA方案不同，AGKA方案只是简单地把多方密钥协商分解成多次两方密钥协商，很容易使中间节点成为攻击者进行中间人攻击的切入点。因为内部节点所包含的中间结果是由特定成员发送给其它成员的，而内部节点没有身份信息，因此不能对每个群成员提供隐含密钥认证。PAGKA则通过在两方密钥协商过程中引入群长期私钥y来G克服上述问题。综上所述，PAGKA能够抵抗中间人攻击。4.4复杂性分析我们把PAGKA方案与AGKA-G方案和AGDH方案进行了复杂性比较，如表4-2所示。PAGKA方案中离开协议的计算开销取决于离开成员的位置，表中给出的是平均开销，即第n2个成员离开时的开销。AGKA-G方案的开销是当密钥树完全平衡时的平均开销。AGDH方案的开销则是准确开销。由表4-2可以看出，PAGKA方案的通信开销对两种成员关系变化事件来说都是最小的，保持常数。其加入协议的计算开销比AGKA-G和AGDH小，但离开协议的开销最大，为O(n)。另外，由于PAGKA和AGKA-G都提供了隐含密钥认证，因此不需要签名和验证。AGDH则通过签名来提供认证，因此其加入协议的计算开销较大，为O(n)。由上述分析可知，PAGKA用较大的计算开销换取了较小的通信开销，因此比较适用于成员数目较少（几十个）且网络延迟较大的动态对等群。表4-2PAGKA复杂性分析Table4-2ComplexityAnalysisforPAGKA方案事件轮单播广签名验证取模点乘TatePairing数播求幂PAGKA加入2020053离开101003n/2-2n-1AGKA-G加入h2h0003h离开h2h0003hAGDH加入4n+124n+3n+3离开10111n-1注：n是当前群成员的数目，h是密钥树的高度。-45- 申请上海交通大学博士学位论文基于Pairing的可认证的群密钥协商协议4.5小结在PAGKA方案中，我们研究了如何把可认证的两方密钥认证协议通过二叉树扩展到多方。只通过简单地把多方密钥协商分解成多次两方密钥协商，很容易使中间节点成为攻击者进行中间人攻击的切入点。为了解决该问题，必须对密钥树的中间节点进行认证，本文提出的一种有效的方法是加入群长期私钥。基于以上分析，PAGKA可以作为把可认证的两方密钥协商扩展到群的通用方法。在扩展过程中，必须对两方协议进行改造，以适当的方式加入群长期私钥。在PAGKA方案中，我们同样使用了椭圆曲线上的Pairing，有助于提高协议的安全性和计算的简单性。另外，不平衡二叉树的使用使其通信开销保持常数。PAGKA提供了隐含密钥认证，完善前向保密，能够很好地抵抗中间人攻击等主动攻击。-46- 申请上海交通大学博士学位论文基于身份的可认证的群密钥协商方案第5章基于身份的可认证的群密钥协商方案目前绝大部分可认证的密钥协商方案都是用数字签名来提供认证的，这会引起两个问题：每个成员需要从CA得到其它成员的证书，而证书的传输会浪费大量带宽；对PKI签名的验证需要大量计算。为了解决上述问题，我们使用了基于身份的密码技术（Identity-basedEncryptionIBE），即用一种公开的确定性算法由用户身份得到用户的公钥，而没必要像传统公钥签名机制那样必须通过数字证书把公钥与用户身份绑定起来。本章提出了一种适用于动态对等群的高效的基于身份的密钥协商协议IAGKA，把密钥树和群长期公钥结合起来，对基于身份的两方密钥协商协议进行扩展。IAGKA方案的通信开销是常数，并提供了密钥独立、隐含密钥认证等安全属性，能够抵抗中间人攻击等主动攻击。5.1基于身份的密钥协商协议[26]N.P.SMART把Boneh-FranklinIBE系统和Joux的三方Diffie-Hellman协议结合起来，提出了一种基于身份的可认证的两方密钥协商协议。该协议使用一个密钥生成中心（KeyGenerateCenterKGC）来对参与协商的各方进行预认证并分发公钥和相应的私钥。KGC随机选择一个主密钥sq∈[1,-1]和一个随机点PG∈，计算Ps=P并公1KGC布(,PP)。身份为ID的用户的公钥/私钥对为(,)QS，其中QH=()ID，KGCIDIDID*HG:0,1{}→1是一个散列函数；SsID=QID，由KGC计算给出。设协商双方A和B都已经从KGC得到了各自的长期私钥Ss=[]Q和Ss=[]Q。AABBA和B分别产生临时私钥ab,[∈1,-q1]，对应的临时公钥是TA=aP和TB=bP。双方相互交换TA和TB以后就能计算出共享密钥：Ke=•ˆˆ(,)(,)aQPeST(5.1)ABKGCABKe=•ˆˆ(,)(,)bQPeST(5.2)BAKGCBA通过下面的分析我们可以看出KA和KB是相等的。-47- 申请上海交通大学博士学位论文基于身份的可认证的群密钥协商方案Ke=•ˆˆ(,)(,)aQPeSTABKGCABa=•eQPˆˆ(,)(,)eSTBKGCABasbs=•eQPˆˆ(,)(,)eQPBAb=•eSTˆˆ(,)(,)eQP(5.3)BAAKGC=•eSTˆˆ(,)(,)ebQPBAAKGC=•ebQPˆˆ(,)(,)eSTAKGCBA=KB并且有：KKe==ˆ(,aQb+QP)。ABBAKGC上述协议提供了双方的隐含密钥认证和完善前向保密，并能抵抗已知密钥攻击。我们把该协议与STR方案融合起来，提出了一种高效的可认证的群密钥协商方案，称为IAGKA。5.2基于身份的可认证的群密钥协商方案5.2.1基本协议IAGKA使用的密钥树如图5-1所示。每个叶节点LN对应一个群成员，每个内部节点用于存放密钥协商的中间结果。因此，本方案也存在如何向群成员提供对内部节点的认证的问题。通过本文第4章的分析可知，可以通过为内部节点引入唯一的群长期公钥Q来解决这个问题。对应的群长期私钥只有合法的群成员才知道。叶节点LN的G<>i临时私钥r由对应的成员M随机产生，长期私钥S由KGC产生。内部节点IN的临iii<>j时私钥k是该节点的两个子节点进行两方密钥协商的结果。群密钥就是根节点的临时j私钥。*假设HG22:→Zp是一个安全的散列函数，那么ki的计算过程如下：⎧kr=11⎨⎩kHekQr=+=((ˆˆQP,))HekQPeSTi((,)(⋅>ˆ,))1ii21−−iiGKGC21iiKGCGi(5.4)图5-1中的群密钥就是内部节点IN3的临时私钥k3：kHe=+((ˆkQrQP,))32233GKGC=⋅HekQP((ˆˆ,)(,))eST223KGCG3(5.5)=⋅H((erQPˆˆ,)(,eSkP))23GKGC32-48- 申请上海交通大学博士学位论文基于身份的可认证的群密钥协商方案INk<3>3k/kP,IN22r/T,S/QLN<2>S/Q3333<3>GGM3IN<1>r/T,S/Qr/T,S/QLNLN11112222<2><1>MM12图5-1IAGKA密钥树Figure5-1IAGKAKeyTree5.2.2成员加入协议假设新成员M要加入有n个成员的群{,,}M"M，加入协议包括如下两条消n+114息：M→GrPQ:(5.7)nn++11n+1M→∪GM{}:BTQ(5.8)nn+<1n>G其中，Q和Q分别代表成员M和群公钥，BT代表包含知道的所有公钥的密iGi钥树。接收到消息5.7后，群G中的每个成员生成一个新的根节点IN，原来的根节1点IN成为新节点的左子节点，新叶节点LN作为右子节点。发起人是最顶端的<>n1叶节点，即M。M产生一个新私钥r'，然后计算所有被改变的密钥，并广播消息nnn5.8。接收到消息5.8以后，每个成员都能计算出新的群密钥。图5-2给出了M4加入群{,,}M123MM时密钥树的变化，发起人是M3。当M3广播了密钥树BT后，所有成员都能利用自己的私钥和BT中的公钥计算出新的群密<>4<4>钥。-49- 申请上海交通大学博士学位论文基于身份的可认证的群密钥协商方案M计算：4''kHe=⋅(ˆˆ(,)rQPe(Sk,)PHe)(=ˆ(rQk+QP,))(5.9)424GKGC4324G34KGCM计算如下：1''k=⋅HekQP((ˆˆˆ,)(,))eST=HekQrQP((+,))(5.10)3223KGCG32233GKGC'''k=⋅HekQP((ˆˆˆ,)(,))eST=HekQrQP((+,))(5.11)4234KGCG42344GKGCBeforeJoinAfterJoinNewNodeINk<4>4INk<3>3LNINLN<4><3><3>k'/k'P,INk/kP,33r/T,S/Q<2>22r/T,S/QS/Q4444S/Q3333GGGGINM4NewcomerM<2>3k/kP,IN22r'/T',S/Q<1>SponsorS/Q3333GGr/T,S/Qr/T,S/QLNLN11112222<3><1>MLN3MM<2>12IN<1>r/T,S/Qr/T,S/Q11112222LNLN<2><1>M1M2图5-2成员加入群时IAGKA密钥树的更新Figure5-2IAGKATreeUpdate(Join)5.2.3成员离开协议假设成员M()in≤要离开群{,,}M"M。如果i>1，则发起人M是要离开成11ns员下面的叶节点，即M，否则M是M。把叶节点LN提到原来IN的位置，i−1s21<+>i1'或把内部节点IN提到原来IN的位置。发起人M生成新的临时私钥r，计算所1ss有被改变的临时密钥，并广播给其它成员。图5-3给出了成员M离开群{,,}M"M时314'密钥树的变化，发起人是M。当M广播了临时公钥bk后，所有成员都能计算出群222密钥：-50- 申请上海交通大学博士学位论文基于身份的可认证的群密钥协商方案M计算：4'''k=⋅HerQP((ˆˆ,)(,eSkP))=HerQ((ˆ+kQP,))(5.12)324GKGC4224G24KGCM计算：1''k=⋅HerQP((ˆˆˆ,)(,))eST=HerQ((+rQP,))(5.13)2212KGC1221221KGC''''kHe=⋅((ˆˆˆkQPe,)(,))STHe=((kQr+QP,))(5.14)3224KGCG42244GKGC5.3安全性分析IAGKA方案的安全性基础是BDH假设，提供了隐含密钥认证、密钥独立（前向保密和后向保密）和抵抗已知密钥攻击等安全属性。5.3.1隐含密钥认证下面以成员加入协议为例说明IAGKA提供了隐含密钥认证，成员离开协议可以类似分析。假设A是能够监听到所有通信的被动攻击者，A是能够修改、删除和插入消息pasact的主动攻击者。以下讨论了9种典型的攻击情景：（1）被动攻击被动攻击者Apas能够得到的信息有(,,',')Qnn++11rPrPkPnn，Mn和Mn+1计算的群密钥分别是：kH=+=(('eˆˆkQrQ,))sPH((eQ,)Pksn'ieˆ(,))QPrsn+1(5.15)(,1)nn++2nn1n+1G2n+1GkH=+((((eˆˆHekQr',))QsPQ+rQ,))sP(5.16)(1,,"nn−−1)221nnGn++1n1G因为r是由M随机选取的,且只有M知道k'，s是KGC的私钥。由BDHn+1n+1nn假设很容易看出不能通过公式5.15计算出，而公式5.16中包含了更多的未知信息。*（2）用QP代替QPn+1n+1该替换对成员M没有影响，它的计算结果是：n+1kH=+(('eˆkQrQ,))sP(5.17)(1nn++)2n1n+1G-51- 申请上海交通大学博士学位论文基于身份的可认证的群密钥协商方案其它成员计算出的结果是：kH=+(('eˆkQr*Q,))sP(5.18)()nn2n++1n1GkH=++((((eˆˆHekQr',))QsPQ*rQ,))sP(5.19)(1,,"nn−−1)221nnGn++1n1G在不知道('ks,)的情况下计算eQˆ(*,)Pksn'相当于解决BDH问题，也就不能计nn+1算出k和k。虽然该替换导致kk=≠k，但攻击者不能计算出上()n(1,,"n−1)(1,,"nn−1)()(n+1)述任何一个结果。既然这种替换不能帮助攻击者计算出任何秘密信息，我们将不再讨论这种替换。*（3）用rP代替rPn+1n+1该替换对Mn+1没有影响，它计算出的密钥是：kH=+(('eˆkQrQ,))sP(5.20)(1nn++)2n1n+1G这种情况已经在上一种情况中讨论过。其它成员计算出的结果是：kH=+(('eˆkQrQ*,))sP(5.21)()nn2n++1n1GkH=+((((eˆˆHekQr',))QsPQ+r*,))QsP(5.22)(1,,"nn−−1)221nnGn++1n1G虽然攻击者能够计算出eQPˆ(,)rsn+1*，但在不知道('ks,)的情况下计算GneQˆ(,)Pksi'相当于解决BDH问题，因此攻击者不能得到k。同样，攻击者也不能n+1()n计算出k。该替换的结果是kk=≠k，但攻击者不能计算出其中的(1,,"n−1)(1,,"nn−1)()(n+1)任何一个密钥。*'（4）用rP代替rPnn在这种情况下，M、M和其它成员计算的密钥如下：n+1nkH=+(('eˆkQrQ,))sP(5.23)(,1)nn++2nn1n+1GkH=++((((eˆˆHekQr*,))QsPQrQ,))sP(5.24)(1,,"nn−−1)221nnGn++1n1G从前面的讨论可以知，攻击者不能计算出上述密钥。*'（5）用kP代替kPnn-52- 申请上海交通大学博士学位论文基于身份的可认证的群密钥协商方案在这种情况下，Mn+1,Mn和其它成员计算的密钥如下：kH=+((*eˆkQrQ,))sP(1nn++)2n1n+1GkH=+((eˆk'QrQ,sP))(5.25)()nn2n++1n1GkH=+((((eˆˆHekQrQ,))sPQ+rQ,))sP(1,,"nn−−1)221nnGn++1n1G这种情况与情况（3）类似。**''（6）分别用rP和kP代替rP和kPnnnn**我们假设Aact知道rn和kn，那么Mn+1,Mn和其它成员计算的密钥如下：kH=+((eˆk*QrQ,sP))(1nn++)2n1n+1GkH=+((eˆk'QrQ,sP))(5.26)()nn2n++1n1GkH=++((((eˆˆHekQr*,))QsPQrQ,))sP(1,,"n−−1)22nnnG1n++1n1虽然这些密钥不相等，但对攻击者来说都是不可能计算出来的。**'（7）分别用rP和rP代替rP和rPnn+1nn+1**'（8）分别用rP和kP代替rP和kPn+1nn+1n***''（9）分别用rP、rP和kP代替rP、rP和kPn+1nnn+1nn因为成员加入协议中的所有消息都是相互独立的，所以情况（7）与情况（3）和情况（4）类似，情况（8）与情况（3）和情况（5）类似，情况（9）与情况（3）和情况（6）类似。5.3.2前向保密和后向保密（密钥独立）因为每种成员关系变化事件所对应的密钥协商过程至少要更改一个成员的临时私钥，这会引起从该成员所对应叶节点到根节点路径上所有内部节点的密钥发生变化，而叶节点的临时私钥都是随机选择的，根据BDH假设可知，被动攻击者在不知道合法成员的长期私钥的情况下从旧密钥推导出新密钥或从当前密钥计算出旧密钥都是不可能的，即IAGKA提供了密钥独立。5.3.3抵抗已知密钥攻击由密钥独立可知被动攻击者不能从已知的群密钥计算出合法成员的长期密钥或其'它群密钥。内部节点的临时私钥为kHer=⋅<((ˆˆQPeSkP,)(,))(0in≤)。ii21GKGCii−假设主动攻击者A将其中的临时密钥r替换成自己知道的值c，那么k被转换成actiii-53- 申请上海交通大学博士学位论文基于身份的可认证的群密钥协商方案'''kHec=⋅((ˆˆQPeSkP,)(,))。由BDH假设可知，由k计算出Si(0<≤n)是ii21GKGCii−ii不可能的，所以Aact不能成功地假冒合法成员。由以上分析可以看出，IAGKA能够抵抗已知密钥攻击。5.4复杂性分析我们把IAGKA方案与AGKA-G方案和AGDH方案进行了复杂性比较，如表5-2所示。其中IAGKA方案的开销是平均开销，对于离开协议来说是第n/2个成员离开时的开销。AGKA-G方案的开销是当密钥树完全平衡时的平均开销。AGDH方案的开销则是准确开销。AGKA-G和AGDH使用了标准的DH密码方案，IAGKA使用的是基于身份的密码方案Boneh-FranklinIBE。表5-1列出了两种密码方案中最费时的密码操作在PIII1GHzPC上的执行时间。由表5-2可以看出，IAGKA方案对每一种成员关系变化事件都是通信轮数最少的，并且不象AGKA-G和AGDH那样需要传输证书，因此通信开销最小。加入协议的计算开销最小，但离开协议的计算开销比AGKA-G和AGDH大。由此可见IAGKA是一种通信开销较小的密钥协商方案，并且实现比较简单。5.5小结在IAGKA方案中，我们把基于身份的密码机制与二叉树结合起来。不但避免了使用传统密码机制所受到的安全威胁，而且通信开销和计算开销都比较小。该方案与本文第4章中PAGKA方案类似，也通过引入群长期私钥来提供成员间的隐含密钥认证。除此以外，IAGKA还提供了前向保密和后向保密，能够抵抗已知密钥攻击和中间人攻击。-54- 申请上海交通大学博士学位论文基于身份的可认证的群密钥协商方案BeforeLeaveAfterLeaveIN<4>k4IN<3>k3/k3P,LN<4>SG/QGr4/T4,S4/Q4IN<3>k3'INM4<2>LN<3>k2/k2P,S/Qr3/T3,S3/Q3IN<2>k2'/k2'P,GGr4/T4,S4/Q4LN<3>S'/Q'GGM3MembertoM4IN<1>leaver1/T1,S1/Q1r2/T2,S2/Q2IN<1>LNLN<2><1>r/T,S/QLN1111r2'/T2',S2/Q2<1>M1M2SponsorM1M2LN<2>图5-3成员离开群时IAGKA密钥树的更新Figure5-3IAGKATreeUpdate(Leave)表5-1DH和ECC密码操作的执行时间Table5-1TimeCostforDH&ECC密码方案操作执行时间（ms）DHRSA签名23.6（p是1024位，q是160位）RSA验证1.32取模求幂6.90ECC点乘3.34（p是192位，q是160位）TatePairing4.05表5-2IAGKA复杂性分析Table5-2ComplexityAnalysisforIAGKA方案事件轮数单播广签名验证取模点乘Tate播求幂PairingIAGKA加入2020053离开101003n/2-2n-1AGKA-G加入h2h0003h离开h2h0003h加入4n+124n+3n+3AGDH离开10111n-1注：n是当前群成员的数目，h是密钥树的高度。-55- 申请上海交通大学博士学位论文基于三叉树的可认证的群密钥协商方案第6章基于三叉树的可认证的群密钥协商方案本文第3章把三叉树和超奇异椭圆曲线上的Pairing结合起来，提出了一种高效的群密钥协商机制PTDH。该机制的通信轮数为常数，总通信量随成员数目的增加而增长的幅度可忽略，三叉树的使用使得其计算开销为On(log)。它提供的安全属性包括群3密钥保密和密钥独立。因此该方案比较适用于那些在高延迟网络中，但对安全性要求不太严格的群应用。本文的第4章和第5章分别提出了两种基于二叉树的可认证的群密钥协商方案PAGKA和IAGKA。这两种方案的通信轮数都为常数，计算开销为On(log)。它们都2提供了隐含的密钥认证，因此比较适用于高延迟网络中对安全性要求较高的群应用。在本章中，我们将上述方案的思想结合起来，即把三叉树引入到可认证的密钥协商协议中去，提出了分别与PAGKA和IAGKA相对应的两种可认证方案：基于Pairing和三叉树的可认证的群密钥协商方案TPAGKA以及基于身份和三叉树的可认证的群密钥协商方案TIAGKA。根据第3章中的分析可知，使用三叉树的方案的基本构成模块是一种三方密钥协商协议和一种相关的两方密钥协商协议。因此对本章的方案来说，除了第4章和第5章中提到的两方协议外，还需要相关的三方协议。另外，PAGKA和IAGKA的思想可用于把可认证的两方协议扩展成可认证的群密钥协商协议。因此在本章中，我们也使用这种扩展方法。6.1基于Pairing和三叉树的可认证的群密钥协商方案首先给出可认证的三方协议，为了保持内容的完整性，也给出相应的两方协议。6.1.1基于Pairing的可认证的三方密钥协商协议和两方密钥协商协议[62]S.Riyami提出了一种基于Pairing的可认证的三方密钥协商协议TAK-4。假设进行密钥协商的三方是A、B和C，它们使用的证书格式是：CertA=(IA||µA||P||Q||SCA(IA||µA||P||Q))。其中，IA代表A的身份标识字符串，||代表数据项的串接，SCA代表CA的签名。A*的长期公钥是µA=xP，其中x∈Zq是A的长期私钥。元素P和Q是公开的，用于指明构造µ以及临时公钥所使用的元素。设S={aP||bP│a,b∈*AZq且P∈G1}，则-57- 申请上海交通大学博士学位论文基于三叉树的可认证的群密钥协商方案*H1:S→Zq是一个散列函数。A、B和C的长期私钥/公钥对分别是（x,xP）、（y,yP）、*（z,zP），三者分别随机选取整数a,b,c∈Zq作为临时私钥，然后把相应的临时公钥aP(bP、cP)证书发送给其它两方。最后三方都能利用自己的长期密钥和临时密钥以及其它两方的长期公钥和临时公钥计算出共享密钥。三方协议的执行过程如图6-1所示，图6-2给出的是两方协议。AaP||CertAB、CBbP||CertBA、CCcP||CertCA、Bk=ebPˆ((++HbPyPyPcP||),(HcPzPzP||))aHaPxPx+1(||)A11k=eaPˆ((++HaPxPxPcP||),(HcPzPzP||))bHbPyPy+1(||)B11k=eaPˆ((++HaPxPxPbP||),(HbPyPyP||))cHcPzPz+1(||)C11k=ePPˆ(,)(aHaPxPxbHbPyPycHcPzPz+++111(||))((||))((||))ABC图6-1TAK-4协议Figure6-1TAK-4AaP||CertABbP||CertBk=eˆ(bP+H(bP||yP)yP,Q)a+H1(aP||xP)xA1k=eˆ(aP+H(aP||xP)xP,Q)b+H1(bP||yP)yB1k=eˆ(P,Q)(a+H1(aP||xP)x)(b+H1(bP||yP)y)AB图6-2两方TAK-4协议Figure6-2Two-partyTAK-4上述两种协议在协商过程中结合了长期密钥和临时密钥，提供了密钥独立性、完善前向保密和隐含密钥认证等安全属性。因此能够抵抗被动攻击和中间人攻击、已知密钥攻击等主动攻击。6.1.2基于Pairing和三叉树的可认证的群密钥协商方案下面利用三叉树把上述协议扩展到多方。为了提供完全的密钥认证，必须引入群长期密钥，作为密钥树中内部节点的身份信息。TPAGKA使用的符号与PAGKA相同，参见本文的表4-1。TPAGKA使用的密钥树如图6-3所示。-58- 申请上海交通大学博士学位论文基于三叉树的可认证的群密钥协商方案y/yPGGk<0,0>2y/yPy/yPGGGGk/kPk/kP<1,0><1,0><1,1><1,1>32y/yPy/yPy3/y3Py/yPy/yP2211r/rPr/rP4455r/rP2233r/rPr/rP11445500000MMMMM12345图6-3TPAGKA密钥树Figure6-3TPAGKAKeyTree第i层第j个节点N的临时私钥记作k，对应的盲密钥记作bk。节点N的子节点分别记作N、N和N。第m个成员产生的秘密密钥是rm。则k可如下计算：⎧⎫rN，若是叶节点mi<>,j⎪⎪ebkˆ((+Hbk||yPyP),⎪⎪<+>il1,1<+>il1,x1x1（6.1）k<>ij,=⎨⎬kH<++>il1,2+1(|bky<++>il1,2|x3P)yx3bk+Hbk(||yPyP))，若N有三个子节点⎪⎪<++>il1,11<++>il1,1x2x2<>ij,⎪⎪ˆ((||),)kH<++>il1,1+1(|bk<++>il1,1|yPyx2)x2ebk+HbkyPyPQ，若N有两个子节点⎩⎭<+>il1,1<+>il1,x1x1<>ij,若N（j＝1、2、3）是内部节点，那么yxj＝yG。若N是Mk对应的叶节点，那么yxj＝yk。每个成员需要计算从它所对应的叶节点到根节点的路径上所有节点的秘密密钥（图6-3中的黑色节点），在计算过程中还需要得到这些节点的兄弟节点的盲密钥（图6-3中的灰色节点）。下面以成员M1为例说明计算根密钥k<0,0>的过程。首先M1生成秘密密钥r（1k<2,0>），并得到M2和M3的盲密钥bk<2,1>和bk<2,2>和长期密钥（证书），这样M1就能计算出：k=+ebrˆ((Hbr||yPyPbr),(+Hbr||yPyP))rHbryPy11111+(||)(6.2)<>1,02122231333然后M1利用盲密钥bk<1,1>就能计算出根密钥：ke=+ˆ((bkHbky||P)yP,Q)kH<>1,0+1(|bky<>1,0|)GGPy(6.3)<>0,0<>1,11<>1,1GG当成员关系发生变化时，密钥树结构的更新方法以及发起人的选择原则都与PTDH类似，只有密钥协商过程不同。下面将通过例子来说明成员加入群和离开群时密钥更新的过程。-59- 申请上海交通大学博士学位论文基于三叉树的可认证的群密钥协商方案’图6-4给出了M6加入图6-3所示的群时密钥树的变化。发起人M4更新秘密密钥r4后重新计算图中所有黑色节点的密钥，然后广播相应得盲密钥。最后，所有成员都能利用自己的秘密密钥和BT<6>中的盲密钥计算出新的群密钥。M1、M2、M3计算：k'=+⋅+ekˆˆ((QQP),)eST(,(T))⋅ekˆ(,)QP⋅erQPˆ(,)(6.4)<>0,0<>1,0G6KGCG<>1,1<>1,2<>1,16KGC6GKGCM5用首先计算：ke'((=+ˆbr''Hbr||yP)yP,Q)rHb51555+(|ryPy|)(6.5)<>1,141444然后计算：''k'((=+ebrHbryPyPbkˆ||),+Hbk(||yPyP))kH<>1,1+1(|bky<>1,1|)GGPy(6.6)<>0,061666<>1,01<>1,0GGM6计算：k'(=+ebkˆ''Hbk(||yPyPbk),+Hbk(||yPyP))rHb61666+(|ryPy|)(6.7)<>0,0<>1,11<>1,1GG<>1,01<>1,0GG<0,0>3<1,2><1,0><1,1>320M6Newcomer<2,0><2,1><2,2><2,3><2,4>00000M1M2M3M4M5Sponsor图6-4成员加入群时TPAGKA密钥树的更新Figure6-4TPAGKATreeUpdate(Join)图6-5给出了成员M7离开群{M1、M2、M3、M4、M5、M6、M7}时的密钥树变化，发起人是M1。M1更新了秘密密钥以后，计算出图中所有黑色节点的秘密密钥，并广播相应的盲密钥br1’、bk<2,0>’和bk<1,0>’。接收到这些盲密钥以后，所有成员都能计算出新的群密钥。M2和M3分别首先分别计算：k'((=+ebrˆ''Hbr||yPyPbr),(+Hbr||yPyP))rHb21222+(|ryPy|),(M)(6.8)<>1,011111313332-60- 申请上海交通大学博士学位论文基于三叉树的可认证的群密钥协商方案k'((=+ebrˆ''Hbr||yPyPbr),(+Hbr||yPyP))rHb31333+(|ryPy|),(M)(6.9)<>1,011111212223’然后计算k<0,0>：''ke'(=+ˆbkH(|bky|P)y,Q)kH<>1,0+1(|bky<>1,0|)GGPy(6.10)<>0,0<>1,11<>1,1GG’M4、M5和M6计算k<0,0>：ke'(=+ˆbkH''(|bky|P)yP,Q)kH<>1,1+1(|bky<>1,1|)GGPy(6.11)<>0,0<>1,01<>1,0GG计算出新密钥后，每个成员都可以解密得到新的群长期密钥。<0,0>2<1,0><1,1><1,2>320M7Memberto<2,0><2,1><2,2><2,3><2,4>Leave00020MMMM1236Sponsor<3,0><3,1>00MM45图6-5成员离开群时TPAGKA密钥树的更新Figure6-5TPAGKATreeUpdate(Leave)6.2基于身份和三叉树的可认证的群密钥协商方案首先给出基于身份的可认证的三方密钥协商协议和基于身份的可认证的两方协议。6.2.1基于身份的可认证的三方密钥协商协议和两方密钥协商协议D.Nalla和K.C.Reddy提出了一种基于身份的可认证的三方密钥协商协议[62]ID-AK-3。该协议使用的符号和参数与IAGKA中的相同，参见本文第5章。-61- 申请上海交通大学博士学位论文基于三叉树的可认证的群密钥协商方案假设协商三方A、B和C都已从KGC得到了各自的私钥Ss=Q、Ss=Q和AABBSsCC=Q。A、B和C分别产生临时私钥a,b,c∈[1,q-1]，对应的临时公钥是TA=aP、TB=bP、TC=cP。其协商过程如图6-6所示。图6-7给出了基于身份的两方协议的执行过程。6.2.2基于身份和三叉树的可认证的群密钥协商方案下面利用三叉树把上述协议扩展到多方。TIAGKA使用的符号与IAGKA相同。TIAGKA使用的密钥树如图6-8所示。TaABC,Qa,QAB⎯⎯⎯⎯⎯→,CTbBAC,Qb,QB⎯⎯⎯⎯⎯→,ACTcCAB,Qc,QCA⎯⎯⎯⎯⎯→,Bke=+ˆˆ((aQQPe),)(,(⋅+STTe))(,⋅ˆbQPe)(,⋅ˆcQP)ABCKGCABCCKGCBKGCke=+ˆˆ((bQQPe),)(⋅+STTe,())(⋅ˆaQPe,)(⋅ˆcQP,)BACKGCBACCKGCAKGCkecQQP=+ˆˆ((),)(,(⋅+eSTTeaQP))(,⋅ˆ)(,⋅ebQPˆ)CABKGCCABBKGCAKGCke=+ˆ((aQQb)(++QQc)(++QQ),P)ABCBCACABKGC图6-6基于身份的可认证的三方密钥协商协议Figure6-6Identity-basedTripartyKeyAgreementProtocolTABYZZZZZXZAC,TBke=ˆˆ(,)(,)aQPe•STABKGCABke=ˆˆ(,)(,)bQPe•STBAKGCBAk===kkeaQˆ(,+bQP)ABABBAKGC图6-7基于身份的可认证的两方密钥协商协议Figure6-7Identity-basedTwo-partyKeyAgreementProtocol-62- 申请上海交通大学博士学位论文基于三叉树的可认证的群密钥协商方案S/QGGk<0,0>2S/QS/QGGGGk/kPk/kP<1,0><1,0><1,1><1,1>32S/QS2/Q2S3/Q3S/QS/Q114455r/rPr2/r2Pr3/r3Pr/rPr/rP11445500000MMMMM12345图6-8TIAGKA密钥树Figure6-8TIAGKAKeyTree第i层第j个节点N的临时私钥记作k，N的子节点分别记作N、N和N。第m个成员产生的秘密密钥是rm。则k可如下计算：⎧⎫rN，若是叶节点mi<>,j⎪⎪⎪⎪ekˆˆ((Q+⋅+Q),)PeST(,()T)<+>il1,x2x3KGCx1x2x3k=⎨⎬<>ij,⋅⋅ekˆˆ(,QP)ek(,QP)，若N有三个子节点(6.12)⎪⎪<++>il1,1xK3GC<++>il1,2xK2GC<>ij,⎪⎪ekˆˆ(,QP)⋅eST(,)，若N有两个子节点⎩⎭<+>ilxK1,2GCxx12<>ij,若N（j＝1、2、3）是内部节点，那么Qxj＝QG，Sxj＝SG。若N是Mk对应的叶节点，那么Qxj＝Qk，Sxj＝Sk。下面以成员M1为例说明计算根密钥k<0,0>的过程。首先M1生成秘密密钥r1（k<2,0>），并得到M2和M3的临时和长期公钥，这样M1就能计算出k<1,0>：eˆˆ((rQQPe+⋅+),)(,(STTe))(⋅ˆrQ,Pe)(⋅ˆrQ,P)(6.13)123KGC12323KGC32KGC然后M1利用盲密钥T<1,1>就能计算出根密钥：ke=⋅ˆˆ(,kQPe)(S,T)(6.14)<>0,0<>1,0GKGCG<>1,1成员关系发生变化时密钥更新的过程与TPAGKA类似，在此通过例子来说明各成员计算新密钥的过程。对图6-4所示的M6加入群{M1、M2、M3、M4、M5}时的情况，发起人M4更新秘密’密钥r4后重新计算图中所有黑色节点的密钥，广播了相应盲密钥后，各成员可如下计算新的群密钥：M1、M2、M3计算：-63- 申请上海交通大学博士学位论文基于三叉树的可认证的群密钥协商方案k'=+⋅+ekˆˆ((QQP),)(,eST(T))(,)(,)⋅ekQPˆ⋅erQPˆ(6.15)<>0,0<>1,0G6KGCG<>1,1<>1,2<>1,16KGC6GKGCM5计算：'ke'(=⋅ˆˆrQ,)Pe(S,T)(6.16)<>1,145KGC45'k'=(ekˆˆ(Q+⋅+QP),)eST(,(T))⋅ekˆ(QP,)⋅erQPˆ(,)(6.17)<>0,0<>1,1G6KGCG<>1,06<>1,06KGC6GKGCM6计算'k'=+⋅erQˆˆˆ((QP),)(,eST(+⋅T))(ekQP,)(⋅ekˆQP,)(6.18)<>0,06GGKGC6<>1,0<>1,1<>1,0GKGC<>1,1GKGC对图6-5所示的成员M7离开群{M1、M2、M3、M4、M5、M6、M7}时的情况，发起人是M1。接收到被改变的盲密钥以后，所有成员都能计算出新的群密钥。’M2(M3)计算k<1,0>：''k'(=+⋅+erQQPˆˆ(),)eSTT(,())⋅erQPˆ(,)⋅erQPˆ(,)(6.19)<>1,0213KGC21313KGC31KGC''(ke'=+⋅+ˆˆ(r(QQ),)(PeS,()TT)(,)(,)⋅eˆrQPe⋅ˆrQP(6.20)<>1,0312KGC31212KGC21KGC'=ˆˆ(',)(,)kekQPe⋅ST(6.21)<>1,0<>1,0GKGCG<>1,1M、M和M用ˆˆ(,)(,)'’。456ekQP<>1,1GKGC⋅eSTG<>1,0计算出k<0,0>计算出新密钥后，每个成员都可以解密得到新的群长期密钥。6.3安全性分析TPAGKA和TIAGKA提供的安全属性与PAGKA和IAGKA类似，它们的安全性基础都是BDH假设。长期密钥（成员身份信息）和临时密钥的结合使用保证了隐含密钥认证。密钥更新过程中临时密钥的改变保证了密钥独立，也保证了完善前向保密性。另外，群长期私钥SG的引入使得原来没有身份信息的中间节点有了向除发起人以外的其它群成员提供认证的方法。具体分析过程分别与本文第4章和第5章类似，在此不再赘述。6.4复杂性分析TPAGKA和TIAGKA与PTDH的密钥树结构相同，因此通信的轮数与PTDH相同。但由于密钥计算过程的不同，使得它们的计算开销有所差别。很显然，为了提供隐含密钥认证，TPAGKA和TIAGKA的计算量比PTDH大。因此，在这里我们仅把它们与同样提供了隐含密钥认证的PAGKA和IAGKA进行比较。-64- 申请上海交通大学博士学位论文基于三叉树的可认证的群密钥协商方案本文所提出方案的通信开销为常数，而计算开销除了决定于成员加入的位置和离开位置外，还受到密钥树平衡程度的影响。表6-1给出了TPAGKA和PAGKA的比较结果。表6-2给出了TIAGKA和IAGKA的比较结果。其中给出的开销是理想情况下的最大开销。由表6-1可以看出，TPAGKA的离开协议的开销比PAGKA小，当n<27时，其加入协议的开销比PAGKA小，当n>26时，加入协议的开销较大，但计算开销随成员数目增长的速度较小。因此该方案对于网络延迟较高的群应用来说具有较高的可扩展性。在表6-2给出结果中，TIAGKA需要的Pairing计算次数是在考虑了双线性的基础上尽可能合并Pairing计算而优化后的结果。例如：把ekˆˆ(,QP)⋅ek(,QP)合并成ekˆ(,Q+kQP)。由表6-2<++>il1,1xK3GC<++>il1,2xK2GC<++>il1,1x3<++>il1,2xK2GC可以看出，TIAGKA的离开协议的开销比IAGKA小，加入协议的开销较大。但计算开销随成员数目增长的速度较小，同样适用于网络延迟较高的群应用。表6-1TPAGKA复杂性分析Table6-1ComplexityAnalysisforTPAGKA方案事件轮数单播广播点乘TatePairingTPAGKA加入2023log⎡n⎤−42log⎡⎤n−2⎢3⎥⎢⎥3离开101nn3log⎡⎤−42log⎡⎤−2⎢3⎥⎢⎥3PAGKA加入20253离开1013n-52n-3表6-2TIAGKA复杂性分析Table6-2ComplexityAnalysisforTIAGKA方案事件轮数单播广播点乘TatePairingTIAGKA加入2023log⎡n⎤−42log⎡⎤n−2⎢3⎥⎢⎥3离开101nn3log⎡⎤−42log⎡⎤−2⎢3⎥⎢⎥3IAGKA加入20253离开1013n-52n-3-65- 申请上海交通大学博士学位论文基于三叉树的可认证的群密钥协商方案6.5小结在本章中，我们把三叉树与可认证协议结合起来，提出了一种基于Pairing和三叉树的可认证的群密钥协商方案TPAGKA及一种基于身份和三叉树的可认证的群密钥协商方案TIAGKA。通过举例说明了两种方案的加入协议和离开协议的协商过程。TPAGKA和TIAGKA提供了隐含密钥认证，完善前向保密，能够很好地抵抗中间人攻击等主动攻击。两种方案的通信开销都为常数，计算开销为O(log3n)。因此，具有较高的可扩展性，适用于网络延迟较高的群应用。-66- 申请上海交通大学博士学位论文安全群通信平台原型的设计与实现第7章安全群通信平台原型的设计与实现[30]为了简化分布式应用的开发，出现了大量可靠的群通信系统，群应用开发者只需要在此基础上实现特定功能，而不需要关心底层的通信细节。比较成熟的群通信系统包[31][32][33]括Spread、Totem和InterGroup。基于这些系统实现了很多不同领域的分布式应[31]用，如：航空交通控制系统、大型仿真系统、股票交易系统和数据库备份系统等。大[29]部分群通信系统提供的基本服务包括：（1）定义群，即定义一个进程集合，集合中的所有进程能够接收到发送给群的任何消息。（2）向群多播消息。（3）按一定顺序向群发送可靠的消息。（4）维护群的成员关系。（5）提供强语义模型来定义当成员关系发生变化时处理消息的方式。[31]Spread是目前功能最完善、性能最好的群通信系统之一，而且有完全开放的源码。[29]它的早期版本已经被很多组织用于研究和实际项目。Spread支持跨平台应用，并且已经移植到多个Unix平台和Windows上，因此我们把它作为研究的基础。7.1安全群通信平台的体系结构在设计一个安全群通信系统时，需要重点考虑的是所使用密码算法和密钥管理算法的安全性和可靠性。随着时间的推移，这些算法的可靠性可能会发生变化。例如，算法被攻破了，算法被证明是不安全的或出现了更好的算法。因此任何需要长期保持安全通信的系统都必须足够灵活，易于修改。另一个要求是管理员或终端用户必须能够很容易地修改安全策略。实现上述目标的一种方法是设计一个完全模块化的系统。作为我们研究重点的Spread系统就具有很好的模块化结构。为了适应各种不同的分布式应用的需求，Spread以一种非常灵活的方式提供基本服务，使得不同的应用可以选择最合适的方法来调用群通信原语。Spread的模块化结构主要体现在两个方面：在网络通信层支持多种链路协议；支持多种客户接口。基于以上分析，本文的安全群通信平台采用了分层结构。安全的群通信服务是以客户函数库的形式提供的，该函数库建立在Spread虚拟同步（VS）函数库之上。图7-1给出了安全群通信平台的体系结构。该平台的功能是通过一个事件处理循环来实现的。成员关系变化事件（成员加入和成员离开）由底层Spread通信系统产生，安全群通信-67- 申请上海交通大学博士学位论文安全群通信平台原型的设计与实现层接收到这些事件后根据其上下文传送到相应模块进行处理。如果事件是接收或发送一个普通消息，那么该消息就被传送到加密模块进行解密或加密。如果是成员关系变化事件，就把它转换成对应的密钥协商模块能够处理的事件，然后调用需要的密钥协商方案。应用程序安全群通信层(VS)密钥协商方案密钥协商协议1密钥协商选择器事件处理引擎密钥协商协议n加密选择器加密方案Spread库加密算法1加密算法n网络图7-1安全群通信框架Figure7-1ArchitectureofSecureGroupCommunication该平台的核心是事件处理引擎。每当成员关系发生变化时，事件处理引擎就会初始化某种密钥协商协议的一个实例，并确保该实例的正确执行。当协议终止时，就会有一个安全的群成员关系变化消息传输给应用程序，应用程序将使用新的群密钥。如果需要加入新的密钥协商协议，只要在事件处理引擎中加入该协议的访问接口，并在适当的时候调用就可以了。群密钥的计算是对应于某个特定的群的。一个客户可能成为多个群的成员，而每个群可以使用不同的密钥协商协议来管理密钥。密钥协商选择器和加密选择器分别用于识别每个群使用的密钥协商协议和加密算法。7.2主要实现技术本文共提出了五种适用于动态对等群的密钥协商方案，其中包括三种基于三叉树的方案和两种基于二叉树的方案。这些方案都是基于椭圆曲线密码机制的，都把超奇异椭圆曲线上的Pairing作为计算密钥的基础操作。因此它们使用的数据结构是非常类似的。我们根据图7-1所示的体系结构，以Spread作为底层通信系统，实现了基于二叉树的两种协议（PAGKA和IAGKA），并以API的形式提供给用户。-68- 申请上海交通大学博士学位论文安全群通信平台原型的设计与实现[92]目前该平台的加密模块采用了OpenSSL库提供的一种高效的对称分组加密算法[93]Blowfish，Blowfish可以使用变长密钥（32位到448位）对大小为64个字节的分组进行加密。当成员要求加密消息时，安全群通信层就调用通用加密函数，通用加密函数[92]又进一步调用Blowfish中的相应函数。事实上，我们能够很容易地把OpenSSL库中的其它密码算法加入进来，只要在加密选择器中提供相应的接口就可以了。当成员关系发生变化时，密钥重发的处理过程与加密过程相似。安全群通信层调用通用密钥协商函数，通用函数根据用户的选择调用密钥协商API中的相应函数来实现密钥协商。由于Spread本身提供了几种密钥协商协议，包括GDH、BD、TGDH和STR（参考本文第2章），因此本文在保持其整体编程框架不变的情况下加入新的协商协议，并对相应的数据结构进行修改。下面主要从数据结构和密钥协商API两个方面介绍平台的主要实现技术。7.2.1密钥协商API使用的主要数据结构和定义[94]我们在实现这些方案时使用了斯坦福大学的IBE系统。由于原系统功能比较复杂，而本文主要使用基本的椭圆曲线密码操作和Pairing计算部分，因此把其中相关的原语提取出来，并根据需要进行适当修改，然后封装成API（称为IBEAPI），以静态库的形式提供给密钥协商API使用。下面首先介绍IBEAPI使用的主要数据结构，并在此基础上说明密钥协商API使用的主要数据结构。[23]IBE库是对Boneh-Franklin密码机制的C语言实现，其中的操作是建立在椭圆曲[95][92]线EFp以及相关有限域F2上的。IBE在底层使用了GMP库和OpenSSL库，分p别用于多精度数的数学运算和基本密码原语操作。表7-1给出了IBEAPI使用的主要数据结构。-69- 申请上海交通大学博士学位论文安全群通信平台原型的设计与实现表7-1IBEAPI使用的主要数据结构Table7-1DataStructureforIBEAPI描述F2上的元素，表示形式是a+bi。p字段名称类型内容fp2_t内容ampz_t元素的实数部分bmpz_t元素的虚数部分描述椭圆曲线EF（表示形式是y2=x3+1）上的点。p字段名称类型内容point_txfp2_t点的x坐标内容yfp2_t点的y坐标infinityint该点是不是无限远点描述系统中使用的主要参数。字段名称类型内容idchar*参数集的id值versionchar*参数集的版本号p,qmpz_t有限域上的主要参数：params_tp=11mod12，p=12q-1。内容Ppoint_t用于求公开密钥的基本点Qpoint_t求Pairing时使用的另一个点Ppubpoint_tKGC的公钥xmpz_t*KGC的私钥curvecurve_t所使用的椭圆曲线PAGKA和IAGKA把密钥树与椭圆曲线密码机制结合起来，其数据结构主要是在二叉树中加入IBEAPI中的数据结构，表7-2给出了PAGKA的主要数据结构。-70- 申请上海交通大学博士学位论文安全群通信平台原型的设计与实现表7-2PAGKA使用的主要数据结构Table7-2DataStructureforPAGKA描述由群成员名组成的链表。字段名称类型内容PAGKA_内容Member_namechar*成员名NAME_LISTnextstruct下一个成员pagka_name_list*描述群成员的基本信息。字段名称类型内容PAGKA_GMMember_namechar*成员名内容certX509*如果是叶节点，那么X.509证书非空。描述密钥树上节点的信息。字段名称类型内容memberPAGKA_GM*如果是叶节点，则member是成员的基本信息，否则为空。indexuint节点的索引号。内部节点的索引号是偶数，叶节点的索引号是奇数。有两种例外情况：根节点的索引号是1，最左边的成员的索引号是2。keyBIGNUM*如果该节点处在到根节点的密钥路径上，则key为该节点PAGKA_NV内容的秘密密钥，否则为空。bkeyBIGNUM*如果该节点处在到根节点的密钥路径上或是相关的兄弟节点，则key为该节点的公开（盲）密钥，否则为空。num_userint成员数目-71- 申请上海交通大学博士学位论文安全群通信平台原型的设计与实现描述密钥树的信息。字段名称类型内容parentstruct指向父节点的指针。pagka_key_tree*leftstruct指向左子节点的指针。pagka_key_tree*rightstruct指向右子节点的指针。PAGKA_内容pagka_key_tree*KEY_prevstruct指向前一个节点的指针，如果TREEpagka_key_tree*该节点是内部节点，则为空。nextstruct指向后一个节点的指针，如果pagka_key_tree*该节点是内部节点，则为空。pagka_nvPAGKA_NV*如果该节点是内部节点，则给出其信息。描述在特定的群中某个成员的上下文信息。字段名称类型内容member_namechar*成员名group_namechar*群名group_secretBIGNUM*群密钥rootPAGKA根节点_KEY_TREE*PAGKA_内容ibeparamsparams_t*椭圆曲线密码机制的参数CONTEXTstatusint该成员计算群密钥的状态，已计算出或正在计算。tmp_keympz_t*临时私钥（随机秘密数值）tmp_bkeypoint_t*临时公钥epochuint所处理的上一条消息的序号。-72- 申请上海交通大学博士学位论文安全群通信平台原型的设计与实现描述PAGKAAPI使用的通信标志。字段名称类型内容message_typeenum消息类型，包括三种类型：PAGKA_PAGKA_MSPAGKA_KEY_MERGE_UTOKEN_G_TYPEPDATE、INFO内容PAGKA_PROCESS_EVENT、PAGKA_INVALIDgroup_namechar*群名称time_stamptime_t时间戳sender_namechar*发送者的名称7.2.2密钥协商API提供的主要函数本节以PAGKAAPI为例说明密钥协商API提供的主要函数，因为我们是以STRAPI为基础来实现PAGKAAPI的，因此二者提供的高层函数类似，主要区别在于底层的运算方法。下面详细介绍新增加的函数和需要修改的函数。（1）voidpoint_to_mpz(mpz_tx,point_tres,params_t*params)在密钥更新协议中，每个成员都需要计算其它成员的公开信息，如H1(bP||yP)yP。该函数把点转换成整数，这样就可以调用OpenSSL库提供的一般散列函数了。（2）voidfp2_to_mpz(mpz_tx,fp2_tres,params_t*params)因为TatePairing的计算结果是有限域上F2的，不能直接用于下一轮密钥协商，p因此必须转换成符合要求的整数。（3）point_t*pagka_compute_bkey(mpz_t*key,params_t*params)在密钥更新协议中，每个成员都需要调用该函数来计算与某个秘密密钥相对应的盲密钥，即key*P。（4）mpz_t*pagka_compute_parent(mpz_t*key,point_t*bkey,params_t*params)在密钥更新协议中，每个成员都需要调用该函数用密钥树上一个节点的秘密密钥和key兄弟节点的盲密钥计算出父节点的秘密密钥，即eˆ(bkey,Q)。（5）intpagka_new_member(PAGKA_CONTEXT**ctx,char*member_name,char*group_name)每个新成员调用该函数产生自己的上下文，主要功能是产生随机秘密数值。-73- 申请上海交通大学博士学位论文安全群通信平台原型的设计与实现（6）intpagka_merge_req(PAGKA_CONTEXT*ctx,char*member_name,char*group_name,PAGKA_TOKEN_INFO**output)当有新成员发出加入请求时引起Spread产生加入事件，包括新成员在内的所有成员接收到加入事件通知后调用该函数计算新的群密钥。（7）intpagka_leave(PAGKA_CONTEXT*ctx,char*group_name,char*member_name,PAGKA_TOKEN_INFO**output)当有成员离开群时，剩余成员调用该函数计算新群密钥，但只有发起人返回要包含所有盲密钥的消息。7.3实验分析我们在该平台上提供了密钥协商API的访问接口，使得群成员能够通过PAGKA方案和IAGKA方案进行密钥协商。本文的第4章和第5章分别对这两种方案的复杂性进行了理论分析。本章则对这些方案（与Spread集成后）在局域网和广域网中的性能进行了实验分析。同时我们还在该平台上实现了AGDH方案，并与PAGKA和IAGKA进行了比较。本文第3.4节分析了计算密钥协商计算开销的两种方法：平均开销和最大开销。在实验中，我们给出的结果是平均开销。7.3.1局域网中的实验结果首先对这三种方案在局域网中的性能进行比较。我们用五台运行RedHatLinux7.1或RedHatLinux7.2的PC（800MHz，128MB内存）组成一个小局域网，它们之间通过100Mbps以太网相连。每台PC运行一个Spreaddaemon，群成员均匀地分布在这五台机器上。实验表明，当成员关系发生变化时，Spread（包括VS通信层）建立新的成员关系所需要的时间随成员数目的增加而线性增加，这是因为每个成员在更新群成员关系以前需要接收来自新成员关系中每个成员的一条消息。在本文的实验环境下，成员数目为2到30的群更新成员关系所需要的时间为5ms到14ms，这相对于密钥协商所需要的几百毫秒来说可以忽略不计。对于AGDH方案，本文使用RSA（由OpenSSL库提供）进行数字签名和验证。因为对RSA签名的验证是非常高效的，而AGDH中每个接收者都要验证接收到的消息，有助于抵消因在同一台机器上运行多个用户进程而导致签名验证开销的增加，使实验结果更接近实际情况。我们使用了1024位的RSA签名（e=65537），一次签名和验证操-74- 申请上海交通大学博士学位论文安全群通信平台原型的设计与实现作的执行时间分别是29.7ms和1.7ms。Diffie-Hellman参数p和q分别是1024位和160位，执行一次取模求幂操作的时间是12ms。对于椭圆曲线密码机制，参数p和q分别是192位和160位，执行一次带预运算的点乘操作和TatePairing分别需要3.87ms和5.5ms。AGDH方案的开销与成员加入或离开的位置没有关系，只与成员数目相关，因此我们给出的实验结果是精确的。PAGKA方案和IAGKA方案的加入协议的开销是准确的，而离开协议的开销则是平均值，即第n/2个成员（处在密钥树的中间位置）离开群时的开销。7.3.1.1加入协议的实验结果图7-2给出了三种方案在一个新成员加入群时的平均开销。从总体上来看，PAGKA的性能最好。IAGKA的开销与AGDH相当，原因是每轮的两次TatePairing计算中有一次不能使用预运算（因为两个点都不是固定的）。当成员数目n<16时，IAGKA的开销较大，但AGDH的开销随成员数目线性增加，当成员数目n>30时，AGDH的开销比IAGKA大。虽然理论分析表明PAGKA和IAGKA的开销是常数，但其实验开销随成员数目略微增加，这是因为成员数目的增加会使得每台机器上的进程数增加，管理密钥树的开销也会增加。700AGDHPAGKA600IAGKAMembershipService500400300Time(ms)2001000051015202530GroupSize图7-2局域环境中成员加入群时的执行时间Figure7-2CostofMemberJoininLAN-75- 申请上海交通大学博士学位论文安全群通信平台原型的设计与实现7.3.1.2离开协议的实验结果图7-3给出了成员离开群时建立新的成员关系所需要的平均时间。因为AGDH方案的取模求幂操作的次数最少，因此性能最好。PAGKA和IAGKA的开销明显大于AGDH的开销，其主要原因是点乘和TatePairing操作的次数随成员数目线性增加。7.3.2广域网中的实验结果本节中给出在高延迟广域网中的实验结果。为了得到具有一定延迟的广域网环境，我们在局域网中进行了仿真。因为每个成员都是在发起人广播了中间结果以后分别计算出群密钥，因此可以通过在Spread通信层的发送消息函数中加入等待时间来模拟一定的网络延迟。在本文的实验中设置的延迟是150ms。为了便于比较各种方案在局域网和广域网中的性能差别，我们使用相同的密码参数（参见第7.3.1节），并且执行与局域网中相同的实验过程。2000AGDH1800PAGKA1600IAGKAMembershipService140012001000800Time(ms)6004002000-200051015202530GroupSize图7-3局域环境中成员离开群时的执行时间Figure7-3CostofMemberLeaveinLAN由前面的实验可知，在局域网中成员关系服务的开销是可以忽略的，而在广域网中，情况则完全不同。在本文的仿真环境中，对于成员数目为2到30的群来说，当成员加入时更新视所需要的时间为600ms到950ms，成员离开时需要300ms到900ms。7.3.2.1加入协议的实验结果图7-4给出了三种方案在新成员加入群时的平均开销以及成员关系服务需要的开-76- 申请上海交通大学博士学位论文安全群通信平台原型的设计与实现销，二者的差就是密钥协商方案本身的开销（包括通信开销和计算开销）。从图中可以看出AGDH的开销明显大于其它方案的开销，这主要是由AGDH的通信开销造成的。AGDH需要4轮通信，而其它方案只需要2轮。另外，当每个成员接收到来自群控制器的消息后，它们分别除去自己的秘密数值，然后用单播的方式发送给群控制器。虽然是n个并发的单播，但为了保证协议的正确执行，n个消息是以Agreed方式发送的，这会大大增加所需开销。PAGKA和IAGKA方案的开销相差不大。PAGKA的开销最小，AGDH的开销最大。二者的开销差别主要是由计算开销不同造成的。由此可见，在高延迟网络中加入协议的通信开销对其性能具有很大影响，而计算开销的影响相对减弱。AGDHPAGKAIAGKA3500MembershipService300025002000Time(ms)15001000500051015202530GroupSize图7-4广域环境中成员加入群时的执行时间Figure7-4CostofMemberJoininWAN7.3.2.2离开协议的实验结果虽然三种方案都只需要1条广播消息，但由于PAGKA和IAGKA的计算开销相对较大，因此整体性能比AGDH方案差。由此可见，在广域网中通信开销决定了离开协议的整体性能，而计算开销仍然是决定不同协议之间性能对比的重要因素。-77- 申请上海交通大学博士学位论文安全群通信平台原型的设计与实现2800AGDH2600PAGKAIAGKA2400MembershipService220020001800160014001200Time(ms)1000800600400200051015202530GroupSize图7-5广域环境中成员离开群时的执行时间Figure7-5CostofMemberLeaveinWAN7.4小结我们实现了一个采用分层结构的安全群通信平台的原型系统。底层由Spread系统提供可靠的群通信服务、成员关系服务和虚拟同步语义服务。上层的密钥管理模块中包含了AGDH方案和本文提出的两种基于二叉树的可认证方案。我们把这些方案的具体实现封装成API，以库的形式提供给用户，本章给出了主要的数据结构和函数。最后我们对该原型系统在局域网和仿真的高延迟广域网中的性能进行了测试，给出了四种方案的加入和离开协议以及底层成员关系服务在不同情况下的（成员数目）平均执行时间。实验表明，在低延迟网络中计算开销是决定群密钥协商方案性能的关键因素，而在高延迟网络中通信开销起决定作用。从总体上来看，不管是在局域网中还是在广域网中PAGKA加入协议的开销最小，IAGKA的开销比前者大，但仍然比AGDH的开销小。PAGKA和IAGKA离开协议的开销较大，特别是在局域网中明显比其它协议的开销大，而在广域网中通信开销的增大使得三种离开协议的开销差别不大。考虑到具体实现方法对性能的影响，本章的实验结果与第4章和第5章中的理论分析基本吻合。-78- 申请上海交通大学博士学位论文群通信系统的通用安全框架与应用第8章群通信系统的通用安全框架与应用在本文的前6章，我们重点研究了群密钥协商协议，第7章给出的群通信平台则以密钥协商为基础提供了数据加密和签名两种安全功能。由本文第1.1节的分析可知，该平台仅为群应用提供了信息的保密性和完整性，而成员对群服务的访问是不受控制的，其它安全服务（包括密钥协商、数据加密和签名）都不可能真正起作用。一个实用的群通信系统必须保证只允许被授权的用户（访问控制机制）加入群密钥协商过程，进而合法地使用各种群服务。本章的研究重点是在第7章的平台上集成必要的访问控制机制，实现一个安全可靠的群通信平台。虽然目前对信息系统中访问控制机制的研究已经比较成熟了，但对它们在群通信系统中的含义以及如何集成等方面的研究还比较少。大部分的可靠群通信系统都采用客户－后台程序结构，即少数后台程序为多数客户提供群通信服务，如Spread系统。因此[121][122]本章在YairAmir和M.R.Thompson工作的基础上研究了Spread系统的安全框架，主要针对如下几个问题：（1）访问控制机制与Spread如何集成以达到灵活高效的目标。（2）群的动态性对安全策略的影响。（3）通过对一些典型群应用的分析说明该框架的通用性和可扩展性。8.1群通信系统的安全框架群通信系统要为各种不同的协作式应用提供通信服务，因此其安全框架也必须允许使用多种实现机制并以简单有效的方式提供给群应用开发者使用。安全机制与可靠群通信系统的集成方法会对平台的性能和灵活性产生重大影响。集成方法主要可分为两类[121]：一类是把特定的密钥管理协议、一种标准加密算法和现有的访问控制机制与可靠的群通信系统邦定在一起。这种系统能够很好地适应某种特定应用的需要，但功能固定，并且由于需要把安全属性与通信协议和密钥管理协议等交织在一起而变得比较难维护。另一类方法是构造一个通用的体系结构，允许群应用安装需要的安全策略以及实施该策略所需要的安全机制。既然每个应用都有特定的安全需求和性能需求，因此允许它们对安全策略的定义和实施方法进行更多控制是很自然的。另外，由于策略条例和访问规则的变化比起核心系统的变化要频繁的多，因此安全策略的修改不应该引起应用程序代码的修改或重新编译，即需要把安全策略的实施与群应用和群通信系统分离开。-79- 申请上海交通大学博士学位论文群通信系统的通用安全框架与应用根据以上分析，群通信系统的通用安全框架应该具备如下特征：（1）足够灵活，能够支持多种策略和协议，允许它们同时执行。（2）保持模块化，安全协议的实现和维护独立于群通信系统。（3）允许群应用选择所使用的安全服务和协议，并提供简单的接口。（4）能够在不影响通信性能的前提下高效地实施安全策略。（5）支持动态安全策略。控制用户访问的措施主要有认证和授权两种。认证用于验证用户所宣称的身份，在本文中是指确定是否允许该用户使用某群通信系统。授权用于对被认证的用户授予使用系统资源的权限，其中系统资源在本文中是指负责用户试图执行的任何与群通信相关的动作：包括加入群、向另一个用户发送一条消息以及向群多播一条消息。由此可见，群通信系统中的访问控制机制是对群成员关系进行控制，如果没有这些机制，其他安全服务（包括密钥协商和数据完整性/保密性）都不会真正发挥作用。该框架支持动态策略的最大的挑战是允许在执行过程中修改策略。既然该框架本身并不知道实际所执行策略的内容，因此访问控制模块能够在不影响通信服务的情况下改变实施决策的方式。为了保证群中成员同步改变策略，可以通过使用同步时钟或群通信服务来协商更改策略的时间。下面，我们首先分析Spread系统的体系结构，然后研究如何在Spread上实现满足上述要求的通用安全框架。8.2Spread系统的通用安全框架8.2.1Spread的体系结构Spread是一种既适用于局域网又适用于广域网的群通信系统，是第一个能够在广域网中完全支持强语义的系统。Spread提供了可靠的、顺序的（先进先出、因果序和全序）消息传输和成员关系服务。Spread提供了三种语义：虚拟同步（VirtualSynchrony）、扩展的虚拟同步（ExtendedVirtualSynchrony）和视同步（ViewSynchrony）。Spread采用客户端-后台程序（Client-Daemon）结构，整个系统由一个或多个后台程序（服务器）和一个用于与客户端（应用程序）连接的函数库组成。后台程序通过Spread协议相互通信，构建了一个虚拟的覆盖网络。该覆盖网络维护系统状态、提供可靠的顺序的多播通信和成员关系服务。函数库为面向消息的应用程序提供应用程序编程接口和基本服务。应用程序和函数库可以与后台程序运行在同一台机器上，通过IPC进行通信。它们也可以运行在不同的机器上，通过TCP/IP进行通信。-80- 申请上海交通大学博士学位论文群通信系统的通用安全框架与应用Spread在广域网上使用单播消息，在覆盖网络中的节点间进行路由，因此不需要象基于IP多播的通信系统那样在路由器上消耗大量资源。另外，路由是建立在覆盖网络而不是物理网络上的，因此比IP多播更容易建立优化的路由树。虽然使用客户端-后台程序结构会因为额外的上下文切换和进程间通信增加少量开销，但与网络延迟相比，这些开销是微不足道的。在Spread系统中，作为客户端的应用程序要加入群，必须首先与其通信域中的某个后台程序连接，然后由后台程序把相关成员关系消息通过其它后台程序通知给其它应用程序。应用程序在群中发送消息时的过程类似，也是通过后台程序转发的。因此，为了保证应用程序之间的安全，应该将系统的安全机制分为三个层次，如图8-1所示。第一层是客户端和后台程序间的安全机制。当客户端要连接到后台程序时，后台程序要对客户端的身份进行认证，检查它能否使用群通信服务。第二层是后台程序间的安全通信，由于后台程序是相互信任的，因此该层主要是保证通信的保密性和完整性，这可以通过加密和签名等措施来实现。第三层则是在前两层的基础上实现客户端之间的安全通信，主要是对客户端的访问权限进行控制，即客户端能否加入某个群和在群内发送消息。上述三层机制能够实现客户端-后台程序-后台程序-客户端之间的安全通信。在文献[121]中，所有的访问控制（包括认证和授权）都是通过客户端与后台程序的交互来完成的，是通过ACL实现的一种静态的群访问控制机制。这种方式不但会引起单点故障问题，而且静态的访问控制机制很难适应动态变化的群应用。从功能上看，这种机制相当于上述框架中的第一层。而对于群应用来说，第三层是至关重要的。为了在不修改底层Spread协议的基础上灵活的添加新的访问控制协议，必须把访问控制的实现与Spread协议分离。Spread不需要直接实现任何访问控制协议，而是允许应用程序注册一个协议句柄，以便在需要进行访问控制的时候调用。该句柄对TCP会话进行完全控制，可以通过任何方式与客户端交互，但只有在成功完成访问控制或确认访问控制已失败后才能返回。如果访问控制成功，Spread就完成本次服务（连接到后台程序），否则就中止服务，并向应用程序返回一条错误信息。要实现上述安全框架，需要对客户端函数库和后台程序进行修改，在其中加入访问控制模块的访问接口。而应用程序只需要实现访问控制模块的客户端和服务器端。下面分别详细描述第一层的身份认证机制和第三层的访问控制机制的实现方法，并说明了该安全框架的灵活性和可扩展性。-81- 申请上海交通大学博士学位论文群通信系统的通用安全框架与应用客户C-D安全机制D-D安全机制DaemonDaemon安全通信客户图8-1Spread体系结构Figure8-1ArchitectureofSpread8.2.2认证框架本文使用的认证框架借鉴了[121]中的方案。图8-2给出了认证模块的结构和身份认证的执行过程。客户端和服务器都需要实现相应的认证模块。对客户端来说，只需要在Spread客户端API中加入一个函数，用于应用程序设置要使用的认证方法，并把需要的数据传输给该协议。当应用程序要连接到后台程序时，就使用所设置的认证方法来确定是否允许建立连接。认证方法设置函数有三个参数：认证方法的名字、一个指向认证函数的函数指针和一个包含认证方法所需要数据的缓冲区（如：用户名和口令等）。应用程序所选择的认证方法将被用于该应用程序建立的所有连接。如果要改变认证方法，应用程序必须重新调用认证方法设置函数，此后建立的连接都使用新的认证方法。对于服务器端，认证模块需要实现身份认证过程，然后用添加认证方法函数（包含指向认证实现函数的指针）注册到Spread后台程序。缺省状态下，认证模块在注册时被置为禁止状态，管理员可以在Spread配置文件中启用需要的认证模块。认证过程如下：当后台程序接收到来自客户端的连接请求时，服务器就向客户端发送一个包含所有允许使用的认证方法的列表，客户端返回它希望使用的认证方法和相关的信息。选定了认证方法以后，后台程序就调用对应的认证实现函数。如果认证过程需要的时间较长，可以使用回调函数以防止后台程序因认证函数的运行而被阻塞。认证结-82- 申请上海交通大学博士学位论文群通信系统的通用安全框架与应用束后，认证模块把认证结果返回给后台程序，这时后台程序重新获得对该连接请求的控制权。如果认证成功，后台程序就继续完成该连接，否则，就断开连接。本框架允许同时使用多个认证协议，只有所有认证模块都通过身份认证才能成功建立连接。一般情况下，客户端会在服务器给出的认证方法列表中选择最简单的一种认证方法，而服务器则要求客户端必须经过足够严格的认证才能建立连接。为了解决这个问题，可以把认证方法分成必须执行的方法和可选的方法两类。客户端需要通过第一类认证方法和第二类中的任意一个认证方法才能建立连接。客户端服务器端客户端6.认证协议要求的交互信息服务器应用程序认证模块认证模块1.连接请求5.认证请求5'.认证请求2.客户基本信息Spread后台程序3.允许使用的认证方法7.认证结果SpreadAPI4.客户选择的认证方法图8-2认证框架Figure8-2ArchitectureofAuthentication在[121]中，当客户通过身份认证后，仍然由后台程序负责实现对其访问权限的控制。权限控制策略是在后台程序启动时设置的，在整个运行过程中保持改变，并应用于所有的群应用。由于后台程序只是提供可靠的通信服务，并不关心上层群应用的具体安全要求，因此由它设置的权限控制策略很难满足所有群的要求，更难满足动态对等群的策略变化。我们认为对群服务的访问应该由群成员来控制，而不应该由后台程序控制，并且要支持动态访问策略。下面详细介绍本文的访问控制框架。8.2.3访问控制框架成功连接到后台程序的客户可以使用的群服务包括：加入群、向另一个成员发送消息以及向整个群发送消息。其中，加入群会引起成员关系变化，而发送消息不会引起成员关系变化。对前一类服务的控制（加入控制）是保护群安全的第一道防线，对群的正常工作影响较大，而对后一类服务的控制（权限控制）只是在客户成为合法群成员后对其行为的限制。每个动态对等群在选择成员时都有不同的策略，这应该由群中现有的成员共同确定，而不能使用与身份认证类似的框架（见8.2.2节）。一旦客户被允许加入群，-83- 申请上海交通大学博士学位论文群通信系统的通用安全框架与应用那么它的访问权限也就应该确定了。成员在离开群以前可能会多次发送消息，很显然没有必要在每次发送消息时都由群中所有其它成员决定是否允许其发送。最简单的一种方法是由后台程序根据在新成员关系下群的访问控制策略对消息的发送进行有效控制。8.2.3.1加入控制框架[123]Kim根据决策人的身份对对等群的加入控制方法进行了分类，包括如下三类方法：（1）使用访问控制列表访问控制列表中包括了允许加入该群的成员的名字（或证书）。由于群成员关系是动态变化的，并且在很多情况下无法事先确定所有可能加入群的成员的名字，因此这种静态的控制方法的灵活性较差，很难适应动态群。（2）由固定的决策人负责控制决策人可以是外部的可信第三方（如：CA）或某个内部成员（如：群的组建者）。使用可信第三方的方案实现比较简单安全，但会增加决策过程的执行时间，因此适用于采用异步通信的群。由内部成员负责决策的方案实现较复杂，而且容易引起单点故障或成为攻击目标。内部成员始终保持在线，比较适用于采用同步通信的群。但是，使用固定决策人的方法破坏了群的对等性。（3）由群成员共同作出决策新成员要加入群，必须得到群中一定数目（静态阈值）的成员的允许，或群中一定比例（动态阈值）的成员的允许。前一种方法中的成员数是固定不变的，对于群中成员的数目少于阈值的情况，需要采用特殊的处理策略。这种方案保持了群的对等性，但比前两种方案的实现复杂得多。因为Spread系统支持同步通信，而本文的研究重点是动态对等群，因此应着重考虑第三种方法。图8-3给出了加入控制模块的结构和执行过程。加入控制是在客户端（群成员）进行的，后台程序不直接参与决策，它只是等待接收当前所有成员关于接受成员关系变化的返回信息，然后更新成员关系。如果有成员反对成员更新，那么后台程序就会拒绝该加入申请。在图8-3中，除了当前群成员和新成员外，还有一个负责分发群成员关系证书的机构GAuth。群成员关系证书用于表明某个客户的群成员身份，形式上类似一个标准的公钥证书，包括分发时间、有效期、群的名字、群成员的公钥和访问权限，该公钥是成员在群中的唯一凭证。某个客户要证明自己的群成员身份，需要提供有效的群成员关系证书，还要证明它知道与证书中的公钥相对应的私钥（如：对一条消息进行签名）。GAuth既可以是与特定群相关的，也可以是独立于群的，即为多个群服务。既可以由群的组建者担当GAuth，也可以由群中所有成员-84- 申请上海交通大学博士学位论文群通信系统的通用安全框架与应用共同担当，另外由CA担当也是很自然的。如果由组建者担任GAuth，会引起单点故障或成为攻击点。如果GAuth对应全体群成员，那么成员关系证书是由它们共同签发的。这种方式不需要引入可信第三方，保持了群的对等性。由CA担当GAuth不但安全性较好，而且能够为多个群服务。由本文前面的研究可知，在密钥协商过程中成员身份信息的获得也要借助于CA（对于使用IBE的协议，则需要密钥生成中心KGC）。因此，如果由CA担当GAuth，只需要在其上增加分发群成员关系证书的功能就可以了，实现很简单。群GAuth4证书及所有赞成消息3.M1群成员关系证书.1M息2消...成赞2.息2消成.M赞.n2..m消息成2.赞1.加入请求Mnew图8-3加入控制过程Figure8-3ProcessofAdmissionControl在执行加入控制之前，每个群都应该确定其加入策略，即客户要加入该群的方法和步骤。我们认为由群的组建者制定加入规则比较合理。加入策略至少应该包含如下字段：群的名字、GAuth、加入控制方法（静态阈值或动态阈值）、加入策略的发布者、加入策略的签名。加入控制过程由如下步骤组成：（1）初始化：要加入群的客户Mnew从GAuth取得该群的加入策略。（2）提出加入请求：Mnew向群发出加入请求消息，该消息包括Mnew的公钥证书PKCnew和群的名字，并由Mnew签名。（3）加入决策：当前群成员收到加入请求后，抽取发送者的PKCnew，并验证其签名。如果该成员赞成Mnew加入群，就发送一个签名的赞成消息（签名）。Mnew收集并验证至少t（加入策略中规定的阈值）个赞成消息。群成员的决策过程可以使用多种不同的签名机制，如：普通数字签名、阈值数字签名-85- 申请上海交通大学博士学位论文群通信系统的通用安全框架与应用[124][125][126][127]、可追溯责任的子群签名（ASM）。这些签名机制各有优缺点，不同的群应用应该根据需要进行选择。（4）申请群成员关系证书：Mnew一旦收集到足够的赞成消息，就向GAuth发送一个签名的证书申请消息，该消息包括PKCnew、群的名字和收集到的赞成消息。（5）群成员关系证书的分发：GAuth验证接收到的请求消息是否真实、是否符合该群的加入策略。如果验证通过，GAuth就向分发群成员关系证书。得到群成员关系证书后，Mnew就是一个合法的群成员，它能够通过对一条消息（challenge）进行签名来证明其身份。8.2.3.2授权控制框架如前所述，新成员的访问权限在其加入群时就应该确定。对于对等群来说，新成员的访问权限由当前成员共同决定是比较合理的。事实上，这完全可以在加入控制过程中实现，即在第（3）步中加入权限决策。图8-4给出了完整的决策过程。决策开始是否允许加入No不允许加入Yes允许加入，但允许发送单播No允许发送多播No不能发送消息消息消息YesYes允许加入、发送单播和多允许加入和播消息发送多播消息决策结束图8-4权限决策过程Figure8-4ProcessofAuthorizationDecision-86- 申请上海交通大学博士学位论文群通信系统的通用安全框架与应用加入控制和权限决策都可以使用多种签名机制，具体方法应该体现在群的访问控制策略中。另外，在群成员关系证书中，还应该包括成员的访问权限（图8-4所示的三种可能的权限组合）。8.2.3.3动态访问控制策略一些群应用的高度动态性使得它们需要动态地改变访问控制策略，如：权限决策的方法和某个成员的访问权限等。修改策略的请求可以由群中任何成员提出，然后经过其它成员的协商批准（具体过程如图8-4）。如果修改请求被批准，新策略被发送到GAuth。对于成员访问权限的修改，还需要向相关成员分发新的群成员关系证书。成员加入群后，要发送消息必须利用后台程序提供的通信服务，因此由后台程序控制成员的访问很方便。后台程序必须知道每个成员的权限，这可以从相应的群成员关系证书中提取得到。因此，每个得到新证书的成员（新成员或改变权限的当前成员）都要把证书发送给后台程序。8.2.3.4访问控制与密钥协商的关系访问控制过程中分发给成员的群成员关系证书是与一个特定的群相关的，其中所包含的公钥只对该群有效，证书的有效期和公钥的长度都可以由具体的群应用来确定。而群密钥也是特定于群的，因此群成员关系证书完全可以用于群密钥协商。一旦成员离开群，其群成员关系证书就会被撤销，不能继续用于该成员的其它服务请求。群成员关系证书与群的生命周期保持一致，不但可以大大简化证书管理，而且使得不同群的信息完全隔离，有助于抵抗主动攻击，增强安全性。本文第3章到第6章所提出的群密钥协商方案中用于验证成员身份和计算群密钥的公钥都来自由可信第三方签名的标准公钥证书，其有效期是由可信第三方确定的，只要证书有效，客户可以使用该身份（证书）加入不同的群。由此可见，证书与群没有一一对应关系。证书的变化可能会影响到群的正常运行。另外，不同的群所共有的证书信息可能会被用于恶意攻击。总之，加入控制是群密钥协商的基础，协商后的群密钥可以用于消息加密和群签名等，访问控制则对加密消息的发送具有最终决定权。8.3群通信系统通用安全框架的应用随着市场经济的迅猛发展和Internet技术的广泛应用，很多企业都希望通过电子商务来优化企业价值链、提高生产力和效率、增加商业机会、加强客户关系以及提高自身-87- 申请上海交通大学博士学位论文群通信系统的通用安全框架与应用管理经营水平。作为电子商务的发展趋势，电子集市（E-marketplace）是集成了信息平台、服务平台和交易平台的全功能场所，创造了众多买卖商家聚集的在线交易空间，买卖双方不仅可以寻找到更多的贸易伙伴，增加更多的商业机会，还能够享受更多的方便和标准化的商务服务，获得一个良好的商务环境。电子集市不但要支持传统贸易中的一对一或一对多的交易模式，更重要的是要支持多对多的交易模式。从技术角度来讲，电子集市的通信平台必须支持相应的三种信息交流方式，即一对一、一对多和多对多。同时需要提供灵活的安全机制，包括：保证买卖双方的身份合法性、确保通信过程中数据的安全性、有效控制用户的访问权限。一个提供了完整安全服务的群通信系统完全能够满足上述要求，下面详细描述如何用本章第2节中的安全框架实现适用于电子集市的安全通信平台。8.3.1电子集市通信平台的认证机制电子集市作为一个开放通用的电子交易平台，其安全机制也必须具有通用性和可扩[128][129]展性。PluggableAuthenticationModule（PAM）就是一种可扩展的认证服务框架，为UNIX系统服务（如：login、ftp）提供认证。PAM把具体应用的实现与认证机制的实现分离，不但允许应用程序选择如何对用户进行认证，而且允许在不重新编译应用程序的情况下实现多种认证模块之间的动态切换。因此，我们把PAM作为电子集市通信平台的认证机制。图8-5给出了PAM的结构框架，说明了应用程序（如：login、telnetd、ftpd）、PAM库和认证模块之间的关系。当应用程序调用了PAMAPI，PAM就根据配置文件装载适当的认证模块，并把应用程序的请求转发到底层的认证模块，如：UNIX口令、Kerberos和S/Key，由它们完成具体的认证操作。然后，PAM把执行结果返回给应用程序。PAM可用于图8-2所示的Spread认证框架中，即把服务器认证模块将作为PAM系统的客户端，通过调用标准的PAM函数来请求认证，如图8-6所示。因为服务器认证模块要为所有到后台程序的连接请求提供认证服务，所以不能被阻塞。服务器认证模块可以派生另一个进程（服务器认证派生进程）负责完成认证协议。服务器认证派生进程用PAMAPI建立与PAM认证模块的连接，通过二者的交互来实现认证。当认证结束后，服务器认证模块会收到通知，然后通知后台程序认证过程完成，并把对连接的控制返还给后台程序。PAM中认证方法的改变对群应用程序不产生任何影响，因此可以把多种认证方法集成到应用程序中去，如：RSA、DCE、Kerberos、S/Key和基于智能卡的认证方法，从而满足电子集市应用对认证方法的多样性要求。-88- 申请上海交通大学博士学位论文群通信系统的通用安全框架与应用ftpdtelnetdlogin（应用程序）PAMAPI配置文件passwordKerberosS/Key（认证机制）图8-5PAM的体系结构Figure8-5ArchitectureofPAM服务器认证派生进程客户端服务器端客户端6.认证协议要求的交互信息服务器应用程序认证模块认证模块1.连接请求5.认证请求5'.认证请求2.客户基本信息Spread后台程序3.允许使用的认证方法7.认证结果SpreadAPI4.客户选择的认证方法6'.认证协议要求的交互信息PAM认证模块图8-6电子集市应用的认证框架Figure8-6ArchitectureofAuthenticationinE-marketplace-89- 申请上海交通大学博士学位论文群通信系统的通用安全框架与应用8.3.2电子集市通信平台的访问控制机制电子集市中的客户会组成若干有共同兴趣的小组（群），在小组中进行贸易协商。为了保护交易者的商业秘密，必须对客户能否进入特定小组以及在小组中可以进行的活动进行控制。而这种控制应该由参与交易的各方独立完成，不应该由提供基本通信服务的底层系统提供。由此可见，本章第2节中描述的访问控制框架符合电子集市的要求。该框架的核心是签名机制，即图8-3中的第2步。可以用于群协商的签名机制主要有三类：普通签名（plainsignatures）、阈值签名（thresholdsignatures）和可追溯责任的子群[127]签名（accountablesubgroupsignatures）。不同的签名机制在效率和安全性方面有所不同，适用于不同的群应用。下面分别介绍这些机制在访问控制框架中的使用方法和适用环境。常用的普通签名机制有RSA和DSA。在访问控制框架中使用普通签名是很简单的，赞成新客户加入群的当前成员对客户的加入请求进行签名。这种方式的最大优点在于当前群成员可以采用异步方式进行签名，应用程序可以根据情况逐渐收集赞成签名。最大的缺点是需要收集线性多个签名，才能向Gauth申请群成员关系证书。另外，单独验证每个签名会大大增加计算开销。（k,n）阈值密码机制是把一个秘密信息分成n部分，分发给每个成员一部分，至少有k个成员提供自己的部分信息才能恢复秘密信息。把这种密码机制用于产生签名就是阈值签名机制，如：阈值RSA和阈值DSA。当访问控制使用阈值签名时，可信第三方为每个当前群成员分发一个秘密份额，当有客户请求加入时，每个赞成加入的成员向该客户发送一个部分签名。新客户把这些签名发给Gauth，由Gauth计算出新成员的部分签名，并发送群成员关系证书。为了保持群的对等性，可以使用完全分布式的阈值签名机制。在初始阶段，可信第三方确定RSA模数n和秘密多项式f(x)，把f(i)发送给成员Mi（共k个成员）。当有客户请求加入群时，每个成员用其拉格朗日系数和秘密份额签名一个部分证书。新成员用这些信息就能计算出其成员关系证书和秘密份额。这种方式只需要在初始阶段使用可信第三方，并且Gauth是由群本身来担任的，因此能够很好地适应对等群中的访问控制要求。但是，证书的分发仍然是一种在线的多轮协议，并且无法追溯证书的分发者。常用的阈值签名机制有阈值RSA和阈值DSA。对阈值RSA来说，最大的缺点是无法验证新成员的秘密份额的正确性，另外，在初始阶段仍然需要可信第三方。阈值DSA可以在没有可信第三方的情况下协商出所需要的参数和多项式。当前成员发送给新客户的签名中除了包括秘密份额，还包括一个随机秘密值，这样就可以提供对新成员秘密份2额的验证。但是，在没有可信第三方的情况下产生一个随机秘密值需要O(n)轮通信。-90- 申请上海交通大学博士学位论文群通信系统的通用安全框架与应用可追溯责任的子群签名允许给定群的任意子群以一种高效的方式进行签名，并且能向任意验证者提供所有签名者的身份。验证签名只需要两次取模求幂和k次取模乘法，而阈值签名则需要t次验证。另外，ASM也不需要可信第三方的支持。阈值签名和ASM只产生一个签名，可以减小群成员关系证书中签名的长度。阈值签名机制产生的签名的长度是常数，与签名者的数目无关。虽然ASM签名因包含了签名者的身份标识而随着群的扩大而增大，但仍然比普通签名的长度短。特别是对于使用动态阈值的大型群，如果使用普通签名机制，则要产生线性多个（签名者的数目）签名。因此所产生的签名的长度取决于签名者的数目，导致群成员关系证书很大。另外，普通签名和ASM直接识别签名者的身份，阈值签名则无法实现签名者的可追溯性。使用普通签名的加入控制开销较小，但群成员关系证书较大。其它签名机制的群成员关系证书较短，但加入控制开销较大。至于选择哪种签名机制，取决于特定群的具体要求。普通签名机制适用于那些带宽不作为主要考虑因素的中小型群。对于大型群来说，阈值较大，带宽是一个重要问题，因此阈值签名和ASM能达到更好的效果。另一方面，对于计算资源比较匮乏的网络，阈值签名和ASM的计算开销较大，因此普通签名机制更适合。8.4小结本章讨论了Spread群通信系统通用安全框架的基本特点。其中，身份认证由后台程序调用认证模块来完成。访问控制分成加入控制和权限控制两部分，加入控制完全由当前群成员共同决定，一旦客户被允许加入群，还要确定其访问权限，后台程序则据此来控制新成员的访问。本章最后以电子集市中通信平台的安全实现为例，说明了该框架的应用。对多种可供选择的身份认证和用于加入控制的签名机制进行比较，从而说明了该框架的通用性、可扩展性和灵活性。-91- 申请上海交通大学博士学位论文总结和展望第9章总结和展望随着网络技术的飞速发展和Internet规模的爆炸性增长，在开放性网络环境下出现了各种各样的分布式群通信应用。这些应用服务在网络协议栈的许多层和现代计算的许多应用领域都十分常见。对于这些工作在缺乏安全的开放网络环境中群应用来说，通信的安全性是至关重要的。群密钥管理方案使得群通信中的参与各方能够得到一个共享密钥（群密钥），是所有其它安全服务的基础。安全高效的群密钥管理方案是设计安全群通信系统时最具有挑战性的一部分工作，因此对其的研究与实现具有重要的理论意义和实用价值，拥有广阔的应用前景。常见的群应用包括电视电话会议、数据库备份、分布式交互仿真和游戏等。它们的共同特点是成员数一般不超过100个，采用多对多的通信模式，且成员间关系是对等的，成员可以随时加入或离开群。这类群被称作动态对等群，目前国际上对此的研究工作还相对较少，本文重点研究动态对等群中的密钥管理方案。群密钥的建立协议可分为两类：基于某种可信第三方的（集中式）密钥分配协议和密钥协商协议。本文认为基于树的密钥协商协议是适合动态对等群的理想方案，但现有方案都在性能或安全性方面存在不足。基于减小开销和提供密钥认证两个方面，本文提出了三类（五种）新方案。1．本文第3章提出了一种高效的群密钥协商方案PTDH，把三叉树和超奇异椭圆曲线上的Pairing结合起来。该方案的通信开销随成员数目的增加而增长的幅度可忽略，计算开销则取决于密钥树的高度。由于三叉树的高度不大于具有相同数目叶节点的二叉树的高度，因此用PTDH的开销比使用二叉树的方案小。此外，三叉树是结构最简单的一种多叉树，节点的插入和删除操作都比较简单，因此很适合作为密钥协商的数据结构。此外，Pairing的引入使其以更短的密钥得到更强的安全性。2．本文第4章利用椭圆曲线上的Pairing在安全属性和灵活性方面的优势，提出了一种基于Pairing的两方可认证的密钥协商协议，然后利用不平衡二叉树把该协议扩展到群，得到一种在安全性和性能方面能满足动态对等群要求的方案。该方案通过引入群公钥证书并在群密钥中结合群和成员的长期密钥和临时密钥，提供了隐含密钥认证。而已有的可认证方案（AGKA和AGKA-G）只是在每一轮密钥协商过程中随机选出的两个成员之间的认证，而不是群内任意两个成员之间的直接认证，所以仍可能受到中间人攻击。另外，该方案的设计思想可以作为把可认证的两方Diffile-Hellman协议扩展到群环境的一种通用方法。-93- 申请上海交通大学博士学位论文总结和展望本文第5章利用上述方法对基于身份的两方密钥协商协议进行扩展，提出了一种基于身份的群密钥协商方案IAGKA。它避免了现有方案依赖数字签名来提供认证而引发的两个问题：每个成员需要从CA得到其它成员的证书，而证书的传输会浪费大量带宽；对PKI签名的验证需要大量计算。基于以上分析，本文第6章把三叉树引入到可认证的密钥协商协议中，提出了分别与PAGKA和IAGKA相对应的两种方案：基于Pairing与三叉树的可认证的群密钥协商方案TPAGKA和基于身份与三叉树的可认证的群密钥协商方案TIAGKA。这两种方案不但保持了基于三叉树的方案在性能方面的优势，而且提供了隐含密钥认证。3．本文第7章实现了PAGKA、IAGKA和AGDH三种方案，并与一种可靠的群通信系统Spread集成起来，构成了一个分层的安全群通信平台原型。我们在该平台上测试了这三种方案的加入协议和离开协议的性能，验证了这两种方案能够更好地适应动态对等群在性能方面的要求。此外，本文还进一步研究了适用于Spread系统的通用安全框架，在上述安全群通信平台上加入访问控制机制，包括身份认证、客户请求加入群时的加入控制以及加入群后的访问控制，并讨论了它们与密钥协商模块的关系。最后以电子集市为例，描述了该框架的应用，显示了其良好的灵活性和通用性。在现有工作的基础上，我们将在以下几个方面开展进一步的研究：（1）研究群协议的形式化证明方法，对所提出方案的安全性进行形式化证明。（2）实现本文提出的其它密钥协商方案，并集成到安全群通信平台原型中，然后通过Opnet进行广域网仿真实验。（3）实现Spread系统的通用安全框架，进而研究如何在该安全群通信平台上实现各种协作式群应用。-94- 申请上海交通大学博士学位论文参考文献参考文献[1]Y.Amir,Y.Kim,C.Nita-Rotaru,andG.Tsudik.OnthePerformanceofGroupKeyAgreementProtocols.Proceedingsofthe22thIEEEInternationalConferenceonDistributedComputingSystems,Vienna,Austria,July2-5,2002.[2]GiuseppeAteniese.SecureandEfficientGroupCommunicationinWideandLocalAreaNetworks:[dissertation].Italy:Univ.ofdiGenova,1999.[3]O.PereiraandJ.J.Quisquater.,‘ASecurityAnalysisoftheCliquesProtocolsSuites’,In14-thIEEEComputerSecurityFoundationsWorkshop.IEEEPress,2001.[4]BlakeWilsonS.andMenezesA.AuthenticatedDiffie-Hellmankeyagreementprotocols.InFifthAnnualWorkshoponSelectedAreasinCryptography(SAC’98)(1999),LectureNotesinComputerScience,SpringerVerlag,339–361.[5]C.Boyd.OnKeyAgreementandConferenceKeyAgreement.InACISP:InformationSecurityandPrivacy:AustralasianConference,294–302.Springer-Verlag,1997.[6]G.Ateniese,M.Steiner,andG.Tsudik.Newmulti-partyauthenticationservicesandkeyagreementprotocols.IEEEJSAC,May2000.[7]M.Steiner,G.Tsudik,andM.Waidner.Diffie-HellmanKeyDistributionExtendedtoGroupCommunication.In3rdACMConferenceonComputerandCommunicationsSecurity,March1996.[8]MichaelSteiner,GeneTsudik,andMichaelWaidner.CLIQUES:Anewapproachtogroupkeyagreement.Proceedingsofthe18thInternationalConferenceonDistributedComputingSystems(ICDCS'98),Amsterdam,May1998,380-387,IEEEComputerSocietyPress.[9]EmmanuelBresson,OlivierChevassut,DavidPointcheval,andJean-JacquesQuisquater.Provablyauthenticatedgroupdiffie-hellmankeyexchange.InEighthACMConferenceonComputerandCommunicationSecurity,255–264.ACM,November5–82001.[10]M.BurmesterandY.Desmedt.Asecureandefficientconferencekeydistributionsystem.AdvancesinCryptology-EUROCRYPT’94,LNCS,Springer,Berlin,950:275–286,1995.-95- 申请上海交通大学博士学位论文参考文献[11]Y.Kim.A.PerrigandG.Tsudik.Simpleandfault-tolerantkeyagreementfordynamiccollaborativegroups.Proceedingsofthe7thACMConferenceonComputerandCommunicationsSecurity(ACMCCS2000),November2000.[12]Y.Kim,A.Perrig,andG.Tsudik.Communication-efficientgroupkeyagreement.ProceedingsofIFIPSEC2001.June2001.[13]A.Perrig.Efficientcollaborativekeymanagementprotocolsforsecureautonomousgroupcommunication.InInternationalWorkshoponCryptographicTechniquesandE-Commerce(CrypTEC’99).July1999.[14]L.Dondeti,S.Mukherjee,andA.Samal.Disec:Adistributedframeworkforscalablesecuremany-to-manycommunication.ProceedingsofTheFifthIEEESymposiumonComputersandCommunications(ISCC2000),July2000.[15]W.DiffieandM.E.Hellman,MultiuserCryptographicTechniques,ProceedingsofAFIPSNationalComputerConference,1976,pp.109-112.[16]W.DiffieandM.E.Hellman,NewDirectionsinCryptography,IEEETransactionsonInformationTheory,v.IT-22,n.6,Nov1976,pp.644-654.[17]M.E.Hellman,TheMathematicsofPublic-KeyCryptography,ScientificAmerican,v.241,n.8,Aug1979,pp.146-157.[18]A.Shamir,AFastSignatureScheme,MITLaboratoryforComputerScience,TechnicalMemorandum,MIT/LCS/TM107,MassachusettsInstituteofTechnology,Jul1978.[19]R.L.Rivest,A.Shamir,andL.M.Adleman,AMethodforObtainingDigitalSignaturesandPublic-KeyCryptosystems,CommunicationsoftheACM,v.21,n.2,Feb1978,pp.120-126.[20]T.ElGamal,APublic-keyCryptosystemandaSignatureSchemeBasedonDiscreteLogarithms,AdvancesinCryptology:ProceedingsofCRYPTO84,SpringerVerlag,1985,pp.10-18.[21]T.ElGamal,APublic-keyCryptosystemandaSignatureSchemeBasedonDiscreteLogarithms,IEEETransactionsonInformationTheory,v.IT-31,N.4,1985,pp.469-472.[22]NationalInstituteofStandardsandTechnology,NISTFIPSPUB186,DigitalSignatureStandard,U.S.DepartmentofCommerce,May1994.-96- 申请上海交通大学博士学位论文参考文献[23]W.Diffie,TheFirstTenyearsofPublic-KeyCryptography,ProceedingsoftheIEEE,v.76,n.5,May1988,pp.560-577.[24]W.Diffie,TheFirstTenyearsofPublic-KeyCryptography,inContemporaryCryptology:TheScienceofInformationIntegrity,G.J.Simmons,ed.,IEEEPress,1992,pp.135-175.[25]N.P.Smart,AnIdentityBasedAuthenticatedKeyAgreementProtocolBasedontheWeilPairing.CryptologyePrintArchive,Report2001/111,2001.[26]A.Joux.AoneroundprotocolfortripartiteDiffie-Hellman.InAlgorithmicNumberTheorySymposium,ANTS-IV,Springer-VerlagLNCS1838,385-394,2000.[27]D.BonehandM.Franklin.“Identity-basedencryptionfromtheWeilpairing,”ProceedingsofCrypto'2001,LectureNotesinComputerScience,Vol.2139,Springer-Verlag,213-229,2001.[28]C.K.Wong,M.Gouda,andS.S.Lam.Securegroupcommunicationusingkeygraphs.InACMSIGGCOM.ACM,September1998.[29]JonathanR.Stanton.AUsersGuidetoSpreadVersion0.11.http://www.spread.org.October2002.[30]D.A.Agarwal,O.Chevassut,M.Thompson,andG.Tsudik.AnIntegratedSolutionforSecureGroupCommunicationinWide-AreaNetworks.Proceedingsof6thSymposiumonComputersandCommunications.IEEEPress,July2001.[31]Y.Amir,C.Danilov,andJ.Stanton,"Alowlatency,losstolerantarchitectureandprotocolforwideareagroupcommunication,"ProceedingsoftheInternationalConferenceonDependableSystemsandNetworks,June2000,327--336.Y.Amir,C.Danilov,andJ.Stanton.Alowlatency,losstolerantarchitectureandprotocolforwideareagroupcommunication.In30thIEEEFTCS,June2000.[32]L.Moser,P.Melliar-Smith,D.Agarwal,R.Budhia,andC.Lingley-Papadopoulos.Totem:Afault-tolerantmulticastgroupcommunicationsystem.CommunicationsoftheACM,April1996.[33]K.Berket,DeborahA.Agarwal,P.M.Melliar-Smith,andLouiseE.Moser,Overviewoftheintergroupprotocols,"inInternationalConferenceonComputationalScience(1),2001,316-325.-97- 申请上海交通大学博士学位论文参考文献[34]A.Fekete,N.Lynch,andA.Shvartsman.Specifyingandusingapartitionablegroupcommunicationservice.Proceedingsofthe16thannualACMSymposiumonPrinciplesofDistributedComputing.(SantaBarbara,CA),53–62,August1997.[35]J.Schultz.Partitionablevirtualsynchronyusingextendedvirtualsynchrony.Master’sthesis,DepartmentofComputerScience,JohnsHopkinsUniversity,January2001.[36]L.E.Moser,Y.Amir,P.M.Melliar-Smith,andD.A.Agarwal.ExtendedVirtualSynchrony.InIEEEICDS,56–65,June1994.[37]Y.Amir.ReplicationusingGroupCommunicationoveraPartitionedNetwork.PhDthesis,InstituteofComputerScience,TheHebrewUniversityofJerusalem,Jerusalem,Israel,1995.[38]Y.Amir,C.Nita-Rotaru,J.StantonandG.Tsudik.ScalingSecureGroupCommunicationSystems:BeyondPeer-to-Peer.TechnicalReportCNDS-2002-3.ComputerScienceDepartment,JohnsHopkinsUniversity.October,2002.[39]C.Nita-Rotaru.Thecostofaddingsecurityservicestogroupcommunication.TechnicalReportCNDS-2000-3,JohnsHopkins,ComputerScienceDept.(CNDS),2000.[40]H.HarneyandC.Muckenhirn.GroupKeyManagementProtocol(GKMP)Specification.RFC2093,July1997.[41]T.DuniganandC.Cao.GroupKeyManagement.Experimental,July1997.[42]R.Poovendran,S.Ahmed,S.Corson,andJ.Baras.AScalableExtensionofGroupKeyManagementProtocol.TechnicalReportTR98-14,InstituteforSystemsResearch,1998.[43]G.H.ChiouandW.T.Chen.SecureBroadcastUsingtheSecureLock.IEEETransactionsonSoftwareEngineering,15(8):929–934,August1989.[44]D.Wallner,E.Harder,andR.Agee.KeyManagementforMulticast:Issuesandarchitectures.RFC2627,June1999.[45]G.Caronni,M.Waldvogel,D.Sunand,andB.Plattner.EfficientSecurityforLargeandDynamicMulticastGroups.InWorkshoponEnablingTechnologies,(WETICE98).IEEECompSocietyPress,1998.[46]D.Wallner,E.Harder,andR.Agee.KeyManagementforMulticast:Issuesandarchitectures.RFC2627,June1999.-98- 申请上海交通大学博士学位论文参考文献[47]D.Balenson,D.McGrew,andA.Sherman.KeyManagementforLargeDynamicGroups:One-WayFunctionTreesandAmortizedInitialization.IETFInternetdraft(workinprogress),August2000.[48]H.Orman.TheOakleykeydeterminationprotocol,Version2.01997.INTERNET-DRAFT,workinprogress.[49]M.Waldvogel,G.Caronni,D.Sun,N.Weiler,andB.Plattner.TheVersaKeyFramework:VersatileGroupKeyManagement.IEEEJournalonSelectedAreasinCommunications(SpecialIssueonMiddleware),17(8):1614–1631,August1999.[50]I.Chang,R.Engel,D.Kandlur,D.Pendarakis,andD.Saha.KeyManagementforSecureInternetMulticastusingBooleanFunctionMinimizationTechniques.InIEEEINFOCOM,March1999.[51]I.Wegener.TheComplexityofBooleanFunctions.JohnWileyandSons,July1987.ISBN:0-471-91555-6.[52]M.J.Moyer,J.R.Rao,andP.Rohatgi.ASurveyofSecurityIssuesinMulticastCommunications.IEEENetworksMagazine,13(6):12–23,November/December1999.[53]W.DiffieandM.E.Hellman.NewDirectionsinCryptography.IEEETransactionsonInformationTheory,IT-22(6):644–654,November1976.[54]G.Ateniese,M.Steiner,andG.Tsudik.AuthenticatedGroupKeyAgreementandFriends.Proceedingsofthe5th(ACM)ConferenceonComputerandCommunicationsSecurity((CCS)-98),17–26,NewYork,1998.ACMPress.[55]C.BeckerandU.Wille.CommunicationComplexityofGroupKeyDistribution.In5thACMConferenceonComputerandCommunicationsSecurity,SanFrancisco,California,November1998,1-6.ACMPress.[56]C.Boyd.OnKeyAgreementandConferenceKeyAgreement.InACISP:InformationSecurityandPrivacy:AustralasianConference,294–302.Springer-Verlag,1997.[57]B.Schneier.AppliedCryptographySecondEdition:protocols,algorithms,andsourcecodeinC.JohnWileyandSons,1996.ISBN:7-111-07588-9.[58]C.G.Gunther.Anidentitybasedkeyexchangeprotocol,LectureNotesinComputerScience434,AdvancesinCryptology:Proc.Eurocrypt'89,Berlin:SpringerVerlag,(1990),29–37,1989.-99- 申请上海交通大学博士学位论文参考文献[59]徐秋亮，李大兴.椭圆曲线密码机制.计算机研究与发展，1999，11：1281~1288.[60]M,Robshaw,Y.Yin.EllipticCurveCryptosystems.AnRSALaboratoriesTechnicalNote.RevisedJune27,1997.[61]JosephSilverman,Thearithmeticofellipticcurves,Proceedings{IEEE}Infocomm'99vol.2,689-698,SpringerLectureNotesinMath.,1986[62]SattamS.Al-RiyamiandKennethG.Paterson.AuthenticatedThreePartyKeyAgreementProtocolsfromPairings.CryptologyePrintArchive,Report2002/035,2002.http://eprint.iacr.org.[63]A.J.Menezes,T.OkamotoandS.Vanstone.Reducingellipticcurvelogarithmstologarithmsinafinitefield.IEEETrans.Info.Th.,39,1639-1646,1993.[64]G.FreyandH.-G.Rück.Aremarkconcerningm-divisibilityandthediscretelogarithminthedivisorclassgroupofcurves,Math.Comp.,62,No.206(1994)865–874.[65]D.Boneh,BLynnandH.Shacham.ShortsignaturesfromtheWeilpairing.InAdvancesinCryptology–ASIACRYPT2001,Springer-VerlagLNCS2248,514-532,2001.[66]J.C.ChaandJ.H.Cheon.Anidentity-basedsignaturefromgapDiffie-Hellmangroups.CryptologyePrintArchive,Report2002/018,2002.http://eprint.iacr.org.[67]F.Hess.Exponentgroupsignatureschemesandefficientidentitybasedsignaturesschemesbasedonpairings.CryptologyePrintArchive,Report2002/012,2002.http://eprint.iacr.org.[68]K.G.Paterson.ID-basedsignaturesfrompairingsonellipticcurves.CryptologyePrintArchive,Report2002/004,2002.http://eprint.iacr.org.[69]R.Sakai,K.Ohgishi,andM.Kasahara.Cryptosystemsbasedonpairing.InThe2000SymposiumonCryptographyandInformationSecurity,Okinawa,Japan,January2000.[70]S.D.Galbraith,Supersingularcurvesincryptography,inC.Boyd(ed.),Asicrypt2001,Springer,LNCS2248,(2001)495–513.[71]A.Shamir.Identity-basedcryptosystemsandsignatureschemes.Proc.Crypto’84,47-53,1984.-100- 申请上海交通大学博士学位论文参考文献[72]Y.DesmedtandJ.Quisquater.Public-keysystemsbasedonthedifficultyoftampering.Proc.Crypto’86,111-117,1986.[73]D.Hühnlein,M.Jacobson,D.Weber.TowardsPracticalNon-interactivePublicKeyCryptosystemsUsingNon-maximalImaginaryQuadraticOrders.Proc.SAC2000,Springer-VerlagLNCS2012,275-287,2000.[74]U.MaurerandY.Yacobi.Non-interactivepublic-keycryptography.Proc.Eurocrypt’91.498-507,1991.[75]S.TsujiandT.Itoh.AnID-basedcryptosystembasedonthediscretelogarithmproblem.IEEEJournalonSelectedAreainCommunication,vol.7,no.4,467-473,1989.[76]H.Tanaka.Arealizationschemefortheidentity-basedcryptosystem.Proc.Crypto’87,341-349,1987.[77]LIMing,WANGYong,GUDawuandBAIYingcai.AuthenticatedGroupKeyAgreementfromtheTatePairings.Proceedingsoftheinternationalworkshopongridandcooperativecomputing(GCC2002),954-963,December2002.[78]L.Dondeti,S.Mukherjee,andA.Samal.ADualEncryptionProtocolforScalableSecureMulticasting.TechnicalReportUNL-CSE-1998-001,UniversityofNebraska-Lincoln,Lincoln,NE.,July1998[79]王海涛，郑少仁.移动Adhoc网络中的安全问题.中国数据通信，2002，8：65-68.[80]S.M.BellovinandM.Merritt.Encryptedkeyexchange:Password-basedprotocolssecureagainstdictionaryattacks.ProceedingsofIEEESecurityandPrivacy,72-84,1992.[81]S.M.BellovinandM.Merritt.Augmentedencryptedkeyexchange:Apassword-basedprotocolsecureagainstdictionaryattacksandpasswordfilecompromise.InACMSecurity(CCS’93),244-250.[82]L.Gong,T.M.A.Lomas,R.M.Needham,andJ.H.Saltzer.Protectingpoorlychosensecretsfromguessingattacks.IEEEJournalonSelectedAreasinCommunications,11(5):648-656,June1993.[83]L.Gong.Optimalauthenticationprotocolsresistanttopasswordguessingattacks.In8thIEEEComputerSecurityFoundationsWorkshop,24-29,1995.-101- 申请上海交通大学博士学位论文参考文献[84]M.Steiner,G.Tsudik,andM.Waidner.Refinementandextensionofencryptedkeyexchange.ACMOperatingSystemReview,29:22-30,1995.[85]D.Jablon.Strongpassword-onlyauthenticatedkeyexchange.ACMComputerCommunicationReview,ACMSIGCOMM,26(5):5-20,1996.[86]D.Jablon.ExtendedPasswordKeyExchangeProtocolsImmunetoDictionaryAttacks.Proc.ofWET-ICE'97,248-255.IEEEComputerSociety,June1997.[87]S.Lucks.Openkeyexchange:Howtodefeatdictionaryattackswithoutencryptingpublickeys.ProceedingsoftheWorkshoponSecurityProtocols,79-90,1997.[88]T.Wu.Thesecureremotepasswordprotocol.InNDSS’98,97-111.[89]S.Patel.Numbertheoreticattacksonsecurepasswordschemes.ProceedingsofIEEESecurityandPrivacy,236-247,1997.[90]P.MacKenzieandR.Swaminathan.Securenetworkauthenticationwithpasswordinformation.Manuscript.[91]M.Bellare,D.Pointcheval,andP.Rogaway.Authenticatedkeyexchangesecureagainstdictionaryattacks.InEUROCRYPT’2000:139-155.[92]OpensslProjectteam.“Openssl”,April2001.http://www.openssl.org/.[93]B.Schneier.Theblowfishencryptionalgorithm.Dr.Dobb’sJournal,38–40,April1994.[94]StanfordIBEsystem.April2002.http://crypto.standford.edu/ibe/.[95]GMP4.2.1.http://www.swox.com/gmp/[96]Y.Amir,D.Dolev,S.Kramer,andD.Malki.Transis:ACommunicationSub-SystemforHighAvailability.InFTCSconference,July1992.[97]G.Ateniese,D.Hasse,Y.Kim,andG.Tsudik.TheDesignofaGroupKeyAgreementAPI,TechnicalReportRZ3170(#93216),IBMResearhDivision,June1999.[98]Y.AmirandJ.Stanton.Thespreadwideareagroupcommunicationsystem.TRCNDS-98-4,DepartmentofComputerScience,1998.[99]A.Ballardie.ScalableMulticastKeyDistribution.RFC1949,May1996.[100]O.Babaoglu,R.Davoli,andA.Montresor.PartitionalbeGroupMembership:SpecificationandAlgorithms.TRUBLCS97-1,DepartmentofComputerScience,UniversityofBologna,January1997.-102-
