精确混沌迭代和近似混沌迭代的比较

张翔 陆正福

摘   要：对于浮点数（双精度数）计算中混沌映射存在着比较明显的有限精度效应，文章设计了一种多精度计算方法，并使用多精度计算来进行混沌迭代运算，比较了精确混沌迭代和近似混沌迭代计算结果的差异。

关键词：混沌映射;多精度计算;迭代

1    混沌简要介绍

1989年英国数学家Matthews提出混沌加密方法以来，混沌系统陆续被应用于保密通信领域。混沌之所以能够成为一种新的密码体制，是因为有以下几个适合作为密码系统的特性：遍历性、混合性、非周期性以及对初值的敏感依赖特性。

然而，由于实际计算中存在着有限精度效应，混沌序列在迭代过程中必将退化为周期序列且周期难以度量。此外，由于使用数值映射作为密码流发生器，有限精度也限制了密钥空间的大小。这使得混沌序列原本优良的性能大打折扣，难以抵御统计分析和参数重构等攻击。

在这些方面有着许多的研究，Shujun等[1]中介绍了Baptista混沌密码及其改进的方法，也指出Baptista混沌密码及其改进的方法的缺陷和破解方法。周红等[2-4]中为了提高混沌密码的保密性，分别把m序列扰动实现，反馈控制，前馈型设计的思想在有限精度下实现。

上面所提到的论文虽然提高了混沌序列的周期，但是由于使用的精度不高，混沌序列的周期也不会超过一定值，所以增加精度才是解决有限精度所带来影响的根本办法。

本文提出了一种多精度计算方法，可以有效地提高精度，从而减少混沌映射中的有限精度效应。但是计算机中的空间和时间是有限的（尤其是时间），所以不可以无限制地提高精度。因此，本文提出了一种结合多精度计算生成混沌映射的方式，

2    多精度数及其运算

本文中的程序是在Java平台下实现的，在这里没有使用Java程序中的BigDecimal类，而是使用了一种类似于科学计数法的方式来保存数并进行数的加减乘除运算。

2.1  多精度数的储存方式

本文中定义了一个类来表示数，该类是这样定义的：

varNumber

{

byte value[];

int exponent;

byte type;

}

包括value[]，exponent，type 3个元素，其中，value数组表示该数的每一位上的值，value[0]表示该数的最高位的值，value[1]表示该数的次高位的值，以此类推，value[len-1]（len为value数组的长度）表示该数的最低位的值;在这里定义数的形式为（0.value）*（256^exponent），exponent表示指数;type用来标识数的类型，用0表示正实数，1表示负实数。

在这里使用了256进制，目的在于两个方面：（1）可以充分利用存储空间;（2）在把数转化为二进制时在程序上容易实现。

本文中所定义的数不但可以表示实数，同样可以用来表示其他类型的数。比如可以用type=2表示实部为正的纯虚数，用type=3表示实部为负的纯虚数。

最后在本文中定义数的标准形式为value数组的前后第一位均不为0。特殊的定义0为：

varNumber

{

value[0] = 0;

exponent = - 2147483648;

type = 0;

}

其中，-2147483648为Java中最小的整型数。

2.2  多精度数的计算

本文中的多精度计算包括正实数范围内的加减乘除计算，实数范围内的加减乘除计算。

由于在Java程序中byte型数进行加减乘除运算的结果为int型数，因此，在中间计算时使用的数据类型是int型数，最后，再把结果转化为byte型数。所以，本文中使用了byte数组的全空间来存储数位的方式并不会在计算中造成数据溢出。

3    混沌映射

3.1  Logistic映射

Logistic映射又被称为虫口问题，其映射形式为：

Xn+1=Xn（1-Xn），0

其中，1≤μ≤4，μ∈（0，4）称为分形参数。当0<μ≤3时，迭代后的值为稳定不动点，μ逐渐增大，出现倍周期分岔现象，当3.569 945 972…<μ≤4时，系统工作于混沌状态。此时所产生的序列{Xn，n=0，1，…}具有非周期、非收敛以及对初始值十分敏感等特性。

3.2  分段线性映射

分段线性映射最常见的是帐篷映射和移位映射。帐篷映射的迭代公式如下：

其中，Xn，p∈（0，1）分别为系统的状态和参数。

移位映射的迭代公式如下：

Xn+1=aXn（mod1），Xn∈（0，1）

其中，Xn为系统的状态，a>1为系统的参数。

4    精确混沌迭代和近似混沌迭代的比较

本文选取Logistic映射进行研究，在Logistic映射中取参数μ=4，初值，x0在程序中表示为：

varNumber

{

value[0]= 32;

exponent=0;

type=0

}

实验步骤如下：

（1）对该映射进行n次的迭代计算，并在迭代中保留小數的所有位数。

（2）对经过迭代计算得到的数进行取舍（四舍五入），保留其前10位，得到精确迭代计算的结果。

（3）把初值代入混沌映射中进行计算，得到x1的值，对x1的标准形式进行取舍，在byte数组中只保留前10位（不足10位的全部保留）。

（4）按照（3）的方法计算x2，x3，…xn，xn为近似迭代计算的结果。

（5）对精确迭代计算的结果和近似迭代计算的结果进行比较。

5    實验结果和总结

在实验中分别取迭代次数n为10，15，20次，并进行比较，比较结果如表1所示。

从表1可知，在迭代次数不高的时候，精确混沌迭代和近似混沌迭代的结果差别不大，但是不同的位数增加了。在无法在精确计算的条件下进行高次迭代（比如300次）时，可以推断只要迭代次数足够，近似计算所产生的扰动对混沌映射有很大的影响。

[参考文献]

[1]SHUJUN L，GUANRONG C，KWOK-WO W，et al.Baptista-type chaotic cryptosystems problems and countermeasures[J].Physics Letters，2004（338）：368-375.

[2]周红，凌燮亭.有限精度混沌系统的m序列扰动实现[J].电子学报，1997（7）：95-97.

[3]周红，罗杰，凌燮亭.混沌非线性反馈密码序列的理论设计和有限精度实现[J].电子学报，1997（10）：57-60.

[4]周红，俞军，凌燮亭.混沌前馈型流密码的设计[J].电子学报，1998（1）：98-101.

Comparison of exact chaos iteration and approximation chaos iteration

Zhang Xiang1， 2， Lu Zhengfu2

（1.Puer University， Puer 665000， China; 2.Department of Mathematics， Yunnan University， Kunming 650091， China）

Abstract：There are some problem in chaos because of finite precison. It is obvious when calculating chaos by floating-point numbers（double precision number）. This paper presents a more accurate method（multi-precision arithmetic）and calculate chaos by this method， comparing the result between in exact chaos iteration and approximation chaos iteration.

Key words：chaos; multi-precision arithmetic; iteration