基于L-M-NFSR結構的16比特S盒設計方法

武小年，舒 瑞，豆道饒，張潤蓮，韋永壯

桂林電子科技大學 廣西密碼學與信息安全重點實驗室，廣西 桂林 541004

S盒是分組密碼算法的重要組成部件，為密碼算法提供非線性變換，增加必要的混淆特性。S盒最早出現在Lucifer 算法中，隨后被廣泛推廣使用。在目前針對分組密碼算法的攻擊中，大多攻擊都是針對其S盒的攻擊。研究并設計強安全的S盒，有效抵抗各種攻擊威脅，以增強分組密碼算法的安全性是密碼算法設計研究的關鍵。

多年來，在對S 盒的研究中，逐步形成了構造S盒的一些主要方法，包括數學方法構造、利用密碼結構構造和基于計算智能算法構造等。在理論研究和實際應用中，基于上述方法，研究者們已經構造了各種強密碼學性質的S盒，包括4/5/6/8/16/32/64比特的S 盒。目前，針對4/8 比特S 盒的研究工作較多。早在2007 年，Leander 等[1]提出最優S 盒的概念，對S 盒的性質進行分析總結。2011年，Saarinen展示了所有4比特S盒的置換等價類[2]；Ullrich等[3]將便于硬件實現的4 比特S 盒劃分為302 個仿射等價類。2015 年，Canteaut 等[4]利用Feistel 和MISTY 結構設計S 盒；Cheng 等[5]提出一種4 比特雙射S 盒的置換等價類改進搜索算法，性能較2011年Saarinen等提出的算法大大提升。2016 年，Perrin 等[6]基于蝴蝶結構設計S盒。2017年，Kapu?ciński等[7]將多目標遺傳算法用于S盒。2018年，Ghoshal等[8]通過使用重復迭代簡單的元胞自動機規則構建最優4比特S盒，并優化其實現面積和功耗成本。2019年，Mishra等[9]以監督機器學習的輔助自動化框架解決S 盒設計與分析問題；Zahid等[10]提出使用三次多項式映射生成8比特S盒，其構造的S盒非線性度的最大值為108。2020年，張潤蓮等[11]在文獻[8]的基礎上，采用變元分量部分固定和分別搜索的策略，提出搜索4 比特S 盒的新方法；黃俊君等[12]提出基于元胞自動機（cellular automata，CA）設計的S盒的鏡面對稱性、互補性以及移位不變性三個性質并進行證明，進一步提出一種權重閾值搜索算法實現對4元布爾函數的有效搜索；Wang等[13]將n比特S 盒的構造看作將n個布爾函數放入容器的過程，其將布爾函數作為組成S 盒的染色體，提出一種新的遺傳算法，以S 盒的非線性為優化目標，以雙射性為優化約束，并以此設計遺傳算法的交叉和變異算子，構造高非線性度的雙射S 盒。2021 年，Kim等[14]使用較小的S盒，利用非平衡MISTY結構和非平衡Bridge結構構造了差分分支數（difference branch number，DBA）和線性分支數（linear branch number，LBN）至少為3的8比特S盒，且其能高效地實現比特切片。

