廖祥宇，鄭明輝，朱小強(qiáng)

(湖北民族大學(xué) 信息工程學(xué)院，湖北 恩施 445000)

隨著計(jì)算機(jī)的飛速發(fā)展，越來越多的人將資源放置數(shù)據(jù)庫中[1]，同時(shí)為了敏感數(shù)據(jù)的安全性，許多人都會(huì)將明文進(jìn)行不同程度的加密，雖然能在一定程度上保證自身敏感數(shù)據(jù)不被竊取，但也極大地降低了密文檢索時(shí)的效率，不能滿足現(xiàn)在高效率的需求.2012年李向前等[2]提出了Blum-Goldwasser概率密碼體制的一種改進(jìn)方案，降低了密文的膨脹率問題.2014年陳成鋼[3]提出了一種確定的背包公鑰密碼體制的破譯算法，利用公開密鑰的超可達(dá)性，直接由公開密鑰破譯得到解密密鑰，從而達(dá)到破譯密文的目的.常見的數(shù)據(jù)庫數(shù)據(jù)索引可以分為以下4類：① 基于文件的索引技術(shù).經(jīng)典算法有DES、AES[4]等算法.這種索引方法相對簡單,但是缺點(diǎn)是這種方法需要是將全部文件進(jìn)行搜索匹配，檢索速率低，不適合大數(shù)據(jù)的數(shù)據(jù)庫.② 基于記錄的索引技術(shù).相比于打包式的檢索，該技術(shù)有了顯著的提高.然而缺點(diǎn)就是用戶僅針對某條記錄中的某個(gè)字段檢索時(shí)，必須對整條記錄進(jìn)行檢索處理.③ 子密鑰索引技術(shù).由David等[5]提出，理論基礎(chǔ)是中國的剩余定理[6],解決了檢索時(shí)對整條記錄檢索的缺陷.然而，缺陷就是檢索時(shí)需要對每條記錄生成索引，過程煩瑣.④ 基于全字段的索引技術(shù).由于其粒度好，適應(yīng)性和靈活性都比前者好很多.但是其缺點(diǎn)是其檢索的基本單位是數(shù)據(jù)段，每一個(gè)字段都有一個(gè)索引，若是有M條記錄，每條記錄有N個(gè)字段，當(dāng)M和N都很龐大的時(shí)候，檢索某一字段時(shí)也需要M×N的時(shí)間，檢索的效率反而降低了.

以上4種常見的數(shù)據(jù)庫索引技術(shù)都實(shí)現(xiàn)了對數(shù)據(jù)的檢索，但是都有一個(gè)共同的缺點(diǎn)就是不能較靈活、快速地對數(shù)據(jù)進(jìn)行檢索以提高效率.為克服上述方案的不足，提出了一種基于Paillier算法[7]的低頻分詞密文檢索技術(shù)(a low frequency ciphertext retrieval technique based on paillier algorithm，LFPR)，該方案在保證滿足用戶檢索需要的同時(shí)，能有效提高密文的檢索效率.

圖1 整體流程Fig.1 Overall flow chart

表1 低頻分詞top10Tab.1 Top10 low-frequency segmentation words

表2 表Ti的存儲(chǔ)格式Tab.2 Storage format of table Ti

1 基于Paillier算法的低頻分詞密文檢索算法

在方案提出之前，首先利用Jieba分詞技術(shù)[8]將明文m按段落進(jìn)行分詞操作，利用權(quán)重選取出頻率最低的10個(gè)分詞，根據(jù)實(shí)際需要選擇其中一個(gè)分詞，作為后續(xù)的索引；然后利用Utf-8將漢字明文轉(zhuǎn)碼變成字符串類型并通過Paillier算法將轉(zhuǎn)碼后的數(shù)據(jù)進(jìn)行加密得到密文Cipertext；最后將密文數(shù)據(jù)存放至數(shù)據(jù)庫YmSql中，形成表結(jié)構(gòu)并通過最初確定的分詞建立索引，實(shí)現(xiàn)快速檢索.整體流程圖如圖1所示.

1.1 預(yù)備知識(shí)

1) Jieba分詞技術(shù).Jieba分詞技術(shù)是針對中文的概率語言模型分詞，其本身具有一個(gè)名為dict.txt的詞典，該詞典擁有20 000多個(gè)中文字詞，每一個(gè)字詞都有根據(jù)訓(xùn)練語料統(tǒng)計(jì)的詞頻和詞性.該技術(shù)涉及Trie樹[9]、有向無環(huán)圖(DAG)[10]、動(dòng)態(tài)規(guī)劃、隱馬爾可夫模型(HMM)[11]以及維特比(Viterbi)等多種算法[12].由自帶dict.txt的詞典生成Trie樹實(shí)現(xiàn)高效率的詞圖掃描，將所有可能的切分情況構(gòu)建有向無環(huán)圖(DAG)；由生成的DAG計(jì)算最大概率，動(dòng)態(tài)規(guī)劃查找最優(yōu)路徑，得到基于詞頻的最優(yōu)分詞組合；對于dict.txt詞典沒有登記的詞，采用隱馬爾可夫(HMM)模型來預(yù)測分詞.

2) Utf-8編碼.Utf-8是PowerBuilder的函數(shù)，該函數(shù)將數(shù)據(jù)字符串轉(zhuǎn)換為Utf-8編碼，并返回編碼后的字符串，利用該函數(shù)將漢字轉(zhuǎn)碼為相對應(yīng)的字符串，最后利用Paillier算法將轉(zhuǎn)碼后的明文數(shù)據(jù)進(jìn)行加密.

