基于NTRU密码体制的RFID安全协议

何文才，阎晓姮，于源猛，刘培鹤，韩妍妍，赵程程

(1.北京电子科技学院通信工程系，北京 100070；2.西安电子科技大学通信工程学院，西安 710071；3.中共大连市委办公厅，辽宁 大连 116001)

1 概述

射频识别(Radio Frequency Identification,RFID)是一种利用射频信号识别并控制被标识物品的非接触式自动识别技术。一套完整的RFID系统，由标签(Tag)、阅读器(Reader)与后台服务器(Server)三大部分组成。其中，标签中存有世界上唯一的标签ID信息。标签与后台服务器通过阅读器进行通信，可实现对物品的识别与管理。RFID技术具有较强的识别能力，被认为在不久的将来会取代条形码技术。目前，RFID技术已被广泛应用到身份识别、公共交通管理、物流仓储管理等多个领域。

由于阅读器与标签通过公开信道进行通信，在信息传输中存在着风险，因此研究RFID系统的安全机制具有较高的应用价值。在一些特定的环境下，由于射频信号传输的开放性以及计算能力的限制，基于对称加密体制的认证协议已不能满足需求，例如保护一些有较高安全性需求的高附加值消费类产品的信息。RSA公钥算法虽然安全性较高，但其在加解密过程中均要进行大量的指数运算，不仅计算复杂度较高，而且对计算资源的要求也较高，不适合在RFID这类计算能力较低的终端产品上使用。

本文提出的RFID安全协议利用了一种后量子公钥密码体制——NTRU密码体制，其安全性是基于格中最短向量问题(SVP)的困难性，对密文的解密是NP困难的，安全性较高。协议使用基于嵌入Hash函数的NTRU公钥加密方案，标签和服务器通过检验原始Hash值与解密所得Hash值是否相等，以实现阅读器与标签之间的双向安全认证。

2 相关工作

现有的RFID安全机制大致可分为3类：基于物理方法的机制，基于密码的机制和两者结合的机制[1]。

早期由于标签芯片在技术上的限制，人们多考虑用物理方法来保护RFID系统的安全。例如Kill命令、主动干扰和静电屏蔽等。但这些方法灵活性差、标签损耗大且往往涉及法律问题。

随着芯片技术的迅猛发展，越来越多的人开始研究基于密码机制的安全协议。基于杂凑和随机化函数的安全协议利用标签ID信息和后台服务器数据的关联来保护标签ID信息，如随机化Hash-Lock协议[2]、Hash链协议[3]、基于杂凑的ID变化协议[4]等。但这些协议在认证过程中，标签和服务器的数据往往会不同步，由此会产生拒绝服务攻击的问题。基于共享密钥和伪随机函数的安全协议使用基于预共享密钥的伪随机数函数来实现认证，如David数字图书馆RFID协议[5]。但该协议对标签有较高的硬件要求，而且当标签的数目很大时，每次认证过程中后台服务器为比较ID而花费的开销会非常大，因此不适宜在低成本的RFID系统中使用。一些RFID协议基于对称加密算法，如DES和AES[6]等。然而，随着标签数量的增加，对称加密算法的密钥管理是十分复杂的，因此并不适合在RFID系统中使用。如果采用公钥密码算法，可以解决密钥管理、隐私保护等RFID系统需要解决的问题。然而典型的RSA公钥加密算法在加解密过程中需要进行复杂的指数运算，计算复杂度过高，因此也不适合在RFID系统中使用。

3NTRU公钥密码体制

3.1 NTRU公钥密码体制的加解密

NTRU公钥密码体制的密钥生成、加密及解密过程如下[7]：

(1)密钥生成

选取3个整数参数(N,p,q)，4个多项式集合Lf,Lg,Lφ,Lm，其系数为整数，次数为N-1，gcd(p,q)=1，且q远大于p。

随机选取2个多项式f∈Lf，g∈Lg，且f具有模p和模q的乘法逆元，用Fp和Fq分别表示f模p和q的逆元，即Fp× f ≡1(modp),Fq× f ≡1(mod q)，计 算 h≡Fq×1(modq)，其中，多项式h为公钥，即Kpu=h。多项式f为私钥，实际上Fp和Fq也需要保密，即Kpr=(f,Fp,Fq)。

