幾種輕量級(jí)分組密碼算法的性能分析

李　悅　李　瑋　曹艷琴　樂嘉錦

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

?

幾種輕量級(jí)分組密碼算法的性能分析

李悅李瑋曹艷琴樂嘉錦

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

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

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

0　引　言

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

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

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

1　輕量級(jí)加密算法介紹

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

表1　算法介紹中用到的符號(hào)解釋

1.1LED算法基本原理

LED[5]輕型分組密碼采用了和AES類似的SPN[13]結(jié)構(gòu)。其加密輪數(shù)為32輪，消息分組長(zhǎng)度為64比特，密鑰分別支持64比特和128比特，分別稱為L(zhǎng)ED-64和LED-128。LED算法在第1輪之前進(jìn)行一次輪密鑰加，以后每4輪進(jìn)行一次，輪函數(shù)包含4個(gè)步驟，分別是輪常量加、S盒替換、行移位、列混合。 其中非線性層為16個(gè)并行的4×4比特的S盒[5,13]。線性層為狀態(tài)矩陣的第j行向左移j位(j=0,1,2,3)。與傳統(tǒng)的AES算法相比，LED算法采用了無密鑰生成的策略，輪密鑰即為初始密鑰，從而提高了加密速度以及減小了硬件實(shí)現(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輪，消息分組長(zhǎng)度為64比特，密鑰分別支持80比特和128比特，稱為TWINE-80和TWINE-128。TWINE算法將64比特的子消息分為16個(gè)4比特的子塊，經(jīng)過36次輪函數(shù)轉(zhuǎn)換后得到密文。其中，輪函數(shù)由8個(gè)4×4比特的S盒非線性變換和基于半字節(jié)的位置置換組成。此外，TWINE算法的輪密鑰由主密鑰經(jīng)過S盒替換、異或、循環(huán)移位等操作而產(chǎn)生[6]。與其他輕量級(jí)分組密碼算法相比，TWINE算法有很大的雪崩效應(yīng)[6]，從而增強(qiáng)了該算法的安全性。圖2為TWINE算法的結(jié)構(gòu)圖。

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

1.3GOST算法基本原理

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

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

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

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

2　加密算法的測(cè)試實(shí)驗(yàn)

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

2.1實(shí)驗(yàn)環(huán)境

? 實(shí)驗(yàn)設(shè)備：裝有Windows操作系統(tǒng)的計(jì)算機(jī)；

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

? 編程語言：Java；本實(shí)驗(yàn)選擇Java作為算法的編程語言；

? 測(cè)試對(duì)象: AES、DES、LED、TWINE、GOST加密算法。

2.2實(shí)驗(yàn)流程

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

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

2.3運(yùn)行時(shí)間與內(nèi)存占用的計(jì)算方法

1) 算法運(yùn)行時(shí)間的計(jì)算方法

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

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

Starttime=System.nanoTime();//算法運(yùn)行開始的計(jì)時(shí)

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

Endtime=System.nanoTime();//算法運(yùn)行結(jié)束的計(jì)時(shí)

算法運(yùn)行時(shí)間(單位毫秒)=(Endtime-Starttime)/1000000

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

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

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

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

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

3　算法的性能分析與比較

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

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

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

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

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

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

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

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

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

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

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

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

4　結(jié)　語

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

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

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

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

[4] 楊威, 萬武南, 陳運(yùn),等.適用于受限設(shè)備的輕量級(jí)密碼綜述[J].計(jì)算機(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] 劉景偉，韋寶典，呂繼強(qiáng)，等. AES S盒的密碼特性分析[J]. 西安電子科技大學(xué)學(xué)報(bào)，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)域：輕量級(jí)密碼算法，物聯(lián)網(wǎng)匿名認(rèn)證技術(shù)。李瑋，副教授。曹艷琴，碩士生。樂嘉錦，教授。

TP393.08

A

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