当RSA遇上‘坏’e：从一道CTF题看AMM算法如何破解e与φ不互素难题

当RSA遭遇特殊指数AMM算法破解e与φ(n)不互素难题的深度解析在CTF密码学挑战中RSA问题往往被设计成需要突破常规思维才能解决的形态。其中当公钥指数e与欧拉函数φ(n)不互素时传统的解密方法将完全失效——这正是NCTF2019 easyRSA赛题设置的巧妙之处。本文将从一个密码学实践者的视角系统剖析这类问题的数学本质与工程化解法重点解读AMM算法在有限域开高次方根的核心原理以及如何通过中国剩余定理CRT组合局部解。1. 问题场景与数学困境1.1 经典RSA解密的先决条件标准RSA解密依赖于一个基本前提必须存在整数d使得ed ≡ 1 mod φ(n)。这要求e与φ(n)互质否则模反元素d将不存在。但在某些特殊场景下出题人故意选择不满足互质条件的e如本题的e0x1337实际系统中因参数生成错误导致非互质基于特殊数学构造的变种RSA方案此时解密过程会遇到根本性障碍。以NCTF2019 easyRSA为例p 199138677823743837339927520157607820029746574557746549094921488292877226509198315016018919385259781238148402833316033634968163276198999279327827901879426429664674358844084491830543271625147280950273934405879341438429171453002453838897458102128836690385604150324972907981960626767679153125735677417397078196059 q 112213695905472142415221444515326532320352429478341683352811183503269676555434601229013679319423878238944956830244386653674413411658696751173844443394608246716053086226910581400528167848306119179879115809778793093611381764939789057524575349501163689452810148280625226541609383166347879832134495444706697124741 e 0x1337 # 与φ(n)有公因子191.2 数学本质分析当gcd(e,φ(n))g1时方程m^e ≡ c mod n的解法需要分情况讨论g与明文无关可通过升幂法求解即寻找k使得m^(e/g) ≡ c^k mod ng与明文相关必须直接在有限域内求解高次方根AMM算法针对的是第二种情况其核心是将问题拆解为在GF(p)和GF(q)上分别求解m^e ≡ c mod p和m^e ≡ c mod q通过CRT合并两个有限域的解关键突破点将模n的大数域问题转化为两个素数域上的可计算问题2. AMM算法原理深度剖析2.1 有限域中的方根问题对于素数p和整数e求解x^e ≡ a mod p需要满足a是模p的e次剩余e | (p-1)或通过变形满足可解条件AMM算法的创新在于处理**e不整除(p-1)**的情况。其数学基础是将p-1分解为s*r^t其中r不整除s通过随机搜索找到非r次剩余的生成元构造递推关系逐步降低方根次数2.2 算法步骤详解以下是AMM算法的关键步骤实现基于SageMathdef AMM(o, r, q): g GF(q) o g(o) # 步骤1寻找非r次剩余 p g.random_element() while p^((q-1)//r) 1: p g.random_element() # 步骤2分解q-1 s*r^t t, s 0, q-1 while s % r 0: t 1 s s // r # 步骤3求解k满足r | k*s 1 k 1 while (k*s 1) % r ! 0: k 1 alp (k*s 1) // r # 步骤4初始化变量 a p^(r^(t-1)*s) b o^(r*alp -1) c p^s h 1 # 步骤5递推求解 for i in range(1, t): d b^(r^(t-1-i)) j -discrete_log(a, d) if d !1 else 0 b b * (c^r)^j h h * c^j c c^r return o^alp * h算法各阶段的时间复杂度对比步骤计算内容时间复杂度1寻找非r次剩余O(r)随机尝试2分解q-1O(log(q))3求解kO(r)4-5递推求解O(t^2*log(r))2.3 算法适用条件验证AMM算法并非万能钥匙需要满足两个关键条件可分解性r必须整除q-1即t0可解性存在整数k使得r | k*s 1在NCTF2019 easyRSA中对于p19913...6059p-1 2 * 19 * 524...4237 * 1337^1r1337正好整除p-1满足条件实践提示在实际CTF比赛中可先用factor(p-1)检查是否满足算法前提条件3. 完整攻击链构建3.1 分而治之策略将原问题分解为三个层次有限域分解在GF(p)和GF(q)上分别求解本原根扩展找到所有可能的e次方根CRT组合筛选符合条件的有效解关键代码结构# 在GF(p)上求解 cp c % p mp AMM(cp, e, p) # 寻找所有本原根 p_proot findAllPRoot(p, e) mps findAllSolutions(mp, p_proot, cp, p) # 同理处理GF(q) ... # CRT组合验证 for mpp in mps: for mqq in mqs: solution CRT_list([int(mpp), int(mqq)], [p, q]) if check_NCTF_prefix(solution): print(bytes.fromhex(solution.hex()))3.2 解的空间分析由于e与φ(n)不互素解的数量会显著增加在GF(p)中最多有gcd(e,p-1)个解在GF(q)中最多有gcd(e,q-1)个解组合后解的总数为gcd(e,p-1)*gcd(e,q-1)在本题中gcd(0x1337, p-1) 1337gcd(0x1337, q-1) 1337理论最大解数达1,787,689种组合优化技巧通过flag格式前缀如NCTF快速过滤无效解4. 实战优化与边界情况4.1 性能优化策略AMM算法在大型素数上的计算成本较高可采用并行计算同时处理p和q的求解预计算加速缓存本原根计算结果早期终止发现有效解立即停止实测性能对比i7-11800H方法p计算时间q计算时间CRT验证时间总时间原始实现142s85s16min~18min优化并行版98s98s2min~4min4.2 特殊场景处理当遇到更复杂的情况时e与φ(n)有多个公因子需分层应用AMM算法高次方根如e10可能需要扩展到扩域求解多素数RSAnpqr增加CRT组合维度典型错误处理模式try: mp AMM(cp, e, p) except Exception as e: print(fAMM failed on p: {str(e)}) if no solution in str(e): try_alternative_approach(p)在Hackergame 2019的十次方根题中就需要在扩域GF(y^3)而非GF(y)中求解R.b PolynomialRing(GF(y^3)) g b^10 - z # 在三次扩域中求解5. 密码学启示与防御建议从工程实践角度这类攻击给密码系统设计者带来重要启示参数验证强制检查gcd(e,φ(n))1错误处理对异常参数给出明确警告系统监控检测异常解密请求对于CTF选手建议建立如下知识体系基础工具SageMath的有限域运算算法模板AMM、CRT等现成实现调试技巧中间结果验证方法# 参数安全检查示例 def validate_rsa_params(p, q, e): phi (p-1)*(q-1) if gcd(e, phi) ! 1: raise ValueError(e must be coprime with φ(n)) if e 2 or e phi: raise ValueError(e out of safe range)在真实密码系统中这类问题通常通过严格的参数生成算法避免。但对于安全研究人员理解这些边界情况的处理方法既能提升CTF竞赛能力也能加深对密码系统脆弱性的认知。