对一个数字图像加密算法的安全性分析*

张鹏伟，张 涛

(解放军信息工程大学三院，河南 郑州 450004)

对一个数字图像加密算法的安全性分析*

张鹏伟，张 涛

(解放军信息工程大学三院，河南 郑州 450004)

混沌系统具有的许多基本特性都可以和密码学中的混乱和扩散概念联系起来，20世纪80年代混沌理论开始涉足密码领域。混沌密码作为一类新型的密码技术，近年来成为当前信息安全领域研究的热点之一。针对一个数字图像加密算法的安全性进行了研究。指出了基于Lorenz混沌系统设计的数字图像加密算法的本质是一个移位算法，给出了算法的信息泄漏规律，以此为基础在已知明文的条件下给出了恢复算法密钥的攻击算法，对于N1×N2大小的明文图像，攻击方法的计算复杂性为(N1×N2)2/212。理论分析和实验结果均表明该图像加密算法是不安全的。

密码分析；混沌密码；数字图像加密算法；已知明文攻击；Lorenz混沌映射

1 引言

混沌现象自20世纪60年代开始被多个科学研究领域关注，20世纪80年代混沌理论开始涉足密码领域。混沌系统具有的许多基本特性，如遍历性、混合性、确定性和对初始条件的敏感性，都可以和密码学中的混乱和扩散概念联系起来[1]。因此，基于混沌系统来设计新型的密码方案就变得自然了[2]。混沌密码是将混沌映射作为编码环节所设计的密码算法。混沌密码作为一类新型的密码技术，近年来在数据加密[3～6]、图像加密[7,8]和数字水印[9]等领域得到了广泛的研究，成为当前信息安全领域研究的热点之一。

王英等人[10]设计了一个基于Lorenz混沌系统的数字图像加密算法，为便于描述，下文中基于算法的作者姓名简称为WZJ图像加密算法。WZJ图像加密算法使用Lorenz混沌系统的三个实初始值和三个实系统参数作为初始密钥，通过Lorenz混沌系统迭代生成实数值数列，对实数值序列进行预处理并按照处理后数列的升序关系来生成移位指示矩阵，对明文图像进行加密时，利用移位指示矩阵对明文图像以N1×N2的数据块为单位进行位置移位变换，产生密文图像完成加密。WZJ图像加密算法使用实混沌系统作为产生加密移位序列的初始乱源，由于初始密钥为Lorenz混沌系统的三个实初始值和三个实系统参数，使得分析者难以实现对该系统的任何直接穷尽攻击，而且该系统不直接用于明文信息加密，又避免了实序列的离散化问题，在混沌图像加密算法的设计上具有新意，有典型的代表性。对该算法进行分析，将有助于完善混沌密码的分析理论。

本文分析指出基于Lorenz混沌系统设计的数字图像加密算法的本质是一个移位算法，给出了算法的信息泄漏规律，以此为基础在已知明文的条件下给出了恢复算法密钥的攻击算法，并对攻击算法的复杂度进行了分析。

2 WZJ数字图像加密算法

下面首先简述WZJ图像加密算法的结构。

WZJ图像加密算法的设计基于Lorenz混沌系统，该混沌系统是经典的三维混沌系统，其动力学方程为：

dx/dt=σ(y-x)

dy/dt=rx-zx-y

dz/dt=xy-bz

其中，σ、r、b为系统参数，典型值为σ=10,r=28,b=8/3。在保持σ、b不变，r=24.74时，Lorenz系统进入混沌状态。Lorenz系统需要数值积分来求得数值混沌序列，文献[10]采用一阶Euler法进行计算。

WZJ图像加密算法包括三步：

(1)输入待加密的明文图像，大小为M×N，对图像进行预处理，即将边界填充灰度值0，将图像大小填充为8×8的整数倍，计填充后的大小为N1×N2。

(2)给Lorenz混沌系统赋初值，并赋三个参数值，迭代Lorenz混沌系统，确定积分步长和截取长度，以及迭代次数；按需要长度l=(N1×N2)/ (8×8)产生三条实值序列x、y、z，将三条实值序列x、y、z各自去掉整数部分，然后按照升序排列;利用该序列指定置乱索引矩阵Px、Py、Pz中各元素的几何位置，各元素按照索引序列的顺序赋为1～l的自然数。

备注1：文献[10]没有更为详细地交待置乱索引矩阵Px、Py、Pz的生成，从文中描述推测，应该是将三条实值序列x、y、z各自去掉整数部分，然后按照升序排列，根据每条序列中的实数在未按升序排列前的位置来对矩阵进行填充。具体地，若x1在序列x中原来的位置为7，则矩阵Px的第一个元素就为7。

(3)加密过程为，以8×8的明文图像块为单位，利用置乱索引矩阵重排图像块生成密文图像。

