基于二维细胞自动机的图像加密技术

图像作为信息密集的载体，包含着非常重要的信息，但其惊人的数据量阻碍了传统密码学对于图像信息安全的应用，而且传统的加密技术将图像作为普通数据流加密，而没有考虑多媒数据的特点。近年随着计算机处理效率的提高，图像信息的安全处理得到了进一步的发展，出现了许多关于图像加密的新算法，主要包括：图像置乱技术、图像隐藏技术和图像加密技术。

而二维细胞自动机数学原理与图像加密技术的结合更是图像加密技术的一个新的突破，为此我们提出了一种基于二维细胞自动机的图像加密算法。它具有简单易实现、安全性高、密钥量大、良好的雪崩效应以及扩散与混淆的性质，运算简单和加密速度快等优点，是一种具有发展潜力的图像加密算法。

一、细胞自动机的数学原理

1、 d维细胞自动机定义描述

细胞自动机包括以下6部分：

1）基本空间Zd，表示d维直角坐标系中具有整数坐标格点的集合，在每个格点上假设有1个细胞，通常细胞也用这个格点的直角坐标（X1，X2，...，Xd）表示。

2）状态集合Q，表示细胞状态的集合，一般取Q={0，1｝，每1个细胞都有1个状态。

3）配置空间Ⅱ。所有细胞的状态合起来称为配置，所有可能的配置构成的集合称为配置空间。配置是与时刻联系在一起的，t时刻的配置记为G，某个细胞c在t时刻的状态用Ct（ c）表示。

4）邻域B。如果某个细胞c和d维直角坐标是（X1，X2，...，Xd），那么B（c）=｛y1，y2，...，yd）：|yi-xi|≤1，1≥i≤d}就是这个细胞的邻域。易见，d维细胞自动机中1个细胞的邻域内恰好有3d个细胞。

5）局部规则f，表示作用在细胞邻域上的局部规则，它是有3d个变量的函数，变量与函数值都取值于Q。

6）整体变换pf，表示由f导出的Ⅱ的整体变换。对于时刻t的配置Ct，，pf作用在Ct上得到的时刻t+1的配置Ct+1，而在配置Ct+1里任一个细胞的状态就是，在t时刻的细胞c的邻域的作用结果，也可表示为Ct+1（c）=f（Ct（B（c））），Vc∈Zd。

2、二维细胞自动机的具体描述

因为图像是由平面坐标像素点组成，是在二维的平面上，因此以二维细胞自动机为例。

二维细胞自动机的基本空间是之，是二维直角坐标系中坐标均为整数的所有格点的集合，每个细胞都在某一格点上，也即可以用（a，b）来表示1个细胞。每个细胞只有0或1两个状态，其邻域是由（a±1，b）、（a，b±1）、（a±1，b±1）和（a，b）共9个细胞组成的集合。f可以用图示法表示，如图1所示。

如果从左上角先水平后竖值到右下角给这9个相对位置排序，那么f就可以用

表示。

注意，式中每一等式对应于图1的一个框图，如f（111111111）=ε512对应于图1最后的框图，f（111111111）的函数值为ε512，其中ε512或者为1或者为0。

为了方便，以序列ε1ε2…ε511ε512来表示f。为了减少书写序列的长度，可以考虑用128bit，16进制数来表示512bit二进制数ε1ε2…ε511ε512。如（09AB43CE）16表示由16个同样的09AB43CE合在一起组成的128bit，16进制数，它就表示一局部规则。

设t=0时刻的初始配置是C0，对任意一细胞，假设其邻域内细胞的状态如图2所示。

那么，这个细胞在t=1时的状态就是f（X1，X2，X3，X4，X5，X6，X7，X8，X9）。所有细胞在t=1时的状态都可以用这种方法得到，合在一起就是t=1时刻的配置C1。这样从t=0时的配置C0得到t=1时的配置C1可以看作是通过f的并行局部作用导出的一整体规则ρf作用在C0上的结果。将ρf再次作用在C1上，就能得到t=2时的配置C2，并依次可得到t=3、t=4……时的配置C3、C4……。

3、雪崩效应的重要作用　　

