圖像混沌加密算法的密碼破譯與算法改進

韓 鳳 英

(空軍航空維修技術(shù)學(xué)院　湖南 長沙410014 )

?

圖像混沌加密算法的密碼破譯與算法改進

韓 鳳 英

(空軍航空維修技術(shù)學(xué)院湖南 長沙410014 )

針對文獻中提出的一種基于位置和像素值變換的圖像混沌加密新算法，分析算法的缺陷并提出對該算法的一種選擇明文攻擊方法，展示明文圖像可以不需要原始密鑰而能準(zhǔn)確地從密文圖像恢復(fù)出來，因而該算法不具備在網(wǎng)絡(luò)通信中應(yīng)用所需的足夠安全性，并提出一種更加安全的改進算法。理論分析和實驗結(jié)果表明：改進算法不僅克服了原算法的那些缺陷，而且具有更好的密碼學(xué)性能。

圖像加密混沌系統(tǒng)密碼分析選擇明文攻擊

0　引　言

數(shù)字圖像作為一種重要數(shù)字媒體信息在當(dāng)今得到了廣泛的應(yīng)用。隨著網(wǎng)絡(luò)通信技術(shù)的迅猛發(fā)展，數(shù)字圖像在信息交換、存儲和通信中使用頻繁。然而，信息存儲和通信環(huán)節(jié)存在的諸多不安全因素對許多重要信息構(gòu)成威脅。為了保證軍事信息、政府機密文件、商業(yè)秘密、個人隱私等重要信息的安全，通常會對信息進行加密處理。而圖像具有數(shù)據(jù)量大、相鄰像素相關(guān)性強、數(shù)據(jù)冗余多等特點[1，2]，不適合采用傳統(tǒng)的加密方式。而混沌系統(tǒng)具有對初始條件的敏感性，參數(shù)可控性、偽隨機性，且在一定的周期內(nèi)具有唯一性，所以適合于數(shù)字圖像加密。許多專家學(xué)者提出了很多基于混沌系統(tǒng)的圖像加密算法[3-6]，而對于基于混沌系統(tǒng)的圖像加密算法的安全性分析研究較少。如果對于存在安全隱患的加密算法，不加以指出，應(yīng)用到工程實踐中，將會帶來安全隱患，造成不可估量的影響。本文研究了文獻[11]中所提出的基于位置和灰度變換的混沌圖像置亂算法，發(fā)現(xiàn)了算法中存在的安全漏洞，并利用選擇明文攻擊，成功地破解了該算法密碼。并基于該算法，提出一種改進算法，改進后的算法克服了原算法的缺陷，安全性得到了提高。實驗證明，本文改進的算法具有更好的密碼學(xué)性能。

1　原密碼算法的分析與破解

1.1原算法簡述

文獻[11]中采用如式(1)所示的經(jīng)典的混沌系統(tǒng)Logistic映射作為混沌加密系統(tǒng)。

xn+1=μxn(1-xn)

(1)

其中,x為系統(tǒng)變量，μ為系統(tǒng)參數(shù)，當(dāng)u=4時，式(1)所生成的序列在區(qū)間(0，1)上具有混沌遍歷性。在文獻[11]中，以x0為式(1)的初值，生成混沌密鑰序列。

用x表示原始明文圖像加的像素點的灰度值，其中0≤x≤255。用y表示用式(1)生成的混沌序列中的某個狀態(tài)值經(jīng)過處理后得到整數(shù)值，其中0≤y≤255。文獻[11]利用式(2)對原始圖像即明文圖像的像素值x進行加密變換后得到密文像素值z：

z=mod(x+y,256)

(2)

式(2)中mod()表示取模，由式(2)可以推導(dǎo)出式(3)所示的像素值解密公式。

x=mod(z-y+256,256)

(3)

用數(shù)組A表示圖像的灰度圖像矩陣，A(i，j)表示第i行第j列處的像素點灰度值。若圖像的大小為M×N，那么i=1，2，…，M，j=1，2，…，N。對圖像像素按行優(yōu)先次序依次掃描，設(shè)像素的序號用k表示，k=1，2，…，M×N。則由像素序號k計算該像素的行號i、列號j的公式為：

