IA174: Elliptic curve cryptography (ECC)
Special thanks to Vláďa Sedláček for the initial development of the ECC lecture and these slides.
1/22
History of elliptic curves
Elliptic curves have been with us for quite a while:
• First appeared by Diophantus’s Arithmetica in the third century A.D.; later studied by
many mathematicians thanks to the rich algebraic and geometric structure; even used in
the proof of Fermat’s Last Theorem.
• The name comes from their appearance in certain integrals measuring the length of the
arc of an ellipse.
2/22
History of elliptic curves
Elliptic curves have been with us for quite a while:
• First appeared by Diophantus’s Arithmetica in the third century A.D.; later studied by
many mathematicians thanks to the rich algebraic and geometric structure; even used in
the proof of Fermat’s Last Theorem.
• The name comes from their appearance in certain integrals measuring the length of the
arc of an ellipse.
• First practical application in 1984 - Lenstra’s factoring method based on elliptic curves
(still useful today).
• In 1985, Koblitz and Miller propose ECC: very efficient compared to other asymmetric
cryptography primitives - small keys and fast computations; great for small devices.
2/22
Fields
Definition 1: Field
A field is a tuple (F, +, ·), such that:
• (F, +) is an abelian group (called additive) with neutral element 0,
• (F \ {0}, ·) is an abelian group (called multiplicative).
• multiplication distributes over addition: for all a, b, c ∈ F, we have
(a + b) · c = a · c + b · c.
3/22
Fields
Definition 1: Field
A field is a tuple (F, +, ·), such that:
• (F, +) is an abelian group (called additive) with neutral element 0,
• (F \ {0}, ·) is an abelian group (called multiplicative).
• multiplication distributes over addition: for all a, b, c ∈ F, we have
(a + b) · c = a · c + b · c.
Common infinite fields include Q, R, C.
How about finite fields?
3/22
Finite fields
In the previous lectures, we encountered Galois fields, which are finite. E.g. the field of bytes
GF(28
) with xor as addition and the multiplication defined via polynomials.
4/22
Finite fields
In the previous lectures, we encountered Galois fields, which are finite. E.g. the field of bytes
GF(28
) with xor as addition and the multiplication defined via polynomials.
The polynomial-based construction can be used to define a field GF(q) for any prime power
q = pk
. All finite fields are of this form.
4/22
Finite fields
In the previous lectures, we encountered Galois fields, which are finite. E.g. the field of bytes
GF(28
) with xor as addition and the multiplication defined via polynomials.
The polynomial-based construction can be used to define a field GF(q) for any prime power
q = pk
. All finite fields are of this form.
Luckily, when dealing with elliptic curves, we will be dealing only with fields GF(p) for a p
prime. These are isomorphic to Fp = (Zp, +, ·).
4/22
What is an elliptic curve?
Definition 2: Elliptic curve, basic version
Let F be any field and a, b ∈ F such that 4a3
+ 27b2
̸= 0. An elliptic curve over F is
the set of points (x, y) ∈ F2
satisfying the Weierstrass equation
y2
= x3
+ a · x + b,
together with a special “point at infinity” O.
In cryptography, we usually take F = Fp with p ≥ 5 a prime number.
5/22
What is an elliptic curve?
Definition 2: Elliptic curve, basic version
Let F be any field and a, b ∈ F such that 4a3
+ 27b2
̸= 0. An elliptic curve over F is
the set of points (x, y) ∈ F2
satisfying the Weierstrass equation
y2
= x3
+ a · x + b,
together with a special “point at infinity” O.
In cryptography, we usually take F = Fp with p ≥ 5 a prime number.
Innoccent pedagogic lies
For the purposes of this lecture, green text might not always be true, but it is “morally true”.
5/22
Elliptic curves over R
6/22
Elliptic curves over Fp
An elliptic curve over F89 given by y2
= x3
− x. 7/22
Groups from elliptic curves
Each elliptic curve E defines a group (E, +) (typically written in additive notation) where the
group operation + is defined as follows: if E : y2
= x3
+ ax + b, then
(x1, y1) + (x2, y2) = (x3, y3) is defined as follows:
• If x1 ̸= x2, then we compute
m =
y2 − y1
x2 − x1
and put
x3 = m2
− x1 − x2, y3 = −m(x3 − x1) − y1.
• If (x1, y1) = (x2, y2) and y1 ̸= 0 then we compute
m =
3x2
1 + a
2y1
and put
x3 = m2
− 2x1, y3 = −m(x3 − x1) − y1.
8/22
Groups from elliptic curves II
• If x1 = x2 and either y1 ̸= y2 or y1 = y2 = 0, then
(x1, y1) + (x2, y2) = O
• O is the neutral element of the group, i.e. P + O = O + P = P for any point P of the
curve.
These addition formulas work over any field. In practice, we often use other formulas, where we
do not have to distinguish the cases
The EC group is always cyclic or bicyclic (a product of two cyclic groups).
9/22
The group law explained in geometrical terms
Fact: Every line that intersects an elliptic curve in at least two points intersects it in exactly
three points (if counted in the right way).
10/22
The group law explained in geometrical terms
Fact: Every line that intersects an elliptic curve in at least two points intersects it in exactly
three points (if counted in the right way).
If P = Q, we have a tangent instead of a secant.
10/22
The group law explained in geometrical terms
Fact: Every line that intersects an elliptic curve in at least two points intersects it in exactly
three points (if counted in the right way).
If P = Q, we have a tangent instead of a secant.
If the line through P and Q is vertical, then P + Q = O (O is the “vertical direction”).
10/22
Discrete logarithm over elliptic curves
We customarily use additive notation when working with EC groups. That is, a k-fold
application of the group operation + is denoted as
k · P = P + . . . + P
| {z }
k times
The discrete logarithm problem over elliptic groups can then be re-formulated as follows: Given
a group (E, +) defined by an elliptic curve, some point G on the curve (generator of a cyclic
sub-group ⟨G⟩), and a point P = k · G, find k.
11/22
How to choose the right elliptic curve?
. . . is a question we will be dealing with for much of the remainder of this lesson. All elliptic
curves are not created equal.
12/22
The discriminant
. . . allows us to recognize some bad-behaved curves.
Let E : y2
= f (x), where f (x) := x3
+ ax + b. Then
∆(f ) := −(4a3
+ 27b2
)
is the discriminant of f .
13/22
The discriminant
. . . allows us to recognize some bad-behaved curves.
Let E : y2
= f (x), where f (x) := x3
+ ax + b. Then
∆(f ) := −(4a3
+ 27b2
)
is the discriminant of f . Over R, the number of components of E depends on the sign of ∆(f ).
y2
= x3
− x, ∆(f ) > 0 y2
= x3
+ x, ∆(f ) < 0
We have ∆(f ) = 0 iff f has a multiple root. Then E is not an elliptic curve, but a singular one.
13/22
Singular curves
The group law fails for singular curves, as the tangents cannot always be defined.
y2
= x3
(additive reduction)
y2
= x3
+ x2
(multiplicative reduction)
14/22
Singular curves
The group law fails for singular curves, as the tangents cannot always be defined.
y2
= x3
(additive reduction)
y2
= x3
+ x2
(multiplicative reduction)
However, if we remove the problematic point, we get a group isomorphic to either the additive
or the multiplicative group of the underlying field. In the first case, we already saw that the
DLP in (Fp, +) is easy. The second case is the classical finite field crypto in (F⋆
p, ·). Since these
are just degenerate cases, we can view ECC as a direct generalization.
14/22
Group size
The curve E and the point G should be such that |⟨G⟩| obeys the standard requirements on
the hardness of the discrete logarithm problem:
• |⟨G⟩| should be sufficiently large, to prevent DL computation by bruteforcing or, e.g., the
baby-step giant-step algorithm.
• |⟨G⟩| should not be smooth, this is to defend against DL algorithms whose runtime is
dominated by the term exponential in the bitsize of the largest prime factor of |G|
(Pohlig-Hellman algorithm, Pollard’s ρ algorithm for discrete logarithm)
15/22
Group size
The curve E and the point G should be such that |⟨G⟩| obeys the standard requirements on
the hardness of the discrete logarithm problem:
• |⟨G⟩| should be sufficiently large, to prevent DL computation by bruteforcing or, e.g., the
baby-step giant-step algorithm.
• |⟨G⟩| should not be smooth, this is to defend against DL algorithms whose runtime is
dominated by the term exponential in the bitsize of the largest prime factor of |G|
(Pohlig-Hellman algorithm, Pollard’s ρ algorithm for discrete logarithm)
Theorem 1: The Hasse-Weil bound
For any elliptic curve E over Fp, we have
p + 1 − 2
√
p ≤ |E| ≤ p + 1 + 2
√
p.
In practice, we use polynomial-time Schoof’s algorithm to compute the group order.
15/22
Fast DL algorithms for elliptic curves
Known attacks on the ECDLP:
• Anomalous curves (|E| = p, underlying field Fp) admit Smart’s attack - an additive
transfer of the ECDLP into the DL in (Zp, +).
16/22
Fast DL algorithms for elliptic curves
Known attacks on the ECDLP:
• Anomalous curves (|E| = p, underlying field Fp) admit Smart’s attack - an additive
transfer of the ECDLP into the DL in (Zp, +).
• Supersingular curves (|E| = p + 1, underlying field Fp ) and more generally curves with a
low embedding degree r (embedding degree = the multiplicative order of p modulo |E|)
admit the MOV attack - a multiplicative transfer of the ECDLP into the DLP in the
multiplicative group (Z⋆
pr , ·).
16/22
Fast DL algorithms for elliptic curves
Known attacks on the ECDLP:
• Anomalous curves (|E| = p, underlying field Fp) admit Smart’s attack - an additive
transfer of the ECDLP into the DL in (Zp, +).
• Supersingular curves (|E| = p + 1, underlying field Fp ) and more generally curves with a
low embedding degree r (embedding degree = the multiplicative order of p modulo |E|)
admit the MOV attack - a multiplicative transfer of the ECDLP into the DLP in the
multiplicative group (Z⋆
pr , ·).
• That’s it, no other known subexponential ECDLP-specific attacks!
16/22
Fast DL algorithms for elliptic curves
Known attacks on the ECDLP:
• Anomalous curves (|E| = p, underlying field Fp) admit Smart’s attack - an additive
transfer of the ECDLP into the DL in (Zp, +).
• Supersingular curves (|E| = p + 1, underlying field Fp ) and more generally curves with a
low embedding degree r (embedding degree = the multiplicative order of p modulo |E|)
admit the MOV attack - a multiplicative transfer of the ECDLP into the DLP in the
multiplicative group (Z⋆
pr , ·).
• That’s it, no other known subexponential ECDLP-specific attacks!
But remember: in practice, ECC security is not the same thing as ECDLP security...
16/22
Implementation choices
In real-life scenarios, an implementation has many choices to make:
• curve choice
• scalar multiplication algorithm choice,
• addition formula choice,
• point representation choice,
• finite field arithmetic implementation choice,
• random number generator choice (recall the Sony Playstation ECDSA incident),
• the choice of running certain security validations,...
Getting these choices right is very hard in practice; many of them might open you up to
unexpected attacks. Do not try this at home!
17/22
Implementation-specific attacks
Examples of attacks against missing security validations:
• the small subgroup attack - applies when the curve has a composite order; mitigated by
cofactor validation; can be combined with the next two attacks,
18/22
Implementation-specific attacks
Examples of attacks against missing security validations:
• the small subgroup attack - applies when the curve has a composite order; mitigated by
cofactor validation; can be combined with the next two attacks,
18/22
Implementation-specific attacks
Examples of attacks against missing security validations:
• the small subgroup attack - applies when the curve has a composite order; mitigated by
cofactor validation; can be combined with the next two attacks,
• the invalid-curve attack - applies when the attacker is allowed to compute on another curve
(typically only differing in the Weierstrass b coefficient); mitigated by point validation,
18/22
Implementation-specific attacks
Examples of attacks against missing security validations:
• the small subgroup attack - applies when the curve has a composite order; mitigated by
cofactor validation; can be combined with the next two attacks,
• the invalid-curve attack - applies when the attacker is allowed to compute on another curve
(typically only differing in the Weierstrass b coefficient); mitigated by point validation,
• the recent Curveball attack (also known as ChainOfFools) - applies if the attacker can
actually solve a self-generated instance of the ECDLP; mitigated by generator validation...
18/22
Implementation-specific attacks
Examples of attacks against missing security validations:
• the small subgroup attack - applies when the curve has a composite order; mitigated by
cofactor validation; can be combined with the next two attacks,
• the invalid-curve attack - applies when the attacker is allowed to compute on another curve
(typically only differing in the Weierstrass b coefficient); mitigated by point validation,
• the recent Curveball attack (also known as ChainOfFools) - applies if the attacker can
actually solve a self-generated instance of the ECDLP; mitigated by generator validation...
And even if you manage to avoid all of these, there is a huge number of side channel attacks
(using time, electricity, EM radiation, caches, exceptional arithmetic cases,...).
18/22
Curve standardization and trust
In practice, you want to use some standardized curves. But this elicits further questions:
• Who gets to choose them and how?
• Is the process transparent enough?
• How do we know there is no hidden weakness or even a backdoor?
19/22
Curve standardization and trust
In practice, you want to use some standardized curves. But this elicits further questions:
• Who gets to choose them and how?
• Is the process transparent enough?
• How do we know there is no hidden weakness or even a backdoor?
Currently, most of ECC on the Internet still uses the P-256 curve designed by the NSA and
standardized by NIST. It follows the ANSI X9.62 standard, but the choice of the seed was
never explained.
A simplified template for generating verifiably pseudorandom curves over fixed Fp.
This causes some trust issues. 19/22
Modern curves
Two curves that are gaining popularity lately are Curve25519 and its sibling Ed25519, both
designed by Daniel Bernstein. The differ from most of the standard curves in several ways:
• they offer better performance and misuse-resistance, leading to higher practical security;
• the generation process is more transparent;
20/22
Takeaways
The key messages of this lecture:
• ECC is a powerful and effficient way to convert deep algebra and number theory into
strong cryptography.
• ECC offers better performance than RSA or discrete logarithm over plain Z×
p (shorter keys
required to offer the same security level).
• One must be very careful with ECC implementations, there are many pitfalls.
• Curve standardization introduces trust issues.
21/22
Bonus
22/22
Bonus
Just an elliptic curve in disguise!
22/22
Bonus
Just an elliptic curve in disguise! The smallest solution:
apple = 154476802108746166441951315019919837485664325669565431700026634898253202035277999,
banana = 36875131794129999827197811565225474825492979968971970996283137471637224634055579,
pineapple = 4373612677928697257861252602371390152816537558161613618621437993378423467772036. 22/22