计算机系统应用  2021, Vol. 30 Issue (11): 266-272   PDF    
基于Arnold置换的交换加密水印算法
赵培越, 张珍珍, 丁海洋, 李子臣     
北京印刷学院 信息工程学院, 北京 102600
摘要:针对载体图像内容安全与数字水印版权保护, 结合Arnold置换与直方图平移可逆水印算法, 提出基于Arnold置换的交换加密水印算法. 算法利用置换后图像直方图不变的特性, 将在密文中嵌入水印的操作映射到明文中, 实现了加密与水印操作先后顺序的交换. 在提取水印时, 可直接从含水印的密文中提取水印, 也可解密后再提取水印. 实验结果表明, 该算法加密操作与水印嵌入操作间的先后顺序不影响含水印密文的生成, 解密操作与水印提取操作的先后顺序不影响水印提取与图像恢复, 且直接解密得到的含水印明文图像质量较高, 水印的不可见性好, 算法有较高的效率.
关键词: 图像置换    直方图平移    数字水印    交换加密水印算法    
Commutative Encryption and Watermarking Algorithm Based on Arnold Permutation
ZHAO Pei-Yue, ZHANG Zhen-Zhen, DING Hai-Yang, LI Zi-Chen     
College of Information Engineering, Beijing Institute of Graphic Communication, Beijing 102600, China
Foundation item: National Natural Science Foundation of China (61370188); General Project of Scientific Research Plan of Beijing Municipal Education Commission (KM202010015009); Scientific Research Plan of Beijing Municipal Education Commission (KM202110015004); Start-up Fund for Ph.D. Student of Beijing Institute of Graphic Communication (27170120003/020); Scientific Research and Innovation Project of Beijing Institute of Graphic Communication (Eb202101)
Abstract: To protect the security of carrier image content and digital watermark copyright, this study proposes a commutative encryption and watermarking algorithm integrating the Arnold permutation and histogram translation-based reversible watermarking algorithm. Taking advantage of the invariance of the image histogram after Arnold permutation, the algorithm maps the operation of watermark embedding in ciphertext to plaintext, which realizes the exchange of encryption and watermark embedding in operation sequence. The watermark can be extracted directly from the watermarked ciphertext, or be extracted after decryption. Experimental results show that the sequence of encryption and watermark embedding of this algorithm does not affect the generation of watermarked ciphertext, and the sequence of decryption and watermark extraction does not influence watermark extraction and image restoration. In addition, the direct decryption yields high-quality watermarked plaintext images, good invisibility of the watermark, and high efficiency of the algorithm.
Key words: image permutation     histogram translation     digital watermark     commutative encryption and watermarking    

1 引言

近年来, 互联网、云计算、大数据等技术朝着高效快速的方向发展, 数据隐私保护和信息安全[1]日益受到重视, 其中图像加密和数字水印成为了研究的热点. 在一些特殊领域如医学、军事、卫星监测等需要对图像进行处理, 将密码技术与数字水印结合到一起, 提供了图像加密与水印共存的安全保护方案[2].

图像置换作为一种重要的图像加密和技术, 其目的是将目标图像进行一定程度上的修改, 使其包含的真实信息可以不被破坏地隐藏起来, 这样便具有不可见性, 保证了图像传输的安全性. 其基本思想是将数字图像作为矩阵进行有限次的初等置换来使图像的像素点变得混乱无序, 从而实现加密效果. 典型的有幻方置换、骑士巡游置换、Fibonacci置换、基于Hilbert曲线置换[3]等算法. 其中Arnold置换直观、简单、具有周期性, 使用非常方便, 该方法使像素的移动具有混沌特性, 加密后的图像安全性较高.

水印算法根据操作域的不同可分为3类: 空域算法、频域算法以及压缩域算法. 空域算法有基于LSB的水印算法、基于差值扩展的水印算法[4]和基于无损压缩的水印算法[5]等. 其中基于直方图平移的可逆水印算法[6]是最具代表性的算法之一. 文献[7]对图像分块, 建立多个差值直方图来嵌入水印信息; 文献[8]通过混沌加密与直方图平移结合, 实现了无损提取水印信息, 但其水印嵌入容量十分有限; 文献[9]利用多组差值直方图平移获取更多差值, 通过图像分块和边缘差值嵌入, 虽然提高了嵌入率, 但是其含水印图像质量随之下降. 文献[10]提出了对载体图像进行分块置换加密, 并通过DCT变换来嵌入水印信息, 文献[11]对水印信息进行置换加密, 对载体图像进行分块后过DCT变换与直方图平移来嵌入水印.

