黄 艳 ,张方国

1(中山大学 计算机学院,广东 广州 510006)

2(广东省信息安全技术重点实验室,广东 广州 510006)

椭圆曲线同源是两条椭圆曲线之间的一个非平凡的代数映射,它是一个群同态.根据Tate 定理[1],定义在有限域Fq上的两条椭圆曲线E1和E2同源当且仅当#E1(Fq)=#E2(Fq).然而,给定有限域上的两条椭圆曲线E1和E2,满足#E1(Fq)=#E2(Fq),找到E1与E2之间的同源是困难的.我们称该问题为标准的同源计算问题.

基于椭圆曲线同源的密码系统早期的研究主要集中在一般椭圆曲线(ordinary elliptic curve)上[2-4].根据Childs 等人[5]的研究结果,计算一般椭圆曲线同源的时间复杂度为量子亚指数时间;根据Biasse 等人[6]的研究结果,计算超奇异椭圆曲线(supersingular elliptic curve)同源的时间复杂度为量子指数时间.另外,Costello 等人[7]发现:在Montgomery 曲线上,超奇异椭圆曲线同源的计算比一般椭圆曲线同源的计算效率更高.

因此,从安全性和计算效率的角度来看,对于目前具有抗量子计算攻击的椭圆曲线同源的密码体制的研究主要集中在超奇异椭圆曲线同源上.Jao 等人[8]提出了扩域上的基于超奇异椭圆曲线同源的密钥交换协议(SIDH).之后,Azarderakhsh 等人[9]将基于SIDH 的加密方案和密钥封装协议提交到美国NIST,参与后量子密码方案的候选,并成功进入第2 轮.然而,其实现的效率相比于基于纠错码[10,11]和基于格[12,13],均不占优势.Yoo 等人[14]和Galbraith 等人[15]提出了基于超奇异椭圆曲线同源的签名方案,这两类签名方案均采用认证结构结合FS[16]转换或者U 转换[17]来加以构造,效率相比于基于格的[18,19]和基于哈希函数[20,21]的签名方案也不占优势,这主要是由于椭圆曲线同源的计算效率不高所致.

目前,对于SIDH 的优化计算主要从以下3 个角度来展开:探索适合的域的形式;借助不同曲线形式、不同坐标形式的优势;利用一些特殊技巧,如加法链、Weil 限制和双线性对等去优化.

以上基于椭圆曲线同源的密码方案均是在扩域上进行的,Castryck 等人[22]提出了基域上的基于超奇异椭圆曲线同源的密钥交换协议(CSIDH),其算法的实现效率相比在扩域上的SIDH 提高了很多,然而其运行时间会随着密钥的变化而变化,因此不能抵抗侧信道攻击.

目前,对于CSIDH 算法的优化主要从以下3 个角度来实施:通过增加冗余,使其算法的运行时间为常数时间;借助不同曲线形式和坐标形式的优势;利用一些特殊技巧,如探索有效的基点生成算法、加法链和最优策略等优化计算.

本文第1 节阐述椭圆曲线同源的计算公式、SIDH 协议、CSIDH 协议以及优化SIDH 和CSIDH 的可能性.第2 节和第3 节分别讨论目前所提出的优化SIDH 和CSIDH 的各种有效技巧.第4 节探讨SIDH 和CSIDH 的其他可能优化的问题.

本节主要描述有限域上计算椭圆曲线同源的Vélu 公式、SIDH 协议以及CSIDH 协议,并分析实现这两个协议的效率影响因素.

1.1 同源和Vélu公式

根据文献[23],两条椭圆曲线之间的同源具有有理函数表达式.特别地,对于一个可分的同源φ,其核的阶#Kerφ为同源φ的次数,φ的表达式由其核唯一决定.即:给定定义在有限域Fq的椭圆曲线E上的一个子群,Vélu 给出变换如下:

其中,群G中的点在φ的作用下均映射到E＇中的单位元O.根据这一变换,可以推导出φ在Weierstrass 曲线形式下的有理函数表达式.对于其他曲线形式的Vélu 公式,也可类似地给出或利用与Weierstrass 曲线的同构进行推导.

表1 给出了目前已有的Weierstrass 曲线、Montgomery 曲线、Edwards 曲线、Huff 曲线、Hessian 曲线和Jacobian quartic 曲线上的ℓ-同源公式和相应的同源曲线公式.假设群G的生成元为点P,其中,阶为ℓ.在Montgomery 曲线上,注意到其中,在同源计算中,可以利用这一性质简化公式的表达形式.ℓ-同源的像的x坐标只与原像中的x坐标和群G中的点的x坐标有关,且ℓ-同源曲线系数也只与群G中的x坐标和原像曲线系数有关.因此,在具体实现时,为了避免求逆,可以只利用坐标(X:Z)(其中,x=X:Z)就能够计算Montgomerey 曲线上的同源和同源曲线.由Edwards 曲线可以发现,ℓ-同源和ℓ-同源曲线的计算公式只与坐标w和曲线系数有关,因此,在具体实现时,为了避免求逆,利用坐标(WE:ZE)(其中,即可完成这些计算.对于Huff 曲线和Hessian 曲线,目前只给了射影坐标(X:Y:Z)下的ℓ-同源和ℓ-同源曲线公式.对于其他坐标形式的优化,还需我们作更进一步的研究.

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 公式(续)

表1 中,通过比较不同曲线形式上的ℓ-同源和ℓ-同源曲线的计算量可知:在Montgomery 曲线和Edwards 曲线的同源计算量相同,且均比在Huff 曲线、Hessian 曲线和Jacobi quartic 曲线的计算更具优势.对于同源曲线的计算,在Edwards 曲线上比在Montgomery 曲线、Huff 曲线、Hessian 曲线和Jacobi quartic 曲线上的计算都更有优势.

1.2 SIDH协议

Jao 等人[9]首次提出了基于超奇异椭圆曲线同源的密钥交换协议.该协议的具体描述如下.

假设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发送给Bob.同时,Bob 进行类似的操作,计算在核〈PB+mBQB〉下的同源φB:E0→EB以及点PA和QA的同源值φB(PA)和φB(QA),将φB(PA)、φB(QA)、EB发送给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).协议过程如图1 所示.定义A和B为Alice 和Bob 的标识,sID 为唯一的会话标识.

Fig.1 Key-exchange protocol based on supersingular elliptic curve isogeny图1 基于超奇异椭圆曲线同源的密钥交换协议

通过对上述协议的描述,我们分析影响SIDH 有效实现的因素主要有:

(1) 有限域的类型以及基本代数运算.在保证安全度的前提下,可以选择在基域Fp或者在扩域中实现.一般来说,尽可能多地选择在基域中进行优化计算.另外,任何加速底层的有限域的基本算术方法都能加快SIDH 的实现;

(2) 椭圆曲线中标量乘的计算.注意到:在SIDH 中,Alice 和Bob 在初始阶段生成同源的核生成点时都需要进行标量乘的计算.同时,在同源的复合计算过程中,也涉及到核生成点的计算,因此也用到了标量乘的计算.从而,有效的标量乘计算可加速SIDH 的计算;

(3) 曲线以及坐标的类型.不同的曲线模型以及相应的不同坐标形式,其上的点加、倍点、同源和同源曲线的代数操作的计算量是不同的,因此,选择一条合适的曲线形式和坐标形式,使其具备有效的代数操作,将能够在很大程度上加快SIDH 的有效实现;

(4) 同源和同源曲线的计算.在SIDH 中,Alice 和Bob 均需要计算ℓe-同源和同源曲线.对于ℓe-同源的计算,需要进行e次ℓ-同源的复合.显然,复合次数越少,计算速度越快.对于同源曲线的计算,当ℓ较大时,直接利用同源曲线公式计算,效率较低.因此,探索有效的ℓe-同源和同源曲线的计算也会促进SIDH 的有效实现;

