置換再交叉運算的所有權轉移協議

劉宗妹 徐金成

(廣東司法警官職業學院信息管理系 廣東 廣州 510520)

0 引 言

射頻識別系統[1-2]因其自身特有的屬性特點，在公交卡系統等各個領域中均有涉及[3]。典型的RFID系統由標簽、讀卡器、數據庫組成，其中讀卡器與數據庫之間采用較為安全的有限方式通信，一般認定為可靠，因此常將二者看作一個整體以便于研究及建模型[4-5]。

標簽在運用過程中，標簽的歸屬者會經常發生變更，一個經典的運用鏈如下：嵌有標簽的商品由生產商生產出來，未出場之前，商品的歸屬者是生產商；批發商從生產商購買商品后，商品的歸屬者由生產商變更為批發商；當零售商從批發購買商品后，商品的歸屬者由批發商變更為零售商；最終消費者會從零售商手上買得該商品，商品的歸屬者由零售商又變更為消費者[6-8]。在上述歸屬者變更過程中，存放在標簽中的隱私信息需要保證其安全性，同時也需要確保信息的前向安全性和后向安全性[9-11]。

為能夠保障標簽在其生命過程中歸屬者變化時，隱私信息的安全性，文獻[12]中基于SQUASH提出一種超輕量級所有權轉移協議，同時聲稱能夠抵抗去同步化等攻擊。文獻[13]中對文獻[12]的安全性提出了質疑，分析了協議并不具備抵抗攻擊者發起的異步攻擊能力，并提出了一個超輕量級協議,但該協議的安全性仍有待全面的系統驗證，同時該協議無法滿足重放攻擊。文獻[14]提出一種協議，但分析后發現，協議因使用隨機數的明文傳送，使得協議存在一定的缺陷，無法抵抗假冒攻擊。文獻[15]同樣利用二次剩余設計一種協議，協議主要存在的問題在于每次通信完成后，通信實體并沒有對認證用到的共享密鑰進行更新， 從而無法提供追蹤攻擊的抵抗能力。

鑒于現有的大多數所有權協議存在如下缺陷：1) 通信過程復雜；2) 通信協議中，通信實體的計算量大；3) 通信協議自身具備的安全缺陷，無法提供安全性。在分析眾多協議基礎之上，本文給出一種所有權協議。協議基于二次剩余和置換再交叉運算對信息加密，對于較為重要的隱私信息基于二次剩余進行加密，增大攻擊者的破解難度，其他信息采用置換再交叉運算進行加密，這樣使得在確保信息安全的前提下， 也可以滿足降低計算量的要求。

1 所有權協議

1.1 符號說明

對協議中出現的符號進行如下說明：

Sold：標簽原所有者；

Snew：標簽新所有者；

Ti：第i個標簽；

Sold_ID：Sold的標識符；

Snew_ID：Snew的標識符；

TID_L：Ti標識符的左半部分；

TID_R：Ti標識符的右半部分；

p1、q1：Sold隨機選擇的兩個大素數；

n1：p1和q1的乘積，即n1=p1×q1；

p2、q2：Snew隨機選擇的兩個大素數；

n2：p2和q2的乘積，即n2=p2×q2；

Kold：Sold與Ti之間共享的密鑰；

Knew：Snew與Ti之間共享的密鑰；

r1、r2、r3：Ti產生的三個隨機數；

r4：Snew產生的隨機數；

⊕：按位異或運算；

&：按位與運算；

Rep-Rec(X,Y)：置換再交叉運算；

X2modn：模運算。

1.2 置換再交叉運算

置換再交叉運算在文中用符號Rep-Rec(X,Y) (Replacement and Re-cross Operation)表示，其具體定義如下：X、Y、Z均表示長度為偶數L位的二進制序列；指針P1、P2分別指向二進制序列X、Y；HW(X)表示二進制序列X的漢明重量。

