a muffin with purple glowing regions where a 3d vornoi function using chebychev distance exceeds some threshold

metamuffin's personal website


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:

todo10

Which would mean that c3 is a solution if m is small enough. However

c=m3[PARSE ERROR: Undefined("Command(\"mod\")")]n[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=c+x*n3x[PARSE ERROR: Undefined("Command(\"N\")")][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



Advertisement by a first-party
Advertisement by a third-party