We start by downloading the source files.
We are give a
from secret import FLAG
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
class RSACipher:
def __init__(self, bits):
self.key = RSA.generate(bits)
self.cipher = PKCS1_OAEP.new(self.key)
def encrypt(self, m):
return self.cipher.encrypt(m)
def decrypt(self, c):
return self.cipher.decrypt(c)
cipher = RSACipher(1024)
enc_flag = cipher.encrypt(FLAG)
with open('output.txt', 'w') as f:
f.write(f'n = {cipher.key.n}\n')
f.write(f'ct = {enc_flag.hex()}\n')
f.write(f'p = {str(cipher.key.p)[::2]}\n')
f.write(f'q = {str(cipher.key.q)[1::2]}')
This looks like a simple RSA encryption script. To decrypt the message we need the key. To get the key we need
So our goal is to recover
We do that by bruteforcing intelligentely. We know that
This works for most of the digits, but sometimes there are multiple possibilities. In that case we just try all of them until they hit a dead end.
The folowing script will recover
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
class RSACipher:
def __init__(self, bits):
self.key = RSA.generate(bits)
self.cipher = PKCS1_OAEP.new(self.key)
def encrypt(self, m):
return self.cipher.encrypt(m)
def decrypt(self, c):
return self.cipher.decrypt(c)
class CloneCipher:
def __init__(self, key):
self.key = key
self.cipher = PKCS1_OAEP.new(self.key)
def decrypt(self, c):
return self.cipher.decrypt(c)
def calculate_p(n, p_str, q_str, step):
# check if we are done
if len(p_str) == step:
if int(p_str) * int(q_str) == n:
return int(p_str)
else:
return -1
i = len(p_str) - 1 - step
if step % 2 == 0:
# we know p_str[i] is correct
# we calulate q_str[i] by brute force
for j in range(10):
q_str = q_str[:i] + str(j) + q_str[i+1:]
calc_n = int(p_str) * int(q_str)
str_calc_n = str(calc_n)
# check if step last digit of n is the same as the last digit of calc_n
if str_calc_n[-step-1] == n_str[-step-1]:
correct_p = calculate_p(n, p_str, q_str, step+1)
if correct_p != -1:
return correct_p
else:
# we know q_str[i] is correct
# we calulate p_str[i] by brute force
for j in range(10):
p_str = p_str[:i] + str(j) + p_str[i+1:]
calc_n = int(p_str) * int(q_str)
str_calc_n = str(calc_n)
# check if step last digit of n is the same as the last digit of calc_n
if str_calc_n[-step-1] == n_str[-step-1]:
correct_p = calculate_p(n, p_str, q_str, step+1)
if correct_p != -1:
return correct_p
cipher = RSACipher(1024)
FLAG = b'flag{fake_flag}'
enc_flag = cipher.encrypt(FLAG)
# n = cipher.key.n
# ct = enc_flag.hex()
# partial_p = str(cipher.key.p)[::2]
# partial_q = str(cipher.key.q)[1::2]
n = 118641897764566817417551054135914458085151243893181692085585606712347004549784923154978949512746946759125187896834583143236980760760749398862405478042140850200893707709475167551056980474794729592748211827841494511437980466936302569013868048998752111754493558258605042130232239629213049847684412075111663446003
ct = "7f33a035c6390508cee1d0277f4712bf01a01a46677233f16387fae072d07bdee4f535b0bd66efa4f2475dc8515696cbc4bc2280c20c93726212695d770b0a8295e2bacbd6b59487b329cc36a5516567b948fed368bf02c50a39e6549312dc6badfef84d4e30494e9ef0a47bd97305639c875b16306fcd91146d3d126c1ea476"
partial_p = "151441473357136152985216980397525591305875094288738820699069271674022167902643"
partial_q = "15624342005774166525024608067426557093567392652723175301615422384508274269305"
flag = bytes.fromhex(ct)
# set e because it is always 65537
e = 65537
# calculate p and q digit by digit knowing n
n_str = str(n)
# recreate p by filling it with 0s and the digits from partial_p
p_str = ""
for i in range(len(partial_p)):
p_str += partial_p[i] + "0"
# remove last 0
p_str = p_str[:-1]
q_str = ""
for i in range(len(p_str)):
if i % 2 == 0:
q_str += "0"
else:
q_str += partial_q[i//2]
p = int(calculate_p(n, p_str, q_str, 0))
q = n // p
# calculate d
phi = (p-1)*(q-1)
d = pow(e, -1, phi)
# Construct the key
constructed_key = RSA.construct((n, e, d))
constructed_cypher = CloneCipher(constructed_key)
print(constructed_cypher.decrypt(flag).decode())
Running this script will give us the flag: