基于超混沌系统和密文交错扩散的图像加密新算法

随着多媒体信息处理技术的广泛应用以及互联网、云计算技术的快速发展，多媒体数据日益广泛地在因特网或云计算节点间传播和存储。如何有效保护用户的秘密信息不被非法者使用，根本的措施是信息保密传输和存储。传统密码学作为一般数据加密手段却不太适合于图像数据加密，原因是图像类的信息具有数据量大、数据之间相关性高等特点。具有这种特点的数据用传统密码学加密会导致效率很低。在新的应用背景下，基于混沌的信息加密和基于混沌同步的保密通信已成为两种典型的非传统信息保密技术。混沌序列具有的内在伪随机性、非周期性和可确定的快速再生性，正与密码学所要求的特性天然相关；因此，混沌在信息加密中有着良好的应用前景，尤其在图像加密场合有许多独特优势等待开发。

但是，以往研究的混沌加密技术大多数基于低维离散混沌映射，少数基于3维连续混沌系统。虽然低维混沌系统由于形式简单而具有计算时间开销小的优点；但由于其密钥空间小，序列的复杂度不高，导致密码系统安全性不高。而高维混沌系统尤其是超混沌系统，由于具有4个以上的状态变量，因此密钥空间更大；另外，超混沌系统具有两个以上正的Lyaponuv指数，其非线性行为更复杂也更难以预测。这些特点使得超混沌系统用于图像加密无疑会提高系统的安全性。因此，随着现代计算机系统性能的不断提高，探索基于高维超混沌系统的图像加密算法将成为主流需求。较先提出了一种基于超混沌系统的典型图像加密算法，该算法由图像像素位置置乱和像素值加密两个阶段组成。但是，发现该算法存在安全缺陷，其主要原因是该算法的密钥与明文无关，导致无法抵御已知明文攻击；其次是该算法的置乱和替代加密独立，使置乱过程成为摆设。最近，提出了一种基于新型超混沌系统的图像加密算法，该算法在加密过程考虑了密钥与明文的相关性，但总体上沿用了像素位置置乱和像素值加密的基本结构。调研发现，现有研究工作中对连续时间高维混沌序列的优化改造问题关注的不多；然而，混沌密码的安全性很大程度上依赖于混沌序列的分布特性、复杂性和随机性。因此，对超混沌序列进行进一步改造无疑能提高密码的安全性。此外，如何提高超混沌图像加密算法的效率也值得研究。为了获得高安全与高效率的图像加密方案，本文提出了基于下列核心思想的超混沌图像加密算法：其一，对超混沌序列进行优化改进，提高其随机性和分布的均匀性。其二，建立密钥与明文的复杂相关性，增强密文对明文和密钥的敏感性。其三，省略像素置乱步骤，采取并行交错的加密策略，提高加密效率和算法的复杂性。

一、超混沌加密算法

1、超混沌系统模型及其序列改造

在本文的密码方案中，我们采用如下新型超混沌系统：

这里，xi=dxi/dt表示系统状态变量xi(i=1，2，3，4)随时间t的变化率。我们用x=[x1，x2，x3，x4]表示系统的状态向量。a，b，c，d，e为系统参数，当a=27.5，b=3，c=19.3，d=2.9，e=3时，系统式(1)是超混沌的；即，任意给定一组状态初值(X1O，X20，x3o，X4o)，理论上按式(1)随时间演化规律产生的4个实数序列是随机的无周期序列。但由于计算机有限精度的实现使这种序列特性有所退化。

原始的超混沌序列并不适合直接用于图像加密，其原因有二：一是实数序列的数值类型与数字图像的像素值类型不匹配；二是数字化原始超混沌序列的分布特性和伪随机特性并不很理想。基于以上原因，我们首先对原始超混沌序列进行改造，(1)使改进序列具有Golomb提出的理想伪随机序列所拥有的特性，即均匀的分布特性；自相关函数接近δ函数；互相关函数接近O。(2)使改进序列的数据类型适合于图像数据加密。

