浮點數據的類復合同態(tài)加密機制

浮點數據的類復合同態(tài)加密機制

隨著信息技術的快速發(fā)展，大量計算機數據存儲的安全性以及敏感數據的竊取和復制變得越來越重要。數據庫系統作為計算機信息系統的核心部件,其安全問題是信息安全領域所要研究的一個重要方面。對于一些重要或敏感數據,用戶迫切希望以密文的形式存儲和傳輸,并且可以對數據庫信息進行操作但又不泄露其中的內容。數據庫加密方法可以應用于不同的環(huán)境,但存在一個共同的問題是對于所形成的密文數據庫無法進行操作。也就是說,對于密文數據庫,若要對某些字段進行統計、平均、求和等數學運算時,必須先對這些字段進行解密運算,然后對明文進行數學運算,之后再加密。這樣一來,首先增大了時空開銷;其次,在實際應用中,對于某些重要或敏感數據,無法滿足用戶對其進行操作但又不讓用戶了解其中的信息的需要。如果能對密文數據庫進行數學運算和常規(guī)的數據庫操作,顯然能夠解決上面存在的問題,并可以大大削減加/解密所需要的時空開銷,提高數據庫的運行效率。秘密同態(tài)(privatehomomorphism)技術就是一個能解決上述問題的有效方法。1算法的基本思想秘密同態(tài)是由Rivest等人于1978年提出的,是允許直接對密文進行操作的加密變換。但是由于其對己知明文攻擊是不安全的,后來由Domingo作了進一步的改進。秘密同態(tài)技術最早是用于對統計數據進行加密的,由算法的同態(tài)性,保證了用戶可以對敏感數據進行操作但又不泄露數據信息。秘密同態(tài)技術是建立在代數理論之上的,其基本思想如下:設Ek1、Dk2分別代表加、解密函數,明文數據空間中的元素是有限集合{M1,M2,…,Mn},α和β代表運算,若α(Ek1(M1),Ek1(M2),…,Ek1(Mn))=Ek1(β(M1,M2,…,Mn))成立,且Dk2(α(Ek1(M1),Ek1(M2),…,Ek1(Mn)))=β(M1,M2,…,Mn)成立,則稱函數族(Ek1,Dk2,α,β)為一個秘密同態(tài)。算法實現過程如下:a)選取安全大素數p、q,及由此計算m=pq(m保密)。b)選取安全參數n(根據需要選擇適當大小)。c)明文空間T=Zm(小于Z的所有非負整數集合),密文空間T′=(Zp×Zq)n。d)選取兩素數rp、rq,分別滿足rp∈Zp,rq∈Zq。e)確定加密密鑰為K=(p,q,rp,rq)。f)加密算法:設有一明文x∈Zm,隨機地將x分為n份:x1,x2,…,xn,并滿足xi∈Ζm?i=(1?2??,n)?x=n∑i=1ximodmxi∈Zm?i=(1?2??,n)?x=∑i=1nximodm。Ek(x)=(,X2RP2MODP,X2RQ2MODQ,…,XNRPNMODP,XNRQNMODQ)g)解密算法Dk(x):(a)計算(X1RPRP-1MODP,X1RQRQ-1MODQ,X2RP2RP-2MODP,X2RQ2RQ-2MODQ,…,XNRPNRP-NMODP,XNRQNRQ-NMODQ)。其中:rp-n和rq-n分別為rpmodp和rqmodq相應次冪的乘法逆元。(b)計算n∑i=1[ximodp,ximodq]=[n∑i=1ximodp,n∑i=1ximodq]=∑i=1n[ximodp,ximodq]=[∑i=1nximodp,∑i=1nximodq]=XMODP,XMODQ(c)利用中國剩余定理計算Dk(x)=(xqq-1+xpp-1)modm。其中qq-1=1modp,pp-1=1modq。2浮點數的秘密同態(tài)加密本文基于秘密同態(tài)加密的基本原理,在同態(tài)加密機制中提出了類復合同態(tài)的概念并應用于浮點數的加密算法中,實現了浮點數的秘密同態(tài)加密,使得同態(tài)加密機制更具有通用性。2.1同態(tài)變換ek定義設σ、τ分別是空間G到H和H到M的同態(tài)變換,則σ和τ的復合σ·τ是空間G到M的同態(tài)變換。即對于?x∈G,有同態(tài)變換y=σ(x)(y∈H),存在z∈M,z=τ(y)=τ(σ(x))=σ·τ(x)。滿足σ·τ(x+y)=σ·τ(x)+σ·τ(y)σ·τ(x×y)=σ·τ(x)×σ·τ(y)基于實際的應用和討論的方便,假設兩次同態(tài)變換分別是加密運算Ek1(x)和Ek2(y)。由于引入復合變換的目的是將浮點數轉換成整數的形式然后進行加密,定義Ek1(x)是對浮點數進行的加密運算,Ek2(y)仍然采用整數上秘密同態(tài)變換的加密機制。2.2浮點數的處理為了保持與原同態(tài)運算的一致性,對浮點數到整數的轉換也采用類似形式。算法的實現過程如下:a)設明文數據x的小數點位數為k(k為非負整數)。b)將原數據分解為x0,x1,…,xk,使得x×10k=x0×100+x1×101+…+xk×10k。其中xi為正整數。c)定義同態(tài)加密變換Ek1(x)=x0×100+x1×101+…+xk×10kd)解密運算Dk1(x)=x/10k,Dk1(x)為浮點數。在浮點數的加、減、乘、除運算中,根據實際的需要設定所有明文數據的最大小數點位數為k(k為非負整數),不夠k位的用零補足,定義計算Ek1(M)(M表示運算表達式)時小數位k′的取值由各明文數據k值經基本運算后的所得值決定,則有:a)加和減Ek1(x±y)=Ek1(x)±Ek1(y)為10的i(0≤i≤k)次方項的加減法。b)乘Ek1(x)×Ek1(y)=(x0×100+x1×101+?+xk×10k)×(y0×100+y1×101+?+yk×10k)=x0y0×100+0+x0y1×100+1+?+xiyj×10i+j+?+xkyk×10k+k=∑i,jxiyj×10i+j=Ek1(xy)Ek1(x)×Ek1(y)=(x0×100+x1×101+?+xk×10k)×(y0×100+y1×101+?+yk×10k)=x0y0×100+0+x0y1×100+1+?+xiyj×10i+j+?+xkyk×10k+k=∑i,jxiyj×10i+j=Ek1(xy)。其中0≤i≤k,0≤j≤k,0≤i+j≤2k。c)除x和y經除法運算后k值消去,則k′取值0,顯然有Ek1(x/y)=Ek1(x)/Ek1(y)由上述加減乘除運算可得Ek1(a/b±c/d)=Ek1(a)/Ek1(b)±Ek1(c)/Ek1(d)=/這些運算保證了可以直接對轉換后的整數進行操作。將浮點數進行同態(tài)加密,即將浮點數明文x經過Ek1(x)同態(tài)變換后,轉換成一整數的形式,然后再用Ek2(y)(其中y=Ek1(x))進行加密變換。解密運算定義為Dk(x)=Dk1(Dk2(x)),Dk1、Dk2分別為Ek1和Ek2的解密運算。解密過程中首先對Ek1(x)形成的密文數據進行解密,然后再利用Dk1(x)計算得到明文數據。2.3類復合同態(tài)加密的步驟類復合同態(tài)運算完成的是浮點數的同態(tài)加密過程,也是本部分的核心。下面的基本運算包括上面講述的浮點數到整數的同態(tài)轉換Ek1(x)以及整數上的同態(tài)加密算法Ek2(x)。具體實現過程如下:a)類復合同態(tài)的加、減法運算Ek2(Ek1(x))±Ek2(Ek1(y))=Ek2(Ek1(x)±Ek1(y))=Ek2(Ek1(x±y))=Ek2·Ek1(x±y)b)類復合同態(tài)的乘法運算Ek2(Ek1(x))×Ek2(Ek1(y))=Ek2(Ek1(x)×Ek1(y))=Ek2(Ek1(xy))=Ek2·Ek1(xy)c)類復合同態(tài)的除法運算Ek2(Ek1(x))/Ek2(Ek1(y))=Ek2即對經過類復合同態(tài)加密后得到的密文之間的加、減、乘、除運算就相當于對明文進行基本運算后再加密。下面給出兩個浮點數加密運算的示例,所用數據有點小,但卻能反映出基本的加密過程(為了清楚簡便,加密過程中把中間生成的整數分割成兩份進行運算)。例1加法運算:設加密密鑰p=17,q=13,rp=2,rq=3,明文x1=0.3,x2=-0.1,x3=2。由類復合同態(tài)的加密原理,設k=1,則有y1=Ek1(x1)=Ek1(0.3)=3×100=3y2=Ek1(x2)=Ek1(-0.1)=-(1×100)=-1y3=Ek1(x3)=Ek1(2.0)=2×101=20則有z1=Ek2(y1)=Ek2(3)=Ek2(2,1)=(,)z2=Ek2(y2)=Ek2(-1)=Ek2(2,-3)=(,)z3=Ek2(y3)=Ek2(20)=Ek2(12,8)=([7,10],[15,7])z1+z2+z3=(,)+(,)+([7,10],[15,7])=([15,22],[24,28])對計算結果進行解密運算得Dk(z1+z2+z3)=Dk1(Dk2([15,22],[24,28]))=Dk1(22)=2.2例2乘法運算:令加密密鑰p=17,q=13,rp=2,rq=3,明文x1=-0.03,x2=0.1。由類復合同態(tài)的加密原理,設k=2,則有y1=Ek1(x1)=Ek1(-0.03)=-(3×100)=-3y2=Ek1(x2)=Ek1(0.10)=0×100+1×101=10則有z1=Ek2(y1)=Ek2(-3)=Ek2(1,-4)=(,)z2=Ek2(y2)=Ek2(10)=Ek2(4,6)=([8,12],[7,2])z1×z2=(,)×([8,12],[7,2])=([0,0],[16,36],[22,42],[7,6])對計算結果進行解密運算得Dk(z1×z2)=Dk1(Dk2([0,0],[16,36],[22,42],[7,6]))=Dk1(-30)=-0.0032.4浮點數同態(tài)加密將同態(tài)加密機制的應用從整數擴展到浮點數范圍內,使秘密同態(tài)加密算法更具有實用性。加密過程中即使經過Ek1(x)加密轉換后得到相同的數據,由于第二次同態(tài)加密素數的隨機選取和加密數據的隨機分割,這樣得到的加密數據也是不一樣的。浮點數同態(tài)加密即在外層加密中保留了原始秘密同態(tài)加密的安全性,同時也對原數據進行了雙重同態(tài)變換,在安全性上只有過之而無不及。由Dominggo-Ferrer等人在文獻中的討論可知,在浮點數上的同態(tài)加密機制在安全性方面同樣能抵抗僅知密文攻擊和已知明文攻擊。3字符的編碼和存儲與整數不同的是,整數加密后能夠實現的在密態(tài)下的加、減、乘、除運算對于字符串是沒有意義的,所以本文通過中國剩余定理將字符串進行轉換,然后利用秘密同態(tài)算法進行加密處理。具體算法如下:a)設一字符串B,將字符串中的每一個字符取其ASCII碼,分別表示為b1,b2,…,bk。其中k是字符串中字符的個數。b)對應取k個兩兩互素的正整數,設為m1,m2,…,mk(mi≥121)。c)由中國剩余定理得同余式組{x≡b1(modm1)x≡b2(modm2)?x≡bk(modmk)???????????x≡b1(modm1)x≡b2(modm2)?x≡bk(modmk)d)同余式組的解x≡k∑i=1Μ′iΜibi(modm)(令m=m1m2…mk;Mi=m/mi;M′i=Mi-1modmi;i=1,2,…,k)就是將要加密的整數值。e)根據秘密同態(tài)算法解密后可得加密數據x,則由bi=xmodmi可得字符串中每個字符的對應ASCII碼值。利用中國剩余定理的證明方法可對字符串與所得加密整數值的對應