基于位平面-块置乱的图像加密算法安全性分析

屈凌峰，陈 帆，和红杰，袁 源

西南交通大学信息科学与技术学院，成都610031

随着通信、数字成像与互联网等信息技术的发展，图像数据通过各种有线/无线信道传输的频率越来越高.图像的机密性、身份认证、完整性会受到诸如黑客攻击、复制或恶意篡改等非法操作的威胁.加密是一种有效且常用的解决方案.一方面，通过对图像加密保持图像数据的机密性和隐私性，因为它将原始的有意义的图像内容转换成难以理解的类似噪音的内容；另一方面，加密图像存储或归档的过程中，在不知其原始内容的情况下对其进行分析和处理往往是不可避免的.因此，加密图像中的可逆数据隐藏（reversible data hiding in encrypted image,RDH-EI）技术引起了广泛关注[1].

RDH-EI 技术能够加密原始图像在密文图像中可逆地隐藏附加数据，并在提取附加数据后，无损重建原始图像.现有的RDH-EI 方法可分为“加密后腾出空间（vacating room after encryption,VRAE）”和“加密前腾出空间（vacating room before encryption,VRBE）”两类.VRBE 的RDH-EI 算法[2-7]在图像加密前利用原始图像像素相关性腾出空间，这类算法往往具有较高的嵌入容量和安全性.但在VRBE 框架中，用户在图像加密前需要对图像进行额外的操作，显然增加了内容所有者的负担.不同于VRBE 算法，VRAE 算法直接从加密的图像中腾出嵌入空间，使秘密信息嵌入到加密后的图像中[8-16].对于用户来说，VRAE 算法操作简单且高效，因为VRAE 只需对图像进行加密，无需任何额外的预处理过程.由于加密后的图像打破了原始图像的相关性和加密图像熵的最大化，使得在加密后的图像中腾出空间较困难，因此VRAE 算法嵌入容量往往较低.为了解决上述问题，在VRAE 算法中通常使用块置乱加密方案[8-10,16].这是因为块置乱加密在一定程度上破坏了明文图像的统计特性，加密过程简单快速，适用于加密大量图像数据的场景.同时，由于块置乱加密保留了图像块内像素的相关性，利用加密后图像块内像素的相关性，可以在加密图像中腾出更多空间用于嵌入信息.

现有的加密域可逆信息隐藏算法都是基于两种相互冲突的度量方法进行评估的，即数据隐藏容量和解密后含秘图像的质量，因此在RDH-EI 算法中缺乏对加密图像安全性的分析[17].加密图像的安全性是至关重要的，因为RDH-EI 的核心是保证原始图像不被第三方泄漏.如果数据隐藏者在隐藏数据前泄漏了用户上传的加密图像集，攻击者就可以利用已知的明文和对应的密文在不知道密钥的情况下破解加密图像集，导致用户的隐私泄露.目前，针对图像纯置乱加密的安全性分析已经得到了广泛研究，并已证明置乱加密无法抵抗已知/选择明文攻击[18-20].文献[18]对图像单像素置乱加密进行定量密码分析证明，对已知明文攻击至少需要logL(2(MN-1))对明文与密文来达到较好的攻击效果.其中MN为图像大小，L为最大像素值.文献[19]分析了文献[10]算法的时间复杂度，并基于二叉树的原理减小了时间复杂度，该算法的时间复杂度仅为o(nMN).文献[12]用同样的方法进行攻击纯置乱加密图像，不同的是，文献[20]基于构造的明文得到了完全正确的置乱矩阵.正确估计置乱矩阵所需要的明文-密文为logL(MN)对.构造明文虽然可以完全恢复置乱矩阵，但是攻击难度较高，因为用构造的非自然图像去加密会引起加密用户的怀疑.

在尽量保留加密图像冗余度的条件下，为了提高加密图像的安全性，文献[16]提出一种基于阿诺德变换的加密算法（Arnold transform-based encryption method,ATBEM）.ATBEM 加密算法首先对图像进行位平面置乱，改变了加密图像的像素值，从而可以抵抗针对单像素置乱的已知明文攻击.接着将图像划分为不重叠的图像块，为了保留像素间的冗余，分块大小不能太小，而为了保证加密图像安全性，分块大小不能太大.根据加密密钥分别对图像块和块内像素置乱.由于ATBEM 没有采用流密码异或加密，因此该加密算法能有效抵抗文献[17]提出的唯密文攻击.同时，位平面置乱可能使像素值发生改变，因此ATBEM 不易受针对纯置乱加密的已知明文攻击[18-20].然而，ATBEM 不改变明文图像位平面比特分布特性，且对于8 位灰度图像而言位平面置乱的密钥空间较小，在已知明文攻击的条件下存在安全隐患.为分析验证ATBEM 存在图像内容信息泄露的安全隐患，本文提出一种针对ATBEM 的已知明文攻击，主要步骤如下：

