CS 355: Topics in Cryptography Spring 2019

Lecture 12: Elliptic Curves

Dima Kogan

1 Why Elliptic Curves?

We use discrete log based assumptions such as DLog, CDH, and DDH all over cryptography. When Diffie
and Hellman first proposed the Diffie-Hellman key exchange protocol, the group that they proposed
was the multiplicative group G = (F∗p , ×) for p prime. The group F∗p is very simple and the discrete log
problem is conjectured to be hard. However, the discrete log problem is not as hard as we would p like 3
in that there are subexponential time algorithms that solve discrete log in F∗p in time roughly 2O( log p) .
e

Hence, to get λ = 128 bits of security, NIST proposes people to use 3092 bit modulus p. This means that
the representation of each group element must be at least 3092 bits, and the algebraic operations must
operate on 3092 bit numbers, which is not ideal.
Since Diffie and Hellman published their papers, people started searching for other groups to use
for the Diffie-Hellman protocol. They were looking for groups for which: (i) the group elements have
compact representation ;(ii) the group operation can be implemented efficiently, and (iii) the discrete-log
problem is hard. Ideally, the best discrete-log algorithm on the group should be no better than the generic
algorithms (e.g., Pollard Rho).
Most groups that people came up with either had easy discrete log problem or did not provide any
real advantage in terms of efficiency over F∗p .
In 1985 Neal Koblitz [1] and Victor S. Miller [2], inspired by an earlier work by Lenstra1 , independently
suggested using the group of points on an elliptic curve as an alternative to F∗p for key exchange.
An elliptic curve is basically a formula of the following form:

y 2 = x 3 + Ax + B.

Let Fp be a finite field. Then, the elliptic curve group that people use for cryptography is the set

E A,B (Fp ) = (x, y) ∈ Fp : y 2 = x 3 + Ax + B ∪ {O } ,

© ª

where O is a special point called point in infinity (we will see why). We can define a suitable group
operation such that the set above is a group. In this group, the best attack on the discrete log problem runs
p
in O( p). Hence, to get λ = 128 bits of security, we just need to use a 256 bit prime. Note that each group
element consists of two field elements x, y ∈ Fp , which means that it only requires 512 bits to represent
them. With optimization, each group element can be represented by ≈ 256 bits.

2 Where do Elliptic Curves come from?

Throughout history, mathematicians have been interested in finding solutions to equations (or points on
curves) of certain properties:
1 Lenstra used elliptic curves for cryptanalysis: he gave a new factoring algorithm for F∗ using elliptic curves [3].
p
 • Find rational solutions (x, y) ∈ Q × Q such that x 2 + y 2 = 1. This question was studied by Pythagoras.

• Find integer solutions (x, y, z) ∈ Z × Z × Z such that x 3 + y 3 = z 3 . The famous Fermat’s Last Theorem
says that there does not exist any positive integer solutions to this equation.

• Find rational solutions (x, y) ∈ Q × Q such that y 2 = x 3 − x + 9. This question was studied by Dio-
phantus.

The last question gives rise to the theory of elliptic curves, but for simplicity, let’s look at the first
question, which is simpler but conveys some of the ideas.

2.1 A Simpler Analogue: The Group of Rational Points on The Unit Circle
Observe that the rational points on the unit circle are in correspondence with Pythagorean triples:
³ a ´2 µ ¶2
b
a 2 + b 2 = c 2 ⇐⇒ + = 1.
c c

Given two rational points (a, b), (c, d ) on the unit circle, we can obtain a new point as following:

(a, b)
(c, d ) = (ac − bd , ad + bc) , 2

and one can easily verify that e 2 + f 2 = 1. The point (1, 0) is an identity element:

(a, b)
(1, 0) = (a, b) ,

and each element has an inverse:

(a, b)
(a, −b) = (a 2 + b 2 , −ab + ab) = (1, 0) .

This group operation also has a geometric construction, as it corresponds to angle addition (see Figure 1),
and the addition law then follows from sine and cosine addition formulas.

Figure 1: The group of rational point on the unit circle.

Image from: F. Lemmermeyer, Pell Conics,
https://www.mathi.uni-heidelberg.de/~flemmermeyer/pell/bfc02.pdf

2 We use a the
symbol to emphasize that this is not addition in Q2 .

3 Elliptic curves over Q
The equation y 2 = x 3 − x + 9 that Diophantus studied is an example of an elliptic curve. Let’s convince
ourselves that finding rational solutions to this equation is not trivial. To find rational solutions to this
equation, the most obvious thing to try is to randomly plug in rational values of x and see if we get rational
values of y.

• If we set x = 0, then we have y 2 = 9. Hence, (0, 3) and (0, −3) are rational solutions to this equation.

