ECC Attacks

Elliptic-curve cryptography is sound on well-chosen curves; what breaks in CTFs is a bad curve or a bad protocol. The curve order may be smooth, the curve may be supersingular or anomalous, the equation may be singular, or the implementation may skip a validation check or reuse a nonce. Each defect collapses the ECDLP - or sidesteps it entirely.

If point addition, scalar multiplication, and the ECDSA signing relation are not yet second nature, read ECC Basics first.

Which Attack? Decision Table

Compute the group order first; almost every structural attack is read off its factorization.

Generic Discrete Log

If the group order is merely small (CTF toy curves, or a small prime-order subgroup), the ECDLP yields to generic square-root algorithms in $O(\sqrt n)$: baby-step giant-step or Pollard's rho. SageMath wraps both behind one call.

# SageMath
E = EllipticCurve(GF(p), [a, b])
G = E(Gx, Gy)
Q = E(Qx, Qy)

d = discrete_log(Q, G, operation="+")   # generic; uses BSGS/rho/Pohlig-Hellman
print("d =", d)

discrete_log automatically applies Pohlig-Hellman if the order factors, so for a smooth order it is often all you need. The sections below explain why each shortcut works and when to reach for a hand-rolled version.

Pohlig-Hellman (Smooth Order)

If $n = \#\langle G\rangle$ factors as $\prod_i \ell_i^{e_i}$ with each prime power small, the ECDLP splits by CRT into independent discrete logs in each subgroup of order $\ell_i^{e_i}$, each solvable in $O(\sqrt{\ell_i})$. The total cost is governed by the largest prime factor, so a curve whose order is smooth (all factors small) is broken even if $n$ itself is huge.

# SageMath - Pohlig-Hellman by hand to show the structure
E = EllipticCurve(GF(p), [a, b])
G = E(Gx, Gy); Q = E(Qx, Qy)
n = G.order()
fac = factor(n)
print("order factorization:", fac)

