馬俊明，葉瑞松（汕頭大學(xué)數(shù)學(xué)系　廣東　汕頭　515063）

對“基于改進廣義cat映射的彩色衛(wèi)星圖像加密算法”的安全性分析

馬俊明，葉瑞松
（汕頭大學(xué)數(shù)學(xué)系廣東汕頭515063）

對一種基于改進廣義cat映射的彩色衛(wèi)星圖像加密算法進行安全性分析，并提出相應(yīng)的選擇明文/密文攻擊和已知明文攻擊方法.該算法改造了一般廣義cat映射，通過增加一個非線性項使得一般廣義cat映射具有更好的混沌特性；并利用改進廣義cat映射進行圖像置亂，然后用復(fù)合混沌映射對置亂后的圖像進行擴散運算，實現(xiàn)圖像加密.經(jīng)過理論分析發(fā)現(xiàn)該算法存在兩方面不足.一方面是擴散過程過于簡單，采用簡單的整幅圖像的異或運算；另一方面是采用改進廣義cat的置亂過程與明文無關(guān).這兩方面的不足，使得算法很容易受到破譯.理論和仿真實驗均表明該算法無法抵抗選擇明文/密文攻擊和已知明文攻擊.關(guān)鍵詞混沌映射；圖像加密；選擇明文攻擊；選擇密文攻擊；已知明文攻擊

0　引言

由于圖像具有信息表達直觀、信息量大、相鄰像素的相關(guān)性強、冗余度大及其視覺屬性等特點，使得傳統(tǒng)的對文本信息而設(shè)計的加密算法，如DES，IDEA，RSA，已經(jīng)不再適應(yīng)圖像信息加密的應(yīng)用場合［1］.為了圖像信息安全的應(yīng)用需要，很多信息安全研究的學(xué)者提出了各種各樣的加密新算法，其中基于混沌的圖像加密算法獨占鰲頭，是目前圖像加密研究中最熱門的研究課題.混沌映射具有初值和系統(tǒng)參數(shù)的高度敏感性、混沌序列偽隨機性、軌道遍歷性以及不可預(yù)測性等復(fù)雜特性，因此混沌映射非常適合用于加密系統(tǒng)的置亂和擴散［3］.

一般來說，研究者在設(shè)計基于混沌圖像加密算法時主要使用四種策略.第一種也是最容易實現(xiàn)的策略就是利用混沌映射產(chǎn)生的序列掩蓋圖像像素值［4］.第二種策略一般稱為置亂，即利用混沌映射產(chǎn)生的混沌序列量化生成相應(yīng)的置亂變換，從而改變圖像像素位置而實現(xiàn)加密［5］.第三種策略依賴于混沌映射的迭代次數(shù)，這類策略中經(jīng)常被提起的是Baptista型加密算法［6-7］.第四種策略是將混沌映射和明文圖像聯(lián)系起來，生成加密過程的密鑰流，通常表現(xiàn)為前三種策略的交叉結(jié)合.顯然第四種策略的安全性會比前三種高，但也不一定是安全不可破解的.文獻［8］提出的圖像加密算法充分體現(xiàn)了第四種策略，但發(fā)表不久后就被王興元等人運用選擇明文攻擊成功實現(xiàn)了破譯［9］.實際上，目前圖像加密算法中有很多是基于混沌系統(tǒng)的圖像加密算法，但是對基于混沌的圖像加密的密碼學(xué)理論并未完善.基于混沌系統(tǒng)的圖像加密算法有待進一步做理論上的研究分析，特別對該類加密算法的密碼學(xué)分析很有必要，也很有價值，有助于提高該類算法的安全性、實用性.一些學(xué)者陸續(xù)發(fā)現(xiàn)了基于混沌的圖像加密方案所存在的缺陷，一些基于混沌系統(tǒng)以及置換-擴散結(jié)構(gòu)的圖像加密算法已經(jīng)陸續(xù)遭到破譯［10-15］.這些遭遇破解的加密算法中大部分有這樣一個特征，就是置換過程和擴散過程是相互獨立的，置換過程的密鑰流與明文圖像無關(guān)，而擴散過程的密鑰流雖然與圖像相關(guān)，但是擴散函數(shù)設(shè)計安全性有缺陷，從而使得選擇明文攻擊、已知明文攻擊等密碼分析得以實現(xiàn).