(2)加密

发送方需要加密的明文消息m∈Lm，随机选取多项式φ∈Lφ，利用公钥h计算：

多项式c就是加密m后得到的密文。

(3)解密

接收方对密文做如下操作：1)利用私钥f计算a≡f·c(modq)，其中，多项式a的系数选在区间内。2)利用私钥Fp计算 Fp·a(mod p)，所得结果即明文消息m。

3.2 加解密的计算复杂性

分析加解密过程不难看出，NTRU算法的计算对象只包括多项式环之间的加、减、模、乘和求逆等运算，而多项式环之间的加、减运算与普通多项式的加、减运算是完全相同的，可见NTRU公钥密码体制的计算复杂度较低。国内外对NTRU算法的研究证明，NTRU算法是公钥体制中最快的、也是较为容易实现的算法。

在相同安全级别下，NTRU算法要比其他公钥算法快得多，用Tumbler软件工具包执行NTRU的速度比RSA快100多倍。用NTRU算法产生密钥的速度也很快，密钥比特数也较小，从而降低了其对带宽、处理器、存储器的性能要求[8]。

3.3 NTRU公钥密码体制的安全性分析

攻击NTRU公钥密码体制的方法主要有3种：(1)格攻击；(2)不完备解密攻击；(3)选择密文攻击。其中最有效的攻击是格攻击。NTRU的安全性是基于数论中的一个著名的数学难题，即在一个维数非常大的格中寻找一个很短的向量。恢复明文消息m和私钥f等价于在特定格中寻找最短的向量。理论上可以通过穷举法找到最短向量，然而在实际中这种方法是不可行的。特别是在格的维数很大的情况下，这种方法的计算量是相当可观的。解决这类难题的最好方法是LLL算法及其改进，利用这些算法可在多项式时间内找到最短向量。同样如果格的维数很大，也不能找到最短向量。

NTRU公钥密码体制的破解时间可利用lbT≥AN+B进行粗略估计，其中，A,B均为常数，可通过实验得出。NTRU公钥密码体制估计的破解时间如表1所示，其中，MIPS-years表示以每秒处理100万条指令的处理器运算一年为单位。整个实验在400 MHz的Celeron处理器上进行，所使用的攻击算法为LLL算法。显然，上述攻击方法是指数时间算法，攻击者不能对NTRU密码体制实施有效攻击。NTRU密码体制的安全性和目前最有影响的RSA体制是一样安全的，到目前为止还没有任何方法说明NTRU密码体制是不安全的。因此，在现阶段NTRU公钥密码体制具备足够高的安全性，可以满足RFID系统的安全性需求[7]。

表1 NTRU公钥密码体制估计的破解时间

3.4 参数选择

NTRU密码体制常用的3个不同的参数集合如表2所示，分别对应3种不同级别的安全性，如表3所示。选取适当的参数可以把解密失败的概率降到 5· 10-5以下。在表2中，Lf=(15,14)表示多项式f的系数中有15个1和14个-1，其他系数为0，Lg,Lφ的含义同Lf。

表2 NTRU密码体制的推荐参数

表3 NTRU密码体制的安全性

4 新的RFID安全协议

4.1 设计目标

基于NTRU公钥密码体制的RFID安全协议须满足如下要求：(1)能够隐藏标签ID信息，使其以密文形态出现，防止泄漏标签的内容隐私。(2)能够隐藏标签的位置信息，使每次访问标签所返回的数据具有随机性，以抵抗对标签的跟踪攻击。(3)系统能抗重放攻击。(4)协议的计算复杂度较低，实现效率较高。(5)能实现标签对阅读器的认证以及阅读器对标签的认证。

4.2 设计思想

标签用NTRU公钥密码体制的公钥加密标签ID信息，继而通过阅读器将密文发送给后台服务器。后台服务器用对应的私钥解密密文，得到标签ID信息。由于攻击者不能成功破译私钥f,Fp和Fq，且在不能破译私钥的情况下，直接破译密文也是非常困难的，因此NTRU公钥体制具有很高的安全性，攻击者不能得到标签的ID信息。标签应内置随机数生成器，使标签发送给阅读器的数据具有随机性。标签将ID和产生的随机数以密文形态发送给阅读器。可利用标签产生的随机数进行标签对阅读器的合法性认证。

