基于ElGamal的同態(tài)交換加密水印算法①

方立嬌,李子臣,丁海洋

(北京印刷學(xué)院 信息工程學(xué)院,北京 102600)

隨著互聯(lián)網(wǎng)技術(shù)、云計算技術(shù)的進一步發(fā)展和普及,用戶可以將海量的數(shù)據(jù)上傳到云來進行存儲,需要時也很方便再下載下來使用[1].但是,云技術(shù)在給人們帶來便捷的同時,人們也不得不考慮數(shù)據(jù)在傳輸和存儲過程中遇到的安全問題[2].為了避免未經(jīng)授權(quán)的非法修改和非法使用,以及惡意攻擊等,需要對多媒體數(shù)據(jù)進行加密保護或者嵌入水印.此外,在一些特殊領(lǐng)域,如網(wǎng)上匿名投票,醫(yī)療軍事等,人們希望不泄露原始數(shù)據(jù)就能夠進行數(shù)據(jù)認證.此時,不僅需要傳輸和訪問過程中的安全保護,還需要考慮使用過程中的安全保護.所以需要將加密技術(shù)與水印技術(shù)結(jié)合起來對多媒體數(shù)據(jù)進行保護[3].

近年來,人們發(fā)現(xiàn)同態(tài)密碼算法所特有的同態(tài)特性,使得加密前后的明文數(shù)據(jù)與密文數(shù)據(jù)之間具有一定的代數(shù)關(guān)系[4-6],這種特性為加密與水印的結(jié)合提供了一種有效的方法.在文獻[7]中Chen 等提出基于公鑰加密域的數(shù)字水印算法,該算法利用Paillier 同態(tài)公鑰加密系統(tǒng)[4]對載體圖像進行加密,數(shù)據(jù)隱藏者將秘密消息嵌入其中,以生成加密圖像,并將嵌入的秘密消息發(fā)送給接收者,最后,接收者可以不解密就提取信息并恢復(fù)原始圖像.文獻[8-10]基于時域水印算法,將水印與同態(tài)加密算法結(jié)合,提出將明文水印映射到密文域,可以直接修改載體的原始信號值來嵌入水印.其中文獻[8]中,Zhang 等針對公鑰密碼體制加密的密文圖像,提出了一種具有概率和同態(tài)特性的無損、可逆和組合數(shù)據(jù)隱藏方案,將密文像素替換為新值,通過多層濕紙編碼將附加數(shù)據(jù)嵌入到密文像素的多個LSB 平面中.實現(xiàn)了數(shù)據(jù)嵌入操作不會影響原始明文圖像的解密,可以在解密前提取一部分嵌入數(shù)據(jù),解密后提取另一部分嵌入數(shù)據(jù)并恢復(fù)原始明文圖像.并且對圖像進行預(yù)處理,預(yù)防了像素溢出的問題.文獻[9]中,提出了一種新的加密圖像的可逆數(shù)據(jù)隱藏方案.該方法無需對原始圖像進行任何預(yù)處理,即可將附加數(shù)據(jù)直接嵌入到加密圖像中.但是必須解密后才能恢復(fù)原始圖像和提取水印信息.在文獻[10]中Xiang 利用Paillier密碼體制的同態(tài)和概率特性,提出了一種新的加密圖像的可逆數(shù)據(jù)隱藏方案,嵌入的數(shù)據(jù)可以直接從加密域中提取出來,方案具有更低的計算復(fù)雜度、更高的安全性能和更好的嵌入性能.文獻[11]提出了一種同態(tài)加密域的離散小波變換(DWT)和多分辨率分析(MRA)的方法,利用模乘法逆元的方法解決了量化帶來的數(shù)據(jù)擴展問題.盡管如此,仍可改善加密域中水印方案的性能.文獻[12] 結(jié)合離散小波變換和離散余弦變換(DCT)的方法提高了加密域水印方案的魯棒性能.水印提取可以在明文域和加密域上執(zhí)行.文獻[13]中提出了一種同態(tài)加密域圖像可逆水印算法,大大降低了數(shù)據(jù)擴展,提高了嵌入容量.人們雖然提出了許多加密技術(shù)與水印技術(shù)相結(jié)合的水印算法,但是仍存在一些關(guān)鍵問題需要研究.比如,先對多媒體數(shù)據(jù)進行加密然后再在多媒體密文中嵌入水印,則可能導(dǎo)致密文無法解密.另一方面,先嵌入水印,然后再加密,那么不能直接在密文域提取出水印信息,只有在解密后才能提取水印信息.這樣使得水印提取的解密步驟冗余,更會使明文數(shù)據(jù)暴露于檢測環(huán)境中,大大降低了多媒體數(shù)據(jù)分發(fā)過程中的安全性.

