Lesson 8.1: ECC Basics, ECDH and ECDSA

Posted Oct 3, 2023 Updated Oct 8, 2026

ECC Basics, ECDH and ECDSA

By HaiND

views 12 min read

Lesson 8.1: ECC Basics, ECDH and ECDSA

This lesson builds elliptic curve cryptography (ECC) from scratch. A curve is the set of points satisfying y^2 = x^3 + ax + b mod p. Two points are added by a geometric rule, a point is multiplied by a number, and from those pieces we build the ECDH key exchange and the ECDSA signature. The environment has no ready-made EC library, so we implement every operation in pure Python on a small curve and run it to see each step. After this lesson you understand what the point at infinity is, why point multiplication is easy while the reverse (ECDLP) is hard, and how ECDSA signs and verifies.

Point addition and double-and-add give k*G. ECDH shares (dA*dB)*G, and ECDSA signs with a secret nonce k.

Prerequisites: Lesson 1.1 (modular arithmetic, inverses), Lesson 1.4 (groups, the field GF(p)), Lesson 7.1 (discrete log, to compare ECDLP with DLP). Lesson 5.1 (hashes) helps with the ECDSA part.

Tools: Python 3 (pure, only hashlib from the standard library). Nothing to install. Every EC operation is hand-written.

Goals

You will understand the Weierstrass curve y^2 = x^3 + ax + b mod p, the point at infinity, and why the points form a group. You will code point addition and scalar multiplication (double-and-add) in pure Python. You will build ECDH (key exchange) and ECDSA (sign, verify) on a small curve and run them. And you will understand the ECDLP and why ECC reaches the same security as RSA/DH with much shorter keys.

Theory

The curve, its points, and the point at infinity

Over a finite field GF(p) (integers modulo a prime p), a short Weierstrass elliptic curve is the set of points (x, y) satisfying:

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

plus one special point called the point at infinity, written O, which acts as the identity element (like 0 for addition). The non-singular condition is 4a^3 + 27b^2 != 0 mod p (if it is 0 the curve is singular, Lesson 8.3).

A concrete example is p = 97, a = 3, b = 2. The point (0, 14) is on the curve because 14^2 = 196 = 2*97 + 2, and 0^3 + 3*0 + 2 = 2, so they match. This finite set of points together with O forms an abelian group under point addition.

Point addition: geometry turned into formulas

The addition rule is chord-and-tangent. To add P + Q, draw the line through P and Q. It meets the curve at a third point, and reflecting that point across the x-axis gives P + Q. Translated into formulas over GF(p):

If P = O then P + Q = Q (and the other way round).
If P = (x, y) and Q = (x, -y) (mirror images) then P + Q = O.
The slope m: if P != Q then m = (y2 - y1) / (x2 - x1). If P = Q (doubling) use the tangent m = (3*x1^2 + a) / (2*y1). Division here means multiplying by the modular inverse (Lesson 1.1).
Then x3 = m^2 - x1 - x2, y3 = m*(x1 - x3) - y1, all mod p.

Note that the addition formula never uses b. This small detail is the root of the invalid curve attack in Lesson 8.3.

Scalar multiplication and the ECDLP

Scalar multiplication adds a point to itself k times: k*P = P + P + ... + P. It is done fast with double-and-add (the same as fast exponentiation, with point addition in place of multiplication). Walk through the bits of k, add on a 1 bit, and double at every step. Computing k*P from k and P is very fast.

The reverse direction is the Elliptic Curve Discrete Logarithm Problem (ECDLP). Given P and Q = k*P, find k. On a well-chosen curve the ECDLP is much harder than the ordinary DLP. There is no efficient index calculus algorithm, so the best algorithm is still about sqrt(group order). As a result, 256-bit ECC is about as secure as 3072-bit RSA/DH. Shorter keys and faster operations are why ECC dominates modern crypto.

ECDH and ECDSA

