基于秘密共享的可分离密文域可逆信息隐藏算法

周 能,张敏情,林文兵

(武警工程大学 密码工程学院 网络与信息安全武警部队重点实验室,西安 710086)

0 概述

密文域可逆信息隐藏是密文域信号处理技术与信息隐藏技术的重要结合点,其对数据处理过程中的信息安全具有隐私保护与秘密信息传递双重作用,且主要应用于加密数据的管理与认证以及隐蔽通信领域,在医学图像、军事图像和云环境下的数据隐私保护上具有很高的应用价值。近年来,出现了很多密文域可逆信息隐藏算法,如文献[1]提出一种在密文图像上的可逆信息隐藏算法,该算法通过将密文图像分成互不重叠的块,每块有两组,通过翻转相应组中每个像素的3个最低有效位(Least Significant Bit,LSB)并嵌入1 bit信息,接收者通过波动函数提取秘密信息,且分块越小,错误率越高。文献[2]通过使用能够进行边匹配的波动函数对文献[1]算法进行改进。文献[3]提出可分离的密文域可逆信息隐藏算法,使得在加密域和明文域中都能提取出秘密信息。上述密文域可逆信息隐藏算法均需要在图像加密后留出空间进行信息隐藏,导致算法的嵌入率较低,数据提取过程中的错误率较高。文献[4]提出一种在加密前预留空间的密文域可逆信息隐藏算法。文献[5]利用数据嵌入的预测误差来提高算法的可逆性、嵌入容量和图像质量。此外,基于压缩的密文域可逆信息隐藏算法也已被提出,如文献[6]将密文域可逆信息隐藏算法用于JPEG图像,文献[7]将密文域可逆信息隐藏算法用于绝对矩块截断编码图像。

文献[8]提出基于公钥密码的加密信号可逆信息隐藏算法,该算法将1 bit信息嵌入至一对相邻的加密像素中,根据Paillier密码体制[9]加密的同态特性,接收端通过比较所有的解密像素对获得秘密信息,但存在固有的溢出问题。文献[10-11]通过解决固有的溢出问题,实现了对文献[8]算法的改进。文献[10]将不可嵌入位置记为边信息,图像所有者将边信息加密之后发送给数据嵌入者,这样数据嵌入者在嵌入秘密信息时能够避免溢出,文献[11]采取信号能量转移的方法,将图像的像素值分成3个整数来表示,从而避免溢出。文献[12]提出一种可分离的算法,该算法将湿纸编码(Wet Paper Code,WPC)[13]和Paillier同态加密特性相结合,在加密域中利用直方图收缩留出嵌入空间,并使用WPC嵌入秘密信息。文献[14]提出的算法根据嵌入密钥选取目标像素,利用差分扩展的方法将目标像素自嵌入至明文图像中,再利用Paillier加密系统进行加密,从而得到加密图像。文献[15]采用加密前预留空间的方法,利用Paillier密码体制的同态和概率特性,提出一种基于镜像密文组的可分离算法,该算法的平均嵌入率为0.25比特每像素(Bit Per Pixel,BPP),但采用的加密前预留空间方法将会增加明文泄露的风险。

在密文域可逆信息隐藏中,对于流密码加密图像与Paillier密码加密图像,研究与设计算法的过程都是从不可分离发展到可分离的过程。与上述加密算法不同,文献[16]利用Shamir(k,n)门限秘密共享设计了密文域可逆信息隐藏算法。该算法利用秘密共享将原始图像加密成n份,并分别发送给n位不同的数据嵌入者,数据嵌入者通过在密文上进行差值扩展(Difference Expansion,DE)或者差值直方图平移操作嵌入信息,接收者得到少于k份无法恢复的原始图像。文献[17]将多秘密共享加法同态的特点与差值扩展算法[18]相结合进行信息嵌入,该算法将像素值作为多项式的系数,而不是多项式的常数项,降低了算法的时间复杂度。

目前,密文域可逆信息隐藏算法采用的图像加密方式主要包括流密码、Paillier公钥密码与秘密共享3种方式。流密码的密钥流通过伪随机数发生器生成,流密码具有结构简单、运行速度快以及消耗资源少等优势,但是也存在扩散程度不足以及保密通信前需要传递密钥等缺点。采用Paillier公钥密码加密图像能够克服流密码加密需要事先传递密钥的缺点,且能够利用Paillier公钥密码的同态特性在密文域中进行信息的嵌入与提取,但是公钥密码加解密速度较慢、密钥尺寸大也是不容忽视的问题。

