Tags: elliptic dlp crypto
Rating:
Commence Operation Delta!! Hint: Last part of this problem, discrete_log() function in sagemath is useful. Run ?discrete_log in sage CLI and read the document.
We are given a curve in the form of Weierstrass form: E:y2+a1xy+a3y=x3+a2x2+a4x+a6 over integer modulo ring N=pq, where p and q are hidden.
By checking the discriminant is zero, we find that the given curve is singular.
def is_singular():
b2 = a1**2 + 4 * a2
b4 = 2 * a4 + a1 * a3
b6 = a3**2 + 4 * a6
b8 = a1**2 * a6 + 4 * a2 * a6 - a1 * a3 * a4 + a2 * a3**2 - a4**2
Di = -(b2**2) * b8 - 8 * b4**3 - 27 * b6**2 + 9 * b2 * b4 * b6
return Di % N == 0
assert is_singular(), "Curve is not singular"
N
over Singular CurveWe are given points P=(Px,Py) and Q=(Qx,Qy). Q=dP where d is secret. Our goal is to recover d which contains the flag.
Denote EC(k) be the curve defined over modulo ring k, and ord(EC(k)) be the order of EC(k). If we factor N, we can solve each DLP over EC(p) and EC(q) and combine them using chinese remainder theorem.
N = pq
We do not know the values of p and q yet. However, we know that elliptic curve operation is not well defined in composite ring(N is composite). Also, if singular curve is the form of cusp(y2=x3) over prime r, its order is r. ord(EC(N))=ord(EC(p))×ord(EC(q)).
Assuming that EC(p) is a cusp(ord(EC(p))=p), N will be the multiple of p=ord(EC(p)). If we calculate scalar multiplication N∗P over EC(N), operation will be not well defined. Let t be the intermediate value which breaks down the operation, because t's inverse does not exist over composite N. This means gcd(t,N) will give a nontrivial factor, which results in factorization, obtaining p.
def factor():
try:
ec.scalar(N, P)
except Exception as e:
t, _ = list(
map(
int,
str(e).lstrip("inverse of Mod(").rstrip(") does not exist").split(", "),
)
)
p = gcd(t, N)
q = N // p
return p, q
EC(p)
Lets classify whether EC(p) is a cusp(form y2=x3) or node(form y2=x3+αx2). To do this, we need to find a singular point. Compute partial derivatives of EC(p) and find values where they vanish and also on a curve.
def calc_singular_point(f):
FF = f.base_ring()
p = FF.order()
dfdx = lambda x, y: FF(a1 * y - 3 * x**2 - 2 * a2 * x - a4)
dfdy = lambda x, y: FF(2 * y + a1 * x + a3)
A = FF(6)
B = FF(4 * a2 + a1**2)
C = FF(2 * a4 + a1 * a3)
roots = solve_quadratic(A, B, C)
for xp in roots:
yp = FF((-a1 * xp - a3) * pow(2, -1, p))
assert dfdx(xp, yp) == 0 and dfdy(xp, yp) == 0
if f.subs(x=xp, y=yp) == 0:
return xp, yp
After that, we shift the curve to set the singular point as origin (0,0).
f = f.subs(x=x + xp, y=y + yp)
assert f.subs(x=0, y=0) == 0
xy_coeff = f.coefficient(x * y)
f = f.subs(y=y + xy_coeff * twoinv * x)
assert f == x ** 3 - y ** 2, "Given curve is not a cusp"
We confirmed EC(p) is a cusp. We can solve DLP easily when a singular curve is a cusp form. EC(p) has group isomorphism with GF(p), and can be regarded as an additive group (Theorem 2.30 [^book]).
φ:EC(p)→GF(p),(x,y)→xy,inf
We use this isomorphism \varphi to map points from EC(p) to elements of the group (GF(p), +). We first also shift the points because curve has shifted and mapped to an additive group. Therefore ord(EC(p)) = p.
# shift points
Pxp = Px - xp
Pyp = Py - yp - xy_coeff * twoinv * Pxp
assert f.subs(x=Pxp, y=Pyp) == 0
Qxp = Qx - xp
Qyp = Qy - yp - xy_coeff * twoinv * Qxp
assert f.subs(x=Qxp, y=Qyp) == 0
# map to additive group over FF
Q_ = FF(FF(Qxp) // FF(Qyp))
P_ = FF(FF(Pxp) // FF(Pyp))
Solving DLP over additive group is easy.
dp = Q_ // P_
We recovered d_{p}, which is the result of DLP over EC(p) between P and Q. Every implementation for this step is done at method solve_dlp_over_p()
.
EC(q)
Lets classify whether EC(q) is a cusp(form y^{2} = x^{3}) or node(form y^{2} = x^{3} + \alpha x^{2}). Again, we need to find a singular point. Compute partial derivatives of EC(p) and find values where they vanish, and also on a curve. We shift the curve to set the singular point as origin (0, 0).
xq, yq = calc_singular_point(f)
# change of variables to make (0, 0) as singular point
f = f.subs(x=x + xq, y=y + yq)
assert f.subs(x=0, y=0) == 0
xy_coeff = f.coefficient(x * y)
f = f.subs(y=y + xy_coeff * twoinv * x)
assert alpha != 0
assert f == x**3 + alpha * x**2 - y**2
We confirmed EC(q) is a node of the form y^{2} = x^{2} (x + \alpha). We have an isomorphism(Theorem 2.31 [^book]):
\phi: (x, y) \rightarrow \frac{y + \alpha x}{y - \alpha x}
\alpha is not a quadratic residue in this challenge, so \phi gives an isomorphism:
EC(q) \simeq S := { u + \alpha v | u, v \in GF(q), u^{2} - \alpha v^{2} = 1 }
where the righthand side is a group under multiplication. This is called nonsplit multiplicative reduction. S is a set of points which field norm is 1. Let K/F be an extension field when F = GF(q). Norm map Norm_{K/F} is surjective; (Proof). By the proof, ord(S)(cardinality of kernel) is equal to q + 1. Confirmation:
# order of Elliptic curve over GF(q) = q + 1
oq = q + 1
ec = EC(FF, (a1, a2, a3, a4, a6))
assert ec.iszeropoint(P) and ec.iszeropoint(Q)
assert ec.scalar(oq, P) == ec.O and ec.scalar(oq, Q) == ec.O
We know ord(EC(q)) = q + 1. Luckily, q + 1 is B-smooth, so we can apply Pohlig Hellman algorithm for solving the DLP.
factors = [2, 2148001447, ...]
assert reduce(mul, factors) == oq
# order is B-smooth where B = 2 ** 33
B = 2**33
assert all(fac << B for fac in factors)
Pohlig Hellman algorithm only cares about input elements form a finite abelian group whose order is a smooth integer, which is our case. Sagemath has discrete_log
method implemented, which takes elements and operations to make every step of the algorithm well defined. Identity, inverse, addition must be defined over custom groups. Define class ECPoint
which is a wrapper of a tuple, define operations, and plug in to discrete_log
.
# ECPoint class for discrete_log
class ECPoint:
def __init__(self, point):
self.point = point
def is_zero(self):
return self.point == EC.O
def __eq__(self, other):
return self.point == other.point
def __hash__(self):
return hash(self.point)
# factory method for discrete_log
add = lambda x, y: ECPoint(ec.add(x.point, y.point))
inv = lambda x: ECPoint(ec.negate(x.point))
# wrapping points with ECPoint class
identity = ECPoint(ec.O)
P_, Q_ = ECPoint(P), ECPoint(Q)
# discrete_log time
dq = discrete_log(
Q_, P_, ord=oq, operation="other", identity=identity, inverse=inv, op=add
)
Recovering d_{q} takes about 10 minutes in my laptop, which is the result of DLP over EC(q) between P and Q. Every implementation for this step is done at method solve_dlp_over_q()
.
EC(N)
We solved DLP over EC(p) and EC(q). Combine the results using the Chinese remainder theorem.
def solve_dlp_over_N():
p, q = factor()
dp = solve_dlp_over_p(p)
dq = solve_dlp_over_q(q)
return crt([dp, dq], [p, q + 1])
We have recovered d, which is the result of DLP over EC(N) between P and Q.
Recover flag
based on d
.
from Crypto.Util.number import long_to_bytes as l2b
flag = l2b(int(d))
flag = flag[: flag.index(b"}") + 1]
We get flag.
TSGCTF{@l1_y0u_n3Ed_IS_ReaDiNG_5ilvErman_ThE_@r1thmetic_of_e11iPtiC_cURVe5}
Problem src: problem.sage depending on elliptic_curve.py
Problem output: output.txt
Exploit driver code: solve.sage
[^book]: Elliptic Curves: Number Theory and Cryptography 2nd Edition