ECDH is DH moved to a curve. A base point (generator) G is public. Alice picks a secret dA and publishes QA = dA*G. Bob picks dB and publishes QB = dB*G. The shared secret is dA*QB = dB*QA = (dA*dB)*G. Security rests on the ECDLP.

ECDSA is a digital signature on a curve. Let n be the order of G (the number of points in the subgroup generated by G). The secret signing key is d and the public key is Q = d*G. To sign a message with hash z:

Pick a random nonce k in [1, n-1].
Compute R = k*G and take r = R.x mod n (if r = 0, pick a new k).
Compute s = k^(-1) * (z + r*d) mod n.
The signature is the pair (r, s).

To verify (r, s) with hash z and public key Q, compute w = s^(-1) mod n, u1 = z*w, u2 = r*w, then X = u1*G + u2*Q. The signature is valid when X.x mod n == r. The nonce k is the weak point of ECDSA. Leaking k or reusing it loses the private key (Lesson 8.2).

Demo

Everything below is a single file that runs as is. The curve is p = 97, a = 3, b = 2.

  
# d81_ecc.py: pure Python ECC on a small curve. Point addition, scalar multiplication, ECDH, ECDSA.
import hashlib

# ===== Curve parameters: y^2 = x^3 + a*x + b mod p =====
p = 97
a, b = 3, 2
INF = None   # point at infinity, use None as the identity point O

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

def point_add(P, Q):
    # add two points with the chord-and-tangent formula
    if P is INF:
        return Q
    if Q is INF:
        return P
    x1, y1 = P
    x2, y2 = Q
    if x1 == x2 and (y1 + y2) % p == 0:
        return INF                       # P + (-P) = O
    if P == Q:
        # tangent: slope m = (3x^2 + a) / (2y)
        m = (3 * x1 * x1 + a) * pow(2 * y1, -1, p) % p
    else:
        m = (y2 - y1) * pow(x2 - x1, -1, p) % p
    x3 = (m * m - x1 - x2) % p
    y3 = (m * (x1 - x3) - y1) % p
    return (x3, y3)

def scalar_mul(k, P):
    # scalar multiplication by double-and-add
    R = INF
    Q = P
    while k > 0:
        if k & 1:
            R = point_add(R, Q)
        Q = point_add(Q, Q)
        k >>= 1
    return R

def find_points():
    pts = []
    for x in range(p):
        rhs = (x**3 + a * x + b) % p
        for y in range(p):
            if (y * y) % p == rhs:
                pts.append((x, y))
    return pts

if __name__ == "__main__":
    pts = find_points()
    print("finite points =", len(pts), "| plus the point at infinity ->", len(pts) + 1)

    # pick base point G and determine its order n
    G = pts[0]
    print("G =", G, "| on curve?", is_on_curve(G))
    # count the order: the group has prime order 103 so every point != O generates the whole group
    n = 1
    T = G
    while T is not INF:
        T = point_add(T, G)
        n += 1
    print("order of G: n =", n)

    # --- point addition and multiplication examples ---
    print("2G =", scalar_mul(2, G), "| 3G =", scalar_mul(3, G))
    print("nG = O ?", scalar_mul(n, G) is INF)

    # ===== ECDH =====
    da, db = 17, 71                      # private keys of Alice, Bob
    Qa, Qb = scalar_mul(da, G), scalar_mul(db, G)
    Sa = scalar_mul(da, Qb)
    Sb = scalar_mul(db, Qa)
    print("ECDH: Alice", Sa, "| Bob", Sb, "| match?", Sa == Sb)

    # ===== ECDSA =====
    def H(msg):
        return int.from_bytes(hashlib.sha256(msg).digest(), "big") % n

    d = 42                               # secret signing key
    Q = scalar_mul(d, G)                 # public key

    def sign(msg, k):
        z = H(msg)
        R = scalar_mul(k, G)
        r = R[0] % n
        s = (pow(k, -1, n) * (z + r * d)) % n
        return (r, s)

    def verify(msg, sig, Q):
        r, s = sig
        if not (1 <= r < n and 1 <= s < n):
            return False
        z = H(msg)
        w = pow(s, -1, n)
        u1, u2 = (z * w) % n, (r * w) % n
        X = point_add(scalar_mul(u1, G), scalar_mul(u2, Q))
        return X is not INF and X[0] % n == r

    msg = b"ecdsa on a small curve"
    sig = sign(msg, k=23)
    print("signature (r, s) = ", sig)
    print("verify correct msg :", verify(msg, sig, Q))
    print("verify wrong msg  :", verify(b"forged msg", sig, Q))

