本站原创【摘 要】计算线性等价是研究非线性密钥序列生成器线性复杂度的有效方法.本文先介绍了计算线性等价的模拟退火法,然后使用遗传算法对该算法进行改进,最后使用一组密钥序列生成器对改进后的算法进行性能评估,并将改进后的算法和原算法进行了比较.结果表明改进后的算法能比原算法更有效的找到非线性密钥序列生成器的线性等价.
【关 键 词】线性等价；模拟退火；遗传算法；序列
【中图分类号】TP309【文献标识码】A
1引言
在序列理论中线性复杂度是非常重要的安全性尺度,许多学者在这方面都做了研究.Garcia和Fuster-Sabater2000致力于分析非线密钥序列生成器的线性复杂度；Wasan等学者指出,寻找线性等价是一种确定非线性密钥序列生成器线性复杂度的有效方法,并提出了基于模拟退火法（SimulatedAnnealing,简写为SA）计算线性等价的方法.
模拟退火法具有较强的局部搜索能力,然而全局搜索能力偏弱.遗传算法（GeicAlgorithm,简写为GA）的全局搜索能力较强.模拟退火—遗传算法已经被广泛的应用在各个领域,取得了令人满意的结果.因此,我们基于Wasan等学者的方法,使用遗传算法对其进行改进,提高了算法的效率.这篇论文包含了对算法的描述,对算法效率和性能的研究,另外还有改进后算法和原算法的对比.
2计算线性等价遗传算法描述
为了更好地阐述非线性密钥序列生成器线性等价问题,首先对其进行遗传算法描述.遗传算法有五个关键步骤：确定候选解的表示方法；随机生成初始种群；评价每个个体（染色体）的适应度；从种群出选出一些个体作为父代,使用交叉和变异操作来产生子代；重复评价适应度并产生子代直到生成满意的结果.
2.1表示方法
在遗传算法中,用到了不同长度的染色体.使用二进制序列来代表染色体,每条染色体表示一个线性反馈移位寄存器（LinearFeedbackShiftRegister下记为LFSR）的反馈函数.这些染色体就是给出的密钥序列长度的候选线性等价,假设长度lengthkey为2L.最短染色体的长度是2bit,最长染色体的长度是2Lbit.
2.2适应度函数
适应度函数用来评估每条染色体ch.适应度函数通过等式①给出.
Fitness（ch）等于（lengthkey-d）+（lengthkey/3）×①
在（1）式中lengthkey-d用来判定生成密钥序列的准确性,lengthkey/3判定最短的LFSR是哪个从而得出最佳结果.1/（1+L（ch）是补充系数,其中L（ch）是染色体ch的长度.
2.3适应度计算算法
每条染色体的适应度ch通过下述算法得到.
Step1：L（ch）等于Length（ch）//令L（ch）成为将要被评估的染色体ch的长度
Step2：w等于LFSR（a0等aL-1）//令w为LFSR的初态,即最初的长度为L（ch）的密钥序列
Step3：g（ch）等于ch（w）//用ch和w生成二进制的序列g（ch）
Step4：d等于Hamming（key,g（ch））//计算密钥序列和g（ch）的汉明距离
Step5：Fitness（ch）等于（lengthkey-d）+（lengthkey/3）（1/（1+L（ch）））//通过等式（1）计算这条染色体的适应度
2.4遗传参数
采用1点交叉和5%概率变异的基因操作来更新种群.种群大小n依赖于已知的密钥序列的长度lengthkey.因此随着密钥序列长度lengthkey的增加,种群大小n应当同时增加.设种群大小计算公式为n等于lengthkey20.
父代个体通过基因的交叉和变异操作产生子代个体.
2.5停止条件
遗传算法的运行在繁殖一定代产生之后停止.问题的解为最后一代种群中适应度最高的染色体.问题的解应该有适应度lengthkey+L,该染色体代表了非线性密钥序列生成器的线性等价.
3计算非线性密钥序列生成器线性等价算法
影响遗传算法性能的关键因素就是淘汰策略,即是从当前的种群中如何选择最优的个体作为下一代种群的个体.这部分研究内容,我们提出了SA-GA1和SA-GA2两个算法来计算非线性密钥序列生成器的线性等价.遗传算法中的染色体表示方案、基因参数和适应度函数都应用到了SA-GA1、SA-GA2算法中.
SA-GA1算法先随机生成初始种群并计算种群整体适应度,然后通过交叉和变异操作该种群繁殖新一代种群同时计算新种群的整体适应度.如果新种群整体适应度较大就淘汰老种群；否则按照模拟退火法以一定概率淘汰老种群.直到降温到预定温度.图1是SA-GA1算法的流程图.
SA-GA2算法先随机生成初始种群并从中随机选择两条染色体（父代）计算适应度,然后通过交叉和变异操作父代繁殖子代同时计算子代的适应度.如果子代适应度较大就淘汰父代；否则按照模拟退火法以一定概率淘汰父代.直到降温到预定温度.图2是SA-GA2算法的流程图.
从算法的流程图中可以看到2个算法的不同：SA-GA1算法是以种群整体启发的,SA-GA2算法是以染色体个体启发的.
4仿真实验及结果分析
为了验证本文提出的改进算法的有效性,使用C语言编程实现了SA-GA1和SA-GA2算法,并进行了多次仿真实验.为了说明改进算法的有效性,本实验所使用的11组不同长度密钥序列的线性等价与参考文献[3]中的相同.模拟退火初始温度设置为300,停止温度为100,每繁殖一代降温为当前温度0.99.输入的密钥序列长度为2L,L的长度从3到13,通过LFSR的特征多项式来生成这些密钥序列,其中特征多项式如表1所示.实验结果成功的概率P如表2所示,P是通过对每个密钥序列执行算法多次,其中成功地找到了问题的解,即最后一代种群中的最好染色体是想要得到的LFSR的次数而计算得到的.
图3可以更直观地看出原始算法和改进后算法成功的概率.
通过表2和图3的对比可以看出模拟退火法和遗传算法的集成提高了算法的性能,改进算法SA-GA1和SA-GA2成功找到线性等价的概率大于原始算法.仿真实验表明,在计算非线性密钥序列生成器线性等价的问题中,模拟退火—遗传算法的性能明显优于模拟退火法.
5结束语
我们在Wasan原有算法的基础上,提出了计算非线密钥序列生成器线性等价的新方法.首先对其进行了遗传算法描述；然后结合模拟退火法和遗传算法,提出了两种改进算法,并详细阐述改进算法的步骤与两种改进算法的区别；最后通过仿真实验验证了改进算法的性能优于原始算法,是解决非线性密钥序列生成器线性复杂度问题的有效方法.
;J].InformationTechnonlgyJournal,2008,7（3）：541-544.[4]罗晨,李渊,刘勇等.基于模拟退火遗传算法的多agent系统任务分配[J].计算机应用研究,2012,29（6）：2114-2116.
[5]王庆荣,袁占亭,张秋余.基于改进遗传—模拟退火算法的公交排班优化研究[J].计算机应用研究,2012,29（7）：2461-2463.
[6]JunSong,FanYang,Maocai,Wang.CryptanalysisofTranspositionCipherUsingSimulatedAnnealingGeicAlgorithm[J].LectureNotesinComputerScience,2008,5370（1）：795-802.
[7]马永杰,云文霞.遗传算法研究进展[J].计算机应用研究,2012,29（4）：1201-1210.
作者简介：
张斌（1987-）,男,硕士研究生,主要研究方向：信息安全.
缪祥华,副教授,博士后.
唐鸣,硕士研究生.
赵之洛,硕士研究生.