吳宏鋒， 宋貞貞

北方工業(yè)大學(xué) 理學(xué)院， 北京 100144

1 引言

域K上的橢圓曲線定義為域K上的一維阿貝爾簇. 一般把橢圓曲線的方程寫成Weierstrass 方程

其中a1，a3，a2，a4，a6∈K. 橢圓曲線的點(diǎn)乘或標(biāo)量乘運(yùn)算， 就是給定橢圓曲線上一個(gè)點(diǎn)P和一個(gè)正整數(shù)k， 計(jì)算k個(gè)點(diǎn)P的和[k]P， 它是所有基于橢圓曲線的各類密碼協(xié)議中的核心運(yùn)算. 改進(jìn)點(diǎn)乘的運(yùn)算效率有多種途徑， 其一就是在不同的曲線模型上構(gòu)造更加快速的計(jì)算公式. 有很多種橢圓曲線的表示模型， 諸如Edwards 曲線[1]、Jacobi 四次曲線[2]或Jacobi 相交曲線[3]等等. 不同的曲線模型有各自的優(yōu)點(diǎn)和特殊應(yīng)用.

早在Jacobi 時(shí)代， 人們就研究過形如y2= (1-x2)(1-k2x2) 的橢圓曲線， 其中k/= 0，±1. 該類型的橢圓曲線可由Jacobi 橢圓函數(shù)參數(shù)化， 一個(gè)點(diǎn)P= (x，y) 可以參數(shù)化表示為(sn(u)，cn(u)dn(u))，因此易于得到它上的加法公式. Jacobi 四次曲線在密碼學(xué)相關(guān)領(lǐng)域中的研究始自Chudnovsky 和Chudnovsky[4]. 他們首先在曲線y2=x4+ax2+b上使用權(quán)射影坐標(biāo)提出不使用逆運(yùn)算的點(diǎn)加和倍乘公式. Billet 和Joye[2]則在一般的Jacobi 四次曲線Y2=dX4+2aX2Z2+Z4上提出了更加快速的統(tǒng)一(unified) 點(diǎn)乘公式， 也就是說， 該運(yùn)算公式不區(qū)分兩個(gè)點(diǎn)是不是相同. Duquesne[5]則進(jìn)一步改進(jìn)了該點(diǎn)乘公式的效率. Hisil 等人[6-8]則引入了一系列的不同坐標(biāo)表示和快速的倍乘和統(tǒng)一加法公式. 關(guān)于Jacobi 四次曲線的發(fā)展歷史可以參考文獻(xiàn)[2，6].

Montgomery[9]最早提出了一種簡(jiǎn)單的被稱為Montgomery 階梯(ladder)的Montgomery 算法. 在Montgomery 算法的每一步中， 都需要計(jì)算點(diǎn)加和倍乘運(yùn)算， 因此該算法還抵抗簡(jiǎn)單的能量攻擊. Montgomery 算法使用差分加法(differential addition) 和倍乘公式， 能有效地提高點(diǎn)乘運(yùn)算的效率. 該算法的關(guān)鍵是在計(jì)算過程中始終保持兩個(gè)點(diǎn)的差不變.

提高點(diǎn)乘運(yùn)算效率是通過縮減點(diǎn)乘運(yùn)算中基本的有限域運(yùn)算的次數(shù)實(shí)現(xiàn)的. 表示有限域運(yùn)算花費(fèi)多少的基本運(yùn)算包括有限域上元素的乘法運(yùn)算(記作M)， 平方運(yùn)算(記作S) 及一個(gè)常數(shù)和其它有限域元素的運(yùn)算(記作D). 在Montgomery 曲線上執(zhí)行差分加法運(yùn)算， 不需要所有的坐標(biāo)都參與， 在仿射情形下只需要使用點(diǎn)的x-坐標(biāo)即可完成整個(gè)運(yùn)算， 當(dāng)然， 如果需要可以在最后的時(shí)候恢復(fù)最終計(jì)算結(jié)果的其它坐標(biāo). 在射影坐標(biāo)下， 可以使用(X:Z) 兩個(gè)坐標(biāo)而不引入Y坐標(biāo)參與計(jì)算， 從而達(dá)到不使用計(jì)算消耗很大的有限域元素求逆運(yùn)算的目的. 這種使用部分坐標(biāo)參與計(jì)算的技巧不僅減小了空間存儲(chǔ)規(guī)模， 更有利于資源受限環(huán)境下的實(shí)際應(yīng)用， 而且提高了點(diǎn)乘運(yùn)算的效率. 正是基于此， 人們也研究其它曲線模型上的快速M(fèi)ontgomery 差分加法算法. 諸如扭Edwards 曲線上的差分算法[10]、Jacobi 四次曲線上的差分算法[11]. Jacobi 四次曲線上的混合加法和倍乘運(yùn)算的最快記錄是由Hisil[6]獲得的， 加法和倍乘運(yùn)算的花費(fèi)分別是6M+3S+1D和2M+5S. 但這些公式需要六個(gè)坐標(biāo)參與表示一個(gè)點(diǎn). 顧海華等人[11]首先研究了Jacobi 四次曲線y2=k2x4+2ax2+1 上的差分加法公式， 在計(jì)算過程中只需要點(diǎn)的(X:Z) 坐標(biāo)， 而且混合加法和倍乘運(yùn)算的總花費(fèi)只需要5M+4S+5D.