指針P1、P2分別指向二進制序列X、Y的第一位，然后開始進行遍歷操作，當指針P1所指向二進制序列X的第i位為0時，指針P2所指向二進制序列Y的第i位數值進行取反操作，即0變1、1變0；當指針P1所指向二進制序列X的第i位為1時，指針P2所指向二進制序列Y的第i位數值不變。依照上述操作可得到二進制序列Z，即完成置換操作。

HW(X)表示二進制序列X的漢明重量、HW(Y)表示二進制序列Y的漢明重量、HW(X-Y)表示HW(X)與HW(Y)的差值絕對值。根據HW(X)、HW(Y)兩者具體數值大小關系進行不同的運算。具體地，當HW(X)≥HW(Y)時，將二進制序列Z的左邊HW(X-Y)位、二進制序列Z的右邊L-HW(X-Y)位進行交換，即可得到的Rep-Rec(X,Y)值；當HW(X)

為更好地描述出置換再交叉運算的實現，結合例子進行解釋。此處取L=12，X=0001 1101 1111，Y=1101 1000 0001，則HW(X)=8，HW(Y)=5，HW(X-Y)=3，Z=0011 1010 0001，Rep-Rec(X,Y)=1101 0000 1001，如圖1所示。此處取L=12，X=1001 1101 0010，Y=1101 1111 0001，則HW(X)=6，HW(Y)=8，HW(X-Y)=2，Z=1011 1101 1100，Rep-Rec(X,Y)=0010 1111 0111，如圖2所示。

圖1 置換再交叉運算(HW(X)≥HW(Y))

