Elliptic curve point multiplication is the operation of successively adding a point along an elliptic curve to itself repeatedly. It is used in elliptic curve cryptography (ECC) as a means of producing a trapdoor function. The literature presents this operation as scalar multiplication, thus the most common name is elliptic curve scalar multiplication, as written in Hessian form of an elliptic curve.
Contents
Basics
Given a curve, E, defined along some equation in a finite field (such as E: y2 = x3 + ax + b), point multiplication is defined as the repeated addition of a point along that curve. Denote as nP = P + P + P + … + P for some scalar (integer) n and a point P = (x, y) that lies on the curve, E. This type of curve is known as a Weierstrass curve.
The security of modern ECC depends on the intractability of determining n from Q = nP given known values of Q and P. It is known as the elliptic curve discrete logarithm problem.
Point addition
With 2 distinct points, P and Q, addition is defined as the negation of the point resulting from the intersection of the curve, E, and the straight line defined by the points P and Q, giving the point, R.
Assuming the elliptic curve, E, is given by y2 = x3 + ax + b, this can be calculated as:
Point doubling
Where the points, P and Q, are coincident, addition is similar, except that there is no well-defined straight line through P and Q, so the operation is closed using limiting case, the tangent to the curve, E, at P and Q.
This is calculated as above, except with:
where a is from the defining equation of the curve, E, above.
Point multiplication
The straightforward way of computing a point multiplication is through repeated addition. However, this is a fully exponential approach to computing the multiplication.
Double-and-add
The simplest method is the double-and-add method, similar to multiply-and-square in modular exponentiation. The algorithm works as follows:
To compute dP, start with the binary representation for d:
There are two possible iterative algorithms.
Iterative algorithm, index increasing:
N ← P Q ← 0 for i from 0 to m do if di = 1 then Q ← point_add(Q, N) N ← point_double(N) return QIterative algorithm, index decreasing:
Q ← 0 for i from m down to 0 do Q ← point_double(Q) if di = 1 then Q ← point_add(Q, P) return QAn alternative way of writing the above as a recursive function is
f(P, n) is if n = 0 then return 0 # computation complete else if n = 1 then return P else if n mod 2 = 1 then return point_add(P, f(P, n - 1)) # addition when n is odd else return f(point_double(P), n/2) # doubling when n is evenwhere f is the function for doubling, P is the coordinate to double, n is the number of times to double the coordinate. Example: 100P can be written as 2(2[P + 2(2[2(P + 2P)])]) and thus requires six doublings and two additions. 100P would be equal to f(P, 100).
This algorithm requires log2(n) iterations of point doubling and addition to compute the full-point multiplication. There are many variations of this algorithm such as using a window, sliding window, NAF, NAF-w, vector chains, and Montgomery ladder.
Windowed method
In the windowed version of this algorithm, one selects a window size w and computes all
This algorithm has the same complexity as the double-and-add approach with the benefit of using fewer point additions (which in practice are slower than doubling). Typically, the value of w is chosen to be fairly small making the pre-computation stage a trivial component of the algorithm. For the NIST recommended curves,
Sliding-window method
In the sliding-window version, we look to trade off point additions for point doubles. We compute a similar table as in the windowed version except we only compute the points
This algorithm has the benefit that the pre-computation stage is roughly half as complex as the normal windowed method while also trading slower point additions for point doublings. In effect, there is little reason to use the windowed method over this approach. The algorithm requires
w-ary non-adjacent form (wNAF) method
In the non-adjacent form we aim to make use of the fact that point subtraction is just as easy as point addition to perform fewer (of either) as compared to a sliding-window method. The NAF of the multiplicand
Where the mods function is defined as
if (d mod 2w) >= 2w−1 return (d mod 2w) − 2w else return d mod 2wThis produces the NAF needed to now perform the multiplication. This algorithm requires the pre-computation of the points
The wNAF guarantees that on average there will be a density of
One property of the NAF is that we are guaranteed that every non-zero element
Montgomery ladder
The Montgomery ladder approach computes the point multiplication in a fixed amount of time. This can be beneficial when timing or power consumption measurements are exposed to an attacker performing a side-channel attack. The algorithm uses the same representation as from 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 R0This algorithm has in effect the same speed as the double-and-add approach except that it computes the same number of point additions and doubles regardless of the value of the multiplicand d. This means that at this level the algorithm does not leak any information through timing or power. However, it has been shown that through application of a FLUSH+RELOAD side-channel attack, the full private key can be revealed in only one multiplication operation.