基于扰动时空混沌系统的动态S盒设计

赵 耿，马英杰，陈 磊，董有恒，侯艳丽

（1.北京电子科技学院，北京 100070；2.北京邮电大学，北京 100876；3.西安电子科技大学，陕西西安 710071）

1 引言

现代分组密码中，置换和替换网络是不可或缺的，如AES（Advanced Encryption Standard）算法.其中S 盒作为分组密码中唯一的非线性部件，主要作用就是实现替换运算［1］，构造动态S 盒的方法有很多，利用混沌系统良好的伪随机性质来构造动态S盒已经成为构造S盒的一个重要方法［2］.唐国坪等提出一种基于Logistic映射的两步构造S 盒的方法，尽管这种设计方法很有效、实用，但还是存在着随机性和不可以测性不够强的缺点［3，4］.陈果等用三维的Baker映射设计了一种S盒克服了这些缺点［5］.王永［6］等和Ozkaynak［7］等分别提出了利用帐篷映射和连续时间的Lorenz 混沌系统来构造S盒.佟晓筠提出了一种新的超混沌系统，并将其用于生成置换和替代图像像素的密钥流，使用动态S盒设计加密算法［8］.闵乐泉设计了基于分段非线性鲁棒混沌映射的伪随机数发生器，提出了批量生成S 盒的算法［9］.Akram Belazi提出了一种基于正弦映射的S盒构造的有效方法［10］.Majid Khan 提出基于混沌布尔函数构造S盒，并将其用于图像加密［11］.这些构造方法为得到抵抗差分密码分析和线性密码分析能力好的S 盒提供了思路.朱虹宏等基于多混沌系统及复合思想，引入Arnold映射置乱算法构造了一种混沌S 盒［12］.Islam 等构造了四维四翼超混沌系统，并以此设计了一种混沌S 盒［13］.然而上述方法所涉及到的混沌映射均在相空间或者回归映射中存在固定结构的吸引子，极易受到相空间重构［14］或者回归映射分析［15］的攻击，而且当混沌系统在有限精度的计算机中运行时会出现退化显现［16］，出现周期现象，严重威胁到混沌密码系统的安全性.基于上述原因，Peizhao Zhou 等人提出了一种基于PWLCM（Piece Wise Linear Chaotic Map）-sin 映射的耦合映射格子的时空混沌系统［17］，并用其生成了S 盒，分析表明该系统生成的S 盒具有良好的非线性，然而，每个格子生成的序列在回归映射中依然具有明显的固定帐篷形状，依然易受到回归映射分析攻击.王永［18］等人为了解决时空混沌系统中存在的概率分布不均以及回归映射中形态结构固定的弱点，向基于分段Logistic 映射的二维耦合映像格子模型添加了偏移量，使得结果更加均匀，然而该文仅仅对该系统的性能进行了分析并未涉及到模型的应用.

为了改进上述缺点，本文提出基于初等元胞自动机（Elementary Cellular Automata，ECA）的新型扰动单向耦合映像网络时空混沌系统，并进行了分布图、分岔图和相图的数值仿真，结果表明扰动系统能够改善原系统的均匀性，提高系统的动力学复杂性.采用均匀化的扰动时空混沌系统设计了动态S盒生成算法，并进行了非线性度、严格雪崩准则和差分均匀性的统计分析，结果表明均匀化扰动时空混沌系统产生的动态S 盒具有更高的安全性.

2 基于初等元胞自动机扰动的时空混沌系统构造

2.1 单向耦合映像网络时空混沌系统及其数值仿真

单向耦合映像网络是一类时空混沌系统，具有易于产生、支持并行计算等优点，其定义为

式中n=0，1，2，…和i=1，2，3，…，L分别代表时间维度（迭代次数）和空间维度（格点索引），xn（i）表示在时刻n时，第i个格点的状态值，L表示格点的总数，ε（ε∈（0，1））代表耦合强度.该系统的边界条件可以表示为xn（i－1）=xn（L），底层映射ƒ为Logistic映射，即

