魏占禎，楊亞濤，陳志偉，2

(1.北京電子科技學院 通信工程系，北京 100070;2.西安電子科技大學 通信工程學院，陜西 西安 710071)

目前，由于部分的網(wǎng)絡(luò)數(shù)據(jù)庫大量使用明文來保存用戶密碼，用戶的信息隱私保護面臨著巨大的風險，尤其在數(shù)據(jù)庫中用戶敏感信息的保護與數(shù)據(jù)泄漏的防止正在越來越受到關(guān)注.

相對于單服務(wù)器模式的數(shù)據(jù)庫安全［1］，在網(wǎng)絡(luò)環(huán)境下，數(shù)據(jù)庫中數(shù)據(jù)的安全存儲以及安全檢索目前采用的數(shù)據(jù)加密與身份認證手段，都只是一次性的將明文信息隱藏化［2］，能在一定程度上達到保護隱私數(shù)據(jù)的目的，但隨著用戶與網(wǎng)絡(luò)數(shù)據(jù)庫服務(wù)提供商之間交互信息的增多，隱私信息和身份認證信息很容易因被跟蹤而導致信息泄露［3］.

數(shù)據(jù)庫加密方法可以應用在單機環(huán)境和網(wǎng)絡(luò)環(huán)境下，但存在一個共同的問題，即對于所形成的密文數(shù)據(jù)庫無法進行操作，即對于密文數(shù)據(jù)庫，若要對某些字段進行統(tǒng)計、平均、求和等數(shù)學運算時，必須先對這些字段進行解密運算，然后對明文進行數(shù)學運算，之后再加密.這樣首先增大了時空開銷;其次，在實際應用中，對于某些重要或敏感數(shù)據(jù)，無法滿足用戶對其進行操作但又不能讓用戶了解其中信息的需要.如果在數(shù)據(jù)庫中存儲用同態(tài)加密［4］方式加密的數(shù)據(jù)，就可以實現(xiàn)對密文的檢索和計算.

同態(tài)密碼(homomorphic cryptograph)可認為由Rivest、Adleman等于1978年最早提出的，也稱為保密同態(tài)(private homomorphic)［5］.

Craig Gentry提出的基于理性格的完全同態(tài)算法［6-7］運算效率比較低，雖然許多研究者對該算法進行改進［8-9］，但是在實際應用中仍存在不少困難.

目前，國內(nèi)外對密文數(shù)據(jù)庫存儲與檢索的研究還比較少，至今還沒有看到高效可用的同態(tài)加密數(shù)據(jù)庫密文檢索算法.Yong Zhang等提出一種數(shù)據(jù)庫密文索引策略［10］，通過SQL語句翻譯器將SQL檢索語句轉(zhuǎn)換為對索引的快速匹配.

Yong Zhang還提出一種字符型數(shù)據(jù)密文的分區(qū)索引方法［11］.Lianzhong Liu等提出一種基于 Bloom Filter的數(shù)據(jù)庫索引方法［12］，根據(jù)數(shù)據(jù)庫索引的匹配可將部分不符合檢索條件的數(shù)據(jù)庫記錄排除.Youssef Gahi等［13］在文獻中提出一個利用完全同態(tài)加密技術(shù)對加密數(shù)據(jù)執(zhí)行SQL語句的安全數(shù)據(jù)庫系統(tǒng)，利用Gentry提出的完全同態(tài)算法和文獻［14］中提供的計算方法，運用普通的同態(tài)加密算法實現(xiàn)了對密文數(shù)據(jù)庫的查詢、更新、刪除等操作，但實現(xiàn)效率非常低.

1 密文檢索方案設(shè)計

在網(wǎng)絡(luò)存儲環(huán)境中，為了保護用戶的數(shù)據(jù)安全和防止隱私信息泄露，用戶與數(shù)據(jù)存儲服務(wù)提供商之間多次交互時可以利用密文進行操作，這些數(shù)據(jù)是以密文的形式存在數(shù)據(jù)庫中.常規(guī)的思路是，把明文數(shù)據(jù)記錄加密為密文之后，上傳到網(wǎng)絡(luò)存儲服務(wù)器，需要的時候執(zhí)行對數(shù)據(jù)庫的查詢操作并獲得數(shù)據(jù)記錄.但這樣的思路在數(shù)據(jù)記錄的發(fā)送階段、查詢階段以及接收與解密階段涉及到多個加/解密操作，并且因為在查詢階段，用戶的數(shù)據(jù)被完全打開，處于明文狀態(tài)，也就無法保證用戶隱私數(shù)據(jù)在查詢階段的私密性.所以，采取同態(tài)加密的思路來實施對網(wǎng)絡(luò)環(huán)境中的數(shù)據(jù)進行同態(tài)加密存儲和安全獲取，以便保證在適當增加計算開銷的情況下，確保用戶數(shù)據(jù)的私密性.

