安全多对多通信的分布式组密钥管理模式

摘要

提供一个进行安全多对多通信的分组密钥管理系统(20)和方法。系统(20)使用一个二进制分配树结构(26)。二进制树(26)包含一个第一内部节点,第一内部节点具有一个第一分支和一个第二分支,这两个分支从属于上述第一内部节点。每个分支均包含一个第一成员(22,22a),第一成员被分配到一个对应的叶节点上。第一成员(22,22a)具有一个唯一二进制ID(24),上述唯一二进制ID与第一成员(22,22a)被分配到的对应叶节点相关。第一成员(22,22a)的一个第一私有密钥(28)可以加密被发送到其它成员(22,22a)的数据。第一成员(22,22a)与一个包括其它成员(22,22a)的密钥关联分组(33)相关。其它成员(22,22a)具有屏蔽密钥(30)。根据第一成员(22,22a)的第一私有密钥(28)导出的一个屏蔽密钥(30)被发送到密钥关联分组(33)。其中第一成员(22,22a)使用从密钥关联分组(33)接收的屏蔽密钥(30)和第一私有密钥(28)计算第一内部节点的一个非屏蔽密钥。非屏蔽密钥被用于加密数据在位于从属于第一内部节点的分支上的成员(22,22a)之间传送的数据。

说明书

相交申请的交叉参考

本专利申请对1999年7月6日提交的美国临时专利申请60/142,490号提出申请日优先权要求。

技术领域

本发明涉及安全通信。更具体地，本发明涉及在多个发送方和多个成员之间提供安全通信的系统。

背景技术

诸如互联网的网络上的安全多点传送被用于诸如股票行情发布，私人会议和分布式交互模拟的应用。某些这样的应用具有一个单独的发送方，这个发送方向大量用户发送保密数据，而其它应用具有大量彼此进行私人通信的用户。近来已经提出了若干个支持一个发送方和多个成员之间的分组通信的方案。一些在多个发送方和多个成员之间进行安全通信的解决方案受到公共故障的影响；它们使用某种形式的集中式分组控制。

多点传送是分组通信的一个可伸缩解决方案；多对多安全多点传送协议也必须是可伸缩的。分组访问控制，私有密钥分配和动态分组管理是安全分组通信协议的三个主要部分。目前大部分一对多安全多点传送协议均使用一个分组管理器这样的集中实体进行访问控制并分配私有密钥。当多点传送组成员关系是动态关系时，分组管理器还必须保证理想的传递保密性。这将保证成员不能解密在加入分组之前发送的保密数据和在离开分组之后发送的保密数据。分组管理器在一个成员加入或离开时改变适当的私有密钥并且将私有密钥分配给对应的成员。重新分配密钥过程必须是可伸缩的；密钥分配开销应当独立于多点传送组的规模。

虽然产生单独一个攻击和故障点，但使用集中实体进行分组控制对于一对多安全多点传送而言是自然而然的。然而在存在多个发送方的情况下，期望多点传送组仍然可以工作，只要有至少一个发送方正在工作。换言之，多对多安全多点传送需要对分组进行分散控制。访问控制，密钥分配和动态分组管理任务应当被授权给所有的发送方。期望在分组内的所有发送方中间平均分配访问控制职责和协议处理开销。

在现有文献中只有少量的安全多对多分组通信协议。然而文献中的所有这种协议均使用集中分组控制并且容易变成单攻击点和故障点。一个协议向第三方实体公开私有密钥，上述第三方实体协助完成密钥分配并且还使用一个集中″分组安全控制器″(GSC)进行分组管理。另一个协议建议在所有组成员中给予相等的信任度。先加入的成员产生密钥并且为后加入的成员分配密钥。虽然这个协议在原理上是可行的，但在成员进行合谋的情况下是脆弱的。可以让非常少的成员控制分组，从而允许非均匀地分配分组控制和密钥分配开销。期望通信协议的结构能够防止组成员之间的合谋。

任何安全分组通信协议均具有分组访问控制，私有密钥分配和动态分组管理三个主要部分。发送方负责控制对安全多点传送分组的访问。在成员可以加入分组之前必须对其进行验证。为了保护隐私，数据在被发送到分组之前被加密。发送方负责以安全和可伸缩的方式向成员分配数据加密密钥。最终，发送方负责保证理想的传递保密性。为了保证理想的传递保密性，发送方应当在一个主机加入或离开分组时改变私有密钥。这个重新分配密钥过程应当是安全和可伸缩的。