备注2：算法的密钥设计者指出可以是三维Lorenz混沌系统的三个实值初始值和三个实值参数，但用于明文图像加密变换的是置乱索引矩阵，因此加密算法的密钥直接等效于置乱索引矩阵，分析中不再需要考虑六个实值数的恢复。此外，设计者没有交待加密过程中如何使用三个置乱索引矩阵，考虑到加密一幅明文图像时，以8×8的像素位置块为单位进行位置变换，其变换后的位置应该是唯一的，因此加密一幅明文图像只能使用一个置乱变换矩阵。

以上为王英等人设计的WZJ数字图像加密算法，详见文献[10]。

3 WZJ数字图像加密算法分析

下面对WZJ数字图像加密算法的安全性进行分析。基于Lorenz混沌系统的图像加密算法本质上是利用置乱索引矩阵产生一个移位密码，对移位密码的分析是古典密码的分析范畴。移位密码实际上对应于一个位置置换表，等价于置乱索引矩阵，故该置换表就是密码算法的等效密钥。下面给出对该移位密码的两个分析方法：

方法1假设攻击者可以得到足够多的明文图像及对应的由同一密钥加密的密文图像。

方法2假设攻击者只能得到一幅明文图像及对应的密文图像。

记明文图像A的第i个8×8像素灰度值块为αi，密文图像AE的第j个8×8像素灰度值块为βj。

由加密算法知，明文图像A的第i个8×8像素灰度值块αi按照置乱索引矩阵的指示进行位置的变换，不防设变换后为密文图像AE的第j个8×8像素灰度值块βj，则由于位置变换并不改变该像素块的像素灰度值，则必有αi=βj。据此，对于明文图像的每一个8×8像素灰度值块αi，可以对密文图像的所有8×8像素灰度值块xj与αi进行对比检验。若xj穷举正确，则xj=αi；若穷举错误，则xj=αi以极小的概率成立，以此为依据就可得到置乱索引矩阵第ij位置的几何值的候选值。同理依次类推，可以得到置乱索引矩阵所有位置几何值的候选值。

算法1对WZJ算法的已知明文攻击算法

步骤1对于0≤i≤(N1×N2)/(8×8),对明文图像的8×8像素灰度值块αi；

对于0≤j≤(N1×N2)/(8×8)，对密文图像的所有8×8像素灰度值块xj；

判定xj=αi是否成立，若成立，则记j为置乱索引矩阵第ij位置的几何值的候选值；若不成立，j++，对xj的下一个可能值进行检验，直到所有的检验结束；

步骤2用步骤1所产生的置乱索引矩阵的候选值加密明文图像,若得到的图像与密文图像一致,则输出置乱索引矩阵，算法结束；否则检验下一个可能的置乱索引矩阵。

定理1算法1找到混沌序列的成功率为1，穷举复杂性为(N1×N2)2/212。

证明由于算法1的各步骤均不漏掉混沌序列的每个可能值，故正确的混沌序列一定可以找出，因此算法1的成功率为1。

由于WZJ数字图像加密算法首先将明文图像分成8×8像素灰度值块，然后逐块进行位置移位加密。假设明文图像的大小为N1×N2，则加密时明文图像被分为(N1×N2)/(8×8)个8×8像素灰度值块。

假设第一个明文图像的8×8像素灰度值块的像素灰度值为αi，根据算法1，利用密文图像的(N1×N2)/(8×8)个8×8像素灰度值块xi均依次检验，找到明文图像8×8像素灰度值块的像素灰度值为αi被移位后在密文图像中的位置，以此类推，直到找到所有的位置,这等价于找到算法的移位矩阵,故算法1的穷举复杂性为(N1×N2)2/212。

□

至此，我们得到置乱索引矩阵所有位置几何值，即该图像加密算法的等效密钥。

我们做了一例攻击实验。取密钥三维Lorenz混沌系统的三个实值初始值为x0=1.184,y0=1.3627,z0=1.2519，控制参数为σ=10,r=28,b=8/3，积分步长为0.001，迭代次数为104，截取长度为34 000～35 000。明文图像为512×512的256色灰度图，因此N1=N2=512。图1是512×512的明文图像Lena.bmp，图2是密文图像。利用算法1得到置乱索引矩阵所有位置几何值，即该图像加密算法的等效密钥。在主频为2.5 GHz的Pentium 4 PC机上，攻击算法所用时间不足1 min。

Figure 1 Plain image

Figure 2 Cipher image

4 结束语

本文对王英等人设计的基于Lorenz混沌系统的数字图像加密算法的安全性进行了研究，该算法本质上是一个移位密码，给出了对该算法的已知明文攻击方法。对于N1×N2大小的明文图像，攻击方法的计算复杂性为(N1×N2)2/212。理论分析和实验结果均表明该图像加密算法是不安全的。

