作為現(xiàn)代信息系統(tǒng)的核心軟件，數(shù)據(jù)庫中包含大量重要的數(shù)據(jù)，但是多數(shù)數(shù)據(jù)庫管理系統(tǒng)運(yùn)行在存在安全漏洞的環(huán)境中，其中，不安全的因素包括操作系統(tǒng)的漏洞，網(wǎng)絡(luò)的攻擊，內(nèi)部人員的蓄意破壞，甚至是數(shù)據(jù)庫管理員(DBA)也是潛在的安全隱患，如何在非可信的環(huán)境下保證數(shù)據(jù)庫中數(shù)據(jù)的安全性已經(jīng)成為研究的一個(gè)熱點(diǎn)，其中，通過加密機(jī)制保護(hù)數(shù)據(jù)庫中的機(jī)密信息是一種有效的手段，加密機(jī)制可以用來防止：

(1)用戶繞過操作系統(tǒng)(或DBMS)的控制入侵到系統(tǒng)中，并竊取數(shù)據(jù)庫中的信息；

(2)存儲(chǔ)數(shù)據(jù)介質(zhì)（如磁盤、光盤、磁帶等）丟失導(dǎo)致數(shù)據(jù)庫中的數(shù)據(jù)泄漏；

(3)數(shù)據(jù)庫中數(shù)據(jù)的真實(shí)性沒有辦法核實(shí)。

然而，當(dāng)數(shù)據(jù)庫中存儲(chǔ)密文數(shù)據(jù)時(shí)，如何進(jìn)行高效地查詢成為一個(gè)重要的問題，一般的方法是首先對(duì)加密數(shù)據(jù)進(jìn)行解密，然后對(duì)解密數(shù)據(jù)進(jìn)行查詢，但由于要對(duì)整個(gè)數(shù)據(jù)庫進(jìn)行加密／解密操作，開銷巨大，在實(shí)際操作中是不可行的。當(dāng)然，針對(duì)某些查詢條件也可以不用解密數(shù)據(jù)而對(duì)加密數(shù)據(jù)直接查詢，例如，當(dāng)soL條件語句包含“=”時(shí)，先對(duì)soL中的條件值進(jìn)行同樣加密處理，然后與數(shù)據(jù)庫中存儲(chǔ)的加密數(shù)據(jù)比較，如果相等，返回相應(yīng)的記錄。然而，對(duì)加密數(shù)據(jù)上的大量查詢（如：>，<，like）變得不可能，由于數(shù)據(jù)加密后，一些固有屬性發(fā)生變化，例如數(shù)據(jù)的有序性(Ordering)、相似性(Similari-ty)、可比性(Comparability)遭到破壞，沒有辦法進(jìn)行比較判斷。

我們提出一種可以有效實(shí)現(xiàn)對(duì)加密字符串?dāng)?shù)據(jù)模糊匹配查詢的方法，加密存儲(chǔ)時(shí)，根據(jù)字符串?dāng)?shù)據(jù)的特點(diǎn)，構(gòu)造一些特征函數(shù)，利用特征函數(shù)對(duì)需要加密的字段進(jìn)行映射，其映射值存放在加密數(shù)據(jù)表中的新增字段中，查詢加密數(shù)據(jù)時(shí)，采用兩階段查詢方法。首先對(duì)加密數(shù)據(jù)進(jìn)行一次粗糙查詢(CoarseQuery)，利用加密數(shù)據(jù)表中的額增字段，過濾部分與查詢條件無關(guān)的記錄；然后對(duì)剩余記錄中的加密數(shù)據(jù)進(jìn)行解密，在解密的數(shù)據(jù)上再進(jìn)行一次精確查詢(Refined Query)，最終實(shí)現(xiàn)查詢目標(biāo)。這種查詢方法可以減少操作代價(jià)較大的解密數(shù)據(jù)，從而提高對(duì)加密數(shù)據(jù)查詢的性能。

一、相關(guān)工作

不用解密數(shù)據(jù)而對(duì)加密數(shù)據(jù)直接進(jìn)行算術(shù)運(yùn)算和訪問已經(jīng)引起研究人員的廣泛關(guān)注。一方面它可以減少解密所花費(fèi)的時(shí)間代價(jià)，提高查詢性能，另一方面可以減少解密數(shù)據(jù)后帶 來潛在的不安全因素。我們使用一些特殊的算法，實(shí)現(xiàn)了對(duì)加密數(shù)據(jù)的加法運(yùn)算，但密鑰管理過于復(fù)雜。建議使用基于同態(tài)函數(shù)的算法來處理加密數(shù)據(jù)，但是有資料認(rèn)為這種函數(shù)能夠通過解線性方程組來破解。