最近，一種基于改進廣義cat映射的圖像加密算法由張新和柏逢明提出［16］.該算法對一般廣義cat映射增加了非線性項，使得一般的廣義cat映射具有更好的混沌特性；并利用改進廣義cat映射進行明文圖像的置亂，然后用復(fù)合混沌映射對置亂后的圖像進行擴散運算，實現(xiàn)圖像加密，達到較好的加密效果.本文將對文獻［16］所構(gòu)造的加密算法進行安全性分析.通過分析，發(fā)現(xiàn)文獻［16］的加密算法的置亂過程與擴散過程相互獨立，并且置亂過程和擴散過程均過于簡單.擴散過程采用簡單的整幅圖像的異或運算；置亂過程雖然采用改進廣義cat映射，但是與明文無關(guān).這兩方面的不足，使得算法很容易受到破譯，無法抵抗選擇明文/密文攻擊以及已知明文攻擊.在已知明文攻擊分析中，還發(fā)現(xiàn)該算法提出的改進cat映射雖然增加非線性項，但是在安全性方面并沒有提高.安全性理論分析結(jié)果表明該算法無法抵抗選擇明文攻擊、選擇密文攻擊及已知明文攻擊，仿真模擬結(jié)果也證實了，在不知道密鑰的情況下，可以對任意一幅密文圖像進行完整的破譯.

1　基于改進廣義cat映射的彩色衛(wèi)星圖像加密算法

文獻［16］的加密算法包括兩部分.首先利用改進廣義cat映射對彩色明文圖像的三個色彩分量分別進行置亂.然后，利用復(fù)合混沌映射對置亂后的圖像進行擴散得到密文圖像.雖然加密算法是針對衛(wèi)星圖像，但是用其它一般的圖像所做的破譯分析，一樣對衛(wèi)星圖像的破譯有效.該算法的具體操作步驟如下.

1.1置亂過程

彩色明文圖像可以用三維矩陣P表示，假設(shè)矩陣大小為N×N×3.在置亂過程中，改進廣義cat映射被用來置亂圖像：

其中（x，y），（x′，y′）分別為置亂前后像素坐標(biāo)，f（x′）=x′2.

Step 1.給定復(fù)合混沌映射（簡稱CCM）：

假設(shè)用于置亂彩色圖像三個顏色分量的三個映射的參數(shù)分別為μ1，μ2，μ3，初始值分別為x1，x2，x3.

Step 2.分別迭代CCM共N×N+d次，得到對應(yīng)序列I1，I2和I3，其中d為給定正整數(shù)，屬于加密密鑰的一部分，其作用是扔掉混沌序列的前d個過渡點，提高序列的混沌特性.

Step 3.利用下述公式生成改進廣義cat映射的控制參數(shù)：

其中i=1，2，3，M可視為密鑰之一.

Step 4.利用（1）和（3）對彩色圖像P的三個色彩分量分別進行置亂，得到置亂圖像CR，CG，CB.

1.2擴散過程

Step 1.分別取序列I1，I2和I3的后面N×N個序列值，構(gòu)成序列Y1，Y2和Y3，如式（4）所示：

Step 2.由式（5）生成擴散過程的偽隨機密鑰流Ki：

Step 3.將密鑰流Ki從上到下，從左到右依次進行排列，得到三個N×N矩陣Xi.置亂圖像通過矩陣Xi進行擴散加密，得到密文圖像的三個分量矩陣：

將矩陣SR，SG，SB進行色彩合成得到彩色加密圖像S.這里也可以先將Xi進行色彩合成X，然后通過S=bitxor（C，X）生成加密圖像，其中C為彩色置亂圖像.后面的寫法是為了行文方便，兩者完全等價.

解密算法和加密算法類似.對于密文圖像，首先使用與加密時相同的密鑰流矩陣執(zhí)行擴散過程的逆過程，然后對反擴散后的圖像矩陣進行反置亂，即可得到原始明文圖像.正如文獻［16］所說，CCM的初始值、映射參數(shù)，M和d構(gòu)成加密算法的全部密鑰，更多具體細節(jié)可以參考該文獻.

