S 盒可分特征的線性不等式刻畫研究*

胡建勇，張文政，董新鋒，周 宇，苗旭東

（1.中國(guó)電子科技集團(tuán)公司第三十研究所，四川 成都 610041；2.保密通信重點(diǎn)實(shí)驗(yàn)室，四川 成都 610041）

0 引言

近年來(lái)，隨著可分性質(zhì)[1]的提出，基于可分性質(zhì)的積分分析[1-8]被相繼提出，并逐步走向自動(dòng)化，日趨成熟。S 盒作為常用的非線性密碼部件，其可分性質(zhì)的傳播嚴(yán)重影響積分路徑的長(zhǎng)度，因此S 盒可分特征的刻畫成為自動(dòng)化積分分析的關(guān)鍵。根據(jù)細(xì)粒度的不同，S 盒可分特征的刻畫可分為比特級(jí)刻畫和非比特級(jí)刻畫。

2015 年，Todo 等人給出了S 盒可分性質(zhì)的非比特級(jí)傳播規(guī)則[1]，在代數(shù)次數(shù)已知的情況下，可以計(jì)算出所有的可分特征，但并沒(méi)有給出非比特級(jí)刻畫。

2016 年，向澤軍等人給出了S 盒比特級(jí)可分特征的計(jì)算方法[4]，借助Sage Math 工具[9]，使用線性不等式，成功實(shí)現(xiàn)比特級(jí)刻畫。但比特級(jí)刻畫存在兩個(gè)問(wèn)題：一是比特級(jí)刻畫與S 盒的代數(shù)表達(dá)式有關(guān)，不具備一般性，無(wú)法支持動(dòng)態(tài)S 盒[10-13]的刻畫；二是對(duì)于大狀態(tài)盒，其比特級(jí)刻畫使用的線性不等式數(shù)量龐大，這會(huì)嚴(yán)重影響自動(dòng)化分析模型的求解效率，甚至無(wú)法有效求解。

2017 年，孫玲等人使用布爾邏輯方程，給出了S 盒可分特征的非比特級(jí)刻畫[5]，但這種刻畫同樣不具備一般性，不支持動(dòng)態(tài)S 盒的刻畫，同時(shí)也不支持混合整數(shù)線性規(guī)劃問(wèn)題（Mixed Integer Linear Programming，MILP）的求解器。

因此，為解決S 盒非比特級(jí)可分特征的刻畫問(wèn)題，使其具有通用性，同時(shí)支持MILP 求解器，本文研究了可分特征的線性不等式刻畫，給出3 種刻畫方法及其一般刻畫形式，其中，凸包的H 表示方法使用的線性不等式數(shù)量最少，并且不使用臨時(shí)變量，但無(wú)法實(shí)現(xiàn)等價(jià)刻畫；大M 方法在增加一個(gè)二進(jìn)制臨時(shí)變量的情況下，能夠?qū)崿F(xiàn)等價(jià)刻畫，但使用的線性不等式數(shù)量最多；維數(shù)擴(kuò)充法同樣增加一個(gè)二進(jìn)制臨時(shí)變量，實(shí)現(xiàn)等價(jià)刻畫，并且使用的線性不等式數(shù)量與凸包的H 表示方法相當(dāng)，刻畫效果達(dá)到最優(yōu)。

1 相關(guān)知識(shí)

設(shè)兩個(gè)m維向量a=(a0,a1,…,am-1)和b=(b0,b1,…,bm-1)，若對(duì)于i=0,1,…,m-1，都有ai≥bi，則稱向量a大于等于向量b，記為a≥b。

定義1（可分性質(zhì)）：設(shè)X是一個(gè)多重集，其元素都取值于，K是由m維向量構(gòu)成的集合，對(duì)于任意的正整數(shù)向量k∈K，k的第i+1 個(gè)分量ki取值范圍為0 ≤ki≤ni-1，如果對(duì)所有x∈X，滿足：

那么就稱多重集X滿足可分性質(zhì)特別地，當(dāng)n0=n1=…=nm-1=1 時(shí)，多重集X滿足比特級(jí)可分性質(zhì)。

對(duì)于n比特S 盒，設(shè)其輸入多重集滿足的可分性質(zhì)為Dkn，對(duì)應(yīng)的輸出多重集滿足的可分性質(zhì)記為，于是(k,k′)稱為S 盒的可分特征。假設(shè)S 盒的代數(shù)次數(shù)為d，根據(jù)S 盒可分性質(zhì)的非比特級(jí)傳播規(guī)則，則可分特征(k,k′)滿足：

