几种轻量级加密算法的比较研究

几种轻量级加密算法的比较研究

　　摘 要： 随着无线射频识别（RFID）技术在各个应用领域的迅猛发展，轻量级（lightweight）加密算法日益受到人们的关注。在RFID中硬件资源是极端受限制的，为了在算法加密性能与硬件资源开销间得到一个好的权衡，把椭圆曲线加密算法（ECC）与流密码加密算法中RC4算法，分组加密算法中的PRESENT算法，进行分析比较。并选取Atmega?32微处理器在AVR Studio仿真平台上进行分析比较。实验获得了这三种算法在算法运行效率、密码安全强度和硬件资源开销间的比较结果。得出，在硬件资源同样极端受限的环境下，ECC所表现出的运行效率和密码安全强度是其他两种算法所不能比拟的，证明了非对称加密算法也可以做到轻量化。

　　关键词： 轻量级加密； RFID； 椭圆曲线加密； 流密码； PRESENT加密算法

　　中图分类号： TN911?34 文献标识码： A 文章编号： 1004?373X（2014）12?0037?05

　　Abstract： With the rapid development of radio frequency identification （RFID） technology， the lightweight encryption algorithm attracts increasing attention. In RFID system， the hardware resources are extremely limited. In order to get a better trade?off between the algorithm's encryption performance and the hardware resource requirements， the elliptic curve cryptography（ECC）is compared with RC4 algorithm in the stream cipher algorithm and PRESENT algorithm in the grouping encryption algorithm. Through the Atmega?32 microprocessor in the AVR Studio simulation platform， the comparison results between the three algorithms′ efficiency and the hardware requirements are obtained. The ECC algorithm ， under the condition of the same restricted hardware resources， is better in the operation efficiency and the password security than the other two algorithms. It proves that the non?symmetric encryption algorithm can also be lightweight.

　　Key words： lightweight encryption； RFID； ECC； stream cipher； PRESENT encryption algorithm

　　0 引 言

　　无线识别射频技术（RFID）具有非接触扫描，体积小型化，抗污染能力强，可重复使用，穿透性强，识别距离远等优点，在物流监管，门禁系统，电子自动收费等领域得到了迅猛地发展[1]。它的信息安全问题也越来越受到人们的关注[2]。以往经典的加密算法如高级加密标准（AES），侧重的是提供高级别加密性能，而没有过多的考虑硬件资源开销问题[3]。显然，在RFID这种硬件资源极端受限的环境下，采用高性能的加密算法是不明智的选择。

　　轻量级（lightweight）加密算法在密钥长度，加密轮数等方面作了改进，使之对处理器计算能力的要求和对硬件资源的开销均有不同程度上的降低，却足以提供所要求的加密性能[4]。在很多RFID低成本无源电子标签（如RFID门票）中，所进行的加密算法只是为了换取一个时间代价，即只要能够保证标签内的信息在所要求的一个时间段内安全即可。

　　流密码中的RC4算法和分组密码中的PRESENT算法，都属于对称加密算法即加密和解密使用相同的密钥，故能较容易做到算法的轻量化，而椭圆曲线加密算法是不对称加密算法[5?7]。本文利用ATmaga?32单片机在AVR Studio.4仿真平台上，对这三种算法的运行效率和密码破译时间进行分析比较。得出在硬件资源同样极端受限的环境下，椭圆曲线加密算法的运行效率要高于另外两种，所生成的密码最难被破译，证明了非对称加密算法同样可以做到轻量化。

　　1 算法介绍

　　1.1 椭圆曲线加密算法

　　1.1.1 椭圆曲线概述

　　椭圆曲线加密算法属于公开密钥加密算法，加密和解密使用不同的密钥。椭圆曲线定义：椭圆曲线是指在射影平面上满足Weierstrass方程的一条光滑曲线和一个无穷远点0∞的集合[8]。本文所选取的这条光滑曲线可以表示为E：Y2=X3+aX+b，此时方程的特征值为大于3的素数。点加运算是椭圆曲线上一条很重要的运算规则，具体规则如下：任意选取椭圆曲线上两点P，Q（若P，Q两点重合，则做P点的切线）做直线交于椭圆曲线的另一点R′，过R′做y轴的平行线交于R，则有P+Q=R。图1给出了椭圆曲线的加法运算法则。根据这个法则，可以知道椭圆曲线内无穷远点0∞与曲线上任一点P有：0∞+P=P，故把无穷远点0∞称为零元。同时可以得出如下结论：如果椭圆曲线上的三个点A，B，C，处于同一条直线上，那么他们的和等于零元，即A+B+C=0∞。k个相同的点P相加，记作kP。如，P+P+P=2P+P=3P。 　　1.1.2 椭圆曲线加密流程

