基于k错穷尽熵分析离散混沌映射稳定性的新方法✴

刘景琳，冯明库（广东技术师范学院电子与信息学院，广州510665）

基于k错穷尽熵分析离散混沌映射稳定性的新方法✴

刘景琳，冯明库
（广东技术师范学院电子与信息学院，广州510665）

为衡量离散混沌映射的随机本质，在用穷尽熵计算混沌序列类随机性强弱的基础上，提出了k错穷尽熵的定义来分析离散混沌映射稳定性的优劣，并证明了其两个基本性质。以Logistic映射、Henon映射、Sine映射、Chebyshev映射和Cubic映射等5种常见离散混沌映射为例，说明了该方法的应用。实验结果表明，此方法能反映离散混沌映射的随机本质，可用来有效识别不同离散混沌映射的稳定性强弱。

保密通信；离散混沌映射；类随机性；稳定性；k错穷尽熵

1 引言

用混沌系统产生的伪随机序列由于具有类随机性、对初始值和控制参数的敏感依赖性、遍历性、易于产生和复制等特点，因此现已被广泛应用于保密通信的研究。但由于计算机的有限精度效应，实值混沌被量化成数字混沌序列时，其混沌特性存在明显的退化，从而使生成的混沌序列类随机性变差，加密信息的安全性降低，所以获取性能优良的数字混沌序列应用于密码学、扩频通信等领域已成为当前的研究热点。

近年来，已有许多文献致力于混沌信号类随机性强弱的研究。Kolmogorov于20世纪60年代提出了一种度量序列复杂性的方法［1］、Lempel和Ziv接着给出了其具体计算算法［2］。1985年，R.Lópezruiz、Mancini和Calbet提出了一个统计复杂性测量法［3］，简称LMC法或CLMC法。David P.Feldman在文献［4］中测试了CLMC法的属性后发现它既不是一个强度热力学变量，也不是一个广度热力学变量，然后提出了一个简单的修改来增加其广度。Pincus从衡量时间序列复杂性的角度提出并发展了近似熵（ApEn）的概念［5］，现已被NIST美国国家标准与技术研究所列为16种随机序列测试方法中的一种。

以上文献分析的都是混沌系统类随机性的强弱，并没有涉及其稳定性评价问题。从密码学的观点看，好的伪随机序列不仅要有好的统计分布、长周期和大线性复杂度等特性，而且还应有良好的稳定性。文献［6］深入讨论了流密码稳定性的重要性，定义了重量复杂度，即k错线性复杂度来量度二进制序列的稳定性。然而文献［7］表明，k错线性复杂度并不能有效区分不同混沌伪随机序列的稳定性。本文拟在文献［8］给出的计算序列穷尽熵（Exhaustive Entropy，ExEn）的基础上，提出k错穷尽熵的定义，用来衡量离散混沌映射类随机性的稳定性，并证明其两个基本性质，然后以Logistic映射、Henon映射、Sine映射、Chebyshev映射和Cubic映射为例，说明该方法的具体应用。

2 穷尽熵

2.1 序列的生成与再生

S表示一个0、1序列，l（S）表示其序列长度，l（S）≥0。若l（S）=0，则表示该序列的长度是0，是个空序列Λ。

假若存在一整数i，使Q=S（1，i），我们称Q是S的前缀子序列，S是Q的延伸。在序列S的长度没有特别指明时，用符号π可以方便地定义S的前缀子序列。

当一个序列被它的子序列串联时，其实是一个简单的复制过程。如W=S（i，j），串联序列R=SW可看作是序列S从序列值Si+m-1（m=1，2，…，j-i +1）开始的自我简单复制。

序列扩展R=SQ称为序列S的再生［2］，记作S→R，Q∈v（Rπ），复制始自Sp，即Q=R（p，l（Q）+ p-1），如001→00101010，p=2。

假若S（1，j）→Sπ，j＜l（S），称非空序列S是可生成的［2］，记作S（1，j）⇒S。S（1，j）被称作序列S的一个基序列。

序列的生成和再生是不同的。再生是序列自我的简单复制过程，而序列的生成中复制序列的最后一个序列值是变化的。

2.2 穷尽熵

事实上，每一个非空序列S都可看作是其前缀子序列Q的生成过程：Q⇒S，Λ=S（1，0）⇒S（1，1）=S1，从其基序列Λ开始经过i步生成S（1，hi），接着生成S（1，hi+1），即S（1，hi）⇒S（1，hi+1），直到生成S的最后一个序列值。序列S可用以下生成过程表示：

H（S）=S（1，h1）S（h1+1，h2）…S（hm-1+1，hm）其中Hi（S）=S（hi-1+1，hi），i=1，2，…，m，h0≡0称作H（S）的组成部分。

