RSA
Posted on Mon 05 August 2024 in ctf
This is a writeup of the crypto challenge RSA in the n00bz CTF 2024.
The attached file encryption.txt
had the following contents:
e = 3
n = 135112325288715136727832177735512070625083219670480717841817583343851445454356579794543601926517886432778754079508684454122465776544049537510760149616899986522216930847357907483054348419798542025184280105958211364798924985051999921354369017984140216806642244876998054533895072842602131552047667500910960834243
c = 13037717184940851534440408074902031173938827302834506159512256813794613267487160058287930781080450199371859916605839773796744179698270340378901298046506802163106509143441799583051647999737073025726173300915916758770511497524353491642840238968166849681827669150543335788616727518429916536945395813
With the small exponent e
the message is vulnerable to Coppersmith's attack.
The following python script exploits this:
import gmpy2
# Given parameters
e = 3
n = 135112325288715136727832177735512070625083219670480717841817583343851445454356579794543601926517886432778754079508684454122465776544049537510760149616899986522216930847357907483054348419798542025184280105958211364798924985051999921354369017984140216806642244876998054533895072842602131552047667500910960834243
c = 13037717184940851534440408074902031173938827302834506159512256813794613267487160058287930781080450199371859916605839773796744179698270340378901298046506802163106509143441799583051647999737073025726173300915916758770511497524353491642840238968166849681827669150543335788616727518429916536945395813
# Calculate the cube root of the ciphertext
m, exact = gmpy2.iroot(c, e)
if exact:
# Convert the integer to bytes
message_bytes = m.to_bytes((m.bit_length() + 7) // 8, byteorder='big')
try:
# Decode the bytes to an ASCII string
message = message_bytes.decode('ascii')
print(f"The plaintext message is: {message}")
except (UnicodeDecodeError, ValueError):
print("The decoded message is not valid ASCII. The extracted integer may not represent a valid ASCII string.")
else:
print("The cube root is not exact, check the values or consider other decryption methods.")
Executing the script returns the flag: n00bz{crypt0_1s_1nc0mpl3t3_w1th0ut_rs4!!}