RSA乘法同態的數據庫密文檢索實現

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

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

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

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

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

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

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

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

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

1 密文檢索方案設計

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

1.1 RSA密碼體制的同態性分析

使用RSA密碼體制在完成加解密運算時，首先選取2 個大素數 p、q，計算 n=pq，φ(n)=(p-1)(q-1);隨機選取一個整數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公鑰密碼體制滿足乘法同態特性.

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

1.2 數據庫中密文檢索協議構造

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

1)向數據庫服務器發送數據

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

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

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

其次，數據擁有者把t個密文關鍵詞ckw1，ckw2，…，ckwt的乘積Ckw=ckw1ckw2…ckwt也一并發送到數據庫.

2)從數據庫服務器獲取數據階段.

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

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

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

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

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

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

1.3 帶有隱私保護的同態密鑰協商

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

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

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

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

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

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

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

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

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

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

③用密鑰K，就可以解密得到明文數據Data.

1.4 協議的安全性證明

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

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

4)S?{#Data}EK

見規則，D可以構造K=RORS

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

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

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

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

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

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

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

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

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

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

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

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

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

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

由圖2可知，利用乘法同態所獲取密鑰的時間基本上也是不采用乘法同態的一半，即密鑰獲取效率也提升了近50%.同時，從圖2平穩的折線中可以明顯看出獲得不同位數的解密密鑰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 結束語

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

［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］陳康，鄭緯民.云計算:系統實例與研究現狀［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.