整數(shù)非線性耦合映象格子模型及其性能分析*

商 凱，劉建東，張 嘯，胡輝輝

1.北京石油化工學(xué)院 信息工程學(xué)院，北京 102617

2.北京化工大學(xué) 信息科學(xué)與技術(shù)學(xué)院，北京 100029

整數(shù)非線性耦合映象格子模型及其性能分析*

商 凱1,2，劉建東1+，張 嘯1,2，胡輝輝1,2

1.北京石油化工學(xué)院 信息工程學(xué)院，北京 102617

2.北京化工大學(xué) 信息科學(xué)與技術(shù)學(xué)院，北京 100029

以時(shí)空混沌研究領(lǐng)域的典型例子——耦合映象格子模型為原型，采用非線性Arnold貓映射作為格點(diǎn)間的耦合方式，分別選用Logistic映射及Tent映射作為其格點(diǎn)的非線性函數(shù)，并將非線性函數(shù)進(jìn)行整數(shù)化處理，進(jìn)而構(gòu)造出一種整數(shù)非線性耦合映象格子模型，模型生成序列具有均勻分布特性及獨(dú)立性。對模型格點(diǎn)間的互信息、模型生成序列的分布特性、差值特性進(jìn)行了仿真分析，并對模型生成序列進(jìn)行了隨機(jī)性測試。仿真結(jié)果表明，模型能夠并行生成相互獨(dú)立的性能良好的偽隨機(jī)序列。

非線性耦合；Arnold貓映射；Logistic映射；Tent映射

1 引言

對于類似于洛倫茲模型的非線性確定論系統(tǒng)，即使是一組基本無法分辨差別的初始條件，它們的相空間軌道隨時(shí)間發(fā)生指數(shù)的分離，結(jié)果使這些軌道隨時(shí)間發(fā)展看起來互不相關(guān)[1]。系統(tǒng)的長時(shí)間行為顯示出的混沌特性，可以使簡單的確定系統(tǒng)產(chǎn)生復(fù)雜的隨機(jī)行為。時(shí)空混沌系統(tǒng)在時(shí)間及空間方向上都是混沌的，其動(dòng)力學(xué)行為非常豐富而復(fù)雜，空間上的任何微小變化都會(huì)隨時(shí)間的增加而擴(kuò)散開去，產(chǎn)生很大的變化，使得時(shí)空混沌系統(tǒng)具有非常好的密碼學(xué)特性。

時(shí)空混沌的典型例子是耦合映象格子（coupled map lattice，CML）模型[2-3]。CML模型采用了密碼學(xué)中最常用的混淆和擴(kuò)散方法，CML模型中格點(diǎn)間的相互耦合，使某一格點(diǎn)的變化擴(kuò)散到其他格點(diǎn)，繼而所有格點(diǎn)都產(chǎn)生巨大的變化；非線性函數(shù)的引入，使輸入和輸出的關(guān)系更為復(fù)雜，實(shí)現(xiàn)了序列迭代隨時(shí)間推移的混淆。正因?yàn)镃ML模型的諸多適合密碼學(xué)的特性，近年來CML模型引起了廣泛的關(guān)注[4-7]。傅志堅(jiān)等人[8]基于時(shí)空混沌單向耦合映象格子（one way coupled map lattice，OCML）模型，提出了生成偽隨機(jī)位序列的兩種新方法，并對序列性能進(jìn)行了詳細(xì)的分析。Khellat等人[9]提出了非局部耦合格子時(shí)空模型（globally nonlocal coupled map lattice，GNCML），并對模型的混沌特性進(jìn)行了嚴(yán)格的證明。然而，上述模型都是采用相鄰格點(diǎn)耦合，一旦某一格點(diǎn)序列信息被獲取，系統(tǒng)將面臨全部信息泄露的危險(xiǎn)。文獻(xiàn)[10]采用非線性Arnold貓映射代替相鄰格點(diǎn)耦合，仿真結(jié)果顯示模型生成序列間的獨(dú)立性明顯提升。然而該模型構(gòu)造在實(shí)數(shù)域內(nèi)，計(jì)算機(jī)實(shí)現(xiàn)時(shí)存在很多問題。此外模型中非線性函數(shù)采用了實(shí)數(shù)域Logistic映射，實(shí)數(shù)域Logistic映射具有明顯的不均勻分布特性。

