Elliptic Curve Cryptography: Smaller Keys, Same Security

1. Why Should You Care?

Compare these two keys with equivalent security:

RSA-3072 public key (384 bytes):
-----BEGIN PUBLIC KEY-----
MIIBojANBgkqhkiG9w0BAQEFAAOCAY8AMIIBigKCAYEA2a3Y...
[about 12 lines of base64]
-----END PUBLIC KEY-----

ECC P-256 public key (65 bytes, or 91 with encoding):
-----BEGIN PUBLIC KEY-----
MFkwEwYHKoZIzj0CAQYIKoZIzj0DAQcDQgAE...
[2 lines of base64]
-----END PUBLIC KEY-----

Same security, 6x smaller. This matters for:

• Certificates in HTTPS (smaller = faster handshakes)
• IoT devices (limited storage and bandwidth)
• Mobile apps (faster operations, less battery)
• Blockchain (every byte costs money)

2. Definition

Elliptic Curve Cryptography (ECC) uses the algebraic structure of elliptic curves over finite fields to create cryptographic operations.

The security is based on the Elliptic Curve Discrete Logarithm Problem (ECDLP): given points P and Q = kP on a curve, finding k is computationally infeasible.

The one-way function:

Easy:     k × P = Q    (scalar multiplication)
          Given k and P, compute Q

Hard:     Q / P = k    (discrete logarithm)
          Given P and Q, find k

3. What Is an Elliptic Curve?

The Mathematical Form

Over real numbers, an elliptic curve is:

y² = x³ + ax + b

Where: 4a³ + 27b² ≠ 0 (ensures no singularities)

Visual Shape

        y
        │     *
        │   *   *
        │  *     *
    ────┼──*─────*──────── x
        │  *     *
        │   *   *
        │     *
        │

Cryptographic Curves Use Finite Fields

In cryptography, we don't use real numbers.
We use integers modulo a prime p:

y² ≡ x³ + ax + b  (mod p)

Example: P-256 curve
p = 2²⁵⁶ - 2²²⁴ + 2¹⁹² + 2⁹⁶ - 1

All operations wrap around at p
Results are always integers from 0 to p-1

4. Point Addition: The Core Operation

Geometric Intuition (Over Real Numbers)

To add points P and Q:

1. Draw a line through P and Q
2. The line intersects the curve at a third point R
3. Reflect R over the x-axis to get P + Q

        y
        │     P*
        │   *   *
        │  *  Q  *
    ────┼──*─────*──────── x
        │  *  R' *  (P + Q)
        │   *   *
        │     R

Point Doubling

To compute P + P = 2P:

1. Draw the tangent line at P
2. The tangent intersects the curve at R
3. Reflect R over the x-axis to get 2P

The Point at Infinity

Special point O (identity element):

P + O = P
P + (-P) = O

-P is P reflected over the x-axis

5. Scalar Multiplication: Where Security Lives

Computing Q = kP

k = 7, P = some point

Naive: P + P + P + P + P + P + P = 7P
       (7 additions)

Double-and-add (efficient):
7 = 111 in binary

Step 1: P
Step 2: 2P (double)
Step 3: 2P + P = 3P (add, because bit is 1)
Step 4: 6P (double)
Step 5: 6P + P = 7P (add, because bit is 1)

Only ~log₂(k) operations

The Hard Problem

Given: P (base point, public)
       Q = kP (result point, public)

Find:  k (the scalar, private key)

For 256-bit curves:
- k is one of ~2²⁵⁶ possibilities
- No known shortcuts (unlike factoring)
- Best attack: ~2¹²⁸ operations (birthday bound)

6. Popular Curves

NIST Curves

P-256 (secp256r1, prime256v1):
- 256-bit prime field
- Most widely deployed
- NIST standardized, NSA designed
- Some distrust due to unexplained constants

P-384 (secp384r1):
- 384-bit prime field
- Higher security margin
- Used in government applications

P-521 (secp521r1):
- 521-bit prime field
- Highest security, slower
- Rarely needed

Curve25519 (Modern Choice)

Designed by Daniel Bernstein:
- 255-bit prime field (2²⁵⁵ - 19)
- Resistant to timing attacks by design
- Faster than NIST curves
- No unexplained constants
- Used in: Signal, WhatsApp, SSH, WireGuard

Variants:
- X25519: Key exchange (ECDH)
- Ed25519: Signatures (EdDSA)

Bitcoin’s Curve

secp256k1:
- 256-bit Koblitz curve
- Slightly faster than P-256
- Used by Bitcoin, Ethereum
- Different from P-256 (secp256r1)

7. ECC Key Generation

from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.backends import default_backend

# Generate key pair
private_key = ec.generate_private_key(
    ec.SECP256R1(),  # P-256 curve
    default_backend()
)
public_key = private_key.public_key()

# What's inside:
# private_key: random 256-bit integer k
# public_key: point Q = k × G (G is the generator point)

# Extract the numbers
private_numbers = private_key.private_numbers()
public_numbers = private_numbers.public_numbers

print(f"Private key (k): {private_numbers.private_value}")
print(f"Public key (x): {public_numbers.x}")
print(f"Public key (y): {public_numbers.y}")

Key Sizes

Curve      | Private Key | Public Key | Security
-----------+-------------+------------+-----------
P-256      | 32 bytes    | 65 bytes*  | 128 bits
P-384      | 48 bytes    | 97 bytes*  | 192 bits
P-521      | 66 bytes    | 133 bytes* | 256 bits
Curve25519 | 32 bytes    | 32 bytes   | 128 bits