一组成部分Hi（S）和其相应的生成过程S（1，hi-1）⇒S（1，hi）若满足S（1，hi-1）不能再生S（1，hi），则称此生成过程是穷尽的［2］。

序列S的穷尽历史记作E（S）。用CH（S）来表示序列S的生成过程H（S）中的组成部分的个数，C（S）来表示序列S生成的随机步数，则C（S）= min｛CH（S）｝，也就是C（S）是生成序列S需要的最小生成步数。

上述定理只是对序列类随机性强弱的保守估测，为了定量准确地区别不同系统的类随机性，我们用公式（1）来计算整个序列的类随机性强弱：

式中，pi为序列的各个穷尽部分（包括最后一个不是穷尽的组成部分）在整个序列中占的比率。这一概念的严格理论由下面的定理2给出。

证明：根据熵的定义，ExEn（s）≥0是显然的。

该定理说明，穷尽熵非负，且在穷尽步数确定的情况下，当各穷尽部分的概率等值时，穷尽熵值最大。又因为以10为底数的对数是增函数，所以穷尽步数N越大，穷尽熵值也越大，序列的类随机性就越强。

3 k错穷尽熵

序列随机性的稳定性一直是密码学者们关注的热点。为度量给定序列的类随机性的稳定性，引入如下定义：

定义设sN、tN是有限域GF（2）上的N长二进制序列。sN的重量穷尽熵定义（Weight Exhaustive Entropy）为

式中，WH（tN）表示tN的Hamming重量，即tN的非零分量个数。

现描述重量穷尽熵的几何意义。考虑空间GF（2）N，以Hamming距离dH作为它的距离，并记作

2．金融结构通过技术的转移和扩散对产业结构的促进作用。技术转移与技术扩散都是一种新技术由高水平向低水平的传播，没有扩散，创新便不可能有经济影响。学者通过各种模型对其进行研究，如谢建国通过两阶段古诺模型、罗德明等人利用罗默模型讨论了技术转移与扩散对实体经济的作用。[15][16]其传导机理主要有以下几类。

上式可理解为重量穷尽熵是原序列任意改变k位后的序列穷尽熵的最小值，所以，也可被称为k错穷尽熵（k-error Exhaustive Entropy）。

性质1：ExEnN（sN）=ExEn0（sN）=ExEn（sN）

由重量穷尽熵的定义知，性质1是显然的。N长序列改变N位后的穷尽熵和原序列的穷尽熵是相等的。

由于tN中非零分量的个数等于sN中零分量的个数，则sN+tN后有可能得到全为1或全为0的长度为N的序列，

被测序列的稳定性优劣可通过原序列穷尽熵与k错穷尽熵之间的偏离程度来衡量，即：

从式（4）可知，RExEn越小，说明N长序列改变k位后对穷尽熵影响不大，则被测序列的稳定性强，反之则稳定性较弱。

4 离散混沌映射序列的稳定性分析

Logistic映射、Henon映射、Sine映射、Chebyshev映射和Cubic映射的方程和参数如表1所示。对每个离散映射，随机取其10个分散初始值进行迭代，为消除过渡态的影响，去除前10 000次迭代值，从10001开始连续取128、256、512个数值进行二值量化后得到二进制混沌序列，并计算每个混沌序列的穷尽熵和各k错穷尽熵。对于同k值穷尽熵，取其不同初始值下的k错穷尽熵的平均值作为该k值下的k错穷尽熵，测试结果如表2所示。

根据公式（4）和表2的各k错穷尽熵的平均值计算RExEn，绘制各混沌映射序列的穷尽熵变化快慢与序列改变比特个数的关系图，如图1所示。从表2和图1可知，原序列改变的比特数越多，各k错穷尽熵越小，与原序列的穷尽熵的偏离程度越大。当N=128（图1（a））时，随着k的增加，Henon映射和Sine映射的RExEn值变化最快，而Logistic映射和Cubic映射的RExEn值变化最慢，说明Henon映射和Sine映射类随机性的稳定性差，而Logistic映射和Cubic映射类随机性的稳定性强，Chebyshev映射的稳定性介于中间。从图1（b）可知，当N=256时，随着k的增加，Sine映射的RExEn值变化最快，最不稳定，Henon映射其次，而Logistic映射的RExEn值变化最慢，稳定性最强。在图1（c）中，Sine映射依然是最不稳定的，而Logistic映射类随机性仍是最稳定的，Cubic映射、Chebyshev映射和Henon映射介于之间，稳定性依次降低。总之，在这5种常见的离散混沌映射中，Logistic映射的稳定性是最优的，这也是众多研究者多采用Logistic映射进行混沌保密通信的原因所在［9-11］。

