基于Kummer曲面的RFID標(biāo)簽*

林齊平,張方國

1.興唐通信科技有限公司,北京100191

2.中山大學(xué)數(shù)據(jù)科學(xué)與計(jì)算機(jī)學(xué)院,廣州510006

3.廣東省信息安全技術(shù)重點(diǎn)實(shí)驗(yàn)室,廣州510006

1 簡介

橢圓曲線密碼(Elliptic curve cryptography,ECC)是比較有名并用得很多的公鑰密碼.ECC是由Koblitz[1]和Miller[2]首先獨(dú)立提出的.對給定的安全水平,橢圓曲線密碼系統(tǒng)的密鑰長度比其它的公鑰密碼更短,因此ECC被廣泛接受并應(yīng)用于資源受限的環(huán)境中.1989年,Koblitz提出ECC的擴(kuò)展,即超橢圓曲線密碼(HECC)[3],隨后跟從HECC的研究人員也有很多.現(xiàn)在HECC的應(yīng)用也慢慢跟上來了.從安全水平來說,有限域GF(2163)上的ECC和域GF(283)上的HECC被認(rèn)為安全性等價于1024比特的RSA[4].

(超)橢圓曲線密碼的主要運(yùn)算是標(biāo)量乘 [k]P,其中 P為橢圓曲線 E上一個點(diǎn) (或者超橢圓曲線Jacobian的一個除子),k為一個整數(shù).已經(jīng)有很多方法對(超)橢圓曲線上的標(biāo)量乘計(jì)算進(jìn)行優(yōu)化加速了.

自從 Cantor[5]的開創(chuàng)性工作以來,超橢圓曲線的標(biāo)量乘計(jì)算就一直采用 Cantor的算法.在上世紀(jì) 90年代,為了更有效地計(jì)算,Flynn給出了虧格 2超橢圓曲線的 Jacobian的計(jì)算公式[6].十年前,Duquesne繼續(xù)并推廣Flynn的工作,并得到Kummer曲面上的公式.Duquesne的計(jì)算公式的效率能與通常的標(biāo)量乘計(jì)算方法相匹敵[7–9].Gaudry等人使用theta函數(shù)基于Kummer曲面也提出虧格2曲線的快速標(biāo)量乘方法[10,11].

在特征為2的有限域上,對應(yīng)的Kummer曲面的標(biāo)量乘都有快速計(jì)算公式.在相同安全水平下,某些類型的曲線對應(yīng)的Kummer曲面的標(biāo)量乘甚至比最好的橢圓曲線標(biāo)量乘還快.由于標(biāo)量乘很有效而且只需要很少的寄存器,可以用于低能耗、芯片和計(jì)算時間受限的輕量級密碼系統(tǒng),比如RFID標(biāo)簽上.

在 1999年,Smart等人使用虧格 2的 Kummer曲面快速標(biāo)量乘設(shè)計(jì)了一個 Diffie-Hellman協(xié)議.2017年,Renes等人[12]使用 Kummer曲面快速標(biāo)量乘提出 qDSA,即商數(shù)字簽名算法.在 2018年,Costello[13]使用Kummer曲面加速基于超奇異同源的密碼計(jì)算.但是,在Kummer曲面上構(gòu)造其它協(xié)議或者加密方案特別少.需要通過精巧設(shè)計(jì),避免Kummer曲面上的加法計(jì)算,才能得到運(yùn)行在Kummer曲面上的協(xié)議.

在本文中,我們把Schnorr的鑒別協(xié)議推廣到Kummer曲面上并用于構(gòu)造RFID標(biāo)簽.

RFID(Radio-Frequency Identification)標(biāo)簽是用于鑒別目的的小設(shè)備,廣泛應(yīng)用于供應(yīng)鏈管理,比如奢侈品的防偽等等.目前用于防偽技術(shù)的RFID還處于初級階段.很多鑒別和隱私保護(hù)協(xié)議都使用對稱密碼[14–16].但是,如果在RFID標(biāo)簽中使用對稱密碼,那么需要在數(shù)據(jù)庫中安全地存儲私鑰.而且,當(dāng)讀取RFID標(biāo)簽時,為了在數(shù)據(jù)庫中找到正確的密鑰需要進(jìn)行復(fù)雜的搜索.這個過程會浪費(fèi)很多時間,特別是在超大型應(yīng)用中更是如此.

最近已經(jīng)有應(yīng)用于RFID標(biāo)簽的相應(yīng)的基于公鑰的協(xié)議.目前基于非對稱密碼的協(xié)議可以分為兩類.

