1. 费马分解法当RSA的p和q成为邻居想象你家的WiFi密码是两个相邻门牌号相乘的结果比如502×503252506。如果邻居知道这个规律只需要计算√252506≈502.499然后检查503是否能整除252506——密码瞬间告破。这就是RSA中费马分解法的核心思想当两个大素数p和q过于接近时它们的乘积n会暴露致命弱点。在CTF竞赛中这类题目通常会给出以下特征题目描述中暗示p和q有特殊关系模数n的位数通常为1024bit或更低使用gmpy2.next_prime()等函数生成相邻素数# 典型漏洞代码示例 from Crypto.Util.number import getPrime import gmpy2 p getPrime(512) q gmpy2.next_prime(p) # q直接紧挨着p生成 n p * q # 这就埋下了被费马分解的隐患2. 数学原理平方差下的素数暴露费马分解的本质是平方差公式的逆向运用。当p和q接近时存在整数a和b使得n p×q a² - b² (ab)(a-b)其中a(pq)/2b(q-p)/2。由于p和q接近b会非常小这使得我们可以通过以下步骤快速分解n计算a的初始值a₀ ⌈√n⌉检查a₀² - n是否为完全平方数若不是则a₀ 1继续尝试找到b后即可得到pa-bqabimport gmpy2 def fermat_factor(n): a gmpy2.isqrt(n) 1 # ⌈√n⌉ while True: b2 a*a - n if gmpy2.is_square(b2): b gmpy2.isqrt(b2) return (a-b, ab) a 1 # 步进搜索3. CTF实战绿城杯RSA2-PLUS题解让我们看一个真实CTF案例2021绿城杯from Crypto.Util.number import * import gmpy2 p getPrime(512) p1 gmpy2.next_prime(p) # p1与p相邻 q getPrime(512) q1 gmpy2.next_prime(q) # q1与q相邻 n p*q*p1*q1 # 包含两组相邻素数解题步骤对n进行费马分解会得到两组解(pq, p1q1)和(pq1, qp1)计算gcd(pq, pq1) p通过p即可得到所有其他因子def solve(): list factor(n) # 使用前述费马分解 X1, Y1 list[0] # 第一组解 X2, Y2 list[1] # 第二组解 p gmpy2.gcd(X1, X2) # 提取公约数 q X1 // p p1 Y1 // q q1 Y2 // p phi (p-1)*(q-1)*(p1-1)*(q1-1) d gmpy2.invert(e, phi) return pow(c, d, n)4. 防御措施如何生成安全的RSA密钥在实际密码工程中必须避免素数过于接近的情况随机性要求使用密码学安全的随机数生成器p和q的差值应大于n^(1/4)生成算法改进# 安全素数生成示例 from Crypto.Util.number import getPrime import gmpy2 import os def gen_safe_prime(bits): while True: p getPrime(bits) q getPrime(bits) # 确保两者差值足够大 if abs(p-q) 2**(bits//2): return p, q边界检查检测|p-q|是否过小验证p/q是否在√n附近5. 进阶技巧非素数情况下的分解策略有时即使p和q不全是素数费马分解依然有效。比如当np×r其中p是素数而r是合数但r的因子都接近√r时def complex_fermat(n, max_iter10000): a gmpy2.isqrt(n) 1 for _ in range(max_iter): b2 a*a - n if gmpy2.is_square(b2): b gmpy2.isqrt(b2) factor1 a - b factor2 a b # 对分解结果进一步检查 if gmpy2.is_prime(factor1): return factor1, n//factor1 elif gmpy2.is_prime(factor2): return factor2, n//factor2 else: # 递归分解 return complex_fermat(factor1) complex_fermat(factor2) a 1 return None6. 性能优化加速费马分解的技巧对于超大的n如2048bit原始费马分解可能较慢。我们可以通过以下优化加速预筛选策略只检查a² - n mod m为平方剩余的情况常用模数m64, 256等def optimized_fermat(n): a gmpy2.isqrt(n) 1 # 预计算平方剩余表 squares_mod64 {0,1,4,9,16,17,25,33,36,41,49,57} while True: b2 a*a - n if b2 % 64 in squares_mod64: # 快速筛选 if gmpy2.is_square(b2): return (a-gmpy2.isqrt(b2), agmpy2.isqrt(b2)) a 1多线程并行将a的搜索范围划分为多个区间每个线程处理一个区间7. 现代CTF中的变形题型最近的CTF比赛出现了更隐蔽的亲密素数题型案例1moectf2022p getPrime(2048) q gmpy2.next_prime(p getPrime(256)) # q与p相差一个256bit数解法 此时常规费马分解仍然有效但需要更多迭代步数。可以通过以下改进调整初始搜索点a ⌈√n⌉ 2^255使用更大的步长如10而不是1案例2特殊多项式关系p getPrime(512) q next_prime(p^2 3*p 1) # 多项式关系这类题目需要先通过n的估算确定多项式系数再建立方程求解。