步骤1利用自然图像不同位平面间的统计特征，恢复图像位平面置乱顺序.

步骤2采用图像块均方根分类的策略，在明文与密文图像间建立等量关系，实现已知明文攻击.

步骤3定量分析ATBEM 加密算法中块置乱加密的安全性能.

1 ATBEM 概述及分析

ATBEM 算法在加密图像中保留了原始图像的冗余空间，包括编码冗余和像素间冗余.利用这些冗余，可以实现在加密图像中进行大容量的数据隐藏.本节以灰度图像为例，对ATBEM 加密算法进行概述及分析.

1.1 ATBEM 概述

对于M ×N大小的8 位灰度图像，ATBEM 使用3个秘钥Key1、Key2、Key3对图像进行加密。基于3个秘钥分别生成置乱矩阵W1、W2、W3，将原始图像f= [f(i,j)](M ×N)的位平面、图像块、块内像素分别置乱得到密文图像f′=[f′(i,j)](M ×N).为便于本文攻击算法的描述，将ATBEM 分解为位平面和像素-块置乱两个步骤.

步骤1位平面置乱.将灰度图像的8个位平面分为两部分[c,r]，其中c ∈[1,5]表示图像的5个低位平面，r ∈[6,8]表示图像的3个高位平面.在秘钥Key1的控制下，生成一维置乱序列W1=[w1(1,k)](1×8)，得到位平面置乱图像f′1

式中，r′为原始图像高3 位平面的置乱顺序，c′为原始图像低5 位平面的置乱顺序.

步骤2像素-块置乱.将加密图像f′1分解为m×n大小的个不重叠的像素块.利用秘钥Key2生成块置乱矩阵W2=[w2(ε,ζ)](λ1×λ2).其中

式中，λ′1={0,··· ,λ1-1},λ′2={0,··· ,λ2-1}.(ε′,ζ′)为置乱后图像块的坐标.同时，基于密钥Key3生成像素置乱矩阵W3=[w3(i,j)](m×n)对图像块内的像素进行置乱加密

式中，(i′,j′)表示像素坐标为(i,j)置乱后的坐标.m′={0,··· ,m-1},n′={0,··· ,n-1}.

1.2 ATBEM 的特性分析

在ATBEM 加密算法中，通过对图像位平面置乱，不仅保留了加密图像中的位平面冗余，而且改变了加密图像的像素值.攻击者若不能正确恢复加密图像位平面置乱顺序，将无法针对块置乱加密进行已知明文攻击.图1描述了ATBEM 加密算法位平面置乱的过程.

图1 位平面置乱过程Figure1 Permutation process of bit planes

在ATBEM 加密算法中，通过对图像分块操作保留了块内像素位平面的编码冗余，这将为后期在加密图像中腾出空间提供可能.由于图像分块大小不能过大，攻击者对图像块内像素求平均值即可得到原始图像的下采样图像.此外，由于图像块内元素较少，在已知明文条件下，置乱矩阵W3很容易被攻击者破解.因此，ATBEM 加密攻击的难度主要在于破解置乱矩阵W1与W2.

ATBEM 加密算法不仅改变原始图像的像素值，而且打乱像素值的位置，提高加密图像的安全性.但是，该加密方案不改变图像位平面内的比特值分布.在已知明文攻击中，攻击者利用图像位平面比特值的分布特性可以恢复位平面置乱顺序，在不知道秘钥的条件下得到位平面一维置乱序列W1，进而恢复位平面顺序.接着利用已知明文攻击的原理，攻击者可以逐步恢复得到W2与W3最终破解加密图像.在下一节中将针对ATBEM 加密算法，提出一种已知明文攻击方法，并定量分析块置乱加密方案的安全性能.

2 基于均方根排序的已知明文攻击

在已知明文攻击中，假设攻击者得到明文图像f及其对应的密文图像f′，利用f ～f′在不知道加密秘钥Key1、Key2、Key3的情况下估计出置乱矩阵W1、W2、W3.攻击者利用置乱矩阵可以解密用户上传的所有加密图像.在1.2 节特性分析中可知，攻击者的主要目标是估计W1与W2，且必须得到完全正确的置乱序列W1，才可以进一步估计置乱矩阵W2.本节将分别介绍基于位平面统计特征确定W1和基于块均方根估计W2的已知明文攻击方法.

2.1 基于位平面统计特征确定W2