安全多对多协议的需求和期望特性如下所述。安全分组通信方案必须是可伸缩的。更具体地说，必须能够在分组内成员(或发送方)数量增加时调整密钥分配开销。所有发送方必须得到平等的信任并且在至少有一个发送方正在工作的情况下分组必须工作。期望向所有发送方分配访问控制和动态分组管理任务。这允许局部处理加入和离开，因而避免控制通信负载的大范围传送。分组管理任务的分配还避免性能瓶颈并且消除多点传送组中的单一攻击点。最终，协议应当能够有效避免或检测并且消除任何合谋成员或发送方。

发明内容

本发明提供了一个进行安全多对多通信的分组密钥管理系统和方法。系统使用一个二进制分配树结构。二进制树包含一个第一内部节点，第一内部节点具有一个第一分支和一个第二分支，这两个分支从属于上述第一内部节点。每个分支均包含一个第一成员，第一成员被分配到一个对应的叶节点上。第一成员具有一个唯一二进制ID，唯一二进制ID与第一成员被分配到的对应叶节点相关。第一成员的第一私有密钥可以对被发送到其它成员的数据进行加密。第一成员与一个由其它成员构成的密钥关联分组相关。其它成员具有屏蔽密钥。根据第一成员的第一私有密钥导出的屏蔽密钥被发送到密钥关联分组。其中，第一成员使用从密钥关联分组接收的屏蔽密钥和第一私有密钥计算第一内部节点的非屏蔽密钥。非屏蔽密钥被用于加密在成员之间传送的数据，上述成员位于从属于第一内部节点的分支上。

附图说明

为了更完整地理解本发明，其目标和优点，参照下面的说明书和附图。

图1是图解一个通信系统的图例，这个通信系统在一个通信分组的成员中间进行多对多通信；

图2是关于一个密钥分配树的图例，其中根据本发明实施例的原理排列上述密钥分配树；

图3是关于一个加入通信系统的成员的图例，其中根据本发明实施例的原理排列上述成员；

图4是关于一个离开通信系统的成员的图例，其中根据本发明实施例的原理排列上述成员；

图5是示出确定一个密钥关联分组的成员的过程的序列图；

图6是示出一个数据加密过程的序列图；

图7是示出一个加入通信系统过程的序列图；

图8是示出一个离开通信系统过程的序列图；和

图9是图解一个通信系统的图例，这个通信系统在一个通信分组的成员中间进行少对多通信。

具体实施方式

参照图1，其中图解了一个支持基于本发明原理的多对多通信的可伸缩安全多点传送协议。本发明的实施例是一个使用基于分配树的密钥管理方案(DTKM)进行安全多对多分组通信的通信系统20。系统20是可伸缩的并且成员22被平等信任。系统20向成员平均分配分组控制职责和密钥分配任务。

每个成员22均被分配一个二进制ID并且这些ID被用来定义每个成员22的密钥关联。密钥关联分组22a中的成员相互联系以便报告成员资格改变并且交换密钥。成员22得到平等信任并且均可以是发送方。未来的成员可以和任何活跃成员联系以便加入分组。活跃成员验证新成员的证书并且为其分配一个唯一二进制ID 24。在不需要查找ID的全局空间的情况下在本地完成ID分配。ID分配过程说明了协议的分布式性质。新成员启动重新分配密钥过程。注意，重新分配密钥以保证理想的传递保密性。以类似于加入的方式处理离开；离开主机的邻居(根据ID确定邻居)需要注意离开并且启动重新分配密钥过程。密钥关联有助于在分组的所有成员中间平均分配密钥分配开销。

