王濤

（全球能源互聯(lián)網(wǎng)研究院，北京102209）

1 引言

本文設(shè)計的Electricity（電力輕量級分組密碼）算法是一個迭代型的分組密碼，整體結(jié)構(gòu)為SP（substitution-permutation，代換、置換）網(wǎng)絡(luò)，分組長度為64 bit，密鑰長度有64 bit、80 bit和128 bit共計3種可選值，對應(yīng)的輪數(shù)分別為16輪、18輪和20輪。電力輕量級分組密碼是一個硬件實現(xiàn)與軟件實現(xiàn)均有極佳性能，且安全性可靠的輕量級分組密碼算法。

相較LED密碼（一種輕型分組密碼算法），選用了硬件實現(xiàn)面積更優(yōu)的S盒和列混淆變換。這使得在相同實驗環(huán)境和實驗策略下，電力輕量級分組密碼更為輕量，即硬件面積需求更低。在一定硬件環(huán)境下，Electricity-80可以在1000 GE以下實現(xiàn)。

在很多輕量級密碼的應(yīng)用中，密鑰需要固化到硬件中。此外，輕量級密碼的一些應(yīng)用也需要同一密碼算法具有較好的軟件實現(xiàn)性能，而不僅僅是低的硬件面積。鑒于上述應(yīng)用需求，通過設(shè)計密鑰擴展算法來保護算法，以抵抗相關(guān)密鑰攻擊。這樣的改變，在保證適度安全強度的前提下，只以較小的硬件面積增加（即密鑰擴展算法的額外開銷）來換取軟件速度的提升和硬件性能的提高，使電力專用算法兼有更好的軟件和硬件實現(xiàn)性能。

通過分析電力專用算法針對一些重要分析方法的安全性，得出電力專用算法具有充足的安全強度，能夠抵抗現(xiàn)有的已知安全性分析方法。

2 算法規(guī)范

Electricity是迭代型的分組密碼，其為Rijndael-like（Rijndael算法是美國國家標準與技術(shù)協(xié)會即NIST所選的高級加密標準（AES）的候選算法）的SP網(wǎng)絡(luò)結(jié)構(gòu)，分組長度為64 bit，密鑰長度有3種可選值：64 bit、80 bit、128 bit，3種密鑰長度對應(yīng)的輪數(shù)分別為16輪、18輪與20輪。

算法將64 bit明文分組載入中間狀態(tài)寄存器，表示為M=m0||m1||…||m63。以下分別介紹加密過程與解密過程所用的有關(guān)結(jié)構(gòu)與數(shù)據(jù)。

2.1 加密過程

在進行后續(xù)加密操作前，首先用輪密鑰K0對其進行一次輪密鑰加運算，然后進行R（R是對3種不同密鑰長度的變體，R分別為16、18與20）輪加密運算，最后將寄存器內(nèi)的值作為密文分組輸出。算法的每一輪分為4步：nibble代換s、行移位r、列混淆ρ、輪密鑰加πKi。于是輪函數(shù)可以寫作fi=πKiiρr s，其中i為輪數(shù)。

nibble代換s：該步將中間狀態(tài)M=m0||m1||…||m63，看作16個4 bit nibble n0||n1||…||n15。

對 每 個0≤i≤15，ni=(mi×4,mi×4+1,mi×4+2,mi×4+3)； 將 每 個nibble ni的值用經(jīng)由4×4的4 bit S盒S:運算后所得的值代替。

對每個0≤i≤15，(mi×4,mi×4+1,mi×4+2,mi×4+3):=S(ni)=S(mi×4,mi×4+1,mi×4+2,mi×4+3)，S盒以16進制表示，見表1。

行移位γ：該步中，將中間狀態(tài)n0||n1||…||n15看作4×4的4 bit nibble矩陣：

表1 加密置換

對于i=0,1,2,3，將矩陣的第i行循環(huán)左移i個nibble的位置。

列混淆ρ：該步中MDS矩陣用于線性擴散，該矩陣的設(shè)計原理見第3.2節(jié)；具體可視為矩陣的連續(xù)4次運用。如上，將中間狀態(tài)看作4×4的4 bit nibble矩陣，然后用矩陣A進行4次左乘。選取一個合適的作用于nibble之上的4×4的4 bit線性變換L，則矩陣A與最終的MDS矩陣W可寫作：

輪密鑰加π：該步將輪密鑰Ki=ki0ki1…ki63與中間狀態(tài)值做異或運算，用所得的結(jié)果更新狀態(tài)寄存器。

