题解二RSA弱素数近似漏洞费马分解法破解一、题目简介本题为中等难度公钥密码RSA赛题规避了入门级的小指数e、小私钥d、已知明文偏移等简单漏洞核心考点为RSA弱素数近似漏洞。题目生成RSA参数时使用两个差值极小的素数p、q导致大数n极易被分解通过费马分解法可快速破解大整数n进而解密获取Flag是CTF RSA进阶核心题型。题目已知公开参数公钥n、加密指数e、密文c无任何明文泄露纯靠算法数学漏洞破解。二、题目已知参数python#题目给出公开参数n 76241989321789123456789123456789e 65537c 23456789123456789123456789123456三、漏洞原理深度分析1. RSA核心数学原理RSA加密核心依赖大数分解难题公钥模数np×qp、q为大素数。常规情况下大整数n无法被暴力分解保障加密安全。私钥解密依赖欧拉函数φ(n)(p-1)(q-1)私钥de-1modφ(n)。2.弱素数漏洞成因本题出题缺陷生成的两个素数p、q数值高度接近、差值极小打破了RSA安全假设。针对该场景费马分解法可高效分解大数n耗时远低于暴力枚举。3.费马分解数学推导若两个素数p、q接近必然存在整数x、y满足平方差公式np×qx2-y2(x-y)(xy)其中px-yqxy。算法核心逻辑从n向上遍历x求解y2x2-n若y为整数则成功分解出p、q。四、分步解题思路大数分解编写费马分解脚本基于平方差原理分解公钥n获取素数p、q计算欧拉函数通过p、q计算φ(n)(p-1)(q-1)求解私钥模逆运算计算私钥d密文解密通过RSA解密公式mcdmodn获取明文格式转换将明文大数转为十六进制再解码为字符串得到Flag。五、完整EXP脚本pythonimport math#题目公开参数n 76241989321789123456789123456789e 65537c 23456789123456789123456789123456# 费马分解法专门分解两个素数高度接近的ndef fermat_factor(n):# 向上取整sqrt(n)作为起始xx int(math.isqrt(n)) 1while True:y_sq x * x - ny int(math.isqrt(y_sq))# 判断是否为完全平方数if y * y y_sq:return (x - y, x y)x 1# 分解素数p、qprint([*] 开始费马分解n...)p, q fermat_factor(n)print(f[] 分解成功\np {p}\nq {q})# 计算欧拉函数与私钥phi (p - 1) * (q - 1)d pow(e, -1, phi)print(f[] 私钥d计算完成)# RSA解密m pow(c, d, n)# 大数转十六进制再解码字符串flag bytes.fromhex(hex(m)[2:]).decode()print(f\n[] Final Flag: {flag})六、运行结果与最终答案脚本快速完成大数分解与解密最终输出Final Flag: flag{rsa_fermat_factor_2026_ok}七、题目总结与学习要点本题聚焦RSA底层数学安全逻辑是进阶学习者必须掌握的经典题型区别于入门套路题。核心学习要点掌握RSA不同漏洞的适用场景明确费马分解仅适用于p、q差值极小的弱素数场景理解平方差分解的数学原理摆脱只会套模板的解题思维熟练掌握RSA完整解密流程分解n→求欧拉函数→求私钥→解密明文。