　　首先确定一个有限域Fp，这个域只有p（p为素数）个元素，在这取p=79。

　　（1） 用户A在这个有限域中选定一条椭圆曲线Ep（a，b），并取椭圆曲线上一点，作为基点G。

　　（2） 用户A在1～p-1之间随机选择一个素数作为私有密钥k，并根据加法则，生成公开密钥K=kG。

　　（3） 用户A将Ep（a，b）和点K，G传给用户B。

　　（4） 用户B接到信息后 ，将待传输的明文编码到Ep（a，b）上一点M，并产生一个随机整数r（r）。

　　（5） 用户B计算点C1=M+rK；C2=rG。

　　（6） 用户B将C1，C2传给用户A。

　　（7） 用户A接到信息后，计算C1～kC2，结果就是点M，再对点M进行解码就可以得到明文。在这个通信过程，偷窥者只能看到Ep（a，b），K，G，C1，C2，而通过K，G 求k或通过C2，G求r都是十分困难的。这正是椭圆曲线加密所基于的数学难题，因此偷窥者无法得到用户A，B间传送的明文信息。本文选用密钥为79 b的椭圆曲线加密算法。图2给出椭圆曲线算法的加解密流程。

　　1.2 流密码加密算法

　　1.2.1 流密码概述

　　流密码（stream cipher）也称为序列密码，按位或字节对数据流进行处理，加密和解密使用相同的密钥，是对称密码算法的一种。本文选取的是流密码中的RC4算法。RC4算法是一个面向字节操作、密钥长度可变的流密码（stream cipher）。算法的基本原理可描述为：对于n位长的数据，有共N=2n个可能的内部置换状态矢量S=S[0]，S[1]，…，S[N-1]，这些状态是保密的。密钥流K由S中的2n个元素按一定方式选出一个元素而生成，每生成一个密钥值，S中的元素就重新置换一次，置换后的S自始至终都包含从0～N-1的所有n位比特数，这体现了“一次一密”的加密体制[9]。

　　1.2.2 流密码加密流程

　　内部状态矢量S的初始化： 把S中的元素按升序从0～N-1赋值，即S[0]=0，S[1]=1，S[N-1]=N-1。同时建立一个临时矢量T，如果密钥K的长度为N字节，则将K赋给T否则，若密钥长度为keylen字节则将K的值赋给T的前keylen个元素，并循环重复用K的值赋给T剩下的元素，直到T的所有元素都被赋值。

　　用类C伪代码可表示如下：

　　for i=0 to N?1 do

　　S[i]=i；

　　T[i]=K[i mod keylen]

　　j=0

　　for i=O to N?1 do

　　j=（j+s[i]+T[i]）mod N

　　swap（s[i]，s[j]）；

　　密钥流的生成：矢量S一旦完成初始化，输人密钥就不再被使用。密钥流的生成是从S[0]～S[N-1]，对每个S[i]，根据当前S的值，将S[i]与S中的另一字节置换。当S[N?1]完成置换后，再从S[0]开始继续重复操作。用类C伪代码可表示如下：

　　i，j=0

　　while（true）

　　i=（i+1）mod N

　　j=（j+S[i]）mod N

　　swap（sEi]，s[j]）

　　t=（sEi]+s[j]）mod N；

　　k=S[t]

　　加密时，将k的值与下一明文字节异或；解密时，将k的值与下一密文字节异或。

　　1.3 PRESENT算法

　　1.3.1 PRESENT算法概述

　　PRESENT是分组密码，分组大小是64位，根据密钥的大小可分为PRESENT?80和PRESENT?128两种参数版本，密钥长度分别为80位和128位，因此，在这里选用PRESENT?80。

　　1.3.2 PRESENT算法流程

　　图3为PRESENT?80的算法流程图。

　　PRESENT?80算法要经过31轮加密，每一轮都经过一个SP结构，每个SP结构都是由addRoundKey、sBoxLayer和pLayer三步操作组成[10]。addRoundKey操作是将PRESENT?80的分组数据与轮密钥Ki按位进行异或操作；sBoxLayer是一个非线性置换操作，在PRESENT?80中由一个4位到4位的S盒（S?box）实现。表1给出了S?box的16进制表示；

　　pLayer操作是一个位变换操作，用于改变PRESENT当前分组数据的顺序，把第i位变为第P（i）位，表2给出了pLayer具体操作。

　　密钥调度：PRESENT?80的初始密钥存放在一个80位的密钥寄存器（Key Register）里，表示为K79K78…K0，然后取其高64位的值作为轮密钥Ki=k63k62…k0 （1≤i≤32）。在第i轮加密中，轮密钥Ki=k63k62…k0=K79K78…K16该轮加密完成后，密钥寄存器更新，产生新的轮密钥如此完成31轮的PRESENT?80加密。

