对基于Zigzag变换与混沌的彩色图像加密方案的破译

温 贺 平

(广东工业大学自动化学院 广东 广州 510006)(东莞职业技术学院 广东 东莞 523808)

0 引 言

随着移动互联网、云计算、社交网络和大数据等信息技术的飞速发展，多媒体数据如图像、视频、音频等的安全性愈来愈引起人们的广泛关注[1]。图像是多媒体数据的主要形式之一，通过数据加密方式对其进行隐私保护是一种常见且有效的手段[2]。混沌具有内秉随机性、对初值和参数高度敏感、众态遍历性等特征[3]，与密码学的混淆、扩散和雪崩效应具有许多相似之处[4]，基于混沌理论的图像加密技术也因此受到了研究人员的高度关注[5-14]。但由于混沌密码设计仍缺乏统一的衡量规范和标准，许多混沌加密算法在安全性方面存在问题[6-9,12,14]，故难以从理论设计走向实际应用。因而，对现有的基于混沌的图像加密算法进行安全性分析十分必要，亦是当今的一个研究热点。

近年来，许多基于“置换-扩散”算法结构的混沌图像加密算法被相继提出[5,7-9,11,13]。然而，其中的许多算法由于存在各种安全缺陷，在提出后已被分析人员实现破译[6-9,12,14]。文献[5]首次提出基于混沌理论的图像加密算法，采用先置换后扩散的算法结构，增强了混淆和扩散特性。文献[6]采用选择密文攻击对文献[5]的算法进行分析，并最终实现了破译。文献[7]提出了一种结合Logistic混沌映射和超混沌的图像加密方案，实验结果表明具有良好的密文统计特性。但是，文献[8]对文献[7]的算法进行了安全性分析，指出其无法抵御已知明文攻击和选择明文攻击，并提出了改进的方案。文献[9]在文献[7]和文献[8]的基础上提出了一种增强型的超混沌图像加密方案。然而，文献[10]采用选择明文攻击方法破译了文献[9]提出的密码算法。文献[11]设计了采用Arnold混沌映射进行比特置换，进而采用仿射密码扩散的图像加密算法。针对文献[11]，文献[12]采用选择明文攻击方法对其实现了破译。文献[13]提出了一种基于3维比特矩阵置换和扩散的图像加密算法，并声称能够抵御各种常见的攻击。文献[14]指出文献[13]的算法是不安全的，同样无法抵御选择明文攻击。密码设计和分析这对矛盾相互促进，推动着混沌密码技术向前发展。而随着混沌密码分析技术的发展，现有的混沌密码设计水平在不断提高和改进，对混沌密码算法的分析和破译难度也相应增大。然而，仍然存在一些混沌加密算法在安全性能方面存在不足，难以抵御常见的密码攻击方法。

文献[15]采用“置换-扩散”算法结构，提出了一种基于Zigzag变换与混沌的彩色图像加密算法，同时给出了一些数据分析结果，并声称能够抵御各种常见攻击。然而，本文经过分析发现，该图像加密算法存在以下安全缺陷：(1) 原算法不论是置换还是扩散过程均与明文图像无关；(2) 原算法的全局置换和局部置换均为纯像素位置置换；(3) 原算法的扩散加密过于简单，且存在等效密钥。因此，针对该算法的安全缺陷，本文提出采用选择明文攻击的方法对其进行密码分析。

1 算法描述

1.1 Zigzag变换

Zigzag变换[16]是一种常见的元素位置置换方法。以图1所示的4×4的矩阵的Zigzag变换过程进行说明，其中A和B分别为Zigzag变换前后的矩阵。其变换过程为：首先，从左下角的13开始，按照Zigzag路径逐一遍历矩阵中所有元素，由此得到一个一维序列Z；然后，将一维序列Z由逆序并按照光栅扫描顺序转换为二维矩阵B。原算法中采用了扩展的Zigzag变换，其实质亦为纯元素位置的置换方法[16]。

图1 Zigzag变换过程图

1.2 三维Logistic混沌映射

原算法采用的三维Logistic映射[17]的迭代方程为:

(1)

