HOME

TheInfoList



OR:

Elliptic curve scalar multiplication is the operation of successively adding a point along an
elliptic curve In mathematics, an elliptic curve is a smooth, projective, algebraic curve of genus one, on which there is a specified point . An elliptic curve is defined over a field and describes points in , the Cartesian product of with itself. If ...
to itself repeatedly. It is used in
elliptic curve cryptography Elliptic-curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. ECC allows smaller keys compared to non-EC cryptography (based on plain Galois fields) to provide e ...
(ECC) as a means of producing a
one-way function In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here, "easy" and "hard" are to be understood in the sense of computational complexity theory, spe ...
. The literature presents this operation as
scalar multiplication In mathematics, scalar multiplication is one of the basic operations defining a vector space in linear algebra (or more generally, a module in abstract algebra). In common geometrical contexts, scalar multiplication of a real Euclidean vector by ...
, as written in
Hessian form of an elliptic curve In geometry, the Hessian curve is a plane curve similar to folium of Descartes. It is named after the German mathematician Otto Hesse. This curve was suggested for application in elliptic curve cryptography, because arithmetic in this curve represe ...
. A widespread name for this operation is also elliptic curve point multiplication, but this can convey the wrong impression of being a multiplication between two points.


Basics

Given a curve, ''E'', defined along some equation in a finite field (such as ''E'': ), point multiplication is defined as the repeated addition of a point along that curve. Denote as for some scalar (integer) ''n'' and a point 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 given known values of ''Q'' and ''P'' if ''n'' is large (known as the elliptic curve discrete logarithm problem by analogy to other cryptographic systems). This is because the addition of two points on an elliptic curve (or the addition of one point to itself) yields a third point on the elliptic curve whose location has no immediately obvious relationship to the locations of the first two, and repeating this many times over yields a point ''nP'' that may be essentially anywhere. Intuitively, this is not dissimilar to the fact that if you had a point ''P'' on a circle, adding 42.57 degrees to its angle may still be a point "not too far" from ''P'', but adding 1000 or 1001 times 42.57 degrees will yield a point that requires a bit more complex calculation to find the original angle. Reverting this process, i.e., given ''Q=nP'' and ''P'', and determining ''n'', can only be done by trying out all possible ''n''—an effort that is computationally intractable if ''n'' is large.


Point operations

There are three commonly defined operations for elliptic curve points: addition, doubling and negation.


Point at infinity

Point at infinity is the
identity element In mathematics, an identity element, or neutral element, of a binary operation operating on a set is an element of the set that leaves unchanged every element of the set when the operation is applied. This concept is used in algebraic structures su ...
of elliptic curve arithmetic. Adding it to any point results in that other point, including adding point at infinity to itself. That is: :\begin \mathcal + \mathcal = \mathcal\\ \mathcal + P = P \end Point at infinity is also written as .


Point negation

