Skip to content
Tutorials Center
My learning

Topics

Lesson 26 of 40 ยท Public-Key Cryptography

Elliptic Curve Cryptography

Learn elliptic curve cryptography hands-on: add points on a small curve, multiply by scalars, run ECDH and a toy ECDSA, then try secp256k1 and read about Ed25519.

RSA and classic Diffie-Hellman need keys of 2048 to 3072 bits to reach 128-bit security. Elliptic curve cryptography (ECC) reaches the same strength with 256-bit keys, which means smaller certificates, faster handshakes and less battery drain. That is why new systems (TLS 1.3, SSH, Signal, Bitcoin, passkeys, WireGuard) are built on curves.

The idea is the same as before: a group in which one operation is easy and the inverse is hard. For Diffie-Hellman that group was "numbers modulo a prime, under multiplication". Here it is "points on a curve, under a geometric addition". You do not need calculus or geometry to use it; with modular arithmetic and a few lines of Python you can do every operation by hand.

Points on a curve

An elliptic curve over a prime field is the set of pairs (x, y) with coordinates modulo a prime p that satisfy

y^2 = x^3 + a*x + b (mod p)

plus one extra element, the point at infinity O, which acts like zero. Over the real numbers the curve is a smooth looping shape; modulo a prime it is a scattering of dots, but the algebra is identical.

The group operation, point addition, has a geometric description over the reals: draw the line through two points, find the third point where it meets the curve, and reflect it across the x-axis. Algebraically, for points P = (x1, y1) and Q = (x2, y2):

  • If x1 = x2 and y1 = -y2, then P + Q = O.
  • The slope is s = (y2 - y1) / (x2 - x1) for different points, and s = (3*x1^2 + a) / (2*y1) when adding a point to itself (doubling). Division means multiplying by the modular inverse.
  • Then x3 = s^2 - x1 - x2 and y3 = s*(x1 - x3) - y1, all modulo p.
flowchart LR
    P["P = (x1, y1)"] --> L["Line through P and Q"]
    Q["Q = (x2, y2)"] --> L
    L --> R["Third intersection<br/>with the curve"]
    R --> F["Reflect over the x-axis"]
    F --> S["P + Q"]

Point addition: join, intersect, reflect. The formulas above compute the same thing without drawing.

Scalar multiplication: the one-way function

Add a point G to itself k times and you get kG, scalar multiplication. It can be done in about log2(k) steps by repeated doubling (the same square-and-multiply idea as pow(a, b, m)), even for a 256-bit k. Going backwards, finding k from G and kG, is the elliptic curve discrete logarithm problem. For well-chosen curves the best known attacks cost about sqrt(n) steps for a group of size n, which is why a 256-bit curve gives 128-bit security. There is no subexponential attack like the number field sieve against RSA, and that is the entire reason ECC keys can be small.

Let us watch it happen on a curve small enough to see completely: y^2 = x^3 + 2x + 2 modulo 17, with generator G = (5, 1). This curve has 19 points including O, and 19 is prime, so every non-zero point generates the whole group.

Python Point addition and scalar multiplication on a small curve

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.

Notice that 20G = G: the multiples cycle with period 19, exactly as powers cycle modulo a prime.

ECDH: Diffie-Hellman on a curve

Elliptic-curve Diffie-Hellman replaces exponentiation with scalar multiplication. Alice picks a secret integer a and publishes A = aG; Bob picks b and publishes B = bG. Alice computes aB and Bob computes bA. Both equal abG, because scalar multiplication is just repeated addition and addition is associative.

The attacker sees G, A and B. On our toy curve there are only 19 points, so the brute force finishes immediately, just as in the earlier lesson. Real curves have a group order of about 2^256.

Python ECDH on the toy curve, and its brute force

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.

In practice you hash the shared point's x-coordinate (or use X25519 directly, see below) through HKDF to obtain symmetric keys.

ECDSA: signatures on curves

The Elliptic Curve Digital Signature Algorithm is a signature scheme built from the same group; Digital Signatures covers signing in depth. In outline, with private key d, public key Q = dG, group order n and message hash h:

  1. Choose a fresh random nonce k with 1 <= k < n and compute the point kG; let r be its x-coordinate modulo n.
  2. Compute s = k^-1 * (h + r*d) mod n. The signature is (r, s).
  3. To verify, compute w = s^-1, then u1 = h*w and u2 = r*w, and check that the x-coordinate of u1*G + u2*Q equals r modulo n.