1.1 RSA密碼體制的同態(tài)性分析

使用RSA密碼體制在完成加解密運算時，首先選取2 個大素數(shù) p、q，計算 n=pq，φ(n)=(p-1)(q-1);隨機選取一個整數(shù)e要求滿足:1＜e＜φ(n)-1，(e，φ(n))=1，求出 d，0 ＜ d ＜ φ(n)，ed=1 modφ(n).此時，公鑰為(e，n)，私鑰 d;加密過程:c=memodn，解密過程:m=cdmodn.

對于明文m1、m2，采用RSA體制加密后，可以得到所以RSA公鑰密碼體制滿足乘法同態(tài)特性.

舉例:假定RSA的公鑰、私鑰分別為(5 437，189 781)與(49 269)，2個明文信息分別為m1=56 947，m2=64 413，根據(jù)RSA的乘法同態(tài)特性，可以得到:

1.2 數(shù)據(jù)庫中密文檢索協(xié)議構(gòu)造

假定數(shù)據(jù)庫中的數(shù)據(jù)記錄以密文存放，采用的加密算法為RSA，數(shù)據(jù)擁有者O(即提供者)和數(shù)據(jù)獲取者D是同一實體，即數(shù)據(jù)擁有者發(fā)送自己的密文數(shù)據(jù)C到數(shù)據(jù)庫服務(wù)器，自己需要時，再獲取這些數(shù)據(jù).假設(shè)密文C對應的明文是M，選用的具有乘法同態(tài)特性的公鑰密鑰體制可以為目前通用的RSA.

1)向數(shù)據(jù)庫服務(wù)器發(fā)送數(shù)據(jù)

O發(fā)送數(shù)據(jù)M時，可以對M用自己的公鑰進行加密，形成密文C，把C發(fā)送到數(shù)據(jù)庫服務(wù)器;同時，選定 t個 M 對應的關(guān)鍵詞 kw1，kw2，…，kwt，t的選取以能夠恰當表達M的屬性為原則，同時，要考慮到引入的計算量，實際中可以t=3;對t個關(guān)鍵詞分別用t個公鑰進行加密，得到t個密文關(guān)鍵詞ckw1，ckw2，…，ckwt;然后獲得如下乘積:Ckw=ckw1ckw2…Ckwt，把Ckw也一并發(fā)送到數(shù)據(jù)庫中.詳細說明如下:

例如，3個關(guān)鍵詞 kw1，kw2，kw3分別用3個公鑰進行加密:

式中:n是2個大素數(shù)p，q的乘積，n=pq，φ(n)=(p-1)(q-1);Ri是隨機選取的素數(shù)，滿足1＜Ri＜φ(n)-1，(Ri，φ(n))=1;所以，此時可以認為，數(shù)據(jù)擁有者自己采用的RSA加密算法的密鑰(與RSA算法中的公鑰不同，在這里稱他們?yōu)槊荑€)為Ki=(Ri，n)(i=1，2，…，k);

其次，數(shù)據(jù)擁有者把t個密文關(guān)鍵詞ckw1，ckw2，…，ckwt的乘積Ckw=ckw1ckw2…ckwt也一并發(fā)送到數(shù)據(jù)庫.

2)從數(shù)據(jù)庫服務(wù)器獲取數(shù)據(jù)階段.

當D(也就是O)，想從數(shù)據(jù)庫服務(wù)器獲取想要的記錄時，用明文輸入關(guān)鍵詞KW，可以對kw1，kw2，kw3進行聯(lián)合加密，根據(jù)加密算法的乘法同態(tài)特性:E(kw1)E(kw2)…E(kwt)=E(kw1kw2…kwt)，

即ckw1ckw2…ckwt=Ckw;服務(wù)器在數(shù)據(jù)庫中查詢與KW匹配的數(shù)據(jù)記錄，如果匹配的關(guān)鍵詞存在，就提取該記錄.把C以密文形式下載到D，所以當D得到這些密文分片后，就可以得到C.詳細如下:當數(shù)據(jù)獲取者(也就是數(shù)據(jù)擁有者)取定3個檢索的關(guān)鍵字kw1，kw2，kw3后，并根據(jù)數(shù)據(jù)庫中的 R(R=R1R2R3)，就可以對 kw1，kw2，kw3進行聯(lián)合加密:

