戰(zhàn) 非 ，趙 侃 ，曹國震 ，張少茹

（1.西安航空學院計算機學院，陜西西安710077；2.西安交通大學醫(yī)學院護理系，陜西西安710049）

隨著云計算技術的普及，海量的用戶數(shù)據(jù)需存儲在云服務器端，數(shù)據(jù)的隱私保護一直是困擾云計算廣泛應用的重要問題。傳統(tǒng)的加密技術先對明文加密，然后將密文存儲在云服務器端，但是當用戶需要在云服務器端進行檢索、計算和統(tǒng)計操作時，傳統(tǒng)的加密方案是無法實現(xiàn)對密文操作等價于明文操作[1]。

近年來全同態(tài)加密算法的提出和發(fā)展確為之提供了可能。所謂全同態(tài)加密指對明文進行加減乘除的多項式運算再加密，與對加密后的密文進行同樣的運算的結(jié)果是等價的[2-3]。目前較為成熟的同態(tài)方案包括基于理想格設計的同態(tài)加密體制、基于整數(shù)的全同態(tài)加密機制以及非Squash和Bootstrapping的加密體制等。但目前提出的這些算法在計算效率和計算深度上都沒有達到理想狀態(tài)，所以同態(tài)加密還有很大的研究和發(fā)展的空間。

文中通過對同態(tài)加密原理的分析，結(jié)合較為成熟的RSA和Bresson這兩種部分同態(tài)的加密算法，在限定理想算法參數(shù)的基礎上，通過對其二者進行拆分和混合，提出一種BRH（Bresson-RSA Homomorphic Encryption Algorithm）全同態(tài)加密算法，該算法通過實驗，實現(xiàn)了在云服務器端針對密文進行“不解密”的多項式計算，等價于對明文數(shù)據(jù)的全同態(tài)操作。

1 全同態(tài)加密理論分析

所謂加密算法的同態(tài)性是指，當兩段明文x和y，當其二者滿足Dec(En(x)?En(y))=x⊕y，En()代表加密運算，Dec()代表解密運算，⊕代表明文域的運算，?代表密文域的運算。若⊕代表加法運算，稱該加密滿足加法同態(tài)，如本文后面分析的Bresson算法；若?代表乘法時，稱該加密滿足乘法同態(tài)[4-5]，如本文分析的RSA算法。如加密算法能夠?qū)崿F(xiàn)任意多次加法和乘法運算，但仍然同時滿足加法同態(tài)性和乘法同態(tài)性，則稱其為全同態(tài)算法，可如下式表示：

f代表滿足滿足加減乘除運算的任意計算函數(shù)。

全同態(tài)加密的性質(zhì)在云計算中具有廣闊的應用前景，用戶可以在云端委托不信任的第三方對數(shù)據(jù)進行統(tǒng)計和計算而不會泄露明文數(shù)據(jù)，相對于傳統(tǒng)的加密方案，極大地提高了云計算效率[6]。

2 RSA算法及同態(tài)分析

RSA算法通過大數(shù)難以分解的數(shù)學問題保證其安全性，密鑰長度達到1024位[7]。RSA是一種能夠抵御目前絕大多數(shù)密碼攻擊的公鑰加密算法，其密鑰產(chǎn)生及加密解密流程如下：

1）產(chǎn)生兩個大素數(shù)p和q，p≠q；

2）計算n=p×q，根據(jù)歐拉公式φ(n)=(p-1)×(q-1)；

3）隨機選擇滿足 gcd(e,φ(n))=1的(e,n)作為公鑰；

4）計算d=e-1modφ(n)，以(d,n)作為私鑰；

5）對明文按式C=pemodn進行加密；

6）對密文按式P=Cdmodn進行解密；

現(xiàn)對RSA算法的同態(tài)性進行分析：

設算法公鑰為(e,n)，私鑰為(d,n)，明文為m，密文為c。加密解密過程如上所述，對于明文m1和m2進行加密可得：

由以上分析可得RSA算法具有乘法同態(tài)性，由于其不滿足加法同態(tài)，所以RSA算法是一種滿足乘法同態(tài)的部分同態(tài)加密算法。

3 Bresson算法及同態(tài)分析

Bresson加密算法在2002由Cramer和Shoup提出的一種在公鑰密碼體制的通用范式的基礎上發(fā)展而來加密算法，安全性通過規(guī)約到因式分解的數(shù)學難題來進行保證[8]。Bresson算法的密鑰生成及加解密過程如下：

1）設N=pq，其中p和q為素數(shù)。若p0和q0也為素數(shù)，且滿足p=2p0-1,q=2q0+1，G為模N2的二次剩余循環(huán)群。

4）解密過程當已知密鑰α，按下式進行解密

現(xiàn)對Bresson算法的同態(tài)性進行析：

設明文為m1和m2，通過算法加密的密文分別為En(m1)=(A1,B1)和En(m2)=(A2,B2)，其中

因此，Bresson算法和RSA算法不同，它具有加法同態(tài)性。

4 BRH混合全同態(tài)算法設計