2.2 解密過程

解密過程中，按與加密過程相反的次序運用各輪輪密鑰，即在解密過程開始前，首先運用子密鑰Kr進行輪密鑰加，然后經(jīng)過R輪解密輪，得出明文分組。加密過程輪函數(shù)為fi=πKiiρr s，則解密輪函數(shù)為fi-1=πKR-is-1ir-1ρ-1，此處的i表示第i次運用解密輪函數(shù)，其中應(yīng)用的密鑰為子密鑰KR-i。

列混淆逆ρ-1：該步中同樣可視為矩陣A的逆矩陣A-1的連續(xù)4次（左乘）運用，A-1利用L的逆變換L-1定義如下：

行移位 逆r-1：將中間狀 態(tài)n0||n1||…||n15看作4×4的4 bit nibble矩陣，對于i=0,1,2,3，將矩陣的第i行循環(huán)右移i個nibble的位置。

nibble代換逆s-1：所用的4×4的4 bit逆S盒以16進制表示，見表2。

表2 解密置換

2.3 密鑰編排

Electricity的密鑰長度可選為64 bit、80 bit或128 bit，處理過程統(tǒng)一描述如下。

將k比特主密鑰看作ω數(shù)目的4 bit nibble，寫作V=v0||v1||…||vk=n0||n1||…||nω。首先將其載入k bit密鑰寄存器R=n0||n1||…||nω=r0||r1||…||rk=v0||v1||…||vk，將 寄 存 器 中 前64 bit取出作為輪密鑰K0：K0=k00k01…k063=r0||r1||…||r63(=v0||v1||…||v63)，然后對于i=1,…,r來說，對密鑰寄存器進行如下更新與取輪密鑰操作。

加輪常量：將5 bit LFSR初始化為全1值(l0,l1,l2,l3,l4)=(1,1,1,1,1)，首先依據(jù)反饋多項式x5+x3+1對其進行更新，然 后 將 其 值 異 或 到 密 鑰 寄 存 器 的 前5 bit中，(r0′,r1′,r2′,r3′,r4′)=(r0茌l0,r1茌l1,r2茌l2,r3茌l3,r4茌l4)。以 后 每 輪 都 首 先 依 據(jù)x5+x3+1更新LFSR狀態(tài)，再進行異或操作。

nibble代換：將k bit密 鑰寄存器 看 作4×λ的4 bit nibble矩陣。

行移位：與加密過程相似，該步將密鑰寄存器看作4×λ的4 bit nibble矩陣，當主密鑰長度為64 bit和128 bit時，對于i=0,1,2,3，將矩陣的第i行循環(huán)左移i個nibble的位置；當主密鑰長度為80 bit時，對于i=0,1,2,3，將矩陣的第i行循環(huán)左移i+3個nibble的位置。

列混淆：與加密過程相似，該步用矩陣A對輪密鑰nibble矩陣進行4次左乘，所用矩陣A與加密過程中所用A相同。

取i輪輪密鑰：取密鑰寄存器的前64 bit作為第i輪的輪密鑰，即Ki=ki0ki1…ki63=r0||r1||…||r63。

2.4 數(shù)據(jù)填充算法

對長度不足64 bit的數(shù)據(jù)分組，要先對其進行10×1式填充，即先填充一個比特1，再填充足夠多的比特0，最后填充一個比特1，將其補足為64倍數(shù)比特（64或128），詳細算法如下。

算法1數(shù)據(jù)填充算法

輸入 長度少于64 bit的數(shù)據(jù)塊m。

輸出 長度為64 bit或者128 bit的填充數(shù)據(jù)塊p。

if長度of m是63

3 設(shè)計準則

Rijndael自其誕生并被選為AES標準以來，受到了廣泛的分析，實踐證明其承受住了絕大部分的考驗。在其基礎(chǔ)上發(fā)展出了Rijndael-like結(jié)構(gòu)，其定義如下。

定義1 Rijndael-like結(jié)構(gòu)：指滿足下述條件的SP網(wǎng)絡(luò)型分組密碼：

·其線性變換形式為(θ1,θ2,θ3,θ4)π；

·（π的條件）yi的各nibble來自不同的xi，其中x=(x1,x2,x3,x4)是π的輸入，y=(y1,y2,y3,y4)是π的輸出，即對于坌i=0,1,2,3，yi的4個nibble分別來自x0、x1、x2與x3；

