橢圓曲線同源的有效計算研究進展*

黃 艷 ,張方國

1(中山大學 計算機學院,廣東 廣州 510006)

2(廣東省信息安全技術重點實驗室,廣東 廣州 510006)

橢圓曲線同源是兩條橢圓曲線之間的一個非平凡的代數(shù)映射,它是一個群同態(tài).根據(jù)Tate 定理[1],定義在有限域Fq上的兩條橢圓曲線E1和E2同源當且僅當#E1(Fq)=#E2(Fq).然而,給定有限域上的兩條橢圓曲線E1和E2,滿足#E1(Fq)=#E2(Fq),找到E1與E2之間的同源是困難的.我們稱該問題為標準的同源計算問題.

基于橢圓曲線同源的密碼系統(tǒng)早期的研究主要集中在一般橢圓曲線(ordinary elliptic curve)上[2-4].根據(jù)Childs 等人[5]的研究結果,計算一般橢圓曲線同源的時間復雜度為量子亞指數(shù)時間;根據(jù)Biasse 等人[6]的研究結果,計算超奇異橢圓曲線(supersingular elliptic curve)同源的時間復雜度為量子指數(shù)時間.另外,Costello 等人[7]發(fā)現(xiàn):在Montgomery 曲線上,超奇異橢圓曲線同源的計算比一般橢圓曲線同源的計算效率更高.

因此,從安全性和計算效率的角度來看,對于目前具有抗量子計算攻擊的橢圓曲線同源的密碼體制的研究主要集中在超奇異橢圓曲線同源上.Jao 等人[8]提出了擴域上的基于超奇異橢圓曲線同源的密鑰交換協(xié)議(SIDH).之后,Azarderakhsh 等人[9]將基于SIDH 的加密方案和密鑰封裝協(xié)議提交到美國NIST,參與后量子密碼方案的候選,并成功進入第2 輪.然而,其實現(xiàn)的效率相比于基于糾錯碼[10,11]和基于格[12,13],均不占優(yōu)勢.Yoo 等人[14]和Galbraith 等人[15]提出了基于超奇異橢圓曲線同源的簽名方案,這兩類簽名方案均采用認證結構結合FS[16]轉換或者U 轉換[17]來加以構造,效率相比于基于格的[18,19]和基于哈希函數(shù)[20,21]的簽名方案也不占優(yōu)勢,這主要是由于橢圓曲線同源的計算效率不高所致.

目前,對于SIDH 的優(yōu)化計算主要從以下3 個角度來展開:探索適合的域的形式;借助不同曲線形式、不同坐標形式的優(yōu)勢;利用一些特殊技巧,如加法鏈、Weil 限制和雙線性對等去優(yōu)化.

以上基于橢圓曲線同源的密碼方案均是在擴域上進行的,Castryck 等人[22]提出了基域上的基于超奇異橢圓曲線同源的密鑰交換協(xié)議(CSIDH),其算法的實現(xiàn)效率相比在擴域上的SIDH 提高了很多,然而其運行時間會隨著密鑰的變化而變化,因此不能抵抗側信道攻擊.

目前,對于CSIDH 算法的優(yōu)化主要從以下3 個角度來實施:通過增加冗余,使其算法的運行時間為常數(shù)時間;借助不同曲線形式和坐標形式的優(yōu)勢;利用一些特殊技巧,如探索有效的基點生成算法、加法鏈和最優(yōu)策略等優(yōu)化計算.

本文第1 節(jié)闡述橢圓曲線同源的計算公式、SIDH 協(xié)議、CSIDH 協(xié)議以及優(yōu)化SIDH 和CSIDH 的可能性.第2 節(jié)和第3 節(jié)分別討論目前所提出的優(yōu)化SIDH 和CSIDH 的各種有效技巧.第4 節(jié)探討SIDH 和CSIDH 的其他可能優(yōu)化的問題.

1 Vélu 公式、SIDH 協(xié)議以及CSIDH 協(xié)議