式中:状态变量x,y,z∈(0,1)，λ、β、α为控制参数。当控制参数满足λ∈(3.53,3.81)、β∈(0,0.022)、α∈(0,015)时，三维Logistic映射处于混沌状态。

1.3 原算法描述

根据文献[15]，原算法的描述如下：

(1) 密钥参数。原算法中共有6个密钥参数(λ,β,α,x0,y0,z0)，其中x0、y0、z0为三维Logisitc混沌映射的3个初始值。

(2) 加密过程。加密算法包括全局置换、局部置换和异或扩散三个加密步骤。首先，利用Zigzag变换对彩色图像的所有像素位置进行全局置换；接着，对预处理后的图像的R、G、B通道分别进行像素位置的置换；最后，利用三维Logisitc混沌映射产生的掩模图像对置换后的图像按比特异或进行扩散加密，得到密文图像。原算法的整体框图如图2所示。对于尺寸为H×W(高×宽)的明文彩色图像I，下面给出其加密过程描述。

图2 原加密算法整体框图

第1步 全局置换。首先，彩色明文图像I的R、G、B三个通道分别为IR、IG、IB，尺寸均为H×W。将IR、IG、IB以列不变且按行依次连接的形式，预处理得到一个尺寸为3H×W的矩阵，记为IY。

接着，利用扩展Zigzag变换对IY的像素位置进行置换，得到相同尺寸的置换矩阵I′Y。

最后，将尺寸为3H×W的矩阵I′Y分解为3个尺寸为H×W的二维矩阵，分别记为I′YR、I′YG、I′YB。

第2步 局部置换。利用扩展Zigzag变换分别对I′YR、I′YG、I′YB进行置换，置换后得到IZR、IZG、IZB。与第1步中对H×W×3个像素进行位置置换不同，此步骤中分别对R、G、B三个通道内的H×W个像素进行置换，因此称之为局部置换。

第3步 异或扩散。首先，输入密钥参数，产生混沌伪随机序列。即选取三维Logistic混沌映射的控制参数为λ、β、α和初始值为x0、y0、z0，根据式(1)，迭代W×H次，得到如下3个实数混沌序列：

(2)

式中：i=1,2,…,H×W，xi,yi,zi∈(0,1)。考虑到计算机的有限精度，每个混沌序列值均取16位有效值，得：

(3)

式中：j=1,2,…,16，m、n、p为比特数据位。

然后，选取混沌序列值中的第7～12数据位，采用下面的方法生成6个新的整数序列：

(4)

式中：i=1,2,…,H×W。分别将这6个整数序列x1i、x2i、y1i、y2i、z1i,z2i对256求余，得到6个用于加密的掩模序列X1,X2,Y1,Y2,Z1,Z2∈[0,255]。

接着，分别将掩模序列X1、X2、Y1、Y2、Z1、Z2转换成尺寸为H×W的二维掩模矩阵JX1、JX2、JY1、JY2、JZ1、JZ2。

最后，利用这6个掩模矩阵分别对置换图像的3个通道进行按比特异或扩散加密，得：

(5)

式中：“⊕”为按比特异或操作，CR、CG、CB为最终密文图像C的3个通道。

(3) 解密过程。解密则是加密的逆过程。与加密过程不同的是，首先利用混沌序列进行反扩散解密，进而利用Zigzag变换进行两次反置换解密恢复出原始明文图像。

2 密码分析和破译

在本节中，首先对原算法存在的安全缺陷进行分析，进而提出基于选择明文攻击的破译方法。

2.1 原算法的安全缺陷分析

根据现代密码学的基本假设[18]，对于攻击者来说，加密算法是完全公开的，只有密钥未知。换言之，加密算法的安全性完全决定于密钥。常用的四种密码攻击方法如表1所示。

表1 常见的四种密码攻击方法

一个安全的密码系统应当可以抵御表1中所有类型的攻击，假如无法抵抗其中的任何一种攻击方法，那么此密码系统是不安全的。因此，从密码分析的角度看，原算法存在如下的安全缺陷：

