本发明涉及密码分析，尤其涉及一种基于milp的从ddt快速恢复s盒的方法和装置。
背景技术：
：：1、从差分分布表(differential distribution table,ddt)中恢复s盒对于现有的密码分析技术十分重要。boura等人(boura,christina&canteaut,anne&jean,jérémy&suder,valentin.(2019).two notions of differential equivalence onsboxes.designs,codes and cryptography.87.10.1007/s10623-018-0496-z.)提出了一个猜测决定算法(guess-and-determine,gd)，从s盒的ddt表恢复s盒，该算法使用了深度优先的搜索策略。之后，dunkelman(dunkelman,o.and huang,s.2019.reconstructing an s-box from its difference distribution table.iacr transactions on symmetriccryptology.2019,2(jun.2019),193-217.doi:https://doi.org/10.13154/tosc.v2019.i2.193-217.)提出了使用差分分布表和线性逼近表(linear approximationtable,lat)之间联系恢复s盒的方法。2022年lu等人(lu,z.,mesnager,s.,cui,t.et al.anstp-based model toward designing s-boxes with good cryptographicproperties.des.codes cryptogr.90,1179-1202(2022).https://doi.org/10.1007/s10623-022-01034-2)指出上述两方法受限于ddt的已知部分，并首次提出了基于可满足性问题(satisiability problem,sat)的从ddt中恢复s盒的自动化方法。2、但是上述方法从ddt中恢复s盒的速度还有待提升。技术实现思路1、为进一步提升从ddt中恢复s盒的速度，本发明首次基于混合线性整数规划问题(mixed integer linear programming,milp)提出了一种基于milp的从ddt快速恢复s盒的方法和装置。2、为了实现上述目的，本发明采用以下技术方案：3、本发明一方面提出一种基于milp的从ddt快速恢复s盒的方法，包括：4、步骤1：构造milp模型，在milp模型中声明s盒在地址i的取值yi和该s盒的ddt在地址(α,β)的取值dα,β；5、步骤2：刻画yi与dα,β之间的关系；6、步骤3：在milp模型中设定dα,β的全部或部分取值；7、步骤4：对该milp模型进行求解，直到返回满足该ddt的s盒的可行解。8、进一步地，所述步骤1中，按照以下方式在milp模型中声明s盒在地址i的取值yi：9、声明整数变量{yi|0≤i<2n,0≤yi<2n}，其中变量yi为s盒在地址i的取值，即yi＝s(i)，n为s盒的比特位数。10、进一步地，所述步骤1还包括：11、添加y0,y1,…,y2n-1中两两不相等的约束以加快milp模型的求解速度，即12、{yi≠yj|0≤i<2n,i<j<2n}。13、进一步地，所述步骤1中，按照以下方式在milp模型中声明该s盒的ddt在地址(α,β)的取值dα,β：14、声明整数变量{dα,β|1≤α,β<2n,0≤dα,β≤2n}，其中dα,β为该s盒的ddt在地址(α,β)的取值。15、进一步地，所述步骤2包括：16、声明整数变量{dα,x|1≤α<2n,0≤x<2n,1≤dα,x≤2n}表示当前s盒在输入为x时和输入为时的输出差分，对于1≤α<2n和0≤x<2n，添加如下约束17、18、声明整数变量{fα,x,β|1≤α<2n,0≤x<2n,1≤β<2n,0≤fα,x,β≤1}表示dα,x是否为β的标志信号，19、建立变量fα,x,β与dα,β之间的联系，20、本发明另一方面还提出一种基于milp的从ddt快速恢复s盒的装置，包括：21、变量声明模块，用于构造milp模型，在milp模型中声明s盒在地址i的取值yi和该s盒的ddt在地址(α,β)的取值dα,β；22、关系刻画模块，用于刻画yi与dα,β之间的关系；23、取值设定模块，用于在milp模型中设定dα,β的全部或部分取值；24、模型求解模块，用于对该milp模型进行求解，直到返回满足该ddt的s盒的可行解。25、与现有技术相比，本发明具有的有益效果：26、本专利采取了与前人完全不同的技术方案，即采用基于milp求解问题构建了从ddt恢复s盒的解决方案，其相对于其他方案的优势如下：27、(1)相对于boura等人或dunkelman等人的猜测决定算法，本专利提出的基于milp从ddt恢复s盒的方法更加简单，并且能够仅根据部分ddt恢复s盒。28、(2)相对于lu等人基于sat问题的求解方案，本专利采取了完全不同的技术路线，即采用基于milp问题的自动化求解方案，因为milp对于整数加法更加友好，求解速度会更快。29、(3)sat求解器每次求解一般只会给出当前问题的一个可行解，而milp求解器(例如gurobi)可以一次返回多个解，加快了寻找满足ddt的不同s盒。技术特征：1.一种基于milp的从ddt快速恢复s盒的方法，其特征在于，包括：2.根据权利要求1所述的基于milp的从ddt快速恢复s盒的方法，其特征在于，所述步骤1中，按照以下方式在milp模型中声明s盒在地址i的取值yi：3.根据权利要求2所述的基于milp的从ddt快速恢复s盒的方法，其特征在于，所述步骤1还包括：4.根据权利要求1所述的基于milp的从ddt快速恢复s盒的方法，其特征在于，所述步骤1中，按照以下方式在milp模型中声明该s盒的ddt在地址(α,β)的取值dα,β：5.根据权利要求1所述的基于milp的从ddt快速恢复s盒的方法，其特征在于，所述步骤2包括：6.一种基于milp的从ddt快速恢复s盒的装置，其特征在于，包括：技术总结本发明公开一种基于MILP的从DDT快速恢复S盒的方法和装置，该方法包括：步骤1：构造MILP模型，在MILP模型中声明S盒在地址i的取值y<subgt;i</subgt;和该S盒的DDT在地址(α,β)的取值D<subgt;α,β</subgt;；步骤2：刻画y<subgt;i</subgt;与D<subgt;α,β</subgt;之间的关系；步骤3：在MILP模型中设定D<subgt;α,β</subgt;的全部或部分取值；步骤4：对该MILP模型进行求解，直到返回满足该DDT的S盒的可行解。本发明提出的方法更加简单，能够仅根据部分DDT恢复S盒，本发明采用基于MILP问题的自动化求解方案，求解速度更快，且采用MILP求解器，可以一次返回多个解，加快了寻找满足DDT的不同S盒。技术研发人员：吕广秋,金晨辉,崔霆,杨阳,陈士伟,张际焱,史臻受保护的技术使用者：中国人民解放军战略支援部队信息工程大学技术研发日：技术公布日：2024/11/11
