杨璐　邵利平　郭文锋

摘  要： 已有的图像加密算法，均是对整个图像同等加密，而对于感兴趣关键区域重点加密的算法还比较少见。本文章提出一种基于迷宫和时空混沌的选择性区域图像加密算法。利用mean-shift算法将图像分割为感兴趣关键区域和弱信息量的背景区域，并提取关键区域轮廓作为部分密钥保存;发挥迷宫可对不规则区域进行置换的优势，对关键区域进行像素位置置换;为保护关键区域的轮廓，对整个图像进一步进行像素值混淆加密;将原始图像信息与感兴趣关键区域轮廓信息与用户给定密钥结合共同启动加密过程，使加密过程与明文图像紧密相关，抵抗已知/选择明文攻击。

关键词： 图像加密; 选择性区域; 迷宫置换; 时空混沌映射; 已知/选择明文攻击

中图分类号：TP309.7          文献标识码：A     文章编号：1006-8228（2022）03-45-05

Abstract： The existing image encryption algorithms all encrypt the entire image equally， the encryption algorithm for key areas of interest is still relatively rare. This paper proposes a selective region image encryption algorithm based on maze and chaotic map. The algorithm uses the mean-shift algorithm to segment the image into the key area of interest and the background area with weak information; extracts the contour of the key area as part of the key to save; taking the advantage of the maze to permute the irregular area， replaces pixel position for key areas; to protect the contours of key areas， the entire image is further encrypted by pixel value confusion; the original image information and the contour information of the key area of interest are combined to the user's given key to start the encryption process， so that the encryption process is closely related to the plaintext image， to resist chosen/known plaintext attack.

Key words： image encryption; selective region; maze permutation; spatiotemporal chaos mapping; chosen/known plaintext attack

0 引言

當前的图像加密算法大部分基于混沌系统，采用像素位置置换-像素值混淆的结构，对整个图像进行同等加密。例如文献[1]提出了一种复合一维Sine和Tent混沌映射的二维超混沌系统，按行优先顺序对图像加密;文献[2]针对Logistic 映射存在系统参数范围受到限制、混沌序列的分布不均匀等问题提出一种改进的 Logistic 映射，置乱-扩散同时操作对图像进行加密;文献[3]生成一种混沌时间序列对图像像素进行置乱和混淆;文献[4]针对单一混沌系统加密不足的问题，提出一种基于改进的LCL复合混沌系统和DFT变换的图像加密算法;文献[5]提出了一种基于 2-D Logistic调制 Sine 映射的图像混沌加密算法。以上文献算法均构造不同类型混沌系统来生成伪随机数列对图像采用置乱-混淆架构加密，但是加密环节与明文信息无关，因此不能抵抗已知选择明文攻击。针对此问题，许多文献相继展开了分析研究，例如，文献[6]指出文献[5]所提出的图像混沌加密算法中的混沌密钥流与明文图像无关，存在安全漏洞，分析者可以在未知加密密钥情况下，通过选择明文攻击破译出原始明文图像。文献[7]提出一种新型的基于DFS迷宫生成算法的混沌加密算法，通过将用户给定密钥与原始明文图像的MD5值绑定驱动加密过程，加密环节与明文信息紧密相关。

本文在文献[7]的基础上，采用改进的BFS迷宫进行置换，避免了文献[7]中DFS迷宫的回溯过程，提高了置换效率，且置换区域可以是任意不规则区域，进一步了发挥迷宫生成算法在像素位置置换方面的优势，对图像中关键不规则区域进行重点保护加密。

本文将在第1小节给出改进的基于BFS迷宫和伪随机数的置换生成算法;在第2小节给出与明文相关的迷宫置换和混淆策略;在第3小节给出完整的加密算法;在第4小节实验验证给出加密算法的加密效果及安全性;最后1小节总结全文研究工作。

1 改进的基于BFS迷宫和伪随机数列的像素位置置换算法

传统的图像加密算法，对图像的像素位置置换一般局限于对标准的矩形区域做置换，不能满足对不规则的关键区域进行位置置换加密的需求，本文采用BFS迷宫生成算法可以对不规则的图像关键区域像素位置进行置换加密。在任意不规则关键信息区域内从任意像素节点出发，随机产生1条遍历该区域所有像素节点的迷宫生成路线。基于BFS的迷宫生成算法（记作算法1）采用队列实现，具体描述为以下步骤。

● 算法1