(4)

其中，|-x-|表示取大于或等于x的最小整數(shù)。利用式(1)生成的混沌序列在文獻[11]中有兩個用途：其一是利用狀態(tài)值x來產(chǎn)生一個[2，M×N]范圍的整數(shù)k，k值就是當(dāng)前欲移動的像素原所在位置的序號；其二是利用狀態(tài)值x來產(chǎn)生另一個[0，255]范圍的整數(shù)y，y值用來作為像素值替代變換的密鑰。設(shè)Visited用來標(biāo)識像素是否已經(jīng)移動，初值為0，表示沒有移動，若待加密的原始明文圖像的大小為M×N，那么Visited的大小為M×N；同時設(shè)置一個count變量用于記錄已經(jīng)移動的像素數(shù)目。每移動一個像素時，將相應(yīng)位置的Visited數(shù)組元素值修改為1，同時count值增1。每當(dāng)一個像素值移到新位置后，立刻用式(2)對其像素值進行替代加密。

1.2原算法密碼的破譯

一個安全的密碼算法必須能夠抵抗選擇明(密)文攻擊、選擇明文攻擊、已知明文攻擊、唯密文攻擊。下面通過選擇明文攻擊來破解文獻[11]中所提出的加密算法。

因為在原算法中，灰度變換密鑰完全由混沌序列的初始密鑰而決定，與待加密的圖像無關(guān)；而位置置亂也完全由混沌序列密鑰決定，也與待加密的明文圖像無關(guān)。所以利用混沌序列對任何圖像進行加密，替代和置亂規(guī)律都是相同的。所以只要能夠選擇明文攻擊，計算出混沌序列，進而可以解密出任何利用該混沌序列進行加密的圖像。

文獻[11]中的算法位置變換如式(5)所示，像素值變換如式(6)所示：

B(1)=A(k1)B(ki)=A(ki+1)B(kM×N-1)=A(1)

(5)

i=1，2，…，M×N-2

C(n)=mod(B(n)+yn,256)n=1，2，…，M×N

(6)其中,A(n)表示原始明文圖像、B(n)表示位置變化圖像、C(n)分最終密文圖像。n表示按行優(yōu)先次序一維化后所得的序列值。

設(shè)截獲了一個用文獻[11]算法加密的2×3大小的密文圖像，其像素按行優(yōu)先次序一維化的數(shù)組為C={119，124,57，10，110，228}。假設(shè)對應(yīng)于選擇明文數(shù)組Ap={0，0，0，0，0，0}，得到的密文數(shù)組為Cp={110，135，2，255，12，254}；又對應(yīng)于選擇明文數(shù)組Aq={1，2，3，4，5，6}，得到的密文數(shù)組為Cq={137，8，0，17，4}。要求破譯出密文圖像C所對應(yīng)的明文圖像A。

(1) 因Ap元素全是零，故Bp={0，0，0，0，0，0}；所以，Y=Cp={110，135，2，255，12，254}。

(2) 由Cq={115，139，8，0，15，0}和Y= {110，135，2，255，12，254}，可以求出破譯的中間版本：

Bq={mod(Cq(n)-yn+256，256)，n=1，2，…，6}={5，4，6，1，3，2}。 因為Bq(1) =Aq(5)，所以k1=5；因為Bq(k1) =Bq(5) =Aq(3)，所以k2=3； 因為Bq(k2) =Bq(3) =Aq(6)，所以k3=6； 因為Bq(k3) =Bq(6) =Aq(2)，所以k4=2；因為Bq(k4) =Bq(2) =Aq(4)，所以k5=4；而Bq(k5) =Aq(1)。故，K={5，3，6，2，4}。

