二次广义cat映射的混合混沌图像加密算法

谢国波，邓华军

广东工业大学 计算机学院，广州 510006

1 引言

在互联网飞速发展的时代，数字图像由于直观性强、信息量丰富，得到了各种领域的广泛应用和研究，图像信息现在已成为人类进行信息交流的重要方式之一。同时其安全性引起了人类的广泛关注，从而加密技术成为了广大学者专研的一门热门课题[1]，探索出安全性高的算法显得尤为重要。由于混沌系统是一种非线性动力系统，对初始条件和系统参数非常敏感，且产生的混沌信号难以分析，具有伪随机性不可预测性等特点，在图像加密中得到了广泛应用和研究[2]。

英国数学家Matthews[3]在1989年首次提出混沌系统用于数据加密。接着人们纷纷提出基于混沌图像加密的算法[4-11]。总体上可分为灰度值替换和像素位置置乱，以及两者的混合结合，但图像加密的安全性及实时性要求和效率还有待加强。

为了获得更安全与效率高的图像加密方案，近年来，一些新的加密算法应运而生，如一次一密，比特级置乱，利用数学模型，利用DNA编码等加密算法逐渐进入大家的视野[12-16]。但上述方法存在一定的缺陷，如一次一密虽然是安全信息领域的一项重要课题，具有形式简单，运算效率高的优点，安全性高也毋庸置疑。但是有一些问题，比如一次一密的密钥流必须是随机产生，且密钥流至少与被加密的信息等长，不可重复使用，在密钥储存和分配存在较大困难，实用性不高。比特置换加密虽然置乱效果比传统方法更具优势，但是在加密时需将像素值全部转换成二进制bit级进行图像加密，效率低，耗时多。利用感知器的数学模型加密虽然在加密过程中灵敏度高，鲁棒性好，但是需要考虑的因素太多，还存在密文明显不均匀的问题，复杂度也相对较高，实用方面还有待提高。DNA序列加密方法虽然取得了一些成果，加密效果良好，但是因生物计算难题，编码过程复杂，实验成本高因素的影响，无法满足实用，且加密的相关系数较高，容易遭到攻击者破坏。

针对上述加密方法存在的一些不足，在分析这些方法的基础上，提出了新的改进的加密算法。利用广义cat映射第一次对像素值迭代，第二次进行置乱，然后再用广义Henon映射产生的混沌序列与置乱后图像进行扩散加密运算。最后又引入了模和异或相结合的变换，使得攻击者无法轻易有效地获取混沌序列，进一步提高了加密的安全性。理论分析和仿真实验表明，改进算法不仅可有效地抵抗选择明文攻击，同时在统计分布性、密钥空间、抗差分攻击能力和伪随机性等方面都具有更好的性能。

2 混沌系统映射

2.1 广义Henon映射

近年来，随着混沌加密沌技术的不断发展，由于低维满足不了加密的实际需求，而Henon映射是二维中应用比较多的映射之一。方程如下：

当a=1.4,b=0.3时系统处于混沌状态。当b=1时，运动中系统保持相平面积不变，被认为是保守系统；当b＜1时，运动中系统相平面积缩小，是耗散系统。此时，最大Lyapunov指数等于0.418。当前大量研究表明，在非线形保守系统中也有混沌，只是没有混沌吸引子。在非线形耗散系统中有混沌并伴有混沌吸引子。基于前人研究，在2002年Richter定义了无限维的广义Henon混沌系统，其动力学方程表示形式如下：

式中，c表示维数，当c＞2时，该系统处于超混沌状态；i=2,3,…,c；p和q为控制参数，实验证明当 p=1.76,q=0.1时系统处于超混沌状态。作为当前具有内在随机特性的广义Henon映射逐步成为人们在混沌图像加密过程中经常用到的混沌映射之一。基于此，本文研究三维Henon映射的超混沌现象，用于图像加密技术的应用中，其表示形式为：

称为广义的三维Henon映射，当1.07≤q≤1.097和p=0.3时，出现混沌现象。

2.2 广义cat映射

Cat映射，又称Arnold映射，是一个二维的可逆混沌映射，被广泛用于图像素位置置乱，其表达式一般形式为：

由于二维cat映射的密钥空间较小和逆过程计算简单，且基于图像位置的加密算法并不改变图像本身像素值，安全性能较低。为了提高图像的加密效果，且因为cat映射自身具有初值敏感性和快速混沌等优良特性，提出定义了一种广义猫映射，动力学方程为：

