應答器、讀取器及其操作方法

2023-06-14 21:26:11

專利名稱：應答器、讀取器及其操作方法
技術領域：
本發明涉及操作應答器的方法、應答器、操作讀取器的方法和讀取器，其中具體地，應答器和讀取器適於無線發射或傳送信息。具體地，本發明涉及用於操作應答器的方法、應答器、用於操作讀取器的方法和讀取器，其中橢圓曲線密碼學具體地用於驗證和/或密鑰協議。
背景技術：
橢圓曲線密碼學是接近基於也稱為伽羅瓦域(Galois field)的有限域上的橢圓曲線的代數結構的公開密鑰密碼學的方法。根據基於橢圓曲線的協議，假設獲得隨機橢圓曲線元素相對於公知基點(橢圓曲線上的點)的離散對數是難實施的。從而，橢圓曲線的尺寸可以決定問題的難度。橢圓曲線是平面曲線，其由滿足橢圓曲線方程的點(X，y)以及 無窮遠處的不同點構成。曲線上的點和無窮遠處的點的這種集合與群運算(橢圓曲線加法運算)一同形成具有作為識別元素的無窮遠處點的阿貝爾群。在這裡，橢圓曲線在有限域上限定，以便限定橢圓曲線的元素X的數量是有限的。對於橢圓曲線的由兩個分量X和y給出的點，其中X和y滿足橢圓曲線方程，限定了橢圓曲線加法運算。橢圓曲線加法運算的乘法應用可以限定橢圓曲線乘法運算，其中一點的乘法是該點的整數乘法。1985 年版 Crypto 中公開的 Victor Miller 的文章「Using of Elliptic Curvesin Cryptography」討論了橢圓曲線在密碼學中的使用，其中提出了密鑰交換協議，其看起來免受Western、Miller和Adleman類型的攻擊。2008年2月出版的「International Journal of Computer Science and NetworkSecurity (Vol. 8, No. 2)中公開的 Braun, Hess, Meyer 的文章「Using Elliptic Curves onRFIDs」公開了在輕量級加密裝置中實現不對稱加密技術的概念，並描述了基於橢圓曲線密碼技術的實施方案，其可以用於大量RFID標籤應用的驗證。

