[SOLVED] Finding root of very large number

Finding root of very large number

I'm doing a CTF of my IT-Security course right now, and have to find a token for a Kerberos registration service. The server uses a faulty RSA-like encryption. (yes, this on purpose and not changeable). Is there a way for me to retrieve the token without brute-forcing it? I have a lot of code afterwards which will need thorough testing but it takes 10-15 minutes every time I test it because I have to brute-force a token first.

Server:


        if option == "get_token":
            e = 0x10001
            self.token = secrets.randbits(16)
            # I heard with RSA you need some kind of private key to reverse this.
            # Although I didn't read the article very thoroughly.
            token_enc = pow(self.token, e)

            return { "token": hex(token_enc) }

My Code:

e = 0x10001
#guess token
enc_token = int(get_token()["token"], 16)
for token in range(2 ** 16):
    print(token)
    if pow(token, e) == enc_token:
        print("SOLVED! " + str(token))
        right_token = token
        break

Solution

You can "reverse" the exponential with exp + log to get very close:

from math import exp, log
import secrets

e = 0x10001
token = secrets.randbits(16)
print("Token:", token)
 
token_enc = pow(token, e)

token2 = exp(log(token_enc)/e)
print("Recovered token:", token2)

Test run gives:

Token: 23573
Recovered token: 23573.000000000025

Now you just have 2 tokens to test for.