Verification works because u1*G + u2*Q = (h + r*d) * s^-1 * G = k*G. Two warnings that matter far more than the algebra: the nonce k must be unique and unpredictable for every signature (a repeated or biased k reveals the private key, which has happened in real products), and the toy below uses a group of order 19, so it proves nothing about security. It only lets you see the mechanism.

Python A toy ECDSA on the order-19 curve

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 second False is probabilistic in a group this tiny: with only 19 possible hash values, a different message can collide. A real group has about 2^256 values and such collisions are out of reach.

A real curve: secp256k1

The curves in use have 256-bit primes and carefully checked parameters. secp256k1, used by Bitcoin and Ethereum, has the particularly simple equation y^2 = x^3 + 7 (so a = 0, b = 7) over the prime p = 2^256 - 2^32 - 977. The same addition and doubling code works unchanged, only with bigger numbers. NIST P-256 (also called secp256r1 or prime256v1) is the most common curve in TLS and WebAuthn, and uses the same formulas with a = -3. The next example sanity-checks the constants: the generator must lie on the curve, and multiplying it by the published group order must give infinity.

Python Scalar multiplication 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.

Real implementations avoid this textbook arithmetic: they use constant-time formulas in projective or Jacobian coordinates (no modular inverse per step), complete addition laws, and checks that received points are on the curve. Invalid-curve attacks, where an attacker sends a point that is not on the curve and extracts bits of your secret, are a real hazard for hand-written ECC.

Curve25519, X25519 and Ed25519

Daniel J. Bernstein designed Curve25519 over the prime 2^255 - 19 for speed, simplicity and misuse resistance. It appears in two forms:

  • X25519 is the key-exchange function you ran in the Diffie-Hellman lesson. Private keys are 32 random bytes with a few bits clamped, public keys are 32 bytes, and any 32-byte string is a valid public key.
  • Ed25519 is a signature scheme on the same field, using an equivalent twisted Edwards curve with a complete addition law. Keys are 32 bytes, signatures 64 bytes. The nonce is derived deterministically by hashing the private key and the message, so a faulty random number generator can no longer cause nonce reuse. It is fast, and verification is simple to implement correctly.

For new designs the usual recommendation is X25519 for key agreement and Ed25519 for signatures, or P-256 where a standard requires NIST curves. A word of caution: elliptic curves, like RSA and Diffie-Hellman, fall to Shor's algorithm on a large quantum computer, as the post-quantum lesson explains.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is scalar multiplication kG on an elliptic curve?

    kG is repeated point addition. Double-and-add computes it in about log2(k) operations, but recovering k from G and kG is the hard elliptic curve discrete logarithm.
  2. 2. Why can elliptic curve keys be much smaller than RSA keys for the same security?

    A 256-bit curve costs about 2^128 steps to attack, comparable with a 3072-bit RSA modulus, because factoring-style shortcuts do not apply.
  3. 3. In ECDH, what do Alice and Bob each compute after exchanging public points A = aG and B = bG?

    aB = a(bG) = (ab)G = b(aG) = bA. Only someone knowing a or b can compute this point.
  4. 4. What is the most dangerous mistake when using ECDSA?

    Two signatures with the same nonce let anyone solve for the private key. Ed25519 avoids this by deriving the nonce deterministically.
  5. 5. Which pair is the usual modern choice for key agreement and signatures on Curve25519?

    X25519 does the Diffie-Hellman exchange and Ed25519 does the signatures, both with 32-byte keys on the same underlying curve.

Summary

  • An elliptic curve group consists of points (x, y) on y^2 = x^3 + ax + b modulo a prime, plus the point at infinity, with a simple addition rule.
  • Scalar multiplication kG is fast (double-and-add), while finding k from kG is believed to be infeasible: that is the trapdoor.
  • ECDH, ECDSA and friends are the old Diffie-Hellman and DSA ideas with "power" replaced by "scalar multiple"; 256-bit curves match 3072-bit RSA.
  • ECDSA needs a fresh unpredictable nonce for every signature; Ed25519 derives it deterministically.
  • Use X25519 and Ed25519 (or P-256) from a vetted library, validate received points, and never hand-roll the arithmetic in production.

Next: Digital Signatures, where you will sign and verify with both RSA and DSA-style schemes and see exactly how nonce reuse leaks a private key.