将混沌序列进行改造，生成中间混沌密钥序列的步骤如下：

(1)设由系统生成的原始混沌序列表示为{xj(i):i=1，2，…，No+l/4;j=1，2，3，4)。{xj(i)包括4个j=1，2，3，4)长度为(No+l/4)的实数序列。其中，xj(i)为待加密图像的像素点总数，No为超混沌系统的预迭代次数。

(2)为了消除混沌序列暂态过程带来的有害效应，以便增强序列对初始条件的敏感性，去掉原始混沌序列的前No个值，得到4个长度分别为l/4的子序列{xj(i):i=1，2，…，l/4;j=1，2，3，4};再按照变换式(2)对序列{xj(i)}进行改造，得到改进序列{yj(i)}。

其中max_ xj和min_ xj分别是第价序列中的最大值、最小值，j=1，2，3，4。然后由改进序列{yj(i)}经二次改造，得到4个混沌密钥子序列{zj(i)}：

其中H取z的绝对值；floor(x)取小于或等于z的最大整数；m为正整数，在本文中取m=14。

(3)将改造后的4个子序列合并成长度为己的混沌密钥序列K，合并方式如式(4)所示：

下面通过实验证明：改进后的超混沌密钥序列具有更好的伪随机性和均匀分布特性。任取一组状态变量初值(xl0，x2o，X30，X40)=(2.5，5.2，3.0，7.3)，时间步长tl=0.001，利用四阶五级Runge- Kutta法求解系统式(1)的状态方程组。以{z1(i)}和{z2(i)}两个子序列的前2000项为例，计算改造后序列。{z1(i)}和{z2(i)}的自相关系数以及两个子序列{z1(i)}和{z2(i)}之间的互相关系数。计算前将序列值归一化到[-1，1]范围：z1(i)=(z1(i)-127.5)/127.5,22(i)=(z2(i)-127.5)/127.5;得到的相关系数结果分别如图1(a)，1(b)和1(c)所示。从图1(a)和1(b)看出，前两个改进序列的自相关函数都非常接近δ函数；而从图l(c)也可以发现，前两个改进序列之间的互相关系数非常接近于0。进一步的实验表明，其余几个改进子序列具有类似的结果。图1(d)则给出了中间混沌密钥序列K的数值分布曲线，结果表明，生成的中间混沌密钥序列值分布均匀。

图2给出了改进前的X序列的对应结果。取前两个序列得到的相关系数结果分别如图2(a)，2(b)和2(c)所示。可见，原始序列的自相关函数并不是δ函数；前两个原始序列之间的互相关系数也不接近于0。进一步的实验表明，其余几个原始子序列具有类似的结果。图2(d)则给出了中间混沌密钥序列KO的数值分布曲线，KO是将原始序列按线性转换公式xxj(i)=[xj(i)-max(xj)]×255/[max(xj)-min(xj)]直接转换成[0，255]范围整数序列后，再连接起来所得到的中间密钥序列。结果表明，这样生成的中间混沌密钥序列值分布是不均匀的。

2、新的图像加密算法

本文提出的超混沌图像加密算法的主要思路是：采用超混沌系统的4个状态变量的初值作为原始密钥；首先由超混沌系统式(1)生成4个混沌实数序列；然后将混沌实数序列按上节所述方法进行优化改造，并得到性能优化的中间混沌密钥序列K。

接下来，利用中间混沌密钥序列构造与加密图像有关的最终密钥序列Key，并利用最终密钥序列Key对图像像素进行两个回合加密。在加密过程中，我们将图像划分成前后两个子块，同时对两子块进行并行加密；并引入密文交错扩散机制。

设原始图像像素大小为M行、N列，总像素数为L=MxN，其矩阵表示形式为P。

相应的加密图像矩阵用类似于式(5)的矩阵G表示，按逐行扫描顺序所得的密文像素序列为{ci，i-l，2，…，L}。明文图像的前半子块依次由像素序列{P(1)，P(2)，…，P（l／2）}组成，后半子块依次由像素序列{P(L／2+1)，P(L／2+2)，…，P(L))组成。

