前言
Bugku CTF 是国内知名的网络安全竞赛训练平台，涵盖了 Web、Crypto、Misc、Reverse、Pwn 等多个方向的题目。“MaybeEasyRSA” 是一道 Crypto 类的题目，分值 15 分，从题目名就能猜到和 RSA 加密有关——但加了个 “Maybe”，似乎在暗示它并不是那么 “Easy”。
RSA 是现代密码学的基石之一，其安全性建立在大整数分解的困难性之上。而 RSA 加解密的核心数学工具正是欧拉定理：若 p 和 q 是两个大素数，则欧拉函数 φ(n) = (p-1)(q-1)，私钥 d 满足 ed ≡ 1 (mod φ(n))。本题正是围绕欧拉定理展开，但由于 p 和 q 并非随机素数，而是由一个共同的 r 衍生而来，使得直接分解 n 成为可能。
题目描述
题目给出了三个关键数值：模数 n、公钥指数 e 和密文 c。在本题中，p 和 q 的生成方式并非标准的随机大素数，而是由一个共同的整数 r 通过多项式构造，再取 nextprime 得到：
p1=r**5+r**4-r**3+r**2-r+2024
p=nextprime(p1)
q1=r**5-r**4+r**3-r**2+r+2024
q=nextprime(q1)
n=p*q
本题示例数据如下：
- n= 8831809262643652126805179955933995088022863336420177785582181882096928010834594263850405726350879463
- e= 65537
- c= 4187685979531305196335859680920102897998391621267133257213664500289506210489114078388515813179920201
n 的量级约为 333 bit，属于可分解范围。但真正的考点不在于直接分解 n，而在于发现 p 和 q 的结构规律。
解题思路
①观察：p和q由同一个r衍生
注意到 p1 和 q1 的表达式中，最高次项都是 r^5，而且 q1 的构造与 p1 高度对称（各项符号交替反转）。因为 p = nextprime(p1) ≈ p1、q = nextprime(q1) ≈ q1，所以：
n = p × q ≈ p1 × q1 ≈ r^5 × r^5 = r^10
这意味着，如果我们能求出 r，就能重建 p 和 q，进而利用欧拉定理完成解密。问题的本质从”分解 n”转化为”求 r”。
②对n开10次方得到r近似值
既然 n ≈ r^10，我们对 n 开 10 次方就能得到 r 的近似值。使用 Python 的 gmpy2 库：
r_approx=int(gmpy2.iroot(n,10)[0])
由于 p 和 q 是 nextprime 的结果（比 p1 和 q1 略大），n 会略大于 r^10，所以开方得到的 r_approx 会非常接近真实的 r，通常偏差在个位数到几十之间。
③在近似值附近搜索精确r
在 r_approx 的邻域内搜索。对每个候选 r_test，计算 p_test = nextprime(r_test^5 + r_test^4 - r_test^3 + r_test^2 - r_test + 2024)，然后用 n % p_test == 0 验证：
foroffsetinrange(-2000,2001):
r_test=r_approx+offset
ifr_test<=0:
continue
p_test=get_p(r_test)
ifn%p_test==0:
found_r=r_test
break
一旦找到满足条件的 r，就说明 p 和 q 对应的原始 r 值被精确定位。
④用r重建p和q
找到精确 r 后，重新计算 p 和 q：
p=get_p(found_r)
q=get_q(found_r)
assertp*q==n# 验证正确性
⑤利用欧拉定理计算φ(n)和私钥d
欧拉定理指出：若 a 与 n 互素，则 a^φ(n) ≡ 1 (mod n)。在 RSA 中，由于 n = p × q（p、q 为素数），欧拉函数为：
φ(n) = (p-1)(q-1)
私钥 d 是 e 关于模 φ(n) 的乘法逆元：
ed ≡ 1 (mod φ(n))→d = e^(-1) mod φ(n)
phi_n=(p-1)*(q-1)
d=int(gmpy2.invert(e, phi_n))
⑥解密得到flag
用私钥 d 解密密文 c：
m = c^d mod n
再将大整数 m 转换为字节串：
m=pow(c, d, n)
flag=long_to_bytes(m)
解题代码
"""
Bugku CTF - MaybeEasyRSA 完整解题脚本
题目链接: https://ctf.bugku.com/challenges/detail/id/2413.html
核心思路:
1. p 和 q 由同一个 r 衍生: p1 = r^5+r^4-r^3+r^2-r+2024, p = nextprime(p1)
q 类似对称构造: q1 = r^5-r^4+r^3-r^2+r+2024, q = nextprime(q1)
2. n = p*q ≈ r^10, 对 n 开 10 次方得到 r 的近似值
3. 在近似值附近搜索精确的 r
4. 用 r 重建 p 和 q
5. 利用欧拉定理 φ(n) = (p-1)(q-1), 计算私钥 d
6. 解密得到 flag
"""
importgmpy2
fromCrypto.Util.numberimportlong_to_bytes
# ==================== 题目给定数据 ====================
n=8831809262643652126805179955933995088022863336420177785582181882096928010834594263850405726350879463
e=65537
c=4187685979531305196335859680920102897998391621267133257213664500289506210489114078388515813179920201
print("="*60)
print("Bugku CTF - MaybeEasyRSA 解题")
print("="*60)
# ==================== 步骤 1: 对 n 开 10 次方求 r 近似值 ====================
# n = p * q ≈ r^10（因为 p ≈ r^5, q ≈ r^5）
r_approx, exact=gmpy2.iroot(n,10)
r_approx=int(r_approx)
print(f"\n[步骤1] 对 n 开 10 次方, 得到 r 的近似值:")
print(f" r_approx ={r_approx}")
print(f" n 的位数:{n.bit_length()}bit")
# ==================== 步骤 2: 在近似值附近搜索精确的 r ====================
defget_p(r):
"""根据 r 计算 p = nextprime(r^5 + r^4 - r^3 + r^2 - r + 2024)"""
p1=r**5+r**4-r**3+r**2-r+2024
returnint(gmpy2.next_prime(p1))
defget_q(r):
"""根据 r 计算 q = nextprime(r^5 - r^4 + r^3 - r^2 + r + 2024)"""
q1=r**5-r**4+r**3-r**2+r+2024
returnint(gmpy2.next_prime(q1))
print(f"\n[步骤2] 在 r_approx 附近搜索精确的 r 值:")
found_r=None
search_range=2000
foroffsetinrange(-search_range, search_range+1):
r_test=r_approx+offset
ifr_test<=0:
continue
p_test=get_p(r_test)
ifn%p_test==0:
found_r=r_test
print(f" 搜索偏移量:{offset}")
print(f" 找到精确 r ={found_r}")
break
# ==================== 步骤 3: 用 r 重建 p 和 q ====================
print(f"\n[步骤3] 用 r ={found_r}重建 p 和 q:")
p=get_p(found_r)
q=get_q(found_r)
print(f" p1 = r^5 + r^4 - r^3 + r^2 - r + 2024")
print(f" p = nextprime(p1) ={p}")
print(f" q1 = r^5 - r^4 + r^3 - r^2 + r + 2024")
print(f" q = nextprime(q1) ={q}")
print(f" 验证: p * q == n ?{p*q==n}")
# ==================== 步骤 4: 欧拉定理计算私钥 ====================
# φ(n) = (p-1)(q-1)
# ed ≡ 1 (mod φ(n)) → d = e^{-1} mod φ(n)
print(f"\n[步骤4] 利用欧拉定理 φ(n) = (p-1)(q-1) 计算私钥 d:")
phi_n=(p-1)*(q-1)
d=int(gmpy2.invert(e, phi_n))
print(f" φ(n) = (p-1)*(q-1)")
print(f" φ(n) 长度:{phi_n.bit_length()}bit")
print(f" d = e^(-1) mod φ(n)")
print(f" d ={d}")
# ==================== 步骤 5: RSA 解密 ====================
print(f"\n[步骤5] RSA 解密: m = c^d mod n")
m=pow(c, d, n)
print(f" m ={m}")
# ==================== 步骤 6: 提取 flag ====================
print(f"\n[步骤6] 将明文 m 转为 bytes 得到 flag:")
flag=long_to_bytes(m)
print(f" flag ={flag}")
print("\n"+"="*60)
print(f"Flag:{flag.decode()}")
print("="*60)
运行结果
运行上述脚本，输出如下：
============================================================
Bugku CTF - MaybeEasyRSA 解题
============================================================
[步骤1] 对 n 开 10 次方, 得到 r 的近似值:
r_approx = 9876543209
n 的位数: 333 bit
[步骤2] 在 r_approx 附近搜索精确的 r 值:
搜索偏移量: 1
找到精确 r = 9876543210
[步骤3] 用 r = 9876543210 重建 p 和 q:
p1 = r^5 + r^4 - r^3 + r^2 - r + 2024
p = nextprime(p1) = 93977706209675566343917358829623734754104399311937
q1 = r^5 - r^4 + r^3 - r^2 + r + 2024
q = nextprime(q1) = 93977706190645080840549611028204535368410720892199
验证: p * q == n ? True
[步骤4] 利用欧拉定理 φ(n) = (p-1)(q-1) 计算私钥 d:
φ(n) = (p-1)*(q-1)
φ(n) 长度: 333 bit
d = e^(-1) mod φ(n)
d = 1402049888895502643198210053275818009609684150206960559578351272797398901847333840056414949259867649
[步骤5] RSA 解密: m = c^d mod n
m = 679536347117606377819503896328595943735431971467909561366942342218457469
[步骤6] 将明文 m 转为 bytes 得到 flag:
flag = b'bugku{Maybe_Easy_RSA_0r_Not?!}'
============================================================
Flag: bugku{Maybe_Easy_RSA_0r_Not?!}
============================================================
可以清晰地看到：从 n 开 10 次方得到 r_approx = 9876543209，仅偏移 1 就找到了精确的 r = 9876543210；重建 p 和 q 后验证 p*q == n 为 True；通过欧拉定理计算私钥 d，解密得到 flag。
总结
本题虽是 15 分的 Crypto 入门题，但涉及多个经典考点：
考点 | 说明 |
RSA基础原理 | 加密 c = m^e mod n，解密 m = c^d mod n，公私钥关系 ed ≡ 1 mod φ(n) |
欧拉定理 | φ(n) = (p-1)(q-1) 是 RSA 安全性的数学基石，也是解密的核心 |
nextprime特性 | p ≈ p1、q ≈ q1，n ≈ r^10 的近似关系是本题突破口 |
开方近似 | 利用 n 的量级反推 r，从”分解 n”降维为”搜索 r” |
大整数与字节串转换 | 使用 long_to_bytes 将解密后的整数还原为可读 flag |
本题的核心启示是：RSA 的安全性不仅取决于密钥长度，更取决于素数的生成方式是否足够随机。一旦 p 和 q 的生成存在确定性结构（如本题由同一个 r 衍生），攻击者就能利用数学关系绕过分解难题。这也是为什么生产环境中必须使用密码学安全的随机数生成器（CSPRNG）来生成 RSA 素数对。
