一種高階可逆元胞自動(dòng)機(jī)加密算法

空間數(shù)據(jù)是促進(jìn)經(jīng)濟(jì)和社會(huì)發(fā)展的重要戰(zhàn)略資源。元胞自動(dòng)機(jī)(cellularautomaton,CA)在空間、時(shí)間和狀態(tài)上的離散性是其應(yīng)用于圖像加密的重要依據(jù),其組成單元的簡(jiǎn)單性、單元之間作用的局部性、信息處理的高度并行性以及全局復(fù)雜性等特點(diǎn),使其在密碼學(xué)領(lǐng)域具有獨(dú)特的優(yōu)勢(shì)目前,已有多位學(xué)者研究了元胞自動(dòng)機(jī)圖像加密方法,多體現(xiàn)為結(jié)合密碼學(xué)基本方法和單規(guī)則元胞自動(dòng)機(jī)設(shè)計(jì)加密算法。文獻(xiàn)[6]引入密碼學(xué)中的移位變換方法,提出了一種可逆多層元胞自動(dòng)機(jī)分組加密算法,達(dá)到了一次一密的加密效果,具有較大的密鑰空間,但此類(lèi)算法無(wú)法抵抗關(guān)于演化規(guī)則的窮舉攻擊。文獻(xiàn)[7]結(jié)合分組密碼方法,利用可逆元胞自動(dòng)機(jī)無(wú)信息損失和高度并行處理的特點(diǎn),提出了一種基于可逆二階觸發(fā)元胞自動(dòng)機(jī)的分組加密算法,具有較高的安全性,但應(yīng)用于圖像加密時(shí),存在加密和解密效率低的問(wèn)題。文獻(xiàn)[8]將已知灰度圖像變?yōu)槎祱D像,應(yīng)用可逆元胞自動(dòng)機(jī)規(guī)則實(shí)現(xiàn)圖像加密,具有較好的擴(kuò)散特性,但數(shù)據(jù)重排增加了計(jì)算時(shí)間,尤其對(duì)較大的圖像加密,加密速度較低。文獻(xiàn)[9]結(jié)合圖像像素置換方法,將元胞與相鄰元胞的鏈接狀態(tài)加權(quán)后作為加密矩陣,通過(guò)置換對(duì)圖像進(jìn)行加密,混亂特性和擴(kuò)散特性較好,但存在密鑰空間較小的不足。本文針對(duì)單規(guī)則元胞自動(dòng)機(jī)圖像加密算法安全性不足的問(wèn)題,結(jié)合可逆元胞自動(dòng)機(jī)無(wú)信息損失和全局并行處理及四叉樹(shù)圖像分割速度快、分割過(guò)程全自動(dòng)的優(yōu)點(diǎn),提出了一種多規(guī)則可逆元胞自動(dòng)機(jī)圖像加密算法,在不顯著增加算法復(fù)雜性的情況下,提高計(jì)算速度與安全性。1高階可逆元胞自動(dòng)機(jī)的定義通常元胞自動(dòng)機(jī)加密是基于單個(gè)規(guī)則對(duì)元胞進(jìn)行多次演化,而本文提出的多規(guī)則可逆元胞自動(dòng)機(jī)是在每次演化過(guò)程中構(gòu)造多個(gè)演化規(guī)則,形成復(fù)雜的構(gòu)形轉(zhuǎn)移,實(shí)現(xiàn)柵格地圖加密,達(dá)到混淆特殊用途地圖中的重要符號(hào)和標(biāo)識(shí),保證重要柵格地圖數(shù)據(jù)安全的目的。定義1的元胞自動(dòng)機(jī)為二階可逆元胞自動(dòng)機(jī)。文獻(xiàn)[10]給出了其可逆性證明。假設(shè)在一個(gè)K階RCA中,新構(gòu)形C式中,V式中,Φ定義2在元胞自動(dòng)機(jī)中,稱(chēng)具有形式局部轉(zhuǎn)換函數(shù)的元胞自動(dòng)機(jī)為多規(guī)則高階可逆元胞自動(dòng)機(jī)。其中,Φ式中,B在進(jìn)行逆向RCA演化時(shí),逆序操作構(gòu)形,即B根據(jù)式(5)可以得到:根據(jù)可逆元胞自動(dòng)機(jī)定義,式(6)中的C因此,式(5)定義的RCA可以從構(gòu)形C2許多規(guī)則的高可逆元生動(dòng)機(jī)加密方法2.1子塊的處理及演化首先,本文將四叉樹(shù)分解的4個(gè)子圖像狀態(tài)作為構(gòu)形,根據(jù)高階元胞自動(dòng)機(jī)定義,則構(gòu)造出的為4階元胞自動(dòng)機(jī),其每個(gè)演化過(guò)程需要3個(gè)規(guī)則,多個(gè)過(guò)程需要多個(gè)規(guī)則。其次,借鑒文獻(xiàn)[11]中的密鑰產(chǎn)生方法,將非均衡元胞自動(dòng)機(jī)的演化結(jié)果作為4階元胞自動(dòng)機(jī)規(guī)則,并將其規(guī)則由固定改為隨機(jī)選擇,以增強(qiáng)算法安全性。由于分割粒度越小加密結(jié)果越安全,本文分割的最小粒度為4×4像素。但是,也存在分割粒度越小計(jì)算量越大的問(wèn)題,本文并未對(duì)所有子塊進(jìn)行連續(xù)分割,而是選取左上角子塊進(jìn)行繼續(xù)分割,即降低了分割粒度,保證圖像內(nèi)容的安全性,又降低了加密過(guò)程的計(jì)算量。根據(jù)四叉樹(shù)分解定義,四叉樹(shù)深度取決于圖像大小,對(duì)于一個(gè)L×L的方圖,圖像分解后的數(shù)量m等于log需要說(shuō)明的是,每幅地圖加密前,都需要進(jìn)行一次非均衡元胞自動(dòng)機(jī)演化規(guī)則的隨機(jī)選擇,并記錄所選擇的演化規(guī)則及其順序。這是因?yàn)樵诮饷苓^(guò)程中,同樣需要子密鑰定義關(guān)于4階RCA的演化規(guī)則。隨機(jī)選擇規(guī)則30、90、110和150作為非均衡元胞自動(dòng)機(jī)的演化規(guī)則:1)使用偽隨機(jī)序列發(fā)生器隨機(jī)產(chǎn)生128位密鑰,記為C2)使用非均衡元胞自動(dòng)機(jī),按照規(guī)則30、90、110和150的順序?qū)3)將規(guī)則30、90、110和150循環(huán)左移一次,即150、30、90和110,作為非均衡元胞自動(dòng)機(jī)新的規(guī)則對(duì)構(gòu)形C4)繼續(xù)將規(guī)則循環(huán)左移,作為新的規(guī)則對(duì)步驟3產(chǎn)生的結(jié)果進(jìn)行演化,產(chǎn)生Φ作為密鑰空間的組成部分,演化規(guī)則的隨機(jī)選擇和移位均擴(kuò)大了傳統(tǒng)單規(guī)則元胞自動(dòng)機(jī)加密算法的密鑰空間。2.2左方圖像分解加密過(guò)程中,使用分層分解方法處理圖像的內(nèi)容,除明文圖像分解結(jié)果全部作為構(gòu)形外,其余過(guò)程只選取4個(gè)子圖像中的一塊繼續(xù)進(jìn)行四叉樹(shù)分解,每次分解結(jié)果作為構(gòu)形。為便于計(jì)算,本文選取左上角子圖像進(jìn)行分解。1)將明文圖像按照四叉樹(shù)分解策略分解成4個(gè)子圖像,并將這4個(gè)子圖像看作式(5)定義的4階RCA的4個(gè)初始化構(gòu)形C2)將2.1節(jié)中產(chǎn)生的密鑰作為RCA的演化規(guī)則,按照4階可逆元胞自動(dòng)機(jī)演化規(guī)則,對(duì)初始化構(gòu)形C3)左上角產(chǎn)生的C4)遞歸重復(fù)該過(guò)程,分離塊C特別地,最后一層數(shù)據(jù)的大小等于16個(gè)字節(jié)(128)位,對(duì)應(yīng)塊C通過(guò)逆向執(zhí)行加密過(guò)程,可從加密圖像中恢復(fù)出明文圖像。3加密網(wǎng)格地圖的實(shí)驗(yàn)和分析3.1圖像a、c#算法實(shí)驗(yàn)所用數(shù)據(jù)為3幅512×512像素、1幅1024×1024像素和1幅4096×4096像素的數(shù)字柵格地圖(分別記為圖像a、圖像b、圖像c、圖像d和圖像e)。算法通過(guò)C#語(yǔ)言和Matlab實(shí)現(xiàn),實(shí)驗(yàn)配置為Intel(R)Core(TM)i5-CPU3GHz,8GB內(nèi)存。根據(jù)統(tǒng)計(jì)分布和熵測(cè)量準(zhǔn)則等指標(biāo)評(píng)估算法安全性,在密鑰空間和算法速度方面與文獻(xiàn)[12]基于混沌的圖像加密算法、文獻(xiàn)[13]基于初等可逆元胞自動(dòng)機(jī)的圖像加密算法、文獻(xiàn)[14]基于二階可逆元胞自動(dòng)機(jī)的圖像加密算法進(jìn)行了比較。3.2結(jié)果與分析3.2.1圖像信息熵實(shí)驗(yàn)本小節(jié)通過(guò)驗(yàn)證加密圖像的不確定性評(píng)估算法的安全性。圖像信息熵越大,灰度分布越一致,算法擴(kuò)散性越好,安全性越高,理想加密圖像的信息熵理論最大值為8。圖2為圖像a、b、c明文圖像及其密文圖像。分別測(cè)試明文圖像和密文圖像的信息熵,并隨機(jī)選擇了16個(gè)子圖像數(shù)據(jù)塊(分別記為s從實(shí)驗(yàn)結(jié)果可知,每個(gè)密文圖像的整體熵非常接近理論值8,每個(gè)局部熵在重要水平的差距為5%左右,在可接受范圍內(nèi)。這就證明了密文圖像的局部熵和整體熵均滿(mǎn)足要求。3.2.2不同加密次數(shù)的密鑰空間差異為評(píng)估本文方法對(duì)明文圖像細(xì)微變化的敏感性,選擇測(cè)試圖像a、b、c、d、e,隨機(jī)改變明文圖像的一個(gè)bit,通過(guò)多輪加密對(duì)加密結(jié)果進(jìn)行NPCR和UACI評(píng)估。其中,NPCR表示兩幅不同像素所占百分比,UACI表示兩圖像之間差異的平均強(qiáng)度,以33%為標(biāo)準(zhǔn)理論值。圖3給出了不同加密次數(shù)的測(cè)試結(jié)果。由圖3中的結(jié)果可以看出,針對(duì)不同的加密次數(shù),圖像a、b、c、d和e的NPCR值和UACI值結(jié)果均高于各自理論值99%和33%,說(shuō)明基于四叉樹(shù)分解的高階元胞自動(dòng)機(jī)加密方法對(duì)明文變化具有較高的敏感性,能夠有效抵抗基于差分的明文攻擊。表3列出了本文算法和其他3種算法在相同半徑r下密鑰空間的對(duì)比。相比于另外3種算法,多演化規(guī)則和規(guī)則移位的使用,以及元胞自動(dòng)機(jī)階數(shù)的增加使得密鑰空間顯著提升。階數(shù)越高,與元胞自動(dòng)機(jī)狀態(tài)相關(guān)的鄰胞數(shù)目越多,所占密鑰空間就越多。3.2.3加密過(guò)程及算法對(duì)比根據(jù)NPCR和UACI分析,本文方法只需要進(jìn)行一次加密就能達(dá)到與現(xiàn)有算法使用多次加密相同的敏感程度。因此,與現(xiàn)有相關(guān)算法相比,避免了大量循環(huán)計(jì)算過(guò)程,加密和解密速度有較大提升。其中,解密過(guò)程與加密過(guò)程的計(jì)算過(guò)程所涉及的計(jì)算方法相同,實(shí)驗(yàn)結(jié)果表明,解密時(shí)間與加密時(shí)間基本相同。表4列出了本文算法和其他3種算法分別對(duì)5幅柵格地圖的加密時(shí)間和解密時(shí)間對(duì)比。由表4中不同算法的加密時(shí)間可知,相對(duì)于文獻(xiàn)[12]的算法,本文算法速度是其約3倍;相對(duì)于文獻(xiàn)[13]和文獻(xiàn)[14]中的算法,本文算法速度分別提高了約2倍、1.5倍。本文算法避免了反復(fù)的循環(huán)迭代過(guò)程,在加密階段,每個(gè)四叉樹(shù)分解的子圖像只加密一次,避免對(duì)所有像素進(jìn)行多次循環(huán)迭代加密的過(guò)程,省去了基于混合長(zhǎng)度塊分解和像素轉(zhuǎn)換操作所需的時(shí)間。