Skip to content
Tutorials Center
My learning

Topics

Lesson 9 of 41 ยท Cryptography Foundations

Elliptic Curves in Plain Language

Learn point addition and scalar multiplication on a tiny elliptic curve, how secp256k1 and ECDSA work, and why reusing a signing nonce leaks the private key.

Bitcoin, Ethereum and most other blockchains sign transactions with elliptic curve cryptography. The name sounds intimidating, but the idea fits on a page: take a special kind of curve, define a way to "add" two points on it, and notice that adding a point to itself many times is easy to do and nearly impossible to undo. That one-way street is the same gap you saw in Public-Key Cryptography Basics, but delivered with much shorter keys.

In this lesson you will build the curve arithmetic yourself on a toy curve with only 31 points, so you can see every number. Then you will meet the real curve (secp256k1), look at how the ECDSA signature algorithm works, and watch what happens when a signer reuses a random value. You do not need calculus. You only need remainders.

A curve over a small prime field

Forget the smooth picture of an ellipse-like curve from textbooks. In cryptography the coordinates are whole numbers modulo a prime p, which means they wrap around like a clock. The curve used by Bitcoin has the form:

TEXT
y^2 = x^3 + 7      (all arithmetic modulo p)

A point is a pair (x, y) of numbers from 0 to p - 1 that satisfies the equation, plus one special extra point called the point at infinity, written here as INF. It plays the role of zero. With a tiny prime such as p = 43 you can list every point by brute force.

Python Listing the points of a toy 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 curve has 30 ordinary points plus INF, a total of 31. That count is called the order of the group, and 31 happens to be prime. A prime order is convenient: every point other than INF can generate the whole group.

Adding points

Elliptic curves have a rule for "adding" two points P1 and P2 to get a third point P3 on the same curve. Geometrically on real numbers you draw a line through the two points, find where it hits the curve a third time, and reflect that point across the x-axis. With modular arithmetic you use the algebraic version of the same recipe:

  • Different points: the slope is (y2 - y1) / (x2 - x1).
  • Same point (doubling): the slope is (3 * x1^2) / (2 * y1) for our curve (the tangent line).
  • Then: x3 = slope^2 - x1 - x2 and y3 = slope * (x1 - x3) - y1, all modulo p.
  • Vertical line (same x, opposite y): the result is INF.
  • Adding INF to any point returns that point unchanged.

Division modulo a prime means multiplying by a modular inverse, which Python gives you as pow(value, -1, p).

flowchart TD
    A["Add P1 and P2"] --> B{"Either point is INF?"}
    B -->|yes| C["Return the other point"]
    B -->|no| D{"Same x but opposite y?"}
    D -->|yes| E["Return INF"]
    D -->|no| F{"P1 equals P2?"}
    F -->|yes| G["Slope from the tangent<br/>(doubling)"]
    F -->|no| H["Slope from the line<br/>through both points"]
    G --> I["Compute x3 and y3"]
    H --> I

The case analysis behind point addition: INF handling, vertical lines, doubling and the general case.

Scalar multiplication: the one-way operation

Add the same point to itself repeatedly and you get its multiples: G, 2G, 3G, and so on. Writing k * G means "add G to itself k times". This is called scalar multiplication, and it is the operation that turns a private key into a public key:

TEXT
private key  d   (a number)
public key   Q = d * G   (a point)

Here G is a fixed, publicly agreed starting point called the generator. Going from d to Q is fast. Going from Q back to d is the elliptic curve discrete logarithm problem, and no efficient method is known for well-chosen curves.

Computing d * G does not take d additions. The double-and-add method walks the bits of d, doubling at each step and adding when the bit is 1, so it needs only about as many steps as d has bits.

Python Point addition and scalar multiplication

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 table ends with the wrap-around: 31 * G is INF and 32 * G returns to G. In a real system the group order is about 2^256, so brute-force search would take longer than the age of the universe, while multiply still finishes in a few hundred steps.

secp256k1: the real curve

Bitcoin and Ethereum both use a standardized curve named secp256k1. It has exactly the same equation as our toy, y^2 = x^3 + 7, but with a 256-bit prime p = 2^256 - 2^32 - 977, a published generator G, and a group order n close to 2^256. The same add and multiply code works unchanged if you swap the constants. The next example checks that the published generator really lies on the curve, that n * G is INF, and shows a toy-sized private key turned into a public key.