交换加密水印算法是现阶段实现密码技术和水印技术相结合的一种主要方法. 文献[12]最先提出了交换加密水印技术(Commutative Encryption and Watermarking , CEW), 将加解密、水印嵌入、提取融合到一起, 在发送前既可先加密后嵌水印, 也可先嵌水印后加密, 均能得到含水印的密文; 在发送后既可从密文中先提取水印, 再解密恢复图像, 也可先解密, 再提取水印恢复图像[13]. 而置换加密后不会对图像的某些统计特征造成影响[14], 所以可通过修改原始载体图像的统计特征来嵌入水印从而实现交换加密水印算法. 文献[15]将原始载体图像分组嵌入比特信息后, 通过修改数据最低比特, 使得全组数据之和的奇偶性与对应嵌入的水印信息相同, 并在同组数据范围内进行置换从而实现CEW, 但仅对载体数据进行置乱, 安全性有待提高. 文献[16]通过空间位置置换及修改载体图像直方图嵌入水印信息实现CEW.

基于对上述算法的研究, 利用Arnold置换前后直方图不变的特性, 提出了一种基于Arnold置换的交换加密水印算法. 原始载体图像先进行分块, 再进行块内和块间的置换加密, 通过直方图平移来实现水印嵌入. 加密操作与水印嵌入操作的顺序不影响含水印密文的生成, 且解密操作与水印提取操作的顺序不影响水印信息的提取与图像的恢复. 实验结果表明, 该算法可以无损恢复原始载体图像并提取水印, 且解密后的含水印明文图像质量高, 水印的不可见性好.

2 基本原理

本节主要介绍Arnold置换, 直方图平移可逆水印算法及交换加密水印算法.

2.1 Arnold置换

Arnold置换(又称猫脸置换)是一种基于古典密码体制的图像加密算法, 本质上是对长宽相等的图像中像素点的位置进行多次矩阵运算, 从而改变空间中像素点的位置, 破坏图像相邻像素点之间的相关性.

2.1.1 Arnold置换原理

传统的Arnold置换[3]的矩阵形式可以表达为: 设有平面点集 $S = \left[ {0,1} \right] \times \left[ {0,1} \right]$ , 对 $\left( {x,y} \right) \in S$ 则有:

$\left[ {\begin{array}{*{20}{c}} {x'} \\ {y'} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} 1&1 \\ 1&2 \end{array}} \right]\left[ {\begin{array}{*{20}{c}} x \\ y \end{array}} \right]\left( {\boldsymbolod \;1} \right)\;\;\;$ (1)

若(x,y)为二维图像坐标, 那么上述置换可以转化为:

$\left[ {\begin{array}{*{20}{c}} {x'} \\ {y'} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} 1&1 \\ 1&2 \end{array}} \right]\left[ {\begin{array}{*{20}{c}} x \\ y \end{array}} \right]\left( {\boldsymbolod \;N} \right)$ (2)

置换矩阵可设为 $C = \left[ {\begin{array}{*{20}{c}} 1&b \\ a&{ab + 1} \end{array}} \right]$ , 则:

$\left[ {\begin{array}{*{20}{c}} {{x_{n + 1}}} \\ {{y_{n + 1}}} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} 1&b \\ a&{ab + 1} \end{array}} \right]\left[ {\begin{array}{*{20}{c}} {{x_n}} \\ {{y_n}} \end{array}} \right]\left( {\boldsymbolod\; N} \right)$ (3)

其中, n代表第n次变换.

2.1.2 Arnold置换的周期性

Arnold置换具有周期性[17], 通过对一个4×4矩阵进行Arnold置换来说明Arnold的周期性.

