一種基于混沌和置換-替代機制的圖像加密算法

趙君勤，葉瑞松

（汕頭大學理學院，廣東　汕頭，515063）

一種基于混沌和置換-替代機制的圖像加密算法

趙君勤，葉瑞松

（汕頭大學理學院，廣東汕頭，515063）

本文提出了一種基于混沌和置換-替代機制的圖像加密方法.該加密算法只對圖像作一輪置換和一輪替代就達到非常好的加密效果.加密算法采用廣義Arnold映射生成置換和替代時需要的一系列向量，并且采用整行和整列加密取代傳統加密算法中的逐個像素加密，從而提高了加密的效率.本文還分析了加密算法的安全性，包括直方圖分析，密鑰敏感性分析，相鄰像素相關性分析，信息熵分析，差分攻擊分析等.所有的實驗數據都表明本文所提的加密算法能有效的抵抗各種攻擊，是一種簡單有效的加密算法，在圖像安全方面有一定的應用價值.

Arnold映射；混沌；置換-擴散機制；圖像加密

0　引言

隨著網絡以及多媒體技術的迅猛發展，越來越多的圖像信息在公共網絡媒介上傳輸、儲存以及共享，其安全問題日益顯得重要，受到社會各界的廣泛關注.加密是保證信息安全的經典且有效的解決方法，其中的圖像加密關注的是圖像信息的安全.圖像具有攜帶數據信息大、數據冗余度高、圖像像素之間的相關性強等的固有特性，其加密算法也就有自身的特點和要求.根據Shannon［1］，置換和擴散是加密算法中兩個最基本的要求.最近10多年來，基于混沌系統的圖像加密算法能很好滿足這兩種要求，得到很多加密效果很好的圖像加密算法.混沌系統有許多優良的性質，如對初始值條件和系統參數的高度敏感性、偽隨機性、遍歷性等.混沌系統的這些良好特性與圖像加密的置換和擴散的要求高度一致，從而使混沌系統在圖像加密領域得到了廣泛應用［2-12］.

自從Fridrich在1998年首次發表了基于混沌系統的置換-擴散加密算法［2］，基于混沌系統的圖像加密算法得到了廣泛深入的研究.研究表明基于混沌動力系統的加密算法具有優良的加密性能.然而，Wang等人在文獻［13］指出，這種典型的置換-擴散結構有很大的缺點，即其置換過程和擴散過程是相互獨立的，并且置換過程的密鑰流與明文圖像無關.這樣的缺點使得該類加密算法容易被選擇明文攻擊和已知明文攻擊所破譯.密碼分析專家可以選擇一副特殊的明文圖像，圖像所有像素灰度值相同，從而使得置亂與擴散可以分開作密碼分析.因此，這樣的加密算法存在很大的安全隱患［14-15］.后來，各種各樣的改進算法陸續發表，例如文獻［16］提出一種置換-替代-主要置換的加密算法取代傳統的置換-擴散加密算法，其所有的加密采用整行/整列加密，改進了傳統的加密算法中逐個像素加密的方法，提高了加密的效率.文獻［17］中利用了位平面分解，對圖像進行比特層次的加密，達到了不錯的加密效果.文獻［18］提出了基于Arnold映射的置換-替代的加密方法，對彩色明文圖像進行加密，改進了文獻［16］的加密性能和效率.Arnold映射具有很好的混沌特性，如系統參數和初值的敏感性，偽隨機性，遍歷性等［19］；其計算量也較少，相對文獻［16］采用的標準映射更有效.

