一種基于零知識證明的RFID技術鑒別協(xié)議

      1、引 言  

　　RFID技術是當前研究的一個熱點，其采用無線信號進行無接觸的雙向信息傳輸，一方面具有極大的方便性和靈活性，另一方面增加了信息被竊取的風險。無線信道與具有保密性的有線信道不同，無線信道的一個特征是其公開性，任何人只要擁有相應頻段的接收設備，就可以對無線信道進行監(jiān)聽，因此和有線信道相比，無線信道更容易被竊聽而且不容易被發(fā)現(xiàn)。對于EPC（電子產品代碼）Class0／O+標準中沒有任何加密措施和鑒別機制的情況，已經引發(fā)了廣泛的關于保護消費者隱私權的激烈討論。而對于遠作用距離的有源RFID系統(tǒng)，則具有更大的安全隱患。因此研究如何在RFID系統(tǒng)實現(xiàn)高效的身份鑒別是非常有必要的。 

　　鑒別又叫認證，是用來證明某人或某事是否真實、可靠或者有效的過程，他通過驗證稱謂者的一個或多個參數(shù)的真實性或者有效性來達到驗證其是否名副其實的目的。鑒別在現(xiàn)實生活中的形式多種多樣，如對人的鑒別，一般通過口令或者人的生理特征（聲音、指紋、視網膜等）進行鑒別。本文主要討論RFID系統(tǒng)的鑒別，其鑒別的過程是基于零知識證明技術的。 

　　身份鑒別是雙向的，即RFID卡與終端要相互鑒別對方身份。目前，在RFID系統(tǒng)存在的安全問題（如保護消費者隱私權）中，攻擊者所采用的主要攻擊方式是對RFID卡信息的非法竊取，而不是偽造RFID卡，因此本文將研究重點放在RFID卡對終端的鑒別問題上。 

　　2、目前常用的兩種鑒別體制的缺陷 

　　鑒別分為2種：對稱鑒別和非對稱鑒別。對稱鑒別是指主機和稱謂者預先共享了某個秘密信息，或者主機知道稱謂者某個秘密信息的映象，主機通過驗證稱謂者是否知道這個秘密來達到鑒別的目的；非對稱鑒別是指主機不知道稱謂者用于證明其身份的某個秘密（包括秘密的映象），而僅通過與稱謂者的秘密對應的公開密鑰來鑒別其真?zhèn)巍?nbsp;

　　2.1對稱鑒別體制 

　　在智能卡中應用較多的是對稱鑒別體制，采用的是DES對稱加密算法。在通信之前，卡要對終端進行驗證，對稱鑒別速度較快，對智能卡的性能、資源要求較低，但是其在使用之前一般需要有一個集中的卡的發(fā)行過程，以便于密鑰的分發(fā)，因此只能適合于比較單一的領域（或單一的人群）使用，如移動電話卡、銀行卡等。對于更廣泛的電子商務、物流管理來講，非對稱鑒別更適合，目前已經出現(xiàn)了一系列的基于智能卡的加密接口規(guī)范。 

　　2.2非對稱鑒別體制 

　　非對稱鑒別體制與對稱鑒別體制相比具有更大的靈活性，他并未完全包括某一特定的密碼算法，卻經常以RSA算法為基礎進行加工。RSA算法是密碼學理論上的一個重大突破，他成功地解決了密鑰分發(fā)的問題，但在實際應用中卻存在以下困難： 

　?。?）RSA算法的保密強度是建立在特定的數(shù)學問題求解的困難性上的，他可以表示成簡單的數(shù)學公式，然而隨著數(shù)學的發(fā)展，許多現(xiàn)在看來難以解決的問題可能在不久的將來會得到解決，而諸如DES之類的對稱密碼算法則難以表示成一個確定的數(shù)學形式，其保密強度因此相應地要高。 

　?。?）RSA算法中密鑰的生成較對稱密碼體制而言要復雜得多，特別是大素數(shù)p和q的生成比較復雜。倘若一個電子標簽應用系統(tǒng)中只采用一對p和q，一旦他們被泄密，則整個密碼系統(tǒng)失效；而若每個電子標簽采用不同的p和q，則p和q的生成任務極其繁重。 

