周 能， 张敏情， 刘蒙蒙

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

可逆信息隐藏作为一种维护网络空间安全的重要技术手段，在网络安全通信、数字版权保护等领域发挥着重要作用。Shi等[1]较为完整地总结了过去二十年可逆信息隐藏算法的发展历程，可逆信息隐藏主要有无损压缩、差值扩展和直方图平移。可逆信息隐藏本身比较复杂，需要确保载体的可恢复性，以及嵌入信息的完整提取，而加密域可逆信息隐藏又需要进一步处理好解密和提取信息之间的关系。Zhang[2]首次提出密文图像可逆信息隐藏算法，该算法用流密码加密图像，类似的算法还有文献[3-5]。虽然流加密的计算复杂度低、加解密速度快，但是有密钥传递、密钥管理等方面的问题。Chen等[6]首次提出了基于公钥密码的加密域可逆信息隐藏，利用公钥密码的特点克服对称加密需要安全通道事先传递密钥的缺点，该算法将1 bit信息嵌入到一对相邻加密像素中，根据Paillier密码体制加密的同态特性，接收端通过比较所有的解密像素对获得秘密信息，后来继续进行研究创新的主要文献有[7-9]。利用公钥密码可以大大减少密钥量，且无须事先传递密钥，可是也带来了较大的密文扩展，且计算复杂度高。比较好的方法是对密文冗余进行重量化与再编码嵌入秘密信息，相关文献有[10-12]。

与上述文献中的方法不同，Wu等[13]首次利用Shamir(k,n)门限秘密共享设计了加密域可逆信息隐藏算法。该算法利用秘密共享将原始图像加密成n份，分别发送给n位不同的数据嵌入者，数据嵌入者通过在密文上进行差值扩展或差值直方图平移操作嵌入信息，接收者得到少于k份时无法恢复原始图像。实际上，文献[13]的方法将一个像素加密成了n份，那么一个密文像素就扩展成8nbits。而Chen等[14]利用的是多秘密共享加法同态的特点结合差值扩展算法[15]进行信息嵌入，该算法将像素值作为多项式的系数而不是多项式的常数项，因而降低了算法的时间复杂度。本文在Chen算法的基础上应用了Shamir(k,n)门限秘密共享的优点，首先用Shamir秘密共享体制把图像加密成n份，并分发给n个不同的存储和处理中心；每个存储和处理中心执行同样的嵌入策略，即利用Shamir秘密共享体制的加法同态特性嵌入信息；当持有k份额，就可以完成原始图像的可逆恢复。

1 Shamir门限秘密共享体制的构造

Shamir提出了一种基于多项式的拉格朗日插值公式的门限秘密共享方案[16]。

设q是素数的幂，ID是有限域GF(q)的本原元，共享的秘密是D∈GF(q)，随机选取GF(q)上的k-1次多项式f(x)，使得：

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

(1)

假设n个参与者能够正确提供k个份额Di(i=1,2,…,k)，则根据拉格朗日插值公式得到

(2)

则f(x)的常数项，即秘密D=f(0)，并且每个参与者IDi都可利用自己掌握的份额Di来验证所求得的f(x)是否正确，从而能够发现其他参与者可能存在的欺骗行为。

当份额数量r

2 基于秘密共享的同态加密图像可逆信息隐藏算法

秘密共享可作为一种保护图像隐私的加密方法，以Shamir(3, 5)门限秘密共享为例研究本文算法的实现，图1显示了秘密共享在用户和云端之间的应用流程。用户利用身份IDi(i=1,2,…,5)将原始图像加密成5份密文图像，然后把这5份密文图像分别上传给不同的存储和处理中心，此外，用户需要将身份ID1～ID5通过安全的方式分别发送给5个不同的存储和处理中心，即存储和处理中心1拥有ID1，存储和处理中心2拥有ID2，…，存储和处理中心5拥有ID5。这样存储和处理中心就能够用身份对要嵌入的数据进行加密，而后应用Shamir门限秘密共享的加法同态进行信息嵌入。最后，合法的接收者只要有3个以上的份额就可正确解密。

