一种基于猫映射和伯努利移位映射的图像加密算法

郭伟创，叶瑞松

(汕头大学数学系，广东汕头515063)

一种基于猫映射和伯努利移位映射的图像加密算法

郭伟创，叶瑞松

(汕头大学数学系，广东汕头515063)

本文提出了一种基于混沌映射的图像加密算法，采用置乱-扩散的机制对图像进行加密.在置乱阶段，先将大小为M×N的8比特灰度图像拉伸为大小M×2N的4比特灰度图像，然后将4比特灰度图像中k×k的小块作为一个单元，利用混沌伪随机序列进行置乱.为了达到更好的加密效果，笔者对置乱后的图像进行了两轮扩散.对该加密算法进行了安全性能分析，包括直方图分析，相邻像素相关性分析，信息熵分析，密钥敏感性分析，密钥空间分析以及差分攻击分析等.数值实验表明该算法是一种有效的图像加密算法，在图像信息安全方面具有一定的应用价值.

混沌；猫映射；伯努利移位映射；图像加密；置乱；扩散

0 引言

随着数字图像在商业、军事等需要安全保密的领域的应用普及，数字图像的安全性研究得到了广泛的关注.一般采用传统的加密方法（如AES、DES等[1]）对文本信息进行加密，以保证文本信息的安全.由于数字图像本身具有数据量大、数据二维空间分布、能量不均匀分布、原始图像数据存在大量冗余等特点，使得传统的加密方法对图像不再适应.随着混沌密码学的发展，混沌映射在设计图像加密算法中发挥了巨大的作用，展现了巨大的潜力[2-9].其根本原因在于混沌映射所固有的混合性质，对参数和初值的敏感性，迭代生成的序列的伪随机性、遍历性等基本特性与密码学的置换和扩散的基本要求有惊人的相似之处.置乱和扩散是指导密码设计的两个原则[10].

“混沌密码”是1989年A.Robert和J.Mattews在文献[11]中明确提出的，并给出了一种基于变形logistic映射的混沌序列密码方案.该文发表后，掀起了关于混沌密码研究的热潮，较好的思路有基于猫映射、面包师映射和标准映射的图像加密算法[5-6，9，12].但在已有的加密方法中有些也是不安全的，密码破译者已发现了相关加密系统的缺陷[13-18].因此图像信息安全领域的研究者陆续对已有的算法作出改进，提出了更优的加密方法.文献[19]提出一种变控制参数的混沌图像加密算法.文献[20]中利用了混沌映射的逆映射，且将置乱和扩散两个阶段合为一个阶段.文献[21]中选取图像子块为操作的对象，以提高加密的效果.文献[22]提出了一种基于混沌的并行图像加密算法.文献[23]将二维猫映射扩展到三维.文献[24]提出了一种将加密和Hash结合在一起的方法.文献[25]提出了一种基于多极点斜帐篷映射加密算法.

本文提出了一种基于二维猫映射和伯努利移位映射的图像加密算法.由于图像各个位平面所占图像信息的比重差别很大，论文首先将大小为M×N的8比特灰度图像的每个像素的高4位比特和低4位比特的信息拆开，组成一个大小M×2N的4比特（即16个灰度级）的灰度图像.将该图像分成大小为k×k的子块，总共有N′=M×2N/k2的图像子块.利用二维猫映射，产生长度为N′的混沌伪随机序列，对分块后的图像进行置乱.置乱采用子块整体搬动的形式实现，节约了计算量，提高加密效率.经过置乱之后的图像重新恢复为8比特灰度图像，用伯努利移位映射产生伪随机灰度值序列，对图像做两轮的扩散操作，很好地实现了加密效果.在加密算法中，置乱过程所产生的伪随机序列不仅对混沌映射的参数和初值高度敏感，而且还与明文相关.因此该加密算法能抵抗统计攻击、差分攻击、已知明文和选择明文攻击，同时还具有较大的密钥空间能抵抗暴力攻击.

1 加密算法

1.1 置乱阶段

在这一阶段，我们利用二维混沌猫映射产生混沌序列，然后用于置乱图像，置乱的步骤如下.