为防范重放攻击，在阅读器中也应包含随机数发生器，产生的随机数和密文一起发送给后台服务器。可利用阅读器产生的随机数进行阅读器对标签的合法性认证，从而完成双向安全认证。

4.3 系统初始化

系统生成NTRU公钥密码体制的公钥和私钥(Kpu,Kpr)。其中，Kpu=h；Kpr=(f,Fp,Fq)。将系统所使用的基于NTRU公钥密码体制的加密函数E和公钥Kpu写入标签(Tag)，将解密函数D和私钥Kpr写入后台服务器(Server)。标签(Tag)和阅读器(Reader)均内置随机数发生器和Hash函数运算器。表4为协议工作流程的符号说明。

表4 符号说明

4.4 协议工作流程

基于NTRU公钥密码体制的新型RFID双向安全认证协议如图1所示。

图1 新的RFID安全协议认证过程

基于NTRU密码体制的RFID安全协议的具体认证过程如下：

(1)认证开始时，阅读器利用内置的随机数发生器产生一个随机数r1，并计算其Hash函数值 S1=h(r1)。阅读器将S1和对标签的访问请求Query一并发送至标签。

(2)标签接收到S1和访问请求后，产生另一个随机数r2，并计算其Hash函数值 S2=h(r2)。之后利用已写入标签的加密函数E和公钥Kpu计算 C=EKpu(I D||S1||S2)，并将C发送至阅读器。

(3)阅读器接收到C后，将C连同其在第(1)步中产生 的S1一并发送至后台服务器。后台服务器接收到C和S1后，利用已写入到服务器的解密函数D和私钥Kpr计算，从而得到标签ID,和。接下来验证是否与接收到的S1相等。如果不等，说明攻击者利用前次的通信数据伪装成合法标签实施了重放攻击，认证失败；如果相等，说明标签合法，即实现了阅读器对标签的合法性验证。

5 协议安全性分析

5.1 安全性及计算复杂度比较

对称加密协议虽然能保护标签数据和用户隐私，但由于系统中的标签和阅读器均采用相同的密钥，只要有一个密钥被破译，整个系统的密钥就会全部泄漏。

在基于杂凑和随机化函数的安全协议中，标签收到访问请求后向阅读器返回的不是原本的ID，而是ID的Hash值，因此并不能保证标签数据和用户隐私的安全性。

使用大模数的RSA算法虽然安全性较高，但其对密钥长度的要求通常在1024 bit以上，且在加解密过程中均要进行大量的模幂运算，不仅计算复杂度较高，而且对计算资源的要求也较高，往往需要专门的密码协处理器，不适宜在资源有限的RFID系统中使用。

相比之下，在本文协议的认证中只用到了多项式环之间的加、减、模、乘和求逆等运算，计算复杂度较低，且用NTRU产生密钥较为容易，其加解密过程比RSA等公钥密码体制快1～2个数量级[9]。此外，NTRU公钥密码体制被认为是一种后量子密码[10]，具有抗量子计算的优点，且实现效率高、占用存储空间小、不需要密码协处理器，在资源有限的计算设备(如RFID标签和阅读器)上非常适合，这都是RSA等公钥体制所无法比拟的，因此比较适合在RFID系统中使用。

5.2 安全分析

基于NTRU密码体制的RFID安全协议可以有效地保护标签信息的内容隐私、定位隐私，并能防范重放攻击，能够较好地实现标签和阅读器之间的双向安全认证。

(1)保护标签信息的内容隐私。在协议流程的第(2)步中，标签基于NTRU公钥密码体制对其ID信息进行了加密，并将加密后的数据经阅读器发送至后台服务器。由于NTRU公钥密码体制是基于格中最短向量问题(SVP)的困难性，攻击者对密文进行解密是NP困难的，因此如果攻击者窃取了加密后的数据，因为其无法得到私钥，就无法解密数据以获得标签ID信息，从而保护了标签信息的内容隐私。

(2)保护标签信息的定位隐私[11]。在每次认证过程中，标签都要利用内置的随机数发生器产生新的随机数r2并计算其Hash函数值 S2=h(r2)，然后将数据 C=EKpu(I D||S1||S2)发送至阅读器。在通常情况下，每次认证过程中标签产生的随机数r2是不同的，故其Hash函数值S2也是不同的。因此，在任何2次认证过程中，标签向阅读器发送的数据C也是不同的。这样做的好处是，攻击者无法辨别2次得到的数据是否来源于同一个标签，从而无法通过获取相同的标签数据来定位标签的位置。