·（θ=(θ1,θ2,θ3,θ4)的 條 件）將 各θi看作線性變換，則要求分 別 是線性變換θi在差分與線性分析中的分枝數(shù)目（branch number）。

對于Rijndael-like結(jié)構(gòu)，其各種安全參數(shù)已有較完備的分析，得出了大量安全界。基于此，本方案延用Rijndael-like結(jié)構(gòu)作為基礎(chǔ)。

3.1 S盒

輕量級密碼學方案中，為了較好地兼顧安全性與性能，常選用4 bit×4 bit的S盒，選擇依據(jù)如下。

·最大差分概率為2-2：

·最大線性偏差為2-2：

·沒有不動點。

·代數(shù)次數(shù)達到最大值3。

·硬件實現(xiàn)面積小。

最終選定的S盒，硬件實現(xiàn)只需8次操作，共計約15.01 GE：

3.2 線性變換層r與ρ

AES的設(shè)計過程中，提出了線性變換/擴散層（diffusion layer）分枝數(shù)目的概念，含義是差分值/線性掩碼經(jīng)線性變換后，輸入輸出值中不為0的S盒的最小數(shù)目。分枝數(shù)目越大，擴散層的擴散效果越好。對S盒數(shù)目為s的加密方案而言，其分枝數(shù)目為s+1。將達到了此數(shù)值的線性變換稱為完美擴散層（perfect diffusion layer）。

已經(jīng)證明，當[m,s,d]碼的生成矩陣所有的子方陣均為非奇異矩陣時，該碼是MDS碼，這一性質(zhì)可用于檢驗所構(gòu)造的線性變換是否完美（達到分枝數(shù)目）。實際構(gòu)造這樣的矩陣時，一方面希望構(gòu)造過程簡明，另一方面希望構(gòu)造的矩陣有較為簡單的硬件實現(xiàn)，一種構(gòu)造方式是利用多個基于bundle（bundle-based）的LFSR(linear feedback shifting register，一種流密碼技術(shù))，經(jīng)過d次更新，實現(xiàn)線性變換。在這種構(gòu)造方式下，最終的線性變換矩陣D就是這些LFSR的狀態(tài)轉(zhuǎn)移矩陣A的d次冪：D=Ad。本方案選取的就是這樣一個矩陣：

矩陣D是作用于4個4 bit bundle上的矩陣（16 bit），其中的矩陣L則是作用于4 bit bundle上的矩陣。若L選為有且僅有4個1的可逆矩陣，則D成為比特置換，而實際傾向于選取硬件實現(xiàn)面積最小且滿足最終構(gòu)造的矩陣D是MDS矩陣的L。

上述矩陣D是MDS矩陣的條件是其所有子方陣都非奇異，這樣可以計算得出7個條件，即下述7個矩陣均非奇異：L、L+1、L2+L+1、L3+L+1、L3+L2+1、L4+L3+1、L4+L3+L2+L+1。

這個L硬件實現(xiàn)時僅需要若干布線與一個異或門，其開銷很低?？偟膩砜矗藭r矩陣D的硬件實現(xiàn)需2n+2數(shù)目的異或門電路，在同類變換中是最低的，且達到4-bundle線性變換的分枝數(shù)，在性能與安全性兩方面都十分出色。

3.3 密鑰編排設(shè)計

本方案的密鑰編排設(shè)計遵循如下理念：

（1）在編排過程中使用非線性變換以增加安全強度，降低相關(guān)密鑰攻擊的可能性；

（2）在（1）的前提下，使用盡量少的S盒，以減少硬件實現(xiàn)開銷，方案中每次只對狀態(tài)寄存器中1/4的4 bit單元運用S盒；

（3）編排過程盡量使用加密過程中使用的部件，以便實現(xiàn)時共用部件，降低實現(xiàn)開銷；

（4）引入與輪數(shù)相關(guān)的量以抵御slide attack（滑動攻擊）。

綜合上述幾點，最終選用了第2.3節(jié)、第3.3節(jié)所述的編排方案。

4 安全性分析

本節(jié)從差分概率/線性閉包偏差上界、密鑰編排安全性等方面分析本方案的安全性。

4.1 差分概率/線性閉包偏差上界

對Rijndael-like結(jié)構(gòu)的差分概率/線性閉包偏差上界已有較完善的研究，這樣的設(shè)計不僅若干輪的單條軌跡概率/偏差很低，甚至連多條跡聚合而成的概率/偏差也不會很高。

