AMM(Adleman-Manders-Miller)在模 p 下开 e 次方根:e^t·s 分解迭代、单位根枚举与 CRT 组合
crypto/rsa · verified
一句话结论
当 RSA 的 e 与 p-1(或 q-1)不互素、简单约化后仍无法用整数开根恢复明文时,只要 e | p-1,就可以用 AMM 算法在 F_p 上求 x^e ≡ c 的一个根:把 p-1 分解为 e^t·s,t=1 时根为 c^{e^{-1} mod s},t≥2 时迭代消去 e 的幂并用 e 次非剩余校正;再乘遍 e 个单位根得到全部根,最后把模 p、模 q 的根两两 CRT 组合,按格式筛选明文。
原理
- 为什么常规解密失效:RSA 解密要求
gcd(e, φ(n)) = 1,否则d = e^{-1} mod φ不存在。若g = gcd(e, φ)较小,可先求m^g = c^{(e/g)^{-1} mod φ}再开g次整数根;但当e | p-1且e | q-1时g可能就等于e,约化后指数变成 1,得到的是m^e在模n下的余数,整数开根不再可用——必须在有限域内开e次根。 - AMM 的分解:设
p为奇素数且e | p-1,把p-1写成p-1 = e^t·s,其中e ∤ s。令d = e^{-1} mod s(e与s互素),则e d - 1 = k s。 - t = 1 的情况:此时
s = (p-1)/e。对e次剩余c,有(c^d)^e = c^{e d} = c^{1 + k s} = c·(c^s)^k ≡ c (mod p), 所以c^d mod p就是一个e次根。这一步与 Tonelli-Shanks 在p-1 = 2s时的c^{(s+1)/2}同源。 - t ≥ 2 的迭代:取一个
e次非剩余z(即z^{(p-1)/e} ≠ 1),令 a = z^{e^{t-1}·s} mod p(阶为e,用于表示单位根),b = c^{e d - 1} mod p,u = z^s mod p,h = 1。 对i = 1..t-1循环:δ = b^{e^{t-1-i}} mod p;- 在阶为
e的子群中求j ≡ -log_a(δ) (mod e)(e小则直接枚举j = 0..e-1,或让a^j = δ^{-1}); b ← b·(u^e)^j,h ← h·u^j,u ← u^e。 循环结束后c^d·h mod p即为一个e次根。本质是逐层消去e^t中的e因子,每一层用单位根修正当前结果。- 全部根:若
x0是一个根,则所有根为x0·ζ,其中ζ遍历e次单位根(ζ^e ≡ 1)。取随机α使ζ = α^{(p-1)/e} ≠ 1,则ζ^0..ζ^{e-1}给出全部e个单位根;模p侧共有gcd(e, p-1) = e个根。 - CRT 组合:设
n = p·q,把模p的e个根与模q的e个根两两 CRT,得到n上全部e^2个候选(一般更多,按各侧gcd计);再用pow(m, e, n) == c与明文格式(flag{、可打印字节)筛选出真实明文。 - 复杂度:每层一次模幂与小规模离散对数;
e很小时(CTF 常见 2/3/5/7)代价极低,e很大时子群离散对数是瓶颈——这也是 AMM 通常用于小e的原因。 - 常见实现误区:迭代中的
j是阶为e子群里的离散对数,必须按a^j ≡ δ^{-1}(或a^{-j} ≡ δ)求;不能用实数对数math.log(δ, a)代替,否则在t ≥ 2、e > 2时会算错。若目标例子恰好t = 1(如p = 131, e = 5时p-1 = 5·26),代码会走c^d分支而不暴露该错误,换一个e^2 | p-1的素数(如p = 101, e = 5,100 = 5^2·4)才会触发。
触发条件
- 已知
n或其分解p、q;已知e、c。 gcd(e, φ(n)) > 1,且e | p-1或e | q-1(至少一侧需要有限域开根;另一侧按gcd(e, p-1)的情况分别处理)。e较小,使单位根枚举与子群离散对数可行。- 明文是整数且
m < n;若m与n不互素可直接分解n,不走本链。 - 有明文格式/前缀可用于在多解中筛选。
利用步骤
- 分解
n得p、q(题给或通过提示/共模/弱素数等分解)。 - 计算
gcd(e, p-1)、gcd(e, q-1): - 若e ∤ p-1,用pow(c, e^{-1} mod (p-1), p)求唯一根或按gcd做约化; - 若e | p-1,用 AMM 求一个根,再枚举单位根得到全部p侧根。 - 对
q侧重复同样处理。 - 将
p侧与q侧根两两 CRT,得到候选m;验证pow(m, e, n) == c并转字节筛格式。
PoC
from itertools import product
from Crypto.Util.number import long_to_bytes
def amm(c, e, p):
"""p 为素数且 e | p-1,返回 x^e ≡ c (mod p) 的一个根。"""
t, s = 0, p - 1
while s % e == 0:
t += 1
s //= e
d = pow(e, -1, s) # e 在模 s 下可逆
if t == 1:
return pow(c, d, p)
z = 2
while pow(z, (p - 1) // e, p) == 1: # 找 e 次非剩余
z += 1
a = pow(z, e ** (t - 1) * s, p) # 阶为 e 的子群生成元
b = pow(c, e * d - 1, p)
u = pow(z, s, p)
h = 1
for i in range(1, t):
delta = pow(b, e ** (t - 1 - i), p)
if delta == 1:
j = 0
else:
# j = -log_a(delta) mod e:a^j ≡ delta^{-1}
target = pow(delta, -1, p)
j = next(j for j in range(1, e) if pow(a, j, p) == target)
b = b * pow(pow(u, e, p), j, p) % p
h = h * pow(u, j, p) % p
u = pow(u, e, p)
return pow(c, d, p) * h % p
def all_roots(x0, e, p):
"""由一个 e 次根得到全部 e 个根(e | p-1)。"""
z = 2
while pow(z, (p - 1) // e, p) == 1:
z += 1
zeta = pow(z, (p - 1) // e, p)
return list({x0 * pow(zeta, k, p) % p for k in range(e)})
def crt(a, p, b, q):
"""x ≡ a (mod p), x ≡ b (mod q)"""
return (a + p * ((b - a) * pow(p, -1, q) % q)) % (p * q)
# 示例:小素数验证(p=101 时 5^2 | 100,会走 t>=2 分支)
p, q, e, m = 101, 131, 5, 42
n = p * q
c = pow(m, e, n)
rp = all_roots(amm(c % p, e, p), e, p)
rq = all_roots(amm(c % q, e, q), e, q)
for a, b in product(rp, rq):
cand = crt(a, p, b, q)
if pow(cand, e, n) == c:
print(cand, long_to_bytes(cand))
说明:以上为按 AMM 原理重写并在小素数上自测通过的实现,非原文脚本;原文脚本的 math.log 求子群离散对数在 t ≥ 2 时不可用,已在此修正。
变体与关联
- e = 2:退化为 Tonelli-Shanks 求模平方根,AMM 的
t、j∈{0,1}推导与二次剩余一致;Rabin 类题目可复用。 - t = 1 快速路径:
e | p-1但e^2 ∤ p-1时直接c^{e^{-1} mod s},无需选取非剩余与迭代。 - 不互素但可约化:若
gcd(e, φ)较小且m^g < n,用“约化指数 + 整数开根”更简单,见 [[crypto-rsa-e-not-coprime-phi-reduced-inverse-root]]。 - 分域求根的其他实现:Sage 的
(x^e - c).roots()或nth_root可直接替代 AMM;实现层缺陷导致不互素的案例见 [[crypto-rsa-custom-pow-wrapper-odd-exponent-minus-one-root-crt]]。 - 扩展域:
F_{q^m}上的r次根可用 BV 算法(r | q-1且(m,r)=1等条件下复杂度更低)。 - 边界:
p非素数、e ∤ p-1、e很大导致子群离散对数不可行、或根数量爆炸且无格式可筛时,本链不适用。
检测与防御
- CTF/实现侧:密钥生成必须校验
gcd(e, φ(n)) = 1;避免让e整除p-1/q-1(例如避免小素数e搭配p ≡ 1 mod e的素数);使用标准库生成密钥,不自造e。 - 检测:解密代码出现“无模逆”后转向分域开根/枚举单位根/CRT 多解筛选;
e为小素数且p-1、q-1含其高次幂;同一密文对应多个合法明文候选(映射非单射)。 - 防御:参数初始化时断言
gcd(e, φ)=1并做已知明文自检dec(enc(m)) == m;对不满足条件的密钥直接拒绝使用并重新生成。