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

一、支持快速查詢的數據庫加密原理

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

二、系統(tǒng)的體系結構和控制流

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

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

這種體系結構不需要對原有的應用程序和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。可以發(fā)現，S2中僅出現了6個1，這是由于8個不同對偶字符的Hash值可能相同，在S2中相同的位數置1。

在定義了映射函數和特征函數之后，對于任何一個字符串，我們可以求得它的劃分值和特征值。為了便于對查詢條件進行翻譯，我們規(guī)定索引字段的前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隸屬相同劃分的記錄；其次，繼續(xù)查找所有與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、利用元數據（如映射函數、特征函數等）中的規(guī)則，轉換查詢SQL中的條件語句；

b、執(zhí)行已經轉換的SQL語句，返回查詢結果，并拋棄索引字段。

第2階段：精確查詢

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

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

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

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

四、加密算法分析

1、安全性分析

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

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

（1）劃分值的安全性

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

（2）特征值的安全性

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

2、過濾效率分析

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

3、存儲空間分析

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

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

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

admin

收藏 海報分享