基于椭圆曲线密码的密文数据库密钥管理方案

王 超

(南阳理工学院，河南 南阳 473004)

0 引 言

数据库加密技术是最受广泛认可的数据库安全技术之一。数据库中的数据经加密后可以抵抗大多数的攻击，所以安全有效的数据库密钥管理方案能够提升数据库系统的效率与安全性。对于数据库加密技术的研究应考虑两个方面的问题：一方面应考虑加密层次、加密算法、加密粒度以及密钥管理等与加密技术自身相关的问题；另一方面也应考虑格、同态、数字水印、量子力学等与数据库加密配套技术可否与数据库加密技术较好地结合等问题[1-2]。其中，等级访问控制下的数据库加密技术可满足这一要求，通过将用户根据安全等级划分为不同的等级，并给各个用户分配与之对应的等级属性密钥，高级别的用户能够推导出低级别用户的密钥信息，但低级别用户无法推导出高级别用户密钥信息。研究安全高效的数据库加密技术已经成为热点问题[3-4]。文献[5]给出了一种基于动态密钥管理的访问控制方案，其主要思想是基于求解离散对数问题进行密钥推导。文献[6]给出了一种基于强制访问控制的密钥管理方案，其主要思想是每个用户都存储一个密钥，用于计算访问数据的密钥，密钥推导是基于Diffie-Hellman。上述两种方法虽然实现了数据库的安全新，但是未考虑数据库的等级权限访问问题，高级别用户无法直接访问低级别用户数据信息，需要获取低级别用户相关密钥信息才可以在密文数据库中访问低级别用户的数据信息，这两种方法对于数据库密钥的管理比较复杂且效率不高。文献[7]给出了一种基于基于大素数因式分解困难性问题的等级密钥管理方案，其主要思想是采用中国剩余定理和单向散列函数来管理秘密密钥，可以有效减少公共参数的存储空间。文献[8]给出了一种在等级访问控制下的动态密钥管理方案，其主要思想是采用椭圆曲线密码、AES与HASH进行混合加密。上述两种方法考虑了等级用户访问的问题，实现了高等级用户对低等级用户的访问，但是这两种方法的时间开销和存储开销较高，无法很好地满足密文数据库访问的效率需求。因此，为了进一步提高密文数据库密钥管理和访问的安全性和效率，给出一种基于椭圆曲线密码的密文数据库密钥管理方案(key management scheme of Encrypted Database based on Elliptic Curve Cryptography, EDECC)。所给EDECC方案中的用户通过独立选取用户密钥，然后安全传送到可信中心，可信中心根据用户密钥信息采用椭圆曲线密码计算具有偏序关系的用户关系参数，并考虑在偏序关系变化后的密文数据库更新方法。所给EDECC方案中的高级别用户能够根据计算得到的用户关系参数及用户密钥安全高效地推导出低级别用户的密钥信息，然后根据推导出的密钥信息即可解密低级别用户的密文数据库，从而能够获取密文数据库中所需的明文数据信息。方案性能分析表明，所给EDECC方案能够抵抗方向攻击、内部收集攻击、外部收集攻击、密文统计攻击等，且与其它经典密文数据库密钥管理方案相比所需时间开销和存储开销更低。因此，所给EDECC方案不仅能够很好地解决等级用户权限管理与密文数据库访问问题，而且也可以有效确保密文数据库的安全性并能提升密文数据库访问的效率。

1 密钥管理方案模型

令集合D={d1,d2,…,dn}表示数据库，其中di是安全性要求相同并能采用同一数据加密密钥的一类数据，可以是表、记录、字段、数据项。密钥集K={k1,k2,…,kn}，则明文数据库经加密后得到的密文数据库为C={c1,c2,…,cn}，其中ci=E(ki,di)。用户实体集合U={u1,u2,…,un}，其中用户实体ui与uj之间的安全等级关系可用偏序参数来描述。

定义1：假设存在L⊆U×U，且用户集合U非空。若L具有自反性、反对称性与传递性，那么L表示为U上的偏序关系，记为≤。例如，假设用户x和用户y之间存在偏序关系，那么可表示为x≤y。

定义2：假设存在一个有序二元组，其中V表示图的顶点集，E表示图的边集。如果在二元组中存在E⊆V×V，并且对于任意α、β和η，有eη=∈E，其中vα≠vβ，那么这个二元组为有向无环图，记为DAG。

定义3：假设在有向无环图中，对于任意i、j和k，有ek=∈E，且vi≤vj，那么称vj为vi的前驱节点，vi为vj的后驱节点。

