基于商用数据库管理系统的字符串数据的加密存储与查询

作为现代信息系统的核心软件，数据库中包含大量重要的数据，但是多数数据库管理系统运行在存在安全漏洞的环境中，其中，不安全的因素包括操作系统的漏洞，网络的攻击，内部人员的蓄意破坏，甚至是数据库管理员(DBA)也是潜在的安全隐患，如何在非可信的环境下保证数据库中数据的安全性已经成为研究的一个热点，其中，通过加密机制保护数据库中的机密信息是一种有效的手段，加密机制可以用来防止：

(1)用户绕过操作系统(或DBMS)的控制入侵到系统中，并窃取数据库中的信息；

(2)存储数据介质（如磁盘、光盘、磁带等）丢失导致数据库中的数据泄漏；

(3)数据库中数据的真实性没有办法核实。

然而，当数据库中存储密文数据时，如何进行高效地查询成为一个重要的问题，一般的方法是首先对加密数据进行解密，然后对解密数据进行查询，但由于要对整个数据库进行加密／解密操作，开销巨大，在实际操作中是不可行的。当然，针对某些查询条件也可以不用解密数据而对加密数据直接查询，例如，当soL条件语句包含“=”时，先对soL中的条件值进行同样加密处理，然后与数据库中存储的加密数据比较，如果相等，返回相应的记录。然而，对加密数据上的大量查询（如：>，<，like）变得不可能，由于数据加密后，一些固有属性发生变化，例如数据的有序性(Ordering)、相似性(Similari-ty)、可比性(Comparability)遭到破坏，没有办法进行比较判断。

我们提出一种可以有效实现对加密字符串数据模糊匹配查询的方法，加密存储时，根据字符串数据的特点，构造一些特征函数，利用特征函数对需要加密的字段进行映射，其映射值存放在加密数据表中的新增字段中，查询加密数据时，采用两阶段查询方法。首先对加密数据进行一次粗糙查询(CoarseQuery)，利用加密数据表中的额增字段，过滤部分与查询条件无关的记录；然后对剩余记录中的加密数据进行解密，在解密的数据上再进行一次精确查询(Refined Query)，最终实现查询目标。这种查询方法可以减少操作代价较大的解密数据，从而提高对加密数据查询的性能。

一、相关工作

不用解密数据而对加密数据直接进行算术运算和访问已经引起研究人员的广泛关注。一方面它可以减少解密所花费的时间代价，提高查询性能，另一方面可以减少解密数据后带 来潜在的不安全因素。我们使用一些特殊的算法，实现了对加密数据的加法运算，但密钥管理过于复杂。建议使用基于同态函数的算法来处理加密数据，但是有资料认为这种函数能够通过解线性方程组来破解。

最近，Dawn Xiaodong Song提出使用序列加密(stream cipher)方法加密数据，实现对加密数据的搜索。存储时，它采用序列密码算法把每个“词”(word)与随机发生器所产生的，随机数进行位异或，结果存储在加密的文件中，查询时，把查询词与密文异或，然后与随机数比较，以确定文件中是否包含该词，这种方法简单，几乎不增加额外存储空间，运算速度快，但是，对数据库中存储数据的加密一般不采用序列密码算法。

Hankan HacijumusuoJ提出基于客户机/服务器(C/S)对加密数据进行查询的一种方法。该方法使用一些函数对需加密的数据建立索引，并把索引存储在服务器中的加密数据库，从而在查询时，可以利用加密数据库中的索引，实现对加密数据的范围查询（如：>．<）。但是，这种方法并不适合对其它类型的数据建立索引，比如说字符申数据，因为字符串数据查询与数值型数据查询的模式不同，字符串数据查询分为精确匹配查询（如，=）和模糊匹配查询(如tlike)。对于精确匹配查询，这种方法是有效的，但是对于模糊匹配查询，这种方法显得无能为力。

二、加密字符串数据存储与查询的体系结构

数据库加密的方式很多，有基于应用程序、DBMS和操作系统，也可以由应用程序、DBMS和操作系统相互共同完成。我们选择在商用数据库管理系统和应用程序之间增加一层软件，即加密／解密层，实现对加密数据的存储与查询。这样可以不用对商用DBMS进行修改，也无须对应用程序修改，具有很好的实用性。加密字符申数据存储与查询的体系结构如图1所示。

在图1的加密/解密层中，元数据是一些函数映射规则。用来修改存储和查询语句，存储时，除了加密数据外，还通过这些规则修改soL语句，存储加密数据的特征值。查询时，通过这些规则修改查询语句，得到对加密数据查询的soL语句。加密和解密是由加密／解密函数来实现对机密信息列进行加密和解密的功能模块。

三、存储和查询

1、加密关系模式(ERS．Encrypted Relatlon Schema)

对于传统数据库中每个关系模式R(Xi，…．Xr．…．Xn)。其中，Xr为需要加密的字符串字段，以加密关系模式RE(X1E，…．XrE．…．Xn，A(xr))存储，其中，RE中XrE是对R中Xr加密的结果，即XrE=E(xr)IA(X，)是对R中Xf通过特征函数转换后新增的附加字段，其余的列与R中的列相同。

