基于有限域逆映射的輕量級加密SOPT-S盒構造與研究*

樊兆龍 ，徐啟建 ，徐勇軍 ，王 飛

（1.中國人民解放軍理工大學 南京 210007；2.中國電子設備系統工程公司研究所 北京 100141；3.中國科學院計算技術研究所 北京 100080）

1 引言

隨著普適計算的深入發展，人們可以隨時隨地、快速透明地獲得所需的數字化服務，由于各種各樣的信息數據均為人們共享，信息的安全問題也越來越復雜。如戰場中的軍事傳感網，節點在感知并獲得戰場實時信息的同時需對其加密以確保安全，并且考慮到傳感器節點能量小、計算能力低的特點，解決這一問題需要設計一個既能在能量及計算能力受限的傳感器節點上實施，又具有頑健性的輕量級加密算法。S盒作為分組密碼結構中唯一的非線性組件對于加密算法的頑健性有著重要的作用[1]。雖然現在存在許多安全性能較高的S盒，如AES中的S盒可以抵抗差分攻擊、線性攻擊等幾乎所有的攻擊，但由于其8×8的S盒需要1000 GE（gate equivalent），其大規模不適合能量受限的無線傳感網節點等設備[2]。另外，6×6（300 GE）S盒以及DES中6×4（120 GE）S盒也不符合輕量級需求。參考文獻[3]介紹了一種超輕量級加密算法PRESENT，該算法的非線性層采用4×4 S盒實現混亂特性，每個S盒只需28 GE，滿足小規模、低消耗的設計要求。參考文獻[4]隨后提出了一種新的算法LED（light encryption device），其中S盒的設計與PRESENT相同。參考文獻[5]中根據Feistel型密碼構造出LBlock密碼，該密碼非線性由8個不同的4×4 S盒并置而成。雖然4×4規模的S盒符合節點對于輕量級的要求，但是其加密算法的安全性也隨之降低，例如在參考文獻[6]的輕量級加密算法 KLEIN中，使用了 4×4對合S盒，即S盒的輸入輸出成對出現，雖然降低了解碼的硬件要求但是其密碼學特性中的差分均勻度以及雪崩效應隨之降低。因此，設計一個規模小但安全性高的S盒用于傳感器加密成為國內外研究的首要問題。

雖然算法抗攻擊性能不完全由S盒決定，但是在輕量級加密算法S盒中，依然是重要的一部分，小規模S盒若沒有較好的性能，整個算法的安全性也將受到影響。本文基于有限域GF（24）上的逆映射構造出一類次最優（suboptimal）4×4 S盒，首先通過求解GF（24）上不可約多項式對應的逆元，再經過一個仿射變換從而得出一系列S盒，最后根據設計要求篩選得出性能最佳的S盒。該算法首次將AES中S盒的構造方法用于輕量級S盒的構造，將其密碼學特性進行分析并與典型的輕量級加密算法PRESENT中S盒進行對比發現，該S盒的雪崩概率以及代數次數均優于PRESENT的S盒，抵抗差分攻擊的能力也強于后者，具有良好的密碼學特性，可以用于輕量級加密非線性層的設計中，為算法后續模塊的設計奠定良好的基礎。

2 預備知識

S盒概念首次出現在Lucifer算法中并隨之廣泛應用于DES、AES等許多密碼算法[7]，其設計要求是構造一個性能優良的S盒首先需要考慮的問題。

由于S盒的密碼學特性可用多輸出布爾函數來描述[8]，所以通過對多輸出布爾函數的分析來具體研究輕量級S盒（4×4）的設計思路。衡量其密碼學指標主要包括以下幾項。

（1）非線性度

令 S(x)=(f1(x),…,fn(x)):GF(2)n→GF(2)n是一個多輸出函數，則S(x)非線性度為:

其中，Ln為全體n元線性仿射函數集，dH(u·S(x),l)表示函數S(x)與l(x)之間的漢明距離。非線性度決定了S盒抵抗線性密碼分析的能力，非線性度越高，則抵抗線性攻擊的能力越強。當S(x)達到上界2n-1- 時，稱為Bent函數，即非線性最佳。

（2）差分均勻性

