[ACTF新生赛2020]crypto-rsa3 题解（Fermat 分解实战）

题目来源：[ACTF新生赛2020]crypto-rsa3
标签：RSA、Fermat分解、p与q过近
难度：入门～中等

---

一、题目描述

题目给出两个文件：

• rsa3.py：加密脚本
• output.txt：输出内容

1. 加密脚本（rsa3.py）

from flag import FLAG
from Cryptodome.Util.number import *
import gmpy2
import random
e = 65537
p = getPrime(512)
q = int(gmpy2.next_prime(p))
n = p * q
m = bytes_to_long(FLAG)
c = pow(m, e, n)
print(n)
print(c)

关键点在：

q = int(gmpy2.next_prime(p))

gmpy2.next_prime(p) 会返回 大于 p 的下一个素数。
也就是说：

• p 是 512 位随机素数
• q 是紧挨着 p 的下一个素数
  这导致 p 和 q 非常接近，为 RSA 埋下了一个安全隐患。

2. 输出文件（output.txt）

内容大致为：

n = 177606504836499246970959030226871608885969321778211051080524634084516973331441644993898029573612290095853069264036530459253652875586267946877831055147546910227100566496658148381834683037366134553848011903251252726474047661274223137727688689535823533046778793131902143444408735610821167838717488859902242863683
c = 1457390378511382354771000540945361168984775052693073641682375071407490851289703070905749525830483035988737117653971428424612332020925926617395558868160380601912498299922825914229510166957910451841730028919883807634489834128830801407228447221775264711349928156290102782374379406719292116047581560530382210049

我们的任务：
根据 n, c, e 解密得到 flag，并按要求包裹成 flag{...} 提交。

二、漏洞分析：p 与 q 过近 → Fermat 分解

1. RSA 安全性对 p、q 的要求

RSA 的安全性依赖于大整数分解的困难性。
一般情况下，建议 p 和 q 长度相近，但数值不能“太接近”。
如果 p 和 q 非常接近，存在有效的攻击方法：Fermat 分解。
当：

• p 和 q 同为 512 位
• q 是 p 的下一个素数，即 |p - q| 很小
  那么 n = p * q 就可以被快速分解。

2. Fermat 分解原理

设：

• n = p * q
• p < q
  令：

a = (p + q) / 2
b = (q - p) / 2

则：

n = p * q
  = (a - b)(a + b)
  = a^2 - b^2

于是：

b^2 = a^2 - n

当 p ≈ q 时，b 会非常小，而 a 非常接近 √n。
因此可以从 a = ⌈√n⌉ 开始，逐个尝试 a，判断 a^2 - n 是否为完全平方数：

• 如果 a^2 - n 是完全平方数 b^2，则：
  • p = a - b
  • q = a + b
    这就是 Fermat 分解的核心思想。
    在本题中，q = next_prime(p)，所以 p 和 q 的差非常小，Fermat 分解几乎立刻成功。

---

三、解题思路总览

整体流程可以概括为：

下面我们一步步用代码实现。

四、具体解题过程

1. 环境准备

需要安装：

pip install gmpy2 pycryptodome

• gmpy2：大数运算、开方、判断平方数等
• pycryptodome：long_to_bytes 等工具函数

2. 读入题目参数

import gmpy2
from Crypto.Util.number import long_to_bytes
# 题目给出的 n 和 c
n = 177606504836499246970959030226871608885969321778211051080524634084516973331441644993898029573612290095853069264036530459253652875586267946877831055147546910227100566496658148381834683037366134553848011903251252726474047661274223137727688689535823533046778793131902143444408735610821167838717488859902242863683
c = 1457390378511382354771000540945361168984775052693073641682375071407490851289703070905749525830483035988737117653971428424612332020925926617395558868160380601912498299922825914229510166957910451841730028919883807634489834128830801407228447221775264711349928156290102782374379406719292116047581560530382210049
e = 65537

3. Fermat 分解求 p、q

核心代码：

print("[+] 开始 Fermat 分解 n...")
# 1. 计算 n 的整数平方根
a = gmpy2.iroot(n, 2)[0]  # 平方根，向下取整
# 如果 a^2 < n，则 a 至少要 +1
if a * a < n:
    a += 1
# 设置最大尝试次数，防止无限循环（理论上很快就能分解）
max_attempts = 1000000
found = False
for counter in range(max_attempts):
    # 计算 a^2 - n
    val = a * a - n
    # 判断 val 是否为完全平方数
    b, is_square = gmpy2.iroot(val, 2)
    if is_square:
        # 找到 p、q
        p = a - b
        q = a + b
        print(f"[+] 找到因子 p = {p}")
        print(f"[+] 找到因子 q = {q}")
        found = True
        break
    a += 1
