ECC

Elliptic Curve Cryptography (ECC) provides the same security as RSA with much smaller key sizes. CTF challenges use ECC for key exchange (ECDH) and digital signatures (ECDSA).

Elliptic curve illustration — Elliptic curve point addition illustration

At a high level, ECC uses points on an elliptic curve instead of arithmetic over large integers (like RSA). A point is a pair (x, y) that satisfies the curve equation $y^2 = x^3 + ax + b$ (mod p).
A private key is a small integer d. The corresponding public key is the point Q = d·G, where G is a fixed generator point on the curve and · denotes scalar multiplication (repeated point addition).
Security comes from the Elliptic Curve Discrete Logarithm Problem (ECDLP): given G and Q = d·G, recovering d is computationally infeasible for well-chosen curves and parameters.
Common uses:
- ECDH: two parties derive a shared secret by multiplying their private scalar with the other party's public point.
- ECDSA: signing uses a per-message random scalar k and produces a signature (r, s) derived from kG and the signer's private key.
Practical benefits for beginners to remember:
- Much smaller keys than RSA for equivalent security (lighter storage and bandwidth).
- Faster on devices with limited resources (important in embedded/IoT contexts).
- Beware: incorrect randomness (reusing k) or weak curves can completely break security.

ECC vs RSA

Below is a concise comparison between ECC and RSA to help beginners understand trade-offs.

Parameters	ECC	RSA
Working algorithm	ECC works on the mathematical model of elliptic curves (points and scalar multiplication).	RSA is based on the difficulty of integer prime factorization.
Bandwidth savings	ECC gives significant bandwidth savings due to smaller key and signature sizes.	RSA provides much lesser bandwidth saving than ECC.
Encryption process	Encryption (or key agreement) tends to be faster with ECC for equivalent security levels.	Encryption is slower than ECC for equivalent security levels.
Decryption process	Decryption (or some operations) can be slower due to certain curve operations and protocol details.	Decryption can be faster in some RSA implementations (depends on exponent choices and CRT).
Security	ECC is considered stronger per-bit and is widely adopted for modern systems.	RSA requires much larger keys to reach the same security margin and is losing favor for new systems.

Key Length Comparison (approximate equivalence)

Security (bits)	RSA key length required	ECC key length required
80	1024	160–223
112	2048	224–255
128	3072	256–383
192	7680	384–511
256	15360	512+

Note: The ranges for ECC reflect how different curves and implementations map to security levels - standard recommendations today are at least 256-bit ECC (P-256 / secp256r1) for typical security.

What Is an Elliptic Curve?

y^2 \equiv x^3 + ax + b \pmod{p}

where $p$ is prime and $4a^3 + 27b^2 \not\equiv 0 \pmod{p}$ (non-singular).

Points on the curve form a group under a special addition operation, plus a "point at infinity" (the identity element).

Standard Named Curves

Curve	p bits	Used in
secp256k1	256	Bitcoin, many CTFs
secp256r1 (P-256)	256	TLS, JWTs
secp384r1 (P-384)	384	High-security TLS
Curve25519	255	Signal, modern TLS
secp192r1	192	Older applications

Point Addition

The fundamental operation: given points $P$ , $Q$ on the curve, $P + Q = R$ is another point on the curve.

For $P \neq Q$ , with slope $m \equiv \dfrac{y_2 - y_1}{x_2 - x_1} \pmod{p}$ :

\begin{aligned} x_3 &\equiv m^2 - x_1 - x_2 \pmod{p} \\ y_3 &\equiv m(x_1 - x_3) - y_1 \pmod{p} \end{aligned}

For point doubling ( $P = Q$ ):

m \equiv \frac{3x_1^2 + a}{2y_1} \pmod{p}

Scalar Multiplication

kP = \underbrace{P + P + \cdots + P}_{k \text{ times}}

This is fast (using double-and-add) but the inverse - finding $k$ given $P$ and $kP$ - is the Elliptic Curve Discrete Logarithm Problem (ECDLP), which is computationally hard.

Python with SageMath

from sage.all import *

# Define curve secp256k1
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a, b = 0, 7
E = EllipticCurve(GF(p), [a, b])

# Generator point
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
G = E(Gx, Gy)

# Key generation
n = int(G.order())       # group order
private_key = randint(1, n-1)
public_key = private_key * G

print(f"Private key: {hex(private_key)}")
print(f"Public key: ({hex(int(public_key.xy()[0]))}, {hex(int(public_key.xy()[1]))})")

Python with PyCryptodome

from Crypto.PublicKey import ECC

# Generate keypair
key = ECC.generate(curve='P-256')
print(key.d)    # private key
print(key.pointQ)  # public key

# Import from PEM
key = ECC.import_key(open('private.pem').read())

# Get public key components
Q = key.pointQ
print(f"Qx = {Q.x}")
print(f"Qy = {Q.y}")

ECDSA

from Crypto.PublicKey import ECC
from Crypto.Signature import DSS
from Crypto.Hash import SHA256

# Sign
key = ECC.generate(curve='P-256')
h = SHA256.new(b"message to sign")
signer = DSS.new(key, 'fips-186-3')
signature = signer.sign(h)

# Verify
verifier = DSS.new(key.public_key(), 'fips-186-3')
try:
    verifier.verify(h, signature)
    print("Valid!")
except ValueError:
    print("Invalid!")

ECDSA signature structure: $(r, s)$ where:

$r = (kG)_x \bmod n$ (the $x$ -coordinate of $kG$ , modulo the curve order)
$s \equiv k^{-1}\bigl(H(m) + dr\bigr) \pmod{n}$

ECDH Key Exchange

from Crypto.PublicKey import ECC