n×n S盒差分均勻度可表示為:

其中，δS(α,β)=|{x＝GF（2）n:S(x堠α)+S(x)=β}|。差分均勻性是用來衡量該密碼抗擊差分密碼分析能力的指標，由差分分布表來反映。差分分布表反映了輸入差分與輸出差分分布情況，分布越均勻，即差分傳播概率最大值越小，S盒抵抗差分攻擊的能力越強，最佳為滿足差分2-一致性S盒。

（3）雪崩效應

指S盒輸出任一比特與輸入比特之間的關系，衡量輸入改變對輸出改變的隨機性，即當輸入有1 bit改變時，有一半輸出比特改變時則滿足雪崩效應，而當每個輸出改變的概率（雪崩概率）為1/2時，滿足嚴格雪崩準則（SAC）[8]。

（4）代數次數及項數分布

代數次數用來衡量S盒的代數非線性程度，代數次數越高，項數越高，復雜度就越高，因此越難用線性表達式逼近。當S盒輸入為n時，最佳的代數次數值為n-1。

3 SOPT-S盒的構造

根據上面提出的設計原則，下面將基于有限域上的逆映射來構造4×4的SOPT-S盒，這類S盒具有良好的密碼學特性并且無陷門[1]。同時，許多大規模的S盒（AES）依靠此類數學函數方法來實現，這為輕量級S盒的構造提供了理論基礎。

3.1 SOPT-S盒構造方法

基于有限域上的逆映射的構造主要分為兩個可逆步驟。首先，將狀態字與GF（24）中的元素一一對應并在GF（24）上求出各狀態字的逆元。然后，根據上步求出的結果再通過一個仿射變換從而構造出4×4 S盒，該仿射變換可表示為:

其中，X-1為第一步的輸出，m(x)表示有限域 GF（24）上的任意4次多項式，μ(x)在保證與m(x)互素的原則下任意選擇，v(x)為仿射常量，保證變換過程中不存在不動點與反不動點。

根據近世代數相關知識可知伽羅瓦域GF（24）上僅存在3個不可約多項式，分別為:x4+x+1、x4+x3+1和x4+x3+x2+x+1。分別求出其各自對應狀態字[0123456789 A B C D E F]的逆元:

其中，括號里使用狀態字的16進制來表示即可得到(X-1)的值。

μ(x)可通過一個矩陣U來表示，由于S盒為4×4 S盒，因此令 U=[U3U2U1U0]，則:

關于仿射常量v(x)=[v3v2v1v0]，則保證變換過程不存在不動點和反不動點，即S(x)=x和S(x)=。

最后可得出S盒的輸出如下:

通過對伽羅瓦域GF(24)上3個不可約多項式下的m(x)、μ(x)以及v(x)進行窮舉測試可得出4000多個S盒，其中除去不包含不動點以及反不動點的S盒，剩余約有600多個，然而并不是這600多個S盒的密碼學性能都可以達到最佳，通過以下分析可以得到若干組{m(x)、μ(x)、v(x)}，以生成最佳S盒。

由于消除不動點與反不動點時引入的仿射常量v(x)不影響S盒的密碼學特性，所以由式(8)可知決定S盒性能的參數為 U 矩陣，即 m(x)和 μ(x)，m(x)表示有限域 GF(24)上的任意4次多項式，μ(x)與m(x)互素，由此可知m(x)的選擇至關重要，m(x)可取 x4+1、x4+x、x4+x2、x4+x3、x4+x2+1、x4+x2+x、x4+x3+x2、x4+x3+1、x4+x3+x、x4+x3+x2+1、x4+x3+x2+x、x4+x2+x+1、x4+x3+x+1、x4+x3+x2+x+1。

定義1 在矩陣U中，若每行每列非零個數均相同，則稱為均勻U矩陣。

對于上述多項式m（x），可將其分為不可約多項式、只含一個因子的多項式以及含多個因子的多項式。當m（x）為不可約多項式時，μ（x）可取任何一個多項式均與其互素。根據式（3）可知不存在一個μ（x）使得U矩陣為均勻矩陣。當m（x）為只含一個因子的多項式時，很容易得出該因子為 x+1，對應的 m（x）為 x4+1，此時，當取 m（x）與 μ（x）互素的多項式時，得到的U矩陣均為均勻矩陣。當m（x）為含有多個因子的多項式時，與μ（x）生成的U矩陣不存在均勻陣。

