基于ElGamal的同态交换加密水印算法①

方立娇,李子臣,丁海洋

(北京印刷学院 信息工程学院,北京 102600)

随着互联网技术、云计算技术的进一步发展和普及,用户可以将海量的数据上传到云来进行存储,需要时也很方便再下载下来使用[1].但是,云技术在给人们带来便捷的同时,人们也不得不考虑数据在传输和存储过程中遇到的安全问题[2].为了避免未经授权的非法修改和非法使用,以及恶意攻击等,需要对多媒体数据进行加密保护或者嵌入水印.此外,在一些特殊领域,如网上匿名投票,医疗军事等,人们希望不泄露原始数据就能够进行数据认证.此时,不仅需要传输和访问过程中的安全保护,还需要考虑使用过程中的安全保护.所以需要将加密技术与水印技术结合起来对多媒体数据进行保护[3].

近年来,人们发现同态密码算法所特有的同态特性,使得加密前后的明文数据与密文数据之间具有一定的代数关系[4-6],这种特性为加密与水印的结合提供了一种有效的方法.在文献[7]中Chen 等提出基于公钥加密域的数字水印算法,该算法利用Paillier 同态公钥加密系统[4]对载体图像进行加密,数据隐藏者将秘密消息嵌入其中,以生成加密图像,并将嵌入的秘密消息发送给接收者,最后,接收者可以不解密就提取信息并恢复原始图像.文献[8-10]基于时域水印算法,将水印与同态加密算法结合,提出将明文水印映射到密文域,可以直接修改载体的原始信号值来嵌入水印.其中文献[8]中,Zhang 等针对公钥密码体制加密的密文图像,提出了一种具有概率和同态特性的无损、可逆和组合数据隐藏方案,将密文像素替换为新值,通过多层湿纸编码将附加数据嵌入到密文像素的多个LSB 平面中.实现了数据嵌入操作不会影响原始明文图像的解密,可以在解密前提取一部分嵌入数据,解密后提取另一部分嵌入数据并恢复原始明文图像.并且对图像进行预处理,预防了像素溢出的问题.文献[9]中,提出了一种新的加密图像的可逆数据隐藏方案.该方法无需对原始图像进行任何预处理,即可将附加数据直接嵌入到加密图像中.但是必须解密后才能恢复原始图像和提取水印信息.在文献[10]中Xiang 利用Paillier密码体制的同态和概率特性,提出了一种新的加密图像的可逆数据隐藏方案,嵌入的数据可以直接从加密域中提取出来,方案具有更低的计算复杂度、更高的安全性能和更好的嵌入性能.文献[11]提出了一种同态加密域的离散小波变换(DWT)和多分辨率分析(MRA)的方法,利用模乘法逆元的方法解决了量化带来的数据扩展问题.尽管如此,仍可改善加密域中水印方案的性能.文献[12] 结合离散小波变换和离散余弦变换(DCT)的方法提高了加密域水印方案的鲁棒性能.水印提取可以在明文域和加密域上执行.文献[13]中提出了一种同态加密域图像可逆水印算法,大大降低了数据扩展,提高了嵌入容量.人们虽然提出了许多加密技术与水印技术相结合的水印算法,但是仍存在一些关键问题需要研究.比如,先对多媒体数据进行加密然后再在多媒体密文中嵌入水印,则可能导致密文无法解密.另一方面,先嵌入水印,然后再加密,那么不能直接在密文域提取出水印信息,只有在解密后才能提取水印信息.这样使得水印提取的解密步骤冗余,更会使明文数据暴露于检测环境中,大大降低了多媒体数据分发过程中的安全性.