在二维细胞自动机中，对任一细胞，它在t=1时的状态取决于f对它的邻域（也二维坐标分量与其相差不过1的细胞的集合）在t=0时的状态的作用结果，而它在t=2时的状态取决于f对它的超邻域（二维坐标分量与其相差不过2的细胞的集合）在t=0时状态的作用结果。依次类推，它在t=n时的状态取决于f对二维坐标分量与其相差不过n的所有细胞在t=0时状态的作用结果。因此，在n相当大时，一般的细胞自动机都存在着明显的雪崩效应。这包括2个方面：

1）当在t=0时某个细胞的状态有所改变，将会在t=n时影响到邻近大范围细胞的状态；

2）当2个细胞自动机在初始时刻的配置完全相同，但是f存在着细微差异，那么在t=n时的配置就会有惊人的差异。这一点，也是本文作为文件加密的理论基础。

二、运用二维细胞自动机的图像加密算法描述和解释　

二维细胞自动机中，细胞是分布在Z2上的，也即在无穷大平面的格点上，而一般的图像都是有限长和有限宽的，因此为了在图像上应用二维细胞自动机，必须在技术上做一些处理。解决的一般方法是将图像看作在一拓扑环面上，即认为图像的右边界与左边界连在一起，上边界和下边界连在一起。这样，不仅图像的中间点具有9个邻域点，而且图像的边界点也有9个邻域点（包括若干对应相反边界的点）。

以黑白二值图像为例，说明如何应用二维细胞自动机对图像加密。对于W×H的黑白二值图像，把图像的每个像素点看作是1个细胞，像素点的黑白值看成细胞的状态。由于是黑白二值图像，因此可以认为黑、白分别表示该像素点所代表细胞的状态为1或0。当需要传输W×H秘密图像时，发送方和接收方先约定一共同的f和一共同的时刻t=n。注意n不应太小，否则会影响保密性。

1、运用二维细胞自动机的图像加密算法　

1）对于任一需要加密的原始图像M，先产生与其相同大小的原始随机黑白二值图像RM，作为t=0时的配置。

2）用双方约定好的f连续作用在随机图上n次，得到t=n的配置，也就是一幅新的随机黑白二值图像Cn（RM）。

3）把Cn（RM）和需加密的M进行Xor异或运算，得到密图N=Cn（RM）+M。

4）发送方传输RM|N，即发送方把原始随机黑白二值图像与黑白二值密图连在一起发送给接收方。

2、运用二维细胞自动机的图像解密算法

1）接收方分解RM|N，即接收方把接收到的图像分为原始随机黑白二值图像RM和黑白二值密图N两部分。

2）把RM当作t=0时的配置，用双方约定好的细胞自动机变换f作用RM上n次，得到t=n的配置，也就是Cn（RM）。

3）把Cn（RM）和黑白二值密图N进行异或运算，即能得到发送方原先进行加密的黑白二值图像，这是因为Cn（RM）+N=Cn（RM）+（Cn（RM）+M）=M。

这种基于细胞自动机的图像加解密算法可以适用于灰度图像。记灰度图像的灰度矩阵为（Pi×j）W×H，只要把灰度图像每个像素的灰度（Pi×j）的值（0～255间）化为长度为8的二进制Pi×j=d0i×jd1　i×j…d7i×j，将（Pi×j）W×H等价于8个二值图像（dki×j）W×H，（0≤k≤7），上述图像加解密算法就可以使用。利用这种思路，彩色图像的加解密算法可由上述算法适当推广即得。

三、运用二维细胞自动机的图像加密实验

仍以灰度图为例，需要加密的Barbara图像如3所示。

任意选取f并设定n值为9，按照上述的加密方法进行操作，可以得到加密后的密图（图4）发送给接收方。图4中，（a）是随机原始图，（b）是密图。

接受方按照上述解密方法进行操作，可以得到解密后的图像如图5示，它与原始加密图像（图3）完全相同。

四、运用二维细胞自动机的图像加密算法的优点及安全性分析

1、基于二维细胞自动机图像加密算法的优点

1）密钥量大，安全性好。当n相当大时，每一像素在t=n时的像素值严格取决于f和所有像素在t=0时的像素值，具有明显的雪崩效应。例如，在加密实验中对使用的f稍稍改动，仅把f（010010101）的值改变为1-f（010010101），再次对图3进行加密，使用同样的原始随机图，n也保持不变，得到的新的密图如图6示。

