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

李　悅　李　瑋　曹艷琴　樂嘉錦

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

?

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

李悅李瑋曹艷琴樂嘉錦

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

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

物聯(lián)網(wǎng)輕量級加密算法算法性能分析

0　引　言

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

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

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

1　輕量級加密算法介紹

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

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

1.1LED算法基本原理

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

圖1　LED算法結(jié)構(gòu)

1.2TWINE算法基本原理

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

圖2　TWINE算法結(jié)構(gòu)

1.3GOST算法基本原理

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

圖3　GOST算法結(jié)構(gòu)

表2展示了這三種算法的結(jié)構(gòu)參數(shù)，表中的長度單位為比特。

表2　三種輕量級算法的結(jié)構(gòu)參數(shù)

2　加密算法的測試實驗

本節(jié)介紹性能測試實驗的實驗環(huán)境、實驗流程以及實驗結(jié)果數(shù)據(jù)的計算方法。

2.1實驗環(huán)境

? 實驗設(shè)備：裝有Windows操作系統(tǒng)的計算機；

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

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

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

2.2實驗流程

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

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

2.3運行時間與內(nèi)存占用的計算方法

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

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

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

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

{執(zhí)行加密運算；}

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

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

該計算方法的源代碼和實現(xiàn)過程與結(jié)果如圖4所示。

圖4　加密算法的運行時間和所占內(nèi)存的計算方法截圖

2) 算法占用內(nèi)存空間的計算方法

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

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

3　算法的性能分析與比較

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

3.1算法的執(zhí)行時間分析

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

圖5　加密算法的明文長度與執(zhí)行時間關(guān)系圖

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

3.2算法的內(nèi)存開銷

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

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

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

? 當(dāng)明文長度小于2 KB時，輕量級加密算法所占用的內(nèi)存空間比傳統(tǒng)商用加密算法所占用的內(nèi)存空間小50%以上。

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

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

4　結(jié)　語

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

[1] 錢志鴻，王義君. 物聯(lián)網(wǎng)技術(shù)與應(yīng)用研究[J]. 電子學(xué)報,2012,40(5)：1023-1029.

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

[3] 陳海明，崔莉. 面向服務(wù)的物聯(lián)網(wǎng)軟件體系結(jié)構(gòu)設(shè)計與模型檢測[J].計算機學(xué)報,2015,38(5):1-21.

[4] 楊威, 萬武南, 陳運,等.適用于受限設(shè)備的輕量級密碼綜述[J].計算機應(yīng)用,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]. 西安電子科技大學(xué)學(xué)報，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。李悅，博士，主研領(lǐng)域：輕量級密碼算法，物聯(lián)網(wǎng)匿名認證技術(shù)。李瑋，副教授。曹艷琴，碩士生。樂嘉錦，教授。

TP393.08

A

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