本節(jié)主要描述有限域上計算橢圓曲線同源的Vélu 公式、SIDH 協(xié)議以及CSIDH 協(xié)議,并分析實現(xiàn)這兩個協(xié)議的效率影響因素.

1.1 同源和Vélu公式

根據(jù)文獻[23],兩條橢圓曲線之間的同源具有有理函數(shù)表達式.特別地,對于一個可分的同源φ,其核的階#Kerφ為同源φ的次數(shù),φ的表達式由其核唯一決定.即:給定定義在有限域Fq的橢圓曲線E上的一個子群,Vélu 給出變換如下:

其中,群G中的點在φ的作用下均映射到E＇中的單位元O.根據(jù)這一變換,可以推導出φ在Weierstrass 曲線形式下的有理函數(shù)表達式.對于其他曲線形式的Vélu 公式,也可類似地給出或利用與Weierstrass 曲線的同構進行推導.

表1 給出了目前已有的Weierstrass 曲線、Montgomery 曲線、Edwards 曲線、Huff 曲線、Hessian 曲線和Jacobian quartic 曲線上的?-同源公式和相應的同源曲線公式.假設群G的生成元為點P,其中,階為?.在Montgomery 曲線上,注意到其中,在同源計算中,可以利用這一性質簡化公式的表達形式.?-同源的像的x坐標只與原像中的x坐標和群G中的點的x坐標有關,且?-同源曲線系數(shù)也只與群G中的x坐標和原像曲線系數(shù)有關.因此,在具體實現(xiàn)時,為了避免求逆,可以只利用坐標(X:Z)(其中,x=X:Z)就能夠計算Montgomerey 曲線上的同源和同源曲線.由Edwards 曲線可以發(fā)現(xiàn),?-同源和?-同源曲線的計算公式只與坐標w和曲線系數(shù)有關,因此,在具體實現(xiàn)時,為了避免求逆,利用坐標(WE:ZE)(其中,即可完成這些計算.對于Huff 曲線和Hessian 曲線,目前只給了射影坐標(X:Y:Z)下的?-同源和?-同源曲線公式.對于其他坐標形式的優(yōu)化,還需我們作更進一步的研究.

Table 1 Vélu formulae between different curve forms表1 不同曲線形式上的Vélu 公式

Table 1 Vélu formulae between different curve forms (Continued)表1 不同曲線形式上的Vélu 公式(續(xù))

表1 中,通過比較不同曲線形式上的?-同源和?-同源曲線的計算量可知:在Montgomery 曲線和Edwards 曲線的同源計算量相同,且均比在Huff 曲線、Hessian 曲線和Jacobi quartic 曲線的計算更具優(yōu)勢.對于同源曲線的計算,在Edwards 曲線上比在Montgomery 曲線、Huff 曲線、Hessian 曲線和Jacobi quartic 曲線上的計算都更有優(yōu)勢.

1.2 SIDH協(xié)議

Jao 等人[9]首次提出了基于超奇異橢圓曲線同源的密鑰交換協(xié)議.該協(xié)議的具體描述如下.

假設Alice 和Bob 想進行密鑰交換獲得一個共同的密鑰,首先,Alice 和Bob 分別產生階為的獨立點{PA,QA}和階為的獨立點{PB,QB}.Alice 選擇計算在核〈PA+mAQA〉下的同源φA:E0→EA以及點PB和QB的同源值φA(PB)和φA(QB),將φA(PB)、φA(QB)、EA發(fā)送給Bob.同時,Bob 進行類似的操作,計算在核〈PB+mBQB〉下的同源φB:E0→EB以及點PA和QA的同源值φB(PA)和φB(QA),將φB(PA)、φB(QA)、EB發(fā)送給Alice.

在密鑰確立階段,Alice 計算在核〈φB(PA)+mAφB(QA)〉下的同源φA＇:EB→EAB,獲得曲線EAB.Bob 進行類似的操作,計算在核〈φA(PB)+mBφA(QB)〉下的同源φB＇:EA→EBA,獲得曲線EAB.最后,Alice 和Bob 獲得共同的j不變量,即j(EAB)=j(EBA).協(xié)議過程如圖1 所示.定義A和B為Alice 和Bob 的標識,sID 為唯一的會話標識.

Fig.1 Key-exchange protocol based on supersingular elliptic curve isogeny圖1 基于超奇異橢圓曲線同源的密鑰交換協(xié)議

通過對上述協(xié)議的描述,我們分析影響SIDH 有效實現(xiàn)的因素主要有:

(1) 有限域的類型以及基本代數(shù)運算.在保證安全度的前提下,可以選擇在基域Fp或者在擴域中實現(xiàn).一般來說,盡可能多地選擇在基域中進行優(yōu)化計算.另外,任何加速底層的有限域的基本算術方法都能加快SIDH 的實現(xiàn);

(2) 橢圓曲線中標量乘的計算.注意到:在SIDH 中,Alice 和Bob 在初始階段生成同源的核生成點時都需要進行標量乘的計算.同時,在同源的復合計算過程中,也涉及到核生成點的計算,因此也用到了標量乘的計算.從而,有效的標量乘計算可加速SIDH 的計算;

(3) 曲線以及坐標的類型.不同的曲線模型以及相應的不同坐標形式,其上的點加、倍點、同源和同源曲線的代數(shù)操作的計算量是不同的,因此,選擇一條合適的曲線形式和坐標形式,使其具備有效的代數(shù)操作,將能夠在很大程度上加快SIDH 的有效實現(xiàn);

(4) 同源和同源曲線的計算.在SIDH 中,Alice 和Bob 均需要計算?e-同源和同源曲線.對于?e-同源的計算,需要進行e次?-同源的復合.顯然,復合次數(shù)越少,計算速度越快.對于同源曲線的計算,當?較大時,直接利用同源曲線公式計算,效率較低.因此,探索有效的?e-同源和同源曲線的計算也會促進SIDH 的有效實現(xiàn);

(5) 壓縮公鑰和恢復公鑰的計算量.Alice 和Bob 在利用SIDH 進行通信時,彼此傳遞的信息有同源曲線和兩個獨立點的同源值,需要12log2p的通信量.而這些通信量可以通過一些壓縮算法更進一步地加以減少,從而降低公鑰的尺寸規(guī)模.同時,其壓縮算法和解壓算法的效率也會在一定程度上影響到SIDH的有效實現(xiàn).

1.3 CSIDH

Castryck 等人[22]提出了定義在基域Fp上的可交換的密鑰交換協(xié)議CSIDH,其具體過程如下.

令p=4?1?2…?n-1 為一個素數(shù),其中,?i(i=1,…,74)為各自不同的素數(shù).E為定義在Fp上的具有自同態(tài)環(huán)O的超奇異橢圓曲線,其中,O為一個虛二次域的Order,π∈O為一個Frobenius 自同態(tài)映射,E??p(O,π)為定義在Fp上滿足當π對應于曲線的Fp-Frobenius 時具有與O同構的自同態(tài)環(huán)的曲線的集合.任何一個類群cl(O)中的元素[a]通過同源作用在E??p(O,π)中的曲線E,即[a]E.假設Alice 和Bob 想交換一個密鑰:在密鑰生成段,Alice 選擇一個理想類[a],計算EA=[a]E,將EA發(fā)給Bob.Bob 選擇一個理想類[b],計算EB=[b]E,將EB發(fā)給Alice;在密鑰確立階段,一旦收到對方的公鑰,Alice 計算[a]EB,Bob 計算[b]EA.由于類群具有可交換的性質,因此Alice 和Bob 均可以計算共享的密鑰,即[a][b]E=[a]EB=[b]EA.

對于CSIDH 的實現(xiàn),主要是計算[a]E的過程,如下面算法1 所示.

算法1[22].

輸入:超奇異橢圓曲線E0和理想類,其中,ei∈{-5,…,5};

輸出:曲線EA,滿足

2.返回a

對于CSIDH 的優(yōu)化,主要考慮算法1 的優(yōu)化,有以下幾種可能.

(1) 基點P的選取.算法1 中,點P的選取與密鑰的正負有直接的聯(lián)系:當密鑰均為正時,隨機選取的點均在Fp上;當密鑰均為負時,隨機選取的點均在上.隨機選取不能保證每次都成功選到合法的點,從而在一定程度上影響到算法的實現(xiàn)效率.因此,設計有效的基點生成算法,將在一定程度上優(yōu)化算法1的實現(xiàn);

(2) 標量乘的計算.在算法1 的步驟1.4 和步驟1.5.1,需要進行標量乘計算,而這些標量乘的計算都形如?1?2…?nP,其中,?1,?2,…,?n均為不同的素數(shù),對于這種形式的標量乘的優(yōu)化,也將能夠提高算法1 的實現(xiàn)效率;

(3) 同源的計算和同源曲線的計算.對于算法1 中計算的同源是一些不同素數(shù)次的同源的復合,對于這樣的同源是否有類似于SIDH 的最優(yōu)策略,也是值得研究的一個方面.另外,考慮到CSIDH 中需要計算的同源的次數(shù)相對于SIDH 中的次數(shù)均要大(針對素數(shù)次同源),計算效率也比較低,對這類同源的優(yōu)化也將在很大程度上促進CSIDH 的優(yōu)化.對于同源曲線的計算,注意到算法1 中并沒有類似SIDH 中需要計算的同源點來恢復同源曲線,因此,對同源曲線公式的優(yōu)化也是優(yōu)化算法1 的一個方面;

(4) 常數(shù)時間的算法.注意到:算法1 需要計算的同源的個數(shù)依賴于密鑰,不能抵抗側信道攻擊.因此,如何設計一個有效的常數(shù)時間的算法來計算[a]E,也是目前研究的一個熱點問題.

2 SIDH 實現(xiàn)的改進概述

SIDH 目前的實現(xiàn)主要是在Montgomery 曲線上坐標(XM:ZM)來實現(xiàn)的,可參見文獻[7,24].下面將從不同理論角度來綜述目前已發(fā)現(xiàn)的SIDH 實現(xiàn)的改進技巧.

2.1 加快有限域中的基本運算

對于優(yōu)化有限域中的基本運算,目前的研究主要包括3 個方面:優(yōu)化有限域中的基本代數(shù)運算、減少有限域的尺寸、將擴域中的基本代數(shù)運算轉化到基域中進行計算.

對于第1 個方面,Koziel 等人[25]借助加法鏈的方法,優(yōu)化有限域中的平方根和求逆運算.Joppe 等人[26]通過探索有限域特征的特殊素數(shù)形式p=2xf y-1(其中,f為素數(shù)),利用Montgomery 歸約算法提高有限域中模運算的速度,從而提高基本的模加、模減、模乘和模逆運算.Seo 等人[27]在64 比特的ARM 上對有限域中的模加、模減和模乘都進行了優(yōu)化.Costello 等人[28]考慮在進行密鑰交換協(xié)議時,若一方的計算速度比較快,則設定有限域的特征為p=2ef-1,或者p=2n-2m-1,或者滿足p+1 和p-1 含有小素因子的素數(shù)p,且這些小素因子的乘積到達相應的安全級別,進而利用p+1 階扭點和p-1 階扭點,加快SIDH 中Alice 的實現(xiàn)速度;

對于第2 個方面,Flynn 等人[29]利用在同等安全級別下虧格為2 的基于橢圓曲線同源的密鑰交換協(xié)議要求的有限域的特征p的尺寸比在虧格為1 的有限域的特征p要小的優(yōu)勢,提出了在虧格為2 的擴域上實現(xiàn)超橢圓曲線同源的密鑰交換協(xié)議;

對于第3 個方面,Costello 等人[30]借助在同樣的特征下,基域Fp中的模代數(shù)運算比在擴域中要快,即:

2.2 優(yōu)化橢圓曲線中的標量乘計算

SIDH 中涉及到的標量乘主要的形式包括P+kQ和?R,其中,P、Q、R均為橢圓曲線上的點,k、?均為正整數(shù).對于P+kQ的計算,主要是利用Ladder 算法[9]進行優(yōu)化計算.Faz-Hernendez 等人[31]給出了一種左右Ladder 算法,并借助預計算的技巧進行了更進一步的優(yōu)化.對于?R的計算,目前的方法主要是利用加法鏈進行優(yōu)化計算[29].

2.3 探索適合的曲線形式、坐標形式

在不同的曲線模型上,利用不同坐標形式計算點加、倍點、同源以及同源曲線的計算量是不同的.探索一個最適合的曲線模型以及相應的坐標形式,使其在上面這些計算的耗費量最小,也是一種非常重要的優(yōu)化SIDH實現(xiàn)的方式.Montgomery 等人[32]最早提出了在Montgomery 曲線上僅利用坐標(XM:ZM)就可以進行倍點和標量乘的計算.De Feo 等人[33]給出了在Montgomery 曲線上坐標(XM:ZM)的3-同源和4-同源公式.利用這些基本運算,Costello 等人[6]在Montgomery 曲線上優(yōu)化了SIDH 的實現(xiàn).另外,Costello 等人[24]又利用計算同源和同源曲線之間共用的3 階點、4 階點繼續(xù)對3 倍點、3-同源和4-同源以及相應的同源曲線進行優(yōu)化.Renes 等人[34]給出了核生成點不在(0,0)的2-同源公式,通過1 次復合該2-同源公式,則很容易得到核生成點不在的4-同源公式,其中,a,b為Montgomery 曲線的系數(shù).與DeFeo 等人[33]的方法相比較,該方法避開了求根號以及額外8階扭點的計算.

注意到,Edwards 曲線與Montgomery 曲線之間存在著雙有理關系[35]:

即,Edwards 曲線上的坐標yE完全可以利用Montgomery 曲線上的坐標xM表示.Kim 等人[36]利用該雙有理關系推導出在Edwards 曲線坐標(YE:ZE)下的4-同源以及4-同源曲線公式,并發(fā)現(xiàn):在該坐標下實現(xiàn)SIDH 的效率比在Montgomery 曲線坐標(XM:ZM)下實現(xiàn) SIDH 的效率要稍微高一點.除了在坐標(YE:ZE)下可以優(yōu)化計算外,Farashahi 等人[37]也探索了新的Edwards 曲線上坐標(WE:ZE)對應的倍點和點加公式,發(fā)現(xiàn)其計算量與在坐標(YE:ZE)下相同.另外,Kim 等人[38]研究了在坐標(WE:ZE)下的奇數(shù)次同源公式和相應的同源曲線公式,其同源公式的計算量與在Montgomery 曲線上的計算量也是相同的,同源曲線的計算量相比于在Montgomery 曲線上要有優(yōu)勢.然而,對于偶數(shù)次同源在Edwards 曲線坐標(WE:ZE)上的公式,目前還沒有被提出.

除了以上對于Montgomery 曲線和Edwards 曲線的不同坐標形式的同源和同源曲線公式的研究,Moody 等人[39]還給出了Huff 曲線下的同源和同源曲線公式,Dang 等人[40]給出了Hessian 曲線下的奇數(shù)次同源和同源曲線公式,Xu 等人[41]給出了Jacobi quartic 曲線下的同源和同源曲線公式.然而,對于在這幾種曲線上的點加、倍點以及同源的計算與在Montgomery 和Edwards 曲線的相應的計算相比,計算的耗費量差異較大,相應的優(yōu)化還沒有給出.此外,對于其他曲線形式,如對Jacobi intersections[42]的同源的研究也沒有給出.

2.4 優(yōu)化同源曲線的計算公式

注意到,同源曲線的優(yōu)化計算也可以加快SIDH 的實現(xiàn),因此,Costello 等人[24]提出了3 種不同的方法來計算奇數(shù)次同源曲線,分別是:

(1) 利用奇數(shù)次同源曲線公式來恢復曲線系數(shù).

在SIDH 中,Alice 和Bob 最終共享的密鑰是橢圓曲線的j不變量,當曲線為Montgomery 曲線(by2=x3+ax2+x)時,其j不變量為只與系數(shù)a有關,系數(shù)b不參與計算.因此,實現(xiàn)SIDH 過程中也只需考慮利用表1 的公式計算同源曲線的系數(shù)a.

(2) 利用額外的2 階扭點的同源值來恢復曲線系數(shù).

在Montgomery 曲線上,當給定初始曲線時,即by2=x3+ax2+x,其二階扭點很容易獲得.即令x3+ax2+x=0,利用韋達定理可得兩個根,分別為x1和x2,從而有二階扭點分別為(0,0)、(x1,0)和(x2,0),計算(x1,0)或者(x2,0)在任意奇數(shù)次同源φ的值依然為2 階扭點,即(φ(x1),0)或者(φ(x2),0),通過這兩個同源值,反過來由公式:

即可恢復同源曲線.

(3) 利用固定的3 個點的同源值恢復曲線系數(shù).

在SIDH 中需要計算兩個獨立點P和Q以及P-Q的同源值.而當知道這3 個點的橫坐標時,利用公式:

即可恢復同源曲線.

方法(1)、方法(2)的優(yōu)點是適合計算小次數(shù)同源曲線,缺點是會隨著同源次數(shù)的增加而增加計算量.方法(3)適合計算較大次數(shù)的同源曲線,并且計算量是固定的,均為8M+5S,前提是要有額外的同源點.

表2 給出了利用以上3 種方法分別計算3-同源曲線和19-同源曲線的計算量.計算3-同源曲線,利用方法(1)的計算量最小;計算19-同源曲線,利用方法(3)的計算量最小.

Table 2 Compute 3-isogeny curve and 19-isogeny curve表2 計算3-同源曲線和19-同源曲線

2.5 減少?e-同源的循環(huán)次數(shù)

對于?e-同源的計算,主要是將其分解為e個?-同源的復合.De Feo 等人[33]提出了3 種方法,分別是基于同源的方法、基于標量乘的方法和最優(yōu)策略算法.其中,基于同源的方法是在復合過程用計算同源的方式去計算每次同源的核生成點;而基于標量乘的方法是在復合過程中用基于標量乘的方式計算每次同源的核生成點;最優(yōu)策略算法是結合前兩種方法的優(yōu)勢提出的一種新的方法,通過比較每次復合中標量乘計算和同源計算的耗費量,并結合最優(yōu)策略的性質,即一個策略是最優(yōu)的當且僅當其分解為兩個最優(yōu)子策略,得到最優(yōu)路徑,利用該路徑來計算每次同源的核生點.3 種方法相比較而言,第3 種方法的計算效率是最優(yōu)的.

圖2 給出了分別用基于標量乘的方法、基于同源的方法和最優(yōu)策略計算?7-的同源.假設計算?-同源的計算量為q,計算標量乘[?]R(其中,R為橢圓曲線上任意一個點)的計算量為p,那么利用基于標量乘的方法需要的計算量為21p+6q,利用基于同源的方法的計算量為21q+6p,利用最優(yōu)策略的方法的計算量為11p+9q.顯然,最優(yōu)策略所需要的計算量最小,是最優(yōu)的.

Fig.2 Compute ?7-isogeny圖2 計算?7-同源

Hutchinson 等人[43]利用并行處理的方法對基于最優(yōu)策略算法進行了更進一步的優(yōu)化.如圖2 所示,在計算同源φ0、φ1、φ3時,可以利用并行處理的方法進行計算.

2.6 減少公鑰的尺寸,優(yōu)化壓縮公鑰的算法

對于基于超奇異橢圓曲線密鑰交換協(xié)議的公鑰尺寸的壓縮,主要有兩種方法:(1) 通過減少公鑰的參數(shù)縮小公鑰的規(guī)模;(2) 通過將公鑰的點表示為基點的線性組合,將相應的坐標代替點達到壓縮公鑰的目的.此外,對于其壓縮算法的效率也是目前研究的一個熱點.

Costello 等人[24]利用Montgomery 曲線下的坐標(XM:ZM)實現(xiàn)SIDH,用3 個點的橫坐標:

代替原來的公鑰:

其中,曲線系數(shù)的計算可以利用第2.4 節(jié)中的方法(3),從而將公鑰尺寸由原來的12log2p降低到6log2p.

Azarderakhsh 等人[44]通過將公鑰中的點表示為

求解離散對數(shù)得到a0、a1、b0、b1,從而將公鑰變?yōu)?EB,a0,a1,b0,b1),將其尺寸減少到4log2p.然而,壓縮公鑰的算法由于需要雙線性對和離散對數(shù)的計算,比以前的計算耗費量要大.Costello 等人[45]構造了n階基點生成算法,優(yōu)化Tate 對計算以及Pohlig-Hellman 算法,將公鑰中表示點的線性組合的系數(shù)由原來的4 個減少到3 個,增加1 額外比特信息,從而將尺寸減少到同時,將壓縮公鑰的計算效率提高了2.4 倍.具體如下.

