圖像作為信息密集的載體，包含著非常重要的信息，但其驚人的數(shù)據(jù)量阻礙了傳統(tǒng)密碼學(xué)對于圖像信息安全的應(yīng)用，而且傳統(tǒng)的加密技術(shù)將圖像作為普通數(shù)據(jù)流加密，而沒有考慮多媒數(shù)據(jù)的特點。近年隨著計算機處理效率的提高，圖像信息的安全處理得到了進一步的發(fā)展，出現(xiàn)了許多關(guān)于圖像加密的新算法，主要包括：圖像置亂技術(shù)、圖像隱藏技術(shù)和圖像加密技術(shù)。

而二維細胞自動機數(shù)學(xué)原理與圖像加密技術(shù)的結(jié)合更是圖像加密技術(shù)的一個新的突破，為此我們提出了一種基于二維細胞自動機的圖像加密算法。它具有簡單易實現(xiàn)、安全性高、密鑰量大、良好的雪崩效應(yīng)以及擴散與混淆的性質(zhì)，運算簡單和加密速度快等優(yōu)點，是一種具有發(fā)展?jié)摿Φ膱D像加密算法。

一、細胞自動機的數(shù)學(xué)原理

1、 d維細胞自動機定義描述

細胞自動機包括以下6部分：

1）基本空間Zd，表示d維直角坐標系中具有整數(shù)坐標格點的集合，在每個格點上假設(shè)有1個細胞，通常細胞也用這個格點的直角坐標（X1，X2，...，Xd）表示。

2）狀態(tài)集合Q，表示細胞狀態(tài)的集合，一般取Q={0，1｝，每1個細胞都有1個狀態(tài)。

3）配置空間Ⅱ。所有細胞的狀態(tài)合起來稱為配置，所有可能的配置構(gòu)成的集合稱為配置空間。配置是與時刻聯(lián)系在一起的，t時刻的配置記為G，某個細胞c在t時刻的狀態(tài)用Ct（ c）表示。

4）鄰域B。如果某個細胞c和d維直角坐標是（X1，X2，...，Xd），那么B（c）=｛y1，y2，...，yd）：|yi-xi|≤1，1≥i≤d}就是這個細胞的鄰域。易見，d維細胞自動機中1個細胞的鄰域內(nèi)恰好有3d個細胞。

5）局部規(guī)則f，表示作用在細胞鄰域上的局部規(guī)則，它是有3d個變量的函數(shù)，變量與函數(shù)值都取值于Q。

6）整體變換pf，表示由f導(dǎo)出的Ⅱ的整體變換。對于時刻t的配置Ct，，pf作用在Ct上得到的時刻t+1的配置Ct+1，而在配置Ct+1里任一個細胞的狀態(tài)就是，在t時刻的細胞c的鄰域的作用結(jié)果，也可表示為Ct+1（c）=f（Ct（B（c））），Vc∈Zd。

2、二維細胞自動機的具體描述

因為圖像是由平面坐標像素點組成，是在二維的平面上，因此以二維細胞自動機為例。

二維細胞自動機的基本空間是之，是二維直角坐標系中坐標均為整數(shù)的所有格點的集合，每個細胞都在某一格點上，也即可以用（a，b）來表示1個細胞。每個細胞只有0或1兩個狀態(tài)，其鄰域是由（a±1，b）、（a，b±1）、（a±1，b±1）和（a，b）共9個細胞組成的集合。f可以用圖示法表示，如圖1所示。

如果從左上角先水平后豎值到右下角給這9個相對位置排序，那么f就可以用

表示。

注意，式中每一等式對應(yīng)于圖1的一個框圖，如f（111111111）=ε512對應(yīng)于圖1最后的框圖，f（111111111）的函數(shù)值為ε512，其中ε512或者為1或者為0。

為了方便，以序列ε1ε2…ε511ε512來表示f。為了減少書寫序列的長度，可以考慮用128bit，16進制數(shù)來表示512bit二進制數(shù)ε1ε2…ε511ε512。如（09AB43CE）16表示由16個同樣的09AB43CE合在一起組成的128bit，16進制數(shù)，它就表示一局部規(guī)則。

設(shè)t=0時刻的初始配置是C0，對任意一細胞，假設(shè)其鄰域內(nèi)細胞的狀態(tài)如圖2所示。

那么，這個細胞在t=1時的狀態(tài)就是f（X1，X2，X3，X4，X5，X6，X7，X8，X9）。所有細胞在t=1時的狀態(tài)都可以用這種方法得到，合在一起就是t=1時刻的配置C1。這樣從t=0時的配置C0得到t=1時的配置C1可以看作是通過f的并行局部作用導(dǎo)出的一整體規(guī)則ρf作用在C0上的結(jié)果。將ρf再次作用在C1上，就能得到t=2時的配置C2，并依次可得到t=3、t=4……時的配置C3、C4……。

3、雪崩效應(yīng)的重要作用　　

