Un RSA incassable? (Cryptanalyse) - 404CTF2022

Principe:
Factoriser le N d'un RSA pour trouver phi(N) et en déduire d, la clef de déchiffrement

Infos (cf menu latéral):
🚩 Flaggué! +100 points gagnés — 💾 Téléchargez les fichiers du challenge
404CTF{F41t35_4tt3t10n5_4v3c_l3_R54}

Le "challenge"

Cassez un RSA bien choisi

RSA et factorisation

On essaie déjà de factoriser N: sur un malentendu, ça peut marcher? Et… oui!

Sage est un équivalent open-source à Maple, très efficace pour faire du calcul symbolique (c'est à dire qu'il sait résoudre des équations, manipuler des inconnues et des variables, etc)

Normalement, pour que RSA soit sécurisé N ne doit pas être factorisable facilement et doit être le produit de deux grands nombres premiers. Ici, on a un N composé de nombreux facteurs, ce qui est totalement inhabituel (et ce qui explique la factorisation rapide)

Phi

Factoriser N nous permet de calculer phi(N) puis d, la clef de déchiffrement
On demande donc à Sage de calculer phi(N)

Notez que phi(AB) = phi(A)phi(B) d'où le fait que Sage puisse rapidement calculer phi(N). Si le calcul avait été long, on aurait pu utiliser la décomposition de N pour chaquer le phi de chacun de ses facteurs, et en faire ensuite le produit

d

Et il ne reste qu'à calculer l'inverse de e (65537) modulo phi(N) pour trouver d

Flag

On déchiffre alors le message avec le d trouvé, et on obtient le flag

En pratique, en déchiffrant, on obtient un nombre m:
101384582033510951325010359008727680625145975108923307577800692180149739885949739152509
On le bascule en base 16:
0x3430344354467b4634317433355f347474337431306e355f347633635f6c335f5235347d
Et on convertit chaque paire d'octets via la table ASCII
404CTF{F41t35_4tt3t10n5_4v3c_l3_R54}

Sage-only

Je suis passé par dCode ici, mais on peut très bien utiliser Sage pour trouver d
Puis pour trouver m, hx et le message en ASCII

Flag: 404CTF{F41t35_4tt3t10n5_4v3c_l3_R54}