EPK(kw1kw2kw3)=C≡(kw1kw2kw3)Rmodn，R是k個隨機素數(shù)的乘積R=R1R2…Rk，所以，此時數(shù)據(jù)獲取者所采用的RSA加密算法的公鑰為PK=(R，n)，這也是數(shù)據(jù)擁有者向外公布的RSA加密算法的公鑰.

3)然后利用自己的私鑰即可解密得到明文M.

需要說明的是，上述方案中數(shù)據(jù)擁有者僅僅上傳了Ckw和R到數(shù)據(jù)庫服務(wù)器中，為數(shù)據(jù)獲取者提供一次性多個(例如3個)關(guān)鍵詞的快速檢索;也可以另外把3個關(guān)鍵詞的密文及其公鑰(kw1，R1)，(kw2，R2)(kw3，R3)上傳到服務(wù)器，以便供數(shù)據(jù)獲取者提供單個關(guān)鍵詞的檢索.

通過上述過程，數(shù)據(jù)庫服務(wù)器上存放的是數(shù)據(jù)的密文C和Ckw，也就是說，數(shù)據(jù)的私密性和安全性得到保障;方案利用RSA的乘法同態(tài)特性，提供了t個關(guān)鍵詞的一次性快速檢索，提高了檢索效率.

1.3 帶有隱私保護的同態(tài)密鑰協(xié)商

現(xiàn)在假定，數(shù)據(jù)擁有者O(即提供者)的RSA公私鑰對為(PK0，SK0)，數(shù)據(jù)獲取者D的RSA公私鑰對為(PKD，SKD)，數(shù)據(jù)庫服務(wù)器S的RSA公私鑰對為(PKs，SKs)，則可以設(shè)計如下的同態(tài)密鑰協(xié)商協(xié)議:

1)數(shù)據(jù)擁有者O(即提供者)向服務(wù)器S發(fā)出數(shù)據(jù)上傳請求EPKS(IDO)=(IDO)PKS，IDO是數(shù)據(jù)擁有者O的身份標識(可以是IP或MAC地址，或其他序列號).

2)服務(wù)器S生成一個隨機數(shù)RS并用O的公鑰加密后返回給 O，即 EPKO(Rs)=(IDO+1‖ID‖SRS)PKO，IDS是服務(wù)器S的身份標識(可以是IP或MAC地址，或其他序列號).

3)0用自己的私鑰解密數(shù)據(jù)EPKO(RS)=(ID0+1‖IDS‖RS)PKO，可以得到 RS，同時可以驗證服務(wù)器S的身份是否合法.

4)O生成一個隨機數(shù)R0，然后可以得到用于數(shù)據(jù)上傳的數(shù)據(jù)加密密鑰K=RORS.

5)O用生成的數(shù)據(jù)加密密鑰K，采用對稱加密算法(例如AES)加密要上傳的數(shù)據(jù)Data，即EK(Data).

至此，數(shù)據(jù)的加密上傳已經(jīng)完成，由于數(shù)據(jù)服務(wù)器無法生成數(shù)據(jù)加密密鑰K=RORS，即其無法解密由用戶上傳的數(shù)據(jù)，用戶數(shù)據(jù)的私密性得到了保障.

當數(shù)據(jù)獲取者D檢索到合適的數(shù)據(jù)，打算下載并使用EK(Data)時，可以采取如下思路:

①數(shù)據(jù)獲取者D分別向數(shù)據(jù)擁有者O和數(shù)據(jù)庫服務(wù)器S發(fā)出請求，他們分別返回用數(shù)據(jù)獲取者D的公鑰加密的隨機數(shù)，即

②利用RSA加密體制的乘法同態(tài)特性，數(shù)據(jù)獲取者D做如下運算，然后解密，就可以得到K=RORS.

③用密鑰K，就可以解密得到明文數(shù)據(jù)Data.

1.4 協(xié)議的安全性證明

BAN邏輯是由Burrows等提出的一種基于信仰的邏輯［15］，下面基于BAN邏輯對提出的協(xié)議進行安全性分析.本文提出的協(xié)議主要目的是在三方之間建立起邏輯密鑰，該協(xié)議的初始假設(shè)為:

三方交互協(xié)議的步驟可以形式化為:

4)S?{#Data}EK

見規(guī)則，D可以構(gòu)造K=RORS

由新鮮規(guī)則、看見規(guī)則和4)，可以得到:

與S、D之間的會話公鑰是K”

