Elliptic Curve Cryptography (ECC), in depth: the group law on a toy curve, constant-time scalar multiplication, ECDH, curve choice and the attacks that skip validation

The curve and the addition rule

Over a prime field of integers modulo p, a short Weierstrass curve is the set of pairs (x, y) satisfying y² = x³ + ax + b, plus one extra point O, the point at infinity. The condition 4a³ + 27b² ≠ 0 mod p rules out cusps and self-intersections. Over the real numbers the curve looks like the picture below, and the addition rule is geometric: draw the line through P and Q, find the third point R where it meets the curve, and reflect it. Adding a point to itself uses the tangent line. O acts as zero: P + O = P, and a point plus its reflection gives O.

Over a finite field the picture becomes a scatter of points, but the algebra survives. For P ≠ Q the slope is λ = (y₂ − y₁)/(x₂ − x₁); for doubling it is λ = (3x₁² + a)/(2y₁). Then x₃ = λ² − x₁ − x₂ and y₃ = λ(x₁ − x₃) − y₁. Division means multiplying by a modular inverse, computed with the extended Euclidean algorithm or Fermat's little theorem. The resulting operation is associative and commutative, so the points form an abelian group, and Hasse's theorem says the number of points is within 2√p of p + 1.

Worked example on a 101-point curve

Take p = 89, a = 2, b = 5. This curve has exactly 101 points including O, and 101 is prime, so every point except O generates the whole group. Pick G = (0, 19). Check it: 19² = 361 = 4·89 + 5, and 0³ + 2·0 + 5 = 5, so G is on the curve.

Double it. λ = (3·0² + 2)/(2·19) = 2/38. The inverse of 38 mod 89 is 82 (38·82 = 3116 = 35·89 + 1), so λ = 2·82 mod 89 = 75. Then x₃ = 75² − 0 − 0 = 5625 ≡ 18 and y₃ = 75·(0 − 18) − 19 = −1369 ≡ 55 (mod 89). So 2G = (18, 55). Adding G again gives 3G = (75, 9). Keep going and 100G = (0, 70), which is −G, the reflection of G, and 101G = O. The group wraps around after n = 101 steps; n is called the order of G.

