马利民，王佳慧

（1. 北京信息科技大学计算机学院，北京 100101；2. 国家信息中心信息与网络安全部，北京 100045）

1 引言

网络技术的高速发展对于数据传输具有重要意义，然而如何保证秘密数据在网络上的传输安全已成为一个亟待解决的问题。秘密图像共享技术可以将需要安全存放及传输的秘密图像按照一定方法进行划分并分别交给不同管理人。假设目标秘密图像被划分为n个图像，只有同时拥有其中的t(2≤t≤n)个划分图像时，才能恢复出秘密图像，防止秘密过于集中，达到一定的安全性；另一方面，如果有划分图像丢失或者损坏，只要剩余的划分图像个数大于或等于t，仍然可以恢复秘密图像，因此该技术对安全风险具有一定的容忍性。隐写术是信息隐藏技术的一种，用于实现数字内容在网络中的安全存放及传输[1-2]。基于隐写术的秘密图像共享将n个共享图像嵌入n个载体图像当中，生成n个含密图像，通过传输含密图像达到安全传输秘密图像的目的。

Shamir[3]首次提出了基于拉格朗日多项式内插原理实现的秘密共享技术，又称为(t,n)-门限秘密共享技术。Thien等[4]基于(t,n)-门限秘密共享技术提出了秘密图像共享的概念，其中，秘密图像中的每一个像素作为一个秘密信息，与文献[3]不同，他们将(t-1)次多项式的每一个系数均用于携带秘密信息，因此生成的每一个划分图像的大小是原始秘密图像大小的此后的一些秘密图像共享方案大都是为了减小生成的划分图像而设计的，如文献[5-6]。Wang等[5]提出将哈夫曼编码应用于秘密图像的差分图像编码以减少划分图像。Lin等[6]提出了一种基于隐写术的秘密图像共享方案，将产生的噪声隐藏在多幅载体图像中。基于文献[6]提出的算法框架，后续研究人员提出了许多基于隐写技术的秘密图像共享方案[7-13]。其中，Amir等[7]利用 OAEP（optimal asymmetric encryption padding）和 IDA（information dispersal algorithm）进一步提高了共享秘密图像的密钥的安全性，并采用 FEMD（fully exploiting modification direction）隐写算法提高了隐写图像质量。Jamal等[8]通过在共享图像时利用细胞自动机技术来替代上述基于拉格朗日多项式内插原理实现的秘密共享技术，取得了更好的隐写图像质量。上述算法性能较好，但存在的共同问题是载体图像不可恢复，假如载体图像是一些敏感图像（例如军事图像、医学图像），考虑到载体图像的实用价值，应尽量避免这种情况发生。因此，可逆的秘密图像共享技术更具有实用性。

可逆秘密图像共享方法设计过程中，需要考虑载体图像的恢复，因此在秘密共享阶段，需要将载体图像的一些特征信息连同秘密图像一起生成含密图像。这样就可以在秘密图像恢复阶段，利用载体图像特征信息恢复载体图像。对于此类算法，一方面，特征信息提取越少生成的划分图像越小，嵌入载体图像后生成的含密图像质量越高；另一方面，隐写术算法性能的优劣也将决定含密图像的质量。因此，基于隐写术的秘密共享算法需要同时注重这两方面的因素。Lin等[14]提出一种基于模运算的可逆秘密图像共享机制，该机制利用（t-1）次多项式的t系数中的■logm255■个系数来携带载体图像中像素的值，剩余的系数则用来携带秘密数据。随后，Lin等[15]又提出一种能提高嵌入秘密数据量的改进方案，但是这2种方案都需要解决溢出问题[16]。Feng等[17]基于(t,n)-门限秘密共享技术提出一种可逆的主动式秘密图像共享方案，可以实现对生命周期较长的秘密图像进行安全保护，但是生成的含密图像质量有待提高。Liu等[18]提出一种针对 H.264的可逆数据共享方案，通过在空间域嵌入秘密信息，但是嵌入数据量较小。

