基于椭圆曲线的RFID电子标签加密算法研究

张艺与，赵海军**，贺春林，陈毅红

(1. 西华师范大学 计算机学院，四川 南充 637009；2. 物联网感知与大数据分析南充市重点实验室，四川 南充 637009)

物联网作为新一代信息技术的重要组成部分，已经广泛应用于各个领域. 它是基于互联网、各类传感器以及射频识别 (Radio Frequency Identification,RFID)等技术的新兴技术，旨在将物与物、人与物连接起来，实现万物互联. RFID是物联网的核心技术，其应用已经遍及各个领域，典型应用如智能交通、现代医疗、身份识别、物流、仓储管理、车辆道路交通自动收费管理、智能家居、产品防伪检测和智能卡等领域.

一方面，与传统的条码技术相比，RFID具有非接触式识别、抗污染性强、使用便捷、低成本和自主识别等优点，所以RFID取代传统条码技术是必然的；另一方面，由于RFID系统对应用完全开放的设计思想，使其安全与隐私难以保障，阻碍着它大规模应用. 典型的RFID系统主要由电子标签(Tag)、阅读器、RFID中间件和应用软件4部分构成. 其中电子标签按供电方式分为有源标签、无源标签以及半有源标签. 与传统的硬件资源相比，电子标签因其自身硬件资源极端受限，计算能力和存储能力较弱，难以实现安全性强的公钥加密算法.但基于简单异或等逻辑运算的轻量级加密算法又难以保证标签数据的安全性，所以对于公钥加密算法的轻量化成为解决这个问题的关键.

国内外学者为了平衡RFID系统中硬件实现效率和算法安全性，做了大量研究，提出了许多轻量级加密方案. 文献[1]提出的轻量级数据加密标准 (Data Encryption Standard Lightweight, DESL)分组密码算法，将数据加密标准(Data Encryption Standard, DES)算法的密钥减少为 56 bit，从而实现轻量化，这种算法保密性好、结构紧凑、效率更高.文献[2]提出了A2U2序列密码算法，该算法是针对RFID标签所专门设计的一种轻量级加密算法，硬件实现成本低. 文献[3]提出了ITUbee算法，通过减少加密轮次，降低能耗以达到轻量化. 由于单向散列(Hash)函数计算简单，故在RFID系统中得以广泛应用，比较典型的有文献[4]提出的散列锁(Hash-Lock)协议. 在非对称密码算法的轻量化研究中，椭圆曲线密码 (Elliptic Curve Cryptography,ECC)体制相比于其他公钥加密算法，具有密钥长度短、占用内存资源低以及加密强度大等技术优势，因此许多学者致力于ECC的轻量化研究. 文献[5]提出了一种基于改进ECC算法的RFID系统安全认证协议；文献[6-8]通过优化ECC算法运算过程中的标量乘运算，以达到降低运算量的目的.

以上轻量加密方案可以概括为：基于对称密码体制的轻量化和基于非对称密码体制的轻量化. 对称密码体制轻量化主要通过减少密钥长度和减少加密轮次来实现，此类方法均是通过牺牲一定安全性来降低算法计算量，非对称密码体制中椭圆曲线密码体制的轻量化主要通过减少密钥长度和优化底层运算来实现轻量化. 同样的，减少密钥长度会牺牲一定的安全性，而优化底层运算来降低算法计算量可以在不改变安全性的基础上提高计算速度，是目前椭圆曲线密码体制研究的热点问题.

本文考虑到ECC算法占用内存小、计算速度快、带宽要求低、加密强度大等优势，选择ECC算法作为RFID系统电子标签的加密算法，并对原有算法进行改进以提高算法的计算速度. 标量乘法是椭圆曲线加密体制最耗时的运算，本文主要研究通过改进椭圆曲线标量乘运算来实现椭圆曲线密码体制的轻量化.

1 RFID 系统数据加密问题

1.1 RFID 系统中的数据特点RFID 作为物联网感知层的核心技术，系统中产生和存储的数据具有如下特点[9]：

（1）时效性 指从数据产生到其被清除的时间，数据时效性是由系统的实施部署所决定. 物联网对实时性要求较高，需要做到能够及时发送、交互性强、数据转发性能高.

（2）海量性 物联网是由若干无线识别的物体彼此连接和结合形成的动态网络，在这个动态网络中所采集、产生的数据量都是巨大的，如何处理这些海量的数据，是物联网数据处理需要特别考虑的问题.

