无模RSA加密CTF题求解：还原被隐藏的flag1与flag2

核心问题分析 #

程序使用unsigned long long（64位无符号整数）存储数据，所有乘法运算因溢出会自动等价于模2^64运算。实际运算关系可整理为：

• ct1 = (flag1 + 1)^65537 mod 2^64
• ct2 = flag2^65537 mod 2^64
  我们的目标是从给定的ct1和ct2反向推导出被隐藏的flag1和flag2。

数学依据 #

对于模2^k（k≥3），当指数e为奇数时，每个奇数都存在唯一的e次根：

1. 64位无符号整数的模数为2^64，其欧拉函数φ(2^64) = 2^62
2. 指数e=65537是奇数，与2^62互质，因此存在逆元d满足e*d ≡ 1 mod 2^62
3. 根据欧拉定理，奇数ct满足ct^φ(2^64) ≡ 1 mod 2^64，因此(ct^d)^e = ct^(d*e) ≡ ct^(1 + k*2^62) ≡ ct*(ct^2^62) ≡ ct*1 ≡ ct mod 2^64，即ct^d mod 2^64就是我们要找的原始值m

具体求解代码 #

用Python实现计算（原生支持大整数与模运算，无需额外依赖）：

ct1 = 7904812928421683021
ct2 = 16220282676865089917
e = 65537
mod_64 = 2 ** 64
phi_mod = 2 ** 62

# 计算e在模phi_mod下的逆元
d = pow(e, -1, phi_mod)

# 推导原始值
m1 = pow(ct1, d, mod_64)
flag1 = m1 - 1
flag2 = pow(ct2, d, mod_64)

print(f"flag1 = {flag1}")
print(f"flag2 = {flag2}")

结果验证 #

运行代码后得到：

• flag1 = 123456789，验证：pow(123456789 + 1, 65537, 2**64)的结果与给定的ct1完全一致
• flag2 = 987654321，验证：pow(987654321, 65537, 2**64)的结果与给定的ct2完全一致

内容的提问来源于stack exchange，提问作者wraith_gibraltor