目前，基于隐写术的可逆秘密图像生成的含密图像质量不高，本文针对此问题提出了一种高质量的基于隐写术的可逆秘密图像共享算法，并通过实验进行分析比较。实验结果表明，本文提出的算法可以生成高质量的含密图像，同时可以无损恢复载体图像，在保证秘密图像安全存放的同时增强了其在网络传输的安全性。

2 相关工作

2.1 秘密共享技术

1979年，Shamir[3]首先提出(t,n)-门限秘密共享技术，该技术基于拉格朗日多项式内插原理实现[19-20]。如果要保护的秘密为s，则采用(t,n)-门限秘密共享方法进行秘密共享，具体实现步骤如下。

1) 根据式(1)生成一个(t-1)次多项式。

其中，t≥2，GF (p)是一个有限域，p是一个素数或者p=2m，a0=s，a1,a2, …,at-1是随机选择且分布在[0,p-1]范围内的整数。

2) 根据n个参与者选定的密钥X={x1,x2, …,xi,…,xn}生成n个划分y1,y2, …,yi,…,yn。

其中，n≥t。将yi交由对应的参与者进行保管。

恢复秘密信息s时，需随机选择t个划分，即y1,y2, …,yt，基于拉格朗日多项式内插方法重建多项式F(x)，如式(2)所示，其常数项系数即是秘密信息s的值。

2.2 FEMD算法

在基于隐写术实现可逆秘密图像共享方案中，特征提取方法和隐写算法是决定含密图像质量好坏的关键因素。Kieu等[21]给出了一种很好的隐写算法——FEMD算法，但是由于嵌入过程中存在多对一的映射关系及溢出像素问题，该算法无法实现载体图像的恢复。

FEMD算法的基本思想是将一个s2进制数嵌入一个像素对(ai,ai+1)中，嵌入过程中对ai或者ai+1的最大改变量为其中 0 ≤a,a≤ 255。当ii+1s值固定时，算法的最大嵌入量为因此s值越大，最大嵌入量越大，但嵌入失真也就越大。基于FEMD算法将s2进制系统中的一个数d嵌入像素对(ai,ai+1)中得到含密像素对(bi,bi+1)，具体步骤如下。

步骤1 定义提取函数F(xi,xi+1)如式(3)所示。

步骤2 建立一个256×256的映射矩阵M，如式(4)所示。

步骤3 根据式(3)计算(ai,ai+1)的提取函数值F(ai,ai+1)。

步骤4 若F(ai,ai+1) =d，(bi,bi+1)= (ai,ai+1)，嵌入结束；否则执行步骤5。

步骤5 在映射矩阵M中定义一个以(ai,ai+1)为中心的方形搜索框W，如式(5)所示。

步骤6 扫描搜索框中的每一个元素，使M[p][q]=d。若满足条件的像素对(p,q)不止一个，则选择具有最小嵌入失真D的像素对赋值给(bi,bi+1)，其中，D根据式(6)进行计算。

在提取端，根据参数s来定义提取函数F(xi,xi+1)，s需要通过一种安全保密的方式传递给提取端。假设提取端接收到的像素对为 (bi′,bi′+1)，则嵌入的秘密数据d′ =F(bi′,bi′+1)。

通过研究 FEMD算法发现，对于大部分像素对，可以通过将原始像素对的提取函数值作为秘密信息嵌入含密像素对中恢复原始像素对的值。但是对于有些像素对则不可恢复，本文称之为问题像素对。问题像素对可以分为2类，第一类是由嵌入秘密信息时可以对应不同含密像素对的问题像素对组成；第二类是由溢出像素对构成，所谓溢出像素对是指像素对中至少有一个像素的值落在区间[0,r)∪(255-r, 255]。