下面图1给出了密文数据库密钥管理方案模型。图中的节点为用户实体，有向边为用户实体之间的偏序关系(Cji为偏序关系参数)，有向边两端连接的节点则为父节点与子节点(其中箭尾连接的节点为父节点，箭头连接的节点为子节点)。如果用户实体ui与uj之间存在偏序关系ui≤uj，则uj为父节点，ui为子节点，也即表示uj具有更高的等级权限，可以访问更多的数据库资源。每个等级的用户均会用自身的用户密钥加密数据库中的数据，高等级的用户有权限解密或访问低等级用户的数据。假设用户实体ui的密钥是uki，用户实体uj的密钥是ukj，且有偏序关系ui≤uj，则密钥ukj能推导出uki，反之一定不成立。

图1 密文数据库密钥管理方案模型

2 EDECC方案设计

所给EDECC密钥管理方案主要包括密钥构造、密钥推导和访问密文数据库三个阶段。下面给出EDECC密钥管理方案各阶段的具体步骤描述。

(1)密钥构造阶段

在密钥构造阶段，用户实体uj先自主选取其自身用户密钥ukj，同时把选取的用户密钥ukj安全传送到可信中心TC。可信中心TC在接收到所有用户实体的密钥参数后即可计算具有偏序关系的用户实体之间的关系参数。所给EDECC密钥管理方案的密钥构造过程具体描述如下所示：

Step1：可信中心TC在域GF(p)上选择椭圆曲线Ep(a,b)，并在椭圆曲线上Ep(a,b)选取基点G，其阶为n，p为大素数，同时公开Ep(a,b)、G与n；

Step2：用户实体uj在区间[1,n-1]上选择随机参数rj，然后计算参数Ψj=rj·G和Θj=H(ukj‖rj)，其中H为哈希函数，同时公开参数Ψj与Θj；

Step3：可信中心TC为用户实体uj选择一个随机整数dj，且有dj∈[1,n-1]，然后计算Zj=dj·G和skj=H(Zj‖Θj)，其中skj为用户实体访问密文数据库的密钥，也为等级用户实体之间的推导密钥，并把skj安全地传送给数据库服务器；

Step4：如果全部等级用户实体ui满足偏序关系ui≤uj，其中1≤i≤n，那么可信中心TC则计算用户实体之间的关系参数Cji=di·Ψj，可信中心TC创建并保存三元组。

(2)密钥推导阶段

在密钥推导阶段，只有高等级用户实体uj才具有权限推导出低等级用户实体ui的用户密钥。当用户实体uj和ui满足偏序关系ui≤uj，那么在密钥构造过程中则产生偏序关系参数Cji，用户实体uj可以利用Cji计算出用户实体ui的密钥信息ski。所给EDECC密钥管理方案的密钥推导过程具体描述如下所示：

Step1：如果用户实体uj想要获取与用户实体ui间的关系参数，可向TC发送查询请求，TC根据保存的三元组来判定两用户实体uj和ui之间是否存在偏序关系，如果uj和ui之间存在偏序关系，那么就向用户实体uj返回关系参数Cji；

所给ECECC方案中的用户实体与等级权限形成了有向无环图，可信中心TC可以根据有向无环图，为所有具有偏序关系的两个等级用户实体计算关系参数。高等级用户实体即可根据这个偏序关系参数推导出低等级用户的密钥，进而可以访问低等级用户实体的密文数据库。

(3)访问密文数据库阶段

在访问密文数据库阶段，密钥管理主要涉及两类密钥：第一类是系统主密钥，其主要作用是对工作密钥进行保护；第二类是工作密钥，其主要作用是对数据库中的数据进行加解密。高等级用户实体在获取低等级用户密钥信息后，即可获取系统主密钥，然后可以解密出工作密钥，通过工作密钥则可以解密数据库中的密文，即可获取所需的明文信息。所给ECECC方案下访问密文数据库的过程图如图2所示。

图2 EDECC方案下访问密文数据库

在图2中，TC为可信中心，用户实体u1对应的用户密钥为uk1，用户实体u2对应的用户密钥为uk2，Kmaster_1与Kmaster_2分别为系统主密钥，Kwork_1与Kwork_2分别为工作密钥，D1与D2分别为密文数据，C12表示用户实体u1与用户实体u2之间的关系参数。图中标识(Ⅰ)是u1对自身密文数据库进行访问的过程，图中标识(Ⅱ)是u1对u2的密文数据库进行访问的过程。〗所给EDECC方案中过程(Ⅰ)和(Ⅱ)的具体描述如下所示：

