## Intro

I’ll be honest, I kind of dropped the ball on the crypto category this time around, but not on Elliptic Labryinth, a medium rated challenge that had to be rereleased due to unintended solves, so we’ll be covering both intended and unintended versions.

In version 1 of the challenge, we’re given a server that is using the parameters of an elliptic curve to encrypt the flag. However, unlike traditional elliptic curve systems, we don’t actually know what the parameters are. We’re given the prime modulus and the upper 200-300 bits of the coefficients. But, the server also lets us generate an arbitrary number of points on the curve, which we can then use to calculate the parameters on our own using some algebra.

Version 2 of the challenge removed the point generation function, and only gives us one point. This would normally be a problem, but because we have a relation between all of our variables (the elliptic curve polynomial), we can apply Coppersmith’s method to find small roots of our polynomial and find the values chopped off of the coefficients.

### Description

`As you navigate through the labyrinth inside the tomb, you encounter GPS inaccuracies that make it difficult to determine the correct path to the exit. Can you overcome the technical issues and use your instincts to find your way out of the maze?`

## The Challenge (v1)

We’re given source code to the server.

### Solution

The `EllipticCurve`

class is initializing an elliptic curve in Weierstrass form, that is:

over the field $\mathbb{Z}_p$. Since we can generate any number of points, the only unknowns are $a$ and $b$, which allows us to set up a system of equations.

$\begin{aligned} y_1^{2} &= x_1^3 + ax_1 + b_1 \\\\ y_2^2 &= x_1^3 + ax_2 + b_2 \end{aligned}$If you’ve taken any kind of algebra class, the rearranging should be trivial, but eventually, we get here:

$\begin{aligned} a &= (x_1 - x_2)^{-1}(y_1^2 - y_2^2)-(x^3_1 - x^3_2) \\\\ b &= y_2^2 - x^3_1 - ax_1 \end{aligned}$So, we can implement this in code.

**Flag**: `HTB{d3fund_s4v3s_th3_d4y!}`

(this flag will make sense after covering the intended solution)

Short solution, but that’s usually the case with these unintended solutions. But now, for the main event.

## The Challenge (v2)

The big difference between version 1 and version 2 is the absence of the point generator.

### Solution

With the removal of the point generator, we’re limited to one equation, so now we actually have to pay attention to these parameters. When we’re given $a$ and $b$, they get bit shifted right by some amount $170 \leq r < 380$. This is hard to write in math, so we can rewrite this as

$\begin{aligned} a &= a_t + a_r \\ b &= b_t + b_r \end{aligned}$where $a_t, b_t$ represent the truncated numbers we get, and $a_r, b_r$ is the value that comes off of the truncation. Knowing this, we can revisit our elliptic curve equation and substitute:

$\begin{aligned} y^2 = x^3+ax+b &\rightarrow y^2 = x^3 + (a_t+a_r)x + (b_t+b_r) \\\\ &\rightarrow 0 = x^3 + (a_t+a_r)x + (b_t+b_r) - y^2 \end{aligned}$We know how all of the variables are related, and the only values we don’t know are $a_r$ and $b_r$, so the question is, how do we solve for them?

#### Coppersmith’s Method

An in-depth discussion of Coppersmith’s method is a bit outside the scope of this writeup, but the motivating question it addresses is “How do we find zeroes of polynomials modulo an integer”? From your basic algebra class, factoring polynomials of lower degrees is very easy. However, in this case, we need to deal with the prime modulus, which is effectively a randomizing function. As far as I’m aware, we don’t have anything to deal with these kinds of polynomials directly.

But, what if we could solve a different problem that’s easier to solve? Coppersmith’s method seeks to take a polynomial with big coefficients, and bring it down to a polynomial with smaller coefficients, but still the same zeroes. It works like this:

- Construct a lattice in a particular way using the polynomial.
- Apply the Lenstra–Lenstra–Lovász (LLL) algorithm to reduce the basis.
- Take the reduced basis and build our polynomial with smaller coefficients.

For those who don’t know, a lattice is essentially a big grid of vectors where any addition and subtraction of vectors in the lattice give another vector in the lattice.

The image above shows a lattice formed from a **basis** of $u_1$ and $u_2$. Notice that lattices are not unique; the basis of $v_1$ and $v_2$ forms the same lattice. When we apply the LLL algorithm, we attempt to find the basis defined by the smallest vectors in the lattice. If can construct our initial basis in a specific way, then reducing the basis will lead to finding that easier-to-solve polynomial.

At the end of the day, even if this doesn’t make total sense, we’re reducing a very complex problem to one we know we produce at least a close approximate solution for, to solve an easier problem.

#### Sage Script

The full process and algorithm is a little complex, but luckily there are a number of implementations out there. The solution to the first version suggested using defund’s implementation, but many other players have reported greater success with Joseph Surin’s version. Either one works, and we can write the below SageMath code to solve.

**Flag**: `HTB{y0u_5h0u1d_h4v3_u53d_c00p325m17h}`