0 引言

自20世纪80年代中期椭圆曲线密码体制(elliptic curve cryptography, ECC)^{[1, 2]}被提出之后，由于其密钥短，运算量相对较少，安全性能高等优势，已被广泛应用在资源受限的硬件设备中^[3]。ECC的安全性依赖于离散对数问题的难解性，如果攻击者能很容易从用户的公钥中计算出私钥，那么这个密码体制就是不安全的。在ECC中，标量乘算法kP（k为用户的私钥，P 为用户选取的椭圆曲线上的一有理点）是最耗时，也是最关键的算法。当攻击者截获或根据消耗轨迹推算出标量k，就能破解椭圆曲线加密，因此，标量乘的安全决定着整个椭圆曲线密码体制的安全性。而标量乘的运算易受到侧信道攻击(side channel attack, SCA)^[4]。

标量乘算法的运行速度决定着整个ECC的实现效率，因此通过提高标量乘的运行速度，可以提高ECC的效率。标量乘算法主要包括两个层次：上层标量k 的展开；底层有限域内点加、倍点的域乘、域平方、求逆等基础运算^[5]，本文重点研究底层。Co_Z 点加运算在2007年由Meloni^[6]首次提出，该运算通过统一椭圆曲线上两射影点的Z 坐标，使点加运算量降低，得出了新的点加算法，并将其应用在Euclidean加法链和Zeckendorf展开式中，通过减少点加运算中的域乘和域平方计算次数提高标量乘效率。近几年，Goundar、Wei等^{[7, 8]}将Co_Z 算法应用到Montgomery阶梯算法、Joy倍点点加算法和NAF(non-adjacent form)算法，优化了Weierstrass椭圆曲线上的标量乘运算公式。2017年，于伟等^[9]在Montgomery算法的基础上，首次利用统一Z 坐标技巧，改进了有限域GF(3^m)上椭圆曲线的点加和倍点公式。本文，我们提出特征2有限域椭圆曲线上的Co_Z 点加运算，推导出不同射影坐标系下的点加及三倍点（3P）运算公式。

1 背景知识 1.1 有限域GF(2^m)上的椭圆曲线

定义在域K 上的一个Weierstrass方程

通过变量的相容性，可以简化方程。根据域K的特征不同，将椭圆曲线分为3种情况：特征不等于2或3、特征等于2和特征等于3。

当域K 的特征不等于2或不等于3时，通过相容性变换，曲线E 可简化为：y² = x³ + ax + b, 其中a, b ∈ K。曲线的判别式是Δ = -16(4a³ + 27b²)。

若域K 的特征是3，则其非超奇异椭圆曲线^[10]简化为：y² = x³ +ax² + b，其中a, b ∈ K，Δ =- a³b。

本文研究的重点是特征为2的非超奇异椭圆曲线，其Weierstrass方程可简化为：y² + xy = x³ + ax² + b，Δ = b。

根据“弦和切线”法则^[11]，有限域GF(2^m)上的两点相加得到椭圆曲线上的第三点。椭圆曲线上的点集合及这种加法运算构成了一个加法交换群，∞为加法交换群的无穷远点。因此，有限域GF(2^m)上的非超奇异椭圆曲线的群运算法则为：

1）单位元

对于所有的P ∈ E (GF (2^m))，P + ∞ = ∞ + P

2）负元素

如果P = (x, y ) ∈ E (GF (2^m))，则(x, y )+(x, x + y )= ∞。记点(x, x + y )为-P，并称其为P 的负。注意，-P 也是E (GF (2^m))上的一点。

3）点加

令P = (x₁, y₁) ∈ E (GF (2^m)), Q= (x₂, y₂) ∈E (GF(2^m))，P ≠ Q, 则P + Q = (x₃, y₃)。其中

(1)

4）倍点

令P = (x₁, y₁) ∈ E (GF (2^m))，P ≠ - P, 则2P =(x₃, y₃)。其中

(2)

由此可得出，仿射坐标系下，点加运算量为1次求逆(I)，1次平方(S)和2次乘(M)；倍点运算量为1I+1S+2M。由于求逆的计算代价较高，因此通过转换坐标系，避免运算公式中出现求逆，可降低点加和倍点的运算代价^[12]。

1.2 射影坐标下的点加和倍点运算公式

本文中，我们考虑两种射影坐标下的点加和倍点运算。

1.2.1 López & Dahab射影坐标

射影点(X:Y:Z ), Z ≠ 0与仿射点()对应，GF(2^m)上的Weierstrass方程的投影形式定义为

令P = (X₁:Y₁:Z₁), Q = (X₂:Y₂:Z₂), P + Q = (X₃:Y₃:Z₃)。若P ≠ Q, 则点加运算公式为

(3)

其中：A = X₁Z₂，B = X₂Z₁，C = Z₁²，D = Z₂²，E = Y₁D，F = Y₂C，G = Z₁Z₂，H = E + F，I = A + B。其倍点运算公式为

