基于混沌和細胞自動機的圖像加密算法

彭 川，李元香

（1.武漢大學(xué) 軟件工程國家重點實驗室，湖北 武漢430072；2.中南民族大學(xué) 計算中心，湖北 武漢430074）

0 引 言

圖像加密是圖像安全保護的核心技術(shù)和有效手段。數(shù)字圖像加密的基本方法有像素置亂和像素替換兩類。實際應(yīng)用中，通常將以上兩種方式結(jié)合進行加密處理。

混沌系統(tǒng)具有類隨機、對初始狀態(tài)和參數(shù)的極其敏感等特性，具有良好的密碼學(xué)特性，非常適合用于信息加密，其安全性依賴于密鑰流的隨機性。自1989年logistic混沌映射作為密鑰發(fā)生器用于信息加密以來，低維混沌系統(tǒng)用于信息加密已經(jīng)得到廣泛的研究。但低維混沌系統(tǒng)的動力學(xué)特性相對簡單，密鑰空間容量小，安全性不高，因此研究中更多的是利用超混沌系統(tǒng)即兩個以上的混沌系統(tǒng)進行加密可以改善其安全性能，但其實現(xiàn)比一般低維混沌系統(tǒng)復(fù)雜。

Von等人在研究具有自組織特性的離散動力系統(tǒng)時引入了細胞自動機 （CA）的概念，1985年，Wolfram最先提出將CA運用于密碼學(xué)，從此，CA逐漸成為研究密碼學(xué)的重要方法，也逐漸出現(xiàn)了許多有價值的學(xué)術(shù)成果［1－5］。國內(nèi)對CA加密技術(shù)的研究也逐漸增多。文獻 ［6］提出了一種基于初等CA的圖像加密算法；文獻 ［7］進行了二維CA的圖像加密方法的研究；文獻 ［8］利用二維細胞自動機設(shè)計了一種雙層耦合的偽隨機數(shù)發(fā)生器；文獻 ［9］提出了一種基于可逆CA的多粒度CA加密模型；文獻 ［10］研究了一種二維CA的反向迭代加密方法?；诩毎詣訖C的圖像加密的安全性能很大程度取決于迭代規(guī)則和鄰域半徑，因此高維細胞自動機比低維細胞自動機具有更高的安全性，已經(jīng)一些研究開始針對高維CA展開。研究表明，可以通過提高細胞自動機結(jié)構(gòu)的復(fù)雜性來提高密鑰流的周期和安全性，但是復(fù)雜的結(jié)構(gòu)卻大大增加了硬件實現(xiàn)的難度和代價。二維CA的結(jié)構(gòu)相對復(fù)雜而又容易硬件實現(xiàn)，所以是研究CA加密系統(tǒng)的理想模型。本文將二維細胞自動機（2D－CA）和混沌理論相結(jié)合，提出一種基于二維觸發(fā)細胞自動機 （2D－TCA）和混沌系統(tǒng)的圖像加密算法。該算法是一種結(jié)合了像素置亂和像素替換的加密方法?；诨煦缦到y(tǒng)良好的密碼學(xué)特性和細胞自動機優(yōu)異的加密性能，該算法具有較高的加解密效率、較大的密鑰空間和較高的安全性能，并且非常便于硬件實現(xiàn)。

1 logistic混沌系統(tǒng)

混沌現(xiàn)象是非線性動力學(xué)系統(tǒng)中確定的類隨機過程，這種過程是非周期的且又不收斂，但它是有界的，并且對初始狀態(tài)和系統(tǒng)參數(shù)具有極其敏感的依賴性。給定同一個混沌系統(tǒng)兩個非常接近的初值或參數(shù)，系統(tǒng)經(jīng)過較短時間后，會產(chǎn)生兩組完全不同的互不相關(guān)的混沌序列。Logistic映射是一種模型簡單的混沌動力系統(tǒng)，以其遍歷性、對初值高度敏感性的特點而倍受關(guān)注，可用以下非線性方程來描述

當(dāng)3.5699456＜λ≤4時，系統(tǒng)的動力學(xué)形態(tài)十分復(fù)雜，將進入混沌狀態(tài)。當(dāng)λ＝4時，logistic混沌序列的概率分布函數(shù)ρ（x）為

