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 6 candidats. Il s’agit d’une épreuve catégorisée comme difficile ⭐⭐⭐.
É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é des deux premières épreuves un jeu d’instruction encore plus restreint. Il va falloir utiliser les instructions du processeur dédié au calcul modulaire. De plus ce processeur a une taille limitée, impossible d’avoir des résultats plus grand que 1024 bits.
Il faut donc trouver une astuce pour les éléments suivants:
- Prendre en main l’arithmétique de Montgomery
- Calculer une multiplication (pour obtenir $N$ à partir de $p$ et $q$)
- Calculer l’inverse de $e$ modulo $\varphi(N)$ sans dépasser la taille limitée
Solution
Arithmétique de Montgomery
Un produit de Montgomery est défini par :
$$ x\star y=x\cdot y\cdot R^{-1}\mod M $$
pour un module $M$, une constante $R$ qui dépend de la taille de travail et deux valeurs $x$ et $y$. Le résultat est correct si les entrées $x$ et $y$ sont telles que $x\cdot y < R\cdot M$.
On a $(aR)\star (bR)=(ab)R\mod M$ et $aR+bR=(a+b)R\mod M$. On parle alors de forme de Montgomery ou de représentation de Montgomery pour la valeur $aR$, représentant $a$. À partir de la constante $RR=R^2\mod M$, on peut facilement calculer la représentation de Montgomery de $a$: $a\star RR=aR\mod M$. Un simple produit par 1 permet de revenir à la valeur de $a$: $aR\star 1=a\mod M$. À noter que dans ce cas $aR$ peut être de la taille de $R\cdot M$, et donc très gros par rapport au module.
Le calcul de $RR$ peut se faire relativement efficacement, et il est proposé par le processeur de la VM. L’utilisateur peut également éviter ce calcul s’il connaît déjà la valeur de $RR$ (par exemple pour le cas où $RR=1$).
Il n’est pas toujours nécessaire de calculer $RR$. Par exemple dans le cas d’un calcul d’inverse modulaire on a:
$$ \mathrm{MPOW}(x,\varphi(M)-1,M)=R\cdot(x\cdot R^{-1})^{\varphi(M)-1}\mod M = RR\cdot x^{-1}\mod M $$
Calcul non modulaire
Si un module $x$ est plus grand que le résultat d’une opération, alors le résultat est le même que cette opération ait été effectuée sur $\mathbb{Z}$ ou sur $\mathbb{Z}/x\mathbb{Z}$. À noter que $x$ n’a pas besoin d’être un nombre premier ici.
Un bon candidat pour $x$ est le module $2^{w}-1$, où $w$ est la taille de travail du processeur de Montgomery. En effet dans ce cas la constant $R$ de Montgomery vaut 1 !
Calcul de $d$
Solution du concepteur
Nous allons utiliser la formule suivante :
$$ d = -(e\cdot d_p\cdot d_q -d_p-d_q)\mod \varphi(N) $$
qui vérifie bien $d\mod (p-1) = d_p$ et $d\mod (q-1)=d_q$.
Le but va être de calculer modulo $\varphi(N)$ et même plus précisément modulo $\frac{\varphi(N)}{2}$, noté $\varphi_2$.
Toutefois $\varphi(N)=(p-1)\cdot (q-1)$ est une valeur paire, or le processeur de Montgomery ne fonctionne que pour les modules impairs. En se restreignant aux premiers $p$ et $q$ congrus à 3 modulo 4, nous savons que $\frac{\varphi(N)}{4}$ est un nombre impair, et posons $\varphi_4 = \frac{\varphi(N)}{4}$.
Nous calculons $d_{\varphi_4}=(-e\cdot d_p\cdot d_q+d_p+d_q)\mod \varphi_4$ via le processeur de Montgomery.
Nous savons déjà que $d$ est impair, puisque $e$ est impair et que $e\cdot d$ est impair, soit $d_2 = 1\mod 2$.
Nous pouvons donc faire une recombinaison via le théorème des restes chinois, avec les modules $\varphi_4$ et $2$:
$$ ((d_2-d_{\varphi_4})\cdot \varphi_4^{-1}\mod 2)\cdot \varphi_4+d_{\varphi_4} $$
C’est assez facile à calculer, puisque $\varphi_4^{-1}\mod 2=1$, et on doit regarder la parité de $d_{\varphi_4}$:
$$
d\mod \varphi_2=\begin{cases}
d_{\varphi_4} &, d_{\varphi_4}=1\mod 2\
d_{\varphi_4}+\varphi_4 &, d_{\varphi_4}=0\mod 2
\end{cases}
$$
Solution d’un participant 1
Revenons à la définition de $d_p$ et $d$. 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 $$
De même, on a : $e\cdot d = 1+k\cdot \varphi(N)$ et $k= -\varphi(N)^{-1}\mod e$
Comme $e$ peut faire jusqu’à 256 bits, et que $\varphi(N)$ est très proche de $N$, le calcul direct de $k\cdot \varphi(N)$ dépasse la capacité du processeur.
Il va donc falloir ruser. L’astuce consiste à décomposer le calcul $k\cdot \varphi(N) = k\cdot (q-1)\cdot (p-1)$ en réduisant la taille à l’aide d’une division par $e$ après la première multiplication. Il faut donc construire un multiple de $e$, par exemple:
$$ k\cdot (q-1) - k_p = k_p - k_p \mod e= 0 \mod e $$
Par ailleurs, on a:
$$ (k\cdot (q-1) - k_p)\cdot (p-1) = k\cdot\varphi(N)-k_p\cdot (p-1) = (e\cdot d-1)-(e\cdot d_p-1) $$
Ainsi on peut calculer $d$:
$$ d = \frac{(k\cdot (q-1) - k_p)}{e}\cdot (p-1)+d_p $$
Remarque: Une seule exponentiation est nécessaire. À partir de $k$, on peut calculer $k_p$ et $k_q$, puisque $k_p = k\cdot (q-1)\mod e$ et $k_q=k\cdot (p-1)\mod e$.
Solution d’un participant 2
On calcule simplement $d = (1+k\cdot\varphi(N))\cdot e^{-1} \mod x$, où $x$ est un nombre premier supérieur à $\varphi(N)$. Par exemple nous pouvons prendre $x=2^{1024}-105$. Cette solution est un peu moins performante si le calcul de $e^{-1}\mod x$ est effectué via une exponentiation. À noter toutefois que cette valeur peut être précalculée (pour une série de $e$ possibles) ou calculée avec un algorithme d’Euclide étendu, car ne faisant pas intervenir de valeurs secrètes.