用二进制密钥分配树26的叶表示成员。各个成员22为自身产生一个唯一私有密钥28并且根据一个关于其两个子节点的私有密钥的函数计算各个内部节点密钥。所有私有密钥28均与其屏蔽密钥30相关，其中使用一个单向函数32计算屏蔽密钥。各个成员22保存连通到根的节点的所有非屏蔽密钥和上述节点的兄弟节点的所有屏蔽密钥。涉及根密钥计算的唯一私有密钥成分为各个成员22提供对分组的部分控制。加入/离开只需要改变加入/离开主机的与根连通的密钥。因而，各个成员资格改变只需要O(log n)个消息，其中n是分组中成员的数量。因而协议是可伸缩的。

通过一个密钥分配树的叶节点表示多点传送组的成员。密钥分配树是严格二进制的，即各个内部节点有且仅有两个子节点。各个成员产生一个唯一私有密钥28，这个唯一私有密钥是在产生包含根密钥的内部节点密钥时由成员产生的成分。内部节点与私有密钥相关并且根据一个关于其子节点的密钥的函数计算这些密钥。以类似方式计算根密钥并且使用根密钥进行数据加密。对于各个私有密钥k，存在一个屏蔽密钥k′和一个非屏蔽密钥密钥。使用一个针对私有密钥的指定单向函数计算屏蔽密钥。在指定一个通过单向函数计算的屏蔽密钥的情况下，不可能计算出屏蔽密钥的对等非屏蔽密钥。各个成员22知道与树根连通的节点的所有密钥和上述节点的兄弟节点的所有屏蔽密钥，但不已知其它的屏蔽密钥或非屏蔽密钥。由作为那些密钥的所有者和授权分配者的成员分配屏蔽密钥。各个成员22使用其接收的屏蔽密钥及其自身的私有密钥28计算树中与根连通的内部节点的非屏蔽密钥和自身的根密钥。一个混合函数34被用来根据节点的子节点的屏蔽密钥计算内部节点密钥。

各个节点被分配一个二进制ID 24并且负责产生一个私有密钥28。与节点相关的成员22还计算其密钥28的屏蔽密钥30并且与密钥分配树26中其直接相邻节点共享屏蔽密钥30。列表I提供了一个发现相邻节点算法的伪码，上述算法得到节点A的二进制ID并且返回A的相邻节点的二进制ID。

                              Table I.

发现相邻节点模块

Find_Neighbor(X＝b_hb_h-1...b₁)，X是一个二进制ID，其中当1＝＜i＜＝h时，b_i是一个二进制数字

begin

X′＝b_hb_h-1...b₁，

if(leaf_node(X′)＝″true″)

      return X′；

elso if(internal_node(X′)＝＝″true″)

      do

           X′＝X′0；

      while(leaf_node(X′)＝＝″false″)；

      return X′

end

注意：

1.如果X是密钥分配树的一个叶节点则leaf_node(X)返回true；否则返回false。

2.如果X是密钥分配树的一个内部节点则internal_node(X)返回true；否则返回false。

参照图2，在执行发现相邻节点算法之后；H(1110)的相邻节点是I(1111)，并且G(110)的相邻节点是H(1110)。具有相同长度的ID 24的相邻节点(图1中H和I)被称作直接相邻节点并且它们彼此交换其私有密钥28的屏蔽密钥30。如果一对相邻节点具有不同的ID长度(图1中的G和H)，ID长度较小的成员发送其私有密钥28的屏蔽密钥30并且从ID长度较大的成员接收具有相同ID长度的对应内部节点的屏蔽密钥30(G从H接收k′₁₁₁)。在使用接收的新密钥的情况下，成员22计算其父节点的私有密钥28。一个混合函数(通常是一个XOR函数)34被用来计算内部节点密钥。例如在图2中，C和D针对屏蔽密钥k′₀₁₀而k′₀₁₁使用混合函数m，34计算内部节点密钥k₀₁。

在系统20中一个密钥关联分组22a的成员之间交换屏蔽密钥30。密钥关联被用来在所有分组成员22中间平均分配密钥分配任务。各个成员22需要与其ID 24的长度一样多的屏蔽密钥30来计算根密钥。由其密钥关联分组22a的不同成员提供各个屏蔽密钥30。对于一个成员的ID中的各个位，存在一个提供对应屏蔽密钥的成员22。下面的发现密钥关联模块33返回其提供的、对应于一个成员ID中一个指定位的成员22 ID 24和私有密钥28。

                               Table II

发现密钥关联分组模块

