Image encryption based on block compression sensing and the improved magic square transformation

随着科学技术的不断发展，信息的安全问题备受关注。在信息安全领域，多图像加密是一个重要内容。图像传输时，往往不止传输一幅图像，而是传输多幅图像^[1-5]。数字图像具有数据量大、信息相关性强等特点，为了防止信息泄露，需要选择安全可靠，且运算时间复杂度低的算法对图像加密^[6-8]。置乱法是一种常用的传统图像加密技术，如幻方变换、Arnold变换、混沌变换、傅里叶和卷积变换等。其中幻方变换是一种加密数字图像的经典方法，部分学者在幻方加密图像方面做了相关的研究^[9]。WANG等人展示了幻方的周期性，并将其用于图像像素点的无序位置^[10]。LIU等人也对这种传统的幻方加密方法进行了研究^[11]。LI等人^[12]研究了通过混沌序列来改变像素点的值并使它们在图像中均匀分布^[13]。幻方生成的算法存在一定的缺陷，经一定幻方变换迭代后的图像，相邻像素群之间具有一定的相关性，图像的安全性明显降低^[14]。因此，为了提高图像加密的安全性，作者提出了改进的幻方变换加密方法。

图像传输过程中往往会因为信息量过大难以满足信息实时加密的需求，CANDES等人和DONOHO等人提出的压缩感知(compressed sensing, CS)理论能解决信息量过大造成的加密时间长的问题。压缩感知理论能用更少的采样值恢复出原始图像，并能在获取数据的同时对数据进行压缩处理^[15]。CS虽然有较大发展，但是在对较大尺寸图像进行处理时，所需运算存储空间较大，并且重构时间过长。针对大尺寸图像的传输问题，2006年，GAN提出了分块压缩感知方法(block compressed sensing, BCS)^[16]。BCS获取图像时采用相同的可压缩采样算子，因而压缩传输过程中所需可压缩采样算子的存储量大大减少，并且重建图像时不需要传输整幅图像的所有采样数据，重建图像块更容易实现^[15]。BCS的观测和重构都对每个图像块单独进行操作，减少了运算所需时间和存储空间，降低了其计算复杂度，能快速恢复出图像，对多图像的传输或是数据量大的图像传输速度有着极大的提高。

本文中提出了一种将分块压缩感知和改进的幻方变换相结合的加密算法，使用分块压缩感知对图像进行采样能够有效节省存储空间，提高运算时间，降低传输负荷，在压缩的过程中完成了图像的首次加密^[17-18]，由于分块压缩感知得到的加密图有明显的块效应，此时的密文安全性并不高，因此, 再用改进的幻方变换对分块压缩感知得到的加密图进行置乱操作，实现图像的二次加密，提高系统的安全性。本文中对提出的算法进行了测试，证实了算法的有效性。

2006年，CANDES和DONOHO等人首次提出压缩感知理论，压缩感知在数据采样的同时完成数据压缩。在信号采样的过程中，用少量的采样点实现了和全采样一样的结果，突破了Nyquist采样定理的限制。压缩感知理论表示，压缩信号或图像可以通过一个小的非自适应线性测量矩阵把一个高维的信号成功地映射到低维空间当中，要想完美重构出原始信号只需要从这部分少量的投影中求解一个最优化问题即可^[19]。

对于数据量大的图像信号，运用压缩感知理论时，不需要先对其进行高密度采样再做压缩处理，只需要通过简单测量便能同时完成采集和压缩。然而实践中发现，当接收端通过少量观测值重构图像时，对整幅图直接进行CS重构的运算量十分大。因而，GAN提出的BCS方法能很好的解决这一问题。

对大小为h×g的一幅图像进行分块，假设想要进行n个CS测量。在BCS中，图像被分成大小为n_g×n_g的小块，扫描每个图像块的像点，得到含N_g=n_g×n_g个元素的向量。记x_i=[x_i1, x_i2, …, x_iNg]^T为第i个图像块的数据，对每个图像块的数据进行观测，采用相同的观测矩阵Φ_g，得到M_g个观测值^[20]。x_i表示第i个块的矢量化信号，相应的输出压缩向量y_i可写为：

