董有恒,趙耿,,馬英杰
(1.北京郵電大學網(wǎng)絡(luò)空間安全學院,北京 100089;2.北京電子科技學院網(wǎng)絡(luò)空間安全系,北京 100071)
混沌系統(tǒng)是一類確定性的動力系統(tǒng),擁有遍歷性、偽隨機性、不可預(yù)測性以及初值敏感性等特殊性質(zhì)[1-2]。自從Lorenz[3]于1963 年模擬天氣預(yù)報時得到第一個經(jīng)典的混沌動力系統(tǒng)后,多種混沌動力系統(tǒng)和混沌映射相繼涌現(xiàn)出來,包括Logistics 映射[4]、Henon 映射、Chebyshev 映射[5]、帳篷映射[6]以及將多個混沌映射混雜在一起的混雜混沌系統(tǒng)[7-8]等。這些系統(tǒng)被廣泛應(yīng)用于多個領(lǐng)域,尤其是在密碼學方向。因為混沌系統(tǒng)的不可預(yù)測性和初值敏感性與密碼學的要求十分契合,所以混沌系統(tǒng)已經(jīng)應(yīng)用于密碼學中的多個方面,如圖像加密[9-13]、S-盒的生成[14-15]、流密碼[16-18]等。然而,混沌系統(tǒng)在有限精度的數(shù)字系統(tǒng)中運行時會不可避免地出現(xiàn)動力學特性退化[19-21]的現(xiàn)象,導(dǎo)致系統(tǒng)的周期變短,偽隨機性被破壞。為了解決這一問題,學者提出了大量的方案,這些方案主要分為以下三類:提高系統(tǒng)的運算精度[22]、將多個混沌系統(tǒng)進行串聯(lián)[23]、添加擾動[24],其中最有效的方法是添加擾動,而擾動系統(tǒng)的輸出相比于擾動控制參數(shù)和輸入更有效[19]。
時空混沌系統(tǒng)[25-28]由于利用了空間上的耦合,不同位置的混沌系統(tǒng)輸出通過耦合能夠互相擾動,從而有效削弱了動力學特性退化的影響,因此擁有更強的混沌特性,逐漸成為混沌系統(tǒng)的研究熱點。耦合映像格(CML,coupled map lattices)系統(tǒng)[29-30]這一啟發(fā)式的設(shè)計方案被提出后,多種基于CML的時空混沌系統(tǒng)被提出,其中包括基于一維CML[9,31-32]和基于高維CML[14,17,33]的兩類時空混沌系統(tǒng)。后者的數(shù)據(jù)吞吐量以及系統(tǒng)的復(fù)雜性比前者好,因此,其在S-盒生成和圖像加密等數(shù)據(jù)量要求較大的密碼系統(tǒng)中擁有更好的適用性?;诙SCML 的時空混沌系統(tǒng)設(shè)計和應(yīng)用更廣泛,文獻[33-34]基于Arnold 映射提出了一種二維非線性耦合映像格系統(tǒng)并應(yīng)用于圖像加密中,研究表明該系統(tǒng)擁有較強的混沌特性,然而在某些控制參數(shù)下,該系統(tǒng)依然存在弱混沌的現(xiàn)象,而且處于混沌狀態(tài)的格子數(shù)占比并不高,此外周期窗口依然存在于它的分岔圖中。Zhou 等[14]基于PWLCM-Sin 映射提出了一種二維混合偽隨機耦合映像格系統(tǒng),該系統(tǒng)有效減少了系統(tǒng)分岔圖中的周期窗口,增強了系統(tǒng)的非周期性。然而,該系統(tǒng)的回歸映射呈現(xiàn)明顯的集中狀態(tài),生成序列的分布并不均勻,易受到回歸映射分析[35]攻擊。Liu 等[17]基于分段logistics 映射提出了一種添加了偏移量的二維耦合映像格系統(tǒng),該系統(tǒng)有效減少了周期窗口,并且實現(xiàn)了生成序列的均勻化,然而,對于某一固定的格子,其每回合施加的偏移量是根據(jù)格子索引和映像格系統(tǒng)的大小決定的,偏移量是固定的而非變化的,因此安全性有待提升。
為了解決上述存在的問題,在先前的工作中已經(jīng)提出了一種一維的偽隨機耦合映像格(PRCML,pseudo-random coupled map lattices)系統(tǒng)[36],但由于該系統(tǒng)是一維的,數(shù)據(jù)量吞吐量和應(yīng)用場景有限,為了進一步改進和優(yōu)化,本文基于分區(qū)初等元胞自動機提出了一種二維偽隨機耦合映像格(2D-PRCML,two-dimensional pseudo-random coupled map lattices)系統(tǒng),主要貢獻如下。
1)對于二維耦合映像格系統(tǒng),耦合計算的過程中需要2 個維度的格子索引,為了滿足這一數(shù)據(jù)需求,本文基于全局混沌的一維初等元胞自動機[37]設(shè)計了一種分區(qū)初等元胞自動機(PECA,partitioned elementary cellular automata),該自動機的迭代結(jié)果具有良好的長周期性和偽隨機性。
2)基于PECA 的迭代結(jié)果,設(shè)計了一種偽隨機的耦合方案。該方案中對某一固定格子的耦合隨著系統(tǒng)迭代進行不斷偽隨機變化。這不僅增強了系統(tǒng)的混沌特性,而且加快了迭代過程中系統(tǒng)的能量傳遞。
3)PECA 的迭代結(jié)果通過進制轉(zhuǎn)換和歸一化后,作為偽隨機擾動添加至系統(tǒng)中。首先,由于PECA 本質(zhì)上是一個離散的動力系統(tǒng),因此不存在動力學特性退化的問題,其輸出作為擾動能夠進一步減弱2D-PRCML 系統(tǒng)的退化問題。其次,這一擾動的絕對值和符號都是根據(jù)PECA 得到的,因此也是偽隨機變化的。分析結(jié)果表明,系統(tǒng)的非周期性、遍歷性和序列的分布均勻性均得到改善,且各格子生成的序列之間的相關(guān)性顯著降低。
在二維時空混沌系統(tǒng)中,典型的二維耦合映像格(2D-CML,two-dimensional coupled map lattices)[38]系統(tǒng)表達式為
其中,時間維度n=1,2,3,…,空間維度i=1,2,3,…,R和j=1,2,3,…,L,整個耦合映像格系統(tǒng)中格子空間大小為RL,耦合強度ε∈(0,1),該系統(tǒng)的邊界條件為
混沌映射f(x)一般為logistics 映射,該映射的數(shù)學表達式為
其中,控制參數(shù)μ∈(0,4],當3.57<μ≤4 時,該映射處于混沌狀態(tài)[9]。x的取值范圍為(0,1)。很顯然,這種典型的2D-CML 系統(tǒng)的耦合方式是鄰近耦合。
元胞自動機(CA,cellular automata)的概念由Neumann 等[39]提出。CA 是一種在空間和時間上都離散的動力系統(tǒng),該系統(tǒng)最初用來模擬生命系統(tǒng)中的自我復(fù)制現(xiàn)象,也是自然界中復(fù)雜現(xiàn)象的一種簡化模型[40]。它主要由元胞、元胞空間、元胞鄰居和迭代規(guī)則以及邊界條件等構(gòu)成。
初等元胞自動機(ECA,elementary cellular automata)是一種簡單的一維元胞自動機[6]。在ECA中,各元胞只有2 種狀態(tài),因此它們的狀態(tài)值集合可以表示為{0,1}。元胞鄰居僅有2 個,即與其緊鄰的2 個元胞。初等元胞自動機的邊界條件一般是周期的,可以表示為
其中,i為元胞的索引,L為該ECA 中元胞的總個數(shù)。在ECA 中,一個元胞的當前狀態(tài)值是由其本身和2 個鄰居的前次狀態(tài)值共同決定的,因此其迭代過程可以表示為一個布爾函數(shù),即
其中,時間維度t=1,2,3,…,空間維度i=1,2,3,…,L,因此,St(i)表示第i個元胞在t時刻的狀態(tài)值。布爾函數(shù)f的計算結(jié)果由迭代規(guī)則r決定,以r=150為例,其計算結(jié)果如表1 所示。
表1 中的迭代結(jié)果St+1(i)可表示為二進制數(shù)10010110,將其進一步轉(zhuǎn)化為十進制數(shù)即迭代規(guī)則150。顯然,在ECA 中,輸入共有8 種,即{000,001,010,…,111};輸出有2 種,即{1,0},因此迭代規(guī)則共有28,即256 種。每種迭代規(guī)則對應(yīng)一種ECA。
表1 當r=150 時,布爾函數(shù)f 的計算結(jié)果
根據(jù)ECA 迭代結(jié)果的性質(zhì),迭代規(guī)則可分為以下五類[37,41-42]:無效規(guī)則、固定點規(guī)則、周期規(guī)則、局部混沌規(guī)則和全局混沌規(guī)則。本文中,任意2種全局混沌規(guī)則下的ECA均可用于構(gòu)建二維分區(qū)初等元胞自動機(PECA,partitioned elementary cellular automata)。ECA 中的全局混沌規(guī)則如表2所示[37]。
表2 ECA 中的全局混沌規(guī)則
PECA 是一種至少包含2 個擁有不同迭代規(guī)則ECA 的高維動態(tài)系統(tǒng),而其中二維分區(qū)初等元胞自動機(2D-PECA,two-dimensional partitioned elementary cellular automata)可表示為
其中,x和y分別代表2 個擁有不同轉(zhuǎn)換規(guī)則r1和r2的ECA。空間維度i∈{1,2,3,…,L}即元胞的索引,各ECA 中元胞的總數(shù)均為L,t代表時間維度。由式(6)可知,在2D-PECA 中2 個ECA的迭代是同步進行的。設(shè)r1=102,r2=105,L=100,且2 個ECA 的初始值是隨機生成的布爾向量,則該2D-PECA 的迭代200 次后的結(jié)果如圖1所示。
圖1 2D-PECA 的迭代200 次后的結(jié)果(r1=102,r2=105)
基于分區(qū)初等元胞自動機和二維耦合映像格,本文提出的2D-PRCML 系統(tǒng)的數(shù)學表達式為
其中,時間維度n=1,2,3,…,空間維度(即格子的索引)i=1,2,3,…,R和j=1,2,3,…,L,一般設(shè)R=L=m;ε是耦合強度;f是logistics 映射;如式(3)所示,索引a、b、c、d由2D-PECA 的迭代結(jié)果得到;pn是第n次迭代時根據(jù)2D-PECA 計算得到的擾動值;δn(i,j)是格子(i,j)在第n次迭代時擾動的符號,其值為-1 或1;運算mod 1 的目的是保留小數(shù)部分,從而保證計算結(jié)果始終在區(qū)間(0,1)上。
設(shè)2D-PECA 中,2 個初等元胞自動機x和y各自的元胞個數(shù)Le應(yīng)大于m和32 中的最大值,系統(tǒng)每迭代一次,即n+1 時,2D-PECA 需先迭代m次得到2 個布爾矩陣E1和E2。各參數(shù)詳細的計算過程如下。
首先,從得到的2 個布爾矩陣E1和E2的中間各截取一個大小為m×m的子矩陣,即與耦合映像格大小相同的矩陣X和Y。然后根據(jù)當前格的位置(i,j)在X與Y中搜索參與耦合的4 個格子的索引,其計算過程可表示為
搜索函數(shù)的運算過程如圖2 所示。圖2 中,每列代表一個元胞,有(無)陰影填充的方格代表該元胞當前狀態(tài)值為1(0),每行代表ECA 迭代一次的結(jié)果。其中,索引a、b由矩陣X和當前格的索引(i,j)得到,即矩陣X第j行中,與第i個元胞最近的2 個狀態(tài)值為1 的元胞的索引,以圖2 為例,a=i-2和b=i+2 可以理解為在e1的第j次迭代結(jié)果中,與元胞i最近的2 個狀態(tài)值為1 的元胞的索引被用作耦合格的索引a和b。同理,可由矩陣Y中第i行,與元胞j最近的2 個狀態(tài)值為1 的元胞索引得到c和d的值。
圖2 搜索函數(shù)的運算過程
每次系統(tǒng)進行迭代時,即n+1 時,2D-PECA都會迭代m次來更新布爾矩陣X與Y的值,而且根據(jù)第1 節(jié)的表述,這一結(jié)果是偽隨機的,所以每次系統(tǒng)進行迭代時,耦合格的索引a、b、c、d都會發(fā)生變化,且這一變化也是偽隨機的。
這樣做的目的如下。1)增強系統(tǒng)的復(fù)雜性,提高系統(tǒng)的李雅普諾夫指數(shù)(LE,Lyapunov exponent),進一步提升系統(tǒng)的不可預(yù)測性;2)加快系統(tǒng)能量的傳遞過程,使整個系統(tǒng)擁有更大范圍的混沌。
擾動值是由2D-PECA 的第m+1 次迭代結(jié)果得到的。2D-PECA 中2 個ECA 某一次的迭代結(jié)果可以看成2 個Le位的二進制數(shù)“”,其中ci(i=1,2,3,…,Le)為第i個元胞當前的狀態(tài)值。取所得到的二進制數(shù)的后32 位來計算擾動值pn,即
其中,函數(shù)bin2dec 的作用是將二進制數(shù)轉(zhuǎn)化為十進制數(shù),分別代表初等元胞自動機x和y在第m+1 次的迭代結(jié)果。顯然,pn始終在區(qū)間(0,1)內(nèi)。需要注意的是,當前2D-PECA 第m+1 次的迭代結(jié)果將作為整個系統(tǒng)下次迭代時2D-PECA 的初始值。由于該迭代結(jié)果是偽隨機的,因此得到的擾動也是偽隨機的,這種偽隨機擾動能夠進一步削弱有限精度系統(tǒng)下的退化問題[19]。
擾動符號是由2.1 節(jié)中得到的矩陣X和Y所決定的,其計算過程為
顯然,經(jīng)過計算δn(i,j)的值為1 或-1。雖然在一次迭代的過程中,對系統(tǒng)中各個格子施加的擾動絕對值是相等的,均為0.5Pn,但由于擾動符號的存在,使對每個格子施加的擾動正負是不同的,且系統(tǒng)每次迭代時X和Y都會被2D-PECA 的迭代所更新,因此擾動符號也是在偽隨機變化的,這樣可以有效降低各個格子之間的相關(guān)性。
2D-PRCML系統(tǒng)的各個參數(shù)設(shè)置如下:logistics映射的控制參數(shù)μ∈(0,4),系統(tǒng)的耦合強度ε∈(0,1)。為了計算方便,本文設(shè)耦合映像格的空間維度R=L=10,因此系統(tǒng)共有100 個格子,令初始值x0=0.05,通過logistics 映射迭代99 次,將迭代后的結(jié)果連同初始值逐行填入100 個格子中,完成各個格子的初始化。2D-PECA 中,初等元胞自動機x和y的元胞數(shù)各為100,兩者初始值設(shè)為100 bit長的二進制隨機數(shù),即
其中,x和y的初始值分別為16 進制數(shù)。根據(jù)1.2 節(jié),本文選擇全局混沌規(guī)則102 和105 分別作為x和y的迭代規(guī)則。
除了基于鄰近耦合的傳統(tǒng)2D-CML 系統(tǒng),本文還選取了2 個較新穎的二維時空混沌系統(tǒng)作為對比:基于Arnold 映射的二維非線性耦合映像格(2D-NLCML,two-dimensional nonlinear coupled map lattices)系統(tǒng)[33-34]、基于偽隨機耦合和PWLCM-Sin 映射的二維混合偽隨機耦合PS 映像格(2D-MCPML,two-dimensional mixed pseudo-random coupling PS map lattice)系統(tǒng)[14]。2D-NLCML 系統(tǒng)中,Arnold 映射的控制參數(shù)p和q分別設(shè)為12 和7,以使其處于混沌狀態(tài)。2D-MCPML 系統(tǒng)中,參數(shù)σ=0.5,其他參數(shù)設(shè)置和2D-PRCML 系統(tǒng)相同。
各系統(tǒng)耦合方案對比如圖3 所示,其中,黑色格子表示當前正在運算的格子,灰色格子表示參與耦合運算的格子。如圖3(a)所示,傳統(tǒng)的2D-CML系統(tǒng)的耦合方案是鄰近耦合。當前格子與其相鄰的上下左右4 個格子進行耦合,且這種耦合是固定的不變的,即對于格子(i,j)來說,在迭代的過程中,參與耦合的4 個格子始終為(i+1,j)、(i-1,j)、(i,j+1)、(i,j-1)。這種方案計算簡單、易于實現(xiàn),但能量傳遞方式緩慢固定,復(fù)雜性不高。
圖3 各系統(tǒng)耦合方案對比
在2D-NLCML 系統(tǒng)中,耦合方案是由Arnold映射所決定的[33-34],數(shù)學表達式為
其中,p和q為控制參數(shù),R和L分別為耦合映像格的總行數(shù)和總列數(shù)。通過上述運算可以得到與格子(i,j)耦合的4 個格子:(a,j)、(b,j)、(i,c)、(i,d)。雖然Arnold 映射是非線性的運算,且p和q的某些取值可以導(dǎo)致混沌,但在此方案中,p和q是固定不變的值,且在每一次系統(tǒng)的迭代過程中,該映射只迭代一次,也就是說輸入i+1 不變,不管系統(tǒng)迭代多少次得到的耦合格始終是(a,j)。該方案只是利用非線性運算實現(xiàn)了非近鄰的耦合,但如圖3(b)所示,耦合方案依然是固定不變的,所以對于系統(tǒng)混沌特性的提升是有限的。
在2D-MCPML 系統(tǒng)中,耦合方案有所改進。參與耦合的格子不再是鄰近或者固定的,而是隨著系統(tǒng)迭代有所變化[14]。在該方案中,與格子(i,j)耦合的格子共有3 個,包括相鄰的2 個格子(i+1,j)和(i,j+1),以及一個根據(jù)格子(i,j)的當前值計算出的隨機位置的格子(a,b)。計算過程如下。設(shè)耦合映像格的大小為R×L,假設(shè)格子(i,j)當前的值為0.409 671 42,a=(40 modR)+1,b=(96 modL)+1。由于格子(i,j)的值隨著系統(tǒng)的迭代不斷變化,(a,b)也隨之不斷變化,且當該系統(tǒng)處于混沌狀態(tài)時,這一變化將是偽隨機的,如圖3(c)所示。然而,這種耦合方案依賴于系統(tǒng)混沌映射本身的特性,后續(xù)分析發(fā)現(xiàn)該方案所設(shè)計的混沌映射迭代結(jié)果分布并不均勻,所以在此基礎(chǔ)上求出的隨機耦合格其分布也是非均勻的;其次該耦合方案中依然存在鄰近成分,所以對能量傳遞速度的提升是有限的。
本文所提出的2D-PRCML 系統(tǒng)中,根據(jù)第2 節(jié)的描述,所用的耦合方案基于2D-PECA 的迭代結(jié)果,所選擇的迭代規(guī)則又使2D-PECA 系統(tǒng)處于混沌狀態(tài),由此得到參與耦合的4 個格子位置均處于偽隨機變化之中,如圖4(d)所示。該方案有效地加快了系統(tǒng)的能量傳遞速度,提高了系統(tǒng)的復(fù)雜性。
LE 是衡量動力系統(tǒng)運行時,在相空間中鄰近軌跡分離速率的一個重要參數(shù)[43-44],通常用來評價混沌系統(tǒng)的不可預(yù)測性。它的數(shù)學定義為
其中,λ為動力系統(tǒng)F(x)的LE,i為時間維度。對于一個混沌系統(tǒng)來說,至少應(yīng)該擁有一個正的LE,且LE 的值越大,說明該系統(tǒng)的混沌特性越強[8-10,45]。為了不失一般性,與文獻[10,31-32]相同,本文采用Wolf 法[43],通過系統(tǒng)生成的序列來計算LE。
K 熵密度(KED,Kolmogorov-Sinai entropy density)是計算時空混沌系統(tǒng)中所有正的LE 在格子總數(shù)下的均值[46-47],在二維時空混沌系統(tǒng)中,其計算式為
其中,h代表KED,λ+代表大小為RL的耦合映像格中正的李雅普諾夫指數(shù),i和j代表LE 為正的格子索引。h為正意味著系統(tǒng)中存在處于混沌狀態(tài)的格子,h的值越大,代表系統(tǒng)的混沌特性越強,復(fù)雜性越高。在不同的控制參數(shù)和耦合強度下,各系統(tǒng)的KED 如圖4 所示。
圖4 各系統(tǒng)的KED
圖4 中x、y、z軸分別代表控制參數(shù)μ、耦合強度ε、K 熵密度h。如圖4 所示,在2D-CML 和2D-NLCML系統(tǒng)中,只有μ>3.6時才存在正的KED,即僅在區(qū)間μ∈(3.6,4]時,才會存在處于混沌狀態(tài)的格子,且2D-CML 系統(tǒng)中,在ε=0.2 附近有一小段弱混沌區(qū)間,在2D-NLCML 系統(tǒng)中對此有所改善,且隨著ε的增大,KED 有所提高。在2D-MCPML以及2D-PRCML 系統(tǒng)中,整個參數(shù)區(qū)間上KED 均大于0,即均存在處于混沌狀態(tài)的格子。同時統(tǒng)計發(fā)現(xiàn),圖4(c)中,僅有9.12%的參數(shù)對(μ,ε)所對應(yīng)的KED 達到了0.8,而在圖4(d)中,這一比例高達99.68%。因此,可以得出結(jié)論,2D-PRCML 系統(tǒng)的混沌特性要遠強于前三類系統(tǒng)。
K 熵闊度(KEB,Kolmogorov-Sinai entropy breadth)是由Zhang 等[25,47]提出的,用來統(tǒng)計固定參數(shù)下時空混沌系統(tǒng)中處于混沌狀態(tài)的格子占比,其定義為
其中,hu 表示K 熵闊度,L+表示系統(tǒng)中李雅普諾夫指數(shù)為正的格子數(shù),L表示系統(tǒng)中的格子總數(shù)。KEB可以從空間層面上來衡量系統(tǒng)的混沌特性。hu 的值越大,系統(tǒng)中處于混沌狀態(tài)的格子越多,即系統(tǒng)擁有越廣泛的混沌特性。各系統(tǒng)的KEB 如圖5 所示。與K 熵密度相對應(yīng),圖5(a)和圖5(b)中,僅當μ>3.6時,2D-CML 和2D-NLCML 系統(tǒng)才存在KEB=1,即只有當μ∈(3.6,4]時,所有的格子才有可能都處于混沌狀態(tài)。統(tǒng)計結(jié)果表明,在圖5(a)和圖5(b)中,整個參數(shù)區(qū)間上分別僅有28.96%和29.76%的參數(shù)對(μ,ε)使系統(tǒng)所有的格子處于混沌狀態(tài),即2D-CML 和2D-NCML 系統(tǒng)所建立的混沌范圍在空間上是有限的。與之相反,在圖5(c)和圖(d)中,KEB=1 的比例分別達到了99.84%和100%,即在2D-MCPML 和2D-PRCML 系統(tǒng)中,大部分的參數(shù)對下,空間上所有的格子均能建立較強的混沌狀態(tài)。
圖5 各系統(tǒng)的KEB
綜上所述,2D-PRCML 系統(tǒng)相比于本文提到的其他時空混沌系統(tǒng)具有更強的混沌特性,KED 均值達到了0.815 4,這也說明該系統(tǒng)的復(fù)雜性和不可預(yù)測性更高。同時,2D-PRCML 系統(tǒng)建立的混沌狀態(tài)足夠廣泛,在整個參數(shù)范圍μ∈(3,4],ε∈(0,1)中,所有的格子均能達到混沌狀態(tài)。進一步地,當2D-PRCML 應(yīng)用于密碼系統(tǒng)中時,由于具有更多的參數(shù)對(μ,ε)使系統(tǒng)處于不可預(yù)測的混沌狀態(tài),這大大擴展了(μ,ε)作為密鑰時的密鑰空間。
分岔圖是用來分析混沌系統(tǒng)特性的一個重要工具,描繪了混沌系統(tǒng)中特有的倍周期分岔現(xiàn)象,可以直觀地衡量在不同的控制參數(shù)下混沌系統(tǒng)的遍歷性和非周期性。
為了進行對比分析,本文設(shè)各系統(tǒng)的耦合強度ε=0.35,并選擇格子(5,5)生成的序列{x(i)|i=1,2,3,…}來繪制分岔圖,各系統(tǒng)的分岔圖如圖6 所示。
顯然,圖6(a)和圖6(b)在μ<3.6 時均存在有明顯的周期窗口,而2D-CML 系統(tǒng)的非周期性甚至要優(yōu)于2D-NLCML,因為在μ∈(3,3.5)時,圖6(b)明顯存在2 個固定的周期點,而在圖6(a)中,雖然有周期點,但周期點不止2 個,因此周期長度要更長。從遍歷性的角度,圖6(a)和圖6(b)僅在μ=4 時,序列的取值才能夠充滿整個值域。在圖6(c)和圖6(d)中,周期窗口在整個區(qū)間μ∈(3,4)上消失了,所以2D-MCPML 和2D-PRCML 系統(tǒng)的非周期性更好,擁有更好的不可預(yù)測性和偽隨機性。此外,圖6(c)中,分岔圖并沒有充滿x的整個值域[0,1],落在最小值0 和最大值1 附近的點很少,這說明 2D-MCPML 系統(tǒng)的遍歷性稍差。而在圖6(d)中,2D-PRCML 系統(tǒng)在整個控制參數(shù)區(qū)間μ∈(3,4)上均有很好的遍歷性,因為生成的序列能夠充滿整個值域[0,1]。綜上所述,2D-PRCML系統(tǒng)在控制參數(shù)區(qū)間μ∈(3,4)上擁有更好的非周期性和遍歷性。
圖6 ε=0.35 時各系統(tǒng)的分岔圖
密碼系統(tǒng)中要求作為密鑰流或隨機數(shù)的序列,其分布特性應(yīng)該足夠均勻?;煦缦到y(tǒng)生成序列的分布均勻性應(yīng)從2 個角度來分析:一是回歸映射上的分布,二是各格子生成序列本身的頻率分布特性。
研究系統(tǒng)的回歸映射是為了判斷系統(tǒng)能否抵抗回歸映射分析攻擊[35-36]?;貧w映射分析攻擊是針對混沌密碼系統(tǒng)的一種有效攻擊手段,其可通過混沌系統(tǒng)生成的序列來估算系統(tǒng)的各控制參數(shù),從而達到預(yù)測系統(tǒng)之后生成序列的目的。而回歸映射的特征越明顯,分布越集中,則系統(tǒng)越容易被攻破。
本文設(shè)μ=4,選擇格子(5,5)生成的序列作為代表,則各系統(tǒng)的回歸映射如圖7 所示。
由圖7(a)~圖7(c)可知,2D-CML、2D-NLCML系統(tǒng)的回歸映射均集中在一條拋物線附近,而2D-MCPML 系統(tǒng)的則集中在一條折線附近,且隨著耦合強度ε的增大,回歸映射中的點逐漸發(fā)散。因此,上述3 種系統(tǒng)的回歸映射具有2 個特點:1)集中在某些區(qū)域,2)對耦合強度的變化敏感,故這3 種系統(tǒng)極易受到回歸映射分析攻擊。圖7(d)中,2D-PRCML 系統(tǒng)的回歸映射的分布近似于噪點的分布,沒有集中的形狀,同時隨著ε的變化,回歸映射依舊保持這種類似于噪點的均勻分布,因此能夠很好地抵抗回歸映射分析攻擊。
圖7 各系統(tǒng)在不同耦合強度下的回歸映射
進一步地,本文設(shè)ε=0.625,μ=4,讓每個系統(tǒng)迭代6 000 次,系統(tǒng)中的各個格子生成長度為6 000的序列,去除序列中前1 000 個元素,減少初值的影響;然后將序列的值域[0,1]平均分成200 段,統(tǒng)計序列中落在每一段中的元素個數(shù)。各系統(tǒng)生成序列的頻率分布如圖8 所示。
圖8 各系統(tǒng)生成序列的頻率分布
圖8 中x、y、z軸分別代表在序列值域[0,1]上的分段,10×10 個格子的編號以及某一格子生成的序列在某一分段上的元素個數(shù)。顯然,2D-PRCML系統(tǒng)中各個格子生成序列的頻率分布比其他3 種系統(tǒng)更加均勻。
在密碼系統(tǒng)中,本文希望同一系統(tǒng)同一時間生成的各個序列之間應(yīng)該相互無關(guān),在時空混沌系統(tǒng)中可以理解為無法通過一個或多個格子生成的序列計算推導(dǎo)出其他格子生成的序列。因此,研究時空混沌系統(tǒng)中各個格子之間的相關(guān)性對其在密碼系統(tǒng)中的應(yīng)用具有重要意義[48]。因此本文計算了各系統(tǒng)在不同參數(shù)對下,不同格子生成序列之間的皮爾遜相關(guān)系數(shù)的均值,相關(guān)性分析如圖9 所示。
工程上,當皮爾遜相關(guān)系數(shù)小于0.3 時,可以認為不相關(guān)。對圖9 進行統(tǒng)計結(jié)果表明,在2D-CML和2D-NLCML 系統(tǒng)中僅有6.88%和5.2%的參數(shù)對(μ,ε)下,各序列之間的相關(guān)系數(shù)小于0.3。而在2D-MCPML 和2D-PRCML 系統(tǒng)中,這一比例分別達到了91.8%和100%。因此2D-PRCML 系統(tǒng)所生成的各個序列之間的相關(guān)性很弱,在密碼系統(tǒng)中敵手很難通過一個或多個格子的輸出計算推導(dǎo)出其他格子的輸出,即該系統(tǒng)的安全性較高。
圖9 相關(guān)性分析
為了進一步驗證本文方案生成序列的隨機性,以及其在偽隨機數(shù)生成方面的應(yīng)用潛力,本文引入了應(yīng)用廣泛,且較權(quán)威的美國國家標準技術(shù)研究所(NIST,National Institute of Standards and Technology)的隨機數(shù)檢測套件SP800-22 對2D-PRCML 系統(tǒng)生成的數(shù)據(jù)進行了檢測[49]。
首先,對2D-PRCML 生成的(0,1)的數(shù)據(jù)x進行量化。
其中,函數(shù)floor(·)為向下取整函數(shù),y為無符號的32 位數(shù)。截取x={x1,x2,…,x1000000}量化后生成的序列y中每個元素的后16 位,生成16 條長度為106的0,1 序列進行隨機性檢測,并檢測100 組數(shù)據(jù)檢測結(jié)果如表3 所示。
表3 列出了量化后100 組數(shù)據(jù)的后16 位生成的偽隨機數(shù)的檢測結(jié)果。本文取顯著性水平α=0.01,即當每項測試的結(jié)果p>0.01 時,則通過該測試,這意味著該序列為隨機序列的置信度水平為99%。而表3 中列出了100 組測試數(shù)據(jù)的通過率,根據(jù)文獻[24,50],100 組數(shù)據(jù)中有不少于96 組數(shù)據(jù)通過測試,即可認為該數(shù)據(jù)通過了隨機性檢測,具有良好的隨機性。顯然,經(jīng)量化后的16 位數(shù)據(jù)生成的序列均通過了NIST 隨機性檢測。這有力地證明了本文提出的系統(tǒng)具有良好的隨機性,即本文方案在偽隨機數(shù)生成器和序列密碼方面具有巨大的應(yīng)用潛力。
表3 NIST 隨機性檢測結(jié)果
本文方案除在密碼學領(lǐng)域有著較好的應(yīng)用前景外,在混沌保密通信方面也有著巨大的實用價值。
混沌系統(tǒng)產(chǎn)生的序列具有非周期性、連續(xù)寬帶頻譜、類噪聲等特性,在相空間中具有極其復(fù)雜的運動軌跡和不可預(yù)測性,因此有著天然的隱蔽性,非常適合作為保密通信的載體。然而,目前混沌保密通信有著以下幾點問題亟待解決[51]:1)模擬電路實現(xiàn)的混沌保密系統(tǒng),很難做到收發(fā)兩端的完全匹配;2)相空間重構(gòu)和回歸映射分析攻擊的出現(xiàn)使通信中使用的混沌映射有被敵手精確預(yù)測的可能,從而降低系統(tǒng)的安全性;3)數(shù)字電路的有限精度導(dǎo)致的混沌系統(tǒng)動力學退化問題;4)混沌系統(tǒng)直接生成的序列分布不均,偽隨機性不足。
本文方案很好地改善或優(yōu)化了上述問題。1)本文提出的2D-PRCML 系統(tǒng)是個離散的動力學系統(tǒng),完全可由數(shù)字系統(tǒng)實現(xiàn),因此混沌保密通信收發(fā)兩端的匹配較容易。2)分布均勻性分析發(fā)現(xiàn),2D-PRCML 系統(tǒng)的輸出序列在回歸映射的分布呈現(xiàn)不規(guī)則且分布均勻的狀態(tài),不同于其他系統(tǒng)的輸出分布過于集中于某一固定形狀,因此可以有效抵抗相空間重構(gòu)或回歸映射分析攻擊。3)2D-PRCML系統(tǒng)通過耦合,各格子間相互擾動有效削弱了動力學退化的問題,進一步地,本文方案中引入了基于PECA 這一離散系統(tǒng)的擾動,可以更有效地削弱系統(tǒng)的動力學退化問題。4)均勻性分析和偽隨機測試的結(jié)果證明,2D-PRCML 系統(tǒng)的輸出序列具有良好的均勻性和偽隨機性,因此安全性方面也有所保證。
綜上,本文提出的2D-PRCML 系統(tǒng)可以有效改善混沌保密通信中存在的部分問題,因此在該方面具有良好的應(yīng)用前景。
基于分區(qū)初等元胞自動機和二維耦合映像格系統(tǒng),本文提出了一種二維時空混沌系統(tǒng),即二維偽隨機耦合映像格系統(tǒng)。首先,本文基于初等元胞自動機設(shè)計了一種二維分區(qū)初等元胞自動機,以滿足二維時空混沌系統(tǒng)的數(shù)據(jù)需求;然后,基于2D-PECA 設(shè)計了一種偽隨機耦合方案,同時利用2D-PECA 的迭代結(jié)果,對系統(tǒng)中的各格子添加了不同的偽隨機擾動。動態(tài)特性分析結(jié)果表明,相比于本文提到的其他二維時空混沌系統(tǒng),2D-PRCML 系統(tǒng)擁有更強和更廣泛的混沌特性,且擁有更好的遍歷性和非周期性。同時,2D-PRCML 系統(tǒng)生成的序列在回歸映射和頻率分布上具有良好的均勻性。進一步地,這些序列在經(jīng)過簡單量化后,生成的0,1序列能夠通過NIST 隨機性測試,證明了其良好的偽隨機性。此外,本文還分析了時空混沌系統(tǒng)中各格子生成序列之間的相關(guān)性,結(jié)果表明2D-PRCML系統(tǒng)所生成序列之間的相關(guān)性要明顯低于其他系統(tǒng),且均小于0.3,從而保證了系統(tǒng)的安全性。綜上所述,這些良好的性質(zhì)表明2D-PRCML 在密碼系統(tǒng)中,特別是偽隨機數(shù)生成器和序列密碼方面具有巨大的應(yīng)用前景。同時,在混沌保密通信方面也具有良好的實用價值。