Step 1.首先读取一张大小为M×N的256-灰度级平面图像，然后将它扩展为大小为M×2N的16-灰度级新平面图像.扩展策略如下：将平面图像分成两部分，把图像的高4位作为一部分，低4位作为另一部分.因此每个8-比特的像素都被分成两部分，如图1所示.

（1）我们将图像的高4位重新组合成一个像素集，那么新像素集的大小为4-比特.但它是由原图像的高8、7、6、5位所组成，故每个新像素占有原图的像素信息量.因为原图的大小为M×N，故将原图的高4位组成的部分Ⅰ大小也为M×N.

（2）如图1第Ⅱ部分所示，将图像的低4位组成新的像素集，这里每个新像素占有原图5.875%的像素信息量.

最后，我们将两部分组成一个大小为M×2N的16灰度级的新平面图像I3.

图1 8比特图像扩展为4比特图像

Step 2.为了提高加密效率，我们采用像素块与像素块置换代替一般所采用的单像素与单像素置换的方法.由Step 1，我们得到大小为M×2N的平面图像I3，选定一个整数k（本文k=4），一般选取k可以整除M×2N.如果没办法整除，对图像稍作拓展，使其边长可以被k整除.那么图像I3被分成N′=M×2N/k2个大小为k×k的小块，这里将每一小块视为一个单元，则得到一个由个大小为k×k的子图像构成的4比特灰度图像I4.然后，我们再利用二维混沌猫映射产生长度为N′的混沌序列来置乱I4.

Step 3.由初始点（x0，y0），我们迭代猫映射N1次得到点（xN1，yN1），将（xN1，yN1）记为（x，y），其中N1={I3（1，1）+I3（1，2）+…+I3（1，2N）+I3（2，1）+…+I3（M，2N）}mod 256.

Step 4.采用下面的遍历算法对图像I3中总共M×2N/k2个大小为k×k的子图像块实现置乱操作（matlab代码）：

这里分块矩阵S表示置乱后的图像，S（i，j）是代表分块矩阵S的第i行、第j列的k×k子块，因此S的大小和I3一样；标记矩阵index大小为，初始值为零矩阵，当index（i，j）元素值改变为1时，表示相应I4（i，j）的子块已经被遍历；pq1=p×q+1.在这一阶段猫映射所选用的参数及初始条件分别为（p，q）=（16，26），（x0，y0）=（0.5678，0.123 4）.

通过上述对分块矩阵的遍历置乱，可以达到改变像素位置和灰度值的效果.分块使得遍历算法的计算量大大减少，提高加密效率.

1.2 扩散阶段

为了提高算法抗统计攻击和抗差分攻击的能力，我们对置乱后的图像进行了两轮扩散.经过这一扩散阶段，密图的直方图与原图完全不一样，且分布非常均匀.扩散过程如下所述.

Step 1.经过置乱阶段，我们得到了一个大小为M×2N的置乱图像S.在这一步，我们要将图像通过扩展过程的逆过程将S压缩成大小为M×N的图像D.S中落在部分Ⅰ的像素，将其当做图像D相同位置像素的高4位，S中落在部分Ⅱ的像素，将其当做图像D相同位置像素的低4位.这样大小为M×2N的16个灰度级的图像将变成大小为M×N的256个灰度级的图像.压缩过程如图2所示.

图2 压缩图像

Step 2.读取图像D的灰度值矩阵DM×N，记L＝M×N；然后将二维矩阵DM×N变换为1×L的向量V1.第一轮扩散方法如下：

t（i）=floor（x（i）*256），

c1（i）=V1（i）⊕[c1（i-1）+t（i））mod 256]，

其中c1（i）、c1（i-1）分别是我们在当步加密后的图像c1的第i个和第i-1个像素值.V1（i）是向量V1的第i个元素，t（i）是临时变量，初始条件c1（0）=139.

这里我们利用伯努利移位映射如下式，产生混沌序列x（t）：

x（i+1）=（x（i）/c）mod1，

初始值x（0）=0.478 912 345 6，参数c=0.367 8.

Step 3.由上一步，我们得到1×L的向量c1，接着进行第二轮扩散，方法如下：

