中国科学院信息工程研究所王明生研究员和李永强副研究员课题组在用遗传算法做差分分析方面取得进展，相关研究结果以“Differential Analysis of ARX Block Ciphers Based on an Improved Genetic Algorithm（基于改进遗传算法的ARX密码差分分析）”为题，在Chinese Journal of Electronics 2023年第2期发表。

文章简介

差分分析是密码分析中最重要的分析方法之一。目前，主要的差分分析方法是Matsui方法、混合整数线性规划、SAT和约束规划的方法。这些分析方法是基于数学和传统搜索方式的方法，无法全面有效地利用已有的搜索结果自主改进搜索过程。随着求解问题规模的增大，以上方法存在效率低，用时长的问题。遗传算法是一种元启发式搜索方法，通过模拟自然进化过程搜索全局最优解。由于遗传算法的搜索过程不依赖于数学计算，并且能够自主地调整和优化搜索方向，所以，近年来遗传算法被越来越多的用于密码设计和分析。然而，在密码分析中，目前已有的工作大多用遗传算法做密钥恢复，很少有工作将遗传算法用于密码分析最重要的一步——搜索差分特征。本工作首次将遗传算法用于差分特征搜索。

用遗传算法搜索差分特征面临的问题是无法直接将差分特征作为遗传算法的个体。为此，本工作将输入差分作为了遗传算法的个体。那么面临的问题是如何评价输入差分，本工作基于模加的差分传播性质，提出了一个新的算法用于评估输入差分。模加的差分传播性质表明：用输入差分可以推出差分特征，推导过程中，如果输入差分和输出差分的前一位不同，那么输出差分的当前位是不确定的，可以是0也可以是1。为此，本工作对不确定的位分别尝试0和1，然后用分支定界的方法提高搜索效率。此新算法作为适应度函数，成功地将遗传算法用于差分特征搜索。

本工作的方法用在了密码算法SPECK32和SPECK48的差分分析上，获得的差分特征的轮数和概率与目前已有的最好差分特征的轮数和概率一样。图1给出了本工作得到的SPECK32和SPECK48的差分特征。对于SPECK32，本工作获得了目前最优的差分；对于SPECK48，本工作的用时与已有工作的用时是可以相比较的。图2对比了本工作和已有工作对SPECK32和SPECK48的差分攻击。从对比结果可以看出，本工作与已有工作的结果是可比较的。

图1 SPECK32和SPECK48的差分特征

图2 本工作和已有工作对SPECK32和SPECK48差分攻击的对比

作者简介

康漫（第一作者），2022年毕业于中国科学院信息工程研究所，获得博士学位，研究方向是密码学、信息安全。2017年毕业于北京化工大学，获得硕士学位。2013年毕业于河北地质大学，获得学士学位。

李永强（通讯作者），现任中国科学院信息工程研究所副研究员。研究兴趣主要是分组密码算法设计与分析。取得的主要成果包括：首次利用非交换元素给出了循环对合MDS矩阵的构造；首次给出了与逆函数不等价的具有已知最优抵抗差分攻击和线性攻击能力的2m比特置换等。相关论文发表于IEEE Transactions on Information Theory，DCC，FFA等期刊,以及Asiacrypt，CHES，FSE等会议。主持重点研发课题，国家自然科学基金面上、青年项目。

文章信息

Differential Analysis of ARX Block Ciphers Based on an Improved Genetic Algorithm

KANG Man, LI Yongqiang, JIAO Lin, WANG Mingsheng.

Chinese Journal of Electronics, 2023, 32(2): 225-236.

DOI: 10.23919/cje.2021.00.415