Lost Modulus

2 minutes to read

We are given a short Python code to encrypt the flag, and we are given the ciphertext in 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

Source code analysis

The challenge script is using $e = 3$, which is the exponent used to encrypt the flag. This is how RSA cryptosystem works, where $m$ is the plain text, $c$ is the ciphertext and $n$ is the public modulus:

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

Solution

This time we don’t have $n$ (the challenge is called “Lost Modulus”). But since $e = 3$, it is so short that it can be vulnerable to a Cube Root Attack. In fact, if the message $m$ is short enough, then $m^3 = c < n$, so the modulus $n$ does not effect.

If this happens, we can obtain the plaintext using a simple cube root: $m = \sqrt[3]{c}$.

We can do it in SageMathCell or using Python and gmpy2:

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

We see that the cube root is exact because the output has a True at the end.

Flag

Now we can parse the number as bytes to get the flag:

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