Cette solution aborde les concepts attendus, mais ne fournit pas le code source nécessaire à l’obtention du flag.
Épreuve
Épreuve du FCSC 2025, résolue par 21 candidats. Il s’agit d’une épreuve catégorisée comme moyenne ⭐⭐.
Énoncé
Rappel des valeurs d’entrée:
- Un exposant public $e$, $3\leq e < 2^{256}$, tel que $e$ est un nombre premier
- Une taille en bit $t$ du module public, $512\leq t\leq 1024$ et $t=0\mod 32$ ,
ainsi que des valeurs attendues:
- Un module public $N$ tel que $N=p\cdot q$
- Deux nombres premiers $p$ et $q$, tels que $2^{t-1}\leq N<2^{t}$
- Deux exposants privés $d_p$ et $d_q$ tels que $e\cdot d_p=1\mod (p-1)$ et $e\cdot d_q=1\mod (q-1)$
- Un exposant privé $d$ tel que pour tout message $m$ non nul, $m^{e\cdot d}=1\mod N$. Soit donc $e\cdot d=1\mod \varphi(N)$ ou $e\cdot d=1\mod \lambda(N)$
- Une valeur d’aide en cas d’optimisation de la signature à l’aide du théorème des reste chinois : $q^{-1}\mod p$.
Par ailleurs il est vérifié que tous les nombres premiers générés sont différents les uns des autres.
Difficulté
On ajoute à la difficulté de la première épreuve la restriction d’utilisation de certaines opérations de la machine virtuelle.
Afin de simuler une génération de clef RSA ne reposant pas sur l’algorithme d’Euclide étendu, l’opération d’inversion modulaire, celle du calcul de pgcd et la division euclidienne ne sont plus disponibles. Par ailleurs l’utilisation des opérations d’addition, de soustraction, de décalage des bits est restreinte afin d’empêcher les participants de développer leur propre algorithme d’Euclide étendu.
Il faut donc trouver une astuce pour les éléments suivants:
- S’assurer de la primalité entre $e$ et $p-1$ (respectivement $q-1$)
- Calculer l’inverse de $e$ modulo $p-1$ (respectivement $q-1$)
- Calculer l’inverse de $e$ modulo $\varphi(N)$
- Calculer l’inverse de $q$ modulo $p$
Solution
Il existe un article de Marc Joye et Pascal Paillier qui couvre le sujet de l’épreuve (découvert a posteriori de la création de l’épreuve).
Inversion de $q$
Commençons par le plus facile, à savoir le calcul de l’inverse de $q$. À l’aide du (petit) théorème de Fermat, on a:
$$ q\cdot q^{p-2} = 1\mod p $$
Calcul de $d_p$, $d_q$, $d$
Pour la suite, revenons à la définition de $d_p$ et $d_q$. Par définition, $e\cdot d_p=1 \mod (p-1)$, donc il existe $k_p$ tel que:
$$ e\cdot d_p = 1 + k_p\cdot (p-1) $$
Nous pouvons même préciser la valeur de $k_p$ :
$$ k_p = -(p-1)^{-1}\mod e $$
Comme $e$ est premier, le petit théorème de Fermat donne à nouveau un moyen de calculer $k_p$ à l’aide d’une exponentiation. Cette exponentiation est d’ailleurs très efficace puisque $e$ est petit. Le calcul de $d_p$ se fait simplement à l’aide d’une division entière:
$$ d_p = \frac{1+k_p\cdot (p-1)}{e} $$
De même, nous allons pouvoir calculer $d_q$ et $d$.
Test de primalité entre $e$ et $p-1$, $q-1$
En ce qui concerne le test de primalité, nous savons déjà que $e$ est un nombre premier. Si $p-1$ (respectivement $q-1$) n’est pas un multiple de $e$, alors il sera premier avec $e$. Ainsi en s’assurant que $p-1\neq 0\mod e$, on s’assure que $p-1$ est inversible modulo $e$. Cette réduction modulaire est d’ailleurs nécessaire pour le calcul de $k_p$.