本文將采用置換-替代的加密機制以及位平面分割的辦法，構造一種有效的圖像加密算法.論文將256個灰度級的灰度明文圖像矩陣PI的8個位平面分割成兩部分，分別由高四位矩陣P1和低四位矩陣P2組成.采用的置換過程是一個新穎的辦法，將P1與P2均當成一個16個灰度級的灰度圖像；置換過程是在P1與P2之間進行，這樣的置換過程完全不同于以往文獻的置換過程.傳統的加密算法中的置換過程是在同一個圖像內的像素位置之間進行，其加密效果和加密效率相對較低.本文將置換設置在P1與P2之間操作，生成的置換向量的混沌映射迭代次數大大減少，提高了加密的效率.論文首先將大小為H×W的8比特灰度圖像的每個像素的高四位比特和低四位比特的信息拆開，組成兩個大小均為H×W的4比特的灰度圖像.利用Arnold映射，產生置亂與擴散所需要的混沌偽隨機序列.一輪置亂與擴散后，將圖像恢復成8比特灰度圖像，加密完成.由于采用位平面分解，將高四位和低四位分開當作4比特的兩個灰度圖像，并在該兩個灰度圖像之間置換，經過行和列的置換后，完全改變了原始明文圖像的灰度值分布，比傳統的基于像素層次的置換具有更好的加密效果.本文提出的加密算法簡單有效，容易實現.置換過程所使用的密鑰流設計成與明文圖像的內容相關，所以增強了抵御已知明文攻擊，選擇明文攻擊的性能.從數值實驗的模擬仿真結果可以看出，本文的加密算法各項性能指標均很好，是一個安全穩健的圖像加密算法.

本文結構如下：第二節給出置換與擴散的具體加密步驟；第三節對加密算法的安全性進行了全面的分析；第四節對本文作總結.

1　加密算法

1.1置亂階段

首先讀取大小為H×W的灰度圖像PI，利用位平面分解將PI分解為兩個大小均為H×W，而灰度級為16的灰度圖像P1與P2.在置換過程，P1與P2分開處理；在擴散過程，可以將P1與P2合成一個大小為H×2W的圖像整體進行操作處理.這個加密算法如下所述，其中步驟1-步驟3是應用Arnold映射生成偽隨機序列，分別用于置換和替代過程，步驟4為置換過程，步驟5為擴散過程.設T=max｛H，2W｝.

步驟1.首先生成擴散時需要的初始替代向量IVC，IVR.選取初始值x0，y0，系統參數a，b，以及混沌序列過渡點數N，應用廣義Arnold映射進行迭代.記錄下第N次的狀態值xN，yN.N的作用是去除混沌序列過渡效應，使得用于加密過程的偽隨機序列性能更好，可以設置為密鑰之一.將xN，yN作為新的初始值x0，y0，用廣義Arnold映射迭代，產生向量IVC，IVR.迭代過程如（1）所述.

其中floor（x）代表向下取整，返回不大于x的最大整數.我們取IVC的前H個元素，并變成列向量，同樣取IVR的前2W個元素.經過這一步，我們得到有2W個元素的行向量IVR，和H個元素的列向量IVC.

步驟2.將步驟1得到的xT，yT作為初始值x0，y0，用廣義Arnold映射迭代，得到新的向量SVR，SVC，將作為替代過程的替代向量，生成過程如（2）所示.

步驟3.將2維H×W的矩陣P1與P2合成一個大小為H×2W的矩陣P.計算P中所有元素的數值總和，并被256除，取其余數，記為N1，如（3）所示.

將步驟1所得到的xN，yN作為初始值，用廣義Arnold映射迭代N1次，得到xN1，yN1，并用xN1，yN1作為新的初始值x0，y0，迭代生成置換向量PR，PC.通過（3）式計算N1，可以使得置換過程的密鑰流PR，PC與明文圖像相關，達到一圖一密的加密效果，使得選擇明文攻擊，已知明文攻擊失效.PR，PC的生成算法如（4）所示.

步驟4.用步驟3生成的PR，PC對圖像進行置換.置換在兩幅16個灰度級的灰度圖像P1與P2之間操作.從i=1開始到i=H結束，將矩陣P2的第PR（i）行與P1的第i行對調；從j=1開始到j=W結束，將矩陣P2第PC（j）列與P1的第j列對調.將置換后的矩陣P1與P2合并成大小為H×2W的矩陣P.

