橢圓曲線的純量乘法
橢圓曲線點的乘法也稱為橢圓曲線的純量乘法,是將橢圓曲線上的一點反覆和自身相加的運算。此運算在橢圓曲線密碼學(ECC)中可以用來產生單向函數。 此條目中將這種乘法用純量乘法來表示,再配合海賽形式的橢圓曲線。此運算也稱為橢圓曲線點的乘法(elliptic curve point multiplication),不過此名稱有時會誤解為二個點之間的乘法(其實是整數純量和點的乘法)。
基礎
[編輯]假定在有限域上定義的曲線E(例如E: y2 = x3 + 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的可能範圍很大的話,這在計算上就是不可行的。
點運算
[編輯]![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/c1/ECClines.svg/600px-ECClines.svg.png)
橢圓曲線上的點,一般會定義三種運算:相加、加倍和反相。
無窮遠點
[編輯]無窮遠點是橢圓曲線算術中的單位元。任意點和此點相加,相加前和相加後的結果不變。若無窮遠點加上無窮遠點,結果仍為無窮遠點。
也就是:
無窮遠點也會寫成0.
反相
[編輯]點的反相是指針對某一個點,可以找到另一個點,與其相加後為無窮遠點()。
在橢圓曲線上,一點反相點的x座標會和該點相同,而y座標會為該點座標的負值:
點的相加
[編輯]針對二個相異點P和Q,其加法定義為P和Q所形成的直線,和曲線E交點的反相點R.[1]
假設橢圓曲線的方程式是y2 = x3 + ax + b,可以計算得到:
若其中沒有任何一點是無窮遠點,且這些點的x座標都不同,則上式正確。這在橢圓曲線數字簽名算法(ECDSA)上非常重要,因為散列值(hash)有可能為0。
點的加倍
[編輯]假設點P和Q重合(座標相同),其加法類似,但無法依上述方式定義直線,因此使用極限的作法,取曲線E在P點的切線。
計算同上,取導數(dE/dx)/(dE/dy)可得[1]:
其中a是方程式E裏的系數。
點乘法
[編輯]最直接計算點乘法的方式就是反覆的執行加法。不過也有其他更有效率的算法。
Double-and-add
[編輯]最簡單的方式就是double-and-add法[2],其作法類似模乘冪中的平方求冪。其演算法如下:
要計算sP,要先將s以二進制表示,其中:
以下是迭代演算法,其迴圈變數i遞減:
let bits = bit_representation #為s的二進制表示(從MSB到LSB)
let res = #無窮遠點
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)版本[2]可以選擇窗口大小w,再計算所有的,。演算法會使用的表示法為 ,其程式是
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建議的曲線,一般來說會是最好的選擇。n位元整數的複雜度會是個點加倍,個點相加。
滑動窗口法
[編輯]滑動窗口法(Sliding-window method)會在點相加和點加倍之間取捨,計算的表格類似窗口法,不過只計算, 。此方式比較有效率,只計算有設定MSB的那些值。而其演算法使用原始double-and-add的表示法。
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-ary非相鄰形式(wNAF)方法
[編輯]非相鄰形式(NAF)的目的是利用點相減的方式和點相加的方式相同的原理,設法使運算量少於滑動窗口法(頂多也只會和滑動窗口法相同)。被乘數的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來進行乘法。此演算法會需要先計算(其中是要乘的數)這些點,以及這些點的負值。若是標準的Weierstrass曲線,若,可得。因此負值很容易計算。接下來要計算的乘法:
Q ← 0 for j ← i − 1 downto 0 do Q ← point_double(Q) if (dj != 0) Q ← point_add(Q, djP) return Q
wNAF方式可以保證平均來說點相加法的密度會是(比無號的窗口法好一點),其中的預計算會需要一個點加倍及個點加法。而演算法剩下的部份需要個點加倍,以及個點加法。
NAF的一個特性是可以保證每一個非零元素之後,至少有個零。其原因是因為演算法在每次計算mods函數後,會清除數字中,較低的個位元。在每一個非零元素後面,就會有一定數量的零位元,這些零位元可以不用儲存。
已有人發現,若針對OpenSSL進行FLUSH+RELOAD的旁路攻擊,約在進行200次簽章後,即可以利用cache-timing找到完整私鑰[3]。
蒙哥馬利階梯法
[編輯]蒙哥馬利階梯法(Montgomery ladder)[4]會用固定的運算時間來進行點乘法,運算時間只會隨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計時攻擊,以很低的成本得到完整的私鑰[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 [2022-12-13]. ISBN 978-3-662-44708-6. doi:10.1007/978-3-662-44709-3_5. (原始內容存檔 (PDF)於2022-12-13).
- ^ 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).