前言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 得到p1r**5r**4-r**3r**2-r2024pnextprime(p1)q1r**5-r**4r**3-r**2r2024qnextprime(q1)np*q本题示例数据如下n 8831809262643652126805179955933995088022863336420177785582181882096928010834594263850405726350879463e 65537c 4187685979531305196335859680920102897998391621267133257213664500289506210489114078388515813179920201n 的量级约为 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_approxint(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_testr_approxoffsetifr_test0:continuep_testget_p(r_test)ifn%p_test0:found_rr_testbreak一旦找到满足条件的 r就说明 p 和 q 对应的原始 r 值被精确定位。④用r重建p和q找到精确 r 后重新计算 p 和 qpget_p(found_r)qget_q(found_r)assertp*qn# 验证正确性⑤利用欧拉定理计算φ(n)和私钥d欧拉定理指出若 a 与 n 互素则 a^φ(n) ≡ 1 (mod n)。在 RSA 中由于 n p × qp、q 为素数欧拉函数为φ(n) (p-1)(q-1)私钥 d 是 e 关于模 φ(n) 的乘法逆元ed ≡ 1 (mod φ(n))→d e^(-1) mod φ(n)phi_n(p-1)*(q-1)dint(gmpy2.invert(e, phi_n))⑥解密得到flag用私钥 d 解密密文 cm c^d mod n再将大整数 m 转换为字节串mpow(c, d, n)flaglong_to_bytes(m)解题代码Bugku CTF - MaybeEasyRSA 完整解题脚本题目链接: https://ctf.bugku.com/challenges/detail/id/2413.html核心思路:1. p 和 q 由同一个 r 衍生: p1 r^5r^4-r^3r^2-r2024, p nextprime(p1)q 类似对称构造: q1 r^5-r^4r^3-r^2r2024, q nextprime(q1)2. n p*q ≈ r^10, 对 n 开 10 次方得到 r 的近似值3. 在近似值附近搜索精确的 r4. 用 r 重建 p 和 q5. 利用欧拉定理 φ(n) (p-1)(q-1), 计算私钥 d6. 解密得到 flagimportgmpy2fromCrypto.Util.numberimportlong_to_bytes# 题目给定数据 n8831809262643652126805179955933995088022863336420177785582181882096928010834594263850405726350879463e65537c4187685979531305196335859680920102897998391621267133257213664500289506210489114078388515813179920201print(*60)print(Bugku CTF - MaybeEasyRSA 解题)print(*60)# 步骤 1: 对 n 开 10 次方求 r 近似值 # n p * q ≈ r^10因为 p ≈ r^5, q ≈ r^5r_approx, exactgmpy2.iroot(n,10)r_approxint(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)p1r**5r**4-r**3r**2-r2024returnint(gmpy2.next_prime(p1))defget_q(r):根据 r 计算 q nextprime(r^5 - r^4 r^3 - r^2 r 2024)q1r**5-r**4r**3-r**2r2024returnint(gmpy2.next_prime(q1))print(f\n[步骤2] 在 r_approx 附近搜索精确的 r 值:)found_rNonesearch_range2000foroffsetinrange(-search_range, search_range1):r_testr_approxoffsetifr_test0:continuep_testget_p(r_test)ifn%p_test0:found_rr_testprint(f 搜索偏移量:{offset})print(f 找到精确 r {found_r})break# 步骤 3: 用 r 重建 p 和 q print(f\n[步骤3] 用 r {found_r}重建 p 和 q:)pget_p(found_r)qget_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*qn})# 步骤 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)dint(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)mpow(c, d, n)print(f m {m})# 步骤 6: 提取 flag print(f\n[步骤6] 将明文 m 转为 bytes 得到 flag:)flaglong_to_bytes(m)print(f flag {flag})print(\n*60)print(fFlag:{flag.decode()})print(*60)运行结果运行上述脚本输出如下Bugku CTF - MaybeEasyRSA 解题[步骤1] 对 n 开 10 次方, 得到 r 的近似值:r_approx 9876543209n 的位数: 333 bit[步骤2] 在 r_approx 附近搜索精确的 r 值:搜索偏移量: 1找到精确 r 9876543210[步骤3] 用 r 9876543210 重建 p 和 q:p1 r^5 r^4 - r^3 r^2 - r 2024p nextprime(p1) 93977706209675566343917358829623734754104399311937q1 r^5 - r^4 r^3 - r^2 r 2024q nextprime(q1) 93977706190645080840549611028204535368410720892199验证: p * q n ? True[步骤4] 利用欧拉定理 φ(n) (p-1)(q-1) 计算私钥 d:φ(n) (p-1)*(q-1)φ(n) 长度: 333 bitd e^(-1) mod φ(n)d 1402049888895502643198210053275818009609684150206960559578351272797398901847333840056414949259867649[步骤5] RSA 解密: m c^d mod nm 679536347117606377819503896328595943735431971467909561366942342218457469[步骤6] 将明文 m 转为 bytes 得到 flag:flag bbugku{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 ≈ q1n ≈ r^10 的近似关系是本题突破口开方近似利用 n 的量级反推 r从”分解 n”降维为”搜索 r”大整数与字节串转换使用 long_to_bytes 将解密后的整数还原为可读 flag本题的核心启示是RSA 的安全性不仅取决于密钥长度更取决于素数的生成方式是否足够随机。一旦 p 和 q 的生成存在确定性结构如本题由同一个 r 衍生攻击者就能利用数学关系绕过分解难题。这也是为什么生产环境中必须使用密码学安全的随机数生成器CSPRNG来生成 RSA 素数对。
Bugku CTF Crypto - MaybeEasyRSA 题解（欧拉定理的应用）
前言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 得到p1r**5r**4-r**3r**2-r2024pnextprime(p1)q1r**5-r**4r**3-r**2r2024qnextprime(q1)np*q本题示例数据如下n 8831809262643652126805179955933995088022863336420177785582181882096928010834594263850405726350879463e 65537c 4187685979531305196335859680920102897998391621267133257213664500289506210489114078388515813179920201n 的量级约为 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_approxint(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_testr_approxoffsetifr_test0:continuep_testget_p(r_test)ifn%p_test0:found_rr_testbreak一旦找到满足条件的 r就说明 p 和 q 对应的原始 r 值被精确定位。④用r重建p和q找到精确 r 后重新计算 p 和 qpget_p(found_r)qget_q(found_r)assertp*qn# 验证正确性⑤利用欧拉定理计算φ(n)和私钥d欧拉定理指出若 a 与 n 互素则 a^φ(n) ≡ 1 (mod n)。在 RSA 中由于 n p × qp、q 为素数欧拉函数为φ(n) (p-1)(q-1)私钥 d 是 e 关于模 φ(n) 的乘法逆元ed ≡ 1 (mod φ(n))→d e^(-1) mod φ(n)phi_n(p-1)*(q-1)dint(gmpy2.invert(e, phi_n))⑥解密得到flag用私钥 d 解密密文 cm c^d mod n再将大整数 m 转换为字节串mpow(c, d, n)flaglong_to_bytes(m)解题代码Bugku CTF - MaybeEasyRSA 完整解题脚本题目链接: https://ctf.bugku.com/challenges/detail/id/2413.html核心思路:1. p 和 q 由同一个 r 衍生: p1 r^5r^4-r^3r^2-r2024, p nextprime(p1)q 类似对称构造: q1 r^5-r^4r^3-r^2r2024, q nextprime(q1)2. n p*q ≈ r^10, 对 n 开 10 次方得到 r 的近似值3. 在近似值附近搜索精确的 r4. 用 r 重建 p 和 q5. 利用欧拉定理 φ(n) (p-1)(q-1), 计算私钥 d6. 解密得到 flagimportgmpy2fromCrypto.Util.numberimportlong_to_bytes# 题目给定数据 n8831809262643652126805179955933995088022863336420177785582181882096928010834594263850405726350879463e65537c4187685979531305196335859680920102897998391621267133257213664500289506210489114078388515813179920201print(*60)print(Bugku CTF - MaybeEasyRSA 解题)print(*60)# 步骤 1: 对 n 开 10 次方求 r 近似值 # n p * q ≈ r^10因为 p ≈ r^5, q ≈ r^5r_approx, exactgmpy2.iroot(n,10)r_approxint(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)p1r**5r**4-r**3r**2-r2024returnint(gmpy2.next_prime(p1))defget_q(r):根据 r 计算 q nextprime(r^5 - r^4 r^3 - r^2 r 2024)q1r**5-r**4r**3-r**2r2024returnint(gmpy2.next_prime(q1))print(f\n[步骤2] 在 r_approx 附近搜索精确的 r 值:)found_rNonesearch_range2000foroffsetinrange(-search_range, search_range1):r_testr_approxoffsetifr_test0:continuep_testget_p(r_test)ifn%p_test0:found_rr_testprint(f 搜索偏移量:{offset})print(f 找到精确 r {found_r})break# 步骤 3: 用 r 重建 p 和 q print(f\n[步骤3] 用 r {found_r}重建 p 和 q:)pget_p(found_r)qget_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*qn})# 步骤 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)dint(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)mpow(c, d, n)print(f m {m})# 步骤 6: 提取 flag print(f\n[步骤6] 将明文 m 转为 bytes 得到 flag:)flaglong_to_bytes(m)print(f flag {flag})print(\n*60)print(fFlag:{flag.decode()})print(*60)运行结果运行上述脚本输出如下Bugku CTF - MaybeEasyRSA 解题[步骤1] 对 n 开 10 次方, 得到 r 的近似值:r_approx 9876543209n 的位数: 333 bit[步骤2] 在 r_approx 附近搜索精确的 r 值:搜索偏移量: 1找到精确 r 9876543210[步骤3] 用 r 9876543210 重建 p 和 q:p1 r^5 r^4 - r^3 r^2 - r 2024p nextprime(p1) 93977706209675566343917358829623734754104399311937q1 r^5 - r^4 r^3 - r^2 r 2024q nextprime(q1) 93977706190645080840549611028204535368410720892199验证: p * q n ? True[步骤4] 利用欧拉定理 φ(n) (p-1)(q-1) 计算私钥 d:φ(n) (p-1)*(q-1)φ(n) 长度: 333 bitd e^(-1) mod φ(n)d 1402049888895502643198210053275818009609684150206960559578351272797398901847333840056414949259867649[步骤5] RSA 解密: m c^d mod nm 679536347117606377819503896328595943735431971467909561366942342218457469[步骤6] 将明文 m 转为 bytes 得到 flag:flag bbugku{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 ≈ q1n ≈ r^10 的近似关系是本题突破口开方近似利用 n 的量级反推 r从”分解 n”降维为”搜索 r”大整数与字节串转换使用 long_to_bytes 将解密后的整数还原为可读 flag本题的核心启示是RSA 的安全性不仅取决于密钥长度更取决于素数的生成方式是否足够随机。一旦 p 和 q 的生成存在确定性结构如本题由同一个 r 衍生攻击者就能利用数学关系绕过分解难题。这也是为什么生产环境中必须使用密码学安全的随机数生成器CSPRNG来生成 RSA 素数对。