步驟5.用步驟1和步驟2產生的初始替代向量IVC，IVR和替代向量SVR，SVC對置換后的圖像進行替代擴散.矩陣P第一行元素與IVR作按位異或運算，再與SVR的第一個元素作按位異或運算；從第二行開始，P的每一行與它的上一行作按位異或運算后，再與SVR對應的元素作按位異或運算.行替代完成后，對列采用相同的步驟進行替代加密，替代加密過程如下描述：

其中“⊕”表示按位異或運算，P（i，：），（：，j）分別P表示的第i行與P的第j列.

步驟6.最后將P矩陣轉換成灰度級為256的灰度圖像，即令C=P1×16+P2，得到大小為H×W的256個灰度級的灰度圖像C，加密完成.

解密算法就是上述加密算法的逆過程.選用大小為512×512的Lena圖像進行仿真實驗，實驗結果如圖1所示.

2　算法的安全性分析

根據密碼學基本原理，一個理想的加密算法需要密鑰具有高度的敏感性，密文與密鑰密切相關［20］.理想的加密方案的密鑰空間應該足夠大，使得蠻力攻擊不可實現；它也應該能夠抵御各種攻擊，如統計攻擊、差分攻擊、已知明文的攻擊和選擇明文的攻擊等.在本節中，我們對提出的加密算法進行安全性分析，包括最重要的統計分析（直方圖分析，相關性分析，信息熵分析）、密鑰敏感性分析、差分攻擊分析等.所有的分析表明，我們所提出的圖像加密算法具有很好的安全性和滿意的加密效果.

2.1直方圖分析

圖像的直方圖是反映圖像像素值分布的圖，加密圖的直方圖應該分布均勻，與未加密圖像的直方圖完全不同.從圖1的（c）、（d）中可以看出，加密過的圖像的直方圖與未加密的圖像直方圖有很大的差別，（c）中圖像像素分布很不均勻，而（d）中分布非常均勻.這說明攻擊者不能從加密圖像中獲得有效的信息，具有很好的防攻擊性.

2.2相關性分析

我們都知道，一般圖像的相鄰像素包括水平方向的兩個相鄰像素，垂直方向的兩個相鄰像素，對角方向的兩個相鄰像素，相鄰像素之間都有很強的相關性，而理想的加密圖像則要求不管哪個方向的相鄰像素之間只能有很小的相關性.基于這樣的標準，我們對圖像的相關性進行了分析，我們隨機抽取圖像中5 000對相鄰像素，利用下面的公式計算他們的相關性：

其中xi，yi是選取的第i對相鄰像素，T是選取的隨機像素的總數.我們采用圖像Lena和Couple進行測試，分別得到它們的密文圖像和明文圖像對應的各個方向的相鄰像素相關值，如表1所示.從表中我們清楚的看到，密文圖像不管哪個方向的相關性都明顯小于原始明文圖像的相應方向的相鄰像素相關性，并且密文圖像的相鄰像素相關性接近零.

圖1　明文圖像、機密圖像及其直方圖.

表1　原圖與密圖的相關系數分析

圖2是從Lena圖及其相應的加密圖像隨機選取5 000組鄰點（水平、垂直、對角）作出的像素相關圖：

圖2　明文圖像與密文圖像相鄰像素相關性比較

2.3信息熵分析

信息熵是檢查隨機性和安全性的一個重要指標.信息源m的信息熵H（m）可通過公式（6）計算：

其中L表示符號的總數，p（mi）是符號mi出現的概率，而log表示的是以2為底的對數.對于含有256個隨機散發符號的信息源，若它的信息熵H（m）接近8，則該密文圖像的像素值接近隨機分布.我們計算了加密圖像和原圖像的信息熵，見表2.從表中可以看出，經過加密的圖像，它的信息熵與8非常接近，即說明我們的加密算法是安全的，可以抵抗來自熵的攻擊.

2.4密鑰敏感性分析

