LitCTF 2026 RSA 近邻素数 Fermat 分解题解

现代密码学 专栏：
https://blog.csdn.net/r_feynman_/category_13190241.html

Crypto 密码解析实战靶场：https://blog.csdn.net/r_feynman_/category_13194584.html

一、前置知识

1. RSA 的基本流程

RSA 首先选择两个大素数 $p$ 和 $q$，计算模数：

$$n=pq$$

然后计算欧拉函数：

$$\phi (n)=(p-1)(q-1)$$

选择公钥指数 $e$，并计算私钥指数 $d$，使它们满足：

$$ed\equiv 1(\mathrm{mod}\phi (n))$$

因此：

$$d=e^{-1}\mathrm{mod}\phi (n)$$

RSA 加密和解密分别为：

$$c\equiv m^e(\mathrm{mod}n)$$

$$m\equiv c^d(\mathrm{mod}n)$$

其中 $m$ 是明文整数，$c$ 是密文整数。

如果攻击者能够分解 $n$ 得到 $p,q$，就可以计算 $\phi (n)$，进一步得到 $d$，最后解密密文。因此 RSA 的核心安全性就在于：当 $p,q$ 足够大且随机时，攻击者难以分解 $n$。

---

2. 模逆

符号 $e^{-1}\mathrm{mod}\phi (n)$ 表示 $e$ 在模 $\phi (n)$ 下的乘法逆元。也就是说，要找一个 $d$，满足：

$$e\times d\equiv 1(\mathrm{mod}\phi (n))$$

Python 中可以使用：

d = pow(e, -1, phi)

这行代码就是在计算上面的模逆。

---

3. Fermat 分解的基本思想

如果两个因子 $p,q$ 很接近，就可以把乘积写成平方差。

令：

$$a=\frac{p+q}{2}$$

$$b=\frac{q-p}{2}$$

那么：

$$p=a-b$$

$$q=a+b$$

所以：

$$n=pq=(a-b)(a+b)=a^2-b^2$$

移项后得到：

$$b^2=a^2-n$$

因此，只要找到一个整数 $a$，使得 $a^2-n$ 是完全平方数，就能得到 $b$，然后恢复：

$$p=a-b$$

$$q=a+b$$

为什么从 $\lceil \sqrt{n}\rceil$ 开始？因为：

$$a^2=n+b^2\ge n$$

所以真实的 $a$ 一定满足：

$$a\ge \lceil \sqrt{n}\rceil$$

Fermat 算法就从 $\lceil \sqrt{n}\rceil$ 开始逐个尝试 $a$，直到 $a^2-n$ 成为完全平方数。

---

4. 整数和字节串的转换

题目加密前使用：

m = bytes_to_long(FLAG)

这一步把字节串 Flag 转换为整数。解密得到整数 $m$ 后，需要执行逆操作：

flag = long_to_bytes(m)

这样才能恢复出原始字节串。

---

二、题目分析：为什么可以使用 Fermat

题目生成 RSA 素数的代码是：

p = getPrime(512)
q = p
for _ in range(NEXT_PRIME_STEPS):
    q = int(gmpy2.next_prime(q))

正常的 RSA 应该独立生成两个素数：

p = getPrime(512)
q = getPrime(512)

但题目中 q 是从 p 开始不断调用 next_prime 得到的。也就是说，$q$ 并不是一个与 $p$ 独立的随机素数，而是位于 $p$ 附近的下一个素数。

因此 $p,q$ 之间的差值很小。实际分解后得到：

$$q-p=1135234$$

对于 512 位素数而言，$1135234$ 非常小，所以 $p,q$ 足够接近，适合使用 Fermat 分解。

题目给出的参数为：

n = 139637440016232025690294457609899605991056011052010466558411851317943636600860419882966079629826706361935550982744312593243181819999590825159611186779613601241742349986440676188542381451066058816661317621009248513651083772907520139375108426466691332559612971244160246310746215067136490772061317571744230078911

c = 81172369642931859390486697024961350889751244109623802937988620847486863147682579984823958801948701482096140632580173113959531836503723522945335985723867818778699337807630592078265626995722998378992215523352858561923474395550395284015986525513984910021995657780411466237306614109262460764382539311725297619429

e = 65537

接下来按照 Fermat 的数学推导编写代码。

---

三、Fermat 分解代码与公式对应关系

1. 导入库并设置参数

from math import isqrt
from Crypto.Util.number import long_to_bytes

n = 139637440016232025690294457609899605991056011052010466558411851317943636600860419882966079629826706361935550982744312593243181819999590825159611186779613601241742349986440676188542381451066058816661317621009248513651083772907520139375108426466691332559612971244160246310746215067136490772061317571744230078911

c = 81172369642931859390486697024961350889751244109623802937988620847486863147682579984823958801948701482096140632580173113959531836503723522945335985723867818778699337807630592078265626995722998378992215523352858561923474395550395284015986525513984910021995657780411466237306614109262460764382539311725297619429

e = 65537

这里的变量与 RSA 公式一一对应：

• n 对应 $n=pq$；
• c 对应 $c\equiv m^e(\mathrm{mod}n)$；
• e 是公钥指数 $e$；
• isqrt 用于计算整数平方根。

---

2. 设置 $a$ 的初始值

根据前置知识，Fermat 中的 $a$ 要从 $\lceil \sqrt{n}\rceil$ 开始。

代码为：

a = isqrt(n)
if a * a < n:
    a += 1