Find_Key_Association(X＝b_hb_h-1...b₁，i)begin   Xi＝b_hb_h-1...b_i+1b_ib_i-1...b₂b₁；if(leaf_node(X_i)＝″true″)

return(X_i，k′_i)； $>>>k>i>>=>>k>>>b>h>>>b>>h>->1>>>·>·>·>>b>>i>+>1>>>ver>>b>->>i>>>>>s>$

else if(internal_node(X_i)＝″true″)

     do

         X_i＝X_i0；

     while(leaf_node(X_i)＝″false″)；

     return(X_i，k′_i)；

else

     do

        X_i＝right_shift(X_i，1))；

     while(leaf_node(X_i)＝″false″)；

     return(X_i，k′_i)；

end

注意：

1.如果X是密钥分配树的一个叶节点则leaf_node(X)返回true；否则返回false。

2.如果X是密钥分配树的一个内部节点则internal_node(X)返回true；否则返回false。

3.right_shift(X，i)以一个二进制ID X＝b_hb_h-1...b₂，b₁，和一个数值，i，作为其输入并且将X右移i次。输出将是b_hb_h-1...b_i+1。

参照图2和5，其中图解了用于H(1110)40的密钥关联模块33。在步骤60加载对应于一个节点的二进制ID 24。接着在步骤62补足位位置。这里，我们补足对应的位位置1，2，3，4，并且得到I(1111)42，1100，1010，0110。在步骤64，如果节点是一个叶节点，则在步骤70获得对应于密钥关联分组的成员的屏蔽密钥。否则。如果节点不是一个叶节点，则在步骤66确定节点是否一个内部节点。这里由于不存在具有最后三个ID的节点，我们在步骤66和68将其右移一个位位置以得到G(110)44，F(101)46，和D(011)48作为H的40密钥关联分组22a中的其余成员。最终在步骤70，I 42，G 44，F 46，和D 48分别向H 40提供密钥k′₁₁₁₁，k′₁₁₀，k′₁₀，k′₀。

参照图6，其中图解了C(010)50的根密钥计算过程。在步骤72，C50产生密钥k₀₁₀并且向D(011)48发送其屏蔽密钥k′₀₁₀(在步骤74和76使用指定单向函数32计算)。类似地，D 48发送k′₀₁₁到C 50。C和D接着可以通过对k′₀₁₀和k′₀₁₁使用指定的混合函数34分别计算k₀₁。接着C50在步骤78向A(000)52发送k′₀₁并且接收返回的k′₀₀。在密钥交换之后，A 52和C 50可以计算k₀。在这个步骤之后，C 50和G 44彼此交换k′₀和k′₁。在步骤80根据关于k′₀和k′₁的函数计算根密钥。在类似的步骤之后，多点传送组的各个成员22获得或计算出k′₀和k′₁并且接着计算根密钥。在传输之前使用接收方的公开密钥加密所有密钥。注意C 50只接收与根54连通的节点的兄弟节点的屏蔽密钥。在使用那些密钥的情况下，可以计算与根54连通的节点的非屏蔽密钥。C 50在步骤82使用已经计算出的根密钥对一个消息进行加密。C 50在步骤84将加密消息多点传送到通信系统20的成员22。

集合的邻居的定义

各个成员X，22还维护一个集合Nx的邻居，该集合包括与X相邻的所有成员。在我们的例子中，N_H包括G 44和I 42。各个成员22监视其集合中的相邻成员并且在一个相邻成员离开时启动ID更新和密钥更新过程。集合的相邻成员在加入或离开期间可以改变并且加入和离开协议向成员提供信息以便更新这些集合。在系统20中，当发生一次加入或离开之后，所有成员22在重新分配密钥期间识别出分组成员资格改变。各个成员22负责使用加入或离开主机的ID 24更新其集合相邻成员。

加入协议过程#1