理想的加密算法應該是對密鑰敏感的，它可以有效的防止入侵者解密原始數據.加密系統的密鑰敏感性有兩種表現：（1）通過不同密鑰加密的密文圖像應截然不同，就算兩個密鑰只有微弱的變化；（2）加密圖像不能被任何不同于密鑰的數據正確的還原.為了計算密鑰敏感性，我們設計了5個不同的密鑰，每一個密鑰與主密鑰都只是很細微的改變，它們分別為

主密鑰：（0.286295319532476，0.56538639123458，22.0，33.0，108）；

密鑰1：（0.286295319532475，0.56538639123458，22.0，33.0，108）；

密鑰2：（0.286295319532476，0.56538639123457，22.0，33.0，108）；

密鑰3：（0.286295319532476，0.56538639123458，22.0，33.0，109）；

密鑰4：（0.286295319532476，0.56538639123458，22.0+10-14，33.0，108）；

密鑰5：（0.286295319532476，0.56538639123458，22.0，33.0+10-14，108）.

我們將整理的結果放到表3，結果顯示所有的相關系數都非常小，不同的密鑰加密出來的圖像完全不同，說明我們的加密算法有很好的密鑰敏感性.

表3　圖像Lena的密鑰敏感性分析I

我們還對密鑰的敏感性程度做更進一步的計算，度量敏感性可以用公式（5）計算.假設我們要檢驗密鑰K的敏感性，則分別用K、K-Δδ和K+Δδ加密明文圖像，其他密鑰參數保持不變，得到的密文圖像分別記為A1，A2，A3.計算密鑰參數K的敏感性如（5）.

其中Ps（K）是密鑰參數K的敏感度，Δδ是擾動值，W，H為加密圖像的寬和高，

如果Δδ越小，Ps（K）較大，則說明該密鑰的敏感性更好.

測試結果見表4所示.從結果看出，密鑰x0，y0，a，b的敏感性均可以達到10-14，相應的密鑰空間（不考慮N）可以達到（1014）4=1056≈2186，所以密鑰可以長達186比特，這樣長度的密鑰足夠抵御蠻力攻擊.

表4　圖像Lena的密鑰敏感性分析II

2.5差分攻擊分析

攻擊者一般會對原圖像做一些輕微的改變來得到原圖與加密圖之間的關系，因此如果原圖一個細微的改變會對加密圖產生重大的改變，那么我們的算法就可以有效的抵抗差分攻擊了.我們一般用NPCR和UACI來衡量這種敏感性，其中NPCR表示像素變化比率，即當原圖一個像素改變時加密圖像數目改變率；UACI表示均一平均變化程度，即指原圖和加密圖的相應像素平均強度變化率，可通過如下公式計算：

其中C1與C2分別為只有一個像素不同的大小為H×W的兩個圖像經過加密后得到的加密圖像.我們隨機選取十個點，計算對應的NPCR和UACI.實驗結果見表5.我們也隨機選取了100個像素，求得NPCR和UACI的平均值分別為99.616 2%，33.436 8%，非常接近NPCR和UACI的數學期望值99.609 4%和33.463 5%，結果顯示我們的加密可以很有效的抵抗差分攻擊.

表5　lena圖的差分攻擊分析　%

3　總結

本文提出了一種基于廣義Arnold映射以及置換-替代機制的圖像加密算法.由于設計的置換和替代利用了圖像的位平面分解，使得加密效果得到提升.另一方面，置換過程在256個灰度級的灰度圖像的高四位矩陣P1和低四位矩陣P2之間實施，比較以往文獻在同一個圖像內的像素位置之間進行的置換過程，本文需要生成的置換向量的混沌映射迭代次數大大減少，從而提高了加密的效率.加密算法的置換過程所使用的密鑰流還被設計成與明文圖像的內容相關，增強了抵御已知明文攻擊，選擇明文攻擊的性能.從加密算法的安全性分析可以看出，各項性能指標均很好，表明該圖像加密方案是安全實用的.

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