(1) 原算法不论是置换还是扩散过程均与明文图像无关。在密钥给定的情况下，对于不同的明文图像，置换和扩散过程中所采用的加密序列是固定不变的。实际上，这些加密序列可视作为算法的等效密钥。即使攻击者完全不知道密钥信息，仅利用这些等效密钥也可破译原算法。此外，这种与明文图像无关的加密算法往往难以抵御已知明文攻击和选择明文攻击。

(2) 原算法的全局置换和局部置换均为纯像素位置置换。原算法先后两次采用Zigzag变换对彩色图像进行了置换操作，理论分析和实验仿真表明此方法有效破坏了原始图像相邻像素的相关性。然而，这两次置换均为纯像素位置置换，并未改变像素值，即置换前后的图像统计直方图完全一致。因而原算法容易受到统计分析的攻击。

(3) 原算法的扩散加密仅采用按比特异或操作。扩散是确保加密算法安全的重要部件。然而，原算法采用按比特异或的方式进行扩散加密，既无非线性运算也无反馈加密机制，导致其扩散部分很容易被破译。

鉴于此，下文将介绍针对原算法的选择明文攻击方法。

2.2 选择明文攻击方法

根据表1，在选择明文攻击的假设下，密码攻击者可以临时使用加密机，选择任意有利于破译的明文，并获得相应的密文。对于“置换-扩散”结构的图像加密算法[15]，基于选择明文攻击的基本分析思路为：首先，选取像素值全部相同的特殊明文图像使得置换过程无效，从而破译出等效的扩散密钥；然后，选取一些特殊的明文图像以及获得相应的密文图像求得等效的置换密钥。基于这个分析思路，本文所采取的选择明文攻击方法的破译步骤为：

(1) 选取1幅像素值全为0的明文图像及得到相应的密文图像获取等效扩散密钥。

根据图1，当输入的明文图像的像素值全为0时，经过两次Zigzag变换的置换图像的像素值也全为0。此时，算法将退化为唯扩散加密过程。所以，根据式(5)，得像素值全为0的明文图像I0对应的密文图像C0与6个混沌掩模矩阵的关系为：

(6)

(2) 选取一些特定的选择明文图像及得到相应的密文图像获取等效置换密钥。

在获得了等效的扩散密钥后，原算法将退化为唯置换加密算法。根据文献[19-20]的分析结果，唯置换加密算法是不安全的，无法抵御选择明文攻击。且对于8比特的图像，选取「log256(L)⎤幅特定的选择明文图像及其对应的密文图像即可破译唯置换加密算法，其中，“「·⎤”表示向下取整，L是图像的像素个数。

对于唯置换加密算法的破译过程，以图像尺寸为4×4的简单例子进行说明。选取一幅像素值全部不等且由小到大的特殊明文图像为：

根据选择明文攻击的条件，临时使用加密机，可获得对应的密文图像。由于唯置换加密过程仅改变图像像素的位置，则不妨假设唯置换后的密文图像为：

当置换过程与明文图像无关时，输入不同的明文图像，唯置换过程是固定的。因此，根据选择明文图像P和对应的密文图像C，即可求得所有像素置换前后的对应关系。例如，明文图像P的第1行第1列的像素置换后对应密文图像C的第3行第2列的像素。事实上，所有像素置换前后的对应关系即为等效的置换密钥，记为EKP。

当然，由于8比特图像每个像素的取值范围为0到255，当图像像素个数超过256时显然无法仅采用一幅选择明文图像进行破译。针对这种情况，再以256×256的8比特灰度图像为例，说明唯置换的分析过程。虚构一幅特殊的明文图像，其像素值全部不等且由小到大依次排列，表示为：

经过唯置换加密后得到的密文图像记为Cv，那么根据Pv和Cv即可获取等效的置换密钥EKP。然而，受限于8比特图像像素取值范围，这样的图像是不存在的。为此，采用下面的方面将这幅虚构的图像Pv分解为2幅可构建的8比特图像P1和P2，分解方法为：

Pv=256×P2+P1

(7)

根据式(7)，得到的P1和P2分别为：

根据选择明文攻击，分别利用加密机获得与P1和P2对应的密文图像C1和C2，进而合并为与Pv对应的虚构密文图像Cv，表示为：

256×C2+C1=Cv

(8)

此时，比较Pv和Cv里所有像素的值即可获取等效的置换密钥EKP。