相對于4/8比特S盒，16/32/64比特S盒的輸入輸出位數較高，如一個完整的16 比特S 盒實例實質上是0 到216-1 的排列組合，其復雜程度明顯提高。在保證S盒優良密碼學性質基礎上，這類高比特S盒的復雜度大大提升，其抵抗攻擊的能力也會相應增強，但目前這類S 盒的研究工作并不太多。2011 年，Piccolo 算法[15]采用了SPS（substitution permutation substitution）結構利用4個并置的輕量級4比特S盒與MDS（maximum distance separable）矩陣組合充當16比特S盒；類似的，在2019年的美國國家標準與技術研究院（National Institute of Standards and Technology，NIST）第二輪算法Saturnin[16]中，同樣使用4個4比特置換S盒基于SPS結構充當16比特S盒。2019年，徐洪等[17]在NBC算法中，基于含有4個狀態更新函數的16 級非線性反饋移位寄存器（nonlinear feedback shift register，NFSR）迭代20拍構造出16比特S盒；田甜等[18]在SPRING 算法中，使用NFSR-SR 迭代20 輪或者32 輪實現對32 比特S 盒的構造，但由于S 盒的復雜度較高，僅計算出S盒的最大差分概率為20/231。2020 年，Beierle 等[19]基于And、Rotation、XOR 操作通過8輪迭代設計一個構造64比特S盒的Alzette結構，并對其安全性指標的上下界進行了分析，其迭代一次的差分性質與線性特性與AES（advanced encryption standard）相當，迭代兩次其安全性與AES 超級S盒相同。

本文將Lai-Massey結構與NFSR組件相結合，設計一個三輪迭代的L-M-NFSR 結構，構造16 比特S盒。在L-M-NFSR結構中，在左右分支各增加一個迭代少量拍數即可符合嚴格雪崩特性的NFSR 組件用于提高結構的擴散性，以具有優良密碼學性質的AES算法8比特S盒通過仿射等價構造一個樣本集，并從中選擇3 個8 比特S 盒作為輪函數，最后通過遍歷搜索生成16比特S盒，并采用圖形處理器（graphics processing unit，GPU）進行并行計算，評估所生成S盒的差分均勻度、非線性度、信噪比、代數次數等密碼性質。測試結果表明基于L-M-NFSR 結構可以生成性質優良的16比特S盒。

1 基于L-M-NFSR結構的16比特S盒構造

16比特密碼S盒的輸入輸出位數較高，一個完整的16比特S盒實例實質上是0到216-1的一種排列組合，復雜度明顯高于4/8 比特S 盒。由于16 比特S 盒的分量布爾函數的多項式復雜，使用數學方法或智能算法構造較困難，本文將以Lai-Massey 結構和NFSR組件相結合構造16比特S盒。

1.1 L-M-NFSR結構的設計

Lai-Massey密碼結構也稱為L-M結構，是典型的迭代分組密碼結構，該結構源自IDEA（international data encryption algorithm）算法，隨后由Vaudenay[20]在1999年從IDEA算法中抽象出Lai-Massey模型，該結構架構簡潔，在軟件實現多拍迭代時較為容易。利用Lai-Massey 設計加密算法時，輪函數的設計是關鍵，簡單的輪函數抵御各種攻擊的能力較差，而復雜的輪函數往往構造困難并增加實現的復雜性。本方案中，擬采用具有優良密碼性質的AES算法8比特S盒仿射等價構造的8比特S盒作為輪函數。

為了提高Lai-Massey結構的擴散性和混淆性，在結構的左右分支中添加NFSR組件參與運算。NFSR常被用于流密碼中作為密鑰產生器，具有結構簡單、易于實現、狀態函數更新靈活的優勢。添加的NFSR組件都能夠在迭代多拍之后達到嚴格雪崩特性，為新結構搜索16比特S盒提供更好的擴散性支持。新的L-M-NFSR結構如圖1所示。

圖1 L-M-NFSR結構圖Fig.1 L-M-NFSR structure diagram

L-M-NFSR結構是一個平衡的二分支結構，迭代輪數為3 輪。針對Lai-Massey 結構的安全性的研究較多，其安全性的高低取決于輪函數的設計是否性質優良，如Vaudenay曾證明出當函數為偽隨機函數，并滿足雙射變換σ是α-的近乎正型函數時，此時3輪的Lai-Massey 結構是安全的，當達到4 輪時，該結構甚至在選擇密文分析的情況下仍然是安全的[20]；2010 年，Luo 等[21]證明出該結構在3 輪時就已經達到偽隨機特性，在4輪時可以達到超偽隨機特性。輪數的增加會提高整體結構的安全性，但此時整體結構的算法實現也會變得更加復雜。因此，L-M-NFSR結構的迭代輪數被設定為3輪。