第1步：在任意不规则区域的像素网格中，指定任意有效网格节点（x， y），即x和y都在要进行迷宫置换的不规则区域内，设由mean-shift图像分割算法得到的标记感兴趣不规则区域与背景区域的二值矩阵为S，其中背景区域像素值均为255（白色），感兴趣区域像素值均为0（黑色）。则需满足x∈[0，M-1]， y∈[0， N-1]且S[x][y]=0，作为迷宫置换的起点坐标，将该节点插到队列的队尾，并标记已访问。

第2步：如果当前像素节点（x，y）在不规则关键区域内的相邻像素节点集（x-1，y）（左）、（x，y+1）（上）、（x+1，y）（右）、（x，y-1）（下）中存在未被访问的有效像素节点，则将这些有效像素节点按随机的顺序依次插入到队列的队尾，并且标记其为已访问像素节点。最后将当前节点从队列的队头移除。

第3步：如果当前节点在关键区域内的相邻节点集中不存在未访问的有效节点，则将队首节点直接移除，将新的队首节点作为当前节点（x，y）。

第4步：反复执行第2-第3步，直到不规则关键区域内的所有节点均被标记已访问。

算法1中，第1步随机选定的起点坐标可作为BFS迷宫的生成密钥，第2步中相邻节点进入队列的顺序的随机性可由特定的密钥驱动混沌映射来随机确定，从而给定密钥，就可惟一地确定一条迷宫生成路径。

以给定节点作为迷宫的起点坐标，按算法1就可以按照迷宫的随机生成路径的顺序依次标注不规则关键区域内的所有像素节点，以此随机路径顺序构造迷宫置换。为了避免文献[7]中DFS迷宫置换的局部效应，对传统BFS迷宫算法置换进行改进，给出改进基于迷宫的像素位置置换算法（记作算法2）如下。

● 算法2

第1步：在图像不规则关键区域，从指定的起始像素节点开始，按照算法1中生成迷宫的访问先后顺序赋予访问的顺序编号排列，记作像素访问顺序数组Sorder。

第2步：将关键不规则区域内像素节点数量記为Number，由指定伪随机数种子驱动混沌映射方程产生1-Number之间的伪随机数序列，并且保证[1， Number]区间内每个数只出现一次，从而实现像素值的一一对应。将此序列记为Smap。

第3步：将第1步中的按BFS迷宫算法生成的像素访问顺序数组Sorder，按照序列Smap中的伪随机数一一对应排列，然后将其按照行优先的顺序填充到不规则关键区域，从而生成置换后的矩阵（反向映射即为逆变换）。

图1是对算法2的置换加密效果进行实验仿真测试，测试图像如图1a（避免涉及侵权，采用本人寸照）所示，分辨率为160×228的彩色图像photo。对其RGB矩阵分别采用改进的基于BFS迷宫和伪随机数算法置换，效果如图1（b）所示。

可看出，相比文献[7]，改进后的迷宫置换算法，只需1次置换就可以实现均匀的置换加密效果。

2 与明文相关的迷宫置换和混淆策略

为抵抗已知/选择明文攻击，本文设计加密算法加密过程中的每个环节不仅与用户给定密钥相关，也与待加密图像RGB矩阵的SHA-1值密切相关，并且与感兴趣的关键区域轮廓相关，使得关键区域轮廓链码的任意微小改动都解密不出原图，进一步增强了关键区域图像信息的安全性。

假设原始待加密图像为A，分辨率：M×N，其分别计算出各自对应的160位的SHA-1值，记为（AR）sha-1、（AG）sha-1和（AB）sha-1。

采用mean-shift图像分割算法将原始图像A分割成感兴趣关键区域与弱信息量背景区域，然后采用轮廓跟踪算法提取感兴趣关键区域的轮廓链码，并将其采用游程压缩编码算法进行压缩，记作CC（即chaincode），计算其对应的SHA-1值，记作（CC）sha-1。并采用式⑴与（AR）sha-1、（AG）sha-1和（AB）sha-1与（CC）sha-1分别异或得到（CAR）sha-1、（CAG）sha-1和（CAB）sha-1：

按式⑷，可得到60个字节。由用户给定密钥驱动产生[0，59]范围内随机数，将式⑷描述的[di]序列打乱，得到新字节序列[ei]，再按式⑸、式⑹生成迷宫置换的起点坐标：

在式⑸和式⑹中，a、b为用户给定的密钥，（Xr， Yr）、（Xg ，Yg）、（Xb ，Yb）是在原始待加密图像RGB矩阵上进行迷宫置换的起点坐标。其中的[sinei cosei]中的i为0-59的随机数，每一次使用均由系统随机数产生，从而增强迷宫置换起点坐标随机变化的复杂性。由式⑴-⑹，迷宫起点坐标与待加密图像信息、感兴趣关键区域轮廓以及用户给定的密钥紧密相关。