(3) 解密C，由C={119，124，57，10，110，228}和Y= {110，135，2，255，12，254}，可求得：B={mod(C(n)-yn+256，256),n=1，2，…，6}={9，245，55，11，98，230}；再根據(jù)K={5，3，6，2，4}，因為k1=5，B(1) =A(k1)，所以A(5)=9；因為k2=3，B(k1)=A(k2),所以A(3)=B(5)=98；因為k3=6，B(k2)=A(k3),所以A(6)=B(3)=55；因為k4=2，B(k3)=A(k4),所以A(2)=B(6)=230；因為k5=4，B(k4)=A(k5)，所以A(4)=B(2)=245；因為B(k5)=A(1)，所以A(1)=B(4)=11。于是得到解密出來的圖像數(shù)組為：A={11，230，98，245，9，55}。

由此可知，通過兩組選擇的明—密文對進行密碼分析，就能破譯出原算法中等價的中間密鑰序列；而等價的中間密鑰序列與被加密圖像內(nèi)容無關(guān)，所以文獻[11]的密碼算法不能抵御選擇明文攻擊。

2　改進算法

原算法具有如下優(yōu)點：置亂與替代結(jié)構(gòu)清晰、簡單，像素位置置亂過程確保了每個像素都發(fā)生位置移動且只移動一次，因此，不動點數(shù)目為0，置亂效率高。但存在如下缺陷：圖像加密算法中的像素值替換與像素位置變化兩個環(huán)節(jié)都與原始明文圖像無關(guān)，所以算法不能抵抗選擇明(密)文攻擊。此外，算法中關(guān)于像素值替代加密的公式所具有的密碼學(xué)性能不優(yōu)，一是針對式(2)利用已知的明—密文對易于破解出替代密鑰序列Y；二是該算法產(chǎn)生的密文在分布性、相鄰像素的相關(guān)性、對明文的敏感性和密文信息熵等方面尚都存在很大的優(yōu)化空間?；诖?，本文提出一種既能抵抗選擇明(密)文攻擊，又具有更優(yōu)密碼學(xué)性能的改進算法。

2.1加密算法

設(shè)像素為M行、N列的明文灰度圖像矩陣為A，其像素總數(shù)為M×N。算法原始密鑰集為{x0，y0，N0，C0，Y0}，其中，雙精度實數(shù)x0和y0作為Logistic系統(tǒng)的兩種初始狀態(tài)值，N0是一個500以上的整數(shù)，C0和Y0都是[0，255]范圍的整數(shù)。改進算法將像素位置置亂與像素值替代兩類操作分開，位置置亂過程的基本思想是：由x0生成與明文相關(guān)的混沌序列，再由混沌序列隨機產(chǎn)生范圍在[1，M×N]之內(nèi)的整數(shù)km，然后依次將序號為m(m=1，2，…，M×N)的像素移動到序號為km的位置(km≠m)。像素值替代加密的密鑰由y0生成的混沌序列產(chǎn)生。

算法輸入：明文圖像矩陣AM×N，初始密鑰{x0，y0，N0，C0，Y0}；

算法輸出：密文圖像矩陣CM×N。

像素位置置亂算法的具體步驟描述如下：

1) 設(shè)置一個長度為M×N的一維標(biāo)志數(shù)組F，并初始化：F(i)=0，i=1，2，…，M×N。 令：m=1。

2) 求明文圖像A全部元素按位異或運算的值s；并按s值修改Logistic系統(tǒng)的初始值x0：x0=(s/256)×x0。使x0與圖像內(nèi)容相關(guān)。

3) 由式(1)生成新的混沌序列值x，根據(jù)x的值計算出t值和k值，其中t=round(x×1012)，k=mod(t，M×N)+1。

4) 若F(k)為1(表示整數(shù)k已經(jīng)產(chǎn)生過)或k等于m，則轉(zhuǎn)到步驟3)繼續(xù)執(zhí)行，直至產(chǎn)生的k滿足：F(k)值是0，且k不等于m。

5) 將A中序號為m的元素移動到序號為k的位置：B(row，col)=A(i，j)，其中，(i，j)是A中第m個像素的行列號，(row，col)是B中第k個像素的行列號；同時置F(k)值為1(表示k已經(jīng)產(chǎn)生過)。

