黃 艷 ,張方國

1(中山大學(xué) 計(jì)算機(jī)學(xué)院,廣東 廣州 510006)

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

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

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

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

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

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

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

本文第1 節(jié)闡述橢圓曲線同源的計(jì)算公式、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é)主要描述有限域上計(jì)算橢圓曲線同源的Vélu 公式、SIDH 協(xié)議以及CSIDH 協(xié)議,并分析實(shí)現(xiàn)這兩個協(xié)議的效率影響因素.

1.1 同源和Vélu公式

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

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

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

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

1.2 SIDH協(xié)議

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

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

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

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

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

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

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

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

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

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

1.3 CSIDH

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

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

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

算法1[22].

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

輸出:曲線EA,滿足

2.返回a

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

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

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

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

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

2 SIDH 實(shí)現(xiàn)的改進(jìn)概述

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

2.1 加快有限域中的基本運(yùn)算

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

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

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

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

2.2 優(yōu)化橢圓曲線中的標(biāo)量乘計(jì)算

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

2.3 探索適合的曲線形式、坐標(biāo)形式

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

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

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

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

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

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

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

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

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

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

即可恢復(fù)同源曲線.

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

在SIDH 中需要計(jì)算兩個獨(dú)立點(diǎn)P和Q以及P-Q的同源值.而當(dāng)知道這3 個點(diǎn)的橫坐標(biāo)時,利用公式:

即可恢復(fù)同源曲線.

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

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

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

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

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

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

Fig.2 Compute ?7-isogeny圖2 計(jì)算?7-同源

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

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

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

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

代替原來的公鑰:

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

Azarderakhsh 等人[44]通過將公鑰中的點(diǎn)表示為

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

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

3 CSIDH 實(shí)現(xiàn)的改進(jìn)概述

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

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

3.2 優(yōu)化橢圓曲線中的標(biāo)量乘計(jì)算

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

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

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

Eligator 算法[51].

輸入:u∈Fp;

輸出:x∈Fp.

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

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

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

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

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

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

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

4 總結(jié)和展望

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

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

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

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

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

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