一种具有层次关系的公钥广播加密方法

摘要

本发明公开了一种具有层次关系的公钥广播加密方法，属于信息安全领域。本发明的方法为：1)根据信息系统的主体和客体按照访问控制关系建立一偏序层次有向图C；有向图的每类节点均包括一系列叶节点，每名用户归属于一叶节点；2)以偏序有向图C、安全参数ε和最大合谋人数t为输入，生成公钥集PK、私钥集SK；3)将公钥集PK中的公钥分别分配给有向图各节点，将私钥集SK中的私钥发送给相应的用户；4)发送者以公钥作为输入，对信息M进行加密，输出密文；5)接收者根据接收的私钥对密文进行解密，输出消息M。本发明大大提高了系统资源的访问控制能力、增强了信息系统的安全性，便于管理；同时对系统发出的信息始终保持加密，且提供对泄密者的追查功能。

说明书

技术领域

本发明涉及一种基于层次关系的密钥控制方法，特别涉及一种具有层次关系的公钥广播加密方法，属于信息安全领域。

背景技术

访问控制是信息安全防范和保护的主要核心策略，也是信息系统管理的核心内容，它的主要任务是保证各种资源不被非法使用和访问。访问控制规定了用户(主体)对信息资源(客体)访问的限制，并在身份识别的基础上，根据身份对提出资源访问的请求加以控制。它是对信息系统资源进行保护的重要措施，也是计算机系统最重要和最基础的安全机制。

目前常见的访问控制方法包括：自主访问控制(Discretionary Access Control)、强制访问控制(Mandatory Access Control)、基于角色的访问控制(Role Based Access Control)。上述访问控制来源于文件操作系统的管理，对于大范围网络访问控制以及日益严重的各类网络攻击而言，具有以下不足：

1、对于安全性较强的信息系统，传统访问控制方法采用“口令”式的身份认证与“查表”式的访问许可，安全性无法保证，安全措施容易攻破；

2、对于分布式网络信息系统，在信息资源分散情况下，访问控制管理复杂，安全性易受人为因素影响，容易出现人为管理漏洞；

3、对于信息资源的保护仅限制访问系统内，一旦信息资源脱离该系统，则没有任何防御措施阻止信息的泄露；

4、更为重要的是，无法实现对已泄露信息资源的追查，出现问题后无法从众多用户中确定泄露者身份，更无法提供确切的证据；

随着目前互联网上以P2P网络为代表的自组织、异构性资源共享服务的兴起，另一个目前较为主要的访问控制问题是：如何在自组织性较强的网络下实现资源的访问控制。由于这种网络中信息资源分散地存放在网络中，用户授权也不采用集中的方式，即主体管理和信息资源管理都是松散的，因此，这种环境下传统的访问控制方法很难奏效。

为了解决上述问题，本发明提出一种基于密码学的访问控制方法，并提供一种基于层次关系的密钥管理和公钥广播加密机制，提高系统的安全性能。

发明内容

本发明的目的在于提供一种具有层次关系的公钥广播加密方法。层次关系是对普遍存在的隶属关系的抽象，例如，在企业中，总经理、项目经理、员工三者构成一个简单的隶属关系；在安全系统中，通常也将安全级别划分为机密、绝密、秘密、公开等具有隶属关系的安全级别。在数学上，通常采用二元偏序关系≤表示某一集合上的这种隶属关系，具体定义如下：

对任意集合C，如果集合中任意两个元素c_i和c_j，能够使用c_j≤c_i表示c_j隶属于c_i，即元素c_i能够控制和管理c_j，并且，c_j能够访问c_i发来的数据，那么，我们称(C，≤)构成一个偏序层次关系。

根据代数格理论，偏序层次能够由一个有向图G＝(V，E)表示，并且，保留直接隶属关系作为边，去除间接隶属关系，则可得到一最小有向图。根据这一上述理论，可以将信息系统的主体和客体按照位置、权力、资源等的访问控制关系表示成上述偏序层次。在上述偏序层次构成的有向图包括：根节点，中间结点，如图1所示，每类节点均包括一系列叶节点，如图2所示，其中叶结点以三角形表示(即用户)。

本发明为实现上述偏序层次的访问控制，而引入了一种新的密钥管理办法，使得将成员访问授权变为对成员密钥的管理。因此，本发明对信息系统做如下规定：