(1)一類是使用橢圓曲線方法[17–20].在這類方法中,為了抵抗側(cè)信道攻擊,ECC的標(biāo)量乘通常使用Montgomery階梯方法.如果鑒別協(xié)議不需要y坐標(biāo)的話,標(biāo)量乘還可以使用只用x坐標(biāo)來計(jì)算[21].

(2)另一類使用超橢圓曲線.Fan等人[22,23]使用HECC構(gòu)造了一個RFID標(biāo)簽協(xié)議.他們使用的超橢圓曲線的參數(shù)為h(x)=x和f(x)=x5+f3x3+x2+f0.

我們在表1中比較了ECC和HECC的計(jì)算復(fù)雜性,其中I為域的逆運(yùn)算,M為乘法運(yùn)算,S為平方運(yùn)算.

表1 特征2的標(biāo)量乘比較[4]Table 1 Comparison of scalar multiplication in characteristic 2[4]

本文的組織如下:在第 2節(jié)中,我們簡單描述Kummer曲面.在第3節(jié)中,我們給出了我們的基于Kummer曲面的鑒別協(xié)議.在第4節(jié)中,我們分析了基于Kummer曲面的RFID標(biāo)簽所需要的資源.第5節(jié)是本文的總結(jié).

2 預(yù)備知識

在上世紀(jì) 90年代初期,Flynn提出了虧格 2曲線的Jacobian公式.Flynn的公式很有效,在1999年,基于Flynn的結(jié)果,Smart等人提出了一個快速密鑰交換協(xié)議.后來,基于Flynn的公式,Duquesne提出Kummer曲面計(jì)算標(biāo)量乘的公式.在本節(jié)中,我們描述GF(2n)上的Kummer曲面.

2.1 GF(2n)上虧格 2曲線的分類

定義在特征為2的有限域上的虧格2曲線如下:

其中

事實(shí)上,我們只關(guān)心型為

的曲線.虧格2曲線可以分為以下三類[24]:

(1) 類型 I:h20;

(2) 類型 II:h2=0,h10;

(3) 類型 III:h2=h1=0,h00.

在本文中,我們只針對類型為 II的虧格 2曲線.任何類型 II曲線可以定義為型如y2+xy=x5+f3x3+εx2+f0的方程,其中ε∈{0,1}.類型II的同構(gòu)類大約有2q2.因此很容易能找到符合密碼學(xué)應(yīng)用的類型II的曲線.

2.2 Kummer曲面

對每一個特征為2,類型為II的虧格2曲線,存在如下一個P3上對應(yīng)的Kummer曲面K[8]:

其中

在本文中,我們令 (k1,k2,k3,k4)為 Kummer曲面上一個元素.除了階為2的點(diǎn)之外,從 Jacobian到P3的映射是2:1的關(guān)系.

當(dāng)Jacobian映射到P3上時,群的運(yùn)算法則丟失了.Kummer曲面上的加法公式不再保持,因此我們把Kummer曲面上的加法稱為偽加法公式.給定Kummer曲面上的兩個元素A和B,當(dāng)且僅當(dāng)我們先知道A?B的值之后我們才能計(jì)算A+B的結(jié)果.Montgomery階梯方法恰好可以用于計(jì)算該過程,因?yàn)樵贛ontgomery階梯方法中A?B在每一步中都保持不變.

算法1虧格2曲線的Montgomery階梯標(biāo)量乘算法Input:D ∈ J(K)and k=(kn?1,···,k0)2 ∈ N Output:κ(kD),kD 在Kummer曲面上的象1初始化 (A,B)=((0,0,0,1),k(D)),其中(0,0,0,1)為J(C)的單位元在Kummer曲面的象.2for i=n?1 down to 0 do 3 if ki=0 then(A,B)=(2A,A+B);5 end 6 else if ki=1 then 4(A,B)=(A+B,2B);8 end 9end 10返回A 7

在每一步中,Montgomery階梯方法計(jì)算一個加法和一個倍加,這種方法恰好可以抵御側(cè)信道攻擊.Duquesne提出的類型II曲線的偽加法和倍加公式如下[9].

命題 1令G是特征為2的有限域,C為定義在G上類型為II虧格2的曲線.κ為從JacobianJ到Kummer曲面的映射.令A(yù),B∈J(C),并且κ(A)=[k1,k2,k3,k4],κ(B)=[l1,l2,l3,l4]分別為它們在Kummer曲面對應(yīng)的象.假設(shè)A?B已知,并且k1(A?B)=1.那么偽加法公式如下:

α=k1l4+k2l3,

β=k4l1+k3l2,

k1(A+B)=(α+β)2,

k2(A+B)=(k1l3+k3l1)2+k1(A+B)k2(A?B),

k3(A+B)=k3l1α+k1l3β+k1(A+B)k3(A?B),

