RSA Beginner

Se nos proporcionan estos números:

e: 3
c: 174422460809195453539354885823735245900172562989776845322302  
n: 245841236512478852752909734912575581815967630033049838269083

Tenemos el exponente $e$, el módulo $n$ y el texto cifrado $c$.

Está claro que estamos ante un criptosistema RSA. Vamos a recordar cómo funciona RSA:

Se eligen dos números primos $p$ y $q$ de forma que el módulo $n = p \cdot q$. Luego se escoge un exponente $e$ (normalmente 3 ó 65537) que sea coprimo con $\phi(n) = (p - 1) \cdot (q - 1)$.

Para cifrar un mensaje $m$ (en formato numérico), se tiene que realizar esta operación:

$$ c = m ^ e \mod{n} $$

Donde $c$ es el texto cifrado. Y para descifrar el texto cifrado, tenemos que calcular $d = e ^ {-1} \mod{\phi(n)}$ y luego realizar la siguiente operación:

$$ m = c ^ d \mod{n} $$

En este punto, la clave pública es el conjunto ${e, n}$, mientras que la clave privada está compuesta por ${p, q}$.

El criptosistema RSA será robusto en función de la dificultad para factorizar el módulo $n$. Si se pudiera factorizar, se podrían obtener $p$ y $q$ a partir de $n$ y por tanto calcular $\phi(n)$ y $d$.

Esta vez, el ódulo $n$ que tenemos es relativamente pequeño, por lo que podremos factorizarlo. Para ello, podemos ir a factordb.com e introducir el módulo:

Y ahora que tenemos $p$ y $q$, podemos usar Python para calcular $\phi(n)$ y $d$. Y finalmente hallar el mensaje $m$:

$ python3 -q
>>> e = 3
>>> c = 174422460809195453539354885823735245900172562989776845322302  
>>> n = 245841236512478852752909734912575581815967630033049838269083
>>> p = 416064700201658306196320137931
>>> q = 590872612825179551336102196593
>>> phi_n = (p - 1) * (q - 1)
>>> d = pow(e, -1, phi_n)
>>> m = pow(c, d, n)
>>> hex(m)
'0x4354466c6561726e7b7273345f69735f61773373306d337d'

El mensaje está en formato numérico, por lo que tenemos que decodificarlo como bytes en ASCII:

>>> bytes.fromhex('4354466c6561726e7b7273345f69735f61773373306d337d')  
b'CTFlearn{rs4_is_aw3s0m3}'