·每名用户归属于某个叶结点，并具有一个独一无二的隐私解密密钥，即私钥；

·每个根节点和中间结点具有一个公开的加密密钥，即公钥；任何人根据其所掌握的公钥无法得到某个用户的私钥。

根据每名用户的隶属关系，他能够接受其父节点发来的信息，而无权解密其他节点发来的信息。通常，中间节点表示为信息系统中的组织或单位，它负责本单位内成员以及下属组织或单位的管理，而最上层的根节点表示整个信息系统，其所发送的信息被所有下属节点接受并解密。为了更好地表达本发明的特征，其提供的安全特征总结如下：

1、每名成员具有属于自己不同的解秘密钥，该密钥具有唯一性，能够表征身份；

2、每个组织能够独立的管理下属成员，并拥有公开密钥，用于下属成员和组织间的通信；

3、信息被加密和分发后，各成员得到相同的加密秘文，但只有授权成员能够解密该信息；

4、组织所拥有的公钥能够表征授权信息(或称许可证信息)，能够确定那些下属成员能够访问该公钥加密后的信息；

需要特别指出的是，中间结点所具有的密钥可以是独立分配的，也可以是通过根节点公开密钥计算得到的。特别是后一种情况，整个系统只需要一个根密钥，而无需为中间节点分配密钥，具有很大的灵活性和实用性。

基于以上分析，本发明提出了一种基于偏序层次的公钥广播方案，该方案包括5个子算法构成：

1)密钥生成(KeyGen)：以偏序有向图C，安全参数ε和最大合谋人数t为输入，输出为公钥集PK＝{pk₀，Pk₁，…，pk_i，…，pk_m}，私钥集SK＝{SK₀，SK₁，…，SK_i，…，SK_m}，以及SK₀＝{sk₀₁，…，sk_0m}和SK_i＝{sk_i1，…，sk_im}，其中将公钥集中的公钥分配给根节点C₀和中间节点C_i，将私钥集中的私钥发送给相应的用户，pk₀是用于根节点加密的主公钥，每个C_i持有一个公钥pk_i，每个用户具有一标识。

2)加密算法(Encrypt)：发送者以公钥pk_i作为输入，对信息M进行加密，输出密文O_i。

3)解密算法(Decrypt)：接收者以密文O_i和任意私钥sk_ij为输入对M进行解密，输出消息M。

4)撤销算法(Revoke)：令集合R是撤销标识集，它是一种以公钥集PK、撤销标识集R、消息M为输入，对消息进行加密的加密算法，输出为只能由剩余用户解密的密文O_i’。

5)跟踪算法(Trace)：令非法解密器D′是由t个解密私钥合谋而成，跟踪算法是一种以密钥集{PK，SK}为输入的Oracle算法，可以在安全参数ε的多项式时间内查获出中至少一个密钥。

上述跟踪算法也被称为k-resilient的广播加密方案。

本发明所提基于偏序层次的公钥广播方案，除了具有上述的偏序层次关系，还具有动态撤销和叛逆用户跟踪的功能。

为了解决大用户下的动态用户撤销，即无须改变系统和用户状态的情况下，实现对已有授权的组织和用户的权利撤销。为此，本发明提出了以下2种算法相结合的撤销方式：

1)中间节点密钥撤销：对整个中间节点的密钥进行撤销；

2)叶节点密钥撤销：对中间节点下的具体用户进行撤销。

通过对公钥密钥的裁减，能够实现对任意数目的隶属关系和用户的动态撤销，而无须改变用户标识和密钥。

为了实现对非法解密器的分析，本发明能够实现对提供密钥给该解密器的非法用户(叛逆者)的跟踪，并且该跟踪采用了黑盒方式，即不需要打开或分析非法解密器的情况下，能够发现非法用户。注意，这里包括非法用户的合谋。为此，本发明提出了以下2种算法相结合的跟踪方式：

1)节点跟踪：发现存在叛逆者的中间节点；

2)子集跟踪：从中间节点中发现具体叛逆者。

采用上述跟踪结束，能够实现对任意数目的叛逆者的有效发现。

纵上所述，本发明的技术方案为：

一种具有层次关系的公钥广播加密方法，其步骤为：

1)根据信息系统的主体和客体按照访问控制关系建立一偏序层次有向图C；所述偏序层次有向图C包括根节点和中间节点，每类节点均包括一系列叶节点，每名用户归属于一叶节点；

