為了解決數(shù)據(jù)庫中加密字符串?dāng)?shù)據(jù)的查詢問題，我們提出了為待加密的字段建立輔助索引字段的兩階段查詢方法。索引字段的內(nèi)容由原始數(shù)據(jù)的劃分值和特征值兩部分組成，它可以用采支持字符串?dāng)?shù)據(jù)的精確匹配查詢和模糊匹配查詢。查詢加密數(shù)據(jù)時，首先利用索引字段對加密數(shù)據(jù)進(jìn)行一次粗糙查詢，然后在解密的數(shù)據(jù)上再進(jìn)行一次精確查詢。這就是今天我們要說的可支持快速查詢的數(shù)據(jù)庫的加密方法。

一、支持快速查詢的數(shù)據(jù)庫加密原理

它將字符串?dāng)?shù)據(jù)的劃分值和特征值合并于同一個索引字段中。劃分值用于支持字符串?dāng)?shù)據(jù)的精確匹配查詢，而特征值用于支持字符串?dāng)?shù)據(jù)的模糊匹配查詢。通過修改查詢語句的轉(zhuǎn)換函數(shù)，本文方法能夠?qū)崿F(xiàn)各種類型的查詢請求，同時系統(tǒng)的性能也得到了提高。

二、系統(tǒng)的體系結(jié)構(gòu)和控制流

我們提出的系統(tǒng)在應(yīng)用程序和數(shù)據(jù)庫管理系統(tǒng)之間增加了一個數(shù)據(jù)庫文件加密和解密引擎，它的體系結(jié)構(gòu)和控制流如圖1所示：

在圖1中，查詢翻譯器負(fù)責(zé)將用戶的原始查詢轉(zhuǎn)換為對加密數(shù)據(jù)的查詢，在轉(zhuǎn)換的過程中它需要訪問元數(shù)據(jù)；元數(shù)據(jù)是一些轉(zhuǎn)換規(guī)則的集合，用于對查詢語句進(jìn)行修改，查詢執(zhí)行器負(fù)責(zé)對加密查詢結(jié)果進(jìn)行解密，并在解密的數(shù)據(jù)上再執(zhí)行一次原始查詢；最后查詢執(zhí)行器將精確查詢結(jié)果返回給用戶。

這種體系結(jié)構(gòu)不需要對原有的應(yīng)用程序和DBMS進(jìn)行修改，因而它具有良好的適用性。

三、加密字符串?dāng)?shù)據(jù)的存儲與查詢

1、 加密字符串?dāng)?shù)據(jù)的存儲

（1）索引字段的定義

索引字段的內(nèi)容由字符串?dāng)?shù)據(jù)的劃分值和特征值兩部分組成。為了對這兩部分的內(nèi)容進(jìn)行解釋，我們需要引入一些基本概念。

定義1 劃分函數(shù)：將屬性R.Ai的值域Di映射到劃分{p1，p2，…，pk}，滿足：(1)所有劃分的并可以覆蓋整個域；(2)任意兩個劃分不重疊。形式上，定義函數(shù)partition如下：

partition(R. Ai)={p1，p2，…，pk}。

數(shù)值型字段值域的劃分方法，通常采用等寬或等深劃分的方法。對于字符型字段，情況要復(fù)雜一些。

一種方法是根據(jù)屬性值的概率分布對屬性的值域進(jìn)行劃分，使得每個劃分包含的元素數(shù)目大致相等。比如說，假定屬性Ai的取值范圍為英文字典中的所有單詞，則Ai值域一個可能的劃分為{(a.-c．)，(d．-h.)，(i．-o．)，(p．-r．)，(s.-z．)}，其中(a．)表示以字母a開頭的所有單詞的集合。

定義2標(biāo)識函數(shù)：為屬性Ai的每個劃分Pi指定一個標(biāo)識符identRAi(Pi)。圖2中說明了對屬性A的5個劃分制定標(biāo)識符。

定義3映射函數(shù)：將屬性Ai域中的一個值v映射到v隸屬劃分的標(biāo)識符。形式上，MapR. Ai（v）=identR.(Ai)，其中向是包含可的劃分。例如，在圖2中，MapR,Ai（me）=5。

映射函數(shù)可以劃分為兩類。如果vi<vj =>MapR.Ai（vi）≤MapRAi（vj）。則稱該函數(shù)是排序保護(hù)的；否則稱它是隨機(jī)的。毫無疑問，隨機(jī)映射函數(shù)能夠提供更好的安全性，但是針對它的查詢翻譯策略也更為復(fù)雜。

定義4特征函數(shù)：將字符串C1 C2…Cn映射到二進(jìn)制位串b0b1…bm-1。形式上，PC(C1_C2 ...Cn)=(bob1…b-1)。H為Hash函數(shù)。如果存在某個J，滿足H(ci，cj+1)=i，1≤j≤n-1，0≤i≤m-1，則bi==1；否則bi=0。