因此，在已知S 盒的狀態(tài)大小n和代數(shù)次數(shù)d的情況下，可以根據(jù)式（1）計(jì)算出所有的可分特征，共計(jì)n+1 條。對(duì)于任意的一條可分特征(k,k′)，它都可以看作二維平面上的一個(gè)點(diǎn)。于是，這n+1 條可分特征可以看作二維平面上的一個(gè)點(diǎn)集，記為Vn,d，從而S 盒可分特征的刻畫實(shí)際上是對(duì)集合Vn,d的刻畫。

對(duì)于集合V，其線性不等式刻畫是指尋找一些線性不等式Λ，使得任意的x∈V都是Λ 的可行解。特別地，當(dāng)Λ 的所有可行解恰好構(gòu)成這個(gè)集合V時(shí)，則稱Λ 是V的等價(jià)刻畫，否則稱為非等價(jià)刻畫。Λ的求解效率取決于線性不等式的數(shù)量和變量的個(gè)數(shù)。因此，在自動(dòng)化分析中，優(yōu)先使用等價(jià)刻畫，并且盡量要求線性不等式的數(shù)量和變量的個(gè)數(shù)盡量小。

2 凸包的H 表示方法

對(duì)于集合V，所有包含V的凸集的交集稱為V的凸包，其本質(zhì)是指一個(gè)最小凸多面體，滿足V中的元素要么在凸多面體上，要么在其內(nèi)部。特別地，當(dāng)V是由二維平面上的一些點(diǎn)構(gòu)成的集合時(shí)，它的凸包就是將最外層的點(diǎn)連接起來(lái)構(gòu)成的凸多邊形。

使用凸包的H 表示方法刻畫集合V，實(shí)際上是對(duì)V的凸包進(jìn)行等價(jià)刻畫，這個(gè)凸包由一些平面或者直線劃分而成，只要計(jì)算每一個(gè)平面或者每一條邊并根據(jù)它們與V的相對(duì)位置，便能夠得到線性不等式刻畫。如果凸包中存在一個(gè)元素不屬于V，那么得到的線性不等式刻畫是V的非等價(jià)刻畫。

對(duì) 于n比特S盒，不妨設(shè)n=md+r，其中0

建立二維空間坐標(biāo)系，連接最外層的整數(shù)點(diǎn)，如圖1 所示。

圖1 Vn,d 的凸包

（1）當(dāng)r=1 時(shí)，最外層的整數(shù)點(diǎn)(0,0)，(1,1)，(n,n)和(md,m)形成三角形，由直線L0:y=x，和L2:y=(n-m)x-(n-m-1)劃分而成，得到一般刻畫形式：

（2）當(dāng)r>1 時(shí)，最外層的整數(shù)點(diǎn)(0,0)，(1,1)，(n,n),(md+r-1,m+1)和(md,m)，形成凸四邊形，由直線和L4:y=(n-m-1)x-(n-m-2)n劃分而成，得到一般刻畫形式：

于是，通過(guò)式（2）或式（3）實(shí)現(xiàn)了Vn,d的刻畫。

由于Vn,d的凸包中包含了不屬于Vn,d的整數(shù)點(diǎn)，因此式（2）或式（3）是Vn,d的非等價(jià)刻畫。

3 大M 方法

大M 方法是在線性規(guī)劃中解決條件約束的形式化問(wèn)題而被提出的[14]。設(shè)條件約束中的A1x≤b1和A2x≤b2至少有一個(gè)成立。大M 方法通過(guò)引入二進(jìn)制臨時(shí)變量y和設(shè)置大數(shù)M實(shí)現(xiàn)條件約束：

如式（4）所示，當(dāng)臨時(shí)變量y=0 時(shí)，A2x≤b2+M恒成立，約束條件為A1x≤b1；當(dāng)臨時(shí)變量y=1 時(shí)，A1x≤b1+M恒成立，約束條件為A2x≤b2。

定義2（離散凸集）：設(shè)集合V是一個(gè)由整數(shù)點(diǎn)構(gòu)成的集合，如果集合V的凸包中包含的所有整數(shù)點(diǎn)都恰好屬于集合V，則稱集合V是一個(gè)離散凸集，否則稱集合V不是一個(gè)離散凸集。

顯然，根據(jù)離散凸集的定義，使用凸包的H 表示方法刻畫離散凸集必然屬于等價(jià)刻畫。

性質(zhì)1：Vn,d不是一個(gè)離散凸集。

證 明：由 于(0,0) ∈Vn,d，(n,n) ∈Vn,d，這 兩點(diǎn)的連線必然包含于Vn,d的凸包，因此凸包中包含整數(shù)點(diǎn)(k,k)，k=0,1,…,n。由于S盒的代數(shù)次數(shù)d>1，根據(jù)可分特征的非比特級(jí)傳播規(guī)則，(2,2),(3,3),…,(n-1,n-1)都不是S 盒的可分特征，不滿足離散凸集的定義，因此Vn,d不是離散凸集。

