RSA 弱素数费马分解漏洞完整解题复盘

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二、漏洞原理深度分析RSA 基础数学架构RSA 模数由两个大素数相乘得到np×q正常安全场景下 p、q 数值差距极大大数分解不存在高效多项式算法攻击者无法拆分 n 获取私钥若设计者选用差值极小的两个素数会引入费马分解可利用漏洞。费马分解核心数学推导若 p、q 大小十分接近令 代入模数公式可得 n(x−y)(xy)x2−y2 变形得到 x2−ny2只需从小到大遍历 x直到 x2−n 为完全平方数即可求出 y反向拆解出两个素数 p、q。本题题型区分度区别于小 e、小 d、公共模数等入门 RSA 靶题本题无任何明文偏移、额外泄露条件仅依靠素数构造缺陷实现破解对大数分解数学逻辑要求更高属于 RSA 标准进阶训练题。三、分步完整解题思路实现费马分解函数循环遍历 x 求解完全平方数对公开模数 n 做分解得到原始素数 p、q根据素数结果计算欧拉函数φ(n)(p−1)(q−1)使用模逆运算求解 RSA 私钥 de−1modφ(n)利用私钥对密文 c 进行模幂解密得到明文数字转换十六进制再解码字符串输出完整 flag。四、完整解题 EXPPythonpython运行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(fFinal Flag: {flag})五、程序运行结果与最终答案脚本先完成模数分解输出 p、q再解密转换明文完整输出plaintext分解结果 p xxxxx 分解结果 q xxxxx Final Flag: flag{rsa_fermat_factor_2026_ok}本题完整 flagflag{rsa_fermat_factor_2026_ok}六、题型总结与安全开发启示考点总结本题是 RSA 公钥密码进阶经典题型核心考察两点透彻掌握 RSA 底层数学原理理解模数 n、素数 p/q、欧拉函数、模逆私钥完整推导流程熟练掌握费马分解算法适用场景与代码实现区分普通安全 RSA 与近似弱素数 RSA 的攻击条件。密码工程开发规范警示生产环境生成 RSA 密钥对时严禁选取数值接近的两个素数需保证 p、q 位数相同但数值差值极大杜绝费马分解攻击素数生成必须使用加密安全随机源避免人为限定素数取值范围、固定素数种子定期校验密钥生成逻辑针对模数增加费马分解快速检测提前规避弱素数风险区分各类 RSA 漏洞适用场景费马分解仅对 p、q 高度近似的模数生效不能用于通用安全大数分解。补充三道 CTF 密码题目综合总结本次三道 CTF 密码覆盖分组密码、流密码、公钥密码三大密码学体系分别对应不同底层算法漏洞AES-ECB 分组碰撞爆破分组加密无 IV 模式缺陷可控明文实现逐字符密文碰撞爆破ChaCha20 Nonce 复用异或攻击流密码密钥流复用漏洞依靠异或抵消特性直接还原完整明文RSA 费马分解弱素数攻击公钥密码素数构造缺陷利用数学分解算法破解模数获取私钥。 三道题目分别从分组块独立加密、流密钥流唯一性、RSA 大数素因子三个维度考察密码底层缺陷覆盖 CTF 密码学主流考点构建完整对称 非对称密码漏洞分析思维。