［2］FRIDRICH J.Symmetricciphersbased on two-dimensionalchaoticmaps［J］.InternationalJournalofBifurcation and Chaos，1998，8（6）：1259-1284.

［3］KOCAREV L.Chaos-based cryptography：a briefoverview［J］.IEEE Circuits and Systems Magazine，2001，1（3）：6-21.

［4］HUANG F，GUAN Z H.A modified method of a class of recently presented cryptosystems［J］.Chaos Solitons and Fractals，2005，23（5）：1893-1899.

［5］PAREEK N K，PATIDAR V，SUD K K.Image encryption using chaotic logistic map［J］.Image and Vision Computing，2006，24（9）：926-934.

［6］YE R S.A novel chaos-based image encryption scheme with an efficient permutation-diffusion mechanism ［J］.Optics Communications，2011，284（15）：5290-5298.

［7］郭偉創，葉瑞松.一種基于貓映射和伯努利移位映射的圖像加密算法［J］.汕頭大學學報（自然科學版），2015，30（1）：13-23.

［8］MASUDAN，AIHARAK.Cryptosystems with discretized chaotic maps［J］.IEEE Trans Circuits Syst I，2002，49（1）：28-40.

［9］LIU H，WANG X.Color image encryption using spatial bit-level permutation and high-dimension chaotic system［J］.Optics Communications，2011，284（16/17）：3895-3903.

［10］BEHNIA S，AKHSHANI A，AHADPOUR S，et al.A fast chaotic encryption scheme based on piecewise nonlinear chaotic maps［J］.Phys Lett A，2007，366（4/5）：391-396.

［11］YE R S，HUANG H Q.Application of the chaotic ergodicity of standard map in image encryption and watermarking［J］.I J Image，Graphics and Signal Processing，2010，1：19-29.

［12］PATIDAR V，PAREEK N K，SUD K K.A new substitution-diffusion based image cipher using chaotic standard and logistic maps［J］.Commun Nonlinear Sci Numer Simulat，2009，14（7）：3056-3075.

［13］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.

［14］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.

［15］LI C Q，LI S J，CHEN G R，et al.Cryptanalysis of a new signal security system for multimedia data transmission［J］.EURASIP J Appl Signal Process，2005，2005（8）：1277-1288.

［16］PATIDAR V，PAREEK N K，PUROHIT G，et al.A robust and secure chaotic standard map based pseudorandom permutation-substitution scheme for image encryption［J］.Optics Communications，2011，284（19）：4331-4339.

［17］YE R S，GUO W C.A chaos-based image encryption scheme using multi modal skewtent maps［J］.Journal ofEmerging Trends in Computing and Information Sciences，2013，4（10）：800-810.

［18］ZHAO J Q，GUO W C，YE R S.A chaos-based image encryption scheme using permutation-substitution architecture［J］.International Journal ofComputer Trends and Technology，2014，15（4）：174-185.

［19］ARNOLD V，AVEZ A.Ergodic problem in classical mechanics［M］.NewYork：Benjamin，1986.

［20］SCHIENER B.Applied cryptography：protocols，algorithms and source code in c［M］.New York：John Wiley and sons，1996.

An Image Encryption Scheme Based on Chaos and Permutation-Substitution Architecture

ZHAO Junqin，YE Ruisong
（Department of Mathematics，Shantou University，Shantou 515063，Guangdong，China）

An image encryption scheme based on chaos and permutation-substitution mechanism is proposed.One round of permutation-substitution process achieves desirable security results.The generalized Arnold map is applied to generate the pseudo-random sequences for the permutation and substitution processes，which are implemented row-by-row/column-by-column instead of pixel-by-pixel to increase the encryption rate.The security and performance analysis of the proposed image encryption scheme are carried out using the histograms，correlation coefficients，information entropy，differential analysis，etc.All the experimental results showthat the proposed image encryption scheme is highly secure and owns excellent performance.

Arnold map；chaos；permutation-substitution architecture；image encryption

TP391

A

1001-4217（2016）03-0016-10

2015-07-17

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

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