輕量級分組密碼算法設計研究

陳懷鳳

(中國電子信息產業集團有限公司第六研究所，北京 100083)

0 引言

分組密碼算法是對稱密碼算法中一種，主要用于對信息進行機密性保護，例如當前最為世人所熟知的高級加密標準AES[1]。最近幾年，隨著物聯網的快速發展，無線射頻技術(RFID)和傳感器網絡(WSNs)等應用場景大幅增加，適于在此類資源受限環境中進行信息加密保護的輕量級密碼算法吸引了廣大密碼學者的注意力，許多輕量級的分組密碼算法也被設計出來，例如PRESENT、LED、LBlock、Piccolo、Simon、Speck等。目前，關于“輕量”沒有嚴格明確的定義，一般情況下是指算法的實現很“小”，也就是占有很小的面積。除了面積外，設計人員也會考慮一些其他的準則，例如算法的吞吐量、各種平臺的普適性、功率、能耗、延時等等。

本文從最近幾年提出的輕量級分組密碼算法出發，分析當前階段輕量級分組密碼算法的設計準則與方法，為新的輕量級分組密碼算法的設計提供參考。

1 輕量級分組密碼算法

替換-置換結構(SPN)和Feistel結構是設計分組密碼算法的兩種主要結構，輕量級分組密碼算法方面同樣如此，在具體設計時，算法的某些組件也可能是利用SPN或者Feistel結構進行設計，形成嵌套結構。

1.1 SPN結構的輕量級分組密碼算法

(1)PRESENT

PRESENT算法[2]在CHES’07上被提出，是與AES差異較大的SPN結構算法，其線性變換是面向比特進行操作的，而非以往常用的面向字節的變換，非線性層采用4比特S盒。該算法已被國際標準化組織(ISO)標準化[3]。

(2)LED

LED算法[4]在CHES’11上被提出，是基于AES的框架設計的64比特分組長度的輕量級分組密碼算法，每一輪包括常數加、S盒替換、行移位、列混合，每四輪組成一步，進行一次密鑰加。可認為其不存在密鑰擴展算法，128比特密鑰分為兩個64比特長度的子密鑰輪流與每一步的狀態進行異或。

(3)PRINCE

PRINCE算法[5]在ASIACRYPT’12上被提出，前5輪與后5輪的輪常數具有簡單的代數關系，除此之外是互逆的操作。該算法無密鑰擴展算法，一部分用作白化密鑰，另一部分作為子密鑰直接與輪常數和輪狀態進行異或，具有α-反射性，即以密鑰k的加密運算等價于以k⊕α的解密運算。

(4)ZORRO

ZORRO算法[6]在CHES’13上被提出，是借鑒了AES和LED的設計思路，每一輪包括S盒替換(只對其中4個nibble進行)、常數加、行移位、列混合、密鑰加，該算法像LED一樣沒有密鑰擴展算法，主密鑰分為64比特長的子密鑰按輪進行異或。

(5)Fantomas/Robin

Fantomas/Robin算法[7]在FSE’14上被提出，這兩個算法是屬于“LS設計”，狀態表示為s×l的矩陣，非線性層對每一列進行s比特的S盒替換，線性層則對每一行進行l比特的線性變換，利用bit-slice技術進行S盒快速實現。

(6)PRIDE

PRIDE算法[8]在CRYPTO’14上被提出，主要針對SPN結構的線性層進行優化，在8比特微處理器上用盡可能少的指令實現算法，采用對合的S盒來降低加密和解密的差異性，也可利用bit-slice技術快速實現。密鑰分成白化密鑰和子密鑰，子密鑰只在部分字節上異或常數，然后與每一輪狀態進行異或。

(7)Midori

Midori算法[9]在ASIACRYPT’15上被提出，包括64比特和128比特兩種分組長度版本，其基本結構與AES類似，也是包括S盒替換、行移位、列混合，密鑰擴展算法極為簡單，以128比特版本為例，密鑰與輪常數異或形成各輪的子密鑰，與每一輪狀態進行異或。

(8)Rectangle

Rectangle[10]也是基于bit-slice技術設計的SPN結構的輕量級分組密碼算法，狀態表示成4×16的矩陣。非線性操作為對每一列進行4比特S盒替換，線性層則是對每一行進行行循環移位，各行移位常數不同，其密鑰擴展算法采用廣義Feistel結構。