由于PB和QB是公開參數(shù),h0可以預計算,相比于Costello 等人的算法減少了一個雙線性對的計算.Naehrig等人[47]利用2-同源的對偶同源比2-同源計算(核生成點非(0,0))要快的性質,將SIKE 中密鑰生成階段的開銷由原來的140%～153%減少到61%～74%,將密鑰封裝由原來的67%～90%減少到38%～57%,將解封裝由原來的59%～65%減少到34%～38%.

3 CSIDH 實現(xiàn)的改進概述

根據(jù)前面對于CSIDH 協(xié)議以及算法1 的描述,優(yōu)化CSIDH 的實現(xiàn)關鍵在于提高算法1 的效率,這一節(jié)主要總結對于算法1 的各種優(yōu)化方法.

3.1 設計常數(shù)時間的算法

3.2 優(yōu)化橢圓曲線中的標量乘計算

Meyer 等人[51]通過調整算法1 中初始點的計算,計算P=4P0,α=?1?2…?n,其中,?1＞?2＞…＞?n.將作為第1 個次數(shù)為?1同源的核生成點,并在具體的迭代計算中優(yōu)先計算次數(shù)較大的同源,再計算次數(shù)較小的同源,減少標量乘的計算,從而使得算法1 的實現(xiàn)效率比之前提高了1.096 倍.之后,Meyer 等人將密鑰空間的指標集合化分為多個集合,從而將同源的計算分解為多個分支,在很大程度上減少了每次循環(huán)需要的標量乘計算.