例如，s1為字符串a(chǎn)bcehklst，Hash函數(shù)H將8個對偶ab, bc,…,st散列到0～15之間的某個數(shù)。s2=PC(abceh-klst)=(0010100010101001)2?？梢园l(fā)現(xiàn)，S2中僅出現(xiàn)了6個1，這是由于8個不同對偶字符的Hash值可能相同，在S2中相同的位數(shù)置1。

在定義了映射函數(shù)和特征函數(shù)之后，對于任何一個字符串，我們可以求得它的劃分值和特征值。為了便于對查詢條件進(jìn)行翻譯，我們規(guī)定索引字段的前h位表示字符串?dāng)?shù)據(jù)的劃分值，后m位表示字符串?dāng)?shù)據(jù)的特征值，整個索引字段的長度為h+m位。如果劃分值的位數(shù)小于h位，則在它的左邊填充0。例如，對于前面的字符串(abcehklst)，它所對應(yīng)的索引字段的內(nèi)容為(0200101000101o1oo1)。

(2)加密關(guān)系存儲模式

對于每個關(guān)系R(A1,…,Ar,…,An)，Ar為待加密的字符串字段，加密后的關(guān)系模式為RE (A1,…,ArE,…,An,...,Ars)。其中，ArE是對應(yīng)于Ar的加密字符串字段，即ArE=E(Ar)；Ars是對應(yīng)于Ar的輔助索引字段，通過對Ar的劃分值和特征值組合得到。

2、加密字符串?dāng)?shù)據(jù)的查詢

根據(jù)加密關(guān)系的存儲模式，使用兩階段的查詢方法實現(xiàn)對加密字符串?dāng)?shù)據(jù)的SQI。查詢。第1階段，對字符串字段的查洵被轉(zhuǎn)化為對其相應(yīng)的索引字段的查詢。然而，存在一些記錄滿足索引字段的查詢條件，卻不滿足字符串字段的查詢條件，導(dǎo)致“偽記錄”的產(chǎn)生。第2階段，對第1階段過濾后的記錄進(jìn)行解密，然后在解密的數(shù)據(jù)上進(jìn)行一次精確查詢。

（1）查詢條件的轉(zhuǎn)化

兩階段查詢的關(guān)毽是如何將對加密字段的查詢轉(zhuǎn)化為對索引字段的查詢。根據(jù)字符串?dāng)?shù)據(jù)查詢的種類，分下面幾種情況進(jìn)行討論。

a、精確匹配查詢：如Ai>v，Ai=v．Ai<v等。

如果查詢條件為Ai=v，可以慕于索引字段對加密關(guān)系進(jìn)行雙重過濾。首先，查找所有與v隸屬相同劃分的記錄；其次，繼續(xù)查找所有與v具有相同特征值的記錄，從而獲得更為精確的查詢結(jié)果。形式上，Tran\s(Ai=v)jAf - MapR.Ai(v)&PC（v），符號&表示字符串連接。例如，Trans(Ai=da-vids) =>Ai= (2100101000101000QI)。