式中，Φ_g是M_g×N_g的观测矩阵，y_i为列向量，其长度为M_g，M_g≪N_g。观测每个图像块，共得到M=M_h(h×g)/N_g个观测值。

当接收端接收到某个图像块观测值后，选用相同的重构算法，对每个图像块进行重构，即可获得整幅图像。本文中采用的是运算量比较小的正交匹配追踪方法。

幻方的定义：以1，2，…，n²个自然数为元素组成的n阶矩阵：

若矩阵A的元素值满足条件：

式中，i, j=1，2，…, n, 称A为n阶幻方^[10]。

对数字图像采用传统的幻方变换进行加密，按行列顺序将图像矩阵P像素值与幻方矩阵A元素值依次对应。根据(4)式将矩阵A中元素a_ij移位至元素a_ijmod(n²)+1处，变换后的矩阵记为A₁，再将矩阵P的像素位置根据矩阵A₁元素所在位置做相应位移，迭代变换多次后获得变换图像。

当L=n²时，T_n²(a_ij)=(a_ij+n²)mod(n²)=a_ijmod(n²)=a_ij。

由此可见，传统幻方变换的周期为T=n²。经过n²次迭代变换，每个像素便回到变换前的位置，因此传统的幻方加密虽然置乱效果显著，但安全性很低，很容易遭攻击。因此，本文中提出了改进的幻方变换方法。

改进的幻方变换有效地解决了传统幻方变换周期性的问题。由于logistic混沌序列具有非周期性，因此矩阵A′的坐标值具有随机性。原幻方矩阵A中的元素随机移动到矩阵A′其它位置处，经过n²次迭代变换，每个像素不会回到变换前的位置，打破了传统幻方置乱的周期性。以4阶改进的幻方变换为例，其置换矩阵图如图 1所示。

Figure 1.  Displacement matrix

具体的实现步骤如下：

(1) 生成一个n×n大小的幻方矩阵A，幻方矩阵元素值a_{i, j}, 且i, j=1, 2, …, n。

(2) x₁(i)，x₂(i)是logistic混沌系统^[21]x_k+1=ux_k(1－x_k)迭代后的状态值，对其进行放大取整处理：

得到两组混沌序列X₁(i), X₂(i)，作为幻方变换移位参量。S表示原始矩阵元素值的和，floor(x)表示将x中元素取整，其值为不大于本身的最小整数。x₁(i), x₂(i)是初值不同的logistic混沌系统迭代后的状态值。

(3) 求得原幻方矩阵A中元素a_ij的坐标值(i, j)，a_ij=1, 2, …, n²，令A′=A。将A′和A按行列一一对应，将元素a_ij移动到元素A_{(X1(i), X2(i))}′，得到置乱后的幻方矩阵A″。

本文中提出基于分块压缩感知和改进的幻方变换的加密方法。图 2a和图 2b分别是本方法的加密过程和解密过程的流程图。首先对4幅大小相同的图像进行分块压缩感知处理，再将处理后的4张图像融合成一张加密图，然后通过改进的幻方变换对其进行二次加密。整个加密过程不仅解决了多图像加密数据量大的问题而且破坏了传统幻方加密的周期性。解密过程为加密过程的逆过程。图 2b中D为改进幻方逆变换后的合成解密图。

Figure 2.  The improved encryption method

加密步骤见下：

(1) 输入4幅大小相同的加密图I_i(i=1, 2, 3, 4)，图像大小为256×256；将加密图I_i(i=1, 2, 3, 4)分别以128×128大小进行分块，每幅图像分块压缩后的大小为192×256。

(2) 将分块压缩后的4幅图像融合为单幅图像，表示为矩阵I。随机生成1个256×256的幻方矩阵，将其中小于等于192×256的元素点取出生成1个新的2维矩阵B(大小为192×256)。

