有限域上橢圓曲線Weil對的計算

胡建軍,王 偉,李恒杰

(蘭州文理學(xué)院 數(shù)字媒體學(xué)院,蘭州 730010)

0 引 言

橢圓曲線上M扭曲的Weil對是密碼學(xué)領(lǐng)域的一個重要問題,其用于解決橢圓曲線的離散對數(shù)和開發(fā)密碼系統(tǒng)。2004年,Miller[1]較為詳實地研究了Weil對的性質(zhì)和其有效計算,開啟了Weil對在公約密碼系統(tǒng)中的應(yīng)用。隨后許多學(xué)者進行了大量卓有成效的研究,這些關(guān)于橢圓曲線Weil對的研究以Miller算法為基礎(chǔ),不僅有大量的理論拓展[2-10],而且還有廣泛的應(yīng)用研究[11-13]。然而,實踐研究發(fā)現(xiàn),一些理論和應(yīng)用研究過分應(yīng)用了Miller算法,導(dǎo)致部分理論研究需要新的方法支持。為此筆者給出了Weil對計算的3種方法,通過實例指出了Miller算法在有限域上實施計算時點的選擇問題,分析了兩種不同方法使用Miller算法的差異,指出了運用Miller算法計算Weil對應(yīng)該注意的問題,驗證了利用Weil對計算橢圓曲線的離散對數(shù)。通過有限域上橢圓曲線Weil對計算問題的研究,將對已有的理論研究形成挑戰(zhàn),同時對于公約密碼體制的應(yīng)用和推廣具有重要的意義。

1 有限域上的橢圓曲線和Weil對的計算

1.1 有限域上的橢圓曲線相關(guān)概念[14]

設(shè)p>3是一個素數(shù),q=pr,r≥1,E(Fq)表示橢圓曲線上的有限域,E(Fq)上的橢圓曲線E是一個形如E:y2=x3+Ax+B的方程,其中A,B∈Fq,且Δ=-16(4A3+27B2)≠0,點對(x,y)∈Fq×Fq是E上滿足方程E:y2=x3+Ax+B的一個解,且要么y=0,要么-4A2-27B3|y2。E(Fq)表示Fq上所有滿足方程E:y2=x3+Ax+B解的點集,包括無窮遠(yuǎn)點O。E(Fq)上“+”運算定義如下

(x,y)+O=O+(x,y)=(x,y)

(1)

(x,y)+(x,-y)=O

(2)

x3=λ2-2x,y3=λ(x-x3)-y

(3)

x3=μ2-x1-x2,y3=μ(x1-x3)-y1

(4)

因此(E(Fq),+)是一個以O(shè)為單位元的阿貝爾群。

1.2 扭曲子群和除子的特征

橢圓曲線上的有限階點是二維的[1]。設(shè)K是一個特征為p的域,Ω是K的代數(shù)封閉空間,M是一個與p互素的正整數(shù),作為一個阿貝爾群,則有E[M]?ZM×ZM,其中ZM表示階為M的循環(huán)群。Weil配對是定義在E[M]上點的非退化內(nèi)積。定義E[M]={T∈E(Fq)|MT=O}是M扭曲點的集合。下面給出一些與Weil配對相關(guān)的一些理論。

引理1 設(shè)D是E上的除子,如果deg(D)=0,則div(f)=D?sum(D)=O[6]。

假設(shè)f°M滿足f(M(T))=f(MT),可以驗證f°M和gM有相同的除子,從而令f°M=gM。

若T,S,T1,T2,S1,S2∈E[M],則

eM(T1+T2,S)=eM(T1,S)eM(T2,S),eM(T,S1+S2)=eM(T,S1)eM(T,S2)

(5)

eM(T,S)=eM(S,T)-1

(6)

eM(T,T)=eM(S,S)=1

(7)

若eM(S,T)=1,則

T=O或S=O

(8)

引理2 假設(shè)函數(shù)f和h在E上沒有公共點,則f(div(h))=h(div(f))[1,8]。

設(shè)μM={x∈Fq|xM=1}是Fq中第M個單位根的群,因為M是素數(shù),因而μM是一個循環(huán)群。

引理4 假設(shè){T1,T2}是E[M]的一個基,則{T1,T2}是E[M]的第M個本原單位根[8]。

定理1 如果eM(T,S)≠1,則T和S線性無關(guān)。

證明 假設(shè)T和S線性相關(guān),則存在一個整數(shù)a,不妨令T被S線性表示,即T=aS。由式(7)可知,eM(T,S)=eM(aS,S)=eM(S,S)a=1,這與假設(shè)矛盾,因此結(jié)論成立。

定理3給出了3種計算Weil對的方法。下面是Miller算法理論基礎(chǔ)。

假設(shè)R=P+Q,經(jīng)過點R和-R的直線垂直x軸。令經(jīng)過點P和Q的直線方程為y=kx+m,因為P、Q和R3點共線,則f(x,y)=y-kx-m是橢圓曲線E的一個除子,即div(f)=(P)+(Q)+(-R)。由經(jīng)過點R和-R的直線垂直x軸可得橢圓曲線E的另一個除子g(x,y)=x-xR。因此,有

(9)

(10)

的定義,其中λ見式(3),μ見式(4)。

下面給出橢圓曲線E上Weil對計算的Miller算法。

算法1 Miller算法[7]。

∥選擇X和W。

1) 讓X=P+T或P或S-P或-P,W=T或S。

2) 讓f=1,n=「log2M?,i=n-1,mi=(M)2∥將M轉(zhuǎn)換成二進制表示。