如果查詢條件為Ai>v，可以基于索引字段中的劃分值對加密關(guān)系進(jìn)行過濾。由于本文中采用了排序保護(hù)映射函數(shù)，屬性值w>v意味著MapR．Ai(w)≥Ma pR．Ai(v)。因此只需對索引字段中劃分值的大小進(jìn)行比較即可。形式上，Trans(Ai>v)Ais (MapR.Ai(v&00…0，其中0的個數(shù)為m。

如果查詢條件為A<v，可以在加密關(guān)系中查找所有滿足MCipR.Ai(w)≤Ma pR．Ai(v)）的記錄w。形式上，Trans(Ai<v)_=>Ais≤MapR.Ai(v)0*11...1，其中1的個數(shù)為m。對Ai≤v查詢條件的處理與Ai<v相同。

b、模糊匹配查詢：如Ailike C1C2…等。

如果查詢條件為Ai like C1C2…，可以基于索引字段中的特征值對加密關(guān)系進(jìn)行過濾。在加密關(guān)系中查找在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、復(fù)合查詢：它是由and和or將兩個或多個簡單查詢組合而成。

復(fù)合查詢的轉(zhuǎn)化方式如下：

（2）查詢算法

算法1兩階段查詢算法

第1階段：粗糙查詢

a、利用元數(shù)據(jù)（如映射函數(shù)、特征函數(shù)等）中的規(guī)則，轉(zhuǎn)換查詢SQL中的條件語句；

b、執(zhí)行已經(jīng)轉(zhuǎn)換的SQL語句，返回查詢結(jié)果，并拋棄索引字段。

第2階段：精確查詢

a、解密第1階段返回的記錄，存放到一個臨時表；

b、修改SQI，語句，將原始SQL語句中的關(guān)系表用臨時表替換，

c、執(zhí)行調(diào)整后的SQL語句，得到查詢結(jié)果。

實際上，算法1中的第1階段是用來過濾與查詢條件無關(guān)的記錄，以減少第2階段解密的記錄數(shù)。相對于查詢操作，解密操作的代價要高許多。算法1的方法正是減少解密操作的代價，從而提高系統(tǒng)的查詢性能。

四、加密算法分析

1、安全性分析

在加密關(guān)系中，敏感字段通過分組加密算法(如DES，AES)加密后，以密文形式存在加密數(shù)據(jù)庫中，從而保證它的安全性。

但新增的索引字段存在潛在的不安全因素，需要進(jìn)一步分析。

（1）劃分值的安全性

由于對屬性值域的劃分是基于屬性值的概率分布，并且每個劃分包含的元素數(shù)目大致相等，因此用戶很難通過統(tǒng)計攻擊獲得劃分值和劃分的對應(yīng)情況。每個劃分包含的元素數(shù)目不能太少（一般不少于10個），因此用戶也不太容易通過已知明文攻擊獲得劃分值所對應(yīng)的屬性值。

（2）特征值的安全性

由于在特征值定義中使用了Hash函數(shù)，攻擊者很難通過特征值直接分析出敏感字段中的值。但是當(dāng)特征值位數(shù)優(yōu)越大時，不同的對偶字符經(jīng)過散列后，其對應(yīng)于特征值中不同位的可能性越大。攻擊者可以通過統(tǒng)計得到特征值中各位出現(xiàn)1的概率。此外，攻擊者也容易得到各對偶字符在英文中出現(xiàn)的概率。通過比較這兩種概率，攻擊者很可能根據(jù)特征值推斷出敏感字段的值。解決方法是限制m的大小，使得特征值中每位對應(yīng)的對偶字符數(shù)目不會太少。同樣，當(dāng)聊越大時，不同的字符串經(jīng)過特征函數(shù)處理后，其對應(yīng)的特征值不同的可能性越大，攻擊者可以通過已知明文攻擊來獲取敏感字段的值。解決方法同樣是限制m的大小，使得不同的字符串可以對應(yīng)于相同的特征值。

2、過濾效率分析

在算法1中，字符串字段的查詢被轉(zhuǎn)化為對索引字段的查詢。然而有一些并不滿足查詢條件的記錄可能滿足索引字段的查詢條件，導(dǎo)致“偽記錄”的產(chǎn)生。這種“偽記錄”的數(shù)量與劃分值位數(shù)九和特征值位數(shù)m的大小密切相關(guān)。當(dāng)h越大時，劃分?jǐn)?shù)目越多，每個劃分包含的元素數(shù)目越少，在查詢的第1階段出現(xiàn)的偽記錄越少（至多一個劃分包含偽記錄），所以過濾效果越好。同樣地，當(dāng)優(yōu)越大時，不同的字符串經(jīng)過特征函數(shù)處理后，其對應(yīng)的特征值重復(fù)的可能性越少，在查詢的第1階段出現(xiàn)的偽記錄越少，所以過濾效果越好。反之，過濾效果越差。

3、存儲空間分析

由于在加密數(shù)據(jù)庫表中增加了索引字段，因此相應(yīng)地增加了存儲空間。很明顯，新增存儲空間的大小與索引字段的位數(shù)成正比。當(dāng)索引字段位數(shù)較大，新增存儲空間較大；反之，新增存儲空間較少。假設(shè)數(shù)據(jù)表的記錄數(shù)為以，索引字段的位數(shù)為H+m位，那么新增存儲空間為n*（H+m）位。

從上面對安全性、過濾效率和存儲空間的分析中可以看出，安全性與過濾效率和存儲空間存在相互制約的關(guān)系，如表1所示。

通過在加密數(shù)據(jù)表增加索引字段，將數(shù)據(jù)文件加密的查詢轉(zhuǎn)化為對索引字段的查詢，實現(xiàn)了加密字符串?dāng)?shù)據(jù)的兩階段查詢方法。該方法需要計算每個字符串?dāng)?shù)據(jù)的劃分值和特征值，并將它們存放在一個索引字段中。該方法可以支持字符串?dāng)?shù)據(jù)的精確匹配查詢和模糊匹配查詢，同時算法的過濾效率也得到了提高，只要索引字段的位數(shù)取合適的值，該方法可以具有較好的安全性，并且增加的存儲空間很少。查
詢所花費(fèi)的時間代價比先解密后查詢方法減少了80%左右。

admin

收藏 海報分享