基于压缩感知和DNA编码的图像加密算法

宫 帅,霍 橙,谢 冬

(安徽师范大学计算机与信息学院,安徽 芜湖 241002)

压缩感知(compressed sensing,CS)理论是一种新的信号处理框架. CS指出将信号从高维空间投影到低维空间,可同时完成采样与压缩过程. 根据投影得到的测量值求解最优化问题,便可从极少数的采样值里高概率地重构原始信号[1-3]. CS的研究主要分为3类:(1)使原始信号满足某种表示方式下的稀疏性;(2)设计合适的测量矩阵使观测值能被正确恢复;(3)设计恢复算法从观测值中恢复出原始信号. CS不局限于奈奎斯特采样定理的限制,在同样的采样值情况下,可传输更多的信号,故能更好地重构原始图像. 近些年来,基于CS的图像加密方案构造是图像加密领域的一大研究热点[4-7].

DNA编码规则[8-9]是DNA计算应用于密码学领域的一种新思维. DNA计算的基本原理是以DNA序列为载体,将要处理的信息转换为DNA分子序列,利用DNA的碱基互补配对性质与运算法则进行信息处理,具有大规模并行计算和低能耗的特点. 1994年Adleman利用DNA碱基互补配对的思想,解决了NP问题的有向哈密顿问题[10],DNA计算自此诞生. 之后,Enayatifar等提出了基于遗传算法和DNA序列的图像算法[11],通过Logistic混沌映射与DNA编码得到DNA掩码初始值,再通过遗传算法得到最佳的掩码. 李红凯等改进了DNA编码的真彩图像加密算法[12],利用混沌序列为映射,对图像进行DNA编解码及DNA加操作时融入了混沌系统的随机性. 李孝东等[13]提出由图像的SHA-256哈希值来生成算法密钥,结合DNA编码、运算规则与混沌映射对图像进行逐行随机编码加密.

传统单一的加密算法密钥空间较小且加密后的密文图像相关性较高,在安全方面仍有很大的改进空间. 本文将CS与DNA编码相结合,提出了一种更加安全、高效的图像加密算法. 首先将明文图像进行CS压缩处理;其次,将处理后的矩阵转换并拆分为多个2 bit二进制矩阵;最后,根据DNA编码规则和DNA运算规则,将转换后的序列与帐篷映射产生的序列进行二次扩散,将加密后的序列先分割后合并形成矩阵,即可得到密文图像.

1 基础知识

1.1 压缩感知

CS是在采集信号的同时对数据进行压缩处理,目的是采集尽可能少的信号并以高概率重构出原始信号.

对于一个信号X∈RN,X中包含k个非零值,通过测量矩阵A获得M个线性观测量,可表示为:

Y=AX,

(1)

式中,A∈RM×N,Y∈RM×1.

若将测量矩阵A视为对称加密体制的密钥,则CS可视为一对称加密系统[5,7]. 如图1所示,X∈RN×N为明文图像预处理后的矩阵,A∈RM×N为测量矩阵,产生矩阵的初始参数可视作密钥.Y∈RM×N为观测矩阵,即形成的密文图像.

图1 压缩感知的压缩(加密)过程Fig.1 Compression(encryption)process of compressed sensing

压缩感知的感知部分即利用设计的测量矩阵A和测量后的矩阵Y来重构原始矩阵X,进而恢复原图像. 压缩感知的重构算法主要分为3类:组合算法(傅里叶采样[14]、链式追踪算法[15]等)、贪婪算法(正交匹配追踪算法[16]等)、凸优化算法(基追踪算法[17]、梯度投影算法[18]等). 本文为对比实验,对计算量和精度的要求居中,故选择正交匹配追踪算法(orthogonal matching pursuit,OMP)进行重构原始图像. OMP算法的基本思想是每次迭代选择一个与测量信号最匹配的、与当前冗余向量最大程度相关的某列进行正交化处理,求得稀疏逼近解,达到一定的阈值条件或迭代次数便可强制终止.

1.2 DNA编码