residues, moduli = [], []
for ell, e in fac:
    m = ell**e
    G_sub = (n // m) * G          # generator of the order-m subgroup
    Q_sub = (n // m) * Q
    d_i = discrete_log(Q_sub, G_sub, operation="+")
    residues.append(d_i); moduli.append(m)

d = crt(residues, moduli)
print("d =", d)

MOV / Frey-Ruck (Pairing Reduction)

The MOV attack (Menezes-Okamoto-Vanstone), and its Tate-pairing cousin Frey-Ruck, reduce the ECDLP on $E/\mathbb{F}_p$ to an ordinary discrete log in the multiplicative group $\mathbb{F}_{p^k}^\times$, where $k$ is the embedding degree - the smallest $k$ with $n \mid p^k - 1$. A bilinear pairing $e(\cdot,\cdot)$ sends

so recovering $d$ becomes a finite-field DLP solvable by index calculus. This is fast only when $k$ is small - which happens for supersingular curves ($k \le 6$) and other special curves.

# SageMath - MOV reduction via the Weil pairing
E = EllipticCurve(GF(p), [a, b])
G = E(Gx, Gy); Q = E(Qx, Qy)
n = G.order()

# embedding degree: smallest k with n | p^k - 1
k = 1
while (p**k - 1) % n != 0:
    k += 1
print("embedding degree k =", k)
assert k <= 6, "k too large for index calculus to be practical"

Ek = E.base_extend(GF(p**k))
Gk = Ek(G); Qk = Ek(Q)

# pick an n-torsion point T independent of G for the pairing
T = Ek.random_point()
T = (T.order() // n) * T
alpha = Gk.weil_pairing(T, n)
beta  = Qk.weil_pairing(T, n)

d = beta.log(alpha)      # discrete log in F_{p^k}^*
print("d =", d)

Smart's Attack (Anomalous Curves)

A curve is anomalous when $\#E(\mathbb{F}_p) = p$. Smart's attack (and the SSSA variant) solves its ECDLP in polynomial time by lifting points to the $p$-adic numbers $\mathbb{Q}_p$ and using the formal-group logarithm: the trace-zero structure makes the lifted scalar readable directly.

# SageMath - Smart's attack for #E(F_p) == p
def smart_attack(G, Q, p):
    E = G.curve()
    Eqp = EllipticCurve(Qp(p, 2), [ZZ(ai) for ai in E.a_invariants()])

    G_lift = Eqp.lift_x(ZZ(G.xy()[0]))
    # match the sign of y on the lift
    if (ZZ(G_lift.xy()[1]) % p) != (ZZ(G.xy()[1]) % p):
        G_lift = -G_lift
    Q_lift = Eqp.lift_x(ZZ(Q.xy()[0]))
    if (ZZ(Q_lift.xy()[1]) % p) != (ZZ(Q.xy()[1]) % p):
        Q_lift = -Q_lift

    pG = p * G_lift
    pQ = p * Q_lift

    # formal-group log: phi(P) = -x/y of p*P
    phiG = -(pG.xy()[0] / pG.xy()[1])
    phiQ = -(pQ.xy()[0] / pQ.xy()[1])

    d = ZZ(phiQ / phiG) % p
    return d

E = EllipticCurve(GF(p), [a, b])
assert E.order() == p, "not anomalous"
d = smart_attack(E(Gx, Gy), E(Qx, Qy), p)
print("d =", d)

Singular Curves (Node / Cusp)

If $4a^3 + 27b^2 \equiv 0 \pmod p$ the curve is singular and not a valid elliptic curve - its smooth points form a group isomorphic to a much easier structure, so the "ECDLP" reduces to an ordinary DLP or even a plain division.

• Node (double root, multiplicative reduction): the group is isomorphic to $\mathbb{F}_p^\times$ (or a quadratic extension's). The ECDLP becomes a finite-field DLP.
• Cusp (triple root, additive reduction): the group is isomorphic to the additive group $(\mathbb{F}_p, +)$, so the discrete log is a single modular division - trivial.

# SageMath - map a singular curve to its easy group
# y^2 = x^3 + a*x + b is singular: find the singular point and the root structure.
R.<x> = GF(p)[]
f = x^3 + a*x + b
roots = f.roots()
print("roots of cubic:", roots)

# Cusp case: x^3 (triple root at 0) -> group is (F_p, +)
# The map (x, y) |-> x/y linearizes the law; d = (x_Q/y_Q) / (x_G/y_G) mod p.

# Node case: double root at x = r. Shift x' = x - r, then y^2 = x'^2 (x' + t).
# With sqrt of t (or in F_{p^2}), the map (x', y) |-> (y + s*x')/(y - s*x')
# sends points to F_p^* (or F_{p^2}^*); solve an ordinary DLP there.

Invalid-Curve Attack

ECDH and ECIES implementations that do not verify the incoming point lies on the intended curve are vulnerable. The scalar-multiplication formulas for $y^2 = x^3 + ax + b$ never use $b$, so a point $(x, y)$ off the real curve actually lives on a different curve $E':\,y^2 = x^3 + ax + b'$ where $b' = y^2 - x^3 - ax$. If you choose $E'$ to have smooth order, the server's secret $d$ reduces modulo a small subgroup order, leaking $d \bmod \ell$ from each crafted point. CRT reassembles $d$.

# SageMath - generate a weak invalid curve and a small-order point
p, a = ..., ...
target_primes = []
weak_points = []

for bp in range(2, 2000):
    Eprime = EllipticCurve(GF(p), [a, bp])
    order = Eprime.order()
    for ell, e in factor(order):
        if ell < 2**16 and ell not in target_primes:
            P = Eprime.gen(0)
            Psub = (order // ell) * P        # point of order ell on E'
            if Psub != Eprime(0):
                target_primes.append(ell)
                weak_points.append((bp, ell, Psub))
    if prod(target_primes) > 2**256:
        break

# Send each Psub to the oracle, recover d mod ell, then crt(residues, moduli).

Small-Subgroup Attack

Closely related: even on the correct curve, if the curve has a cofactor $h > 1$ (so $\#E = h\cdot n$ with small factors of $h$), an attacker can send a point of small order $\ell \mid h$. The shared secret then lands in a tiny subgroup, leaking $d \bmod \ell$. Curves like Curve25519 defend by clamping the scalar (clearing low bits) so the cofactor is absorbed; implementations that skip cofactor handling on a non-prime-order curve are exposed.

# SageMath - exploit a non-trivial cofactor
E = EllipticCurve(GF(p), [a, b])
N = E.order()
n = G.order()
h = N // n
print("cofactor h =", h, "factors:", factor(h))

# For each small ell | h, find a point T of order ell, send it, recover d mod ell.
for ell, _ in factor(h):
    T = (N // ell) * E.random_point()      # order ell (or identity; retry)
    # oracle returns d*T; brute force d mod ell by matching i*T for i in [0, ell)

The difference from the invalid-curve attack: there the point is off-curve and you pick the partner curve; here the point is genuinely on the curve but in a small-order subgroup permitted by the cofactor.

Twist Attacks

Protocols that transmit only the $x$-coordinate (Montgomery-ladder ECDH, e.g. Curve25519 done carelessly) cannot tell whether a given $x$ corresponds to a point on the curve $E$ or on its quadratic twist $E^t$. For roughly half of all $x$ values the point lies on the twist. If $E^t$ has smooth order (a non-twist-secure curve), an attacker sends $x$-coordinates of small-order twist points and recovers $d$ modulo small primes via Pohlig-Hellman on the twist - then CRT.

# SageMath - inspect twist security
E = EllipticCurve(GF(p), [a, b])
Et = E.quadratic_twist()
print("curve order :", factor(E.order()))
print("twist order :", factor(Et.order()))
# If the twist order is smooth, x-only ECDH that skips validation is twist-vulnerable.

ECDSA Nonce Reuse

If the same nonce $k$ signs two different messages, $r$ repeats (since $r = (kG)_x$) and the private key falls out algebraically - no lattice needed.

then $d \equiv \dfrac{s_1 k - h_1}{r}\pmod n$.

import hashlib

n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141  # secp256k1
def H(msg): return int(hashlib.sha256(msg).hexdigest(), 16)

# Given (r, s1) on msg1 and (r, s2) on msg2 with the SAME r:
h1, h2 = H(msg1), H(msg2)
k = ((h1 - h2) * pow(s1 - s2, -1, n)) % n
d = ((s1 * k - h1) * pow(r, -1, n)) % n
print("private key d =", hex(d))

A subtle variant: even different signers who share a faulty RNG, or a single signer whose nonces differ by a known constant, leak the key the same way (it becomes a linear system in $d$).

Biased-Nonce Hidden Number Problem

When nonces are not reused but are short (top bits zero) or biased (a fixed bit pattern), each signature gives an approximate linear equation in $d$. Collecting enough of them turns key recovery into a lattice problem - the Hidden Number Problem. Rewrite the signing relation:

and if every $k_i$ is small, $d$ is the hidden number recovered by LLL on a lattice built from the $(s_i^{-1}r_i,\, s_i^{-1}h_i)$ pairs. The full construction, the "how many signatures" rule, and a runnable SageMath script live on the lattice attacks page.

# SageMath - sketch; the complete lattice is on the lattice-attacks page
# sigs: list of (h, r, s); recover d when each nonce k < 2^ell (top bits zero)
def hnp_recover(sigs, n, KB):
    t = [(Integer(s).inverse_mod(n) * r) % n for (h, r, s) in sigs]
    u = [(Integer(s).inverse_mod(n) * h) % n for (h, r, s) in sigs]
    m = len(sigs)
    B = Matrix(QQ, m + 2, m + 2)
    for i in range(m):
        B[i, i] = n
        B[m, i] = t[i]
        B[m + 1, i] = u[i]
    B[m, m] = QQ(KB) / n
    B[m + 1, m + 1] = KB
    return B.LLL()   # read d from the short row; then verify Q == d*G

Checklist

• Factor E.order() first - largest prime factor small? Pohlig-Hellman.
• E.is_supersingular() or small embedding degree $k$? MOV / Frey-Ruck pairing reduction.
• E.order() == p? Smart's anomalous-curve attack (polynomial time).
• (4*a^3 + 27*b^2) % p == 0? Singular curve - reduce to node ($\mathbb{F}_p^\times$) or cusp ($\mathbb{F}_p^+$).
• Server multiplies points without checking they are on the curve? Invalid-curve attack + CRT.
• Cofactor $> 1$ and no clamping? Small-subgroup attack.
• $x$-only ECDH on a non-twist-secure curve? Twist attack via Pohlig-Hellman on $E^t$.
• Two signatures share $r$? Nonce reuse - algebraic key recovery.
• Many signatures with short/biased nonces? Biased-nonce HNP lattice.
• Small order overall? Generic discrete_log (BSGS / Pollard rho).

See Also

• ECC Basics - curve arithmetic, ECDSA, and ECDH groundwork.
• Lattice Attacks - the HNP lattice for biased ECDSA nonces in full.
• RSA Attacks - the other major asymmetric attack catalogue.
• RSA Basics - shared modular-arithmetic background.

Last updated on Jun 15, 2026