Elliptic Curve Cryptography — ECC Explained

Elliptic curve cryptography was proposed by Neal Koblitz and Victor Miller independently in 1985. It took until the mid-2000s to see widespread adoption, partly due to NSA-promoted curves (P-256 etc.) that raised concerns about potential backdoors. The publication of Curve25519 by Daniel Bernstein in 2006 — a curve designed with a fully transparent, verifiable security rationale — resolved many concerns and drove modern ECC adoption.

Today, ECDH (Curve25519) is the default key exchange in TLS 1.3, Signal, WhatsApp, and most modern cryptographic protocols. EdDSA (Ed25519) replaced RSA and ECDSA for digital signatures in many systems. Understanding why ECC works means understanding elliptic curve point arithmetic — and why adding two points on a curve is a one-way function.

Why ECC Replaces RSA for Modern Cryptography

Elliptic curve cryptography (ECC) is a public-key cryptosystem that uses the algebraic structure of elliptic curves over finite fields. Its core mechanic: given a point G on a curve and a scalar k, computing k*G (point multiplication) is fast, but recovering k from the result is computationally infeasible — that's the trapdoor function. ECC achieves equivalent security to RSA with significantly smaller keys: a 256-bit ECC key provides roughly the same security as a 3072-bit RSA key.

ECC relies on the elliptic curve discrete logarithm problem (ECDLP). In practice, you define a curve (e.g., secp256r1, Curve25519), a base point G, and a large prime modulus. Private key is a random scalar; public key is the point multiplied by that scalar. The critical property: no sub-exponential algorithm exists for ECDLP, unlike RSA's integer factorization which has the General Number Field Sieve. This means ECC is faster per bit of security and uses less bandwidth — crucial for constrained environments.

Use ECC for TLS handshakes (ECDHE key exchange), digital signatures (ECDSA, EdDSA), and blockchain wallets. It's the default for modern protocols: TLS 1.3 mandates ECDHE, and Bitcoin/ Ethereum use secp256k1. Avoid ECC only when you need post-quantum security — Shor's algorithm breaks ECDLP. For everything else, ECC is the standard: smaller keys, faster operations, and no known practical attacks when implemented correctly.

Elliptic Curve Point Arithmetic

An elliptic curve is defined by y² = x³ + ax + b (mod p). Points on the curve (including a 'point at infinity' as identity element) form a group under a geometric addition rule: draw a line through two points, find the third intersection with the curve, reflect over the x-axis.

Scalar multiplication: nP = P + P + P + ... (n times). Given P and nP, finding n is the Elliptic Curve Discrete Logarithm Problem (ECDLP) — computationally infeasible for properly chosen curves.

The security of ECC relies on the hardness of ECDLP. Unlike RSA's factoring, there is no known sub-exponential algorithm for ECDLP on well-chosen curves over prime fields. This is why 256-bit ECC matches 3072-bit RSA.

ECDH Key Exchange

Elliptic Curve Diffie-Hellman (ECDH) allows two parties to establish a shared secret over an insecure channel. Each party generates a private scalar and derives a public point (scalar generator). They exchange public points and compute the secret as their own scalar times the other's public point. The result is the same point (shared secret) because scalar multiplication is commutative: a (b G) = b (a G) = (ab)*G.

Below is a Python example using the correct modern choice: Curve25519 via the cryptography library.

from cryptography.hazmat.primitives.asymmetric.x25519 import X25519PrivateKey
from cryptography.hazmat.primitives.serialization import Encoding, PublicFormat

# ECDH with Curve25519 — the correct modern choice

# Alice
alice_private = X25519PrivateKey.generate()
alice_public  = alice_private.public_key()

# Bob
bob_private = X25519PrivateKey.generate()
bob_public  = bob_private.public_key()

# Key exchange
alice_shared = alice_private.exchange(bob_public)
bob_shared   = bob_private.exchange(alice_public)

print(f'Shared secret match: {alice_shared == bob_shared}')
print(f'Key size: {len(alice_shared)} bytes = {len(alice_shared)*8} bits')
# Compare RSA: 256-bit ECC ≈ 3072-bit RSA in security
alice_pub_bytes = alice_public.public_bytes(Encoding.Raw, PublicFormat.Raw)
print(f'Public key size: {len(alice_pub_bytes)} bytes (vs RSA-3072: 384 bytes)')

Curve25519 — Why This Curve?

Curve25519, designed by Daniel J. Bernstein, is defined over the prime field 2^255 - 19 (hence the name). It was chosen with explicit, verifiable security criteria — unlike NIST P-curves whose seeds were derived from SHA-1 without explanation, raising backdoor concerns.

ECC vs RSA — Key Size Comparison

ECC achieves equivalent security with dramatically smaller keys, making it critical for constrained environments.