　?。?）受電子標簽資源的限制，在電子標簽中實現(xiàn)RSA算法非常困難，主要是實現(xiàn)RSA算法中的大數(shù)乘方取模比較困難，即使能實現(xiàn)，其速度往往比較慢，而對于電子標簽而言，其操作或交易都是在非常短的時間內完成的，如門禁系統(tǒng)、車輛管控系統(tǒng)等。因此RSA算法有時不符合某些電子標簽及其應用的要求，除非電子標簽有對大數(shù)乘方取模操作的硬件支持，但這又帶來了電子標簽的成本較高，用戶難以接受的問題。   

　　（4）對于RFID系統(tǒng)而言，無源電子標簽本身沒有電源，只能從射頻信號中提取能量，因此其功率必然受到一定的限制，難以完成像RSA這樣復雜的算法；而對于有源的電子標簽，依靠自身電池提供能量，可以完成此算法，但會嚴重影響其使用壽命。 

　　3、新型的零知識鑒別協(xié)議 

　　在實際生活中，A要向B證明他知道某秘密的常用方法是把他知道的秘密告訴B，但這樣一來B就知道了這個秘密。如何在不告訴B這個秘密的情況下使B相信A知道這個秘密，就是零知識證明要解決的問題。有了零知識證明，A就可以不公布秘密，卻能使任何人相信他知道這個秘密。零知識證明可以使研究人員向世人證明他知道一個特殊定理的證明方法但又不泄漏證明，這種方法在商業(yè)上也有許多用途。零知識證明的研究受到各國研究人員的重視，在國際上一直很活躍，基本的零知識證明算法基于同構圖和漢密爾頓回路"。 

　　所謂的零知識鑒別協(xié)議是指一個證明者P是一個具有無限計算能力的圖靈機，向一個僅具有多項式計算能力的圖靈機（驗證者）V證明他宣稱的一個結論是正確的，在此過程中，驗證者V除了相信P的宣稱以外，得不到其他額外的信息，允許P，V違背協(xié)議。 

　　嚴格地講，假設P，V是兩個概率圖靈機，P有無限的計算能力，V的計算能力是多項式的，若一個證明協(xié)議滿足以下3點，就稱此協(xié)議為一個零知識證明協(xié)議： 
　　完備性 如果P的聲稱是真的，則V以絕對優(yōu)勢的概率接受P的結論； 

　　有效性 如果P的聲稱是假的，則V以絕對優(yōu)勢的概率拒絕P的結論； 

　　零知識性 無論V采取任何手段，當P的聲稱是真的，并且不違背協(xié)議時，V除了接受P的結論以外，得不到其他額外的信息。 

　　這一概念產生之后，關于他的理論和實際應用方面的研究立刻全面展開。零知識證明系統(tǒng)已逐漸形成一個體系，他象單向函數(shù)、單向陷門函數(shù)以及偽隨機數(shù)發(fā)生器一樣，成為構造安全密碼系統(tǒng)的基本方法之一。零知識交互式證明系統(tǒng)在身份驗證、數(shù)字簽名和抗選擇密文攻擊等方面獲得了廣泛的應用，使用零知識交互式證明的身份驗證模式比使用RSA的執(zhí)行速度要快得多。 

　　Feige-Fiat-Shamir算法是第一個基于零知識證明的算法，他出現(xiàn)于上個世紀80年代。2000年，Nyang和Song提出了一個應用于智能卡的基于零知識證明和身份認證協(xié)議，從此關于零知識證明的應用研究廣泛展開。 

　　目前有一種有效的零知識鑒別協(xié)議可應用于RFID系統(tǒng)，該協(xié)議是以離散對數(shù)為基礎的，離散對數(shù)是現(xiàn)代密碼學常用的重要的單向函數(shù)，其特點之一是只需較小的通信量和計算量。 