(5) 压缩公钥和恢复公钥的计算量.Alice 和Bob 在利用SIDH 进行通信时,彼此传递的信息有同源曲线和两个独立点的同源值,需要12log2p的通信量.而这些通信量可以通过一些压缩算法更进一步地加以减少,从而降低公钥的尺寸规模.同时,其压缩算法和解压算法的效率也会在一定程度上影响到SIDH的有效实现.

1.3 CSIDH

Castryck 等人[22]提出了定义在基域Fp上的可交换的密钥交换协议CSIDH,其具体过程如下.

令p=4ℓ1ℓ2…ℓn-1 为一个素数,其中,ℓi(i=1,…,74)为各自不同的素数.E为定义在Fp上的具有自同态环O的超奇异椭圆曲线,其中,O为一个虚二次域的Order,π∈O为一个Frobenius 自同态映射,Eℓℓp(O,π)为定义在Fp上满足当π对应于曲线的Fp-Frobenius 时具有与O同构的自同态环的曲线的集合.任何一个类群cl(O)中的元素[a]通过同源作用在Eℓℓp(O,π)中的曲线E,即[a]E.假设Alice 和Bob 想交换一个密钥:在密钥生成段,Alice 选择一个理想类[a],计算EA=[a]E,将EA发给Bob.Bob 选择一个理想类[b],计算EB=[b]E,将EB发给Alice;在密钥确立阶段,一旦收到对方的公钥,Alice 计算[a]EB,Bob 计算[b]EA.由于类群具有可交换的性质,因此Alice 和Bob 均可以计算共享的密钥,即[a][b]E=[a]EB=[b]EA.

对于CSIDH 的实现,主要是计算[a]E的过程,如下面算法1 所示.

算法1[22].

输入:超奇异椭圆曲线E0和理想类,其中,ei∈{-5,…,5};

输出:曲线EA,满足

2.返回a

对于CSIDH 的优化,主要考虑算法1 的优化,有以下几种可能.

(1) 基点P的选取.算法1 中,点P的选取与密钥的正负有直接的联系:当密钥均为正时,随机选取的点均在Fp上;当密钥均为负时,随机选取的点均在上.随机选取不能保证每次都成功选到合法的点,从而在一定程度上影响到算法的实现效率.因此,设计有效的基点生成算法,将在一定程度上优化算法1的实现;

(2) 标量乘的计算.在算法1 的步骤1.4 和步骤1.5.1,需要进行标量乘计算,而这些标量乘的计算都形如ℓ1ℓ2…ℓnP,其中,ℓ1,ℓ2,…,ℓn均为不同的素数,对于这种形式的标量乘的优化,也将能够提高算法1 的实现效率;

(3) 同源的计算和同源曲线的计算.对于算法1 中计算的同源是一些不同素数次的同源的复合,对于这样的同源是否有类似于SIDH 的最优策略,也是值得研究的一个方面.另外,考虑到CSIDH 中需要计算的同源的次数相对于SIDH 中的次数均要大(针对素数次同源),计算效率也比较低,对这类同源的优化也将在很大程度上促进CSIDH 的优化.对于同源曲线的计算,注意到算法1 中并没有类似SIDH 中需要计算的同源点来恢复同源曲线,因此,对同源曲线公式的优化也是优化算法1 的一个方面;

(4) 常数时间的算法.注意到:算法1 需要计算的同源的个数依赖于密钥,不能抵抗侧信道攻击.因此,如何设计一个有效的常数时间的算法来计算[a]E,也是目前研究的一个热点问题.

SIDH 目前的实现主要是在Montgomery 曲线上坐标(XM:ZM)来实现的,可参见文献[7,24].下面将从不同理论角度来综述目前已发现的SIDH 实现的改进技巧.

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

对于优化有限域中的基本运算,目前的研究主要包括3 个方面:优化有限域中的基本代数运算、减少有限域的尺寸、将扩域中的基本代数运算转化到基域中进行计算.