一个未来成员可以在密钥分配树26的任何节点上加入。然而为了增强效率期望控制未来成员加入的节点以便保持密钥树的均衡。系统20通过在树中选择位于一个可管理或由时间期限(TTL)限定的范围内的成员22对树26进行本地平衡。可管理范围的一个例子包含将一个消息限制到一个可控制扩充范围上，例如一个5人LAN，一个部门LAN，一个分公司LAN，一个公司WAN。TTL限定范围的一个例子包含限制消息可以跨越的路由器转发段的数量。未来成员在多点传送组中位于限定范围内具有最小ID长度的本地成员上加入。不期望的候选方案需要一或多个实体保持有密钥分配树26的一个快照。例如，为了跟踪分组的所有成员22及其在密钥树26中的位置，或者向整个分组广播成员状态报告消息，或者向一个跟踪所有加入和离开的集中实体广播成员状态报告消息。第一候选产生过多的网络传输，而第二候选具有一个单点故障。

参照图3和7，J 56是一个在步骤86加入到C 50上的新成员。当验证J的证书时，C在步骤88分割其ID 010(图3中示出)，为自身保留0100，将0101分配给J 56。C 50a还改变其私有密钥28并且向J 56发送其新密钥的屏蔽密钥。J 56在步骤90，92和94产生一个其自身的私有密钥28并且向C 50a发送屏蔽密钥。注意J 56中所有对应于和根54连通的内部节点的密钥因加入而发生改变。J 56需要所有在图3中表示成黑色的节点的非屏蔽密钥和表示成灰色的节点的屏蔽密钥。注意，C 50a所知的屏蔽密钥没有发生改变，因而它可以在步骤96当接收到k′₁时计算所有对应于节点010，01和0的新密钥和根密钥。现在J 56需要对应于011，00和1的屏蔽密钥。通过使用较早提供的Find_Key_Association()模块33，它在步骤98确定具有ID011(D)，000(A)和110(G)的节点是其密钥关联分组的成员。注意这些节点及其相邻节点也需要J 56知道或可以计算的屏蔽密钥。具体地，J 56向D 48发送k′₀₁₀并且从D 48接收k′₀₁₁。它接着在步骤100计算k′₀₁，向A 50发送k′₀₁，并且接收返回的k′₀₁₁。A 50也需要本地多点传送被k00加密的k′₀₁，其中只能由A 50和B 58来解密。J 56现在可以在步骤102计算其发送到G 44的k′，接收返回的k′₁并且为自身计算根密钥。G 44多点传送用k1加密并且只被E 60，F 46，G 44，H 40，和I 42解密的k′₀。在进行上述密钥交换之后，所有授权成员会具有其计算新根密钥所需的密钥。总之，在一次加入期间会有O(logn)个单点传送消息和O(log n)个子分组多点传送消息。注意，由于多点传送消息只须被发送到多点传送组内部的选定子分组上，多点传送消息会被限制到一个TTL限定范围或可管理范围内。我们在下面的Join()模块62中概括加入过程。其中将新成员和一个现有成员的ID 24当作参数。在模块中，k′表示M发送到X的密钥。

                            Table III.

加入模块

Join(X，Y＝b_hb_h-1...b₁)/^*Y是现存在成员^*/

begin

    Y＝b_hb_h-1...b₁0；

    X＝b_hb_h-1...b₁0；

    k_x＝generate_new_key()；

    i＝1；

    while(i＝＜length(X))

    begin

        (M，k′)＝Find_Key_Association(X，i)；

        outgoing_key＝k′_{right_shift(x，i-1)}

        send_key_from_to(outgoing_key，X，M)；

        scoped_secure_multicast(outgoing_key，M，k)；

        send_key_from_to(k′，M，X)；

        i＝i+1；

        k_{right_shift(x，i-1)}＝m(outgoing_key，k′)；

    end

注意：

1.generate_new_key()返回一个新私有密钥。

2.right_shift(X，i)以一个二进制ID X＝b_hb_h-1...b₂，b₁，和一个数值，i，作为其输入并且将X右移i次。输出将是b_hb_h-1...b_i+1。

3.send_keys_from_to(key，X，Y)指示X向Y发送″key″。

4.scope_secure_multicast(key1，X，key2)指示X用key2加密key1并且本地多点传送key1。

5.length(X)返回二进制ID X中的位数。

6.m()是混合函数，其中

加入协议过程#2

