Writeup DGSE - CTF - VX Elliptique

This article describes my solution for the 250-point challenge called “VX Elliptique”.


Nous avons intercepté 2 fichiers (VX_elliptique.pdf et livres_Friang.pdf) émis par un sous-marin d’Evil Gouv.
La référence à Brigitte Friang ne peut être une coïncidence. Nous savons de source sure qu’Eve Descartes a été enlevée par Evil Gouv et est retenue dans un de leurs sous-marins dans l’océan Atlantique.
Ce doit être elle qui a envoyé ces fichiers. Grâce à une de ses crises mathématiques, elle aura sûrement caché l’identification du sous-marin dans ces fichiers.
Votre mission est de retrouver l’identification du sous-marin.

If you want to test it yourself, VX_elliptique.pdf file is available here and livres_Friang.pdf is available here.


We have two PDF files, one is password protected, the other is not. The solution of the equation in VX_elliptique.pdf seems to be the password to unlock the other one.

Mathematics behind ECC

We have the following equation.

\[y^2 = x^3 + Ax^2 + x [n]\]

Which can also be written as follows.

\[y^2\bmod n = (x^3 + Ax^2 + x) \bmod n (1)\]

The procedure can be split into 3 parts:

Solve \(A\)

Although it is possible to find \(A\) according to Bézout’s theorem and the modular inverse, I will take a different approach: brute force. We will see at the end how it would also have been possible to find \(A\) with the techniques mentioned before.

Here is the script I wrote to test all the values of \(A\).

#! /usr/bin/env python

y = 14361142164866602439359111189873751719750924094051390005776268461061669568849
x = 54387532345611522562080964454373961410727797296305781726528152669705763479709
n = 57896044618658097711785492504343953926634992332820282019728792003956564819949
A = 0

equality = (y**2) % n

while (True):
    result = (x**3 + A*x**2 + x) % n
    if result == equality:
        print (f"A = {A}")
        A += 1

In less than 1 second, I found the value of \(A\).

python bf.py
A = 486662

Solve \(x_1\) and \(x_2\)

Now that we have the complete equation and know the \(y_1\) and \(y_2\) values, we can retrieve the corresponding \(x_1\) and \(x_2\) values. As we have in a previous challenge, we will use SageMath to perform operations in finite fields.

First, let’s define constants.

sage: n = 57896044618658097711785492504343953926634992332820282019728792003956564819949
sage: x = 54387532345611522562080964454373961410727797296305781726528152669705763479709
sage: y = 14361142164866602439359111189873751719750924094051390005776268461061669568849
sage: y1 = 43534902453791495272426381314470202206884068238768892013952523542894895251100
sage: y2 = 30324056046686065827439799532301040739788176334375034006985657438931650257514
sage: a = 486662
sage: m = (n - 1) / 2

We want to work modulo \(n\), so we define our polynomial ring with the Galois Field of cardinal \(n\).


Then we look for the roots for \(y=y_1\) and \(y=y_2\) of the following polynomial.

\[y^2 - (k^3+ak^2+k)\]
sage: L=(y1^2 - (k^3 + a*k^2 + k)).roots();L
sage: L=(y2^2 - (k^3 + a*k^2 + k)).roots();L

There are three different roots \(x_{11}\), \(x_{12}\) and \(x_{13}\) for \(y=y_1\) and a single triple root \(x_{20}\) for \(y=y_2\).

Solve \(z\)

We now have all the necessary information to complete the last step. This time we have a modular equation system.

\[\begin{equation} \left\{ \begin{array}{l} z \equiv a \: \mbox{mod $n$} \\ z \equiv b \: \mbox{mod $m$} \end{array} \right. \end{equation}\]

With \(a=x_1\), \(b=x_2\) and \(m = \frac{n - 1}{2}\)

To solve this equation, we need to solve the Chinese Remainders Theorem (CRT). Obviously, SageMath will help us to solve this system.

For each value of \(x\) previously found, the function \(CRT(x_1, x_2, n, m)\) is used.

sage: CRT(54387532345611522562080964454373961410727797296305781726528152669705763479709, 24592060322915955458376742075654918743307884467086758475495911637571571854426, n, m)
sage: CRT(48377962721867712227812115825967814866900072246814115371447647755178792218507, 24592060322915955458376742075654918743307884467086758475495911637571571854426, n, m)
sage: CRT(13026594169836960633677904728346131575642115122520666941481783583028573455020, 24592060322915955458376742075654918743307884467086758475495911637571571854426, n, m)

One of the three values of \(z\) that SageMath provided us is the password of the second PDF.

It turns out that the password is the first value of \(z\) found: 1626912004825687681....

Once the second file is unlocked, there are 3 images of books written by Brigitte Friang. On one of them, we notice which one does not seem to be the default one. It is attached with the following number which is the flag to validate the challenge.


We’re done with our elliptical curves, I’m sure you’ve learned a lot, as I have.