發明內容
本發明的目的是提供使得特別是用於驗證目的的密碼協議較少受到未被授權的攻擊的影響的裝置和方法。具體地，本發明的目的是改善驗證過程或數據交換過程期間的安全性的裝置和方法。具體地，本發明的目的是提供用於安全驗證的裝置和方法，同時確定所涉及的裝置，特別是所涉及的應答器，且特別是RFID標籤的計算能力的界限。由獨立權利要求的主題解決該問題。示例性實施例在從屬權利要求中限定。根據本發明的實施例，提供了一種用於操作應答器的方法，該方法包括應答器接收，特別是無線地接收，表示X和Sqrt[b]/X的發射的讀取器數據，其中X為二進位伽羅瓦域中的元素且b為常數；應答器處理讀取器數據，以確定X是否為由橢圓曲線方程y2+xy =x3+ax2+b定義的橢圓曲線上的點的第一坐標，其中在伽羅瓦域上定義該橢圓曲線，使得X和y為伽羅瓦域中的元素，其中y為橢圓曲線上的該點的第二坐標。
具體地，在伽羅瓦域中定義的加法運算和乘法運算將應用在橢圓曲線方程中。實施例採用橢圓曲線密碼學用於驗證和密鑰協議。與橢圓曲線相關聯的基礎數據元素是「點」即，一對值(X，y)，使得這些值滿足上述給定曲線方程(基本上，定義哪個點落在橢圓曲線上的X和I之間的數學關係)。某些協議的數學運算允許僅採用曲線上的點的X坐標進行橢圓曲線計算(即，忽略涉及I坐標的計算)，這會產生要求較少計算的協議。這種特性具體地與Diffie-Hellman密鑰交換相關聯。對於給定橢圓曲線，基礎有限域中的每個值為該曲線上的點的X坐標，或者為「姐妹」曲線(B卩，所謂的空間曲線(twisted curve))上的點的x坐標。如果在空間曲線上而不是在預期曲線上進行橢圓曲線計算，則可能的是在計算中使用的私有密鑰可以容易地根據該計算的輸入和輸出計算。由於這種可能性，計算裝置，如應答器，在計算之前檢查輸入落在預期曲線上而不落在空間曲線上。雖然這在X和y坐標二者都可用時是容易實現的(通過簡單地檢查所述坐標滿足曲線方程)，但當由使用的協議僅提供X坐標時，這可能是非常複雜的過程。因此，對於約束裝置，根據本發明的實施例，提供了檢查X坐標落在預期曲線上而 不落在其空間曲線上的簡單方法；具體地，這種操作在不存在與I坐標相關的信息時操作。從而該方法針對在二進位域上構建的曲線，由於二進位域中的簡單的算法形式(與素域(prime field)相比)，這些曲線特別適合約束裝置。其中，計算給定X坐標是否落在在二進位域上構建的曲線上的常規過程要求計算所謂的「逆域(field inverse) 」;域元素X的逆是X』，使得xXx』 = I。計算這種逆將要求約束裝置執行複雜的算法，對其軟體和/或硬體複雜性帶來不利影響。本發明的實施例提供了驗證X坐標落在具體曲線，而且落在希望用於橢圓曲線運算的點的精確集合內的簡化方法。應答器(發射器-響應器的簡稱)可以具有在合適的電詢問時接收和發射(特別是，通過無線電磁信號，如射頻(RF)信號)信號的能力。替代地，應答器可以採用光纖通信接收或發射信號。應答器可以為具有其自己的電源的有源應答器，或者應答器可以為不具有自己的電源的無源或被動應答器。然而，甚至被動應答器也可以通過影響由讀出裝置產生的電磁磁場以修改電磁磁場而發射信號。電磁磁場的修改能夠由讀出裝置檢測到，以獲取應答器希望發射的信息或信號。具體地，應答器可以為射頻驗證標籤(RFID標籤)，其採用利用無線電波(射頻帶中的電磁波)在讀取器和RFID標籤之間交換數據的通信技術。具體地，RFID標籤可以附加至用於驗證和跟蹤對象的目的的對象上。具體地，RFID標籤可以攜帶唯一地識別RFID標籤且因此識別附加的對象的唯一驗證號。可以採用讀出裝置從數米遠讀取RFID標籤。具體地，RFID標籤可以包括集成電路和天線，集成電路用於存儲和處理信息，調製和解調射頻信號，天線用於接收和發射信號。讀取器數據可以已經由具有比應答器高的計算能力和處理能力的讀取器或讀出裝置發射。特別是，讀取器數據可以已經採用RF信號發射，並且可以已經由應答器採用天線並且之後採用解調技術解調接收到的讀取器數據而接收。讀取器數據以任何可能的編碼方案以任何階表示X和sqrt[b]/x,該編碼方案適合從中導出x以及sqrt[b]/x,其中sqrt[b]表示常數b的平方根。具體地,讀取器數據可以代表(x, sqrt [b]/x)。x例如可以被導出為橢圓曲線上的點G的第一分量(或X分量)乘以隨機數r，即，X= (rG)Xo
X例如可以被編碼為具有大量分量，如163個分量的二進位向量。從而，X為二進位伽羅瓦域(或二進位有限域)中的元素，其中二進位伽羅瓦域是包含有限數量的元素，在該情況中為2163個元素的有限域。通常，二進位伽羅瓦域具有可以被寫為2n的大量元素，其中2也被稱為該域的特徵數，且η為正整數，例如為163。B為被限定在伽羅瓦域內的常數值。應答器可以處理(具體地，採用處理電路，如集成電路)讀取器數據(具體地，在解調或解碼讀取器數據以重新獲取X和sqrt [b] /x之後)，並且可以運行一個或多個測試以確定X是否為由上述橢圓曲線方程定義的橢圓曲線上的點的第一坐標。進一步，應答器可以進行一個或多個一致性測試。由如上文給出的橢圓方程定義的橢圓曲線上的點可以被表示為向量(X，y)，其中X和y都是伽羅瓦域中的元素。接收表示(X，sqrt[b]/x)的讀取器數據使得應答器能夠在不需要大量的計算努力和計算時間的情況下確定X是否為橢圓曲線上的點的向量。唯一地，當確定X為橢圓曲 線上的點的第一坐標時，應答器可以發射也稱為應答器數據的響應數據，其已經從讀取器數據以及應答器的私有密鑰和應答器的公開密鑰中導出。從而，可以避免應答器在X不是橢圓曲線上的點的第一坐標而是所謂的空間曲線上的點的第一坐標的情況也發射這種數據。如果X為空間曲線上的第一坐標，則潛在的攻擊者可能接收和處理應答器數據，從而以比在其中X事實上為橢圓曲線上的點的第一坐標的情況簡單得多的方式獲取應答器的私有密鑰。從而，可以避免未被授權的攻擊者可能訪問或知道應答器的私有密鑰。從而，應答器的驗證且通常讀出裝置和應答器之間的通信可以被改善，特別是關於數據安全性和驗證或驗證安全性方面。具體地，提供了檢查特徵數為2的伽羅瓦域內的值(即，所謂的「二進位域中的元素)為指定橢圓曲線上的點的X坐標的改善方法。這種過程稱為「點確認」。可以需要這種功能以通過應用輸入至為非法點的裝置和系統而確保某些密碼協議不易受到攻擊。具體地，提供至應答器的X坐標由附加的檢查值實現，這允許比現有技術更簡單的確認算法。這在下述情況中是特別有價值的，即必須在具有高度受限計算能力的裝置內，如在應答器內進行確認，具體地，其中採用更有能力的計算裝置進行該協議。具體地，採用本發明的實施例可以簡化諸如應答器之類的約束裝置的實施方案。根據本發明的實施例，由應答器進行的所述處理包括採用Trace運算(Traceoperation),其中該Trace運算將伽羅瓦域中的每個元素映射至值O或I,其中Trace運算為線性運算。由於伽羅瓦域中的每個元素可以被表示為基礎元素域中的總和，因此元素的跡(Trace)隨後又可以被計算為每個單獨的基礎元素的預先計算的跡的和。當其跡將被計算的伽羅瓦域元素被表示為前述二進位向量時，則其跡可以通過將其二進位表示與包含每個基礎元素的預先計算的跡的對應二進位向量進行邏輯與，並且隨後計算將這兩個向量域相與的結果的模-2求和(或奇偶)而被計算。進行Trace運算確實需要應答器的大量的計算能力，並且因此可以由(輕量級)應答器在合理的時間中進行。從而，可以簡化X是否是由上述橢圓曲線方程定義的橢圓曲線上的點的第一坐標的確定。從而，由讀出裝置執行以檢查應答器的驗證的驗證檢查可以以更加安全的方式進行。具體地，對潛在的攻擊者來說可能更加難以知道應答器的私有密鑰。
根據本發明的實施例，由應答器進行的所述處理進一步確定X是否為橢圓曲線上的點的循環子集(cyclic subset)中的點的第一坐標,其中循環子集中的該點可以由橢圓曲線上的兩點的橢圓曲線加法運算的結果表示。橢圓曲線上的點的循環子群是橢圓曲線的奇數子群。當應答器對讀取器數據作出響應時，確保或檢查X是否是橢圓曲線點的奇數子群的第一坐標甚至可以進一步改善應答器的私有密鑰的安全性，因為當應答器對讀取器數據作出響應時，捕獲由應答器進行的響應的潛在攻擊者不能夠(或者可能具有更多的困難)導出應答器的私有密鑰，其中X為橢圓曲線點的奇數子群中包含的點的第一坐標。根據本發明的實施例,所述處理涉及檢查Trace [X] == Trace [a]是否成立以及檢查Trace [sqrt [b]/x] = =0是否成立。進行上述測試將使得能夠確定x是否是橢圓曲線點的奇數子群中點的第一坐標。從而，可以改善操作安全性。根據本發明的實施例，該方法還包括在接收讀取器數據之前將sqrt[b]存儲為應答器中的第一預存儲值(具體地，存儲在應答器中)。當第一預存儲值(即，sqrt [b])存儲在應答器中時，可以減少由應答器使用的處理努力和/或處理時間，從而加速該方法。進一 步，應答器可以配備比根據現有技術所要求的少的計算設備或能力。根據本發明的實施例，該方法還包括由應答器根據在伽羅瓦域中定義的乘法運算(其將伽羅瓦域中的兩個元素映射至伽羅瓦域中的另一個元素)進行伽羅瓦元素X和sqrt [b]/x的乘法運算，以及將進行乘法運算的結果與第一預存儲值(即，sqrt [b]的表示)進行比較。通過進行這種乘法運算和進行比較，可以由應答器檢查或確定接收到的讀取器數據中包含的b是否匹配對應答器來說已知的橢圓曲線的對應的橢圓曲線參數。具體地，最初，讀取器和應答器可能都已經知道橢圓曲線方程，因此都可能已經知道a和b。從而，應答器可以檢查接收到的讀取器數據是否與在應答器的存儲裝置中預先表示的橢圓曲線方程一致。從而，可以進一步改善該方法，特別是關於安全問題方面。根據本發明的實施例，該方法還包括在接收讀取器數據之前將Trace[a](的表示)存儲為應答器中的第二預存儲值。在接收讀取器數據之前將Trace [a]存儲在應答器中可以減少在將Trace [a]與Trace[x]進行比較時應答器花費的處理時間或處理努力。具體地，應答器的處理時間可以減少，或者應答器可以配備較少的計算能力。根據本發明的實施例，伽羅瓦域中的每個元素由具有η個分量的位向量表示，其中η在100和550之間，具體地在100和200之間，進一步具體地為163。因此，伽羅瓦域中的每個元素，如橢圓曲線方程中出現的X和y，可以被表示為具有在100和200之間的分量，具體地具有163個分量的向量,其中每個分量為O或I。從而，例如可以通過基於分量的異或(XOR)運算進行伽羅瓦域中的加法運算。從而，可以簡化計算，並且可以加速該方法。根據本發明的實施例，通過將X的二進位表示與包含每個基礎元素的預先計算的跡的對應二進位向量進行邏輯與，並且隨後計算將這兩個向量域相與的結果的模-2求和(或奇偶校驗(parity)),對x進行Trace運算。從而，可以簡化或加速該方法。根據本發明的實施例，由應答器進行的所述處理是在進行兩次Trace運算和一次乘法運算之後完成的。具體地，乘法運算可以涉及進行伽羅瓦元素X和sqrt[b]/x的相乘，所述兩次Trace運算可以涉及形成Trace [X]和形成Trace (sqrt [b]/x)。從而,對應答器的處理能力不存在高的要求。從而，可以以緊湊且划算的方式製造應答器。根據本發明的實施例，讀取器數據是以基於複合模量表示的糾錯保護格式提供的。在這種表示中，X和sqrt[b]/x的值由比表示伽羅瓦域中的元素最少所需要的位的數量(在示例實施例的情況中，這為163)更多的數量的位擴展和表示。表示每個擴展量的位被選擇為使得擴展X和sqrt[b]/x中的冗餘信息將在擴展值的積中產生已知的冗餘信息。如果該積的計算由攻擊者操縱，則極有可能的是，計算出的積包含不正確的冗餘，且所述操縱將被檢測到。從而，可以進一步改善該方法的安全性。根據本發明的實施例，用於操作應答器的方法還包括在確定X為由橢圓曲線方程定義的橢圓曲線上的點的第一坐標時，應答器發射，特別是無線地發射應答器數據，其中應答器數據基於(具體地取決於)x和應答器中存儲的私有密鑰，其中應答器數據具體地進一步基於應答器中存儲的公開密鑰。從而，應答器可以對接收到的讀取器數據作出響應，具體地用於繼續進行驗證過程。應答器數據，即，接收到的讀取器數據的響應，可以由讀出裝置接收，以驗證應答器。具體地，讀出裝置可以進行一次或多次檢查或比較和/或在檢查和 /或比較之前進行計算，以推導是否已經由應答器基於X和私有密鑰獲得應答器數據，私有密鑰相對於應答器的公開密鑰具有預期的關係。從而，可以在不給攻擊者從應答器數據中導出應答器的私有密鑰的機會的情況下進行應答器的驗證。從而，可以改善驗證應答器的驗證方法。應當理解，所公開的、描述的、說明的或應用於用於操作應答器的方法的特徵(單獨地或以任何組合)也可以(單獨地或以任何組合)應用於，用於或提供用於根據本發明的實施例的應答器、用於操作讀取器的方法和讀取器，反之亦然。根據一種實施例，提供了一種應答器，包括接收模塊，適於接收，特別是無線地接收，表示X和sqrt [b] Λ的發射的讀取器數據，其中X為二進位伽羅瓦域中的元素且b為標量(sqrt[b]/x表示b的平方根除以X，其中針對伽羅瓦域中的元素定義該除法)；處理模土夾，適於處理讀取器數據，以確定X是否為由橢圓曲線方程y2+xy = x3+ax2+b定義的橢圓曲線上的點的第一坐標，其中在伽羅瓦域上定義該橢圓曲線，使得X和y為伽羅瓦域中的元素，其中y為橢圓曲線上的該點的第二坐標，其中具體地，在伽羅瓦域中定義的加法運算和乘法運算將應用在橢圓曲線方程中。具體地，接收模塊適於接收RF信號，即，射頻帶中的電磁信號。進一步，接收模塊可以包括用於解碼或解調接收信號以獲取X和sqrt[b]/X的電路。具體地，處理模塊可以被編程，以及可以訪問數據存儲裝置、數據表或散列表。具體地，根據本發明的實施例的應答器可以按照與常規應答器相比更小或更輕的方式製造，同時提供相同程度的安全特徵，特別是關於應答器的私有密鑰的安全性方面。根據本發明的實施例，提供了一種用於操作讀取器的方法，該方法包括讀取器發射，特別是無線地發射表示X和sqrt [b] Λ的讀取器數據，其中X為二進位伽羅瓦域中的元素且b為常數，其中該方法具體地還包括讀取器接收，特別是無線地接收應答器數據，其中應答器數據基於X和應答器中存儲的私有密鑰。具體地，讀取器可以為具有比應答器高很多的計算能力的裝置。具體地，讀取器可以發射讀取器數據，用於啟動用於驗證的驗證過程。在接收到應答器數據時(僅在X為由橢圓曲線方程定義的橢圓曲線上的點的分量的情況中)，讀取器可以進行處理步驟和比較或檢查步驟，以確定應答器是否發射與應答器的公開密鑰的公共證書一致的應答器數據。從而，使得讀取器能夠驗證應答器，特別是RFID標籤。根據本發明的實施例，提供了一種讀取器，包括發射模塊，適於發射，特別是無線地發射表示X和sqrt [b] Λ的讀取器數據，其中X為二進位伽羅瓦域中的元素且b為常數，其中讀取器具體地還包括適於接收，特別是無線地接收應答器數據的接收模塊，其中應答器數據基於X和應答器中存儲的私有密鑰。本發明的上述方面和其它方面根據以下將描述的實施例的示例而明白，並參照實施例的這些示例進行說明。


