Partial Tenacity
3 minutos de lectura
Se nos proporciona el código fuente en Python que cifra la flag:
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]}')
También tenemos la salida del script:
n = 113885866414967666002972488658501581523252563769498903942813659534669192201155190251383326523008134606996199193472232684661637386940661594327513591391999626564784682500337524012474617483098011060289946582371155292302705685943021986766584545105444481270761266224342249010400461266963638157749562695294713843509
ct = 44a45518f4b49c2985a4e696d6fb48bc94e2e9e10b1b518786ab7205298d47250ae85ef69acd04f5daafdcdeda748eff1510ec8a42f1923dfd1bf893082eb7ebed7ca88441f92c1dac61ca5fdf0e9d968cf8213e2ca0a8e24dbfec2bbd58205c60abceb242025a1e8412a0a92a0ae7dd3d6bb0cde0bf28511376003ae907a52b
p = 169785301867063487293453013833911015973907683687605489113424565682424824172371
q = 02316166678868901218282182600315316354684047272123731927933503134218133661721
Análisis del código fuente
El servidor utiliza un cifrado estándar RSA-OAEP para cifrar la flag. La cuestión es que se nos da información sobre la clave privada (números primos
f.write(f'p = {str(cipher.key.p)[::2]}\n')
f.write(f'q = {str(cipher.key.q)[1::2]}')
El código anterior significa que tenemos algunos dígitos de ambos números primos representados como números decimales. Pero son alternados.
Podemos expresar lo anterior de la siguiente manera:
Donde
Solución
Ya que sabemos que
Como resultado, podemos usar potencias y módulo
Una vez que encontramos
Luego
Y así sucesivamente hasta que tengamos todos los dígitos de
Implementación
La implementación es bastante simple, utilizando un bucle y una prueba para ver si la condición coincide para
#!/usr/bin/env python3
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
n = 113885866414967666002972488658501581523252563769498903942813659534669192201155190251383326523008134606996199193472232684661637386940661594327513591391999626564784682500337524012474617483098011060289946582371155292302705685943021986766584545105444481270761266224342249010400461266963638157749562695294713843509
ct = bytes.fromhex('44a45518f4b49c2985a4e696d6fb48bc94e2e9e10b1b518786ab7205298d47250ae85ef69acd04f5daafdcdeda748eff1510ec8a42f1923dfd1bf893082eb7ebed7ca88441f92c1dac61ca5fdf0e9d968cf8213e2ca0a8e24dbfec2bbd58205c60abceb242025a1e8412a0a92a0ae7dd3d6bb0cde0bf28511376003ae907a52b')
p = '169785301867063487293453013833911015973907683687605489113424565682424824172371'
q = '02316166678868901218282182600315316354684047272123731927933503134218133661721'
p_digits = []
q_digits = []
for d in str(p):
p_digits.append(d)
p_digits.append('0')
p = int(''.join(p_digits[:-1]))
for d in str(q):
q_digits.append('0')
q_digits.append(d)
q_digits.append('0')
q = int(''.join(q_digits))
for i in range(len(q_digits)):
if i % 2 == 0:
while n % (10 ** (i + 1)) != (p * q) % (10 ** (i + 1)):
q += 10 ** i
else:
while n % (10 ** (i + 1)) != (p * q) % (10 ** (i + 1)):
p += 10 ** i
assert p * q == n
e = 65537
d = pow(e, -1, (p - 1) * (q - 1))
cipher = PKCS1_OAEP.new(RSA.construct((n, e, d)))
pt = cipher.decrypt(ct)
print(pt.decode())
Inicialmente establecemos los dígitos desconocidos en
Flag
Si ejecutamos el script anterior, obtendremos la flag:
$ python3 solve.py
HTB{RS4_w1th_p0w3rs_0f_10_4s_m0duli}
El script completo se puede encontrar aquí: solve.py
.