对于第1 个方面,Koziel 等人[25]借助加法链的方法,优化有限域中的平方根和求逆运算.Joppe 等人[26]通过探索有限域特征的特殊素数形式p=2xf y-1(其中,f为素数),利用Montgomery 归约算法提高有限域中模运算的速度,从而提高基本的模加、模减、模乘和模逆运算.Seo 等人[27]在64 比特的ARM 上对有限域中的模加、模减和模乘都进行了优化.Costello 等人[28]考虑在进行密钥交换协议时,若一方的计算速度比较快,则设定有限域的特征为p=2ef-1,或者p=2n-2m-1,或者满足p+1 和p-1 含有小素因子的素数p,且这些小素因子的乘积到达相应的安全级别,进而利用p+1 阶扭点和p-1 阶扭点,加快SIDH 中Alice 的实现速度;

对于第2 个方面,Flynn 等人[29]利用在同等安全级别下亏格为2 的基于椭圆曲线同源的密钥交换协议要求的有限域的特征p的尺寸比在亏格为1 的有限域的特征p要小的优势,提出了在亏格为2 的扩域上实现超椭圆曲线同源的密钥交换协议;

对于第3 个方面,Costello 等人[30]借助在同样的特征下,基域Fp中的模代数运算比在扩域中要快,即:

2.2 优化椭圆曲线中的标量乘计算

SIDH 中涉及到的标量乘主要的形式包括P+kQ和ℓR,其中,P、Q、R均为椭圆曲线上的点,k、ℓ均为正整数.对于P+kQ的计算,主要是利用Ladder 算法[9]进行优化计算.Faz-Hernendez 等人[31]给出了一种左右Ladder 算法,并借助预计算的技巧进行了更进一步的优化.对于ℓR的计算,目前的方法主要是利用加法链进行优化计算[29].

2.3 探索适合的曲线形式、坐标形式

在不同的曲线模型上,利用不同坐标形式计算点加、倍点、同源以及同源曲线的计算量是不同的.探索一个最适合的曲线模型以及相应的坐标形式,使其在上面这些计算的耗费量最小,也是一种非常重要的优化SIDH实现的方式.Montgomery 等人[32]最早提出了在Montgomery 曲线上仅利用坐标(XM:ZM)就可以进行倍点和标量乘的计算.De Feo 等人[33]给出了在Montgomery 曲线上坐标(XM:ZM)的3-同源和4-同源公式.利用这些基本运算,Costello 等人[6]在Montgomery 曲线上优化了SIDH 的实现.另外,Costello 等人[24]又利用计算同源和同源曲线之间共用的3 阶点、4 阶点继续对3 倍点、3-同源和4-同源以及相应的同源曲线进行优化.Renes 等人[34]给出了核生成点不在(0,0)的2-同源公式,通过1 次复合该2-同源公式,则很容易得到核生成点不在的4-同源公式,其中,a,b为Montgomery 曲线的系数.与DeFeo 等人[33]的方法相比较,该方法避开了求根号以及额外8阶扭点的计算.

注意到,Edwards 曲线与Montgomery 曲线之间存在着双有理关系[35]:

即,Edwards 曲线上的坐标yE完全可以利用Montgomery 曲线上的坐标xM表示.Kim 等人[36]利用该双有理关系推导出在Edwards 曲线坐标(YE:ZE)下的4-同源以及4-同源曲线公式,并发现:在该坐标下实现SIDH 的效率比在Montgomery 曲线坐标(XM:ZM)下实现 SIDH 的效率要稍微高一点.除了在坐标(YE:ZE)下可以优化计算外,Farashahi 等人[37]也探索了新的Edwards 曲线上坐标(WE:ZE)对应的倍点和点加公式,发现其计算量与在坐标(YE:ZE)下相同.另外,Kim 等人[38]研究了在坐标(WE:ZE)下的奇数次同源公式和相应的同源曲线公式,其同源公式的计算量与在Montgomery 曲线上的计算量也是相同的,同源曲线的计算量相比于在Montgomery 曲线上要有优势.然而,对于偶数次同源在Edwards 曲线坐标(WE:ZE)上的公式,目前还没有被提出.

