對(duì)基于Zigzag變換與混沌的彩色圖像加密方案的破譯

溫 賀 平

(廣東工業(yè)大學(xué)自動(dòng)化學(xué)院 廣東 廣州 510006)(東莞職業(yè)技術(shù)學(xué)院 廣東 東莞 523808)

0 引 言

隨著移動(dòng)互聯(lián)網(wǎng)、云計(jì)算、社交網(wǎng)絡(luò)和大數(shù)據(jù)等信息技術(shù)的飛速發(fā)展，多媒體數(shù)據(jù)如圖像、視頻、音頻等的安全性愈來(lái)愈引起人們的廣泛關(guān)注[1]。圖像是多媒體數(shù)據(jù)的主要形式之一，通過(guò)數(shù)據(jù)加密方式對(duì)其進(jìn)行隱私保護(hù)是一種常見(jiàn)且有效的手段[2]?；煦缇哂袃?nèi)秉隨機(jī)性、對(duì)初值和參數(shù)高度敏感、眾態(tài)遍歷性等特征[3]，與密碼學(xué)的混淆、擴(kuò)散和雪崩效應(yīng)具有許多相似之處[4]，基于混沌理論的圖像加密技術(shù)也因此受到了研究人員的高度關(guān)注[5-14]。但由于混沌密碼設(shè)計(jì)仍缺乏統(tǒng)一的衡量規(guī)范和標(biāo)準(zhǔn)，許多混沌加密算法在安全性方面存在問(wèn)題[6-9,12,14]，故難以從理論設(shè)計(jì)走向?qū)嶋H應(yīng)用。因而，對(duì)現(xiàn)有的基于混沌的圖像加密算法進(jìn)行安全性分析十分必要，亦是當(dāng)今的一個(gè)研究熱點(diǎn)。

近年來(lái)，許多基于“置換-擴(kuò)散”算法結(jié)構(gòu)的混沌圖像加密算法被相繼提出[5,7-9,11,13]。然而，其中的許多算法由于存在各種安全缺陷，在提出后已被分析人員實(shí)現(xiàn)破譯[6-9,12,14]。文獻(xiàn)[5]首次提出基于混沌理論的圖像加密算法，采用先置換后擴(kuò)散的算法結(jié)構(gòu)，增強(qiáng)了混淆和擴(kuò)散特性。文獻(xiàn)[6]采用選擇密文攻擊對(duì)文獻(xiàn)[5]的算法進(jìn)行分析，并最終實(shí)現(xiàn)了破譯。文獻(xiàn)[7]提出了一種結(jié)合Logistic混沌映射和超混沌的圖像加密方案，實(shí)驗(yàn)結(jié)果表明具有良好的密文統(tǒng)計(jì)特性。但是，文獻(xiàn)[8]對(duì)文獻(xiàn)[7]的算法進(jìn)行了安全性分析，指出其無(wú)法抵御已知明文攻擊和選擇明文攻擊，并提出了改進(jìn)的方案。文獻(xiàn)[9]在文獻(xiàn)[7]和文獻(xiàn)[8]的基礎(chǔ)上提出了一種增強(qiáng)型的超混沌圖像加密方案。然而，文獻(xiàn)[10]采用選擇明文攻擊方法破譯了文獻(xiàn)[9]提出的密碼算法。文獻(xiàn)[11]設(shè)計(jì)了采用Arnold混沌映射進(jìn)行比特置換，進(jìn)而采用仿射密碼擴(kuò)散的圖像加密算法。針對(duì)文獻(xiàn)[11]，文獻(xiàn)[12]采用選擇明文攻擊方法對(duì)其實(shí)現(xiàn)了破譯。文獻(xiàn)[13]提出了一種基于3維比特矩陣置換和擴(kuò)散的圖像加密算法，并聲稱(chēng)能夠抵御各種常見(jiàn)的攻擊。文獻(xiàn)[14]指出文獻(xiàn)[13]的算法是不安全的，同樣無(wú)法抵御選擇明文攻擊。密碼設(shè)計(jì)和分析這對(duì)矛盾相互促進(jìn)，推動(dòng)著混沌密碼技術(shù)向前發(fā)展。而隨著混沌密碼分析技術(shù)的發(fā)展，現(xiàn)有的混沌密碼設(shè)計(jì)水平在不斷提高和改進(jìn)，對(duì)混沌密碼算法的分析和破譯難度也相應(yīng)增大。然而，仍然存在一些混沌加密算法在安全性能方面存在不足，難以抵御常見(jiàn)的密碼攻擊方法。

