幾種輕量級分組密碼算法的性能分析

李　悅　李　瑋　曹艷琴　樂嘉錦

(東華大學計算機科學與技術學院　上海 201620)

?

幾種輕量級分組密碼算法的性能分析

李悅李瑋曹艷琴樂嘉錦

(東華大學計算機科學與技術學院上海 201620)

輕量級加密算法憑借其密鑰長度相對較短、密碼算法結構簡單、資源消耗小等特點成為物聯網加密算法研究的重要方向之一。挑選了LED、TWINE和GOST這3種典型的輕量級分組密碼算法進行測試實驗并實施性能評估分析。該性能分析方法和結果為今后的物聯網輕量級算法設計與實施提供了可信的實驗數據及性能測試方法。

物聯網輕量級加密算法算法性能分析

0　引　言

近年來，隨著信息技術的飛速發展，物聯網已成為當前世界新一輪經濟和科技發展的戰略制高點之一[1-3]。無線傳感器網絡(WSNs)和無線射頻技術(RFID)的硬件制造和維護成本低，并且具有網絡健壯性高、自組織性強、適用性廣泛等特點，已成為物聯網應用的關鍵組成部分。由于WSNs和RFID都是基于無線網絡傳輸信息，以致攻擊者更加容易獲得、干擾甚至破壞信息傳輸。再則，由于物聯網上使用的微型計算設備計算能力有限，傳統的安全方案資源消耗過大而不能夠適用。

在這種背景之下，輕量級分組密碼算法應運而生[4-12]。輕量級分組密碼算法必須能夠在硬件資源嚴格受限的硬件設備上快速執行且要保證相對的安全性。輕量級密碼算法與傳統密碼算法相比，輕量級密碼算法的執行效率更高、計算資源消耗更少，更適合于計算能力有限的 RFID 標簽、微型無線傳感器等設備。近幾年，許多輕量級加密算法被提出，例如：LED[5]，TWINE[6-8]，GOST[9-11]，HIGHT[12]等多種輕量級密碼算法被提出，其中的很多已經被定義為ISO標準，并應用到了智能卡和RFID設備中。

本文以LED、TWINE、GOST輕量級分組密碼算法為例，基于算法的結構和特點，并結合多種技術對這三種算法的性能進行分析比較。該研究成果為新型輕量級分組算法的設計及分析提供了重要的參考價值。

1　輕量級加密算法介紹

許多輕量級分組密碼算法設計都受到DES和AES設計原理的影響。例如Jian Guo等人在CHES2011上提出的輕量級分組算法LED[5]，輪函數就是代替-置換網絡(SPN)結構，它借鑒了AES[13]的設計思路。輕量級分組密碼算法TWINE[6]是Suzaki等人在SAC 2012上首次提出，它使用了廣義Feistel的算法結構。TWINE算法共有36輪迭代運算，其分組長度為64比特，密鑰長度為80比特和128比特。另外一種典型的輕量級加密算法GOST采用的也是Feistel的32輪迭代結構，分組大小為64比特密鑰長度為256比特。本節將詳細介紹以上3種代表性的輕量級加密算法(LED、TWINE和GOST)的基本原理。在進行輕量級加密算法基本原理說明之前，我們首先對算法原理介紹過程中用到的相關符號進行解釋，具體符號解釋列表見表1所示。

表1　算法介紹中用到的符號解釋

1.1LED算法基本原理

LED[5]輕型分組密碼采用了和AES類似的SPN[13]結構。其加密輪數為32輪，消息分組長度為64比特，密鑰分別支持64比特和128比特，分別稱為LED-64和LED-128。LED算法在第1輪之前進行一次輪密鑰加，以后每4輪進行一次，輪函數包含4個步驟，分別是輪常量加、S盒替換、行移位、列混合。 其中非線性層為16個并行的4×4比特的S盒[5,13]。線性層為狀態矩陣的第j行向左移j位(j=0,1,2,3)。與傳統的AES算法相比，LED算法采用了無密鑰生成的策略，輪密鑰即為初始密鑰，從而提高了加密速度以及減小了硬件實現規模。LED算法的結構如圖1所示。

圖1　LED算法結構

1.2TWINE算法基本原理

TWINE算法采用廣義的Feistel結構與優化分組置亂相結合的方法。其加密輪數為36輪，消息分組長度為64比特，密鑰分別支持80比特和128比特，稱為TWINE-80和TWINE-128。TWINE算法將64比特的子消息分為16個4比特的子塊，經過36次輪函數轉換后得到密文。其中，輪函數由8個4×4比特的S盒非線性變換和基于半字節的位置置換組成。此外，TWINE算法的輪密鑰由主密鑰經過S盒替換、異或、循環移位等操作而產生[6]。與其他輕量級分組密碼算法相比，TWINE算法有很大的雪崩效應[6]，從而增強了該算法的安全性。圖2為TWINE算法的結構圖。

圖2　TWINE算法結構

1.3GOST算法基本原理