k4(A+B)=αβ+k1(A+B)k4(A?B)

倍加公式如下:

3 Kummer曲面上的鑒別協(xié)議

Schnorr的鑒別協(xié)議[25,26]是基于群F?q或者有限域上的橢圓曲線或者有限域上虧格g的曲線的Jacobian上的離散對數(shù)問題的.在本節(jié)中,我們把Schnorr的鑒別協(xié)議推廣到Kummer曲面上.

3.1 鑒別協(xié)議

? 輸入:系統(tǒng)參數(shù)集合(q,f3,ε,f0,P,n).其中q指定有限域,f3,ε,f0定義一個與虧格2類型II曲線相對應(yīng)的Kummer曲面,P為階為n的Kummer曲面上一個元素.

? 證明者(標(biāo)簽):證明者的私鑰為a,且有Z=?aP.

? 協(xié)議的過程:協(xié)議包括以下交互信息:

(1)證明者→驗(yàn)證者:{X}.證明者選取r∈RZn,并計(jì)算X=rP.然后發(fā)送X給驗(yàn)證者.

(2)驗(yàn)證者→證明者:{e}.驗(yàn)證者選取e∈RZn并把它發(fā)送給證明者.

(3)證明者→驗(yàn)證者:{y,R}.證明者計(jì)算y=ae+rmodn和R=(2ae+rmodn)P,然后把它們發(fā)送給驗(yàn)證者.

(4)驗(yàn)證者.驗(yàn)證者接收到{y,R}之后,他開始計(jì)算yP,eZ并驗(yàn)證pseudo-add(yP,eZ,R)是否等于X,如果驗(yàn)證通過則接受,否則拒絕.

圖1 Kummer曲面上的Schnorr協(xié)議Figure 1 Schnorr’s protocol on Kummer surface

3.2 協(xié)議的分析

我們的鑒別協(xié)議可以完全運(yùn)行于 Kummer曲面上.協(xié)議的正確性可以驗(yàn)證如下.當(dāng)驗(yàn)證者接收到{y,R}后,他計(jì)算Kummer曲面上的標(biāo)量乘yP和eZ.然后他有四個點(diǎn)yP,eZ,R和X,因此他可以使用Kummer曲面上的偽加法公式驗(yàn)證yP+eZ是否與X相等.偽加法公式能成功運(yùn)行是因?yàn)轵?yàn)證者知道R=yP?eZ的值.

從圖1可以看到,證明者需要計(jì)算兩個標(biāo)量乘和一個模乘,驗(yàn)證者需要兩個標(biāo)量乘和一個偽加法計(jì)算.與原來的協(xié)議相比,為了能在Kummer曲面上執(zhí)行Schnorr鑒別協(xié)議,我們需要額外多計(jì)算一次標(biāo)量乘.但是,因?yàn)橛?jì)算的有效性能抵消掉額外的一次標(biāo)量乘計(jì)算,因此這是可以接受的.

我們的協(xié)議的安全性是基于 Kummer曲面上求解離散對數(shù)困難問題的.而Kummer曲面離散對數(shù)問題的困難性并不低于虧格2曲線的Jacobian的離散對數(shù)問題[27].

3.3 基于Kummer曲面的RFID標(biāo)簽

我們可以利用 Kummer曲面的鑒別協(xié)議來設(shè)計(jì) RFID標(biāo)簽.協(xié)議的主要操作是標(biāo)量乘.設(shè)計(jì)基于Kummer曲面的鑒別協(xié)議主要是硬件中的有限域的有效操作.下一節(jié)中我們分析基于 Kummer曲面的RFID標(biāo)簽的資源情況.

4 Kummer曲面上的操作

在本節(jié)中,我們將分析Kummer曲面上的標(biāo)量乘所需要的寄存器、點(diǎn)壓縮和解壓縮過程.

4.1 標(biāo)量乘所需要的寄存器

表2,3是運(yùn)行在Kummer 曲面上的偽加法公式和倍加公式的寄存器情況,其中前 5個寄存器是參數(shù)和點(diǎn)κ(A?B),分別是R1=,R2=f3,R3=k2(A?B),R4=k3(A?B),R5=k4(A?B).不失一般性,我們假設(shè)k1(A?B)=1.從表2和表3可以看到,運(yùn)行Kummer曲面上的偽加法和倍加總共需要13個寄存器.

表2 特征2的偽加法公式Table 2 Points pseudo-addition in characteristic 2

表3 特征2的倍加公式Table 3 Points doubling in characteristic 2

