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

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

（1.中國電子科技集團公司第三十研究所，四川 成都 610041；2.保密通信重點實驗室，四川 成都 610041）

0 引言

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

2015 年，Todo 等人給出了S 盒可分性質的非比特級傳播規則[1]，在代數次數已知的情況下，可以計算出所有的可分特征，但并沒有給出非比特級刻畫。

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

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

因此，為解決S 盒非比特級可分特征的刻畫問題，使其具有通用性，同時支持MILP 求解器，本文研究了可分特征的線性不等式刻畫，給出3 種刻畫方法及其一般刻畫形式，其中，凸包的H 表示方法使用的線性不等式數量最少，并且不使用臨時變量，但無法實現等價刻畫；大M 方法在增加一個二進制臨時變量的情況下，能夠實現等價刻畫，但使用的線性不等式數量最多；維數擴充法同樣增加一個二進制臨時變量，實現等價刻畫，并且使用的線性不等式數量與凸包的H 表示方法相當，刻畫效果達到最優。

1 相關知識

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

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

那么就稱多重集X滿足可分性質特別地，當n0=n1=…=nm-1=1 時，多重集X滿足比特級可分性質。

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

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

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

2 凸包的H 表示方法

對于集合V，所有包含V的凸集的交集稱為V的凸包，其本質是指一個最小凸多面體，滿足V中的元素要么在凸多面體上，要么在其內部。特別地，當V是由二維平面上的一些點構成的集合時，它的凸包就是將最外層的點連接起來構成的凸多邊形。

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

對 于n比特S盒，不妨設n=md+r，其中0

建立二維空間坐標系，連接最外層的整數點，如圖1 所示。

圖1 Vn,d 的凸包

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

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

于是，通過式（2）或式（3）實現了Vn,d的刻畫。

由于Vn,d的凸包中包含了不屬于Vn,d的整數點，因此式（2）或式（3）是Vn,d的非等價刻畫。

3 大M 方法

大M 方法是在線性規劃中解決條件約束的形式化問題而被提出的[14]。設條件約束中的A1x≤b1和A2x≤b2至少有一個成立。大M 方法通過引入二進制臨時變量y和設置大數M實現條件約束：

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

定義2（離散凸集）：設集合V是一個由整數點構成的集合，如果集合V的凸包中包含的所有整數點都恰好屬于集合V，則稱集合V是一個離散凸集，否則稱集合V不是一個離散凸集。

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

性質1：Vn,d不是一個離散凸集。

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

證明：不妨設n=md+r，其中0

建立二維空間坐標系，連接最外層的整數點，如圖2 所示。

圖2 的凸包

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

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

（1）當r=1，m=1 時，

（2）當r=1，m>1 時，

（3）當r=2 時，

（4）當r>2 時，

式中：b∈F2；M是一個較大的正整數。

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

4 維數擴充法

維數擴充法的主要思想是對集合Vn,d的維數進行擴充，使得擴充后的集合成為離散凸集，然后結合凸包的H 表示方法，實現Vn,d的等價刻畫。

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

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

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

性質4：當|a-b|=1 時，是一個離散凸集。

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

圖3 Vspn,d 的凸包

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

（1）當r=1，m=1 時，的凸包是一個三棱錐，由平面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 劃分而成，等價刻畫的一般形式為：

（2）當r=1，m>1 時，的凸包是一個四棱錐，由平面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 劃分而成，等價刻畫的一般形式如式（10）所示。

（3）當r=2 時，的凸包是一個四棱錐，由平面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 劃分而成，等價刻畫的一般形式為：

（4）當r>2 時，的凸包是一個五棱錐，由平 面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 劃分而成，等價刻畫的一般形式如式（12）所示。

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

5 刻畫效果對比

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

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

凸包的H 表示方法不會引入臨時變量，得到的線性不等式刻畫屬于非等價刻畫，而大M 方法和維數擴充法需要引入1 個二進制臨時變量，得到的線性不等式刻畫屬于等價刻畫。使用凸包的H 表示方法，對應的線性不等式數量最少；使用大M 方法，對應的線性不等式數量最多；而使用維數擴充法，對應的線性不等式數量與凸包的H 表示方法相當。因此，與凸包的H 表示方法和大M 方法相比，維數擴充法的刻畫效果最優，對應的線性不等式是最優刻畫。

為了驗證一般形式的正確性，針對常用的4 比特S 盒和8 比特S 盒進行了實驗驗證，驗證結果如表2 所示，不同刻畫方法對應的一般形式均能正確地刻畫S 盒非比特級可分特征，其中凸包的H 表示方法對應的一般形式是非等價刻畫，大M 方法和維數擴充法對應的一般形式為等價刻畫。

6 結語

本文旨在解決S 盒非比特級可分特征的線性不等式刻畫問題，給出了凸包的H 表示方法、大M方法和維數擴充法3種刻畫方法及其一般刻畫形式。其中，大M 方法和維數擴充法首次實現了S 盒非比特級可分特征的等價刻畫，并且維數擴充法通過引入一個二進制臨時變量，在實現等價刻畫的同時，對應的線性不等式數量最少，是一種最優刻畫方法，對應的一般形式可直接應用于分組密碼的自動化積分分析中。