最近，Dawn Xiaodong Song提出使用序列加密(stream cipher)方法加密數(shù)據(jù)，實(shí)現(xiàn)對(duì)加密數(shù)據(jù)的搜索。存儲(chǔ)時(shí)，它采用序列密碼算法把每個(gè)“詞”(word)與隨機(jī)發(fā)生器所產(chǎn)生的，隨機(jī)數(shù)進(jìn)行位異或，結(jié)果存儲(chǔ)在加密的文件中，查詢時(shí)，把查詢?cè)~與密文異或，然后與隨機(jī)數(shù)比較，以確定文件中是否包含該詞，這種方法簡(jiǎn)單，幾乎不增加額外存儲(chǔ)空間，運(yùn)算速度快，但是，對(duì)數(shù)據(jù)庫中存儲(chǔ)數(shù)據(jù)的加密一般不采用序列密碼算法。

Hankan HacijumusuoJ提出基于客戶機(jī)/服務(wù)器(C/S)對(duì)加密數(shù)據(jù)進(jìn)行查詢的一種方法。該方法使用一些函數(shù)對(duì)需加密的數(shù)據(jù)建立索引，并把索引存儲(chǔ)在服務(wù)器中的加密數(shù)據(jù)庫，從而在查詢時(shí)，可以利用加密數(shù)據(jù)庫中的索引，實(shí)現(xiàn)對(duì)加密數(shù)據(jù)的范圍查詢（如：>．<）。但是，這種方法并不適合對(duì)其它類型的數(shù)據(jù)建立索引，比如說字符申數(shù)據(jù)，因?yàn)樽址當(dāng)?shù)據(jù)查詢與數(shù)值型數(shù)據(jù)查詢的模式不同，字符串?dāng)?shù)據(jù)查詢分為精確匹配查詢（如，=）和模糊匹配查詢(如tlike)。對(duì)于精確匹配查詢，這種方法是有效的，但是對(duì)于模糊匹配查詢，這種方法顯得無能為力。

二、加密字符串?dāng)?shù)據(jù)存儲(chǔ)與查詢的體系結(jié)構(gòu)

數(shù)據(jù)庫加密的方式很多，有基于應(yīng)用程序、DBMS和操作系統(tǒng)，也可以由應(yīng)用程序、DBMS和操作系統(tǒng)相互共同完成。我們選擇在商用數(shù)據(jù)庫管理系統(tǒng)和應(yīng)用程序之間增加一層軟件，即加密／解密層，實(shí)現(xiàn)對(duì)加密數(shù)據(jù)的存儲(chǔ)與查詢。這樣可以不用對(duì)商用DBMS進(jìn)行修改，也無須對(duì)應(yīng)用程序修改，具有很好的實(shí)用性。加密字符申數(shù)據(jù)存儲(chǔ)與查詢的體系結(jié)構(gòu)如圖1所示。

在圖1的加密/解密層中，元數(shù)據(jù)是一些函數(shù)映射規(guī)則。用來修改存儲(chǔ)和查詢語句，存儲(chǔ)時(shí)，除了加密數(shù)據(jù)外，還通過這些規(guī)則修改soL語句，存儲(chǔ)加密數(shù)據(jù)的特征值。查詢時(shí)，通過這些規(guī)則修改查詢語句，得到對(duì)加密數(shù)據(jù)查詢的soL語句。加密和解密是由加密／解密函數(shù)來實(shí)現(xiàn)對(duì)機(jī)密信息列進(jìn)行加密和解密的功能模塊。

三、存儲(chǔ)和查詢

1、加密關(guān)系模式(ERS．Encrypted Relatlon Schema)

對(duì)于傳統(tǒng)數(shù)據(jù)庫中每個(gè)關(guān)系模式R(Xi，…．Xr．…．Xn)。其中，Xr為需要加密的字符串字段，以加密關(guān)系模式RE(X1E，…．XrE．…．Xn，A(xr))存儲(chǔ)，其中，RE中XrE是對(duì)R中Xr加密的結(jié)果，即XrE=E(xr)IA(X，)是對(duì)R中Xf通過特征函數(shù)轉(zhuǎn)換后新增的附加字段，其余的列與R中的列相同。