2　密碼學(xué)分析

密碼分析學(xué)的主要任務(wù)是研究密碼破譯的理論和技術(shù).根據(jù)Kerchoff原則［1］，一般假設(shè)分析者在分析加密算法時能準確地知道這個加密系統(tǒng)的設(shè)計和運作，充分了解加密和解密算法，但不知道加密者使用的密鑰.本文主要涉及選擇明文攻擊、選擇密文攻擊和已知明文攻擊，具體介紹如下：

（A）選擇明文攻擊：分析者擁有有利于破解算法的選擇明文及其對應(yīng)密文；

（B）選擇密文攻擊：分析者擁有有利于破解算法的選擇密文及其對應(yīng)明文；

（C）已知明文攻擊：分析者擁有足夠多使用同一密鑰加密的密文及其對應(yīng)明文.

2.1選擇明文攻擊

首先選擇像素值全為零的明文圖像P1加密得到對應(yīng)密文圖像S1.由于置亂過程中只改變像素點坐標(biāo)而不改變像素值，故P1置亂后仍為P1.根據(jù)式（6）可得：

S1=bitxor（P1，X）=bitxor（O，X）=X，

其中O為全零矩陣.然后選擇第二幅明文圖像P2進行加密得到S2.P2的三個色彩分量都是由序列1到N×N從上到下從左到右依次排列成N×N矩陣，具體如下：

由式（6）可知P2置亂后的圖像C2為 C2對于破解置亂過程起到關(guān)鍵性作用，因為C2中每一像素點的像素值都可以表示該像素點置亂前坐標(biāo)，即C2（x′，y′）=x+（y-1）N=P2（x，y）.

假設(shè)待破譯密文圖像為S，利用上述得到的兩幅圖像S1和C2進行破譯如下：

Step 1.利用式（6）以及S1得到S對應(yīng)的置亂圖像C：

Step 2.設(shè)明圖像為P.將圖像C，C2，P不同色彩分量從上到下從左到右依次轉(zhuǎn)化成長度為N×N的序列CIR，C2IR，PIR，CIG，C2IG，PIG，CIB，C2IB，PIB，執(zhí)行運算

這里將圖像分成三個分量來處理主要是方便使用Matlab編程實現(xiàn)，上式也可以用P（C2）=C代替.

Step 3.將序列PIR，PIG，PIB恢復(fù)成矩陣形式并合成明文圖像P.

2.2選擇密文攻擊

選擇密文攻擊和選擇明文攻擊類似，但操作步驟有所不同，下面將具體描述選擇密文攻擊.取2.1中兩幅明文圖像作為選擇密文攻擊中的選擇密文圖像S3=P1，S4=P2.設(shè)其對應(yīng)的明文圖像以及置亂圖像分別為P3，P4，C3，C4.令dS=bitxor（S3，S4），dC=bitxor（C3，C4），dP=bitxor（P3，P4），由式（6）及定義可知：

從dP到dC只經(jīng)歷置亂過程，dC每個色彩分量由序列1到N×N從上到下從左到右依次排列成N×N矩陣，易知dP像素值表示其置亂后坐標(biāo).注意dP與2.1節(jié)的C2有所不同，后者是正向置亂，前者是反向置亂.根據(jù)標(biāo)準置亂圖像以及P3可以求出C3，C3（dP）=P3.又由式（6）及S3定義可知C3=X.

假設(shè)待破譯密文圖像為S.求解對應(yīng)置亂圖像C，C=bitxor（S，C3），然后求解對應(yīng)明文圖像為P，P=C（dP）.至此完成選擇密文攻擊.

由于該加密算法的擴散過程過于簡單，只使用了簡單的異或運算，使得分析者容易利用特殊的明文或密文消除擴散效應(yīng)得到只經(jīng)過置亂過程的密文圖像，這樣的圖像是非常容易受到暴力攻擊的.論文在選擇明文/密文攻擊中只選取了兩幅圖像，在仿真試驗中容易實現(xiàn)且運行時間短.綜上所述，任意一個加密算法過于脆弱的擴散過程會使置亂過程失效并威脅到整個加密系統(tǒng)的安全性.

