Elliptic Curves from Scratch: Group Law, Double-and-Add and a Toy ECDH

Elliptic-curve cryptography has a reputation for being harder than RSA, and in one sense it is: there is no single-sentence description like "multiply two primes". But the whole thing rests on one geometric idea and two formulas, and once those are in hand the rest, scalar multiplication, Diffie–Hellman, the reason 256-bit curves are safe and 7-bit curves are not, follows in a few dozen lines of Python. This post builds it from nothing. All code is pure Python with no dependencies, and every number quoted was produced by running it.

A curve and a rule for adding points

An elliptic curve in short Weierstrass form is the set of points $(x, y)$ satisfying

y^{2} = x^{3} + a x + b, 4 a^{3} + 27 b^{2} \neq 0,

together with one extra point $O$ , the point at infinity. The inequality just rules out curves with cusps or self-intersections. Over the real numbers the curve is a smooth figure symmetric about the x-axis, and that symmetry is what makes the group law work.

Plot of the real elliptic curve y squared equals x cubed minus x plus one with the chord through P and Q, its third intersection R, and the reflected sum P plus Q — The group law over the reals. A line through P and Q meets the curve in exactly one more point R; reflecting R across the x-axis gives P + Q.

The rule: to add $P$ and $Q$ , draw the line through them. A cubic meets a line in three points, so the line hits the curve once more, at $R$ . Reflect $R$ across the x-axis and call the result $P + Q$ . To double a point, use the tangent line instead of the chord. The vertical line through $P$ and its reflection $- P$ "meets the curve at infinity", which is why $O$ is needed as the identity: $P + (- P) = O$ .

Writing the line as $y = λ x + ν$ and substituting into the curve equation gives a cubic in $x$ whose three roots are $x_{1}, x_{2}, x_{3}$ . The coefficient of $x^{2}$ in that cubic is $- λ^{2}$ , and it must equal $- (x_{1} + x_{2} + x_{3})$ , so

x_{3} = λ^{2} - x_{1} - x_{2}, y_{3} = λ (x_{1} - x_{3}) - y_{1},

where the slope is

