如何高效破解16位RSA-like密钥的加密令牌

本文介绍一种基于对数运算的数学优化方法，无需暴力穷举即可在毫秒级时间内精准恢复16位明文令牌，适用于CTF中e=0x10001且明文极小（仅2¹⁶种可能）的非标准RSA变体场景。

本文介绍一种基于对数运算的数学优化方法，无需暴力穷举即可在毫秒级时间内精准恢复16位明文令牌，适用于CTF中e=0x10001且明文极小（仅2¹⁶种可能）的非标准RSA变体场景。

从您给出的 CTF 服务代码来看，这里的加密虽然打着“RSA-like”的旗号，但实现上其实被极度简化了：明文 token 只是一个 16 位随机整数，也就是落在 [0, 2¹⁶) 这个范围内；公指数依然用了 e = 0x10001 = 65537。问题恰恰出在最关键的一步上——模运算（mod N）被彻底省略了。换句话说，所谓加密实际上只是在做单纯的幂运算：token_enc = token^e，而不是标准 RSA 中的 c ≡ m^e mod N。这个设计缺陷会直接改变题目的性质：原本应当落在离散对数或大整数分解这类困难问题上的安全性，最终退化成了一个可以直接求解实数根的普通计算问题。

由于 token 是正整数且远小于 e 次方根的精度误差范围，我们可利用自然对数与指数函数近似反解：

from math import exp, log

e = 0x10001
enc_token = int(get_token()["token"], 16)

# 计算 e 次方根的浮点近似值
approx_token = exp(log(enc_token) / e)
# 取整并检查邻近整数（因浮点误差，真实值必在 floor(approx) 或 ceil(approx) 中）
candidate_low = int(approx_token)
candidate_high = candidate_low + 1

for cand in [candidate_low, candidate_high]:
if cand = 2**16:
continue
if pow(cand, e) == enc_token:
print("Found token:", cand)
break

✅ 为什么只需验证最多2个候选值？
pow(token, e) 在 token ∈ [0, 2¹⁶) 这个区间里，是一个严格单调递增的整数函数。说得直白一点，token 只要变大，结果就一定跟着变大，不会出现“回头”或重复。再看 exp(log(x)/e)，它的浮点误差通常非常小，一般不到 1e-10，实测结果甚至像 23573.000000000025 这样，已经无限贴近真实整数。也正因为如此，真正的 token 只可能落在 floor(approx) 或 ceil(approx) 这两个值上，没必要把全部 65536 种可能逐个遍历一遍。

⚠️ 关键注意事项：

• 此方法仅适用于无模幂运算的非标准场景（如本题）；若存在模 N，则必须进行大数分解或离散对数攻击，此法失效。
• 确保 enc_token > 0（token=0 时 0^e=0，需单独处理）；
• 使用 int() 截断而非 round()，避免边界错误（例如 23572.99999999999 应取 23572 而非 23573）；
• 实际CTF中建议添加 cand 范围校验（0 ≤ cand ），防止因极端浮点异常导致越界。

通过该方法，您的测试流程将从10–15分钟的暴力循环缩短至毫秒级响应，大幅提升后续代码调试效率。记住：密码学的安全性高度依赖完整设计——缺失模运算的“RSA”本质上已丧失所有安全保证。