(3) logistic混沌系统迭代产生两个混沌序列u₁(i)和u₂(i)，通过第2.3节中(4)式产生密钥序列k₁和k₂，长度分别为192和256；对矩阵B分别做行置乱和列置乱，k₁, k₂分别控制行和列的置乱位置坐标，得到置乱矩阵C；置乱过程如图 3所示。

Figure 3.  The scrambling process

(4) 将矩阵C转换成长度为R=192×256的1维序列C_R，按升序重新排列序列C_R，并用序列V₁和V₂分别记录升序排列之前的矩阵C的行元素x(i)和列元素y(i)的所在位置，然后用序列V₁置乱x(i)得到序列x′(i)，序列V₂置乱y(i)得到序列y′(i)。

(5) 对图像矩阵I做改进的幻方变换，使其图像矩阵I的每一个像素值按照坐标(x′(i), y′(i))所对应的元素进行移位置乱操作，得到置乱后的图像矩阵I′，实现了图像二次加密。

该算法是对称加密算法，解密过程为加密的逆过程。

在MATLAB R2010b平台上进行数值仿真，选用4幅大小为256×256的灰度图像“Barbara”, “Lena”，“fruits”, “peppers”作为原始图像，如图 4a~图 4d所示。根据原始图像的大小选择合适的随机测量矩阵，分别将4张原始图像通过压缩感知进行分块加密，再将压缩后的4张加密图融合为一张图。其中，随机测量矩阵用来作为密钥1。然后再进行改进后的幻方变换，得到二次加密后的加密图像如图 4i所示，其中混沌参量值x₀，u为重要的解密密钥。为了保证实验的普遍性，对多组图像进行了测试，其中图 4e~图 4h中4幅256×256的灰度图像“candy”, “milk”，“flower”, “Tiffany”的解密图如图 5e~图 5h所示，解密过程是加密过程的逆过程，解密图像如图 5所示。

Figure 4.  The original image and the encrypted image

Figure 5.  The decrypted image

解密结果中，可以清晰地看到重建的原始图像。通常，相关系数(correlation coefficient，CC)C_CC和峰值信噪比(peak signal-to-noise ratio，PSNR)R_PSNR被用来评估解密图像的质量。相关计算公式表示为：

式中，σ表示原图像与解密图像之间的均方误差，E代表期望值，f和F分别代表原始图像和解密图像。采样样本大小与原始样本大小的比率定义为压缩比r=[(N-M)/N]×100%。当设置M=96，压缩比为62.5%时，通过正确的密钥解密出的图像的CC值记录在表 1中。由表 1中的数据可以看出，所有重建图像的CC值都高于0.99，PSNR值都大于35dB，这意味着每个解密图像的质量都非常高。

分别对4幅大小为256×256的灰度图像做分块压缩感知，分块尺寸为128×128, 64×64。当每幅图像的块观测值数目为图像块像素个数的0.75倍时，对图像进行128×128分块处理时，加密系统所需时间为0.98s，对图像进行64×64分块处理时，加密系统所需时间为0.44s。实验结果显示，随着分块尺寸的变小，加密系统所需时间减少，能很快地处理图像，但同时发现，随着块尺寸的无限缩小，图像质量逐步变差，因此不能无限小的分块。当图像分块大小分别为128×128, 64×64时，由表 2中解密图像的CC值可以看出，解密图像质量良好，所以本文中提出的加密系统选用128×128大小的图像块进行分块压缩处理，图 6a~图 6d为分块尺寸为64×64时“candy”, “milk”，“flower”, “Tiffany”的解密图。

Figure 6.  The decrypted image with block size of 64×64

在图像传输和处理的过程中，密文很容易受到噪声的攻击，降低解密图像的质量甚至会使解密图像无法识别出原始信息。因此在设计一个好的加密系统时，需要考虑系统抗噪声攻击的能力。为了测试系统的抗噪声攻击能力，按照以下形式给加密图像增加乘性噪声：

式中，F和F′分别是原加密图像和受噪声影响后的加密图像，k表示噪声的强度系数，G是噪声类型。