(4)

其中：A = X₁², B = Z₁², C = X₁Z₁。

根据运算公式，可以看出一次点加运算量为13M + 5S，一次倍点运算量为4M + 5S。当假设Z₂ = 1时，点加运算量降至10M + 5S。López等^[13]改进了倍点运算，将运算量降低到3M+5S。

1.2.2 Jacobian射影坐标

射影点(X:Y:Z ), Z ≠ 0与仿射点P =()对应，GF(2^m)上的Weierstrass方程的投影形式定义为

令P = (X₁:Y₁:Z₁)，Q = (X₂:Y₂:Z₂)，P + Q = (X₃:Y₃:Z₃)。若P≠Q，则点加运算公式为

(5)

其中：A = Z₁²，B = Z₂²，C = X₁B，D = X₂A，E = Z₁Z₂，F = Y₁Z₂，G = Y₂Z₁，H = FB + GA，I = E (C + D )，J = C + D。其倍点运算公式为

(6)

其中：A = X₁²，B = Z₁²，C = X₁B，D = Y₁Z₁。

根据运算公式，可以看出一次点加运算量为14M+5S，一次倍点运算量为4M+5S。假设Z₂= 1时，点加运算量将降到10M+3S。

2 Co_Z点加运算和3P 运算 2.1 射影坐标下的Co_Z 点加运算

令集合K³\ {(0:0:0)}是有限域GF(2^m)上的非零三维向量的集合，其上的投影点存在如下等价关系

通过这一关系，我们可以将椭圆曲线上的两点P = (X₁:Y₁:Z₁), Q = (X₂:Y₂:Z₂)通过坐标处理，共享Z 轴，这就是Co_Z 的主要思路。上节给出了射影坐标下的点加运算公式，当引入Co_Z 后，可以推导出射影坐标系下改进后的Co_Z 点加运算公式。

2.1.1 López & Dahab射影坐标下的Co_Z 点加

López & Dahab射影坐标下的两点P, Q 在仿射坐标下表示为, 分母通分后，两坐标可表示为

再转换为射影坐标，则得到

因此可将P, Q 两点转换为Z 坐标相同的点。

令初始点P = (X₁:Y₁:Z )，Q = (X₂:Y₂:Z )统一Z 坐标，则P + Q = (X₃:Y₃:Z₃)的计算公式如下

(7)

可将其简化为

(8)

P+Q 点中X、Y 轴坐标满足(X₁ZA²:Y₁Z² A⁴: Z² A²)~(X₁:Y₁:Z )，因此Co_Z 点加运算的输出点P+Q 和输入点P 具有相同的Z 坐标，而统一Z 轴变换已经在Co_Z 点加运算中计算出来，所以不需要额外的运算量。点加算法如算法1。

算法1所需运算量为10M+3S，比Z₂ = 1时的点加运算量减少了2S。由于在算法1计算过程中，输入点P 与输出点P+Q 的Z 轴的统一运算量较大，因此在López & Dahab射影坐标下Co_Z 点加的效率提升不是很明显。

2.1.2 Jacobian射影坐标下的Co_Z 点加运算

令初始点P = (X₁:Y₁:Z ), Q = (X₂:Y₂:Z )，统一Z 坐标，则P + Q = (X₃:Y₃:Z₃)的计算公式可简化为

P+ Q 点中X、Y 轴坐标满足(X₁A²:Y₁A³:ZA ) ~(X₁:Y₁:Z )，因此Co_Z 点加运算的输出点P+ Q和输入点P 具有相同的Z 坐标，而统一Z 轴变换已经在Co_Z 点加运算中计算出来，所以不需要额外的运算量。点加算法如算法2。

Jacobian射影坐标下Co_Z 点加操作所需运算量为8M + 3S，比Z₂ = 1时的点加运算量减少了2M。

2.2 有限域GF (2^m)上的3P 运算

本小节将计算有限域GF (2^m)下的3P 运算，首先回顾一下倍点的运算公式。

令P = (x₁, y₁)，2P = (x₂, y₂),其中

计算3P = 2P + P = (x₃, y₃)，Dimitrov等^[14]给出了仿射坐标系下的3P 运算公式

因此，仿射坐标系下计算一次3P 运算量为1I+ 3S+ 6M，这种算法比文献[15]减少了1M + 1S.在Dimitrov提出的3P 运算公式的基础上，可以推导出射影坐标下的3P 运算公式。本文对输入点的Z 坐标进行特殊化处理，能够改进3P 运算公式，减少运算量。

2.2.1 López & Dahab射影坐标下的3P 运算

2008年，顾海华^[16]提出一种López & Dahab射影坐标下的3P 运算公式(TPL)：3P = (X₃:Y₃:Z₃)，则

其中: A = X₁²，B = X₁Z₁，C = AB，D = A - Y₁，E = aB² - D (D + B )，F = C + E，G = BC + FD，H = B²E。

