代理計算簽名及其在RFID認證中的應用

高員，李琳，肖靜，趙成志

（工業(yè)和信息化部電子第五研究所，廣東 廣州 510610）

代理計算簽名及其在RFID認證中的應用

高員，李琳，肖靜，趙成志

（工業(yè)和信息化部電子第五研究所，廣東 廣州 510610）

射頻識別 （RFID）是物聯(lián)網(wǎng)中實現(xiàn)物品標識的一項關鍵技術，但RFID標簽的計算能力十分有限，導致傳統(tǒng)的公鑰密碼技術很難有效地應用到RFID認證技術中，限制了RFID的應用范圍和提供服務的形式。針對讀卡器和標簽計算資源不對稱的特點，提出一種新的簽名算法——代理計算簽名，將傳統(tǒng)的簽名技術中耗能的復雜運算交給讀卡器 （驗證方）來完成，從而實現(xiàn)標簽對消息的簽名，并仍能保持簽名的安全性，解決了RFID標簽很難計算數(shù)字簽名的困難問題。結(jié)合Rabin型數(shù)字簽名和加密算法，進一步地給出了基于代理計算簽名的RFID認證方案，實現(xiàn)了標簽與讀卡器間的雙向認證，大大地降低了標簽的實現(xiàn)成本。

射頻識別；代理計算；簽名；認證

0 引言

射頻識別技術 （RFID）是物聯(lián)網(wǎng)[1]中實現(xiàn)物品標識的一項關鍵技術[2]，由標簽、閱讀器和天線3個部分組成[3-4]。它利用射頻信號通過空間耦合 （交換磁場或電磁場）來實現(xiàn)無接觸信息傳遞，并通過所傳遞的信息達到識別的目的。射頻識別技術已被廣泛地應用于工業(yè)自動化、商業(yè)自動化、交通運輸控制管理、軍事、商品防偽、監(jiān)視、定位和工業(yè)等眾多領域。

由于RFID系統(tǒng)的標簽資源有限、標簽信息易被非授權訪問，解決RFID中標簽與讀卡器之間的相互認證和信息保密就成為擴展RFID應用的關鍵問題。

本文針對讀卡器和標簽計算資源不對稱的特點，提出一種代理計算簽名算法，將傳統(tǒng)的簽名計算中耗能的復雜運算交給讀卡器 （驗證方）來完成，從而實現(xiàn)標簽對消息的簽名，并仍能保持簽名的安全性。結(jié)合Rabin數(shù)字簽名和加密算法[5]，本文進一步地給出基于代理計算簽名的RFID認證方案，實現(xiàn)了標簽與讀卡器之間的雙向認證，解決了RFID標簽資源有限的問題。

1 代理計算簽名算法

本文提出的代理計算簽名算法是基于橢圓曲線簽名算法ECDSA[6-8]設計的。

1.1 代理計算簽名算法設計

1.1.1 密鑰生成

用戶A具有域參數(shù)組D=（q，F(xiàn)R，a，b，G，n，h），對消息m進行簽名。A在區(qū)間 [1，n-1]內(nèi)選擇隨機整數(shù) （x，t），計算Q=xG=（x1，y1），T=t-1G=（x2，y2）； （Q，T）為公鑰， （x，t）為私鑰，其中：x為簽名私鑰，t為掩蔽私鑰。

1.1.2 代理計算簽名

a）簽名者A選取秘密隨機數(shù)k，1≤k≤n-1，計算u=kt mod n，發(fā)送u給簽名驗證者B。

b）B計算uT=（x3，y3），將x3轉(zhuǎn)換為整數(shù)，計算r=x3mod n。若r=0，則返回步驟a），A重新選擇隨機數(shù)k；否則B將r發(fā)送給A。

c）A以k作為會話密鑰，計算s=k-1（H（m）+rx）mod n。若s=0，則返回步驟a），A重新選擇隨機數(shù)k；否則 （s，r）即為用戶A對消息m的簽名。

1.1.3 驗證簽名

為驗證用戶A對消息m的簽名 （s，r），用戶B需獲得A的公鑰 （Q，T）和域參數(shù)組D=（q，F(xiàn)R，a，b，G，n，h），并對D和 （Q，T）的有效性進行確認，然后用戶B進行如下操作：

a）計算w=s-1mod n。

b）計算u1=H （m）w mod n，u2=rw mod n。

c）計算X=u1G+u2Q。

d）若X=0，則為非法簽名；否則將X的橫坐標轉(zhuǎn)換為整數(shù)x1，并計算v=x1 mod n。

e）若v=r，則接受簽名。

1.2 代理計算簽名算法分析