* Uncompressed format (04 || x || y)
  Compressed: (02/03 || x), about half size

8. ECDSA: Elliptic Curve Digital Signatures

Signing Process

To sign message m with private key k:

1. Compute hash: e = HASH(m)
2. Generate random nonce r (CRITICAL: must be random)
3. Compute R = r × G
4. Get x-coordinate: rx = Rx mod n
5. Compute s = r⁻¹(e + rx × k) mod n
6. Signature is (rx, s)

Verification Process

To verify signature (rx, s) on message m with public key Q:

1. Compute hash: e = HASH(m)
2. Compute u1 = e × s⁻¹ mod n
3. Compute u2 = rx × s⁻¹ mod n
4. Compute R = u1 × G + u2 × Q
5. Check: Rx mod n == rx?

Code Example

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import ec

# Generate keys
private_key = ec.generate_private_key(ec.SECP256R1())
public_key = private_key.public_key()

# Sign
message = b"Hello, ECDSA!"
signature = private_key.sign(
    message,
    ec.ECDSA(hashes.SHA256())
)

# Verify
try:
    public_key.verify(
        signature,
        message,
        ec.ECDSA(hashes.SHA256())
    )
    print("Signature valid!")
except Exception:
    print("Signature invalid!")

9. EdDSA: The Modern Alternative

Why EdDSA Over ECDSA?

ECDSA problems:
1. Needs secure random nonce per signature
   - PlayStation 3 hack: reused nonce → private key leaked
   - Same nonce twice = game over

2. Complex to implement securely
   - Timing attacks
   - Fault attacks

EdDSA (Ed25519) solutions:
1. Deterministic nonce from message hash
   - No random number needed during signing
   - Can't accidentally reuse

2. Designed for constant-time implementation
   - Resistant to timing attacks

3. Faster and simpler

Ed25519 Example

from cryptography.hazmat.primitives.asymmetric import ed25519

# Generate keys
private_key = ed25519.Ed25519PrivateKey.generate()
public_key = private_key.public_key()

# Sign (no algorithm needed - it's built-in)
message = b"Hello, Ed25519!"
signature = private_key.sign(message)

# Verify
try:
    public_key.verify(signature, message)
    print("Signature valid!")
except Exception:
    print("Signature invalid!")

10. ECDH: Key Exchange with Curves

from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.kdf.hkdf import HKDF

# Alice generates her key pair
alice_private = ec.generate_private_key(ec.SECP256R1())
alice_public = alice_private.public_key()

# Bob generates his key pair
bob_private = ec.generate_private_key(ec.SECP256R1())
bob_public = bob_private.public_key()

# Both compute the same shared secret
alice_shared = alice_private.exchange(ec.ECDH(), bob_public)
bob_shared = bob_private.exchange(ec.ECDH(), alice_public)

assert alice_shared == bob_shared  # Same!

# Derive actual key from shared secret
derived_key = HKDF(
    algorithm=hashes.SHA256(),
    length=32,
    salt=None,
    info=b'handshake data'
).derive(alice_shared)

X25519: Modern ECDH

from cryptography.hazmat.primitives.asymmetric import x25519

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

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

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

assert alice_shared == bob_shared

11. ECC Security Considerations

Nonce Reuse in ECDSA

If you sign two different messages with the same nonce r:

Signature 1: s1 = r⁻¹(e1 + rx × k)
Signature 2: s2 = r⁻¹(e2 + rx × k)

From these:
s1 - s2 = r⁻¹(e1 - e2)
r = (e1 - e2) / (s1 - s2)

Then:
k = (s1 × r - e1) / rx

Private key recovered!

Sony's PlayStation 3 used fixed r → hacked

Curve Choice Matters

Weak curves to avoid:
- Curves with small embedding degree (pairing attacks)
- Curves over binary fields (recent attacks)
- Curves with suspicious constants

Safe choices:
- Curve25519/Ed25519 (recommended)
- P-256 (widely supported)
- P-384 (higher security needs)

Implementation Attacks

Timing attacks:
- Measure how long operations take
- Infer secret bits from timing

Defenses:
- Use constant-time implementations
- Libraries like libsodium handle this
- Curve25519 designed to resist

Invalid curve attacks:
- Send points not on the curve
- Weak group structure

Defenses:
- Always validate points
- Use Montgomery curves (Curve25519)

12. ECC vs RSA: Final Comparison

                    | RSA              | ECC
--------------------+------------------+-----------------
Key size (128-bit)  | 3072 bits        | 256 bits
Key size (256-bit)  | 15360 bits       | 512 bits
Key generation      | Slow (primality) | Fast
Signing             | Slower           | Faster
Verification        | Faster           | Slower
Encryption support  | Direct (hybrid)  | Only key exchange
Quantum resistance  | Broken by Shor   | Broken by Shor
Maturity            | 1977             | 1985+
Adoption            | Legacy dominant  | Modern dominant

13. Common Misconceptions

14. Summary

Three things to remember:

1. ECC achieves same security with smaller keys. 256-bit ECC ≈ 3072-bit RSA. This means faster operations, smaller certificates, less bandwidth.

2. Curve choice matters. Use Curve25519/Ed25519 for new projects. Fall back to P-256 for compatibility.

3. Never reuse ECDSA nonces. One reuse = private key compromised. Prefer Ed25519’s deterministic signing.

15. What’s Next

We’ve seen how RSA uses factoring and ECC uses curves. But both need to solve a fundamental problem: how do two parties who’ve never met agree on a shared secret?

In the next article: Diffie-Hellman Key Exchange—the mathematical magic that makes secure communication possible without pre-shared secrets.