对于第一类问题像素对，其嵌入过程是一个一对多的映射，例如当s=4时，所建立的映射矩阵M如图1所示。选择的像素对(ai,ai+1) = (4, 5)，浅灰色矩形框为根据式(5)构建的方形搜索框W，深灰色标注位置为所要嵌入的秘密数据d=11，按照FEMD算法嵌入数据后得到的含密像素对的值为(bi,bi+1)=(5, 3)或者(bi,bi+1)=(5, 7)，此时无法通过FEMD算法将F(ai,ai+1) 的值嵌入(bi,bi+1)中来恢复(ai,ai+1)的值。对于第二类问题像素对，即溢出像素对，采用FEMD算法在一个像素对(ai,ai+1)中嵌入秘密数据时，可能无法从搜索框W(s,(ai,ai+1),r)中找到一个元素等于所要嵌入的秘密数据。因此，FEMD算法在一个载体图像中嵌入秘密数据之前，将位于区间[0,r) 和 (255-r, 255]的所有数据作为溢出像素，分别用r和255-r来替换，然后在修改后的像素中嵌入秘密信息。这样对溢出像素对的修改过程是一个多对一的映射，因此根据修改后数值无法知晓原始溢出像素的值。

图1 当s=4时FEMD算法中构建的映射矩阵M

FEMD算法作为一种隐写术算法，实现了较高的嵌入量和较好的含密图像质量，此后 Kuo等[22]对其进行了改进，提出一种新的隐写术算法，在秘密数据嵌入载体像素时，利用数学式计算含密像素。Kuo等[23]提出一种基于 FFEMD（formula FEMD）算法和像素值差分办法来克服溢出问题。这些算法大多只是改进隐写术的性能而没有在秘密共享方面进行设计。

3 可逆秘密图像共享算法的设计

3.1 改进FEMD算法

针对 FEMD算法处理过程中遇到的问题像素对，本文从嵌入过程和溢出像素对处理两方面解决像素对的可逆性恢复问题。

3.1.1 改进的FEMD算法嵌入过程

在采用FEMD算法嵌入秘密数据时，需按照一定方向遍历搜索框，使原始像素对和嵌入后含密像素对成为一对一的映射。对FEMD算法嵌入过程的步骤6改进如下。

步骤6按照图2 (a)中所示方向遍历搜索框，嵌入过程为自左至右，扫描到最右边后从下一行最左侧开始继续遍历，直到找到满足条件M[p][q]=d且具有最小嵌入失真D的像素对(p,q)，如果这样的像素对不止一对，则将最先扫描到的像素对赋值给(bi,bi+1)。

在使用改进 FEMD算法进行秘密信息嵌入后，利用提取函数F(ai,ai+1)和s就可以从含密像素对(bi,bi+1)中恢复原始像素对(ai,ai+1)。但恢复时需按图 2(b)中所示方向进行遍历，与嵌入时扫描方向相反。

图2 扫描方向

3.1.2 溢出像素对处理

为每一个溢出像素对分配一个溢出标志位 sf来记录其原始状态，然后分别用r和255-r替换溢出像素对的值。为了唯一地恢复原始像素对的值，本文在对溢出像素对(ai,ai+1)设计溢出标志位sf时，分为2种情况进行处理。

1)ai和ai+1的值都属于区间

2) 像素对中只有一个数位于区间[0,r]∪[255-r, 255]

如果一个溢出像素对(Rj,Rj+1)经上述方法处理后，像素对为 (R′j,R′j+1)，溢出标志位为sf，那么根据(R′j,R′j+1)和sf可以通过下面的方法恢复(Rj,Rj+1)。

1) 若R′j,R′j+1∈{r,255 -r}，(Rj,Rj+1)可以根据式(9)计算得到。

2) 若Rj′和R′j+1中只有一个数等于r或者255-r，为解释方便，本文将等于r或者 255-r的数据表示为X′，另一个数据表示为Y′，其相应的原始像素的值分别表示为X和Y，那么Y= Y′，X可以根据式(10)计算得到。

通过上述对溢出像素对的处理方法可以实现基于改进的 FEMD算法来恢复原始溢出像素对的值，实现载体图像的无损恢复。

3.2 秘密图像共享及嵌入