（3）多态性与异构性 在物联网中通过无线传感器网络、RFID系统以及M2M系统来采集数据，这些底层设备在不同应用系统中又有不同用途，并且这些设备结构不同、性能各异，其采集的数据结构也各不相同，也就导致了物联网中数据的多态和异构.

根据RFID系统中数据的以上特点，需要针对该类数据的特点选取合适的数据加密方法.

1.2 RFID 系统中的数据加密机制作为数据保护的核心技术，数据加密可保障数据机密性、完整性、认证性、不可抵赖性以及可用性[10]. 因此，物联网下的数据加密机制成为了物联网安全的重要研究内容之一. 在当前RFID系统的数据加密机制的研究领域，根据算法的安全性和实现复杂度分为轻量级加密算法、中量级加密算法和重量级加密算法[11]. RFID系统中主要的轻量级数据加密方法有：基于简单异或等逻辑运算的轻量级互认证协议(Lightweight Mutual Authentication Protocol,LMAP)[12]、DESL 算法[1]、A2U2算法[2]和 Present-80算法[13]等；中量级数据加密方法有：基于散列(Hash)函数的Hash-lock加密算法[4]、随机Hashlock加密算法[14]等；重量级数据数据加密方法有：基于公钥加密的RSA[15]、椭圆曲线密码体制[16]和超椭圆曲线密码体制 (Hyperelliptic Curve Cryptography, HECC)[17]等. 轻量级加密算法计算量相对较少，对硬件资源要求低，但相应的安全性不高. 重量级加密算法安全性高，但对于硬件资源极端受限的情况下不适用，其中椭圆曲线加密体制与其他公钥密码体制相比密钥短、加密强度高，占用存储资源少，其轻量化能够实现硬件资源受限和安全性之间很好的平衡，因此许多学者致力于轻量化ECC以适应于RFID系统的电子标签数据加密.

2 椭圆曲线密码体制概述

2.1 椭 圆 曲 线 的 定 义椭 圆 曲 线 加 密 体 制 由Kobilitz和Miller[16]提出. 椭圆曲线是指由韦尔斯特拉(Weierstrass)方程

所确定的平面曲线，通常用E表示，表示亏格为1的代数曲线. 其中a、b、c、d和e属于域F，F可以是有理数域、复数域或有限域F(p). 椭圆曲线是其上所有点(x，y)的集合，再加一个无穷远点O. 无穷远点是指椭圆曲线上一个特殊的点，为仿射平面无穷远处的点.

2.2 有限域F(p)上的椭圆曲线用于密码学的椭圆曲线分为以素数为模的整数域F(p)(适合于软件实现)和特征为2的伽罗华域F(2m)(适合于硬件实现)两大类. 本文主要研究有限域F(p)上的曲线，这类椭圆曲线最简单的表示式为

其中，p为一个大素数，a、b、x和y均在有限域F(p)中，即从{0, 1, ·· · ,p−1}上取值，且满足 4a3+27b2(modp)≠0，这类椭圆曲线通常用Ep(a,b)表示. 该椭圆曲线上只有有限个离散点，设为N个，则N称为椭圆曲线的阶，N越大，安全性越高.

设点P=(x1,y1)和点Q=(x2,y2)在F(p)的椭圆曲线上. 另外，设O为无穷远处的点.

椭圆曲线（Elliptic Curve，EC）的加法运算规则如下：

对于给定点P和Q，如果x1=x2y2=−y1，则

一般情况下，R=Q+P，其中R=(x3,y3)的结果定义如下：

2.3 椭圆曲线离散对数问题椭圆曲线加密体制的安全性基于椭圆曲线上离散对数问题的难度，目前还不存在多项式时间算法求解椭圆曲线上的离散对数问题[18]. 其中Q为P的倍点，则存在正整数k，由k和P容易计算Q. 由P、Q求k称为椭圆曲线上的离散对数问题 (Ecliptic Curve Discrete Logarithm Problem，ECDLP).

3 椭圆曲线加密算法的轻量化

3.1 椭圆曲线上的标量乘椭圆曲线密码体制中最核心的问题是在给定大整数k以及点P∈E后有效地计算出kP，即

该运算称为标量乘，其中k称为标量. 标量乘的计算主要由点加与倍点两部分组成，是ECC的主要运算之一，占用的执行时间最多，因此决定了椭圆曲线密码体制的效率. 因此本文提出对标量乘运算进行优化来实现椭圆曲线加密算法的轻量化.

3.2 提出的 PECC-NAF 并行标量乘计算方法