2、特征函救字符函數(shù)(Alphabet Functlon)

定義1、設(shè)有一函數(shù)A: sl→s2．其中sl和s2為兩字符串，如果s2是由sl中不重復(fù)的字符組成1，并且s2中的字符按照一定大小順序排列2。則我們稱函數(shù)A為字符函數(shù)，例如：字符串sl為Chess basketball，則s2 -A(sl)(abcehklst)。 定義2、設(shè)數(shù)據(jù)庫中關(guān)系模式R(Xi，…．Xr，…．Xn)，加密后對(duì)應(yīng)關(guān)系模式為RE(X1E，…．XrE．…．Xn，A(xr))。其中，A是字符函數(shù)，我們稱A(Xr)為關(guān)系RE的字符字段。

3、查詢算法 算法1

第一階段：粗糙查詢(Coarse Query)階段

(1)利用元數(shù)據(jù)（如字符函數(shù)），調(diào)整SQL語句，首先，把條件語句中的加密字段用字符字段替換l然后，用字符函數(shù)去映射條件字符串I最后，改寫Where子句，只要字符字段包含條件字符串中所有單個(gè)的字符，就返回相應(yīng)記錄。

(2)執(zhí)行已經(jīng)轉(zhuǎn)換的SQL語句，返回滿足條件的記錄，并拋棄字符字段。

第二階段：精確查詢(Refined Query)階段

(1)解密第一階段已經(jīng)過濾的記錄，存放到數(shù)據(jù)庫中的一個(gè)臨時(shí)表。

(2)調(diào)整SQL語句，把原始SQL語句中的關(guān)系表用臨時(shí)表替換。

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

4、分析

（1）算法1的查詢正確性

定理1(算法1的查詢正確性)：利用算法1對(duì)加密數(shù)據(jù)查詢時(shí)，查詢處理的結(jié)果是正確的。 證明：從兩個(gè)方面考慮，一方面，符合查詢條件的記錄不會(huì)被過濾掉，任意一記錄，如果需加密的字段包含查詢條件的字符串，加密后，其對(duì)應(yīng)的字符字段必然包括條件字符串的所有單個(gè)字符，根據(jù)算法1的第一階段步驟，此記錄是不會(huì)被過濾掉，在第二階段查詢中，加密字段被解密后，也必然包括條件字符串，所以也不會(huì)過濾掉。另一方面，不符合查詢條件的記錄一定被過濾掉，這個(gè)比較簡(jiǎn)單，在算法1的第一階段查詢處理，由于根據(jù)字符字段來過濾記錄，可能包括一些不滿足條件的記錄，但經(jīng)過第二階段查詢處理，這些不滿足條件的記錄一定被過濾掉，所以說查詢處理的結(jié)果是正確的。

（2）安全性

在加密關(guān)系模式中，對(duì)機(jī)密信息列進(jìn)行加密處理來保證其安全性。但是，其對(duì)應(yīng)的字符字段中包含機(jī)密信息字段出現(xiàn)過的單個(gè)字符，盡管對(duì)單個(gè)字符進(jìn)行重新排序，打亂原來順序，仍然給攻擊者泄漏一些信息，容易實(shí)施已知明文攻擊和統(tǒng)計(jì)攻擊。 為進(jìn)一步保證安全，我們選擇基于中國剩余定理(CRT，Chinese remainder theorem)對(duì)字符字段進(jìn)行加密。這種加密模式能夠很好防止已知明文攻擊和統(tǒng)計(jì)攻擊，并且性能好，特別是解密的速度相當(dāng)快，只需要進(jìn)行一次模運(yùn)算，而且不增加額外存儲(chǔ)空間。但是這種加密方法的安全性與一些成熟的算法（如AES，DES）相比，還是有許多不足之處，所以我們并不用這種方法對(duì)機(jī)密信息字段直接進(jìn)行加密。使用這種方法對(duì)字符字段加密后，如果攻擊者需要從字符字段來獲取機(jī)密信息，除了破譯CRT加密外，還得從字符字段來推斷機(jī)密信息，這無疑增加了攻擊者的難度。

（3）問題

