基于分治策略的SAT差分自动化搜索算法及其应用

摘要：

为了提高自动化搜索效率,结合分治策略提出了一种基于SAT模型的最优差分特征搜索算法.利用任意部分连续轮的Matsui边界条件提供的信息,将搜索空间划分为互不相交的子集.通过分析SAT差分模型间的可满足性关系,提出一种降序分支搜索链模型.进一步地,在模型优化层面,减少了需搜索划分子集数量的方法;在算法实现层面,结合并行技术实现对模型搜索空间的约减.将加速算法应用于ARX类密码算法族SPECK,获得了 20 轮、14 轮、11 轮 SPECK-48、SPECK-96、SPECK-128 的最优差分特征,较现有最好结果分别提高了 1轮、4轮、2轮.

关键词：差分特征、分组密码、自动化搜索、分治策略

所属期刊栏目：44

分类号：TP391(计算技术、计算机技术)

资助基金：国家自然科学基金No.62102448

在线出版日期：2023-05-12（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：137-144