椭圆曲线的标量乘法

椭圆曲线点的乘法也称为椭圆曲线的标量乘法，是将椭圆曲线上的一点反复和自身相加的运算。此运算在椭圆曲线密码学（ECC）中可以用来产生单向函数。此条目中将这种乘法用标量乘法来表示，再配合海赛形式的椭圆曲线（英语：Hessian form of an elliptic curve）。此运算也称为椭圆曲线点的乘法（elliptic curve point multiplication），不过此名称有时会误解为二个点之间的乘法（其实是整数标量和点的乘法）。

基础

假定在有限域上定义的曲线E（例如E: $y 2 = x 3 + ax + b$ ），其点乘定义为重复的进行在曲线上点的加法，表示为 $nP = P + P + P + \dots + P$ ，其中n是系数（整数）以及在曲线E上的一点 $P = (x, y)$ ，这类的曲线称为魏尔施特拉斯曲线（Weierstrass curve）。

现代椭圆曲线密码学安全性的基础是在给定Q和P，以及 $Q = nP$ 的情形下，若n很大，无法求得n的特性而来（类似其他的迪菲-赫尔曼密钥交换问题，此问题称为椭圆曲线离散对数问题）。此原因是因为椭圆曲线上两点的相加（或是某一个点加上自身）会得到第三点，而这个点的位置和前一点或前二点没有明确的关系，重复很多次之后，nP可能会在曲线上的任何位置。在直觉上，椭圆曲线的标量乘法和以下例子类似：假设在圆上选一个点P，再将其角度加上42.57度，所得的点离P会有一些距离，不过不会太远，不过若加上1000次或1001次的42.57度，需要需比较复杂的运算才能求出所得的点的位置。回到椭圆曲线的标量乘法，若要进行逆运算，给定Q=nP，已知P和Q，要求n，只能一个一个的针对可能的n来检查，若n的可能范围很大的话，这在计算上就是不可行的。

点运算

椭圆曲线的点乘法：相加（图1）、加倍（图2和图4）和反相（图3）

椭圆曲线上的点，一般会定义三种运算：相加、加倍和反相。

无穷远点

无穷远点 ${\mathcal {O}}$ 是椭圆曲线算术中的单位元。任意点和此点相加，相加前和相加后的结果不变。若无穷远点加上无穷远点，结果仍为无穷远点。

也就是：

{\begin{aligned}{\mathcal {O}}+{\mathcal {O}}={\mathcal {O}}\\{\mathcal {O}}+P=P\end{aligned}}

无穷远点也会写成 $0$ .

反相

点的反相是指针对某一个点，可以找到另一个点，与其相加后为无穷远点（ ${\mathcal {O}}$ ）。

{\begin{aligned}P+(-P)={\mathcal {O}}\end{aligned}}

在椭圆曲线上，一点反相点的x座标会和该点相同，而y座标会为该点座标的负值：

{\begin{aligned}(x,y)+(-(x,y))&={\mathcal {O}}\\(x,y)+(x,-y)&={\mathcal {O}}\\(x,-y)&=-(x,y)\end{aligned}}

点的相加

针对二个相异点P和Q，其加法定义为P和Q所形成的直线，和曲线E交点的反相点R.^[1]

{\begin{aligned}P+Q&=-R\\(x_{p},y_{p})+(x_{q},y_{q})&=(x_{r},y_{r})\end{aligned}}

假设椭圆曲线的方程式是 $y 2 = x 3 + ax + b$ ，可以计算得到：

{\begin{aligned}\lambda &={\frac {y_{q}-y_{p}}{x_{q}-x_{p}}}\\x_{r}&=\lambda ^{2}-x_{p}-x_{q}\\y_{r}&=\lambda (x_{p}-x_{r})-y_{p}\\\end{aligned}}

若其中没有任何一点是无穷远点 ${\mathcal {O}}$ ，且这些点的x座标都不同，则上式正确。这在椭圆曲线数字签名算法（ECDSA）上非常重要，因为散列值（hash）有可能为0。

点的加倍

假设点P和Q重合（座标相同），其加法类似，但无法依上述方式定义直线，因此使用极限的作法，取曲线E在P点的切线。

计算同上，取导数(dE/dx)/(dE/dy)可得^[1]：

\lambda ={\frac {3x_{p}^{2}+a}{2y_{p}}}

其中a是方程式E里的系数。

点乘法

最直接计算点乘法的方式就是反复的执行加法。不过也有其他更有效率的算法。

Double-and-add

最简单的方式就是double-and-add法^[2]，其作法类似模乘幂中的平方求幂。其算法如下：

要计算sP，要先将s以二进制表示 $s=s_{0}+2s_{1}+2^{2}s_{2}+\cdots +2^{m}s_{m}$ ，其中 $s_{0}~..~s_{m}\in \{0,1\},m=\lfloor \log _{2}{s}\rfloor$ ：

