Mind your Ps and Qs
1 minuto de lectura
Tenemos la salida de un cifrado RSA:
Decrypt my super sick RSA:
c: 240986837130071017759137533082982207147971245672412893755780400885108149004760496
n: 831416828080417866340504968188990032810316193533653516022175784399720141076262857
e: 65537
Contexto de RSA
RSA funciona de manera que, dado un mensaje $m$ en formato decimal, podemos cifrarlo como sigue:
$$ c = m^e \mod{n} $$
Y para descifrar, se necesitan dos valores más: $\phi(n) = (p - 1) (q - 1)$ y $d = e^{-1} \mod{\phi(n)}$, de manera que:
$$ m = c^d \mod{n} $$
Vulnerabilidad
El módulo $n$ es relativamente corto, y por tanto se puede factorizar fácilmente Podemos encontrar los factores $p$ y $q$ con factor.db:
Una vez que tenemos $p$ y $q$ es trivial descifrar RSA, porque podemos calcular $\phi(n)$ y $d$.
Flag
$ python3 -q
>>> c = 240986837130071017759137533082982207147971245672412893755780400885108149004760496
>>> n = 831416828080417866340504968188990032810316193533653516022175784399720141076262857
>>> e = 65537
>>> p = 1593021310640923782355996681284584012117
>>> q = 521911930824021492581321351826927897005221
>>> assert n == p * q
>>> phi_n = (p - 1) * (q - 1)
>>> d = pow(e, -1, phi_n)
>>> m = pow(c, d, n)
>>> bytes.fromhex(hex(m)[2:])
b'picoCTF{sma11_N_n0_g0od_23540368}'