混沌流密码研究
胡汉平1 董占球2
（华中科技大学图像识别与人工智能研究所/图像信息处理与智能控制教育部重点实验室
**科学院研究生院，）
摘要：在数字化混沌系统和基于混沌同步的保密通信系统的研究中存在一些亟待解决的重要问题：数字化混沌的特性退化，混沌时间序列分析对混沌系统安全性的威胁等，已严重影响着混沌流密码系统的实用化进程。为此，提出了通过变换的误差补偿方法克服数字混沌的特性退化问题；构建混沌编码模型完成对混沌序列的编码、采样，由此得到满足均匀、独立分布的驱动序列；引入非线性变换，以抵抗对混沌流密码系统安全性的威胁。关键词：混沌流密码系统；特性退化；非线性变换；混沌时间序列分析
1.引言
随着以计算机技术和网络通信技术为代表的信息技术的不断发展和迅速普及，通信保密问题日益突出。信息安全问题已经成为阻碍经济持续稳定发展和威胁**安全的一个重要问题。众所周知，密码是信息安全的核心，设计具有自主知识产权的新型高性能的密码体制是目前最亟待解决的重要问题。混沌是确定性系统中的一种貌似随机的运动。混沌系统都具有如下基本特性：确定性、有界性、对初始条件的敏感性、拓扑传递性和混合性、宽带性、快速衰减的自相关性、长期不可预测性和伪随机性[1]，正是因为混沌系统所具有的这些基本特性恰好能够满足保密通信及密码学的基本要求：混沌动力学方程的确定性保证了通信双方在收发过程或加解密过程中的可靠性；混沌轨道的发散特性及对初始条件的敏感性正好满足shannon提出的密码系统设计的第一个基本原则――扩散原则；混沌吸引子的拓扑传递性与混合性，以及对系统参数的敏感性正好满足shannon提出的密码系统设计的第二个基本原则――混淆原则；混沌输出信号的宽带功率谱和快速衰减的自相关特性是对抗频谱分析和相关分析的有利保障，而混沌行为的长期不可预测性是混沌保密通信安全性的根本保障等。因此，自1989年r.mathews,d.wheeler,l.m.pecora和carroll等人首次把混沌理论使用到序列密码及保密通信理论以来，数字化混沌密码系统和基于混沌同步的保密通信系统的研究已引起了相关学者的高度关注[2]。虽然这些年的研究取得了许多可喜的进展，但仍存在一些重要的基本问题尚待解决。1.1 数字混沌的特性退化问题
在数字化的混沌密码系统的研究方向上，国内外学者已经提出了一些比较好的数字混沌密码系统及其相应的密码分析方法：文献[3]提出基于帐篷映射的加解密算法；文献[4]1998年fridrich通过定义一种改进的二维螺旋或方形混沌映射来构造一种新的密码算法；文献[5,6]提出把混沌吸引域划分为不同的子域，每一子域与明文一一对应，把混沌轨道进入明文所对应的混沌吸引域子域的迭代次数作为其密文；在文献[7]中，作者把一个字节的不同比特与不同的混沌吸引子联系起来实现加/解密；文献[8]较为详细地讨论了通过混沌构造s盒来设计分组密码算法的方法；文献[9,10]给出了混沌伪随机数产生的产生方法；英国的safechaos公司将混沌用于公钥密码体制，推出了chaos+public key(v4.23)系统[11]；等等。但是，这些数字混沌系统一般都是在计算机或其它有限精度的器件上实现的，由此可以将混沌序列生成器归结为有限自动机来描述，在这种条件下所生成的混沌序列会出现特性退化：短周期、强相关以及小线性复杂度等[12-15]，即数字混沌系统与理想的实值混沌系统在动力学特性上存在相当大的差异。它所带来的混沌密码系统安全的不稳定性是困扰混沌密码系统进入实用的重要原因[16]。尽管有人指出增加精度可以减小这一问题所造成的后果，但其代价显然是非常大的。1.2 对混沌流密码系统的相空间重构分析
目前，对混沌保密通信系统的分析工作才刚刚起步，主要方法有：统计分析（如周期及概率分布分析和相关分析等）、频谱分析（包括傅立叶变换和小波变换等）和混沌时间序列分析[17]。前两者都是传统的信号分析手段，在此就不再赘述，而混沌时间序列是近20年来发展的一门扎根于非线性动力学和数值计算的新兴学科方向。从时间序列出发研究混沌系统，始于packard等人于1980年提出的相空间重构（phase space reconstruction）理论。众所周知，对于决定混沌系统长期演化的任一变量的时间演化，均包含了混沌系统所有变量长期演化的信息（亦称为全息性），这是由混沌系统的非线性特点决定的，这也是混沌系统难以分解和分析的主要原因。因此，理论上可以通过决定混沌系统长期演化的任一单变量的时间序列来研究混沌系统的动力学行为，这就是混沌时间序列分析的基本思想。混沌时间序列分析的目的是通过对混沌系统产生的时间序列进行相空间重构分析，利用数值计算估计出混沌系统的宏观特征量，从而为进一步的非线性预测[18]（包括基于神经网络或模糊理论的预测模型）提供模型参数，这基本上也就是目前对混沌保密通信系统进行分析或评价的主要思路。描述混沌吸引子的宏观特征量主要有：lyapunov指数（系统的特征指数）、kolmogorov熵（动力系统的混沌水平）和关联维（系统复杂度的估计）等[17]。而这些混沌特征量的估计和poincare截面法都是以相空间重构以及f.takens的嵌入定理为基础的，由此可见相空间重构理论在混沌时间序列分析中的重大意义。1.3 对混沌流密码系统的符号动力学分析
我们在以往的实验分析工作中都是针对混沌密码系统的统计学特性进行研究的，如周期性、平衡性、线性相关性、线性复杂度、混淆和扩散特性等，即使涉及到非线性也是从混沌时间序列分析（如相图分析或分数维估计等）的角度出发进行研究的。然而，符号动力学分析表明，混沌密码系统的非线性动力学分析同样非常主要，基于实用符号动力学的分析可能会很快暴露出混沌编码模型的动力学特性。基于gray码序数和单峰映射的符号动力学之间的关系，文献[20]提出了一种不依赖单峰映射的初始条件而直接从单峰映射产生的二值符号序列来进行参数估计的方法。分析结果表明，基于一般混沌编码模型的密码系统并不如人们想象的那么安全，通过对其产生的一段符号序列进行分析，甚至能以较高的精度很快的估计出其根密钥（系统参数或初始条件）。上述结论虽然是针对以单峰映射为主的混沌编码模型进行的分析，但是，混沌流密码方案的安全性不应该取决于其中采用的混沌系统，而应该取决于方案本身，而且单峰映射的低计算复杂度对于实际应用仍是非常有吸引力的。因此，我们认为，如果希望利用混沌编码模型来设计更为安全的密码系统，必须在混沌编码模型产生的符号序列作为伪随机序列输出（如用作密钥流或扩频码）之前引入某种扰乱策略，这种扰乱策略实质上相当于密码系统中的非线性变换。该非线性变换不应影响混沌系统本身的特性，因为向混沌系统的内部注入扰动会将原自治混沌系统变为了非自治混沌系统，但当自治混沌系统变为非自治混沌系统之后，这些良好特性可能会随之发生较大的变化，且不为设计者所控制。这样有可能引入原本没有的安全隐患，甚至会为分析者大开方便之门。上述非线性变换还应该能被混沌编码模型产生的符号序列所改变。否则，分析者很容易通过输出的伪随机序列恢复出原符号序列，并利用符号动力学分析方法估计出混沌编码模型的系统参数和初始条件。因此，非线性变换的构造就成了设计高安全性数字混沌密码系统的关键之一。2.混沌流密码系统的总体方案
为克服上述问题，我们提出了如下的混沌流密码系统的总体方案，如图1所示：
在该方案中，首先利用一个混沌映射f产生混沌序列xi，再通过编码c产生符号序列ai，将所得符号序列作为驱动序列ai通过一个动态变化的置换bi以得到密钥流ki，然后据此对置换进行动态变换t。最后，将密钥流（即密钥序列）与明文信息流异或即可产生相应的密文输出（即输出部分）。图1中的初始化过程包括对混沌系统的初始条件、迭代次数，用于组合编码的顺序表以及非线性变换进行初始化，初始化过程实质上是对工作密钥的输入。在图1所示的混沌编码模型中，我们对实数模式下的混沌系统的输出进行了编码、采样。以log**tic为例，首先，以有限群论为基本原理对驱动序列进行非线性变换，然后，根据有限群上的随机行走理论，使非线性变换被混沌编码模型产生的驱动序列所改变。可以从理论上证明，我们对非线性变换采用的变换操作是对称群的一个生成系，所以，这里所使用的非线性变换的状态空间足够大（一共有256！种）。3.克服数字混沌特性退化的方法
增加精度可以在某些方面减小有限精度所造成的影响，但效果与其实现的代价相比显然是不适宜的。为此，周红等人在文献[22]中提出将m序列的输出值作为扰动加到数字混沌映射系统中，用于扩展数字混沌序列的周期；王宏霞等人在文献[23]中提出用lfsr的输出值控制数字混沌序列输出，从而改善混沌序列的性质；李汇州等人在文献[24]中提出用双分辨率的方法解决离散混沌映射系统的满映射问题。上述方法又带来新的问题：使用m序列和lfsr方法，混沌序列的性质由外加的m序列的性质决定；使用双分辨率时，由于输入的分辨率高于输出的分辨率，其效果与实现的代价相比仍然没有得到明显的改善。为此，我们提出了一种基于lyapunov数的变参数补偿方法。由于lyapunov数是混沌映射在迭代点处斜率绝对值的几何平均值，所以，可以将它与中值定理结合对数字混沌进行补偿。以一维混沌映射为例，该补偿方法的迭代式为：
（1）
式中，为lyapunov数，ki是可变参数。参数ki的选择需要满足下面几个条件：
（1）ki的选取应使混沌的迭代在有限精度下达到满映射；（2）ki的选取应使混沌序列的分布近似地等于实值混沌的分布；（3）ki的选取应使混沌序列的周期尽可能的长。根据上述几个条件，我们已经选取了合适的80个参数，并且以log**tic为例对该变参数补偿方法输出的混沌序列进行了分析。在精度为32位的条件下，我们计算了混沌序列的周期，其结果如下：
除周期外，我们还对复杂度、相关性和序列分布进行了检测。从结果可知，该变参数补偿方法，使得在不降低混沌的复杂度基础上，增长其周期，减弱相关性，使其逼近实值混沌系统。该方法不仅非常明显地减小了有限精度所造成的影响，使数字混沌序列的密度分布逼近实值混沌序列的理论密度分布，改善数字混沌伪随机序列的密码学性质，而且极大地降低实现其方法的代价。4.非线性变换
为克服符号动力学分析对混沌密码系统的威胁，我们根据有限群上的随机行走理论提出了一种非线性变换方法，并对引入了非线性变换的混沌密码系统进行了符号动力学分析，分析结果表明，引入了非线性变换的模型相对一般混沌编码模型而言，在符号动力学分析下具有较高的安全性。以二区间划分的模型为例，我们选用log**tic映射作为图1中的混沌映射f，并根据符号动力学分析中的gray码序数[20,21]定义二进制码序数，见2式。（2）
二值符号序列s的二进制码序数w(s)∈(0,1)。注意，这里的wr(xi)并不是单值的，因为同样的状态xi可能对应不同的置换bi。图2 在2区间划分下产生的二值符号序列的wr(xi)分析
图2中的wr(xi)为参数r控制下从当前状态xi出发产生的二值符号序列的二进制码序数。图2（a）是未进行非线性变换时的情形，可以看出，其它三种进行非线性变换时的情形都较图2（a）中的分形结构更为复杂。由此可见，引入了非线性变换的混沌模型相对一般混沌编码模型而言，在符号动力学分析下具有较高的安全性。5.混沌流密码系统的理论分析和数值分析结果
5.1 理论分析结果
密钥流的性质直接关系到整个流密码系统的安全性，是一个极为重要的指标。我们对密钥流的均匀、独立分布性质和密钥流的周期性质给出了证明，其结果如下：
（1）密钥留在0,1,…,255上均匀分布。（2）密钥流各元素之间相互独立。（3）密钥流出现周期的概率趋向于零。（4）有关密钥流性质的证明过程并不涉及改变非线性变换的具体操作，也不涉及具体的驱动序列产生算法，仅仅要求驱动序列服从独立、均匀分布，并且驱动序列和非线性变换之间满足一定的条件，这为该密码系统，特别是系统驱动部分的设计和改进留下余地。总之，该密码系统可扩展，可改进，性能良好且稳定。5.2 数值分析结果
目前，基本密码分析原理有：代替和线性逼近、分别征服攻击、统计分析等，为了阻止基于这些基本原理的密码分析，人们对密码流生成器提出了下列设计准则：周期准则、线性复杂度准则、统计准则、混淆准则、扩散准则和函数非线性准则。我们主要根据以上准则，对本密码系统的密钥流性质进行保密性分析，以证明其安全性。分析表明：混沌流密码系统符合所有的安全性设计准则，产生的密钥序列具有串分布均匀、随机统计特性良好、相邻密钥相关性小、周期长、线性复杂度高...