#!/usr/bin/env python3
from Crypto.Util.number import long_to_bytes,bytes_to_long
import gmpy2
from pwn import success
e = 3
# The hexed Value of the flag
flag = '05c61636499a82088bf4388203a93e67bf046f8c49f62857681ec9aaaa40b4772933e0abc83e938c84ff8e67e5ad85bd6eca167585b0cc03eb1333b1b1462d9d7c25f44e53bcb568f0f05219c0147f7dc3cbad45dec2f34f03bcadcbba866dd0c566035c8122d68255ada7d18954ad604965'
# Getting the bytes value from the above hexed value
bstring = bytes.fromhex(flag)
# Converting Bytes to decimal so we can do RSA Operations on it
final = bytes_to_long(bstring)
'''
Now we only know e which is 3 so it will be small in comparision to n, so how RSA Encrypt the message is it takes the message convert it into bytes, and then convert it into the long format using bytes_to_long and encrypt it.
Encrypt using formula -> (pt ^ e) % n or pow(pt,e,n)
So if (pt ^ e) < n then it is a problem as the modulo will be the same number as (pt ^ e) so we can just take the cuberoot of the number and we can get the flag.
'''
gmpy2.get_context().precision=4096 # so we don't loose precision and cuberoot doesn't come in e format
pt = gmpy2.root(final,e)
success('Plain Text -> ' + long_to_bytes(pt).decode())
'''
kali@kali:~/HTB/challenges/Crypto/LostModulus$ python3 howto.txt
[*] Checking for new versions of pwntools
To disable this functionality, set the contents of /home/kali/.cache/.pwntools-cache-3.9/update to 'never' (old way).
Or add the following lines to ~/.pwn.conf or ~/.config/pwn.conf (or /etc/pwn.conf system-wide):
[update]
interval=never
[*] You have the latest version of Pwntools (4.5.1)
[+] Plain Text -> HTB{n3v3r_us3_sm4ll_3xp0n3n7s_f0r_rs4}
kali@kali:~/HTB/challenges/Crypto/LostModulus$
'''