通過該式可以計算出混沌序列軌跡的均值為0，初始值不同的兩個序列的互相關(guān)函數(shù)值為0。這表明logistic序列具有遍歷性，且其產(chǎn)生序列的概率密度分布函數(shù)與初值無關(guān)。因此，設(shè)定適當(dāng)λ值、并取兩個不同x值作為初值，可得到兩個互不相關(guān)的混沌序列。通?？蓪ι傻幕煦缧蛄羞M行二值量化處理，量化處理所用的閾值函數(shù)如下所示

式中：xi——生成的混沌序列中第i個元素值，f （xi）——其量化后的對應(yīng)值。

根據(jù)上述混沌映射特性，可以快速得到隨機性很強的混沌序列。本文的加密算法通過設(shè)定初值作為密鑰產(chǎn)生logistic混沌序列，對該混沌序列進行量化處理后得到二值混沌序列，然后利用該序列對圖像進行第一次加密處理。由于混沌的初值敏感特性，初值的極小改變會導(dǎo)致產(chǎn)生完全不同的混沌序列，因而極大增強了系統(tǒng)的安全性。

2 觸發(fā)細胞自動機

在細胞自動機中，有一類具有特殊性質(zhì)的細胞自動機，其細胞單元的轉(zhuǎn)換狀態(tài)與其鄰域狀態(tài)配置中的某個單元的狀態(tài)值之間存在線性關(guān)系，即改變鄰域狀態(tài)配置中這一單元的狀態(tài)值將直接導(dǎo)致轉(zhuǎn)移狀態(tài)的改變，稱這種轉(zhuǎn)移狀態(tài)與其鄰域狀態(tài)配置中的某位狀態(tài)具有線性關(guān)系的規(guī)則為反轉(zhuǎn)規(guī)則，這類細胞自動機稱為觸發(fā)細胞自動機 （toggle－CA，TCA）。TCA的迭代過程可描述為

表1 規(guī)則90的反轉(zhuǎn)規(guī)則

3 算法描述

根據(jù)上面說明的混沌產(chǎn)生方法和2D－TCA的原理，可設(shè)計基于混沌和細胞自動機的圖像加密算法，以大小為M×N的灰度圖像IM×N為加密對象，本文的加密算法可描述如下：

（1）設(shè)定迭代次數(shù)count＝0，最大迭代次數(shù)countmax；

（2）設(shè)定混沌參數(shù)初值μ＝μ0，λ＝λ0，由式 （1）產(chǎn)生長度為M×N的混沌序列 ｛｛Li｝｝并二值化處理，其中，0＜i≤M×N；

（3）將混沌序列L與圖像I進行異或運算，得到圖像LIM×N；

（4）產(chǎn)生2D－TCA 反轉(zhuǎn)規(guī)則f，以 LIM×N作為該2DTCA的初態(tài)；

（5）利用反轉(zhuǎn)規(guī)則f依次對最左列的每個細胞進行迭代加密；

（6）2D－TCA每列循環(huán)左移一次；

（7）迭代次數(shù)count加1；

（8）若count＜countmax，轉(zhuǎn)第 （2）步；否則結(jié)束，得到加密圖像LICA。

依照上述加密過程，可得到相應(yīng)的解密過程，解密算法可描述如下：

（1）設(shè)定迭代次數(shù)count＝0，最大迭代次數(shù)countmax；

（2）設(shè)定混沌參數(shù)初值μ＝μ0，λ＝λ0，由式 （1）產(chǎn)生長度為M×N的混沌序列 ｛Li｝，其中，0＜i≤M×N；

（3）2D－TCA循環(huán)右移一次；

（4）產(chǎn)生2D－TCA反轉(zhuǎn)規(guī)則f，以LICA作為該2DTCA的初態(tài)；

（5）按照反轉(zhuǎn)規(guī)則f依次對最左列的每個細胞進行解密；

（6）用混沌序列L與圖像I進行異或運算；

（7）迭代次數(shù)count加1；

（8）若count＜countmax，轉(zhuǎn)至第 （2）步；否則結(jié)束，即得到解密圖像。

