基于NTRU密碼體制的RFID安全協(xié)議

何文才，閻曉姮，于源猛，劉培鶴，韓妍妍，趙程程

(1.北京電子科技學(xué)院通信工程系，北京 100070；2.西安電子科技大學(xué)通信工程學(xué)院，西安 710071；3.中共大連市委辦公廳，遼寧 大連 116001)

1 概述

射頻識別(Radio Frequency Identification,RFID)是一種利用射頻信號識別并控制被標(biāo)識物品的非接觸式自動識別技術(shù)。一套完整的RFID系統(tǒng)，由標(biāo)簽(Tag)、閱讀器(Reader)與后臺服務(wù)器(Server)三大部分組成。其中，標(biāo)簽中存有世界上唯一的標(biāo)簽ID信息。標(biāo)簽與后臺服務(wù)器通過閱讀器進行通信，可實現(xiàn)對物品的識別與管理。RFID技術(shù)具有較強的識別能力，被認(rèn)為在不久的將來會取代條形碼技術(shù)。目前，RFID技術(shù)已被廣泛應(yīng)用到身份識別、公共交通管理、物流倉儲管理等多個領(lǐng)域。

由于閱讀器與標(biāo)簽通過公開信道進行通信，在信息傳輸中存在著風(fēng)險，因此研究RFID系統(tǒng)的安全機制具有較高的應(yīng)用價值。在一些特定的環(huán)境下，由于射頻信號傳輸?shù)拈_放性以及計算能力的限制，基于對稱加密體制的認(rèn)證協(xié)議已不能滿足需求，例如保護一些有較高安全性需求的高附加值消費類產(chǎn)品的信息。RSA公鑰算法雖然安全性較高，但其在加解密過程中均要進行大量的指數(shù)運算，不僅計算復(fù)雜度較高，而且對計算資源的要求也較高，不適合在RFID這類計算能力較低的終端產(chǎn)品上使用。

本文提出的RFID安全協(xié)議利用了一種后量子公鑰密碼體制——NTRU密碼體制，其安全性是基于格中最短向量問題(SVP)的困難性，對密文的解密是NP困難的，安全性較高。協(xié)議使用基于嵌入Hash函數(shù)的NTRU公鑰加密方案，標(biāo)簽和服務(wù)器通過檢驗原始Hash值與解密所得Hash值是否相等，以實現(xiàn)閱讀器與標(biāo)簽之間的雙向安全認(rèn)證。

2 相關(guān)工作

現(xiàn)有的RFID安全機制大致可分為3類：基于物理方法的機制，基于密碼的機制和兩者結(jié)合的機制[1]。

早期由于標(biāo)簽芯片在技術(shù)上的限制，人們多考慮用物理方法來保護RFID系統(tǒng)的安全。例如Kill命令、主動干擾和靜電屏蔽等。但這些方法靈活性差、標(biāo)簽損耗大且往往涉及法律問題。

隨著芯片技術(shù)的迅猛發(fā)展，越來越多的人開始研究基于密碼機制的安全協(xié)議?；陔s湊和隨機化函數(shù)的安全協(xié)議利用標(biāo)簽ID信息和后臺服務(wù)器數(shù)據(jù)的關(guān)聯(lián)來保護標(biāo)簽ID信息，如隨機化Hash-Lock協(xié)議[2]、Hash鏈協(xié)議[3]、基于雜湊的ID變化協(xié)議[4]等。但這些協(xié)議在認(rèn)證過程中，標(biāo)簽和服務(wù)器的數(shù)據(jù)往往會不同步，由此會產(chǎn)生拒絕服務(wù)攻擊的問題?；诠蚕砻荑€和偽隨機函數(shù)的安全協(xié)議使用基于預(yù)共享密鑰的偽隨機數(shù)函數(shù)來實現(xiàn)認(rèn)證，如David數(shù)字圖書館RFID協(xié)議[5]。但該協(xié)議對標(biāo)簽有較高的硬件要求，而且當(dāng)標(biāo)簽的數(shù)目很大時，每次認(rèn)證過程中后臺服務(wù)器為比較ID而花費的開銷會非常大，因此不適宜在低成本的RFID系統(tǒng)中使用。一些RFID協(xié)議基于對稱加密算法，如DES和AES[6]等。然而，隨著標(biāo)簽數(shù)量的增加，對稱加密算法的密鑰管理是十分復(fù)雜的，因此并不適合在RFID系統(tǒng)中使用。如果采用公鑰密碼算法，可以解決密鑰管理、隱私保護等RFID系統(tǒng)需要解決的問題。然而典型的RSA公鑰加密算法在加解密過程中需要進行復(fù)雜的指數(shù)運算，計算復(fù)雜度過高，因此也不適合在RFID系統(tǒng)中使用。