利用交换加密水印(Commutative Encryption Watermarking,CEW)方案,可以实现在明文或密文域嵌入水印,提取水印时,不仅在密文域能提取出数字水印,而且在解密后的明文域也可以提取水印,实现加密和水印嵌入顺序的交换.人们通常选择基于独立操作数的CEW[14],文献[15] 中的方案基于树形结构的Haar 变换,在变换系数的子集中执行水印嵌入,并对其余部分进行加密.但是部分加密的CWE 方案面临暴露明文媒体数据的风险.文献[16]借助Paillier 密码算法的同态特性,实现相同操作数的加密和水印相结合,在不解密的情况下也能提取出水印,提高了多媒体信息的安全性,但是该方案忽略了像素溢出的问题.随后,文献[17]提出了一种基于模运算CEW 方案,但是该方案的加密算法并不安全.目前人们提出了许多加密域水印方案和CEW 方案,但是对同态加密域的CEW技术的研究还很少还不成熟,仍有许多可以改进的地方.

基于上述问题,本文利用ElGamal 密码算法的乘法同态特性,同时,结合Patchwork 水印算法[18],提出一种更方便的基于同态操作的CEW 方案,将明文水印算法通过同态映射到密文域,实现密文水印的嵌入以及明文水印在密文域中嵌入.解决了加密和数字水印相互影响的问题,保证了数据加密、水印嵌入操作不受先后顺序的限制,实现数据在密文状态下的直接检测水印以及解密后水印仍可提取的功能,以确保算法具有更高的安全性.

1 理论基础

本节将介绍CEW[16],ElGamal 密码体制[5]的同态特性、Patchwork 水印算法[18],以及本文提出的基于ElGamal 同态交换加密水印算法的基本原理.

1.1 交换加密水印

CEW是实现加密与水印结合的有效途径.利用CEW 方案,可以实现加密和水印操作顺序的交换.下图1是交换加密水印算法的流程图.

图1 交换加密水印算法流程图

图1中,E为加密函数,W是数字水印函数,CEW是交换加密水印算法,k是加密密钥,X是明文多媒体载体,w是嵌入的数字水印,Xew是经过交换加密水印运算后的多媒体信息,Xw是解密后含水印明文多媒体载体,w´是提取的数字水印.

目前,为了避免加密与水印之间相互干扰,大多数CEW 算法都是通过操作的独立性来完成.这意味着水印的操作数对用户是透明的,因为没有加密,降低了多媒体信息数据的安全性.为此,人们将正交分解引入到基于独立操作的CEW (CEWod)[19]中,以提高多媒体信息的安全性.然而,CEWod 也是一种基于独立操作的CEW,并不是解决CEW 安全问题的根本出路.本文利用同态加密来削弱对特定加密算法和水印算法的限制,并提高水印方案的安全性.

1.2 ElGamal 同态加密算法

ElGamal 算法[5],是国际公认的公钥密码体制,算法的安全性依赖于计算有限域上离散对数这一难题.ElGamal 密码算法由参数产生、密钥生成、加密和解密4 部分组成.

参数产生:设G为有限域Zp的乘法群,p是一个素数,g是Zp上的一个生成元,且g∈ZP*.

密钥生成:选取x∈[1,p-1],计算y=gx(modp),那么x为私钥,y为公钥.

加密过程:对消息m,可以任意的选取随机数r∈[1,p-1],利用公钥y和系统参数计算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 密码体制具有乘法同态特性[5].

1.3 Patchwork 水印算法

Patchwork 算法是根据数据统计特性而设计的一种数字水印算法.在水印信息嵌入之前,先从原始载体数据中选择一些数据,然后将这些数据按照一定的关系组成两个集合,通过修改这两个集合的关系来嵌入水印,两个集合间的关系可以是大小/能量/奇偶性关系,提取水印时根据对应关系提取水印信息.一般Patchwork 水印算法[18]的步骤可以描述如下:

(1)数据集合选取:从载体数据中选择两组数据,将这些数据按照一定关系组成两个集合A={ai,j},B={bi,j},i∈[1,n],j∈[1,n],其中A,B的图像的像素值相近.

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

(3)水印提取:通过计算均值s提取水印信息:

即:

以d=1为例,假设原始载体中随机选取2N2个数据对(ai,j,bi,j),则嵌入水印算法如下:

利用ai,j+1,bi,j-1 可以保持载波数据的平均值,所以水印提取算法为:

其中,当s≈2,表示带水印载波,水印信息为1;若s≈0,表示无水印载波嵌入水印,水印信息为0.

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

