橢圓曲線點的乘法

**橢圓曲線點的乘法**也稱為**橢圓曲線的純量乘法**，是將橢圓曲線上的一點反覆和自身相加的運算。此運算在橢圓曲線密碼學（ECC）中可以用來產生單向函數。
此條目中將這種乘法用純量乘法來表示，再配合海賽形式的橢圓曲線。此運算也稱為**橢圓曲線點的乘法**（elliptic curve point multiplication），不過此名稱有時會誤解為二個點之間的乘法（其實是整數純量和點的乘法）。

## 基礎

假定在有限域上定義的曲線 _E_（例如 _E_: _y_2 = _x_3 + _ax_ + _b_），其點乘定義為重覆的進行在曲線上點的加法，表示為 _nP_ = _P_ + _P_ + _P_ + … + _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_ 的可能範圍很大的話，這在計算上就是不可行的。

## 點運算

橢圓曲線上的點，一般會定義三種運算：相加、加倍和反相。

### 無窮遠點

無窮遠點 ${\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_.

　
: ${\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) 可得：

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

其中 _a_ 是方程式 _E_ 裡的係數。

## 點乘法

最直接計算點乘法的方式就是反覆的執行加法。不過也有其他更有效率的算法。

### Double-and-add

最簡單的方式就是 double-and-add 法，其作法類似模乘冪中的平方求冪。其演算法如下：

要計算 _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_，在資訊安全上，此方法會有計時攻擊的風險。以下的蒙哥馬利階梯（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)_。

此一演算法需要執行 log2(_d_) 個運算（點乘二或點加）。有許多演算法是以此為基礎來進行的修改，例如窗口法、滑動窗口法、NAF、NAF-w、vector chains 和蒙哥馬利階梯法。

### 窗口法

此演算法的窗口法（windowed version）版本可以選擇窗口大小 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 di > 0 then
          Q ← point_add(Q, diP) # using pre-computed value of diP
  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 di = 0 then
          Q ← point_double(Q)
      else 
          t ← extract j (up to w − 1) additional bits from d (including di)
          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 非相鄰形式（wNAF）方法

非相鄰形式（NAF）的目的是利用點相減的方式和點相加的方式相同的原理，設法使運算量少於滑動窗口法（頂多也只會和滑動窗口法相同）。被乘數 $d$ 的 NAF 方式需要先用以下演算法進行計算

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

其中有號餘數函數 mods 定義如下

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

因此會需要用 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 (dj != 0)
           Q ← point_add(Q, djP)
   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 找到完整私鑰。

### 蒙哥馬利階梯法

蒙哥馬利階梯法（Montgomery ladder）會用固定的運算時間來進行點乘法，運算時間只會隨 _d_ 的長度而變化，不會因為 _d_ 的各位元內容而變化。這可以抵抗旁路攻擊中的功率攻擊或是計時攻擊。此演算法的實現方式和 double-and-add 相同。

```
  R0 ← 0
  R1 ← P
  for i from m downto 0 do
      if di = 0 then
          R1 ← point_add(R0, R1)
          R0 ← point_double(R0)
      else
          R0 ← point_add(R0, R1)
          R1 ← point_double(R1)
  return R0
```

此演算法的速度類似 double-and-add，但是在處理 _d_ 的每一位元時，都會進行點相加以及點加倍。因此演算法本身不會因為時間或是功率而洩漏 _d_ 的資料。
不過若利用旁路攻擊中的 FLUSH+RELOAD 對 OpenSSL 進行攻擊，已證實只需要經由一次簽名，用 cache 計時攻擊，以很低的成本得到完整的私鑰。

## 參考資料