文獻(xiàn)[15]采用“置換-擴(kuò)散”算法結(jié)構(gòu)，提出了一種基于Zigzag變換與混沌的彩色圖像加密算法，同時(shí)給出了一些數(shù)據(jù)分析結(jié)果，并聲稱(chēng)能夠抵御各種常見(jiàn)攻擊。然而，本文經(jīng)過(guò)分析發(fā)現(xiàn)，該圖像加密算法存在以下安全缺陷：(1) 原算法不論是置換還是擴(kuò)散過(guò)程均與明文圖像無(wú)關(guān)；(2) 原算法的全局置換和局部置換均為純像素位置置換；(3) 原算法的擴(kuò)散加密過(guò)于簡(jiǎn)單，且存在等效密鑰。因此，針對(duì)該算法的安全缺陷，本文提出采用選擇明文攻擊的方法對(duì)其進(jìn)行密碼分析。

1 算法描述

1.1 Zigzag變換

Zigzag變換[16]是一種常見(jiàn)的元素位置置換方法。以圖1所示的4×4的矩陣的Zigzag變換過(guò)程進(jìn)行說(shuō)明，其中A和B分別為Zigzag變換前后的矩陣。其變換過(guò)程為：首先，從左下角的13開(kāi)始，按照Z(yǔ)igzag路徑逐一遍歷矩陣中所有元素，由此得到一個(gè)一維序列Z；然后，將一維序列Z由逆序并按照光柵掃描順序轉(zhuǎn)換為二維矩陣B。原算法中采用了擴(kuò)展的Zigzag變換，其實(shí)質(zhì)亦為純?cè)匚恢玫闹脫Q方法[16]。

圖1 Zigzag變換過(guò)程圖

1.2 三維Logistic混沌映射

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

(1)

式中:狀態(tài)變量x,y,z∈(0,1)，λ、β、α為控制參數(shù)。當(dāng)控制參數(shù)滿(mǎn)足λ∈(3.53,3.81)、β∈(0,0.022)、α∈(0,015)時(shí)，三維Logistic映射處于混沌狀態(tài)。

1.3 原算法描述

根據(jù)文獻(xiàn)[15]，原算法的描述如下：

(1) 密鑰參數(shù)。原算法中共有6個(gè)密鑰參數(shù)(λ,β,α,x0,y0,z0)，其中x0、y0、z0為三維Logisitc混沌映射的3個(gè)初始值。

(2) 加密過(guò)程。加密算法包括全局置換、局部置換和異或擴(kuò)散三個(gè)加密步驟。首先，利用Zigzag變換對(duì)彩色圖像的所有像素位置進(jìn)行全局置換；接著，對(duì)預(yù)處理后的圖像的R、G、B通道分別進(jìn)行像素位置的置換；最后，利用三維Logisitc混沌映射產(chǎn)生的掩模圖像對(duì)置換后的圖像按比特異或進(jìn)行擴(kuò)散加密，得到密文圖像。原算法的整體框圖如圖2所示。對(duì)于尺寸為H×W(高×寬)的明文彩色圖像I，下面給出其加密過(guò)程描述。

圖2 原加密算法整體框圖

第1步 全局置換。首先，彩色明文圖像I的R、G、B三個(gè)通道分別為IR、IG、IB，尺寸均為H×W。將IR、IG、IB以列不變且按行依次連接的形式，預(yù)處理得到一個(gè)尺寸為3H×W的矩陣，記為IY。

接著，利用擴(kuò)展Zigzag變換對(duì)IY的像素位置進(jìn)行置換，得到相同尺寸的置換矩陣I′Y。

最后，將尺寸為3H×W的矩陣I′Y分解為3個(gè)尺寸為H×W的二維矩陣，分別記為I′YR、I′YG、I′YB。

第2步 局部置換。利用擴(kuò)展Zigzag變換分別對(duì)I′YR、I′YG、I′YB進(jìn)行置換，置換后得到IZR、IZG、IZB。與第1步中對(duì)H×W×3個(gè)像素進(jìn)行位置置換不同，此步驟中分別對(duì)R、G、B三個(gè)通道內(nèi)的H×W個(gè)像素進(jìn)行置換，因此稱(chēng)之為局部置換。

第3步 異或擴(kuò)散。首先，輸入密鑰參數(shù)，產(chǎn)生混沌偽隨機(jī)序列。即選取三維Logistic混沌映射的控制參數(shù)為λ、β、α和初始值為x0、y0、z0，根據(jù)式(1)，迭代W×H次，得到如下3個(gè)實(shí)數(shù)混沌序列：

(2)

