基于加密數(shù)據(jù)庫的快速查詢方法研究

◆王福超 牛長春

（華北水利水電大學(xué)信息工程學(xué)院 河南 450046）

1 引言

隨著無線網(wǎng)絡(luò)以及智能手機的普及，人們在生活、工作和學(xué)習(xí)中使用著越來越多的網(wǎng)絡(luò)應(yīng)用。尤其是近幾年，各種訂票軟件、訂餐軟件、租房軟件成為人們?nèi)粘Ｉ畹某Ｓ闷贰Ｓ脩粼谑褂眠@些產(chǎn)品的同時，產(chǎn)生了大量的數(shù)據(jù)存儲在企業(yè)的數(shù)據(jù)庫中。目前大多數(shù)企業(yè)為了減少維護成本，會選擇將收集到的數(shù)據(jù)存儲到云數(shù)據(jù)庫中，讓第三方代替維護和管理，這就造成了不可避免的安全隱患。因為數(shù)據(jù)庫的管理人員屬于可靠但好奇的角色，在對數(shù)據(jù)庫進行管理時，不可避免地要訪問到企業(yè)內(nèi)部重要資料、收集用戶的數(shù)據(jù)，并具有對數(shù)據(jù)的查看權(quán)和修改權(quán)，即使排除數(shù)據(jù)庫管理人員對數(shù)據(jù)庫安全的威脅因素，仍存在當(dāng)數(shù)據(jù)庫被黑客攻擊后造成數(shù)據(jù)泄漏的風(fēng)險。

為保證用戶的隱私安全，排除來自企業(yè)內(nèi)部的威脅因素，目前最常用也是最可靠的方法之一是將關(guān)鍵信息加密后再向數(shù)據(jù)庫中存儲。但明文信息被加密成密文后就失去了自身的屬性，尤其是當(dāng)數(shù)值型數(shù)據(jù)被加密后，無法直接進行比較和運算，當(dāng)需要進行這些操作時，密文需要被全部解密成明文后才能完成，這將嚴重耗費系統(tǒng)資源。針對這種問題，近幾年，有不少相關(guān)的新技術(shù)相繼被學(xué)者們提出。如保持有序加密技術(shù)、同態(tài)加密技術(shù)、密文索引查詢技術(shù)等，但能夠?qū)⑦@些技術(shù)綜合到一個系統(tǒng)實現(xiàn)的還不多。本文主要在關(guān)系型數(shù)據(jù)庫中的密文數(shù)據(jù)提供高效查詢，并提供添加、更新、刪除數(shù)據(jù)和密鑰管理的功能。根據(jù)加密數(shù)據(jù)庫的缺點，將結(jié)合較新的技術(shù)達到能快速對數(shù)據(jù)執(zhí)行加解密，且加密強度足夠高。對密鑰管理靈活高效，不能占用系統(tǒng)大量的資源，要保證密鑰的安全性，數(shù)據(jù)在加密存儲后，支持對密文的快速查詢。支持多種常用的查詢語句。如等值查詢、范圍查詢等，同時應(yīng)支持部分函數(shù)查詢，并實現(xiàn)快速查詢。

2 研究現(xiàn)狀

目前，針對數(shù)據(jù)庫加密的研究主要集中在加密技術(shù)的選擇、加密算法的改進以及對密鑰的安全管理等方面。2016 年，黃保華等人[1]分別針對字符型和數(shù)值型數(shù)據(jù)提出了一種基于索引技術(shù)的二階段查詢方案，該方案的設(shè)計思路是從時間性能和過濾性能兩方面來提高查詢效率。對于數(shù)值型數(shù)據(jù)，分別使用單調(diào)和非單調(diào)函數(shù)確保索引的過濾性和安全性。對于字符型數(shù)據(jù)，通過構(gòu)造敏感字符信息矩陣，達到過濾不需要的密文數(shù)據(jù)以減少解密時間的效果。但對于使用該方案帶來的存儲索引空間消耗較大的問題，作者沒有給出有效的解決方案。2017 年，王偉等人[2]使用MapReduce 編程框架并結(jié)合已有的CryptDB 加密系統(tǒng)的工作原理，設(shè)計了一款基于B/S 架構(gòu)的并行密文數(shù)據(jù)庫系統(tǒng)。作者的設(shè)計思路是將云計算技術(shù)與可搜索加密技術(shù)融合使用，使用任務(wù)調(diào)度算法來產(chǎn)生適當(dāng)?shù)娜蝿?wù)分配策略，使加密和存儲大規(guī)模數(shù)據(jù)的性能和速度得到明顯提升。S.Muthurajkumar 等人[3]提出了一種將時間約束與Map reduce 算法相結(jié)合的時態(tài)安全云圖約簡算法，以及本文新提出的鏈式Hill 密碼加密算法。該算法的主要優(yōu)點是減少了處理時間，有效地保證了系統(tǒng)的安全性。Sha Ma 等人[4]提出了標準模型中第一個使用光滑投影哈希函數(shù)（SPHF）的泛型PCE，并證明了它的s-priv1-cca 安全與當(dāng)前的斷開安全無關(guān)。本文設(shè)計了支持快速查詢的加密模型，并實現(xiàn)了模型中使用的三種加密算法，將輸入的明文數(shù)據(jù)使用三種算法加密后分別存儲到數(shù)據(jù)庫中，查詢時該模型可根據(jù)查詢語句的類型來匹配數(shù)據(jù)庫中相應(yīng)的密文數(shù)據(jù)，進而支持在加密數(shù)據(jù)庫中可直接對密文進行比較和運算，提高對加密數(shù)據(jù)庫的查詢速度。