DNA计算以其超大规模和并行运算等特点被广泛应用于密码学中. DNA序列的4种脱氧核苷酸AGCT互补,若二进制数据00、01、10、11参照DNA的编码方式,将会产生4!=24种编码方式,再根据DNA的碱基互补规则,会有8种组合方式符合互补规则[11-13]，如表1所示.

表1 DNA编码规则Table 1 DNA coding rules

根据编码规则1进行编码组合,灰度值200二进制表示为11001000;若根据编码规则4,其可以解码成一个新的像素值147,可二进制表示为10010011. 因此,根据不同的编码规则,可将灰度值解码成不同的像素值. 在图像加密时可将8 bit像素值转化为2 bit的DNA序列进行运算. DNA序列的加减法运算是源于二进制数据的加减法运算,若采用第一种编码方式对DNA进行加减运算,会产生如表2 和表3所示的结果.

表2 DNA加法运算Table 2 DNA addition

表3 DNA减法运算Table 3 DNA subtraction

8种不同的编码方式会产生8种不同的运算规则,在进行加密时通常会利用参数来进行选择8种编码方式的一种或者是几种混叠在一起进行加密,以达到扩散的目的.

1.3 帐篷映射

帐篷映射是一种简单且相对稳定的混沌映射[4],其表达式如下:

(2)

式中,μ∈(0,1),z(n)∈(0,1),n=1,2,…. 系统达到混沌状态,与Logistic映射相比,基于混沌映射的系统具有良好的相关性且产生的随机值分布更均匀[4],故本文的混沌部分选取帐篷映射实现.

2 基于压缩感知和DNA编码的图像加密算法

为解决压缩感知后产生的小数和负数导致的DNA编码过程复杂且精度不够问题,本文采用后稀疏化对图像进行压缩感知处理,即在解密过程中对密文图像和测量矩阵稀疏化后调用OMP重构算法进行重构,再做逆稀疏化得到重构图像.

图2 基于CS与DNA编码的图像加密方案Fig.2 Image encryption scheme based on CS and DNA coding

2.1 加密算法

(1)将大小为M×N的原始图像I转换为大小为N×N的矩阵(若M>N,将其分组表示成两个N×N的图像;反之,则将其补成N×N的图像);

(2)调整产生测量矩阵算法中的参数(矩阵的行数M与列数N),产生一个适当的测量矩阵A;

(3)随机选取一种编码规则,将压缩后的二维矩阵Y转化为M行N列16 bit的二进制二维矩阵Y1;

(4)将Y1拆分为8个M行N列2 bit的二进制二维矩阵,并将8个矩阵分别转化为8个1行M×N列2 bit的二进制序列,然后将 8个序列合并成一个M行8×N列2 bit的二进制矩阵Y2;

(5)利用帐篷映射产生一个1行8×M×N列2 bit的二进制序列(产生序列时参数可调)并将其转换为M行8×N列的二维矩阵Z1,利用DNA编码规则对矩阵Y2和Z1进行DNA配对加法/减法运算得到DNA扩散后的矩阵Z2;

(6)选取一种不同于步骤(3)的编码规则,对矩阵Z2进行二次编码,拆分转置并进行进制转换,得到新的M行N列的二维矩阵Z3即为加密后的矩阵.

2.2 解密算法

(1)选取与加密过程对应的编码规则对密文图像做逆二次编码,并拆分为8个M行N列2 bit的二进制二维矩阵,将8个矩阵先转置再合并为一个M行8×N列2 bit的二进制矩阵Y′2;

(2)将Y′2与帐篷映射产生的矩阵Z1进行DNA配对减法/加法运算;

(3)对逆规则后的矩阵做逆编码处理并合并矩阵做十进制转换得到DNA解密后的矩阵Y′1;

(4)对矩阵Y′1和测量矩阵A做稀疏化处理并作为输入调用OMP重构算法;

(5)对重构后的矩阵做逆稀疏化处理得到重构图像.

3 实验仿真

为方便分析和对比,本文选取传统的基于CS的图像加密方案和基于DNA编码的图像加密方案用作对比实验,采用256×256的三类灰度图像(人物、动物、景物)作为实验明文图像,以MATMAB R2013b作为实验仿真平台对算法进行验证. 在图3中,A∈R200×256,A中d(稀疏度)=160,帐篷映射z(0)=0.85,μ=0.3.

