椭圆曲线的标量乘法
椭圆曲线点的乘法也称为椭圆曲线的标量乘法,是将椭圆曲线上的一点反复和自身相加的运算。此运算在椭圆曲线密码学(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).