6) 若m≤M×N，則轉(zhuǎn)到步驟3)，繼續(xù)循環(huán)執(zhí)行步驟3)到步驟5)。

像素值替代加密算法的具體步驟描述如下：

1) 初始化：選取經(jīng)過替代變化后的加密圖像的第M和第N個像素點的像素值分另賦給C0和Y0，令C1=C0，Y1=Y0，m=1。

2) 混沌系統(tǒng)式(1)從初值y0開始迭代(N0+M×N)次，對生成的y序列舍棄前N0個值，取后面長度為M×N的子序列，并將子序列的實數(shù)值按式(7)轉(zhuǎn)換成整數(shù)序列(1≤y(n)≤255)：

y(n)=mod(round(y(n)×1012),255)+1

n=1，2，…，M×N-1

(7)

3) 將m值轉(zhuǎn)換為相應(yīng)的行、列號i和j，先按式(8)對第m個像素進行替代加密，然后按式(9)修改C1、Y1、m的值。

C(i,j)=mod(B(i,j)⊕y(m)+C1⊕Y1,256)

(8)

C1=C(i,j),Y1=y(m),m=m+1

(9)

4) 若m≤M×N，則轉(zhuǎn)到步驟3)繼續(xù)循環(huán)執(zhí)行； 否則，輸出密文矩陣C，算法結(jié)束。

2.2解密算法

算法輸入：密文圖像矩陣CM×N，初始密鑰集{x0，y0，N0，C0，Y0}；

算法輸出：明文圖像矩陣AM×N。

首先，對密文像素值進行反替代操作，操作步驟與前面的密文像素值替代操作類似，只是將式(8)改為下列求解B(i，j)的式(10)：

B(i,j)=(mod(C(i,j)-C1⊕Y1+256,256))⊕y(m))

(10)

然后，對密文像素的位置進行反置亂操作，操作步驟也與前面的密文像素位置的置亂操作類似，只是將公式B(row，col)=A(i，j)改為求解A(i，j)的公式：A(i，j)=B(row，col)。

3　仿真實驗與安全性分析

在仿真實驗中采用標(biāo)準(zhǔn)Lena圖像(256×256×8位)，用Matlab 7.1對算法實驗進行仿真測試。設(shè)混沌序列的初值及參數(shù)值為：C0=68，Y0=24，N0=600，x0=0.543，y0=0.403。

3.1密鑰空間與抗攻擊性能分析

改進算法相比原算法，初始密鑰增加了4個(C0、Y0、N0和y0)。假設(shè)N0可能取值個數(shù)為500，C0、Y0可能取值個數(shù)各為255，雙精度實數(shù)x0和y0各為15位小數(shù)，則密鑰空間為500×255×255×1015×1015≈2125。如此大的密鑰空間，足以抵抗窮舉攻擊。

改進算法所產(chǎn)生的置亂序列{km|m=1，2，…，M×N}與被加密圖像內(nèi)容相關(guān)，這將使選擇明(密)文攻擊方法失效。因為，改進算法中，待解密的密文圖像的變換序列與明文圖像的變換序列不相同，所以即便用選擇明文攻擊得出等價的位置變換密鑰序列，也不可能破解密文圖像。另外，改進了像素置亂方式和像素值替代加密方法。特別地，在式(8)中通過引入?yún)?shù)C1(代表前一點的密文)和Y1(代表前一個密鑰)，一方面使加密過程產(chǎn)生信息擴散機制。另一方面，使同一公式中包含了兩個密鑰y(m)和Y1，這樣，攻擊者即使用已知的B(i，j)-C(i，j)數(shù)據(jù)對也無法唯一確定y(m)和Y1。故不能用選擇明(密)文攻擊法破解y(m)序列，也說明本文的改進算法具有抵抗選擇明(密)文攻擊的能力。

3.2加密效果測試

