空间Arnold猫映射耦合帐篷映象格子模型的密码学特性分析

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

(北京石油化工学院信息工程学院，北京 102617)

空间Arnold猫映射耦合帐篷映象格子模型的密码学特性分析

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

(北京石油化工学院信息工程学院，北京 102617)

采用具有均匀分布特性的帐篷映射作为耦合映象格子系统的非线性函数，并用Arnold猫映射作为耦合映象格子模型中格点间的耦合方式，对典型的时空混沌模型-耦合映象格子系统进行了改进，从互信息、分布特性、相空间结构、复杂度和Lyapunov指数等方面对其进行了仿真实验和分析。仿真实验结果表明，空间Arnold猫映射耦合帐篷映象格子模型的空间格子序列具有独立性，并且系统的遍历性及统计分布特性均得到改善。

耦合映象格子；帐篷映射；Arnold猫映射；互信息

时空混纯系统随时间和空间变化，能够并行产生性能良好的多维类随机序列。时空混沌系统具有非常多的正李雅普诺夫指数， 系统在时间及空间方向上都是混沌的，其动力学行为非常丰富而复杂，空间上的任何一点的微小变化都会随时间的增加而扩散开去，产生很大的变化。利用时空混沌可以大大提高系统的复杂性，从而有利于提高系统的安全性。时空混沌研究中的典型例子是耦合映象格子(CML)模型 。从常规密码学的角度来看CML模型相当新颖。在常规密码学的领域里，有2种广为使用的手段：混淆和扩散。在CML的迭代模型中，格点间的耦合起了扩散的作用，他能将1个格点的变化扩散开去，影响其他所有格点；而每个格点的非线性动力学函数就起了混淆的作用，经过多次迭代，输出与输入的关系变得很复杂。混淆和扩散在CML迭代模型中被很好地结合在一起，这种结合会使经过多次迭代后的输出与初始条件及系统参数的关系变得极为复杂，而复杂的依赖关系可以很好地被用来设计密码算法。

由于CML模型极具密码学应用价值，进而受到密码学研究领域的广泛关注。CML模型最初由K.Kaneko等提出[1-2]。在对CML模型的研究中，Khellat等[3]提出了非局部耦合格子时空系统(Globally Nonlocal Coupled Map Lattice，GNCML)，分析了选取哪些参数时系统为混沌系统。Meherzi等[4]提出了单向耦合映象格子模型(One-way Coupled Map Lattice，OCML)，分析了模型的特点。这些模型均采用相邻耦合方式，这种相邻格子耦合是一种规则简单的线性耦合，进而使空间相邻格点生成序列相互间的独立性差，互信息量高，这表明空间相邻耦合情况下的相邻格点的时间序列互相依赖，应用于密码学领域存在明显的安全隐患。文献[5]中提出采用猫映射耦合的空间非线性耦合方式，并对模型的Lyapunov指数与Kolmogorov-Sinai熵进行了计算和分析，对模型序列间的互信息进行了研究，大部分序列间具有独立性。该文格点的非线性函数采用了Logistic映射。从密码学的角度来看，Logistic映射在统计分布特性及遍历性方面均存在明显缺陷，而帐篷映射在这些方面具有明显优势。笔者采用具有均匀分布特性的帐篷映射作为耦合映象格子系统的非线性函数，并用Arnold猫映射作为耦合映象格子模型中格点间的耦合方式，对典型耦合映象格子系统进行改进，从互信息、分布特性、相空间结构、复杂度、Lyapunov指数等方面对其进行仿真实验和分析研究。

1 基于映射的Arnold猫映射耦合帐篷映象格子模型

耦合帐篷映象格子(CML)模型的形式为：

(1)

其中非线性映射函数f采用帐篷映射：

(2)

式中：n为迭代步数；i=1，2，……，L为格点坐标，L为系统格点数；ε为耦合系数，且满足0≤ε≤1；α为帐篷映射参数，满足0≤α≤1；边界条件为xn(0)=xn(L),xn(L+1)=xn(1)，初值为[0，1]内的随机数。