if not found:
    print("[-] Fermat 分解失败，可能 p、q 差距较大或尝试次数不足")
    exit(1)

这里关键点：

• gmpy2.iroot(n, 2)：计算 n 的整数平方根，第二个参数 2 表示开平方。
• 判断 a^2 - n 是否为完全平方数：gmpy2.iroot(val, 2) 返回 (b, is_square)，若 is_square 为 True，则 val 是完全平方数。
  由于本题 p 和 q 非常接近，循环次数很少，基本瞬间就能分解成功。

4. 验证分解结果

# 验证 p * q == n
if p * q != n:
    print("[-] 分解结果不正确：p * q != n")
    exit(1)
print("[+] 验证通过：p * q == n")

5. 计算私钥 d

# 计算 phi(n)
phi_n = (p - 1) * (q - 1)
# 确保 e 和 phi(n) 互质
if gmpy2.gcd(e, phi_n) != 1:
    print("[-] e 和 phi(n) 不互质，无法计算私钥 d")
    exit(1)
# 求私钥 d：e * d ≡ 1 (mod phi(n))
d = gmpy2.invert(e, phi_n)
print(f"[+] 私钥 d = {d}")

6. 解密得到明文 m 并转 flag

# RSA 解密
m = pow(c, d, n)
# 将大整数转为字节串
flag_bytes = long_to_bytes(m)
flag = flag_bytes.decode()
print("\n[+] 解密得到的 flag:")
print(flag)
# 题目要求包上 flag{}
print("\n[+] 最终提交格式:")
print(f"flag{{{flag}}}")

---

五、完整解题脚本

把上面的片段合起来，就是一个完整脚本：

import gmpy2
from Crypto.Util.number import long_to_bytes
# 题目参数
n = 177606504836499246970959030226871608885969321778211051080524634084516973331441644993898029573612290095853069264036530459253652875586267946877831055147546910227100566496658148381834683037366134553848011903251252726474047661274223137727688689535823533046778793131902143444408735610821167838717488859902242863683
c = 1457390378511382354771000540945361168984775052693073641682375071407490851289703070905749525830483035988737117653971428424612332020925926617395558868160380601912498299922825914229510166957910451841730028919883807634489834128830801407228447221775264711349928156290102782374379406719292116047581560530382210049
e = 65537
print("[+] 开始 Fermat 分解 n...")
# Fermat 分解
a = gmpy2.iroot(n, 2)[0]
if a * a < n:
    a += 1
max_attempts = 1000000
found = False
for _ in range(max_attempts):
    val = a * a - n
    b, is_square = gmpy2.iroot(val, 2)
    if is_square:
        p = a - b
        q = a + b
        print(f"[+] p = {p}")
        print(f"[+] q = {q}")
        found = True
        break
    a += 1
if not found:
    print("[-] Fermat 分解失败")
    exit(1)
# 验证
if p * q != n:
    print("[-] p * q != n")
    exit(1)
# 计算 phi(n) 和 d
phi_n = (p - 1) * (q - 1)
if gmpy2.gcd(e, phi_n) != 1:
    print("[-] e 和 phi(n) 不互质")
    exit(1)
d = gmpy2.invert(e, phi_n)
# 解密
m = pow(c, d, n)
flag = long_to_bytes(m).decode()
print("\n[+] flag 内容:", flag)

运行结果：

[+] 开始 Fermat 分解 n...
[+] p = 13326909050357447643526585836833969378078147057723054701432842192988717649385731430095055622303549577233495793715580004801634268505725255565021519817179231
[+] q = 13326909050357447643526585836833969378078147057723054701432842192988717649385731430095055622303549577233495793715580004801634268505725255565021519817179293

[+] flag 内容: actf{p_and_q_should_not_be_so_close_in_value}

---

六、总结与安全启示

1. 题目考点
   • 理解 RSA 中 p、q 的选择对安全性的影响
   • 当 p 与 q 过于接近时，Fermat 分解可以快速恢复私钥
2. 攻击条件
   • p 和 q 长度相同，但数值非常接近（如本题 q = next_prime(p)）
   • 攻击复杂度主要取决于 |p - q| 的大小，|p - q| 越小，分解越快
3. 安全实践
   • 不要使用形如 q = next_prime(p) 的生成方式
   • 一般建议 p 和 q 长度相近，但数值差异足够大，避免 Fermat 攻击
   • 实际工程中应使用成熟库（如 OpenSSL、 cryptography 等）生成 RSA 参数
4. CTF 提示
   • 看到 q = next_prime(p) 或类似提示“p、q 很接近”，优先考虑 Fermat 分解或 yafu 工具分解 n
   • 解密后注意 flag 的编码格式，常见有 ACTF{...}、flag{...}，题目一般会说明包裹方式

---