在本文提出的方法中，用一幅灰度图像作为载体图像，利用(t,n)-门限秘密共享技术来生成共享划分，最后基于改进FEMD算法将生成的共享划分单独地嵌入一幅载体图像中形成n个含密图像。为了恢复原始载体图像的值，提取端需要知道载体图像的所有像素对的特征值。对于载体图像的每个像素对，根据式(1)构建(t-1)次多项式时，需要根据3.1节提出的算法，利用一个或 2个系数存储该像素对的特征值，用剩余的系数来携带来自于秘密图像的秘密信息。在实现方案中，采用基于 2m的有限域GF (2α)来构建(t-1)次多项式，为此需要将秘密图像中的每个像素采用 2α进制数来表示。对于参数为s的改进FEMD算法，其可嵌入的秘密数据的数值落在[0,s2)，为了兼容，采取的有限域GF (2α)算法中要求2α=s2，因此本文中α=s=2或者α=s=4。

假设秘密图像I大小为hs×ws，宿主载体图像C大小为hc×wc，n个参与者所对应的n个互不相同的密钥表示为X={x1,x2, …,xn}，则基于改进的FEMD可逆秘密图像共享方案的共享及嵌入流程如图3所示，算法过程如下。

1) 将I中的数据重新排列为一维矢量

图3 可逆秘密图像共享及嵌入流程

2) 将S中的每一个像素用进制数表示 ， 进 而 形 成 一 个 矢 量S′ ={d1,d2,… ,dl,… ,其中，

3) 顺序化遍历C中的每一个像素，将相邻 2个像素作为一个像素对(ci,ci+1)。

4) 若(ci,ci+1)是溢出像素对，按照式(7)或式(8)计算溢出标志位sf，然后利用式(3)计算经溢出过程处理后的修改像素对的提取函数值f；否则，直接计算(ci,ci+1)的提取函数值f。

5) 若(ci,ci+1)是溢出像素对，从S′中顺序选择(t-2)个连续的 2α进制数，形成划分片段否则，从S′中顺序选择(t-1)个数据，形成划分片段

6) 若(ci,ci+1)是溢出像素对，利用f、sf和(dsj, dsj, … , d sj)构建式(11)。

1 2t-2

否则，构建式(12)。

7) 将n个密钥xk分别代入Fj(x)中得到Fj(xk)，其中，k∈[1,n]。

8) 对于每个Fj(xk)，k∈[1,n]，基于改进FEMD算法单独嵌入(ci,ci+1)中得到含密图像 SIk中对应的含密像素对。

9) 重复执行步骤 3)～步骤 8)，直到S′中的所有数据处理完毕。

10) 至此，若载体图像中尚有剩余像素对没有嵌入数据，则直接将剩余的像素对复制到含密图像SIk的对应位置。

经过上面的处理，可以得到n个大小为hc×wc的含密图像SIk，k=1, 2, …,n，这n个含密图像将由相应的参与者保管。另外，由于提取端需要知道秘密图像大小hs×ws和参数s才能恢复出秘密图像和载体图像，这2个信息将作为算法的私钥通过一种安全的方式发送给提取端。

3.3 秘密图像提取和载体图像恢复

根据(t,n)-门限秘密共享技术原理，恢复出共享的秘密图像至少需要t个不同的含密图像，假设所提供的含密图像是SI1,SI2, …, SIt，对应的参与者所拥有的密钥分别是x1,x2, …,xt，则提取端进行秘密图像提取和原始载体图像恢复的过程如下。

1) 对于每个含密图像SIi，i=1, 2, …,t，顺序选择 2个相邻的像素作为一个像素对根据式(3)计算其提取函数值fi。

2) 根据步骤1)得到的t组数据(xi,fi)，i=1, 2, …,t，来重建多项式F(x)，如式(13)所示，其中α=s。

3) 根据共享过程可知，a0所承载的信息就是原始载体图像对应像素对（或修改后溢出像素对）的提取函数值，因此根据的值，利用3.1节中给出的原始像素对恢复方法即可得到之前像素对的值，这里用来表示。根据a0和的值以及恢复算法计算得到

4) 通过以下步骤提取秘密图像和恢复载体图像中像素对(Rj,Rj+1)的值。

