RSA Beginner

We are given these numbers:

e: 3
c: 174422460809195453539354885823735245900172562989776845322302  
n: 245841236512478852752909734912575581815967630033049838269083

We have the exponent $e$, the modulus $n$ and the ciphertext $c$.

It is clear that we have an RSA cryptosystem. Let’s review how RSA works:

Two prime numbers $p$ and $q$ are chosen so that we have the modulus $n = p \cdot q$. Then an exponent $e$ is chosen (usually 3 or 65537) so that it is coprime with $\phi(n) = (p - 1) \cdot (q - 1)$.

In order to encrypt a message $m$ (in numeric format), this operation must be performed:

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

So that $c$ is the ciphertext. And to decrypt the ciphertext, we must first calculate $d = e ^ {-1} \mod{\phi(n)}$ and then compute this:

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

At this point, the public key is the set ${e, n}$, whereas the private key is formed by ${p, q}$.

The RSA cryptosystem will be robust as far as the modulus $n$ is difficult to factorize. Otherwise, one could compute $p$ and $q$ from $n$ and therefore compute $\phi(n)$ and $d$.

This time, the modulus $n$ we have is relatively short, so we might be able to factorize it. For that purpose, we can go to factordb.com and introduce the modulus:

Now that we have $p$ and $q$, we can use Python to compute $\phi(n)$ and $d$. And finally, compute the message $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'

Remember that the message is in numeric format, so we must decode it as ASCII bytes:

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