2)以偏序有向图C、安全参数ε和最大合谋人数t为输入，生成公钥集PK、私钥集SK；

3)将公钥集PK中的公钥分别分配给根节点C₀和中间节点C_i，将私钥集SK中的私钥发送给相应的用户；

4)发送者以公钥作为输入，对信息M进行加密，输出密文O_i；

5)接收者根据接收的私钥对密文O_i进行解密，输出消息M。

进一步的，所述公钥集为PK＝{pk₀，pk₁，…，pk_i，…，pk_m}，私钥集为SK＝{SK₀，SK₁，…，SK_i，…，SK_m}；其中，SK₀＝{sk₀₁，…，sk_0m}，SK_i＝{sk_i1，…，sk_im}，m为中间节点数目，pk₀为用于根节点加密的主公钥，pk_i为每个中间节点C_i持有一个公钥。

进一步的，所述方法通过随机选择一个整数作为偏序层次中根节点的主密钥，每一个中间节点C_i选择整数作为它的节点密钥，且把$T_i=g^{s_i}$分发给其他中间节点C_i，作为节点之间的偏序关系，然后每一个C_i都根据主公共密钥pk＝(g，z₀，(x₁，z₁)，...，(x_t，z_t)，{T_k}_k∈Λ(0))计算出本身的公钥${\mathrm{pk}}_i=(g,z_{i,0},{(x_k,z_{i,k})}_{k=1}^t,{\left\{T_k\right\}}_{k\in \Lambda \left(i\right)});$其中是G_q的一个生成元，G_q是素数阶q上的一个生成群，p是一素数且q|p-1，z₀＝g^ε，$z_i=g^{f\left(x_i\right)}\mathrm{mod}p,$z₀＝g^ε，$z_{i,k}=g^{f_k\left(x_i\right)}\mathrm{mod}p,$$f\left(x\right)=s_0+{\Sigma }_{i=1}^t{a}_i{x}^i$为一t次随机多项式，a_i为多项式系数，Λ(0)为控制域。

进一步的，所述方法中，接收者接收到一个由C_i节点发送的密文O_i之后，如果接收者所在节点附属于C_i节点，则接收者利用它的私钥对密文进行解密。

进一步的，所述方法中，发送者随机选择一数利用私钥pk_i对信息M进行加密，输出密文O_i；所述加密计算公式为：$O_i=(h,s_i,{(x_k,h_{i,k})}_{k=1}^t,{\left\{T_k^{\prime }\right\}}_{k\in \Lambda \left(i\right)}),$其中，h＝g^r表示对r的密码学承诺，h_i，k＝(z_i，k)^r表示对pk_i中z_i，k的随机化。

进一步的，所述方法中设置一撤销标识集R，对于撤销标识集R中的中间节点j，在控制域中去掉与节点j直接相关的偏序关系T′_j，如果存在几条通向该节点j的隶属关系，则把所有隶属关系对应的T′_j去掉。

进一步的，所述方法为每个用户设置一标识x_i；对于所述撤销标识集R中的用户，利用该用户的标识x_i取代加密计算公式$O_i=(h,s_i,{(x_k,h_{i,k})}_{k=1}^t,{\left\{T_k^{\prime }\right\}}_{k\in \Lambda \left(i\right)})$中的一个h_i，k。

进一步的，所述方法中，监测信息系统中是否存在非法解密器D′，所述非法解密器D′是由t个解密私钥合谋而成；如果发现非法解密器，则采用以密钥集{PK，SK}为输入的Oracle算法，查获出非法解密器中至少一个密钥，根据查获的密钥确定叛逆用户。

进一步的，所述查获出查获出非法解密器中至少一个密钥的方法为：

1)在控制域中，从根节点开始，依次去掉与中间节点j直接相关的偏序关系T′_j，如果存在几条通向该节点j的隶属关系，则把所有隶属关系对应的T′_j去掉；

2)将用撤销密钥加密的密文发送到中间节点的解密器，如果该密文被解密，说明叛逆用户不在此中间节点方向内；否则，则说明在此节点内，继续向下搜索，直至到达最终中间节点；

3)对于查获的存在叛逆用户的中间节点，将用撤销密钥加密的密文发送到每个中间节点中每个用户的解密器，如果该密文被解密，说明此用户不是叛逆用户，否则说明该密钥即为叛逆用户标识。

