几种轻量级分组密码算法的性能分析

李　悦　李　玮　曹艳琴　乐嘉锦

(东华大学计算机科学与技术学院　上海 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