一種基于Logistic方程的圖像加密算法

張應(yīng)征,吳杰,涂立

(1.湖南工程職業(yè)技術(shù)學(xué)院 信息工程學(xué)院,湖南 長(zhǎng)沙,410151;2.華中科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,湖北 武漢,430074)

隨著計(jì)算機(jī)技術(shù)與互聯(lián)網(wǎng)應(yīng)用的飛速發(fā)展,信息加密技術(shù)顯得越來越重要,但傳統(tǒng)的加密方法在圖像加密方面存在局限性,如加密效率低、對(duì)大數(shù)據(jù)和像素間相關(guān)性很高的圖像加密不適用等,而混沌作為一種復(fù)雜的非線性系統(tǒng),對(duì)參數(shù)和初值的敏感度高,具有良好的遍歷性和偽隨機(jī)性,特別適用于加密,因此,近年來混沌理論被越來越多地應(yīng)用到密碼學(xué)。

本文擬首先分析混沌系統(tǒng)的特點(diǎn),在一維Logistic混沌方程的基礎(chǔ)上提出廣義Logistic方程的模型,在分析研究廣義Logistic方程的相圖軌跡基礎(chǔ)上,設(shè)計(jì)一種帶有一次耦合項(xiàng)的二維廣義Logistic方程,然后利用該方程生成一些具有隨機(jī)性的序列,再將這些序列優(yōu)化,并進(jìn)行分段映射與仿真。

1 Logistic方程

Logistic方程是一個(gè)簡(jiǎn)單的非線性方程,又叫蟲口模型[1],表示法為

其中0≤xn≤ 1,n∈ Z,0≤u≤ 4,u稱為分岔參數(shù),采用不同的u值進(jìn)行迭代計(jì)算,整個(gè)系統(tǒng)會(huì)呈現(xiàn)出不同的特性。Logistic方程產(chǎn)生的序列由x的初值x0和分岔參數(shù)u控制,其中只要任何一個(gè)值有細(xì)微的差別,經(jīng)過多次迭代計(jì)算以后,都會(huì)得到完全不同的實(shí)數(shù)序列[2],經(jīng)過迭代計(jì)算后的效果圖如圖1所示,其中縱坐標(biāo)表示輸出序列分布x的范圍;橫坐標(biāo)表示分岔參數(shù)u的取值范圍(參數(shù)u取[0,4]的值)。

由圖1可知:(1)當(dāng)0≤u≤ 1時(shí),無論選用什么樣的初值x0,經(jīng)過多次迭代計(jì)算后,最終產(chǎn)生的數(shù)值將是1個(gè)穩(wěn)定值0,在這個(gè)范圍內(nèi),系統(tǒng)沒有混沌特性;(2)當(dāng)1≤u≤ 3時(shí),產(chǎn)生的迭代值是一個(gè)穩(wěn)定的非0值;當(dāng)u大于3時(shí),系統(tǒng)將出現(xiàn)2個(gè)分岔,u=3是一個(gè)臨界點(diǎn);(3)在處,系統(tǒng)演化成4周期,也就是說,無論取什么初值xn系統(tǒng)都會(huì)穩(wěn)定地收斂到一個(gè)4周期函數(shù);當(dāng)后,大量的倍周期分支出現(xiàn)在更加窄狹的u區(qū)間間隔里,這種周期倍化的演化過程沒有限制,但相應(yīng)的u有一個(gè)極限值:u=3.569 945 67…,當(dāng)3.569 945 67＜u≤ 4時(shí)系統(tǒng)進(jìn)入混沌區(qū)間。由圖1可知,當(dāng)3.569 945 67＜u≤4,初值x0經(jīng)過迭代計(jì)算產(chǎn)生的序列是非周期性的,系統(tǒng)沒有收斂性。

美國(guó)數(shù)學(xué)家Feigenbaum得出了一個(gè)結(jié)論:一個(gè)系統(tǒng)一旦發(fā)生倍周期分岔,必然導(dǎo)致混沌[3],并從Logistic方程發(fā)現(xiàn)該系統(tǒng)由倍周期分岔通向混沌的2個(gè)普適性常數(shù),后來被稱為Feigenbaum常數(shù)[4]。Logistic方程通過迭代計(jì)算可以產(chǎn)生一序列隨機(jī)數(shù)列,這些隨機(jī)數(shù)列可以應(yīng)用于各種加密算法。加密是為了安全采取的一種手段,盡管Logistic方程有一定的優(yōu)點(diǎn),但是也存在一些安全隱患,例如混沌區(qū)存在一些空白窗,而且這些空白窗口與初始值無關(guān),即無論選取什么樣的初始值x0,空白窗都會(huì)存在。如圖2所示,空白窗口出現(xiàn)在u=3.829的附近,在這些窗口中產(chǎn)生的序列只有少數(shù)的幾個(gè)值,由此得到的序列沒有隨機(jī)性,而是幾個(gè)確定的數(shù)值,用“空白窗”區(qū)間的序列來加密,系統(tǒng)沒有任何安全性[5],因此加密時(shí)必須避開“空白窗”。