第1回合的加密操作由步骤1至步骤3描述。

步骤1 i→1；并对前一子块的第1个像素分别采用式(6a)与式(6b)生成最终加密密钥并进行加密操作；同时对后一子块的第1个像素分别采用式(7a)与式(7b)生成最终加密密钥并进行加密操作。

在上述公式中，bitxor(x，y)将x和y按其二进制值进行比特位异或运算；mod(x，y)求x除以y得到整数商以后的余数。CO是一个预设的正整数，CO∈[1，255]。P(i)，c(i)分别是原始图像和加密图像第i个像素的值。

步骤2 i→i+1；并对前一子块的第i个像素分别采用式(8a)与式(8b)生成最终加密密钥且进行加密操作；同时对后一子块的相应像素分别采用与式(7a)和式(7b)相同的公式生成最终加密密钥并进行加密操作。

步骤3重复步骤2，直到i=L/2，便完成了第1回合的加密操作。

第2回合加密操作由步骤4至步骤6描述。

步骤4 i→1;并对前一子块的第1个像素分别采用式(9a)与式(9b)生成最终加密密钥且进行加密操作；同时对后一子块的第1个像素分别采用式(lOa)与式(lOb)生成最终加密密钥并进行加密操作。

步骤5 i→i+1，并对前一子块的第i个像素分别采用式(lla)与式(llb)生成最终加密密钥并进行加密操作；同时对后一子块的第i个像素分别采用与式(lOa)和式(lOb)相同的公式生成加密密钥并进行相应的加密操作。

步骤6重复步骤5，直到i=L/2，便完成了第2回合的加密操作，并得到密文图像C。

从上述加密过程可见，对图像像素加密所采用的最终加密密钥Key(i)不仅与当前混沌密钥K(0)有关，而且与另一子块前一个已经加密的密文像素值有关，即引入了密文交错扩散机制。因此，经过两个回合的加密后，任何像素值的变化都将影响到其余所有像素的密文值。

设解密图像用矩阵D表示，其像素值的表示形式类似于矩阵式(5)，按逐行扫描顺序所得的解密图像像素序列为{D(i)i=1，2，…，L]，L为图像像素总数。解密过程是加密过程的逆操作；但解密的像素顺序为逆序。2个回合的解密操作共由8个步骤组成。

第1回合的解密操作由下列步骤1至步骤4描述。

步骤1 i=L/2。

步骤2对后半子块的第i个像素分别采用式(12a)和式(12b)生成解密密钥并进行解密：

对前半子块的第i个像素分别采用式(13a)和式(13b)生成解密密钥并进行解密操作：

步骤3 i→i-l，并判断新的i值：如果i>l，则执行步骤2；否则，执行步骤4。

步骤4对后半子块的第1个像素采用与式(12a)及式(12b)相同的计算公式生成密钥并进行解密操作；而对前半子块的第1个像素则分别采用式(14a)和式(14b)生成解密密钥并进行解密操作，于是完成了第1回合的解密。

第2回合的解密操作由下列步骤5至步骤8组成。

步骤5 i=L/2。

步骤6对后半子块的第i个像素分别采用式(15a)和式(15b)生成解密密钥并进行解密：

对前半子块的第i个像素则分别采用式(16a)和式(16b)生成解密密钥并进行解密：

步骤7 i→i-1，并判断新的t值：如果i>1，则执行步骤6；否则，执行步骤8。

步骤8对后半子块的第1个像素分别采用与式(15a)，式(15b)相同的公式生成解密密钥并进行解密操作；而对前半子块的第1个像素则分别采用式(17a)和式(17b)生成解密密钥并进行解密操作。

完成步骤8的操作后，就得到了最终的解密图像D。

二、实验仿真与性能分析