由上述步驟看出，提出的協(xié)議是安全的.流程實現(xiàn)了安全的密鑰協(xié)商.協(xié)議中，隨機數(shù)的傳輸都是用對方的公鑰進行加密，只有合法接受者的私鑰才能解密數(shù)據(jù)，保障了隨機數(shù)和數(shù)據(jù)的安全性，實現(xiàn)了接收方的不可抵賴性.另外，步驟1)～3)可以看作是一個雙向認證流程，有效防止了中間人攻擊和重放攻擊.

2 方案分析與密鑰獲取性能測試

對所提出的方案進行如下分析:

1)解決了聯(lián)合授權(quán)問題，特別適宜于有三方關(guān)聯(lián)需求的商業(yè)應用場景.方案中，數(shù)據(jù)提供者提供自己的數(shù)據(jù)，數(shù)據(jù)服務(wù)器提供數(shù)據(jù)展示的平臺，數(shù)據(jù)獲取者期望獲得想要的數(shù)據(jù)服務(wù).通過該方案，數(shù)據(jù)獲取者必須在獲得數(shù)據(jù)提供者和服務(wù)器雙方共同授權(quán)的情況下(同時獲得RO和RS)，才能解密得到數(shù)據(jù)Data，即:1)數(shù)據(jù)獲取者可以向數(shù)據(jù)提供者和服務(wù)器雙方支付相關(guān)的費用或發(fā)出請求授權(quán)，以便來獲得想要的數(shù)據(jù)資源和服務(wù);2)也有利于數(shù)據(jù)提供者和服務(wù)器對所擁有的相關(guān)資源進行有效管理和控制.

2)保護了數(shù)據(jù)隱私.由于數(shù)據(jù)服務(wù)器無法生成數(shù)據(jù)加密密鑰K=RORS，即其無法解密由用戶上傳的數(shù)據(jù)，用戶數(shù)據(jù)的私密性得到了保障.

3)減少了計算開銷.在第7)步，數(shù)據(jù)獲取者D只需1次乘法操作和1次解密操作，即可得到K=RORS;即采用方法1(RSA乘法同態(tài)機制)來獲取會話密鑰:

相反，如果不利用RSA的乘法同態(tài)特性，數(shù)據(jù)獲取者D只能方法2來獲取會話密鑰:

需要做2次解密操作和1次乘法操作，即2次解密分別得到RO和RS，再用乘法得到K=RORS.由于RSA的解密操作比較耗時，所以提出的思路提升了解密密鑰的獲取效率.為了驗證這2種情況下獲取密鑰的性能，實施了實驗仿真并進行了效能測試.實驗采用 Openssl密碼算法庫中的 256、512、1 024、2 048 bit RSA生成的密鑰，采用無密文填充的加密方案，實現(xiàn)了基于RSA乘法同態(tài)特性的密鑰獲取效率對比.服務(wù)器環(huán)境為:AMD Athlon(TM)II X2 250 Processor雙核CPU，DDR3 1 333 MHz 2G 內(nèi)存，Windows XP SP3，Visual Studio 2010 Win32 Console Application，其中模擬測試核心部分偽碼如下:

首先，采用512 bit的隨機數(shù)RO和512 bit的隨機數(shù)RS，在RSA模數(shù)n的不同取值(n=256，512，768，1 024，2 048，4 096)情況下，分別采用乘法同態(tài)和不采用乘法同態(tài)的2種RSA算法，對比測試了2種密鑰獲取方式，得到了2種機制情況下的所獲得密鑰K的生成時間對比結(jié)果，如圖1所示.

圖1 RSA算法獲取密鑰的2種方案效率對比Fig.1 The performance comparison between the two encryption key generators based on RSA

由圖1可知，利用乘法同態(tài)所獲取密鑰的時間基本上是不采用乘法同態(tài)的一半，即密鑰獲取效率幾乎提升了50%.

其次，改變隨機數(shù)RO和隨機數(shù)RS的位數(shù)，讓它們分別取值為 64、128、256、512 bit，選取 RSA 的模數(shù)n=1 024 bit，分別采用乘法同態(tài)和不采用乘法同態(tài)的RSA算法，測試了2種密鑰獲取方式，得到了2種機制情況下所獲取密鑰K的計算耗時對比結(jié)果，如圖2所示.

由圖2可知，利用乘法同態(tài)所獲取密鑰的時間基本上也是不采用乘法同態(tài)的一半，即密鑰獲取效率也提升了近50%.同時，從圖2平穩(wěn)的折線中可以明顯看出獲得不同位數(shù)的解密密鑰K所消耗的時間在 2種方法下變換不大.也就是說，獲取1 024 bit的解密密鑰與獲取較短長度的解密密鑰耗時幾乎相當.