在二維細胞自動機中，對任一細胞，它在t=1時的狀態(tài)取決于f對它的鄰域（也二維坐標分量與其相差不過1的細胞的集合）在t=0時的狀態(tài)的作用結(jié)果，而它在t=2時的狀態(tài)取決于f對它的超鄰域（二維坐標分量與其相差不過2的細胞的集合）在t=0時狀態(tài)的作用結(jié)果。依次類推，它在t=n時的狀態(tài)取決于f對二維坐標分量與其相差不過n的所有細胞在t=0時狀態(tài)的作用結(jié)果。因此，在n相當大時，一般的細胞自動機都存在著明顯的雪崩效應(yīng)。這包括2個方面：

1）當在t=0時某個細胞的狀態(tài)有所改變，將會在t=n時影響到鄰近大范圍細胞的狀態(tài)；

2）當2個細胞自動機在初始時刻的配置完全相同，但是f存在著細微差異，那么在t=n時的配置就會有驚人的差異。這一點，也是本文作為文件加密的理論基礎(chǔ)。

二、運用二維細胞自動機的圖像加密算法描述和解釋　

二維細胞自動機中，細胞是分布在Z2上的，也即在無窮大平面的格點上，而一般的圖像都是有限長和有限寬的，因此為了在圖像上應(yīng)用二維細胞自動機，必須在技術(shù)上做一些處理。解決的一般方法是將圖像看作在一拓撲環(huán)面上，即認為圖像的右邊界與左邊界連在一起，上邊界和下邊界連在一起。這樣，不僅圖像的中間點具有9個鄰域點，而且圖像的邊界點也有9個鄰域點（包括若干對應(yīng)相反邊界的點）。

以黑白二值圖像為例，說明如何應(yīng)用二維細胞自動機對圖像加密。對于W×H的黑白二值圖像，把圖像的每個像素點看作是1個細胞，像素點的黑白值看成細胞的狀態(tài)。由于是黑白二值圖像，因此可以認為黑、白分別表示該像素點所代表細胞的狀態(tài)為1或0。當需要傳輸W×H秘密圖像時，發(fā)送方和接收方先約定一共同的f和一共同的時刻t=n。注意n不應(yīng)太小，否則會影響保密性。

1、運用二維細胞自動機的圖像加密算法　

1）對于任一需要加密的原始圖像M，先產(chǎn)生與其相同大小的原始隨機黑白二值圖像RM，作為t=0時的配置。

2）用雙方約定好的f連續(xù)作用在隨機圖上n次，得到t=n的配置，也就是一幅新的隨機黑白二值圖像Cn（RM）。

3）把Cn（RM）和需加密的M進行Xor異或運算，得到密圖N=Cn（RM）+M。

4）發(fā)送方傳輸RM|N，即發(fā)送方把原始隨機黑白二值圖像與黑白二值密圖連在一起發(fā)送給接收方。

2、運用二維細胞自動機的圖像解密算法

1）接收方分解RM|N，即接收方把接收到的圖像分為原始隨機黑白二值圖像RM和黑白二值密圖N兩部分。

2）把RM當作t=0時的配置，用雙方約定好的細胞自動機變換f作用RM上n次，得到t=n的配置，也就是Cn（RM）。

3）把Cn（RM）和黑白二值密圖N進行異或運算，即能得到發(fā)送方原先進行加密的黑白二值圖像，這是因為Cn（RM）+N=Cn（RM）+（Cn（RM）+M）=M。

這種基于細胞自動機的圖像加解密算法可以適用于灰度圖像。記灰度圖像的灰度矩陣為（Pi×j）W×H，只要把灰度圖像每個像素的灰度（Pi×j）的值（0～255間）化為長度為8的二進制Pi×j=d0i×jd1　i×j…d7i×j，將（Pi×j）W×H等價于8個二值圖像（dki×j）W×H，（0≤k≤7），上述圖像加解密算法就可以使用。利用這種思路，彩色圖像的加解密算法可由上述算法適當推廣即得。

三、運用二維細胞自動機的圖像加密實驗

仍以灰度圖為例，需要加密的Barbara圖像如3所示。

任意選取f并設(shè)定n值為9，按照上述的加密方法進行操作，可以得到加密后的密圖（圖4）發(fā)送給接收方。圖4中，（a）是隨機原始圖，（b）是密圖。

接受方按照上述解密方法進行操作，可以得到解密后的圖像如圖5示，它與原始加密圖像（圖3）完全相同。

四、運用二維細胞自動機的圖像加密算法的優(yōu)點及安全性分析

1、基于二維細胞自動機圖像加密算法的優(yōu)點

1）密鑰量大，安全性好。當n相當大時，每一像素在t=n時的像素值嚴格取決于f和所有像素在t=0時的像素值，具有明顯的雪崩效應(yīng)。例如，在加密實驗中對使用的f稍稍改動，僅把f（010010101）的值改變?yōu)?-f（010010101），再次對圖3進行加密，使用同樣的原始隨機圖，n也保持不變，得到的新的密圖如圖6示。

