（1.信息工程大學密碼工程學院，河南 鄭州 450001；2.國家密碼管理局，北京 100036）
0 引言
非線性編碼是分組密碼算法的主要模塊，混淆性能較好的非線性編碼設計是分組密碼算法研究的重要內容。目前，常用的非線性編碼為S 盒，它是分組密碼算法的關鍵部件，主要提供算法所必需的混淆作用，其密碼強度直接影響整個密碼算法的安全強度。尤其是大規模S 盒，其極大地提高了非線性編碼的線性度和差分均勻度，可以在較少的輪數內使分組密碼達到抵抗差分分析和線性分析的安全界。
大規模S 盒一般是由小規模S 盒通過某種結合規則滿足一定的約束條件構造的，可分為以下4 種情形。第一種情形是利用密碼學結構如MISTY、Feistel 或直接由小規模S 盒并置構造大規模S 盒，基于3 輪平衡Feistel 結構[1-2]、3 輪Lai-Massey 結構[3]及3 輪MISTY 結構[4]構造大規模S 盒，可使S 盒密碼性質適中并減少硬件資源占用。其中，MISTY[5]使用2 個9 bit 置換與一個7 bit 置換，使用3 輪MISTY 結構構造16 bit 大規模S 盒，再使用3 輪MISTY 結構構造32 bit 非線性置換，這種嵌套結構可提高整個非線性環節的密碼學性質，但需合理選擇內嵌的非線性函數。文獻[6]提出一種新的8 bit 輕量化S 盒設計方法，其單輪邏輯運算僅涉及4個單比特邏輯與運算和4個單比特邏輯異或運算，迭代4輪后密碼性質可達到差分均勻度為16、非線性度為96，分量函數的代數次數能達到6 且整體平衡。NUX[7]直接使用4 個4 bit 置換并置合成16 bit S 盒，這種構造方式適合輕量級密碼設計，但不能提高S 盒的密碼學性質。第二種情形是基于SPS 結構構造。Piccolo 算法[8]采用了SPS 結構構造的16 bit S 盒，其中，小規模S 盒為4 bit，線性層為4×4 的有限域上的極大距離可分（MDS,maximum distance separable）矩陣，但是MDS 矩陣硬件實現占用資源多。第三種情形是基于非線性反饋移位寄存器（NFSR,nonlinear feedback shift register）直接構造，如CACR2019 密碼學會商用密碼征集算法中NBC 算法[9]基于16 級非線性移位寄存器構造的16 bit S 盒，以及SPRING 算法[10]中4 個8 bit寄存器互相反饋的環狀串聯結構構造的32 bit S 盒，但是這2 種方式構造的大規模S 盒分別需要迭代20輪或32 輪，硬件實現時延較大，而且32 bit S 盒目前仍難以完全刻畫其差分均勻度和非線性度等密碼性質。美國國家標準與技術研究院（NIST）發起輕量級密碼算法公開征集[11]，最終入圍算法中SPARKLE[12]及GIFT-COFB（combined feedback）[13]等算法均采用了32 bit 或者64 bit 大規模密碼S 盒。第四種情形是基于ARX 結構構造的大規模S 盒，2020 年美洲密碼會上，Christof 等[14]基于ARX 結構構造了64 bit S 盒Alzette，僅使用循環移位、異或及模232加基于4 輪平衡Feistel 結構構造64 bit S 盒，在現代CPU 上僅需12 條指令迭代兩次就可達到與AES 一樣安全，不過由于64 bit S 盒規模較大，其密碼學性質不易刻畫。因此，大規模S 盒構造不僅要合理選擇密碼結構，而且對S 盒的尺寸也有要求，即至少能有效刻畫其密碼學性質。
基于SPS 結構大規模S 盒的構造主要體現在線性擴散層P置換的設計上，P置換安全性設計指標主要是分支數，分支數反映了擴散變換的好壞，分支數越大，擴散變換效果越好。分支數與差分分析、線性分析密切相關，利用P置換的分支數，評估活躍S 盒數目的下界，從而量化分組密碼抵抗差分分析和線性分析的能力。近些年，分組密碼擴散層的研究成果非常豐富，主要有以下三類。1) 利用MDS碼構造最優擴散層。基于線性變換與線性碼的聯系，尋找較大分支數的線性變換，也就是尋找距離較大的線性碼，極大距離可分碼的分支數達到了最大值，其對應的MDS 矩陣是擴散層構造的較好選擇，AES[15]、FOX[3]等分組密碼都采用了MDS 擴散層。2) 利用MDBL（maximum distance binary linear）碼構造最優擴散層。MDBL 矩陣的分支數是二元域矩陣所能取到的最大可能值，與MDS 矩陣相比，MDBL 矩陣的擴散速度略慢，但由于不涉及有限域上的乘法，其硬件實現通常更加輕量化，而且MDBL 矩陣更加靈活，更易于適應各種平臺的優化實現，uBlock 分組密碼[16]采用了MDBL 擴散層。3) 利用具有良好數學性質的循環矩陣構造最優擴散層[17-18]。基于循環矩陣的構造策略被分組密碼廣泛采用，在循環矩陣中，任意行向量的每個元素都是前一行向量的各個元素依次右移一個位置的結果，從而使硬件實現復用乘法電路以節省硬件面積，利用循環矩陣可以非常靈活地在硬件面積和實現時延間進行折中。
基于SPS 結構構造的大規模S 盒作為分組密碼算法的非線性核心部件，不僅大幅提高了算法抵抗差分/線性密碼分析的攻擊能力，而且給算法整體結構采取何種性質的線性變換留下了很大的選擇空間。Donut[19]使用4 個8 bit 置換基于SPS 結構構造32 bit大規模S盒，線性變換P是基于4×4有限域上的MDS 矩陣；Saturnin[20]使用4 個4 bit 置換基于SPS 結構構造16 bit 大規模S 盒，4 bit 置換為最佳置換，線性變換P為4×4 有限域上的MDS 矩陣。但是，由于有限域上MDS 矩陣乘法運算的存在，硬件實現面積較大，導致傳統MDS 不適用于射頻識別（RFID）系統和傳感器網絡等資源受限的環境。為了解決這一問題，Sajadieh 等[21]基于線性反饋移位寄存器（LFSR）提出了迭代型MDS 矩陣擴散層的構造方式，在保證最優分支數的前提下，極大地節省了硬件實現面積。Wu 等[22]將矩陣元素擴充到多項式環上，利用不同類型的LFSR 結構設計輕量級最優擴散層。Augot 等[23]通過分析迭代矩陣的窮舉搜索結果，結合BCH 碼相關結論，提出了最優迭代擴散層的直接構造算法。除硬件實現面積之外，時延也是擴散層設計的一個重要參數。Li等[24-25]研究了低時延迭代型MDS 矩陣和對合MDS矩陣的構造。Guo 等[26-27]通過提取矩陣可逆的充要條件以及分支數等價的劃分原則，刻畫了逆矩陣的具體形式和基本特征，提出了循環移位異或型最優擴散層的構造算法。文獻[28]提出一種利用線性變換輸入與輸出關系反證得出分支數大小的普適方法，證明了一類由循環移位與異或運算構造的輕量級擴散變換是最優線性變換。
本文借鑒文獻[28]線性變換輸入輸出關系反證法的思想，提出將最優線性變換目標問題轉化為若干個遞進關系定理的證明方法，不僅解決了該類最優線性變換的證明，而且適用于任意線性變換的證明，并在此基礎上研究了2 輪SPS 結構的大規模S 盒構造問題。本文主要貢獻如下：基于循環移位與異或運算構造了有限域上分支數最佳的線性變換P，給出了該類最優線性變換的一種新的證明方法，建立了2 輪SPS 結構的大規模S 盒模型，通過小規模S 盒與最優循環移位-異或型矩陣，設計了一系列密碼學性質優良的輕量級大規模S 盒，與已有大規模S 盒構造方法相比，本文的大規模S 盒設計方案運算代價更加低廉，其差分、線性等密碼學性質更加優良。
1 基本概念及引理
定義7[30]對于2 個n×n階二元矩陣P和Q，如果存在一個行置換ρ和一個列置換γ，滿足ρ(γ(P))=γ(ρ(Q))=Q，則稱P和Q為置換同形矩陣。
引理1[30]若2 個n×n階二元矩陣P和Q是置換同形的，則P和Q具有相同的分支數，即Bd(P)=Bd（Q）。
引理2[29]假設分組密碼算法輪密鑰是隨機獨立均勻分布的，且與每輪的輸入數據按照逐比特異或運算。若線性擴散層的分支數為d，小部件S 盒的最大差分概率為p，則SPS 結構函數差分概率的上界為pd-1。
引理3[29]假設分組密碼算法輪密鑰是隨機獨立均勻分布的，且與每輪的輸入數據按照逐比特異或運算。若線性擴散層的分支數為d，小部件S 盒的最大線性概率為q，則SPS 結構函數線性概率的上界為qd-1。
定義8一般形式。設X∈()m，定義基于循環移位與異或運算的線性變換為
其中，0 ≤li＜li+1＜nm，1≤r≤nm。
引理4[31]線性變換L(X,m,n)是最優線性變換必須滿足以下2 個必要條件。
1)r為奇數且r≥m。
2) 至少存在m個li,滿足ni≤li＜n(i+1)，i= 0,1,…,m- 1。
2 一類最優循環移位-異或型線性變換的證明
本節根據第1 節給出的一般形式和必要條件，討論最簡形式下的最優循環移位-異或型線性變換，即最優線性變換中循環移位項數最少的形式。本節給出了輸入為 ()4擴散層中最簡形式下的最優線性變換，并對其中一種進行了詳細證明。
需證明所有ai,bi(i= 0,1,2,3)的非0 個數之和不小于5。下面分別討論a0,a1,a2,a3中至少有一個不為0 情況下A和B的非0 個數之和，也就是A的非0 個數分別為1、2、3、4 時上述線性擴散變換的分支數。從式(6)～式(9)可以看到，b0,b1,b2,b3的形式相似，所以分類討論時，從a0,a1,a2,a3中任意選取ai不為0 后會得到相似形式的b0,b1,b2,b3，所以不同ai的選取對證明過程不會產生影響。
3 SPS 結構大規模S 盒
2 輪SPS 結構大規模S 盒如圖1 所示。其基本思想如下：mnbit 輸入依次進入第一層混淆層、擴散層P和第二層混淆層，每個混淆層均由n個mbit小規模S 盒并置而成，該小規模S 盒均選擇相同的mbit S 盒，擴散層P是mnbit 規模的線性置換。P可看作上基于循環移位-異或型分支數最佳的線性變換。因此，本節主要研究循環移位-異或型最優線性變換。
圖1 2 輪SPS 結構大規模S 盒
3.1 16 bit 最優線性置換
令n=m=4，采用循環移位和異或運算組合操作構造線性置換P，使其差分和線性分支數達到最佳5。對于SPS 結構中使用的16 bit 線性置換P，可以統一表示為
根據定理6，當n=4、t=1 時，可得16 bit 最優線性變換P1(x)為
根據推論1，當n=4、t=3 時，可得16 bit 最優線性變換P2(x)為
由性質1 可知，對于線性置換P′，如果其循環移位數滿足=(ti+4)mod16,i= 1,2,…,5，則線性置換P和P′的分支數相同.
由性質2 可知，對于線性置換P′，如果其循環移位數滿足= (16 -ti)mod16,i= 1,2,…,5，則線性置換P和P′的分支數相同。
考慮到線性置換循環移位等價性質，與置換P1和P2等價的線性置換如表1 所示。
表1 線性置換P1 和P2 的等價類
基于此，小規模S 盒選用4 bit 置換，根據圖1描述的大規模S 盒模型可以構造一系列具有相同優良密碼學性質的16 bit S 盒。
3.2 32 bit/64 bit 最佳線性置換
32 bit/64 bit 最佳線性置換可由16 bit 最佳線性置換通過一定的規則變換得到，對于SPS 結構中使用的32 bit 線性置換P，可以統一表示為
定理7若兩類16 bit 最佳線性置換如式(10)和式(11)所示，該16 bit 最佳線性置換對應的循環移位-異或型矩陣為是一個MDS 矩陣，將式(10)和式(11)的循環移位數和模數分別擴大2 倍，則32 bit 最佳線性置換的2 個等價類分別為
同理，考慮到線性置換循環移位等價性質，與置換P3和P4等價的線性置換如表2 所示。
表2 線性置換P3 和P4 的等價類
根據線性置換循環移位數的等價性質，即=(ti+8)mod32,i=1,…,5，可知屬于相同等價類的線性置換構造的32 bit S 盒具有相同的最大差分和線性概率等密碼性質。小規模S盒選用8 bit置換，根據圖1 描述的大規模S 盒可以構造一系列具有相同優良密碼學性質的32 bit S 盒。
同理，考慮到線性置換循環移位等價性質，與置換P5和P6等價的線性置換如表3 所示。
表3 線性置換P5 和P6 的等價類
根據線性置換循環移位數的等價性質，即=(ti+16)mod64,i=1,…,5，可知屬于相同等價類的線性置換構造的64 bit S 盒具有相同的最大差分和線性概率等密碼性質。小規模S 盒選用3.1 節構造的16 bit 置換，根據圖1 描述的大規模S 盒可以構造一系列具有相同優良密碼學性質的64 bit S 盒。
4 實例分析
4.1 16 bit 大規模S 盒
對于線性變換P2(x) =x⊕ (x＜＜＜ 4) ⊕ (x＜＜＜7) ⊕ (x＜＜＜ 11) ⊕ (x＜＜＜15)，采用2 輪SPS 結構可以有效生成密碼學性質優良且實現代價低廉的16 bit S 盒。
1) 為便于與現有結果比較，采用與Piccolo 算法相同的 4 bit S 盒S={10,2,8,6,12,15,7,1,3,11,14,13,0,5,4,9}，使用線性置換P2(x)，按照圖1所示的SPS 結構構造16 bit S 盒S1，其密碼學性質如下：差分均勻度為Diff(S1)=96，最大差分概率為，線性度為Lin(S1)=3 200，最大線性概率為；硬件流水線實現時，P2(x)共需要4 個異或運算和4 個循環移位，由于比特之間的異或運算大約需要2 個邏輯門電路，而循環移位靠拉線實現，不占資源，一個4 bit S 盒大約需要 30 個邏輯門電路，因此共需要16×4×2+30×8=368 個邏輯門電路；軟件實現時，僅需要一次查表。
NBC 算法采用Galois 結構的16 級NFSR 構造16 bit S 盒S3，寄存器每迭代一拍，除常規移位外每拍以非線性方式更新4 bit，每拍有8 個異或運算，4 個與運算以及一個與非運算，共迭代20 拍。該16 bit S 盒S3的密碼學性質如下：差分均勻度為 Diff(S3)=22，最大差分概率為，線性度為Lin(S3)=3 144，最大線性概率為；硬件流水線實現時，S3共需要20×(8×2+4×1.25+1×1)=440 個邏輯門電路；軟件實現時，僅需要一次查表。
與有限域上的MDS 矩陣乘法運算及Galois 結構的16 級非線性移位寄存器運算相比，該類大規模S 盒的運算代價更加低廉，密碼學指標更優，密碼學性質對比如表4 所示。
表4 16 bit S 盒S1、S2 及S3 密碼學性質對比
2) 通過挑選4 bit 最優S 盒，結合上述線性置換P2(x)，可以構造密碼學性質更優的16 bit S 盒。考慮到差分和線性性質達到最優4 bit S 盒分別屬于16 個仿射等價類[32]，通過在這些最優4 bit S 盒等價類代表元中選擇S 盒進行測試，得到一系列16 bit S 盒。其構造參數及密碼性質如表5 所示。
由表5 可見，通過該方式構造的系列16 bit S 盒的密碼性質優良且較為穩定，其最大差分概率集中分布在區間[2-9.83,2-8.64]，最大線性概率集中分布在區間[2-8.71,2-8]。與現有的Piccolo 算法S 盒相比較，通過本文方法可以得到更優密碼學性質的16 bit S 盒，其4 bit S 盒S={2,0,1,8,3,11,6,7,4,9,10,15,12,13,14,5}和線性置換P2(x)構造，其密碼學性質如下：最大差分概率2-9.83，最大線性概率2-8.71。該S 盒具有更均衡的抗差分和抗線性攻擊能力。
表5 2 輪SPS 結構構造的大規模S 盒密碼學性質
4.2 32 bit 大規模S 盒
對于最優線性變換P3(x)或P4(x)，采用2 輪SPS結構可以有效生成密碼學性質優良且實現代價低廉的32 bit 大規模S 盒。為了降低資源占用，這里8 bit S 盒可考慮使用4 bit 小規模S 盒（t1、t2及t3）通過3 輪平衡Feistel 結構構造得到，如圖2 所示。其中，選用4 bitti（i=1,2,3）盒的最大差分概率與最大線性概率均為2-2，即Diff(ti)=4，Lin(ti)=8，，使8 bit 小規模S 盒的差分概率p≤2-4.67，線性概率q≤2-4。基于此類線性置換采用SPS 結構可以有效構造密碼學性質優良且軟硬件實現代價低廉的32 bit S盒。其密碼學性質如下。
由引理2 可知，2 輪SPS 結構構造的32 bit 大規模置換S 盒的差分概率上界為pd-1；由引理3 可知，2 輪SPS 結構構造的32 bit 大規模置換S 盒的線性概率上界為qd-1。
1) 差分均勻度Diff(S)=104，最大差分概率為
2) 線性度為 Lin(S)=224，最大線性概率為
3) 硬件流水線實現時，P3(x)或P4(x)共需要4 個異或運算和4 個循環移位，由于比特位之間的異或運算大約需要2個邏輯門電路，而循環移位靠拉線實現，不占資源，如圖2 所示的8 bit S 盒需要3 個4 bit 異或運算和3 個4 bit T 盒運算，因此，共需要32×4×2+8×(3×4×2+3×30)=1 168 個邏輯門電路。
圖2 3 輪平衡Feistel 結構構造的8 bit S 盒
SPRING 算法[10]的32 bit S 盒迭代32 拍，每拍需要4 個移位寄存器和4 個反饋函數運算，移位寄存器共需要32×6=192 個邏輯門電路，反饋函數需要4×2×2+6=22 個邏輯門電路，一拍S 盒共需要192+22=214 個邏輯門電路。由于一輪S 盒迭代32 拍，硬件流水線實現共需要32×214=6 848 個邏輯門電路。與SPRING 算法的32 bit S 盒相比，采用2 輪SPS 結構構造的32 bit S 盒有更優的密碼學性質，如表6 所示。
表6 32 bit S 盒密碼學性質對比
4.3 64 bit 大規模S 盒
對于最優線性變換P5(x)或P6(x)，采用2 輪SPS結構可以有效構造密碼學性質優良且實現代價低廉的64 bit 大規模S 盒。為了降低資源占用，這里的16 bit S 盒可考慮使用4 bit 小規模S 盒通過圖1的2 輪SPS 結構構造得到，如圖3 所示，其中選用的4 bitt（ii=4,5,…,11）盒的最大差分概率與最大線性概率均為2-2，即Diff(ti)=4，，Lin(ti)=8，，使16 bit 小規模S 盒的最大差分概率p≤2-9.83，線性概率q≤2-8.71。基于此類線性置換采用SPS結構可以有效構造密碼學性質優良且軟硬件實現代價低廉的64 bit S 盒。其密碼學性質如下。
圖3 2 輪SPS 結構構造的16 bit S 盒
由引理2 可知，2 輪SPS 結構構造的64 bit 大規模置換S 盒的差分概率的上界為pd-1；由引理3可知，2 輪SPS 結構構造的64 bit 大規模置換S 盒的線性概率的上界為qd-1。
1) 差分均勻度為Diff(S)=724，最大差分概率為
2) 線性度為Lin(S)=3 2004，最大線性概率為
3) 硬件流水線實現時，P3(x)或P4(x)共需要4 個異或運算和4 個循環移位，由于比特位之間的異或運算大約需要2 個邏輯門電路，而循環移位靠拉線實現，不占資源，2 輪SPS 結構構造的16 bit S 盒如圖3 所示。16 bit S 盒約需要368 個邏輯門電路，因此共約需要64×4×2+8×368=3 456 個邏輯門電路。
Alzette 算法[14]的64 bit S 盒迭代4 輪，每輪包含一個32 bit 整數加法運算、2 個32 bit 異或運算及2 個32 bit 循環右移運算，一個32 bit 整數加法運算最多需要200 個邏輯門電路，2 個32 bit異或運算約需要2×2×32=128 個邏輯門電路，循環移位拉線實現不占資源，因此該64 bit S 盒流水線硬件實現共需要4×(200+128)=1 312 個邏輯門電路。與Alzette 算法的64 bit S 盒相比，采用2 輪SPS 結構構造的64 bit S 盒有更優的密碼學性質，如表7 所示。
表7 64 bit S 盒密碼學性質對比
5 結束語
本文基于循環移位與異或運算構造了有限域上分支數最佳的一類線性變換P，給出了該類最優線性變換的一種新的證明方法，建立了2 輪SPS 結構的大規模S 盒模型，通過小規模S 盒與最優循環移位-異或型線性變換，設計了一系列密碼學性質優良的輕量級大規模S 盒。該設計方案僅使用查表、循環移位、異或三類基本運算，提高了大規模S 盒的線性度和差分均勻度，與已有大規模S 盒構造方法相比，本文大規模S 盒設計方案運算代價更加低廉，其差分、線性等密碼學性質更加優良，可應用于對稱密碼算法非線性置換的設計。