GOST分組算法采用32輪Feistel迭代結構，其消息分組長度為64比特，密鑰長度為256比特。在加密數據時，明文輸入被分成左右兩部分，輪函數F的過程是：將右半部分與第i輪的子密鑰進行模232加，該結果分成8個4位分組，第一個4位分組當成第一個S盒，第二個分組當成第二個盒，依次類推。8個S盒的輸出重組成32比特的字，然后整個字循環左移11位。與傳統DES算法相比，GOST密鑰產生過程相對DES的簡單，只需進行查表運算，GOST的密鑰為256比特，而DES的密鑰才56比特，GOST的非線性層為8個大小為4×4比特的S盒，而DES的S盒大小為6×4比特，大大地減少了GOST的內存消耗。GOST是一個比DES更適宜軟件實現的算法，它通過增大密鑰長度、對S盒保密、增加加密輪數等方法來增加GOST算法的安全性。圖3為GOST的算法結構圖。

圖3　GOST算法結構

表2展示了這三種算法的結構參數，表中的長度單位為比特。

表2　三種輕量級算法的結構參數

2　加密算法的測試實驗

本節介紹性能測試實驗的實驗環境、實驗流程以及實驗結果數據的計算方法。

2.1實驗環境

? 實驗設備：裝有Windows操作系統的計算機；

? 硬件配置：CPU：Intel Core I3-2350M 2.30 GHz；內存：4 GB；

? 編程語言：Java；本實驗選擇Java作為算法的編程語言；

? 測試對象: AES、DES、LED、TWINE、GOST加密算法。

2.2實驗流程

本次性能測試目的是分析輕量級密碼算法的運行效率和算法占用內存大小。由于計算機之間的硬件和計算能力不盡相同，運行時計算資源和內存資源也在隨時在變動，因此簡單地將三個輕量級加密算法進行橫向比較是很難比較出它們的性能優越性。因為它們都是優化或者簡化的加密算法，性能差別甚小。為了提高實驗的應用價值和客觀性，我們將輕量級密碼算法和傳統的DES和AES加密算法進行縱向比較。

本次性能測試實驗分別采用AES、DES、LED、TWINE、GOST五種算法對長度為64比特、128比特、256比特、512比特、1024比特和2048比特的明文消息進行加密運算。每個長度的明文在不同算法下使用128比特長度的密鑰進行10次加密運算，去掉最高值和最低值，取其余8次結果的平均值作為該算法處理該明文長度的性能測試結果。

2.3運行時間與內存占用的計算方法

1) 算法運行時間的計算方法

2012年Java推出的JDK1.5開發套件給出了更精確的計時方法：System.nanoTime()，輸出的精度是納秒級別，這個功能給性能測試提供了更準確的參考。

本次實驗利用System.nanoTime將算法結束的計時與運行前的計時進行相減得到算法的運行時間：

Starttime=System.nanoTime();//算法運行開始的計時

{執行加密運算；}

Endtime=System.nanoTime();//算法運行結束的計時

算法運行時間(單位毫秒)=(Endtime-Starttime)/1000000

該計算方法的源代碼和實現過程與結果如圖4所示。

圖4　加密算法的運行時間和所占內存的計算方法截圖

2) 算法占用內存空間的計算方法

Java自帶的runtime類可以通過totalmemory方法和freememory方法得到算法運行結束時所申請的內存空間大小和所剩余的可用空間大小，通過這兩個數值計算得到算法運行時的內存開銷：

定義memoryusage變量為算法運行時的內存開銷memoryusage=runtime.totalMemory()-runtime.freeMemory()

3　算法的性能分析與比較

本文對同一個明文和密鑰采用不同的算法進行加密處理并對運行時間和內存占用空間進行記錄，然后從如下幾個方面對算法進行評估和比較：一是評估執行這幾種算法的加解密所需的時間長短，來比較這5種算法的運行效率；二是評估它們運行時的內存開銷，來比較它們對硬件資源的不同需求。

3.1算法的執行時間分析

除了橫向比較三種輕量級加密算法的運行性能，我們還將它們和現在的傳統商業加密算法DES和AES算法進行縱向比較。我們分別用這些算法對64位、128位、256位、512位、1024位和2048位長度的明文進行加密實驗，將每種算法加密各種長度明文的耗時進行匯總并繪制成明文長度和加密時間的對應關系圖 (見圖5所示)。

圖5　加密算法的明文長度與執行時間關系圖

X軸代表的是明文長度，Y軸代表加密時間。根據圖5的數據曲線顯示，算法的執行時間隨明文長度的增加而增加；從加密時間的角度分析圖5可以發現輕量級算法LED、TWINE和GOST的加密時間大約是AES和DES算法所需時間的1/10，這是因為輕量級加密算法對算法結構的進行了多項優化，其中一項算法優化方法就是對子密鑰產生過程進行優化，LED算法簡化了輪密鑰生成策略，直接把初始密鑰作為輪密鑰；這樣減少了32輪的密鑰擴展和置換操作，減少了算法的計算復雜度；GOST算法的子密鑰產生過程與DES相似但是減少了子密鑰生成過程中的擴展和置換，而是采用11位循環左移運算來生成輪密鑰，從而降低了計算復雜度；圖5的實驗結果分析也證明了這些簡化密鑰生成過程的優化方法確實提高了算法的運行效率。

