基于遗传算法构建s盒的探析

《基于遗传算法构建s盒的探析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于遗传算法构建S盒的探析摘要：S盒是作为分组密码的重要组件，对密码的安全性起着关键作用。而遗传算法作为一种启发式的全局优化搜索算法，可以很好地用于S盒的构建。本文就此进行了技术细节探讨，并对相关难点做了分析与总结。关键词：S盒；遗传算法；非线性度；差分均匀度；雪崩度中图分类号：TP18；TN918.1S盒是多数分组的密码中的唯一非线性组件[1]，其所起的混淆作用是分组密码必不可缺的，影响着整个密码结构的强度。目前分组密码中8×8的S盒较为普遍，传统的随机生成、数学构造等方法构建的S盒不有稳定的密码学性质，难以达到非线性度、差分均匀度等密码分析的要求。本文利用遗传算法

2、的全局优化搜索特性，快速构建S盒。1遗传算法原理遗传算法（GeneticAlgorithm）一种基于遗传学原理模拟自然界生物种群进化规律而产生的优化搜索模型，其最初由J.Holland教授于1975年提出，因诸多良好特性而广泛应用[2]。6遗传算法本质上是一种种群基因迭代并优胜劣汰的过程。算法从一个随机初始种群出发，经过竞争、选择、交叉、变异，形成新的种群，如此重复迭代，直到产生符合约束条件的个体。图1展示的是遗传算法的一般流程结构：图1遗传算法流程由此可见，将遗传算法应用于S盒有着两大关键点：一是基因如何编码；二是适应度如何评估。2S盒的设计原则任意一个n×m的S盒

3、可以看做是映射S（x）=（f1（x），f2（x），…，fm（x））：F2n→F2m。在实际使用中分组密码多采用8×8的双射S盒，由于8的阶乘种可能性，给S盒构建带来了极大的困难。目前，S盒的安全性主要通过以下指标来度量：非均匀度、雪崩度和差分均匀度等。这在一定程度上对应着前述三种设计原则。2.1非线性度非线性度作为S盒的设计原则之一，反映了S盒输入与输出的非线性关系，它的强度决定了基于S盒的密码学算法抵抗线性密码分析的能力。设Ns表示非线度，Ln表示全体线性函数的集合，dH（f，l）表示f和l的汉明距离，则Ns可以用以下公式来表示：2.2雪崩度表示S盒的雪崩度，其公式

4、如下：6雪崩度主要是描述输入比特的变化对每个输出比特变化的影响程度。2.3差分均匀度δ表示S盒的差分均匀度，其公式如下：差分攻击是分组密码的有效攻击方式之一，具有较小的δ是S盒抗击差分攻击的必要条件。3基于遗传算法的S盒构造3.1S盒的编码用遗传算法构建S盒，一般多用于构造双射S盒，首先要确定编码格式。一种常用的有效编码方法是直接使用相应的十进制整数编码，这种方式带来的好处是方面遗传算法的迭代、交叉等遗传操作，但在计算适应值时需要进行一定的转换。另一种方式是直接采用二进制编码的方式，在计算适应值时带来了方面，但迭代、交叉等遗传操作时的去重则显得有些复杂。3.2产生初始

5、种群遗传算法S盒的初始种群多采用随机生成的方法，为了避免多余的计算量，有时会预置一批随机S盒存储在文件中使用，以减少算法的运行时间。3.3适应值函数6自然界中，个体适应值即是它繁殖的能力，它将直接关系到其后代的数量。根据前文介绍的S盒设计原则，我们期望能生成一批同时满足非线性度、差分均匀度和雪崩度的S盒。但很难找到同时达到最优的情况。因此，在计算适应值时，一种有效的方法是采用以下公式：f（s）=asfs（Ns）+adfd（δ）+abfb（Bs）其中，fs、fd、fb分别是非线性度、差分均匀度和雪崩度的函数，asadab为相应的系数。各个系数根据实际需要进行选择，以保证

6、筛选出最合实际使用的S盒。3.4选择方法算法中个体选择方法采用局部竞争机制选择：μ+λ选择，即从λ个后代与μ个父体中选取μ个最优个体。这种方式可以保证最优个体能一直保留下去[3]。3.5交叉与变异交叉操作的方式是设定一个交叉算子，当为当代种群中所有个体分配杂交概率，如果概率小于交叉算子，则将选中的个体进行杂交操作。变异操作采用基本位变异的思想，是模拟基因突变的遗传操作，它对种群中的每个个体，以变异概率改变某一些基因座上的基因值为其他的等位基因。4算法实现的关键点4.1适应值的调节6针对分组密码的攻击方式和分析手段多种多样，不同的攻击策略带来的攻击成本也不尽相同。因此，

7、适应值的调节将决定着S盒密码的安全强度。而且遗传算法运行到一定代数适应值会变得比较接近，这是如何进行选择和调节，将影响算法的收敛性。一种可行的方法是采用线性放大放大适应值，使概率选择变为多层次。4.2参数的选择种群规模：初始种群规模影响算法的进行，规模太小有可能造成过早的局部收敛，规模太大将制约着算法的运行效率。变异和交叉算子：两者直接决定了交叉和变异的概率，交叉概率过小将增加算法的遗传代数，变异概率则影响这种群的多样性，过大的变异概率会导致种群同位基因难以恢复，太小则种群多样性起不到明显效果。5结束语本文介绍遗传算法在构建S盒方面的应用，分析了生成