# Google Beginner CTF: ReadySetAction

**SPOILER WARNING: Go play the CTF at
capturetheflag.withgoogle.com first**

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

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

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}$

$c={m}^{3}\phantom{\rule{0ex}{0ex}}\phantom{\rule{0.6667em}{0ex}}\mathrm{m}\mathrm{o}\mathrm{d}\text{\hspace{0.17em}}\text{\hspace{0.17em}}n$

so the exponentiation could yield a much higher result that we dont get because it is wrapped at $n$

$m=\sqrt[3]{c+x\ast n}\phantom{\rule{1em}{0ex}}x\in \mathbb{N}$

where $x$

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$

changes to this article (as recorded with git; visible on codeberg)

2022-09-26 6bccd84 language improvement 2022-09-25 7959408 gctf writeup: readysetaction