(9)SKINNY/MANTIS

SKINNY算法族[11]在CRYPTO’16上被提出，是一族可調的輕量級分組密碼算法，每一輪包括S盒替換、常數加、密鑰加、行移位、列混合，該算法使用TWEAKEY結構，輸入包括明文分組、tweak和密鑰，該算法利用MILP(混合整數線性編程)技術給出了差分路徑下活性S盒個數的界。MANTIS是SKINNY的低延時變種算法。

(10)SPARX

SPARX算法[12]在ASIACRYPT’16上被提出，整體采用SPN結構，但是其非線性層是采用模加、循環移位和異或操作構造的ARX結構算法，具體為三輪或四輪SPECK輪函數。其密鑰引入時覆蓋整個狀態，而不是一半。該算法第一次對基于ARX結構的分組密碼算法給出了針對差分特征和線性特征的可證明安全界。

1.2 Feistel結構的輕量級分組密碼算法

(1)HIGHT

HIGHT算法[13]在CHES’06上被提出，是采用廣義Feistel結構的ARX類算法，具有8個分支，非線性操作通過模加運算引入，線性變換有兩個，都是將一個輸入的3個循環移位進行異或求和。通過密鑰擴展算法生成白化密鑰和輪密鑰，各種密鑰通過模加運算和異或運算引入。

(2)LBlock

LBlock算法[14]在ACNS’16上被提出，分組長度為64比特，采用平衡Feistel結構，在其中一個分支上進行循環移位操作，F函數則采用SPN結構。F函數中采用4比特S盒，按nibble進行位置變換完成線性操作。其密鑰擴展算法引入了兩個新的4比特S盒。

(3)Piccolo

Piccolo算法[15]在CHES’11上被提出，分組長度為64比特，采用廣義Feistel結構，具有4個分支。與其他廣義Feistel結構算法不同，該算法的幾個分支之間具有較復雜的線性變換。其F函數采用SPN結構，其4比特S盒在具有合適的非線性度盒差分分布的密碼學特性的基礎上，硬件占用特別低。

(4)TWINE

TWINE算法[16]在2011年被提出，分組長度為64比特，采用廣義Feistel結構，具有16個分支。其F函數是4比特狀態異或密鑰后過一個4比特S盒替換，線性變換主要是16個分支較為復雜的位置置換。

(5)LEA

LEA算法[17]在WISA’13上被提出，分組長度為128比特，是采用廣義Feistel結構的ARX類算法，具有4個分支。所有的模加、循環移位和異或都是面向32比特字進行的，密鑰擴展算法也同樣采用ARX結構。

(6)SIMON/SPECK

SIMON/SPECK算法[18]在2013年由美國國家安全局(NSA)提出，SIMON算法是面向硬件實現的輕量級分組密碼算法族，具有10個版本，采用平衡Feistel結構。其輪函數特特別簡單，只使用與、循環移位和異或操作。SPECK算法是面向軟件實現的輕量級分組密碼算法族，采用ARX結構，其輪函數只采用模加、循環移位和異或操作。設計人員并未對這兩個算法進行安全性說明，而是留給廣大密碼學者進行分析。

(7)RoadRunneR

RoadRunneR算法[19]在LightSec’15上被提出，分組長度為64比特，采用平衡Feistel結構。與LBlock類似，其F函數采用SPN結構，類似于Fantomas/Robin算法的LS設計，使用bit-slice技術實現S盒，其線性層則類似于HIGHT算法，也是幾個循環移位的異或和。

(8)SIMECK

SIMECK算法[20]在CHES’15上被提出，是受SIMON算法族啟發而設計的算法族，其輪函數與SIMON相比，只在循環移位的位數上有所不同，以獲得更小的硬件面積。

2 分組密碼算法設計中的“重量”與“輕量化”

輕量級分組密碼算法在設計時主要考慮的是“輕量化”，但除此之外，不同的密碼學者還有不同的考慮，在本節將根據上一節簡單介紹的密碼算法，總結輕量級分組密碼算法的設計考慮的關鍵點。

2.1 對“重量”的理解

本小節主要介紹密碼學界對密碼算法設計中“重量”的理解，在文獻[21]中對此有所介紹。