輪函數采用8比特S盒替代，在此以密碼性質優良的AES 算法的8 比特S 盒作為樣本通過仿射等價構造出一批具有同樣優良性質的8 比特S 盒樣本集。樣本集中的8比特S盒都具有雙射性，非線性度為112，差分均勻度為4，代數次數為7。這些S 盒作為輪函數，可以為16 比特S 盒的構造提供良好的非線性以及差分均勻性支持。同時，通過替換這些被選擇作為輪函數的8比特S盒，可以方便地構造出新的16 比特S 盒，增加了部件的可變性，結構變換靈活，在實際應用中也更加安全。

在圖1中，以L和R表示左右兩分支的8比特輸入，L,R∈；L′和R′表示該結構左右兩個分支的8比特輸出，L′,R′∈；NFSR1和NFSR2為設計的兩個8 級非線性反饋移位寄存器；⊕表示異或運算；S0、S1、S2分別表示每一輪中采用的8 比特S 盒。NFSR1和NFSR2在結構第一輪中的計算結果分別以A1和B1表示，在結構第二輪計算中的結果分別以A2和B2表示，||表示連接符號，即結構左右兩個分支的輸出比特串首位相接，則L-M-NFSR結構的輸出函數SLMN(L,R)如式（1）：

1.2 NFSR結構設計

NFSR由異或運算和與運算構成，一個n級NFSR概念圖如圖2所示。

圖2 NFSR概念圖Fig.2 NFSR concept diagram

圖2 中，一個NFSR 由n個狀態寄存器和一個狀態反饋函數組成，每經過一個移位脈沖信號，寄存器中的所有位向右移動，最右邊那一位移出，而反饋函數f的結果反饋到寄存器最左邊的存儲單元中，按此過程循環。其中，寄存器狀態xi的取值為0 或者1，其隨著寄存器每一輪的計算不斷更新。

在NFSR結構中，若狀態更新函數含有異或運算和與運算，則該反饋移位寄存器是非線性的；若只有異或操作，則反饋移位寄存器是線性的。為保證圖1中NFSR組件的非線性，設計時定義狀態更新函數包含與運算。為獲得迭代少量拍數即可達到嚴格雪崩特性的NFSR 組件，嘗試在每一輪的迭代前，先取其中兩個位置進行與操作，然后判斷其非線性性質，這確保設計的NFSR 組件中都有2 個狀態更新函數包含了異或運算和與運算，從而使得NFSR 組件可以每迭代一拍就會以非線性的方式完成寄存器狀態的更新。

具體地，為構造圖1 中的兩個NFSR 組件，設置每個NFSR組件有8個狀態寄存器，以表示寄存器迭代前的某個比特位狀態，以表示寄存器迭代后的比特位狀態；⊕表示異或運算，?表示與運算。通過多次測試，確定了兩個符合要求的NFSR 組件，每個NFSR 組件設置了4 個狀態更新函數，其更新位置分別為，其結構如圖3所示。

圖3 NFSR1結構圖Fig.3 NFSR1 structure diagram

NFSR1狀態更新函數如式（2）：

為簡化NFSR2的設計，對NFSR1的兩個位置的狀態更新函數進行更改，NFSR2的具體結構如圖4所示。

圖4 NFSR2結構圖Fig.4 NFSR2 structure diagram

NFSR2狀態更新函數如式（3）：

在迭代至10拍時，NFSR1符合嚴格雪崩準則，雪崩效應程度能夠達到n/2，即4；迭代至23 拍時，NFSR2也符合嚴格雪崩準則。

1.3 16比特S盒搜索過程

在L-M-NFSR結構中，使用了3個8比特S盒、兩個NFSR 組件，再通過遍歷左右兩個分支輸入數據，構造出16 比特S 盒。針對基于L-M-NFSR 結構搜索16比特S盒的搜索過程如算法1所示。