λ = {\begin{cases} \frac{y_{2} - y_{1}}{x_{2} - x_{1}} & (addition, P \neq Q) \\ \frac{3 x_{1}^{2} + a}{2 y_{1}} & (doubling, P = Q) . \end{cases}

That is the entire group law. With these rules the points form an abelian group: addition is commutative, associative (the hard part to prove, easy to check numerically), $O$ is the identity, and $- P = (x, - y)$ .

The same rule over a finite field

Nothing in those formulas needs real numbers. Replace the field with $F_{p}$ , the integers modulo a prime, and replace division by multiplication with the modular inverse. The picture stops being a curve and becomes a scatter of points, but the algebra is identical and the group structure survives.

Scatter plot of the 102 affine points of the curve y squared equals x cubed plus 3x plus 2 modulo 97, symmetric about y equals p over 2 — The 102 affine points of y² = x³ + 3x + 2 over F₉₇. Adding the point at infinity gives a group of order 103, which is prime.

p, a, b = 97, 3, 2          # y^2 = x^3 + 3x + 2 over F_97
O = None                    # point at infinity

def inv(x):
    return pow(x, p - 2, p)         # Fermat: x^(p-2) is x^-1 mod p

def add(P, Q):
    if P is O: return Q
    if Q is O: return P
    x1, y1 = P
    x2, y2 = Q
    if x1 == x2 and (y1 + y2) % p == 0:
        return O                    # P + (-P)
    if P == Q:
        lam = (3 * x1 * x1 + a) * inv(2 * y1) % p    # tangent
    else:
        lam = (y2 - y1) * inv(x2 - x1) % p           # chord
    x3 = (lam * lam - x1 - x2) % p
    y3 = (lam * (x1 - x3) - y1) % p
    return (x3, y3)

Enumerating every $(x, y)$ pair that satisfies the equation finds 102 affine points; with $O$ the group has order 103. Hasse's theorem says the order must lie within $p + 1 \pm 2 \sqrt{p}$ , here $98 \pm 19.7$ , and it does. Because 103 is prime, the group is cyclic and every point other than $O$ generates it, which is exactly the property real curves are chosen to have (or to have up to a small cofactor).

Scalar multiplication: double-and-add

The operation cryptography actually uses is computing $k P = P + P + \dots + P$ for a large integer $k$ . Doing it by repeated addition takes $k$ steps, which for a 256-bit $k$ is longer than the age of the universe. Double-and-add does it in $O (\log k)$ steps by reading $k$ in binary:

def mul(k, P):
    """Double-and-add, most significant bit first."""
    R = O
    for bit in bin(k)[2:]:
        R = add(R, R)               # always double
        if bit == "1":
            R = add(R, P)           # add only when the bit is set
    return R

For $k = 42 = 101010_{2}$ the loop performs six doublings and three additions instead of 41 additions. On a 256-bit curve the same loop needs about 256 doublings and on average 128 additions, a few hundred field operations in total. This is the entire reason the scheme is practical.

It is also where real implementations part ways with this one. The branch on bit == "1" makes the running time and the power trace depend on the secret $k$ , which is enough for a side-channel attack to read it bit by bit. Production code uses a Montgomery ladder or complete addition formulas that perform the same operations regardless of the key bits, and never calls inv mid-loop (inversions are done once at the end, in projective coordinates).

Diffie–Hellman on the toy curve

With a generator $G$ of prime order $n$ , ECDH is three lines. Alice picks a secret $d_{A}$ and publishes $Q_{A} = d_{A} G$ ; Bob does the same; each multiplies the other's public point by their own secret, and $d_{A} (d_{B} G) = d_{B} (d_{A} G)$ because scalar multiplication is just repeated addition and addition is associative.

G, n = (0, 14), 103         # any non-identity point generates; order is prime

import random
random.seed(7)
d_a, d_b = random.randrange(1, n), random.randrange(1, n)
Q_a, Q_b = mul(d_a, G), mul(d_b, G)

print("Alice d_a =", d_a, "Q_a =", Q_a)
print("Bob   d_b =", d_b, "Q_b =", Q_b)
print("shared (Alice) =", mul(d_a, Q_b))
print("shared (Bob)   =", mul(d_b, Q_a))

Alice d_a = 42 Q_a = (88, 64)
Bob   d_b = 20 Q_b = (15, 67)
shared (Alice) = (64, 70)
shared (Bob)   = (64, 70)

Both sides arrive at $(64, 70)$ . In a real protocol the x-coordinate goes through a key-derivation function to become a symmetric key; the raw point is never used directly.

Why this curve is worthless

An eavesdropper sees $G$ , $Q_{A}$ and $Q_{B}$ , and needs $d_{A}$ or $d_{B}$ : the elliptic-curve discrete logarithm problem. On our curve it falls to the most naive attack imaginable:

k, T = 1, G
while T != Q_a:
    T = add(T, G)
    k += 1
print("recovered d_a =", k, "after", k, "additions")
# recovered d_a = 42 after 42 additions

Forty-two additions, and in the worst case 102. The point is not that brute force exists; it is how the cost scales. The best known generic algorithm, Pollard's rho, recovers a discrete logarithm in a group of prime order $n$ in about

\sqrt{\frac{π n}{4}} \approx 0.886 \sqrt{n}

group operations. For $n = 103$ that is 9 operations. For $n \approx 2^{256}$ it is about $2^{128}$ , which is the "128-bit security" quoted for 256-bit curves. The security of the whole system is the square root of the group order, so every bit of security costs two bits of curve.

Curve	Field size	Group order $n$	Rho cost $\approx 0.886 \sqrt{n}$	Notes
toy, $y^{2} = x^{3} + 3 x + 2$	7 bits	103	9	broken by hand
secp256k1	256 bits	$\approx 2^{256}$	$2^{128}$	Bitcoin, Ethereum; Koblitz curve, $a = 0$
NIST P-256	256 bits	$\approx 2^{256}$	$2^{128}$	TLS default for ECDHE and ECDSA
Curve25519	255 bits	$\approx 2^{252}$	$2^{126}$	cofactor 8; X25519 in TLS 1.3, SSH, Signal
NIST P-384	384 bits	$\approx 2^{384}$	$2^{192}$	CNSA suite

Being large is necessary but not sufficient. Curves whose order equals $p$ (anomalous curves) or has small factors, or whose embedding degree is tiny, have discrete logarithms that collapse to easier problems in other groups. Standard curves are chosen to avoid every known special structure, and the SafeCurves criteria go further by also demanding that the implementation be easy to get right: complete addition formulas, no exceptional cases, and a shape (Montgomery or twisted Edwards) that resists invalid-curve and twist attacks.

WARNING

The code in this post is for understanding, not for use. It leaks the secret through timing, accepts points that are not on the curve, performs no validation of the peer's public key, and uses random rather than secrets. Real implementations (X25519 via cryptography in Python, or your platform's TLS library) handle all of this and have been reviewed by people whose job it is to find the mistakes. Use them.

The complete toy implementation

# Toy short-Weierstrass curve y^2 = x^3 + a x + b over F_p, pure Python.
p, a, b = 97, 3, 2
O = None  # point at infinity


def inv(x):
    return pow(x, p - 2, p)


def on_curve(P):
    if P is O:
        return True
    x, y = P
    return (y * y - (x**3 + a * x + b)) % p == 0


def add(P, Q):
    if P is O:
        return Q
    if Q is O:
        return P
    x1, y1 = P
    x2, y2 = Q
    if x1 == x2 and (y1 + y2) % p == 0:
        return O
    if P == Q:
        lam = (3 * x1 * x1 + a) * inv(2 * y1) % p
    else:
        lam = (y2 - y1) * inv(x2 - x1) % p
    x3 = (lam * lam - x1 - x2) % p
    y3 = (lam * (x1 - x3) - y1) % p
    return (x3, y3)


def mul(k, P):
    R = O
    for bit in bin(k)[2:]:
        R = add(R, R)
        if bit == "1":
            R = add(R, P)
    return R


def order(P):
    n, Q = 1, P
    while Q is not O:
        Q = add(Q, P)
        n += 1
    return n


points = [O] + [(x, y) for x in range(p) for y in range(p) if on_curve((x, y))]
print("group order #E(F_p) =", len(points))      # 103
G = (0, 14)
print("order of G =", order(G))                   # 103
print("3G =", mul(3, G), "=", add(G, add(G, G)))  # (38, 59) both ways
print("nG =", mul(103, G))                        # None, i.e. the identity

Elliptic Curves from Scratch: Group Law, Double-and-Add and a Toy ECDH

A curve and a rule for adding points

The same rule over a finite field

Scalar multiplication: double-and-add

Diffie–Hellman on the toy curve

Why this curve is worthless

WARNING

Further reading

Cite this post

Keep reading