u,v为正整数，是系统的控制参数。xn和yn是一个N×N图像的像素点位置，其取值扩展到0至N之间，并且以N为周期，满足det(A)=1，保留了传统二维cat映射的保面积的一一映射特性。但cat映射具有回复性，多次应用cat映射置乱迭代后，又会恢复到原来的状态。为了解决这个问题，文中设计的算法采用映射式（5）进行迭代和置乱时，置乱若干次后，当图像的像素点位置发生显著改变的情况下，将其与广义Henon映射结合扩散加密，使其像素值也发生了变化，避免了因为出现重复图像而带来的安全隐患。同时迭代和置乱时都使用不同的矩阵，意味着迭代和置乱的参数u,v的值不同，而且采用猫映射置乱和迭代的次数不同，使得Amold置乱的矩阵也会不同，通过使用不同的置乱控制参数u,v，有效避免了因Amold映射的周期性而导致的像素点置乱失效问题。同时增加了复杂度，并且增大了密钥的空间，从而一定程度上提高了算法的安全性。

3 算法分析与设计

3.1 加密概要

本文针对传统的Henon映射和cat映射产生的序列加密算法安全性不够高，提出基于广义cat映射和三维广义Henon映射产生的混沌序列，通过调节混沌系统控制器参数，可以产生更加复杂的混沌序列来提高加密的抗攻击性和安全性。下面对图像加密主要分三个步骤：迭代、置乱和扩散。迭代时，使用广义cat映射对像素位置进行多次迭代，来增加像素位置变化的范围。并且迭代次数与原始图像密切相关，通过公式计算得到。置乱过程时，再次利用广义cat映射（与迭代时的混沌系统控制参数不同）将迭代后的图像按照从上到下，从左到右进行多轮置乱，轮数也是由原始图像通过不同计算公式得到。然后采用广义Henon映射方程进行迭代来产生混沌序列，取值从1 001次开始取，有利于增加复杂度，加大破译难度，接着经过公式变换和预处理，得到最终混沌序列。其间运用模和异或相结合的算法，使得攻击者无法有效地获取混沌序列，进一步提高了加密的安全性。最后将置乱后的图像与广义猫映射产生的最终混沌序列经过像素扩散得到加密图像，完成加密过程。

3.2 加密步骤

步骤1输入要加密的原始图像，用矩阵表示为M×N的图像P，进行边界填充0（黑色），使图像长和宽相等（前提是M=N，如果M＜N，则通过补图的方式将图像补成大小为N×N新图像，如果M＞N，则补成大小为M×M的新图像）。假设处理后的大小为M×M ，记为B。

步骤2把图像B读取成一维数组C，计算像素点总和sum,混沌系统的置乱次数为k1=mod( )sum,256+M,迭代的次数k2=1 000+mod(sum,1 000)，将k1，k2作为内部密钥。

步骤4将D按照从左往右，从上到下规则依次利用广义cat映射式（5）对其像数值进行置乱，置乱k1次后，得到加密图像为F。

步骤5由外部密钥x1,y1,z1和a,b作为广义Henon映射的初始值进行迭代，按照式（3）迭代1 000次后开始取值，产生三个M×M混沌序列分别是{Xk|k=0,1,…,M×M},{Yk|k=0,1,…,M×M},{Zk|k=0,1,…,M×M}，然后将这三个序列经过式（6）变换得到RX,RY,RZ。

步骤6接着对RX,RY,RZ混沌序列进行一定的处理，取每个元素的小数点后第4，5，6位组成一个新的整数序列，然后将它们对256取余得到QX,QY,QZ,并将其转化成二进制，使得结果和图像的灰度值一样在（0～255）之间，再将广义cat映射迭代后图像D像素点的值也转化成二进制。

步骤7将QX异或QY异或QZ异或D，得到序列S，接着对图像序列F进行式（7）扩散变换即可得到最终加密序列G。其中F(i)和F(i-1)分别是图像内部垂直或水平相邻像素点的值。

步骤8将最终加密序列转化成十进制还原成图像，得到加密图。解密过程为上述过程的逆过程，此处不再赘述。加密流程如图1。

图1 图像加密流程图

4 实验仿真及算法安全性分析

文中的图像加解密算法是在matlab2016a环境下进行，选取256×256的8位lena灰度图像作为实验仿真测试图像，混沌系统的控制参数设置为a=1.08,b=0.3,u=75,v=125,u1=50,v1=100,外部密钥为x1=0.315 623 56,y1=0.456 336 18,z1=0.635 897 16,x0=0.326 953 62,y0=0.416 383 61。迭代次数k2和置乱次数k1作为内部密钥，由图像本身的像素值特性决定。加密结果如图2，（a）为原始图像，（b）为原始图像经过迭代后的效果图，（c）为（b）经过置乱后的效果图，（d）为经过扩散后的最终加密图像，（e）为正确解密图像，（f）为当对密钥x1增加10-8微小量0.000 000 01后的解密图。经验证，任意改变其中一个密钥的10-8微小增量，得到的解密图与原始图像差距巨大。由此得出文中加密方法对密钥具有很强的敏感性，加密效果好，可以抵抗敏感性攻击。