算法1基于L-M-NFSR結構生成S盒流程

輸入：基于AES 算法S 盒仿射等價構造的8 比特S 盒樣本集SBox8，Sbox8 中S盒的個數n。

輸出：生成的16比特S盒txt文件。

基于L-M-NFSR 結構生成的16 比特S 盒的數量取決于所構造8比特S盒樣本集的大小，假設8比特S盒樣本集的大小為n，則基于該方法可搜索出n3個16比特S盒。

2 測試結果及分析

2.1 測試環境

在計算機處理器為Intel?CoreTMi5-4210U，主頻1.70 GHz，RAM為8 GB，操作系統為64位Windows 10專業版環境下，先采用Java語言實現對AES算法S盒的仿射等價，產生一批8比特S盒樣本集；再采用Java實現基于L-M-NFSR結構的16比特S盒搜索算法，生成一批16比特S盒。

為評估S 盒的密碼學性質，測試所生成的16 比特S 盒是否滿足雙射性，并測試其差分均勻度、非線性度、信噪比、代數次數。由于計算16比特S盒的非線性度、差分均勻度等性質的復雜度較高，采用常用CPU 計算方式耗時較長，在此采用GPU 技術進行并行計算，大大縮短各個性質的計算時間，提高測試效率。

2.2 S盒性質測試及分析

在S盒構造中，8比特S盒樣本集共放置了7個性質優良的8 比特S 盒，最終生成了343 個16 比特S盒。盡管采用GPU 技術提高了測試效率，但其密碼學性質計算仍然耗時較長，如一個16 比特S 盒的非線性度計算還需要3天。在此只選取前256個S盒進行測試，測試結果表明這些S 盒都滿足雙射性，其他性質的測試結果如表1所示。

表1 16比特S盒性質測試的上下限Table 1 Upper and lower limits of 16-bit S-box

差分攻擊在密碼算法攻擊中具有極強的威脅性，而防御差分攻擊的能力與密碼算法使用的S盒息息相關。差分均勻度是評估S 盒能否抵御差分攻擊的一個重要指標，S 盒的差分分布越均勻，差分均勻度越小，其抵抗差分攻擊的可能性就越高。256 個S盒的差分均勻度最大為22，最小為18，差分均勻度散點圖如圖5所示。

圖5 S盒的差分均勻度散點圖Fig.5 S-box differential uniformity scatterplot

非線性度用于檢驗S 盒抵抗線性攻擊的能力，S盒的非線性度越高，或者線性度越小，則有效抵御線性攻擊的能力越強。256個S盒的非線性度值最高為31 992，所有S盒的非線性度散點圖如圖6所示。

圖6 S盒的非線性度散點圖Fig.6 S-box nonlinearity scatterplot

側信道攻擊通過采集密碼算法運行過程中泄漏的側信息進行分析，從物理層面實現對密碼算法的攻擊，常用方法有差分功耗分析（differential power analysis，DPA）、相關功耗分析（correlation power analysis，CPA）等。信噪比（signal-to-noise ratio，SNR）在2004 年CARDIS 會議上由Guilley 等[22]提出，是根據傳統密碼分析框架對信息泄露進行完整建模，獲取密鑰猜測值的漢明重量的自相關值，其具體定義如下：對于n比特的S盒函數S是的映射布爾函數，其信噪比為：

其中，fiw(a)表示構成S 盒的分量布爾函數fi(x)的Walsh 譜變換，i=0,1,…,n-1。信噪比模型和定義表明，非線性S盒的噪聲對密碼算法的DPA信號起著決定性作用，S 盒的信噪比越低，其抵抗DPA 攻擊的能力越強。對所生成的256 個S 盒的信噪比計算發現，其大多低于148，散點圖如圖7所示。

