基于遗传算法的S?box设计方法研究

摘 要： S?box是分组密码中惟一的非线性部件，它的密码强度决定了整个分组密码的安全强度。提出了一种基于遗传算法的S?box设计方法，并对S?box的双射性、非线性度、严格雪崩准则、输出比特间独立性和差分均匀性进行了测试和分析。分析结果表明，利用该算法产生的S?box具有良好的密码学特性，适合用于开发新的分组密码算法。

关键词： S?box； 遗传算法； 密码学； 性能分析

中图分类号： TN918.4?34 文献标识码： A 文章编号： 1004?373X（2013）07?0101?04

0 引 言

随着计算机技术、网络技术的不断应用和发展，各种安全问题也越来越多地受到人们的重视。密码学作为信息安全领域的内容之一，已成为研究的热点问题。在分组密码系统中，S?box（Substitution box）是惟一非线性部件，因DES的使用广为流传。S?box为分组密码算法提供了所需的混淆作用[1]。S?box的构成可以分为两大类，直接用数学方法构造和采用人工智能的算法进行演化。AES、Camellia的S?box是基于有限域上的逆函数，还有一部分是基于m?序列[2]和正型置换，这样构造出来的S?box在差分均匀度，非线性度等性质都表现良好，但其代数结构简单，存在线性冗余等缺点，易受到代数攻击[3]。采用演化方法[4]构造的S?box，能够生成随机性和密码学性能良好的S?box，本文研究的重点就是利用演化算法中的遗传算法构造S?box。

1 遗传算法基本原理

遗传算法[[5]]（Genetic Algorithm）是一种模拟生物种群进化的优化方法，它的思想来源于自然界中的进化过程，其运算过程如下：

（1）确定染色体编码方案和适应值计算方法；

（2）随机生成一个初始群体；

（3）计算群体中每个个体的目标函数和其他相关函数，根据目标函数和适应值函数的关系计算出每个个体的适应值，并按大小进行排列；

（4）选取适应值较大的两个个体进行交叉和变异产生新的个体；

（5）满足一定迭代次数算法停止。

给出了遗传算法的流程图。

基本遗传算法的流程图

2 S?box设计方法

本文最初的个体（S?box）由两个混沌映射迭代产生，然后利用遗传算法优化个体，遗传算法中的所有控制参数由混沌映射迭代产生，具体方法如下：

第1步：公式（1）和公式（2）分别定义了混沌Logistic映射和Tent映射，用于生成遗传算法的控制参数。

[xn+1=λxn（1-xn）， λ∈（0，4）， xn∈0，1] （1）

