This challenge involves hyperelliptic curves and understanding the Cantor’s algorithm to be able to construct a relationship that can be used to extract some small roots using the Coppermisth algorithm.

We are given a chall.sage file that, first of all, sets up some parameters:

p = 94235683804629271565982999971710609375595046800623466974818400769289845080223265348096429515360903332205728922039831445325696288131469248632324474133225349921788521516761748848030075106682083159721250623229343087538822420218805346047462578541418450143242476874246298541119785973740522737514515994196626057947
Zp = Zmod(p)
R.<x> = PolynomialRing(Zp)

a = 50388745719041913460291516577153707251851589986907343887836950814620908576049743625336406788413868434770966202375151155498184781903665587711680037916397047153196612649839072989391148224527332860455558388897073964777769901562543742670098611486382534056016050623712004728700806297510524525947953184925678738191
b = 77079665980869941586534539811707525781544605363177140690146778399875761035230354698555185675543136711786384579448967682817286610411073515757944721339483414323574243444638341503092366359064263273232684465918634617514909696812221857920483650952488398729514231494850081371324567953025480739514958298506881528450
F = x**5 + a*x**3 + b*x
H = 0

C = HyperellipticCurve(F, H)
J = C.jacobian()(Zp)

In the general case, a hyperelliptic curve is defined as:

$$C : y^2 + h(x)y = F(x)$$

In our case,

$$C : y^2 = x^5 + ax^3 + bx := F(x)$$

meaning that $h = 0$. The degree of $F$ being 5 means that this is a curve of genus 2. This is, indeed, an imaginary hyperelliptic curve. Before tackling the challenge, let’s brush up on hyperelliptic curve representations.

The Mumford representation

Ordinary elliptic curves happen to have a group structure, meaning that we can pick any two points in the curve and, through some fancy algorithm, sum them up to obtain a new point in the curve.

Hyperelliptic curves do not have a group structure, meaning that we can’t sum points that belong to it. However, we can define a new group, called the Jacobian of the curve, denoted $J(C)$, which actually comes from a quotient group. Instead of dealing with single points, we deal with divisors. A divisor is essentially a formal sum of points on the curve.

Working with formal sums of points is messy. To make this easier to deal with, we use the Mumform representation. Any non-zero element in the Jacobian of a curve can be uniquely represented by a pair of polynomials, $[u(x), v(x)]$ such that:

  1. $u$ is monic
  2. $\text{deg}(v) < \text{deg}(u) \leq g = 2$
  3. $u$ divides $F - v^2$

If we pick a point, $P_1 = (x_1, y_1)$ and denote its Mumford representation by $[u(x), v(x)]$, then $u(x_1) = 0$ and $v(x_1) = y_1$.

If we pick two points, $P_1 = (x_1, y_1)$ and $P_2 = (x_2, y_2)$, then the Mumford representation $[u(x), v(x)]$ of $P_1 + P_2$ will satisfy $u(x_1) = u(x_2) = 0$, $v(x_1) = y_1$ and $v(x_2) = y_2$.

Now, what if we pick three points $P_1, P_2$ and $P_3$? If we call $[u(x), v(x)]$ its Mumford representation, it cannot satisfy $u(x_1) = u(x_2) = u(x_3) = 0$, because we would need $\text{deg}(u) \geq 3$, but we know that $\text{deg}(u) \leq 2$. How can we keep adding points and obtaining a valid Mumford representation?

The Cantor’s algorithm

When solving the challenge, I found quite useful this Wikipedia article that also explains the Cantor’s algorithm and names the specific steps of it. This algorithm finds the Mumform representation of the sum of two reduced divisors $D_1$ and $D_2$.

In the challenge generates two (actually 3) points, $P$ and $Q$, and outputs $P+Q$. The goal is to find $P$:

def random_point():
    while True:
        Px = Zp.random_element()
        if F(Px).is_square():
            return J(C.lift_x(Px))