t（i）=floor（y（i）*256），

c2（i）=C1（i）⊕[c2（i-1）+t（i）mod 256]，

其中c2（i）、c2（i-1）分别是密图c2的第i个和第i-1个像素值.c1（i）是向量c1的第i个元素，t（i）是临时变量，初始条件c2（0）=c1（L）.这里我们利用伯努利移位映射如下式，产生混沌序列y（i）：

y（i+1）=（y（i）/c）mod1，

初始值y（0）=0.123 445 678 9，参数c=0.367 8.

完整的加密算法包括了置乱阶段和扩散阶段，我们选用大小为512×512的Lena图像进行仿真实验，实验结果如图3所示.

图3 加密结果

2 算法的安全性分析

在这里我们对算法的安全性进行分析，包括直方图、相关性系数、信息熵、密钥敏感性分析，密钥空间分析，差分分析，抗已知明文和选择明文攻击分析.同时我们还与其它3种加密算法作比较.这三种算法分别是在文献[26]中所提出的：Traditional Chaosbased Image Encryption Architecture（TCIEA）、Lightweight Bit-level Confusion and Cascade Cross Circular Diffusion Encryption Scheme（LBCCC）和A Chaos-based Pseudorandom Permutation and Bilateral Diffusion Scheme for Image Encryption（PBD）.以上所有的这些分析表明该图像加密算法具有较高的安全性.

2.1 直方图分析

直方图反映的是一个图像的像素值的分布情况.图3中（c）、（d）是原始图像和密文图像的像素值分布情况，由图（3）中（c）、（d）可以看出，原始图像的直方图和密文图像的直方图有着明显的区别.可见，在加密过程已将原始图像像素值的不均匀分布变成了均匀分布，有效地降低了明文和密文的相关性，隐藏了图像的统计特性，说明统计攻击无效.

2.2 相关性分析

一般情况下，原始图像相邻（水平、垂直、对角）像素之间具有很强的相关性.通过加密图像可以破坏图像像素之间的相关性，使得密图相邻像素之间的相关性变小，增强了密图的安全性.为检验图像相邻像素的相关性，我们随机选取6 000对图像相邻的水平、垂直、对角3个方向的灰度值，然后根据如下公式计算相关性系数：

其中X＝（x1，…，xT），Y＝（y1，…，yT）是2对相邻像素的灰度值，T是总的对数.

这里，我们采用Lena图、Couple图和NBA图进行测试，分别得到它们的密文图像和明文图像之间的相关性值，如表1所示.

表1 原图与密图的相关系数分析

图4是从Lena图及其相应的加密图像（本文算法）随机选取6 000组邻点（水平、垂直、对角）作出的像素相关图.

图4 原图与加密图相邻像素相关性比较

2.3 差分攻击分析

密文对明文的敏感性越好，算法抵抗差分攻击的性能也就越好，而攻击者通常是对明文进行微小调整（改变原图一个像素的大小），然后再通过比较原明文的密文和微小调整后明文的密文之间的差别来进行攻击.对于图像加密的差分攻击，一般用NPCR和UACI这两个指标来进行评测.NPCR，即像素变化比率，是指当原图一个像素改变时加密图像数目改变率，改变率越大表明算法对原图越敏感，越能抵抗明文攻击.UACI，即统一平均变化程度，是指原图和加密图的相应像素平均强度的变化率，变化率越大，表明加密图与原图比平均强度越大，加密算法越好，越能抵抗差分攻击.

NPCR与UACI计算公式如下：

式中C1和C2为两个密文图像，它们所对应的明文图像只有一个像素点的差别，M、N为C1和C2的宽和高.

我们随机选取lena图的10像素点做仿真实验，并分析得到NPCR和UACI的值，其值情况如表2所示，可以看出加密效果很好，能够抵抗差分攻击.

表2 lena图的NPCR和UACI测试结果

2.4 信息熵分析

信息熵是衡量随机性和密码系统安全性的一个重要准则.设m代表一幅随机的灰度图像，则m的信息熵可以用下式进行计算：

