Lost Modulus

2 minutos de lectura

Se nos proporciona un código en Python para cifrar la flag, y nos dan el texto cifrado en hexadecimal:

#!/usr/bin/python3
from Crypto.Util.number import getPrime, long_to_bytes, inverse  
flag = open('flag.txt', 'r').read().strip().encode()

class RSA:
    def __init__(self):
        self.p = getPrime(512)
        self.q = getPrime(512)
        self.e = 3
        self.n = self.p * self.q
        self.d = inverse(self.e, (self.p-1)*(self.q-1))
    def encrypt(self, data: bytes) -> bytes:
        pt = int(data.hex(), 16)
        ct = pow(pt, self.e, self.n)
        return long_to_bytes(ct)
    def decrypt(self, data: bytes) -> bytes:
        ct = int(data.hex(), 16)
        pt = pow(ct, self.d, self.n)
        return long_to_bytes(pt)

def main():
    crypto = RSA()
    print ('Flag:', crypto.encrypt(flag).hex())

if __name__ == '__main__':
    main()

Flag: 05c61636499a82088bf4388203a93e67bf046f8c49f62857681ec9aaaa40b4772933e0abc83e938c84ff8e67e5ad85bd6eca167585b0cc03eb1333b1b1462d9d7c25f44e53bcb568f0f05219c0147f7dc3cbad45dec2f34f03bcadcbba866dd0c566035c8122d68255ada7d18954ad604965

Análisis del código fuente

En el script del reto se utiliza $e = 3$, que es el exponente utilizado para cifrar la flag. Así es como funciona el criptosistema RSA, donde $m$ es el texto claro, $c$ es el texto cifrado y $n$ es el módulo público:

$$ c = m^e \mod{n} $$

Solución

Esta vez no tenemos $n$ (el reto se llama “Lost Modulus”). Pero como $e = 3$, es tan pequeño que puede ser vulnerable a un ataque de raíz cúbica. De hecho, si $m$ es suficientemente corto, entonces $m^3 = c < n$, por lo que el módulo $n$ no tiene efecto.

Si esto ocurre, podemos obtener el texto en claro con una simple raíz cúbica: $m = \sqrt[3]{c}$.

Se puede hacer en SageMathCell o con Python y gmpy2:

$ python3 -q
>>> import gmpy2
>>> c = int('05c61636499a82088bf4388203a93e67bf046f8c49f62857681ec9aaaa40b4772933e0abc83e938c84ff8e67e5ad85bd6eca167585b0cc03eb1333b1b1462d9d7c25f44e53bcb568f0f05219c0147f7dc3cbad45dec2f34f03bcadcbba866dd0c566035c8122d68255ada7d18954ad604965', 16)  
>>> gmpy2.iroot(c, 3)
(mpz(9208566198168854769137135900129825812636831889153009607082441577495048346488797274341323901), True)

Vemos que la raíz cúbica es exacta porque la salida muestra True al final.

Flag

Ahora podemos parsear el número como bytes y capturar la flag:

>>> bytes.fromhex(hex(9208566198168854769137135900129825812636831889153009607082441577495048346488797274341323901)[2:])  
b'HTB{n3v3r_us3_sm4ll_3xp0n3n7s_f0r_rs4}'