isqrt(n) 返回的是 $\lfloor \sqrt{n}\rfloor$。如果 a * a < n，说明当前结果还没有达到向上取整的平方根，需要执行 a += 1。

所以这段代码执行结束后，满足：

$$a=\lceil \sqrt{n}\rceil$$

---

3. 搜索完全平方数

Fermat 的核心公式是：

$$b^2=a^2-n$$

对应代码为：

while True:
    b2 = a * a - n
    b = isqrt(b2)

    if b * b == b2:
        p = a - b
        q = a + b
        break

    a += 1

其中：

b2 = a * a - n

对应：

$$b^2=a^2-n$$

变量 b2 只是暂时保存候选的 $b^2$。

然后：

b = isqrt(b2)

计算候选的 $b=\lfloor \sqrt{b^2}\rfloor$。

不能仅仅因为 b2 大于零就认为找到了结果，因为大多数尝试中的 $a^2-n$ 都是正数。真正的判断条件是：

if b * b == b2:

也就是验证：

$$b^2=a^2-n$$

如果成立，说明 b2 是完全平方数，当前 $a,b$ 就是正确解。

接下来：

p = a - b
q = a + b

对应公式：

$$p=a-b$$

$$q=a+b$$

如果没有找到完全平方数，则执行：

a += 1

继续尝试下一个 $a$。

本题第一次循环就成功，得到：

p = 11816828678466656423081159330348408729653180163168648515169882895485696059054463515539073361184747740171805314224608981224166619296322583683400493772811143

q = 11816828678466656423081159330348408729653180163168648515169882895485696059054463515539073361184747740171805314224608981224166619296322583683400493773946377

验证：

assert p * q == n
print(q - p)

输出：

1135234

由此确认 Fermat 分解正确。

本次计算中：

$$a=11816828678466656423081159330348408729653180163168648515169882895485696059054463515539073361184747740171805314224608981224166619296322583683400493773378760$$

$$b=567617$$

并且：

$$a^2-n=567617^2$$

---

四、计算私钥并解密

1. 计算 $\phi (n)$

恢复 $p,q$ 后，计算欧拉函数：

$$\phi (n)=(p-1)(q-1)$$

代码为：

phi = (p - 1) * (q - 1)

也可以使用等价公式：

$$\phi (n)=n-p-q+1$$

---

2. 计算私钥指数 $d$

RSA 私钥满足：

$$ed\equiv 1(\mathrm{mod}\phi (n))$$

所以：

$$d=e^{-1}\mathrm{mod}\phi (n)$$

对应代码为：

d = pow(e, -1, phi)

这里 pow(e, -1, phi) 正是在求模逆，也就是求满足：

$$e\times d\equiv 1(\mathrm{mod}\phi (n))$$

的 $d$。

---

3. 解密密文

RSA 解密公式为：

$$m\equiv c^d(\mathrm{mod}n)$$

代码为：

m = pow(c, d, n)

pow(c, d, n) 高效计算 $c^d\mathrm{mod}n$，得到明文整数 $m$。

题目加密前执行了：

m = bytes_to_long(FLAG)

所以需要使用 long_to_bytes 将整数还原成字节串：

flag = long_to_bytes(m)
print(flag.decode())

---

五、完整解题脚本

from math import isqrt
from Crypto.Util.number import long_to_bytes

n = 139637440016232025690294457609899605991056011052010466558411851317943636600860419882966079629826706361935550982744312593243181819999590825159611186779613601241742349986440676188542381451066058816661317621009248513651083772907520139375108426466691332559612971244160246310746215067136490772061317571744230078911

c = 81172369642931859390486697024961350889751244109623802937988620847486863147682579984823958801948701482096140632580173113959531836503723522945335985723867818778699337807630592078265626995722998378992215523352858561923474395550395284015986525513984910021995657780411466237306614109262460764382539311725297619429

e = 65537

# Fermat 分解：n = a^2 - b^2
# 从 a = ceil(sqrt(n)) 开始

a = isqrt(n)
if a * a < n:
    a += 1

while True:
    # 对应公式：b^2 = a^2 - n
    b2 = a * a - n
    b = isqrt(b2)

    # 判断 b2 是否为完全平方数
    if b * b == b2:
        # 对应公式：p = a - b，q = a + b
        p = a - b
        q = a + b
        break

    a += 1

# 对应公式：phi(n) = (p - 1)(q - 1)
phi = (p - 1) * (q - 1)

# 对应公式：d = e^(-1) mod phi(n)
d = pow(e, -1, phi)

# 对应公式：m = c^d mod n
m = pow(c, d, n)

# bytes_to_long 的逆操作
flag = long_to_bytes(m)
print(flag.decode())

运行结果：

litctf{rsa_fermat_finds_close_primes}

---

六、总结

这道题的攻击链很清晰：

1. 源码中 q 从 p 连续调用 next_prime 得到，导致 $p,q$ 过于接近；
2. 对近邻素数使用 Fermat 分解：

$$n=a^2-b^2$$

3. 从 $a=\lceil \sqrt{n}\rceil$ 开始搜索，使 $a^2-n$ 成为完全平方数；
4. 根据：

$$p=a-b,q=a+b$$

恢复 $p,q$；
5. 根据：

$$\phi (n)=(p-1)(q-1)$$

计算欧拉函数；
6. 根据：

$$d=e^{-1}\mathrm{mod}\phi (n)$$

计算私钥；
7. 根据：

$$m=c^d\mathrm{mod}n$$

完成解密。

最终 Flag：

litctf{rsa_fermat_finds_close_primes}