在ATBEM 加密算法中，灰度图像位平面置乱顺序的情况共有A33×A55=720 种，暴力破解的难度在于，攻击者难以在720 种情况中确定哪一种是由正确的置乱序列W1生成的f′1.为实现快速且正确的估计位平面置乱序列W1，引入自然灰度图像位平面间的统计特征1.

特征1[21]灰度图像不同位平面间0 或1 值的比例存在差异.

选取常见的6 幅灰度图像Lena、Airplane、Camera、Man、Pepper、Baboon 作为测试图像.统计6 幅灰度图像中8个位平面内比特值为1 的比例，结果保留小数点后4 位.测试结果如表1所示.在表1中，以Lena 图像为例，可以看到相邻位平面间比特值为1 的比例接近但不重复，且位平面内比特值为1 的比例在0.5 上下波动.其余测试图像与Lena 图像一样，不存在任意两个位平面内比特值为1 的比例完全相同的情况.表1验证了特征1，即对于同一幅灰度图像而言，每个位平面内比特值为1 的比例存在差异.

由1.2 节分析可知，ATBEM 加密算法没有破坏明文图像0 或1 值在每个位平面的分布特性.利用位平面间1 值比例的差异，在已知明文攻击的条件下攻击者可以正确估计置乱矩阵W1.基于位平面统计特征确定置乱序列W1的方法如下：

表1 不同灰度图像每个位平面‘1’值的比例Table1 Ratio of ‘1’ value in each bit plane of different grayscale images

计算明文f及密文f′图像在每个位平面中，比特值为1 所占比例R(u)、R(v)，其中u ∈[1,2,··· ,8],v ∈[1,2,··· ,8].函数R(x)如下：

当x=u时,表示明文图像f在第u个位平面中坐标为(i,j)的比特值.当x=v时，表示密文图像f′在第v个位平面中坐标为(i,j)的比特值.

R(u)、R(v)各有8 种情况，对比R(u)和R(v)中的所有情况，当且仅当R(u) =R(v)时，一维置乱序列W1的估计为

2.2 基于块均方根估计W2

将恢复位平面后的加密图像视为新的密文图像，该密文图像为像素-块置乱加密.由于图像块内像素被置乱，为了使明文与密文中的图像块对应，定义图像块均方根（root mean square,RMS）.设图像块的大小为m×n，对明文图像中所有图像块求RMS 得到RMS 集合J，

RMS 值不同，必定为不同的图像块，而RMS 值相同，则不一定为相同的图像块.以2×2 图像块为例，图2中(a)～(c)的RMS 值均为7.5，且(a)与(b)图像块元素相同，而(a)与(c)元素不同.图像块(d)的RMS 值约为7.3，其块内元素必然与(a)不同.

图像块RMS 忽略块内像素的位置关系，在明文与密文图像间建立等量关系，并将图像块进行分类.图2中的(a)～(d)4个图像块分为两类：(a)～(c)RMS 值相同为一类，(d)为一类.为便于描述，定义以下集合关系：

图2 2×2 图像块的均方根Figure2 Root mean square of 2×2 image block size

定义1明文图像f中的RMS 集合J索引排序后的集合为其中sort()为排序函数.置乱加密不改变像素值，相应地，密文图像f′排序后的RMS集合与一致，但元素索引不同.

定义2同一类图像块构成RMS 分类集合G.设在明文图像f中，第i个RMS 分类集合为Gi={l1,··· ,li,··· ,lv}，那么密文图像f′中第i个RMS 分类集合为G′i={l′1,···,l′i,···,l′v}.

定义3在RMS 分类集合G中，某图像块出现的概率为p.当时，表示该图像块仅出现一次；反之，当时，表示该图像块出现次数大于一次.

在定义2 中，由于RMS 分类集合G中存在完全一样的图像块（如图2(a)～(b)）即p ＞这些图像块会导致置乱矩阵W2估计错误.为了提高W2的正确率，需要多对明文-密文图像.

以两对明文-密文图像中第i个RMS 分类集合Gi、G′i为例.已知第2 对明文图像为f2，密文图像为f′2，由Gi、G′i集合中图像块的索引坐标提取f2、f′2中的图像块，构成第2 对明文-密文图像RMS 分类集合：G2i与G′2i，其中

对比f′～f′2密文图像RMS 分类集合G′i、G′2i中的所有图像块，分别记录每个块的位置于集合Λ1和Λ2中，得到2个位置集合

在块置乱的过程中，明文图像中位于(ε,ζ)坐标的图像块被置乱到密文图像的(ε′,ζ′)位置，因此∀(ε′,ζ′)∈Λ1(l′i)，f′(ε′,ζ′)=l′i，且块置乱矩阵W2的估计为

