[CJE 编辑推荐] 基于改进遗传算法的ARX密码差分分析

中国科学院信息工程研究所王明生研究员和李永强副研究员带领的团队开yunapp体育官网入口下载手机版，在遗传算法应用于差分分析领域获得新突破，相关研究成果以《基于改进遗传算法的ARX密码差分分析》为名，发表于《电子学报》2023年第2期。

文章简介

差分分析属于密码分析的核心技术，占据重要地位。现阶段，应用广泛的分析手段包括Matsui方法、混合整数线性规划、SAT以及约束规划。这些技术依托数学原理，并沿用传统搜索模式，难以充分借助既有搜索数据来优化分析流程。当处理的问题规模持续扩大时，这些方法暴露出效率不高、耗时较长的弊端。遗传算法属于一类启发式搜索技术，它借助对自然演化过程的模仿来探寻整体最优的解决方案，这种算法在搜寻时无需依赖数学运算，并且可以自动地修正和改进搜索路径，因此，近些年来遗传算法在密码的编制和破解工作中获得了越来越广泛的应用。但是，当前密码分析领域中的多数研究主要借助遗传算法来恢复密钥，却鲜有研究将遗传算法应用于密码分析中最为关键的一环——寻找差分特征。这项研究首次尝试运用遗传算法进行差分特征搜寻。

在运用遗传算法寻找差异特征时存在一个障碍，即不能直接把差异特征当作遗传算法的载体开元ky888棋牌官网版，因此这项研究把输入差异转化成遗传算法的载体，接下来需要解决的是如何评估输入差异，针对这一问题，该研究根据模加运算的差异传播特性，设计了一种新方法用于评价输入差异。模加运算具有差分传播特性，依据输入差异能够推算出差异特征，推算时，若输入差异与输出差异的前一位数值不同，则输出差异的当前位值无法确定，既可能是0也可能是1，针对这种情况，本研究分别对不确定的位尝试赋值为0和1，并借助分支界定技术提升搜索效率，该新方法被用作适应度函数，成功实现了将遗传算法应用于差异特征探寻。

这项研究的方案应用于密码学中的SPECK32与SPECK48算法的差分攻击，所得到的差分属性在轮数与出现几率方面，达到了当前最优的差分属性水准。图1展示了本项研究揭示的SPECK32和SPECK48的差分属性。在SPECK32上，本项研究达到了当前最佳的差分性能；在SPECK48上，本项研究的执行时间与其它方法的时间表现基本持平。图2展示了本项研究与其它方法针对SPECK32和SPECK48的差分攻击结果对比。通过分析对比情况，可以看出本项研究与其它方法的研究成果具有可比性。

图1 SPECK32和SPECK48的差分特征

图二比较了本项研究同其他研究在针对SPECK32和SPECK48所实施的差分攻击方面的不同之处

作者简介

康漫是第一作者，他在2022年从中国科学院信息工程研究所博士毕业，研究领域涉及密码学及信息安全。此前，他在2017年从北京化工大学获得硕士学位。更早的时候，他在2013年从河北地质大学拿到了学士学位。

李永强担任通讯作者，目前任职于中国科学院信息工程研究所，担任副研究员一职。他的研究领域主要集中在分组密码算法的设计与分析方面。其代表性贡献有：首次借助非交换元素，成功构建了循环对合MDS矩阵；首次提出了一种2m比特的置换方案，该方案与逆函数不等价，同时具备已知的最佳抗差分攻击和抗线性攻击性能。该研究成果见于IEEE Transactions on Information Theory、DCC、FFA等学术期刊开元ky888棋牌官方版，亦发表于Asiacrypt、CHES、FSE等学术会议。负责人承担了重点研发计划项目，同时获得了国家自然科学基金的面上项目与青年项目的资助。

文章信息

改进遗传算法的ARX分组密码差分分析

康满，李永强，焦林，王明生。

中国电子杂志，二零二三年，三十二卷第二期：二二五至二三六页。

DOI: 10.23919/cje.2021.00.415