On dispose d’un fichier d’une (très) mauvaise implémentation d’un algorithme de chiffrement RSA. Il faut remarquer que le module $N$ n’est pas le produit de deux nombres premiers mais un seul très grand nombre premier. (Voir https://fr.wikipedia.org/wiki/Chiffrement_RSA).
La sécurité de RSA repose principalement sur la factorisation d’un nombre $N$ produit de deux grands nombres premiers. La clé privée est générée de cette manière $ed \equiv 1 \pmod{\phi(N)}$ avec $e$ l’exposant public et $\phi(N)$ l’indicatrice d’Euler qui désigne le nombre d’entiers premiers avec $N$ (Voir https://fr.wikipedia.org/wiki/Indicatrice_d%27Euler) et $N$ le module RSA. Pour comprendre la résolution du challenge il faut connaître deux propriétés remarquables de l’indicatrice d’Euler:
-
Pour $p$ premier, $\phi(p) = p-1$, en effet les entiers premiers avec p dans $[1,p]$ sont tous les entiers sauf p lui-même. (Voir https://fr.wikipedia.org/wiki/Nombre_premier).
-
L’indicatrice d’euler est une fonction multiplicative, c’est à dire que si $N=pq$ avec p et q premiers alors $\phi(N) = \phi(pq) = \phi(p)\phi(q) = (p-1)(q-1)$
Alors, la difficulté pour retrouver la clé privée réside dans la connaissance des facteurs de $N$. Dans notre cas $N$ n’est pas le produit de deux nombres premiers mais un nombre premier, alors $\phi(N) = N-1$ donc cette difficulté n’existe plus si nous utilisons qu’un seul nombre premier.
En se reportant à l’algorithme de déchiffrement, on obtient le code suivant:
from Crypto.Util.number import *
n = 22914764349697556963541692665721076425490063991574936243571428156261302060328685591556514036751777776065771167330244010708082147401402002914377904950080486799957005111360365028092884367373338454223568447811216200859660057226322801828334633020895296785582519610777820724907394060126570265818769159991752144783469338557691407102432786644694590118176582000965124360500257946304028767088296724907062561163478654995994205065812479605136088813543435895840276066683243706020091519857275219422246006137390619897086478975872204136389082598585864385077220265194919486850918633328368814287347732293510186569121425821644289329813
e = 65537
c = 11189917160698738647911433493693285101538131455035611550077950709107429331298329502327358588774261161674422351739941120882289954400477590502272629693853242116507000433761914368814656180874783594812260498542390500221519883099478550863172147588922341571443502449435143090576514228274833316274013491937919397957017546671325357027765817692571583998487352090789855980131184451611087822399088669705683765370510052781742383736278295296012267794429263720509724794426552010741678342838319060084074826713065120930332229122961216786019982413982114571551833129932338204333681414465713448112309599140515483842800125894387412148599
d = pow(e,-1,n-1) # Calcul de la clé privée
print(f"Le flag est : {long_to_bytes(pow(c,d,n)).decode()}")
Le flag est : FCSC{d0bf88291bcd488f28a809c9ae79d53da9caefc85b3790f57615e61c70a45f3c}