Python The real secp256k1 constants

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 what is not in this code: any secret-dependent shortcut. Anyone can recompute the public key from the private key, which is what lets you derive your address later in Keys, Addresses and Wallets. Production libraries add protections against timing leaks that this teaching version ignores.

ECDSA in one page

ECDSA (Elliptic Curve Digital Signature Algorithm) is the signature scheme used by Bitcoin and Ethereum. Let d be the private key, Q = d * G the public key, n the group order, and z the hash of the message reduced to a number. To sign:

  1. Pick a fresh random number k between 1 and n - 1. This is the nonce.
  2. Compute the point R = k * G and let r be its x-coordinate modulo n.
  3. Compute s = k^-1 * (z + r * d) mod n.
  4. The signature is the pair (r, s).

To verify with Q:

  1. Compute w = s^-1 mod n.
  2. Compute the point u1 * G + u2 * Q, where u1 = z * w and u2 = r * w (both mod n).
  3. Accept if the x-coordinate of that point, modulo n, equals r.

Verification works because u1 * G + u2 * Q = (z + r * d) * w * G = k * G = R, so it lands exactly on the point the signer started with, without ever needing d or k.

The nonce must never repeat

Look at the formula s = k^-1 * (z + r * d). It has two unknowns the attacker lacks: k and d. One equation with two unknowns reveals nothing. But if the same k signs two different messages z1 and z2, then r is the same in both signatures, and you get two equations with the same two unknowns:

TEXT
s1 = k^-1 * (z1 + r*d)
s2 = k^-1 * (z2 + r*d)

s1 - s2 = k^-1 * (z1 - z2)   so   k = (z1 - z2) / (s1 - s2)
then d = (s1 * k - z1) / r

Anyone can spot a repeated r in public signatures, then compute the private key with a few lines of algebra. This has happened in real life: weak or duplicated randomness in signing software and in some wallets led to stolen funds. Modern libraries avoid the risk by deriving k deterministically from the private key and the message (the scheme is called RFC 6979).

The final example runs ECDSA on the toy curve (group order 31) and then recovers the private key from two signatures that reused k. With such a tiny order, random message hashes would verify by accident about one time in 31, so this code is a demonstration of the algebra, not of security.

Python ECDSA on a toy curve and a nonce-reuse break

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 attacker never touched d directly. Two public signatures and some modular algebra were enough. That is why signature libraries treat nonce generation as a security-critical part of the code.

Why blockchains use curves instead of RSA

  • Short keys: a 256-bit curve key offers security comparable to a 3,072-bit RSA key, so public keys, signatures and transactions are smaller.
  • Fast signing: a signature costs a couple of scalar multiplications.
  • Mature tooling: secp256k1 has been in production in Bitcoin since 2009 and is supported by hardware wallets and libraries.

Many newer systems use the Ed25519 curve instead, which avoids the nonce pitfall by design. A quantum computer large enough to run Shor's algorithm would break both RSA and elliptic curves, which is one reason post-quantum signatures such as the hash-based ones from Digital Signatures with a Toy Scheme are an active research area.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the relationship between a private key d and a public key Q on an elliptic curve?

    The public key is the generator point added to itself d times. Computing it is fast; recovering d from Q is the discrete logarithm problem.
  2. 2. What does the point at infinity (INF) do in the point-addition rules?

    INF is the identity element of the group. It is also the result when you add a point to its mirror image, such as 31*G on our toy curve.
  3. 3. Why is double-and-add used for scalar multiplication?

    Doubling at each bit position lets you compute 2^256-sized multiples in a few hundred operations, which is what makes real keys practical.
  4. 4. What happens if an ECDSA signer reuses the same nonce k for two different messages?

    Both signatures share the same r, which gives two equations in the unknowns k and d. Solving them exposes the private key.
  5. 5. What is secp256k1?

    It is a standardized curve y^2 = x^3 + 7 over a 256-bit prime field. Bitcoin and Ethereum sign transactions with ECDSA on it.

Summary

  • An elliptic curve over a prime field is the set of points (x, y) with y^2 = x^3 + 7 (mod p) plus a point at infinity; a rule for adding points turns it into a group.
  • A public key is Q = d * G: easy to compute with double-and-add, believed infeasible to reverse.
  • secp256k1 is the 256-bit version of the same curve used by Bitcoin and Ethereum.
  • ECDSA signs with (r, s) built from a fresh nonce k, and verifies using only the public key.
  • Reusing a nonce lets anyone compute the private key; libraries derive nonces deterministically for this reason.

Next: Keys, Addresses and Wallets