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

基于椭圆曲线同源的密码系统早期的研究主要集中在一般椭圆曲线(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的其他可能优化的问题.

1 Vélu公式、SIDH协议以及CSIDH协议

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

1.1 同源和Vélu公式

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

$\begin{array}{l} \phi :E \to E' \\ ({x_P}, {y_P}) \to ({x_P} + \sum\nolimits_{Q \in G\backslash O} {({x_{P + Q}} - {x_Q})} , {y_P} + \sum\nolimits_{Q \in G/O} {({y_{P + Q}} - {y_Q})} ) \\ \end{array} $

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

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

表 1中, 通过比较不同曲线形式上的ℓ-同源和ℓ-同源曲线的计算量可知: 在Montgomery曲线和Edwards曲

线的同源计算量相同, 且均比在Huff曲线、Hessian曲线和Jacobi quartic曲线的计算更具优势.对于同源曲线的计算, 在Edwards曲线上比在Montgomery曲线、Huff曲线、Hessian曲线和Jacobi quartic曲线上的计算都更有优势.

1.2 SIDH协议

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

假设$p = \ell _A^{{e_A}}\ell _B^{{e_B}}f \mp 1$是一个大素数, 其中, ℓ_A和ℓ_B均为小素数; e_A和e_B满足$\ell _A^{{e_A}} \approx \ell _B^{{e_B}}$; f为一个小因子, 使得p为素数.在有限域${\mathbb{F}_{{p^2}}}$中选择一个超奇异椭圆曲线E₀作为起始曲线, 其基数为$\# {E_0}({\mathbb{F}_{{p^2}}}) = {(\ell _A^{{e_A}}\ell _B^{{e_B}})^2}.$

假设Alice和Bob想进行密钥交换获得一个共同的密钥, 首先, Alice和Bob分别产生阶为$\ell _A^{{e_A}}$的独立点{P_A, Q_A}和阶为$\ell _B^{{e_B}}$的独立点{P_B, Q_B}.Alice选择${m_A} \in \{ 1, 2, ..., \ell _A^{{e_A} - 1}\}, $计算在核〈P_A+m_AQ_A〉下的同源ϕ_A: E₀→E_A以及点P_B和Q_B的同源值ϕ_A(P_B)和ϕ_A(Q_B), 将ϕ_A(P_B)、ϕ_A(Q_B)、E_A发送给Bob.同时, Bob进行类似的操作, 计算在核〈P_B+m_BQ_B〉下的同源ϕ_B: E₀→E_B以及点P_A和Q_A的同源值ϕ_B(P_A)和ϕ_B(Q_A), 将ϕ_B(P_A)、ϕ_B(Q_A)、E_B发送给Alice.

在密钥确立阶段, Alice计算在核〈ϕ_B(P_A)+m_Aϕ_B(Q_A)〉下的同源ϕ_A': E_B→E_AB, 获得曲线E_AB.Bob进行类似的操作, 计算在核〈ϕ_A(P_B)+m_Bϕ_A(Q_B)〉下的同源ϕ_B': E_A→E_BA, 获得曲线E_AB.最后, Alice和Bob获得共同的j不变量, 即j(E_AB)=j(E_BA).协议过程如图 1所示.定义A和B为Alice和Bob的标识, sID为唯一的会话标识.

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

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

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

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

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

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

1.3 CSIDH

Castryck等人^[22]提出了定义在基域$ {\mathbb{F}}_p $上的可交换的密钥交换协议CSIDH, 其具体过程如下.

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

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

算法1^[22].

输入: 超奇异椭圆曲线E₀和理想类$[\mathit{\boldsymbol{a}}] = [\mathit{\boldsymbol{l}}_1^{{e_1}}...\mathit{\boldsymbol{l}}_n^{{e_n}}]$, 其中, e_i∈{-5, …, 5};

输出: 曲线E_A, 满足$[\mathit{\boldsymbol{l}}_1^{{e_1}}...\mathit{\boldsymbol{l}}_n^{{e_n}}]E = {E_A}.$

1. 当e_i≠0:

  1.1. 机选择x∈$ {\mathbb{F}}_p $, 令点P的横坐标为x;

  1.2. 令s←+1, 若x³+ax²+x在$ {\mathbb{F}}_p $为一个平方; 否则, s←-1;

  1.3. 令S={i|e_i≠0, sign(e_i)=s}.若s=Ø, 重新选择x;

  1.4. 令$k \leftarrow \prod\limits_{i \in S} {{\ell _i}} $, 计算$Q \leftarrow \left[{\frac{{p + 1}}{k}} \right]P$;

  1.5. For i∈S:

    1.5.1.  计算$R \leftarrow \left[{\frac{k}{{{\ell _i}}}} \right]Q.$若R=O, 则跳过i;

    1.5.2.  计算在核〈R〉下的同源φ: E→E_a: y²=x³+ax²+x;

    1.5.3.  令a←a, Q←φ(Q), $k \leftarrow \frac{k}{{{\ell _i}}}, $e_i←e_i-s.

2. 返回a

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

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

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

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

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

2 SIDH实现的改进概述

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

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

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

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

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

对于第3个方面, Costello等人^[30]借助在同样的特征下, 基域$ {\mathbb{F}}_p $中的模代数运算比在扩域${\mathbb{F}_{{p^2}}}$中要快, 即:

${A_{{\mathbb{F}_{{p^2}}}}} = 2{A_{{\mathbb{F}_p}}}, {S_{{\mathbb{F}_{{p^2}}}}} = 2{S_{{\mathbb{F}_p}}} + {M_{{\mathbb{F}_p}}} + 4{A_{{\mathbb{F}_p}}}, {M_{{\mathbb{F}_{{p^2}}}}} = 3{M_{{\mathbb{F}_p}}} + 5{A_{{\mathbb{F}_p}}}, {I_{{\mathbb{F}_{{p^2}}}}} = {I_{{\mathbb{F}_p}}} + 2{M_{{\mathbb{F}_p}}} + 2{S_{{\mathbb{F}_p}}}, $

其中, $ {A}_{{\mathbb{F}}_{{p}^{2}}}、{S}_{{\mathbb{F}}_{{p}^{2}}}、{M}_{{\mathbb{F}}_{{p}^{2}}}$和${I_{{\mathbb{F}_{{p^2}}}}}$分别为扩域中的加法、平方、乘和求逆运算, $ {A}_{{\mathbb{F}}_{p}}、{S}_{{\mathbb{F}}_{p}}、{M}_{{\mathbb{F}}_{p}}$和${I_{{\mathbb{F}_p}}}$分别表示基域中的加法、平方、乘和求逆运算, 将扩域${\mathbb{F}_{{p^2}}}$中亏格为1的椭圆曲线的Kummer线(将椭圆曲线E的商E/〈±1〉称为Kummer线)上2-同源的计算通过Weil限制的方法转化到基域$ {\mathbb{F}}_p $上亏格为2的超椭圆曲线的Kummer面(对于亏格为2的超椭圆曲线C, J_C为其雅克比, 其商J_C/〈±1〉为Kummer面)上的(2, 2)-同源的计算.

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曲线上仅利用坐标(X_M: Z_M)就可以进行倍点和标量乘的计算.De Feo等人^[33]给出了在Montgomery曲线上坐标(X_M: Z_M)的3-同源和4-同源公式.利用这些基本运算, Costello等人^[6]在Montgomery曲线上优化了SIDH的实现.另外, Costello等人^[24]又利用计算同源和同源曲线之间共用的3阶点、4阶点继续对3倍点、3-同源和4-同源以及相应的同源曲线进行优化.Renes等人^[34]给出了核生成点不在(0, 0)的2-同源公式, 通过1次复合该2-同源公式, 则很容易得到核生成点不在$\left({1, \mp \sqrt {\frac{{a + 2}}{b}} } \right)$的4-同源公式, 其中, a, b为Montgomery曲线的系数.与DeFeo等人^[33]的方法相比较, 该方法避开了求根号以及额外8阶扭点的计算.

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

$({x_E}, {y_E}) = \left( {\frac{{{x_M}}}{{{y_M}}}, \frac{{{x_M} - 1}}{{{x_M} + 1}}} \right).$

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

除了以上对于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曲线(by²=x³+ax²+x)时, 其j不变量为$j = \frac{{256{{({a^2} - 3)}^3}}}{{{a^2} - 4}}, $只与系数a有关, 系数b不参与计算.因此, 实现SIDH过程中也只需考虑利用表 1的公式计算同源曲线的系数a.

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

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

$ a' = \frac{{ - ({\phi ^2}({x_1}) + 1)}}{{\phi ({x_1})}}或者a' = \frac{{ - ({\phi ^2}({x_2}) + 1)}}{{\phi ({x_2})}} $

即可恢复同源曲线.

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

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

$ a = \frac{{{{(1 - {x_P}{x_Q} - {x_P}{x_{P - Q}} - {x_Q}{x_{P - Q}})}^2}}}{{4{x_P}{x_Q}{x_{P - Q}}}} - {x_P} - {x_Q} - {x_{P - Q}} $

即可恢复同源曲线.

方法(1)、方法(2)的优点是适合计算小次数同源曲线, 缺点是会随着同源次数的增加而增加计算量.方法(3)适合计算较大次数的同源曲线, 并且计算量是固定的, 均为8M+5S, 前提是要有额外的同源点.

表 2给出了利用以上3种方法分别计算3-同源曲线和19-同源曲线的计算量.计算3-同源曲线, 利用方法(1)的计算量最小; 计算19-同源曲线, 利用方法(3)的计算量最小.

2.5 减少ℓ^e-同源的循环次数

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

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

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

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

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

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

$ x({\phi _A}({P_B})), x({\phi _A}({Q_B})), x({\phi _A}({P_B} - {Q_B})) $

代替原来的公钥:

$ {\phi _A}({P_B}), {\phi _A}({P_B}), {E_B}, $

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

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

$ {\phi _A}({P_B}) = {a_0}{U_B} + {b_0}{V_B}, {\phi _A}({Q_B}) = {a_1}{U_B} + {b_1}{V_B}, $

其中, $\left({{a_i}, {b_i} \in Z/\ell _B^{{e_B}}Z, i = 0, 1} \right), $U_B和V_B为同源曲线E_B上阶为$\ell _B^{{e_B}}$的线性独立点, 计算双线性对:

$\begin{gathered} {g_0} = {e_{\ell _B^{{e_B}}}}({U_B}, \;{V_B}), \\ {g_1} = {e_{\ell _B^{{e_B}}}}({U_B}, {\phi _A}({P_B})) = {e_{{3^n}}}({U_B}, {a_0}{U_B} + {b_0}{Q_B}) = g_0^{{b_0}}, \\ {g_2} = {e_{\ell _B^{{e_B}}}}({U_B}, {\phi _A}({Q_B})) = {e_{{3^n}}}({U_B}, {a_1}{U_B} + {b_1}{Q_B}) = g_0^{{b_1}}, \\ {g_3} = {e_{\ell _B^{{e_B}}}}({V_B}, {\phi _A}({P_B})) = {e_{{3^n}}}({V_B}, {a_0}{U_B} + {b_0}{Q_B}) = g_0^{{a_0}}, \\ {g_4} = {e_{\ell _B^{{e_B}}}}({V_B}, {\phi _A}({Q_B})) = \;{e_{{3^n}}}({V_B}, {a_1}{U_B} + {b_1}{Q_B}) = g_0^{{a_1}}. \\ \end{gathered} $

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

由于

$ \langle {\varphi }_{A}({P}_{B})+{\ell }_{B}m{\varphi }_{A}({Q}_{B})\rangle =\left\{ \begin{array}{l}\langle {a}_{0}^{-1}{\varphi }_{A}({P}_{B})+{a}_{0}^{-1}{\ell }_{B}m{\varphi }_{A}({Q}_{B})\rangle , \;\;如果{a}_{0}\in {Z}_{{\ell }_{B}^{{e}_{B}}}^{\ast } \\ \langle {b}_{0}^{-1}{\varphi }_{A}({P}_{B})+{b}_{0}^{-1}{\ell }_{B}m{\varphi }_{A}({Q}_{B})\rangle , \;\;如果{b}_{0}\in {Z}_{{\ell }_{B}^{{e}_{B}}}^{\ast }, \end{array} \right.$

而

$\begin{gathered} a_0^{ - 1}{\phi _A}({P_B}) = {U_B} + a_0^{ - 1}{b_0}{V_B}, a_0^{ - 1}{\phi _A}({Q_B}) = a_0^{ - 1}{a_1}{U_B} + a_0^{ - 1}{b_1}{V_B}, \\ b_0^{ - 1}{\phi _A}({P_B}) = b_0^{ - 1}{a_0}{U_B} + {V_B}, b_0^{ - 1}{\phi _A}({Q_B}) = b_0^{ - 1}{a_1}{U_B} + b_0^{ - 1}{b_1}{V_B}. \\ \end{gathered} $

因此, 公钥就变为

$ PK=\left\{ \begin{array}{l}({E}_{B}, 0, {a}_{0}^{-1}{b}_{0}, {a}_{0}^{-1}{a}_{1}, {a}_{0}^{-1}{b}_{1}), \;\;如果{a}_{0}\in {Z}_{n}^{\ast } \\ ({E}_{B}, 1, {b}_{0}^{-1}{a}_{0}, {b}_{0}^{-1}{a}_{1}, {b}_{0}^{-1}{b}_{1}), \;\;如果{b}_{0}\in {Z}_{n}^{\ast } \end{array} \right..$

Zanon等人^[46]提出了更有效的阶为2^e的基点生成算法, 利用逆的基分解, 即: 由

$\left[ {\begin{array}{*{20}{c}} {{\phi _A}({P_B})} \\ {{\phi _A}({Q_B})} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} {{a_0}}&{{b_0}} \\ {{a_1}}&{{b_1}} \end{array}} \right]\left[ {\begin{array}{*{20}{c}} {{U_B}} \\ {{V_B}} \end{array}} \right]$

可推导

$\left[ {\begin{array}{*{20}{c}} {{U_B}} \\ {{V_B}} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} {{c_0}}&{{d_0}} \\ {{c_1}}&{{d_1}} \end{array}} \right]\left[ {\begin{array}{*{20}{c}} {{\phi _A}({P_B})} \\ {{\phi _A}({Q_B})} \end{array}} \right], $

其中, $\left[{\begin{array}{*{20}{c}} {{a_0}} & {{b_0}} \\ {{a_1}} & {{b_1}} \end{array}} \right] = \frac{1}{D}\left[{\begin{array}{*{20}{c}} {{d_1}} & { - {d_0}} \\ { - {c_1}} & {{c_0}} \end{array}} \right], D = {c_0}{d_1} - {c_1}{d_0}.$

计算双线性对:

$\begin{gathered} {h_0} = {e_{\ell _B^{{e_B}}}}({\phi _A}({P_B}), {\phi _A}({Q_B})) = {e_{{3^n}}}{({P_B}, \;{Q_B})^{{2^n}}}, \\ {h_1} = {e_{\ell _B^{{e_B}}}}({\phi _A}({P_B}), {U_B}) = {e_{{3^n}}}({\phi _A}({P_B}), {c_0}{\phi _A}({P_B}) + {d_0}{\phi _A}({Q_B})) = h_0^{{d_0}}, \\ {h_2} = {e_{\ell _B^{{e_B}}}}({\phi _A}({P_B}), {V_B}) = {e_{{3^n}}}({\phi _A}({P_B}), {c_{1\:}}{\phi _A}({P_B}) + {d_1}{\phi _A}({Q_B})) = h_0^{{d_1}}, \\ {h_3} = {e_{\ell _B^{{e_B}}}}({\phi _A}\left( {{Q_B}} \right), {U_B}) = {e_{{3^n}}}({\phi _A}({Q_B}), {c_{0\:}}{\phi _A}({P_B}) + {d_0}{\phi _A}({Q_B})) = h_0^{ - {c_0}}, \\ {h_4} = {e_{\ell _B^{{e_B}}}}({\phi _A}\left( {{Q_B}} \right), {V_B}) = {e_{{3^n}}}({\phi _A}({Q_B}), {c_{1\:}}{\phi _A}({P_B}) + {d_1}{\phi _A}({Q_B})) = h_0^{ - {c_1}}. \\ \end{gathered} $

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

3 CSIDH实现的改进概述

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

3.1 设计常数时间的算法

对于算法1中的密钥$[a] = [{\boldsymbol{l}}_1^{{e_1}}{\boldsymbol{l}}_2^{{e_2}}...{\boldsymbol{l}}_n^{{e_n}}], $指标e₁, …, e_n包含了需要计算的奇数次同源的个数.密钥不同, 相应的指标不同, 所需要计算的同源个数也会不同.另外, 这些指标均从集合{-5, …, 5}中选取, 其正负情况决定了所选的基点在$ {\mathbb{F}}_p $中还是在${\mathbb{F}_{{p^2}}}$中, 相应的同源的计算量也会有较大区别.因此, 算法1的计算耗费量不是常数时间的, 会随着密钥的变化而变化, 不能抵抗侧信道攻击.针对上述存在的问题, Meyer等人^[48]利用差分加法的计算与同源的计算耗费量相同这一点, 通过增加冗余的标量乘计算来固定同源的计算个数, 并将相应的指标区间从集合{-5, …, 5}变为集合{0, …, 10}, 改进了算法1, 其计算的耗费量也是常数时间的, 能够抵抗测信道的攻击.然而, 其实现的效率却是算法1的2倍.Onuki等人^[49]设定密钥的空间为集合{-5, …, 5}, 结合上述增加冗余固定同源个数的方式, 提出了更快的实现CSIDH的算法, 其运行时间依然为常数时间.然而, 注意到增加冗余并不能抵抗错误注入攻击, Cervantes-Vázquez等人^[50]移除冗余的同源计算, 利用Edwards曲线上的代数操作和加法链, 提出更加有效的且能抵抗侧信道攻击的算法.

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

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

3.3 优化基点P的生成算法

当密钥的每个分量均变为正时, 随机点的选取只需考虑定义在$ {\mathbb{F}}_p $上的点.Meyer等人^[51]首次利用Eligator算法快速生成定义在$ {\mathbb{F}}_p $上的点P的横坐标x.给定曲线y²=x³+ax²+x, 其中, a∈$ {\mathbb{F}}_p $, 该算法对于步骤(2)中的$\frac{1}{{{u^2} - 1}}$可以采取预先计算的方式, 避免了求逆, 比随机选取点的算法效率要高.

Eligator算法^[51].

输入: u∈$ {\mathbb{F}}_p $;

输出: x∈$ {\mathbb{F}}_p $.

1. 在集合$\left\{ {2, 3, ..., \frac{{p - 1}}{2}} \right\}$中随机选一个u,

2. 计算$v = \frac{a}{{{u^2} - 1}}.$

3. 计算$e = \left({\frac{{{v^3} + a{v^2} + v}}{p}} \right).$

4. 如果e=1, 输出x=v; 否则, 输出x=-v-a.

当密钥的每个分量有正有负时, Onuki等人^[49]利用Eligator算法快速生成两个合法点, 分别是定义在$ {\mathbb{F}}_p $上的点和定义在${\mathbb{F}_{{p^2}}}$上的点.

3.4 优化同源的计算

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

3.5 优化同源曲线的计算

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

$ ({X_M}:{Z_M}) \to ({Y_E}:{Z_E}) = ({X_M} + {Z_M}:{X_M} - {Z_M}) $

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

$a' = {a^\ell }{(\prod\nolimits_{i = 1}^S {{Y_{[iP]}}} )^8}, d' = {d^\ell }{(\prod\nolimits_{i = 1}^S {{Z_{[iP]}}} )^8}, $

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

4 总结和展望

自椭圆曲线同源在公钥密码学中得到广泛应用, 其对应的公钥加密和密钥封装进入美国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)-同源的计算比较复杂, 需要我们进一步加以深入研究;

(3) 对于同源次数形如$\ell _1^{{e_1}}\ell _2^{{e_2}}...\ell _k^{{e_k}}$的同源的有效计算, 也是一个值得研究的问题.除了基于同源和基于标量乘的算法, 设计最优策略算法或者借助并行处理的技巧优化计算, 这也是我们迫切需要研究的;

(4) 对于SIDH中有限域${\mathbb{F}_{{p^2}}}$的特征p的选取, 也是一个研究的热点.之前的SIDH中参数$p = f \cdot \ell _A^{{e_A}} \cdot \ell _B^{{e_B}} - 1$, 要求$\ell _A^{{e_A}} \approx \ell _B^{{e_B}}.$当对于SIDH中一方要求计算比较快时, 参数p的选取也可以有其他的方法, 如p=2ⁿf-1形式或者p=2ⁿ-2^m-1或者满足p+1和p-1均含有多个小素因子的乘积, 且能够达到后量子相应的安全级别的素数p;

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

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

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