具體地，對于2輪的SPN結(jié)構(gòu)，差分方面有如下定理。

定理1若L的差分分枝數(shù)為βd，則2輪SPN結(jié)構(gòu)的差分概率上界為：

其中，DPSi(u,j)是第i個S盒將輸入差分u映射到輸出差分j的概率。將本方案的S盒差分分布數(shù)據(jù)代入式（7），計算得出2輪差分對概率不超過2-8；再依照與定理1中類似的分析過程，可得本方案4輪差分對的概率不超過2-32。

線性方面，定義相關(guān)系數(shù)為兩倍的線性偏差，則有如下定理。

定理2若L的線性分枝數(shù)為βl，則2輪SPN結(jié)構(gòu)的線性相關(guān)系數(shù)平方上界為：

此處LPSi(u,j)是掩碼對(u,j)在第i個S盒上的相關(guān)系數(shù)平方值。將本方案的S盒線性參數(shù)代入式（8），計算得出2輪線性掩碼的相關(guān)系數(shù)平方值不超過2-8；再依與定理2中類似的分析過程，可得出本方案4輪線性掩碼的相關(guān)系數(shù)平方值不超過2-32。此處的計算結(jié)果在值上與差分方面是相等的。

4.2 高階差分攻擊、插值攻擊與代數(shù)攻擊

高階差分攻擊利用某些加密方案代數(shù)次數(shù)相對較低的特點，將高階差分值作為區(qū)分依據(jù)，當加密方案輸出結(jié)果的某個比特可以寫作輸入比特的n次多項式時，方案輸出值的階差分值在該比特位點上是常數(shù)。插值攻擊和代數(shù)攻擊也利用這種相對較低的代數(shù)次數(shù)：插值攻擊通過插值法求解輸出比特或中間比特的多項式表達式，實施區(qū)分；代數(shù)攻擊則在輸入比特、密鑰比特與輸入比特之間建立二次代數(shù)方程組，設(shè)法通過求解方程組完成密鑰的恢復(fù)。

鑒于本方案采用的S盒代數(shù)次數(shù)最高為3，僅在部分輸出上為2，即使在最不利的情形下，經(jīng)7輪以上后，各輸出比特表達為輸入比特的代數(shù)形式后，次數(shù)也已達到27=128，這意味著至少要2128數(shù)目的明文才能得到固定值的高階（128階）差分；鑒于方案的分組長度僅為64 bit，獲取這么多的明文是不可能的?？紤]到方案的實際輪數(shù)超過16輪，各經(jīng)過改進的高階差分變體成功的可能性也是極低的。

鑒于類似的考量，也無法得到實施插值攻擊所需的數(shù)據(jù)規(guī)模。在代數(shù)攻擊方面，則會因為次數(shù)過高、方程組規(guī)模過大而無法進行。

4.3 密鑰編排安全性

涉及密鑰編排的攻擊包括slide attack、相關(guān)密鑰攻擊與中間相遇攻擊等。為了抵御slide attack，設(shè)計中引入了與輪數(shù)相關(guān)的常量，因此這種攻擊成功的可能性不大；由于輪函數(shù)采用了Rijndael-like結(jié)構(gòu)，引入的差分會迅速擴散，因此相信相關(guān)密鑰攻擊也不太可能；而對于中間相遇攻擊，由于Rijndael-like結(jié)構(gòu)中各比特的值會隨nibble迅速擴散開，因此不太可能找到對較多輪數(shù)有效的中立密鑰比特，也就無法高效地實施中間相遇攻擊。

5 硬件實現(xiàn)評估

本方案采用的結(jié)構(gòu)與各部件都已有較完善的討論。根據(jù)已有成熟結(jié)論，給出本方案的串行化硬件實現(xiàn)結(jié)構(gòu)，其64 bit變體的實現(xiàn)如圖1所示（datapath為4 bit，密鑰編排部分與加密部分很相似）。

考慮上述實現(xiàn)的硬件面積。加密部分的狀態(tài)框內(nèi)含16個4 bit存儲單元，其中實線框為雙輸入的單元，平均每比特存儲約需6 GE，虛線框為單輸入的單元，平均每比特可以僅使用約4.67 GE；密鑰編排模塊的64 bit存儲與之類似；S盒約需15.01 GE；列混淆模塊總計約需26.7 GE；用于生成常量的5 bit LFSR約需26.02 GE；控制邏輯需一個idle、一個控制初始的數(shù)據(jù)載入、一個控制輪密鑰加與代換、3個控制行移位、2個控制列混淆，總計8個狀態(tài)；此外，需3 bit的LFSR作為轉(zhuǎn)移條件，總計約需80 GE。再考慮數(shù)據(jù)處理過程中用到的異或與片選組件，估計總計約需916.28 GE；其中控制邏輯約占8.73%。這樣的實現(xiàn)每輪約需39個時鐘周期，因此16輪加密總計需624個時鐘周期。