在另一个加入多点传送组的过程中，一个新成员向其希望加入的多点传送组的成员发送一个限定范围多点传送消息。消息由新成员的认证信息以及其单点传送(例子：IP)地址构成。参照图3和7，C 50在步骤86应答J 56的加入请求。当验证J的证书时，C在步骤88分割其ID010(图1中示出)，为自身保留0100，将0101分配给J 56。接着，C 50改变其私有密钥并且将其新密钥的屏蔽密钥以及它知道的所有屏蔽密钥(图3中表示成灰色)发送到J 56。由于是J的相邻节点，它也在步骤104向J56发送其单点传送地址。J 56在步骤106产生一个其自身的私有密钥并且向C 50a发送(单点传送)屏蔽密钥。注意J 56中所有对应于和根54连通的内部节点(图3中表示成黑色)的密钥因加入而发生改变。注意C 50a和J56在步骤108可以通过k₀₁₀，k₀₁和k₀和根密钥计算所有的新密钥。内部节点011，00和1的子节点需要屏蔽密钥k′₀₁₀，k’₀₁，和k′₀。C 50a负责发送它们，C 50a在步骤110分别使用密钥k_011’k′₀₀，和k′₁对其加密并且通过多点传送发送加密密钥。注意：

^*C，J和D可以解密k′₀₁₀，

^*A，B，C，J和D可以解密k′₀₁，并且

^*A，B，...，和I可以检索k′ ₀。

所有上述密钥所有权均符合密钥分配规则，即所有成员均知道其与根54连通的非屏蔽密钥和与根54连通的节点的兄弟节点的屏蔽密钥。在进行上述密钥交换之后，所有授权成员会具有其计算新根密钥所需的密钥。总之，会有一个单独的单点传送消息，该消息包括O(log n)个密密钥。总之，会有一个单独的单点传送消息，该消息包括O(log n)个密钥和O(log n)个多点传送消息，其中每个多点传送消息包括一个密钥。注意，成员需要知道其集合中相邻的成员的单点传送地址。使用分组多点传送地址发送所有其它密钥。这个性质有利于协议的分布式性质。并且，我们的协议不需要成员将所有成员的ID保存到单点传送地址转换表中。

同步加入

可以通过若干种方式更新内部节点密钥。最简单的方式是每当其任意子节点密钥发生改变时便计算一个内部节点密钥。然而在有多个同时加入时简单方案不适用。具体地，树26的不同部分中的成员可以具有一个内部节点密钥的不同版本，从而使分组无法工作。所以期望有一个同步同时加入的方法。

同步同时加入的第一个方法，即一个版本维护方案需要维护所有内部节点密钥的版本号。如果一个成员通过多点传送接收相同密钥的两个版本，它使用混合(XOR)函数34混合两个密钥。如果接收到相同密钥的不止两个版本，则多次使用混合函数34以得到新密钥。由于XOR函数是联合类型的函数，所有成员会具有计算出的相同密钥。版本维护方案的一个缺点是各个密钥会涉及某些开销。

一个同步同时加入的候选方法需要总是使用混合函数34更新内部节点密钥。换言之，总是通过对旧密钥和接收或计算的新密钥使用混合函数34来获得新的内部节点密钥。第二方法在存储方面更加有效，而第一方法在计算内部节点密钥需要的处理时间较少。

B.离开协议

当一个成员22离开时，其相邻成员启动重新分配密钥过程。如果相邻成员是离开的成员的兄弟成员，则假定其父节点在密钥分配树中的位置。否则它通知离开成员的兄弟成员的后代改变其ID。在两种情况中，相邻成员改变其私有密钥28并且启动重新分配密钥过程。它向其密钥关联分组的成员发送新密钥，而这些成员负责向其子分组中的适当成员传播新密钥。在本章节的其它部分中，我们将描述ID更新过程和之后的重新分配密钥过程。

在步骤112中X是离开节点而Y(＝Neighbor(X))是其相邻节点。如果Y的ID长度与X相同，则Y将其ID右移一个位位置以得到其新ID。如果Y的ID长于X的ID，则X的兄弟及其后代按以下方式改变其ID。注意，X的兄弟的各个后代Z与X共享一个密钥。在步骤114，如果Z＝b_hb_h-1...b_i+1b_ib_i-1...b₂b₁，则离开之后Z的ID将是b_hb_h-1...b_i+1b_{i->...b2b1，其中i是Z的ID和X的ID的长度差值加1。在两个情况下，Y在步骤116产生新私有密钥并且启动重新分配密钥。在图4中，如果E离开，则F得到ID 10并且产生一个新私有密钥；如果G离开，则H和I分别得到ID 110，111并且H产生新私有密钥。}