Step1：每个等级的用户实体均有各自的密文数据库，均可以加解密数据。用户实体u1在密文构造过程中会生成密钥sk1，同时将该密钥发送到数据库管理系统，在数据库加密完成后，则可用sk1加密系统主密钥，而系统主密钥在加密之后则存储在单独的硬件安全模块中进行保护。即有sk1=H(Z1‖Θ1)和C=Esk1(Kmaster_1)，其中Z1=d1·G，Θ1=H(uk1‖r1)，d1是用户实体u1随机选取的参数，r1是可信中心TC随机选取的参数，且有d1,r1∈[1,n-1]。则当用户实体u1访问密文数据库时，需对系统主密钥进行解密，即有Kmaster_1=Dsk1(C)；

Step2：获取系统主密钥后，即可解密出工作密钥。其中，工作密钥以数据项密钥为例，由于考虑到加解密效率，则数据项以表(d_ID_τ,d_K_τ)的形式存储，d_ID表示数据项标识，d_K表示数据项密钥，ξ表示数据项的个数。数据库的每个数据项均有表密钥T_K，每个记录均有行参数Ri和列参数Fj，且有i∈[1,n]和j∈[1,m]。如果用户想要选取数据项dij，需先确定其行参数和列参数，再计算d_ID_τ=f1(Ri,Fj)和d_K_τ=fs(T_K,Ri,Fj)，其中τ∈[1,ξ]，f1表示数据项标识生成函数，f2表示数据项密钥生成函数。当用户采用(d_ID_τ,d_K_τ)对数据进行加密之后，使用Kmaster加密数据项密钥表。解密时首先应采用系统主密钥将数据项密钥表解密后，再根据需解密数据项的行参数Ri和列参数Fj计算数据项标识d_ID_τ=f1(Ri,Fj)，然后在已解密的数据项密钥表中查找对应的数据项密钥d_K_τ，并解密得到对应的数据项。

Step3：如果用户实体u1需访问u2的密文数据库，即高等级用户实体访问低等级用户实体的密文数据库。u1应先按照密钥推导阶段中的步骤推导出低等级用户实体u2的密钥sk2，再重复Step1和Step2即可访问用户实体u2的密文数据库。

3 EDECC方案动态管理

用户实体的状态主要包括修改用户密钥、增加/删除等级关系、增加新的等级用户与删除等级用户四种状态，由于在实际的密钥管理过程中用户实体的状态经常是不断变化的，而且这些状态变化通常会对密文数据库造成一定的影响，所以需要对密文数据库的密钥进行动态管理。下面针对上述每种状态变化对密文数据库的密钥管理进行具体分析。

(1) 修改用户密钥

(2) 增加/删除等级关系

在图1的密钥管理方案中，若是用户实体u1和用户实体u5之间存在偏序关系，即如果用户实体u5成为用户实体u1的后驱节点，则可信中心TC需计算C15=d5·Ψ1，其中d5是可信中心TC为用户实体u5选择的随机整数，Ψ1为u1已公开的参数，但u1与u5的密文数据库不发生变化。

若要删除用户实体之间的关系，TC只需直接删除用户实体之间的关系参数即可，并且被删除关系的用户实体的密文数据库同样不发生变化。

(3) 增加新的等级用户

如果需要增加新的等级用户，首先应判断新增等级用户与哪些用户实体具有从属关系，即先确定新增等级用户的前驱节点或后驱节点，然后根据从属关系计算新增等级用户与其从属用户实体之间的关系参数，且密文数据库同样不发生变化。

(4) 删除等级用户

图3给出删除等级用户的过程，当用户实体u3被删除之后，则与u3相关联的全部等级关系也均会被删除，同时u3的密文数据库会产生相应变化。则删除等级用户过程的具体描述如下所示：

图3 EDECC方案等级用户删除

Step1：用户实体u3首先采用密钥sk3将其密文数据库的系统主密钥解密，然后采用其前驱节点的密钥sk1将用户实体u3的密文数据库加密，此时用户实体u3的密文数据库则交由用户实体u1管理；

Step2：判断被删除等级用户实体是否有后驱节点，如果被删除等级用户无后驱节点，则结束；如果被删除等级用户有后驱节点，则将其后驱节点与被删除等级用户的前驱节点建立等级关系。在图3中，被删除等级用户u3有后驱节点u6与u7，则需要分别建立u1与u6、u1与u7的等级关系，同时可信中心TC计算它们之间的关系参数C16与C17。

4 方案性能分析

4.1 安全性分析

(1) 反向攻击

反向攻击是指低等级用户实体ui想要推导出高等级用户实体uj的密钥skj，然后用获取的密钥解密密文数据库获取明文。如果攻击者想要对所给ECECC方案实施反向攻击，则需要求解椭圆曲线离散对数难题。根据已公布的Ep(a,b)、G与n，可计算2p，3p,…np，且有np=O。则反向攻击即是在椭圆曲线E上求解整数d使得T=dP，其中T和P为椭圆曲线上的点，且有1≤d≤n。