明文圖像為圖1(a)，改進算法的加密圖像為圖1(b)，可以看出加密后的圖像雜亂無章，看不出任何明文圖像內(nèi)容，圖像類似于噪聲。

圖1　明文圖像和加密圖像

明文圖像和密文圖像對應(yīng)的直方圖分別如圖2所示。由(a)可知，明文圖像的像素值在[0,255]的區(qū)間中分布非常不均勻；由(b)可知，文獻[11]的算法生成的加密圖的直方圖比(a)稍均勻，但是還不太理想； 由(c)可知本文的改進算法生成的加密圖的直方圖分布非常均勻。因此，改進算法具有抵抗統(tǒng)計分析攻擊的能力。

(a) 明文圖像的直方圖

(b) 原算法加密圖像的直方圖

(c) 改進算法加密圖像的直方圖圖2　明文和密文圖像的直方圖

3.3相關(guān)性測試

相鄰像素之間的相關(guān)程度可以用相鄰像素之間的相關(guān)系數(shù)來衡量。相鄰像素之間的相關(guān)系數(shù)計算如下：

(11)

(12)

(13)

(14)

其中，x和y表示圖像中相鄰2個像素的像素值，γxy為圖像相鄰兩個像素的相關(guān)系數(shù)。選擇水平、垂直、對角三個方向的全部相鄰像素，采用式(14)計算出相關(guān)系數(shù)。如表1所示，原始明文圖像相鄰像素點具有高相關(guān)性，其相關(guān)系數(shù)非常接近1；本文所設(shè)計的加密算法生成的密文圖像相鄰像素幾乎不相關(guān)，相關(guān)性接近于0；而其他幾個文獻中的相鄰像素的相關(guān)性也高于采用本文所設(shè)計加密算法得到的加密圖像的相關(guān)性。

表1　明文和密文圖像中相鄰像素的相關(guān)系數(shù)

3.4敏感性測試

如果明文或密鑰的微小變化就引起密文的變化越大，則說明算法的敏感性越強，也說明算法的抗差分攻擊能力越強。度量算法的敏感性通常用NPCR(可用像素改變率)和UACI(歸一化平均改變強度)兩個參數(shù)，可以采用文獻[10]中的方法計算。NPCR與UACI的計算都是在明文圖像只改變了一個像素時，密文圖像的改變程度。對8位灰度圖像，這兩個值的理想期望值是NPCR=99.6094%，UACI= 33.4635%。

由文獻[11]的算法可知，該算法對明文是不敏感的，因為明文中一個像素發(fā)生變化，只可能引起密文中一個像素變化。在本實驗中選擇5組明文圖像來驗證改進算法的明密文敏感性。每組第1幅明文圖像是原始Lena圖像，第2幅明文圖像是將原始Lena圖像其中一個像素的值增加1，這個被改變的像素所在位置包含了最前、中間、末尾三種極端情況。根據(jù)文獻[10]中的計算方法計算出NPCR和UACI值，見表2。由表2的結(jié)果可知，這兩個值都非常接近理想期望值，這表明密文對明文高度敏感性。

表2　幾組密文圖像之間的NPCR和UACI值

為驗證密文對初始密鑰的敏感性，我們分別對兩組密鑰中的x0與y0改變10-10(其他密鑰不變)，然后用兩組密鑰分別加密同一幅Lena圖像。當(dāng)僅有x0改變10-10時，所得兩幅密文圖像的NPCR和UACI值分別是0.9959和0.3341，圖3(a)給出了兩幅密文圖像前100個像素的差值曲線。當(dāng)僅有y0改變10-10時，所得兩幅密文圖像的NPCR和UACI值分別是0.9959和0.3351，圖3(b)給出了兩幅密文圖像前100個像素的差值曲線。可見，密文對密鑰x0和y0是充分敏感的。進一步的實驗也證實了密文對密鑰C0、Y0和N0也充分敏感。

圖3　密文對密鑰的敏感性測試結(jié)果

4　結(jié)　語

