结构 RSA e=8:N=P(B−1)²+BS² 参数恢复与三层平方根解密
crypto/rsa · verified
一句话结论
当 RSA 模数由 p=(f·B+g)、q=(g·B+f) 生成时,N = P·(B−1)² + B·S²(P=f·g、S=f+g,B=2^128);由 N mod B = P mod B 取 P 的低 128 位、用 N // B³ 估算 P 的高位并小范围搜索,即可恢复 P、S,解二次方程得到 f、g 与 p、q;随后因 e=8=2³,对密文连续做 3 轮模 p/q 平方根 + CRT 组合,枚举候选明文找出 flag。
原理
- 模数结构:设
p = f·B + g、q = g·B + f,则p·q = f·g·(B²+1) + B·(f²+g²)。 令P=f·g、S=f+g,有f²+g² = S²−2P,代入得N = P·(B²−2B+1) + B·S² = P·(B−1)² + B·S²。 这就是题目给出的特殊结构。 - 低 128 位直接给出 P mod B:
N mod B = P·(B−1)² + B·S² mod B;(B−1)² ≡ 1 (mod B)、B·S² ≡ 0 (mod B),所以N mod B = P mod B。 - 高位估算:
P约 256 bit(f、g 各 128 bit 相乘),P·(B−1)²约 512 bit,B·S²约 386 bit;N // B³与 P 的高位只差少量进位(原文在 ±500 内搜索),组合P_cand = high·B + low后验证N − P_cand·(B−1)²能被 B 整除且商为完全平方,即得到 S。 - 恢复 f、g:
f、g是x² − S·x + P = 0的两根(韦达定理);判别式S²−4P开方后f=(S+√Δ)/2、g=(S−√Δ)/2。 - 恢复 p、q:
p=(f<<128)+g、q=(g<<128)+f,用p·q==N验证。 - e=8 的多层平方根:RSA 加密
c=m^8 mod N;解密等价于对 c 连续开 3 次平方根(因为8=2³)。在Z_p中,若p≡3 (mod 4),平方根为±c^((p+1)/4);分别对 p、q 求根后用 CRT 组合,每层最多 4 个根,3 层最多 64 个候选;对候选转字节检查flag/{即可筛出明文。 - 为什么可行:模数结构把 512 bit 的分解问题降为“已知低 128 位 + 高位小范围搜索 + 完全平方判定”;e=8 又允许逐层开方而不是求逆元(若 gcd(8,φ)≠1,常规
d=e^{-1} mod φ不存在)。这两个缺陷叠加使题目可解。
触发条件
- 已知
N、e=8、c,且题目/生成脚本提示模数由两个 128 bit 参数按上述结构生成(或能从 N 的低位/高位关系推断)。 p、q为素数且满足p≡q≡3 (mod 4)(否则(p+1)/4求根公式不适用,需要 Tonelli-Shanks)。c是模 N 的二次剩余(每一层都要能开方);明文较短/有可识别格式(如HECTF{...})。- 计算资源足够做 3 层根组合(最多 64 个候选)与候选解码。
利用步骤
- 取低位:
B=2^128,P_low = N % B。 - 估高位:
approx_high = N // B**3,在approx_high ± 500内枚举P_high,令P_cand = P_high·B + P_low。 - 验证 P/S:计算
rem = N − P_cand·(B−1)²;要求rem ≥ 0、rem % B == 0,令S2 = rem // B;若isqrt(S2)² == S2,则P=P_cand、S=isqrt(S2)。 - 解二次方程:
Δ=S²−4P,f=(S+isqrt(Δ))//2、g=(S−isqrt(Δ))//2;p=(f<<128)+g、q=(g<<128)+f;验证p*q==N。 - 三层开方:对
c做 3 轮:每轮对val mod p、val mod q用pow(a,(p+1)//4,p)求根(先检查pow(a,(p-1)//2,p)==1),再用 CRT 组合;收集所有候选。 - 筛 flag:对每个候选
long_to_bytes,检查是否包含flag/{或可 UTF-8 解码;输出明文。
PoC
核心恢复与开方代码(按原文脚本简化):
from math import isqrt
from Crypto.Util.number import long_to_bytes, inverse
B = 1 << 128
P_low = n % B
approx_high = n // (B ** 3)
for delta in range(-500, 500):
P = (approx_high + delta) * B + P_low
rem = n - P * ((B - 1) ** 2)
if rem < 0 or rem % B:
continue
S2 = rem // B
S = isqrt(S2)
if S * S != S2:
continue
D = S * S - 4 * P
f = (S + isqrt(D)) // 2
g = (S - isqrt(D)) // 2
p = (f << 128) + g
q = (g << 128) + f
assert p * q == n
break
def sqrt_mod_prime(a, p):
if pow(a, (p - 1) // 2, p) != 1:
return []
x = pow(a, (p + 1) // 4, p) # 需 p % 4 == 3
return [x, p - x]
def crt(rp, rq):
return (rp * q * inverse(q, p) + rq * p * inverse(p, q)) % (p * q)
cands = [c]
for _ in range(3):
nxt = []
for v in cands:
for rp in sqrt_mod_prime(v % p, p):
for rq in sqrt_mod_prime(v % q, q):
nxt.append(crt(rp, rq))
cands = list(set(nxt))
for m in cands:
b = long_to_bytes(m)
if b'flag' in b or b'{' in b:
print(b.decode())
原文输出:HECTF{this_is_a_flag_emm_is_a_true_flag_ok_all_right}。
变体与关联
- 变体:
B位数、e=4/16(更多/更少平方根层);p、q 不满足 3 mod 4 时用 Tonelli-Shanks;P/S 搜索范围更大时用 Coppersmith/格;把结构换成N=P·(B+1)²+B·S²等变体。 - 关联:[[crypto-rsa-rabin-random-square-root-oracle]](e=2 的平方根与 CRT 四根)、[[crypto-rsa-known-prime-sum-quadratic-factorization]](已知 p+q 解二次方程)、[[crypto-rsa-perfect-square-modulus-p-squared]](模数结构退化)、[[crypto-rsa-structurally-related-moduli-continued-fraction-crt]](另一类结构 RSA)。
- 同题:
ez_rsa用连分数恢复相邻素数;ez_ecc用点减半恢复 ECC 参数(见关联卡)。
检测与防御
- 密钥生成:不要用有代数关系的 f、g 生成 p、q;使用标准 RSA 密钥生成(随机大素数、足够熵),避免模数出现完全平方/低比特线性关系。
- 公钥指数:不要用
e=8等与 φ 不互素的指数;常规应使用e=65537且gcd(e,φ)=1,配合 OAEP 填充。 - 审计:检查 N 的低位/高位是否存在可预测结构、
N mod 2^k是否泄露因子;对自研 RSA 参数做随机性与结构测试。 - CTF 之外:真实协议中出现 e=8/结构化模数通常意味着实现错误;应轮换密钥并评估历史密文是否可解。