面向數據庫加密的秘密同態算法的研究

（燕山大學 信息科學與工程學院， 河北 秦皇島 066004）

摘 要：在Domingo提出的秘密同態加密算法的理論基礎上，給出了一種將浮點數轉換為整數的同態運算，基于復合同態的數學理論基礎，提出了類復合同態的概念并擴展應用到了實現浮點型數據的同態加密機制中。最后利用中國剩余定理實現了字符串數據的加密。

關鍵詞：秘密同態；浮點數加密；字符串加密；中國剩余定理

中圖分類號：TP309文獻標志碼：A

文章編號：1001-3695(2009)04-1535-03

Research of privacy homomorphism algorithm based on encrypted database

SHI Zhong-pan， CAI Cui-yan， WANG Xian-feng

(Institute of Information Science Engineering， Yanshan University， Qinhuangdao Hebei 066004， China)

Abstract:On the basis of Domingo’s privacy homomorphism algorithm theory，this paper gave a homomorphism operation that could convert data from floating-point to integer.Based on the mathematical theory of compound homomorphism，raised and applied a similar-compound homomorphism notion in the encryption mechanism over float-point data. Besides，achieved the encryption of string using the Chinese remainder theorem in the text at last.

Key words:privacy homomorphism; float-point encryption; string encryption; Chinese remainder theorem

隨著信息技術的飛速發展，計算機大批量數據存儲的安全問題、敏感數據的防竊取和防竄改問題越來越引起人們的重視。數據庫系統作為計算機信息系統的核心部件，其安全問題是信息安全領域所要研究的一個重要方面。對于一些重要或敏感數據，用戶迫切希望以密文的形式存儲和傳輸，并且可以對數據庫信息進行操作但又不泄露其中的內容。

數據庫加密方法可以應用于不同的環境，但存在一個共同的問題是對于所形成的密文數據庫無法進行操作。也就是說，對于密文數據庫，若要對某些字段進行統計、平均、求和等數學運算時，必須先對這些字段進行解密運算，然后對明文進行數學運算，之后再加密。這樣一來，首先增大了時空開銷；其次，在實際應用中，對于某些重要或敏感數據，無法滿足用戶對其進行操作但又不讓用戶了解其中的信息的需要。如果能對密文數據庫進行數學運算和常規的數據庫操作，顯然能夠解決上面存在的問題，并可以大大削減加/解密所需要的時空開銷，提高數據庫的運行效率。秘密同態(private homomorphism)技術就是一個能解決上述問題的有效方法。

1 秘密同態及其在整數上的實現[4]

秘密同態是由Rivest等人于1978年提出的，是允許直接對密文進行操作的加密變換。但是由于其對己知明文攻擊是不安全的，后來由Domingo作了進一步的改進。秘密同態技術最早是用于對統計數據進行加密的，由算法的同態性，保證了用戶可以對敏感數據進行操作但又不泄露數據信息。秘密同態技術是建立在代數理論之上的，其基本思想如下：

設Ek1、Dk2分別代表加、解密函數，明文數據空間中的元素是有限集合{M1，M2，…，Mn}，α和β代表運算，若

α(Ek1(M1)，Ek1(M2)，…，Ek1(Mn))=Ek1(β(M1，M2， …，Mn))

成立，且

Dk2(α(Ek1(M1)，Ek1(M2)，…，Ek1(Mn)))= β(M1，M2， …，Mn)

成立，則稱函數族(Ek1，Dk2，α，β)為一個秘密同態。

算法實現過程如下：

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∈Zm，i=(1，2，…，n)，x=ni=1xi mod m。

Ek(x)=([x1 rp mod p，x1 rq mod q]，[x2 rp2 mod p， x2 rq2mod q]，…，[xn rpn mod p， xn rqn mod q])

g)解密算法Dk（x）：

(a)計算([x1 rprp-1mod p， x1 rqrq-1mod q]，[x2 rp2 rp-2mod p， x2 rq2 rq-2mod q]，…，[xn rpn rp-nmod p， xn rqnrq-nmod q]) 。其中:rp-n和rq-n分別為rp mod p和rq mod q相應次冪的乘法逆元。

(b)計算

ni=1[xi mod p，xi mod q]=[ni=1xi mod p，ni=1xi mod q]=[x mod p，x mod q]

(c)利用中國剩余定理計算Dk(x)=(xqq-1+xpp-1)modm。其中qq-1=1 mod p，pp-1=1 mod q。

2 浮點型數據的同態加密運算

本文基于秘密同態加密的基本原理，在同態加密機制中提出了類復合同態的概念并應用于浮點數的加密算法中，實現了浮點數的秘密同態加密，使得同態加密機制更具有通用性。

2.1 類復合同態的定義