圖7 S盒的信噪比散點圖Fig.7 S-box signal-to-noise ratio scatterplot

代數次數是評估S盒抵抗插值攻擊、立方攻擊等代數攻擊的評估指標，這256個16比特S盒的代數次數均達到最優15。

2.3 NFSR對L-M-NFSR結構的影響分析

NFSR 組件的加入，增加了L-M-NFSR 結構實現的成本開銷，但其優化了所生成S 盒的密碼學性質。為評估其對S盒性質的影響，去掉L-M-NFSR結構中的NFSR組件，其結構如圖8所示。

圖8 去掉NFSR組件的L-M-NFSR結構圖Fig.8 L-M-NFSR structure diagram without NFSR components

基于圖8，按照上述搜索方法生成16 比特S 盒，并測試其差分均勻度，這些S盒的差分均勻度散點圖如圖9所示。

圖9 去掉NFSR后生成的S盒的差分均勻度散點圖Fig.9 Scatterplot of differential uniformity of S-boxes without NFSR components

由圖9 可看出，在去掉NFSR 組件后，所生成16比特S 盒的差分均勻度非常高，其差分特性很差，不能抵抗差分攻擊。圖5結果表明，在加入了兩個符合嚴格雪崩準則的NFSR組件之后，其差分均勻度得到極大優化，最高僅為22。

2.4 S盒性質對比分析

目前16 比特S 盒的構造方法，主要有Piccolo 和Saturnin 算法中使用的SPS 結構16 比特S 盒，以及NBC算法中使用16級NFSR構造16比特S盒。NBC算法入選全國密碼算法設計競賽分組算法第二輪，該算法在抵抗線性、差分、積分分析等方面具有較高的安全性，其在測試中給出了S 盒的線性度、差分均勻度以及代數次數等性質的具體結果。基于上述同樣的實驗環境，測試了Piccolo、Saturnin 和NBC 算法S 盒的相關性質，并與本文方法構造的3 個S 盒SLMN1、SLMN2 和SLMN3 的測試結果列舉如表2所示。

表2 不同方法構造的S盒性質測試結果Table 2 Properties results of S-box constructed by different methods

由表2 可知，Piccolo 和Saturnin 算法中的S 盒代數次數僅為9，其他性質也都較弱。NBC算法S盒和本文構造的16 比特S 盒的代數次數都達到最優15，其他相關性質都明顯增強。Piccolo 和Saturnin 算法中的S 盒都是采用4 比特S 盒基于SPS 結構與MDS矩陣組合充當16 比特S 盒，其硬件實現成本較高。NBC 算法S 盒采用NFSR 構造，其實現比較簡單，硬件成本較低。本文基于L-M-NFSR結構所構造的16比特S 盒，其密碼學性質稍優于NBC 算法S 盒，但在S 盒的具體實現中，由于采用了8 比特S 盒提供混淆特性，其硬件實現成本高于NBC 算法S 盒。盡管NBC 算法S 盒實現的硬件成本較低，但其需要迭代20 輪才能達到最優的密碼學性質，而本文方法只需迭代1 輪，實現速度更快。此外，本文方法的可變性強，通過更換8比特S盒可以快速構造出許多新的性質較優的16比特S盒。

3 結束語

本文將Lai-Massey結構與NFSR組件相結合，構造一種新的L-M-NFSR結構，以AES算法S盒進行仿射等價獲得的8比特S盒作為新結構中的輪函數，左右分支增加NFSR 組件，通過3 輪迭代和遍歷搜索，構造出16 比特S 盒。為提高對所構造S 盒性質的評估效率，采用GPU技術進行并行計算，測試S盒的差分均勻度、非線性度、信噪比等。測試結果表明，本文方法構造的16 比特S 盒具有較優的差分均勻度、非線性度和信噪比，具有一定的抵御數學攻擊和差分功耗攻擊的能力。今后的工作中，考慮進一步優化結構，降低實現成本。