3NTRU公鑰密碼體制

3.1 NTRU公鑰密碼體制的加解密

NTRU公鑰密碼體制的密鑰生成、加密及解密過程如下[7]：

(1)密鑰生成

選取3個整數(shù)參數(shù)(N,p,q)，4個多項式集合Lf,Lg,Lφ,Lm，其系數(shù)為整數(shù)，次數(shù)為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)加密

發(fā)送方需要加密的明文消息m∈Lm，隨機選取多項式φ∈Lφ，利用公鑰h計算：

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

(3)解密

接收方對密文做如下操作：1)利用私鑰f計算a≡f·c(modq)，其中，多項式a的系數(shù)選在區(qū)間內(nèi)。2)利用私鑰Fp計算 Fp·a(mod p)，所得結(jié)果即明文消息m。

3.2 加解密的計算復(fù)雜性

分析加解密過程不難看出，NTRU算法的計算對象只包括多項式環(huán)之間的加、減、模、乘和求逆等運算，而多項式環(huán)之間的加、減運算與普通多項式的加、減運算是完全相同的，可見NTRU公鑰密碼體制的計算復(fù)雜度較低。國內(nèi)外對NTRU算法的研究證明，NTRU算法是公鑰體制中最快的、也是較為容易實現(xiàn)的算法。

在相同安全級別下，NTRU算法要比其他公鑰算法快得多，用Tumbler軟件工具包執(zhí)行NTRU的速度比RSA快100多倍。用NTRU算法產(chǎn)生密鑰的速度也很快，密鑰比特數(shù)也較小，從而降低了其對帶寬、處理器、存儲器的性能要求[8]。

3.3 NTRU公鑰密碼體制的安全性分析

攻擊NTRU公鑰密碼體制的方法主要有3種：(1)格攻擊；(2)不完備解密攻擊；(3)選擇密文攻擊。其中最有效的攻擊是格攻擊。NTRU的安全性是基于數(shù)論中的一個著名的數(shù)學(xué)難題，即在一個維數(shù)非常大的格中尋找一個很短的向量?；謴?fù)明文消息m和私鑰f等價于在特定格中尋找最短的向量。理論上可以通過窮舉法找到最短向量，然而在實際中這種方法是不可行的。特別是在格的維數(shù)很大的情況下，這種方法的計算量是相當(dāng)可觀的。解決這類難題的最好方法是LLL算法及其改進，利用這些算法可在多項式時間內(nèi)找到最短向量。同樣如果格的維數(shù)很大，也不能找到最短向量。

NTRU公鑰密碼體制的破解時間可利用lbT≥AN+B進行粗略估計，其中，A,B均為常數(shù)，可通過實驗得出。NTRU公鑰密碼體制估計的破解時間如表1所示，其中，MIPS-years表示以每秒處理100萬條指令的處理器運算一年為單位。整個實驗在400 MHz的Celeron處理器上進行，所使用的攻擊算法為LLL算法。顯然，上述攻擊方法是指數(shù)時間算法，攻擊者不能對NTRU密碼體制實施有效攻擊。NTRU密碼體制的安全性和目前最有影響的RSA體制是一樣安全的，到目前為止還沒有任何方法說明NTRU密碼體制是不安全的。因此，在現(xiàn)階段NTRU公鑰密碼體制具備足夠高的安全性，可以滿足RFID系統(tǒng)的安全性需求[7]。