在第一階段的粗糙查詢中，當(dāng)機(jī)密信息字段包含不同字符個(gè)數(shù)越多。ERS中字符字段包含字符個(gè)數(shù)就越多，那么在第一階段粗糙查詢中，被過濾的記錄越少，在第二階段查詢中需要解密的記錄越多，這樣會(huì)導(dǎo)致查詢的性能下降。一種極端的情形是，需要加密的機(jī)密信息宇段包含所有的字符，則ERS中字符字段也包含所有字符，那么通過第一階段的粗糙查詢后，將返回所有的記錄，不會(huì)起到任何過濾作用。 我們經(jīng)常發(fā)現(xiàn)soL查詢語句的條件字符串往往包含重復(fù)的字符，以此為前提，在下一節(jié)提出一種改進(jìn)的方法，能夠在第一階段粗挺查詢中過濾掉更多無關(guān)的記錄，更大程度改善查詢性能。

四、改進(jìn)的存儲(chǔ)和查詢

1、改進(jìn)的加密關(guān)系模式(IERS，Improved Encrypted Rela-tional Schema)

在ERS的加密關(guān)系模式RE(X1E，…．XrE．…．Xn，A(xr))中，增加一個(gè)字段F(Xr>，F(xiàn)(Xr)是對(duì)R中Xr，通過頻率函數(shù)(Frequency Function)映射后產(chǎn)生的。

2、特征函數(shù)2：頻宰函數(shù)(Frequency Function)

定義3、設(shè)s是來自字符表∑={a1，a2，…，am）的一字符串，nl是aj在s中出現(xiàn)的次數(shù)3，其中l(wèi)≤i≤m．a(chǎn)i是按順序排列。1≤ni<10，我們定義頻率函數(shù)為： F(s）=[n1，n2，…．nm] 例如，字符串s為Chessbasketball，則F(s>=[2.2.1.2.1.1．2,3,]。

定義4、設(shè)數(shù)據(jù)庫中關(guān)系模式R(X1，…，Xr，…，Xn)。加密后對(duì)應(yīng)關(guān)系模式為RE(X1E，…．XrE．…．Xn，A(xr))。其中，F(xiàn)是頻率函數(shù)，我們稱F(Xr)為關(guān)系RE的頻率字段。

3、改進(jìn)的查詢算法

算法2、第一階段：粗糙查詢階段

(1)利用元數(shù)據(jù)（如字符函數(shù)和頻率函數(shù)）調(diào)整SQL語句。除了進(jìn)行算法1中的調(diào)整方法外，還應(yīng)在where子句后面增加頻率字段形成的過濾條件，使得條件字符串中每個(gè)字符的頻率應(yīng)少于或等于字符字段中相應(yīng)字符的頻率。

(2)執(zhí)行已經(jīng)轉(zhuǎn)換過查詢條件的soL語句，返回過濾后部分記錄，并拋棄字符字段和頻率字段。

第二階段、精確查詢階段，與算法1-致。

4、分析

（1）算法2的查詢正確性

定理2（算法2的查詢正確性）利用算法2對(duì)加密數(shù)據(jù)查詢時(shí)，查詢處理的結(jié)果是正確的。

證明：與定理l的證明方法一樣，也從兩個(gè)方面考慮，一方面，符合查詢條件的記錄不會(huì)被過濾掉。由定理1可知，符合查詢條件的記錄不會(huì)被字符字段被過濾掉。同樣地，任意一條記錄，如果需加密的字段包含查詢條件的字符串，加密后，其對(duì)應(yīng)的頻率字段中各字符的頻率必然大于或等于條件字符串中相應(yīng)字符的頻率，根據(jù)算法2的第一階段步驟，此記錄是不會(huì)被過濾掉，在第二階段查詢中，加密字段被懈密后，也必然包括條件字符串，所以也不會(huì)過濾掉。另一方面，不符合查詢條件的記錄一定被過濾掉，第一階段查詢處理，由于根據(jù)字符字段和頻率字段來過濾記錄，包括一些不滿足條件的記錄，但經(jīng)過第二階段查詢處理，這些不滿足條件的記錄一定被過濾掉，所以說查詢處理的結(jié)果是正確的。

（2）安全性

改進(jìn)的加密關(guān)系模式(IERS)既存儲(chǔ)機(jī)密信息所包含的字符，又存儲(chǔ)各字符在機(jī)密信息出現(xiàn)的頻率，這無疑給攻擊者帶來更大的便利，我們還是采取上一節(jié)的方法對(duì)字符字段和頻率字段進(jìn)行基于CRT加密，以保證其安全性。在lERS中進(jìn)行粗糙查詢時(shí)，對(duì)頻率字段不必全部解密，只有當(dāng)記錄的字符字段滿足查詢條件時(shí)，才會(huì)進(jìn)一步使用頻率字段進(jìn)行過濾查詢，這樣能夠在一定程度提高系統(tǒng)的性能。

五、實(shí)驗(yàn)與性能分析

本文提出兩階段查詢方法的關(guān)鍵之處在于第一階段粗糙查詢的過濾效率，如果第一階段過濾效率好，那么第二階段只需解密少量的記錄，反之，則需要解密較多記錄，如果需要解密較多記錄，則此方法的意義則不大。在實(shí)驗(yàn)中，我們驗(yàn)證了此方法的可行性．實(shí)驗(yàn)所使用的數(shù)據(jù)表為employee (no,name．s_infor，age，sex)．有100萬條數(shù)據(jù)，使用的加密算法是safer++。需要加密的字段為s，Lnfor．SQL語句為select* from employee where s_infor like條件字符串，實(shí)驗(yàn)環(huán)境為Windows NT操作系統(tǒng)，SQL Server 2000數(shù)據(jù)庫服務(wù)器。CPU為P4 2GHz，內(nèi)存為512MB。我們做兩個(gè)實(shí)驗(yàn)，分別為：

(1)比較本文所采取方法和先解密后查詢方法的時(shí)間代價(jià)。

(2)對(duì)IERS進(jìn)行測(cè)試，分別得到字符字段和頻率字段過濾記錄的效果。

1、實(shí)驗(yàn)1與先解密后查詢方法的性能比較

在第一個(gè)實(shí)驗(yàn)中，分析各種查詢方法對(duì)加密數(shù)據(jù)表查詢所花費(fèi)的時(shí)間代價(jià)。

圖2(a)和圖2(b)分別顯示需加密字符串長(zhǎng)度和需加密記錄數(shù)不同時(shí)，各種方法的查詢代價(jià)，通過比較，我們發(fā)現(xiàn)，與先解密后查詢方法相比，本文所采取的方法在性能上提高50%以上。這主要是因?yàn)閟afer++算法解密速度慢，所花費(fèi)的時(shí)間大約是查詢數(shù)據(jù)所花費(fèi)時(shí)間的12倍，是CTR解密所花費(fèi)時(shí)間的10倍。查詢加密數(shù)據(jù)的主要代價(jià)花費(fèi)在數(shù)據(jù)的解密上，而本文所采取的方法正是盡可能減少解密的記錄數(shù)，從而使得查詢性能得以提高，我們?cè)谙乱粋€(gè)實(shí)驗(yàn)進(jìn)一步分析采用字符字段和頻率字段所起到的過濾效果，以便清晰了解所減少的解密記錄數(shù)。

2、實(shí)驗(yàn)2 附加字段過濾的效果

在實(shí)驗(yàn)2中，我們首先測(cè)試Where子句中條件字符串長(zhǎng)度的變化對(duì)字符字段過濾效率的影響，圖3(a)顯示查詢的結(jié)果，不同折線表示需加密字段的長(zhǎng)度，我們可以看到：

(1)隨著條件字符串長(zhǎng)度的增加，返回的記錄越少。原因是條件字符串長(zhǎng)度增加，包含不同的字符個(gè)數(shù)相應(yīng)增加，那么加密數(shù)據(jù)庫中字符字段與之匹配的記錄越少，所以返回的記錄越少。

(2)隨著需加密字段的長(zhǎng)度增加，返回的記錄越多。原因是加密字段的長(zhǎng)度增加，對(duì)應(yīng)的字符字段包含的字符個(gè)數(shù)相應(yīng)增加，那么與條件字符串匹配的記錄越多，所以返回的記錄越多。

然后根據(jù)頻率字段再進(jìn)行過濾，假設(shè)Where子句中條件字符串只有一個(gè)字符的頻率為2，過濾的結(jié)果見圖3(b)。我們看到：隨著需加密字段值長(zhǎng)度的增加，返回的記錄越多。原因是隨著需加密字段值長(zhǎng)度的增加，對(duì)應(yīng)的頻率字段包含重復(fù)字符個(gè)數(shù)相應(yīng)增多，那么條件字符串各字符的頻率與頻率字段值匹配的記錄越多，所以返回的記錄越多。

圖3(c)給出在字符字段和頻率宇段的共同過濾下，所返回的記錄百分比，不同折線表示需加密字段的長(zhǎng)度。soL語句中條件字符串有一個(gè)字符的頻率為2。我們可以看到，返回的記錄百分比在2～12%，過濾效果相當(dāng)好。

admin

收藏 海報(bào)分享