1.2.1 簽名的正確性分析

若簽名 （s，r）確實是消息m的合法簽名，則s=k-1（H（m）+rx）mod n，重新整理得：

k=s-1（H （m）+rx）=s-1H （m）+s-1rx=w H（m）+ wrx=u1+u2xmod n

于是X=u1G+u2Q=（u1+u2x）G=kG，uT=ktT= ktt-1G=kG，因此v=r為所需。

1.2.2 簽名的安全性分析

本文提出的代理計算簽名主要用于解決誠實的驗證者對簽名者真實性的驗證問題，因此，代理計算簽名的安全性問題主要考慮簽名的不可偽造性問題。以下我們基于ECDSA簽名給出兩個定理，以說明代理計算簽名的安全性。

a）定理1：如果ECDSA簽名是安全的，則基于ECDSA的代理計算簽名也是安全的。

證明：如果ECDSA簽名是安全的，則表明ECDSA簽名是不可偽造的。即給定消息m，不具有私鑰x的人無法產(chǎn)生m的正確ECDSA簽名，或找到兩個不同的消息使其具有相同的簽名在計算上不可行。在本文的代理計算簽名中，s的計算是由簽名者本人完成的，r的運算通過了驗證者的代理計算。由于r是可以公開的，因此，對于定理1只需證明，攻擊者由計算r的兩個參數(shù)u=kt mod n和T計算出k在計算上是不可行的。

由T計算t需要解決ECDLP問題，并需要進行求逆運算，而在mod n運算下任選k′都存在t′，使得k′t′≡kt mod n，因此，攻擊者只能通過驗證所選t′是否滿足T=t′-1G來判斷所選取t′的正確性。但是，如果攻擊者能夠在多項式時間內(nèi)判斷出正確的t，則破解了ECDLP問題。因此，這是不可行的，也即在多項式時間內(nèi)由代理計算中的兩個參數(shù)計算出簽名所使用的正確的k是不可行的。所以結(jié)論成立。

b）定理2：如果ECDSA簽名是安全的，則在相同的掩蔽私鑰t下，即使攻擊者獲得多個代理計算請求參數(shù)u1=k1t mod n，u2=k2t mod n，…，uh=kht mod n和T，h是產(chǎn)生代理計算簽名的次數(shù)，所產(chǎn)生的所有代理計算簽名也都是安全的。

證明：同定理1的證明思路，這時只需證明，攻擊者由獲得的多個代理計算請求參數(shù)u1=k1t mod n，u2=k2t mod n，…，uh=kht mod n和T計算出k在計算上是不可行的。在mod n運算下任選t′都存在一組對應的隨機數(shù)k1′，k2′，…，kh′，使得k1′t′，k2′t′，…，kh′t′等于k1t，k2t，…，kht，這只需令ki′=kitt′-1，i=1，2，…，h。因此，攻擊者只能通過驗證所選t′是否滿足T=t′-1G來判斷所選取t′的正確性。但是，如果攻擊者能夠在多項式時間內(nèi)判斷出正確的t，則破解了ECDLP問題。因此，這是不可行的，也即在多項式時間內(nèi)由代理計算中獲得的多個參數(shù)計算出簽名所使用的正確的會話密鑰k1，k2，…，kh是不可行的。所以結(jié)論成立。

2 基于代理計算簽名的RFID認證方案

基于上一章節(jié)的代理計算簽名算法，結(jié)合Rabin公鑰體制，本章設計將標簽中的復雜運算交給讀卡器來完成的RFID認證方案。

RFID系統(tǒng)采用基于證書的方式來管理密鑰，可信第三方 （CA）基于Rabin型數(shù)字簽名來管理證書，其私鑰是 （p，q），公鑰是nCA=pq。

讀卡器采用Rabin公鑰加密體制[5]，CA為讀卡器頒發(fā)的簽名證書標記為Certr，私鑰是 （e，d），公鑰是nr=ed。

標簽采用代理計算簽名體制，CA為標簽頒發(fā)的簽名證書標記為Certt，私鑰是 （x，t），公鑰是（Q=xG，T=t-1G），橢圓曲線域參數(shù)D=（q，F(xiàn)R，a，b，G，n，h）。

2.1 RFID雙向認證方案設計

2.1.1 初始化

系統(tǒng)為每一個標簽和讀卡器分配一個惟一的標識碼，分別用UIDt和UIDr表示；選擇hash鏈作為隨機數(shù)產(chǎn)生器PRNG（） （即每次選取的隨機數(shù)都是對上次通信所選隨機數(shù)hash值的計算），一個對稱加密算法 E，hash函數(shù)H（）。 將 [nCA， nr，UIDr，H（）]存入到標簽的存儲器中，將 [nCA，Q，T，UIDt，H（）]存入到讀卡器中。