(1) 對文獻[11]提出的混沌圖像加密算法分析了存在的安全缺陷，通過選擇明文攻擊破譯了該算法。

(2) 提出了一種改進型置亂—替代結(jié)構(gòu)圖像混沌加密新算法。使像素位置置亂序列的產(chǎn)生不僅依賴于混沌密鑰，而且與明文相關(guān)；像素值替代變換的加密過程同時引入了密文擴散和雙密鑰參與機制，有效地提高了算法的安全性。

(3) 對改進算法進行了詳盡的實驗測試和安全性分析，證明了改進算法具有很強的抗選擇明(密)文攻擊和窮舉攻擊的性能；而且密文直方圖分布均勻，算法對明密文敏感，加密圖的相鄰像素的相關(guān)系數(shù)近于0。

因此本文提出的改進算法具有更好的密碼學(xué)特性，更適合應(yīng)用在數(shù)字圖像的保密通信及安全存儲中。

[1] 廖曉峰,肖迪,陳勇,等.混沌密碼學(xué)原理及其應(yīng)用[M].北京:科學(xué)出版社，2009:37-39.

[2] Mazloom S，Eftekhari-Moghadam A M.Color image encryption based on Coupled Nonlinear Chaotic Map[J].Chaos,Solitons and Fractals，2009，42(3):1745-1754.

[3] Wang Y,Wong K W,Liao X,et al.A new chaos-based fast image encryption algorithm[J].Applied Soft Computing,2011，11(1):514-522.

[4] Zhang Guochao,Liu Shaohui,Jiang Feng,et al.An improved image compression scheme with an adaptive arameter set in encrypted domain[J].Visual Communications an Image Processing,2013,9(1):1-6.

[5] 謝凱明，鄧家先，陳益剛.基于JPEG2000的圖像聯(lián)合壓縮加密算法[J].計算機應(yīng)用研究，2014，31(12)：3695-3699.

[6] 盧守東,肖芳雄.基于三維混沌系統(tǒng)的通用數(shù)字圖像加密與恢復(fù)算法[J].計算機應(yīng)用與軟件,2013,30(12):87-92.

[7] Zhu Congxu,Liao Chunlong,Deng Xiaoheng.Breaking and improving an image encryption scheme based on total shuffling scheme[J].Nonlinear Dynamics,2013,71(1-2):25-34.

[8] Rhouma Rhouma，Safya Belghith.Cryptanalysis of a new image encryption algorithm based on hyper-chaos[J].Physics Letters A，2008，372(38):5973-5978.

[9] Gao T,Chen Z.A new image encryption algorithm based on hyper-chaos[J].Physics Letters A,2008,372(4) :394-400.

[10] Zhang Guoji,Liu Qing.A novel image encryption method based on total shuffling scheme[J].Optics Communications,2011,284(12):2775-2780.

[11] 王青松，范鐵生.基于位置和灰度變換的混沌圖像置亂算法[J].小型微型計算機系統(tǒng)，2012，33(6):1284-1288.

CODE BREAKING FOR IMAGE CHAOTIC ENCRYPTION ALGORITHM AND ALGORITHM IMPROVEMENT

Han Fengying

(AirForceAeronauticalCollege，Changsha410014,Hunan,China)

Aiming at the new algorithm of image chaotic encryption based on location and pixel gray transformation proposed in the literature,we analysed the flaws of the algorithm and presented an attack method against it by choosing the plaintext,and showed that the plaintext image can be recovered exactly from the cipher image without the need of original key,therefore the algorithm is not secure enough to be applied in network communication,and proposed an improved algorithm which is more secure.Theoretical analysis and experimental results all showed that the improved algorithm can overcome these flaws and has better cryptographic performances as well.

Image encryptionChaotic systemCryptanalysisChoosing plaintext attack

2015-02-09。國家自然科學(xué)基金項目(61073187);湖南省教育廳科研項目(13C995)。韓鳳英，副教授，主研領(lǐng)域：信息安全。

TP309.7

A

10.3969/j.issn.1000-386x.2016.08.065