费雪耶兹算法结合混沌理论的图像加密方案
马开运 滕琳 孟娟
摘 要：为解决明文图像与加密密钥无关引起的安全性问题，提出一种基于费雪耶兹算法结合混沌理论的图像加密方案。首先采用一维的Logistic混沌系统针对明文图像特征进行处理生成密钥，密钥作为三维Chen混沌系统的初值，再对三维Chen混沌系统产生的混沌序列进行离散以及量化处理，得到三组伪随机序列。利用费雪耶兹算法与其中两组伪随机序列对图像进行置乱，得到置乱后的图像再与剩余的一组伪随机序列进行扩散变换，得到最终的加密图像。实验测试结果表明，该算法具有良好的安全性，能抵抗大部分攻击。
关键词：费雪耶兹算法;一维Logistic混沌系统;三维Chen混沌系统;图像加密
DOI：10. 11907/rjdk. 201906????????????????????????????????????????????????????????????????? 開放科学（资源服务）标识码（OSID）：
中图分类号：TP309 ? 文献标识码：A ??????????????? 文章编号：1672-7800（2020）011-0189-08
Image Encryption Scheme Based on Fisher-Yates Algorithm Combined
with Chaos Theory
MA Kai-yun1，2，3，TENG Lin4，MENG Juan1，2，3
（1. School of Information Engineering， Dalian Ocean University;
2. Key Laboratory of? Environment Controlled Aquaculture，Ministry of Education，China;
3. Key Laboratory of Marine Information Technology of Liaoning Province， Dalian， Liaoning， Peoples Republic of China;
4. School of Information Science and Technology， Dalian Maritime University， Dalian 116023， China）
Abstract：In order to solve the security problem caused by the plaintext image independent of the encryption key， a new image encryption scheme based on Fischer algorithm and chaos theory is proposed. Firstly， the one-dimensional Logistic chaotic system is used to process the characteristics of plaintext image to generate the key. The key is taken as the initial value of the three-dimensional Chen chaotic system. Then， the chaotic sequence generated by the three-dimensional Chen chaotic system is discretized and quantized， and three groups of pseudo-random sequences are obtained. The image is scrambled by using Fischer algorithm and two groups of pseudo-random sequences. The image is then transformed with the remaining pseudo-random sequences to obtain the final encrypted image. Experimental results show that the algorithm has high security and can resist most attacks.
Key Words：Fisher-Yates scrambling algorithm; one-dimensional logistic chaotic system; three-dimensional Chen chaotic system; image encryption
0 引言
大数据时代越来越多的信息呈现数字化特征，人们每天的生活已经离不开数据。数字化在带给人们便捷的同时，个人隐私泄露、数据非法窃取等安全性问题也随之而来。图像加密是密码学的一个重要研究方向，数字图像数据量大，包含较多的冗余信息，像素相关性较大。传统的加密算法如RSA、DES等算法，对加密文本信息效果良好，但是对加密数字图像数据效果不佳。混沌理论作为非线性科学研究的新兴学科，由于其与密码学有着很多联系，既包含了传统密码学部分优良特性，又在这些特性上进行了提升，如对初始条件和参数控制的敏感性、混沌轨道的伪随机性、混沌态的不可预测性、遍历性、混合性等[1-2]，所以利用混沌理论结合传统密码学进行图像的加密会使密文图像安全性得到提升。
目前基于混沌理论的图像加密算法通常采用“置乱—扩散”的加密结构。置乱算法通常采用改进的Arnold变换、幻方变换、Hilbert曲线变换等方法，对图像像素的位置进行置乱[3-5]。这些置乱方法极大促进了图像加密技术发展，但后来的研究又暴露了一些问题，如Arnold变换具有明显的周期性，一些置乱算法存在全局置乱性差的缺点。本文采用费雪耶兹置乱方法是一种洗牌算法，其优点是它在完全随机排序中没有任何规律性，与Arnold变换等一些有限周期置乱方法相比，该算法是安全的，其运用于图像加密效果良好。文献[6]利用该算法结合一维Logistic映射产生的混沌序列和排序置乱算法对图像像素进行两次置乱，再利用DNA编码结合混沌序列替换明文信息，最后增加像素级扩散的明文统计，以确保明文的敏感性;文献[7]将一幅平面图像分割成大小相等的多个切片，然后用三维Cat混沌映射对图像的三维表示进行洗牌。利用分数阶非线性微分方程组实现图像像素值的扩散，利用费雪耶兹算法构造混沌矩阵，用于数据点排列。由于低维混沌系统结构较简单，易受到攻击，因此加密所选择的混沌系统也通过使用多个一维映射的参数耦合、多个一维映射的切换和级联等方法[8-9]，增加一维混沌系统结构的复杂度，或是选用高维的混沌系统，如三维Lorenz混沌系统[10]、三维Chen混沌系统、四维混沌系统[11]甚至更高维度的混沌系统以及超混沌系统[12-14]等。为进一步提高图像加密算法的安全性，研究人员开始把明文特征与密钥进行结合，以防止密码分析者通过选择明文攻击去破解加密图像，如王兴元等[15]通过把原图像进行分块处理，利用混沌序列结合分块处理的图像块对置乱以及扩散的操作产生影响;朱和贵等[16]利用方程随机生成4个初始值，其中一对用来作为混沌系统的初值进行图像置乱操作，另一对用来作为混沌系统的初值进行图像扩散操作。
本文根据明文特征结合一维Logistic混沌系统生成密钥，作为三维Chen混沌系统的初始值。通过处理三维Chen混沌系统迭代产生的混沌序列得到伪随机序列。通过处理伪随机序列，将其中两组通過结合费雪耶兹算法对图像像素位置进行置乱，剩余的一组用来进行扩散变换，得到最终的加密图像。
1 相关知识
1.1 费雪耶兹算法
费雪耶兹（Fisher-Yates）算法也称高纳德（Knuth）随机置乱算法，是对一组有限的序列进行随机排序。以10个元素的一组序列为例（随机数产生的序列为6，3，8，4，1，4，1，1，1，1），算法步骤如图1所示。
因为每次随机产生的数值不一样，所以最终置乱得到的序列也不一样，如果把原算法直接应用于图像像素置乱，得到的密文图像就可能无法正确还原，而每次选择随机数进行置乱操作之后随机数产生的范围会越来越小，前面被置乱的序列值位置就会固定，不会被下一次置乱所影响。本文利用混沌序列代替每次随机产生的数值，进而有效控制算法中每次交换的元素，有效解决了这些问题。把该算法应用到图像置乱领域，以一个3×3数组矩阵为例，置乱过程如图2所示。
1.2 两种混沌系统
1.2.1 一维Logistic混沌系统
一维Logistic映射也称虫口映射，是应用最为广泛的经典一维混沌映射[17]，其动力学公式如式（1）所示。当控制参数μ∈（3.569 945 6，4]时，Logistic映射处于混沌状态。选取初值x0=0.1、μ=4对系统进行仿真，得到经典的一维Logistic混沌系统吸引子相图，如图3所示。
xn+1=μxn（1-xn）?????????? （1）
1.2.2 三维Chen混沌系统
三维Chen 混沌系统由陈关荣教授[18]在1999年提出，该微分系统方程如下：
x=α（y-x）y=γ-αx-xz+γyz=xy-βz????????? （2）
当混沌系统控制参数α=35，β=3，γ=28时，系统处于混沌状态且混沌性质最好。设混沌系统初始值x0=0.995，y0=0.995，z0=0.995，对系统数值进行仿真，得到三维Chen混沌系统吸引子相图如图4所示。
2 算法设计
2.1 密钥获取
目前很多混沌加密算法没有把明文和密钥关系考虑进去，多张不同的图像采用相同的密钥加密，密码分析者可选择密文攻击或明文攻击，很容易破解出密钥，算法安全性无法保证。对一幅大小为m×n的灰度明文图像用二维矩阵P表示，按照一行接一行的顺序将图像矩阵转换成一条整数值序列，记作{Ai}，按照一列接一列的顺序将原图像矩阵转换成一条整数值序列记作{Bi}，其中i∈（1，m×n）。
P=p11p12p21p22？p1np2n？？？pm1pm2？pmn
将{Ai}、{Bi}倒序排列，序列下标值为奇数时：
Ci=B（m×n+1-i）???????? （3）
序列下标值为偶数时：
Ci=A（m×n+1-i）???????? （4）
以一个4×4大小的数组矩阵为例，序列获取流程如图5所示。
利用一维Logistic混沌系统选取系统初值X0，控制参数μ、X0和μ与加密时间有关，以秒为单位，则一整天时间TM=86400s。假设加密时间为JM，那么通过式（5）、式（6）可得到X0与μ的值。将系统迭代m×n+100次舍弃前100个序列产生的一维混沌序列记作{Xi}，其中i∈（1， m×n）。将{Ai}、{Bi}、{Ci}序列分别与{Xi}相乘，累积之和分别为A、B、C，再通过式（7）-（9）得到最终密钥a、b、c。这种方式获取的密钥会根据图像像素分布的位置以及大小的变化而变化，也就是说不同的图像通过处理会生成不同的密钥，密钥获取流程如图6所示。
x0=JMTM，JM∈（0，86 400）JM+0.5TM，JM=0||JM=86 400?????? （5）
μ=4-0.1×JMTM???????????????? （6）
a=（mod（modA'，m×n，255））/255???? （7）
b=（mod（modB'，m×n，255））/255???? （8）
c=（mod（modC'，m×n，255））/255??? （9）
2.2 伪随机序列获取
将前述获取的密钥a、b、c分别作为三维Chen混沌系统x、y、z的初值，即x0=a，y0=b，z0=c。利用龙格库塔法对连续的三维Chen混沌系统进行离散化，令混沌系统的控制参数α=35，β=3，γ=28，迭代m×n+100次。为避免混沌映射初始迭代对随机性的负面影响，舍弃前100个序列值，得到3个方向的混沌序列{T1i}、{T2i}、{T3i}，其中i∈（1， m×n）。对3个方向的混沌序列进行量化处理，步骤如下：①将所有实数序列值去掉负号即取正数;②去掉所有实数序列值的整数部分，保留小数。
处理得到伪随机序列{Xi}、{Yi}、{Zi}，其中i∈（1， m×n），{Xi}、{Yi}、{Zi}∈（0，1）。由于得到的偽随机序列存在局部连续递增或递减问题，所以要对伪随机序列进行处理。
当下标值i为奇数时：
E1i=X'（i）???????????? （10）
E2i=Y'i???????????? （11）
当下标值i为偶数时：
E1i=Y'i???????????? （12）
E2i=X'i???????????? （13）
这样处理之后得到两组伪随机序列{E1i}与{E2i}，Z方向的伪随机序列直接赋给序列{E3i}，具体的伪随机序列获取流程如图7所示。
2.3 置乱算法
利用费雪耶兹算法，将所需加密的m×n大小图像矩阵按照一列接一列的顺序转换成一条整数值序列，表示为{Di}，其中i∈（1， m×n）。对伪随机序列{E1i}、{E2i}进行处理，处理方式如式（14）、式（15）所示。
E1′（i）=ceil（m×n×E1（i））?????? （14）
E2′（i）=ceil（m×n×E2（i））?????? （15）
处理完之后的{E1′i}、{E2′i}∈（0，m×n]为正整数。把{E1′i}、{E2′i}每轮的序列值作为费雪耶兹算法置乱时每轮的随机数，令Q∈[0，255]，利用式（16）-（21）对图像像素位置进行两次置乱操作，得到第一次置乱后的序列{D′i}和第二次置乱后的序列{D″i}。
Q=Di?????????????? （16）
D（i）=DE1′i??????? （17）
D（E1′（i））=Q?????????? （18）
Q=D′（i）?????????????? （19）
D′（i）=D′E2′i?????? （20）
D′E2′i=Q????????? （21）
2.4 加密步骤
加密步骤如下：①根据原图像像素特征获取密钥，本文以大小为256×256的“Lena”为例，如图8（a）所示;②根据所得密钥结合三维Chen混沌系统产生三组混沌序列，对三组混沌序列进行处理以获取加密用的三组伪随机序列，伪随机序列获取方法见前文详述;③根据费雪耶兹置乱算法，利用E1′（i）、E2′（i）序列对原图像进行两次像素置乱，第一次置乱得到图像F1，再利用F1进行第二次置乱，得到图像F2，如图8（b）、8（c）所示;④对{E3i}序列进行处理，如式（20）所示。
E3′（i）=uint8（E3（i）×255）???????? （22）
把{E3′i}按照一列接一列的方式组成一个m×n大小的混沌矩阵P1进行矩阵扩散变换，扩散操作描述为：
G=P1F2?????????????? （23）
G为扩散操作后的加密矩阵，得到最终加密图像如图8（d）所示，加密流程如图9所示。
2.5 解密步骤
解密步骤是加密步骤的逆过程，通过密文图像的矩阵G与P1矩阵进行扩散操作，可描述为：
F2=P1G?????????????? （24）
得到圖像F2，经过处理之后得到{D″i}序列，令Q∈[0， 255]，由方程（25）～（27）处理之后，得到第一次置乱的图像F1，再由方程（28）～（30）处理之后得到明文图像，解密流程如图10所示。
Q=D″m×n+1-i????????? （25）
D″m×n+1-i=
D″E2′m×n+1-i???????? （26）
D″E2′m×n+1-i=Q???? （27）
Q=D′m×n+1-i??????????? （28）
D′m×n+1-i=
D′E1′m×n+1-i?????????? （29）
D′E1′m×n+1-i=Q?????? （30）
3 实验分析测试
3.1 密钥空间
密钥空间大小关系算法安全度。为避免密文图像被暴力攻击导致泄密，一个相对安全的加密算法需要拥有一个足够大的密钥空间。本文算法中密钥为多个数据组成，分别由一维Logistic映射与明文图像生成的密钥a、b、c，即三维Chen混沌系统的初值。若浮点数的精度可以达到10-14，则该算法的密钥空间大小可达到1014×1014×1014=1042，可以看出该算法的密钥空间足够大，所以加密算法能够在一定程度上抵抗暴力破解。
3.2 密钥敏感性
密钥敏感性体现在：如果密钥的数据只由一个参数控制，那么这个参数就算有细微变化，最终得出的密文图像也会与原密钥得出的密文图像有非常大的区别。如果密钥由多个参数组成，只有当这个密钥中所有参数都正确，才会得出最终正确的图像。为了验证加密算法对各密钥的敏感性，本文选取的测试明文图像是“Lena”，分别对各密钥中的数据做微小改变，每次改动密钥中一个元素的值。实验准备3组与原密钥数据接近的错误密钥进行测试。首先利用正确密钥对密文图像进行解密，正确的密钥key（a=0.0.975013469899183，b=0.559240934707444，c=0.9185988 40376545），解密后正确解密的图像如图11（a）所示。接着分别输入akey（a=0.975013469899182，b=0.559240934707 444，c=0.918598840376545），bkey（a=0.975013469899183，b=0.559240934707443，c=0.918598840376545），ckey（a=0.975013469899183，b=0.559240934707444，c=0.9185988 40376544），使用错误密钥解密的图像分别如图11（b）、（c）、（d）所示。
实验结果显示，密钥参数的微小改变对解密结果有很大影响，错误密钥解密生成的图像和明文图像几乎没有联系，3幅错误密钥解密的图像也说明本文算法的密钥敏感性较高。
3.3 算法统计特性分析
3.3.1 直方图
直方图是一个数字图像的灰度值以及分布情况的具体化展现，加密算法的安全性能高低可以通过直方图显示的图像线条分布情况进行判断，越好的加密算法像素灰度值的平滑程度越高，像素灰度值分布越均匀，像素直方图如图12所示。
3.7 噪声攻击
在通过物理信道进行图像传输过程中不可避免会受到噪声污染，因此可以设计出一个良好的密码系统，以在一定程度上抵抗噪声干扰。在加密图像中加入不同密度d的椒盐噪声和不同均值m和方差v的高斯白噪声，见图15。从图15可以看出，当密文图像受到不同密度的噪声影响时，仍然可以成功地恢复解密图像。
4 结语
针对很多图像加密算法密钥与明文图像没有关联问题，本文首先对明文图像进行处理，生成与明文图像特征相关的三组实数序列，运用一维Logistic混沌系统处理三组实数序列得到密钥，密钥作为三维Chen混沌系统的初值;再处理通过三维Chen混沌系统产生的三组混沌序列生成三组伪随机序列，运用费雪耶兹置乱算法结合两组伪随机序列对图像进行两次置乱;最后用剩余的一组伪随机序列处理两次置乱后的图像，进行扩散变换得到最终加密图像。对本文的加密方案进行仿真，从密钥空间大小、密钥的敏感性、直方图、相邻像素相关性、信息熵、差分攻击分析、信息丢失攻击以及噪声攻击等方面进行测试。测试结果表明，本文算法抵御各种破解攻击的能力更强，具有更高的安全性。但本文算法运行效率还存在一定的提升空间，后续可针对算法运行效率优化进行研究。
参考文献：
[1] 王永，马键滨，刘兆龙，等. 基于时空混沌系统的彩色图像加密算法[J]. 计算机应用研究，2016，33（8）：1-7.
[2] FRANCISCO B I，CARLOS L，STEPHEN W. Chaotic dynamics in nonautonomous maps application to the nonautonomous henon map[J].? International Journal of Bifurcation and Chaos，2015，25（12）：1-14.
[3] 丁煜明. 基于混沌的数字图像加密算法研究与实现[D]. 广州：广东工业大学，2016.
[4] 张硕. 小波分析与混沌理论在图像加密中的应用[D]. 桂林：桂林电子科技大学，2010.
[5] 汪乐乐，李国东. 基于分数阶Fourier的双混沌加密算法[J]. 计算机科学，2018，45（S2）：393-397，401.
[6] WANG X， ZHANG J J，ZHANG F C， et al.New chaotical image encryption algorithm based on fisher-Yatess scrambling and DNA coding[J].? Chinese Physics B，2019，28（4）：125-134.
[7] FARHAN M， SANJEEV K.A novel fractional order chaos-based image encryption using fisher yates algorithm and 3-D cat map[J]. Multimedia Tools and Applications，2019，78（11）：14867-14895.
[8] 吕群，薛伟. 结合混沌映射和动态S-盒的图像加密算法[J]. 小型微型计算机系统，2018，39（3）：607-613.
[9] HUA Z，ZHOU Y. One-dimensional nonlinear model for producing chaos[J].? IEEE Transactions on Circuits&Systems，2018，65（1）：235-245.
[10] ZHANG Q. Research and implementation of image encryption based on Lorenz chaotic system[D]. 哈尔滨：黑龙江大学，2017.
[11] YANG K X， WU Z H， HAO R B， et al.Four-dimensional chaotic system and ITS application in image encryption[J].? Application Research of Computers，2019，23（4），1-5.
[12] HONG M? Y，YE L，LI H? G， et al. A new image cryptosystem based on 2D hyper-chaotic system[J]. Multimed Tools Appl，2017，15（76）：8087-8108.
[13] 王勇，方小強，王瑛. 超混沌系统和AES 结合的图像加密算法[J]. 计算机工程与应用，2019，55（8）：164-170.
[14] 张勋才，刘奕杉，崔光照. 基于DNA编码和超混沌系统的图像加密算法[J]. 计算机应用研究，2019，36（4）：1139-1143.
[15] WANG X，TENG L.An image blocks encryption algorithm based on spatiotemporal chaos[J].? Nonlinear? Dynamics，2012，67（1）：365-371.
[16] 朱和贵，蒲宝明，朱志良，等. 二维Sine-Tent超混沌映射及其在图像加密中的应用[J]. 小型微型计算机系统，2019，40（7）：1510-1518.
[17] 左飞. 数字图像处理：技术详解与Visual C++实践[M]. 北京：电子工业出版社，2014.
[18] CHEN G R， UETA T. Yet another chaotic attractor[J].? International Journal of Bifurcation and Chaos，1999，9（7）：1465-1466.
[19] SHANNON C E. Communication theory of secrecy systems[J].? Bell Syst Tech J，1949，28（9）：656-715.
[20] AHMAD J，KHAN M A，HWANG S O，et al.A compression sensing and noise-tolerant image encryption scheme based on chaotic maps and orthogonal matrices[J]. Neural Computing Applications，2016，28（1）：953-967.
（责任编辑：杜能钢）