2、特征函救字符函数(Alphabet Functlon)

定义1、设有一函数A: sl→s2．其中sl和s2为两字符串，如果s2是由sl中不重复的字符组成1，并且s2中的字符按照一定大小顺序排列2。则我们称函数A为字符函数，例如：字符串sl为Chess basketball，则s2 -A(sl)(abcehklst)。 定义2、设数据库中关系模式R(Xi，…．Xr，…．Xn)，加密后对应关系模式为RE(X1E，…．XrE．…．Xn，A(xr))。其中，A是字符函数，我们称A(Xr)为关系RE的字符字段。

3、查询算法 算法1

第一阶段：粗糙查询(Coarse Query)阶段

(1)利用元数据（如字符函数），调整SQL语句，首先，把条件语句中的加密字段用字符字段替换l然后，用字符函数去映射条件字符串I最后，改写Where子句，只要字符字段包含条件字符串中所有单个的字符，就返回相应记录。

(2)执行已经转换的SQL语句，返回满足条件的记录，并抛弃字符字段。

第二阶段：精确查询(Refined Query)阶段

(1)解密第一阶段已经过滤的记录，存放到数据库中的一个临时表。

(2)调整SQL语句，把原始SQL语句中的关系表用临时表替换。

(3)执行调整后的SQL语句，得到查询结果。

4、分析

（1）算法1的查询正确性

定理1(算法1的查询正确性)：利用算法1对加密数据查询时，查询处理的结果是正确的。 证明：从两个方面考虑，一方面，符合查询条件的记录不会被过滤掉，任意一记录，如果需加密的字段包含查询条件的字符串，加密后，其对应的字符字段必然包括条件字符串的所有单个字符，根据算法1的第一阶段步骤，此记录是不会被过滤掉，在第二阶段查询中，加密字段被解密后，也必然包括条件字符串，所以也不会过滤掉。另一方面，不符合查询条件的记录一定被过滤掉，这个比较简单，在算法1的第一阶段查询处理，由于根据字符字段来过滤记录，可能包括一些不满足条件的记录，但经过第二阶段查询处理，这些不满足条件的记录一定被过滤掉，所以说查询处理的结果是正确的。

（2）安全性

在加密关系模式中，对机密信息列进行加密处理来保证其安全性。但是，其对应的字符字段中包含机密信息字段出现过的单个字符，尽管对单个字符进行重新排序，打乱原来顺序，仍然给攻击者泄漏一些信息，容易实施已知明文攻击和统计攻击。 为进一步保证安全，我们选择基于中国剩余定理(CRT，Chinese remainder theorem)对字符字段进行加密。这种加密模式能够很好防止已知明文攻击和统计攻击，并且性能好，特别是解密的速度相当快，只需要进行一次模运算，而且不增加额外存储空间。但是这种加密方法的安全性与一些成熟的算法（如AES，DES）相比，还是有许多不足之处，所以我们并不用这种方法对机密信息字段直接进行加密。使用这种方法对字符字段加密后，如果攻击者需要从字符字段来获取机密信息，除了破译CRT加密外，还得从字符字段来推断机密信息，这无疑增加了攻击者的难度。

（3）问题

在第一阶段的粗糙查询中，当机密信息字段包含不同字符个数越多。ERS中字符字段包含字符个数就越多，那么在第一阶段粗糙查询中，被过滤的记录越少，在第二阶段查询中需要解密的记录越多，这样会导致查询的性能下降。一种极端的情形是，需要加密的机密信息宇段包含所有的字符，则ERS中字符字段也包含所有字符，那么通过第一阶段的粗糙查询后，将返回所有的记录，不会起到任何过滤作用。 我们经常发现soL查询语句的条件字符串往往包含重复的字符，以此为前提，在下一节提出一种改进的方法，能够在第一阶段粗挺查询中过滤掉更多无关的记录，更大程度改善查询性能。

四、改进的存储和查询

1、改进的加密关系模式(IERS，Improved Encrypted Rela-tional Schema)

