An Elliptic Curve Modulo a Prime

Take every number modulo a prime, and the curve becomes a grid of points. Add them, multiply a point by a number, and then try to find that number again.

Elliptic curvesDiscrete logarithmdemo

Objectives

List the points of E_23(1, 1) and explain the mirror symmetry between y and p − y.
Compute one point addition modulo p, including the modular inverse in the slope.
Compute kG by double-and-add, run ECDH with two secrets, and explain why finding k from kG is hard when the group is large.

20%

The same curve with every number taken modulo a prime: a grid of points that you can add, multiply, and try to divide.

y^2 = x^3 + ax + b (mod p), 4a^3 + 27b^2 ≠ 0 (mod p)

The points of the curve

a point of the curve
the column x = 3
its points, labelled
the mirror line

Use coordinates modulo a prime p. Now x and y are whole numbers from 0 to p − 1, so the curve is a finite set of points. The default is the toy curve y^2 = x^3 + x + 1 (mod 23), from Stallings, Table 10.1. The addition formulas use modular arithmetic.

prime p

the curve

y^2 = x^3 + 1x + 1 (mod 23)

is it singular?

4a^3 + 27b^2 = 4×1^3 + 27×1^2 = 31 = 8 (mod 23) not zero: the curve is not singular

x, to search one column

x^3 + 1x + 1 = 31 = 8 (mod 23) y^2 = 8 (mod 23) for y = 10 and y = 13. 10 + 13 = 23: each is the mirror of the other.

The page found every point this way: for each x it computes the right side, then tries every y. That is 529 tries for p = 23.

The points come in mirror pairs, (x, y) and (x, p − y), on either side of the dashed line. This is the same mirror as on the real curve: −y modulo p is p − y. Here there are 13 pairs and 1 point with y = 0, which is its own mirror.

how many points

Its 27 plotted points plus O form a group of 28 points. p + 1 = 24. The count is always close to p + 1.

Add two points

P
Q
the line, modulo p
R, the third point
mirror: R to the answer
P+Q, the answer

The rule is the same as on the real curve: the line through P and Q, the third point R, and its mirror image. Modulo p the line is no longer a stroke. It is 23 separate dots, one in each column, and it still passes through P, Q and R.

Pick the same point twice to double it. Pick a point and its mirror image to get O.

the slope, written out

Division modulo p means multiplying by an inverse: the number that gives 1 when you multiply by it, modulo p.

slope s = (y_Q − y_P) / (x_Q − x_P)   mod 23
        = (7 − 10) / (9 − 3)
        = −3 / 6
numerator:    −3 mod 23 = 20
denominator:  6 mod 23 = 6
inverse:      6^-1 mod 23 = 4
              (6 × 4 = 24 = 1 mod 23)
divide = multiply by an inverse:
s = 20 × 6^-1 = 20 × 4 = 80 mod 23 = 11

x = s^2 − x_P − x_Q
  = 11^2 − 3 − 9 = 109 mod 23 = 17
y = s(x_P − x) − y_P
  = 11 × (3 − 17) − 10 = −164 mod 23 = 20

P + Q = (17, 20)
check: 20^2 mod 23 = 9
       17^3 + 1×17 + 1 mod 23 = 9

Multiply a point by a number

G
arrow: add one more G; the newest is thickest
kG, the newest point

Scalar multiplication: kG adds k copies of G, so kG = G + G + … + G. Here k is an ordinary whole number, and G is a point. Add G again and again, and follow the arrows.

starting point G

where the walk is

1G = (3, 10)

Keep adding G. After some number of steps the walk reaches O, the point at infinity, and then it starts again from G. The order of G is the smallest n with nG = O.

The arrows jump across the grid with no visible pattern. Knowing where kG is says almost nothing about k.

double-and-add computes kG efficiently

Adding G one at a time takes k − 1 additions. Double-and-add reads k in binary from the left, like square-and-multiply. Start at G for the first bit. For each later bit it doubles the point, and when the bit is 1 it also adds G. For example, with G = (3,10), k = 11 = 1011 needs 3 doublings and 2 additions to reach 11G = (18,20).

k for double-and-add

k = 11 = 1011 in binary

Double-and-add for k = 11: one row per bit of k, the doubling, whether G is added, and the multiple and point reached.
Bit	Double	Add G?	Multiple	Point
1	start at G		1	(3, 10)
0	1 × 2 = 2	no	2	(7, 12)
1	2 × 2 = 4	yes: 4 + 1 = 5	5	(9, 16)
1	5 × 2 = 10	yes: 10 + 1 = 11	11	(18, 20)

3 doublings and 2 additions: 5 operations instead of 10. For a 256-bit k, double-and-add needs at most 255 doublings and 255 additions. Adding G one at a time would need about 2^256 additions.

Find k

G
Q = kG, k hidden
your walk
your last guess

The page picked a secret k and shows only Q = kG. Find k. Recovering k from G and kG is the elliptic curve discrete logarithm problem (ECDLP). You can walk G, 2G, 3G, … until you reach Q, or type a guess. Large, well-chosen groups make it hard.

choosing a hidden k …

your guess for k

your work

steps walked: 0 guesses: 0

Here G has order 28, so at most 27 steps find any k. A real curve has about 2^256 points. A walk would need about 2^255 steps on average. The best known attack, Pollard's rho, needs about 2^128 steps. That number is an estimate of the attack's cost, and it is far out of reach.

ECDH: Diffie–Hellman with points

Replace each power with a multiple of a point. Everyone knows the curve and a base point G = (3, 10). Alice sends A = aG. Bob sends B = bG. Their shared point is S = aB = bA = abG. The defaults reuse the secrets of the exchange modulo 19, a = 11 and b = 13.

Alice

Knows her secret a.

Alice's secret a

Computes A = aG = 11G = (18, 20), and sends A.

Receives B = (1, 7).

Computes S = aB = 11 × (1, 7) = (19, 5)

Public channel

Everything here is visible to the attacker.

The curve E_23(1, 1) and G = (3, 10), order 28

Alice to Bob: A = (18, 20) →

← Bob to Alice: B = (1, 7)

The attacker does not see a, b or S.

Bob

Knows his secret b.

Bob's secret b

Computes B = bG = 13G = (1, 7), and sends B.

Receives A = (18, 20).

Computes S = bA = 13 × (18, 20) = (19, 5)

G, public
A = aG, from Alice
B = bG, from Bob
S = abG, shared and secret

why the two results are equal

aB = a(bG) = (ab)G = b(aG) = bA ab = 11 × 13 = 143, and 143 mod 28 = 3 so S = 3G = (19, 5)

The multiple can be reduced modulo 28, the order of G, because 28G = O. Alice and Bob never send S.

The attacker sees the curve, G, A and B. Recovering either private number, a from A = aG or b from B = bG, lets an attacker compute the shared point. That is the ECDLP from the step before. This toy group is too small for security.

Standard curves reach similar classical security with smaller public values. At about 128-bit security, ffdhe3072 sends 384 bytes, ECDH on P-256 sends 65 bytes (33 compressed), and X25519 sends 32 bytes (NIST SP 800-57 Part 1 Rev. 5, Table 2). This page is educational code with tiny numbers. Use a maintained library for anything real.

step 1/5

CPE 645 / CS 685

An Elliptic Curve Modulo a Prime

Adding Points on an Elliptic Curve

Qubits, Measurement, and Interference