将两幅密图进行点异或运算得到图7。可见，f稍微改变一点，两图就有极大的差异，细胞自动机的雪崩效应使得密文的每一位受明文中的多位影响，随着t的增加，细胞自动机规则的进化使得密文和密钥间的统计关系也变得复杂。因此，基于二维细胞自动机的图像加密方法具有很好的扩散和混淆性质。

从细胞自动机的雪崩效应可以看出，攻击者要破译加密算法，找到局部规则f和时刻n是关键，f和n就是运用细胞自动机图像加密算法的密钥。但是由图1可以看出，f的自变量的集合共有512个元素，每一个自变量所对应的函数的不同就导致f有差异。也就是说，所用的二维细胞自动机的f共有2512个。f的选取范围可以进一步扩大。可以考虑以与某个像素点的棋盘距离不大于2的所有像素点作为该像素的邻域，这样对应到二维细胞自动机中1个细胞的邻域就包括25个细胞，f的自变量有225个，而f的总数达到233554432，这使得整个算法的密钥量更大，保密性更强，而对于加密和解密速度却没有太大的影响，使用蛮力搜索攻击将遭遇不可思议的困难。这个密钥量远大于文献[12]中提到的对于256×256图像下界为109536的密钥量，以及目前许多文献提到基于混沌的图像加密算法，如基于离散混沌系统广义同步定理的数字图像加密方案密钥量为1076，基于广义Chen’s混沌系统的图像加密算法密钥量为2149，基于混沌映射的图像加密算法密钥量为2256。

2）规则具有可复合性，抗攻击性强。发送方和接收方可以共同约定2个局部规则f和g，加密时先用f再用g循环作用在随机图上，这样即增加了破译的难度，同时也增加了密钥的数量。利用不同局部规则复合的思想，基于二维细胞自动机的图像加密算法具有更强的抗攻击性，而文献[12]所用的方法显然不具有这种性质。

3）加密效率高，运算简单。假设已有一长宽分别为l和w的二值图，按照我们的加密方法需要产生一l×w的随机二值图，然后对这个随机图进行基于二维细胞自动机规则的变换。对于随机图的每一个像素，得到它变换后对应的像素需要先寻找它周围的24个像素，然后对这25个像素寻找二维细胞自动机规则的对应局部规则，而这种寻找在细胞自动机规则放入内存后应该是O（1）时间，然后代入这个局部规则对应的数，就得到变换后的图像中这个像素所对应的数值。计算起来总共有l×w个查找和代入过程，由于迭代次数为n，此时的时间复杂性为O（n×l×w）。然后把新的变换后的随机图和原图作异或又需要l×w次异或运算。考虑到1个灰度图可以看作是8个二值图叠加而来，所以按照我们的方法，由原是l3w大小的灰度图，最后得到l×w大小的灰度密图，总共的时间复杂度为O（8×n×l×w）+O（8×l×w）=O（n×l×w）。当n给定时，时间复杂度即为O（l×w）。在任意选定一f（比如前面提到的16进制数（09AB43CE）16的表示的局部规则）和t=9，邻域值只设定为9的条件下，在CPU为Pentium（R）4CPU2.60GHz、内存为512MB机器配置下，对于128×128的灰度图，加密时间为0.06s。而文献[12]所用的方法虽然时间复杂度本质上与二维细胞自动机图像加密算法相同，但是它首先要采用S细胞自动机N技术重置图像的像素值，并且需要消耗将二维数据向一维数据转换的时间，解密后的数据还要重排，加上复杂的运算步骤因而加密速度小于基于二维细胞自动机图像加密算法。

细胞自动机是解决局部与整体联系问题的强有力的数学工具，近年细胞自动机在传统密码学中已经有了相当多的运用。由于细胞自动机模型的普遍性，细胞自动机也可以应用于图像处理，本文提出的基于二维细胞自动机的图像加密算法仅是其中一个实例。可以预期，细胞自动机在图像的安全与处理中的应用将会得到更广泛的进展。

admin普通用户

海报分享