(3)能有效防范重放攻击。在每次认证开始时，阅读器都要利用内置的随机数发生器产生新的随机数 r1并计算其Hash函数值 S1=h(r1)发送至标签，然后标签将数据C=EKpu(I D ||S1||S2)发送至阅读器。如果攻击者获取到原始标签发出的数据C并存储，而后企图利用重放该数据C至阅读器来伪装成原始标签，那么由于阅读器在每次认证过程中所产生的r1和S1是不同的，后台服务器通过验证数据C中是否包含新的S1就能马上识别重放攻击。

(4)能实现标签和阅读器之间的双向安全认证[12]。在每次认证过程中，后台服务器对接收到的数据解密，得到和。服务器通过判断与接收到的S1是否相等，来实现阅读器对标签的合法性验证；标签通过判断与自己产生的S2是否相等，来实现标签对阅读器的合法性验证。

6 结束语

本文基于一种运算效率比较高的公钥加密算法提出了一种新型RFID安全协议，并对其性能进行了分析。该协议利用NTRU公钥体制和基于嵌入Hash函数的加密方案来保证RFID标签与阅读器之间的通信安全。研究结果表明，新协议能实现对用户数据及位置隐私的保护，并能及时检测重放攻击，协议运行所需时间和硬件资源均比较少，具有较强的实用性。作为后量子密码之一的NTRU密码，与对称密码和RSA密码相比具有能够抵抗量子计算机破解的优点，并且计算复杂度小、实现效率高。总之，基于NTRU公钥密码体制的新型RFID安全协议具有较高的参考和应用价值，值得深入研究。

[1]周永彬,冯登国.RFID安全协议的设计与分析[J].计算机学报,2006,29(4):581-589.

[2]Weis S,Sarma S,Rivest R,et al.Security and Privacy Aspects of Low-cost Radio Frequency Identification Systems[C]//Proc.of International Conference on Security in Pervasive Computing.Berlin,Germany:[s.n.],2003:454-469.

[3]Ohkubo M,Suzuki K,Kinoshita S.Hash-chain Based Forwardsecure Privacy Protection Scheme for Low-cost RFID[C]//Proc.of Symposium on Cryptography and Information Security.Sendai,Japan:[s.n.],2004:719-724.

[4]Henrici D,Muller P.Hash-based Enhancement of Location Privacy for Radiofrequency Identification Devices Using Varying Identifiers[C]//Proc.of International Workshop on Pervasive Computing and Communication Security.Orlando,USA:[s.n.],2004:149-153.

[5]Molnar D,Wagner D.Privacy and Security in Library RFID:Issues,Practices and Architectures[C]//Proc.of the 11th ACM Conferenceon Computer and Communication Security.Washington D.C.,USA:ACM Press,2004:210-219.

[6]Feldhofer M,Dominikus S,Wolkerstorfer J.Strong Autentication for RFID Systems Using the AES Algorithm[C]//Proc.of CHS’04.Berlin,Germany:[s.n.],2004:357-370.

[7]贺 蕾.NTRU公钥密码体制研究及其在WLAN中的应用设计[D].成都:西南交通大学,2006.

[8]步山岳.NTRU公开密钥体制算法分析与实现[J].计算机工程,2002,28(6):111-113.

[9]步山岳,徐新亚,姚清海.NTRU公开密钥体制安全性分析[J].计算机工程与应用,2002,38(24):180-181.

[10]张焕国,管海明,王后珍.抗量子密码体制的研究现状[C]//中国密码学会2011年会论文集.北京:中国密码学会,2011:1-31.

[11]Chen Yuyi,Lu Junchao,Chen Shini.A Low-cost RFID Authentication Protocol with Location Privacy Protection[C]//Proc.of the 5th International Conference on Information Assurance and Security.Xi’an,China:[s.n.],2009:109-113.

[12]Kang S Y,Lee D G,Lee I Y.A Study on Secure RFID Mutual Authentication Scheme in Pervasive Computing Environment[J].Computer Communications,2008,31(18):4248-4254.