從上述算法描述可以看出，加密和解密互為逆過程，其不同之處在于加密和解密循環(huán)移位的方向相反；移位和異或運算的順序相反。因此在硬件實現(xiàn)時，加解密功能可實現(xiàn)模塊共享。其硬件系統(tǒng)只需由一個雙向移位寄存器、一個移位寄存器控制單元、一個反轉(zhuǎn)規(guī)則生成器、一個異或運算單元及一個混沌序列生成器構(gòu)成，因此很容易進行硬件實現(xiàn)。

4 仿真實驗與分析

4.1 密鑰空間分析

加解密過程中，密鑰由混沌初值μ，λ和細胞自動機的規(guī)則共同決定。半徑為r的2D－TCA系統(tǒng)有24r＋1種細胞配置狀態(tài)，有224r＋1種規(guī)則，該算法的密鑰空間隨著r的增加呈現(xiàn)指數(shù)及增長。即使取半徑r為1，由μ，λ的取值范圍可知密鑰空間仍然足夠大，采取窮舉搜索是無法得到密鑰的，即該加密系統(tǒng)是計算安全的。

4.2 算法效率分析

本文對上述算法進行了仿真實驗。實驗所用的原圖像為128×128的8位灰度圖，如圖1（a）所示，圖1（b）為原圖像的灰度直方圖。實驗中的參數(shù)設(shè)定分別為：logistic混沌系統(tǒng)初值μ＝4，λ＝0.6，觸發(fā)細胞自動機鄰域半徑r＝1，構(gòu)造的反轉(zhuǎn)規(guī)則用二進制表示為 （01100101011001010110010101010110）。

為了說明算法的效率，實驗對一般細胞自動機迭代加密方法和本文的算法進行了加解密的比較實驗。圖2、圖3、圖4分別為本文算法1輪、3輪、5輪迭代的加密結(jié)果、密圖直方圖和解密圖像。用一般細胞自動機迭代方法經(jīng)過6輪迭代后也可得到較好的加密效果，其密圖、密圖直方圖和解密圖像如圖5所示。但與之相比，本文算法只需3輪迭代已經(jīng)可得到較好的加密結(jié)果，因此具有較高的效率。

4.3 密鑰敏感性分析

本文算法的密鑰由混沌系統(tǒng)初值和細胞自動機規(guī)則共同確定。由于混沌系統(tǒng)的初值敏感特性，初值的微小改變將導(dǎo)致無法得到正確的解密圖像。實驗中分別設(shè)定加解密時的初值λ0為0.6和0.6＋10－6，得到的加密結(jié)果如圖6（a）所示，圖6（b）為錯誤解密圖像。結(jié)果表明，即使對于10－6這樣微小的改變，得到的解密圖像是完全錯誤的，這說明該加密系統(tǒng)對密鑰的變化非常敏感。

一個好的加密系統(tǒng)必須滿足 “雪崩”效應(yīng)，即任意改變明文、密文或密鑰的一位后，其誤差傳播應(yīng)該使得相應(yīng)的密（明）文產(chǎn)生明顯變化。圖7（a）、圖7（b）分別表示5次迭代加密后，明文 （密文）改變一位所引起的對應(yīng)的密文 （明文）的擴散變化情況。實驗表明，明文 （密文）的微小變化會引起 “雪崩效應(yīng)”，從而可以有效抵抗差分分析攻擊。

4.4 相鄰像素相關(guān)性分析

原始圖像中相鄰像素通常具有很大的相關(guān)性。相鄰像素的相關(guān)性可反應(yīng)出圖像像素的擴散程度。

相關(guān)性越小，隨機性越好，即加密性能越好，此時攻擊者是無法通過像素的相關(guān)性來破解密圖的。性能良好的加密系統(tǒng)應(yīng)盡量讓密圖的相鄰像素相關(guān)性系數(shù)接近零。圖8、圖9、圖10分別反映了原圖和密圖的水平方向、垂直方向、對角線方向的相鄰像素相關(guān)性情況。不難看出，原圖不論在哪個方向上的相鄰像素之間都具有很高的相關(guān)性；而密圖中，各方向上相鄰像素的相關(guān)性呈現(xiàn)出高度的隨機分布特性，說明此時相鄰像素的相關(guān)性已經(jīng)幾乎為零。

