橢圓曲線點的乘法也稱為橢圓曲線的純量乘法，是將椭圆曲线上的一點反覆和自身相加的運算。此運算在椭圆曲线密码学（ECC）中可以用來產生單向函數。
此條目中將這種乘法用标量乘法來表示，再配合。此運算也稱為橢圓曲線點的乘法（elliptic curve point multiplication），不過此名稱有時會誤解為二個點之間的乘法（其實是整數純量和點的乘法）。
基礎
假定在有限域上定義的曲線E（例如E: ），其點乘定義為重覆的進行在曲線上點的加法，表示為，其中n是係數（整數）以及在曲線E上的一點，這類的曲線稱為魏尔施特拉斯曲線（Weierstrass curve）。
現代橢圓曲線密碼學安全性的基礎是在給定Q和P，以及的情形下，若n很大，無法求得n的特性而來（類似其他的迪菲-赫爾曼密鑰交換問題，此問題稱為橢圓曲線離散對數問題）。此原因是因為橢圓曲線上兩點的相加（或是某一個點加上自身）會得到第三點，而這個點的位置和前一點或前二點沒有明確的關係，重覆很多次之後，nP可能會在曲線上的任何位置。在直覺上，橢圓曲線的純量乘法和以下例子類似：假設在圓上選一個點P，再將其角度加上42.57度，所得的點離P會有一些距離，不過不會太遠，不過若加上1000次或1001次的42.57度，需要需比較複雜的運算才能求出所得的點的位置。回到橢圓曲線的純量乘法，若要進行逆運算，給定Q=nP，已知P和Q，要求n，只能一個一個的針對可能的n來檢查，若n的可能範圍很大的話，這在計算上就是不可行的。
點運算
橢圓曲線上的點，一般會定義三種運算：相加、加倍和反相。
無窮遠點
無窮遠點{{tmath|\mathcal{O} }}是橢圓曲線算術中的單位元。任意點和此點相加，相加前和相加後的結果不變。若無窮遠點加上無窮遠點，結果仍為無窮遠點。
也就是：
:\begin{align}
\mathcal{O} + \mathcal{O} = \mathcal{O}\\
\mathcal{O} + P = P
\end{align}
無窮遠點也會寫成.
反相
點的反相是指針對某一個點，可以找到另一個點，與其相加後為無窮遠點（{{tmath|\mathcal{O} }}）。
:\begin{align}
P + (-P) = \mathcal{O}
\end{align}
在橢圓曲線上，一點反相點的x座標會和該點相同，而y座標會為該點座標的負值：
:\begin{align}
(x, y) + (-(x, y)) &= \mathcal{O}\\
(x, y) + (x, -y) &= \mathcal{O}\\
(x, -y) &= -(x, y)
\end{align}
點的相加
針對二個相異點P和Q，其加法定義為P和Q所形成的直線，和曲線E交點的反相點R.
:\begin{align}
P + Q &= -R \\
(x_p, y_p) + (x_q, y_q) &= (x_r, y_r)
\end{align}
假設橢圓曲線的方程式是，可以計算得到：
:\begin{align}
\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{align}
若其中沒有任何一點是無窮遠點{{tmath|\mathcal{O} }}，且這些點的x座標都不同，則上式正確。這在椭圆曲线数字签名算法（ECDSA）上非常重要，因為散列值（hash）有可能為0。
點的加倍
假設點P和Q重合（座標相同），其加法類似，但無法依上述方式定義直線，因此使用極限的作法，取曲線E在P點的切線。
計算同上，取導數(dE/dx)/(dE/dy)可得，其作法類似模乘幂中的平方求幂。其演算法如下：
要計算sP，要先將s以二進制表示，其中{{tmath|s_0 ~..~ s_m \in \{0, 1\}, m\lfloor \log_2{s} \rfloor }}：
以下是迭代演算法，其迴圈變數i遞減：
let bits = bit_representation #為s的二進制表示（從MSB到LSB）
let res = \begin{align}\mathcal{O}\end{align} #無窮遠點
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可以寫成 *'，需要六個點乘二和二個點加運算，100P等於f(P, 100)*。
此一演算法需要執行log2(d)個運算（點乘二或點加）。有許多演算法是以此為基礎來進行的修改，例如窗口法、滑動窗口法、NAF、NAF-w、vector chains和蒙哥馬利階梯法。
窗口法
此演算法的窗口法（windowed version）版本。
蒙哥馬利階梯法
蒙哥馬利階梯法（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計時攻擊，以很低的成本得到完整的私鑰。
參考資料
评论 (0)