2022-10-31
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.
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)
P = (0x5b5e2d0616a293aa121c66a982a36ed163fad1608ce5cc9601d6331d7c5a431, 0x55a9fd40e74741d7b8867c17fbb8db2cbceb8a5b1f48230aaf9234f682a7424)
K.<x>=GF(p)[]
f = x^3 + a*x + b
assert(f.discriminant() == 0)
# change of variables
double_root = f.roots()[1][0]
t = f.subs(x=x + double_root)
c = GF(p)(t(1) - 1).square_root()
G = (G[0] - double_root, G[1])
P = (P[0] - double_root, P[1])
# compute mapping
u = (G[1] + c*G[0]) / (G[1] - c*G[0]) % p
v = (P[1] + c*P[0]) / (P[1] - c*P[0]) % p
# DLOG over multiplicative group
n = discrete_log(v, u)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()[0]
P = K.random_element()*G
n = discrete_log(P, G, G.order(), operation="+")
assert(n*G == P)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)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()[0]
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)#\(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()[0]
P = K.random_element()*G
# anomalous curve
assert(E.order() == p)
# p-adic lift
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()[0]), all=True):
if K(G_.xy()[1]) == G.xy()[1]:
break
pG_ = p*G_
for P_ in E_.lift_x(ZZ(P.xy()[0]), all=True):
if K(P_.xy()[1]) == P.xy()[1]:
break
pP_ = p*P_
# p-adic elliptic log
psi_G = -(pG_.xy()[0] / pG_.xy()[1])
psi_P = -(pP_.xy()[0] / pP_.xy()[1])
n = ZZ(psi_P/psi_G)
assert(n*G == P)