从BUUCTF一道RSA难题看e与φ不互素问题的AMM算法实战解析
1. 当RSA遇上特殊条件：e与φ(n)不互素问题
第一次遇到RSA题目时，很多CTF选手都会觉得"这不就是白给题吗？"——毕竟只要知道p和q，按照标准流程计算私钥d就能解密。但现实往往给我们当头一棒：当公钥指数e与欧拉函数φ(n)不互素时，常规解密方法会完全失效，输出的解密结果变成一堆乱码。这种情况在CTF竞赛中越来越常见，比如BUUCTF的easyRSA题目就设置了e=0x1337这样的特殊值。
为什么会出现这种情况？让我们从RSA的基本原理说起。在标准RSA中，私钥d实际上是e在模φ(n)下的乘法逆元，即d ≡ e⁻¹ mod φ(n)。这个逆元存在的前提就是e与φ(n)必须互素。当两者不互素时，逆元不存在，我们无法用常规方法计算私钥。此时就需要AMM算法这样的"非常规武器"来解决问题。
我最初遇到这类问题时也是一头雾水，直到在wp（writeup）中发现了AMM算法这个神奇的工具。它就像一把能打开特殊锁具的万能钥匙，通过有限域开方和中国剩余定理(CRT)的组合，绕过了传统解密的限制。下面我们就来深入剖析这个算法的精妙之处。
2. AMM算法原理深度解析
2.1 算法核心思想
AMM算法全称Adleman-Manders-Miller Root Extraction Method，是一种在有限域中计算高次方根的算法。它的核心思路是将原问题mᵉ ≡ c mod n分解为两个子问题：
{ mᵉ ≡ c mod p mᵉ ≡ c mod q }然后在GF(p)和GF(q)上分别求解e次方根，最后用CRT组合结果。这个思路看似简单，但实现起来却有不少精妙的数学技巧。
我第一次实现这个算法时，最困惑的部分是如何在有限域中开任意次方根。这需要以下几个关键步骤：
- 找到满足条件的随机元素p，使得p^((q-1)/r) ≠ 1
- 分解q-1为s * rᵗ的形式
- 计算k使得k*s + 1能被r整除
- 通过一系列迭代计算最终结果
2.2 算法实现细节
让我们结合代码来看具体实现。以下是AMM算法的Python实现关键部分：
def AMM(o, r, q): g = GF(q) o = g(o) # 步骤1：找到合适的p p = g(random.randint(1, q)) while p ^ ((q-1) // r) == 1: p = g(random.randint(1, q)) # 步骤2：分解q-1为s * r^t t = 0 s = q - 1 while s % r == 0: t += 1 s = s // r # 步骤3：计算k k = cal_k(s, r) # 解方程k*s ≡ -1 mod r alp = (k * s + 1) // r a = p ^ (r**(t-1) * s) b = o ^ (r*alp - 1) c = p ^ s h = 1 # 步骤4：迭代计算 for i in range(1, t): d = b ^ (r^(t-1-i)) if d != 1: j = - dicreat_log(a, d) b = b * (c^r)^j h = h * c^j c = c ^ r result = o^alp * h return result在实际应用中，我发现这个算法有两个关键条件必须满足：
- r必须能整除q-1（即r|q-1），否则t=0会导致计算错误
- 必须存在整数k使得r能整除k*s+1，否则算法会陷入死循环
3. 实战BUUCTF easyRSA题目
3.1 题目分析与准备
让我们回到BUUCTF的easyRSA题目。题目给出了以下参数：
e = 0x1337 p = 199138677823743... q = 112213695905472... c = 105623026905419...首先检查e与φ(n)是否互素：
phi = (p-1)*(q-1) gcd(e, phi) # 结果为0x1337，说明不互素这种情况下常规解密方法失效，必须使用AMM算法。我们需要分别在GF(p)和GF(q)上计算c的e次方根。
3.2 分步解题过程
第一步：计算cp和cq
cp = c % p cq = c % q第二步：在GF(p)和GF(q)上应用AMM算法
mp = AMM(cp, e, p) mq = AMM(cq, e, q)第三步：找到所有原始根由于e次方根在有限域中可能有多个解，我们需要找到所有可能的解：
p_proot = findAllPRoot(p, e) q_proot = findAllPRoot(q, e)第四步：生成所有可能的解组合
mps = findAllSolutions(mp, p_proot, cp, p) mqs = findAllSolutions(mq, q_proot, cq, q)第五步：使用CRT组合结果并验证
for mpp in mps: for mqq in mqs: solution = CRT_list([int(mpp), int(mqq)], [p, q]) if check(solution): # 检查是否以'NCTF'开头 print(bytes.fromhex(solution.hex()))在实际操作中，这个过程大约需要16分钟，因为e=0x1337较大，需要进行24196561次CRT组合。这也是为什么比赛时只有两个人解出这道题的原因。
4. AMM算法的适用条件与优化
4.1 算法适用条件
通过多次实践，我总结出AMM算法适用的两个必要条件：
r | q-1：r必须能整除q-1，这样才能保证t>0，使得a = p^(r^(t-1)*s)计算有效。我在一次尝试中忽略了这点，结果程序直接抛出除零错误。
存在k使得r | k*s + 1：这个条件保证了方程有解。曾经有一次我遇到了死循环，就是因为这个条件不满足，程序不断尝试k值直到内存溢出。
4.2 性能优化技巧
对于大型CTF比赛，算法效率至关重要。以下是几个优化AMM算法实现的技巧：
预处理原始根：可以预先计算并缓存常见的原始根，减少重复计算。
并行计算：由于各次CRT组合是独立的，可以使用多线程并行处理。
早期终止：一旦找到符合条件的解就立即终止计算，不必遍历所有可能性。
选择合适语言：对于性能关键部分，可以使用C/C++扩展替代Python。
# 并行计算示例 from multiprocessing import Pool def parallel_CRT(args): mpp, mqq = args solution = CRT_list([int(mpp), int(mqq)], [p, q]) if check(solution): return solution return None with Pool(8) as p: # 使用8个进程 results = p.map(parallel_CRT, [(mpp, mqq) for mpp in mps for mqq in mqs])5. 其他场景下的应用与思考
5.1 不同e值的情况
AMM算法不仅适用于e=0x1337这种情况，对于其他e与φ(n)不互素的场景也同样有效。例如在hackergame 2019的一道题目中，e=10且与φ(n)不互素，也可以使用AMM算法解决。
不过需要注意的是，当模数不是素数而是像y³这样的高次幂时，计算会变得非常耗时。这时可能需要寻找其他优化方法，或者考虑题目是否有特殊性质可以利用。
5.2 与其他方法的对比
除了AMM算法，对于e与φ(n)不互素的情况还有几种可能的解法：
直接开方法：当e较小时（如e=2,3,4），可以直接尝试开方。但这种方法在e较大时不适用。
多项式求根：在多项式环中求解，如：
R.<b> = PolynomialRing(GF(y^3)) g = b^e - z y_roots = [yr[0] for yr in g.roots()]- 分解n：如果n可以被分解，有时可以通过分解后的信息找到解密方法。
在实际CTF比赛中，AMM算法通常是这类问题的最通用解法。我建议CTF选手熟练掌握这个算法，因为它在各种变种RSA题目中都有应用。