[xn+1=xna， 0xn

式中：[xn][（n=0，1，2，…）]是两个混沌映射的状态值；[λ]和[a]是参数值，设[λ=4]，[a=0.5]。

给定初始值[x0]。Logistic映射迭代50次，去掉瞬间状态，用Logistic映射迭代值作为Tent映射的初始值，Tent映射迭代50次。

第2步：根据初始种群描述的方法，通过混沌映射迭代产生初始种群。

第3步：根据非线性度公式（见式（13））计算当前S?box的非线性度。S?box非线性度最小值作为个体的适应值。如果种群中最大适应值大于等于一个预定值F，或者种群数达到最大值，转到第8步。

第4步：当前个体按照适应值从小到大排列。如果两个个体有相同的适应值，那么非线性度的平均值按从小到大排列。

第5步：根据选择算子，选出下一代个体。

第6步：根据交叉算子，对新生个体进行重组。

第7步：根据变异算子，对新生个体进行变异。

第8步：产生适应值最大的个体，操作结束。

2.1 初始种群

两个混沌映射进行迭代产生初始种群。初始个体的产生描述如下：

第1步：Logistic映射迭代10次，Tent映射迭代10次。[x]表示当前Tent映射状态值。通过公式（3）得到整数值[X]：

[X=256×x] （3）

第2步：定义序列S，最初为空序列。添加[X]到[S]中。

第3步：如果[S]中数值不大于256，转到第1步。否则，输出的[S]作为初始种群的个体。

重复操作第1～3步，直到所有种群都被初始化。

2.2 选择算子

选择数量由式（4）计算产生。

[NE=p1×C] （4）

式中：[NE]是选择数量；[C]是种群大小；[p1]是选择概率。由于个体是按适应值排序的，很容易找到适应值大的个体选择数量。被选择的个体直接成为下一代。

2.3 交叉算子

交叉算子可以避免局部极小值，并从父染色体里获得基因片段。交叉过程描述如下：

第1步：通过公式（5）计算交叉所产生的个体总数。

[NC=p2×C] （5）

式中[p2]为交叉概率。

第2步：通过公式（1）Logistic映射迭代10次，通过公式（6）产生整数[l]：

[l=8×x] （6）

式中[x]是Logistic映射当前状态值。

第3步：通过公式（2）Tent映射迭代10次，通过式（7）和式（8）分别产生整数[m]和[i]：

[m=8×x] （7）

[i=C×x] （8）

第4步：选择适应值最大的个体作为[父1]，当前种群中第[i]个个体作为[父2]。然后，两个交叉子代产生于Exchg函数[（父1，l，父2，m）]。添加到交叉种群。

第5步：如果交叉算子产生的当前个体数量不大于[NC]，重复该操作的第2～4步，直到所有选择产生交叉子代。

2.4 变异算子

变异算子只发生在交叉个体，步骤如下：

第1步：定义[NM]为需要变异的个体数量。[NM=p3×C] （9）

式中[p3]为变异概率。

第2步：公式（1）中Logistic映射迭代10次。

第3步：公式（2）中Tent映射迭代10次。

第4步：根据公式（10）生成整数[I]：

[I=NM×x] （10）

式中[x]为Tent映射当前状态值。交叉种群中第[I]个个体被选择执行变异操作。

第5步：重复第2步操作，通过公式（11）得到整数[P1]：

[P1=NM×x] （11）

第6步：重复第3步操作，通过公式（12）得到整数[P2]：

[P2=NM×x] （12）

第7步：交换第[（P1+j）]项和第[（P2+j）]项个体，其中，[j=0，1，???，9]。生成了一个变异个体。

第8步：如果变异个体数量不大于[NM]，回到第2步，否则，停止变异算子。

3 S?box性能分析

设[x0=0.1]，[p1=0.2]，[p2=0.5]，[p3=0.3]，[C=5 000]，[F=100]。通过2.1节的方法首先得到5 000个初始个体。初始个体用来生成下一代个体。2.2～2.4节分别描述了选择，交叉，变异生成下一代个体的过程。通过式（1）和式（2）中两种混沌映射的迭代生成控制参数，用于产生下一代个体。第500代种群形成的S?box如图2所示。

文献[6?8]给出了具有代表性的混沌S?box构造方法，用于和本文S?box进行性能比较。文献[9]给出了S?box演化算法，也用于和本文S?box进行性能比较。

3.1 双射性

文献[6]提出了双射性检验方法。当[m=n]时，S?box满足双射的充分必要条件为：各分量布尔函数[fi]的线性运算之和为[2n-1]，[ωti=1naifi=2n-1，][ai∈0，1，（a1，a2，…，an）≠][（0，0，…，0）；][ωt]为汉明重量。[fi]满足[01]平衡，说明S?box满足双射性。本文S?box满足双射性要求。

3.2 非线性度

用Walsh谱表示的非线性度为：

[Nf=2n-11-2-nmaxSfω] （13）

在线性密码分析中，关键一步是构造单轮有效线性逼近，单轮线性逼近和S?box的线性逼近有关，S?box的非线性度越大越好。表1给出了本文S?box和文献[6?9]中S?box的非线性度值，本文S?box非线性度值为107.2，好于其他方法构造的S?box。

非线性度值比较

[S?box＼&非线性度值＼&平均值＼&本文＼&108 108 106 108 106 106 106 108＼&107.2＼&文献[6]＼&104 106 104 108 98 100 100 106＼&103.3＼&文献[7]＼&103 109 104 105 105 106 104 103＼&104.9＼&文献[8]＼&107 103 100 102 96 108 104 108＼&103.5＼&文献[9]＼&105 102 109 106 102 105 105 108＼&105.3＼&]

3.3 严格雪崩准则

Webster和Tavares首次提出了严格雪崩准则[[10]]。文献[11]提出了一种有效的方法检验S?box是否满足严格雪崩准则。如果函数满足这一标准，说明一个输入比特的改变，将有一半的输出结果发生变化。一般情况下，S?box的严格雪崩性是通过矩阵计算测试出来的。如果每个元素值和矩阵平均值都接近0.5，说明S?box满足严格雪崩准则。图3给出了本文S?box的相关矩阵，平均值为0.505 9，接近理想值0.5。

3.4 输出比特间独立性

Webster和Tavares首次提出了这个标准。这是安全密码系统另一个基本属性。对由一个明文比特的反码所产生的雪崩向量集而言，所有雪崩变量应该是成对独立的。通过计算两个雪崩向量的相关系数可以测量其独立程度。

Adams C.和Tavares S.给出了另一种测量输出比特独立的方法[12]：对于给定的布尔函数[fi]，[fk（j≠k）]是S盒的两个输出比特，如果[fifk]高度非线性且尽可能的满足严格雪崩效应，则它们可以确保当一个输入比特取反时，每个输出比特对的相关系数接近0。可以通过验证S盒的任意两个输出比特间[fifk]是否满足严格雪崩准则来证明S盒是否满足输出比特间独立性准则。

给出了计算结果，本文S?box输出比特间独立性―非线性度最小值为100，平均值大于100。输出比特间独立性―严格雪崩准则平均值为0.502 1，接近理想值0.5。本文S?box满足该准则。

[-104102106102-106104102106-106104102106-100104106104104102104102100102106100102102104104106104100102104102102102106106100104104102100104-104100104104-102100100102-106104100108-]

输出比特间独立性―非线性度计算结果

[-0.531 30.476 60.531 30.498 0-0.501 90.498 00.476 60.501 9-0.502 00.515 60.478 50.502 0-0.501 90.484 40.478 50.498 00.529 30.531 30.517 60.507 80.498 00.476 60.470 70.515 60.498 00.515 60.470 70.501 90.503 90.529 30.498 00.498 00.498 00.531 30.476 60.515 60.478 50.515 60.470 70.529 30.498 00.501 90.515 60.501 9-0.531 30.529 30.501 90.531 3-0.484 40.478 50.529 30.484 4-0.501 90.501 90.478 50.501 9-]

输出比特间独立性―严格雪崩准则计算结果

3.5 差分均匀性

差分均匀性是针对差分密码分析而引入的，用来度量一个密码函数抗击差分密码分析的能力。S盒的差分均匀性越小越好。

用差分逼近概率[[13]]表示输入输出的异或分别情况：[DPf=maxΔx≠0，Δy#x∈X|f（x）f（xΔx）=Δy2n] （14）

式中：[x]为所有可能输入的集合；[2n]是集合的元素个数；[DPf]表示给定一个输入差分[Δx]，输出为[Δy]的最大可能性。

给出了计算结果，最大值为10，本文S?box差分逼近概率为3.906%，说明本文S?box具有良好的抵抗差分攻击能力。

S?box差分分布

4 结 语

本文提出了分组密码算法中一种新的S?box设计方法，此方法首先通过混沌映射迭代生成初始的S?box，在初始S?box的基础上通过遗传算法，得到性能更好的S?box。遗传算法进化过程中的控制参数由混沌映射迭代产生。本算法产生的S?box不仅具有混沌映射的随机分布特性，还具有遗传算法的优化特性。通过测试可以看出，本文S?box具有良好的密码学特性，适合开发新的分组密码算法。

参考文献

[1] CHEN Hua， FENG Deng?guo. An effective evolutionary strategy for bijective s?boxes [C]// 2004 IEEE Congress on Evolutionary Computation. Oregon： IEEE， 2004， 2： 2120?2123.

[2] 刘晓晨，冯登国.满足若干密码学性质的S盒的构造[J].软件学报，2000（10）：15?17.

[3] FREDERIK A， MATTHIAC K. Algebraic attacks on combiners with memory [C]// 23rd Annual International Cryptology Conference. Santa Barbara， California， USA： 2003： 162?175.

[4] 张焕国，冯秀涛，覃中平，等.演化密码与DES的演化研究[J].计算机学报，2003（12）：23?25.

[5] 玄光南，程润伟.遗传算法与工程设计[M].北京：科学出版社，2000.

[6] JAKIMOSKI G， KOCAREV L. Chaos and cryptography： block encryption ciphers based on chaotic maps [J]. IEEE Transactions on Circuits and Systems?I， 2001， 48（2）： 163?169.

[7] TANG G， LIAO X， CHEN Y. A method for designing dynamical S?boxes based on discretized chaotic map [J]. Chaos Solitons Fractals 2005， 23： 413?416.

[8] ASIM M， JEOTI V. Efficient and simple method for designing chaotic S?boxes [J]. Etri J.， 2008， 30（1）： 170?176.

[9] BHATTACHARYA D， BANSAL N， BANERJEE A， et al. A near optimal S?box design [J]. Lecture Notes in Computer Science， 2012， 4812： 7?90.

[10] WEBSTER A F， TAVARES S. On the design of S?boxes [J]. Lecture Notes in Computer Science， 1986， 218： 523?534.

[11] PIEPRZYK J， FINKELSTEN G. Towards effective nonlinear cryptosystem design [J]. IEEE Proc. Part E： Computers and Digital Techniques. 1988， 135（6）： 325?335.

[12] ADAMS C， TAVARES S. The structured design of cryptographically good S?boxes [J]. Journal of Cryptology， 1990， 3（1）： 27?41.

[13] HALE J K，VERDYN LUNEL S M. Introduction to functional differential equations [M]. New York： Springer? verlag， 1993.