ezRSA#

Field	Detail
CTF	VulnByDefault (VBD) CTF
Category	Crypto
Points	50
Difficulty	Very Easy
Flag Format	`VBD{}`
Author	VBD

Challenge#

You need a quantum computer to break 2048 bit RSA

We’re given two files:

chal.py#

1
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
2

3
p = getPrime(1024)
4
q = getPrime(1024)
5
n = p * q
6
e = 65537
7
m = bytes_to_long(b"VBD{redacted}")
8
c = pow(m, e, n)
9

10
print(f"n = {n}")
11
print(f"e = {e}")
12
print(f"c = {c}")

output.txt#

1
n = 12139060964644731299616588431144357295893267399513044368168674423463865922105679298581275775928030934980825037505343533330532571920073270930494856617633446603701570111731333521968321149524054928051226723496783699003262124686452853097178492606004846446132558563235032863230996887915790170744047365490053682585227928502155463679243464129824500488865322057558073443748579179673923873951539414050323136771458433363878212559520936505989861408021168584818265882088807751868274225219033214124264482250739877294262244348169816175715334853867011387005662752280370313684398535181288043659304611812082202634455705893735722144691
2
e = 65537
3
c = 2027061416518539479227361922503073616455584052179531114664299751979222876324402343920874746923263105838961615269889480729305386812288353942096836088189138045056661651351561704740399755324098095245350717206509435579347680523366257195142346380022013984134393207328313972552189607141838671464207713340780455198087734627261571224948916053344495541325279422710899259606254672851662179439172534792519654723049214197013878859128524628078962920429097010773719219281227340703928176601061418390449183543575468085737641002867191684818036182905347659400615796230893276884470919389823485665892343397687944728461714491295766674366

Solution#

Standard textbook RSA. To decrypt, we need to factor n into p and q.

Despite the challenge taunt (“You need a quantum computer”), this n is already factored in factordb.com â€” meaning the primes were previously known or easily factorable.

Step 1: Factor n via FactorDB#

1
from factordb.factordb import FactorDB
2

3
f = FactorDB(n)
4
f.connect()
5
print(f.get_status())   # FF = fully factored
6
p, q = f.get_factor_list()

Step 2: Standard RSA Decryption#

1
phi = (p - 1) * (q - 1)
2
d = pow(e, -1, phi)        # modular inverse (private exponent)
3
m = pow(c, d, n)           # decrypt
4
flag = m.to_bytes((m.bit_length() + 7) // 8, 'big').decode()
5
print(flag)

Full Solve Script#

1
from factordb.factordb import FactorDB
2

3
n = 12139060964644731299616588431144357295893267399513044368168674423463865922105679298581275775928030934980825037505343533330532571920073270930494856617633446603701570111731333521968321149524054928051226723496783699003262124686452853097178492606004846446132558563235032863230996887915790170744047365490053682585227928502155463679243464129824500488865322057558073443748579179673923873951539414050323136771458433363878212559520936505989861408021168584818265882088807751868274225219033214124264482250739877294262244348169816175715334853867011387005662752280370313684398535181288043659304611812082202634455705893735722144691
4
e = 65537
5
c = 2027061416518539479227361922503073616455584052179531114664299751979222876324402343920874746923263105838961615269889480729305386812288353942096836088189138045056661651351561704740399755324098095245350717206509435579347680523366257195142346380022013984134393207328313972552189607141838671464207713340780455198087734627261571224948916053344495541325279422710899259606254672851662179439172534792519654723049214197013878859128524628078962920429097010773719219281227340703928176601061418390449183543575468085737641002867191684818036182905347659400615796230893276884470919389823485665892343397687944728461714491295766674366
6

7
f = FactorDB(n)
8
f.connect()
9
p, q = f.get_factor_list()
10
assert p * q == n
11

12
phi = (p - 1) * (q - 1)
13
d = pow(e, -1, phi)
14
m = pow(c, d, n)
15
flag = m.to_bytes((m.bit_length() + 7) // 8, 'big').decode()
16
print(flag)

Flag#

1
VBD{ae746bf43346cc8cbc6d613d8e8da1f3}

Key Takeaways#

Always check factordb.com first for RSA challenges, it’s the quickest win
The factordb-pycli Python package automates the lookup: pip install factordb-pycli
Despite using 1024-bit primes (2048-bit n), if the primes are known/weak, RSA breaks trivially
No quantum computer needed, just a database lookup