2.1.2 標簽與讀卡器的雙向認證過程

RFID標簽與讀卡器相互認證過程如圖1所示。

圖1 RFID標簽與讀卡器相互認證過程示意圖

a）讀卡器選取隨機數(shù)z，向標簽發(fā)起認證請求，將 （Query，Certr，z）發(fā)送給標簽。

b）標簽用CA的公鑰nCA對該證書加以驗證，若成立，則說明該讀卡器是經(jīng)過可信第三方認證的授權讀卡器。標簽選取隨機數(shù)f作為后續(xù)通信的會話密鑰 （對稱密鑰），利用公鑰nr對f進行Rabin型公鑰加密，即計算a=f（f+z）mod nr，其中z是對f進行Rabin型公鑰加密時選取的隨機數(shù)。標簽選取秘密隨機數(shù)k，1≤k≤n-1，計算u=kt mod n，將 （a，b）=Ef（u，Certt）發(fā)送給讀卡器。

c）讀卡器收到 （a，b）后，首先，用私鑰（e，d）解密a得出f，并檢驗隨機數(shù)z的正確性；然后，用f解密b得到 （u，Certt），驗證證書Certt后，計算uT=（x3，y3），將x3轉(zhuǎn)換為整數(shù)，計算r= x3mod n。若r=0，則返回a），標簽重新選擇隨機數(shù)k；否則，讀卡器將f的hash值H（f）、Ef（r||H（r）） （其中H（r）是為了保護消息完整性）發(fā)送給標簽。

e）標簽收到H（f）′后，驗證H（f）′=H（f）是否成立。若不成立，則終止通信；否則，完成標簽對讀卡器的認證。標簽對E f（r||H（r））解密后得到r，計算s=k-1（H（f）+rx）mod n， （s，r）即為標簽對會話密鑰f的簽名，將 （s，r）發(fā)送給讀卡器。

f）讀卡器收到 （s，r）后，驗證簽名 （s，r）是否有效，若有效，完成讀卡器對標簽的認證；否則，終止通信并審計。

2.2 RFID雙向認證方案分析

2.2.1 安全性分析

本文提出的RFID認證方案，不僅能夠?qū)崿F(xiàn)信息的保密功能及標簽與讀卡器之間身份的相互認證，還能夠滿足抵抗信息泄露、竊聽、重放攻擊、流量分析攻擊和前向攻擊等安全要求。本節(jié)中我們將對RFID認證協(xié)議所能抵抗的各類攻擊進行分析：

a）防止非法讀取

因為標簽和讀卡器都需先進行身份認證，才能相互交換數(shù)據(jù)，因此，可以有效地防止非法讀取。

b）防止竊聽

由于讀卡器和標簽之間的通信信道是不安全的信道，所以非法用戶可以訪問該信道。在方案第1步中，讀卡器發(fā)送的Certr是經(jīng)過CA簽名的公鑰證書，在第2步中讀卡器需對隨機數(shù)z的正確性進行驗證。因此，第1步中發(fā)送的消息 （Query，Certr，z）都是可以對外開放的，在后續(xù)通信中，標簽與讀卡器間通信時發(fā)送的是hash值和加密的信息，非法用戶不能竊聽到數(shù)據(jù)內(nèi)容。

c）前向安全性

如果一個非法用戶可以破壞一個標簽，擁有它現(xiàn)在保存的全部數(shù)據(jù)，那么它就可以追蹤該標簽以前的會話，這就是前向攻擊。在本章的方案中，由于隨機數(shù)使用的是hash鏈，所以標簽每次選取的隨機數(shù)f和k都與上次不同，即使攻擊者截取了某次標簽的輸出，也不能根據(jù)此值推算出標簽以前的輸出，因此，可以有效地防止前向攻擊。

e）防止重放攻擊

攻擊者事先記錄標簽發(fā)出的信息，當讀卡器與標簽再次通信時，攻擊者通過記錄下的標簽信息來偽裝成合法標簽與讀卡器進行通信。但是，由于標簽中的隨機數(shù)構建了一個hash鏈，保證了每次通信時使用的隨機數(shù)是不同的，因此，攻擊者記錄的信息不會被再次利用。讀卡器可以使用隨機數(shù)z來判斷收到的消息a是否被重放。

f）防止位置追蹤

由于在當前的協(xié)議中，標簽在每次通信中輸出的信息都是不固定的，并且hash函數(shù)的輸出也是不可預知的，因此，攻擊者無法根據(jù)固定的輸出來對標簽的位置進行跟蹤。