本文主要研究形如Wa，b:y2=b2(a2- 4)x4- 2abx2+ 1 的Jacobi 四次曲線， 該類曲線在所有Jacobi 四次曲線中的比例接近二分之一， 且具有很好的密碼學(xué)屬性. 通過構(gòu)造新的雙有理等價(jià)變換， 本文得到了非?？焖俚牟罘旨臃ê捅冻斯? 在射影w-坐標(biāo)系統(tǒng)下， 混合加法和倍乘運(yùn)算的總花費(fèi)僅需要5M+4S+1D或者3M+6S+3D. 相較于Jacobi 四次曲線上的已有結(jié)果， 本文提出的公式是目前最有效的.

本文的組織結(jié)構(gòu)如下， 第2 節(jié)回顧并總結(jié)了Jacobi 四次曲線的基本知識(shí)和差分加法公式的基本內(nèi)容，第3 節(jié)研究了Wa，b曲線的一般性質(zhì)， 第4 節(jié)構(gòu)造快速的差分加法公式并給出快速算法. 最后第5 節(jié)總結(jié)全文并和以前的研究作簡(jiǎn)要的對(duì)比.

在整個(gè)文章中， 如果不加說明， 總是假定域K和有限域Fq的特征大于3.χ表示有限域Fq上的二次特征，u是有限域Fq上的平方元當(dāng)且僅當(dāng)χ(u)=1.

2 預(yù)備知識(shí)

2.1 Jacobi 四次曲線

設(shè)K是特征不等于2 的域.K上的Jacobi 四次曲線定義為

注意點(diǎn)(0，-1) 是一個(gè)2 階點(diǎn)，Ed，a上沒有其它的仿射二階點(diǎn). 退奇異性產(chǎn)生兩個(gè)二階無窮遠(yuǎn)點(diǎn)， 這兩個(gè)點(diǎn)定義在K上當(dāng)且僅當(dāng)d是K上的平方元. 通過簡(jiǎn)單的代數(shù)運(yùn)算可知， 2-y21+ax21=1-dx41， 且2-y21+ax21= 0 當(dāng)且僅當(dāng)[2]P是無窮遠(yuǎn)點(diǎn). 使得[2]P是無窮遠(yuǎn)點(diǎn)的P是使得公式(1) 不成立的僅有的點(diǎn)， 因此公式(1) 不是完全的， 完全的含義是指公式對(duì)任意點(diǎn)都成立.

在射影坐標(biāo)下， 單位元表示為(0 : 1 : 1). 點(diǎn)(X:Y:Z) 的逆是(-X:Y:Z). 在射影坐標(biāo)下， 倍乘公式表示為[2](X1:Y1:Z1)=(X3:Y3:Z3)， 其中

加法公式(2) 是統(tǒng)一的， 即它不要求兩個(gè)點(diǎn)不一定不同， 但一般來說該公式不是完全的. 對(duì)任意的d，x1，x2∈K， 如果d是非平方元， 那么dx21x22/=1. 如果d是平方元， 但d(a2-d)/=0， 且點(diǎn)P=(x1，y1)和Q=(x2，y2) 是奇數(shù)階點(diǎn)， 則dx21x22/=1. 關(guān)于更多的討論公式的完全性的內(nèi)容可見文獻(xiàn)[6].

2.2 Differential addition

1987 年， Montgomery[9]提出了一個(gè)能抵抗邊信道攻擊的Montgomery 算法(見算法1). 在該算法的每一步都執(zhí)行加法和倍乘運(yùn)算， 因此可以認(rèn)為在循環(huán)體中每一步循環(huán)所消耗的能量或計(jì)算時(shí)間都是無差異的， 因此可以抵抗簡(jiǎn)單能量分析攻擊. 在Montgomery 算法中， 如果采用射影坐標(biāo)， 則在中間的計(jì)算過程中只需要點(diǎn)的X和Z坐標(biāo)， 而不需要Y坐標(biāo)參與計(jì)算. 在算法結(jié)束時(shí)， 如果需要恢復(fù)Y坐標(biāo)， 這可以通過公式由X和Z坐標(biāo)計(jì)算得到.