為了能抗側(cè)信道攻擊,非對稱密碼在計(jì)算標(biāo)量乘的時候需要使用 Montgomery階梯方法.Montgomery階梯方法計(jì)算結(jié)構(gòu)穩(wěn)定,因此天然能抗簡單的能量攻擊和時間攻擊.同時 Montgomery階梯方法還很適合于硬件實(shí)現(xiàn).

4.2 點(diǎn)壓縮與解壓縮

命題 2Kummer曲面上的點(diǎn)(k1,k2,k3,k4)可以使用最多兩個有限域元素加上1比特來表示.

證明:Kummer曲面是屬于空間P3上的,因此一個點(diǎn)可以用3個有限域元素來表示.Kummer曲面上的單位元為(0,0,0,1).因此,Kummer曲面上除了單位元以外,一個點(diǎn)(k1,k2,k3,k4)中的k1,k2,k3最少有一個非0.不失一般性,假設(shè)k1?=0,那么令k1=1.現(xiàn)在點(diǎn)(k1,k2,k3,k4)可以由(k2,k3,b)來表示了,其中b∈{0,1}為k4的最低比特?cái)?shù).給定k2,k3,我們有以下方程成立:

其中K2(k1,k2,k3),K1(k1,k2,k3),且K0(k1,k2,k3)已知.該二次方程有兩個根,最后我們可以使用b來確定正確的k4的值.

4.3 性能分析

在文獻(xiàn)[22,23]中,Fan等人的實(shí)驗(yàn)結(jié)果表明HECC也可以用于RFID標(biāo)簽設(shè)計(jì)上.他們用于構(gòu)造RFID標(biāo)簽而選取的曲線同樣也是虧格2中類型II的曲線.但是HECC的缺點(diǎn)是標(biāo)量乘的計(jì)算太復(fù)雜.經(jīng)過近年來的發(fā)展,在新的坐標(biāo)公式和技術(shù)下,HECC的實(shí)現(xiàn)性能已經(jīng)和ECC相當(dāng)了.

我們的基于Kummer曲面的RFID標(biāo)簽方案比其它虧格2的方案更優(yōu).而且,我們方案的性能還與某些ECC方案的實(shí)現(xiàn)性能不相上下.

記M為有限域F2m的乘法,S為F2m上的平方運(yùn)算.有限域F2m的二次擴(kuò)域?yàn)镕22m.在二次擴(kuò)域F22m中,兩個元素相乘

為經(jīng)典的計(jì)算,需要4M和1個加法.使用Karatsuba算法[28]后,兩個擴(kuò)域元素相乘為

(a1x+a0)(b1x+b0)=a1b1x2+((a1+a0)(b1+b0)?a1b1?a0b0)x+a0b0

只需要3M和4個加法計(jì)算.而二次擴(kuò)域上的平方計(jì)算量通常都比兩個基域的平方計(jì)算量要多.

不管是使用經(jīng)典的還是 Karatsuba算法,二次擴(kuò)域中的一個模乘計(jì)算量要比3個基域的模乘計(jì)算量多.我們忽略加法計(jì)算量,并假設(shè)基域的模乘與二次擴(kuò)域的模乘的計(jì)算量比率為1:3,平方的計(jì)算量的比率為1:2.那么表4表示在相同安全水平下的標(biāo)量乘比較 (假設(shè)ECC使用有限域F22m而 Kummer曲面使用有限域F2m).其中在特征為2的有限域中,在多項(xiàng)式基中通常S=0.3M,而在規(guī)范基中平方運(yùn)算就是移位運(yùn)算,因此S=0.

表4 同等安全水平下ECC和Kummer曲面計(jì)算量比較Table 4 Computation of ECC and Kummer surface over same security level

可能基于Kummer曲面上的RFID標(biāo)簽的計(jì)算時間在RFID標(biāo)簽一側(cè)比ECC的慢,但是在驗(yàn)證者一側(cè),基于Kummer曲面上的RFID標(biāo)簽的計(jì)算速度確實(shí)比較快.

5 總結(jié)

在本文中,我們擴(kuò)展了Schnorr的鑒別協(xié)議到Kummer曲面上,并用它來構(gòu)造一個巧妙的RFID標(biāo)簽.我們的結(jié)果表明基于 Kummer曲面的 RFID標(biāo)簽方案比其它虧格為 2的方案更好.而且,與基于ECC的RFID標(biāo)簽相比,我們的方案在驗(yàn)證的時候能節(jié)省百分之13到15的計(jì)算量.在應(yīng)用方面,RFID與區(qū)塊鏈可以結(jié)合起來組成一個閉合的信任鏈,從生產(chǎn)到消費(fèi)全生命周期可以實(shí)現(xiàn)可追溯、去信任等,這在將來將會有很多這方面的應(yīng)用.