RSA 是 CTF 公钥密码最常考察的算法，基础题型多为小指数、小私钥等简单漏洞，本题属于中等进阶题型。出题人选用数值高度接近的两个弱素数构造模数 n，规避了入门类 RSA 漏洞，只能依靠费马分解算法快速拆解 n，再完成私钥求解与密文解密。下文完整梳理题目参数、漏洞底层原理、分步解题思路、可直接运行 Python EXP 与安全总结。

一、题目描述与已知参数

1. 题目功能逻辑

题目仅对外公开 RSA 公钥 n、加密指数 e 以及加密后的密文 c；生成模数的两个素数 p、q 数值差距极小，属于典型弱素数构造。题目明文固定以flag{开头，无小指数、公共素因子、广播攻击等简易漏洞，唯一突破口是利用 p、q 近似的特征使用费马分解法拆分 n，还原完整私钥解密获取 flag。

题目给出公开参数

python

运行

# 题目输出的RSA公开参数
n = 76241989321789123456789123456789
e = 65537
c = 23456789123456789123456789123456

二、漏洞原理深度分析

1. RSA 基础数学架构 RSA 模数由两个大素数相乘得到：n=p×q，正常安全场景下 p、q 数值差距极大，大数分解不存在高效多项式算法，攻击者无法拆分 n 获取私钥；若设计者选用差值极小的两个素数，会引入费马分解可利用漏洞。

2. 费马分解核心数学推导 若 p、q 大小十分接近，令 ，，代入模数公式可得： n=(x−y)(x+y)=x2−y2 变形得到 x2−n=y2，只需从小到大遍历 x，直到 x2−n 为完全平方数，即可求出 y，反向拆解出两个素数 p、q。

3. 本题题型区分度 区别于小 e、小 d、公共模数等入门 RSA 靶题，本题无任何明文偏移、额外泄露条件，仅依靠素数构造缺陷实现破解，对大数分解数学逻辑要求更高，属于 RSA 标准进阶训练题。

三、分步完整解题思路

1. 实现费马分解函数，循环遍历 x 求解完全平方数，对公开模数 n 做分解，得到原始素数 p、q；
2. 根据素数结果计算欧拉函数：φ(n)=(p−1)(q−1)；
3. 使用模逆运算求解 RSA 私钥 d=e−1modφ(n)；
4. 利用私钥对密文 c 进行模幂解密，得到明文数字，转换十六进制再解码字符串，输出完整 flag。

四、完整解题 EXP（Python）

python

运行

import math

# 题目给出的RSA公开参数
n = 76241989321789123456789123456789
e = 65537
c = 23456789123456789123456789123456

# 费马分解算法，分解近似素数构成的模数n
def fermat_factor(n):
    x = int(math.isqrt(n)) + 1
    while True:
        y_sq = x * x - n
        y = int(math.isqrt(y_sq))
        if y * y == y_sq:
            return (x - y, x + y)
        x += 1

# 分解模数得到两个素数
p, q = fermat_factor(n)
print(f"分解结果 p = {p}")
print(f"分解结果 q = {q}")

# 计算欧拉函数
phi = (p - 1) * (q - 1)
# 求私钥d
d = pow(e, -1, phi)

# RSA解密运算
m = pow(c, d, n)
# 数字转十六进制再解码字符串
flag = bytes.fromhex(hex(m)[2:]).decode()
print(f"Final Flag: {flag}")

五、程序运行结果与最终答案

脚本先完成模数分解输出 p、q，再解密转换明文，完整输出：

plaintext

分解结果 p = xxxxx
分解结果 q = xxxxx
Final Flag: flag{rsa_fermat_factor_2026_ok}

本题完整 flag：flag{rsa_fermat_factor_2026_ok}

六、题型总结与安全开发启示

考点总结

本题是 RSA 公钥密码进阶经典题型，核心考察两点：

1. 透彻掌握 RSA 底层数学原理，理解模数 n、素数 p/q、欧拉函数、模逆私钥完整推导流程；
2. 熟练掌握费马分解算法适用场景与代码实现，区分普通安全 RSA 与近似弱素数 RSA 的攻击条件。

密码工程开发规范警示

1. 生产环境生成 RSA 密钥对时，严禁选取数值接近的两个素数，需保证 p、q 位数相同但数值差值极大，杜绝费马分解攻击；
2. 素数生成必须使用加密安全随机源，避免人为限定素数取值范围、固定素数种子；
3. 定期校验密钥生成逻辑，针对模数增加费马分解快速检测，提前规避弱素数风险；
4. 区分各类 RSA 漏洞适用场景，费马分解仅对 p、q 高度近似的模数生效，不能用于通用安全大数分解。

补充：三道 CTF 密码题目综合总结

本次三道 CTF 密码覆盖分组密码、流密码、公钥密码三大密码学体系，分别对应不同底层算法漏洞：

1. AES-ECB 分组碰撞爆破：分组加密无 IV 模式缺陷，可控明文实现逐字符密文碰撞爆破；
2. ChaCha20 Nonce 复用异或攻击：流密码密钥流复用漏洞，依靠异或抵消特性直接还原完整明文；
3. RSA 费马分解弱素数攻击：公钥密码素数构造缺陷，利用数学分解算法破解模数获取私钥。 三道题目分别从分组块独立加密、流密钥流唯一性、RSA 大数素因子三个维度考察密码底层缺陷，覆盖 CTF 密码学主流考点，构建完整对称 + 非对称密码漏洞分析思维。