3.2.1 二进制方法 二进制方法是计算ECC标量乘的传统算法，基于点运算，即点加和点乘运算，是一种用于求幂运算的加法表示. 设F(p)是有限域，椭圆曲线Ep(a,b)的基点为P，P的阶为n，标量k随机地从区间 [1, 2, ··· ,n−1]选取，k的二进制表示为 (kn−1, ··· ,k2,k1,k0)2,ki∈{0, 1}，则

算法1具体步骤如下：

步骤 1将结果集Q置为0.

步骤 2从右到左扫描每一位二进制位ki，当ki=1时执行一次点加操作Q=Q+P，并将计算结果存入结果集中.

步骤 3执行一次点乘操作P=2P. 返回步骤2，直至所有二进制位扫描结束.

步骤 4返回结果集Q.

对于标量k，二进制算法需要执行l−1次倍点运算和h−1次点加运算，其中h是k的二进制表示中汉明重量(即非零比特的个数)，因此标量乘的运算量取决于标量k二进制表示的长度l和汉明重量h. 因为长度为l位的标量k的平均汉明重量期望值是l/2，所以，算法1的计算量可以近似表示为(l−1)/2A+(l−1)D，其中D表示倍点运算，A表示点加运算[19]. 图1给出了标量k为119时的二进制标量乘kP的计算过程.

图 1 二进制标量乘计算过程Fig. 1 The calculation process of Binary scalar

3.2.2 高效的非邻接形式方法 从二进制算法可以看到，标量乘kP运算中标量k的二进制表示长度以及其非零元的个数(即汉明重量)决定了该运算的计算效率. 为了减少运算量，提高运算效率，可以通过构建原二进制表示的等价序列表示，目的是缩短标量原二进制表示中的长度或减少原二进制表示中汉明重量. 根据这一思想，提出了一种稀疏的使用带符号数位集的表示即非邻接形式(Non-Adjacent Form, NAF)[19]的高效计算方法.

一个正整数k的NAF表达式为其中ki∈{−1, 0, 1}，kl−1≠0，并且没有两个连续的数字ki是非零的，也就是说若ki=0，则ki+1≠0；若ki≠0，则ki+1=0，其中NAF的长度是l. 整数k的非邻接形式记作NAF(k). 算法2具体步骤如下：

步骤 1将结果集Q置为0.

步骤 2从左到右扫描每一位ki，执行倍乘运算Q=2Q.

步骤 3当ki=1时执行一次点加操作Q=Q+P，并将计算结果存入结果集中. 当ki=−1时执行一次点减操作Q=Q−P，并将计算结果存入结果集中. 返回步骤2，直至所有位扫描结束.

步骤 4返回结果集Q.

在以上算法运算过程中，有l−1次倍点运算和平均(l−1)/3次点加运算. 因此算法2的运算量可以表示为 (l−1)/3A+(l−1)D[19]. 图 2 给出了标量k为119时的NAF标量乘kP的计算过程.

图 2 NAF 标量乘计算过程Fig. 2 The calculation process of NAF scalar multiplication

3.2.3 PECC-NAF 并行标量乘算法 为了进一步减少标量乘法的执行时间，本文在基于NAF标量乘算法的基础上，提出了一种并行计算ECC标量乘法的方法 (Parallel ECC-NAF，PECC-NAF)来实现加密. 算法3具体步骤如下：

步骤 1执行倍乘运算.

（1） 将结果集R置为P.

（2） 从右到左扫描每一位ki，每次循环均执行倍乘运算R=2R，并将结果集R存入共享数组Ai.

步骤 2转换标量表示为NAF(k)，再执行点加运算.

（1） 执行 NAF 标量转换.

（2） 从右到左扫描每一位ki，并从共享数组中Ai中取出当前倍乘运算结果存入临时数组T中. 取出当前位的值ki存入临时变量m中.

（3） 判断当前位m的值，当m=1时执行一次点加操作Q=Q+T，并将计算结果存入结果集中. 当m=−1时执行一次点减操作Q=Q−T，并将计算结果存入结果集中. 返回步骤2，直至所有位扫描结束.

（4） 返回结果集Q.

在以上算法运算过程中，有l−1次倍点运算和平均(l−1)/3次点加运算，点加运算次数明显小于倍点运算次数. 由于并行执行点加和倍点运算，因此标量乘的计算时间取决于(l−1)次倍点运算. 与算法1和算法2对比，运算效率有明显的改善和提升. 图3给出了标量k为119时的PECC-NAF标量乘kP的计算过程.

图 3 PECC-NAF 标量乘计算过程Fig. 3 The calculation process of PECC-NAF scalar multiplication

