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