Consider the group of points induced by the curve

$E: y^2 = x^3 + ax + b \pmod{p}$

With generator $G$ and $P = nG$. The fastest known algorithms solve ECDLP over $E(\mathbb{F}_p)$ in $O(\sqrt{p})$.

This is a list of speedup scenarios.

# Singularity

E is singular (has a double/triple root). There exists an efficient map from the set of non-singular points in E to the multiplicative base group of E.

a = 0x9c07797788e4959f91bcae7ecfdc65ead5311ac6fad817534681c8
b = 0x1270895856df5bce5e86d023160ac61c13925b588549e150ba4cf38accd806
p = 0x9a888cfd499443d7637469ef4e20d6bbb2dcd1ddf928778cdea3501cf8dea17

G  = (0x4f2b1892ba1acd7ffea403db4a460bde0da7e49e824cd6fb9914e36afcbb2, 0x7fe796eacf863f5c6978fa9cb04c85e3a0dbbd1bbf0b105b28f7cab52b03e8)

K.<x>=GF(p)[]
f = x^3 + a*x + b
assert(f.discriminant() == 0)

# change of variables
double_root = f.roots()
t = f.subs(x=x + double_root)
c = GF(p)(t(1) - 1).square_root()

G = (G - double_root, G)
P = (P - double_root, P)

# compute mapping
u = (G + c*G) / (G - c*G) % p
v = (P + c*P) / (P - c*P) % p

# DLOG over multiplicative group
n = discrete_log(v, u)


# Smooth Order

E is of smooth order. The usual Pohlig-Hellman attack works.

K = GF(0xe9c1eb62c2e8d8777cd419d03008e72f)
E = EllipticCurve(K, [2, 3])

# smooth
print(E.order().factor())

G = E.gens()
P = K.random_element()*G

n = discrete_log(P, G, G.order(), operation="+")
assert(n*G == P)


# Constrained log

The log is constrained to some interval $(a, b)$. Pollard’s lambda algorithm runs in $O(\sqrt{b - a})$.

from random import getrandbits

E = EllipticCurve(GF(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F), [0, 7])
G = E.lift_x(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798)
P = getrandbits(32)*G

n = discrete_log_lambda(P, G, (0, 1<<32), operation="+")
assert(n*G == P)


# Small Embedding Degree

E has a small embedding degree $k < \log^2 p$. The MOV attack uses a bilinear map to transfer the log to the extended field $\mathbb{F}_{p^k}$.

p = 0x10cd3de04a2aa57345a2b75aa5
K = GF(p)
E = EllipticCurve(K, [-35, 98])

G = E.gens()
P = E.lift_x(0x84651664b83b8ef185c5a2e08)

# compute embedding degree
k = 1
o = G.order()
while (p**k - 1) % o != 0:
k += 1

N = P.order()
assert(gcd(N, p) == 1)

# extend field
E = E.change_ring(GF(p^k))
T = E.random_element()
M = T.order()
d = gcd(M, N)
T = (M//d)*T

# bilinear mapping to the extended field
u = E(G).weil_pairing(T, M)
v = E(P).weil_pairing(T, M)

# DLOG over multiplicative group
n = v.log(u)
assert(n*G == P)


# Trace of one

$\#E(\mathbb{F}_p) = p$. Smart’s attack reduces to the p-adic log over $E(\mathbb{Q}_p)$.

p = 0xa15c4fb663a578d8b2496d3151a946119ee42695e18e13e90600192b1d0abdbb6f787f90c8d102ff88e284dd4526f5f6b6c980bf88f1d0490714b67e8a2a2b77
a = 0x5e009506fcc7eff573bc960d88638fe25e76a9b6c7caeea072a27dcd1fa46abb15b7b6210cf90caba982893ee2779669bac06e267013486b22ff3e24abae2d42
b = 0x2ce7d1ca4493b0977f088f6d30d9241f8048fdea112cc385b793bce953998caae680864a7d3aa437ea3ffd1441ca3fb352b0b710bb3f053e980e503be9a7fece

K = GF(p)
E = EllipticCurve(K, [a, b])
G = E.gens()
P = K.random_element()*G

# anomalous curve
assert(E.order() == p)

E_ = EllipticCurve(Qp(p), [ZZ(t) + randint(0,p)*p for t in E.a_invariants()])

for G_ in E_.lift_x(ZZ(G.xy()), all=True):
if K(G_.xy()) == G.xy():
break
pG_ = p*G_

for P_ in E_.lift_x(ZZ(P.xy()), all=True):
if K(P_.xy()) == P.xy():
break
pP_ = p*P_