Finding root of very large number

Question

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

@Swifty the token is a BIG number: OverflowError: int too large to convert to float — vaizki
– vaizki, Commented Dec 13, 2024 at 11:03
Ah. But then it would be possible to at least get the magnitude of token to reduce the search range. — Swifty
– Swifty, Commented Dec 13, 2024 at 13:10
Ok, I just tried approximating by decomposing the big number into products of 10 ** 100, and it gave me the token. I'll wrap this into a function. — Swifty
– Swifty, Commented Dec 13, 2024 at 13:22
This question is similar to: How to compute the nth root of a very big integer. If you believe it’s different, please edit the question, make it clear how it’s different and/or how the answers on that question are not helpful for your problem. — President James K. Polk
– President James K. Polk, Commented Dec 15, 2024 at 17:39

vaizki · Accepted Answer · 2024-12-13 11:02:49Z

3

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.

answered Dec 13, 2024 at 11:02

vaizki

2,0921 gold badge12 silver badges15 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Swifty Dec 13, 2024 at 13:31

Indeed, that's simpler and better than my decomposition :)

President James K. Polk Dec 14, 2024 at 15:24

Note that python's log function is more sophisticated than many other languages' log functions. Most log functions convert their integer arguments to a double and then use code optimized for IEEE 754 doubles. If the integer argument is too large to fit in a double, an error is returned. Python, however, treats integers differently and will return a log approximation no matter how large the integer is.

metallbrot Jan 6 at 11:28

this is some quake2 inverse root shit, thank you

Collectives™ on Stack Overflow

Finding root of very large number

1 Answer 1

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related