利用交換加密水印(Commutative Encryption Watermarking,CEW)方案,可以實現(xiàn)在明文或密文域嵌入水印,提取水印時,不僅在密文域能提取出數(shù)字水印,而且在解密后的明文域也可以提取水印,實現(xiàn)加密和水印嵌入順序的交換.人們通常選擇基于獨立操作數(shù)的CEW[14],文獻[15] 中的方案基于樹形結(jié)構(gòu)的Haar 變換,在變換系數(shù)的子集中執(zhí)行水印嵌入,并對其余部分進行加密.但是部分加密的CWE 方案面臨暴露明文媒體數(shù)據(jù)的風(fēng)險.文獻[16]借助Paillier 密碼算法的同態(tài)特性,實現(xiàn)相同操作數(shù)的加密和水印相結(jié)合,在不解密的情況下也能提取出水印,提高了多媒體信息的安全性,但是該方案忽略了像素溢出的問題.隨后,文獻[17]提出了一種基于模運算CEW 方案,但是該方案的加密算法并不安全.目前人們提出了許多加密域水印方案和CEW 方案,但是對同態(tài)加密域的CEW技術(shù)的研究還很少還不成熟,仍有許多可以改進的地方.

基于上述問題,本文利用ElGamal 密碼算法的乘法同態(tài)特性,同時,結(jié)合Patchwork 水印算法[18],提出一種更方便的基于同態(tài)操作的CEW 方案,將明文水印算法通過同態(tài)映射到密文域,實現(xiàn)密文水印的嵌入以及明文水印在密文域中嵌入.解決了加密和數(shù)字水印相互影響的問題,保證了數(shù)據(jù)加密、水印嵌入操作不受先后順序的限制,實現(xiàn)數(shù)據(jù)在密文狀態(tài)下的直接檢測水印以及解密后水印仍可提取的功能,以確保算法具有更高的安全性.

1 理論基礎(chǔ)

本節(jié)將介紹CEW[16],ElGamal 密碼體制[5]的同態(tài)特性、Patchwork 水印算法[18],以及本文提出的基于ElGamal 同態(tài)交換加密水印算法的基本原理.

1.1 交換加密水印

CEW是實現(xiàn)加密與水印結(jié)合的有效途徑.利用CEW 方案,可以實現(xiàn)加密和水印操作順序的交換.下圖1是交換加密水印算法的流程圖.

圖1 交換加密水印算法流程圖

圖1中,E為加密函數(shù),W是數(shù)字水印函數(shù),CEW是交換加密水印算法,k是加密密鑰,X是明文多媒體載體,w是嵌入的數(shù)字水印,Xew是經(jīng)過交換加密水印運算后的多媒體信息,Xw是解密后含水印明文多媒體載體,w′是提取的數(shù)字水印.

目前,為了避免加密與水印之間相互干擾,大多數(shù)CEW 算法都是通過操作的獨立性來完成.這意味著水印的操作數(shù)對用戶是透明的,因為沒有加密,降低了多媒體信息數(shù)據(jù)的安全性.為此,人們將正交分解引入到基于獨立操作的CEW (CEWod)[19]中,以提高多媒體信息的安全性.然而,CEWod 也是一種基于獨立操作的CEW,并不是解決CEW 安全問題的根本出路.本文利用同態(tài)加密來削弱對特定加密算法和水印算法的限制,并提高水印方案的安全性.

1.2 ElGamal 同態(tài)加密算法

ElGamal 算法[5],是國際公認的公鑰密碼體制,算法的安全性依賴于計算有限域上離散對數(shù)這一難題.ElGamal 密碼算法由參數(shù)產(chǎn)生、密鑰生成、加密和解密4 部分組成.