设原始矩阵为 $A{\rm{ = }}\left[ {\begin{array}{*{20}{c}} 1&2&3&4 \\ 5&6&7&8 \\ 9&{10}&{11}&{12} \\ {13}&{14}&{15}&{16} \end{array}} \right]$ , 分别对该矩阵进行1,2,3次Arnold置换. 得出3次置换后的矩阵分别为:

$ \begin{split} &\left[ {\begin{array}{*{20}{c}} 1&{14}&{11}&8 \\ {12}&5&2&{15} \\ 3&{16}&9&6 \\ {10}&7&4&{13} \end{array}} \right]\;\;\left[ {\begin{array}{*{20}{c}} 1&7&9&{15} \\ 6&{12}&{14}&4 \\ {11}&{13}&3&5 \\ {16}&2&8&{10} \end{array}} \right]\;\;\\ &\left[ {\begin{array}{*{20}{c}} 1&2&3&4 \\ 5&6&7&8 \\ 9&{10}&{11}&{12} \\ {13}&{14}&{15}&{16} \end{array}} \right] \end{split} $

可以看到经过3次置换后, 矩阵A恢复成原始状态. Arnold置换周期与图像阶数的关系见表1.

2.1.3 Arnold置换恢复算法

解密时需要用到Arnold置换恢复算法. 目前归纳的Arnold置换恢复算法[18]有3种: 一是利用周期恢复; 二是通过逆矩阵恢复; 三是解方程组法. 本算法利用周期性来恢复.

设大小为N×N的图像进行Arnold置换, 置换了n次, Arnold置换周期为T, 以此求恢复图像. 已经置换n次, 利用置换周期, 只要再经过 $T - \left( {n\;\boldsymbolod \;T} \right)$ 次即可恢复原图.

2.2 基于直方图平移的可逆水印算法

文献[19]提出了基于直方图平移的信息隐藏基本方案, 直方图中横坐标是灰度值, 纵坐标是该灰度值对应的像素点的数量, 而每一个竖条称为一个bin. 直方图中最高的那个点, 就称为峰点P. 最低的那个点(通常为0), 叫做零点Z (如无为0的点, 可以将灰度值为254的点的灰度值改为255, 并进行标记, 以此空出254位置, 最后可根据标记恢复).

对灰度图像直方图进行分析, 通过将直方图峰值点与零点的像素平移来空出嵌入空间, 并在峰值点嵌入水印信息, 提取恢复时根据峰值点与相临的bin便可提取水印信息并恢复图像. 直方图平移嵌水印过程如图1.

表 1 图像阶数N与置换周期T的关系

图 1 直方图平移嵌水印流程图

2.3 交换加密水印算法

在发送方, 加密与嵌入水印顺序可以交换; 在接收方, 可从含水印的密文图像中直接提取水印, 也可从解密后恢复图像的中提取水印, 从而达到交换加密水印的目的. 交换加密水印算法框架如图2. 其中I为原始载体图像, w为水印, k为密钥, ${I_w}$ 为含水印图像, ${I'_w}$ 为含水印密文图像.

图 2 交换加密水印算法框架

3 基于Arnold置换的交换加密水印算法

本文提出的基于Arnold置换的交换加密水印算法如图3.

图 3 基于Arnold置换的交换加密水印算法

算法步骤可总结如下:

(1) 对原始图像进行分块;

(2) 在嵌入水印时, 在明文和密文中均可以嵌入, 最终得到含水印密文图像;

(3) 提取水印时, 可从含水印密文图像中直接提取, 也可解密后再提取.

3.1 含水印密文图像的生成

算法中涉及的参数有ab ${n_1}$ ${n_2}$ ${T_1}$ ${T_2}$ . 其中ab为置换矩阵参数, $ab \ne 0$ , $({n_1}\;\boldsymbolod \;{T_1}) \ne 0$ , $({n_2}\;\boldsymbolod \;{T_2}) \ne 0$ . ${n_1}$ 为水印图像置换次数与原始图像各小块的块间置换次数, ${n_2}$ 为原始图像各小块的块内置换次数. ${T_1}$ 为水印图像对应的置换周期, ${T_2}$ 为原始图像小块对应的置换周期.

3.1.1 先加密后嵌水印

其步骤可总结如下:

(1) 水印图像m置换 ${n_1}$ 次, 得到水印w;

(2) 把原始图像I分为k个的大小为8×8的明文分块, 记第k小块为I(k). 对I(k)按照2.1.1小节分别进行块内置换 ${n_2}$ 次、块间置换 ${n_1}$ 次, 最终得到密文图像 $I'$ ;

(3) 按照从上到下、从左到右的方式遍历密文小块 $I'\left( k \right)$ 的像素点;

(4) 将小块内 $P+1$ $ Z-1 $ 的所有bin向右平移一位, 空出 $P + 1$ 的bin. 可通过判断某个点的灰度值是否在P–Z之间, 然后对应灰度值加1即可;

(5) 每个密文小块嵌入1 bit信息, 嵌入到峰值点P中. 仅在第一个峰值点像素值P处嵌入信息. 嵌0就是加0运算, 嵌1就是加1运算, 这样像素值就会保持为P不变或者变为 $P + 1$ .

嵌入公式如式(4)所示:

$p' = \left\{ {\begin{array}{*{20}{l}} {p + b,\;{\text{if}}\;p = P} \\ {p + 1,\;{\text{if}}\;p \ge P\;{\text{and}}\;p \le Z - 1} \\ {p,\;{\text{otherwise}}} \end{array}} \right.$ (4)

其中, p是原始像素值, b是1 bit水印, $p'$ 是嵌入信息后的像素值;

(6)将全部水印信息嵌入到密文图像 $I'$ , 最终得到含水印的密文图像 ${I'_w}$ .

