基于马尔科夫链的组密钥更新代价分析方法.doc

基于马尔科夫链的组密钥更新代价分析方法【 摘 要 】 组密钥管理机制大多基于树结构或星结构。在这两种结构中，成员的加入和离开均对密钥更新代价影响很大。提出基于连续时间马可夫链的代价更新分析方法，利用连续时间马可夫链来模拟成员动态变化，并对星结构和树结构的组播密钥管理方案进行更新代价仿真分析，并比较了两者的性能差异。仿真结果表明，组成员离开的概率和速率是影响星结构和树结构密钥管理方案在密钥更新代价上差异的主要因素。因此，在动态变化的环境下，应使用星结构和树结构相结合的组密钥管理机制。【 关键词 】 组密钥管理；更新代价；马尔科夫链【 abstract 】 tree-based and star-based key management schemes have being widely used in group key management. in this paper, we use continus-time markov chain (ctmc) to simulate the dynamic environment when group members join and leave. and we also analyze the updating cost of the tree-based and star-based structure. the analysis results show that the probability and velocity of members leaving dominate the relative performance between the two schemes. therefore, we propose to use an adaptive key management scheme according to star-based scheme and canonical-tree-based scheme.【 keywords 】 group key management; updating cost; markov chain1 引言组播技术是面向组的介于单播和广播通信之间的数据传输方式。它提供了一种一到多或多到多的数据通信模型，能够有效地节约网络带宽、降低网络负载。但由于组播体系结构的特点，它对安全性的要求也不同于单播和广播。组播的安全性可以通过密码学机制实现，而设计安全高效的密钥管理系统是当前安全组播研究的核心问题之一。文章从组密钥管理机制的代价分析入手，着重研究目前最为常用的两种组密钥管理机制的代价，即基于星型结构的组密钥管理机制的代价和基于树型结构的组密钥管理机制的代价。由于在所有的组密钥管理的代价中，密钥更新代价对整个组密钥管理代价影响最大4，因此文章重点分析因成员变化所引发的组密钥更新代价。对于成员的动态变化（成员加入或离开）所引发的组密钥更新代价，文章首先利连续时间马可夫链（ctmc）来构建成员动态管理模型，并在此基础上设计了基于ctmc组密钥代价更新分析方法。最后，将基于ctmc的组密代价更新分析方法进行仿真，并对仿真结果给出相关结论。2 组密钥管理机制目前的组密钥管理机制中，大多采用星结构和树结构两种方式。而对于组密钥管理来说，更新代价是对整个代价影响最大的，因此本文重点分析基于这2种结构的在组密钥管理的密钥更新代价。2.1 基于星结构的组密码管理机制在星结构中，假设组内有n个成员，密钥管理中心(key management center, kmc)管理n+1把密钥，其中1把组密钥（group key,gk），用来加密组间通信的内容，由kmc和组成员共同拥有，n把个人密钥(private key)(k1,kn)，是n个组成员个人拥有的，只有kmc和组成员掌握，在密钥更新的过程中使用。基于星结构的密钥管理机制如图1所示。2.2 树结构密钥管理机制在树结构密钥管理机制中，用根节点设置组密钥，叶节点设置组成员的个人密钥，剩下的节点为辅助节点(auxiliary node)，辅助节点随着叶节点的数量变化，用来设置辅助密钥(auxiliary key，ak)，辅助密钥为组密钥管理机制提供了延展性。树结构中，除了根节点和叶节点外，还有辅助节点，设置的是辅助密钥（akn）,为了给密钥管理机制提供延展性。每一位组成员，所拥有的是从自己所在叶节点往上到根节点的路径中经过的所有密钥。如图2所示，组成员总数n=8，对应的叶结点从k1到k8。树的分支度(degree)为4，深度(height)为2。其中分支度为根节点或辅助节点所能连接的最大下层节点数。在图2中，辅助节点2个，辅助密钥为ak1，ak2。3 基于ctmc模型的组密钥更新代价分析在ctmc模型中，没有限制系统所能服务的人数，系统的状态在任何一个时间点都有可能改变，对系统而言，成员加入的过程是由泊松分布所决定的，停留在系统中时间的长短是负指数分布所决定的。新成员进入系统的平均速率是?姿，停留在系统中的平均时间是1/?滋。新成员以速率?姿进入成员停留的时间为1/?滋。成员的状态转换如图3所示。每一个状态代表目前系统中组成员的数目，每个成员停留在系统中的时间是独立的，这是一个m/m/ 类型的ctmc模型，它是一种排队系统，对于组密钥管理系统来讲，新成员到达的过程是参数为?姿的泊松分布，每个管理员的服务时间服从参数为?滋的负指数分布。有足够多的管理员，系统能够服务的人员数也没有限制，对每一个新加入的成员，都有管理员即时为其服务，不会产生排队等待的现象。令nt表示t?莛0时刻，系统所处的状态，对组成员系统，表示正在系统中接受管理的成员数，或者正在进行管理的管理员数，nt可以取e=0,1,2,。nt ；t=0为一个状态可数的生灭过程，其参数为该系统有无限多个状态，达到稳定状态时,对于系统中的平均成员总数和平均离开或加入的成员数有下面的公式：以下仿真结果是依据第3节中的分析方法，并应用matlab软件模拟分析而来的。如图4和图5所示（a表示?姿，b表示?滋,保持?姿/?滋不变，使?姿从1变化到100，得出密钥更新代价的比较结果。），以?姿的值为x坐标，在图中用a表示，?姿从1到100变化。保持?姿/?滋的值不变，当?姿/?滋=10时，星结构性能好于树结构；当?姿/?滋=100时，由星结构性能不好变成树结构较优；当?姿/?滋=1000，10000时，树结构明显优于星结构。所以可以看出，当?姿固定， ?姿/?滋比值变大，?滋的值随之变小时，性能会由星结构比较好变成树结构比较好。ctmc模型中，当成员总数比较少时，适合用星结构，人数比较多时，适合用树结构。图6(a)中，a为?姿，b为?滋,令a从1到100，b从0.01到1，精度为0.01，分布图显示，在?滋取0.46到0.5之间有一条分界线，与dtmc模型类似，在这条线以上，是星结构性能比较好的区域，在这条线以下，是树结构比较好的区域。在ctmc中，平均离开的人数/平均组成员的大小为?滋(1-e?鄄?滋)，平均每回合组成员变动的比率只和组成员离开的速率?滋有关，因为?滋是成员离开的速率，这是因为如果当组成员变动的比率过大，设置辅助密钥将是多余的，星结构的性能比标准树结构要好。图6(b)是?滋的精度为0.002，取值从0.44到0.6的分布图，可以更清楚地看出，?滋=0.46以上是星结构比较好的区域。由以上分析可知，星结构和标准树结构的密钥更新代价只和成员离开的概率q或离开的速率?滋有关，当q0.17或?滋0.46时，应选用星结构的密钥管理机制；当q0.17或?滋0.46时，应选用标准的树结构的密钥管理机制。5 结束语以组密钥管理机制中的密钥更新代价为研究重点，采用ctmc模型，对树结构和星结构的密钥更新代价进行仿真分析，指出两者在不同情况下的性能表现，并找出影响它们性能表现的主要因素。研究结果对网络中的组密钥管理机制设计有一定的理论指导意义。参考文献1 deering s. host extensions for ip multicasting. ietf rfc 1112, 1989.2 quinn b, almeroth k. ip multicast applications: challenges and solutions. ietf rfc 3170, 2001.3 周福才,徐剑,徐海芳,刘泽超. ad hoc网络中基于双线性配对的str组密钥管理协议研究j.通信学报，2008，29(10):117-125.4 xu j, zhou f c, li x y, et al. hierarchical data processing model and complete tree ke