CTF实战：当RSA的e与φ(n)不互素时，别再傻傻分解n了！手把手教你AMM算法开e次方根

CTF实战当RSA的e与φ(n)不互素时AMM算法开e次方根的终极指南在CTF密码学挑战中RSA问题一直是考察选手数学功底和编程能力的经典题型。但当你遇到公钥指数e与欧拉函数φ(n)不互素的情况时传统解密方法瞬间失效——这正是[NCTF2019]easyRSA等赛题设置的巧妙陷阱。本文将彻底解析AMMAdleman-Manders-Miller算法这一数学核武器手把手教你如何在有限域中开高次方根并构建完整的解题框架。1. 问题本质与常规解法的失效面对已知p、q的RSA题目新手常会直接计算私钥d≡e⁻¹ mod φ(n)。但当gcd(e,φ(n))≠1时模逆元d根本不存在。以[NCTF2019]easyRSA为例e 0x1337 p 199138677823743837339927520157607820029746574557746549094921488292877226509198315016018919385259781238148402833316033634968163276198999279327827901879426429664674358844084491830543271625147280950273934405879341438429171453002453838897458102128836690385604150324972907981960626767679153125735677417397078196059 q 112213695905472142415221444515326532320352429478341683352811183503269676555434601229013679319423878238944956830244386653674413411658696751173844443394608246716053086226910581400528167848306119179879115809778793093611381764939789057524575349501163689452810148280625226541609383166347879832134495444706697124741 φ(n) (p-1)*(q-1) print(gcd(e, φ(n))) # 输出结果为487验证不互素此时必须将问题拆解到素域层面。通过中国剩余定理CRT原问题可转化为\begin{cases} m^e \equiv c \mod p \\ m^e \equiv c \mod q \end{cases}2. AMM算法的数学原理AMM算法是解决素域GF(p)中高次方根问题的利器其核心在于将开方问题转化为离散对数问题。算法执行需要满足两个关键条件r | p-1r整除p-1存在整数k使得r | k*s 1其中s(p-1)/r^t算法流程可分为三个阶段2.1 参数初始化阶段寻找满足条件的非r次剩余pg GF(q) p g(random.randint(1, q)) while p^((q-1)//r) 1: p g(random.randint(1, q))2.2 指数分解阶段计算t和s使得q-1 r^t \cdot s \quad (\gcd(r,s)1)对应代码实现t 0 s q - 1 while s % r 0: t 1 s s // r2.3 核心计算阶段通过以下步骤逐步求解计算k满足k*s ≡ -1 mod r构造辅助值α (k*s 1)/r初始化a p^(r^(t-1)*s)迭代计算h值3. SageMath实战实现以下是优化后的AMM算法完整实现def AMM(o, r, q): g GF(q) o g(o) p g(random.randint(1, q)) while p^((q-1)//r) 1: p g(random.randint(1, q)) t 0 s q - 1 while s % r 0: t 1 s s // r k inverse_mod(r, s) alp (k * s 1) // r a p^(r^(t-1)*s) b o^(r*alp - 1) c p^s h 1 for i in range(1, t): d b^(r^(t-1-i)) if d ! 1: j -discrete_log(d, a) else: j 0 b b * (c^r)^j h h * c^j c c^r return o^alp * h4. 完整解题流程与优化技巧4.1 分域求解与CRT组合分别在GF(p)和GF(q)域求解cp c % p cq c % q mp AMM(cp, e, p) mq AMM(cq, e, q)寻找所有本原根def findAllPRoot(p, e): proot set() while len(proot) e: proot.add(pow(random.randint(2, p-1), (p-1)//e, p)) return proot组合所有可能解def findAllSolutions(mp, proot, cp, p): all_mp set() for root in proot: mp2 mp * root % p assert(pow(mp2, e, p) cp) all_mp.add(mp2) return all_mp4.2 实际应用中的加速技巧并行计算p和q域的求解可并行处理预计算对于固定参数的比赛环境可预先计算本原根边界检查添加flag格式验证减少无效计算def check(m): try: return m.hex().startswith(4e435446) # NCTF的hex前缀 except: return False5. 算法适用性与变种场景AMM算法并非万能钥匙其有效性取决于以下条件条件必要性验证方法r | q-1必须满足检查(q-1)%r 0∃k使r | ks1必须满足扩展欧几里得算法r较小影响效率实测r65537时已较慢对于更复杂的情况如e与φ(n)有多个公因数可采用分层求解策略对e进行素因数分解e π r_i^a_i逐层求解m^(r_i^a_i) ≡ c mod p通过中国剩余定理组合结果在[De1CTF2019]babyrsa等赛题中还可能遇到需要结合以下技术的情况Hensel提升从模p解提升到模p^k解多项式分解当AMM不适用时考虑环上的多项式求根# 多项式求根示例当e10且模y^3时 R.b PolynomialRing(Zmod(y^3)) g b^e - z roots [r[0] for r in g.roots()]理解AMM算法的核心在于掌握有限域中的离散对数与高次剩余理论。这需要选手不仅会调用SageMath的现成函数更要明白背后的数论原理。建议通过以下方式深化理解用小型素数如p23手工演算算法流程比较AMM与Tonelli-Shanks算法二次剩余特例的异同研究Pohlig-Hellman算法与AMM的内在联系在最近的几场CTF比赛中AMM算法的变种应用频率明显上升。例如特殊e构造e取φ(n)的大因数如e(p-1)/2多素数RSA需要处理多个素域的解并组合非素数次方需先分解e为素数幂次再分层处理掌握AMM算法后你会发现许多看似无解的RSA题目其实都存在优雅的数学解法。关键在于将密码学问题转化为合适的数学问题——这正是CTF密码学挑战的精髓所在。