基于混合整數線性規劃的分組密碼安全性分析?

劉千里 吳 暉

（海軍裝備部駐武漢地區第五軍事代表室 武漢 430205）

1 引言

針對分組密碼算法的分析，差分分析和線性分析是兩種典型的分析方法，相應的差分概率和線性概率是評估分組密碼算法安全性的重要指標，在分組密碼算法設計中，首要評估的就是算法在差分分析和線性分析的下安全強度［1～2］。

在差分分析方法中，核心是尋找高概率的差分特性和差分路徑；在線性分析方法中，關鍵是選擇高概率的線性逼近和線性路徑；而對于最大差分概率和最大線性逼近概率往往是通過分析密碼算法的最小活躍S 盒數量來進行評估。當前，對于一個分組密碼算法而言，自動化搜索活躍S 盒是差分分析與線性分析的研究熱點［3～4］。

Mouha 等［5～6］于2011 年將混合整數線性規劃思想應用于密碼學分析，把尋找最小活躍S 盒數量轉化為最優化問題，建立最優化數學模型，以最小活躍S 盒為優化目標，以差分/線性分支數為約束條件，然后采用優化工具求解數學模型，以求得目標函數的最小值。該方法在求解最小活躍S 盒的核心在于將建立最優化理論的數學模型，將密碼學中的運算特別是混淆和擴散模塊轉化為不等式約束，通過建立相應的目標函數和約束條件，得到優化的數學模型，最后求解優化問題，得到最小活躍S 盒數量。

本文將混合整數線性規劃方法進一步推廣到廣義Feistel結構的安全性分析中，將搜索最小活躍S 盒數量問題轉化為混合整數線性規劃問題，通過求解最優化問題得到活躍S 盒的下界，通過在I 型廣義Feistel結構上優化建模，給出了混合整數線性規劃方法在分組密碼算法分析中的具體應用。

2 基礎運算的約束建模

一般分組密碼運算包括S 盒操作、異或操作、線性變換以及分支操作，本節首先針對這些基本運算，基于字節運算構建截斷差分分析模型，即在分析中考慮每個字節上要么存在非零差分，要么差分為零［7～8］。

考慮n個字節的向量Δ=(Δ1,Δ2…,Δn)，定義關于向量Δ 的差分向量x=(x1,x2…,xn)：

下面以差分向量作為優化模型中的約束變量，建立一些基本運算的優化模型。

異或運算（⊕）。異或運算（Z=X⊕Y）含有輸入變量(X,Y)，一個輸出變量Z，設輸入差分向量為(x,y)，輸出差分向量為z，對于異或運算而言，其差分分支數為2，為在方程中表示差分分支數，引入虛擬二元變量d，當且僅當輸入差分向量(x,y)以及輸出差分向量z為零時，二元變量d才為零，否則為1。因此可以用如下不等式描述輸入輸出差分變量的關系：

線性變換（L）。線性變換（Y=L(X)），對應輸入差分向量(x1,x2,…,xM)，輸出差分向量(y1,y2,…,yM)，給定線性變換的差分分支數Bd，同樣地引入二元虛擬變量dL，用于描述輸入差分向量與輸出差分向量之間的約束關系，dL為零當且僅當輸入差分向量(x1,x2,…,xM)與輸出差分向量(y1,y2,…,yM)均為零，否則dL為1，因此可建立線性變換的約束不等式：

目標函數。目標函數選取為在變量的約束下，使得活躍S 盒最小，即使得通過S 盒的差分向量的和最小。此外，為避免出現差分全零情況，需要添加一個額外的約束，即輸入差分至少有一個非零。對于約束而言，如果所有約束變量都限制為二元變量，則整個優化模型為純整數線性規劃，實際上，只需要將虛擬變量d約束為二元變量，而其他變量根據該變量自動約束在二元域上，此時整個優化模型即為混合整數線性規劃，相對于純整數線性規劃而言，具有更快的求解效率。

同樣地，對于線性分析而言，可以針對線性掩碼集合T=(T1,T2,…Tn)，定義關于線性掩碼向量y=(y1,y2,…,yn)：

由于線性分析與差分分析存在對偶性，對于線性分析而言，線性變換（L）的約束描述與差分分析一致，僅需要將差分分支數Bd換為線性分支數BL［9］。對于異或運算而言，其約束模型與差分分析一致［10］，這里不再贅述。

3 I型廣義Feistel結構的優化模型建立

本節給出了分析I型廣義Feistel結構最小差分活躍S 盒建模具體過程，該過程可以推廣到一般的分組密碼算法的安全性分析。

一輪I型廣義Feistel結構如下所示［11］：

不妨設分組長度為16 字節，其中F=L?S是32 比特進32 比特出的函數，其中包含字節S 盒查表，L是MDS線性變換。

設第R輪的輸入差分向量,i=1,2,…,16，輸出差分向量,i=1,2,…,16，需要建立輸入差分向量與輸出差分向量之間的約束關系。設通過函數F后的差分向量為,i=1,2,…,4，而F包含差分分支數為5 的線性變換，則根據式（2）結果可得：

圖1 I型廣義Feistel結構

最后，應用上一節異或運算的差分向量約束的結論（1），可以得到差分向量與之間的約束關系：

目標函數為使得活躍S 盒最小，而S 盒僅在F=L?S函數中出現，因此，僅影響活躍S盒數量，目標函數為

綜合式（3）～（6），即可得到任意R輪的最小活躍S盒的優化模型：

至此，我們建立了標準的優化約束模型，給定輪數R，即可求解該模型下的最小差分活躍S盒，同樣地，可以建立了標準的優化約束模型，對給定輪數R，求解該模型下的最小線性活躍S盒。

4 優化模型求解

采用文獻［12］中的專用優化工具編程求解上述優化模型，代碼如下。

求解可得給定輪數R 下最小活躍S 盒數量N（R）如表1。

表1 不同輪數（R）下最小活躍S盒數量（N（R））

上表結果與采用剪枝策略的分析方法結果一致，但是基于混合整數線性規劃的分析和實現更為簡潔和易用。從上表可知，若選用的8 比特S 盒的差分概率及線性概率達到最優即2-6，那么24 輪時最小活躍S盒為24個，相應最大差分概率及最大線性逼近概率均為2-6×24=2-144<2-128，即采用I 型廣義Feistel結構至少需要24輪，方可抵抗差分分析與線性分析。

5 結語

本文將混合整數線性規劃方法應用于求解I型廣義Feistel結構的最小差分/線性活躍S盒，給出了優化約束模型的建立過程，通過軟件仿真，驗證了其正確性和有效性，該方法可以進一步推廣至相關密鑰分析、積分分析等，為算法設計和分析人員提供重要參考和指導，提高算法設計與分析的效率。