---
tags: Crypto, Brigitte_Friang
---

# Write-up "VX Elliptique", Crypto, Opération Brigitte Friang, DGSE, 2020

###### tags: Crypto, Brigitte_Friang

## Présentation du challenge
### Énoncé

*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.*

### Données

`VX_elliptique.pdf` : fichier contenant les informations pour trouver le mot de passe du second fichier


`livres_Friang.pdf` : fichier pdf protégé par un mot de passe

## Recherche du mot de passe
On dipose de deux fichiers pdf, l'un chiffré, l'autre non. Le pdf non chiffré contient notamment **l'équation d'une courbe elliptique**, ainsi que des informations sur des points de cette courbe.

\begin{equation}
y^2 \: \mbox{mod $n$} = (x^3 + Ax^2 + x) \: \mbox{mod $n$} \: \: \: \: \: (1)
\end{equation}

La marche à suivre semble assez linéaire :
* Trouver l'inconnue $A$ à partir de $x$ et $y$
* Trouver $x_1$ et $x_2$ à partir de $y_1$ et $y_2$
* Trouver $z$ à partir de $x_1$ et $x_2$

On va se servir du logiciel de calcul **sage** pour effectuer la plupart de nos calculs.

### Étape 1 : Recherche de $A$

#### Recherche de l'équation

On connait un couple $(x,y)$ valide, on a donc une seule inconnue. On va d'abord se ramener à une équation modulaire linéaire à partir de $(1)$ :

\begin{equation}
y^2 \: \mbox{mod $n$} = (x^3 + Ax^2 + x) \: \mbox{mod $n$} \Leftrightarrow(y^2 - x^3 - x) \: \mbox{mod $n$} = A x^2 \: \mbox{mod $n$}
\end{equation}

Posons pour plus de clarté :

$b = (y^2 - x^3 - x) \: \mbox{mod n} \\
a = x^2 \\
A = X$

On dispose alors d'une équation diophantienne d'inconnue $X$ :

\begin{equation}
aX \equiv b \: \mbox{mod $n$} \: \: \: \: \: (2)
\end{equation}

#### Résolution de l'équation

Cette équation admet une solution si et seulement si le **pgcd** de $a$ et de $n$ divise $b$. Leur pgcd s'obtient avec la fonction $\verb|gcd(a, n)|$ de *sage*.


La fonction nous renvoie $\verb|gcd(a, n) = 1|$ On a donc $a$ et $n$ premiers entre eux.
Or comme $a$ et $n$ sont premiers entre eux, selon le **théorème de Bézout** il existe $u$ et $v$ tel que $ua + vn = 1$. En particulier il existe un entier $u$ tel que $ua \equiv 1 \: \mbox{mod n}$. C'est l'**inverse modulaire** de $a$, que l'on peut calculer avec la fonction $\verb|inverse_mod(a, n)|$ de *sage*.


On trouve

\begin{split}
u = 33208700369591938334711589173041607863\\
...330741681120497861327034574193752378903
\end{split}

On multiplie maintenant l'équation $(2)$ par $u$ :

\begin{equation}
uaX \equiv ub \: \mbox{mod $n$}
\end{equation}

Comme $ua \equiv 1 \: \mbox{mod n}$ on a :

\begin{equation}
X \equiv ub \: \mbox{mod $n$}
\end{equation}

Et donc après application numérique et application du modulo :

\begin{equation}
X \equiv 486662 \: \mbox{mod $n$}
\end{equation}

Finalement avec $k \in \mathbb{Z}$ on obtient l'ensemble des solutions pour $X$ :

\begin{equation}
X = 486662 + kn
\end{equation}

On peut donc récupérer notre inconnue $A$ en prenant $k = 0$. Ainsi on a **A=486662** (666 ? Encore une diablerie de la DGSE...)

### Étape 2 : Recherche de $x_1$ et $x_2$

Maintenant que l'on dispose de l'équation complète et connaissant les valeurs $y_1$ et $y_2$, on peut récupérer les valeurs $x_1$ et $x_2$ correspondantes.
Pour ce faire on va une nouvelle fois se servir de *sage* pour effectuer des opérations dans les corps finis.
On veut travailler modulo $n$, on définit donc notre anneau de polynômes avec le champ de Galois de cardinal $n$ :


On va ensuite chercher les **racines** pour $y = y_1$ et $y = y_2$ du polynôme suivant :
\begin{equation}
x^3 + Ax^2 + x - y^2
\end{equation}


On trouve trois racines différentes $x_{11}$, $x_{12}$ et $x_{13}$ pour $y = y_1$ et une unique racine triple ${x_{20}}$ pour $y = y_2$.

### Étape 3 : Recherche de $z$

On dispose maintenant de toutes les informations nécessaires pour réaliser la dernière étape de notre périple mathématique. On se trouve cette fois-ci dans le cas d'un système d'équation modulaire de type :

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

Avec $a = x_1$, $b = x_2$, et $m = \frac{n - 1}{2}$.
Encore une fois notre boite à outils magique possède l'instrument adapté : la fonction $\verb|crt(x_1, x_2, n, m)|$ de *sage* permet justement de résoudre ce type de système. On prend comme valeur pour $x_1$ la valeur de la 1ère racine trouvée $x_{11}$, et on testera les autres si besoin.


La fonction nous sort une valeur

\begin{split}
z = 1626912004825687681266928944940137740110044614947501\\
...502667974700957265876831665835249437745227202257555\\
...252761324145945972681589648893511804029315415851794
\end{split}

Autant dire tout de suite qu'un `Ctrl + C Ctrl + V` s'impose. Rentrons notre "nombre de passe" dans le `livres_Friang.pdf`, et bingo, les portes du paradis s'ouvrent devant nous.

## Scan du code barre

Le fichier dévérouillé contient simplement les photos de couverture de trois livres tous écrits par Brigitte Friang elle même, *Marche autant que tu pourras*, *Regarde-toi qui meurs* et *Comme un verger avant l'hiver*.


On remarque rapidement la présence d'un code barre sur la couverture de *Regarde-toi qui meurs* qui n'a à priori rien à faire ici, avec un code d'identification au dessus : **BF-2703-9020-RTQM**

Mission accomplie, repos soldat.

---
###### -- *MrR0bot*