　　2 实验与分析

　　2.1 实验设计和实现

　　在微处理器平台的选择上，希望微处理器既能够适用于低功耗的RFID系统中，又能够很好地对上述三种算法进行实现。ATmega32单片机是Atmel公司推出的一款高性能、低功耗AVR高档微处理器。芯片内部集成了较大容量的存储器和丰富强大的硬件接口电路，但由于采用了小引脚封装（为DIP28和TQFP/MLF32），所以其价格相对比较便宜，非常适用于成本较低的RFID系统[11]。另外，ATmega32含有32 KB的内存容量，能够完全满足这三种加密算法的内存需要。所以可以把ATmega32单片机作为目标平台。 　　开发工具选择方面，仿真工具选用AVR Studio4，编译工具选用Win AVR（GCC），并把后者添加前者内，这样就可以在同一个界面下完成对算法编译和仿真。为了数据的准确性，所有仿真都执行多次，取其平均值。

　　2.2 算法性能评估与比较

　　本文从三个方面对这三种算法进行评估和比较：一是评估它们运行时的内存开销，来比较它们各自对硬件资源的需求；二是评估执行这三种算法所需要的机器周期，来比较这三种算法的运行效率；三是评估三种算法各自的密码破译时间，来比较它们的密码安全强度。

　　2.2.1 内存开销比较

　　算法的内存开销，主要是指算法在完成一次加密和解密的过程中所需要的内存大小[12]。表3给出了这三种算法在完成一次加密和解密的过程中所需要的内存大小，单位为字节。为了更直观的比较，在图4中以三维柱状图的形式给出。

　　从表3可以看出，三种算法的代码开销都没有超过总内存的[110]，佐证了这三种算法的轻量级性，而流密码中的RC4算法的代码开销尤为突出，这与其密钥短小有莫大的关系。RRESENT的代码稍大，主要是因为算法过程中的位置换运算消耗内存大。

　　2.2.2 算法的运行效率

　　算法的运行效率，是指算法完成一次加密和解密所需要的机器周期，它反应了算法对能量的运用效率。在能量及其有限的RFID系统中，算法的运行效率显得尤其的关键。在此我们把CPU工作频率设定在8 MHz下，并且为了能够完全覆盖这三种算法，选取一个256位的测试向量进行。表4给出了这三种算法各自的执行时间，单位是机器周期。

　　表4 算法的执行时间

　　为了更直观，图5给出了三种算法完成一次加密和解密所需要的机器周期的比较。

　　可以明显的看出，在算法的运行效率上椭圆曲线算法要优于另外两种算法，这与在仿真过程中，软件只运行椭圆曲线加密算法的低计算开销部分有关。而在运行RC4算法和PRESENT?80时，都要进行位置换和位赋值的操作，这在硬件上实现可能没有任何性能开销，所做的只是将电路的对应位置相连，但是在软件上实现就显得困难多。

　　2.2.3 算法安全强度比较

　　算法的破译，称为密码分析，针对这三种加密算法选用各自最有效的密码分析方法分别对其进行密码分析，用破译算法所耗时间和所占的空间，来衡量这三种算法的密码安全强度。

　　椭圆曲线加密算法，加密和解密所用密钥是不同的，对此采用密钥穷尽搜索方式[13]。在一个有3 000台计算机的网络中进行密钥穷尽搜索的计算，使用粗略的时间估算原理可以得出破解椭圆曲线密钥需要几小时到几天的时间，尽管如此，这种加密强度对于低成本的RFID系统来说还是绰绰有余的，因为召集这样多的人力和计算机资源来破解这种低成本的电子标签是得不偿失的。

　　流密码中的RC4算法，是对称加密算法中的一种，采用暴力攻击方式对其进行破解[14]。暴力攻击RC4算法，必须知道密文某几个字节对应的明文，使之成为已知明文攻击，知道明文后，通过逐一假设密钥尝试解密密文与已知明文进行比较，若解密结果与明文匹配，那么正确的密钥就已经找到。找到了加密密钥，剩余的密文就可以完全解密。用暴力攻击中的全查表法，破译RC4算法所需空间为10 TB，所需时间几乎为0。可以看出虽然RC4算法的代码所占内存小但是安全性却是比较低的。

　　对于分组密码中的PRESENT算法，采用代数分析对其进行攻击[15]。所谓代数分析就是将一个密码算法的计算过程构造成一组代数方程，通过求解这组方程中的未知元来获取该密码算法中的密钥信息。在PRESENT算法的代数分析中，所需的空间可以由单台个人计算机提供，所需要的时间代价是几天，这些时间代价主要用在求解方程组上。为了便于比较，表5给出这三种算法的破译代价。