除了以上对于Montgomery 曲线和Edwards 曲线的不同坐标形式的同源和同源曲线公式的研究,Moody 等人[39]还给出了Huff 曲线下的同源和同源曲线公式,Dang 等人[40]给出了Hessian 曲线下的奇数次同源和同源曲线公式,Xu 等人[41]给出了Jacobi quartic 曲线下的同源和同源曲线公式.然而,对于在这几种曲线上的点加、倍点以及同源的计算与在Montgomery 和Edwards 曲线的相应的计算相比,计算的耗费量差异较大,相应的优化还没有给出.此外,对于其他曲线形式,如对Jacobi intersections[42]的同源的研究也没有给出.

2.4 优化同源曲线的计算公式

注意到,同源曲线的优化计算也可以加快SIDH 的实现,因此,Costello 等人[24]提出了3 种不同的方法来计算奇数次同源曲线,分别是:

(1) 利用奇数次同源曲线公式来恢复曲线系数.

在SIDH 中,Alice 和Bob 最终共享的密钥是椭圆曲线的j不变量,当曲线为Montgomery 曲线(by2=x3+ax2+x)时,其j不变量为只与系数a有关,系数b不参与计算.因此,实现SIDH 过程中也只需考虑利用表1 的公式计算同源曲线的系数a.

(2) 利用额外的2 阶扭点的同源值来恢复曲线系数.

在Montgomery 曲线上,当给定初始曲线时,即by2=x3+ax2+x,其二阶扭点很容易获得.即令x3+ax2+x=0,利用韦达定理可得两个根,分别为x1和x2,从而有二阶扭点分别为(0,0)、(x1,0)和(x2,0),计算(x1,0)或者(x2,0)在任意奇数次同源φ的值依然为2 阶扭点,即(φ(x1),0)或者(φ(x2),0),通过这两个同源值,反过来由公式:

即可恢复同源曲线.

(3) 利用固定的3 个点的同源值恢复曲线系数.

在SIDH 中需要计算两个独立点P和Q以及P-Q的同源值.而当知道这3 个点的横坐标时,利用公式:

即可恢复同源曲线.

方法(1)、方法(2)的优点是适合计算小次数同源曲线,缺点是会随着同源次数的增加而增加计算量.方法(3)适合计算较大次数的同源曲线,并且计算量是固定的,均为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-同源的循环次数

对于ℓe-同源的计算,主要是将其分解为e个ℓ-同源的复合.De Feo 等人[33]提出了3 种方法,分别是基于同源的方法、基于标量乘的方法和最优策略算法.其中,基于同源的方法是在复合过程用计算同源的方式去计算每次同源的核生成点;而基于标量乘的方法是在复合过程中用基于标量乘的方式计算每次同源的核生成点;最优策略算法是结合前两种方法的优势提出的一种新的方法,通过比较每次复合中标量乘计算和同源计算的耗费量,并结合最优策略的性质,即一个策略是最优的当且仅当其分解为两个最优子策略,得到最优路径,利用该路径来计算每次同源的核生点.3 种方法相比较而言,第3 种方法的计算效率是最优的.

图2 给出了分别用基于标量乘的方法、基于同源的方法和最优策略计算ℓ7-的同源.假设计算ℓ-同源的计算量为q,计算标量乘[ℓ]R(其中,R为椭圆曲线上任意一个点)的计算量为p,那么利用基于标量乘的方法需要的计算量为21p+6q,利用基于同源的方法的计算量为21q+6p,利用最优策略的方法的计算量为11p+9q.显然,最优策略所需要的计算量最小,是最优的.

Fig.2 Compute ℓ7-isogeny图2 计算ℓ7-同源

Hutchinson 等人[43]利用并行处理的方法对基于最优策略算法进行了更进一步的优化.如图2 所示,在计算同源φ0、φ1、φ3时,可以利用并行处理的方法进行计算.