參數(shù)產(chǎn)生:設(shè)G為有限域Zp的乘法群,p是一個素數(shù),g是Zp上的一個生成元,且g∈ZP*.

密鑰生成:選取x∈[1,p-1],計算y=gx(modp),那么x為私鑰,y為公鑰.

加密過程:對消息m,可以任意的選取隨機數(shù)r∈[1,p-1],利用公鑰y和系統(tǒng)參數(shù)計算c1=gr(modp)和c2=mgr(modp),可以得到密文為E(m)=(c1,c2),其中,E(·)表示加密算法.

解密過程:接收者接收到密文消息c=(c1,c2)后,利用私鑰x,計算m=D(E(m))=c2(c1x)-1modp,其中,D(·)表示解密算法.

對兩個明文m1、m2,對其分別進行加密,得到E(m1)=(gr1modp,m1yr11modp),E(m2)=(gr2modp,m2yr12modp), 則E(m1)E(m2)=(gr1+r2modp,m1m2yr11+r2modp)D(E(m1)E(m2))=m1m2yr11+r2[(gr1+r2)x]-1(modp)=m1m2.

因此,ElGamal 密碼體制具有乘法同態(tài)特性[5].

1.3 Patchwork 水印算法

Patchwork 算法是根據(jù)數(shù)據(jù)統(tǒng)計特性而設(shè)計的一種數(shù)字水印算法.在水印信息嵌入之前,先從原始載體數(shù)據(jù)中選擇一些數(shù)據(jù),然后將這些數(shù)據(jù)按照一定的關(guān)系組成兩個集合,通過修改這兩個集合的關(guān)系來嵌入水印,兩個集合間的關(guān)系可以是大小/能量/奇偶性關(guān)系,提取水印時根據(jù)對應(yīng)關(guān)系提取水印信息.一般Patchwork 水印算法[18]的步驟可以描述如下:

(1)數(shù)據(jù)集合選取:從載體數(shù)據(jù)中選擇兩組數(shù)據(jù),將這些數(shù)據(jù)按照一定關(guān)系組成兩個集合A={ai,j},B={bi,j},i∈[1,n],j∈[1,n],其中A,B的圖像的像素值相近.

(2)水印嵌入:將集合A中所有的像素點增加d,將集合B中所有的像素點減少d.

(3)水印提取:通過計算均值s提取水印信息:

即:

以d=1為例,假設(shè)原始載體中隨機選取2N2個數(shù)據(jù)對(ai,j,bi,j),則嵌入水印算法如下:

利用ai,j+1,bi,j-1 可以保持載波數(shù)據(jù)的平均值,所以水印提取算法為:

其中,當s≈2,表示帶水印載波,水印信息為1;若s≈0,表示無水印載波嵌入水印,水印信息為0.

2 基于ElGamal和Patchwork 交換加密水印算法

通過將ElGamal 同態(tài)加密算法與Patchwork 水印算法相結(jié)合,在嵌入水印時,可以在明文嵌入水印,或者在加密后密文嵌入水印.在水印提取時,既可以密文域提取水印,也可以在解密后的明文中提取水印.實現(xiàn)了加密算法和水印算法先后順序的交換.

算法總體結(jié)構(gòu)如圖2所示.

圖2 算法總體結(jié)構(gòu)圖

在設(shè)計算法的時候,我們可以由ElGamal 對消息m加密,計算得到密文為c1=gr(modp),c2=myr(modp).將m的密文記為E(m)=mod [(c1,c2),p].

D{mod [(c1,c2),p]}=c2/c1x(modp),其中y是加密時的公鑰,x是解密時的私鑰.

2.1 交換加密水印算法基本原理

基于ElGamal 加密算法與Patchwork 水印算法的CEW 算法包括如下步驟:

(1)數(shù)據(jù)集合選取:在載體圖像中選擇一些數(shù)據(jù),根據(jù)像素值下標之和的奇偶性將數(shù)據(jù)重新組成兩個集合A={ai,j},B={bi,j},i∈[1,N],j∈[1,N],其中A,B集合中的像數(shù)值用ai,j和bi,j代表,并且在實際圖像的像素點下標之和分別為偶數(shù)和奇數(shù).