以下將參照實施例的示例更詳細地描述本發明，但本發明不限於所述實施例。 圖I示意性地說明根據本發明的實施例的包括讀取器和應答器的系統，該系統根據用於操作應答器的方法的實施例和用於操作讀取器的方法的實施例執行驗證過程；圖2示意性地說明根據本發明的實施例的包括讀取器和應答器的另一系統，其根據本發明根據用於操作應答器的方法的實施例和用於操作讀取器的方法的實施例執行驗證過程。
具體實施例方式附圖中的圖示是示意性的。在不同的附圖中，為相似或相同的元件提供相似或相同的附圖標記。圖I圖示讀取器100和應答器103的通信對話，用於驗證應答器103。讀取器100無線發射信息或讀取器數據105(在該情況中為rG，其中G為橢圓曲線上的點，r為隨機數)，所述信息或讀取器數據105由應答器103接收。應答器103進行一些處理並將信息或讀取器數據107 (在該情況中為q(rG)和cert (Q)，其中q為應答器的私有密鑰，Q = qG為應答器的公開密鑰)無線地返回至讀取器100。在接收到讀取器數據107之後，讀取器進行一些計算和檢查程序，以驗證應答器103。具體地，RFID標籤103採用如圖I所示的橢圓曲線Diffie_Hellman驗證協議。在該協議中，讀取器「Rdr」 100產生隨機數r並進行橢圓曲線點乘法，以計算點rG (其中G為選擇用於預期橢圓曲線的基點)。它隨後將該結果，即橢圓曲線點，發送至標籤103。標籤103處理私有/公開密鑰對，其中標量q為私有密鑰，點Q = qG為在目標橢圓曲線上計算的公開密鑰。此外，標籤承載證書cert (Q)，其為通過公開密鑰(以及與該標籤相關聯的其它可能的數據)計算的籤名，其中採用信任授權的私有密鑰產生該籤名；可以採用信任授權的對應公開密鑰驗證該籤名。這允許任何人驗證公開密鑰是否是由信任授權確保的真實標籤；具體地，作為驗證協議的一部分，將由讀取器驗證該證書。在應答器103處接收到點(rG)(其可以被認為是至標籤103的質詢輸入)之後，標籤將接收到的點乘以其私有密鑰q，隨後將結果q(rG)回傳至讀取器100。由於該計算應當等於r (qG),因此讀取器能夠通過檢查它接收到的點q(rG)匹配r (qG) = rQ的計算而驗證該標籤使用(且因此知曉)正確的私有密鑰值q。在大多數的抽象層級，該協議可以被認為在由(X，y)坐標對定義的目標橢圓曲線上的完整點上運行。然而，根據本發明的實施例，這種協議也可以僅採用所關注的點的X坐標運行，但還發送檢查值，如下文參照圖2說明的那樣。然而，採用(x，y)坐標或僅採用X坐標執行該協議，對標籤來說非常重要的是驗證提供給它的點確實落在目標橢圓曲線上。這種「有效性檢查」的原因如下。在有限域上定義的每條橢圓曲線具有「姐妹」曲線，即所謂的「空間曲線」；空間曲線上的點位於有限域中的未落在原始曲線上的X坐標值處。由於在曲線或其「空間曲線」上的每個X坐標處存在兩個點，因此曲線E上的點的數量和它的空間曲線E』上的點的數量之間的關係非常簡單，即，#E+#E> = 2+2X#GF換句話說，該曲線及其空間曲線上的點的總數量是基礎域的大小的兩倍加2(其是每條曲線的所謂的「無窮遠處的點」)。因此，當已知曲線上的點的數量時，很平常地計算其空間曲線上的點的數量。 通常，希望直到標籤的私有密鑰q的攻擊者的問題是解決所謂的橢圓曲線離散對數問題(EC-DLP);給定輸入點(rG)和輸出點q(rG)，他希望計算值q。通常，當在曲線E上進行q(rG)的計算時，這個問題具有由#E的最大因子的平方根確定的複雜性。通常，目標曲線E被選擇為使得#E是原始的或具有非常大的素因子(primefactor);然而，這種選擇會導致其中#E』「平滑」，即，包含多個小的素因子的情況，使得其最大素因子的平方根不是非常高。在這種情況中，如果攻擊者用E』上的點代替在E上計算的初始預期點(rG)，則標籤將採用曲線E』計算q(rG)並且由攻擊者重獲q將非常簡單。因此，讀取器100還發送另一個檢查值，以使得應答器103能夠確定接收到的點rG是否是橢圓曲線上的點，如下文將說明的那樣。為了防止這種攻擊，標籤必須驗證以該協議提供它的點實際上落在預期曲線E上。而且，當在二進位域上構建曲線時，總是存在的情況是曲線#E上的點的數量為偶數，其通常被選擇為大素數η的兩倍(所謂的「餘因子(co-factor) = 2曲線」)；在這些情況中，橢圓曲線協議通常在形成η階子群的點上進行，因此2和2η階的點也應當被有效檢查排除在外。η階子群包含在乘以標量η時產生無窮遠處的點的所有點。如上所述，當在二進位域上定義曲線時，通常的實踐是選擇曲線參數，使得η為素數，因此點的循環子群位於該曲線上。為了進行這種有效檢查，本發明的實施例採用已知為TraceO的數學函數的特性。TraceO將伽羅瓦域中的每個元素映射到值O或I。公知的是，如果Trace ( α ) =0，則y2+y= α形式的二次方程在二進位伽羅瓦域上是可解的；因此，對於正態曲線方程y2+xy = x3+ax2+b,在對於X關0，(y/x)2+ (y/x) = x+a+ (b/x2)時，以及相應地在Trace (x+a+(b/x2)) = O時,可以表明存在解(x, y)。由於Trace 是相加性函數(S卩，Trace (v+w) = Trace (v) +Trace (w))並且保持平方，即 Trace (v2) = Trace2(v),則當Trace (x) +Trace (a) +Trace ( V b/x) = 0 時,該方程具有解。
由於「a」為曲線方程常數，因此可以預先計算它的TraceO。而且，由於已知人們可以通過檢查Trace (X) = Trace (a)是否成立確定x坐標是否是落入GF(2n)範圍內的橢圓曲線的奇數子群中的點的X坐標，兩次TraceO計算使得我們完整地驗證輸入點，即我們檢查Trace (x) = = Trace (a)並且檢查Trace ( V b/x) ==0計算TraceO是相對簡單的操作。其Trace O將被計算的位向量可以被認為是其係數為I的多項式t的各個冪的總和。隨後，採用TraceO的相加性，我們通過將GF(2n)中的任意元素與Trace(P)的預計算值相與且隨後計算該結果中的所有位的以2為模的和(即，奇偶校驗)而計算GF(2n)中的任意元素的TraceO。這種計算可以容易由邏輯電路或者計算機或微處理器的軟體中定義的操作執行。 圖2示意性地說明包括讀取器200和應答器203的系統，其中進行涉及根據本發明的實施例的應答器的操作和讀取器的操作的驗證過程。讀取器200包括發射模塊206，其用於編碼、調製和無線發射信息或讀取器數據205至應答器203。進一步，讀取器200包括用於處理數據的處理模塊209，其中處理模塊209訪問數據存儲裝置211。在數據存儲裝置211中，可以存儲用於定義橢圓曲線的上述橢圓曲線方程的參數。具體地，在存儲裝置211中，可以存儲標量a和b以及橢圓曲線上的預定點G。進一步，處理模塊209可以適於產生為標量的隨機數r。讀取器200的處理模塊209被通信地連接至接收模塊213，接收模塊213適於特別是經由天線接收由讀取器203發送的應答器數據207，並用於解碼和/或解調應答器數據207。從應答器數據207中得到的信息從接收模塊213提供至處理模塊209。應答器203(在圖示的實施例中由RFID標籤表示)包括接收模塊215，其用於特別是經由天線接收由讀取器200發射的讀取器數據205。接收模塊215解調和/或解碼讀取器數據205，並將得到的信息，如(X和sqrt (b) /x)，提供至處理模塊217，處理模塊217適於進行Trace運算和橢圓曲線乘法或橢圓曲線加法運算。處理模塊217訪問存儲裝置219。具體地，在存儲裝置219中可以存儲橢圓曲線方程的參數，特別是參數a和b，並存儲橢圓曲線上的預定點G。進一步，存儲裝置219可以包括應答器203的私有密鑰q以及應答器203的公開密鑰Q。具體地，應答器203的公開密鑰Q可以被導出或預計算為qG，其中G為橢圓曲線上對讀取器200和應答器203來說已知的預定點。進一步，應答器可以使用確保公開密鑰Q的可靠性的證書("cert")，其中該證書可以已經由授權的認證授權發布。基於接收到的讀取器數據205，應答器可以從讀取器數據205導出(x，sqr[b]/x)，應答器203的處理模塊217導出響應數據或應答器數據207，其由應答器中包括的發射模塊221編碼和/或調製，隨後被作為應答器數據207發送至讀取器200。應答器數據207的內容在不同的實施例中可以不同，但應答器數據基於讀取器數據205中從讀取器200接收的值X，並且應答器數據207同樣基於應答器203的私有密鑰q。進一步，應答器數據207可以基於應答器203的公開密鑰Q。具體地，應答器數據207可以類似於圖I中圖示的應答器數據107。在接收到可以從中導出(x，Sqr[b]/x)的讀取器數據205之後，應答器203的處理模塊217計算Trace [X]並將結果與被預計算並被存儲在存儲裝置219中的Trace [a]進行比較。進一步，應答器203的處理模塊217計算Trace (sqrt [b]/x)並檢查結果是否為零。進一步，處理模塊217通過使X和sqrt[b]/x相乘以獲得如從讀取器200接收到的sqr[b]而進行伽羅瓦域乘法運算。進一步，將sqr[b]的該值與存儲裝置219中存儲的sqr[b]的預先存儲值進行比較。如果sqr[b]的值匹配存儲裝置219中存儲的(sqr[b])的值，並且如果Trace [X]的計算值匹配Trace [a]的預先計算和存儲值且如果Trace (sqr[b]/x)的計算值等於零，則應答器203確認讀取器200和應答器203都涉及相同的橢圓曲線方程(因為參數相同)，並且確認值X是橢圓曲線上的點的第一坐標，並且進一步確認橢圓曲線上的點是該橢圓曲線上的點的奇數子群中的元素。因此，採用應答器數據207安全地響應讀取器，不具有應答器數據207被潛在的攻擊者分析的風險，從而獲得應答器203的私有密鑰q。根據本發明的實施例，提供了特定協議架構，其被設計為最小化標籤上所要求的計算，以實現這種基於檢查的Trace O。在該協議中，讀取器200將一對值發送至標籤203 ；然而，代替點的常規(x，y)坐標或單個X坐標，則它發送數據值對(X，V b/x)。這將用於計算模逆的職責轉移至讀取器，在讀取器中通常更多的計算能力是可用的。值V b是可以預先計算的常數，從曲線參數b導出；事實上，它是在任何情況中存 儲在標籤203內的自然值，因為為了進行通常橢圓曲線標量乘法運算，該值通常被用在每個計算步驟中；因此，將該值存儲在標籤內沒有引入任何系統開銷。應當注意到，這種原則對應在二進位域上定義的任何餘因子-2橢圓曲線同樣適用，因為總是可以計算V b (二進位域中的每個值具有該形式的平方根)。當採用該協議時，隨後，標籤僅需要進行單次乘法，其中它計算兩個接收到的值X和V b/x的域內的積，並且確認結果等於V b ;這檢查提供的這兩個值形成相容對。隨後直接採用兩個輸入值(再一次，Trace (a)是能夠預先計算的)可以檢查Trace (x) = = Trace (a),並且Trace ( V b/x) == 0。這是比提供(x，y)時將要求的方法簡單且更有效的檢查方法，從而標籤將必須驗證輸入坐標滿足曲線方程。作為最小值，這要求計算y (x+y) = (x+a) x2+b其可以被視為需要對標籤進行2次乘法和平方運算，隨後進行附加Trace O計算，以檢查Trace (X) = = Trace (a)檢查實現完整確認或奇數階。相反，本發明的協議僅需要單次乘法和兩次TraceO計算；發明人相信對於這種類型的橢圓曲線不存在任何更簡單、安全的點驗證方法。注意到，值(X，V b/x)可以以基於複合模量表示的糾錯保護格式提供至標籤；這隨後可以用來保護標籤內使用的乘法，以檢查數據對抵抗故障攻擊的一致性。本發明可以用作用於RFID標籤的採用基於橢圓曲線的不對稱驗證的協議的基礎。對於採用橢圓曲線的其它密碼協議(如，密鑰交換，其它驗證協議)，可以作為簡化約束裝置內的點驗證的機制應用本發明，從而在具有不同量的計算資源的裝置之間進行該協議。可以在將來的NFC應用、自動收費或電子ID裝置中發現這種應用。
權利要求
1.一種用於操作應答器(203)的方法，該方法包括 應答器接收，特別是無線地接收，表示X和sqrt [b] /x的發射的讀取器數據(205)，其中X為二進位伽羅瓦域中的元素且b為常數； 應答器處理讀取器數據(205)，以確定X是否為由橢圓曲線方程y2+xy = x3+ax2+b定義的橢圓曲線上的點的第一坐標， 其中在伽羅瓦域上定義該橢圓曲線，使得X和y為伽羅瓦域中的元素， 其中y為橢圓曲線上的該點的第二坐標。
2.根據權利要求I所述的方法，其中由應答器進行的所述處理包括採用Trace運算，該Trace運算將伽羅瓦域中的每個元素映射至0或1，Trace運算為線性運算。
3.根據權利要求I或2所述的方法，其中由應答器進行的所述處理進一步確定X是否為橢圓曲線上的點的循環子集中的點的第一坐標，其中循環子集中的該點可以由橢圓曲線上的兩點的橢圓曲線加法運算的結果表示。
4.根據權利要求3所述的方法,其中所述處理涉及檢查Trace[x] == Trace [a]是否成立以及檢查Trace[sqrt[b]/x] ==0是否成立。
5.根據前述權利要求中任一項所述的方法，還包括在接收讀取器數據之前將sqrt[b]存儲為應答器中的第一預存儲值。
6.根據前述權利要求中任一項所述的方法，還包括 應答器根據在伽羅瓦域中定義的乘法運算進行伽羅瓦元素X和sqrt[b]/X的乘法運算，以及 將進行乘法運算的結果與第一預存儲值進行比較。
7.根據前述權利要求中任一項所述的方法，還包括在接收讀取器數據之前將Trace [a]存儲為應答器中的第二預存儲值。
8.根據前述權利要求中任一項所述的方法，其中伽羅瓦域中的每個元素由具有n個分量的位向量表示，其中n在100和550之間，具體地在100和200之間，進一步具體地為163。
9.根據前述權利要求中任一項所述的方法，其中通過將X的二進位表示與包含每個基礎元素的預先計算的跡的對應二進位向量進行邏輯與，並且隨後計算將這兩個向量域相與的結果的模-2求和，對X進行Trace運算。
10.根據前述權利要求中任一項所述的方法，其中所述處理是在進行兩次Trace運算和一次乘法運算之後完成的。
11.根據前述權利要求中任一項所述的方法，其中讀取器數據是以基於複合模量表示的糾錯保護格式提供的。
12.根據前述權利要求中任一項所述的方法，還包括 在確定X為由橢圓曲線方程定義的橢圓曲線上的點的第一坐標時 應答器發射，特別是無線地發射應答器數據(207)， 其中應答器數據基於X和應答器中存儲的私有密鑰， 其中應答器數據具體地進一步基於應答器中存儲的公開密鑰。
13.一種應答器(203)，包括 接收模塊(215)，適於接收，特別是無線地接收，表示X和sqrt [b] /x的發射的讀取器數據(205)，其中X為二進位伽羅瓦域中的元素且b為常數；處理模塊(217)，適於處理讀取器數據(205)，以確定X是否為由橢圓曲線方程y2+xy =x3+ax2+b定義的橢圓曲線上的點的第一坐標， 其中在伽羅瓦域上定義該橢圓曲線，使得X和y為伽羅瓦域中的元素， 其中y為橢圓曲線上的該點的第二坐標。
14.一種用於操作讀取器(200)的方法，該方法包括 讀取器發射，特別是無線地發射，表示X和sqrt [b] /x的讀取器數據(205)，其中x為二進位伽羅瓦域中的元素且b為常數， 其中該方法具體地還包括 讀取器接收，特別是無線地接收，應答器數據(207)， 其中應答器數據基於X和應答器中存儲的私有密鑰。
15.一種讀取器(200)，包括 發射模塊(206)，適於發射，特別是無線地發射，表示X和sqrt[b]/x的讀取器數據(205)，其中X為二進位伽羅瓦域中的元素且b為常數， 其中讀取器具體地還包括 適於接收、特別是無線地接收，應答器數據的接收模塊(213)，其中應答器數據基於X和應答器中存儲的私有密鑰。
全文摘要
本發明描述了一種應答器、讀取器及其操作方法，該方法包括應答器接收，特別是無線地接收，表示x和sqrt[b]/x的發射的讀取器數據(205)，其中x為二進位伽羅瓦域中的元素且b為常數；應答器處理讀取器數據(205)，以確定x是否為由橢圓曲線方程y2+xy＝x3+ax2+b定義的橢圓曲線上的點的第一坐標，其中在伽羅瓦域上定義該橢圓曲線，使得x和y為伽羅瓦域中的元素，其中y為橢圓曲線上的該點的第二坐標。進一步地，本發明還描述了應答器、用於操作讀取器的方法和讀取器。
文檔編號H04W12/02GK102781005SQ20121014059
公開日2012年11月14日 申請日期2012年5月8日 優先權日2011年5月12日
發明者布魯斯·默裡 申請人:Nxp股份有限公司