图3 混合加密的加密解密效果示意图Fig.3 Schematic diagram of the encryption and decryption effects of mixed encryption

3.1 重构图像正确性验证

从图3可以看出,本文所用加密算法对不同种类图像(人物、动物、景物)的加密和解密没有影响,图像加密后完全类似于噪声,视觉无法辨认,隐藏了原始信息. 加密后的图像在外界无干扰的情况下可完全恢复原始图像.

一般地,用峰值信噪比(peak signal to noise ratio,PSNR)通过量化的方法来衡量恢复的图像品质. PSNR值是原图像与被处理图像之间的均方误差相对于(2n-1)2的对数值,单位为dB:

(3)

式中,Pmax为图像的最大像素值;I为原始图像;I′为重构图像;VMSE为I和I′的均方差. PSNR值高于40 dB,说明图像重构质量非常接近原图像;在30～40 dB,表示图像失真但可接受;在20～30 dB,表示图像重构质量差;低于20 dB,表示图像不可接受. 从表4数据看,两种单独加密方案重构图像的PSNR值均在30～40 dB,混合加密方案重构图像PSNR值均高于40 dB,可知混合加密方案重构效果较好,重构图像非常接近原图像.

表4 重构图像的PSNR值Table 4 PSNR values of reconstructed images

3.2 密文图像相关性分析

在图像加密方案中,要求产生的密文图像具有良好的统计特性. 相关性是衡量密文图像抵抗统计学攻击的标准,好的加密效果要求相邻像素点的相关性尽可能地低. 相关性系数定义如下:

(4)

式中,K为随机抽取的K对相邻像素点,本实验K=1 000;xi和yi是随机选择的相邻像素值. 表5提供了原始图像在3个方向上的相关性系数,表6、表7和表8分别提供了3种密码方案的密文图像在3个方向上的相关性系数. 数据表明,混合加密方案的密文图像在3个方向上的相关性均较低,即密文图像具有良好的统计特性.

表5 原始图像相关性Table 5 Correlation of original images

表6 密文图像对角线相关性Table 6 Diagonal correlation of ciphertext images

表7 密文图像水平相关性Table 7 Horizontal correlation of ciphertext images

表8 密文图像垂直相关性Table 8 Vertical correlation of ciphertext images

3.3 密文图像抗猜测攻击性分析

方案的抗猜测攻击性是指攻击者猜测的密钥与真实密钥存在一定的误差,即密钥的敏感性. 本文的抗攻击性分析分为3个不同的条件进行:第一组将密钥1(测量矩阵)中的系数d进行细微改变,由原来的d=160改为d=159来重构图像,其他因素不变;第二组将密钥2(帐篷映射产生的序列)中的初值由原来的z(0)=0.85改为z(0)=0.850 000 000 001来重构图像,其他因素不变;第三组将第一组和第二组的组合联立,即密钥1和密钥2同时改变,其他因素不变.

本文在分析时结合主观的肉眼观察和客观的PSNR值来区分差距,如图4所示,微调密钥后的重构图像与原始图像差别极大. 由表9中的数据可知,第一组的PSNR值均低于20dB,说明重构图像效果极差,已不能接受;第二组和第三组的PSNR值相差极小,且均小于第一组的PSNR值,说明图像重构的效果更差. 实验数据表明,本文的密钥1和密钥2均具有较好的敏感性,文中的加密算法能够较好地抵抗来自密钥的敏感性攻击,即加密算法的抗猜测攻击性强.

图4 不同类型图像的加密解密效果示意图Fig.4 Schematic diagram of the encryption and decryption effects of different types of images

表9 3组实验PSNR值Table 9 The PSNR of three experiments

4 结论

本文基于压缩感知理论与DNA编码运算规则,提出了一种图像加密方案,先对图像进行后稀疏化的压缩感知处理,再将压缩后的矩阵转换并拆分为多个2 bit二进制矩阵,使用DNA编码运算规则和二次编码实现对多个二进制矩阵的单独加密,从而达到对图像的像素扩散. 实验结果表明,提出的加密方案重构效果较好,且能够抵抗一些常见的攻击.