三素数 RSA 高位泄露:Coppersmith 小根 + beta 逐档下调恢复 82 位未知低位
crypto/rsa · verified
一句话结论
三素数 RSA 中每个 512 位素数泄露高 430 位、仅低 82 位未知时,f(x)=p_hi·2^82+x 是模 p 的小根问题;Coppersmith 在 beta=1/3 的界 X≈N^(1/9)≈2^170 远大于 2^82,即使某个素数略低于 N^(1/3) 导致标准 beta 失败,逐档下调 beta(1/3→0.32→0.30→0.25→0.20)并用 Howgrave-Graham 格求解即可恢复三个因子。
原理
- 设 512 位素数
p = p_hi·2^82 + x,其中p_hi是已知高 430 位,x < 2^82未知。构造f(x)=p_hi·2^82+x,则f(x)≡0 (mod p),且x很小。 - Coppersmith 的单一小根定理:对模 N 的因子
p ≥ N^β,若X < N^(β²/δ)(δ 为多项式次数,这里 δ=1),可在多项式时间内求出|x|<X的根。三素数时p≈N^(1/3),取 β=1/3 得X≈N^(1/9)。N 为 1535 bit 时N^(1/9)≈2^170,远大于2^82,理论上轻松可解。 - 但
β=1/3的前提是p ≥ N^(1/3)。三个素数随机生成,某个因子可能略小于N^(1/3),此时该界不成立,Sage 的small_roots(beta=1/3)可能返回空。 - 解法是把 β 逐档下调(1/3、0.32、0.30、0.25、0.20),每档用对应的
X求根;对每个候选根x计算p_hi·2^82+x并检查是否整除 N。只要真实因子的 β 落在所选档位内就能出根。 - 另一个实测细节:Sage 自带
small_roots在 β=1/3 边界数值稳定性不佳;改用自实现的 Howgrave-Graham 格(参数 mm=6、tt=3)后稳定命中。恢复三个因子后phi=(p-1)(q-1)(r-1),标准 RSA 解密。
触发条件
- RSA 使用三个或更多素数,且每个素数的高位(约 430/512)被公开。
- 未知低位长度小于 Coppersmith 界(本例 82 bit < ~170 bit)。
- 攻击者能拿到 N、e、c 与各素数高位;模数位数量级允许格构造。
- 素数彼此独立,乘积等于 N,便于用候选根整除校验。
利用步骤
- 确认 N 为三素数乘积(1535 bit 左右),每个因子 512 bit,且服务端公开
p_hi/q_hi/r_hi。 - 估计未知位数
SHIFT(本例 82),构造f(x)=hi·2^SHIFT+x。 - 对每个 hi,从 β=1/3 开始逐档下调,调用
small_roots(X=2^SHIFT, beta=β)或自实现 Howgrave-Graham 格;候选根需满足N % cand == 0。 - 三个因子都恢复后计算
phi与d,解密密文;用p*q*r==N与明文格式交叉验证。 - 若标准
small_roots不稳定,增大格参数(mm/tt)或切换到自实现格基约减。
PoC
def recover_prime(hi, N, SHIFT, X):
for beta in (1/3, 0.32, 0.30, 0.25, 0.20):
for rt in (hi * 2**SHIFT + x).small_roots(X=X, beta=beta, epsilon=1/100):
cand = int(hi) * 2**SHIFT + int(rt)
if N % cand == 0:
return cand
raise ValueError("no root")
p = recover_prime(p_hi, N, 82, 2**82)
q = recover_prime(q_hi, N, 82, 2**82)
r = recover_prime(r_hi, N, 82, 2**82)
assert p * q * r == N
phi = (p - 1) * (q - 1) * (r - 1)
m = pow(c, pow(e, -1, phi), N)
# 自实现 Howgrave-Graham 格的参数示例(Sage)
# mm, tt = 6, 3;按 f(x)=hi*2^SHIFT+x 与模 N 构造格,
# LLL 后取短向量还原小根;再对候选做 N % cand == 0 校验。
变体与关联
- 变体:泄露高位/低位、多个素数共享高位、已知 p+q 或 p-q 的一部分,都可转成 Coppersmith 小根/近似公因子问题。
- 变体:双素数时 β=1/2,界为
N^(1/4);多素数时 β=1/k,界相应变小,需要更多泄露位或更强格。 - 关联:[[crypto-rsa-common-modulus]](共享模数)、[[crypto-rsa-pell-equation-prime-generation]](素数生成规律导致的分解)。
- 边界:未知位数超过界时无解;β 下调会增加格维数与计算量;Sage 版本/数值精度会影响边界行为;模数不是精确三因子乘积时需先确认因子个数。
检测与防御
- 检测:公钥/接口是否暴露素数高位、
p_hi等字段;密钥生成是否使用多素数且泄露部分因子;对 N 做因子个数与位长分布检查。 - 修复:不要公开素数的任何部分;使用标准双素数 RSA 或成熟库生成密钥;多素数场景下确保未知位远大于 Coppersmith 界。
- 加固:密钥生成后自检因子独立性;对 API 返回的公钥参数做最小化;定期轮换密钥;避免在调试接口返回
p_hi/q_hi/r_hi。