上海大学 计算机工程与科学学院，上海 200444
出版日期:2020-06-28发布日期:2020-07-03通讯作者:牛志华（1976-），女，山西省晋中市人，副教授，主要研究方向为序列密码.电话（Tel.）：021-66135387；E-mail：zhniu@shu.edu.cn.基金资助:国家重点研发计划项目(2016YFB1000600，2016YFB1000601，2016YFB10006011)，国家自然科学基金重点项目(61936001)，上海市自然科学基金项目（16ZR1411200，17ZR1409800，19ZR1417700），科技部广东省部省联动项目（2018B010113001），国家自然科学基金项目（61572309）A Hybrid Genetic Algorithm for Computing the k-Error Linear Complexity of Periodic Sequences
NIU Zhihua,YUAN Can,KONG DeyuSchool of Computer Engineering and Science, Shanghai University, Shanghai 200444, China
Online:2020-06-28Published:2020-07-03摘要/Abstract
摘要： 周期序列的线性复杂度及其稳定性是序列密码评价的重要度量指标.k-错线性复杂度是线性复杂度稳定性的一个重要评价指标.然而，目前对于大部分周期序列(除周期为2n、pn、2pn外)，尚无有效的算法求解其k-错线性复杂度.因此，本文提出了一种混合的遗传算法来近似计算任意周期序列的k-错线性复杂度.采用轮盘赌、最优保留策略、两点交叉和单点随机变异，并引入自适应算子来调整交叉概率和变异概率，以保证遗传算法的收敛性.通过并行计算适应度函数来提高算法的效率，同时与模拟退火算法相结合，加速算法收敛并避免早熟.结果表明：当k<8且周期小于256时，k-错线性复杂度的实验值仅比精确值高8%.
关键词: 密码学, 周期序列, 线性复杂度, k-错线性复杂度, 遗传算法
Abstract: The linear complexity of periodic sequences and its stability are important metrics for the evaluation in stream cipher. The k-error linear complexity is an important evaluation index for the stability of linear complexity. However, at present, it is difficult to compute the k-error linear complexity of the period sequences (except for 2n、pn、2pn). Therefore, a hybrid genetic algorithm is proposed to approximate the k-error linear complexity of arbitrary periodic sequences by adopting the roulette wheel and elitist reserved strategy, the two-point crossover and simple random mutation, and by introducing adaptive operators to adjust the crossover and mutation probabilities to ensure the convergence of the genetic algorithm. The efficiency of the algorithm is improved by using the parallel computing fitness function. Simultaneously, by combining with the simulated annealing algorithm, it increases the convergence speed and avoids the premature convergence. The results show that the experiment value of k-error linear complexity is only 8% higher than the exact value when k<8 and the period is less than 256.
Key words: cryptography, periodic sequences, linear complexity, k-error linear complexity, genetic algorithm
PDF全文下载地址:
点我下载PDF