针对上述流密码加密方式和Paillier公钥密码加密方式存在的问题,本文选择秘密共享加密方式对图像进行加密,一方面是由于图像所有者不需要向数据嵌入者传递密钥,仅需要向接收者传递密钥,另一方面是由于秘密共享的加解密速度比Paillier公钥密码快。在秘密共享的基础上,本文利用位平面分割技术实现了可分离的密文域可逆信息隐藏算法。

1 相关知识

1.1 秘密共享

1.1.1 Shamir门限秘密共享

Shamir门限秘密共享方案[19]采用的数学原理是拉格朗日插值方程,且其主要思想是利用秘密共享技术将秘密S分成n份,并分布于n个不同的存储和处理中心进行保护,使用其中的k份可以重新还原出秘密S,如果份数少于k,则不能还原出秘密S。数据共享份额被分布式存储于不同的物理位置,这样即使n-k-1个共享被攻击而且已经威胁到系统安全,数据的机密性仍可以保持且可以重构原始数据,从而实现抵抗入侵。

假设q是素数的幂,D是有限域G(q)的本原元,共享的秘密S∈G(q),随机选取G(q)上的k-1次多项式f(x),使得下式成立:

f(x)=S+a1x+a2x2+…+ak-1xk-1

(1)

(2)

f(x)的常数项即秘密S=f(0),每个参与者Di都可利用其掌握的份额Si来验证所求得的f(x)是否正确,从而能够发现其他参与者可能存在的欺骗行为。当份额数量r

1.1.2 多秘密共享

在(k,n)门限秘密共享中,如果每次需要共享d个秘密S1,S2,…,Sd,并且假定攻击者只能得到c(c

定理1存在一个(k-d,d,k,n)多秘密共享方案,能够在n个用户之间共享d个秘密,其中,d≤k

本文设置参数d=t、k=2t、n=2t,且能够提供无条件安全性,下面介绍多秘密共享的加法同态性质。

1)加密性质。随机选择ri∈G(q′),1≤i≤t组成密钥R=(rt,rt-1,…,r1),且秘密信息P=(pt,pt-1,…,p1)由pi∈G(q′),1≤i≤t组成,然后将R和P中的元素设置为多项式f(x)的系数,具体如式(3)所示,采用公共身份D1,D2,…,Dt计算得到f(D1),f(D2),…,f(Dt)作为密文数据,并记为(EncR(p1),EncR(p2),…,EncR(pt))。

f(x)=ptx2t-1+pt-1x2t-2+…+p1xt+rtxt-1+

rt-1xt-2+…+r1x0

(3)

2)同态加法性质。给定st,st-1,…,s1,并作为多项式g(x)的前t项系数,具体如式(4)所示,同样将D1,D2,…,Dt代入式(4)可得到g(D1),g(D2),…,g(Dt),然后计算f′(Di)=f(Di)+g(Di),1≤i≤t,并将其记为(EncR(p′1),EncR(p′2),…,EncR(p′t))

g(x)=stx2t-1+st-1x2t-2+…+s1xt

(4)

3)解密性质。由同态加法性质得到了t个等式,如式(5)所示,由于f′(Di)、Di、rt,rt-1,…,r1均为已知,因此可通过高斯消元法求得z′t,z′t-1,…,z′1,且满足z′i=pi+si,1≤i≤t。

f′(Di)=z′t(Di)2t-1+z′t-1(Di)2t-2+…+z′1(Di)t+

rt(Di)t-1+rt-1(Di)t-2+…+r1(Di)0

(5)

1.2 图像位平面分割

记8位图像矩阵I的大小为M×N,图像像素记为Ii,j,则Ii,j的二进制表示为{bi,j,7,bi,j,6,…,bi,j,0},且有:

(6)

(7)

其中,1≤i≤M,1≤j≤N,⎣·」表示向下取整。图像可用大小为M×N的矩阵I表示:

图像所有者将图像矩阵I按位的从高到低的顺序分解为高位平面矩阵H和低位平面矩阵L,H由前8-v个比特(bi,j,7,bi,j,6,…,bi,j,v)所代表的元素组合而成,L由后v个比特(bi,j,v-1,bi,j,v-2,…,bi,j,0)所代表的元素组合而成。记hi,j与li,j分别表示矩阵H和L中的元素,且满足hi,j∈[0,28-2v],li,j∈[0,2v-1],则有:

(8)

(9)