从图1和图2对比可以看出，二进制标量乘每一次点加操作都要等待倍点运算的结果与上一次结果相加，其中倍点运算较点加操作更复杂，因此点加操作会产生较长的等待时间. 而NAF标量乘用NAF表示标量，降低了标量的汉明重量，从而减少了点加操作的次数，但点加操作仍然需要等待倍点运算；从图3可以看出，PECC-NAF标量乘运算，在NAF标量乘基础上将运算量更大的倍点运算与点加运算并行执行，改变了原算法的执行过程. 改进算法的点加操作不再需要在每一步都等待倍点运算结果，只需在非零位将点加和倍点运算的结果相加，提高了算法的执行效率. 改进算法利用了并行化思想，将点加和倍点运算并行执行，虽然不能实现两种运算完全互不影响，但倍点运算可以看做是完全独立的进程，极大地减少了点加运算的等待时间，因此认为该算法改进方案是可取的.

该并行算法策略是在基于NAF算法基础上，将标量乘中倍乘和点加操作并行化. 采用任务分解策略，将NAF标量乘法算法分解为两部分进行并行计算.

第1部分由进程1处理，进程1计算l−1次倍乘操作，并将结果保存到共享数组A中. 可以看出，{−1, 0, 1}和倍乘操作之间没有依赖关系. 进程 1 必须根据密钥l−1的长度执行倍乘操作. 在本方案中，如果密钥大小为160 bit，则进程1必须执行重复操作159次. 此外，进程1必须保存共享数组A中的点乘结果，数组A的大小与n的大小相同.

进程2中要做两步操作. 首先求出NAF表示，然后执行加法操作. 加法操作的次数等于密钥的汉明重量. 进程2必须在执行加法操作之前得到NAF表示. 根据NAF表示中的位(1或−1)的类型，执行加法或减法操作.

如果NAF表示中的位是‘1’，进程2执行加法运算并将结果保存在累加器Q中；如果位是‘−1’，执行减法运算并将结果保存在Q中；如果位是‘0’，进程2不执行任何运算.

进程2通过读取共享数组A中保存的点(2P、4P、…、2n−1P)来执行加减操作，两个进程都能够访问位于共享内存中的共享数组A. 进程1在数组A中执行写操作，而进程2在数组A中执行读操作.

对共享数组的访问需要谨慎处理. 进程1应该只允许写入，而进程2应该只允许读出. 共享数组A的读写方式为：进程1在开始执行第i+1次倍点操作时为A[i]添加同步锁，在写入结果之后释放同步锁，能够保证进程2在读取A[i]时的数据一致性.

4 算法实验结果及分析

本文将提出的PECC-NAF标量乘法从算法运行效率、内存开销和密钥长度3个维度与二进制标量乘法和NAF标量乘法进行比较，综合比较证明PECC-NAF标量乘法的可行性.

图4中给出了算法的执行过程，3种算法的执行过程相同，其中标量转换和标量乘步骤的核心算法各有差异，这决定了3种算法不同的运行效率和内存开销. 并将基于PECC-NAF标量乘的椭圆曲线加密算法与现有的其他能够应用到RFID标签的加密算法进行安全性比较，更加全面地证明本文改进算法的可行性.

4.1 算法运行效率分析实验选择比特币采用的secp256k1标准定义的椭圆曲线，使用IDEA编程工具和JAVA编写了顺序代码和并行代码. 在具体的实现过程中使用随机生成的一个大整数作为密钥，在并行和顺序形式中密钥的每个二进制位用来确定加法和减法操作的数目. 根据一个随机密钥生成执行标量乘法，对于每类不同大小的密钥，在并行和串行形式中都采用相同的密钥执行标量乘法的计算. 非零位数在计算ECC标量乘法中的作用非常关键，由于使用了NAF表示，密钥中的非零位的平均数量约为50%或者更少，因此能够有效提高运算速度.

在实现过程中，测试了并行和串行两种算法的两种不同的密钥大小：255、160 bit. 为两种密钥大小随机生成一个大整数作为私钥，将私钥与基点相乘做标量乘运算. 分别测试了标量乘运算在二进制算法、NAF算法下的串行和并行执行情况(其中NAF算法的并行算法即为PECC-NAF算法)，对每种情况执行10次，取平均执行时间进行比较. 表1给出了二进制算法和NAF算法串行和并行形式各自的执行时间.

图 4 算法比较流程图Fig. 4 Flow chart of different algorithms