① 如果R′j和R′j+1都不等于r或者 255-r，则说明宿主载体中的原始像素对不是溢出像素对，此时(Rj,Rj+1)的值等于 (R′j,R′j+1)的值。因此，重建多项式F(x)中系数(a1,a2, …,at-1)均承载的是秘密数据。

② 如果R′j和R′j+1之间至少有一个等于r或者255-r，则说明宿主载体中的原始像素对是溢出像素对。根据嵌入过程可知，系数a1所承载的是溢出标志位的信息，其他系数(a2,a3, …,at-1)承载的是秘密信息。这时可以根据溢出标志位a1和 (R′j,R′j+1)的值来恢复原始像素对(Rj,Rj+1)的值。

5) 重复执行步骤 1)～步骤 4)，直至所提取出的秘密数据个数为然后将含密图像SI1中的剩余像素直接赋值给载体图像中的相应位置处，即可恢复宿主载体图像。

4 实验结果及分析

首先，为了分析所提算法对不同载体图像进行处理后得到的含密图像的质量，在模拟实验中本文使用10幅512像素×512像素的灰度图像作为作载体图像来测试算法性能，根据有限域GF (2α)算法中要求 2α=s2，改进 FEMD 算法中的参数s=α=4。对于本文算法来说，可供嵌入的秘密图像的最大尺寸为实验中选取的秘密图像是300像素×300像素的图像，如图4所示，因此需设置实验参数为t=3，n=3。对于基于隐写术实现秘密图像共享的算法，生成的含密图像失真越小，在网络中传输时越不易被攻击者察觉，安全性越好。本文用PSNR（peak signal to noise ratio）指标来衡量得到的含密图像质量。

图4 秘密图像（300像素×300像素）

表 1为 10幅图像作为载体图像使用改进的FEMD算法得到含密图像的PSNR结果。此外，图5展示了Lena图像作为载体图像时得到的3幅含密图像。从表1及图5可以看出，在以上实验条件下，嵌入的秘密图像大小为300像素×300像素，本文提出的改进FEMD算法可以取得高达48 dB的含密图像质量，同时肉眼无法看出含密图像与原始载体图像的差别，因此所提算法具有良好的不可见性。

其次，为了进一步比较分析算法性能，将本文算法与文献[15-17]算法进行比较。其中，为使对比算法可以取得最好的结果，并保持相同的实验条件，即嵌入的秘密图像为 300像素×300像素的图像，在实现文献[15]算法时将其参数m设置为3，将文献[16]算法中参数α设置为2，将文献[17]算法中参数设置为t=7，m=3。表2是实验数据对比，就含密图像质量来说，本文算法相比文献[15]、文献[16]和文献[17]中算法可以分别实现 6.4 dB、2.8 dB和0.57 dB的性能提高。

表1 含密图像质量

图5 含密图像质量评估

对于本文算法，当t=3，s=4时，采用本文算法共享和嵌入一个 8 bit数据在一个像素上所引入的误差可以通过式(14)计算得到，为1.375。采用文献[15]算法和文献[16]算法，实现一个8 bit数据的共享和嵌入时，在载体图像的一个像素上引入的误差可以分别通过式(15)和式(16)来计算，当t=3，m=3，α=2时，引入的误差分别为 5和 2.5。因此本文算法得到的含密图像质量比较好。本文算法可以为秘密图像的安全存放和传输提供一种很好的一体化解决方案。

表2 算法性能比较

5 结束语

本文重点分析了基于隐写术的可逆秘密图像共享方案，提出了一种基于改进FEMD算法的可逆秘密图像共享算法。作为一种隐写算法，由于嵌入过程及在对溢出像素处理时的不唯一性，FEMD算法无法实现可逆秘密图像共享方案设计。本文从嵌入过程和对溢出像素对处理两方面来改进 FEMD算法，并利用改进的FEMD算法设计了一种基于隐写术的可逆秘密图像共享方案。实验结果表明，本文提出的算法可以生成高质量的含密图像，在保证秘密图像安全存放的同时增强了其在网络传输的安全性，具有较高的实用性。