4.1 直方图统计特性分析

图3为加密过程灰度直方度，通过观察分析，明文图像和加密后图像的灰度统计值有着显著的差异，明文图像灰度直方图分布不均匀，具有强相关性，加密后各直方图分布很均匀，较好地隐藏了明文图像的分布规律，攻击者很难从直方图中读取任何有意义的信息。从而有效地抵御统计分析攻击。

图2 加密解密图

图3 灰度直方图

通常用直方图的方差来衡量加密图像的均匀性，灰度直方图中有横纵坐标，用横坐标表示灰度级，纵坐标表示每个灰度级出现的像素个数。均匀性计算公式如式（8）所示，其中Z是直方图中的不同灰度级像素个数分布统计值，zi和zj分别是灰度值等于i和 j的像素个数分布统计值。密文直方图方差值越小，表示其加密图像的均匀性越高，当在相同明文图像中用不同密钥加密的密文图像的两个方差值越接近，表示当密钥变化时密文图像的均匀性越好。文中取外部密钥(x1,y1,z1,x0,y0)作为key1和只改变相关参数x1,y1,z1,x0,y0分别加密过后的密文迭代图，置乱后图，扩散后图的直方图进行数学均匀性计算，其中方差值在5 000左右浮动，每个灰度值中像素数的平均波动约为70左右，相比于明文直方图的方差值675 536.562 8，相比于文献[11]的方差值，本文算法密文均匀性更好，表明文中算法的加密算法有效性高。

本文均匀算法中，密文均匀性方差数值如表1所示。

4.2 相邻像素点相关性分析

为了分析说明原始图像和经迭代、置乱和扩散的程度，分别从水平、垂直、对角方向随机抽取原始图像和加密图像100对相邻点像素，然后分别作出三个方向的像素散点图。图4（a）表示原始图像水平方向相邻像素散点图，图4（b）表示加密图像在水平方向的相邻相素散点图。图4（c）～（f）依次表示垂直方向，对角方向的原始图像和加密图像的相邻相素散点图。对比观察分析散点图可得，原始图像三个方向各像素间存在较强的线性对应关系，而加密图像三个方向的像素间散点分布比较均匀，呈现出随机性。

为了定量论述原始图像和加密过程后的各图像像素之间的相关性，分别从图像的水平、垂直、对角方向选取所有点进行测试。通过式（9）～（12）计算出相邻像素的相关系数，计算结果如表2。

式中I，I′表示第i对像素点灰度值，Ii和I'i分别表示图像中同方向相邻像素点的像素值，γII′表示相邻像素的相关系数。相关系数越接近1表示高度相关，相关系数越接近0，表示越不相关。由表2计算结果可知，原始图像的相关系数接近1，高度相关，加密的图像相关系数都接近0，相关性极低。由此得知，文中加密算法具有良好的效果，安全性高。

4.3 密钥空间和执行效率分析

密钥空间是衡量加密算法安全性高低的重要一方面，因此，一个好的加密算法应保证有尽可能大的密钥空间。文中采用混沌系统的x0,y0,x1,y1,z1这5个状态变量的初始值作为外部密钥和迭代置乱次数k1，k2作为内部密钥，假设外部初始值的密钥都是双精度数据，至少可以保留15位有效数字，由此得出加密外部密钥空间为1075，又因为k1,k2取值范围一般为（10，100），因此，文中密钥空间为：k1×k2×1075≥1077，高于文中提到的大多数文献加密算法，再加上广义Henon映射的P参数，密钥空间将会更大，可以有效地抵御穷举攻击。加密算法的时间复杂度是加密效率的重要指标，实验在硬件环境为Intel双核2.60 GHz CPU，4 GB的RAM，500 GB硬盘，Windows 7操作系统个人计算机上，采用matlab2016a编译器平台进行实验，最终加密密钥和像素值均用15位整数表示。在上述计算机系统环境下对256×256的8位Lena图像经三轮像素迭代加密，平均耗时约0.039 6 s，将文献[5]的算法在同样的环境下，采用相同数据类型和图像进行实验，耗时0.089 6 s，可见文中算法时间上少了1倍多，文献[5]的时间复杂度高的主要原因是在实现图像置乱时比较耗时，所以整个时间复杂度增加。而文中算法主要分三个步骤：迭代、置乱、扩散。其时间复杂度分别为 O(MN)、O(MN)、O(MN)，当M、N不是很大的时候，整体复杂度约为O(MN)，文中算法最耗时的部分是扩散阶段中的浮点数转整数运算，整体上看，文中算法要比文献[5]中的算法运行得更快。同时文中算法迭代次数为MN/6，低于文献[6]的MN/4，可见，文中算法一定程度上提高了加密的运行效率。

