Writeup DGSE - CTF - VX Elliptique

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

Introduction

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.

Start

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}")
        break
    else:
        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\).

R.<k>=PolynomialRing(GF(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
[(54387532345611522562080964454373961410727797296305781726528152669705763479709,
  1),
 (48377962721867712227812115825967814866900072246814115371447647755178792218507,
  1),
 (13026594169836960633677904728346131575642115122520666941481783583028573455020,
  1)]
sage: L=(y2^2 - (k^3 + a*k^2 + k)).roots();L
[(24592060322915955458376742075654918743307884467086758475495911637571571854426,
  1)]

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)
1626912004825687681266928944940137740110044614947501502667974700957265876831665835249437745227202257555252761324145945972681589648893511804029315415851794

sage: CRT(48377962721867712227812115825967814866900072246814115371447647755178792218507, 24592060322915955458376742075654918743307884467086758475495911637571571854426, n, m)
298866324658067043152535979487281689346418895898703530005178331141609468368515196383762924558049325643319211125756093104393630525207165166469723912137964

sage: CRT(13026594169836960633677904728346131575642115122520666941481783583028573455020, 24592060322915955458376742075654918743307884467086758475495911637571571854426, n, m)
669594744434241509260428824541316709656639804114134854927746139613649946258056910180935366203703863781306641125198724424226805412500527449207424152005314

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.

BF-2703-9020-RTQM

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