將兩幅密圖進行點異或運算得到圖7?？梢?，f稍微改變一點，兩圖就有極大的差異，細胞自動機的雪崩效應(yīng)使得密文的每一位受明文中的多位影響，隨著t的增加，細胞自動機規(guī)則的進化使得密文和密鑰間的統(tǒng)計關(guān)系也變得復(fù)雜。因此，基于二維細胞自動機的圖像加密方法具有很好的擴散和混淆性質(zhì)。

從細胞自動機的雪崩效應(yīng)可以看出，攻擊者要破譯加密算法，找到局部規(guī)則f和時刻n是關(guān)鍵，f和n就是運用細胞自動機圖像加密算法的密鑰。但是由圖1可以看出，f的自變量的集合共有512個元素，每一個自變量所對應(yīng)的函數(shù)的不同就導(dǎo)致f有差異。也就是說，所用的二維細胞自動機的f共有2512個。f的選取范圍可以進一步擴大。可以考慮以與某個像素點的棋盤距離不大于2的所有像素點作為該像素的鄰域，這樣對應(yīng)到二維細胞自動機中1個細胞的鄰域就包括25個細胞，f的自變量有225個，而f的總數(shù)達到233554432，這使得整個算法的密鑰量更大，保密性更強，而對于加密和解密速度卻沒有太大的影響，使用蠻力搜索攻擊將遭遇不可思議的困難。這個密鑰量遠大于文獻[12]中提到的對于256×256圖像下界為109536的密鑰量，以及目前許多文獻提到基于混沌的圖像加密算法，如基于離散混沌系統(tǒng)廣義同步定理的數(shù)字圖像加密方案密鑰量為1076，基于廣義Chen’s混沌系統(tǒng)的圖像加密算法密鑰量為2149，基于混沌映射的圖像加密算法密鑰量為2256。

2）規(guī)則具有可復(fù)合性，抗攻擊性強。發(fā)送方和接收方可以共同約定2個局部規(guī)則f和g，加密時先用f再用g循環(huán)作用在隨機圖上，這樣即增加了破譯的難度，同時也增加了密鑰的數(shù)量。利用不同局部規(guī)則復(fù)合的思想，基于二維細胞自動機的圖像加密算法具有更強的抗攻擊性，而文獻[12]所用的方法顯然不具有這種性質(zhì)。

3）加密效率高，運算簡單。假設(shè)已有一長寬分別為l和w的二值圖，按照我們的加密方法需要產(chǎn)生一l×w的隨機二值圖，然后對這個隨機圖進行基于二維細胞自動機規(guī)則的變換。對于隨機圖的每一個像素，得到它變換后對應(yīng)的像素需要先尋找它周圍的24個像素，然后對這25個像素尋找二維細胞自動機規(guī)則的對應(yīng)局部規(guī)則，而這種尋找在細胞自動機規(guī)則放入內(nèi)存后應(yīng)該是O（1）時間，然后代入這個局部規(guī)則對應(yīng)的數(shù)，就得到變換后的圖像中這個像素所對應(yīng)的數(shù)值。計算起來總共有l(wèi)×w個查找和代入過程，由于迭代次數(shù)為n，此時的時間復(fù)雜性為O（n×l×w）。然后把新的變換后的隨機圖和原圖作異或又需要l×w次異或運算?？紤]到1個灰度圖可以看作是8個二值圖疊加而來，所以按照我們的方法，由原是l3w大小的灰度圖，最后得到l×w大小的灰度密圖，總共的時間復(fù)雜度為O（8×n×l×w）+O（8×l×w）=O（n×l×w）。當n給定時，時間復(fù)雜度即為O（l×w）。在任意選定一f（比如前面提到的16進制數(shù)（09AB43CE）16的表示的局部規(guī)則）和t=9，鄰域值只設(shè)定為9的條件下，在CPU為Pentium（R）4CPU2.60GHz、內(nèi)存為512MB機器配置下，對于128×128的灰度圖，加密時間為0.06s。而文獻[12]所用的方法雖然時間復(fù)雜度本質(zhì)上與二維細胞自動機圖像加密算法相同，但是它首先要采用S細胞自動機N技術(shù)重置圖像的像素值，并且需要消耗將二維數(shù)據(jù)向一維數(shù)據(jù)轉(zhuǎn)換的時間，解密后的數(shù)據(jù)還要重排，加上復(fù)雜的運算步驟因而加密速度小于基于二維細胞自動機圖像加密算法。

細胞自動機是解決局部與整體聯(lián)系問題的強有力的數(shù)學(xué)工具，近年細胞自動機在傳統(tǒng)密碼學(xué)中已經(jīng)有了相當多的運用。由于細胞自動機模型的普遍性，細胞自動機也可以應(yīng)用于圖像處理，本文提出的基于二維細胞自動機的圖像加密算法僅是其中一個實例?？梢灶A(yù)期，細胞自動機在圖像的安全與處理中的應(yīng)用將會得到更廣泛的進展。

admin

收藏 海報分享