admin 为了解决数据库中加密字符串数据的查询问题，我们提出了为待加密的字段建立辅助索引字段的两阶段查询方法。索引字段的内容由原始数据的划分值和特征值两部分组成，它可以用采支持字符串数据的精确匹配查询和模糊匹配查询。查询加密数据时，首先利用索引字段对加密数据进行一次粗糙查询，然后在解密的数据上再进行一次精确查询。这就是今天我们要说的可支持快速查询的数据库的加密方法。
一、支持快速查询的数据库加密原理
它将字符串数据的划分值和特征值合并于同一个索引字段中。划分值用于支持字符串数据的精确匹配查询，而特征值用于支持字符串数据的模糊匹配查询。通过修改查询语句的转换函数，本文方法能够实现各种类型的查询请求，同时系统的性能也得到了提高。
二、系统的体系结构和控制流
我们提出的系统在应用程序和数据库管理系统之间增加了一个数据库文件加密和解密引擎，它的体系结构和控制流如图1所示：
在图1中，查询翻译器负责将用户的原始查询转换为对加密数据的查询，在转换的过程中它需要访问元数据；元数据是一些转换规则的集合，用于对查询语句进行修改，查询执行器负责对加密查询结果进行解密，并在解密的数据上再执行一次原始查询；最后查询执行器将精确查询结果返回给用户。
这种体系结构不需要对原有的应用程序和DBMS进行修改，因而它具有良好的适用性。
三、加密字符串数据的存储与查询
1、 加密字符串数据的存储
（1）索引字段的定义
索引字段的内容由字符串数据的划分值和特征值两部分组成。为了对这两部分的内容进行解释，我们需要引入一些基本概念。
定义1 划分函数：将属性R.Ai的值域Di映射到划分{p1，p2，…，pk}，满足：(1)所有划分的并可以覆盖整个域；(2)任意两个划分不重叠。形式上，定义函数partition如下：
partition(R. Ai)={p1，p2，…，pk}。
数值型字段值域的划分方法，通常采用等宽或等深划分的方法。对于字符型字段，情况要复杂一些。
一种方法是根据属性值的概率分布对属性的值域进行划分，使得每个划分包含的元素数目大致相等。比如说，假定属性Ai的取值范围为英文字典中的所有单词，则Ai值域一个可能的划分为{(a.-c．)，(d．-h.)，(i．-o．)，(p．-r．)，(s.-z．)}，其中(a．)表示以字母a开头的所有单词的集合。
定义2标识函数：为属性Ai的每个划分Pi指定一个标识符identRAi(Pi)。图2中说明了对属性A的5个划分制定标识符。
定义3映射函数：将属性Ai域中的一个值v映射到v隶属划分的标识符。形式上，MapR. Ai（v）=identR.(Ai)，其中向是包含可的划分。例如，在图2中，MapR,Ai（me）=5。
映射函数可以划分为两类。如果vi<vj =>MapR.Ai（vi）≤MapRAi（vj）。则称该函数是排序保护的；否则称它是随机的。毫无疑问，随机映射函数能够提供更好的安全性，但是针对它的查询翻译策略也更为复杂。
定义4特征函数：将字符串C1 C2…Cn映射到二进制位串b0b1…bm-1。形式上，PC(C1_C2 ...Cn)=(bob1…b-1)。H为Hash函数。如果存在某个J，满足H(ci，cj+1)=i，1≤j≤n-1，0≤i≤m-1，则bi==1；否则bi=0。
例如，s1为字符串abcehklst，Hash函数H将8个对偶ab, bc,…,st散列到0～15之间的某个数。s2=PC(abceh-klst)=(0010100010101001)2。可以发现，S2中仅出现了6个1，这是由于8个不同对偶字符的Hash值可能相同，在S2中相同的位数置1。
在定义了映射函数和特征函数之后，对于任何一个字符串，我们可以求得它的划分值和特征值。为了便于对查询条件进行翻译，我们规定索引字段的前h位表示字符串数据的划分值，后m位表示字符串数据的特征值，整个索引字段的长度为h+m位。如果划分值的位数小于h位，则在它的左边填充0。例如，对于前面的字符串(abcehklst)，它所对应的索引字段的内容为(0200101000101o1oo1)。
(2)加密关系存储模式
对于每个关系R(A1,…,Ar,…,An)，Ar为待加密的字符串字段，加密后的关系模式为RE (A1,…,ArE,…,An,...,Ars)。其中，ArE是对应于Ar的加密字符串字段，即ArE=E(Ar)；Ars是对应于Ar的辅助索引字段，通过对Ar的划分值和特征值组合得到。
2、加密字符串数据的查询
根据加密关系的存储模式，使用两阶段的查询方法实现对加密字符串数据的SQI。查询。第1阶段，对字符串字段的查洵被转化为对其相应的索引字段的查询。然而，存在一些记录满足索引字段的查询条件，却不满足字符串字段的查询条件，导致“伪记录”的产生。第2阶段，对第1阶段过滤后的记录进行解密，然后在解密的数据上进行一次精确查询。
（1）查询条件的转化
两阶段查询的关毽是如何将对加密字段的查询转化为对索引字段的查询。根据字符串数据查询的种类，分下面几种情况进行讨论。
a、精确匹配查询：如Ai>v，Ai=v．Ai<v等。
如果查询条件为Ai=v，可以慕于索引字段对加密关系进行双重过滤。首先，查找所有与v隶属相同划分的记录；其次，继续查找所有与v具有相同特征值的记录，从而获得更为精确的查询结果。形式上，Tran\s(Ai=v)jAf - MapR.Ai(v)&PC（v），符号&表示字符串连接。例如，Trans(Ai=da-vids) =>Ai= (2100101000101000QI)。
如果查询条件为Ai>v，可以基于索引字段中的划分值对加密关系进行过滤。由于本文中采用了排序保护映射函数，属性值w>v意味着MapR．Ai(w)≥Ma pR．Ai(v)。因此只需对索引字段中划分值的大小进行比较即可。形式上，Trans(Ai>v)Ais (MapR.Ai(v&00…0，其中0的个数为m。
如果查询条件为A<v，可以在加密关系中查找所有满足MCipR.Ai(w)≤Ma pR．Ai(v)）的记录w。形式上，Trans(Ai<v)_=>Ais≤MapR.Ai(v)0*11...1，其中1的个数为m。对Ai≤v查询条件的处理与Ai<v相同。
b、模糊匹配查询：如Ailike C1C2…等。
如果查询条件为Ai like C1C2…，可以基于索引字段中的特征值对加密关系进行过滤。在加密关系中查找在Ais中第h+H(cj，cj +1)位（1≤j≤k-1）为1的记录的集合。形式上，Trans(Ai like C1_C2…Ck)=>Ai s like s，其中
‘？’是代表单个字符的通配符。例如，Trans(Ai like vid)~A{like‘??????l?tlrltl9 ltltltltl7..
c、复合查询：它是由and和or将两个或多个简单查询组合而成。
复合查询的转化方式如下：
（2）查询算法
算法1两阶段查询算法
第1阶段：粗糙查询
a、利用元数据（如映射函数、特征函数等）中的规则，转换查询SQL中的条件语句；
b、执行已经转换的SQL语句，返回查询结果，并抛弃索引字段。
第2阶段：精确查询
a、解密第1阶段返回的记录，存放到一个临时表；
b、修改SQI，语句，将原始SQL语句中的关系表用临时表替换，
c、执行调整后的SQL语句，得到查询结果。
实际上，算法1中的第1阶段是用来过滤与查询条件无关的记录，以减少第2阶段解密的记录数。相对于查询操作，解密操作的代价要高许多。算法1的方法正是减少解密操作的代价，从而提高系统的查询性能。
四、加密算法分析
1、安全性分析
在加密关系中，敏感字段通过分组加密算法(如DES，AES)加密后，以密文形式存在加密数据库中，从而保证它的安全性。
但新增的索引字段存在潜在的不安全因素，需要进一步分析。
（1）划分值的安全性
由于对属性值域的划分是基于属性值的概率分布，并且每个划分包含的元素数目大致相等，因此用户很难通过统计攻击获得划分值和划分的对应情况。每个划分包含的元素数目不能太少（一般不少于10个），因此用户也不太容易通过已知明文攻击获得划分值所对应的属性值。
（2）特征值的安全性
由于在特征值定义中使用了Hash函数，攻击者很难通过特征值直接分析出敏感字段中的值。但是当特征值位数优越大时，不同的对偶字符经过散列后，其对应于特征值中不同位的可能性越大。攻击者可以通过统计得到特征值中各位出现1的概率。此外，攻击者也容易得到各对偶字符在英文中出现的概率。通过比较这两种概率，攻击者很可能根据特征值推断出敏感字段的值。解决方法是限制m的大小，使得特征值中每位对应的对偶字符数目不会太少。同样，当聊越大时，不同的字符串经过特征函数处理后，其对应的特征值不同的可能性越大，攻击者可以通过已知明文攻击来获取敏感字段的值。解决方法同样是限制m的大小，使得不同的字符串可以对应于相同的特征值。
2、过滤效率分析
在算法1中，字符串字段的查询被转化为对索引字段的查询。然而有一些并不满足查询条件的记录可能满足索引字段的查询条件，导致“伪记录”的产生。这种“伪记录”的数量与划分值位数九和特征值位数m的大小密切相关。当h越大时，划分数目越多，每个划分包含的元素数目越少，在查询的第1阶段出现的伪记录越少（至多一个划分包含伪记录），所以过滤效果越好。同样地，当优越大时，不同的字符串经过特征函数处理后，其对应的特征值重复的可能性越少，在查询的第1阶段出现的伪记录越少，所以过滤效果越好。反之，过滤效果越差。
3、存储空间分析
由于在加密数据库表中增加了索引字段，因此相应地增加了存储空间。很明显，新增存储空间的大小与索引字段的位数成正比。当索引字段位数较大，新增存储空间较大；反之，新增存储空间较少。假设数据表的记录数为以，索引字段的位数为H+m位，那么新增存储空间为n*（H+m）位。
从上面对安全性、过滤效率和存储空间的分析中可以看出，安全性与过滤效率和存储空间存在相互制约的关系，如表1所示。
通过在加密数据表增加索引字段，将数据文件加密的查询转化为对索引字段的查询，实现了加密字符串数据的两阶段查询方法。该方法需要计算每个字符串数据的划分值和特征值，并将它们存放在一个索引字段中。该方法可以支持字符串数据的精确匹配查询和模糊匹配查询，同时算法的过滤效率也得到了提高，只要索引字段的位数取合适的值，该方法可以具有较好的安全性，并且增加的存储空间很少。查
询所花费的时间代价比先解密后查询方法减少了80%左右。
小知识之字符串
字符串或串(String)是由数字、字母、下划线组成的一串字符。一般记为 s=“a1a2···an”(n>=0)。它是编程语言中表示文本的数据类型。