全同態(tài)算法最大的優(yōu)勢就是使密文的計算和統(tǒng)計等同于對明文的操作，特別是在云計算中，需要通過云服務器對密文數(shù)據(jù)進行檢索和計算，經(jīng)過全同態(tài)加密方案的數(shù)據(jù)省去了二次解密加密的過程，實現(xiàn)數(shù)據(jù)在云端“不解密”的使用，能夠大大的提高云服務的響應時間[9]。

但是前文提到的基于理想格的全同態(tài)加密方案在實現(xiàn)上還存在巨大的困難，密鑰的生成時間過長、密鑰尺寸過大、加密過程中噪聲的產(chǎn)生，計算維度過低等缺陷使該類算法應用上較為困難[10]。文中以實現(xiàn)云服務器端對密文實現(xiàn)全同態(tài)操作為出發(fā)點，提出了一種混合RSA和Bresson算法的全同態(tài)BRH（Bresson-RSA Homomorphic Encryption Algorithm）加密算法。

BRH算法實現(xiàn)原理為：首先生成RSA和Bresson算法的密鑰；然后對計算多項式進行代數(shù)拆解，分解為純加減計算向量和純乘除計算向量；根據(jù)Bresson算法的加法同態(tài)性對加減多項式進行加密，根據(jù)RSA算法的乘法同態(tài)性對乘除多項式進行加密；在云服務器端對密文進行多項式計算并根據(jù)提出算法進行還原，最終實現(xiàn)全同態(tài)操作。

首先為了實驗仿真的便利以及算法復雜度的考慮，設定該算法在理想條件下執(zhí)行。具體指同態(tài)的加減乘除操作均為整數(shù)，且運算多項式不包含常數(shù)。

當計算過程中若出現(xiàn)浮點數(shù)進行浮點數(shù)到整數(shù)的映射，映射過程如下：

1）設浮點數(shù)小數(shù)位數(shù)為τ且非負整數(shù)，浮點數(shù)表示為γ=γ0?γ1γ2…γτ。

2）則浮點數(shù)可表示為：

γ=γ0×100+γ1×101+…γi×10τ。

3）定義映射函數(shù)為：

f(γ)=γ0×100+γ1×101+…+γi×10τ在映射函數(shù)f下降浮點數(shù)表示為(f(γ),τ)。

4）定義逆映射f-1為：

則 (f(γ),τ)之間的加法操作為：

乘法操作表示為：

減法操作同式（14）類似，除法操作同式（15）類似。由此實現(xiàn)操作數(shù)從浮點域向整數(shù)域的映射。

設f+,-表示加減操作，f×,÷代表乘除操作，設不帶常數(shù)的計算表達式為：

BRH算法具體實現(xiàn)流程如下所示：

1）根據(jù)上述分析的RSA算法和Bresson算法規(guī)則，生成RSA算法的公鑰PKR和私鑰SKR；生成Bresson算法的公鑰PKB和私鑰SKB。

2）將需操作計算的式（16）拆分為單純加減計算向量α=(a1,a2,…,an)+,-和單純乘除向量。

3）對計算向量α進行Bresson加密得EnPKB(α)=(EnPKB(a1),…,EnPKB(an))+,-，將密文發(fā)送至云服務器，在服務器端進行不解密相同運算f+,-(EnPKB(a1),…,EnPKB(an))，然后返回加密密文。然后通過Bresson私鑰進行解密得到向量α的值。

4）對計算向量β進行RSA加密得，將密文發(fā)送至云服務器，在服務器端進行不解密相同運算，然后返回加密密文。然后通過RSA私鑰進行解密得到向量β的值。

5）對|α|與|β|進行還原，完成服務器端的對應同態(tài)操作。

5 云仿真實驗

本次實驗在Java環(huán)境中配置SSH框架，實現(xiàn)Hadoop平臺搭建集群模擬云環(huán)境，集群由6臺計算機組成，其中一臺配置為“CPU I7-4790，8G內(nèi)存，主頻 3.2 GHz，1T硬盤”作為 NameNode，扮演 Master和JobTracker的角色。為了更好模擬云環(huán)境，其余5臺計算機選取實驗室中配置各不相同的5臺機器，作為Slave和DataNode，即云計算中的計算節(jié)點。MapReduce過程對明文以默認值為單位劃分數(shù)據(jù)塊，不變化數(shù)據(jù)塊大小。重寫map（）函數(shù)實現(xiàn)混合加密算法。

第一部分實驗：為更直觀表現(xiàn)算法同態(tài)操作的特點，規(guī)定正整數(shù)進行(x+y)+(a+b)×z的簡單表達式計算。通過變化隨機產(chǎn)生的正整數(shù)取值范圍，對比直接對數(shù)據(jù)明文進行計算和采用BRH算法計算在云平臺下的執(zhí)行時間如圖1所示。

圖1 不同量級數(shù)據(jù)計算對比圖