3.3 優(yōu)化基點P的生成算法

當密鑰的每個分量均變?yōu)檎龝r,隨機點的選取只需考慮定義在Fp上的點.Meyer 等人[51]首次利用Eligator算法快速生成定義在Fp上的點P的橫坐標x.給定曲線y2=x3+ax2+x,其中,a∈Fp,該算法對于步驟(2)中的可以采取預先計算的方式,避免了求逆,比隨機選取點的算法效率要高.

Eligator 算法[51].

輸入:u∈Fp;

輸出:x∈Fp.

當密鑰的每個分量有正有負時,Onuki 等人[49]利用Eligator 算法快速生成兩個合法點,分別是定義在Fp上的點和定義在上的點.

3.4 優(yōu)化同源的計算

考慮到CSIDH 中同源的次數(shù)相對于SIDH 中同源的次數(shù)較大,Bernstein 等人[52]利用Strassen 算法進行優(yōu)化,將?-同源的計算由原來的O(?)降為

3.5 優(yōu)化同源曲線的計算

注意到,CSIDH 中同源曲線的計算與在SIDH 中的計算方式是不同的:在SIDH 中,需要計算額外點的同源值,同源曲線的計算剛好可以利用這些點的同源值,避免了因同源次數(shù)增加而相應的同源曲線的計算量增加所帶來的不便;在CSIDH 中,不需要額外點的計算,同源曲線的計算只能利用推導的公式本身去優(yōu)化計算.由于利用Montgomery 曲線形式計算同源曲線的效率不是很高[24],Meyer 等人[48]借助Montgomery 曲線與扭Edwards曲線之間雙有理等價關系,利用扭Edwards 曲線上的同源曲線公式來優(yōu)化計算.即:在Montgomery 曲線上,坐標(XM:ZM)可以通過變換:

轉化到扭Edwards 曲線射影坐標(YE:ZE).同時,Montgomery 曲線系數(shù)(A:C)可以通過變換a=A+2C和d=A-2C轉化到扭Edwards 曲線參數(shù)(a,d).在扭Edwards 曲線上,利用公式:

可以計算扭Edwards 曲線上的?-同源曲線參數(shù)(a＇,d＇),其中,?-同源的核為〈P〉={[iP]:i=0,…,?=2s+1}.通過變換(A＇:C＇)=(2(a＇+d＇):a＇-d＇),可以得到Montgomery 曲線上的?-同源曲線.Kim 等人[38]借助奇數(shù)階點在2 倍標量乘的作用下不改變其階這一性質,優(yōu)化Ewards 曲線上在新坐標(WE:ZE)下的同源曲線公式,如表1 所示.

4 總結和展望

自橢圓曲線同源在公鑰密碼學中得到廣泛應用,其對應的公鑰加密和密鑰封裝進入美國NIST 標準第2 輪,對于SIDH 和CSIDH 的有效計算引起了學者們的重視,正如上面所分析的,取得了很多突破性的進展.但是,這一領域還有許多問題亟待解決.

(1) 借助不同曲線模型,探索不同坐標形式以及在該坐標下的倍點、點加、同源和同源曲線的計算公式,利用這些優(yōu)化的公式來優(yōu)化SIDH 和CSIDH 的實現(xiàn).目前比較主流的實現(xiàn)SIDH 和CISDH 均在Montgomery 和Edwards 曲線上,對于其他曲線,如Huff 曲線、Hessian 曲線、Legendre 曲線和Jacobian Intersections 等的研究還比較少.是否最優(yōu)的實現(xiàn)就是在Montgomery 曲線或者Edwards 曲線,亦或者有更好的曲線代替這兩種曲線去實現(xiàn)SIDH 和CISDH,是值得關注的問題;