Point negation is finding such a point, that adding it to itself will result in point at infinity (). :\begin P + (-P) = \mathcal \end For elliptic curves of the form ''E'': , negation is a point with the same ''x'' coordinate but negated ''y'' coordinate: :\begin (x, y) + (-(x, y)) &= \mathcal\\ (x, y) + (x, -y) &= \mathcal\\ (x, -y) &= -(x, y) \end


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''. :\begin P + Q &= R \\ (x_p, y_p) + (x_q, y_q) &= (x_r, y_r) \end Assuming the elliptic curve, ''E'', is given by , this can be calculated as: :\begin \lambda &= \frac \\ x_r &= \lambda^2 - x_p - x_q \\ y_r &= \lambda(x_p - x_r) - y_p \\ \end These equations are correct when neither point is the point at infinity, , and if the points have different x coordinates (they're not mutual inverses). This is important for the ECDSA verification algorithm where the hash value could be zero.


Point doubling

Where the points ''P'' and ''Q'' are coincident (at the same coordinates), addition is similar, except that there is no well-defined straight line through ''P'', so the operation is closed using a limiting case, the tangent to the curve, ''E'', at ''P''. This is calculated as above, taking derivatives (dE/dx)/(dE/dy): :\lambda = \frac 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, there are more efficient approaches to computing the multiplication.


Double-and-add

The simplest method is the double-and-add method, similar to square-and-multiply in modular exponentiation. The algorithm works as follows: To compute ''sP'', start with the binary representation for ''s'': , where . * Iterative algorithm, index increasing: let bits = bit_representation(s) # the vector of bits (from LSB to MSB) representing s let res = \begin\mathcal\end # point at infinity let temp = P # track doubled P val for bit in bits: if bit

1: res = res + temp # point add temp = temp + temp # double return res * Iterative algorithm, index decreasing: let bits = bit_representation(s) # the vector of bits (from LSB to MSB) representing s let i = length(bits)-2 let res = P while(i >= 0): # traversing from second MSB to LSB res = res + res # double if bits

1: res = res + P # add i = i -1 return res Note that both of the iterative methods above are vulnerable to timing analysis. See Montgomery Ladder below for an alternative approach. * Recursive algorithm: f(P, d) is if d = 0 then return 0 # computation complete else if d = 1 then return P else if d mod 2 = 1 then return point_add(P, f(P, d - 1)) # addition when d is odd else return f(point_double(P), d/2) # doubling when d is even where ''f'' is the function for multiplying, ''P'' is the coordinate to multiply, ''d'' is the number of times to add the coordinate to itself. Example: ''100P'' can be written as ' and thus requires six point double operations and two point addition operations. ''100P'' would be equal to ''f(P, 100)''. This algorithm requires log2(''d'') 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 2^w values of dP for d = 0, 1, 2, \dots, 2^w - 1. The algorithm now uses the representation d = d_0 + 2^wd_1 + 2^d_2 + \cdots + 2^d_m and becomes 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 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, w = 4 is usually the best selection. The entire complexity for a ''n''-bit number is measured as n + 1 point doubles and 2^w - 2 + \tfrac point additions.


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 dP for d = 2^, 2^ + 1, \dots, 2^w - 1. Effectively, we are only computing the values for which the most significant bit of the window is set. The algorithm then uses the original double-and-add representation of d = d_0 + 2d_1 + 2^2d_2 + \cdots + 2^md_m. 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 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, except that the former can be implemented in constant time. The algorithm requires w - 1 + n point doubles and at most 2^ - 1 + \tfrac point additions.


-ary non-adjacent form (NAF) 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 d must be computed first with the following algorithm 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) Where the signed modulo function ''mods'' is defined as if (d mod 2w) >= 2w−1 return (d mod 2w) − 2w else return d mod 2w This produces the NAF needed to now perform the multiplication. This algorithm requires the pre-computation of the points \lbrace 1, 3, 5, \dots, 2^ - 1 \rbrace P and their negatives, where P is the point to be multiplied. On typical Weierstrass curves, if P = \lbrace x, y \rbrace then -P = \lbrace x, -y \rbrace. So in essence the negatives are cheap to compute. Next, the following algorithm computes the multiplication dP: Q ← 0 for j ← i − 1 downto 0 do Q ← point_double(Q) if (dj != 0) Q ← point_add(Q, djP) return Q The wNAF guarantees that on average there will be a density of \tfrac point additions (slightly better than the unsigned window). It requires 1 point doubling and 2^ - 1 point additions for precomputation. The algorithm then requires n point doublings and \tfrac point additions for the rest of the multiplication. One property of the NAF is that we are guaranteed that every non-zero element d_i is followed by at least w - 1 additional zeroes. This is because the algorithm clears out the lower w bits of d with every subtraction of the output of the ''mods'' function. This observation can be used for several purposes. After every non-zero element the additional zeroes can be implied and do not need to be stored. Secondly, the multiple serial divisions by 2 can be replaced by a division by 2^w after every non-zero d_i element and divide by 2 after every zero. It has been shown that through application of a FLUSH+RELOAD side-channel attack on OpenSSL, the full private key can be revealed after performing cache-timing against as few as 200 signatures performed.


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 In computer security, a side-channel attack is any attack based on extra information that can be gathered because of the fundamental way a computer protocol or algorithm is implemented, rather than flaws in the design of the protocol or algorit ...
. 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 R0 This 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 on OpenSSL, the full private key can be revealed after performing cache-timing against only one signature at a very low cost. Java Code for Montgomery Ladder: /** * EC Multiplication algorithm using the Montgomery Ladder approach to mitigate * timing side channel attacks. Mostly constructed around * https://eprint.iacr.org/2014/140.pdf pg 4 * 2R here is defined as a call to the addition method. * * @param theS scalar value to multiply by. S is a private key * and should be kept secret. * @return Curve.E521 point which is result of multiplication. */ public E521 multiplyMontgomery(final BigInteger theS, final E521 P)


References

{{Reflist Elliptic curves