2.6 减少公钥的尺寸,优化压缩公钥的算法

对于基于超奇异椭圆曲线密钥交换协议的公钥尺寸的压缩,主要有两种方法:(1) 通过减少公钥的参数缩小公钥的规模;(2) 通过将公钥的点表示为基点的线性组合,将相应的坐标代替点达到压缩公钥的目的.此外,对于其压缩算法的效率也是目前研究的一个热点.

Costello 等人[24]利用Montgomery 曲线下的坐标(XM:ZM)实现SIDH,用3 个点的横坐标:

代替原来的公钥:

其中,曲线系数的计算可以利用第2.4 节中的方法(3),从而将公钥尺寸由原来的12log2p降低到6log2p.

Azarderakhsh 等人[44]通过将公钥中的点表示为

求解离散对数得到a0、a1、b0、b1,从而将公钥变为(EB,a0,a1,b0,b1),将其尺寸减少到4log2p.然而,压缩公钥的算法由于需要双线性对和离散对数的计算,比以前的计算耗费量要大.Costello 等人[45]构造了n阶基点生成算法,优化Tate 对计算以及Pohlig-Hellman 算法,将公钥中表示点的线性组合的系数由原来的4 个减少到3 个,增加1 额外比特信息,从而将尺寸减少到同时,将压缩公钥的计算效率提高了2.4 倍.具体如下.

由于PB和QB是公开参数,h0可以预计算,相比于Costello 等人的算法减少了一个双线性对的计算.Naehrig等人[47]利用2-同源的对偶同源比2-同源计算(核生成点非(0,0))要快的性质,将SIKE 中密钥生成阶段的开销由原来的140%～153%减少到61%～74%,将密钥封装由原来的67%～90%减少到38%～57%,将解封装由原来的59%～65%减少到34%～38%.

根据前面对于CSIDH 协议以及算法1 的描述,优化CSIDH 的实现关键在于提高算法1 的效率,这一节主要总结对于算法1 的各种优化方法.

3.1 设计常数时间的算法

3.2 优化椭圆曲线中的标量乘计算

Meyer 等人[51]通过调整算法1 中初始点的计算,计算P=4P0,α=ℓ1ℓ2…ℓn,其中,ℓ1＞ℓ2＞…＞ℓn.将作为第1 个次数为ℓ1同源的核生成点,并在具体的迭代计算中优先计算次数较大的同源,再计算次数较小的同源,减少标量乘的计算,从而使得算法1 的实现效率比之前提高了1.096 倍.之后,Meyer 等人将密钥空间的指标集合化分为多个集合,从而将同源的计算分解为多个分支,在很大程度上减少了每次循环需要的标量乘计算.

3.3 优化基点P的生成算法

当密钥的每个分量均变为正时,随机点的选取只需考虑定义在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 优化同源的计算

考虑到CSIDH 中同源的次数相对于SIDH 中同源的次数较大,Bernstein 等人[52]利用Strassen 算法进行优化,将ℓ-同源的计算由原来的O(ℓ)降为

3.5 优化同源曲线的计算

注意到,CSIDH 中同源曲线的计算与在SIDH 中的计算方式是不同的:在SIDH 中,需要计算额外点的同源值,同源曲线的计算刚好可以利用这些点的同源值,避免了因同源次数增加而相应的同源曲线的计算量增加所带来的不便;在CSIDH 中,不需要额外点的计算,同源曲线的计算只能利用推导的公式本身去优化计算.由于利用Montgomery 曲线形式计算同源曲线的效率不是很高[24],Meyer 等人[48]借助Montgomery 曲线与扭Edwards曲线之间双有理等价关系,利用扭Edwards 曲线上的同源曲线公式来优化计算.即:在Montgomery 曲线上,坐标(XM:ZM)可以通过变换:

转化到扭Edwards 曲线射影坐标(YE:ZE).同时,Montgomery 曲线系数(A:C)可以通过变换a=A+2C和d=A-2C转化到扭Edwards 曲线参数(a,d).在扭Edwards 曲线上,利用公式:

可以计算扭Edwards 曲线上的ℓ-同源曲线参数(a＇,d＇),其中,ℓ-同源的核为〈P〉={[iP]:i=0,…,ℓ=2s+1}.通过变换(A＇:C＇)=(2(a＇+d＇):a＇-d＇),可以得到Montgomery 曲线上的ℓ-同源曲线.Kim 等人[38]借助奇数阶点在2 倍标量乘的作用下不改变其阶这一性质,优化Ewards 曲线上在新坐标(WE:ZE)下的同源曲线公式,如表1 所示.

自椭圆曲线同源在公钥密码学中得到广泛应用,其对应的公钥加密和密钥封装进入美国NIST 标准第2 轮,对于SIDH 和CSIDH 的有效计算引起了学者们的重视,正如上面所分析的,取得了很多突破性的进展.但是,这一领域还有许多问题亟待解决.

(1) 借助不同曲线模型,探索不同坐标形式以及在该坐标下的倍点、点加、同源和同源曲线的计算公式,利用这些优化的公式来优化SIDH 和CSIDH 的实现.目前比较主流的实现SIDH 和CISDH 均在Montgomery 和Edwards 曲线上,对于其他曲线,如Huff 曲线、Hessian 曲线、Legendre 曲线和Jacobian Intersections 等的研究还比较少.是否最优的实现就是在Montgomery 曲线或者Edwards 曲线,亦或者有更好的曲线代替这两种曲线去实现SIDH 和CISDH,是值得关注的问题;

(2) 对于优化SIDH,除了考虑以上的方法外,还可以利用超椭圆曲线的优势去优化计算.注意到利用亏格为2 的Kummer 面实现SIDH,其域的尺寸在同等安全级别下比亏格为1 的Kummer 线上实现SIDH要小,其上的(2,2)-同源也有快速计算公式,然而,其(3,3)-同源的计算比较复杂,需要我们进一步加以深入研究;

(5) 对于公钥尺寸的有效压缩,也是目前研究的一个热点.基于Kummer 线上的SIDH 的加密和密钥封装的公钥压缩,已有很多工作.然而,对于阶为3e点的有效压缩算法,依然是一个亟待解决的问题.此外,利用Kummer 面上SIDH 设计的加密方案,其上的公钥尺寸还比较大.能否缩短公钥的尺寸,如将公钥中的点表示为固定基点的线性组合?这些问题均是值得我们后续研究的;

(6) 对于CSIDH 的优化,设计一个常数时间且有效的算法实现[a]E的计算,依然是目前研究的一个热点.目前设计的算法,实现的效率还比较低.能否借助一些特性,如基域上的ℓ-同源只有两种情况,减少同源的计算,或者构造更加有效的基点生成算法等,对其进行更进一步的优化?都是值得研究的;

(7) 借助其他优化标量乘或者双线性对[53]的技术,如借助多维标量乘[54]、椭圆网[55]等技术优化SIDH 或者CSIDH 的方式,也值得更进一步地加以研究.

猜你喜欢 公钥同源密钥 山西恩予：打造药食同源新业态今日农业(2022年2期)2022-11-16幻中邂逅之金色密钥故事作文·低年级(2022年2期)2022-02-23幻中邂逅之金色密钥故事作文·低年级(2022年1期)2022-02-03以同源词看《诗经》的训释三则汉字汉语研究(2021年2期)2021-08-30神奇的公钥密码知识就是力量(2018年10期)2018-10-18Android密钥库简析计算机与网络(2018年2期)2018-09-10同源宾语的三大类型与七项注意新高考·英语进阶（高二高三）(2018年8期)2018-01-15国密SM2密码算法的C语言实现中国新通信(2017年18期)2017-10-22基于身份的聚合签名体制研究成长·读写月刊(2017年4期)2017-05-16一种新的动态批密钥更新算法西安交通大学学报(2009年12期)2009-02-08