2023-05-10计算机应用,JournalofComputerApplications2023,43(5):1504-1510ISSN1001-9081CODENJYIIDUhttp：//www.joca.cn基于混合整数线性规划模型的SPONGENTS盒紧凑约束分析石一鹏1，刘杰1*，祖锦源1，张涛1，张国群2（1.西北工业大学软件学院，西安710129；2.上海机电工程研究所，上海201109）（∗通信作者电子邮箱lucky_jiel@nwpu.edu.cn）摘要：应用基于混合整数线性规划（MILP）模型的S盒紧凑约束计算方法，可以较好地解决SPONGENT在差分密码分析过程中差分路径搜索效率低下的问题；为寻找S盒的最优描述，提出一种紧凑性验证算法从约束条件存在必要性的角度验证S盒的不等式约束的紧凑性问题。首先，引入MILP模型分析SPONGENTS盒的不等式约束，得到了由23个不等式组成的约束；然后，提出一种用于评价约束不等式存在必要性的指标，并基于该指标提出了一种验证约束不等式组紧凑程度的紧凑性验证算法；最后，使用所提算法验证所求得的SPONGENTS盒约束的紧凑性。计算分析表明，23个不等式都具有唯一可以排除的不可能差分模式，即每个不等式都有存在的必要性；同时，对于同一案例，与利用贪心算法原理筛选的不等式相比，数量减少了20%。因此，所得到的SPONGENT的S盒不等式约束是紧凑的，且所提紧凑性验证算法的效果要优于对比的贪心算法。关键词：差分密码分析；混合整数线性规划；代换‒置换网络；SPONGENT；S盒中图分类号：TP309.7文献标志码：ACompactconstraintanalysisofSPONGENTS-boxbasedonmixedintegerlinearprogrammingmodelSHIYipeng1，LIUJie1*，ZUJinyuan1，ZHANGTao1，ZHANGGuoqun2（1.SchoolofSoftware，NorthwesternPolytechnicalUniversity，Xi'anShaanxi710129，China；2.ShanghaiInstituteofMechanicalandElectricalEngineering，Shanghai201109，China）Abstract:ApplyingthecompactconstraintcalculationmethodofS-boxbasedonMixedIntegerLinearProgramming（MILP）modelcansolvethelowefficiencyofdifferentialpathsearchofSPONGENTindifferentialcryptanalysis.TofindthebestdescriptionofSbox，acompactnessverificationalgorithmwasproposedtoverifytheinequalityconstraintsinS-boxfromtheperspectiveofthenecessityoftheexistenceofconstraints.Firstly，theMILPmodelwasintroducedtoanalyzetheinequalityconstraintsofSPONGENTS-box，andtheconstraintcomposedof23inequalitieswasobtained.Then，anindexforevaluatingth...