表 1 二进制算法与 NAF 算法串/并行速率比较Tab. 1 Comparison of serial/parallel rate between Binary algorithm and NAF algorithm

由实验结果可以看出，在算法的运行效率上PECC-NAF算法要优于传统二进制算法以及NAF算法本身. 这是因为在计算标量乘运算过程时，PECC-NAF算法将倍点运算与点加运算同时进行，点加运算不再需要每次等待倍点运算结果，只需在标量的NAF表示中遇到非零位时再取倍点运算结果进行计算，因此极大地提高了标量乘的运算效率.

同时，本文将PECC-NAF标量乘算法与文献[7]中提出的改进标量乘算法的运行时间进行比较. 通过Java编程，在程序中随机生成5个整数和椭圆曲线上面的点P，计算kP所生成的时间，比较结果由表2给出.

表 2 两种算法的运算时间的比较 (单位：ms)Tab. 2 Comparison of operation time of two algorithms(unit: ms)

由表2可以看出，针对不同的标量k，PECCNAF算法的运算时间要比文献[7]中的改进算法更短. 这是因为文献[7]中改进算法是基于多基标量乘，标量转换算法和标量乘算法复杂度高. 本文提出的PECC-NAF算法与之相比，标量转换更为简单，且利用并行化思想优化了标量乘计算过程，有效提高了算法计算效率.

4.2 算法内存开销分析在内存开销损失不大的前提下提高了标量乘运算的运行效率，表3给出了二进制算法和NAF算法串行和并行形式各自需要的内存大小.

由表3可以看出，在算法内存开销上，改进的算法与二进制算法相比有较为明显的提升，但与NAF算法相比，优化并不明显，有一定的内存开销损失，但相对于算法整体内存开销可以忽略不计.综合考虑算法运行效率的提升以及算法内存开销，改进的算法具有一定的应用价值，对后续研究椭圆曲线密码体制具有一定的启示作用.

表 3 二进制算法与 NAF 算法串/并行内存开销比较Tab. 3 Comparison of serial/parallel memory overhead between Binary algorithm and NAF algorithm

4.3 算法安全性分析改进算法 PECC-NAF 主要是对标量乘运算运行效率的影响，没有改变椭圆曲线加密体制的加解密过程. 因此，将PECC-NAF算法运用到椭圆曲线加密体制中代替原标量乘运算，能够在提高算法运行效率的同时，保证算法的安全性. 表4给出了在相同加密强度下，公钥加密算法ECC和RSA 的安全性比较. 其中MI/S(Million Instruction Per Second)表示单字长定点指令平均执行速度，每秒处理百万级的机器语言指令数. MI/S-年表示以每秒执行100万条指令的计算机运行1年，一般认为破译时间为1012MI/S-年表示安全.

表 4 ECC、RSA 的安全性比较Tab. 4 Security comparison of ECC and RSA

由表4可以看出，在相同加密强度下，ECC密钥长度始终比RSA密钥长度短. 并且随密钥长度不断增加，ECC的安全性比RSA增长更快.

表5比较了基于改进标量乘PECC-NAF算法的椭圆曲线加密算法与文献[11]中的4种密码体制的算法性能.

对表5的数据分析可知，ECC与其他密码体制相比虽然具有高安全性，但由于其算法复杂度较高，算法执行效率低. 本文通过改进标量乘来优化ECC，在保证算法安全性的基础上，降低运算量，提高算法执行效率.

表 5 ECC 与其他密码体制算法性能比较Tab. 5 Comparison of performance between ECC and other encryption algorithms

5 结束语

RFID系统自身硬件资源非常受限，难以实现安全性强的公钥加密算法. 要实现适用性和安全性的平衡，需要选择合适的加密算法. 本文提出采用公钥加密算法中的椭圆曲线密码体制作为RFID系统的加密机制；与减少密钥长度的椭圆曲线轻量化方案相比，本文在保证算法安全性的基础上降低算法运算量. 为了减少标量乘法的执行时间，提出了一种新方法即PECC-NAF并行执行标量乘运算.PECC-NAF算法改变了传统标量乘算法的执行过程，在二进制标量乘算法和NAF标量乘算法基础上进行了显著的过程优化，计算速度更快，计算量更低，从而使得椭圆曲线加密体制整体上达到了安全、有效以及轻量化的要求. 下一步可以将该算法应用到物联网射频识别认证协议的设计中，继续利用椭圆曲线加密体制的优势设计轻量级的认证协议，使其既能保障RFID系统的安全性和隐私，也能适应RFID系统资源极端受限的情况.