算法1 Montgomery 算法Input: P ∈E(Fq)， k = ∑t-1 i=0 ki2i， where ki ∈{0，1}， kt-1 /= 0.Output: kP ∈E(Fq).1 P1 ←P，P2 ←2P;2 for i = t-2 down to 0 do 3 if ki = 0 then P2 ←P1 +P2， P1 ←2P1;5 end 6 else 4 P1 ←P1 +P2， P2 ←2P2;8 end 9 end 10 return P1 7

給定點(diǎn)P， 要計(jì)算[k]P. 在算法的主要執(zhí)行過程中， 主要的中間參數(shù)是點(diǎn)P1和P2. 在初始化過程中，分別把P和2P賦給P1和P2. 迭代過程中，如果ki=0，把(2P1，P1+P2)賦給(P1，P2). 如果ki=1，把(P1+P2，2P2) 賦給(P1，P2). 算法最關(guān)鍵的地方在于， 任何時(shí)候總有關(guān)系式P2-P1=P成立. 這是該算法可以忽略掉Y坐標(biāo)參與其中的關(guān)鍵. 當(dāng)?shù)Y(jié)束時(shí)， 返回P1=[k]P. 例如， 計(jì)算[49]P=(110001)2P，得到鏈

用x(P) 表示點(diǎn)P的x-坐標(biāo)(在射影坐標(biāo)系統(tǒng)下， 表示X和Z坐標(biāo)對(duì)(X:Z)). 如果知道{x(P)，x(Q)，x(P+Q)，x(P-Q)}中的任意三個(gè)都可以確定第四個(gè)的值. 我們用xADD 和xDBL 表示Montgomery 算法中的差分加法和倍乘， 這個(gè)技巧稱為Montgomery ladder， 算法2 展示了該過程， 該算法由x(P) 計(jì)算x([k]P). 最后的值x1=x([k]P). 最后的值x2可以用來恢復(fù)點(diǎn)[k]P的y-坐標(biāo).

算法2 Montgomery ladder Input: x(P) where P ∈E(Fq)， k = ∑t-1 i=0 ki2i with kt-1 /= 0.Output: x([k]P) ∈Fq.1 (x1，x2) ←(x(P)，xDBL([2]P);2 for i = t-2 down to 0 do 3 if ki = 0 then(x1，x2) ←(xDBL([2]P1)，xADD(P1 +P2));5 end 6 else 4(x1，x2) ←(xADD(P1 +P2)，xDBL([2]P2));8 end 9 end 10 return x1(and optionally x2 to recover [k]P from (P，x1，x2))7

3 Jacobi 四次曲線Wa，b 及其性質(zhì)

本文主要考慮具有如下參數(shù)表示的Jacobi 四次曲線Wa，b， 其定義為在點(diǎn)(0，-1) 處是正則的. 點(diǎn)(0，1) 對(duì)應(yīng)Montgomery 曲線上的無窮遠(yuǎn)點(diǎn). 同理，φ-1在點(diǎn)(0，0) 處是正則的， 因?yàn)榈葍r(jià)表示

由公式(3) 可知， 若b是一個(gè)平方元， 則Wa，b與Wa，1:y2=(a2-4)x4-2ax2+1 Fq-同構(gòu).

Jacobi 四次曲線Wa，b的j-不變量為256(a2-3)3/(a2-4). 因此，j(Wa，b)=0 當(dāng)且僅當(dāng)a2=3. 又3 是Fq中的平方元當(dāng)且僅當(dāng)q ≡1，11 (mod 12)， 因此， 若q不滿足此條件則j-不變量不為0.j(Wa，b)=1728 當(dāng)且僅當(dāng)2a3= 9a， 即a= 0 或2 = (3/a)2. 2 是Fq中的平方元當(dāng)且僅當(dāng)(-1)(q2-1)/8= 1， 即q ≡±1 (mod 8). 作為密碼學(xué)應(yīng)用， 一般要求Jacobi 四次曲線滿足j-不變量不等于0 和1728. 因此， 參數(shù)a應(yīng)滿足a2/=0，3，4，9/2.

熟知， 在有限域Fq上， 與一個(gè)給定的橢圓曲線E同構(gòu)的橢圓曲線的個(gè)數(shù)為(q-1)/|Aut(E)|[13]， 由此， 以及上面的討論可得如下引理.

引理3 給定Fq上一Jacobi 四次曲線Wa，b:y2=b2(a2-4)x4-2abx2+1. 則與它Fq-同構(gòu)的橢圓曲線的個(gè)數(shù)為