3 模型設(shè)計

支持速查的加密模型設(shè)計參考了CryptDB 系統(tǒng)的洋蔥加密模型[5]，洋蔥模型具有集多種算法于一體，支持快速查詢并能確保加密數(shù)據(jù)足夠安全的優(yōu)秀性能，但也顯得有些臃腫。本人將其簡化后設(shè)計成新的加密模型為系統(tǒng)使用，如圖1 所示，分別為確定加密模型（DET 模型）、保序加密模型（OPE 模型）和同態(tài)加密模型（Hom 模型），這些模型的使用能顯著提高系統(tǒng)對密文數(shù)據(jù)的查詢速度。此外，為提高數(shù)據(jù)安全性，分別在確定加密層和保序加密層上各包裝一層隨機加密模型（RND 模型）。并將這三種模型結(jié)合起來使用，其模型的功能介紹如下。

圖1 系統(tǒng)使用的加密模型

3.1 基礎(chǔ)模型簡介

確定加密模型（DET 模型），該模型在設(shè)計中使用到了兩層加密，里層使用的是確定加密層，外層包裝上隨機加密層。DET模型的特點是相同的明文V 通過算法加密后的值C 也是確定的。使用此模型可加快等值查詢的速度。保序加密模型（OPE 模型）該模型用到的算法是文獻[6]中提出的非線性保序索引算法（OPE算法），該算法能滿足加密后的索引數(shù)據(jù)仍能保持明文順序的需求。如明文V1＜ V2，則將明文加密后的索引值I1＜ I2。利用這種特性可以直接在密文上完成明文關(guān)系的比較，提高查詢效率。同態(tài)加密模型（Hom 模型），模型主要負責(zé)加密用戶表中的數(shù)值型數(shù)據(jù)，其使用的算法是文獻[7-8]提出的同態(tài)加密算法（Hom 算法），此算法的特點是，加密后得到的密文分組可直接參與計算。因此我們可以直接使用MySql 內(nèi)置的聚集函數(shù)，從而提高函數(shù)查詢的速度。

3.2 隨機加密模型（RND 模型）

RND 模型的主要作用是包裝DET 模型和OPE 模型。作為強加密層，它能有效隱藏密文可能會暴露出來的明文特征，提高被包裝模型處理數(shù)據(jù)的安全性。該模型使用的算法簡稱RND 算法，具體使用的是數(shù)據(jù)庫中內(nèi)置的AES 算法，為方便操作，把每條記錄的行號和主密鑰作為算法密鑰，以表名和字段名為條件執(zhí)行加解密操作。該模型還有個特點是可以動態(tài)的包裝和剝離，當(dāng)用戶通過系統(tǒng)向數(shù)據(jù)庫中存入密文數(shù)據(jù)C 后，還需要把C 當(dāng)作參數(shù)使用此模型處理成新的密文數(shù)據(jù)后再存儲，查詢C 時則把待查詢屬性列的所有數(shù)據(jù)項的RND 層全部剝離，查詢完成再立即對其包裝。使用該模型可保證數(shù)據(jù)一直處于安全狀態(tài)。

4 速查性能測試與分析

為了對模型進行效率評估，我們分別在兩種條件下進行測試。首先在數(shù)據(jù)量大小一定的情況下，使用不同種類的查詢語句，分別測試語句在執(zhí)行過程中各個模塊的詳細耗時情況。其次測試在不同數(shù)據(jù)樣本下，使用相同查詢語句的查詢性能，最后對系統(tǒng)進行綜合評價。

4.1 數(shù)據(jù)庫中數(shù)據(jù)樣本大小確定，執(zhí)行不同類型的查詢語句。

測試條件：表中共2000 條數(shù)據(jù)記錄。

