数据库中字符数据的模糊匹配加密方法

对于一些重要部门或敏感领域的数据库，存在一个严重的不安全因素，即原始数据以可读的形式存储在数据库中，这使得对于一些计算机内行或内部人员来说，可以轻易绕过用户标识和鉴定、存取控制、视图、审计等基本安全技术。因此，非常有必要对数据库中存储的重要数据或敏感数据进行加密处理，在数据受到真正的威胁前设置最后一道防御屏障。但是加密后大大影响了系统原有性能，使得大型数据库加密在实际查询应用中基本不能实现。为此我们借鉴针对数值型数据的保序加密方法，提出针对字符数据的模糊匹配的加密方法。

一、针对数值型数据的保序加密方法

OPES( Order Preserving EncryptionScheme)是一种对于数值型数据保存顺序的加密方法，它允许比较操作直接应用在加密数据上，不用解密操作数。这样，等式和范围查询以及MAX，MIN和COUNT查询都可以直接应用于加密数据。同样的，GROUP BY和ORDERBY操作也能直接执行。只有对一组数进行SUM和AVG操作时，才需要解码数据值。而且加密后不影响系统的原有功能比如对数据库的查询、检索、修改、更新。

OPES基本性质：

1、应用OPES对加密数据查询处理的结果是可靠而且完整的。既不存在假命中，也不会遗漏任何答案元组。避免了在代价昂贵和复杂的后处理过程中过滤无关元组。

2、OPES能够很好地处理更新。可以修改数据库中列中的值或者可以在列中插入新值，不需要改变其他加密值。

3、OPES允许数据库在加密表上建立索引，并且能够很容易地整合到现有数据库系统中。因为在设计时，它就运用了像B树这样的索引结构。数据库被加密这对应用程序是透明的。

三、针对字符数据的模糊匹配加密方法

1、针对字符数据的模糊匹配加密方法实例

在数据库中检索和查询时，对字符串最常见的操作是在使用like操作符时的模式匹配或是等式选择。

例如：

例1：“找出大客户名单中以‘J’开头的所有客户的姓名”

Select name from Customers

where name like 'J%’

例2：查询姓名为‘Smith’的大客户的联系方式

Select telephone from Customers

where name ='Smith’

查询数值型密文数据时，可以通过保持原有明文数据顺序来提高密文查询响应速度。查询字符型密文数据时，就可以通过模糊排序来保持明文数据的大致顺序。

2、模糊匹配加密方法FMES

根据数据库中字符数据的这种查询方式，为了保证查询检索的高效率，本文提出针对字符数据的模糊匹配的两步加密方法：

首先，提取排序列字符串的第一个字符进行排序加密；

其次，对排序列的每个数据项的剩余字符进行仿射密码加密。

假设排序列全部字符集为P，分为两部分P1，P2。

（1）第一步：字符保序加密

提取加密列的字符串的第一个字符，组成一个明文字符集P1。按照OPES的方法保存这个字符集的原有顺序并加密。事先给定一个目标分布的样本值集合，通过四个步骤，把输入字符集转换成密文字符集。

a、转换：把所有输入字符转换成其ASCII值。

b、建模：根据ASCII值，把输入分布和目标分布制作成分段的线性样条的模型。使得相同或相近的字符按照ASCII值划分入相邻的存储桶中，用最小描述长度决定存储桶的数目。

c、平铺：明文字符集P根据特定的映射函数被转换成一个“平面”字符集F，这样F中的值均匀分布。

d、镜像：由明文字符集和目标样本值求得一个匹配因子L，平面字符集F根据L被镜像转换成密码字符集C。

表示为：

这种单调性变化使得ASCII值能够保存顺序，从而使每个字符之间可以模糊排序。密钥是映射函数的三个参数。

（2）第二步：仿射密码加密

仿射密码也称为线性替换密码，是多码替代的特殊情形。本方法中采用的是Hill密码，它是广义仿射密码的一个特例，其基本思想是将n个明文字母通过线性变换将它们转换为n个密文字母，解密时只需做一次逆变换即可。

设明文M= m1，m2…．，mn∈Zqn，密文C= (c1，c2…．，cn∈Zqn；，密钥为Zq上的n×n阶可逆方阵K=（kij)n×n其中方程组为：