在實(shí)數(shù)域上構(gòu)造混沌模型存在以下幾方面問題[11]:一是實(shí)數(shù)域被無窮多的無理數(shù)所充滿，由于計(jì)算機(jī)截?cái)嗾`差的存在，它不能處理無理數(shù)，在有限精度實(shí)現(xiàn)的情況下，數(shù)字化混沌系統(tǒng)的動(dòng)力學(xué)特性相對連續(xù)系統(tǒng)而言存在嚴(yán)重的退化；二是計(jì)算機(jī)精度及所采用的機(jī)器甚至語言類型都可能影響有限精度混沌系統(tǒng)的最終結(jié)果；三是不利于計(jì)算機(jī)高速實(shí)現(xiàn)。由此，本文提出了整數(shù)非線性耦合映象格子模型，將混沌映射整數(shù)化實(shí)現(xiàn)，并從互信息、分布特性、差值特性、隨機(jī)性等方面對模型進(jìn)行分析研究。仿真結(jié)果表明，模型能夠并行生成相互獨(dú)立的性能良好的偽隨機(jī)序列。基于本文提出的模型算法，結(jié)合密碼學(xué)應(yīng)用背景，可實(shí)現(xiàn)效果理想的單向Hash函數(shù)[11]和圖像加密算法[12]等一系列的密碼學(xué)應(yīng)用。

2 整數(shù)非線性耦合映象格子模型

耦合映象格子模型的形式為：

式中，n為迭代步數(shù)；i=1,2,…,L為格點(diǎn)坐標(biāo)，L為系統(tǒng)格點(diǎn)數(shù)；ε為耦合系數(shù)，且滿足0≤ε≤1；f為非線性映射函數(shù)；初值為[0,1]內(nèi)的隨機(jī)數(shù)。

由于CML模型相鄰格點(diǎn)相互耦合，格點(diǎn)間互信息大，一旦某一格點(diǎn)序列信息被獲取，系統(tǒng)將面臨全部信息泄露的危險(xiǎn)。在耦合映象格子模型中，用非線性耦合代替?zhèn)鹘y(tǒng)的相鄰耦合，可解決格點(diǎn)間的安全性問題。非線性Arnold貓映射耦合映象格子（ACML）模型的形式為：

式中，n、i、ε表示的含義與CML模型一致；j、k(0＜j,k＜L)表示空間格點(diǎn)號，由Arnold貓映射決定：

上述模型在實(shí)數(shù)域內(nèi)實(shí)現(xiàn)，應(yīng)用到密碼學(xué)領(lǐng)域存在諸多問題。以式（2）為原型，從密碼學(xué)的需求出發(fā)，構(gòu)造整數(shù)非線性耦合映象格子模型，其形式為：

式中，xn+1(i)表示第n+1步迭代第i個(gè)格點(diǎn)的值；mod表示取模運(yùn)算；a表示系統(tǒng)的位數(shù)，2a表示系統(tǒng)可容納的最大狀態(tài)值。整數(shù)模型取消了耦合系數(shù)ε，使得各個(gè)格點(diǎn)平等地影響下一輪迭代，同時(shí)避免了小數(shù)的出現(xiàn)，實(shí)現(xiàn)全部整數(shù)運(yùn)算。非線性函數(shù)f(xi)分別采用動(dòng)態(tài)整數(shù)Logistic映射和動(dòng)態(tài)整數(shù)Tent映射實(shí)現(xiàn)，并對其進(jìn)行分析比較。

動(dòng)態(tài)整數(shù)Logistic映射的形式為：

式中，a表示系統(tǒng)的位數(shù)；xi∈[1,2a-1]；ki表示函數(shù)的水平移動(dòng)距離。整數(shù)Logistic函數(shù)具有封閉性[13]，即所有xi∈[1,2a-1]帶入函數(shù)f(xi)，都能保證運(yùn)算結(jié)果仍在xi∈[1,2a-1]范圍內(nèi)。由于乘以4和除以2a均可以通過計(jì)算機(jī)中的移位實(shí)現(xiàn)，整數(shù)Logistic映射有很強(qiáng)的實(shí)用性。

動(dòng)態(tài)整數(shù)Tent映射的形式為：

式中，xi∈[1,2a-1]；a、ki含義與整數(shù)Logistic映射一致。動(dòng)態(tài)整數(shù)Tent映射具有良好的均勻分布特性和差值特性。

2.1 信息熵和互信息

信息熵和平均交互信息量（互信息）的定義源于信息論。信息熵表示信源每發(fā)出一個(gè)符號所能提供的平均信息量，而互信息表示通信前后平均不確定性的消除[14]。

令隨機(jī)變量X和Y取值分別為{x1,x2,…,xn}和{y1,y2,…,yn}時(shí)的概率分別為p(xi)和p(yj)(i,j=1,2,…,n)，相對應(yīng)的X和Y的信息熵為：

信息熵可以表征序列的復(fù)雜度。序列越混亂，其信息熵就越大。選取8位二進(jìn)制為系統(tǒng)長度，則當(dāng)X為均勻分布時(shí)，H(X)理論值最大為8。計(jì)算動(dòng)態(tài)整數(shù)Logistic映射和動(dòng)態(tài)整數(shù)Tent映射取不同格點(diǎn)數(shù)目時(shí)的信息熵，見表1。相同格點(diǎn)數(shù)目下，兩種模型的信息熵均在理論最大值附近，說明模型復(fù)雜度高。非線性函數(shù)選取整數(shù)Tent映射信息熵略大于選取整數(shù)Logistic映射，說明前者的混亂程度更高。XY的聯(lián)合信息熵為：

Table 1 Entropy of information with different lattices表1 不同格點(diǎn)數(shù)目下模型的信息熵

則隨機(jī)變量X和Y之間互信息的表述形式為：

互信息滿足非負(fù)性和對稱性。當(dāng)X和Y完全相同時(shí)互信息最大，當(dāng)X和Y相互獨(dú)立時(shí)互信息為0。

采用值域均勻分割[15]的方式計(jì)算p(xi),p(yj),p(xiyj)，并帶入式（12）計(jì)算X和Y的互信息。為了直觀展示，對互信息進(jìn)行歸一化處理，并消除相同格點(diǎn)計(jì)算值的影響。選取32個(gè)格點(diǎn)，8位二進(jìn)制為系統(tǒng)長度，貓映射參數(shù)p=10，q=10，計(jì)算整數(shù)模型格點(diǎn)間的互信息，如圖1～圖4所示（I(X,Y)表示互信息，i和j表示格點(diǎn)號）。相鄰耦合下，非線性函數(shù)采用整數(shù)Logistic映射及采用整數(shù)Tent映射的互信息均在0.2附近（為消除相同格點(diǎn)的影響，對角線位置取0.2）。而在非線性耦合方式下，非線性函數(shù)采用整數(shù)Logistic映射及采用整數(shù)Tent映射的絕大多數(shù)互信息均遠(yuǎn)小于0.1，可以認(rèn)為格點(diǎn)間相互獨(dú)立。此外，采用整數(shù)Logistic映射作為非線性函數(shù)時(shí)存在4個(gè)互信息較大的點(diǎn)，在該參數(shù)下存在缺陷。

2.2 分布特性

選取32個(gè)格點(diǎn)，每個(gè)格點(diǎn)變量取8位字長，貓映射參數(shù)p=10，q=10，分別選取整數(shù)Logistic映射和整數(shù)Tent映射為非線性函數(shù)，對式（4）進(jìn)行迭代，生成32個(gè)格點(diǎn)的時(shí)空混沌序列，如圖5和圖6所示（i為格點(diǎn)號，n為迭代次數(shù)，x為序列值）。可以看到，分別選取整數(shù)Logistic映射和整數(shù)Tent映射時(shí)，式（4）均呈現(xiàn)時(shí)空混沌狀態(tài)。

Fig.1 Mutual information of linear CML model (integral Logistic map)圖1 線性CML模型互信息（整數(shù)Logistic映射）

Fig.2 Mutual information of linear CML model (integral Tent map)圖2 線性CML模型互信息（整數(shù)Tent映射）

Fig.3 Mutual information of nonlinear CML model (integral Logistic map)圖3 非線性CML模型互信息（整數(shù)Logistic映射）

Fig.4 Mutual information of nonlinear CML model (integral Tent map)圖4 非線性CML模型互信息（整數(shù)Tent映射）

Fig.5 Spatiotemporal chaos character of nonlinear CML(integral Logistic map)圖5 非線性CML模型時(shí)空混沌特性（整數(shù)Logistic映射）

Fig.6 Spatiotemporal chaos character of nonlinear CML(integral Tent map)圖6 非線性CML模型時(shí)空混沌特性（整數(shù)Tent映射）

進(jìn)一步統(tǒng)計(jì)混沌序列中每個(gè)狀態(tài)值出現(xiàn)的頻數(shù)。理想均勻分布序列每個(gè)狀態(tài)值出現(xiàn)的頻率相同，則各格點(diǎn)的頻數(shù)分布應(yīng)為一個(gè)平面。對式（4）分別選取整數(shù)Logistic映射和整數(shù)Tent映射，迭代次數(shù)取15次，其頻數(shù)分布如圖7和圖8所示（i為格點(diǎn)號，x為序列值，F(xiàn)requence為頻數(shù)）。兩種非線性函數(shù)下模型的頻數(shù)分布均在n=15平面附近。對比得到，整數(shù)Logistic映射的頻數(shù)分布不規(guī)則程度大于整數(shù)Tent映射，在序列取值較大時(shí)偏差大。整數(shù)Tent映射的頻數(shù)分布則較為平整。

Fig.7 Frequences of nonlinear CML model (integral Logistic map)圖7 非線性CML模型頻數(shù)統(tǒng)計(jì)（整數(shù)Logistic映射）

Fig.8 Frequences of nonlinear CML model (integral Tent map)圖8 非線性CML模型頻數(shù)統(tǒng)計(jì)（整數(shù)Tent映射）

2.3 差值分析

基于確定迭代規(guī)則產(chǎn)生的序列，相鄰狀態(tài)值之間存在相關(guān)關(guān)系。這種關(guān)系可通過序列的差值直觀地展現(xiàn)。序列k階差值的定義為dn=|xn+k-xn|，其中xn+k、xn為序列的第n+k項(xiàng)和第n項(xiàng)。離散隨機(jī)序列的差值分布應(yīng)該是線性遞減的，且分布形態(tài)與差值階數(shù)無關(guān)。

式（4）中非線性函數(shù)分別選取整數(shù)Logistic映射和整數(shù)Tent映射，統(tǒng)計(jì)非線性耦合模型的1～50階差值如圖9和圖10所示（k為差值階數(shù)，dn為差值數(shù)值，F(xiàn)requence為頻數(shù)）。模型在兩種映射下的差值均從dn=1開始線性遞減，符合理論上隨機(jī)序列的差值分布特性（根據(jù)文獻(xiàn)[16]，整數(shù)域差值為0的頻數(shù)為差值為1的頻數(shù)的一半，其余依次遞減）。同時(shí)可以看到，整數(shù)Logistic映射的差值分布毛刺較多，而整數(shù)Tent映射更平滑。

Fig.9 Difference characteristics of nonlinear CML(integral Logistic map)圖9 非線性CML模型差值分布（整數(shù)Logistic映射）

Fig.10 Difference characteristics of nonlinear CML(integral Tent map)圖10 非線性CML模型差值分布（整數(shù)Tent映射）

2.4 隨機(jī)性測試

采用美國國家標(biāo)準(zhǔn)與技術(shù)研究所（NIST）制定的隨機(jī)數(shù)的15種測試方法對整數(shù)Tent非線性耦合映象格子模型格點(diǎn)序列進(jìn)行隨機(jī)性測試，測試結(jié)果見表2。測試中每種方法計(jì)算的P值如果小于1%，則證明序列不是隨機(jī)序列；反之，則證明序列為隨機(jī)序列。從表2中可以看到，整數(shù)Tent非線性耦合映象格子模型生成的序列可以通過全部測試，證明序列為隨機(jī)序列。整數(shù)Logistic非線性耦合映象格子產(chǎn)生的隨機(jī)序列不能通過15項(xiàng)測試中Cumulative Sums、Frequency、Random Excursions、Random Excursions Variant、Runs這5項(xiàng)測試，需進(jìn)一步優(yōu)化。

Table 2 Results of randomness test表2 隨機(jī)性測試結(jié)果

3 結(jié)束語

以耦合映象格子模型為基礎(chǔ)，采用非線性耦合Arnold貓映射代替相鄰耦合，得到整數(shù)非線性耦合映象格子模型。仿真結(jié)果表明，模型在互信息、序列復(fù)雜度、分布特性、差值特性及隨機(jī)性方面均有良好的性能，且可在計(jì)算機(jī)中高速實(shí)現(xiàn)。另外，分別選取動(dòng)態(tài)整數(shù)Logistics映射及動(dòng)態(tài)整數(shù)Tent映射作為模型的非線性函數(shù)，對其進(jìn)行對比分析，分析得出選取整數(shù)Tent映射作為非線性函數(shù)時(shí)，互信息更小，分布特性更為均勻，差值分布誤差小，且能通過隨機(jī)數(shù)測試。在下一步的研究中，將利用該模型構(gòu)造輕量級散列函數(shù)及序列密碼，為解決無線傳感器網(wǎng)絡(luò)安全問題奠定基礎(chǔ)。

[1]Yang Weiming.Spatiotemporal chaos and coupled map lattice[M].Shanghai:Shanghai Scientific and Technological Education Publishing House,1994.

[2]Kaneko K.Period-doubling of kink-antikink patterns,quasiperiodicity in antiferro-like structures and spatial intermittency in coupled map lattices—toward a prelude to a field theory of chaos[J].Progress of Theoretical Physics,1984, 72(3):480-486.

[3]Kaneko K.Pattern dynamics in spatiotemporal chaos[J]. Physica D Nonlinear Phenomena,1989,34(1/2):1-41.

[4]He Jun,Li Zhibin,Qian Haifeng.Cryptography based on spatiotemporal chaos system and multiple maps[J].Journal of Software,2010,5(4):421-428.

[5]Chapaneri S,Chapaneri R,Sarode T.Evaluation of chaotic map lattice systems for image encryption[C]//Proceedings of the 2014 International Conference on Circuits,Systems, Communication and Information Technology Applications, Mumbai,India,Apr 4-5,2014.Piscataway,USA:IEEE,2014: 59-64.

[6]Banerjee T,Paul B,Sarkar B C.Spatiotemporal dynamics of a digital phase-locked loop based coupled map lattice system[J].Chaos An Interdisciplinary Journal of Nonlinear Science,2014,24(1):013116.

[7]Cao Lvchen,Luo Yuling,Bi Jinjie,et al.An authentication strategy based on spatiotemporal chaos for software copyright protection[J].Security and Communication Networks, 2015,8(18):4073-4086.

[8]Fu Zhijian,Zeng Yicheng,Xu Maolin.Two novel methods for generating spatiotemporal chaotic pseudorandom bit sequences based on one way coupled map lattices[J].Acta Physica Sinica,2008,57(7):4014-4020.

[9]Khellat F,Ghaderi A,Vasegh N.Li-Yorke chaos and syn-chronous chaos in a globally nonlocal coupled map lattice [J].Chaos Solitons&Fractals,2011,44(11):934-939.

[10]Zhang Yingqian,Wang Xingyuan.Spatiotemporal chaos in Arnold coupled Logistic map lattice[J].Nonlinear Analysis Modelling and Control,2013,18(4):526-541.

[11]Liu Jiandong.One-way Hash function based on integer coupled Tent maps and its performance analysis[J].Journal of Computer Research and Development,2008,45(3):563-569.

[12]Zhang Yingqian,Wang Xingyuan.A symmetric image encryption algorithm based on mixed linear-nonlinear coupled map lattice[J].Information Sciences,2014,273:329-351.

[13]Chen Shuai.Research on chaos encryption theory and key technology for wireless micro-sensor network[D].Chongqing:Chongqing University,2006.

[14]Jiang Dan.Information theory&coding[M].Hefei:Science and Technology of China Press,2009.

[15]Zhang Dianzhong.Research on the correlation between the mutual information and Lempel-Ziv complexity of nonlinear time series[J].Acta Physica Sinica,2007,56(6):3152-3153.

[16]Wang Yong.Research on chaos based encryption algorithm and Hash function construction[D].Chongqing:Chongqing University,2007.

附中文參考文獻(xiàn)：

[1]楊維明.時(shí)空混沌和耦合映象格子[M].上海:上海科學(xué)技術(shù)教育出版社,1994.

[8]傅志堅(jiān),曾以成,徐茂林.基于單向耦合映象格子生成偽隨機(jī)位序列的兩種新方法[J].物理學(xué)報(bào),2008,57(7): 4014-4020.

[11]劉建東.基于整數(shù)耦合帳篷映射的單向Hash函數(shù)及其性能分析[J].計(jì)算機(jī)研究與發(fā)展,2008,45(3):563-569.

[13]陳帥.無線微傳感器網(wǎng)絡(luò)混沌加密理論及其關(guān)鍵技術(shù)研究[D].重慶:重慶大學(xué),2006.

[14]姜丹.信息論與編碼[M].合肥:中國科學(xué)技術(shù)大學(xué)出版社,2009.

[15]張佃中.非線性時(shí)間序列互信息與Lempel-Zi復(fù)雜度的相關(guān)性研究[J].物理學(xué)報(bào),2007,56(6):3152-3153.

[16]王永.混沌加密算法和Hash函數(shù)構(gòu)造研究[D].重慶:重慶大學(xué),2007.

SHANG Kai was born in 1990.He is an M.S.candidate at Beijing University of Chemical Technology.His research interests include security and key management for wireless sensor network,etc.

商凱（1990—），男，北京化工大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)闊o線傳感器網(wǎng)絡(luò)密鑰管理及安全等。

LIU Jiandong was born in 1966.He received the M.S.degree from Tianjin University in 1995.Now he is a professor at College of Information Engineering,Beijing Institute of Petrochemical Technology.His research interests include chaos cryptography and information hiding,etc.

劉建東（1966—），男，1995年于天津大學(xué)獲得碩士學(xué)位，現(xiàn)為北京石油化工學(xué)院信息工程學(xué)院教授，主要研究領(lǐng)域?yàn)榛煦缑艽a，信息隱藏等。

ZHANG Xiao was born in 1990.He is an M.S.candidate at Beijing University of Chemical Technology.His research interests include cryptography and RFID authentication protocols,etc.

張嘯（1990—），男，北京化工大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)镽FID認(rèn)證協(xié)議，混沌密碼等。

HU Huihui was born in 1991.He is an M.S.candidate at Beijing University of Chemical Technology.His research interests include image encryption and chaos cryptography,etc.

胡輝輝（1991—），男，北京化工大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)閳D像加密，混沌密碼等。

Integral Nonlinear Coupled Map Lattices Model and PerformanceAnalysis*

SHANG Kai1,2,LIU Jiandong1+,ZHANG Xiao1,2,HU Huihui1,2
1.College of Information Engineering,Beijing Institute of Petrochemical Technology,Beijing 102617,China
2.College of Information Science and Technology,Beijing University of Chemical Technology,Beijing 100029,China
+Corresponding author:E-mail:sky@bipt.edu.cn

By using nonlinear map—Arnold cat map as the coupling method between lattices and integral Logistic function and integral Tent function as the nonlinear function,this paper proposes the integral nonlinear coupled map lattices model based on the typical spatiotemporal chaos model—coupled map lattices model.The features of the proposed model include uniform distribution and independence.The mutual information between lattices,the distribution character,the difference characteristics,and randomness are measured to investigate the chaotic behaviors of the proposed system.The simulation results indicate that the proposed model is able to generate excellent pseudorandom sequences in parallel and each sequence is independent with others.

nonlinear couple;Arnold cat map;Logistic map;Tent map

10.3778/j.issn.1673-9418.1603083

A

：TP309.7

*The Natural Science Foundation of Beijing under Grant No.4112018(北京市自然科學(xué)基金).

Received 2016-03,Accepted 2016-07.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-07-14,http://www.cnki.net/kcms/detail/11.5602.TP.20160714.1616.018.html

SHANG Kai,LIU Jiandong,ZHANG Xiao,et al.Integral nonlinear coupled map lattices model and performance analysis.Journal of Frontiers of Computer Science and Technology,2017,11(3):389-395.