帐篷映射函数具有均匀分布特性，在不同参数下分布特性保持一致，满足了密码算法的平衡性要求。但是，当帐篷映射作为耦合帐篷格子模型的非线性函数时，模型不再具有均匀分布特性[6]。同时耦合帐篷映象格子模型中，第n+1轮迭代的格点总要受到第n轮相邻格点的影响，相邻格点独立性差，互信息值大，攻击者可以用相邻格点序列来恢复或者替代未知格点随机序列，影响了基于该模型实现的密码学算法的安全性。

猫映射最早由Arnold提出[7]，因常用一张猫脸演示而得名。二维猫映射的矩阵形式为：

(3)

采用Arnold猫映射的推广形式来代替CML模型中相邻格点耦合的耦合方式[5]。空间Arnold猫映射耦合帐篷映象格子(ACTML)模型的形式为：

(4)

其中：n，i，ε表示的含义与CML模型一致，非线性映射函数f同样为帐篷映射；j，k(0

(5)

其中：p，q为映射参数，不同的p和q赋值将导致ACLML系统具有不同的动力学行为。当映射参数设置为固定值，在帐篷映射参数连续变化时多数空间格点仍具有混沌特性。

2 ACTML模型特性分析

2.1 ACTML的互信息分析

互信息可以表明2个序列的统计约束程度。序列X={x1，x2，…，xn}与Y={y1，y2，…，yn}的概率分布分别为p(xi)，p(yj)，(i，j=1，2，…，n)。则X，Y的信息熵分别为：

(6)

(7)

由X与Y构成的联合序列XY={x1y1，x1y2，…，xnyn}的概率分布分别对应{p(x1y1)，p(x1y2)，…，p(xnyn)}。联合序列XY的联合信息熵为：

(8)

则序列X与Y的互信息定义为：

(9)

互信息I(X，Y)是X和Y之间关联程度的度量指标，满足对称性、非负性以及极值性。当X，Y序列相同时互信息值为最大，当X，Y序列相互独立时互信息值为0[8]。ACTML模型中大多数的空间格子序列具有独立性，不同格点间的互信息为0。这一特性保证了ACTML模型中格点序列不会被其他格点序列所恢复。

采用等间距分割格子的方式来获取式(6)～式(8)的概率[9]，并带入式(9)计算互信息。由于当序列X和Y选取相同格点时，互信息最大，以该值对互信息序列进行归一化处理得到1个不超过1的互信息序列。选取CML的参数为ε=0.8，α=0.61， 选取ACTML的参数为p=10，q=10，ε=0.8，α=0.61，比较100个格点间的互信息，结果如图2、图3所示。由图2和图3可以看到，CML模型在对角线位置，即格点相邻附近的互信息数值较大，而ACTML模型互信息接近为0，只有(55，5)，(65，15)，(75，25)，(85，35)，(95，45)5个点互信息较大，格点位置关系明显，相互差值为10。对图2、图3中点的个数进行统计，结果如图4所示。在CML中互信息为0的比例为60%，而在ACTML中互信息为0的比例为99.9%，可见ACTML系统的不同格点序列互相独立，利用其构造密码算法更为安全。

2.2 ACTML的分布特性

统计分布特性可以直观地展示序列在各个区间的分布情况。理想的随机序列呈现均匀分布特性。ACTML模型中，选取以下参数进行实验：格点数L=15，帐篷映射系数α=0.13，耦合系数ε从0.01到0.99变化，猫映射参数p=10，q=5。序列长度为10 000的分布曲线如图5所示。由图5可以看到，随着耦合系数ε的连续变化，序列在ε∈[0.1， 0.9]之间的分布均匀，即每个长度为0.01的区间出现的概率为理论计算概率0.01左右，可以认为ACTML模型在该参数条件下为均匀分布。CML模型在与ACTML相同参数条件下的分布曲线如图6所示。

由图5、图6可以看出，耦合系数大时其分布曲线呈下凹型，耦合系数小时其分布曲线呈上凸型。ACTML模型均匀的分布曲线使得模型参数更难被分析，模型生成的序列安全性高。

2.3 ACTML的相空间结构

用同一格点序列的连续数值对(Xn，Xn+1)(0≤n≤N)构造的相空间结构图来表现序列的相关性。当序列相邻值线性相关，相空间结构图呈直线；当序列相邻值无相关性，则相空间结构图呈混沌状态，即序列相邻值的相关性越小，相空间结构混乱程度越大，在相空间中的便利性越好。

选取参数：格点数L=8，帐篷系数α=0.61，迭代步数N=400。在耦合系数ε分别为0，0.05，0.4，0.8，0.9，0.99时的CML、ACTML模型相空间结构分别如图7、图8所示。由图8可以看出，随着耦合系数的增大，ACTML模型的相空间结构的混乱程度不断增加。耦合系数为0时，相空间结构为单帐篷直线；耦合系数为0.99时，相空间结构的混乱程度增至最大，充满整个空间。对比相同参数条件下的CML模型相空间结构图(如图7所示)可以看出：在耦合系数较小(ε=0，0.05，0.4)时，2个模型的结构图的混乱程度相近，符合相空间结构在耦合系数小，相邻值相关性大的情况下数值对呈现集中分布的理论分析。伴随着耦合系数继续增大(ε=0.8，0.9，0.99)，2个模型的相空间结构趋于混乱，但ACTML模型的遍历性明显要好于CML模型，尤其在ε=0.99时，ACTML模型的结构图将整个空间充满，而CML模型则不然。通过对比发现，ACTML模型在同一格点时间序列的混沌程度上优于CML模型。ACTML模型中，通过局部格点帐篷映射的拉伸与折叠及格点间的非线性耦合的双重非线性作用，使得系统状态走向各态遍历。

2.4 ACTML的复杂度

序列复杂度是指序列接近随机序列的程度[10]，其越接近随机序列，复杂度越大，被恢复的难度就越大。目前混沌序列复杂度测算多采用Pincus提出的近似熵(ApEn)方法[11]。采用近似熵来计算，可以较为便捷地获取序列的复杂度。

CML模型和ACTML模型中，选取L=100，在耦合系数ε为0.05，0.30，0.70，0.99时分别计算其近似熵(ApEn)值，结果分别如图9、图10所示。从图9及图10中可以看到，在ε为0.05，0.30时，ACTML模型和CML模型的ApEn基本相似，因为耦合系数小的情况下序列主要由同一格点影响；当ε为0.70，0.99时，随着帐篷映射参数α的变化，ACTML模型的ApEn更为平滑，即使在α值较小时，ApEn值也较大，抗攻击分析能力强，而CML模型的近似熵在α值较小时，ApEn值较小，模型复杂度更为依赖耦合系数。对比分析得到，ACTML模型受参数影响小，安全性高。

3.5 ACTML的Lyapunov指数

Lyapunov指数为随着时间推移，相互靠近的2条轨线按照指数分离或聚合的平均变化率。其指数为负，则说明系统的整体运动是稳定的、收缩的；指数为正，则说明系统在某个方向上不断膨胀和折叠，即具有初值敏感性，此时运动是混沌状态。通常，混沌系统都具有至少1个正的Lyapunov指数[12]。实际应用中，多以最大Lyapunov指数来分析系统的性质，且计算更容易实现。

采用文献[13]中所述的方法，采用式(10)来计算最大Lyapunov指数(λmax)：

(10)

将ACTML模型的耦合系数ε、格子数L、帐篷映射参数α组合变化，经过1 000步暂态过程后，分析5 000步运算过程中最大Lyapunov指数，如图11、图12所示。由图11、图12可以看出，在耦合系数ε固定仅格子数L变化时，λmax变化小；帐篷映射参数α对λmax影响明显。另外，随着参数变化，ACTML模型的最大Lyapunov指数均为正数，具有奇异吸引子，可判定各个状态均为时空混沌系统。在模型应用于密码算法时，应选取Lyapunov指数大的区域。

4 结束语

以帐篷映射作为格点的非线性函数，采用猫映射实现空间方向上的非线性耦合，在时间及空间2个维度的非线性因素的共同作用下，系统展示出更加优越的密码学特性。实验分析结果证明，ACTML模型的混纯特性在密码学意义上优于CML系统。通过对模型实验分析可以看到，格点数目、耦合系数、帐篷映射参数等均对模型的输出有着明显的影响，同时需要认识到在某些参数情况下模型的表现并不理想。所以，在应用模型时，需要调整相关参数，以达到理想效果。

[1] Kaneko K. Period-doubling of kink-antikink patterns， quasi-periodicity in antiferro-like structures and spatial intermittency in coupled map lattices-toward a prelude to a field theory of chaos[J]. Prog Theor Phys， 1984，72:480-486.

[2] Mayer-Kress G， Kaneko K. Spatiotemporal chaos and noise[J]. Stat Phys， 1989，54:1489.

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

[4] Meherzi S， Marcos S， Belghith S. A new spatiotemporal chaotic system with advantageous synchronization and unpredictability features，2006[C]. Japan: International Symposium on Nonlinear Theory and its Applications， Research Society of Nonlinear Theory and its Applications，2006:473-477.

[5] Zhang Yingqian， Wang Xingyuan. Spatiotem-poral chaos in Arnold coupled logistic map lattice[J]. Nonlinear Analysis Modelling and Control， 2013，18(4):526-541.

[6] 刘建东，杨凯，余有明.改进型耦合帐篷映像格子模型及其性能分析[J].计算机研究与发展，2011，48(9):1667-1675.

[7] Arnold E A， Avez A. Ergodic Problems of Classical Mechanics[M]. New Jersey: Benjamin， W A， 1968.

[8] 张佃中.非线性时间序列互信息与Lempel-Ziv复杂度的相关性研究[J].物理学报，2007，56(6):3152-3153.

[9] 杨志安，王光瑞，陈式刚.用等间距分格子法计算互信息函数确定延迟时间[J].计算物理，1995，12(4):442-448.

[10] 孙克辉，贺少波，尹林子，等.模糊熵算法在混沌序列复杂度分析中的应用[J].物理学报，2012，61(13):1305071-1305077.

[11] Steven M Pincus. Approximate entropy: a complexity measure for biological time series data[C]. Bioengineering Conference， 1991.， Proceedings of the 1991 IEEE Seventeenth Annual Northeast，1991：35-36.

[12] 张盈谦.混合时空混沌模型在混沌密码学中的应用研究[D].大连：大连理工大学，2015.

[13] 赖建文，周世平，李国辉，等.非重正交的李雅普诺夫指数谱的计算方法[J].物理学报，2000，49(12):2328-2333.

Cryptographic Analysis of Spatial Arnold Coupled Tent Map Lattices System

SHANG Kai， LIU Jiandong*， ZHANG Xiao， HU Huihui

(Information Engineering College， Beijing Institute of Petrochemical Technology， Beijing 102617， China)

By employing equally distributed tent map as the nonlinear function and Arnold cat maps as the coupling method between lattices in coupled map lattices, this paper proposed Arnold Coupled Tent Map Lattices system(ACTML) based on the classic model of spatiotemporal chaos-Coupled Map Lattices system (CML). A detailed analysis of the system is done compared with Coupled Map Lattices system, including mutual information, distribution character, phase space structure, complexity, and Lyapunov exponent. The results indicate that spatial lattices of Arnold Coupled Tent Map Lattices system are independent of each others. In addition, ergodicity and distributions are enhanced.

coupled map lattices； tent map； arnold cat maps； mutual information

2016-05-06

北京市自然科学基金项目(4112018)

商凯(1990—)，男，硕士生，主要研究方向为无线传感器网络的密钥管理等，E-mailsky@bipt.edu.cn；刘建东(1966—)，男，硕士，教授，研究方向为混沌密码与信息隐藏等，E-mail:liujiandong@bipt.edu.cn.

TP309.7

A