则Hill密码处理为：

加密：C= Ek(m)=MK modq

解密：M= Dk(m)=CK-1 modq

实际中的Hill密码处理是采用解方程式的方法把明文变成密文。先把明文字符集P2按数据项分组，第一个字符相同的字符串分为一组，不同的字符分为不同组，这样无论有多少元组，整个数据库最多分成26个方程式，再建立字母与数字的对应关系来求解。本方法中字母与数字不采用顺序排列，而是采用乱序表，以避免正向猜测攻击，增加其安全性。密钥是变换矩阵和乱序表。

（3）运用FMES实现数据库常规操作

在使用like操作符进行模式匹配时，第一步就可以保证结果的正确性。

在进行等式选择操作时，先把查询语句中的明文字符串进行FMES两步加密，然后和密文匹配。插入字符串时，只需要保证明文字符串处在第一个字符相同的一组中即可。进行删除、更新操作中的第二步时，先判断除去第一个字符之后的剩余字符集p2处于26个组中的哪一个组，如果组中不只一个字符，即p2长度小于组中字符集个数，那么以上方程组中某些项即为O，简化了矩阵运算。

3、必要性

本方法没有采取对整个字符集整体排序加密，而是把字符串分为两部分，只对每个字符串的第一个字符运用OPES，大大降低了时空复杂度。而且两步加密的FMES有以下两个优点：

首先，两步加密加大了非法用户分析攻击的难度，提高了算法安全性。

其次，第一步排序加密保证了相当快的加密、解密响应速度，保证了系统性能。

允许各种操作直接应用在加密数据上，不用解密操作数。而且能够很好得处理更新，不需要改变其后的加密值。第二步仿射密码可以保证密码空间的线性替代，其明文空间、密钥空间和密文空间中的有限字符集都是一个线性映射的、而且是线性有序的。运行速度快，并且有较好的抗频率分析的功能。更重要的是，第二步加密后数据量没有增加，数据长度不变，使得剩余字符能和第一个字符一一对应。总之，两步加密相辅相成、连接紧密，既保证了加密安全性，又保证了系统运行性能。

4、安全性分析

一个加密模式的安全性在很大程度上取决于这个密码系统是否能抵抗各种攻击。

一般地，Hill密码的强度在于完全隐藏了单字母的频率，所以具有较好的抗频率分析的功能。

对于敏感的字符型数据，攻击者没必要根据加密值c来决定确切值p，它只需要获得p的精密估计就可以破坏数据。例如在某数据库Customers中，攻击者也许不关心准确的zipcode（邮政编码），而只需要判断这个zipcode是否在某段zipcode范围之内，就能推导某客户所在省份，从而暴露客户的一系列具体信息。特别是字符串长度较短时，字符串长度越短，越容易估测取值范围，从而越容易暴露。尤其第一步（字符保序加密）中，取值是单个字符，分布斜度大，取值范围很明显为a—z，A~Z。因此很容易遭到统计分析破译。对于一个单字符p，如果攻击者有c%的可能性能够估计到字符p位于区间[p1，p2]中，那么区间宽度（p2-p1）／区域宽度(p)就称为C%可信度上的暴露估计。这样，攻击者可以利用重复数据猜测区域分布。这个问题的解决方法是运用多名码方法，将一个给定明文值映射到一个加密值集合。

基本思想是修改平铺阶段。其中，每个存储桶应该映射到和存储桶中点数成正比例的空间，在这个约束下计算每个存储桶的比例系数时，把重复数据都包括在点数内。这样，重复数据聚集的区域被成比例扩散，这个区域内相邻明文值就被映射到平面数据库中相对较远的位置。