在ERS的加密关系模式RE(X1E，…．XrE．…．Xn，A(xr))中，增加一个字段F(Xr>，F(Xr)是对R中Xr，通过频率函数(Frequency Function)映射后产生的。

2、特征函数2：频宰函数(Frequency Function)

定义3、设s是来自字符表∑={a1，a2，…，am）的一字符串，nl是aj在s中出现的次数3，其中l≤i≤m．ai是按顺序排列。1≤ni<10，我们定义频率函数为： F(s）=[n1，n2，…．nm] 例如，字符串s为Chessbasketball，则F(s>=[2.2.1.2.1.1．2,3,]。

定义4、设数据库中关系模式R(X1，…，Xr，…，Xn)。加密后对应关系模式为RE(X1E，…．XrE．…．Xn，A(xr))。其中，F是频率函数，我们称F(Xr)为关系RE的频率字段。

3、改进的查询算法

算法2、第一阶段：粗糙查询阶段

(1)利用元数据（如字符函数和频率函数）调整SQL语句。除了进行算法1中的调整方法外，还应在where子句后面增加频率字段形成的过滤条件，使得条件字符串中每个字符的频率应少于或等于字符字段中相应字符的频率。

(2)执行已经转换过查询条件的soL语句，返回过滤后部分记录，并抛弃字符字段和频率字段。

第二阶段、精确查询阶段，与算法1-致。

4、分析

（1）算法2的查询正确性

定理2（算法2的查询正确性）利用算法2对加密数据查询时，查询处理的结果是正确的。

证明：与定理l的证明方法一样，也从两个方面考虑，一方面，符合查询条件的记录不会被过滤掉。由定理1可知，符合查询条件的记录不会被字符字段被过滤掉。同样地，任意一条记录，如果需加密的字段包含查询条件的字符串，加密后，其对应的频率字段中各字符的频率必然大于或等于条件字符串中相应字符的频率，根据算法2的第一阶段步骤，此记录是不会被过滤掉，在第二阶段查询中，加密字段被懈密后，也必然包括条件字符串，所以也不会过滤掉。另一方面，不符合查询条件的记录一定被过滤掉，第一阶段查询处理，由于根据字符字段和频率字段来过滤记录，包括一些不满足条件的记录，但经过第二阶段查询处理，这些不满足条件的记录一定被过滤掉，所以说查询处理的结果是正确的。

（2）安全性

改进的加密关系模式(IERS)既存储机密信息所包含的字符，又存储各字符在机密信息出现的频率，这无疑给攻击者带来更大的便利，我们还是采取上一节的方法对字符字段和频率字段进行基于CRT加密，以保证其安全性。在lERS中进行粗糙查询时，对频率字段不必全部解密，只有当记录的字符字段满足查询条件时，才会进一步使用频率字段进行过滤查询，这样能够在一定程度提高系统的性能。

五、实验与性能分析

本文提出两阶段查询方法的关键之处在于第一阶段粗糙查询的过滤效率，如果第一阶段过滤效率好，那么第二阶段只需解密少量的记录，反之，则需要解密较多记录，如果需要解密较多记录，则此方法的意义则不大。在实验中，我们验证了此方法的可行性．实验所使用的数据表为employee (no,name．s_infor，age，sex)．有100万条数据，使用的加密算法是safer++。需要加密的字段为s，Lnfor．SQL语句为select* from employee where s_infor like条件字符串，实验环境为Windows NT操作系统，SQL Server 2000数据库服务器。CPU为P4 2GHz，内存为512MB。我们做两个实验，分别为：

(1)比较本文所采取方法和先解密后查询方法的时间代价。

(2)对IERS进行测试，分别得到字符字段和频率字段过滤记录的效果。

1、实验1与先解密后查询方法的性能比较

在第一个实验中，分析各种查询方法对加密数据表查询所花费的时间代价。

图2(a)和图2(b)分别显示需加密字符串长度和需加密记录数不同时，各种方法的查询代价，通过比较，我们发现，与先解密后查询方法相比，本文所采取的方法在性能上提高50%以上。这主要是因为safer++算法解密速度慢，所花费的时间大约是查询数据所花费时间的12倍，是CTR解密所花费时间的10倍。查询加密数据的主要代价花费在数据的解密上，而本文所采取的方法正是尽可能减少解密的记录数，从而使得查询性能得以提高，我们在下一个实验进一步分析采用字符字段和频率字段所起到的过滤效果，以便清晰了解所减少的解密记录数。

2、实验2 附加字段过滤的效果

在实验2中，我们首先测试Where子句中条件字符串长度的变化对字符字段过滤效率的影响，图3(a)显示查询的结果，不同折线表示需加密字段的长度，我们可以看到：

(1)随着条件字符串长度的增加，返回的记录越少。原因是条件字符串长度增加，包含不同的字符个数相应增加，那么加密数据库中字符字段与之匹配的记录越少，所以返回的记录越少。

(2)随着需加密字段的长度增加，返回的记录越多。原因是加密字段的长度增加，对应的字符字段包含的字符个数相应增加，那么与条件字符串匹配的记录越多，所以返回的记录越多。

然后根据频率字段再进行过滤，假设Where子句中条件字符串只有一个字符的频率为2，过滤的结果见图3(b)。我们看到：随着需加密字段值长度的增加，返回的记录越多。原因是随着需加密字段值长度的增加，对应的频率字段包含重复字符个数相应增多，那么条件字符串各字符的频率与频率字段值匹配的记录越多，所以返回的记录越多。

图3(c)给出在字符字段和频率宇段的共同过滤下，所返回的记录百分比，不同折线表示需加密字段的长度。soL语句中条件字符串有一个字符的频率为2。我们可以看到，返回的记录百分比在2～12%，过滤效果相当好。