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 the ...
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 to provide equivalent security, compared to cryptosystems based on modula ...
(ECC).
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 ...
, 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 repres ...
. 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 by some equation in a
finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field (mathematics), field that contains a finite number of Element (mathematics), elements. As with any field, a finite field is a Set (mathematics), s ...
(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. Reversing 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 is an element that leaves unchanged every element when the operation is applied. For example, 0 is an identity element of the addition of real numbers. This concept is use ...
of elliptic curve arithmetic. Adding it to any point results in that other point, including adding point at infinity to itself.
That is:
:
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 ().
:
For elliptic curves of the form ''E'': , negation is a point with the same ''x'' coordinate but negated ''y'' coordinate:
:
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 , this can be calculated as:
:
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):
:
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 .
eA
* Iterative algorithm, index increasing:
let bits = bit_representation(s) # the vector of bits (from LSB to MSB) representing s
let res =
# 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:
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 log
2(''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
values of
for
. The algorithm now uses the representation
and becomes
Q ← 0
for i from m to 0 do
Q ← point_double_repeat(Q, w)
if d
i > 0 then
Q ← point_add(Q, d
iP) # using pre-computed value of d
iP
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
In algorithms, precomputation is the act of performing an initial computation before run time to generate a lookup table that can be used by an algorithm to avoid repeated computation each time it is executed. Precomputation is often used in alg ...
stage a trivial component of the algorithm. For the NIST recommended curves,
is usually the best selection. The entire complexity for a ''n''-bit number is measured as
point doubles and
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
for
. 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
.
Q ← 0
for i from m downto 0 do
if d
i = 0 then
Q ← point_double(Q)
else
t ← extract j (up to w − 1) additional bits from d (including d
i)
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
point doubles and at most
point additions.
-ary non-adjacent form (NAF) method
In the
non-adjacent form
The non-adjacent form (NAF) of a number is a unique signed-digit representation, in which non-zero values cannot be adjacent. For example:
:(0 1 1 1)2 = 4 + 2 + 1 = 7
:(1 0 −1 1)2 = 8 − 2 + 1 = 7
:(1 −1 1 1)2 = 8 − 4 + 2 + 1 = 7
:(1 0 0 ...
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
must be computed first with the following algorithm
i ← 0
while (d > 0) do
if (d mod 2) = 1 then
d
i ← d mods 2
w
d ← d − d
i
else
d
i = 0
d ← d/2
i ← i + 1
return (d
i−1, d
i-2, …, d
0)
Where the signed modulo function ''mods'' is defined as
if (d mod 2
w) >= 2
w−1
return (d mod 2
w) − 2
w
else
return d mod 2
w
This produces the NAF needed to now perform the multiplication. This algorithm requires the pre-computation of the points
and their negatives, where
is the point to be multiplied. On typical Weierstrass curves, if
then
. So in essence the negatives are cheap to compute. Next, the following algorithm computes the multiplication
:
Q ← 0
for j ← i − 1 downto 0 do
Q ← point_double(Q)
if (d
j != 0)
Q ← point_add(Q, d
jP)
return Q
The wNAF guarantees that on average there will be a density of
point additions (slightly better than the unsigned window). It requires 1 point doubling and
point additions for precomputation. The algorithm then requires
point doublings and
point additions for the rest of the multiplication.
One property of the NAF is that we are guaranteed that every non-zero element
is followed by at least
additional zeroes. This is because the algorithm clears out the lower
bits of
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
after every non-zero
element and divide by 2 after every zero.
It has been shown that through application of a FLUSH+RELOAD side-channel attack on
OpenSSL
OpenSSL is a software library for applications that provide secure communications over computer networks against eavesdropping, and identify the party at the other end. It is widely used by Internet servers, including the majority of HTTPS web ...
, 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'' number of operations. This can be beneficial when timing, power consumption, or branch measurements are exposed to an attacker performing a
side-channel attack
In computer security, a side-channel attack is a type of security exploit that leverages information inadvertently leaked by a system—such as timing, power consumption, or electromagnetic or acoustic emissions—to gain unauthorized access to ...
. The algorithm uses the same representation as from double-and-add.
R
0 ← 0
R
1 ← P
for i from m downto 0 do
if d
i = 0 then
R
1 ← point_add(R
0, R
1)
R
0 ← point_double(R
0)
else
R
0 ← point_add(R
0, R
1)
R
1 ← point_double(R
1)
// invariant property to maintain correctness
assert R
1 point_add(R
0, P)
return R
0
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 branches or power consumption.
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.
Rust code for Montgomery Ladder:
/// Constant operation point multiplication.
/// NOTE: not memory safe.
/// NOTE: not timing-side channel safe (not constant time).
/// * `s`: scalar value to multiply by
/// * multiplication is defined to be P₀ + P₁ + ... Pₛ
fn sec_mul(&mut self, s: big) -> E521
Constant time Montgomery ladder
The security of a cryptographic implementation is likely to face the threat of the so called
timing attacks
In cryptography, a timing attack is a side-channel attack in which the attacker attempts to compromise a cryptosystem by analyzing the time taken to execute cryptographic algorithms. Every logical operation in a computer takes time to execute, an ...
which exploits the data-dependent timing characteristics of the implementation. Machines running cryptographic
implementations consume variable amounts of time to process different inputs and so the timings
vary based on the encryption key. To resolve this issue, cryptographic algorithms are implemented
in a way which removes data dependent variable timing characteristic from the implementation leading
to the so called constant-time implementations. Software implementations are considered to be constant-time in the
following sense as stated in: “''avoids all input-dependent branches, all input-dependent array''
''indices, and other instructions with input-dependent timings.''” The GitHub page lists coding rules
for implementations of cryptographic operations, and more generally for operations involving secret or
sensitive values.
The Montgomery ladder is an
-coordinate only algorithm for elliptic curve point multiplication
and is based on the double and add rules over a specific set of curves known as
Montgomery curve
In mathematics, the Montgomery curve is a form of elliptic curve introduced by Peter L. Montgomery in 1987, different from the usual Weierstrass form. It is used for certain computations, and in particular in different cryptography applications.
...
. The algorithm has a conditional branching
such that the condition depends on a secret bit. So a straightforward implementation of the ladder won't be
constant time and has the potential to leak the secret bit. This problem has been addressed in literature
and several constant time implementations are known. The constant time Montgomery ladder algorithm is as given below which uses two functions CSwap and Ladder-Step. In the return value of the algorithm Z
2p-2 is the value of Z
2−1 computed using the
Fermat's little theorem
In number theory, Fermat's little theorem states that if is a prime number, then for any integer , the number is an integer multiple of . In the notation of modular arithmetic, this is expressed as
a^p \equiv a \pmod p.
For example, if and , t ...
.
algorithm Montgomery-Ladder(x
P, n) is
input: An
-bit scalar
and the
-coordinate
of a point
.
output:
-coordinate of
, the
-times scalar multiple of
.
X
1 ← x
P; X
2 ← 1; Z
2 ← 0; X
3 ← x
P; Z
3 ← 1
prevbit ← 0
for
from
downto 0 do
bit ← bit-value at index
of
b ← bit
prevbit
prevbit ← bit
(
X
2,Z
2,
X
3,Z
3) ← CSwap(
X
2,Z
2,
X
3,Z
3,b)
(
X
2,Z
2,
X
3,Z
3) ← Ladder-Step(
X
2,Z
2,
X
3,Z
3,X
1)
return X
2Z
2p-2
The Ladder-Step function (given below) used within the ladder is the core of the algorithm and is a combined form of the differential add and doubling operations. The field
constant a
24 is defined as a
24 =
, where
is a parameter of the underlying
Montgomery curve
In mathematics, the Montgomery curve is a form of elliptic curve introduced by Peter L. Montgomery in 1987, different from the usual Weierstrass form. It is used for certain computations, and in particular in different cryptography applications.
...
.
Function Ladder-Step(
X
2,Z
2,
X
3,Z
3,X
1)
T
1 ← X
2 + Z
2
T
2 ← X
2 - Z
2
T
3 ← X
3 + Z
3
T
4 ← X
3 - Z
3
T
5 ← T
12
T
6 ← T
22
T
2 ← T
2 · T
3
T
1 ← T
1 · T
4
T
1 ← T
1 + T
2
T
2 ← T
1 - T
2
X
3 ← T
12
T
2 ← T
22
Z
3 ← T
2 · X
1
X
2 ← T
5 · T
6
T
5 ← T
5 - T
6
T
1 ← a
24 · T
5
T
6 ← T
6 + T
1
Z
2 ← T
5 · T
6
return (
X
2,Z
2,
X
3,Z
3)
The CSwap function manages the conditional branching and helps the ladder to run following the requirements of a constant time implementation. The function swaps the pair of field elements
X
2,Z
2 and
X
3,Z
3 only if
= 1 and
this is done without leaking any information about the secret bit. Various methods of implementing CSwap have been proposed in literature.
A lesser costly option to manage the constant time requirement of the Montgomery ladder is conditional select which is formalised through a function CSelect. This function has been used in various optimisations and has been formally discussed in
Since the inception of the standard Montgomery curve
Curve25519
In cryptography, Curve25519 is an elliptic curve used in elliptic-curve cryptography (ECC) offering 128 bits of security (256-bit key size) and designed for use with the Elliptic-curve Diffie–Hellman (ECDH) key agreement scheme, first described a ...
at 128-bit security level, there has been various software implementations to compute the ECDH on various architectures and to achieve best possible performance cryptographic developers have resorted to write the implementations using assembly language of the underlying architecture. The work provided a couple of 64-bit assembly implementations targeting the AMD64 architecture. The implementations were developed using a tool known as ''qhasm'' which can generate high-speed assembly language cryptographic programs. It is to be noted that the function CSwap was used in the implementations of these ladders. After that there has been several attempts to optimise the ladder implementation through hand-written assembly programs out of which the notion of CSelect was first used in
[, Code available at https://github.com/armfazh/rfc7748_precomputed.] and then in.
[, Code available at https://github.com/kn-cs/x25519] Apart from using sequential instructions, vector instructions have also been used to optimise the ladder computation through various works.
[, Coce available at https://github.com/armfazh/fld-ecc-vec][, Code available at https://github.com/kn-cs/vec-ladder] Along with AMD64, attempts have also been made to achieve efficient implementations on other architectures like ARM. The works and provides efficient implementations targeting the ARM architecture. The libraries lib25519 and are two state-of-art libraries containing efficient implementations of the Montgomery ladder for
Curve25519
In cryptography, Curve25519 is an elliptic curve used in elliptic-curve cryptography (ECC) offering 128 bits of security (256-bit key size) and designed for use with the Elliptic-curve Diffie–Hellman (ECDH) key agreement scheme, first described a ...
. Nevertheless, the libraries have implementations of other cryptographic primitives as well.
Apart from
Curve25519
In cryptography, Curve25519 is an elliptic curve used in elliptic-curve cryptography (ECC) offering 128 bits of security (256-bit key size) and designed for use with the Elliptic-curve Diffie–Hellman (ECDH) key agreement scheme, first described a ...
, there have been several attempts to compute the ladder over other curves at various security levels. Efficient implementations of the ladder over the standard curve
Curve448
In cryptography, Curve448 or Curve448-Goldilocks is an elliptic curve potentially offering 224 bits of security and designed for use with the elliptic-curve Diffie–Hellman (ECDH) key agreement scheme.
History
Developed by Mike Hamburg of Rambus ...
at 224-bit security level have also been studied in literature.
A curve named Curve41417 providing security just over 200 bits was proposed in which a variant of Karatsuba strategy was used to implement the field multiplication needed for the related ECC software. In pursuit of searching Montgomery curves that are competitive to
Curve25519
In cryptography, Curve25519 is an elliptic curve used in elliptic-curve cryptography (ECC) offering 128 bits of security (256-bit key size) and designed for use with the Elliptic-curve Diffie–Hellman (ECDH) key agreement scheme, first described a ...
and
Curve448
In cryptography, Curve448 or Curve448-Goldilocks is an elliptic curve potentially offering 224 bits of security and designed for use with the elliptic-curve Diffie–Hellman (ECDH) key agreement scheme.
History
Developed by Mike Hamburg of Rambus ...
research has been done and couple of curves were proposed along with efficient sequential
and vectorised implementations
of the corresponding ladders. At 256-bit security level efficient implementations of the ladder have also been addressed through three different Montgomery curves.
[, Code available at https://github.com/kn-cs/mont256-dh and https://github.com/kn-cs/mont256-vec]
References
{{Reflist
Elliptic curves
Articles with example Rust code