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

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

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

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

1 Logistic方程

Logistic方程是一個簡單的非線性方程,又叫蟲口模型[1],表示法為

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

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

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

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

2 廣義Logistic方程及其分析

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

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

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

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

以下計算特定的m和n參數(shù)下廣義Logistic方程的Feigenbaum第一常數(shù),從理論上證明廣義Logistic方程同樣具有混沌特性。注意到計算Feigenbaum第一常數(shù),并不需要把所有分岔點對應(yīng)的x,k值計算出來,進(jìn)而注意到在分岔點處,x對k的斜率存在突變,因此選擇分岔點處的k值即可,而經(jīng)過足夠次迭代后迭代數(shù)據(jù)中的xmax是容易計算的。實驗證明系統(tǒng)在分岔點處存在比較明顯的變化,當(dāng)分岔點增多時,需要對k值作更加細(xì)致的研究。最后得到的經(jīng)典Logistic方程以及m=2,n=1時的廣義Logistic方程在各分岔點處的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(本研究暫時只討論特定m值和n值下廣義Logistic的混沌特性,并不需要研究該方程的Feigenbaum常數(shù)的精確值,所以這里只給出一個近似值)。

標(biāo)準(zhǔn)Logistic方程以及m=1,n=2時的廣義Logistic方程各分岔點處的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時,Feigenbaum第一常數(shù)趨近于4.6(由于計算時精度的選取關(guān)系,所以結(jié)果只是1個近似值)。

3 二維廣義Logistic方程及其不動點分析

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

其中:x∈(0,1),y∈(0,1),n∈Z,u1=u2=u∈[0,1.2],r∈(0,1),其動力學(xué)行為是由u1,u2,r1,r2以及初始值x0和y0這6個控制參數(shù)所決定的。通過選取不同的控制參數(shù)組合,對系統(tǒ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,迭代計算后的分岔圖如圖4所示。

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

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

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

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

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

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

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

4 分段映射與仿真

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

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

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

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

互相關(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)行迭代計算,分別生成2個具有1 000個迭代值的混沌序列,對這2個序列進(jìn)行互相關(guān)性實驗測試,并將測試的結(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時,利用二維廣義Logistic方程進(jìn)行迭代計算,分別生成2個具有1 000個迭代值的混沌序列,對這2個序列進(jìn)行互相關(guān)性實驗測試,用來量化分析二維廣義Logistic方程的性質(zhì),實驗仿真結(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)行分段計算,其分段余弦映射(Piecewise cosine chaotic map,PCCM)方程式(4)中的t=0.4。結(jié)果見表3。

表3 分段前后的序列信息

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