def small_point():
    while True:
        Px = Zp(secrets.randbelow(1 << 40))
        if F(Px).is_square():
            return J(C.lift_x(Px))


P = random_point()
Q = small_point() + small_point()
print(P + Q)

Sagemath does not implement the random_element method on Hyperelliptic curves, so the author of the challenge had to create its own random_point function, which is fairly simple. The small_point function follows the same process, but the x coordinate of the point is pretty small (less than $2^{40}$) compared to the size of the prime p (1024 bits). This already smells like LLL hehe.

In our case, the two reduced divisors are $P$ and $Q$, and we are given the Mumford representation of $P+Q$. Besides, we can safely assume that all the generated $x$ coordinates for the curve points are different. Denote $[u_1(x), v_1(x)]$ and $[u_2(x), v_2(x)]$ the Mumford representations of $Q$ and $P$, respectively.

Knowing this, we can adapt the Cantor’s algorithm found in Wikipedia:

  1. Because of the assumption, $1 = \gcd(u_1, u_2)$. Besides $e_1$ and $e_2$ will be some polynomials we don’t care about. We just need to remember that $e_1 u_1 + e_2 u_2 = 1$.
  2. Because of the previous step and $h = 0$, we have that $d = 1$, $c_1 = 1$ and $c_2 = 0$.
  3. Now, $s_1 = e_1$, $s_2 = e_2$ and $s_3 = 0$.
  4. Set $$u = u_1u_2, \qquad v = e_1 u_1 v_2 + e_2 u_2 v_1 \ (\text{mod} \ u)$$
  5. Set $$u’ = \dfrac{F - v^2}{u}, \qquad v’ = -v \ (\text{mod} \ u’)$$

Because we are just summing three points up, the algorithm ends here, as already $\deg(u’) = 2 = g$. What we are given is $u’$ and $v’$.

Setting up relationships

From the step 5 of the algorithm, we know that $v’ = -v (\text{mod} \ u’)$, which means that

$$\exists k \in GF(p)[x] : v’ = k u’ - v \iff v = ku’ - v’$$

Note that $\deg(u’) = 2$, so that $\deg(v’) < \deg(u’) = 2$. Besides, $\deg(u) = 3$, meaning that $\deg(v) < \deg(u) = 3$. All of this, implies that $\deg(k)$ = 0. In other words, $k$ is a constant polinomial.

Besides, $F-v^2 = u u’$ (from step 5 as well), so substituting that in:

$$F - (ku’ - v’)^2 = u u’ = (x - x_1)(x-x_2)(x - x_3) u’$$

The last step comes from $u = u_1u_2$ and $u_1$ being the first component of the Mumford representation of $Q$, which is the sum of the two small points, so their $x$ coordinates ($x_1$ and $x_2$) will be roots of $u_1$. Similarly, $x_3$ is a root of $u_2$.

Expanding that expression, we get:

$$\begin{equation*} \begin{split} & F - (v’)^2 + 2ku’v’ - k^2 (u’)^2 = (x-x_1)(x-x_2)(x-x_3)u’ \\ \iff & \dfrac{F - (v’)^2}{u’} + 2kv’ - k^2u’ = (x-x_1)(x-x_2)(x-x_3) \end{split} \end{equation*}$$

The challenge gives us $u’$ and $v’$, so we can compute $\dfrac{F-(v’)^2}{u’}$, which will be a monic polynomial of degree 3.

We have two polynmials of degree 3 on both sides, so now we can make equations by comparing coefficients:

$$x^3 + k_2(k)x^2 + k_1(k)x+k_0(k) = x^3 - (x_1+x_2+x_3)x^2 + (x_1x_2 + x_1x_3+x_2x_3)x - x_1x_2x_3$$

where $k_2$ is a quadratic expression depending on $k$, and $k_1$ and $k_0$ depend linearly on $k$. From that:

$$\begin{equation*}\left\{ \begin{split} k_2(k) & = - (x_1 + x_2 + x_3) \\ k_1(k) & = x_1 x_2 + x_1x_3 + x_2x_3 \\ k_0(k) & = -x_1x_2x_3 \end{split}\right. \end{equation*}$$

So we have three equations and 4 unknowns. However, 2 of them are known to be small numbers. From these 3 equations, we can get rid of two of them, together with 2 unknowns, getting a single equation with the two small unknowns.

Recovering $x_1$ and $x_2$

We need to get rid of $k$ and $x_3$. I think it makes it easier to solve the problem if we call

$$S = x_1 + x_2, \qquad M = x_1x_2$$

Or maybe it is not easier. But this is how I did it lol

Anyway, you can use several methods to remove $k$ and $x_3$. What I did is to manually isolate $k$ in the first equation and then substitute that into the other two. I could have also done that to remove $x_3$ now, but things started to get messy, so I just opted to use the resultant of the two polynomials. You can do all of this with this Sagemath code:

First, create the polynomials to work with:

P_SM = PolynomialRing(GF(p), names=["S", "M"])
P_k = PolynomialRing(P_SM, names=["k"])
P_x = PolynomialRing(P_k, names=["x"])
R = PolynomialRing(GF(p), names=["x"])

S = P_SM.gen(0)
M = P_SM.gen(1)
k = P_k.gen()
x = P_x.gen()

Receive the data from the challenge:

r = remote("what-the-hecc-2.ctf.theromanxpl0.it", 9102)
parts = r.recvline().decode().strip()[1:-1].split(", ")
u_p = R(parts[0])
v_p = -R(parts[1][1:])

print(f"{u_p = }")
print(f"{v_p = }")

Remove $k$:

W = P_x(R(F - v_p**2) / R(u_p))
u_p = P_x(u_p)
v_p = P_x(v_p)

lhs = W + 2*k*v_p -k**2*u_p
x3 = - lhs[2] - S
f1 = lhs[1] - M - S*x3
f2 = lhs[0] + M*x3

And the resultant is computed like this:

res = f1.resultant(f2)

Now, res holds a polynomials whose only unknowns are $S$ and $M$. We know that these two numbers are small (around 40 and 80 bits, respectively).

This is usually solved using the Coppersmith algorithm. In this case, the bivariate version. Usually, defund’s version works pretty well. However, I couldn’t make it work for this case. My second option usually is ubuntor’s version, but I couldn’t make it work either. After a while looking for some other implementations, I found cuso, which is installed as a Python library. This one turned out to work! Also, it is super easy to use:

import cuso
roots = cuso.find_small_roots([res], {S: (1<<30, 1<<40), M: (1<<60, 1<<80)})

Just like that! Hopefully, after executing that, we will factor the polynomial and recover $S$ and $M$, which trivially recovers the rest of the variables $x_1, x_2, x_3$ and $k$. We are interested in $x_3$, because that is what the server asks. We can recover the unknowns and send them to recover the flag using this code:

s = int(roots[0][S])
m = int(roots[0][M])
x1 = (s + int((s**2 - 4*m)**(1/2))) // 2
x2 = (s - int((s**2 - 4*m)**(1/2))) // 2

roots = R(f2.subs(S=s,M=m)(x).monic()).roots()
ks = []
for root in roots:
    poss_k = int(root[0])
    if f1.subs(S=s, M=m, k=poss_k) == 0:
        print(f"Found k: {poss_k}")
        ks.append(poss_k)

for _k in ks:
    x3 = -lhs[2].subs(k=_k) - s
    print(f"{x3 = }")
    y3 = C.lift_x(x3)[1]
    r.sendlineafter(b"Px Py: ", f"{x3} {y3}".encode())
    r.interactive()

TRX{1_th1nk_we_c4n_d0_wa44a44aaaaa44y_b3tt3r_uwu}

Congrats to the author, I liked this challenge :D