图 7中给出了加密图像在各种噪声情况下重构的解密图像。当加密图像加入了强度为0.1的随机噪声时，原始图像和解密图像的PSNR分别为21.1092dB, 20.9332dB, 23.7608dB, 22.7085dB，对应的CC值分别为0.9612, 0.9531, 0.9795和0.9637；当加密图像加入了均值为0、方差为0.1的高斯白噪声时，原始图像和重构的解密图像间的PSNR分别为30.3852dB, 30.6284dB, 32.8713dB, 32.7124dB，CC值分别为0.9895, 0.9877, 0.9942和0.9908。此时的噪声强度对重构的解密图像影响不大，图像很容易被重构，由此看出作者提出的算法具有良好的抗噪能力。

Figure 7.  Noise analysis

灰度直方图是判断一个图像的统计特性的指标，一种理想的加密算法，应该破坏原始图像的统计特性，使不同的原始图像具有均匀的统计分布或者类似的与原始图像无关的灰度直方图。

图 8中给出了4幅原图的灰度直方图。其中横坐标表示灰度值(灰度级别)，纵坐标表示具有各个灰度值或者灰度级别的像素在图像中出现的次数或者概率, 横纵坐标均无量纲。图 8a~图 8d最终为原图灰度直方图, 图 8e为加密后密文的灰度直方图(直方图横坐标表示灰度级，纵坐标表示图像中该灰度级出现的频率，均无量纲)。从测试结果可以看出, 4幅原始图像的灰度直方图完全不同，它们加密图像的灰度直方图与任意一幅图的灰度直方图都不相同，成均匀分布。为了保证实验的普遍性，对多组图像进行了测试，所得到的加密图像都具有相似的分布特征。可以看出，改进后的加密系统仍具有好的统计特性，从加密图像的灰度直方图，攻击者很难获得原始信息。

Figure 8.  Histogram analysis

在本次设计的加密算法中，密钥参量分别是测量矩阵R，logistic的系统参量u和初值x₀。当初始值为x₀+dx(dx的范围是-0.5×10^-15~0.5×10^-15)时，给出了4幅图像的相关增长量dx的CC值曲线(横坐标为dx的取值范围，纵坐标为CC值的大小，增量dx和CC值均为无量纲化的)。图 9分别是图像“Barbara”，“Lena”，“fruits”，“peppers”每个偏差所对应的CC值曲线。图 10a~图 10d分别是正确密钥时所对应的解密图。图 11a~图 11d分别是错误密钥x₀′所对应的解密图。可见密钥正确时，解密图像与原始图像完全一致，而密钥有微小偏差时，图像将完全不能解密。表明了本算法对密钥具有良好的敏感性。

Figure 9.  CC curves of the decrypted images for x₀+dx

Figure 10.  Decrypted image with correct keys

Figure 11.  The decrypted image with incorrect keys

本文中提出了一种基于分块压缩感知和改进的幻方变换的数字图像加密算法，在压缩的过程中完成了图像的第1次加密，再用改进的幻方变换对图像进行置乱，实现图像的二次加密。这种加密算法能够很快地处理大数据的图像，并在压缩感知之后对像素进行了空间位置置乱，增强了图像传输过程中的安全性。分块压缩感知方法是把整幅图像分成等尺寸的块，对每个图像块进行独立观测和重构，减小运算复杂度，并且图像重构前不需要传输整幅图像所有观测数据，提高了实时性。由混沌序列控制位置坐标，改进后的幻方置乱没有传统幻方置乱的周期性，增强了置乱的安全性。置换技术有效地打乱输入明文的次序，能有效地掩盖明文的统计特性、抵御统计分析。由测试结果可知，本文中提出的加密系统能高质量地重构出原始图像，算法对密钥敏感，具有较好的统计特性和较强的抗干扰能力。将分块压缩感知和幻方变换加密结合，应用分块压缩感知进行采样能够有效节省存储空间，减小传输负荷，分块压缩感知和置乱技术的结合，在研究大数据图像处理过程中，能较快较安全的完成图像传输。