表1 NTRU公鑰密碼體制估計的破解時間

3.4 參數(shù)選擇

NTRU密碼體制常用的3個不同的參數(shù)集合如表2所示，分別對應(yīng)3種不同級別的安全性，如表3所示。選取適當(dāng)?shù)膮?shù)可以把解密失敗的概率降到 5· 10-5以下。在表2中，Lf=(15,14)表示多項式f的系數(shù)中有15個1和14個-1，其他系數(shù)為0，Lg,Lφ的含義同Lf。

表2 NTRU密碼體制的推薦參數(shù)

表3 NTRU密碼體制的安全性

4 新的RFID安全協(xié)議

4.1 設(shè)計目標(biāo)

基于NTRU公鑰密碼體制的RFID安全協(xié)議須滿足如下要求：(1)能夠隱藏標(biāo)簽ID信息，使其以密文形態(tài)出現(xiàn)，防止泄漏標(biāo)簽的內(nèi)容隱私。(2)能夠隱藏標(biāo)簽的位置信息，使每次訪問標(biāo)簽所返回的數(shù)據(jù)具有隨機性，以抵抗對標(biāo)簽的跟蹤攻擊。(3)系統(tǒng)能抗重放攻擊。(4)協(xié)議的計算復(fù)雜度較低，實現(xiàn)效率較高。(5)能實現(xiàn)標(biāo)簽對閱讀器的認(rèn)證以及閱讀器對標(biāo)簽的認(rèn)證。

4.2 設(shè)計思想

標(biāo)簽用NTRU公鑰密碼體制的公鑰加密標(biāo)簽ID信息，繼而通過閱讀器將密文發(fā)送給后臺服務(wù)器。后臺服務(wù)器用對應(yīng)的私鑰解密密文，得到標(biāo)簽ID信息。由于攻擊者不能成功破譯私鑰f,Fp和Fq，且在不能破譯私鑰的情況下，直接破譯密文也是非常困難的，因此NTRU公鑰體制具有很高的安全性，攻擊者不能得到標(biāo)簽的ID信息。標(biāo)簽應(yīng)內(nèi)置隨機數(shù)生成器，使標(biāo)簽發(fā)送給閱讀器的數(shù)據(jù)具有隨機性。標(biāo)簽將ID和產(chǎn)生的隨機數(shù)以密文形態(tài)發(fā)送給閱讀器?？衫脴?biāo)簽產(chǎn)生的隨機數(shù)進行標(biāo)簽對閱讀器的合法性認(rèn)證。

為防范重放攻擊，在閱讀器中也應(yīng)包含隨機數(shù)發(fā)生器，產(chǎn)生的隨機數(shù)和密文一起發(fā)送給后臺服務(wù)器?？衫瞄喿x器產(chǎn)生的隨機數(shù)進行閱讀器對標(biāo)簽的合法性認(rèn)證，從而完成雙向安全認(rèn)證。

4.3 系統(tǒng)初始化

系統(tǒng)生成NTRU公鑰密碼體制的公鑰和私鑰(Kpu,Kpr)。其中，Kpu=h；Kpr=(f,Fp,Fq)。將系統(tǒng)所使用的基于NTRU公鑰密碼體制的加密函數(shù)E和公鑰Kpu寫入標(biāo)簽(Tag)，將解密函數(shù)D和私鑰Kpr寫入后臺服務(wù)器(Server)。標(biāo)簽(Tag)和閱讀器(Reader)均內(nèi)置隨機數(shù)發(fā)生器和Hash函數(shù)運算器。表4為協(xié)議工作流程的符號說明。

表4 符號說明

4.4 協(xié)議工作流程

基于NTRU公鑰密碼體制的新型RFID雙向安全認(rèn)證協(xié)議如圖1所示。

圖1 新的RFID安全協(xié)議認(rèn)證過程

基于NTRU密碼體制的RFID安全協(xié)議的具體認(rèn)證過程如下：