Logistic方程的另一個(gè)缺點(diǎn)就是,在Logistic方程的混沌區(qū)間3.569 945 67＜u≤4,如果分支參數(shù)u不等于4,那么得到的混沌序列就不會(huì)均勻分布在[0,1]區(qū)間,有的值無法取到,系統(tǒng)也就不存在遍歷性,例如,由圖2可知,如果選取分支參數(shù)u=3.75,無論經(jīng)過多少次迭代計(jì)算,都不可能得到xn=0.1的值。要獲得在[0,1]區(qū)間具有良好的隨機(jī)性和遍歷性的混沌序列,那么就只有選取根分支參數(shù)u=4.0,但是這等于是把密鑰告訴了攻擊者,使得加密算法失去了意義,因而加密者有必要設(shè)計(jì)一種更加優(yōu)越的混沌方程。

2 廣義Logistic方程及其分析

在經(jīng)典Logistic方程的基礎(chǔ)上研究廣義Logistic方程[6]

其中參數(shù)的選擇范圍為:m∈Z,n∈Z,0＜xi＜1。

首先分析k的變化范圍。因?yàn)閒'(x)=kxm-1(1-x)n-1[m(1-x) -nx],f'(x)在區(qū)間[0,1]內(nèi)僅存在1個(gè)零點(diǎn),故f(x)在該區(qū)間內(nèi)為單峰函數(shù),且峰值為最大值。

為得到系統(tǒng)精確的分岔圖,曾有人采用K均值聚類算法提取迭代數(shù)據(jù)中獲得系統(tǒng)收斂的解[7],聚類的計(jì)算量非常大,而且算法復(fù)雜,并且當(dāng)分岔解的個(gè)數(shù)增加時(shí),聚類數(shù)以2的冪次增加,如果需要獲得一定的精度,則需要很大的樣本空間,聚類法其實(shí)并不適用于求解混沌系統(tǒng)的精確分插圖。

以下計(jì)算特定的m和n參數(shù)下廣義Logistic方程的Feigenbaum第一常數(shù),從理論上證明廣義Logistic方程同樣具有混沌特性。注意到計(jì)算Feigenbaum第一常數(shù),并不需要把所有分岔點(diǎn)對(duì)應(yīng)的x,k值計(jì)算出來,進(jìn)而注意到在分岔點(diǎn)處,x對(duì)k的斜率存在突變,因此選擇分岔點(diǎn)處的k值即可,而經(jīng)過足夠次迭代后迭代數(shù)據(jù)中的xmax是容易計(jì)算的。實(shí)驗(yàn)證明系統(tǒng)在分岔點(diǎn)處存在比較明顯的變化,當(dāng)分岔點(diǎn)增多時(shí),需要對(duì)k值作更加細(xì)致的研究。最后得到的經(jīng)典Logistic方程以及m=2,n=1時(shí)的廣義Logistic方程在各分岔點(diǎn)處的k值,迭代關(guān)系式為xi+1=kx2(1-xi)從而得出 Feigenbaum第一常數(shù),數(shù)據(jù)如表1所示。

表1 Feigenbaum第一常數(shù)(m=2,n=1)

由表1可知,廣義Logistic關(guān)系式[8]xi+1=kx2(1-xi)的Feigenbaum第一常數(shù)趨近于4.6(本研究暫時(shí)只討論特定m值和n值下廣義Logistic的混沌特性,并不需要研究該方程的Feigenbaum常數(shù)的精確值,所以這里只給出一個(gè)近似值)。

標(biāo)準(zhǔn)Logistic方程以及m=1,n=2時(shí)的廣義Logistic方程各分岔點(diǎn)處的k值,迭代關(guān)系式為:xi+1=kx(1-xi)2得出的Feigenbaum第一常數(shù)如表2所示。

表2 Feigenbaum第一常數(shù)(m=1,n=2)

由表2可知,當(dāng)?shù)P(guān)系式為xi+1=kx(1-xi)2時(shí),Feigenbaum第一常數(shù)趨近于4.6(由于計(jì)算時(shí)精度的選取關(guān)系,所以結(jié)果只是1個(gè)近似值)。

3 二維廣義Logistic方程及其不動(dòng)點(diǎn)分析

在廣義Logistic方程的基礎(chǔ)上,將二維廣義Logistic混沌方程改進(jìn)為