在图4中，C 50离开多点传送组。J 56发现离开，将其ID从0101改变成010，并且为自身产生一个新私有密钥28。因此，J到根54的路径上的内部节点密钥发生改变并且J 56负责启动与其对等方，即本章节前面定义的011(D)，000(A)和110(G)的密钥交换。J 56向D 48发送屏蔽密钥k′₀₁₀。J 56和D 48现在可以计算k₀₁。J56接着向A 52发送k′₀₁，A 52负责与所有具有k₀₀的成员共享k′₀₁。最终，J 56向G 44发送k′₀，而G 44依次向所有具有k₁的成员发送k′₀。注意在步骤118 J56不需要从D 48，A 52，或G 44返回任何密钥；在步骤120它已经具有计算根密钥所需的屏蔽密钥。虽然离开成员C 50也知道所有那些屏蔽密钥，但它不知道任何所需的非屏蔽密钥，因而不能计算或获得根密钥。一次离开产生O(log n)个多点传送消息，每个消息传送一个加密私有密钥。下面，我们概括了成员离开分组之后的重新分配密钥过程。

                          Table IV.

离开模块

Leave(X)

begin

Y＝Find_Neighbor(X)；

for each Z in{descendants(sibling(X))}U(Y)

Z＝delete_i^th_bit(Z，length(Z)-length(X)+1)；

ky＝generate_new_key()；

compute_internal_node_keys(Y)；

i＝1；

while(i＝＜length(Y))

begin

   (M，k′)＝Find_Key_Association(Y，i)；

   outgoing_key＝k′_{right_shift(Y，i-1)}；

                 right_shift(y，i-1)

send_key_from_to(outgoing_key，Y，M)；

scoped_secure_multicast(outgoing_key，M，k)；/^* M alreadyhas k^*/，

   i＝i+1；

  end

end

注意：

·descendants(X)返回多点传送组中是X的后代的成员

·如果X＝b_hb_h-1...b₂b₁，则sibling(X)＝b_hb_h-1...b₂ y₁

·delete_i^th_bit(X，i)以一个二进制ID和一个整数作为其输入并且返回删除了位位置i的X。例如如果X＝b_hb_h-1...b_i+1b_ib_i-1...b₂b₁，则函数返回b_hb_h-1...b_i+1b_i-1...b₂b₁。

·generate_new_key()返回一个新私有密钥。

·compute_internal_node_keys(Y)指示Y本地计算所有内部节点密钥及其屏蔽密钥。

·right_shift(X，i)以一个二进制ID X＝b_hb_h-1...b₂，b₁，和一个数值，i，作为其输入并且将X右移i次。输出将是b_hb_h-1...b_i+1。

·send_keys_from_to(key，X，Y)指示X向Y发送″key″。

·scope_secure_multicast(key1，X，key2)指示X用key2加密key1并且本地多点传送key1。

·length(X)返回二进制ID X中的位数。

·m()是混合函数。

安全数据通信

多点传送组中的所有成员可以用指定密钥计算根密钥。一个有数据要发送的成员使用根密钥加密数据并且通过传统多点传送通道(例如：MBONE)发送数据。其它成员可以在不进行任何其它的密钥交换的情况下解密数据。协议还允许进行安全子分组通信。一个发送方通过加密与子分组共享的密钥可以向一个成员子分组发送保密数据。

分组合并

可以有效合并根据本发明原理构造的独立通信系统以构成一个单独的多对多多点传送组。为了合并两个大小近似相等的分组，我们通过对现有根密钥使用混合函数34来计算一个新公共分组密钥。具有ID 1⁺(例子：1，11，111等等。)或ID 0⁺(例子：0，00，000等等。)的成员可以充当一个分组的缺省代表并且启动分组合并。如果一个分组层次高于其它分组，则层次较高的分组加入到层次较深的树的最高层次点上。这种分组加入类似于一个加入，具有ID 0⁺(或1⁺)的成员22改变其私有密钥并且启动重新分配密钥。

