探索计算机迭代下混沌序列的周期研究
摘要：
研究了计算机迭代下基于浮点格式的混沌序列周期及其分布规律。通过构造与标准浮点格式匹配的非标准浮点格式，统计测算了六种常见混沌系统在不同浮点精度下退化的混沌序列周期及其分布，采用线性拟合方法获得了混沌序列周期随计算精度变化的分布关系，纠正了多年来基于定点格式的相应分布关系，为后续的混沌抗退化机制研究提供了一个合理的可用于实验测试的参考标准，也表明对于混沌序列而言，基于定点格式的结论不能简单随意推广到浮点格式。
关键词：混沌；浮点；有限精度效应；周期
0 引言
计算机或其他数字系统计算混沌系统时，有限的精度所带来的截断误差必定会使混沌序列退化为周期序列 ，即所谓有限精度效应。密码学界普遍怀疑混沌密码算法存在因混沌退化而引起的安全性隐患 ，短周期意味着弱密钥 。
人们为改善有限精度效应的负面作用相继提出了利用多个混沌系统迭代、迭代过程中加入扰动等方法 ，但这些方法都是以牺牲系统运行速度或增加系统资源为代价的，即使如此，仍然不能从理论上证明混沌密码算法不存在由于混沌退化引起的安全性隐患。一种新的解决方案是，如果能够找到一种安全混沌 J，它具有一定强度的抗退化能力，在可及的空间和可及的时闻内不会因为混沌退化而出现周期轨道，根据密码分析学原理，由这样的混沌系统构造的密码算法对于混沌退化而言是安全的。混沌抗退化机制研究可能是解决混沌密码算法因混沌退化而引起的安全性问题的有效理论途径。本文研究基于浮点格式的混沌序列周期及其分布规律，作为混沌抗退化机制的重要内容之一，为混沌抗退化机制研究寻找一个合理的可用于实验测试的参考标准。在理论预期下，一个具有抗退化能力的混沌系统的平均序列周期必定远大于纯退化混沌系统的平均序列周期。
Cernak_6 测得一维混沌序列的周期分布范围[0，2 ]，其中P为比特位表示的计算精度，s=0．68±0．05；Beck等人” 观察到类似结果，一维混沌序列的平均周期正比于于定点格式的，虽然沿用至今 J，却只有定性意义，实际意义有限，特别是要作为混沌抗退化机制研究的定量评估标准，理论依据不充分。因为定点数定义在部分实数域上，当计算对象中存在一个或多个变量(包括中间变量)超出了定点数的定义域时，定点格式计算失效。另外，在给定精度下，定点格式的最小单元是常数，浮点格式的最小单元是数的指数函数，必然要影响计算对象，两者功能上存在显著差别 。作为混沌系统抗退化能力的检验标准，需要在浮点格式下重新研究数字混沌序列周期及其分布规律。本文统计测算研究了6种定义于[0，1)上的离散混沌系统，较之Cernak等人的研究，结果表明，就混沌序列而言，定点格式的结论不能简单随意推广到浮点格式。
1 混沌序列周期搜索算法
设混沌系统迭代方程为：
任意给定初始值 。，经一段瞬态演化后混沌系统将进入周期为 的循环状态，如图1所示，％至 一。称为过渡态。搜索算法的目标是找出周期 的值。
对应图1，一种快速搜索算法如图2所示，步骤如下：
① 给定初始值‰ 和一个步进n(n为常数)；② 按照式(1)，初始值迭代一个步进后得到 ，设置对应的迭代次数n为搜索范围上限；③ 从第n+1次迭代开始，比较 = 是否成立，其中= l，2，3，n；④ 若对于某一个i，X = 成立，则T=i，退出搜索；⑤ 若对所有的i=1，2，3， n， = 均不成立，则初始值改为 ，重复② 。
2 非标准浮点数构造与实现
2．1 构造方法
新颁布的IEEE Std 754—2008标准定义了四种浮点数格式 ，由符号域s、指数域E和尾数域 三部分组成，如表1所示。以4种标准浮点数的(E，M)为参考点，采用最小二乘法得一拟合二次曲线：
M = 0．8150E 一6．0754E +19．8588 (2)均方误差为0．2873，如图3所示。在图3横坐标E上的[5，8]和[8，11]两区间内插入6、7和9、10四个整数，对应纵坐标为13、l7和31、41，加上符号域5所占的l位，得到20、25、41、52位共四种非标准浮点数格式，如表2所示。限于计算时间，不考虑64至128位之间的非标准浮点数。
2．2 实现
为了在VC+上实现非标准浮点数下的周期搜索算法，用float型浮点数表示16、20、25位浮点数，用double型浮点数表示4l、52位浮点数。表示方法如下。
分别用s。、E 和 表示20位的非标准浮点数a的符号域、指数域和尾数域，分别用S 、E 和 表示float型浮点数b的符号域、指数域和尾数域。符号域两者均为1位，故将5直接赋值给s 。指数域中，E 的取值范围为[一3l，32]，的取值范围为[一127，128]，用 表示E 相当于完全忽略掉[一t27，一32]和[33，128]的数，有2 +2。=96个整数。故对于[一31，0]内的数(E。最高位为“0”)，将 第5、6位固定为1’，E 的最高位赋值给E 的最高位，E。的低5位赋值给 的低5位；对于[1，32]范围内的数(E。最高位为“1”)，将 第5、6位固定为0’，E。的最高位赋值给 的最高位，E。的低5位赋值给E 的低5位。尾数域中， 比 少10位，将M 赋值给M 的高13位，M 的低10位全部置零。赋值过程如图4所示(当e为’时， 为“1”；当e为“1”时，为“0”)。
2．3 实现方法合理性验证
2．2节实现方法的合理性需要用混沌序列周期测算实验验证。验证方法如下：系统参数取某一固定值，分别用float型、double型以及double型表示float型这三种浮点数测算同一混沌序列的周期。设 、 和 依次表示给定系统参数下这三种浮点数测算的关于不同迭代初始值的平均周期， 、和 依次表示对应 、 和 的关于不同系统参数的平均周期，若 与 有相似的分布，且 ，Tb》一To，一Tb》则用float型、double型实现非标浮点数对于测算混沌序列的周期而言就是合理的。
选用Logistic映射系统在[3．7，4)上以间隔0．025均匀取值，初始值 。在(0，1)上以间隔0．001均匀取值，测得 、 和 的分布如图5所示，相关系数R=0．697 1， = 1 724， =由此可见，此非标准浮点数的实现方法是合理的。
3 混沌序列周期测算及分析
3．1 测算对象与方法采用第1章所述的混沌序列周期搜索算法，按照第2章所述的标准和非标准浮点格式及其实现方法，分别测算6种式(8)中无系统参数。
测算方法如下：对于一固定系统参数值，迭代初始值在(O，I)区间上以间隔0．OOI(二维Cat混沌系统以间隔0．01)均匀取值，得到999(二维Cat混沌系统为99 )个周期值，统计出最小值、最大值和平均值。测算程序用VC++6．0编写。
3．2 测算结果及分析图6给出了Logistic映射在不同计算精度P的非标准与标准浮点格式测算下的混沌序列周期分布规律，针对每一种计算精度，分别测算了最长周期 一最短周期 。 以及平均周期 。由此可见，混沌序列的平均周期 和最长周期 与计算精度服从关系：
其中k与b为最小二乘法给出线性拟合系数。其他5种混沌序列也具有相同的分布规律，各混沌序列的拟合系数由表3给出。
由图6及表3给出的多种混沌系统的测算数据，再考虑到测算样本的有限性，若用D表示混沌系统的维度，则可归纳出在浮点格式下混沌序列周期的分布规律：
分布区间远小于定点格式下的[0，2 ]。
同理，平均周期服从：
因此，对于一维混沌系统，double型浮点格式下的混沌序列平均周期约为64 bit定点格式下的1／30000。可见，用计算机研究混沌系统时，采用定点格式或浮点格式，所得结论不能轻易互相引用。
式(1O)和式(11)给出了浮点格式下混沌序列周期的分布规律，为评估混沌系统的抗退化强度提供了一个参考标准。
若混沌系统存在很强的抗退化能力，其序列周期的分布将出现异常而远远超出式(10)的范围。
4 结语
本文提出了一种混沌序列周期快速搜索算法和一种与标准浮点格式匹配的非标准浮点格式构造与实现方法，以此为基础，分别测算了计算机迭代下基于浮点格式的6种混沌序列的周期分布及其平均周期。结果表明：混沌序列的平均周期和最大周期随计算精度呈指数增长；在浮点格式下的混沌序列平均周期远小于定点格式下的平均周期；对于混沌系统计算花销主要是指所需的指数运算数、对运算数等。本协议与协议ID．T、ID-．CMM ，CPK．DDL 的比较结果如表1所示。
从表1中易知：协议ID一1Tr通信轮数与通信方数n有关，而剩下四个协议是常数轮的，但协议ID—BD不能抵抗共谋攻击 。本协议能高效支持成员加入／离开操作，但协议ID—CMM、CPK．·DDL不支持此操作并且协议ID—CMM需要双线性对运算。此外协议ID．CMM和CPK．DDL均不能抵抗临时密钥泄露攻击，但本协议提供了强安全性保证。综合各方面的考虑，本协议在安全性和效率方面都具有优势。此外，本协议还提供组群密钥交换协议的完全健壮性。协议执行过程中丢失的用户只会使其他用户接收不到该用户选择的部分密钥k ，但剩余用户仍可以正确计算剩余用户之间共享的组群会话密钥k=H。(ki．++k )，其中 一， ，为剩余用户。
丢失用户可以通过加入组群操作继续参与组群安全通信。
6 结语
基于高效CPK体制，本文提出了一个两轮的强安全组群密钥交换协议。本协议提供显式密钥认证和完全的健壮性，高效支持多成员动态加入或者离开，并且成员加入或者离开操作能确保前向保密性和后向保密性。它能一直保持会话密钥的秘密性，除非某一方的会话临时私钥和长期私钥同时泄露。它也能抵抗密钥泄露伪装攻击和临时密钥泄露攻击，提供完美的前向安全性。此外，本协议相当于提供了一个设计常数轮强安全组群密钥交换协议的方法，且大部分的秘密共享体制均可直接应用于本协议。
人次