測試語句：select id， tname， tage， tsex from teacher where tname='邢567'；

表1 等值查詢耗時統(tǒng)計表

第三次 15ms 1ms 111ms ＜1ms 141ms 268ms 平均耗時 15.3ms 3.3 122.3 ＜1ms 109.3ms 250.3ms

測試語句：select tname， tage， tsex from teacher where id ＜ 10；

表2 范圍查詢耗時統(tǒng)計表

測試語句：select salary.bsalary，teacher.tname from salary inner join teacher on teacher.id = salary.id where teacher.id = 120；

表3 連接查詢耗時統(tǒng)計表

測試語句：select avg（bsalary） from salary where id ＜ 1000；

表4 函數(shù)查詢耗時統(tǒng)計表

分析表1、4 看出系統(tǒng)在執(zhí)行等值查詢和函數(shù)查詢操作時耗時比較短，分別為250.3ms 和260.7ms。相對從表2、3 中的對比發(fā)現(xiàn)，范圍查詢和連接查詢操作的耗時比較長，分別為460ms和457ms。造成這種現(xiàn)象的原因是：前兩種查詢方式只需將部分確定加密的字段去除隨機層（函數(shù)查詢不需要），且需要解密的密文較少。而后兩者查詢方式中，范圍查詢操作需要對使用了確定加密和保序加密的字段全部去除隨機層，并且需要解密的密文集較大。此外，連接查詢還涉及多表之間的連接，因此耗時較長。

從執(zhí)行過程中各模塊的耗時情況來看，對語句的重構(gòu)操作和執(zhí)行操作花費的時間最短，幾乎在2 毫秒以內(nèi)。獲取元信息操作耗時也比較短，因為其只需要執(zhí)行一條查詢元信息表的語句，將返回的元信息保存即可。最耗時的是隨機加密層的處理操作，因為系統(tǒng)加密粒度是字段級別的，需要對字段中的所有數(shù)據(jù)執(zhí)行加解密操作。

4.2 數(shù)據(jù)庫中數(shù)據(jù)樣本大小不確定，執(zhí)行相同類型的查詢語句，如表5 所示：

表5 不同樣本下的查詢操作耗時表

3000 條 11ms 1ms 157ms ＜1ms 110ms 279ms 1548ms 5000 條 13ms 1ms 377ms ＜1ms 108ms 499ms 3246ms 10000 條 10ms 2ms 455ms ＜1ms 109ms 576ms 6254ms 15000 條 10ms 2ms 609ms ＜1ms 110ms 731ms 12562ms

測試條件：分別有1000 條、3000 條、5000 條、10000 條、20000 條記錄。

測試語句：select * from teacher where id = 656；

根據(jù)表5 可以發(fā)現(xiàn)，查詢操作中耗時最短的依然是sql 語句重構(gòu)操作和執(zhí)行操作，接下來耗時較短的分別是元信息獲取操作和解密并顯示出結(jié)果操作。這些操作的耗時是比較穩(wěn)定的，不會隨著樣本數(shù)量的改變而產(chǎn)生大幅度變化。但對于隨機加密層的處理操作，其耗時是隨著查詢樣本數(shù)據(jù)的增多而增加。

根據(jù)表5 繪制出折線圖如圖3 所示：該圖清晰地顯示出系統(tǒng)查詢耗時與數(shù)據(jù)樣本之間的關(guān)系。從圖中可以看出，在所使用的查詢語句相同的情況下，隨著數(shù)據(jù)表中的數(shù)據(jù)樣本的不斷增大，查詢所耗費的時間也近似呈現(xiàn)出線性增加的趨勢，這反映出本系統(tǒng)具有良好的穩(wěn)定性。與使用普通加密策略的查詢耗時結(jié)果對比，系統(tǒng)具有較快的查詢速度。

圖3 查詢耗時-樣本關(guān)系折線圖

5 總結(jié)

對隱私的保護催生出了數(shù)據(jù)庫加密技術(shù)，而把數(shù)據(jù)加密之后又會顯露出無法對密文直接進行比較和運算，導(dǎo)致查詢速度過慢的問題。通過研究和分析，本人提出了綜合使用索引技術(shù)和同態(tài)技術(shù)將數(shù)據(jù)加密的方案來實現(xiàn)對加密數(shù)據(jù)庫的快速查詢，并設(shè)計了支持速查的安全加密模型。模型中用到的每種算法加密后的數(shù)據(jù)都有各自的特性，將這些密文數(shù)據(jù)分別存儲后，利用數(shù)據(jù)的特性來提高系統(tǒng)對等值查詢、范圍查詢和函數(shù)查詢的查詢速度。