證明 當時m(x)=x4+1，由式(3)可知，Ui多項式可表示

所以m=x4+1時，可以發現如下規律:不同μ(x)生成的均勻矩陣與各狀態字的逆元相乘之后得到的矩陣中每一行均為任意3個各不相同的狀態字的模2和。而m(x)取其他多項式時并不存在該規律（此處略去證明部分），由此為尋找最優S盒提供了途徑。通過對該m(x)以及所有與之互素的μ(x)進行窮舉分析，構造出了雪崩效應以及代數次數最佳的S盒。

3.2 SOPT-S盒構造過程

（1）以不可約多項式為例進行S盒的構造。

取m(x)=x4+1，這時，與m(x)互素的多項式μ(x)分別為:

通過計算，仿射常量v(x)可取:v(x)=x2+x+1和v(x)=x，即 v(x)=[0111]和 v(x)=[0010]。現以 m(x)=x4+1、μ(x)=x2+x+1、v(x)=x2+x+1為例進行上述仿射變換可得:

根據式（6）求得S盒，見表1。

表1 SOPT-S盒

當然以上只是選擇所有的{m(x)、μ(x)、v(x)}對中的一例進行 S 盒的構造，以下列出上述所有的{m(x)、μ(x)、v(x)}對以生成最佳S盒（包括上文已構造）。

（2）當不可約多項式取剩余兩個多項式時，雖然一些密碼學特性像非線性度以及差分均勻度與上述不可約多項式相同，然而對于雪崩概率以及代數次數并不能達到最佳，不能構成性能最佳的S盒，因此不做深究。

4 SOPT-S盒密碼學性能

結合第1節給出的輕量級S盒設計準則以及第2節構造出的SOPT-S盒，本節將在對其密碼學性能進行詳細分析的同時，與現有典型的輕量級加密算法PRESENT非線性層中所使用的S盒進行對比，其中包括非線性度、差分均勻性和差分分布表、雪崩效應和雪崩概率、代數次數。

4.1 非線性度對比

非線性度決定了密碼算法抵抗線性分析的能力，根據第1節中對于非線性的描述以及參考文獻[9,10]的研究可知，假設 F(x):GF(2)n→GF(2)n，則非線性度為:

PRESENT中的S盒以及SOPT-S盒的非線性度進行求解可得如下結果:

其中，非線性度上界為 。結果表明，SOPT-S盒與PRESENT-S盒均具有較好的非線性度。

4.2 差分均勻性對比

較小的差分均勻度δ是S盒抗擊差分密碼分析的必要條件。由于差分均勻度可用差分分布表來反映，在此計算出了SOPT-S盒的差分分布，見表2。

其中，Δ(x)表示輸入差分，Δ(y)表示輸出差分，Δ代表了差分特征值，表1、表2均反映了當輸入差分取0～F時對應的輸出差分分別取0～F的個數，即差分特征數。

通過對表2進行分析可以看出:SOPT-S盒差分分布中每一行（除Δ(x)=0行）最高差分輸出個數為4，滿足上文提到的差分4-一致性，并且每行均有7個差分輸出Δ(y)非0，同時第一列不包含非0元素，分布均勻。PRESENT-S盒雖然也滿足差分4-一致性，但是大多數行分布都不均勻，存在包含1個以上差分輸出個數為4的行，導致每行含0個數過多。其中第4行（Δ(x)=1）以及最后一行（Δ(x)=F）差分輸出非零的個數僅為4個，非0個數最少。此外，當wt(ΔI)=wt(ΔO)=1時，差分輸出的個數全部為 0，所以容易受到差分攻擊。參考文獻[11]對于其S盒的分析中同樣可以看出，雖然滿足其構造條件可以提高雪崩效應，但是并不能有效地抵抗差分攻擊，因為當輸入輸出漢明距離等于1時，差分分布表中對應項為0，所以使得差分分布不均勻，導致了有差分攻擊的可能性。總之，SOPT-S盒在差分均勻性這一指標上優于PRESENT-S盒，可以更好地抵抗差分攻擊。