这种López & Dahab射影坐标下的3P 运算量为12M+4S。

2.2.2 Jacobian射影坐标下的3P 运算

Jacobian射影坐标下的3P = (X₃:Y₃:Z₃)，运算经过简化可以写成

其中：E = X₁Z₁² + X₂，F = EZ₂，G = Y₁X₁³Z₁³ + Y₂，H = aF² + G (G + F )+ E³，X₂ = X₁⁴ + bZ₁⁸，Y₂ = X₁⁴Z₂ +(X₁² + Y₁Z₁ + Z₂) X₂，Z₂ = X₁Z₁²。

因此，此3P 运算量为13M+7S。

对Z 坐标进行特殊化处理，当Z₁ = 1时，可以得出改进后的3P 运算公式。通过分析可知，改进后的3P 运算代价为12M+3S，具体算法如算法3。

2.3 Co_Z 对称三进制标量乘算法

标量k 可展开成对称三进制形式(symmetric ternary form，STF)^[17]，相对二进制形式，它能够缩短展开后的链长，减少点加和3P 运算次数。将对称三进制应用到标量乘运算中，具体的标量乘算法可参考文献[3].在对称三进制标量乘算法中，每轮迭代中只有当k_i ≠ 0时，才执行点加运算，而根据对称三进制的展开式，非零数出现的概率为2/3，因此其运算代价为n (T + 2A/3), 其中A 表示点加的运算代价，T 表示3P 的运算代价。

为提高标量乘的安全性，使其能够抵御简单能量攻击(simple power analysis, SPA)，通过增加标量乘算法的运算量，文献[18]提出了一种可抵御SPA攻击的对称三进制标量乘算法。将本文提出的点加和3P 运算公式与文献[18]算法相结合，可优化标量乘算法的效率，如算法4。

在算法4中，每轮循环都需要执行一次Co_Z 点加和一次3P 运算，因此整个标量乘算法的运算量为n(A+T)。文献[18]中的可抵御SPA攻击的对称三进制标量乘算法采用的是仿射坐标系，每轮循环运算量为2I+ 5S+ 9M，这里求逆与域乘的运算量之比为8。由于在算法4中引入了Co_Z 点加算法，减少了每轮循环中点加和3P 运算所需的M、S计算次数，因此提高了运算效率。

3 运算效率分析

将本文提出的Co_Z 点加、3P 运算公式应用到文献[3]的对称三进制标量乘算法中，比较不同运算公式下的标量乘算法运算效率（见表 1）. 160-bit对称三进制标量乘算法的运算量为101(T + 2A/3)。

在有限域GF (2^m)内，平方运算更加高效，因此在二元域内，可以忽略计算平方(S)的时间^[12]，只比较计算域乘所需要的时间代价。Jacobian射影坐标下，当Co_Z 点加与3P 运算应用到对称三进制标量乘算法中，算法的运算效率提高了12%。若在Jacobian射影坐标和López & Dahab射影坐标下均使用Co_Z 点加运算公式，则对称三进制标量乘算法在Jacobian射影坐标的运算效率要比López & Dahab射影坐标下提高8%。

在160-bit下，对称三进制标量乘算法的运算量为101(T + A )。表 2给出了使用不同点加、3P 运算公式时，可抵御SPA攻击对称三进制标量乘算法的运算量。在Jacobian射影坐标下，改进后的点加、3P运算公式后得到的运算量为2020M+606S，此即为算法4的运算量。

当引用Co_Z 操作后，López & Dahab射影坐标下的点加运算量由10M+5S降至10M+3S；Jacobian射影坐标下的点加运算量由10M+3S降至8M+3S。新提出的Jacobian射影坐标下3P运算公式比之前的少了1M+4S。由表 2可知，Jacobian射影坐标下，结合了Co_Z点加和改进后的3P运算的算法4的运算效率，相比使用改进前的点加、3P运算公式的可抵御SPA攻击对称三进制标量乘算法提高了13%(只比较计算域乘所需要的时间代价)。

4 结论

本文对有限域GF (2^m)内的点加、3P 运算公式进行改进，使得运算过程中的域乘、域平方计算次数得到减少。当引入Co_Z 思想后，通过统一输入点的Z 坐标，López & Dahab射影坐标下Co_Z 点加运算量降低了2S；Jacobian射影坐标下Co_Z 点加运算量降低了2M。此外，当输入点的Z 轴特殊化处理为1后，Jacobian射影坐标下3P 运算量减少了1M+ 4S，都有不同程度的效率提高。将提出的Co_Z 点加、3P 运算公式与可抵御SPA攻击的标量乘算法相结合，提出一种Co_Z 对称三进制标量乘算法，使得标量乘算法的运算效率提高了13%。下一步，可选取合适的椭圆曲线，将Co_Z 点加与曲线相结合，提出更高效的标量乘算法，使其能应用到具体的硬件环境中。