实验中使用256x256的8位Elaine灰度图像和其它经典测试图像，在Matlab7.1下仿真。式(1)的系统参数取：a=27.5，b=3，c=19.3，d=2.9，e=3。这样，系统式(1)是超混沌的。取系统状态初值为(2.5，5.2，3.0，7.3)；微分方程组数值求解的时间步长取0.001;其它参数为：No=1000，m=14，Co=52。

对原始Elaine图像进行2个回合的加密，加密前后的直观效果如图3所示。

1、密钥空间和执行效率分析

本文方案采用超混沌系统的4个状态变量初值作为原始密钥，用15位小数的双精度实数表示。因此，密钥空间可以达到1015 x1015 x1015 x1015 =1060≈2199，相当于199 bit的密钥长度。若将预迭代次数No和正整数CO也作为原始密钥，则密钥空间更大。故本文算法具有抗穷举攻击的能力。实验硬件环境为2.13 GHz Intel Celeron CPU，2 GB内存牙口120GB硬盘的笔记本计算机；软件环境为WindowsXP+Matlab7.1编译器。加密过程全部改用双字节整数运算，加密一幅256×256的灰度图像耗时约0.047 s；约快了17倍。效率提高的主要途径在于省去了置乱环节、采用整数运算且实行子图并行加密策略。

2、统计特性分析

(1)像素值分布特性

图4分别给出了Elaine明文图像和密文图像所对应的像素值分布直方图，由图4(a)可见，原始图像的像素值分布是不均匀的；但图4(b)表明，密文图像的像素值却呈现出平坦而均匀的分布特性，即加密图像的像素值在[o，255]范围内出现的概率几乎均等。因此，本文算法将能够有效地抵抗统计攻击。

(2)原始图像和加密图像的2维相关性

两个数据矩阵之间的2维相关系数定义为：

其中Aij，Bij分别代表明文、密文图像数据矩阵中位置（i，j）处的像素值。A，B分别代表明文、密文图像的像素平均值。采用前述初始参数，对4幅标准测试图像进行加密实验，分别得到它们的密文图像和明文图像之间的CAB值，结果如表1所示。结果表明本文算法所得的加密图像和明文图像之间具有非常小的相关性(CAB一O)。

(3)相邻像素之间的相关性分析

从图像中选取所有邻居像素对(包括水平、垂直和对角方向的3类邻居对），用式(19)分别对每一类相邻像素之间的相关系数进行计算：

其中xi和yi分别表示图像中第i组邻居像素的两个像素值；x，y分别为像素值xi与Yi的平均值；M为邻居像素对的组数；r即为相邻像素的相关系数。取与前所述相同的初始参数对Lena图像进行加密，计算加密前后图像3种方向的r系数，所得结果如表2第2，第3列所示。尽管明文Lena图像的相邻像素存在高度相关性(r+1)；但对应密文图像的相邻素已几乎不相关(7-0)。表2同时也给出了同样基于超混沌的图像加密算法的相应结果。对比已有算法，本文算法所得的密文图像的r系数比密文图像的所有r系数更低，表明本文算法对于打破相邻像素之间的相关性取得的效果更好。

3、抗差分攻击能力分析

对明文的敏感性越强，算法抵抗差分攻击的能力也就越强。可以用像素数改变率NPCR (Numberof Pixels Change Rate)指标度量加密算法对明文的敏感性；也可以用归一化像素值平均改变强度UACI (Unified Average Changing Intensity)指标度量敏感性。当两个明文图像仅存在一个像素不同时，设它们的密文图像中第（i，j）点的像素值分别为C1（i，j）和C2(i，j)。若C1（i，j）=C2（i，j），定义D(i，j)=0；若C1(i，J)≠C2(i，J)，定义D(i，J)=1。则NPCR与UACI的计算公式分别为:

NPCR与UACI的理想期望值可以用下列公式计算：

其中M和N分别是图像像素的行数与列数，佗为图像颜色位深。对于8位灰度图像（n=8），NPCR与UACI的理想期望值分别为NPCRE=99.6094070与UACIE=33.4635070。本文实验中，先后选取了100组Lena图像进行加密，每组2个图像，一个为原始图像，另一个则是对原始图像随机选择一个像素并使该像素的值改变1（将最低比特位取反），所得100组密文图像之间的NPCR与UACI值结果如图5(a)和5(b)所示。图5(c)和5(d)同时给出了算法加密结果。实验所得本文算法的NPCR与UACI值都分布在理想值（图中水平线）附近；并得到NPCR与UACI的平均值分别为NPCR =99.6057~0和UACI=33.40497%，都非常接近相应的理想值。而算法的NPCR与UACI的平均值分别为NPR =46.1099V0和UACI=0.1808%。可见，本文算法对明文的敏感性远远超过算法对明文的敏感性。原因是算法只在一轮像素替代操作过程中产生密文扩散效应，因此任何一个位置点的明文发生变化，仅仅只影响该点后面的密文发生变化。而本文算法设计了两轮替代操作，并进行交叉扩散，因此任何位置点的明文像素值发生变化，都将影响几乎所有点的密文发生变化。本文对图像加密2轮获得的丽趸瓦值高于]对图像加密4轮所得的平均值99.5933533~0，接近该文对图像加密5轮所得的平均值99.6273041%；本文对图像加密2轮获得的UACI值高于加密3轮所得的平均值33.3999634%，接近该文加密5轮所得的平均值33.4815979%。