4.3 雪崩效應對比

S盒雪崩效應的優劣可以通過雪崩概率來度量，即改變輸入的1 bit，輸出比特改變的概率。當雪崩概率為1/2時，滿足嚴格雪崩準則（SAC），此時雪崩效應為最理想[1]。表3和表4分別給出本文構造S盒的雪崩概率以及PRESENT-S盒的雪崩概率。

表2 SOPT-S盒差分分布

表3 SOPT-S盒雪崩概率

表4 PRESENT-S盒雪崩概率

其中，0001到1000分別表示從最低位到最高位進行取補運算，S1～S4表示S盒對應位改變的概率。

通過對比可以看出，SOPT-S盒雪崩概率值均為1/2，滿足嚴格雪崩準則的條件。而PRESENT中S盒的雪崩概率值不全為1/2，其中包括了1、3/4以及1/2。由此表明，SOPT-S盒在雪崩效應指標上明顯優于PRESENT的S盒，可以更快地將輸入擴散到整個S盒中繼而輸出。

4.4 代數次數及項數對比

根據參考文獻[10]，4×4 S盒可以表示為有限域GF(2)上4 個布爾函數 :Sbox(x0,…,x3)=(f0(x0,…,x3),…,f3(x0,…,x3))，更進一步講，S盒可由4個只含and和xor邏輯符號的布爾方程 fi(x0,…,x3)(0≤i≤3)表示:

其中，aj(i)∈{0,1}是待確定的系數。據此可以確定SOPT-S盒布爾方程及其代數次數:

代數次數 D(f0)=3，D(f1)=3，D(f2)=3，D(f3)=3。

PRESENT-S盒布爾方程以及代數次數為:

代數次數 D(f0)=3，D(f1)=3，D(f2)=3，D(f3)=2。

將式（9）、式（10）兩組方程進行對比整理，可得表 5。

表5 結果對比

可以看出:SOPT-S盒4個布爾方程的代數次數全部達到了最佳 （n-1），同時方程項數越多，方程越復雜。而PRESENT-S盒代數次數沒有全部達到最佳，最后一個布爾方程沒有3次項，并且方程項數較少。因此，SOPT-S盒代數次數及項數分布指標也要優于PRESENT-S盒，可以更好地抵抗線性攻擊和其他有關攻擊。

將SOPT-S盒與PRESENT-S盒以上密碼學特性進行總體上的對比，見表6。

表6從整體上反映出SOPT-S盒以及PRESENT-S盒的密碼學性能，可以看出SOPT-S盒在雪崩效應以及代數次數兩個指標上達到最佳值，非線性度和差分均勻度也保持與PRESENT-S盒性能相當，從而為輕量級加密算法的設計提供了有力的支撐，進而在戰場上利用傳感網節點能高效、快速地對獲得的第一手信息進行加密，保證了信息不會暴露而是安全地傳遞。

4.5 與其他最優S盒對比

雖然現有的參考文獻中提出了許多非線性最佳或者雪崩效率達到最佳即SAC的S盒，但只是在某一種密碼學特性中表現最優，輕量級加密的設計需要對S盒的多個因素綜合考慮，才能保證算法不被某一種攻擊所攻破。參考文獻[9]中提到，當函數的非線性為第1.1節介紹的Bent函數時，雖然非線性度達到最大，但是該函數并不是一個平衡函數 （不能構成S盒）并且代數次數不超過 D/2。參考文獻[12]基于 APN（almost perfect nonlinear）函數構造了一種APN S盒，APN函數是有限域GF(24)上差分性質很好的非線性函數，APN S盒滿足差分2-一致性，它在抵抗差分密碼攻擊以及線性密碼攻擊時最有效[13]。然而，APN S盒的構造要求函數必須為APN置換函數，滿足這一條件同時執行變量n為偶數的APN函數并不存在。Dillon在參考文獻[14]中構造出了分組密碼執行變量為偶數（n=6）的APN多項式置換函數，滿足差分2-一致性條件同時非線性達到了上界 ，但是n為6的S盒不滿足構造輕量級S盒的要求。基于以上問題，本文構造的S盒在非線性度以及差分均勻度上取了折中，雖然未達到最佳值，但是在S盒的設計上遵循了輕量級的設計思路，同時在其他特性上達到了最佳，構造的次最優S盒很大程度上節省了硬件空間，適用于傳感器節點的加密環境。