式中：i=1,2,…,H×W，xi,yi,zi∈(0,1)?？紤]到計(jì)算機(jī)的有限精度，每個(gè)混沌序列值均取16位有效值，得：

(3)

式中：j=1,2,…,16，m、n、p為比特?cái)?shù)據(jù)位。

然后，選取混沌序列值中的第7～12數(shù)據(jù)位，采用下面的方法生成6個(gè)新的整數(shù)序列：

(4)

式中：i=1,2,…,H×W。分別將這6個(gè)整數(shù)序列x1i、x2i、y1i、y2i、z1i,z2i對(duì)256求余，得到6個(gè)用于加密的掩模序列X1,X2,Y1,Y2,Z1,Z2∈[0,255]。

接著，分別將掩模序列X1、X2、Y1、Y2、Z1、Z2轉(zhuǎn)換成尺寸為H×W的二維掩模矩陣JX1、JX2、JY1、JY2、JZ1、JZ2。

最后，利用這6個(gè)掩模矩陣分別對(duì)置換圖像的3個(gè)通道進(jìn)行按比特異或擴(kuò)散加密，得：

(5)

式中：“⊕”為按比特異或操作，CR、CG、CB為最終密文圖像C的3個(gè)通道。

(3) 解密過(guò)程。解密則是加密的逆過(guò)程。與加密過(guò)程不同的是，首先利用混沌序列進(jìn)行反擴(kuò)散解密，進(jìn)而利用Zigzag變換進(jìn)行兩次反置換解密恢復(fù)出原始明文圖像。

2 密碼分析和破譯

在本節(jié)中，首先對(duì)原算法存在的安全缺陷進(jìn)行分析，進(jìn)而提出基于選擇明文攻擊的破譯方法。

2.1 原算法的安全缺陷分析

根據(jù)現(xiàn)代密碼學(xué)的基本假設(shè)[18]，對(duì)于攻擊者來(lái)說(shuō)，加密算法是完全公開(kāi)的，只有密鑰未知。換言之，加密算法的安全性完全決定于密鑰。常用的四種密碼攻擊方法如表1所示。

表1 常見(jiàn)的四種密碼攻擊方法

一個(gè)安全的密碼系統(tǒng)應(yīng)當(dāng)可以抵御表1中所有類(lèi)型的攻擊，假如無(wú)法抵抗其中的任何一種攻擊方法，那么此密碼系統(tǒng)是不安全的。因此，從密碼分析的角度看，原算法存在如下的安全缺陷：

(1) 原算法不論是置換還是擴(kuò)散過(guò)程均與明文圖像無(wú)關(guān)。在密鑰給定的情況下，對(duì)于不同的明文圖像，置換和擴(kuò)散過(guò)程中所采用的加密序列是固定不變的。實(shí)際上，這些加密序列可視作為算法的等效密鑰。即使攻擊者完全不知道密鑰信息，僅利用這些等效密鑰也可破譯原算法。此外，這種與明文圖像無(wú)關(guān)的加密算法往往難以抵御已知明文攻擊和選擇明文攻擊。

(2) 原算法的全局置換和局部置換均為純像素位置置換。原算法先后兩次采用Zigzag變換對(duì)彩色圖像進(jìn)行了置換操作，理論分析和實(shí)驗(yàn)仿真表明此方法有效破壞了原始圖像相鄰像素的相關(guān)性。然而，這兩次置換均為純像素位置置換，并未改變像素值，即置換前后的圖像統(tǒng)計(jì)直方圖完全一致。因而原算法容易受到統(tǒng)計(jì)分析的攻擊。

(3) 原算法的擴(kuò)散加密僅采用按比特異或操作。擴(kuò)散是確保加密算法安全的重要部件。然而，原算法采用按比特異或的方式進(jìn)行擴(kuò)散加密，既無(wú)非線(xiàn)性運(yùn)算也無(wú)反饋加密機(jī)制，導(dǎo)致其擴(kuò)散部分很容易被破譯。

鑒于此，下文將介紹針對(duì)原算法的選擇明文攻擊方法。

2.2 選擇明文攻擊方法

根據(jù)表1，在選擇明文攻擊的假設(shè)下，密碼攻擊者可以臨時(shí)使用加密機(jī)，選擇任意有利于破譯的明文，并獲得相應(yīng)的密文。對(duì)于“置換-擴(kuò)散”結(jié)構(gòu)的圖像加密算法[15]，基于選擇明文攻擊的基本分析思路為：首先，選取像素值全部相同的特殊明文圖像使得置換過(guò)程無(wú)效，從而破譯出等效的擴(kuò)散密鑰；然后，選取一些特殊的明文圖像以及獲得相應(yīng)的密文圖像求得等效的置換密鑰?；谶@個(gè)分析思路，本文所采取的選擇明文攻擊方法的破譯步驟為：

