[發(fā)明專利]一種基于大狀態(tài)S盒的自動化搜索差分路徑的方法及應(yīng)用

有效

• 申請?zhí)枺?/td>: 202011362011.6
• 申請日: 2020-11-27
• 公開（公告）號: CN112532375B
• 公開（公告）日: 2022-12-02
• 發(fā)明（設(shè)計）人: 潘印雪
• 申請（專利權(quán)）人: 華東師范大學(xué)
• 主分類號: H04L9/00
• 分類號: H04L9/00;H04L9/06
• 代理公司: 上海德禾翰通律師事務(wù)所 31319
• 代理人: 夏思秋

1.一種基于大狀態(tài)S盒的自動化搜索差分路徑的方法，其特征在于，所述大狀態(tài)S盒為8-bitS盒，所述方法包括以下步驟：

步驟A：利用字節(jié)級MILP模型對r-輪密碼各組件進(jìn)行建模，并進(jìn)一步建模密碼不同輪之間的關(guān)系以及每輪S盒的數(shù)量關(guān)系，得到最小活躍S盒個數(shù)及其位置的集合；所述步驟A進(jìn)一步包括：

步驟A1：利用字節(jié)級MILP模型對密碼各組件以及不同輪之間的關(guān)系和每輪S盒的數(shù)量關(guān)系進(jìn)行建模；

步驟A2：統(tǒng)計r-輪分組密碼算法中涉及到的所有操作，使用步驟A1中的模型建模，并將其轉(zhuǎn)化為Gurobi求解器語言；所述步驟A2進(jìn)一步包括：

步驟A21：根據(jù)A1中的模型構(gòu)建r-輪密碼算法的MILP模型，并將其轉(zhuǎn)化為求解器語言；預(yù)先估計一個S盒數(shù)量的上界，將其添加到模型中；

步驟A22：利用Gurobi求解器求解模型，對于低輪的密碼，直接指定求解器的輸出為活躍S盒數(shù)目及其位置；對于高輪的密碼，多定義一個callback()函數(shù)；

步驟A3：判定求解器是否有解，如果有解，則表明找到該輪密碼最小活躍S盒數(shù)量的下界及其位置，在模型中移除此種情況，繼續(xù)求解；否則，則表明全部解已找到；

步驟B：根據(jù)密碼S盒的差分分布表基于布爾函數(shù)和凸包原理對S盒進(jìn)行有關(guān)概率的比特級建模，并建立一個過濾模型，對S盒概率模型進(jìn)行再處理，得到經(jīng)過濾模型篩選后指定需要的數(shù)量的不等式集合；所述步驟B進(jìn)一步包括：

步驟B1：由密碼S盒的表達(dá)式生成差分分布表，根據(jù)差分分布表非零權(quán)重值的不同，將其分為若干個子表；

步驟B2：對S盒的子差分分布表采用布爾函數(shù)和凸包原理進(jìn)行有關(guān)概率的比特級建模；

步驟B3：建立一個過濾模型，對S盒概率模型進(jìn)行再處理，得到特定數(shù)量的不等式集合；

所述步驟B2進(jìn)一步包括：

步驟B21：對于數(shù)據(jù)量最小的子差分分布表，根據(jù)布爾函數(shù)原理，利用LogicFriday軟件轉(zhuǎn)化為線性不等式；

步驟B22：將剩余的每一個子差分分布表分成16個分組(*,*,*,*,x₄,...,x_n-1,y₀,...,y_n-1)，每個分組的(x₄...,x_n-1,y₀,...,y_n-1)部分，根據(jù)凸包原理，經(jīng)過SageMath軟件處理轉(zhuǎn)化為線性不等式；

步驟B23：對于步驟B22中的線性不等式，記δ為負(fù)系數(shù)之和，θ為常系數(shù)，則令λ＝δ+θ，若所述線性不等式有一個系數(shù)等于λ或-λ則保留這個不等式；否則，不保留；

步驟B24：擴(kuò)充步驟B23中的16組(x₀,x₁,x₂,x₃)對應(yīng)位置在不等式中的系數(shù)；若x_i為0時，則此位置的系數(shù)為|λ|且常系數(shù)不變，若x_i為1時，此位置的系數(shù)為-|λ|，并且常系數(shù)變?yōu)?δ；

所述步驟B3進(jìn)一步包括：

步驟B31：將S盒的不可能差分模式依次代入步驟B2得到的全部不等式中，如果不等式不成立，說明此不等式可將不可能差分模式去除，記下全部符合條件的不等式的序集合

步驟B32：根據(jù)約簡算法：不可能差分模式必須至少被1個不等式排除在解空間外，構(gòu)建MILP過濾模型篩選步驟B31中的不等式，指定需要的不等式數(shù)量，然后求得特定數(shù)量的不等式集合；

步驟C：利用比特級MILP模型對r-輪密碼各組件、步驟A得到的活躍S盒位置以及S盒差分分布表概率模型進(jìn)行統(tǒng)一建模，得到高概率差分路徑；所述步驟C進(jìn)一步包括：

步驟C1：基于比特用線性不等式來刻畫密碼各線性組件操作；

步驟C2：利用步驟A和步驟B得到的S盒位置集合和S盒差分傳播不等式，根據(jù)不同的概率添加不同的變量，來概率化活躍S盒；

步驟C3：構(gòu)造r-輪密碼比特級MILP模型，并轉(zhuǎn)化為Gurobi求解器語言，指定求解器的輸入和輸出，得到概率值和相應(yīng)的差分路徑。

2.根據(jù)權(quán)利要求1所述的自動化搜索差分路徑的方法，其特征在于，步驟A2中，所述操作包括：線性變換，XOR，不同輪之間的關(guān)系轉(zhuǎn)化和漢明重量、每輪活躍S盒數(shù)量約束。

3.根據(jù)權(quán)利要求1或2所述的方法在大狀態(tài)S盒自動化搜索差分路徑上的應(yīng)用。