Le défi se compose uniquement d’un fichier output.txt comportant trois grands nombres nommés n, e, c, où selon les notations usuelles:
ndésigne le module public d’une clef RSAedésigne l’exposant public d’une clef RSAcdésigne un chiffré RSA, de la forme $\mathrm{flag}^e \mod n$
Afin de pouvoir déchiffrer et retrouver le flag, il faut calculer l’exposant privé d. A priori il s’agit d’un problème difficile, sauf si on connaît la factorisation de n.
Le module public est donné sous forme décimale et ressemble à un nombre aléatoire. On peut toutefois l’affiché sous forme hexadécimale via la fonction hex() de python.
On trouve alors assez rapidement
n = (0x99<<(4096-8)) + (0x15e2e92<<(2069-25)) + 0xad629a0a95
La méthode bit_length() permet d’obtenir rapidement les valeurs 4096 et 2069
Si n est bien un module public RSA, alors il est sous la forme n=p.q où p et q sont deux nombres premiers.
Posons $p_1$, $p_0$ et $q_1$, $q_0$, tels que
n = (p_1.2^{2044}+p_0)(q_1.2^{2044}+q_0) = p_1.q_1.2^{4088}+(p_1.q_0+p_0.q_1).2^{2044}+p_0.q_0
Il suffit alors de factoriser les petites valeurs 0x99 et 0xad629a0a95 (par exemple à l’aide d’un outil en ligne):
p1.q1 = 0x99 = 17.9
p0.p0 = 0xad629a0a95 = 807071 . 922699
En posant $p=17.2^{2044}+807071$, $q= 9.2^{2044}+ 922699$, on constate que $p_1.q_0+p_0.q_1 = \mathtt{0x15e2e92}$.
Par ailleurs on peut vérifier que p et q sont bien des nombres premiers grâce à la fonction gmpy2.is_prime(p).
On trouve alors d via le calcul d = gmpy2.invert(e, (p-1)*(q-1))
Il suffit de déchiffrer et de formater le résultat:
>>> bytearray.fromhex(hex(gmpy2.powmod(c,d,n))[2:])
bytearray(b'ECSC{a8dbf9b45fc442592cb80221e1ac8ce1bba4b462249d4cd0ac1ac1e290ef95dd}')