證明：不妨設(shè)n=md+r，其中0

建立二維空間坐標(biāo)系，連接最外層的整數(shù)點(diǎn)，如圖2 所示。

圖2 的凸包

當(dāng)r=1，m=1 時(shí)，最外層整數(shù)點(diǎn)連接的圖形是一個(gè)三角形，由直線和L2:y=1劃分而成；當(dāng)r=1，m>1 時(shí)，最外層整數(shù)點(diǎn)連接的圖形是一個(gè)梯形，由直線和L4:y=m劃分而成；當(dāng)r=2時(shí)，最外層整數(shù)點(diǎn)連接的圖形是一個(gè)平行四邊形，由直線和L:y=x-m(d-1)劃分而成；當(dāng)r>2 時(shí)，最外層整數(shù)點(diǎn)連接的圖形是一個(gè)凸五邊形，由直線L0:y=x,，L6:y=m+1以及劃分而成。這些凸多邊形構(gòu)成的凸包，并且凸包中包含的所有整數(shù)點(diǎn)恰好都屬于集合。因此，是一個(gè)離散凸集。

注意到單個(gè)整數(shù)點(diǎn)構(gòu)成的集合一定是一個(gè)離散凸集。于是，Vn,d可以劃分為和{(n,n)}兩個(gè)離散凸集。使用凸包的H 表示方法計(jì)算和{(n,n)}的等價(jià)刻畫，它們便形成了條件約束，從而利用大M 方法可以得到Vn,d的一般刻畫形式。

（1）當(dāng)r=1，m=1 時(shí)，

（2）當(dāng)r=1，m>1 時(shí)，

（3）當(dāng)r=2 時(shí)，

（4）當(dāng)r>2 時(shí)，

式中：b∈F2；M是一個(gè)較大的正整數(shù)。

于是，式（5）、式（6）、式（7）和式（8）等價(jià)刻畫了Vn,d。

4 維數(shù)擴(kuò)充法

維數(shù)擴(kuò)充法的主要思想是對(duì)集合Vn,d的維數(shù)進(jìn)行擴(kuò)充，使得擴(kuò)充后的集合成為離散凸集，然后結(jié)合凸包的H 表示方法，實(shí)現(xiàn)Vn,d的等價(jià)刻畫。

性質(zhì)3：設(shè)V={(b,c)|b,c∈Z}是一個(gè)離散凸集，對(duì)于任意的整數(shù)a，令E(a,V)={(a,b,c)|b,c∈V}，則E(a,V)同樣是一個(gè)離散凸集。

證明：建立三維空間的坐標(biāo)系(t,x,y)，對(duì)于二維空間上的任意整數(shù)點(diǎn)(b,c)∈V，都可以將它看作三維空間平面t=0 上的整數(shù)點(diǎn)(0,b,c)，整數(shù)點(diǎn)(a,b,c)是(0,b,c)沿著t軸方向的平移點(diǎn)。因此，E(a,V)中的全部整數(shù)點(diǎn)都是V中對(duì)應(yīng)整數(shù)點(diǎn)沿著t軸方向的平移點(diǎn)，并且平移的距離都為a。在這種平移下，點(diǎn)的相對(duì)位置保持不變。V是一個(gè)離散凸集，其凸包內(nèi)所有整數(shù)點(diǎn)恰好都屬于集合V。這個(gè)凸包經(jīng)過(guò)相同的平移，構(gòu)成E(a,V)的凸包，它包含的整數(shù)點(diǎn)恰好也都屬于集合E(a,V)。因此，E(a,V)是一個(gè)離散凸集。

對(duì)于任意的整數(shù)a和b，令E(b,{(n,n)})，于是滿足性質(zhì)4。

性質(zhì)4：當(dāng)|a-b|=1 時(shí)，是一個(gè)離散凸集。

證明：建立三維空間的坐標(biāo)系(t,x,y)，于是E(a,) 中的點(diǎn)全部位于平面t=a上。E(b,{(n,n)})={(b,n,n)}，點(diǎn)(b,n,n)位于平面t=b上，可以看作平面t=a上的點(diǎn)(a,n,n)沿著t軸方向正向或者反向平移的點(diǎn)，由于|a-b|=1，平移的距離等于1，在平面t=a和平面t=b之間不含整數(shù)點(diǎn)。由于是離散凸集，根據(jù)性質(zhì)3，E(a,)同樣是離散凸集，在平面t=a上，存在一個(gè)凸包，使得凸包中所有的整數(shù)點(diǎn)恰好都屬于集合，這個(gè)凸包是一個(gè)凸多邊形，如圖3 所示。將整點(diǎn)與凸多邊形上的每一個(gè)頂點(diǎn)相連，從而形成棱錐，它是的凸包，并且其包含的整數(shù)點(diǎn)恰好都屬于。因此，是一個(gè)離散凸集。