(1) 選取1幅像素值全為0的明文圖像及得到相應(yīng)的密文圖像獲取等效擴(kuò)散密鑰。

根據(jù)圖1，當(dāng)輸入的明文圖像的像素值全為0時(shí)，經(jīng)過(guò)兩次Zigzag變換的置換圖像的像素值也全為0。此時(shí)，算法將退化為唯擴(kuò)散加密過(guò)程。所以，根據(jù)式(5)，得像素值全為0的明文圖像I0對(duì)應(yīng)的密文圖像C0與6個(gè)混沌掩模矩陣的關(guān)系為：

(6)

(2) 選取一些特定的選擇明文圖像及得到相應(yīng)的密文圖像獲取等效置換密鑰。

在獲得了等效的擴(kuò)散密鑰后，原算法將退化為唯置換加密算法。根據(jù)文獻(xiàn)[19-20]的分析結(jié)果，唯置換加密算法是不安全的，無(wú)法抵御選擇明文攻擊。且對(duì)于8比特的圖像，選取「log256(L)?幅特定的選擇明文圖像及其對(duì)應(yīng)的密文圖像即可破譯唯置換加密算法，其中，“「·?”表示向下取整，L是圖像的像素個(gè)數(shù)。

對(duì)于唯置換加密算法的破譯過(guò)程，以圖像尺寸為4×4的簡(jiǎn)單例子進(jìn)行說(shuō)明。選取一幅像素值全部不等且由小到大的特殊明文圖像為：

根據(jù)選擇明文攻擊的條件，臨時(shí)使用加密機(jī)，可獲得對(duì)應(yīng)的密文圖像。由于唯置換加密過(guò)程僅改變圖像像素的位置，則不妨假設(shè)唯置換后的密文圖像為：

當(dāng)置換過(guò)程與明文圖像無(wú)關(guān)時(shí)，輸入不同的明文圖像，唯置換過(guò)程是固定的。因此，根據(jù)選擇明文圖像P和對(duì)應(yīng)的密文圖像C，即可求得所有像素置換前后的對(duì)應(yīng)關(guān)系。例如，明文圖像P的第1行第1列的像素置換后對(duì)應(yīng)密文圖像C的第3行第2列的像素。事實(shí)上，所有像素置換前后的對(duì)應(yīng)關(guān)系即為等效的置換密鑰，記為EKP。

當(dāng)然，由于8比特圖像每個(gè)像素的取值范圍為0到255，當(dāng)圖像像素個(gè)數(shù)超過(guò)256時(shí)顯然無(wú)法僅采用一幅選擇明文圖像進(jìn)行破譯。針對(duì)這種情況，再以256×256的8比特灰度圖像為例，說(shuō)明唯置換的分析過(guò)程。虛構(gòu)一幅特殊的明文圖像，其像素值全部不等且由小到大依次排列，表示為：

經(jīng)過(guò)唯置換加密后得到的密文圖像記為Cv，那么根據(jù)Pv和Cv即可獲取等效的置換密鑰EKP。然而，受限于8比特圖像像素取值范圍，這樣的圖像是不存在的。為此，采用下面的方面將這幅虛構(gòu)的圖像Pv分解為2幅可構(gòu)建的8比特圖像P1和P2，分解方法為：

Pv=256×P2+P1

(7)

根據(jù)式(7)，得到的P1和P2分別為：

根據(jù)選擇明文攻擊，分別利用加密機(jī)獲得與P1和P2對(duì)應(yīng)的密文圖像C1和C2，進(jìn)而合并為與Pv對(duì)應(yīng)的虛構(gòu)密文圖像Cv，表示為：

256×C2+C1=Cv

(8)

此時(shí)，比較Pv和Cv里所有像素的值即可獲取等效的置換密鑰EKP。

一般地，對(duì)于尺寸為H×W的彩色圖像，由于其總共有3HW個(gè)取值為0到255的像素，因此根據(jù)上面方法破譯唯置換過(guò)程所需的選擇明文圖像數(shù)量為「log256(3HW)?。

(3) 利用等效的擴(kuò)散密鑰和置換密鑰，對(duì)密文圖像破譯得到原始明文圖像。

首先，利用第(1)步所獲得的等效擴(kuò)散密鑰EKD，由密文圖像的CR、CG、CB破譯得到唯置換圖像的IZR、IZG、IZB。