3.2算法的內存開銷

除了對LED、TWINE、GOST、AES和DES加密算法的運行時間進行分析比較外，我們還對每種算法加密不同長度明文所需的內存空間進行統計并將結果數據繪制成表3所示。

表3　算法的性能分析(單位：MB)

根據表3內存使用情況匯總，我們可以比較分析出這五種算法的內存消耗情況，并且得到如下結論：

? 當明文長度小于2 KB時，輕量級加密算法所占用的內存空間比傳統商用加密算法所占用的內存空間小50%以上。

? 傳統AES和DES算法預留了足夠的明文緩存空間，因此當明文長度小于2 KB不會影響AES和DES算法的內存占用空間，而輕量級加密算法為了減少內存占用率，只預留了1024 bit的明文緩存，當明文長度超過1024 bit，輕量級加密算法的內存占用將會隨著明文長度的增加而增加。

由此可見，輕量級加密算法在加密2 KB以內的明文時占用內存空間少，但是在加密長度較長的明文時內存占用與AES和DES相當。

4　結　語

本文從算法的運行效率和內存開銷這兩個方面對LED、TWINE和GOST三種輕量級分組密碼進行了性能分析并與DES和AES算法進行了縱向比較，結果證明在資源嚴格受限的硬件環境下新型輕量級算法的運算效率高于傳統的AES和DES加密算法。通過多種算法分析研究,發現在輕量級分組密碼設計過程中可以通過簡化密鑰產生過程來提高算法的執行效率、可以通過擴展密鑰長度來增強算法安全性。算法設計者可以從以上這些方面考慮優化輕量級加密算法，從而提高算法的執行效率和安全性。本研究成果為設計新型輕量級算法提供了新型的性能測試方法和重要的性能分析數據。

[1] 錢志鴻，王義君. 物聯網技術與應用研究[J]. 電子學報,2012,40(5)：1023-1029.

[2] 胡永利，孫艷豐，尹寶才. 物聯網信息感知與交互技術[J] . 計算機學報,2012,35(6):1147-1163.

[3] 陳海明，崔莉. 面向服務的物聯網軟件體系結構設計與模型檢測[J].計算機學報,2015,38(5):1-21.

[4] 楊威, 萬武南, 陳運,等.適用于受限設備的輕量級密碼綜述[J].計算機應用,2014,34(7):1871-1877.

[5] Guo J, Peryrin T, Poschmann A. The LED Block Cipher[J]. Cryptographic Hardware and Embedded Systems, 2011,6917:326-341.

[6] Suzaki T, Minematsu K, Morioka S, et al. TWINE: Lightweight Block Cipher for Multiple Platforms[C]//Proceedings of Selected Areas in Cryptography, Aug. 2013,LNCS,7707:339-354.

[7] Li W, Zhang W W, Gu D, et al. Security analysis of the lightweight cryptosystem TWINE in the internet of things[J].KSII Transactions on Internet and Information Systems,2015,9:793-810.

[8] Karakoc F, Demirci H, Harmanci A E. Biclique cryptanalysis of LBlock and TWINE[J].Information Processing Letters,2013,113:423-429.

[9] Isobe T. A single-key attack on the full GOST block cipher[J].Fast Software Encryption,2011,6733:209-305.

[10] Kin J. On the security of the block cipher GOST suitable for the protection in U-business services[J].Personal and Ubiquitous Computing,2013,17:1429-1435.

[11] Lu L Z, Chen S Z. A compress slide attack on the full GOST block cipher[J].Information Processing Letters, 2013,113:634-639.

[12] Chen J Z, Wang M Q, Preneel B. Impossible differential cryptanalysis of the lightweight block ciphers TEA, XTEA and HIGHT[C]//Progress in Cryptology, AFRICACRYPT 2012-5th International Conference on Cryptology in Africa, Proceedings,2012,7374:117-137.

[13] 劉景偉，韋寶典，呂繼強，等. AES S盒的密碼特性分析[J]. 西安電子科技大學學報，2004，31(2):255-259.

PERFORMANCE ANALYSIS ON SEVERAL LIGHTWEIGHT BLOCK CIPHER ALGORITHMS

Li YueLi WeiCao YanqinLe Jiajin

(SchoolofComputerScienceandTechnology,DonghuaUniversity,Shanghai201620,China)

Lightweight encryption algorithms, with their features of relatively shorter key length, simple cryptography structure and low resource consumption, have become one of the important directions of IoT encryption algorithms research. We carried out the test experiments on three selected typical lightweight block cipher algorithms (LED, TWINE and GOST) as well as made performance assessment and analysis. The performance analysis method and results in this paper provides a trustable experimental data and performance test approach for the design and implementation of lightweight algorithm of IoT in the future.

Internet of Things (IoT)Lightweight encryption algorithmAlgorithm performance analysis

2015-07-17。李悅，博士，主研領域：輕量級密碼算法，物聯網匿名認證技術。李瑋，副教授。曹艷琴，碩士生。樂嘉錦，教授。

TP393.08

A

10.3969/j.issn.1000-386x.2016.10.070