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