本发明的积极效果：

与现有技术相比，本发明的方法可以提高系统资源的访问控制能力、增强信息系统的安全性、便于管理；同时对系统发出的信息依然保持加密，且提供对泄密者的追查功能。

附图说明

图1(a)-(d)为各种偏序层次结构的图形化示意图；

图2本发明实施例中公钥广播方案所具有的偏序层次结构。

具体实施方式

为了叙述的方便，我们首先给出一些符号上的说明。记C＝{C_i}_i∈□是一些群(group)组成的偏序层次(hierarchy)，其中C₀为根节点。如果C_j是C_i的子节点(descendant)，即C_j＜C_i，那么我们利用Γ(i，j)＝{u∈C：C_j≤u＜C_i}表示从C_i到C_j的所有路径。如果C_i是根节点，可以把Γ(i，j)简写为Γ(j)。对于任意节点C_i，我们定义它的支配集(dominated set)为Λ(i)＝{u∈C：u＜C_i}。

设k是一个安全参数，t是最大合谋尺寸。令G_q是素数阶q上的一个生成群。我们所提出加密策略的安全程度依赖于群G_q中离散对数问题计算上的困难。更确切的说，安全程度是依赖于判决Diffe-Hellman问题的困难。可以将群G_q认为Z_p^*上的一个q阶子群，其中，p是一个大素数且q|p-1。

1)密钥生成：令是G_q的一个生成元。系统管理者随机选择一个整数作为偏序层次中根节点的主密钥。类似地，对于偏序有向图C中每一个节点C_i选择整数s_i作为它的节点密钥，但是他只把$T_i=g^{s_i}$分发给C_i，表示节点之间的偏序关系，而对s_i进行保密(即不发送s_i)，然后构造一个t次随机多项式$f\left(x\right)=s_0+{\Sigma }_{i=1}^t{a}_i{x}^i.$然后随机选择t个未使用的分享(x₁，f(x₁))，…，(x_t，f(x_t))生成一个主公共密钥：

pk＝(g，z₀，(x₁，z₁)，…，(x_t，x_t)，{T_k}_k∈Λ(0))(1.1)

其中z₀＝g^ε，$z_i=g^{f\left(x_i\right)}\mathrm{mod}p.$

管理者为每个用户生成一个新的标识x_i∈_R□_q，把x_i作为C_i的新的身份标识，每一个使用者C_i的私钥是sk_i＝(x_i，f_i(x_i))，其中f_i(x)＝∑_k∈Γ(i)s_k+f(x)。记${\stackrel{·}{T}}_i={\Pi }_{k\in \Gamma \left(i\right)}{T}_k,$每一个C_i都可以根据上面的公式(1.1)计算出它自己的公钥：

${\mathrm{pk}}_i=(g,z_{i,0},{(x_k,z_{i,k})}_{k=1}^t,{\left\{T_k\right\}}_{k\in \Lambda \left(i\right)})$

$=(g,z_0,{\stackrel{·}{T}}_i,{(x_k,z_k·{\stackrel{·}{T}}_i)}_{k=1}^t,{\left\{T_k\right\}}_{k\in \Lambda \left(i\right)})---\left(1.2\right)$

$=(g,g^{f_i\left(0\right)},{(x_k,g^{f_i\left(x_k\right)})}_{k=1}^t,{\left\{g^{s_k}\right\}}_{k\in \Lambda \left(i\right)})$

我们把{T_k}_k∈Λ(i)称作节点C_i的控制域。

2)加密算法：对于一个信息M，发送者随机选择一个数按照如下方法利用pk_i计算密文O_i：

$O_i=(h,s_i,{(x_k,h_{i,k})}_{k=1}^t,{\left\{T_k^{\prime }\right\}}_{k\in \Lambda \left(i\right)})---\left(1.3\right)$

$=(g^r,M·z_{i,0}^r,{(x_k,z_{i,k}^r)}_{k=1}^t,{\left\{T_k^r\right\}}_{k\in \Lambda \left(i\right)})$

其中，$s_i=M·z_{i,0}^r$对信息M的加密。

3)解密算法：接收者接收到一个由C_i节点发送的密文O_i之后，如果接收者所在节点附属于C_i节点，则接收者C_j利用它的私钥sk_i计算下面的等式：

