Skip to main content
Be Bitwise

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:

text
y^2 = x^3 + ax + b

Over 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.

Key Concept

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):

text
1. Hash the message: h = hash(message)
2. Pick a random nonce k
3. 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 n
6. Signature is (r, s)

Verification:

text
1. Hash the message: h = hash(message)
2. Compute u1 = h * s^(-1) mod n
3. Compute u2 = r * s^(-1) mod n
4. Compute point R' = u1*G + u2*public_key
5. If R'.x mod n == r, the signature is valid

EdDSA 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 LevelRSA Key SizeECC Key SizeRatio
80-bit1024 bits160 bits6:1
128-bit3072 bits256 bits12:1
192-bit7680 bits384 bits20:1
256-bit15360 bits521 bits30: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.