圖7 密文 （明文擴散情況）

表2說明了原圖、密圖各方向上相鄰像素的相關(guān)性系數(shù)?？梢钥吹剑瓐D的相鄰像素具有很高的相關(guān)系數(shù)值，而加密后的圖像相鄰像素相關(guān)系數(shù)接近于零，即其相鄰像素已基本不相關(guān)，說明本文的加密算法具有較好的擴散效果。

表2 相鄰像素相關(guān)性系數(shù)

5 結(jié)束語

混沌系統(tǒng)具有良好的加密性能，但低維混沌系統(tǒng)如logistic混沌系統(tǒng)的密鑰空間較小，缺乏足夠的安全性；細胞自動機迭代加密方法簡單易行，但較大的鄰域半徑不利于硬件實現(xiàn)。本文提出的基于混沌和細胞自動機的圖像加密算法，結(jié)合了兩者的優(yōu)點，實現(xiàn)了一種簡單可行，且便于硬件實現(xiàn)的圖像加密算法。由于密鑰由混沌初值和細胞自動機迭代規(guī)則共同確定，所以具有很大的密鑰空間。在細胞自動機的鄰域半徑較小時，也可得到很好的加密效果，所以非常便于硬件實現(xiàn)。可在此基礎(chǔ)上實現(xiàn)一種高性能、低代價的硬件加密系統(tǒng)。

［1］ZHANG Chuan－wu，SHEN Ye－qiao，PENG Qi－cong.Encryption based on cellular automata inverse iteration ［J］.Chinese Journal of Computers，2004，27 （1）：125－129.

［2］Seredyn ski F，Bouvry P，Zomaya A Y.Cellular automata computations and secret key cryptography ［J］.Parallel Computing，2004，30 （5）：753－766.

［3］Marcin Seredynski，Pascal Bouvry.Block encryption using reversible cellular automata ［J］.New Generation Computing，2005，23 （9）：245－258.

［4］Sung J，Hong D，Hong S.Cryptanalysis of an involutional block cipher using cellular automata ［J］.Information Processing Letters，2007，104 （5）：183－185.

［5］Tan S K，Guan S－U.Evolving cellular automata to generate nonlinear sequences with desirable properties ［J］.Applied Soft Computing，2007，7 （3）：1131－1134.

［6］Jin Jun.Image encryption method based on elementary cellular automata［C］.Proc of IEEE SOUTHEASTCON.Tatlanta，USA：IEEE Press，2009.

［7］ZHANG Xiaoyan，WANG Chao，LI Sumei，et al.Image encryption technology on two dimensional cellular automata ［J］.Journal of Optoelectronics Laser，2008，19 （2）：242－245 （in Chinese）.［張曉巖，王超，李素梅，等.基于二維細胞自動機的圖像加密技術(shù) ［J］.光電子·激光，2008，19 （2）：242－245.］

［8］XIA Xuewen，LI Yuanxiang，ZHU Jixiang.A high－quality pseudorandom numbers generator based on two－layer couple cellular automata ［C］.Proceedings of the Eleventh Conference on Congress on Evolutionary Computation，2009：2265－2272.

［9］XIA Xue－wen，XIONG Zeng－gang，LI Yuan－xiang.Data encryption based on multi－granularity reversible cellular automata［J］.Computer Engineering and Design，2010，31 （16）：3599－3603（in Chinese）.［夏學(xué)文，熊曾剛，李元香.多粒度可逆細胞自動機模型的數(shù)據(jù)加密方法 ［J］.計算機工程與設(shè)計，2010，31 （16）：3599－3603.］

［10］XIA Xue－wen，LI Yuan－xiang，ZENG Hui.Data encryption algorithm based on two dimension toggle cellular automata［J］.Computer Science，2010，37 （3）：46－48 （in Chinese）.［夏學(xué)文，李元香，曾輝.二維可反向迭代細胞自動機在數(shù)據(jù)加密中的應(yīng)用 ［J］.計算機科學(xué)，2010，37 （3）：46－48.］