• If we set x = 1, then again, we have y 2 = 9. Hence, (1, 3) and (1, −3) are rational solutions to this
equation.
p
• If we set x = 2, then we have y 2 = 15. However, 15 is not a rational number.

In fact, it is easy to check that (−1, ±3), (0, ±3), (1, ±3) are rational solutions to y 2 = x 3 − x + 9, but it is not
clear how to get more rational solutions to this equation. Diophantus asked the following question: Is
there a more systematic way of enumerating all solutions in Q × Q for the equation y 2 = x 3 − x + 9?
Let’s just draw out the curve y 2 = x 3 − x + 9. Elliptic curves generally have the following form.

Diophantus made the following observation:

1. Observation 1: Say you know 2 rational points (x 0 , y 0 ), (x 1 , y 1 ) ∈ Q × Q on the curve. Then, it is

possible to get a third rational point on the curve by drawing a line that intersects the curve at the
two points (x 0 , y 0 ), (x 1 , y 1 ), and finding a third intersecting point (x 2 , y 2 ) on the curve. It turns out
that (x 2 , y 2 ) is also a rational solution contained in Q × Q.

2. Observation 2: Say you know 1 rational point (x, y) ∈ Q × Q on the curve. Then, the point (x, −y) is
also a rational point on the curve.

Diophantus observed that starting from a finite set of points on the curve like (−1, ±3), (0, ±3), (1, ±3), by
incorporating observation 1 and observation 2, one can get many more rational solutions to the equation.
Let us denote Ẽ (Q) ⊂ Q × Q to be the set of all rational solutions to y 2 = x 3 − x + 9, or more generally
y = x 3 + Ax + B . Consider then the addition operation
: Ẽ (Q) × Ẽ (Q) → Ẽ (Q), defined as (1) “draw line”
2
+ (2) “flip y” . Then, it is natural to ask then whether the set Ẽ (Q) under this addition operation forms a
group.
It turns out that it almost does, but we are missing the identity element. If you add a special point O
called the point at ∞, then E (Q) = Ẽ (Q) ∪ {O } forms a group.

• Identity element: by definition, for any point P ∈ E (Q), we have O
P = P
O = P .

• Inverses: for every point P = (x, y) ∈ E (Q), we define −P = (x, −y), and extend our addition rule such
that P
(−P ) = O . (Indeed our “draw line & flip” rule is not well-defined for P
(−P ) since the line
between P and −P does not intersect the curve at a third point.)

• Associativity: it can be shown that for every P,Q, R ∈ E (Q), it holds P
(Q
R) = (P
Q)
R.

The geomtric addition rule can also be expressed algebraically. For example for P = (x 1 , y 1 ),Q =
(x 2 , y 2 ) ∈ E (Q) such that P 6= ±Q and P,Q 6= O , the slope of the line between P and Q is
y2 − y1
m= , (1)
x2 − x1

and the equation of the line is

y = m(x − x 1 ) + y 1 .
To find the intersection with E , substitute into the curve equation:

(m(x − x 1 ) + y 1 )2 = x 3 + Ax + B .

This can be rearranged as:

0 = x3 − m2 x2 + · · · .
This is not easy to solve, but we know two out of the three roots of this degree-three polynomial, namely P
and Q (since they are by definition on the intersection of the line with the curve). And therefore

x 3 − m 2 x 2 + · · · = (x − x 1 )(x − x 2 )(x − x 3 ) = x 3 − (x 1 + x 2 + x 3 )x 2 . . . ,

so
x3 = m 2 − x1 − x2
and
ỹ 3 = m(x 3 − x 1 ) + y 1 .
Reflecting across the x-axis, we get that

P
Q = (x 3 , y 3 ) where x3 = m 2 − x1 − x2 and y 3 = m(x 1 − x 3 ) − y 1 . (2)

The other cases can be handled similarly. For example for P
P we need to take the tangent to the
curve instead of the chord between P and Q.
4 Elliptic Curves Over Finite Fields
Similarly to E (Q), we can consider all points on the curve

E : y 2 = x 3 + Ax + B

over the finite field Fp . This gives rise to the finite group E (Fp ).
For example, consider the curve E : y 2 = x 3 + x + 1 over F5 . Recall that since 5 is a prime, F5 is the set
{0, 1, 2, 3, 4} with addition and multiplication modulo 5.

x x3 + x + 1 y Points
0 1 ±1 (0, 1), (0, 4)
1 3 − −
2 1 ±1 (2, 1), (2, 4)
3 1 ±1 (3, 1), (3, 4)
4 4 ±2 (4, 2), (4, −2)
∞ ∞ O