β为明密文对数，对所有的RMS 分类集合用同样的操作可以得到一个估计的置乱矩阵为W2的近似矩阵.

在1.2 节的分析中，块内像素置乱矩阵W3容易被攻击者破解，攻击者仅需在已知的明文图像中找到仅出现一次的图像块Bi={l1,1,··· ,li,j,··· ,lm,n}，其中li,j表示Bi块中坐标为(i,j)的像素，该图像块满足设像素值li,j在对应的密文图像块中被置乱到坐标为(x,y)位置.控制块内像素置乱矩阵W3=[w3(i,j)]m×n由式(13)确定

由于块置乱加密分块大小不能太大，因此容易找到满足条件的图像块.本节实现了置乱矩阵W1、、W3的确定与估计，攻击者在不知道秘钥Key1、Key2、Key3的情况下得到置乱矩阵W1、、W3，破解了密文图像库中用户上传的所有加密图像.

3 定量分析及选择明文攻击

ATBEM 加密攻击难度主要在于破解置乱矩阵W1与W2.攻击者可以精确得到置乱矩阵W1，影响攻击效果的主要因素是块置乱矩阵W2.本节针对块置乱加密进行定量分析，同时对块置乱加密在选择明文攻击（即攻击者可以选择一些特殊图像，通过加密机进行块置乱加密，从而估计块置乱矩阵）的条件下分析明文构造方法.

3.1 定量分析

情况1最小块为δ= 2×2，且不同的块互相独立，每个块中像素值出现的概率均为考虑到最小块相邻像素的相关性，假设每个最小块中有2个重复元素，那么每个块出现的概率为∀L ∈{0,··· ,L-1}.在置乱矩阵中，每个坐标(ε,ζ)的平均数目为一般即时，中将有超过一半的值被唯一确定.即在情况1 下要恢复一半以上的图像块位置，所需的明文密文对数为此时所确定的x为所需的明文-密文对数的下限.对于512×512，L= 256，δ= 2×2 = 4 而言，仅需对明文密文即可恢复50%以上图像块的置乱位置.情况1 适用于纹理复杂度高的图像，对于平滑图像的定量分析见情况2.

图3 p与明文对数x和L(p)的关系Figure3 Rrelationship betweenpandxandL(p)

情况2某个块不服从均匀分布，其余块服从均匀分布.这种情况适用于平滑图像，即图像中存在较多的重复块.该块出现的概率为P0=p，其余块的概率为{1,··· ,L-1}，对于x个明文f1(i,j)～fx(i,j)，该块恰好出现k次的概率为的平均数目为

从图3(a)可以看出，当图像足够平滑时（p ＞0.2）分块大小不再影响L(p)，明密文对数x仅与p的变化有关.从图3(b)可以看出，块置乱加密图像越平滑分块越小，破解所需的明文对数越多，安全性也越好.对于单纯的块置乱加密，即使分块大小为2×2，若攻击者已知1 对或2 对明文-密文即可破解加密图像，加密图像的安全性仍然不高.

3.2 选择明文攻击

从上述分析中可以发现，图像纹理复杂度越高，攻击所需的明文-密文对数越少.类似文献[20]中提到的构造明文，利用上述结论可以得出在选择明文攻击下明文图像的构造方法.

对于构造明文进行攻击（选择明文攻击），仅需构造明文图像像素服从均匀分布，即可得到较为精确的块置乱矩阵.由3.1 节分析可知，图像分块越小，块置乱加密安全性能越高，对于2×2 的块，假设每个像素值均服从均匀分布，那么任意两个块像素值相同的概率为

代入δ=4 得这意味着对于在最坏的情况下，中可能存在接近个错误位置，此时只需一对明文密文，置乱矩阵估计正确率仍可以达到99.9%.

4 实 验

实验选取6 幅测试图像如图4所示.测试图像为512×512 的未压缩灰度图像.由于攻击的效果与已知图像的纹理程度及分块大小有关，假设攻击者在分块大小为2×2 和4×4 情况下，已知明文分别为(a)～(e).用已知的明文和密文得到置乱矩阵W2的估计矩阵解密图像(f)块置乱加密图像.

由图3(b)可知，图像纹理复杂度越高，分块大小越大，已知明文攻击效果越好.为验证图3(b)的分析结果，对于已知1 对明文-密文且大小为512×512 的灰度图像，图像分块大小为2×2(δ=4)及4×4(δ=16)的攻击结果如图5所示.

图4 6 幅测试图像Figure4 Six test images