2.3已知明文攻擊

雖然文獻［16］在廣義cat映射第二個變換表達式中添加了非線性項，但該非線性項只與第一個變換表達式有關(guān)，且第一個變換表達式的結(jié)果也會呈現(xiàn)在加密結(jié)果中，所以下面將運用同余函數(shù)性質(zhì)來消除該非線性項.

假設(shè)點坐標(biāo)（x，y）經(jīng)過文獻［16］中改進廣義cat映射得到（x′，y′），滿足式（1），而經(jīng)過一般廣義cat映射得到點（x″，y″），滿足

結(jié)合上式與（1）式可得

因此破譯該算法的置亂過程只需要破解原始cat映射的控制參數(shù)a和b即可.

2.3.1求解含有控制參數(shù)a和b的矩陣M

由于文獻［16］的加密算法對明文圖像的不同色彩分量分別進行加密，所以此處不妨假設(shè)明文密文圖像都是二維矩陣.假設(shè)已知明文-密文圖像對（PA，SA），（PB，SB），對應(yīng)置亂圖像CA，CB.定義

根據(jù)2.2節(jié)可知dC=dS且從dP到dC只經(jīng)歷置亂過程.將式（8）應(yīng)用到dC可得由dP經(jīng)過原始cat映射置亂后圖像dC′.

不妨設(shè)dP（x1，y1）=v1，dP（x2，y2）=v2且v1≠v2.由式（7）可得

將dC′中像素值等于v1和v2的像素點構(gòu)造成集合V1和V2：易知（x″1，y″1）∈V1，（x″2，y″2）∈V2.假設(shè)U可逆，定義集合V為

2.3.2破譯密文圖像

Step 1：利用矩陣M，式子（1），（7）和（8）可以得到PA的置亂圖像CA；

Step 2：由式（6）可知SA=bitxor（CA，X）?X=bitxor（CA，SA）；

Step 3：利用待破譯密文圖像S求解對應(yīng)置亂圖像C=bitxor（S，X）；

Step 4：利用矩陣M，式（1），（7）和（8）求解對應(yīng)明文圖像為P.

3　仿真實驗

仿真實驗是指在一定的計算機條件下用仿真軟件編程達到模擬現(xiàn)實的效果.大小為256×256的8比特經(jīng)典測試彩色圖像Lena將在軟件Matlab R2014b下進行仿真.加密算法密鑰取自文獻［16］本身，即

Lena明文圖像以及相應(yīng)的密文圖像如圖1所示.

圖1　文獻［16］的加密算法的加密結(jié)果

在對圖像Lena進行破譯之前，作為示例，先利用兩幅8×8圖像作為選擇明文進行選擇明文攻擊，得到的數(shù)值過程如下.

Step1：由2.1可知兩幅選擇明文分別為

Step2：求解擴散過程中密鑰矩陣X：

Step3：求解矩陣C2用于破解置亂過程：

可以看出矩陣C2中并無重復(fù)的像素值，且每一個像素值都可以代表該像素點置亂前的位置.利用矩陣C2和X可以很好得還原任意一副8×8密文圖像.對于圖像Lena的仿真結(jié)果具體如圖2和圖3所示.

圖2?。╝）選擇明文/密文Ⅰ，（b）選擇明文/密文Ⅱ，（c）還原圖像.

圖3　（a）已知明文Ⅰ，（b）已知明文Ⅱ，（c）還原圖像.

4　總結(jié)

論文對文獻［16］的加密算法進行安全性分析并提出相應(yīng)的選擇明文/密文攻擊和已知明文攻擊分析.論文經(jīng)過分析發(fā)現(xiàn)該加密算法主要存在兩方面的缺陷.一方面是擴散過程過于簡單，可以設(shè)計更安全的擴散函數(shù)改進擴散過程.另一方面是文獻［16］提出的改進的廣義cat映射混沌映射和一般廣義cat映射可以相互轉(zhuǎn)換，因而不能提高算法安全性，設(shè)計者可以考慮設(shè)計一個與明文圖像相關(guān)的置亂過程，使得加密算法對不同的明文圖像具有不同的密鑰，從而更好的抵抗分析者的攻擊，這也是后續(xù)的主要研究工作.