(2)水印嵌入:將集合A中所有的像素點改變λ 倍,將集合B中所有的像素點改變 λ-1倍.此處的λ接近1.λ值的大小由均衡水印提取率與嵌入水印后圖像質(zhì)量的得到.

(3)水印提取:

其中,s的值將決定是否帶有載波水印,若s≈λ2,含有帶水印載波,水印信息為1;若s≈1,表示無水印載波,水印信息為0.

2.2 含水印密文載體的生成

首先在原始載體數(shù)據(jù)中選擇一些數(shù)據(jù),然后計算這些像素值下標的值,再按照下標值的奇偶性分配組成兩個集合{ai,j},{bi,j},i∈[1,N],j∈[1,N].

2.2.1 先嵌入水印后加密

在明文中嵌入水印:

其中,,是帶水印的明文.

然后對含水印的明文進行加密:

為了將來能在密文中提取水印,選取適當隨機參數(shù)(ra,rb)滿足:

當水印信息為1 時,使得(≥(modp));當水印信息為0 時,使得(＜(modp)).

由于,ElGamal 加密算法是一種概率公鑰密碼體制,選取適當?shù)碾S機參數(shù),滿足上述不等式是可行的.

2.2.2 先加密后嵌入水印

對每個像素值加密,加密算法ca1=gra(modp),ca2=ai,jgra(modp),cb1=grb(modp),cb2=bi,jgrb(modp),其中rarb為在區(qū)間(1,p-1)中的隨機參數(shù).

同理,將 λ加密之后的密文記為(cλ1,cλ2),將λ-1加密之后的密文記為(cλ-11,cλ-12).

在密文中嵌入水印:

其中,,是密文水印載體.

為了能在密文中提取水印,選取適當隨機參數(shù)(ra,rb,rλ,rλ-1)滿足:

當水印信息為1 時,使得(cλ2ca2≥cλ-12cb2(modp));當水印信息為0 時,使得(cλ2ca2＜cλ-12cb2(modp)).

2.3 水印信息的提取

2.3.1 在解密后的明文提取水印

首先引入如下的結(jié)論.

定理.對利用上述先嵌入水印后加密與先加密后嵌入水印所得到的含水印的密文進行解密結(jié)果是相同的,即:

其次證明:

提取水印步驟如下:

然后計算:

最后,根據(jù)s的值,提取水印信息.若s≈λ2,表示有載波水印,水印信息為1;若s≈1,表示不含有載波水印,實際水印信息為0.

2.3.2 在密文中提取水印

在密文中提取水印的步驟如下:

首先計算:

然后,根據(jù)s的值提取水印信息.若s=1,表示含有載波水印,水印信息為1.若s=0,表示未含載波水印,水印信息為0.

3 實驗分析

3.1 實驗設(shè)置

在實驗時,為了驗證算法的可行性,實驗首選標準Lena(256×256)灰度圖像來做示例,ElGamal 加密算法中選取大素數(shù)p=257,g=3,私鑰x=2,公鑰y=gxmodp.為簡單起見,加密時選取的隨機數(shù)r=5.

實驗使用水印算法的客觀評價標準,如峰值信噪比(PSNR)、誤碼率(BER)和嵌入率(BR)來測試和衡量設(shè)計的水印算法的性能指標.其中,峰值信噪比(PSNR)的值用來衡量嵌入水印后的圖像與原始圖像之間的差異,PSNR 值越大,差異越小,效果越好.誤碼率BER∈[0,1],BER的值越接近0 說明提取水印準確率越高.對于相同大小的載體,當嵌入率(BR)越高時,相應(yīng)的嵌入容量也越大.假設(shè)原始圖像用I表示,解密后含水印的圖像記為I′,使用(i,j)表示圖像的像素坐標,其中h代表圖像的高度,w表示圖像的寬度,M為嵌入的水印總比特數(shù).

峰值信噪比(PSNR)的計算公式為:

誤碼率(BER)的計算公式為:

