EVEN RSA CAN BE BROKEN??? - picoCTF

La descripcion nos dice lo siguiente:

“Este servicio te proporciona una bandera (flag) encriptada. ¿Puedes desencriptarla solo con N y e?” y nos pide conectarnos usando netcat, tambien nos da el codigo fuente del programa

El enunciado sugiere que:

• Se usa RSA

• El reto omite la clave privada (d)

• Se debe romper la seguridad con solo N, e y el ciphertext

¿Qué es RSA?

RSA es un algoritmo de criptografía asimétrica inventado en 1977 por Rivest, Shamir y Adleman (de ahí el nombre R–S–A).

¿Qué significa criptografía asimétrica?

Usa dos claves diferentes:

• Una clave pública para cifrar

• Una clave privada para descifrar

Descargamos el codigo fuente que contiene la siguiente informacion:

Vemos que el mensaje se cifra de la siguiente manera:

y se generaba con:

Esto nos confirmó que si podíamos factorizar N, podíamos obtener d y descifrar c.

Usamos la pagina

https://factordb.com/

para ver si es factoriable:

N = 2 × q → esto no debería pasar nunca en RSA

Eso nos dio acceso a p = 2 y q = N // 2

Construimos el script :

tenemos:

usando la formula:

m = pow(c, d, N)

Y luego lo convertimos de número a texto con:

long_to_bytes(m)

Ejecutando el script tenemos:

Una vez obtenida la flag lo ponemos en el desafio:

y Resuelto!!!!!!