图1 秘密共享在用户和云端之间的应用Fig.1 Application of secret sharing between users and cloud

算法中，密文图像分别由不同的存储和处理中心保管，部分存储和处理中心被人为攻击破坏或自身故障不会泄露密文图像。假设攻击者Adversary无法获得2个以上的份额，那么算法就是安全的。

2.1 算法框架

以一对像素为例来演示总体框架，设有限域的大小为251，即q=251，图2所示为基于秘密共享的同态加密图像可逆信息隐藏算法流程图。图像所有者首先按照差值扩展的方法预处理原始像素对，然后用秘密共享加密得到5对密文像素，最后将5对密文像素分别上传给5个不同的存储和处理中心；数据嵌入者将要嵌入的信息1转成(1, 0)，而后按照同样的方式加密得到密文信息，接着将密文信息与密文像素相加得到携密密文像素，实际上5个存储和处理中心执行同样的嵌入策略；合法的接收者获得3个以上的份额就可以重构拉格朗日插值多项式正确解密并提取嵌入的信息。

图2 所提算法流程图(以t=2，即一对像素为例)Fig.2 The sketch of the proposed algorithm(take t=2 as an example, which is a pair of pixels)

2.2 算法过程

2.2.1 密钥生成

2.2.2 图像加密

(1)生成t个2次多项式用于加密图像fi(x)=r2i-1x2+r2ix+pi(mod251),i∈[1,t]。

2.2.3 信息嵌入

2.2.4 解密并提取信息

2.2.5 举例说明算法具体过程

数据嵌入者实际上是5个存储和处理中心，它们执行同样的嵌入策略。都是将秘密信息m=1扩展为一对(1, 0)，然后利用和图像所有者同样的方式得到密文信息(18, 12)、(54, 30)、(112, 54)、(189, 84)和(35, 120)。5个存储和处理中心分别将密文信息与密文像素相加得到携密密文像素(139, 122)、(212, 158)、(76, 206)、(230, 15)和(173, 87)。

接收者获得3份携密密文像素就可以重构拉格朗日插值多项式，计算携密明文像素为(105, 98)，根据差值扩展的性质，因为(105+98)mod2=1，所以提取秘密信息为1，最后恢复原始像素值为(103, 100)。

2.3 边信息处理

在可逆信息隐藏中，边信息在可逆恢复过程中十分重要，因而采用标准的边信息处理方式。本文算法有两处产生边信息。

(1) 差值扩展产生不可嵌入位置：当像素对(x′i,y′i)中任一像素不在图像灰度[0, 255]的范围内，标记为不可嵌入位置。

可用位图的方法，即式(3)来标记这些不可嵌入位置：

(3)

图像中的不可嵌入位置是少数，即位图中1是少数，大多数是0，这样可以将位图压缩后作为边信息嵌入到图像中。图像所有者按下列步骤处理图像。

(1)将图像分为两部分，并得到边信息，记为I。

(2)利用秘密共享加密图像第一部分的像素，并将密文像素最低有效位(least significant bit, LSB)标记为L。

(3)将边信息I通过直接替换图像第一部分LSB的方式进行嵌入。

(4)将L按照本文算法嵌入图像的第二部分。

数据嵌入者收到密文图像后，可得到边信息I，然后在图像的第二部分嵌入秘密信息S。通常约定图像的第1行嵌入I、第2行和第3行嵌入L、其余部分嵌入S。这样就可以知道嵌入的起点和终点，至此完成了边信息的处理。

3 仿真实验与理论分析

为测试本文算法性能，选用USC-SIPI图像库中大小为512×512的6幅标准测试灰度图像，如图3所示，并用MATLAB R2015b编程进行仿真实验。

图3 标准测试图像Fig.3 Standard test images

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

峰值信噪比(peak signal-to-noise ratio, PSNR)通常被用来评价载体图像质量，根据人类视觉系统的特点，通常认为PSNR>35 dB时，人眼觉察不到图像有明显的失真，PSNR可由式(4)计算。

