本文介绍一种基于对数运算的数学优化方法，无需暴力穷举即可在毫秒级时间内精准恢复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¹⁶) 区间内是严格单调递增的整数函数，而 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”本质上已丧失所有安全保证。