(2) 對于優(yōu)化SIDH,除了考慮以上的方法外,還可以利用超橢圓曲線的優(yōu)勢去優(yōu)化計算.注意到利用虧格為2 的Kummer 面實現(xiàn)SIDH,其域的尺寸在同等安全級別下比虧格為1 的Kummer 線上實現(xiàn)SIDH要小,其上的(2,2)-同源也有快速計算公式,然而,其(3,3)-同源的計算比較復雜,需要我們進一步加以深入研究;

(5) 對于公鑰尺寸的有效壓縮,也是目前研究的一個熱點.基于Kummer 線上的SIDH 的加密和密鑰封裝的公鑰壓縮,已有很多工作.然而,對于階為3e點的有效壓縮算法,依然是一個亟待解決的問題.此外,利用Kummer 面上SIDH 設計的加密方案,其上的公鑰尺寸還比較大.能否縮短公鑰的尺寸,如將公鑰中的點表示為固定基點的線性組合?這些問題均是值得我們后續(xù)研究的;

(6) 對于CSIDH 的優(yōu)化,設計一個常數(shù)時間且有效的算法實現(xiàn)[a]E的計算,依然是目前研究的一個熱點.目前設計的算法,實現(xiàn)的效率還比較低.能否借助一些特性,如基域上的?-同源只有兩種情況,減少同源的計算,或者構造更加有效的基點生成算法等,對其進行更進一步的優(yōu)化?都是值得研究的;

(7) 借助其他優(yōu)化標量乘或者雙線性對[53]的技術,如借助多維標量乘[54]、橢圓網(wǎng)[55]等技術優(yōu)化SIDH 或者CSIDH 的方式,也值得更進一步地加以研究.