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

SAT-based differential automatic search algorithm using divide-and-conquer strategy and its applications

作　　者：胡斌[1] 谈潇 王森鹏 HU Bin;TAN Xiao;WANG Senpeng(Department of Cryptogram Engineering,Information Engineering University,Zhengzhou 450001,China;State Key Laboratory of Cryptology,Beijing 100878,China)

机构地区：[1]信息工程大学密码工程学院,河南郑州450001 [2]密码科学技术国家重点实验室,北京100878

出　　处：《通信学报》2023年第4期137-144,共8页Journal on Communications

基　　金：国家自然科学基金资助项目(No.62102448)。

摘　　要：为了提高自动化搜索效率,结合分治策略提出了一种基于SAT模型的最优差分特征搜索算法。利用任意部分连续轮的Matsui边界条件提供的信息,将搜索空间划分为互不相交的子集。通过分析SAT差分模型间的可满足性关系,提出一种降序分支搜索链模型。进一步地,在模型优化层面,减少了需搜索划分子集数量的方法;在算法实现层面,结合并行技术实现对模型搜索空间的约减。将加速算法应用于ARX类密码算法族SPECK,获得了20轮、14轮、11轮SPECK-48、SPECK-96、SPECK-128的最优差分特征,较现有最好结果分别提高了1轮、4轮、2轮。To improve the efficiency of automatic search,an algorithm for searching the optimal differential characteristics based on SAT model was proposed by combining the divide-and-conquer strategy.The search space was divided into disjoint subsets by using the information from Matsui boundary conditions of arbitrary continuous rounds.By analyzing the relationships between satisfiability of differential models based on SAT,a descending branch search chain model was proposed.Furthermore,at the model optimization level,the number of subsets that need to be searched and partitioned was decreased.At the level of algorithm implementation,the search space was reduced by utilizing the parallel technology.Finally,the accelerated algorithm was applied to SPECK family of ARX cryptographic algorithms.The 20,14,11-round optimal differential characteristics of SPECK-48,SPECK-96,SPECK-128 are obtained,which increase the previous best results by 1,4,2 rounds respectively.

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]