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

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

1.北京石油化工學院 信息工程學院，北京 102617

2.北京化工大學 信息科學與技術學院，北京 100029

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

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

1.北京石油化工學院 信息工程學院，北京 102617

2.北京化工大學 信息科學與技術學院，北京 100029

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 信息熵和互信息

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

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

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

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

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

互信息滿足非負性和對稱性。當X和Y完全相同時互信息最大，當X和Y相互獨立時互信息為0。

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

2.2 分布特性

選取32個格點，每個格點變量取8位字長，貓映射參數(shù)p=10，q=10，分別選取整數(shù)Logistic映射和整數(shù)Tent映射為非線性函數(shù)，對式（4）進行迭代，生成32個格點的時空混沌序列，如圖5和圖6所示（i為格點號，n為迭代次數(shù)，x為序列值）?？梢钥吹?，分別選取整數(shù)Logistic映射和整數(shù)Tent映射時，式（4）均呈現(xiàn)時空混沌狀態(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ù)Logistic映射）

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

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

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

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

2.3 差值分析

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

式（4）中非線性函數(shù)分別選取整數(shù)Logistic映射和整數(shù)Tent映射，統(tǒng)計非線性耦合模型的1～50階差值如圖9和圖10所示（k為差值階數(shù)，dn為差值數(shù)值，F(xiàn)requence為頻數(shù)）。模型在兩種映射下的差值均從dn=1開始線性遞減，符合理論上隨機序列的差值分布特性（根據(jù)文獻[16]，整數(shù)域差值為0的頻數(shù)為差值為1的頻數(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 隨機性測試

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

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

3 結(jié)束語

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

[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.

附中文參考文獻：

[1]楊維明.時空混沌和耦合映象格子[M].上海:上?？茖W技術教育出版社,1994.

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

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

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

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

[15]張佃中.非線性時間序列互信息與Lempel-Zi復雜度的相關性研究[J].物理學報,2007,56(6):3152-3153.

[16]王永.混沌加密算法和Hash函數(shù)構造研究[D].重慶:重慶大學,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—），男，北京化工大學碩士研究生，主要研究領域為無線傳感器網(wǎng)絡密鑰管理及安全等。

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年于天津大學獲得碩士學位，現(xiàn)為北京石油化工學院信息工程學院教授，主要研究領域為混沌密碼，信息隱藏等。

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—），男，北京化工大學碩士研究生，主要研究領域為RFID認證協(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—），男，北京化工大學碩士研究生，主要研究領域為圖像加密，混沌密碼等。

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(北京市自然科學基金).

Received 2016-03,Accepted 2016-07.

CNKI網(wǎng)絡優(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.