例如，明文值p映射到平面空间中的f，p+1映射到f'。加密p时，可以随机选择一个区间[f，f']内的值。这样，p的加密值会均匀分布在区间[f，f']内。把线性样条产生的桶内均匀性和比例系数产生的桶间均匀性结合起来，即使明文分布P1有重复数据的偏差分布，结果平铺分布仍然是均匀的。这也是对OPES的改进——在平铺阶段暴露出重复数据。利用这个扩展，算法中可以通过转换谓词来选择加密数据。

例如，选择操作中把字符等式查询转换为范围谓词查询。例如：

这些过程对用户来说是透明的。

5、密钥管理

（1）原理

密码学中常用的一个原则：在最坏的情况下要保证“秘密全部存在于密钥之中”。密钥的保密和安全管理就显得尤为重要。本文的加密方法中，数据库加密算法和密钥第一次加密确定后，就不再更改，所以生存周期长，容易给攻击者以可乘之机。两个步骤加密的密钥都是需要绝对保密的。所以需要采取公钥加密系统对数据库密钥进行二次加密。

数据库系统的密钥管理比网络系统的管理更复杂，并且具有它自己独特的特点，即数据库文件加密密钥的时间不变和用户不变性。到目前为止，讨论比较多的是集中密钥管理和子密钥数据库文件加密的密钥管理。

集中密钥管理中，若用户想访问数据库数据，必须输入用户标识符(ID)，由安全核实机构对其核实，看是否有访问权。若有权访问，则提供给相应的数据加密密钥，对所需数据解密后，供用户使用。

这种密钥管理方式，用户使用方便、灵活，但由于这些密钥都由安全管理人员控制，权利过分集中，同时在用户远程访问时，数据必须要由网络加密保护。本方法中改进了这种方式，实行密钥分散管理，即按照数据秘密等级把密钥K分量化K1，K2，. - - -．，Kn，比如本方法中分为K1，K2，排序列字符串加密密钥为K1，其余字符串常规加密密钥为K2，K2还可以根据应用，提出防欺诈的分散密钥管理方法。

（2）密文数据库简化模型

假设数据库模型简化如下：数据库D={d1，d2…．，dn}，d1代表安全级别相同、用同一数据加密密钥加密的一类数据，其安全级别记为j1。根据加密粒度的选择，相应的数据密钥集KD={kd1，kd2…，，kdn），这样密文数据库可表示为C={(ci,ji)|ci=E(kdi,di),i=1,2,…,n)。

本方法中数据库D={d1，d2}，相应的数据密钥集K={K1，K2}，密文数据库可表示为C={(ci,ji)| ci=E(Ki，di)，i=1，2)。以下的例子中，简称数据库服务器管理员为A，用户为B。

数据库文件加密后，往往需要对不伺的用户授以不同的使用权利。本方法中使用权限访问表解决这一问题。权限访问表以矩阵形式存储。

当且仅当用户i能够访问安全级别为1的数据类dj时，表中对应的元素就是密钥认证结果KA (Key Authentication)。这种方式类似于多级安全数据库中的强制访问控制策略。

（3）防欺诈的分散密钥管理方法

数据库服务器管理员A接到用户B的请求，查询权限访问表，以确定用户的访问级别是K1还是K2。图1、图2、图3中均以K来代表K1或K2，说明某用户的密文访问过程。

首先，利用单向散列函数进行密钥认证，见图1。如果和已知散列值相同，就证明了存储在服务器上的密钥的完整性和正确性。实际传输过程中的密钥不是数据库的真实密钥K，而是K的散列码值KA，这样一旦在网络传输过程中泄露KA或被篡改E(KA)，攻击者也不会直接得到数据库的真实密钥，进一步提高了安全性。其次，通过双向身份认证，结合数据库授权机制，把相应密钥分发给有权访问相应数据的用户，即管理员A把密钥KA加密后传送给用户B，见图2。用户B收到被加密的密钥E(KA)后解密，见图3。

其中运用公钥加密系统，使得用户B相信确实是管理员A发送的密钥，而且这个密钥只有用户B才能解密，不会发送到无关人员处。这就起到了防欺诈的作用，保证了把完整、真实的密钥安全分配给授权用户。

由于通用数据库和安全数据库设计理念和算法的不同，在数据库系统之上加入B级安全机制会导致查询性能大大降低。所以对加密数据进行查询处理还需要更加成熟的方法。本文提出的一种针对字符数据的模糊匹配的两步加密算法，保证了敏感数据的安全性和完整性，也解决了系统性能问题，有很大的实际应用前景。

admin普通用户

海报分享