橢圓曲線的純量乘法

橢圓曲線點的乘法也稱為橢圓曲線的純量乘法，是將橢圓曲線上的一點反覆和自身相加的運算。此運算在橢圓曲線密碼學中可以用來產生單向函式。此條目中將這種乘法用標量乘法來表示，再配合。此運算也稱為橢圓曲線點的乘法。基礎.假定在有限域上定義的曲線"E"，其點乘定義為重覆的進行在曲線上點的加法，表示為"nP""P" + "P" + "P" + … + "P"，其中"n"是係數以及在曲線"E"上的一點"P"("x", "y")，這類的曲線稱為魏爾施特拉斯曲線。現代橢圓曲線密碼學安全性的基礎是在給定"Q"和"P"，以及"Q""nP"的情形下，若"n"很大，無法求得"n"的特性而來會得到第三點，而這個點的位置和前一點或前二點沒有明確的關係，重覆很多次之後，"nP"可能會在曲線上的任何位置。在直覺上，橢圓曲線的純量乘法和以下例子類似：假設在圓上選一個點"P"，再將其角度加上42.57度，所得的點離"P"會有一些距離，不過不會太遠，不過若加上1000次或1001次的42.57度，需要需比較複雜的運算才能求出所得的點的位置。回到橢圓曲線的純量乘法，若要進行逆運算，給定"Q=nP"，已知"P"和"Q"，要求"n"，只能一個一個的針對可能的"n"來檢查，若"n"的可能範圍很大的話，這在計算上就是不可行的。點運算.橢圓曲線上的點，一般會定義三種運算：相加、加倍和反相。無窮遠點.無窮遠點}是橢圓曲線算術中的單位元。任意點和此點相加，相加前和相加後的結果不變。若無窮遠點加上無窮遠點，結果仍為無窮遠點。也就是：formula_1無窮遠點也會寫成0.反相.點的反相是指標對某一個點，可以找到另一個點，與其相加後為無窮遠點。formula_2在橢圓曲線上，一點反相點的"x"座標會和該點相同，而"y"座標會為該點座標的負值：formula_3點的相加.針對二個相異點"P"和"Q"，其加法定義為"P"和"Q"所形成的直線，和曲線"E"交點的反相點"R".formula_4假設橢圓曲線的方程式是"y"2"x"3 + "ax" + "b"，可以計算得到：formula_5若其中沒有任何一點是無窮遠點}，且這些點的x座標都不同，則上式正確。這在橢圓曲線數字簽名演算法有可能為0。點的加倍.假設點"P"和"Q"重合，其加法類似，但無法依上述方式定義直線，因此使用極限的作法，取曲線"E"在"P"點的切線。計算同上，取導數(dE/dx)/(dE/dy)可得：formula_6其中"a"是方程式"E"裡的係數。點乘法.最直接計算點乘法的方式就是反覆的執行加法。不過也有其他更有效率的演算法。Double-and-add.最簡單的方式就是double-and-add法，其作法類似模乘冪中的平方求冪。其演演算法如下：要計算"sP"，要先將"s"以二進製表示，其中：以下是迭代演演算法，其迴圈變數i遞減：let bits = bit_representation #為s的二進製表示let res = formula_7 #無窮遠點for bit in bits:res = res + res # doubleif bit == 1:res = res + P # addi = i - 1return res因Double和add的執行時間不同，根據執行時間就可以知道是執行Double或add，間接可以推算"d"，在資訊安全上，此方法會有的風險。以下的蒙哥馬利階梯是可以避免計時攻擊的作法。以下則是使用遞迴函式的作法：f(P, d) isif d = 0 thenreturn 0 # 已計算完成else if d = 1 thenreturn Pelse if d mod 2 = 1 thenreturn point_add(P, f(P, d - 1)) # 若d為奇數，進行additionelsereturn 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和蒙哥馬利階梯法。視窗法.此演演算法的視窗法版本可以選擇視窗大小w，再計算所有的formula_8，formula_9。演演算法會使用的表示法為formula_10 ，其程式是Q ← 0for i from m to 0 doQ ← point_double_repeat(Q, w)if di &gt; 0 thenQ ← point_add(Q, diP) # using pre-computed value of diPreturn Q演演算法的複雜度和Double-and-add相同，但其點相加使用的較少。一般來說，會選擇 "w" 為夠小的值，簡化預運算的步驟。若針對NIST建議的曲線，一般來說formula_11會是最好的選擇。"n"位元整數的複雜度會是formula_12個點加倍，formula_13個點相加。滑動視窗法.滑動視窗法會在點相加和點加倍之間取捨，計算的表格類似視窗法，不過只計算formula_8， formula_15。此方式比較有效率，只計算有設定MSB的那些值。而其演演算法使用原始double-and-add的表示法formula_16。Q ← 0for i from m downto 0 doif di = 0 thenQ ← point_double(Q)elset ← extract j (up to w − 1) additional bits from d (including di)i ← i − jif j = 2w−1return (d mod 2w) − 2welsereturn d mod 2w因此會需要用NAF來進行乘法。此演演算法會需要先計算formula_20這些點，以及這些點的負值。若是標準的Weierstrass曲線，若formula_22，可得formula_23。因此負值很容易計算。接下來要計算formula_8的乘法：Q ← 0for j ← i − 1 downto 0 doQ ← point_double(Q)if (dj != 0)Q ← point_add(Q, djP)return QwNAF方式可以保證平均來說點相加法的密度會是formula_25，其中的預計算會需要一個點加倍及formula_26個點加法。而演演算法剩下的部份需要formula_27個點加倍，以及formula_28個點加法。NAF的一個特性是可以保證每一個非零元素formula_29之後，至少有formula_30個零。其原因是因為演演算法在每次計算mods函式後，會清除數字formula_19中，較低的formula_32個位元。在每一個非零元素後面，就會有一定數量的零位元，這些零位元可以不用儲存。已有人發現，若針對OpenSSL進行FLUSH+RELOAD的旁路攻擊，約在進行200次簽章後，即可以利用cache-timing找到完整私鑰。蒙哥馬利階梯法.蒙哥馬利階梯法會用固定的運算時間來進行點乘法，運算時間只會隨"d"的長度而變化，不會因為"d"的各位元內容而變化。這可以抵抗旁路攻擊中的功率攻擊或是計時攻擊。此演演算法的實現方式和double-and-add相同。R0 ← 0R1 ← Pfor i from m downto 0 doif di = 0 thenR1 ← point_add(R0, R1)R0 ← point_double(R0)elseR0 ← point_add(R0, R1)R1 ← point_double(R1)return R0此演演算法的速度類似double-and-add，但是在處理"d"的每一位元時，都會進行點相加以及點加倍。因此演演算法本身不會因為時間或是功率而洩漏"d"的資料。不過若利用旁路攻擊中的FLUSH+RELOAD對OpenSSL進行攻擊，已證實只需要經由一次簽名，用cache計時攻擊，以很低的成本得到完整的私鑰。