定義 設σ、τ分別是空間G到H和H到M的同態變換，則σ和τ的復合σ#8226;τ是空間G到M的同態變換。即對于x∈G，有同態變換y=σ (x)(y∈H)，存在z∈M，z=τ(y)=τ (σ(x))=σ#8226;τ(x)。滿足

σ#8226;τ(x+y)=σ#8226;τ(x)+σ#8226;τ(y)

σ#8226;τ(x×y)=σ #8226;τ(x)×σ#8226;τ(y)

基于實際的應用和討論的方便，假設兩次同態變換分別是加密運算Ek1（x）和Ek2（y）。由于引入復合變換的目的是將浮點數轉換成整數的形式然后進行加密，定義Ek1（x）是對浮點數進行的加密運算，Ek2（y）仍然采用整數上秘密同態變換的加密機制。 

2.2 浮點數到整數的同態加密變換

為了保持與原同態運算的一致性，對浮點數到整數的轉換也采用類似形式。

算法的實現過程如下：

a)設明文數據x的小數點位數為k（k為非負整數）。

b)將原數據分解為x0，x1，…，xk，使得x×10k=x0×100+x1×101+…+xk×10k。其中xi為正整數。

c)定義同態加密變換

Ek1(x)= x0×100+x1×101+…+xk×10k

d)解密運算Dk1(x)=x/10k，Dk1(x)為浮點數。

在浮點數的加、減、乘、除運算中，根據實際的需要設定所有明文數據的最大小數點位數為k（k為非負整數），不夠k位的用零補足，定義計算Ek1(M)（M表示運算表達式）時小數位k′的取值由各明文數據k值經基本運算后的所得值決定，則有：

a)加和減 Ek1(x±y)=Ek1(x)±Ek1(y)為10的i（0≤i≤k）次方項的加減法。

b)乘 Ek1(x)×Ek1(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=Ek1(xy)。其中0≤i≤k，0≤j≤k， 0≤i+j≤2k。

c）除 x和y經除法運算后k值消去，則k′取值0，顯然有

Ek1(x/y)=Ek1(x)/Ek1(y)

由上述加減乘除運算可得

Ek1(a/b±c/d)=Ek1(a)/Ek1(b)±Ek1(c)/Ek1(d)=[Ek1(a)Ek1(d)±Ek1(b)Ek1(c)]/[Ek1(b)Ek1(d)]

這些運算保證了可以直接對轉換后的整數進行操作。

將浮點數進行同態加密，即將浮點數明文x經過Ek1(x)同態變換后，轉換成一整數的形式，然后再用Ek2(y)（其中y= Ek1(x)）進行加密變換。

解密運算定義為Dk(x)=Dk1(Dk2(x))， Dk1、Dk2分別為Ek1和Ek2的解密運算。解密過程中首先對Ek1(x)形成的密文數據進行解密，然后再利用Dk1(x)計算得到明文數據。

2.3 類復合同態基本運算

類復合同態運算完成的是浮點數的同態加密過程，也是本部分的核心。下面的基本運算包括上面講述的浮點數到整數的同態轉換Ek1(x)以及整數上的同態加密算法Ek2(x)。具體實現過程如下：

a)類復合同態的加、減法運算

Ek2(Ek1(x))±Ek2(Ek1(y))=Ek2(Ek1(x)±Ek1(y))=Ek2(Ek1(x±y))=Ek2#8226;Ek1(x±y)

b)類復合同態的乘法運算

Ek2(Ek1(x))×Ek2(Ek1(y)) =Ek2(Ek1(x)×Ek1(y))=Ek2(Ek1(xy))= Ek2#8226;Ek1(xy)

c）類復合同態的除法運算