当参数ε=0.625，u=4，L=100 时，式（1）所示单向耦合映像网络的分布图如图1（a）所示，当参数ε=0.875，u=4，L=100 时，单向耦合映像网络的分布图如图1（b）所示.从图1 可以看出，参数ε的取值能够影响单向耦合映像网络时空混沌系统的分布情况，该系统存在均匀性较差的缺点.

图1 单向耦合映像网络的分布图

当参数u=4，改变参数ε的取值，式（1）所示系统的相图如图2 所示.从图2 可以看出，参数ε的取值能够影响单向耦合映像网络时空混沌系统的相图，该系统存在动力学特性不够复杂的缺点.

图2 相图u=4（ε=0.125,ε=0.625,ε=875）

2.2 初等元胞自动机

元胞自动机是由数学家Stanislaw M Ulam和John von Neumann 于1948 年提出的［19，20］.初等元胞自动机是一种特殊的一维元胞自动机.初等元胞自动机的构成如图3所示.

图3 初等元胞自动机

图3 中元胞Cn−1和Cn+1是元胞Cn的邻居，其中C1和CL互为邻居.在ECA中，每次迭代的当前元胞状态值由当前元胞和其邻居的前次状态值决定，如式（3）所示

其中代表了元胞Ci在t时刻的状态值，t代表时间维度，即迭代次数，i代表空间维度，即元胞编号.此处f为布尔函数并由局部转换规则决定，其本质上是一个由集合｛000，001，010，011，…，111｝到集合｛0，1｝的映射.显然对于初等元胞自动机，共有256 个转换规则.其中以第105号转换规则为例，其转换表如表1所示.

表1 第105号ECA转换规则

根据W Li 等人的研究［21］，具有不同转换规则的ECA，其在迭代过程中所表现出的动态特性也互不相同.任意一个具有全局混沌规则的ECA 均能够用来构建本文所提出的时空混沌系统.这些全局混沌规则已在表2 中给出.其中具有110 号转换规则的ECA，我们简称为110号ECA，以此类推.

表2 全局混沌规则

为了进一步说明具有这些混沌规则的ECA 在迭代过程中所表现的伪随机性.我们在图4中展示了60号，105号以及150号的迭代结果.

图4 全局混沌的ECA迭代结果

图4 中黑色（白色）的方格代表本方格上的元胞其状态值为“1”（“0”），纵坐标代表迭代次数，由上至下递增，横坐标代表元胞索引.显然，三种ECA 均显示出伪随机性.本文选择105号ECA用来构造时空混沌系统.

2.3 基于初等元胞自动机扰动的时空混沌系统构造及其数值仿真

针对式（1）所示传统单向耦合映像网络时空混沌系统存在均匀性较差以及动力学特性不够复杂的问题，本文基于初等元胞自动机构造了新型扰动单向耦合映像网络时空混沌系统，即

式中，Sn为初等元胞自动机的迭代结果，为初等元胞自动机第i个元胞的迭代结果，其中p(Sn)=

当参数ε=0.625，u=4，L=100 时，式（4）所示扰动时空混沌系统的分布图如图5（a）所示，当参数ε=0.875，u=4，L=100 时，扰动时空混沌系统的分布图如图5（b）所示.

从图1、图5的对比可以看出，提出的基于初等元胞自动机构造的新型扰动单向耦合映像网络时空混沌系统均匀性明显优于传统时空混沌系统.

图5 扰动时空混沌系统的分布图

当参数u=4，改变参数ε的取值，式（4）所示系统的相图如图6所示.

图6 相图u=4（ε=0.125,ε=0.625,ε=0.875）

从图2、图6的对比可以看出，提出的基于初等元胞自动机构造的新型扰动单向耦合映像网络时空混沌系统的动力学复杂性明显优于传统时空混沌系统.

3 基于扰动时空混沌系统的动态S盒设计