本文加密算法中置换环节的随机性强，还体现在在任何一个当前选定结点上的试探方向也是随机的。首先采用Logistic混沌映射，生成OCML时空混沌映射的初始矩阵序列，再结合本文设计密钥驱动OCML映射产生伪随机数序列，随机决定当前选定结点上的试探方向。用于产生OCML初始矩阵序列的Logistic混沌映射的定义如下：

OCML是一种经典的二维时空混沌映射，广泛应用在图像加密算法中。其数学模型如式⑻：

式⑻中t为时间坐标，i为空间坐标;[ε]为耦合系数且处于（0，1）之间，[f]为局部更新函数，这里采用式⑺的Logistic混沌映射。

用于产生时空混沌映射初始矩阵序列的Logistic混沌映射的初始值[x0]和[μ]，以及OCML模型中的耦合系数[ε]、其中更新函数的参数[μ1]，按照式⑼～式⑿产生。

采用式⑼～⑿生成Logistic映射的初始值、参数以及二维时空混沌映射中的更新函数的参数和耦合系数，可将用户给定密钥与待加密图像信息、关键不规则区域链码信息绑定，共同驱动OCML二维时空混沌映射产生伪随机数序列参与置换-混淆加密，有效抵抗已知/选择明文攻击。

将Logistic映射构成伪随机数数列[xi，i∈0，3×MN-1]，作为图像R、G、B矩阵OCML混沌映射的初始矩阵序列，其中[xii∈0，MN-1]用于R矩阵，[xi，i∈MN，2MN-1]用于G矩阵，[xi，i∈2MN，3MN-1]用于B矩阵。用来驱动OCML混沌映射，这里OCML时空混沌映射的迭代轮数作为密钥记为L，即迭代L轮产生伪随机数列[vri，vgi，vbii∈0，MN-1]，按照式⒀量化到[0，255]之间得到[kri、kgi、kbi]：

[kri、kgi、kbi]分别用于RGB矩阵，既可作为随机数种子产生迷宫生成结点的随机探索方向。以下给出具体的迷宫生成节点的探索算法（记作算法3）。

● 算法3

第1步：统计在感兴趣关键区域范围内未被访问的当前结点的相邻结点数量。

第2步：若第1步统计数量不等于0，则由[ki]，i∈[0，3MN-1]按照线性同余法生成[0，3]内的随机整数作为当前节点的随机试探方向，如果当前结点坐标记作（x，y），其试探方向（x，y-1）记作0，（x-1，y）记作1，（x+1，y）记作2，（x，y+1））记作3，直到找到一个未被访问的相邻结点。

为了进一步保护关键区域的轮廓不被轻易提取，算法进一步对关键区域以及背景区域进行像素值混淆加密，加密轨迹即迷宫置换后像素矩阵的排列顺序，加密算法的置换-混淆环节紧耦合，进一步提高加密算法的安全性。

伪随机数列[kri、kgi、kbii∈0，MN-1]也可用于对整个图像进行像素值混淆加密。在本文中，采用式⒁，来进行混淆加密：