圖3 Vspn,d 的凸包

于是，Vn,d的等價(jià)刻畫實(shí)際上就是的等價(jià)刻畫。由于中引入了臨時(shí)變量t，取值為a或者b。為了便于自動(dòng)化分析模型的求解，限定t為二進(jìn)制變量，不妨令a=1,b=0。

（1）當(dāng)r=1，m=1 時(shí)，的凸包是一個(gè)三棱錐，由平面t=0，t=1，x-y=0，(n-1)t+y-n=0 和平面n(n-2)-n(n-2)t+x-(n-1)y=0 劃分而成，等價(jià)刻畫的一般形式為：

（2）當(dāng)r=1，m>1 時(shí)，的凸包是一個(gè)四棱錐，由平面t=0，t=1，x-y=0，(n-m)t+y-n=0，-n(d-1)t+xdy+n(d-1)=0 和平面(n-1)(d-1)t-x+dy-n(d-1)=0 劃分而成，等價(jià)刻畫的一般形式如式（10）所示。

（3）當(dāng)r=2 時(shí)，的凸包是一個(gè)四棱錐，由平面t=0，t=1，x-y=0，-n(d-1)t+x-dy+n(d-1)=0，(n-1)(d-1)t-x+dy-n(d-1)=0 和平面m(d-1)t+x-y=0 劃分而成，等價(jià)刻畫的一般形式為：

（4）當(dāng)r>2 時(shí)，的凸包是一個(gè)五棱錐，由平 面t=0，t=1，x-y=0，(n-m-1)t+y-n=0，-n(d-1)t+x-dy+n(d-1)=0，(n-1)(d-1)t-x+dy-n(d-1)=0 和 平面((n-m)(1-r)+r)t+x-(r-1)y+n(r-2)=0 劃分而成，等價(jià)刻畫的一般形式如式（12）所示。

于是，式（9）、式（10）、式（11）、式（12）同樣等價(jià)刻畫了Vn,d。

5 刻畫效果對(duì)比

針對(duì)集合，在不同和的取值下，使用凸包的H表示方法、大M 方法和維數(shù)擴(kuò)充法得到線性不等式刻畫。如表1 所示，不同刻畫方法在刻畫類型、線性不等式數(shù)量和二進(jìn)制臨時(shí)變量個(gè)數(shù)方面各不相同。

表1 不同刻畫方法的刻畫效果

凸包的H 表示方法不會(huì)引入臨時(shí)變量，得到的線性不等式刻畫屬于非等價(jià)刻畫，而大M 方法和維數(shù)擴(kuò)充法需要引入1 個(gè)二進(jìn)制臨時(shí)變量，得到的線性不等式刻畫屬于等價(jià)刻畫。使用凸包的H 表示方法，對(duì)應(yīng)的線性不等式數(shù)量最少；使用大M 方法，對(duì)應(yīng)的線性不等式數(shù)量最多；而使用維數(shù)擴(kuò)充法，對(duì)應(yīng)的線性不等式數(shù)量與凸包的H 表示方法相當(dāng)。因此，與凸包的H 表示方法和大M 方法相比，維數(shù)擴(kuò)充法的刻畫效果最優(yōu)，對(duì)應(yīng)的線性不等式是最優(yōu)刻畫。

為了驗(yàn)證一般形式的正確性，針對(duì)常用的4 比特S 盒和8 比特S 盒進(jìn)行了實(shí)驗(yàn)驗(yàn)證，驗(yàn)證結(jié)果如表2 所示，不同刻畫方法對(duì)應(yīng)的一般形式均能正確地刻畫S 盒非比特級(jí)可分特征，其中凸包的H 表示方法對(duì)應(yīng)的一般形式是非等價(jià)刻畫，大M 方法和維數(shù)擴(kuò)充法對(duì)應(yīng)的一般形式為等價(jià)刻畫。

6 結(jié)語(yǔ)

本文旨在解決S 盒非比特級(jí)可分特征的線性不等式刻畫問(wèn)題，給出了凸包的H 表示方法、大M方法和維數(shù)擴(kuò)充法3種刻畫方法及其一般刻畫形式。其中，大M 方法和維數(shù)擴(kuò)充法首次實(shí)現(xiàn)了S 盒非比特級(jí)可分特征的等價(jià)刻畫，并且維數(shù)擴(kuò)充法通過(guò)引入一個(gè)二進(jìn)制臨時(shí)變量，在實(shí)現(xiàn)等價(jià)刻畫的同時(shí)，對(duì)應(yīng)的線性不等式數(shù)量最少，是一種最優(yōu)刻畫方法，對(duì)應(yīng)的一般形式可直接應(yīng)用于分組密碼的自動(dòng)化積分分析中。