文章总结： 文章以CTF题为例，系统演示因密钥生成脚本用nextprime使p、q仅差1432，致2048位RSA可被费马分解法秒破；给出完整Python攻击链：分解N→算φ(N)→求d→模幂解密→转flag，并总结正确独立随机选素数、审计代码、用成熟库等安全要点。 综合评分： 92 文章分类： CTF,密码学,RSA,漏洞分析,实战经验
RSA弱密钥攻击实战：费马分解法完全解析
原创
破镜安全 破镜安全
破镜安全
2026年1月19日 08:00 四川
RSA弱密钥攻击实战：费马分解法完全解析
前言
RSA是目前应用最广泛的公钥加密算法之一，其安全性建立在大整数因数分解的困难性之上。然而，如果在密钥生成过程中出现失误，即使使用了足够长的密钥，RSA加密系统仍然可能被轻易攻破。本文将通过一道CTF密码学题目，深入剖析RSA弱密钥的产生原因、攻击原理以及完整的攻击实现过程。
一、题目环境搭建与初步分析
1.1 题目文件
本题提供了一个Python加密脚本 enc.py，让我们先来查看其完整内容：
from Crypto.Util.number import getPrime, isPrime, getRandomNBitInteger, bytes_to_long, long_to_bytes
from gmpy2 import powmod,invert,gcd
from flag import flag
import sympy
q = getPrime(1024)
p = sympy.nextprime(q)
N = p * q
e = 0x10001
flag = flag.ljust(80)
m = bytes_to_long(flag)
c = pow(m,e,N)
print('N = ',N)
print('e = ',e)
print('c = ',c)
1.2 题目给出的加密参数
运行加密脚本后，题目给出了以下三个参数：
N = 12194420073815392880989031611545296854145241675320130314821394843436947373331080911787176737202940676809674543138807024739454432089096794532016797246441325729856528664071322968428804098069997196490382286126389331179054971927655320978298979794245379000336635795490242027519669217784433367021578247340154647762800402140321022659272383087544476178802025951768015423972182045405466448431557625201012332239774962902750073900383993300146193300485117217319794356652729502100167668439007925004769118070105324664379141623816256895933959211381114172778535296409639317535751005960540737044457986793503218555306862743329296169569
e = 65537
c = 4504811333111877209539001665516391567038109992884271089537302226304395434343112574404626060854962818378560852067621253927330725244984869198505556722509058098660083054715146670767687120587049288861063202617507262871279819211231233198070574538845161629806932541832207041112786336441975087351873537350203469642198999219863581040927505152110051313011073115724502567261524181865883874517555848163026240201856207626237859665607255740790404039098444452158216907752375078054615802613066229766343714317550472079224694798552886759103668349270682843916307652213810947814618810706997339302734827571635179684652559512873381672063
其中：
- N 是RSA模数，由两个大素数 p 和 q 的乘积
- e 是公钥指数，值为 65537（0x10001）
- c 是加密后的密文
1.3 RSA加密算法基础回顾
在分析漏洞之前，我们需要先理解RSA加密的基本原理：
密钥生成过程：
- 选择两个大素数 p 和 q
- 计算模数 N = p × q
- 计算欧拉函数 φ(N) = (p-1) × (q-1)
- 选择公钥指数 e，满足 1 < e < φ(N) 且 gcd(e, φ(N)) = 1
- 计算私钥指数 d，满足 e × d ≡ 1 (mod φ(N))
加密过程：
- 明文 m 加密为密文 c：c = m^e mod N
解密过程：
- 密文 c 解密为明文 m：m = c^d mod N
RSA安全性的关键：
- 攻击者知道 N 和 e（公钥）
- 攻击者需要计算 d（私钥）才能解密
- 计算 d 需要知道 φ(N)
- 计算 φ(N) 需要知道 p 和 q
- 因此，RSA的安全性依赖于分解 N 的困难性
二、代码审计与漏洞发现
2.1 逐行分析加密代码
让我们仔细审计加密脚本的每一行代码：
q = getPrime(1024) # 生成一个1024位的随机素数q
p = sympy.nextprime(q) # 获取q的下一个素数作为p
N = p * q # 计算RSA模数
e = 0x10001 # 设置公钥指数为65537
前两行代码引起了我们的注意。正常的RSA密钥生成应该是：
# 正确的做法
p = getPrime(1024)
q = getPrime(1024)
但这里使用了 p = sympy.nextprime(q)，这意味着什么？
2.2 nextprime() 函数的含义
sympy.nextprime(q) 函数返回大于 q 的下一个素数。这意味着：
- p 是紧邻 q 的下一个素数
- p 和 q 在数值上非常接近
- p > q，且 p – q 的值很小
2.3 素数间隔的数学背景
根据素数定理，在大数 n 附近，相邻素数的平均间隔约为 ln(n)。
对于1024位的素数（约为 2^1024）：
- ln(2^1024) = 1024 × ln(2) ≈ 1024 × 0.693 ≈ 710
这意味着在1024位素数附近，相邻两个素数的平均间隔只有约710左右。
2.4 漏洞的危害性
当 p 和 q 过于接近时，会导致严重的安全问题：
- 违反RSA安全假设：RSA的安全性要求 p 和 q 应该是随机独立选择的大素数，且差值足够大
- 易受特定攻击：当 p 和 q 接近时，存在高效的分解算法可以快速分解 N
- 费马分解法适用：这正是费马分解法的最佳应用场景
结论：这是一个典型的RSA弱密钥漏洞。
三、费马分解法的数学原理
3.1 基本思想
费马分解法（Fermat’s Factorization Method）是一种专门针对两个因子接近的合数的分解算法。其核心思想是将合数表示为两个平方数的差。
3.2 数学推导
对于任意奇数 N = p × q（其中 p > q 且都是奇数），我们可以进行如下变换：
设：
a = (p + q) / 2
b = (p - q) / 2
则有：
p = a + b
q = a - b
将 p 和 q 代入 N = p × q：
N = (a + b)(a - b) = a² - b²
因此：
a² = N + b²
这就是费马分解法的数学基础。
3.3 算法步骤
基于上述数学推导，我们可以设计如下算法：
步骤1： 从 a = ⌈√N⌉ 开始（即 N 的平方根向上取整）
步骤2： 计算 b² = a² – N
步骤3： 检查 b² 是否为完全平方数
- 如果是，则 b = √(b²)，算法结束
- 如果不是，则 a = a + 1，返回步骤2
步骤4： 得到 a 和 b 后，计算：
- p = a + b
- q = a – b
步骤5： 验证 p × q = N
3.4 算法效率分析
费马分解法的效率完全取决于 p 和 q 的差值：
当 p 和 q 接近时：
- 设 p – q = 2k，则 b = k
- 从 a = ⌈√N⌉ 开始，只需迭代约 k 次
- 时间复杂度：O(k)
当 p 和 q 相差很大时：
- k 值很大，迭代次数急剧增加
- 算法效率大幅下降，甚至不如暴力分解
本题的情况：
- p = nextprime(q)，意味着 p – q 很小（约几百到几千）
- 因此 k 值很小，费马分解法可以在极短时间内完成
- 这正是费马分解法的最佳应用场景
四、费马分解法的Python实现
4.1 代码实现
基于前面的算法步骤，我们可以编写如下Python代码：
from math import isqrt
def fermat(n):
"""
费马分解法实现
参数: n - 待分解的合数
返回: (p, q) - n的两个因子
"""
# 步骤1: 从sqrt(n)向上取整开始
a = isqrt(n) + 1
b2 = a * a - n
# 步骤2-3: 不断增加a，直到b²是完全平方数
while b2 < 0 or isqrt(b2) ** 2 != b2:
a = a + 1
b2 = a * a - n
# 步骤4: 计算b，然后得到p和q
b = isqrt(b2)
p = a + b
q = a - b
# 步骤5: 验证结果
assert n == p * q
return p, q
4.2 代码详解
让我们逐行解析这段代码：
第1行：from math import isqrt
- 导入Python标准库中的整数平方根函数
isqrt(n)返回不大于 √n 的最大整数
第7-8行： 初始化
a = isqrt(n) + 1
b2 = a * a - n
- 从 √N 向上取整开始搜索
- 计算 b² = a² – N
第10-13行： 主循环
while b2 < 0 or isqrt(b2) ** 2 != b2:
a = a + 1
b2 = a * a - n
- 检查 b² 是否为完全平方数
isqrt(b2) ** 2 != b2判断 b² 是否为完全平方数- 如果不是，则 a 自增1，继续搜索
第15-18行： 计算结果
b = isqrt(b2)
p = a + b
q = a - b
- 找到满足条件的 a 和 b
- 根据公式计算 p 和 q
第20-22行： 验证
assert n == p * q
return p, q
- 验证分解结果的正确性
- 返回两个因子
4.3 实际运行分解N
现在让我们使用费马分解法来分解题目给出的 N：
N = 12194420073815392880989031611545296854145241675320130314821394843436947373331080911787176737202940676809674543138807024739454432089096794532016797246441325729856528664071322968428804098069997196490382286126389331179054971927655320978298979794245379000336635795490242027519669217784433367021578247340154647762800402140321022659272383087544476178802025951768015423972182045405466448431557625201012332239774962902750073900383993300146193300485117217319794356652729502100167668439007925004769118070105324664379141623816256895933959211381114172778535296409639317535751005960540737044457986793503218555306862743329296169569
p, q = fermat(N)
print(f"p = {p}")
print(f"q = {q}")
print(f"p - q = {p - q}")
运行结果：
p = 110428348144013242234907008083355974834266917027228724749730385104087025249352345946164980361082178532313669767485270254326404723948153912910688118140621712922649644396733499972695482991866293857864311557686710317462165131360819813493524457615383204504505224030129953230866877990529769205769592709254542472051
q = 110428348144013242234907008083355974834266917027228724749730385104087025249352345946164980361082178532313669767485270254326404723948153912910688118140621712922649644396733499972695482991866293857864311557686710317462165131360819813493524457615383204504505224030129953230866877990529769205769592709254542470619
p - q = 1432
4.4 结果分析
分解成功！让我们分析这个结果：
- p 和 q 确实非常接近：两者只相差 1432
- 验证我们的理论：1432 / 2 = 716，这意味着算法只需迭代约 716 次
- 执行速度极快：即使是2048位的 N，分解也在瞬间完成
- 证实了漏洞：这证明了使用 nextprime() 生成密钥的严重安全问题
五、RSA解密过程
成功分解 N 得到 p 和 q 后，我们就可以按照标准的RSA解密流程来恢复明文。
5.1 步骤一：计算欧拉函数 φ(N)
欧拉函数 φ(N) 表示小于 N 且与 N 互质的正整数的个数。对于 N = p × q（p 和 q 都是素数），欧拉函数的计算公式为：
φ(N) = (p - 1) × (q - 1)
这个公式的数学原理：
- 小于 N 的正整数共有 N-1 个
- 其中与 N 不互质的数是 p 的倍数和 q 的倍数
- 通过容斥原理可以推导出上述公式
Python实现：
phi = (p - 1) * (q - 1)
5.2 步骤二：计算私钥 d
私钥 d 是公钥 e 在模 φ(N) 下的乘法逆元，即满足：
e × d ≡ 1 (mod φ(N))
换句话说，d 是使得 (e × d) 除以 φ(N) 余 1 的数。
数学背景：
- 这是模运算中的乘法逆元问题
- 只有当 gcd(e, φ(N)) = 1 时，d 才存在
- 在RSA中，e 通常选择 65537，保证与 φ(N) 互质
Python实现：
d = pow(e, -1, phi)
这里使用了Python 3.8+的新特性：pow(a, -1, m) 直接计算 a 关于模 m 的乘法逆元。
5.3 步骤三：解密密文
有了私钥 d 后，我们就可以解密密文 c 了。RSA解密公式为：
m = c^d mod N
数学原理：
- 加密时：c = m^e mod N
- 解密时：m = c^d mod N
- 由于 e × d ≡ 1 (mod φ(N))，根据欧拉定理，可以证明 (m^e)^d ≡ m (mod N)
Python实现：
m = pow(c, d, N)
这里使用了Python的三参数 pow 函数，它高效地计算模幂运算。
5.4 步骤四：将明文转换为字符串
解密得到的 m 是一个大整数，我们需要将它转换回原始的字符串形式。
转换过程：
- 加密时使用
bytes_to_long()将字符串转为整数 - 解密时使用
long_to_bytes()将整数转回字符串
Python实现：
from Crypto.Util.number import long_to_bytes
flag = long_to_bytes(m)
print(flag.decode())
long_to_bytes() 函数将大整数转换为字节串，然后使用 .decode() 方法将字节串解码为UTF-8字符串。
六、完整解题脚本
将前面所有步骤整合，我们得到完整的解题脚本：
from math import isqrt
from Crypto.Util.number import long_to_bytes
def fermat(n):
"""费马分解法"""
a = isqrt(n) + 1
b2 = a * a - n
while b2 < 0 or isqrt(b2) ** 2 != b2:
a = a + 1
b2 = a * a - n
b = isqrt(b2)
p = a + b
q = a - b
assert n == p * q
return p, q
# 题目给出的参数
N = 12194420073815392880989031611545296854145241675320130314821394843436947373331080911787176737202940676809674543138807024739454432089096794532016797246441325729856528664071322968428804098069997196490382286126389331179054971927655320978298979794245379000336635795490242027519669217784433367021578247340154647762800402140321022659272383087544476178802025951768015423972182045405466448431557625201012332239774962902750073900383993300146193300485117217319794356652729502100167668439007925004769118070105324664379141623816256895933959211381114172778535296409639317535751005960540737044457986793503218555306862743329296169569
e = 65537
c = 4504811333111877209539001665516391567038109992884271089537302226304395434343112574404626060854962818378560852067621253927330725244984869198505556722509058098660083054715146670767687120587049288861063202617507262871279819211231233198070574538845161629806932541832207041112786336441975087351873537350203469642198999219863581040927505152110051313011073115724502567261524181865883874517555848163026240201856207626237859665607255740790404039098444452158216907752375078054615802613066229766343714317550472079224694798552886759103668349270682843916307652213810947814618810706997339302734827571635179684652559512873381672063
# 步骤1: 使用费马分解法分解N
print("[*] 步骤1: 使用费马分解法分解 N")
p, q = fermat(N)
print(f"[+] p = {p}")
print(f"[+] q = {q}")
print(f"[+] p - q = {p - q}")
# 步骤2: 计算欧拉函数
print("\n[*] 步骤2: 计算欧拉函数 φ(N)")
phi = (p - 1) * (q - 1)
print("[+] φ(N) = (p-1) * (q-1)")
# 步骤3: 计算私钥d
print("\n[*] 步骤3: 计算私钥 d")
d = pow(e, -1, phi)
print("[+] d = e^(-1) mod φ(N)")
# 步骤4: 解密密文
print("\n[*] 步骤4: 解密密文")
m = pow(c, d, N)
print("[+] m = c^d mod N")
# 步骤5: 转换为字符串
print("\n[*] 步骤5: 将明文转换为字符串")
flag = long_to_bytes(m)
print(f"[+] Flag: {flag.decode()}")
6.1 运行结果
执行上述脚本，得到以下输出：
[*] 步骤1: 使用费马分解法分解 N
[+] p = 110428348144013242234907008083355974834266917027228724749730385104087025249352345946164980361082178532313669767485270254326404723948153912910688118140621712922649644396733499972695482991866293857864311557686710317462165131360819813493524457615383204504505224030129953230866877990529769205769592709254542472051
[+] q = 110428348144013242234907008083355974834266917027228724749730385104087025249352345946164980361082178532313669767485270254326404723948153912910688118140621712922649644396733499972695482991866293857864311557686710317462165131360819813493524457615383204504505224030129953230866877990529769205769592709254542470619
[+] p - q = 1432
[*] 步骤2: 计算欧拉函数 φ(N)
[+] φ(N) = (p-1) * (q-1)
[*] 步骤3: 计算私钥 d
[+] d = e^(-1) mod φ(N)
[*] 步骤4: 解密密文
[+] m = c^d mod N
[*] 步骤5: 将明文转换为字符串
[+] Flag: flag{5c9c885c361541e0b261f58b61db8cec}
成功获取flag！
七、深入分析与安全启示
7.1 为什么费马分解法如此高效？
让我们通过数学分析来理解费马分解法的效率：
迭代次数分析：
- 设 p – q = 2k，则 b = (p-q)/2 = k
- 从 a = ⌈√N⌉ 开始，真实的 a = (p+q)/2
- 迭代次数 ≈ (p+q)/2 – √N = k
本题的具体情况：
- p – q = 1432，因此 k = 716
- 只需迭代约 716 次就能找到解
- 对于现代计算机，这几乎是瞬间完成的
对比传统分解方法：
- 暴力分解需要尝试 √N 次，对于2048位的数字这是不可能的
- 费马分解法将复杂度从 O(√N) 降低到 O(k)
- 当 k 很小时，这是指数级的效率提升
7.2 RSA密钥生成的正确方法
通过本题，我们学到了RSA密钥生成的重要原则：
错误的做法（本题的漏洞）：
q = getPrime(1024)
p = sympy.nextprime(q) # 危险！p和q过于接近
正确的做法：
p = getPrime(1024)
q = getPrime(1024)
while p == q: # 确保p和q不相同
q = getPrime(1024)
更安全的做法（增加检查）：
p = getPrime(1024)
q = getPrime(1024)
# 确保p和q不相同
while p == q:
q = getPrime(1024)
# 确保p和q的差值足够大
while abs(p - q) < 2**512:
q = getPrime(1024)
7.3 其他针对RSA的攻击方法
除了费马分解法，当RSA实现不当时，还可能遭受以下攻击：
1. 小公钥指数攻击（Low Public Exponent Attack）
- 当 e 很小（如 e=3）且明文 m 也很小时
- 可能出现 m^e < N，直接开 e 次方根即可得到 m
2. 共模攻击（Common Modulus Attack）
- 多个用户使用相同的 N 但不同的 e
- 攻击者可以在不分解 N 的情况下恢复明文
3. Wiener’s 攻击
- 当私钥 d 很小时（d < N^0.25）
- 可以通过连分数算法快速恢复 d
4. Pollard’s p-1 算法
- 当 p-1 或 q-1 只包含小素因子时有效
- 利用费马小定理进行分解
5. 中国剩余定理（CRT）侧信道攻击
- 利用 RSA-CRT 实现中的时序差异
- 可能泄露私钥信息
八、总结
8.1 本题关键知识点回顾
通过本题的完整分析和实战，我们掌握了以下核心知识：
1. 漏洞识别能力
- 通过代码审计发现
p = sympy.nextprime(q)的安全隐患 - 理解 p 和 q 过于接近会导致的安全问题
- 认识到密钥生成过程的重要性
2. 费马分解法
- 数学原理：N = a² – b²
- 算法实现：从 √N 开始迭代搜索
- 效率分析：时间复杂度 O(k)，其中 k = (p-q)/2
- 适用场景：两个因子接近的合数分解
3. RSA完整攻击流程
- 分解 N 得到 p 和 q
- 计算欧拉函数 φ(N) = (p-1)(q-1)
- 计算私钥 d = e^(-1) mod φ(N)
- 解密密文 m = c^d mod N
- 转换明文 flag = long_to_bytes(m)
4. Python密码学编程
- 使用
math.isqrt()进行整数平方根运算 - 使用
pow(a, -1, m)计算模逆元 - 使用
pow(c, d, N)进行模幂运算 - 使用
Crypto.Util.number进行大整数与字节串转换
8.2 安全启示
本题给我们带来了重要的安全启示：
1. 密钥生成是RSA安全的基石
- RSA的安全性不仅依赖于密钥长度
- 更依赖于正确的密钥生成方式
- 即使使用2048位密钥，错误的生成方式也会导致系统完全不安全
2. 避免数学关系
- p 和 q 必须是独立随机生成的
- 不能使用 nextprime、p=2q+1 等具有数学关系的生成方式
- 应确保 |p-q| 足够大
3. 代码审计的重要性
- 在实际应用中，应对密码学实现进行严格的代码审计
- 即使是看似微小的实现细节，也可能导致严重的安全漏洞
- 密码学代码需要经过专业的安全评估
4. 使用成熟的密码学库
- 不要自己实现密码学算法
- 使用经过充分测试和审计的密码学库（如 OpenSSL、PyCryptodome）
- 遵循密码学最佳实践和标准
8.3 实战价值
通过本题的学习和实践，我们获得了以下实战能力：
CTF竞赛能力
- 快速识别RSA弱密钥漏洞
- 掌握费马分解法的实现和应用
- 理解RSA攻击的完整流程
安全审计能力
- 能够审计密码学代码中的安全问题
- 识别密钥生成过程中的潜在漏洞
- 评估RSA实现的安全性
密码学研究能力
- 深入理解RSA的数学原理
- 掌握因数分解的多种方法
- 了解密码学攻击的思路和技巧
8.4 结语
本文通过一道CTF密码学题目，完整展示了RSA弱密钥攻击的全过程。从代码审计发现漏洞，到理解费马分解法的数学原理，再到实现完整的攻击脚本，每一步都进行了详细的分析和讲解。
费马分解法是一个优雅而强大的算法，它告诉我们：在密码学中，即使使用了足够长的密钥，如果密钥生成过程存在缺陷，整个系统的安全性也会土崩瓦解。这个案例深刻地说明了”细节决定成败”在密码学领域的重要性。
希望通过本文的学习，读者不仅能够掌握费马分解法这一具体技术，更能够建立起正确的密码学安全意识，在今后的学习和工作中避免类似的安全隐患。
密码学是一门既需要深厚数学功底，又需要严谨工程实践的学科。让我们在探索密码学奥秘的道路上不断前行！
参考资料：
- RSA加密算法原理
- 费马分解法（Fermat’s Factorization Method）
- 素数定理（Prime Number Theorem）
- Python密码学库 PyCryptodome 文档
免责声明：
本文所载程序、技术方法仅面向合法合规的安全研究与教学场景，旨在提升网络安全防护能力，具有明确的技术研究属性。
任何单位或个人未经授权，将本文内容用于攻击、破坏等非法用途的，由此引发的全部法律责任、民事赔偿及连带责任，均由行为人独立承担，本站不承担任何连带责任。
本站内容均为技术交流与知识分享目的发布，若存在版权侵权或其他异议，请通过邮件联系处理，具体联系方式可点击页面上方的联系我。
本文转载自：破镜安全 破镜安全 破镜安全《RSA弱密钥攻击实战：费马分解法完全解析》
版权声明
本站仅做备份收录，仅供研究与教学参考之用。
读者将信息用于其他用途的，全部法律及连带责任由读者自行承担，本站不承担任何责任。
评论