商 凯，刘建东，张 啸，胡辉辉

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].上海:上海科学技术教育出版社,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.