[1] Zhang Bin. The research and application of chaotic cipher algorithm analysis method [D].Zhengzhou:The PLA Information Engineering University,2006.(in Chinese)

[2] Kohda T,Tsuneda A. Statistics of chaotic binary sequences [J]. IEEE Transactions on Information Theory,1997,43(1):104-112.

[3] Yuan Chun,Zhong Yu-zhuo,Yang Shi-qiang. Composite chaotic pseudo-random sequence encryption algorithm for compressed video[J]. Tsinghua Science and Technology,2004,9(2):234-241.

[4] Hu Han-ping,Liu Shuang-hong,Wang Zu-xi. A method of chaotic key stream generated [J]. Chinese Journal of Computers,2004,27(3):408-412.(in Chinese)

[5] Wang Shi-hong,Lu Hua-ping,Hu Gang. A new self-synchronizing stream cipher[BE/OL]. [2005-11-16].http://arxiv.org,number:nlin.

[6] Liao Ni-huan,Gao Jin-feng. Generalized map chaotic spread spectrum sequence and its characteristic analysis [J]. Journal of Electronics and Information,2006,28(7):1255-1257.(in Chinese)

[7] Mao Yao-bin,Chen Guan-rong. Chaos-based image encryption[M]∥Handbook of Geometric Computing,Berlin:Springer Berlin Heidelberg, 2005:231-265.

[8] Paraskevi T,Klimis N,Stefanos K. Security of human video objects by incorporating a chaos-based feedback cryptographic scheme[C]∥Proc of ACM Multimedia’04,2004:1.

[9] Tang Guo-ping,Liao Xiao-feng. Shearing robust watermarking algorithm based on chaotic maps [J]. Computer Engineering,2005,31(9):34-36.(in Chinese)

[10] Wang Ying, Zheng De-ling, Ju Lei. Digital image encryption algorithm based on three-dimension Lorenz chaos system [J]. Journal of Beijing University of Science and Technology,2004,26(6):678-682.(in Chinese)

附中文参考文献：

[1] 张斌.混沌密码算法分析方法的研究与应用[D].郑州:解放军信息工程大学,2006.

[4] 胡汉平,刘双红,王祖喜.一种混沌密钥流产生方法[J]. 计算机学报,2004,27(3):408-412.

[6] 廖旎焕,高金峰. 广义映射混沌扩频序列及其特性分析[J]. 电子与信息学报,2006,28(7):1255-1257.

[9] 唐国坪,廖晓峰. 基于混沌映射的抗剪切鲁棒水印算法[J]. 计算机工程,2005,31(9):34-36.

[10] 王英,郑德玲,鞠磊. 基于Lorenz混沌系统的数字图像加密算法[J].北京科技大学学报,2004,26(6):678-682.

张鹏伟(1977-),男,山西偏关人，博士生，研究方向为信息安全和电子商务。E-mail:Zhang-pw@126.com

ZHANG Peng-wei,born in 1977,PhD candidate,his research interests include information security, and electronic commerce.

张涛(1978-),男,四川武胜人，博士，工程师，研究方向为信息安全和电子商务。E-mail:Zt890@sina.com

ZHANG Tao,born in 1978,PhD,engineer,his research interests include information security, and electronic commerce.

Security analysis of a digital image encryption algorithm

ZHANG Peng-wei，ZHANG Tao

(The PLA Information Engineering University,Zhengzhou 450004,China)

Many of the basic characteristics of the chaotic systems can be linked with the concepts of confusion and diffusion in cryptography, and the chaos theory began to get involved in the cryptography field in the 1980s. As a kind of new cryptography technology, chaotic cipher has become a hot topic in the field of information security in recent years. We study the security of a digital image encryption algorithm, and show that the digital image encryption and decryption algorithm based on Lorenz chaos system is essentially a shift cipher. We also point out the leakage laws of the algorithm and propose a algorithm against known plaintexts attacks. For a N1×N2plain image, the computational complexity is (N1×N2)2/212. Theoretical analysis and experimental results demonstrate the insecure feature of this digital image encryption algorithm.

cryptanalysis;chaos cipher;digital image encryption algorithm;know plain text attack;Lorenz chaotic map

1007-130X(2015)09-1652-04

2014-09-25;

2014-12-30基金项目：博士后科学基金资助项目(2014M562582)

TP309

A

10.3969/j.issn.1007-130X.2015.09.008

通信地址：450001 河南省郑州市高新区科学大道62号信息工程大学301信箱

Address:Mailbox 301,The PLA Information Engineering University,62 Kexue Avenue,High-tech Zone,Zhengzhou 450004,Henan,P.R.China