由圖1分析可得，對于明文直接計算，以目前搭建云平臺的硬件水平?jīng)]有任何壓力，在取值量級增加的情況下計算時間沒有明顯的變化。但是通過混合同態(tài)BRG算法進行計算，雖然是在理想實驗條件下通過代數(shù)結(jié)構(gòu)實現(xiàn)，但是耗時明顯增大，在一定范圍內(nèi)的密文規(guī)模下執(zhí)行效率較為穩(wěn)定，但是隨著數(shù)據(jù)量級繼續(xù)增大，計算時間有大幅遞增的趨勢。這表現(xiàn)出了目前同態(tài)計算的特點，并且由于混合算法中的RSA算法在密鑰生成時計算量較大，也降低了算法效率。

第二部分實驗：隨機生成102內(nèi)的正整數(shù)，同時以四分之一概率隨機生成不同數(shù)量的加減乘除運算符，進行對正整數(shù)進行疊加運算，遇到浮點數(shù)按本文上述的映射規(guī)則進行整數(shù)映射。統(tǒng)計模擬計算規(guī)模（以運算符數(shù)量代表）與執(zhí)行效率之間的關系。實驗結(jié)果如圖2所示。

圖2 不同運算符個數(shù)計算對比圖

由圖2分析可得，在當前搭建的云環(huán)境中，對明文數(shù)據(jù)直接進行計算同樣沒有壓力，執(zhí)行效率平穩(wěn)。但是混合同態(tài)運算受運算規(guī)模制約較大，執(zhí)行時間表現(xiàn)出線性遞增。原因是由于操作符的數(shù)量直接決定了BRH算法進行混合加密解密的次數(shù)，成為制約該方案執(zhí)行效率的瓶頸。

6 結(jié)束語

本文對同態(tài)加密理論進行了簡要分析，指出了目前全同態(tài)加密在實現(xiàn)上的不足，在研究RSA算法和Bresson算法的結(jié)構(gòu)和各自具有的同態(tài)性的基礎上，提出了一種便于理解和實現(xiàn)的混合全同態(tài)加密BRH算法。該算法適合于應用在云計算中，能夠?qū)崿F(xiàn)在云服務器端進行不解密的多項式計算，最后通過搭建云實驗環(huán)境，對提出算法進行了仿真實驗，驗證了該算法的正確性。然而，該算法的局限性也非常大，首先算法的執(zhí)行是基于理想實驗參數(shù)，都是進行正整數(shù)的運算，并且計算量級較小，對于浮點數(shù)進行了不精確的映射，影響了算法的精度。其次，云平臺的集群規(guī)模也較小，沒能較為完全的模擬實際云計算環(huán)境的復雜情況，這些都需要在日后的研究中進行進一步改進和研究。

[1]王鶴鳴.從信息化發(fā)展歷程看密碼學發(fā)展——專訪西安電子科技大學通信工程學院王育民教授[J].信息安全與通信保密，2011，9（12）:13-19.

[2]徐鵬，劉超，斯雪明.基于整數(shù)多項式環(huán)的全同態(tài)加密算法[J].計算機工程，2012，38（24）:1-4.

[3]王勇.隨機函數(shù)及其在密碼學中的應用研究[J].信息網(wǎng)絡安全，2012（3）:17-18.

[4]周燕，劉培玉，趙靜.基于自適應慣性權重的混沌粒子群算法[J].山東大學學報理學版，2012，47（3）:1-7.

[5]林如磊，王箭，杜賀.整數(shù)上的全同態(tài)加密方案的改進[J].計算機應用研究，2013，30（5）:1515-1519.

[6]湯殿華，祝世雄，曹云飛.一個較快速的整數(shù)上的全同態(tài)加密方案[J].計算機工程與應用，2012，48（28）:117-122.

[7]侯佩，寇雅楠，黃利斌.混合加密體制在數(shù)字簽名中的應用[J].計算機工程與計，2011，32（6）:1942-1945.

[8]周福才，徐箭.格理論與密碼學[M].北京:科學出版社，2013.

[9]孫國梓，董宇，李云.基于CP-ABE算法的云存儲數(shù)據(jù)訪問控制[J].通信學報，2011，32（7）:146-152.

[10]劉波.云計算的安全評估之其應對措施探討[J].移動通信，2011，35（9）:34-37.

[11]光焱，顧純祥，祝躍飛.一種基于LWE問題的無證書全同態(tài)加密體制[J].電子與信息學報，2013，35（4）:988-993.

[12]白健，劉慧，張若箐.一種新型基于R—LWE的公鑰密碼體制[J].北京電子科技學院學報，2013，21（2）:46-49.

[13]王永濤.基于屬性密碼體制的相關研究[D].上海：上海交通大學，2011.

[14]Vrakerski Z， Centry C， Vaikuntanathan V.（Leveled）fully homomorphic encryption without bootstrapping[C]//Proc of Innovations in Theoretical Computer Science 2012（ITCS 2012）.New York:ACM，2012:309-325.

[15]Centry C，Haleci S.Fully homomorphic encryption without squashing using depth-3 arithmetic circuits[C]//Proc of the 52th IEEE Annual Symp on Foundations of Computer Science（FOVS 2011）.Piscataway，NJ:IEEE，2011:107-109.

[16]M.Sipser.Introduction to the Theory of Computation[M].Thrid Edition.Wadsworth Publishing Co Inc，2012.