幂塔模合数:三因子分解 + 欧拉降幂逐素数求值 + CRT 后 XOR 解明文
ctf/crypto · verified
一句话结论
题目把 n 声称成 256 位素数,但实际可分解为三个素因子;对幂塔 l = 2^(2^t) mod n,先在每个素因子 p 上用费马小定理把指数降为 2^t mod (p-1),分别求 2^exp mod p,再用中国剩余定理合并得到 l,最后与密文 c 异或即可恢复明文。
原理
- 合数模幂可拆:若
n = p1*p2*p3,则l mod n可由l mod pi通过 CRT 唯一还原。 - 欧拉/费马降幂:对素数 p,
2^(p-1) ≡ 1 (mod p)(p≠2),所以2^(2^t) mod p = 2^(2^t mod (p-1)) mod p;指数2^t本身很大,但只需计算它对 p-1 的余数。 - 逐因子求值:
exp = pow(2, t, p-1),l_p = pow(2, exp, p);这里 t 是题目给定的幂塔高度参数。 - CRT 合并:三组同余
l ≡ l_p (mod p)用 CRT 得到l mod n。 - 异或解密:题目密文
c = m XOR l(或c = flag XOR l的整数形式),m = c XOR l,long_to_bytes得到 flag。 - 为什么容易误判:n 的位数/形式可能伪装成素数;用 FactorDB、
isprime或小因子试除可发现它实际是合数,从而把不可解的模幂拆成三个小模数。
触发条件
- 模数 n 实际为合数且可分解(小因子、FactorDB 可查、或题目给出因子线索)。
- 需要计算幂塔/超大指数模 n,直接
pow(2, 2**t, n)不可行。 - 密文与幂塔结果做 XOR 或简单线性组合。
- 已知幂塔高度 t 与密文 c。
利用步骤
- 检查 n 的素性;若声称素数但可疑,用 FactorDB/试除/
factorint分解,得到 p1、p2、p3。 - 对每个 pi 计算
exp_i = pow(2, t, pi-1),再算l_i = pow(2, exp_i, pi)。 - 用 CRT 合并
l_i得到l mod n。 - 计算
m = c ^ l(按题目定义的异或/加法关系),转字节得到 flag。 - 若 p=2 出现在因子中,单独处理(
2^k mod 2在 k≥1 时为 0)。
PoC
from Crypto.Util.number import long_to_bytes
t = 6039738711082505929
n = 127 * 841705194007 * 1005672644717572752052474808610481144121914956393489966622615553
c = 114092817888610184061306568177474033648737936326143099257250807529088213565247
primes = [127, 841705194007,
1005672644717572752052474808610481144121914956393489966622615553]
def crt(residues, moduli):
total, prod = 0, 1
for m in moduli:
prod *= m
for r, m in zip(residues, moduli):
p = prod // m
total += r * pow(p, -1, m) * p
return total % prod
residues = []
for p in primes:
exp = pow(2, t, p - 1)
residues.append(pow(2, exp, p))
l = crt(residues, primes)
print(long_to_bytes(c ^ l))
输出:
ISCTF{Euler_1s_v3ry|useful!!!!!}
变体与关联
- 因子数量/结构变体:两素数、三素数、含小因子;CRT 同样适用,模数两两互素即可。
- 降幂变体:用 Carmichael λ(n) 代替 φ(n) 可进一步减小指数;底数与模数不互素时需先剥离公因子。
- 关联:[[ctf-crypto-noise-crt-lattice-recovery]](带噪 CRT)、[[crypto-rsa-multiprime-partial-key-coppersmith]](多素数 RSA)。
- 边界:n 无法分解或因子过大时,幂塔计算不可行;若密文不是简单 XOR,需按题目公式逆运算。
检测与防御
- 检测:CTF 中先验证模数素性,不要轻信“256 位素数”的描述;检查是否存在小因子或 FactorDB 记录。
- 防御:密码协议使用标准大素数/安全模数,避免把合数当素数;不要用幂塔/XOR 作为加密方案。
- 加固:对模数做素性证明与结构检查;使用 AEAD 或标准 KEM/DEM。