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 = 118641897764566817417551054135914458085151243893181692085585606712347004549784923154978949512746946759125187896834583143236980760760749398862405478042140850200893707709475167551056980474794729592748211827841494511437980466936302569013868048998752111754493558258605042130232239629213049847684412075111663446003
ct = 7f33a035c6390508cee1d0277f4712bf01a01a46677233f16387fae072d07bdee4f535b0bd66efa4f2475dc8515696cbc4bc2280c20c93726212695d770b0a8295e2bacbd6b59487b329cc36a5516567b948fed368bf02c50a39e6549312dc6badfef84d4e30494e9ef0a47bd97305639c875b16306fcd91146d3d126c1ea476
p = 151441473357136152985216980397525591305875094288738820699069271674022167902643
q = 15624342005774166525024608067426557093567392652723175301615422384508274269305
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 $p$ y $q$):
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:
$$ p = \sum_{i = 0}^{D / 2} {d_p}_i \cdot 10^{2i} \quad + \quad \sum_{i = 0}^{D / 2} {x_p}_i \cdot 10^{2i + 1} $$
$$ q = \sum_{i = 0}^{D / 2} {d_q}_i \cdot 10^{2i + 1} \quad + \quad \sum_{i = 0}^{D / 2} {x_q}_i \cdot 10^{2i} $$
Donde $D$ es el número de dígitos; $d_p$ y $d_q$ son los dígitos conocidos de $p$ y $q$; y $x_p$ y $x_q$ son los dígitos desconocidos de $p$ y $q$.
Solución
Ya que sabemos que $n = p \cdot q$, por lo que la siguiente condición se cumple:
$$ \begin{align} n & = p \cdot q \\ & = \left(\sum_{i = 0}^{D / 2} {d_p}_i \cdot 10^{2i} + \sum_{i = 0}^{D / 2} {x_p}_i \cdot 10^{2i + 1}\right) \cdot \left(\sum_{i = 0}^{D / 2} {d_q}_i \cdot 10^{2i + 1} + \sum_{i = 0}^{D / 2} {x_q}_i \cdot 10^{2i}\right) \end{align} $$
Como resultado, podemos usar potencias y módulo $10$ para extraer cada dígito desconocido, porque:
$$ \begin{align} n \mod{10} & = p \cdot q \mod{10} \\ & = {d_p}_0 \cdot {x_q}_0 \mod{10} \end{align} $$
Una vez que encontramos ${x_q}_0$, podemos aumentar a potencia de $10$ y encontrar ${x_p}_0$:
$$ \begin{align} n \mod{10^2} & = p \cdot q \mod{10^2} \\ & = \left({x_p}_0 \cdot 10 + {d_p}_0 \right) \cdot \left({d_q}_0 \cdot 10 + {x_p}_0 \right) \mod{10^2} \end{align} $$
Luego ${x_q}_1$:
$$ \begin{align} n \mod{10^3} & = p \cdot q \mod{10^3} \\ & = \left({d_p}_1 \cdot 10^2 + {x_p}_0 \cdot 10 + {d_p}_0 \right) \cdot \\ & \qquad \qquad \cdot \left({x_q}_1 \cdot 10^2 + {d_q}_0 \cdot 10 + {x_p}_0 \right) \mod{10^3} \end{align} $$
Y así sucesivamente hasta que tengamos todos los dígitos de $p$ y $q$.
Implementación
La implementación es bastante simple, utilizando un bucle y una prueba para ver si la condición coincide para $p$ o para $q$:
#!/usr/bin/env python3
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
n = 118641897764566817417551054135914458085151243893181692085585606712347004549784923154978949512746946759125187896834583143236980760760749398862405478042140850200893707709475167551056980474794729592748211827841494511437980466936302569013868048998752111754493558258605042130232239629213049847684412075111663446003
ct = bytes.fromhex('7f33a035c6390508cee1d0277f4712bf01a01a46677233f16387fae072d07bdee4f535b0bd66efa4f2475dc8515696cbc4bc2280c20c93726212695d770b0a8295e2bacbd6b59487b329cc36a5516567b948fed368bf02c50a39e6549312dc6badfef84d4e30494e9ef0a47bd97305639c875b16306fcd91146d3d126c1ea476')
p = 151441473357136152985216980397525591305875094288738820699069271674022167902643
q = 15624342005774166525024608067426557093567392652723175301615422384508274269305
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 $0$, de manera que, en cada iteración, cuando falla la condición, agregamos $10^i$ al valor de $p$ o de $q$.
Flag
Si ejecutamos el script anterior, obtendremos la flag:
$ python3 solve.py
HTB{v3r1fy1ng_pr1m3s_m0dul0_p0w3rs_0f_10!}
El script completo se puede encontrar aquí: solve.py
.