以下是迭代算法，其循环变数i递减：

   let bits = bit_representation #為s的二進制表示（從MSB到LSB）
   let res =  ${\begin{aligned}{\mathcal {O}}\end{aligned}}$  #無窮遠點
   for bit in bits:
       res = res + res # double
       if bit == 1:            
           res = res + P # add
       i = i - 1
   return res

因Double和add的执行时间不同，根据执行时间就可以知道是执行Double或add，间接可以推算d，在资讯安全上，此方法会有计时攻击（英语：timing attack）的风险。以下的蒙哥马利阶梯（Montgomery Ladder）是可以避免计时攻击的作法。

以下则是使用递回函数的作法：

  f(P, d) is
     if d = 0 then
         return 0                         # 已計算完成
     else if d = 1 then
         return P
     else if d mod 2 = 1 then
         return point_add(P, f(P, d - 1)) # 若d為奇數，進行addition
     else
         return f(point_double(P), d/2)   # d為偶數，進行doubling

其中f是乘法的函数，P是要乘的座标，d是要加的次数。例如100P可以写成 2(2[P + 2(2[2(P + 2P)])])，需要六个点乘二和二个点加运算，100P等于f(P, 100)。

此一算法需要执行log₂(d)个运算（点乘二或点加）。有许多算法是以此为基础来进行的修改，例如窗口法、滑动窗口法、NAF、NAF-w、vector chains和蒙哥马利阶梯法。

窗口法

此算法的窗口法（windowed version）版本^[2]可以选择窗口大小w，再计算所有的 $dP$ ， $d=0,1,2,\dots ,2^{w}-1$ 。算法会使用的表示法为 $d=d_{0}+2^{w}d_{1}+2^{2w}d_{2}+\cdots +2^{mw}d_{m}$ ，其程式是

  Q ← 0
  for i from m to 0 do
      Q ← point_double_repeat(Q, w)
      if d_i > 0 then
          Q ← point_add(Q, d_iP) # using pre-computed value of d_iP
  return Q

算法的复杂度和Double-and-add相同，但其点相加使用的较少（实务上，点相加比点加倍要花时间）。一般来说，会选择 w 为够小的值，简化预运算的步骤。若针对NIST建议的曲线，一般来说 $w=4$ 会是最好的选择。n位元整数的复杂度会是 $n+1$ 个点加倍， $2^{w}-2+{\tfrac {n}{w}}$ 个点相加。

滑动窗口法

滑动窗口法（Sliding-window method）会在点相加和点加倍之间取舍，计算的表格类似窗口法，不过只计算 $dP$ ， $d=2^{w-1},2^{w-1}+1,\dots ,2^{w}-1$ 。此方式比较有效率，只计算有设定MSB的那些值。而其算法使用原始double-and-add的表示法 $d=d_{0}+2d_{1}+2^{2}d_{2}+\cdots +2^{m}d_{m}$ 。

  Q ← 0
  for i from m downto 0 do
      if d_i = 0 then
          Q ← point_double(Q)
      else 
          t ← extract j (up to w − 1) additional bits from d (including d_i)
          i ← i − j
          if j < w then
              Perform double-and-add using t 
              return Q
          else 
              Q ← point_double_repeat(Q, w)
              Q ← point_add(Q, tP)
  return Q

此算法的好处是预运算阶段的复杂程度是一般窗口法的一半，也将较慢的点相加改为点加倍。实务上，使用窗口法而不使用滑动窗口法的情形不太多。此算法会使用 $w-1+n$ 次点加倍，最多只用 $2^{w-1}-1+{\tfrac {n}{w}}$ 次点加法。

$w$ -ary非相邻形式（ $w$ NAF）方法

非相邻形式（英语：non-adjacent form）（NAF）的目的是利用点相减的方式和点相加的方式相同的原理，设法使运算量少于滑动窗口法（顶多也只会和滑动窗口法相同）。被乘数 $d$ 的NAF方式需要先用以下算法进行计算

   i ← 0
   while (d > 0) do
       if (d mod 2) = 1 then 
           d_i ← d mods 2^w
           d ← d − d_i
       else
           d_i = 0
       d ← d/2
       i ← i + 1
   return (d_i−1, d_i-2, …, d₀)

其中有号余数函数mods定义如下

   if (d mod 2^w) >= 2^w−1
       return (d mod 2^w) − 2^w
   else
       return d mod 2^w

因此会需要用NAF来进行乘法。此算法会需要先计算 $\lbrace 1,3,5,\dots ,2^{w-1}-1\rbrace P$ （其中 $P$ 是要乘的数）这些点，以及这些点的负值。若是标准的Weierstrass曲线，若 $P=\lbrace x,y\rbrace$ ，可得 $-P=\lbrace x,-y\rbrace$ 。因此负值很容易计算。接下来要计算 $dP$ 的乘法：

   Q ← 0
   for j ← i − 1 downto 0 do
       Q ← point_double(Q)
       if (d_j != 0)
           Q ← point_add(Q, d_jP)
   return Q