［1］STINSON D R.Cryptography：theory and practice［M］.Boca Raton：CRC Press，1995.

［2］MATTHEWSR.On the derivation ofa chaotic encryption algorithm［J］.Cryptologia，1989，13（1）：29-42.

［3］SHANNON C E.Communication theory ofsecrecy system［J］.Bell Syst Tech J，1949，28（4）：656-715.

［4］GAO H，ZHANG Y，LIANG S，et al.A newchaotic algorithm for image encryption［J］.Chaos，Solitons& Fractals，2006，29（2）：393-399.

［5］CHUNG K L，CHANG L C.Large encrypting binary images with higher security［J］.Pattern Recognition Letters，1998，19（5/6）：461-468.

［6］BAPTISTA MS.Cryptography with chaos［J］.Phys Lett A，1998，240（1/2）：50-54.

［7］葛辛.數(shù)字混沌加密技術(shù)研究［D］.河南：解放軍信息工程大學(xué)，2007：1-9.

［8］ZHANG G，LIU Q.A novel image encryption method based on total shuffling scheme［J］.Optics Communications，2011，284（12）：2775-2780.

［9］WANG X，HE G.Cryptanalysis on a novel image encryption method based on total shuffling scheme［J］. Optics Communications，2011，284（24）：5804-5807.

［10］RHOUMA R，BELGHIT S.Cryptanalysis of a new image encryption algorithm based on hyper-chaos［J］. Physics Letters A，2008，372（38）：5973-5978.

［11］WANG Y，WONG K W，LIAO X F，et al.A chaos-based image encryption algorithm with variable control parameters［J］.Chaos，Solitons and Fractals，2009，41（4）：1773-1783.

［12］LI S J，LI C Q，CHEN G R，et al.A general quantitative cryptanalysis of permutation-only multimedia ciphers against plain-image attacks［J］.Signal Process：Image Commun，2009，23（3）：212-223.

［13］Li C Q，Li S J，Chen G R，Chen G，Hu L.Cryptanalysis of a newsignal security system for multimedia data transmission［J］.EURASIP J Appl Signal Process，2005，2005：1277-1288.

［14］葉瑞松，馬俊明，曾少君.一種圖像加密算法的密碼分析及其改進［J］.汕頭大學(xué)學(xué)報（自然科學(xué)版），2015，30（4）：57-70.

［15］馬俊明，葉瑞松.一種圖像加密算法的密碼學(xué)分析［J］.網(wǎng)絡(luò)新媒體，2015，4（6）：37-42.

［16］張新，柏逢明.基于改進廣義cat映射的彩色衛(wèi)星圖像加密算法［J］.長春理工大學(xué)學(xué)報（自然科學(xué)版），2015，38（14）：93-96.

AbstractAcolor satellite image encryption algorithmbased on improved generalized cat mapping was proposed recently.The algorithmmodified the generalized cat mappingbyaddinga nonlinearterm to make the generalized cat mapping with more chaotic natures.Three color components of color images were scrambled by using the improved generalized cat mapping.The diffusion for scrambled image is carried out by using compound chaos mapping.In this paper，three kinds of cryptanalysis on this image encryption algorithm are devised，including chosen plaintext attack，chosen ciphertext attack and known plaintext attack.There are twoshortcomings in this encryption algorithm according to the theoretical security analysis.The diffusion processing only uses a simple XOR operation on the whole image.The scrambled image is independent on the plain image.Both theoretical and simulation experiments show that the encryption algorithm cannot resist chosen plaintext/ciphertext attacks and known-plaintext attacks.

Keywordschaotic mapping；image encryption；chosen plaintext attack；chosen ciphertext attack；known plaintext attacks

Security Analysis on a Color Satellite Image Encryption Algorithm Based on Improved Generalized Cat Mapping

MA Junming，YE Ruisong
（Department of Mathematics，Shantou University，Shantou 515063，Guangdong，China）

A

1001-4217（2016）02-0050-09

2015-12-08

葉瑞松（1968—），男（漢族），博士，教授.研究方向：分形混沌及應(yīng)用.E-mail：rsye@stu.edu.cn

國家自然科學(xué)基金資助項目（11271238）