基于混合整數(shù)線性規(guī)劃的分組密碼安全性分析?

劉千里 吳 暉

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

1 引言

針對(duì)分組密碼算法的分析，差分分析和線性分析是兩種典型的分析方法，相應(yīng)的差分概率和線性概率是評(píng)估分組密碼算法安全性的重要指標(biāo)，在分組密碼算法設(shè)計(jì)中，首要評(píng)估的就是算法在差分分析和線性分析的下安全強(qiáng)度［1～2］。

在差分分析方法中，核心是尋找高概率的差分特性和差分路徑；在線性分析方法中，關(guān)鍵是選擇高概率的線性逼近和線性路徑；而對(duì)于最大差分概率和最大線性逼近概率往往是通過(guò)分析密碼算法的最小活躍S 盒數(shù)量來(lái)進(jìn)行評(píng)估。當(dāng)前，對(duì)于一個(gè)分組密碼算法而言，自動(dòng)化搜索活躍S 盒是差分分析與線性分析的研究熱點(diǎn)［3～4］。

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

本文將混合整數(shù)線性規(guī)劃方法進(jìn)一步推廣到廣義Feistel結(jié)構(gòu)的安全性分析中，將搜索最小活躍S 盒數(shù)量問(wèn)題轉(zhuǎn)化為混合整數(shù)線性規(guī)劃問(wèn)題，通過(guò)求解最優(yōu)化問(wèn)題得到活躍S 盒的下界，通過(guò)在I 型廣義Feistel結(jié)構(gòu)上優(yōu)化建模，給出了混合整數(shù)線性規(guī)劃方法在分組密碼算法分析中的具體應(yīng)用。

2 基礎(chǔ)運(yùn)算的約束建模

一般分組密碼運(yùn)算包括S 盒操作、異或操作、線性變換以及分支操作，本節(jié)首先針對(duì)這些基本運(yùn)算，基于字節(jié)運(yùn)算構(gòu)建截?cái)嗖罘址治瞿Ｐ停丛诜治鲋锌紤]每個(gè)字節(jié)上要么存在非零差分，要么差分為零［7～8］。

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

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

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

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

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

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

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

3 I型廣義Feistel結(jié)構(gòu)的優(yōu)化模型建立

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

一輪I型廣義Feistel結(jié)構(gòu)如下所示［11］：

不妨設(shè)分組長(zhǎng)度為16 字節(jié)，其中F=L?S是32 比特進(jìn)32 比特出的函數(shù)，其中包含字節(jié)S 盒查表，L是MDS線性變換。

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

圖1 I型廣義Feistel結(jié)構(gòu)

最后，應(yīng)用上一節(jié)異或運(yùn)算的差分向量約束的結(jié)論（1），可以得到差分向量與之間的約束關(guān)系：

目標(biāo)函數(shù)為使得活躍S 盒最小，而S 盒僅在F=L?S函數(shù)中出現(xiàn)，因此，僅影響活躍S盒數(shù)量，目標(biāo)函數(shù)為

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

至此，我們建立了標(biāo)準(zhǔn)的優(yōu)化約束模型，給定輪數(shù)R，即可求解該模型下的最小差分活躍S盒，同樣地，可以建立了標(biāo)準(zhǔn)的優(yōu)化約束模型，對(duì)給定輪數(shù)R，求解該模型下的最小線性活躍S盒。

4 優(yōu)化模型求解

采用文獻(xiàn)［12］中的專(zhuān)用優(yōu)化工具編程求解上述優(yōu)化模型，代碼如下。

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

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

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

5 結(jié)語(yǔ)

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