Elliptic Curves & Digital Signatures
Asymmetric Encryption · Networking & Cryptography track
4 min read
In this module
Curves That Secure the Internet
Elliptic Curve Cryptography (ECC) delivers the same security as RSA and classic Diffie-Hellman with dramatically smaller key sizes. A 256-bit ECC key matches a 3072-bit RSA key for strength. Faster operations, less bandwidth, smaller certificates. That trifecta is why ECC has become the dominant choice for modern cryptographic systems.
What Is an Elliptic Curve?
An elliptic curve (for cryptography) is defined by an equation of the form:
y^2 = x^3 + ax + bOver real numbers, this produces a smooth curve. In cryptography, we work over a finite field (modular arithmetic), which turns the curve into a scattered set of points. These points form a mathematical group — you can "add" points together using a geometric construction.
Point addition: Given two points P and Q on the curve, draw a line through them. It hits the curve at a third point. Reflect that point across the x-axis and you have P + Q.
Scalar multiplication: Adding a point to itself k times (P + P + ... + P = kP) is the core operation. Computing kP when you know k and P is fast. Finding k when you know only P and kP — the elliptic curve discrete logarithm problem — is computationally infeasible.
Elliptic curve cryptography relies on the difficulty of the elliptic curve discrete logarithm problem: given points P and kP on a curve, finding the scalar k is computationally infeasible. This is even harder than the integer DLP, enabling equivalent security with much smaller keys.
Common Curves
P-256 (secp256r1 / prime256v1): A NIST-standardised curve, widely used in TLS and code signing. Some controversy hangs over it because NIST's parameter generation process was never fully transparent.
Curve25519: Designed by Daniel J. Bernstein with security, speed, and implementation simplicity as the explicit goals. It powers Signal, WireGuard, and SSH. The design closes the door on entire classes of implementation bugs.
secp256k1: The curve Bitcoin and Ethereum use for digital signatures.
P-384 and P-521: Larger NIST curves for higher security requirements.
Digital Signatures with ECDSA
ECDSA (Elliptic Curve Digital Signature Algorithm) is the elliptic curve version of DSA. It is used to sign TLS certificates, authenticate software updates, and verify cryptocurrency transactions.
The signing process (simplified):
1. Hash the message: h = hash(message)2. Pick a random nonce k3. Compute the point R = kG (where G is the curve's generator point)4. Compute r = R.x mod n (the x-coordinate of R modulo the curve order)5. Compute s = k^(-1) * (h + r * private_key) mod n6. Signature is (r, s)Verification:
1. Hash the message: h = hash(message)2. Compute u1 = h * s^(-1) mod n3. Compute u2 = r * s^(-1) mod n4. Compute point R' = u1*G + u2*public_key5. If R'.x mod n == r, the signature is validEdDSA and Ed25519
EdDSA (Edwards-curve Digital Signature Algorithm) is a modern alternative to ECDSA built on twisted Edwards curves. Ed25519 is the most popular variant, riding on Curve25519.
EdDSA has several advantages over ECDSA:
- Deterministic signatures: No random nonce is needed (the nonce is derived from the message and private key), wiping out a class of catastrophic implementation bugs
- Faster: Optimised arithmetic on Edwards curves
- Simpler implementation: Fewer edge cases and failure modes
Ed25519 shows up in SSH, Signal, TLS 1.3, and many cryptocurrency protocols.
The Nonce Problem in ECDSA
ECDSA signatures require a random nonce k for each signature. If that nonce is predictable, reused, or even slightly biased, the private key falls out.
In 2010, the hacker group fail0verflow recovered the private key Sony used to sign PlayStation 3 firmware. Why? Sony used the same nonce for every signature. Once you have two signatures sharing k, computing the private key is trivial.
One implementation mistake — reusing a random number — completely broke the security of a billion-dollar console platform. EdDSA's deterministic nonce generation exists precisely to slam this door shut.
ECC vs. RSA Key Sizes
| Security Level | RSA Key Size | ECC Key Size | Ratio |
|---|---|---|---|
| 80-bit | 1024 bits | 160 bits | 6:1 |
| 128-bit | 3072 bits | 256 bits | 12:1 |
| 192-bit | 7680 bits | 384 bits | 20:1 |
| 256-bit | 15360 bits | 521 bits | 30:1 |
The gap widens dramatically at higher security levels. That's why TLS 1.3 overwhelmingly favours ECDHE for key exchange and ECDSA or EdDSA for signatures.
The Quantum Threat
Like RSA, ECC falls to quantum computers running Shor's algorithm. A sufficiently powerful quantum machine could solve the ECDLP efficiently. Post-quantum algorithms based on lattices, codes, or hash functions are being standardised to eventually replace both RSA and ECC. NIST finalised its first post-quantum standards in 2024, kicking off the transition.