# Alice
alice_key = ECC.generate(curve='P-256')
alice_public = alice_key.public_key()

# Bob
bob_key = ECC.generate(curve='P-256')
bob_public = bob_key.public_key()

# Shared secret (using sage for the multiplication)
from sage.all import *
# Both compute: shared = d_alice * Q_bob = d_bob * Q_alice

Identifying Weak Curves

In CTF challenges, the curve might be intentionally weak:

from sage.all import *

# Check if curve order is smooth (small factors → Pohlig-Hellman)
E = EllipticCurve(GF(p), [a, b])
n = E.order()
print(f"Order: {n}")
print(f"Factorization: {factor(n)}")

# If n has small factors → Pohlig-Hellman ECDLP attack
# If n = p (anomalous curve) → Smart's attack
print(f"Is anomalous? {n == p}")

# Is it supersingular? (MOV attack possible)
print(E.is_supersingular())

See also

RSA Basics - RSA overview and common attacks.
Hash Functions - Hashing concepts used in signatures and protocols.

ECC Attacks

Elliptic Curve Cryptography (ECC) provides strong security when implemented correctly. CTF crypto challenges target implementation flaws - especially nonce reuse in ECDSA, invalid curve attacks, and small subgroup attacks.

ECC Quick Review

Curve over $\mathbb{F}_p$ :

y^2 \equiv x^3 + ax + b \pmod{p}

Key generation: fixed generator $G$ ; private key $d$ ; public key $Q = dG$ .

ECDSA sign (with per-signature nonce $k$ ):

r = (kG)_x \bmod n, \qquad s \equiv k^{-1}\bigl(h + dr\bigr) \pmod{n}

where $h$ is the message hash. Verify: with $u_1 = h s^{-1}$ , $u_2 = r s^{-1}$ , check $(u_1 G + u_2 Q)_x \equiv r \pmod{n}$ .

Attack: ECDSA Nonce Reuse

If the same nonce k is used for two different messages, the private key is trivially recoverable:

# Given: two signatures (r1,s1), (r2,s2) for messages m1, m2
# with the same nonce k (we know r1 == r2 since r = (k·G).x)

# s1 = k⁻¹(h1 + d·r) mod n
# s2 = k⁻¹(h2 + d·r) mod n
# → s1 - s2 = k⁻¹(h1 - h2) mod n
# → k = (h1 - h2) · (s1 - s2)⁻¹ mod n
# → d = (s1·k - h1) · r⁻¹ mod n

from Crypto.PublicKey.ECC import EccKey
import hashlib

n  = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141  # secp256k1

def modinv(a, m):
    return pow(a, -1, m)

h1 = int(hashlib.sha256(msg1).hexdigest(), 16)
h2 = int(hashlib.sha256(msg2).hexdigest(), 16)
r, s1, s2 = r, s1, s2  # from given signatures

k = ((h1 - h2) * modinv(s1 - s2, n)) % n
d = ((s1 * k - h1) * modinv(r, n)) % n

print(f"Private key d = {hex(d)}")

Attack: Short Nonce / Biased Nonce (Lattice Attack)

If nonces are truncated (short) or biased (e.g., MSB always 0), the private key can be recovered via a lattice (Hidden Number Problem). Requires multiple signatures.

This is solved using SageMath with LLL reduction:

from sage.all import *

# Set up the lattice for HNP
# See: https://crypto.stackexchange.com/questions/44644
# For short nonces: nonce k has top l bits = 0
# This becomes a bounded-norm vector in a lattice

n = ...   # group order
signatures = [(h1, r1, s1), (h2, r2, s2), ...]  # collected from oracle

l = 8  # number of known MSB bits of k (0)

# Build matrix and run LLL
# (Implementation omitted for brevity - use known PoC scripts)

Reference: CryptoHack Ledger Donjon CTF writeup for full implementation.

Attack: Invalid Curve Attack

If the server accepts arbitrary curve points without checking they're actually on the curve, you can send points from weak curves (with small subgroup order) to recover the private key bit by bit.

# Send a point P' on a weaker curve y^2 = x^3 + ax + b' (mod p)
# with small group order q
# Server computes d·P' and returns some function of the result
# Since q is small, brute-force d mod q
# Use CRT to recover full d from several such residues

Attack: Smart's Attack (ECDLP on Anomalous Curves)

For curves where $\#E(\mathbb{F}_p) = p$ (anomalous curves), the ECDLP can be solved in polynomial time using a lift to $p$ -adic numbers.

def smart_attack(P, Q, p):
    """Solve Q = k*P on an anomalous curve over Fp."""
    from sage.all import EllipticCurve, GF, Qp, ZZ

    E = P.curve()
    Eqp = EllipticCurve(Qp(p, 2), [ZZ(a) + p * ZZ(0) for a in E.a_invariants()])

    P_Qp = Eqp.lift_x(ZZ(P.xy()[0]))
    Q_Qp = Eqp.lift_x(ZZ(Q.xy()[0]))

    p_times_P = p * P_Qp
    p_times_Q = p * Q_Qp

    x_P, y_P = p_times_P.xy()
    x_Q, y_Q = p_times_Q.xy()

    phi_P = -(x_P / y_P)
    phi_Q = -(x_Q / y_Q)

    k = ZZ(phi_Q / phi_P) % p
    return k

Attack: MOV Attack (Supersingular Curves)

For supersingular curves (small embedding degree), the ECDLP can be reduced to a DLP in a finite field extension via the Weil or Tate pairing.

# In SageMath:
E = EllipticCurve(GF(p), [a, b])
assert E.is_supersingular()  # confirm

# Use pairings to reduce to finite field DLP
# Then use index calculus on F_{p^k}

Last updated on Aug 1, 2025

ECC Basics

ECC