一般地，对于尺寸为H×W的彩色图像，由于其总共有3HW个取值为0到255的像素，因此根据上面方法破译唯置换过程所需的选择明文图像数量为「log256(3HW)⎤。

(3) 利用等效的扩散密钥和置换密钥，对密文图像破译得到原始明文图像。

首先，利用第(1)步所获得的等效扩散密钥EKD，由密文图像的CR、CG、CB破译得到唯置换图像的IZR、IZG、IZB。

接着，利用第(2)步所获得的等效置换密钥EKP，由置换图像的IZR、IZG、IZB破译得到原始明文图像的IR、IG、IB，亦即完成算法的破译。

因此，原算法无法抵御选择明文攻击，且攻击所需的数据复杂度为O(「log256(3HW)⎤+1)。

3 算法破译实验

为了验证所提出的攻击方法的有效性，选取图像尺寸为256×256的RGB彩色图像“Lena”进行实验。实验硬件平台为一台PC，处理器为Intel Core i5，主频为3.2 GHz，内存大小为8 GB。软件环境为Windows 7操作系统上运行MATLAB R2016a。

首先，根据第2.2节的第(1)步，选取一幅像素值全为0的明文图像并得到相应的密文图像，分别如图3(a)和图3(b)所示。其中，图3(b)即为等效扩散密钥EKD。

(a) 全0明文图像 (b) 对应的密文图像图3 全0明文图像及其对应的密文图像

然后，利用等效扩散密钥EKD，将“Lena”密文图像恢复为唯置换的图像。“Lena”密文图像和恢复的置换图像及其相应的直方图如图4所示。

(a) “Lena”密文图像 (b) 密文图像R通道的直方图

(c) 恢复的置换图像 (d) 置换图像R通道的直方图图4 “Lena”密文图像和恢复的置换图像及其直方图

接着，根据第2.2节的第(2)步，选取如图5(a)-(c)所示的3幅明文图像P1、P2、P3，根据选择明文攻击的条件，分别得到如图6(a)-(c)所示的相应的3幅密文图像C1、C2、C3。

(a) 明文图像P1 (b) 明文图像P2 (c) 明文图像P3图5 选取的3幅特殊的明文图像

(a) 密文图像C1 (b) 密文图像C2 (c) 密文图像C3图6 与图5分别对应的3幅密文图像

根据式(7)-式(8)，分别将图5(a)-(c)所示的3幅明文图像和图6(a)-(c)所示的相应的3幅密文图像进行如下的合并运算操作：

Pv=2562×P3+256×P2+P1

Cv=2562×C3+256×C2+C1

进而比较Pv和Cv里所有元素的值即可获取等效置换密钥EKP。

最后，根据第2.2节的第(3)步，破译还原出原始“Lena”图像及其直方图分别如图7(a)-(b)所示。

(a) 破译的“Lena”图像 (b) R通道的直方图图7 破译得到的“Lena”图像及其直方图

从图4(b)、图4(d)和图7(b)可以看出，虽然密文图像的直方图呈现类噪声分布特性，但置换图像和破译图像的直方图特性完全一致，从中也可以看出唯置换加密过程并未改变图像的统计信息。对于尺寸为256×256的彩色图像，实现破译所需的数据复杂度仅为O(「(log2563WH)⎤+1)=O(4)，运行时间约为1.25 s。

实验结果表明，本文所提的选择明文攻击方法可以有效破译原算法，而且破译所需的时间和数据复杂度都比较低。

4 结 语

本文针对一种基于Zigzag变换与混沌的彩色图像加密方案进行了安全性能分析。经过密码分析发现，原算法存在安全缺陷，置换和扩散过程均与明文无关，算法存在等效密钥。因此，本文提出了基于选择明文攻击分别获取等效扩散密钥和等效置换密钥，从而实现了对原算法的破译。理论分析和实验仿真表明，原算法是不安全的，无法抵御选择明文攻击。且对于图像尺寸为H×W的彩色图像，破译的数据复杂度为O(「(log2563HW)⎤+1)。本文的密码分析对于混沌密码设计者提高算法的安全性能具有一定的参考作用。