Click to expand challenge code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import getPrime, bytes_to_long


flag = "FL1TZ{*********}"

p = getPrime(512)
q = getPrime(512)
n = p * q
e = 5
m = bytes_to_long(flag.encode())
c = pow(m, e, n)

data = {
    "n": n,
    "e": e,
    "c": c
}

with open("computer.json", "w") as f:
    import json
    json.dump(data, f, indent=4)

Since this CTF was destined to be pretty advanced, I didn’t want beginner players to leave with 0 solves. So this challenge is a freebie.
It’s a textbook RSA challenge at the end of the day :)

Solution

Seeing $e=3$ is a pretty obvious indication that you’re gonna use a Low exponent Attack

Low exponent attack

If you’re unfamiliar with this attack, go play on cryptohack first to get the basics of RSA.
But to set the stage, since we know that $c=m^e\mod n$, if we know that e is relatively small (aka anything below 0x10001), we can safely assume that $c = m + kn$ with $k \in \Z$ and that $k$ is relatively small ($k \lt 2^{16}$).

This is a bruteforceable range so what we can do is to just loop around the values in that range until one decrypts our flag correctly.
to decrypt we just take $m=\sqrt[3]{c+kn}$ over small values of $k$

Solver

Click to expand solver code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
from sympy import integer_nthroot
from Crypto.Util.number import long_to_bytes
data = {
  "n": 73539119616387953390739800349162296889929546890090543889993874511622797249196267131045564445773173905414213126551404529575686960651044977944959808993198036611015159472932349483222966379786679562526483302790715340879782393710146767878051963120396764875749481672901593410527395827059347330427901154076729932223,
  "e": 5,
  "c": 9468915152993094883603033505359730336969579215367867376501348539807899828151112958315663505504751915445454464880699413704160458880583680307083100176804875698702059358758480728617067234170370891821622331498749208246106295081101
}
n = data["n"]
e = data["e"]
c = data["c"]
k = 0
while True:
    m = integer_nthroot(c + k*n, e)
    k+=1
    if not m[1]:
        continue
    try:
        flag = long_to_bytes(m[0])
        print(flag.decode())
        break
    except Exception as e:
        continue

FL1TZ{N0_surpr153S}