其中，p（mi）表示像素值mi出现的概率，2n是原始图像m所有像素的灰度等级数.对一个能发出2n个符号的真随机信源，其信息熵就是n.一幅256级灰度图像的理想信息熵是8，若一幅256级灰度图像的加密图像的信息熵接近8，则该密文图像的像素值接近随机分布.在此，我们分别计算Lena图、Couple图和NBA图以及它们相应的加密图像的信息熵，其值情况如表3所示，由此表表明本文算法具有较好的加密效果.

表3 lena图、Couple图、NBA图及相应密图的信息熵

2.5 密钥分析

一个好的加密算法应该对密钥敏感，密钥空间应该足够大以抵抗穷举攻击.在整个加密过程，我们采用参数x0，y0，p，q，x（0），c，c1（0），y（0）作为密钥，并对密钥的敏感性进行分析.

密钥参数k的敏感性测试如下所述.首先选用图像I=（I（i，j））M′N作为加密对象（比如lena图像），然后依次分别采用密钥k，k-Dd，k+Dd，在不改变其它密钥参数的情况下，对图像I进行加密，得到相应的加密图像I1，I2，I3，那么我们定义参数k的敏感系数ps（k）计算公式如下：

图5 密钥对加密图像的敏感性影响

图6 密钥对解密的敏感性影响

表4 密钥的敏感性测试结果

2.6 抗御已知明文和选择明文攻击分析

在置乱阶段，我们计算N1的大小，然后迭代混沌猫映射N1次得到（x，y），再由（x，y）产生置乱图像所需的混沌序列.因为N1的大小由所有的数值I3（i，j），1≤i≤M，1≤j≤2N所决定，那么（x，y）与平面图像的像素相关，由此产生用于置换的混沌伪随机序列，同样也依赖于平面图像.当加密不同的平面图像时，相应的混沌序列应用于置换平面图像也会有所不同，故攻击者无法通过加密一些特殊图像而获得一些破解算法的有效信息，所以该加密算法可以抵抗已知明文和选择明文攻击.

3 结论

本文提出了一种基于猫映射和伯努利移位映射的图像加密算法，该算法在置乱阶段不仅很好的打乱了图像的像素位置排列，而且还改变了图像的像素值，并且在扩散阶段，有效地改变了图像的所有像素值.另外，本文还进行了统计分析，密钥敏感性分析和密钥空间分析等，结论表明这个算法是有效的，具有较高的安全性，在图像和信息安全方面具有应用价值.

参考文献:

[1]Stinson D R.Cryptography：theory and practice[M].Boca Raton：CRC Press，1995.

[2]Kocarev L.Chaos-based cryptography，a brief overview[J].IEEE Circuits and Systems Magazine，2001，1（3）：6-21.

[3]Pareek N K，Patidar V，Sud K K.Image encryption using chaotic logistic map[J].Image and Vision Computing，2006，24（9），926-934.

[4]Wong K W，Kwok B S H，Law W S.A fast image encryption scheme based on chaotic standard map[J].Physics Letters A，2008，372（15）：2645-2652.

[5]Patidar V，Pareek N K，Purohit G，et al.A robust and secure chaotic standard map based pseudorandom permutation substitution scheme for image encryption[J].Optics Communications，2011，284（19）：4331-4339.

[6]Guo S G，Sun J S，Wang Z Q.A block cipher based on suitable use of the chaotic standard map [J].Chaos Solitons Fractals，2005，26（1）：117-129.

[7]刘树堂，孙福艳，基于空间混沌的图像加密设计[J].中国科学G辑：物理学力学天文学，2009，39（3）：387-393.

[8]马在光，丘水生.基于广义猫映射的一种图像加密系统[J].通信学报，2003，24（2）：51-57.

[9]Ye R.A novel chaos-based image encryption scheme with an efficient permutation-diffusion mechanism[J].Optics Communication，2011，284（22）：5290-5298.

[10]Shannon C E.Communication theory of secrecy system[J].Bell System Technical Journal，1949，28（4）：656-715.

[11]Matthews R.On the derivation of a chaotic encryption algorithm[J].Cryptologia，1989，13（1）：29-42.