网络分区和分组离开操作

通过一个重复发现过程相邻成员可以注意到网络分区。例如，当一个成员相邻成员不发送心跳消息时，对应成员22可以假定相邻成员不可用，或者成员可以启动一个发现过程以确定子分组中有其它成员可用。子分组多点传送地址可以用于这个发现过程。

注意，密钥树中每个子树的成员可以使用其共有的内部节点的屏蔽密钥在其内部进行通信。因而在有网络的情况下所有连接子分组均可以在其内部进行通信。

平衡密钥树

为了有效进行私有密钥分配，密钥树应当是平衡的。使用智能加入算法防止形成非均衡树。加入协议需要未来成员在一个具有最小ID长度的现有发送方上加入。然而由于加入请求被发送到一个限定范围(本地)内的发送方，我们可以不具有一个全局平衡的树。并且一系列的离开可以产生一个非均衡树。通过强制执行一个分组离开和分组合并操作可以重新平衡树。在使用智能位置选择进行分组合并的情况下我们可以重构一个平衡树。

少对多安全分组通信

本发明的一个可选实施例提供了安全少对多分组通信。一类多点传送应用具有较小的成员集合，其中发送方发送数据和其它内容而接收方接收数据。所有发送方也是接收方。互联网上的面板讨论多点传送，部门经理讨论策略而其它雇员倾听的在线公司会议是少对多分组通信的例子。上述某些应用也需要适用的数据保密性。在设计一个信任模型时，由于发送方拥有数据，显然它们必须对多点传递分组拥有控制。在我们的范围内，控制包括分组访问控制，私有密钥分配等等。期望发送方具有相等控制，得到平等的信任，并且平等分摊协议处理开销。

子分组

参照图9，其中图解了一个基于本发明原理的少对多通信系统122。发送方属于一个发送方子分组124，上述子分组共享一个公共分组密钥(Root Key₀)并且使用本发明的原理。加入和离开期间的重新分配密钥与多对多通信实施例的重新分配密钥相同。接收方构成n个接收方子分组126；接收方子分组126的成员在其间共享一个公共分组密钥(RootKey_I，1＜I＜n)并且使用本发明的原理。通过使用对应的根密钥，各个子分组成员22可以与相同子分组的其它成员通信。

各个接收方子分组至少有一个发送方是图9所示的成员22b。换言之，某些发送方属于两个子分组，即发送方分组和一个接收方分组。属于一个接收方子分组的发送方22b负责对该子分组进行分组控制。然而注意，根据本发明的原理，分组管理开销被分布在接收方子分组的所有成员中间。

少对多分组构成

可以通过若干种不同方式构成少对多分组。例如，发送方首先构成发送方子分组124。某些发送方则可以在开始时接受接收方的成员资格请求并且构成接收方子分组126。我们的协议也允许某些接收方限制数据传输。当一个接收方希望发送数据时，它与控制其所属的子分组的发送方联系。如果发送方批准接收方的数据传输，它向少对多分组122的所有成员传递许可。

可选地，可以首先构成接收方子分组126并且接着由子分组的领导构成发送方子分组124以便启动少对多通信。公司会议是这种少对多分组的例子。例如如果ABC公司具有若干个部门M，N，...，Z，则各个部门首先构成接收方子分组126。各个分组的经理(领导)接着构成发送方子分组124并且启动少对多分组通信。

安全通信

各个发送方产生一个会话密钥并且向少对多分组发送经过会话密钥加密的数据。它接着向发送方子分组124传递经过Root Key₀加密的会话密钥。属于一个接收方子分组126的成员的各个发送方22b解密会话密钥，用接收方子分组密钥加密会话密钥并且传递会话密钥。在图9中，S1使用Root Key₀解密会话密钥并且使用Root Key₁加密会话密钥。使用随机产生的会话密钥进行数据传输保证接收方不能发送数据。

可选地，可以使用发送方子分组密钥Root Key₀进行数据传输。在那种情况下，多点传送路由器需要过滤接收方发送的所有数据。

虽然在当前最优实施例中描述了本发明，但可以理解的是，在不偏离如所附权利要求书提出的本发明的宗旨的前提下能够修改或调整本发明。