(1)認(rèn)證開始時，閱讀器利用內(nèi)置的隨機數(shù)發(fā)生器產(chǎn)生一個隨機數(shù)r1，并計算其Hash函數(shù)值 S1=h(r1)。閱讀器將S1和對標(biāo)簽的訪問請求Query一并發(fā)送至標(biāo)簽。

(2)標(biāo)簽接收到S1和訪問請求后，產(chǎn)生另一個隨機數(shù)r2，并計算其Hash函數(shù)值 S2=h(r2)。之后利用已寫入標(biāo)簽的加密函數(shù)E和公鑰Kpu計算 C=EKpu(I D||S1||S2)，并將C發(fā)送至閱讀器。

(3)閱讀器接收到C后，將C連同其在第(1)步中產(chǎn)生 的S1一并發(fā)送至后臺服務(wù)器。后臺服務(wù)器接收到C和S1后，利用已寫入到服務(wù)器的解密函數(shù)D和私鑰Kpr計算，從而得到標(biāo)簽ID,和。接下來驗證是否與接收到的S1相等。如果不等，說明攻擊者利用前次的通信數(shù)據(jù)偽裝成合法標(biāo)簽實施了重放攻擊，認(rèn)證失??；如果相等，說明標(biāo)簽合法，即實現(xiàn)了閱讀器對標(biāo)簽的合法性驗證。

5 協(xié)議安全性分析

5.1 安全性及計算復(fù)雜度比較

對稱加密協(xié)議雖然能保護標(biāo)簽數(shù)據(jù)和用戶隱私，但由于系統(tǒng)中的標(biāo)簽和閱讀器均采用相同的密鑰，只要有一個密鑰被破譯，整個系統(tǒng)的密鑰就會全部泄漏。

在基于雜湊和隨機化函數(shù)的安全協(xié)議中，標(biāo)簽收到訪問請求后向閱讀器返回的不是原本的ID，而是ID的Hash值，因此并不能保證標(biāo)簽數(shù)據(jù)和用戶隱私的安全性。

使用大模數(shù)的RSA算法雖然安全性較高，但其對密鑰長度的要求通常在1024 bit以上，且在加解密過程中均要進行大量的模冪運算，不僅計算復(fù)雜度較高，而且對計算資源的要求也較高，往往需要專門的密碼協(xié)處理器，不適宜在資源有限的RFID系統(tǒng)中使用。

相比之下，在本文協(xié)議的認(rèn)證中只用到了多項式環(huán)之間的加、減、模、乘和求逆等運算，計算復(fù)雜度較低，且用NTRU產(chǎn)生密鑰較為容易，其加解密過程比RSA等公鑰密碼體制快1～2個數(shù)量級[9]。此外，NTRU公鑰密碼體制被認(rèn)為是一種后量子密碼[10]，具有抗量子計算的優(yōu)點，且實現(xiàn)效率高、占用存儲空間小、不需要密碼協(xié)處理器，在資源有限的計算設(shè)備(如RFID標(biāo)簽和閱讀器)上非常適合，這都是RSA等公鑰體制所無法比擬的，因此比較適合在RFID系統(tǒng)中使用。

5.2 安全分析

基于NTRU密碼體制的RFID安全協(xié)議可以有效地保護標(biāo)簽信息的內(nèi)容隱私、定位隱私，并能防范重放攻擊，能夠較好地實現(xiàn)標(biāo)簽和閱讀器之間的雙向安全認(rèn)證。

(1)保護標(biāo)簽信息的內(nèi)容隱私。在協(xié)議流程的第(2)步中，標(biāo)簽基于NTRU公鑰密碼體制對其ID信息進行了加密，并將加密后的數(shù)據(jù)經(jīng)閱讀器發(fā)送至后臺服務(wù)器。由于NTRU公鑰密碼體制是基于格中最短向量問題(SVP)的困難性，攻擊者對密文進行解密是NP困難的，因此如果攻擊者竊取了加密后的數(shù)據(jù)，因為其無法得到私鑰，就無法解密數(shù)據(jù)以獲得標(biāo)簽ID信息，從而保護了標(biāo)簽信息的內(nèi)容隱私。

