[發(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
• 代理人: 夏思秋

本發(fā)明公開了一種基于大狀態(tài)S盒的自動化搜索差分路徑的方法，所述方法包括：利用字節(jié)級MILP模型對r?輪密碼各組件進(jìn)行建模，并進(jìn)一步建模密碼不同輪之間的關(guān)系以及每輪S盒的數(shù)量關(guān)系，得到最小活躍S盒個數(shù)和活躍S盒位置的集合；根據(jù)密碼S盒的差分分布表基于布爾函數(shù)和凸包原理對S盒進(jìn)行有關(guān)概率的比特級建模，并建立一個過濾模型，對S盒概率模型進(jìn)行再處理，得到特定數(shù)量的不等式集合；利用比特級MILP模型對r?輪密碼各組件、活躍S盒位置以及S盒差分分布表概率模型進(jìn)行統(tǒng)一建模，得到最高概率的差分路徑。本發(fā)明可以有效地找出r?輪包含大狀態(tài)S盒的分組密碼算法活躍S盒數(shù)量下界及其最好的差分路徑。

技術(shù)領(lǐng)域

本發(fā)明屬于密碼分析技術(shù)領(lǐng)域，涉及一種基于大狀態(tài)S盒的自動化搜索差分路徑的方法，適合對基于大S盒的分組密碼算法高效搜索差分路徑，從而進(jìn)一步進(jìn)行差分分析。

背景技術(shù)

隨著互聯(lián)網(wǎng)的迅速發(fā)展，云時代和大數(shù)據(jù)時代應(yīng)運而來，萬物互聯(lián)，一切皆數(shù)據(jù)的環(huán)境下，信息安全問題已成為當(dāng)下最關(guān)注的問題之一。密碼算法作為保障信息安全的核心技術(shù)，其安全性至關(guān)重要。

差分分析是由Bihma和Shamir在1990年提出，是目前最為有效的密碼分析方法之一。差分分析幾乎適用于所有的分組密碼算法，可以說差分分析是密碼學(xué)安全分析的基礎(chǔ)。值得注意的是，差分分析的第一步，也是最重要的一步，就是尋找一條高概率的差分路徑，因此如何尋找一條有效的差分路徑成為密碼學(xué)者關(guān)注的問題。

近些年，基于MILP的自動化搜索差分路徑的方法廣受歡迎。Mouha等人首次提出字節(jié)級MILP模型，并用其找尋AES的最小活躍S盒個數(shù)。在Asiacrypt 2014，孫思維等人提出了比特級MILP框架來搜索包含4-bit S盒的密碼的差分路徑，并提出用貪心算法來約束MILP模型中有關(guān)S盒的不等式數(shù)量，但貪心算法不能保證不等式的最小數(shù)量。后來，Sasaki和Todo基于孫思維的框架提出一個新方法來約束S盒，可以得到指定數(shù)量的不等式，不足的是此方法對于8-bit的S盒不適用。

Abdelkhalek首次提出針對大狀態(tài)S盒的模型，然而生成的不等式數(shù)量太多，求解器無法運行，并不能找到包含8-bit S盒密碼的高輪差分路徑。2019年，Li和Wu提出了一種低bit擴(kuò)充高bit的方法，用于建模8-bit的S盒，但是存在建模不精準(zhǔn)的問題，有限的時間內(nèi)會生成許多無效的差分路徑。

發(fā)明內(nèi)容

為了解決現(xiàn)有技術(shù)存在的不足，本發(fā)明的目的是提供一種基于大狀態(tài)S盒的自動化搜索差分路徑的方法，綜合考慮了字節(jié)級和比特級MILP建模，采用Logic Friday，SageMath軟件和Gurobi求解器，提出對于大狀態(tài)S盒的新模型，能夠有效地找出r-輪包含大狀態(tài)S盒的分組密碼算法活躍S盒數(shù)量下界及高概率差分路徑，從而實現(xiàn)高效的自動化搜索基于大狀態(tài)S盒的差分路徑。

本發(fā)明提出了一種基于大狀態(tài)(8-bit)S盒的自動化搜索差分路徑的方法，包括以下步驟：

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

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

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

本發(fā)明所述步驟A進(jìn)一步包括：

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

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