# metamuffin's personal website

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:

todo10

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

$c={m}^{3}\text{[PARSE ERROR: Undefined("Command(\"mod\")")]}n\text{[PARSE ERROR: NewLine]}$

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}\phantom{\rule{1em}{0ex}}x\in \text{[PARSE ERROR: Undefined("Command(\"N\")")]}\text{[PARSE ERROR: NewLine]}$

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

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

Article written by metamuffin, text licenced under CC BY-ND 4.0, non-trivial code blocks under GPL-3.0-only except where indicated otherwise