　　表5 算法破译代价

　　尽管在衡量破译时间上使用的是粗略估算时间原理，但这并不妨碍对这三种算法安全强度的分析，因为RFID系统本身成本就很低，在其中进行加密运算，很大程度上就是为了换取一个安全的时间代价。从表4可以看出：流密码中的RC4算法是最好破译的，这与它的算法简单、密钥短小、算法按位操作有关；椭圆曲线算法和PRESENT?80算法所换取的时间代价是相似的，但是在破译所需空间上，椭圆曲线算法却要比PRESENT?80算法大很多，可以这样说，椭圆曲线加密算法的安全强度胜过PRESENT?80算法。

　　3 结 语

　　对于RFID这种硬件资源极端受限的系统中，就如何在算法的加密性能与硬件资源消耗之间取得一个最佳的权衡。本文选取了不对称加密算法中的椭圆曲线加密算法，并选取对称加密算法中RC4加密算法和PRESENT?80算法与之进行比较。对它们在微处理器平台上进行仿真分析，并比较它们各自的内存消耗，运行效率和密码破译难度。从最后的实验数据可以看出，运行这三种加密算法所耗用的内存都没有超过微处理器内存的10%，证实了这三种算法都属于轻量级的加密算法；在算法的运行效率上，椭圆曲线加密算法所需要的机器周期要比另外两种算法少。

　　在加密强度上，椭圆曲线加密算法作为不对称加密算法所表现出的密码强度更是两外两种算法不能企及的。在硬件资源极端受限的环境下，椭圆曲线加密算法在内存开销、运行效率和密码的安全强度之间做到了较好的兼顾，不对称加密算法同样也可以做到算法的轻量化。

　　参考文献

　　[1] XOLE P H， TURNER L H， HU Zhong?hao， et al. The next generation of RFID technology [C]// Proceedings of Unique Radio Innovation for the 21st Century： Building Scalable and Global RFID Networks. Berlin： [s.n.]， 2010， 3?24. 　　[2] 张忠，徐秋亮.物联网环境下UC安全的组证明RFID协议[J].计算机学报，2011，34（7）：1188?1194.

　　[3] MOJTABA Alizadeh， WAN Haslina Hassan， MAZDAK Zamani， et al. Implementation and evaluation of lightweight encryption algorithms suitable for RFID [J]. Journal of Next Generation Information Technology， 2013， 01（4）： 65?77.

　　[4] FINKENZELLER K. Fundamentals and applications in iontactless smart card， radio frequency identification and near?field communication [M]. 3rd ed. Chichester： Wiley， 2010.

　　[5] KOBLIT Zneal. The stateof elliptic curve cryptography [J]. Designs Codes and Cryptography， 2000， 19： 173?193.

　　[6] COUTURE N， KENT K.B. The effectiveness of brute force attacks on RC4 [C]// Proceedings of Second Annual Conference on Communication Networks and Services Research. [S.l.]： [s.n.]， 2004： 333?336.

　　[7] BODGANOV A， KUNDSEN L R， LEANDER G， et al. PRESENT： an ultra?lightweight block cipher [C]// Workshop on Cryptographic Hardware and Embedded Systems. Berlin： [s.n.]， 2007： 450?466.

　　[8] 李俊芳，崔建双.椭圆曲线加密算法及实例分析[J].网络安全技术与应用，2004（11）：55?57.

　　[9] 黄道林，杨军.RC4加密算法FPGA设计与实现[J].云南大学学报：自然科学版，2009，31（z1）：80?83.

　　[10] GUANG Gong. Lightweight cryptography for RFID systems [D]. Canana： University of Waterloo， 2010.

　　[11] 许鸣，黄健.面向嵌入式应用的加密算法开销与性能分析[J].计算机工程与设计，2009（23）：5365?5368.

　　[12] 茅岑微.适用于RFID的几种小型加密算法比较[J].射频世界，2008（6）：21?24.

　　[13] CERTICOM. ECC challenge [EB/OL]. [2009?11?16]. http：//www.certicom.com /inde.

　　[14] MANTIN Itsik， SHAMIR Adi. A practical attack on broadcast RC4 [C]//Fast Software Encryption. Germany： Springer?verlag， 2002： 87?104.

　　[15] BIHAM Eli， DUNKELMAN Orr， KELLER Nathan. Linear cryptanalysis of reduced?round serpent [J]. Lecture Notes in Computer Science， 2002， 2355： 16?27.

本文来源：https://www.2haoxitong.net/k/doc/f74ce67f7275a417866fb84ae45c3b3567ecdd9d.html