橢圓曲線的純量乘法

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

基礎

假定在有限域上定義的曲線E（例如E: y² = x³ + 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的可能範圍很大的話，這在計算上就是不可行的。

點運算

橢圓曲線的點乘法：相加（圖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.

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

假設橢圓曲線的方程式是y² = x³ + 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}$, where $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

在資訊安全上，此方法會容易受到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)個運算（點乘二或點加）。有許多演算法是以此為基礎來進行的修改，例如window、sliding window、NAF、NAF-w、vector chains和Montgomery ladder。