3) Hash散列函數(shù).Hash散列函數(shù)就是把任意長度的輸入，通過散列算法，變換成固定長度的輸出，該輸出就是散列值，不同的輸入其散列的值也不相同，具有唯一性.

1.2 低頻分詞的選取

首先Jieba算法將明文進(jìn)行分詞操作，利用權(quán)重計(jì)算選取出頻率最低的10個(gè)分詞，結(jié)果如表1所示.根據(jù)實(shí)際需要選擇其中一個(gè)分詞作為該段的索引，同時(shí)確保每段選取的都不相同，這樣既保證了選取的分詞是出現(xiàn)頻率最低的且選擇的分詞具有唯一性，最后通過分詞索引找到的段落也具有唯一性.測試明文鏈接為：http://cpc.people.com.cn/xuexi/n/2015/0717/c397563-27322232.html.

1.3 基于Paillier算法的明文加密

1.4 建立數(shù)據(jù)庫表字段及索引

完成全部數(shù)據(jù)的加密后，將加密后的數(shù)據(jù)導(dǎo)入數(shù)據(jù)庫中.首先為了保證數(shù)據(jù)解密后的自然語言是完整且正確的，將數(shù)據(jù)以自然段落劃分為標(biāo)準(zhǔn)生成表字段，根據(jù)明文自然段的多少確定表字段T1,T2,…,Tn(1≤i≤n)，每一個(gè)表字段中都有Snumer、Scipertext、Shash三列組成，其中Shash是每個(gè)漢字出現(xiàn)的位置編號(hào)；Scipertext是通過Paillier算法加密得到的密文；Shash是Snumber和Scipertexi相加計(jì)算的結(jié)果，并將Shash作為索引值，每張Ti表只有一個(gè)Hi作為該表的索引.假設(shè)n=517，g=123,r=59.則加密后的數(shù)據(jù)庫存儲(chǔ)表Ti結(jié)構(gòu)如表2所示.

2 實(shí)驗(yàn)仿真

借助PyCharm開發(fā)環(huán)境和Mysql2008R2數(shù)據(jù)庫環(huán)境，采用文章所提出的檢索算法對密文數(shù)據(jù)進(jìn)行檢索并與經(jīng)典的AES算法和全字段加密算法對比.

圖2 檢索結(jié)果Fig.2 Retrieval results

圖3 解密結(jié)果Fig.3 Decryption results

圖4 字?jǐn)?shù)對檢索時(shí)間的影響Fig.4 The influence of word count on retrieval time

2.1 檢索結(jié)果驗(yàn)證

通過對建立的索引進(jìn)行查詢，查詢結(jié)果如圖2所示.通過查詢結(jié)果可以看出，通過索引Hi查詢，可以直接定位到密文所在的位置，因?yàn)镠i是Hash索引的結(jié)果，根據(jù)Hash散列函數(shù)的特性可以確定該索引結(jié)果是唯一的，通過Snumber將密文按順序排序，利用n解密密文得到Utf-8，最后Uif-8將轉(zhuǎn)碼為明文m，解密結(jié)果如圖3所示.綜上，該的檢索技術(shù)是可以實(shí)現(xiàn)并且檢索結(jié)果具有唯一性.

2.2 字節(jié)長度與檢索時(shí)間

在搭建好的實(shí)驗(yàn)環(huán)境下，通過輸入不同字節(jié)的數(shù)據(jù)，對密文檢索時(shí)間進(jìn)行對比驗(yàn)證，得到字節(jié)長度與檢索時(shí)間之間的關(guān)系，如圖4所示.

測試數(shù)據(jù)選取了100、500、1 000三個(gè)密文字?jǐn)?shù)節(jié)點(diǎn)進(jìn)行測試，通過圖4可以看出，在密文字?jǐn)?shù)較少時(shí)，檢索速率較快，但隨著密文字?jǐn)?shù)增多，檢索的時(shí)間也隨之增加；密文字?jǐn)?shù)在500字以內(nèi)時(shí)，檢索時(shí)間大致相同，但隨著密文字?jǐn)?shù)的不斷增加，本文算法的檢索時(shí)間較其他兩種算法的檢索時(shí)間有明顯的提高.密文長度越長，密文的檢索時(shí)間也會(huì)相應(yīng)地增加.

3 結(jié)論

提出了一種基于Paillier公鑰密碼體制在數(shù)據(jù)庫的改進(jìn)與分析的算法，首先將Paillier算法、Jieba算法、Hash算法和數(shù)據(jù)庫索引技術(shù)有效結(jié)合，利用Paillier算法對整個(gè)明文進(jìn)行加密操作，利用p,q大素?cái)?shù)的乘積n確保數(shù)據(jù)的安全性，然后結(jié)合Jieba算法和算法得到低頻分詞作為索引，最后將密文存儲(chǔ)在數(shù)據(jù)庫中，利用索引查詢密文.實(shí)驗(yàn)結(jié)果表明，本文提出的算法能夠有效地增加數(shù)據(jù)在數(shù)據(jù)庫中的安全并且降低了在數(shù)據(jù)庫中對整個(gè)密文進(jìn)行檢索，提高了檢索效率.該算法的不足之處在于:當(dāng)檢索內(nèi)容過長時(shí)，運(yùn)行時(shí)間明顯變長，只能應(yīng)用于字段較少的內(nèi)容.該問題是以后研究的重點(diǎn).