表1 密文图像方差计算统计结果表

图4 相邻像素相关性散点图

表2 相邻像素点相关性计算结果表

4.4 信息熵分析

基于香农提出的信息熵概念，近年来被广泛应用于与信息相关的各种领域。文中信息熵反映的是图像中灰度分布情况，灰度分布越均匀，意味着不确定性信息就越多，信息熵就越大。经过计算，文中原始图像的信息熵为6.728 3，迭代后图像，置乱后的图像，扩散加密后的图像信息熵分别为7.966 3、7.981 2、7.989 6。由此得出，加密码后的信息熵明显大于原始图像，并且加密后的图像信息均已接近灰度级为256的图像的最大信息熵8，表现出良好伪随机性，加密安全性高。

4.5 抗差分攻击能力分析

一个安全性高的加密算法，应该具有对明文强烈的敏感性。敏感性越强，抵御差分攻击能力越好，即给明文任一微小的增量或者减量，密文图像将会产生显著的改变。由于一些攻击者针对明文的一些特性，通过观察密文的变化规率，进而反推导加密过程，使加密存在安全的威胁。基于此，文中的迭代和置乱过程都是与明文的像素值相关。从而使加密过程与明文自身特性密切相关。文中使用NPCR（像素值改变率）和UACI（归一化平均改变强度）两个衡量指标来描述加密过程与明文之间的关系。假设用C1表示明文图像加密后的密文，C2表示明文中像素值增加和减小任一微小量的加密后的密文。设在位置(i,j)的像素值分别为C1(i,j)和C2(i,j)。定义一个二维矩阵P与C1大小等同。当C1(i,j)=C2(i,j),定义P(i,j)=0,否则P(i,j)=1；NPCR和UACI的计算公式可定义如下：

从明文图像任取一点坐标，使像素值作微量改变，如位置为（6，102）的像素点，将其像素值由106改为107，根据式（13）～（14）计算出 NPCR=99.79%,UACI=33.96%，由此得出，文中算法对明文具有强烈的敏感性，抗差分攻击能力好。

表3 图像的NPCR和UACI计算结果表

4.6 经典攻击类型分析

加密算法的攻击分析，通常是指在未知加密算法流程和未知密钥的条件下，通过密文破译出密钥或者明文的技术手段。假设攻击者了解加密系统中的加密算法，根据Kerckhoff原则，密码分析攻击方法又可以分为下面四种：

（1）唯密文攻击。攻击者拥有一定的密文消息，而对明文一无所知。

（2）已知明文攻击。攻击者已经通过某种方式获得一些明文，并且还知道相应的密文。

（3）选择明文攻击。攻击者知道加密算法，选择相应的明文，根据加密算法得到相应明文对应的密文。

（4）选择密文攻击。攻击者知道解密算法，选择相应的密文，让解密算法解密，来获得解密后的明文。显然选择明文攻击是最具有威胁的攻击，如果一个加密算法能够抵御这种攻击，则可以抵御其他类型的攻击。文中算法的迭代和置乱过程都是与明文的像素值相关，从而使加密过程与明文自身特性密切相关。这样对于不同的明文图像就会产生完全不同的混沌序列，进而产生不同的密钥序列，攻击者无法通过选择明文攻击破解加密系统。因此，文中的算法能够有效地抵御这四种类型的攻击。

5 结束语

本文基于传统的二维cat映射和Henon映射的改进，并融合了现有像素位置置乱和像素值扩散的算法的优点，还有效解决了目前算法易受选择明文（密文）的攻击，提出了基于广义cat映射二次混合加密算法，大大增加了算法的复杂度。加密过程主要分为迭代、置乱、扩散，最后又引入了模和异或相结合的变换，使得攻击者无法轻易有效地获取混沌序列，进一步提高了加密的安全性。理论分析加实验仿真结果验证了文中算法的有效性。文中算法具有对明文和密钥极强的敏感性，抗统计分析能力强，密钥空间大，有效抵抗熵攻击，抗差分攻击能力强等特性，算法安全性高，加密效果好，具有广阔的应用前景。