企业官网建设流程全解析

1. 费马分解法：当RSA的p和q成为"邻居"

想象你家的WiFi密码是两个相邻门牌号相乘的结果，比如502×503=252506。如果邻居知道这个规律，只需要计算√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² = (a+b)(a-b)

其中a=(p+q)/2，b=(q-p)/2。由于p和q接近，b会非常小，这使得我们可以通过以下步骤快速分解n：

1. 计算a的初始值：a₀ = ⌈√n⌉
2. 检查a₀² - n是否为完全平方数
3. 若不是则a₀ += 1继续尝试
4. 找到b后即可得到p=a-b，q=a+b

import 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, a+b) 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 # 包含两组相邻素数

解题步骤：

1. 对n进行费马分解，会得到两组解：(pq, p1q1)和(pq1, qp1)
2. 计算gcd(pq, pq1) = p
3. 通过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密钥

在实际密码工程中，必须避免素数过于接近的情况：

1. 随机性要求：

   • 使用密码学安全的随机数生成器
   • p和q的差值应大于n^(1/4)

2. 生成算法改进：

# 安全素数生成示例 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

3. 边界检查：
   • 检测|p-q|是否过小
   • 验证p/q是否在√n附近

5. 进阶技巧：非素数情况下的分解策略

有时即使p和q不全是素数，费马分解依然有效。比如当n=p×r，其中p是素数而r是合数，但r的因子都接近√r时：

def complex_fermat(n, max_iter=10000): 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 None

6. 性能优化：加速费马分解的技巧

对于超大的n（如2048bit），原始费马分解可能较慢。我们可以通过以下优化加速：

1. 预筛选策略：
   • 只检查a² - n mod m为平方剩余的情况
   • 常用模数m=64, 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), a+gmpy2.isqrt(b2)) a += 1

2. 多线程并行：
   • 将a的搜索范围划分为多个区间
   • 每个线程处理一个区间

7. 现代CTF中的变形题型

最近的CTF比赛出现了更隐蔽的"亲密素数"题型：

案例1（moectf2022）：

p = getPrime(2048) q = gmpy2.next_prime(p + getPrime(256)) # q与p相差一个256bit数

解法： 此时常规费马分解仍然有效，但需要更多迭代步数。可以通过以下改进：

1. 调整初始搜索点：a = ⌈√n⌉ + 2^255
2. 使用更大的步长（如+10而不是+1）

案例2（特殊多项式关系）：

p = getPrime(512) q = next_prime(p^2 + 3*p + 1) # 多项式关系

这类题目需要先通过n的估算确定多项式系数，再建立方程求解。