圖2 K值進行密鑰獲取的2種方案效率對比Fig.2 Performance comparison between the two encryption key generators based on different size of Keys

3 結(jié)束語

本文以網(wǎng)絡(luò)環(huán)境下數(shù)據(jù)存儲的安全問題綜合分析為切入點，提出了一種新的帶有隱私保護的同態(tài)密鑰協(xié)商方案，保障了用戶在數(shù)據(jù)記錄的發(fā)送階段、查詢階段以及接收階段用戶數(shù)據(jù)的私密性，并對所設(shè)計的協(xié)議進行了安全性證明;對密鑰獲取的性能進行了對比測試，仿真表明，利用RSA的乘法同態(tài)性質(zhì)所獲取密鑰的時間基本上相當于不采用乘法同態(tài)的一半，即數(shù)據(jù)獲取者獲取解密密鑰的效率提升了近50%.本方案為網(wǎng)絡(luò)數(shù)據(jù)庫的數(shù)據(jù)隱私與安全提供了一條有效解決思路.研究基于ECC公鑰密碼體制同態(tài)特性的密文存儲與檢索算法將是本文下一步的研究方向.

［1］CASTAGNOS G，CHEVALLIER M B.Towards a DL-based additively homomorphic encryption scheme［C］//Proceedings of 2007 Information Security Conference(ISC 2007).Berlin:Springer-Verlag，2007:362-375.

［2］陳康，鄭緯民.云計算:系統(tǒng)實例與研究現(xiàn)狀［J］.軟件學報，2009(5):1337-1348

CHEN Kang，ZHENG Weimin.Cloud computing:system instances and current research［J］.Journal of Software，2009(5):1337-1348.

［3］SADEGHI A R，SCHNEIDER T，WINANDY M.Tokenbased cloud computing secure outsourcing of data and arbitrary computations with lower latency［C］//Proceedings of 3rd International Conference on Trust and Trustworthy Computing(TRUST 2010).Berlin，Germany，2010:417-429.

［4］GENTRY C.A fully homomorphic encryption scheme［D］.Stanford:Stanford University，2009:25-88.

［5］RIVEST R L，ADLEMAN L，DERTOUZOS M L.On data banks and privacy homomorphism ［M］.New York:Academic Press，1978:169-179.

［6］GENTRY C.Fully homomorphic encryption using ideal lattices［C］//Proceedings of 41st ACM Symposium on Theory of Computing(STOC 09).New York，USA，2009:169-178.

［7］GTOTH J.A verifiable secret shuffle of homomorphic encryptions［C］//Proceedings of 30th International Cryptology Conference(Crypto 2010).Berlin，Germany，2010:546-579.

［8］SMART N P，VRECAUTEREN F.Fully homomorphic encryption with relatively small key and ciphertext sizes［C］//Proceedings of 13th International Conference on Practice and Theory in Public Key Cryptography.Berlin，Germany，2010:420-443.

［9］DIJK M，GENTRY C，HALEVI S，et al.Fully homomorphic encryption over the integers［C］//Proceedings of 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques(EUROCRYPT 2010).Berlin，Germany ，2010:24-43.

［10］ZHANG Yong，LI Weixin，NIU Xiamu.A secure cipher Index over encrypted character data in database［C］//Proceedings of 2008 International Conference on Machine Learning and Cybernetics.Kunming，China，2008:1111-1116.

［11］ZHANG Yong，LI Weixin，NIU Xiamu.A method of bucket index over encrypted character data in Database［C］//Proceedings of 3rd Intelligent Information Hiding and Multimedia Signal Processing(IIHMSP 2007).Piscataway，USA，2007:186-189.

［12］LIU Lianzhong，GAI Jingfen.Bloom filter based index for query over encrypted character strings in database［C］//Proceedings of the 2009 WRI World Congress on Computer Science and Information Engineering.Piscataway，USA，2009:303-307.

［13］GAHI Y，GUENNOUN M，KHALIL E K .A secure database system using homomorphic encryption schemes［C］//Proceedings of the 3rd International Conference on Advances in Databases，Knowledge，and Data Applications(DBKDA 2011).st.Maarten，The Netherlands Antilles，2011:54-58.

［14］SHOR P.Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer［J］.SIAM Journal on Computing，1997，26(5):1484-1509.

［15］BURROWS M，ABADI M，NEEDHAM R.A logic of authentication［J］.ACM Transactions on Computer Systems，1990，8(1):18-36.