3.1 扰动时空混沌系统产生序列

处理函数：Mseq=chaosGenFun（K，n0，n）

输入：密钥K，输出长度n0，n.

描述：①密钥K由8 个长度相等的子密钥构成，可表示为（K（0），K（1），K（2），…，K（7））.②n0为要舍去的混沌系统初始迭代次数，n是后续的迭代次数.

输出：扰动时空混沌序列Mseq.

描述：Mseq是一个矩阵，大小为n×8，生成的混沌序列中的元素以64位双精度浮点数型进行储存.

3.2 生成密钥流

处理函数：［KS］=ksGenFun（Mseq，nks）

输入：Mseq，输出长度nks.

描述：nks为后续步骤中所需密钥流的总长度.

输出：密钥流KS.

描述：KS是一个长度为nks的向量.

3.3 生成动态S盒

处理函数：［S1，S2］=SboxGenFun（KS）输入：KS.

描述：KS由上一个处理函数产生，要求其长度8n≥512+nks.

输出：S盒S1，S2.

描述：双S 盒S1，S2均是大小为16×16 的替换表，且满足双射条件.S 盒和密钥流是由所生成KS的不同部分构成.

（1）初始化S盒S1和S2.按顺序赋值为0～255：

（2）构造两个16×16 的随机矩阵R1，R2.分别取KS的256 个元素，RV1=KS（nks，nks+255），RV2=KS（nks+256，nks+511），然后逐行将RV1和RV2 分别转换为两个随机矩阵R1，R2，大小为16×16.

（3）利用R1，R2，对S盒S1和S2进行随机化处理.对S1，S2的元素进行如下操作：

其中，i，j=0，2，3，…，15代表S1中元素的索引，分别表示行和列.函数(x)MSB和(x)LSB分别代表取x的最高四位和最低四位.的作用就是根据R1（i，j）的值，得到与S1中位置（i，j）上的元素进行交换的元素索引（k，l），并将两元素进行交换.按顺序将S1中的所有元素即位置（1，1）至（16，16）按照式（6）进行交换乱序后得到随机化后的S1盒.具体过程如图7 所示.同理，利用随机矩阵R2对S2盒进行上述乱序操作.

图7 构造S盒S1的示意图

4 动态S盒的安全性分析

4.1 非线性度

本文S 盒的非线性度如表3 所示，其平均值为105.75，略优于文献［4，11，12］的非线性度，说明该S 盒抵抗线性分析的能力更强.

表3 S盒非线性度对比

4.2 严格雪崩准则

严格雪崩准则是指若某个输入比特发生改变，那么对应的输出比特发生改变的概率为1/2.通过计算，该S盒的数据如表4所示.

表4 S盒严格雪崩准则对比

表4 中列出了平均值与理论值0.5 的差距.根据表4可以得出，由本文算法得出的S盒仅与理论值0.5相差0.002 5，优于文献［11］和文献［12］，仅次于文献［4］提出的算法，可见该S盒能较好满足严格雪崩准则.

4.3 差分均匀性

通过计算可以得出本文S 盒的差分均匀度与其他文献的S 盒的差分均匀度的对比如表5 所示，根据表5可以看出本文S 盒的差分均匀度为10 与文献［12］的相同，同样优于另外两个文献的数据.由此说明本文S 盒针对差分线性分析的抵抗能力较强.

表5 S盒差分均匀性对比

4 总结

本文基于初等元胞自动机构造了新型扰动单向耦合映像网络时空混沌系统，并进行了分布图、分岔图和相图的数值仿真，结果表明扰动系统能够改善原系统的均匀性，提高系统的动力学复杂性.采用均匀化的扰动时空混沌系统设计了动态S盒生成算法，并进行了非线性度、严格雪崩准则和差分均匀性的统计分析，结果表明均匀化扰动时空混沌系统产生的动态S 盒具有更高的安全性.故本文方案可产生大量性能优秀的S 盒，在分组密码设计等方面拥有良好的应用前景.