算法的“重量”一般是指運行算法所需要的時間和空間的資源占用量，可以在兩種不同的環境中進行測量：硬件環境和軟件環境。但是要注意，硬件環境中的輕量級算法并不意味著軟件環境中的輕量級，反之亦然。

2.1.1硬件環境中的重量

存儲方面主要考慮實現算法需要的邏輯門數量，該量一般使用GE(Gate Equivalence，1GE等價于一個與非門)作為單位。時間效率方面使用吞吐量(Throughput)來表示，也就是在給定時鐘頻率下，算法每秒鐘處理的數據比特數；包括密鑰擴展操作在內的延時也是考慮點之一。對上述量的評估比較復雜，由于各種硬件環境較多且不同密碼研究人員不同的評估環境和方式，很難對不同密碼研究人員的實現結果進行合適的比較。

2.1.2軟件環境中的重量

軟件環境中的重量包括算法運行的時間復雜度和存儲復雜度。時間復雜度的一種評估方式是加密算法(或解密算法)處理1字節數據需要的時鐘周期數，但是某些特定的應用場景中，密鑰擴展等間接開銷也較大，這種計算方式不太準確；另外一種就是考慮算法整體的延時，也就是將所有間接開銷都計算在內考慮需要的時鐘周期數。存儲復雜度主要是考慮算法正常運行時占用的RAM空間量，另外，也要考慮算法存儲(例如Flash)占用的空間量。

2.1.3耗電功率

耗電量是軟硬件實現都要考慮的一個指標。RFID中存在功率限制，或者說某些嵌入式設備是采用電池供電的，在設計算法時應當要考慮算法運行時的平均耗電量以及相應的功率峰值。

2.2 對“輕量級密碼算法”的理解

在2012年，SAARINEN M J O和ENGELS D W從RFID或輕量化傳感器網絡的工業使用方面提出了輕量級密碼算法應該符合的限制和目標[22]，主要包括以下幾點：

(1)算法可在不經過明顯改動的條件下，實現單向可調的認證加密算法、解密算法以及安全的哈希函數。

(2)各種輸入(包括初始化向量IV、認證關聯數據等)的填充以及操作規則需明確定義，輸入數據比率應當盡可能小以避免消息的擴展操作。

(3)初始化向量IV可以不是nonce(nonce在重用選擇IV攻擊中也是安全的)，在各種可能的攻擊模型中，安全強度與密鑰以及狀態的長度一致。

(4)硬件實現應當低于2 000門(GE)，該實現包含加密、解密算法以及相應的狀態存儲；在MCU或CPU平臺上的軟件實現速度以及大小也應在設計時作為指標進行考慮。

(5)算法應當有不低于50個周期的延時，且加密或解密的吞吐量滿足每周期至少輸出1比特。

(6)功率應當低于1～10 μW/MHz，相應的峰值應分別低于3 μW和30 μW，也就是說在2 MHz頻率下，峰值應當低于1.5～15 μW/MHz。

3 輕量級分組密碼算法的設計方法

根據設計準則，將第1節中的輕量級分組密碼算法進行簡單的分類，主要包括面向軟件輕量化、面向硬件輕量化這兩個方向進行設計的算法，部分算法在設計者精心選擇密碼組件的前提下，能夠適應多種平臺或者滿足多種目標，例如低延時或低功耗。

3.1 面向硬件輕量化的分組算法

面向硬件輕量化設計的分組密碼算法如下：

(1)PRESENT：非線性層采用4比特S盒，線性層使用簡單的比特拉線。

(2)LED：采用4比特S盒(PRESENT的S盒)，線性變換是特別簡單的矩陣乘重復四次。

(3)PRINCE：采用4比特S盒，采用4個簡單的小矩陣構造大的線性層矩陣。

(4)Midori：Midori64采用4比特S盒，線性層采用的矩陣只有1和0元素，比較簡單。

(5)Rectangle：采用4比特S盒，使用bit-slice技術快速實現，線性層由循環移位和異或組成，利于軟硬件實現。

(6)SKINNY/MANTIS：SKINNY64采用4比特S盒，線性變換只有循環移位操作以及簡單的異或構成，該算法的軟件實現也很有優勢。

(7)HIGHT：面向硬件實現設計的ARX類算法，所有運算都是以8比特為單位進行的，所以也適合8比特軟件平臺實現。