Output:

finite points = 102 | plus the point at infinity -> 103
G = (0, 14) | on curve? True
order of G: n = 103
2G = (86, 53) | 3G = (38, 59)
nG = O ? True
ECDH: Alice (67, 84) | Bob (67, 84) | match? True
signature (r, s) =  (19, 10)
verify correct msg : True
verify wrong msg  : False

Reading the result, the group has 103 points (including O), and 103 is prime, so every point other than O generates the whole group and has order n = 103. scalar_mul(n, G) returns O, as the theory says (multiplying by the full order gives the identity). ECDH gives Alice and Bob the same point (67, 84). ECDSA signs and then verifies the right message with True, while a forged message gives False, so the signature does its job.

Note that p = 97 while n = 103. The group order differs from the prime of the field, so do not mix the two numbers. In ECDSA every mod is taken by n (the group order), not by p.

Lab

This is a groundwork lesson with nothing to break yet. Practice before Lessons 8.2 and 8.3:

List all points of the curve p = 97, a = 3, b = 2 yourself. Check that (x, y) and (x, p-y) always come in pairs (mirror images across the x-axis), and that there is at most one point with y = 0.
Write a function point_neg(P) that returns -P, and check P + (-P) = O for a few points.
Build ECDH end to end. After you have the shared secret, hash its x coordinate with SHA-256 into an AES-128 key, encrypt a sentence, and decrypt it again.
Try a standard curve. Take the secp256k1 parameters (p, a=0, b=7, G, n can all be looked up), plug them into the same point_add and scalar_mul above (they work on big numbers because they use Python’s pow(..., -1, p)), then sign and verify a message. The goal is to see the small-curve code run unchanged on a real curve.
Done when ECDH plus AES runs on the small curve, and signing and verifying works on secp256k1.

Key takeaways

The curve is y^2 = x^3 + ax + b mod p, points are added with chord-and-tangent, and O is the identity. The non-singular condition is 4a^3 + 27b^2 != 0.
The addition formula does not use b, only a. Remember this for Lesson 8.3.
Scalar multiplication k*P is fast with double-and-add. The reverse (ECDLP) is hard, and that is the security foundation.
ECDH: the shared secret is (dA*dB)*G. ECDSA: signing needs a nonce k, and every mod is by the group order n, not p.
The ECDSA nonce k must be secret, random, and different each time. This is the weak point (Lesson 8.2).

Common pitfalls

Mixing up p (the prime of the field) and n (the group order). Point coordinates are computed mod p, while scalars and ECDSA are computed mod n. Confusing them breaks every signature.
Forgetting the point at infinity O in point_add. A missing P is INF branch or a missing P + (-P) = O branch makes the code crash or return a wrong point.
Using (y2 - y1)/(x2 - x1) when P == Q. Doubling must use the tangent formula, otherwise x2 - x1 = 0 and the inverse fails.
Taking r or s equal to 0 without choosing a new nonce. The signature degenerates and verification fails. Always check r != 0 and s != 0.
Assuming the group order is always prime. This group happens to have prime order 103, which is convenient, but in general the order can be composite. Then G must lie in the subgroup of large prime order (the cofactor issue), otherwise you run into Pohlig-Hellman (Lesson 8.3).

Lesson 8.1: ECC Basics, ECDH and ECDSA

Goals

Theory

The curve, its points, and the point at infinity

Point addition: geometry turned into formulas

Scalar multiplication and the ECDLP

ECDH and ECDSA

Demo

Lab

Key takeaways

Common pitfalls

Further reading

Trending Tags