3) 當(dāng)i>0時,重復(fù)執(zhí)行下列語句序列

f=f2hWW,W=2W。

若mi=1,則f=fhST,W=W+P。

4)返回f。

用下面的方法可以獲得階為M的線性無關(guān)的兩個點[8]。

算法2 求解階為M的線性無關(guān)的兩個點[6]。

按照下列步驟選擇S和T。

1) 隨機選擇一個點P∈E(Fq)。

2) 計算點P的階N。

4) 重復(fù)1)～3)選擇S,當(dāng)S和T線性無關(guān)時結(jié)束。

2 Weil對計算實例和分析

2.1 Weil對計算實例

為提高計算效率,采用PARI軟件和編程相結(jié)合的方法計算Weil對。其中橢圓曲線的點由PARI軟件的E.gen功能獲得,點加和倍乘運算分別利用PARI軟件的elladd和ellmul函數(shù)獲得,其他的數(shù)據(jù)通過編程實現(xiàn)。下面是一個Miller算法實例。

假設(shè)有限域F631上的橢圓曲線E為y2=x3+30x+34,則E(F631)?Z/5Z×Z/130Z,驗證發(fā)現(xiàn)點S=(36,60)、T=(121,387)、P=(262,497)、Q=(213,75)和R=(0,36)在曲線上,其中S,T∈E[5],P,Q∈E(F631),P,Q,R的階均為130,且S和T線性無關(guān),下面給出計算橢圓曲線E的線性對e5(S,T)的過程。

fS(P+T)=fS([483,248])=106,fS(P)=fS([262,497])=42,

fT(-P+S)=fS([465,196])=590,fT(-P)=fS([262,134])=188

由于mod((242)5,631)=1,因此242是e5(S,T)的第5個單位根。

fT(Q+S)=fT([144,241])=487,fT(Q)=fT([213,75])=502,

由于mod((232)5,631)≠1,因此利用定理3和算法1未能計算出e5(S,T)的第5個單位根。

2.2 兩種不同Weil對計算方法分析

另外,根據(jù)算法2驗算可知,點T=(121,387)可以由點P=(262,497)或Q=(213,75)生成,點R=(0,36)不能生成S=(36,60)或T=(121,387)之一。由此可見,計算eM(S,T)與E(Fq)上任意點的選擇無關(guān)。

3 MOV攻擊

1993年,Menezes等[15]提出了一種將橢圓曲線上的對數(shù)問題約減到有限域上的對數(shù)問題求解算法,簡稱MOV(Menezes-Okamoto-Vanstone)攻擊算法。MOV攻擊算法基于Weil配對的求解。

假設(shè)S,T,R∈E[M],R∈〈T〉,R=lT,S和T線性無關(guān),則eM(R,S)=eM(lT,S)=(eM(T,S))l。

算法3 MOV算法。

輸入:T∈E[M]和R∈〈T〉;

輸出:滿足R=lT的l。

1) 在E[M]中尋找一個滿足S?〈T〉的S。

2) 計算α=eM(T,S)。

3) 計算β=eM(R,S)。

MOV算法只能求解同階上的離散對數(shù),不能在小子階上計算大子階的離散對數(shù)。而MOV算法攻擊的實質(zhì)是求解小子階上的離散對數(shù)。

定理4 假設(shè)P,Q∈E[N],Q∈〈P〉,Q=mP,M|N,S,T,R∈E[M],R∈〈T〉,R=lT,S和T線性無關(guān),則求解m是困難的。

證明 假設(shè)N=dM,則dP,dQ∈E[M]。不妨令R=dP,則α=eM(T,S),β=eM(R,S)=eM(lT,S)=αl,γ=eM(R,S)m=eM(T,S)ml,由于eM(R,S)M=1,而當(dāng)M|ml時,γ恒為1。因為m∈{1,2,…,N-1},這樣的m不止1個,因此求解m是困難的。

利用2.1的實例數(shù)據(jù),驗證定理4的結(jié)論。

已知Q=7P。令S=26P=(420,483),R=26Q=(121,244),T=(36,60),W=(0,36),則-W=(0,595),S-W=(36,124),W+T=(315,385),R-W=(176,145),利用Miller算法可得

fS(W+T)=176,fS(W)=556,fT(-W)=579,

fT(S-W)=0,fT(R-W)=475,fR(W)=427,fR(W+T)=181。

從而

因此無法有效獲得數(shù)值7。

當(dāng)然,如果在130的階上計算,可得到數(shù)值7,但此時的算法復(fù)雜度為exp(c(log(qd))1/3(loglog(qd))2/3),其中c是常數(shù),d是橢圓曲線的度。

由此可見,當(dāng)階N很大且不是異常曲線時,MOV攻擊算法需要很大時間代價,攻擊性很弱。

4 結(jié) 語

有限域橢圓曲線上的Weil對計算對橢圓曲線密碼系統(tǒng)具有重要的作用。筆者給出了計算橢圓曲線第M個本原單位根時,需要選擇線性無關(guān)的兩個階為M的點,并給出了利用Miller算法計算Weil對時需要使用的公式,分析了兩個不同公式之間的差異。同時利用MOV算法驗證了Weil對計算橢圓曲線的離散對數(shù),給出了MOV算法的應(yīng)用領(lǐng)域。通過有限域上橢圓曲線Weil對計算問題的研究,將會對已有的理論研究結(jié)果形成挑戰(zhàn),同時對于公約密碼體制的應(yīng)用和推廣具有重要的意義。