Skip to content
Tutorials Center
My learning

Topics

Lesson 33 of 37 · Cryptographic Applications

Elliptic Curves over Finite Fields

Add points on an elliptic curve modulo a prime, multiply by scalars, count points with Hasse's bound, and run ECDH on a toy curve and on secp256k1.

An elliptic curve is the set of solutions to y² = x³ + ax + b, plus one extra "point at infinity". On the real plane it is a smooth curve with a famous geometric trick: draw a line through two points on the curve and it meets the curve in a third point. Reflect that third point across the x-axis and you have defined an addition of points. Remarkably, this addition is associative, has an identity (the point at infinity) and inverses, so the points form a group.

Now do everything modulo a prime p. The curve becomes a scattered cloud of points, but the same formulas work, and the group is finite. In this group the discrete logarithm problem (given P and kP, find k) appears to be much harder than modulo p, so much smaller keys give the same security. A 256-bit elliptic-curve key matches roughly a 3072-bit RSA key. This lesson builds the group law, counts points, and runs a key exchange.

Points on a curve modulo p

Python All points of y^2 = x^3 + 2x + 3 mod 97

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The picture is symmetric: if (x, y) is on the curve, so is (x, -y). Brute-force counting is fine for a tiny p; for 256-bit curves Schoof's algorithm counts points in polynomial time.

The group law

Represent the point at infinity as None. For P = (x₁, y₁) and Q = (x₂, y₂):

  • P + (-P) = ∞, where -P = (x, -y).
  • If P ≠ Q: slope λ = (y₂ - y₁)/(x₂ - x₁).
  • If P = Q (doubling): λ = (3x₁² + a)/(2y₁).
  • Then x₃ = λ² - x₁ - x₂ and y₃ = λ(x₁ - x₃) - y₁, all modulo p.

Division means multiplying by a modular inverse, available as pow(v, -1, p).

Python Point addition and doubling

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All results stay on the curve, addition is associative and commutative. Associativity is deeply non-obvious from the formulas; the test is a numerical sanity check, not a proof.

Scalar multiplication

kP = P + P + ... + P (k terms) is computed with double-and-add, the elliptic-curve analogue of repeated squaring: scan the bits of k, doubling each step and adding P when the bit is 1. It takes about log k group operations. The cyclic subgroup generated by P has an order n, the least n > 0 with nP = ∞.

Python Double-and-add, order of a point

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The order of P divides the number of points on the curve (Lagrange's theorem).

Hasse's bound

How many points can a curve have? Hasse's theorem: |N - (p + 1)| ≤ 2√p. So a curve modulo p has about p points, give or take 2√p. This is the key size fact: a curve over a 256-bit prime has a group of about 256-bit order.

Python Hasse's bound on many curves

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The check skips singular curves (where 4a³ + 27b² ≡ 0), which have repeated roots and do not form a group.

Elliptic-curve Diffie-Hellman

Replace g^a by a·G. Alice sends A = a·G, Bob sends B = b·G, and the shared secret is a·B = b·A = ab·G. The attacker faces the elliptic curve discrete logarithm problem. Bitcoin and Ethereum use the curve secp256k1: y² = x³ + 7 over p = 2²⁵⁶ - 2³² - 977, with a published generator G of prime order n.

Python ECDH on secp256k1

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

n·G = ∞ confirms the published parameters, and both parties compute the same shared point. (In practice the x-coordinate is hashed to get a key. Production code uses constant-time libraries: the naive double-and-add above leaks the secret through timing.)

Why curves, not just numbers modulo p?

Modulo a prime, the index calculus algorithm solves the discrete log in sub-exponential time, forcing 2048-bit sizes. For generic elliptic curves no sub-exponential attack is known; the best are √n-type methods such as Pollard's rho, so 256-bit keys suffice. Smaller keys mean faster signatures, smaller certificates and less bandwidth, which is why mobile and embedded systems love ECC.

flowchart LR
    G["G (public generator)"] --> A["A = a*G"]
    G --> B["B = b*G"]
    A -->|"Alice computes a*B"| S["shared point ab*G"]
    B -->|"Bob computes b*A"| S

Elliptic-curve Diffie-Hellman: the same shape as the original, with addition in place of multiplication.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What plays the role of the identity element in the elliptic curve group?

    P + infinity = P for every point P.
  2. 2. How do you compute kP quickly?

    Double-and-add needs about log2(k) doublings and additions.
  3. 3. Hasse's theorem says the number N of points modulo p satisfies:

    The count stays within 2*sqrt(p) of p + 1.
  4. 4. Why can ECC use much smaller keys than RSA?

    Only square-root attacks are known, so 256-bit curves match about 3072-bit RSA.

Summary

  • An elliptic curve mod p has a finite group of points with an identity (the point at infinity).
  • Add with the chord-tangent formulas using modular inverses; multiply with double-and-add.
  • Hasse: the number of points is p + 1 plus or minus 2√p.
  • ECDH replaces g^a with a·G; secp256k1 and Curve25519 are the common curves.
  • Smaller keys come from the absence of sub-exponential discrete-log attacks.

Next: Project: A Prime Explorer