# Google Beginner CTF: ReadySetAction

**SPOILER WARNING: Go play the CTF at
[capturetheflag.withgoogle.com](https://capturetheflag.withgoogle.com/) first**

The challenge was a short python script with the following code:

```py
from Crypto.Util.number import *

flag = b"REDACTED"

p = getPrime(1024)
q = getPrime(1024)
n = p*q

m = bytes_to_long(flag)


c = pow(m,3,n)

print(c)
print(n)
#154780 ... 6709
#210348 ... 4477
#(i removed both 617 digit long numbers here)
```

It was immediatly obvious to me that this has to do with RSA cryptography
because it multiplies large primes and then does some powmod magic. Because I
didn't remember exactly how RSA worked, I quickly read the Wikipedia article
again - specifically section
[4.1 Attacks against plain RSA](https://en.wikipedia.org/wiki/RSA_%29cryptosystem%29#Attacks_against_plain_RSA)

The first item already seems like the solution:

> When encrypting with low encryption exponents (e.g., e = 3) and small values
> of the m (i.e., m < n1/e), the result of me is strictly less than the modulus
> n. In this case, ciphertexts can be decrypted easily by taking the eth root of
> the ciphertext over the integers.

Which would mean that $\sqrt[3]{c}$ is a solution _if_ $m$ is small enough.
However

$c = m^3 \mod n \\$

so the exponentiation could yield a much higher result that we dont get because
it is wrapped at $n$. So we can try out how often it wrapped:

$m = \sqrt[3]{c + x*n} \quad x \in \N\\$

where $x$ can be brute-forced if $m$ is sufficiently small. Back in python it
looks like this:

```py
c = ...
n = ...

# simple but bad binary search for n-th root
def nth_root(c,e):
    high = 1
    while high**e < c:
        high *= 2
    low = 0
    mid = 0
    last_mid = 0
    while mid**e != c:
        mid = (low + high) // 2
        if last_mid == mid:
            return 0 # i use 0 to indicate a failure
        if mid**e > c:
            high = mid
        else:
            low = mid
        last_mid = mid
    return mid

for x in range(100000):
    m = nth_root(c + n*x, e)
    # the probability of finding a perfect cube number is low, so any result is what we want
    if m != 0: print(long_to_bytes(m))
```

Thats it! With $x=1831$ we get our flag: `CTF{34sy_RS4_1s_e4sy_us3}`