基于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.