A TLS certificate with Ed25519 is 12x smaller than RSA-3072. Signing an Ed25519 signature takes ~10 microseconds vs ~1 millisecond for RSA-3072 — 100x faster. Key generation is also blindingly fast: Ed25519 keys are generated in microseconds, while RSA-3072 can take tens of milliseconds. This matters for ephemeral keys in protocols like TLS 1.3.

Digital Signatures with Ed25519

Ed25519 is the EdDSA variant using Curve25519. It provides fast, secure, and deterministic signatures. Unlike ECDSA (which requires a random nonce and is vulnerable to nonce reuse), Ed25519 derives the nonce deterministically from the message and private key via a hash. This eliminates the catastrophic risk of random number failures.

Ed25519 signatures are 64 bytes, public keys are 32 bytes. Verification is about 2x faster than ECDSA with P-256 and ~100x faster than RSA-3072. Combined with X25519 for key exchange, Ed25519 forms a complete modern signature and key-agreement suite.

ECDSA: Signing Without Exposing the Key

You want to prove you own a private key without showing it. That's the entire job of a digital signature. ECDSA does this using elliptic curves, and it does it with smaller signatures than RSA.

The algorithm has three moving parts: key generation, signing, and verification. Key generation is trivial — pick a random scalar, multiply the generator point. That's your public key. Signing uses the private key and the message hash to produce two integers, (r, s). Verification takes the public key, message hash, and signature pair, and checks that the math checks out.

Why not just encrypt the hash with the private key? Because ECDSA doesn't use encryption. It uses the discrete log problem. The signer proves they know the scalar without revealing it. That's the trick. Every ECDSA signature is a zero-knowledge proof in disguise.

The critical detail: never reuse a nonce. If you sign two different messages with the same nonce, anyone can recover your private key. This isn't theoretical. The PlayStation 3 hack happened because Sony reused the same nonce in two signatures. Don't be Sony.

// io.thecodeforge — dsa tutorial

import java.security.*;
import java.security.spec.*;

public class EcdsaSignVerify {
    public static void main(String[] args) throws Exception {
        KeyPairGenerator gen = KeyPairGenerator.getInstance("EC");
        gen.initialize(new ECGenParameterSpec("secp256r1"));
        KeyPair pair = gen.generateKeyPair();

        String message = "Transfer 500 BTC to address x";
        Signature signer = Signature.getInstance("SHA256withECDSA");
        signer.initSign(pair.getPrivate());
        signer.update(message.getBytes());
        byte[] signature = signer.sign();

        Signature verifier = Signature.getInstance("SHA256withECDSA");
        verifier.initVerify(pair.getPublic());
        verifier.update(message.getBytes());

        System.out.println("Signature valid: " + verifier.verify(signature));
    }
}

Domain Parameters: The Shared Stage Every ECDSA Implementation Needs

ECDSA doesn't work in a vacuum. Both signer and verifier must agree on the same elliptic curve domain parameters before anything happens. These parameters define the mathematical stage where the algorithm performs.

The six parameters are: the prime p defining the field, the coefficients a and b of the curve equation, the base point G with prime order n, and the cofactor h. If any of these differ between signer and verifier, the signature verification fails silently — or worse, passes with the wrong key.

Standardized curves like secp256k1 (Bitcoin) and P-256 (NIST) ship these parameters as part of the spec. But if you're defining custom curves — and you shouldn't be — you must generate and validate them properly. Generation requires checking that the order n is prime, that G is on the curve, that the curve has no singularities, and that the cofactor is small.

Most libraries handle domain parameter validation automatically when you specify a standard curve name. The moment you hardcode your own hex strings for these values, you're taking on the full burden of correctness. One wrong byte in the base point and your entire PKI is worthless.

// io.thecodeforge — dsa tutorial

import java.security.spec.*;

public class DomainParamsCheck {
    public static void main(String[] args) throws Exception {
        // secp256r1 domain parameters from standard
        ECParameterSpec spec = ECNamedCurveTable.getParameterSpec("secp256r1");
        
        ECPoint g = spec.getGenerator();
        System.out.println("Generator order: " + spec.getOrder());
        System.out.println("Cofactor: " + spec.getCofactor());
        
        // Quick sanity: G must be on curve
        boolean onCurve = isOnCurve(g, spec.getCurve());
        System.out.println("G on curve: " + onCurve);
    }

    static boolean isOnCurve(ECPoint p, EllipticCurve c) {
        if (p == ECPoint.POINT_INFINITY) return true;
        java.math.BigInteger x = p.getAffineX();
        java.math.BigInteger y = p.getAffineY();
        java.math.BigInteger rhs = y.multiply(y).mod(c.getField().getP());
        java.math.BigInteger lhs = x.multiply(x).multiply(x)
            .add(c.getA().multiply(x)).add(c.getB()).mod(c.getField().getP());
        return rhs.equals(lhs);
    }
}