The one-way function is now visible. Given k = 17, computing 17G takes a handful of additions. Given only the point 17G, recovering 17 is the elliptic curve discrete logarithm problem. On this toy curve you could try all 101 values; on a curve with about 2²⁵⁶ points, the best known general attack (Pollard's rho) needs about 2¹²⁸ operations. Unlike integer factoring, there is no known sub-exponential attack on well-chosen curves, which is why the keys can be so much smaller than RSA's.

Scalar multiplication and constant time

Private keys are integers k; public keys are points kG. Computing kG uses the binary expansion of k, like fast modular exponentiation. Textbook double-and-add doubles for every bit and adds only when the bit is 1. That leaks: the time and power trace of a multiplication reveal the bit pattern of the secret, and real attacks have recovered keys from timing over a network and from cache behaviour on shared machines. The Montgomery ladder fixes the operation sequence by doing one add and one double per bit regardless of its value.

p, a, b = 89, 2, 5          # y^2 = x^3 + 2x + 5 over F_89
O = None                    # point at infinity: the identity
G, n = (0, 19), 101         # generator and its (prime) order

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

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

def ladder(k, P):
    """Montgomery ladder: one add and one double per bit, whatever the bit."""
    R0, R1 = O, P
    for bit in bin(k)[2:]:
        if bit == "1":
            R0, R1 = add(R0, R1), add(R1, R1)
        else:
            R0, R1 = add(R0, R0), add(R0, R1)
    return R0

On the toy curve, ladder(17, G) returns (82, 2). The ladder keeps the invariant R1 − R0 = P, which also makes it suit x-only arithmetic on Montgomery curves, the reason X25519 uses it. Note what this toy does not do: Python's big integers, the if on the bit and the special-casing of O are all data-dependent. Production code selects between R0 and R1 with constant-time conditional swaps, uses fixed-width field arithmetic and complete addition formulas that have no special cases. That is the main reason never to write your own.

Coordinates and encodings

Every affine addition needs a modular inverse, which costs as much as dozens of multiplications. Real implementations use projective or Jacobian coordinates, representing a point as (X, Y, Z) with x = X/Z and y = Y/Z (projective) or x = X/Z², y = Y/Z³ (Jacobian). Additions then use only multiplications, and a single inversion at the end converts back to affine. A 256-bit scalar multiplication becomes about 256 doublings and 256 additions of a dozen field multiplications each, a few tens of microseconds on a modern CPU.

Encoding matters too. An uncompressed point is the byte 0x04 followed by x and y; a compressed one is 0x02 or 0x03 (the parity of y) followed by x, and the receiver recomputes y with a square root. X25519 sends only a 32-byte u-coordinate.

Key agreement with ECDH

Elliptic curve Diffie-Hellman works exactly like classic Diffie-Hellman with point multiplication in place of exponentiation. On the toy curve, Alice picks a = 17 and publishes A = 17G = (82, 2). Bob picks b = 42 and publishes B = 42G = (26, 79). Alice computes 17B and Bob computes 42A; both get (17·42 mod 101)G = 7G = (81, 79). An eavesdropper sees G, A and B and would need a discrete logarithm to get the shared point.

The shared point is not a key. Its x-coordinate has structure, and different sessions must derive independent keys, so pass it through a key derivation function with context. In real code that looks like this:

from cryptography.hazmat.primitives import hashes, serialization
from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives.asymmetric.x25519 import X25519PrivateKey
from cryptography.hazmat.primitives.kdf.hkdf import HKDF

# X25519: the common choice for new key agreement
alice, bob = X25519PrivateKey.generate(), X25519PrivateKey.generate()
shared = alice.exchange(bob.public_key())          # 32 raw bytes, never a key by itself
key = HKDF(algorithm=hashes.SHA256(), length=32, salt=None,
           info=b"myproto v1 session key").derive(shared)

# P-256: decode the peer's bytes through the validating API, then exchange
peer_bytes = ec.generate_private_key(ec.SECP256R1()).public_key().public_bytes(
    serialization.Encoding.X962, serialization.PublicFormat.UncompressedPoint)
peer = ec.EllipticCurvePublicKey.from_encoded_point(ec.SECP256R1(), peer_bytes)
mine = ec.generate_private_key(ec.SECP256R1())
shared_p256 = mine.exchange(ec.ECDH(), peer)

Two details carry the security here. from_encoded_point rejects bytes that are not a point on P-256, which is the validation step discussed below. And the HKDF info string binds the key to a protocol and version, so the same shared secret can never be reused as a key elsewhere. Plain ECDH as shown is anonymous: without authenticating the public keys (certificates or signatures), a man in the middle simply runs two exchanges.

Choosing a curve

For new key agreement, X25519 is the usual default: its API takes 32 bytes and returns 32 bytes, every 32-byte string is accepted as a public key by design, and the ladder is built in. Choose P-256 when compliance requires NIST curves or hardware only supports them. The cofactor is the ratio of the full group order to the prime subgroup used. A cofactor of 8 means some points have tiny orders; X25519 handles this by clamping the private scalar to a multiple of 8, but protocols that compare or hash public keys must still account for equivalent encodings.

Attacks when checks are skipped

• Invalid-curve attacks. The addition formulas never use b. If a server multiplies its private key by an attacker-supplied point without checking that it lies on the curve, the attacker can choose a point on a different curve with a small subgroup, learn the key modulo that small order, and combine many such answers with the Chinese remainder theorem. Always check on_curve and reject O for short Weierstrass curves; libraries do this when you decode via their APIs.
• Small-subgroup and all-zero outputs. On cofactor curves, a low-order public key forces the shared secret into a tiny set. RFC 7748 notes that X25519 can produce an all-zero output; check for it if your protocol needs contributory behaviour. pyca/cryptography raises an error in that case.
• Weak curves. Some curves make the discrete log easy. Our toy y² = x³ + x + 3 over F₉₇ has exactly 97 points, the same as p; such anomalous curves fall to Smart's attack in polynomial time. Curves with small embedding degree fall to pairing-based reductions. Use only standard named curves.
• Side channels. Variable-time scalar multiplication or table lookups indexed by secret bits leak keys through timing and caches.
• Nonce failures in signatures. Reused or biased ECDSA nonces leak the private key; see the ECDSA article for the arithmetic.

Quantum computers and the comparison with RSA

Shor's algorithm solves the elliptic curve discrete log in polynomial time on a large fault-tolerant quantum computer, and ECC falls faster than RSA at equal classical security because its keys are smaller. No such machine exists yet, but recorded traffic can be decrypted later, so key agreement is moving first. Browsers and major servers already deploy the hybrid X25519MLKEM768 group in TLS 1.3, which combines X25519 with the post-quantum ML-KEM so the session stays secure if either holds. Signatures are migrating more slowly. The comparison with RSA is otherwise straightforward: ECC keys and signatures are far smaller and key generation is fast, while RSA verification is faster and its implementation pitfalls are better known to auditors.

What to do next

1. Run the toy code above, check on_curve for every multiple of G, and confirm that 101G is O.
2. Repeat the ECDH example with your own secrets and verify both sides agree.
3. Feed add a point that is not on the curve and see that it still returns an answer; then add the check that rejects it.
4. Use X25519 with HKDF for new key agreement, P-256 where compliance requires it, and always decode peer keys through the library's validating API.
5. Inventory every place your systems use ECDH or ECDSA and record which will need a hybrid or post-quantum replacement, starting with key exchange.
6. Never ship hand-written curve arithmetic; use a maintained, constant-time library.