Pour ce challenge, il faut commencer par lire le code source qui a généré le message chiffré. Quand on le compare à une implémentation correcte de RSA, on remarque qu’un seul nombre premier à été choisi.
Il manque donc n et phi(n), qui sont les deux composants d’une clé privée. À la place, nous avonc donc une seule opération pour créer le message chiffré.
pow(flag, e, n)
Or comme e et n sont connus, il nous suffit juste de trouver l’opération inverse. Avec un peu de recherche, on trouve dans la doc de pyCryptoDome une fonction nommée inverse, qui nous donne l’exposant à utiliser pour retrouver notre flag.
Pour trouver notre exposant, il nous faut calculer l’inverse de e modulo phi(n), phi(n) pour un nombre premier étant tout simplement n-1
Dans le cas d’une multiplication de deux nombres premiers P et Q, comme c’est le cas dans RSA :
n = P * Q
phi(n) = (P - 1)*(Q - 1)
On arrive à un script qui calcule le flag :
import json
from Crypto.Util.number import inverse, long_to_bytes
e = ...
c = ...
n = ...
phi_n = n-1
inv = inverse(e, phi_n)
rep = pow( c , inv, n)
print(long_to_bytes(rep))