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

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

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

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

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

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

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

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

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

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

1 引言

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

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

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

2 整數非線性耦合映象格子模型

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

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

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

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

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

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

動態整數Logistic映射的形式為：

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

動態整數Tent映射的形式為：

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

2.1 信息熵和互信息

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

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

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

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

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

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

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

2.2 分布特性

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

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

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

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

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

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

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

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

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

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

2.3 差值分析

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

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

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

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

2.4 隨機性測試

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

Table 2 Results of randomness test表2 隨機性測試結果

3 結束語

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

[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]劉建東.基于整數耦合帳篷映射的單向Hash函數及其性能分析[J].計算機研究與發展,2008,45(3):563-569.

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

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

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

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

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

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認證協議，混沌密碼等。

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網絡優先出版: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.