式⒁中，[p'i]是迷宫置换后产生的图像矩阵的像素值，[Ci]是最终的密文像素值，[C0]是迷宫置换起点坐标的像素值。式⒁对应逆运算如下式：

综上所述，本文所提加密算法，加密过程的每个环节既与明文原始图像信息紧密相关，又与不规则关键区域轮廓紧密相关，且置换与混淆环节紧密耦合，算法可以抵御已知/选择明文攻击，同时加强了对原始图像中感兴趣关键区域的图像信息的保护。

3 基于迷宫置换和OCML时空混沌映射图像加密解密算法

结合前面的工作，下面给出完整详细加密算法（记作算法4）。

● 算法4

第1步：对AR、AG、AB和密钥关键区域链码CC分别计算出对应的160位SHA-1值（AR）sha-1、（AG）sha-1、（AB）sha-1和（CC）sha-1。

第2步：将（AR）sha-1、（AG）sha-1和（AB）sha-1通过式⑵分别与（CC）sha-1进行异或得到（CAR）sha-1、（CAG）sha-1和（CAB）sha-1。

第3步：将（CAR）sha-1、（CAG）sha-1和（CAB）sha-1通过式⑶和式⑷产生di， i∈[0，59]，由用户给定秘钥作为随机数种子seed生成[0，59]范围内随机数，用以打乱序列di，生成新字节序列记作ei。

第4步：将ei，i∈[0，59]和用户指定的随机数种子seed和两个用户给定秘钥a、b按式⑸、式⑹产生AR、AG和AB迷宫置换起点坐标（Xr ，Yr）、（Xg ，Yg）、（Xb ，Yb）。

第5步：将ei，i∈[36，59]和a、b按式⑼～⑿产生时空混沌映射初始矩阵序列的Logistic混沌映射的初始值[x0]和[μ]，以及OCML模型中的耦合系数[ε]、其中更新函数的参数[μ1]。

第6步：将[x0]和[μ]按式⑺进行迭代，生成与原始图像规格相等的OCML二维时空混沌映射的初始矩阵，结合式⑾和式⑿产生的[ε]和[μ1]按照式⑻驱动OCML混沌映射，迭代L轮生成伪随机数列[vri，vgi，vbi][i∈0，MN-1]，按式⒀产生[kri、kgi、kbi][i∈0，MN-1]分别用于R矩阵，用于G矩阵，用于B矩阵。

第7步：将 （Xr，Yr）、（Xg，Yg）、（Xb，Yb）及伪随机数序列[kri、kgi、kbi]，按算法2、算法3對原始待加密图像RGB矩阵对应的感兴趣关键区域进行BFS迷宫置换，置换后的矩阵分别记作PR、PG和PB。

第8步：对置换后生成的PR、PG和PB矩阵，利用前面OCML生成的伪随机数序列[kri、kgi、kbi]，采用式⒁，按照行优先顺序对图像的全部像素值进行混淆加密，最终得到密图。其RGB像素矩阵分别记作CR、CG和CB。

解密算法（记为算法5）即为加密算法的逆过程。

由上述完整加密算法可知，本文算法密钥由用户给定密钥a、b，原始待加密图像SHA-1值、不规则关键区域链码CC、随机数种子seed组成。总密钥空间足够大，可以抵抗蛮力破解。

4 实验

以下对本文所提图像加密算法从正确性、安全性以及加密效果几个方面进行实验验证。

4.1 正确性

对图1（a）按算法4以及给定密钥进行1轮加密，其对应的加密图像如图2（a）所示，对加密的图像按算法5进行解密，其对应的实验结果如图2（b）所示。

由图2可验证本文算法的正确性。

4.2 直方图均衡性

好的图像加密算法要求加密后的密图有比较均衡的直方图分布。以下是加密后图像图2（a）所对应的直方图，如图3所示。

可看出，加密后图像的RGB矩阵各阶灰度分布均衡，本文算法具有较好的加密效果。

4.3 密钥敏感性

表1是对部分密钥进行微小改动后对应实验效果，图4（a）～图4（b）是对应的解密结果。

由此可以看出，任何一个密钥有极微小改动，都解密不出原始图像。

4.4 明文敏感性分析

对原始待加密图像进行微小改动，如表2所示;按原密钥加密后与原密图进行对比，如图5所示。

从表2和图5可看出，对明文图像的RGB矩阵中任意一个像素值做微小改动，即导致密图图与原加密图像有很大差异，本文加密算法明文敏感性强。

5 结束语

综上所述，本文提出的图像加密算法将用户给定密钥与待加密图像信息及图像不规则关键区域轮廓绑定，驱动加密过程，使得加密算法中所有加密环节都与明文信息及关键区域轮廓紧密相关，且置换-混淆环节紧密耦合。实验表明，本文设计的图像加密算法加密后密图直方图分布均衡;密钥敏感性强，明文敏感性也非常强，能够抵抗已知/选择明文攻击，具有较好的加密质量和较强的安全性。

参考文献（References）：

[1] 朱和贵，蒲宝明，朱志良，等.二维Sine-Tent超混沌映射及其在图像加密中的应用[J].小型微型计算机系统，2019（7）：1510-1518

[2] 曾祥秋，叶瑞松.基于改进的Logistic映射的混沌图像加密算法[J].计算机工程，2021.3.2

[3] 蔡敏，尚钦明，孟晓燕.基于混沌时间序列的图像加密算法设计与实现[J].现代电子技术，2021（5）：47-51

[4] 魏慧，李国东，许向亮.基于改进的复合混沌系统的图像加密算法[J].微电子学与计算机，2020（4）：19-25

[5] Hua Zhongyun， Zhou Yicong. Image encryption using 2D logistic-adjusted-sine map [J]. Information Sciences，2016，339：237-253

[6] Feng Wei， He Yigang， Li Hongmin， et al. Cryptanalysis and improvementof the image encryption scheme based on 2D logistic-adjusted-sine map[J]. IEEE Access，2019（7）：12584-12597

[7] 楊璐，邵利平，郭毅，等.基于迷宫置换和Logistic混沌映射的图像加密算法[J].计算机应用，2014（7）：1902-1908

3929501908221