(8)LBlock：采用4比特S盒，線性操作包括32比特字的循環左移8位以及按4比特nibble的置換。

(9)Piccolo：采用廣義Feistel結構，4比特S盒，F函數中的線性操作只有按nibble的拉線，分支間使用簡單的矩陣乘。

(10)TWINE：采用具有16個分支的廣義Feistel結構，4比特S盒，線性變換就是按nibble的拉線操作。

(11)SIMON、SIMECK：只有循環移位、與和異或操作，硬件占用極低。

3.2 面向軟件輕量化的分組算法

面向軟件輕量化設計的分組密碼算法如下：

(1)ZORRO：采用的8比特S盒是利用更小的S盒組合構造而成的。

(2)Fantomas/Robin：采用8比特S盒(利用小S盒構造)，利用bit-slice技術快速實現，設計者認為該算法硬件實現也較有優勢。

(3)PRIDE：面向8比特位寬單片機的軟件實現設計，bit-slice技術實現16個并行的4比特S盒，并選擇使用極少指令數的線性變換操作。

(4)SPARX：面向軟件輕量化實現設計，采用ARX結構。

(5)LEA：面向軟件快速實現設計，采用ARX結構，以32比特為單位進行各種運算。

(6)SPECK：面向軟件快速實現設計，采用ARX結構。

(7)RoadRunneR：面向8比特處理器的軟件輕量化實現設計，具有較低的代碼量，同時吞吐量較高。采用可bit-slice快速實現的4比特S盒以及具有較少代碼量的線性操作。

3.3 輕量級分組密碼算法的特點與設計思路

3.3.1硬件輕量化的分組算法特點與設計思路

通過總結以上可以發現，面向硬件的輕量級分組密碼算法具有以下特點：

(1)非線性運算多使用4比特S盒或者不使用S盒。這主要是4比特S盒的代數表示形式比較簡單，占用的門數較少，例如LBlock選取的S盒全都可以只使用22個GE實現。

(2)存在多個S盒時，使用相同的S盒，利于算法的多種實現方式，比如并行以提高加密速率，或著串行重用S盒以降低資源占用。

(3)線性層比較簡單，多使用按nibble的位置置換或是由簡單矩陣構成的復雜矩陣進行矩陣乘運算。位置置換在硬件中幾乎不占用資源，復雜矩陣在硬件中可以通過簡單矩陣的重用來實現，資源占用低。

(4)使用SPN結構的輕量級分組密碼算法其加密與解密的操作一般是不同的，這會在實現解密運算時，增加許多額外的資源，但考慮到各種工作模式的存在以及實際使用中加密和解密在設備中使用的不對稱性(只進行加密或解密)，這一問題可以通過相應的協議來解決。不然的話，就需要非常細心地選擇各種密碼組件，例如對合的S盒或像PRINCE的α-反射結構。

(5)Feistel結構的加密和解密運算結構相同，在實現時不會增加太多額外資源。

(6)密鑰擴展算法要簡單，可以重用密碼算法輪函數中的組件，有些算法甚至無密鑰擴展的過程，直接與輪常數異或后再作用到中間狀態上，例如LED、PRINCE等。

3.3.2軟件輕量化的分組算法特點與設計思路

通過總結以上可以發現，面向軟件的輕量級分組密碼算法具有以下特點：

(1)使用4比特S盒的密碼算法多利用bit-slice技術提升加密效率，這需要在選擇S盒時注意S盒代數實現時的指令個數。

(2)ARX類的算法適合軟件快速實現，加法、異或、循環移位操作適合在CPU或MCU中通過一條(或很少的)指令實現。

(3)循環移位常數選擇8或者8的倍數，適合在8比特及其以8倍數為位寬的處理器上快速執行。

(4)SPN結構或者Feistel結構在硬件實現中的優缺點在軟件方面也有類似的問題，主要體現在代碼量以及執行效率方面。

(5)密鑰擴展算法要簡單，可以重用密碼算法輪函數中的組件以降低代碼量。

4 結論

本文簡單介紹了當前階段輕量級分組密碼算法的設計特點，在給出密碼算法“重量”理解的基礎上，分析了輕量級密碼算法非線性組件與線性組件的特點，并從結構以及組件等方面給出了設計面向硬件輕量化或軟件輕量化分組密碼算法的設計思路，為新輕量級分組密碼算法的設計提供參考。