其中:x∈(0,1),y∈(0,1),n∈Z,u1=u2=u∈[0,1.2],r∈(0,1),其動(dòng)力學(xué)行為是由u1,u2,r1,r2以及初始值x0和y0這6個(gè)控制參數(shù)所決定的。通過選取不同的控制參數(shù)組合,對(duì)系統(tǒng)的動(dòng)力學(xué)行為進(jìn)行全面的考察。如圖3所示,縱坐標(biāo)表示輸出序列分布y的取值范圍,分岔參數(shù)u的取值范圍用橫坐標(biāo)表示,參數(shù)u的取值區(qū)間為[0,1.2],初始值x1=0.10,y1=0.11,r1=r2=0.1。

同理用縱坐標(biāo)表示輸出序列分布x的取值范圍,分岔參數(shù)u的取值范圍用橫坐標(biāo)表示,參數(shù)u取值區(qū)間為[0,1.2],初始值選取x1=0.10,y1=0.11,迭代計(jì)算后的分岔圖如圖4所示。

通過對(duì)二維廣義Logistic方程的研究和實(shí)驗(yàn),可知從整體上來說二維廣義Logistic方程得到的分岔圖和Logistic方程結(jié)構(gòu)很相似,它具有經(jīng)典Logistic方程應(yīng)有的特性。從局部來看,二維廣義Logistic方程的混沌區(qū)間發(fā)生了很大的變化,如參數(shù)u的取值范圍就發(fā)生了很大的變化,二維廣義Logistic方程比經(jīng)典Logistic方程更加優(yōu)越。更重要的是二維廣義Logistic方程混沌區(qū)的混沌密度更高,且空隙距離縮小,二維廣義Logistic方程的迭代圖如圖5所示。

為了在控制參數(shù)空間對(duì)二維廣義Logistic方程的演化行為進(jìn)行全面的研究,本研究選擇性地選取不同的參數(shù),作出二維廣義Logistic方程的相圖(見圖6),第一條軌跡線為u1=u2=u∈[0.2,1.0]選取的初始點(diǎn),當(dāng)u=0.2時(shí),系統(tǒng)趨向于相平面的一個(gè)穩(wěn)定不動(dòng)的點(diǎn);隨著r的增大,當(dāng)u=0.3時(shí),相平面出現(xiàn)了2個(gè)穩(wěn)定的不動(dòng)點(diǎn)。而當(dāng)u=0.888時(shí),2個(gè)不動(dòng)點(diǎn)失穩(wěn),新的穩(wěn)定狀態(tài)圍繞著原有的2個(gè)點(diǎn)演變?yōu)?條曲線(圖6(a));u=0.92時(shí),4條曲線演變?yōu)橐粭l不規(guī)則的開口曲線(圖6(b));u=0.95時(shí),進(jìn)一步變化,相平面演化成奇怪吸引子(圖6(c));吸引子是描述運(yùn)動(dòng)的收斂類型,也就是當(dāng)時(shí)間趨向于無窮大時(shí),系統(tǒng)出發(fā)的非定常流的所有軌道都趨于某個(gè)穩(wěn)定的范圍(這種范圍有復(fù)雜的幾何結(jié)構(gòu))。隨著u的不斷增大到0.99時(shí),系統(tǒng)又出現(xiàn)穩(wěn)定的不動(dòng)點(diǎn)(圖6(d)),但是這些不動(dòng)點(diǎn)數(shù)量較多,也就是說,給系統(tǒng)一個(gè)初始值x1,系統(tǒng)最后都會(huì)收斂到這些點(diǎn)上,或者說系統(tǒng)是一個(gè)多周期函數(shù),這個(gè)函數(shù)的周期數(shù)就是這些不動(dòng)點(diǎn)的個(gè)數(shù);當(dāng)u=1.0時(shí)系統(tǒng)出現(xiàn)越界,數(shù)值變得不可控,也不可預(yù)測(cè)。

圖7、8、9是用相空間重構(gòu)法的描述的二維廣義Logistic方程的奇怪吸引子[9]。

由圖6～9得到二維廣義Logistic方程的奇怪吸引子的特點(diǎn):

(1)從整體來看,二維廣義Logistic方程系統(tǒng)是穩(wěn)定的,吸引子外的一切運(yùn)動(dòng)最后都會(huì)收斂到吸引子內(nèi)部,而內(nèi)部吸引子的運(yùn)動(dòng)是不穩(wěn)定的,類似于混沌;

(2)奇怪吸引子不一定都是集中的,有一些是分散的,或者稀疏的分布。從而這些奇怪吸引子具有無窮層次的機(jī)構(gòu)相似性;

(3)由二維廣義Logistic方程xn/xn+1=f(x)=xn/[uxn(1 -xn)]得到u(1 -xn),當(dāng),由此得到的是一個(gè)一元二次方程,即開口向下的拋物線。如圖7所示。