高位平面矩阵H和低位平面矩阵L分别为:

2 本文算法

2.1 算法框架

基于秘密共享的可分离密文域可逆信息隐藏算法流程如图1所示。图像所有者对原始图像进行位平面分割,选择采用秘密共享体制加密低位平面和多秘密共享体制加密预处理后的高位平面。数据嵌入者在密文低位平面上利用DE算法嵌入秘密信息,在密文高位平面上通过多秘密共享同态加法嵌入秘密信息,接收者在加密域和明文域中都能正确提取出秘密信息,且能够可逆恢复原始图像。

图1 本文算法流程Fig.1 Procedure of the proposed algorithm

2.2 算法过程

2.2.1 预处理

表1 本文算法中参数的对应关系Table 1 Corresponding relation of parameters in the proposed algorithm

本文算法中有两处产生边信息,以图像位平面分割参数v=5为例说明本文对边信息的处理方法。因为v=5,所以hi,j∈[0,224],li,j∈[0,31],则分别对应的有限域大小为q′=223和q=31,且不可嵌入位置有:

1)差值扩展产生不可嵌入位置:当位平面H、L的像素对(x,y)中任一像素的值不在图像灰度值[0,224]、[0,31]内时,则标记为不可嵌入位置。

(10)

图像中的不可嵌入位置是少数的,即位图中少数为1,多数为0,这样可以将位图利用游程长度编码(Run-Length Coding,RLC)压缩后作为边信息嵌入到图像中。图像所有者按以下步骤对图像进行处理:

步骤1将图像分为2个部分,并得到边信息,记为U。

步骤2利用秘密共享加密图像中的第一部分像素,并将密文像素最低有效位标记为X。

步骤3将边信息U通过直接替换图像中的第一部分LSB的方式进行嵌入。

步骤4将X按照本文算法嵌入到图像的第二部分。

数据嵌入者接收到密文图像后,可得到边信息U,然后在图像的第二部分嵌入秘密信息m。通常约定图像的第1行嵌入U、第2行和第3行均嵌入X、其他部分均嵌入m,知道了嵌入的起点和终点,即完成了边信息的处理。

2.2.2 高位平面

若图像有t个像素,则可组成t/2个像素对(xi,yi),i∈[1,t/2],并生成Di∈G(q′),1≤i≤t。图像所有者按照以下步骤对高位平面进行处理:

步骤1密钥生成:随机选择r1,r2,…,rt∈G(q′)组成密钥R=(rt,rt-1,…,r1),只需要将密钥R传递给接收者。

2.2.3 低位平面

若图像有t个像素,则可组成t/2个像素对(xi,yi),i∈[1,t/2],并按以下步骤处理低位平面:

步骤2图像加密:对每个像素对(xi,yi),随机选择ai,bi∈G(q),1≤i≤k-1并构成式(11)中的2个多项式,计算Yi=f1(Di),Y′i=f2(Di)得到密文像素,记为EncK(xi)=Yi,EncK(yi)=Y′i。

f1(x)=xi+a1x+a2x2+…+ak-1xk-1

f2(x)=yi+b1x+b2x2+…+bk-1xk-1

(11)

2.2.4 算法实例

f(x)的常数项f(0)=6,同样计算另一个拉格朗日插值方程可得到f(0)=4,因此得到原始像素对为(6,4)。

3 仿真实验与结果分析

为测试本文算法的性能,本文选用USC-SIPI图像库中大小为512×512的256级灰度图像进行实验,实验环境为CPU为Intel®CoreTMi7-5500U @ 2.40 GHz,RAM为4 GB,OS为Windows 10,Programming为MATLAB R2015b。

本文算法对Lena图像的实验过程如图2所示。

图2 本文算法对Lena图像的实验过程(v=5)Fig.2 The experimental process of Lena image by the proposed algorithm(v=5)

3.1 嵌入率与峰值信噪比分析

可逆信息隐藏通常采用峰值信噪比(Peak Signal to Noise Ratio,PSNR)[21]评价直接解密图像的质量或失真情况,PSNR的计算方法为:

(12)

其中,MSE(Mean Square Error)是原始图像和嵌入信息后图像之间的均方根误差,MSE的计算方法为:

(13)

其中,M×N是图像大小,Ii,j是原图像的像素值,Ci,j是嵌入信息后图像的像素值。