2.2.2 性能分析

RFID安全認證協(xié)議不僅要解決安全性方面的問題，由于RFID標簽的有限存儲容量和計算能力，認證協(xié)議也必須在計算時間和存儲容量方面進行考慮，盡量使標簽的計算量不要過大，存儲數(shù)據(jù)盡量地少，這樣才能最大程度地降低標簽的成本，從而降低整個RFID系統(tǒng)的成本。下面我們通過統(tǒng)計標簽在整個認證過程中所需的計算量來對協(xié)議進行評估。表1即為整個認證過程中標簽涉及到的計算。

表1 標簽在基于公鑰的RFID認證方案中的計算量

在驗證讀卡器的公鑰證書和建立會話密鑰的過程中，標簽需要進行一次模nCA上的平方運算、一次hash運算和模nr上的一次加法、一次乘法運算。

在整個代理計算簽名技術實現(xiàn)的過程中，標簽需要進行3次hash運算、1次對稱加密運算、1次對稱解密運算和模n上的1次求逆運算，以及3次乘法運算、1次加法運算。

3 結(jié)束語

本文提出了一種代理計算簽名技術，并將其應用到RFID認證當中，實現(xiàn)了讀卡器和標簽的、基于公鑰技術的雙向認證。該技術解決了讀卡器不能進行復雜耗能運算的困難問題，使得RFID系統(tǒng)的標簽管理更加方便、靈活。在本文給出的RFID認證方案中，標簽所需要的運算量非常小，既保障了系統(tǒng)實現(xiàn)的靈活性和可擴展性，又極大地降低了標簽的實現(xiàn)成本。如何設計更為安全、高效的代理計算簽名，以及如何實現(xiàn)對RSA類簽名的代理計算都是值得進一步研究的問題。

[1]AKYILDIZ I F，SU W，SANKARASUBRAMANIAM Y，et al.Wireless sensor networks：a survey[J].Computer Networks，2002，38：393-422.

[2]陳積明，林瑞仲，孫優(yōu)賢.無線傳感器網(wǎng)絡的信息處理研究 [J].儀器儀表學報，2006，27（9）：1107-1111.

[3]游戰(zhàn)清，李蘇劍.無線射頻識別技術 （RFID）理論與應用 [M].北京：電子工業(yè)出版社，2004.

[4]周曉光，王曉華，王偉.射頻識別 （RFID）系統(tǒng)設計、仿真與應用 [M].北京：人民郵電出版社，2008.

[5]HANKERSON D，MENEZES A，VANSTONE S.橢圓曲線密碼學導論 [M].張煥國，譯.北京：電子工業(yè)出版社，2005：22-66.

[6]MILLER.V.Use of elliptic curves in cryptography[C]// Advances in Cryptology-Proceedings of CRYPTO’ 85. 1986：417-426.

[7]KOBLITZN.Elliptic curve cryptosystems[J].Math.Comp.，1987，48（5）：203-209.

[8]RABIN M O.Digitalized signatures and public-key functions as intractable as factorization[R].MIT/LCS/TR-212，MIT Laboratory for Computer Science，1979.

Com puting-Comm ission Signature and its App lication in RFID Authentication

GAO Yuan，LILin，XIAO Jing，ZHAO Cheng-zhi
（CEPREI，Guangzhou 510610，China）

RFID is one of the key technologies for items identification in Internet of things，while the limited computing ability of RFID tagsmake it difficult to apply traditional public key cryptography to RFID authentication efficiently， which greatly limits the scope of RFID applications and the forms of providing services.A new signature algorithm called computingcomm ission signature algorithm is p resented aim at the character that the computing resources of readers and RFID tags are asymmetric.In our signature algorithm， we leaved the complex energy-consuming computation in traditional signature algorithm to the verifier（readers）so that the signature can be generated on tags and the security of the signature is still satisfied.Our signature algorithm solved the difficult problem of computing digital signature in RFID tags. Combining with Rabin-type signature and encryption algorithm，a RFID authentication schem e based on computing-comm ission signature is further proposed，which achieved mutual authentication between readers and tags.It greatly reduced the implementation cost of tags.

Radio Frequency Identification（RFID）；computing-commission；signature；Authentication

TP 309

：A

：1672-5468（2015）01-0024-06

10.3969/j.issn.1672-5468.2015.01.006

2014-08-27

2014-12-30

高員 （1986-），女，河北衡水人，工業(yè)和信息化部電子第五研究所軟件質(zhì)量工程研究中心助理工程師，碩士，主要從事信息安全等級保護測評、公鑰密碼學與信息安全等研究工作。