$U_i\left(x_j\right)=\frac{h^{{\mathrm{sk}}_j·{\lambda }_0\left(z_j\right)}{\Pi }_{k=1}^t{h}_{1,k}^{{\lambda }_k\left(z_j\right)}}{{\left({\Pi }_{k\in \Gamma (i,j)}{T_k}^{\prime }\right)}^{{\lambda }_0\left(x_j\right)}}---\left(1.4\right)$

其中${\lambda }_k\left(x_j\right)={\Pi }_{0\le i\le t,i\ne k}\frac{x_i}{z_i-z_k},${x₀＝x_j，x₁，...，x_t}。继而它得到了明文

M＝S_i/U_i(x_j)。

4)撤销算法：

撤销算法分为2种情况：

a)中间节点密钥撤销：

以中间节点i的密钥撤销为例加以说明，如果需要撤销某一下属节点j，只需要在控制域Λ^*(i)中去掉与节点j对应的的T′_j，即去除此两节点间的偏序关系，如果存在几条通向该节点的隶属关系，则需要把所有隶属关系对应的T′_j去掉。由于随机数r在每次加密中都不相同，因此，节点j无法得到T′_j，因此无法完成解密。因此，中间节点的撤销数目不受任何限制。

b)叶节点密钥撤销：

叶结点的撤销需要获得该叶节点的标识x_l，并以该标识x_l取代$O_i=(h,s_i,{(x_k,h_{i,k})}_{k=1}^t,{\left\{T_k^{\prime }\right\}}_{k\in {\Lambda }^{*}\left(i\right)})$中的一个(x_k，h_i，k)，即令某个x_l＝x_i，并根据指数上范德蒙矩阵(vandermonde matrix)求逆得到h_i，l代替h_i，k，则该用户在解密中所使用的密钥已经在加密中出现，根据拉格朗日插值公式的性质，无法完成完成公式(4)，因此也无法实现解密。这种方法只能最多一次撤销t个人，但是对于大文件应用下，可以将文件分为几本部分，并分别不同的撤销密钥加密，并将明文进行叠交的方式进行加密，来实现大用户数的撤销。

5)跟踪算法：

如果发现了非法解密器(如广播系统中的置顶盒)，那么采用以下两种策略的组合进行叛逆用户的“黑盒跟踪”：

a)节点跟踪：首先针对中间节点采用中间节点密钥撤销的方式，从根节点开始进行跟踪：将用撤销密钥加密的密文发送到该解密器，如果该密文被解密，说明叛逆用户不在此中间节点方向内，否则，则说明在此节点内，则继续向下搜索，直至到达最终中间节点；

b)子集跟踪：对于已发现的中间节点，为确定该节点内某个具体叛逆者，可在该节点的下属用户集合内采用叶节点密钥撤销算法找到给用户：将用撤销密钥加密的密文发送到该解密器，如果该密文被解密，说明此用户不是叛逆用户，否则，则说明该密钥即为叛逆用户标识；

不难看出，多项式中系数扩展须满足层次要求。(1.4)的等式结果可以如下计算：

$U_i\left(x_j\right)=\frac{g^{f_j\left(x_j\right)·{\lambda }_0\left(z_j\right)·r}{\Pi }_{k=1}^t{g}^{f_i\left(x_k\right)·{\lambda }_k\left(z_j\right)·r}}{{\Pi }_{k\in \Gamma (i,j)}{g}^{s_k·{\lambda }_0\left(z_j\right)·r}}$

$=\frac{g^{f_j\left(x_j\right)·{\lambda }_0\left(z_j\right)·r}{\Pi }_{k=1}^t{g}^{f_i\left(x_k\right)·{\lambda }_k\left(z_j\right)·r}}{g^{{\Sigma }_{k\in \Gamma (i,j)}{s}_k·{\lambda }_0\left(z_j\right)·r}}$

$=g^{f_i\left(z_j\right)·{\lambda }_0\left(z_j\right)·r}{\Pi }_{k=1}^t{g}^{f_i\left(x_k\right)·{\lambda }_k\left(z_j\right)·r}$

$=g^{(s+{\Sigma }_{k\in \Gamma \left(i\right)}{s}_k)·r}$

$=g^{f_i\left(0\right)·r}$

$=z_{i,0}^r$

我们可以证明在DDH问题是难解决的情况下，这个算法在选择明文攻击下是语义安全的。