[發(fā)明專利]一種基于MILP的Tweakable GOST2差分路線搜索方法

有效

• 申請?zhí)枺?/td>: 202110122266.3
• 申請日: 2021-01-28
• 公開（公告）號: CN112953703B
• 公開（公告）日: 2022-12-06
• 發(fā)明（設計）人: 王高麗;劉晟源
• 申請（專利權）人: 華東師范大學
• 主分類號: H04L9/06
• 分類號: H04L9/06
• 代理公司: 上海德禾翰通律師事務所 31319
• 代理人: 夏思秋

1.一種基于MILP的Tweakable GOST2差分路徑搜索方法，其特征在于，所述方法包括以下步驟：

步驟A：在字節(jié)層面，使用MILP模型對Tweakable GOST2進行建模，使用gurobi對模型進行求解，如果有解，則得到Tweakable GOST2差分路線中最小活躍S盒個數(shù)和活躍S盒位置的集合；所述步驟A進一步包括：

步驟A1：在字節(jié)層面利用MILP模型對Tweakable GOST2密碼算法各組件進行建模；對基于字節(jié)的密碼組件進行建模是利用不等式組來描述傳播規(guī)則的；所述步驟A1進一步包括：

步驟A11：使用不等式組刻畫XOR操作中基于字節(jié)的差分擴散路徑；

步驟A12：使用不等式組刻畫S盒操作中基于字節(jié)的差分擴散路徑；

步驟A13：使用不等式組刻畫模加操作中基于字節(jié)的差分擴散路徑；

步驟A2：對Tweakable GOST2密碼算法的Tweak模塊進行建模；所述步驟A2中，有兩種添加Tweak模塊的方式：假設i表示Tweakable GOST2算法中的第i輪，一種是在第i輪右側輸入差分異或Tweak、另一種是在第i輪輸出后面異或Tweak，用不等式組描述Tweakable GOST2算法Tweak模塊差分傳播和子Tweak生成的信息；

步驟A3：對Tweakable GOST2密碼算法的不同輪間關系進行建模；所述步驟A3中，使用不等式組描述Tweakable GOST2算法不同輪之間漢明重量，S盒數(shù)目，各組件之間關系信息，進而來描述Tweakable GOST2差分傳播特征；

步驟A4：使用python語言建模，并使用gurobi求解器求解，由于最優(yōu)解不止一個，得到最優(yōu)解后將當前解作為約束寫入模型中，直到當前解不是最優(yōu)解，或者求解器無解；

步驟B：在比特層面，根據(jù)GOST2算法S盒的相關性質，生成描述S盒的不等式；所述步驟B進一步包括：

步驟B1：在比特層面，根據(jù)GOST2算法S盒生成其對應的差分分布表和差分模式，并將差分模式按照概率分組；

步驟B2：使用SAGEMATH不等式生成器得到Tweakable GOST2的P凸包的H-表示；

步驟B3：對生成的不等式進行處理，得到不同概率對應的不等式；

步驟C：在比特層面，使用MILP模型對Tweakable GOST2進行建模設定求解器的初始值和終止條件，得到Tweakable GOST2差分路線；所述步驟C進一步包括:

步驟C1：在比特層面利用MILP模型對Tweakable GOST2密碼算法各組件進行建模；所述步驟C1進一步包括：

步驟C11：使用不等式組刻畫XOR操作中基于字節(jié)的差分擴散路徑；

步驟C12：使用不等式組刻畫S盒操作中基于字節(jié)的差分擴散路徑；

步驟C13：使用不等式組刻畫模加中基于字節(jié)的差分擴散路徑；

步驟C2：對Tweakable GOST2密碼算法的Tweak模塊進行建模；

步驟C3：根據(jù)步驟A得到的活躍S盒位置和個數(shù)和步驟B得到的描述S盒的不等式進行建模，設定求解器的初始值和終止條件，使用gurobi求解后得到Tweakable GOST2的差分路徑及其概率；

所述步驟C2中，使用不等式組描述Tweakable GOST2算法Tweak模塊差分傳播和子Tweak生成的信息；

所述步驟C3中，使用不等式組描述Tweakable GOST2算法不同輪之間漢明重量，S盒數(shù)目，各組件之間關系信息，進而來描述Tweakable GOST2差分傳播特征。