在曲線Wa，b的兩個(gè)參數(shù)a和b中，a基本上決定了曲線的幾何屬性. 假設(shè)a2/= 0，3，4，9/2. 由公式(3) 可知，Wa，b與Wa，ˉb是Fq-同構(gòu)的當(dāng)且僅當(dāng)存在u ∈F*q使得ˉb=u2b. 同理， 取ˉa=-a， 則Wa，b與W-a，ˉb是Fq-同構(gòu)的當(dāng)且僅當(dāng)存在u ∈F*q使得ˉb=-u2b.

假設(shè)a2/=0，3，4，9/2，a2/=ˉa2， 且Wa，b與Wˉa，ˉb是Fq-同構(gòu). 則由公式(3) 可得

因?yàn)閃a，b與Wˉa，ˉb同構(gòu)， 所以ˉa2/= 4. 上述關(guān)于ˉa2的二次方程在Fq中有解， 因此(a2-4)2(a2-9)2+4(a2-4)(2a2-9)2= (a2-4)a2(a2-3)2為Fq中的平方元， 知a2-4 是Fq中的平方元. 同理ˉa2-4 也是Fq中的平方元. 以上論述表明， 當(dāng)j(Wa，b)/=0，1728 且a2-4 不是Fq中的平方元時(shí)， 則不存在ˉa2/=a2的Jacobi 四次曲線Wˉa，ˉb與Wa，b同構(gòu). 這些為安全曲線選擇提供了依據(jù).

4 Jacobi 四次曲線Wa，b 上的差分加法公式

這節(jié)討論推導(dǎo)Jacobi 四次曲線Wa，b上的點(diǎn)差分公式. 對(duì)Jacobi 四次曲線Wa，b上的點(diǎn)P=(x，y)，定義它的w-坐標(biāo)為

該函數(shù)對(duì)除了二階點(diǎn)以外的所有仿射點(diǎn)都有定義. 在密碼學(xué)應(yīng)用上， 一般要求點(diǎn)的階是奇數(shù)， 所以不影響其合理性. 雙有理等價(jià)保持橢圓曲線間的點(diǎn)運(yùn)算法則， 由引理1 和Montgomery 曲線的點(diǎn)差分公式，可以得到如下定理.

定理2 設(shè)P= (xP，yP) 和Q= (xQ，yQ) 是Wa，b上的點(diǎn). 那么P，Q，P+Q和P-Q的w-坐標(biāo)滿足如下關(guān)系

由算法公式(5) 可知， 差分加法和倍乘的運(yùn)算花費(fèi)分別是3M+2S和2M+2S+1D， 所以總的混合射影w-坐標(biāo)差分公式的計(jì)算代價(jià)是5M+4S+1D.

當(dāng)域的乘法和倍乘計(jì)算的花費(fèi)滿足2M ＞3S時(shí)， 下述算法更有效， 它的混合射影w-坐標(biāo)差分公式的計(jì)算代價(jià)是3M+7S+1D.

在上面的算法中， 差分加法和倍乘的的花費(fèi)分別為3M+2S和4S+3D. 三個(gè)常數(shù)乘法中的兩個(gè)常數(shù)乘法是被α乘， 另一個(gè)是被1/α乘.

5 總結(jié)

本文提出了一般Jacobi 四次曲線上的快速差分加法公式. 在射影坐標(biāo)系統(tǒng)下， 本文提出的混合加法和倍乘運(yùn)算的總花費(fèi)只需要5M+4S+1D或者3M+6S+3D， 是目前Jacobi 四次曲線上最快的運(yùn)算公式. 相比其他模型的橢圓曲線， 這也是最具競(jìng)爭(zhēng)優(yōu)勢(shì)的記錄. 文獻(xiàn)[11] 中的差分加法公式， 使用(x2:Z2)坐標(biāo)、混合加法和倍乘運(yùn)算的總花費(fèi)為5M+4S+5D， 比較可知本文的公式更有效. 結(jié)合Montgomery算法的差分加法公式在計(jì)算點(diǎn)乘方面非常有效， 而且能有效地抵抗簡(jiǎn)單能量分析. Jacobi 四次曲線相較于其它模型的橢圓曲線有很多的優(yōu)勢(shì)， 它上面的基本點(diǎn)加和倍乘運(yùn)算非常高效， 本文構(gòu)造的快速差分加法公式進(jìn)一步增強(qiáng)了它在橢圓曲線模型選擇中的競(jìng)爭(zhēng)優(yōu)勢(shì)， 未來可進(jìn)一步探索該類型橢圓曲線的有效算法和其它性質(zhì).