另外,在數(shù)字水印圖像處理技術(shù)領(lǐng)域中,一般原始載體圖像的像素值為[0,255],由于加密域水印算法中的加密操作,很可能會出現(xiàn)像素值為負數(shù)或者像素值超過255的現(xiàn)象,為了減少或者避免像素溢出的問題,人們會在嵌入水印信息之前對待處理圖像進行預(yù)處理[20].在本算法中,由于ElGamal 算法加密操作,會出現(xiàn)像素值溢出的情況,為了減少溢出,在仿真實驗過程中,選取素數(shù)p=257,這樣使得在對像素值進行模運算的時候,盡可能地使得運算結(jié)果的范圍為0～255,有極小的可能性像素值會上溢.在實際實驗時,我們可以對所有像素點進行掃描和標記,在加密后和嵌入水印之前,預(yù)先將大于255的像素值修改為255,并對修改位進行標識.然后在解密和提取水印的過程中,根據(jù)標識位將像素值修改為原像素值.有時候圖像預(yù)處理比較繁瑣,但是進行圖像預(yù)處理,能夠保證算法準確無誤的進行.

3.2 實驗結(jié)果分析

圖3(a)是原始載體圖像,圖3(b)是利用ElGamal加密系統(tǒng)加密后得到的密文圖像,圖3(c)是嵌入水印后的密文水印圖像,以及圖3(d)是解密后的含水印圖像,計算得到的PSNR值為24.71 dB,BER值為0.0039.圖4分別是原始圖像,嵌入水印信息之后的含水印圖像和密文含水印圖像,以及解密后的含水印圖像,圖4(b)的PSNR值為51.36 dB,解密后的含水印圖像,PSNR值為50.38 dB,BER值均為0,說明能準確提取水印.由實驗結(jié)果可知,利用本算法無論是在明文域還是在密文域,都能成功提取水印信息,并解密得到原始圖像,且解密得到的水印圖像質(zhì)量較高.

圖3 加密域下的實驗結(jié)果圖

圖4 明文域下的實驗結(jié)果圖

3.3 水印算法的性能測試

為了更進一步評估本算法的試用性和魯棒性,接下來對再分別選取4 幅256×256 大小的圖像(peppers、cameraman、plane、baboon)進行性能評估.根據(jù)式(14),計算在不同嵌入容量下得到的水印圖像的峰值信噪比,表1是密文域不同嵌入容量下的PSNR,表2是明文域不同嵌入容量下的PSNR值.由表1和表2,可見隨著嵌入容量的減小,PSNR值越來越大,并且算法無論是在密文域還是在明文域,在嵌入容量高達0.25 bpp (bpp 表示每像素嵌入的比特數(shù)[13])情況下,含水印圖像解密后也能獲得比較清晰的圖像.在明文域下解密得到的PSNR值達到了50.38 dB,很好的恢復(fù)了原始圖像.

表1 密文域不同嵌入容量下的PSNR (dB)

與其他加密域的水印算法文獻[16]和文獻[13]進行比較結(jié)果見表3.由表3可見,在無水印攻擊時,以256×256的Lena 灰度圖像為例,與文獻[16]和[13]中的算法比較,本文水印算法在明文域的PSNR 值為50.38 dB,文獻[16]和文獻[13]的PSNR值分別為48.13 dB和42.81 dB,本文算法求得的PSNR值,高于其他算法,說明提取出的水印圖像與原始圖像差異較小,水印圖像效果較好,水印圖像質(zhì)量得到了改善,同時還能實現(xiàn)密文域下水印的提取,并且本文算法還具有一定的抗攻擊性能,由此可見,本文算法的整體性能得到了改善.

表2 明文域不同嵌入容量下的PSNR (dB)

表3 本文算法與其他文獻算法比較

4 結(jié)論與展望

本文基于同態(tài)加密算法ElGamal 與Patchwork 水印算法,構(gòu)造了一種新的同態(tài)密文域交換加密水印算法,實現(xiàn)了加解密算法和水印算法先后順序的完全交換.與以前的水印算法相比,本文提出的水印算法既可以保證多媒體數(shù)據(jù)在存儲分發(fā)過程中的安全性,也可以保證數(shù)據(jù)在使用以及認證過程中的安全性.在算法性能方面,實驗結(jié)果表明,該算法具有較高的嵌入率和峰值信噪比,提取出的水印圖像質(zhì)量較好,因此本文的算法具有一定的研究意義和參考性.

下一步的研究可以尋求更高效的方法解決同態(tài)加密域像素溢出的問題,或者提高交換加密域水印算法的魯棒性,來進一步改善算法的綜合性能.