针对非常大的数字反转 pow(int, int)

Question

我现在正在做 IT 安全课程的 CTF，并且必须找到 Kerberos 注册服务的令牌。服务器使用了错误的类似 RSA 的加密。 （是的，这是故意的，不可更改）。有没有办法让我在不暴力破解的情况下检索令牌？之后我有很多代码需要彻底测试，但每次测试都需要 10-15 分钟，因为我必须先暴力破解令牌。

服务器：

        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) }

我的代码：

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

Answer 1

您可以使用 exp + log “反转”指数以非常接近：

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)

测试运行给出：

Token: 23573
Recovered token: 23573.000000000025

现在您只有 2 个代币可供测试。