wNAF方式可以保证平均来说点相加法的密度会是 ${\tfrac {1}{w+1}}$ （比无号的窗口法好一点），其中的预计算会需要一个点加倍及 $2^{w-2}-1$ 个点加法。而算法剩下的部分需要 $n$ 个点加倍，以及 ${\tfrac {n}{w+1}}$ 个点加法。

NAF的一个特性是可以保证每一个非零元素 $d_{i}$ 之后，至少有 $w-1$ 个零。其原因是因为算法在每次计算mods函数后，会清除数字 $d$ 中，较低的 $w$ 个位元。在每一个非零元素后面，就会有一定数量的零位元，这些零位元可以不用储存。

已有人发现，若针对OpenSSL进行FLUSH+RELOAD的旁路攻击，约在进行200次签章后，即可以利用cache-timing找到完整私钥^[3]。

蒙哥马利阶梯法

蒙哥马利阶梯法（Montgomery ladder）^[4]会用固定的运算时间来进行点乘法，运算时间只会随d的长度而变化，不会因为d的各位元内容而变化。这可以抵抗旁路攻击中的功率攻击或是计时攻击。此算法的实现方式和double-and-add相同。

  R₀ ← 0
  R₁ ← P
  for i from m downto 0 do
      if d_i = 0 then
          R₁ ← point_add(R₀, R₁)
          R₀ ← point_double(R₀)
      else
          R₀ ← point_add(R₀, R₁)
          R₁ ← point_double(R₁)
  return R₀

此算法的速度类似double-and-add，但是在处理d的每一位元时，都会进行点相加以及点加倍。因此算法本身不会因为时间或是功率而泄漏d的资料。不过若利用旁路攻击中的FLUSH+RELOAD对OpenSSL进行攻击，已证实只需要经由一次签名，用cache计时攻击，以很低的成本得到完整的私钥^[5]。

参考资料

^ ^1.0 ^1.1 存档副本. [2021-12-20]. （原始内容存档于2021-12-20）.
^ ^2.0 ^2.1 Hankerson, Darrel; Vanstone, Scott; Menezes, Alfred. Guide to Elliptic Curve Cryptography. Springer Professional Computing. New York: Springer-Verlag. 2004. ISBN 0-387-95273-X. S2CID 720546. doi:10.1007/b97644.
^ Benger, Naomi; van de Pol, Joop; Smart, Nigel P.; Yarom, Yuval. Batina, Lejla; Robshaw, Matthew , 编. "Ooh Aah... Just a Little Bit" : A Small Amount of Side Channel Can Go a Long Way (PDF). Cryptographic Hardware and Embedded Systems – CHES 2014. Lecture Notes in Computer Science 8731. Springer: 72–95. 2014. ISBN 978-3-662-44708-6. doi:10.1007/978-3-662-44709-3_5.
^ Montgomery, Peter L. Speeding the Pollard and elliptic curve methods of factorization. Math. Comp. 1987, 48 (177): 243–264. JSTOR 2007888. MR 0866113. doi:10.2307/2007888  .
^ Yarom, Yuval; Benger, Naomi. Recovering OpenSSL ECDSA Nonces Using the FLUSH+RELOAD Cache Side-channel Attack. IACR Cryptology ePrint Archive. 2014 [2021-12-24]. （原始内容存档于2021-12-05）.

[crypto-1] 1.0 ^1.1 存档副本. [2021-12-20]. （原始内容存档于2021-12-20）.

[guide-2] 2.0 ^2.1 Hankerson, Darrel; Vanstone, Scott; Menezes, Alfred. Guide to Elliptic Curve Cryptography. Springer Professional Computing. New York: Springer-Verlag. 2004. ISBN 0-387-95273-X. S2CID 720546. doi:10.1007/b97644.

[3] Benger, Naomi; van de Pol, Joop; Smart, Nigel P.; Yarom, Yuval. Batina, Lejla; Robshaw, Matthew , 编. "Ooh Aah... Just a Little Bit" : A Small Amount of Side Channel Can Go a Long Way (PDF). Cryptographic Hardware and Embedded Systems – CHES 2014. Lecture Notes in Computer Science 8731. Springer: 72–95. 2014. ISBN 978-3-662-44708-6. doi:10.1007/978-3-662-44709-3_5.

[4] Montgomery, Peter L. Speeding the Pollard and elliptic curve methods of factorization. Math. Comp. 1987, 48 (177): 243–264. JSTOR 2007888. MR 0866113. doi:10.2307/2007888  .

[5] Yarom, Yuval; Benger, Naomi. Recovering OpenSSL ECDSA Nonces Using the FLUSH+RELOAD Cache Side-channel Attack. IACR Cryptology ePrint Archive. 2014 [2021-12-24]. （原始内容存档于2021-12-05）.

[1]

[2]

[3]

[4]

[5]

基础

点运算