接著，利用第(2)步所獲得的等效置換密鑰EKP，由置換圖像的IZR、IZG、IZB破譯得到原始明文圖像的IR、IG、IB，亦即完成算法的破譯。

因此，原算法無(wú)法抵御選擇明文攻擊，且攻擊所需的數(shù)據(jù)復(fù)雜度為O(「log256(3HW)?+1)。

3 算法破譯實(shí)驗(yàn)

為了驗(yàn)證所提出的攻擊方法的有效性，選取圖像尺寸為256×256的RGB彩色圖像“Lena”進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)硬件平臺(tái)為一臺(tái)PC，處理器為Intel Core i5，主頻為3.2 GHz，內(nèi)存大小為8 GB。軟件環(huán)境為Windows 7操作系統(tǒng)上運(yùn)行MATLAB R2016a。

首先，根據(jù)第2.2節(jié)的第(1)步，選取一幅像素值全為0的明文圖像并得到相應(yīng)的密文圖像，分別如圖3(a)和圖3(b)所示。其中，圖3(b)即為等效擴(kuò)散密鑰EKD。

(a) 全0明文圖像 (b) 對(duì)應(yīng)的密文圖像圖3 全0明文圖像及其對(duì)應(yīng)的密文圖像

然后，利用等效擴(kuò)散密鑰EKD，將“Lena”密文圖像恢復(fù)為唯置換的圖像?！癓ena”密文圖像和恢復(fù)的置換圖像及其相應(yīng)的直方圖如圖4所示。

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

(c) 恢復(fù)的置換圖像 (d) 置換圖像R通道的直方圖圖4 “Lena”密文圖像和恢復(fù)的置換圖像及其直方圖

接著，根據(jù)第2.2節(jié)的第(2)步，選取如圖5(a)-(c)所示的3幅明文圖像P1、P2、P3，根據(jù)選擇明文攻擊的條件，分別得到如圖6(a)-(c)所示的相應(yīng)的3幅密文圖像C1、C2、C3。

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

(a) 密文圖像C1 (b) 密文圖像C2 (c) 密文圖像C3圖6 與圖5分別對(duì)應(yīng)的3幅密文圖像

根據(jù)式(7)-式(8)，分別將圖5(a)-(c)所示的3幅明文圖像和圖6(a)-(c)所示的相應(yīng)的3幅密文圖像進(jìn)行如下的合并運(yùn)算操作：

Pv=2562×P3+256×P2+P1

Cv=2562×C3+256×C2+C1

進(jìn)而比較Pv和Cv里所有元素的值即可獲取等效置換密鑰EKP。

最后，根據(jù)第2.2節(jié)的第(3)步，破譯還原出原始“Lena”圖像及其直方圖分別如圖7(a)-(b)所示。

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

從圖4(b)、圖4(d)和圖7(b)可以看出，雖然密文圖像的直方圖呈現(xiàn)類(lèi)噪聲分布特性，但置換圖像和破譯圖像的直方圖特性完全一致，從中也可以看出唯置換加密過(guò)程并未改變圖像的統(tǒng)計(jì)信息。對(duì)于尺寸為256×256的彩色圖像，實(shí)現(xiàn)破譯所需的數(shù)據(jù)復(fù)雜度僅為O(「(log2563WH)?+1)=O(4)，運(yùn)行時(shí)間約為1.25 s。

實(shí)驗(yàn)結(jié)果表明，本文所提的選擇明文攻擊方法可以有效破譯原算法，而且破譯所需的時(shí)間和數(shù)據(jù)復(fù)雜度都比較低。

4 結(jié) 語(yǔ)

本文針對(duì)一種基于Zigzag變換與混沌的彩色圖像加密方案進(jìn)行了安全性能分析。經(jīng)過(guò)密碼分析發(fā)現(xiàn)，原算法存在安全缺陷，置換和擴(kuò)散過(guò)程均與明文無(wú)關(guān)，算法存在等效密鑰。因此，本文提出了基于選擇明文攻擊分別獲取等效擴(kuò)散密鑰和等效置換密鑰，從而實(shí)現(xiàn)了對(duì)原算法的破譯。理論分析和實(shí)驗(yàn)仿真表明，原算法是不安全的，無(wú)法抵御選擇明文攻擊。且對(duì)于圖像尺寸為H×W的彩色圖像，破譯的數(shù)據(jù)復(fù)雜度為O(「(log2563HW)?+1)。本文的密碼分析對(duì)于混沌密碼設(shè)計(jì)者提高算法的安全性能具有一定的參考作用。