Ek2(Ek1(x))/Ek2(Ek1(y))=Ek2[(Ek1(x)/Ek1(y))=Ek2(Ek1(x/y))=Ek2#8226;Ek1(x/y)

即對經過類復合同態加密后得到的密文之間的加、減、乘、除運算就相當于對明文進行基本運算后再加密。

下面給出兩個浮點數加密運算的示例，所用數據有點小，但卻能反映出基本的加密過程(為了清楚簡便，加密過程中把中間生成的整數分割成兩份進行運算)。

例1 加法運算：設加密密鑰p=17，q=13， rp=2，rq=3，明文x1=0.3， x2=-0.1，x3=2。

由類復合同態的加密原理，設k=1，則有

y1=Ek1(x1)=Ek1(0.3)=3×100 =3

y2=Ek1(x2)=Ek1(-0.1) = -(1×100) =-1

y3=Ek1(x3)=Ek1(2.0) =2×101=20

則有

z1=Ek2(y1)=Ek2(3)=Ek2(2，1)=([4，6]，[4，9])

z2=Ek2(y2)=Ek2(-1)=Ek2(2，-3)=([4，6]， [5，12])

z3=Ek2(y3)=Ek2(20)=Ek2(12，8)=([7，10]，[15，7])

z1+z2+z3=([4，6]，[4，9])+([4，6]，[5，12])+([7，10]，[15，7])=([15，22]，[24，28])

對計算結果進行解密運算得

Dk(z1+z2+z3)=Dk1(Dk2([15，22]，[24，28]))=Dk1(22)=2.2

例2 乘法運算：令加密密鑰p=17，q=13， rp=2， rq=3，明文x1=-0.03， x2=0.1。

由類復合同態的加密原理，設k=2， 則有

y1=Ek1(x1)=Ek1(-0.03) =-(3×100) =-3

y2= Ek1(x2)=Ek1(0.10)=0×100+1×101=10

則有

z1=Ek2(y1)=Ek2(-3)=Ek2(1，-4) =([2，3]，[1，3])

z2=Ek2(y2)=Ek2(10)=Ek2(4，6)=([8，12]，[7，2])

z1×z2=([2，3]，[1，3])×([8，12]，[7，2])=([0，0]，[16，36]，[22，42]，[7，6])

對計算結果進行解密運算得

Dk(z1×z2)=Dk1(Dk2([0，0]，[16，36]，[22，42]，[7，6]))=Dk1(-30) =-0.003

2.4 安全性分析

將同態加密機制的應用從整數擴展到浮點數范圍內，使秘密同態加密算法更具有實用性。加密過程中即使經過Ek1(x)加密轉換后得到相同的數據，由于第二次同態加密素數的隨機選取和加密數據的隨機分割，這樣得到的加密數據也是不一樣的。浮點數同態加密即在外層加密中保留了原始秘密同態加密的安全性，同時也對原數據進行了雙重同態變換，在安全性上只有過之而無不及。由Dominggo-Ferrer等人在文獻[2]中的討論可知，在浮點數上的同態加密機制在安全性方面同樣能抵抗僅知密文攻擊和已知明文攻擊。

3 字符串數據的同態加密

與整數不同的是，整數加密后能夠實現的在密態下的加、減、乘、除運算對于字符串是沒有意義的，所以本文通過中國剩余定理將字符串進行轉換，然后利用秘密同態算法進行加密處理。具體算法如下：

a）設一字符串B，將字符串中的每一個字符取其ASCII碼，分別表示為b1，b2，… ，bk。其中k是字符串中字符的個數。

b）對應取k個兩兩互素的正整數，設為m1，m2，…，mk(mi≥121)。

c）由中國剩余定理得同余式組

x≡b1(mod m1)

x≡b2(mod m2)

…

x≡bk(mod mk)

d）同余式組的解x≡ki=1M′iMibi(mod m)（令m=m1m2…mk；Mi=m/mi；M′i=Mi-1 mod mi；i=1，2，…，k）就是將要加密的整數值。

e）根據秘密同態算法解密后可得加密數據x，則由bi=x mod mi可得字符串中每個字符的對應ASCII碼值。

利用中國剩余定理的證明方法可對字符串與所得加密整數值的對應關系進行證明。在具體的實現過程中，素數的選取和存儲也是需要考慮的問題。在安全性方面，它仍然保留了原整數秘密同態加密的特點。

4 結束語

秘密同態加密技術是一種能對密文數據庫進行數學運算和常規的數據庫操作的加密機制。可以對數據庫信息進行操作但又不泄露其中的內容，但到目前為止最好的成果僅能用在整數的范圍內。本文在原加密算法的理論基礎上，對同態算法進行了擴展，實現了在浮點數和字符串數據上秘密同態算法的應用。目前本算法已成功應用于某煤碼頭皮帶秤管理系統中，較好地解決了系統的安全問題。

參考文獻：

［1］

DOMINGO F J.A new privacy homomorphism and applications[J].Information Processing Letters，1996，60(5):277-282.

[2]BRICKELL E F，YACOBI Y.On privacy homomorphisms[C]//Proc of Advances in Cryptology-Eurocrypt’87， LNCS 304.Berlin:Sprin-ger-Verlag，1988:117-125.

[3]RIVEST R L，ADLEMAN L，DETROUZOS M L.On data banks and privacy homomorphism[C]//DeMILLO R A. Proc of Foundations of Secure Computation.New York:Academic Press，1978:169-179.

[4]楊勇，方勇，周安民.秘密同態技術研究及其算法實現 [J].計算機工程，2005，31(2):157-159.

［5］向廣利，陳莘萌，馬捷，等.實數范圍上的同態加密機制[J].計算機工程與應用，2005，41(20):12-14.

[6]王曉峰，王尚平.秘密同態技術在數據庫安全中的應用[J].計算機工程與應用，2003，39(14):194-196.