# RSA Noob Write-Up

RSA Noob is a cryptography challenge from CTFLearn.

It is actually pretty simple. We are given a public key and a ciphertext. We need to decrypt the ciphertext to get the flag.

### Table of contents:

## Challenge

Here’s the challenge file:

```
e: 1
c: 9327565722767258308650643213344542404592011161659991421
n: 245841236512478852752909734912575581815967630033049838269083
```

## Solution

Let’s remember the RSA algorithm:

- Choose two large prime numbers,
`p`

and`q`

. - Compute
`n = p * q`

. - Compute
`phi = (p - 1) * (q - 1)`

. - Choose an integer
`e`

such that`1 < e < phi`

and`e`

is coprime to`phi`

. - Compute
`d`

such that`d * e ≡ 1 (mod phi)`

. - The public key is
`(e, n)`

and the private key is`(d, n)`

. - To encrypt a message
`m`

, compute`c = m^e (mod n)`

. - To decrypt a ciphertext
`c`

, compute`m = c^d (mod n)`

.

We have the public key `(e, n)`

and the ciphertext `c`

. We need to decrypt the ciphertext to get the flag. Since `n`

is small, we can factorize it to get `p`

and `q`

. Then we can compute `phi`

and `d`

to decrypt the ciphertext.

Here’s the Python script to factorize `n`

.

```
from sage.all import *
n = 245841236512478852752909734912575581815967630033049838269083
factorized = factor(n)
p = factorized[0][0]
q = factorized[1][0]
print(f"p: {p}")
print(f"q: {q}")
```

We are able to factorize `n`

into `p`

and `q`

. Now we can compute `phi`

and `d`

to decrypt the ciphertext.

```
from Crypto.Util.number import inverse
e = 1
c = 9327565722767258308650643213344542404592011161659991421
n = 245841236512478852752909734912575581815967630033049838269083
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, n)
print(bytes.fromhex(hex(m)[2:]).decode())
```

## Bonus

Since `e`

is 1, we can directly decrypt the ciphertext without factorizing `n`

.

```
c = 9327565722767258308650643213344542404592011161659991421
print(bytes.fromhex(hex(m)[2:]).decode())
```

This is because `m = c^e (mod n)`

is equal to `m = c`

when `c^e`

less than `n`

. There’s no need to compute `d`

in this case.