通过将ElGamal 同态加密算法与Patchwork 水印算法相结合,在嵌入水印时,可以在明文嵌入水印,或者在加密后密文嵌入水印.在水印提取时,既可以密文域提取水印,也可以在解密后的明文中提取水印.实现了加密算法和水印算法先后顺序的交换.

算法总体结构如图2所示.

图2 算法总体结构图

在设计算法的时候,我们可以由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)数据集合选取:在载体图像中选择一些数据,根据像素值下标之和的奇偶性将数据重新组成两个集合A={ai,j},B={bi,j},i∈[1,N],j∈[1,N],其中A,B集合中的像数值用ai,j和bi,j代表,并且在实际图像的像素点下标之和分别为偶数和奇数.

(2)水印嵌入:将集合A中所有的像素点改变λ 倍,将集合B中所有的像素点改变 λ-1倍.此处的λ接近1.λ值的大小由均衡水印提取率与嵌入水印后图像质量的得到.

(3)水印提取:

其中,s的值将决定是否带有载波水印,若s≈λ2,含有带水印载波,水印信息为1;若s≈1,表示无水印载波,水印信息为0.

2.2 含水印密文载体的生成

首先在原始载体数据中选择一些数据,然后计算这些像素值下标的值,再按照下标值的奇偶性分配组成两个集合{ai,j},{bi,j},i∈[1,N],j∈[1,N].

2.2.1 先嵌入水印后加密

在明文中嵌入水印:

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

然后对含水印的明文进行加密:

为了将来能在密文中提取水印,选取适当随机参数(ra,rb)满足:

当水印信息为1 时,使得(≥(modp));当水印信息为0 时,使得(＜(modp)).

由于,ElGamal 加密算法是一种概率公钥密码体制,选取适当的随机参数,满足上述不等式是可行的.

2.2.2 先加密后嵌入水印

对每个像素值加密,加密算法ca1=gra(modp),ca2=ai,jgra(modp),cb1=grb(modp),cb2=bi,jgrb(modp),其中rarb为在区间(1,p-1)中的随机参数.

同理,将 λ加密之后的密文记为(cλ1,cλ2),将λ-1加密之后的密文记为(cλ-11,cλ-12).

在密文中嵌入水印:

其中,,是密文水印载体.

为了能在密文中提取水印,选取适当随机参数(ra,rb,rλ,rλ-1)满足:

当水印信息为1 时,使得(cλ2ca2≥cλ-12cb2(modp));当水印信息为0 时,使得(cλ2ca2＜cλ-12cb2(modp)).

2.3 水印信息的提取

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

首先引入如下的结论.

定理.对利用上述先嵌入水印后加密与先加密后嵌入水印所得到的含水印的密文进行解密结果是相同的,即:

其次证明:

提取水印步骤如下:

然后计算:

最后,根据s的值,提取水印信息.若s≈λ2,表示有载波水印,水印信息为1;若s≈1,表示不含有载波水印,实际水印信息为0.

2.3.2 在密文中提取水印

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

首先计算:

然后,根据s的值提取水印信息.若s=1,表示含有载波水印,水印信息为1.若s=0,表示未含载波水印,水印信息为0.

3 实验分析

3.1 实验设置

在实验时,为了验证算法的可行性,实验首选标准Lena(256×256)灰度图像来做示例,ElGamal 加密算法中选取大素数p=257,g=3,私钥x=2,公钥y=gxmodp.为简单起见,加密时选取的随机数r=5.

实验使用水印算法的客观评价标准,如峰值信噪比(PSNR)、误码率(BER)和嵌入率(BR)来测试和衡量设计的水印算法的性能指标.其中,峰值信噪比(PSNR)的值用来衡量嵌入水印后的图像与原始图像之间的差异,PSNR 值越大,差异越小,效果越好.误码率BER∈[0,1],BER的值越接近0 说明提取水印准确率越高.对于相同大小的载体,当嵌入率(BR)越高时,相应的嵌入容量也越大.假设原始图像用I表示,解密后含水印的图像记为I′,使用(i,j)表示图像的像素坐标,其中h代表图像的高度,w表示图像的宽度,M为嵌入的水印总比特数.