圖2 置換再交叉運算(HW(X)

1.3 協議步驟

所有權轉移協議共分為兩個階段：初始化階段；所有權轉移階段。

(1) 初始化階段。所有權轉移協議開始之前，Sold隨機選擇p1、q1大素數，計算兩者的積，同時賦值給n1。將事先計算好的B的值，同時存放在Sold、Snew、Ti三者中。Sold中存放Sold_ID、Kold；Snew中存放Snew_ID；Ti中存放Sold_ID、Kold、Snew_ID。

(2) 所有權轉移階段。對圖3中字符進行解釋：

A=n1⊕Sold_ID；

B=Rep-Rec (TID_L⊕TID_R,TID_L&TID_R)；

B′=Rep-Rec (Knew⊕x,Knew&x)；

D=B⊕Sold_ID⊕r1；

D″=D4modn′1；

E=Snew_ID⊕r2；

F=Sold_ID⊕r1；

G=B⊕r′1；

H=Rep-Rec(G⊕n2⊕r′2,G&n2&r′2)；

M=n2⊕Snew_ID；

N=Kold⊕r3；

N′=N2modn2；

N″=N4modn2；

P=Rep-Rec(N⊕n2,N&n2)；

Q=Knew⊕x；

L=r4⊕x；

V=Rep-Rec(r4⊕Q,r4&Q)。

所有權轉移協議如圖3所示。

圖3 所有權轉移協議

步驟1Sold用n1、Sold_ID來計算A的值，將A及Query指令傳送給Ti。

步驟2Ti收到信息后，先計算A⊕Sold_ID得到n′1，在生成r1、r2隨機數，并用B、Sold_ID、r1計算D的值，用D、n′1計算D″的值，用Snew_ID、r2計算E的值，用Sold_ID、r1計算F的值，最后將(D″，E，F)傳送給Sold。

步驟3Sold收到信息后，先計算F⊕Sold_ID得到隨機數r′1，用n1和D″通過二次剩余定理的方法，解出D的值，這里用D′表示，即Sold會解出以n為模的D2的D的值，利用p和q獲得D2的值。

比對D′⊕r′1與B⊕Sold_ID的值。若不相等，Ti驗證不通過，協議終止；若相等，說明D′=D、r′1=r1，Sold用B、r′1來計算G的值，最后將(G，E)傳送給Snew。

步驟4Snew收到信息后，先隨機生成p2、q2大素數，并計算n2=p2q2，接著計算E⊕Snew_ID得到隨機數r′2，然后用G、n2、r′2計算H的值，用n2、Snew_ID計算M的值，最后將(H，G，M)傳送給Ti。

步驟5Ti收到信息后，先計算M⊕Snew_ID得到n′2，接著用r1、B、n′2、r2來計算H′的值，即：

H′=Rep-Rec((B⊕r1)⊕n′2⊕r2, (B⊕r1)&n′2&r2)。

比對H′與H的值。若相等，說明n2′=n2，r′2=r2，接著Ti生成r3隨機數，用Kold、r3來計算N的值，用N、n′2分別計算N′、N″的值，用N、n′2來計算P的值，最后將(N″，P)傳送給Snew；若不相等，協議終止。

步驟6Snew收到信息后，先用二次剩余定理解出以n′2為模的N2的解，這里用x表示該解，同時利用p2和q2為模，識別N2的值。在用x、n2來計算P′的值，即：

P′=Rep-Rec(x⊕n2,x&n2)

比對P′與P的值。若不相等，協議終止；若相等，說明x=N′，生成r4隨機數，生成新的共享密鑰Knew，用Knew、x計算Q的值，用x、r4計算L的值，用r4、Q計算V的值，用x、Knew來計算B′的值，并更新信息：Snew_ID=r4、B=B′，最后將(L，Q，V)傳送給Ti。

步驟7Ti收到信息后，先計算Q⊕N′得到新的共享密鑰K′new，計算L⊕N′得到r′4隨機數，用r′4、Q來計算V′的值，即：

V′=Rep-Rec(r′4⊕Q,r′4&Q)

比對V′與V的值。若不相等，協議終止；若相等，說明r′4=r4，用N′、K′new來計算B′的值，Ti更新信息：Knew=Q⊕N′，r4=L⊕N′，B=B′。此時Ti和Snew之間的密鑰保持一致，所有權完成轉移。

協議與其他此類協議比較所具備的優勢如下：在抵抗攻擊者發動攻擊方面，采用二次剩余對發送信息加密，在數學領域中，大素數的分解一直是無法破解的難題，因此采用二次剩余加密，能夠增大攻擊者的破解難度。在保證信息安全的前提下，要盡可能地降低系統的計算量，因此設計出一種基于超輕量級的采用按位運算實現的置換再交叉運算對部分信息進行加密，能夠滿足降低系統的計算量。

2 安全性分析

本文協議采用基于GNY邏輯形式化語言對協議進行邏輯形式化推理[16]。

(1) 協議形式化描述。

協議流程如下：

Msg1：Sold→Ti：Query、A。

Msg2：Ti→Sold：D″、E、F。

Msg3：Sold→Snew：G、E。

Msg4：Snew→Ti：H、G、M。

Msg5：Ti→Snew：N″、P。

Msg6：Snew→Ti：L、Q、V。

用GNY形式邏輯語言規范以上協議，描述如下：

Msg1：Ti<*Query、A；

Msg2：Sold<* {D″、E、F}；

Msg3：Snew<*{G、E}；

Msg4：Ti<*{H、G、M}；

Msg5：Snew<*{N″、P}；

Msg6：Ti<*{L、Q、V}。

(2) 協議初始化假設。

協議假設如下：Snew、Ti、Sold表示主體。

Sup1：(Sold_ID、Snew_ID、Knew、Kold、TID、r1、r2、r3、B)∈Ti；

Sup2：(p2、q2、n2、r4、Snew_ID、Knew)∈Sold；

Sup3：(Sold_ID、Kold、p1、q1、n1)∈Snew；

Sup4：Sold|≡#(r1、r2、r3、r4)；

Sup5：Ti|≡#(r1、r2、r3、r4)；

Sup6：Snew|≡#(r1、r2、r3、r4)；

(3) 協議證明目標。

目標的證明公式如下：

Goal1：Ti|≡Sold|～#{A}；

Goal2：Sold|≡Ti|～#{D″、E、F}；

Goal3：Snew|≡Sold|～#{G、E}；

Goal4：Ti|≡Snew|～#{H、G、M}；

Goal5：Snew|≡Ti|～#{N″、P}；

Goal6：Ti|≡Snew|～#{L、Q、V}。

(4) 協議證明過程。

因協議證明目標Goal2：Sold|≡Ti|～#{D″、E、F}；Goal3：Snew|≡Sold|～#{G、E}；Goal4：Ti|≡Snew|～#{H、G、M}；Goal5：Snew|≡Ti|～#{N″、P}；Goal6：Ti|≡Snew|～#{L、Q、V}的證明過程與協議證明目標Goal1：Ti|≡Sold|～#{A}證明過程相似，以協議證明目標Goal1為例。

∴ {A}∈Ti

∴Sold=#{A}

∴ {A}∈Sold

∴Sold|≡ #{A}

∴Ti|=Sold～{A}

∵ 新鮮性定義以及推導出來的Sold=#{A}、Ti|=Sold～{A}

∴ Goal1：Ti|≡Sold|～#{A}得證明。

本文協議與其他協議進行安全性比較結果如表1所示。

表1 協議之間的安全性比較

3 性能分析

性能分析部分選擇標簽為對象，標簽原所有者和標簽新所有者中均包含數據庫，數據庫具備強大的存儲空間和計算能力，因此不作為性能分析的對象。以標簽為對象時，主要關注于標簽一端的計算量，因對于現有的無源低成本計算量的標簽來說，標簽具備的計算能力受到嚴格的限制。本文協議與其他此類協議進行性能分析如表2所示。

表2 協議之間的性能比較

對于表2中符號進行下面的含義約定：用a表示二次剩余加密方法的計算量；用b表示產生隨機數的計算量；用c表示按位運算(按位運算一般包含按位或運算、按位異或運算、按位與運算、左移運算、右移運算)；用d表示置換再交叉運算加密方法的計算量。

在上述不同的運算中，計算量最大的是二次剩余，次之的是隨機數的產生計算量，置換再交叉運算及按位運算均屬于超輕量級的運算。現有的文獻已證明：超輕量級的運算進行次數的多與少，對協議的計算量所帶來的影響可以忽略。

以本文協議中3a的產生為例說明標簽一端的計算量的計算方法。1) 第一次用到二次剩余。標簽一端在步驟2中計算D″的時候，會第一次用到二次剩余。2) 第二次用到二次剩余。標簽一端在步驟5中計算N′的時候，會第二次用到二次剩余。3) 第三次用到二次剩余。標簽一端在步驟5中計算N″的時候，會第三次用到二次剩余。基于上述分析，本文協議標簽一端一共會有三次用到二次剩余加密方法對信息進行，因此是3a。從表2中，計算量角度出發協議進行性能比較分析，可以得出本文協議與文獻[14-15]中的協議計算量相當，但本文協議能夠彌補文獻[14-15]中的協議存在的安全缺陷問題，因此本文協議仍具備一定的使用價值。

4 結 語

標簽在其生命周期中，標簽的歸屬者經常發生變更，為確保標簽所有權的完整性，設計一種標簽所有權轉移協議。為能夠抵抗攻擊者發起的攻擊模型，協議采用二次剩余定理對傳送的部分信息進行加密，基于數學難題大數分解的二次剩余定理，具備較高的安全性；在保證安全的前提下，為盡可能降低系統的計算量，采用置換再交叉運算對傳送的另一部分信息進行加密，置換再交叉運算基于位運算實現，能夠極大程度上降低系統的計算量。對協議基于GNY邏輯形式化推理，推理出協議具備的安全性；將協議與其他協議進行性能分析，比對出協議具備低計算量的屬性。