本文算法对Lena图像和Man图像的嵌入率实验数据如表2、表3所示。从表2、表3可以看出,在相同的嵌入容量下,参数v的大小对嵌入率影响较大,这是由于参数v的变化导致图像中不可嵌入像素的个数发生变化,当v=5时,本文算法的嵌入率最高。为了更加直观地展现在相同嵌入率下,直接解密图像的PSNR性能,图3、图4分别给出了图像Lena和图像Man的PSNR值曲线。从图3、图4可以看出,当参数v=5时,图像的PSNR性能最好,因此本文算法的最优参数为v=5。为了更好地分析本文算法性能,选择在最优参数条件下的实验数据与其他算法进行对比,本文算法与文献[3,15,17]算法在图像Lena和图像Man上的实验数据对比结果如图5、图6所示。从图5、图6可以看出,当嵌入率相同时,本文算法的PSNR值比文献[3]高,这是因为文献[3]采用流密码加密图像后只是压缩图像的最低有效位,算法的嵌入率完全取决于压缩效率,而且对图像造成的失真也较大。文献[15]采用加密前预留空间的方法,将部分位平面数据通过可逆信息隐藏算法自嵌入到图像的其他部分中,从而转化为密文域中的嵌入容量,有效降低了直接解密图像的失真情况,因此文献[15]算法的PSNR性能比本文算法好。然而,文献[15]利用Paillier公钥密码加密图像,算法的时间复杂度比本文算法高。虽然文献[17]的算法PSNR性能比本文算法好,但文献[17]仅利用多秘密共享加密图像,不能直接从密文域中提取信息,没有实现算法的可分离。

图5 4种算法对Lena图像的PSNR性能对比Fig.5 PSNR performance comparison of four algorithms for Lena image

图6 4种算法对Man图像的PSNR性能对比Fig.6 PSNR performance comparison of four algorithms for Man image

表2 本文算法对Lena图像的实验数据比较Table 2 Experimental data comparison of Lena images by the proposed algorithm

表3 本文算法对Man图像的实验数据比较Table 3 Experimental data comparison of Man images by the proposed algorithm

图3 不同参数下Lena图像的PSNR性能对比Fig.3 Comparison of PSNR performance of Lena images with different parameters

图4 不同参数下Man图像的PSNR性能对比Fig.4 Comparison of PSNR performance of Man images with different parameters

3.2 算法综合性能分析

密文域可逆信息隐藏算法多数采用流密码和Paillier公钥密码加密图像,而本文算法采用秘密共享以及多秘密共享加密图像,下面将对这三类算法进行详细的对比分析。

1)时间复杂度。文献[3]利用流密码加密和解密一个像素的时间复杂度是O(1),文献[15]利用Paillier公钥密码加密和解密一个像素的时间复杂度是O(n3),本文算法利用秘密共享加密和解密一个

像素的时间复杂度分别为O(n)和O(nlbn)。

2)数据扩展率。数据扩展是指原始图像在利用密码算法加密后有较大的密文扩展,而数据扩展率(Data Expansion Rate,DER)可以用来定量描述密文扩展的大小,DER的计算方法为:

(14)

其中,Ao表示原始图像的所有比特数,Ae表示密文图像的所有比特数。

当采用如文献[3]中的流密码算法时没有数据扩展,因此DER为1;当采用如文献[15]中的Paillier公钥密码算法时,其数据扩展较大,灰度图像的像素值为8 bit,如果使用512 bit的密钥,密文像素值为1 024 bit,因此DER为128;虽然文献[17]采用的是多秘密共享加密,但是将8 bit的灰度图像仍然加密为8 bit的密文图像,因此DER同样为1。本文算法利用秘密共享加密低位平面与多秘密共享加密高位平面,将1个像素加密为n个密文像素,因此DER为n。本文算法与文献[3,15,17]算法的特征比较如表4所示。

表4 本文算法与文献[3,15,17]算法的特征比较Table 4 Comparison of the characteristics between the proposed algorithm and those in references[3,15,17]

4 结束语

基于秘密共享的可分离密文域,本文提出一种可逆信息隐藏算法,并结合秘密共享方案和位平面分割技术,达到了分散风险和抵抗入侵的目的,同时,分别在高位平面与低位平面上嵌入信息,从而提高算法的嵌入容量。实验结果表明,与其他可分离算法相比,本文算法在较低嵌入容量时有较高的PSNR值,但是随着嵌入容量的增加,PSNR值下降较快,这是由低位平面造成的失真越来越大引起的。下一步将利用中国剩余定理对图像进行加密,以解决失真问题,提升高嵌入容量时的PSNR值。