5 結束語

無線傳感網的飛速發展帶給傳感器節點信息安全越來越大的沖擊，傳感器節點的信息加密已成為共同關注的話題，建立一個良好的信息加密體系對于城市管控、個人隱私、金融貿易，尤其在軍事領域中有著重大的意義。然而節點在這種特殊的環境下完成加密任務對于加密算法的要求極為苛刻，不僅要保證S盒具有優良的密碼學特性以滿足算法的安全性和頑健性，還要保證S盒占有較小的硬件空間，從而實現算法的高效性。考慮到現有輕量級算法存在的一些問題，國家高技術研究發展計劃（“863”計劃）也將其作為研究的內容之一，可以說明研究輕量級加密算法S盒構造的必要性。本文基于有限域的逆映射構造出一類性能優良的S盒，并對其密碼學性能進行了分析測試，與現在流行的加密算法PRESENT中的S盒相比，該S盒有著更好的密碼學性能，其中雪崩效應以及代數次數均達到了最佳，同時在硬件實現方面，差分均勻度也與PRESENT-S盒占有的硬件開銷相等，為輕量級加密算法中分組密碼的非線性層設計提供了一種參考。對于未來輕量級S盒的研究，應著眼于尋找規模小，硬件（FPGA）實現簡單，不僅可以很好地抵抗傳統密碼分析，而且對于擴展性的分析，如差分分析中的差分能量分析也具有較好的抵抗力。同時，從整個輕量級加密算法來看，對于非線性層與線性層二者的結合也是研究的一個方向。

表6 整體性能對比

1 Feng D G,Wu W L.Design and Analysis of Block Cipher.Beijing:Tsinghua University Press,2000

2 Eisenbarth T,Paar C,Poschmann A,et al.A survey of lightweight-cryptography implementations.IEEE Circuits and Systems Society,2007(6)

3 Bogdanov A A,Knudsen L R,Leander G,et al.PRESENT:an ultra-lightweight block cipher.Proceedings of CHES 2007,Vienna,Austria,2007

4 Guo J,Peyrin T,Poschmann A,et al.The LED block cipher.Procedings of 13th International Workshop,Nara,Japan,2011:326～341

5 Wu W L,ZhangL.LBlock:alight weight block cipher.Proceedings of ACNS 2011,Nerja,Spain,2011:327～344

6 Gong Z,Nikova S,Law Y W.KLEIN:a new family of lightweight block ciphers.Proceedings ofRFIDSec 2011,Amherst,Massachusetts,USA,2011

7 Khoo K,Gong G.Highly nonlinear S-boxes with reduced bound on maximum correlation.Proceedings of IEEE International Symposium,Paris,France,2004

8 Qu L J,Tan Y,Tan C H,et al.Constructing differentially 4-uniform permutations over via the switching method.IEEE Transactions on Information Theory,2013(7)

9 Leander G,Poschmann A.On the classification of 4 bit S-boxes.Proceedings of Ari thmetic of Finite Fields,First International Workshop,WAIFI 2007,Madrid,Spain,2007

10 Gligoroski D,Elisabeth G M M.On deviations of the AES S-box when represented as vector valued boolean function.IJCSNS International Journal of Computer Science and Network Security,2007(4)

11 AlDabbagh S S M,Shaikhli I F T A.Security of PRESENT S-box.International Conference on Advanced Computer Science Applications and Technologies,Kuala Lumpur,Malaysia,2012

12 Fu M F.Research of block cipher S-box based on APN permutation.Network and Computer Security,2012(10)

13 Budaghyan L,Carlet C,Leander G.Constructing new APN functions from known ones.Finite Fields and Applications,2008（2）

14 Dillon J.APN Polynomials:An Update.International Conference Finite Fields and Their Applications,2009