3.1.2 先嵌水印后加密

其步骤可总结如下:

(1) 水印图像m置换 ${n_1}$ 次, 得到水印w;

(2) 把原始图像I分为k个的大小为8×8的明文分块, 记第k个小块为I(k);

(3) 按照3.1.1小节中步骤(3)–步骤(5), 将水印w嵌入到原始图像I中, 每个小块嵌入1 bit信息, 最终得到含水印的图像 ${I_w}$ ;

(4) 对 ${I_w}$ 按照式(3)分别进行块内置换 ${n_2}$ 次、块间置换 ${n_1}$ 次, 最终得到含水印的密文图像 ${I'_w}$ .

3.2 水印提取与图像恢复

接收方接收到含水印的密文图像后进行相应处理, 可先提取水印信息、恢复图像; 也可解密以后再提取水印信息、恢复图像. 在提取水印时, 因为每个小块只嵌入1 bit水印信息, 所以只需判断像素值为P+1的点的个数即可得知该小块嵌入的是0还是1.

本文以先加密后嵌水印得到的含水印密文图像为例, 对提取水印恢复图像过程进行详细描述.

3.2.1 直接提取水印、恢复图像

其步骤可总结如下:

(1) 按照与嵌入时相同的方式遍历小块 ${I_w}^\prime \left( k \right)$ 的像素点.

(2) 判断小块 ${I_w}^\prime \left( k \right)$ 内像素值P+1的个数num.

(3) 提取1 bit水印信息, 如式(5)所示:

$w = \left\{ {\begin{array}{*{20}{l}} {0,\;{\text{if}}\;num = 0} \\ {1,\;{\text{otherwise}}} \end{array}} \right.$ (5)

(4) 其他小块重复步骤(1)–步骤(3), 完成全部水印信息的提取, 最终得到水印图像w, 然后对w再置换 ${T_1} - \left( {{n_1}\;\boldsymbolod \;{T_1}} \right)$ 次得到水印图像m.

(5) 提取水印后, 将 ${I^\prime }\left( k \right)$ 中像素值进行处理, 如式(6)所示:

$p{\rm{ = }}\left\{ {\begin{array}{*{20}{l}} {p',\;{\text{if}}\;p' = P} \\ {p' - 1,\;{\text{if}}\;p' = P + 1} \\ {p' - 1,\;{\text{if}}\;p' \ge P + 2\;{\text{and}}\;p' \le Z} \\ {p',\;{\text{otherwise}}} \end{array}} \right.$ (6)

(6) 其他小块重复步骤(1)–步骤(5), 最终获取完整的密文图像 $I'$ .

(7) 对 $I'\left( k \right)$ 块间置换 ${T_1} - \left( {{n_1}\;\boldsymbolod \;{T_1}} \right)$ 次, 块内置换 ${T_2} - \left( {{n_2}\;\boldsymbolod \;{T_2}} \right)$ 次, 得到恢复图像.

3.2.2 先解密, 再提取水印恢复图像

其步骤可总结如下:

(1) 对含水印的密文图像 ${I'_w}$ 分别进行块间置换 ${T_1} - \left( {{n_1}\;\boldsymbolod \;{T_1}} \right)$ 次、块内置换 ${T_2} - \left( {{n_2}\;\boldsymbolod \;{T_2}} \right)$ 次, 得到含水印的明文图像 ${I_m}$ .

(2) 对 ${I_m}$ 各小块进行处理, 同3.2.1小节中步骤(1)–步骤(3). 最终得到水印m.

(3) 按照式(6)对提取水印后的图像进行处理, 得到恢复图像.

4 算法仿真分析

本文算法在Matlab R2020a, Windows 10操作系统下进行仿真测试, 使用水印算法的客观评价标准, 选取大小为512×512的经典灰度图像进行测试, 从加密参数、不可见性、可逆性、效率说明算法的性能. 置换矩阵中参数选取为a=1, b=1.

4.1 加密参数测试

嵌入率可以用来衡量算法的嵌入容量, 计算公式如式(7)所示:

$ {\text{嵌入率}}=\frac{{\text{嵌入的}}{\rm{bit}}{\text{数}}}{{\text{载体图像像素个数}}}$ (7)

选取三幅灰度图Lena、Boat、Peppers, 在嵌入水印容量为0.156 bpp时, 对置换加密参数 $\left( {{n_1},{n_2}} \right)$ 进行测试. 选取6对不同参数对 $\left( {{n_1},{n_2}} \right)$ 时, 在密文域嵌水印, 解密后得到的含水印图像的PSNR值见表2.

表 2 不同(n1, n2)时含水印图像PSNR值 (dB)

表2可知选取不同参数对 $\left( {{n_1},{n_2}} \right)$ 并不会影响解密后含水印图像的质量.

4.2 不可见性测试

峰值信噪比PSNR值可以说明含水印明文图像中水印的不可见性, PSNR值越大, 说明水印的不可见性越好. 本文算法在不同嵌入容量下, 解密得到的含水印图像的PSNR值及平均PSNR值. 见表3.

表 3 不同嵌入容量下PSNR值及平均值 (dB)

通过表3不难看出, 本文算法在水印嵌入后, PSNR平均值都在51 dB以上, 且随着嵌入容量的增加, PSNR值有所提升.

嵌入率为0.0156 bpp, 载体图像为Lena图时在密文中嵌水印实验结果, 如图4.

嵌入率为0.0156 bpp, 载体图像为Lena图时在明文中嵌水印实验结果, 如图5.

通过图4图5可以看出在密文域或明文域中嵌水印, 解密后含水印图像质量较高, 水印不可见性好.

图 4 密文域嵌水印实验结果

图 5 明文嵌水印实验结果

本文还与文献[79]中相关经典算法进行对比, 见表4.

表 4 算法性能对比

与文献[7]、文献[8]算法对比, 可以看出本文算法在PSNR值与嵌入容量上占优; 与文献[9]对比, 在嵌入容量相近时, 本文算法PSNR值也要更高.

4.3 可逆性测试

通过归一化系数NC值来判断是否有可逆性. 本文给出了10幅512×512大小的灰度图像的NC值, 见表5.

表5中可以看出, 所有图像的NC值均为1, 说明恢复图像与原始图像一样. 而且提取出的水印错误率为0, 说明本算法具有可逆性.

表 5 可逆性测试

4.4 算法效率测试

本实验还进行了算法效率测试, 在不同嵌入容量下, 对10幅灰度图分别进行10次测试, 最后取平均值, 结果见表6.

表 6 不同嵌入容量下各算法的运行时间(s)

表6可知, 随着数据量的增大, 算法所需时间有所增长, 但总体满足效率要求.

5 结束语

本文提出的基于Arnold置换的交换加密水印算法, 实现了加密操作与水印操作的交换, 解密后的含水印图像质量高, 水印的不可见性好. 算法中两次置换加密提高了载体图像在使用及分发时的安全性, 不仅能有效保护与恢复载体图像, 而且从含水印密文图像或解密后的含水印图像中都能提取水印信息, 对于身份认证与版权保护有着重要作用, 可以广泛地应用于医学、军事等领域.

参考文献
[1]
冯登国, 张敏, 张妍, 等. 云计算安全研究. 软件学报, 2011, 22(1): 71-83. DOI:10.3724/SP.J.1001.2011.03958
[2]
Jiang L, Xu ZQ, Xu YY. Commutative encryption and watermarking based on orthogonal decomposition. Multimedia Tools and Applications, 2014, 70(3): 1617-1635. DOI:10.1007/s11042-012-1181-2
[3]
方毅. Arnold置乱变换图像加密算法研究[硕士学位论文]. 赣州: 江西理工大学, 2018.
[4]
Tian J. Reversible data embedding using a difference expansion. IEEE Transactions on Circuits and Systems for Video Technology, 2003, 13(8): 890-896. DOI:10.1109/TCSVT.2003.815962
[5]
Celik MU, Sharma G, Tekalp AM. Lossless watermarking for image authentication: A new framework and an implementation. IEEE Transactions on Image Processing, 2006, 15(4): 1042-1049. DOI:10.1109/TIP.2005.863053
[6]
贾玉洁. 基于图像像素直方图平移的可逆信息隐藏优化算法研究[硕士学位论文]. 合肥: 安徽大学, 2020.
[7]
Luo H, Yu FX, Chen C, et al. Reversible data hiding based on block median preservation. Information Sciences, 2011, 181(2): 308-328. DOI:10.1016/j.ins.2010.09.022
[8]
罗昊, 谢晓尧, 彭长根. 基于直方图平移的加密域可逆水印算法. 郑州大学学报(理学版), 2018, 50(2): 29-34.
[9]
李志佳, 夏玮. 基于差值直方图平移的密文域可逆信息隐藏算法. 计算机工程, 2019, 45(11): 152-158.
[10]
Jiang L, Xu ZQ. Combination algorithm of active and passive security protection for image based on arnold transform. Proceedings of 2010 International Conference on Multimedia Information Networking and Security. Nanjing: IEEE, 2010. 625–629.
[11]
Roy S, Pal AK. A robust reversible image watermarking scheme in DCT domain using Arnold scrambling and histogram modification. International Journal of Information and Computer Security, 2018, 10(2–3): 216-236.
[12]
Katzenbeisser S. First Summary Report on Hybrid Systems. European Project IST-2002-507932, ECRYPT-Network of Excellence in Cryptology, 2005.
[13]
佟德宇. 矢量地理数据交换密码水印模型和算法研究[博士学位论文]. 南京: 南京师范大学, 2018.
[14]
柯彦, 张敏情, 刘佳, 等. 密文域可逆信息隐藏综述. 计算机应用, 2016, 36(11): 3067-3076, 3092. DOI:10.11772/j.issn.1001-9081.2016.11.3067
[15]
Steinebach M, Zmudzinski S, Bolke T. Audio watermarking and partial encryption. Proceedings of SPIE 5681, Security, Steganography, and Watermarking of Multimedia Contents VII. San Jose: SPIE, 2005.
[16]
中山大学. 一种结合加密和水印的多媒体信息安全保障方法: 中国, 200912192270.6. 2010-02-10.
[17]
杨洋. 基于Arnold变换的数字图像加密算法[硕士学位论文]. 广州: 华南理工大学, 2015.
[18]
郭琳琴, 张新荣, 李震. 基于Arnold逆变换的图像置乱恢复算法. 计算机应用与软件, 2010, 27(9): 265-267. DOI:10.3969/j.issn.1000-386X.2010.09.083
[19]
Ni ZC, Shi YQ, Ansari N, et al. Reversible data hiding. IEEE Transactions on Circuits and Systems for Video Technology, 2006, 16(3): 354-362. DOI:10.1109/TCSVT.2006.869964