假设攻击者能推导出高等级用户实体uj的密钥skj，其中skj=H(Zj‖Θj)，Θj是公开的，则就相当于求解Zj，其中Zj=dj·G，G是公开的，则就相当于求解dj。这与椭圆曲线离散对数问题是矛盾的，因此用户实体ui无法推导出高等级用户实体uj的密钥skj，即所给EDECC方案可以抵抗反向攻击。

(2) 内部收集攻击

如果存在低等级用户实体ui拥有m个前驱节点uj,uj+1,…,uj+m-1，同时收集它们之间的m个关系参数Cji,C(j+1)i,…,C(j+m-1)i，如果攻击者想要推导出其中一个前驱节点的密钥skt，t∈[j,j+m-1]，则内部收集攻击指求解下列方程组：

①Zj=di·G；

②Cti=di·Ψt=di·rt·G；

③skj=H(Zj‖Θj)；

在反向攻击证明中可知式①无法推导出di，式②中对于任意t∈[j,j+m-1]无法推导出rt，则由式①和②可知无法推导出Zj，所以式③中无法推导出高等级用户实体的密钥skj，即所给EDECC方案可以抵抗内部收集攻击。

(3) 外部收集攻击

外部收集攻击是指假设在图1中攻击者从外部收集了关系参数C24、C25和C36，但是不知道它们前驱节点u2与u3的用户密钥与关系参数，那么攻击者则无法计算出用户实体u4、u5与u6的密钥。具体分析过程描述如下所示(以关系参数C25为例)：

①Ψ5=r5·G；

②Θ5=H(uk5‖r5)；

③C25=d5·Ψ2；

④sk5=H(Z5‖Θ5)；

由于式①无法推导出r5，则由式②无法推导出Θ5，而由式③无法推导出d5，式④中Z5是由可信中心TC秘密计算出来的，所以由式④无法推导出用户实体u5的密钥sk5。同理可知，攻击者也无法推导出用户实体u4与u6的密钥sk4与sk6。

(4) 密文统计攻击

攻击者如果利用密文统计分析攻击密文数据库，需首先从密文数据库中找出多个相同密文，然后与猜测密钥加密后的密文进行差分统计来判断猜测密钥是否准确。但是由于所给EDECC方案对不同用户数据采用不同密钥，得到加密的密文也不相同，所以攻击者无法在密文数据库中找到相同的密文，即所给方案可以抵抗密文统计统计。具体分析过程如下。所给EDECC方案的工作密钥由行参数Ri和列参数Fj生成，即d_k=ET_K(Ri)⊕ET_K(Fj)，则在n行m列的密文数据库中，第ρ行第τ列和第δ行第γ列的参数规则如下(ρ,δ∈[1,n]，τ,γ∈[1,m])：

由式①可以推导出下式②：

则可知：

③d_k_1≠d_k_2⟹Ed_k_1(d)≠Ed_k_2(d)；

根据式①、②和③可知，密文数据库中不同行列参数分块加密后也不相同，进而推导出由行列参数构成的工作密钥也不相同，最后加密获得的密文也不相同，所以密文数据库中不会出现相同的密文，攻击者也就无法实施密文统计攻击。

4.2 开销分析

下面分析所给EDECC方案的时间开销和存储开销，并与文献[9]方案和文献[10]方案进行比较分析。文献[9]方案和文献[10]方案均采用了椭圆曲线密码，但这两种方案的用户密钥不能自主选择，需由可信第三方来生成，而且文献[9]方案是采用AES加密算法来进行等级用户之间的密钥推导。而所给EDECC方案不仅能够自主选择用户密钥，而且能够实现动态密钥管理。

(1) 时间开销

表1 所给EDECC方案与其它方案的时间开销比较

(2) 存储开销

表2 所给EDECC方案与其它方案的存储开销比较

5 结 语

为安全高效地访问密文数据库，则文中给出了一种基于椭圆曲线密码的密文数据库密钥管理方案，通过等级用户中前驱节点与后驱节点之间的偏序关系参数，实现密钥构造与密钥推导，高等级用户能推导出低等级用户的用户密钥，根据所获取的低等级用户密钥能够解密出其密文数据库，最后即可获取所需的明文信息，同时能实现动态密钥管理。通过性能分析可知，所给EDECC方案不仅可以抵抗诸如反向攻击、内部收集攻击、外部收集攻击、密文统计攻击等，而且具有更小的时间开销和存储开销。因此，所给EDECC方案可以较好地实现等级用户权限管理以及等级体制下密文数据库的访问。