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

馬俊明，葉瑞松（汕頭大學數學系　廣東　汕頭　515063）

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

馬俊明，葉瑞松
（汕頭大學數學系廣東汕頭515063）

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

0　引言

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

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

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

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

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

1.1置亂過程

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

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

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

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

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

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

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

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

1.2擴散過程

Step 1.分別取序列I1，I2和I3的后面N×N個序列值，構成序列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為彩色置亂圖像.后面的寫法是為了行文方便，兩者完全等價.

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

2　密碼學分析

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

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

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

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

2.1選擇明文攻擊

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

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

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

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

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

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

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

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

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

2.2選擇密文攻擊

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

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

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

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

2.3已知明文攻擊

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

假設點坐標（x，y）經過文獻［16］中改進廣義cat映射得到（x′，y′），滿足式（1），而經過一般廣義cat映射得到點（x″，y″），滿足

結合上式與（1）式可得

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

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

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

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

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

將dC′中像素值等于v1和v2的像素點構造成集合V1和V2：易知（x″1，y″1）∈V1，（x″2，y″2）∈V2.假設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求解對應置亂圖像C=bitxor（S，X）；

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

3　仿真實驗

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

Lena明文圖像以及相應的密文圖像如圖1所示.

圖1　文獻［16］的加密算法的加密結果

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

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

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

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

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

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

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

4　總結

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

［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］葛辛.數字混沌加密技術研究［D］.河南：解放軍信息工程大學，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］.汕頭大學學報（自然科學版），2015，30（4）：57-70.

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

［16］張新，柏逢明.基于改進廣義cat映射的彩色衛星圖像加密算法［J］.長春理工大學學報（自然科學版），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—），男（漢族），博士，教授.研究方向：分形混沌及應用.E-mail：rsye@stu.edu.cn

國家自然科學基金資助項目（11271238）