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

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

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

1 引言

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

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

2 預備知識

S盒概念首次出現(xiàn)在Lucifer算法中并隨之廣泛應(yīng)用于DES、AES等許多密碼算法[7]，其設(shè)計要求是構(gòu)造一個性能優(yōu)良的S盒首先需要考慮的問題。

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

（1）非線性度

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

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

（2）差分均勻性

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

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

（3）雪崩效應(yīng)

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

（4）代數(shù)次數(shù)及項數(shù)分布

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

3 SOPT-S盒的構(gòu)造

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

3.1 SOPT-S盒構(gòu)造方法

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

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

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

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

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

關(guān)于仿射常量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盒性能的參數(shù)為 U 矩陣，即 m(x)和 μ(x)，m(x)表示有限域 GF(24)上的任意4次多項式，μ(x)與m(x)互素，由此可知m(x)的選擇至關(guān)重要，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中，若每行每列非零個數(shù)均相同，則稱為均勻U矩陣。

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

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

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

3.2 SOPT-S盒構(gòu)造過程

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

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

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

根據(jù)式（6）求得S盒，見表1。

表1 SOPT-S盒

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

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

4 SOPT-S盒密碼學性能

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

4.1 非線性度對比

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

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

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

4.2 差分均勻性對比

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

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

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

4.3 雪崩效應(yīng)對比

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

表2 SOPT-S盒差分分布

表3 SOPT-S盒雪崩概率

表4 PRESENT-S盒雪崩概率

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

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

4.4 代數(shù)次數(shù)及項數(shù)對比

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

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

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

PRESENT-S盒布爾方程以及代數(shù)次數(shù)為:

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

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

表5 結(jié)果對比

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

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

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

4.5 與其他最優(yōu)S盒對比

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

5 結(jié)束語

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

表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