图5 已知1 对明密文攻击结果（第1 行分块大小为2×2，第2 行为4×4）Figure5 Known one pair of plaintext-ciphertext attack result (the block size of the first line is 2×2,and the second behavior is 4×4)

在图5中，第1 排分别为已知图4(a)～(e)明密文对，在分块大小为2×2 时用估计矩阵解密图像(f)块置乱加密图像的结果.第2 排为4×4 大小下的攻击结果.从图5可以看出，在已知1 对明密文条件下，实施已知明文攻击可导致加密图像内容泄露，在同样分块大小情况下，已知纹理图像（Baboon）的攻击效果好于已知平滑图像（Airplane）.

在2×2(δ= 4)和4×4(δ= 16)条件下，已知1 对明文-密文攻击得到的正确率如表2所示.

表2 已知1 对明密文估计正确率Table2 Accuracy of estimation when one pair of plaintext-ciphertext is known

表2 已知1 对明密文估计正确率Table2 Accuracy of estimation when one pair of plaintext-ciphertext is known

明密文对 2×2/% 4×4/%Airplane 44.3 96.5 Lena 61.1 99.9 Man 66.8 99.3 Pepper 69.8 100.0 Baboon 94.1 100.0

从表2可以看出，在已知1 对明密文条件下，当最小分块为2×2 时，已知明文攻击可以破解近50%的置乱矩阵.当分块大小为4×4 时，攻击者在已知1 对明文-密文的条件下即可破解近100%的置乱矩阵.

当已知的明文-密文对增加到2 时，已知Lena 和Baboon 2 对明文-密文对，在分块大小为2×2 条件下，得到的置乱矩阵解密其余4个加密图像的攻击结果如图6所示.

图6 已知2 对明文-密文攻击结果Figure6 Known two pairs of plaintext-ciphertext attack results

从图6可以看出，当明密文对增加到2 对时，攻击结果已经可以完全分辨出图像内容，表3给出了分块大小分别为2×2 和4×4 时块置乱矩阵的正确率.

表3 已知2 对明文-密文 估计正确率Table3 Accuracy ofestimation when two pairs of plaintext-ciphertext is known

表3 已知2 对明文-密文 估计正确率Table3 Accuracy ofestimation when two pairs of plaintext-ciphertext is known

已知明文（2 对）攻击密文 2×2/% 4×4/%Lena-Baboon Airplane 100 100 Papper 100 100 Man 100 100 Camera 100 100

由表3可知，在已知2 对明文-密文对的条件下，即使分块大小是2×2 仍可以完全获得置乱矩阵，进而完全破解加密图像.实验表明，对于块置乱加密的已知明文攻击，攻击结果与图像纹理复杂度有关，图像纹理复杂度越高，攻击效果越好，图像分块越大.

图4中的测试图像均没有出现大面积平滑区域，为测试具有大面积平滑区域图像的攻击效果，图7选取2 幅明文图像作为已知的明文，测试图像均满足p ＞0.1，图7(a)中P= 0.2，图7(b)中P=0.15.

图7 2 幅测试图像Figure7 Two test images

利用图7中2 对明密文，在分块大小为2×2、4×4、8×8 条件下估计的置乱矩阵正确率可达83%、90%、92%.用估计的置乱矩阵解密图4(d)的块置乱加密图像，结果如图8所示，可以看出，对于p ＞0.1 的图像，攻击者利用2 对明密文图像即可破解超过80%的块置乱加密图像内容，加密图像的内容被严重泄露.

图8 已知2 对明密文(p ＞0.1)不同分块大小下的攻击结果Figure8 Attack results of known two pairs of plaintext-ciphertext (p ＞0.1)

5 结 语

为提高图像加密域可逆信息隐藏算法的隐藏容量，文献[16]提出了一种基于阿诺德变换的图像加密算法.该算法结合位平面、图像块、块内像素置乱生成加密图像，有效抵抗唯密文攻击和传统已知明文攻击.本文分析了ATBEM 算法的安全性，提出了一种针对ATBEM 的已知明文攻击方法.首先利用位平面的统计特性恢复出原始图像的像素值.在此基础上，利用图像块的均方根特征估计图像块的置乱加密矩阵.分析讨论了块大小、图像平滑性、块置乱加密矩阵估计正确率之间的关系.实验及分析结果表明，根据1 对明文-密文图像，当块大小为2×2 时加密矩阵的估计正确率超过60%；当分块大小为4×4 时加密矩阵的估计正确率近100%.如果攻击者得到2 对明文-密文图像，就能完全正确地估计块置乱加密矩阵，因此ATBEM 很难抵抗本文提出的已知明文攻击.