通過理論分析和實(shí)驗(yàn)仿真得到如下的結(jié)論,當(dāng)控制參數(shù)u1,u2相差較大,得到的結(jié)果大有區(qū)別。研究u1=0.72,u2=0.28且r∈(0.1,0.75)時(shí)二維廣義Logistic方程系統(tǒng)行為的演化規(guī)律,二維廣義Logistic方程的迭代分岔圖如圖10、11所示。當(dāng)u1=0.8,u2=0.2、且r∈[0,0.6]時(shí)系統(tǒng)行為演變規(guī)律,如圖12、13所示。

4 分段映射與仿真

分段線性映射是一種一維映射,這里通過對(duì)一般分段線性映射進(jìn)行有效改進(jìn),得到如下的分段余弦函數(shù)(Piecewise cosine chaotic map,PCCM)[10],該方程為

其中,yn為初始混沌的序列值,且yn∈(0,1);t為系統(tǒng)的控制參數(shù),并且t∈(0,0.5)。仿真實(shí)驗(yàn)證明,這種改進(jìn)后的分段余弦映射具有很好的混沌特性和復(fù)雜的動(dòng)力學(xué)行為。

通?？梢允褂眯蛄械幕ハ嚓P(guān)函數(shù)進(jìn)行量化分析,用來衡量混沌序列的性能優(yōu)劣。當(dāng)互相關(guān)函數(shù)值越小,表明被測(cè)序列的偽隨機(jī)性越好?；ハ嚓P(guān)函數(shù)的定義為

其中,xk、yk是在二元域[-1,1]上長(zhǎng)度為p的2個(gè)混沌序列。

互相關(guān)性的分析是指在混沌方程中參數(shù)x1,r,u,y1等系統(tǒng)初值作微小的變化情況下,序列的相似度。如果互相關(guān)性越小,說明其混沌序列更好,反之則越差。

取初值u=3.9,x1=0.1和初值x1=0.1+10-15,利用Logistic方程進(jìn)行迭代計(jì)算,分別生成2個(gè)具有1 000個(gè)迭代值的混沌序列,對(duì)這2個(gè)序列進(jìn)行互相關(guān)性實(shí)驗(yàn)測(cè)試,并將測(cè)試的結(jié)果以圖像的形式直觀表示,結(jié)果如圖14所示,經(jīng)典Logistic混沌方程生成的混沌具有較小的互相關(guān)性,其相關(guān)性系數(shù)在0.35左右,因此經(jīng)典Logistic方程生成的混沌序列具有較好的偽隨機(jī)性。

取2組初值:u=0.958,x1=0.10,y1=0.11,r=0.1和x2=0.10+10-15,y2=0.10+10-15時(shí),利用二維廣義Logistic方程進(jìn)行迭代計(jì)算,分別生成2個(gè)具有1 000個(gè)迭代值的混沌序列,對(duì)這2個(gè)序列進(jìn)行互相關(guān)性實(shí)驗(yàn)測(cè)試,用來量化分析二維廣義Logistic方程的性質(zhì),實(shí)驗(yàn)仿真結(jié)果如圖15、16所示。

由圖15可知,二維廣義Logistic混沌方程生成的x1與x2序列的互相關(guān)性比較小,其相關(guān)性系數(shù)基本在0.22左右,因此二維廣義Logistic方程生成的代表x向量的混沌序列具有良好的偽隨機(jī)性。

由圖16可知,二維廣義Logistic混沌方程生成的y1和y2的互相關(guān)性也比較小,其相關(guān)性系數(shù)基本在0.004 8左右,因此二維廣義Logistic方程生成的代表y向量的混沌序列也具有很好的偽隨機(jī)性。

由式(1)、(3)的結(jié)果可知,二維廣義Logistic混沌方程不管從x序列或者y序列方面來看,其互相性關(guān)系數(shù)均小于傳統(tǒng)Logistic混沌方程的互相關(guān)性系數(shù),可以說明,由二維廣義Logistic方程生成的混沌序列比由經(jīng)典Logistic方程生成的混沌具有更好的偽隨機(jī)性。

由二維廣義Logistic方程方程生成混沌序列,其中取初值x1=0.10,y1=0.11,r1=0.1,u=0.958,經(jīng)過迭代65 536次得到y(tǒng)序列,然后取y序列的值代入式(4)進(jìn)行分段計(jì)算,其分段余弦映射(Piecewise cosine chaotic map,PCCM)方程式(4)中的t=0.4。結(jié)果見表3。

表3 分段前后的序列信息

上述仿真結(jié)果證明,二維廣義Logistic方程生成的混沌序列本身比經(jīng)典Logistic方程生成的混沌序列優(yōu)越,再通過分段映射方程對(duì)其混沌序列進(jìn)一步的優(yōu)化,這樣就有利于混沌序列的又一次隨機(jī)變化,由二維廣義Logistic方程生成的混沌序列經(jīng)過上述的優(yōu)化,更加有利于圖像加密。