4、对密钥敏感性的测试

一个好的加密算法应该对密钥具有强烈的敏感性，即密钥的微小变化，将导致密文截然不同。本文实验中先以(X1O，x2o，x3o，X40)=(2.5，5.2，3.0，7.3)为加密密钥，对Cameraman图像进行加密；然后用稍微不同的密钥对加密图像进行解密（解密密钥每次仅使其中1个初始变量改变10-10），图6分别给出了正确密钥和XIO错误密钥的解密Cameraman图像。

可见，密钥的微小差异导致不能正确解密。为了度量解密图像和原始图像的差别，引入均方误差MSE指标，设原始图像及其解密图像分别表示为P={p（i，j）和D={D（i，j）），i=l，2，…，M,j=-1，2，…，N。则图像D与P之间的均方误差计算公式为:

对Cameraman图像，表3第1行给出了本文算法正确密钥及4组错误密钥所得解密图像分别与原始图像之间的均方误差值，结果表明，正确密钥可以实现完全精确解密；而具有微小错误的解密密钥所解密的图像将与原始图像相差巨大。这体现了算法对密钥的敏感性。表3笫2行给出算法所得解密图像分别与原始图像之间的均方误差值。比较而言，本文算法对初始密钥X10和x2o更敏感；而算法对初始密钥X30和X40更敏感。这是由于两个超混沌系统的特性差异决定的。

5、信息熵分析

信息熵是反映信息的随机性的重要度量指标。设s代表一种信息源，则s的信息熵H(s)可以用式(25)进行计算：

其中P(si)表示符号si出现的概率，2n是信息源s的总状态数。对一个能发出2n个符号的真随机信源，其信息熵就是佗。以一幅256级灰度图像作为信息源为例，其像素值有28种可能值，因此一幅256级灰度图像的理想信息熵应该是8。如果一幅256级灰度图像的加密图像具有接近8的信息熵，则表明该密文图像接近随机分布。我们对标准Lena图像用本文算法加密，得到其密文图像信息熵为7.9976，非常接近理想值8。

6、混沌序列改进前后的加密性能对比

下面通过实验测试，对比本文改进混沌序列相对于原始混沌序列所得加密图像的性能差异。我们分别用图l的K序列与图2的KO序列得到中间混沌密钥，然后用本文相同的加密方法加密同样的Lena图像，对两种加密图像的主要统计指标（2维相关性CAB，相邻像素的相关系数r及信息熵）进行计算，结果如表4所示。结果表明，用改进序列生成的密钥加密图像具有更小的相关系数但更大的信息熵，因此，得到的加密图像将具有更好的安全性。