峰值信噪比(PSNR)的计算公式为:

误码率(BER)的计算公式为:

另外,在数字水印图像处理技术领域中,一般原始载体图像的像素值为[0,255],由于加密域水印算法中的加密操作,很可能会出现像素值为负数或者像素值超过255的现象,为了减少或者避免像素溢出的问题,人们会在嵌入水印信息之前对待处理图像进行预处理[20].在本算法中,由于ElGamal 算法加密操作,会出现像素值溢出的情况,为了减少溢出,在仿真实验过程中,选取素数p=257,这样使得在对像素值进行模运算的时候,尽可能地使得运算结果的范围为0～255,有极小的可能性像素值会上溢.在实际实验时,我们可以对所有像素点进行扫描和标记,在加密后和嵌入水印之前,预先将大于255的像素值修改为255,并对修改位进行标识.然后在解密和提取水印的过程中,根据标识位将像素值修改为原像素值.有时候图像预处理比较繁琐,但是进行图像预处理,能够保证算法准确无误的进行.

3.2 实验结果分析

图3(a)是原始载体图像,图3(b)是利用ElGamal加密系统加密后得到的密文图像,图3(c)是嵌入水印后的密文水印图像,以及图3(d)是解密后的含水印图像,计算得到的PSNR值为24.71 dB,BER值为0.0039.图4分别是原始图像,嵌入水印信息之后的含水印图像和密文含水印图像,以及解密后的含水印图像,图4(b)的PSNR值为51.36 dB,解密后的含水印图像,PSNR值为50.38 dB,BER值均为0,说明能准确提取水印.由实验结果可知,利用本算法无论是在明文域还是在密文域,都能成功提取水印信息,并解密得到原始图像,且解密得到的水印图像质量较高.

图3 加密域下的实验结果图

图4 明文域下的实验结果图

3.3 水印算法的性能测试

为了更进一步评估本算法的试用性和鲁棒性,接下来对再分别选取4 幅256×256 大小的图像(peppers、cameraman、plane、baboon)进行性能评估.根据式(14),计算在不同嵌入容量下得到的水印图像的峰值信噪比,表1是密文域不同嵌入容量下的PSNR,表2是明文域不同嵌入容量下的PSNR值.由表1和表2,可见随着嵌入容量的减小,PSNR值越来越大,并且算法无论是在密文域还是在明文域,在嵌入容量高达0.25 bpp (bpp 表示每像素嵌入的比特数[13])情况下,含水印图像解密后也能获得比较清晰的图像.在明文域下解密得到的PSNR值达到了50.38 dB,很好的恢复了原始图像.

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

与其他加密域的水印算法文献[16]和文献[13]进行比较结果见表3.由表3可见,在无水印攻击时,以256×256的Lena 灰度图像为例,与文献[16]和[13]中的算法比较,本文水印算法在明文域的PSNR 值为50.38 dB,文献[16]和文献[13]的PSNR值分别为48.13 dB和42.81 dB,本文算法求得的PSNR值,高于其他算法,说明提取出的水印图像与原始图像差异较小,水印图像效果较好,水印图像质量得到了改善,同时还能实现密文域下水印的提取,并且本文算法还具有一定的抗攻击性能,由此可见,本文算法的整体性能得到了改善.

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

表3 本文算法与其他文献算法比较

4 结论与展望

本文基于同态加密算法ElGamal 与Patchwork 水印算法,构造了一种新的同态密文域交换加密水印算法,实现了加解密算法和水印算法先后顺序的完全交换.与以前的水印算法相比,本文提出的水印算法既可以保证多媒体数据在存储分发过程中的安全性,也可以保证数据在使用以及认证过程中的安全性.在算法性能方面,实验结果表明,该算法具有较高的嵌入率和峰值信噪比,提取出的水印图像质量较好,因此本文的算法具有一定的研究意义和参考性.

下一步的研究可以寻求更高效的方法解决同态加密域像素溢出的问题,或者提高交换加密域水印算法的鲁棒性,来进一步改善算法的综合性能.