Thus, E (F5 ) has order 9. We denote |E (F5 )| = 9 (or sometimes #E (F5 ) = 9). We can use the addition formula
from Equations 1 and 2 to compute (3, 1)
(2, 4) on E :
4−1 3
m= = = −3 = 2 (mod 5)
2 − 3 −1
x 3 = 22 − 3 − 2 = 4 y 3 = 2(3 − 4) − 1 = 2 ,

so (3, 1)
(2, 4) = (4, 2).

5 Some important properties

1. The general case we consider is a curve

y 2 = x 3 + Ax + B

where 4A 3 + 27B 2 6= 0. If this condition does not hold, then the curve has a multiple root, and the
curve is called singular.

Figure 2: Singular Elliptic Curves. From: http://mathworld.wolfram.com/EllipticDiscriminant.html

2. The group E (Fp ) is commutative (aka Abelian): P
Q = Q
P for every P,Q ∈ E (Fp ).
 3. Hasse’s Theorem: the order of E (Fp ) satisfies:

|E (Fp )| = p + 1 − t ,
p
where |t | ≤ 2 p. Moreover, it is possible to efficiently compute the order |E (Fp )| using an algorithm
by Schoof.

4. The interesting case from a cryptographic perspective is when |E (Fp )| has a large prime factor and
thus contains a large cyclic subgroup. Such curves can in fact be efficiently generated.

5. For α ∈ N and a point P ∈ E (Fp ), we denote αP := |P
P

{z. . .
P}.
α times

6 Elliptic-Curve Cryptography
Public Parameters. A prime p, parameters A, B ∈ Fp such that E : y 2 = x 3 + Ax + B is an elliptic curve, a
point P ∈ E (Fp ) of large prime order q (i.e., qP = O ), the order q.

Elliptic-Curve Discrete Log. Given P, αP ∈ E (Fp ) where α ←

R
Zq , find α. For most elliptic curves, the best
p
known algorithm for this problem runs in time Ω( q). There are exceptions, so to avoid the pitfall of
choosing an insecure curve, many implementations use a fixed set of curves.

DH Key Exchange. Alice chooses α ← R

Zq , computes and sends Q A = αP . Bob chooses β ←
R
Zq , com-
putes and sends Q B = βP . The shared secret is αβP .

7 Examples of Elliptic Curves Used in Practice

The NIST Curve P256. Standardized by NIST in 1999. All implementations of TLS 1.3 are required to
support this curve for DH key exchange. The curve P256 is defined over the prime p := 2256 − 2224 + 2192 +
296 − 1. The curve has the form y 2 = x 3 − 3x + b where

b := 5ac635d8 aa3a93e7 b3ebbd55 769886bc 651d06b0 cc53b0f6 3bce3c3e 27d2604b.

The standard also specifies a generator point. The parameter b was generated using some public de-
terministic algorithm run on a seed S. We don’t know how S was selected, which some people find
worrying.

Curve 25519. This is another popular curve designed by Dan Bernstein to have additional security
properties. It is defined over the prime p := 2255 − 19, hence its name. This p is the largest prime less than
2255 . The curve has the form:
y 2 = x 3 + 486662x 2 + x .
Notice that this is not in the standard form we have discussed (it has a x 2 term). It is called Montgomery
form which is useful for implementation.
References
[1] N. Koblitz, “Elliptic curve cryptosystems,” Mathematics of computation, vol. 48, no. 177, pp. 203–209,
1987.

[2] V. S. Miller, “Use of elliptic curves in cryptography,” in CRYPTO ’85, 1985.

[3] H. W. Lenstra, “Factoring integers with elliptic curves,” The Annals of Mathematics, vol. 126, no. 3, p.
649, nov 1987. [Online]. Available: https://doi.org/10.2307%2F1971363

[4] S. Kim, “CS355 lecture notes,” 2018, https://crypto.stanford.edu/cs355/18sp/lec14.pdf.

[5] D. Boneh and V. Shoup, “A graduate course in applied cryptography,” 2019. [Online]. Available:
https://crypto.stanford.edu/~dabo/cryptobook/

[6] D. Hankerson, A. J. Menezes, and S. Vanstone, “Guide to elliptic curve cryptography,” Computing
Reviews, vol. 46, no. 1, p. 13, 2005.

[7] T. R. Shemanske, Modern Cryptography and Elliptic Curves: A Beginner’s Guide. American Mathemat-
ical Soc., 2017, vol. 83.

[8] S. D. Galbraith, Mathematics of Public Key Cryptography. Cambridge University Press, 2012. [Online].
Available: https://www.math.auckland.ac.nz/~sgal018/crypto-book/crypto-book.html

[9] A. Sutherland, “Lecture notes on elliptic curves,” 2019, https://math.mit.edu/classes/18.783/2019/

LectureNotes10.pdf.