5 结论

本文提出了k错穷尽熵的概念，用于判定不同混沌映射的稳定性强弱，并证明了其两个基本性质。5个离散混沌映射的测试结果表明了此方法的有效性。相对于k错线性复杂度，k错穷尽熵不仅能用来定量判定离散混沌映射类随机性的强弱，还能有效区分其稳定性优劣，且编程简单，易于实现，对于数字混沌保密通信中混沌流密码的安全性检测具有实际工程应用价值。此方法对连续混沌系统的适用情况以及穷尽熵与近似熵之间的关系将是下一步研究的方向。

［1］Kolmogorov A N.Three approaches to the quantitative definition ofinformation［J］.Problems of Information Transmission，1965，1（1）：1-7.

［2］Lempel A，Ziv J.On the complexity of finite sequences［J］. IEEE Transactions on Information Theory，1976，22（1）：75-81.

［3］López-Ruiz R，Mancini H L，Calbet X.A statistical measure of complexity［J］.Physics Letters A，1995，209（5-6）：321-326.

［4］Feldman D P，Crutchfield J P.Measure of statistical complexity：why？［J］.Physics Letters A，1998，238：244-252.

［5］Pincus S M.Approximate Entropy as a measure of system complexity［J］.Proceedings of The National Academy of Sciences，1991，88（6）：2297-2301.

［6］Ding C S，Xiao C Z，Shan W J.The stability theory of stream cippers［M］.New York：Spinger-Verlag，1991.

［7］Xiang F，Qiu S S.Analysis on stability of binary chaotic pseudorandom sequence［J］.IEEE Communications Letters，2008，12（5）：337-339.

［8］冯明库，丘水生，刘雄英，等.一种离散混沌序列类随机性分析法［J］.系统工程与电子技术，2008，30（5）：968-972. FENG Ming-ku，QIU Shui-sheng，LIU Xiong-ying，etal. Analysis on the random-like property of discrete chaotic sequences［J］.Systems Engineering and Electronics，2008，30（5）：968-972.（in Chinese）

［9］Kocarev L，Jakimoski G.Logistic map as a block encryption algorithm［J］.Physics Letters A，2001，289（4-5）：199-206.

［10］Álvarez G，Montoya F，Romera M，et al.Key stream cryptanalysis of a chaotic cryptographic method［J］.Computer Physics Communications，2004，156（2）：205-207.

［11］Pareek N K，Patidar V，Sud K K.Image encryption using chaotic Logistic map［J］.Image and Vision Computing，2006，24（9）：926-934.

LIU Jing-lin was born in Shantou，Guangdong Province，in 1964.She received the B.S.degree from South China Normal University in 1987.She is now an associate professor.Her research concerns electronics application.

Email：liujinglin1964＠126.com

冯明库（1970—），男，山东新泰人，2008年于华南理工大学获博士学位，现为副教授，主要研究方向为非线性理论、混沌理论及混沌保密通信等。

FENG Ming-ku was born in Xintai，Shandong Province，in 1970.He received the Ph.D.degree from South China University of Technology in 2008.He is now an associate professor.His research interests include nonlinear theory，chaos theory and chaos secure communication.

Email：fengmk＠163.com

A New Approach to Analyse Discrete Chaotic Maps Stability Based on k-error Exhaustive Entropy

LIU Jing-lin，FENG Ming-ku
（College of Electronic＆Information，Guangdong Polytechnical Normal University，Guangzhou 510665，China）

In order to reflectthe random nature ofdiscrete chaotic maps，the notion of k-error exhaustive entropy is proposed to analyse the stability of discrete chaotic maps，which is based on exhaustive entropy used to measure the strength of random-like property of chaotic sequences.And its two basic properties are proved.Then with five common discrete chaotic maps，such as Logistic map，Henon map，Sine map，Chebyshev map and Cubic map，an example is presented to demonstrate how the method works.Experimentresults indicate thatthe approach can reflectthe random nature ofdiscrete chaotic map and can be used to evaluate the stability ofdifferent discrete chaotic maps effectively.

secure communication；discrete chaotic map；random-like property；stability；k-error exhaustive entropy

The National Natural Science Foundation of China（No.60802004，51003035）；The Technology Project of Guangdong Province（2011B080701092）

TN918；TP309；O415.5

A

10.3969／j.issn.1001-893x.2012.02.010

刘景琳（1964—），女，广东汕头人，1987年于华南师范大学获学士学位，现为副教授，主要研究方向为电子技术应用；

1001-893X（2012）02-0170-05

2011-09-28；

2011-11-22

国家自然科学基金资助项目（60802004，51003035）；广东省科技计划项目（2011B080701092）