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 60 candidats. Il s’agit d’une épreuve catégorisée comme facile ⭐.
Énoncé
Cette épreuve est une introduction à la série. Il s’agit de prendre en main la machine virtuelle ainsi que son jeu d’instruction. On prend également connaissance des valeurs d’entrée:
- Un exposant public $e$, $3\leq e < 2^{256}$
- 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é
La difficulté principale de cette épreuve est d’avoir une méthode efficace pour générer des nombres premiers $p$ et $q$ de façon à satisfaire le critère de la taille de $N$. La méthode naïve consiste à générer $p$ et $q$, puis à calculer $N$ et enfin à vérifier la taille de $N$. Cette méthode n’est pas la plus efficace et, sauf à avoir beaucoup de chance, elle ne permettait pas d’avoir le flag dans le temps imparti.
Solution
Si on choisit un nombre aléatoire $r$ de $x$ bits, alors $2^{x-1}\leq x<2^x$. Ainsi le produit de deux nombres aléatoires de $x$ bits est compris entre $2^{2x-2}$ et $2^{2x}$, alors qu’on cherche un encadrement entre $2^{t-1}$ et $2^t$. Il est ainsi nécessaire de connaître la racine carrée entière de $2^{t-1}$. La méthode pour calculer une telle valeur était d’ailleurs l’objet de l’épreuve il était une bergère.
Pour $t=1024$, si on pose s=0xb504f333f9de6484597d89b3754abe9f1d6f60ba893ba84ced17ac85833399154afc83043ab8a2c3a8b1fe6fdc83db390f74a85e439c7b4a780487363dfa2768, alors $s^{2} < 2^{t-1} < (s+1)^2$.
Pour $t=512$, si on pose s'=0xb504f333f9de6484597d89b3754abe9f1d6f60ba893ba84ced17ac8583339915, alors $s’^{2} < 2^{t-1} < (s’+1)^2$. On peut noter la ressemblance entre les racines carréees.
Générer des nombres premiers plus grands que la racine carrée de $2^{t-1}$ est donc une solution possible. Pour cela, soit on inclut la racine carrée de $2^{1023}$ dans notre code, soit on remarque l’écriture binaire de 0xb=0b1011 et on force les deux bits de poids fort des nombres premiers à 1.
Pour le reste, il faut s’assurer de la primalité entre $(p-1)$ et $e$ (de même entre $q-1$ et $e$) via un calcul de pgcd.
Le pseudo-code pour générer un nombre premier est donc le suivant:
- Prendre un nombre aléatoire $r$ de taille $\frac{t}{2}$.
- Soit forcer les deux bits de poids forts de $r$ à 1, soit rejeter si $r$ est inférieur à $2^{\frac{t-1}{2}}$ (ou que $r^2<2^{t-1}$)
- Tester si $e$ et $r-1$ sont premiers entre eux $\mathrm{gcd}(e,r-1)=1$
- Tester si $r$ est un nombre premier
Après avoir généré $p$ et $q$ de cette façon, le reste ne pose pas de problèmes puisque la machine fournit l’instruction d’inversion modulaire.