(2)保護標(biāo)簽信息的定位隱私[11]。在每次認(rèn)證過程中，標(biāo)簽都要利用內(nèi)置的隨機數(shù)發(fā)生器產(chǎn)生新的隨機數(shù)r2并計算其Hash函數(shù)值 S2=h(r2)，然后將數(shù)據(jù) C=EKpu(I D||S1||S2)發(fā)送至閱讀器。在通常情況下，每次認(rèn)證過程中標(biāo)簽產(chǎn)生的隨機數(shù)r2是不同的，故其Hash函數(shù)值S2也是不同的。因此，在任何2次認(rèn)證過程中，標(biāo)簽向閱讀器發(fā)送的數(shù)據(jù)C也是不同的。這樣做的好處是，攻擊者無法辨別2次得到的數(shù)據(jù)是否來源于同一個標(biāo)簽，從而無法通過獲取相同的標(biāo)簽數(shù)據(jù)來定位標(biāo)簽的位置。

(3)能有效防范重放攻擊。在每次認(rèn)證開始時，閱讀器都要利用內(nèi)置的隨機數(shù)發(fā)生器產(chǎn)生新的隨機數(shù) r1并計算其Hash函數(shù)值 S1=h(r1)發(fā)送至標(biāo)簽，然后標(biāo)簽將數(shù)據(jù)C=EKpu(I D ||S1||S2)發(fā)送至閱讀器。如果攻擊者獲取到原始標(biāo)簽發(fā)出的數(shù)據(jù)C并存儲，而后企圖利用重放該數(shù)據(jù)C至閱讀器來偽裝成原始標(biāo)簽，那么由于閱讀器在每次認(rèn)證過程中所產(chǎn)生的r1和S1是不同的，后臺服務(wù)器通過驗證數(shù)據(jù)C中是否包含新的S1就能馬上識別重放攻擊。

(4)能實現(xiàn)標(biāo)簽和閱讀器之間的雙向安全認(rèn)證[12]。在每次認(rèn)證過程中，后臺服務(wù)器對接收到的數(shù)據(jù)解密，得到和。服務(wù)器通過判斷與接收到的S1是否相等，來實現(xiàn)閱讀器對標(biāo)簽的合法性驗證；標(biāo)簽通過判斷與自己產(chǎn)生的S2是否相等，來實現(xiàn)標(biāo)簽對閱讀器的合法性驗證。

6 結(jié)束語

本文基于一種運算效率比較高的公鑰加密算法提出了一種新型RFID安全協(xié)議，并對其性能進行了分析。該協(xié)議利用NTRU公鑰體制和基于嵌入Hash函數(shù)的加密方案來保證RFID標(biāo)簽與閱讀器之間的通信安全。研究結(jié)果表明，新協(xié)議能實現(xiàn)對用戶數(shù)據(jù)及位置隱私的保護，并能及時檢測重放攻擊，協(xié)議運行所需時間和硬件資源均比較少，具有較強的實用性。作為后量子密碼之一的NTRU密碼，與對稱密碼和RSA密碼相比具有能夠抵抗量子計算機破解的優(yōu)點，并且計算復(fù)雜度小、實現(xiàn)效率高?？傊?，基于NTRU公鑰密碼體制的新型RFID安全協(xié)議具有較高的參考和應(yīng)用價值，值得深入研究。

[1]周永彬,馮登國.RFID安全協(xié)議的設(shè)計與分析[J].計算機學(xué)報,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中的應(yīng)用設(shè)計[D].成都:西南交通大學(xué),2006.

[8]步山岳.NTRU公開密鑰體制算法分析與實現(xiàn)[J].計算機工程,2002,28(6):111-113.

[9]步山岳,徐新亞,姚清海.NTRU公開密鑰體制安全性分析[J].計算機工程與應(yīng)用,2002,38(24):180-181.

[10]張煥國,管海明,王后珍.抗量子密碼體制的研究現(xiàn)狀[C]//中國密碼學(xué)會2011年會論文集.北京:中國密碼學(xué)會,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.