RSA乘法同態(tài)的數(shù)據(jù)庫密文檢索實(shí)現(xiàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

舉例:假定RSA的公鑰、私鑰分別為(5 437，189 781)與(49 269)，2個(gè)明文信息分別為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í)體，即數(shù)據(jù)擁有者發(fā)送自己的密文數(shù)據(jù)C到數(shù)據(jù)庫服務(wù)器，自己需要時(shí)，再獲取這些數(shù)據(jù).假設(shè)密文C對(duì)應(yīng)的明文是M，選用的具有乘法同態(tài)特性的公鑰密鑰體制可以為目前通用的RSA.

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

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

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

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

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

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

當(dāng)D(也就是O)，想從數(shù)據(jù)庫服務(wù)器獲取想要的記錄時(shí)，用明文輸入關(guān)鍵詞KW，可以對(duì)kw1，kw2，kw3進(jìn)行聯(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āng)D得到這些密文分片后，就可以得到C.詳細(xì)如下:當(dāng)數(shù)據(jù)獲取者(也就是數(shù)據(jù)擁有者)取定3個(gè)檢索的關(guān)鍵字kw1，kw2，kw3后，并根據(jù)數(shù)據(jù)庫中的 R(R=R1R2R3)，就可以對(duì) kw1，kw2，kw3進(jìn)行聯(lián)合加密:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4)S?{#Data}EK

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

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

與S、D之間的會(huì)話公鑰是K”

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

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

對(duì)所提出的方案進(jìn)行如下分析:

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

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

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

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

需要做2次解密操作和1次乘法操作，即2次解密分別得到RO和RS，再用乘法得到K=RORS.由于RSA的解密操作比較耗時(shí)，所以提出的思路提升了解密密鑰的獲取效率.為了驗(yàn)證這2種情況下獲取密鑰的性能，實(shí)施了實(shí)驗(yàn)仿真并進(jìn)行了效能測試.實(shí)驗(yàn)采用 Openssl密碼算法庫中的 256、512、1 024、2 048 bit RSA生成的密鑰，采用無密文填充的加密方案，實(shí)現(xiàn)了基于RSA乘法同態(tài)特性的密鑰獲取效率對(duì)比.服務(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的隨機(jī)數(shù)RO和512 bit的隨機(jī)數(shù)RS，在RSA模數(shù)n的不同取值(n=256，512，768，1 024，2 048，4 096)情況下，分別采用乘法同態(tài)和不采用乘法同態(tài)的2種RSA算法，對(duì)比測試了2種密鑰獲取方式，得到了2種機(jī)制情況下的所獲得密鑰K的生成時(shí)間對(duì)比結(jié)果，如圖1所示.

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

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

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

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

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

［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ì)算:系統(tǒng)實(shí)例與研究現(xiàn)狀［J］.軟件學(xué)報(bào)，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.