[12]Chen G R，Mao Y B，Chui C K.A symmetric image encryption scheme based on 3D chaotic cat maps[J].Chaos，Solitons&Fractals，2004，21（3）：749-761.

[13]Li S J，Li C Q，Chen G R，et al.A general quantitative cryptanalysis of permutation-only multimedia ciphers against plain-image attacks[J].Signal Process Image Commun，2009，23（3）：212-223.

[14]Cokal C，Solak E.Cryptanalysis of a chaos-based image encryption algorithm[J].Physics Letters A，2009，373（15）：1357-1360.

[15]Xiao D，Liao X F，Wei P C.Analysis and improvement of a chaos-based image encryption algorithm[J].Chaos，Solitons&Fractals，2009，40（5）：2191-2199.

[16]Liu J M，Qu Q.Cryptanalysis of a substitution-diffusion based on cipher using chaotic standard and logistic map[C].2010 Third International Symposium on Information Processing.2010：67-69.

[17]Rhouma R，Solak E，Belghith S.Cryptanalysis of a new substitution-diffusion based image cipher [J].Commun.Nonlinear Sci Numer Simula，2010，15（7）：1887-1892.

[18]Wang X Y，He G X.Cryptanalysis on a novel image encryption method based on total shuffling scheme[J].Optics Communications，2011，284（24）：5804-5807.

[19]Wang Y，Wong K W，Liao X F，et al.A chaos-based image encryption algorithm with variable control parameters[J].Chaos，Solitons&Fractals，2009，41（4）：1773-1783.

[20]Zhang W，Wong K W，Yu H，et al.An image encryption scheme using reverse 2-dimensional c haotic map and dependent diffusion[J].Commun Nonlinear Sci Numer Simulat，2013，18（8）：2066-2080.

[21]Zhang Y S，Di X.An image encryption scheme based on rotation matrix bit-level permutation andblock diffusion[J].Commun Nonlinear Sci Numer Simulat，2014，19（1）：74-82.

[22]Zhou Q，Wong K W，Liao X F，et al.Parallel image encryption algorithm based on discretized chaotic map[J].Chaos，Solitons&Fractals，2008，38（4）：1081-1092.

[23]Kanso A.Ghebleh M.A novel image encryption algorithm based on a 3D chaotic map[J]. Commun Nonlinear Sci Numer Simulat，2012，17（7）：2943-2959.

[24]Wong K W.A combined chaotic cryptographic and hashing scheme[J].Physics Letters A，2003，307（5/6）292-298.

[25]Ye R S，Guo W C.A chaos-based image encryption scheme using multi modal skew tent maps [J].Journal of Emerging Trends in Computing and Information Sciences，2013，4（10）：800-810.

[26]Guo W C，Zhao J Q，Ye R S.A chaos-based pseudorandom permutation and bilateral diffusion scheme for image encryption[J].international Journal of Image，Graphics and Signal Processing（IJIGSP），2014，6（11）：50-61.

An Image Encryption Scheme Based on Cat M ap and Bernoulli Shift M ap

GUO Weichuang，YE Ruisong
（Department of Mathematics，Shantou University，Shantou 515063，Guangdong，China）

A chaos-based image encryption scheme with permutation-diffusion architecture is proposed.In the permutation process，the 8-bit gray scale image with size is expanded to a 4-bit gray scale one with size by dividing the plain-image into two parts：one consisting of the higher 4 bits and one consisting of the lower 4 bits.The resulted 4-bit gray scale image is then set to be blocks with size and shuffle the image at block level.To achieve more avalanche effect and larger key space，a chaotic Bernoulli shift map based bilateral diffusion function is applied as well.The security and performance of the proposed image encryption have been analyzed，including histograms，correlation coefficients，information entropy，key sensitivity analysis，key space analysis，differential analysis，encryption rate analysis，etc.All the experimental results suggest that the proposed image encryption scheme is robust and secure.

chaos；chat map；Bernoulli shift map；image encryption；shuffling；diffusion

TP 391

A

1001-4217（2015）01-0013-11

2014-10-09

叶瑞松（1968-），男，福建诏安县人，博士.教授.研究方向：分形混沌及其应用，信息安全．E-mail：rsye@stu.edu.cn