其中L與S盒都是4 bit輸入、4 bit輸出的元件，模塊L的細節(jié)如圖2所示。

圖2 模塊L的實現(xiàn)示意

在上述實現(xiàn)中，加密與密鑰編排部分分別用了兩個列混淆模塊與S盒，還有一種高度串行的實現(xiàn)方法是令加密與密鑰編排部分共用同一個列混淆與S盒，但實踐發(fā)現(xiàn)，這種實現(xiàn)看似節(jié)約了兩個加密模塊，卻要額外使用多個片選電路，且增加控制邏輯的規(guī)模與復(fù)雜度，加倍加密所需的時鐘周期數(shù)目，實際能減少的實現(xiàn)面積卻極為有限，因此不予討論。

8 0 bit與128 bit的變體在硬件實現(xiàn)架構(gòu)上與64 bit變體是相似的，不同點在于密鑰編排部分需要更多的狀態(tài)寄存器。此外，由于每輪密鑰編排中全部完成列混淆運算所需的時鐘周期數(shù)目不相同（64 bit分組需4×4+4=20個周期，80 bit密鑰狀態(tài)需5×4+5=25個周期，128 bit密鑰狀態(tài)需8×4+8=40個周期）。對于128 bit密鑰的變體，由于密鑰編排多出的周期數(shù)目40為4的倍數(shù)，尚可在此期間內(nèi)令數(shù)據(jù)狀態(tài)寄存器反復(fù)循環(huán)移位來消耗時間；對于80 bit密鑰變體，多出的5個時鐘周期則難處理，為此將其在行移位階段設(shè)計成移動位，以便用多出的3個周期將其補齊。這樣最終推算結(jié)果見表3。

6 軟件實現(xiàn)評估

利用SSE指令實現(xiàn)的本方案實例在便攜計算機上進行了軟件實現(xiàn)性能測試實驗。該便攜機處理器為Intel i5-2400，主頻為2.5 GHz，內(nèi)存為4 GB。Electricity軟件實現(xiàn)性能數(shù)據(jù)見表4。

圖1 硬件實現(xiàn)示意

表3 Electricity硬件實現(xiàn)性能

表4 Electricity軟件實現(xiàn)性能數(shù)據(jù)

7 結(jié)束語

得益于S盒與MDS矩陣研究的后期進展，本方案獲得了相對已有方案而言極有競爭力的硬件實現(xiàn)面積。選取了合適的輪數(shù)后，本方案的硬件實現(xiàn)加密延時得到控制，這方面優(yōu)于LED很多，加之各部件面積的優(yōu)化，整體硬件實現(xiàn)面積也優(yōu)于LED。

[1]QIU S,BAI G Q,CHEN H Y.One-dimensional confusion coefficient for block cipher[J].Journal of Cryptologic Research,2014,1(2):124-133.

[2]ZHOU Y B,LI J T,LIU J Y.The evolution of security requirements for cryptographic modules:the status quo,dilemma and future trends[J].Journal of Chengdu University of Information Technology.2011,26(2):109-122.

[3]ZHANG S Y,CHEN G L,FAN L,et al.Algorithm of G-AES[J].Journal of Cryptologic Research,2014,1(2):187-199.

[4]LIU Y Z,ZHANG L,LUO P,et al.Research of trustworthy software system in the network[C]//The 5th International Symposium on Parallel Architectures,Algorithms and Programming,December 17-20,2012,Taipei,China.New Jersey:IEEE Press,2012:287-294.

[5]HONG D,SUNG J,HONG S,et al.HIGHT:a new block cipher suitable for low-resource device[M].Berlin:Springer,2006:46-59.

[6]Leander G,PAAR C,POSCHMANN A,et al.New lighweight DES variants[J].Fast Software Encryption 2007-FSE 2007,4593:196-210.

[7]BOGDANOV A,KNUDSEN L R,LEANDER G,et al.PRESENT:an ultra-lightweight block cipher[J].Lecture Notes in Computer Science,2007(4727):450-466.