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