(4)

式(4)中：MSE(mean square error)是原图像和嵌入信息后图像之间的均方误差，可由式(5)计算：

(5)

式(5)中：MN是图像大小；p(i,j)表示原图像的像素；c(i,j)表示嵌入信息后图像的像素。

图4给出了6幅标准测试图像在不同嵌入率(embedding rate, ER)下的PSNR，本文算法的嵌入率由式(6)得到。

图4 所提算法的性能Fig.4 Performance of the proposed algorithm

(6)

式(6)中：L表示图像像素个数；N表示图像中不可嵌入的像素个数。图5给出了不同算法对Lena图进行实验的数据对比。表1列出了6幅标准测试图像不可嵌入像素个数以及最大嵌入率。

表1 最大嵌入率

图5 Lena图像性能对比Fig.5 Comparisons on Lena

因为文献[4]采用加密前预留空间的策略进行信息嵌入，有效降低了直接解密图像的失真，所以其PSNR要高于本文算法；文献[8]将Paillier公钥加密和湿纸编码相结合进行两次信息嵌入，当嵌入率较低时，其算法性能要稍优于本文算法，但是随着嵌入容量的增加，两次信息嵌入给图像带来的失真也越来越大，从而导致PSNR下降较快；文献[9]同样在加密前预留了部分位平面数据，而后利用Paillier的同态加法在镜像密文组的目标像素上嵌入信息，可是该算法构造镜像密文组的方法给图像造成的失真较大，因而本文算法的PSNR要高于文献[9]；文献[14]和本文算法都是结合差值扩展算法进行信息嵌入提取，所以算法性能较为接近。

图6给出了利用本文算法对Lena图像进行加密得到的加密图像份额、直接解密后的携密明文图像和无损恢复的图像。嵌入容量为130 989 bits，直接解密图的PSNR为33.151 dB。

图6 Lena测试图像及加密图像Fig.6 The testing Lena image and encrypted images

3.2 算法综合性能分析

当前，加密域可逆信息隐藏中利用最为广泛的加密方式是流加密和Paillier公钥加密，为了对比分析的全面性，选择采用流加密和Paillier公钥加密的两种典型加密域可逆信息隐藏算法与文献[14]、本文算法进行性能对比分析。

时间复杂度：利用流密码加密和解密一个像素的时间复杂度是O(1)；利用Paillier公钥密码加密和解密一个像素的时间复杂度是O(n3)；利用秘密共享加密和解密一个像素的时间复杂度分别是O(n)和O(nlog2n)。

数据扩展：数据扩展是指原始图像在加密后有较大的密文扩展。利用流密码的算法没有数据扩展，如文献[4]，所以数据扩展为1；利用Paillier公钥密码的算法数据扩展较大，如文献[8-9]，灰度图像的像素值是8 bits，如果使用512 bits的密钥，密文像素值为1 024 bits，所以数据扩展为128；虽然文献[14]利用的是多秘密共享加密，但是将8 bits的灰度图像仍然加密成8 bits的密文图像，所以数据扩展同样为1，因而在恢复原始像素时并未体现出秘密共享的特性；本文算法利用的是Shamir(3, 5)门限秘密共享，把1个像素加密成5个密文像素，所以数据扩展为5，虽然数据扩展比文献[14]要高，但是任意3个密文像素都能够恢复出原始像素，体现出了秘密共享的思想。表2给出了所提算法与相关算法的特征比较。

表2 所提算法与相关算法的特征比较

4 结论

本文算法利用Shamir秘密共享体制加密图像，而后利用其满足的加法同态特性进行信息嵌入，通过对算法的理论分析与仿真实验得到以下结论。

(1)利用秘密共享加密图像达到了分散风险和容忍入侵的目的，与此同时，利用的差值扩展算法嵌入率高且能够实现完全可逆。

(2)本文算法的时间复杂度要比利用Paillier公钥密码加密图像的时间复杂度低，且数据扩展小。