　　假設P是一個素數(shù)，Zp是整數(shù)環(huán)模p，定義Kp是p-1最大的除數(shù)，他的素因子至少為v=[log2p]. 

　　我們將考慮語言集L，他的元素是串a=（I；β，p），而β是串Znp=Zp／{O}，βkp 1（mod p），I∈Znp是I.βs 1（mod p），對于所有的s∈Zp-1，有L={（I；β，p）│p是一個素數(shù)，β，I∈Z*p；βkp 1（mod p）；I.βs 1（mod p）}. 

　　我們稱I為公開數(shù)，s為秘密數(shù)。假設H為Z*p（。）的子集，有kp，那么公開數(shù)是H的元素，注意到任何β∈H，β≠1，有至少為v=[10g2p]的階。 

　　我們約定│p│表示p的二進制長度，a∈RA表示元素a是用一致性分配從集合A中隨機選取的。 

　　協(xié)議（P，V）：輸入x=（I；β，p），V校驗p是一個素數(shù)，然后計算kp，校驗I∈H，βkp 1（mod p）。如果任何一個條件失敗了，那么V停止和退出。 

　　步驟一 P發(fā)送給V：z=βr（mod p），而r∈RZp-1；   

　　步驟二 V發(fā)送給P：q，而q∈RZ│p│； 

　　步驟三 P認證q∈Z│p│；如果校驗成功，發(fā)送給V：y （r+qs）（mod（p一1）），而s是βs.I （mod p）； 

　　步驟四 V認證y∈Zp-1，Z βy.Iq（mod p）。如果這一校驗失敗，那么協(xié)議停止。 

　　步驟五 上面的步驟獨立的重復t次，V接受，其中t=t（│p│）幾乎恒定。 

　　該協(xié)議是語言集L中的成員證明。當x∈L時，那么認證方將（幾乎）總是接受，而當x不是L的成員時，那么認證方將（幾乎）總是拒絕。 

　　4、算法的完備性、有效性和零知識性

      完備性 當x∈L時，βr.Iq βr.βφ。Iq Z（βs，I）q Z.（Mod p），對于步驟4中的校驗，V總是接受； 

　　有效性 當x L時，若I H或βk，≠1（mod p），V總是拒絕；若I∈H，βkp 1（mod p），甚至是功能無限強的，不誠實證明方都不能回答步驟3的幾個序列q，所以當沒有s使得βs 1（mod p）時，連續(xù)t次后，V接受的概率可以忽略不計。 

　　零知識性 從直觀上講，證明方不向認證方顯示任何新知識，因為認證方可以自己模擬協(xié)議通信。認證方可以猜測他自己的問題q，自己得到證明方將發(fā)給他的Z和y.就是說，他可以用實際協(xié)議中同樣的分配，產生滿足步驟4中條件的串（Z，q，y）。這一模擬的關鍵是，給定的q和y，都容易獲得適當?shù)腪.當然，模擬的證明將不向認證方保證x∈L. 

　　因此，該協(xié)議符合零知識鑒別的條件。 

　　5、性能分析 

　　V是限于│n│的多項式，因此│v│=O（log│n│）。對于通信和計算復雜度，我們只考慮群元素G，H為模數(shù)，群操作可以按模操作的方式表達的情況。我們假設H=*m，輸入的長度是θ（│m│），協(xié)議的性能將按│m│的方式測量。在協(xié)議的每一循環(huán)中，步驟1和步驟3通信│m│比特，步驟2通信│v│比特。對于t的重復，我們有t（2│m│+│v│）比特。由于當t△logs│m│時，│v│=O（log │m│），通信的比特數(shù)是│m│logε│m│。 

　　6、結語 

　　RFID技術中應用身份鑒別機制是一種必然趨勢，本文提出將基于零知識證明的鑒別協(xié)議應用在RFID技術上，此協(xié)議具有較低的運算復雜度、較小的通信量和較高的安全性，并且密鑰不易被竊聽，隨著研究的不斷深入和人們對于信息安全和個人隱私的重視，一定會有廣闊的應用前景。